Inference-friendly Graph Compression for Graph Neural Networks

2025/04/17 by Yangxin Fan, Fan, Yangxin, Haolai Che +3 · 1 citation
Computer Science · #Advanced Graph Neural Networks #Explainable Artificial Intelligence (XAI) #FOS: Computer and information sciences #Graph Theory and Algorithms #Machine Learning (cs.LG)

paper · pdf · doi:10.48550/arxiv.2504.13034

openalex publication_date 2025/04/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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 G_c, to best preserve the inference results of M over G, such that the result can be directly inferred by accessing G_c 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 G_c 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.

Citations

• A Comprehensive Survey on Graph Reduction: Sparsification, Coarsening, and Condensation
• Search to Fine-tune Pre-trained Graph Neural Networks for Graph-level Tasks
• Everything is Connected: Graph Neural Networks
• Efficient Graph Neural Network Inference at Large Scale
• Graph neural networks for materials science and chemistry
• Detecting Anomalous Cryptocurrency Transactions: an AML/CFT Application of Machine Learning-based Forensics
• Survey on Graph Neural Network Acceleration: An Algorithmic Perspective
• Adaptive Transfer Learning on Graph Neural Networks
• Scaling Up Graph Neural Networks Via Graph Coarsening
• OGB-LSC: A Large-Scale Challenge for Machine Learning on Graphs
• A Unified Lottery Ticket Hypothesis for Graph Neural Networks
• Automorphic Equivalence-aware Graph Neural Network
• Degree-Quant: Quantization-Aware Training for Graph Neural Networks
• Expressive Power of Invariant and Equivariant Graph Neural Networks
• Open Graph Benchmark: Datasets for Machine Learning on Graphs
• Point-GNN: Graph Neural Network for 3D Object Detection in a Point Cloud
• Fast Graph Representation Learning with PyTorch Geometric
• Graph Neural Networks for Social Recommendation
• How Powerful are Graph Neural Networks?
• Survey and Taxonomy of Lossless Graph Compression and Space-Efficient Graph Representations
• AllenNLP: A Deep Semantic Natural Language Processing Platform
• Link Prediction Based on Graph Neural Networks
• Spectrally approximating large graphs with smaller graphs
• Graph Attention Networks
• Inductive Representation Learning on Large Graphs
• Semi-Supervised Classification with Graph Convolutional Networks
• Small-World Brain Networks Revisited
• Structural equivalence of individuals in social networks
• The Graph Neural Network Model

Related

• Embedding Compression with Hashing for Efficient Representation Learning in Large-Scale Graph
• FIT-GNN: Faster Inference Time for GNNs that 'FIT' in Memory Using Coarsening
• Accelerating Graph Neural Networks with a Novel Matrix Compression Format
• Reconstruction for Powerful Graph Representations
• STRIDE: Structure and Embedding Distillation with Attention for Graph Neural Networks