Temporal graphs are ubiquitous in real-world scenarios, such as social
network, trade and transportation. Predicting dynamic links between nodes in a
temporal graph is of vital importance. Traditional methods usually leverage the
temporal neighborhood of interaction history to generate node embeddings first
and then aggregate the source and target node embeddings to predict the link.
However, such methods focus on learning individual node representations, but
overlook the pairwise representation learning nature of link prediction and
fail to capture the important pairwise features of links such as common
neighbors (CN). Motivated by the success of Neural Common Neighbor (NCN) for
static graph link prediction, we propose TNCN, a temporal version of NCN for
link prediction in temporal graphs. TNCN dynamically updates a temporal
neighbor dictionary for each node, and utilizes multi-hop common neighbors
between the source and target node to learn a more effective pairwise
representation. We validate our model on five large-scale real-world datasets
from the Temporal Graph Benchmark (TGB), and find that it achieves new
state-of-the-art performance on three of them. Additionally, TNCN demonstrates
excellent scalability on large datasets, outperforming popular GNN baselines by
up to 6.4 times in speed. Our code is available at https:
//github.com/GraphPKU/TNCN.

我们提出了 TNCN，这是 NCN 的一个时间版本，用于预测时间图中的链接，并使用多跳公共邻居来学习更有效的成对表示。我们在五个大规模真实世界数据集上验证了我们的模型，并发现它在其中三个上实现了最新的最先进表现。此外，TNCN 在处理大型数据集上表现出了出色的可扩展性，在速度上超过了流行的 GNN 基线最多 6.4 倍。

高效神经常见邻居用于时间图链接预测

Efficient Neural Common Neighbor for Temporal Graph Link Prediction

We introduce and explore a new method for inferring hidden geometric
coordinates of nodes in complex networks based on the number of common
neighbors between the nodes. We compare this approach to the HyperMap method,
which is based only on the connections (and disconnections) between the nodes,
i.e., on the links that the nodes have (or do not have). We find that for high
degree nodes the common-neighbors approach yields a more accurate inference
than the link-based method, unless heuristic periodic adjustments (or
"correction steps") are used in the latter. The common-neighbors approach is
computationally intensive, requiring $O(t^4)$ running time to map a network of
$t$ nodes, versus $O(t^3)$ in the link-based method. But we also develop a
hybrid method with $O(t^3)$ running time, which combines the common-neighbors
and link-based approaches, and explore a heuristic that reduces its running
time further to $O(t^2)$, without significant reduction in the mapping
accuracy. We apply this method to the Autonomous Systems (AS) Internet, and
reveal how soft communities of ASes evolve over time in the similarity space.
We further demonstrate the method's predictive power by forecasting future
links between ASes. Taken altogether, our results advance our understanding of
how to efficiently and accurately map real networks to their latent geometric
spaces, which is an important necessary step towards understanding the laws
that govern the dynamics of nodes in these spaces, and the fine-grained
dynamics of network connections.

使用常见邻居方法将节点隐藏的几何坐标推断出来，与基于连接的 HyperMap 方法相比，常见邻居方法对于高度的节点推断更准确且能够预测自治系统互联网间的未来连接，提高了对复杂网络的映射精度。

使用共同邻居推断网络几何形状

Network Geometry Inference using Common Neighbors

Missing link prediction of networks is of both theoretical interest and
practical significance in modern science. In this paper, we empirically
investigate a simple framework of link prediction on the basis of node
similarity. We compare nine well-known local similarity measures on six real
networks. The results indicate that the simplest measure, namely common
neighbors, has the best overall performance, and the Adamic-Adar index performs
the second best. A new similarity measure, motivated by the resource allocation
process taking place on networks, is proposed and shown to have higher
prediction accuracy than common neighbors. It is found that many links are
assigned same scores if only the information of the nearest neighbors is used.
We therefore design another new measure exploited information of the next
nearest neighbors, which can remarkably enhance the prediction accuracy.

本文研究了基于节点相似度的网络链路预测模型，并比较了九种不同的局部相似度度量方法在六个真实网络中的性能。结果表明，最简单的方法即共同邻居法在各项性能上表现最佳，其次是 Adamic-Adar 指数。在此基础上提出了一种基于资源分配过程的新的相似度度量方法，并发现仅考虑最近邻信息时许多链接分配得分相同，设计出一种利用下一个最近邻信息的新方法，可以显著提高预测准确性。