Subgraphormer: Unifying Subgraph GNNs and Graph Transformers via Graph Products
This work addresses the challenge of unifying two prominent graph neural network paradigms for researchers in graph machine learning, though it appears incremental as it builds on existing methods.
The paper tackled the problem of integrating Subgraph GNNs and Graph Transformers by proposing Subgraphormer, which combines their strengths via a connection to product graphs, resulting in significant performance improvements over both approaches on various datasets.
In the realm of Graph Neural Networks (GNNs), two exciting research directions have recently emerged: Subgraph GNNs and Graph Transformers. In this paper, we propose an architecture that integrates both approaches, dubbed Subgraphormer, which combines the enhanced expressive power, message-passing mechanisms, and aggregation schemes from Subgraph GNNs with attention and positional encodings, arguably the most important components in Graph Transformers. Our method is based on an intriguing new connection we reveal between Subgraph GNNs and product graphs, suggesting that Subgraph GNNs can be formulated as Message Passing Neural Networks (MPNNs) operating on a product of the graph with itself. We use this formulation to design our architecture: first, we devise an attention mechanism based on the connectivity of the product graph. Following this, we propose a novel and efficient positional encoding scheme for Subgraph GNNs, which we derive as a positional encoding for the product graph. Our experimental results demonstrate significant performance improvements over both Subgraph GNNs and Graph Transformers on a wide range of datasets.