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.

We investigate the problem of detecting and estimating a changepoint in the attachment function of a network evolving according to a preferential attachment model on $n$ vertices, using only a single final snapshot of the network. Bet et al. (2023) show that a simple test based on thresholding the number of vertices with minimum degrees can detect the changepoint when the change occurs at time $n-\Omega(\sqrt{n})$. They further make the striking conjecture that detection becomes impossible for any test if the change occurs at time $n-o(\sqrt{n}).$ Kaddouri et al. (2024) make a step forward by proving the detection is impossible if the change occurs at time $n-o(n^{1/3}).$ In this paper, we resolve the conjecture affirmatively, proving that detection is indeed impossible if the change occurs at time $n-o(\sqrt{n}).$ Furthermore, we establish that estimating the changepoint with an error smaller than $o(\sqrt{n})$ is also impossible, thereby confirming that the estimator proposed in Bhamidi et al. (2018) is order-optimal.