Pith. sign in

REVIEW 4 major objections 5 minor 295 references

Coarsening-based GNN training degrades sharply under heterophily; ACE, an auxiliary-loss wrapper with a learned projector, recovers up to ~15 accuracy points at ~5% overhead.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

ACE adds a heterophily-aware auxiliary loss to coarsening-based GNN training, recovering discarded node-level information and improving accuracy on heterophilic graphs by up to ~15 points.

T0 review reviewed 2026-08-01 challenge →

load-bearing objection Solid empirical study of heterophily in coarsening-based GNN training, but the auxiliary loss's label masking is unspecified and could invalidate the headline gains; worth reviewing, not yet citable. the 4 major comments →

arxiv 2607.21885 v1 pith:TOESOWFD submitted 2026-07-24 cs.LG cs.NAeess.SPmath.NA

Remedying Coarsening-Based GNN Training under Heterophily via Adaptive Complementary Enhancement

Guoming Li , Jian Yang , Xukun Wang , Zixiao Wang , Shangsong Liang , Yifan Chen This is my paper
classification cs.LG cs.NAeess.SPmath.NA
keywords graph coarseningheterophilygraph neural networksauxiliary losslearned projectormutual informationanisotropic diffusionhomoscedastic uncertainty
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper argues that training a GNN on a coarsened graph — a common trick for scaling to massive graphs — fails on heterophilic graphs, where connected nodes tend to have different labels, because coarsening discards exactly the fine-grained, label-relevant structure inside each supernode. Existing coarsening pipelines lose roughly four times more accuracy on heterophilic benchmarks than on homophilic ones, and even heterophily-specialized GNN backbones cannot escape the drop. The authors propose ACE, which learns a projector that reconstructs original node features from supernode features, regularized by an anisotropic diffusion term that respects local heterophily. Training then combines the usual coarsened-graph loss with an auxiliary full-graph loss, automatically weighted by homoscedastic uncertainty. Across four coarsening pipelines and six GNN backbones, ACE consistently recovers a large fraction of the gap — up to about 15 accuracy points on heterophilic graphs — while adding only a few percent to runtime and memory.

Core claim

The central claim is that performance degradation in coarsening-based GNN training under heterophily is not a model artifact but a consequence of information loss in the coarsening step itself. Treating the discarded intra-supernode structure G\G' as a source of label information, the paper proves a mutual-information bound (Proposition 2.2): the similarity between full-graph-trained and coarsened-graph-trained models is capped by I(f(A,X;Θ*);Y) − I(g(G\G');Y | f(A,X;Θ**)), so the larger the conditional mutual information between discarded structure and labels, the larger the gap. ACE attacks this gap directly: it learns a heterophily-aware projector P(ϕ) that maps supernode centroids back t

What carries the argument

The load-bearing object is the learned heterophily-aware projector P(ϕ), defined by a softmax over per-node affinities that combine a structural affinity S = A C⁻¹ P and a feature affinity F (Gaussian kernel to supernode centroids), with the logits produced by a small MLP. It is trained by minimizing J_ASR: an anisotropic smoothness term whose edge weights exp(−||Xi−Xj||²) suppress smoothing across dissimilar neighbors, plus a feature reconstruction cost. The projector bridges the coarsened graph back to the full graph: lifting coarsened logits through P(ϕ) defines an auxiliary cross-entropy loss against full-graph labels, and learnable homoscedastic uncertainty parameters σ₁, σ₂ automatical

Load-bearing premise

The load-bearing assumption is that the full-graph-trained and coarsened-graph-trained model outputs are conditionally independent given the true labels, which is what makes the mutual-information bound in Proposition 2.2 go through; the empirical ACE recipe does not depend on this assumption.

What would settle it

Estimate the quantities in Proposition 2.2 on a real heterophilic dataset (e.g., Genius): I(f(A,X;Θ*); f(A,X;Θ**)), I(f(A,X;Θ*);Y), and I(g(G\G');Y | f(A,X;Θ**)) using trained models. If the inequality fails, or if the conditional mutual information Ω is not larger for heterophilic than for comparable homophilic graphs, the paper's information-theoretic explanation of the coarsening gap would be refuted, even if ACE still improves accuracy empirically.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • Any existing coarsening-based GNN pipeline can be upgraded by adding ACE's auxiliary loss with the learned projector, without retraining or altering the coarsening algorithm.
  • Coarsening-based training becomes practical on large heterophilic graphs, where the gap to full-graph training shrinks substantially — for instance, GCN on Genius improves from 67.47 to 77.63 against a full-graph score of 87.42.
  • The same recipe extends to other graph-reduction methods such as graph condensation and to extreme 1% coarsening ratios, where the relative gains are even larger.
  • Inference cost stays identical to the base coarsening pipeline because the auxiliary branch is discarded after training; only training time and memory rise by roughly 4–7%.
  • ACE-enhanced conventional coarsening methods become competitive with state-of-the-art scalable training approaches such as sampling and condensation, while preserving the simpler model-agnostic coarsening paradigm.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • A direct test of the proposed mechanism would estimate the three mutual-information terms in Proposition 2.2 on real heterophilic and homophilic graphs; if the conditional mutual information Ω is not larger under heterophily, or if the inequality fails, the theory would be refuted even though ACE's empirical gains could still stand on the auxiliary-loss supervision.
  • Because the projector is learned purely from features and structure, ACE could plausibly transfer to other settings where a reduced graph substitutes for the full one, such as graph distillation, continual graph learning, or scalable inference on evolving graphs.
  • The homoscedastic weighting likely acts as a form of curriculum: early training may emphasize the cheap coarsened loss and later shift to the fine-grained auxiliary loss. Inspecting the learned σ₁/σ₂ trajectories would reveal whether the benefit comes from a stable early phase or from late fine-grained correction.
  • The paper's own limitation section concedes that ACE recovers discarded information implicitly rather than through explicit intra-supernode structure, which it says caps the achievable gain; adding a lightweight explicit decoder of intra-supernode edges is a natural next step toward closing the remaining gap to full-graph training.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper studies the performance degradation of coarsening-based GNN training on heterophilic graphs. It first documents empirically that existing coarsening pipelines (SCAL, FGC, UGC, SGBGC) lose substantially more accuracy on heterophilic than homophilic graphs. It then proposes ACE, a plug-and-play auxiliary-loss framework: a learnable projector P(ϕ) is optimized with an anisotropic structural regularization term, and the resulting projector is used to lift coarsened-graph predictions to the original graph for an auxiliary cross-entropy loss against the full label matrix; the primary and auxiliary losses are combined via homoscedastic uncertainty weighting. Experiments on 5 heterophilic and 2 homophilic datasets with up to 6 backbones report consistent gains, up to ~15 points, with modest computational overhead. The paper also offers two theoretical propositions (Prop. 2.2 on a mutual-information gap, Prop. 3.1 on the projector's spectral behavior).

Significance. If the empirical results are valid, ACE is a practical and broadly applicable enhancement for coarsening-based training: it is model-agnostic, works across four coarsening pipelines, and the experiments are extensive (10 runs with standard deviations, multiple backbones, ablation studies, noise robustness, and overhead measurements). The paper also releases code and includes careful efficiency analyses. However, the two theoretical propositions are not rigorously established; they are best viewed as post-hoc intuition rather than proofs. The central unresolved issue is whether the auxiliary loss uses only training labels: the manuscript defines Y as the full n×c label matrix and never specifies a mask, which could invalidate the reported test accuracy gains.

major comments (4)
  1. [Sec. 2.1, Eq. (5), Eq. (11)] The label matrix Y is defined as the full n×c one-hot matrix, and both auxiliary losses (Eq. (5) and Eq. (11)) are written against Y with no train/validation/test mask. In transductive node classification, using test labels in the loss would inflate the reported test accuracies (Tables 3, 8–11) and make the comparison to coarsening baselines unfair. Please state explicitly how the label mask is applied in the auxiliary loss and in Y' = C^{-1} P Y. If test labels are used, the experiments must be rerun with a proper training mask; if a mask is used in the code but omitted from the text, it must be described precisely.
  2. [Eq. (5), Eq. (11), Sec. 2.1] The lifting operator is written as P^T C (or P(ϕ*)^T C). Given the coarsened labels are defined as Y' = C^{-1} P Y, the natural inverse mapping from coarse predictions to fine nodes is P^T C^{-1}, or simply P^T if f outputs a probability vector. The factor C appears to be the wrong inverse. This makes the definition of the auxiliary loss mathematically inconsistent with the stated coarsening convention. Please correct the equations or clarify the intended operator; if the implementation actually uses C^{-1}, that should be stated explicitly.
  3. [Appendix A, Prop. 2.2] The proof is not valid. Lemma A.2 assumes conditional independence A⊥B|Y for the outputs of two models trained on the same labels, which is not justified and generally false for two trained GNNs. Moreover, Eq. (20) applies the data-processing inequality to the chain Y→f(A,X;Θ*)→(f(A,X;Θ**),g(G\G')), but this Markov chain does not hold: f(A,X;Θ**) depends on Y through the coarsened labels Y' and is not a function of f(A,X;Θ*). Consequently, the inequality in Eq. (4) is not established. The theoretical explanation should either be rigorously proven or explicitly presented as a heuristic.
  4. [Appendix B, Prop. 3.1] The proof analyzes a local objective Li((P(ϕ)µ)_i) and differentiates with respect to the lifted signal (P(ϕ)µ)_i while treating neighboring lifted signals as constants. The resulting update rule (Eq. (29)) is not the fixed-point condition for the minimizer, and the optimization is over ϕ, not directly over the lifted signal. Thus the claimed high-frequency/low-frequency interpolation behavior of P(ϕ*) is not proven. Please revise the proof or weaken the proposition to a stated intuition.
minor comments (5)
  1. [Eq. (11)] The homoscedastic uncertainty weighting uses 1/(2σ^2) for both losses, which is the regression form from Kendall et al. For classification, the standard form is (1/σ^2) L + log σ. Please verify and correct the formula.
  2. [Sec. 3.2.1] Typo: 'features anisotropic structural regularization' should likely be 'features an anisotropic structural regularization' or 'incorporates anisotropic structural regularization'.
  3. [Throughout] Inconsistent naming: 'GLOGNN' vs 'GloGNN', 'Ogbn-product' vs 'Ogbn-products', and 'arXiv' vs 'arXiv-year' in a few places. Please standardize.
  4. [Appendix D.2] The description states UGC 'explicitly accounts for the heterophily present in such graphs,' which seems to contradict the introduction's claim that prior coarsening work has been developed almost exclusively for homophilic graphs. Please reconcile.
  5. [Sec. 2.2, Table 1] The text says the degradation is 'often nearly four times larger' on heterophilic graphs. This ratio is not computed or shown; please provide the exact computation or substantiate the claim.

Circularity Check

2 steps flagged

No significant circularity in the empirical method; the theory sections contain a self-definitional proposition and a proof that assumes its conclusion.

specific steps
  1. other [Appendix A, proof of Proposition 2.2 (Lemma A.2 and Eq. 20)]
    "Assume that A and B are conditionally independent given Y, i.e. A⊥B|Y. Then I(A;B)≤min{I(A;Y), I(B;Y)}. ... Notice that f(; Θ∗), f(; Θ∗∗), and g are all deterministic functions. Hence, by letting U=Y, V=f(A, X; Θ∗), W=(f(A, X; Θ∗∗), g(G \ G′)), we can derive..."

    The proposition's bound is obtained by first assuming the two model outputs are conditionally independent given Y, which already enforces that their shared information flows only through the label. The subsequent DPI step postulates the Markov chain Y→f(A,X;Θ*)→(f(A,X;Θ**),g(G\G')), which is a stronger version of the target claim: it asserts the full-graph output screens off all extra label information carried by the coarsened model and the discarded graph. Thus the 'explanation' of the coarsening gap rests on the informational separation it is supposed to prove, rather than being derived from the coarsening process.

  2. self definitional [Section 3.2.1, Eq. (10) and Proposition 3.1 / Appendix B]
    "JASR(ϕ) = Σ_{i,j∈E} ωij · ∥(P(ϕ)µ)i −(P(ϕ)µ)j∥2 + β·∥X−P(ϕ)µ∥2F, where ωij := exp(−∥Xi −Xj∥2). ... Heterophilic Regime: In regions where ∥Xi −Xj∥→∞, P(ϕ∗) approaches the solution of identity reconstruction, prioritizing high-frequency signal fidelity over structural smoothness."

    The proposition's two regimes follow immediately from the definition of ωij: when ∥Xi-Xj∥ is large, ωij→0 and only the reconstruction term remains; when it is small, ωij→1 and the smoothness term dominates. The 'heterophily-aware' interpolation is therefore installed into the objective by construction, and the proposition restates that definitional behavior rather than deriving an independent property of the learned projector.

full rationale

The empirical core of ACE is not circular. The reported gains are measured on external heterophilic and homophilic benchmarks against four coarsening baselines and multiple backbones; the refined projector is optimized unsupervised via Eq. (10) using only graph structure and features, and the auxiliary loss is a standard supervised objective. There is no load-bearing self-citation chain: the reference to the corresponding author's earlier spectral-coarsening work is contextual, and the anisotropic-diffusion inspiration is attributed to external prior work. The only circular-adjacent parts are theoretical. Proposition 2.2's proof assumes conditional independence of model outputs given Y and a DPI Markov chain that effectively contains the conclusion, so the mutual-information explanation is not independently derived. Proposition 3.1 is a self-definitional unpacking of JASR: the heterophily-aware regimes are built into ωij by definition. Separately, Eqs. (5) and (11) write the auxiliary loss against the full n×c label matrix Y without explicitly stating a train/validation/test mask; if Y included test labels, the accuracy tables would be fitted values rather than predictions. That is an unguarded definition in the manuscript, not evidence that the authors used test labels, and it does not undermine the self-contained nature of the empirical comparison as normally instantiated. Overall, the central empirical contribution is externally benchmarked and independent of the theory, so the circularity score is low.

Axiom & Free-Parameter Ledger

5 free parameters · 5 axioms · 0 invented entities

The load-bearing logical assumptions are mostly empirical premises (coarsening loses information; anisotropic diffusion helps) and two unjustified information-theoretic steps in the proof of Prop 2.2. The method's free parameters are hyperparameters (β, T, MLP width), not fitted to test data.

free parameters (5)
  • β (anisotropic regularization trade-off) = 1 (default; robust across 0.01–100)
    Balances reconstruction vs anisotropic smoothness in Eq (10); tuned from {0.1,1,10}.
  • T (projector optimization epochs) = not reported
    Number of epochs for learning P(ϕ); complexity is O(T(n d + |E| d)) but T is never given.
  • λ (toy auxiliary loss weight) = not stated
    Trade-off in Eq (5), manually chosen; replaced by uncertainty weighting in final ACE.
  • MLP hidden dim for f_ϕ = 500
    Architecture choice for the projector MLP, fixed across experiments.
  • σ1, σ2 (uncertainty weights) = learned
    Learned via homoscedastic uncertainty weighting in Eq (11); not reported post-training.
axioms (5)
  • standard math Cross-entropy minimization with softmax is equivalent to mutual information maximization (Lemma A.1, from Qin et al. 2020)
    Cited lemma used to convert loss minimization to MI maximization in the proof of Prop 2.2.
  • ad hoc to paper Outputs of two different models trained on the same labels are conditionally independent given the label (Lemma A.2)
    Unproven and generally false: model outputs share feature/architecture correlations beyond the label. This assumption is load-bearing for the core bound.
  • ad hoc to paper Data processing inequality can be applied as I(Y; f_full) ≥ I(Y; (f_coarse, g(G\G')))
    Eq (20) assumes Y→f_full→(f_coarse,g) is a Markov chain, which is not established; f_coarse is not a function of f_full.
  • domain assumption Anisotropic diffusion captures heterophily better than isotropic diffusion
    Motivates the anisotropic structural regularization in Eq (10); inherited from prior literature [Fu et al. 2023, Perona & Malik].
  • domain assumption Coarsening discards label-relevant structure, especially under heterophily
    Central premise supported only empirically via the toy experiment; not formally proven.

reviewed 2026-08-01 · how reviews work

0 comments
Cite this review

Pith. "Pith review of Remedying Coarsening-Based GNN Training under Heterophily via Adaptive Complementary Enhancement." pith.science (2026). https://pith.science/paper/TOESOWFD

@misc{pith2026260721885,
  author       = {Pith},
  title        = {Pith review of: Remedying Coarsening-Based GNN Training under Heterophily via Adaptive Complementary Enhancement},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TOESOWFD}},
  note         = {Machine review of arXiv:2607.21885}
}
Share X Bluesky LinkedIn Reddit HN
read the original 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.

Figures

Figures reproduced from arXiv: 2607.21885 by Guoming Li, Jian Yang, Shangsong Liang, Xukun Wang, Yifan Chen, Zixiao Wang.

Figure 1
Figure 1. Figure 1: Illustration for graph coarsening: G ′ encodes inter￾supernode relations; G \ G′ holds intra-supernode informa￾tion discarded during coarsening. mutual information between their outputs satisfies I(f(A, X; Θ∗ ); f(A, X; Θ∗∗)) ≤ I(f(A, X; Θ∗ ); Y ) − Ω , (4) where Ω = I(g(G \ G′ ); Y |f(A, X; Θ∗∗)), and g : G \ G ′ 7→ Y is arbitrary neural network that maps G \ G′ to the node label space Y and maximizes the… view at source ↗
Figure 2
Figure 2. Figure 2: Effect of β across coarsening pipelines, GNN backbones, and datasets. More results can be found in [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Comparison of preprocessing time for SCAL, SG [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figure 5
Figure 5. Figure 5: Effect of β across coarsening pipelines, GNN backbones, and datasets [PITH_FULL_IMAGE:figures/full_fig_p022_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Preprocessing time of each coarsening training pipelines and those with our ACE across diverse benchmarks. [PITH_FULL_IMAGE:figures/full_fig_p023_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Per-epoch training time of SCAL, FGC, SGBGC, and their ACE-improved versions across diverse backbone [PITH_FULL_IMAGE:figures/full_fig_p023_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Training GPU memory allocation of SCAL, FGC, SGBGC, and their ACE-improved versions across diverse [PITH_FULL_IMAGE:figures/full_fig_p024_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Noise robustness evaluation on the Pokec dataset. Experiments are conducted using GCN and GPRGNN backbones [PITH_FULL_IMAGE:figures/full_fig_p024_9.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

295 extracted references · 9 canonical work pages

  1. [1]

    A note on over-smoothing for graph neural networks, 2020

    Chen Cai and Yusu Wang. A note on over-smoothing for graph neural networks, 2020. URL https://arxiv.org/abs/2006.13318

    Pith/arXiv arXiv 2020

  2. [2]

    Grand: Graph neural diffusion

    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://pr...

    2021

  3. [3]

    Graph coarsening: from scientific computing to machine learning

    Jie Chen, Yousef Saad, and Zechen Zhang. Graph coarsening: from scientific computing to machine learning. SeMA Journal, 79 0 (1): 0 187--223, 2022 a

    2022

  4. [4]

    Optimization-induced graph implicit nonlinear diffusion

    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, pa...

    2022

  5. [5]

    A gromov- W asserstein geometric view of spectrum-preserving graph coarsening

    Yifan Chen, Rentian Yao, Yun Yang, and Jie Chen. A gromov- W asserstein 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 Learni...

    2023

  6. [6]

    Adaptive universal generalized pagerank graph neural network

    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

    2021

  7. [7]

    Spectral Graph Theory , volume 92

    Fan Chung. Spectral Graph Theory , volume 92. CBMS Regional Conference Series in Mathematics, 1997. ISBN 978-0-8218-0315-8. doi:/10.1090/cbms/092

    doi:10.1090/cbms/092 1997

  8. [8]

    Elements of information theory

    Thomas M Cover. Elements of information theory. John Wiley & Sons, 1999

    1999

  9. [9]

    Re-think and re-design graph neural networks in spaces of continuous graph diffusion functionals

    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...

    2023

  10. [10]

    Halappanavar, Edoardo Serra, and Alex Pothen

    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. doi:1...

    arXiv 2024

  11. [11]

    Polynormer: Polynomial-expressive graph transformer in linear time

    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

    2024

  12. [12]

    Graph coarsening via convolution matching for scalable graph neural network training

    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 http...

    arXiv 2024

  13. [13]

    Ahmed A. A. Elhag, Gabriele Corso, Hannes St \"a 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

    2022

  14. [14]

    Pde-gcn: Novel architectures for graph neural networks motivated by partial differential equations

    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

    2021

  15. [15]

    Faster graph embeddings via coarsening

    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...

    2020

  16. [16]

    Implicit graph neural diffusion based on constrained dirichlet energy minimization

    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

    2023

  17. [17]

    Bronstein

    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

    2023

  18. [18]

    Learning from graphs with heterophily: Progress and future, 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

    Pith/arXiv arXiv 2024

  19. [19]

    Scalable graph condensation with evolving capabilities

    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. doi:10.1145/3770854.3780217. URL ht...

    arXiv 2026

  20. [20]

    From continuous dynamics to graph neural networks: Neural diffusion and beyond, 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

    Pith/arXiv arXiv 2023

  21. [21]

    Aditya Prakash, and Wei Jin

    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 Ar...

    doi:10.24963/ijcai.2024/891 2024

  22. [22]

    Open graph benchmark: Datasets for machine learning on graphs

    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

    2020

  23. [23]

    Scaling up graph neural networks via graph coarsening

    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

    2021

  24. [24]

    Graph condensation for graph neural networks

    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

    2022

  25. [25]

    Graph coarsening with preserved spectral properties

    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

    2020

  26. [26]

    Graph coarsening with message-passing guarantees, 2024

    Antonin Joly and Nicolas Keriven. Graph coarsening with message-passing guarantees, 2024. URL https://arxiv.org/abs/2405.18127

    Pith/arXiv arXiv 2024

  27. [27]

    Ugc: Universal graph coarsening

    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

    2024

  28. [28]

    Multi-task learning using uncertainty to weigh losses for scene geometry and semantics

    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

    2018

  29. [29]

    Kingma and Jimmy Ba

    Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization, 2014. URL https://arxiv.org/abs/1412.6980

    Pith/arXiv arXiv 2014

  30. [30]

    Kipf and Max Welling

    Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks, 2017. URL https://openreview.net/forum?id=SJU4ayYgl

    2017

  31. [31]

    A unified framework for optimization-based graph coarsening

    Manoj Kumar, Anurag Sharma, and Sandeep Kumar. A unified framework for optimization-based graph coarsening. Journal of Machine Learning Research, 24 0 (118): 0 1--50, 2023 a . URL http://jmlr.org/papers/v24/22-1085.html

    2023

  32. [32]

    Featured graph coarsening with similarity guarantees

    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 Researc...

    2023

  33. [33]

    Finding global homophily in graph neural networks when meeting heterophily

    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

    2022

  34. [34]

    Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods

    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

    2021

  35. [35]

    Graph summarization methods and applications: A survey

    Yike Liu, Tara Safavi, Abhilash Dighe, and Danai Koutra. Graph summarization methods and applications: A survey. ACM Comput. Surv., 51 0 (3), jun 2018. ISSN 0360-0300. URL https://doi.org/10.1145/3186727

    doi:10.1145/3186727 2018

  36. [36]

    Spectrally approximating large graphs with smaller graphs

    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

    2018

  37. [37]

    Li, Jian Tang, Guy Wolf, and Stefanie Jegelka

    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

    Pith/arXiv arXiv 2024

  38. [38]

    A fractional graph laplacian approach to oversmoothing

    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

    2023

  39. [39]

    E. A. Nadaraya. On estimating regression. Theory of Probability & Its Applications, 9 0 (1): 0 141--142, 1964. doi:10.1137/1109020. URL https://doi.org/10.1137/1109020

    doi:10.1137/1109020 1964

  40. [40]

    Perona and J

    P. Perona and J. Malik. Scale-space and edge detection using anisotropic diffusion. IEEE Transactions on Pattern Analysis and Machine Intelligence, 12 0 (7): 0 629--639, 1990. doi:10.1109/34.56205

    doi:10.1109/34.56205 1990

  41. [41]

    A critical look at the evaluation of GNN s under heterophily: Are we really making progress? In International Conference on Learning Representations, 2023

    Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. A critical look at the evaluation of GNN s under heterophily: Are we really making progress? In International Conference on Learning Representations, 2023. URL https://openreview.net/forum?id=tJbbQfw-5wv

    2023

  42. [42]

    Aditya Prakash, Chanhyun Kang, Yao Zhang, and V.S

    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. doi:10.1145...

    arXiv 2014

  43. [43]

    Rethinking softmax with cross-entropy: Neural network classifier as mutual information estimator, 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

    Pith/arXiv arXiv 2020

  44. [44]

    J. W. Ruge and K. Stüben. 4. Algebraic Multigrid, pages 73--130. doi:10.1137/1.9781611971057.ch4. URL https://epubs.siam.org/doi/abs/10.1137/1.9781611971057.ch4

    doi:10.1137/1.9781611971057.ch4

  45. [45]

    Konstantin Rusch, Michael M

    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

    Pith/arXiv arXiv 2023

  46. [46]

    Scalable graph neural network training: The case for sampling

    Marco Serafini and Hui Guan. Scalable graph neural network training: The case for sampling. SIGOPS Oper. Syst. Rev., 55 0 (1): 0 68–76, June 2021. ISSN 0163-5980. doi:10.1145/3469379.3469387. URL https://doi.org/10.1145/3469379.3469387

    arXiv 2021

  47. [47]

    Graph attention networks

    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

    2018

  48. [48]

    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 0 (2): 0 415--436, 2023. doi:10.1109/TBDATA.2022.3177455

    arXiv 2023

  49. [50]

    Sgformer: Simplifying and empowering transformers for large-graph representations

    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. Curra...

    2023

  50. [51]

    Graph coarsening via supervised granular-ball for scalable graph neural network training

    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 0 (12): 0 12872--12880, Apr. 2025. doi:10.1609/aaai.v39i12.33404. URL https://ojs.aaai.org/index.php/AAAI/article/view/33404

    work page doi:10.1609/aaai.v39i12.33404 2025

  51. [52]

    Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks

    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

    2022

  52. [53]

    A survey on multi-task learning

    Yu Zhang and Qiang Yang. A survey on multi-task learning. IEEE Transactions on Knowledge and Data Engineering, 34 0 (12): 0 5586--5609, 2022. doi:10.1109/TKDE.2021.3070203

    arXiv 2022

  53. [54]

    Yu, and Shirui Pan

    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

    Pith/arXiv arXiv 2024

  54. [56]

    Beyond homophily in graph neural networks: Current limitations and effective designs

    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

    2020

  55. [58]

    Proceedings of the AAAI Conference on Artificial Intelligence , author=

    Deeper Insights Into Graph Convolutional Networks for Semi-Supervised Learning , volume=. Proceedings of the AAAI Conference on Artificial Intelligence , author=. 2018 , month=. doi:10.1609/aaai.v32i1.11604 , number=

    doi:10.1609/aaai.v32i1.11604 2018

  56. [59]

    2020 , isbn =

    Liu, Meng and Gao, Hongyang and Ji, Shuiwang , title =. 2020 , isbn =. doi:10.1145/3394486.3403076 , booktitle =

    arXiv 2020

  57. [60]

    2021 , eprint=

    Graph Neural Networks Exponentially Lose Expressive Power for Node Classification , author=. 2021 , eprint=

    2021

  58. [61]

    2023 , eprint=

    Spectral Heterogeneous Graph Convolutions via Positive Noncommutative Polynomials , author=. 2023 , eprint=

    2023

  59. [62]

    2024 , eprint=

    Optimizing Polynomial Graph Filters: A Novel Adaptive Krylov Subspace Approach , author=. 2024 , eprint=

    2024

  60. [63]

    2023 , eprint=

    LON-GNN: Spectral GNNs with Learnable Orthonormal Basis , author=. 2023 , eprint=

    2023

  61. [64]

    ICML , year=

    Feature Expansion for Graph Neural Networks , author=. ICML , year=

  62. [65]

    Proceedings of the 2023 SIAM International Conference on Data Mining (SDM) , publisher=

    Dominic Jack and Sarah Erfani and Jeffrey Chan and Sutharshan Rajasegarar and Christopher Leckie , title =. Proceedings of the 2023 SIAM International Conference on Data Mining (SDM) , publisher=. 2023 , pages =

    2023

  63. [66]

    Proceedings of the AAAI Conference on Artificial Intelligence , author=

    Improving Expressive Power of Spectral Graph Neural Networks with Eigenvalue Correction , volume=. Proceedings of the AAAI Conference on Artificial Intelligence , author=. 2024 , month=. doi:10.1609/aaai.v38i13.29326 , number=

    work page doi:10.1609/aaai.v38i13.29326 2024

  64. [67]

    Proceedings of the AAAI Conference on Artificial Intelligence , author=

    SEA-GWNN: Simple and Effective Adaptive Graph Wavelet Neural Network , volume=. Proceedings of the AAAI Conference on Artificial Intelligence , author=. 2024 , month=. doi:10.1609/aaai.v38i10.29058 , number=

    work page doi:10.1609/aaai.v38i10.29058 2024

  65. [68]

    2023 , eprint=

    Accelerating Scalable Graph Neural Network Inference with Node-Adaptive Propagation , author=. 2023 , eprint=

    2023

  66. [69]

    PC-Conv: Unifying Homophily and Heterophily with Two-Fold Filtering , url=

    Li, Bingheng and Pan, Erlin and Kang, Zhao , year=. PC-Conv: Unifying Homophily and Heterophily with Two-Fold Filtering , url=. doi:10.1609/aaai.v38i12.29246 , journal=

    work page doi:10.1609/aaai.v38i12.29246

  67. [70]

    2024 , eprint=

    An Effective Universal Polynomial Basis for Spectral Graph Neural Networks , author=. 2024 , eprint=

    2024

  68. [71]

    2023 , eprint=

    Learning Graph Filters for Spectral GNNs via Newton Interpolation , author=. 2023 , eprint=

    2023

  69. [72]

    2024 , eprint=

    Rethinking Spectral Graph Neural Networks with Spatially Adaptive Filtering , author=. 2024 , eprint=

    2024

  70. [73]

    2017 , eprint=

    Multi-dimensional Graph Fourier Transform , author=. 2017 , eprint=

    2017

  71. [74]

    and Bresson, Xavier , title=

    Monti, Federico and Bronstein, Michael M. and Bresson, Xavier , title=. Proceedings of the 31st International Conference on Neural Information Processing Systems , pages=. 2017 , isbn=

    2017

  72. [75]

    Factorization Machines , year=

    Rendle, Steffen , booktitle=. Factorization Machines , year=

  73. [76]

    Higher-Order Factorization Machines , url=

    Blondel, Mathieu and Fujino, Akinori and Ueda, Naonori and Ishihata, Masakazu , booktitle=. Higher-Order Factorization Machines , url=

  74. [77]

    Proceedings of the 26th International Joint Conference on Artificial Intelligence , pages=

    Guo, Huifeng and Tang, Ruiming and Ye, Yunming and Li, Zhenguo and He, Xiuqiang , title=. Proceedings of the 26th International Joint Conference on Artificial Intelligence , pages=. 2017 , isbn=

    2017

  75. [78]

    2017 , eprint=

    Attentional Factorization Machines: Learning the Weight of Feature Interactions via Attention Networks , author=. 2017 , eprint=

    2017

  76. [79]

    and Sturmfels, Pascal and Lee, Su-In , title=

    Janizek, Joseph D. and Sturmfels, Pascal and Lee, Su-In , title=. J. Mach. Learn. Res. , month=. 2021 , publisher=

    2021

  77. [80]

    2020 , isbn=

    Wang, Xiao and Zhu, Meiqi and Bo, Deyu and Cui, Peng and Shi, Chuan and Pei, Jian , title=. 2020 , isbn=. doi:10.1145/3394486.3403177 , booktitle=

    arXiv 2020

  78. [81]

    2024 , eprint=

    Spectral GNN via Two-dimensional (2-D) Graph Convolution , author=. 2024 , eprint=

    2024

  79. [82]

    Aggarwal and Dawei Yin and Jiliang Tang , title=

    Yao Ma and Suhang Wang and Chara C. Aggarwal and Dawei Yin and Jiliang Tang , title=. Proceedings of the 2019 SIAM International Conference on Data Mining (SDM) , chapter=. 2019 , doi=

    2019

  80. [83]

    The Eleventh International Conference on Learning Representations , year=

    Specformer: Spectral Graph Neural Networks Meet Transformers , author=. The Eleventh International Conference on Learning Representations , year=

Showing first 80 references.

This paper was first reviewed by deepseek-v4-flash on August 1, 2026.