Near-optimal Anomaly Detection in Graphs using Lovász Extended Scan Statistic
The detection of anomalous activity in graphs is a statistical problem that arises in many applications, such as network surveillance, disease outbreak detection, and activity monitoring in social networks. Beyond its wide applicability, graph structured anomaly detection serves as a case study in the difficulty of balancing computational complexity with statistical power. In this work, we develop from first principles the generalized likelihood ratio test for determining if there is a well connected region of activation over the vertices in the graph in Gaussian noise. Because this test is computationally infeasible, we provide a relaxation, called the Lovász extended scan statistic (LESS) that uses submodularity to approximate the intractable generalized likelihood ratio. We demonstrate a connection between LESS and maximum a-posteriori inference in Markov random fields, which provides us with a poly-time algorithm for LESS. Using electrical network theory, we are able to control type 1 error for LESS and prove conditions under which LESS is risk consistent. Finally, we consider specific graph models, the torus, knearest neighbor graphs, and ǫ-random graphs. We show that on these graphs our results provide near-optimal performance by matching our results to known lower bounds.
This paper presents a new algorithm to detect 
      activation in a weighted graph, as well as some theoretical analysis 
      regarding minimal detection levels of this algorithm as well as 
      others. The problem considered - detecting activation in graphs is 
      (relatively) new and interesting. Furthermore, the new solution 
      proposed by the authors is to the best of my knowledge highly 
      original, and may be of applicability in other problems. That 
      said, the paper is not very clearly written, and is not easy to read and 
      follow. Detailed comments are as follows: p.1 L36 - Detection 
      is broader than as written in first sentence of intro. Consider for 
      example change detection, outlier detection etc. In many such problems the 
      null is not merely noise. p.2 L57-72: Not clear why authors 
      spend these lines presenting these applications. On first read I 
      thought they actually had data from these applications and would show 
      the results of their algorithms. The wording on line 55 is quite 
      misleading "we will examine two real-world examples". In fact, can the 
      authors point to links where such data is available in the public 
      domain ? p.2 L85: is C required to be a single connected component 
      ? Does not seem so from definition, and constraint that out(C) \leq 
      rho means that for sufficiently large rho C can be a collection of a 
      quite large number of singletons. p2 L87 number of edges --> 
      total weight ? p.2 L100 typically one cannot control both types of 
      error, but rather tries to maximize probability of detection while 
      fixing the false alarm rate. p2 L106 "instead of the test being 
      randomized" not clear. p3 top - it is not clear that as p\to\infty 
      there is a 0/1 limiting law of perfect distinguishability or 
      indistinguishability (type I plus type II errors tending to 0 or to 1). 
      p3 L135 "used to localize binary signals over graphs" not clear. 
      p4 L165 "that do not take the graph into account" is not clear. 
      p4 L172-177 - whole paragraph is not very clear. Also, w.r.t. 
      proposition 2 and the problem formulation, I would like to point out 
      that there may be a difference between detection of presence of 
      activation in the graph, and estimation of which nodes where activated. 
      See for example work by Y. Ingster (1997) and by Donoho and Jin, 
      Annals of Statistics, 2004. I presume there may be a similar phenomena 
      here, unless there is a constraint that C is connected ? p.4 
      L177 tends to provide worse performance - is this an empirical observation 
      or is there a mathematically precise statement. p 5 can the 
      authors comment on the complexity of the LESS algorithm as a function of p 
      rho etc. p.7 how does r_C depend on rho ?