Martino Alessio, Rizzi Antonello
Department of Information Engineering, Electronics and Telecommunications, University of Rome "La Sapienza", Via Eudossiana 18, 00184 Rome, Italy.
Entropy (Basel). 2020 Oct 14;22(10):1155. doi: 10.3390/e22101155.
Graph kernels are one of the mainstream approaches when dealing with measuring similarity between graphs, especially for pattern recognition and machine learning tasks. In turn, graphs gained a lot of attention due to their modeling capabilities for several real-world phenomena ranging from bioinformatics to social network analysis. However, the attention has been recently moved towards hypergraphs, generalization of plain graphs where multi-way relations (other than pairwise relations) can be considered. In this paper, four (hyper)graph kernels are proposed and their efficiency and effectiveness are compared in a twofold fashion. First, by inferring the simplicial complexes on the top of underlying graphs and by performing a comparison among 18 benchmark datasets against state-of-the-art approaches; second, by facing a real-world case study (i.e., metabolic pathways classification) where input data are natively represented by hypergraphs. With this work, we aim at fostering the extension of graph kernels towards hypergraphs and, more in general, bridging the gap between structural pattern recognition and the domain of hypergraphs.
图核是处理图之间相似性度量时的主流方法之一，特别是在模式识别和机器学习任务中。反过来，由于图对从生物信息学到社交网络分析等多种现实世界现象的建模能力，它们受到了广泛关注。然而，最近人们的注意力已经转向超图，超图是普通图的推广，其中可以考虑多向关系（而非成对关系）。本文提出了四种（超）图核，并以两种方式比较了它们的效率和有效性。第一，通过在基础图之上推断单纯复形，并针对18个基准数据集与现有方法进行比较；第二，通过面对一个实际案例研究（即代谢途径分类），其中输入数据天然地由超图表示。通过这项工作，我们旨在促进图核向超图的扩展，更广泛地说，弥合结构模式识别与超图领域之间的差距。
