第一作者：Muhan Zhang, Yixin Chen

作者单位：Washington University

发表时间：2018

发表期刊：NeurIPS 2018

关键内容：提出了一种图链接预测启发式算法 \(\gamma\)-decaying heuristic，并提出了SEAL(learning from Subgraphs, Embeddings and Attributes for Link prediction)预测框架.

图1

1. 引言

  • enclosing subgraph: The enclosing subgraph for a node pair (x, y) is the subgraph induced from the network by the union of x and y’s neighbors up to h hops.

常用的链接预测启发式算法：Katz, rooted PageRank and SimRank.

  • Katz index: 给邻居节点赋予不同的权重, 对于短路径赋予较大的权重, 而长路径赋予较小的权重。

  • PageRank: 入链: in-links。出链: out-links。

  • SimRank: 一种用于衡量结构上下文中个体相似度的方法，其基本思想是：如果两个对象a和b分别与另外两个对象c和d关联，且已知c与d是相似的，则a与b也是相似的；并且任意节点与其自身拥有最大的相似度值为1。

  • \(\gamma\)-decaying heuristic: 论文中进行了详细推导。并且证明了Katz, rooted PageRank and SimRank 作为 \(\gamma\)-decaying heuristic 的特殊形式。 图2

2. SEAL: An implemetation of the theory using GNN

SEAL framework : 1)enclosing subgraph extraction, 2)node information matrix construction(each row of matrix corresponds to a node’s feature vector, three components: structural node labels, node embeddings, node attributes), 3)GNN learning.

structural node labels: A node labeling is function fl : V -> N which assigns an integer label \(f_l(i)\) to every node i in the enclosing subgraph. The purpose is to use different labels to mark nodes’ different roles in an enclosing subgraph. 具体方法是Double-Radius Node Labeling (DRNL).

node embeddings: 加入负样本进行嵌入。

3. Experimental results

图3 图4

4. References

Zhang M, Chen Y. Link prediction based on graph neural networks[J]. Advances in neural information processing systems, 2018, 31.