Beyond Weisfeiler–Lehman with Local Ego-Network Encodings
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 Wei...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-09-01
|
| Series: | Machine Learning and Knowledge Extraction |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2504-4990/5/4/63 |
| _version_ | 1797380300418842624 |
|---|---|
| author | Nurudin Alvarez-Gonzalez Andreas Kaltenbrunner Vicenç Gómez |
| author_facet | Nurudin Alvarez-Gonzalez Andreas Kaltenbrunner Vicenç Gómez |
| author_sort | Nurudin Alvarez-Gonzalez |
| collection | DOAJ |
| description | 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi mathvariant="normal" mathsize="normal">I</mi><mi mathvariant="normal" mathsize="small">G</mi><mi mathvariant="normal" mathsize="small">E</mi><mi mathvariant="normal" mathsize="small">L</mi></mrow></semantics></math></inline-formula>, 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi mathvariant="normal" mathsize="normal">I</mi><mi mathvariant="normal" mathsize="small">G</mi><mi mathvariant="normal" mathsize="small">E</mi><mi mathvariant="normal" mathsize="small">L</mi></mrow></semantics></math></inline-formula> and 1-WL, and characterize its expressive power and limitations. Experiments show that <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi mathvariant="normal" mathsize="normal">I</mi><mi mathvariant="normal" mathsize="small">G</mi><mi mathvariant="normal" mathsize="small">E</mi><mi mathvariant="normal" mathsize="small">L</mi></mrow></semantics></math></inline-formula> 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. |
| first_indexed | 2024-03-08T20:35:24Z |
| format | Article |
| id | doaj.art-f356f514957141fe92aab1c80616ab23 |
| institution | Directory Open Access Journal |
| issn | 2504-4990 |
| language | English |
| last_indexed | 2024-03-08T20:35:24Z |
| publishDate | 2023-09-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Machine Learning and Knowledge Extraction |
| spelling | doaj.art-f356f514957141fe92aab1c80616ab232023-12-22T14:22:07ZengMDPI AGMachine Learning and Knowledge Extraction2504-49902023-09-01541234126510.3390/make5040063Beyond Weisfeiler–Lehman with Local Ego-Network EncodingsNurudin Alvarez-Gonzalez0Andreas Kaltenbrunner1Vicenç Gómez2Department of Information and Communications Technologies, Universitat Pompeu Fabra, 08018 Barcelona, SpainInternet Interdisciplinary Institute, Universitat Oberta de Catalunya, 08018 Barcelona, SpainDepartment of Information and Communications Technologies, Universitat Pompeu Fabra, 08018 Barcelona, SpainIdentifying 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi mathvariant="normal" mathsize="normal">I</mi><mi mathvariant="normal" mathsize="small">G</mi><mi mathvariant="normal" mathsize="small">E</mi><mi mathvariant="normal" mathsize="small">L</mi></mrow></semantics></math></inline-formula>, 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi mathvariant="normal" mathsize="normal">I</mi><mi mathvariant="normal" mathsize="small">G</mi><mi mathvariant="normal" mathsize="small">E</mi><mi mathvariant="normal" mathsize="small">L</mi></mrow></semantics></math></inline-formula> and 1-WL, and characterize its expressive power and limitations. Experiments show that <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi mathvariant="normal" mathsize="normal">I</mi><mi mathvariant="normal" mathsize="small">G</mi><mi mathvariant="normal" mathsize="small">E</mi><mi mathvariant="normal" mathsize="small">L</mi></mrow></semantics></math></inline-formula> 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.https://www.mdpi.com/2504-4990/5/4/63graph neural networksgraph representation learningWeisfeiler–Lehmangraph isomorphismGNN expressivityego networks |
| spellingShingle | Nurudin Alvarez-Gonzalez Andreas Kaltenbrunner Vicenç Gómez Beyond Weisfeiler–Lehman with Local Ego-Network Encodings Machine Learning and Knowledge Extraction graph neural networks graph representation learning Weisfeiler–Lehman graph isomorphism GNN expressivity ego networks |
| title | Beyond Weisfeiler–Lehman with Local Ego-Network Encodings |
| title_full | Beyond Weisfeiler–Lehman with Local Ego-Network Encodings |
| title_fullStr | Beyond Weisfeiler–Lehman with Local Ego-Network Encodings |
| title_full_unstemmed | Beyond Weisfeiler–Lehman with Local Ego-Network Encodings |
| title_short | Beyond Weisfeiler–Lehman with Local Ego-Network Encodings |
| title_sort | beyond weisfeiler lehman with local ego network encodings |
| topic | graph neural networks graph representation learning Weisfeiler–Lehman graph isomorphism GNN expressivity ego networks |
| url | https://www.mdpi.com/2504-4990/5/4/63 |
| work_keys_str_mv | AT nurudinalvarezgonzalez beyondweisfeilerlehmanwithlocalegonetworkencodings AT andreaskaltenbrunner beyondweisfeilerlehmanwithlocalegonetworkencodings AT vicencgomez beyondweisfeilerlehmanwithlocalegonetworkencodings |