Higher-order Link Prediction Using Triangle Embeddings

Higher-order structures, like triangles, in networks provide rich information about a network. Usually, the focus is on pairwise interactions that are modeled as edges. However, many interactions may actually involve more than two nodes simultaneously. For example, social interactions often occur in groups of people, research collaborations are among more than two authors, and biological networks describe interactions of a group of proteins. Predicting the occurrence of such higher-order structures helps us solve problems in various disciplines, such as social network analysis, drug combinations research, and news topic connections. The primary focus of this paper is to explore representations of three-node interactions, called triangles (a special case of higher-order structures) in order to predict higher-order links. We propose new methods to embed triangles by generalizing the node2vec algorithm under different operators, by using 1-hop subgraphs in the the graph2vec algorithm, and in graph neural networks. The performance of these techniques is evaluated against some benchmark scores on various datasets used in the bibliography. From the results, it is observed that our node2vec based triangle embedding method performs better or similar on most of the datasets compared to previous models.