Efficient random graph matching via degree profiles

Random graph matching refers to recovering the underlying vertex correspondence between two random graphs with correlated edges; a prominent example is when the two random graphs are given by Erdős-Rényi graphs \(G(n,\frac{d}{n})\). This can be viewed as an average-case and noisy version of the graph isomorphism problem. Under this model, the maximum likelihood estimator is equivalent to solving the intractable quadratic assignment problem. This work develops an \({\widetilde{O}}(n d^2+n^2)\)-time algorithm which perfectly recovers the true vertex correspondence with high probability, provided that the average degree is at least \(d = \varOmega (\log ^2 n)\) and the two graphs differ by at most \(\delta = O( \log ^{-2}(n) )\) fraction of edges. For dense graphs and sparse graphs, this can be improved to \(\delta = O( \log ^{-2/3}(n) )\) and \(\delta = O( \log ^{-2}(d) )\) respectively, both in polynomial time. The methodology is based on appropriately chosen distance statistics of the degree profiles (empirical distribution of the degrees of neighbors). Before this work, the best known result achieves \(\delta =O(1)\) and \(n^{o(1)} \le d \le n^c\) for some constant c with an \(n^{O(\log n)}\)-time algorithm and \(\delta ={{\widetilde{O}}}((d/n)^4)\) and \(d = {\widetilde{\varOmega }}(n^{4/5})\) with a polynomial-time algorithm.

1. To ensure the Bernoulli parameter in (2) is well-defined, we need to assume \(q(1-s) \le 1-q\), or equivalently \(s \ge 2-1/q\). Similarly, to ensure the edge probability in the parent graph \(p=q/s \le 1\), we need to assume \( s \ge q\).

2. Throughout the paper, we use standard big O notation, e.g., for any sequences \(\{a_n\}\) and \(\{b_n\}\), \(a_n=\varTheta (b_n)\) (or \(a_n \asymp b_n\)) if \(1/c\le a_n/ b_n \le c\) holds for all n for some absolute constant \(c>0\); \(a_n =\varOmega (b_n)\) and \(b_n = O(a_n)\) (or \(a_n > rsim b_n\) and \(b_n \lesssim a_n\)) if \(a_n/b_n \ge c\). We use big \({\widetilde{O}}\) notation to hide logarithmic factors.

3. Achievability and converse bounds for more general correlated Erdős-Rényi random graph models are also available in [13, 14].

4. To be precise, all but two elements (namely, \(A_{ik}\) and \(B_{ki}\)) are independent. This can be easily dealt with by excluding those two from the empirical distribution, which, by the triangle inequality, changes the distance statistic by at most \(\frac{1}{n}\).

5. Alternatively, outdegrees can be computed via the number of common neighbors by squaring the adjacency matrix using fast matrix multiplication.

Authors and Affiliations

1. Department of Statistics, The Wharton School, University of Pennsylvania, Philadelphia, USA

   Jian Ding & Zongming Ma

2. Department of Statistics and Data Science, Yale University, New haven, USA

   Yihong Wu

3. The Fuqua School of Business, Duke University, Durham, USA

   Jiaming Xu

Corresponding author

Correspondence to Yihong Wu.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

J. Ding is supported in part by the NSF Grant DMS-1757479 and an Alfred Sloan fellowship. Z. Ma is supported in part by an NSF CAREER award DMS-1352060 and an Alfred Sloan fellowship. Y. Wu is supported in part by the NSF Grant CCF-1527105, an NSF CAREER award CCF-1651588, and an Alfred Sloan fellowship. J. Xu is supported by the NSF Grants CCF-1850743, CCF-1856424, and IIS-1932630.

J. Ding and Y. Wu would like to thank the Centre de Recherches Mathématiques at the Université de Montréal, where some of the work was carried out during the Workshop on Combinatorial Statistics. Y. Wu is also grateful to David Pollard for helpful discussions on small ball probability. J. Xu would like to thank Nadav Dym and Shahar Kovalsky for pointing out the connections between fractional isomorphism and iterated degree sequences. The authors are grateful to the anonymous referees for helpful comments and corrections.

Appendix A Auxiliary results

Recall the following tail bound for binomial random variable \(X\sim \mathrm{Binom}(n,p)\) [37, Theorems 4.4, 4.5]

and

Theorem 5

( [43]) Let \(X \sim \mathrm {Bin}(n,p)\). It holds that

Appendix B Analysis for seeded graph matching

In this section we analyze Algorithm 3 for seeded graph matching. Note that when Algorithm 3 is used as a subroutine in Algorithm 2, the seed set S is obtained from Algorithm 1 based on matching degree profiles, which can potentially depend on the edges between the non-seeded vertices. To deal with this dependency, the following lemma gives a sufficient condition for the seeded graph matching subroutine (Algorithm 3) to succeed, even if the seed set is chosen adversarially:

Lemma 18

(Seeded graph matching) Assume \(n\ge 4\), \(s \ge 30 q\), and

If the number of seeds satisfies \(m \ge \frac{96 \log n}{q s}\), then with probability \(1 - 5n^{-1}\), the following holds: for any \(\pi _0:S \rightarrow T\) that coincides with true permutation \(\pi ^*\) on the seed set S, (i.e. \(\pi _0 = \pi ^*|_S\)) with \(|S|=m\), Algorithm 3 with \(\pi _0\) as the seed set and threshold \(\kappa =\frac{1}{2} mqs\) outputs \({{\widehat{\pi }}} = \pi \).

We start by analyzing the first stage of Algorithm 3, which upgrades a partial (but correct) permutation \(\pi _0: S \rightarrow T\) to a full permutation \(\pi _1:[n] \rightarrow [n]\) with at most \(O(\log n/q)\) errors, even if the seed set S is adversarially chosen.

Lemma 19

Assume \(n\ge 2\), \(m q s \ge 96 \log n\), and \(s \ge 12q\). Recall the threshold \( \kappa =\frac{1}{2} mqs \) in Algorithm 3. Then with probability at least \(1- 2n^{ -m }\), the following holds in Algorithm 3: for any partial permutation \(\pi _0: S \rightarrow T\) such that \(\pi _0 = \pi ^*|_S\) and \(|S|=m\), \(\pi _1\) is guaranteed to have at most \(\frac{192\log n}{qs}\) errors with respect to \(\pi ^*\), i.e., \(|\{i\in [n]: \pi _1(i) \ne \pi ^*(i) \}| \le \frac{192\log n}{qs}\).

Proof (Proof of Lemma 19)

Without loss of generality, we assume \(\pi ^*\) is the identity permutation.

Fix a seed set S of cardinality m. Since \(\pi _0 = \pi ^*|_S\), it follows that

Recall that according to the definition of the weights in (35), we have

First, we show that

Indeed, for \(i \in S^c\) we have \(n_{i i} {{\mathop {\sim }\limits ^{\text {i.i.d.}}}}\mathrm{Binom}(m, qs)\). It follows from the Chernoff bound (165) that

Therefore,

Using the following fact (which follows from a simple union bound)

we get that

where the last inequality holds due to the assumption that \(mqs \ge 16 \log n\). Setting \(t=\frac{ 32 \log n}{qs}\), we arrive at the desired (170).

Next, fix any permutation \(\pi \) such that \(\pi |_S = \pi _0\) and it has \(\ell \) non-fixed points. Since by assumption \(\pi _0=\pi ^* |_S\) and \(\pi ^*\) is the identity permutation, it follows that \(\pi (i)=i\) for all \(i \in S\). Let \(F = \{i \in S^c: \pi (i) = i\}\) denote the set of fixed points in \(S^c\). Then \(|F|=n-m-\ell \) and \(|S^c\backslash F|=\ell \). Thus

Note that for each \(i \in S^c \backslash F\), \(n_{i\pi (i)} \sim \mathrm{Binom}(m, q^2)\). Since by assumption \(s \ge 12q\), it follows that \(\kappa = mqs/2 \ge 6 m q^2\). Hence, the Chernoff bound (166) yields that for each \(i \in S^c \backslash F\),

Note that \(\{n_{i\pi (i)}: i \in S^c \backslash F\}\) are not mutually independent. For instance, \(n_{i \pi (i)}\) and \(n_{\pi (i), \pi (\pi (i))}\) are dependent. To deal with this dependency issue, we construct a subset \({{\mathcal {I}}}\subset S^c \backslash F\) with \(|{{\mathcal {I}}}| \ge \ell /3\) such that \(\{n_{i\pi (i)}: i \in {{\mathcal {I}}}\}\) are mutually independent. In particular, consider the canonical cycle decomposition of permutation \(\pi |_{S^c \backslash F}\). Let \({{\mathcal {C}}}_1, \ldots , {{\mathcal {C}}}_{a}\) denote the cycles. Since \(\pi \) has no fixed point in \(S^c \backslash F\), each cycle \({{\mathcal {C}}}_i\) has length \(\ell _i \ge 2\). Let \(\varGamma \) denote the graph formed by the union of these cycles. Each cycle \(C_i\) has an independent set \({{\mathcal {I}}}_i\) of size \(\lfloor \ell _i /2 \rfloor \ge \ell _i/3\). Let \({{\mathcal {I}}}= \cup _{i=1}^a {{\mathcal {I}}}_i\). Then \({{\mathcal {I}}}\) is an independent set in \(\varGamma \) and \(|{{\mathcal {I}}}| \ge \sum _{i=1}^a \ell _i/3=\ell /3\). Since \({{\mathcal {I}}}\) is an independent set, it follows that \(\{i, \pi (i)\} \cap \{j, \pi (j)\} =\emptyset \) for all \(i \ne j \in {{\mathcal {I}}}\). Therefore, \(\{n_{i\pi (i)}: i \in {{\mathcal {I}}}\}\) are mutually independent. Therefore,

Note that

Using (171) again, we have

where the last inequality holds provided \(\ell qs\ge 192 \log n\). Let \(\varPi _\ell \) denote the set of permutations \(\pi \) which has \(\ell \) non-fixed points and satisfies \(\pi |_S = \pi _0\). Then \(|\varPi _\ell | \le \left( {\begin{array}{c}n-m\\ \ell \end{array}}\right) \ell ! \le n^\ell \). By the union bound, we have that for any \(\ell \ge \frac{ 192 \log n}{qs}\),

where the last inequality holds due to the assumption that \(mqs \ge 96 \log n\) and \(n \ge 2\). Applying the union bound again over \(\ell \), we get that

where the last inequality holds due to \(m \log n \ge \log 2\).

Combining the last displayed equation with (170) we get that with probability at least \(1- 2 n^{-2m}\), \(\pi _1\) has at most \(192\log n/(qs)\) errors with respect to \(\pi ^*\).

Finally, applying a simple union bound over all the \(\left( {\begin{array}{c}n\\ m\end{array}}\right) \le n^m\) possible choices of seed set S with \(|S|=m\), we complete the proof. \(\square \)

The second stage of Algorithm 3 upgrades an almost exact full permutation \(\pi _1:[n] \rightarrow [n]\) to an exact full permutation \({\widehat{\pi }}: [n] \rightarrow [n]\). The following lemma provides a worst-case guarantee even if \(\pi _1\) is adversarially chosen.

Lemma 20

Let \(0 \le \ell \le n\). Assume that \((\ell -1) qs \ge 12 nq^2 +2 \) and \( (\ell -1) q s \ge 16 \max \{ 1, n-\ell \} \log n\). Then with probability at least \(1-3n^{-1}\), the following holds for Algorithm 3: for any \(\pi _1\) with at most \(n-\ell \) errors with respect to the true permutation \(\pi ^*\), we have \({\widehat{\pi }}=\pi ^*\).

Proof

Without loss of generality, we assume \(\pi ^*\) is the identity permutation.

We first fix a permutation \(\pi _1\) which has at least \(\ell \) fixed points. Let \(F \subset [n]\) denote the set of fixed points of \(\pi _1\). Then \(|F| \ge \ell \). Recall that

Then for \(i=k\),

Similarly, for \(i \ne k\), note that \(A_{ij} B_{k \pi _1(j)} =0\) if \(j=i\) or \(j=\pi _1^{-1}(k)\). Thus, \(w_{ik} = \sum _{j \in [n]\backslash \{i,\pi _1^{-1}(k)\} }A_{ij} B_{k \pi _1(j)}. \) Moreover, \(A_{ij} B_{k \pi _1(j)} {{\mathop {\sim }\limits ^{\text {i.i.d.}}}}\mathrm{Bern}(q^2)\) for all \(j \in [n]\backslash \{i,\pi _1^{-1}(k) , k \}\). Therefore,

It follows from the Chernoff bound (165) that

Thus, by the union bound,

where the last inequality holds due to the assumption that \( (\ell -1) q s \ge 16 \log n\). Moreover, since by assumption \( (\ell -1) qs /2 -1 \ge 6 n q^2\), it follows that the Chernoff bound (166) that for any \(i \ne k\),

Thus, by the union bound again,

In conclusion, for a fixed permutation \(\pi _1\) with at least \(\ell \) fixed points, with probability at least \(1-3\exp \left( - \frac{1}{8} (\ell -1) q s \right) \),

and hence \({\widehat{\pi }} = \pi ^*\).

Finally, applying a simple union bound over all the \(\left( {\begin{array}{c}n\\ n-\ell \end{array}}\right) (n-\ell )! \le n^{n-\ell }\) possible choices of permutation \(\pi _1\) with at least \(\ell \) fixed points, we get that even if \(\pi _1\) is adversarially chosen, \({\widehat{\pi }} = \pi ^*\) with probability at least

where the first inequality holds due to \((\ell -1) qs \ge 16(n-\ell ) \log n\) and the last inequality holds due to \((\ell -1) qs \ge 16 \log n\). \(\square \)

We now prove Lemma 18:

Proof (Proof of Lemma 18)

In view of Lemma 19, we get that with probability at least \(1- 2n^{ -m }\), \(\pi _1\) is guaranteed to have at most \(192 \log n/(qs)\) errors with respect to \(\pi ^*\), even if \(\pi _0\), or equivalently the seed set S, is adversarially chosen.

We next apply Lemma 20 with \(\ell = n- 192 \log n/(qs)\). In view of the assumption \( n (qs)^2 \ge 2^{11} \times 3 \log ^2 n\) and \(n \ge 4\), we have \((\ell -1) \ge n/2\). Thus \((\ell -1) qs \ge n qs /2 \ge 16 \log n\), and \((\ell -1) qs \ge nq s /2 \ge 12 nq^2+2\) in view of \(s \ge 30 q\) and \(nqs \ge 20\). Moreover, \((\ell -1) qs \ge n qs /2 \ge 2^{10} \times 3 \log ^2 n / (qs) = 16(n-\ell ) \log n\). Therefore, all assumptions of Lemma 20 are satisfied. It follows from Lemma 20 that with probability at least \(1-3n^{-1}\), \({\widehat{\pi }}=\pi ^*\), even if \(\pi _1\) is adversarially chosen.

In conclusion, we get that with probability at least \(1-5n^{-1}\), Algorithm 3 with \(\pi _0\) as the seed set outputs \({{\widehat{\pi }}} = \pi \). \(\square \)

Reprints and permissions