Three iterations of $(d-1)$-WL test distinguish non isometric clouds of $d$-dimensional points

• URL: http://arxiv.org/abs/2303.12853v2
• Date: Tue, 28 Mar 2023 12:29:33 GMT
• Title: Three iterations of $(d-1)$-WL test distinguish non isometric clouds of $d$-dimensional points
• Authors: Valentino Delle Rose, Alexander Kozachinskiy, Crist\'obal Rojas, Mircea Petrache and Pablo Barcel\'o
• Abstract summary: We study when the Weisfeiler--Lehman test is complete for clouds of euclidean points represented by complete distance graphs. Our main result states that the $(d-1)$-dimensional WL test is complete for point clouds in $d$-dimensional Euclidean space, for any $dge 2$, and that only three iterations of the test suffice.
• Score: 58.9648095506484
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Weisfeiler--Lehman (WL) test is a fundamental iterative algorithm for checking isomorphism of graphs. It has also been observed that it underlies the design of several graph neural network architectures, whose capabilities and performance can be understood in terms of the expressive power of this test. Motivated by recent developments in machine learning applications to datasets involving three-dimensional objects, we study when the WL test is {\em complete} for clouds of euclidean points represented by complete distance graphs, i.e., when it can distinguish, up to isometry, any arbitrary such cloud. Our main result states that the $(d-1)$-dimensional WL test is complete for point clouds in $d$-dimensional Euclidean space, for any $d\ge 2$, and that only three iterations of the test suffice. Our result is tight for $d = 2, 3$. We also observe that the $d$-dimensional WL test only requires one iteration to achieve completeness.

Related papers

• 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)
• On the Power of the Weisfeiler-Leman Test for Graph Motif Parameters [9.599347633285637]
  The $k$-dimensional Weisfeiler-Leman ($k$WL) test is a widely-recognized method for verifying graph isomorphism. This paper provides a precise characterization of the WL-dimension of labeled graph motif parameters.
  arXiv  Detail & Related papers  (2023-09-29T08:26:44Z)
• Clustering based Point Cloud Representation Learning for 3D Analysis [80.88995099442374]
  We propose a clustering based supervised learning scheme for point cloud analysis. Unlike current de-facto, scene-wise training paradigm, our algorithm conducts within-class clustering on the point embedding space. Our algorithm shows notable improvements on famous point cloud segmentation datasets.
  arXiv  Detail & Related papers  (2023-07-27T03:42:12Z)
• Weisfeiler and Leman Go Measurement Modeling: Probing the Validity of the WL Test [58.1543112860658]
  We uncover misalignments between graph machine learning practitioners' conceptualizations of expressive power and $k$-WL. We argue for extensional definitions and measurement of expressive power based on benchmarks.
  arXiv  Detail & Related papers  (2023-07-11T20:06:12Z)
• Point2Vec for Self-Supervised Representation Learning on Point Clouds [66.53955515020053]
  We extend data2vec to the point cloud domain and report encouraging results on several downstream tasks. We propose point2vec, which unleashes the full potential of data2vec-like pre-training on point clouds.
  arXiv  Detail & Related papers  (2023-03-29T10:08:29Z)
• Complete Neural Networks for Complete Euclidean Graphs [4.416503115535553]
  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.
  arXiv  Detail & Related papers  (2023-01-31T18:07:26Z)
• MATE: Masked Autoencoders are Online 3D Test-Time Learners [63.3907730920114]
  MATE is the first Test-Time-Training (TTT) method designed for 3D data. It makes deep networks trained for point cloud classification robust to distribution shifts occurring in test data.
  arXiv  Detail & Related papers  (2022-11-21T13:19:08Z)
• MetaSets: Meta-Learning on Point Sets for Generalizable Representations [100.5981809166658]
  We study a new problem of 3D Domain Generalization (3DDG) with the goal to generalize the model to other unseen domains of point clouds without access to them in the training process. We propose to tackle this problem via MetaSets, which meta-learns point cloud representations from a group of classification tasks on carefully-designed transformed point sets. We design two benchmarks for Sim-to-Real transfer of 3D point clouds. Experimental results show that MetaSets outperforms existing 3D deep learning methods by large margins.
  arXiv  Detail & Related papers  (2022-04-15T03:24:39Z)
• On the emergence of tetrahedral symmetry in the final and penultimate layers of neural network classifiers [9.975163460952045]
  We show that even the final output of the classifier $h$ is not uniform over data samples from a class $C_i$ if $h$ is a shallow network. We explain this observation analytically in toy models for highly expressive deep neural networks.
  arXiv  Detail & Related papers  (2020-12-10T02:32:52Z)

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.