On topological descriptors for graph products
Mattie Ji, Amauri Souza, Vikas Garg
Topological descriptors have been increasingly used for capturing multiscale structural information in relational data. In this work, we consider various filtrations on (Cartesian) graph products and the effect on their outputs on the topological descriptors - the Euler characteristics (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 while 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. Overall, this work paves way for powerful graph persistent descriptors via graph product filtrations.