Beyond Weisfeiler–Lehman with local ego-network encodings

Alvarez-Gonzalez, Nurudin; Kaltenbrunner, Andreas; Gómez, Vicenç

doi:http://dx.doi.org/10.3390/make5040063

Beyond Weisfeiler–Lehman with local ego-network encodings

Llicència

Citació

Alvarez-Gonzalez N, Kaltenbrunner A, Gómez V. Beyond Weisfeiler–Lehman with local ego-network encodings. Mach Learn Knowl Extr. 2023 Sep 22;5(4):1234-65. DOI: 10.3390/make5040063

Resum

Identifying similar network structures is key to capturing graph isomorphisms and learning representations that exploit structural information encoded in graph data. This work shows that ego networks can produce a structural encoding scheme for arbitrary graphs with greater expressivity than the Weisfeiler–Lehman (1-WL) test. We introduce IGEL, a preprocessing step to produce features that augment node representations by encoding ego networks into sparse vectors that enrich message passing (MP) graph neural networks (GNNs) beyond 1-WL expressivity. We formally describe the relation between IGEL and 1-WL, and characterize its expressive power and limitations. Experiments show that IGEL matches the empirical expressivity of state-of-the-art methods on isomorphism detection while improving performance on nine GNN architectures and six graph machine learning tasks.