Research map / Point clouds / Point cloud classification
Complete Neural Networks for Complete Euclidean Graphs
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.
Shows that 3-WL applied to centralized Gram matrices of point clouds (and a Euclidean 2-SEWL variant) yields complete invariants for SO(3)/O(3) with permutations, and builds a polynomial-size GNN (2-SEWLnet) that simulates 2-SEWL with separation guarantees.
Problem
No polynomial-complexity architecture for 3D point clouds was known to be complete, i.e., to distinguish all non-isomorphic point clouds under permutation and rigid motion invariance.
Approach
Treat each point cloud as a complete Euclidean graph with inner-product edge weights and apply k-WL style tests; show a single iteration of vanilla 3-EWL and a 2-SEWL variant (adding triple-product geometric features) are complete, and realize 2-SEWL as a GNN using injective continuous multiset functions (sort-based polarization) with embedding dimension linear in the number of iterations.
Key results
- 2-SEWLnet achieves 100% separation accuracy on Hard1-3 and Harder point cloud pairs, the only model to do so across all four examples together with the 1-EWL simulation on Hard examples.
- 1-EWL simulation (1-EWLsim) separates Hard1-3 at 100% but only reaches 50% on Harder, matching the theoretical limitation of 1-EWL.
- MACE and TFN reach 100% on all four pairs (with 3-order correlations / order-3 representations), while GVPGNN is mixed (53.7 ± 13.1% on Harder).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use 2-SEWLnet instead of 1-EWLsim | Point-cloud separation models · Harder | separation accuracy: 50 % -> 100 % | Helped |
| Use 2-SEWLnet instead of 1-EWLsim | Point-cloud separation models · Hard1, Hard2, and Hard3 | separation accuracy: 100 % | No clear effect |
| Replace sum aggregation with sort and nonlinear point-wise activations (ablation) | 1-EWLsim · Hard1-Hard3 | separation accuracy | Helped |
Experimental setup
Datasets: Hard1-Hard3 point cloud pairs Harder point cloud pair (from prior work)
Benchmarks: Hard1 Hard2 Hard3 Harder
Metrics: separation accuracy
Baselines: 1-EWL MACE TFN GVPGNN EGNN-style 1-EWLsim
Builds on: k-WL / k-FWL Tensor Field Network EGNN polarization for multiset injective functions SchNet
Closest papers by meaning
- Weisfeiler Leman for Euclidean Equivariant Machine Learning (ICML 2024 · similarity 0.88)
- On the Completeness of Invariant Geometric Deep Learning Models (ICLR 2025 · similarity 0.85)
- What do Graph Neural Networks learn? Insights from Tropical Geometry (NeurIPS 2024 · similarity 0.85)
- PointRWKV: Efficient RWKV-Like Model for Hierarchical Point Cloud Learning (AAAI 2025 · similarity 0.85)
- Point Deformable Network with Enhanced Normal Embedding for Point Cloud Analysis (AAAI 2024 · similarity 0.84)
- DC-PCN: Point Cloud Completion Network with Dual-Codebook Guided Quantization (AAAI 2025 · similarity 0.84)
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.