  Link prediction is a common problem in network science that transects many
disciplines. The goal is to forecast the appearance of new links or to find
links missing in the network. Typical methods for link prediction use the
topology of the network to predict the most likely future or missing
connections between a pair of nodes. However, network evolution is often
mediated by higher-order structures involving more than pairs of nodes; for
example, cliques on three nodes (also called triangles) are key to the
structure of social networks, but the standard link prediction framework does
not directly predict these structures. To address this gap, we propose a new
link prediction task called "pairwise link prediction" that directly targets
the prediction of new triangles, where one is tasked with finding which nodes
are most likely to form a triangle with a given edge. We develop two
PageRank-based methods for our pairwise link prediction problem and make
natural extensions to existing link prediction methods. Our experiments on a
variety of networks show that diffusion based methods are less sensitive to the
type of graphs used and more consistent in their results. We also show how our
pairwise link prediction framework can be used to get better predictions within
the context of standard link prediction evaluation.
