The Pyramid Quantized Weisfeiler-Lehman Graph Representation

Abstract : Graphs are flexible and powerful representations for non-vectorial structured data. Graph kernels have been shown to enable efficient and accurate statistical learning on this important domain, but many graph kernel algorithms have high order polynomial time complexity. Efficient graph kernels rely on a discrete node labeling as a central assumption. However, many real world domains are naturally described by continuous or vector valued node labels. In this article, we propose an efficient graph representation and comparison scheme for large graphs with continuous vector labels, the pyramid quantized Weisfeiler-Lehman graph representation. Our algorithm considers statistics of subtree patterns with discrete labels based on the Weisfeiler-Lehman algorithm and uses a pyramid quantization strategy to determine a logarithmic number of discrete labelings that results in a representation that guarantees a multiplicative error bound on an approximation to the optimal partial matching. As a result, we approximate a graph representation with continuous vector labels as a sequence of graphs with increasingly granular discrete labels. We evaluate our proposed algorithm on two different tasks with real datasets, on a fMRI analysis task and on the generic problem of 3D shape classification. Source code of the implementation can be downloaded from. https://web.imis.athena-innovation.gr/~kgkirtzou/Projects/WLpyramid.html
Type de document :
Article dans une revue
Neurocomputing, Elsevier, 2016, 173, pp.1495-1507. 〈10.1016/j.neucom.2015.09.023〉
Liste complète des métadonnées

Littérature citée [53 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01205717
Contributeur : Matthew Blaschko <>
Soumis le : samedi 26 septembre 2015 - 22:17:48
Dernière modification le : vendredi 6 avril 2018 - 13:32:01
Document(s) archivé(s) le : mardi 29 décembre 2015 - 09:32:54

Fichier

Main.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Katerina Gkirtzou, Matthew Blaschko. The Pyramid Quantized Weisfeiler-Lehman Graph Representation. Neurocomputing, Elsevier, 2016, 173, pp.1495-1507. 〈10.1016/j.neucom.2015.09.023〉. 〈hal-01205717〉

Partager

Métriques

Consultations de la notice

289

Téléchargements de fichiers

347