代码：https://github.com/mys007/ecc

一、模型概要

论文主要介绍了一种在图结构上进行卷积操作的一种方法，简称为ECC。ECC的卷积操作和常规的二维图像卷积操作都是一种加权平均操作，不同之处在于ECC可以作用在任何图结构上，并且其权重由节点间的边权所决定。

1.1 概念与符号定义

• 对于一个有向图或者无向图$G=(V,E)$G=(V,E)，结点的个数$|V|=n$∣V∣=n，边缘的个数$|E|=m$∣E∣=m ，设 $l \in \{0,...,l_{max} \}$l∈{0,...,lmax​} 为神经网络的层数索引。
• 设图G的顶点和边上都有标签，记第$l$l层的每个顶点的标签(即特征)维度为$d_l$dl​, 则通过矩阵$X^l \in \mathbb{R}^{n \times d_l }$Xl∈Rn×dl​来表示这$n$n个顶点上的标签。同理以$L \in \mathbb{R}^{m \times s}$L∈Rm×s表示边上的标签（也称属性）。注意，顶点上的标签（特征）维度会随着层数的改变而改变，而边上的标签维度不随着网络层数而变化。记$X^0$X0为输入信号。
• 顶点$i$i的邻居被定义为与$i$i直接相连的顶点以及$i$i本身，即：
  $N(i) = \{j; (j,i) \in E\} \cup \{i\}$N(i)={j;(j,i)∈E}∪{i}

1.2 ECC的具体方法

• 对于一个顶点，ECC的作用域为其所有邻居。
• 第$l$l层的第$i$i个顶点的特征值$X^l(i) \in \mathbb{R}^{d_l}$Xl(i)∈Rdl​为是由第$l-1$l−1层$i$i的所有邻居的特征值$X^{l-1}(j) \in \mathbb{R}^{d_{l-1}}$Xl−1(j)∈Rdl−1​加权求和得到的。
• 若要解决顶点无序性以及邻居节点数目不确定的问题，显然以常规的方法定义权重是行不通的。ECC的做法：定义函数$F^l: \mathbb{R}^s \mapsto \mathbb{R}^{d_l \times d_{l-1}}$Fl:Rs↦Rdl​×dl−1​ ，其输入是一条边$e_{ji}$eji​上的标签值$L(j,i)$L(j,i)，输出则是一个权重矩阵$\Theta_{ji}^l \in \mathbb{R}^{d_l \times d_{l-1}}$Θjil​∈Rdl​×dl−1​。
• 那么ECC则可表示为：
  $X^l(i) = \frac{1}{N(i)} \sum_{j \in N(i)}F^{l}(L(j,i); \omega^l)X^{l-1}(j) + b^l$Xl(i)=N(i)1​j∈N(i)∑​Fl(L(j,i);ωl)Xl−1(j)+bl$= \frac{1}{N(i)} \sum_{j \in N(i)}\Theta_{ji}^l X^{l-1}(j) + b^l$=N(i)1​j∈N(i)∑​Θjil​Xl−1(j)+bl
  其中$b^l \in \mathbb{R}^{d_l}$bl∈Rdl​是一个可学习的偏置，$\omega^l$ωl是函数$F^l$Fl的可学习权重。文中使用多层感知机mlp来表示函数$F^l$Fl。在训练阶段，$b^l 、\omega^l$bl、ωl在每一次迭代时都会被更新。测试阶段，$b^l 、\omega^l$bl、ωl不会再变化，而$\Theta_{ji}^l$Θjil​的具体值仍依赖于给定的边$e_{ji}$eji​上的标签值$L(j,i)$L(j,i)。因此ECC是一种使用了动态卷积核的方法。

二、 点云上的应用

2.1 点云构图 Graph Construction on point cloud

点云（PointCloud）也可以被视为一种图结构。论文介绍了在原始点云数据结构上进行构图以及对其进行下采样的方法。

• 用点云中每个点$p$p作为图G中的每个顶点$v$v;
• 每个顶点$v$v的初始取值为相应的$p$p的特征值(密度、RGB值等);
• 顶点$v_i$vi​的空间邻域内的所有顶点$v_j$vj​被认为是$v_i$vi​的邻居。空间领域可以有多种取法，可以用knn取，也可以在固定半径的范围内取，实验中固定半径的方法更好;
• 将$v_i$vi​与其所有邻居$v_j$vj​以有向边$e(j,i)$e(j,i)相连，每条边的标签以一个六维向量来表示：
  $L(j; i) = (δx, δy, δz, ||δ||, arccos( δz/||δ||) ,arctan(δy/δx) )$L(j;i)=(δx,δy,δz,∣∣δ∣∣,arccos(δz/∣∣δ∣∣),arctan(δy/δx))其中$\delta=p_j - p_i$δ=pj​−pi​, 即$p_j,p_i$pj​,pi​两点在欧氏空间下的向量偏移。上式中前三个分量为$\delta$δ在笛卡尔坐标系下的坐标值，后三个分量为其在球坐标系下的坐标值。

2.2 点云下采样 Graph Coarsening on point cloud

使用体素化方法对点云进行粗粒度化(也即pooling)。具体做法：

• 使用一个分辨率为$r^h$rh的3d网格框住整个点云$P^{h-1}$Ph−1

• 对于网格中的每个体素, 用该体素的中心点来表示该体素内的所有点

• 用上一节的方法对新的点云$P^h$Ph进行图的构造,得到更粗粒度的图$G^{h}$Gh

按论文中的说法，对于每一个输入图G，都事先使用Graph Coarsening方法为其建立一个$h^{max}$hmax层的图金字塔，金字塔的层数越高，对应的图具有更粗的粒度。然后在网络的pooling层，则根据金字塔中对应的相邻层的结点映射关系来执行pooling操作。