Serving Graph Compression for Graph Neural Networks

Si Si, Felix Yu, Ankit Singh Rawat, Cho-Jui Hsieh, Sanjiv KumarICLR 2023 · OpenReview

TL;DR

Graph Neural Networks (GNNs) are powerful but notoriously difficult to deploy because they often require keeping the entire training graph in memory during inference. This paper introduces Virtual Node Graph (VNG), a method that compresses massive training sets into a tiny collection of synthetic "virtual nodes" that mimic the original graph's behavior. VNG reduces storage requirements by up to 70x with minimal loss in accuracy.

The Serving Bottleneck

In many real-world GNN applications—like social network analysis or recommendation systems—new "testing" nodes are often connected to existing "training" nodes. To make an accurate prediction for a new user, the GNN must propagate information from the neighbors it already knows.

This creates a massive "serving bottleneck." While the GNN model weights themselves might only take up a few megabytes, the training graph and its associated node features can take up gigabytes.

Serving size comparison across datasets

As shown above, the storage ratio of data to model can be staggering. For example, on the Reddit dataset, the GNN model is a lean 7.6MB, but the training data required to serve it is over 460MB. This makes deploying GNNs on edge devices or low-resource servers nearly impossible.

Existing solutions like model pruning or "coreset" selection (picking a subset of real nodes) often fail. Simply dropping nodes ignores the complex graph structure and significantly hurts the model's predictive power as the dropping rate increases.

Accuracy drop with random node dropping

The Virtual Node Graph (VNG) Method

To overcome these limitations, the authors propose the Virtual Node Graph (VNG) method. Instead of trying to find the "best" real nodes to keep, VNG constructs a small set of synthetic nodes with artificially designed features and connections.

The process involves two main steps:

  1. Finding Virtual Node Features: The authors use a weighted k-means algorithm. They don't just look at the raw input features; they concatenate features from all layers of the GNN to see how information evolves. The "weight" in the k-means ensures that nodes with more influence on the graph (higher degrees) have a larger say in forming the virtual nodes.
  2. Constructing the Virtual Adjacency Matrix: Once they have the nodes, they need to know how they connect. They formulate this as a low-rank least-squares problem. They solve for a small, factorized matrix that minimizes the "propagation error"—essentially ensuring that a signal passing through the virtual nodes looks almost identical to a signal passing through the original, massive training graph.

The beauty of this approach is that it is "plug-and-play." You don't need to retrain your GNN or change its architecture; you simply swap the original training set for the compressed VNG during the inference stage.

Datasets and Evaluation

The authors evaluated VNG on four standard large-scale node classification benchmarks:

  • ogbn-arxiv: A citation network of computer science papers.
  • Reddit: A social graph where nodes are posts and edges represent user comments.
  • ogbn-products: An Amazon product co-purchase network.
  • Amazon2M: A massive product graph with over 2 million nodes.

Key Insights

  • The Data is the Bottleneck, Not the Model: Compressing the model weights (the usual approach in AI) yields diminishing returns compared to compressing the graph itself.
  • Feature-Graph Synergy: Standard compression techniques like SVD or Sparsification fail because they treat node features and the graph structure as separate entities. VNG succeeds by optimizing them jointly to preserve the GNN's forward pass.
  • Virtual > Real: By creating synthetic nodes rather than selecting real ones, the algorithm has more "degrees of freedom" to represent the aggregate information of the training set, leading to much higher compression ratios for the same level of accuracy.

Key Results

The results demonstrate that VNG is a game-changer for GNN deployment:

  • Massive Space Savings: VNG achieved compression rates of 37.5x on Arxiv, 41.1x on Reddit, and 69.1x on Product datasets.
  • Accuracy Preservation: Even at these extreme compression levels, the drop in accuracy was often less than 1%. For instance, on Reddit, VNG maintained ~91% accuracy with only 5% of the nodes, while other methods like random dropping or k-means fell to the 70-80% range.
  • Inference Speedup: Because the "neighborhood" the GNN has to look at is now much smaller, inference becomes significantly faster, which is critical for real-time online applications.

Limitations and Future Work

While VNG is highly effective, the authors note a few areas for improvement:

  • Extreme Compression Limits: If you try to compress the graph beyond 50x-100x, the performance loss starts to become more noticeable.
  • Architecture Specificity: The current derivation is optimized for Graph Convolutional Networks (GCNs). While the authors show it works for GraphSAGE, further work could generalize the optimization for more complex attention-based models like GAT.
  • Hybrid Approaches: The authors suggest that VNG could be combined with traditional quantization (reducing the precision of numbers) to squeeze the storage requirements even further.

Summary updated

Abstract

Serving a GNN model online is challenging --- in many applications when testing nodes are connected to training nodes, one has to propagate information from training nodes to testing nodes to achieve the best performance, and storing the whole training set (including training graph and node features) during inference stage is prohibitive for large-scale problems. In this paper, we study graph compression to reduce the storage requirement for GNN in serving. Given a GNN model to be served, we propose to construct a compressed graph with a smaller number of nodes. In serving time, one just needs to replace the original training set graph by this compressed graph, without the need of changing the actual GNN model and the forward pass. We carefully analyze the error in the forward pass and derive simple ways to construct the compressed graph to minimize the approximation error. Experimental results on semi-supervised node classification demonstrate that the proposed method can significantly reduce the serving space requirement for GNN inference.
BibTeX
@inproceedings{si2023serving,
  author = {Si Si and Felix Yu and Ankit Singh Rawat and Cho-Jui Hsieh and Sanjiv Kumar},
  title = {{Serving Graph Compression for Graph Neural Networks}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=T-qVtA3pAxG},
}
Figure