Dynamic Graph CNN (Edge Conv)
Dynamic Graph CNN for Learning on Point Clouds by Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay E. Sarma, Michael M. Bronstein, Justin M. Solomon
EdgeConv is a new neural-network module suitable for CNN-based high-level tasks on point clouds including classification and segmentation. EdgeConv appealing property is that it incorporates local neighborhood information as it can be stacked or recurrently applied to learn global shape properties.
EdgeConv captures local geometric structure while maintaining permutation invariance. It generates edge features that describe the relationship between a point and its neighbors instead of generating points’ feature directly from embedding.
EdgeConv is designed to better capture local geometric functions and be invariant to the ordering of neighbors and thus permutation invariant.

Approach
EdgeConv is inspired from PointNet and convolutional operations, but instead of working on individual points it exploits the geometric structure by constructing a local neighborhood graph and applying convolution-like operation on the edge connecting the neighborhood pair of points. It thus has the property of translation-invariant and non-locality.
Here the graph is not fixed as it is dynamically updated after each layer of the network, that is the k-nearest neighbors (kNN) of a point changes after each layer which is calculated from the sequence of embedding.
What is EdgeConv?
EdgeConv applies channel-wise symmetric aggregation operation ([]) on the edge features associated with all the edges emanating from each vertex.

The edge features are defined as Eij = H(Xi,Xj), where H is some parametric non-linear function parametrized by the set of learnable parameters. H will be MLP for the model.

So the output of EdgeConv at the i-th vertex is:

Where [] can be summation or max.
The Edge Function (h)
The choice of edge function has a crucial influence on the properties of the resulting EdgeConv operation. Below are some function and their properties.
Why is it named as Dynamic Graph CNN
Dynamic graph update: It was seen empirically beneficial to recompute the graph in the feature space produced by each layer using nearest neighbors. So at each layer, the graph is updated with the nearest neighbors using the current feature space.

Architecture

The architecture is similar to Pointnet, which also has a spatial transformer which computes a global shape transformation. There are two architecture for two tasks: classification and segmentation
- Classification: Consists of 2 EdgeConv layer (The first layer uses 3 fully connected layers (64,64,64) while the second layer uses a shared fully connected layer(128)) followed by pooling operation and 3 fully-connected layers to transform the global feature, producing the k-class score. All layer includes ReLU and batch normalization.
- Segmentation: Consists of a sequence of 3 EdgeConv layers followed by 3 fully-connected layers producing a k-class score for each point.
Edge Function: For each EdgeConv block we use the edge function H(Xi,Xj) = H(Xi, Xj — Xi), where the function is implemented as MLP and [] as max-pooling.
K value: for classification, the authors used k as 20 and for segmentation, they used k as 30.
Discussion
EdgeConv is a novel pointcloud operation suitable for CNN-based high-level task such as classification and segmentation. It is differentiable and can be plugged into the existing architecture. It incorporates the local feature which can be stacked or recurrently applied to learn the global feature. It is able to capture fine-grain geometric properties of point clouds.
Reference
- Dynamic Graph CNN for Learning on Point Clouds (Paper)
