Designing a novel linear-time graph kernel for semantic link network

摘要

Graph is an efficient tool for representing structured data such as proteins, molecular compounds, and socialrnnetworks. Graph kernel is a technique to measure the similarity between graphs. However, existing graphrnkernels still have several limitations: (1) semantics on link is ignored; (2) node is associated with single label;rn(3) most graph kernels require more than cubic time, which is still computationally expensive; and, (4) therernis seldom consideration of handling the graph comparison when the number of node types becomes huge. Inrnthis paper, we utilize semantic link network (SLN) to represent complex structured data with richer semanticrninformation. Topic model is employed for dimension reduction and tagging each node with multiple labels.rnAnd a novel linear-time graph kernel for SLN is designed to calculate the similarity between two SLNs. Thisrnwork remedies the limitations of the conventional graph kernels. The effectiveness and efficiency of thisrnapproach are evaluated by the document classification task on public corpora. Empirical results demonstraternthat the proposed method can achieve better performance than the traditional topicmodel-based classificationrnapproach.