Generalized graphlet kernels for probabilistic inference in sparse graphs. (1st August 2014)

• Record Type: Journal Article
• Authors: LUGO-MARTINEZ, JOSE; RADIVOJAC, PREDRAG
• Is Part Of: Network science. Volume 2:Number 2(2014)
• Page Start: 254
• Page End: 276
• Publication Date: 2014-08-01
• Subjects: graph kernels, -- vertex classification, -- graph edit distance; Social networks -- Research -- Periodicals; System analysis -- Periodicals; System theory -- Periodicals; Computer science -- Periodicals; 003.72
• DOI: 10.1017/nws.2014.14
• Languages: English
• ISSNs: 2050-1242

Abstract

Abstract: Graph kernels for learning and inference on sparse graphs have been widely studied. However, the problem of designing robust kernel functions that can effectively compare graph neighborhoods in the presence of noisy and complex data remains less explored. Here we propose a novel graph-based kernel method referred to as an edit distance graphlet kernel. The method was designed to add flexibility in capturing similarities between local graph neighborhoods as a means of probabilistically annotating vertices in sparse and labeled graphs. We report experiments on nine real-life data sets from molecular biology and social sciences and provide evidence that the new kernels perform favorably compared to established approaches. However, when both performance accuracy and run time are considered, we suggest that edit distance kernels are best suited for inference on graphs derived from protein structures. Finally, we demonstrate that the new approach facilitates simple and principled ways of integrating domain knowledge into classification and point out that our methodology extends beyond classification; e.g. to applications such as kernel-based clustering of graphs or approximate motif finding. Availability:www.sourceforge.net/projects/graphletkernels/