# Network Alignment with Transferable Graph Autoencoders

Jiashu He
Computer and Information Science
University of Pennsylvania
Philadelphia, PA 19104
<EMAIL_ADDRESS>
&Charilaos I. Kanatsoulis
Electrical and Systems Engineering
University of Pennsylvania
Philadelphia, PA 19104
<EMAIL_ADDRESS>
&Alejandro Ribeiro
Electrical and Systems Engineering
University of Pennsylvania
Philadelphia, PA 19104
<EMAIL_ADDRESS>

###### Abstract

Network alignment is the task of establishing one-to-one correspondences
between the nodes of different graphs and finds a plethora of applications in
high-impact domains. However, this task is known to be NP-hard in its general
form, and existing algorithms do not scale up as the size of the graphs
increases. To tackle both challenges we propose a novel generalized graph
autoencoder architecture, designed to extract powerful and robust node
embeddings, that are tailored to the alignment task. We prove that the
generated embeddings are associated with the eigenvalues and eigenvectors of
the graphs and can achieve more accurate alignment compared to classical
spectral methods. Our proposed framework also leverages transfer learning and
data augmentation to achieve efficient network alignment at a very large scale
without retraining. Extensive experiments on both network and sub-network
alignment with real-world graphs provide corroborating evidence supporting the
effectiveness and scalability of the proposed approach.

##  1 Introduction

Network alignment, also known as graph matching, is a classical problem in
graph theory, that aims to find node correspondence across different graphs
and is vital in a number of high-impact domains (Emmert-Streib et al., 2016).
In social networks, for instance, network alignment has been used for user
deanonymization (Nilizadeh et al., 2014) and analysis (Ogaard et al., 2013),
while in bioinformatics it is a key tool to identify functionalities in
protein complexes (Singh et al., 2008), or to identify gene–drug modules (Chen
et al., 2018). Graph matching also finds application in computer vision (Conte
et al., 2003), sociology (Racz & Sridhar, 2021), or politics (Li et al.,
2022), to name a few. Graph matching can be cast as a quadratic assignment
problem (QAP), which is in general NP-hard (Koopmans & Beckmann, 1957).

Various approaches have been developed to tackle network alignment and can be
divided into two main categories; i) optimization algorithms that attempt to
approximate the QAP problem by relaxing the combinatorial constraints, ii)
embedding methods that approach the problem by implicitly or explicitly
generating powerful node embeddings that facilitate the alignment task.
Optimization approaches, as (Anstreicher & Brixius, 2001; Vogelstein et al.,
2015) employ quadratic programming relaxations, while (Klau, 2009) and (Peng
et al., 2010) utilize semidefinite or Lagrangian-based relaxations
respectively. Successive convex approximations were also proposed by (Konar &
Sidiropoulos, 2020) to handle the QAP. Challenges associated with these
methods include high computational cost, infeasible solutions, or nearly
optimal initialization requirements. Embedding methods, on the other hand,
overcome these challenges, but they usually produce inferior solutions, due to
an inherent trade-off between embedding uniqueness (permutation-equivariance)
and ability to capture the structural information of the graph. Typical
embedding techniques include spectral methods (Umeyama, 1988; Feizi et al.,
2019; Zhang & Tong, 2016), structural feature engineering methods (Berlingerio
et al., 2013; Heimann et al., 2018), and random walk approaches (Perozzi et
al., 2014; Grover & Leskovec, 2016a). Recently (Chen et al., 2020; Karakasis
et al., 2021) have proposed joint node embedding and network alignment, to
overcome these challenges, but these methods do not scale up as the size of
the graph increases.

Figure 1: The overall architecture of a three-layer T-GAE and its traing
paradigm: The input signal is processed by a local MLP and then processed by
GNN layers with skip connections. The outputs of all neural network layers are
encoded by an MLP followed by a single-layer decoder to generate the
reconstructed graph. The whole model is trained end-to-end with a single or
multiple graphs.

Graph Neural Networks (GNNs) are powerful architectures that learn graph
representations (embeddings). They have shown state-of-the-art performance in
several tasks, including biology (Gainza et al., 2020; Strokach et al., 2020;
Jiang et al., 2021), quantum chemistry (Gilmer et al., 2017), social networks
and recommender systems (Ying et al., 2018; Wu et al., 2020). Recently, (Gao
et al., 2021a) proposed a GNN approach to match attributed graphs. The method
used a joint embedding framework for pairs of graphs and achieved high levels
of matching accuracy. However, this method does not scale to large graphs,
since training graphs with large sizes is computationally prohibitive.

To address these challenges, we propose a novel self-supervised GNN framework
to perform network alignment on a large scale. Specifically, we design a
generalized transferable graph autoencoder (T-GAE) (shown in Fig. 1), to
produce permutation equivariant and highly expressive embeddings, overcoming
the challenges of other embedding techniques. T-GAE is trained on multiple
graphs and learns node representations which are tailored to perform alignment
between nodes of different graphs. The T-GAE representations combine the
eigenvectors of the graph in a nonlinear fashion and are provably at least as
good in network alignment as certain spectral methods. Additionally, the
proposed framework leverages transfer learning and data augmentation to
efficiently operate with large graphs. Training is performed with small
graphs, in a self-supervised manner, and the trained encoder can be executed
on large graphs to tackle network alignment at a very large scale. Extensive
experiments with real-world benchmarks test the effectiveness and limits of
the proposed T-GAE approach in the tasks of graph and sub-graph matching. The
experimental results provide corroborating evidence that T-GAE offers an
elegant framework for large-scale network alignment. Our contributions are
summarized as follows:

  * (C1)

We propose T-GAE, a generalized graph autoencoder architecture that can be
trained with multiple graphs and produce expressive/permutation equivariant
representations, tailored to network alignment.

  * (C2)

We draw the the connection between T-GAE and spectral methods and prove that
T-GAE is at least as good in graph matching as the absolute value of the graph
eigenvectors.

  * (C3)

We leverage data augmentation and transfer learning, to develop a robust
framework that efficiently performs network alignment at a large scale.

  * (C4)

We demonstrate the effectiveness and scalability of the proposed T-GAE with
real-world, benchmark graphs in challenging graph and sub-graph matching
settings.

##  2 Preliminaries

Graphs are represented by $\mathcal{G}:=(\mathcal{V},\mathcal{E})$, where
$\mathcal{V}=\\{1,\dots,N\\}$ is the set of vertices (nodes) and
$\mathcal{E}=\left\\{\left(v,u\right)\right\\}$ correspond to edges between
pairs of vertices. A graph is represented in a matrix form by a graph operator
$\bm{S}\in\mathbb{R}^{N\times N}$, where $\bm{S}(i,j)$ quantifies the relation
between node $i$ and node $j$ and $N=|\mathcal{V}|$ is the total number of
vertices. In this work, we use the graph adjacency and normalized graph
adjacency. Oftentimes, the nodes of the graph are associated with graph
signals or node attributes $\bm{X}\in\mathbb{R}^{N\times D}$, that encode
additional information about the nodes. In this paper, we study both network
alignment of graphs with or without attributes.

###  2.1 Network Alignment

######  Definition 1 (Network Alignment).

Given a pair of graphs
$\mathcal{G}:=(\mathcal{V},\mathcal{E}),~{}\hat{\mathcal{G}}:=(\hat{\mathcal{V}},\hat{\mathcal{E}})$,
with graph adjacencies $\bm{S},~{}\hat{\bm{S}}$, network alignment aims to
find a bijection $g:\mathcal{V}\rightarrow\hat{\mathcal{V}}$ which minimizes
the number of edge disagreements between the two graphs. Formally, the problem
can be written as:

$\min_{\bm{P}\in\mathcal{P}}~{}\left\lVert~{}\bm{S}-\bm{P}\hat{\bm{S}}\bm{P}^{T}~{}\right\rVert_{F}^{2},$
(1)

where $\mathcal{P}$ is the set of permutation matrices.

As mentioned in the introduction, network alignment, is equivalent to the QAP,
which has been proven to be NP-hard (Koopmans & Beckmann, 1957).

###  2.2 Spectral Decomposition of the Graph

A popular approach to tackle network alignment is by learning powerful node
embeddings associated with connectivity information in the graph. Network
alignment can be achieved by matching the node embeddings of different graphs
rather than graph adjacencies, as follows:

$\min_{\bm{P}\in\mathcal{P}}~{}\left\lVert~{}\bm{E}-\bm{P}\hat{\bm{E}}~{}\right\rVert_{F}^{2},$
(2)

where $\bm{E}\in\mathbb{R}^{N\times F}$ is embedding matrix and $\bm{E}[i,:]$
is the vector representation of node $i$. The optimization problem in (2) is a
linear assignment problem and can be optimally solved in
$\mathcal{O}\left(N^{3}\right)$ by the Hungarian method (Kuhn, 1955b). Simpler
sub-optimal alternatives also exist that operate with
$\mathcal{O}\left(N^{2}\right)$ or $\mathcal{O}\left(N~{}\text{log}(N)\right)$
flops.

A question that naturally arises is how to generate powerful node embeddings
that capture the network connectivity and also be effective in aligning
different graphs. A natural and effective approach is to leverage the spectral
decomposition of the graph, $\bm{S}=\bm{V}\bm{\Lambda}\bm{V}^{T}$, where
$\bm{V}$ is the orthonormal matrix of the eigenvectors, and $\bm{\Lambda}$ is
the diagonal matrix of corresponding eigenvalues. Note that we assume
undirected graphs and thus $\bm{S}$ is symmetric. Spectral decomposition has
been proven to be an efficient approach to generating meaningful node
embedding for graph matching (Umeyama, 1988; Feizi et al., 2019). In
particular, $\bm{E}=\bm{V}$ or $\bm{E}=\bm{V}\bm{\Lambda}$ are node embeddings
that capture the network connectivity since they can perfectly reconstruct the
graph. However, $\bm{V}$ is not unique. Thus computing the spectral
decomposition of the same graph with node relabelling,
$\tilde{\bm{S}}=\bm{P}{\bm{S}}\bm{P}^{T}$ is not guaranteed to produce a
permuted version of $\bm{V}$, i.e., $\bm{P}\bm{V}$. Even in the case where
$\bm{S}$ does not have repeated eigenvalues $\bm{V}$ is only unique up to
column sign, which prevents effective matching.

To overcome the aforementioned uniqueness limitation, one can focus on the top
$m$ eigenvectors that correspond to non-repeated eigenvalues in both $\bm{S}$
and $\hat{\bm{S}}$ and compute their absolute values. Then network alignment
can be cast as:

$\min_{\bm{P}\in\mathcal{P}}~{}\left\lVert~{}\left|\bm{V}_{m}\right|-\bm{P}\left|\hat{\bm{V}}_{m}\right|~{}\right\rVert_{F}^{2},$
(3)

where $\bm{V}_{m}\in\mathbb{R}^{N\times m}$ corresponds to the subspace of
non-repeated eigenvalues. The formulation in (3) is a similar to the problem
solved in (Umeyama, 1988).

##  3 Graph Neural Networks (GNNs) Upper-Bounds Spectral Methods for Network
Alignment

A GNN is a cascade of layers and performs local, message-passing operations
that are usually defined by the following recursive equation:

$\displaystyle
x_{v}^{(l+1)}=g\left(x_{v}^{(l)},f\left(\left\\{x_{u}^{(l)}:u\in\mathcal{N}\left(v\right)\right\\}\right)\right),$
(4)

where $\mathcal{N}\left(v\right)$ is the 1-hop neighborhood of vertex $v$,
i.e., $u\in\mathcal{N}\left(v\right)$ if and only if $(u,v)\in\mathcal{E}$.
The function $f$ operates on multisets ($\\{\cdot\\}$ represents a multiset)
and $f,~{}g$ are ideally injective. Common choices for $f$ are the summation
or mean function, and for $g$ the linear function, or the multi-layer
perceptron (MLP).

Overall, the output of the $L-$th layer of a GNN is a function
$\phi\left(\bm{X};\bm{S},\mathcal{H}\right):\mathbb{R}^{N\times
D}\to\mathbb{R}^{N\times D^{L}}$, where $\bm{S}$ is the graph operator, and
$\mathcal{H}$ is the tensor of the trainable parameters in all $L$ layers and
produces $D^{L}-$ dimensional embeddings for the nodes of the graph defined by
$\bm{S}$.

GNNs admit some very valuable properties. First, they are permutation
equivariant:

######  Theorem 3.1 ((Xu et al., 2019; Maron et al., 2018)).

Let $\phi\left(\bm{X};\bm{S},\mathcal{H}\right):\mathbb{R}^{N\times
D}\to\mathbb{R}^{N\times D^{L}}$ be a GNN with parameters $\mathcal{H}$. For
$\tilde{\bm{X}}=\bm{P}\bm{X}$ and $\tilde{\bm{S}}=\bm{P}\bm{S}\bm{P}^{T}$ that
correspond to node relabelling according to the permutation matrix $\bm{P}$,
the output of the GNN takes the form:

$\tilde{\bm{X}}^{(L)}=\phi\left(\tilde{\bm{X}};\tilde{\bm{S}},\mathcal{H}\right)=\bm{P}\phi\left(\bm{X};\bm{S},\mathcal{H}\right)$
(5)

Theorem 3.1 implies that given a graph operator $\bm{S}$ and parameters
$\mathcal{H}$, the GNN output
$\bm{X}^{(L)}=\phi\left(\bm{X};\bm{S},\mathcal{H}\right)$ is unique. Note that
this property is not satisfied by other spectral methods. Furthermore, GNNs
are stable (Gama et al., 2020), transferable (Ruiz et al., 2020), and have
high expressive power (Xu et al., 2019; Abboud et al., 2021; Kanatsoulis &
Ribeiro, 2022).

###  3.1 GNNs and Network Alignment

To characterize the ability of a GNN to perform network alignment we first
point out the GNNs perform nonlinear spectral operations. Details can be found
in Appendix B. Then we can derive the following theorem:

######  Theorem 3.2.

Let $\mathcal{G},~{}\hat{\mathcal{G}}$ be graphs with adjacencies
$\bm{S},~{}\hat{\bm{S}}$ that have non-repeated eigenvalues. Also let
${\bm{P}^{\star}},~{}{\bm{P}^{\dagger}}$ be a solutions to the optimization
problems in (1) and (3) respectively. Then there exists a GNN
$\phi\left(\bm{X};\bm{S},\mathcal{H}\right):\mathbb{R}^{N\times
D}\to\mathbb{R}^{N\times D^{L}}$ such that:

$\left\lVert~{}\bm{S}-\bm{P}^{\star}\hat{\bm{S}}\bm{P}^{\star
T}~{}\right\rVert_{F}^{2}\leq~{}\left\lVert~{}\bm{S}-\bm{P}^{\ast}\hat{\bm{S}}\bm{P}^{\ast
T}~{}\right\rVert_{F}^{2}\leq~{}\left\lVert~{}\bm{S}-\bm{P}^{\dagger}\hat{\bm{S}}\bm{P}^{\dagger
T}~{}\right\rVert_{F}^{2},$ (6)

with

$\bm{P}^{\ast}=\operatorname*{arg\,min}_{\bm{P}\in\mathcal{P}}~{}\left\lVert~{}\phi\left(\bm{X};{\bm{S}},\mathcal{H}\right)-\bm{P}\phi\left(\hat{\bm{X}};\hat{\bm{S}},\mathcal{H}\right)~{}\right\rVert_{F}^{2}$
(7)

We prove Theorem 3.2 in Appendix C. Theorem 3.2 compares the network alignment
power of a graph neural network with that of a spectral algorithm Umeyama
(1988), that uses the absolute values of graph adjacency eigenvectors to match
two different graphs. According to Theorem 3.2 there always exists a GNN that
can perform at least as well as the spectral approach. The proof studies a GNN
with white random input and measures the variance of the filter output. Then
it shows that GNN layers are able to compute the absolute values of the graph
adjacency eigenvectors when the adjacency has non-repeated eigenvalues. As a
result there always exists a single layer GNN that outputs the same node
features as the ones used in Umeyama (1988), which concludes our proof.

##  4 Proposed Method

We now leverage the favorable properties of GNNs (permutation equivariance,
expressivity, and transferability) and design a GNN approach to tackle network
alignment at a large-scale. Our approach learns low-dimensional node
embeddings that enable graph matching via solving a linear assignment rather
than a quadratic assignment problem. As previously mentioned, the node
embeddings produced by a GNN are permutation equivariant. In other words, they
are unique for each graph and are also independent of the order of the nodes.
In the remaining section, we will design a robust GNN framework such that the
node embeddings are expressive to accurately match similar nodes and also
stable to graph perturbations, so that they yield high-quality network
alignment.

###  4.1 Learning geometry preserving embeddings

A fundamental property of node embeddings is to preserve the geometry and
topological characteristics of the network. This will allow expressive node
representations that can effectively approximate the original problem in (1)
with the problem in (2). To achieve this goal we leverage an auto-encoder
architecture that reconstructs the original graph from the node embeddings.
Results on GNN expressivity indicate that this reconstruction is doable under
specific conditions (Abboud et al., 2021). To build topology-preserving
embeddings we solve the following optimization problem:

$\min_{\mathcal{H}}~{}l\left(~{}\rho\left(\phi\left(\bm{X};{\bm{S}},\mathcal{H}\right)\phi\left(\bm{X};{\bm{S}},\mathcal{H}\right)^{T}\right),\bm{S}\right),$
(8)

where $l\left(\cdot\right)$ is the binary cross entropy (BCE) and
$\rho\left(\cdot\right)$ is the logistic function.

###  4.2 Large-scale node representation Learning with Generalized Graph Auto-
encoders

The goal of the proposed framework is to learn a function that maps graphs to
node representations and effectively match nodes from different graphs. This
function is modeled by a GNN encoder, which should work for a family of
graphs, rather than a single graph. So the idea is not to train an auto-
encoder on a single graph but train a generalized graph auto-encoder by
solving the following optimization problem.

$\min_{\mathcal{H}}~{}\mathbb{E}\left[l\left(~{}\rho\left(\phi\left(\bm{X};{\bm{S}},\mathcal{H}\right)\phi\left(\bm{X};{\bm{S}},\mathcal{H}\right)^{T}\right),\bm{S}\right)\right],$
(9)

where $\bm{S}\in\mathbb{S}$ is a realization from a family of graphs and the
expectation is taken over this graph family. The above formulation not only
allow us to learn expressive mappings from graphs to node representations but
also enable a generalized framework that can be applied to out-of-distribution
graphs that have not been observed during training. The implications of this
framework are of paramount importance since they enable node embedding and
graph matching for large-scale graphs, where training is computationally
prohibitive.

###  4.3 Robust and Generalizable Node representations with self-supervised
learning (data augmentation)

So far we proposed a convolutional framework to produce expressive node
representations that are tailored to perform network alignment. In this
subsection, we further upgrade our framework by ensuring the robustness and
generalization ability of the proposed GNN mapping. In particular for each
$\bm{S}\in\mathbb{S}$ we produce a set of graphs represented by $\hat{\bm{S}}$
that are perturbed versions of $\bm{S}$. To do so we add or remove an edge
with a certain probability yielding ${\bm{S}^{\prime}}=\bm{S}+\bm{M}$, where
$\bm{M}\in\\{-1,0,1\\}^{N\times N}$. Note that $\bm{M}[i,j]$ can be equal to
$1$ and $-1$ only if $\bm{S}[i,j]$ is equal to $0$ and $1$ respectively. Then
we relabel each node by permuting the rows and columns of the adjacency matrix
yielding $\hat{\bm{S}}=\bm{P}\left(\bm{S}+\bm{M}\right)\bm{P}^{T}$.

To train the proposed generalized graph-autoencoder we consider the following
optimization problem:

$\min_{\mathcal{H}}~{}\mathbb{E}_{\mathbb{M}}\left[\mathbb{E}_{\mathbb{S}}\left[l\left(~{}\rho\left(\phi\left(\bm{X};{\bm{S}},\mathcal{H}\right)\phi\left(\bm{X};{\bm{S}},\mathcal{H}\right)^{T}\right),\bm{S}\right)\right]\right],$
(10)

where $\mathbb{E}_{\mathbb{S}}$ is the expectation with respect to the family
of graphs $\mathbb{S}$ and $\mathbb{E}_{\mathbb{M}}$ is the expectation with
respect to the perturbed graphs. In practice, the training set consists of
different graphs
$\left\\{\mathcal{G}_{0},\dots,\mathcal{G}_{i},\dots,\mathcal{G}_{I}\right\\}$
with adjacency matrices
$\left\\{\bm{S}_{0},\dots,\bm{S}_{i},\dots,\bm{S}_{I}\right\\}$, where
$\bm{S}_{i}\in\mathbb{S}$. For each graph, we augment the training set with
perturbed versions that are described by the following graph adjacencies
$\left\\{\bm{S}_{i0},\dots,\bm{S}_{ij},\dots,\bm{S}_{iJ}\right\\}$, where
$\bm{S}_{ij}=\bm{P}_{ij}(\bm{S}_{i}+\bm{M}_{ij})\bm{P}_{ij}^{T}$ for some
symmetric perturbation matrix $\bm{M}_{ij}\in{\\{-1,0,1\\}}^{n\times n}$ and
permutation matrix $\bm{P}_{ij}$. Then we train according to (10) where
$\mathbb{E}_{\mathbb{S}},\mathbb{E}_{\mathbb{M}}$ correspond to empirical
expectations. Note that training according to (10) also benefits the
robustness of the model, which is crucial in deep learning tasks (Wang et al.,
2022). A schematic illustration of the training process can be found in Fig.
1.

######  Remark 4.1.

(Large-scale network alignment by transference)
The proposed framework learns a mapping $\phi:\mathbb{G}\to\mathbb{R}^{N\times
F}$ that produces expressive and robust node representations for a family of
graphs $\mathcal{G}\in\mathbb{G}$. This mapping is designed in such a way that
the problem in (2) approximates the problem in (1) and allows solving network
alignment in polynomial time. The proposed framework is particularly useful in
large-scale network alignment. It leverages the transferability properties of
the GNN encoder (Ruiz et al., 2020), along with the novel training design, and
enables execution in large-scale graphs. Overall, the model is trained on
regularly-sized graphs, and this process identifies and underlying low-
dimensional signal regularities that also appear in big-data graphs. By doing
so, the learned mapping can be applied to larger, big-data graphs with high
accuracy and efficiency.

###  4.4 Alignment and Complexity analysis

After learning the powerful T-GAE node embeddings, network alignment is
performed by solving the linear assignment problem, presented in (2). An
illustration of the assignment is presented in Fig. 2.

To analyze the complexity of our approach we study the 3 main parts of T-GAE:
a) The design of the input structural features, b) The message-passing GNN
that produces node embeddings, and c) the linear assignment algorithm. The
computation of our neighborhood-based structural features is expected to take
$\mathcal{O}\left(\left|\mathcal{V}\right|\right)$ in real graphs, as proved
in Henderson et al. (2011). The computational and memory complexity of the
message-passing GNN is
$\mathcal{O}\left(\left|\mathcal{V}\right|c^{2}+\left|\mathcal{E}\right|c\right)$,
and $\mathcal{O}\left(\left|\mathcal{V}\right|c\right)$, where $c$ is the
width of the GNN. The computational complexity to align the nodes of the graph
is $\mathcal{O}\left(\left|\mathcal{V}\right|^{2}\right)$ since we are using
the suboptimal greedy Hungarian. If we want to optimally solve the linear
assignment problem we need to use the Hungarian algorithm that has
$\mathcal{O}\left(\left|\mathcal{V}\right|^{3}\right)$ complexity. If we want
to process very large graphs we can embed the nodes in 1-dimensional space and
use a sorting algorithm with complexity
$\mathcal{O}\left(\left|\mathcal{V}\right|\text{log}\left(\left|\mathcal{V}\right|\right)\right)$
to perform linear assignment. Overall the complexity of T-GAE is
$\mathcal{O}\left(\left|\mathcal{V}\right|^{2}\right)$, or
$\mathcal{O}\left(\left|\mathcal{V}\right|c^{2}+\left|\mathcal{E}\right|c+\left|\mathcal{V}\right|\text{log}\left(\left|\mathcal{V}\right|\right)\right)$
for very large graphs.

##  5 Experiments

In this section, we evaluate the performance of the proposed framework on both
graph and sub-graph alignment with various benchmark networks. We compare
against several baselines and assess the performance of the competing methods
in terms of matching accuracy, hit-rate, and runtime.

Figure 2: Alignment pipeline for the proposed T-GAE framework. The node
features produced by T-GAE are used to calculate a pairwise distance matrix,
followed by the greedy Hungarian algorithm to predict node correspondences.

###  5.1 Datasets and baselines

Table 2 provides a brief overview of the considered networks. We compare the
performance of the proposed T-GAE with 3 categories of baseline methods: (a)
GNN based methods: WAlign (Gao et al., 2021b); (b) Graph/Node embedding
techniques: NetSimile (Berlingerio et al., 2013), Spectral (Umeyama, 1988),
DeepWalk (Perozzi et al., 2014), (Grover & Leskovec, 2016b), and GraphWave
(Donnat et al., 2018); (c) Optimization based graph matching algorithms: FINAL
(Zhang & Tong, 2016). In the case of graphs without attributes FINAL is
equivalent to the popular Isorank (Singh et al., 2008) algorithm, whereas
using NetSimile as an input to FINAL resulted in inferior performance and was
therefore omitted. Further details about the datasets and the baselines can be
found in Appendix E.

For graph matching experiments, we consider graphs without node attributes,
and design the input to the GNN models, using $7$ structural features proposed
in (Berlingerio et al., 2013). The features include the degree of each node,
the local and average clustering coefficient, and the number of edges,
outgoing edges, and neighbors in each node’s egonet. As a result, the
performance of NetSimile provides a measure to assess the benefit of using
T-GAE for node embedding.

Table 2: Summary of Dataset statistics

Task | Dataset | $|\mathcal{V}|$ | $|\mathcal{E}|$ |  $\\#$ Aligned Edges | Network Type
---|---|---|---|---|---
Graph Matching | Celegans (Kunegis, 2013) | 453 | 2,025 | 2,025 | Interactome
Arenas (Leskovec & Krevl, 2014) | 1,135 | 3,982 | 3,982 | Email Communication
Douban (Zhang & Tong, 2016) | 3,906 | 7,215 | 7,215 | Social Network
Cora (Sen et al., 2008) | 2,708 | 5,278 | 5,278 | Citation Network
Dblp (Pan et al., 2016) | 17,716 | 52,867 | 52,867 | Citation Network
| Coauthor CS (Shchur et al., 2018) | 18,333 | 81,894 | 81,894 | Coauthor Network
Subraph Matching |  ACM-DBLP (Zhang & Tong, 2019) |  9,872 9,916 |  39,561 44,808 | 6,352 | Citation Network
Douban Online-Offline (Zhang & Tong, 2016) |  3,906 1,118 |  1,632 3,022 | 1,118 | Social Network

###  5.2 Graph Matching Experiments

To test the performance of the competing methods, we first attempt to match
the graphs of Table 2 with permuted and perturbed versions of them. In
particular, let $\mathcal{G}$ be a graph of Table 2 with adjacency matrix
$\bm{S}$. For each graph we produce 10 permuted-perturbed versions according
to $\hat{\bm{S}}=\bm{P}\left(\bm{S}+\bm{M}\right)\bm{P}^{T}$, where
$\bm{M}\in\\{-1,0,1\\}^{N\times N}$ and $\bm{P}$ is a permutation matrix. For
each perturbation level $p\in\\{0,1\%,5\%\\}$, the total number of
perturbations is defined as $p|\mathcal{E}|$, where $|\mathcal{E}|$ is the
number of edges of the original graph. Then every edge and non-edge share the
same probability of being removed or added. We also conducted experiments by
removing edges according to the degrees of its vertices. Results for that
model are discussed in Appendix H.

####  5.2.1 Transferability Analysis

We first test the ability of T-GAE to perform large-scale network alignment
and transfer across different datasets. To this end, we train T-GAE according
to (9), where $\mathbb{S}$ consist of the small-size networks, i.e., Celegans,
Arena, Douban, and Cora. Then we resort to transfer learning and use the T-GAE
encoder to produce node embedding on (a) perturbed versions of Celegans,
Arena, Douban, and Cora, and (b) larger graphs, i.e., Dblp, and Coauthor CS.
Note that neither the larger graphs, nor the perturbed versions of the small
graphs were considered during training. This is in contrast with all competing
baselines that are retrained on every testing graph pair. The average and
standard deviation of the matching accuracy for 10 randomly generated
perturbation samples are presented in Table 3.

Table 3: Graph matching accuracy on 10 randomly perturbed samples under
different levels of edge editing. The proposed T-GAE is trained on the clean
Celegans, Arena, Douban, and Cora networks, and tested on noisy versions of
them and the larger Dblp, and Coauthor CS. We test 3 different message-passing
mechanisms for the layers of T-GAE as annotated in the table. Accuracy above
80% is highlighted in green, 40% to 80% accuracy is in yellow, and performance
below 40% is in red.

|  Algorithm |  Celegans |  Arenas |  Douban |  Cora |  Dblp |  Coauthor CS
---|---|---|---|---|---|---|---
$0\%$ perturbation |  Spectral |  ${78.5\pm 18.4}$ |  ${87.9\pm 0.4}$ |  ${82.1\pm 23.2}$ |  ${85.0\pm 0.4}$ |  ${67.6\pm 33.8}$ |  ${97.5\pm 0.1}$
NetSimile |  ${72.7\pm 0.9}$ |  ${84.9\pm 0.8}$ |  ${46.4\pm 0.4}$ |  ${73.7\pm 0.4}$ |  ${63.7\pm 0.2}$ |  ${90.9\pm 0.1}$
FINAL |  $\mathbf{92.2\pm 1.2}$ |  ${88.1\pm 0.4}$ |  ${89.9\pm 0.3}$ |  $\mathbf{87.5\pm 0.7}$ |  ${85.6\pm 0.2}$ |  $\mathbf{97.6\pm 0.1}$
GraphWave |  ${65.3\pm 1.7}$ |  ${70.7\pm 1.3}$ |  ${17.5\pm 0.2}$ |  ${8.3\pm 0.4}$ |  — |  —
WAlign |  ${88.4\pm 1.6}$ |  ${88.3\pm 0.2}$ |  $\mathbf{90.0\pm 0.4}$ |  ${87.2\pm 0.4}$ |  ${85.6\pm 0.2}$ |  ${97.5\pm 0.2}$
T-GAE (GNNc) |  ${89.5\pm 1.3}$ |  $\mathbf{88.4\pm 0.5}$ |  ${90.1\pm 0.4}$ |  ${87.1\pm 0.6}$ |  ${85.6\pm 0.1}$ |  $\mathbf{97.6\pm 0.1}$
|  T-GAE (GCN) |  ${87.8\pm 1.1}$ |  ${88.3\pm 0.4}$ |  ${89.9\pm 0.2}$ |  ${87.4\pm 0.4}$ |  $\mathbf{85.8\pm 0.1}$ |  $\mathbf{97.6\pm 0.1}$
|  T-GAE (GIN) |  ${88.9\pm 1.3}$ |  ${87.8\pm 0.5}$ |  ${89.9\pm 0.4}$ |  ${87.3\pm 0.4}$ |  ${85.6\pm 0.2}$ |  $\mathbf{97.6\pm 0.1}$
$1\%$ perturbation |  Spectral |  ${68.5\pm 16.1}$ |  ${73.7\pm 8.4}$ |  ${25.8\pm 27.2}$ |  ${59.1\pm 9.3}$ |  ${55.6\pm 19.0}$ |  ${58.2\pm 22.1}$
NetSimile |  ${66.3\pm 3.8}$ |  ${80.1\pm 0.7}$ |  ${40.0\pm 1.2}$ |  ${66.4\pm 1.6}$ |  ${55.1\pm 1.7}$ |  ${75.2\pm 2.2}$
FINAL |  ${33.2\pm 7.8}$ |  ${31.8\pm 8.7}$ |  ${27.8\pm 5.7}$ |  ${30.0\pm 3.3}$ |  ${15.2\pm 3.3}$ |  ${13.3\pm 5.0}$
GraphWave |  ${22.5\pm 22.4}$ |  ${39.0\pm 23.1}$ |  ${9.9\pm 5.9}$ |  ${3.7\pm 2.9}$ |  — |  —
WAlign |  ${80.7\pm 3.0}$ |  ${84.3\pm 0.5}$ |  ${77.2\pm 4.8}$ |  ${80.1\pm 1.2}$ |  ${73.1\pm 1.6}$ |  ${75.2\pm 5.4}$
T-GAE (GNNc) |  ${83.4\pm 1.6}$ |  ${83.3\pm 1.0}$ |  ${83.3\pm 0.6}$ |  ${81.0\pm 0.9}$ |  ${75.3\pm 1.5}$ |  ${81.6\pm 1.1}$
|  T-GAE (GCN) |  ${83.4\pm 2.3}$ |  $\mathbf{84.8\pm 0.6}$ |  ${84.1\pm 1.2}$ |  ${82.5\pm 0.8}$ |  ${76.0\pm 1.1}$ |  ${84.3\pm 0.8}$
|  T-GAE (GIN) |  $\mathbf{84.1\pm 1.1}$ |  ${84.4\pm 1.2}$ |  $\mathbf{84.9\pm 0.6}$ |  $\mathbf{82.9\pm 0.5}$ |  $\mathbf{79.1\pm 0.4}$ |  $\mathbf{86.5\pm 0.8}$
$5\%$ perturbation |  Spectral |  ${24.9\pm 15.9}$ |  ${44.0\pm 16.3}$ |  ${23.8\pm 20.6}$ |  ${29.5\pm 0.8}$ |  ${28.0\pm 7.8}$ |  ${9.7\pm 5.0}$
NetSimile |  ${41.1\pm 13.0}$ |  ${46.5\pm 7.6}$ |  ${20.7\pm 4.6}$ |  ${41.2\pm 3.3}$ |  ${19.5\pm 4.8}$ |  ${26.3\pm 6.0}$
FINAL |  ${10.4\pm 2.7}$ |  ${8.0\pm 1.8}$ |  ${7.8\pm 3.0}$ |  ${6.7\pm 2.8}$ |  ${2.7\pm 0.9}$ |  ${2.0\pm 0.4}$
GraphWave |  ${7.6\pm 9.2}$ |  ${3.6\pm 3.6}$ |  ${1.9\pm 2.8}$ |  ${0.8\pm 0.3}$ |  — |  —
WAlign |  ${42.4\pm 21.1}$ |  ${30.0\pm 15}$ |  ${21.9\pm 10.7}$ |  ${33.4\pm 7.3}$ |  ${15.9\pm 8.3}$ |  ${11.3\pm 7.5}$
T-GAE (GNNc) |  $\mathbf{50.8\pm 3.3}$ |  ${45.2\pm 8.0}$ |  ${44.5\pm 7.5}$ |  ${47.3\pm 3.3}$ |  ${32.7\pm 1.6}$ |  $\pagecolor{red!50}{21.7\pm 5.2}$
|  T-GAE (GCN) |  ${37.5\pm 9.7}$ |  ${45.0\pm 8.2}$ |  ${49.5\pm 4.2}$ |  ${50.9\pm 2.8}$ |  ${31.8\pm 2.8}$ |  $\pagecolor{red!50}{23.0\pm 4.1}$
|  T-GAE (GIN) |  ${48.3\pm 9.1}$ |  $\mathbf{47.1\pm 5.6}$ |  $\mathbf{57.9\pm 6.1}$ |  $\mathbf{58.2\pm 2.0}$ |  $\mathbf{40.8\pm 2.1}$ |  $\pagecolor{red!50}\mathbf{26.9\pm 5.4}$

Our first observation is that for zero perturbation most algorithms are able
to achieve a high level of matching accuracy. This is expected, since for zero
perturbation the network alignment is equivalent to graph isomorphism.
Furthermore, there is a clear benefit of processing the NetSimile embeddings
with GNNs since they offer up to $22\%$ performance increase. When some
perturbation is added, the conclusions are straightforward. Our proposed T-GAE
markedly outperforms all the competing alternatives and shows the desired
robustness to efficiently perform network alignment.

Regarding the ability of T-GAE to perform large-scale network alignment the
results are definitive. T-GAE enables low-complexity training with small
graphs, and execution at larger settings by leveraging transfer learning. In
particular, it is able to achieve very high levels of matching accuracy for
both Dblp and Coauthor CS, for $p=0\%,~{}0.1\%$. To the best of our knowledge,
this is the first attempt that performs exact alignment on a network at the
order of $20$k nodes and $80$k edges.

####  5.2.2 Perturbed Training

In the previous experiment, T-GAE is trained with a family of original graphs
and tested to match perturbed versions of a larger family of graphs. T-GAE
exhibited more robust performance compared to the baseline methods, however,
its matching accuracy dropped significantly as the perturbation level of
testing data increased. To tackle this problem we follow a self-supervised
learning approach and train T-GAE with a family of real graphs and
perturbations of them. We train according to (10), which aims to produce
similar node embeddings for both the original graphs and perturbed versions of
them. The data augmentation process follows the previously explained
perturbation models. Similar to the previous experiment we train over the four
small datasets and execute over all datasets. Note that training and testing
is performed with different perturbations of the original graphs. Table 4
reports the testing results of the best T-GAE when training is performed with
graph perturbations.

Table 4: Performance Comparison of T-GAE when trained with/without
perturbation.

Algorithm |  Celegans |  Arenas |  Douban |  Cora |  Dblp |  Coauthor CS
---|---|---|---|---|---|---
0% perturbation
T-GAE |  ${89.5\pm 1.3}$ |  ${88.4\pm 0.5}$ |  ${90.3\pm 0.4}$ |  ${87.4\pm 0.4}$ |  ${85.6\pm 0.1}$ |  ${97.6\pm 0.1}$
T-GAE with pert. |  $\mathbf{89.7\pm 1.5}$ |  $\mathbf{88.6\pm 0.6}$ |  $\mathbf{90.1\pm 0.4}$ |  $\mathbf{87.4\pm 0.5}$ |  $\mathbf{85.7\pm 0.2}$ |  $\mathbf{97.7\pm 0.1}$
1% perturbation
T-GAE |  $\mathbf{84.1\pm 1.1}$ |  ${84.8\pm 0.6}$ |  ${84.9\pm 0.6}$ |  ${82.9\pm 0.5}$ |  ${79.1\pm 0.4}$ |  ${86.5\pm 0.8}$
T-GAE with pert. |  ${83.4\pm 1.6}$ |  $\mathbf{85.6\pm 0.5}$ |  $\mathbf{85.2\pm 0.6}$ |  $\mathbf{83.2\pm 0.9}$ |  $\mathbf{79.7\pm 0.4}$ |  $\mathbf{87.1\pm 1.0}$
5% perturbation
T-GAE |  ${50.8\pm 3.3}$ |  ${47.1\pm 5.6}$ |  ${57.9\pm 6.1}$ |  $\mathbf{58.2\pm 2.0}$ |  ${40.8\pm 2.1}$ |  ${26.9\pm 5.4}$
T-GAE with pert. |  $\mathbf{52.3\pm 5.4}$ |  $\mathbf{62.6\pm 2.2}$ |  $\mathbf{58.5\pm 5.0}$ |  ${57.4\pm 2.7}$ |  $\mathbf{43.6\pm 3.7}$ |  $\mathbf{30.4\pm 7.4}$

We observe that incorporating graph perturbations in the training process
significantly helps in high perturbation levels and benefits the robustness of
the proposed method. On the other hand, when testing on low levels of
perturbations, using the original graph or perturbations to train the T-GAE
does not lead to significant changes. In particular, at 5% testing
perturbation, T-GAE archives 15.5% increase in the Arenas dataset, whereas at
0% and 1% testing perturbation the increase is 0.2% and 0.8% respectively.

###  5.3 Sub-graph Matching Experiments

In this subsection, we test the performance of T-GAE in matching subgraphs of
different networks that have aligned nodes (nodes that represent the same
entities in different networks). For example, in ACM-DBLP data set, the task
is to find and match the papers that appear in both citation networks, whereas
in social networks like Douban Online-Offline, we aim to identify the users
that take part into both online and offline activities. To this end, we test
the performance of the proposed T-GAE framework on these datasets. We compare
two different approaches. In the first, T-GAE is trained according to (9) to
produce embedding for the graph pair we aim to match, i.e., the ACM-DBLP pair,
or the Douban Online-Offline pair. In the second, T-GAE is trained according
to (9) with Celegans, Arena, Douban, and Cora, and transfer learning is used
to match the targeted graph pair. To assess the performance of the competing
algorithms we measure the hit rate (Järvelin & Kekäläinen, 2000). The results
are presented in Fig. 5. The execution time for the reported results is
presented in Appendix F.

Figure 3: Subgraph Matching comparison between competing algorithms.

We observe a significant improvement in matching accuracy with GNN-based
methods compared to traditional graph or node embedding techniques. These
results demonstrate the ability of GNNs to generate expressive and robust node
embeddings compared to classical algorithms. In particular, our proposed
framework, T-GAE, consistently achieves the best performance among all
competing methods. This suggests that the training framework (10), illustrated
in Fig. 1, provides an efficient approach to network alignment. It is also
notable, that T-GAE works well with both types of graph convolutions (GIN,
GCN). This result indicates that the proposed framework has the potential to
be extended to different types of neural networks.

Limitations: Although our approach achieves state-of-the-art performance in
aligning real-graphs, approaching network alignment with a learning method,
remains a heuristic and does not offer optimality guarantees. Furthermore, in
order to process large graphs we cast network alignment as a self-supervised
task. As a result in small-scale settings where the task can be tackled with
computationally intensive efficient methods, our algorithm is not expected to
perform the best. Finally, for very large graphs the complexity of T-GAE
$\mathcal{O}(|\mathcal{V}|^{2})$ is limiting and therefore our alternative
method with complexity
$\mathcal{O}(|\mathcal{V}|c^{2}+|\mathcal{E}|c+|\mathcal{V}|\text{log}(|\mathcal{V}|))$
has to be employed.

##  6 Conclusion

We proposed T-GAE, a generalized transferable graph autoencoder to perform
network alignment on a large scale. T-GAE can be trained with multiple graphs
and produce robust and permutation equivariant embeddings tailored to network
alignment. The produced embeddings are related to the spectral decomposition
of the graph and are at least as good in graph matching as certain spectral
methods. The proposed approach leverages transfer learning and data
augmentation and achieves high levels of matching accuracy for graphs with
more than $15,000$ nodes. Experiments with real-world benchmarks on both graph
matching and subgraph matching tasks demonstrated the effectiveness and limits
of the proposed approach.

## References

  * Abboud et al. (2021) Ralph Abboud, Ismail Ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz.  The surprising power of graph neural networks with random node initialization.  In _IJCAI_ , 2021.
  * Anstreicher & Brixius (2001) Kurt M Anstreicher and Nathan W Brixius.  Solving quadratic assignment problems using convex quadratic programming relaxations.  _Optimization Methods and Software_ , 16(1-4):49–68, 2001.
  * Berlingerio et al. (2013) Michele Berlingerio, Danai Koutra, Tina Eliassi-Rad, and Christos Faloutsos.  Network similarity via multiple social theories.  In _Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining_ , pp. 1439–1440, 2013.
  * Chen et al. (2018) Jiazhou Chen, Hong Peng, Guoqiang Han, Hongmin Cai, and Jiulun Cai.  HOGMMNC: a higher order graph matching with multiple network constraints model for gene–drug regulatory modules identification.  _Bioinformatics_ , 35(4):602–610, 07 2018.  ISSN 1367-4803.  doi: 10.1093/bioinformatics/bty662.  URL https://doi.org/10.1093/bioinformatics/bty662.
  * Chen et al. (2020) Xiyuan Chen, Mark Heimann, Fatemeh Vahedian, and Danai Koutra.  Cone-align: Consistent network alignment with proximity-preserving node embedding.  In _Proceedings of the 29th ACM International Conference on Information & Knowledge Management_, pp. 1985–1988, 2020.
  * Conte et al. (2003) D. Conte, P. Foggia, C. Sansone, and M. Vento.  Graph matching applications in pattern recognition and image processing.  In _Proceedings 2003 International Conference on Image Processing (Cat. No.03CH37429)_ , volume 2, pp. II–21, 2003.  doi: 10.1109/ICIP.2003.1246606.
  * Ding et al. (2020) Jian Ding, Zongming Ma, Yihong Wu, and Jiaming Xu.  Efficient random graph matching via degree profiles, 2020.
  * Donnat et al. (2018) Claire Donnat, Marinka Zitnik, David Hallac, and Jure Leskovec.  Learning structural node embeddings via diffusion wavelets.  In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_. ACM, jul 2018.  doi: 10.1145/3219819.3220025.  URL https://doi.org/10.1145%2F3219819.3220025.
  * 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.
  * Feizi et al. (2019) Soheil Feizi, Gerald Quon, Mariana Recamonde-Mendoza, Muriel Medard, Manolis Kellis, and Ali Jadbabaie.  Spectral alignment of graphs.  _IEEE Transactions on Network Science and Engineering_ , 7(3):1182–1197, 2019.
  * Gainza et al. (2020) P. Gainza, F. Sverrisson, F. Monti, E. Rodolà, D. Boscaini, M. M. Bronstein, and B. E. Correia.  Deciphering interaction fingerprints from protein molecular surfaces using geometric deep learning.  _Nature Methods_ , 17(2):184–192, February 2020.
  * Gama et al. (2020) Fernando Gama, Joan Bruna, and Alejandro Ribeiro.  Stability properties of graph neural networks.  _IEEE Transactions on Signal Processing_ , 68:5680–5695, 2020.
  * Gao et al. (2021a) Ji Gao, Xiao Huang, and Jundong Li.  Unsupervised graph alignment with wasserstein distance discriminator.  In _Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining_, pp. 426–435, 2021a.
  * Gao et al. (2021b) Ji Gao, Xiao Huang, and Jundong Li.  Unsupervised graph alignment with wasserstein distance discriminator.  In _Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining_, KDD ’21, pp. 426–435, New York, NY, USA, 2021b. Association for Computing Machinery.  ISBN 9781450383325.  doi: 10.1145/3447548.3467332.  URL https://doi.org/10.1145/3447548.3467332.
  * 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_ , pp. 1263–1272. PMLR, 2017.
  * Grover & Leskovec (2016a) Aditya Grover and Jure Leskovec.  node2vec: Scalable feature learning for networks.  In _Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining_ , pp. 855–864, 2016a.
  * Grover & Leskovec (2016b) Aditya Grover and Jure Leskovec.  node2vec: Scalable feature learning for networks, 2016b.
  * Heimann et al. (2018) Mark Heimann, Haoming Shen, Tara Safavi, and Danai Koutra.  Regal: Representation learning-based graph alignment.  In _Proceedings of the 27th ACM international conference on information and knowledge management_ , pp. 117–126, 2018.
  * Henderson et al. (2011) Keith Henderson, Brian Gallagher, Lei Li, Leman Akoglu, Tina Eliassi-Rad, Hanghang Tong, and Christos Faloutsos.  It’s who you know: graph mining using recursive structural features.  In _Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining_ , pp. 663–671, 2011.
  * Järvelin & Kekäläinen (2000) Kalervo Järvelin and Jaana Kekäläinen.  Ir evaluation methods for retrieving highly relevant documents.  In _Proceedings of the 23rd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval_ , SIGIR ’00, pp. 41–48, New York, NY, USA, 2000. Association for Computing Machinery.  ISBN 1581132263.  doi: 10.1145/345508.345545.  URL https://doi.org/10.1145/345508.345545.
  * Jiang et al. (2021) Dejun Jiang, Zhenxing Wu, Chang Yu Hsieh, Guangyong Chen, Ben Liao, Zhe Wang, Chao Shen, Dongsheng Cao, Jian Wu, and Tingjun Hou.  Could graph neural networks learn better molecular representation for drug discovery? a comparison study of descriptor-based and graph-based models.  _Journal of Cheminformatics_ , 13(1):12, dec 2021.
  * Kanatsoulis & Ribeiro (2022) Charilaos I Kanatsoulis and Alejandro Ribeiro.  Representation power of graph neural networks: Improved expressivity via algebraic analysis.  _arXiv preprint arXiv:2205.09801_ , 2022.
  * Karakasis et al. (2021) Paris A Karakasis, Aritra Konar, and Nicholas D Sidiropoulos.  Joint graph embedding and alignment with spectral pivot.  In _Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining_, pp. 851–859, 2021.
  * Kipf & Welling (2017) Thomas N Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  In _International Conference on Learning Representations_ , 2017.
  * Klau (2009) Gunnar W Klau.  A new graph-based method for pairwise global network alignment.  _BMC bioinformatics_ , 10(1):1–9, 2009.
  * Konar & Sidiropoulos (2020) Aritra Konar and Nicholas D Sidiropoulos.  Graph matching via the lens of supermodularity.  _IEEE Transactions on Knowledge and Data Engineering_ , 34(5):2200–2211, 2020.
  * Koopmans & Beckmann (1957) Tjalling C Koopmans and Martin Beckmann.  Assignment problems and the location of economic activities.  _Econometrica: journal of the Econometric Society_ , pp. 53–76, 1957.
  * Kuhn (1955a) Harold W Kuhn.  The hungarian method for the assignment problem.  _Naval research logistics quarterly_ , 2(1-2):83–97, 1955a.
  * Kuhn (1955b) Harold W Kuhn.  The hungarian method for the assignment problem.  _Naval research logistics quarterly_ , 2(1-2):83–97, 1955b.
  * Kunegis (2013) Jérôme Kunegis.  Konect: the koblenz network collection.  _Proceedings of the 22nd International Conference on World Wide Web_ , 2013.
  * Leskovec & Krevl (2014) Jure Leskovec and Andrej Krevl.  SNAP Datasets: Stanford large network dataset collection.  http://snap.stanford.edu/data, June 2014.
  * Li et al. (2022) Jinning Li, Huajie Shao, Dachun Sun, Ruijie Wang, Yuchen Yan, Jinyang Li, Shengzhong Liu, Hanghang Tong, and Tarek Abdelzaher.  Unsupervised belief representation learning with information-theoretic variational graph auto-encoders.  In _Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval_. ACM, jul 2022.  doi: 10.1145/3477495.3532072.  URL https://doi.org/10.1145%2F3477495.3532072.
  * Mao et al. (2023) Cheng Mao, Yihong Wu, Jiaming Xu, and Sophie H. Yu.  Random graph matching at otter’s threshold via counting chandeliers, 2023.
  * Maron et al. (2018) Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman.  Invariant and equivariant graph networks.  In _International Conference on Learning Representations_ , 2018.
  * Nilizadeh et al. (2014) Shirin Nilizadeh, Apu Kapadia, and Yong-Yeol Ahn.  Community-enhanced de-anonymization of online social networks.  In _Proceedings of the 2014 acm sigsac conference on computer and communications security_ , pp. 537–548, 2014.
  * Ogaard et al. (2013) Kirk Ogaard, Heather Roy, Sue Kase, Rakesh Nagi, Kedar Sambhoos, and Moises Sudit.  Discovering patterns in social networks with graph matching algorithms.  In Ariel M. Greenberg, William G. Kennedy, and Nathan D. Bos (eds.), _Social Computing, Behavioral-Cultural Modeling and Prediction_ , pp. 341–349, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg.  ISBN 978-3-642-37210-0.
  * Pan et al. (2016) Shirui Pan, Jia Wu, Xingquan Zhu, Chengqi Zhang, and Yang Wang.  Tri-party deep network representation.  In Subbarao Kambhampati (ed.), _Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, New York, NY, USA, 9-15 July 2016_ , pp. 1895–1901. IJCAI/AAAI Press, 2016.
  * Peng et al. (2010) Jiming Peng, Hans Mittelmann, and Xiaoxue Li.  A new relaxation framework for quadratic assignment problems based on matrix splitting.  _Mathematical Programming Computation_ , 2:59–77, 2010.
  * Perozzi et al. (2014) Bryan Perozzi, Rami Al-Rfou, and Steven Skiena.  DeepWalk.  In _Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining_. ACM, aug 2014.  doi: 10.1145/2623330.2623732.  URL https://doi.org/10.1145%2F2623330.2623732.
  * Racz & Sridhar (2021) Miklos Racz and Anirudh Sridhar.  Correlated stochastic block models: Exact graph matching with applications to recovering communities.  In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), _Advances in Neural Information Processing Systems_ , volume 34, pp. 22259–22273. Curran Associates, Inc., 2021.  URL https://proceedings.neurips.cc/paper/2021/file/baf4f1a5938b8d520b328c13b51ccf11-Paper.pdf.
  * Rossi & Ahmed (2015) Ryan A. Rossi and Nesreen K. Ahmed.  The network data repository with interactive graph analytics and visualization.  In _AAAI_ , 2015.  URL https://networkrepository.com.
  * Ruiz et al. (2020) Luana Ruiz, Fernando Gama, and Alejandro Ribeiro.  Gated graph recurrent neural networks.  _IEEE Transactions on Signal Processing_ , 68:6303–6318, 2020.
  * Sardellitti et al. (2017) Stefania Sardellitti, Sergio Barbarossa, and Paolo Di Lorenzo.  On the graph fourier transform for directed graphs.  _IEEE Journal of Selected Topics in Signal Processing_ , 11(6):796–811, 2017.
  * Sen et al. (2008) Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad.  Collective classification in network data.  _AI magazine_ , 29(3):93–93, 2008.
  * Shchur et al. (2018) Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann.  Pitfalls of graph neural network evaluation.  _Relational Representation Learning Workshop, NeurIPS 2018_ , 2018.
  * Singh et al. (2008) Rohit Singh, Jinbo Xu, and Bonnie Berger.  Global alignment of multiple protein interaction networks with application to functional orthology detection.  _Proceedings of the National Academy of Sciences_ , 105(35):12763–12768, 2008.
  * Strokach et al. (2020) Alexey Strokach, David Becerra, Carles Corbi-Verge, Albert Perez-Riba, and Philip M. Kim.  Fast and flexible protein design using deep graph neural networks.  _Cell Systems_ , 11(4):402–411.e4, October 2020.
  * Umeyama (1988) S. Umeyama.  An eigendecomposition approach to weighted graph matching problems.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 10(5):695–703, 1988.  doi: 10.1109/34.6778.
  * Vogelstein et al. (2015) Joshua T Vogelstein, John M Conroy, Vince Lyzinski, Louis J Podrazik, Steven G Kratzer, Eric T Harley, Donniell E Fishkind, R Jacob Vogelstein, and Carey E Priebe.  Fast approximate quadratic programming for graph matching.  _PLOS one_ , 10(4):e0121002, 2015.
  * Wang et al. (2022) Xuezhi Wang, Haohan Wang, and Diyi Yang.  Measure and improve robustness in nlp models: A survey, 2022.
  * Wu et al. (2020) Shiwen Wu, Fei Sun, Wentao Zhang, Xu Xie, and Bin Cui.  Graph neural networks in recommender systems: a survey.  _ACM Computing Surveys (CSUR)_ , 2020.
  * Wu et al. (2022) Yihong Wu, Jiaming Xu, and Sophie H. Yu.  Settling the sharp reconstruction thresholds of random graph matching, 2022.
  * 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.  URL https://openreview.net/forum?id=ryGs6iA5Km.
  * Ying et al. (2018) Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec.  Graph convolutional neural networks for web-scale recommender systems.  _Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , 10:974–983, June 2018.
  * Zhang & Tong (2016) Si Zhang and Hanghang Tong.  Final: Fast attributed network alignment.  In _Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , KDD ’16, pp. 1345–1354, New York, NY, USA, 2016. Association for Computing Machinery.  ISBN 9781450342322.  doi: 10.1145/2939672.2939766.  URL https://doi.org/10.1145/2939672.2939766.
  * Zhang & Tong (2019) Si Zhang and Hanghang Tong.  Attributed network alignment: Problem definitions and fast solutions.  _IEEE Transactions on Knowledge and Data Engineering_ , 31:1680–1692, 2019.  URL https://api.semanticscholar.org/CorpusID:70142000.

##  Appendix A Notation and further reading

Our notation is summarized in Table 1.

Table 1: Key notations used in this paper. $\mathcal{G}$ | $\triangleq$ |  Graph
---|---|---
$\mathcal{V}$ | $\triangleq$ |  Set of nodes
$\mathcal{E}$ | $\triangleq$ |  Set of edges
$N$ | $\triangleq$ |  Number of nodes
$\bm{D}$ | $\triangleq$ |  Degree matrix
$\bm{S}$ | $\triangleq$ |  $\\{0,1\\}^{N\times N}$ adjacency matrix
$\bm{X}$ | $\triangleq$ |  $N\times D$ feature matrix
$\bm{H}$ | $\triangleq$ |  aggregation results of GNN convolution
$\bm{W}$ | $\triangleq$ |  weight matrix of the Graph Neural Network
$\bm{N}_{v}$ | $\triangleq$ |  neighbors of node v
$\bm{I}$ | $\triangleq$ |  Identity matrix
$\bm{0}$ | $\triangleq$ |  vector or matrix of zeros
$\bm{A}^{T}$ | $\triangleq$ |  transpose of matrix $\bm{A}$
$\bm{A}_{rc}$ | $\triangleq$ |  entry at r-th row and j-th column of matrix $\bm{A}$
$\lVert\cdot\rVert_{F}$ | $\triangleq$ |  Frobenius norm

Graph matching, as an important problem, has been studied not only by the
community of data mining, it has also been mathematically and statistically
investigated. A number of approaches have been proposed to solve this problem
for Erdős Rényi random graphs $G(n,\frac{d}{n})$. It has been proved that a
perfectly true vertex correspondence can be recovered in polynomial time with
high probability (Ding et al., 2020). Furthermore, a sharp threshold has been
proved for both Erdős Rényi model and Gaussian model (Wu et al., 2022). Most
recently, a novel approach to calculate similarity scores based on counting
weighted trees rooted at each vertex has been proposed Mao et al. (2023). Such
approach has been proved to be effective in solving the aforementioned network
alignment problem on random graphs with high probability. Readers are
encouraged to refer to the authors of these publications (Ding et al., 2020;
Wu et al., 2022; Mao et al., 2023) for further reading.

##  Appendix B Spectral characterization of GNNs

What remains to be answered is the ability of a GNN to approximate a function
that performs graph alignment. To understand the function approximation
properties of GNNs we study them in the spectral domain. To this end, we
consider the recursive formula in (4) where $f$ is the summation function and
$g$ is multivariate linear for $K-2$ layers, and the MLP in the $(K-1)$-th
layer. The overall operation can be written in a matrix form as:

$\bm{X}^{(l+1)}=\sigma\left(\sum_{k=0}^{K-1}\bm{S}^{k}\bm{X}^{(l)}\bm{H}_{k}^{(l)}\right),$
(11)

where $\bm{H}_{k}^{(l)}\in\mathbb{R}^{D^{l+1}\times D^{l}}$ is a linear
mapping. Computing the spectral decomposition of $\bm{S}$ yields:

$\bm{X}^{(l+1)}=\sigma\left(\sum_{k=0}^{K-1}\bm{V}\bm{\Lambda}^{k}\bm{V}^{T}\bm{X}^{(l)}\bm{H}_{k}^{(l)}\right)=\sigma\left(\sum_{k=0}^{K-1}\sum_{n=1}^{N}\lambda_{n}^{k}\bm{v}_{n}\bm{v}_{n}^{T}\bm{X}^{(l)}\bm{H}_{k}^{(l)}\right).$
(12)

Then each each column of $\bm{X}^{(l+1)}$ can be written as

$\displaystyle\bm{X}^{(l+1)}[:,i]$
$\displaystyle=\sigma\left(\sum_{k=0}^{K-1}\sum_{n=1}^{N}\lambda_{n}^{k}\bm{v}_{n}\bm{v}_{n}^{T}\bm{X}^{(l)}\bm{H}_{k}^{(l)}[:,i]\right)=\sigma\left(\sum_{n=1}^{N}a_{n}^{(i)}\bm{v}_{n}\right),$
(13)

where $\lambda_{n},\bm{v}_{n}$ are the $n-$th eigenvalue and eigenvector and
$a_{n}^{(i)}=\bm{v}_{n}^{T}\bm{X}^{(l)}\sum_{k=0}^{K-1}\lambda_{n}^{k}\bm{H}_{k}^{(l)}[:,i]$
is a scalar related to the Graph Fourier Transform (GFT) of $\bm{X}^{(l)}$
(Sardellitti et al., 2017). It is clear from equation (13) that the output of
each layer is a linear combination of the adjacency eigenvectors, followed by
a pointwise non-linearity. Thus, a GNN can produce unique and more powerful
graph embeddings than spectral methods by processing the eigenvectors and
eigenvalues of the adjacency matrix.

##  Appendix C Proof of Theorem 3.2

To prove Theorem 3.2. We consider one layer GNN with a vector input
$\bm{x}\in\mathbb{R}^{N}$. This GNN can be represented by the following
equation:

$\bm{Y}=\sigma\left(\sum_{k=0}^{K-1}\bm{S}^{k}\bm{x}\bm{h}_{k}^{T}\right),$
(14)

where $\bm{h}_{k}\in\mathbb{R}^{m}$ and $\bm{x}\bm{h}_{k}^{T}$ is an outer-
product operation. The equation in (14) describes a set of $m$ graph filters
of the form:

$\bm{y}_{i}=\sigma\left(\sum_{k=0}^{K-1}h_{k}^{i}\bm{S}^{k}\bm{x}\right),~{}~{}\text{for}~{}i=1,\dots,m$
(15)

###  C.1 White random input and variance computation

Let $\bm{x}$ be a white random vector with $\mathbb{E}\left[\bm{x}\right]=0$
and $\mathbb{E}\left[\bm{x}\bm{x}^{T}\right]=\bm{I}$, where $\bm{I}$ is the
diagonal matrix. Also let $\sigma\left(\cdot\right)=\left(\cdot\right)^{2}$ be
the elementwise square function. Then (15) can be written as:

$\bm{y}_{i}=\left(\sum_{k=0}^{K-1}h_{k}^{i}\bm{S}^{k}\bm{x}\right)^{2}=\text{diag}\left(\sum_{k=0}^{K-1}h_{k}^{i}\bm{S}^{k}\bm{x}\bm{x}^{T}\sum_{j=0}^{K-1}h_{j}^{i}\bm{S}^{j^{T}}\right)$
(16)

Since $\bm{x}$ is a random vector $\bm{y}_{i}$ is also a random vector. The
expected value of $\bm{y}_{i}$ yields:

$\displaystyle\mathbb{E}\left[\bm{y}_{i}\right]$
$\displaystyle=\mathbb{E}\left[\text{diag}\left(\sum_{k=0}^{K-1}h_{k}^{i}\bm{S}^{k}\bm{x}\bm{x}^{T}\sum_{j=0}^{K-1}h_{j}^{i}\bm{S}^{j^{T}}\right)\right]=\text{diag}\left(\sum_{k=0}^{K-1}h_{k}^{i}\bm{S}^{k}\mathbb{E}\left[\bm{x}\bm{x}^{T}\right]\sum_{j=0}^{K-1}h_{j}^{i}\bm{S}^{j^{T}}\right)$
$\displaystyle=\text{diag}\left(\sum_{k=0}^{K-1}h_{k}^{i}\bm{S}^{k}\sum_{j=0}^{K-1}h_{j}^{i}\bm{S}^{j^{T}}\right)$
(17)

###  C.2 Single band filtering

In the second part of the proof we study the graph filter using the spectral
decomposition of the graph:

$\bm{y}=\sum_{k=0}^{K-1}h_{k}\bm{S}^{k}\bm{x}=\sum_{k=0}^{K-1}h_{k}\bm{V}\bm{\Lambda}^{k}\bm{V}^{T}\bm{x}=\sum_{k=0}^{K-1}h_{k}\sum_{n=1}^{N}\lambda_{n}^{k}\bm{v}_{n}\bm{v}_{n}^{T}\bm{x}=\sum_{n=1}^{N}\bm{v}_{n}^{T}\bm{x}\sum_{k=0}^{K-1}h_{k}\lambda_{n}^{k}\bm{v}_{n}.$
(18)

Let us focus on the following polynomial:

$\tilde{h}\left(\lambda\right)=\sum_{k=0}^{K-1}h_{k}\lambda^{k},$ (19)

that represents a graph filter in the frequency domain by. For $q$ distinct
eigenvalues we can write a system of linear equations using the polynomial in
(19):

$\displaystyle\begin{bmatrix}\tilde{h}\left(\lambda_{1}\right)\\\
\tilde{h}\left(\lambda_{2}\right)\\\ \vdots\\\
\tilde{h}\left(\lambda_{q}\right)\end{bmatrix}=\begin{bmatrix}1~{}\lambda_{1}~{}\lambda_{1}^{2}\dots\lambda_{1}^{K-1}\\\
1~{}\lambda_{2}~{}\lambda_{2}^{2}\dots\lambda_{2}^{K-1}\\\ \vdots\\\
1~{}\lambda_{q}~{}\lambda_{q}^{2}\dots\lambda_{q}^{K-1}\\\
\end{bmatrix}\begin{bmatrix}h_{0}\\\ h_{1}\\\ \vdots\\\
h_{K-1}\end{bmatrix}=\bm{W}\bm{h}$ (20)

$\bm{W}$ is a Vandermonde matrix and when $K=q$ the determinant of $\bm{W}$
takes the form:

$\text{det}\left(\bm{W}\right)=\prod_{1\leq i<j\leq
q}\left(\lambda_{i}-\lambda_{j}\right)$ (21)

Since the values $\lambda_{i}$ are distinct, $\bm{W}$ has full column rank and
there exists a graph filter with unique parameters $\bm{h}$ that passes only
the $\lambda$ eigenvalue, i.e.,

$\tilde{h}\left(\lambda_{i}\right)=\bigg{\\{}\begin{matrix}1,~{}\text{if}~{}~{}\lambda_{i}=\lambda\\\
0,~{}\text{if}~{}~{}\lambda_{i}\neq\lambda\end{matrix}$ (22)

Under this parametrization, equation (18) takes the form
$\bm{y}=\bm{v}_{\lambda}\bm{v}_{\lambda}^{T}\bm{x}$, where $\bm{v}_{\lambda}$
is the eigenvector corresponding to $\lambda$.

###  C.3 GNN and absolute eigenvectors

Using the previous analysis we can design parameters $h_{k}$ such that:

$\sum_{k=0}^{K-1}h_{k}\bm{S}^{k}=\bm{v}_{\lambda}\bm{v}_{\lambda}^{T}$ (23)

and then equation (C.1) takes the form:

$\displaystyle\mathbb{E}\left[\bm{y}_{i}\right]=\text{diag}\left(\sum_{k=0}^{K-1}h_{k}^{i}\bm{S}^{k}\sum_{j=0}^{K-1}h_{j}^{i}\bm{S}^{j^{T}}\right)=\text{diag}\left(\bm{v}_{\lambda}\bm{v}_{\lambda}^{T}\bm{v}_{\lambda}\bm{v}_{\lambda}^{T}\right)=\text{diag}\left(\bm{v}_{\lambda}\bm{v}_{\lambda}^{T}\right)=\left|\bm{v}_{\lambda}\right|^{2}$
(24)

We can therefore design $\bm{h}_{k}\in\mathbb{R}^{m}$ for $k=0,\dots,m-1$ to
compute the absolute value of $m$ eigenvectors of $\bm{S}$ that correspond to
the top $m$ distinct eigenvalues, i.e.,

$\displaystyle\mathbb{E}\left[\bm{y}_{i}\right]=|{\bm{u}}_{i}|^{2},\quad
i=1,\dots,m$ (25)

We can do the same for graph $\hat{\bm{S}}$ and compute:

$\displaystyle\mathbb{E}\left[\hat{\bm{y}}_{i}\right]=|\hat{\bm{u}}_{i}|^{2},\quad
i=1,\dots,m$ (27)

Since both $\bm{S},~{}\hat{\bm{S}}$ have distinct eigenvalues, we can
concatenate the output of each neuron and result in layer-1 outputs as:

$\bm{Y}^{(1)}=|\bm{U}|,\quad\hat{\bm{Y}}^{(1)}=|\hat{\bm{U}}|$ (29)

As a result, the previously described GNN can a least yield the same alignment
accuracy as the absolute values of the eigenvectors.

##  Appendix D Data Augmentation-Perturbation Model

Figure 4 gives an illustrative example of data augmentation process, used for
training, and the perturbation model used during testing. In particular, we
add or remove an edge with a certain probability yielding
${\bm{S}^{\prime}}=\bm{S}+\bm{M}$, where $\bm{M}\in\\{-1,0,1\\}^{N\times N}$.
Note that $\bm{M}[i,j]$ can be equal to $1$ and $-1$ only if $\bm{S}[i,j]$ is
equal to $0$ and $1$ respectively. Then we relabel each node by permuting the
rows and columns of the adjacency matrix yielding
$\hat{\bm{S}}=\bm{P}\left(\bm{S}+\bm{M}\right)\bm{P}^{T}$.

Figure 4: The proposed data augmentation process. The first step is to remove
existing edges and/or add new ones, while the second step reorders the nodes
by permuting the rows and columns of the graph adjacency.

##  Appendix E Implementation Details

In this section we discuss the implementation details of our framework. The
code and datasets used in all experiments can be found here:
https://github.com/GraphMatching/Graph-Matching

###  E.1 Assignment Optimization

The proposed T-GAE learns learns a GNN encoder that can produce node
representations for different graphs. Let
$\phi\left({\bm{X}};{\bm{S}},\mathcal{H}\right)$ represent the embeddings of
the nodes corresponding to the graph with adjacency $\bm{S}$ and
$\phi\left(\hat{\bm{X}};\hat{\bm{S}},\mathcal{H}\right)$ represent the
embeddings of the nodes corresponding to the graph with adjacency
$\hat{\bm{S}}$. Then network alignment boils down to solving the following
optimization problem:

$\min_{\bm{P}\in\mathcal{P}}~{}\left\lVert~{}\phi\left(\bm{X};{\bm{S}},\mathcal{H}\right)-\bm{P}\phi\left(\hat{\bm{X}};\hat{\bm{S}},\mathcal{H}\right)~{}\right\rVert_{F}^{2}.$
(30)

The problem in (30) can be optimally solved in $\mathcal{O}\left(N^{3}\right)$
flops by the Hungarian algorithm (Kuhn, 1955a). To avoid this computational
burden we employ the greedy Hungarian approach that has computational
complexity $\mathcal{O}\left(N^{2}\right)$ and usually works well in practice.

The greedy Hungarian approach is described in Algorithm 1. For each row of
$\phi\left({\bm{X}};{\bm{S}},\mathcal{H}\right),~{}\phi\left(\hat{\bm{X}};\hat{\bm{S}},\mathcal{H}\right)$,
which corresponds to the node embeddings of the different graphs, we compute
the pairwise Euclidean distance which is stores in the distance matrix
$\bm{D}$. Then, at each iteration, we find the nodes with the smallest
distance and remove the aligned pairs from $\bm{D}$. This process is repeated
until all the nodes are paired up for alignment.

Input: Feature matrices $\bm{X}$, $\hat{\bm{X}}$

Output: Assignment Matrix

$\bm{P}~{}:=\bm{0}_{N\times N}$

// Initialize permutation matrix

$\bm{D}~{}:=$ PairwiseDistance $\left(\bm{X},\hat{\bm{X}}\right)$

// pairwise Euclidean distance

$\text{rows}:=$ 0,1,…,$N$-1

// Corresponds to $\bm{X}$

$\text{cols}:=$ 0,1,…,$N$-1

// Corresponds to $\hat{\bm{X}}$

/* Iterate to assign node pairs with minimum Euclidean distance */

1 for  _$n$ =1 to $N$_ do

2 $i,~{}j:=\text{argmin}~{}(\bm{D})$

3 $r~{}:=\text{rows}~{}[i]$

4 $c~{}:=\text{cols}~{}[j]$

5 $\bm{P}_{rc}:=1$

6 Remove $r$ from rows

7 Remove $c$ from cols

8 Remove the $i$-th row from $\bm{D}$

9 Remove the $j$-th column from $\bm{D}$

10

11return $\bm{P}$

Algorithm 1 Greedy Hungarian Algorithm

###  E.2 Datasets

The descriptions of the real-world datasets used in our experiments are
presented below:

  * •

Celegans (Kunegis, 2013): The vertices represent proteins and the edges their
protein-protein interactions.

  * •

Arenas Email (Leskovec & Krevl, 2014): The email communication network at the
University Rovira i Virgili in Tarragona in the south of Catalonia in Spain.
Nodes are users and each edge represents that at least one email was sent.

  * •

Douban (Zhang & Tong, 2016): Contains user-user relationship on the Chinese
movie review platform. Each edge implies that two users are contacts or
friends.

  * •

Cora (Sen et al., 2008): The dataset consists of 2708 scientific publications,
with edges representing citation relationships between them. Cora has been one
of the major benchmark datasets in many graph mining tasks.

  * •

Dblp (Pan et al., 2016): A citation network dataset that is extracted from
DBLP, Association for Computing Machinery (ACM), Microsoft Academic Graph
(MAG), and other sources. It is considered a benchmark in multiple tasks.

  * •

Coauthor_CS (Shchur et al., 2018): The coauthorship graph is generated from
MAG. Nodes are the authors and they are connected with an edge if they
coauthored at least one paper.

  * •

ACMDBLP (Zhang & Tong, 2019): The citation networks that share some common
nodes. The task is to identify the publications that appear in both networks.

  * •

Douban OnlineOffline (Zhang & Tong, 2016): The two social networks contained
in this dataset represents the online and offline events of the Douban social
network. The task is to identify users that participate in both online and
offline events.

###  E.3 Baselines

####  E.3.1 Graph Neural Network(GNN) based methods

  * •

WAlign (Gao et al., 2021b) fits a GNN to each of the input graphs, trains the
model by reconstructing the given inputs and minimizing an approximation of
Wasserstein distance between the node embeddings. We use the author’s
implementation from https://github.com/gaoji7777/walign.git. To have a fair
comparision with the node embedding models, all GNN methods are set to have
the hidden dimension equal to 4 in the graph matching experiments. In sub
graph matching, the hidden dimension of GNNS are fine-tuned from 4 to 512.
Other parameters are the same as the author suggested.

####  E.3.2 Graph/Node embedding techniques

  * •

NetSimile (Berlingerio et al., 2013) uses the structural features described
earlier to match the nodes of the graphs. Since the NetSimile features are
used as input to the T-GAE, they provide a measure to assess the benefit of
using T-GAE for node embedding. It proposed 7 egonet-based features, to
measure network similarity. We process these features by Algorithm 1 to
perform network alignment. The 7-dimensional Netsimile features are:

    * –

$d_{i}$ = degree of node i

    * –

$c_{i}$ = number of triangles connected to node i over the number of connected
triples centered on node i

    * –

$\bar{d}_{N_{i}}$ = $\frac{1}{d_{i}}\sum_{j\in N_{i}}{d_{j}}$, average number
of two-hop neighbors

    * –

$\bar{c}_{N_{i}}$ = $\frac{1}{d_{i}}\sum_{j\in N_{i}}{c_{j}}$, average
clustering coefficient

    * –

Number of edges in node i’s egonet

    * –

Number of outgoing edges from node i’s egonet

    * –

Number of neighbors in node i’s egonet

The implementation is based on netrd library where we use the feature
extraction function. The source code can be found at
https://netrd.readthedocs.io/en/latest/_modules/netrd/distance/netsimile.html

  * •

Spectral (Umeyama, 1988) It solves the following optimization problem:

$\min_{\bm{P}\in\mathcal{P}}~{}\left\lVert~{}\left|\bm{V}\right|-\bm{P}\left|\hat{\bm{V}}\right|~{}\right\rVert_{F}^{2},$
(31)

where $\bm{V},~{}\hat{\bm{V}}$ are the eigenvectors corresponding to the
adjacencies of the graphs that we want to match. In our initial experiments,
we observed that a subset of the eigenvectors yields improved results compared
to the whole set. We tried $1-10$ top eigenvectors and concluded that $4$
eigenvectors are those that yield the best results on average. Thus we solve
the above problem with the top-4 eigenvectors.

  * •

DeepWalk (Perozzi et al., 2014): A node embedding approach, simulates random
walks on the graph and apply skip-gram on the walks to generate node
embedding. We use the implementation from Karateclub
https://github.com/benedekrozemberczki/karateclub/blob/master/karateclub/node_embedding/neighbourhood/deepwalk.pyThe
algorithm is implemented with the default parameters as suggested by this
repository, the number of random walks is 10 with each walk of length 80. The
dimensionality of embedding is set to be 128. We run the algorithm with 1
epoch and set the learning rate to be 0.05.

  * •

Node2Vec (Grover & Leskovec, 2016b): An improve version of DeepWalk, it has
weights on the randomly generated random walks, to make the neighborhood
preserving objective more flexible. We use the implementation from
https://github.com/benedekrozemberczki/karateclub/blob/master/karateclub/node_embedding/neighbourhood/node2vec.py.
The default parameters are used. We simulate 10 random walks on the graph with
length 80. p and q are both equal to 1. Dimensionality of embeddings is set to
be 4 and we run 1 epoch with learning rate 0.05.

  * •

GraphWave (Donnat et al., 2018): The structure information of the graphs is
captured by simulating heat diffusion process on them. We use the
implementation from (Donnat et al.,
2018):https://github.com/benedekrozemberczki/karateclub/blob/master/karateclub/node_embedding/structural/graphwave.py
with the default parameters: number of evaluation points is 200, step size is
0.1, heat coefficient is 1.0 and Chebyshev polynomial order is set to be 100.
Note that this implementation does not work on graphs with more than 10,000
nodes, so we exclude this model on the DBLP and Coauthor_CS dataset.

####  E.3.3 Optimization based graph matching algorithms

  * •

FINAL (Zhang & Tong, 2016) is an optimization approach, following an alignment
consistency principle, and tries to match nodes with similar topology. In the
case of graphs without attributes FINAL is equivalent to the popular Isorank
(Singh et al., 2008) algorithm, whereas using NetSimile as an input to FINAL
resulted in inferior performance and was therefore omitted. We use the code in
https://github.com/sizhang92/FINAL-KDD16 with $\bm{H}$ being the degree
similarity matrix, $\alpha=0.8,~{}\text{maxiter}=30,~{}\text{tol}=1e-4$ as
suggested in the repository.

Note that FINAL only outputs the exact matching, and the Hit@1 performance in
the sub-graph matching experiment is weak, so it’s only included in the graph
matching experiments. REGAL (Heimann et al., 2018) demonstrated very weak
matching accuracy and is not included in the tables. For similar reasons,
Node2Vec and DeepWalk are only used in sub-graph matching.

###  E.4 T-GAE Parameters

We implement our proposed Transferable graph autoencoder (T-GAE) framework,
following Equations (8), (9), (10), for the tasks described later in the
section. We use 1 MLP and 6 GNN layers, followed by another MLP to design the
Encoder $\phi\left(\bm{X},{\bm{S}};\mathcal{H}\right)$ of T-GAE, as
illustrated in Figure 1. For the GNN layers we use 3 different models: i)
graph convolutional network (GCN) (Kipf & Welling, 2017), which is a message-
passing architecture, described in Equation (4) with $f$ being the mean
function, and $g$ being the linear function, ii) graph isomorphism network
(GIN) (Xu et al., 2019), which is also described by (4) with $f$ being the
summation function, and $g$ being the MLP, and iii) graph neural network with
k-hop neighborhood convolutions (GNNc), as described by Equation (11). For
graph matching experiments, in order to run experiments on large scale
networks, we use an output dimension of 4. On sub-graph matching tasks, we
fine tune this parameter from 4 to 512 and used the one that gives the best
performance.

To select the hyperparameters of our model we utilize a validation graph (JAZZ
(Rossi & Ahmed, 2015)), which is not included in our comparisons to ensure
unbiased comparisons. Note that all parameters of T-GAE are fixed for all
datasets that are reported. The model is not fine-tuned on every network that
is used in testing.

The parameters of T-GAE include:

  * •

We train our model Adam optimizer for 100 epochs and initial learning rate
equal to $0.001$ for graph matching experiment. To have a fair comparision
with WAlign (Gao et al., 2021b), we train 20 epochs for the subgraph matching
tasks.

  * •

The hidden dimension of the GNN modules is equal to $6$ and that of the output
layer (encoder) is equal to 4 for graph matching experiments. For subgraph
matching, the hidden dimensions are set to be 512, the same to the optimal
value for WAlign (Gao et al., 2021b).

  * •

The activation function for each GNN layer is ReLU.

  * •

We use an 1-layer decoder followed by the sigmoid function.

  * •

To conduct the experiments in Sections 5.2.2, G.1 we augment the dataset with
$25$ perturbed graphs for each perturbation level.

##  Appendix F Efficiency and Run-time Comparison

We analyze the efficiency of the proposed graph matching framework by
comparing its running time with the competing algorithms. The GNN-based
methods achieve at most $\times$50 less running time on the subgraph matching
tasks. The proposed training objective (10) scales well from networks with
1,000 nodes (Zhang & Tong, 2016) to denser networks with $\times$10 nodes,
with minor running time increase, compared to other node embedding techniques.

We also noticed that compared to the other GNN based framework WAlign Gao et
al. (2021b), T-GAE takes more time to train on the larger scale networks. This
is because the deep GNN is trained by the structure of the network. The
training takes more time as the netowrk scales up and the number of nodes and
edges grow dramatically, whereas the training labels for WAlign come from the
input feature, which does not scale up with as the size of the training graphs
increase. This could be one of the limitations to the proposed training
paradigm and that is why we leverage transfer learning to efficiently match
large scale graphs, as illustrated in Table3.

Figure 5: Runtime comparison for the competing algorithms on the sub-graph
matching datasets. All GNN-based methods have 8 layers with 512 as hidden
dimensions and are trained with 20 epochs.

##  Appendix G Uniform Perturbation Model Suppltmentary Results

###  G.1 Specific Perturbed Training

The last question that we will try to answer with our experiments about
Uniform Perturbation model is whether training and testing on the same graph
compares to training with a family of graphs or a combination of a family and
perturbed graphs, that was examined in the previous subsection. In this
subsection we test the performance of T-GAE on Celegans, Arenas, Douban, and
Cora, on 4 different settings: i) when training on each graph separately
according to (8); ii) when training on all 4 graphs according to (9); iii)
when training on the perturbations of only one graph according to (9), but
$\mathbb{S}$ being defined over a family of graph perturbations; iv when
training on all 4 graphs plus perturbed versions of them, according to (10).
The results for the different levels of perturbations are presented in Table
2.

Table 2: Performance of T-GAE when trained on a family of graphs or on a specific graph on uniform perturbation model Perturbation |  Celegans |  Arenas |  Douban |  Cora
---|---|---|---|---
0% perturbation
T-GAE specific (8) |  ${89.3\pm 1.4}$ |  ${88.3\pm 0.4}$ |  ${90.2\pm 0.5}$ |  ${87.5\pm 0.4}$
T-GAE (9) |  ${89.5\pm 1.3}$ |  ${88.4\pm 0.5}$ |  ${90.1\pm 0.4}$ |  ${87.4\pm 0.4}$
T-GAE specific with pert. |  $\mathbf{90.4\pm 0.8}$ |  ${88.5\pm 0.4}$ |  $\mathbf{90.2\pm 0.3}$ |  $\mathbf{{87.6\pm 0.5}}$
T-GAE with pert. (10) |  ${89.7\pm 1.5}$ |  $\mathbf{88.6\pm 0.6}$ |  ${90.1\pm 0.4}$ |  ${87.4\pm 0.5}$
1% perturbation
T-GAE specific (8) |  ${81.3\pm 1.7}$ |  ${85.4\pm 0.5}$ |  ${85.1\pm 1.1}$ |  ${83.1\pm 1.0}$
T-GAE (9) |  $\mathbf{84.1\pm 1.1}$ |  ${84.8\pm 0.6}$ |  ${84.9\pm 0.6}$ |  ${82.9\pm 0.5}$
T-GAE specific with pert. |  ${83.1\pm 1.4}$ |  ${85.3\pm 0.9}$ |  $\mathbf{85.3\pm 0.7}$ |  $\mathbf{83.5\pm 0.6}$
T-GAE with pert. (10) |  ${83.4\pm 1.6}$ |  $\mathbf{85.6\pm 0.5}$ |  ${85.2\pm 0.6}$ |  ${83.2\pm 0.9}$
5% perturbation
T-GAE specific (8) |  ${48.9\pm 9.5}$ |  ${61.5\pm 5.4}$ |  ${58.0\pm 3.9}$ |  ${58.8\pm 2.7}$
T-GAE (9) |  ${50.8\pm 3.3}$ |  ${47.1\pm 5.6}$ |  ${57.9\pm 6.1}$ |  ${58.2\pm 2.0}$
T-GAE specific with pert. |  $\mathbf{53.5\pm 11.9}$ |  ${54.3\pm 6.4}$ |  ${57.3\pm 4.6}$ |  $\mathbf{58.9\pm 2.4}$
T-GAE with pert. (10) |  ${52.3\pm 5.4}$ |  $\mathbf{62.6\pm 2.2}$ |  $\mathbf{58.5\pm 5.0}$ |  ${57.4\pm 2.7}$

Table 2 shows when testing on low perturbation or no perturbations, all the
models work statistically the same. The only exception is in the Celegans
dataset where training on a family of graphs seems to improve the matching
performance by $2.8\%$ compared to training just on a single graph. For $5\%$
perturbation level, on the other hand, either T-GAE specific with pert. or
T-GAE with pert. yield the best results, which implies that a self-supervised
approach with perturbations benefits performance and robustness. We also
observe that T-GAE with pert., i.e., training according to (10) is in general
the most consistent approach.

##  Appendix H Degree Perturbation Model Results

Degree Model: In this model we only remove edges. Edges with higher degrees
are more likely to be removed to preserve the structure of the graph.
Specifically, the probability of removing edge $(i,j)$ is set to
$\frac{s_{ij}d_{i}d_{j}}{\sum_{ij}{s_{ij}d_{i}d_{j}}}$, where $d_{i}$ is the
degree of node $v_{i}$ and $s_{i,j}$ is the $(i,j)$ element of the graph
adjacency.

###  H.1 Transferability Analysis

We test the performance of T-GAE for large-scale network alignment on the
degree perturbation model, as described in Section 5.2. We adopt the same
setting as in Section 5.3 to train the T-GAE according to (9) on small-size
networks, i.e., Celegans, Arena, Douban, and Cora, and conduct transfer
learning experiments on the larger graphs, i.e., Dblp, and Coauthor CS. The
trained T-GAE is used to generate node embedding for the graphs, and 1
computes the assignment matrix. The results presented in Table 3 are based on
the average and standard deviation of the matching accuracy over 10 randomly
generated perturbed samples.

Table 3: Graph Matching Accuracy for uniform perturbation model |  Algorithm |  Celegans |  Arenas |  Douban |  Cora |  Dblp |  Coauthor CS
---|---|---|---|---|---|---|---
$0\%$ perturbation |  Spectral |  ${66.5\pm 28.4}$ |  ${87.8\pm 0.5}$ |  ${35.7\pm 35.5}$ |  ${84.7\pm 0.5}$ |  ${84.6\pm 0.1}$ |  $\mathbf{97.6\pm 0.1}$
NetSimile |  ${71.8\pm 1.0}$ |  ${84.7\pm 0.5}$ |  ${46.9\pm 0.5}$ |  ${73.0\pm 0.7}$ |  ${63.7\pm 0.2}$ |  ${90.1\pm 0.1}$
FINAL |  $\mathbf{92.7\pm 1.9}$ |  ${88.2\pm 0.5}$ |  ${90.0\pm 0.4}$ |  ${87.1\pm 0.5}$ |  $\mathbf{85.6\pm 0.1}$ |  $\mathbf{97.6\pm 0.1}$
T-GAE (GNNc) |  ${89.3\pm 1.2}$ |  ${88.1\pm 0.4}$ |  $\mathbf{90.2\pm 0.4}$ |  ${87.5\pm 0.5}$ |  $\mathbf{85.6\pm 0.1}$ |  $\mathbf{97.6\pm 0.1}$
T-GAE (GCN) |  ${89.7\pm 1.4}$ |  ${88.2\pm 0.5}$ |  ${90.1\pm 0.3}$ |  ${87.4\pm 0.4}$ |  $\mathbf{85.6\pm 0.1}$ |  $\mathbf{97.6\pm 0.1}$
T-GAE (GIN) |  ${89.6\pm 1.0}$ |  $\mathbf{88.2\pm 0.4}$ |  ${90.1\pm 0.3}$ |  $\mathbf{87.6\pm 0.4}$ |  ${85.4\pm 0.1}$ |  ${97.5\pm 0.1}$
$1\%$ perturbation |  Spectral |  ${21.8\pm 16.9}$ |  ${62.9\pm 21.8}$ |  ${9.8\pm 13.5}$ |  ${25.3\pm 13.4}$ |  ${3.4\pm 0.8}$ |  ${8.6\pm 4.6}$
NetSimile |  ${63.1\pm 1.4}$ |  ${81.1\pm 0.7}$ |  ${37.6\pm 0.6}$ |  ${64.4\pm 1.2}$ |  ${52.2\pm 0.5}$ |  ${76.8\pm 0.6}$
FINAL |  ${62.5\pm 4.1}$ |  ${55.6\pm 2.0}$ |  ${35.0\pm 1.1}$ |  ${32.0\pm 2.0}$ |  ${24.5\pm 0.6}$ |  ${19.1\pm 0.5}$
T-GAE (GNNc) |  ${68.0\pm 8.7}$ |  ${82.0\pm 3.4}$ |  ${80.3\pm 2.1}$ |  ${78.6\pm 1.9}$ |  ${69.8\pm 1.2}$ |  ${72.3\pm 2.4}$
T-GAE (GCN) |  $\mathbf{68.9\pm 5.2}$ |  ${83.5\pm 1.3}$ |  ${82.2\pm 1.4}$ |  ${78.5\pm 1.3}$ |  ${62.3\pm 1.6}$ |  ${83.6\pm 1.0}$
T-GAE (GIN) |  ${49.6\pm 16.2}$ |  $\mathbf{86.3\pm 0.7}$ |  $\mathbf{83.7\pm 2.2}$ |  $\mathbf{81.0\pm 2.5}$ |  $\mathbf{75.1\pm 0.6}$ |  $\mathbf{88.3\pm 0.4}$
$5\%$ perturbation |  Spectral |  ${14.4\pm 3.9}$ |  ${28.8\pm 9.4}$ |  ${1.4\pm 0.7}$ |  ${3.5\pm 1.9}$ |  ${0.3\pm 0.1}$ |  ${0.5\pm 0.2}$
NetSimile |  ${12.6\pm 1.4}$ |  ${22.4\pm 1.0}$ |  ${10.3\pm 0.4}$ |  ${32.0\pm 0.7}$ |  ${18.4\pm 0.1}$ |  ${20.2\pm 0.3}$
FINAL |  $\mathbf{24.3\pm 2.3}$ |  ${20.5\pm 1.6}$ |  ${7.5\pm 0.4}$ |  ${8,6\pm 0.7}$ |  ${4.7\pm 0.2}$ |  ${3.5\pm 1.3}$
T-GAE (GNNc) |  ${14.0\pm 2.9}$ |  ${28.9\pm 2.8}$ |  ${24.2\pm 1.9}$ |  ${38.5\pm 2.3}$ |  ${24.6\pm 0.7}$ |  $\pagecolor{red!50}{10.8\pm 0.4}$
T-GAE (GCN) |  ${9.9\pm 2.6}$ |  ${28.3\pm 1.3}$ |  $\mathbf{30.7\pm 1.4}$ |  ${47.0\pm 1.7}$ |  ${22.2\pm 0.7}$ |  $\pagecolor{red!50}{13.6\pm 0.5}$
T-GAE (GIN) |  ${13.0\pm 1.8}$ |  $\mathbf{42.9\pm 2.1}$ |  ${28.9\pm 1.4}$ |  $\mathbf{52.4\pm 3.3}$ |  $\mathbf{35.7\pm 0.8}$ |  $\pagecolor{red!50}\mathbf{23.6\pm 0.6}$

When testing on 0 perturbation level most algorithms are able to discover the
node correspondences, as in the uniform perturbation model. The benefit of
processing the NetSimile embeddings with GNNs is still significant in this
perturbation model as we observe up to $53\%$ performance increase. When
testing on perturbed graphs, our proposed T-GAE consistently outperforms all
the competing baselines, while being robust and efficient when performing
network alignment under different perturbation models. Finally, on large-scale
networks, T-GAE is able to achieve very high levels of matching accuracy for
both Dblp and Coauthor CS, for $p=0\%,~{}1\%$.

###  H.2 Perturbed Training

We train the T-GAE with a family of original graphs and test to match
perturbed versions of a larger family of graphs. We notice that although being
more robust to perturbations than the baseline methods, the matching accuracy
of T-GAE dropped as the perturbation level of testing data increased,
especially on the degree perturbation model. To tackle this problem we follow
a self-supervised learning approach and train T-GAE with a family of real
graphs and perturbations of them. We train according to (10), which encourages
the model to produce similar node embeddings for the original graphs and the
perturbed versions of them. We augment the dataset as illustrated in 4, adding
and deleting edges, according to the degree Model perturbation probability
presented in Section 5.2. Training and testing are conducted on different
randomly generated perturbed samples. Table 4 reports the testing results of
T-GAE when trained on the best perturbation levels.

Table 4: Performance Comparison of T-GAE when trained with/without perturbation on degree perturbation model Algorithm |  Celegans |  Arenas |  Douban |  Cora |  Dblp |  Coauthor CS
---|---|---|---|---|---|---
0% perturbation
T-GAE |  ${89.7\pm 1.4}$ |  ${88.2\pm 0.4}$ |  $\mathbf{90.2\pm 0.4}$ |  ${87.6\pm 0.4}$ |  ${85.6\pm 0.1}$ |  ${97.6\pm 0.1}$
T-GAE with pert. |  $\mathbf{90.4\pm 1.2}$ |  $\mathbf{88.4\pm 0.4}$ |  ${90.1\pm 0.3}$ |  $\mathbf{87.6\pm 0.4}$ |  $\mathbf{85.7\pm 0.1}$ |  $\mathbf{97.6\pm 0.0}$
1% perturbation
T-GAE |  $\mathbf{68.9\pm 5.2}$ |  ${86.3\pm 0.7}$ |  ${83.7\pm 2.2}$ |  ${81.0\pm 2.5}$ |  $\mathbf{75.1\pm 0.6}$ |  ${88.3\pm 0.4}$
T-GAE with pert. |  ${67.2\pm 10.2}$ |  $\mathbf{87.3\pm 1.0}$ |  $\mathbf{85.3\pm 1.0}$ |  $\mathbf{82.7\pm 0.8}$ |  ${74.1\pm 0.7}$ |  $\mathbf{89.7\pm 0.7}$
5% perturbation
T-GAE |  ${14.0\pm 2.9}$ |  ${42.9\pm 2.1}$ |  ${30.7\pm 1.4}$ |  ${52.4\pm 3.3}$ |  ${35.7\pm 0.8}$ |  ${23.6\pm 0.6}$
T-GAE with pert. |  $\mathbf{17.7\pm 2.0}$ |  $\mathbf{55.7\pm 3.2}$ |  $\mathbf{47.1\pm 2.2}$ |  $\mathbf{57.6\pm 1.1}$ |  $\mathbf{39.4\pm 0.7}$ |  $\mathbf{30.2\pm 0.7}$

The results show that introducing training perturbations significantly
improves the graph matching accuracy in high testing perturbation levels. When
testing on low perturbation levels, however, the use of perturbations to train
the T-GAE does not lead to significant changes in this perturbation model. At
5% testing perturbation, training with perturbations offers a 16.4% accuracy
increase in the Douban dataset and 12.8% accuracy improvement in the Arenas
Dataset, whereas at 1% testing perturbation, the increase is 1% and 1.6%
respectively. And at 0 testing perturbation, the performance on these two
datasets is similar.

###  H.3 Specific Perturbed Training

The last experiment we conduct on the degree perturbation model is to compare
the performance of T-GAE on Celegans, Arenas, Douban, and Cora, on 4 different
settings: i) training is performed on a specific graph according to (8); ii)
training on the family of all 4 graphs based on (9); iii) training on the
perturbations of one specific graph according to (9), with $\mathbb{S}$ being
defined over a family of graph perturbations; iv) training on the
perturbations of all 4 graphs according to (10). The results for different
levels of perturbations are presented in Table 2.

Table 5: Performance of T-GAE when trained on a family of graphs or on a specific graph on degree perturbation model Perturbation |  Celegans |  Arenas |  Douban |  Cora
---|---|---|---|---
0% perturbation
T-GAE specific (8) |  ${88.9\pm 1.1}$ |  ${88.4\pm 0.5}$ |  ${90.0\pm 0.3}$ |  ${87.5\pm 0.4}$
T-GAE (9) |  ${89.7\pm 1.4}$ |  ${88.2\pm 0.4}$ |  $\mathbf{90.2\pm 0.4}$ |  $\mathbf{87.6\pm 0.4}$
T-GAE specific with pert. |  ${89.4\pm 1.0}$ |  ${88.3\pm 0.4}$ |  ${90.1\pm 0.4}$ |  ${{87.5\pm 0.6}}$
T-GAE with pert. (10) |  $\mathbf{90.4\pm 1.2}$ |  $\mathbf{88.4\pm 0.4}$ |  ${90.1\pm 0.3}$ |  $\mathbf{87.6\pm 0.4}$
1% perturbation
T-GAE specific (8) |  $\mathbf{74.8\pm 2.8}$ |  ${85.8\pm 1.5}$ |  ${85.1\pm 0.7}$ |  ${82.3\pm 1.3}$
T-GAE (9) |  ${68.9\pm 5.2}$ |  ${86.3\pm 0.7}$ |  ${83.7\pm 2.2}$ |  ${81.0\pm 2.5}$
T-GAE specific with pert. |  ${70.7\pm 4.6}$ |  ${87.0\pm 0.7}$ |  ${84.1\pm 0.8}$ |  ${81.6\pm 1.5}$
T-GAE with pert. (10) |  ${67.2\pm 10.2}$ |  $\mathbf{87.3\pm 1.0}$ |  $\mathbf{85.3\pm 1.0}$ |  $\mathbf{82.7\pm 0.8}$
5% perturbation
T-GAE specific (8) |  $\mathbf{30.6\pm 5.0}$ |  ${44.2\pm 1.2}$ |  ${41.3\pm 1.6}$ |  ${56.0\pm 1.4}$
T-GAE (9) |  ${14.0\pm 2.9}$ |  ${42.9\pm 2.1}$ |  ${30.7\pm 1.4}$ |  ${52.4\pm 3.3}$
T-GAE specific with pert. |  ${27.3\pm 4.8}$ |  ${46.4\pm 3.8}$ |  ${42.0\pm 2.1}$ |  ${56.3\pm 1.8}$
T-GAE with pert. (10) |  ${17.7\pm 2.0}$ |  $\mathbf{55.7\pm 3.2}$ |  $\mathbf{47.1\pm 2.2}$ |  $\mathbf{57.6\pm 1.1}$

From Table 5 we observe that all the models work statistically the same when
testing on zero perturbation. When testing on low or high perturbation levels,
training with perturbation achieves the best accuracy in most datasets. The
Celegans dataset is an exception and achieves a better matching accuracy by
$5.9\%$ and $3.3\%$ when trained on a specific graph, respectively, compared
to training on a family of graphs or perturbed adjacencies. Overall, we see
that training with perturbations helps improve the matching accuracy and the
robustness of the proposed method. T-GAE with pert. or T-GAE specific with
pert.. In other words, training according to (10) is in general produces the
most consistent and accurate results compared to the settings where we train
the model on the original graph without perturbation.

From the additional perturbation model, we conclude that our proposed T-GAE
framework is able to transfer and perform network alignment on large and
small-size graphs and is robust to achieve consistent accuracy under different
perturbation models and perturbation levels.