Graph neural networks achieve high accuracy in link prediction by jointly leveraging graph topology and node attributes. Topology, however, is represented indirectly; state-of-the-art methods based on subgraph classification label nodes with distance to the target link, so that, although topological information is present, it is tempered by pooling. This makes it challenging to leverage features like loops and motifs associated with network formation mechanisms. We propose a link prediction algorithm based on a new pooling scheme called WalkPool. WalkPool combines the expressivity of topological heuristics with the feature-learning ability of neural networks. It summarizes a putative link by random walk probabilities of adjacent paths. Instead of extracting transition probabilities from the original graph, it computes the transition matrix of a "predictive" latent graph by applying attention to learned features; this may be interpreted as feature-sensitive topology fingerprinting. WalkPool can leverage unsupervised node features or be combined with GNNs and trained end-to-end. It outperforms state-of-the-art methods on all common link prediction benchmarks, both homophilic and heterophilic, with and without node attributes. Applying WalkPool to a set of unsupervised GNNs significantly improves prediction accuracy, suggesting that it may be used as a general-purpose graph pooling scheme.
翻译:图表神经网络通过联合利用图形表层学和节点属性实现链接预测的高度精准性。 但是,地形学被间接代表; 以离目标链接相距远的子图分类标签节点为基础的最先进的方法,因此,尽管存在地形信息,但它会通过集合来调节。 这使得利用与网络形成机制相关的环形和motifs等特征具有挑战性。 我们提议了一个基于称为Walk Pool的新集合方案的联系预测算法。 Walk Pool 将表层性超感性与神经网络的特征学习能力结合起来。 它通过随机的行走概率汇总相邻路径的图状链接。 它不是从原始图中提取过渡概率,而是通过将“ 预知性” 潜在图的过渡矩阵进行计算。 这可能会被解释为对地貌敏感的表指纹。 Walk Pool 能够利用非超超常的节点特征或与GNNNP和受过训练的终端至端组合组合能力。 它比州- 状态- 行走概率图概率图的精确性, 将所有通用的GPLO型预测方法都用作普通的GPINS的G的路径预测基准。