# A fast topological approach for predicting anomalies in time-varying graphs

arXiv: https://arxiv.org/abs/2305.06523 · HTML: https://mlsanity.com/paper/2305.06523/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 33 references that are in the map.
- First posted on arXiv 11 May 2023.

## Builds on (most cited first, 9 of 9)

- [Persistence Images: A Stable Vector Representation of Persistent Homology](https://mlsanity.com/paper/1507.06217/) (2015)
- [An introduction to Topological Data Analysis: fundamental and practical aspects for data scientists](https://mlsanity.com/paper/1710.04019/) (2017)
- [Geometry Helps to Compare Persistence Diagrams](https://mlsanity.com/paper/1606.03357/) (2016)
- [Persistence Curves: A canonical framework for summarizing persistence diagrams](https://mlsanity.com/paper/1904.07768/) (2019)
- [A Nonparametric Approach for Multiple Change Point Analysis of Multivariate Data](https://mlsanity.com/paper/1306.4933/) (2013)
- [Fast and Accurate Tumor Segmentation of Histology Images using Persistent Homology and Deep Convolutional Features](https://mlsanity.com/paper/1805.03699/) (2018)
- [Dissecting Ethereum Blockchain Analytics: What We Learn from Topology and Geometry of Ethereum Graph](https://mlsanity.com/paper/1912.10105/) (2019)
- [ChainNet: Learning on Blockchain Graphs with Topological Features](https://mlsanity.com/paper/1908.06971/) (2019)
- [Topological Data Analysis of Single-cell Hi-C Contact Maps](https://mlsanity.com/paper/1812.01360/) (2018)

## Built on by (most cited first, 1 of 1)

- [Vector Summaries of Persistence Diagrams for Permutation-based Hypothesis Testing](https://mlsanity.com/paper/2306.06257/) (2023)

## Abstract (arXiv)

Large time-varying graphs are increasingly common in financial, social and biological settings. Feature extraction that efficiently encodes the complex structure of sparse, multi-layered, dynamic graphs presents computational and methodological challenges. In the past decade, a persistence diagram (PD) from topological data analysis (TDA) has become a popular descriptor of shape of data with a well-defined distance between points. However, applications of TDA to graphs, where there is no intrinsic concept of distance between the nodes, remain largely unexplored. This paper addresses this gap in the literature by introducing a computationally efficient framework to extract shape information from graph data. Our framework has two main steps: first, we compute a PD using the so-called lower-star filtration which utilizes quantitative node attributes, and then vectorize it by averaging the associated Betti function over successive scale values on a one-dimensional grid. Our approach avoids embedding a graph into a metric space and has stability properties against input noise. In simulation studies, we show that the proposed vector summary leads to improved change point detection rate in time-varying graphs. In a real data application, our approach provides up to 22% gain in anomalous price prediction for the Ethereum cryptocurrency transaction networks.