Link prediction | 三篇SEAL相关工作小结

本文涉及三篇link prediction相关工作，均与subgraph相关，或者说与SEAL相关，作者为Muhan Zhang, 目前在Facebook. 以下内容结合图学习小组sw大佬分享内容以及本人(AIGraph)学习，如有疏漏，欢迎吐槽。

涉及的论文(以下论文都已经公开代码和原文)

• Link Prediction Based on Graph Neural Networks（NeurIPS'18）

• Inductive Matrix Completion Based on Graph Neural Networks (ICLR'20) 

• Revisiting Graph Neural Networks for Link Prediction (最近的)
  

链路预测是图的关键问题。传统link prediction算法侧重一些启发式算法，比如使用一些评分函数，如公共邻域和katz指数。这些方法简单、可解释和可扩展。不过，每种启发式算法都有一个很强的假设，即当两个节点可能有边，这就限制了它们在这些假设失败的图上的有效性。在这方面，一个更合理的方法应该是从一个给定的图中学习一个合适的启发式方法，而不是使用预定义的启发式方法。

本次介绍的这三篇工作通过提取每个目标边周围的局部子图，学习一个函数从子图模式映射到边的存在性，从而自动学习适合于当前网络的“启发式”。

用一句话概括三篇论文做的事情：

• SEAL: 通过局部子图抓取图的结构信息，获得丰富的节点表示

• IGMC: 将SEAL通过子图学习结构的思想用于二分图的推荐系统中

• Revisiting SEAL: SEAL+labeling trick，在OGB link prediction上获得了很好的表现。

SEAL

SEAL并不限制学习到的图结构特征符合某一种特别的形式（如gamma-decaying heuristics），而是之直接学习一般图结构特征
步骤为：
（1）提取子图
（2）构造点信息矩阵
（3）GNN学习

上图显示了SEAL的框架，SEAL对于每一条边提取一个局部封闭的子图结构，然后用一个GNN学习节点的表示，从而进行link prediction. 如何定义一个子图的封闭结构呢？简单的来说：给定两个点x,y那么subgraph={i|d(i,x)<=h or d(i,y)<=h},h是h-hop. 复杂来说: 参考原文了哈

那么主要有三个步骤：

（1）点结构标签：表示点在子图中的作用。这么做因为要预测的边的两个节点是center，而子图中相对center的位置不同的点的重要性也不同。
不mark出点的结构性标签，GNN就不知道是要预测哪两个点之间的边
边结构标注的方法符合两个原则：
（i）center 的label为1
（ii）对于其他点，任意两点i、j如果d(x,i)=d(x,j) d(y,i)=d(y,j) 那么i、j的label相同。d为两点之间的路径长度。

根据以上两个原则论文提出Double-Radius Node Labeling (DRNL)方法

（2）加入显示、隐式特征
（3）将点嵌入、点属性拼接

以上方法虽然简单，但是有效，并且论文提出了一个有意思的理论：

定理1：（针对传统的启发式算法）任何一个高阶的启发式，都可以通过提取的子图G_(x,y)^h计算得到

与启发式算法对比，这些方法一般都不适用node feature

这些方法有node feature

论文:

https://proceedings.neurips.cc/paper/2018/file/53f0d7c537d99b3824f0f99d62ea2428-Paper.pdf

IGMC(基于图神经网络的归纳矩阵补全)

矩阵补全(Matrix Completion)被广泛应用于推荐系统中,本文提出的这篇IGMC为每一个(user, item) pair提取一个包含子图(enclosing subgraph)，并用图神经网络(graph neural network)训练一个由子图结构映射到用户对商品评分(rating)的回归模型。IGMC在多个数据集上取得了最先进的性能.

做法与上面类似，提取每个子图后，首先要对其中的节点进行标注(node labeling)。目的是为了区分子图中节点的不同角色。比如要区分目标节点(target user/item)和背景节点 (context nodes)。目标节点标示出到底要预测子图中哪一对(user, item)之间的评分。同时，可以区分不同阶的邻居节点，比如一阶邻居(1-hop neighbors)和二阶邻居(2-hop neighbors)对目标节点的贡献程度并不相同。对目标用户(target user)，标注为0，对目标商品(target item)，标注为1；对i-hop的背景用户标注为2i，对i-hop的背景商品标注为2i+1。之后，将这些标注转化为one-hot encoding vector，作为每个节点的初始特征输入给图神经网络。在图神经网络(GNN)中，结合relational graph convolutional operator (R-GCN)作为卷积层，进行学习。

论文链接：https://arxiv.org/abs/1904.12058

REVISITING SEAL

这篇论文在OGB上跑了跑实验，同时又进一步分析了一下，方法还是那个方法。摘要如下：

图神经网络（GNN）近年来取得了巨大的成功。三种最常见的应用任务包括节点分类，链接预测和图分类。虽然有大量关于节点分类和图分类的文献，但用于链接预测的GNN相对较少研究和了解。存在两种代表性的方法类别：GAE和SEAL。GAE首先使用GNN学习所有节点的节点嵌入，然后聚合源节点和目标节点的嵌入作为它们的链接表示。SEAL提取围绕源节点和目标节点的子图，在子图中标记节点，然后使用GNN从标记的子图中学习链接表示。在本文中，我们彻底讨论了这两种方法之间的区别，并得出结论，简单地聚合节点嵌入并不能产生有效的链接表示，而从链接周围正确标记的子图中学习可以提供高度可表达且可概括的链接表示。最近的大规模OGB链接预测数据集的实验表明，与GAE方法相比，SEAL的性能提高了195％，在4个数据集中的3个数据集上获得了最新的技术成果。

那么主要看一看分析：

Proposition: GAE不能学习到结构性的链接表示

Theorem: 如果GNN学习两个图，学习到的表示一样，那么两个图同构，反过来也是。

这个理论表明：直接聚合不能够学习到有结构性的表示，而加上label tricking的seal可以，下面的图可能说的更清楚一些，根据seal的做法，加上一些自定义的标签可以区分图中的node pair (v1,v2),(v1,v3),但是不加的话，没有办法区分。

最终的效果很好

读完的感受: 方法简单但有效的时候，分析很重要，甚至考验数学功底，不然可能被审稿人认为测试集混进了训练中，然后直接拒掉。

---

由于微信平台算法改版，公号内容将不再以时间排序展示，如果大家想第一时间看到我们的推送，强烈建议星标我们和给我们多点点【在看】。星标具体步骤为：

（1）点击页面最上方"AINLP"，进入公众号主页。

（2）点击右上角的小点点，在弹出页面点击“设为星标”，就可以啦。

感谢支持，比心。

欢迎加入AINLP技术交流群

进群请添加AINLP小助手微信 AINLPer（id: ainlper)，备注NLP技术交流

推荐阅读

这个NLP工具，玩得根本停不下来

征稿启示| 200元稿费+5000DBC（价值20个小时GPU算力）

完结撒花！李宏毅老师深度学习与人类语言处理课程视频及课件（附下载）

从数据到模型，你可能需要1篇详实的pytorch踩坑指南

如何让Bert在finetune小数据集时更“稳”一点

模型压缩实践系列之——bert-of-theseus，一个非常亲民的bert压缩方法

文本自动摘要任务的“不完全”心得总结番外篇——submodular函数优化

Node2Vec 论文+代码笔记

模型压缩实践收尾篇——模型蒸馏以及其他一些技巧实践小结

中文命名实体识别工具（NER）哪家强？

学自然语言处理，其实更应该学好英语

斯坦福大学NLP组Python深度学习自然语言处理工具Stanza试用

关于AINLP

AINLP 是一个有趣有AI的自然语言处理社区，专注于 AI、NLP、机器学习、深度学习、推荐算法等相关技术的分享，主题包括文本摘要、智能问答、聊天机器人、机器翻译、自动生成、知识图谱、预训练模型、推荐系统、计算广告、招聘信息、求职经验分享等，欢迎关注！加技术交流群请添加AINLPer(id：ainlper)，备注工作/研究方向+加群目的。

阅读至此了，分享、点赞、在看三选一吧🙏