Summary
Theoretical work showing conditions for exact community recovery in $K$ correlated $2$-community SBMs where node labels are not maintained between networks. The work extends previous work for $K=2$ which introduces new challenges and proof mechanisms to allow for $K \ge 3$ networks. Theorems 1 and 2 provide necessary and sufficient conditions for exact community recovery relating to the difficulty of the pairwise matching problem $T_c(a, b)$ and the individual exact community recovery problem $D_+(a,b)$.
Strengths
This research fully answers the open question of [18] introducing novel ideas top extend existing techniques to work in the much more complicated scenario with $K \ge 3$ networks. I feel the paper was well-structured to introduce and explain the problem at hand to someone outside of the research area. Section 2 did an excellent job introducing the problem highlighting the interplay between the community recovery and graph matching. Section 3 giving the main results along with a helpful high level description of the algorithm used within the proof and Figure 2 demonstrates these results pictorially highlighting the regions where their research come into play. Section 4 gave more details of the proof, while still a bit technically in places was still useful for myself who wanted to get the vibe of the proof without delving into the details in the Appendix.
The paper is very clear in its goal, what is has achieved and possible future directions in this area.
Weaknesses
While reading this paper, I was unsure whether this paper fitted the remit of NeurIPS and would be better suited in another journal rather than conference paper. I felt more comfortable about this upon noticing that [18], which supplied the problem for this work, was itself inspired by work of community recovery in correlated SBMs [37] published in NeurIPS. I recognise this is a personal bias of what I consider a NeurIPS paper.
There is some discussion of how this work relates to real-world networks, but it is unclear how much further research needs to be done before these ideas can be used for practical analysis of real graphs. A number of my questions below relate to applying these ideas to more realistic networks.
Questions
How does changing the correlated SBM to allow for different subsampling probabilities $s_i$ for each network affect the theory?
Is it possible to do just exact graph matching better than $s^2 T_c(a,b) > 1$ for $K \ge 3$ graphs? Perhaps this is addresses in some of the referenced papers, but my reading of Lines 128-129 is that exact graph matching is done pairwise for any graphs $G_k$ and $G_l$ which means that all graphs can be paired. Is there any improvement by doing things other than pairwise? I believe the answer reading on later is no, at least asymptotically, but it is uncertain later whether the benefit of extra graphs is solely for graph matching and community detection together, rather than individually. This may be addressed by resolving whether the "if if" typo in Line 128 should be just a single "if" or, in fact, "if and only if".
While it is useful to consider the extreme case, often there is some evidence of persistent node labelling across networks. For example, Joe Bloggs on Facebook is more likely to correspond to the email joe_bloggs_01@mail.com compared to a completely random node. How could this scenario be incorporated into graph matching and community detection?
Do Steps 3-5 in the algorithm still work if $a < b$? Obviously, there is a symmetry in these two parameters, but as the algorithm is written, in this scenario neighbours are more likely to be the other community rather than the same. Please can you explain the changes necessary to make this approach work when $a < b$?
What subsampling parameter $s$ should we expect in real-world networks? Figure 2 shows two possible values but I have no idea what I would expect as normal. Given networks $G_1, \ldots, G_K$ one could find a maximum likelihood estimator for $s$, perhaps by computing the true $G$ using the graph matching algorithms described here and finding the subsample rate.
Any intuition why the value $k = 13$ in the $k$-core algorithm in Line 244?
How do these ideas relate to subsampling from any arbitrary base graph $G$ rather than just a 2-community SBM? For example, if $G$ was sampled from a generalised random dot product graph (A statistical interpretation of spectral embedding: the generalised random dot product graph, Rubin-Delanchy et al), then the subsampled graphs $G_i$ would also be a GRDPG. The problem of community recovery may not always make sense in that setting, but graph matching is still very important.
An alternative way of subsampling graphs is EdgeFlip used for edge-differential privacy in networks (Sharing social network data: differentially private estimation of exponential-family random graph models, Karwa et al). Edges and non-edges are flipped in $G$ with some probability $p$. How do these techniques work using this method of generating anomalised networks? The results here could show the dangers of producing multiple anomalous versions of the same network, a potentially important result for data privacy.
Limitations
The authors highlight the positive and negative impact of their results, particular for de-anomalising multiple networks.