Harnessing Multiple Correlated Networks for Exact Community Recovery

Thank you for your review and comments!

We fully agree with the reviewer that the main open problem that our work leaves open is to develop efficient algorithms for the setting studied in our paper (whenever this is possible). The quest for efficient algorithms has been a major driving force behind the recent surge of papers on random graph matching (see Section 5), culminating in the breakthrough works [27] and [28] on correlated Erdos--Renyi random graphs. These works give promise that it is possible to develop efficient algorithms in our setting (perhaps with some conditions on the correlation parameter $s$). Our work lays the groundwork by determining the information-theoretic limits, which provide targets for efficient algorithms to achieve.

Q1 (sparse setting): Weak recovery in the constant average degree regime using correlated graphs is indeed a fascinating direction for future work (as already suggested in [18]). We suspect that the $k$-core analysis still gives something nontrivial in the large but constant average degree regime. However, proving this is far from immediate, due to a lack of concentration at this scale. Furthermore, determining the precise threshold for weak/partial recovery seems like a challenging problem which requires many more new ideas.

Q2 ($K$ diverging with $n$): An inspection of our proofs shows that our results hold also when $K$ diverges (slowly) with $n$. We have not made an attempt to see how fast $K$ can grow with $n$ to have the results still hold, in part because the conditions (3.1) and (3.2) converge exponentially in $K$, so they are already very close to their limiting values for large constant $K$.

That said, as an example, let us consider one particular aspect of the proof -- the correctness of the $k$-core estimator -- and see what we may allow $K$ to be here. Lemma F.4 says that the result holds with high probability; in other words, that the error probability is $o(1)$. A careful inspection of the proof of Lemma 4.8 in [18] actually shows that the error probability is bounded by $n^{-0.16}$ (moreover, if $k$ in the $k$-core is chosen to be a large constant, then this error probability can be made to be an arbitrarily small inverse polynomial in $n$). Since in a union bound over $K$ graphs we gain a factor of at most $K^{2}$, this shows that this lemma allows $K$ to grow polynomially in $n$. Of course, there are other aspects of the proof where the dependence on $K$ of the error probabilities have to be checked, and together these can give a full answer of how fast $K$ can grow with $n$.

Q3 (practical applications): We fully agree with the reviewer and we hope that such applications will arise in the future, motivated by our (theoretical) work.

Thank you for your review and comments!

We agree with the reviewer that it is natural to consider more general settings, such as more than two communities, as well as unbalanced communities. We suspect that our methods can be extended to these settings as well. However, in the present paper we decided to keep the setting as simple as possible, to focus on the effect of more than two graphs.

Thank you for your comments on the planted partition model and the Renyi divergence; we will add these terminologies to the paper. Thank you also for spotting that typo, and for suggesting to move forward some definitions; we will make these edits in the revision.

Q1 (on the $k$-core matching): The general intuition behind why the $k$-core matching performs well is as follows. The $k$-core of a graph captures its "central" part, in some sense. Thus if a vertex is part of the $k$-core of the intersection graph, then it has many common connections in the two graphs, so it is likely that these can help find the correct match for this vertex.

The choice of $k=13$ is not particularly important -- any large enough constant will work. The particular choice of $k=13$ comes from [18], where it arises in their Lemma 4.8 and Lemma 4.10. In particular, Lemma 4.10 is a probability tail bound, and the choice of $k \geq 13$ (and in particular $k=13$) guarantees that this vanishes sufficiently quickly. The proof of Lemma 4.10 contains a union bound that may be loose, so it may be possible that the value of $k$ can be further lowered, but this doesn't have any major importance.

Q2 (low-degree hardness): Yes, we conjecture that there is an information-computation gap for matching correlated SBMs, and we conjecture that this is the same as for matching correlated Erdos--Renyi random graphs, as in [28]. Namely, let $\alpha \approx 0.338$ denote Otter's tree counting constant [28]. We conjecture that if graph matching is information-theoretically feasible and $s^2 > \alpha$, then there is an efficient algorithm to do so. On the other hand, if $s^2 < \alpha$, then there does not exist such an efficient algorithm. Investigating this question is beyond the scope of the current paper.

Q3 ($K$ unbounded): As $K \to \infty$ (and assuming $s \in (0,1)$), the condition (3.1) converges to the condition that exact community recovery is possible in the parent graph $G$, while the condition (3.2) converges to the condition that $G_{1}$ is connected. The convergence in both cases is exponential in $K$, so for large constant $K$ the conditions will already be very close to the limiting conditions.

An inspection of our proofs shows that our results also hold for $K$ growing slowly with $n$; we haven't tried to optimize the bounds to allow $K$ to grow as fast as possible.

Q4 (3+ symmetric communities): We fully agree with the reviewer's conjecture (which generalizes the conjecture of reference [43] for $K=2$). We suspect that our methods can be extended to show this. However, in the present paper our aim was to focus on the effect of the number of graphs $K$, so we decided to keep other aspects of the setting as simple as possible. This is an interesting question for future work.

Q5 (two unbalanced communities): This is a natural and intriguing question. However, we believe that unbalanced communities do not help. Note that while unbalanced communities allow the communities to be matched, what we really need is to match individual vertices, and this is not readily done simply by virtue of the communities being unbalanced. Note also that after the partial matching and the initial majority votes, all nodes that have been matched have a correct estimate of their community. However, the condition (3.2) really comes from the (number of) unmatched vertices, and the related genie-aided argument, which gives the CH divergence. Of course, the arguments above are not a proof, just some heuristics, and we leave resolving this is as an interesting open question for the future.

Thank you for your review and comments!

Weak recovery in the constant average degree regime using correlated graphs is indeed a fascinating direction for future work (as already suggested in [18]). We suspect that the $k$-core analysis still gives something nontrivial in the large but constant average degree regime. However, proving this is far from immediate, due to a lack of concentration at this scale. Furthermore, determining the precise threshold for weak/partial recovery seems like a challenging problem which requires many more new ideas.

Regarding Figure 2, indeed, the reviewer is completely right: characterizing both the pink and the violet regions, and the boundary between them, are all important findings of the paper. Previously, [18] characterized the union of these two regions. We will correct the caption of Figure 2, please see the attachment to the "global" response/rebuttal for an updated version. Thank you for catching this.

Regarding the second set of questions about Figure 2, we hope that the "global" response/rebuttal -- which describes the threshold for exact graph matching from $K$ graphs (not just pairwise exact graph matching) -- helps clarify things. In particular, the previously yellow region now splits into an updated yellow region and a grey region. It is indeed the case that the union of the pink and the updated yellow regions is the region described in lines 12-15 of the abstract. We will add a sentence along these lines to the text in order to aid the reader.

Thank you for your review and comments!

Q1 (different subsampling probabilities): This is a very natural question, and our developed theory can fully handle this. We simply chose to keep this part of the model simple, since there are already several parameters involved in the model.

Let us illustrate on Theorem 1 how the results change with different subsampling probabilities $\{s_i\}$. First, condition (3.1) becomes $(1-\prod_{i=1}^{K}(1-s_i)) D_{+}(a,b)$. This change is immediate, since $(1-\prod_{i=1}^{K}(1-s_i))$ is the probability that an edge in the parent graph survives in at least one of the subsampled graphs, so this quantity arises in the correctly matched union graph (from which (3.1) is derived).

More interesting is how (3.2) changes with different subsampling probabilities. An immediate adaptation of our proof gives the sufficient condition

$\left[s_1\left(1-\prod_{i=2}^{K}(1-s_i)\right)\right]T_{c}(a,b)+\left[s_{1}\prod_{i=2}^{K}(1-s_i)\right]D_{+}(a,b)>1$.

However, this condition is not necessary. The tight sufficient condition turns out to be:

$\min_{j \in [K]} \left(\left[s_j\left(1-\prod_{i=1, i \neq j}^{K}(1-s_i) \right)\right]T_{c}(a,b)+\left[s_{j}\prod_{i=1, i \neq j}^{K}(1-s_i)\right]D_{+}(a,b)\right)>1$.

The basic idea is as follows. Suppose that $j^*$ minimizes the expression above. Then, under this condition, we can first exactly recover the communities in $G_{j^*}$ (using the same algorithm as in our proof). Subsequently, we can port this partition to $G_1$ using the ideas in Appendices G and I.

In the revision, we will add a remark to the paper along the lines above.

Q2 (exact graph matching threshold): This is an excellent question and indeed it is possible to do exact graph matching better than just pairwise using $K \geq 3$ graphs. The exact graph matching threshold given $K$ correlated SBMs is given by

$s\left(1-\left(1-s\right)^{K-1}\right)T_{c}(a,b)=1$.

We expand upon this in detail in the "global" response/rebuttal, please see there for more.

Q3 ("Joe Bloggs"): This is an astute observation and there are indeed various ways to incorporate this into a model, depending on the situation. One is to consider "seeded" graph matching, where a subset of vertices in the graphs are already matched, and the task is to match the remaining vertices. This setting is sometimes closer to practical applications, and is widely studied (e.g., [33], [45]). Another possibility is to consider "attributed" graph matching, where each node has a corresponding vector of attributes, and these are correlated across the graphs. See, e.g., Zhang, Wang, Wang, and Wang (IEEE Trans. on Information Theory, 2024) and Wang, Wang, and Wang (COLT 2024). Of course, these two modeling frameworks can be combined, and others may be relevant as well, depending on the application. All of these are worth more detailed study in our setting; however, this is beyond the scope of the current paper. We will add these to the possible future directions mentioned in the paper.

Q4 (when $a<b$): Yes, everything works also when $a<b$, simply by replacing "majority" with "minority" everywhere. This is correctly stated in the Algorithms stated in Appendix C. In lines 173--192 of the main text, we gave a high level overview, which is perhaps more intuitive in the assortative setting when $a>b$. We forgot to mention here that this description is for $a>b$; we will correct this in the revision. Thank you for catching this omission.

Q5 (subsampling parameter in real-world networks): We suspect that the answer may vary widely across applications. As an example, in a recent work by Li, Arroyo, Pantazis, Lyzinski (IEEE TNSE, 2023), the authors develop both theory and also apply it to human connectomes. While their paper does not indicate what the correlation parameter may be in this application, their theory and simulations are for constant correlation, and they vary the correlation parameter between 0 and 1. Likewise, our theory holds for any constant correlation $s\in [0,1]$; we hope that this can thus be useful in applications, regardless of what the actual correlation parameter is.

Q6 (the value of $k$ in the $k$-core): The choice of $k=13$ is not particularly important -- any large enough constant will work. The particular choice of $k=13$ comes from [18], where it arises in their Lemma 4.8 and Lemma 4.10. In particular, Lemma 4.10 is a probability tail bound, and the choice of $k\geq 13$ (and in particular $k=13$) guarantees that this vanishes sufficiently quickly. The proof of Lemma 4.10 contains a union bound that may be loose, so it may be possible that the value of $k$ can be further lowered, but this doesn't have any major importance.

Q7 (subsampling from an arbitrary base graph or a GRDPG): This is an excellent direction for future research. We suspect that the $k$-core analysis should also work for understanding (the information-theoretic limits of) graph matching of correlated GRDPGs, and the results of [39] support this heuristic as well. However, this is by no means obvious, and requires its own careful analysis.

The setting of an arbitrary base graph is much more challenging. This essentially corresponds to a "smoothed analysis" of graph matching, which has not been done before. This would be very interesting to consider, but it is significantly beyond the scope of this paper.

Q8 (alternative sampling using EdgeFlip): This setting is also interesting, and somewhat resembles the alternative setting we describe at the end of the paper (lines 365--372). We suspect that our methods are able to handle such a setting as well. In particular, for a constant number of graphs $K$, we conjecture that the results would be quantitatively different but qualitatively similar to the ones in the current paper. However, if $K$ is large (diverging with $n$), then we expect new qualitative phenomena to appear. This is an exciting avenue for future research, which we plan to pursue.