Fast Online Node Labeling for Very Large Graphs

This paper studies the online node classification problem under a transductive learning setting. Current methods either invert a graph kernel matrix with O(n³) runtime and O(n²) space complexity or sample a large volume of random spanning trees, thus are difficult to scale to large graphs. In this work, we propose an improvement based on the online relaxation technique introduced by a series of works (Rakhlin et al., 2012; Rakhlin & Sridharan, 2015; 2017). We first prove an effective regret O(^√n^1+γ) when suitable parameterized graph kernels are chosen, then propose an approximate algorithm FASTONL enjoying O(k^√n^1+γ) regret based on this relaxation. The key of FASTONL is a generalized local push method that effectively approximates inverse matrix columns and applies to a series of popular kernels. Furthermore, the per-prediction cost is O(vol (S) log 1/ϵ) locally dependent on the graph with linear memory cost. Experiments show that our scalable method enjoys a better tradeoff between local and global consistency.