Unfolding Kernel embeddings of graphs: Enhancing class separation through manifold learning

Luca Rossi, Andrea Torsello, Edwin R. Hancock

Research output: Journal article publicationJournal articleAcademic researchpeer-review

13 Citations (Scopus)


In this paper, we investigate the use of manifold learning techniques to enhance the separation properties of standard graph kernels. The idea stems from the observation that when we perform multidimensional scaling on the distance matrices extracted from the kernels, the resulting data tends to be clustered along a curve that wraps around the embedding space, a behavior that suggests that long range distances are not estimated accurately, resulting in an increased curvature of the embedding space. Hence, we propose to use a number of manifold learning techniques to compute a low-dimensional embedding of the graphs in an attempt to unfold the embedding manifold, and increase the class separation. We perform an extensive experimental evaluation on a number of standard graph datasets using the shortest-path (Borgwardt and Kriegel, 2005), graphlet (Shervashidze et al., 2009), random walk (Kashima et al., 2003) and Weisfeiler-Lehman (Shervashidze et al., 2011) kernels. We observe the most significant improvement in the case of the graphlet kernel, which fits with the observation that neglecting the locational information of the substructures leads to a stronger curvature of the embedding manifold. On the other hand, the Weisfeiler-Lehman kernel partially mitigates the locality problem by using the node labels information, and thus does not clearly benefit from the manifold learning. Interestingly, our experiments also show that the unfolding of the space seems to reduce the performance gap between the examined kernels.

Original languageEnglish
Pages (from-to)3357-3370
Number of pages14
JournalPattern Recognition
Issue number11
Publication statusPublished - 1 Nov 2015
Externally publishedYes


  • Graph kernels
  • Kernel learning
  • Kernel unfolding
  • Manifold learning

ASJC Scopus subject areas

  • Software
  • Signal Processing
  • Computer Vision and Pattern Recognition
  • Artificial Intelligence


Dive into the research topics of 'Unfolding Kernel embeddings of graphs: Enhancing class separation through manifold learning'. Together they form a unique fingerprint.

Cite this