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 follows1 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.
Richard. (2008). A study of graph spectra for comparing graphs and trees: https://doi.org/10.1016/j.patcog.2008.03.011 ↩︎
Wills P, Meyer FG (2020) Metrics for graph comparison: A practitioner’s guide. PLoS ONE 15(2): e0228728. https://doi.org/10.1371/journal.pone.0228728 ↩︎