A Simple and Expressive Graph Neural Network Based Method for Structural Link Representation

Veronica Lachi, Francesco Ferrini, Antonio Longa, Bruno Lepri, Andrea Passerini
Proceedings of the Geometry-grounded Representation Learning and Generative Modeling Workshop (GRaM), PMLR 251:187-201, 2024.

Abstract

Graph Neural Networks (GNNs) have achieved state-of-the-art results in tasks like node classification, link prediction, and graph classification. While much research has focused on their ability to distinguish graphs, fewer studies have addressed their capacity to differentiate links, a complex and less explored area. This paper introduces SLRGNN, a novel, theoretically grounded GNN-based method for link prediction. SLRGNN ensures that link representations are distinct if and only if the links have different structural roles within the graph. Our approach transforms the link prediction problem into a node classification problem on the corresponding line graph, enhancing expressiveness without sacrificing efficiency. Unlike existing methods, SLRGNN computes link probabilities in a single inference step, avoiding the need for individual subgraph constructions. We provide a formal proof of our method’s expressiveness and validate its superior performance through experiments on real-world datasets. The code is publicly available1

Cite this Paper

BibTeX
@InProceedings{pmlr-v251-lachi24a, title = {A Simple and Expressive Graph Neural Network Based Method for Structural Link Representation}, author = {Lachi, Veronica and Ferrini, Francesco and Longa, Antonio and Lepri, Bruno and Passerini, Andrea}, booktitle = {Proceedings of the Geometry-grounded Representation Learning and Generative Modeling Workshop (GRaM)}, pages = {187--201}, year = {2024}, editor = {Vadgama, Sharvaree and Bekkers, Erik and Pouplin, Alison and Kaba, Sekou-Oumar and Walters, Robin and Lawrence, Hannah and Emerson, Tegan and Kvinge, Henry and Tomczak, Jakub and Jegelka, Stephanie}, volume = {251}, series = {Proceedings of Machine Learning Research}, month = {29 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v251/main/assets/lachi24a/lachi24a.pdf}, url = {https://proceedings.mlr.press/v251/lachi24a.html}, abstract = {Graph Neural Networks (GNNs) have achieved state-of-the-art results in tasks like node classification, link prediction, and graph classification. While much research has focused on their ability to distinguish graphs, fewer studies have addressed their capacity to differentiate links, a complex and less explored area. This paper introduces SLRGNN, a novel, theoretically grounded GNN-based method for link prediction. SLRGNN ensures that link representations are distinct if and only if the links have different structural roles within the graph. Our approach transforms the link prediction problem into a node classification problem on the corresponding line graph, enhancing expressiveness without sacrificing efficiency. Unlike existing methods, SLRGNN computes link probabilities in a single inference step, avoiding the need for individual subgraph constructions. We provide a formal proof of our method’s expressiveness and validate its superior performance through experiments on real-world datasets. The code is publicly available1} }
Endnote
%0 Conference Paper %T A Simple and Expressive Graph Neural Network Based Method for Structural Link Representation %A Veronica Lachi %A Francesco Ferrini %A Antonio Longa %A Bruno Lepri %A Andrea Passerini %B Proceedings of the Geometry-grounded Representation Learning and Generative Modeling Workshop (GRaM) %C Proceedings of Machine Learning Research %D 2024 %E Sharvaree Vadgama %E Erik Bekkers %E Alison Pouplin %E Sekou-Oumar Kaba %E Robin Walters %E Hannah Lawrence %E Tegan Emerson %E Henry Kvinge %E Jakub Tomczak %E Stephanie Jegelka %F pmlr-v251-lachi24a %I PMLR %P 187--201 %U https://proceedings.mlr.press/v251/lachi24a.html %V 251 %X Graph Neural Networks (GNNs) have achieved state-of-the-art results in tasks like node classification, link prediction, and graph classification. While much research has focused on their ability to distinguish graphs, fewer studies have addressed their capacity to differentiate links, a complex and less explored area. This paper introduces SLRGNN, a novel, theoretically grounded GNN-based method for link prediction. SLRGNN ensures that link representations are distinct if and only if the links have different structural roles within the graph. Our approach transforms the link prediction problem into a node classification problem on the corresponding line graph, enhancing expressiveness without sacrificing efficiency. Unlike existing methods, SLRGNN computes link probabilities in a single inference step, avoiding the need for individual subgraph constructions. We provide a formal proof of our method’s expressiveness and validate its superior performance through experiments on real-world datasets. The code is publicly available1
APA
Lachi, V., Ferrini, F., Longa, A., Lepri, B. & Passerini, A.. (2024). A Simple and Expressive Graph Neural Network Based Method for Structural Link Representation. Proceedings of the Geometry-grounded Representation Learning and Generative Modeling Workshop (GRaM), in Proceedings of Machine Learning Research 251:187-201 Available from https://proceedings.mlr.press/v251/lachi24a.html.

Related Material