TL;DR该研究提出一种基于在线松弛技术的 FastONL 算法，使用广义本地推方法有效逼近逆矩阵列，并针对一系列流行核提出近似算法，本文还证明了合适参数化图核被选中时可以实现有效的后悔，具体表现为 O (k 根号 (n^(1+γ)))。
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 co
我们提出了一种适用于未知特征生成过程的混合在线学习的、高效的预测方法，证明了该方法可在有限的 VC 类中实现具有次线性的遗憾上限，并在具有 α fat-shattering 维度的类中实现具有次线性的遗憾上限。此外，我们拓展了我们的结果到具有 K 个变化的分布转移场景，并为具有有限策略集合 H 和未知分布的 i.i.d. 生成的上下文以及敌对生成的成本的情境 K 臂赌博机建立了遗憾上限。
本文提出了一种新颖的流图半监督学习逼近方法，旨在捕捉标签分布的稀疏性并确保算法准确地传播标签，进一步将每个节点的空间复杂度降低到 O (1)，同时提供了适用于大型数据的分布式算法和为自然语言应用构建的图构建机制以及经过深度学习架构训练的鲁棒性图增强策略，实验结果证明该方法在内存占用上具有显著的降低，并且在性能上优于现有的最先进算法。