Learning Convolutional Neural Networks for Graphs (2016 ICML)
ppt讲解
[概要]
对于图像images来说，CNN对输入image的局部关联的区域进行操作，与此类似，本文提出了一种通用的方法，也抽取graph中局部关联的区域进行相应的操作。
由于images是排列成grid形状，所以images可以直接运用卷积操作。但是对于图结构来说，需要一个从graph到向量的映射的一个预处理过程。
作者提出了对任意的图学习卷积神经网络的框架：PATCHY-SAN(Select-Assemble-Normalize)。通过三个步骤构建卷积分片：
- 从图中选择一个固定长度的节点序列；
- 对序列中的每个节点，收集固定大小的邻居集合；
- 对由当前节点及其对应的邻居构成的子图进行规范化，作为卷积结构的输入。
通过上述三个步骤构建出所有的卷积片之后，利用卷积结构分别对每个分片进行操作。
图结构：可以是有向图，也可以是无向图；图可以有多种类型的边；图的点或边的特征，可以同时有多个离散和连续的特征。
[应用]
将 CNNs 拓展到大规模的基于 graph 的学习问题中，主要考虑两类问题：
- 给定一组 graphs，学习一个函数，使之可以对 unseen graphs 用于 classification 或者 regression problem
- 给定一个大型的 graph，学习 graph 的表示，使其可以用于推理不可见的 graph 属性，例如：node types 或者 missing edges
[算法]
1. 节点序列选择[Node Sequence Selection]
- graph labeling: labeling算法用来确定一个graph中node的次序。这个算法可以是centrality的测量方式，比如：between centrality， Weisfeiler-Lehman algorithm, 或者其他你认为可行的算法。由此可以得到每个节点的rank 值（为了不同的图能够有一个规范化的组织方式）
- 从该序列中根据一定的间隔
隔段选取
个节点构成最终的节点序列。对每个访问的点，生成一个receptive field, 直到生成
figure 1.jpg
2. 邻居节点收集[Neighborhood Assembly]
对于上一步获得的节点序列中的每一个节点，利用广度优化搜索扩展邻居节点，和源节点一起构成一个至少大小的邻域集合。
3. 图规范化[Graph Normalization]
figure 2.png
使用NAUTY, 对邻域集合用标号函数进行排序, 得到大小为的接受域。
4. 卷积结构[Convolutional Architecture]
对于节点的属性，个节点属性值构成了一个输入通道，对于边的属性，
个属性值也构成了一个输入通道。我们可以分别用一维的卷积层来处理这两种输入通道（对于节点属性卷积层长度为
，对于边属性卷积层长度为
）。
[贡献] Theoretical Contributions
- the definition of the normalization problem on graphs and its complexity;
- a method for comparing graph lebaling approaches for a collection of graphs;
- a result that shows PATCHY-SAN generalizes CNNs on images.
[优缺点] Pros/Cons
Advantages
- Graph kernel design not required
- Outperforms graph kernels on several datasets (speed and accuracy)
- Incorporates node and edge features (discrete and continuous)
- Supports visualizations (graph motifs, etc.)
Disadvantages
- Prone to overfitting on smaller data sets (graph kernel benchmarks)
- Shift from designing graph kernels to tuning hyperparameters
- Graph normalization not part of learning
[实验及结果分析]
Date Sets
6 standard benchmark data sets: MUTAG, PCT, NCI1, NCI109, PROTEIN, D&D.
Experimental Set-up
PSCN vs state-of-the-art graph kenerls: SP, RW, GK, WL
Reference：
