Learning Convolutional Neural Networks for Graphs
Learning Convolutional Neural Networks for Graphs
Mathias Niepert, Mohamed Ahmed, Konstantin Kutzkov
NEC lab
Intro
提供了一种在graph上面做CNN的方法。
先解释了在image上做CNN的核心：convolution就是将一个receptive field中，关于中心点在其邻居上做一个linear transformation。而且这里还隐藏了一个spacial顺序：从左到右，从上到下，并且是impact。
Background
这里提出了一个patchy-san(Select-Assemble-Normalize)方法，对node进行排序，然后对每一个node都挖取固定k个邻居，从而组成了receptive field。
在3.2提到了color refinement，大概是BFS时候的一种分层方法。
Learning CNNs for Arbitrary Graphs
核心算法有四个步骤
- Node Sequence Selection：是receptive field扫过整个sequence的顺序。w个receptive field，同时按照stride s进行移动。如果seq中node个数少于w，就用0 padding。至于为什么要进行选择node order，是因为有些graphical application（甚至很大部分）是需要能够将异构的图案映射到相似的representation vector上。
- Neighbourhood Assembly：对于每一个node，构造receptive field，半径为k。（这里他用了一个set N来表示接收到的邻居）
- Graph Normalization：将这个receptive field映射到linear space。
- Convolution Architecture：对于feturization，能够对于node和edge分别得到这么多个tensor $$(w,k,a_v)$$, $$(w, k,k,a_e)$$，其中$$a_v$$是node channel/特则，$$a_e$$是edge的。这些可以变成$$(wk, a_v), (wk^2, a_e)$$的tensor，然后在训练的同时将二者的convolutional layer合并即可。
Appendix
操作步骤的前三步，也就是SAN就是为解决graph similarity的问题。是一个很有意思的突破口。从理论上分析了graph normalization的作用。
针对于二维平面可以，但是三维上还有待发展。