Stable distance of persistent homology for dynamic graph comparison

Persistent homology theory provides approaches for analyzing topological features, which is now widely applied in graph comparison on social networks, biological networks, and co-location networks. These approaches utilize filtration techniques to extract the topological properties of a graph and construct vectorizations that represent these properties for further computation. However, most existing methods are designed for static scenarios and are unsuitable for the time-varying structure in realistic dynamic graphs. In this paper, we propose the Stable Distance of Persistent Homology (SDPH) to compare and quantify the differences in the topological properties of dynamic graphs. In detail, we design Dynamic Dowker Filtration (DDF) to map dynamic graph to a persistent complex based on the e-interleaved theory, which enables us to trace the structure holes formed by the accumulation of temporal edge via computing the persistent homology. DDF exhibits stability and duality, inducing a time-structure triangle inequality. Based on this inequality, we finally construct Time-interlevel Kernel (TIK) for vectorizing the extracted topological features with an inner product. We conduct the graph clustering and classification experiments on synthetic and real-world datasets. Experimental results show that the proposed SDPH outperforms the baseline methods in these tasks and validate that the proposed SDPH can effectively measure the topological difference of dynamic graphs. Through SDPH, we would provide insight and inspiration on how to apply persistent homology theory to dynamic graph analysis. (c) 2023 Published by Elsevier B.V.

Automated summary

Persistent homology theory is widely used for analyzing topological features, but existing methods are not suitable for the time-varying structure in dynamic graphs. This paper proposes Stable Distance of Persistent Homology (SDPH) to compare and quantify the differences in the topological properties of dynamic graphs. The proposed approach, utilizing Dynamic Dowker Filtration and Time-interlevel Kernel, effectively measures the topological difference of dynamic graphs.