Pith. sign in

REVIEW 3 major objections 6 minor 34 references

It Takes a Graph to Know a Graph: Rewiring for Homophily with a Reference Graph

T0 review · 3 major / 6 minor · reviewed 2026-08-15 · deepseek-v4-flash

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

Pith's one-line read Rewiring with a label-aware reference graph beats specialized GNNs

desk verdict A clean, practical rewiring method whose empirical story holds up — but the abstract overclaims past what the experiments actually compare against. read the letter →

arxiv 2505.12411 v1 pith:QQ2SGUWW submitted 2025-05-18 cs.LG

Harel Mendelman , Haggai Maron , Ronen Talmon This is my paper · ORCID
classification cs.LG
keywords graphneuralnetworksheterophilyrewiringhomophilyreferencelabel-drivendiffusionnodeclassificationedge
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper argues that graph rewiring, not just specialized architectures, can fix GNNs on heterophilic graphs, where connected nodes tend to have different labels. It proves that higher edge homophily relaxes the tension between the smoothness GNNs impose on embeddings and the linear separability needed for classification (Theorem 1), then shows that rewiring with a reference graph lifts homophily in expectation when the reference graph's residual edges are more homophilic than the original graph (Propositions 1 and 2). The proposed method, REFine, builds that reference graph by combining node features with training labels through label-driven diffusion, and treats edge addition or deletion as a scalable per-cluster preprocessing step. On 11 real-world datasets, standard GNNs trained on the rewired graph match or outperform both existing rewiring techniques and specialized heterophilic GNN architectures. The practical payoff is that homophily-enhancing rewiring is a viable alternative to designing new message-passing schemes.

What carries the argument

The load-bearing object is the reference graph $G_r$, a second graph on the same node set whose edge set is derived from a clipped label-driven diffusion kernel $\Gamma = P D P$: first normalize a Gaussian feature-affinity matrix $W_D$ into a diffusion kernel $D$, define a label-propagation kernel $P$ from training labels, and multiply $P D P$ so labels are propagated onto unlabeled nodes through feature geometry. Row-wise clipping of $\Gamma$ yields the binary adjacency of $G_r$. Two propositions carry the argument: edge addition improves expected homophily exactly when the reference graph's edges not already present are more homophilic than the original graph (Prop. 1), and edge deletion improves it when the common part of the original graph and the reference graph's complement is less homophilic than the original (Prop. 2). A corollary simplifies the addition condition to $H(G_r) > H(G)$ when the reference graph is much larger than the original, which is the condition used in practice. Scalability comes from partitioning the graph into balanced clusters, rewiring each cluster independently, and reattaching inter-cluster edges, giving per-cluster cost $O(c^3)$ and overall $O(c^2 n)$, effectively linear in the number of nodes when clusters are small.

What would settle it

On a heterophilic benchmark, corrupt the node features so they are independent of the class labels while keeping the original graph and label distribution fixed; REFine should then fail to produce a reference graph with $H(G_r) > H(G)$ and should show no accuracy gain over training on the original graph. A cleaner test: run the method on two synthetic graphs with identical structure and labels, one with label-aligned features and one with permuted features, and compare rewired homophily and test accuracy.

Watch

Extended reading notes

Core claim

The central claim is that a graph's own structure can be improved for message passing by consulting a second graph, the reference graph, built from the same nodes, and that homophily-enhancing rewiring is provably effective when the reference graph is more homophilic than the original. Formally, the paper links edge homophily to a lower bound on the Dirichlet energy of any linearly separable embedding: $\mathrm{tr}(Z^T L Z) \geq \frac{\alpha_m |E|}{2\|W\|^2}(1-H(G))$, so low-homophily graphs force a trade-off between smoothing and separability. It then proves that adding random edges from the reference graph increases expected homophily if $H(G_r \setminus G) > H(G)$, and deleting random edges shared with the reference graph's complement increases it if $H(G \cap G_r^c) < H(G)$. The practical discovery is that a reference graph built from feature similarities and training labels via the label-driven diffusion kernel $\Gamma = P D P$ is homophilic enough to trigger these conditions, and that rewiring with it improves node classification for standard GNNs across low-homophily benchmarks.

Load-bearing premise

The method assumes the feature space gives a meaningful similarity measure aligned with the labels; if it does not, the label-driven reference graph will not be more homophilic than the original graph, and the rewiring step can lower both homophily and accuracy.

Editorial extensions

If this is right

  • Standard GNNs (GCN, GATv2, APPNP) can match or exceed specialized heterophilic architectures (MixHop, H2GCN, GPRGNN, OrderedGNN) simply by training on the rewired graph.
  • The larger the homophily gap between the original graph and the reference graph, the larger the expected accuracy gain; datasets with very low original homophily benefit most.
  • The method scales to graphs with hundreds of thousands of nodes because rewiring is performed independently on clusters, with complexity linear in node count when clusters are small.
  • Rewiring can be guided by a simple check: if the reference graph, or its residual edges, is not more homophilic than the original, edge addition should be avoided because it degrades both homophily and accuracy.
  • A reference graph constructed from features and training labels can be used to rewire larger graphs without requiring full label supervision, since only training labels enter the diffusion kernel.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Because the reference graph is built from features and training labels only, the same construction could be applied inductively to unseen graphs in a trained model's deployment, provided the label-driven diffusion kernel can be estimated from a small labeled seed.
  • The homophily conditions in Propositions 1 and 2 could be used online: estimate $H(G_r \setminus G)$ and $H(G \cap G_r^c)$ from a validation sample, then choose edge addition, deletion, or no rewiring accordingly, turning $k$ from a fixed hyperparameter into an adaptive decision.
  • If feature similarity and label structure diverge, for example when features are noisy or dominated by a spurious signal, the method's own condition predicts failure; a test on a graph with deliberately label-uncorrelated features would sharpen the boundary of applicability.
  • The reference-graph idea could also be used to target properties other than homophily, such as preserving local clustering or reducing over-squashing, by choosing the reference graph to encode the desired structural prior.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 6 minor

Summary. The paper proposes REFine, a graph rewiring method that increases edge homophily by adding or deleting edges guided by a reference graph constructed from node features and training labels via label-driven diffusion. The authors prove that adding or removing random edges from or against a suitable reference graph improves expected homophily (Props. 1-2), and they prove a lower bound linking homophily to the Dirichlet energy of linearly separable embeddings (Thm. 1). The method clusters large graphs with METIS for scalability and is evaluated on 11 heterophilic datasets across GCN, GATv2, and APPNP, comparing favorably to several rewiring baselines and specialized GNNs. The paper includes code and reports extensive ablations, including the effect of cluster size and the homophily of the constructed reference graphs.

Significance. If the concerns below are addressed, the paper makes a useful contribution: it gives a clean expected-homophily monotonicity result for reference-guided rewiring, a scalable and practical algorithm, and strong empirical gains on several heterophilic benchmarks. The release of code and the use of standard benchmarks support reproducibility. The main conceptual novelty—using a feature- and label-driven reference graph to rewire for homophily—is well motivated. However, the strongest claims in the abstract and introduction are currently broader than what is actually verified, and one central proof contains an algebraic error that must be corrected.

major comments (3)
  1. [Appendix A.1, proof of Theorem 1] The proof contains an algebraic error: the displayed equality \sum_{(u,v)\in E} A_{uv}\|y_u - y_v\|^2 = 2\|W\|^2\operatorname{tr}(Z^T L Z) is false because \|(z_u - z_v)W\|^2 is not equal to \|W\|^2\|z_u - z_v\|^2 for a general matrix W. The correct step is an inequality \|(z_u - z_v)W\|^2 \le \|W\|^2\|z_u - z_v\|^2, which still yields the stated lower bound after dividing by \|W\|^2. This must be corrected; as written, the proof does not establish Theorem 1, which is the paper's main theoretical motivation.
  2. [Section 2 and Tables 1-2] The abstract and Section 1 claim that REFine 'outperforms existing rewiring techniques,' but the only homophily-targeted rewiring method discussed in Section 2, DHGR [23], is excluded from all experiments on the basis that it is closer to graph structure learning. The baselines actually evaluated (SDRF, FoSR, BORF) are designed for over-smoothing and over-squashing, not homophily. As a result, the headline claim is not substantiated for the directly relevant competitor. The authors should either add a DHGR comparison (even on a subset of datasets) or narrow the claim to the evaluated baselines.
  3. [Section 5 and Props. 1-2] The theoretical guarantees of Props. 1 and 2 apply to a random rewiring process on the whole graph and require exact conditions on H(G_r\setminus G) and H(G\cap G_r^c). In the deployed method, rewiring is performed per METIS cluster, the conditions are checked only approximately using a sampled graph (Appendix C.3), and the choice of edge addition versus deletion is selected as a hyperparameter by validation accuracy rather than by whether the proposition's condition holds. The abstract's statement 'with theoretical guarantees on the homophily of the rewired graph' therefore overstates the connection between the theory and the actual algorithm. The gap should be made explicit and analyzed, or the guarantee should be limited to the idealized setting of Section 4.1.
minor comments (6)
  1. [Section 5, notation] The text 'where n<n ' is missing a subscript, and 'Y =\in \mathbb{R}^{n\times 1}' contains a typo; please fix both.
  2. [Section 4.2, figure reference] The text refers to '(4a)' and '(4b)' when discussing Figure 2; these should be '(2a)' and '(2b)'.
  3. [Appendix A.2, sampling model] The proof models edge selection as i.i.d. Bernoulli draws, while Algorithm 1 samples a random subset without replacement. The expectation formula is unaffected by this distinction, but the proof should state the correct sampling model or justify the equivalence.
  4. [Theorem 1 statement] The theorem says 'linearly separable embeddings,' but the proof assumes the exact equality Y = ZW, i.e., a zero-error linear classifier. This assumption is stronger than linear separability and should be stated explicitly in the theorem.
  5. [Appendix D] 'T/0' should be 'T/O' (timeout).
  6. [Table 1 caption] The REFine Gain row uses upward and downward arrows without a definition; please add a note that they indicate positive and negative gains, respectively.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the theoretical guarantees are direct consequences of the edge-homophily definition, and the accuracy gains are independent empirical measurements.

full rationale

The central theoretical results (Theorem 1, Propositions 1 and 2, Corollary 1) are derived self-containedly from the definition of edge homophily and elementary algebra. For example, Proposition 1's condition H(Gr\G) > H(G) is exactly the sign condition for the derivative of E[H(G(k))] with respect to k, so the 'guarantee' is a mathematical implication rather than an assumption of the conclusion. The label-driven diffusion kernel Γ = PDP is attributed to the authors' prior work [14], but Section 5 and Appendix C.2 specify the construction in full, and Appendix E.3 evaluates H(Gr) for Γ = D versus Γ = PDP on real data; the accuracy results in Tables 1 and 2 are direct experimental measurements after validation-set hyperparameter selection, not quantities forced by the definitions. No fitted parameter is renamed as a prediction, and no uniqueness theorem is imported from the authors' prior work. The omission of DHGR from the comparison tables is a benchmarking completeness concern, not circularity.

Assumptions & free parameters 5 free parameters · 4 assumptions · 0 invented entities

The central claim relies on standard hyperparameters (epsilon, k, kernel choice, direction, cluster size) tuned on validation, plus domain assumptions: feature similarity aligns with labels, GNNs smooth embeddings, sampled homophily approximates full homophily, and METIS clusters preserve useful structure. No new physical or conceptual entities are introduced.

free parameters (5)
  • scale parameter epsilon = searched in {1e-8, 1e-7, 1e-6, 1e-5, 1e-4, 1e-3, 1e-2, 1e0, 1e1, 1e2}
    Gaussian kernel bandwidth for the feature affinity W_D, selected per dataset by validation accuracy.
  • number of rewired edges k = searched in {0.1m, 0.3m, 0.5m, 0.7m, 0.9m, m}
    Number of edges added from E_r\E or deleted from E\E_r^c, selected via validation accuracy.
  • kernel choice Gamma = PDP vs D = binary choice
    Whether to use label-driven diffusion or features only; selected per dataset via validation.
  • rewiring direction = addition or deletion
    Whether to add or delete edges; selected via validation accuracy.
  • cluster size c = 100 or 500
    METIS cluster size set by graph size, with Table 11 showing limited sensitivity.
assumptions (4)
  • domain assumption The feature space offers a meaningful measure of similarity that aligns with the labels
    Section 5 states this assumption explicitly; if false, the reference graph may not be homophilic and rewiring can hurt (Fig. 1c). Acknowledged as a limitation in Section 8.
  • domain assumption Message passing GNNs inherently smooth embeddings along the graph
    Section 4 motivates Theorem 1 using the claim that smoothing is the nature of GNNs; this underlies why increasing homophily should help.
  • domain assumption The sampled graph homophily approximates the true graph homophily
    Appendix C.3 uses sampled graphs to check the Prop. 1/2 conditions with validation labels; the approximation is validated only on a few datasets.
  • standard math METIS produces balanced clusters and preserves useful structure
    Section 5 uses METIS for scalability and preserves inter-cluster edges; the per-cluster guarantees assume clusters behave like independent graphs.

how reviews work

0 comments
Cite this review

Pith. "Pith review of It Takes a Graph to Know a Graph: Rewiring for Homophily with a Reference Graph." pith.science (2026). https://pith.science/paper/QQ2SGUWW

@misc{pith2026250512411,
  author       = {Pith},
  title        = {Pith review of: It Takes a Graph to Know a Graph: Rewiring for Homophily with a Reference Graph},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QQ2SGUWW}},
  note         = {Machine review of arXiv:2505.12411}
}
read the original abstract

Graph Neural Networks (GNNs) excel at analyzing graph-structured data but struggle on heterophilic graphs, where connected nodes often belong to different classes. While this challenge is commonly addressed with specialized GNN architectures, graph rewiring remains an underexplored strategy in this context. We provide theoretical foundations linking edge homophily, GNN embedding smoothness, and node classification performance, motivating the need to enhance homophily. Building on this insight, we introduce a rewiring framework that increases graph homophily using a reference graph, with theoretical guarantees on the homophily of the rewired graph. To broaden applicability, we propose a label-driven diffusion approach for constructing a homophilic reference graph from node features and training labels. Through extensive simulations, we analyze how the homophily of both the original and reference graphs influences the rewired graph homophily and downstream GNN performance. We evaluate our method on 11 real-world heterophilic datasets and show that it outperforms existing rewiring techniques and specialized GNNs for heterophilic graphs, achieving improved node classification accuracy while remaining efficient and scalable to large graphs.

Figures

Figures reproduced from arXiv: 2505.12411 by the authors.

Figure 1
Figure 1. Edge addition on Cornell: First row shows ho [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 3
Figure 3. Rewiring method overview: (1) Cluster the original graph into clusters. (2) Construct a [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figure 4
Figure 4. Rewiring Cora using Gr built only from train labels. Homophily and rewiring effectiveness. In Appendix G.1, we empirically demonstrate that datasets with lower original homophily tend to show greater test accuracy gains from our rewiring method. This is likely because the reference graph typically has much higher homophily than the original in such cases, resulting in a significantly more homophilic rewired graph an… view at source ↗
Figures from the paper (6 more)
Figure 5
Figure 5. Figure 5: Simulation of edge addition on the Wisconsin dataset. [PITH_FULL_IMAGE:figures/full_fig_p015_5.png]
Figure 6
Figure 6. Figure 6: Simulation of edge addition on the Texas dataset. [PITH_FULL_IMAGE:figures/full_fig_p015_6.png]
Figure 7
Figure 7. Figure 7: Simulation of edge addition on the Wiki dataset. [PITH_FULL_IMAGE:figures/full_fig_p016_7.png]
Figure 8
Figure 8. Figure 8: Heatmap visualizations of the kernels PDP and D for the BlogCatalog dataset. The rows and columns are sorted by label, with an ideal heatmap showing high-value diagonal blocks for each class. The PDP heatmap exhibits better class separation compared to D, reflecting im…
Figure 9
Figure 9. Figure 9: Edge homophily of the original graph G, the reference graph Gr used for rewiring, and the rewired graph G (k) . E.3 Reference graph homophily: features vs. label-driven diffusion [PITH_FULL_IMAGE:figures/full_fig_p020_9.png]
Figure 10
Figure 10. Figure 10: Test accuracy improvement across all evaluated datasets. [PITH_FULL_IMAGE:figures/full_fig_p022_10.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

34 extracted references · 12 canonical work pages

  1. [23]

    Make heterophilic graphs better fit gnn: A graph rewiring approach

    Wendong Bi, Lun Du, Qiang Fu, Yanlin Wang, Shi Han, and Dongmei Zhang. Make heterophilic graphs better fit gnn: A graph rewiring approach. IEEE Transactions on Knowledge and Data Engineering, 2024

    work page 2024

  2. [1]

    Braingnn: Interpretable brain graph neural network for fmri analysis

    Xiaoxiao Li, Yuan Zhou, Nicha Dvornek, Muhan Zhang, Siyuan Gao, Juntang Zhuang, Dustin Scheinost, Lawrence H Staib, Pamela Ventola, and James S Duncan. Braingnn: Interpretable brain graph neural network for fmri analysis. Medical Image Analysis, 74:102233, 2021

    2021

  3. [2]

    Learning effective road network representation with hierarchical graph neural networks

    Ning Wu, Xin Wayne Zhao, Jingyuan Wang, and Dayan Pan. Learning effective road network representation with hierarchical graph neural networks. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pages 6–14, 2020

    work page 2020

  4. [3]

    Fast and flexible protein design using deep graph neural networks

    Alexey Strokach, David Becerra, Carles Corbi-Verge, Albert Perez-Riba, and Philip M Kim. Fast and flexible protein design using deep graph neural networks. Cell systems, 11(4):402–411, 2020

    work page 2020

  5. [4]

    Birds of a feather: Homophily in social networks

    Miller McPherson, Lynn Smith-Lovin, and James M Cook. Birds of a feather: Homophily in social networks. Annual review of sociology, 27(1):415–444, 2001

    2001

  6. [5]

    Graph neural networks for graphs with heterophily: A survey

    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. arXiv preprint arXiv:2202.07082, 2022

    arXiv 2022

  7. [6]

    Be- yond homophily in graph neural networks: Current limitations and effective designs

    Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Be- yond homophily in graph neural networks: Current limitations and effective designs. Advances in neural information processing systems, 33:7793–7804, 2020

    work page 2020

  8. [7]

    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. IEEE, 2022

    work page 2022

Show all 34 references
  1. [8]

    Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing

    Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In international conference on machine learning...

    2019

  2. [9]

    Adaptive universal generalized pagerank graph neural network

    Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. arXiv preprint arXiv:2006.07988, 2020

    2006 arXiv

  3. [10]

    Exploiting neighbor effect: Conv-agnostic gnn framework for graphs with heterophily

    Jie Chen, Shouzhen Chen, Junbin Gao, Zengfeng Huang, Junping Zhang, and Jian Pu. Exploiting neighbor effect: Conv-agnostic gnn framework for graphs with heterophily. IEEE Transactions on Neural Networks and Learning Systems, 2023

    2023

  4. [11]

    Rewiring techniques to mitigate over- squashing and oversmoothing in gnns: A survey

    Hugo Attali, Davide Buscaldi, and Nathalie Pernelle. Rewiring techniques to mitigate over- squashing and oversmoothing in gnns: A survey. arXiv preprint arXiv:2411.17429, 2024

    2024 arXiv

  5. [12]

    Deeper insights into graph convolutional networks for semi-supervised learning

    Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018

    2018

  6. [13]

    On the bottleneck of graph neural networks and its practical implications

    Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. arXiv preprint arXiv:2006.05205, 2020

    2006 arXiv

  7. [14]

    Supervised and semi-supervised diffusion maps with label-driven diffusion

    Harel Mendelman and Ronen Talmon. Supervised and semi-supervised diffusion maps with label-driven diffusion. In The Thirteenth International Conference on Learning Representations, 2025

    2025

  8. [15]

    Diffusion maps

    Ronald R Coifman and Stéphane Lafon. Diffusion maps. Applied and computational harmonic analysis, 21(1):5–30, 2006

    2006

  9. [16]

    Geom-gcn: Geometric graph convolutional networks

    Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gcn: Geometric graph convolutional networks. arXiv preprint arXiv:2002.05287, 2020

    2002 arXiv

  10. [17]

    New benchmarks for learning on non-homophilous graphs

    Derek Lim, Xiuyu Li, Felix Hohne, and Ser-Nam Lim. New benchmarks for learning on non-homophilous graphs. arXiv preprint arXiv:2104.01404, 2021. 10

    2021 arXiv

  11. [18]

    Neighborhood homophily-based graph convolutional network

    Shengbo Gong, Jiajun Zhou, Chenxuan Xie, and Qi Xuan. Neighborhood homophily-based graph convolutional network. In Proceedings of the 32nd ACM international conference on information and knowledge management, pages 3908–3912, 2023

    2023

  12. [19]

    Graph neural networks with heterophily

    Jiong Zhu, Ryan A Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K Ahmed, and Danai Koutra. Graph neural networks with heterophily. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pages 11168–11176, 2021

    2021

  13. [20]

    Powerful graph convolutional networks with adaptive propagation mechanism for homophily and heterophily

    Tao Wang, Di Jin, Rui Wang, Dongxiao He, and Yuxiao Huang. Powerful graph convolutional networks with adaptive propagation mechanism for homophily and heterophily. In Proceedings of the AAAI conference on artificial intelligence, volume 36, pages 4210–4218, 2022

    2022

  14. [21]

    Revisiting over-smoothing and over-squashing using ollivier-ricci curvature

    Khang Nguyen, Nong Minh Hieu, Vinh Duc Nguyen, Nhat Ho, Stanley Osher, and Tan Minh Nguyen. Revisiting over-smoothing and over-squashing using ollivier-ricci curvature. In International Conference on Machine Learning, pages 25956–25979. PMLR, 2023

    2023

  15. [22]

    Understanding over-squashing and bottlenecks on graphs via curvature

    Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. arXiv preprint arXiv:2111.14522, 2021

    2021 arXiv

  16. [24]

    Opengsl: A comprehensive benchmark for graph structure learning

    Zhiyao Zhou, Sheng Zhou, Bochao Mao, Xuanyi Zhou, Jiawei Chen, Qiaoyu Tan, Daochen Zha, Yan Feng, Chun Chen, and Can Wang. Opengsl: A comprehensive benchmark for graph structure learning. Advances in Neural Information Processing Systems, 36:17904–17928, 2023

    2023

  17. [25]

    How to learn a graph from smooth signals

    Vassilis Kalofolias. How to learn a graph from smooth signals. In Artificial intelligence and statistics, pages 920–929. PMLR, 2016

    2016

  18. [26]

    Measuring and relieving the over-smoothing problem for graph neural networks from the topological view

    Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Measuring and relieving the over-smoothing problem for graph neural networks from the topological view. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 3438–3445, 2020

    2020

  19. [27]

    A fast and high quality multilevel scheme for partitioning irregular graphs

    George Karypis and Vipin Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on scientific Computing, 20(1):359–392, 1998

    1998

  20. [28]

    Fosr: First-order spectral rewiring for addressing oversquashing in gnns

    Kedar Karhadkar, Pradeep Kr Banerjee, and Guido Montúfar. Fosr: First-order spectral rewiring for addressing oversquashing in gnns. arXiv preprint arXiv:2210.11790, 2022

    2022 arXiv

  21. [29]

    Semi-supervised classification with graph convolutional networks

    Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907, 2016

    2016 arXiv

  22. [30]

    How attentive are graph attention networks?arXiv preprint arXiv:2105.14491, 2021

    Shaked Brody, Uri Alon, and Eran Yahav. How attentive are graph attention networks?arXiv preprint arXiv:2105.14491, 2021

    2021 arXiv

  23. [31]

    Predict then propagate: Graph neural networks meet personalized pagerank

    Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint arXiv:1810.05997, 2018

    2018 arXiv

  24. [32]

    Ordered gnn: Ordering message passing to deal with heterophily and over-smoothing.arXiv preprint arXiv:2302.01524, 2023

    Yunchong Song, Chenghu Zhou, Xinbing Wang, and Zhouhan Lin. Ordered gnn: Ordering message passing to deal with heterophily and over-smoothing.arXiv preprint arXiv:2302.01524, 2023

    2023 arXiv

  25. [33]

    Less is more: on the over- globalizing problem in graph transformers

    Yujie Xing, Xiao Wang, Yibo Li, Hai Huang, and Chuan Shi. Less is more: on the over- globalizing problem in graph transformers. arXiv preprint arXiv:2405.01102, 2024

    2024 arXiv

  26. [34]

    T/O" indicates a timeout and

    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? arXiv preprint arXiv:2302.11640, 2023. 11 A Proofs A.1 Proof of Theorem 1 Proof of Theorem 1....

    2023 arXiv

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.