Concentration of Multilinear Functions of the Ising Model with Applications to Network Data

Understand

We prove near-tight concentration of measure for polynomial functions of the Ising model under high temperature.

• For any degree $d$, we show that a degree-$d$ polynomial of a $n$-spin Ising model exhibits exponential tails that scale as $\exp(-r^{2/d})$ at radius $r=\tilde{\Omega}_d(n^{d/2})$.
• Our concentration radius is optimal up to logarithmic factors for constant $d$, improving known results by polynomial factors in the number of spins.
• We demonstrate the efficacy of polynomial functions as statistics for testing the strength of interactions in social networks in both synthetic and real world data.