Dynamic Graph CNN (Edge Conv)

Sanket Gujar
Sep 4, 2018 · 4 min read

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.

Pointcloud Segmentation with EdgeConv: Visualized as distance from the red point to all the rest of the points. You can observe how deep feature captures the semantically similar features.

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.

EdgeConv Operation: The output of EdgeConv is calculated by aggregating the edge features associated with edges from each connecting 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.

Computing edge feature Eij from a point pair Xi, Xj.

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.

Edge Function (h)

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.

Structure of feature space produced at different stages of network architecture. Visualized as the distance between the red point and the rest of the points.

Architecture

Model 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

  1. 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.
  2. 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

  1. Dynamic Graph CNN for Learning on Point Clouds (Paper)

Sanket Gujar

Written by

Computer Science Graduate Student at WPI, Former Perception Intern at Luminar tech, PA. sanketgujar.github.io

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade