Rethinking Efficient Graph Coarsening via a Non-Selfishness Principle

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 \textit{selfishness} matching paradigm incurs substantial computational and memory overhead. To address this problem, we shift to a \textit{non-selfishness} principle that prioritizes the collective interference of neighborhood in coarsening, and propose an efficient method named \texttt{NOPE}, which achieves linear memory consumption and near-linear computational complexity in the number of nodes. Furthermore, we derive a faster variant \texttt{NOPE}*, which reduces $\mathcal{O}(\Delta\cdot d)$ interference evaluation to $\mathcal{O}(d)$ based on the local isotropy assumption, and consequently alleviates the computational bottleneck for high-degree nodes. Experimental results show that \texttt{NOPE}* achieves $1.8–10\times$ speedup over \texttt{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://anonymous.4open.science/r/NOPE-FA74.