Remedying Coarsening-Based GNN Training under Heterophily via Adaptive Complementary Enhancement
Summary
Proposes ACE, a plug-and-play method that adaptively enhances coarsening-based GNN training on heterophilic graphs by reconstructing node features and applying anisotropic regularization, achieving consistent gains on heterophilic benchmarks with minimal overhead.
arXiv:2607.21885v1 Announce Type: new
Abstract: Coarsening-based training for graph neural networks (GNNs), i.e.\ training on coarsened graphs rather than the original large ones, has become a promising direction for scaling GNNs to massive graphs. However, prior work has been evaluated almost exclusively on \textit{homophilic} graphs, leaving the more challenging \textit{heterophilic} settings underexplored. We show, both empirically and theoretically, that existing coarsening-based training methods suffer significant performance degradation on heterophilic graphs due to inevitable loss of graph information during coarsening. To address this, we propose {\bf A}daptive {\bf C}omplementary {\bf E}nhancement, a plug-and-play, model-agnostic strategy that reintegrates the information discarded in coarsening: ACE learns a projector for re-constructing original node features and applies \textit{anisotropic structural regularization} to embed local heterophily. We further adopt \textit{homoscedastic uncertainty weighting} to adaptively balance the combined training objective of primary coarsened-graph training loss and full-graph auxiliary loss with augmented node features re-constructed by the heterophily-aware projector. Extensive experiments show that ACE drives consistent gains on heterophilic benchmarks while preserving competitive results on homophilic graphs with minimal computational overhead. Code is available at the GitHub repository: https://github.com/vasile-paskardlgm/ACE.
View Cached Full Text
Cached at: 07/27/26, 07:42 AM
# Remedying Coarsening-Based GNN Training under Heterophily via Adaptive Complementary Enhancement Source: [https://arxiv.org/html/2607.21885](https://arxiv.org/html/2607.21885) Jian YangSchool of Information, Renmin University of China, Beijing, ChinaXukun WangAcademy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, ChinaZixiao WangMohamed bin Zayed University of Artificial Intelligence, Abu Dhabi, UAEShangsong LiangSchool of Computer Science, Sun Yat\-sen University, Guangzhou, China[Yifan Chen†](https://arxiv.org/html/2607.21885v1/mailto:[email protected])Department of Computer Science, Hong Kong Baptist University, Hong Kong SAR, China ###### Abstract Coarsening\-based training for graph neural networks \(GNNs\), i\.e\. training on coarsened graphs rather than the original large ones, has become a promising direction for scaling GNNs to massive graphs\. However, prior work has been evaluated almost exclusively onhomophilicgraphs, leaving the more challengingheterophilicsettings underexplored\. We show, both empirically and theoretically, that existing coarsening\-based training methods suffer significant performance degradation on heterophilic graphs due to inevitable loss of graph information during coarsening\. To address this, we proposeAdaptiveComplementaryEnhancement, a plug\-and\-play, model\-agnostic strategy that reintegrates the information discarded in coarsening: ACE learns a projector for re\-constructing original node features and appliesanisotropic structural regularizationto embed local heterophily\. We further adopthomoscedastic uncertainty weightingto adaptively balance the combined training objective of primary coarsened\-graph training loss and full\-graph auxiliary loss with augmented node features re\-constructed by the heterophily\-aware projector\. Extensive experiments show that ACE drives consistent gains on heterophilic benchmarks while preserving competitive results on homophilic graphs with minimal computational overhead\. Code is available at the GitHub repository:[https://github\.com/vasile\-paskardlgm/ACE](https://github.com/vasile-paskardlgm/ACE)\. 22footnotetext:Corresponding author## 1Introduction Graph neural networks \(GNNs\) have emerged as powerful tools for capturing structural information from graph signals, achieving prominent performance across a broad spectrum of structured and graph\-based applications\[Wu et al\.,[2022](https://arxiv.org/html/2607.21885#bib.bib49)\]\. However, as real\-world graphs scale to millions of nodes and billions of edges, the computational complexity of mainstream propagation algorithms results in formidable training costs\[Zhou et al\.,[2022](https://arxiv.org/html/2607.21885#bib.bib55)\]\. In response, various scalable training strategies have been proposed, includingmodel\-centricgraph sampling\[Serafini and Guan,[2021](https://arxiv.org/html/2607.21885#bib.bib46)\]anddata\-centricgraph reduction\[Hashemi et al\.,[2024](https://arxiv.org/html/2607.21885#bib.bib21)\]\. Among data\-centric methods,graph coarseninghas emerged as a widely adopted paradigm\[Huang et al\.,[2021](https://arxiv.org/html/2607.21885#bib.bib23), Kumar et al\.,[2023b](https://arxiv.org/html/2607.21885#bib.bib32), Kataria et al\.,[2024](https://arxiv.org/html/2607.21885#bib.bib27), Xia et al\.,[2025](https://arxiv.org/html/2607.21885#bib.bib51), Dickens et al\.,[2024](https://arxiv.org/html/2607.21885#bib.bib12)\]\. By training GNNs on a reduced graph to produce predictions for the original scale, these methods achieve significant efficiency\. Unlikegraph condensation\[Jin et al\.,[2022](https://arxiv.org/html/2607.21885#bib.bib24)\], coarsening ismodel\-agnostic, allowing a single coarsened graph to support a broad family of GNN architectures\[Huang et al\.,[2021](https://arxiv.org/html/2607.21885#bib.bib23), Kataria et al\.,[2024](https://arxiv.org/html/2607.21885#bib.bib27)\]\. Despite this empirical success, existing coarsening methods have been developed almost exclusively forhomophilicgraphs, leaving more challengingheterophilicgraphs \(distinct fromheterogeneousgraphs;Wang et al\.[2023](https://arxiv.org/html/2607.21885#bib.bib48)\) largely unexplored\[Gong et al\.,[2024](https://arxiv.org/html/2607.21885#bib.bib18)\]\. In homophilic graphs, neighboring nodes tend to share similar labels or features, whereas this assumption breaks down in heterophilic graphs; therein neighbors often possess different labels or representations\. Our preliminary analysis \(in Section[2\.2](https://arxiv.org/html/2607.21885#S2.SS2)\) reveals that coarsening\-based training suffers a much greater performance drop on heterophilic graphs relative to full\-graph training, while the degradation on homophilic graphs is notably smaller\. We turn to explain this disparity through the lens of mutual information, showing that graph heterophily significantly exacerbates themutual information gapbetween models trained via coarsening and those trained on the full graph\. These results suggest that heterophily poses a fundamental challenge to coarsening\-based training\. In response, this work proposesAdaptiveComplementaryEnhancement \(ACE\), a plug\-and\-play, model\-agnostic framework for enhancing coarsening\-based GNN training under heterophily\. The central principle of ACE is to reintegrate the graph information discarded during coarsening via a heterophily\-aware auxiliary loss\. In particular, ACE begins by learning a refinedprojectorfor re\-constructing original node features with averaged supernode feature; this learning process is further featuresanisotropic structural regularization\(c\.f\. Eq\. \([3\.2\.1](https://arxiv.org/html/2607.21885#S3.Ex2)\)\) for identifying heterophily\. This regularization stems from anisotropic graph diffusion and were primarily adapted to supervised GNN training settings\[Chamberlain et al\.,[2021](https://arxiv.org/html/2607.21885#bib.bib2), Elhag et al\.,[2022](https://arxiv.org/html/2607.21885#bib.bib13)\]; here, we formulate it as an unsupervised data augmentation mechanism to embed local heterophily into the reconstructed features as well as the projector\. The resulting projector lifts GNN predictions from the coarsened graph back to the full\-graph scale to define an auxiliary loss with respect to the full\-graph labels\. To further stabilize training, we adopthomoscedastic uncertainty\[Kendall et al\.,[2018](https://arxiv.org/html/2607.21885#bib.bib28)\]to adaptively weigh the auxiliary objective against the primary coarsening loss\. ACE’s modularity enables seamless integration into existing pipelines, where our empirical studies verify consistent performance gains\. To summarize, our main contributions are as follows: - •We recognize the heterophily challenge in coarsening\-based GNN training, and provide empirical evidence and theoretical explanations highlighting this underexplored limitation\. - •We proposeAdaptiveComplementaryEnhancement, a plug\-and\-play, model\-agnostic appraoch that augments coarsening\-based training with an heterophily\-aware auxiliary loss\. - •We conduct extensive experiments on large\-scale heterophilic and homophilic benchmarks, demonstrating that ACE consistently improves coarsening training by a notable margin\. ## 2Preliminaries and Challenges We first introduce key notations and background knowledge, then identify the heterophily challenge in existing coarsening training via empirical and theoretical analysis\. ### 2\.1Notations and Preliminaries ##### Notations\. Let𝒢=\(A,X\)\\mathcal\{G\}=\(A,X\)represent a graph, whereA∈\{0,1\}n×nA\\in\\\{0,1\\\}^\{n\\times n\}denotes the adjacency matrix andX∈ℝn×dX\\in\\mathbb\{R\}^\{n\\times d\}is the node features/signals\. The normalized graph Laplacian is defined asL=I−D−12AD−12L=I\-D^\{\-\\frac\{1\}\{2\}\}AD^\{\-\\frac\{1\}\{2\}\}\[Chung,[1997](https://arxiv.org/html/2607.21885#bib.bib7)\], whereIIis the identity matrix andDDis the degree matrix\. Additionally, we denoteY∈\{0,1\}n×cY\\in\\\{0,1\\\}^\{n\\times c\}as the one\-hot encoded label matrix, whereccis the number of node classes\. On graph coarsening, we follow prior literature\[Liu et al\.,[2018](https://arxiv.org/html/2607.21885#bib.bib35), Chen et al\.,[2022a](https://arxiv.org/html/2607.21885#bib.bib3)\], and let𝒞1,𝒞2,…,𝒞n′\\mathcal\{C\}\_\{1\},\\mathcal\{C\}\_\{2\},\.\.\.,\\mathcal\{C\}\_\{n^\{\\prime\}\}be a partition of the node set inton′<nn^\{\\prime\}<ndisjoint clusters, where each cluster corresponds to asupernodein the coarsened graph\. The partition matrixP∈\{0,1\}n′×nP\\in\\\{0,1\\\}^\{n^\{\\prime\}\\times n\}satisfiesPi,j=1P\_\{i,j\}=1if nodevj∈𝒞iv\_\{j\}\\in\\mathcal\{C\}\_\{i\}\. The coarsened graph𝒢′=\(A′,X′\)\\mathcal\{G\}^\{\\prime\}=\(A^\{\\prime\},X^\{\\prime\}\)is given by:A′=PAPTA^\{\\prime\}=PAP^\{T\},X′=C−1PXX^\{\\prime\}=C^\{\-1\}PX, andY′=C−1PYY^\{\\prime\}=C^\{\-1\}PY, whereC=diag\(\|𝒞1\|,\|𝒞2\|,…,\|𝒞n′\|\)C=\\text\{diag\}\(\|\\mathcal\{C\}\_\{1\}\|,\|\\mathcal\{C\}\_\{2\}\|,\.\.\.,\|\\mathcal\{C\}\_\{n^\{\\prime\}\}\|\)\. ##### Coarsening\-based GNN Training\. Following prior works \(e\.g\.,\[Huang et al\.,[2021](https://arxiv.org/html/2607.21885#bib.bib23), Xia et al\.,[2025](https://arxiv.org/html/2607.21885#bib.bib51)\]\), coarsening training seeks to improve efficiency by training on a coarsened graph𝒢′\\mathcal\{G\}^\{\\prime\}, while aiming to retain comparable downstream performance to models trained on the full graph𝒢\\mathcal\{G\}\. Formally, this paradigm can be defined as follows: ###### Definition 2\.1\(Coarsening\-based GNN Training\)\. Letf\(;Θ\)f\(;\\Theta\)denote a GNN with parameter setΘ\\Thetaand a softmax output layer\. Coarsening\-based GNN training minimizes the task loss on the coarsened graph:ℒ\(f\(A′,X′;Θ\),Y′\)\\mathcal\{L\}\(f\(A^\{\\prime\},X^\{\\prime\};\\Theta\),Y^\{\\prime\}\), which serves as a surrogate objective for the original graph loss:ℒ\(f\(A,X;Θ\),Y\)\\mathcal\{L\}\(f\(A,X;\\Theta\),Y\)\. In this work, we focus on thenode classificationtask, whereℒ\\mathcal\{L\}instantiated as thecross\-entropyloss, following prior studies\[Huang et al\.,[2021](https://arxiv.org/html/2607.21885#bib.bib23), Kumar et al\.,[2023b](https://arxiv.org/html/2607.21885#bib.bib32), Kataria et al\.,[2024](https://arxiv.org/html/2607.21885#bib.bib27), Xia et al\.,[2025](https://arxiv.org/html/2607.21885#bib.bib51)\]\. ##### Graph with Heterophily\. Heterophilic graphs—distinct fromheterogeneousgraphs\[Wang et al\.,[2023](https://arxiv.org/html/2607.21885#bib.bib48)\]—have become a central focus in modern node\-classification research\[Zheng et al\.,[2024](https://arxiv.org/html/2607.21885#bib.bib54), Gong et al\.,[2024](https://arxiv.org/html/2607.21885#bib.bib18)\]\. Unlike homophilic graphs, where neighboring nodes typically share similar labels or attributes, heterophilic graphs connect dissimilar nodes, violating key assumptions behind message\-passing GNNs and often exacerbatingover\-smoothingeffects\[Rusch et al\.,[2023](https://arxiv.org/html/2607.21885#bib.bib45), Yan et al\.,[2022](https://arxiv.org/html/2607.21885#bib.bib52)\]\. Such structures commonly arise in real\-world networks \(e\.g\., financial, communication, and certain molecular graphs\) and pose distinct challenges for GNN architectures\[Lim et al\.,[2021](https://arxiv.org/html/2607.21885#bib.bib34), Platonov et al\.,[2023](https://arxiv.org/html/2607.21885#bib.bib41)\]\. Despite their importance, the impact of heterophily has remained largely unexamined in coarsening\-based GNN training, leaving a notable gap that we explore in this work\. ##### Dirichlet Energy on Graphs\. LetEEbe the edge set of graph𝒢\\mathcal\{G\}\. The Dirichlet energy of node featuresXXis typically defined as ℰ\(𝒢\)=12∑\(i,j\)∈EAij‖XiDii−XjDjj‖22=trace\(X⊤LX\)\.\\mathcal\{E\}\(\\mathcal\{G\}\)=\\frac\{1\}\{2\}\\sum\_\{\(i,j\)\\in E\}A\_\{ij\}\\\|\\frac\{X\_\{i\}\}\{\\sqrt\{D\_\{ii\}\}\}\-\\frac\{X\_\{j\}\}\{\\sqrt\{D\_\{jj\}\}\}\\\|\_\{2\}^\{2\}=\\text\{trace\}\(X^\{\\top\}LX\)\\ \.\(1\)Dirichlet energy serves as a fundamental descriptor of smoothness over the graph and is central to understanding diffusion, propagation, and convolution behavior on graphs\[Giovanni et al\.,[2023](https://arxiv.org/html/2607.21885#bib.bib17), Han et al\.,[2023](https://arxiv.org/html/2607.21885#bib.bib20)\]\. This concept closely tied to the aforementioned key phenomena: heterophily, where label signals exhibit high Dirichlet energy\[Maskey et al\.,[2023](https://arxiv.org/html/2607.21885#bib.bib38)\], and over\-smoothing, where repeated graph propagation drives the energy of node representations toward zero\[Cai and Wang,[2020](https://arxiv.org/html/2607.21885#bib.bib1)\]\. ### 2\.2Heterophily Challenge ##### Empirical Observations\. We examine how existing coarsening\-based GNN training methods behave under heterophily\. Specifically, we evaluate three representative approaches—SCAL\[Huang et al\.,[2021](https://arxiv.org/html/2607.21885#bib.bib23)\], FGC\[Kumar et al\.,[2023b](https://arxiv.org/html/2607.21885#bib.bib32)\], and SGBGC\[Xia et al\.,[2025](https://arxiv.org/html/2607.21885#bib.bib51)\]—using a 10% coarsening ratio across large heterophilic graphs \(Genius, Gamers, Wiki\[Lim et al\.,[2021](https://arxiv.org/html/2607.21885#bib.bib34)\]\) and homophilic graphs \(Ogbn\-arxiv, Ogbn\-products\[Hu et al\.,[2020](https://arxiv.org/html/2607.21885#bib.bib22)\]\)\. The experiments are conducted with three backbone GNNs: GCN\[Kipf and Welling,[2017](https://arxiv.org/html/2607.21885#bib.bib30)\], LINKX\[Lim et al\.,[2021](https://arxiv.org/html/2607.21885#bib.bib34)\], and GloGNN\[Li et al\.,[2022](https://arxiv.org/html/2607.21885#bib.bib33)\], where the latter two are explicitly designed for heterophilic settings\. Full details follow Section[4\.1](https://arxiv.org/html/2607.21885#S4.SS1)\. Table 1:Impact of heterophily on coarsening\-based training\. “\-” denotes full\-graph training, andΔ↓\\Delta\\downarrowindicates the average performance drop of coarsening training relative to full\-graph training for each dataset\.BackboneGCNLINKXGloGNNΔ↓\\Delta\\downarrowMethod\-SCALFGCSGBGC\-SCALFGCSGBGC\-SCALFGCSGBGCGenius87\.4267\.4770\.1371\.2290\.7760\.6265\.4962\.6890\.6659\.4763\.8167\.3326\.26Gamers62\.1847\.3940\.1444\.6266\.0650\.1342\.4847\.6066\.1946\.2845\.9247\.1519\.07Pokec75\.4550\.4453\.8155\.4882\.0456\.4857\.6354\.1883\.0061\.5866\.9163\.7722\.35Arxiv71\.7463\.4265\.5264\.1269\.5457\.7159\.3861\.5572\.6857\.0961\.7361\.247\.79Products75\.6468\.3771\.2871\.9674\.5962\.4967\.5264\.9377\.4866\.5370\.4669\.116\.50 Results in Table[1](https://arxiv.org/html/2607.21885#S2.T1)reveals a striking trend:allcoarsening\-based methods suffer substantially larger performance degradation on heterophilic graphs compared to homophilic ones—often nearlyfour timeslarger—and this occurs consistently across all backbone models, including heterophily\-specialized architectures \(LINKX and GloGNN\)\. Notably, these heterophily\-oriented models exhibit even larger performance drops, underscoring that the difficulty stems not from the model itself but from a morefundamental limitation of coarsening\-based training under heterophilic settings\. More empirical results supporting this observation are presented in the main experiments in Section[4](https://arxiv.org/html/2607.21885#S4)and Appendix[D\.4](https://arxiv.org/html/2607.21885#A4.SS4)\. ##### Theoretical Explanation\. The empirical results on heterophilic graphs reveal a pronounced and consistent performance gap between models trained on the coarsened graph and those trained on the full graph, indicating that the degradation arises from the coarsening process itself\. Motivated by this observation, we study the heterophily challenge from an information\-theoretic perspective to understand how and why this gap arises\. Let𝒢∖𝒢′\\mathcal\{G\}\\setminus\\mathcal\{G\}^\{\\prime\}denote thediscarded graph informationduring coarsening, consisting of the intra\-supernode structural details \(illustrated in Figure[1](https://arxiv.org/html/2607.21885#S2.F1)\)\. Using this notion, we characterize the discrepancy between the full\-graph–trained model and the coarsened\-graph–trained model by quantifying the mutual information between𝒢∖𝒢′\\mathcal\{G\}\\setminus\\mathcal\{G\}^\{\\prime\}and the labelYY, leading to the following proposition: Figure 1:Illustration for graph coarsening:𝒢′\\mathcal\{G\}^\{\\prime\}encodes inter\-supernode relations;𝒢∖𝒢′\\mathcal\{G\}\\setminus\\mathcal\{G\}^\{\\prime\}holds intra\-supernode information discarded during coarsening\.###### Proposition 2\.2\. Let the GNN trained on the original graph bef\(;Θ∗∗\)f\(;\\Theta^\{\\ast\\ast\}\)and the one trained on the coarsened graph bef\(;Θ∗\)f\(;\\Theta^\{\\ast\}\), where Θ∗\\displaystyle\\Theta^\{\\ast\}≜argminΘℒ\(f\(A,X;Θ\),Y\),\\displaystyle\\triangleq\\arg\\min\\limits\_\{\\Theta\}\\mathcal\{L\}\(f\(A,X;\\Theta\),Y\)\\ ,\(2\)Θ∗∗\\displaystyle\\Theta^\{\\ast\\ast\}≜argminΘℒ\(f\(A′,X′;Θ\),Y′\)\.\\displaystyle\\triangleq\\arg\\min\\limits\_\{\\Theta\}\\mathcal\{L\}\(f\(A^\{\\prime\},X^\{\\prime\};\\Theta\),Y^\{\\prime\}\)\\ \.\(3\)When both models are evaluated on the original graph, the mutual information between their outputs satisfies I\(f\(A,X;Θ∗\);f\(A,X;Θ∗∗\)\)≤I\(f\(A,X;Θ∗\);Y\)−Ω,\\displaystyle I\(f\(A,X;\\Theta^\{\\ast\}\);f\(A,X;\\Theta^\{\\ast\\ast\}\)\)\\leq I\(f\(A,X;\\Theta^\{\\ast\}\);Y\)\-\\Omega\\ ,\(4\)whereΩ=I\(g\(𝒢∖𝒢′\);Y\|f\(A,X;Θ∗∗\)\)\\Omega=I\(g\(\\mathcal\{G\}\\setminus\\mathcal\{G\}^\{\\prime\}\);Y\|f\(A,X;\\Theta^\{\\ast\\ast\}\)\), andg:𝒢∖𝒢′↦𝒴g:\\mathcal\{G\}\\setminus\\mathcal\{G\}^\{\\prime\}\\mapsto\\mathcal\{Y\}is arbitrary neural network that maps𝒢∖𝒢′\\mathcal\{G\}\\setminus\\mathcal\{G\}^\{\\prime\}to the node label space𝒴\\mathcal\{Y\}and maximizes the conditional mutual informationI\(g\(𝒢∖𝒢′\);Y\|f\(A,X;Θ∗∗\)\)I\(g\(\\mathcal\{G\}\\setminus\\mathcal\{G\}^\{\\prime\}\);Y\|f\(A,X;\\Theta^\{\\ast\\ast\}\)\)\. Proof is provided in Appendix[A](https://arxiv.org/html/2607.21885#A1)\. This proposition provides anexplanatory clarificationby linking the model performance gap to the information loss induced by graph coarsening\. In the bound of Eq\. \([4](https://arxiv.org/html/2607.21885#S2.E4)\), the gap between the two models is expressed by the mutual informationI\(f\(A,X;Θ∗\);f\(A,X;Θ∗∗\)\)I\(f\(A,X;\\Theta^\{\\ast\}\);f\(A,X;\\Theta^\{\\ast\\ast\}\)\), which measures how similar the outputs of the full\-graph\-trained model and the coarsened\-graph\-trained model are\. Since the full\-graph modelf\(A,X;Θ∗\)f\(A,X;\\Theta^\{\\ast\}\)is unaffected by coarsening, the termI\(f\(A,X;Θ∗\);Y\)I\(f\(A,X;\\Theta^\{\\ast\}\);Y\)remains fixed\. Therefore, the magnitude of the model gap is determined entirely by the quantityΩ=I\(g\(𝒢∖𝒢′\);Y\|f\(A,X;Θ∗∗\)\)\\Omega=I\(g\(\\mathcal\{G\}\\setminus\\mathcal\{G\}^\{\\prime\}\);Y\|f\(A,X;\\Theta^\{\\ast\\ast\}\)\), which refers to the graph information lost during coarsening\. A largerΩ\\OmegaforcesI\(f\(A,X;Θ∗\);f\(A,X;Θ∗∗\)\)I\(f\(A,X;\\Theta^\{\\ast\}\);f\(A,X;\\Theta^\{\\ast\\ast\}\)\)to be smaller, producing a larger discrepancy between the full\-graph and coarsened\-graph models\. In heterophilic graphs, the discarded region𝒢∖𝒢′\\mathcal\{G\}\\setminus\\mathcal\{G\}^\{\\prime\}contains diverse labels and informative local structure; thus makingΩ\\Omegalarge\. Consequently, the mutual information between the two models becomes small, yielding the substantial performance drop observed empirically\. In contrast, homophilic graphs discard much less label\-relevant content, resulting in a much smaller gap\. ## 3Proposed Method: Adaptive Complementary Enhancement We now present our proposed method, Adaptive Complementary Enhancement \(ACE\)\. We begin with a motivating toy experiment and then introduce the framework in detail\. ### 3\.1Motivating Toy Experiment: A Simple Auxiliary Loss Matters As demonstrated in Section[2\.2](https://arxiv.org/html/2607.21885#S2.SS2), the heterophily challenge primarily arises from the loss of graph information during coarsening\. A natural solution is therefore toreintegrate the discarded information during training\. With this insight, we conduct a simple toy experiment: we augment the training via coarsening pipeline with an auxiliary loss that addresses the coarsening matrixP⊤CP^\{\\top\}Cand the original labelYY\. The resulting unified loss function is stated below, whereλ\\lambdadenotes the trade\-off hyperparameter\. ℒ~=\\displaystyle\\tilde\{\\mathcal\{L\}\}=ℒ\(f\(A′,X′;Θ\),Y′\)⏟Primary Coarsened\-Graph Training Loss\\displaystyle\\underbrace\{\\mathcal\{L\}\\left\(f\(A^\{\\prime\},X^\{\\prime\};\\Theta\),Y^\{\\prime\}\\right\)\}\_\{\\text\{Primary Coarsened\-Graph Training Loss\}\}\+λ⋅ℒ\(P⊤C⋅f\(A′,X′;Θ\),Y\)⏟Auxiliary Loss\.\\displaystyle\\quad\\quad\\quad\+\\quad\\lambda\\cdot\\underbrace\{\\mathcal\{L\}\\left\(P^\{\\top\}C\\cdot f\(A^\{\\prime\},X^\{\\prime\};\\Theta\),Y\\right\)\}\_\{\\text\{Auxiliary Loss\}\}\\ \.\(5\) Table 2:Toy experiment results\. Performance gains over the vanilla coarsening\-based training are highlighted inbold\.ModelMethodGeniusGamersPokecGCNSCAL67\.4747\.3950\.44w/ℒ~\\tilde\{\\mathcal\{L\}\}71\.32 \(\+3\.85\)52\.86 \(\+5\.47\)55\.29 \(\+4\.85\)FGC70\.1340\.1453\.81w/ℒ~\\tilde\{\\mathcal\{L\}\}75\.67 \(\+5\.54\)49\.26 \(\+9\.12\)57\.22 \(\+3\.41\)SGBGC71\.2244\.6255\.48w/ℒ~\\tilde\{\\mathcal\{L\}\}73\.81 \(\+2\.59\)53\.09 \(\+8\.47\)62\.42 \(\+6\.94\)GloGNNSCAL59\.4746\.2861\.58w/ℒ~\\tilde\{\\mathcal\{L\}\}67\.41 \(\+7\.94\)53\.11 \(\+6\.83\)67\.74 \(\+6\.16\)FGC63\.8145\.9266\.91w/ℒ~\\tilde\{\\mathcal\{L\}\}72\.33 \(\+8\.52\)51\.26 \(\+5\.34\)71\.44 \(\+4\.53\)SGBGC67\.3347\.1563\.77w/ℒ~\\tilde\{\\mathcal\{L\}\}73\.26 \(\+5\.93\)54\.31 \(\+7\.17\)69\.36 \(\+5\.59\) We follow the same experimental setup as in Section[2\.2](https://arxiv.org/html/2607.21885#S2.SS2)and compare the augmented loss \([3\.1](https://arxiv.org/html/2607.21885#S3.Ex1)\) against standard coarsening\-based training pipelines\. Remarkably, as shown in Table[2](https://arxiv.org/html/2607.21885#S3.T2), the introduction of the simple auxiliary loss leads to substantial and consistent improvements across all coarsening\-based methods and across diverse GNN backbones on heterophilic graphs\. A more comprehensive investigation in Appendix[C](https://arxiv.org/html/2607.21885#A3)reveals that the auxiliary loss benefits homophilic graphs as well\. In summary, these positive results highlight the strong potential of the auxiliary loss that compensates for information discarded during coarsening\. ### 3\.2The ACE Framework Motivated by the observations from the toy experiments, we develop a heterophily\-aware enhancement to coarsening\-based GNN training by incorporating an auxiliary loss\. This leads to our proposed framework, ACE, which consists of two core modules: \(i\)Refined Projector Constructionand \(ii\)Training With Unified Coarsening Loss\. #### 3\.2\.1Step i: Refined Projector Construction ##### Parameterized Projector\. Although the simple auxiliary loss enhance training efficacy, its construction relies on the coarsening projectorPP, which is entirely dictated by the chosen graph coarsening algorithm: either classical\[Purohit et al\.,[2014](https://arxiv.org/html/2607.21885#bib.bib42), Loukas and Vandergheynst,[2018](https://arxiv.org/html/2607.21885#bib.bib36), Jin et al\.,[2020](https://arxiv.org/html/2607.21885#bib.bib25), Fahrbach et al\.,[2020](https://arxiv.org/html/2607.21885#bib.bib15), Chen et al\.,[2023](https://arxiv.org/html/2607.21885#bib.bib5)\], or learnable\[Kumar et al\.,[2023a](https://arxiv.org/html/2607.21885#bib.bib31),[b](https://arxiv.org/html/2607.21885#bib.bib32), Joly and Keriven,[2024](https://arxiv.org/html/2607.21885#bib.bib26), Xia et al\.,[2025](https://arxiv.org/html/2607.21885#bib.bib51)\]\. None of existing designs specifically incorporate heterophily\-related cues into the construction of the so\-called projector\. We therefore seek to empower the projector with heterophily\-awareness\. To this end, we first construct thestructural affinitymatrixSSand thefeature affinitymatrixFF, both inℝn×n′\\mathbb\{R\}^\{n\\times n^\{\\prime\}\}: S=AC−1P,\\displaystyle S=AC^\{\-1\}P\\ ,\(6\)Fij=exp\(−‖Xi−μj‖2\);μj=1\|𝒞j\|∑i∈𝒞jXi\.\\displaystyle F\_\{ij\}=\\exp\(\-\\\|X\_\{i\}\-\\mu\_\{j\}\\\|^\{2\}\)\\ ;\\ \\mu\_\{j\}=\\frac\{1\}\{\|\\mathcal\{C\}\_\{j\}\|\}\\sum\_\{i\\in\\mathcal\{C\}\_\{j\}\}X\_\{i\}\\ \.\(7\)Following the intuition ofAlgebraic Multigrid\(AMG;[Ruge and Stüben](https://arxiv.org/html/2607.21885#bib.bib44)\), we note the termSijS\_\{ij\}measures how strongly nodeiiconnects to supernodejj, and the termFijF\_\{ij\}is aKernel Regressionsimilarity\[Nadaraya,[1964](https://arxiv.org/html/2607.21885#bib.bib39)\]between nodeiiand the centroidμj\\mu\_\{j\}\. Together, they encode structural and feature connections while preserving coarsening structure\. Using these two matrices, we devise a learnable, heterophily\-aware projector: Pij\(ϕ\)=exp\(αij\)∑k∈𝒩\(i\)exp\(αik\),\\displaystyle P\_\{ij\}\(\\phi\)=\\frac\{\\exp\(\\alpha\_\{ij\}\)\}\{\\sum\_\{k\\in\\mathcal\{N\}\(i\)\}\\exp\(\\alpha\_\{ik\}\)\}\\ ,\(8\)αij:=fϕ\(\[Sij,Fij\]\),\\displaystyle\\alpha\_\{ij\}:=f\_\{\\phi\}\(\\left\[S\_\{ij\},F\_\{ij\}\\right\]\)\\ ,\(9\)wherefϕf\_\{\\phi\}is an MLP parametrized withϕ\\phi\. Analogous to graph attention mechanism\[Veličković et al\.,[2018](https://arxiv.org/html/2607.21885#bib.bib47)\],P\(ϕ\)P\(\\phi\)learns how each fine node should associate with each supernode, balancing structural and feature signals throughϕ\\phi\. ##### Heterophily\-Aware Optimization\. To ensure thatP\(ϕ\)P\(\\phi\)correctly encodes heterophily, we study principled learning of the projectorPP\. Conventional attributed graph coarsening specifies the projector through optimizing a combination of Dirichlet energyℰ\(𝒢\)\\mathcal\{E\}\(\\mathcal\{G\}\)and feature reconstruction‖X−PP⊤X‖2\\\|X\-PP^\{\\top\}X\\\|^\{2\}\[Kumar et al\.,[2023b](https://arxiv.org/html/2607.21885#bib.bib32), Kataria et al\.,[2024](https://arxiv.org/html/2607.21885#bib.bib27)\], thereby promoting smooth GNN predictions—an inductive bias suited for homophilic graphs\. However, such objectives are inapplicable under heterophily, where neighboring nodes often carry contrasting information\. To overcome this issue, we draw inspiration from\[Fu et al\.,[2023](https://arxiv.org/html/2607.21885#bib.bib16)\], which constructs a heterophily\-aware Dirichlet energy viaanisotropic diffusion\[Perona and Malik,[1990](https://arxiv.org/html/2607.21885#bib.bib40)\], and propose theAnisotropic Structural Regularizationterm, defined as follows: 𝒥ASR\(ϕ\)=∑i,j∈Eωij⋅‖\(P\(ϕ\)𝝁\)i−\(P\(ϕ\)𝝁\)j‖2⏟Anisotropic Smoothness\\displaystyle\\mathcal\{J\}\_\{\\text\{ASR\}\}\(\\phi\)=\\underbrace\{\\sum\_\{i,j\\in E\}\\omega\_\{ij\}\\cdot\\\|\(P\(\\phi\)\\bm\{\\mu\}\)\_\{i\}\-\(P\(\\phi\)\\bm\{\\mu\}\)\_\{j\}\\\|^\{2\}\}\_\{\\text\{Anisotropic Smoothness\}\}\+β⋅‖X−P\(ϕ\)𝝁‖F2⏟Reconstruction Cost\\displaystyle\\quad\\quad\\quad\\quad\\quad\+\\,\\beta\\cdot\\underbrace\{\\\|X\-P\(\\phi\)\\bm\{\\mu\}\\\|\_\{F\}^\{2\}\}\_\{\\text\{Reconstruction Cost\}\}\(10\)whereωij:=exp\(−‖Xi−Xj‖2\)\\omega\_\{ij\}:=\\exp\(\-\\\|X\_\{i\}\-X\_\{j\}\\\|^\{2\}\),𝝁\\bm\{\\mu\}represents the stacked centroids\{μ1,μ2,…,μn′\}\\\{\\mu\_\{1\},\\mu\_\{2\},\.\.\.,\\mu\_\{n^\{\\prime\}\}\\\}\(see Eq\. \([7](https://arxiv.org/html/2607.21885#S3.E7)\)\), andβ\\betais the tradeoff coefficient\. The core idea behind this design is the superior ability of graph anisotropic diffusion to model heterophilic relationships in graphs, which regular isotropic diffusion adopted in most GNNs cannot capture\[Eliasof et al\.,[2021](https://arxiv.org/html/2607.21885#bib.bib14), Chen et al\.,[2022b](https://arxiv.org/html/2607.21885#bib.bib4), Dan et al\.,[2023](https://arxiv.org/html/2607.21885#bib.bib9), Han et al\.,[2023](https://arxiv.org/html/2607.21885#bib.bib20)\]\. Notably, prior methods apply anisotropic diffusion in supervised GNN training, whereas we use it in anunsupervisedmanner, relying solely on the graph data\. Despite lack of supervision, minimizing the proposed regularization term𝒥ASR\(ϕ\)\\mathcal\{J\}\_\{\\text\{ASR\}\}\(\\phi\)ensures that the projectorP\(ϕ∗\)P\(\\phi^\{\\ast\}\)isheterophily\-aware, as shown in the following proposition: ###### Proposition 3\.1\. Letϕ∗\\phi^\{\\ast\}denote the minimizer of𝒥ASR\(ϕ\)\\mathcal\{J\}\_\{\\text\{ASR\}\}\(\\phi\)\. The resulting projectorP\(ϕ∗\)P\(\\phi^\{\\ast\}\)acts as a conditional spectral filter that interpolates between two distinct regimes below based on local homophily: - •Heterophilic Regime:In regions where‖Xi−Xj‖→∞\\\|X\_\{i\}\-X\_\{j\}\\\|\\to\\infty,P\(ϕ∗\)P\(\\phi^\{\\ast\}\)approaches the solution of identity reconstruction, prioritizing high\-frequency signal fidelity over structural smoothness\. - •Homophilic Regime:In regions where‖Xi−Xj‖→0\\\|X\_\{i\}\-X\_\{j\}\\\|\\to 0,P\(ϕ∗\)P\(\\phi^\{\\ast\}\)approaches the solution of isotropic laplacian smoothing, enforcing local smoothness\. The proof is provided in Appendix[B](https://arxiv.org/html/2607.21885#A2)\. This proposition provides alocal optimality characterizationof the learned projector, demonstrating that ACE naturally adapts to both homophilic and heterophilic graph structures: In heterophilic regions, where‖Xi−Xj‖→∞\\\|X\_\{i\}\-X\_\{j\}\\\|\\to\\infty, the weightsωij\\omega\_\{ij\}vanish, suppressing the smoothness term and allowing the projector to prioritize high\-frequency, heterophily\-specific information; In homophilic regions, where‖Xi−Xj‖→0\\\|X\_\{i\}\-X\_\{j\}\\\|\\to 0, the smoothness constraint remains active, encouraging projector to preserve locally consistent, low\-frequency structure\. By minimizing Eq\. \([3\.2\.1](https://arxiv.org/html/2607.21885#S3.Ex2)\) with standard optimizers such as Adam\[Kingma and Ba,[2014](https://arxiv.org/html/2607.21885#bib.bib29)\], we can easily learn the projectorP\(ϕ∗\)P\(\\phi^\{\\ast\}\)adaptive to heterophilic graphs\. #### 3\.2\.2Step ii: Training With Joint Coarsening Loss The optimized projectorP\(ϕ∗\)P\(\\phi^\{\\ast\}\)can then be used to construct the auxiliary loss term in Eq\. \([3\.1](https://arxiv.org/html/2607.21885#S3.Ex1)\)\. However, the combined loss in Eq\. \([3\.1](https://arxiv.org/html/2607.21885#S3.Ex1)\) is inherently inflexible: it relies on a manually chosen tradeoff hyperparameter, which does not adapt to the dynamics of training and may vary across datasets or backbones\. To overcome this inconvenience and better leverage the supervision signals available in coarsening\-based GNN training, we further enhance the primitive combined loss \([3\.1](https://arxiv.org/html/2607.21885#S3.Ex1)\) by employingHomoscedastic Uncertainty weighting\[Kendall et al\.,[2018](https://arxiv.org/html/2607.21885#bib.bib28)\]\. This technique interprets the primary and auxiliary objectives as amulti\-task learningproblem\[Zhang and Yang,[2022](https://arxiv.org/html/2607.21885#bib.bib53)\], allowing their relative contributions to be balanced automatically via learnable task uncertainties\. The resulting ACE objective is: ℒACE=\\displaystyle\\mathcal\{L\}\_\{\\text\{ACE\}\}=12σ12ℒ\(P\(ϕ∗\)⊤C⋅f\(A′,X′;Θ\),Y\)⏟Auxiliary Loss\\displaystyle\\frac\{1\}\{2\\sigma\_\{1\}^\{2\}\}\\underbrace\{\\mathcal\{L\}\\left\(P\(\\phi^\{\\ast\}\)^\{\\top\}C\\cdot f\(A^\{\\prime\},X^\{\\prime\};\\Theta\),Y\\right\)\}\_\{\\text\{Auxiliary Loss\}\}\+12σ22ℒ\(f\(A′,X′;Θ\),Y′\)⏟Primary Loss\+log\(σ1σ2\),\\displaystyle\+\\,\\frac\{1\}\{2\\sigma\_\{2\}^\{2\}\}\\underbrace\{\\mathcal\{L\}\\left\(f\(A^\{\\prime\},X^\{\\prime\};\\Theta\),Y^\{\\prime\}\\right\)\}\_\{\\text\{Primary Loss\}\}\+\\,\\log\(\\sigma\_\{1\}\\sigma\_\{2\}\)\\ ,\(11\)whereσ1\\sigma\_\{1\}andσ2\\sigma\_\{2\}are learnable uncertainty parameters that dynamically adjust weights of the two losses during training\. #### 3\.2\.3Complexity Analysis We analyze the computational overhead introduced by ACE relative to vanilla training via coarsening, focusing on the cost of constructing the refined projector and the additional terms incurred by the ACE optimization framework\. We follow the notations in Section[2\.1](https://arxiv.org/html/2607.21885#S2.SS1)\. ##### Complexity of Refined Projector Construction\. Constructing the refined projectorP\(ϕ∗\)P\(\\phi^\{\\ast\}\)consists of a light pre\-computation stage and an iterative optimization overTTepochs\. The pre\-computation refers to calculatingωij\\omega\_\{ij\}over all fine\-level edges in𝒪\(\|E\|d\)\\mathcal\{O\}\(\|E\|d\)time, and forming the structure and feature affinities restricted by the coarsening assignment\{𝒞1,𝒞2,…,𝒞n′\}\\\{\\mathcal\{C\}\_\{1\},\\mathcal\{C\}\_\{2\},\.\.\.,\\mathcal\{C\}\_\{n^\{\\prime\}\}\\\}with𝒪\(nd\)\\mathcal\{O\}\(nd\)cost\. An optimization step then includes a forward pass of the parametric MLP mapfϕf\_\{\\phi\}over the sparse candidate pairs with𝒪\(n\)\\mathcal\{O\}\(n\)cost; the sparse lifting operation \(P\(ϕ\)𝝁P\(\\phi\)\\bm\{\\mu\}are then performed with𝒪\(nd\)\\mathcal\{O\}\(nd\)cost; ultimately, obtaining the reconstruction and anisotropic smoothness terms costs𝒪\(nd\)\\mathcal\{O\}\(nd\)and𝒪\(\|E\|d\)\\mathcal\{O\}\(\|E\|d\)time, respectively\. Aggregating all the components, the total complexity of refined projector construction is𝓞\(𝑻\(𝒏𝒅\+\|𝑬\|𝒅\)\)\\bm\{\\mathcal\{O\}\(T\(nd\+\|E\|d\)\)\}, which is linear in the graph size and remains lightweight compared with a standard GNN layer\. ##### Overhead in Training with Joint Coarsening Loss\. Training with the ACE loss is compatible with the standard coarsened\-graph pipeline on𝒢′\\mathcal\{G\}^\{\\prime\}, while adding a step to compute the auxiliary loss by lifting the coarsened logits back to the fine graph\. This lifting step incurs an additional cost of approximately𝓞\(𝒏𝒄\)\\bm\{\\mathcal\{O\}\(nc\)\}time\. Since the feature dimensionddis typically much larger than the number of classescc, this overhead is negligible relative to the dominant cost of vanilla coarsening\-based training, which is on the order of𝒪\(nd2\+\|E′\|d\)\\mathcal\{O\}\(nd^\{2\}\+\|E^\{\\prime\}\|d\)\(letE′E^\{\\prime\}be the edge set of𝒢′\\mathcal\{G\}^\{\\prime\}\)\. ##### Remark\. In summary, ACE improves performance by re\-leveraging fine\-grained supervision while maintaining the efficiency advantage of coarsening\-based training\. The inference complexity remains identical to the baseline, as the auxiliary branch is discarded after training\. This claim is verified in the following section, where ACE is shown to improve performance with minimal computational overhead\. ## 4Experiments We conduct extensive experiments to evaluate the effectiveness of ACE across diverse coarsening\-based GNN training pipelines\. Our evaluation covers both large\-scale heterophilic and homophilic benchmarks and multiple GNN backbones\. We organize the study around the following research questions: - •RQ1:How much does ACE improve performance over vanilla coarsening training pipelines? - •RQ2:How does the refined projectorP\(ϕ∗\)P\(\\phi^\{\\ast\}\)influence training behavior? - •RQ3:How does ACE influence the scalability and efficiency of coarsening\-based training? - •RQ4:How does ACE narrow the performance gap between conventional methods and state\-of\-the\-art ones? ### 4\.1Experimental Setup We evaluate four state\-of\-the\-art coarsening\-based GNN training pipelines: SCAL\[Huang et al\.,[2021](https://arxiv.org/html/2607.21885#bib.bib23)\], FGC\[Kumar et al\.,[2023b](https://arxiv.org/html/2607.21885#bib.bib32)\], UGC\[Kataria et al\.,[2024](https://arxiv.org/html/2607.21885#bib.bib27)\], and SGBGC\[Xia et al\.,[2025](https://arxiv.org/html/2607.21885#bib.bib51)\]\. For our ACE, we parameterizefϕf\_\{\\phi\}as a two\-layer MLP with 500 hidden dimensions and tune the trade\-off coefficientβ\\betafrom \{0\.1,1,10\} during projector optimization\. We use five large\-scale heterophilic datasets from\[Lim et al\.,[2021](https://arxiv.org/html/2607.21885#bib.bib34)\]: Genius, Gamers, Pokec, Snap, and arXiv\-year, and two large homophilic datasets from the OGB\[Hu et al\.,[2020](https://arxiv.org/html/2607.21885#bib.bib22)\]: Ogbn\-arXiv and Ogbn\-products\. Full dataset statistics are provided in Appendix[D\.1](https://arxiv.org/html/2607.21885#A4.SS1)\. We consider six GNN backbones: GCN\[Kipf and Welling,[2017](https://arxiv.org/html/2607.21885#bib.bib30)\], LINKX\[Lim et al\.,[2021](https://arxiv.org/html/2607.21885#bib.bib34)\], GLOGNN\[Li et al\.,[2022](https://arxiv.org/html/2607.21885#bib.bib33)\], GPRGNN\[Chien et al\.,[2021](https://arxiv.org/html/2607.21885#bib.bib6)\], SGFormer\[Wu et al\.,[2023](https://arxiv.org/html/2607.21885#bib.bib50)\], and Polynormer\[Deng et al\.,[2024](https://arxiv.org/html/2607.21885#bib.bib11)\], covering models specialized for heterophily, homophily, or both\.Due to space constraints, we report results for three backbones \(GCN, LINKX, and GLOGNN\) in the main text, anddefer the remaining results to Appendix[D\.4](https://arxiv.org/html/2607.21885#A4.SS4)\. We set a 10% coarsening ratio for all pipelines and finetune based on the recommended configurations from the original papers and benchmark repositories\. All models are trained for 500 epochs using the Adam optimizer\[Kingma and Ba,[2014](https://arxiv.org/html/2607.21885#bib.bib29)\], with early stopping triggered after 50 epochs of no validation improvement\. Training follows a consistent configuration across all methods: learning rate0\.010\.01, weight decay5e−45e\-4, and dropout0\.50\.5\. All reported numbers are averaged over 10 independent runs\. Additional training details and complementary experimental results are provided in Appendix[D](https://arxiv.org/html/2607.21885#A4)\. Table 3:Performance of integrating ACE into GCN, LINKX, and GloGNN\. Improvements on heterophilic datasets are highlighted inbold\. Standard deviations are reported in Table[7](https://arxiv.org/html/2607.21885#A4.T7); results for the remaining pipelines are provided in Table[8](https://arxiv.org/html/2607.21885#A4.T8)\.BackboneMethodHeterophilic GraphsHomophilic GraphsGeniusGamersPokecSnaparXiv\-yearogbn\-arXivogbn\-productsGCN\-87\.4262\.1875\.4545\.6546\.0271\.7475\.64SCAL67\.4747\.3950\.4422\.6627\.5963\.4268\.37\+ ACE77\.63 \(\+10\.16\)55\.63 \(\+8\.24\)58\.12 \(\+7\.68\)33\.47 \(\+10\.81\)34\.53 \(\+6\.94\)66\.03 \(\+2\.61\)70\.38 \(\+2\.01\)FGC70\.1340\.1453\.8123\.0625\.4965\.5271\.28\+ ACE77\.32 \(\+7\.19\)52\.52 \(\+12\.38\)61\.67 \(\+7\.86\)32\.73 \(\+9\.67\)31\.91 \(\+6\.42\)67\.02 \(\+1\.50\)72\.47 \(\+1\.19\)UGC69\.3742\.7051\.7421\.4929\.1863\.0668\.92\+ ACE75\.28 \(\+5\.91\)53\.83 \(\+11\.13\)59\.37 \(\+7\.63\)30\.82 \(\+9\.33\)33\.49 \(\+4\.31\)64\.87 \(\+1\.81\)70\.19 \(\+1\.27\)SGBGC71\.2244\.6255\.4825\.1627\.0264\.1271\.96\+ ACE76\.26 \(\+5\.04\)56\.28 \(\+11\.66\)64\.04 \(\+8\.56\)31\.93 \(\+6\.77\)33\.75 \(\+6\.73\)66\.22 \(\+2\.10\)73\.13 \(\+1\.17\)LINKX\-90\.7766\.0682\.0461\.9556\.0069\.5474\.59SCAL60\.6250\.1356\.4840\.1342\.6657\.7162\.49\+ ACE73\.29 \(\+12\.67\)57\.11 \(\+6\.98\)65\.77 \(\+9\.29\)47\.64 \(\+7\.51\)47\.18 \(\+4\.52\)61\.02 \(\+3\.31\)64\.84 \(\+2\.35\)FGC65\.4942\.4857\.6338\.1744\.3759\.3867\.52\+ ACE74\.71 \(\+9\.22\)52\.33 \(\+9\.85\)70\.47 \(\+12\.84\)49\.08 \(\+10\.91\)47\.65 \(\+3\.28\)61\.73 \(\+2\.35\)69\.21 \(\+1\.69\)UGC63\.6144\.5552\.3841\.2241\.4955\.4664\.37\+ ACE71\.08 \(\+7\.47\)50\.69 \(\+6\.14\)67\.24 \(\+14\.86\)47\.33 \(\+6\.11\)46\.21 \(\+4\.72\)60\.28 \(\+4\.82\)66\.52 \(\+2\.15\)SGBGC62\.6847\.6054\.1842\.9145\.4261\.5564\.93\+ ACE71\.53 \(\+8\.85\)56\.48 \(\+8\.88\)63\.24 \(\+9\.06\)46\.47 \(\+3\.56\)49\.02 \(\+3\.60\)63\.88 \(\+2\.33\)66\.87 \(\+1\.94\)GloGNN\-90\.6666\.1983\.0062\.0954\.6872\.6877\.48SCAL59\.4746\.2861\.5843\.8440\.9157\.0966\.53\+ ACE72\.29 \(\+12\.82\)55\.46 \(\+9\.18\)70\.34 \(\+8\.76\)49\.28 \(\+5\.44\)46\.26 \(\+5\.35\)59\.20 \(\+2\.11\)67\.91 \(\+1\.38\)FGC63\.8145\.9266\.9142\.7043\.2861\.7370\.46\+ ACE74\.77 \(\+10\.96\)53\.42 \(\+7\.50\)74\.27 \(\+7\.36\)50\.38 \(\+7\.68\)46\.62 \(\+3\.34\)63\.78 \(\+2\.05\)71\.93 \(\+1\.47\)UGC61\.4942\.9664\.0445\.6140\.3660\.2968\.74\+ ACE73\.68 \(\+12\.19\)51\.77 \(\+8\.81\)72\.47 \(\+8\.43\)49\.71 \(\+4\.10\)45\.24 \(\+4\.88\)63\.21 \(\+2\.92\)70\.87 \(\+2\.13\)SGBGC67\.3347\.1563\.7745\.2641\.2761\.2469\.11\+ ACE78\.43 \(\+11\.10\)56\.29 \(\+9\.14\)74\.55 \(\+10\.78\)52\.82 \(\+7\.56\)47\.50 \(\+6\.23\)63\.63 \(\+2\.39\)72\.18 \(\+3\.07\) ### 4\.2RQ1: Performance Gains from ACE We examine how ACE improves the established coarsening training pipelines\. As shown in Tables[3](https://arxiv.org/html/2607.21885#S4.T3)and[8](https://arxiv.org/html/2607.21885#A4.T8), adding ACE yields consistent and significant gains across all backbones and datasets\. The gains are notably striking on heterophilic graphs—where coarsening tends to discard more essential graph information—with increases of up to 14\.86\. These confirm that ACE markedly enhances the efficacy of coarsening training, especially under heterophilic conditions\. Beyond these overall improvements, ACE also significantly outperforms the naive auxiliary loss used in the toy experiments\. By using the refined projector, ACE achievesroughly twice the performance gainof the naive formulation\. This highlights the value of our refinement: it not only strengthens the effect of reintegrating the discarded information but also validates the central premise that restoring lost information is essential for handling heterophily in coarsening\-based training\. Moreover, ACE also benefits other graph\-reduction methods beyond coarsening, such asgraph condensation\[Jin et al\.,[2022](https://arxiv.org/html/2607.21885#bib.bib24)\]\(Table[9](https://arxiv.org/html/2607.21885#A4.T9)\), and remains robust even underextreme coarsening ratio\(Table[10](https://arxiv.org/html/2607.21885#A4.T10)\), highlighting its generality and broad applicability\. ### 4\.3RQ2: Impact of the Refined Projector The optimization of Eq\. \([3\.2\.1](https://arxiv.org/html/2607.21885#S3.Ex2)\) for obtainingP\(ϕ∗\)P\(\\phi^\{\\ast\}\)is governed by a trade\-off hyperparameterβ\\beta, which balances the reconstruction and anisotropic regularization terms and thus shapes the refined projector\. To evaluate how sensitive the learned projector—and consequently the coarsening training—is to this choice, we conduct an ablation study over a wide range ofβ\\betawithin \{0\.01,0\.1,1,10,100\}\. We perform this analysis using two strong pipelines \(SCAL and SGBGC\) and two large heterophilic benchmarks \(Pokec and Snap\)\. Additional results for UGC and FGC are provided in Appendix[D\.4](https://arxiv.org/html/2607.21885#A4.SS4)\. \(a\) \(b\) \(c\) \(d\) Figure 2:Effect ofβ\\betaacross coarsening pipelines, GNN backbones, and datasets\.More results can be found in Figure[5](https://arxiv.org/html/2607.21885#A4.F5)\.Figure[2](https://arxiv.org/html/2607.21885#S4.F2)\(and Figure[5](https://arxiv.org/html/2607.21885#A4.F5)\) showcase that varyingβ\\betaacross two orders of magnitude produces only minor performance differences, consistently across datasets and backbone GNNs\. This highlights that the learning dynamics of the refined projectorP\(ϕ∗\)P\(\\phi^\{\\ast\}\)are highly robust to the choice ofβ\\beta\. Although occasional small fluctuations can be observed, the overall trend remains stable, and settingβ\\betabe 1 already yields superior performance without further tuning\. To sum up, such insensitivity to hyperparameter choice makes ACEpractically convenient, requiring minimal effort to deploy while preserving strong performance across diverse settings\. ##### Beyond the Projection Module\. Readers are encouraged to consult the additional ablation studies in Appendix[D\.4](https://arxiv.org/html/2607.21885#A4.SS4)\(Tables[12](https://arxiv.org/html/2607.21885#A4.T12)and[13](https://arxiv.org/html/2607.21885#A4.T13)\), which investigate the remaining components of ACE and offer an extensive understanding of their isolated contributions beyond the projector module\. \(a\) \(b\) Figure 3:Comparison of preprocessing time for SCAL, SGBGC, and their ACE\-enhanced variants\.Complete results are provided in Figure[6](https://arxiv.org/html/2607.21885#A4.F6)\. ### 4\.4RQ3: Effects of ACE on Efficiency and Resource Consumption ##### Preprocessing Overhead\. Coarsening training pipelines require a preprocessing stage to construct coarsened graphs, typically incurring substantial cost \(often on the order ofn⋅En\\cdot E\)\. ACE adds one additional step—learning the refined projectorP\(ϕ∗\)P\(\\phi^\{\\ast\}\)—but, as discussed in Section[3\.2\.3](https://arxiv.org/html/2607.21885#S3.SS2.SSS3), this operation scales only withn\+En\+Elevel and is therefore lightweight relative to the core coarsening procedure\. Figure[3](https://arxiv.org/html/2607.21885#S4.F3)\(with full results in Figure[6](https://arxiv.org/html/2607.21885#A4.F6)\) confirms this analysis: ACE introduces only a negligible increase in preprocessing time across all pipelines and datasets\. This validates that the refined projector construction is highly efficient, allowing ACE to improve coarsened representations without altering the overall preprocessing cost profile\. ##### Training Overhead\. We next assess the runtime and memory efficiency of ACE during model training, using the large\-scale Pokec dataset and all six backbone GNNs\. As shown in Figure[4](https://arxiv.org/html/2607.21885#S4.F4)\(with additional results in Figures[7](https://arxiv.org/html/2607.21885#A4.F7)and[8](https://arxiv.org/html/2607.21885#A4.F8)\), ACE adds only a small overhead: approximately4%–7%in both training time per epoch and GPU memory usage\. Given that ACE delivers over 10% accuracy improvement on challenging heterophilic graphs, this modest overhead represents a highly favorable trade\-off and highlights the practicality of integrating ACE into existing coarsening\-based pipelines\. \(a\) \(b\) Figure 4:Training memory usage and per\-epoch runtime \(on Pokec\) of SCAL and SCAL\+ACE across diverse backbone GNNs\.More results are provided in Tables[7](https://arxiv.org/html/2607.21885#A4.F7)and[8](https://arxiv.org/html/2607.21885#A4.F8)\.Table 4:Comparison with state\-of\-the\-art scalable GNN training methods based on graph data reduction\. Results on aGCNbackbone with a 10% reduction ratio are reported in terms of test accuracy and total training time\.Complementary results are deferred to Table[11](https://arxiv.org/html/2607.21885#A4.T11)\.CategoryMethodPokecSnapGamersOgbn\-productACCTime \(min\)ACCTime \(min\)ACCTime \(min\)ACCTime \(min\)CoarseningFGC53\.8124\.7323\.0631\.6640\.1412\.3971\.2832\.71UGC51\.7423\.6921\.4929\.1942\.7011\.2368\.9231\.41Data\-AdaptiveGECC60\.6633\.8229\.3138\.7750\.6618\.4371\.6945\.29Subgraph\-SamplingAGS57\.3221\.8128\.3229\.4848\.8110\.1371\.0230\.18OursFGC\+ACE61\.6725\.6732\.7332\.9252\.5212\.8972\.4733\.65UGC\+ACE59\.3724\.3430\.8231\.2553\.8311\.7270\.1932\.24 ### 4\.5RQ4: Competitiveness of Conventional Methods with ACE To assess the position of ACE among existing scalable and efficient GNN training paradigms, we compare ACE\-enhanced conventional coarsening methods—specifically FGC and UGC—with representative state\-of\-the\-art approaches beyond coarsening, including the sampling\-based method AGS\[Das et al\.,[2024](https://arxiv.org/html/2607.21885#bib.bib10)\]and the graph condensation method GECCGong et al\. \[[2026](https://arxiv.org/html/2607.21885#bib.bib19)\]\. Results using the GCN backbone are presented here, while those with GPRGNN backbone are deferred to Appendix[D\.4](https://arxiv.org/html/2607.21885#A4.SS4)\. As shown in Table[4](https://arxiv.org/html/2607.21885#S4.T4)\(with additional results in Table[11](https://arxiv.org/html/2607.21885#A4.T11)\), the conventional coarsening methods FGC and UGC substantially underperform state\-of\-the\-art approaches when used alone\. However, after incorporating ACE, both methods exhibit significant performance gains, achieving results that are comparable to, and in several cases surpass, those of the state\-of\-the\-art baselines\. These findings suggest that ACE can substantially enhance the competitiveness of conventional coarsening\-based training methods\. Furthermore, ACE introduces only negligible computational overhead relative to the compared baselines, resulting in a more favorable performance\-cost trade\-off\. Overall, the results highlight ACE as a practical and promising direction for revitalizing conventional coarsening\-based training methods in the era of scalable graph learning\. ## 5Conclusion ##### Paper Summary\. We study how graph heterophily affects GNN performance in coarsening\-based GNN training\. Guided by empirical observations and supported by our theoretical analysis, we interpret the degradation as that for heterophilic graphs coarsening discards more essential graph information than for homophilic graphs, which is an underexplored perspective in prior research\. To address this issue, we introduced ACE, which first learns a heterophily\-aware refined projector via Anisotropic Structural Regularization and incorporates it into an auxiliary loss; we then combine the designs and propose an improved optimization objective via Homoscedastic Uncertainty weighting, thus adaptively reintegrating discarded information to enhance coarsening\-based training\. Across diverse coarsening training pipelines, benchmarks, and backbone GNNs, ACE consistently achieves superior performance gains with minimal computational overhead, offering an efficient and easy\-to\-deploy enhancement for practical coarsening training\. ##### Limitations and Future Work\. Although ACE substantially improves coarsening\-based training, a non\-negligible performance gap remains compared to full\-graph training\. This is primarily because ACE recovers discarded information implicitly via the refined projector, rather than modeling explicit intra\-supernode structure\. While this design preserves scalability and efficiency, it may limit the achievable performance\. A promising direction for future work is to develop more expressive mechanisms for integrating discarded information, extending the ACE framework to further close this gap without sacrificing scalability\. ###### Acknowledgements\. Yifan Chen acknowledges funding from National Natural Science Foundation of China \(NSFC\) under grant62502408, Research Grants Council \(RGC\) under grant22303424, GuangDong Basic and Applied Basic Research Foundation under grant2025A1515010259, and Guangdong and Hong Kong Universities “1\+1\+1” Joint Research Collaboration Scheme under grant2025A050500\. ## References - Cai and Wang \[2020\]Chen Cai and Yusu Wang\.A note on over\-smoothing for graph neural networks, 2020\.URL[https://arxiv\.org/abs/2006\.13318](https://arxiv.org/abs/2006.13318)\. - Chamberlain et al\. \[2021\]Ben Chamberlain, James Rowbottom, Maria I Gorinova, Michael Bronstein, Stefan Webb, and Emanuele Rossi\.Grand: Graph neural diffusion\.In Marina Meila and Tong Zhang, editors,*Proceedings of the 38th International Conference on Machine Learning*, volume 139 of*Proceedings of Machine Learning Research*, pages 1407–1418\. PMLR, 18–24 Jul 2021\.URL[https://proceedings\.mlr\.press/v139/chamberlain21a\.html](https://proceedings.mlr.press/v139/chamberlain21a.html)\. - Chen et al\. \[2022a\]Jie Chen, Yousef Saad, and Zechen Zhang\.Graph coarsening: from scientific computing to machine learning\.*SeMA Journal*, 79\(1\):187–223, 2022a\. - Chen et al\. \[2022b\]Qi Chen, Yifei Wang, Yisen Wang, Jiansheng Yang, and Zhouchen Lin\.Optimization\-induced graph implicit nonlinear diffusion\.In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors,*Proceedings of the 39th International Conference on Machine Learning*, volume 162 of*Proceedings of Machine Learning Research*, pages 3648–3661\. PMLR, 17–23 Jul 2022b\.URL[https://proceedings\.mlr\.press/v162/chen22z\.html](https://proceedings.mlr.press/v162/chen22z.html)\. - Chen et al\. \[2023\]Yifan Chen, Rentian Yao, Yun Yang, and Jie Chen\.A gromov\-Wasserstein geometric view of spectrum\-preserving graph coarsening\.In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors,*Proceedings of the 40th International Conference on Machine Learning*, volume 202 of*Proceedings of Machine Learning Research*, pages 5257–5281\. PMLR, 23–29 Jul 2023\. - Chien et al\. \[2021\]Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic\.Adaptive universal generalized pagerank graph neural network\.In*International Conference on Learning Representations*, 2021\.URL[https://openreview\.net/forum?id=n6jl7fLxrP](https://openreview.net/forum?id=n6jl7fLxrP)\. - Chung \[1997\]Fan Chung\.*Spectral Graph Theory*, volume 92\.CBMS Regional Conference Series in Mathematics, 1997\.ISBN 978\-0\-8218\-0315\-8\.[/10\.1090/cbms/092](https://arxiv.org/doi.org//10.1090/cbms/092)\. - Cover \[1999\]Thomas M Cover\.*Elements of information theory*\.John Wiley & Sons, 1999\. - Dan et al\. \[2023\]Tingting Dan, Jiaqi Ding, Ziquan Wei, Shahar Kovalsky, Minjeong Kim, Won Hwa Kim, and Guorong Wu\.Re\-think and re\-design graph neural networks in spaces of continuous graph diffusion functionals\.In A\. Oh, T\. Naumann, A\. Globerson, K\. Saenko, M\. Hardt, and S\. Levine, editors,*Advances in Neural Information Processing Systems*, volume 36, pages 59375–59387\. Curran Associates, Inc\., 2023\. - Das et al\. \[2024\]Siddhartha Shankar Das, S M Ferdous, Mahantesh M\. Halappanavar, Edoardo Serra, and Alex Pothen\.Ags\-gnn: Attribute\-guided sampling for graph neural networks\.In*Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining*, KDD ’24, page 538–549, New York, NY, USA, 2024\. Association for Computing Machinery\.ISBN 9798400704901\.[10\.1145/3637528\.3671940](https://arxiv.org/doi.org/10.1145/3637528.3671940)\.URL[https://doi\.org/10\.1145/3637528\.3671940](https://doi.org/10.1145/3637528.3671940)\. - Deng et al\. \[2024\]Chenhui Deng, Zichao Yue, and Zhiru Zhang\.Polynormer: Polynomial\-expressive graph transformer in linear time\.In*The Twelfth International Conference on Learning Representations*, 2024\.URL[https://openreview\.net/forum?id=hmv1LpNfXa](https://openreview.net/forum?id=hmv1LpNfXa)\. - Dickens et al\. \[2024\]Charles Dickens, Edward Huang, Aishwarya Reganti, Jiong Zhu, Karthik Subbian, and Danai Koutra\.Graph coarsening via convolution matching for scalable graph neural network training\.In*Companion Proceedings of the ACM on Web Conference 2024*, WWW ’24, page 1502–1510, New York, NY, USA, 2024\. Association for Computing Machinery\.ISBN 9798400701726\.URL[https://doi\.org/10\.1145/3589335\.3651920](https://doi.org/10.1145/3589335.3651920)\. - Elhag et al\. \[2022\]Ahmed A\. A\. Elhag, Gabriele Corso, Hannes Stärk, and Michael M\. Bronstein\.Graph anisotropic diffusion for molecules\.In*ICLR2022 Machine Learning for Drug Discovery*, 2022\.URL[https://openreview\.net/forum?id=MDYOh60QN94](https://openreview.net/forum?id=MDYOh60QN94)\. - Eliasof et al\. \[2021\]Moshe Eliasof, Eldad Haber, and Eran Treister\.Pde\-gcn: Novel architectures for graph neural networks motivated by partial differential equations\.In M\. Ranzato, A\. Beygelzimer, Y\. Dauphin, P\.S\. Liang, and J\. Wortman Vaughan, editors,*Advances in Neural Information Processing Systems*, volume 34, pages 3836–3849\. Curran Associates, Inc\., 2021\. - Fahrbach et al\. \[2020\]Matthew Fahrbach, Gramoz Goranci, Richard Peng, Sushant Sachdeva, and Chi Wang\.Faster graph embeddings via coarsening\.In Hal Daumé III and Aarti Singh, editors,*Proceedings of the 37th International Conference on Machine Learning*, volume 119 of*Proceedings of Machine Learning Research*, pages 2953–2963\. PMLR, 13–18 Jul 2020\.URL[https://proceedings\.mlr\.press/v119/fahrbach20a\.html](https://proceedings.mlr.press/v119/fahrbach20a.html)\. - Fu et al\. \[2023\]Guoji Fu, Mohammed Haroon Dupty, Yanfei Dong, and Wee Sun Lee\.Implicit graph neural diffusion based on constrained dirichlet energy minimization\.In*NeurIPS 2023 Workshop: New Frontiers in Graph Learning*, 2023\.URL[https://openreview\.net/forum?id=a9loLCbWs1](https://openreview.net/forum?id=a9loLCbWs1)\. - Giovanni et al\. \[2023\]Francesco Di Giovanni, James Rowbottom, Benjamin Paul Chamberlain, Thomas Markovich, and Michael M\. Bronstein\.Understanding convolution on graphs via energies\.*Transactions on Machine Learning Research*, 2023\.ISSN 2835\-8856\.URL[https://openreview\.net/forum?id=v5ew3FPTgb](https://openreview.net/forum?id=v5ew3FPTgb)\. - Gong et al\. \[2024\]Chenghua Gong, Yao Cheng, Xiang Li, Caihua Shan, and Siqiang Luo\.Learning from graphs with heterophily: Progress and future, 2024\.URL[https://arxiv\.org/abs/2401\.09769](https://arxiv.org/abs/2401.09769)\. - Gong et al\. \[2026\]Shengbo Gong, Mohammad Hashemi, Juntong Ni, Carl Yang, and Wei Jin\.Scalable graph condensation with evolving capabilities\.In*Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V\.1*, KDD ’26, page 314–323, New York, NY, USA, 2026\. Association for Computing Machinery\.ISBN 9798400722585\.[10\.1145/3770854\.3780217](https://arxiv.org/doi.org/10.1145/3770854.3780217)\.URL[https://doi\.org/10\.1145/3770854\.3780217](https://doi.org/10.1145/3770854.3780217)\. - Han et al\. \[2023\]Andi Han, Dai Shi, Lequan Lin, and Junbin Gao\.From continuous dynamics to graph neural networks: Neural diffusion and beyond, 2023\.URL[https://arxiv\.org/abs/2310\.10121](https://arxiv.org/abs/2310.10121)\. - Hashemi et al\. \[2024\]Mohammad Hashemi, Shengbo Gong, Juntong Ni, Wenqi Fan, B\. Aditya Prakash, and Wei Jin\.A comprehensive survey on graph reduction: Sparsification, coarsening, and condensation\.In Kate Larson, editor,*Proceedings of the Thirty\-Third International Joint Conference on Artificial Intelligence, IJCAI\-24*, pages 8058–8066\. International Joint Conferences on Artificial Intelligence Organization, 8 2024\.[10\.24963/ijcai\.2024/891](https://arxiv.org/doi.org/10.24963/ijcai.2024/891)\.URL[https://doi\.org/10\.24963/ijcai\.2024/891](https://doi.org/10.24963/ijcai.2024/891)\.Survey Track\. - Hu et al\. \[2020\]Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec\.Open graph benchmark: Datasets for machine learning on graphs\.In H\. Larochelle, M\. Ranzato, R\. Hadsell, M\.F\. Balcan, and H\. Lin, editors,*Advances in Neural Information Processing Systems*, volume 33, pages 22118–22133\. Curran Associates, Inc\., 2020\. - Huang et al\. \[2021\]Zengfeng Huang, Shengzhong Zhang, Chong Xi, Tang Liu, and Min Zhou\.Scaling up graph neural networks via graph coarsening\.In*Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining*, KDD ’21, page 675–684, New York, NY, USA, 2021\. Association for Computing Machinery\.ISBN 9781450383325\. - Jin et al\. \[2022\]Wei Jin, Lingxiao Zhao, Shichang Zhang, Yozen Liu, Jiliang Tang, and Neil Shah\.Graph condensation for graph neural networks\.In*International Conference on Learning Representations*, 2022\.URL[https://openreview\.net/forum?id=WLEx3Jo4QaB](https://openreview.net/forum?id=WLEx3Jo4QaB)\. - Jin et al\. \[2020\]Yu Jin, Andreas Loukas, and Joseph JaJa\.Graph coarsening with preserved spectral properties\.In Silvia Chiappa and Roberto Calandra, editors,*Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics*, volume 108 of*Proceedings of Machine Learning Research*, pages 4452–4462\. PMLR, 26–28 Aug 2020\. - Joly and Keriven \[2024\]Antonin Joly and Nicolas Keriven\.Graph coarsening with message\-passing guarantees, 2024\.URL[https://arxiv\.org/abs/2405\.18127](https://arxiv.org/abs/2405.18127)\. - Kataria et al\. \[2024\]Mohit Kataria, Sandeep Kumar, and Jayadeva\.Ugc: Universal graph coarsening\.In A\. Globerson, L\. Mackey, D\. Belgrave, A\. Fan, U\. Paquet, J\. Tomczak, and C\. Zhang, editors,*Advances in Neural Information Processing Systems*, volume 37, pages 63057–63081\. Curran Associates, Inc\., 2024\. - Kendall et al\. \[2018\]Alex Kendall, Yarin Gal, and Roberto Cipolla\.Multi\-task learning using uncertainty to weigh losses for scene geometry and semantics\.In*Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition \(CVPR\)*, June 2018\. - Kingma and Ba \[2014\]Diederik P\. Kingma and Jimmy Ba\.Adam: A method for stochastic optimization, 2014\.URL[https://arxiv\.org/abs/1412\.6980](https://arxiv.org/abs/1412.6980)\. - Kipf and Welling \[2017\]Thomas N\. Kipf and Max Welling\.Semi\-supervised classification with graph convolutional networks, 2017\.URL[https://openreview\.net/forum?id=SJU4ayYgl](https://openreview.net/forum?id=SJU4ayYgl)\. - Kumar et al\. \[2023a\]Manoj Kumar, Anurag Sharma, and Sandeep Kumar\.A unified framework for optimization\-based graph coarsening\.*Journal of Machine Learning Research*, 24\(118\):1–50, 2023a\.URL[http://jmlr\.org/papers/v24/22\-1085\.html](http://jmlr.org/papers/v24/22-1085.html)\. - Kumar et al\. \[2023b\]Manoj Kumar, Anurag Sharma, Shashwat Saxena, and Sandeep Kumar\.Featured graph coarsening with similarity guarantees\.In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors,*Proceedings of the 40th International Conference on Machine Learning*, volume 202 of*Proceedings of Machine Learning Research*, pages 17953–17975\. PMLR, 23–29 Jul 2023b\. - Li et al\. \[2022\]Xiang Li, Renyu Zhu, Yao Cheng, Caihua Shan, Siqiang Luo, Dongsheng Li, and Weining Qian\.Finding global homophily in graph neural networks when meeting heterophily\.In*ICML*\. PMLR, 2022\.URL[https://proceedings\.mlr\.press/v162/li22ad\.html](https://proceedings.mlr.press/v162/li22ad.html)\. - Lim et al\. \[2021\]Derek Lim, Felix Matthew Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Prasad Bhalerao, and Ser\-Nam Lim\.Large scale learning on non\-homophilous graphs: New benchmarks and strong simple methods\.In A\. Beygelzimer, Y\. Dauphin, P\. Liang, and J\. Wortman Vaughan, editors,*Advances in Neural Information Processing Systems*, 2021\. - Liu et al\. \[2018\]Yike Liu, Tara Safavi, Abhilash Dighe, and Danai Koutra\.Graph summarization methods and applications: A survey\.*ACM Comput\. Surv\.*, 51\(3\), jun 2018\.ISSN 0360\-0300\.URL[https://doi\.org/10\.1145/3186727](https://doi.org/10.1145/3186727)\. - Loukas and Vandergheynst \[2018\]Andreas Loukas and Pierre Vandergheynst\.Spectrally approximating large graphs with smaller graphs\.In Jennifer Dy and Andreas Krause, editors,*Proceedings of the 35th International Conference on Machine Learning*, volume 80 of*Proceedings of Machine Learning Research*, pages 3237–3246\. PMLR, 10–15 Jul 2018\.URL[https://proceedings\.mlr\.press/v80/loukas18a\.html](https://proceedings.mlr.press/v80/loukas18a.html)\. - Luan et al\. \[2024\]Sitao Luan, Chenqing Hua, Qincheng Lu, Liheng Ma, Lirong Wu, Xinyu Wang, Minkai Xu, Xiao\-Wen Chang, Doina Precup, Rex Ying, Stan Z\. Li, Jian Tang, Guy Wolf, and Stefanie Jegelka\.The heterophilic graph learning handbook: Benchmarks, models, theoretical analysis, applications and challenges, 2024\.URL[https://arxiv\.org/abs/2407\.09618](https://arxiv.org/abs/2407.09618)\. - Maskey et al\. \[2023\]Sohir Maskey, Raffaele Paolino, Aras Bacho, and Gitta Kutyniok\.A fractional graph laplacian approach to oversmoothing\.In A\. Oh, T\. Naumann, A\. Globerson, K\. Saenko, M\. Hardt, and S\. Levine, editors,*Advances in Neural Information Processing Systems*, volume 36, pages 13022–13063\. Curran Associates, Inc\., 2023\. - Nadaraya \[1964\]E\. A\. Nadaraya\.On estimating regression\.*Theory of Probability & Its Applications*, 9\(1\):141–142, 1964\.[10\.1137/1109020](https://arxiv.org/doi.org/10.1137/1109020)\.URL[https://doi\.org/10\.1137/1109020](https://doi.org/10.1137/1109020)\. - Perona and Malik \[1990\]P\. Perona and J\. Malik\.Scale\-space and edge detection using anisotropic diffusion\.*IEEE Transactions on Pattern Analysis and Machine Intelligence*, 12\(7\):629–639, 1990\.[10\.1109/34\.56205](https://arxiv.org/doi.org/10.1109/34.56205)\. - Platonov et al\. \[2023\]Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova\.A critical look at the evaluation of GNNs under heterophily: Are we really making progress?In*International Conference on Learning Representations*, 2023\.URL[https://openreview\.net/forum?id=tJbbQfw\-5wv](https://openreview.net/forum?id=tJbbQfw-5wv)\. - Purohit et al\. \[2014\]Manish Purohit, B\. Aditya Prakash, Chanhyun Kang, Yao Zhang, and V\.S\. Subrahmanian\.Fast influence\-based coarsening for large networks\.In*Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining*, KDD ’14, page 1296–1305, New York, NY, USA, 2014\. Association for Computing Machinery\.ISBN 9781450329569\.[10\.1145/2623330\.2623701](https://arxiv.org/doi.org/10.1145/2623330.2623701)\.URL[https://doi\.org/10\.1145/2623330\.2623701](https://doi.org/10.1145/2623330.2623701)\. - Qin et al\. \[2020\]Zhenyue Qin, Dongwoo Kim, and Tom Gedeon\.Rethinking softmax with cross\-entropy: Neural network classifier as mutual information estimator, 2020\.URL[https://arxiv\.org/abs/1911\.10688](https://arxiv.org/abs/1911.10688)\. - \[44\]J\. W\. Ruge and K\. Stüben\.*4\. Algebraic Multigrid*, pages 73–130\.[10\.1137/1\.9781611971057\.ch4](https://arxiv.org/doi.org/10.1137/1.9781611971057.ch4)\.URL[https://epubs\.siam\.org/doi/abs/10\.1137/1\.9781611971057\.ch4](https://epubs.siam.org/doi/abs/10.1137/1.9781611971057.ch4)\. - Rusch et al\. \[2023\]T\. Konstantin Rusch, Michael M\. Bronstein, and Siddhartha Mishra\.A survey on oversmoothing in graph neural networks, 2023\.URL[https://arxiv\.org/abs/2303\.10993](https://arxiv.org/abs/2303.10993)\. - Serafini and Guan \[2021\]Marco Serafini and Hui Guan\.Scalable graph neural network training: The case for sampling\.*SIGOPS Oper\. Syst\. Rev\.*, 55\(1\):68–76, June 2021\.ISSN 0163\-5980\.[10\.1145/3469379\.3469387](https://arxiv.org/doi.org/10.1145/3469379.3469387)\.URL[https://doi\.org/10\.1145/3469379\.3469387](https://doi.org/10.1145/3469379.3469387)\. - Veličković et al\. \[2018\]Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio\.Graph attention networks\.In*International Conference on Learning Representations*, 2018\.URL[https://openreview\.net/forum?id=rJXMpikCZ](https://openreview.net/forum?id=rJXMpikCZ)\. - Wang et al\. \[2023\]Xiao Wang, Deyu Bo, Chuan Shi, Shaohua Fan, Yanfang Ye, and Philip S\. Yu\.A survey on heterogeneous graph embedding: Methods, techniques, applications and sources\.*IEEE Transactions on Big Data*, 9\(2\):415–436, 2023\.[10\.1109/TBDATA\.2022\.3177455](https://arxiv.org/doi.org/10.1109/TBDATA.2022.3177455)\. - Wu et al\. \[2022\]Lingfei Wu, Peng Cui, Jian Pei, Liang Zhao, and Le Song\.*Graph Neural Networks: Foundations, Frontiers, and Applications*\.Springer, 2022\.ISBN 978\-981\-16\-6054\-2\.[10\.1007/978\-981\-16\-6054\-2](https://arxiv.org/doi.org/10.1007/978-981-16-6054-2)\.URL[https://doi\.org/10\.1007/978\-981\-16\-6054\-2](https://doi.org/10.1007/978-981-16-6054-2)\. - Wu et al\. \[2023\]Qitian Wu, Wentao Zhao, Chenxiao Yang, Hengrui Zhang, Fan Nie, Haitian Jiang, Yatao Bian, and Junchi Yan\.Sgformer: Simplifying and empowering transformers for large\-graph representations\.In A\. Oh, T\. Naumann, A\. Globerson, K\. Saenko, M\. Hardt, and S\. Levine, editors,*Advances in Neural Information Processing Systems*, volume 36, pages 64753–64773\. Curran Associates, Inc\., 2023\. - Xia et al\. \[2025\]Shuyin Xia, Xinjun Ma, Zhiyuan Liu, Cheng Liu, Sen Zhao, and Guoyin Wang\.Graph coarsening via supervised granular\-ball for scalable graph neural network training\.*Proceedings of the AAAI Conference on Artificial Intelligence*, 39\(12\):12872–12880, Apr\. 2025\.[10\.1609/aaai\.v39i12\.33404](https://arxiv.org/doi.org/10.1609/aaai.v39i12.33404)\.URL[https://ojs\.aaai\.org/index\.php/AAAI/article/view/33404](https://ojs.aaai.org/index.php/AAAI/article/view/33404)\. - Yan et al\. \[2022\]Yujun Yan, Milad Hashemi, Kevin Swersky, Yaoqing Yang, and Danai Koutra\.Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks\.In*2022 IEEE International Conference on Data Mining \(ICDM\)*, pages 1287–1292, 2022\. - Zhang and Yang \[2022\]Yu Zhang and Qiang Yang\.A survey on multi\-task learning\.*IEEE Transactions on Knowledge and Data Engineering*, 34\(12\):5586–5609, 2022\.[10\.1109/TKDE\.2021\.3070203](https://arxiv.org/doi.org/10.1109/TKDE.2021.3070203)\. - Zheng et al\. \[2024\]Xin Zheng, Yi Wang, Yixin Liu, Ming Li, Miao Zhang, Di Jin, Philip S\. Yu, and Shirui Pan\.Graph neural networks for graphs with heterophily: A survey, 2024\.URL[https://arxiv\.org/abs/2202\.07082](https://arxiv.org/abs/2202.07082)\. - Zhou et al\. \[2022\]Yu Zhou, Haixia Zheng, Xin Huang, Shufeng Hao, Dengao Li, and Jumin Zhao\.Graph neural networks: Taxonomy, advances, and trends\.*ACM Transactions on Intelligent Systems and Technology*, 13\(1\), jan 2022\.ISSN 2157\-6904\.[10\.1145/3495161](https://arxiv.org/doi.org/10.1145/3495161)\.URL[https://doi\.org/10\.1145/3495161](https://doi.org/10.1145/3495161)\. - Zhu et al\. \[2020\]Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra\.Beyond homophily in graph neural networks: Current limitations and effective designs\.In*NeurIPS*, 2020\.URL[https://proceedings\.neurips\.cc/paper\_files/paper/2020/file/58ae23d878a47004366189884c2f8440\-Paper\.pdf](https://proceedings.neurips.cc/paper_files/paper/2020/file/58ae23d878a47004366189884c2f8440-Paper.pdf)\. ## Appendix AProof of Proposition[2\.2](https://arxiv.org/html/2607.21885#S2.Thmtheorem2) Proposition[2\.2](https://arxiv.org/html/2607.21885#S2.Thmtheorem2)\.Let the GNN trained on the original graph bef\(;Θ∗∗\)f\(;\\Theta^\{\\ast\\ast\}\)and the one trained on the coarsened graph bef\(;Θ∗\)f\(;\\Theta^\{\\ast\}\), where Θ∗\\displaystyle\\Theta^\{\\ast\}≜argminΘℒ\(f\(A,X;Θ\),Y\),\\displaystyle\\triangleq\\arg\\min\\limits\_\{\\Theta\}\\mathcal\{L\}\(f\(A,X;\\Theta\),Y\)\\ ,\(12\)Θ∗∗\\displaystyle\\Theta^\{\\ast\\ast\}≜argminΘℒ\(f\(A′,X′;Θ\),Y′\)\.\\displaystyle\\triangleq\\arg\\min\\limits\_\{\\Theta\}\\mathcal\{L\}\(f\(A^\{\\prime\},X^\{\\prime\};\\Theta\),Y^\{\\prime\}\)\\ \.\(13\)When both models are evaluated on the original graph, the mutual information between their outputs satisfies I\(f\(A,X;Θ∗\);f\(A,X;Θ∗∗\)\)≤I\(f\(A,X;Θ∗\);Y\)−Ω,\\displaystyle I\(f\(A,X;\\Theta^\{\\ast\}\);f\(A,X;\\Theta^\{\\ast\\ast\}\)\)\\leq I\(f\(A,X;\\Theta^\{\\ast\}\);Y\)\-\\Omega\\ ,\(14\)whereΩ=I\(g\(𝒢∖𝒢′\);Y\|f\(A,X;Θ∗∗\)\)\\Omega=I\(g\(\\mathcal\{G\}\\setminus\\mathcal\{G\}^\{\\prime\}\);Y\|f\(A,X;\\Theta^\{\\ast\\ast\}\)\), andg:𝒢∖𝒢′↦𝒴g:\\mathcal\{G\}\\setminus\\mathcal\{G\}^\{\\prime\}\\mapsto\\mathcal\{Y\}is arbitrary neural network that maps𝒢∖𝒢′\\mathcal\{G\}\\setminus\\mathcal\{G\}^\{\\prime\}to the node label space𝒴\\mathcal\{Y\}and maximizes the conditional mutual informationI\(g\(𝒢∖𝒢′\);Y\|f\(A,X;Θ∗∗\)\)I\(g\(\\mathcal\{G\}\\setminus\\mathcal\{G\}^\{\\prime\}\);Y\|f\(A,X;\\Theta^\{\\ast\\ast\}\)\)\. ###### Proof\. We first introduce two lemmas that will serve as the foundation for our subsequent analysis\. ###### Lemma A\.1\(\(Theorem 1\[Qin et al\.,[2020](https://arxiv.org/html/2607.21885#bib.bib43)\]Restated\)\)\. In standard neural network training, the infimum of the expected cross\-entropy loss with a softmax output is equivalent to the mutual information between input and output variables, up to an additivelogc\\log cterm \(whereccis the number of classes\), provided that all class probabilities are bounded away from zero\[Qin et al\.,[2020](https://arxiv.org/html/2607.21885#bib.bib43)\]\. ###### Lemma A\.2\. LetYYbe the ground\-truth label, and letAAandBBbe the outputs of two different models trained to predictYY\. Assume thatAAandBBare conditionally independent givenYY, i\.e\.A⟂B∣YA\\perp B\\mid Y\. Then I\(A;B\)≤min\{I\(A;Y\),I\(B;Y\)\}\.I\(A;B\)\\;\\leq\\;\\min\\\{\\,I\(A;Y\),\\;I\(B;Y\)\\,\\\}\. ###### Proof\. The conditional independenceA⟂B∣YA\\perp B\\mid Yimplies the Markov chains A→Y→BandB→Y→A\.A\\to Y\\to B\\qquad\\text\{and\}\\qquad B\\to Y\\to A\.By the data\-processing inequality applied to the first Markov chain, any information shared betweenAAandBBmust flow throughYY, which yields I\(A;B\)≤I\(A;Y\)\.I\(A;B\)\\leq I\(A;Y\)\.Applying data processing to the second chain analogously gives I\(A;B\)≤I\(B;Y\)\.I\(A;B\)\\leq I\(B;Y\)\.Taking the minimum of the two bounds establishes I\(A;B\)≤min\{I\(A;Y\),I\(B;Y\)\}\.I\(A;B\)\\leq\\min\\\{I\(A;Y\),\\;I\(B;Y\)\\\}\.Intuitively, sinceAAandBBcan only correlate through the common targetYY, their mutual information cannot exceed the amount of information that each individually retains aboutYY\. The weaker predictor therefore determines the maximum possible dependence between them\. ∎ Now we begin the proof\. By Lemma[A\.1](https://arxiv.org/html/2607.21885#A1.Thmtheorem1), the optimization objectives in Eq\. \([2](https://arxiv.org/html/2607.21885#S2.E2)\) can be equivalently expressed in terms of mutual\-information maximization\. In particular, Θ∗\\displaystyle\\Theta^\{\\ast\}≜argmaxΘI\(f\(A,X;Θ\);Y\),\\displaystyle\\triangleq\\arg\\max\\limits\_\{\\Theta\}I\(f\(A,X;\\Theta\);Y\)\\ ,\(15\)Θ∗∗\\displaystyle\\Theta^\{\\ast\\ast\}≜argmaxΘI\(f\(A′,X′;Θ\);Y′\),\\displaystyle\\triangleq\\arg\\max\\limits\_\{\\Theta\}I\(f\(A^\{\\prime\},X^\{\\prime\};\\Theta\);Y^\{\\prime\}\)\\ ,\(16\)thus recasting the original loss\-minimization problems into the perspective of mutual\-information maximization\. Next, recall the chain\-rule of mutual information\[Cover,[1999](https://arxiv.org/html/2607.21885#bib.bib8)\]: I\(U,V;W\)−I\(U;W\)=I\(V;W\|U\)I\(U,V;W\)\-I\(U;W\)=I\(V;W\|U\)\(17\)LetU=f\(A,X;Θ∗∗\)U=f\(A,X;\\Theta^\{\\ast\\ast\}\),V=g\(𝒢∖𝒢′\)V=g\(\\mathcal\{G\}\\setminus\\mathcal\{G\}^\{\\prime\}\),W=YW=Y, we obtain: I\(f\(A,X;Θ∗∗\),g\(𝒢∖𝒢′\);Y\)−I\(f\(A,X;Θ∗∗\);Y\)\\displaystyle\\;I\\Bigl\(f\(A,X;\\Theta^\{\\ast\\ast\}\),g\(\\mathcal\{G\}\\setminus\\mathcal\{G\}^\{\\prime\}\);Y\\Bigr\)\-I\\Bigl\(f\(A,X;\\Theta^\{\\ast\\ast\}\);Y\\Bigr\)=\\displaystyle=I\(g\(𝒢∖𝒢′\);Y\|f\(A,X;Θ∗∗\)\)\.\\displaystyle\\;I\\Bigl\(g\(\\mathcal\{G\}\\setminus\\mathcal\{G\}^\{\\prime\}\);Y\\big\|f\(A,X;\\Theta^\{\\ast\\ast\}\)\\Bigr\)\\ \.\(18\)We focus on the termI\(f\(A,X;Θ∗∗\),g\(𝒢∖𝒢′\);Y\)I\\Bigl\(f\(A,X;\\Theta^\{\\ast\\ast\}\),g\(\\mathcal\{G\}\\setminus\\mathcal\{G\}^\{\\prime\}\);Y\\Bigr\), which quantifies the relationship between two models trained on different partitions of the graph𝒢\\mathcal\{G\}—namely,𝒢′\\mathcal\{G\}^\{\\prime\}and𝒢∖𝒢′\\mathcal\{G\}\\setminus\\mathcal\{G\}^\{\\prime\}—and the labels of the entire graph,YY\. Specifically, we leverage the data processing inequality\[Cover,[1999](https://arxiv.org/html/2607.21885#bib.bib8)\]: I\(U;V\)≥I\(U;W\),with Markov chain:U→V→W\.I\(U;V\)\\geq I\(U;W\),\\,\\text\{with Markov chain:\}\\,\\,U\\rightarrow V\\rightarrow W\\ \.\(19\)Notice thatf\(;Θ∗\)f\(;\\Theta^\{\\ast\}\),f\(;Θ∗∗\)f\(;\\Theta^\{\\ast\\ast\}\), andggare all deterministic functions\. Hence, by lettingU=YU=Y,V=f\(A,X;Θ∗\)V=f\(A,X;\\Theta^\{\\ast\}\), andW=\(f\(A,X;Θ∗∗\),g\(𝒢∖𝒢′\)\)W=\\Bigl\(f\(A,X;\\Theta^\{\\ast\\ast\}\),g\(\\mathcal\{G\}\\setminus\\mathcal\{G\}^\{\\prime\}\)\\Bigr\), we can derive the following inequality: I\(f\(A,X;Θ∗\);Y\)≥I\(f\(A,X;Θ∗∗\),g\(𝒢∖𝒢′\);Y\)\.I\\Bigl\(f\(A,X;\\Theta^\{\\ast\}\);Y\\Bigr\)\\geq I\\Bigl\(f\(A,X;\\Theta^\{\\ast\\ast\}\),g\(\\mathcal\{G\}\\setminus\\mathcal\{G\}^\{\\prime\}\);Y\\Bigr\)\\ \.\(20\)The inequality encapsulates the intuitive principle that the aggregate contribution from the model trained on the coarsened graph,f\(A,X;Θ∗∗\)f\(A,X;\\Theta^\{\\ast\\ast\}\), and the additional term representing the information excluded in the coarsened graph,g\(𝒢∖𝒢′\)g\(\\mathcal\{G\}\\setminus\\mathcal\{G\}^\{\\prime\}\), is bounded above by the output of the model trained directly on the full graph,f\(A,X;Θ∗\)f\(A,X;\\Theta^\{\\ast\}\)\. By combining Equation[A](https://arxiv.org/html/2607.21885#A1.Ex9)and Equation[20](https://arxiv.org/html/2607.21885#A1.E20), and observing thatI\(f\(A,X;Θ∗\);Y\)≥I\(f\(A,X;Θ∗∗\);Y\)I\\Bigl\(f\(A,X;\\Theta^\{\\ast\}\);Y\\Bigr\)\\geq I\\Bigl\(f\(A,X;\\Theta^\{\\ast\\ast\}\);Y\\Bigr\), the following inequality is derived: Δ\\displaystyle\\Delta=\|I\(f\(A,X;Θ∗\);Y\)−I\(f\(A,X;Θ∗∗\);Y\)\|\\displaystyle=\\Bigl\|I\\Bigl\(f\(A,X;\\Theta^\{\\ast\}\);Y\\Bigr\)\-I\\Bigl\(f\(A,X;\\Theta^\{\\ast\\ast\}\);Y\\Bigr\)\\Bigr\|≥I\(g\(𝒢∖𝒢′\);Y\|f\(A,X;Θ∗∗\)\)\.\\displaystyle\\geq I\\Bigl\(g\(\\mathcal\{G\}\\setminus\\mathcal\{G\}^\{\\prime\}\);Y\|f\(A,X;\\Theta^\{\\ast\\ast\}\)\\Bigr\)\\ \.\(21\) Finally, applying Lemma[A\.2](https://arxiv.org/html/2607.21885#A1.Thmtheorem2)withA:=f\(A,X;Θ∗\)A:=f\(A,X;\\Theta^\{\\ast\}\)andB:=f\(A,X;Θ∗∗\)B:=f\(A,X;\\Theta^\{\\ast\\ast\}\), and using the fact that I\(f\(A,X;Θ∗\);Y\)≥I\(f\(A,X;Θ∗∗\);Y\),\\displaystyle I\\Bigl\(f\(A,X;\\Theta^\{\\ast\}\);Y\\Bigr\)\\geq I\\Bigl\(f\(A,X;\\Theta^\{\\ast\\ast\}\);Y\\Bigr\)\\ ,\(22\)we obtain I\(f\(A,X;Θ∗\);f\(A,X;Θ∗∗\)\)\\displaystyle I\(f\(A,X;\\Theta^\{\\ast\}\);f\(A,X;\\Theta^\{\\ast\\ast\}\)\)≤I\(f\(A,X;Θ∗∗\);Y\)\\displaystyle\\leq I\\Bigl\(f\(A,X;\\Theta^\{\\ast\\ast\}\);Y\\Bigr\)\(23\)≤I\(f\(A,X;Θ∗\);Y\)−I\(g\(𝒢∖𝒢′\);Y\|f\(A,X;Θ∗∗\)\)\\displaystyle\\leq I\\Bigl\(f\(A,X;\\Theta^\{\\ast\}\);Y\\Bigr\)\-I\\Bigl\(g\(\\mathcal\{G\}\\setminus\\mathcal\{G\}^\{\\prime\}\);Y\|f\(A,X;\\Theta^\{\\ast\\ast\}\)\\Bigr\)\(24\)=I\(f\(A,X;Θ∗\);Y\)−Ω,\\displaystyle=I\\Bigl\(f\(A,X;\\Theta^\{\\ast\}\);Y\\Bigr\)\-\\Omega\\ ,\(25\)which establishes the desired inequality and completes the proof\. ∎ ## Appendix BProof of Proposition[3\.1](https://arxiv.org/html/2607.21885#S3.Thmtheorem1) Proposition[3\.1](https://arxiv.org/html/2607.21885#S3.Thmtheorem1)\.LetP\(ϕ∗\)P\(\\phi^\{\\ast\}\)denote the projector obtained by solvingminϕ𝒥ASR\(ϕ\)\\min\_\{\\phi\}\\mathcal\{J\}\_\{\\text\{ASR\}\}\(\\phi\)\. The resultingP\(ϕ∗\)P\(\\phi^\{\\ast\}\)acts as a conditional spectral filter that interpolates between two distinct regimes based on local homophily: - •Heterophilic Regime:In regions where‖Xi−Xj‖→∞\\\|X\_\{i\}\-X\_\{j\}\\\|\\to\\infty,P\(ϕ∗\)P\(\\phi^\{\\ast\}\)approaches the solution of identity reconstruction, prioritizing high\-frequency signal fidelity over structural smoothness\. - •Homophilic Regime:In regions where‖Xi−Xj‖→0\\\|X\_\{i\}\-X\_\{j\}\\\|\\to 0,P\(ϕ∗\)P\(\\phi^\{\\ast\}\)approaches the solution of isotropic laplacian smoothing, enforcing local smoothness\. ###### Proof\. We analyze the local optimality condition for a specific nodeiiby isolating the terms inℒ\(P\)\\mathcal\{L\}\(P\)dependent on\(P\(ϕ\)𝝁\)i\(P\(\\phi\)\\bm\{\\mu\}\)\_\{i\}\. The local objective is given by: ℒi\(\(P\(ϕ\)𝝁\)i\)=‖\(P\(ϕ\)𝝁\)i−Xi‖2\+λ∑j∈𝒩\(i\)exp\(−‖Xi−Xj‖2\)⋅‖\(P\(ϕ\)𝝁\)i−\(P\(ϕ\)𝝁\)j‖2\.\\mathcal\{L\}\_\{i\}\(\(P\(\\phi\)\\bm\{\\mu\}\)\_\{i\}\)=\\\|\(P\(\\phi\)\\bm\{\\mu\}\)\_\{i\}\-X\_\{i\}\\\|^\{2\}\+\\lambda\\sum\_\{j\\in\\mathcal\{N\}\(i\)\}\\exp\(\-\\\|X\_\{i\}\-X\_\{j\}\\\|^\{2\}\)\\cdot\\\|\(P\(\\phi\)\\bm\{\\mu\}\)\_\{i\}\-\(P\(\\phi\)\\bm\{\\mu\}\)\_\{j\}\\\|^\{2\}\.\(26\)The necessary condition for optimality requires the gradient∇\(P\(ϕ\)𝝁\)iℒi\\nabla\_\{\(P\(\\phi\)\\bm\{\\mu\}\)\_\{i\}\}\\mathcal\{L\}\_\{i\}to vanish\. Differentiating with respect to\(P\(ϕ\)𝝁\)i\(P\(\\phi\)\\bm\{\\mu\}\)\_\{i\}yields: 2\(\(P\(ϕ\)𝝁\)i−Xi\)\+2λ∑j∈𝒩\(i\)exp\(−‖Xi−Xj‖2\)\(\(P\(ϕ\)𝝁\)i−\(P\(ϕ\)𝝁\)j\)=0\.2\(\(P\(\\phi\)\\bm\{\\mu\}\)\_\{i\}\-X\_\{i\}\)\+2\\lambda\\sum\_\{j\\in\\mathcal\{N\}\(i\)\}\\exp\(\-\\\|X\_\{i\}\-X\_\{j\}\\\|^\{2\}\)\(\(P\(\\phi\)\\bm\{\\mu\}\)\_\{i\}\-\(P\(\\phi\)\\bm\{\\mu\}\)\_\{j\}\)=0\.\(27\)Rearranging terms to isolate\(P\(ϕ\)𝝁\)i\(P\(\\phi\)\\bm\{\\mu\}\)\_\{i\}, we obtain the closed\-form update rule for the optimal lifted signal: \(P\(ϕ∗\)𝝁\)i\(1\+λ∑j∈𝒩\(i\)exp\(−‖Xi−Xj‖2\)\)=Xi\+λ∑j∈𝒩\(i\)exp\(−‖Xi−Xj‖2\)\(P\(ϕ\)𝝁\)j\.\(P\(\\phi^\{\\ast\}\)\\bm\{\\mu\}\)\_\{i\}\\left\(1\+\\lambda\\sum\_\{j\\in\\mathcal\{N\}\(i\)\}\\exp\(\-\\\|X\_\{i\}\-X\_\{j\}\\\|^\{2\}\)\\right\)=X\_\{i\}\+\\lambda\\sum\_\{j\\in\\mathcal\{N\}\(i\)\}\\exp\(\-\\\|X\_\{i\}\-X\_\{j\}\\\|^\{2\}\)\(P\(\\phi\)\\bm\{\\mu\}\)\_\{j\}\.\(28\)This leads to the expression: \(P\(ϕ∗\)𝝁\)i=Xi\+λ∑j∈𝒩\(i\)exp\(−‖Xi−Xj‖2\)\(P\(ϕ\)𝝁\)j1\+λ∑j∈𝒩\(i\)exp\(−‖Xi−Xj‖2\)\.\(P\(\\phi^\{\\ast\}\)\\bm\{\\mu\}\)\_\{i\}=\\frac\{X\_\{i\}\+\\lambda\\sum\_\{j\\in\\mathcal\{N\}\(i\)\}\\exp\(\-\\\|X\_\{i\}\-X\_\{j\}\\\|^\{2\}\)\(P\(\\phi\)\\bm\{\\mu\}\)\_\{j\}\}\{1\+\\lambda\\sum\_\{j\\in\\mathcal\{N\}\(i\)\}\\exp\(\-\\\|X\_\{i\}\-X\_\{j\}\\\|^\{2\}\)\}\.\(29\)We now examine the asymptotic behavior of the weight coefficientexp\(−‖Xi−Xj‖2\)∈\(0,1\]\\exp\(\-\\\|X\_\{i\}\-X\_\{j\}\\\|^\{2\}\)\\in\(0,1\]\. Case 1 \(Homophily\):Consider a neighborhood where features are locally smooth, such thatXi≈XjX\_\{i\}\\approx X\_\{j\}\. Here,‖Xi−Xj‖→0\\\|X\_\{i\}\-X\_\{j\}\\\|\\to 0, implyingexp\(−‖Xi−Xj‖2\)→1\\exp\(\-\\\|X\_\{i\}\-X\_\{j\}\\\|^\{2\}\)\\to 1\. The update rule in Eq\. \([28](https://arxiv.org/html/2607.21885#A2.E28)\) converges to: \(P\(ϕ∗\)𝝁\)i≈Xi\+λ∑j∈𝒩\(i\)\(P\(ϕ\)𝝁\)j1\+λdi,\(P\(\\phi^\{\\ast\}\)\\bm\{\\mu\}\)\_\{i\}\\approx\\frac\{X\_\{i\}\+\\lambda\\sum\_\{j\\in\\mathcal\{N\}\(i\)\}\(P\(\\phi\)\\bm\{\\mu\}\)\_\{j\}\}\{1\+\\lambda d\_\{i\}\},\(30\)wheredid\_\{i\}is the degree of nodeii\. This formulation is equivalent to the first\-order approximation of the graph diffusion process \(Low\-Pass Filter\), where the node representation is smoothed by averaging over its neighbors\. Case 2 \(Heterophily\):Consider a neighborhood exhibiting high feature variance \(e\.g\., class boundaries\), such that‖Xi−Xj‖\\\|X\_\{i\}\-X\_\{j\}\\\|is large\. Here,exp\(−‖Xi−Xj‖2\)→0\\exp\(\-\\\|X\_\{i\}\-X\_\{j\}\\\|^\{2\}\)\\to 0\. The regularization term vanishes, yielding: \(P\(ϕ∗\)𝝁\)i≈Xi\+01\+0=Xi\.\(P\(\\phi^\{\\ast\}\)\\bm\{\\mu\}\)\_\{i\}\\approx\\frac\{X\_\{i\}\+0\}\{1\+0\}=X\_\{i\}\.\(31\)In this regime, the structural constraint is relaxed\. The projector effectively decouples nodeiifrom its dissimilar neighbors, allowing the reconstructed signal to retain the high\-frequency information residual essential for distinguishing heterophilic boundaries\. Sinceexp\(−‖Xi−Xj‖2\)\\exp\(\-\\\|X\_\{i\}\-X\_\{j\}\\\|^\{2\}\)varies continuously,P\(ϕ∗\)P\(\\phi^\{\\ast\}\)adaptively interpolates between these two extrema based on the local feature manifold\. ∎ ## Appendix CToy Experiment Results \(Full\) We provide the complete results of the toy experiments introduced in Section[3\.1](https://arxiv.org/html/2607.21885#S3.SS1), complementing the summary reported in Table[2](https://arxiv.org/html/2607.21885#S3.T2)\. The full results are shown in Table[5](https://arxiv.org/html/2607.21885#A3.T5)\. As observed, on heterophilic graphs, adding the simple auxiliary loss yields substantial performance gains, with an average improvement exceeding6 points\(see the “Δ↑\\Delta\\uparrow\(Heterophily\)” column\)\. These results further strengthen the empirical motivation behind our method\. Interestingly, although the auxiliary loss is designed to address heterophily, we also observe minor improvements on homophilic datasets\. This is consistent with the fact that many benchmarks labeled as “homophilic”—such as those from the OGB suite—actually contain mixed patterns with non\-negligible local heterophily\[Zheng et al\.,[2024](https://arxiv.org/html/2607.21885#bib.bib54), Gong et al\.,[2024](https://arxiv.org/html/2607.21885#bib.bib18), Luan et al\.,[2024](https://arxiv.org/html/2607.21885#bib.bib37)\]\. Such latent heterophily allows the same enhancement to deliver modest benefits even on nominally homophilic graphs\. Table 5:Full toy experiment results\. We highlight substantial improvements—observed exclusively on heterophilic datasets—inbold\. “Δ↑\\Delta\\uparrow\(Heterophily\)” reports the average gain on heterophilic graphs\.BackboneMethodHeterophilic GraphsHomophilic GraphsΔ↑\\Delta\\uparrow\(Heterophily\)GeniusGamersPokecArxivProductsGCNFull Graph87\.4262\.1875\.4571\.7475\.64/SCAL67\.4747\.3950\.4463\.4268\.374\.72SCAL w/ℒ~\\tilde\{\\mathcal\{L\}\}71\.32 \(\+3\.85\)52\.86 \(\+5\.47\)55\.29 \(\+4\.85\)64\.71 \(\+1\.29\)69\.11 \(\+0\.74\)FGC70\.1340\.1453\.8165\.5271\.286\.02FGC w/ℒ~\\tilde\{\\mathcal\{L\}\}75\.67 \(\+5\.54\)49\.26 \(\+9\.12\)57\.22 \(\+3\.41\)66\.18 \(\+0\.66\)72\.06 \(\+0\.78\)SGBGC71\.2244\.6255\.4864\.1271\.966\.00SGBGC w/ℒ~\\tilde\{\\mathcal\{L\}\}73\.81 \(\+2\.59\)53\.09 \(\+8\.47\)62\.42 \(\+6\.94\)65\.72 \(\+1\.60\)72\.37 \(\+0\.41\)LINKXFull Graph90\.7766\.0682\.0469\.5474\.59/SCAL60\.6250\.1356\.4857\.7162\.497\.14SCAL w/ℒ~\\tilde\{\\mathcal\{L\}\}70\.44 \(\+9\.82\)54\.28 \(\+4\.15\)63\.93 \(\+7\.45\)59\.38 \(\+1\.67\)63\.61 \(\+1\.12\)FGC65\.4942\.4857\.6359\.3867\.526\.91FGC w/ℒ~\\tilde\{\\mathcal\{L\}\}71\.92 \(\+6\.43\)48\.62 \(\+6\.14\)65\.81 \(\+8\.18\)61\.44 \(\+2\.06\)68\.77 \(\+1\.25\)SGBGC62\.6847\.6054\.1861\.5564\.936\.09SGBGC w/ℒ~\\tilde\{\\mathcal\{L\}\}68\.13 \(\+5\.45\)52\.83 \(\+5\.23\)61\.77 \(\+7\.59\)63\.24 \(\+1\.69\)66\.19 \(\+1\.26\)GloGNNFull Graph90\.6666\.1983\.0072\.6877\.48/SCAL59\.4746\.2861\.5857\.0966\.536\.97SCAL w/ℒ~\\tilde\{\\mathcal\{L\}\}67\.41 \(\+7\.94\)53\.11 \(\+6\.83\)67\.74 \(\+6\.16\)58\.32 \(\+1\.23\)67\.44 \(\+0\.91\)FGC63\.8145\.9266\.9161\.7370\.466\.13FGC w/ℒ~\\tilde\{\\mathcal\{L\}\}72\.33 \(\+8\.52\)51\.26 \(\+5\.34\)71\.44 \(\+4\.53\)63\.08 \(\+1\.35\)71\.52 \(\+1\.06\)SGBGC67\.3347\.1563\.7761\.2469\.116\.23SGBGC w/ℒ~\\tilde\{\\mathcal\{L\}\}73\.26 \(\+5\.93\)54\.31 \(\+7\.17\)69\.36 \(\+5\.59\)62\.75 \(\+1\.51\)70\.07 \(\+0\.96\) ## Appendix DExperimental Details This section provides all supplementary experimental details, including dataset statistics \(Appendix[D\.1](https://arxiv.org/html/2607.21885#A4.SS1)\), descriptions of coarsening training baselines \(Appendix[D\.2](https://arxiv.org/html/2607.21885#A4.SS2)\), backbone GNN introductions \(Appendix[D\.3](https://arxiv.org/html/2607.21885#A4.SS3)\), and additional experimental results \(Appendix[D\.4](https://arxiv.org/html/2607.21885#A4.SS4)\)\. ### D\.1Dataset Statistics All dataset statistics are summarized in Table[6](https://arxiv.org/html/2607.21885#A4.T6)\. To characterize homophily levels, we report theedge homophilymetric\[Zhu et al\.,[2020](https://arxiv.org/html/2607.21885#bib.bib56)\], where a smaller value ofℋ\\mathcal\{H\}indicates stronger heterophily\. Table 6:Statistics for the large graph datasets\.ℋ\\mathcal\{H\}quantifies the homophily level\[Zhu et al\.,[2020](https://arxiv.org/html/2607.21885#bib.bib56)\], where lower values denote stronger heterophily, and higher values indicate more homophilic graphs\.StatisticsHeterophilic GraphsHomophilic GraphsGeniusGamersPokecSnaparXiv\-yearogbn\-arXivogbn\-products\# Nodes421,961168,1141,632,8032,923,922169,343169,3432,449,029\# Edges984,9796,797,55730,622,56413,975,7881,166,2431,157,79961,859,140\# Features12765269128128100\# Classes222554047\#ℋ\\mathcal\{H\}0\.620\.450\.440\.070\.220\.660\.82 ### D\.2Overview of Coarsening Training Baselines We provide an overview of the four advanced coarsening\-based GNN training pipelines used in our experiments, summarized as follows: - •SCAL\[Huang et al\.,[2021](https://arxiv.org/html/2607.21885#bib.bib23)\]\.SCAL introduces a spectral graph coarsening technique\[Loukas and Vandergheynst,[2018](https://arxiv.org/html/2607.21885#bib.bib36)\]that operates in an unsupervised manner, relying solely on the inherent graph structure\. The coarsened graph is constructed during preprocessing, and GNNs are subsequently trained on these reduced graphs\. A novel coarsened graph convolution is proposed to maintain consistency between operations on the original and coarsened graphs\. Optimization is performed exclusively with respect to the loss computed on the coarsened graph labels\. As the first work to explore GNN training on coarsened graphs, SCAL has inspired numerous follow\-up studies aimed at improving computational efficiency and scalability\. - •FGC\[Kumar et al\.,[2023b](https://arxiv.org/html/2607.21885#bib.bib32)\]\.FGC enhances graph coarsening by incorporating both structural and feature information\. It formulates the coarsening process as the minimization of a Dirichlet energy functional, which unifies graph topology and node attributes\. The resulting coarsened graphs are more informative and support superior downstream GNN training\. - •UGC\[Kataria et al\.,[2024](https://arxiv.org/html/2607.21885#bib.bib27)\]\.UGC employs carefully designed hash functions for efficient graph coarsening on attributed graphs\. In addition, it explicitly accounts for the heterophily present in such graphs\. This combination allows for the generation of coarsened graphs that outperform those produced by FGC in terms of training effectiveness\. - •SGBGC\[Xia et al\.,[2025](https://arxiv.org/html/2607.21885#bib.bib51)\]\.SGBGC constructs coarsened graphs via an iterative granulation process\. It partitions the original graph into granular\-balls based on a node purity criterion, with each granular\-ball treated as a supernode\. This approach achieves substantial graph compression while preserving structural integrity, offering notable gains in both efficiency and scalability\. ### D\.3Backbone GNN Introductions We briefly summarize the six backbone GNNs used in our experiments: - •GCN\[Kipf and Welling,[2017](https://arxiv.org/html/2607.21885#bib.bib30)\]\.GCN approximates spectral graph convolution via a first\-order polynomial, aggregating normalized neighbor features in each layer\. Its simplicity and efficiency make it a strong baseline, though its inherent smoothness bias limits performance on heterophilic graphs\. - •LINKX\[Lim et al\.,[2021](https://arxiv.org/html/2607.21885#bib.bib34)\]\.LINKX separately embeds node features and adjacency structure and fuses them using MLPs, avoiding graph convolution altogether\. This decoupled design removes the homophily bias and scales well to large, low\-homophily graphs where many GNNs struggle\. - •GloGNN\[Li et al\.,[2022](https://arxiv.org/html/2607.21885#bib.bib33)\]\.GloGNN aggregates information using a learned global correlation matrix rather than local neighborhoods, enabling flexible \(including signed\) information mixing\. A closed\-form update with Woodbury acceleration allows linear\-time scaling, making GloGNN highly effective on heterophilic graphs\. - •GPRGNN\[Chien et al\.,[2021](https://arxiv.org/html/2607.21885#bib.bib6)\]\.GPRGNN learns the coefficients of a generalized PageRank propagation, enabling adaptive multi\-hop filtering\. By learning propagation weights instead of fixing them, it naturally adjusts to both homophilic and heterophilic patterns and mitigates over\-smoothing\. - •SGFormer\[Wu et al\.,[2023](https://arxiv.org/html/2607.21885#bib.bib50)\]\.SGFormer employs a single\-layer global attention paired with a lightweight GNN, capturing all\-pair interactions in one step with linear complexity\. It is extremely efficient but lacks the richer positional and structural encodings common in deeper graph Transformers\. - •Polynormer\[Deng et al\.,[2024](https://arxiv.org/html/2607.21885#bib.bib11)\]\.Polynormer is a kernel\-based graph Transformer that computes attention via graph kernels derived from sampled neighborhoods\. Its polynomial\-expressive architecture learns high\-degree equivariant polynomials through a linear local\-to\-global attention mechanism\. ### D\.4Supplementary Experimental Results This section provides additional experimental results that were moved from the main text due to space constraints\. Specifically, we include: - •Table[7](https://arxiv.org/html/2607.21885#A4.T7):Standard deviations corresponding to the mean results in Table[3](https://arxiv.org/html/2607.21885#S4.T3)\. - •Table[8](https://arxiv.org/html/2607.21885#A4.T8):ACE\-integrated results for the remaining backbone GNNs: GPRGNN, SGFormer, and Polynormer\. - •Table[9](https://arxiv.org/html/2607.21885#A4.T9):Results ontask\-optimizedcoarsening training pipelines—ConvMatch and GCond—using GCN and GPRGNN across all benchmarks\. - •Table[10](https://arxiv.org/html/2607.21885#A4.T10):Results under a 1% coarsening ratio, using GCN and GPRGNN as backbones\. - •Table[11](https://arxiv.org/html/2607.21885#A4.T11):Comparison between ACE\-enhanced coarsening methods and state\-of\-the\-art approaches under GPRGNN backbone\. - •Table[12](https://arxiv.org/html/2607.21885#A4.T12)and Table[13](https://arxiv.org/html/2607.21885#A4.T13):Comprehensive ablation study of ACE components under the GCN and GPRGNN backbones\. - •Figure[5](https://arxiv.org/html/2607.21885#A4.F5):Complete ablation results for the tradeoff coefficientβ\\beta\. - •Figure[6](https://arxiv.org/html/2607.21885#A4.F6):Full preprocessing\-time comparison between vanilla and ACE\-enhanced coarsening training pipelines\. - •Figure[7](https://arxiv.org/html/2607.21885#A4.F7):Full per\-epoch training\-time comparison across coarsening training pipelines\. - •Figure[8](https://arxiv.org/html/2607.21885#A4.F8):Full training memory consumption comparison across coarsening training pipelines\. - •Figure[9](https://arxiv.org/html/2607.21885#A4.F9):Assessment of feature noise robustness for ACE and state\-of\-the\-art methods\. Table 7:Standard deviations corresponding to the mean results reported in Table[3](https://arxiv.org/html/2607.21885#S4.T3)\.BackboneMethodHeterophilic GraphsHomophilic GraphsGeniusGamersPokecSnaparXiv\-yearogbn\-arXivogbn\-productsGCN\-0\.340\.290\.210\.220\.380\.230\.26SCAL0\.180\.350\.230\.260\.260\.230\.23\+ ACE0\.210\.290\.210\.270\.220\.220\.38FGC0\.180\.230\.250\.230\.250\.210\.18\+ ACE0\.240\.180\.310\.210\.270\.380\.22UGC0\.270\.260\.240\.240\.230\.220\.20\+ ACE0\.310\.240\.210\.260\.220\.210\.23SGBGC0\.180\.200\.250\.190\.230\.200\.23\+ ACE0\.220\.260\.180\.230\.250\.230\.29LINKX\-0\.330\.190\.260\.290\.320\.210\.19SCAL0\.320\.210\.170\.330\.290\.200\.23\+ ACE0\.290\.190\.270\.320\.210\.290\.27FGC0\.240\.210\.250\.200\.250\.230\.31\+ ACE0\.320\.240\.320\.260\.320\.200\.23UGC0\.190\.260\.310\.170\.380\.170\.38\+ ACE0\.250\.310\.170\.230\.230\.230\.25SGBGC0\.170\.220\.260\.200\.270\.200\.19\+ ACE0\.330\.170\.250\.320\.230\.330\.23GloGNN\-0\.320\.230\.270\.170\.230\.330\.26SCAL0\.330\.330\.190\.230\.320\.290\.33\+ ACE0\.240\.260\.320\.200\.260\.270\.38FGC0\.190\.220\.270\.320\.310\.330\.20\+ ACE0\.270\.320\.330\.250\.270\.310\.26UGC0\.190\.260\.170\.260\.200\.290\.29\+ ACE0\.270\.170\.380\.190\.270\.310\.33SGBGC0\.220\.220\.170\.240\.200\.190\.26\+ ACE0\.240\.290\.290\.190\.260\.290\.27 Table 8:Results of integrating ACE into GPRGNN, SGFormer, and Polynormer\. Improvements on heterophilic datasets appear inbold\.BackboneMethodHeterophilic GraphsHomophilic GraphsGeniusGamersPokecSnaparXiv\-yearogbn\-arXivogbn\-productsGPRGNN\-90\.0561\.8978\.8340\.1945\.0771\.7878\.29SCAL66\.1943\.4860\.9228\.2226\.5363\.2865\.92\+ ACE78\.57 \(\+12\.38\)51\.74 \(\+8\.26\)70\.25 \(\+9\.33\)32\.42 \(\+4\.20\)35\.59 \(\+9\.06\)64\.76 \(\+1\.48\)68\.25 \(\+2\.33\)FGC69\.2845\.9257\.1426\.4428\.6062\.1963\.28\+ ACE79\.02 \(\+9\.74\)52\.38 \(\+6\.46\)64\.87 \(\+7\.73\)31\.22 \(\+4\.78\)36\.73 \(\+8\.13\)64\.29 \(\+2\.10\)65\.83 \(\+2\.55\)UGC68\.0641\.2061\.3325\.3829\.1261\.4465\.26\+ ACE78\.17 \(\+10\.11\)51\.06 \(\+9\.86\)69\.37 \(\+8\.04\)31\.46 \(\+6\.08\)34\.59 \(\+5\.47\)63\.19 \(\+1\.75\)67\.84 \(\+2\.58\)SGBGC69\.9344\.2662\.4126\.9331\.2663\.1463\.02\+ ACE77\.39 \(\+7\.46\)50\.61 \(\+6\.35\)67\.38 \(\+4\.97\)30\.24 \(\+3\.31\)38\.42 \(\+7\.16\)65\.02 \(\+1\.88\)68\.47 \(\+5\.45\)SGFormer\-85\.0165\.9380\.8463\.8451\.2372\.6381\.54SCAL63\.9151\.7463\.4742\.7330\.8161\.3871\.74\+ ACE75\.81 \(\+11\.90\)57\.38 \(\+5\.64\)71\.88 \(\+8\.41\)53\.62 \(\+10\.89\)43\.76 \(\+12\.95\)63\.02 \(\+1\.64\)73\.84 \(\+2\.10\)FGC67\.2652\.0961\.3740\.2932\.4863\.8173\.62\+ ACE76\.31 \(\+9\.05\)56\.38 \(\+4\.29\)70\.33 \(\+8\.96\)50\.13 \(\+9\.84\)43\.02 \(\+10\.54\)65\.11 \(\+1\.30\)74\.84 \(\+1\.22\)UGC65\.3849\.0764\.3544\.1628\.6060\.7770\.04\+ ACE75\.48 \(\+10\.10\)58\.34 \(\+9\.27\)71\.48 \(\+7\.13\)49\.78 \(\+5\.62\)38\.26 \(\+9\.66\)63\.29 \(\+2\.52\)73\.16 \(\+3\.12\)SGBGC68\.7352\.6660\.7346\.3834\.0161\.6268\.30\+ ACE76\.12 \(\+7\.39\)57\.02 \(\+4\.36\)69\.66 \(\+8\.93\)52\.09 \(\+5\.71\)39\.74 \(\+5\.73\)64\.21 \(\+2\.59\)72\.73 \(\+4\.43\)Polynormer\-85\.6464\.7286\.0661\.9253\.4873\.4083\.82SCAL64\.9348\.4264\.3840\.6332\.7463\.9371\.38\+ ACE75\.73 \(\+10\.80\)55\.62 \(\+7\.20\)73\.16 \(\+8\.78\)47\.63 \(\+7\.00\)40\.61 \(\+7\.87\)65\.28 \(\+1\.35\)73\.47 \(\+2\.09\)FGC62\.0344\.2266\.6338\.6635\.2664\.2272\.48\+ ACE74\.79 \(\+12\.76\)57\.48 \(\+13\.26\)77\.81 \(\+11\.18\)50\.13 \(\+11\.47\)46\.72 \(\+11\.46\)65\.79 \(\+1\.57\)74\.61 \(\+2\.13\)UGC66\.0245\.4968\.4943\.8430\.3461\.2871\.79\+ ACE74\.20 \(\+8\.18\)57\.02 \(\+11\.53\)76\.24 \(\+7\.75\)51\.26 \(\+7\.42\)43\.28 \(\+12\.94\)64\.10 \(\+2\.82\)73\.45 \(\+1\.66\)SGBGC67\.9841\.3762\.1345\.0132\.6363\.3370\.16\+ ACE77\.83 \(\+9\.85\)53\.81 \(\+12\.44\)74\.86 \(\+12\.73\)49\.38 \(\+4\.37\)38\.97 \(\+6\.34\)65\.03 \(\+1\.70\)72\.88 \(\+2\.72\) Table 9:Additional results fortask\-optimizedcoarsening pipelines—GCond\[Jin et al\.,[2022](https://arxiv.org/html/2607.21885#bib.bib24)\]and ConvMatch\[Dickens et al\.,[2024](https://arxiv.org/html/2607.21885#bib.bib12)\]—evaluated using GCN \(homophily\-oriented\) and GPRGNN \(heterophily\-oriented\) backbones across diverse benchmarks\.BackboneMethodHeterophilic GraphsHomophilic GraphsGeniusGamersPokecSnaparXiv\-yearogbn\-arXivogbn\-productsGCN\-87\.4262\.1875\.4545\.6546\.0271\.7475\.64GCond70\.2251\.2753\.7729\.7830\.2266\.3871\.19\+ ACE78\.33 \(\+8\.11\)56\.26 \(\+4\.99\)58\.49 \(\+4\.72\)36\.37 \(\+6\.59\)37\.83 \(\+7\.61\)67\.15 \(\+0\.77\)72\.01 \(\+0\.82\)ConvMatch68\.1343\.7450\.6624\.3725\.9466\.1270\.93\+ ACE76\.44 \(\+8\.31\)52\.07 \(\+8\.33\)55\.39 \(\+4\.73\)32\.29 \(\+7\.92\)30\.85 \(\+4\.91\)67\.95 \(\+1\.83\)72\.83 \(\+1\.90\)GPRGNN\-90\.0561\.8978\.8340\.1945\.0771\.7878\.29GCond71\.3949\.4758\.6530\.4731\.3865\.9370\.27\+ ACE79\.63 \(\+8\.24\)55\.65 \(\+6\.18\)71\.33 \(\+12\.68\)34\.28 \(\+3\.81\)37\.19 \(\+5\.81\)66\.49 \(\+0\.56\)72\.01 \(\+1\.74\)ConvMatch66\.3144\.6751\.4022\.3324\.6066\.1967\.28\+ ACE77\.24 \(\+10\.93\)50\.42 \(\+5\.75\)66\.67 \(\+15\.27\)30\.05 \(\+7\.72\)31\.43 \(\+6\.83\)67\.43 \(\+1\.24\)68\.44 \(\+1\.19\) Table 10:Additional results under an extreme 1% coarsening ratio\.BackboneMethodHeterophilic GraphsHomophilic GraphsGeniusGamersPokecSnaparXiv\-yearogbn\-arXivogbn\-productsGCN\-87\.4262\.1875\.4545\.6546\.0271\.7475\.64SCAL55\.4239\.2146\.2620\.4122\.4360\.3964\.69\+ ACE73\.76 \(\+18\.34\)52\.43 \(\+13\.22\)53\.80 \(\+7\.54\)28\.73 \(\+8\.32\)29\.38 \(\+6\.95\)64\.47 \(\+4\.08\)68\.73 \(\+4\.04\)FGC63\.8436\.0845\.3721\.2321\.4062\.8666\.14\+ ACE72\.74 \(\+8\.90\)50\.18 \(\+14\.10\)54\.55 \(\+9\.18\)30\.25 \(\+9\.02\)29\.01 \(\+7\.61\)63\.71 \(\+0\.85\)70\.22 \(\+4\.08\)SGBGC64\.1740\.2548\.6623\.2422\.4262\.5664\.81\+ ACE71\.02 \(\+6\.85\)52\.39 \(\+12\.14\)53\.29 \(\+4\.63\)28\.63 \(\+5\.39\)30\.22 \(\+7\.80\)64\.66 \(\+2\.10\)68\.37 \(\+3\.56\)GPRGNN\-90\.0561\.8978\.8340\.1945\.0771\.7878\.29SCAL59\.3937\.8250\.6826\.2822\.1561\.4763\.06\+ ACE73\.54 \(\+14\.15\)47\.46 \(\+9\.64\)61\.62 \(\+10\.94\)30\.33 \(\+4\.05\)30\.42 \(\+8\.27\)63\.22 \(\+1\.75\)65\.81 \(\+2\.75\)FGC57\.4736\.8151\.4223\.3726\.5561\.0560\.39\+ ACE71\.23 \(\+13\.76\)45\.23 \(\+8\.42\)59\.83 \(\+8\.41\)27\.83 \(\+4\.46\)31\.17 \(\+4\.62\)63\.14 \(\+2\.09\)63\.77 \(\+3\.38\)SGBGC61\.6338\.4154\.4823\.4125\.0761\.3960\.97\+ ACE70\.78 \(\+9\.15\)47\.81 \(\+9\.40\)64\.13 \(\+9\.65\)28\.35 \(\+4\.94\)30\.93 \(\+5\.86\)63\.77 \(\+2\.38\)65\.48 \(\+4\.51\) Table 11:Comparison with state\-of\-the\-art scalable GNN training methods based on graph data reduction\. Results on aGPRGNNbackbone with a 10% reduction ratio are reported in terms of test accuracy and total training time\.CategoryMethodPokecSnapGamersOgbn\-productACCTime \(min\)ACCTime \(min\)ACCTime \(min\)ACCTime \(min\)CoarseningFGC57\.1422\.4826\.4430\.8445\.9210\.2863\.2832\.17UGC61\.3321\.5525\.3828\.2641\.2010\.5665\.2630\.46Data\-AdaptiveGECC64\.1932\.1630\.8136\.4349\.6216\.8166\.7743\.49Subgraph\-SamplingAGS62\.7719\.9228\.3428\.3848\.139\.4466\.1129\.54OursFGC\+ACE64\.8722\.9631\.2231\.3752\.3810\.8665\.8333\.09UGC\+ACE69\.3721\.8831\.4629\.8451\.0611\.1667\.8431\.22 Table 12:Detailed ablation study of individual components in ACE\. Results are reported on aGCNbackbone with a 10% reduction ratio, including test accuracy for the full method \(ACE base\) and relative performance drop for each variant\.MethodVariantGeniusGamersPokecSnapOgbn\-ProductAverage DropFGCACE \(base\)77\.3252\.5261\.6732\.7372\.47\-ACE \(fixed weighting\)\-0\.35\-0\.59\-0\.41\-0\.62\-0\.06\-0\.41ACE \(no anisotropic reg\)\-0\.70\-1\.83\-1\.90\-1\.30\-0\.18\-1\.18ACE \(fixed projector\)\-1\.34\-2\.60\-3\.51\-1\.66\-0\.36\-1\.90naive auxiliary loss\-1\.65\-3\.26\-4\.45\-2\.07\-0\.41\-2\.37UGCACE \(base\)75\.2853\.8359\.3730\.8270\.19\-ACE \(fixed weighting\)\-0\.26\-0\.71\-0\.63\-0\.50\-0\.11\-0\.44ACE \(no anisotropic reg\)\-0\.81\-2\.06\-1\.75\-1\.22\-0\.19\-1\.20ACE \(fixed projector\)\-1\.72\-3\.61\-3\.83\-1\.93\-0\.35\-2\.29naive auxiliary loss\-2\.44\-4\.23\-4\.16\-2\.65\-0\.56\-2\.70Table 13:Detailed ablation study of individual components in ACE\. Results are reported on aGPRGNNbackbone with a 10% reduction ratio, including test accuracy for the full method \(ACE base\) and relative performance drop for each variant\.MethodVariantGeniusGamersPokecSnapOgbn\-ProductAverage DropFGCACE \(base\)79\.0252\.3864\.8731\.2265\.83\-ACE \(fixed weighting\)\-0\.27\-0\.41\-0\.46\-0\.44\-0\.10\-0\.34ACE \(no anisotropic reg\)\-0\.79\-1\.23\-1\.64\-1\.14\-0\.15\-0\.99ACE \(fixed projector\)\-1\.65\-2\.84\-3\.47\-1\.92\-0\.28\-2\.03naive auxiliary loss\-2\.12\-3\.33\-3\.93\-2\.47\-0\.43\-2\.46UGCACE \(base\)78\.1751\.0669\.3731\.4667\.84\-ACE \(fixed weighting\)\-0\.38\-0\.56\-0\.42\-0\.53\-0\.08\-0\.39ACE \(no anisotropic reg\)\-0\.75\-1\.78\-1\.93\-1\.42\-0\.16\-1\.21ACE \(fixed projector\)\-2\.14\-3\.59\-3\.45\-2\.46\-0\.30\-2\.39naive auxiliary loss\-2\.81\-4\.02\-4\.09\-3\.16\-0\.45\-2\.91\(a\) \(b\) \(c\) \(d\) \(e\) \(f\) \(g\) \(h\) Figure 5:Effect ofβ\\betaacross coarsening pipelines, GNN backbones, and datasets\.\(a\) \(b\) \(c\) \(d\) Figure 6:Preprocessing time of each coarsening training pipelines and those with our ACE across diverse benchmarks\.\(a\) \(b\) \(c\) Figure 7:Per\-epoch training time of SCAL, FGC, SGBGC, and their ACE\-improved versions across diverse backbone GNNs\.\(a\) \(b\) \(c\) Figure 8:Training GPU memory allocation of SCAL, FGC, SGBGC, and their ACE\-improved versions across diverse backbone GNNs\.\(a\) \(b\) Figure 9:Noise robustness evaluation on the Pokec dataset\. Experiments are conducted using GCN and GPRGNN backbones with a 10% graph reduction ratio\. We report performance under feature perturbations, where Gaussian noise is added to randomly sampled node features in the original graph, with sampling ratios of \{0%, 1%, 5%, 10%, 25%\}\.
Similar Articles
Modeling Heterophily in Multiplex Graphs: An Adaptive Approach for Node Classification
This paper introduces HAAM, a novel method for node classification in multiplex graphs that adapts to both homophilic and heterophilic interactions across dimensions. It uses dimension-specific compatibility matrices and a product of trainable low-pass and high-pass filters approximated via Chebyshev polynomials to capture smooth and abrupt signal changes.
Hierarchical Multi-Scale Graph Neural Networks: Scalable Heterophilous Learning with Oversmoothing and Oversquashing Mitigation
This paper introduces HMH, a hierarchical multi-scale Graph Neural Network framework designed to address oversmoothing and oversquashing in heterophilous graphs. It utilizes spectral filters with Haar bases to achieve scalable learning and improved performance on node and graph classification tasks.
Heterogeneous Graph Condensation via Role-Aware Clustering
This paper proposes HGC-RC, a role-aware heterogeneous graph condensation framework that uses lightweight propagation and a hybrid clustering strategy to produce compact heterogeneous graphs, enabling efficient HGNN training on large-scale graphs without sacrificing performance.
Beyond the Golden Teacher: Enhancing Graph Learning through LLM-GNN Co-teaching
This paper proposes LLM-GNN Co-Teaching, a bidirectional framework for few-shot graph learning on text-attributed graphs. The LLM and GNN exchange confident pseudo-labels and use round-based preference optimization (RPL-PO) to mutually improve, outperforming prior methods on benchmarks.
Generated Contents Enrichment
This paper proposes a joint adversarial framework that uses graph convolutional networks to enrich sparse scene graphs before generating semantically richer visual content. The approach makes scene enrichment explicit at the representation level, producing visually plausible and structurally coherent images.