# Geodesic Distance Between Graphs: A Spectral Metric for Assessing the
Stability of Graph Neural Networks

Soumen Sikder Shuvo Ali Aghdaei Zhuo Feng
Stevens Institute of Technology
{sshuvo, aaghdae1<EMAIL_ADDRESS>

###### Abstract

This paper presents a spectral framework for assessing the generalization and
stability of Graph Neural Networks (GNNs) by introducing a Graph Geodesic
Distance (GGD) metric. For two different graphs with the same number of nodes,
our framework leverages a spectral graph matching procedure to find node
correspondence so that the geodesic distance between them can be subsequently
computed by solving a generalized eigenvalue problem associated with their
Laplacian matrices. For graphs with different sizes, a resistance-based
spectral graph coarsening scheme is introduced to reduce the size of the
bigger graph while preserving the original spectral properties. We show that
the proposed GGD metric can effectively quantify dissimilarities between two
graphs by encapsulating their differences in key structural (spectral)
properties, such as effective resistances between nodes, cuts, the mixing time
of random walks, etc. Through extensive experiments comparing with the state-
of-the-art metrics, such as the latest Tree-Mover’s Distance (TMD) metric, the
proposed GGD metric shows significantly improved performance for stability
evaluation of GNNs especially when only partial node features are available.

##  1 Introduction

In the era of big data, comparison and distinction between data points are
important tasks. A graph is a specific type of data structure that represents
the connections between a group of nodes or agents. Comparing two graphs often
involves using a pairwise distance measure, where a small distance indicates a
high structural similarity and vice versa. To understand the generalization
between distribution shifts, it is important to use an appropriate measure of
divergence between data distributions, both theoretically and experimentally
Chuang et al. [2020]. Determining suitable distance metrics for non-Euclidean
data entities, like graphs with or without node attributes, which are
fundamental to many graph learning methods such as graph neural networks
(GNNs), remains a significant challenge, even though distance metrics for data
points in Euclidean space are readily available. The need to develop new
analytical techniques that allow the visualization, comparison, and
understanding of different graphs has led to a rich field of research study
Haslbeck and Waldorp [2018]. This study dives into the exploration of a novel
framework for computing geometric distances between graphs, which can be
immediately leveraged for many graph-based machine learning (ML) tasks, such
as the stability evaluation of GNNs.

Many distance metrics for comparing graphs have previously been proposed
Borgwardt et al. [2020]. Some of them are merely based on graph local
structures Haussler et al. [1999], Xu et al. [2013], Zhu et al. [2020],
Fernández and Valiente [2001], Bunke and Shearer [1998], whereas others
exploit both graph structural properties and node attributes Shervashidze et
al. [2011], Morris et al. [2019]. For example, the Graph Edit Distance (GED)
has been proposed to measure the distance between graphs considering the
number of changes needed to match one graph to another Sanfeliu and Fu [1983],
Gao et al. [2010], Li et al. [2017]; Distance metrics based on the graph
kernel have also been investigated Shervashidze et al. [2011], Vishwanathan et
al. [2010], such as the Wasserstein Weisfeiler-Leman metric (WWL) Morris et
al. [2019] and the Gromov–Wasserstein metric Mémoli [2011], which allow
computing graph distances based on low-dimensional graph representations or
optimal transport (OT) Titouan et al. [2019], Chapel et al. [2020], leading to
the development of the state-of-the-art graph distance metric called Tree
Mover’s Distance (TMD) Chuang and Jegelka [2022].

However, the existing graph distance metrics have distinct limitations. For
example, the GED metric can capture local node or edge changes but struggles
with global perturbations Sanfeliu and Fu [1983], Gao et al. [2010], Li et al.
[2017]; the WWL and TMD metrics heavily rely on node features (attributes) for
calculating the distance between graphs, leading to degraded performance when
only partial node features are available Rossi et al. [2022], Chen et al.
[2022].

To address the limitations of prior methods, we propose a Graph Geodesic
Distance (GGD) metric that can be computed through the following steps: for
two graphs of the same size (with $n$ nodes), (1) a spectral graph matching
procedure is exploited for finding the node correspondence between two graphs,
and (2) a geodesic distance metric is defined on the cone of $n\times n$
modified graph Laplacians that can be regarded as a Riemannian manifold Lim et
al. [2019]. For graphs of different sizes, we introduce a resistance-based
spectral graph coarsening scheme to transform the larger graph into a smaller
one suitable for the GGD evaluation. We show that the proposed GGD metric can
theoretically capture key structural (spectral) dissimilarities between two
graphs, such as mismatches in Laplacian eigenvalues/eigenvectors, cuts,
effective-resistance distances, etc.

One distinct advantage of the proposed GGD metric is its capability to compute
distances between graphs based on their spectral (structural) properties,
while including node feature information into our framework can further
improve the accuracy. Therefore, GGD is suitable for analyzing many real-world
graphs that may only have partial or even no node features. Moreover, the
proposed framework for computing GGDs is more computationally efficient than
existing OT-based metrics, such as the TMD metric. Our preliminary results
show that the GGD metric has a better correlation with established GNN output
compared to the state-of-the-art TMD metric Chuang and Jegelka [2022]. It also
allows us to achieve up to $10\%$ accuracy gain and $9\times$ runtime speedup
in graph classification tasks than TMD.

##  2 Existing Graph Distance Metrics

Graph Edit Distance (GED) For non-attributed graph data, a common and simple
distance metric is GED. Sanfeliu and Fu [1983], Gao et al. [2010]. Given a set
of graph edit operations, also known as elementary graph operations, the GED
between two graphs $G_{1}$ and $G_{2}$, written as $\text{GED}(G_{1},G_{2})$,
can be defined as:

$\text{GED}(G_{1},G_{2})=\min\limits_{\begin{subarray}{c}(e_{1},\ldots,e_{k})\in\mathcal{P}(G_{1},G_{2})\end{subarray}}\sum_{i=1}^{k}c(e_{i})$
(1)

where $\mathcal{P}\left(G_{1},G_{2}\right)$ denotes the set of edit operations
transforming $G_{1}$ into a graph isomorphism of $G_{2}$, $c(e_{i})$ is the
cost of edit operation $e_{i}$. The set of elementary graph edit operators
typically includes node insertion, node deletion, node substitution, edge
insertion, edge deletion, and edge substitution.

Tree Mover’s Distance (TMD) TMD is a pseudometric for measuring distances
between simple graphs, extending the concept of WWL to multisets of tree
structures Chuang and Jegelka [2022]. By progressively adding neighboring
nodes to the previous node at each level, we obtain the computation tree of a
node. These tree structures are crucial in graph analysis Weisfeiler and Leman
[1968], Pearson [1905] and graph kernels Ramon and Gärtner [2003],
Shervashidze et al. [2011]. TMD uses hierarchical optimal transport (HOT) to
analyze these computational trees from input graphs. For a graph $G=(V,E)$
with node features $f_{v}\in\mathbb{R}^{s}$ for node $v\in V$, let
$T_{v}^{1}=v$, and $T_{v}^{L}$ be the depth-L computation tree of node $v$.
The multiset of these trees for $G$ is $T_{G}^{L}=\\{T_{v}^{L}\\}_{v\in V}$.
The number and shape of trees must match to calculate optimal transport
between two multisets of trees. If multisets are uneven, they are augmented
with blank nodes. For multisets $T_{p}$ and $T_{q}$, the augmenting function
$\sigma$ adds blank trees to equalize their sizes. A blank tree
$T_{\mathbb{O}}$ has a single node with a zero vector feature
$\mathbb{O}_{p}\in\mathbb{R}^{s}$:

$\sigma:(T_{p},T_{q})\rightarrow\left(T_{p}\cup
T_{\mathbb{O}}^{\max(|T_{q}|-|T_{p}|,0)},T_{q}\cup
T_{\mathbb{O}}^{\max(|T_{p}|-|T_{q}|,0)}\right)$ (2)

Let $X=\left\\{x_{i}\right\\}_{i=1}^{k}$ and
$Y=\left\\{y_{i}\right\\}_{j=1}^{k}$ be two data multisets and
$C\in\mathbb{R}^{k\times k}$ be the transportation cost for each data pair:
$C_{ij}=d\left(x_{i},y_{j}\right)$, where $d$ is the distance between $x_{i}$
and $y_{j}$. The unnormalized Optimal Transport between $X$ and $Y$ can be
defined as:

$\mathrm{OT}_{d}(X,Y):=\min_{\gamma\in\Gamma(X,Y)}\langle
C,\gamma\rangle\quad\Gamma(X,Y)=\left\\{\gamma\in\mathbb{R}_{+}^{m\times
m}\mid\gamma\mathbb{1}_{m}=\gamma^{\top}\mathbb{1}_{m}=\mathbb{1}_{m}\right\\}$
(3)

Here $\Gamma$ is the set of transportation plans that satisfies the flow
constrain $\gamma\mathbb{1}_{m}=\gamma^{\top}\mathbb{1}_{m}=\mathbb{1}_{m}$
Chuang and Jegelka [2022].

The distance between two trees $T_{p}$ and $T_{q}$ with roots $r_{p}$ and
$r_{q}$ is defined recursively:

$\text{TD}_{w}\left(T_{p},T_{q}\right):=\begin{cases}\left\|f_{r_{p}}-f_{r_{q}}\right\|+w(L)\cdot\mathrm{OT}_{\mathrm{TD}_{w}}\left(\sigma\left(T_{r_{p}},T_{r_{q}}\right)\right)&\text{if
}L>1\\\ \left\|f_{r_{p}}-f_{r_{q}}\right\|&\text{otherwise}\end{cases}$ (4)

where $L$ is the maximum depth of $T_{p}$ and $T_{q}$, and $w$ is a depth-
dependent weighting function.
Subsequently, the concept of distance from individual trees is enlarged to
entire graphs. For graphs $G_{1}$ and $G_{2}$, with multisets
$\mathbf{T}_{G_{1}}^{L}$ and $\mathbf{T}_{G_{2}}^{L}$ of depth-L computation
trees, the Tree Mover’s Distance is:

$\text{TMD}_{w}^{L}(G_{1},G_{2})=\text{OT}_{\mathrm{TD}_{w}}(\sigma(\mathbf{T}_{G_{1}}^{L},\mathbf{T}_{G_{2}}^{L}))$
(5)

##  3 GGD: A Geodesic Distance Metric for Graphs

##### Laplacian matrices on the Riemannian manifold

To overcome the limitations of the previous OT-based graph distance metrics
Chuang and Jegelka [2022], we aim to develop a new pseudometric that can
effectively encapsulate topological differences between graphs. One way to
represent a simple graph is through its Laplacian matrix, which is a Symmetric
Positive Semidefinite matrix. Adding a small positive value to each diagonal
element will allow us to transform the original Laplacian matrix into a
Symmetric Positive Definite (SPD) one, which is called the modified Laplacian
matrix in this work. Then we can consider the cone of such modified Laplacian
matrices as a natural Riemannian manifold Lim et al. [2019], where each
modified Laplacian has the same dimensions (same number of rows/columns) and
can be regarded as a data point on the Riemannian manifold Vemulapalli and
Jacobs [2015], Pennec et al. [2006]. In the last, the geodesic distance
between two graphs can be defined as the shortest path distance on the
Riemannian manifold if their node correspondence is known in advance. This
approach is more appropriate than directly comparing the graphs in the
Euclidean space Lim et al. [2019], Crane et al. [2020], Huang et al. [2015].
We will later show (Section 4.3) that such a geodesic distance metric can
effectively capture structural (spectral) mismatches between graphs.

##### A spectral framework for computing GGDs

Before computing GGDs, it is necessary to establish the node-to-node
correspondence between two graphs. This can be achieved by leveraging existing
graph-matching techniques Livi and Rizzi [2013], Emmert-Streib et al. [2016],
Caetano et al. [2009]. In this work, we will leverage a recent spectral graph
matching framework that has been shown to recover accurate matching with high
probability Fan et al. [2020].

The proposed GGD metric can be computed in the following two phases. Phase 1
consists of a spectral graph matching step, using combinatorial optimization
with the eigenvalues/eigenvectors of the graph adjacency matrices to identify
the approximate node-to-node correspondence. Phase 2 computes the GGD between
the modified Laplacian matrices of the matched graphs by exploiting
generalized eigenvalues. The proposed GGD metric differs from previous OT-
based graph distance metrics in its ability to accurately represent structural
discrepancies between graphs, enabling us to uncover the topological
variations between them more effectively. Since only the graph Laplacian
(adjacency) matrix is required to calculate the GGD, our metric can even work
effectively for graphs without node feature information.

##### A motivating example

Let’s consider a simple graph $G_{1}$, characterized by an almost ring-like
topology, as shown in Figure 1. We also create two other graphs $G_{2}$ and
$G_{3}$ by inserting an extra edge into $G_{1}$ in different ways. Note that
the additional edge in $G_{3}$ will have a greater impact on $G_{1}$’s global
structure since it connects two further nodes.

Table 1: Distance between graphs with simple perturbation

Graph |  |  |  |
---|---|---|---|---
Pairs |  Distance Metrics (Normalized) |  |  |
|  GGD | TMD with |  |
NF, L = 4 |  TMD without |  |  |
NF, L = 4 |  GED |  |  |
$G_{1},G_{2}$ |  0.623 | 0.689 | 0.970 |  1
$G_{1},G_{3}$ |  0.855 | 0.711 | 1 |  1
$G_{2},G_{3}$ |  1 | 1 | 0.333 |  1

We compute the normalized distances (the largest distance always equals one)
between the aforementioned three graphs using different metrics (GED, TMD, and
GGD) and report the results in Table 3. As observed, $G_{2}$ and $G_{3}$ have
distances similar to $G_{1}$ when the TMD metric is adopted without using node
features (NFs). On the other hand, the TMD metric can produce similar results
as the proposed GGD metric when node features are fully utilized. Not
surprisingly, the GED always produces the same distances since only one edge
has been added. The above results imply that the GED and TMD (without using
NFs) metrics may not properly capture the dissimilarities in the structural
(spectral) properties of the graphs.

##  4 Computing GGDs Between Graphs of the Same Size

###  4.1 Phase 1: Spectral Graph Matching for Finding Node Correspondence

Computing the GGD metric between two input graphs requires solving a graph
matching problem in advance. Graph matching techniques can be used to
establish node-to-node correspondence by seeking a bijection between node sets
to maximize the alignment of edge sets Livi and Rizzi [2013], Emmert-Streib et
al. [2016], Caetano et al. [2009]. This combinatorial optimization problem can
be cast into a Quadratic Assignment Problem, which is NP-hard to solve or
approximate Fan et al. [2020], Wang et al. [2020].

Figure 1: Graphs with simple perturbations

In this study, we will exploit a spectral graph matching method called GRAMPA
(GRAph Matching by Pairwise eigen-Alignments) Fan et al. [2020] to find the
approximate node correspondence between two graphs. GRAMPA starts with
comparing the eigenvectors of the adjacency matrices of the input graphs.
Instead of comparing only the eigenvectors responding to the largest
eigenvalues, it considers all pairs of eigenvectors/eigenvalues to generate a
similarity matrix. This similarity matrix can be constructed by summing up the
outer products of eigenvector pairs, weighted by a Cauchy kernel Fan et al.
[2020]. Subsequently, a rounding procedure will be performed to determine the
optimal match between nodes employing the similarity matrix.

######  Definition 4.1 (Similarity Matrix).

Let $G_{1}$ and $G_{2}$ be two undirected graphs with $n$ nodes, and let their
weighted adjacency matrices be $A_{1}$ and $A_{2}$, respectively. The spectral
decompositions of $A_{1}$ and $A_{2}$ are expressed as follows:
$A_{1}=\sum_{i=1}^{n}\zeta_{i}u_{i}u_{i}^{\top}\quad\text{and}\quad
A_{2}=\sum_{j=1}^{n}\mu_{j}v_{j}v_{j}^{\top}$, where the eigenvalues are
ordered such that $\zeta_{1}\geq\ldots\geq\zeta_{n}$ and
$\mu_{1}\geq\ldots\geq\mu_{n}$. The similarity matrix
$\widehat{X}\in\mathbb{R}^{n\times n}$ is defined as:

$\widehat{X}=\sum_{i,j=1}^{n}w\left(\zeta_{i},\mu_{j}\right)\cdot
u_{i}u_{i}^{\top}\mathbf{J}v_{j}v_{j}^{\top},\quad\text{where}\quad
w(x,y)=\frac{1}{(x-y)^{2}+\eta^{2}}$ (6)

Here, $\mathbf{J}\in\mathbb{R}^{n\times n}$ denotes an all-one matrix and $w$
is the Cauchy kernel of bandwidth $\eta$.

The permutation estimate matrix $\widehat{\pi}$ can be obtained by rounding
$\widehat{X}$, typically achieved by solving the Linear Assignment Problem
(LAP):

$\widehat{\pi}={\operatorname{argmax}}\sum_{i=1}^{n}\widehat{X}_{i,\pi(i)}$
(7)

This LAP can be solved efficiently using the Hungarian Algorithm Fan et al.
[2020], Kuhn [1955], where:

$\widehat{\pi}(i)=\underset{j}{\operatorname{argmax}}\widehat{X}_{ij}.$ (8)

######  Lemma 4.1 (Graph Matching Recovery).

Given symmetric matrices $A$, $B$ and $Z$ from the Gaussian Wigner model,
where $B_{\pi^{*}}=A+\sigma Z$, there exist constants $c,c^{\prime}>0$ such
that if $1/n^{0.1}\leq\eta\leq c/\log n$ and $\sigma\leq c^{\prime}\eta$, then
with probability at least $1-n^{-4}$, GRAMPA Algorithm correctly recovers the
permutation matrix $\pi^{*}$ from the Similarity matrix $\widehat{X}$ Fan et
al. [2020]. Its proof can be found in the supporting documents A.2.

Once $\widehat{\pi}$ is obtained, the best-matched mirrors of the input graphs
are:

$\textnormal{Best Match to }B=\widehat{\pi}\cdot
A\cdot\widehat{\pi}^{\top},\quad\textnormal{Best Match to
}A=\widehat{\pi}^{\top}\cdot B\cdot\widehat{\pi}$ (9)

In practice, the graph matching performance is not too sensitive to the choice
of tuning parameter $\eta$. For small-sized graphs, such as the MUTAG
datasetMorris et al. [2020], setting $\eta=0.5$ yields satisfactory results in
matching. In Appendix A.3, the effect of $\eta$ for computing GGDs has been
comprehensively analyzed.

###  4.2 Phase 2: Computing Geodesic Distances Between Graph Laplacians

The GGD metric can be formally defined as the infimum length of geodesics
connecting two data points in the Riemannian manifold formed by the cone of
the modified graph Laplacian matrices Lim et al. [2019]. This distance metric
can be imagined as a matrix representation of the geometric distance
$|\log(a/b)|$ between two positive numbers $a,b$ Bonnabel and Sepulchre
[2010], Shamai and Kimmel [2017], Owen and Provan [2010].

######  Definition 4.2 (Graph Geodesic Distance).

Let $\mathcal{L}_{1}$ and $\mathcal{L}_{2}\in\mathbb{S}_{++}^{n}$ denote two
modified Laplacian matrices corresponding to two matched graphs $G_{1}$ and
$G_{2}$ both having $n$ nodes, then their Graph Geodesic Distance denoted by
$GGD(G_{1},G_{2}):\mathbb{S}_{++}^{n}\times\mathbb{S}_{++}^{n}\rightarrow\mathbb{R}_{+}$,
is defined as:

$GGD(G_{1},G_{2})=\left[\sum_{i=1}^{n}\log^{2}(\lambda_{i}(\mathcal{L}_{1}^{-1}\mathcal{L}_{2}))\right]^{1/2}$
(10)

where $\lambda_{i}$ are the generalized eigenvalues computed with the matrix
pencil ($\mathcal{L}_{1}$, $\mathcal{L}_{2}$).

###  4.3 Connection between GGD and Graphs’ Structural Mismatches

Figure 2: The cut mismatch (for the node set $S$) between two simple graphs is
$\frac{6}{2}=3$

For two graphs $G_{1}$ and $G_{2}$ that share the same node set $V$ (node
correspondence is known in advance), let $L_{1}$ and $L_{2}$ be their
respective Laplacian matrices. Consider a node subset denoted by $S$ and its
complement denoted by $S^{\prime}$. We assign each node in $S$ a value of $1$,
and each node in $S^{\prime}$ a value of $0$. Then the node set $S$ can be
defined as:

$S\stackrel{{\scriptstyle\text{def}}}{{=}}\\{v\in V:x(v)=1\\}$

The graph cut for node subset $S$, corresponding to the number of edges
crossing $S$ and $S^{\prime}$ in graph $G_{1}$ can be computed by:

$\text{cut}_{G_{1}}(S,S^{\prime})=x^{T}L_{1}x$

As illustrated in Figure 2, the node subset $S$ has six edges crossing the
boundary in $G_{1}$ but only two in $G_{2}$. This cut mismatch can be related
to the generalized eigenvalue of the matrix pencil $(L_{1},L_{2})$ using the
Generalized Courant-Fischer Minimax Theorem Golub and Van Loan [2013], Feng
[2020].

######  Lemma 4.2 (The Generalized Courant-Fischer Minimax Theorem).

Given two Laplacian matrices $L_{1},L_{2}\in\mathbb{R}^{n\times n}$ such that
$\operatorname{null}\left(L_{2}\right)\subseteq\operatorname{null}\left(L_{1}\right)$,
the $k$-th largest generalized eigenvalue of $L_{1}$ and $L_{2}$ can be
computed as follows for $1\leq k\leq\operatorname{rank}\left(L_{2}\right)$:

$\lambda_{k}=\min_{\begin{subarray}{c}\operatorname{dim}(U)=k\\\
U\perp\operatorname{null}\left(L_{2}\right)\end{subarray}}\max_{x\in
U}\frac{x^{\top}L_{1}x}{x^{\top}L_{2}x}$ (11)

This theorem allows us to find the upper bound of the maximum cut mismatch
between two graphs by computing the most dominant generalized eigenvalue via
the following optimization problem Feng [2020]:

$\lambda_{\max}=\max_{\begin{subarray}{c}|x|\neq 0\\\
x^{\top}\mathbb{1}=0\end{subarray}}\frac{x^{\top}L_{1}x}{x^{\top}L_{2}x}\geq\max_{\begin{subarray}{c}|x|\neq
0\\\
x(v)\in\\{0,1\\}\end{subarray}}\frac{x^{\top}L_{1}x}{x^{\top}L_{2}x}=\max\frac{cut_{G_{1}}(S,S^{\prime})}{cut_{G_{2}}(S,S^{\prime})}$
(12)

Based on (12), we can infer that the dominant generalized eigenvalue is
closely related to the most significant graph cut mismatch between graphs
$G_{1}$ and $G_{2}$. As a result, $\lambda_{\max}=\lambda_{1}$ connects to the
upper bound of the cut mismatch between graphs $G_{1}$ and $G_{2}$, whereas
$\lambda_{\min}=\lambda_{n}$ connects to the upper bound of the cut mismatch
between graphs $G_{2}$ and $G_{1}$. Similarly, the second-largest (smallest)
eigenvalues correspond to the next most significant cut mismatches. It is also
obvious that the generalized eigenvalues close to $1$ will correspond to the
minimum cut mismatches between two graphs.

##  5 Computing GGDs for Graphs with Different Sizes

##### Submatrix selection methods

To calculate geodesic distances between SPD matrices of different sizes, prior
studies have proposed a submatrix adaptation method Lim et al. [2019]. In this
approach, a principle submatrix with the same size as the smaller matrix is
obtained from the larger matrix Ye and Lim [2016], and subsequently used to
calculate the GGD. Furthermore, this method can be extended to project the
smaller matrix into a larger one with the same size as the larger matrix Lim
et al. [2019]. While these methods are efficient for handling SPD matrices,
for our application taking the submatrix of the modified Laplacian can lose
important nodes/edges, compromising critical graph structural properties.

##### Graph coarsening methods

In this work, we will leverage spectral graph coarsening to address the issue.
Spectral graph coarsening is a widely adopted process Loukas [2019], Aghdaei
and Feng [2022] for reducing graph sizes while preserving key spectral
(structural) properties, such as the Laplacian eigenvalues/eigenvectors.
Recent spectral graph coarsening methods aim to decompose an input graph into
many distinct node clusters, so that a reduced graph can be formed by treating
each node cluster as a new node, with a goal of assuring that the reduced
graph will approximately retain the original graph’s structure Loukas [2019],
Han et al. [2024], Aghdaei and Feng [2022]. Therefore, when computing GGDs for
graphs of different sizes, we can first adopt spectral graph coarsening to
transform the bigger graph into a smaller one, so that our framework in
Section 4 can be subsequently utilized. However, existing state-of-the-art
graph coarsening methods do not allow us to precisely control the size of the
reduced graphs.

###  5.1 Our Approach: Spectral Graph Coarsening by Effective Resistances

In this work, we introduce a spectral graph coarsening method using effective-
resistance clustering Aghdaei and Feng [2022]. Our approach starts with
estimating the effective resistances of all edges in the original graph. We
can also incorporate the difference between node feature (if available)
vectors as an additional parameter. In the graph coarsening phase, our method
will rank edges according to their resistance distances and only the top few
edges with the smallest resistances will be coarsened into new nodes. This
approach enables precise control over the size of the reduced graphs while
preserving crucial structural properties, such as the eigenvalues/eigenvectors
of the adjacency matrices, which are essential for the subsequent spectral
graph matching step (Phase 1 in Section 4.1).

Consider a connected, weighted, undirected graph $G=(V,E,w)$ with $|V|=n$. The
effective resistance between nodes $(p,q)\in V$ plays a crucial role in
various graph analysis tasks including spectral sparsification algorithms
Spielman and Teng [2011]. The effective resistance distances can be accurately
computed using the equation:

$R_{eff}(p,q)=\sum\limits_{i=2}^{n}\frac{w_{p,q}(u_{i}^{\top}b_{pq})^{2}}{\sigma_{i}},$
(13)

where ${b_{p}}\in\mathbb{R}^{n}$ denote the standard basis vector with all
zero entries except for the $p$-th entry being $1$, and
${b_{pq}}=b_{p}-b_{q}$. $u_{i}\in\mathbb{R}^{n}$ for $i=1,\dots,n$ denote the
unit-length, mutually-orthogonal eigenvectors corresponding to Laplacian
eigenvalues $\sigma_{i}$ for $i=1,\dots,n$.

##### Scalable estimation of effective resistances

To address the computational complexity associated with directly computing
eigenvalues and eigenvectors required for estimating edge effective
resistances, we leverage a scalable framework for approximating the
eigenvectors of the graph Laplacian matrix using the Krylov subspace Saad
[2011]. Let $A$ denote the adjacency matrix of graph $G$, consider its
order-$m$ Krylov subspace $\mathbf{K}_{m}(A,x)$ that is a vector space spanned
by the vectors computed through power iterations $x,Ax,A^{2}x,\ldots,A^{m-1}x$
Liesen and Strakos [2013]. By enforcing orthogonality among the above vectors
in the Krylov subspace, a new set of mutually orthogonal vectors of unit
lengths can be constructed for approximating the original Laplacian
eigenvectors in 13, which are denoted as $\tilde{u}_{1}$, $\tilde{u}_{2}$,
$\ldots$, $\tilde{u}_{m}$. To estimate the effective resistance between two
nodes $p$ and $q$, we can exploit the approximated eigenvectors:

$R_{eff}(p,q)\approx\sum\limits_{i=1}^{m}\frac{w_{p,q}(\tilde{u}^{\top}_{i}b_{pq})^{2}}{\tilde{u}^{\top}_{i}L\tilde{u}_{i}},$
(14)

where $\tilde{u}_{i}$ represents the approximated eigenvector corresponding to
the $i$-th eigenvalue of $L$.

##### Graph coarsening with node features

In order to account for the variation in node features along with edge
resistive distance, we can use the following modified effective resistance
formulation:

$R^{*}_{eff}(p,q)=R_{eff}(p,q)+\alpha\|f_{p}-f_{q}\|$ (15)

where $f_{p}$ and $f_{q}$ are node feature vectors of nodes $p$ and $q$,
respectively, while $\alpha$ is a weighting factor that determines the effect
of node feature information in the graph coarsening process.

##  6 GGD as a Distance Metric

Assuming that the graph matching problem can always find the exact
correspondence between nodes, we prove that the GGD metric between any two
(nonempty) graphs is a pseudometric that satisfies the following conditions:

  * •

The distance between a graph and itself or between two isomorphic graphs is
zero: $GGD(G,G)=0$.

  * •

(Positivity) The distance between two distinct graphs is positive:
$GGD(G_{1},G_{2})>0$.

  * •

(Symmetry) The distance between $G_{1}$ and $G_{2}$ is the same of the one
between $G_{2}$ and $G_{1}$: $GGD(G_{1},G_{2})=GGD(G_{2},G_{1})$.

  * •

The triangle inequality: $GGD(G_{1},G_{3})\leq
GGD(G_{1},G_{2})+GGD(G_{2},G_{3})$.

Detailed proofs of the above four properties are provided in Appendix A.1.

##  7 Experiments

###  7.1 Stability Analysis of GNNS

Figure 3: Correlation between graph distance metrics and GNN’s outputs

To analyze the stability of GNN models Bronstein et al. [2017], Garg et al.
[2020], Duvenaud et al. [2015], we conducted multiple experiments with the GGD
and TMD metrics. GNNs typically operate by a message-passing mechanism Gilmer
et al. [2017], where at each layer, nodes send their feature representations
to their neighbors. The feature representation of each node is initialized to
its original features and is updated by repeatedly aggregating incoming
messages from neighbors. In our experiment, we relate GGD to the Graph
Isomorphism Networks (GIN) Xu et al. [2019], one of the most widely applied
and powerful GNNs, utilizing the MUTAG dataset Morris et al. [2020] as our
reference graph dataset. The objective is to analyze the relationship between
the input distance $GGD(G_{1},G_{2})$ and the distance between the output GIN
vectors, $\|h(G_{1})-h(G_{2})\|$ for randomly selected pairs of graphs. The
result is illustrated in Figure 3.

We observe a strong correlation between GGD and the output distance, as
indicated by a high Pearson correlation coefficient. This finding implies the
effectiveness of the proposed GGD metric for analyzing the stability of GNN
models Chuang and Jegelka [2022]. To compare GGD with existing metrics, we
repeat this experiment using TMD without considering node attributes
(features). As shown in Figure 3, GGD demonstrates a better correlation with
GIN outputs than the TMD metric across different levels. These findings
indicate that when dealing with graphs without node features, GGD should be
adopted for the stability analysis of graph learning models.

###  7.2 Graph Classification

Table 2: Classification accuracies for various models on graph datasets
Accuracy in percentage
---
Dataset | MUTAG | PC-3H | SW-620H | BZR
GGD | 86$\pm$7.5 | 78.34 | 77.6$\pm$3.5 | 83.23
TMD, L = 2 | 76$\pm$5.3 |  |  |
TMD, L = 3 | 77$\pm$5.2 | 71.24 | 70.2$\pm$2.3 | 73.43
TMD, L = 4 | 78.2$\pm$6 | 71.37 | 70.8$\pm$2.3 | 73.96
TMD, L = 5 |  | 71.89 | 71.2$\pm$1.88 | 75.13
GCNKipf and Welling [2017] | 77$\pm$3.8 | 70.56 | 69.4 | 72.56
GINXu et al. [2019] | 82.6$\pm$4.6 | 75.34 | 73.4 | 77.09
WWLTogninalli et al. [2019] | 72.4$\pm$2.6 | 65.46 | 68.34 | 73.59
WL SubtreeShervashidze et al. [2011] | 76$\pm$6.3 | 68.43 | 70.56 | N/A
FGHTitouan et al. [2019] | 88.33$\pm$5.6 | 61.77 | 59.3 | 53.66

We evaluate whether the GGD metric aligns with graph labels in graph
classification tasks using datasets from TUDatasets Morris et al. [2020]. We
employ a Support Vector Classifier (SVC) $(C=1)$ with an indefinite kernel
$e^{-\gamma*GGD(G_{1},G_{2})}$, which can be viewed as a noisy observation of
the true positive semidefinite kernel Luss and d’Aspremont [2007]. The
parameter $\gamma$ is selected through cross-validation from the set {0.01,
0.05, 0.1}. For comparative analysis with existing methods, we include graph
kernels based on graph subtrees: the WL subtree kernel Shervashidze et al.
[2011]; and two widely adopted GNNs: graph isomorphism network (GIN) Xu et al.
[2019] and graph convolutional networks (GCN) Kipf and Welling [2017].

Table 2 presents the mean and standard deviation over five independent trials
with a 90%-10% train-test split. For most cases, GGD consistently outperforms
the performance of state-of-the-art GNNs, graph kernels, and metrics when node
attributes are missing. Additionally, we observe that GGD allows us to obtain
better results for larger datasets than smaller ones.

###  7.3 Runtime Complexity Analysis and Comparison

Table 3: Runtime comparison for different distance metrics on various datasets. | MUTAG | PC-3H | SW-620H | BZR
---|---|---|---|---
GGD | 4.87 s | 31.89 s | 45.37 s | 5.80 s
TMD, L = 3 | 5.30 s | 88.6 s | 98.7 s | 7.22 s
TMD, L = 4 | 7.89 s | 112 s | 134.38 s | 10.34 s
TMD, L = 6 | 11.27 s | 273 s | 288 s | 14.98 s

When comparing various graph distance metrics, a primary consideration is
their computational complexity. Conventional approaches usually require
intricate computations that frequently have cubic time or higher complexities.
For our problem, the spectral graph matching step requires the eigenvalue
decomposition of adjacency matrices and solving the linear assignment problem
(LAP). Eigenvalue decomposition of an $n\times n$ matrix has a complexity of
$O(n^{3})$ Borodin and Munro [1975], André et al. [2015], while solving the
LAP using the Hungarian algorithm also has a runtime complexity of $O(n^{3})$.
Similarly, calculating the generalized eigenvalue of two SPD matrices entails
a cubic complexity. Consequently, the overall complexity of GGD calculation is
$O(n^{3})$. On the other hand, TMD is an OT-based distance metric with a
complexity of $O(n^{3}\log(n))$ Chuang and Jegelka [2022], Flamary et al.
[2021]. Therefore, GGD exhibits slightly better (lower) runtime complexity
than the TMD metric.

To evaluate runtime performance, we conduct extensive experiments to compare
the runtime of computing TMD at various levels with GGD on both small graphs
(MUTAG, BZR) and large graphs (PC-3H, SW-620H) collected from the TUDataset
Morris et al. [2020]. Table 3 presents the average runtime (in seconds) for
computing $100$ distances between different graphs obtained by repeating the
experiment five times. The results demonstrate that GGD consistently
outperforms TMD in terms of runtime across all datasets and scenarios,
particularly when dealing with larger graphs that contain more nodes. The TMD
metric computation usually requires more levels to effectively capture the
entire graph structure. In such cases, GGD exhibits runtime performance
approximately $6-9$ times faster than of TMD. Hence, we conclude that GGD is
significantly more computationally efficient than TMD, especially when working
with large graphs. More details about our experimental setup can be found in
Appendix A.4.

###  7.4 Partial Node Features

Cutting-edge graph distance metrics like TMD, rely on node attributes to
compute the dissimilarity between graphs, resulting in more accurate outcomes
when all attributes are available. However, acquiring datasets with complete
node attributes is often unattainable in real-world scenarios, leading to
situations where certain features are partially missing. In such scenarios
when only partial node features are available, we compare TMD with GGD to
better understand their differences. Table 4 shows that the TMD metric
outperforms GGD at various levels when node features are fully accessible.
However, when node features are randomly removed from the MUTAG dataset, the
accuracy of TMD degrades substantially.

Distance |  |  |  |  |
---|---|---|---|---|---
Metric | Node Features Missing in Percentage |  |  |  |
| 0% | 20% | 50% | 80% | 100%
TMD, L = 3 | 0.84 | 0.78 | 0.72 | 0.63 | 0.61
TMD, L = 4 | 0.81 | 0.77 | 0.62 | 0.58 | 0.57
TMD, L = 5 | 0.80 | 0.75 | 0.65 | 0.58 | 0.53
GGD | 0.78 | 0.78 | 0.77 | 0.77 | 0.77

Table 4: Comparison of Correlation with GNN outputs and distance metrics with
Partial Node Features

Figure 4: Percentage of the original GGD using numbers of extreme Eigenvalues

###  7.5 GGD Approximation using Extreme Eigenvalues

Table 5: Performance of GGD using Extreme Eigenvalues only Task |  Number of Extreme Eigenvalues |  |
---|---|---|---
|  2 | 4 | All
Correlation with GNN |  0.74 | 0.76 | 0.77
Classification Accuracy |  $81.50\pm 6.85$ | $83.87\pm 7.56$ | $86.00\pm 7.5$

The largest or smallest eigenvalues correspond to the most dominant mismatches
in graph cuts and effective resistance distances, contributing most to the
total GGD value. Similarly, the second largest and smallest eigenvalues
correspond to the next significant mismatched cuts. In our experiment, we
obtain approximate GGDs using a few extreme eigenvalue pairs and compare them
with the ground truth. Figure 4 illustrates the relative accuracy of the
approximate GGDs, in which we observe that the top four pairs of extreme
eigenvalues contribute $80\%$ of the total GGD values. In addition, we conduct
the SVC classification task and GNN correlation study using GGD with only $2$
and $4$ extreme eigenvalue pairs, respectively and present the associated
findings in Table 5.

##  8 Conclusion

In this work, we introduce Graph Geodesic Distance (GGD), a novel spectral
graph distance metric based on graph matching and the infimum on a Riemannian
manifold. GGD captures the essential structural mismatches of graphs vital for
graph classification tasks. Additionally, we show that GGD can serve as an
effective metric for analyzing the stability of GNN models and graph
classification tasks, achieving superior performance when only partial node
features are available.

## References

  * Aghdaei and Feng [2022] Ali Aghdaei and Zhuo Feng.  Hyperef: Spectral hypergraph coarsening by effective-resistance clustering.  In _Proceedings of the 41st IEEE/ACM International Conference on Computer-Aided Design_ , pages 1–9, 2022.
  * André et al. [2015] Rémi André, Tual Trainini, Xavier Luciani, and Eric Moreau.  A fast algorithm for joint eigenvalue decomposition of real matrices.  In _2015 23rd European Signal Processing Conference (EUSIPCO)_ , pages 1316–1320, 2015.  doi: 10.1109/EUSIPCO.2015.7362597.
  * Bonnabel and Sepulchre [2010] Silvere Bonnabel and Rodolphe Sepulchre.  Riemannian metric and geometric mean for positive semidefinite matrices of fixed rank.  _SIAM Journal on Matrix Analysis and Applications_ , 31(3):1055–1070, 2010.
  * Borgwardt et al. [2020] Karsten Borgwardt, Elisabetta Ghisu, Felipe Llinares-López, Leslie O’Bray, and Bastian Rieck.  Graph kernels: State-of-the-art and future challenges.  _Foundations and Trends® in Machine Learning_ , 13(5-6):531–712, 2020.  ISSN 1935-8237.
  * Borodin and Munro [1975] A. Borodin and I. Munro.  _The Computational Complexity of Algebraic and Numeric Problems_.  Elsevier Computer Science Library, Theory of Computation Series. American Elsevier Publishing Company, 1975.  ISBN 9780608163741.
  * Bronstein et al. [2017] Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst.  Geometric deep learning: going beyond euclidean data.  _IEEE Signal Processing Magazine_ , 34(4):18–42, 2017.
  * Bunke and Shearer [1998] Horst Bunke and Kim Shearer.  A graph distance metric based on the maximal common subgraph.  _Pattern recognition letters_ , 19(3-4):255–259, 1998.
  * Caetano et al. [2009] Tibério S Caetano, Julian J McAuley, Li Cheng, Quoc V Le, and Alex J Smola.  Learning graph matching.  _IEEE transactions on pattern analysis and machine intelligence_ , 31(6):1048–1058, 2009.
  * Chapel et al. [2020] Laetitia Chapel, Mokhtar Z Alaya, and Gilles Gasso.  Partial optimal tranport with applications on positive-unlabeled learning.  _Advances in Neural Information Processing Systems_ , 33:2903–2913, 2020.
  * Chen et al. [2022] Xu Chen, Siheng Chen, Jiangchao Yao, Huangjie Zheng, Ya Zhang, and Ivor W Tsang.  Learning on attribute-missing graphs.  _IEEE transactions on pattern analysis and machine intelligence_ , 44(2):740–757, 2022.
  * Chuang and Jegelka [2022] Ching-Yao Chuang and Stefanie Jegelka.  Tree mover’s distance: Bridging graph metrics and stability of graph neural networks.  _Advances in Neural Information Processing Systems_ , 35:2944–2957, 2022.
  * Chuang et al. [2020] Ching-Yao Chuang, Antonio Torralba, and Stefanie Jegelka.  Estimating generalization under distribution shifts via domain-invariant representations.  _International conference on machine learning_ , 2020.
  * Crane et al. [2020] Keenan Crane, Marco Livesu, Enrico Puppo, and Yipeng Qin.  A survey of algorithms for geodesic paths and distances.  _arXiv preprint arXiv:2007.10430_ , 2020.
  * Duvenaud et al. [2015] David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P Adams.  Convolutional networks on graphs for learning molecular fingerprints.  _Advances in neural information processing systems_ , 28, 2015.
  * Emmert-Streib et al. [2016] Frank Emmert-Streib, Matthias Dehmer, and Yongtang Shi.  Fifty years of graph matching, network alignment and network comparison.  _Information sciences_ , 346:180–197, 2016.
  * Fan et al. [2020] Zhou Fan, Cheng Mao, Yihong Wu, and Jiaming Xu.  Spectral graph matching and regularized quadratic relaxations: Algorithm and theory.  In _International conference on machine learning_ , pages 2985–2995. PMLR, 2020.
  * Feng [2020] Zhuo Feng.  Grass: Graph spectral sparsification leveraging scalable spectral perturbation analysis.  _IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems_ , 39(12):4944–4957, 2020.
  * Fernández and Valiente [2001] Mirtha-Lina Fernández and Gabriel Valiente.  A graph distance metric combining maximum common subgraph and minimum common supergraph.  _Pattern Recognition Letters_ , 22(6-7):753–758, 2001.
  * Flamary et al. [2021] Rémi Flamary, Nicolas Courty, Alexandre Gramfort, Mokhtar Z Alaya, Aurélie Boisbunon, Stanislas Chambon, Laetitia Chapel, Adrien Corenflos, Kilian Fatras, Nemo Fournier, et al.  Pot: Python optimal transport.  _Journal of Machine Learning Research_ , 22(78):1–8, 2021.
  * Gao et al. [2010] Xinbo Gao, Bing Xiao, Dacheng Tao, and Xuelong Li.  A survey of graph edit distance.  _Pattern Analysis and applications_ , 13:113–129, 2010.
  * Garg et al. [2020] Vikas Garg, Stefanie Jegelka, and Tommi Jaakkola.  Generalization and representational limits of graph neural networks.  In _International Conference on Machine Learning_ , pages 3419–3430. PMLR, 2020.
  * Gilmer et al. [2017] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl.  Neural message passing for quantum chemistry.  In _International conference on machine learning_ , pages 1263–1272. PMLR, 2017.
  * Golub and Van Loan [2013] Gene H Golub and Charles F Van Loan.  _Matrix computations_.  JHU press, 2013.
  * Han et al. [2024] Xiaoxue Han, Zhuo Feng, and Yue Ning.  A topology-aware graph coarsening framework for continual graph learning.  _arXiv preprint arXiv:2401.03077_ , 2024.
  * Haslbeck and Waldorp [2018] Jonas MB Haslbeck and Lourens J Waldorp.  How well do network models predict observations? on the importance of predictability in network models.  _Behavior research methods_ , 50:853–861, 2018.
  * Haussler et al. [1999] David Haussler et al.  Convolution kernels on discrete structures.  Technical report, Citeseer, 1999.
  * Huang et al. [2015] Zhiwu Huang, Ruiping Wang, Shiguang Shan, Xianqiu Li, and Xilin Chen.  Log-euclidean metric learning on symmetric positive definite manifold with application to image set classification.  In _International conference on machine learning_ , pages 720–729. PMLR, 2015.
  * Kipf and Welling [2017] Thomas N. Kipf and Max Welling.  Semi-Supervised Classification with Graph Convolutional Networks.  In _International Conference on Learning Representations_ , 2017.
  * Kuhn [1955] Harold W Kuhn.  The hungarian method for the assignment problem.  _Naval research logistics quarterly_ , 2(1-2):83–97, 1955.
  * Li et al. [2017] Tao Li, Han Dong, Yongtang Shi, and Matthias Dehmer.  A comparative analysis of new graph distance measures and graph edit distance.  _Information Sciences_ , 403:15–21, 2017.
  * Liesen and Strakos [2013] Jörg Liesen and Zdenek Strakos.  Krylov subspace methods: principles and analysis.  Numerical Mathematics and Scie, 2013.
  * Lim et al. [2019] Lek-Heng Lim, Rodolphe Sepulchre, and Ke Ye.  Geometric distance between positive definite matrices of different dimensions.  _IEEE Transactions on Information Theory_ , 65(9):5401–5405, 2019.
  * Livi and Rizzi [2013] Lorenzo Livi and Antonello Rizzi.  The graph matching problem.  _Pattern Analysis and Applications_ , 16:253–283, 2013.
  * Loukas [2019] Andreas Loukas.  Graph reduction with spectral and cut guarantees.  _J. Mach. Learn. Res._ , 20(116):1–42, 2019.
  * Luss and d’Aspremont [2007] Ronny Luss and Alexandre d’Aspremont.  Support vector machine classification with indefinite kernels.  _Advances in neural information processing systems_ , 20, 2007.
  * Mémoli [2011] Facundo Mémoli.  Gromov–wasserstein distances and the metric approach to object matching.  _Foundations of computational mathematics_ , 11:417–487, 2011.
  * Morris et al. [2019] Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe.  Weisfeiler and leman go neural: Higher-order graph neural networks.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 33, pages 4602–4609, 2019.
  * Morris et al. [2020] Christopher Morris, Nils M Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann.  Tudataset: A collection of benchmark datasets for learning with graphs.  _arXiv preprint arXiv:2007.08663_ , 2020.
  * Owen and Provan [2010] Megan Owen and J Scott Provan.  A fast algorithm for computing geodesic distances in tree space.  _IEEE/ACM Transactions on Computational Biology and Bioinformatics_ , 8(1):2–13, 2010.
  * Pearson [1905] Karl Pearson.  The problem of the random walk.  _Nature_ , 72(1865):294–294, 1905.
  * Pennec et al. [2006] Xavier Pennec, Pierre Fillard, and Nicholas Ayache.  A riemannian framework for tensor computing.  _International Journal of computer vision_ , 66:41–66, 2006.
  * Ramon and Gärtner [2003] Jan Ramon and Thomas Gärtner.  Expressivity versus efficiency of graph kernels.  In _Proceedings of the first international workshop on mining graphs, trees and sequences_ , pages 65–74, 2003.
  * Rossi et al. [2022] Emanuele Rossi, Henry Kenlay, Maria I Gorinova, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bronstein.  On the unreasonable effectiveness of feature propagation in learning on graphs with missing node features.  In _Learning on Graphs Conference_ , pages 11–1. PMLR, 2022.
  * Saad [2011] Y Saad.  _Numerical Methods for Large Eigenvalue Problems: Revised Edition_ , volume 66.  Siam, 2011.
  * Sanfeliu and Fu [1983] Alberto Sanfeliu and King-Sun Fu.  A distance measure between attributed relational graphs for pattern recognition.  _IEEE transactions on systems, man, and cybernetics_ , (3):353–362, 1983.
  * Shamai and Kimmel [2017] Gil Shamai and Ron Kimmel.  Geodesic distance descriptors.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 6410–6418, 2017.
  * Shervashidze et al. [2011] Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt.  Weisfeiler-lehman graph kernels.  _Journal of Machine Learning Research_ , 12(9), 2011.
  * Spielman and Teng [2011] Daniel Spielman and ShangHua Teng.  Spectral sparsification of graphs.  _SIAM Journal on Computing_ , 40(4):981–1025, 2011.
  * Titouan et al. [2019] Vayer Titouan, Nicolas Courty, Romain Tavenard, and Rémi Flamary.  Optimal transport for structured data with application on graphs.  In _International Conference on Machine Learning_ , pages 6275–6284. PMLR, 2019.
  * Togninalli et al. [2019] Matteo Togninalli, Elisabetta Ghisu, Felipe Llinares-López, Bastian Rieck, and Karsten Borgwardt.  Wasserstein weisfeiler-lehman graph kernels.  _Advances in neural information processing systems_ , 32, 2019.
  * Vemulapalli and Jacobs [2015] Raviteja Vemulapalli and David W Jacobs.  Riemannian metric learning for symmetric positive definite matrices.  _arXiv preprint arXiv:1501.02393_ , 2015.
  * Vishwanathan et al. [2010] S Vichy N Vishwanathan, Nicol N Schraudolph, Risi Kondor, and Karsten M Borgwardt.  Graph kernels.  _The Journal of Machine Learning Research_ , 11:1201–1242, 2010.
  * Wang et al. [2020] Tao Wang, He Liu, Yidong Li, Yi Jin, Xiaohui Hou, and Haibin Ling.  Learning combinatorial solver for graph matching.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pages 7568–7577, 2020.
  * Weisfeiler and Leman [1968] Boris Weisfeiler and Andrei Leman.  The reduction of a graph to canonical form and the algebra which appears therein.  _nti, Series_ , 2(9):12–16, 1968.
  * Xu et al. [2019] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka.  How powerful are graph neural networks?  In _International Conference on Learning Representations_ , 2019.
  * Xu et al. [2013] Yunwen Xu, Srinivasa M Salapaka, and Carolyn L Beck.  A distance metric between directed weighted graphs.  In _52nd IEEE Conference on Decision and Control_ , pages 6359–6364. IEEE, 2013.
  * Ye and Lim [2016] Ke Ye and Lek-Heng Lim.  Schubert varieties and distances between subspaces of different dimensions.  _SIAM Journal on Matrix Analysis and Applications_ , 37(3):1176–1197, 2016.
  * You and Park [2021] Kisung You and Hae-Jeong Park.  Re-visiting riemannian geometry of symmetric positive definite matrices for the analysis of functional connectivity.  _NeuroImage_ , 225:117464, 2021.
  * Zhu et al. [2020] Yuehua Zhu, Muli Yang, Cheng Deng, and Wei Liu.  Fewer is more: A deep graph metric learning perspective using fewer proxies.  _Advances in Neural Information Processing Systems_ , 33:17792–17803, 2020.

##  Appendix A Appendix

###  A.1 Detailed Proofs Showing GGD is a Pseudometric

####  A.1.1 Identity Property

###### Proof.

Let the corresponding SPD matrix of the graph $G$ be
$\mathcal{L}\in\mathbb{S}_{++}^{n}$. From Equation 10, we have:

$GGD(G,G)=\left[\sum_{i=1}^{n}\log^{2}(\lambda_{i}(\mathcal{L}^{-1}\mathcal{L}))\right]^{1/2}=\left[\sum_{i=1}^{n}\log^{2}(\lambda_{i}(I))\right]^{1/2}$

The identity matrix has only one eigenvalue, which is 1. So,
$GGD(G,G)=\left[\log^{2}(1)\right]^{1/2}=0$ ∎

####  A.1.2 Positivity Property

###### Proof.

Let the corresponding SPD matrices of the graphs $G_{1}$ and $G_{2}$ be
$\mathcal{L}_{1}$, $\mathcal{L}_{2}\in\mathbb{S}_{++}^{n}$. Let the
generalized eigenvalues of ($\mathcal{L}_{1}^{-1}\mathcal{L}_{2}$) be
$\lambda_{1},\lambda_{2},\lambda_{3},\ldots,\lambda_{n}$. From Equation 10, we
get:

$GGD(G_{1},G_{2})=\left[\log^{2}(\lambda_{1})+\log^{2}(\lambda_{2})+\log^{2}(\lambda_{3})+\ldots+\log^{2}(\lambda_{n})\right]^{1/2}$

Now,
$\log^{2}(\lambda_{1})+\log^{2}(\lambda_{2})+\log^{2}(\lambda_{3})+\ldots+\log^{2}(\lambda_{n})\geq
0$, for any values of $\lambda_{i}$.

We can conclude, $GGD(G_{1},G_{2})\geq 0$. ∎

####  A.1.3 Symmetry Property

###### Proof.

Let the corresponding SPD matrices of the graphs $G_{1}$ and $G_{2}$ be
$\mathcal{L}_{1}$, $\mathcal{L}_{2}\in\mathbb{S}_{++}^{n}$. Let the
generalized eigenvalues of ($\mathcal{L}_{1}^{-1}\mathcal{L}_{2}$) be
$\lambda_{1},\lambda_{2},\lambda_{3},\ldots,\lambda_{n}$. From Equation 10, we
get:

$GGD(G_{1},G_{2})=\left[\sum_{i=1}^{n}\log^{2}(\lambda_{i})\right]^{1/2}$

Given that the inverse of a symmetric matrix is also symmetric, and the
product of two symmetric matrices is symmetric, it follows that
($\mathcal{L}_{1}^{-1}\mathcal{L}_{2}$) is a symmetric tensor. Furthermore,
the eigenvalues of a symmetric matrix and the eigenvalues of its inverse
matrix are inversely related.

So, the eigenvalues of ($\mathcal{L}_{2}^{-1}\mathcal{L}_{1}$) will be
$\frac{1}{\lambda_{1}},\frac{1}{\lambda_{2}},\frac{1}{\lambda_{3}},\ldots,\frac{1}{\lambda_{n}}$.

$GGD(G_{2},G_{1})=\left[\sum_{i=1}^{n}\log^{2}(\frac{1}{\lambda_{i}})\right]^{1/2}$

Now, $\log\left(\frac{1}{\lambda_{i}}\right)=-\log(\lambda_{i})$; so,
$\log^{2}\left(\frac{1}{\lambda_{i}}\right)=\log^{2}(\lambda_{i})$

So, we can conclude $GGD(G_{1},G_{2})=GGD(G_{2},G_{1})$ ∎

####  A.1.4 Triangle Inequality

###### Proof.

Let, $\mathcal{L}_{1},\mathcal{L}_{2},\mathcal{L}_{3}\in\mathbb{S}_{++}^{n}$
are three SPD matrices corresponding to graphs $G_{1},G_{2},G_{3}$.

Now, The Frobenius norm $\|X\|_{F}$ is the geodesic length at $d(\exp
X,I)=\|X\|_{F}$ Bonnabel and Sepulchre [2010]. Hence at identity,
$d(\mathcal{L},I)=\|\log\mathcal{L}\|_{F}$.

From Bonnabel and Sepulchre [2010], You and Park [2021] we get,

$GGD(G_{1},G_{2})=GGD\left(G_{1}^{-1/2}G_{2}G_{1}^{-1/2},I\right)=\left\|\log\left(\mathcal{L}_{1}^{-1/2}\mathcal{L}_{2}\mathcal{L}_{1}^{-1/2}\right)\right\|_{F}=\left\|\log\left(\mathcal{L}_{1}^{-1}\mathcal{L}_{2}\right)\right\|_{F}$
(16)

We know,

$\mathcal{L}_{1}^{-1}\mathcal{L}_{3}=\mathcal{L}_{1}^{-1}(\mathcal{L}_{2}\mathcal{L}_{2}^{-1})\mathcal{L}_{3}=(\mathcal{L}_{1}^{-1}\mathcal{L}_{2})(\mathcal{L}_{2}^{-1}\mathcal{L}_{3})$

Now using the Frobenius Norm inequality, we get:

$\|\mathcal{L}_{1}^{-1}\mathcal{L}_{3}\|=\|(\mathcal{L}_{1}^{-1}\mathcal{L}_{2})(\mathcal{L}_{2}^{-1}\mathcal{L}_{3})\|\leq\|\mathcal{L}_{1}^{-1}\mathcal{L}_{2}\|\|\mathcal{L}_{2}^{-1}\mathcal{L}_{3}\|$

Now taking logarithms on both sides:

$\|\log(\mathcal{L}_{1}^{-1}\mathcal{L}_{3})\|\leq\|\log(\mathcal{L}_{1}^{-1}\mathcal{L}_{2})\|+\|\log(\mathcal{L}_{2}^{-1}\mathcal{L}_{3})\|$

Using Equation 10, we conclude:

$GGD(G_{1},G_{3})\leq GGD(G_{1},G_{2})+GGD(G_{2},G_{3})$

∎

###  A.2 Graph Matching Recovery

Given symmetric matrices $A$, $B$ and $Z$ from the Gaussian Wigner model,
where $B_{\pi^{*}}=A+\sigma Z$, there exist constants $c,c^{\prime}>0$ such
that if $1/n^{0.1}\leq\eta\leq c/\log n$ and $\sigma\leq c^{\prime}\eta$, then
with probability at least $1-n^{-4}$, GRAMPA Algorithm correctly recovers the
permutation matrix $\pi^{*}$.

From 6, the similarity matrix $\widehat{X}$ is defined as:

$\widehat{X}=\sum_{i,j=1}^{n}\frac{u_{i}u_{i}^{T}\mathbf{J}v_{j}v_{j}^{T}}{(\zeta_{i}-\mu_{j})^{2}+\eta^{2}},$

where $u_{i}$ and $v_{j}$ are eigenvectors of $A$ and $B$ respectively, and
$\zeta_{i}$ and $\mu_{j}$ are their corresponding eigenvalues. $\mathbf{J}$ is
a all-one matrix, and $\eta$ is the tuning parameter.

Now, the proof is divided into two parts:

######  Lemma A.1 (Noiseless Setting Diagonal Dominance).

In a noiseless situation, means replacing B with A, similarity matrix
$\widehat{X}^{*}$ is defined as:

$\widehat{X}^{*}=\sum_{i,j=1}^{n}\frac{u_{i}u_{i}^{T}\mathbf{J}u_{j}u_{j}^{T}}{(\zeta_{i}-\zeta_{j})^{2}+\eta^{2}}$
(17)

For some constants $C,c>0$, if $1/n^{0.1}<\eta<c/\log n$, then with
probability at least $1-5n^{-5}$ for large $n$, it can be proved that the
diagonal components of $\widehat{X}^{*}$ are dominant by showing Fan et al.
[2020]:

$\min_{i\in[n]}(\widehat{X}^{*})_{ii}>\frac{1}{3\eta^{2}},\quad\text{and}\quad\max_{i,j\in[n]:i\neq
j}(\widehat{X}^{*})_{ij}<C\left(\frac{\sqrt{\log n}}{\eta^{3/2}}+\frac{\log
n}{\eta}\right)$ (18)

######  Lemma A.2 (Bounding the Noise Impact).

The difference between the similarity matrix $X$ in the presence of noise and
the noiseless situation is bounded. If $\eta>1/n^{0.1}$, then for a constant
$C>0$, with probability at least $1-2n^{-5}$ for large $n$, it can be shown:

$\max_{i,j\in[n]}|\widehat{X}_{ij}-(\widehat{X}^{*})_{ij}|<C\sigma\left(\frac{1}{\eta^{3}}+\frac{\log
n}{\eta^{2}}\left(1+\frac{\sigma}{\eta}\right)\right)$ (19)

Assuming Lemma A.1 and A.2, for some $c,c^{\prime}>0$ sufficiently small, and
by setting $\eta<c/\log n$ and $\sigma<c^{\prime}\eta$, the algorithm ensures
that all diagonal entries of $\widehat{X}$ are larger than all off-diagonal
entries, thereby achieving exact recovery.

###  A.3 Effect of tuning parameter $\eta$ on Graph Matching

In the original work, it is suggested that the regularization parameter $\eta$
needs to be chosen so that $\sigma\vee n^{-0.1}\lesssim\eta\lesssim 1/\log n$
Fan et al. [2020]. It is also mentioned that for practical cases, computing
permutation matrix for different values of $\eta$ in an iterative way can
result in better accuracy. The GRAMPA uses $\eta=0.2$ for all their
experiments Fan et al. [2020]. We used a few values of $\eta$ in the
classification problem using MUTAG dataset and got that the best accuracy is
obtained at $\eta=0.5$. In Figure 5, the performance of the tuning parameter
is demonstrated.

Figure 5: Classification Accuracy vs GRAMPA tuning parameter

###  A.4 Experimental Setup

To evaluate the performance of the Graph Geodesic Distance (GGD) metric, we
utilized graph datasets from the TUDataset collection Morris et al. [2020].
For small graphs, we used datasets like MUTAG and BZR, and for larger graphs,
we selected PC-3H and SW-620H, which present more sizable networks.

While Classification tasks, each dataset was split into 90% training and 10%
testing sets to ensure an unbiased evaluation process. When assessing the
correlation with GNN, we trained a 3-layer GIN with 90% of all graphs from
MUTAG and validated with the rest 10%. For the performance evaluation using
graphs with partial node features, we took each dataset with node features and
randomly removed a certain portion of features.

All experiments have been evaluated on a laptop with an Apple M1 chip,
featuring an 8-core CPU and a 7-core GPU.