A graph isomorphism algorithm using pseudoinverses (Q1913583)

This paper presents a heuristic algorithm of complexity at most \(O(nm^2)\) to test isomorphism between two graphs with \(m\) vertices and \(n\) edges. The traditional approach for isomorphism testing has been to use the fact that the adjacency matrices (or incidence matrices or Laplace matrices) of isomorphic graphs are permutationally equivalent. The novelty in the author's approach is the efficient use of the fact that the pseudoinverses of these matrices are also permutationally equivalent. The pseudoinverse of a matrix \(X\) is taken as the matrix \(X^+\) giving a solution \(\overline {x} = X^+b\) for the equations \(Xx = b\) which minimizes the squared error \((b - Xx)^T (b - Xx)\). If the \(m \times m\) matrix \(X\) of rank \(r\) is factorizable as \(X = UV\), where \(U\) is \(m \times r\) of rank \(r\) and \(V\) is \(r \times n\) of rank \(r\), then \(X^+ = V^+ U^+ = V^T(VV^T)^{-1} (U^TU)^{-1} U^T\) can be readily computed. Using a spanning tree of a graph (assumed connected), one gets a traditional canonical partition of the incidence matrix \(M\) as well as the Laplacian \(MM^T = K\) which facilitates the use of the above formula for the computation of \(M^+\) or \(K^+\). Concentrating on \(K^+\), the authors compute the diagonals of \(K^+_1\) and \(K^+_2\) (the \(K^+\) of the candidate graphs \(G_1\) and \(G_2\)) and use them to find a one-one correspondence between the vertices of \(G_1\) and \(G_2\). If this happens to be an isomorphism (preserves adjacencies) one is through. It is easier to detect non-isomorphism. An alternative approach of trying to match each column of \(K^+_1\) with a column of \(K^+_2\) iteratively has also been studied. This proves efficient in some cases. The methods are illustrated with two examples. Inbuilt functions for pseudoinverses in `Mathematica' have been used.