The celebrated theorem of Chung, Graham, and Wilson on quasirandom graphs implies that if the 4-cycle and edge counts in a graph G are both close to their typical number in G (n, 1/2), then this also holds for the counts of subgraphs isomorphic to H for any H of constant size. We aim to prove a similar statement where the notion of close is whether the given (signed) subgraph count can be used as a test between G (n, 1/2) and a stochastic block model SBM. Quantitatively, this is related to approximately maximizing H | (H) |^1{|V (H) |}, where (H) is the Fourier coefficient of SBM, indexed by subgraph H. This formulation turns out to be equivalent to approximately maximizing the partition function of a spin model over alphabet equal to the community labels in SBM. We resolve the approximate maximization when SBM satisfies one of four conditions: 1) the probability of an edge between any two vertices in different communities is exactly 1/2; 2) the probability of an edge between two vertices from any two communities is at least 1/2 (this case is also covered in a recent work of Yu, Zadik, and Zhang) ; 3) the probability of belonging to any given community is at least c for some universal constant c>0; 4) SBM has two communities. In each of these cases, we show that there is an approximate maximizer of | (H) |^1{|V (H) |} in the set A = \stars, 4-cycle\. This implies that if there exists a constant-degree polynomial test distinguishing G (n, 1/2) and SBM, then the two distributions can also be distinguished via the signed count of some graph in A. We conjecture that the same holds true for distinguishing G (n, 1/2) and any graphon if we also add triangles to A.
Bangachev et al. (Wed,) studied this question.