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

Simple item page
dc.article.numberarXiv:2303.12853
dc.catalogadoraba
dc.contributor.authorDelle Rose, Valentino
dc.contributor.authorKozachinskiy, Alexander
dc.contributor.authorRojas González, Luis Cristóbal
dc.contributor.authorPetrache, Mircea Alexandru
dc.contributor.authorBarceló Baeza, Pablo
dc.date.accessioned2023-08-29T17:18:05Z
dc.date.available2023-08-29T17:18:05Z
dc.date.issued2023
dc.description.abstractThe 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≥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.
dc.fechaingreso.objetodigital2023-08-29
dc.fuente.origenORCID
dc.identifier.doi10.48550/arXiv.2303.12853
dc.identifier.urihttp://www.scopus.com/inward/record.url?eid=2-s2.0-85151883336&partnerID=MN8TOARS
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/74546
dc.information.autorucInstituto de Ingeniería Matemática y Computacional; Rojas González, Luis Cristóbal; 0000-0002-9037-6102; 1182858
dc.information.autorucFacultad de Matemáticas; Petrache, Mircea Alexandru; 0000-0003-2181-169X; 1064194
dc.information.autorucInstituto de Ingeniería Matemática y Computacional; Barceló Baeza, Pablo; 0000-0003-2293-2653; 13516
dc.language.isoen
dc.nota.accesoContenido completo
dc.pagina.final14
dc.pagina.inicio1
dc.rightsacceso abierto
dc.subject.ddc510
dc.subject.deweyMatemática física y químicaes_ES
dc.titleThree iterations of (d − 1)-WL test distinguish non isometric clouds of d-dimensional points
dc.typepreprint
sipa.codpersvinculados1182858
sipa.codpersvinculados1064194
sipa.codpersvinculados13516
sipa.trazabilidadORCID;2023-08-28
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Three iterations.pdf
Size:
232.05 KB
Format:
Adobe Portable Document Format
Description:
Download
Collections
Artículos de revistas