- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies finite graph structural encodings through the algebra of -FWL. It presents an exact algebraic characterization of -FWL refinement and constructs three families of structural dictionaries: polynomial, endpoint, and joint. The authors introduce explicit budgets, analyze the distinction between raw structural information and readout-visible information, and evaluate structural discrimination across graphs and different object domains.
Critical strengths
I appreciate Theorem 1 as a connection between the combinatorial and algebraic perspectives of -FWL. The characterization provides a useful way to understand the refinement process through algebraic operations.
The finite-dictionary analysis is systematic and provides useful observations about channel redundancy, equivalence under changes of complete polynomial bases, and the effects of restricted readouts. In particular, the analysis showing how higher moments can improve mean-readout discrimination without adding raw information is informative.
Critical weaknesses
- Incremental novelty and theoretical role of Theorem 1.
Although I appreciate the conceptual value of Theorem 1, its novelty relative to existing work (cited in the paper) remains somewhat unclear.
Maron et al. (2019) already show how matrix multiplication and polynomial transformations can realize 2-FWL refinement and introduce a generalized -way multiplication closely related to the proposed shared-pivot contraction. Geerts and Reutter (2022) also establish a round-sensitive correspondence between WL distinguishing power and tensor-language computations. The authors appropriately acknowledge these connections, including the work of Puny et al. (2023). I recognize that Theorem 1 establishes the specific fixed-graph equality which is not stated in precisely this form in the cited works. Its proof connects shared-pivot contractions to the joint color-profile counts of -FWL and uses finite polynomial interpolation to recover color-class indicators.
However, I am not fully convinced that this characterization provides a substantial new theoretical insight beyond the established algebraic descriptions of -FWL. In particular, the refinement-round upper bounds for the proposed dictionaries appear to require only . It would be helpful to clarify what additional theoretical consequences follow from the reverse inclusion , and how these consequences contribute to the finite-dictionary framework.
- Significance and explanatory power of the finite-dictionary framework.
The introduction raises an interesting question: how can different graph structural encodings be compared within a common framework?
The proposed budget provides a useful way to organize the selected dictionaries. However, Theorem 1 characterizes the full algebra, whereas Proposition 1 establishes sufficient -FWL membership bounds These bounds limit the distinguishing power of the finite dictionaries, but do not characterize the distinctions they capture or establish general conditions for strict separation between dictionary families.
I recognize that the paper provides several valuable partial comparisons, including monotonicity under channel addition, redundancy results, polynomial-basis equivalence, and readout analysis. The authors also clearly acknowledge that their membership bounds are sufficient rather than tight. Nevertheless, I find the broader theoretical contribution of the framework somewhat limited. It remains unclear to what extent the framework enables researchers to compare or select finite structural encodings beyond organizing their constructions and establishing upper bounds.
Could the authors identify additional theoretical principles that follow from the proposed framework? For example, can it establish conditions under which two finite dictionaries have equivalent or strictly different distinguishing power? Even results under restricted assumptions could help demonstrate its broader significance.
Questions for authors
please address the weaknesses
5 comments
How to interpret prediction. With the same GNNPlus model, joint gains over the walk/endpoint baseline average 2.025 and 0.875 percentage points on PROTEINS_full and ENZYMES. Squaring retained inputs and applying invertible discrete cosine transform (DCT) mixing also change scores without adding information. Checkpoints are selected and scored on the same held-out folds, so comparisons are descriptive. Appendix I reports variation and all references, including those with higher means. Predictive gains alone therefore cannot identify added information as their cause.
Q1 — Please address the weaknesses
W1 explains that the reverse inclusion completes the algebraic reference. W2 gives conditions under which features are equivalent or strictly stronger, and an example where changing the readout recovers a distinction without new information. These provide concrete answers to the requested encoding comparisons and their uses. We ask you to reconsider the framework's contribution on this evidence.
References
- Maron, H., Ben-Hamu, H., Serviansky, H., and Lipman, Y. Provably Powerful Graph Networks. NeurIPS, 2019.
- Geerts, F. and Reutter, J. L. Expressiveness and Approximation Properties of Graph Neural Networks. ICLR, 2022.
- Puny, O., Lim, D., Kiani, B., Maron, H., and Lipman, Y. Equivariant Polynomials for Graph Neural Networks. ICML, 2023.
- Bao, L., Jin, E., Bronstein, M., Ceylan, İ. İ., and Lanzinger, M. Homomorphism Counts as Structural Encodings for Graph Learning. ICLR, 2025.
Finite-encoding comparisons in the revised PDF
We have uploaded the revised PDF. The changes below address the role of Theorem 1 and the comparisons available beyond round upper bounds.
W1 — The role of the algebra (§2.3, p.4). We now state explicitly that Geerts and Reutter (2022) recover Theorem 1 and Proposition 1 after matching the operations. The reverse inclusion completes the characterization on a fixed finite graph; the round bounds and readout identities do not require it. Sections 3–4 compare finite encodings using reconstruction identities, basis changes and explicit separation arguments.
W2 — When features are equivalent or strictly stronger (§3, pp.5–6). Table 1 (p.5) now lists the conditions, conclusions and uses of the comparisons. It includes the existing redundancy result when factors are retained and equivalence under complete, degree-compatible basis changes with the constant retained.
Added Proposition 2 covers positive-degree strongly regular graphs with matching parameters but different four-clique counts. Their complete walk/endpoint feature multisets agree at every degree and moment order; joint features distinguish them with degree-one seeds. Corollary 1 retains this gain with 19 channels on each side by replacing a duplicate. Both studied bases and all ordered triples, including repetitions, are covered; construction costs differ.
W2 — When changing the readout is enough (§4.3, p.7). Added Proposition 3 uses the same ordered-triple domain. On rook/Shrikhande, every separate-channel moment agrees in the original monomial and Chebyshev bases. Yet invertible mixing at degree one, followed by cubing and averaging, separates the graphs. The basis-change result establishes that mixing preserves information and width; the moment calculation establishes the recovered distinction.
We hope these additions help clarify how the results can guide the choice of features and readouts. They identify both a case where increasing degree cannot replace joint features and a case where changing the readout recovers a distinction without adding information.
Thank you for recognizing the encoding and readout analysis. Propositions 2–3 and Corollary 1 are discussion-stage additions.
W1 — Incremental novelty and the role of the reverse inclusion
The reverse inclusion establishes that the full set of allowed operations can reproduce the FWL color classes at the same round on a fixed finite graph (k≥2). The forward direction says every generated feature is constant within those classes. The reverse says the operations can generate an indicator for each class. Together, they specify exactly what the full algebra can distinguish, without guaranteeing a small complete feature set.
Proposition 1 needs only the forward inclusion, and the readout identities have direct proofs independent of the reverse. The reverse inclusion supplies the complete algebraic reference. The finite-feature comparisons in W2 establish which distinctions remain when only particular features or readouts are used.
Matching operations with Geerts and Reutter (2022, GR) recovers Theorem 1 and Proposition 1; the foundations also include Maron et al. (2019) and Puny et al. (2023). Submitted Appendix A extends shared constructions to prescribed finite graph families.
W2 — Can the framework actually compare or guide the choice of finite encodings?
For the studied dictionaries, we establish when features are redundant, when joint features add information, and when a readout change recovers an existing distinction (Table 1). A dictionary is the selected set of feature channels. Products of retained single-endpoint features add no information before pooling. Complete degree-compatible polynomial blocks, with the constant retained, encode the same information under invertible basis changes.
When different features are needed. The baseline records walks and separate endpoint summaries; joint features also count walks meeting at a common vertex. For strongly regular graphs with matching parameters but different four-clique counts, the baseline's complete feature multisets agree at every polynomial degree, while joint separates at degree one. Higher powers reduce to equality/adjacency/nonadjacency types with matching triple counts, and endpoint summaries are constant. Retaining triangle indicators together with joint common-neighbor counts reveals the differing four-clique counts (Section 3.2; Appendix D).
Here Q controls walk-polynomial degree and P controls channelwise powers. At Q=P=1, Corollary 1 replaces the duplicate equality coordinate I21 by the weighted triple common-neighbor count K111. The retained I12 recovers the removed coordinate. This matches 19/19 channels, retains all baseline information and recovers the full 27-channel dictionary. Construction costs differ. Endpoint channels are absent at Q=1, but still fail to separate at higher degrees. Both monomial and Chebyshev bases and all ordered triples, including repeats, are covered.
When a different readout is enough. A feature row lists the channels for one ordered triple. Its multiset retains complete rows and their multiplicities, ignoring row order. On rook/Shrikhande, for both original bases and every finite Q,P≥1:
The last two rows differ because the same column values occur in different combinations within a row. Pooling columns separately discards those combinations; taking higher powers does not restore them. At Q=1,P=3, invertible mixing (I,M)↦(I,I+M) before cubing and averaging recovers the distinction with the same information and 27 channels (Proposition 3; Appendix E). Here I is the identity seed and M the normalized adjacency seed. The 19-channel corollary concerns complete rows rather than this moment readout.
MoSE uses this pair against node-return random walks (Bao et al., 2025). Our comparison connects the added information in complete rows to failure at every original moment order and an explicit readout change that succeeds.
How to interpret object discrimination. Mixed allocates channels to both walk and endpoint features; Wider Powers uses the same width for matrix powers alone. On the same 188 MUTAG graphs, Mixed fully recovers vertex-pair symmetry classes (orbits) on 183 graphs versus 85 for Wider Powers. Full recovery means that no two different classes remain confused. Yet mean pairwise resolution (PR) is near one for both: 0.999996 versus 0.999370. Thus an almost perfect average can hide incomplete recovery on many graphs. Node/edge mean differences are near zero, so pair gains need not transfer across domains. These results follow the stated floating-point protocol (Appendix N.3).