“问渠那得清如许，为有源头活水来”，通过前沿领域知识的学习，从其他研究领域得到启发，对研究问题的本质有更清晰的认识和理解，是自我提高的不竭源泉。为此，我们特别精选论文阅读笔记，开辟“源头活水”专栏，帮助你广泛而深入的阅读科研文献，敬请关注。
地址：https://www.zhihu.com/people/tan-cheng-70-42
论文地址：
【1】https://papers.nips.cc/paper/2020/file/5bca8566db79f3788be9efd96c9ed70d-Paper.pdf
快捷下载：本公众号后台回复【paper64】下载本论文
01
这篇文章是来自NeurIPS 2020的《Subgraph Neural Networks》[1]，作者首先提出了一个新的问题：子图分类；然后设计了subgraph neural networks（SubGNN）来有效地获取子图表征。
在图的node-level和graph-level预测的任务上，深度学习方法已经取得了很好的表现了，但是对子图（subgraph）预测的研究很少。graph-level的表征提供了对图的全局视角但损失了一定的局部信息，而node-level的表征更关注局部拓扑结构。subgraph-level的表征需要关注近邻（neighbor）、结构（structure）和位置（position）三个方面的信息，更多的信息带来更多的挑战：（1）要求对不同大小的子图进行联合预测，这涉及到怎样在忽略节点邻域且包含一些迥然不同的节点时（如下图1左，红框内的两个绿色节点）得到表征；（2）子图包含丰富的高阶连接模式，包括内部成员节点和外部与补图（原图除了给定子图的部分）的连接，这涉及到怎样把两类连接的信息注入GNN的信息传输；（3）子图位于原图的某一区域，这涉及到怎样有效学习子图在原图上的位置；（4）子图之间不可避免地会存在依赖关系，这涉及到怎样在保持特征信息的同时利用依赖关系并实现inductive learning。
02
子图表征和属性预测：给定子图集合，SubGNN定义了信息传播结构，用于为每个子图生成维的子图表征，然后用这些表征学习子图分类器，即。
子图表征学习要求模型对子图特有的一些属性编码。如下图2所示，子图有六个拓扑属性，两列表示子图内部和外部的，三行表示位置、近邻和结构三类。对于位置，border position表示子图与补图之间的距离，internal position表示元素和子图之间的相对距离；对于近邻，border neighborhood表示中任意节点k步内的节点集合，internal neighborhood表示每个元素自己的border neighborhood；对于结构，border structure表示内部节点与border neighborhood之间的边，internal structure表示子图元素之间的内部连接。
03
如下图所示，SubGNN用启发式的方法，把message从anchor patches传递到子图元素，然后聚合得到的表征到最终的子图embedding。
04
Subgraph-Level Message PassingAnchor patches 是从图上随机采样的子图，定义message从anchor patch到子图元素为：其中表示通道（位置、结构和近邻），是衡量元素和anchor patch 的相似度函数。这些messages然后会被转换为顺序不变的隐层表征和子图元素：其中是对通道可学习的权重矩阵，是的简写。表征的顺序不变性对于层间message传递是必要的，但是它会限制捕捉子图结构和位置的能力。因此这里构造了property-aware的输出表征。最后SubGNN把信息汇聚到P，N，S三个子通道并concat起来（）。chaneel-specific表征首先通过通道聚合函数聚合成每一层子图元素的表征，然后通过聚合函数聚合所有层元素的表征得到最后的子图元素表征。最后每个元素的元素表征通过聚合到最后的子图表征。05
（1）用于生成anchor patches的采样函数；（3）用于给anchor patches和子图元素之间的message赋权重的相似函数。本文目的在于学术交流，并不代表本公众号赞同其观点或对其内容真实性负责，版权归原作者所有，如有侵权请告知删除。
“源头活水”历史文章
更多源头活水专栏文章，
请点击文章底部“阅读原文”查看
分享、点赞、在看，给个三连击呗！