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.
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
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
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
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.· IEEE Transactions on Pattern...· 0 citations
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...
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· Entropy· 0 citations
Related blog posts
MIT News · Artificial Intelligence· news.mit.eduNov 17, 2026
By studying the computational foundations of language learning, Associate Professor Jacob Andreas builds intelligent systems that can communicate effectively with humans.
Microsoft Research Blog· microsoft.comNov 16, 2026
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.
MIT News · Artificial Intelligence· news.mit.eduNov 13, 2026