Detecting Weak but Hierarchically-Structured Patterns in Networks

The ability to detect weak distributed activation patterns in networks is critical to several applications, such as identifying the onset of anomalous activity or incipient congestion in the Internet, or faint traces of a biochemical spread by a sensor network. This is a challenging problem since weak distributed patterns can be invisible in per node statistics as well as a global network-wide aggregate. Most prior work considers situations in which the activation/non-activation of each node is statistically independent, but this is unrealistic in many problems. In this paper, we consider structured patterns arising from statistical dependencies in the activation process. Our contributions are three-fold. First, we propose a sparsifying transform that succinctly represents structured activation patterns that conform to a hierarchical dependency graph. Second, we establish that the proposed transform facilitates detection of very weak activation patterns that cannot be detected with existing methods. Third, we show that the structure of the hierarchical dependency graph governing the activation process, and hence the network transform, can be learnt from very few (logarithmic in network size) independent snapshots of network activity.

• Publication year

  2010

• Venue

  International Conference on Artificial Intelligence and Statistics

• Publication date

  2010-02-28

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1003.0205
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Combinatorial Testing Problems

  2009cited by this paper
• Detection of an Abnormal Cluster in a Network

  2009cited by this paper
• Sparse classification boundaries

  2009influential reference
• On the treeness of internet latency and bandwidth

  2009cited by this paper
• Searching for a trail of evidence in a maze

  2007cited by this paper
• Treelets--An adaptive multi-scale basis for sparse unordered data

  2007cited by this paper
• The Haar Wavelet Transform of a Dendrogram

  2006influential reference
• Genomic analysis of the hierarchical structure of regulatory networks

  2006cited by this paper
• GOODNESS-OF-FIT TESTS VIA PHI-DIVERGENCES

  2006cited by this paper
• Signal Reconstruction From Noisy Random Projections

  2006cited by this paper
• Near-optimal detection of geometric objects by fast multiscale methods

  2005cited by this paper
• Hierarchical sensor networks: capacity bounds and cooperative strategies using the multiple-access relay channel model

  2004influential reference
• Nonparametric Goodness-of-Fit Testing Under Gaussian Models

  2004influential reference
• Higher criticism for detecting sparse heterogeneous mixtures

  2004influential reference
• Nonparametric Goodness-of-Fit Testing Under Gaussian Models

  2002influential reference
• Community structure in social and biological networks

  2001cited by this paper
• Distributed Detection and Data Fusion

  1996cited by this paper
• Controlling the false discovery rate: a practical and powerful approach to multiple testing

  1995cited by this paper
• Ising spin system on a Cayley tree: Correlation decomposition and phase transition

  1975cited by this paper

• Constrained estimation via the fused lasso and some generalizations

  2017cites this paper
• Data-Driven Tree Transforms and Metrics

  2017cites this paper
• Multiscale network analysis through tail-greedy bottom-up approximation, with applications in neuroscience

  2017cites this paper
• SHAH: SHape-Adaptive Haar Wavelets for Image Processing

  2016cites this paper
• Detecting Localized Categorical Attributes on Graphs

  2016cites this paper
• Structured patterns retrieval using a metric attractor network: Application to fingerprint recognition

  2016cites this paper
• Detecting Structure-correlated Attributes on Graphs

  2016cites this paper
• The DFS Fused Lasso: Linear-Time Denoising over General Graphs

  2016cites this paper
• Anomalous cluster detection

  2014cites this paper
• Community Sense and Response Systems

  2014influential citation
• Connected Sub-graph Detection

  2014cites this paper
• Detecting Activity in Graphs with Spectral Scan Relaxations

  2013cites this paper
• Graph Structured Normal Means Inference

  2013cites this paper
• A fresh perspective: Learning to sparsify for detection in massive noisy sensor networks

  2013influential citation
• Resource-constrained Data Collection and Fusion for Identifying Weak Distributed Patterns in Networks

  2013cites this paper
• An impossibility result for high dimensional supervised learning

  2013cites this paper
• Detecting Anomalous Activity on Networks With the Graph Fourier Scan Statistic

  2013cites this paper
• Sensor Networks for Geospatial Event Detection - Theory and Applications

  2013cites this paper
• Detecting Activations over Graphs using Spanning Tree Wavelet Bases

  2012cites this paper
• Sparsistency of the Edge Lasso over Graphs

  2012cites this paper
• Shah: Shape-Adaptive Haar Wavelet Transform For Images With Application To Classification

  2012cites this paper
• Proposal : Graph Structured Statistical Inference

  2012cites this paper
• Harmonic Analysis of Digital Data Bases

  2011cites this paper
• Sensing structure in learning-based binary classification of high-dimensional data

  2011cites this paper
• Using Dimension Reduction Techniques to Model Genetic Relationships for Association Studies Thesis Proposal for

  2010cites this paper
• Identifying graph-structured activation patterns in networks

  2010cites this paper
• FINAL REPORT : AFOSR GRANT FA 9550-10-1-0382 Resource-constrained Data Collection and Fusion for Identifying Weak Distributed Patterns in Networks Duration : July 15 , 2010 to July 14 , 2013

  2009cites this paper