摘要

背景： 许多问题都可以表示为基于graph结构数据的预测
方法： 将卷积操作从网格推广到任意的graphs，同时避免了频域，能够解决不同大小和连通性的graph
细节： filters的权值依赖顶点到邻域的边值；开发了用于graph分类的深度神经网络
结果： 在点云分类上的效果很好
代码： https://github.com/mys007/ecc (PyTorch版本)

1.引言

在空间域中构建了一个图卷积神经网络，filters的权值依赖于边上的值，并且对每个特定的输入都动态更新。提出的图卷积网络适用于任意的数据结构
将图卷积网络应用到点云分类任务中，并取得到了较好的结果

2.相关工作

频域方法
空间域方法

3.方法

3.1 Edge-Conditioned Convolution

令【点云处理之论文狂读经典版7】—— Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs 为前馈神经网络层的索引。

令【点云处理之论文狂读经典版7】—— Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs 表示无向或有向图，其中是顶点(Vertex)的有限集合，是边(Edge)的集合。

假设图是通过顶点和边进行表示的，即【点云处理之论文狂读经典版7】—— Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs 表示给每个顶点分配值（feature），表示给每个边分配值（attribute）。用矩阵的形式可以表示所有的顶点和所有的边表示为输入信号。

顶点【点云处理之论文狂读经典版7】—— Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs 的 neighborhood 包含了所有相邻的顶点和本身。

顶点【点云处理之论文狂读经典版7】—— Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs 处的filtered信号通过其neighborhood点信号，的加权和计算得到。

尽管这种交换聚合的方式解决了permutation-invariant和neighborhood 大小可变的问题，但是这样也抹除了任意的结构信息。（意思是指聚合的方法太暴力？只用顶点进行更新会损失结构信息，所以引出了边值作为权重）

为了解决这个问题，提出在每个边值上都加入filter权值的条件。定义一个输入为边值【点云处理之论文狂读经典版7】—— Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs 的filter-generating network ，输出为特定边的权值矩阵，见图1。

这个被称为 Edge-Conditioned Convolution (ECC) 的卷积操作，用公式可以表示为：
【点云处理之论文狂读经典版7】—— Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs
其中是可学习的偏置，的可学习参数为网络权值。和是模型参数，仅在训练时更新，是根据输入graph的边值动态生成的参数。filter-generating network 【点云处理之论文狂读经典版7】—— Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs 可以是任意可导的模型，本文使用的是多层感知机。

复杂度
对所有顶点计算【点云处理之论文狂读经典版7】—— Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs 至多需要次的评估，以及(有向图)或(无向图)次矩阵-向量乘法运算。但是在GPU上进行操作会更有效率一些。

3.2 Relationship to Existing Formulations

在规则的网格上进行卷积可以看作是ECC的一种特殊形式。

3.3. Deep Networks with ECC

网络结构包括交错卷积、全局池化和全连接层组成，见图3。通过这种方式，从局部邻域中得到的信息会逐层结合得到最终的context（增大接受域）。虽然边值对特定的graph来说是固定的，但通过filter generating networks进行了（学习的）解释，可能会从一层到另外一层时发生改变（在层之间未共享【点云处理之论文狂读经典版7】—— Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs 的权重）。因此，只有1-hop neighborhoods限制的ECC并不会被约束，类似于在标准CNN中使用小的3×3filter来换取更深的网络，这是有益的。

在每次卷积后使用Batch Normalization，用于快速收敛。

Pooling

尽管（non-strided）卷积层和所有point-wise层不会改变基础graph，并且只能在顶点上更新信号，但池化层被定义为在一个新的、coarsened graph的顶点上输出聚合信号。因此，必须为每个输入graph构造一个逐步coarser的graph 【点云处理之论文狂读经典版7】—— Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs 的pyramid。

令【点云处理之论文狂读经典版7】—— Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs 表示pyramid中不同的 graph ，每一个都与和相关联。coarsening的过程包含3步：

subsampling or merging vertices
creating the new edge structure and labeling (so-called reduction)
mapping the vertices in the original graph to those in the coarsened one with

最终，索引为【点云处理之论文狂读经典版7】—— Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs 的池化层将聚合到基于的更低维度。

在coarsening的过程中，由于self-edge经常出现，因此会出现较小的graph减少为若干断开连接的顶点，这样也不会出现问题。因为该结构被用来处理带有变量【点云处理之论文狂读经典版7】—— Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs 的graph，我们通过全局 average/max池化操作解决最低分辨率下graph的变化的顶点数量。

3.4. Application in Point Clouds

Graph Construction

给定一组点云【点云处理之论文狂读经典版7】—— Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs 和对应的点特征，我们构造一个有向图，并分配和。

对于每个点都构造顶点，通过分配对应的信号（如果没有特征，那么赋值为0）
通过有向边连接每个顶点和其在空间neighborhood中的顶点，实验表明，Ball query的表现更好
在笛卡尔坐标系和球面坐标系下，6D向量被作为边上的值，其中表示顶点间的偏移。

Graph Coarsening

对于一组输入点云【点云处理之论文狂读经典版7】—— Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs ，通过VoxelGrid algorithm获得下采样点云的pyramid ，具体流程包括在点云上覆盖上分辨率为的网格，对每个voxel中的点取质心。每个下采样后的点云【点云处理之论文狂读经典版7】—— Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs 都被独立转化成neighborhood 半径为的graph 和 labeling 。定义pooling map ，保证中的每个点都被分配给下采样点云中距离其（中的每个点）最近的点。

Data Augmentation

We randomly rotate point clouds about their upaxis, jitter their scale, perform mirroring, or delete random points.

4.实验

【点云处理之论文狂读经典版7】—— Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs 表示ECC的输出通道数为，后面跟着batch normalization和ReLU激活函数。表示最大池化层，grid分辨率为，neighborhood半径为。为平均池化层。是通道数为【点云处理之论文狂读经典版7】—— Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs 的全连接层。表示概率为的dropouot。