Adjacency-degree algebras and spectral determination of graphs
arXiv:2607.21494
2026
Architecture
2 ideas extracted · analyzed Aug 30, 2026
What the math gives to ML
The paper identifies a noncommutative adjacency-degree algebra whose principal cyclic module captures information obtained by repeatedly applying adjacency and degree operators to the all-ones vector. Its strongest transferable asset is that scalar moments of words in A and D are graph-isomorphism invariants, and the complete collection determines every tree, while ordinary color refinement can fail on related graphs. This suggests augmenting graph neural networks with degree-aware noncommutative walk features rather than only powers of A or standard 1-WL messages. A second use is to compress message passing into the principal module using operator identities such as AK=KC_A and DK=KC_D, potentially reducing computation on graphs with few structural orbits.
Ideas from this paper
Unverified
2026
Build a low-dimensional basis for the principal module generated by the all-ones vector, then perform adjacency and degree propagation in compressed coordinates. On forests, the paper states that this module equals the automorphism-orbit module, so the reduced representation can preserve principal adjacency-degree information while using far fewer coordinates than the number of vertices.
Useful6/10
Difficulty6/10
Novelty7/10
Unverified
2026
Augment a graph neural network with features generated by noncommutative words in the adjacency matrix and diagonal degree matrix. Ordered patterns such as AD^2A and DADA distinguish where degree information occurs along a walk; the paper proves that the full scalar moment family determines every tree.
Useful6/10
Difficulty4/10
Novelty6/10