- 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 , 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 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 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 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 (invariant or not) with generically independent outputs is simply ). However, the arguably more difficult and interesting case of global identifiability, i.e. the existence of a continuous injective map 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 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 , dimension of the Stiefel manifold, the fact that the commutant of a symmetric matrix in are rotations in the eigenspaces of , or that polynomials commute with ). I feel that, theory-wise, Prop. 3.7 is a real contribution, however, the map 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 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?
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
Key changes in presentation
Response to weaknesses and questions