Reduction Algorithms for Persistence Diagrams of Networks: CoralTDA and PrunIT
Reduction Algorithms for Persistence Diagrams of Networks: CoralTDA and PrunIT
复制标题
DOI：
10.48550/arxiv.2211.13708
复制
发表时间：
2022-11
期刊：
影响因子：
--
通讯作者：
C. Akcora;Murat Kantarcioglu;Y. Gel;Baris Coskunuzer
中科院分区：
文献类型：
--
作者：
C. Akcora;Murat Kantarcioglu;Y. Gel;Baris Coskunuzer
拓扑数据分析(TDA)提供了传统方法无法获得的关于数据内在属性的宝贵和补充信息。然而，高昂的计算成本仍然是阻碍TDA在现实世界研究中成功应用的主要障碍，特别是在大型复杂网络上的机器学习。事实上，大多数现代网络，如引文、区块链和在线社交网络，往往有数十万个顶点，这使得应用现有的TDA方法是不可行的。我们开发了两个新的、非常简单但有效的算法来计算大型图的精确持续图，以解决这一主要的TDA限制。首先，我们证明了一个图的$(k+1)$-core足以计算它的$k^{th}$持久性图$pd_k(\mathcal{G})$。其次，我们提出了一种剪枝算法，通过删除支配顶点来计算图的持久性图。我们在大型网络上的实验表明，我们的新方法可以获得高达95%的计算收益。该框架在图论和TDA之间架起了第一座桥梁，并在大型复杂网络的机器学习中得到了应用。我们的实施可在https://github.com/cakcora/PersistentHomologyWithCoralPrunit上获得
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 $\mathcal{G}$ suffices to compute its $k^{th}$ persistence diagram, $PD_k(\mathcal{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