Weisfeiler and Leman go Hyperbolic: Learning Distance Preserving Node Representations

Giannis Nikolentzos, Michail Chatzianastasis, Michalis Vazirgiannis
Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, PMLR 206:1037-1054, 2023.

Abstract

In recent years, graph neural networks (GNNs) have emerged as a promising tool for solving machine learning problems on graphs. Most GNNs are members of the family of message passing neural networks (MPNNs). There is a close connection between these models and the Weisfeiler-Leman (WL) test of isomorphism, an algorithm that can successfully test isomorphism for a broad class of graphs. Recently, much research has focused on measuring the expressive power of GNNs. For instance, it has been shown that standard MPNNs are at most as powerful as WL in terms of distinguishing non-isomorphic graphs. However, these studies have largely ignored the distances between the representations of the nodes/graphs which are of paramount importance for learning tasks. In this paper, we define a distance function between nodes which is based on the hierarchy produced by the WL algorithm, and propose a model that learns representations which preserve those distances between nodes. Since the emerging hierarchy corresponds to a tree, to learn these representations, we capitalize on recent advances in the field of hyperbolic neural networks. We empirically evaluate the proposed model on standard graph and node classification datasets where it achieves competitive performance with state-of-the-art models.

Cite this Paper

BibTeX
@InProceedings{pmlr-v206-nikolentzos23a, title = {Weisfeiler and Leman go Hyperbolic: Learning Distance Preserving Node Representations}, author = {Nikolentzos, Giannis and Chatzianastasis, Michail and Vazirgiannis, Michalis}, booktitle = {Proceedings of The 26th International Conference on Artificial Intelligence and Statistics}, pages = {1037--1054}, year = {2023}, editor = {Ruiz, Francisco and Dy, Jennifer and van de Meent, Jan-Willem}, volume = {206}, series = {Proceedings of Machine Learning Research}, month = {25--27 Apr}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v206/nikolentzos23a/nikolentzos23a.pdf}, url = {https://proceedings.mlr.press/v206/nikolentzos23a.html}, abstract = {In recent years, graph neural networks (GNNs) have emerged as a promising tool for solving machine learning problems on graphs. Most GNNs are members of the family of message passing neural networks (MPNNs). There is a close connection between these models and the Weisfeiler-Leman (WL) test of isomorphism, an algorithm that can successfully test isomorphism for a broad class of graphs. Recently, much research has focused on measuring the expressive power of GNNs. For instance, it has been shown that standard MPNNs are at most as powerful as WL in terms of distinguishing non-isomorphic graphs. However, these studies have largely ignored the distances between the representations of the nodes/graphs which are of paramount importance for learning tasks. In this paper, we define a distance function between nodes which is based on the hierarchy produced by the WL algorithm, and propose a model that learns representations which preserve those distances between nodes. Since the emerging hierarchy corresponds to a tree, to learn these representations, we capitalize on recent advances in the field of hyperbolic neural networks. We empirically evaluate the proposed model on standard graph and node classification datasets where it achieves competitive performance with state-of-the-art models.} }
Endnote
%0 Conference Paper %T Weisfeiler and Leman go Hyperbolic: Learning Distance Preserving Node Representations %A Giannis Nikolentzos %A Michail Chatzianastasis %A Michalis Vazirgiannis %B Proceedings of The 26th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2023 %E Francisco Ruiz %E Jennifer Dy %E Jan-Willem van de Meent %F pmlr-v206-nikolentzos23a %I PMLR %P 1037--1054 %U https://proceedings.mlr.press/v206/nikolentzos23a.html %V 206 %X In recent years, graph neural networks (GNNs) have emerged as a promising tool for solving machine learning problems on graphs. Most GNNs are members of the family of message passing neural networks (MPNNs). There is a close connection between these models and the Weisfeiler-Leman (WL) test of isomorphism, an algorithm that can successfully test isomorphism for a broad class of graphs. Recently, much research has focused on measuring the expressive power of GNNs. For instance, it has been shown that standard MPNNs are at most as powerful as WL in terms of distinguishing non-isomorphic graphs. However, these studies have largely ignored the distances between the representations of the nodes/graphs which are of paramount importance for learning tasks. In this paper, we define a distance function between nodes which is based on the hierarchy produced by the WL algorithm, and propose a model that learns representations which preserve those distances between nodes. Since the emerging hierarchy corresponds to a tree, to learn these representations, we capitalize on recent advances in the field of hyperbolic neural networks. We empirically evaluate the proposed model on standard graph and node classification datasets where it achieves competitive performance with state-of-the-art models.
APA
Nikolentzos, G., Chatzianastasis, M. & Vazirgiannis, M.. (2023). Weisfeiler and Leman go Hyperbolic: Learning Distance Preserving Node Representations. Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 206:1037-1054 Available from https://proceedings.mlr.press/v206/nikolentzos23a.html.

Related Material