论文笔记（二） DEMO-Net:Degree-specific Graph Neural Networks for Node and Graph Classification

这篇论文不是cv相关，由于要做报告，顺便发篇博客吧

这是2019年8月份在KDD上的一篇关于图神经网络的文章，（找了半天连中文笔记都找不到，只好自己写一篇了）我也是第一次接触图神经网络，有错误请务必评论指正，不胜感激。

FCOs论文链接：https://arxiv.org/abs/1906.02319?context=cs
开源代码：https://github.com/jwu4sml/DEMO-Net
报告ppt：https://pan.baidu.com/s/1KNjHfdpBQvOvLsxJbolOPg提取码：dgrv

Introduction

background

1. 各种高影响力的领域都产生了大量的图数据：比如生物信息学，全基因组关联研究，社交网络分析等等，而一整张图是难以进行分析的，所以需要从节点和边的属性以及图的拓扑结构中学习到高效的节点和图的表示，然后用这种表示来进行分类、聚合等数据分析
2. 深度学习在网格结构数据（图像，视频，语言等等）上的成功：所以研究者们觉得 图的拓扑结构和节点属性可以通过像卷积神经网络那样 对局部相邻节点的连续特征向量的压缩 来整合成一个端到端的训练架构

由此诞生了图卷积网络，在于模仿卷进神经网络在图像数据上的成功。其把节点的局部相邻节点聚集并转换为了特征向量。通过使用Laplacian平滑[9，12]或高级注意机制[18]将节点属性与图结构信息集成，图神经网络学习在低维特征空间中的节点表示，其中图中的邻近节点将共享相似的表示。并且，为了学习整个图的表示，研究者提出了图级池化机制来压缩节点表示为全局特征向量。由图神经网络学习到的节点和图的表示在许多下游图挖掘任务中取得了state-of-the-art的成就，比如节点分类，图分类等等。

但是，它目前存在如下缺陷：

1. 在图神经网络设计上对图卷积的特性分析十分有限。
2. 对节点邻域的属性进行简单地混合。这导致学习表示的度特定的图结构信息丢失。
3. 对图级的池化方法的理论性解释大大缺失。
   所以，基于这些缺点，本文做出了如下贡献：
4. 从 Weisfeiler-Lehman 图同构测试的观点下给出了图神经网络的理论分析.
5. 提出了一个名为DEMO-Net的通用图神经网络框架：a.提出了一个特定度数的多任务图卷积函数来学习节点表示. b. 提出了一种新的图级池化方案，用于学习特定度数的Hilbert核空间中的图表示.
6. 在节点和图的分类benchmark上的实验结果证明了我们提出的DEMO-Net模型的有效性和高效性

Related work

问题定义

(懒得打公式了。。。)

图神经网络就是为了解决如上问题诞生的。
其步骤主要分为以下几个step：
• Feature initialization(label initialization): 节点的特征由原始属性向量初始化。
• Neighborhood detection (multiset-label determination): 它确定要从邻域那里收集信息的节点所在的邻居节点。
• Neighbors sorting (multiset-label sorting): 以度值的升序或降序对邻居进行排序。
• Feature aggregation(label compression): 通过压缩包括自身在内的已聚合邻居的特征向量来更新节点特征。
• Graph-level pooling(graphrep resentation): 它汇总了形成全局图形表示的所有节点功能。

其中，最为重要的是第4步，基于不同的特征聚合方法，已经提出了很多图卷积网络：
其中，第一个公式中的hkv表示第k层的节点表示，sigama表示**函数，avu表示对邻接矩阵A的重归一化加上自身的循环，Wk表示该层权重。
第二个公式中的avu表示邻居节点对该节点的重要性
第三个公式中的AGGREGATE函数为聚合函数，通常来说有三种：1. max聚合 2. mean聚合 3. LSTM编码聚合 ,CONCAT为连接操作。
基于对这些聚合函数的观察，作者总结了以下几点：
• 除了GraphSAGE之外，它们的特征聚合方案对邻居节点的顺序不变。
• k层神经网络的输出特征可以看作是种子周围子树的表示。
• 当神经层越深时，节点表示变得越近且难以区分，因为子树将共享更多的公共元素。

Proposed Model

作者的模型是基于WL图同构测试中节点属性的特性提出的，我们先看看WL图同构测试：
WL图同构测试是一种用来检测两个图是否同构的算法，步骤如下：

1. 聚合邻居节点
2. 通过哈希映射重新为节点定值
3. 等节点值不再被哈希映射更新时，看两个图的节点分布是否一致。若一致则同构
   作者发现，WL图同构测试和图卷积神经网络在步骤上是一致的：
   所以，作者想通过发现WL图同构测试上的一些特性来设计图神经网络。
   首先作者发现了以下特性：
   要满足两个节点共享同一特征向量，必须满足：
4. 节点属性一致
5. 节点的度数一致

所以，作者设计了如下的图卷积方程：

其中fs()表示了节点的属性，fdeg()表示了度数相同的节点。
fs()可以很简单的被一个全连接层表示：

而对于fdeg()，作者给出了两种表示方法：
6. 特定度数权重方程：

7. 哈希核方程：


对于图表示的学习，图的表示由节点的表示连接而成：


对于图之间的相似性度量，作者采用graph kernel 的方式来比较：
作者定义的degree-specific WL kernel：

其中：



这部分知识储备有限，只翻译一下作者的观点。。。
相比于其他的graph kernel

1. Sum/mean Kernel
   
2. WL subtree Kernel
   
   作者提出的graph kernel有如下优点：
3. 当节点具有连续的属性向量时，WL子树内核无法应用于测量图相似度。
4. 将公式(1)与公式(6)比较，我们的图级表示特定于度的内核空间中，从而导致明确保留特定于度的图结构。

Experiment