Fast Semi-supervised Learning on Large Graphs: An Improved Green-function Method
This work addresses a specific computational bottleneck in graph-based semi-supervised learning, offering an incremental improvement for researchers and practitioners dealing with large-scale graph data.
The paper tackles the instability of the Green-function method for semi-supervised learning on large sparse graphs by proposing an improved optimization-based approach, achieving enhanced efficiency, accuracy, and stability in experiments.
In the graph-based semi-supervised learning, the Green-function method is a classical method that works by computing the Green's function in the graph space. However, when applied to large graphs, especially those sparse ones, this method performs unstably and unsatisfactorily. We make a detailed analysis on it and propose a novel method from the perspective of optimization. On fully connected graphs, the method is equivalent to the Green-function method and can be seen as another interpretation with physical meanings, while on non-fully connected graphs, it helps to explain why the Green-function method causes a mess on large sparse graphs. To solve this dilemma, we propose a workable approach to improve our proposed method. Unlike the original method, our improved method can also apply two accelerating techniques, Gaussian Elimination, and Anchored Graphs to become more efficient on large graphs. Finally, the extensive experiments prove our conclusions and the efficiency, accuracy, and stability of our improved Green's function method.