The Graph Isomorphism Problem

The graph isomorphism problem is a computational problem in the field of graph theory. It is known to be in NP but is not known to be NP-complete and has been a topic of interest in computer science and mathematics. Finding an efficient algorithm for determining graph isomorphism remains an open problem. In concrete terms, this means that if you can rearrange the vertices of one graph to match the structure of the other graph, preserving the connectivity between vertices, then the graphs are considered isomorphic.

Definition: Let $\mathcal{S}(n)$ denote the symmetric group of degree $n$ and $\mathcal{P}(n)$ the set of all $n \times n$ permutation matrices. The graphs $\mathcal{G}_A=(V_A, E_A)$ and $\mathcal{G}_B=(V_B, E_B)$ are called isomorphic if one of the two equivalent conditions is satisfied:

(i) There exists a permutation $\pi \in \mathcal{S}(n)$ such that $$(v_i, v_j) \in E_A \Longleftrightarrow (v_{\pi(i)}, v_{\pi(j)}) \in E_B$$ which preserves the edge weights.

(ii) There exists a permutation matrix $P \in \mathcal{P}(n)$ such that $$A = P^\top B P$$ or, equivalently, $P A = B P$.

In [1], we delve into the details of the graph isomorphism problem and proposes a sophisticated solution involving the relaxation technique using doubly stochastic matrices. The relaxation process centers around minimizing the cost function $$\min_{X \in \mathcal{D}(n)} \lVert X A - B X \rVert^2_F,$$ where $\mathcal{D}(n) = \{X \in \mathbb{R}^{n \times n} | X \geq 0, X \mathbb{1}_n = \mathbb{1}_n , \mathbb{1}_n^\top X = \mathbb{1}_n^\top\}$ is the set of doubly stochastic matrices, which is the convex hull of the set of all permutation matrices $\mathcal{P}(n)$. This is also known as Birkhoff ’s theorem. The convex nature of the relaxation enables the consideration of convex combinations of isomorphisms as potential solutions.

The optimization problem is reformulated through vectorization, wherein the cost function is expressed in terms of matrix vectorization: $$\min_{x \geq 0, Cx =d} x^\top H x,$$ with $H = (A^2 \otimes I_n\ ) - 2 (A \otimes B) + (I_n \otimes B^2) = ( A \otimes I_n - I_n \otimes B)^2$ and $ x = \text{vec}(X) $. This transformation results in a convex optimization problem, albeit not strictly convex, providing a mathematically elegant framework for addressing the graph isomorphism problem. The paper also explores isospectral graphs, shedding light on the rank and null space properties of corresponding matrices. The analysis focuses on eigenvalues and eigenvectors of adjacency matrices, contributing to a deeper understanding of the structural aspects of isomorphic graphs.

Eventually, we  turn the cost function into a constraint and optimize a different function instead: $$\min_{x \geq 0, Cx=d, Hx=0} -x^\top x,$$ where  the first two constraints enforce the stochasticity of $X$ and the third constraint guarantees that $X A = B X$. In order to solve this optimization problem, we use the Frank–Wolfe algorithm, which for a constrained convex optimization problem of the form $$\min_{x \in \mathcal{C}} f(x)$$ defined on a convex set C consists of the following two steps:

1.  Given a feasible initial condition $x^{(k)} \in \mathcal{C}$, compute an optimal solution $y^*$ of the linear problem $$\min_{y \in \mathcal{C}} \langle y, \nabla f(x^{(k)}) \rangle.$$

2. Define $x^{(k+1)}$ to be a convex combination of $x^{(k)}$ and $y^*$ , i.e., $$x^{(k+1)} = (1-\gamma) x^{(k)} + \gamma y^*,$$ where $0 \leq \gamma \leq 1$ is chosen so that $f(x^{(k+1)})$ is minimized.

The cost function we seek to minimize is not convex but strictly concave and the global minima are permutation matrices. Since we are just interested in showing that at least one permutation matrix exists that solves the graph isomorphism problem, the non-uniqueness of the optimal global solution is not a problem.

As a numerical example, we consider the Paley graph of size $n = 29$ shown in Figure 1 (a), whose automorphism
group contains 406 permutations, Despite the many symmetries, the Frank–Wolfe solver quickly converges to a permutation matrix as shown in Figures 1 (b)–(e). The number of iterations depends on the random permutation we choose to generate $\mathcal{G}_B$.
 

Figure 1: (a) Strongly regular Paley graph $\mathcal{G}_A$. The graph $\mathcal{G}_B$ is a random permutation of $\mathcal{G}_A$ . (b)–(e) Convergence of the Frank–Wolfe solver to a permutation matrix. The initial matrix $X^{(0)}$ is constant. The cost function first decreases only slowly, but then quickly converges to the optimal value. The matrix $X^{(3)}$ is a valid solution of the graph isomorphism problem.

The proposed approach in [1] transforms the graph isomorphism problem into a continuous optimization problem, making it potentially easier to solve than traditional combinatorial optimization problems. We extended existing techniques to strongly regular graphs, emphasizing the impact of symmetries and repeated eigenvalues on feasible solution spaces. The use of continuous relaxations is expected to pave the way for efficient numerical algorithms in solving the graph isomorphism problem and provide insights into the geometric properties and inherent symmetries of graphs. The formulation of the optimization problem is speculated to be applicable to quantum annealers, provided it can be reformulated as a quadratic unconstrained binary optimization (QUBO) problem.

[1] S. Klus, P. Gelß. Continuous optimization methods for the graph isomorphism problem. arXiv: 2311.16912