Sketch-GNN: Scalable Graph Neural Networks with Sublinear Training Complexity

Mucong Ding, Tahseen Rabbani, Bang An, Evan Z. Wang, Furong Huang

Abstract

Graph Neural Networks (GNNs) are widely applied to graph learning problems such as node classification. When scaling up the underlying graphs of GNNs to a larger size, we are forced to either train on the complete graph and keep the full graph adjacency and node embeddings in memory (which is often infeasible) or mini-batch sample the graph (which results in exponentially growing computational complexities with respect to the number of GNN layers). This paper proposes a sketch-based algorithm whose training time and memory grow sublinearly with respect to graph size by training GNNs atop a few compact sketches of graph adjacency and node embeddings. Based on polynomial tensor-sketch (PTS) theory, our framework provides a novel protocol for sketching non-linear activations and graph convolution matrices in GNNs. In addition, we develop a locality-sensitive hashing (LSH) technique that can be trained to improve the quality of sketches. Experiments on large-graph benchmarks demonstrate the scalability and competitive performance of our Sketch-GNNs versus their full-size GNN counterparts.

Introduction

Scaling Graph Neural Networks (GNNs) to massive graphs containing millions or billions of nodes is a notorious bottleneck in machine learning. Standard approaches typically fall into two camps, both with significant flaws. Full-batch training requires storing the entire graph and all intermediate node embeddings in GPU memory—an $O(n)$ linear dependence that quickly exceeds hardware limits. Conversely, mini-batch sampling reduces memory but often leads to "neighbor explosion," where the number of nodes to be processed grows exponentially with the number of layers.

Existing "sublinear" methods often rely on graph coarsening or condensation, which require expensive preprocessing that can take longer than the actual training. Sketch-GNN addresses this gap by introducing a framework where the training complexity does not grow linearly with the number of nodes ($n$), achieving sublinear training complexity in both time and memory without sacrificing accuracy or requiring heavy preprocessing.

Methodology

The core innovation of Sketch-GNN is the application of Polynomial Tensor Sketch (PTS) theory to GNN operations. Unlike most sketching techniques that focus on linear weights or gradients, Sketch-GNN sketches the activation functions themselves.

  • Sketching the Non-Linearity: By approximating non-linearities (like ReLU or Sigmoid) as power series, the authors can perform message passing entirely within a compressed "sketched" space of dimension $c$ (where $c \ll n$).
  • Two-Sided Sketching: The framework sketches both the $n \times n$ adjacency matrix and the $n \times d$ node feature matrix into compact $c \times c$ and $c \times d$ structures.
  • Learnable Locality Sensitive Hashing (LSH): Standard sketching uses fixed, random hash functions. Sketch-GNN introduces a learnable LSH that is updated online during training using a triplet loss. This ensures that nodes with similar embeddings are hashed into the same "buckets," improving the quality of the sketch as the model learns better representations.
  • Training in the Sketch Space: Crucially, the model never "unsketches" back to the full graph size during training. It updates weights based on the sketched representations, maintaining sublinear complexity throughout the epoch with zero preprocessing overhead.

Experimental Evaluation

The authors evaluated Sketch-GNN on a mix of classic benchmarks and large-scale graphs, including ogbn-arxiv (169K nodes), Reddit (233K nodes), and ogbn-products (2.4M nodes). A key insight from these experiments is that the "sketch ratio" ($c/n$) required to maintain performance actually decreases as the graph size $n$ increases, reinforcing the sublinear nature of the algorithm.

Table 1: Performance comparison on the ogbn-arxiv benchmark across different GNN architectures and sketch ratios.

As shown in Table 1, Sketch-GNN achieves competitive accuracy compared to the "Full-Graph" oracle. On the ogbn-arxiv dataset, Sketch-GNN reached approximately 70.5% accuracy with a 0.4 sketch ratio for GAT, nearly matching the oracle (~72.3%) and significantly outperforming graph coarsening baselines. Furthermore, the framework demonstrates architecture agnosticism, showing consistent performance across GCN, GraphSAGE, and GAT, whereas competing methods like graph condensation often generalize poorly across different architectures.

Conclusion and Future Work

Sketch-GNN represents a significant advancement in scalable GNN training, offering a path to handle massive datasets on standard hardware. While the approximation of non-linear activations introduces a slight performance ceiling and potential error accumulation in very deep networks, the framework's memory efficiency and lack of preprocessing overhead make it highly practical. Future work aims to optimize implementation with lower-level CUDA kernels and extend theoretical error bounds to more complex attention-based models.

Summary updated

Abstract

Graph Neural Networks (GNNs) are widely applied to graph learning problems such as node classification. When scaling up the underlying graphs of GNNs to a larger size, we are forced to either train on the complete graph and keep the full graph adjacency and node embeddings in memory (which is often infeasible) or mini-batch sample the graph (which results in exponentially growing computational complexities with respect to the number of GNN layers). Various sampling-based and historical-embedding-based methods are proposed to avoid this exponential growth of complexities. However, none of these solutions eliminates the linear dependence on graph size. This paper proposes a sketch-based algorithm whose training time and memory grow sublinearly with respect to graph size by training GNNs atop a few compact sketches of graph adjacency and node embeddings. Based on polynomial tensor-sketch (PTS) theory, our framework provides a novel protocol for sketching non-linear activations and graph convolution matrices in GNNs, as opposed to existing methods that sketch linear weights or gradients in neural networks. In addition, we develop a locality-sensitive hashing (LSH) technique that can be trained to improve the quality of sketches. Experiments on large-graph benchmarks demonstrate the scalability and competitive performance of our Sketch-GNNs versus their full-size GNN counterparts.
BibTeX
@inproceedings{ding2022sketch,
  author = {Mucong Ding and Tahseen Rabbani and Bang An and Evan Z. Wang and Furong Huang},
  title = {{Sketch-GNN: Scalable Graph Neural Networks with Sublinear Training Complexity}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=swMG8AtauM7},
}
Figure