Algebraic Knot Deep Graph Learning for Structural Generalization

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 ${\mathbb{F}}_2$. 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/