Self-attention Dual Embedding for Graphs with Heterophily
This addresses the challenge of applying GNNs to heterophilic graphs, which are common in real-world scenarios, offering improved accuracy for node classification tasks.
The paper tackles the problem of node classification on heterophilic graphs where standard GNNs underperform, proposing a novel GNN with a self-attention mechanism that achieves state-of-the-art results on real-world graphs with thousands to millions of nodes.
Graph Neural Networks (GNNs) have been highly successful for the node classification task. GNNs typically assume graphs are homophilic, i.e. neighboring nodes are likely to belong to the same class. However, a number of real-world graphs are heterophilic, and this leads to much lower classification accuracy using standard GNNs. In this work, we design a novel GNN which is effective for both heterophilic and homophilic graphs. Our work is based on three main observations. First, we show that node features and graph topology provide different amounts of informativeness in different graphs, and therefore they should be encoded independently and prioritized in an adaptive manner. Second, we show that allowing negative attention weights when propagating graph topology information improves accuracy. Finally, we show that asymmetric attention weights between nodes are helpful. We design a GNN which makes use of these observations through a novel self-attention mechanism. We evaluate our algorithm on real-world graphs containing thousands to millions of nodes and show that we achieve state-of-the-art results compared to existing GNNs. We also analyze the effectiveness of the main components of our design on different graphs.