这篇文章在DiffPool的基础上引入了多通道（Multi-channel）的概念，提出了multi channel graph convolutional networks (MuchGCN)，通过inter-channel和intra-channel两种方式聚合通道上的信息。
本文被IJCAI2020接收，在写这篇博客时我看的是2019年12月挂到arXiv上的版本，整体感觉有点粗糙，被会议接收的论文可能是作者更新过的版本。地址：Multi-Channel Graph Convolutional Networks

Motivation

在DiffPool模型中，每一层池化后只有一个粗粒度的图生成，这样会造成一定的信息损失，例如在社交网络中，一个节点可能有多重身份，按照不同的身份进行聚类会得到不同的结果。所以在池化的过程中，需要生成多个图来保持原图上节点具有多重身份的特点。

Preliminaries

Graph Neural Networks

GNN模型可以用下式来表示：$H_{k}=\sigma\left(\left(H_{k-1}+A H_{k-1}\right) W_{k}\right) \in \mathbb{R}^{n \times d}$Hk​=σ((Hk−1​+AHk−1​)Wk​)∈Rn×d$H_k$Hk​是$k$k次卷积后图上节点的embedding matrix，$W_{k} \in \mathbb{R}^{d \times d}$Wk​∈Rd×d是线性变换矩阵。在经过$K$K此卷积后，得到$Z=\operatorname{GNN}(A, X) \in \mathbb{R}^{n \times d}$Z=GNN(A,X)∈Rn×d。

Differentiable Pooling

这里用的公式和DiffPool论文里的一样，可以参考我之前写过的DiffPool的论文笔记：DiffPool: Hierarchical Graph Representation Learning with Differentiable Pooling

Multi-Graph Learning

在每一层的池化过程中，为了获得不同的池化结果，需要考虑不同的$A^i$Ai来生成不同的$Z^i$Zi：$Z^i=GNN(A^i, X)$Zi=GNN(Ai,X)，论文中提到 Considering graph instance i, a specific adjacency matrix $A^i$Ai is formulated to consider one class of the node characteristics and correlations.

Multi-channel Graph Convolutional Networks

Definition

definition 1: layer

A layer is composed of operations of graph convolutions and feature learning

用$l$l表示层号，如上图所示，每一层的输入是若干个图，例如第1层的输入是两个图$\left[\left\{X^{1}, A^{1}\right\},\left\{X^{2}, A^{2}\right\}\right]$[{X1,A1},{X2,A2}]，层的输出是学到的节点的embedding，例如第一层的输出是$\left[Z^{(1,1)}, \cdots, Z^{(1,4)}\right]$[Z(1,1),⋯,Z(1,4)]。

definition 2： channel

Given a specific layer, a channel represents the input graph denoted by $G^i={(X^i, A^i)}$Gi=(Xi,Ai), where i denotes the channel index.

例如上图中第0层只有一个channel：$[G^0={(X^0, A^0)}]$[G0=(X0,A0)]，第1层有两个channel：$[G^1={(X^1, A^1)},G^2={(X^2, A^2)} ]$[G1=(X1,A1),G2=(X2,A2)]

Method

Single-channel Learning Process

在第$l$l层$i$i个channel里的第$k$k步消息传递可用下式来表示：$H_{k}^{i}=\sigma\left(\left[H_{k-1}^{i}+A^{i} \cdot H_{k-1}^{i}\right] \cdot W_{k}^{(l)}\right)$Hki​=σ([Hk−1i​+Ai⋅Hk−1i​]⋅Wk(l)​)通过将每一步的$H_{k}$Hk​拼接起来得到$\mathcal{H}^{i}=\left[X^{i}, H_{k}^{i}\right],k=1,\cdot \cdot \cdot, K$Hi=[Xi,Hki​],k=1,⋅⋅⋅,K。使用第$l$l层的第$j$j个卷积核$\theta^{(l, j)} \in \mathbb{R}^{1 \times(K+1)}$θ(l,j)∈R1×(K+1)对$\mathcal{H}^{i}$Hi进行卷积操作：$Z^{(l, j)}=\phi\left(\operatorname{sum}\left(\mathcal{H}^{i} \odot \theta^{(l, j)}\right)+b\right) \in \mathbb{R}^{n_{l} \times d}$Z(l,j)=ϕ(sum(Hi⊙θ(l,j))+b)∈Rnl​×d得到第$l$l层上的第$j$j个embedding matrix。
如上图，在得到了第$0$0层的$Z^{0,1}$Z0,1和$Z^{0,2}$Z0,2后，按照DiffPool的方法可以得到$S^{0,1}$S0,1和$S^{0,2}$S0,2，进而得到第1层的两个channel$[G^1={(X^1, A^1)},G^2={(X^2, A^2)} ]$[G1=(X1,A1),G2=(X2,A2)]，同时，还能得到$G^1$G1和$G^2$G2之间的inter-channel adjacency matrix $A^{1,2}=S^{(0,1)^{T}} A^{0} S^{(0,2)} \in \mathbb{R}^{n_{1} \times n_{1}}$A1,2=S(0,1)TA0S(0,2)∈Rn1​×n1​。

Multi-channel Learning Process

当一层有多个channel时，不仅要聚合每个channel内部的信息，还要channel之间聚合信息$H_{k}^{i, c}=\sigma\left(\left[H_{k-1}^{i, c}+A^{i, c} \cdot H_{k-1}^{c}\right] \cdot W_{k}^{(l)}\right)$Hki,c​=σ([Hk−1i,c​+Ai,c⋅Hk−1c​]⋅Wk(l)​)$H_{k}^{i, c}$Hki,c​是第$i$i个channel在与第$c$c个channel进行$k$k步聚合后的embedding matrix。$A^{i,c}$Ai,c的定义在上一小节中已给出。
和single-channel类似，通过将每一步的$H$H拼接起来得到$\mathcal{H}^{i}=\left[X^{i}, H_{k}^{i}, H_{k}^{i, c}\right]$Hi=[Xi,Hki​,Hki,c​]，然后在$\mathcal{H}^{i}$Hi用$\theta^{(l, j)}$θ(l,j)进行卷积操作得到$Z$Z。这里有一点我没有看懂，不知道$H_{k}^{i, c}$Hki,c​是不是包括了该层上channeli其他所有channel做信息传递的结果。

Multi-channel Graph Convolutional Net-works

在第$l$l层上对所有的$Z^{(l, j)}$Z(l,j)做池化得到一个该层的向量表示$Y^{(l)}=\sum_{j=1}^{C_{l} T_{l}}\left(\text { GlobalPool }\left(Z^{(l, j)}\right)\right) \in \mathbb{R}^{d \times 1}$Y(l)=j=1∑Cl​Tl​​( GlobalPool (Z(l,j)))∈Rd×1$C_l$Cl​是第$l$l层的channel个数，且$T_{l} \triangleq \frac{C_{l+1}}{C_{l}}$Tl​≜Cl​Cl+1​​。
把所有的$Y^{(l)}$Y(l)拼接起来得到整张图最终的表示$Y=\oplus_{l} Y^{(l)} \in \mathbb{R}^{d \cdot L \times 1}$Y=⊕l​Y(l)∈Rd⋅L×1。