Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2410.18676 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916594509152256 |
|---|---|
| author | Bao, Linus Jin, Emily Bronstein, Michael Ceylan, İsmail İlkan Lanzinger, Matthias |
| author_facet | Bao, Linus Jin, Emily Bronstein, Michael Ceylan, İsmail İlkan Lanzinger, Matthias |
| contents | Graph Transformers are popular neural networks that extend the well-known Transformer architecture to the graph domain. These architectures operate by applying self-attention on graph nodes and incorporating graph structure through the use of positional encodings (e.g., Laplacian positional encoding) or structural encodings (e.g., random-walk structural encoding). The quality of such encodings is critical, since they provide the necessary $\textit{graph inductive biases}$ to condition the model on graph structure. In this work, we propose $\textit{motif structural encoding}$ (MoSE) as a flexible and powerful structural encoding framework based on counting graph homomorphisms. Theoretically, we compare the expressive power of MoSE to random-walk structural encoding and relate both encodings to the expressive power of standard message passing neural networks. Empirically, we observe that MoSE outperforms other well-known positional and structural encodings across a range of architectures, and it achieves state-of-the-art performance on a widely studied molecular property prediction dataset. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_18676 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Homomorphism Counts as Structural Encodings for Graph Learning Bao, Linus Jin, Emily Bronstein, Michael Ceylan, İsmail İlkan Lanzinger, Matthias Machine Learning Graph Transformers are popular neural networks that extend the well-known Transformer architecture to the graph domain. These architectures operate by applying self-attention on graph nodes and incorporating graph structure through the use of positional encodings (e.g., Laplacian positional encoding) or structural encodings (e.g., random-walk structural encoding). The quality of such encodings is critical, since they provide the necessary $\textit{graph inductive biases}$ to condition the model on graph structure. In this work, we propose $\textit{motif structural encoding}$ (MoSE) as a flexible and powerful structural encoding framework based on counting graph homomorphisms. Theoretically, we compare the expressive power of MoSE to random-walk structural encoding and relate both encodings to the expressive power of standard message passing neural networks. Empirically, we observe that MoSE outperforms other well-known positional and structural encodings across a range of architectures, and it achieves state-of-the-art performance on a widely studied molecular property prediction dataset. |
| title | Homomorphism Counts as Structural Encodings for Graph Learning |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2410.18676 |