Change Point Detection in Dynamic Graphs with Decoder-only Latent Space Model

This manuscript studies the unsupervised change point detection problem in time series of graphs using a decoder-only latent space model. The proposed framework consists of learnable prior distributions for low-dimensional graph representations and of a decoder that bridges the observed graphs and latent representations. The prior distributions of the latent spaces are learned from the observed data as empirical Bayes to assist change point detection. Specifically, the model parameters are estimated via maximum approximate likelihood, with a Group Fused Lasso regularization imposed on the prior parameters. The augmented Lagrangian is solved via Alternating Direction Method of Multipliers, and Langevin Dynamics are recruited for posterior inference. Simulation studies show good performance of the latent space model in supporting change point detection and real data experiments yield change points that align with significant events.

• Publication year

  2024

• Venue

  Trans. Mach. Learn. Res.

• Publication date

  2024-04-06

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 2404.04719
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• VGGM: Variational Graph Gaussian Mixture Model for Unsupervised Change Point Detection in Dynamic Networks

  2024cited by this paper
• Euclidean mirrors and first-order changepoints in network time series

  2024cited by this paper
• The Heterophilic Graph Learning Handbook: Benchmarks, Models, Theoretical Analysis, Applications and Challenges

  2024cited by this paper
• Discovering Communication Pattern Shifts in Large-Scale Labeled Networks Using Encoder Embedding and Vertex Dynamics

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

  2023influential reference
• Change point detection and inference in multivariate non-parametric models under mixing conditions

  2023cited by this paper
• Spatial mapping of mitochondrial networks and bioenergetics in lung cancer

  2023cited by this paper
• A partially separable model for dynamic valued networks

  2023cited by this paper
• Relational event models in network science

  2023cited by this paper
• Revisiting Heterophily For Graph Neural Networks

  2022cited by this paper
• A Generalization of ViT/MLP-Mixer to Graphs

  2022cited by this paper
• New kernel-based change-point detection

  2022cited by this paper
• Euclidean Mirrors and Dynamics in Network Time Series

  2022cited by this paper
• Graph similarity learning for change-point detection in dynamic networks

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

  2022cited by this paper
• Spectral embedding for dynamic networks with stability guarantees

  2021cited by this paper
• Optimal network online change point localisation

  2021cited by this paper
• High-Resolution Image Synthesis with Latent Diffusion Models

  2021cited by this paper
• scGNN is a novel graph neural network framework for single-cell RNA-Seq analyses

  2021cited by this paper
• Disentangling positive and negative partisanship in social media interactions using a coevolving latent space network with attractors model

  2021cited by this paper
• Change Point Detection in Weighted and Directed Random Dot Product Graphs

  2021cited by this paper
• Graph Neural Networks with Learnable Structural and Positional Representations

  2021cited by this paper
• An Evaluation of Change Point Detection Algorithms

  2020cited by this paper
• Generative Adversarial Attributed Network Anomaly Detection

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

  2020cited by this paper
• Laplacian Change Point Detection for Dynamic Graphs

  2020cited by this paper
• Denoising Diffusion Probabilistic Models

  2020cited by this paper
• A statistical approach for social network change detection: an ERGM based framework

  2020cited by this paper
• Asymptotic distribution-free change-point detection for data with repeated observations

  2020cited by this paper
• Learning Latent Space Energy-Based Prior Model

  2020cited by this paper
• AUTO-ENCODING VARIATIONAL BAYES

  2020cited by this paper
• On the Anatomy of MCMC-based Maximum Likelihood Learning of Energy-Based Models

  2019cited by this paper
• BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding

  2019cited by this paper
• Change-point detection in dynamic networks via graphon estimation

  2019cited by this paper
• Conditional Structure Generation through Graph Variational Generative Adversarial Nets

  2019cited by this paper
• BART: Denoising Sequence-to-Sequence Pre-training for Natural Language Generation, Translation, and Comprehension

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

  2019influential reference
• Detecting Structural Changes in Longitudinal Network Data

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

  2018influential reference
• GraphVAE: Towards Generation of Small Graphs Using Variational Autoencoders

  2018cited by this paper
• Accurate and Diverse Sampling of Sequences Based on a "Best of Many" Sample Objective

  2018cited by this paper
• DESIRE: Distant Future Prediction in Dynamic Scenes with Interacting Agents

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

  2017cited by this paper
• Inductive Representation Learning on Large Graphs

  2017cited by this paper
• An Augmented ADMM Algorithm With Application to the Generalized Lasso Problem

  2017cited by this paper
• Consistent change-point detection with kernels

  2016cited by this paper
• Cooperative Training of Descriptor and Generator Networks

  2016cited by this paper
• Synthesizing Dynamic Patterns by Spatial-Temporal Generative ConvNet

  2016cited by this paper
• Variational Graph Auto-Encoders

  2016cited by this paper
• Likelihood-based model selection for stochastic block models

  2015cited by this paper
• Statistical Analysis of Network Data with R

  2015cited by this paper
• Global Convergence of ADMM in Nonconvex Nonsmooth Optimization

  2015cited by this paper
• Rate-optimal graphon estimation

  2014cited by this paper
• Detecting Change Points in the Large-Scale Structure of Evolving Networks

  2014cited by this paper
• Group Fused Lasso

  2013cited by this paper
• Network histograms and universality of blockmodel approximation

  2013cited by this paper
• Stochastic blockmodel approximation of a graphon: Theory and consistent estimation

  2013cited by this paper
• Exponential-family Random Network Models

  2012cited by this paper
• Pseudo-likelihood methods for community detection in large sparse networks

  2012cited by this paper
• Graph-based change-point detection

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

  2012cited by this paper
• Consistency of community detection in networks under degree-corrected stochastic block models

  2011cited by this paper
• Optimal detection of changepoints with a linear computational cost

  2011cited by this paper
• Exponential-family random graph models for valued networks.

  2011cited by this paper
• The group fused Lasso for multiple change-point detection

  2011influential reference
• A separable model for dynamic networks

  2010cited by this paper
• Stochastic blockmodels and community structure in networks

  2010cited by this paper
• Introduction to stochastic actor-based models for network dynamics

  2010cited by this paper
• Fast detection of multiple change-points shared by many signals using group LARS

  2010cited by this paper
• Goodness of Fit of Social Network Models

  2008cited by this paper
• Estimating time-varying networks

  2008cited by this paper
• ergm: A Package to Fit, Simulate and Diagnose Exponential-Family Models for Networks.

  2008cited by this paper
• 4. A Relational Event Framework for Social Action

  2008cited by this paper
• Model‐based clustering for social networks

  2007cited by this paper
• Inference in Curved Exponential Family Models for Networks

  2006cited by this paper
• Discrete Temporal Models of Social Networks

  2006influential reference
• Reality mining: sensing complex social systems

  2006cited by this paper
• Model selection and estimation in regression with grouped variables

  2006cited by this paper
• Scan Statistics on Enron Graphs

  2005cited by this paper
• Latent Space Approaches to Social Network Analysis

  2002cited by this paper
• The statistical evaluation of social network dynamics

  2001cited by this paper

• Change Point Detection on A Separable Model for Dynamic Networks

  2023cites this paper