通过图积的拓扑描述符，揭示了持久同调比欧拉示性数更丰富信息。
On topological descriptors for graph products
- 基于颜色滤波构建图积的拓扑分析框架
- 持久同调在图积上包含严格更多信息，而欧拉示性数不具优势
- 提供顶点与边级滤波的持久同调计算算法，适合图学习研究者
拓扑描述符在捕捉关系数据的多尺度结构信息方面日益重要。本文研究图（盒积）的各种滤波及其对拓扑描述符——欧拉示性数（EC）和持久同调（PH）的影响。我们完整刻画了EC在一般基于颜色的滤波下的表达能力。结果表明，图积的持久同调描述符包含比单个图计算更丰富的信息，而欧拉示性数不具备此优势。此外，我们提出了计算顶点与边级滤波下图积持久同调图的算法。通过运行时分析、表达能力和图分类性能的实证研究，验证了理论分析。本工作为通过积滤波构建强大的图持久同调描述符奠定了基础。代码见https://github.com/Aalto-QuML/tda_graph_product。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。