Paper Reading AI Learner

Fast Online Node Labeling for Very Large Graphs

2023-05-25 17:13:08
Baojian Zhou, Yifan Sun, Reza Babanezhad


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 一致性之间的更好的权衡中取得了更好的结果。



3D Action Action_Localization Action_Recognition Activity Adversarial Attention Autonomous Bert Boundary_Detection Caption Chat Classification CNN Compressive_Sensing Contour Contrastive_Learning Deep_Learning Denoising Detection Dialog Diffusion Drone Dynamic_Memory_Network Edge_Detection Embedding Embodied Emotion Enhancement Face Face_Detection Face_Recognition Facial_Landmark Few-Shot Gait_Recognition GAN Gaze_Estimation Gesture Gradient_Descent Handwriting Human_Parsing Image_Caption Image_Classification Image_Compression Image_Enhancement Image_Generation Image_Matting Image_Retrieval Inference Inpainting Intelligent_Chip Knowledge Knowledge_Graph Language_Model Matching Medical Memory_Networks Multi_Modal Multi_Task NAS NMT Object_Detection Object_Tracking OCR Ontology Optical_Character Optical_Flow Optimization Person_Re-identification Point_Cloud Portrait_Generation Pose Pose_Estimation Prediction QA Quantitative Quantitative_Finance Quantization Re-identification Recognition Recommendation Reconstruction Regularization Reinforcement_Learning Relation Relation_Extraction Represenation Represenation_Learning Restoration Review RNN Salient Scene_Classification Scene_Generation Scene_Parsing Scene_Text Segmentation Self-Supervised Semantic_Instance_Segmentation Semantic_Segmentation Semi_Global Semi_Supervised Sence_graph Sentiment Sentiment_Classification Sketch SLAM Sparse Speech Speech_Recognition Style_Transfer Summarization Super_Resolution Surveillance Survey Text_Classification Text_Generation Tracking Transfer_Learning Transformer Unsupervised Video_Caption Video_Classification Video_Indexing Video_Prediction Video_Retrieval Visual_Relation VQA Weakly_Supervised Zero-Shot