# On seeded subgraph-to-subgraph matching:
The ssSGM Algorithm and matchability information theory

Lingyao Meng  Johns Hopkins University, Department of Applied Mathematics and
Statistics  Mengqi Lou  Georgia Institute of Technology, School of Industrial
and Systems Engineering  Jianyu Lin  Johns Hopkins University, Department of
Applied Mathematics and Statistics  Vince Lyzinski  University of Maryland,
College Park, Department of Mathematics  Donniell E. Fishkind  Johns Hopkins
University, Department of Applied Mathematics and Statistics

###### Abstract

The subgraph-subgraph matching problem is, given a pair of graphs and a
positive integer $K$, to find $K$ vertices in the first graph, $K$ vertices in
the second graph, and a bijection between them, so as to minimize the number
of adjacency disagreements across the bijection; it is “seeded” if some of
this bijection is fixed. The problem is intractable, and we present the ssSGM
algorithm, which uses Frank-Wolfe methodology to efficiently find an
approximate solution. Then, in the context of a generalized correlated random
Bernoulli graph model, in which the pair of graphs naturally have a core of
$K$ matched pairs of vertices, we provide and prove mild conditions for the
subgraph-subgraph matching problem solution to almost always be the correct
$K$ matched pairs of vertices.

MSC2020 subject classifications: 05C60 05C80 90C35

Keywords: graph matching, Frank-Wolfe method, matchability, seeded graph
matching

##  1 Background and overview

Given a pair of graphs, the graph matching problem seeks to discover a
correspondence between the vertex sets of the graphs that minimizes a measure
of graph dissimilarity; see, for example, [5, 17, 12] for surveys of the
recent graph matching literature. This problem of optimally aligning a pair of
graphs is practically useful, theoretically challenging, and computationally
difficult. Practically, graph matching methods have been successfully used for
aligning protein interaction networks [50, 37], uncovering bilateral brain
structure [40], image alignment in computer vision [54, 19, 43], and de-
anonymizing social networks [4, 39], to name a few applications.
Theoretically, there is a growing literature devoted to uncovering sharp
information-theoretic thresholds for graph matchability (i.e., when can graph
matching algorithms uncover a latent correspondence across the vertex sets of
the graph pair in the presence of noise); see, for example, [6, 32, 30, 7, 8,
47, 11, 16, 14]). Computationally, when the graphs are allowed to be weighted,
directed and loopy, the graph matching problem is equivalent to the NP-hard
quadratic assignment problem. Even the simpler graph isomorphism
problem—determining if two graphs are isomorphic—is NP-intermediate (see [1]
for the remarkable proof of the quasipolynomial time complexity of the
problem). This combination of utility and complexity has led to a huge number
of approximate graph matching algorithms in the literature; see, for example,
[46, 26, 51, 22, 24, 29, 28, 53, 52].

One particular branch of algorithms (see, for example, [46, 15, 52, 41])
proceeds by relaxing the combinatorial graph matching problem to a continuous
optimization problem via relaxing the permutation matrix constraint to the set
of doubly-stochastic matrices (e.g. see Section 3.2). This constrained,
continuous optimization problem can then be approximately solved via the
Frank-Wolfe method [18] or a fast approximation thereof (see for example [10,
52, 41]), and the relaxed solution is projected to the nearest feasible point
in the original combinatorial problem. These Frank-Wolfe-based algorithms
empirically provide excellent performance, especially in the presence of
seeded vertices (ie. when some of a natural correspondence is known a-priori).

In the present work, we consider the problem of finding the best-matched pair
of subgraphs (of a fixed order) in a pair of graphs, simultaneously optimally
aligning these subgraphs, also incorporating any seeds; this seeded subgraph-
subgraph matching problem is described in Section 2.1. Our contributions are
two-fold: First, in Section 3 we develop the ssSGM algorithm to efficiently,
approximately solve this problem; it incorporates several significant
modifications to the Frank-Wolfe methodology of the SGM Algorithm [15] for
seeded graph matching. Sections 4, 5 illustrate ssSGM with simulations and
real-data experiments. Our second contribution is an information-theoretic
result in Section 6; if there is a latent alignment of a pair of subgraphs
across the pair of graphs, we provide and prove mild conditions where the
exact solution of the subgraph-subgraph matching problem recovers the latent
alignment. Discussion follows in Section 7.

##  2 Graph Matching and subgraph-subgraph matching

All graphs in this paper are simple (i.e. no orientation to edges, no loops,
no multi-edges).

Suppose $G$ and $H$ are graphs with respective vertex sets $V$ and $W$ with
the same cardinality, say $n:=|V|=|W|$. For any bijection $\phi:V\rightarrow
W$, a disagreeing pair is any pair of vertices $v,v^{\prime}\in V$ such that
$v\sim v^{\prime}$ and $\phi(v)\not\sim\phi(v^{\prime})$, or $v\not\sim
v^{\prime}$ and $\phi(v)\sim\phi(v^{\prime})$. The graph matching problem is
to find a bijection $\phi:V\rightarrow W$ with minimum number of disagreeing
pairs.

Suppose that $\delta^{(1)}$, $\delta^{(2)}$, and $\delta^{(3)}$ are any real
numbers such that $\delta^{(1)}\neq\delta^{(2)}$. We can equivalently express
the graph matching problem as follows. Say the vertex sets are
$V=\\{v_{1},v_{2},\ldots$ $,v_{n}\\}$ and $W=\\{w_{1},w_{2},\ldots,w_{n}\\}$,
and let $A$ and $B$ be $n\times n$ matrices with, for all
$i,j\in\\{1,2,3,\ldots,n\\}$ such that $i\neq j$, $A_{ij}$ is defined as
$\delta^{(1)}$ or $\delta^{(2)}$ according as $v_{i}\sim v_{j}$ or
$v_{i}\not\sim v_{j}$, and $B_{ij}$ is defined as $\delta^{(1)}$ or
$\delta^{(2)}$ according as $w_{i}\sim w_{j}$ or $w_{i}\not\sim w_{j}$, and
define $A_{ii}=B_{ii}=\delta^{(3)}$. Let $\varPi_{n}$ denote the set of
$n\times n$ permutation matrices. The graph matching problem can be expressed
as $\min\|A-XBX^{T}\|_{F}^{2}$ s.t. $X\in\varPi_{n}$. The usual choice of
$\delta^{(1)}$, $\delta^{(2)}$, and $\delta^{(3)}$ are, respectively, $1$,
$0$, and $0$, in which case $A$ and $B$ are the standard $\\{0,1\\}$-adjacency
matrices of $G$ and $H$, respectively. This will turn out to be an unhelpful
choice for us here, and we will need to adopt an alternative, as described
next in Section 2.1. (Specifically, we will take $\delta^{(1)}$,
$\delta^{(2)}$, and $\delta^{(3)}$ as, respectively, $1$, $-1$, and $-1$.)

The implicit story is that there is a natural correspondence between the two
vertex sets that we wish to discover. For example, if the two graphs are
modeling two different social media platforms with the same users in each
platform (perhaps the users identify themselves by their real names in one
platform and a different identifier in the other platform) and, for any two
users, adjacency in a platform means the respective users communicated in that
platform, then the graph matching problem would attempt to cross-identify the
users between platforms.

The seeded graph matching problem refers to the setting where the natural
correspondence between the vertex sets is partially known a priori, so we
restrict the optimization to bijections that agree with the known
correspondences [32]. In the social media story above, this would happen if
some users identify themselves by their real name in both platforms. (See [13]
for a variant, known as soft-seeding, where the a priori known alignment is
soft-coded into the search space and is allowed to be updated; this would be
useful if the a priori known correspondences were not completely certain. We
will not be working with soft-seeding here.) The practical utility of even a
few seeds on matching performance (see [15]) has led to seeded graph matching
becoming a popular variant of the classical framework; see, for example, [36,
2, 42, 3, 38, 49] for state of the current algorithmic and theoretic seeded
graph matching problem literature.

The focus of our work here is a further generalization of this problem
setting, called the subgraph-subgraph matching problem, which we describe in
detail next in Section 2.1.

###  2.1 The seeded subgraph-subgraph matching problem

In this section, we formally present the seeded subgraph-subgraph matching
problem, which is the main focus of our work here.

Suppose $G$ and $H$ are graphs with respective vertex sets $V$ and $W$, say
$m:=|V|$, $n:=|W|$. Let $K$ be a positive integer such that
$K\leq\min\\{m,n\\}$. For any two subsets $\Omega\subseteq V$ and
$\Lambda\subseteq W$ such that $|\Omega|=|\Lambda|=K$, and any bijection
$\phi:\Omega\rightarrow\Lambda$, a disagreeing pair is any pair of vertices
$v,v^{\prime}\in\Omega$ such that $v\sim v^{\prime}$ and
$\phi(v)\not\sim\phi(v^{\prime})$, or $v\not\sim v^{\prime}$ and
$\phi(v)\sim\phi(v^{\prime})$. The subgraph-subgraph matching problem is to
find subsets $\Omega\subseteq V$ and $\Lambda\subseteq W$ with
$|\Omega|=|\Lambda|=K$, and to find a bijection
$\phi:\Omega\rightarrow\Lambda$, minimizing the number of disagreeing pairs
(optimized over all possible choices of pairs of vertex subsets and also all
bijections between the corresponding vertex subsets).

Analogously to the previous section, the implicit story is that there is a
natural correspondence between a core of $K$ vertices in each graph, and we
want to estimate the core and the correspondence. For example, if the two
graphs are modeling two different social media platforms, where adjacency of
two vertices in a platform means the respective users communicated in that
platform, and if we know that the number of users who are common to both
platforms is $K$ (albeit, each user with different identifiers in the two
platforms), then the subgraph-subgraph matching problem would attempt to find
these $K$ common users and to cross-identify them between platforms.

We can equivalently express the problem as follows. Say the vertices are
$V=\\{v_{1},v_{2},\ldots$ $,v_{m}\\}$ and $W=\\{w_{1},w_{2},\ldots,w_{n}\\}$,
and then let $A\in\\{1,-1\\}^{m\times m}$ and $B\in\\{1,-1\\}^{n\times n}$ be
the respective $\pm 1$-adjacency matrices of $G$ and $H$. That is, for all
indices $i,j$, we have that $A_{ij}$ is $1$ or $-1$ according as $v_{i}\sim
v_{j}$ or $v_{i}\not\sim v_{j}$, and $B_{ij}$ is $1$ or $-1$ according as
$w_{i}\sim w_{j}$ or $w_{i}\not\sim w_{j}$. For any positive integers $c,d,e$
such that $e\leq\min\\{c,d\\}$, let $\varPi_{c,d,e}$ denote the set of
$c\times d$ binary matrices with at most one $1$ per row and at most one $1$
per column, with the total number of $1$’s being $e$; that is,
$\varPi_{c,d,e}:=\\{X\in\\{0,1\\}^{c\times
d}:X\vec{\mathbf{1}}_{d}\leq\vec{\mathbf{1}}_{c},\vec{\mathbf{1}}_{c}^{T}X\leq\vec{\mathbf{1}}_{d}^{T},\vec{\mathbf{1}}_{c}^{T}X\vec{\mathbf{1}}_{d}=e\\}$,
where $\vec{\mathbf{1}}$ denotes a vector of ones with length indexed by its
subscript. The subgraph-subgraph matching problem can be expressed as
$\min\|A-XBX^{T}\|_{F}^{2}$ s.t. $X\in\varPi_{m,n,K}$; indeed, for all
$i=1,2,\ldots,m$ and $j=1,2,\ldots,n$ such that $X_{ij}=1$, if we understand
this to say that $v_{i}\in\Omega$ and $w_{j}\in\Lambda$ and
$\phi(v_{i})=w_{j}$, then the objective function is eight times the number of
disagreeing pairs plus a constant (this constant is $m^{2}-K^{2}$), so we are
basically minimizing the number of disagreeing pairs.

Next, we expand the objective function
$\|A-XBX^{T}\|_{F}^{2}=\|A\|^{2}_{F}-2\textup{trace}A^{T}XBX^{T}+\|XBX^{T}\|^{2}_{F}$;
note that $\|A\|_{F}^{2}$ and $\|XBX^{T}\|_{F}^{2}$ are constants,
respectively equal to $m^{2}$ and $K^{2}$, and note that $A$ is symmetric,
from which we get the following equivalent formulation of the subgraph-
subgraph matching problem:

$\displaystyle\max_{X\in\varPi_{m,n,K}}\textup{trace}AXBX^{T}\ \ .$ (1)

Note that if we had instead used standard $\\{0,1\\}$-adjacency matrices,
rather than $\pm 1$-adjacency matrices, then this expression would not be
equivalent to the subgraph-subgraph matching problem.

In the social media story above, sometimes we will know a-priori a few members
of the core and their correspondence across the media platforms. With this in
mind, the seeded subgraph-subgraph matching problem is where the subgraph-
subgraph matching optimization is done when fixing $s$ vertices of $\Omega$,
$s$ vertices of $\Lambda$, and $\phi$ is fixed in mapping the former fixed
vertices to the latter fixed vertices in some particular manner. Without loss
of generality, the fixed vertices (“seeds”) are $v_{1},v_{2},\ldots,v_{s}$ and
$w_{1},w_{2},\ldots,w_{s}$ and, without loss of generality, for each
$i=1,2,\ldots,s$, we fix $\phi(v_{i})=w_{i}$. Thus we can equivalently
express:

$\displaystyle(\textup{seeded subgraph-subgraph matching problem})\ \
\max_{X\in\varPi_{m-s,n-s,K-s}}\textup{trace}A(I_{s}\oplus X)B(I_{s}\oplus
X)^{T}\ \ .$ (2)

This problem is computationally intractable; indeed, the special cases seeded
graph matching problem and graph matching problem are computationally
intractable, as elaborated in Section 1.

Thus we seek approximate solutions that are efficiently computable. In the
next section, we adapt the Frank-Wolfe methodology—that was used for efficient
approximate solution of the seeded graph matching problem in [15]—to our
setting of seeded subgraph-subgraph graph matching.

Much of the literature on subgraph matching is focused on matching $G$ to a
subgraph of $H$ (i.e., $K=m<n$) where $H$ is often of much larger order than
$G$; see, for example, [44, 48, 34, 35, 45]. Our problem is more akin to the
$K$-core alignment problem [9] or partial alignment problem [21, 47], wherein
we seek to correctly partially align (often all but a vanishing fraction of) a
pair of large networks. However, in our present framework we do not assume the
subgraphs we seek to align have any structural properties a priori (i.e.,
density, average degree, etc.), and we do not posit a latent (or structural)
alignment of the remainder of the graphs after aligning the subgraphs.

##  3 The ssSGM algorithm

In this section we introduce the ssSGM algorithm, which provides an
efficiently computable, approximate solution to the seeded subgraph-subgraph
matching problem, by generalizing the techniques of [46, 15, 45]. The
algorithm is described as follows. We begin by relaxing the seeded subgraph-
subgraph matching problem, and then we apply Frank-Wolfe methodology to
approximately solve the relaxed problem. Finally, we project the relaxed
solution to the nearest feasible point in the original problem, which provides
an approximate solution to the seeded subgraph-subgraph matching problem. We
begin by stating two key technical lemmas.

###  3.1 Key technical lemmas

For any positive integers $c,d,e$ such that $e\leq\min\\{c,d\\}$, let
${\mathcal{D}}_{c,d,e}$ denote the set of $c\times d$ nonnegative, real
matrices with row sums at most $1$, column sums at most $1$, and all entries
summing to $e$; that is, ${\mathcal{D}}_{c,d,e}:=\\{X\in\mathbb{R}_{\geq
0}^{c\times
d}:X\vec{\mathbf{1}}_{d}\leq\vec{\mathbf{1}}_{c},\vec{\mathbf{1}}_{c}^{T}X\leq\vec{\mathbf{1}}_{d}^{T},\vec{\mathbf{1}}_{c}^{T}X\vec{\mathbf{1}}_{d}=e\\}$.
The following result is quite useful; it is essentially due to Mendelsohn and
Dulmage [33] (as extended in [20] ), and it is a generalization of the
classical Birkhoff-Von Neumann Theorem. Let $\mathcal{H}(\cdot)$ denote the
convex hull of its argument.

######  Lemma 1.

For any positive integers $c,d,e$ such that $e\leq\min\\{c,d\\}$, it holds
$\mathcal{H}(\varPi_{c,d,e})={\mathcal{D}}_{c,d,e}$.

Next, let $M$ be any given matrix in $\mathbb{R}^{c\times d}$. The generalized
linear assignment problem is defined as

$\displaystyle\max_{X\in\varPi_{c,d,e}}\textup{trace}M^{T}X$ (3)

The special case where $c=d=e$ is the well-known linear assignment problem,
and is solvable in time $O(e^{3})$ by the Hungarian Algorithm [27, 23]. Note
that (3) is equivalent to
$\max_{X\in{\mathcal{D}}_{c,d,e}}\textup{trace}M^{T}X$; this is an immediate
consequence of Lemma 1 and since, for any linear function, the function value
of a convex combination of vectors is the convex combination of the vectors’
function values.

Let $\underline{\xi}$ be any real number less than all of the entries of $M$,
and let $\overline{\xi}$ be any real number greater than all of the entries of
$M$. Define the matrix $\mathcal{M}\in\mathbb{R}^{(c+d-e)\times(c+d-e)}$ such
that $\mathcal{M}=\bigl{[}\begin{smallmatrix}M&\overline{\xi}E\\\
\overline{\xi}E&\underline{\xi}E\end{smallmatrix}\bigr{]}$, where $E$ denotes
a matrix of all $1$s, appropriately sized. In Appendix A we prove the
following lemma.

######  Lemma 2.

For any positive integers $c,d,e$ such that $e\leq\min\\{c,d\\}$, and for any
$M\in\mathbb{R}^{c\times d}$, suppose
$\mathcal{X}^{*}\in\varPi_{c+d-e,c+d-e,c+d-e}$ is a solution of the linear
assignment problem

$\max_{{\mathcal{X}}\in\varPi_{c+d-e,c+d-e,c+d-e}}\textup{trace}\mathcal{M}^{T}{\mathcal{X}}.$

Let $X^{*}$ be the $c\times d$ upper-left corner submatrix of
$\mathcal{X}^{*}$; ie induced by the first $c$ rows and first $d$ columns of
$\mathcal{X}^{*}$. Then $X^{*}$ is a solution to the generalized linear
assignment problem $\max_{X\in\varPi_{c,d,e}}\textup{trace}M^{T}X$.

###  3.2 Solving the relaxed problem with Frank-Wolfe methodology

In order to efficiently obtain an approximate solution to the seeded subgraph-
subgraph matching problem as expressed in (2), we begin by expressing its
relaxation:

$\displaystyle(\textup{relaxed seeded subgraph-subgraph matching problem})\ \
\max_{X\in{\mathcal{D}}_{m-s,n-s,K-s}}\textup{trace}A(I_{s}\oplus
X)B(I_{s}\oplus X)^{T}.$ (4)

We will apply Frank-Wolfe [18] methodology to approximately solve this relaxed
problem; afterwards, we will project the relaxed solution back to the original
feasible region.

In general, when maximizing any objective function over any polytope, Frank-
Wolfe methodology consists of generating a sequence of iterates, which are
points in the polytope, terminating when an iterate does not change much from
the previous iterate. The first iterate is an arbitrary point in the polytope
and, given any iterate, the next iterate is calculated from the current
iterate in two steps. The first step is to linearize the objective function
about the current iterate, and to maximize this linear function over the
polytope; this is simply a linear programming problem. The second step is to
maximize the (original) objective function along (only) the line segment
between the current iterate and the linear program solution from the first
step; the solution to this one-dimensional optimization problem is the next
iterate.

The objective function for the seeded subgraph-subgraph matching problem is
the quadratic function $f(X):=\textup{trace}A(I_{s}\oplus X)B(I_{s}\oplus
X)^{T}$, and we want to maximize it over the set
${\mathcal{D}}_{m-s,n-s,K-s}$, which is clearly a polytope. A natural choice
for the first Frank-Wolfe iterate is the $(m-s)\times(n-s)$ matrix with all
entries $\frac{K-s}{(m-s)(n-s)}$, which is clearly in
${\mathcal{D}}_{m-s,n-s,K-s}$.

Given any current Frank-Wolfe iterate, say $Z\in{\mathcal{D}}_{m-s,n-s,K-s}$,
the linearization of $f$ about $Z$ is given by $\textup{trace}[\nabla
f(Z)]^{T}X$ plus a fixed constant that can be ignored when maximizing. If we
partition $A=\bigl{[}\begin{smallmatrix}A^{(11)}&A^{(21)^{T}}\\\
A^{(21)}&A^{(22)}\end{smallmatrix}\bigr{]}$ and
$B=\bigl{[}\begin{smallmatrix}B^{(11)}&B^{(12)}\\\
B^{(12)^{T}}&B^{(22)}\end{smallmatrix}\bigr{]}$, where
$A^{(21)}\in\\{-1,1\\}^{(m-s)\times s}$,
$B^{(12)}\in\\{-1,1\\}^{s\times(n-s)}$,
$A^{(22)}\in\\{-1,1\\}^{(m-s)\times(m-s)}$, and
$B^{(22)}\in\\{-1,1\\}^{(n-s)\times(n-s)}$ then $\nabla
f(X)=2A^{(21)}B^{(12)}+2A^{(22)}XB^{(22)}$, hence the first step to computing
the next Frank-Wolfe iterate is to solve the generalized linear assignment
problem

$\displaystyle\max_{X\in{\mathcal{D}}_{m-s,n-s,K-s}}\textup{trace}\left(A^{(21)}B^{(12)}+A^{(22)}ZB^{(22)}\right)^{T}X,$
(5)

which can be done efficiently (in cubic time) via the Hungarian Algorithm,
thanks to Lemma 2. Say the solution $X$ to this linear program is
$X^{*}\in{\mathcal{D}}_{m-s,n-s,K-s}$. The second step to computing the next
Frank-Wolfe iterate is maximizing $f$ along the line segment $\\{\lambda
X^{*}+(1-\lambda)Z:\lambda\in[0,1]\\}$; this is trivial to do since $f$ is a
quadratic function in $\lambda$. Say the optimal $\lambda$ is $\lambda^{*}$.
The the next Frank-Wolfe iterate is defined to be
$\lambda^{*}X^{*}+(1-\lambda^{*})Z\in{\mathcal{D}}_{m-s,n-s,K-s}$.

When the Frank-Wolfe algorithm terminates, say that
$Z\in{\mathcal{D}}_{m-s,n-s,K-s}$ is the output. That is, $Z$ is the
approximate solution to the relaxed problem (4). Since $Z$ may not be binary
valued, our last task is to find a nearest matrix that is feasible in the
original problem, ie. we solve
$\min_{X\in\varPi_{m-s,n-s,K-s}}\|X-Z\|_{F}^{2}$. Noting that
$\|X-Z\|_{F}^{2}=\|X\|_{F}^{2}-2\textup{trace}Z^{T}X+\|Z\|_{F}^{2}$, we see
that this is equivalent to solving
$\max_{X\in\varPi_{m-s,n-s,K-s}}\textup{trace}Z^{T}X$, which is again a
generalized linear assignment problem, solvable efficiently (in cubic time)
via the Hungarian Algorithm, thanks to Lemma 2. The optimal solution will be
an approximate solution to the seeded subgraph-subgraph matching problem as
expressed in (2) and is the output of this algorithm which we call ssSGM. We
summarize the algorithm as follows:

Input : Adjacency matrices $A\in\\{-1,1\\}^{m\times m}$,
$B\in\\{-1,1\\}^{n\times n}$ of $G$,$H$ respectively, $K:=$ the number of core
vertices, $s:=$ the number of seeds

Initialization : $Z\leftarrow$ the matrix in ${\mathcal{D}}_{m-s,n-s,K-s}$
with all entries $\frac{K-s}{(m-s)(n-s)}$

1 while  _$Z$ is not approximately equal to what it was in immediately
previous iteration_ do

2 Calculate $M\leftarrow
A^{(21)}B^{(12)}+A^{(22)}ZB^{(22)}\in\mathbb{R}^{(m-s)\times(n-s)}$;

3

4 Compute
$X^{*}\leftarrow\arg\max_{X\in\varPi_{m-s,n-s,K-s}}\textup{trace}M^{T}X$ via
Algorithm 2 ;

5

6 Solve $\max_{\lambda\in[0,1]}\textup{trace}A(I_{s}\oplus[\lambda
X^{*}+(1-\lambda)Z])B\left(I_{s}\oplus[\lambda
X^{*}+(1-\lambda)Z]\right)^{T}$; this is done exactly since the objective is
quadratic in the one variable $\lambda$. Say $\lambda^{*}$ is the solution ;

7

8 Set $Z\leftarrow\lambda^{*}X^{*}+(1-\lambda^{*})Z$ ;

9

10 end while

11

12Compute
$X^{*}\leftarrow\arg\max_{X\in\varPi_{m-s,n-s,K-s}}\textup{trace}Z^{T}X$ via
Algorithm 2 ;

13

Output : sets $\Omega:=\\{v_{i}:\exists j\mbox{ s.t. }(I_{s}\oplus
X^{*})_{ij}=1\\},\Lambda:=\\{w_{j}:\exists i\mbox{ s.t. }(I_{s}\oplus
X^{*})_{ij}=1\\}$. function $\phi:\Omega\rightarrow\Lambda$ where $\forall
i,j$ $\phi(v_{i})=w_{j}$ if and only if $(I_{s}\oplus X^{*})_{ij}=1$ .

Algorithm 1 ssSGM Algorithm

The ssSGM Algorithm (Algorithm 1) utilizes the following subroutine Algorithm
2 to solve the generalized linear assigment problem.

Input : Positive integers $c,d,e$ such that $e\leq\min\\{c,d\\}$ and matrix
$M\in\mathbb{R}^{c\times d}$

1

2Calculate $\underline{\xi}\leftarrow\min\\{M_{ij}\\}-1$,
$\overline{\xi}\leftarrow\max\\{M_{ij}\\}+1$;

3

4Construct
$\mathcal{M}\leftarrow\bigl{[}\begin{smallmatrix}M&\overline{\xi}E\\\
\overline{\xi}E&\underline{\xi}E\end{smallmatrix}\bigr{]}\in\mathbb{R}^{(c+d-e)\times(c+d-e)}$,
where matrix $E$ is all $1$s, appropriately sized ;

5

6Solve
$\max_{{\mathcal{X}}\in\varPi_{c+d-e,c+d-e,c+d-e}}\textup{trace}\mathcal{M}^{T}{\mathcal{X}}$
with Hungarian Algorithm ;

7

8Define $X^{*}$ to be the first $c$ rows and first $d$ columns of the optimal
${\mathcal{X}}$ in line 3 ;

9

Output : $X^{*}\in\varPi_{c,d,e}$

Algorithm 2 Solving generalized linear assignment problem:
$\max_{X\in\varPi_{c,d,e}}\textup{trace}M^{T}X$

In the special case where $m=n=K$, the ssSGM algorithm is the SGM algorithm of
[15], the one difference being that SGM can and does use the standard
$\\{0,1\\}$-adjacency matrices instead of the $\\{-1,1\\}$-adjacency matrices
used in ssSGM; indeed, ssSGM can’t use $\\{0,1\\}$-adjacency matrices in
general. Also, in the general case, the ssSGM algorithm is utilizing
innovative techniques introduced here.

##  4 Experiments with synthetic data

In this section we perform numerical experiments to illustrate the utility of
the ssSGM algorithm.

We will be working with the correlated Erdos-Renyi random graph model, a
special case of the correlated Bernoulli random graph model in Section 6.1.
The model parameters are positive integers $n,K$ such that $K\leq n$ and real
numbers $p,\varrho\in[0,1]$. The vertex set of $G$ is
$V=\\{v_{1},v_{2},\ldots,v_{n}\\}$ and the vertex set of $H$ is
$W=\\{w_{1},w_{2},\ldots,w_{n}\\}$. For all positive integers $i,j$ such that
$1\leq i<j\leq n$, $p$ is the probability that $v_{i}\sim_{G}v_{j}$, and $p$
is the probability that $w_{i}\sim_{H}w_{j}$. For all positive integers $i,j$
such that $1\leq i<j\leq K$, $\varrho$ is the Pearson correlation coefficient
for the Bernoulli random variable indicating adjacency $v_{i}\sim_{G}v_{j}$
with the Bernoulli random variable indicating adjacency $w_{i}\sim_{H}w_{j}$;
all other adjacencies are collectively independent. The random graphs $(G,H)$
are called correlated Erdos-Renyi random graphs. The parameters
$n,K,p,\varrho$ fully specify the distribution of $(G,H)$. Clearly, the core
here are the vertices $\\{v_{1},v_{2},\ldots,v_{K}\\}$ and
$\\{w_{1},w_{2},\ldots,w_{K}\\}$, with the natural alignment associating
$v_{i}$ to $w_{i}$, for all $i=1,2,\ldots,K$. There are $s$ seeds, for a given
nonnegative integer $s\leq K$, and they are $\\{v_{1},v_{2},\ldots,v_{s}\\}$
and $\\{w_{1},w_{2},\ldots,w_{s}\\}$.

After realizing $G$ and $H$ from this model, we discrete-uniformly randomly
relabel the nonseed vertices $\\{v_{s+1},v_{s+2},\ldots,v_{n}\\}$ of $G$. and
the nonseed vertices $\\{w_{s+1},w_{s+2},\ldots,w_{n}\\}$ of $H$. We use the
ssSGM algorithm with the $s$ seeds to attempt to identify the $K$ core
vertices in $G$ and in $H$ and to align them; the ssSGM’s match ratio is the
fraction of the $K-s$ nonseed, core vertices of $G$ that the algorithm
correctly matches to their naturally aligned counterpart in $H$. We also use
the SGM algorithm to do a seeded graph match of $G$ to $H$; recall that the
SGM algorithm applies Frank-Wolfe methodology to match the entire graphs, and
not just subgraphs, which is the innovation of ssSGM. As above, SGM’s match
ratio is the fraction of the $K-s$ nonseed, core vertices of $G$ that the
algorithm correctly matches.

When running the SGM algorithm, $\\{-1,1\\}$-adjacency matrices were used
instead of the usual $\\{0,1\\}$-adjacency matrices. This was done in order to
make the most fair comparison with the ssSGM algorithm, which requires the use
of $\\{-1,1\\}$-adjacency matrices. However, empirical experiments indicate
that the choice of $\\{-1,1\\}$-adjacency matrices v.s. $\\{0,1\\}$-adjacency
matrices in the SGM algorithm doesn’t significantly affect the runtime and
effectiveness of the SGM algorithm.

The experiments here had $n=500$, $K=100$, and we did $200$ experiments for
each combination of $p=0.1,0.3,0.5$ and $\varrho=0.5,0.6,0.7,0.8$ and
$s=5,10,15,20,\ldots,50$; for each such combination, we averaged the match
ratio for each of ssSGM and SGM over the $200$ experiments. Figure 1 plots the
average match ratios of ssSGM and SGM against the number of seeds $s$, for
each combination of $\varrho$ and $p$. The difference between the average
match ratios of ssSGM and SGM is highlighted in green when the average match
ratio of ssSGM was higher than that of SGM, and the difference is highlighted
in red otherwise.

$\varrho=0.5,p=0.1$

$\varrho=0.5,p=0.3$

$\varrho=0.5,p=0.5$

$\varrho=0.6,p=0.1$

$\varrho=0.6,p=0.3$

$\varrho=0.6,p=0.5$

$\varrho=0.7,p=0.1$

$\varrho=0.7,p=0.3$

$\varrho=0.7,p=0.5$

$\varrho=0.8,p=0.1$

$\varrho=0.8,p=0.3$

$\varrho=0.8,p=0.5$

Figure 1: ssSGM vs SGM on synthetic data

Note that ssSGM is empirically seen here to achieve a better match ratio than
SGM as the graphs gets less sparse (less dense, if the density is more than
$0.5$) and as the correlation between the two graphs gets stronger. However,
ssSGM identifies the core vertices in the two graphs, which SGM is not
designed to do. So, even in cases where SGM achieves a better match ratio on
the core, this might be useless as a practical matter if the core vertices
need to be identified.

##  5 Experiments with real data

The data set for this section comes from the University of California Irvine
Machine Learning Repository. “Mathwiki” is a simple graph with $1068$ vertices
and $27079$ edges; the vertices are Wikipedia pages for mathematics topics
and, for every pair of vertices, the two vertices are adjacent precisely when
one associated webpage has a hyperlink to the other associated webpage. The
data set is found at
https://archive.ics.uci.edu/ml/datasets/Wikipedia+Math+Essentials.

For each value of $K=700,800,900,1000$ and each number of seeds
$s=20,40,60,...,500$, we perform the following experiment $200$ times. We
randomly select $K$ core vertices from the $1068$ vertices of Mathwiki. The
set $V$ consists of the $K$ core vertices and $\frac{1068-K}{2}$ randomly
selected noncore vertices of Mathwiki, and the set $W$ consists of the $K$
core vertices and the other $\frac{1068-K}{2}$ noncore vertices of Mathwiki.
The graph $G$ is defined as Mathwiki induced by $V$, and the graph $H$ is
defined as Mathwiki induced by $W$. The $K$ core vertices are common to both
$G$ and $H$ with the identity mapping, and we randomly choose $s$ seeds from
the $K$ core vertices. The nonseed vertices of $G$ are randomly permuted and
the nonseed vertices of $H$ are randomly permuted. We run ssSGM and SGM on
$(G,H)$, and average the core match ratios for ssSGM and for SGM over the
$200$ repetitions.

$K=700,\ \ m=n=884$

$K=800,\ \ m=n=934$

$K=900,\ \ m=n=984$

$K=1000,\ \ m=n=1034$

Figure 2: Mathwiki experiments

Figure 2 plots the average match ratios of ssSGM and SGM against the number of
seeds $s$, separately for each value of $K$. The difference between the
average match ratios of ssSGM and SGM is highlighted in green when the average
match ratio of ssSGM was higher than that of SGM, and the difference is
highlighted in red otherwise.

Real data is often quite sparse, and sometimes the correlation between core
vertices can be quite weak. In those circumstances SGM can achieve a higher
core match ration than ssSGM but, as mentioned before, this might be
meaningless when the core needs to be identified, a task that ssSGM is
designed to perform and SGM is not. The Mathwiki graph has density
$\frac{27079}{\binom{1068}{2}}=0.0475$, which is somewhat sparse, but the core
correlation is perfect; indeed, the match ratios were high, and ssSGM
outperformed SGM in average match ratio. Note that the $y$-axis in Figure 1
was from $0$ to $1$, whereas the $y$-axis in Figure 2 was scaled much closer
to $1$.

##  6 Consistency

Until this point in this paper, our work has been focused on developing the
ssSGM algorithm and highlighting it as an efficient and effective tool for the
seeded subgraph-subgraph matching problem. This section, Section 6, is
concerned with matchability from the information theory direction and is in
the spirit of [45, 31]. Specifically, when there is a natural underlying
correspondence between a core of a pair of graphs, when will the solution to
the seeded subgraph-subgraph matching problem identify this core and give us
this natural correspondence? Our main result for this work is Theorem 3 which,
under the model described in Section 6.1, guarantees that this almost always
happens when there are mild assumptions.

###  6.1 The random graph model and the main consistency result

We first define the correlated Bernoulli random graph model with which we will
work. For any positive integer $k$, let $[k]$ denote the set of integers
$\\{1,2,3,\ldots,k\\}$. The Bernoulli random graph model parameters are
positive integers $m,n,K$ such that $K\leq\min\\{m,n\\}$ and, for all positive
integers $i,j$ such that $1\leq i<j\leq\max\\{m,n\\}$, real number
$p_{ij}\in[0,1]$ and, for all positive integers $i,j$ such that $1\leq i<j\leq
K$, real number $\varrho_{ij}\in[0,1]$. For simplicity, the vertex set of $G$
is $V=[m]$ and the vertex set of $H$ is $W=[n]$. For all positive integers
$i,j$ such that $1\leq i<j\leq m$, $p_{ij}$ is the probability that
$i\sim_{G}j$ and, for all positive integers $i,j$ such that $1\leq i<j\leq n$,
$p_{ij}$ is the probability that $i\sim_{H}j$ and, for all positive integers
$i,j$ such that $1\leq i<j\leq K$, $\varrho_{ij}$ is the Pearson correlation
coefficient for the Bernoulli random variable indicating adjacency
$i\sim_{G}j$ with the Bernoulli random variable indicating adjacency
$i\sim_{H}j$; all other adjacencies are collectively independent. The random
graphs $(G,H)$ are called correlated Bernoulli random graphs.

The parameters fully specify the distribution of $(G,H)$. Clearly, the core
here are the vertices $[K]\subseteq V$ and $[K]\subseteq W$, with the natural
alignment associating $i\in V$ to $i\in W$, for all $i=1,2,\ldots,K$. For our
main result in this section, we will not need to suppose there are seeds.

Assumptions for Section 6: We are considering a sequence of model instances
with the following three assumptions:

  * •

For each value $\mathfrak{n}=1,2,3,\ldots$, we are considering a model
instance with $\mathfrak{n}=\max\\{m,n\\}$, so the model parameters
$m,n,K,p_{ij},\varrho_{ij}$ (for all relevant $i,j$) are all functions of
$\mathfrak{n}$, even as the notation for these parameters omits $\mathfrak{n}$
for ease of exposition.

  * •

We assume that there exists a real number $q\in(0,\frac{1}{2})$, which is not
a function of $\mathfrak{n}$, such that, for all $\mathfrak{n}=1,2,\ldots$, it
holds that $p_{ij}\in[q,1-q]$ for all $i,j:1\leq i<j\leq\mathfrak{n}$, and
$\varrho_{ij}>(1-2q)^{2}$ for all $i,j:1\leq i<j\leq K$.

  * •

For each $\mathfrak{n}=1,2,3,\ldots$, define $\epsilon:=\min_{i,j:1\leq
i<j\leq K}\left(\varrho_{ij}-(1-2q)^{2}\right)$; of course, $\epsilon$ is a
function of $\mathfrak{n}$, and $\epsilon\in(0,1)$. We assume that
$\epsilon^{2}K\in\omega(\log\mathfrak{n})$; specifically,
$\lim_{\mathfrak{n}\rightarrow\infty}\frac{\epsilon^{2}K}{\log\mathfrak{n}}=\infty$.

We will say that a property of such random graphs $(G,H)$ holds almost always
to mean that, with probability $1$, the property holds for all but a finite
number of values of $\mathfrak{n}$.

Recall that the matrices $A$ and $B$ are such that for each $i,j$ we have
$A_{ij}$ is $1$ or $-1$ according as $i\sim_{G}j$ or not, and $B_{ij}$ is $1$
or $-1$ according as $i\sim_{H}j$ or not. This means that the diagonals of $A$
and $B$ are all $-1$s. However, as long as the values of the diagonals are all
equal to each other, the specific (common) value does not affect the solution
of the subgraph-subgraph matching problem

$\displaystyle\max_{X\in\varPi_{m,n,K}}\textup{trace}AXBX^{T}\ \ $ (6)

since it just changes the objective function by a constant. It will be helpful
for our analysis in Section 6 to have the diagonals of $A$ and $B$ be all
zeros, and we adopt this convention. The relaxed subgraph-subgraph matching
problem

$\displaystyle\max_{X\in{\mathcal{D}}_{m,n,K}}\textup{trace}AXBX^{T}\ \ $ (7)

is affected, but the results of this convention do not empirically seem to
change the efficacy of the ssSGM algorithm. The main result of Section 6 is
the following. ($I_{K}$ denotes the $K\times K$ identity matrix, and the zero
matrices are appropriately sized.)

######  Theorem 3.

Under the above Assumptions of Section 6, it almost always holds that

$\arg\max_{X\in\varPi_{m,n,K}}\textup{trace}AXBX^{T}=\arg\max_{X\in{\mathcal{D}}_{m,n,K}}\textup{trace}AXBX^{T}=\left\\{\bigl{[}\begin{smallmatrix}I_{K}&0\\\
0&0\end{smallmatrix}\bigr{]}\right\\}.$

In other words, under the above-specified conditions, the subgraph-subgraph
matching problem solution almost always locates the correct core and correctly
matches these core vertices. Moreover, even the relaxed problem solution
achieves this goal, which further motivates the focus of the ssSGM algorithm
on solving the relaxed problem.

The following is the key lemma (which we prove in the upcoming sections) from
which our main result Theorem 3 immediately follows.

######  Lemma 4.

Under the above Assumptions of Section 6, it almost always holds that

$\arg\max_{P,Q\in\varPi_{m,n,K}}\textup{trace}APBQ^{T}=\left\\{\bigl{[}\begin{smallmatrix}I_{K}&0\\\
0&0\end{smallmatrix}\bigr{]}\right\\}.$

Proof of Theorem 3: By Lemma 1, any $X\in{\mathcal{D}}_{m,n,K}$ can be
expressed $X=\sum_{i}\alpha_{i}P^{(i)}$ where $\\{\alpha_{i}\\}$ are
nonnegative real numbers that sum to $1$ and $\\{P^{(i)}\\}=\varPi_{m,n,K}$.
Then

$\textup{trace}AXBX^{T}=\textup{trace}A\left(\sum_{i}\alpha_{i}P^{(i)}\right)B\left(\sum_{j}\alpha_{j}P^{(j)}\right)^{T}=\sum_{i,j}\alpha_{i}\alpha_{j}\textup{trace}AP^{(i)}BP^{(j)T}$

is a convex combination of expressions of the form $\textup{trace}APBQ^{T}$ in
Lemma 4, and Theorem 3 follows immediately from Lemma 4. ∎

In order to prove Lemma 4 (which was used just above to prove our main result
Theorem 3), we provide some preliminaries next in Section 6.2, including some
observations regarding the distribution of the random graphs and also another
key lemma. Then we will prove Lemma 4 in Section 6.3.

###  6.2 Preliminaries for the proof of Lemma 4

In this section we provide some preliminaries for the proof of Lemma 4,
continuing with the notation of Section 6.1.

For any positive integers $i,j$ such that $1\leq i<j\leq K$, it is
straightforward to calculate the joint probabilities of adjacency for $i,j$ in
$G$ and $i,j$ in $H$:

$\displaystyle\begin{array}[]{c||cc}&i\sim_{H}j&i\not\sim_{H}j\\\
\hline\cr\hline\cr
i\sim_{G}j&p_{ij}^{2}+\varrho_{ij}p_{ij}(1-p_{ij})&(1-\varrho_{ij})p_{ij}(1-p_{ij})\\\
i\not\sim_{G}j&(1-\varrho_{ij})p_{ij}(1-p_{ij})&(1-p_{ij})^{2}+\varrho_{ij}p_{ij}(1-p_{ij})\end{array}$
(11)

Suppose that the random variables $Y\sim\textup{Bernoulli}(p_{ij})$,
$Y_{Heads}\sim\textup{Bernoulli}\left(\varrho_{ij}\cdot
1+(1-\varrho_{ij})p_{ij}\right)$,
$Y_{Tails}\sim\textup{Bernoulli}\left(\varrho_{ij}\cdot
0+(1-\varrho_{ij})p_{ij}\right)$ are independent. It will be useful to note by
simple computation that the joint distribution of the pair of random variables
$(Y,\ (1-Y)Y_{Tails}+Y\cdot Y_{Heads})$ is that same as that of
$(Y,Y^{\prime})$ where $Y^{\prime}\sim\textup{Bernoulli}(p_{ij})$ and the
Pearson correlation coefficient for $Y,Y^{\prime}$ is $\rho_{ij}$; indeed, the
joint probabilities are given above in (11). As a consequence, the
distribution of the pair of random variables $(A_{ij},B_{ij})$ is a function
of three independent Bernoulli random variables. The following result from
[25] will be very useful to us.

######  Theorem 5.

Let $Y_{1},Y_{2},\ldots,Y_{N}$ be independent Bernoulli random variables with
respective Bernoulli parameters $r_{1},r_{2},\ldots,r_{N}$. Let
$g:\\{0,1\\}^{N}\rightarrow\mathbb{R}$ be a function and $L\in\mathbb{R}_{>0}$
with the property that for any $y,y^{\prime}\in\\{0,1\\}^{N}$ such that
$y,y^{\prime}$ differ in exactly one position (ie.
$\sum_{i=1}^{N}|y_{i}-y_{j}|=1$) it holds that $|g(y)-g(y^{\prime})|\leq L$.
Define $\sigma:=L\sqrt{\sum_{i=1}^{N}r_{i}(1-r_{i})}$ and define
$Y:=g(Y_{1},Y_{2},\ldots,Y_{N})$. Then

$\mbox{for any }\tau:0\leq\tau<2\frac{\sigma}{L}\ \mbox{ it holds that }\
\mathbb{P}\left(|Y-\mathbb{E}Y|>\tau\sigma\right)\leq
2e^{-\frac{\tau^{2}}{4}}.$

###  6.3 Proof of Lemma 4

In this section we prove Lemma 4, continuing with the notation of Section 6.1.

For any particular value of $\mathfrak{n}$, consider for now any particular
(fixed) $P,Q\in\varPi_{m,n,K}$ such that $P$ and $Q$ are not both
$\bigl{[}\begin{smallmatrix}I_{K}&0\\\ 0&0\end{smallmatrix}\bigr{]}$. Define
the random variable

$\displaystyle Y_{PQ}:=\textup{trace}A\bigl{[}\begin{smallmatrix}I_{K}&0\\\
0&0\end{smallmatrix}\bigr{]}B\bigl{[}\begin{smallmatrix}I_{K}&0\\\
0&0\end{smallmatrix}\bigr{]}^{T}-\textup{trace}APBQ^{T}$

(which is random by virtue of the $\pm 1$-adjacency matrices $A$ and $B$); our
first task (receiving the bulk of our attention in this proof) is to bound
$\mathbb{P}(Y_{PQ}\leq 0)$. With a strong enough bound, we will then be able
to consider all possible such $P,Q$, and all $\mathfrak{n}$, and quickly prove
Lemma 4.

For any positive integer $a$, let $[a]$ denote the set of integers
$\\{1,2,3,\ldots,a\\}$. Define

$\displaystyle\Omega_{P}:=\\{i\in[m]\ :\ \exists j\in[n]\mbox{ such that
}P_{ij}=1\\},\ \ \Lambda_{P}:=\\{j\in[n]\ :\ \exists i\in[m]\mbox{ such that
}P_{ij}=1\\},$ $\displaystyle\Omega_{Q}:=\\{i\in[m]\ :\ \exists j\in[n]\mbox{
such that }Q_{ij}=1\\},\ \ \Lambda_{Q}:=\\{j\in[n]\ :\ \exists i\in[m]\mbox{
such that }Q_{ij}=1\\}.$

Of course, $|\Omega_{P}|=|\Lambda_{P}|=|\Omega_{Q}|=|\Lambda_{Q}|=K$, by
definition.
Define the following bijections:

$\displaystyle\phi_{P}:\Omega_{P}\rightarrow\Lambda_{P}\mbox{ such that
}\phi_{P}(i)=j\mbox{ precisely when }P_{ij}=1,$
$\displaystyle\phi_{Q}:\Omega_{Q}\rightarrow\Lambda_{Q}\mbox{ such that
}\phi_{Q}(i)=j\mbox{ precisely when }Q_{ij}=1,$

In what follows, $(i,j)$ will refer to the ordered pair of indices (as opposed
to an open interval). Define

$\displaystyle S_{I}$ $\displaystyle=$ $\displaystyle\\{(i,j)\in[K]\times[K]\
:\ i\neq j\\}$ $\displaystyle S_{PQ}$ $\displaystyle=$
$\displaystyle\\{(i,j)\in\Omega_{P}\times\Omega_{Q}\ :\ i\neq j\mbox{ and
}\phi_{P}(i)\neq\phi_{Q}(j)\\}$ $\displaystyle S$ $\displaystyle=$
$\displaystyle\\{(i,j)\in S_{I}\ :\ \phi_{P}(i)=i\mbox{ and }\phi_{Q}(j)=j\\}$
$\displaystyle S^{\prime}$ $\displaystyle=$ $\displaystyle\\{(i,j)\in S_{I}\
:\ \phi_{P}(i)=j\mbox{ and }\phi_{Q}(j)=i\\}$

Note that $S$ and $S^{\prime}$ are disjoint, and that $S\cup
S^{\prime}\subseteq S_{I}$ and $S\cup S^{\prime}\subseteq S_{PQ}$. Also note
that for all $(i,j)\in S\cup S^{\prime}$ we have
$A_{ij}B_{ij}=A_{ij}B_{\phi_{P}(i),\phi_{Q}(j)}$, hence it holds that

$\displaystyle Y_{PQ}$ $\displaystyle:=$
$\displaystyle\textup{trace}A\bigl{[}\begin{smallmatrix}I_{K}&0\\\
0&0\end{smallmatrix}\bigr{]}B\bigl{[}\begin{smallmatrix}I_{K}&0\\\
0&0\end{smallmatrix}\bigr{]}^{T}-\textup{trace}APBQ^{T}$ (12)
$\displaystyle\equiv$ $\displaystyle\sum_{(i,j)\in S_{I}}A_{ij}B_{ij}\ \ \
-\sum_{(i,j)\in S_{PQ}}A_{ij}B_{\phi_{P}(i),\phi_{Q}(j)}$ $\displaystyle=$
$\displaystyle\sum_{(i,j)\in S_{I}\backslash(S\cup S^{\prime})}A_{ij}B_{ij}\ \
\ -\sum_{(i,j)\in S_{PQ}\backslash(S\cup
S^{\prime})}A_{ij}B_{\phi_{P}(i),\phi_{Q}(j)}.$

Next, define

$\displaystyle T_{PQ}$ $\displaystyle=$ $\displaystyle\\{i\in[K]\ :\
\phi_{P}(i)=\phi_{Q}(i)=i\\}$ $\displaystyle T_{P}$ $\displaystyle=$
$\displaystyle\\{i\in[K]\ :\ \phi_{P}(i)=i\\}\ \backslash\ T_{PQ}$
$\displaystyle T_{Q}$ $\displaystyle=$ $\displaystyle\\{i\in[K]\ :\
\phi_{Q}(i)=i\\}\ \backslash\ T_{PQ}$

Note that $T_{PQ}\subseteq\Omega_{P}\cap\Omega_{Q}$,
$T_{P}\subseteq\Omega_{P}$, and $T_{Q}\subseteq\Omega_{Q}$. Of course,
$T_{PQ}$, $T_{P}$, and $T_{Q}$ are mutually disjoint. Denote
$t_{PQ}:=|T_{PQ}|$, $t_{P}:=|T_{P}|$, and $t_{Q}:=|T_{Q}|$.

The following relationships are easy to demonstrate:

$\displaystyle t_{PQ}$ $\displaystyle<$ $\displaystyle K$ (13) $\displaystyle
t_{PQ}+t_{P}+t_{Q}$ $\displaystyle\leq$ $\displaystyle K$ (14)
$\displaystyle|S_{I}|$ $\displaystyle=$ $\displaystyle K^{2}-K$ (15)
$\displaystyle|S_{PQ}|$ $\displaystyle\leq$ $\displaystyle K^{2}-t_{PQ}$ (16)
$\displaystyle|S_{PQ}|$ $\displaystyle\geq$ $\displaystyle K^{2}-2K+t_{PQ}$
(17) $\displaystyle|S^{\prime}|$ $\displaystyle\leq$ $\displaystyle K-t_{PQ}$
(18) $\displaystyle|S|$ $\displaystyle=$ $\displaystyle
t_{PQ}(t_{PQ}-1)+t_{PQ}(t_{P}+t_{Q})+t_{P}t_{Q}$ (19) $\displaystyle\leq$
$\displaystyle t_{PQ}(t_{PQ}-1)+t_{PQ}(K-t_{PQ})+\frac{(K-t_{PQ})^{2}}{4}$
$\displaystyle=$
$\displaystyle\frac{K^{2}}{4}+\frac{Kt_{PQ}}{2}+\frac{t_{PQ}^{2}}{4}-t_{PQ}$

Inequality (16) holds since $|\Omega_{P}|=|\Omega_{Q}|=K$ and, if $i\in
T_{PQ}$, then $(i,i)\in\Omega_{P}\times\Omega_{Q}$ and $(i,i)\not\in S_{PQ}$.
Inequality (17) holds since $\\{(i,j)\in\Omega_{P}\times\Omega_{Q}\ :\ i\neq
j\\}$ has at least $K^{2}-K$ elements, and
$\\{(i,j)\in\Omega_{P}\times\Omega_{Q}\ :\ i\neq j\mbox{ and
}\phi_{P}(i)=\phi_{Q}(j)\\}$ has at most $K-t_{PQ}$ elements. The inequality
in (19) follows from (14) and the Arithmetic-Geometric Mean Inequality, which
says $t_{P}t_{Q}\leq\left(\frac{t_{P}+t_{Q}}{2}\right)^{2}$.

Now, define $\beta$ and $\gamma$ as follows:

$\displaystyle\beta$ $\displaystyle:=$ $\displaystyle
K^{2}-3K+2t_{PQ}-(t_{PQ}(t_{PQ}-1)+t_{PQ}(t_{P}+t_{Q})+t_{P}t_{Q})$ (20)
$\displaystyle\gamma$ $\displaystyle:=$ $\displaystyle
K^{2}-t_{PQ}-(t_{PQ}(t_{PQ}-1)+t_{PQ}(t_{P}+t_{Q})+t_{P}t_{Q})$ (21)

The point of defining $\beta$ and $\gamma$ as such is that, by easy
application of Equations (15) through (19), the cardinalities of the sets
indexing the sums in Equation 12 can be bounded as

$\displaystyle\beta$ $\displaystyle\leq$ $\displaystyle|S_{I}\backslash(S\cup
S^{\prime})|=|S_{I}|-|S|-|S^{\prime}|\leq\gamma$ (22) $\displaystyle\beta$
$\displaystyle\leq$ $\displaystyle|S_{PQ}\backslash(S\cup
S^{\prime})|=|S_{PQ}|-|S|-|S^{\prime}|\leq\gamma.$ (23)

We next show that, for $\mathfrak{n}$ large enough, it holds that

$\displaystyle\beta>0\ \ \ \mbox{ and }\ \ \ \gamma\leq 2\beta.$ (24)

Indeed, using the definition of $\beta$ in (21), applying the inequality (19),
gives us

$\displaystyle\beta$ $\displaystyle\geq$ $\displaystyle
K^{2}-3K+2t_{PQ}-\left(\frac{K^{2}}{4}+\frac{Kt_{PQ}}{2}+\frac{t_{PQ}^{2}}{4}-t_{PQ}\right)$
(25) $\displaystyle=$
$\displaystyle\frac{3}{4}K^{2}-3K+3t_{PQ}-\frac{Kt_{PQ}}{2}-\frac{t_{PQ}^{2}}{4}$
$\displaystyle\geq$
$\displaystyle\frac{3}{4}K^{2}-3K+3t_{PQ}-\frac{Kt_{PQ}}{2}-\frac{K^{2}}{4}$
$\displaystyle=$ $\displaystyle\frac{1}{2}(K-t_{PQ})(K-6)\ >0\ \ \ \ \ \ \ \
\mbox{ when }K>6.$

From the Assumptions of Section 6 listed in Section 6.1, recall that
$\epsilon^{2}K\in\omega(\log\mathfrak{n})$. Since $\epsilon\in(0,1)$, we have
that $K$ goes to infinity as $\mathfrak{n}$ goes to infinity. Thus $\beta\geq
0$ when $\mathfrak{n}$ is large enough. Next, using the definitions of $\beta$
and $\gamma$ in (21), applying the inequality (19), gives us

$\displaystyle 2\beta-\gamma$ $\displaystyle=$ $\displaystyle
K^{2}-6K+5t_{PQ}-(t_{PQ}(t_{PQ}-1)+t_{PQ}(t_{P}+t_{Q})+t_{P}t_{Q})$ (26)
$\displaystyle\geq$ $\displaystyle
K^{2}-6K+5t_{PQ}-\left(\frac{K^{2}}{4}+\frac{Kt_{PQ}}{2}+\frac{t_{PQ}^{2}}{4}-t_{PQ}\right)$
$\displaystyle=$
$\displaystyle\frac{3}{4}K^{2}-6K+6t_{PQ}-\frac{Kt_{PQ}}{2}-\frac{t_{PQ}^{2}}{4}.$

The bottom line of (26) is a concave quadratic in the variable $t_{PQ}$ hence,
when minimizing it over $t_{PQ}$ in the range of
$t_{PQ}\in\\{0,1,2,\ldots,K-1\\}$, the minimum is achieved when $t_{PQ}$ is
$0$ or $K-1$. Plugging in $0$ for $t_{PQ}$ in the bottom line of (26) yields
$\frac{3}{4}K^{2}-6K$, and plugging in $K-1$ for $t_{PQ}$ in the bottom line
of (26) yields $K-6-\frac{1}{4}$. Hence we have that $2\beta-\gamma\geq 0$ for
$\mathfrak{n}$ big enough (hence $K$ is big enough), completing our
demonstration of (24).

We are now almost prepared to bound the expectation of $Y_{PQ}$. From the
joint probability formula in Equation(11), we calculate, for each $(i,j)\in
S_{I}$,

$\displaystyle\mathbb{E}(A_{ij}B_{ij})$ $\displaystyle=$ $\displaystyle
p^{2}_{ij}+\varrho_{ij}p_{ij}(1-p_{ij})+(1-p_{ij})^{2}+\varrho_{ij}p_{ij}(1-p_{ij})-2(1-\varrho_{ij})p_{ij}(1-p_{ij})$
(27) $\displaystyle=$
$\displaystyle(1-2p_{ij})^{2}+4p_{ij}(1-p_{ij})\varrho_{ij}$
$\displaystyle\geq$
$\displaystyle(1-2p_{ij})^{2}\varrho_{ij}+4p_{ij}(1-p_{ij})\varrho_{ij}$
$\displaystyle=$ $\displaystyle\varrho_{ij}\ \ \geq(1-2q)^{2}+\epsilon,$

the last inequality following from the Assumptions for Section 6 listed in
Section 6.1. However, for any positive integers $i,j\in[m]$ such that $i\neq
j$ and any $i^{\prime},j^{\prime}\in[n]$ such that $i^{\prime}\neq
j^{\prime}$, and also such that $i$ being adjacent to $j$ in $G$ is
independent of $i^{\prime}$ being adjacent to $j^{\prime}$ in $H$, we have

$\displaystyle\mathbb{E}(A_{ij}B_{i^{\prime}j^{\prime}})\ =\ \mathbb{E}A_{ij}\
\mathbb{E}B_{i^{\prime}j^{\prime}}\ =\
(1-2p_{ij})(1-2p_{i^{\prime}j^{\prime}})\ \leq(1-2q)^{2},$ (28)

the last inequality following from the Assumptions for Section 6 listed in
Section 6.1. Using Equations (27), (28), (22), and (23), we take the
expectation of $Y_{PQ}$ in Equation (12) and bound it as follows.

$\displaystyle\mathbb{E}Y_{PQ}$ $\displaystyle=$ $\displaystyle\sum_{(i,j)\in
S_{I}\backslash(S\cup S^{\prime})}\mathbb{E}A_{ij}B_{ij}\ \ \ -\sum_{(i,j)\in
S_{PQ}\backslash(S\cup
S^{\prime})}\mathbb{E}A_{ij}B_{\phi_{P}(i),\phi_{Q}(j)}$ (29)
$\displaystyle\geq$ $\displaystyle\sum_{(i,j)\in S_{I}\backslash(S\cup
S^{\prime})}\left((1-2q)^{2}+\epsilon\right)\ \ \ -\sum_{(i,j)\in
S_{PQ}\backslash(S\cup S^{\prime})}(1-2q)^{2}$ $\displaystyle\geq$
$\displaystyle\left((1-2q)^{2}+\epsilon\right)\beta-(1-2q)^{2}\gamma$
$\displaystyle=$ $\displaystyle(1-2q)^{2}(\beta-\gamma)+\epsilon\beta$
$\displaystyle=$ $\displaystyle\epsilon\beta-3(1-2q)^{2}(K-t_{PQ}).$

From (29), and the inequality (25) for $\beta$, we obtain that

$\displaystyle\mathbb{E}Y_{PQ}-\frac{\epsilon\beta}{2}$ $\displaystyle\geq$
$\displaystyle\frac{\epsilon\beta}{2}-3(K-t_{PQ})$ (30) $\displaystyle\geq$
$\displaystyle\frac{\epsilon}{2}\left(\frac{3}{4}K^{2}-3K+3t_{PQ}-\frac{Kt_{PQ}}{2}-\frac{t_{PQ}^{2}}{4}\right)-3(K-t_{PQ})$
$\displaystyle\geq$ $\displaystyle\frac{3}{8}\epsilon
K^{2}-6(K-t_{PQ})-\frac{1}{4}\epsilon Kt_{PQ}-\frac{1}{8}\epsilon t_{PQ}^{2}$

The bottom line of (30) is a concave quadratic in the variable $t_{PQ}$ hence,
when minimizing it over $t_{PQ}$ in the range of
$t_{PQ}\in\\{0,1,2,\ldots,K-1\\}$, the minimum is achieved when $t_{PQ}$ is
$0$ or $K-1$. Plugging in $0$ for $t_{PQ}$ in the bottom line of (30) yields
$\frac{3}{8}\epsilon K^{2}-6K=K(\frac{3}{8}\epsilon K-6)$, and plugging in
$K-1$ for $t_{PQ}$ in the bottom line of (30) yields an expression bounded
below by $\frac{1}{2}\epsilon K-7$. However,
$\epsilon^{2}K\in\omega(\log\mathfrak{n})$ and $\epsilon\in(0,1)$ imply that
$\epsilon K$ is greater than any particular number when $\mathfrak{n}$ is
large enough, hence for large enough $\mathfrak{n}$ we have that the
expression in (30) is positive, i.e.

$\displaystyle\mathbb{E}Y_{PQ}>\frac{\epsilon\beta}{2}.$ (31)

We are now in a position to bound $\mathbb{P}(Y_{PQ}\leq 0)$, which will be
accomplished using Theorem 5; there are a number of conditions and
requirements for Theorem 5, which we next verify as holding.

For each $i,j:1\leq i<j\leq K$, recall from the paragraph immediately
preceding Theorem 5 that the distribution of the pair of random variables
$(A_{ij},B_{ij})$ may be thought of as a function of three independent
Bernoulli random variables, one of them having Bernoulli coefficient in the
interval $[q,1-q]$. Indeed, the joint distribution of all
$A_{ij},B_{i^{\prime}j^{\prime}}$, collectively for all $i,j:1\leq i<j\leq m$
and $i^{\prime},j^{\prime}:1\leq i^{\prime}<j^{\prime}\leq n$ is thus a
function of
$3\binom{K}{2}+\left[\binom{m}{2}-\binom{K}{2}\right]+\left[\binom{n}{2}-\binom{K}{2}\right]$
collectively independent Bernoulli random variables.

Specifically, by (12), we have that $Y_{PQ}$ is a function of such independent
Bernoulli random variables which underly $A_{ij}B_{ij}$ for all $(i,j)\in
S_{I}\backslash(S\cup S^{\prime})$ and which underly
$A_{ij}B_{\phi_{P}(i),\phi_{Q}(j)}$ for all $(i,j)\in S_{PQ}\backslash(S\cup
S^{\prime})$. Let us denote by $N$ the number of these Bernoulli variables;
from (22), (23), and (24) we have that

$\displaystyle\frac{3}{2}\beta\leq N\leq 6\gamma\leq 12\beta$ (32)

(since we are allowing for three such Bernoullis for each such $(i,j)$, and
there is a $\frac{1}{2}$ in the left-hand side because the $(i,j)$ are ordered
pairs). Denote by $r_{1},r_{2},\ldots,r_{N}$ the associated Bernoulli
coefficients; at least $\frac{\beta}{2}$ of these are in the interval
$[q,1-q]$. Thus

$\displaystyle
q(1-q)\frac{\beta}{2}\leq\sum_{i=1}^{N}r_{i}(1-r_{i})\leq\sum_{i=1}^{N}\frac{1}{2}(1-\frac{1}{2})=\frac{N}{4}.$
(33)

It is easy to see that changing the realized value of any of these $N$
Bernoulli random variables (from zero to one or vice versa) can change the
realized value of $Y_{PQ}$ by at most $L:=8$; define
$\sigma:=L\sqrt{\sum_{i=1}^{N}r_{i}(1-r_{i})}$, hence
$\sigma^{2}=64\sum_{i=1}^{N}r_{i}(1-r_{i})$. Thus, by (32) and (33),
$\sigma^{2}$ satisfies

$\displaystyle 32q(1-q)\beta\ \leq\ \sigma^{2}\ \leq\ 192\beta.$ (34)

Finally, since by definition of $\epsilon$ we have $0<\epsilon\leq
1-(1-2q)^{2}$, it follows from (34) and (24) that

$\displaystyle\frac{1}{2}\sigma^{2}-\epsilon\beta$ $\displaystyle\geq$
$\displaystyle 16q(1-q)\beta-\left[1-(1-2q)^{2}\right]\beta$ $\displaystyle=$
$\displaystyle 12q(1-q)\beta>0,$

from which it immediately follows that (since $L=8$)

$\displaystyle\mbox{if we define }\tau:=\frac{\epsilon\beta}{2\sigma}\ \mbox{
then }\ \tau<2\frac{\sigma}{L}.$ (35)

We now apply Theorem 5 with $\tau:=\frac{\epsilon\beta}{2\sigma}$ and $\sigma$
as above, since the theorem conditions have just been demonstrated to apply;
there exists a positive constant $C_{1}$ (not dependent on $\mathfrak{n}$)
such that

$\displaystyle\mathbb{P}(Y_{PQ}\leq 0)$ $\displaystyle\leq$
$\displaystyle\mathbb{P}\left(|Y_{PQ}-\mathbb{E}Y_{PQ}|>\frac{\epsilon\beta}{2}\right)\
\ \ \ \ \ \ \ \mbox{by Equation (\ref{eqn:fifteen})}$ (36) $\displaystyle\leq$
$\displaystyle 2e^{-\frac{\epsilon^{2}\beta^{2}}{16\sigma^{2}}}\ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \mbox{by Theorem
\ref{thm:bound}}$ $\displaystyle\leq$ $\displaystyle
2e^{-2C_{1}\epsilon^{2}\beta}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \mbox{by Equation (\ref{eqn:twelve}})$ $\displaystyle\leq$
$\displaystyle 2e^{-C_{1}\epsilon^{2}(K-t_{PQ})(K-6)}\ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \mbox{by Equation (\ref{eqn:ten}})$

when $K>6$.

Until this point, $P$ and $Q$ have been fixed. Keep $\mathfrak{n}$ fixed. For
each $t=0,1,2,\ldots,K-1$, define ${\mathcal{E}}_{t,\mathfrak{n}}$ to be the
event that there exists an ordered pair $(P,Q)$ in the set $\Phi^{(t)}$ such
that $Y_{PQ}\leq 0$, where

$\displaystyle\Phi^{(t)}:=\Huge\\{\
(P^{\prime},Q^{\prime})\in\varPi_{m,n,K}\times\varPi_{m,n,K}\ :\
|\\{i\in[K]:\phi_{P^{\prime}}(i)=\phi_{Q^{\prime}}(i)=i\\}|=t\ \Huge\\}$

For each $t=0,1,2,\ldots,K-1$, we have that

$\displaystyle|\Phi^{(t)}|$ $\displaystyle\leq$
$\displaystyle\binom{K}{t}\left[\binom{m}{K-t}\binom{n}{K-t}(K-t)!\right]^{2}$
(37) $\displaystyle=$
$\displaystyle\frac{K!}{t!(K-t)!)}\left[\frac{m!}{(K-t)!(m-(K-t))!}\ \
\frac{n!}{(K-t)!(n-(K-t))!}\ (K-t)!\right]^{2}$ $\displaystyle\leq$
$\displaystyle K^{K-t}\left[m^{K-t}n^{K-t}\right]^{2}$ $\displaystyle\leq$
$\displaystyle\mathfrak{n}^{5(K-t)}.$

Applying (36) and (37), there exists a constant $C_{2}$ not dependent on
$\mathfrak{n}$ such that when $\mathfrak{n}$ is big enough it holds that

$\displaystyle\mathbb{P}[{\mathcal{E}}_{t,\mathfrak{n}}]$ $\displaystyle\leq$
$\displaystyle 2\ \mathfrak{n}^{5(K-t)}\ e^{-C_{1}\epsilon^{2}(K-t)(K-6)}\ \
=\ \ 2e^{5(K-t)\log\mathfrak{n}-C_{1}\epsilon^{2}(K-t)(K-6)}$ (38)
$\displaystyle=$ $\displaystyle
2e^{(K-t)\left[5\log\mathfrak{n}-C_{1}\epsilon^{2}(K-6)\right]}$
$\displaystyle\leq$ $\displaystyle 2e^{(K-t)(-C_{2}\epsilon^{2}K)}\ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \mbox{since
}\epsilon^{2}K\in\omega(\log\mathfrak{n})$ $\displaystyle\leq$ $\displaystyle
2e^{(-C_{2}\epsilon^{2}K)}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \mbox{since }K-t\geq 1$ $\displaystyle\leq$
$\displaystyle\frac{1}{\mathfrak{n}^{3}}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \mbox{since
}\epsilon^{2}K\in\omega(\log\mathfrak{n}).$

Hence, we have from (38) that

$\displaystyle\mathbb{P}\left[\bigcup_{t=0}^{K-1}{\mathcal{E}}_{t,\mathfrak{n}}\right]\
\leq K\ \frac{1}{\mathfrak{n}^{3}}\ \leq\ \frac{1}{\mathfrak{n}^{2}};$

thus, since $\sum_{\mathfrak{n}=1}^{\infty}\frac{1}{\mathfrak{n}^{2}}<\infty$,
Lemma 4 follows from applying the Borel-Cantelli Lemma to the set of events
$\\{\bigcup_{t=0}^{K-1}{\mathcal{E}}_{t,\mathfrak{n}}\\}_{\mathfrak{n}=1}^{\infty}$.
∎

##  7 Discussion, future work

The graph matching problem (as well as the many variants and generalizations)
is important because of its wide-ranging application as well as its
challenging theory and computational complexity. We provide here an efficient
and effective algorithm (ssSGM) to approximately solve the seeded subgraph-
subgraph matching problem, and we state and prove an information-theoretic
matchability result (Theorem 3) in this context.

There are a number of promising directions for further work that build on our
work here.

The seeds that are incorporated into ssSGM are vertices in the core together
with their a priori known alignments across the pair of graphs; such known
alignments are the usual definition of “seeds” in graph matching. However, in
our setting where there are core vertices and non core vertices, we might know
a priori that certain vertices are in the core, but not know their alignments.
It would be interesting to incorporate such “pre-seeds” into our subgraph-
subgraph matching problem, and compare their effectiveness to seeds in
identifying a latent matching.

Also, Theorem 3 provides (mild) sufficient conditions for matchability in our
setting, but it does not provide necessary conditions. It would be worth
extending our results to obtain necessary and sufficient conditions (up to
order). In particular, the “total correlation” (a measurement of correlation
between a pair of graphs) introduced in [16] and [14] combines the edge
correlation together with the Bernoulli coefficients, and was demonstrated to
be an extremely effective tool for determining matchability. Their random
pair-of-graphs model was less general than ours here, but sets forward an
promising tool to achieve necessary and sufficent conditions.

## References

  * [1] László Babai.  Graph isomorphism in quasipolynomial time.  In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 684–697, 2016.
  * [2] Serhat Bakirtas and Elza Erkip.  Seeded database matching under noisy column repetitions.  In 2022 IEEE Information Theory Workshop (ITW), pages 386–391. IEEE, 2022.
  * [3] Hongkai Chen, Zixin Luo, Jiahui Zhang, Lei Zhou, Xuyang Bai, Zeyu Hu, Chiew-Lan Tai, and Long Quan.  Learning to match features with seeded graph matching network.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 6301–6310, 2021.
  * [4] Carla-Fabiana Chiasserini, Michel Garetto, and Emili Leonardi.  De-anonymizing clustered social networks by percolation graph matching.  ACM Transactions on Knowledge Discovery from Data (TKDD), 12(2):1–39, 2018.
  * [5] Donatello Conte, Pasquale Foggia, Carlo Sansone, and Mario Vento.  Thirty years of graph matching in pattern recognition.  International journal of pattern recognition and artificial intelligence, 18(03):265–298, 2004.
  * [6] COSN Proc. of the first ACM Conf. on Online social networks.  On the performance of percolation graph matching, 2013.
  * [7] D. Cullina and N. Kiyavash.  Improved achievability and converse bounds for erdos-renyi graph matching.  In ACM SIGMETRICS Performance Evaluation Review, volume 44 (1), pages 63–72. ACM, 2016.
  * [8] D. Cullina and N. Kiyavash.  Exact alignment recovery for correlated erdos renyi graphs.  arXiv preprint arXiv:1711.06783, 2017.
  * [9] Daniel Cullina, Negar Kiyavash, Prateek Mittal, and H Vincent Poor.  Partial recovery of erdős-rényi graph alignment via k-core alignment.  Proceedings of the ACM on Measurement and Analysis of Computing Systems, 3(3):1–21, 2019.
  * [10] Marco Cuturi.  Sinkhorn distances: Lightspeed computation of optimal transport.  Advances in neural information processing systems, 26, 2013.
  * [11] Jian Ding and Hang Du.  Detection threshold for correlated erdös-rényi graphs via densest subgraph.  IEEE Transactions on Information Theory, 2023.
  * [12] F. Emmert-Streib, M. Dehmer, and Y. Shi.  Fifty years of graph matching, network alignment and network comparison.  Information sciences, 346–347:180–197, 2016.
  * [13] Fei Fang, Daniel L Sussman, and Vince Lyzinski.  Tractable graph matching via soft seeding.  arXiv preprint arXiv:1807.09299, 2018.
  * [14] D. E. Fishkind, F. Parker, H. Sawczuk, L. Meng, E. Bridgeford, A. Athreya, C. Priebe, and V. Lyzinski.  The phantom alignment strength conjecture: practical use of graph matching alignment strength to indicate a meaningful graph match.  Applied Network Science, 6(1):1–27, 2021.
  * [15] Donniell E Fishkind, Sancar Adali, Heather G Patsolic, Lingyao Meng, Digvijay Singh, Vince Lyzinski, and Carey E Priebe.  Seeded graph matching.  Pattern recognition, 87:203–215, 2019.
  * [16] Donniell E. Fishkind, Lingyao Meng, Ao Sun, Carey E. Priebe, and Vince Lyzinski.  Alignment strength and correlation for graphs.  Pattern Recognition Letters, 125:295–302, 2019.
  * [17] P. Foggia, G. Percannella, and M. Vento.  Graph matching and learning in pattern recognition in the last 10 years.  International Journ. of Pattern Recognition and Artificial Intelligence, 28(01):1450001, 2014.
  * [18] M. Frank and P. Wolfe.  An algorithm for quadratic programming.  Naval Research Logistics Quarterly, 3(1-2):95–110, 1956.
  * [19] Shang Gao, Jingya Wang, Huchuan Lu, and Zimo Liu.  Pose-guided visible part matching for occluded person reid.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 11744–11752, 2020.
  * [20] Jonna Gill and Svante Linusson.  The k-assignment polytope.  Discrete Optimization, 6(2):148–161, 2009.
  * [21] Georgina Hall and Laurent Massoulié.  Partial recovery in the graph alignment problem.  Operations Research, 71(1):259–272, 2023.
  * [22] 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, pages 117–126, 2018.
  * [23] R. Jonker and A. Volgenant.  A shortest augmenting path algorithm for dense and sparse linear assignment problems.  Computing, 38(4):325–340, 1987.
  * [24] KDD Proc. of the 17th ACM SIGKDD international Conf. on Knowledge discovery and data mining.  On the privacy of anonymized networks, 2011.
  * [25] J. H. Kim, B. Sudakov, and V. H. Vu.  On the asymmetry of random regular graphs and random graphs.  Random Structures and Algorithms, 21:216–224, 2002.
  * [26] Gunnar W Klau.  A new graph-based method for pairwise global network alignment.  BMC bioinformatics, 10(1):1–9, 2009.
  * [27] H. W. Kuhn.  The Hungarian method for the assignment problem.  Naval Research Logistic Quarterly, 2:83–97, 1955.
  * [28] Zhi Liang, Meng Xu, Maikun Teng, and Liwen Niu.  Netalign: a web-based tool for comparison of protein interaction networks.  Bioinformatics, 22(17):2175–2177, 2006.
  * [29] Chung-Shou Liao, Kanghao Lu, Michael Baym, Rohit Singh, and Bonnie Berger.  Isorankn: spectral methods for global alignment of multiple protein networks.  Bioinformatics, 25(12):i253–i258, 2009.
  * [30] V. Lyzinski.  Information recovery in shuffled graphs via graph matching.  IEEE Trans. on Information Theory, 64(5):3254–3273, 2018.
  * [31] V. Lyzinski, D. Fishkind, M. Fiori, J.T. Vogelstein, C.E. Priebe, and G. Sapiro.  Graph matching: Relax at your own risk.  IEEE Trans. on Pattern Analysis and Machine Intelligence, 38(1):60–73, 2015.
  * [32] V. Lyzinski, D.E. Fishkind, and C.E. Priebe.  Seeded graph matching for correlated Erdös-Rényi graphs.  Journ. of Mach. Learn. Res., 15:3513–3540, 2014.
  * [33] N.S. Mendelsohn and Dulmage A.L.  The convex hull of sub-permutation matrices.  Proc. Amer. Math. Soc., 9:253–254, 1958.
  * [34] J. D. Moorman, Q. Chen, T. K. Tu, Z. M. Boyd, and A. L. Bertozzi.  Filtering methods for subgraph matching on multiplex networks.  In 2018 IEEE International Conf. on Big Data (Big Data), pages 3980–3985. IEEE, 2018.
  * [35] J. D. Moorman, T. Tu, Q. Chen, X. He, and A. Bertozzi.  Subgraph matching on multiplex networks.  IEEE Trans. on Network Science and Engineering, 2021.
  * [36] Elchanan Mossel and Jiaming Xu.  Seeded graph matching via large neighborhood statistics.  Random Structures & Algorithms, 57(3):570–611, 2020.
  * [37] Behnam Neyshabur, Ahmadreza Khadem, Somaye Hashemifar, and Seyed Shahriar Arab.  Netal: a new graph-based method for global alignment of protein–protein interaction networks.  Bioinformatics, 29(13):1654–1662, 2013.
  * [38] Heather Patsolic, Sancar Adali, Joshua T Vogelstein, Youngser Park, Carey E Friebe, Gongkai Li, and Vince Lyzinski.  Seeded graph matching via joint optimization of fidelity and commensurability.  Arxiv preprint at http://arxiv.org/abs/1401.3813, 2014.
  * [39] Heather G Patsolic, Youngser Park, Vince Lyzinski, and Carey E Priebe.  Vertex nomination via seeded graph matching.  Statistical Analysis and Data Mining: The ASA Data Science Journal, 13(3):229–244, 2020.
  * [40] Benjamin D Pedigo, Michael Winding, Carey E Priebe, and Joshua T Vogelstein.  Bisected graph matching improves automated pairing of bilaterally homologous neurons from connectomes.  Network Neuroscience, pages 1–29, 2022.
  * [41] Ali Saad-Eldin, Benjamin D Pedigo, Carey E Priebe, and Joshua T Vogelstein.  Graph matching via optimal transport.  arXiv preprint arXiv:2111.05366, 2021.
  * [42] F. Shirani, S. Garg, and E. Erkip.  Seeded graph matching: Efficient algorithms and theoretical guarantees.  2017 51st Asilomar Conference on Signals, Systems, and Computers, pages 253–257, 2017.
  * [43] Hui Sun, Wenju Zhou, and Minrui Fei.  A survey on graph matching in computer vision.  In 2020 13th International Congress on Image and Signal Processing, BioMedical Engineering and Informatics (CISP-BMEI), pages 225–230. IEEE, 2020.
  * [44] Zhao Sun, Hongzhi Wang, Haixun Wang, Bin Shao, and Jianzhong Li.  Efficient subgraph matching on billion node graphs.  arXiv preprint arXiv:1205.6691, 2012.
  * [45] D. L. Sussman, V. Lyzinski, Y. Park, and C. E. Priebe.  Matched filters for noisy induced subgraph detection.  IEEE Trans. on Pattern Analysis and Machine Intelligence, 42(11):2887–2900, 2019.
  * [46] J. T. Vogelstein, J. M. Conroy, V. Lyzinski, L. J. Podrazik, S. G. Kratzer, E. T. Harley, D. E. Fishkind, R. T. Vogelstein, and C. E. Priebe.  Fast Approximate Quadratic Programming for Graph Matching.  PLoS ONE, 10(04), 2014.
  * [47] Y. Wu, J. Xu, and S. H. Yu.  Settling the sharp reconstruction thresholds of random graph matching.  arXiv preprint arXiv:2102.00082, 2021.
  * [48] Dominic Yang, Yurun Ge, Thien Nguyen, Denali Molitor, Jacob D Moorman, and Andrea L Bertozzi.  Structural equivalence in subgraph matching.  IEEE Transactions on Network Science and Engineering, 2023.
  * [49] Liren Yu, Jiaming Xu, and Xiaojun Lin.  Graph matching with partially-correct seeds.  The Journal of Machine Learning Research, 22(1):12829–12882, 2021\.
  * [50] Mikhail Zaslavskiy, Francis Bach, and Jean-Philippe Vert.  Global alignment of protein–protein interaction networks by graph matching methods.  Bioinformatics, 25(12):i259–1267, 2009.
  * [51] 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, pages 1345–1354, 2016.
  * [52] Zhen Zhang, Yijian Xiang, Lingfei Wu, Bing Xue, and Arye Nehorai.  Kergm: Kernelized graph matching.  Advances in Neural Information Processing Systems, 32, 2019.
  * [53] Yali Zheng, Lili Pan, Jiye Qian, and Hongliang Guo.  Fast matching via ergodic markov chain for super-large graphs.  Pattern Recognition, 106:107418, 2020.
  * [54] Feng Zhou and Fernando De la Torre.  Factorized graph matching.  In 2012 IEEE Conference on Computer Vision and Pattern Recognition, pages 127–134. IEEE, 2012.

##  Appendix A Proof of Lemma 2

Proof of Lemma 2: Suppose $c,d,e$ are any positive integers such that
$e\leq\min\\{c,d\\}$, and consider any particular $M\in\mathbb{R}^{c\times
d}$. Let $\underline{\xi}$ be any real number less than all of the entries of
$M$, and let $\overline{\xi}$ be any real number greater than all of the
entries of $M$. Define the matrix
$\mathcal{M}\in\mathbb{R}^{(c+d-e)\times(c+d-e)}$ such that
$\mathcal{M}=\bigl{[}\begin{smallmatrix}M&\overline{\xi}E_{c\times(c-e)}\\\
\overline{\xi}E_{(d-e)\times d}&\ \
\underline{\xi}E_{(d-e)\times(c-e)}\end{smallmatrix}\bigr{]}$, where $E$ is a
matrix of all $1$s, sized per subscript.
Consider the linear assignment problem
$\max_{{\mathcal{X}}\in\varPi_{c+d-e,c+d-e,c+d-e}}\textup{trace}\mathcal{M}^{T}{\mathcal{X}}$,
and also any solution $\mathcal{X}\in\varPi_{c+d-e,c+d-e,c+d-e}$, say it is
partitioned as
${\mathcal{X}}=\bigl{[}\begin{smallmatrix}{\mathcal{X}}^{(11)}&{\mathcal{X}}^{(12)}\\\
{\mathcal{X}}^{(21)}&{\mathcal{X}}^{(22)}\end{smallmatrix}\bigr{]}$, where
${\mathcal{X}}^{(11)},{\mathcal{X}}^{(12)},{\mathcal{X}}^{(21)},{\mathcal{X}}^{(22)}$
are respectively of sizes $c\times d$, and $c\times(c-e)$, and $(d-e)\times
d$, and $(d-e)\times(c-e)$. If $\overline{\xi}$ is great enough, then it is
clear that ${\mathcal{X}}^{(12)}$ must have a $1$ in each of its $c-e$
columns, and in $c-e$ of its $c$ rows, with the same constant contribution of
$\overline{\xi}(c-e)$ to the objective function value without regard for which
$e$ of its rows do not have $1$s. Similarly, ${\mathcal{X}}^{(21)}$ must have
a $1$ in each of its $d-e$ rows, and in $d-e$ of its $d$ columns, with the
same constant contribution of $\overline{\xi}(d-e)$ to the objective function
value without regard for which $e$ of its columns do not have $1$s. Thus
${\mathcal{X}}^{(22)}$ is all zeros, and ${\mathcal{X}}^{(11)}$ is in
$\varPi_{c,d,e}$. Ignoring a constant translation of the objective function
value by $\overline{\xi}(c-e+d-e)$, we thus have that the optimization problem
is equivalent to the generalized linear assignment problem
$\max_{X\in\varPi_{c,d,e}}\textup{trace}M^{T}X$, whose solution is
${\mathcal{X}}^{(11)}$ in the solution ${\mathcal{X}}$ of the former problem.
Now, simple algebra demonstrates that the above analysis applies equally well
as long as $\overline{\xi}$ is greater than all of the values of $M$, and the
result is shown. ∎