CensNet:Convolution with Edge-Node Switching in Graph Neural Networks 边和节点切换卷积的图神经网络 IJCAI

文章目录

• 1 相关介绍
• 1.1 背景介绍
• 1.2 结合节点和边特征的Embeddings方法
• 1.3 Contributions
• 2 符号定义
• 3 交换节点和边的卷积
• 3.1 传播规则
• 节点层传播规则
• 边层传播规则
• 3.2 和任务相关的损失函数
• 3.3 训练算法
• 4 实验
• 4.1 benchmark data sets
• Tox21
• Lipophilicity
• Cora, Citeseer, and PubMed
• 4.2 Experimental Settings
• 多任务图分类
• 图回归
• 半监督节点分类
• 实验设置
• 4.3 实验结果
• 多任务图分类
• 图回归
• 半监督节点分类
• 5 小结

论文：CensNet：Convolution with Edge-Node Switching in Graph Neural Networks
边和节点切换卷积的图神经网络CensNet

作者：Xiaodong Jiang,Pengsheng Ji,Sheng Li 美国乔治亚大学计算机科学系

来源：IJCAI 2019

论文链接：https://www.ijcai.org/proceedings/2019/0369.pdf

github链接：未开源代码

此文提出了边和节点角色相互切换进行卷积的图神经网络CensNet，用于同时具有节点特征和边特征的图结构数据的半监督分类和回归问题。CensNet是一个graph embedding框架，它将节点和边嵌入到一个潜在的特征空间中。利用原无向图的“line graph”，CensNet交换节点和边的作用，提出了两种新的图卷积运算来进行特征传播。实验中在学术引文网络和分子化学图上的实验结果表明，CensNet已经达到了state-of-the-art的性能。

1 相关介绍

1.1 背景介绍

在现实中，图通常同时包含节点特征和边特征。在社交网络中，节点特征可能是人口统计信息或用户行为，而边特征可能是关系类型或友谊年限。在引文网络中，节点特征可以是论文的文档级embedding，边特征可以是两篇文章的共同关键词或共同作者。在化学领域中，每个化合物都可以看作是一个图，其中原子是节点，化学键的性质是边特征。
文中从以下两个方面论证了联合学习节点embedding和边embedding的动机。

• 首先，边和节点总是提供互补的特征信息，这对图的embedding是有帮助的。
• 其次，学习边embedding对于边相关的任务(如边分类和回归)是必不可少的。

受到图论中的Line Graph的启发，文中提出了一种新的将边和节点交换的卷积网络(CensNet)，用于学习节点和边的embedding。令$G$G定义为一个无向图，则很容易得到节点的邻接矩阵,其Line Graph$L (G)$L(G)可以用于表示图$G$G的边之间的邻接关系。在CensNet框架中，可以切换节点和边的角色，CensNet对输入图$G$G和对应的Line Graph进行图卷积运算。CensNet在$G$G和Line Graph$L (G)$L(G)上使用两个前向传递的特征传播规则，交替更新节点和边的embedding。同时，设计了一种处理大规模图数据的CensNet mini-batch训练算法。

1.2 结合节点和边特征的Embeddings方法

在图卷积中，能够同时结合节点和边特征的模型并不多见，可分为两类。
第一种方法是在边特征上为每个关系或维定义不同的权值矩阵，并将不同关系的传播累加起来。（ Modeling relational data with graph convolutional networks. In ESWC, 2018）使用以下规则进行向前传递更新：

$h_{i}^{l+1}=\sigma\left(\sum_{r \in \mathcal{R}} \sum_{j \in \mathcal{N}_{i}^{r}} \frac{1}{c_{i, r}} W_{r}^{(l)} h_{j}^{(l)}+W_{0}^{(l)} h_{i}^{(l)}\right)$hil+1​=σ⎝⎛​r∈R∑​j∈Nir​∑​ci,r​1​Wr(l)​hj(l)​+W0(l)​hi(l)​⎠⎞​

• 关系$r \in \mathcal{R}$r∈R都有对应的权重矩阵$W_{r}$Wr​

这种简单的聚合虽然计算效率很高，但却无法捕捉到不同关系之间的依赖关系以及节点与边的特征之间的相互作用。

第二种方法是通过为邻域内的不同节点指定不同的权值，将注意力机制添加到图卷积中。 MonNet和GAT都是这种思想。

这两种方法都只能处理离散的或低维的边的特征。

与现有的图卷积和embedding方法不同的是，文中提出的CensNet框架与图卷积的选择无关，但是目前只实现了一种基于谱的方法[Kipf和Welling, 2017]。此外，CensNet中节点和边的co-embedding方式受到line graph的启发，并受相互加强的特征传播规则的驱动，可以处理离散或连续的节点或边的特征。

1.3 Contributions

• Co-embedding of nodes and edges。CensNet利用图结构和节点、边的特征，将节点和边同时嵌入到潜在特征空间中。此外，由于可选的更新规则，节点embedding和边embedding可以相互加强。

• Convolution on line graph。将节点和边的作用交换，设计了输入图和对应的line graph的卷积运算。

• Diverse learning tasks on graphs，多样的图学习任务。将CensNet应用于一些基于图的学习任务，包括多任务图分类、图回归和半监督节点分类。

• Extensive evaluations on benchmark data sets，对benchmark数据集的广泛评估。对引文网络Cora, Citeseer和PubMed和Quantum Chemistry数据集Tox21和Lipophilicity的大量实验表明，CensNet已经达到或匹配了最先进的性能。

2 符号定义

在下面给出了具有节点和边特征的图的数学符号：

• 无向图$G$G的节点集为$V$V，边集$E$E
• $E \subseteq V \times V$E⊆V×V，$N_{v}=|V|$Nv​=∣V∣和$N_{e}=|E|$Ne​=∣E∣分别表示节点和边的数量
• $A_{v} \in \mathbb{R}^{N_{v} \times N_{v}}$Av​∈RNv​×Nv​表示无向图$G$G的节点的的邻接矩阵，是一个没有权重的二进制矩阵
• $X \in \mathbb{R}^{N_{v} \times d_{v}}$X∈RNv​×dv​定义为节点的特征矩阵
• $A_{e} \in \mathbb{R}^{N_{e} \times N_{e}}$Ae​∈RNe​×Ne​表示无向图$G$G的边的的邻接矩阵，或者$L (G)$L(G)的节点的邻接矩阵，也是一个没有权重的二进制矩阵
• $Z \in \mathbb{R}^{N_{e} \times d_{e}}$Z∈RNe​×de​定义为边的特征矩阵
• $H_{v}^{(l)}$Hv(l)​表示第$l$l层节点卷积的隐含层，其中$H_{v}^{(0)}=X$Hv(0)​=X
• $H_{e}^{(l)}$He(l)​表示第$l$l层边卷积的隐含层，其中$H_{e}^{(0)}=Z$He(0)​=Z

3 交换节点和边的卷积

CensNet框架由两类层组成:节点层和边层。图1展示了用于半监督节点分类的CensNet体系结构。输入层由节点邻接矩阵和相应的节点特征以及其line graph对应的部分（边邻接矩阵和边特征）组成。三种颜色的边(即图中的z1、z2、z3)转换为三个line graph节点(正方形)。

• 图1：使用边和节点交换卷积的CensNet体系结构图
• 橘黄色的部分代表在节点特征矩阵和邻接矩阵上的卷积
• 浅绿色代表在对应的line graph上的卷积
• 两种类型的层作为一个组合：Node层，用前一层的node embedding和edge embedding更新node embedding；Edge层，用前一层的node embedding和edge embedding更新edge embedding

根据具体任务和标签的可用性，CensNet对节点或边embedding矩阵采用不同类型的**函数。例如，在图节点半分类任务中(如引文网络中的论文分类)，有每个节点的标签，因此可以对最后一层的节点embedding矩阵使用sigmoid函数。对于图分类或回归任务(例如，分子性质预测)，可以应用 average pooling层来重塑节点embedding并获得图级embedding。

CensNet框架是一个交互式图的高级抽象，同时结合了节点和边的embedding。CensNet框架是一个不一定要使用卷积的近似谱图核。因此，其他新技术，如Lanczos网络中的核（Lanczosnet: Multi-scale deep graph convolutional networks，ICLR 2019），也可以应用到CensNet框架中。

3.1 传播规则

CensNet在分层传播中使用了近似谱图卷积。定义了带自环的归一化(拉普拉斯化)节点邻接矩阵为：

$\tilde{A}_{v}=D_{v}^{-\frac{1}{2}}\left(A_{v}+I_{N_{v}}\right) D_{v}^{-\frac{1}{2}}$A~v​=Dv−21​​(Av​+INv​​)Dv−21​​

• $D_v$Dv​是$A_{v}+I_{N_{v}}$Av​+INv​​矩阵的度矩阵

节点层传播规则

定义第$(l + 1)$(l+1)层节点特征的逐层传播规则为

$H_{v}^{(l+1)}=\sigma\left(T \Phi\left(H_{e}^{(l)} P_{e}\right) T^{T} \odot \tilde{A}_{v} H_{v}^{(l)} W_{v}\right)$Hv(l+1)​=σ(TΦ(He(l)​Pe​)TT⊙A~v​Hv(l)​Wv​)

• $T \in \mathbb{R}^{N_{v} \times N_{e}}$T∈RNv​×Ne​是二进制转换矩阵，其中$T_{i,m}$Ti,m​表示边$m$m是否连接节点$i$i
• 已知每条边由两个节点组成，矩阵$T$T的每一列有两个元素为1，其他元素为0
• $P_e$Pe​是一个$d_e$de​维向量，定义为边特征向量的可学习权值
• $\Phi$Φ表示对角化操作,表示把一个一维向量转化成一个稀疏矩阵的对角线
• $\odot$⊙是Hadamard积
• 该规则可以看作将$T \Phi\left(H_{e}^{(l)} P_{e}\right) T^{T}$TΦ(He(l)​Pe​)TT对应的元素映射到规范化节点邻接矩阵，$T \Phi\left(H_{e}^{(l)} P_{e}\right) T^{T} \odot \tilde{A}_{v}$TΦ(He(l)​Pe​)TT⊙A~v​通过使用来自line graph对应部分进行融合了的节点特征矩阵
• 如果没有实际边，line graph图的影响为零，因此保持了原始图的稀疏性，带来了显著的计算优势。

边层传播规则

类似地，定义归一化(拉普拉斯化)边邻接矩阵为：

$\tilde{A}_{e}=D_{e}^{-\frac{1}{2}}\left(A_{e}+I_{N_{e}}\right) D_{e}^{-\frac{1}{2}}$A~e​=De−21​​(Ae​+INe​​)De−21​​

• $D_e$De​是$A_{v}+I_{N_{v}}$Av​+INv​​矩阵的度矩阵

定义边特征的传播规则如下:

$H_{e}^{(l+1)}=\sigma\left(T^{T} \Phi\left(H_{v}^{(l)} P_{v}\right) T \odot A_{e} H_{e}^{(l)} W_{e}\right)$He(l+1)​=σ(TTΦ(Hv(l)​Pv​)T⊙Ae​He(l)​We​)

• $T$T矩阵与点特征传播规则相同，$P_v$Pv​表示节点的可学习权值。在返回的结果中，使用节点特征和邻接矩阵来改进边的embedding。$T$T和$P_v$Pv​使得节点和边上的信号得以结合；节点和边embedding交替更新。

3.2 和任务相关的损失函数

输出层的设计以及损失函数都是与任务相关的。

• 对于节点或边分类任务，可以将sigmoid函数应用于最终隐藏的节点层或边层；对于图分类任务，
• 需要额外的 pooling操作，将节点级 embedding映射到图级表示。

对于半监督节点分类任务，损失函数定义为：

$\mathcal{L}(\Theta)=-\sum_{l \in Y_{L}} \sum_{f=1}^{F} Y_{l f} \log M_{l f}$L(Θ)=−l∈YL​∑​f=1∑F​Ylf​logMlf​

• $Y_{L}$YL​是有标签的节点集合
• $M$M为最后一层节点输出的softmax结果，假设最终节点特征映射为$F$F维
• $\left(W_{v}, W_{e}, P_{v}, P_{e}\right)$(Wv​,We​,Pv​,Pe​)是参数集

对于多任务图分类，可以对每个目标的交叉熵求和。

对于返回为连续值的回归任务，使用$l^p$lp正则化均方误差(MSE)定义以下损失函数：

$\mathcal{L}(\Theta)=\sum_{l \in Y_{L}} \sum_{f=1}^{F}\left\|Y_{l f}-\hat{Y}_{l f}\right\|_{2}^{2}+\lambda\|\Theta\|_{p}$L(Θ)=l∈YL​∑​f=1∑F​∥∥∥​Ylf​−Y^lf​∥∥∥​22​+λ∥Θ∥p​

• $\hat{Y}$Y^为最后的节点隐含层的预测结果。利用正则化项来控制模型的复杂度，避免过拟合。

3.3 训练算法

算法1中展示了半监督节点分类算法，它使用了节点层和边层定义的分层传播规则。使用Adam或SGD等优化算法来处理交叉熵损失函数。当输入数据无法装入GPU内存时，通常首选 mini-batc策略。

因此，在算法2中，还针对标记节点较少的节点分类任务，设计了一个针对大图的mini-batc训练算法。关键思想是对训练、验证和测试集中的节点按比例取样，以构建batch。实验结果表明，这种训练策略可以使训练的的性能可与整个图进行训练相比。

4 实验

4.1 benchmark data sets

Tox21

“21世纪毒理学”创建了一个测量化合物毒性的公共数据库，该数据库已在2014年的Tox21数据挑战中被使用。该数据集包含7831种化合物和药物的定量毒性测量。复合结构(SMILE格式)通常表示为原子为节点、键为边的图。化学键有55种特征，每个原子有25种特征。每种化合物都与12个二元标签相关联，代表12个不同毒理学实验的结果(活性/非活性)。这些标签中约有20%的缺失值，在计算损失时排除了这些观察值，但仍将其保留在训练过程中。

Lipophilicity

亲脂性（Lipophilicity）是药物分子的一个重要特征，它同时影响膜的通透性和溶解度。该数据集提供了4,200个化合物的辛醇/水分配系数(logD, pH7.4)的实验结果。边上有34个特征(键)，节点上有25个特征(原子)。

Cora, Citeseer, and PubMed

这三个数据集是半监督节点分类任务的benchmarks，许多图卷积网络模型已经对其进行了分析。

• Cora有2708个节点（论文）和5429个边（引文链接），每个节点有1433个tf-idf特征,论文分为7个不同的研究领域。
• Citeeser有3327个节点，4732个边，3703个节点特征，论文分为6个研究领域。
• PubMed包含19717个节点和44338个边，每个节点有500个特征，论文分为3类。
• 这些引用图并不是CensNet适合的benchmarks，因为没有可用的边的特征。文中使用人工标记的边特征展示了CensNet有竞争力的性能。这种边特征可以是成对节点特征的相关性或余弦相似性。

对于三个引文图，创建了两个简单的边的特征:(1)对应两个节点特征之间的余弦相似性，(2)表示边的方向的二维向量。如果论文A引用了论文B，那么向量就是[1,0]，否则就是[0,1]。遵循（Lanczosnet: Multi-scale deep graph convolutional networks，ICLR 2019）中的分裂策略，并对不同的标签率进行了实验。对于训练集，Cora使用标签数据分别为3%、1%和0.5、Citeseer使用标签数据分别为1%、0.5%和0.3%、PubMed使用标签数据分别为0.1%、0.05%和0.03%来进行实验，评估CensNet和 baselines。对于三个数据集，随机选择50%进行验证，其余50%进行测试。

4.2 Experimental Settings

多任务图分类

• 评估了CensNet在4种数据分割场景下对Tox21数据集的性能。
• [Moleculenet: a
  benchmark for molecular machine learning，2018]对Tox21数据进行了全面的模型比较
• 目前state-of-the-art的方法是GCN [ICLR,2017]
• 实现了minibatch 的GCN和其他两个经典的分类算法，逻辑回归和随机森林作为三个baseline
• 比较所有比较方法在验证集和测试集的AUC值

图回归

• 回归任务类似于图分类，但使用不同的损失函数和性能度量
• 实验中使用与Tox21相同的数据分割策略
• baseline算法有GCN、线性回归和随机森林回归
• 比较所有比较方法在验证集和测试集的均方根误差(RMSE)

半监督节点分类

• 这是图学习和统计学习社区中的一个经典任务，最广泛使用的benchmark数据集是三个引文网络，Cora、Citeseer和PubMed
• 采用的是小样本学习策略（few-shot learning strategy），即，只在训练集中保留少量带标签的数据，而将其余的数据分开进行验证和测试
• 在使用不同百分比的标记数据时，将CensNet与七个有代表性的图卷积网络进行了比较。七个baseline包括ChebyNet，GCN，GraphSAGE，GAT，LNet，AdaLNet，CensNet。
• LNet和AdaLet是完成这项任务的目前的state-of-the-art的方法，将对这两种方法与提出的CensNet进行全面比较。

实验设置

• 所有实验都在Azure Linux VM上进行(CPU: Intel® Xeon® CPU E5-2690 v3, GPU: NVIDIA Tesla K80)
• 在PyTorch [Paszke et al.， 2017] v1.0.0中实现了所有的图数据卷积网络算法。对于其他经典算法(随机森林、线性回归、逻辑回归)，使用Python包Scikit-learn中的实现。对于图卷积模型，没有实施任何复杂的fine-tuning策略，而是尝试了学习率{0.01,0.005,0.001,0.0005}，batch大小{16,32,64,128,256}，epoch数{200,300,500,1000}等不同的设置
• 实现了三层架构(节点层-边层-节点层)，每层有32个单元
• 对每种方法报告最好的结果
• 对于基于树的方法，使用交叉验证来调整参数;对于线性和逻辑回归模型，在不使用变量选择的情况下运行算法

4.3 实验结果

多任务图分类

表1显示了验证和测试集上的AUC值，有四种不同的训练标签率。重复所有实验三次，并比较AUC值和均方根误差(RMSE)。

图2(a)显示了200个epoch中验证集AUC的变化。GCN曲线在20个epoch内趋于平缓，而CensNet可以持续改善。同时，训练集较小的CensNet效果比使用训练集更大的GCN更好。

图回归

重复所有实验三次，比较均方根误差(RMSE)。

从表1可以总结出以下结论:

• 这4种算法都是在训练集较大的情况下获得了较好的性能，而随机森林和logistic回归只能获得有限的性能提升
• 与传统方法相比，GCN和CensNet都有较大的性能提升，说明在分子回归任务中，图结构是不可忽视的
• CensNet将GCN在RMSE中的性能提高了5%-15%，这意味着考虑分子中的边特征可以提高节点embedding的质量，从而为学习过程带来显著的好处

从图2(b)可以看出，经过50-75个epoch后，CensNet处于领先地位，而GCN的曲线仍然保持平缓。

半监督节点分类

• 遵循（Lanczosnet: Multi-scale deep graph convolutional networks，ICLR 2019）中相同的实验设置，并重新使用benchmark测试结果作为baselines。
• 在所有的实验中，观察到所有的图卷积网络使用低标签率训练集都存在显著的过拟合问题。
• CensNet方法在9个实验中的4个实验中都获得了最好的精度，其次是LNet和AdaLNet——这是完成这项任务的state-of-the-art算法。
• 有人可能认为，将边中信息添加到算法中与baseline比较是不公平的;然而，新创建的边的特征都来自benchmark数据;因此没有额外的信号被引入。
• 经典的GCN [Kipf, 2017]在大多数情况下也取得了具有竞争力的结果，这与[ Pitfalls of graph neural network evaluation， 2018]的大量实验的结论相一致。

5 小结

目前作者正在探索其他的graph kernels和更有效的训练算法，以将深度图学习扩展到更大和更复杂的数据集。