Locality Statistics for Anomaly Detection in Time Series of Graphs

The ability to detect change-points in a dynamic network or a time series of graphs is an increasingly important task in many applications of the emerging discipline of graph signal processing. This paper formulates change-point detection as a hypothesis testing problem in terms of a generative latent position model, focusing on the special case of the Stochastic Block Model time series. We analyze two classes of scan statistics, based on distinct underlying locality statistics presented in the literature. Our main contribution is the derivation of the limiting properties and power characteristics of the competing scan statistics. Performance is compared theoretically, on synthetic data, and empirically, on the Enron email corpus.

• Publication year

  2013

• Venue

  IEEE Transactions on Signal Processing

• Publication date

  2013-06-03

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/TSP.2013.2294594arXiv 1306.0267
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Scan Statistics

  2014cited by this paper
• Spatial Scan Statistic

  2014cited by this paper
• Community Detection in Random Networks

  2013cited by this paper
• NetSpot: Spotting Significant Anomalous Regions on Dynamic Networks

  2013cited by this paper
• Anomaly Detection in Time Series of Graphs using Fusion of Graph Invariants

  2012cited by this paper
• On Latent Position Inference from Doubly Stochastic Messaging Activities

  2012cited by this paper
• On the Limiting Distribution of a Graph Scan Statistic

  2012cited by this paper
• Scan statistics on graphs

  2012cited by this paper
• I and J

  2012cited by this paper
• A latent process model for time series of attributed random graphs

  2011influential reference
• Scan statistics for the online discovery of locally anomalous subgraphs

  2011cited by this paper
• Attribute fusion in a latent process model for time series of graphs

  2011influential reference
• Fluctuations of Spiked Random Matrix Models and Failure Diagnosis in Sensor Networks

  2011cited by this paper
• Subgraph Detection Using Eigenvector L1 Norms

  2010cited by this paper
• Bayesian anomaly detection methods for social networks

  2010influential reference
• this paper

  2009cited by this paper
• Spatial Scan Statistics for Graph Clustering

  2008cited by this paper
• Random Dot Product Graph Models for Social Networks

  2007cited by this paper
• Influence of cultivation temperature on the ligninolytic activity of selected fungal strains

  2006cited by this paper
• Scan Statistics on Enron Graphs

  2005influential reference
• Latent Space Approaches to Social Network Analysis

  2002cited by this paper
• Stochastic Blockmodels for Directed Graphs

  1987cited by this paper
• Stochastic blockmodels: First steps

  1983cited by this paper
• The Asymptotic Theory of Extreme Order Statistics

  1979cited by this paper
• Limit Theorems for the Maximum Term in Stationary Sequences

  1964cited by this paper
• Computational Statistics and Data Analysis Statistical Inference on Attributed Random Graphs: Fusion of Graph Features and Content: an Experiment on Time Series of Enron Graphs

  year unknowncited by this paper

• Comprehensive Robust Dynamic Mode Decomposition from Mode Extraction to Dimensional Reduction

  2026cites this paper
• Beyond Euclidean Summaries: Online Change Point Detection for Distribution-Valued Data

  2026cites this paper
• Change-Point Detection With Multivariate Repeated Measures

  2025cites this paper
• Anomaly detection for live streaming graphs using copula based student-t process regression

  2025cites this paper
• A Proof of The Changepoint Detection Threshold Conjecture in Preferential Attachment Models

  2025cites this paper
• Anomaly Detection in Graph Structured Data: A Survey

  2024cites this paper
• WMSNs Data Hidden Anomaly Detection Based on OH-KFJLT Bloom Filter

  2024cites this paper
• Modelling and monitoring multi-relational networks with ordinal information

  2024cites this paper
• Efficient Cyberattack Detection Methods in Industrial Control Systems

  2024cites this paper
• Detecting a late changepoint in the preferential attachment model

  2023cites this paper
• MedGraph: malicious edge detection in temporal reciprocal graph via multi-head attention-based GNN

  2023cites this paper
• An improved k-NN anomaly detection framework based on locality sensitive hashing for edge computing environment

  2023cites this paper
• Forgery Cyber-Attack Supported by LSTM Neural Network: An Experimental Case Study

  2023cites this paper
• Change Point Detection on A Separable Model for Dynamic Networks

  2023cites this paper
• Graph similarity learning for change-point detection in dynamic networks

  2022cites this paper
• Identification of patterns for space-time event networks

  2022cites this paper
• Anomaly Detection in Multiplex Dynamic Networks: from Blockchain Security to Brain Disease Prediction

  2022cites this paper
• Online Change Point Detection for Weighted and Directed Random Dot Product Graphs

  2022cites this paper
• Anomalous Subgraph Detection in Given Expected Degree Networks With Deep Learning

  2021cites this paper
• Online Change Point Detection for Random Dot Product Graphs

  2021cites this paper
• Anomaly Detection in Edge Streams Using Term Frequency-Inverse Graph Frequency (TF-IGF) Concept

  2021cites this paper
• Latent Space Model for Higher-Order Networks and Generalized Tensor Decomposition

  2021cites this paper
• Change-Point Detection in Dynamic Networks with Missing Links

  2021cites this paper
• Network approaches in anomaly detection for disease conditions

  2021cites this paper
• Spectral analysis of networks with latent space dynamics and signs

  2021cites this paper
• Anomalous IoT Sensor Data Detection: An Efficient Approach Enabled by Nonlinear Frequency-Domain Graph Analysis

  2021cites this paper
• Long-Short Term Echo State Network for Time Series Prediction

  2020cites this paper
• Exploiting Pattern Set Dissimilarity for Detecting Changes in Communication Networks

  2020cites this paper
• GRAPH MATCHING AND VERTEX NOMINATION

  2020cites this paper
• F-FADE: Frequency Factorization for Anomaly Detection in Edge Streams

  2020cites this paper
• Non‐parametric regression for networks

  2020cites this paper
• Multiple network embedding for anomaly detection in time series of graphs

  2020cites this paper
• The Importance of Being Correlated: Implications of Dependence in Joint Spectral Inference across Multiple Networks

  2020cites this paper
• Local Statistic With Dynamic Vertex Selection for Change-Point Detection in Stochastic Block Networks

  2020influential citation
• A Fast and Efficient Change-point Detection Framework for Modern Data

  2020cites this paper
• Detection and Locating Cyber and Physical Stresses in Smart Grids using Graph Signal Processing

  2020cites this paper
• Performance evaluation method for network monitoring based on separable temporal exponential random graph models with application to the study of autocorrelation effects

  2020cites this paper
• Nonlinear Polynomial Graph Filter for Anomalous IoT Sensor Detection and Localization

  2020cites this paper
• A Probabilistic Framework to Node-level Anomaly Detection in Communication Networks

  2019cites this paper
• High-Order Temporal Correlation Model Learning for Time-Series Prediction

  2019cites this paper
• Anomaly Detection in the Dynamics of Web and Social Networks Using Associative Memory

  2019cites this paper
• A comprehensive survey of anomaly detection in banking, wireless sensor networks, social networks, and healthcare

  2019cites this paper
• Community Correlations and Testing Independence Between Binary Graphs

  2019cites this paper
• Detecting malicious logins as graph anomalies

  2019cites this paper
• Change point localization in dependent dynamic nonparametric random dot product graphs

  2019cites this paper
• Modelling and prediction of financial trading networks: an application to the New York Mercantile Exchange natural gas futures market

  2019cites this paper
• Anomalous Sensor Detection Based on Nonlinear Graph Filter

  2019cites this paper
• Official Journal of the Bernoulli Society for Mathematical Statistics and Probability

  2019cites this paper
• Change detection in dynamic attributed networks

  2018influential citation
• An Unsupervised Anomaly Detection Algorithm for Time Series Big Data

  2018cites this paper
• Optimal change point detection and localization in sparse dynamic networks

  2018cites this paper
• Change point detection in social networks - Critical review with experiments

  2018cites this paper
• Exact variable-length anomaly detection algorithm for univariate and multivariate time series

  2018cites this paper
• Scan Statistics on Graphs and Networks

  2018cites this paper
• Contributions à la calibration d'algorithmes d'apprentissage : Validation-croisée et détection de ruptures

  2018cites this paper
• Error sensitivity analysis of Delta divergence - a novel measure for classifier incongruence detection

  2018cites this paper
• Three-dimensional piecewise cloud representation for time series data mining

  2018cites this paper
• Anomaly detection based on a dynamic Markov model

  2017cites this paper
• Asymptotic distribution-free change-point detection for multivariate and non-Euclidean data

  2017cites this paper
• Vertex nomination via seeded graph matching

  2017cites this paper
• A statistical approach to social network monitoring

  2017cites this paper
• Vertex Nomination Via Local Neighborhood Matching

  2017cites this paper
• A New Time Series Representation Model and Corresponding Similarity Measure for Fast and Accurate Similarity Detection

  2017cites this paper
• Bernoulli Are there needles in a moving haystack ? Adaptive sensing for detection of dynamically evolving signals RUI

  2017cites this paper
• Are there needles in a moving haystack? Adaptive sensing for detection of dynamically evolving signals

  2017cites this paper
• FUSION AND INFERENCE FROM MULTIPLE AND MASSIVE DISPARATE DISTRIBUTED DYNAMIC DATA SETS

  2017cites this paper
• Behavioral Service Graphs: A formal data-driven approach for prompt investigation of enterprise and internet-wide infections

  2017cites this paper
• FUSION AND INFERENCE FROM MULTIPLE AND MASSIVE DISPARATE DISTRIBUTED DYNAMIC DATA SETS

  2017cites this paper
• A Novel Method for Fast and Accurate Similarity Measure in Time Series Field

  2017cites this paper
• A Piecewise Aggregate pattern representation approach for anomaly detection in time series

  2017cites this paper
• Identifying Market Behaviours Using European Stock Index Time Series by a Hybrid Segmentation Algorithm

  2017cites this paper
• Modelling and prediction of financial trading networks: An application to the NYMEX natural gas futures market

  2017cites this paper
• Compression of spatio-temporal networks via point-to-point process models

  2017cites this paper
• Scalable Algorithms for Mining Dynamic Graphs and Hypergraphs with Applications to Anomaly Detection.

  2017cites this paper
• The Kato-Temple inequality and eigenvalue concentration

  2016influential citation
• Efficient NP Tests for Anomaly Detection Over Birth-Death Type DTMCs

  2016cites this paper
• Sequential change-point detection based on nearest neighbors

  2016cites this paper
• Graph analysis combining numerical, statistical, and streaming techniques

  2016cites this paper
• Piecewise two-dimensional normal cloud representation for time-series data mining

  2016cites this paper
• Online Anomaly Detection Under Markov Statistics With Controllable Type-I Error

  2016influential citation
• A Self-Learning and Online Algorithm for Time Series Anomaly Detection, with Application in CPU Manufacturing

  2016cites this paper
• Advances in Model Selection Techniques with Applications to Statistical Network Analysis and Recommender Systems

  2016cites this paper
• Behavioral Service Graphs: A Big Data Approach for Prompt Investigation of Internet-Wide Infections

  2016cites this paper
• Identifying Anomalies in Graph Streams Using Change Detection

  2016cites this paper
• The Kato–Temple inequality and eigenvalue concentration with applications to graph inference

  2016cites this paper
• Likelihood-based assessment of dynamic networks

  2016cites this paper
• Information Recovery in Shuffled Graphs via Graph Matching

  2016cites this paper
• Querying of Time Series for Big Data Analytics

  2016cites this paper
• Anomaly Detection in Graph : Unsupervised Learning , Graph-based Features and Deep Architecture

  2015cites this paper
• Big Data Analytics for Social Networks

  2015cites this paper
• Properties of latent variable network models

  2015cites this paper
• Community Detection using Locality Statistics

  2015influential citation
• Anomaly detection in dynamic networks: a survey

  2015cites this paper
• Behavioral clusters in dynamic graphs

  2015cites this paper
• Kernel neighbor density with parallel computing mechanism for anomaly detection algorithm

  2015cites this paper
• Anomaly Detection on Whole-Brain Functional Imaging of Neuronal Activity using Graph Scan Statistics

  2015cites this paper
• Online anomaly detection with constant false alarm rate

  2015cites this paper
• A Principled Massive-Graph Similarity Function with Attribution

  2015cites this paper
• FlashGraph: Processing Billion-Node Graphs on an Array of Commodity SSDs

  2014cites this paper
• Network Analysis with the Enron Email Corpus

  2014cites this paper