Unfolding kernel embeddings of graphs:enhancing class separation through manifold learning

Rossi, Luca, Torsello, Andrea and Hancock, Edwin R. (2015). Unfolding kernel embeddings of graphs:enhancing class separation through manifold learning. Pattern Recognition, 48 (11), pp. 3357-3370.


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.

Publication DOI: https://doi.org/10.1016/j.patcog.2015.03.018
Divisions: Engineering & Applied Sciences
Engineering & Applied Sciences > Systems analytics research institute (SARI)
Additional Information: © 2015, Elsevier. Licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International http://creativecommons.org/licenses/by-nc-nd/4.0/
Uncontrolled Keywords: graph kernels,kernel learning,kernel unfolding,manifold learning,Software,Artificial Intelligence,Computer Vision and Pattern Recognition,Signal Processing
Full Text Link:
Related URLs: http://www.scop ... tnerID=8YFLogxK (Scopus URL)
Published Date: 2015-11
Authors: Rossi, Luca ( 0000-0002-6116-9761)
Torsello, Andrea
Hancock, Edwin R.

Export / Share Citation


Additional statistics for this record