Fast Online Node Labeling for Very Large Graphs

MaRDI QIDQ6438010zbMATH OpenFDO

Authors Baojian Zhou, Yi-Fan Sun, Reza Babanezhad

Publication date 25 May 2023

Has companion code repository https://github.com/baojian/FastONL

Abstract: This paper studies the online node classification problem under a transductive learning setting. Current methods either invert a graph kernel matrix with $mathcalO(n^3)$ runtime and $mathcalO(n^2)$ 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 extit{online relaxation} technique introduced by a series of works (Rakhlin et al.,2012; Rakhlin and Sridharan, 2015; 2017). We first prove an effective regret $mathcalO(sqrt{n}^{1+gamma})$ when suitable parameterized graph kernels are chosen, then propose an approximate algorithm FastONL enjoying $mathcalO(ksqrt{n}^{1+gamma})$ regret based on this relaxation. The key of FastONL is a extit{generalized local push} method that effectively approximates inverse matrix columns and applies to a series of popular kernels. Furthermore, the per-prediction cost is $mathcalO(extvol(mathcalS)log1/epsilon)$ locally dependent on the graph with linear memory cost. Experiments show that our scalable method enjoys a better tradeoff between local and global consistency.

This page was built for publication: Fast Online Node Labeling for Very Large Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6438010)