Efficient Minimax Signal Detection on Graphs
Several problems such as network intrusion, community detection, and disease outbreak can be described by observations attributed to nodes or edges of a graph. In these applications presence of intrusion, community or disease outbreak is characterized by novel observations on some unknown connected subgraph. These problems can be formulated in terms of optimization of suitable objectives on connected subgraphs, a problem which is generally computationally difficult. We overcome the combinatorics of connectivity by embedding connected subgraphs into linear matrix inequalities (LMI). Computationally efficient tests are then realized by optimizing convex objective functions subject to these LMI constraints. We prove, by means of a novel Euclidean embedding argument, that our tests are minimax optimal for exponential family of distributions on 1-D and 2-D lattices. We show that internal conductance of the connected subgraph family plays a fundamental role in characterizing detectability.
** I have read the authors' response and the other reviews. The authors have provided satisfactory answers to my concerns. I agree with one of the other reviewers that the presentation is dense, but I think the authors have done a good job considering the space limitations. It would certainly be a better paper with no page limit, but the authors don't have that option. The experimental performance analysis could be improved, but considering the strength of the theoretical contribution, the paper remains for me in the top 15-25 percent of accepted NIPS papers. **Summary of the paper: The paper addresses the problem of signal detection for the case where the signals reside on connected subgraphs of a graph that models the relationships between a set of entities. The authors discuss how the problems can be formulated as optimization of objective functions defined on the subgraphs. A straightforward search over the subgraphs is computationally infeasible, so the authors present a highly novel approach that leads to computationally efficient tests. The paper includes proofs that the tests are nearly minimax optimal for the exponential family of distributions and graphs satisfying the polynomial growth property. The paper concludes with an analysis of synthetic and real datasets.Strengths:(1) The paper addresses a problem of growing importance and presents novel approaches for statistical tests. These are computationally feasible and the authors have managed to theoretically characterize the performance. The paper is, for the most part, very well-written, so that the concepts and the development of the approach is clear and easy to follow. The proofs are not straightforward and involve techniques that are of interest in their own right. Weaknesses:(1) The presented proofs (in the supplementary material) for two of the key results are limited to the 2D-lattice case, but are claimed in the paper for more general settings. The authors argue in each case that this is “For simplicity”, but I don’t think the extension to the claimed polynomial growth is completely obvious, and I’d prefer to see a “For completeness” proof follow the simple arguments. There is also a bold claim that the “analysis extends beyond Poisson & Gaussian models and applies to general graph structures and models” but there is little support for this claim. While the few sentences of argument are reasonable and it is likely that the analysis can be extended as the authors claim, the presented material does not genuinely support the claim.  (2) More detail could be provided for the simulation comparison. Apologies if I missed them, but what are the ground-truth subsets for the lattice examples? Are these constrained to be different from the completely arbitrary connected subsets considered by the SA algorithm? Are they randomized? Why not show a comparison for several choices of \gamma rather than just a value corresponding to thin sets? Other comments:The sketch of the proof of Theorem 3 is hard to follow. I think this largely arose for me because I didn’t understand what was meant by “M is connected”. M is a matrix. The only graph associated with it previously in the text is H, so I initially read this as “H is connected”, which means that the argument is circular. After a careful reading of the actual proof, I understand that what is meant by “M is connected” is that the graph with nodes Supp{Diag(M)} and edge set Supp(M) is connected.In the supplementary material, proof of Theorem 3, I think it is worth adding a sentence prior to (16) explaining that, due to the presence of the anchor node implied by M, the disconnected nature of H can only arise from A, the edge set of the underlying graph. This logical step wasn’t obvious to me at first.Theorem 3 proof: Line 3: |\overbar{C}| = k_2The connection between the proof of Theorem 4 and the claim at the end of the proof of Theorem 3 is not immediately obvious. I think it would be better if a direct argument were made in the Theorem 3 proof, or if the authors provided additional clarification regarding which part of the Theorem 4 proof was being applied.With regard to Theorem 4, it seems odd to me to state a theorem for polynomial growth graphs and then present a proof that (strictly) holds only for 2D-lattices. There isn’t a page limit on the supplementary material and the extension “Similar properties can be shown for polynomial growth graphs,…” is a little flimsy.A similar comment applies to the proof of Theorem 7; I think it is reasonable to focus on the Gaussian case, because the extension to the Poisson model seems relatively straightforward, but I can’t see a good reason to include only a sketch of the proof for the 2D-lattice when claiming a general result.