Bermuda Triangles: GNNs Fail to Detect Simple Topological Structures
Not on the map. Why?
Abstract (arXiv)
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 publicly available on github.com/FujitsuLaboratories/bermudatriangles and dataset.labs.fujitsu.com.
Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 11 of its 22 references that are in the map. First posted on arXiv 1 May 2021.
Builds on
11 of 22 references.
References · 11
- 2017Attention Is All You Needcited by 60,361
- 2017Graph Attention Networkscited by 8,923
- 2018How Powerful are Graph Neural Networks?cited by 4,393
- 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,163
- 2019Graph Neural Networks for Social Recommendationcited by 714
- 2020Benchmarking Graph Neural Networkscited by 680
- 2018T-GCN: A Temporal Graph ConvolutionalNetwork for Traffic Predictioncited by 401
- 2020Point-GNN: Graph Neural Network for 3D Object Detection in a Point Cloudcited by 335
- 2019Multi-Label Image Recognition with Graph Convolutional Networkscited by 322
- 2018GraKeL: A Graph Kernel Library in Pythoncited by 54
- 2019Understanding the Representation Power of Graph Neural Networks in Learning Graph Topologycited by 52
Built on by
Citing papers per year: 2026: 1.
1 paper.