A novel approach to graph distinction through GENEOs and permutants
This work addresses graph isomorphism discrimination for researchers in machine learning and graph theory, but it is incremental as it applies an existing method to a new domain.
The paper tackled the problem of distinguishing r-regular graphs up to isomorphisms using Group Equivariant Non-Expansive Operators (GENEOs), showing that GENEOs offer a good compromise between efficiency and computational cost in graph comparison.
The theory of Group Equivariant Non-Expansive Operators (GENEOs) was initially developed in Topological Data Analysis for the geometric approximation of data observers, including their invariances and symmetries. This paper departs from that line of research and explores the use of GENEOs for distinguishing $r$-regular graphs up to isomorphisms. In doing so, we aim to test the capabilities and flexibility of these operators. Our experiments show that GENEOs offer a good compromise between efficiency and computational cost in comparing $r$-regular graphs, while their actions on data are easily interpretable. This supports the idea that GENEOs could be a general-purpose approach to discriminative problems in Machine Learning when some structural information about data and observers is explicitly given.