logo

Spectral Distance Between Graphs 📂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 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.


  1. Richard. (2008). A study of graph spectra for comparing graphs and trees: https://doi.org/10.1016/j.patcog.2008.03.011 ↩︎

  2. 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 ↩︎