Complete Neural Networks for Complete Euclidean Graphs

• URL: http://arxiv.org/abs/2301.13821v4
• Date: Tue, 9 Apr 2024 11:57:04 GMT
• Title: Complete Neural Networks for Complete Euclidean Graphs
• Authors: Snir Hordan, Tal Amir, Steven J. Gortler, Nadav Dym,
• Abstract summary: We show that point clouds can be completely determined, up to permutation and rigid motion, by applying the 3-WL graph isomorphism test to the point cloud's centralized Gram matrix. We then show how our complete Euclidean tests can be simulated by an Euclidean graph neural network of moderate size and demonstrate their separation capability on highly symmetrical point clouds.
• Score: 4.416503115535553
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Neural networks for point clouds, which respect their natural invariance to permutation and rigid motion, have enjoyed recent success in modeling geometric phenomena, from molecular dynamics to recommender systems. Yet, to date, no model with polynomial complexity is known to be complete, that is, able to distinguish between any pair of non-isomorphic point clouds. We fill this theoretical gap by showing that point clouds can be completely determined, up to permutation and rigid motion, by applying the 3-WL graph isomorphism test to the point cloud's centralized Gram matrix. Moreover, we formulate an Euclidean variant of the 2-WL test and show that it is also sufficient to achieve completeness. We then show how our complete Euclidean WL tests can be simulated by an Euclidean graph neural network of moderate size and demonstrate their separation capability on highly symmetrical point clouds.

Related papers

• Bridging Domain Gap of Point Cloud Representations via Self-Supervised Geometric Augmentation [15.881442863961531]
  We introduce a novel scheme for induced geometric invariance of point cloud representations across domains. On one hand, a novel pretext task of predicting translation of distances of augmented samples is proposed to alleviate centroid shift of point clouds. On the other hand, we pioneer an integration of the relational self-supervised learning on geometrically-augmented point clouds.
  arXiv  Detail & Related papers  (2024-09-11T02:39:19Z)
• Neural varifolds: an aggregate representation for quantifying the geometry of point clouds [2.2474167740753557]
  We propose a new surface geometry characterisation, namely a neural varifold representation of point clouds. The varifold representation quantifies the surface geometry of point clouds through the manifold-based discrimination. The proposed neural varifold is evaluated on three different sought-after tasks -- shape matching, few-shot shape classification and shape reconstruction.
  arXiv  Detail & Related papers  (2024-07-05T20:08:16Z)
• Point Cloud Compression with Implicit Neural Representations: A Unified Framework [54.119415852585306]
  We present a pioneering point cloud compression framework capable of handling both geometry and attribute components. Our framework utilizes two coordinate-based neural networks to implicitly represent a voxelized point cloud. Our method exhibits high universality when contrasted with existing learning-based techniques.
  arXiv  Detail & Related papers  (2024-05-19T09:19:40Z)
• On the Completeness of Invariant Geometric Deep Learning Models [22.43250261702209]
  Invariant models are capable of generating meaningful geometric representations by leveraging informative geometric features in point clouds. We show that GeoNGNN, the geometric counterpart of one of the simplest subgraph graph neural networks (subgraph GNNs), can effectively break these corner cases' symmetry. By leveraging GeoNGNN as a theoretical tool, we further prove that: 1) most subgraph GNNs developed in traditional graph learning can be seamlessly extended to geometric scenarios with E(3)-completeness.
  arXiv  Detail & Related papers  (2024-02-07T13:32:53Z)
• Weisfeiler Leman for Euclidean Equivariant Machine Learning [3.0222726571099665]
  We show that PPGN can simulate $2$-WL uniformly on all point clouds with low complexity. Secondly, we show that $2$-WL tests can be extended to point clouds which include both positions and velocities.
  arXiv  Detail & Related papers  (2024-02-04T13:25:18Z)
• Geometric Neural Diffusion Processes [55.891428654434634]
  We extend the framework of diffusion models to incorporate a series of geometric priors in infinite-dimension modelling. We show that with these conditions, the generative functional model admits the same symmetry.
  arXiv  Detail & Related papers  (2023-07-11T16:51:38Z)
• Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
  We present two new classes of algorithms for efficient field integration on graphs encoding point clouds. The first class, SeparatorFactorization(SF), leverages the bounded genus of point cloud mesh graphs, while the second class, RFDiffusion(RFD), uses popular epsilon-nearest-neighbor graph representations for point clouds.
  arXiv  Detail & Related papers  (2023-02-02T08:33:36Z)
• Convolutional Neural Networks on Manifolds: From Graphs and Back [122.06927400759021]
  We propose a manifold neural network (MNN) composed of a bank of manifold convolutional filters and point-wise nonlinearities. To sum up, we focus on the manifold model as the limit of large graphs and construct MNNs, while we can still bring back graph neural networks by the discretization of MNNs.
  arXiv  Detail & Related papers  (2022-10-01T21:17:39Z)
• Differentiable Convolution Search for Point Cloud Processing [114.66038862207118]
  We propose a novel differential convolution search paradigm on point clouds. It can work in a purely data-driven manner and thus is capable of auto-creating a group of suitable convolutions for geometric shape modeling. We also propose a joint optimization framework for simultaneous search of internal convolution and external architecture, and introduce epsilon-greedy algorithm to alleviate the effect of discretization error.
  arXiv  Detail & Related papers  (2021-08-29T14:42:03Z)
• Permutation Matters: Anisotropic Convolutional Layer for Learning on Point Clouds [145.79324955896845]
  We propose a permutable anisotropic convolutional operation (PAI-Conv) that calculates soft-permutation matrices for each point. Experiments on point clouds demonstrate that PAI-Conv produces competitive results in classification and semantic segmentation tasks.
  arXiv  Detail & Related papers  (2020-05-27T02:42:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.