Link prediction is a fundamental task in graph learning, inherently shaped by
the topology of the graph. While traditional heuristics are grounded in graph
topology, they encounter challenges in generalizing across diverse graphs.
Recent research efforts have aimed to leverage the potential of heuristics, yet
a unified formulation accommodating both local and global heuristics remains
undiscovered. Drawing insights from the fact that both local and global
heuristics can be represented by adjacency matrix multiplications, we propose a
unified matrix formulation to accommodate and generalize various heuristics. We
further propose the Heuristic Learning Graph Neural Network (HL-GNN) to
efficiently implement the formulation. HL-GNN adopts intra-layer propagation
and inter-layer connections, allowing it to reach a depth of around 20 layers
with lower time complexity than GCN. HL-GNN is proven to be more expressive
than heuristics and conventional GNNs, and it can adaptively trade-off between
node features and topological information. Extensive experiments on the
Planetoid, Amazon, and OGB datasets underscore the effectiveness and efficiency
of HL-GNN. It outperforms existing methods by a large margin in prediction
performance. Additionally, HL-GNN is several orders of magnitude faster than
heuristic-inspired methods while requiring only a few trainable parameters. The
case study further demonstrates that the generalized heuristics and learned
weights are highly interpretable.

利用统一矩阵公式和 HL-GNN 方法，本研究提出了一种整合了各类算启发式方法和传统图神经网络的学习模型，通过广泛的实验验证了其高效性和显著优于现有方法的预测性能。