Testing graph isomorphism with powers of the adjacency matrix

Question

Suppose $A$ and $B$ are two square, symmetric, binary matrices with null diagonal representing the adjacency matrices of undirected graphs. If the multisets of the column-sums of $A$ and $B$ differ, then they are definitely not isomorphic. If the column-sum multisets are the same, then $A$ and $B$ might be isomorphic. Now I am wondering how the effectiveness of this test is improved by running it on $A^s$ and $B^s$ with a large integer $s$. Are there any two non-isomorphic graphs that "look" the same in this sense for all $s$ or even for an infinite number of values of $s$?

Answer 1

Slightly more generally than Dan's example, if a graph is $r$-regular, the column-sum multiset of $A^s$ is $(r^s,\ldots,r^s)$. So any two nonisomorphic $r$-regular graphs on $n$ vertices provide an example.

Answer 2

If $A = C_3 \cup C_3$ and $B = C_6$, then it seems like the column-sum multiset is always $\{2^s,2^s,2^s,2^s,2^s,2^s\}$. I'm still interested in references and broader explanations.

Answer 3

Testing graph isomorphism by multiset of column sums of adjacency with any power is the same as what first order Weisfeiler-Lehman (1-WL test known as vertex coloring) test does. So that approach is definitely not powerful than 1-WL test and you cannot distinguish not just isospectral graphs but also the graphs whose just maximum eigenvalues are the same.

1-WL test starts checking column-sum (actually not necessarily sum but any injective function) of Adjacency matrix. Let's think all vertices are the same, If $a_0=b_0={\bf1}$ is a vector of enough 1s, 1-WL test checks if multiset of $Aa_0$ and $Bb_0$ are equal or not. To do that generally, we can use the sort function, so we can check if $sort(Aa_0)=sort(Bb_0)$. If they are the same, then 1-WL relabel the result after concatenating of the current color of the vertex and the previous step ($a_1=[a_0,~Aa_0]$ and $b_1=[b_0,~Bb_0]$), relabel $a_1$ and $b_1$ and repeat the process. Relabbellin process can be seen as assigning a unique identifier for each unique row of the concatenated colors of both graphs ($[a_1;b_1]$).

In the second turn, it checks if $sort(Aa_1)=sort(Bb_1)$. If they are the same, again relabelling and again checking. If they are not equal in any step it concludes that the graphs are not isomorphic at all, or if the relabelling process cannot change the color of vertices ($a_{t+1}=a_{t}$) then the algorithm stops and supposed they are isomorphic (still they might not be isomorphic). So, what you describe is a simplified version of 1-WL test which performs $S$ number of iteration. Because if we enroll the update and change the relabelling process by just assign new color of vertex (neglect the old color of vertex by $a_1=Aa_0$), after $S$ iteration, it checks $sort(A^S{\bf1})=sort(B^S{\bf1})$ which is exactly what you asked!

This algorithm definitely not powerful and be able to just find very very easy cases. Check higher-order Weisfeiler-Lehman test procedures.