acceptodds
Under review as a conference paper at ICLR 2027

Graph Structural Encodings from -FWL Algebra: Operations, Budgets, and Readouts

Abstract

Structural encodings supply graph statistics to learning models, yet the field lacks a common language for comparing them: a new channel family is proposed, a gain is reported, and it is rarely clear whether the gain reflects new structural information or only better access to information already present. This paper supplies that language for -dimensional folklore Weisfeiler–Leman refinement (-FWL). On a fixed finite graph we show that each refinement round is generated exactly by pointwise operations and contractions whose replacement branches share a single pivot, and we build three dictionary families on this operation: polynomial, endpoint, and joint channels. Each family carries an explicit budget (degree , tuple order , retained objects , moment ) with sufficient refinement-round membership bounds, so constructions are compared in a common currency rather than by channel count. We then separate what an encoding contains from what a readout can see: channelwise powers are injective on exact vectors and multisets, adding no raw distinction, yet the same expansion changes what mean pooling observes, and every joint triple first moment collapses to on equal-size regular graphs of minimum degree at least one. Graph-pair experiments on BREC and within-graph experiments on ZINC, QM9, OGB, LRGB, and TU graphs evaluate nodes, edges, and vertex pairs against automorphism orbits at matched width; endpoints combined with powers improve pair discrimination on four TU datasets with 95% intervals above zero, while node and edge changes are smaller and can reverse. We report unresolved comparisons alongside averages so that high capacity is not mistaken for full recovery. Operations, budgets, readouts, and object domains jointly determine the distinctions an encoding exposes, and greater discrimination alone does not establish a downstream benefit.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph structural encodings, Weisfeiler–Leman expressivity, Higher-order graph representations

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_wPZcOpenReview ↗
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 kk-FWL. It presents an exact algebraic characterization of kk-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 kk-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
  1. 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 kk-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 Hℓ=Wℓ,H_\ell=W_\ell, 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 kk-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 kk-FWL. In particular, the refinement-round upper bounds for the proposed dictionaries appear to require only Hℓ⊆WℓH_\ell\subseteq W_\ell. It would be helpful to clarify what additional theoretical consequences follow from the reverse inclusion Wℓ⊆HℓW_\ell\subseteq H_\ell, and how these consequences contribute to the finite-dictionary framework.

  1. 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 (Q,k,m,P)(Q,k,m,P) provides a useful way to organize the selected dictionaries. However, Theorem 1 characterizes the full algebra, whereas Proposition 1 establishes sufficient kk-FWL membership bounds Dseed⊆WL,Dexplicit⊆WL+1.\mathcal D_{\mathrm{seed}}\subseteq W_L,\quad \mathcal D_{\mathrm{explicit}}\subseteq W_{L+1}. 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
AuthorsOpenReview ↗

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≥2k\ge2). 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 QQ controls walk-polynomial degree and PP controls channelwise powers. At Q=P=1Q=P=1, Corollary 1 replaces the duplicate equality coordinate I21I_{21} by the weighted triple common-neighbor count K111K_{111}. The retained I12I_{12} 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=1Q=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≥1Q,P\ge1:

Exact representation or readoutAcross the two graphs
Seed-plus-endpoint feature multisetEqual
Joint-augmented feature multisetDifferent
Means of each augmented channel's powersEqual

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=3Q=1,P=3, invertible mixing (I,M)↦(I,I+M)(I,M)\mapsto(I,I+M) before cubing and averaging recovers the distinction with the same information and 27 channels (Proposition 3; Appendix E). Here II is the identity seed and MM 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).

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.
AuthorsOpenReview ↗

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.

Reviewer_baKbOpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

The paper proposes an algebraic framework for structural encodings for graph learning, so that constructed features can be related to the k-WL test in terms of power. Their characterization is algebraic, troiugh pointwise operations and shared-pivot contractions, and lead to three families of features: polynomial channels (normalized adjacency matrix powers), endpoint channels capturing information between pairs of vertices and joint channels to express higher-order relations. Authors establish upper bounds on the expressive powers of these features in terms of rounds for the folklore version of k-WL, and then analyze how different readout mechanisms preserve or discard structural information. Finally, they experimentally evaluate the distinguishing power of the proposed encodings on BREC and several real-world graph datasets, measuring their ability to distinguish graphs, nodes, edges, and vertex pairs. Their results suggest that combining different feature families can improve structural discrimination, particularly for vertex pairs, although these improvements do not consistently extend to nodes or edges.

Critical strengths
  • A strength of the paper is its attempt to distinguish between the information contained in an encoding and the information preserved by its readout. Authors refine their analysis of expressive power by considering not only which structural features are computed, but also how those features are pooled.
Critical weaknesses
  • The paper is very difficult to read. Authors build up a notation-heavy paper right from the start, and after finishing the first read It was not clear at all whether all this notation was actually necessary.
  • The theoretical novelty of the expressivity analysis is unclear. As authors themselves cite, Geerts and Reutter (ICLR 2022) already provide a tensor-language characterization that bounds the distinguishing power of graph computations through the number of indices and nesting depth of summations. The proposed polynomial and joint channels can be expressed directly in this language, from where we would obtain ever stronger upper bounds related to the combination of these structural encodings + the underlying message-passing model.
Questions for authors

Please clarify how Proposition 1 and Theorem 1 provide results beyond what can be shown in the framework of Geerts and Reutter 2022.

6 comments
AuthorsOpenReview ↗

Thank you for the feedback. We clarify the comparisons and their relationship to Geerts and Reutter (2022, GR). Propositions 2–3 and Corollary 1 are discussion-stage additions.

W1 — Readability and the role of notation

We now explain the central comparisons through one graph pair before relying on the notation. The baseline records walk statistics and separate endpoint summaries. Joint features also count walks meeting at a common vertex.

Every triangle in the rook graph has one common neighbor; a Shrikhande triangle has none. The joint-augmented representation records the triangle and its common-neighbor count in the same feature row. Walk/endpoint features miss this difference at every degree. Pooling each augmented channel separately can also lose the association, even though the full rows distinguish the graphs (Figures 1–3; Sections 3.2 and 4.3). Table 1 summarizes the conditions and uses.

The two budgets answer different questions: QQ increases the polynomial degree of walk features; PP increases the powers of each feature used in pooling. For example, (M2)uv(M^2)_{uv} sums weighted two-step walks, whereas (Muv)2(M_{uv})^2 squares one entry. Section 2.2 and Appendices C.1/C.6 give definitions and index ordering.


W2 — Contribution to graph structural encodings

The results identify when adding features is necessary and when changing the readout is sufficient for the studied dictionaries. Submitted p.6 establishes that endpoint products are redundant when their factors are retained, complete degree-compatible polynomial bases preserve information, and monomial joint means fail on equal-size positive-degree regular graphs over all ordered triples.

The revision adds two comparisons:

  • Insufficient features. For strongly regular graphs with matching parameters but different four-clique counts, complete walk/endpoint feature multisets agree at every polynomial degree. Joint features distinguish at degree one (Proposition 2). Higher matrix powers reduce to combinations of the identity, adjacency and all-ones matrices; endpoint summaries are constant and triple-pattern counts match. Raising degree cannot fix this baseline failure.
  • Information lost by pooling. On rook/Shrikhande, the complete joint-augmented rows differ, but each column separately has the same value distribution. Averaging any power of each column therefore fails to distinguish the graphs. Mixing columns before cubing and averaging succeeds at Q=1,P=3Q=1,P=3, without adding information or width (Proposition 3). Here changing how existing features are combined is enough.

Both comparisons use all ordered triples, including repeats. Failures hold in the monomial and Chebyshev bases. Recovery uses (I,I+M)(I,I+M), where II is the identity and MM the normalized adjacency matrix. Corollary 1 replaces a duplicate baseline coordinate to retain the strict gain with 19 channels on each side at Q=P=1Q=P=1. The full augmentation has 19/27 channels, and the readout comparison keeps 27 throughout. Construction costs differ (Section 2.2).

Finite encoding comparisons already exist (Black et al., 2024; Flora et al., 2026), and MoSE uses this graph pair against node-return random walks (Bao et al., 2025). Our comparisons establish failure at every degree for the specified complete baseline, then show why every original channelwise moment misses the added joint information and how mixing makes it visible.

Exact calculations check these mechanisms. Object experiments separately examine which domains benefit. Prediction keeps GNNPlus fixed and records positive average joint gains over the stated baseline on both datasets. Squaring retained inputs and invertible DCT mixing also change scores without adding information. Checkpoints are selected and scored on the same held-out folds, so these prediction comparisons are descriptive (Section 5; Appendix I).

Q1 — What do Theorem 1 and Proposition 1 provide beyond GR?

Both results can be recovered from GR after matching operations. They provide the algebraic reference and sufficient round bounds; W2 gives the additional comparisons of finite feature sets and readouts. Equality and adjacency predicates generate the initial color indicators; pointwise operations provide polynomial closure; summing replacement factors over one shared vertex gives pivot contraction (GR Appendices C and D.2; revised Section 2.3 and Appendix A).

The equivalence holds on a fixed finite graph, k≥2k\ge2. Proposition 1 gives sufficient round bounds, which need not be tight or make a selected feature set complete.

For a model-specific upper bound, the encoding and model must be analyzed together. Consider exact, unlabelled polynomial/endpoint pair features EE, followed by a shared pointwise map ρ\rho and graph-level summation: Fρ(G)=∑u,vρ(E(u,v))F_\rho(G)=\sum_{u,v}\rho(E(u,v)). Including feature preprocessing, this computation uses at most three indices in GR's language and is bounded by stable 2-FWL. Other backbones require their own expressions; a strictly tighter bound is not automatic (Section 5.1).

Revised Proposition 4 (submitted Proposition 2) answers a different question: if a model can construct the added channels from the seeds, precomputing those channels does not enlarge its unrestricted function class. This assumes exact construction, retention of intermediate states, composition and seed selection, with a fixed head and unrestricted finite depth/width (Appendix F).

We ask you to reconsider the contribution in light of W2's explicit equivalence, separation and readout comparisons.

References

  • Geerts, F. and Reutter, J. L. Expressiveness and Approximation Properties of Graph Neural Networks. ICLR, 2022.
  • Black, M., Wan, Z., Mishne, G., Nayyeri, A., and Wang, Y. Comparing Graph Transformers via Positional Encodings. ICML, 2024.
  • Flora, J., Black, M., Wong, W.-K., and Nayyeri, A. Understanding Truncated Positional Encodings for Graph Neural Networks. ICML, 2026.
  • Bao, L., Jin, E., Bronstein, M., Ceylan, İ. İ., and Lanzinger, M. Homomorphism Counts as Structural Encodings for Graph Learning. ICLR, 2025.

Thanks for working out this examples. I think both weaknesses still stand. For W1, you added a running example but the notation is still heavy, and I still believe a serious effort must be done to improve the paper presentation. For W2, you do improve results that go beyond GR22, but these are not done in terms of a general methodology (which was the original goal of the paper as I understand) but rather separate analysis. For example, I don't see how the algebra is used at all for Proposition 2.

Reviewer_kbenOpenReview ↗
Rating
4
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper develops a finite-budget framework for graph structural encodings using k-FWL as a reference. The central algebraic result shows, on a fixed finite graph, that each k-FWL refinement round is generated by pointwise algebra together with contractions whose replacement branches share a common pivot. The paper then derives polynomial, endpoint, and joint dictionary families with explicit budgets and sufficient refinement-round membership bounds. A second theme separates information contained in an encoding from information visible to a restricted readout: channelwise powers can be injective on exact vectors/multisets while changing mean-pooled statistics, and a joint-triple first-moment construction collapses on regular graphs.

Critical strengths
  1. The paper provides a useful conceptual decomposition that is often missing in structural-encoding work: which operations create distinctions, what finite budget is required, what object domain receives the features, and which distinctions survive a particular readout. The shared-pivot formulation gives a coherent language for comparing polynomial, endpoint, and joint statistics, and the manuscript is unusually explicit about the fixed-graph/non-uniform scope of Theorem 1 and the fact that the round bounds are sufficient rather than tight.

  2. The empirical study is diagnostic rather than leaderboard-driven. It matches channel width in key object-domain comparisons, reports node/edge/pair behavior separately, and retains unresolved comparisons instead of converting them into optimistic averages. The broad set of datasets plus the released code/protocol details make the empirical conclusions more credible.

Critical weaknesses
  1. The novelty boundary with prior polynomial/tensor/algebraic characterizations of WL/FWL is still somewhat unclear. Theorem 1 uses finite interpolation on each fixed graph to recover refinement partitions, so the construction is non-uniform and the polynomial degree can depend on the graph. Prior work already connects higher-order WL to polynomial/tensor operations and equivariant bases. I believe the explicit “shared pivot + finite budget + readout” organization is useful, but the paper should sharpen which theorem-level capability is genuinely new rather than a reformulation of known algebraic expressivity results. Relatedly, Proposition 1 gives only sufficient round-membership bounds, not tight finite-budget characterization or strict separations.

  2. The empirical evidence stops at structural discrimination. Section 6.3 explicitly says the paper does not rerun or score downstream prediction, and the BREC deterministic comparisons depend on float32 features, rounding/tolerances, and no relabeling checks. I appreciate the transparency, but for an ICLR paper motivated by structural encodings for learning, at least one controlled downstream experiment with the same backbone/compute budget would make the practical significance much clearer.

Questions for authors
  1. Can the authors state more sharply what Theorem 1 contributes beyond existing tensor/polynomial characterizations of k-FWL (e.g., which operation, equivalence, or finite-budget statement is not already implied by prior frameworks)? Is graph-dependent interpolation essential, or is any useful graph-family-uniform bound available?
  2. Can the sufficient round-membership bounds be complemented by a nontrivial lower bound or strict separation showing when one finite dictionary provably contains distinctions another cannot access at the same budget?
4 comments
AuthorsOpenReview ↗

Thank you for recognizing the encoding decomposition and comparisons.

W1 — Novelty of the algebraic characterization and sufficient bounds

Theorem 1 and Proposition 1 can be recovered from Geerts and Reutter (2022, GR) after matching the operations. Our encoding analysis establishes which finite feature choices add information and which readouts preserve it. The shared-pivot operation builds on Maron et al. (2019).

Submitted p.6 gives three concrete results. Endpoint products are redundant if their individual factors are retained. Complete, degree-compatible polynomial bases encode the same information. On equal-size positive-degree regular graphs, averaging monomial joint channels over all ordered triples loses graph distinctions. Added Propositions 2–3 extend this analysis: even unlimited polynomial degree or moment order can fail for the specified comparisons, while changing features or mixing channels succeeds (Sections 3–4; Q2 below).


W2 — Downstream prediction and numerical reliability

Joint augmentation improves the average recorded score over the walk/endpoint baseline on both datasets, and all reliability experiments met expectations. The prediction experiment keeps the model and training settings fixed while changing its structural inputs.

Walk + endpoints uses walk statistics and separate endpoint summaries, padded with zeros to the chosen width. Base + joint fills the zero slots with statistics of walks meeting at a common vertex; Base + squares fills them with squared retained entries. Joint + DCT mixes joint inputs through an invertible discrete cosine transform. RRWP (relative random-walk probabilities) and Chebyshev inputs are additional references.

Encoding / paired differencePROTEINS_fullENZYMES
Walk + endpoints74.011%45.583%
Base + joint76.036%46.458%
Joint augmentation gain+2.025 pp+0.875 pp
Base + squares73.043%46.500%
Joint + DCT mixing74.934%45.083%
No additional encoding75.072%43.583%
RRWP (reference)76.151%47.667%
Chebyshev (reference)78.804%47.875%

The 720 runs cover two datasets, nine inputs, widths 8/12/14/16 and ten folds. Within each dataset/fold/width, GNNPlus (three-layer GINE), parameter count, initial weights, splits, seeds and training settings match. Joint and squares retain all baseline inputs, input width and model size; preprocessing costs differ.

Scores average four widths' ten-fold means. Joint gains are positive at all PROTEINS_full widths and three ENZYMES widths, but negative at ENZYMES width 8. Standard deviations of the paired gains across folds range from 2.8 to 9.6 percentage points. RRWP and Chebyshev have higher means on both datasets.

Squares nearly match joint on ENZYMES but fall below the base on PROTEINS_full. DCT lowers both joint means while preserving information and the exact model function class. Thus score changes alone do not establish information gains. After mixing, shared initial weights need not give the same initial predictions; initialization, optimization and arithmetic effects are not isolated. The basis comparison follows Chen et al. (2025).

The node/edge input interface retains a statistic that distinguishes rook/Shrikhande. Prediction tests all joint channels together, so the gains are not attributed to that statistic alone.

Co-Sparsify's pipeline (Chen et al., 2026) uses the same held-out fold to select a checkpoint and score it. Folds share training data, and widths reuse splits. These are descriptive comparisons under that protocol, not independent-test estimates or 40 independent replications (Appendix I).

The reliability checks support their validated pair distinctions. Exact arithmetic or outward-rounded intervals that enclose exact values provide computational guarantees; repeated runs and relabelings give consistent decisions (Appendix H.1).

These pair checks do not certify the separate bundled counts—262 versus 211 at Q=4Q=4, or 88 versus 48 at Q=2Q=2—or triple/joint results. Those comparisons differ in width and cost (Appendix O). Object controls retain their stated floating-point scope (Appendix N).

Q1 — What does Theorem 1 add, and is graph-dependent interpolation essential?

Theorem 1 gives a complete algebraic description of each FWL round on a fixed finite graph; common expressions also exist for prescribed finite graph families and bounded graph size. The result is recoverable from GR after matching operations (GR Appendices C and D.2; revised Appendix A). It describes the full allowed algebra, without guaranteeing a small complete feature set.

The proof uses polynomials to recover color indicators: functions equal to one on a refinement color class and zero elsewhere. For one fixed graph (k≥2k\ge2), the interpolation coefficients may depend on that graph. Submitted p.13 shows that the same expressions can instead be shared across a prescribed finite graph family.

Added Appendix A.1 gives common expressions for all simple undirected unlabelled graphs with n≤Nn\le N. Their local degree is at most N+1N+1 in previous indicators/counts, before recursively substituting earlier expressions. This is neither walk-degree budget QQ nor moment budget PP; variable count can grow.

For unbounded size, consider the first-round color of an isolated vertex. On the center of a star K1,mK_{1,m}, its indicator must equal one when m=0m=0 and zero for every positive integer mm. A single finite polynomial in mm cannot do this. This rules out that exact indicator construction, not all uniform distinguishing features or nonpolynomial maps.


Q2 — A lower bound or strict finite-dictionary separation at the same budget

Proposition 2 proves strict separation, and Corollary 1 retains it with 19 channels on each side. Here QQ controls the polynomial degree of walk features, and PP controls the channelwise powers retained. 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-row multisets agree for every finite Q,P≥1Q,P\ge1. A row records one triple's features; the multiset retains these rows and their multiplicities. Joint-augmented rows distinguish the graphs already at Q=P=1Q=P=1. Both monomial and Chebyshev bases and all ordered triples, including repeats, are covered (Section 3.2; Appendix D).

Higher matrix powers reduce to combinations of the identity, adjacency and all-ones matrices. Endpoint summaries are constant, and triple-pattern counts match. Joint features associate triangles with their common-neighbor counts, revealing the different four-clique counts.

For equal width, replace one duplicate equality coordinate, I21=I12I_{21}=I_{12}, by K111K_{111}, the weighted common-neighbor count of a triple. The retained equality coordinate recovers the removed one, so these 19 channels retain the baseline and recover the full 27-channel dictionary. Endpoint channels are absent at Q=P=1Q=P=1 but remain unable to separate at higher degrees. The uncompressed widths are 19/27; joint total degree can reach kQkQ. Equal channel width does not imply equal cost or the same behavior under a restricted moment readout.

Proposition 3 separately improves the readout at Q=1,P=3Q=1,P=3 by invertible mixing, preserving information and width. MoSE already uses rook/Shrikhande against node-return random-walk structural encodings (RWSE; Bao et al., 2025); our comparisons concern the specified complete triple dictionaries and readout.

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.
  • Chen, R., Li, Y., Wu, D., Mo, F., Zhang, S., Ip, P. L., Iam, H. C., Li, Y., and U, L. H. Enhanced Subgraph Learning in 2-FWL GNNs via Local Connectivity, Spectral, and Distance Encodings. KDD, 2025.
  • Chen, R., Mo, F., Ip, P. L., Zhang, S., Wu, D., Li, Y., and U, L. H. Connectivity-Guided Sparsification of 2-FWL GNNs: Preserving Full Expressivity with Improved Efficiency. AAAI, 2026.
  • Bao, L., Jin, E., Bronstein, M., Ceylan, İ. İ., and Lanzinger, M. Homomorphism Counts as Structural Encodings for Graph Learning. ICLR, 2025.
AuthorsOpenReview ↗

PDF revisions addressing your questions

We have uploaded the revised PDF. Here is where to find the changes prompted by your questions:

  • Uniformity and novelty (W1/Q1): §2.3, p.4; Appendix A.1, p.16. We now state explicitly that Geerts and Reutter (2022) recover Theorem 1 and Proposition 1 after matching the operations. Added Proposition 5 gives a common indicator construction for all simple undirected unlabelled graphs of size at most NN. This establishes uniform existence at bounded size, without guaranteeing a small complete dictionary.

  • Strict separation (W1/Q2): §3.2, pp.5–6. Added Proposition 2 proves that, for positive-degree strongly regular graphs with matching parameters but different four-clique counts, the complete walk/endpoint baseline fails at every degree and moment order, while joint features distinguish them with degree-one seeds. Both studied bases and all ordered triples, including repetitions, are covered. Corollary 1 retains the strict gain with 19 channels on each side by replacing a duplicate coordinate; equal width does not imply equal construction cost.

  • Numerical reliability (W2): §5.2, p.8; Appendix H.1, p.29. We added exact-arithmetic and rigorous interval checks, repeated runs and relabeling tests. These support the validated pair distinctions; they do not certify the separate bundled counts or joint-triple results.

  • Downstream prediction (W2): §5.4, pp.9–10; Table 2, p.10. We added GNNPlus comparisons with matched input width, model and training settings. Joint augmentation improves the mean over walk/endpoint inputs by 2.03 and 0.88 percentage points on PROTEINS_full and ENZYMES. The paper also reports information-preserving controls and fold variation. Preprocessing costs differ, and checkpoint selection and scoring use the same held-out fold, so these are descriptive comparisons.

We hope these additions are helpful and that the pointers above make the relevant changes easier to find in the revised PDF.

AuthorsOpenReview ↗

We would like to clarify two points from our earlier response.

BREC reliability. All checks we ran on BREC's official isomorphic pairs passed (§5.2, Appendix H.1). We also added exact rational arithmetic using Fraction. It keeps values such as 1/31/3 as ratios of integers, so sums and products stay exact. This avoids floating-point rounding in those operations wherever the same arithmetic is used.

Downstream prediction. In response to your question about the compute budget, Table 2 compares the encodings under the same GNNPlus backbone and training protocol at each input width and fold. Across widths and folds, the joint features score higher on average than the walk-and-endpoint baseline on both datasets. The same fold is used for checkpoint selection and scoring. Feature construction costs vary, so a comparison at equal total compute remains open (§5.4, Appendix I.1).

Comments on the paper

3 comments
AuthorsOpenReview ↗

Revision overview

What do our results show? When a graph representation fails to distinguish two graphs, there are two possible reasons: its features may lack the necessary information, or its readout may lose information that is already present. Our paper studies both causes.

What was in the submission? We showed that some added features are redundant when their constituent features are retained, and that complete polynomial bases can encode the same information. We also showed that mean pooling can hide distinctions in the features.

What did we add? We compare a baseline built from walk and endpoint features with joint features that count walks meeting at a common vertex. For strongly regular graph pairs with the same parameters but different numbers of four-cliques, increasing the baseline's polynomial degree never distinguishes the pair, but adding joint features does. The strict gain also holds with 19 channels on each side at Q=P=1Q=P=1, although construction costs differ (Proposition 2 and Corollary 1).

We also study the rook and Shrikhande graphs. Their joint features distinguish them, but averaging powers of each channel separately misses the distinction at every degree and moment order in the two original bases. Mixing the existing channels before taking their third moments recovers it without adding information or channels (Proposition 3). Both comparisons use all ordered triples, including repeated vertices.

What do the experiments tell us? Object experiments show that improvements for vertex pairs need not extend to nodes or edges. In fixed-model prediction, joint features give positive average gains over the stated baseline on two datasets; information-preserving changes also affect scores. The prediction comparisons are descriptive.

All reliability experiments met expectations. Exact arithmetic and interval bounds guarantee the validated pair distinctions; these checks do not certify the separate bundled counts or triple/joint outcomes (Sections 3–5).

Area_Chair_uSF4OpenReview ↗

Please engage with the authors rebuttal by Nov 18

Dear Reviewers,

The authors have posted their rebuttal. Please engage with it by November 18, 2026, noting which of your concerns are resolved or which remain. Even brief engagement helps greatly.

Best regards,
Area Chair

AuthorsOpenReview ↗

Revision overview: what changed and where to find it

We have uploaded the revised PDF. ICLR allows ten main-text pages during discussion, compared with nine at submission. The changes below address the presentation, theoretical comparisons and experimental evidence raised in the reviews. All locations refer to the revised PDF.

  • Presentation — §§2.1–2.3, pp.2–4; Table 1, p.5. We now introduce the encoding constructions before the algebra and collect the budget definitions in §2.2. Figure 2 (p.3) illustrates separate endpoint sums versus a shared pivot. Encoding information and readout behavior now have separate sections (§§3–4, pp.5–7); Table 1 lists each comparison's conditions and use.

  • Prior work and theoretical scope — §2.3, p.4; Appendix A.1, p.16. We explicitly state how Geerts and Reutter (2022) recover Theorem 1 and Proposition 1, and distinguish the roles of the two inclusions. Added Proposition 5 gives shared indicator expressions for all simple undirected unlabelled graphs up to a fixed size, without promising a small complete dictionary.

  • Strict encoding comparisons — §3.2, pp.5–6. Added Proposition 2 proves that the complete walk/endpoint baseline fails at every degree and moment order on positive-degree strongly regular graph pairs with matching parameters and different four-clique counts. Joint features succeed with degree-one seeds. Corollary 1 preserves the gain with 19 channels on each side, although construction costs differ.

  • Readout failure and recovery — §4.3, p.7. Added Proposition 3 shows that, on rook/Shrikhande, all separate-channel moments fail in the original bases, while invertible mixing before cubing and averaging succeeds without adding information or channels. Both this comparison and the strict separation use all ordered triples, including repetitions, and cover monomial and Chebyshev bases.

  • Backbone reconstruction — §5.1, p.8. We moved the formal synthesis statement into the main text. Submitted Proposition 2 is now revised Proposition 4. The existing construction circuits are in Appendix F.2–F.3 (p.26).

  • Experimental evidence — §§5.2 and 5.4, pp.8–10. We added exact/interval pair-validation checks and relabeling tests (Appendix H.1, p.29), plus GNNPlus prediction comparisons with matched input width, model and training settings (Table 2, p.10). Joint augmentation improves the mean on both datasets. Information-preserving controls, fold variation and scoring limitations are reported alongside these results. The validation does not certify the separate bundled counts or joint-triple results; prediction comparisons are descriptive and preprocessing costs differ.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.