1 of 82

VCC

VISUAL

COMPUTING

CENTER

​

IVUL

DeepGCNs.org

DeepGCNs: Can GCNs go as deep as CNNs?

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

* equal contribution

2 of 82

DeepGCNs: Can GCNs go as deep as CNNs?

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

* equal contribution

DeepGCNs.org

3 of 82

Grid Data：

  • Image

Grid data vs. General graphs

DeepGCNs.org

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

4 of 82

Grid Data：

  • Image
  • Video

​

Grid data vs. General graphs

DeepGCNs.org

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

5 of 82

Grid Data：

  • Image
  • Video
  • Audio
  • Text

Grid data vs. General graphs

DeepGCNs.org

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

6 of 82

Grid Data：

  • Image
  • Video
  • Audio
  • Text
  • Grid game (Go)
  • ...

​

Grid data vs. General graphs

DeepGCNs.org

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

7 of 82

Grid Data：

  • Image
  • Video
  • Audio
  • Text
  • Grid game (Go)
  • ...

​

Grid data vs. General graphs

CNN works well

DeepGCNs.org

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

8 of 82

Why do we need graph convolutional networks?

Grid data vs. General graphs

DeepGCNs.org

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

9 of 82

Why we need graph convolutional networks?

Grid data vs. General graphs

DeepGCNs.org

Tremendous non-grid graph structured data

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

10 of 82

General Graphs：

  • Social Networks
  • Citation Networks

​

Grid data vs. General graphs

Lots of real-world applications need to deal with Non-Grid data

DeepGCNs.org

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

11 of 82

General Graphs：

  • Social Networks
  • Citation Networks
  • Molecules

​

Grid data vs. General graphs

Lots of real-world applications need to deal with Non-Grid data

DeepGCNs.org

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

12 of 82

General Graphs：

  • Social Networks
  • Citation Networks
  • Molecules
  • Point Clouds
  • 3D Meshes
  • ...

​

Grid data vs. General graphs

Lots of real-world applications need to deal with Non-Grid data

DeepGCNs.org

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

13 of 82

General Graphs：

  • Social Networks
  • Citation Networks
  • Molecules
  • Point Clouds
  • 3D Meshes
  • ...

​

Grid data vs. General graphs

CNN doesn’t work

GCN to rescue

​

Lots of real-world applications need to deal with Non-Grid data

DeepGCNs.org

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

14 of 82

CNN vs. GCN - Recap: CNN

Slides by Thomas Kipf

DeepGCNs.org

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

15 of 82

CNN vs. GCN - Recap: CNN

Slides by Thomas Kipf

DeepGCNs.org

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

16 of 82

CNN vs. GCN - Recap: CNN

Slides by Thomas Kipf

DeepGCNs.org

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

17 of 82

CNN vs. GCN - Recap: CNN

Slides by Thomas Kipf

DeepGCNs.org

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

18 of 82

CNN vs. GCN - Recap: CNN

Slides by Thomas Kipf

DeepGCNs.org

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

19 of 82

CNN vs. GCN - Introduction: GCN

Slides by Thomas Kipf

DeepGCNs.org

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

20 of 82

CNN vs. GCN - Introduction: GCN

Slides by Thomas Kipf

DeepGCNs.org

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

21 of 82

CNN vs. GCN - Introduction: GCN

Slides by Thomas Kipf

DeepGCNs.org

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

22 of 82

CNN vs. GCN - Comparison

Convolutional Neural Network (CNN)

DeepGCNs.org

Slides by Thomas Kipf

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

23 of 82

CNN vs. GCN - Comparison

Convolutional Neural Network (CNN)

DeepGCNs.org

Slides by Thomas Kipf

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

24 of 82

CNN vs. GCN - Comparison

Convolutional Neural Network (CNN)

Graph Convolutional Network (GCN)

DeepGCNs.org

Slides by Thomas Kipf

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

25 of 82

CNN vs. GCN - Comparison

Convolutional Neural Network (CNN)

Graph Convolutional Network (GCN)

DeepGCNs.org

Slides by Thomas Kipf

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

26 of 82

CNN vs. GCN

Convolutional Neural Network (CNN)

DeepGCNs.org

Grid

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

27 of 82

CNN vs. GCN

Convolutional Neural Network (CNN)

Graph Convolutional Network (GCN)

DeepGCNs.org

Grid

Graph

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

28 of 82

Kipf, T.N. and Welling, M., 2016. Semi-Supervised Classification with Graph Convolutional Networks.

Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P. and Bengio, Y., 2018. Graph Attention Networks.

Wang, Y., Sun, Y., Liu, Z., Sarma, S.E., Bronstein, M.M. and Solomon, J.M., 2018. Dynamic Graph CNN for Learning on Point Clouds.

Hamilton, W.L., Ying, R. and Leskovec, J., 2017. Inductive Representation Learning on Large Graphs.

Most SOTA GCN models are no deeper than 3 or 4 layers.

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

29 of 82

Most SOTA GCN models are no deeper than 3 or 4 layers.

Kipf, T.N. and Welling, M., 2016. Semi-Supervised Classification with Graph Convolutional Networks.

Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P. and Bengio, Y., 2018. Graph Attention Networks.

Wang, Y., Sun, Y., Liu, Z., Sarma, S.E., Bronstein, M.M. and Solomon, J.M., 2018. Dynamic Graph CNN for Learning on Point Clouds.

Hamilton, W.L., Ying, R. and Leskovec, J., 2017. Inductive Representation Learning on Large Graphs.

Why?

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

30 of 82

Why GCNs are limited to shallow structures?

Over-fitting

Over-smoothing

Vanishing Gradient

Figures from https://towardsdatascience.com/the-vanishing-gradient-problem-69bf08b15484

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

31 of 82

  • Over-fitting
  • Over-smoothing
  • Vanishing gradient
  • Their mixture

Why GCNs are limited to shallow structures?

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

32 of 82

Over smoothing: They prove that by repeatedly applying Laplacian smoothing many times, the features of vertices within each connected component of the graph will converge to the same values

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

33 of 82

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

34 of 82

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

35 of 82

Training Loss of GCNs with varying depth

PlainGCNs

ResGCNs

Deeper GCNs don’t converge well.

Even a 112-layer deep GCN converges well!!!

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

36 of 82

Training Loss of GCNs with varying depth

PlainGCNs

ResGCNs

Deeper GCNs don’t converge well.

Even a 112-layer deep GCN converges well!!!

How can we make GCNs deeper?

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

37 of 82

Residual Graph Connections

DeepGCNs.org

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

38 of 82

Residual Graph Connections

DeepGCNs.org

Aggregate

Update

Skip connection

An example: ResMRGCN

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

39 of 82

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

40 of 82

Dense Graph Connections

DeepGCNs.org

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

41 of 82

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

42 of 82

Better Receptive Field?

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

43 of 82

Dilated Graph Convolutions

1

4

3

2

6

7

5

8

9

11

12

10

13

14

15

16

1

4

3

2

6

7

5

8

9

11

12

10

13

14

15

16

1

4

3

2

6

7

5

8

9

11

12

10

13

14

15

16

Dilated Convolution on a regular graph, e.g. 2D image

Dilated graph Convolution on an irregular graph, e.g. 3D point cloud

DeepGCNs.org

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

44 of 82

Dilated Graph Convolutions

= dilation rate

DeepGCNs.org

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

45 of 82

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

46 of 82

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

47 of 82

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

48 of 82

Deep Graph Convolutional Networks (GCNs)

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

49 of 82

Experiments

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

50 of 82

Graph Learning on 3D Point Clouds

  • Point clouds are unordered and irregular

​

  • Represented by 3D coordinates and extra features such as color, surface normal, etc.

​

  • We use k-NN to construct the directed dynamic edges between points at every GCN layer in the feature space.

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

51 of 82

Stanford 3D Large-Scale Indoor Spaces Dataset

http://buildingparser.stanford.edu/dataset.html

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

52 of 82

Table 1. Comparison of ResGCN-28 with state-of-the-art.

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

53 of 82

Table 1. Comparison of ResGCN-28 with state-of-the-art.

We outperform other SOTA in 9 out of 13 classes

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

54 of 82

Table 2. Comparison of ResGCN-28 with DGCNN* (Our shallow baseline model)

* We reproduced the results of DGCNN on all classes since the results across all classes were not provided in the DGCNN paper.

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

55 of 82

Table 2. Comparison of ResGCN-28 with DGCNN* (Our shallow baseline model)

* We reproduced the results of DGCNN on all classes since the results across all classes were not provided in the DGCNN paper.

Consistent improvements

across all the classes.

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

56 of 82

Table 2. Comparison of ResGCN-28 with DGCNN* (Our shallow baseline model)

* We reproduced the results of DGCNN on all classes since the results across all classes were not provided in the DGCNN paper.

Consistent improvements

across all the classes.

~ 4% boost in mIOU.

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

57 of 82

PlainGCN VS. ResGCN

DeepGCNs.org

Deeper

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

58 of 82

Ablation Study

skip connections, dilation, depth, width, # of NNs

DeepGCNs.org

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

59 of 82

Ablation Study

DeepGCNs.org

Table 3. Ablation study on area 5 of S3DIS.

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

60 of 82

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

61 of 82

Table 3. Ablation study on area 5 of S3DIS.

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

62 of 82

Qualitative Results

Visualizations on S3DIS

DeepGCNs.org

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

63 of 82

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

64 of 82

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

65 of 82

Reduce Kernel Size

Reduce Network Depth

Reduce Network Width

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

66 of 82

Wider

Deeper

No Dilation

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

67 of 82

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

68 of 82

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

69 of 82

More Results

GCN variants

DeepGCNs.org

  • ResEdgeConv
  • ResGraphSAGE
  • ResGIN
  • ResMRGCN

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

70 of 82

Table 3. Comparisons of Deep GCNs variants on area 5 of S3DIS.

ResEdgeConv

ResGIN

ResMRGCN

ResGraphSAGE

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

71 of 82

More Results

DeepGCNs.org

Table 4. Node classification of biological networks

Wider

Deeper

By John Morris.

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

72 of 82

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

73 of 82

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

74 of 82

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

75 of 82

Conclusion and Future Work

  • 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.

​

  • Dilated graph convolutions help to gain a larger receptive field without loss of resolution.

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

76 of 82

Conclusion and Future Work

  • 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.

​

  • Dilated graph convolutions help to gain a larger receptive field without loss of resolution.
  • It will be worthwhile to explore how to transfer other operators, e.g. pooling methods, deformable convolutions, other architectures, e.g. feature pyramid architectures, and so on.

​

  • It will be also interesting to study different distance measures to compute dilated k-nn, constructing graphs using different k at each layer, better dilation rate schedules, etc.

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

77 of 82

https://www.deepgcns.org

TensorFlow Repo

Pytorch Repo

500+ Stars

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

78 of 82

Follow-up works

DeepGCNs.org

Sub-Graph Detection for Temporal Action Detection. Mengmeng xu. et al.

​

GCN for 3D Vehicle Detection on LiDAR. Jesue Zarzar. et al.

GraphSR: Towards Super-Resolution Modules for Graphs. Guocheng Qian

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

79 of 82

Our team

DeepGCNs.org

Guohao Li

Matthias Müller

Ali Thabet

Bernard Ghanem

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

80 of 82

Our team

DeepGCNs.org

Guohao Li

Matthias Müller

Ali Thabet

Bernard Ghanem

Guocheng Qian

Itzel C. Delgadillo

Abdulellah Abualshour

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

81 of 82

Thank You

Poster ID: 12

Project website: https://www.deepgcns.org

Preprint Paper: https://arxiv.org/abs/1904.03751

DeepGCNs.org

82 of 82

VCC

VISUAL

COMPUTING

CENTER

​

IVUL

DeepGCNs.org

DeepGCNs: Can GCNs go as deep as CNNs?

Guohao Li*, Matthias Müller*, Ali Thabet, Bernard Ghanem

* equal contribution

Poster ID: 12