Link prediction requires predicting which new links are likely to appear in a
graph. Being able to predict unseen links with good accuracy has important
applications in several domains such as social media, security, transportation,
and recommendation systems. A common approach is to use features based on the
common neighbors of an unconnected pair of nodes to predict whether the pair
will form a link in the future. In this paper, we present an approach for link
prediction that relies on higher-order analysis of the graph topology, well
beyond common neighbors. We treat the link prediction problem as a supervised
classification problem, and we propose a set of features that depend on the
patterns or motifs that a pair of nodes occurs in. By using motifs of sizes 3,
4, and 5, our approach captures a high level of detail about the graph topology
within the neighborhood of the pair of nodes, which leads to a higher
classification accuracy. In addition to proposing the use of motif-based
features, we also propose two optimizations related to constructing the
classification dataset from the graph. First, to ensure that positive and
negative examples are treated equally when extracting features, we propose
adding the negative examples to the graph as an alternative to the common
approach of removing the positive ones. Second, we show that it is important to
control for the shortest-path distance when sampling pairs of nodes to form
negative examples, since the difficulty of prediction varies with the
shortest-path distance. We experimentally demonstrate that using off-the-shelf
classifiers with a well constructed classification dataset results in up to 10
percentage points increase in accuracy over prior topology-based and feature
learning methods.

本文使用图的拓扑结构，提出了一种基于 3、4、5 阶 motif-based features 的监督分类算法来预测链接，实验结果显示在构建完好的分类数据集上使用现成的分类器，相较于之前基于拓扑结构和特征学习方法，准确率提高了 10 个百分点。