Concentration of Multilinear Functions of the Ising Model with Applications to Network Data
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 degreed polynomial of a n-spin Ising model exhibits exponential tails that scale as
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.
Summary:
 
  The paper considers concentration of bilinear functions of samples from an ferromagnetic Ising model under high temperature (satisyfing Dobrushin's condition which implies fast mixing). The authors show that for the case when there is no external field, that any bilinear function with bounded coefficients concentrate around a radius of O(n) around the mean where n is the number of nodes in the Ising Model. The paper also shows that for Ising models with external fields, bilinear functions of mean shifted variables again obey such concentration properties.
   The key technical contribution is adapting the theory of exhangeable pairs from [Cha05] which has been applied for linear functions of the Ising model and apply it to bilinear functions. Naive applications give concentration radius of n^{1.5} which the authors improve upon. The results are also optimal due to the lower bound for the worst case.
Strengths:
 a) The key strength is the proof technique - the authors show that the usual strategy of creating an exchangeable pair from a sample X from the Ising model and X' which is one step of glauber dynamics is not sufficient. So they restrict glauber dynamics to a desirable part of the configuration space and show that the same exchangeable trick can be done on this censored glauber dynamics. They also show that this glauber dynamics mixes fast using path coupling results and also by a coupling argument by chaining two glauber Markov Chains tightly. This tightly chained censored glauber dynamics really satisfies all conditions of the exchangeable pairs argument needed. The authors show this carefully by several Lemmas in the appendix. I quite enjoyed reading the paper.
b) I have read the proofs in the appendix. Barring some typos that can be fixed, the proof is correct to the best of my knowledge and the technique is the major contribution of the paper.
c) The authors apply this to test if samples from a specific distribution on social networks is from an Ising model in the high temperature regime. Both synthetic and real world experiments are provided.
Weaknesses:
  Quite minor weaknesses:
    a) Page 1 , appendix : Section 2, point 2 Should it not be f(X)- E[f(X)] ??
    b) Why is Lemma 1 stated ? It does not help much in understanding Thm 1 quoted. A few lines connecting them could help.
    c) Definition 1, I think It should be intersection and not union ?? Because proof of lemma 5 has a union of bad events which should be the negation of intersection of good events we want in Defn 1. 
    d) Typo in the last equation in Claim 3. 
    e) Lemma 9 statement. Should it not be (1-C/n)^t ??
    f) In proof of Lemma 10, authors want to say that due to fast mixing, total variation distance is bounded by some expression. I think its a bit unclear what the parameter eta is ?? It appears for the first time. It will be great if the authors can explain that step better .
    g) Regarding the authors experiments with Last.fm - Whats the practical use case of testing if samples came from an Ising model or not ? Actually the theoretical parts of this paper are quite strong. But I just wanted to hear author's thoughts.
    h) Even for linear functions of uniform distribution on the boolean hypercube, at a different radius there are some anti concentration theorems like Littlewood Offord. Recently they have been generalized to bilinear forms (by Van Vu , terry tao with other co authors). I am wondering if something could be said about anti concentration theorems for Bilinear forms on Ising Models ??