Understanding and extending subgraph GNNs by rethinking their symmetries
Subgraph GNNs are a recent class of expressive Graph Neural Networks (GNNs) which model graphs as collections of subgraphs. So far, the design space of possible Subgraph GNN architectures as well as their basic theoretical properties are still largely unexplored. In this paper, we study the most pro...
| Asıl Yazarlar: | , , , |
|---|---|
| Materyal Türü: | Conference item |
| Dil: | English |
| Baskı/Yayın Bilgisi: |
Curran Associates
2022
|
| _version_ | 1826310620891316224 |
|---|---|
| author | Frasca, F Bevilacqua, B Bronstein, M Maron, H |
| author_facet | Frasca, F Bevilacqua, B Bronstein, M Maron, H |
| author_sort | Frasca, F |
| collection | OXFORD |
| description | Subgraph GNNs are a recent class of expressive Graph Neural Networks (GNNs) which model graphs as collections of subgraphs. So far, the design space of possible Subgraph GNN architectures as well as their basic theoretical properties are still largely unexplored. In this paper, we study the most prominent form of subgraph methods, which employs node-based subgraph selection policies such as ego-networks or node marking and deletion. We address two central questions: (1) What is the upper-bound of the expressive power of these methods? and (2) What is the family of equivariant message passing layers on these sets of subgraphs?. Our first step in answering these questions is a novel symmetry analysis which shows that modelling the symmetries of node-based subgraph collections requires a significantly smaller symmetry group than the one adopted in previous works. This analysis is then used to establish a link between Subgraph GNNs and Invariant Graph Networks (IGNs). We answer the questions above by first bounding the expressive power of subgraph methods by 3-WL, and then proposing a general family of message-passing layers for subgraph methods that generalises all previous node-based Subgraph GNNs. Finally, we design a novel Subgraph GNN dubbed SUN, which theoretically unifies previous architectures while providing better empirical performance on multiple benchmarks. |
| first_indexed | 2024-03-07T07:54:38Z |
| format | Conference item |
| id | oxford-uuid:8072a0e9-e1e6-4a29-adda-faa1e78a3649 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T07:54:38Z |
| publishDate | 2022 |
| publisher | Curran Associates |
| record_format | dspace |
| spelling | oxford-uuid:8072a0e9-e1e6-4a29-adda-faa1e78a36492023-08-09T10:18:24ZUnderstanding and extending subgraph GNNs by rethinking their symmetriesConference itemhttp://purl.org/coar/resource_type/c_5794uuid:8072a0e9-e1e6-4a29-adda-faa1e78a3649EnglishSymplectic ElementsCurran Associates2022Frasca, FBevilacqua, BBronstein, MMaron, HSubgraph GNNs are a recent class of expressive Graph Neural Networks (GNNs) which model graphs as collections of subgraphs. So far, the design space of possible Subgraph GNN architectures as well as their basic theoretical properties are still largely unexplored. In this paper, we study the most prominent form of subgraph methods, which employs node-based subgraph selection policies such as ego-networks or node marking and deletion. We address two central questions: (1) What is the upper-bound of the expressive power of these methods? and (2) What is the family of equivariant message passing layers on these sets of subgraphs?. Our first step in answering these questions is a novel symmetry analysis which shows that modelling the symmetries of node-based subgraph collections requires a significantly smaller symmetry group than the one adopted in previous works. This analysis is then used to establish a link between Subgraph GNNs and Invariant Graph Networks (IGNs). We answer the questions above by first bounding the expressive power of subgraph methods by 3-WL, and then proposing a general family of message-passing layers for subgraph methods that generalises all previous node-based Subgraph GNNs. Finally, we design a novel Subgraph GNN dubbed SUN, which theoretically unifies previous architectures while providing better empirical performance on multiple benchmarks. |
| spellingShingle | Frasca, F Bevilacqua, B Bronstein, M Maron, H Understanding and extending subgraph GNNs by rethinking their symmetries |
| title | Understanding and extending subgraph GNNs by rethinking their symmetries |
| title_full | Understanding and extending subgraph GNNs by rethinking their symmetries |
| title_fullStr | Understanding and extending subgraph GNNs by rethinking their symmetries |
| title_full_unstemmed | Understanding and extending subgraph GNNs by rethinking their symmetries |
| title_short | Understanding and extending subgraph GNNs by rethinking their symmetries |
| title_sort | understanding and extending subgraph gnns by rethinking their symmetries |
| work_keys_str_mv | AT frascaf understandingandextendingsubgraphgnnsbyrethinkingtheirsymmetries AT bevilacquab understandingandextendingsubgraphgnnsbyrethinkingtheirsymmetries AT bronsteinm understandingandextendingsubgraphgnnsbyrethinkingtheirsymmetries AT maronh understandingandextendingsubgraphgnnsbyrethinkingtheirsymmetries |