# Rethinking Efficient Graph Coarsening via a Non-Selfishness Principle

arXiv: https://arxiv.org/abs/2605.13021 · HTML: https://mlsanity.com/paper/2605.13021/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 47 references that are in the map.
- First posted on arXiv 13 May 2026.

## Builds on (most cited first, 26 of 26)

- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [Exploring the Potential of Large Language Models (LLMs) in Learning on Graphs](https://mlsanity.com/paper/2307.03393/) (2023)
- [Large Language Models on Graphs: A Comprehensive Survey](https://mlsanity.com/paper/2312.02783/) (2023)
- [Graph Condensation for Graph Neural Networks](https://mlsanity.com/paper/2110.07580/) (2021)
- [Harnessing Explanations: LLM-to-LM Interpreter for Enhanced Text-Attributed Graph Representation Learning](https://mlsanity.com/paper/2305.19523/) (2023)
- [Can GNN be Good Adapter for LLMs?](https://mlsanity.com/paper/2402.12984/) (2024)
- [Statistical inference on random dot product graphs: a survey](https://mlsanity.com/paper/1709.05454/) (2017)
- [Fast Graph Condensation with Structure-based Neural Tangent Kernel](https://mlsanity.com/paper/2310.11046/) (2023)
- [Graph Condensation: A Survey](https://mlsanity.com/paper/2401.11720/) (2024)
- [When Do LLMs Help With Node Classification? A Comprehensive Analysis](https://mlsanity.com/paper/2502.00829/) (2025)
- [A Gromov--Wasserstein Geometric View of Spectrum-Preserving Graph Coarsening](https://mlsanity.com/paper/2306.08854/) (2023)
- [Graph Coarsening via Convolution Matching for Scalable Graph Neural Network Training](https://mlsanity.com/paper/2312.15520/) (2023)
- [Are Large Language Models In-Context Graph Learners?](https://mlsanity.com/paper/2502.13562/) (2025)
- [A Unified Framework for Optimization-Based Graph Coarsening](https://mlsanity.com/paper/2210.00437/) (2022)
- [Graph Coarsening with Message-Passing Guarantees](https://mlsanity.com/paper/2405.18127/) (2024)
- [TAGLAS: An atlas of text-attributed graph datasets in the era of large graph and language models](https://mlsanity.com/paper/2406.14683/) (2024)
- [Graph-Skeleton: ~1% Nodes are Sufficient to Represent Billion-Scale Graph](https://mlsanity.com/paper/2402.09565/) (2024)
- [OXYGENERATOR: Reconstructing Global Ocean Deoxygenation Over a Century with Deep Learning](https://mlsanity.com/paper/2405.07233/) (2024)
- [<SOG_k>: One LLM Token for Explicit Graph Structural Understanding](https://mlsanity.com/paper/2602.01771/) (2026)
- [AH-UGC: Adaptive and Heterogeneous-Universal Graph Coarsening](https://mlsanity.com/paper/2505.15842/) (2025)
- [Inductive Reasoning for Temporal Knowledge Graphs with Emerging Entities](https://mlsanity.com/paper/2604.10164/) (2026)

## Built on by (most cited first, 1 of 1)

- [Does Graph Compression Preserve Signal Propagation?](https://mlsanity.com/paper/2607.23338/) (2026)

## Abstract (arXiv)

Graph coarsening is a graph dimensionality reduction technique that aims to construct a smaller and more tractable graph while preserving the essential structural and semantic properties of the original graph. However, most existing methods rely on pair-wise similarity matching, where each node independently searches for its best partner based on global information. This selfishness matching paradigm incurs substantial computational and memory overhead. To address this problem, we shift to a non-selfishness principle that prioritizes the collective interference of neighborhood in coarsening, and propose an efficient method named NOPE, which achieves linear memory consumption and near-linear computational complexity in the number of nodes. Furthermore, we derive a faster variant NOPE*, which reduces O(δ dot d) interference evaluation to O(d) based on the local isotropy assumption, and consequently alleviates the computational bottleneck for high-degree nodes. Experimental results show that NOPE* achieves 1.8-10× speedup over NOPE and surpass almost all baselines with 1-3 orders of magnitude acceleration. Meanwhile, learning on coarsened graphs yields comparable performance to original graphs, and can even show superior performance over LLM-based graph reasoning owing to compact graph information. The code can be available at https://github.com/dazonglian/NOPE-main.