Copyright notice: The material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

If you want a paper that is not available here, or if you have any problems accessing these documents, e-mail me.

Pyramid Quantized Weisfeiler-Lehman Graph Representation

The Pyramid Quantized Weisfeiler-Lehman Graph Representation (WLpyramid) is an efficient graph representation and comparison scheme for large graphs with continuous vector labels. Our algorithm considers statistics of subtree patterns with discrete labels based on the Weisfeiler-Lehman algorithm. The key advantage of these subtree statistics, which are tree structures constructed recursively from each node in the graph up to a predefined depth h, is their linear complexity to the number of edges in the graph under investigation. Moreover, they make use of an efficient hashing scheme enumerating the relevant dimensions of an exponentially sized feature space. To take advantage of this efficient scheme when working on continuous vector labeled graphs, we use 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 or vector valued labels as a sequence of graphs discrete labels with increasingly granular discrete labels. WLpyramid was evaluated on two different tasks with real datasets, on a fMRI analysis task and on the generic problem of 3D shape classification.

Publications

  • The Pyramid Quantized Weisfeiler-Lehman Graph Representation.
    Gkirtzou K., and Blaschko M.
    Neurocomputing, 2016
    [pdf] [bibtex] [doi]
  • Sparsity regularization and graph-based representation in medical imaging
    Gkirtzou Katerina
    PhD Thesis, Ecole Centrale de Paris, 2013.
    [pdf] [bibtex] [presentation]
  • fMRI Analysis with Sparse Weisfeiler-Lehman Graph Statistics.
    Gkirtzou Katerina, Honorio Jean, Samaras Dimitris, Goldstein Rita and Blaschko B. Matthew
    4th International Workshop on Machine Learning in Medical Imaging (MLMI), 2013.
    [pdf] [bibtex] [doi]

Code

The code is provided under the GNU GPL license. It does not come with any warranty of any kind.