Skip to content

Scaffold: Support Graph Theory Based Sparsification for Graph Neural Networks

Sep 2026 · arXiv.org · Vol abs/2609.31466 · 0 citations · 68 references
Computer Science

TL;DR

To the authors' knowledge, Scaffold is the first scalable GNN sparsification framework to use a joint supporting-path dilation-congestion criterion, and across 19 homophilic and heterophilic benchmarks, Scaffold achieves the best aggregate rank among the evaluated sparsification and related methods.

Abstract

Graph neural networks (GNNs) rely on message passing over graph edges, making their computational and memory costs strongly dependent on graph density. Graph sparsification offers a natural way to reduce these costs, but removing edges indiscriminately can distort important communication structure and degrade predictive performance. We introduce Scaffold, a topology-based, unsupervised graph sparsification framework derived from support graph theory preconditioners. Scaffold explicitly controls two complementary structural quantities: dilation, which measures the length of rerouting paths induced by removed edges, and congestion, which measures how strongly these rerouted paths concentrate on the retained support. By jointly controlling dilation and congestion, Scaffold preserves short communication paths while avoiding structural bottlenecks. To our knowledge, Scaffold is the first scalable GNN sparsification framework to use a joint supporting-path dilation-congestion criterion. Across 19 homophilic and heterophilic benchmarks spanning small to large graphs, Scaffold achieves the best aggregate rank among the evaluated sparsification and related methods. Using only 10%-50% of the original edges per sparse support, Scaffold recovers or closely approaches full-graph GNN performance while using less than half the memory of full-graph training and reducing end-to-end training time, including sparsification overhead. We provide an open-source software package at https://github.com/siddhartha047/Scaffold.

View source

Similar papers

#machine learning Preprint Oct 2026

EDiS: Edge Disjoint Subgraph Sparsification Framework for Graph Neural Networks

This work provides a combinatorial analysis of the per-epoch sampler, the composition step that draws a training graph from the cached decomposition, and derives a selector-agnostic conditional bound on high-score cut survival in composed training graphs.

S. Navuluru, Siddhartha Shankar Das, Franck Dernoncourt et al. · 0 citations
Preprint Aug 2026

Subgraph Filtering for Fair Graph Neural Networks

Subgraph Filtering for Fair Graph Neural Networks is proposed, a lightweight and architecture-agnostic framework that mitigates structural bias at its source and achieves consistent fairness improvements while maintaining competitive predictive performance, leading to a better fairness--accuracy trade-off than recent f...

Hao-Hui Lu, Ji-Yuan Tian, Fangyu Zhou et al. · 0 citations
#machine learning Preprint Oct 2026

Path Laplacian Encodings for Directed Graphs

This work introduces PathLapPE, a novel spectral positional encoding (PE) derived from the path Laplacian on directed graphs that provides node- and edge-level features that encode directional higher-order structure and can be incorporated into standard graph learning architectures.

Lydia Mezrag, Semih Cantürk, Michael Perlmutter et al. · 0 citations
Sep 2026

Generalizing on Diverse Shifts: A Unified Topology-Aware Reweighting Algorithm for Graphs.

Topology-Aware Dynamic Reweighting (TAR+), a model-agnostic framework for node classification under strict graph distribution shifts and related robustness stressors, is proposed, supporting the broad applicability of topology-aware reweighting across heterogeneous graph learning conditions.

Jia-Xing Li, Jia-Shuo Liu, Wei-Huang Zheng et al. · 0 citations
#machine learning Preprint Oct 2026

Efficient Graph Generation via Direct Prediction and Flow Matching

Generative modeling of graph-structured data is crucial for tasks ranging from drug discovery to social network simulation. Among these models, denoising diffusion models have achieved great success in graph generation by learning to progressively reverse a process that adds noise to the original graph. However, the st...

Susie Lu · 0 citations
#graph neural networks Open access Sep 2026

Preserving the Motif-Relevant Structure in Graph Neural Networks: An Entropy-Aware Study of Aggregation and Depth

Graph neural networks have shown strong potential for learning structural representations of biological networks. However, repeated message passing may blur local structural signals that are relevant for motif- and graphlet-based analysis. This paper investigates multilabel graphlet classification in protein–protein in...

Lidija Kunst, Friedhelm Schwenker, H. Kestler · 0 citations

Related blog posts

MIT News · Artificial Intelligence Nov 17, 2026

Learning the language of machine learning

By studying the computational foundations of language learning, Associate Professor Jacob Andreas builds intelligent systems that can communicate effectively with humans.

Microsoft Research Blog Nov 16, 2026

TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient

AI coding agents are increasingly help developers fix bugs and build features largely on their own, but every interaction with their models consumes tokens. In each session, an agent sends instructions, tool descriptions, and session history to its model. Most efforts to reduce this cost focus on individual tasks. Yet developers return to the same […] The post TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient appeared first on Microsoft Research.

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.