3 Iterations of (d − 1)-WL test distinguish non-isometric point clouds of d-dimensional points

Dec 10, 2023

Speakers

About

The Weisfeiler-Lehman (WL) test is a fundamental iterative algorithm for checking the 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 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> 2, and 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.

Organizer

Like the format? Trust SlidesLive to capture your next event!

Professional recording and live streaming, delivered globally.

Sharing

Recommended Videos

Presentations on similar topic, category or speaker

Interested in talks like this? Follow NeurIPS 2023