Timezone: »
Poster
Fast Online Node Labeling for Very Large Graphs
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 *online relaxation* technique introduced by a series of works (Rakhlin et al., 2012; Rakhlin & 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 *generalized local push* method that effectively approximates inverse matrix columns and applies to a series of popular kernels. Furthermore, the perprediction cost is $\mathcal{O}(\operatorname{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.
Author Information
Baojian Zhou (Fudan University)
Baojian Zhou is an assistant professor of the School of Data Science at Fudan University. His interests are data mining and machine learning, especially mining and learning from largescale graph data.
Yifan Sun (Stony Brook University)
Reza Babanezhad (Samsung)
More from the Same Authors

2023 : DecisionAware ActorCritic with Function Approximation and Theoretical Guarantees »
Sharan Vaswani · Amirreza Kazemi · Reza Babanezhad · Nicolas Le Roux 
2023 Poster: Targetbased Surrogates for Stochastic Optimization »
Jonathan Lavington · Sharan Vaswani · Reza Babanezhad · Mark Schmidt · Nicolas Le Roux 
2022 Poster: Towards Noiseadaptive, Problemadaptive (Accelerated) Stochastic Gradient Descent »
Sharan Vaswani · Benjamin DuboisTaine · Reza Babanezhad 
2022 Oral: Towards Noiseadaptive, Problemadaptive (Accelerated) Stochastic Gradient Descent »
Sharan Vaswani · Benjamin DuboisTaine · Reza Babanezhad 
2022 Poster: Approximate FrankWolfe Algorithms over Graphstructured Support Sets »
Baojian Zhou · Yifan Sun 
2022 Spotlight: Approximate FrankWolfe Algorithms over Graphstructured Support Sets »
Baojian Zhou · Yifan Sun 
2021 Poster: InfiniteDimensional Optimization for ZeroSum Games via Variational Transport »
Lewis Liu · Yufeng Zhang · Zhuoran Yang · Reza Babanezhad · Zhaoran Wang 
2021 Spotlight: InfiniteDimensional Optimization for ZeroSum Games via Variational Transport »
Lewis Liu · Yufeng Zhang · Zhuoran Yang · Reza Babanezhad · Zhaoran Wang