Online detection of local abrupt changes in high-dimensional Gaussian graphical models

• URL: http://arxiv.org/abs/2003.06961v1
• Date: Mon, 16 Mar 2020 00:41:34 GMT
• Title: Online detection of local abrupt changes in high-dimensional Gaussian graphical models
• Authors: Hossein Keshavarz, George Michailidis
• Abstract summary: The problem of identifying change points in high-dimensional Gaussian graphical models (GGMs) in an online fashion is of interest, due to new applications in biology, economics and social sciences. We develop a novel test to address this problem that is based on the $ell_infty$ norm of the normalized covariance matrix of an appropriately selected portion of incoming data.
• Score: 13.554038901140949
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The problem of identifying change points in high-dimensional Gaussian graphical models (GGMs) in an online fashion is of interest, due to new applications in biology, economics and social sciences. The offline version of the problem, where all the data are a priori available, has led to a number of methods and associated algorithms involving regularized loss functions. However, for the online version, there is currently only a single work in the literature that develops a sequential testing procedure and also studies its asymptotic false alarm probability and power. The latter test is best suited for the detection of change points driven by global changes in the structure of the precision matrix of the GGM, in the sense that many edges are involved. Nevertheless, in many practical settings the change point is driven by local changes, in the sense that only a small number of edges exhibit changes. To that end, we develop a novel test to address this problem that is based on the $\ell_\infty$ norm of the normalized covariance matrix of an appropriately selected portion of incoming data. The study of the asymptotic distribution of the proposed test statistic under the null (no presence of a change point) and the alternative (presence of a change point) hypotheses requires new technical tools that examine maxima of graph-dependent Gaussian random variables, and that of independent interest. It is further shown that these tools lead to the imposition of mild regularity conditions for key model parameters, instead of more stringent ones required by leveraging previously used tools in related problems in the literature. Numerical work on synthetic data illustrates the good performance of the proposed detection procedure both in terms of computational and statistical efficiency across numerous experimental settings.

Related papers

• Reproduction of scan B-statistic for kernel change-point detection algorithm [10.49860279555873]
  Change-point detection has garnered significant attention due to its broad range of applications. In this paper, we reproduce a recently proposed online change-point detection algorithm based on an efficient kernel-based scan B-statistic. Our numerical experiments demonstrate that the scan B-statistic consistently delivers superior performance.
  arXiv  Detail & Related papers  (2024-08-23T15:12:31Z)
• Generation is better than Modification: Combating High Class Homophily Variance in Graph Anomaly Detection [51.11833609431406]
  Homophily distribution differences between different classes are significantly greater than those in homophilic and heterophilic graphs. We introduce a new metric called Class Homophily Variance, which quantitatively describes this phenomenon. To mitigate its impact, we propose a novel GNN model named Homophily Edge Generation Graph Neural Network (HedGe)
  arXiv  Detail & Related papers  (2024-03-15T14:26:53Z)
• Graph Spatiotemporal Process for Multivariate Time Series Anomaly Detection with Missing Values [67.76168547245237]
  We introduce a novel framework called GST-Pro, which utilizes a graphtemporal process and anomaly scorer to detect anomalies. Our experimental results show that the GST-Pro method can effectively detect anomalies in time series data and outperforms state-of-the-art methods.
  arXiv  Detail & Related papers  (2024-01-11T10:10:16Z)
• Unsupervised Anomaly and Change Detection with Multivariate Gaussianization [8.508880949780893]
  Anomaly detection is a challenging problem given the high-dimensionality of the data. We propose an unsupervised method for detecting anomalies and changes in remote sensing images. We show the efficiency of the method in experiments involving both anomaly detection and change detection.
  arXiv  Detail & Related papers  (2022-04-12T10:52:33Z)
• High dimensional change-point detection: a complete graph approach [0.0]
  We propose a complete graph-based, change-point detection algorithm to detect change of mean and variance from low to high-dimensional online data. Inspired by complete graph structure, we introduce graph-spanning ratios to map high-dimensional data into metrics. Our approach has high detection power with small and multiple scanning window, which allows timely detection of change-point in the online setting.
  arXiv  Detail & Related papers  (2022-03-16T15:59:20Z)
• E-detectors: a nonparametric framework for sequential change detection [86.15115654324488]
  We develop a fundamentally new and general framework for sequential change detection. Our procedures come with clean, nonasymptotic bounds on the average run length. We show how to design their mixtures in order to achieve both statistical and computational efficiency.
  arXiv  Detail & Related papers  (2022-03-07T17:25:02Z)
• Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methods [73.35353358543507]
  Gradient Descent-Ascent (SGDA) is one of the most prominent algorithms for solving min-max optimization and variational inequalities problems (VIP) In this paper, we propose a unified convergence analysis that covers a large variety of descent-ascent methods. We develop several new variants of SGDA such as a new variance-reduced method (L-SVRGDA), new distributed methods with compression (QSGDA, DIANA-SGDA, VR-DIANA-SGDA), and a new method with coordinate randomization (SEGA-SGDA)
  arXiv  Detail & Related papers  (2022-02-15T09:17:39Z)
• Partially Observable Online Change Detection via Smooth-Sparse Decomposition [16.8028358824706]
  We consider online change detection of high dimensional data streams with sparse changes, where only a subset of data streams can be observed at each sensing time point due to limited sensing capacities. On the one hand, the detection scheme should be able to deal with partially observable data and meanwhile have efficient detection power for sparse changes. In this paper, we propose a novel detection scheme called CDSSD. In particular, it describes the structure of high dimensional data with sparse changes by smooth-sparse decomposition.
  arXiv  Detail & Related papers  (2020-09-22T16:03:04Z)
• Learning Domain-invariant Graph for Adaptive Semi-supervised Domain Adaptation with Few Labeled Source Samples [65.55521019202557]
  Domain adaptation aims to generalize a model from a source domain to tackle tasks in a related but different target domain. Traditional domain adaptation algorithms assume that enough labeled data, which are treated as the prior knowledge are available in the source domain. We propose a Domain-invariant Graph Learning (DGL) approach for domain adaptation with only a few labeled source samples.
  arXiv  Detail & Related papers  (2020-08-21T08:13:25Z)
• Offline detection of change-points in the mean for stationary graph signals [55.98760097296213]
  We propose an offline method that relies on the concept of graph signal stationarity. Our detector comes with a proof of a non-asymptotic inequality oracle.
  arXiv  Detail & Related papers  (2020-06-18T15:51:38Z)
• High-dimensional, multiscale online changepoint detection [7.502070498889449]
  We introduce a new method for high-dimensional, online changepoint detection in settings where a $p$- Gaussian data stream may undergo a change in mean. The algorithm is online in the sense that both its storage requirements and worst-case computational complexity per new observation are independent of the number of previous observations. Simulations confirm the practical effectiveness of our proposal, which is implemented in the R package 'ocd', and we also demonstrate its utility on a seismology data set.
  arXiv  Detail & Related papers  (2020-03-07T21:54:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.