acceptodds
Under review as a conference paper at ICLR 2027

Algebraic Knot Deep Graph Learning for Structural Generalization

Abstract

As graph-structured data grow increasingly complex, the ability to reliably distinguish non-isomorphic graphs becomes essential, yet the difficulty of achieving it is often underestimated. Strongly regular graphs illustrate this challenge sharply: non-isomorphic graphs with the same parameters may share identical degrees and identical common-neighbor counts for every adjacent and every non-adjacent pair of nodes. As a result, they are indistinguishable not only to Message Passing Neural Networks (MPNNs), the dominant class of Graph Neural Networks (GNNs), but also to more expressive architectures matching the 3-dimensional Weisfeiler–Leman (3-WL) test. To address this limitation, knot theory offers a conceptually different structural perspective, since chord diagrams represent knot crossing relations through interlacement graphs, providing a connection between knot-theoretic structure and graph adjacency. Motivated by this phenomenon, we introduce KnotState, which characterizes induced subgraphs through the rank–nullity structure of their adjacency matrices over . We then design KSGL, a graph learning framework that integrates multi-order local and global KnotState information with message passing. Specifically, we establish an order-dependent discriminative hierarchy for KSGL and introduce the KnotState separation order, showing that structural distinctions obtained at a given order are preserved at all higher orders. Further, we find that KSGL contains its underlying MPNN as a special case and can distinguish graph pairs that MPNNs, and in some cases 3-WL, leave unresolved. Experiments on challenging non-isomorphic graph benchmarks show that increasing the KnotState order progressively resolves previously indistinguishable graph pairs. We also demonstrate the utility of KnotState on zeolite property prediction under both interpolation and unseen-topology generalization. To the best of our knowledge, KSGL is the first GNN framework to systematically translate knot-theoretic state information into multi-order local–global graph representations with theoretical guarantees, establishing a new connection between knot theory and expressive graph learning. Code is available at https://anonymous.4open.science/r/KSGL-0DBD/

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph Neural Networks, Knot deep Learning, Structural Generalization

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_P5y1OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes KnotState Deep Graph Learning (KSGL), which uses rank–nullity statistics of induced adjacency matrices over F2\mathbb{F}_2 to capture structural information beyond standard message passing. The authors construct local and global KnotState distributions across different subgraph orders and incorporate them into a GNN backbone. They study the discriminative power of these representations, including their ability to distinguish certain graph pairs beyond 3-WL. The method is evaluated on strongly regular graphs, BREC, and zeolite property prediction.

Critical strengths

The idea of using adjacency rank–nullity statistics for graph representation is interesting. The graph discrimination results are fairly strong, especially on strongly regular graphs and BREC, where KSGL distinguishes 300 of 400 graph pairs. The zeolite experiments also show improvements in heat-of-adsorption prediction, giving some evidence that the proposed features are useful beyond graph discrimination benchmarks.

Critical weaknesses

W1. I find the theoretical contributions somewhat limited. The MPNN inclusion and order-persistence results follow rather directly from how the features are constructed, while the beyond-3-WL result requires the KnotState separation order to be finite. The paper does not really characterize when this condition holds. Supplementary Table 8 also shows that KSGL distinguishes none of the 100 CFI pairs in BREC at the evaluated orders, compared with 60 for 3-WL. This raises questions about which graph structures KnotState can actually distinguish, something the current theory does not explain well.

W2. The computational cost of extracting KnotState features is a major concern. The method involves computing rank–nullity distributions over induced vertex subsets, which can become very expensive at higher orders. However, the authors evaluate BREC using orders up to K=20K=20 without clearly explaining how these features are computed. Table 5 and Appendix E also exclude preprocessing from their efficiency comparisons. Since feature extraction could account for a large portion of the total cost, I don't think the reported inference time alone is sufficient to evaluate the efficiency or scalability of KSGL.

W3. The experimental comparisons do not clearly show what KnotState offers over existing structural encodings. Table 2 compares local and global KnotState signatures, but the full KSGL results also include graph refinement, making it difficult to isolate the contribution of each component. There is also no direct comparison with simpler substructure-counting features, such as those used in GSN [1], which have already been shown to improve graph discrimination. Furthermore, it is unclear whether the BREC results follow the same evaluation protocol as the reported learned baselines, which could affect how the separation accuracies should be compared.

Overall, the graph discrimination results are promising, but I am not fully convinced by the theoretical contribution or the experimental evidence for the advantages of KnotState over existing approaches. The unclear computational cost is also a significant concern, particularly at higher orders.

References

[1] Bouritsas et al., Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting. IEEE TPAMI, 2023.

Questions for authors

Q1. How exactly are high-order KnotState features computed on BREC, particularly at K=20K=20? Which orders are used for different graph sizes, are the distributions computed exactly, and what are the preprocessing time and memory requirements?

Q2. How would KSGL compare with a GIN backbone augmented with simpler substructure-counting features, such as clique or cycle counts, under comparable computational budgets?

Q3. Were the BREC results obtained using the same evaluation protocol as the reported learned baselines, or through deterministic comparison of structural signatures? If the procedures differ, how should the separation accuracies be interpreted?

6 comments

We sincerely thank the reviewer for their thoughtful reading of our paper and valuable feedback. We would like to provide point-by-point responses to further improve this work as follows. We have also incorporated the changes (in blue) to the revised version.

Response to Q1:

Our initial KnotState computation relied on exact enumeration of induced subsets to establish rigorous structural discrimination. On BREC, the initial exact procedure proceeds order by order: at a higher order, we exhaustively enumerate induced subsets only for graph pairs unresolved at the preceding order. Once a graph pair is distinguished, the order-persistent separation result (Theorem 5.1, Sec. 5, p. 6; proof in Appendix B.4, p. 18) makes further higher-order enumeration unnecessary for that pair. For an nn-vertex graph, the global order-ss distribution involves (ns)\binom{n}{s} induced subsets, each requiring a binary adjacency-nullity calculation. The feasible global orders are 1≤s≤min⁡(K,n)1\leq s\leq\min(K,n); for a root uu, the local orders are bounded by min⁡(K,∣BR(u)∣)\min(K,|B_R(u)|). The maximum order examined on BREC is K=20K=20 (Sec. 6.2, p. 8; exact pair counts in Appendix C, Table 8, p. 21). The deterministic results and the new sampling experiments are separate evaluations.

We profiled KnotState preprocessing while varying graph size ∣V∣|V|, maximum order KK, and local radius RR. For exact preprocessing, the number of evaluated subgraphs is

Nexact=∑s=1K[(∣V∣s)+∑u∈V(∣BR(u)∣−1s−1)].N_{\mathrm{exact}}=\sum_{s=1}^{K}\left[\binom{|V|}{s}+\sum_{u\in V}\binom{|B_R(u)|-1}{s-1}\right].

Hence, ∣V∣|V| and KK primarily affect global enumeration, while RR affects the sizes of the rooted neighborhoods BR(u)B_R(u). Each setting was repeated three times. We report median wall-clock time and incremental peak host memory above the initialized process footprint.

Sensitivity of exact KnotState preprocessing:

FactorConfiguration# Evaluated SubgraphsTime (s)Δ\DeltaRSS (MiB)
KKn=35,d=16,R=1,K=4n=35,d=16,R=1,K=471,9600.0189.06
KKn=35,d=16,R=1,K=5n=35,d=16,R=1,K=5460,2920.10611.39
KKn=35,d=16,R=1,K=6n=35,d=16,R=1,K=62,236,3320.64113.40
∣V∣\lvert V\rvertn=25,d=8,R=1,K=6n=25,d=8,R=1,K=6247,4300.07513.16
∣V∣\lvert V\rvertn=35,d=8,R=1,K=6n=35,d=8,R=1,K=62,006,5220.57312.90
∣V∣\lvert V\rvertn=50,d=8,R=1,K=6n=50,d=8,R=1,K=618,248,8604.72413.53
RRn=35,d=16,R=1,K=6n=35,d=16,R=1,K=62,236,3320.64113.40
RRn=35,d=16,R=2,K=6n=35,d=16,R=2,K=613,571,7123.48413.87

The results confirm that exact preprocessing time is combinatorial in ∣V∣|V| and KK. Fixing K=6K=6 and increasing ∣V∣|V| from 25 to 50 increases runtime by approximately 63×63\times. Increasing KK from 4 to 6 on SRG-like graphs increases runtime by approximately 36×36\times. The effect of RR is graph-dependent. On SRG(35,16,6,8)\mathrm{SRG}(35,16,6,8), R=2R=2 covers the full diameter and increases runtime by 5.4×5.4\times. In contrast, peak memory remains nearly constant because combinations are streamed in fixed-size chunks rather than stored simultaneously.

Table 5 (Sec. 6.4, p. 10; complete comparison in Appendix E, Table 7, p. 20) excludes preprocessing because it compares the online neural-model cost after features have been computed: parameter count, training-time GPU memory, and inference latency. KnotState enumeration is a deterministic, training-independent CPU operation performed once and cached for reuse across epochs and inference. We agree that this one-time cost is important for end-to-end deployment and report it separately here.

Response to Q2:

Thank you for this valuable suggestion. We compared conventional structural descriptors with KSGL on the BREC Extension benchmark (100 graph pairs) using learned GIN models with different node features. The results are shown in the table below.

Learned GIN with different node features on BREC:

Structural descriptor / ModelExtension (100)
GIN0
Degree + GIN0
Clustering coefficient + GIN5
Triangle count + GIN5
Clique counts (3--4) + GIN20
Graphlet counts (3 nodes) + GIN5
Graphlet counts (4 nodes) + GIN84
Cycle counts (3--5) + GIN96
Adjacency rank/nullity + GIN57
KSGL (K=5)96
KSGL (K=6)97
KSGL (K=7)98
KSGL (K=8)99
KSGL (K=9)100
KSGL (K=10)100

This table demonstrates the strong discriminative power of KSGL with learned GIN on the BREC Extension benchmark. Even at a relatively low order (K=5)(K=5), KSGL distinguishes 96 of 100 graph pairs, matching the strongest conventional feature-augmented GIN baseline, Cycle counts (3–5), and outperforming four-node graphlet counts (84/100). As KK increases from 5 to 9, KSGL progressively improves from 96 to 100 separations, achieving complete separation at K=9K=9, which is maintained at K=10K=10. This empirical improvement is consistent with the order hierarchy in Proposition 5.2 (Sec. 5, p. 5) and the persistent structural separation property established in Theorem 5.1 (Sec. 5, p. 6; proof in Appendix B.4, p. 18).

These improvements reflect the distinct structural information captured by KnotState. Conventional descriptors characterize degrees, clustering, specific subgraph patterns, or short cycles, but do not explicitly retain the distribution of algebraic dependencies across induced subgraphs. In contrast, KnotState captures multi-order adjacency rank–nullity distributions over F2\mathbb F_2, revealing structural differences beyond these fixed-order statistics. More importantly, the advantage of KSGL lies not merely in adding more structural features, but in how these features are constructed and integrated into graph learning. Unlike conventional feature-augmented GIN models, KSGL jointly incorporates root-conditioned local KnotState distributions and graph-wide global KnotState statistics into node representations. The local component preserves vertex-specific algebraic dependencies, while the global component supplies structural information shared across the entire graph. Their combination allows the subsequent GIN layers to learn from both local and global structural information.

The comparison is particularly informative because the learning backbone is GIN: the improvement therefore highlights the contribution of KnotState representations rather than a change to a fundamentally different neural architecture. Proposition 5.1 (Sec. 5, p. 5) establishes that KSGL contains its underlying MPNN as a special case. Furthermore, Theorem 5.3 (Neural realizability of KnotState separation; Sec. 5, p. 6; proof in Appendix B.7, p. 19) establishes that the complete MLP+GIN architecture can realize every distinction encoded by the cumulative KnotState signatures on any fixed finite graph family.

These results demonstrate that KSGL transforms multi-order algebraic structural information into learnable graph representations, achieving stronger discrimination than GIN augmented with conventional structural descriptors and establishing a theoretical connection between KnotState structural separation and neural expressivity.

Response to Q3:

We distinguish the KnotState structural representation from KSGL, the learning framework that integrates cumulative local–global KnotState information into the complete MLP+GIN architecture (Sec. 5, pp. 5–6). The structural results in Table 3 (Sec. 6.2, p. 8), with exact pair counts in Appendix C (Table 8, p. 21), are obtained through direct deterministic comparison of KnotState structural signatures. The learned-model evaluations are reported separately in the corresponding learning experiments, including zeolite property prediction in Sec. 6.3 (Table 4, p. 9). The published BREC baselines and the deterministic KnotState evaluation should therefore be interpreted according to their respective protocols. Importantly, these two evaluations are theoretically connected. Theorem 5.3 (Neural realizability of KnotState separation; Sec. 5, p. 6; proof in Appendix B.7, p. 19) establishes that for fixed K,RK,R and any finite graph family G\mathcal G, with sufficiently expressive MLPs, GIN updates, and sum pooling, there exist shared parameters θ\theta such that

SK,R(G)≠SK,R(H)⟹hGθ≠hHθS_{K,R}(G)\neq S_{K,R}(H)\quad\Longrightarrow\quad h_G^{\theta}\neq h_H^{\theta}

for every G,H∈GG,H\in\mathcal G. Thus the theoretical discriminative capacity of KSGL is no weaker than that of the underlying KnotState structural representation. This theorem proves the existence of a shared neural parameterization preserving all structural-signature distinctions on a fixed finite graph family. It does not assert that every trained checkpoint automatically attains all such distinctions. The structural comparison and learned architecture therefore provide complementary evidence. The former establishes which graph pairs KnotState can distinguish, while the theorem guarantees the ability of the full KSGL architecture to realize those distinctions.

Reviewer_PoPbOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes KnotState Deep Graph Learning (KSGL), a framework that uses algebraic properties of induced subgraphs to improve structural discrimination and graph representation learning. Motivated by connections between knot theory, chord diagrams, and interlacement graphs, the authors introduce KnotState descriptors based on the rank and nullity of induced adjacency matrices over F2\mathbb F_2. KSGL combines multi-order global and rooted local KnotState distributions with a message-passing GNN to capture structural information beyond conventional neighborhood aggregation. The paper establishes an order-dependent hierarchy showing that distinctions available at a given KnotState order remain available at higher orders, and introduces the KnotState separation order to characterize when graph pairs become distinguishable. The authors also show that KSGL contains its underlying MPNN as a special case and can distinguish certain non-isomorphic graph pairs that remain indistinguishable to 3-WL. Experiments on strongly regular graph families and BREC demonstrate improved graph-pair discrimination, while zeolite property prediction experiments examine the usefulness of KnotState representations for interpolation and generalization to unseen framework topologies.

Critical strengths
  1. Interesting connection between algebraic graph descriptors and graph learning. The paper offers an interesting perspective on structural representation learning by connecting rank-nullity properties of induced adjacency matrices over F2\mathbb F_2 with knot-theoretic interlacement structures. Rather than modifying the message-passing operator itself, KSGL introduces additional structural information through local and global KnotState distributions. I think this is a useful direction, particularly for regular graphs where conventional neighborhood aggregation struggles to identify structural differences.

  2. Clear integration of local and global structural information. One positive aspect is that KSGL combines rooted neighborhood statistics with graph-wide distributions of induced-subgraph algebraic properties. The local descriptors provide node-dependent structural information, while the global descriptors summarize structural patterns across the entire graph. The resulting representations can be integrated into an existing GIN backbone without redesigning the message-passing architecture. The ablation results in Table 2 are also useful because they show the contributions of local information, global information, and subsequent structural refinement.

  3. Theoretical characterization of order-dependent discrimination. The paper provides a clear formalization of how structural information changes with the maximum KnotState order KK. Proposition 5.1 establishes that KSGL contains its underlying MPNN as a special case, while Proposition 5.2 and Theorem 5.1 characterize the preservation of structural distinctions as higher-order KnotState components are added. The KnotState separation order κR(G,H)\kappa_R(G,H) also provides a useful way to describe the smallest induced-subgraph order at which the proposed signatures distinguish a graph pair.

  4. Evaluation beyond synthetic expressivity benchmarks. The zeolite experiments are a useful addition because they test whether the structural descriptors contribute to an actual prediction problem. The distinction between interpolation and unseen-topology generalization is particularly relevant to the paper's motivation. The results show improvements in heat-of-adsorption prediction and provide an opportunity to examine whether stronger structural representations are beneficial when encountering previously unseen zeolite frameworks.

Critical weaknesses
  1. Novelty beyond existing interlace-polynomial descriptors. The proposed KnotState descriptor uses the nullity of induced adjacency matrices over F2\mathbb F_2, with global distributions counting induced vertex subsets according to their nullities. However, the authors acknowledge that the complete global KnotState distribution contains the same information as the existing two-variable interlace polynomial. While the connection to knot theory provides useful motivation, the method operates on arbitrary graph adjacency matrices without requiring actual knot or chord diagram representations. The main contribution therefore appears to be the combination of truncated interlace-polynomial-related statistics, rooted local distributions, and a GNN backbone, rather than a fundamentally new algebraic invariant. I think the authors should clarify this distinction and explain more explicitly how their approach differs from existing algebraic structural encodings.

  2. Theoretical hierarchy vs. learned-model expressivity. Proposition 5.2 shows that increasing the maximum KnotState order KK preserves lower-order structural information, but this follows directly from concatenating all components up to order KK. Similarly, Theorem 5.1 establishes that structural signatures remain distinguishable when higher-order coordinates are added. While these results characterize the information retained by the descriptors, they do not necessarily guarantee that a trained KSGL model will preserve these distinctions after the input MLP, message-passing layers, and graph-level readout. Non-injective transformations or pooling operations could still map different structural representations to the same output. Since the proof in Appendix B.4 concerns the raw structural signatures, I think the authors should clarify whether additional assumptions are needed to extend these guarantees to the complete neural architecture.

  3. Conditional expressivity advantage beyond 3-WL. Corollary 5.1 shows that KSGL can distinguish graph pairs that remain indistinguishable to 3-WL when their KnotState separation order κR(G,H)\kappa_R(G,H) is finite. However, the paper does not establish whether this condition holds for all non-isomorphic graph pairs or characterize the graph families where it applies. The result also does not imply that KSGL generally dominates 3-WL, since this would require showing that KSGL preserves every distinction available to 3-WL. The BREC results highlight this limitation: KSGL separates 300/400 pairs but none of the 100 CFI pairs, whereas 3-WL separates 60 CFI pairs. These findings suggest that the two approaches capture different structural distinctions, and the authors should clarify the precise scope of their expressivity claims.

  4. Computational cost of KnotState preprocessing. KSGL computes KnotState distributions from induced subgraphs of increasing order, which can become computationally expensive as KK grows. For example, a global order-ss descriptor considers (ns)\binom ns vertex subsets, each requiring a binary adjacency-rank or nullity computation, while local descriptors introduce additional rooted computations. Although the resulting aggregated features are compact, their extraction may be considerably more expensive than the subsequent GNN training or inference. However, the efficiency comparisons in Table 5 and supplementary Table 7 exclude offline feature preprocessing, so the reported parameter counts, GPU memory usage, and inference latency do not reflect the complete computational cost. This is particularly important because the BREC experiments use KnotState orders up to K=20. An end-to-end comparison including preprocessing would help establish the practical efficiency of KSGL.

  5. Structural discrimination vs. neural expressivity. The graph-discrimination experiments measure cumulative pair separation using deterministic 1-WL/GIN-style refinement of KnotState augmented features, without an additional supervised classifier. This is useful for evaluating the discriminative information contained in the descriptors, but it does not establish whether a finite, trained KSGL model can consistently reproduce the same separations. The theoretical signatures and their learned neural representations may have different expressive capabilities. Moreover, the BREC results show that KSGL separates 300/400 pairs, including all 140 regular pairs, but fails on all 100 CFI pairs. This suggests that its improvement is concentrated in particular graph categories rather than being consistent across the benchmark. Evaluating the actual trained KSGL architecture would help connect the structural discrimination results to its practical neural expressivity.

Questions for authors
  1. Novelty beyond the interlace polynomial (Sections 2-3, pp. 2-4; Appendix A.1-A.5). The KnotState descriptors are based on the nullity of induced adjacency matrices over F2\mathbb F_2, and Appendix A acknowledges their connection to the two-variable interlace polynomial. In particular, the complete global KnotState distributions contain the same information as this existing graph invariant. Could the authors clarify what is fundamentally new in the proposed construction? Is the main contribution the rooted local distributions, their combination with global statistics, or their integration into a message-passing framework? A comparison with models using conventional interlace-polynomial or adjacency-rank features would help establish the added value of KSGL.

  2. Expressivity beyond 3-WL (Section 5, Definition 5.1, Corollary 5.1; Section 6.2; Appendix B.5). Corollary 5.1 shows that KSGL can distinguish graph pairs that remain indistinguishable to 3-WL when their KnotState separation order κR(G,H)\kappa_R(G,H) is finite. However, it is unclear which graph families satisfy this condition or whether every non-isomorphic pair has a finite separation order. Could the authors characterize these graph families and provide examples where KnotState signatures fail to distinguish non-isomorphic graphs even at the maximum possible order? Also, KSGL separates 300/400 BREC pairs but none of the 100 CFI pairs, whereas 3-WL separates 60 CFI pairs. Does this suggest that their expressive powers may be incomparable rather than KSGL generally dominating 3-WL? A clearer theoretical explanation would be helpful.

  3. End-to-end computational complexity (Sections 3 and 5-6.4; Table 5; Appendix B.4, Table 7). KSGL computes local and global KnotState distributions by examining induced subgraphs and evaluating adjacency nullity over F2\mathbb F_2. Since the number of induced subsets grows combinatorially with the maximum order KK, feature extraction could become expensive even when the GNN itself is relatively small. However, the reported efficiency comparisons exclude offline preprocessing. Could the authors provide the complete computational cost, including KnotState extraction, feature storage, training, and inference? In particular, how do preprocessing time and memory scale with graph size nn, order KK, and radius RR, and what is the largest graph size for which exact extraction remains practical? An end-to-end comparison with other structural GNNs would help clarify the claimed computational advantages.

  4. Generalization to unseen zeolite topologies (Section 6.3, pp. 8-9; Table 4; Appendix D). The unseen-topology experiments are useful, but the results are somewhat mixed. KSGL improves heat-of-adsorption prediction compared with GNN and SymGNN, while SymGNN performs better on unseen-topology adsorption-isotherm prediction. Could the authors explain why KnotState improves one task but not the other? Is this related to the structural information captured by KnotState or to differences in the physical factors governing the prediction targets? It would also be helpful to evaluate additional held-out topology splits and report results separately for each framework to determine whether the improvements extend beyond the selected ITW and CHA topologies.

  5. Contribution of higher-order KnotState features (Sections 3 and 5-6.1; Tables 1-2; Appendix A.2-A.5). The lower-order KnotState distributions capture familiar graph statistics, while higher orders introduce additional binary adjacency dependencies. However, it is unclear how much of the improvement comes specifically from these higher-order nullity patterns rather than simply providing more structural features. Could the authors compare KnotState with graphlet counts, cycle statistics, degree-based features, and other induced-subgraph descriptors under similar feature dimensions and computational budgets? It would also be useful to measure the additional information gained at each order KK beyond the lower-order features already included. This would help clarify what makes binary adjacency nullity particularly valuable for structural discrimination.

7 comments

We thank the Reviewer for the feedback and insightful suggestions. Below we provide our detailed response to your question. We have also incorporated the changes (in blue) to the revised version.

Response to Q1:

Could the authors clarify what is fundamentally new in the proposed construction? Is the main contribution the rooted local distributions, their combination with global statistics, or their integration into a message-passing framework?

We thank you for highlighting the connection to classical interlace polynomials. Yes, the complete global KnotState distributions contains information of the two-variable interlace polynomial of Arratia et al. (2004), and we have added the respective discussion on page 4.

More importantly, the central contribution of our paper lies in the transformation of graph algebraic information into root-conditioned, multiorder structural representations that can be integrated into message passing. Unlike a global polynomial shared by all vertices, rooted KnotState distributions characterize induced adjacency dependencies within individual neighborhoods, retaining node-specific structural information. Importantly, this localization provides a strict information gain over the complete two-variable global interlace polynomial, and we have added this discussion on page 5.

Below we present an explicit example demonstrating the utility of the information contained in rooted KnotState. To make the distinction from the classical two-variable interlace polynomial more transparent, consider two graphs (G) and (H) on (V=0,…,6\\{0,\ldots,6\\}), with edge sets

E(G)=01,13,16,24,36,56,E(G)=\\{01,13,16,24,36,56\\},

E(H)=01,05,12,15,23,24,34,45,46.E(H)=\\{01,05,12,15,23,24,34,45,46\\}.

where, (ij) denotes the edge (i,j). The graphs are non-isomorphic. Exact enumeration of all 128 vertex subsets confirms that

HGs(r)=HHs(r),H_G^s(r)=H_H^s(r),

for all s,rs,r and therefore (q(G;x,y)=q(H;x,y)). Nevertheless, their fourth-order rooted KnotState distributions differ. Specifically,

ℓ1,41(G)=(4,0,0,0,0),\ell_{1,4}^{1}(G)=(4,0,0,0,0),

ℓ4,41(H)=(2,0,2,0,0),\ell_{4,4}^{1}(H)=(2,0,2,0,0),

and the corresponding rooted-signature multisets satisfy

Φ41(G)≠Φ41(H).\Phi_4^1(G)\neq\Phi_4^1(H).

KSGL further combines these root-conditioned signatures with global statistics in a unified multi-order representation and provides theoretical results connecting structural separation to neural realizability.

A comparison with models using conventional interlace-polynomial or adjacency-rank features would help establish the added value of KSGL.

Deterministic separation on BREC (common-WL refinement view).

Structural descriptorExtension (100)
GIN0
Degree0
Clustering coefficient5
Triangle count5
Clique counts (3--4)20
Graphlet counts (3 nodes)5
Graphlet counts (4 nodes)84
Cycle counts (3--5)96
Adjacency rank/nullity57
Global KnotState (K=5)96
Local KnotState (K=5)62
Joint KnotState (K=5)96
Global KnotState (K=6)97
Local KnotState (K=6)63
Joint KnotState (K=6)97
Global KnotState (K=7)98
Local KnotState (K=7)64
Joint KnotState (K=7)98
Global KnotState (K=8)99
Local KnotState (K=8)65
Joint KnotState (K=8)99
Global KnotState (K=9)100
Local KnotState (K=9)66
Joint KnotState (K=9)100

This Table above demonstrates the strong structural discriminative power of KnotState on the BREC Extension benchmark. Even at a relatively low order (K=5)(K=5), Global and Joint KnotState distinguish 96 of 100 graph pairs, matching the strongest conventional descriptor, Cycle counts (3–5), and outperforming four-node graphlet counts 84/10084/100. As KK increases from 5 to 9, Global KnotState progressively improves from 96 to 100 separations, while Local KnotState increases from 62 to 66. Joint KnotState reaches complete separation 100/100100/100 at K=9K=9, consistent with the order hierarchy in Proposition 5.2 and the persistent separation property established in Theorem 5.1.

These improvements reflect the distinct structural information captured by KnotState. Conventional descriptors characterize degrees, clustering, specific subgraph patterns, or short cycles, but do not explicitly retain the distribution of algebraic dependencies across induced subgraphs. In contrast, KnotState captures multi-order adjacency rank–nullity distributions over F2\mathbb F_2, revealing structural differences beyond these fixed-order statistics. The stronger performance of Global KnotState further highlights the importance of graph-wide algebraic organization, while rooted Local KnotState provides complementary vertex-specific information. Together, these results demonstrate the effectiveness of multi-order algebraic representations for distinguishing challenging non-isomorphic graphs.

**Response to Q2: **

It is unclear which graph families satisfy this condition or whether every non-isomorphic pair has a finite separation order.

We identify a specific class of graph pairs for which KSGL distinguishes structures that standard 3-WL cannot, particularly, non-isomorphic strongly regular graphs with identical parameters (n,d,λ,μ)(n,d,\lambda,\mu) but different induced-subgraph adjacency-nullity distributions. Strongly regular graphs sharing these parameters are indistinguishable by standard 3-WL. However, if their order-ss KnotState distributions differ, KSGL distinguishes them at order ss, as verified in our Experiment 1. The converse does not hold universally. We provide an example below.

"Could the authors characterize these graph families and provide examples where KnotState signatures fail to distinguish non-isomorphic graphs even at the maximum possible order?"

Yes, we present such explicit maximum-order counter-example. Let V(G)=V(H)=0,…,7V(G)=V(H)=\\{0,\ldots,7\\} and

E(G)&=\\{01,07,13,14,17,26,36,45,67\\},\\\\ E(H)&=\\{01,02,04,05,14,23,27,36,47\\}. \end{aligned}$$ where $(ij)$ denotes the undirected edge $(i,j)$. Exact enumeration of all $2^8=256$ vertex subsets yields $$H_G^s(r)=H_H^s(r)$$ for all $s,r$. Moreover, the two graphs have identical multisets of rooted one-hop neighborhood isomorphism types. Hence, $$S_{K,1}(G)=S_{K,1}(H)\quad(1\leq K\leq8),\qquad\kappa_1(G,H)=\infty.$$ > "Also, KSGL separates 300/400 BREC pairs but none of the 100 CFI pairs, whereas 3-WL separates 60 CFI pairs. Does this suggest that their expressive powers may be incomparable rather than KSGL generally dominating 3-WL? A clearer theoretical explanation would be helpful." KSGL achieves separations beyond 3-WL conditionally. As the Rook and Shrikhande graphs provide an explicit witness, KSGL can separate the SRG family completely, while 3-WL cannot. Hence we can get the proposition 5.3 (p. 6) : KSGL is **partially stronger** than the 3-WL test.

Response to Q3:

Sensitivity of exact KnotState preprocessing.

FactorConfigurationNumber of the evaluated subgraphsTime (s)Δ\DeltaRSS (MiB)
KKn=35,d=16,R=1,K=4n=35,d=16,R=1,K=471,9600.0189.06
KKn=35,d=16,R=1,K=5n=35,d=16,R=1,K=5460,2920.10611.39
KKn=35,d=16,R=1,K=6n=35,d=16,R=1,K=62,236,3320.64113.40
∣V∣\lvert V\rvertn=25,d=8,R=1,K=6n=25,d=8,R=1,K=6247,4300.07513.16
∣V∣\lvert V\rvertn=35,d=8,R=1,K=6n=35,d=8,R=1,K=62,006,5220.57312.90
∣V∣\lvert V\rvertn=50,d=8,R=1,K=6n=50,d=8,R=1,K=618,248,8604.72413.53
RRn=35,d=16,R=1,K=6n=35,d=16,R=1,K=62,236,3320.64113.40
RRn=35,d=16,R=2,K=6n=35,d=16,R=2,K=613,571,7123.48413.87

We profiled KnotState preprocessing while varying graph size ∣V∣|V|, maximum order KK, and local radius RR. For exact preprocessing, the number of evaluated subgraphs is

Nexact=∑s=1K[(∣V∣s)+∑u∈V(∣BR(u)∣−1s−1)].N_{\mathrm{exact}}=\sum_{s=1}^{K}\left[\binom{|V|}{s}+\sum_{u\in V}\binom{|B_R(u)|-1}{s-1}\right].

Thus, ∣V∣|V| and KK primarily affect global enumeration, while RR affects the sizes of the rooted neighborhoods BR(u)B_R(u). Each configuration was repeated three times. We report median wall-clock time and incremental peak host memory above the initialized process. The results confirm that exact preprocessing time is combinatorial in ∣V∣|V| and KK: increasing nn from 25 to 50 at K=6K=6 increases runtime by approximately 63×63\times. Increasing KK from 4 to 6 on SRG-like graphs increases runtime by approximately 36×36\times. The effect of RR is graph-dependent; on SRG$(35,16,6,8)$, R=2R=2 covers the full diameter and increases runtime by 5.4×5.4\times. In contrast, peak memory remains nearly constant because combinations are processed in fixed-size chunks rather than stored simultaneously. Table above excludes preprocessing because it was designed to compare the online neural-model cost after features have been computed: parameter count, training-time GPU memory, and inference latency. KnotState enumeration is a deterministic, training-independent CPU operation performed once and cached for reuse across epochs and inference. We agree that this one-time cost is important for end-to-end deployment and will clarify this distinction and report it separately. For larger graphs or higher orders, we use a hybrid estimator: blocks below an exact-enumeration threshold are computed exactly, while larger blocks are estimated from QQ uniformly sampled subsets,

H^(r)=NQ∑i=1Q1![ν(Si)=r].\widehat{H}(r)=\frac{N}{Q}\sum_{i=1}^{Q}\mathbf{1}\\!\left[\nu(S_i)=r\right].

With an exact-block limit of 2×1062\times10^6 and Q=10,000Q=10{,}000, preprocessing at R=1R=1 completed in 1.211.21 seconds for (n,K)=(35,10)(n,K)=(35,10) and 0.750.75 seconds for (n,K)=(100,10)(n,K)=(100,10), despite their much larger theoretical candidate spaces. The estimator is unbiased, with standard error p(1−p)/Q\sqrt{p(1-p)/Q}. Therefore, sampling makes higher-order statistics feasible, although large radii can remain expensive when rooted neighborhoods approach the entire graph.

Reviewer_xfvQOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper addresses the limited structural discrimination capability of GNNs and proposes KnotState and KSGL. KnotState treats the adjacency matrix of an induced subgraph as a linear operator over F2and uses its kernel dimension/rank deficiency as an algebraic invariant; KSGL further constructs local and global multi-order KnotState statistics, concatenates them, and feeds them into message-passing backbones such as GIN. The theoretical part provides an order hierarchy, shows that MPNNs are a special case, and gives conditional separation results beyond 3-WL; the experiments cover strongly regular graphs, BREC, and zeolite property prediction, and also report efficiency.

Critical strengths
  1. It proposes a computable local/global KnotState structural representation and establishes a theoretical connection between the order hierarchy and conditional separation beyond 3-WL. Introducing the algebraic dependency structure of induced subgraphs into GNN structural encoding is highly inspiring.
  2. The experimental coverage is relatively broad. The method validates structural discrimination and property prediction on SRG, BREC, and zeolite tasks; in Table 5, KSGL outperforms several higher-order methods in parameter size, GPU memory, and inference latency, indicating favorable efficiency potential at certain scales.
  3. Overall writing is clear, and the problem statement is well articulated.
Critical weaknesses
  1. It is not clarified whether “distinguish” in Theorem 5.1 / Corollary 5.1 occurs at the level of raw KnotState features or at the level of the final representation after MLP + GIN. The separation conclusions in the main text are mainly based on multiset differences in ΦsR(G)Φ_s^R (G), whereas the actual model additionally passes through MLPin, a log transform, and GIN message passing.
  2. The core computational cost is not sufficiently evaluated. KnotState requires enumerating induced subsets, which grows combinatorially with K,R, and graph size. There is a lack of measured time/memory as |V|,K, and R grow, as well as a feasibility analysis on large graphs.
Questions for authors

Q1. Please clarify the definition of “KSGL distinguishes G,H” in Theorem 5.1 and Corollary 5.1: does it mean that the raw KnotState features ΦsRΦ_s^R are distinguishable, or that the final graph representations after MLP+GIN are distinguishable?

Q2. Please report how the time and memory for KnotState feature enumeration/preprocessing vary with |V|, K, and R, and explain why Table 5 excludes offline preprocessing. Can the method still run on larger graphs or with higher K? Can sampling/approximation be used to estimate higher-order statistics?

6 comments

Thank you very much for the constructive feedback and valuable suggestions! Below we provide our detailed response to your question. We have also incorporated the changes (in blue) to the revised version.

Response to Q1:

We have strengthened the theoretical analysis by establishing the connection between KnotState signature separation (Theorem 5.1, p. 6; Proof in Appendix B.4, p. 18) and neural realizability through the complete MLP+GIN architecture (Theorem 5.3, p. 6; Proof in Appendix B.7, pp. 19).

Theorem 5.1 (Order-persistent separation) If κR(G,H)<∞\kappa_R(G,H)<\infty, then the cumulative KnotState signatures satisfy SK,R(G)≠SK,R(H)S_{K,R}(G) \neq S_{K,R}(H) for every K≥κR(G,H)K\geq\kappa_R(G,H). Proof is in Appendix B.4, p. 18.

First, the new version of Theorem 5.1 guarantees that if κR(G,H)<∞\kappa_R(G,H)<\infty, then the cumulative KnotState signatures satisfy SK,R(G)≠SK,R(H)S_{K,R}(G)\neq S_{K,R}(H) for every K≥κR(G,H)K\geq\kappa_R(G,H).

We present the proof of Theorem 5.1 (also stated on p. 18). Let k=κR(G,H)<∞k=\kappa_R(G,H)<\infty. By Definition 5.1, ΦkR(G)≠ΦkR(H)\Phi_k^R(G)\neq\Phi_k^R(H). For every K≥kK\geq k, projection of SK,R(G)S_{K,R}(G) onto its order-kk coordinates recovers ΦkR(G)\Phi_k^R(G). Thus, equality of the cumulative signatures would imply ΦkR(G)=ΦkR(H)\Phi_k^R(G)=\Phi_k^R(H), a contradiction. Hence, SK,R(G)≠SK,R(H)S_{K,R}(G)\neq S_{K,R}(H) for all K≥kK\geq k.

Now turning to Neural realizability of KnotState separation, we have now the following result:

Theorem 5.3 (Neural realizability of KnotState separation) Fix K,RK,R and any finite family of graphs G\mathcal{G}. With sufficiently expressive MLPs, GIN updates, and sum pooling, there exist shared parameters θ\theta such that hGθ≠hHθh_G^\theta\neq h_H^\theta if SK,R(G)≠SK,R(H)S_{K,R}(G)\neq S_{K,R}(H) for every G,H∈GG,H\in G.

We present the proof of Theorem 5.3 (also stated on p. 18--19). Since GG is finite, the set of node-level KnotState signatures is finite. As ρ(t)=log⁡(1+t)\rho(t)=\log(1+t) is injective, a sufficiently wide ReLU MLP can map each distinct signature to a distinct one-hot vector. Suppose the node representations at layer ℓ\ell are such one-hot encodings. Choose εℓ=1/2\varepsilon_\ell=1/2 in the GIN update. The aggregated vector becomes

au(ℓ)=32hu(ℓ)+∑v∈N(u)hv(ℓ).a_u^{(\ell)} = \frac{3}{2}h_u^{(\ell)} + \sum_{v\in N(u)}h_v^{(\ell)}.

Its half-integer coordinate identifies the root color, while its integer counts determine the multiset of neighbor colors. Hence, distinct rooted color-neighborhood configurations yield distinct aggregated vectors. Since only finitely many such vectors occur, a sufficiently wide ReLU MLP can map them injectively to new one-hot encodings. Repeating this construction through all GIN layers produces a color refinement that preserves every distinction present in the initial node-color multiset. Finally, sum pooling gives the histogram of the final one-hot colors. Distinct initial KnotState signature multisets therefore yield distinct graph embeddings under the constructed shared parameters.

To visualize both theoretical results more clearly, we provide an illustrative example of neural separation construction for the 4×44\times4 Rook graph GG and the Shrikhande graph HH (Theorem 5.2, p. 6; Appendix B.6, p. 19). Both graphs have vertex set Z4×Z4\mathbb Z_4\times\mathbb Z_4. In the 4×44\times4 Rook graph GG, two vertices (i,j)(i,j) and (k,l)(k,l) are adjacent if they share the same row or column. The Shrikhande graph HH is the Cayley graph Cay⁡(Z42,S)\operatorname{Cay}(\mathbb Z_4^2,S), where

S={(1,0),(3,0),(0,1),(0,3),(1,1),(3,3)}.S=\{(1,0),(3,0),(0,1),(0,3),(1,1),(3,3)\}.

Both graphs have 1616 vertices, 4848 edges, and identical degree sequences (6,…,6)(6,\ldots,6). Moreover, both are strongly regular with parameters (16,6,2,2)(16,6,2,2), although they are non-isomorphic. However, their fourth-order KnotState counts satisfy

HG4(0)=800≠768=HH4(0).H_G^4(0)=800\neq768=H_H^4(0).

For every admissible K≥4K\geq4, choose the shared input MLP to retain only the fourth-order global coordinate. Since ρ(t)=log⁡(1+t)\rho(t)=\log(1+t), the resulting initial node representations are

hu(0)(G)=log⁡801,hv(0)(H)=log⁡769.h_u^{(0)}(G)=\log801,\qquad h_v^{(0)}(H)=\log769.

In every GIN layer, set εℓ=0\varepsilon_\ell=0 and choose the MLP update to act as the identity. As both graphs are 66-regular, the GIN update becomes

hu(ℓ+1)=hu(ℓ)+∑v∈N(u)hv(ℓ)=7hu(ℓ).h_u^{(\ell+1)}=h_u^{(\ell)}+\sum_{v\in N(u)}h_v^{(\ell)}=7h_u^{(\ell)}.

After LL layers and sum pooling, the final graph embeddings are

h_G &=16\cdot7^L\log801,\\ h_H &=16\cdot7^L\log769. \end{aligned}$$ Consequently, $$h_G-h_H=16\cdot7^L\log\frac{801}{769}>0.$$ Hence, the complete MLP+GIN architecture provably separates the two graphs under a shared parameterization for every admissible $K\geq4$.

Response to Q2.

Please report how the time and memory for KnotState feature enumeration/preprocessing vary with |V|, K, and R, and explain why Table 5 excludes offline preprocessing.

We profiled KnotState preprocessing while varying graph size ∣V∣|V|, maximum order KK, and local radius RR. For exact preprocessing, the number of evaluated subgraphs is Nexact=∑s=1K[(∣V∣s)+∑u∈V(∣BR(u)∣−1s−1)].N_{\mathrm{exact}} = \sum_{s=1}^{K} \left[ \binom{|V|}{s} + \sum_{u\in V}\binom{|B_R(u)|-1}{s-1} \right]. Hence, ∣V∣|V| and KK primarily affect global enumeration, while RR affects the sizes of the rooted neighborhoods BR(u)B_R(u). Each setting was repeated three times. We report median wall-clock time and incremental peak host memory above the initialized process footprint.

The results in the table below confirm that exact preprocessing time is combinatorial in ∣V∣|V| and KK. Fixing K=6K=6 and increasing ∣V∣|V| from 25 to 50 increases runtime by approximately 63×63\times. Increasing KK from 4 to 6 on SRG-like graphs increases runtime by approximately 36×36\times. The effect of RR is graph-dependent. On SRG(35,16,6,8)\mathrm{SRG}(35,16,6,8), R=2R=2 covers the full diameter and increases runtime by 5.4×5.4\times. In contrast, peak memory remains nearly constant because combinations are streamed in fixed-size chunks rather than stored simultaneously. Table below excludes preprocessing overhead because it is designed to compare the online neural-model cost after features have been computed: parameter count, training-time GPU memory, and inference latency. KnotState enumeration is a deterministic, training-agnostic CPU operation performed once and cached for reuse across epochs and inference. We agree that this one-time cost is important for end-to-end deployment and will clarify this distinction and report preprocessing cost separately in the revision.

Sensitivity of exact KnotState preprocessing.

FactorConfiguration# Evaluated SubgraphsTime (s)Δ\DeltaRSS (MiB)
KKn=35,d=16,R=1,K=4n=35,d=16,R=1,K=471,9600.0189.06
KKn=35,d=16,R=1,K=5n=35,d=16,R=1,K=5460,2920.10611.39
KKn=35,d=16,R=1,K=6n=35,d=16,R=1,K=62,236,3320.64113.40
∥V∥\|V\|n=25,d=8,R=1,K=6n=25,d=8,R=1,K=6247,4300.07513.16
∥V∥\|V\|n=35,d=8,R=1,K=6n=35,d=8,R=1,K=62,006,5220.57312.90
∥V∥\|V\|n=50,d=8,R=1,K=6n=50,d=8,R=1,K=618,248,8604.72413.53
RRn=35,d=16,R=1,K=6n=35,d=16,R=1,K=62,236,3320.64113.40
RRn=35,d=16,R=2,K=6n=35,d=16,R=2,K=613,571,7123.48413.87

Response to Q2.

Can the method still run on larger graphs or with higher K? Can sampling/approximation be used to estimate higher-order statistics?

Thank you for this interesting suggestion on sampling/approximation! We address it in detail below.

Our initial KnotState computation relied on exact enumeration of induced subsets to establish rigorous structural discrimination. For an nn-vertex graph, the order-ss global distribution involves (ns)\binom{n}{s} subsets, each requiring a binary adjacency-nullity calculation. For example, a 46-vertex graph has approximately 4.08×1094.08\times10^9 order-10 subsets, illustrating the rapid combinatorial growth of exact enumeration. This makes exact evaluation increasingly computationally demanding at higher orders, particularly when graph preprocessing is included.

To extend KnotState to larger graphs and higher orders, we introduce a hybrid exact-sampling strategy. Candidate spaces containing at most 10410^4 subsets are evaluated exactly, while larger spaces are estimated through uniform subset sampling. The resulting estimators are unbiased and admit simultaneous Hoeffding concentration bounds. For the above example, global subset evaluations are reduced from approximately 4.08×1094.08\times10^9 to 8,192, corresponding to a 99.9998% reduction. We evaluated this strategy on all 400 official BREC graph pairs across orders K=1,…,20K=1,\dots,20, using 8,192 global samples per graph and 1,024 rooted samples per node whenever exact enumeration exceeded the threshold. The complete screening averaged 8.88 seconds per graph pair, with a peak process RSS of 226.91 MB. At K=20K=20, joint KnotState achieved 261 exact and five confidence-based separations, compared with 300 separations from full exact enumeration.

We now state the following proposition on the unbiasedness of sampled KnotState:

Proposition Let CC be a finite candidate family of induced subsets, either global or rooted. For each feasible nullity value rr, define pr(G)=1∣C∣∑U∈C1 [AG[U] over F2 has nullity r].p_r(G)=\frac{1}{|C|} \sum_{U\in C} 1\ [A_G[U] \text{ over } F_2 \text{ has nullity } r]. Let U1,…,UmU_1,\dots,U_m be independent uniform samples from CC, and define p^r(G)=1m∑i=1m1 [AG[Ui] over F2 has nullity r].\widehat p_r(G)=\frac{1}{m} \sum_{i=1}^{m} 1\ [A_G[U_i] \text{ over } F_2 \text{ has nullity } r]. Then p^r(G)\widehat p_r(G) is an unbiased estimator of pr(G)p_r(G), and E[p^r(G)]=pr(G).E[\widehat p_r(G)]=p_r(G). Moreover, for any ε>0\varepsilon>0, Pr(∣p^r(G)−pr(G)∣≥ε)≤2exp⁡(−2mε2).Pr\left( |\widehat p_r(G)-p_r(G)|\geq\varepsilon \right) \leq 2\exp(-2m\varepsilon^2). For MM estimated coordinates, a simultaneous confidence bound of at least 1−α1-\alpha is obtained by choosing εj=log⁡(2M/α)2mj,\varepsilon_j= \sqrt{\frac{\log(2M/\alpha)}{2m_j}}, where mjm_j is the sample size of coordinate jj.

Proof. For each sample UiU_i, uniform sampling gives E[1 [AG[Ui] over F2 has nullity r]]=pr(G).E\left[ 1\ [A_G[U_i] \text{ over } F_2 \text{ has nullity } r] \right]=p_r(G). By linearity of expectation, E[p^r(G)]=1m∑i=1mpr(G)=pr(G),E[\widehat p_r(G)]=\frac{1}{m}\sum_{i=1}^{m}p_r(G)=p_r(G), establishing unbiasedness. Since the indicators are independent and bounded in [0,1][0,1], Hoeffding's inequality yields the stated concentration bound. The simultaneous bound follows from the union bound over the MM estimated coordinates.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.