acceptodds
Under review as a conference paper at ICLR 2027

Geometry-Induced Diffusion on Graphs: Learning Task-Adaptive Propagation for GNNs

Abstract

Long-range information propagation remains challenging in Graph Neural Networks (GNNs), where repeated local aggregation can lead to oversmoothing and oversquashing. Existing approaches often rely on global attention mechanisms or modify the graph topology through rewiring, potentially increasing computational or architectural complexity. We introduce a learnable node-wise function that induces a weighted graph Laplacian , allowing the propagation geometry to adapt to the task while preserving the original graph topology. This construction is not specific to a particular GNN architecture; here, we instantiate it within Chebyshev spectral convolutions, yielding -ChebNet. We show that learning reshapes the spectrum of the diffusion operator, modifying how long different graph signal components persist during propagation and thus the timescale over which oversmoothing occurs. On a controlled bottleneck example, we further show that reweighting the graph through can reduce effective resistance, a quantity previously connected to oversquashing. Experiments on synthetic long-range tasks and real-world graph benchmarks show improved predictive performance while retaining the computational structure of sparse polynomial graph filtering.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph Neural Networks, Graph Laplacians, Learnable Graph Geometry, Graph Diffusion, Oversmoothing, Oversquashing, Long-Range Graph Learning

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_fFnWOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

In this work, the authors present a diffusion geometry for GNNs which is task-depending. The fixed graph Laplacian gives its place to a learned discrete Laplacian with a propagation operator that keeps the original topology. Furthermore, by studying the spectral decay, the work associates the learned geometry to the well-known phenomena of oversmoothing and oversquashing. The introduced µ-ChebNet is a novel architecture that exploits spectral and message-passing. µ-ChebNet performs well already at smaller depths, showing we can use a less layers for long-range. Finally, the model is on par with widely known and strong baselines.

Critical strengths
  • Novel GNN arch where the diffusion geometry is learned directly
  • Provides interpretability via μ which shows how propagation is affected
Critical weaknesses
  • Related work missing: for example "Neural Sheaf Diffusion" (Bodnar et al.), provides connections between GNNs and topology
  • The paper talks about rewiring, yet no rewiring method appears in any results table.
  • Learnable-filter spectral GNNs (like GPR-GNN, BernNet, ChebNetII, JacobiConv) aren’t compared, even though L_μ could plug into any of them.
  • More benchmarks, like LRGB, the standard long-range suite, and maybe heterophily benchmarks could strengthen the paper.
Questions for authors
  • Connection with StableNet from paper "Return of ChebNet: Understanding and Improving an Overlooked GNN on Long Range Tasks". The paper appears also as two similar references (a diff in the order of authors)
2 comments

We thank the reviewer for the useful suggestions.

Weaknesses

  • We have extended our related work section to discuss Neural Sheaf Diffusion and clarify its connection to our construction. Our weighted Laplacian is a special case of a sheaf Laplacian with one-dimensional stalks and equal restriction maps at the endpoints of each edge. We now explain that our specific contribution lies in defining these edge weights through a node weight and analyzing the resulting operator. We have also added a discussion of GPR-GNN and other methods that learn graph propagation or modify the graph structure.
  • Our additional long-range graph benchmark LRGB Peptides-Func and Peptides-struct benchmarks presented in Appendix Section I “SUPPLEMENTARY EXPERIMENTAL RESULTS”, subsection 3, table 5 now includes graph rewiring methods: LASER, DRew-GCN also with positional encodings (PE). The μ\mu-ChebNET architecture outperforms them in both tasks except for the method with PE on peptide-struc against which it remains comparable without the need of additional embeddings (Test MAE of 0.2552 ±\pm 0.0039 vs 0.2536 ±\pm 0.0015).
  • Following the review, we have added comparisons with BernNet and a μ\mu-BernNet variant that uses our learned Laplacian just as the ChebNet does. Training and testing could be finalized for the Graph property prediction benchmark we added (Appendix Section I “SUPPLEMENTARY EXPERIMENTAL RESULTS”, subsection4, table 6). It confirms the advantage of the μ\mu variant with improved performance on all three tasks: diameter, sssp, eccentricity. Further hyperparameter optimization can be envisioned. The additional long-range graph benchmark LRGB Peptides-Func and Peptides-struct benchmarks presented in Appendix Section I “SUPPLEMENTARY EXPERIMENTAL RESULTS”, subsection 3, table 5 also includes BernNet and μ\mu-BernNet results. However, the hyperparameters tuning is not finalized. We expect to replace the corresponding table values once optimized. Relevant interpretations and conclusions will be then made. We are also waiting for the models' training and testing to finalize to be able to include their performance on the City-networks datasets.
  • As mentioned above, we have extended our evaluation to Peptides-func and Peptides-struct from LRGB. We have also added City Networks and Graph property benchmarks. We have focused this revision on long-range propagation. We expect our model to work like other GNNs on heterophily benchmarks, since it is based on the same layer.

Questions

  • Stable-ChebNet is a method that is particularly designed to emulate unitary dynamics. This is therefore different from the type of architecture that is considered in this paper. However, our current experiences show that there is no systematic advantage on using μ\mu-stable-ChebNet over any ChebNet variant. This could be an artifact of unoptimized parameters.

I thank the authors for their response which address most of my concerns. I will raise my score accordingly.

Reviewer_pZ6eOpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

This paper provides a lightweight modification to ChebNet. They focus on learning a positive node-wise function, then assigning each existing edge a weight, resulting in a weighted Laplacian that replaces the fixed Laplacian in ChebNet. The authors analyze its spectral properties and illustrate how node weighting changes graph properties such as diffusion, and effective resistance.

Critical strengths
  1. The idea seems simple and computationally efficient. The proposed method uses sparse polynomial filtering, making it practical to apply.

  2. The writing is generally clear and easy to follow. The visual illustrations are good.

  3. The performance gains compared to fixed-Laplacian ChebNet are impressive.

Critical weaknesses
  1. There are many works that already learn graph diffusion, perform edge reweighting and modify spectral properties related to information propagation. There should be proper discussion of those distinctions as well. Positioning the contribution mainly against fixed-Laplacian ChebNet is insufficient to establish novelty.

  2. The theory relies on heat diffusion with decay factors. However, actual ChebNet uses learned filters that do not need to be necessarily positive, monotone, or low-pass. This makes a theory-empirical gap.

  3. The experiments are limited to one node classification dataset and a few synthetic benchmarks. To better assess the method’s applicability, the authors should evaluate it on multiple real-world datasets with diverse structural characteristics. The comparison should also go beyond ChebNet to include strong message-passing, spectral, and graph-reweighting baselines to establish whether the proposed approach offers advantages over existing methods for long-range information propagation. Currently, the experiments read more like a proof of concept.

  4. I can't comment on reproducibility as no code is provided.

Questions for authors

Please refer to the weaknesses.

3 comments
  • We thank the reviewer for this comment and have substantially expanded the related work and the positioning of our contribution. The revised paper now discusses (i) learned diffusion operators (GDC, DiffWire, GRAND, BLEND); (ii) graph rewiring based on curvature, spectral gap and effective resistance (GTR, DRew, LASER); (iii) attention-based reweighting (GAT); and (iv) Neural Sheaf Diffusion. Our distinction from these approaches is the structure of the learned operator. Rather than learning free edge weights or new edges, we learn one scalar per node, and edge weights are induced through a weighted Dirichlet form. This has three consequences, each now made explicit in the paper. First, the operator is symmetric and positive semidefinite, so it plugs into any spectral filter, with a drift–diffusion interpretation (Theorem 2). Second, the node factorization is what makes the spectral bounds of Theorem 3 possible; they do not hold for general edge weights. Third, it allows precise statements about oversquashing (new Section 4.4): μ\mu acts on the network’s Jacobian only by reweighting shortest-path transition probabilities, it provably reduces the commute time across bottlenecks to the optimal order for node potentials, and a degree ceiling (Lemma 4.2) quantifies exactly what node-wise weighting can and cannot achieve compared with free edge weights. We also show (Section 4.5) that the induced operator is a symmetrized softmax attention, which clarifies its relation to GAT, and that LμL_\mu is a sheaf Laplacian with one-dimensional stalks, a subclass of NSD whose structure is what enables the guarantees above. Finally, the construction is not specific to ChebNet: it can replace the Laplacian in any spectral GNN.
  • We thank the reviewer for raising this point, which we now address explicitly. First, our structural results do not depend on the filter. Theorems 1–3 are statements about the operator LμL_\mu, and any spectral filter g acts on its modes through g(λkμ)g(λ^\mu_k). Reshaping the spectrum therefore changes what every filter can do. For instance, eigenvalues that are degenerate under LL, and hence indistinguishable by any filter, are split by LμL_\mu(Appendix B). Second, we added a new section (Section 4.4) analyzing the Jacobian of μ\mu-ChebNet with arbitrary learned Chebyshev filters, which need not be positive, monotone, or low-pass. On any graph, the sensitivity ∥∂hi/∂xs∥\|\partial h_i/ \partial x_s\| is bounded by the walk weights of the µ-weighted operator, with a constant that depends only on the filter order and weight norms (Proposition 1). The filters therefore only set a graph-independent scale. Dependence on the graph, and on μ\mu, enters through shortest-path transition probabilities. At the boundary of the receptive field, this becomes an exact identity. On a barbell of two m-node cliques, for any fixed filter weights, a bridge-focused node weighting increases the actual cross-clique Jacobian by a factor of order m (Proposition 2). We also derive, on any graph, exact formulas for how a node weight changes the commute time of the induced walk (Proposition 3). On the barbell, this reduces the commute time from O(m2)\mathcal O(m^2) to O(m)\mathcal O(m), which is the optimal order for node weightings. Finally, regarding heat diffusion: the Laplacian is the generator of diffusion, which is why this vocabulary appears throughout. In Section 4.2, heat diffusion serves only as the simplest model to interpret the spectral changes of Theorem 3; it is not an assumption of the results above. We have clarified this in the text.
  • Since the initial submission, we have extended the experimental section with several real-world and synthetic benchmarks presented in Appendix Section I “SUPPLEMENTARY EXPERIMENTAL RESULTS”, subsections 3 to 5: the long-range graph benchmark LRGB Peptides-Func and Peptides-struct, the Graph Property Prediction (diameter, sssp, eccentricity), the City-Networks (Paris, Shanghai, Los Angeles, London) datasets. Learning with μ\mu improves the backbone architecture predictions and the ChebNet variants present good or competitive performance. City-networks results in Table 7, Graph property prediction ones table 6 presents additional methods. Table 5 with LRGB datasets is the most complete comparison including more models appropriate for the task: transformer-based, rewiring, state space or GNNs. Our approach remains relevant in terms of performance and computational costs.
  • We are polishing the code and will make it available with the camera-ready version of the paper. We can provide it beforehand if necessary.

I thank the authors for the thorough revision. The expanded related work and the new Section 4.4 addressed my concerns about novelty positioning and the theory-empirical gap. I have raised my score from 1 to 2 (weak reject).

My rating remains a weak reject because the empirical demonstration of the method’s value for real-world use is not yet convincing. The gains over ChebNet seem somewhat marginal. Overall, the contribution remains incremental. It is a lightweight modification of ChebNet with a learned node-wise weighting, and the theory, while a useful addition, does not yet translate into clear practical gains. The work is technically sound, but in my opinion it falls below the bar of a top-tier conference such as ICLR.

We thank the reviewer for the follow-up. We would like to highlight that the benefit of learning μ\mu becomes more pronounced in the presence of severe structural bottlenecks. To investigate this, we conducted an additional experiment on two-community SBM graphs, progressively reducing the number of edges connecting the communities. We compare ChebNet and μ\mu-ChebNet with the same polynomial order K=7K=7 and 8 layers. Both models therefore have the same theoretical receptive-field radius, allowing us to investigate the effect of learned node weighting on information propagation across the bottleneck. As the bottleneck becomes more restrictive, the test MSE of ChebNet increases sharply, while μ\mu-ChebNet maintains substantially lower error in the most challenging settings. With a single bridge edge, μ\mu-ChebNet achieves a test MSE more than 10 times lower than standard ChebNet. When the communities are more densely connected, the models exhibit comparable performance. We also evaluated both models on TreeNeighborsMatch, a benchmark specifically designed to investigate oversquashing. While both models achieve nearly perfect accuracy on shallower trees, at depth 5, μ\mu-ChebNet achieves a mean test accuracy of 95.86%, compared with 88.53% for ChebNet. Moreover, the variability across runs is considerably lower, with standard deviations of 3.35 and 13.18 percentage points, respectively. Together with the other synthetic and real-world benchmarks added in this revision, these results provide further empirical support for our theoretical analysis. They show that a lightweight modification, learning one weight per node, can improve performance on challenging long-range tasks while retaining sparse spectral filtering. It broadens the scope of application of such GNNs without sacrificing computational costs. The additional experiments conducted during the review time were undertaken without exhaustive hyperparameter or activation-function tuning, suggesting that further optimization could potentially improve our empirical results.

Reviewer_yTRDOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

Motivated by calculus on graphs and the Dirichlet form associated with a given positive weight function, the paper proposes a specific design for learning weighted graph Laplacians. The authors argue that this general approach to enriching the graph diffusion operator can mitigate oversmoothing and oversquashing, and instantiate their method within ChebNet.

Critical strengths
  • The paper is well motivated, and the connection between the proposed weight function and a continuous setting is sound.
Critical weaknesses
  • The experimental section does not support the main claims. There is too little evidence of oversquashing mitigation, and the connection to effective resistance is insufficiently developed: it is expected that certain choices of edge weights can reduce effective resistance, but no bounds relating μ\mu to the Jacobian sensitivity introduced in [1] or to effective resistance [2] are provided.
  • The authors do not discuss why this specific approach to learning edge weights should be preferred over other methods, and no ablations are performed.
Questions for authors
  • Can you test the method on benchmarks specifically designed to assess oversquashing and long-range propagation, such as TreeNeighborsMatch [3] and the ECHO datasets [4]? These would make the oversquashing mitigation argument much more convincing.
  • How does your method perform when compared with a similar approach that learns a weighted Laplacian using a standard edge weight parameterization? Outperforming a simple baseline that takes the scalar outputs from the GCN and passes them through an MLP to get edge weights would provide evidence in favor of your specific parameterization.
  • Does your approach also improve learning on other benchmarks? The experiment on ogbn-proteins is useful, but the manuscript would be substantially improved by testing on more datasets and showing that your approach consistently improves the base architecture.

[1] Understanding over-squashing and bottlenecks on graphs via curvature, ICLR 2022

[2] Understanding Oversquashing in GNNs through the Lens of Effective Resistance, ICML 2023

[3] On the Bottleneck of Graph Neural Networks and its Practical Implications, ICLR 2021

[4] Can You Hear Me Now? A Benchmark for Long-Range Graph Propagation, ICLR 2026

3 comments

We thank the reviewer for the valuable critique points.

Weaknesses

  • We have now added an additional section to our paper addressing the questions on jacobian sensitivity and on resistance distance/commute time. For the latter, we have chosen to study commute time, since it is invariant to uniform rescaling of the weight, unlike the resistance distance. On a barbell graph, we show that a suitable node weighting reduces the commute time between the two cliques. We also derive bounds on Jacobian sensitivity for general graphs and calculate the sensitivity exactly in the linear case at the edge of the receptive field. On the barbell, this exact result shows higher sensitivity across the bottleneck (Section 4.4). We have also added in the experimental section (Appendix Section I “SUPPLEMENTARY EXPERIMENTAL RESULTS”) a comparison between the Jacobian sensitivities of μ\mu-ChebNet and the ones of ChebNet. The result is that the sensitivities are raised between the cliques (interclique) and lowered inside the cliques (intraclique). This shows μ\mu facilitates passing through the bridge bottleneck. We kept the plots of the resistance distances for the barbell graph, where we showed that with the μ\mu-Laplacian, the resistance distance between the two cliques decreases, whereas the intraclique increases, confirming the Jacobian sensitivity experiment (section 5).
  • We have added an explanation in the related work section (Section 2) of why we learn one weight per node. This gives us fewer values to predict than learning a weight for every edge, while our construction yields symmetric edge weights. The resulting Laplacian has the theoretical advantages described below in our answer to the second question. The node weights are predicted by a small GCN, and the resulting operator can be used as a plug in in a downstream model; here, we use ChebNet. We have also added an ablation with and without the learned node weighting on the barbell Jacobian experiment (Appendix Section I, subsection 1), as well as comparisons with GAT on ogbn-proteins (Table 1), Graph Property Prediction (Table 6), and City Networks (Table 7).

Questions

  • Since the initial submission, we have extended the experimental section with several benchmarks that probe long-range propagation, thus oversquashing indirectly. You can notably find in Appendix Section I “SUPPLEMENTARY EXPERIMENTAL RESULTS”, the following benchmarks (subsections 3 to 5): the long-range graph benchmark LRGB Peptides-Func and Peptides-struct, the Graph Property Prediction (diameter, sssp, eccentricity) analogous to ECHO-Synth, the City-Networks (Paris, Shanghai, Los Angeles, London) datasets. We observe that models with μ\mu improve the backbone architecture results and our ChebNet variants present good performance. Nonetheless, following the recommendation, we are currently working on the incorporation of the TreeNeighborsMatch and ECHO datasets. We will include them if they are finalised on time. Last, direct analysis of over-squashing via sensitivity (Jacobian) analysis notably on Barbell graphs datasets was added in sections “4.4 SENSITIVITY AND OVERSQUASHING” “I.1 EXPERIMENTAL SENSITIVITY ANALYSIS WITH THE BARBELL GRAPH TASK”, showing that learned μ\mu increases the influence across the bottleneck.
  • Our method (GCN followed by averaging the representations of node pairs to compute their edge weight) uses this specific edge parametrization first of all to only need to learn one weight per node and not per edge, and to yield a symmetric graph Laplacian. This Laplacian is then used to derive the drift-diffusion decomposition (theorem 2), the spectral bounds (theorem 3), and now the commute times and sensitivity bounds (section 4.4). To learn the edge weights using a MLP for example would not allow us to benefit from the simplicity of a symmetric Laplacian and it would be more computationally costly. It was the intention of the paper to keep this model lightweight. We have also added a short section (section 4.5), where we explained a link to GAT by showing their similar structure.
  • As stated above, we have extended the experimental section with several benchmarks presented in Appendix Section I “SUPPLEMENTARY EXPERIMENTAL RESULTS”, subsections 3 to 5: the long-range graph benchmark LRGB Peptides-Func and Peptides-struct, the Graph Property Prediction (diameter, sssp, eccentricity), the City-Networks (Paris, Shanghai, Los Angeles, London) datasets. Learning with μ\mu improves from the backbone architecture and the ChebNet variants present good performance.

In addition to the theoretical analysis and experimental results presented in our previous response, we have conducted two further experiments specifically addressing your concerns about oversquashing mitigation. First, we thank the reviewer for suggesting TreeNeighborsMatch. We have now evaluated ChebNet and μ\mu-ChebNet on this benchmark, following the experimental setup of Alon and Yahav (2021). The benchmark is designed to control the severity of oversquashing through the problem radius, with larger values corresponding to more challenging settings. Both models achieve nearly perfect accuracy on trees of depths 3 and 4. At depth 5, however, μ\mu-ChebNet achieves a mean test accuracy of 95.86%, compared with 88.53% for ChebNet, with lower variability across the four reported runs (standard deviations of 3.35% and 13.18%). Experiments on deeper trees are still ongoing, and we therefore restrict our reported results to depths 3–5. To further investigate oversquashing mitigation, we also conducted an experiment on two-community stochastic block model (SBM) graphs, progressively reducing the number of edges connecting the communities. We compare ChebNet and μ\mu-ChebNet with the same polynomial order K=7K=7 and 8 layers. Both models therefore have the same theoretical receptive-field radius, allowing us to investigate the effect of learned node weighting on information propagation across the bottleneck. As the bottleneck becomes more restrictive, ChebNet’s test MSE increases sharply, while μ\mu-ChebNet maintains substantially lower error in the most challenging settings. With a single bridge edge, μ\mu-ChebNet achieves a test MSE more than 10 times lower than standard ChebNet. When the communities are more densely connected, the models exhibit comparable performance. Together with the additional Jacobian sensitivity analysis and benchmarks presented in our previous response, these experiments provide further empirical evidence supporting the role of learned node weights in mitigating oversquashing. The new results are included in Appendix I.6 and I.7.

I thank the authors for their careful rebuttal. Since most of my concerns have been addressed, I will raise my score.

Comments on the paper

1 comment

We thank the reviewers for their constructive feedback, which has helped us strengthen the theoretical analysis, clarify the positioning of our contribution, and substantially extend the experimental evaluation. We summarize the main concerns raised and how we addressed them. The recurring comments concerned the positioning of our approach within the existing literature, the theoretical connection to oversquashing, and the need for broader experimental validation.

  • We have expanded our Related Work (Sec. 2) to discuss other learned graph operators and Neural Sheaf Diffusion, among other works. We have clarified how our node-wise parameterization differs from these approaches, emphasizing its lightweight construction and the theoretical properties it enables. We have also established connections to GAT (Sec. 4.5).
  • We have added a theoretical section (Sec. 4.4) on oversquashing, analyzing the sensitivity and the commute time. We derived bounds on Jacobian sensitivity for arbitrary learned Chebyshev filters, established exact results at the boundary of the receptive field for it, and demonstrated both improved sensitivity and commute time across bottlenecks on barbell graphs. 
  • We have also added an experimental study of the Jacobian sensitivities (Appendix I.1), showing that the learned node weighting increases sensitivity between nodes in opposite cliques of a barbell graph.
  • We have considerably extended the experimental evaluation (Appendix I) with the LRGB Peptides-Func and Peptides-Struct benchmarks, Graph Property Prediction tasks (diameter, SSSP, eccentricity), and City Networks (Paris, Shanghai, Los Angeles, London). These additions allow us to evaluate the approach across a broader range of long-range propagation tasks and compare it with additional baselines, including transformers, rewiring methods, state space based, and classical GNNs such as GAT.  Also, we have additional experiments with BernNet and our plugged in Laplacian, showing that LμL_\mu can also benefit other spectral architectures.
  • To further address oversquashing mitigation, we have added two experiments with specifically designed benchmark (SBM and TreeNeighborsMatch, Appendix I.6–I.7) showing the benefits of learning μ\mu as the bottleneck severity increases.

We appreciate that the reviewers have acknowledged several of these improvements. The reviewers indicated that the revisions addressed most of their concerns. We believe that these revisions have substantially strengthened the manuscript, both theoretically and experimentally, and hope that the additional results and clarifications will be taken into consideration in the final assessment.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.