DeepGCNs: Can GCNs Go as Deep as CNNs?

Introduction

GCNs have been gaining a lot of momentum in the last few years. This increased interest is attributed to two main factors: the increasing proliferation of non-Euclidean data in real-world applications, and the limited performance of CNNs when dealing with such data. GCNs operate directly on non-Euclidean data and are very promising for applications that depend on this information modality. GCNs are currently used to predict individual relations in social networks , model proteins for drug discovery , enhance predictions of recommendation engines , efficiently segment large point clouds , among other fields.

A key reason behind the success of CNNs is the ability to design and reliably train very deep CNN models. In contrast, it is not yet clear how to properly train deep GCN architectures, where several works have studied their limitations . Stacking more layers into a GCN leads to the common vanishing gradient problem. This means that back-propagating through these networks causes over-smoothing, eventually leading to features of graph vertices converging to the same value . Due to these limitations, most state-of-the-art GCNs are no deeper than $4$ layers .

Vanishing gradients is not a foreign phenomenon in the world of CNNs. It also posed limitations on the depth growth of these types of networks. ResNet provided a big step forward in the pursuit of very deep CNNs when it introduced residual connections between input and output layers. These connections massively alleviated the vanishing gradient problem. Today, ResNets can reach 152 layers and beyond. Further extension came with DenseNet , where more connections are introduced across layers. More layers could potentially mean more spatial information loss due to pooling. This issue was also addressed, with Dilated Convolutions . The introductions of these key concepts had substantial impact on the progress of CNNs, and we believe they can have a similar effect if well adapted to GCNs.

In this work, we present an extensive study of methodologies that allow for training very deep GCNs. We adapt concepts that were successful in training deep CNNs, mainly residual connections, dense connections, and dilated convolutions. We show how we can incorporate these layers into a graph framework, and present an extensive analysis of the effect of these additions to the accuracy and stability of deep GCNs. To showcase these layer adaptations, we apply them to the popular task of point cloud semantic segmentation. We show that adding a combination of residual and dense connections, and dilated convolutions, enables successful training of GCNs up to $56$ layers deep (refer to Figure 1). This very deep GCN improves the state-of-the-art on the challenging S3DIS point cloud dataset by $3.7\%$.

Contributions. We summarize our contributions as three fold. (1) We adapt residual/dense connections, and dilated convolutions to GCNs. (2) We present extensive experiments on point cloud data, showing the effect of each of these new layers to the stability and performance of training deep GCNs. We use point cloud semantic segmentation as our experimental testbed. (3) We show how these new concepts help build a 56-layer GCN, the deepest GCN architecture by a large margin, and achieve close to $4\%$ boost in state-of-the-art performance on the S3DIS dataset .

Related Work

A large number of real-world applications deal with non-Euclidean data, which cannot be systematically and reliably processed by CNNs in general. To overcome the shortcomings of CNNs, GCNs provide well-suited solutions for non-Euclidean data processing, leading to greatly increasing interest in using GCNs for a variety of applications. In social networks , graphs represent connections between individuals based on mutual interests/relations. These connections are non-Euclidean and highly irregular. GCNs help better estimate edge strengths between the vertices of social network graphs, thus leading to more accurate connections between individuals. Graphs are also used to model chemical molecule structures . Understanding the bio-activities of these molecules can have substantial impact on drug discovery. Another popular use of graphs is in recommendation engines , where accurate modelling of user interactions leads to improved product recommendations. Graphs are also popular modes of representation in natural language processing , where they are used to represent complex relations between large text units.

GCNs also find many applications in computer vision. In scene graph generation, semantic relations between objects are modelled using a graph. This graph is used to detect and segment objects in images, and also to predict semantic relations between object pairs . Scene graphs also facilitate the inverse process, where an image is reconstructed given a graph representation of the scene . Graphs are also used to model human joints for action recognition in video . GCNs are a perfect candidate for 3D point cloud processing, especially since the unstructured nature of point clouds poses a representational challenge for systematic research. Several attempts in creating structure from 3D data exist by either representing it with multiple 2D views , or by voxelization . More recent work focuses on directly processing unordered point cloud representations . The recent EdgeConv method by Wang et al. applies GCNs to point clouds. In particular, they propose a dynamic edge convolution algorithm for semantic segmentation of point clouds. The algorithm dynamically computes node adjacency at each graph layer using the distance between point features. This work demonstrates the potential of GCNs for point cloud related applications and beats the state-of-the-art in the task of point cloud segmentation. Unlike most other works, EdgeConv does not rely on RNNs or complex point aggregation methods.

Current GCN algorithms including EdgeConv are limited to shallow depths. Recent works attempt to train deeper GCNs. For instance, Kipf et al. trained a semi-supervised GCN model for node classification and showed how performance degrades when using more than 3 layers . Pham et al. proposed Column Network (CLN) for collective classification in relational learning and showed peak performance with 10 layers with the performance degrading for deeper graphs. Rahimi et al. developed a Highway GCN for user geo-location in social media graphs, where they add “highway” gates between layers to facilitate gradient flow. Even with these gates, the authors demonstrate performance degradation after 6 layers of depth. Xu et al. developed a Jump Knowledge Network for representation learning and devised an alternative strategy to select graph neighbors for each node based on graph structure. As with other works, their network is limited to a small number of layers ($6$). Recently, Li et al. studied the depth limitations of GCNs and showed that deep GCNs can cause over-smoothing, which results in features at vertices within each connected component converging to the same value. Other works also show the limitations of stacking multiple GCN layers, which lead to highly complex back-propagation and the common vanishing gradient problem.

Many difficulties facing GCNs nowadays (e.g. vanishing gradients and limited receptive field) were also present in the early days of CNNs . We bridge this gap and show that the majority of these drawbacks can be remedied by borrowing several orthogonal tricks from CNNs. Deep CNNs achieved a huge boost in performance with the introduction of ResNet . By adding residual connections between inputs and outputs of layers, ResNet tends to alleviate the vanishing gradient problem. DenseNet takes this idea a step further and adds connections across layers as well. Dilated Convolutions are a more recent approach that has lead to significant performance gains, specifically in image-to-image translation tasks such as semantic segmentation , by increasing the receptive field without loss of resolution. In this work, we show how one can benefit from concepts introduced for CNNs, mainly residual/dense connections and dilated convolutions, to train very deep GCNs. We support our claim by extending the work of Wang et al. to a much deeper GCN, and therefore significantly increasing its performance. Extensive experiments on the task of point cloud semantic segmentation validate these ideas for general graph scenarios.

Methodology

Graph Definition. A graph $\mathcal{G}$ is represented by a tuple $\mathcal{G}=(\mathcal{V},\mathcal{E})$ where $\mathcal{V}$ is the set of unordered vertices and $\mathcal{E}$ is the set of edges representing the connectivity between vertices $v\in\mathcal{V}$. If $e_{i,j}\in\mathcal{E}$, then vertices $v_{i}$ and $v_{j}$ are connected to each other with an edge $e_{i,j}$.

$\mathcal{G}_{l}=(\mathcal{V}_{l},\mathcal{E}_{l})$ and $\mathcal{G}_{l+1}=(\mathcal{V}_{l+1},\mathcal{E}_{l+1})$ are the input and output graphs at the $l$-th layer, respectively. $\mathcal{W}_{l}^{agg}$ and $\mathcal{W}_{l}^{update}$ are the learnable weights of the aggregation and update functions respectively, and they are the essential components of GCNs. In most GCN frameworks, aggregation functions are used to compile information from the neighborhood of vertices, while update functions perform a non-linear transform on the aggregated information to compute new vertex representations. There are different variants of those two functions. For example, the aggregation function can be a mean aggregator , a max-pooling aggregator , an attention aggregator or an LSTM aggregator . The update function can be a multi-layer perceptron , a gated network , etc. More concretely, the representation of vertices is computed at each layer by aggregating features of neighbor vertices for all $v_{l+1}\in\mathcal{V}_{l+1}$ as follows,

where $\rho$ is a vertex feature aggregation function and $\phi$ is a vertex feature update function, $\mathbf{h}_{v_{l}}$ and $\mathbf{h}_{v_{l+1}}$ are the vertex features at the $l$-th layer and $l+1$-th layer respectively. $\mathcal{N}(v_{l})$ is the set of neighbor vertices of $v$ at the $l$-th layer, and $\mathbf{h}_{u_{l}}$ is the feature of those neighbor vertices parametrized by $\mathcal{W}_{\rho}$. $\mathcal{W}_{\phi}$ contains the learnable parameters of these functions. For simplicity and without loss of generality, we use a max-pooling vertex feature aggregator, without learnable parameters, to pool the difference of features between vertex $v_{l}$ and all of its neighbors: $\rho(.)=\max(\mathbf{h}_{u_{l}}-\mathbf{h}_{v_{l}}|~u_{l}\in\mathcal{N}(v_{l}))$. We then model the vertex feature updater $\phi$ as a multi-layer perceptron (MLP) with batch normalization and a ReLU as an activation function. This MLP concatenates $\mathbf{h}_{v_{l}}$ with its aggregate features from $\rho(.)$ to form its input.

Dynamic Edges. As mentioned earlier, most GCNs have fixed graph structures and only update the vertex features at each iteration. Recent work demonstrates that dynamic graph convolution, where the graph structure is allowed to change in each layer, can learn better graph representations compared to GCNs with fixed graph structure. For instance, ECC (Edge-Conditioned Convolution) uses dynamic edge-conditional filters to learn an edge-specific weight matrix. Moreover, EdgeConv finds the nearest neighbors in the current feature space to reconstruct the graph after every EdgeConv layer. In order to learn to generate point clouds, Graph-Convolution GAN (Generative Adversarial Network) also applies $k$-NN graphs to construct the neighbourhood of each vertex in every layer. We find that dynamically changing neighbors in GCNs helps alleviate the over-smoothing problem and results in an effectively larger receptive field, when deeper GCNs are considered. In our framework, we propose to re-compute edges between vertices via a Dilated $k$-NN function in the feature space of each layer to further increase the receptive field. In what follows, we provide detailed description of three operations that can enable much deeper GCNs to be trained: residual connections, dense connections, and dilated aggregation.

2 Residual Learning for GCNs

Designing deep GCN architectures is an open problem in the graph learning space. Recent work suggests that GCNs do not scale well to deep architectures, since stacking multiple layers of graph convolutions leads to high complexity in back-propagation. As such, most state-of-the-art GCN models are usually no more than 3 layers deep . Inspired by the huge success of ResNet , DenseNet and Dilated Convolutions , we transfer these ideas to GCNs to unleash their full potential. This enables much deeper GCNs that reliably converge in training and achieve superior performance in inference.

In the original graph learning framework, the underlying mapping $\mathcal{F}$, which takes a graph as an input and outputs a new graph representation (see Equation (1)), is learned. Here, we propose a graph residual learning framework that learns an underlying mapping $\mathcal{H}$ by fitting another mapping $\mathcal{F}$. After $\mathcal{G}_{l}$ is transformed by $\mathcal{F}$, vertex-wise addition is performed to obtain $\mathcal{G}_{l+1}$. The residual mapping $\mathcal{F}$ learns to take a graph as input and outputs a residual graph representation $\mathcal{G}_{l+1}^{res}$ for the next layer. $\mathcal{W}_{l}$ is the set of learnable parameters at layer $l$. In our experiments, we refer to our residual model as ResGCN.

3 Dense Connections in GCNs

DenseNet was proposed to exploit dense connectivity among layers, which improves information flow in the network and enables efficient reuse of features among layers. Inspired by DenseNet, we adapt a similar idea to GCNs so as to exploit information flow from different GCN layers. In particular, we have:

The operator $\mathcal{T}$ is a vertex-wise concatenation function that densely fuses the input graph $\mathcal{G}_{0}$ with all the intermediate GCN layer outputs. To this end, $\mathcal{G}_{l+1}$ consists of all the GCN transitions from previous layers. Since we fuse GCN representations densely, we refer to our dense model as DenseGCN. The growth rate of DenseGCN is equal to the dimension $D$ of the output graph (similar to DenseNet for CNNs ). For example, if $\mathcal{F}$ produces a $D$ dimensional vertex feature, where the vertices of the input graph $\mathcal{G}_{0}$ are $D_{0}$ dimensional, the dimension of each vertex feature of $\mathcal{G}_{l+1}$ is $D_{0}+D\times(l+1)$.

4 Dilated Aggregation in GCNs

Let $\mathcal{N}^{(d)}(v)$ denote the $d$-dilated neighborhood of vertex $v$. If $(u_{1},u_{2},...,u_{k\times d})$ are the first sorted $k\times d$ nearest neighbors, vertices $(u_{1},u_{1+d},u_{1+2d},...,u_{1+(k-1)d})$ are the $d$-dilated neighbors of vertex $v$ (see Figure 3), i.e.

Therefore, the edges $\mathcal{E}^{(d)}$ of the output graph are defined on the set of $d$-dilated vertex neighbors $\mathcal{N}^{(d)}(v)$. Specifically, there exists a directed edge $e\in\mathcal{E}^{(d)}$ from vertex $v$ to every vertex $u\in\mathcal{N}^{(d)}(v)$. The GCN aggregation and update functions are applied, as in Equation (1), by using the edges $\mathcal{E}^{(d)}$ created by the Dilated $k$-NN, so as to generate the feature $\mathbf{h}_{v}^{(d)}$ of each output vertex in $\mathcal{V}^{(d)}$. We denote this layer operation as a dilated graph convolution with dilation rate $d$, or more formally: $\mathcal{G}^{(d)}=(\mathcal{V}^{(d)},\mathcal{E}^{(d)})$. To improve generalization, we use stochastic dilation in practice. During training, we perform the aforementioned dilated aggregations with a high probability $(1-\epsilon)$ leaving a small probability $\epsilon$ to perform random aggregation by uniformly sampling $k$ neighbors from the set of $k\times d$ neighbors $\{u_{1},u_{2},...,u_{k\times d}\}$. At inference time, we perform deterministic dilated aggregation without stochasticity.

Experiments

We propose ResGCN and DenseGCN to handle the vanishing gradient problem of GCNs. To enlarge the receptive field, we define a dilated graph convolution operator for GCNs. To evaluate our framework, we conduct extensive experiments on the task of large-scale point cloud segmentation and demonstrate that our methods significantly improve performance. In addition, we also perform a comprehensive ablation study to show the effect of different components of our framework.

Point cloud segmentation is a challenging task because of the unordered and irregular structure of 3D point clouds. Normally, each point in a point cloud is represented by its 3D spatial coordinates and possibly auxiliary features such as color and surface normal. We treat each point as a vertex $v$ in a directed graph $\mathcal{G}$ and we use $k$-NN to construct the directed dynamic edges between points at every GCN layer (refer to Section 3.1). In the first layer, we construct the input graph $\mathcal{G}_{0}$ by executing a dilated $k$-NN search to find the nearest neighbor in 3D coordinate space. At subsequent layers, we dynamically build the edges using dilated $k$-NN in feature space. For the segmentation task, we predict the categories of all the vertices at the output layer.

2 Experimental Setup

We use the overall accuracy (OA) and mean intersection over union (mIoU) across all classes as evaluation metrics. For each class, the IoU is computed as $\frac{TP}{TP+T-P}$, where $TP$ is the number of true positive points, $T$ is the number of ground truth points of that class, and $P$ is the number of predicted positive points. To motivate the use of deep GCNs, we do a thorough ablation study on area 5 to analyze each component and provide insights. We then evaluate our proposed reference model (backbone of 28 layers with residual graph connections and stochastic dilated graph convolutions) on all 6 areas and compare it to the shallow DGCNN baseline and other state-of-the-art methods.

3 Network Architectures

As shown in Figure 2, all the network architectures in our experiments have three blocks: a GCN backbone block, a fusion block and an MLP prediction block. The GCN backbone block is the only part that differs between experiments. For example, the only difference between PlainGCN and ResGCN is the use of residual skip connections for all GCN layers in ResGCN. Both have the same number of parameters. We linearly increase the dilation rate $d$ of dilated $k$-NN with network depth. For fair comparison, we keep the fusion and MLP prediction blocks the same for all architectures. In the S3DIS semantic segmentation task, the GCN backbone block takes as input a point cloud with 4096 points, extracts features by applying consecutive GCN layers to aggregate local information, and outputs a learned graph representation with 4096 vertices. The fusion and MLP prediction blocks follow a similar architecture as PointNet and DGCNN . The fusion block is used to fuse the global and multi-scale local features. It takes as input the extracted vertex features from the GCN backbone block at every GCN layer and concatenates those features, then passes them through a 1$\times$1 convolution layer followed by max pooling. The latter layer aggregates the vertex features of the whole graph into a single global feature vector, which in return is concatenated with the feature of each vertex from all previous GCN layers (fusion of global and local information). The MLP prediction block applies three MLP layers to the fused features of each vertex/point to predict its category. In practice, these layers are 1$\times$1 convolutions.

PlainGCN. This baseline model consists of a PlainGCN backbone block, a fusion block, and a MLP prediction block. The backbone stacks 28 EdgeConv layers with dynamic $k$-NN, each of which is similar to the one used in DGCNN . No skip connections are used here.

ResGCN. We construct ResGCN by adding dynamic dilated $k$-NN and residual graph connections to PlainGCN. These connections between all GCN layers in the GCN backbone block do not increase the number of parameters.

DenseGCN. Similarly, DenseGCN is built by adding dynamic dilated $k$-NN and dense graph connections to the PlainGCN. As described in Section 3.3, dense graph connections are created by concatenating all the intermediate graph representations from previous layers. The dilation rate schedule of our DenseGCN is the same as ResGCN.

4 Implementation

We implement all our models using Tensorflow. For fair comparison, we use the Adam optimizer with the same initial learning rate $0.001$ and the same learning rate schedule; the learning rate decays $50\%$ every $3\times 10^{5}$ gradient decent steps. The networks are trained with two NVIDIA Tesla V100 GPUs using data parallelism. The batch size is set to $8$ for each GPU. Batch Normalization is applied to every layer. Dropout with a rate of $0.3$ is used at the second MLP layer of the MLP prediction block. As mentioned in Section 3.4, we use dilated $k$-NN with a random uniform sampling probability $\epsilon=0.2$ for GCNs with dilations. In order to isolate the effect of the proposed deep GCN architectures, we do not use any data augmentation or post processing techniques. We train our models end-to-end from scratch.

5 Results

For convenient referencing, we use the naming convention BackboneBlock-#Layers to denote the key models in our analysis and we provide all names in Table 1. We focus on residual graph connections for our analysis, since ResGCN-28 is easier and faster to train, but we expect that our observations also hold for dense graph connections.

We investigate the performance of different ResGCN architectures, e.g. with dynamic dilated $k$-NN, with regular dynamic $k$-NN (without dilation), and with fixed edges. We also study the effect of different parameters, e.g. number of $k$-NN neighbors (4, 8, 16, 32), number of filters (32, 64, 128), and number of layers (7, 14, 28, 56). Overall, we conduct 20 experiments and show their results in Table 1.

Effect of residual graph connections. Our experiments in Table 1 (Reference) show that residual graph connections play an essential role in training deeper networks, as they tend to result in more stable gradients. This is analogous to the insight from CNNs . When the residual graph connections between layers are removed (i.e. in PlainGCN-28), performance dramatically degrades (-12% mIoU). In Appendices A and B, we show similar performance gains by combining residual graph connections and dilated graph convolutions with other types of GCN layers.

Effect of dilation. Results in Table 1 (Dilation) show that dilated graph convolutions account for a 2.85% improvement in mean IoU (row 3), motivated primarily by the expansion of the network’s receptive field. We find that adding stochasticity to the dilated $k$-NN does help performance but not to a significant extent. Interestingly, our results in Table 1 also indicate that dilation especially helps deep networks when combined with residual graph connections (rows 1,8). Without such connections, performance can actually degrade with dilated graph convolutions. The reason for this is probably that these varying neighbors result in ‘worse’ gradients, which further hinder convergence when residual graph connections are not used.

Effect of dynamic $k$-NN. While we observe an improvement when updating the $k$ nearest neighbors after every layer, we would also like to point out that it comes at a relatively high computational cost. We show different variants without dynamic edges in Table 1 (Fixed $k$-NN).

Effect of dense graph connections. We observe similar performance gains with dense graph connections (DenseGCN-28) in Table 1 (Connections). However, with a naive implementation, the memory cost is prohibitive. Hence, the largest model we can fit into GPU memory uses only $32$ filters and $8$ nearest neighbors, as compared to $64$ filters and $16$ neighbors in the case of its residual counterpart ResGCN-28. Since the performance of these two deep GCN variants is similar, residual connections are more practical for most use cases and, hence we focus on them in our ablation study. Yet, we do expect the same insights to transfer to the case of dense graph connections.

Effect of nearest neighbors. Results in Table 1 (Neighbors) show that a larger number of neighbors helps in general. As the number of neighbors is decreased by a factor of 2 and 4, the performance drops by 2.5% and 3.3% respectively. However, a large number of neighbors only results in a performance boost, if the network capacity is sufficiently large. This becomes apparent when we increase the number of neighbors by a factor of 2 and decrease the number of filters by a factor of 2.

Effect of network depth. Table 1 (Depth) shows that increasing the number of layers improves network performance, but only if residual graph connections and dilated graph convolutions are used, as in Table 1 (Connections).

Effect of network width. Results in Table 1 (Width) show that increasing the number of filters leads to a similar increase in performance as increasing the number of layers. In general, a higher network capacity enables learning nuances necessary for succeeding in corner cases.

Qualitative Results. Figure 4 shows qualitative results on area 5 of S3DIS . As expected from the results in Table 1, our ResGCN-28 and DenseGCN-28 perform particularly well on difficult classes such as board, beam, bookcase and door. Rows 1-4 clearly show how ResGCN-28 and DenseGCN-28 are able to segment the board, beam, bookcase and door respectively, while PlainGCN-28 completely fails. Please refer to Appendices C, D and E for more qualitative results and other ablation studies.

Comparison to state-of-the-art. Finally, we compare our reference network (ResGCN-28), which incorporates the ideas put forward in the methodology, to several state-of-the-art baselines in Table 2. The results clearly show the effectiveness of deeper models with residual graph connections and dilated graph convolutions. ResGCN-28 outperforms DGCNN by 3.9% (absolute) in mean IoU, even though DGCNN has the same fusion and MLP prediction blocks as ResGCN-28 but with a shallower PlainGCN backbone block. Furthermore, we outperform all baselines in 9 out of 13 classes. We perform particularly well in the difficult object classes such as board, where we achieve 51.1%, and sofa, where we improve state-of-the-art by about 10%.

This significant performance improvement on the difficult classes is probably due to the increased network capacity, which allows the network to learn subtle details necessary to distinguish between a board and a wall for example. The first row in Figure 4 is a representative example for this occurrence. Our performance gains are solely due to our innovation in the network architecture, since we use the same hyper-parameters and even learning rate schedule as the baseline DGCNN and only decrease the number of nearest neighbors from $20$ to $16$ and the batch size from $24$ to $16$ due to memory constraints. We outperform state-of-the art methods by a significant margin and expect further improvement from tweaking the hyper-parameters, especially the learning schedule.

Conclusion and Future Work

In this work, we investigate how to bring proven useful concepts (residual connections, dense connections and dilated convolutions) from CNNs to GCNs and answer the question: how can GCNs be made deeper? Extensive experiments show that by adding skip connections to GCNs, we can alleviate the difficulty of training, which is the primary problem impeding GCNs to go deeper. Moreover, dilated graph convolutions help to gain a larger receptive field without loss of resolution. Even with a small amount of nearest neighbors, deep GCNs can achieve high performance on point cloud semantic segmentation. ResGCN-56 performs very well on this task, although it uses only $8$ nearest neighbors compared to $16$ for ResGCN-28. We were also able to train ResGCN-151 for 80 epochs; the network converged very well and achieved similar results as ResGCN-28 and ResGCN-56 but with only 3 nearest neighbors. Due to computational constraints, we were unable to investigate such deep architectures in detail and leave it for future work.

Our results show that after solving the vanishing gradient problem plaguing deep GCNs, we can either make GCNs deeper or wider (e.g. ResGCN-28W) to get better performance. We expect GCNs to become a powerful tool for processing non-Euclidean data in computer vision, natural language processing, and data mining. We show successful cases for adapting concepts from CNNs to GCNs. In the future, it will be worthwhile to explore how to transfer other operators, e.g. deformable convolutions , other architectures, e.g. feature pyramid architectures , etc. It will also be interesting to study different distance measures to compute dilated $k$-NN, constructing graphs with different $k$ at each layer, better dilation rate schedules for GCNs, and combining residual and dense connections.

We also point out that, for the specific task of point cloud semantic segmentation, the common approach of processing the data in $1m\times 1m$ columns is sub-optimal for graph representation. A more suitable sampling approach should lead to further performance gains on this task.

Acknowledgments. The authors thank Adel Bibi and Guocheng Qian for their help with the project. This work was supported by the King Abdullah University of Science and Technology (KAUST) Office of Sponsored Research through the Visual Computing Center (VCC) funding.

References

Appendix A Deep GCN Variants

In our experiments in the paper, we work with a GCN based on EdgeConv to show how very deep GCNs can be trained. However, it is straightforward to build other deep GCNs with the same concepts we proposed (e.g. residual/dense graph connections, dilated graph convolutions). To show that these concepts are universal operators and can be used for general GCNs, we perform additional experiments. In particular, we build ResGCNs based on GraphSAGE , Graph Isomorphism Network (GIN) and MRGCN (Max-Relative GCN) which is a new GCN operation we proposed. In practice, we find that EdgeConv learns a better representation than the other implementations. However, it is less memory and computation efficient. Therefore, we propose a simple GCN combining the advantages of them all.

All of the ResGCNs have the same components (e.g. dynamic $k-NN$, residual connections, stochastic dilation) and parameters (e.g. #NNs, #filters and #layers) as ResGCN-28 in Table Ablation Study of the paper except for the internal GCN operations. To simplify, we refer to these models as ResEdgeConv, ResGraphSAGE, ResGIN and NewResGCN respectively. Note that ResEdgeConv is an alias for ResGCN in our paper. We refer to it as ResEdgeConv to distinguish it from the other GCN operations.

ResEdgeConv. Instead of aggregating neighborhood features directly, EdgeConv proposes to first get local neighborhood information for each neighbor by subtracting the feature of the central vertex from its own feature. In order to train deeper GCNs, we add residual/dense graph connections and dilated graph convolutions to EdgeConv:

ResGraphSAGE. GraphSAGE proposes different types of aggregator functions including a Mean aggregator, LSTM aggregator and Pooling aggregator. Their experiments show that the Pooling aggregator outperforms the others. We adapt GraphSAGE with the max-pooling aggregator to obtain ResGraphSAGE:

In the original GraphSAGE paper, the vertex features are normalized after aggregation. We implement two variants, one without normalization (see Equation (6)), the other one with normalization $\mathbf{h}^{res}_{v_{l+1}}=\mathbf{h}^{res}_{v_{l+1}}/\left\|\mathbf{h}^{res}_{v_{l+1}}\right\|_{2}$.

ResGIN. The main difference between GIN and other GCNs is that an $\epsilon$ is learned at each GCN layer to give the central vertex and aggregated neighborhood features different weights. Hence ResGIN is formulated as follows:

ResMRGCN. We find that first using a max aggregator to aggregate neighborhood relative features $(\mathbf{h}_{u_{l}}-\mathbf{h}_{v_{l}}),~u_{l}\in\mathcal{N}(v_{l})$ is more efficient than aggregating raw neighborhood features $\mathbf{h}_{v_{l}},~u_{l}\in\mathcal{N}(v_{l})$ or aggregating features after non-linear transforms. We refer to this simple GCN as MRGCN (Max-Relative GCN). The residual version of MRGCN is as such:

Where $\mathbf{h}_{v_{l+1}}$ and $\mathbf{h}_{v_{l}}$ are the hidden state of vertex $v$ at $l+1$; $\mathbf{h}^{res}_{v_{l+1}}$ is the hidden state of the residual graph. All the mlp (multilayer perceptron) functions use a ReLU as activation function; all the max and sum functions above are vertex-wise feature operators; concat functions concatenate features of two vertices into one feature vector. $\mathcal{N}^{(d)}(v_{l})$ denotes the neighborhood of vertex $v_{l}$ obtained from Dilated $k$-NN.

Appendix B Results for Deep GCN Variants

Table 3 shows a comparison of different deep residual GCNs variants on the task of semantic segmentation; we report the mIOU for area 5 of S3DIS. All deep GCN variants are 28 layers deep and we denote them as ResEdgeConv-28, ResGraphSAGE-28, ResGraphSAGE-N-28, ResGIN-$\epsilon$-28 and ResMRGCN-28; ResGraphSAGE-28 is GraphSAGE without normalization, ResGraphSAGE-N-28 is the version with normalization. The results clearly show that different deep GCN variants with residual graph connections and dilated graph convolutions converge better than the PlainGCN. ResMRGCN-28 achieves almost the same performance as ResEdgeConv-28 while only using half of the GPU memory. ResGraphSAGE-28 and ResGraphSAGE-N-28 are slightly worse than ResEdgeConv-28 and ResMRGCN-28. The results also show that using normalization for ResGraphSAGE is not essential. Interestingly, we find that ResGIN-$\epsilon$-28 converges well during the training phase and has a high training accuracy. However, it fails to generalize to the test set. This phenomenon is also observed in the original paper in which they find setting $\epsilon$ to $0$ can get the best performance. Therefore, we can draw the conclusion that the concepts we proposed (e.g. residual/dense graph connections and dilated graph convolutions) generalize well to different types of GCNs and enable training very deep GCNs.

Appendix C Qualitative Results for the Ablation Study

We summarize the most important insights of the ablation study in Figure 5. Figures 6, 7, 8, 9, 10 show qualitative results for the ablation study presented in the paper.

Appendix D Run-time Overhead of Dynamic k-NN

We conduct a run-time experiment comparing the inference time of the reference model (28 layers, $k$=16) with dynamic k-NN and fixed k-NN. The inference time with fixed k-NN is 45.63ms. Computing the dynamic k-NN increases the inference time by 150.88ms. It is possible to reduce computation by updating the k-NN less frequently (e.g. computing the dynamic k-NN every 3 layers).

Appendix E Comparison with DGCNN over All Classes

To showcase the consistent improvement of our framework over the baseline DGCNN , we reproduce the results of DGCNN The results over all classes were not provided in the original DGCNN paper in Table 4 and find our method outperforms DGCNN in all classes.