graph classification是指将由节点和边构成的图结构数据进行分类，具体的场景诸如判断由原子构成的化学分子是否具有某种性质，某种物质是否具有抗癌性，某个蛋白质分子是否属于酶这样的问题。
由于图结构数据不像图像数据一样属于欧几里得数据，传统用于图像分类的CNN方法不能够直接应用在图结构数据上。目前常见的图结构数据分类的算法都是先用图神经网络的方法处理加工节点数据，然后一次性汇聚所有的节点数据成为一个能代表整个图结构数据的向量。由于向量属于欧几里得数据，因此可以送入传统的神经网络算法进行分类。
但是这样一次性汇聚所有节点进而生成图向量的方式不能够很好的保留图的结构信息，因此分类精度不高。更好的方式是像CNN算法一样用池化操作，不断生成更为抽象、高层次的数据。这种在图结构数据上逐层进行的池化也被称作层次池化。目前层次池化分为两大块：1、以DiffPool为代表的图坍缩形池化，2、以SAGPool为代表的TopK池化。
1、所谓图坍缩池化，就是指池化时将多个节点合并成一个簇，并且将这个簇作为下一层的单独节点处理，新节点的特征值往往就是该簇所包含的节点的加权求和。每经过一次图坍缩池化，图的节点数量就会越来越少。一般而言，图坍缩池化算法的最后一个池化层会把图坍缩成仅剩一个节点，也就是一个一维向量。由于一维向量是标准的欧式数据，这样就能送入后续标准的全连接层中进行分类。
图坍缩池化
图坍缩池化，从表面上来看是很完美的，但是也存在两个亟需解决的问题：（1）、在池化时，每个节点都会以概率的形式被映射到多个簇中（即所谓的软分配机制），这会造成很大的运行内存需要。假设某层共有N个节点，池化后需要将这N个节点按一定比例k（0<k<1)投射到新的节点中，那么运行时，该层所需要的存储内存的数量级为kN^2，这在工业场景中对于有成千上万的节点的图来说，是不能够接受的。
（2）、目前主流的算法Diffpool中在进行节点池化时也是通过图卷积神经网络来对节点进行簇的分配，加之原本的节点特征也需要经过多层图卷积网络更新特征，模型中涉及了非常多的“松散”的图卷积神经网络会使得网络难以训练，往往需要一些正则化项才能使得模型训练得到收敛的状态。
2、所谓的TopK池化，就是在每次聚合节点特征后，都会通过某种算法根据节点的特征值和邻接关系给节点一个重要度得分（有时重要度得分也会作为权重与节点特征相乘），之后会选取前 K percent 重要的节点保留，而剩下的节点就会被删除，这样也能够得到不断越来越小的图。
Top-K池化
与图坍缩池化不同的是，Top-K池化不可能逐渐减少到仅剩一个节点。所以在经过多层Top-K池化后，还需要一个读出算法来读取出能代表整个graph特征的向量，最常见的作法是，对于每一层Top-K池化得到的表征，先求所有特征节点的平均值，再求所有特征节点的最大值，接着将这两个一维向量拼接成一个一维向量，(之所以要这样做，是因为这样能够是最终代表整个graph的向量中能保留更多的的结构信息。）最后，将所有层得到的向量进行求和，综合所有层的表征，便可以得到最终更具表达能力的一维图向量。接下去的操作就和图坍缩池化的后续操作一样，将这个一维图向量送入普通的全连接网络就可以进行最终的图分类了。
Top-K池化虽然不像一般的图坍缩池化一样需要很大的内存，但是其不断丢弃节点的过程难免会丢失很多信息。在我看来，Top-K的池化操作的读出算法其实也是全局池化的操作——即通过求平均和最大值的方式，将复杂的拓扑数据直接压缩成一维向量，即便最后将多个层池化后结果的加和作为最终的图向量，确实可以丰富图向量的信息，其不可能做到像图坍缩池化一样保留全面的节点信息。在我看来，Top-K池化的关键在于怎样保证选取的节点能够更好地保留图结构中的关键信息，所以对于每个节点的重要程度评判机制至关重要。
网友评论