#  The Phantom Alignment Strength Conjecture: Practical use of graph matching
alignment strength to indicate a meaningful graph match

D.E.Donniell E. Fishkind  F.Felix Parker  H.Hamilton Sawczuk  L.Lingyao Meng
E.Eric Bridgeford  A.Avanti Athreya  C.E.Carey Priebe  V.P.Vince Lyzinski
Department of Applied Mathematics and Statistics, Johns Hopkins University,
Baltimore, MD  Center for Systems Science and Engineering, Johns Hopkins
University, Baltimore, MD  Department of Biostatistics, Johns Hopkins
University, Baltimore, MD  Department of Mathematics , University of Maryland,
College Park, College Park, MD

###### Abstract

The alignment strength of a graph matching is a quantity that gives the
practitioner a measure of the correlation of the two graphs, and it can also
give the practitioner a sense for whether the graph matching algorithm found
the true matching. Unfortunately, when a graph matching algorithm fails to
find the truth because of weak signal, there may be “phantom alignment
strength” from meaningless matchings that, by random noise, have fewer
disagreements than average (sometimes substantially fewer); this alignment
strength may give the misleading appearance of significance. A practitioner
needs to know what level of alignment strength may be phantom alignment
strength and what level indicates that the graph matching algorithm obtained
the true matching and is a meaningful measure of the graph correlation. The
Phantom Alignment Strength Conjecture introduced here provides a principled
and practical means to approach this issue. We provide empirical evidence for
the conjecture, and explore its consequences.

graph matching,

alignment strength,

graph correlation,

###### keywords:

Research

##  1 Introduction

This paper is about graph matchability in practice. Specifically, when given
two graphs and an unobserved “true” bijection (also called “true matching” or
“true alignment”) between their vertices, will exact (i.e. optimal) graph
matching and approximate graph matching algorithms provide us with the
matching which is the “truth”? How might we know in actual practice whether
the “truth” has been found? Our work is in response to the latter question.
The main contribution here is our formulation of the Phantom Alignment
Strength Conjecture in Section 4, followed up in Section 4 with the practical
implications of this conjecture in deciding when alignment strength is high
enough to indicate truth. This conjecture is also interesting as a theoretical
matter, completely aside from its consequences.

Graphs (networks) are a commonly used data modality for encoding
relationships, interactions, and dependencies in data in an incredibly broad
range of the sciences and engineering; this includes sociology (e.g., social
network analysis [1]), neuroscience connectomics [2, 3], biology (e.g.,
biological interaction networks [4, 5]), and automated knowledge discovery
[6], to name just a few application areas.

The graph matching problem is, given two graphs with the same number of
vertices, to find the bijection between the vertex sets that minimizes the
number of adjacency “disagreements” between the graphs. Often there is an
underlying “true” bijection that the graph matching is attempting to
recover/approximate. Sometimes part of this true bijection is known a-priori,
in which case minimizing the number of disagreements over the remainder of the
bijection is called seeded graph matching. Graph matching and seeded graph
matching are formally defined in Section 2.

Graph matching and seeded graph matching are used in a wide variety of places,
and we mention just a few. Information about the interactions amongst objects
of interest is sometimes split across multiple networks or multiple layers of
the same network [7]. In many applications, such as neuroscience connectomics
where, for example, DT-MRI derived graphs can be generated by aligning scans
to a common template before uncovering the underlying edge structure [8], the
vertices across networks or across layers are a priori aligned and identified.
These aligned vertex labels can then be used to create joint network inference
procedures that can leverage the signal across multiple networks for more
powerful statistical inference [9, 10, 11, 12]. In many other applications,
the vertex labels across networks or across layers are unknown or noisily
observed. Social networks provide a canonical example of this, where common
users across different social network platforms may use different user names
and their user profiles may not be linked across networks. Discovering this
latent correspondence (in the social network example, this is anchoring
profiles to a common user across networks) is a key inference task [13, 14]
for leveraging the information across networks for subsequent inference, and
it is a key consideration for understanding the degree of user anonymity [15]
across platforms.

For a thorough survey of the relevant graph matching literature, see [16, 17,
18].

The graph matching problem is computationally complex. Indeed, the simpler
graph isomorphism problem has been shown to be of quasi-polynomial complexity
[19]. Allowing loopy, weighted, directed graphs makes graph matching
equivalent to the NP-hard quadratic assignment problem. Due to its practical
importance and computational difficulty, a large branch of the graph matching
literature is devoted to developing algorithms to efficiently, but
approximately, solve the graph matching problem; see, for example, [20, 21,
22, 23, 24, 25, 26, 27, 28] among myriad others.

Somewhat dual to the algorithmic development literature, a large branch of the
modern graph matching literature is devoted to theoretically exploring the
question of graph matchability, also called graph de-anonymization; this is
the question of determining when there is enough signal present for graph
matching to recover the “true” bijection. Many of the recent papers in this
area have introduced latent alignment across graphs by correlating the edges
across networks between common pairs of vertices, focusing on understanding
the phase transition between matchable and non-matchable networks in terms of
the level of correlation across networks and/or the sparsity level of the
networks; see, for example, [29, 30, 31, 32, 33, 34, 35, 36, 37, 38].

In [39], a novel measure of graph correlation between two random graphs called
total correlation is introduced; it is neatly partitioned into an inter-graph
contribution (the “edge correlation” that had been the previous focus in the
literature) and a novel intra-graph contribution. Furthermore, they introduce
a statistic called alignment strength, which is $1$ minus a normalized count
of the number of disagreements in an optimal/true graph match; they prove
under mild conditions that alignment strength is a strongly consistent
estimator of total correlation. Experimental results in [39] suggest that the
matchability phase transition, as well as the complexity of the problem, is a
function of this more nuanced total correlation rather than simply the cross-
graph edge correlation/edge sparsity that had been the previous focus in the
literature.

Analyses mining the matchability phase transition in the literature that also
have considered similarity across generative network models beyond simple
sparsity have thus far focused on simple community-structured network models
[40, 41, 42], or have proceeded by removing the heterogeneous within-graph
model information and simply using the across graph edge correlation [43].
Recently, there have been numerous papers in the literature at the interface
between algorithm development and mining matchability phase-transitions; see,
for instance, [44, 38, 37]. A common theme of many of these results is that,
under assumptions on the across graph edge-correlation and network sparsity,
algorithms are designed to efficiently (or approximately efficiently) match
graphs with corresponding theoretical guarantees on the performance of the
algorithms in recovering the latent alignment.

However, the question remains how a practitioner knows in practice whether or
not a graph matching has successfully recovered the truth. This issue is not
resolved by asymptotic analysis with hidden constants. Nor, in general, are
the underlying parameters known to the practitioner. It seems that the graph
alignment statistic is a very natural metric to use in deciding if the truth
is found. Unfortunately, when there is an absence of signal, an optimal (or
approximately optimal) graph matching will find spurious and random alignment
strength due to chance. Indeed, this meaningless alignment strength can be
high and misleading. How do we gauge whether or not it is high enough to
signal that truth is found?

After formally defining seeded graph matching and alignment strength in
Section 2 and defining the correlated Bernoulli random graph model (and
attendant parameters) in Section 3, we then address this issue with our
Phantom Alignment Strength Conjecture in Section 4, and in the ensuing
discussion in Section 4. Then, in Section 5, we present empirical evidence for
the conjecture using synthetic and real data, and comparing to theoretical
results; Section 5 begins with a thorough summary. This is followed in Section
6 by notable mentions, and future directions.

##  2 Seeded graph matching, alignment strength

In the seeded graph matching setting, we are given two simple graphs, say they
are $G_{1}=(V_{1},E_{1})$ and $G_{2}=(V_{2},E_{2})$, such that
$|V_{1}|=|V_{2}|$, denote the number of vertices $\mathfrak{n}:=|V_{1}|$. Let
$\varPi$ denote the set of all bijections $V_{1}\rightarrow V_{2}$. It is
usually understood that there exits a “true” bijection $\varphi^{*}\in\varPi$
which represents a natural correspondence between the vertices in $V_{1}$ and
the vertices in $V_{2}$; for example, $V_{1}$ and $V_{2}$ might be the same
people, with $E_{1}$ indicating which pairs exchanged emails and $E_{2}$
indicating pairs that communicated in a different medium. Or $G_{1}$ may be
the electrical connectome (brain graph) of a worm and $G_{2}$ might be the
chemical connectome of the same worm, both graphs sharing the same vertex set
of neurons. The vertex set $V_{1}$ is partitioned into two disjoint sets,
${\mathcal{S}}$ “seeds” (possibly empty) and ${\mathcal{N}}$ “nonseeds,”
denote $s:=|{\mathcal{S}}|$ and $n:=|{\mathcal{N}}|$. (When $s=0$ this is the
conventional graph matching problem.) The graphs $G_{1}$ and $G_{2}$ are
observed, and the values of $\varphi^{*}$ are observed on the set of seeds
${\mathcal{S}}$, however the values of $\varphi^{*}$ are not observed on the
nonseeds ${\mathcal{N}}$, and one of several important tasks is to estimate
$\varphi^{*}$.

Let $\varPi^{S}$ denote the set of all bijections $V_{1}\rightarrow V_{2}$
that agree with $\varphi^{*}$ on the seeds ${\mathcal{S}}$. For any
$\varphi\in\varPi^{S}$, its match ratio is defined to be
$\frac{1}{n}|\\{v\in{\mathcal{N}}:\varphi(v)=\varphi^{*}(v)\\}|$, i.e. the
fraction of the nonseeds that are correctly matched by $\varphi$. (It is
common to multiply the match ratio by $100$ to express it as a percentage.)

For any set $V$, let ${V\choose 2}$ denote the set of two-element subsets of
$V$; for each $i=1,2$ and any $\\{u,v\\}\in{V_{i}\choose 2}$ let
$u\sim_{G_{i}}v$ and $u\not\sim_{G_{i}}v$ denote adjacency and, respectively,
nonadjacency of $u$ and $v$ in $G_{i}$. Next, let $\mathbbm{1}$ denote the
indicator function for its subscript. Given any $\varphi\in\varPi$, we define
the full number of disagreements through $\varphi$ to be

$\displaystyle\mathcal{D}^{\prime}(\varphi):=\sum_{\\{u,v\\}\in{V_{1}\choose
2}}\left(\mathbbm{1}_{[u\sim_{G_{1}}v]\wedge[\varphi(u)\not\sim_{G_{2}}\varphi(v)]}+\mathbbm{1}_{[u\not\sim_{G_{1}}v]\wedge[\varphi(u)\sim_{G_{2}}\varphi(v)]}\right)$
(1)

and, given any $\varphi\in\varPi^{S}$, we define the restricted number of
disagreements through $\varphi$ to be

$\displaystyle\mathcal{D}(\varphi):=\sum_{\\{u,v\\}\in{{\mathcal{N}}\choose
2}}\left(\mathbbm{1}_{[u\sim_{G_{1}}v]\wedge[\varphi(u)\not\sim_{G_{2}}\varphi(v)]}+\mathbbm{1}_{[u\not\sim_{G_{1}}v]\wedge[\varphi(u)\sim_{G_{2}}\varphi(v)]}\right).$
(2)

The seeded graph matching problem is to find

$\displaystyle\hat{\varphi}\in\arg\min_{\varphi\in\varPi^{S}}\mathcal{D}^{\prime}(\varphi),$
(3)

and the idea is that $\hat{\varphi}$ is an estimate for the true bijection
$\varphi^{*}$. Unfortunately, except in the smallest instances, computing
$\hat{\varphi}$ is intractable. A state-of-the-art algorithm SGM from [20] is
commonly used to approximately solve the optimization problem in (3), and we
denote its output $\hat{\varphi}_{\textup{SGM}}\ (\in\varPi^{S})$, and it is
an approximation of $\hat{\varphi}$ and, hence, an approximation of
$\varphi^{*}$. For any $\varphi\in\varPi^{S}$, the full alignment strength
$\mathfrak{str}^{\prime}(\varphi)$ and the restricted alignment strength
$\mathfrak{str}(\varphi)$ are defined as

$\displaystyle\mathfrak{str}^{\prime}(\varphi):=1-\frac{\mathcal{D}^{\prime}(\varphi)}{\frac{1}{\mathfrak{n}!}\sum_{\phi\in\varPi}\mathcal{D}^{\prime}(\phi)}\
\ \ \mbox{ and }\ \ \
\mathfrak{str}(\varphi):=1-\frac{\mathcal{D}(\varphi)}{\frac{1}{n!}\sum_{\phi\in\varPi^{S}}\mathcal{D}(\phi)}.$
(4)

Although the denominators of (4) have exponentially many summands, alignment
strength is easily computed as follows. For $i=1,2$, define the full density
of $G_{i}$ as $\mathfrak{d}^{\prime}G_{i}:=\frac{|E_{i}|}{{\mathfrak{n}\choose
2}}$ and the restricted density of $G_{i}$ as $\mathfrak{d}G_{i}=$ the number
of edges of $G_{i}$ induced by ${\mathcal{N}}$, divided by ${n\choose 2}$. It
holds that

$\displaystyle\mathfrak{str}^{\prime}(\varphi)$ $\displaystyle=$
$\displaystyle 1-\frac{\mathcal{D}^{\prime}(\varphi)/{\mathfrak{n}\choose
2}}{\mathfrak{d}^{\prime}G_{1}(1-\mathfrak{d}^{\prime}G_{2})+(1-\mathfrak{d}^{\prime}G_{1})\mathfrak{d}^{\prime}G_{2}}\
\ \ \mbox{ and }$ $\displaystyle\mathfrak{str}(\varphi)$ $\displaystyle=$
$\displaystyle 1-\frac{\mathcal{D}(\varphi)/{n\choose
2}}{\mathfrak{d}G_{1}(1-\mathfrak{d}G_{2})+(1-\mathfrak{d}G_{1})\mathfrak{d}G_{2}};$
(5)

see [39] for the derivation of (5) from (4).

The importance of alignment strength to a practitioner is twofold:

First, the alignment strength of $\varphi^{*}$ (and its proxies
$\hat{\varphi}$ and $\hat{\varphi}_{\textup{SGM}}$) may be thought of as a
measure of how similar the structure of the graphs $G_{1}$ and $G_{2}$ are
through the “true” bijection; indeed, if the number of disagreements under
$\varphi^{*}$ (and its proxies $\hat{\varphi}$ and
$\hat{\varphi}_{\textup{SGM}}$) is about equal to the average over all
bijections then its alignment strength is near $0$ (as clearly seen from the
definition in (4)) and, at the other extreme, if $\varphi^{*}$ (and its
proxies $\hat{\varphi}$ and $\hat{\varphi}_{\textup{SGM}}$) is nearly an
isomorphism between $G_{1}$ and $G_{2}$ then its alignment strength is near
$1$. It was proven in [39] that the full alignment strength of the “true”
bijection $\mathfrak{str}^{\prime}(\varphi^{*})$ is a strongly consistent
estimator of $\varrho_{T}$, which is a parameter called the total correlation
between the two graphs $G_{1}$ and $G_{2}$, defined in Section 3.

Another way that alignment strength is of much importance to a practitioner is
in providing confidence that $\hat{\varphi}_{\textup{SGM}}$ or $\hat{\varphi}$
is a good estimate of $\varphi^{*}$, the “truth.” If
$\mathfrak{str}(\hat{\varphi}_{\textup{SGM}})$ or
$\mathfrak{str}(\hat{\varphi})$ is high enough then we may be confident that a
meaningful match capturing similar graph structure has been found, and
therefore $\hat{\varphi}_{\textup{SGM}}$ or $\hat{\varphi}$ is approximately
or exactly $\varphi^{*}$. But, how high is high enough?

Indeed, these issues in the use of alignment strength become vastly more
complicated by the possibility of phantom alignment strength. This is a
phenomenon that occurs when, in the presence of weak signal, meaningless
matchings have many fewer disagreements than average (sometimes very
substantially fewer) due to random noise, and $\hat{\varphi}$ and/or
$\hat{\varphi}_{\textup{SGM}}$ is one of these meaningless matchings—optimal
in the optimization problem, but meaningless as estimates of $\varphi^{*}$.
Indeed, the alignment strength of $\hat{\varphi}$ and/or
$\hat{\varphi}_{\textup{SGM}}$ may be elevated enough to give the misleading
appearance of significance when, in reality, they don’t at all resemble
$\varphi^{*}$. This will be illustrated in Section 5.

The purpose of this paper is to give a principled, practical means of
approaching the decision of what level of alignment strength for
$\hat{\varphi}$ and/or $\hat{\varphi}_{\textup{SGM}}$ indicates that they are
a good approximation of $\varphi^{*}$, in which case the alignment strength
reflects the amount of meaningful similar structure between $G_{1}$ and
$G_{2}$ —beyond the random similarity between completely unrelated graphs.

(A note on terminology: We define both full alignment strength and restricted
alignment strength since each will end up being important at a different time.
The Phantom Alignment Strength Conjecture of Section 4 requires restricted
alignment strength specifically; indeed, since full alignment strength
includes the seeds, this would dilute the desired effect, falsifying the
conjecture conclusion. However, after we have confidence that our graph
matching is the true matching, it is then full alignment strength that will be
a better estimator of total correlation introduced in Section 3.)

##  3 The correlated Bernoulli random graph model

######  Definition 1.

Given positive integer $\mathfrak{n}$, vertex set $V$ such that
$|V|=\mathfrak{n}$, the parameters of the correlated Bernoulli random graph
model are Bernoulli parameters $p_{\\{u,v\\}}\in[0,1]$ for each
$\\{u,v\\}\in{V\choose 2}$, and an edge correlation parameter
$\varrho_{e}\in[0,1]$. The pair of random graphs $(G_{1},G_{2})$ have a
correlated Bernoulli random graph distribution when as follows: $G_{1}$ and
$G_{2}$ each have vertex set $V$. For each $\\{u,v\\}\in{V\choose 2}$, and
each $i=1,2$, the probability of $u\sim_{G_{i}}v$ is the Bernoulli parameter
$p_{\\{u,v\\}}$, and the Pearson correlation for random variables
$\mathbbm{1}_{v\sim_{G_{1}}w}$ and $\mathbbm{1}_{v\sim_{G_{2}}w}$ is the edge
correlation parameter $\varrho_{e}$. Other than these dependencies, the rest
of the adjacencies are independent.

The distribution of the pair of random graphs $G_{1},G_{2}$ is determined by
the above (see [39]). Of course, the identity function is the “true” matching
$\varphi^{*}$ between $G_{1}$ and $G_{2}$.

(If the Bernoulli parameters are all equal, then the random graphs $G_{1}$ and
$G_{2}$ are each said to be Erdos-Renyi, so the correlated Erdos-Renyi random
graph model is a special case of the correlated Bernoulli random graph model.)

Important functions of the model parameters are as follows. The Bernoulli mean
and Bernoulli variance are, respectively, defined as

$\displaystyle\mu:=\frac{\sum_{\\{u,v\\}\in{V\choose
2}}p_{\\{u,v\\}}}{{\mathfrak{n}\choose 2}},\ \ \ \
\sigma^{2}:=\frac{\sum_{\\{u,v\\}\in{V\choose
2}}(p_{\\{u,v\\}}-\mu)^{2}}{{\mathfrak{n}\choose 2}}.$

Assume that $\mu$ is not equal to $0$ nor $1$. The heterogeneity correlation
is defined in [39] as

$\displaystyle\varrho_{h}:=\frac{\sigma^{2}}{\mu(1-\mu)};$ (6)

it is in the unit interval $[0,1]$; see [39]. Also pointed out in [39] is that
$\varrho_{h}$ is $0$ if and only if all Bernoulli parameters are equal (i.e.
the graphs are Erdos-Renyi) and $\varrho_{h}$ is $1$ if and only if all
Bernoulli parameters are $\\{0,1\\}$-valued. In particular, if $\varrho_{h}$
is $1$ then $G_{1}$ and $G_{2}$ are almost surely isomorphic. The total
correlation $\varrho_{T}$ is defined in [39] to satisfy the relationship

$\displaystyle(1-\varrho_{T})=(1-\varrho_{h})(1-\varrho_{e}).$ (7)

In the following key result, Theorem 1, which was proved in [39], let us
consider a probability space that incorporates correlated Bernoulli random
graph distributions for each of the number of vertices
$\mathfrak{n}=1,2,3,\ldots$. Thus, the parameters are functions of
$\mathfrak{n}$, but to prevent notation clutter we omit notating the
dependence on $\mathfrak{n}$. The symbol $\stackrel{{\scriptstyle
a.s.}}{{\rightarrow}}$ denotes almost sure convergence.

######  Theorem 1.

Suppose $\mu$ is bounded away from $0$ and $1$, over all $\mathfrak{n}$. Then
it holds that
$\mathfrak{str}^{\prime}(\varphi^{*})-\varrho_{T}\stackrel{{\scriptstyle
a.s.}}{{\rightarrow}}0$.

Theorem 1 together with Equation 7 shows that the alignment strength of the
true bijection captures (asymptotically) an underlying correlation between the
random graphs that can be neatly (and symmetrically, per Equation 7)
partitioned into a inter-graph contribution (edge correlation) and an intra-
graph contribution (heterogeneity correlation).

Next, instead of considering a sequence of correlated Bernoulli random graphs,
let us dig down deeper one probabilistic level. Specifically, suppose that for
each $\\{u,v\\}\in{V\choose 2}$ there exists an interval-$[0,1]$-valued
distribution $F_{\\{u,v\\}}$ such that the Bernoulli parameter $p_{\\{u,v\\}}$
(in the correlated Bernoulli random graph model) is an independent random
variable with distribution $F_{\\{u,v\\}}$. Denote the mean of this
distribution $\mu_{F_{\\{u,v\\}}}$, denote the variance of this distribution
$\sigma^{2}_{F_{\\{u,v\\}}}$, and (if we have $\mu_{F_{\\{u,v\\}}}$ not $0$
nor $1$) define the heterogeneity correlation of the distribution to be

$\displaystyle\varrho_{F_{\\{u,v\\}}}:=\frac{\sigma^{2}_{F_{\\{u,v\\}}}}{\mu_{F_{\\{u,v\\}}}(1-\mu_{F_{\\{u,v\\}}})}\
\ .$ (8)

######  Theorem 2.

Given an edge correlation parameter $\varrho_{e}\in[0,1]$ and, for each
$\\{u,v\\}\in{V\choose 2}$, given a $[0,1]$-valued distribution
$F_{\\{u,v\\}}$ such that the Bernoulli parameter $p_{\\{u,v\\}}$ is
independently distributed as $F_{\\{u,v\\}}$, then the distribution of the
associated correlated Bernoulli random graphs $(G_{1},G_{2})$ is completely
specified by $\varrho_{e}$ and, for all $\\{u,v\\}\in{V\choose 2}$, the values
of $\mu_{F_{\\{u,v\\}}}$ and $\varrho_{F_{\\{u,v\\}}}$.

Proof: Consider any $\\{u,v\\}\in{V\choose 2}$; the Bernoulli coefficient
$p_{\\{u,v\\}}$, call it $X$, has distribution $F_{\\{u,v\\}}$. For any
$p\in[0,1]$, conditioning on $X=p$, the joint probabilities of combinations of
$u,v$ adjacency in $G_{1},G_{2}$ are computed in a straightforward way (see
[39] Appendix A) in the table:

$\displaystyle\begin{array}[]{c||cc}&u\sim_{G_{2}}v&u\not\sim_{G_{2}}v\\\
\hline\cr\hline\cr
u\sim_{G_{1}}v&p^{2}+\varrho_{e}p(1-p)&(1-\varrho_{e})p(1-p)\\\
u\not\sim_{G_{1}}v&(1-\varrho_{e})p(1-p)&(1-p)^{2}+\varrho_{e}p(1-p)\end{array}$
(12)

Probabilities of these adjacency combinations, relative to the underlying
distribution $F_{\\{u,v\\}}$, are computed by integrating/summing the
conditional probabilities (in table) times the density/mass of
$F_{\\{u,v\\}}$, obtaining

$\displaystyle\mathbb{P}[u\sim_{G_{1}}v\mbox{ and
}u\not\sim_{G_{2}}v]=\mathbb{P}[u\not\sim_{G_{1}}v\mbox{ and }u\sim_{G_{2}}v]$
$\displaystyle=$ $\displaystyle(1-\varrho_{e})(\mathbb{E}X-\mathbb{E}X^{2})$
$\displaystyle=$
$\displaystyle(1-\varrho_{e})(\mathbb{E}X-(\mathbb{E}X)^{2}-\mathbb{E}X^{2}+(\mathbb{E}X)^{2})$
$\displaystyle=$
$\displaystyle(1-\varrho_{e})[\mu_{F_{\\{u,v\\}}}(1-\mu_{F_{\\{u,v\\}}})\ -\
\sigma^{2}_{F_{\\{u,v\\}}}]$ $\displaystyle=$
$\displaystyle\mu_{F_{\\{u,v\\}}}(1-\mu_{F_{\\{u,v\\}}})(1-\varrho_{e})(1-\varrho_{F_{\\{u,v\\}}}).$

Then, for each $i=1,2$, because
$\mathbb{P}[u\sim_{G_{i}}v]=\mathbb{E}X=\mu_{F_{\\{u,v\\}}}$ we have all four
adjacency combinations as functions of $\mu_{F_{\\{u,v\\}}}$ and
$\varrho_{F_{\\{u,v\\}}}$. The result follows from the independence across all
pairs of vertices. ∎

In the Phantom Alignment Strength Conjecture we assume all distributions
$F_{\\{u,v\\}}$ are the same, call the common distribution $F$. Note that
Bernoulli mean $\mu$ and heterogeneity correlation $\varrho_{h}$ are now
random variables, and if $\mathfrak{n}$ is large, then $\mu$ and $\varrho_{h}$
will respectively be good estimators of $\mu_{F}$ and $\varrho_{F}$. A very
important consequence of Theorem 2 is that the only information that matters
regarding $F$ is contained (well-estimated) in the quantities $\mu$ and
$\varrho_{h}$.

##  4 Phantom Alignment Strength Conjecture, consequences

In this section, we propose the Phantom Alignment Strength Conjecture, which
is the central purpose of this paper. We then discuss its consequences; the
conjecture gives us a principled and practical way to decide if we should be
convinced that the output of a graph matching algorithm well-approximates the
true matching.

Henceforth we use the term alignment strength to refer to the restricted
alignment strength.

Consider correlated Bernoulli random graphs $G_{1},G_{2}$ such that there are
a “moderate” number $n$ of nonseed vertices (say $n\geq 300$), $s$ seeds
(selected discrete uniformly from the $\mathfrak{n}:=n+s$ vertices), and
Bernoulli parameters are independently realized from any fixed $[0,1]$-valued
distribution with moderate mean $\mu^{\prime}$ (say $.05<\mu^{\prime}<.95$).
The Phantom Alignment Strength Conjecture states that, subject to caveats, as
discussed in Section 6, there exists a phantom alignment strength value
$\hat{q}\equiv\hat{q}(n,s,\mu^{\prime})\in[0,1]$ such that
$\mathfrak{str}(\hat{\varphi})$ has “negligible” variance and is approximately
a function of the total correlation $\varrho_{T}$ and, specifically, it holds
that, with “high probability,”

$\displaystyle\mathfrak{str}(\hat{\varphi})\approx\left\\{\begin{array}[]{rl}\varrho_{T}&\mbox{
if }\varrho_{T}>\hat{q};\mbox{ in which case }\hat{\varphi}=\varphi^{*}\\\
\hat{q}&\mbox{ if }\varrho_{T}\leq\hat{q};\mbox{ in which case
}\hat{\varphi}\mbox{ is ``very different'' from
}\varphi^{*}\end{array}\right..$ (15)

Moreover, the conjecture states that, when using the seeded graph matching
algorithm SGM of [20], (given $n,s,\mu^{\prime}$, as above) then there exists
$\hat{q}_{\textup{SGM}}\equiv\hat{q}_{\textup{SGM}}(n,s,\mu^{\prime})\in[0,1]$
such that $\hat{q}_{\textup{SGM}}\geq\hat{q}$, and
$\mathfrak{str}(\hat{\varphi}_{\textup{SGM}})$ has “negligible” variance and
is approximately a function of the total correlation $\varrho_{T}$ and,
specifically, it holds that, with “high probability,”

$\displaystyle\mathfrak{str}(\hat{\varphi}_{\textup{SGM}})\approx\left\\{\begin{array}[]{rl}\varrho_{T}&\mbox{
if }\varrho_{T}>\hat{q}_{\textup{SGM}};\mbox{ in which case
}\hat{\varphi}_{\textup{SGM}}=\varphi^{*}\\\ \hat{q}&\mbox{ if
}\varrho_{T}\leq\hat{q}_{\textup{SGM}};\mbox{ in which case
}\hat{\varphi}_{\textup{SGM}}\mbox{ is ``very different'' from
}\varphi^{*}\end{array}\right..$ (18)

Note that both $\mathfrak{str}(\hat{\varphi})$ and
$\mathfrak{str}(\hat{\varphi}_{\textup{SGM}})$ are conjectured to be an
approximately piecewise linear function of $\varrho_{T}$; two pieces, one
piece with slope $0$ and one piece with slope $1$. However,
$\mathfrak{str}(\hat{\varphi})$ is continuous and shaped like a hockey stick
(see Figure 2(f)), whereas for $\mathfrak{str}(\hat{\varphi}_{\textup{SGM}})$
there can be a discontinuity (see Figure 2(b)); but the function value of the
linear portion with slope $0$ is the same for
$\mathfrak{str}(\hat{\varphi}_{\textup{SGM}})$ as it is for
$\mathfrak{str}(\hat{\varphi})$, namely it is the phantom alignment strength
value $\hat{q}$.

There are important consequences of the Phantom Alignment Strength Conjecture
for the practitioner. Suppose that a practitioner has two particular graphs
$G_{1},G_{2}$ with $n$ nonseed vertices and $s$ seeds that can be considered
as realized from a correlated Bernoulli random graph model, and the
practitioner wants to seeded graph match them, computing
$\hat{\varphi}_{\textup{SGM}}$ as an approximation of the true matching
$\varphi^{*}$. How can the practitioner tell if $\hat{\varphi}_{\textup{SGM}}$
is $\varphi^{*}$? This conjecture provides a principled, practical mechanism.
The practitioner should realize two independent Erdos-Renyi graphs $H_{1}$ and
$H_{2}$ with $n$ nonseed vertices, $s$ seeds, and adjacency probability
parameter $p$ equal to the combined density of $G_{1}$ and $G_{2}$. Then use
SGM to seeded graph match $H_{1}$ and $H_{2}$, and the alignment strength of
the bijection (between $H_{1}$ and $H_{2}$) is approximately
$\hat{q}\equiv\hat{q}(n,s,\mu)$, since the total correlation in generating
$H_{1}$ and $H_{2}$ is $0$, by design. Then, when subsequently seeded graph
matching $G_{1}$ and $G_{2}$, if
$\mathfrak{str}(\hat{\varphi}_{\textup{SGM}})$ is greater than some
predetermined and fixed $\epsilon>0$ above $\hat{q}$, then that would indicate
that $\hat{\varphi}_{\textup{SGM}}=\varphi^{*}$ and, if
$\mathfrak{str}(\hat{\varphi}_{\textup{SGM}})$ is less than this, then there
is no confidence that $\hat{\varphi}_{\textup{SGM}}$ is $\varphi^{*}$.
Moreover, in the former case the practitioner can have confidence in
approximating
$\mathfrak{str}(\hat{\varphi}_{\textup{SGM}})\approx\varrho_{T}$, and in the
latter case there wouldn’t be confidence in this approximation. (In the former
case, note that the full alignment strength
$\mathfrak{str}^{\prime}(\hat{\varphi}_{\textup{SGM}})$ would then be an even
better estimate of $\varrho_{T}$.)

(If some of the model assumptions are violated and the Bernoulli mean of
$G_{1}$ may be different from $G_{2}$, then it may be better not to combine
their densities, but rather to realize $H_{1}$ and $H_{2}$ as Erdos-Renyi
graphs with respective adjacency parameter equal to their respective
densities.)

##  5 Empirical evidence in favor of the Phantom Alignment Strength Conjecture

In this section we provide empirical evidence for the Phantom Alignment
Strength Conjecture.

A summary is as follows:

We begin in Section 5.1 with a scale small enough ($n$ is just on the order of
tens) to solve seeded graph matching and attain optimality. Although the
Phantom Alignment Strength Conjecture does not apply because $n$ is so small,
we nonetheless see many ingredients of the conjecture. Then, in Section 5.2,
we use synthetic data on a scale for the conjecture to be applicable, and we
empirically demonstrate the conjecture for many types of Bernoulli parameter
distributions; unimodal, bimodal, symmetric, skewed, etc. The SGM algorithm is
employed for seeded graph matching, since exact optimality is unattainable in
practice.

In Section 5.3, the alignment strength of completely uncorrelated Erdos-Renyi
graphs (graph matched with SGM, using no seeds), taken as a function of $n$,
is empirically demonstrated to be the same order of growth (in terms of $n$)
as the theoretical bound for matchability (as a function of $n$), which
suggests that the two quantities are the same, in excellent accordance with
the conjecture.

Then, in Section 5.4, we observe that when there is block structure and
differing distributions for the Bernoulli parameters by block (thus the
conjecture hypotheses are not adhered to) then the conjecture’s claims may
fail to hold, to some degree. Nonetheless, there is still a phantom alignment
strength that allows for a procedure similar to what we recommend in Section 4
to be successfully used for deciding when alignment strength is significant
enough to indicate that the seeded graph matching has found the truth.

Real data is then used for demonstration in Section 5.5 and Section 5.6.

Specifically, in Section 5.5, we use a human connectome at many different
resolution levels, and graph match it to a manually noised copy of itself.

Then, in Section 5.6, we consider several pairs of real-data graphs (titled
Wikipdeia, Enron, and C Elegans) whose vertices are the same objects, and the
adjacencies in each pair of graphs represent relationships between the objects
across two different modalities.

All of these experiments serve as strong empirical evidence for the Phantom
Alignment Strength Conjecture, and motivate its use.

###  5.1 Of hockey sticks and phantom alignment strength

We begin with an experiment in which the value of $n$ is well below what is
required in the statement of the Phantom Alignment Strength Conjecture.
However, $n$ is small enough here to enable us to compute $\hat{\varphi}$
exactly, using the integer programming formulation from [39]. We will be able
to see many features of the Phantom Alignment Strength Conjecture, and we will
also see that phantom alignment strength is not just an artifact of the SGM
algorithm.

For each value of $\varrho_{e}$ from $0$ to $1$ in increments of $.025$, we
did $100$ independent repetitions of the following experiment. We realized a
pair of correlated Bernoulli random graphs on $\mathfrak{n}=30$ vertices with
edge correlation $\varrho_{e}$ and, for each pair of vertices, the associated
Bernoulli parameter was $0.5$. (In particular, the graphs are correlated
Erdos-Renyi.) Since here $\sigma^{2}=0$, we have that $\varrho_{h}=0$, and
thus $\varrho_{T}=\varrho_{e}$. We discrete uniform randomly chose $s=15$
seeds, so there were $n=15$ nonseeds. For each experiment, we solved the
seeded graph matching problem to optimality (indeed, $n=15$ is small enough to
do so), obtaining $\hat{\varphi}$. If it happened that
$\hat{\varphi}=\varphi^{*}$ then we plotted a green asterisk in Figure 1 for
the resulting alignment strength $\mathfrak{str}(\hat{\varphi})$ against the
total correlation $\varrho_{T}$ and, if $\hat{\varphi}\neq\varphi^{*}$, we
plotted a red asterisk for the resulting alignment strength
$\mathfrak{str}(\hat{\varphi})$ against the total correlation $\varrho_{T}$.
The black diamonds in Figure 1 are the mean alignment strengths for the $100$
repetitions, plotted for each value of $\varrho_{e}$.

Figure 1: For each $\varrho_{e}$ from $0$ to $1$ in increments of $.025$,
alignment strength of $\hat{\varphi}$ for $100$ independent realizations when
all Bernoulli probabilities were $0.5$ (in particular,
$\varrho_{T}=\varrho_{e}$), with $n=15$ nonseeds, $s=15$ seeds, a green
asterisk if $\hat{\varphi}=\varphi^{*}$, else a red asterisk.

It is readily seen from Figure 1 that the variance for the alignment strength
of $\hat{\varphi}$ is quite high, which is reason to not formulate the Phantom
Alignment Strength Conjecture until $n$ is much larger. Other that this,
observe that if we substitute “mean of the alignment strength of
$\hat{\varphi}$” into the conjecture in place of “alignment strength of
$\hat{\varphi}$" then the conjecture would hold here. Indeed, when
$\varrho_{T}>\ \approx 0.44\equiv\hat{q}$ we very generally had that
$\hat{\varphi}=\varphi^{*}$, and when $\varrho_{T}\leq\ \approx 0.44$ we very
generally had that $\hat{\varphi}\neq\varphi^{*}$. (This boundary is not
sharp, but is close.) Also, note that when $\varrho_{T}>\ \approx 0.44$, the
mean of the alignment strength was approximately equal to $\varrho_{T}$.
Furthermore, when $\varrho_{T}\leq\ \approx 0.44$, we see that the (mean)
alignment strength of $\hat{\varphi}$ is the phantom alignment strength (mean)
of $\ \approx 0.44$. Indeed, in this latter case, the alignment strength of
$\hat{\varphi}$ is a misleading high value, and is not meaningful.

###  5.2 Of hockey sticks and broken hockey sticks

In this section, we use synthetic data that meets the hypotheses of the
Phantom Alignment Strength Conjecture. Our setup was as follows. We chose the
number of nonseeds to be $n=1000$, and we repeated an experiment for all
combinations of the following:

  * •

Each pair of Beta distribution parameters $\alpha,\beta$ listed in the
following table:

$\begin{array}[]{c|cc}&\alpha&\beta\\\ \hline\cr\mbox{Pair A}&1&1\\\
\mbox{Pair B}&0.5&0.5\\\ \mbox{Pair C}&2&2\\\ \mbox{Pair D}&5&1\\\ \mbox{Pair
E}&2&5\end{array}$

  * •

Each $\mu^{\prime}=$(mean of the scaled/translated Beta distribution) from
$.1$ to $.9$ in increments of $.1$,

  * •

Each number of seeds $s=0,10,20,50,250,1000$,

  * •

Each value of edge correlation $\varrho_{e}$ from $0$ to $1$ in increments of
$0.025$,

  * •

Each value of $\delta$ from $0$ to
$\delta_{max}:=\min\\{\frac{\alpha+\beta}{\alpha}\mu^{\prime},\frac{\alpha+\beta}{\beta}(1-\mu^{\prime})\\}$
in increments of $\frac{1}{10}\delta_{max}$.

For each combination of the above, we realized a pair of correlated Bernoulli
random graphs on $n+s$ vertices, with edge correlation $\varrho_{e}$ and, for
each pair of vertices, the associated Bernoulli parameter was independently
realized from the distribution
$\delta\cdot\textup{Beta}(\alpha,\beta)+\mu^{\prime}-\delta\frac{\alpha}{\alpha+\beta}$.
Note that

  * •

The distribution
$\delta\cdot\textup{Beta}(\alpha,\beta)+\mu^{\prime}-\delta\frac{\alpha}{\alpha+\beta}$
has support interval of length $\delta$, has mean $\mu^{\prime}$, and the
support interval is contained in the interval $[0,1]$.

  * •

The distribution
$\delta\cdot\textup{Beta}(\alpha,\beta)+\mu^{\prime}-\delta\frac{\alpha}{\alpha+\beta}$
is uniform when $\alpha,\beta$ is $1,1$, and is bimodal when $\alpha,\beta$ is
$0.5,0.5$, is symmetric unimodal when $\alpha,\beta$ is $2,2$, and is skewed
in the other two cases, in different directions, one where the mode is an
endpoint of the support and one where the mode is interior of the support.

  * •

The Bernoulli mean $\mu$ is approximately $\mu^{\prime}$, since ${n+s\choose
2}$ is very large for these purposes.

(a) number of seeds $s=0$

(b) number of seeds $s=10$

(c) number of seeds $s=20$

(d) number of seeds $s=50$

(e) number of seeds $s=250$

(f) number of seeds $s=1000$

(g) Zoom into subfigure (c), $s=20$

(h) Zoom into subfigure (d), $s=50$

Figure 2: Alignment strength $\mathfrak{str}(\hat{\varphi}_{\textup{SGM}})$
plotted against total correlation $\varrho_{T}$ for the synthetic data
experiments in Section 5.2, separated according to the number of seeds $s$.
The number of nonseeds was $n=1000$, and only the case of $\mu^{\prime}=0.5$
is shown here. Match ratio of each experiment is color coded green, blue, or
red according to the legend above. Subfigures (g) and (h) are zooms into
subfigures (c) and (d), to increase the granularity so that the thresholding
is better seen.

The $s$ seeds were chosen discrete uniform randomly from the $n+s$ vertices,
and we computed $\hat{\varphi}_{\textup{SGM}}$ via the SGM algorithm for
seeded graph matching. In Figure 2 we plotted alignment strength
$\mathfrak{str}(\hat{\varphi}_{\textup{SGM}})$ against total correlation
$\varrho_{T}$ for all of the pairs of graphs generated in the case where
$\mu^{\prime}=0.5$, in different subfigures for the different values of
$s=0,10,20,50,250,1000$; green dots indicate when
$\hat{\varphi}_{\textup{SGM}}=\varphi^{*}$, blue and red dots indicate when
$\hat{\varphi}_{\textup{SGM}}\neq\varphi^{*}$, blue when
$\hat{\varphi}_{\textup{SGM}}$ agreed with $\varphi^{*}$ on at least $85\%$ of
the nonseeded vertices (i.e. “match ratio $\geq 85\%$”), and red when
$\hat{\varphi}_{\textup{SGM}}$ agreed with $\varphi^{*}$ on less than $85\%$
of the nonseeded vertices.

Note that in Figure 2, each of (a)-(f) are plots of $2255$ points, each point
represented with a filled circle, and the crowding of the points makes them
resemble lines; so, in Figure 2, we also included (g) and (h), which are zooms
of a portion of (c) and (d), respectively. With the increased granularity in
(g) and (h), we see that if we ignore some outlier red and green dots, then
there is a better defined transition from red to green than would appear in
(c) and (d).

The Phantom Alignment Strength Conjecture is well motivated by the results
illustrated in Figure 2. In particular, alignment strength
$\mathfrak{str}(\hat{\varphi}_{\textup{SGM}})$ exhibits very low variance and
is approximately a piecewise-linear function of total correlation
$\varrho_{T}$. There appears to be a critical value $\hat{q}_{\textup{SGM}}$,
dependent on the number of seeds $s$ in these experiments, for which the
following holds. When total correlation $\varrho_{T}$ is above
$\hat{q}_{\textup{SGM}}$ then $\hat{\varphi}_{\textup{SGM}}=\varphi^{*}$ and
$\mathfrak{str}(\hat{\varphi}_{\textup{SGM}})\approx\varrho_{T}$, and when
total correlation $\varrho_{T}$ is below $\hat{q}_{\textup{SGM}}$ then
$\hat{\varphi}_{\textup{SGM}}\neq\varphi^{*}$, evidenced by
$\mathfrak{str}(\hat{\varphi}_{\textup{SGM}})\not\approx\varrho_{T}$, and
$\mathfrak{str}(\hat{\varphi}_{\textup{SGM}})$ is constant— at a phantom
alignment strength level. When there are enough seeds, we see that the two
pieces of the function join to become continuous, suggesting that
$\hat{\varphi}_{\textup{SGM}}=\hat{\varphi}$ is then achieved for all
$\varrho_{T}$, and the value of $\hat{q}_{\textup{SGM}}$ is then $\hat{q}$.

Also note that the five different Beta distributions from which Bernoulli
parameters were realized (the five pairs of Beta parameters labelled A, B, C,
D, E) in these experiments were collected into each of the figures of Figure
2, and the experiment results for these different distributions are
indistinguishable from each other in the figures, in accordance with Theorem
2, and reflected in the Phantom Alignment Strength Conjecture claim that the
phantom alignment strength is just a function of $n,s,\mu^{\prime}$, and that
it isn’t relevant what distribution is used to obtain the Bernoulli
parameters.

Also note the phase transition from matchable to non-matchable which takes
place when $\varrho_{T}$ gets to $\hat{q}_{\textup{SGM}}$, and this phase
transition becomes better and better defined as the number of seeds goes up.

For the other values of $\mu^{\prime}$, the figures exhibited the same overall
type of structure, although the phantom alignment strength values were
different. In the interest of space, we only present here the
$\mu^{\prime}=0.5$ experiment figures.

###  5.3 Phantom alignment strength vs theoretical matchability threshold

Among other assertions, the Phantom Alignment Strength Conjecture asserts,
under conditions, that the alignment strength
$\mathfrak{str}(\hat{\varphi}_{\textup{SGM}})$ when $\varrho_{T}=0$, called
the “phantom alignment strength,” is equal to the total correlation threshold
for matchability of exact seeded graph matching (i.e. the particular value
such that $\hat{\varphi}=\varphi^{*}$ or not according as $\varrho_{T}$ is
greater than this value or not); indeed, we have denoted this common quantity
$\hat{q}$. In this section, we will compare alignment strength
$\mathfrak{str}(\hat{\varphi}_{\textup{SGM}})$ when $\varrho_{T}=0$ to the
matchability threshold proved in [45].

Consider a probability space with a sequence of correlated Bernoulli random
graphs for each of the number of vertices $\mathfrak{n}\equiv n=1,2,3,\ldots$,
with $s=0$ seeds and all Bernoulli parameters equal to a fixed value $p$ (ie
correlated Erdos-Renyi random graphs). When we say that a sequence of events
happens “almost always” we mean that, with probability $1$, all but a finite
number of the events occur. The following result was stated and proved in
[45]; although stated there in terms of $\varrho_{e}$, we write $\varrho_{T}$
instead, since here, where $\varrho_{h}=0$, we have that
$\varrho_{T}=\varrho_{e}$.

######  Theorem 3.

There exists positive, real valued, fixed constants $c_{1},c_{2}$ such that if
$\varrho_{T}\geq c_{1}\sqrt{\frac{\log n}{n}}$ then almost always
$\hat{\varphi}=\varphi^{*}$, and if $\varrho_{T}\leq c_{2}\sqrt{\frac{\log
n}{n}}$ then
$\lim_{n\rightarrow\infty}\mathbb{E}|\\{\varphi\in\varPi:\mathcal{D}^{\prime}(\varphi)<\mathcal{D}^{\prime}(\varphi^{*})\\}|=\infty$.

For each value of $p=.05,.1,.2,.3,.4,.5$, and each of $500$ values of $n$
between $500$ and $4000$, (as mentioned, $s=0$) we plotted realizations of
alignment strength $\mathfrak{str}(\hat{\varphi}_{\textup{SGM}})$ vs the value
of $n$, for uncorrelated ($\varrho_{e}=0$) pairs of random Bernoulli (Erdos-
Renyi) graphs where each Bernoulli parameter is $p$, hence $\varrho_{T}=0$
(since $\varrho_{e}=0$, $\varrho_{h}=0$). Figure 3 shows the plots for
$p=0.05,0.1,0.5$.

Figure 3: Phantom alignment strength as a function of $n$,
fitted to $f_{p}(n):=d_{p}+c_{p}\sqrt{\frac{\log n}{n}}$.

Then, for each $p$, we fit the associated points to a curve
$f_{p}(n):=d_{p}+c_{p}\sqrt{\frac{\log n}{n}}$ for real numbers $c_{p}$ and
$d_{p}$; the values of $d_{p}$ and $c_{p}$ are given in Table 1, and $f_{p}$
is also drawn in Figure 3. For each value of $p$, note the near-perfect fit of
$f_{p}$ to the associated points plotted in Figure 3, and note that the value
of $d_{p}$ is close to zero.

Table 1: Values of the constants in $f_{p}(n):=d_{p}+c_{p}\sqrt{\frac{\log n}{n}}$ $p$ | $d_{p}$ | $c_{p}$
---|---|---
$0.05$ | $-0.021$ | $2.19$
$0.1$ | $-0.010$ | $1.80$
$0.2$ | $-0.003$ | $1.58$
$0.3$ | $-0.001$ | $1.51$
$0.4$ | $0.000$ | $1.48$
$0.5$ | $0.000$ | $1.47$

Indeed, this suggests, as conjectured in the Phantom Alignment Strength
Conjecture, that the phantom alignment strength (ie
$\mathfrak{str}(\hat{\varphi}_{\textup{SGM}})$ when $\varrho_{T}=0$) exists as
a value $\hat{q}$ which coincides with the amount of total correlation needed
for $\hat{\varphi}=\varphi^{*}$.

###  5.4 Block settings

The setting of the Phantom Alignment Strength Conjecture in Section 4 was
specifically concerning correlated Bernoulli random graphs $G_{1},G_{2}$ such
that there are $n$ nonseed vertices, $s$ seed vertices (selected discrete
uniformly from the $\mathfrak{n}:=n+s$ vertices), and Bernoulli parameters for
each pair of vertices are selected independently from any fixed distribution
with mean $\mu^{\prime}$.

Let us consider a block setting, which differs from the above in that there is
a positive integer $K$, and the vertex set $V$ is first randomly partitioned
into $K$ blocks $B_{1},B_{2},\ldots,B_{K}$ as follows: There is a given
probability vector $\pi\in[0,1]^{K}$ such that $\sum_{i=1}^{K}\pi_{i}=1$ and
each vertex in $V$ is independently placed in block $B_{i}$ with probability
$\pi_{i}$ for $i=1,2,\ldots,K$. Next, suppose there is a unit-interval-valued
(ie $[0,1]$-valued) distribution $F_{i,j}$ for each $i=1,2,\ldots,K$ and
$j=i,i+1,\ldots,K$ such that, for each $1\leq i\leq j\leq K$ and each $u\in
B_{i}$ and $v\in B_{j}$, the Bernoulli parameter $p_{\\{u,v\\}}$ is
independently realized from distribution $F_{i,j}$. Let $M$ be the $K\times K$
symmetric matrix with $i,j$th entry equal to the mean of distribution
$F_{i,j}$.

Similarly to the Phantom Alignment Strength Conjecture, does there exists a
phantom alignment strength value $\hat{q}\equiv\hat{q}(n,s,\pi,M)\in[0,1]$ and
also $\hat{q}_{\textup{SGM}}\equiv\hat{q}_{\textup{SGM}}(n,s,\pi,M)\in[0,1]$
whereby Equation (15) and Equation (18) hold? This is not so simple.

We consider the following choices for $n$, $s$, $\pi$, and $M$:

$\displaystyle n=1000\ \ \ \ s=40\ \ \ \ \pi=\left[\begin{array}[]{c}0.2\\\
0.8\end{array}\right]\ \ \ \ M=\left[\begin{array}[]{cc}0.3&0.4\\\
0.4&0.5\end{array}\right]$

In experiment “A”, we took $F_{1,1}$ to be point mass distribution at $0.3$,
$F_{1,2}$ to be point mass distribution at $0.4$, and $F_{2,2}$ to be point
mass distribution at $0.5$. For each value of edge correlation $\varrho_{e}$
from $0$ to $1$ in increments of $0.001$, we realized Bernoulli parameters and
then we realized associated correlated Bernoulli random graphs. In Figure 6,
we plotted alignment strength $\mathfrak{str}(\hat{\varphi}_{\textup{SGM}})$
against total correlation $\varrho_{T}$; green dots indicate when
$\hat{\varphi}_{\textup{SGM}}=\varphi^{*}$, (else) light blue when
$\hat{\varphi}_{\textup{SGM}}$ agreed with $\varphi^{*}$ on at least $85\%$ of
the nonseeded vertices, (else) dark blue when $\hat{\varphi}_{\textup{SGM}}$
agreed with $\varphi^{*}$ on at least $50\%$, (else) red when
$\hat{\varphi}_{\textup{SGM}}$ agreed with $\varphi^{*}$ on less than $50\%$
of the nonseeded vertices. We then repeated the experiment with the only
difference being that $F_{2,2}$ was the uniform distribution on the interval
$[0,1]$, so $(n,s,\pi,M)$ are same as above; the resulting plot is Figure 6
(alignment strength $\mathfrak{str}(\hat{\varphi}_{\textup{SGM}})$ vs
$\varrho_{T}$, same dot color scheme as above). Let us call this Experiment
“B.”

Next, we repeated the above experiment for all eight possible combinations of:
$F_{1,1}$ is the uniform distribution on a) interval $[0.25,0.35]$ or b)
interval $[0,0.6]$
$F_{1,2}$ is the uniform distribution on a) interval $[0.35,0.45]$ or b)
interval $[0,0.8]$
$F_{2,2}$ is the uniform distribution on a) interval $[0.45,0.55]$ or b)
interval $[0,1]$
and we superimposed all of the alignment strength vs total correlation plots
in Figure 6 (same dot color scheme as above); we will call this Experiment
“C.” Again, the underlying $(n,s,\pi,M)$ are the same as the previous
experiments.

Note that Figure 6, Figure 6, and Figure 6 (for respective experiments A,B,
and C) are not similar, even though they originate from the same values of
$n$, $s$, $\pi$, and $M$. Thus, the Phantom Alignment Strength Conjecture is
not simply extended to the case of nontrivial block structure.

Figure 4: Experiment A in Section 5.4; here $F_{1,1}$, $F_{1,2}$, $F_{2,2}$
are resp. point mass at $0.3$, $0.4$, $0.5$.

Figure 5: Experiment B in Section 5.4; same as Experiment A except that
$F_{2,2}$ is uniform $[0,1]$.

Figure 6: Experiment C in Section 5.4; eight different combinations for
$F_{1,1}$, $F_{1,2}$, $F_{2,2}$.

However, also note that when SGM was broadly failing to get the truth in
experiments A, B, and C (i.e. the red dots in Figure 6, Figure 6, and Figure
6), the alignment strength was almost constant, at a value of around $0.12$.
This suggests a decision procedure (analogous the procedure described in
Section 4) for deciding if $G_{1}$, $G_{2}$ from an $(n,s,\pi,M)$-block model
are graph matched with some truth. The procedure would be to realize $H_{1}$
and $H_{2}$ as correlated Bernoulli random graphs where $\varrho_{e}=0$, where
the $n+s$ vertices are apportioned to the blocks in proportion to $\pi$, and
where, for every pair of vertices, the Bernoulli parameter is taken as the
entry of $M$ associated with the block memberships of the two vertices, and
then the $s$ seeds are chosen uniformly at random. The alignment strength of
the seeded graph match of $H_{1}$ to $H_{2}$ can then be used as a phantom
alignment strength value in the sense that, if the alignment strength of the
seeded graph match of $G_{1}$ to $G_{2}$ is more than some $\epsilon>0$
greater than this phantom alignment strength value, then we decide that there
is at least some truth present in the seeded graph match of $G_{1}$ to
$G_{2}$.

What made the block structure more complicated? We will next provide some
insight. Indeed, Experiment B was constructed in an extreme way in order to
cause particular mischief. The value of $\varrho_{h}$ in Experiment A was
approximately $.0129$, and the value of $\varrho_{h}$ in Experiment B was
approximately $.2277$; in particular, that is why the value of $\varrho_{T}$
was never below approximately $.22$ in Experiment B, as is clear from Figure
6. However, in Experiment B when $\rho_{e}=0$, all of the vertices in the
first block are stochastic twins; they share the same probabilities of
adjacency as each other to all of the vertices in the graph, and all
adjacencies are collectively independent. Thus the “true” bijection (the
identity) has no signal in that case. (One might even say that the “truth”
isn’t very “truthy.”) As such, the total correlation in that case,
approximately $.2277$, does not contribute to matchability vis-a-vis the first
block. As positive edge correlation $\varrho_{e}$ is increasingly added in to
Experiment B, the first block achieves matchability on the strength of only
the edge correlation, and the second block achieves matchability on the
strength of edge correlation together with heterogeneity correlation. In this
manner, total correlation does not tell a uniform story across all vertices.
This is in contrast to the hypotheses of the Phantom Alignment Strength
Conjecture (and the setup in the empirical matchability experiments in the
paper [39]) where the Bernoulli parameters were realized from one
distribution. Note that with Experiment C, there is more variety in
$\varrho_{h}$ (for the eight experiments the values of $\varrho_{h}$ ranged
from approximately $.0161$ to approximately $.30$); there is still some lack
of demarcation between matchable and nonmatchable in terms of total
correlation, but the situation is improved somewhat from the left tail of the
figure, and total correlation has more influence as a unified quantity.

We did additional experiments with other values of $(n,s,\pi,M)$ and found
comparable results to what appears above.

###  5.5 Real data; matching graphs to noisy renditions

Recall that the Phantom Alignment Strength Conjecture is formulated under the
assumption that each pair of vertices has a Bernoulli parameter that is a
realization of a distribution which is common to all of the pairs of vertices.
How realistic is this assumption in practice? And, more to the point of the
practitioner, do the conclusions of the conjecture apply to real data, in
general?

In this section we consider a human connectome at different resolution levels.
(This connectome has been featured in [46, 47].) Diffusion-weighted Magnetic
Resonance Imaging (dMRI) brain scans were collected from one hundred and
fourteen humans at the Beijing Normal University [48]. Fiber tracts, which
trace axonal pathways through a three-spatial-dimensional cuboid array of
$1\times 1\times 1\;\textrm{mm}^{3}$ voxels of the dMRI scan, are estimated
using the ndmg pipeline [49].

For each value of $\mathfrak{n}=70,\ 107,\ 277,\ 582,\ 3230$, the graph
$G_{\mathfrak{n}}$ was formed in the following manner. Starting from the
original cuboid array of voxels, $\mathfrak{n}$ equally spaced “contractile”
voxels were selected, and each voxel in the array was merged with its nearest
contractile voxel [50]; the $\mathfrak{n}$ such groupings of voxels (centered
at their contractile voxel) are the $\mathfrak{n}$ vertices of the graph
$G_{\mathfrak{n}}$. For any two vertices in $G_{\mathfrak{n}}$, we declare
them adjacent precisely when there exists a fiber that runs through any voxel
of one vertex and also any voxel of the other vertex for any of the one
hundred and fourteen individuals.

Given any graph $G=(V,E)$, and also given any noise parameter $\rho\in[0,1]$,
we can instantiate a graph $\overline{G}$ called a $\rho$-noised rendition of
$G$ on the same vertex set $V$ as follows. Denote the density of $G$ by
$\mathfrak{d}^{\prime}G:=\frac{|E|}{{|V|\choose 2}}$. First, instantiate an
independent Erdos-Renyi graph $H$ on $V$ with Bernoulli parameter
$\mathfrak{d}^{\prime}G$; i.e. each pair of vertices is an edge independently
of the others with probability $\mathfrak{d}^{\prime}G$. Next, for each pair
of vertices $\\{u,v\\}$, perform an independent Bernoulli trial; with
probability $\rho$ set $u$ adjacent/ not adjacent (resp.) to $v$ in
$\overline{G}$ according as $u$ adjacent/ not adjacent (resp.) to $v$ in $G$,
and with probability $1-\rho$ set $u$ adjacent/ not adjacent (resp.) to $v$ in
$\overline{G}$ according as $u$ adjacent/ not adjacent (resp.) to $v$ in $H$.
In this manner, $\overline{G}$ is a mixture of $G$ and noise graph $H$. When
graph matching $G$ to a $\rho$-noised rendition of $G$, clearly $\varphi^{*}$
is the identity function $V$ to $V$.

For each of $\mathfrak{n}=70,\ 107,\ 277,\ 582,\ 3230$, we did the following
experiment. For each value of the noise parameter $\rho$ from $0$ to $1$ in
increments of $.025$, we did $20$ repetitions of instantiating a $\rho$-noised
rendition of $G_{\mathfrak{n}}$, then seeded graph matched $G_{\mathfrak{n}}$
to it using the SGM algorithm after selecting $10\%$ of the $\mathfrak{n}$
vertices (discrete uniform randomly) as seeds. The mean alignment strength
$\mathfrak{str}(\hat{\varphi}_{\textup{SGM}})$ (the mean being over the $20$
repetitions) vs noise parameter $\rho$ was plotted in five respective figures
(for the five different values of $\mathfrak{n}$) in the left side of Figure
7; green dots indicate when $\hat{\varphi}_{\textup{SGM}}=\varphi^{*}$, (else)
light blue when $\hat{\varphi}_{\textup{SGM}}$ agreed with $\varphi^{*}$ on at
least $85\%$ of the nonseeded vertices, (else) dark blue when
$\hat{\varphi}_{\textup{SGM}}$ agreed with $\varphi^{*}$ on at least $50\%$,
(else) red when $\hat{\varphi}_{\textup{SGM}}$ agreed with $\varphi^{*}$ on
less than $50\%$ of the nonseeded vertices.

Figure 7: Section 5.5 experiments; LHS is noisy connectome, RHS is
corresponding synthetic.

We then repeated the above experiments, with the only difference being that in
place of $G_{\mathfrak{n}}$ we used an Erdos-Renyi graph instantiation, the
Erdos-Renyi using the Bernoulli parameter
$\mathfrak{d}^{\prime}G_{\mathfrak{n}}$ (the density of the connectome
$G_{\mathfrak{n}}$). The resulting plots are in the right hand side of Figure
7. Simple calculations of the distributions show that the pairs of graphs
being seeded graph matched here in these repeated experiments are precisely
correlated Erdos-Renyi graphs with the parameter $\rho$ being precisely the
edge correlation $\varrho_{e}$, which is equal to $\varrho_{T}$ since
$\varrho_{h}=0$.

To emphasize: The left hand side of Figure 7 is from seeded graph matching
connectome to noisy connectome, and the right hand side of Figure 7 is from
seeded graph matching synthetic data of the same connectome density to a noisy
version of this synthetic data, which turns out to precisely be seeded graph
matching pairs of correlated Bernoulli random graphs where the noise parameter
turns out to be the total correlation, so the figures in the right hand side
of Figure 7 are of Section 5.2 variety (except that the alignment strength
values are averaged over $20$ instantiations).

Notice that the figures in the left hand side of Figure 7 and their respective
counterparts in the right hand side of Figure 7 look remarkably similar in
many important ways. The differences seem to just be that the seeded graph
matching success and alignment strength values clearly exhibit thresholding in
the synthetic data, which is less pronounced and more gradual in the
connectome data, although the sharpness of the connectome thresholding seems
to be catching up as the number of vertices increases. Aside from this, there
stills seems to be a reasonable phantom alignnment strength for the connectome
data.

###  5.6 Real data; matching same objects under different modalities

In this section, we illustrate the ideas in this paper using three real data
sets from [20]; they are the Wikipedia, Enron, and C Elegans pairs of graphs.
Each is an example of a pair of graphs with the same underlying objects (thus
there is a natural “true” bijection), and adjacencies between objects in the
respective graphs are relationships among the objects in two different
modalities.

The Wikipedia pair of graphs $G_{1}$, $G_{2}$ from [20] were created in the
year 2009. The vertices of $G_{1}$ are the English language Wikipedia articles
hyperlinked from the Wikipedia article “Algebraic Geometry,” and all Wikipedia
articles hyperlinked from these articles; in total, there are
$\mathfrak{n}=1382$ vertices. These vertices/articles each have directly
corresponding articles in the French language Wikipedia, and these are the
vertices of $G_{2}$. Every pair of vertices/articles in $G_{1}$ are adjacent
in $G_{1}$ precisely when one of the articles hyperlinks to the other article
in the English language Wikipedia, and every pair of vertices in $G_{2}$ are
adjacent in $G_{2}$ precisely when one of the articles links to the other in
the French language Wikipedia. Thus $G_{1}$ and $G_{2}$ are simple, undirected
graphs, and the “true” bijection is the function mapping English articles to
their French versions.

For each value of $s=0,5,50,150,250,382,500$, we did 100 replicates of
uniformly sampling $s$ seeds from the $\mathfrak{n}$ vertices, seeded graph
matched $G_{1}$ to $G_{2}$ using SGM, then recording the alignment strength
$\mathfrak{str}(\hat{\varphi}_{\textup{SGM}})$, averaged over the 100
replicates, plotted (in blue) vs the number of seeds $s$ in Figure 8. In the
same figure, we recorded the match ratio (the number of nonseeds correctly
matched, divided by the number of nonseeds), averaged over the 100
replications, plotted (in purple) vs the number of seeds $s$, also in Figure
8. In addition, for each value of $s=0,5,50,150,250,382,500$, we did 100
replicates of realizing uncorrelated pairs of Erdos-Renyi graphs $H_{1}$,
$H_{2}$, each with $1382$ vertices and Bernoulli parameter of $H_{1}$ equal to
the density of $G_{1}$, Bernoulli parameter of $H_{2}$ equal to the density of
$G_{2}$, then uniformly sampling $s$ seeds from the $1382$ vertices, then
seeded graph matched $H_{1}$ to $H_{2}$ using SGM, and recording the alignment
strength $\mathfrak{str}(\hat{\varphi}_{\textup{SGM}})$, averaged over the 100
replicates, plotted (in green) vs the number of seeds $s$ in Figure 8; these
values represent the phantom alignment strength values in the respective seed
levels. Note that, as the number seeds went from $0$ to $5$ to $50$, the jump
in match ratio coincides with a jump in the gap between seeded graph matching
alignment strength and the phantom alignment strength. (Even when $s=0$ there
is some truth in the graph match; the match ratio was $.0151$, approximately
$21$ nonseed vertices matched correctly, whereas chance is $1/1382$, one
nonseed vertex matched correctly.)

Figure 8: Matching English and French Wikipedia graphs

The C. Elegans pair of graphs $G^{e\ell}$, $G^{ch}$ from [51, 20] are
connectomes mapping out the neural structure of the roundworm Caenorhabditis
Elegans. C. Elegans is of interest to neuroscientists due to its well studied
genetics [52], comparatively simple nervous system [53], and a growing
understanding of the correspondence between the two [54, 55]. Like in humans,
communication in the C. Elegans nervous system occurs via synapses, or
junctions, between pairs of neurons. Neuronal synapses in the C. Elegans
connectome can be classified in two ways [51]: an electrical synapse is a
channel through which electrical impulses traverse, whereas chemical synapses
are junctions through which neurotransmitters flow. We consider
$\mathfrak{n}=279$ somatic neurons of the hermaphrodite C. Elegans as the
vertices of each graph. For each pair of vertices/neurons, they are adjacent
in $G^{e\ell}$ precisely when there is an electrical synapse between them, and
they are adjacent in $G^{ch}$ precisely when there is a chemical synapse
between them.

We conducted the identical experiments as we did for the Wikipedia graphs,
except that the number of seeds $s$ considered were
$s=0,1,5,10,20,50,75,100,150,200$, and we matched $G^{e\ell}$ and $G^{ch}$.
The resulting plots are in Figure 9; alignment strength of the C Elegans
seeded graph match in blue, phantom alignment strength in green, match ratio
in purple. Note that seeded graph matching did poorly, as evidenced by low
match ratio, even when the number of seeds was huge ($200$ seeds and $79$
nonseeds), and correspondingly the gap between seeded graph matching alignment
strength and phantom alignment strength was small.

Figure 9: Matching C Elegans’ electrical and chemical connectome

The Enron graphs from [20] arose in the following manner. Enron was a large
and highly respected energy company that dissolved spectacularly in 2001 amid
systemic fraud. The United States Justice Department released a trove of email
messages between company employees. The graphs $G_{130}$, $G_{131}$, and
$G_{132}$ have as vertices $\mathfrak{n}=184$ Enron employees and, for each
pair of vertices/employees, the vertices are adjacent in $G_{130}$ precisely
when there is an email from one employee to the other in week number 130 of
the email corpus, they are adjacent in $G_{131}$ precisely when there is an
email from one employee to the other in week number 131, and they are adjacent
in $G_{132}$ precisely when there is an email from one employee to the other
in week number 132. The paper [56] identified an anomaly going into week 132,
and [20] used match ratio differences between pairs of these graphs to
highlight this anomaly.

We conducted the identical experiments for each of the pairs $G_{130},G_{131}$
and $G_{131},G_{132}$ and $G_{130},G_{132}$ as we did for the Wikipedia
graphs, except that the number of seeds $s$ considered were
$s=0,1,5,10,20,50,60,90,100$. The resulting plots are in Figure 10. As noted
in [20], the match ratio from matching $G_{130}$ to $G_{131}$ is highest of
the three, since the anomaly had not yet occurred. The next highest match
ratio was from matching $G_{131}$ to $G_{132}$, then came matching $G_{130}$
to $G_{132}$. Note that the gap between seeded graph matching alignment
strength and phantom alignment strength was ordered the same way; highest was
$G_{130}$ to $G_{131}$, then was $G_{131}$ to $G_{132}$, and then was
$G_{130}$ to $G_{132}$. Indeed, more gap here when there was higher match
ratio. (Note that the match ratios here differ a bit from those in the paper
[20], Figure 8; that figure was inadvertently from a nonsimple graph version
of the data, and here we created a simple graph.)

Figure 10: Matching Enron email networks; all pairs from weeks
$\\{130,131,132\\}$.

##  6 Notable mentions and future directions, plus caveats

The applications of graph matching are broad and many, and getting the right
answer is only valuable when we know that we have the right answer. This paper
provides principled tools that can help the practitioner decide if seeded
graph matching has found the true bijection.

The first caveat —and future direction— is that we are presenting a
conjecture, and not a theorem. Indeed, the Phantom Alignment Strength
Conjecture, as formulated in Section 4, includes terms in quotes; “moderate,”
“high probability,” “very different,” and “negligible.” Ironing these terms
out with specifics is part of the puzzle of proving the conjecture, and is an
important next task. It may be a hard task, and we expect this paper to
stimulate more experimentation, fine-tuning, and eventually a proof of the
conjecture.

Part of the first caveat is the consideration that we don’t have a proof of
the conjecture as of now, and our experimentation is wide but not exhaustive,
and thus there may be additional hypotheses or limitations to the conjecture
statement.

A second caveat is that the conjecture is expressed in terms of an underlying
model for a pair of random graphs, and we need to consider if particular real
data that we may encounter (beyond the examples that we used here) can more
generally be considered as arising from such a model.

Also, when there are multiple blocks with Bernoulli coefficients being
realized from different distributions for different blocks, we saw in Section
5.4 that total correlation became a much less reliable tool for determining
matchability. More work is needed to explore this further; the paper [39],
when presenting empirical evidence for the relationship between total
correlation and matchability, restricted their attention to the setting
hypothesized in our Phantom Alignment Strength Conjecture, which excludes
multiple blocks. Indeed, in the setting of our conjecture, the role of total
correlation in matchability is starkly visible. See Figure 2(d), where the
x-axis is total correlation, and compare to Figure 11. Figure 11 is the same
data plotted in Figure 2(d), except that the x-axis is used for edge
correlation instead of total correlation. The contrast between these two
figures is quite dramatic. Indeed, the current-literature-standard yardstick
of edge correlation failed miserably in capturing matchability, whereas total
correlation captured matchability perfectly here. These two figures are
powerful illustration of the role of total correlation in matchability.

Figure 11: The same as the plot in Figure 2(d), except that the x-axis in this
figure is edge correlation instead of total correlation. The contrast between
these two figures is quite stark, and highlights the utility of total
correlation with regard to matchability.

While more work remains to be done, we have here presented principled tools
that can be of significant help to the practitioner now.

A large measure of inspiration for this paper came from Figures 1, 2, and 3 of
[39] (on which half of us are co-authors). Those figures displayed the results
of graph matchings of many simulations of pairs of correlated Bernoulli random
graphs under similar conditions of the Phantom Alignment Strength Conjecture.
One axis of each figure tracked edge correlation, and the second axis tracked
heterogeneity correlation; green, yellow, and red dots were respectively
located at coordinates corresponding to parameters where the graph matchings
were always the truth, mostly the truth, and often not the truth,
respectively. It was striking to observe that the regions of red and green
were sharply demarcated by a level curve of total correlation, with little
yellow between the red and green. These figures starkly demonstrated the role
of total correlation in matchability, as well as thresholding behavior.
Together with the theoretical results of [39] tieing alignment strength to
total correlation (when graph matching gets truth), we had important
ingredients for the “hockey stick” at the heart of the Phantom Alignment
Strength Conjecture.

## Acknowledgements

The authors thanks Dr. David Marchette for creating the Wikipedia graph that
we used here.

## Funding

This paper is based on research sponsored by the Air Force Research Laboratory
and DARPA under agreement number FA8750-20-2-1001 and FA8750-17-2-0112. The
U.S. Government is authorized to reproduce and distribute reprints for
Governmental purposes notwithstanding any copyright notation thereon. The
views and conclusions contained herein are those of the authors and should not
be interpreted as necessarily representing the official policies or
endorsements, either expressed or implied, of the Air Force Research
Laboratory and DARPA or the U.S. Government.

## Abbreviations

C. Elegans: Caenorhabditis Elegans
dMRI: Diffusion-weighted Magnetic Resonance Imaging
DT-MRI: Diffusion Tensor Magnetic Resonance Imaging

## Availability of data and materials

Located at https://cs.jhu.edu/~fparker9/phantom-alignment-strength/

## Competing interests

The authors declare that they have no competing interests.

## Authors’ contributions

DEF formulated the Phantom Alignment Strength Conjecture, penned much of the
manuscript.
FP, HS, and LM did the numerical experiments and contributed to the
formulation of the conjecture.
VL penned the introduction section, including the literature review, and made
the bibliography.
EB was involved in the acquisition of the human connectome data set, processed
the data for our particular use, and penned a portion of the manuscript
involving the human and C Elegans connectome networks.
VL, CEP, and AA worked on the theoretical development, edited the manuscript.
All authors read and approved the manuscript.

## Authors’ information

## References

  * [1] Wasserman, S., Faust, K.: Social Network Analysis: Methods and Applications. Cambridge University Press, ??? (1994)
  * [2] Bullmore, E., Sporns, O.: Complex brain networks: Graph theoretical analysis of structural and functional systems. Nature Rev. Neurosci 10, 186–198 (2009)
  * [3] Vogelstein, J.T., Bridgeford, E.W., Pedigo, B.D., Chung, J., Levin, K., Mensh, B., Priebe, C.E.: Connectal coding: discovering the structures linking cognitive phenotypes to individual histories. Current opinion in neurobiology 55, 199–212 (2019)
  * [4] Szklarczyk, D., Franceschini, A., Wyder, S., Forslund, K., Heller, D., Huerta-Cepas, J., Simonovic, M., Roth, A., Santos, A., Tsafou, K.P., et al.: String v10: protein–protein interaction networks, integrated over the tree of life. Nucleic acids research 43(D1), 447–452 (2015)
  * [5] Tong, A.H.Y., Lesage, G., Bader, G.D., Ding, H., Xu, H., Xin, X., Young, J., Berriz, G.F., Brost, R.L., Chang, M., et al.: Global mapping of the yeast genetic interaction network. science 303(5659), 808–813 (2004)
  * [6] Wang, Q., Mao, Z., Wang, B., Guo, L.: Knowledge graph embedding: A survey of approaches and applications. IEEE Transactions on Knowledge and Data Engineering 29(12), 2724–2743 (2017)
  * [7] Kivelä, M., Arenas, A., Barthelemy, M., Gleeson, J.P., Moreno, Y., Porter, M.A.: Multilayer networks. Journal of complex networks 2(3), 203–271 (2014)
  * [8] Gray, W.R., Bogovic, J.A., Vogelstein, J.T., Landman, B.A., Prince, J.L., Vogelstein, R.J.: Magnetic resonance connectome automated pipeline: an overview. Pulse, IEEE 3(2), 42–48 (2012)
  * [9] Levin, K., Athreya, A., Tang, M., Lyzinski, V., Park, C.E. Y. Priebe: A central limit theorem for an omnibus embedding of multiple random graphs and implications for multiscale network inference. arXiv preprint arXiv:1705.09355 (2017)
  * [10] Chen, L., Vogelstein, J.T., Lyzinski, V., Priebe, C.E.: A joint graph inference case study: the c. elegans chemical and electrical connectomes. In: Worm, vol. 5 (2016). Taylor & Francis
  * [11] Arroyo, J., Athreya, A., Cape, J., Chen, G., Priebe, C.E., Vogelstein, J.T.: Inference for multiple heterogeneous networks with a common invariant subspace. arXiv preprint arXiv:1906.10026 (2019)
  * [12] Durante, D., Dunson, D.B., et al.: Bayesian inference and testing of group differences in brain networks. Bayesian Analysis 13(1), 29–58 (2018)
  * [13] Lin, L., Liu, X., Zhu, S.-C.: Layered graph matching with composite cluster sampling. IEEE Transactions on Pattern Analysis and Machine Intelligence 32(8), 1426–1442 (2010)
  * [14] Yartseva, L., Grossglauser, M.: On the performance of percolation graph matching. In: Proceedings of the First ACM Conference on Online Social Networks, pp. 119–130 (2013)
  * [15] Ding, X., Zhang, L., Wan, Z., Gu, M.: A brief survey on de-anonymization attacks in online social networks. In: 2010 International Conference on Computational Aspects of Social Networks, pp. 611–615 (2010). IEEE
  * [16] Conte, D., Foggia, P., Sansone, C., Vento, M.: Thirty years of graph matching in pattern recognition. International Journal of Pattern Recognition and Artificial Intelligence 18(03), 265–298 (2004)
  * [17] Foggia, P., Percannella, G., Vento, M.: Graph matching and learning in pattern recognition in the last 10 years. International Journal of Pattern Recognition and Artificial Intelligence 28(01), 1450001 (2014)
  * [18] Emmert-Streib, F., Dehmer, M., Shi, Y.: Fifty years of graph matching, network alignment and network comparison. Information sciences 346–347, 180–197 (2016)
  * [19] Babai, L.: Graph isomorphism in quasipolynomial time. In: Proceedings of the Forty-eighth Annual ACM Symposium on Theory of Computing, pp. 684–697 (2016). ACM
  * [20] Fishkind, D.E., Adali, S., Patsolic, H.G., Meng, L., Singh, D., Lyzinski, V., Priebe, C.E.: Seeded graph matching. Pattern Recognition 87, 203–215 (2019)
  * [21] Umeyama, S.: An eigendecomposition approach to weighted graph matching problems. Pattern Analysis and Machine Intelligence, IEEE Transactions on 10(5), 695–703 (1988)
  * [22] Singh, R., Xu, J., Berger, B.: Pairwise global alignment of protein interaction networks by matching neighborhood topology. In: Annual International Conference on Research in Computational Molecular Biology, pp. 16–31 (2007). Springer
  * [23] Zaslavskiy, M., Bach, F., Vert, J.-P.: A path following algorithm for the graph matching problem. IEEE Transactions on Pattern Analysis and Machine Intelligence 31(12), 2227–2242 (2009)
  * [24] Zhou, F., De la Torre, F.: Factorized graph matching. In: Computer Vision and Pattern Recognition (CVPR), 2012 IEEE Conference On, pp. 127–134 (2012). IEEE
  * [25] Vogelstein, J.T., Conroy, J.M., Lyzinski, V., Podrazik, L.J., Kratzer, S.G., Harley, E.T., Fishkind, D.E., Vogelstein, R.J., Priebe, C.E.: Fast Approximate Quadratic Programming for Graph Matching. PLoS ONE 10(04) (2014)
  * [26] Zhang, S., Tong, H.: Final: Fast attributed network alignment. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1345–1354 (2016)
  * [27] Feizi, S., Quon, G., Recamonde-Mendoza, M., Médard, M., Kellis, M., Jadbabaie, A.: Spectral alignment of networks. arXiv preprint arXiv:1602.04181 (2016)
  * [28] Heimann, M., Shen, H., Safavi, T., Koutra, D.: Regal: Representation learning-based graph alignment. In: Proceedings of the 27th ACM International Conference on Information and Knowledge Management, pp. 117–126 (2018)
  * [29] Pedarsani, P., Grossglauser, M.: On the privacy of anonymized networks. In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1235–1243 (2011). ACM
  * [30] Patsolic, H., Adali, S., Vogelstein, J.T., Park, Y., Priebe, C.E., Li, G., Lyzinski, V.: Seeded graph matching via joint optimization of fidelity and commensurability. arXiv preprint arXiv:1401.3813 (2014 (2019 major revision))
  * [31] Cullina, D., Kiyavash, N.: Improved achievability and converse bounds for erdos-renyi graph matching. In: ACM SIGMETRICS Performance Evaluation Review, vol. 44, pp. 63–72 (2016). ACM
  * [32] Lyzinski, V., Fishkind, D.E., Fiori, M., Vogelstein, J.T., Priebe, C.E., Sapiro, G.: Graph matching: Relax at your own risk. IEEE Transactions on Pattern Analysis and Machine Intelligence 38(1), 60–73 (2016)
  * [33] Cullina, D., Kiyavash, N.: Exact alignment recovery for correlated erdos renyi graphs. CoRR abs/1711.06783 (2017)
  * [34] Sussman, D.L., Park, Y., Priebe, C.E., Lyzinski, V.: Matched filters for noisy induced subgraph detection. IEEE Transactions on Pattern Analysis and Machine Intelligence (2019)
  * [35] Cullina, D., Kiyavash, N., Mittal, P., Poor, H.V.: 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)
  * [36] Fan, Z., Mao, C., Wu, Y., Xu, J.: Spectral graph matching and regularized quadratic relaxations ii: Erd$\backslash$h $\\{$o$\\}$ sr$\backslash$’enyi graphs and universality. arXiv preprint arXiv:1907.08883 (2019)
  * [37] Ding, J., Ma, Z., Wu, Y., Xu, J.: Efficient random graph matching via degree profiles. Probability Theory and Related Fields, 1–87 (2020)
  * [38] Mossel, E., Xu, J.: Seeded graph matching via large neighborhood statistics. Random Structures & Algorithms 57(3), 570–611 (2020)
  * [39] Fishkind, D.E., Meng, L., Sun, A., Priebe, C.E., Lyzinski, V.: Alignment strength and correlation for graphs. Pattern Recognition Letters 125, 295–302 (2019)
  * [40] Onaran, E., Garg, S., Erkip, E.: Optimal de-anonymization in random graphs with community structure. arXiv preprint arXiv:1602.01409 (2016)
  * [41] Shirani, F., Garg, S., Erkip, E.: Matching graphs with community structure: A concentration of measure approach. In: 2018 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 1028–1035 (2018). IEEE
  * [42] Lyzinski, V.: Information recovery in shuffled graphs via graph matching. IEEE Transactions on Information Theory 64(5), 3254–3273 (2018)
  * [43] Lyzinski, V., Sussman, D.L.: Matchability of heterogeneous networks pairs. Information and Inference: A Journal of the IMA 9(4), 749–783 (2020)
  * [44] Barak, B., Chou, C., Lei, Z., Schramm, T., Sheng, Y.: (nearly) efficient algorithms for the graph matching problem on correlated random graphs. In: Advances in Neural Information Processing Systems, pp. 9190–9198 (2019)
  * [45] Lyzinski, V., Fishkind, D.E., Priebe, C.E.: Seeded graph matching for correlated Erdos-Renyi graphs. Journal of Machine Learning Research 15, 3513–3540 (2014)
  * [46] Priebe, C.E., Park, Y., Vogelstein, J.T., Conroy, J.M., Lyzinski, V., Tang, M., Athreya, A., Cape, J., Bridgeford, E.: On a two-truths phenomenon in spectral graph clustering. Proc. Natl. Acad. Sci. U.S.A. 116(13), 5995–6000 (2019). doi:10.1073/pnas.1814462116
  * [47] Chung, J., Bridgeford, E., Arroyo, J., Pedigo, B.D., Saad-Eldin, A., Gopalakrishnan, V., Xiang, L., Priebe, C.E., Vogelstein, J.T.: Statistical Connectomics. OSF Preprints (2020). doi:10.31219/osf.io/ek4n3
  * [48] Zuo, X.-N., Anderson, J.S., Bellec, P., Birn, R.M., Biswal, B.B., Blautzik, J., Breitner, J.C.S., Buckner, R.L., Calhoun, V.D., Castellanos, F.X., Chen, A., Chen, B., Chen, J., Chen, X., Colcombe, S.J., Courtney, W., Craddock, R.C., Di Martino, A., Dong, H.-M., Fu, X., Gong, Q., Gorgolewski, K.J., Han, Y., He, Y., He, Y., Ho, E., Holmes, A., Hou, X.-H., Huckins, J., Jiang, T., Jiang, Y., Kelley, W., Kelly, C., King, M., LaConte, S.M., Lainhart, J.E., Lei, X., Li, H.-J., Li, K., Li, K., Lin, Q., Liu, D., Liu, J., Liu, X., Liu, Y., Lu, G., Lu, J., Luna, B., Luo, J., Lurie, D., Mao, Y., Margulies, D.S., Mayer, A.R., Meindl, T., Meyerand, M.E., Nan, W., Nielsen, J.A., O’Connor, D., Paulsen, D., Prabhakaran, V., Qi, Z., Qiu, J., Shao, C., Shehzad, Z., Tang, W., Villringer, A., Wang, H., Wang, K., Wei, D., Wei, G.-X., Weng, X.-C., Wu, X., Xu, T., Yang, N., Yang, Z., Zang, Y.-F., Zhang, L., Zhang, Q., Zhang, Z., Zhang, Z., Zhao, K., Zhen, Z., Zhou, Y., Zhu, X.-T., Milham, M.P.: An open science resource for establishing reliability and reproducibility in functional connectomics. Sci. Data 1(140049), 1–13 (2014). doi:10.1038/sdata.2014.49
  * [49] Kiar, G., Bridgeford, E.W., Gray Roncal, W.R., , Chandrashekhar, V., Mhembere, D., Ryman, S., Zuo, X.-N., Margulies, D.S., Craddock, R.C., Priebe, C.E., Jung, R., Calhoun, V.D., Caffo, B., Burns, R., Milham, M.P., Vogelstein, J.T.: A High-Throughput Pipeline Identifies Robust Connectomes But Troublesome Variability. bioRxiv, 188706 (2018). 188706
  * [50] Mhembere, D., Roncal, W.G., Sussman, D., Priebe, C.E., Burns, R.: Computing Scalable Multivariate Glocal Invariants of Large (Brain-) Graphs. 2013 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2013 - Proceedings (2013). doi:10.1109/GlobalSIP.2013.6736874
  * [51] Varshney, L.R., Chen, B.L., Paniagua, E., Hall, D.H., Chklovskii, D.B.: Structural Properties of the Caenorhabditis elegans Neuronal Network. PLoS Comput. Biol. 7(2), 1001066 (2011). doi:10.1371/journal.pcbi.1001066
  * [52] C. elegans Sequencing Consortium: Genome sequence of the nematode C. elegans: a platform for investigating biology. Science 282(5396), 2012–2018 (1998). doi:10.1126/science.282.5396.2012. 9851916
  * [53] White, J.G., Southgate, E., Thomson, J.N., Brenner, S.: The structure of the nervous system of the nematode Caenorhabditis elegans. Philos. Trans. R. Soc. London, Ser. B 314(1165), 1–340 (1986). doi:10.1098/rstb.1986.0056. 22462104
  * [54] Bargmann, C.I.: Neurobiology of the Caenorhabditis elegans genome. Science 282(5396), 2028–2033 (1998). doi:10.1126/science.282.5396.2028. 9851919
  * [55] Arnatkevic̆iūtė, A., Fulcher, B.D., Pocock, R., Fornito, A.: Hub connectivity, neuronal diversity, and gene expression in the Caenorhabditis elegans connectome. PLoS Comput. Biol. 14(2), 1005989 (2018). doi:10.1371/journal.pcbi.1005989
  * [56] Priebe, C.E., Conroy, J.M., Marchette, D.J., Park, Y.: Scan statistics on enron graphs. Comput. Math. Org. Theory 11(3), 229–247 (2005)