# Inference-friendly Graph Compression for Graph Neural Networks

arXiv: https://arxiv.org/abs/2504.13034 · HTML: https://mlsanity.com/paper/2504.13034/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 30 of its 62 references that are in the map.
- First posted on arXiv 17 Apr 2025.

## Builds on (most cited first, 30 of 30)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [AllenNLP: A Deep Semantic Natural Language Processing Platform](https://mlsanity.com/paper/1803.07640/) (2018)
- [Point-GNN: Graph Neural Network for 3D Object Detection in a Point Cloud](https://mlsanity.com/paper/2003.01251/) (2020)
- [OGB-LSC: A Large-Scale Challenge for Machine Learning on Graphs](https://mlsanity.com/paper/2103.09430/) (2021)
- [Graph neural networks for materials science and chemistry](https://mlsanity.com/paper/2208.09481/) (2022)
- [A Unified Lottery Ticket Hypothesis for Graph Neural Networks](https://mlsanity.com/paper/2102.06790/) (2021)
- [Expressive Power of Invariant and Equivariant Graph Neural Networks](https://mlsanity.com/paper/2006.15646/) (2020)
- [Degree-Quant: Quantization-Aware Training for Graph Neural Networks](https://mlsanity.com/paper/2008.05000/) (2020)
- [Everything is Connected: Graph Neural Networks](https://mlsanity.com/paper/2301.08210/) (2023)
- [Scaling Up Graph Neural Networks Via Graph Coarsening](https://mlsanity.com/paper/2106.05150/) (2021)
- [A Comprehensive Survey on Graph Reduction: Sparsification, Coarsening, and Condensation](https://mlsanity.com/paper/2402.03358/) (2024)
- [Spectrally approximating large graphs with smaller graphs](https://mlsanity.com/paper/1802.07510/) (2018)
- [Adaptive Transfer Learning on Graph Neural Networks](https://mlsanity.com/paper/2107.08765/) (2021)
- [Parallel and Distributed Graph Neural Networks: An In-Depth Concurrency Analysis](https://mlsanity.com/paper/2205.09702/) (2022)
- [Survey on Graph Neural Network Acceleration: An Algorithmic Perspective](https://mlsanity.com/paper/2202.04822/) (2022)
- [Small-World Brain Networks Revisited](https://mlsanity.com/paper/1608.05665/) (2016)
- [Search to Fine-tune Pre-trained Graph Neural Networks for Graph-level Tasks](https://mlsanity.com/paper/2308.06960/) (2023)
- [Survey and Taxonomy of Lossless Graph Compression and Space-Efficient Graph Representations](https://mlsanity.com/paper/1806.01799/) (2018)
- [Efficient Graph Neural Network Inference at Large Scale](https://mlsanity.com/paper/2211.00495/) (2022)
- [Graph-Skeleton: ~1% Nodes are Sufficient to Represent Billion-Scale Graph](https://mlsanity.com/paper/2402.09565/) (2024)
- [Automorphic Equivalence-aware Graph Neural Network](https://mlsanity.com/paper/2011.04218/) (2020)
- [Detecting Anomalous Cryptocurrency Transactions: an AML/CFT Application of Machine Learning-based Forensics](https://mlsanity.com/paper/2206.04803/) (2022)
- [Learning Graph Neural Networks using Exact Compression](https://mlsanity.com/paper/2304.14793/) (2023)

## Abstract (arXiv)

Graph Neural Networks (GNNs) have demonstrated promising performance in graph analysis. Nevertheless, the inference process of GNNs remains costly, hindering their applications for large graphs. This paper proposes inference-friendly graph compression (IFGC), a graph compression scheme to accelerate GNNs inference. Given a graph G and a GNN M, an IFGC computes a small compressed graph Gc, to best preserve the inference results of M over G, such that the result can be directly inferred by accessing Gc with no or little decompression cost. (1) We characterize IFGC with a class of inference equivalence relation. The relation captures the node pairs in G that are not distinguishable for GNN inference. (2) We introduce three practical specifications of IFGC for representative GNNs: structural preserving compression (SPGC), which computes Gc that can be directly processed by GNN inference without decompression; (α, r)-compression, that allows for a configurable trade-off between compression ratio and inference quality, and anchored compression that preserves inference results for specific nodes of interest. For each scheme, we introduce compression and inference algorithms with guarantees of efficiency and quality of the inferred results. We conduct extensive experiments on diverse sets of large-scale graphs, which verifies the effectiveness and efficiency of our graph compression approaches.