acceptodds
Under review as a conference paper at ICLR 2027

Which Communication Routes Help a GNN? A Graphon Theory of Task-Conditioned Edge Sensitivity

Abstract

Which communication routes in a graph neural network actually help its task, and does the answer remain meaningful when the same population is represented by graphs of different sizes or by different random samples? On a single finite graph, this question can be answered locally by differentiating the task loss with respect to edge weights. Across graphs, however, those derivatives live in different coordinates and need not be directly comparable. We use graphons to make this question tractable at the population level. A graphon provides common coordinates for communication in large dense graphs, allowing the local value of changing a route to be represented by a signed task-conditioned sensitivity field. For nonlinear residual message passing, we derive this field exactly: each route is valued through the interaction between the representation difference available to cross it and a backward signal describing what the task needs. We prove that the complete field is stable under graphon cut convergence. In particular, dense Bernoulli graphs may remain noisy edge by edge in raw , while their sensitivities converge in expected at rate to those of the corresponding mean communication kernel. Under stronger aligned assumptions, finite communication updates also track a common population trajectory over fixed horizons. Experiments separate structural stability from operational usefulness. Synthetic and CiteSeer-calibrated studies show stable sensitivities despite persistent edge noise, and a fixed-forward diagnostic shows that changing the task alone can change communication preferences. A controlled routing problem shows that route-specific forward–backward alignment can matter for intervention, whereas on METR-LA much of the transferred intervention benefit is captured by a simpler signed magnitude score. Together, these results show when task-conditioned communication has a coherent population meaning while separating that guarantee from how much task-specific detail is useful in a particular model.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph limits, Graphons, Graph Neural Networks, Message Passing, GNN interpretability

Reviews

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

This paper presents a graphon-based theory to analyze the effect of varying message-passing communication routes between nodes on the task objective across graphs of different resolutions.

Critical strengths

The paper presents a novel question and opens the doors to study the alignment of the graph structure with the task objective in GNNs through the lens of graphon theory.

Critical weaknesses

The effect of structural variance in the graph population that affect GNN training and performance for example in terms of spectral properties and homophilic vs. heterophilic tendencies is not explored. Not necessarily theoretical analysis, but even a discussion supported empirically could be useful in understanding situations when the stability holds vs. when it does not and the potential underlying reason a particular communication route is more aligned with a task.

Questions for authors

What role does node feature separability play in this analysis?

--- Post Rebuttal Discussion --- The additional experiments provide further insights into how changing tasks affects performance on graphs with varying assortativity in the structure and different class-distinguishability levels of node features. Therefore, I have raised my score to 3.

Reviewer_43U8OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The main contribution of the paper is a theoretical analysis of edge sensitivity in graph neural networks (GNNs) conditioned on the task. In particular, the paper goes beyond the finite graph setting and presents the analysis at population level using graphon theory. Theoretical results are validated using empirical experiments.

Critical strengths
  • The paper tackles an important theoretical issue in GNNs at population level;
  • The analysis framework based on graphon theory is appropriate and intuitive;
  • The analysis of the alignment between communication and task signals is particularly interesting and provides useful insights.
Critical weaknesses
  • One main weakness is the presentation and clarify of the paper need to be improved. For example: in Sec. 3 no definition of the object RR (e.g. its dimensions) and its interpretation are provided, and CyhC_{yh} and ChC_h appear undefined below Eq.(5); the DD in Eq.(8) and Eq.(10), and DVD_V in Eq.(12), should be properly defined; the inner product in Eq.(10) should be properly discussed. In general, given the paper is relatively mathematically dense, interpretations and discussions will help the reader appreciate the ideas presented.
  • The experiments section should also provide more clarify. For example, what are the tasks under consideration? Without this, it is difficult to understand the intuition behind the alignment between communication and task signals in these cases, which I believe is the key idea of the paper. Delegating necessary details to Appendix is in my view not helpful in terms of understanding (the tasks are not clear even after reading Appendix). Also, please make sure the figures are referenced in the text explicitly, so that the reader can follow which result is being discussed.
  • It is unclear what the implications of the theoretical results are: can they inform the training process of GNNs, or defence against adversarial perturbation in practice? These should be properly discussed to justify the value of the theoretical results.
Questions for authors
  • How tight are the theoretical bounds derived in the paper, can the authors comment on that?
  • Am I right that the paper focuses on node classification as the task? If yes, would homophily/heterophily be a useful axis to exam communication-task alignment? Also, can the analysis be generalised to other graph ML tasks such as graph classification?
Reviewer_BUcnOpenReview ↗
Rating
2
Confidence
1
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper establishes a continuous mathematical framework using Graphon theory to quantify the sensitivity of each edge in GNNs to a specific tas. The authors also prove that this sensitivity can remain stable in graphs of different scales and random sampling.

Critical strengths

The mathematical derivation of this paper (i.e., backpropagation and operator estimation in continuous space) is solid.

Critical weaknesses
  1. The author mentioned in Sec. 6.5 that better gains can be achieved solely through a simple signed magnitude score, which means there is a lot of evidence that route-specific angular coupling does not provide additional gains.

  2. Graphon theory is naturally applicable to dense graph sequences. The stability of the theorem in this article depends on this assumption, but complex networks that are highly valuable in the real world are often highly sparse. Although the author mentioned sparse tools such as Graphops in Related Work, the mathematical foundation of this paper does not address the stability of structural derivatives in sparse environments, which limits its generalization significance in practical scenarios.

Questions for authors

Could the authors provide an experimental comparison using end-to-end joint training (don't use fixed feature parameters)?

Why do you need to divide the abstract into three paragraphs? This is the first time I have seen this format.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.