Extended persistence is a technique from topological data analysis to obtain global multiscale topological information from a graph. This includes information about connected components and cycles that are captured by the so-called persistence barcodes. We introduce extended persistence into a supervised learning framework for graph classification. Global topological information, in the form of a barcode with four different types of bars and their explicit cycle representatives, is combined into the model by the readout function which is computed by extended persistence. The entire model is end-to-end differentiable. We use a link-cut tree data structure and parallelism to lower the complexity of computing extended persistence, obtaining a speedup of more than 60x over the state-of-the-art for extended persistence computation. This makes extended persistence feasible for machine learning. We show that, under certain conditions, extended persistence surpasses both the WL[1] graph isomorphism test and 0-dimensional barcodes in terms of expressivity because it adds more global (topological) information. In particular, arbitrarily long cycles can be represented, which is difficult for finite receptive field message passing graph neural networks. Furthermore, we show the effectiveness of our method on real world datasets compared to many existing recent graph representation learning methods.

使用扩展持久性技术将全局拓扑信息融入图分类的监督学习框架中，通过可导的读出函数计算扩展持久性获取全局拓扑信息；使用链剪树数据结构和并行计算降低计算复杂度，使扩展持久性在机器学习中具备可行性。研究结果表明，在特定条件下，扩展持久性在表达能力上超越了WL图同构测试和0维条形码，因为它提供更多的全局（拓扑）信息，并能表示任意长的循环。此外，通过与现有的图表示学习方法进行比较，验证了我们方法在真实数据集上的有效性。

GEFL：图分类的扩展过滤学习