Efficient Graph Matching for Correlated Stochastic Block Models

Thank you for your review and comments!

We concur with the reviewer that lengthy papers present challenges with the conference format and its restrictions. However, we argue that this is a widespread general issue, not specific to our paper -- indeed, there are numerous NeurIPS papers with lengthy appendices. Within the constraints, we certainly aimed to provide a good summary of the results and the proof ideas and techniques within the main text.

We will certainly do a careful check over the whole paper for grammatical and spelling errors. We will also ask a native English-speaking colleague of ours to proofread our paper, specifically focusing on spelling and correct phrasing of sentences. (We (the authors) are non-native English speakers, and we appreciate your patience as we improve the writing of the paper.)

Thank you for your review and comments!

Comment #1 (runtime analysis):

In the literature on random graph matching, the quest for polynomial-time algorithms has been a major driving force behind the recent surge of papers on the topic. These culminated in the recent breakthrough works [33] and [35] on correlated Erdős--Rényi random graphs. Our work continues along this line of work, going beyond the correlated Erdős--Rényi model, and giving the first polynomial-time algorithm for graph matching on correlated SBMs. Unfortunately, the running time is a high order polynomial --- this is an issue that is present already in the prior work [35]. Thus, the implementation of the algorithm for simulations would only be possible on small graphs. As such, our contribution should be viewed as a conceptual, theoretical result.

At the same time, we do believe that fast and implementable algorithms do exist under some weakened condition, such as $s^2>\alpha'$ for some $\alpha' > \alpha$. One recent empirical evidence towards this is the work of Muratori and Semerjian [42], who empirically studied a significantly accelerated version of the subtree counting method, using a restricted family of subtrees with a limited depth and where each node has at most $2$ or $3$ descendants. It is conjectured in [42] that for some $\alpha'>\alpha$, the proposed faster algorithm can achieve exact graph matching on correlated Erdős--Rényi graphs much more efficiently than the original algorithm. In future work, we plan to empirically study their algorithm on correlated SBMs. Furthermore, we plan to attempt to rigorously show the exact graph matching result on correlated Erdős--Rényi graphs and later extend it to correlated SBMs. This direction is exciting to explore, but it is beyond the scope of the current paper.

Comment #2 (sparsity and other density regimes):

In Section 2 (from line $89$ to $100$ in our manuscript), we have argued that the logarithmic average degree is the most interesting parameter regime to study. The logarithmic average degree regime is also called the "bottleneck regime" of random graphs and it is the bare minimum for the graph to be connected. If we go sparser to constant average degree regime, then it is information-theoretically impossible to recover the communities exactly. If the vertices have polynomially growing degrees, then community recovery is easy as long as $\liminf_{n \to \infty} |p_{n}/q_{n} - 1| > 0$ (see [39]).

In Section 7 (from line $363$ to $372$ in our manuscript), we have also discussed that our result can be extended to a denser regime (where the average degree grows as a (small) polynomial of $n$) too. In the even denser regime, whenever $\liminf_{n \to \infty} |p_{n}/q_{n} - 1| > 0$ is satisfied, we can do community recovery (exactly and efficiently) by applying the work of Mossel, Neeman, and Sly [39], and then using the exact graph matching algorithm from Mao, Wu, Xu, and Yu [35] as a black box on the correlated Erdős--Rényi models under each community.

Comment #3 (on differentiating SBM from ER):

To apply our result in the logarithmic average degree regime where $p=a\frac{\log n}{n}$ and $q=b\frac{\log n}{n}$ (Theorem 1), we only need that $a\neq b$. If $a = b$, then the correlated SBM degenerates to the correlated ER model, where the result by Mao, Wu, Xu, and Yu [35] already applies. In other words, we do not need any nontrivial differentiation.

Comment #4 (on the necessity of the condition $s^2 > \alpha$):

Indeed, we conjecture that the condition $s^{2} > \alpha$ is necessary for a polynomial-time algorithm for graph matching to exist, just as [35] conjectures the same for the correlated Erdős--Rényi model. Thus, this graph matching in these models is conjectured to exhibit an information-computation gap; that is, a region of the parameters where the problem is information-theoretically feasible, but it is not possible with polynomial-time algorithms. There are many interesting problems that are conjectured to exhibit such an information-computation gap, but as of yet there is no problem where this has been proven. Instead, people often resort to proving results on restricted classes of algorithms (such as within the low-degree polynomials framework), which can be seen as evidence of computational hardness (though not as a full proof). Related to our work, in the easier task of correlation detection in the case of correlated Erdős--Rényi random graphs, the recent work [16] proved a corresponding low-degree hardness result.

Thank you for your review and comments!

Comment #1:

We would like to kindly make some clarifications regarding these comments.

Firstly, the correlated ER model is actually a special case of the correlated SBM model (not the other way around). Specifically, when the in-community edge density $p$ is equal to the cross-community edge density $q$, then the resulting SBM is in fact an ER graph.

Secondly, we do not assume that the non-edges of the first graph remain non-edges in the second graph. Since both graphs are subsampled from a mother graph, it is possible that some non-edges in the first graph are edges in the second graph. That said, it is true that the non-edges in the mother graph remain non-edges in both sub-sampled correlated graphs.

Comment #2:

In the literature on random graph matching, the quest for polynomial-time algorithms has been a major driving force behind the recent surge of papers on the topic. These culminated in the recent breakthrough works [33] and [35] on correlated Erdős--Rényi random graphs. Our work continues along this line of work, going beyond the correlated Erdős--Rényi model, and giving the first polynomial-time algorithm for graph matching on correlated SBMs. Unfortunately, the running time is a high order polynomial --- this is an issue that is present already in the prior work [35]. Thus, the implementation of the algorithm for simulations would only be possible on small graphs. As such, our contribution should be viewed as a conceptual, theoretical result.

At the same time, we do believe that fast and implementable algorithms do exist under some weakened condition, such as $s^2>\alpha'$ for some $\alpha' > \alpha$. One recent empirical evidence towards this is the work of Muratori and Semerjian [42], who empirically studied a significantly accelerated version of the subtree counting method, using a restricted family of subtrees with a limited depth and where each node has at most $2$ or $3$ descendants. It is conjectured in [42] that for some $\alpha'>\alpha$, the proposed faster algorithm can achieve exact graph matching on correlated Erdős--Rényi graphs much more efficiently than the original algorithm. In future work, we plan to empirically study their algorithm on correlated SBMs. Furthermore, we plan to attempt to rigorously show the exact graph matching result on correlated Erdős--Rényi graphs and later extend it to correlated SBMs. This direction is exciting to explore, but it is beyond the scope of the current paper.

Thank you for your review and comments!

We agree with the reviewer that there are several technical challenges to overcome, and a significant part of our contributions is indeed showing how to overcome these technical challenges.

However, we also believe that there are compelling conceptual challenges in our work, the main one being how to center the edge-indicator random variables for the centered subgraph counts. Let us elaborate on why this is so.

First of all, centering the edge-indicator random variables is crucial for the statistic to work, as discussed in Mao, Wu, Xu, Yu (2023) [ref. 35]. In the Erdős--R'enyi setting it is trivial how to center the edge-indicator random variables, since it is a homogeneous model, where all edge probabilities are the same. However, for heterogeneous models, it is no longer clear how to do this. Moreover, for general models, this may not even be possible. Consider, for instance, the graph matching problem for correlated inhomogeneous random graphs, studied in the recent works [51] and [17]. In particular, the work [17], titled "Efficiently matching random inhomogeneous graphs via degree profiles" studied efficient algorithms for this task. However, they note that

"in the inhomogeneous case it is also very difficult to obtain good estimates on these edge probabilities (for the obvious reason that the number of parameters is proportional to the number of observed variables)."

In other words, this challenge is made explicit in the work [17]. The authors get around the challenge by considering a much simpler statistic: degree profiles. However, this comes at a significant cost: their matching algorithm only works when $s = 1 - O(1/\log^{2}(n))$. In other words, it only works for vanishing correlation; it cannot handle constant correlation. A major point of our work is that the matching algorithm works for constant correlation.

More generally, it is not at all clear for which classes of graphs a "good enough" centering of the edge-indicator random variables can be computed. We view this as both a conceptual and a technical challenge. A main point of our work is to show that SBMs indeed fall within this class.

Thank you for your review!