%0 Conference Paper %1 beddarwiesing2022extension %A Beddar-Wiesing, Silvia %A D'Inverno, Giuseppe Alessio %A Graziani, Caterina %A Lachi, Veronica %A Moallemy-Oureh, Alice %A Scarselli, Franco %B Workshp on Mining and Learning on Graphs (MLG), ECML PKDD %D 2022 %K imported itegpub isac-www %P 1--13 %T On the Extension of the Weisfeiler-Lehman Hierarchy by WL Tests for Arbitrary Graphs %U https://openreview.net/forum?id=Qt6GrgDz2y5 %X Graph isomorphism (GI) has occupied both theoreticians and applied scientists since the early 1950s. Over the years, several approaches and algorithms with which an isomorphism between two graphs can be tested have been developed. A general approach is the Weisfeiler–Lehman (WL) test, which is based on a coloring algorithm and provides a necessary criterion for graph isomorphism. However, the WL test is restricted to examining graphs with only node attributes. Therefore, this paper presents two extensions of the WL algorithm to allow for testing on arbitrary graphs. One considers edge attributes, and the other tests the isomorphism on dynamic graphs. Additionally, we extend the WL-hierarchy by the attributed and dynamic WL tests and show that it is a partial order, which induces a lattice. In the future, this may allow for practical implications coming from lattice theory.

@inproceedings{beddarwiesing2022extension, abstract = {Graph isomorphism (GI) has occupied both theoreticians and applied scientists since the early 1950s. Over the years, several approaches and algorithms with which an isomorphism between two graphs can be tested have been developed. A general approach is the Weisfeiler–Lehman (WL) test, which is based on a coloring algorithm and provides a necessary criterion for graph isomorphism. However, the WL test is restricted to examining graphs with only node attributes. Therefore, this paper presents two extensions of the WL algorithm to allow for testing on arbitrary graphs. One considers edge attributes, and the other tests the isomorphism on dynamic graphs. Additionally, we extend the WL-hierarchy by the attributed and dynamic WL tests and show that it is a partial order, which induces a lattice. In the future, this may allow for practical implications coming from lattice theory.}, added-at = {2023-01-18T12:54:07.000+0100}, author = {Beddar-Wiesing, Silvia and D'Inverno, Giuseppe Alessio and Graziani, Caterina and Lachi, Veronica and Moallemy-Oureh, Alice and Scarselli, Franco}, biburl = {https://www.bibsonomy.org/bibtex/2e57baab7e90862f4f099e62dafc4bba6/ies}, booktitle = {Workshp on Mining and Learning on Graphs (MLG), ECML PKDD}, interhash = {c429a44faab55e82ab1d1a25d09763df}, intrahash = {e57baab7e90862f4f099e62dafc4bba6}, keywords = {imported itegpub isac-www}, pages = {1--13}, timestamp = {2023-01-18T12:54:07.000+0100}, title = {On the Extension of the {W}eisfeiler-{L}ehman Hierarchy by WL Tests for Arbitrary Graphs}, url = {https://openreview.net/forum?id=Qt6GrgDz2y5}, year = 2022 }