The Weisfeiler-Lehman Distance: Reinterpretation and Connection with GNNs
In this paper, we present a novel interpretation of the so-called Weisfeiler-Lehman (WL) distance, introduced by Chen et al. (2022), using concepts from stochastic processes. The WL distance aims at comparing graphs with node features, has the same discriminative power as the classic Weisfeiler-Lehman graph isomorphism test and has deep connections to the Gromov-Wasserstein distance. This new interpretation connects the WL distance to the literature on distances for stochastic processes, which also makes the interpretation of the distance more accessible and intuitive. We further explore the connections between the WL distance and certain Message Passing Neural Networks, and discuss the implications of the WL distance for understanding the Lipschitz property and the universal approximation results for these networks.
Code (0)
등록된 구현이 없습니다.
Methods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
A New Perspective on "How Graph Neural Networks Go Beyond Weisfeiler-Lehman?"
We propose a new perspective on designing powerful Graph Neural Networks (GNNs). In a nutshell, this enables a general solution to inject structural properties of graphs into a message-passing aggregation scheme of GNNs.…
Graph LearningTwo-Dimensional Weisfeiler-Lehman Graph Neural Networks for Link Prediction
Link prediction is one important application of graph neural networks (GNNs). Most existing GNNs for link prediction are based on one-dimensional Weisfeiler-Lehman (1-WL) test. 1-WL-GNNs first compute node representation…
Link PredictionVocal Bursts Valence PredictionWeisfeiler-Lehman meets Gromov-Wasserstein
The Weisfeiler-Lehman (WL) test is a classical procedure for graph isomorphism testing. The WL test has also been widely used both for designing graph kernels and for analyzing graph neural networks. In this paper, we pr…
Isomorphism TestingTwin Weisfeiler-Lehman: High Expressive GNNs for Graph Classification
The expressive power of message passing GNNs is upper-bounded by Weisfeiler-Lehman (WL) test. To achieve high expressive GNNs beyond WL test, we propose a novel graph isomorphism test method, namely Twin-WL, which simult…
ClassificationGraph ClassificationVocal Bursts Intensity PredictionA Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Tests
Recently, subgraph GNNs have emerged as an important direction for developing expressive graph neural networks (GNNs). While numerous architectures have been proposed, so far there is still a limited understanding of how…
Subgraph Counting - 3 StarSubgraph Counting - C4Subgraph Counting - C5Subgraph Counting - C6+2