The Weisfeiler-Lehman Distance: Reinterpretation and Connection with GNNs

Samantha Chen, Sunhyuk Lim, Facundo Memoli, Zhengchao Wan, Yusu Wang
Proceedings of 2nd Annual Workshop on Topology, Algebra, and Geometry in Machine Learning (TAG-ML), PMLR 221:404-425, 2023.

Abstract

In this paper, we present a novel interpretation of the Weisfeiler-Lehman (WL) distance introduced by \cite{chen2022weisfeilerlehman} using concepts from stochastic processes. The WL distance aims compares 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. Our 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v221-chen23a, title = {The Weisfeiler-Lehman Distance: Reinterpretation and Connection with GNNs}, author = {Chen, Samantha and Lim, Sunhyuk and Memoli, Facundo and Wan, Zhengchao and Wang, Yusu}, booktitle = {Proceedings of 2nd Annual Workshop on Topology, Algebra, and Geometry in Machine Learning (TAG-ML)}, pages = {404--425}, year = {2023}, editor = {Doster, Timothy and Emerson, Tegan and Kvinge, Henry and Miolane, Nina and Papillon, Mathilde and Rieck, Bastian and Sanborn, Sophia}, volume = {221}, series = {Proceedings of Machine Learning Research}, month = {28 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v221/chen23a/chen23a.pdf}, url = {https://proceedings.mlr.press/v221/chen23a.html}, abstract = {In this paper, we present a novel interpretation of the Weisfeiler-Lehman (WL) distance introduced by \cite{chen2022weisfeilerlehman} using concepts from stochastic processes. The WL distance aims compares 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. Our 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.} }
Endnote
%0 Conference Paper %T The Weisfeiler-Lehman Distance: Reinterpretation and Connection with GNNs %A Samantha Chen %A Sunhyuk Lim %A Facundo Memoli %A Zhengchao Wan %A Yusu Wang %B Proceedings of 2nd Annual Workshop on Topology, Algebra, and Geometry in Machine Learning (TAG-ML) %C Proceedings of Machine Learning Research %D 2023 %E Timothy Doster %E Tegan Emerson %E Henry Kvinge %E Nina Miolane %E Mathilde Papillon %E Bastian Rieck %E Sophia Sanborn %F pmlr-v221-chen23a %I PMLR %P 404--425 %U https://proceedings.mlr.press/v221/chen23a.html %V 221 %X In this paper, we present a novel interpretation of the Weisfeiler-Lehman (WL) distance introduced by \cite{chen2022weisfeilerlehman} using concepts from stochastic processes. The WL distance aims compares 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. Our 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.
APA
Chen, S., Lim, S., Memoli, F., Wan, Z. & Wang, Y.. (2023). The Weisfeiler-Lehman Distance: Reinterpretation and Connection with GNNs. Proceedings of 2nd Annual Workshop on Topology, Algebra, and Geometry in Machine Learning (TAG-ML), in Proceedings of Machine Learning Research 221:404-425 Available from https://proceedings.mlr.press/v221/chen23a.html.

Related Material