Weisfeiler and Leman Go Loopy: A New Hierarchy for Graph Representational Learning

Paolino, Raffaele; Maskey, Sohir; Welke, Pascal und Kutyniok, Gitta : Weisfeiler and Leman Go Loopy: A New Hierarchy for Graph Representational Learning. Advances in Neural Information Processing Systems 37 (NeurIPS 2024), Vancouver Convention Centre, 10. – 15. Dezember 2024.

Abstract

We introduce -loopy Weisfeiler-Leman ( - WL), a novel hierarchy of graph isomorphism tests and a corresponding GNN framework, - MPNN, that can count cycles up to length . Most notably, we show that - WL 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 -WL for any fixed . We empirically validate the expressive and counting power of the proposed - MPNN on several synthetic datasets and present state-of-the-art predictive performance on various real-world datasets.

• Dokumententyp: Konferenzbeitrag (Paper)
• Fakultät: Mathematik, Informatik und Statistik > Mathematik > Professur für Mathematische Grundlagen des Verständnisses der künstlichen Intelligenz
• Themengebiete: 500 Naturwissenschaften und Mathematik > 510 Mathematik
• Sprache: Englisch