High-Order Joint Embedding for Multi-Level Link Prediction

Link prediction infers potential links from observed networks, and is one of the essential problems in network analyses. In contrast to traditional graph representation modeling which only predicts two-way pairwise relations, we propose a novel tensor-based joint network embedding approach on simultaneously encoding pairwise links and hyperlinks onto a latent space, which captures the dependency between pairwise and multi-way links in inferring potential unobserved hyperlinks. The major advantage of the proposed embedding procedure is that it incorporates both the pairwise relationships and subgroup-wise structure among nodes to capture richer network information. In addition, the proposed method introduces a hierarchical dependency among links to infer potential hyperlinks, and leads to better link prediction. In theory we establish the estimation consistency for the proposed embedding approach, and provide a faster convergence rate compared to link prediction using pairwise links or hyperlinks only. Numerical studies on both simulation settings and Facebook ego-networks indicate that the proposed method improves both hyperlink and pairwise link prediction accuracy compared to existing link prediction algorithms. Supplementary materials for this article are available online.

链路预测（link prediction）旨在从已观测的网络中推断潜在关联，是网络分析领域的核心问题之一。与仅能预测双向成对关联的传统图表示建模不同，本文提出一种新颖的基于张量的联合网络嵌入方法，可同时将成对链路与超链路（hyperlink）编码至隐空间，该方法能够捕捉成对链路与多路链路间的依赖关系，进而推断潜在的未观测超链路。所提嵌入方法的核心优势在于，其同时融合了节点间的成对关联与子群组结构，从而能够捕获更丰富的网络信息。此外，所提方法引入了链路间的层级依赖关系以推断潜在超链路，可实现更优异的链路预测效果。理论层面，本文证明了所提嵌入方法的估计一致性，且相较于仅使用成对链路或仅使用超链路的链路预测方法，其收敛速度更快。针对仿真数据集与Facebook自我中心网络（Facebook ego-networks）的数值实验结果表明，相较于现有链路预测算法，所提方法可同时提升超链路与成对链路的预测精度。本文的补充材料可在线获取。