Paolino, R., Maskey, S., Welke, P., & Kutyniok, G. (2024, May 11). Weisfeiler and Leman go Loopy: A New Hierarchy for Graph Representational Learning [Poster Presentation]. ICLR 2024 Workshop Bridging the Gap Between Practice and Theory in Deep Learning, Austria. https://doi.org/10.34726/6959
We introduce r-loopy Weisfeiler-Leman (r-lWL), a novel hierarchy of graph isomorphism tests and a corresponding GNN framework, r-lMPNN, that can count cycles up to length r + 2. Most notably, we show that r-lWL can count homomorphisms of cactus graphs. This strictly extends classical 1-WL, which can only count homomorphisms of trees and, in fact, is incomparable to k-WL for any fixed k. We empirically validate the expressive and counting power of the proposed r-lMPNN on several synthetic datasets and present state-of-the-art predictive performance on various real-world datasets. The code is available online.
-
Project title:
Structured Data Learning with Generalized Similarities: ICT22-059 (WWTF Wiener Wissenschafts-, Forschu und Technologiefonds)
-
Additional information:
We introduce r-loopy Weisfeiler-Leman (r-lWL), a novel hierarchy of graph isomorphism tests and a corresponding GNN framework, r-lMPNN, that can count cycles up to length r + 2. Most notably, we show that r-lWL can count homomorphisms of cactus graphs. This strictly extends classical 1-WL, which can only count homomorphisms of trees and, in fact, is incomparable to k-WLfor any fixed k. We empirically validate the expressive and counting power of the proposed r-lMPNN on several synthetic datasets and present state-of-the-art predictive performance on various real-world datasets. The code is available online.
-
Research Areas:
Visual Computing and Human-Centered Technology: 100%
CC BY-NC-SA 4.0
