acceptodds
Under review as a conference paper at ICLR 2027

The Identifiability of Vertex Signals on Graphs under Quadratic Readouts

Abstract

A readout layer of a graph neural network is a permutation invariant map from vertex signals to some fixed vector space agnostic to the size of the graph. We measure how a readout can fail to locally distinguish a signal in using the dimension of the fibre . In this study, we consider a quadratic readout of the form , where is the adjacency or Laplacian matrix of the graph. We show that if the signal channel dimension is sufficiently large relative to the size of the graph (), and the spectrum of is simple, we can achieve perfect local identifiability for generic (full rank) vertex signals. In contrast, the commonly used sum readout or a graph agnostic quadratic readout has fibre dimension that is non-decreasing with . These observations inform the design of graph neural network architectures, as they demonstrate how information loss in the readout layers can be potentially mitigated with careful consideration of the nonlinearity of the readout, the number of vertex signal channels , and how it relates to the size of the graph .

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph Neural Networks, Graph Readout, Graph Pooling, Spectral Graph Theory, Nonlinear Readout

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_UosKOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper analyzes theoretically how much information the readout layer of a GNN loses by mapping node signals of a graph to a fixed-size vector, by studying local identifiability of the readout via its generic fiber dimension (e.g., fiber dimension zero would mean that a generic signal is locally identifiable from its readout). The analysis distinguishes linear/quadratic and graph-agnostic/informed readouts, where the graph structure is injected via positional encodings in the linear case and a Gram matrix of the signals, weighted by a graph shift operator in the quadratic case, respectively. In the graph-agnostic case, the fibers can be obtained as orbits under an orthogonal group action. For the quadratic graph-informed case, the authors distinguish the wide (number of nodes n ≤ signal dimension d) case from the tall (n > d) case. For the former, they obtain the fiber dimension via identifying fibers as orbits of a subgroup of orthogonal matrices commuting with the graph shift operator; for the latter, by showing that the Jacobian of the readout generically has full rank, and thus a dimension-counting bound is tight. As an implication for GNN design, the paper concludes that under the studied readouts one needs the feature dimension to exceed the number of nodes for local identifiability.

Critical strengths
  • The exposition is relatively clear and easy to follow, and the paper is well-organized (e.g., the results are summarized in table 1 and fig. 1).
Critical weaknesses
  • I feel that the paper does very little to motivate the problem or argue why it is relevant to study this. E.g., already the abstract is quite technical, and it is not made clear throughout the manuscript why local identifiability of the readout should matter for GNNs in practice apart from the vague statement about compression in the introduction.
  • The dependence of the theory on the graph structure is rather shallow, i.e., the graph only enters as a fixed symmetric matrix MM, and the results depend only on its eigenvalue multiplicities, i.e., the analysis uses no specifics of commonly used graph shift operators (GSO) such as the adjacency, combinatorial/normalized Laplacian. The statements would also hold verbatim for any symmetric matrix. More importantly, one crucial ingredient I think the analysis misses is the architecture that produces the signals that are given to the readout. It is well-known that GNNs commonly have expressivity limitations, e.g. MPNNs by 1-WL, so rk(X)\mathrm{rk} (X) is at most the number of WL colors, or more generally, any permutation-equivariant encoder assigns identical rows to nodes related by graph automorphisms, so the generic full-rank assumption on XX fails on every graph with a non-trivial automorphism group. While the effect of this on the GSO spectrum is briefly discussed in sec. 4, the analysis seems to miss that this also affects XX itself.
  • The introduction motivates the problem with permutation invariance of the readout. However, permutation invariance is a discrete symmetry and it seems to me that this is largely irrelevant to the local and analytical quantity the paper analyzes (i.e., the generic fiber dimension of any map Rn×d→Rm\mathbb{R}^{n \times d} \to \mathbb{R}^m (invariant or not) with generically independent outputs is simply nd−mnd-m). However, the arguably more difficult and interesting case of global identifiability, i.e. the existence of a continuous injective map Rn×d/Sn→Rm\mathbb{R}^{n \times d} / S_n \to \mathbb{R}^m is mostly a topological question and has already been addressed by the works [1, 2] which the authors cite but only shallowly engage with in l. 142-149. Even if the fiber dimension is zero, the fiber still consists of 2n2^n points from sign flips of the GSO eigenvectors (e.g., [3]) which the paper doesn't identify as such or relate to the literature.
  • There are no experiments that would show that any of the “implications for GNN design” are relevant, at least some experiments on synthetic graphs could support the design claims.
  • A lot of the theory is well-known but reproved or elementary dimension counting (e.g. first fundamental theorem of O(n)O(n), dimension of the Stiefel manifold, the fact that the commutant of a symmetric matrix MM in O(n)O(n) are rotations in the eigenspaces of MM, or that polynomials p(M)p(M) commute with MM). I feel that, theory-wise, Prop. 3.7 is a real contribution, however, the map Q↦Q⊤MQQ \mapsto Q^\top M Q on the Stiefel manifold it concerns is classical (e.g., [4], not cited). Of course, substantial theoretical novelty is not necessary for an ICLR paper if, e.g., the theory explains some empirical phenomenon, but for a purely theoretical paper I am missing a result that is sufficiently new, relevant, or surprising to clear the bar for acceptance.
  • Also, the main “practical” takeaway that feature dimension should scale with the number of nodes is not new ([5,6,7], which the paper all cites). If I am not mistaken, the main story is even somewhat circular: The introduction motivates the issue as “compression” but then the conclusion the paper draws in l. 450-454 is to just not be in the regime where compression occurs, which the authors themselves contend might be “unreasonable” (l. 453).

Miscellaneous (i.e., did not affect the score):

  • Margins are violated, please check the formatting instructions.
  • I didn’t see the readout (1⊤X,X⊤X,X⊤MX)(1^\top X, X^\top X, X^\top M X) in l. 14 (abstract) being analyzed anywhere in the paper.

[1] Tal Amir, Steven J. Gortler, Ilai Avni, Ravina Ravina, and Nadav Dym. Neural injective functions for multisets, measures and graphs via a finite witness theorem. NeurIPS 2023.

[2] Nadav Dym and Steven J. Gortler. Low-dimensional invariant embeddings for universal geometric learning. Foundations of Computational Mathematics, 25:375–415, 2025.

[3] Derek Lim, Joshua Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra, Haggai Maron, Stefanie Jegelka. Sign and Basis Invariant Networks for Spectral Graph Representation Learning. ICLR 2023.

[4] Ky Fan and Gordon Pall. Imbedding conditions for Hermitian and normal matrices. Canadian Journal of Mathematics, 1957.

[5] Edward Wagstaff, Fabian Fuchs, Martin Engelcke, Ingmar Posner, and Michael A. Osborne. On the limitations of representing functions on sets. ICML 2019.

[6] Edward Wagstaff, Fabian B. Fuchs, Martin Engelcke, Michael A. Osborne, and Ingmar Posner. Universal approximation of functions on sets. JMLR, 2022.

[7] David Buterez, Jon Paul Janet, Steven J. Kiddle, Dino Oglic, and Pietro Lio. Graph neural networks with adaptive readouts. NeurIPS 2022.

Questions for authors
  • What do you see as the main theoretical contribution?
  • What are the novel practical takeaways for graph ML, given that the fact that the number of features should scale with nodes has already been pointed out by prior work (see weaknesses)?
  • Have you run any experiments with GNNs (e.g., on synthetic data/tasks) to support the design implications of the theory?
  • Why is local identifiability the right measure of “compression” here?
1 comment

Thank you for your detailed and thoughtful comments, and apologies for the delay in completing the revisions. We have rewritten the article after reflecting on comments from all reviewers, and we are grateful for the comments that has led to improvements in our work.

Key updates in results

  1. Theorem 3.2: An upgrade of the main theorem for the generic fibre dimension of the map (X^\top X , X^\top M X) for all n,dn,d, from an lower bound to an equality beyond the simple spectrum case, as a function of the multiplicities of the eigenvalues of M.
  2. Proposition 4.1: The fibre dimension in the case where signals are constant on Weisfeiler Leman colour equivalent classes of vertices.
  3. Section 4 and Table 2: Evaluation of the theoretical generic fibre dimension on benchmark datasets.

Key changes in presentation

  1. Following reviewer suggestions, we have restructured the sections to spotlight the key theoretical contribution, which is Theorem 3.2. Known classical results for the sum/linear, and gram readouts, are now filed under the Mathematical Background section.
  2. Addition of section 4 on GNN outputs
  3. A more extensive discussion section that discusses the quadratic readouts in a broader applicational context, given new results.

Response to weaknesses and questions

  1. The main theoretical contribution is Theorem 3.2, which we have strengthened significantly from the previous version (prop 3.7).
  2. The new proposition 4.1 addresses the theoretical case of signals that are generated by message passing GNNs. We show in table 2 on graphs across benchmark datasets that the fact that signals are low rank in this particular way in fact reduces the fibre dimension compared to the generic case, as the eigenvalue multiplicities of the adjacency/Laplacian matrix of the quotient graphs under WL equivalence is often much lower than that of the original graph itself.
  3. We believe that the generic fibre dimension gives us a principled numerical quantity to compare the information loss due to different maps. This allows us to quantify not only whether a map is locally injective, but also how far a map is from being locally injective, which is also a valid question to explore.
  4. We ran some preliminary experiments that show did not show conclusive improvement of q\mathbf{q} over s,g\mathbf{s}, \mathbf{g} on a limited class of regression/classification benchmark datasets. This is maybe due to the learnt MPGNN representation being powerful enough to overcome to limitations of the readout, or the bottleneck in the performance being elsewhere in the architecture rather than being in the readout. Unfortunately, we did not have enough time to extract robust scientific observations from our preliminary experiments, and to present them at a fitting standard, and thus we decided not to include these results. We acknowledge this limitation in this regard in the 'Limitations' section of the Discussion section.
Reviewer_YvX2OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies the information lost by fixed linear and quadratic graph readouts through the generic dimension of their fibres. It characterizes the fibres of the Gram readout and its combination with fixed linear measurements using orthogonal-group orbits. Its main result is that, for a fixed symmetric graph matrix with simple spectrum, the joint readout has generic fibre dimension max{d(n−d−1), 0}. Thus generic signals become locally identifiable at d ≥ n−1. For d ≥ n, the paper also characterizes the dependence on eigenvalue multiplicities and shows that adding polynomial functions of M does not further distinguish signals. The contribution is theoretical, with proofs in the appendix.

Critical strengths

The exact dimension formula is the main contribution. The transition at d = n−1 is sharper than simply observing that quadratic statistics contain more information than a sum. The constructive Jacobian argument in Appendix A.1 establishes attainability of the dimension bound in the tall regime, rather than relying on an equation count. This goes beyond the Gram-type pooling studied by Wang and Ji [1]. It also answers a different question from the global injectivity of neural multiset embeddings in Amir et al. [2]: the result gives an exact local fibre dimension for specified quadratic measurements. Both works are already cited.

The spectral characterization gives a useful account of the ambiguity that remains. In the full-row-rank regime, orthogonal symmetries within eigenspaces yield an explicit multiplicity-dependent ambiguity, including 2ⁿ solutions for simple spectrum. The same argument explains why adding polynomial filters of M cannot remove it.

Critical weaknesses

The comparison with sum pooling also uses different output budgets: q has d(d+1) scalar coordinates, whereas sum pooling has d. A lower fibre dimension alone does not separate the benefit of the quadratic structure from that of a larger representation. The tall-regime result does attain the dimension-counting lower bound for its output space. What remains unclear is why this readout should be preferred to alternatives with comparable output size.

Several statements need correction. Equation (8) is not strictly smaller at d = 1, where both dimensions are n−1; Equation (11) is not strict when M is proportional to the identity. Proposition 3.6 states d ≤ n, although its full-row-rank assumption and proof require d ≥ n, and the discussion also reverses the regime for the 2ⁿ-point fibre. These affect the comparisons and the scope of the proposition, but appear repairable from the surrounding arguments. I do not see them as undermining the main simple-spectrum formula.

Questions for authors

Can you give a concrete readout-design implication of the fibre characterization? A nontrivial example connecting reduced ambiguity to a task-relevant distinction, a theoretical comparison at a matched output budget, or a small targeted validation would help. Any one of these could address my significance concern; a full architecture benchmark is not needed.

Please clarify the conditions for the strict inequalities (8)–(11), correct the regime in Proposition 3.6 and Section 4, and distinguish generic signals from merely full-rank signals in the tall regime.

[1] Wang and Ji. Second-Order Pooling for Graph Neural Networks.

[2] Amir et al. Neural Injective Functions for Multisets, Measures and Graphs via a Finite Witness Theorem.

1 comment

Thank you for your detailed and thoughtful comments, and apologies for the delay in completing the revisions. We have rewritten the article after reflecting on comments from all reviewers, and we are grateful for the comments that has led to improvements in our work.

Key updates in results

  1. Theorem 3.2: An upgrade of the main theorem for the generic fibre dimension of the map (X^\top X , X^\top M X) for all n,dn,d, from an lower bound to an equality beyond the simple spectrum case, as a function of the multiplicities of the eigenvalues of M.
  2. Proposition 4.1: The fibre dimension in the case where signals are constant on Weisfeiler Leman colour equivalent classes of vertices.
  3. Section 4 and Table 2: Evaluation of the theoretical generic fibre dimension on benchmark datasets.

Key changes in presentation

  1. Following reviewer suggestions, we have restructured the sections to spotlight the key theoretical contribution, which is Theorem 3.2. Known classical results for the sum/linear, and gram readouts, are now filed under the Mathematical Background section.
  2. Addition of section 4 on GNN outputs
  3. A more extensive discussion section that discusses the quadratic readouts in a broader applicational context, given new results.

Response to Weaknesses and Questions

  1. (W1 + Q1) We acknowledge the reviewer's comments, and included a paragraph in the Discussion ('Limitations') that compares the q\mathbf{q} readout to the Amir et al neural moments readout in terms of the budget. The comparison between the sum and q\mathbf{q} readout at fixed output budget is difficult, as fixing the output domain necessitates different signal dimension domains as well. Nonetheless, we include a synthetic example in Discussion ('Comparing quadratic readouts to the sum readout') to show a case where we artificially force the input and output dimensions to match; in this situation, the amount of information one loses by imposing symmetry through a sum readout on n×d(d+1)n \times d(d+1) signal is equivalent to throwing away d2d^2 channels before applying q\mathbf{q} to the remaining dd channels, demonstrating the greater efficiency of q\mathbf{q} at mitigating information loss due to imposing symmetry invariance.

  2. (W2 + Q2) The errors are now fixed in the new manuscript: the comparisons of readout dimensions are moved to the Discussion section, where the conditions for strictness are specified. The typo d≤nd \leq n in Proposition 3.6 is now corrected. The new section 3.2.1, equation (17), specifies the set AM\mathcal{A}_M that distinguishes generic signals from merely full-rank signals in the tall regime.

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

This paper investigates the identifiability of vertex signals under linear and quadratic readout operators in graph neural networks. The paper is purely theoretical and provides mathematical proofs but offers no empirical evaluation on graph-learning benchmarks. The authors quantify information loss using the generic dimension of the fibres associated with different readout functions. The paper characterizes the fibres of sum- and Gram-based readouts and derives an explicit formula for the generic fibre dimension of a graph-informed quadratic readout. The main conclusion is that, when the graph matrix has a simple spectrum, the quadratic readout becomes locally identifiable for generic vertex signals when the feature dimension is sufficiently large.

Critical strengths

S1. The paper studies how much information is lost during graph readout, a problem often overlooked in GNN research. Using fibre dimension to measure this loss is an interesting perspective.

S2. The analysis shows how the spectrum of the graph matrix affects identifiability. The distinction between simple and repeated eigenvalues helps explain when graph-informed readouts can reduce ambiguity.

S3. The authors admit that they used generative AI to develop theoretical ideas, assist with proofs, formulate mathematical claims, and draft portions of the manuscript. They also state that they independently verified the AI-assisted work.

Critical weaknesses

W1. The major concern is that the paper does not provide any empirical results, even on a small synthetic graph dataset. It is suggested to evaluate whether the proposed graph-informed quadratic readout improves representation quality or downstream tasks such as node classification and link prediction. Otherwise, it is unclear to readers whether reduced fibre dimensions can translate into improved predictive performance on real graph datasets.

W2. Another concern is still about the practical usage of this work. The main identifiability result relies on a simple graph-matrix spectrum and a feature dimension approximately as large as the number of vertices. These assumptions may not hold for real-world graphs or learned GNN representations. Are the assumptions in this work general enough?

W3. For Proposition 3.6, I am confused that it supposes d\leq n. But rank X=min(n,d)=n; does this mean that d is actually no smaller than n? They seem to contradict each other?

W4. In Equation 8, the inequality \delta(g)<\delta(s) does not always hold. \delta(s) is computed using both d and n, but \delta(g) is obtained only from n. For example, both dimensions equal one when (n=2) and (d=1). The authors should specify the conditions under which the strict inequalities hold.

Questions for authors

Please refer to the weakness

1 comment

Thank you for your detailed and thoughtful comments, and apologies for the delay in completing the revisions. We have rewritten the article after reflecting on comments from all reviewers, and we are grateful for the comments that has led to improvements in our work.

Key updates in results

  1. Theorem 3.2: An upgrade of the main theorem for the generic fibre dimension of the map (X^\top X , X^\top M X) for all n,dn,d, from an lower bound to an equality beyond the simple spectrum case, as a function of the multiplicities of the eigenvalues of M.
  2. Proposition 4.1: The fibre dimension in the case where signals are constant on Weisfeiler Leman colour equivalent classes of vertices.
  3. Section 4 and Table 2: Evaluation of the theoretical generic fibre dimension on benchmark datasets.

Key changes in presentation

  1. Following reviewer suggestions, we have restructured the sections to spotlight the key theoretical contribution, which is Theorem 3.2. Known classical results for the sum/linear, and gram readouts, are now filed under the Mathematical Background section.
  2. Addition of section 4 on GNN outputs
  3. A more extensive discussion section that discusses the quadratic readouts in a broader applicational context, given new results.

Addressing comments

  1. (W1) We ran some preliminary experiments that show did not show conclusive improvement of q\mathbf{q} over s,g\mathbf{s}, \mathbf{g} on a limited class of regression/classification benchmark datasets. This is maybe due to the learnt MPGNN representation being powerful enough to overcome to limitations of the readout, or the bottleneck in the performance being elsewhere in the architecture rather than being in the readout. Unfortunately, we did not have enough time to extract robust scientific observations from our preliminary experiments, and to present them at a fitting standard, and thus we decided not to include these results. We acknowledge this limitation in this regard in the 'Limitations' section of the Discussion section.
  2. (W2) Proposition 4.1 now addresses this question explicitly: as a k-layer MPGNN has vertex features that are constant on WL colour-refinement classes of vertices, effectively the role of the number of vertices for such signals is replaced by the number of colour classes, so d = number of classes suffices to achieve local identifiability on such datasets (assuming simple spectrum of the quotient graph). In Table 2 we show that local identifiability is often achievable on benchmark datasets, due to the quotient graph having lower eigenvalue multiplicities.
  3. (W3) The typo is now fixed in the proposition (now Proposition 3.7). d≤nd \leq n is now corrected to n≤dn \leq d.
  4. (W4) The explicit condition when the inequality is strict is now fixed in line 468. Note that δ(g)\delta(\mathbf{g}) depends on dd as well in the tall regime where d≤nd \leq n.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.