Timezone: »

 
Poster
Fast Online Node Labeling for Very Large Graphs
Baojian Zhou · Yifan Sun · Reza Babanezhad

Wed Jul 26 05:00 PM -- 06:30 PM (PDT) @ Exhibit Hall 1 #723
in Poster Session 4 »
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 per-prediction 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.
[ PDF]  [ Poster] 

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 large-scale graph data.

Yifan Sun (Stony Brook University)
Reza Babanezhad (Samsung)

More from the Same Authors