Glocalized Weisfeiler-Lehman Graph Kernels: Global-Local Feature Maps of Graphs

By Christopher Morris, Kristian Kersting, Petra Mutzel. 2017

92 citations recorded by the source corpus.

Most state-of-the-art graph kernels only take local graph properties into account, i.e., the kernel is computed with regard to properties of the neighborhood of vertices or other small substructures. On the other hand, kernels that do take global graph properties into account may not scale well to large graph databases. Here we propose to start exploring the spacebetween local and global graph kernels, so called glocalized graph kernels, striking the balance between both worlds. Specifically, we introduce a novel graph kernel based on the k-dimensional Weisfeiler-Lehmanalgorithm. Unfortunately, the k-dimensional Weisfeiler-Lehman algorithm scales exponentially in k. Consequently, we devise a stochastic version of the kernel with provable approximation guarantees using conditional Rademacher averages. On bounded-degree graphs, it can even be computed in constant time. We support our theoretical results with experiments on several graph classification benchmarks, showing that our kernels often outperform the state-of-the-art in terms of classification accuracies.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

Citations in the corpus

Provably Powerful Graph Networks (2019, methodology): “Assuming a graph with n nodes, dense edge data and a constant feature depth, the layer proposed in Morris et al. (2018) has O(n(3)) space complexity (number of subsets) and O(n(4)) time complexity (O(n(3)) subsets with O(n) neighbors each). Our layer (block), however, has O(n(2)) space complexity as”
Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks (2018, methodology): “Prominent examples of this trend include kernels based on graphlet counting (Shervashidze et al. 2009), and, most notably, the Weisfeiler-Lehman subtree kernel (Shervashidze et al. 2011) as well as its higher-order variants (Morris, Kersting, and Mutzel 2017).”
Towards a practical k-dimensional Weisfeiler-Leman algorithm (2019, methodology): “Possible applications include classification of molecules or social networks [24, 6, 21, 23].”
Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings (2019, methodology): “Let ( G, l ) be a labeled graph, following (Morris et al., 2019), we assume an initial node coloring and G [ w ] match.”
A survey on graph kernels (2019, methodology): “Morris et al. (2017) introduced a graph kernel based on higher dimensional variants of the Weisfeiler-Lehman algorithm.”
TUDataset: A collection of benchmark datasets for learning with graphs (2020, background): “, 2019), as well as the Weisfeiler-Lehman subtree kernel (Shervashidze et al., 2011; Morris et al., 2017).”