A fast topological approach for predicting anomalies in time-varying
  graphs
Umar Islambekov Hasani Pathirana Omid Khormali Cuneyt Akcora Ekaterina Smirnova
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.