Please use this identifier to cite or link to this item:
Title: Beyond Weisfeiler–Lehman with Local Ego-Network Encodings
Author: Alvarez-Gonzalez, Nurudin  
Kaltenbrunner, Andreas  
Gómez, Vicenç  
Citation: Alvarez-Gonzalez, N, [Nurudin], Kaltenbrunner, A. [Andreas], Gómez, V. [Vicenç]. (2023). Beyond Weisfeiler–Lehman with Local Ego-Network Encodings. Machine Learning and Knowledge Extraction, 5(4). doi: 10.3390/make5040063
Abstract: 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.
Keywords: graph neural networks
graph representation learning
graph isomorphism
GNN expressivity
ego networks
Document type: info:eu-repo/semantics/article
Version: info:eu-repo/semantics/publishedVersion
Issue Date: 22-Sep-2023
Publication license:  
Appears in Collections:Articles cientÍfics

Files in This Item:
File Description SizeFormat 
Beyond_Weisfeiler_Lehman_with_Local_Ego_Network_Encodings.pdf1,2 MBAdobe PDFThumbnail
View statistics

Items in repository are protected by copyright, with all rights reserved, unless otherwise indicated.