[论文笔记] [2015] Deep Convolutional Networks on Graph-Structured Data

这是15年的一篇论文，是Joan Bruna等人对13年的工作 Spectral Network [1] 做出的改进，主要解决两个了问题：

1. spectral network 拓展到大规模数据（large-scale, high-dimensional）任务上
2. 对于没有给定图结构的任务，提出了一种 graph estimation 方法

Generalizing Convolutions to Graphs

这一篇在spetral network的定义上，描述地更加简洁明了。

Definition 1. Let $W$ be a $N\times N$ similarity matrix representing an undirected graph $G$, and let $L=I?D^{?1/2}W{D}^{?1/2}$ be its graph Laplacian with $D=W?1$ eigevectors $U=(u_1,...,u_N)$. Then a graph convolution of input signals $x$ with filters $g$ on $G$ is defined by $x{?}_{G}g=U^T(Ux\odot Ug)$, where $\odot$ represents a point-wise product.
Learning filters on a graph thus to learning spectral multipliers $w_g=(w_1,....,w_N)$
$$x{?}_{G}g:=U^T(diag(w_g)Ux)$$

为了使卷积具备局部的性质（目的是为了减少参数和复杂度），采用 smoothing kernel $\mathcal{K}\in {\mathbb{R}}^{N\times N_0}$，$w_g=\mathcal{K}{\tilde{w}}_g$。
pooling 通过层次聚类实现。

Graph Construction

考虑到在很多任务中，并没有直接的图结构，为了构建图，作者提出了两种方式，无监督和监督的方式，估计图的相似矩阵（其实就是构建图的邻接矩阵，这里的相似就是计算图上两个节点的特征相似度，作为边的权重）。

Unsupervised Graph Estimation

无监督的方式，其实就是直接根据节点的特征，计算两个节点之间的欧式距离（或者 Z-score），再利用 Gaussian diffusion Kernel （或者 self-tuning diffusion）计算得到邻接矩阵的权重
$$w(i,j)=ex{p}^{?\frac{d(i,j)}{{\alpha }^2}}$$

Supervised Graph Estimation

当数据带有 label，可以考虑采用监督的方式，先构建一个全连接的神经网络，输入 $X\in {\mathbb{R}}^{L\times N}$ 以及 labels $y\in {1,...,C}^L$，每一层采用ReLU，并加入 dropout。然后抽出第一层的 $W_1\in {\mathcal{R}}^{N\times M_1}$，通过
$$d_{sup}(i,j)=\Vert W_{1,i}?W_{1,j}{\Vert }^2$$
计算得到两个节点的距离。这里利用 $W_1$ 作为节点的表示向量，根据这个训练得到的表示向量计算节点的特征，思路就有点像 word2vec，比用无监督的方式会优一些。

Experiments

作者在三个数据集上做了实验，其中一个是预测分子活性，实验中的数据集有8193个样本，2796个特征。因为是带label的数据集，采用监督的方式构建图结构（这里的图结构就是每个特征作为图上一个节点，再根据上述方法计算邻接矩阵的权重），再通过GCN层和FC层，比单纯使用全连接层的效果会优一些。

总结

这篇论文的一个亮点就是提出了在没有提前给出图结构的任务上，如何构建图结构，并利用图卷积建模。但有个问题需要思考的是，这种估计的方式是否会为后面的建模带来误差，虽然也看到一些工作也是用上面的方法来构建图。
另外一方面，想起了19年IJCAI上的一篇工作 [2]，文中提到了一个 Self-adaptive 邻接矩阵，这是一个可学习的矩阵（由两个Node Embedding相乘，就是在计算节点间的相似度），可单独作为图卷积层（没有给定图结构），端到端的学习出节点隐藏的空间依赖（也就是学习出隐藏的图结构），感觉也是一种构建图的方式，但任务的后续建模可能还需推敲。

参考文献

[1] Bruna J, Zaremba W, Szlam A, et al. Spectral networks and locally connected networks on graphs[J]. arXiv preprint arXiv:1312.6203, 2013.
[2] Wu Z, Pan S, Long G, et al. Graph wavenet for deep spatial-temporal graph modeling[J]. arXiv preprint arXiv:1906.00121, 2019.