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.
@cite_38: 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.
@cite_9: 
@cite_52: Nonparametric detection of existence of an anomalous disk over a lattice network is investigated. If an anomalous disk exists, then all nodes belonging to the disk observe samples generated by a distribution q, whereas all other nodes observe samples generated by a distribution p that is distinct from q. If there does not exist an anomalous disk, then all nodes receive samples generated by p. The distributions p and q are arbitrary and unknown. The goal is to design statistically consistent test as the network size becomes asymptotically large. A kernel-based test is proposed based on maximum mean discrepancy (MMD) which measures the distance between mean embeddings of distributions into a reproducing kernel Hilbert space (RKHS). A sufficient condition on the minimum size of candidate anomalous disks is characterized in order to guarantee the consistency of the proposed test. A necessary condition that any universally consistent test must satisfy is further derived. Comparison of sufficient and necessary conditions yields that the proposed test is order-level optimal.
@cite_0: We consider the problem of detecting whether or not in a given sensor network, there is a cluster of sensors which exhibit an "unusual behavior." Formally, suppose we are given a set of nodes and attach a random variable to each node. We observe a realization of this process and want to decide between the following two hypotheses: under the null, the variables are i.i.d. standard normal; under the alternative, there is a cluster of variables that are i.i.d. normal with positive mean and unit variance, while the rest are i.i.d. standard normal. We also address surveillance settings where each sensor in the network collects information over time. The resulting model is similar, now with a time series attached to each node. We again observe the process over time and want to decide between the null, where all the variables are i.i.d. standard normal; and the alternative, where there is an emerging cluster of i.i.d. normal variables with positive mean and unit variance. The growth models used to represent the emerging cluster are quite general, and in particular include cellular automata used in modelling epidemics. In both settings, we consider classes of clusters that are quite general, for which we obtain a lower bound on their respective minimax detection rate, and show that some form of scan statistic, by far the most popular method in practice, achieves that same rate within a logarithmic factor. Our results are not limited to the normal location model, but generalize to any one-parameter exponential family when the anoma- lous clusters are large enough.
@cite_24: 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.
@cite_63: The problem of quickest data-adaptive and sequential search for clusters in a Gauss-Markov random field is considered. In the existing literature, such search for clusters is often performed using fixed sample size and non-adaptive strategies. In order to accommodate large networks, in which data adaptivity leads to significant gains in detection quality and agility, in this paper sequential and data-adaptive detection strategies are proposed and are shown to enjoy asymptotic optimality. The quickest detection problem is abstracted by adopting an acyclic dependency graph to model the mutual effects of different random variables in the field and decision making rules are derived for general random fields and specialized for Gauss-Markov random fields. Performance evaluations demonstrate the gains of the data-adaptive schemes over existing techniques in terms of sampling complexity and error exponents.
@cite_16: We provide a unified treatment of a broad class of noisy structure recovery problems, known as structured normal means problems. In these problems, the goal is to identify, from a finite collection of Gaussian distributions with different means, the distribution that produced the observed data. Recent work has studied several special cases including sparse vectors, biclusters, and graph-based structures. We establish nearly matching upper and lower bounds on the minimax probability of error for any structured normal means problem. We also derive an optimality certificate for the maximum likelihood estimator, which can be applied to many instantiations. We consider an experimental design setting, where we generalize our minimax bounds and derive an algorithm for computing a design strategy with a certain optimality property. We show that our results give tight minimax bounds for many structure recovery problems and consider some consequences for interactive sampling.
@cite_13: We develop a matched signal detection (MSD) theory for signals with an intrinsic structure described by a weighted graph. Hypothesis tests are formulated under different signal models. In the simplest scenario, we assume that the signal is deterministic with noise in a subspace spanned by a subset of eigenvectors of the graph Laplacian. The conventional matched subspace detection can be easily extended to this case. Furthermore, we study signals with certain level of smoothness. The test turns out to be a weighted energy detector, when the noise variance is negligible. More generally, we presume that the signal follows a prior distribution, which could be learnt from training data. The test statistic is then the difference of signal variations on associated graph structures, if an Ising model is adopted. Effectiveness of the MSD on graph is evaluated both by simulation and real data. We apply it to the network classification problem of Alzheimer's disease (AD) particularly. The preliminary results demonstrate that our approach is able to exploit the sub-manifold structure of the data, and therefore achieve a better performance than the traditional principle component analysis (PCA).
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.