Do users from Carnegie Mellon University form social communities on Facebook? Do signal processing researchers tightly collaborate with each other? Do Chinese restaurants in Manhattan cluster together? These seemingly different problems share a common structure: an attribute that may be localized on a graph. In other words, nodes activated by an attribute form a subgraph that can be easily separated from other nodes. In this paper, we thus focus on the task of detecting localized attributes on a graph. We are particularly interested in categorical attributes such as attributes in online social networks, ratings in recommender systems, and viruses in cyber-physical systems because they are widely used in numerous data mining applications. To solve the task, we formulate a statistical hypothesis testing problem to decide whether a given attribute is localized or not. We propose two statistics: Graph wavelet statistic and graph scan statistic, both of which are provably effective in detecting localized attributes. We validate the robustness of the proposed statistics on both simulated data and two real-world applications: High air-pollution detection and keyword ranking in a coauthorship network collected from IEEE Xplore. Experimental results show that the proposed graph wavelet statistic and graph scan statistic are effective and efficient.
Our detection problem bears resemblance to many detection problems in the current graph-related literature, such as detecting a smooth graph signal or a localized graph signal under a specific noise model. For example, @cite_0 @cite_52 detects a cluster in a lattice graph that exhibits unusual behavior; @cite_13 constructs a generalized likelihood test to detect smooth graph signals; @cite_16 considers a general graph-structured normal means test; @cite_63 considers combining data gathering and decision-making to design the quickest detection in the markov random field; @cite_38 , constructs the uniform spanning tree wavelet statistic to approximate the epsilon scan statistic; and @cite_24 @cite_9 , considers the Lovasz extended scan statistic and spectral relaxation as relaxations of the combinatorial scan statistic.
@cite_38 @cite_9 @cite_52 @cite_0 @cite_24 @cite_63 @cite_16 @cite_13
2169357279 2964058506 2962796373 2069455711
We consider the change-point detection problem of deciding, based on noisy measurements, whether an unknown signal over a given graph is constant or is instead piecewise constant over two connected induced subgraphs of relatively low cut size. We analyze the corresponding generalized likelihood ratio (GLR) statistics and relate it to the problem of finding a sparsest cut in a graph. We develop a tractable relaxation of the GLR statistic based on the combinatorial Laplacian of the graph, which we call the spectral scan statistic, and analyze its properties. We show how its performance as a testing procedure depends directly on the spectrum of the graph, and use this result to explicitly derive its asymptotic properties on few significant graph topologies. Finally, we demonstrate both theoretically and by simulations that the spectral scan statistic can outperform naive testing procedures based on edge thresholding and @math testing. We consider the detection of clusters of activation over graphs under Gaussian noise. This problem appears in many real world scenarios, such as detecting contamination or seismic activity by sensor networks, viruses in human and computer networks, and groups with anomalous behavior in social and biological networks. We introduce the spanning tree wavelet basis over a graph, a localized basis that reflects the topology of the graph, and a detector based on this construction. We characterize orthonormality and sparsifying properties of the proposed basis, which can be useful for tasks other than detection, such as de-noising, compression and localization. For the detection problem, we provide a necessary condition for asymptotic distinguishability of the null and alternative hypotheses. Then we prove that our detector can correctly detect signals in a low signalto-noise regime using spanning tree wavelets, for any spanning tree. We then use electric network theory to show that a spanning tree drawn uniformly at random provides a stronger performance guarantee that in many cases matches the necessary condition. For edge transitive graphs, k-nearest neighbor graphs, and ǫ-graphs we obtain nearly optimal performance with the uniform spanning tree wavelet detector. We consider the change-point detection problem of deciding, based on noisy measurements, whether an unknown signal over a given graph is constant or is instead piecewise constant over two induced subgraphs of relatively low cut size. We analyze the corresponding generalized likelihood ratio (GLR) statistic and relate it to the problem of nding a sparsest cut in a graph. We develop a tractable relaxation of the GLR statistic based on the combinatorial Laplacian of the graph, which we call the spectral scan statistic, and analyze its properties. We show how its performance as a testing procedure depends directly on the spectrum of the graph, and use this result to explicitly derive its asymptotic properties on few graph topologies. Finally, we demonstrate both theoretically and by simulations that the spectral scan statistic can outperform naive testing procedures based on edge thresholding and 2 testing. We explore scalable and accurate dynamic pattern detection methods in graph-based data sets. We apply our proposed Dynamic Subset Scan method to the task of detecting, tracking, and source-tracing contaminant plumes spreading through a water distribution system equipped with noisy, binary sensors. While static patterns affect the same subset of data over a period of time, dynamic patterns may affect different subsets of the data at each time step. These dynamic patterns require a new approach to define and optimize penalized likelihood ratio statistics in the subset scan framework, as well as new computational techniques that scale to large, real-world networks. To address the first concern, we develop new subset scan methods that allow the detected subset of nodes to change over time, while incorporating temporal consistency constraints to reward patterns that do not dramatically change between adjacent time steps. Second, our Additive Graph Scan algorithm allows our novel scan statistic to process small graphs (500 nodes) in 4.1 seconds on average while maintaining an approximation ratio over 99 compared to an exact optimization method, and to scale to large graphs with over 12,000 nodes in 30 minutes on average. Evaluation results across multiple detection, tracking, and source-tracing tasks demonstrate substantial performance gains achieved by the Dynamic Subset Scan approach.