Detecting Correlation Efficiently in Very Supercritical Stochastic Block Models: Breaking the Otter’s Threshold Barrier

Consider a pair of sparse correlated stochastic block models \(\mathcal S(n, \tfrac{\lambda}{n}; \epsilon; \mathcal s)\) subsampled from a common parent stochastic block model with two symmetric communities, average degree \(\lambda = O(1)\), divergence parameter \(\epsilon \in (0,1)\) and subsampling probability \(\mathcal s\). For all \(\epsilon \in (0,1)\), we construct a statistic based on the combination of two low-degree polynomials and show that there exists a sufficiently small constant \(\delta = \delta(\epsilon) \gt 0\) and a sufficiently large constant \(\Delta = \Delta(\epsilon, \delta)\) such that when \(\lambda \gt \Delta\) and \(\mathcal s \gt \sqrt{\alpha} - \delta\) where \(\alpha \approx 0.338\) is Otter’s constant, this statistic can distinguish this model and a pair of independent stochastic block models \(\mathcal S(n, \tfrac{\lambda s}{n}, \epsilon)\) with probability \(1 - o(1)\). We also provide an efficient algorithm that approximates this statistic in polynomial time. Our result is the first detection or matching type algorithm that breaks the Otter’s threshold in sparse correlated random graphs. The crux of our statistic’s construction lies in a carefully curated family of multigraphs called decorated trees, which enables effective aggregation of the community signal and graph correlation from the counts of the same decorated tree while suppressing the undesirable correlations among counts of different decorated trees. We believe such construction may be of independent interest.