ORIGINAL ARTICLE: Jarek Duda (2024), Simple inexpensive vertex and edge invariants distinguishing dataset strongly regular graphs, arXiv:2402.04916. https://doi.org/10.48550/arXiv.2402.04916
In graph isomorphism problem, one of the most fundamental in computer science, we would like to test if two graphs are isomorphic. In 2015 László Babai has bounded its time complexity by quasi-polynomial
(O(exp(
c
ln(n)
))forsomec>0
), there remains open question if it can be reduced to polynomial. While for most of graphs such test is relatively easy, there are their families which are very difficult to distinguish, especially strongly regular graphs (SRGs) - much more difficult than just regular (constant degree), which vertices are already indistinguishable for standard Weisfeiler-Leman vertex invariants. There are proposed simple algebraic-combinatorial polynomial time vertex and edge invariants which were able to distinguish all graphs in dataset of 43717 SRGs of Edward Spence and usually their vertices, also some hints for potential proof of distinguishing all non-isomorphic graphs in the future especially using uniqueness of tensor decomposition theorem.
This notebook introduces to strongly regular graphs (SRGs) and proposed simple inexpensive invariants experimentally tested to distinguish all 43717 graphs in dataset of Edward Spence. The details can be found in arXiv:2402.04916, more discussion especially toward potential proof of solving graph isomorphism problem this way can be found in arXiv:1703.04456. Below is example of such vertex invariant: used Mathematica code, applied to presented as adjacency matrices 41 SRGs of 29-14-6-7 parameters. Colorful 25x12 matrices are the found vertex invariants (sorted numbers of closed length 3 paths inside neighborhoods), allowing to distinguish both entire graphs, and some their vertices e.g. to restrict automorphisms - they can only permute inside blocks of constant invariants, marked with blue separators.
Assume we work on undirected graphs with v vertices, given by adjacency matrix A:
A=
T
A
in
vv
{0,1}
. Regular graphs are defined as having constant degree
∑
j
A
ij
k
. Standard Weisfeiler-Leman isomorphism test builds vertex labels based on degrees of vertices, what does not work already for regular graphs - in practice resolved by extending the graph into one using vertices as subsets of the original vertices, what corresponds to exponential cost. Strongly regular graphs (SRGs) are even more difficult to distinguish - they are not only regular (k constant degree), but additionally: every two adjacent vertices have λ common neighbours, every two non-adjacent vertices have µ common neighbors. Finally they have four parameters: v-k-λ-μ, for example below are 2 non-isomorphic SRGs for 16-6-2-2 parameters:
In[]:=
As={{{0,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0},{1,0,1,1,0,0,0,1,1,1,0,0,0,0,0,0},{1,1,0,1,0,0,0,0,0,0,1,1,1,0,0,0},{1,1,1,0,0,0,0,0,0,0,0,0,0,1,1,1},{1,0,0,0,0,1,1,1,0,0,1,0,0,1,0,0},{1,0,0,0,1,0,1,0,1,0,0,1,0,0,1,0},{1,0,0,0,1,1,0,0,0,1,0,0,1,0,0,1},{0,1,0,0,1,0,0,0,1,1,1,0,0,1,0,0},{0,1,0,0,0,1,0,1,0,1,0,1,0,0,1,0},{0,1,0,0,0,0,1,1,1,0,0,0,1,0,0,1},{0,0,1,0,1,0,0,1,0,0,0,1,1,1,0,0},{0,0,1,0,0,1,0,0,1,0,1,0,1,0,1,0},{0,0,1,0,0,0,1,0,0,1,1,1,0,0,0,1},{0,0,0,1,1,0,0,1,0,0,1,0,0,0,1,1},{0,0,0,1,0,1,0,0,1,0,0,1,0,1,0,1},{0,0,0,1,0,0,1,0,0,1,0,0,1,1,1,0}},​​{{0,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0},{1,0,1,1,0,0,0,1,1,1,0,0,0,0,0,0},{1,1,0,0,1,0,0,1,0,0,1,1,0,0,0,0},{1,1,0,0,0,1,0,0,1,0,0,0,1,1,0,0},{1,0,1,0,0,0,1,0,0,0,1,0,1,0,1,0},{1,0,0,1,0,0,1,0,0,0,0,1,0,1,0,1},{1,0,0,0,1,1,0,0,0,1,0,0,0,0,1,1},{0,1,1,0,0,0,0,0,0,1,0,1,0,1,1,0},{0,1,0,1,0,0,0,0,0,1,1,0,1,0,0,1},{0,1,0,0,0,0,1,1,1,0,0,0,0,0,1,1},{0,0,1,0,1,0,0,0,1,0,0,1,1,0,0,1},{0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,1},{0,0,0,1,1,0,0,0,1,0,1,0,0,1,1,0},{0,0,0,1,0,1,0,1,0,0,0,1,1,0,1,0},{0,0,0,0,1,0,1,1,0,1,0,0,1,1,0,0},{0,0,0,0,0,1,1,0,1,1,1,1,0,0,0,0}}};​​Table[AdjacencyGraph[A],{A,As}]
Out[]=

,

The basic tool for the discussed invariants is well known matrix similarity test: if
∀
p1.v
Tr(
p
A
)Tr(
p
B
)
, then there exists orthogonal O such that
AOB
T
O
. It allows to easily test existence of orthogonal matrix/rotation between two matrices. In contrast, for graph isomorphism we need permutation - which can be characterized as orthogonal with
{0,1}
coefficients. So the remaining question is: among possible similarity matrices between A and B, is there a permutation?​ This question is especially difficult for SRGs as they always have only 3 different eigenvalues - 2 large degenerated eigenspaces in which such similarity matrices can freely rotate. For example with 1+9+6 degeneracy for the above 16-6-2-2 SRGs:
In[]:=
Table[es=Eigensystem[A];Row[{Column[es[[1]]],MatrixForm[es[[2]]]}],{A,As}]

6
-2
-2
-2
-2
-2
-2
-2
-2
-2
2
2
2
2
2
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
-1
0
0
-1
0
0
0
0
0
0
0
0
1
1
0
0
-1
0
-1
0
0
0
0
0
0
0
0
1
0
1
0
0
-1
-1
0
0
0
0
0
0
0
0
1
0
0
1
0
-1
0
0
0
-1
0
0
0
0
0
1
0
0
0
1
0
-1
0
0
-1
0
0
0
0
0
1
0
0
0
0
1
0
-1
0
-1
0
0
0
0
0
1
0
0
0
0
0
1
-1
0
0
0
0
-1
0
0
1
0
0
0
0
0
0
1
-1
0
0
0
-1
0
0
1
0
0
0
0
0
0
0
1
-1
0
0
-1
0
0
1
0
0
0
0
0
0
0
0
1
1
1
2
-1
-1
0
-1
-1
0
-1
-1
0
0
0
1
-1
-1
-1
-1
0
1
0
0
1
0
0
1
0
0
1
0
-1
-1
-1
-1
1
0
0
1
0
0
1
0
0
1
0
0
-1
-1
0
-1
0
0
0
0
0
0
1
1
1
0
0
0
-1
0
-1
-1
0
0
0
1
1
1
0
0
0
0
0
0
0
-1
-1
-1
1
1
1
0
0
0
0
0
0
0
0
0
,​​
6
-2
-2
-2
-2
-2
-2
-2
-2
-2
2
2
2
2
2
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
-2
0
1
-1
-2
0
1
0
0
0
0
0
0
0
1
0
0
1
0
-1
0
0
-1
0
0
0
0
0
0
1
0
0
1
0
-1
0
0
0
-1
0
0
0
0
0
1
0
0
1
0
0
-1
-1
0
0
0
0
0
0
0
1
0
0
0
1
0
-1
0
0
-1
0
0
0
0
0
1
0
0
0
0
2
-1
-1
0
-1
-1
0
1
0
0
1
0
0
0
0
0
1
-2
1
1
-1
-1
0
0
0
1
0
0
0
0
0
0
2
-2
0
0
-1
-1
0
1
1
0
0
0
0
0
0
0
0
-1
1
1
-1
-1
1
0
0
0
0
0
0
0
0
0
0
-1
-1
0
0
1
1
-1
0
0
0
0
0
0
0
1
0
-1
0
-1
1
0
1
0
-1
0
0
0
0
0
1
0
0
0
-1
1
-1
1
0
0
0
0
-1
0
0
1
0
0
-1
0
0
0
0
-1
-1
0
1
0
1
0
1
0
0
0
-1
0
1
-1
0
-1
-1
1
0
0
1
1
0
0
0
0
-1
1
0
0
-1
-1
-1
1
1
1
0
0
0
0
0
0

Normalizing above 9 or 6 dimensional subspace basis, and treating 16 columns as vectors, the question of the existence of permutation becomes: if such two sets of 16 vectors (e.g. 6 dimensional) differ only by rotation? Such sets of points cover sphere, with angles recreating the graph: all neighbors are in one constant angle, all non-neighbors are in a second constant angle:
Here are simple proposed vertex invariant as used for 41 SRGs of 29-14-6-7 at the top, which combinatorially are numbers of length p=3 closed paths in neighborhood of given vertex - sorted first separately for each vertex, then lexicographically among vertices. We can see they easily distinguish the two 16-6-2-2 SRGs as only the first has length 3 closed paths inside neighborhoods:
In[]:=
dinv[A_,p_:3]:=(ns=Table[Flatten[Position[a,1]],{a,A}];(*neighborhoods*)​​Sort[Table[Sort[Diagonal[MatrixPower[A[[n,n]],p]]],{n,ns}]]);​​Table[dinv[A,3],{A,As}]
Out[]=
{{{2,2,2,2,2,2},{2,2,2,2,2,2},{2,2,2,2,2,2},{2,2,2,2,2,2},{2,2,2,2,2,2},{2,2,2,2,2,2},{2,2,2,2,2,2},{2,2,2,2,2,2},{2,2,2,2,2,2},{2,2,2,2,2,2},{2,2,2,2,2,2},{2,2,2,2,2,2},{2,2,2,2,2,2},{2,2,2,2,2,2},{2,2,2,2,2,2},{2,2,2,2,2,2}},{{0,0,0,0,0,0},{0,0,0,0,0,0},{0,0,0,0,0,0},{0,0,0,0,0,0},{0,0,0,0,0,0},{0,0,0,0,0,0},{0,0,0,0,0,0},{0,0,0,0,0,0},{0,0,0,0,0,0},{0,0,0,0,0,0},{0,0,0,0,0,0},{0,0,0,0,0,0},{0,0,0,0,0,0},{0,0,0,0,0,0},{0,0,0,0,0,0},{0,0,0,0,0,0}}}

CITE THIS NOTEBOOK

Simple inexpensive vertex and edge invariants distinguishing dataset strongly regular graphs​
by Jarek Duda​
Wolfram Community, STAFF PICKS, February 13, 2024
​https://community.wolfram.com/groups/-/m/t/3121910