Salim Asif, Shiju S S, Sumitra S
IEEE Trans Pattern Anal Mach Intell. 2023 Jan;45(1):828-840. doi: 10.1109/TPAMI.2022.3143806. Epub 2022 Dec 5.
We describe the design of a reproducing kernel suitable for attributed graphs, in which the similarity between two graphs is defined based on the neighborhood information of the graph nodes with the aid of a product graph formulation. Attributed graphs are those which contain a piece of vector information and a discrete label over the nodes and edges. We represent the proposed kernel as the weighted sum of two other kernels of which one is an R-convolution kernel that processes the attribute information of the graph and the other is an optimal assignment kernel that processes label information. They are formulated in such a way that the edges processed as part of the kernel computation have the same neighborhood properties and hence the kernel proposed makes a well-defined correspondence between regions processed in graphs. These concepts are also extended to the case of the shortest paths. We identified the state-of-the-art kernels that can be mapped to such a neighborhood preserving framework. We found that the kernel value of the argument graphs in each iteration of the Weisfeiler-Lehman color refinement algorithm can be obtained recursively from the product graph formulated in our method. By incorporating the proposed kernel on support vector machines we analyzed the real-world data sets and it showed superior performance in comparison with that of the other state-of-the-art graph kernels.
我们描述了一种适用于属性图的再生核的设计，其中两个图之间的相似性是借助积图公式，基于图节点的邻域信息来定义的。属性图是那些在节点和边上包含向量信息和离散标签的图。我们将所提出的核表示为另外两个核的加权和，其中一个是处理图的属性信息的R - 卷积核，另一个是处理标签信息的最优分配核。它们的构建方式使得作为核计算一部分处理的边具有相同的邻域属性，因此所提出的核在图中处理的区域之间建立了明确的对应关系。这些概念也扩展到了最短路径的情况。我们确定了可以映射到这种邻域保持框架的最先进的核。我们发现，在魏斯费勒 - 莱曼颜色细化算法的每次迭代中，论证图的核值可以从我们方法中制定的积图递归获得。通过将所提出的核纳入支持向量机，我们分析了真实世界的数据集，结果表明与其他最先进的图核相比，它具有卓越的性能。
