# Network Recovery from Unlabeled Noisy Samples ††thanks: This research was
partially supported by ARO award W911NF1810237.

Nathaniel Josephs, Wenrui Li, and Eric. D. Kolaczyk  Dep. of Math. and Stat.
Boston University
Boston, MA, 02215, USA
{njosephs, wenruili<EMAIL_ADDRESS>
###### Abstract

There is a growing literature on the statistical analysis of multiple networks
in which the network is the fundamental data object. However, most of this
work requires networks on a shared set of labeled vertices. In this work, we
consider the question of recovering a parent network based on noisy unlabeled
samples. We identify a specific regime in the noisy network literature for
recovery that is asymptotically unbiased and computationally tractable based
on a three-stage recovery procedure: first, we align the networks via a
sequential pairwise graph matching procedure; next, we compute the sample
average of the aligned networks; finally, we obtain an estimate of the parent
by thresholding the sample average. Previous work on multiple unlabeled
networks is only possible for trivial networks due to the complexity of brute-
force computations.

###### Index Terms:

multiple networks, noisy, unlabeled, unbiased recovery, signal-plus-noise,
correlated Erdős-Rényi

##  I Introduction

Networks are widely used across various scientific disciplines and are the
preeminent method for representing relational data. The study of individual
networks is well established, but technological advances are making data sets
with multiple networks increasingly common. Consequently, there is a growing
literature on the statistical analysis of multiple network data that includes
solutions for estimating a population network based on noisy realizations [1,
2], modeling distributions over networks [3], and averaging [4, 5], hypothesis
testing [6, 7], and classification [8, 9] for collections of networks. There
is also a large literature on graph signal processing [10] with solutions for
combining [11], clustering [12], and classifying [13] multiple graphs. Work in
this area, including all of the aforementioned work, generally assumes
networks with labeled nodes.

Unlabeled networks, on the other hand, have been less studied, but are now
emerging as relevant objects in many areas including differential privacy and
anonymized networks [14, 15, 16], registration of brain networks due to
mismeasurement (e.g, misalignment of brain regions due to batch effects of
brain scans) [17] or to elastic shapes [18], and active learning of unlabeled
nodes [19]. Therefore, it is important to try to obtain similar tools for
studying multiple unlabeled networks.

In this work, we turn to the growing literature on noisy networks. There, a
variant of the traditional ‘signal-plus-noise’ framework has been found useful
for quantifying the uncertainty of various network characteristics due to
observing a noisy version of a true underlying network. Specifically, an
underlying network $\bm{A}$ may have some characteristic $\eta(\bm{A})$ that
is of interest, and uncertainty in either the empirical version
$\eta(\tilde{\bm{A}})$ and/or improved estimators are studied based on a noisy
observation $\tilde{\bm{A}}$. This framework has been studied when the network
characteristics of interest are subgraph counts estimated from a single noisy
network [20], as well as subgraph densities [21] and branching factors [22]
which require several noisy replicates. Herein, we assume $m\geq 2$ noisy
networks are observed, without node labels, and our goal is to recover the
entire underlying network $\bm{A}$, i.e $\eta(\cdot)$ is the identity.

In solving the problem of network recovery given a sample of unlabeled noisy
networks, we also introduce an efficient computation of the network average in
our setting. This contribution is of independent interest, since previous work
on computing averages for unlabeled networks is limited by the computational
complexity of their solutions. For instance, in [23], by characterizing the
geometry of the space of unlabeled networks and associating with that space a
Procrustean distance, the authors are led to a notion of nonparametric average
(the Fréchet mean) for which brute-force computation yields an $O((n!)^{m})$
algorithm, where $m$ is the number of networks and $n$ is the number of nodes.
Iterative approaches have been proposed based on graph matching ideas for
computing the sample Fréchet mean of unlabeled networks [4, 24, 25], but these
are $O(m(n!))$ and thus still too expensive for large networks.

The remainder of this paper is organized as follows. In Section II, we discuss
our problem setting in which multiple noisy networks are observed and we make
a connection between the ‘signal-plus-noise’ model and the correlated Erdős-
Rényi model. We introduce a three-staged approach for estimating the parent
network given a collection of unlabeled noisy networks in Section III and
discuss the theoretical properties of the resulting estimator in Section IV. A
simulation study is presented in Section V and we conclude with a discussion
of possible future directions for this work in Section VI.

##  II Noisy Networks

In the noisy network literature, one is assumed to have a noisy version
$\tilde{\bm{A}}$ of a true underlying network $\bm{A}$, where the latter is
unobserved. Interest frequently is in estimating a network characteristic
$\eta(\bm{A})$, for which the default choice is the plug-in estimate
$\eta(\tilde{\bm{A}})$. Typically, one assumes that

$\displaystyle\mathbb{P}(\tilde{A}_{uv}=1~{}|~{}A_{uv})=\begin{cases}1-\beta_{uv}&\text{if}~{}A_{uv}=1\\\
\alpha_{uv}&\text{if}~{}A_{uv}=0\end{cases}\enskip,$ (1)

where often these error rates are assumed to be constant, i.e
$\alpha_{uv}\equiv\alpha$ and $\beta_{uv}\equiv\beta$ for
$\alpha,\beta\in[0,1]$. Furthermore, in all of the settings in which multiple
replicates are observed, the node labels are implicitly assumed to be known.

Throughout, we assume that $m\geq 2$ noisy networks are observed following
(1), but their node labels are unobserved, and we are interested in recovering
the entire true underlying network $\bm{A}$. To do so, we make a connection
between the ‘signal-plus-noise’ model in (1) and the correlated Erdős-Rényi
model.

###  II-A Correlated Erdős-Rényi Model

The correlated Erdős-Rényi model was introduced by [15] and has been used
extensively in the context of graph matching [26, 17, 27, 28, 29, 30, 31, 32,
33] as well as testing edge correlation between two unlabeled graphs [34].
This popular model is defined as follows.

######  Definition II.1 (Correlated Erdős-Rényi Model)

Given an integer $n$ and $q,s\in[0,1]$, let $\tilde{\bm{A}}^{(1)}$ and
$\tilde{\bm{A}}^{(2)}$ denote the adjacency matrices of two Erdős-Rényi random
graphs on the same vertex set $[n]=\\{1,\ldots,n\\}$ with probability
$q\in[0,1]$. Let ${\pi}^{*}:[n]\rightarrow[n]$ denote a latent permutation. We
assume that conditional on $\tilde{\bm{A}}^{(1)}$, for all $u<v$,
$\tilde{A}^{(2)}_{{\pi}^{*}(u){\pi}^{*}(v)}$ are independent and distributed
as

$\displaystyle\tilde{A}^{(2)}_{{\pi}^{*}(u),{\pi}^{*}(v)}\sim\begin{cases}\text{Bern}(s)&\text{if}~{}\tilde{A}^{(1)}_{u,v}=1\\\
\text{Bern}\Big{(}\frac{q(1-s)}{1-q}\Big{)}&\text{if}~{}\tilde{A}^{(1)}_{u,v}=0\end{cases}\enskip.$

It follows from Definition II.1 that marginally we have
$\tilde{\bm{A}}^{(2)}\sim\text{ER}(n,q)$, since for all $u<v$, we have

$\displaystyle\mathbb{P}\big{(}\tilde{A}^{(2)}_{{\pi}^{*}(u),{\pi}^{*}(v)}=1\big{)}$
$\displaystyle=s\cdot\mathbb{P}(\tilde{A}^{(1)}_{u,v}=1)$ $\displaystyle\ \ \
+\frac{q(1-s)}{1-q}\cdot\mathbb{P}(\tilde{A}^{(1)}_{u,v}=0)$
$\displaystyle=s\cdot q+\frac{q(1-s)}{1-q}\cdot(1-q)$
$\displaystyle=q\enskip.$

Note that the original correlated Erdős-Rényi model in Definition II.1 can be
seen as a particular case of the ‘signal-plus-noise’ model in (1) in which the
true underlying network is Erdős-Rényi, $\alpha=0$ , and the node labels of
the noisy replicates are permuted after sampling. To see the connection
between these models, let $\tilde{\bm{A}}^{(1)}$ and $\tilde{\bm{A}}^{(2)}$ be
drawn from (1), whose entries above the diagonal are independent conditional
on some $\bm{A}\sim ER(n,p)$. Suppose the nodes in $\tilde{\bm{A}}^{(2)}$ are
then permuted by a latent permutation $\pi^{*}$. It follows that
$\tilde{\bm{A}}^{(1)}$ and $\tilde{\bm{A}}^{(2)}$ are samples from a
correlated Erdős-Rényi model by letting $q$ and $s$ satisfy

$\displaystyle\begin{split}q&=p(1-\beta)+(1-p)\alpha\enskip,\\\
s&=\frac{p(1-\beta)^{2}+(1-p)\alpha^{2}}{p(1-\beta)+(1-p)\alpha}\enskip.\end{split}$
(2)

When $\alpha=0$, this reduces to the equivalent generative formulation of the
correlated Erdős-Rényi model in Definition II.1 with $q=ps$ and $s=1-\beta$.

This insight – that $q$ and $s$ can be defined to include $\alpha>0$ – allows
us to view the correlated Erdős-Rényi graph model as a generative formulation
of two networks being noisy samples of some (unknown) true underlying Erdős-
Rényi network. These samples have the same natural interpretation as noisy
replicates in the ‘signal-plus-noise’ model, which are noisy unlabeled
observations of a true underlying network. Furthermore, $\alpha>0$ enriches
the correlated Erdős-Rényi model by allowing for the common scenario of
observing a spurious edge while simultaneously retaining the efficient
solutions designed for graph matching in the correlated Erdős-Rényi setting.
Finally, by taking this generative perspective, it becomes clear that a
collection of noisy networks from (1) has the property that each pair comes
from a correlated Erdős-Rényi model with the same parent if that parent is
assumed to be Erdős-Rényi.

##  III Recovery

In this section, we propose a three-staged approach for recovering an
underlying network based on multiple unlabeled noisy networks. The first stage
involves aligning the unlabeled noisy networks via a sequential pairwise graph
matching procedure. This procedure yields estimates of the latent
permutations. In the second stage, we align the networks via their estimated
permutations and compute the sample average

$\displaystyle\bar{\bm{A}}=\frac{1}{m}\sum_{i=1}^{m}\hat{\bm{A}}^{(i)}\enskip,$
(3)

where $\hat{\bm{A}}^{(i)}$ denotes the adjacency matrix for
$\tilde{\bm{A}}^{(i)}$ that has been aligned to
$\tilde{\bm{A}}^{(1)}\equiv\hat{\bm{A}}^{(1)}$. We obtain our estimate of the
parent network in the final stage by binarizing each entry of the sample
average from (3) based on some threshold $w$:

$\displaystyle\hat{A}_{uv}=\begin{cases}1&\text{if}~{}\bar{A}_{uv}>w\\\
0&\text{if}~{}\bar{A}_{uv}<w\end{cases}\enskip.$ (4)

In the remainder of this section, we provide details for the sequential graph
matching procedure and we discuss its computational cost as well as two
improvements beyond the pairwise approach in the case that $m>2$.

###  III-A Multiple Graph Matching

Given a collection of unlabeled networks
$\tilde{\bm{A}}^{(1)},\ldots,\tilde{\bm{A}}^{(m)}$ sampled independently from
(1) conditional on some fixed but unknown $\bm{A}$, we estimate the latent
permutations in order to find a common alignment. We do this by leveraging
results from the graph matching literature [35, 36, 37]. The graph matching
problem is to find an optimal alignment, or an isomorphism depending on if an
exact solution is possible, given two unlabeled networks.

There have been several graph matching techniques specfically designed for
correlated Erdős-Rényi networks including seeded graph matching [17],
percolation graph matching [26, 29], canonical labeling [27], and $k$-core
alignment [28]. Herein, we choose to match $\tilde{\bm{A}}^{(i+1)}$ to
$\tilde{\bm{A}}^{(i)}$ using degree profiles [30] because of its probabilistic
guarantees for exact recovery.

A degree profile is the empirical distribution of the degrees of a node’s
neighbors, which is computed for each node in each network. Matching occurs by
defining a distance matrix $Z^{(i,j)}$, where $Z_{uv}^{(i,j)}$ is the total
variation distance between the degree profiles of nodes $u$ and $v$ in
$\tilde{\bm{A}}^{(i)}$ and $\tilde{\bm{A}}^{(j)}$. Ding et al. [30] prove that
for correlated Erdős-Rényi networks (with $\alpha=0$), under certain
conditions, the smallest $n$ entries of $Z$ recovers the exact permutation
with high probability.

When the assumptions required in [30] do not hold, the authors recommend
outputting an approximation, which can be accomplished by solving the
following linear assignment problem:

$\underset{S:|S|=n}{\min}\quad\sum_{(u,v)}|Z_{uv}^{(i,j)}|\quad\text{s.t
}S=\\{(u,v)\\}\text{ is a permutation}\enskip.$

We apply this procedure sequentially, which is summarized in Algorithm 1. Note
that Algorithm 1 can be implemented in parallel and therefore has the same
computational cost as Algorithm 1 in [30] for $m=2$, which is
$O(nd^{2}+n^{2})$, where $d$ is the average degree.

Multi-graph match
$\big{(}\tilde{\bm{A}}^{(1)},\ldots,\tilde{\bm{A}}^{(m)}\big{)}$;

Input : $m$ unlabeled noisy networks,
$\big{\\{}\tilde{\bm{A}}^{(i)}\big{\\}}_{i=1}^{m}$, on $n$ nodes

Output : $m-1$ permutations
$\hat{\pi}^{(1,2)},\hat{\pi}^{(2,3)},\cdots,\hat{\pi}^{(m-1,m)}$

for  _$i\in[m-1]$_ do in parallel

Match $\tilde{\bm{A}}^{(i)}$ and $\tilde{\bm{A}}^{(i+1)}$ by degree profiles
[30] to obtain $\hat{\pi}^{(i,i+1)}$;

end forpar

Algorithm 1 Sequential pairwise graph matching procedure for aligning multiple
unlabeled noisy networks.

Given $\hat{\pi}^{(1,2)},\ldots,\hat{\pi}^{(m-1,m)}$ from Algorithm 1, let
$\hat{\bm{A}}^{(i)}$ denote the adjacency matrix for $\tilde{\bm{A}}^{(i)}$
that has been realigned to $\tilde{\bm{A}}^{(1)}\equiv\hat{\bm{A}}^{(1)}$ for
all $i=2,\ldots,m$ based on the composition of the estimated permutations, i.e

$\displaystyle\hat{A}^{(i)}_{uv}=\tilde{A}^{(i)}_{\hat{\pi}^{(i)}(u),\hat{\pi}^{(i)}(v)}\enskip,$
(5)

where $\hat{\pi}^{(i)}=\hat{\pi}^{(1,2)}\circ\cdots\circ\hat{\pi}^{(i-1,i)}$
for $i=2,\ldots,m$. With this notation, we can compute our sample average in
(3). Note that this average is conditional on the estimated permutations
$\hat{\pi}^{(i-1,i)}$ for all $i=2,\ldots,m$, and if these estimated
permutations are correct, then this coincides with the sample Frèchet mean of
$\tilde{\bm{A}}^{(1)},\ldots,\tilde{\bm{A}}^{(m)}$ induced by the Frobenius
distance, i.e

$\widehat{\mu_{m}}:=\underset{\bm{A}\in\mathcal{G}}{\arg\min}\frac{1}{m}\sum_{i=1}^{m}d_{\text{F}}^{2}\big{(}\bm{A},\tilde{\bm{A}}^{(i)}\big{)}\enskip,$

where $\mathcal{G}$ is our space of networks and

$d_{\text{F}}^{2}\big{(}\bm{A}^{(i)},\bm{A}^{(j)}\big{)}=\frac{1}{n(n-1)}\sum_{u,v\in[n]}\big{(}A_{uv}^{(i)}-A_{uv}^{(j)}\big{)}^{2}\enskip.$
(6)

However, note that we are computing a sample average and do not have a notion
of population, since our samples are noisy versions of a single fixed network.
This is in contrast to the Frèchet mean estimated in [23], which is an
estimate of a population average over a given distribution of unlabeled
networks.

In Section IV, we prove under certain conditions that $\hat{\bm{A}}$ in (4)
based on $\bar{\bm{A}}$ has nice properties in terms of recovering the latent
parent network $\bm{A}$. When these conditions do not hold, though, we can
still improve this estimate by borrowing information across networks. We
describe two such methods next.

###  III-B Cleanup Procedure and Seeded Matching

In [30], the authors propose an iterative cleanup procedure, which solves the
following sparse linear assignment problem for a prespecified number of
iterations $t=1,\ldots,T$:

$\displaystyle\hat{\pi}^{(i,j)}_{t}=\arg\max_{\pi}\langle\pi,\tilde{\bm{A}}^{(i)}\hat{\pi}^{(i,j)}_{t-1}\tilde{\bm{A}}^{(j)}\rangle\enskip,$
(7)

where $\hat{\pi}^{(i,j)}$ is initialized from the output of the graph matching
procedure.

We can improve this given $m>2$ networks by iteratively cleaning up pairs of
networks, which we summarize in Algorithm 2. This adds little computational
overhead as the optimization in (7) is for sparse matrices ($\pi$ is a
permutation matrix and thus
$\tilde{\bm{A}}^{(i)}\hat{\pi}^{(i,j)}_{t-1}\tilde{\bm{A}}^{(j)}$ is sparse),
which has highly efficient implementations using the Jonker-Volgenant
algorithms [38].

Multi-graph cleanup $\big{(}\hat{\pi}^{(2)},\ldots,\hat{\pi}^{(m)}\big{)}$;

Input : $m-1$ permutations composed from output of Algorithm 1

Output : $m-1$ permutations $\hat{\pi}^{(1)},\cdots,\hat{\pi}^{(m)}$

repeat

Sample $i<j$ randomly;

for  _$t=1,\ldots,T$_ do

$\hat{\pi}^{(j)}_{t}=\arg\max_{\pi}\langle\pi,\hat{\bm{A}}^{(i)}\hat{\pi}^{(j)}_{t-1}\tilde{\bm{A}}^{(j)}\rangle$

end for

until  _convergence_ ;

Algorithm 2 Cleanup procedure for multiple graph matching.

Another approach to improving the sequential alignment procedure by
incorporating the multiple samples is through seeded matching. In graph
matching, seeds are pairs of corresponding vertices between the two graphs
that are prespecified prior to running the algorithm. For matching via degree
profiles, seeds are given as matched pairs

$S=\big{\\{}(u,v):a_{u}\geq\tau,b_{v}\geq\tau^{\prime},Z_{uv}\leq\xi\big{\\}}\enskip,$
(8)

where $u$ and $v$ are nodes with high degrees $a_{u}$ and $b_{v}$,
respectively, whose degree profiles are close in distance. This is
particularly useful for dense graphs, but still requires a sufficient number
of seeds to have probabilistic guarantees.

We can expand the definition of seeds recursively to leverage the additional
information when $m>2$ as follows:

$\begin{split}\tilde{S}^{(i,j)}=\bigcup_{k=1}^{m}\ \big{\\{}(u,v):\exists\
w\text{ s.t }&(u,w)\in\tilde{S}^{(i,k)},\\\
&(w,v)\in\tilde{S}^{(k,j)}\big{\\}}\enskip,\end{split}$

where $\tilde{S}^{(i,i+1)}$ is initiated as in (8) for $i=1,\ldots,m-1$.

Note that the degree profiles for every node in every network are already
computed in Algorithm 1. Therefore, we only need to compute
$\binom{m}{2}-(m-1)\approx\frac{m^{2}}{2}$ additional pairwise comparisons
since $Z^{(i,i+1)}$ is already computed for $i=1,\ldots,m-1$. Furthermore,
$|\tilde{S}^{(i,j)}|$ is bounded above by $(1-\frac{\log n}{nq})$-quantile of
Binomial$(n-1,q)$, so the search time for the recursion is also bounded.

##  IV Theoretical Results

In this section, we provide a probabilistic guarantee for when Algorithm 1
exactly recovers the latent permutations. Then, conditional on these latent
permutations, we show that our estimate of the true underlying network from
(4) is asymptotically unbiased.

###  IV-A Algorithm 1 Performance

We begin by showing that, with high probability, Algorithm 1 can move us from
an unlabeled network problem to a labeled network problem by exactly
recovering the latent permutations.

###### Theorem IV.1

Let $\tilde{\bm{A}}^{(1)},\ldots,\tilde{\bm{A}}^{(m)}$ be a collection of
unlabeled networks sampled independently from (1) conditional on some fixed
but unknown $\bm{A}\sim\text{ER}(n,q)$. Let $q$ and $s$ satisfy (2). If
$\sigma^{2}=1-s$ and $q\leq 1/12$ with

$\sigma\leq\frac{\sigma_{0}}{\log n},\qquad L=L_{0}\log n,\qquad nq\geq
C_{0}\log^{2}n\enskip,$

for a sufficiently small constant $\sigma_{0}$ and sufficiently large
constants $L_{0}$ and $C_{0}$, then with probability $1-O(1/n)$, Algorithm 1
outputs $\hat{\pi}=\pi^{*}$. It follows that Algorithm 1 outputs

$\hat{\pi}^{(i,i+1)}={\pi}^{*(i,i+1)}\enskip,$

for all $i\in[m-1]$ with probability $1-O(m/n)$.

The proof of Theorem IV.1 is straightforward. The first part is just Theorem 1
from [30], but with the recognition that if $\alpha>0$, then, for any
$\beta\in[0,1]$, $q$ and $s$ must be defined by (2). The conclusion follows
from the fact that each permutation is recovered with probability $1-O(1/n)$,
hence the probability of recovering all $m-1$ permutations is $1-O(m/n)$.
Therefore, we obtain exact recovery if $m=o(n)$, i.e so long as the network
order grows faster than the sample size.

It may seem counterintuitive that the likelihood of recovery should decrease
as our sample size increases. This is due to the fact that our procedure takes
a pairwise graph matching approach and so each comparison reduces the
probability of the overall recovery. However, in practice, we see that the
methods in Section III-B help mitigate the loss of accuracy as $m$ increases,
which offsets the decrease in Theorem IV.1.

###  IV-B Unbiased Recovery

Here, we show that an unbiased estimator of the parent network can be defined
as a function of the average of the aligned networks.

First, we have

$\begin{split}\mathbb{E}[\bar{A}_{uv}~{}|~{}\bm{A}]&=\mathbb{E}[\bar{A}_{uv}~{}|~{}\bm{A},\hat{\pi}=\pi^{*}]\mathbb{P}(\hat{\pi}=\pi^{*}~{}|~{}\bm{A})\\\
&\ \ \ +O(\mathbb{P}(\hat{\pi}\neq\pi^{*}~{}|~{}\bm{A}))\enskip.\end{split}$
(9)

Note that the exact recovery in Theorem IV.1 is marginal, i.e not conditional
on $\bm{A}$. We can overcome this with the following assumption.

###### Assumption 1

$\mathbb{P}(\bm{A}~{}|~{}\hat{\pi}=\pi^{*})\geq\mathbb{P}(\bm{A})\enskip.$

Assumption 1 implies that parent networks have higher likelihoods when
matching via degree profiles successfully recovers the latent permutation of
two noisy replicates. This assumption can be expected to be difficult to
verify in practice, given that unsurprisingly the conditional likelihood is
intractable. Nevertheless, this is intuitively reasonable and is also
corroborated by simulation.

It follows from Assumption 1 that $\hat{\pi}=\pi^{*}$ with high probability
conditional on $\bm{A}$:

$\displaystyle\mathbb{P}(\hat{\pi}=\pi^{*}~{}|~{}\bm{A})$
$\displaystyle=\frac{\mathbb{P}(\bm{A}~{}|~{}\hat{\pi}=\pi^{*})\mathbb{P}(\hat{\pi}=\pi^{*})}{\mathbb{P}(\bm{A})}$
$\displaystyle\geq\frac{\mathbb{P}(\bm{A})\mathbb{P}(\hat{\pi}=\pi^{*})}{\mathbb{P}(\bm{A})}$
$\displaystyle=\mathbb{P}(\hat{\pi}=\pi^{*})$
$\displaystyle=1~{}\text{as}~{}n\to\infty\enskip.$

From the definition of the aligned average in (3), we have

$\displaystyle\mathbb{E}[\bar{A}_{uv}~{}|~{}\bm{A},\hat{\pi}=\pi^{*}]$
$\displaystyle=\frac{1}{m}\sum_{i=1}^{m}\mathbb{E}[\tilde{A}^{(i)}_{uv}~{}|~{}A_{uv},\hat{\pi}=\pi^{*}]$
$\displaystyle=\frac{1}{m}\sum_{i=1}^{m}(1-\beta)\cdot{A_{uv}}+\alpha\cdot(1-A_{uv})$
$\displaystyle=\begin{cases}1-\beta&A_{uv}=1\\\
\alpha&A_{uv}=0\end{cases}\enskip.$

Therefore, for large $n$, we have unbiased recovery of $\bm{A}$ when there is
adequate separation between the noise rates.

###### Assumption 2

$1-\beta>\alpha\enskip.$

Assumption 2 stipulates that there is enough signal compared to the noise in
(1) and is much weaker than other methods in the noisy network literature that
require the noise rates to be known or estimated. We do not need to know
$\alpha$ or $\beta$, but rather an appropriate threshold $w$ that separates
true edges from spurious ones. In practice, $w$ is also unknown, but we find
that an elbow method works well empirically for choosing a break $\hat{w}$ in
estimated edge weights for our estimate in (4).

Given $w$ or an unbiased estimate $\hat{w}$, it follows that, with high
probability, we have an unbiased estimate of $\bm{A}$, i.e for all $u,v$,

$\mathbb{E}[\hat{A}_{uv}~{}|~{}\bm{A}]\to
A_{uv}~{}\text{as}~{}n\to\infty\enskip.$

Furthermore, the assumption of independent noise implies
$\hat{\bm{A}}^{(1)},\ldots,\hat{\bm{A}}^{(m)}$ are independent conditional on
$\bm{A}$. Therefore, the central limit theorem from [5] for labeled networks
holds for our sample average $\bar{\bm{A}}$ in (3) in case confidence
intervals are desired.

##  V Simulations

In this section, we present the results from a simulation study. All of the
code for our algorithms and reproducing our simulation is available at
https://github.com/KolaczykResearch/NetworkRecovery.

We mimic the setup in Figure 5 of [30] by varying $n$ and $\beta$ while
letting $p=\log^{2}(n)/n$. However, we also vary $m$, as well as introducing
$\alpha>0$, which we do by setting $\alpha$ to satisfy edge unbiasededness,
i.e

$\alpha\cdot|E^{c}|=\beta\cdot|E|\enskip.$

The assumption of edge unbiasedness guarantees the expected number of edges in
the noisy observation is equal to the number of edges, $|E|$, in the true
network. This also ensures that Assumption 2 is satisfied for large $n$
because $\alpha~{}=~{}\Theta(\beta~{}\cdot~{}\log^{2}(n)~{}/~{}n)$ and hence
$\hat{w}=.5$ can be used an appropriate threshold.

For each of the simulation parameters, we compute the fraction of correctly
matched pairs, the squared Frobenius distance in (6) between $\bar{\bm{A}}$
and $\bm{A}$, and the fraction of correctly identified edges and non-edges
between $\hat{\bm{A}}$ and $\bm{A}$. These are referred to as Recovery,
Frobenius, and Accuracy, respectively. For each of the settings, we run 10
independent trials and report the median for each of these measures. The
results are given in Figure 1.

Figure 1: Results from the simulation. The rows represent the number of
networks $m$ and the colors represent the number of nodes $n$. The columns
display different accuracy measurements, where the first and second show the
Frobenius distance and accuracy, respectively, between the aligned average
from (3) and the estimate from (4) compared to the true underlying network.
The third column shows the accuracy of multi-graph matching with multi-graph
cleanup from Algorithms 1 and 2.

The rightmost column for Recovery parallels the findings in Figure 5 of [30].
In particular, we have the same results even with $m>2$ and $\alpha>0$, which
is what we would expect from Theorem IV.1. Furthermore, Frobenius is low and
Accuracy is high when Recovery is high, which is also what we would expect.
The plateaus in Frobenius and Accuracy as $\sqrt{\beta}\log(n)$ increases
correspond to the fact that $p=\log^{2}(n)/n$, i.e as $n$ increases, the
density decreases and thus most potential edges are (correctly) predicted to
be absent. Finally, it is worth noting that the sharp decline in the results
around $\sqrt{\beta}\log(n)\geq 0.7$ has been described as “all-or-nothing
recovery” and is being extensively studied in the case of $\alpha=0$ [31, 32,
33].

##  VI Conclusion

###  VI-A Summary

In this work, we turned our attention to the underdeveloped area of multiple
unlabeled networks. In order to overcome the additional combinatorial
challenge arising from node permutations, we focused on networks arising from
a ‘signal-plus-noise’ model in which the observed networks are unlabeled noisy
samples from a true underlying network. This setting allowed us to leverage
results from the graph matching literature and we developed a procedure that
sequentially aligns the unlabeled networks by recovering the latent
permutations. In doing so, we moved the problem to the labeled setting with
high probability, which yielded an unbiased estimator of the underlying
network. This solution is computationally efficient and will hopefully serve
as a starting point for future analysis of multiple unlabeled networks.

###  VI-B Future Work

The theoretical guarantee of the performance of graph matching via degree
profiles relies on the distribution of the node degrees in each network.
Originally, the authors only considered the correlated Erdős-Rényi model given
in Definition II.1. In this setting, the node degrees are binomial random
variables and hence exhibit nice tail bounds. As we verified, the theory holds
in the generative framework even when $\alpha$, the type I noise rate, is
positive. However, we still only considered the case when the true underlying
network $\bm{A}$ is Erdős-Rényi, hence the edge probabilities for the
underlying network $\bm{A}$ are homogeneous. It is worth pursuing whether the
results hold if the true underlying network $\bm{A}$ is from an inhomogeneous
Erdős-Rényi in which the true edges are still drawn from Bernoulli
distributions but with possibly different probabilities.

Another interesting question is whether the results hold in the case where the
number of nodes is random. We could achieve this by assuming a Poisson
distribution on the network order, thus inducing a hierarchical model.

## References

  * [1] C. M. Le, K. Levin, E. Levina _et al._ , “Estimating a network from multiple noisy realizations,” _Electronic Journal of Statistics_ , vol. 12, no. 2, pp. 4697–4740, 2018.
  * [2] L. Wang, Z. Zhang, D. Dunson _et al._ , “Common and individual structure of brain networks,” _The Annals of Applied Statistics_ , vol. 13, no. 1, pp. 85–112, 2019.
  * [3] D. Durante, D. B. Dunson, and J. T. Vogelstein, “Nonparametric bayes modeling of populations of networks,” _Journal of the American Statistical Association_ , vol. 112, no. 520, pp. 1516–1530, 2017.
  * [4] B. J. Jain, “Statistical graph space analysis,” _Pattern Recognition_ , vol. 60, pp. 802–812, 2016.
  * [5] C. E. Ginestet, J. Li, P. Balachandran, S. Rosenberg, and E. D. Kolaczyk, “Hypothesis testing for network data in functional neuroimaging,” _The Annals of Applied Statistics_ , vol. 11, no. 2, pp. 725–750, 2017.
  * [6] D. Ghoshdastidar, M. Gutzeit, A. Carpentier, U. Von Luxburg _et al._ , “Two-sample hypothesis testing for inhomogeneous random graphs,” _Annals of Statistics_ , vol. 48, no. 4, pp. 2208–2229, 2020.
  * [7] L. Chen, N. Josephs, L. Lin, J. Zhou, and E. D. Kolaczyk, “A spectral-based framework for hypothesis testing in populations of networks,” _arXiv preprint arXiv:2011.12416_ , 2020.
  * [8] J. D. Arroyo Relión, D. Kessler, E. Levina, and S. F. Taylor, “Network classification with applications to brain connectomics,” _The Annals of Applied Statistics_ , vol. 13, no. 3, p. 1648, 2019.
  * [9] N. Josephs, L. Lin, S. Rosenberg, and E. D. Kolaczyk, “Bayesian classification, anomaly detection, and survival analysis using network inputs with application to the microbiome,” _arXiv preprint arXiv:2004.04765_ , 2020\.
  * [10] A. Ortega, P. Frossard, J. Kovačević, J. M. Moura, and P. Vandergheynst, “Graph signal processing: Overview, challenges, and applications,” _Proceedings of the IEEE_ , vol. 106, no. 5, pp. 808–828, 2018.
  * [11] H. E. Egilmez, A. Ortega, O. G. Guleryuz, J. Ehmann, and S. Yea, “An optimization framework for combining multiple graphs,” in _2016 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2016, pp. 4114–4118.
  * [12] W. Tang, Z. Lu, and I. S. Dhillon, “Clustering with multiple graphs,” in _2009 Ninth IEEE International Conference on Data Mining_. IEEE, 2009, pp. 1016–1021.
  * [13] M. Ménoret, N. Farrugia, B. Pasdeloup, and V. Gripon, “Evaluating graph signal processing for neuroimaging through classification and dimensionality reduction,” in _2017 IEEE Global Conference on Signal and Information Processing (GlobalSIP)_. IEEE, 2017, pp. 618–622.
  * [14] A. Narayanan and V. Shmatikov, “De-anonymizing social networks,” in _2009 30th IEEE symposium on security and privacy_. IEEE, 2009, pp. 173–187.
  * [15] P. Pedarsani and M. Grossglauser, “On the privacy of anonymized networks,” in _Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining_ , 2011, pp. 1235–1243.
  * [16] L. Rossi, M. Musolesi, and A. Torsello, “On the k-anonymization of time-varying and multi-layer social graphs,” in _Proceedings of the International AAAI Conference on Web and Social Media_ , vol. 9, no. 1, 2015.
  * [17] V. Lyzinski, D. E. Fishkind, and C. E. Priebe, “Seeded graph matching for correlated erdös-rényi graphs.” _J. Mach. Learn. Res._ , vol. 15, no. 1, pp. 3513–3540, 2014.
  * [18] X. Guo, A. B. Bal, T. Needham, and A. Srivastava, “Statistical shape analysis of brain arterial networks (ban),” _arXiv preprint arXiv:2007.04793_ , 2020\.
  * [19] T. Kajdanowicz, R. Michalski, K. Musial, and P. Kazienko, “Learning in unlabeled networks–an active learning and inference approach,” _AI Communications_ , vol. 29, no. 1, pp. 123–148, 2016.
  * [20] P. Balachandran, E. D. Kolaczyk, and W. D. Viles, “On the propagation of low-rate measurement error to subgraph counts in large networks,” _The Journal of Machine Learning Research_ , vol. 18, no. 1, pp. 2025–2057, 2017.
  * [21] J. Chang, E. D. Kolaczyk, and Q. Yao, “Estimation of subgraph densities in noisy networks,” _Journal of the American Statistical Association_ , pp. 1–14, 2020.
  * [22] W. Li, D. L. Sussman, and E. D. Kolaczyk, “Estimation of the epidemic branching factor in noisy contact networks,” _arXiv preprint arXiv:2002.05763_ , 2020.
  * [23] E. D. Kolaczyk, L. Lin, S. Rosenberg, J. Walters, and J. Xu, “Averages of unlabeled networks: Geometric characterization and asymptotic behavior,” _The Annals of Statistics_ , vol. 48, no. 1, pp. 514–538, 2020.
  * [24] X. Guo, A. Srivastava, and S. Sarkar, “A quotient space formulation for statistical analysis of graphical data,” _arXiv preprint arXiv:1909.12907_ , 2019.
  * [25] A. Calissano, A. Feragen, and S. Vantini, “Populations of unlabeled networks: Graph space geometry and geodesic principal components,” 2020.
  * [26] L. Yartseva and M. Grossglauser, “On the performance of percolation graph matching,” in _Proceedings of the first ACM conference on Online social networks_ , 2013, pp. 119–130.
  * [27] O. E. Dai, D. Cullina, N. Kiyavash, and M. Grossglauser, “Analysis of a canonical labeling algorithm for the alignment of correlated erdos-rényi graphs,” _Proceedings of the ACM on Measurement and Analysis of Computing Systems_ , vol. 3, no. 2, pp. 1–25, 2019.
  * [28] D. Cullina, N. Kiyavash, P. Mittal, and H. V. 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_ , vol. 3, no. 3, pp. 1–21, 2019.
  * [29] B. Barak, C.-N. Chou, Z. Lei, T. Schramm, and Y. Sheng, “(nearly) efficient algorithms for the graph matching problem on correlated random graphs,” _Advances in Neural Information Processing Systems_ , vol. 32, pp. 9190–9198, 2019.
  * [30] J. Ding, Z. Ma, Y. Wu, and J. Xu, “Efficient random graph matching via degree profiles,” _Probability Theory and Related Fields_ , pp. 1–87, 2020.
  * [31] G. Hall and L. Massoulié, “Partial recovery in the graph alignment problem,” _arXiv preprint arXiv:2007.00533_ , 2020.
  * [32] Y. Wu, J. Xu, and S. H. Yu, “Settling the sharp reconstruction thresholds of random graph matching,” _arXiv preprint arXiv:2102.00082_ , 2021.
  * [33] L. Ganassali, L. Massoulié, and M. Lelarge, “Impossibility of partial recovery in the graph alignment problem,” _arXiv preprint arXiv:2102.02685_ , 2021.
  * [34] Y. Wu, J. Xu, and S. H. Yu, “Testing correlation of unlabeled random graphs,” _arXiv preprint arXiv:2008.10097_ , 2020.
  * [35] D. Conte, P. Foggia, C. Sansone, and M. Vento, “Thirty years of graph matching in pattern recognition,” _International journal of pattern recognition and artificial intelligence_ , vol. 18, no. 03, pp. 265–298, 2004.
  * [36] V. Lyzinski, D. E. Fishkind, M. Fiori, J. T. Vogelstein, C. E. Priebe, and G. Sapiro, “Graph matching: Relax at your own risk,” _IEEE transactions on pattern analysis and machine intelligence_ , vol. 38, no. 1, pp. 60–73, 2015.
  * [37] J. Yan, X.-C. Yin, W. Lin, C. Deng, H. Zha, and X. Yang, “A short survey of recent advances in graph matching,” in _Proceedings of the 2016 ACM on International Conference on Multimedia Retrieval_ , 2016, pp. 167–174.
  * [38] R. Jonker and A. Volgenant, “A shortest augmenting path algorithm for dense and sparse linear assignment problems,” _Computing_ , vol. 38, no. 4, pp. 325–340, 1987.