Inference-friendly Graph Compression for Graph Neural Networks
Yangxin Fan, Haolai Che, Yinghui Wu · 2025
Read Inference-friendly Graph Compression for Graph Neural Networks by Yangxin Fan, Haolai Che, Yinghui Wu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-13034.txt.
Introduction
Yangxin Fan, Haolai Che, and Yinghui Wu propose a way to shrink large graphs so that neural network models can read them faster, in a 2025 paper. These models work well on graph data, but running them on huge graphs costs a lot of time. Their scheme builds a small graph that gives nearly the same results as the full one, with little or no need to unpack it first.
They define when two points in a graph look the same to the model, and base the shrinking on that idea. Three versions trade size against accuracy in set ways, or protect key points of interest. Tests on many large graphs show the approach works well and runs fast.
Catalog record
| CREATOR | Yangxin Fan, Haolai Che, Yinghui Wu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 118 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-13034
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Inference-friendly Graph Compression for Graph Neural Networks Yangxin Fan, Haolai Che, Yinghui Wu Abstract . Graph Neural Networks ( 𝖦𝖭𝖭𝗌 \mathsf{GNNs} ) have demonstrated promising performance in graph analysis. Nevertheless, the inference process of 𝖦𝖭𝖭𝗌 \mathsf{GNNs} remains costly, hindering their applications for large graphs. This paper proposes inference-friendly graph compression ( 𝖨𝖥𝖦𝖢 \mathsf{IFGC} ), a graph compression scheme to accelerate 𝖦𝖭𝖭𝗌 \mathsf{GNNs} inference. Given a graph G G and a 𝖦𝖭𝖭 \mathsf{GNN} M M , an 𝖨𝖥𝖦𝖢 \mathsf{IFGC} computes a small compressed graph G c G_{c} , to best preserve the inference results of M M over G G , such that the result can be directly inferred by accessing G c G_{c} with no or little decompression cost. (1) We characterize 𝖨𝖥𝖦𝖢 \mathsf{IFGC} with a class of inference equivalence relation. The relation captures the node pairs in G G that are not distinguishable for 𝖦𝖭𝖭 \mathsf{GNN} inference. (2) We introduce three practical specifications of 𝖨𝖥𝖦𝖢 \mathsf{IFGC} for representative 𝖦𝖭𝖭𝗌 \mathsf{GNNs} : structural preserving compression ( 𝖲𝖯𝖦𝖢 \mathsf{SPGC} ), which computes G c G_{c} that can be directly processed by 𝖦𝖭𝖭 \mathsf{GNN} inference without decompression; ( α , r ) (\alpha,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. 1. Introduction Graph Neural Networks (GNNs) have shown promising performance in various analytical tasks such as node classification ( Kipf and Welling 2016 ) and link prediction ( Zhang and Chen 2018 ) . In general, a \mathsf{GNN} {\mathcal{M}} converts an input graph G (as a pair (X,A) of node feature matrix X and an adjacency matrix A ), to a vector representation (“embeddings”) {\mathcal{M}}(G) via multiple layers. For each node, each layer applies a same “node update function” to uniformly update its embedding as a weighted aggregation of embeddings from its neighbors, subsequently transforming it towards an output embedding. The training of {\mathcal{M}} is to optimize its model parameters (“weights”) and obtain a proper update function to make it best fits a set of training data in a training graph. Given an input (test) graph G , the inference of {\mathcal{M}} applies the node update function to generate output embeddings {\mathcal{M}}(G) (a matrix of node embeddings). {\mathcal{M}}(G) can be post-processed to task-specific output, such as class labels for node classification. Despite their promising performances, \mathsf{GNNs} incur expensive inference process when G is large ( Chen et al. 2020 ; Zeng et al. 2021 ; Zhou et al. 2021 ) . The emerging need for large-scale testing, fine-tuning and benchmarking of graph learning models, require fast inferences of \mathsf{GNNs} under various configurations. Consider the following scenarios. (1) Inference in large networks . For a graph G with |V| nodes and |E| edges (where V and E refers to its node and edge set), with on average F features per node, an L -layered \mathsf{GNN} M may typically take O(L|E|dF^{2}+L|V|F^{2}) time ( Chen et al. 2020 ) (as summarized in Table 3 ). This can be prohibitively expensive for large real-world graphs. (2) Real-time Inference. \mathsf{GNN} models have been developed for e.g., traffic analysis ( Peng et al. 2020 ) , social recommendation ( Fan et al. 2019 ) , energy forecasting ( Karimi et al. 2021 ; Fan et al. 2023 ; Ahmed et al. 2022 ) , cybersecurity ( Zhou et al. 2019 ) , computer vision ( Shi and Rajkumar 2020 ) , and edge devices ( Zhou et al. 2021 ) . Such scenarios often require real-time response at e.g., milliseconds ( Zhou et al. 2021 ) . In such cases, even a linear time inference of “small” \mathsf{GNNs} (when F and L are small constants) may still not be feasible for large graphs (when |V| and |E| are large). (3) Fine-tuning & Benchmarking . Fine-tuning and testing pre-trained \mathsf{GNNs} to adapt them for various domain-specific tasks is a routine process in \mathsf{GNN} -based data analysis for e.g., materials sciences, biomedicine, social science, and geosciences ( Han et al. 2021 ; Zhili et al. 2024 ; Zhou et al. 2020 ; Reiser et al. 2022 ; Veličković 2023 ) . Inference tests of large pool of “candidate” \mathsf{GNNs} over domain-specific graph data (such as knowledge graphs) is a cornerstone in such context. Fast \mathsf{GNN} inference can accelerate large-scale domain-specific testing and benchmarking. Several approaches have been developed to accelerate \mathsf{GNN} inference, by simplifying model architecture ( Peng et al. 2022 ) , (learning) to optimize inference process ( Tailor et al. 2020 ) , or data sampling ( Chen et al. 2021 ) . These methods typically works with specific \mathsf{GNN} {\mathcal{M}} , requires prior knowledge of its internals ( e.g., model parameter values), and may incur new computation overhead each time a different \mathsf{GNN} {\mathcal{M}} is specified. (a) Social role classification: a hospital network ( G_{1} ) can be “compressed” by merging nodes with equivalent social roles for testing a \mathsf{GCN} -based classifier (adapted from ( Borgatti and Everett 1992 ) , node attributes include Age, YoE (years of experience), and Dpt (department)). (b) Visualization of a fraction of real-world citation network ( Hu et al. 2020 ) ( |G|=1,335,586 ) and its compressed counterpart ( |G_{c}|=148,887 ) for a \mathsf{GraphSAGE} -based node classification. 88.6\% of nodes and edges are compressed, reducing inference cost by 92.0\% , achieving 12.5 times speed-up with up to 6.7\% loss of accuracy. Figure 1 . Compression Scheme to scale node classification. Compressing graphs for \mathsf{GNN} inference . Unlike prior “model-specific” approaches, we propose a model-agnostic, “ once-for-all ” graph compression scheme to accelerate \mathsf{GNN} inference, for a set of \mathsf{GNNs} . Consider a set of \mathsf{GNNs} \mathbb{M} (a \mathsf{GNN} “class”) with the same form of inference, which apply the same “type” of the node update function but only differs in model weights (see Example 1 ). The inference of a \mathsf{GNN} M over G can be characterized as an “inference query” ( Barceló et al. 2020 ; Geerts 2023 ) , which invokes the inference of {\mathcal{M}} to compute {\mathcal{M}}(G) . We advocate an “inference-friendly” graph compression scheme for \mathsf{GNN} inference at scale. Given \mathbb{M} and a large graph G , \circ It uses a compression function {\mathcal{C}} to compute a smaller counterpart G_{c} of G “once-for-all”, for any {\mathsf{GNN}}{\mathcal{M}}\in\mathbb{M} ; \circ For any inference query that requests {\mathcal{M}}(G) for a specific \mathsf{GNN} {\mathcal{M}}\in\mathbb{M} , it performs an inference directly over G_{c} instead of G to compute {\mathcal{M}}(G_{c}) , with a reduced time cost, such that {\mathcal{M}}(G_{c}) (approximately) equals {\mathcal{M}}(G) . Such a compression is desirable: (1) It readily reduces the cost for any single inference query that computes {\mathcal{M}}(G) ; (2) An inference query often does not require the entire output {\mathcal{M}}(G) but only a fraction {\mathcal{M}}(G,V_{T})\subseteq{\mathcal{M}}(G) of a specified test (node) set V_{T} of interests; (3) Multiple inference queries can be posed to request output from different \mathsf{GNNs} in \mathbb{M} in G . For any workload with inference queries that specify any