Bermuda Triangles: GNNs Fail to Detect Simple Topological Structures
Abstract
Most graph neural network architectures work by message-passing node vector embeddings over the adjacency matrix, and it is assumed that they capture graph topology by doing that. We design two synthetic tasks, focusing purely on topological problems -- triangle detection and clique distance -- on which graph neural networks perform surprisingly badly, failing to detect those "bermuda" triangles. Datasets and their generation scripts are available on https://github.com/FujitsuLaboratories/bermudatriangles.
Cite
Text
Tolmachev et al. "Bermuda Triangles: GNNs Fail to Detect Simple Topological Structures." ICLR 2021 Workshops: GTRL, 2021.Markdown
[Tolmachev et al. "Bermuda Triangles: GNNs Fail to Detect Simple Topological Structures." ICLR 2021 Workshops: GTRL, 2021.](https://mlanthology.org/iclrw/2021/tolmachev2021iclrw-bermuda/)BibTeX
@inproceedings{tolmachev2021iclrw-bermuda,
title = {{Bermuda Triangles: GNNs Fail to Detect Simple Topological Structures}},
author = {Tolmachev, Arseny and Sakai, Akira and Todoriki, Masaru and Maruhashi, Koji},
booktitle = {ICLR 2021 Workshops: GTRL},
year = {2021},
url = {https://mlanthology.org/iclrw/2021/tolmachev2021iclrw-bermuda/}
}