# Reduction Algorithms for Persistence Diagrams of Networks: CoralTDA and PrunIT

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 63 references that are in the map.
- First posted on arXiv 24 Nov 2022.

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

- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [An introduction to Topological Data Analysis: fundamental and practical aspects for data scientists](https://mlsanity.com/paper/1710.04019/) (2017)
- [A roadmap for the computation of persistent homology](https://mlsanity.com/paper/1506.08903/) (2015)
- [Deep Learning with Topological Signatures](https://mlsanity.com/paper/1707.04041/) (2017)
- [Simplicial Closure and higher-order link prediction](https://mlsanity.com/paper/1802.06916/) (2018)
- [Topological Graph Neural Networks](https://mlsanity.com/paper/2102.07835/) (2021)
- [Graph Filtration Learning](https://mlsanity.com/paper/1905.10996/) (2019)
- [Learning metrics for persistence-based summaries and applications for graph classification](https://mlsanity.com/paper/1904.12189/) (2019)
- [Link Prediction with Persistent Homology: An Interactive View](https://mlsanity.com/paper/2102.10255/) (2021)
- [Persistence Homology of Networks: Methods and Applications](https://mlsanity.com/paper/1907.08708/) (2019)
- [Topological Relational Learning on Graphs](https://mlsanity.com/paper/2110.15529/) (2021)
- [Using persistent homology and dynamical distances to analyze protein binding](https://mlsanity.com/paper/1412.1394/) (2014)
- [Volume Optimal Cycle: Tightest representative cycle of a generator on persistent homology](https://mlsanity.com/paper/1712.05103/) (2017)
- [Topological Anomaly Detection in Dynamic Multilayer Blockchain Networks](https://mlsanity.com/paper/2106.01806/) (2021)
- [Persistent 1-Cycles: Definition, Computation, and Its Application](https://mlsanity.com/paper/1810.04807/) (2018)
- [Understanding the Power of Persistence Pairing via Permutation Test](https://mlsanity.com/paper/2001.06058/) (2020)
- [Classification of weighted networks through mesoscale homological features](https://mlsanity.com/paper/1512.06457/) (2015)

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

- [Explaining the Power of Topological Data Analysis in Graph Machine Learning](https://mlsanity.com/paper/2401.04250/) (2024)
- [TopER: Topological Embeddings in Graph Representation Learning](https://mlsanity.com/paper/2410.01778/) (2024)

## Abstract (arXiv)

Topological data analysis (TDA) delivers invaluable and complementary information on the intrinsic properties of data inaccessible to conventional methods. However, high computational costs remain the primary roadblock hindering the successful application of TDA in real-world studies, particularly with machine learning on large complex networks. Indeed, most modern networks such as citation, blockchain, and online social networks often have hundreds of thousands of vertices, making the application of existing TDA methods infeasible. We develop two new, remarkably simple but effective algorithms to compute the exact persistence diagrams of large graphs to address this major TDA limitation. First, we prove that (k+1)-core of a graph G suffices to compute its kth persistence diagram, PDk(G). Second, we introduce a pruning algorithm for graphs to compute their persistence diagrams by removing the dominated vertices. Our experiments on large networks show that our novel approach can achieve computational gains up to 95%. The developed framework provides the first bridge between the graph theory and TDA, with applications in machine learning of large complex networks. Our implementation is available at https://github.com/cakcora/PersistentHomologyWithCoralPrunit