Designing a novel linear‐time graph kernel for semantic link network. (20th May 2015)

• Record Type: Journal Article
• Authors: Peng, Li; Zhang, Zhiying; Huang, Qiaoli; Huang, Zhixing; Zhuge, Hai; Orgun, Mehmet A.; Orgun, Atilla Elçi; Pieprzyk, Josef; Chefranov, Alexander; Shankaran, Rajan; Wang, Huaxiong; Zhuge, Hai
• Is Part Of: Concurrency and computation. Volume 27:Number 15(2015:Oct.)
• Page Start: 4039
• Page End: 4052
• Publication Date: 2015-05-20
• Subjects: Parallel processing (Electronic computers) -- Periodicals; Parallel computers -- Periodicals; 004.35
• DOI: 10.1002/cpe.3541
• Languages: English
• ISSNs: 1532-0626

Abstract

<abstract abstract-type="main" id="cpe3541-abs-0001"> <title>Summary</title> <p id="cpe3541-para-0001">Graph is an efficient tool for representing structured data such as proteins, molecular compounds, and social networks. Graph kernel is a technique to measure the similarity between graphs. However, existing graph kernels still have several limitations: (1) semantics on link is ignored; (2) node is associated with single label; (3) most graph kernels require more than cubic time, which is still computationally expensive; and, (4) there is seldom consideration of handling the graph comparison when the number of node types becomes huge. In this paper, we utilize semantic link network (SLN) to represent complex structured data with richer semantic information. Topic model is employed for dimension reduction and tagging each node with multiple labels. And a novel linear‐time graph kernel for SLN is designed to calculate the similarity between two SLNs. This work remedies the limitations of the conventional graph kernels. The effectiveness and efficiency of this approach are evaluated by the document classification task on public corpora. Empirical results demonstrate that the proposed method can achieve better performance than the traditional topic model‐based classification approach. Copyright © 2015 John Wiley &amp; Sons, Ltd.</p> </abstract>