PlanE: Representation Learning over Planar Graphs
Radoslav Dimitrov, Zeyang Zhao, Ralph Abboud, Ismail Ilkan Ceylan
Abstract
Graph neural networks are prominent models for representation learning over graphs, where the idea is to iteratively compute representations of nodes of an input graph through a series of transformations in such a way that the learned graph function is isomorphism invariant on graphs, which makes the learned representations graph invariants. On the other hand, it is well-known that graph invariants learned by these class of models are incomplete: there are pairs of non-isomorphic graphs which cannot be distinguished by standard graph neural networks. This is unsurprising given the computational difficulty of graph isomorphism testing on general graphs, but the situation begs to differ for special graph classes, for which efficient graph isomorphism testing algorithms are known, such as planar graphs. The goal of this work is to design architectures for efficiently learning complete invariants of planar graphs. Inspired by the classical planar graph isomorphism algorithm of Hopcroft and Tarjan, we propose PlanE as a framework for planar representation learning. PlanE includes architectures which can learn complete invariants over planar graphs while remaining practically scalable. We empirically validate the strong performance of the resulting model architectures on well-known planar graph benchmarks, achieving multiple state-of-the-art results.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
7 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Open Graph Benchmark: Datasets for Machine Learning on Graphs cites Strategies for Pre-training Graph Neural Networks
- Almost Surely Asymptotically Constant Graph Neural Networks cites Do Transformers Really Perform Badly for Graph Representation?
- Weisfeiler and Leman Go Loopy: A New Hierarchy for Graph Representational Learning cites Strategies for Pre-training Graph Neural Networks
- Do Transformers Really Perform Badly for Graph Representation? cites Open Graph Benchmark: Datasets for Machine Learning on Graphs
- Do Transformers Really Perform Badly for Graph Representation? cites Strategies for Pre-training Graph Neural Networks
- Do Transformers Really Perform Badly for Graph Representation? cites Principal Neighbourhood Aggregation for Graph Nets
- Graph Representational Learning: When Does More Expressivity Hurt Generalization? cites Weisfeiler and Leman Go Loopy: A New Hierarchy for Graph Representational Learning
- Graph Representational Learning: When Does More Expressivity Hurt Generalization? cites Homomorphism Counts for Graph Neural Networks: All About That Basis
- Homomorphism Counts for Graph Neural Networks: All About That Basis cites Open Graph Benchmark: Datasets for Machine Learning on Graphs
- Homomorphism Counts for Graph Neural Networks: All About That Basis cites What graph neural networks cannot learn: depth vs width
- Principal Neighbourhood Aggregation for Graph Nets cites Open Graph Benchmark: Datasets for Machine Learning on Graphs
Cited by top-tier papers7
- Homomorphism Counts for Graph Neural Networks: All About That BasisEmily Jin, Michael M. Bronstein, Ismail Ilkan Ceylan, Matthias LanzingerICML 2024 · 23 citations
- Generative Modelling of Structurally Constrained GraphsManuel Madeira, Clément Vignac, Dorina Thanou, Pascal FrossardNeurIPS 2024 · 20 citations
- Almost Surely Asymptotically Constant Graph Neural NetworksSam Adam-Day, Michael Benedikt, Ismail Ilkan Ceylan, Ben FinkelshteinNeurIPS 2024 · 11 citations
- Weisfeiler and Leman Go Loopy: A New Hierarchy for Graph Representational LearningRaffaele Paolino, Sohir Maskey, Pascal Welke, Gitta KutyniokNeurIPS 2024 · 4 citations
- Graph Representational Learning: When Does More Expressivity Hurt Generalization?Sohir Maskey, Raffaele Paolino, Fabian Jogl, Gitta Kutyniok et al.ICLR 2026 · 4 citations
Builds on15
- Open Graph Benchmark: Datasets for Machine Learning on GraphsWeihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong et al.NeurIPS 2020 · 3,935 citations
- Strategies for Pre-training Graph Neural NetworksWeihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik et al.ICLR 2020 · 1,744 citations
- Do Transformers Really Perform Badly for Graph Representation?Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng et al.NeurIPS 2021 · 1,632 citations
- Principal Neighbourhood Aggregation for Graph NetsGabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò et al.NeurIPS 2020 · 914 citations
- What graph neural networks cannot learn: depth vs widthAndreas LoukasICLR 2020 · 336 citations
Related papers
- Complete Neural Networks for Complete Euclidean GraphsSnir Hordan, Tal Amir, Steven J. Gortler, Nadav DymAAAI 2024 · 9 citations
- Reconstruction for Powerful Graph RepresentationsLeonardo Cotta, Christopher Morris, Bruno RibeiroNeurIPS 2021 · 96 citations
- Cycle to Clique (Cy2C) Graph Neural Network: A Sight to See beyond Neighborhood AggregationYun Young Choi, Sun Woo Park, Youngho Woo, U Jin ChoiICLR 2023
- Learning Invariant Graph Representations for Out-of-Distribution GeneralizationHaoyang Li, Ziwei Zhang, Xin Wang, Wenwu ZhuNeurIPS 2022 · 170 citations
- Three Iterations of (d - 1)-WL Test Distinguish Non Isometric Clouds of d-dimensional PointsValentino Delle Rose, Alexander Kozachinskiy, Cristobal Rojas, Mircea Petrache et al.NeurIPS 2023 · 14 citations
