Not All Neighbors Matter: Understanding the Impact of Graph Sparsification on GNN Pipelines

arXiv:2603.06952 · cs.LG, cs.DB · Submitted 2026-08-17 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "Not All Neighbors Matter: Understanding the Impact of Graph Sparsification on GNN Pipelines".

Jane: The paper was written by Yuhang Song, Naima Abrar Shami, Romaric Duvignau and Vasiliki Kalavri from Boston University and Chalmers University of Technology.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Jane: We also have Lu with us today — senior AI researcher at Tsinghua.

Tom: We also have Meng with us today — lead engineer at a mysterious AI startup.

Jane: We also have Lalam with us today — the in-house Large Language Model.

Tom: Alright, let's get started.

Title and Authors: Tom: Welcome back, everyone! We're looking at a paper called "Not All Neighbors Matter: Understanding the Impact of Graph Sparsification on GNN Pipelines" — and honestly, that title alone tells you so much.

Jane: It really does, Tom. The authors are Yuhang Song, Naima Abrar Shami, Romaric Duvignau, and Vasiliki Kalavri, from Boston University and Chalmers University of Technology. And the core question they're asking is pretty simple: when you're training a graph neural network, do you actually need every single edge in the graph?

Tom: And the answer, based on their experiments, seems to be no. Which is wild when you think about it. We've been building these massive systems to handle billion-edge graphs, and this team is saying, hey, maybe we can just remove a bunch of edges before we even start training.

Jane: Right. And the intuition is that real-world graphs are noisy and redundant. Think about a social network — you might have thousands of connections, but only a handful of them really matter for predicting what you'll do next. The rest is just noise.

Tom: Exactly. And what they're proposing is graph sparsification as a pre-processing step. You shrink the graph first, then train your GNN on the smaller version. No changes to the model, no changes to the training algorithm. Just a smaller input.

Jane: And the results are pretty striking. On the PubMed dataset, random sparsification actually improved GAT accuracy by six point eight percent. That's not just preserving accuracy — that's making the model better.

Tom: Which is counterintuitive, right? You'd think removing data would hurt. But it turns out, sometimes the noise was holding the model back. By removing edges, you're kind of forcing the model to focus on the signal.

Jane: And that's the regularization effect. It's like when you're studying for an exam and you throw away your messy notes and keep only the clean summary. You end up learning the material better.

Tom: Now, the authors also found that the benefits scale up. On the Products graph, which has over two million nodes, the K-Neighbor sparsifier made model serving eleven point seven times faster with only a zero point seven percent accuracy drop. That's a huge win for anyone running these models in production.

Jane: And that's what I love about this paper — it's not just theory. They built an actual framework that works with DGL and PyG, so people can start using this tomorrow.

Tom: So the big picture here is that we've been over-engineering our systems to handle graphs that are bigger than they need to be. And this paper is saying, maybe the answer isn't more hardware — it's less data.

Jane: Well, less noisy data. That's the nuance. And I think that's going to be a recurring theme as we dig into the methodology and the results. There's a lot more to unpack here.

Tom: Absolutely. Next up, we're going to break down what they actually did — the framework, the sparsification methods, and how they ran their experiments. Stick around.

Paper Summary: Jane: So, Tom, we've established that the title is promising. Now let's talk about what this paper actually does. The team built an experimental framework that lets you systematically test how different sparsification methods affect GNN performance.

Tom: And that's the key word — systematically. Before this, people were testing sparsification in isolation, on one model, on small datasets. This paper runs four sparsification methods across four GNN architectures and five real-world graphs.

Jane: Let's name those methods, because they're pretty clever. You've got Random, which just removes edges at random. K-Neighbor, which keeps up to K edges per node. Rank Degree, which starts from seed nodes and adds high-degree neighbors. And Local Degree, which keeps edges to your most-connected neighbors.

Tom: And each one has a different philosophy. Random is pure simplicity. K-Neighbor guarantees every node keeps some connectivity. Rank Degree and Local Degree both prioritize high-degree nodes, but in different ways.

Jane: Right. And the models they tested are the big ones — GCN, GraphSAGE, GAT, and SGFormer, which is a graph transformer. So they're covering the spectrum from classic convolution to modern attention.

Tom: Now here's what I found fascinating. They didn't just measure final accuracy. They measured time to convergence, time to reach a target accuracy, inference speed on sparsified graphs, and even whether the pre-processing cost pays for itself.

Jane: That last one is so important for practical use. Because sparsification takes time too — you're running an algorithm to decide which edges to remove. The question is, does that upfront cost get recovered by faster training?

Tom: And the answer, for most cases, is yes. On the Products dataset, nearly every method-model combination amortized the pre-processing cost in a single training run. K-Neighbor's sixteen seconds of pre-processing saved ninety-six seconds for GCN and one thousand four hundred ninety seconds for GraphSAGE.

Jane: That's a massive return on investment. And it gets better on larger graphs. The speedups on Papers100M — that's a graph with one hundred eleven million nodes — were substantial.

Tom: But here's the thing, Jane. It's not all good news. Rank Degree, which sounds great in theory, actually caused severe accuracy drops on the larger datasets. Like ten to twenty-eight percentage points on Arxiv, Products, and Papers100M.

Jane: That's a cautionary tale. Not all sparsification is created equal. The method matters, and the graph matters. What works on a small, dense graph might fail on a large, sparse one.

Tom: And that's why their framework is so valuable. It lets you test these trade-offs before you commit to a production pipeline.

Jane: Exactly. And I think the most exciting finding is that K-Neighbor consistently hit that sweet spot — good compression, minimal accuracy loss, and real speedups. It's the workhorse method.

Tom: So the summary is: sparsification works, but you have to choose wisely. And the authors have given us the tools to do that. Next, we're going to dig into the specific improvements they suggest — the parameter sweeps and the practical guidance.

Improvements Suggested: Tom: Alright Jane, we've covered what they did. Now let's talk about what they suggest people actually do differently. Because this paper isn't just a study — it's a practical guide.

Jane: And the biggest suggestion is pretty simple: don't assume you need the full graph. Before you scale out your distributed training system, try sparsifying the graph first. It might save you a lot of money and complexity.

Tom: They even did parameter sweeps to help you choose. On the Products dataset, they varied the compression level for each method and tracked accuracy and training time. And the results give you clear guidance.

Jane: Let's talk about Random first. It degrades gracefully. Even at seventy-five percent edge removal, you only lose one to three percent accuracy. So if you're not sure what to use, Random is a safe default for moderate compression.

Tom: And K-Neighbor with K equals five is the sweet spot. It removed ninety-one point six percent of edges on Products while losing less than one percent accuracy for GCN and GraphSAGE. That's remarkable compression with almost no cost.

Jane: But they also warn against going too aggressive. K equals three pushes reduction to ninety-four point seven percent, but the accuracy drop becomes noticeable. So there's a cliff you can fall off.

Tom: Now, Rank Degree is the cautionary tale. Their sweep showed that no matter how you tune it, it performs poorly on large graphs. The method is just too aggressive — it removes too much structural information.

Jane: And Local Degree gives you a nice dial. You can set alpha to zero point nine and keep forty-five percent of edges with minimal loss, or set it to zero point two five and remove ninety-five percent of edges with only three to four percent degradation. It's the most tunable option.

Tom: So the practical advice is: start with K-Neighbor, K equals five. If you need more compression, try Local Degree and tune alpha. Avoid Rank Degree for large graphs.

Jane: And they also suggest something clever — cross-graph inference. You train on the original graph, then serve on the sparsified graph. No retraining needed. On Products, that gave an eleven point seven times speedup for GAT with only a zero point seven percent accuracy drop.

Tom: That's huge for deployment. You train once, and then you can serve multiple sparsified versions depending on your latency budget.

Jane: And the framework they built makes all of this easy. You can save the sparsified graph to disk, so you only pay the pre-processing cost once. Then you can train multiple models on it.

Tom: So the improvement here isn't just a new algorithm — it's a new workflow. Sparsify first, then train, then serve on the compressed graph. And the paper gives you the tools and the guidance to do it right.

Jane: And I think that's going to have real impact. Not just for researchers, but for anyone running GNNs in production. We're going to wrap up with our final thoughts on the paper next.

Conclusion: Jane: Alright Tom, time to wrap up our discussion of "Not All Neighbors Matter: Understanding the Impact of Graph Sparsification on GNN Pipelines." And I have to say, this paper left me feeling optimistic.

Tom: Me too, Jane. The core message is that we've been carrying around a lot of unnecessary baggage. Real-world graphs are noisy and redundant, and this paper shows that removing that noise can actually help.

Jane: And the evidence is strong. Across all the models they tested, there was always at least one sparsification method that matched or exceeded the original graph's accuracy. That's not a fluke — that's a pattern.

Tom: The K-Neighbor sparsifier is the star of the show. It consistently delivered strong compression with minimal accuracy loss, and the speedups on large graphs were dramatic. On Papers100M, it made training and inference substantially faster.

Jane: And they didn't just report accuracy — they measured everything. Time to convergence, time to target accuracy, inference speed, pre-processing overhead. That's the kind of thorough evaluation that makes results trustworthy.

Tom: Now, there are caveats. Rank Degree failed on large graphs. And aggressive compression can hurt. But the framework they built lets you find the right operating point for your specific use case.

Jane: And that framework is open source. So anyone can start using these techniques tomorrow. That's what makes this paper impactful — it's not just theory, it's a tool.

Tom: I also appreciate that they're honest about limitations. They focused on edge reduction, not node reduction. And they only tested four sparsification methods. There's room to expand.

Jane: But as a first comprehensive study, it's really valuable. It gives us a map of the territory, and it points to where future work should go.

Tom: So our takeaway for the listeners: before you buy more GPUs or build a distributed system, try sparsifying your graph first. It might save you a lot of time and money.

Jane: And with that, we're saying goodbye to this paper. Thanks to the authors for the great work, and thanks to you for listening. We'll be back with the next paper soon.

Tom: Until then, keep your graphs lean and your models accurate. See you next time!

Yuhang Song, Naima Abrar Shami, Romaric Duvignau, Vasiliki Kalavri

Boston University · Chalmers University of Technology

cs.LG, cs.DB

Submitted: 2026-08-17

Updated: 2026-08-18

Code: https://github.com/qitianwu/SGFormer

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 84/100

The gist: The paper addresses the fundamental question of "how much of the graph structure is actually necessary for effective learning" in Graph Neural Networks (GNNs).

Key concepts

Graph Sparsification
This is a pre-processing step where the large, noisy graph being used for GNN training is shrunk by removing redundant edges. The goal is to reduce complexity without losing critical information, making the model more efficient.
GNN Pipelines
Graph Neural Networks (GNNs) are machine learning models designed to operate on graph-structured data. This paper focuses on optimizing the entire process of training and deploying these pipelines by using a smaller, sparser input graph.
K-Neighbor Sparsifier
One of the methods discussed, K-Neighbor keeps up to K edges per node. It was highlighted as a highly effective method that achieves significant compression while maintaining minimal accuracy loss.

Terminology

Summary

The paper addresses the fundamental question of how much of the graph structure is actually necessary for effective learning in Graph Neural Networks (GNNs). The authors' intuition is that real-world graphs are noisy, redundant, and often exhibit heavy-tailed degree distributions, meaning many edges may be structurally redundant for the downstream learning objective. They explore whether graph sparsification—a standard data management technique—can be applied as a lightweight pre-processing step to accelerate GNN training and inference workloads. Instead of scaling the system or modifying the learning algorithm, they consider compressing the graph's structure before learning, with the goal of reducing memory, I/O, and neighborhood sampling overhead, while preserving predictive accuracy.

The paper notes that the impact of graph sparsification on modern GNNs remains poorly understood, as prior work typically evaluates individual sparsification techniques in isolation, focuses on a single model, or restricts experiments to small datasets. To address this gap, the authors develop an extensible benchmarking framework that enables easy and systematic evaluation of the effects of graph sparsification on GNN training and inference pipelines.

Key findings from the abstract include:

  • Sparsification often preserves or even improves predictive performance. As an example, random sparsification raises the accuracy of the GAT model by 6.8% on the PubMed graph.

  • "Benefits increase with scale, substantially accelerating both training and inference. Our results show that the K-Neighbor sparsifier improves model serving performance on the Products graph by 11.7× with only a 0.7% accuracy drop."

  • The computational overhead of sparsification is quickly amortized, making it practical for very large graphs.

The paper makes three main contributions:

  1. Framework design: "We design and implement an extensible experimental framework that is compatible with DGL and allows users to transparently integrate graph sparsification as a pre-processing step in their GNN training and inference pipelines. The framework supports four graph sparsification techniques (Random, K-Neighbor, Rank Degree, Local Degree), four widely-used GNN architectures (GCN, GraphSage, GAT, SGFormer), and five real-world graphs, of different scales and domains (PubMed, CoauthorCS, Arxiv, Products, Papers100M)."

  2. Evaluation metrics: "We define a comprehensive suite of evaluation metrics that quantify how graph sparsification affects accuracy–efficiency tradeoffs across models and datasets. Our evaluation goals cover training dynamics, serving-time behavior, pre-processing overhead, and the sensitivity of compression levels and accuracy to various graph sparsification parameters."

  3. Experimental results: "We present and analyze the first set of results revealing how graph sparsification impacts GNN accuracy, training convergence, and end-to-end performance, providing practical guidance on when compression is a viable alternative or complement to systems-level scaling."

The paper reports several consistent patterns:

  1. "Graph reduction can often preserve, and sometimes even improve, predictive performance. Across all evaluated GNN architectures, there exists at least one instance of a model trained on a sparsified graph that exceeds the accuracy of the same model trained on the original graph."

  2. "The K-Neighbor sparsifier consistently achieves a particularly strong trade off between efficiency and accuracy, across datasets and models. When evaluated with the GraphSAGE model on Products, it achieves up to 6.8× speedup while retaining accuracy within 1% of a model trained on the original graph."

  3. "The benefits of reduction become more pronounced at scale, substantially accelerating both training and inference. At the same time, overly aggressive compression tends to harm performance, highlighting the importance of preserving informative local structure."

  4. The computational overhead of sparsification is quickly amortized, making it a practical pre-processing step even for very large graphs.

The framework consists of three main components: (1) graph loading, (2) graph sparsification, and (3) model training and evaluation.

Graph loading: Users can load their graphs into the framework using either our direct C++ interface or a Python interface. The framework handles the original dataset format provided by OGB, where graph structure is stored as two NumPy arrays representing source and destination nodes, respectively. It supports OGB raw datasets, DGL built-in datasets, and PyG datasets.

Graph sparsification: Once the graph data is loaded, it is represented in an edge-list format. The framework follows the convention of treating graphs as undirected by adding reverse edges and self-loops. All sparsification algorithms are implemented in C++ and parallelized using shared-memory OpenMP. The output is a graph in edge-list format, which can be directly converted to NumPy format to reconstruct DGL or PyG graph objects. Summarized graphs can also be stored to a file to enable skipping the graph loading and the sparsification phases for subsequent training runs.

Model training and evaluation: Model training is performed using either mini-batch neighbor sampling or full-graph training, depending on the model. The framework implements three representative GNN architectures—GCN, GAT, and GraphSAGE—each using standard DGL operators and trained without any architecture-specific optimizations, plus SGFormer, a graph transformer. The framework decouples training from testing by checkpointing model weights after each epoch and performing post-hoc evaluation. It also supports cross-graph inference: models trained on the original graph can be evaluated on summarized graphs, and vice versa.

For large-scale graphs, we provide a separate training pipeline based on DGL's GraphBolt backend where original or sparsified graphs are loaded from disk in a streaming fashion, and node features are accessed via memory-mapped storage.

The paper evaluates four sparsification techniques:

  1. Random Sparsifier: reduces the size of a graph by independently retaining each edge with a fixed probability p. The implementation converts the input graph to an edge list, then uniformly samples at random to achieve the desired sparsification ratio.

  2. K-Neighbor Sparsifier: constructs a reduced graph by selecting up to k incident edges for each vertex. If a vertex's degree is less than or equal to k, all incident edges are retained. Otherwise, k neighbors are sampled uniformly at random without replacement from N(i). For undirected graphs, if an edge is selected by either endpoint, we consider it as selected.

  3. Rank Degree Sparsifier: starts with selecting a random set of 'seed' vertices, then iteratively adds top rho neighboring vertices based on their degree rank until a target vertex size x is reached. The implementation uses training nodes as the initial seed nodes. The process is inherently sequential, so the authors execute the selection iteratively, hop by hop and parallelize the selection within each hop while maintaining the overall sequential structure.

  4. Local Degree Sparsifier: selects the edges to the top d(i) alpha neighbors, sorted by degree in descending order, where alpha is a parameter that controls the sparsification level. The goal is to keep those edges in the sparsified graph that lead to nodes with high degree.

The paper uses five real-world graphs:

  • PubMed: classic benchmark with sparse TF-IDF features and three classes (19.7K nodes, 44.3K edges)

  • CoauthorCS: feature-rich co-authorship network with 15 classes and higher average degree than PubMed (18.3K nodes, 81.9K edges)

  • Arxiv: a graph representing the citation network between all Computer Science arXiv papers indexed by MAG (169.3K nodes, 1.2M edges)

  • Products: a product co-purchasing graph with millions of nodes and tens of millions of edges (2.4M nodes, 61.9M edges)

  • Papers100M: a citation graph with over 100M nodes and 1.6B edges used to evaluate whether sparsification can make training and inference feasible or substantially faster at large scales (111.1M nodes, 1.6B edges)

The paper addresses five research questions:

  • [Q1] Accuracy and time to convergence: measured via maximum accuracy (highest test accuracy under a uniform stopping rule) and time to convergence (wall-clock time to reach maximum accuracy)

  • [Q2] Training efficiency: measured via time-to-target accuracy (training time required to reach the original graph's best accuracy on the sparsified graph)

  • [Q3] Serving-time trade-offs: examining deployment-time trade-offs when models are trained on the original graph but inference is performed on a summarized one

  • [Q4] Pre-processing overhead: measuring the wall-clock time from reading the original graph to emitting the summarized result

  • [Q5] Compression vs. performance: reporting the edge reduction percentage that a sparsification algorithm achieves relative to the resulting test accuracy and training time

  • "On the small-medium datasets (PubMed and CoauthorCS), training on sparsified graphs frequently improves accuracy over the original graph, suggesting that edge removal acts as structural regularization that reduces overfitting. For example, on PubMed-GAT, Random sparsification raises accuracy from 0.730 to 0.780 (+6.8%), and on CoauthorCS-GCN, Rank Degree reaches 0.9463 versus 0.9288 (+1.9)."

  • "On larger, sparser graphs (Arxiv, Products, Papers100M), training on the original graph achieves the best accuracy in the majority of cases. However, it is worth noting that there always exists at least one sparsification method that reaches test accuracy within 1% of the original model, with the only exception of GAT on Papers100M."

  • K-Neighbor consistently preserves accuracy across all datasets and models, staying within 1% of the original in most cases and even surpassing it on Papers100M-GCN (0.5986 vs. 0.5958).

  • Rank Degree, in contrast, causes severe accuracy drops of 10–28 percentage points on Arxiv, Products, and Papers100M.

  • Sparsification offers minimal speedup on small datasets but substantial gains on larger ones. For example, K-Neighbor accelerates Products-GAT convergence by 3.2× and Papers100M-GAT by 2.2×.

  • On CoauthorCS, K-Neighbor achieves 10.8× speedup for GCN and 8.4× for GraphSAGE.

  • On Arxiv, only K-Neighbor reaches the target, reducing training time by 1.8× on GCN, 8.4× on GraphSAGE, and exhibiting a striking 31.6× speedup on GAT (1145s → 36s).

  • On Products, both Random and K-Neighbor reach the target accuracy with substantial speedups: K-Neighbor achieves 11.1× for GCN and 19.5× for GAT.

  • On Papers100M, only Random reaches the target for all three models, with speedups of 5.4–7.0×.

  • Random and K-Neighbor preserve accuracy within 1-2% of the original for most dataset-model pairs (e.g., Products-GraphSAGE: Random 0.793 vs. original 0.794; K-Neighbor 0.779).

  • K-Neighbor also improves inference performance: on Products, it reduces GAT inference time from 413s to 35s (11.7×) with only a 0.7% accuracy drop, and GraphSAGE inference from 838s to 181s (4.6×) with a 1.9% drop.

  • In contrast, Rank Degree causes severe accuracy degradation of 15-28 percentage points on Arxiv and Products (e.g., Products-GCN: 0.574 vs. 0.792).

  • On PubMed and CoauthorCS, graph loading dominates runtime while sparsification is negligible.

  • On Products, sparsification completes in 12-20s versus 266-3414s training time.

  • Rank Degree on Papers100M is a notable outlier at 9970s (2.8 hours): 22× slower than K-Neighbor (452s) and 49× slower than Random (202s).

  • K-Neighbor pre-processing proves most cost-effective overall, amortizing in 13 out of 19 configurations. In contrast, Random performs worst, amortizing in only 8 out of 19 cases.

  • Random degrades gracefully (75% edge removal causes only 1-3% accuracy loss), making it a safe default for moderate compression.

  • For K-Neighbor, k=5 emerges as the sweet spot on Products, removing 91.6% of edges while losing less than 1% accuracy for GCN (0.790 vs. 0.792) and GraphSAGE (0.795 vs. 0.796).

  • Rank Degree's accuracy appears insensitive to its two hyperparameters. At the same time, the compression is always extreme due to the nature of the method.

  • Local Degree provides smooth tuning via alpha: alpha=0.9 retains 45% of edges with minimal accuracy loss, while alpha=0.25 removes 95% of edges with only 3-4% degradation.

The paper concludes: "We present a systematic study of graph sparsification as a pre-processing step for accelerating GNN training and inference pipelines. By integrating four sparsification methods with four GNN architectures across five real-world graphs spanning three orders of magnitude in size, we evaluate the end-to-end impact of graph sparsification on model accuracy, training efficiency, serving-time performance, and pre-processing overhead."

Key takeaways: "First, we show that graph sparsification can preserve, and in some cases even improve, model accuracy. Second, methods such as K-Neighbor sparsification consistently offer a favorable accuracy–efficiency trade-off, whereas more aggressive approaches like Rank Degree are unsuitable for most practical settings due to severe accuracy degradation. Finally, we demonstrate that the pre-processing overhead of sparsification is modest and amortizable, and can be easily offset by the gains in subsequent training and inference runs."

The authors note future directions: "exploring summarization methods that reduce the number of nodes is an important direction for future work. In addition, we plan to investigate the effects of other sparsification methods, like the metric backbone, and data reduction techniques like feature quantization."

Improvements for AI systems

Based on the paper, here are the specific improvements I can make to AI systems:

Improvement: Add a configurable graph sparsification layer before GNN training that supports four methods (Random, K-Neighbor, Rank Degree, Local Degree) with tunable parameters (retention ratio, K value, alpha, target size).

What the improved system can do:

  • Reduce graph size by up to 95% before training, cutting memory usage and I/O overhead

  • Automatically select the best sparsification method per dataset-model pair using the paper's finding that K-Neighbor (k=5) is most robust

  • Achieve up to 11.7× inference speedup on large graphs (e.g., Products) with less than 1% accuracy drop

Improvement: Implement a parameter sweeper that automatically tests sparsification configurations (e.g., K ∈ 3,5,10, alpha ∈ 0.25,0.5,0.9) and selects the optimal trade-off point.

Improvement: Add a training mode that uses sparsified graphs to reach a target accuracy faster, with automatic early stopping based on the original graph's best accuracy.

Improvement: Add a serving mode that uses a sparsified graph for inference while keeping the model trained on the original graph, with automatic accuracy monitoring.

Improvement: Implement a cost-benefit analyzer that tracks sparsification time (including data conversion) and predicts whether pre-processing will be amortized within a single training run.

Improvement: Add an optional mode that leverages sparsification as a regularizer, particularly for small datasets where the paper shows accuracy improvements.

Improvement: Integrate with GraphBolt/DGL's streaming backend to handle sparsified graphs that exceed single-GPU memory, using memory-mapped storage for features.

Improvement: Build a recommendation engine that suggests the best sparsification method based on the GNN architecture and dataset characteristics.

Abstract

As graphs scale to billions of nodes and edges, graph Machine Learning workloads are constrained by the cost of multi-hop traversals over exponentially growing neighborhoods. While various system-level and algorithmic optimizations have been proposed to accelerate Graph Neural Network (GNN) pipelines, data management and movement remain the primary bottlenecks at scale. In this paper, we explore whether graph sparsification, a well-established technique that reduces edges to create sparser neighborhoods, can serve as a lightweight pre-processing step to address these bottlenecks while preserving accuracy on node classification tasks. We develop an extensible experimental framework that enables systematic evaluation of how different sparsification methods affect the performance and accuracy of GNN models. We conduct the first comprehensive study of GNN training and inference on sparsified graphs, revealing several key findings. First, sparsification often preserves or even improves predictive performance. As an example, random sparsification raises the accuracy of the GAT model by 6.8% on the PubMed graph. Second, benefits increase with scale, substantially accelerating both training and inference. Our results show that the K-Neighbor sparsifier improves model serving performance on the Products graph by 11.7x with only a 0.7% accuracy drop. Importantly, we find that the computational overhead of sparsification is quickly amortized, making it practical for very large graphs.

Sources

Related papers