PaperlayerView exact revision on arXiv

Source-linked AI summary

Wasserstein Weisfeiler-Lehman Graph Kernels

Matteo Togninalli, Elisabetta Ghisu, Felipe Llinares-López, Bastian Rieck, Karsten Borgwardt

arXiv:1906.01277v2cs.LGq-bio.MNstat.ML

TL;DR

Existing graph kernels may lose distributional information through simple substructure aggregation and have limited support for continuous attributes. WWL combines WL-inspired node embeddings with Wasserstein distances, outperforming state-of-the-art methods for continuous attributes while matching them for categorical graphs. Its scope is constrained by computational cost, unresolved mixed categorical-continuous handling, and the fact that Wasserstein-derived kernels are not generally guaranteed positive definite.

  • Problem

    Simple aggregation in many R-Convolution graph kernels can discard substructure-distribution information, while only limited approaches support continuously attributed graphs.

  • Method

    WWL combines WL-inspired node embeddings with graph Wasserstein distances to compare node-feature distributions, supporting categorical and continuous attributes with weighted edges.

  • Results

    WWL outperforms state-of-the-art graph kernels for continuous node attributes and matches the state of the art in the categorical setting.

  • Takeaways & Limitations

    Wasserstein-based graph kernels provide a graph-classification approach that captures node-feature distributions beyond simple aggregation.

  • Takeaways & Limitations

    Wasserstein-derived kernels are not necessarily positive definite in general, while runtime and joint categorical-continuous handling remain constrained.

Abstract

from arXiv · show

Most graph kernels are an instance of the class of $\mathcal{R}$-Convolution kernels, which measure the similarity of objects by comparing their substructures. Despite their empirical success, most graph kernels use a naive aggregation of the final set of substructures, usually a sum or average, thereby potentially discarding valuable information about the distribution of individual components. Furthermore, only a limited instance of these approaches can be extended to continuously attributed graphs. We propose a novel method that relies on the Wasserstein distance between the node feature vector distributions of two graphs, which allows to find subtler differences in data sets by considering graphs as high-dimensional objects, rather than simple means. We further propose a Weisfeiler-Lehman inspired embedding scheme for graphs with continuous node attributes and weighted edges, enhance it with the computed Wasserstein distance, and thus improve the state-of-the-art prediction performance on several graph classification tasks.

1 Introduction

Existing graph kernels often aggregate substructure similarities simply, potentially losing distributional information and limiting continuous-attribute handling. The paper proposes Wasserstein-based graph kernels with a WL-inspired embedding scheme and reports improved classification performance.

  • R-Convolution graph kernels decompose graphs into substructures, then aggregate their similarities, often with simple operations such as sums or averages.
  • Simple aggregation can discard valuable information about individual substructure distributions, while continuous node attributes remain insufficiently supported.
  • The proposed graph Wasserstein distance compares node-feature representations through optimal transport rather than relying only on aggregated component summaries.
  • The method introduces a Weisfeiler–Lehman-inspired embedding scheme for categorically labelled and continuously attributed graphs, including weighted edges.
  • The resulting kernels outperform state-of-the-art graph kernels on traditional graph-classification benchmarks with continuous attributes.

2 Background: graph kernels and Wasserstein distance

Graph kernels compare substructures under the R-Convolution framework, whereas Wasserstein distance compares probability distributions through minimum-cost transport. The paper adapts this distance to finite sets of node embeddings.

  • A positive definite kernel represents a dot product in a high-dimensional feature space and can therefore support dot-product-based learning algorithms.
  • Graphs are undirected structures with nodes, edges, optional categorical labels, continuous node attributes, and potentially weighted edges.
  • R-Convolution graph kernels decompose graphs into substructures and combine pairwise substructure similarities, but aggregation can ignore their distribution.
  • The Lp-Wasserstein distance compares probability distributions on a metric space using transportation plans with specified marginals.
  • The paper focuses on the L1-Wasserstein distance, which can be interpreted through the minimum-cost transport of probability mass between distributions.
  • For finite node-embedding sets, the Wasserstein distance becomes a sum represented with a distance matrix and a transport matrix.

3 Wasserstein distance on graphs

The method embeds each graph’s nodes, computes pairwise Wasserstein distances between embedding distributions, and converts those distances into similarities for learning. WL-style refinement is extended to continuous attributes and weighted edges.

  • 3 Wasserstein distance on graphs: The pipeline transforms each graph into node embeddings, measures Wasserstein distances between graph pairs, and computes a similarity matrix for learning.
  • 3 Wasserstein distance on graphs: The Graph Wasserstein Distance is defined from an embedding scheme and a ground distance between node-feature vectors.
  • 3.1 Generating node embeddings: The embedding scheme adapts Weisfeiler–Lehman propagation from categorical labels to continuously attributed graphs with weighted edges.
  • 3.1 Generating node embeddings: WL refinement updates node representations by combining current features with neighborhood information, using weighted averages for continuous attributes.
  • 3.1 Generating node embeddings: Further extensions for high-dimensional edge attributes are left for future work, although the weighted-edge scheme applies broadly without hashing.
  • 3.2 Computing the Wasserstein distance: Categorical embeddings use normalized Hamming distance, whereas continuous embeddings use Euclidean distance before Wasserstein computation.
  • 3.1 Generating node embeddings: The method leaves joint treatment of categorical labels and continuous attributes for future work because an appropriate mixed-data distance is unresolved.
  • 3.2 Computing the Wasserstein distance: The naive Wasserstein computation has complexity O(n^3log(n)); Sinkhorn regularization can reduce computational burden toward near-linear time while preserving accuracy.

4 From Wasserstein distance to kernels

The paper constructs the WWL kernel by applying a Wasserstein distance to graph embeddings, using a Laplacian transformation to support learning. Categorical WWL is theoretically positive definite, whereas definiteness remains unresolved for continuous attributes.

  • Kernel construction: The proposed graph kernel derives similarity from the Wasserstein distance between graph embeddings.The procedure computes node embeddings, pairwise ground distances, an optimal transport distance, and an exponential kernel value.
  • Kernel construction: WWL is a Laplacian kernel designed for both categorical and continuous node labels.The paper distinguishes categorical WWL from continuous WWL according to the graph embedding scheme used.
  • Definiteness: The general Wasserstein distance does not necessarily yield a positive definite kernel because its metric structure depends on the chosen ground distance.This limits direct application of classical positive-definite kernel constructions.
  • Definiteness: The categorical WWL kernel is positive definite for all λ > 0.
  • Definiteness: Definiteness of the continuous WWL kernel remains an open problem, so the paper uses Kreĭn-space learning methods for that setting.These methods are designed to work with indefinite kernels.
  • Evaluation context: Table 2 compares classification accuracies for graphs with continuous node and/or edge attributes across HGK, GraphHopper, and WWL.

5 Experimental evaluation

The evaluation compares WWL with established graph kernels and baselines using shared data splits and repeated cross-validation. WWL is competitive on categorical data and achieves the strongest reported overall performance on continuous attributed graphs.

  • Continuous attributes: The authors report that WWL outperforms all state-of-the-art graph kernels for attributed graphs.They describe this result as establishing a new state of the art for kernel graph classification on attributed graphs.
  • Experimental setup: The experiments use real-world datasets spanning categorical labels, continuous attributes, and continuous edge weights.The datasets include MUTAG, PTC-MR, NCI1, D&D, ENZYMES, PROTEINS, IMDB-B, BZR, COX2, BZR-MD, and COX2-MD.
  • Experimental setup: WWL is compared with WL, WL-OA, vertex and edge histograms, HGK variants, GraphHopper, VH-C, and an RBF-WL baseline.RBF-WL replaces the Wasserstein distance with an RBF-based aggregation of node-embedding similarities.
  • Experimental setup: The evaluation uses SVM or KSVM classification, 10-fold cross-validation, ten repetitions, and identical splits for every method.Parameters are selected using the training set only, and average accuracy is reported.
  • Categorical labels: On categorical datasets, WWL is comparable to WL-OA and improves over classical WL.WWL largely improves over WL-OA on PTC-MR and is slightly better on D&D, while WL-OA is better on NCI1 and PROTEINS.
  • Continuous attributes: WWL significantly outperforms other methods on 4 of 7 continuous datasets, is better on one, and is tied on two.Its average rank is first, ahead of HGK-WL, RBF-WL, HGK-SP, and VH-C.

6 Conclusion

The paper introduces Wasserstein Weisfeiler–Lehman graph kernels, which outperform state-of-the-art methods for continuous attributes while matching them in the categorical setting.

  • WWL graph kernels form a new family of graph kernels.
  • Significance testing uses 2-sample t-tests with a 0.05 threshold and Bonferroni correction within each data set.
  • The method outperforms state-of-the-art graph kernels on traditional graph classification benchmarks with continuous attributes.
  • WWL graph kernels match the state of the art for categorical node attributes.

A.1 Extended considerations on WWL definiteness

The definiteness analysis relates Wasserstein-based graph kernels to conditional definiteness and Hilbert-space geometry, while emphasizing that general Wasserstein definiteness remains unresolved.

  • Whether optimal-transport distances generally yield positive definite kernels remains an open research question.
  • The Wasserstein distance is not generally isometric to an L2-norm because its induced metric space depends strongly on the ground distance.
  • The geodesic Laplacian kernel is positive definite when its geodesic distance is conditionally negative definite.
  • The discrete ground metric makes the Wasserstein distance conditionally negative definite.
  • The analysis proves positive definiteness for categorical WWL kernels under particular ground-distance conditions.

A.1.1 The case of categorical embeddings

For categorical WL embeddings, shared label dictionaries support shared transport solutions across iterations, enabling a proof that the WWL kernel is positive definite.

  • A shared dictionary across graphs makes optimal-transport solutions shared across Weisfeiler–Lehman iterations.
  • An optimal transport plan under Hamming distances at iteration H is also optimal for the corresponding discrete distances at iteration H.
  • An optimal transport plan at iteration H remains optimal for Hamming distances at iteration H−1.
  • The categorical WL Wasserstein distance is postulated to be conditionally negative definite.
  • The WWL kernel is positive definite for all λ > 0.

A.1.2 The case of continuous embeddings

Continuous embeddings are harder to analyze: the induced Wasserstein space is not positively curvature-bounded in general, and positive definiteness remains conjectural despite empirical support after feature standardization.

  • The continuous-case WWL kernel lacks a formal positive-definiteness proof, unlike the categorical case.
  • The geodesic Laplacian kernel is used instead of the Gaussian kernel because it requires only conditional negative definiteness rather than flatness.
  • The graph-embedding space is not CAT(k) for any k > 0 because arbitrarily small examples can have multiple optimal transport geodesics.
  • For all considered data sets, standardized input features yielded conditionally negative definite GWD matrices.
  • The paper conjectures that the continuous embedding space is an Alexandrov space with curvature bounded below by zero.
  • The authors report empirical evidence that proper normalization can make the GWD conditionally negative definite.

A.2 Proof of Lemma 1

The proof shows that an optimal transport plan for the WL Hamming distance remains optimal for the corresponding discrete metric distance matrix. This follows from the refinement of labels across WL iterations and the resulting transport-cost structure.

  • Optimality argument: If a supposedly optimal plan were not optimal for the discrete metric matrix, rearranging its transport mass would produce a lower-cost plan, contradicting optimality.The contradiction establishes optimality for the discrete metric distance matrix.
  • Distance matrices: The Hamming distance between WL node embeddings defines the matrix used to compare nodes across two graphs.Its ij-th entry compares the embeddings of node i in one graph and node j in the other at iteration h.
  • WL refinement: WL refinement preserves distinctions: labels different at iteration h remain different at iteration h + 1.This monotonicity underlies the identities used in the proof.
  • Conclusion: Therefore, the transport plan P h is also optimal for the discrete distance matrix DH disc.The conclusion follows after showing that a better plan would contradict the assumed optimality of P h.

A.3 Proof of Lemma 2

The supplied passages combine the Lemma 2 proof with experimental and runtime evidence. They describe monotone WL distance refinement, benchmark limitations, computational trade-offs, and robustness and accuracy checks.

  • A.3 Proof of Lemma 2: WL Hamming distances increase stepwise with iteration h while preserving their ordering, apart from entries changing from 0 to 1.This monotonicity supports carrying an optimal transport plan through successive WL iterations.
  • A.3 Proof of Lemma 2: An optimal solution at iteration H is also optimal for the discrete distance matrices at every earlier iteration h = 0, . . . , H −1.The proof then rewrites the resulting expression as a sum of optimal transport problems.
  • A.3 Proof of Lemma 2: The final sum is conditionally negative definite because it consists of one-dimensional optimal transport problems with the discrete metric.The component problems are stated to be conditionally negative functions, and their sum inherits conditional negative definiteness.
  • A.5 Data sets and additional results: Synthetic-data results were excluded from the main manuscript because methods varied substantially and small feature preprocessing changes altered performance by up to 15%.The authors also report that continuous attributes were not informative on SYNTHETIC-NEW relative to categorical degree labels.
  • A.7 Runtime comparison: WWL runtime is empirically competitive, with a kernel matrix computed in a median time of 40 s depending on graph size and count.WL and WL-OA scale linearly with node count, while GH was shown to scale quadratically and HGK is considerably slower in the reported setup.
  • A.7 Runtime comparison: The Wasserstein distance computation has naive complexity O(n3log(n)), while Sinkhorn approximations can reduce computational burden toward near-linear time.The speedups are described as especially useful for graphs with thousands of nodes.
  • A.7 Runtime comparison: 72.08 ± 0.93 accuracy was obtained on ENZYMES after cross-validating the Sinkhorn regularisation parameter γ, remaining above the current state of the art.The most frequently selected γ values were 0.3, 0.5, and 1.
  • A.8 Performance on isomorphic synthetic graphs: WWL is reported to be more robust against increasing edge-removal noise on the tested Erdős–Rényi graphs.The experiment compares relative distances involving a graph, its permuted and perturbed variant, and an independent graph.
Loading 1906.01277v2…