Self-attention Dual Embedding for Graphs with Heterophily
Yurui Lai Taiyan Zhang Rui Fan
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.