On topological descriptors for graph products
Topological descriptors have been increasingly utilized for capturing multiscale structural information in relational data. In this work, we consider various filtrations on the (box) product of graphs and the effect on their outputs on the topological descriptors - the Euler characteristic (EC) and persistent homology (PH). In particular, we establish a complete characterization of the expressive power of EC on general color-based filtrations. We also show that the PH descriptors of (virtual) graph products contain strictly more information than the computation on individual graphs, whereas EC does not. Additionally, we provide algorithms to compute the PH diagrams of the product of vertex- and edge-level filtrations on the graph product. We also substantiate our theoretical analysis with empirical investigations on runtime analysis, expressivity, and graph classification performance. Overall, this work paves way for powerful graph persistent descriptors via product filtrations. Code is available at https://github.com/Aalto-QuML/tda_graph_product.
Code (0)
등록된 구현이 없습니다.
Tasks
Graph ClassificationSimilar Papers 제목 키워드 기반
Topological descriptors for 3D surface analysis
We investigate topological descriptors for 3D surface analysis, i.e. the classification of surfaces according to their geometric fine structure. On a dataset of high-resolution 3D surface reconstructions we compute persi…
ClassificationGeneral ClassificationA Study on Topological Descriptors for the Analysis of 3D Surface Texture
Methods from computational topology are becoming more and more popular in computer vision and have shown to improve the state-of-the-art in several tasks. In this paper, we investigate the applicability of topological de…
General ClassificationDescriptellation: Deep Learned Constellation Descriptors
Current descriptors for global localization often struggle under vast viewpoint or appearance changes. One possible improvement is the addition of topological information on semantic objects. However, handcrafted topolog…
Simultaneous Localization and MappingStability of topological descriptors for neuronal morphology
The topological morphology descriptor of a neuron is a multiset of intervals associated to the shape of the neuron represented as a tree. In practice, topological morphology descriptors are vectorized using persistence i…
Curvature Filtrations for Graph Generative Model Evaluation
Graph generative model evaluation necessitates understanding differences between graphs on the distributional level. This entails being able to harness salient attributes of graphs in an efficient manner. Curvature const…
modelTopological Data Analysis