Oral
Weisfeiler and Leman Go Loopy: A New Hierarchy for Graph Representational Learning
Raffaele Paolino · Sohir Maskey · Pascal Welke · Gitta Kutyniok
West Exhibition Hall C, B3
[
Abstract
]
[ Visit Oral Session 5A: Graph Neural Networks ]
Fri 13 Dec 10:20 a.m. — 10:40 a.m. PST
[
OpenReview]
Abstract:
We introduce rr-loopy Weisfeiler-Leman (rr-ℓℓWL), a novel hierarchy of graph isomorphism tests and a corresponding GNN framework, rr-ℓℓMPNN, that can count cycles up to length r+2r+2. Most notably, we show that rr-ℓℓWL can count homomorphisms of cactus graphs. This extends 1-WL, which can only count homomorphisms of trees and, in fact, is incomparable to kk-WL for any fixed kk. We empirically validate the expressive and counting power of rr-ℓℓMPNN on several synthetic datasets and demonstrate the scalability and strong performance on various real-world datasets, particularly on sparse graphs.
Chat is not available.