Optimal Single Sample Tests for Structured versus Unstructured Network
  Data
  We study the problem of testing, using only a single sample, between mean
field distributions (like Curie-Weiss, Erd\H{o}s-R\'enyi) and structured Gibbs
distributions (like Ising model on sparse graphs and Exponential Random
Graphs). Our goal is to test without knowing the parameter values of the
underlying models: only the \emph{structure} of dependencies is known. We
develop a new approach that applies to both the Ising and Exponential Random
Graph settings based on a general and natural statistical test. The test can
distinguish the hypotheses with high probability above a certain threshold in
the (inverse) temperature parameter, and is optimal in that below the threshold
no test can distinguish the hypotheses.
  The thresholds do not correspond to the presence of long-range order in the
models. By aggregating information at a global scale, our test works even at
very high temperatures.
  The proofs are based on distributional approximation and sharp concentration
of quadratic forms, when restricted to Hamming spheres. The restriction to
Hamming spheres is necessary, since otherwise any scalar statistic is useless
without explicit knowledge of the temperature parameter. At the same time, this
restriction radically changes the behavior of the functions under
consideration, resulting in a much smaller variance than in the independent
setting; this makes it hard to directly apply standard methods (i.e., Stein's
method) for concentration of weakly dependent variables. Instead, we carry out
an additional tensorization argument using a Markov chain that respects the
symmetry of the Hamming sphere.
