Research map / Graph learning / GNN architectures
Graph As Point Set
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Converts a graph into a point set via parameterized symmetric rank decomposition of D+A (coordinates with inner products encoding edges), then encodes it with an orthogonal-equivariant Transformer (PST) and a DeepSets variant (PSDS).
Problem
Graph representation learning typically relies on adjacency via message passing or adjacency-based attention; the paper asks whether adjacency can be dropped by converting graphs losslessly into sets of independent points for set encoders.
Approach
Symmetric rank decomposition of the augmented adjacency D+A gives each node a coordinate whose inner products encode edges; two graphs are isomorphic iff their coordinate point sets match up to an orthogonal transformation. A scalar-vector Transformer that is O(r)-equivariant then encodes the point set, and the coordinates inject graph structure losslessly into attention.
Key results
- PST counts all 13 listed substructures in the synthetic counting benchmark, while the second-best I2-GNN counts 10 of 13.
- PST achieves ZINC-full MAE 0.018 versus best baseline ~0.022, a reduction of about 18%.
- PST attains the best PascalVOC-SP F1 (0.4010) and Peptides-Func AP (0.6984) on the Long Range Graph Benchmark.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use PST instead of 2-DRFWL(2) GNN | QM9 graph property prediction · QM9 (11 of 12 targets) | MAE: average 11% reduction in loss | Helped |
| add 3D coordinates or features as input (ablation) | PST on QM9 · QM9 (8 of 12 targets) | MAE: average 4% reduction in loss | Helped |
| use PSDS instead of PST as the set encoder (ablation) | graph-to-set method · QM9 | MAE: 3.49_{\pm 0.05} vs 3.55_{\pm 0.10} | Mixed |
| use PSDS instead of PST as the set encoder (ablation) | graph-to-set method · ZINC | MAE: 0.063_{\pm0.003} -> 0.162_{\pm 0.007} | Hurt |
| use PSDS instead of PST as the set encoder (ablation) | graph-to-set method · PascalVOC-SP | F1 score: 0.2134_{\pm0.0050} -> 0.4010_{\pm0.0072} | Hurt |
| use PSDS instead of PST as the set encoder (ablation) | graph-to-set method · Peptides-Func | AP: 0.5965_{\pm 0.0064} -> 0.6984_{\pm0.0051} | Hurt |
| use PST instead of Grit | graph property prediction · ZINC | MAE: 0.059_{\pm 0.002} -> 0.063_{\pm0.003} | Hurt |
| use PST instead of the strongest reported baseline | graph property prediction · ZINC-full | MAE: 0.022_{\pm0.002} -> 0.018_{\pm0.001} | Helped |
| use PST instead of CIN | graph property prediction · ogbg-molhiv | AUC: 80.94_{\pm0.57} -> 80.32_{\pm 0.71} | Hurt |
| use PST instead of Exphormer | long-range graph prediction · PascalVOC-SP | F1 score: 0.3975_{\pm0.0037} -> 0.4010_{\pm0.0072} | Helped |
| use PST instead of Grit | long-range graph prediction · Peptides-Func | AP: 0.6988_{\pm 0.0082} vs 0.6984_{\pm0.0051} | No clear effect |
| use PST instead of Graph ViT | long-range graph prediction · Peptides-Struct | MAE: 0.2449_{\pm0.0016} -> 0.2470_{\pm 0.0015} | Hurt |
Surprising findings
- Vanilla MPNNs can match Graph Transformers on LRGB with better hyperparameters, suggesting LRGB is not a rigorous benchmark.
- PSDS (DeepSets-based) is comparable to GIN, showing a non-attention set encoder also works on graphs.
Limitations
- Scalability is constrained by the Transformer's quadratic attention; PST is slower on large graphs.
- Higher time complexity than existing graph transformers.
- Theory relies on mapping to high-dimensional coordinates, so prior 3D equivariant expressivity results do not transfer directly.
Experimental setup
Datasets: QM9 ZINC ZINC-full ogbg-molhiv TU datasets PascalVOC-SP Peptides-Func Peptides-Struct synthetic substructure counting graphs
Benchmarks: QM9 ZINC ZINC-full ogbg-molhiv Long Range Graph Benchmark substructure counting synthetic
Metrics: MAE AUC F1 score AP normalized MAE
Baselines: GIN ID-GNN NGNN GNN-AK+ I2-GNN PPGN Graphormer GPS Grit SAN Exphormer CIN
Builds on: DeepSets Graph Transformer PPGN Laplacian eigenvector positional encoding
Closest papers by meaning
- Structure-Aware Transformer for Graph Representation Learning (ICML 2022 · similarity 0.88)
- SGFormer: Simplifying and Empowering Transformers for Large-Graph Representations (NeurIPS 2023 · similarity 0.88)
- Subgraphormer: Unifying Subgraph GNNs and Graph Transformers via Graph Products (ICML 2024 · similarity 0.86)
- Graph Positional and Structural Encoder (ICML 2024 · similarity 0.86)
- Learning Efficient Positional Encodings with Graph Neural Networks (ICLR 2025 · similarity 0.86)
- G-Adapter: Towards Structure-Aware Parameter-Efficient Transfer Learning for Graph Transformer Networks (AAAI 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.