- 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 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 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 ? 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
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 / Model | Extension (100) |
|---|---|
| GIN | 0 |
| Degree + GIN | 0 |
| Clustering coefficient + GIN | 5 |
| Triangle count + GIN | 5 |
| Clique counts (3--4) + GIN | 20 |
| Graphlet counts (3 nodes) + GIN | 5 |
| Graphlet counts (4 nodes) + GIN | 84 |
| Cycle counts (3--5) + GIN | 96 |
| Adjacency rank/nullity + GIN | 57 |
| 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 , 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 increases from 5 to 9, KSGL progressively improves from 96 to 100 separations, achieving complete separation at , which is maintained at . 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 , 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 and any finite graph family , with sufficiently expressive MLPs, GIN updates, and sum pooling, there exist shared parameters such that
for every . 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.
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 n-vertex graph, the global order-s distribution involves (sn) induced subsets, each requiring a binary adjacency-nullity calculation. The feasible global orders are 1≤s≤min(K,n); for a root u, the local orders are bounded by min(K,∣BR(u)∣). The maximum order examined on BREC is K=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∣, maximum order K, and local radius R. For exact preprocessing, the number of evaluated subgraphs is
Nexact=∑s=1K[(s∣V∣)+∑u∈V(s−1∣BR(u)∣−1)].
Hence, ∣V∣ and K primarily affect global enumeration, while R affects the sizes of the rooted neighborhoods BR(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:
The results confirm that exact preprocessing time is combinatorial in ∣V∣ and K. Fixing K=6 and increasing ∣V∣ from 25 to 50 increases runtime by approximately 63×. Increasing K from 4 to 6 on SRG-like graphs increases runtime by approximately 36×. The effect of R is graph-dependent. On SRG(35,16,6,8), R=2 covers the full diameter and increases runtime by 5.4×. 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.