Affinity-Aware Graph Networks
This work addresses the challenge of enhancing GNN expressivity for relational data analysis, offering a domain-specific improvement with competitive gains.
The authors tackled the problem of limited expressivity in Graph Neural Networks (GNNs) due to small receptive fields by incorporating affinity measures from random walks, such as effective resistance and commute times, into message passing networks, resulting in improved performance on node and graph property prediction tasks, including achieving the best known single-model validation MAE on the OGB-LSC-PCQM4Mv1 dataset.
Graph Neural Networks (GNNs) have emerged as a powerful technique for learning on relational data. Owing to the relatively limited number of message passing steps they perform -- and hence a smaller receptive field -- there has been significant interest in improving their expressivity by incorporating structural aspects of the underlying graph. In this paper, we explore the use of affinity measures as features in graph neural networks, in particular measures arising from random walks, including effective resistance, hitting and commute times. We propose message passing networks based on these features and evaluate their performance on a variety of node and graph property prediction tasks. Our architecture has lower computational complexity, while our features are invariant to the permutations of the underlying graph. The measures we compute allow the network to exploit the connectivity properties of the graph, thereby allowing us to outperform relevant benchmarks for a wide variety of tasks, often with significantly fewer message passing steps. On one of the largest publicly available graph regression datasets, OGB-LSC-PCQM4Mv1, we obtain the best known single-model validation MAE at the time of writing.