A Topological Perspective on Demystifying GNN-Based Link Prediction
  Performance
Yu Wang Tong Zhao Yuying Zhao Yunchao Liu Xueqi Cheng Neil Shah Tyler Derr
Graph Neural Networks (GNNs) have shown great promise in learning node
embeddings for link prediction (LP). While numerous studies aim to improve the
overall LP performance of GNNs, none have explored its varying performance
across different nodes and its underlying reasons. To this end, we aim to
demystify which nodes will perform better from the perspective of their local
topology. Despite the widespread belief that low-degree nodes exhibit poorer LP
performance, our empirical findings provide nuances to this viewpoint and
prompt us to propose a better metric, Topological Concentration (TC), based on
the intersection of the local subgraph of each node with the ones of its
neighbors. We empirically demonstrate that TC has a higher correlation with LP
performance than other node-level topological metrics like degree and subgraph
density, offering a better way to identify low-performing nodes than using
cold-start. With TC, we discover a novel topological distribution shift issue
in which newly joined neighbors of a node tend to become less interactive with
that node's existing neighbors, compromising the generalizability of node
embeddings for LP at testing time. To make the computation of TC scalable, We
further propose Approximated Topological Concentration (ATC) and
theoretically/empirically justify its efficacy in approximating TC and reducing
the computation complexity. Given the positive correlation between node TC and
its LP performance, we explore the potential of boosting LP performance via
enhancing TC by re-weighting edges in the message-passing and discuss its
effectiveness with limitations. Our code is publicly available at
https://github.com/YuWVandy/Topo_LP_GNN.