[论文阅读] | Semi-supervised classification with GCN(侧重Cora数据集)

写在前面

  本文比较适合基本了解GCN中图卷积运算的读者，即$H^{(l+1)}=\sigma(\tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2} H^l W^l)$H(l+1)=σ(D~−1/2A~D~−1/2HlWl)，这个公式的出处为论文[1]。因为我是在阅读其他论文(采用的GCN与[1]相同)的时候发现，上述公式对应的图卷积运算只适用于处理无向图，但实验使用的引文网络数据集Cora、Citeseer和Pubmed理论上来说对应的是有向图。于是感到十分疑惑，便查看了论文[1]，发现作者直接将Cora一类的数据集当做无向图处理，并建立对称的邻接矩阵；出于好奇，查找了Cora数据集的来源、组织格式以及如何将其处理成有向图。

---

1 GCN简介

1.1 图(Graph)

图通常由图中的顶点、边以及边的权值组成，即$G = (V,E,W)$G=(V,E,W)。其中，

• 顶点集合：$V = (v_1, v_2,...v_n), n=|V|$V=(v1​,v2​,...vn​),n=∣V∣ 表示该图包含顶点$v_1、v_2$v1​、v2​等共计$n$n个顶点；
• 边集合：$E=(e_1,e_2,...e_m)$E=(e1​,e2​,...em​)，表示该图共含有$m$m条边；
• 权值集合：一种比较简单的定义方式为，针对图中任意两个顶点$v_i$vi​和$v_j$vj​，如果它们两个之间有一条边，则对应的权值$w_{ij}$wij​为1，否则为0,即：
  $w_{i,j}= \left\{\begin{matrix} 0&, v_i 和 v_j 没有边 \\ 1&, v_i 和 v_j 存在边 \\ \end{matrix}\right.$wi,j​={01​,vi​和vj​没有边,vi​和vj​存在边​
  图中所有顶点之间的权值组成权值集合$W$W。

1.2 图对应的矩阵

• 邻接矩阵$A$A：$n$n行$n$n列，第$i$i行第$j$j列为$w_{ij}$wij​，对角线元素为0
  $A= \begin{bmatrix} 0 & w_{1,2} & w_{1,3} & ... & w_{1,n}\\ w_{2,1}& 0 & w_{2,3} & ... & w_{2,n}\\ ... & ... & ...& ... & ... \\ w_{n,1} & w_{n,2} & w_{n,3} & ... & 0 \\ \end{bmatrix}$A=⎣⎢⎢⎡​0w2,1​...wn,1​​w1,2​0...wn,2​​w1,3​w2,3​...wn,3​​............​w1,n​w2,n​...0​⎦⎥⎥⎤​

• 度矩阵$D$D： $n$n行$n$n列的对角矩阵，对角线上元素为顶点的度$d_i = \sum_{j=1}^n w_{ij}$di​=∑j=1n​wij​
  $D= \begin{bmatrix} d_1 & 0 & ... & 0 \\ 0 & d_2 & ... & 0 \\ ... & ... & ...& ... \\ 0 & 0 & ...& d_n\\ \end{bmatrix}$D=⎣⎢⎢⎡​d1​0...0​0d2​...0​............​00...dn​​⎦⎥⎥⎤​

• 拉普拉斯矩阵：$L=D-A$L=D−A
  $l_{i,j}= \left\{\begin{matrix} d_i,&i=j \\ -1,&i\neq j且w_{ij}=1 \\ 0,&i\neq j且w_{ij}=0\\ \end{matrix}\right.$li,j​=⎩⎨⎧​di​,−1,0,​i=ji​=j且wij​=1i​=j且wij​=0​
  如果图$G$G为无向图，即$A_{ij}=A_{ji}$Aij​=Aji​，则此时的邻接矩阵、度矩阵和拉普拉斯矩阵均为对称矩阵。

1.3 拉普拉斯矩阵$L$L的性质

1. 半正定矩阵：所有特征值大于等于0
2. 对称矩阵：$n$n阶$L$L矩阵有$n$n个线性无关的特征向量，而且不同特征值对应的特征向量正交。这个性质(无向图对应的拉普拉斯矩阵对称)使得拉普拉斯矩阵可以进行特征分解，进而在特征分解的基础上推导出谱域图卷积公式。

1.4 GCN结构

GCN的基本结构如上图所示，与CNN整体框架有些相似，包括输入层、中间多层隐藏层(图卷积层)和输出层。

** 输入层：图的邻接矩阵$A$A和特征矩阵$X$X，其中特征矩阵$X$X由每个顶点对应的特征向量组成，例如常用的词袋模型、embedding等。

** 图卷积层：根据前一层计算出的特征和参数矩阵计算下一层的特征,例如第$l$l层的计算
$H^{(l+1)}=\sigma(\tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2} H^l W^l) \ \quad(1)$H(l+1)=σ(D~−1/2A~D~−1/2HlWl) (1)
   其中 $\tilde{A} = A+I$A~=A+I, $\tilde{D} = \sum\tilde{A}$D~=∑A~, $W^{l}$Wl为参数矩阵，$H^{l}$Hl为特征矩阵。

** 输出层：得到经过多层图卷积运算后计算出的特征，根据输出特征可以进行后续顶点分类等任务。

---

2 Cora数据集简介

  Cora是研究论文之间引用关系的数据集，包含2708篇论文和5249条引用，这2708篇论文对应7个类别（Case_Based、Genetic_Algorithms、Neural_Networks、Probabilistic_Methods、Reinforcement_Learning、Rule_Learning、Theory），每篇论文使用维度为1433的词袋模型表示特征。将其组织成图，则图中的每一个顶点对应一篇论文，图中的边则表示论文之间的引用关系。

2.1 原始Cora组织形式

数据集下载链接：link
下载解压后的Cora数据集对应两个文件：

1."cora.content"文件

包含2708条数据，对应2708篇论文
每条数据的格式为：<paper_id> <word_attributes>+ <class_label>
   <paper_id>：论文ID
   <word_attributes>：使用词袋模型(字典长度为1433)表示的特征向量，由0和1组成
   <class_label>：论文所属的类别标签，如Genetic_Algorithms

** 注意，Cora数据集其实是给出了所有2708个样本的标签信息的，有的论文中描述划分的测试集为“unlabled”其实是为了验证其设计的半监督算法而设计的。

2. "cora.cites"文件

描述论文之间的引用关系，包含5249条数据；
每条的组织格式为< ID of cited paper> < ID of citing paper>，前一项表示被引用论文的ID。
例如35,1033 表示ID为1033的论文引用了ID为35的论文，在建立的图中，有一条边从1033指向35。

由此可见，Cora等一类的引文网络建立的图理论上是有向图。这就回到了我初始的疑问，论文[1]建立起的GCN网络肯定是不能处理有向图的，因为有向图对应的拉普拉斯矩阵不是对称的，就不能进行特征分解，也推导不出公式(1)对应的图卷积运算。

不过论文[1]明确表示

We treat the citation links as (undirected) edges and construct abinary,symmetric adjacency matrix A

也就是说，将引文网络对应的图看做是无向图。但是它采用的数据集格式并非本文2.1中展示的，而是下面2.2中所示的组织格式。

2.2 Cora数据集另一种组织格式

下载链接：link

这种组织格式是在论文[2]中定义的。论文[2]发表于2016年，研究一种基于Graph embedding的半监督学习框架。在论文[2]中，作者采用了Cora数据集。

上图来自于原文，从中我们可以看出：

1.关于有向图和无向图

  如果论文$i$i引用了$j$j，则设置$a_{ij}=a_{ji}=1$aij​=aji​=1，这样建起其的图必然为无向图，对应的邻接矩阵为对称矩阵。

2.关于数据集划分

Cora数据含有2708个样本，划分为训练集和测试集

• 训练集：140个样本，每类随机选择20个样本，一共包含7个类别，因此训练集含有140个样本；
• 测试集：随机选择了1000个样本
• 无标注样本：1708个样本(这里说的无标注是考虑算法的需求，不使用对应的标签)

因此形成的数据集文件如下：

• ind.cora.x： $140 ×1433$140×1433 ，140个训练样本的对应的特征向量；
• ind.cora.y：$140 ×7$140×7，训练样本的one-hot编码向量；
• ind.cora.allx：$1708 ×1433$1708×1433，除了随机选择的1000个测试样本，其余的有标注和未标注样本对应的特征向量；
• ind.cora.ally：$1708 ×7$1708×7，allx样本的one-hot编码向量；
• ind.cora.tx：$1000 ×1433$1000×1433，1000个测试样本的对应的特征向量；
• ind.cora.ty：$1000 ×7$1000×7，测试样本的one-hot编码向量；
• ind.cora.graph：格式为{index: [index_of_neighbor_nodes]}的字典，字典的key表示引用论文的下标，对应的values表示被引用的论文下标。graph中的引用关系已经变成了对称的形式，如下图，1引用了2，同时2引用了1。
  
  

3 总结

  论文[2]之后的很多论文都沿用了论文[2]中的数据集组织和划分形式，将理论上为有向图的引文网络数据集当做无向图处理。当然，现在已经有专门用于有向图运算的GCN了，不过在2017年论文[1]提出使用一阶切比雪夫多项式简化之前k阶切比雪夫多项式定义的图卷积运算时，推导出的公式(1)对应的图卷积还只能用于无向图。

参考文献

[1] Kipf, T. N., & Welling, M. (2016). Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907. [2] Yang, Z., Cohen, W., & Salakhudinov, R. (2016, June). Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning (pp. 40-48).