📂Graph Theory

Spectral Distance Between Graphs

Definition

Let us consider two graphs $G_{1}$ and $G_{2}$ with the number of vertices being $n$, and their adjacency matrices denoted as $A_{1}$ and $A_{2}$ respectively. We represent their eigenvalues, which are sorted in descending order, i.e., their spectra, as follows. $$A_{1} \mapsto \lambda_{1}^{(1)} \ge \cdots \ge \lambda_{n}^{(1)} \\ A_{2} \mapsto \lambda_{1}^{(2)} \ge \cdots \ge \lambda_{n}^{(2)}$$ The spectral distance between the two graphs is defined as follows^{1 2}. $$d \left( G_{1} , G_{2} \right) := \sqrt{ \sum_{k=1}^{n} \left( \lambda_{k}^{(1)} - \lambda_{k}^{(2)} \right)^{2} }$$

Explanation

At first glance, it might seem reasonable to define the distance between graphs based on the Hamming distance of the adjacency matrices themselves. However, simply comparing matrices element-wise is vulnerable to the order of vertices. On the other hand, the spectral distance has the advantage of being defined independently of labeling, due to its definition.