Abstract
This paper studies the online node classification problem under a transductive learning setting. Current methods either invert a graph kernel matrix with $\mathcal{O}(n^3)$ runtime and $\mathcal{O}(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 \textit{online relaxation} technique introduced by a series of works (Rakhlin et al.,2012; Rakhlin and Sridharan, 2015; 2017). We first prove an effective regret $\mathcal{O}(\sqrt{n^{1+\gamma}})$ when suitable parameterized graph kernels are chosen, then propose an approximate algorithm FastONL enjoying $\mathcal{O}(k\sqrt{n^{1+\gamma}})$ regret based on this relaxation. The key of FastONL is a \textit{generalized local push} method that effectively approximates inverse matrix columns and applies to a series of popular kernels. Furthermore, the per-prediction cost is $\mathcal{O}(\text{vol}({\mathcal{S}})\log 1/\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.
Abstract (translated)
本研究在一种递归学习设定下研究了在线节点分类问题。当前的方法要么使用 $\mathcal{O}(n^3)$ 的运行时长和 $\mathcal{O}(n^2)$ 的空间复杂度来翻转图的卷积矩阵，要么使用大量的随机连通树来采样，因此难以处理大型图。在这项工作中，我们基于一系列研究提出的 \textit{在线放松} 技术提出了改进，我们首先证明了当选择合适的参数化图kernel时，选择的卷积矩阵的有效 regret 为 $\mathcal{O}(\sqrt{n^{1+\gamma}})$，然后基于这个放松技术提出了一个基于这个放松技术的近似算法 FastONL，其有效 regret为 $\mathcal{O}(k\sqrt{n^{1+\gamma}})$。FastONL 的关键是一种 \textit{广义本地推送} 方法，有效地近似了逆矩阵列并适用于一系列流行的卷积kernel。此外，每个预测的成本为 $\mathcal{O}(\text{vol}({\mathcal{S}})\log 1/\epsilon)$ locally 依赖于具有线性内存成本的图。实验结果表明，我们的可扩展方法在 local 和 global 一致性之间的更好的权衡中取得了更好的结果。
URL
https://arxiv.org/abs/2305.16257
