A Truss-Based Framework for Graph Similarity Computation

Yanwei Zheng, Zichun Zhang, Qi Luo, Zhenzhen Xie, Dongxiao Yu

OAI: oai:igi-global.com:322087 • DOI: 10.4018/JDM.322087

The study of graph kernels has been an important area of graph analysis, which is widely used to solve the similarity problems between graphs. Most of the existing graph kernels consider either local or global properties of the graph, and there are few studies on multiscale graph kernels. In this article, the authors propose a framework for graph kernels based on truss decomposition, which allows multiple graph kernels and even any graph comparison algorithms to compare graphs at different scales. The authors utilize this framework to derive variants of five graph kernels and compare them with the corresponding basic graph kernels on graph classification tasks. Experiments on a large number of benchmark datasets demonstrate the effectiveness and efficiency of the proposed framework.

Databases Computer Science and Information Technology Data Mining and Databases