On topological descriptors for graph products
Mattie Ji, Amauri H. Souza, Vikas Garg
拓扑描述符越来越多地用于捕获关系数据中的多尺度结构信息。 在这项工作中,我们考虑了图形(框)产品上的各种过滤,以及他们对拓扑描述符(Euler特征(EC)和持久性同源性(PH)的输出的影响。 特别是,我们建立了EC对一般基于颜色的过滤的表达力的完整表征。 我们还表明,(虚拟)图形产品的PH描述符严格包含的信息比单个图形上的计算更多,而EC没有。 此外,我们还提供算法来计算图形产品上顶点和边缘级过滤产品的PH图。 我们还通过关于运行时分析、表现力和图形分类性能的实证调查来证实我们的理论分析。 总的来说,这项工作为通过产品过滤的强大图形持久描述符铺平了道路。 代码可在https://github.com/Aalto-QuML/tda_graph_product上查阅。
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) gr...