Fast online node labeling with graph subsampling
Large data applications rely on storing data in massive, sparse graphs with millions to trillions of nodes. Graph-based methods, such as node prediction, aim for computational efficiency regardless of graph size. Techniques like localized approximate personalized page rank (APPR) solve sparse linear systems with complexity independent of graph size, but is in terms of the maximum node degree, which can be much larger in practice than the average node degree for real-world large graphs. In this paper, we consider an \emph{online subsampled APPR method}, where messages are intentionally dropped at random. We use tools from graph sparsifiers and matrix linear algebra to give approximation bounds on the graph's spectral properties ($O(1/\epsilon^2)$ edges), and node classification performance (added $O(n\epsilon)$ overhead).
Code (0)
등록된 구현이 없습니다.
Tasks
Computational EfficiencyNode ClassificationSimilar Papers 제목 키워드 기반
Subsampling of Correlated Graph Signals
Graph signals are functions of the underlying graph. When the edge-weight between a pair of nodes is high, the corresponding signals generally have a higher correlation. As a result, the signals can be represented in ter…
Fast Online Node Labeling for Very Large Graphs
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…
Node ClassificationTransductive LearningSubsampling Graphs with GNN Performance Guarantees
How can we subsample graph data so that a graph neural network (GNN) trained on the subsample achieves performance comparable to training on the full dataset? This question is of fundamental interest, as smaller datasets…
Graph Neural NetworkModel SelectionIsing on the Graph: Task-specific Graph Subsampling via the Ising Model
Reducing a graph while preserving its overall structure is an important problem with many applications. Typically, reduction approaches either remove edges (sparsification) or merge nodes (coarsening) in an unsupervised …
Graph ClassificationGraph Neural NetworkImage SegmentationSemantic SegmentationConvolutional Neural Network Architectures for Signals Supported on Graphs
Two architectures that generalize convolutional neural networks (CNNs) for the processing of signals supported on graphs are introduced. We start with the selection graph neural network (GNN), which replaces linear time …
Authorship AttributionGraph Neural Network