计算机视觉与模式识别会议 CVPR 2020 将于 6 月 14-19 日在美国西雅图举行。不久之前，大会官方论文结果公布，在 6656 篇有效投稿中，最终有 1470 篇论文被接收，录取率约为 22%。本文对北大被接收的一篇论文进行了解读。该文研究图神经网络中的无监督图表征学习，在三维点云的分类/分割任务上取得了非常接近全监督学习方法的性能的突破性进展。
- 论文链接：https://arxiv.org/pdf/1911.08142.pdf
- 开源代码：https://github.com/gyshgx868/graph-ter
一、引言
图（Graph）是不规则数据/非欧几里得数据（例如 3D 点云、社交网络、引文网络、脑网络等）的一种自然而有效的表征。由于图的强大表现力，图数据的机器学习越来越受到重视，如近年来提出的图卷积神经网络（Graph Convolutional Neural Network, GCNN）。不过，现有的 GCNN 模型大多以监督或半监督的方式进行训练，这需要大量的标记样本才能学习到有效的特征表示。由于标记成本较高（特别是在大规模的图上），现有方法难以进行广泛应用。因此，我们需要以无监督的方式来学习图特征表示，以便适应更多图的学习任务。
代表性的无监督学习方法包括自动编码器（Auto-Encoders，AEs）和生成对抗网络（Generative Adversarial Networks，GANs）。基于 AE 和 GAN，许多方法通过学习「变换共变表征」（Transformation Equivariant Representations，TERs）来进一步提高无监督特征学习的质量。在 TER 学习中，通常假定在数据上施加变换会引起数据特征空间的共变，因此能够从变换前的和变换后的数据的特征表示中重构施加在数据上的变换，以此来学习数据的特征表示，如 Zhang 等人提出的 AET [1]。然而，AET 着重于对图像进行变换共变表征进行学习，难以直接拓展到非欧几里得空间的图数据。
因此，在本文中作者提出在自动编码器框架下，以无监督的方式编码图中节点的变换方式来实现「图变换共变表征」（Graph Transformation Equivariant Representations，GraphTER）学习，如图 1 所示。作者的方法的创新性体现在两个方面：1）作者们定义图信号变换，并提出了一种基于图的自动编码器网络。该网络对原始图和变换后的图进行编码，以便可以从这两种特征表示中重建出图信号上的变换；2）相比于将全局空间变换应用于整个图像的 AET，作者对图上的节点进行逐点变换，使得每个节点可以具有不同的变换。因此，通过借助节点邻居信息来解码这些节点的变换能够揭示节点所在邻域的图结构，进而学习各个节点的特征表示。这些特征表示不仅能够捕获节点周围的局部图结构，而且通过在每个训练迭代中随机采样部分节点进行变换来揭示图的全局信息。
图 1：作者提出的无监督图特征学习方法 GraphTER。编码器 E 分别对原始图信号 X 和邻接矩阵 A，以及变换之后的图信号 X ̃和邻接矩阵 A ̃进行特征学习。解码器 D 从这两种特征表示预测节点变换，从而使得自动编码器能够学习到图的本质特征。
二、图信号变换
与传统的欧几里得数据（例如图像等）不同，图信号是不规则的，因此难以定义其变换。作者将图信号变换定义为对节点上信号的滤波，如对每个节点独立滤波（平移、旋转等），或考虑邻域信息对节点进行低通/高通滤波。
假设从整个变换分布 T_g 中采样图信号变换 t，t~T_g。将该变换应用于从数据分布 X_g 中采样的图信号 X 上，便得到了变换后的图信号：X ̃=t(X)
变换 t 将应用于每个节点，与 t 相关联的每个节点信号的变换可以彼此不同。例如，对于平移变换 t，我们可以将不同的平移量应用于不同的节点。如果每个节点的变换是相同（不同）的，可以将该变换称为各向同性（各向异性）的。与变换后的图信号 X ̃关联的的邻接矩阵为
。
其中 f(⋅) 是线性或非线性函数，应用于每对节点以获得其相似性。例如，一种广泛采用的 f(⋅) 是根据节点特征构建 k 近邻（k-nearest-neighbor，k-NN）图。这样就得到了变换后的图，因为 A ̃中边的权重也间接地通过 t 进行变换。
在本文中，作者们专注于逐节点图信号变换，即每个节点各向同性或各向异性地具有自己的变换。这种做法有两个优点：
（1）通过对逐节点应用变换，可以在图中采样部分节点来研究在各种变换下图的不同部分的特征；
（2）通过解码节点的变换，能够学习单个节点的特征表示。此外，这些节点的特征表示不仅能够捕获局部图结构信息，而且在每个训练迭代中随机地采样部分节点施加变换，随着训练迭代的增加还能够学习到全局的图结构信息。
三、方法
给定一组包含 N 个节点的图信号 X={x_1,x_2,…,x_N }^⊤，在每个训练迭代中, 遵循样本分布 S_g，随机地从图中的所有节点全局或局部地采样节点子集 S，即 S~S_g。全局采样是指在全局范围内对整个图的所有节点进行随机采样，而局部采样则仅限于图中的一组局部节点。
图 2：在 3D 点云上展示不同的采样方法（全局或局部）和逐节点平移方法（各向同性或各向异性），红色和蓝色点分别表示经过变换的点和原始点。为了能够清晰地展示，作者们将整个机翼作为局部采样的点集。
然后，作者对 S 中的每个节点 x_i 施加节点变换 t_i（各向同性或各向异性），如图 2 所示。与此同时，与变换后的图信号关联的邻接矩阵 A ̃也在变换 t 下与 A 共变。如图 3 所示，作者构造了一个 k-NN 图，在对采样的节点进行变换之后，邻接矩阵 A 中表示的连通信息也会随之改变。
图 3：进行逐节点变换前后的 k-NN 图示例。首先以黄色节点为中心构建 k-NN（k=5）图（其他连接略去）。然后，作者们在部分蓝色节点上进行平移变换，从而改变了黄色节点周围的图拓扑结构。
具体来说，给定图信号和与其对应的邻接矩阵 (X,A)，以及经过 t 变换的图信号和邻接矩阵 (X ̃,A ̃ )，如果函数 E(⋅) 满足下述等式，那么可以称则函数 E(⋅) 是满足「变换共变性」的：
其中ρ(t) 表示在特征空间中 t 的同态变换。
作者设计了自动编码器网络来学习变换共变表征：编码器 E(⋅) 对图中节点的特征表示进行编码，而解码器 D(⋅) 从编码器学习到的原始和变换后的图信号的特征表示中估算逐节点变换 t ̂。
为了估计逐节点变换 t ̂，作者应用损失函数 l(t,t ̂ ) 来最小化逐节点变换 t 和估计的变换 t ̂之间的差异。这时，整个自动编码器网络便可以通过最小化下面的损失函数进行训练：
在上述公式中，从解码器估计的逐节点变换表示为：
因此，作者通过反向传播该损失来迭代地更新编码器 E 和解码器 D 中的参数。
为了估计这些逐节点变换，作者设计了图卷积自动编码器网络，如图 4 所示。作者选择一种图卷积方法 EdgeConv [2] 作为自动编码器网络的基本构建模块，该图卷积通过聚合每个节点和其周围邻居的特征来学习节点的特征表示。
图 4：GraphTER 自动编码器网络结构。在无监督特征学习阶段，特征编码器和变换解码器将在无标签的样本上进行训练。在评估阶段，作者提取编码器的前几个 EdgeConv 模块，冻结其权重作为特征提取器，并使用标记的样本训练线性分类器完成特征的分类。
三、实验结果
作者以 3D 点云分类任务和分割任务为例来验证提出的 GraphTER 模型。
1. 3D 点云分类
作者在 ModelNet40 数据集上来验证 GraphTER 模型。在该数据集中，作者将 3D 点云中的点视为图上的节点，3D 点坐标视为图信号，并通过点坐标间的欧氏距离在点云上建立 k-NN 图（k=20）。
表 1 展示了 3D 点云的分类结果，在实验中作者选取 25% 的节点应用各向同性的逐节点剪切（Shear）变换。作者与无监督方法和有监督方法进行比较。GraphTER 模型在 ModelNet40 数据集上达到了 92.0％的分类准确率，这优于最新的无监督方法。大多数的无监督模型都结合了 GAN 和 AED 的思想，例如 FoldingNet，MAP-VAE 和 L2G-AE。结果表明，GraphTER 模型相比于这些方法都有显著的提高，表明了 GraphTER 模型优于 GAN 和 AED。此外，无监督的 GraphTER 模型还可以达到与全监督模型结果相当的分类准确率，这极大地缩小了无监督方法与全监督方法之间的差距。
表 1：3D 点云分类准确率对比（%）。
2. 3D 点云分割
在该任务中，作者使用 ShapeNet part 数据集来验证提出的模型。作者同样将 GraphTER 分别同无监督方法和有监督方法进行比较，如表 2 中所示。作者的模型达到了 81.9％的 mIoU，这比最先进的无监督方法 MAP-VAE 提升了 13.9％。此外，无监督的 GraphTER 模型还可以达到与最新的全监督的方法相当的性能。
表 2：3D 点云分割结果对比（mIoU）
图 5 展示了 GraphTER 模型和两个全监督的方法（DGCNN 和 RSCNN）的 3D 点云分割的可视化结果。在第一行的「桌子」模型上，GraphTER 模型带来了更准确的分割，并在其他模型上获得了相似的分割结果。
图 5：GraphTER 与全监督方法的 3D 点云分割可视化结果对比。
此外，作者也将 GraphTER 和最新的无监督方法 MAP-VAE 进行对别，如图 6 所示。与 MAP-VAE 相比，作者提出的模型能够带来更准确的分割结果，例如飞机的引擎和椅子腿的部分。
图 6：GraphTER 与无监督方法 MAP-VAE 的 3D 点云分割可视化结果对比。
五、结论
在本文中，作者们提出了一种以无监督方式自动编码节点的变换来学习图变换共变表征的方法——GraphTER。作者全局或局部地从图上采样不同的节点，然后各向同性或各向异性地进行逐节点变换，从而能够表征各种规模的图结构。通过解码这些逐节点的变换，GraphTER 能够学习到图的固有表征。作者将 GraphTER 应用于 3D 点云分类和分割任务中，实验结果验证了 GraphTER 优于最新的无监督方法，并且大大缩小了与全监督方法性能之间的差距。作者将在未来的工作中将 GraphTER 模型推广到更多的应用中，例如引文网络或社交网络的节点分类。
[1] Liheng Zhang, Guo-Jun Qi, Liqiang Wang, and Jiebo Luo. AET vs. AED: Unsupervised Representation Learning by Auto-Encoding Transformations rather than Data. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 2547–2555, 2019.
[2] Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay E Sarma, Michael M Bronstein, and Justin M Solomon. Dynamic Graph CNN for Learning on Point Clouds. ACM Transactions on Graphics (TOG), 38(5):146, 2019.
[3] Xiang Gao, Wei Hu, and Guo-Jun Qi. GraphTER: Unsupervised Learning of Graph Transformation Equivariant Representations via Auto-Encoding Node-wise Transformations. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2020.
