.png){kind=icon}
Return
Coarse-and-Learn: Efficient Online Node Labeling
.png){kind=icon}
PRE
AI
DOI：10.1007/978-981-95-4384-7_32.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We consider online node classification over a very large undirected graph, where a key step is the inverse of a large, sparse Laplacian matrix. We explore the benefits and limitations of graph coarsening, in which nodes not currently being labeled are summarized into supernodes, producing an informative compressed Laplacian at each step. This results in a computationally scalable method for very large graphs. We give kernel-dependent learning bounds of O(tr(M) + root epsilon ) where M is the inverse regularized kernel matrix, which can reduce to O(root N + root epsilon ) for the appropriate choice of kernel. Here, epsilon is the spectral error between the coarsened and uncoarsened matrix M. Our large-scale numerical experiments suggest comparable learning performance, for considerable computational cost reduction.
Keywords:
graph coarsening
online learning
Journal
N
IF:
0
Papers:
26
Citations:
0
Organization
Cited Papers
.png){kind=icon}
ShareSave
ShareSaveShareSaveShareSave
View more