Understanding and Improving Graph Convolutional Networks

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering

Final Year Thesis Oral Defense

Title: "Understanding and Improving Graph Convolutional Networks"

by

DING Mucong

Abstract:

The adoption of deep learning onto graph data has been lagging behind 
until the recent development of graph convolutional network (GCN), which 
nicely integrate the node features and graph topology by neighborhood 
aggregation. Although GCN compares favorably with other state-of-the-art 
methods, its mechanisms remain unclear and it fails in going deep (known 
as the over-smoothing problem): experimental studies have shown that with 
the increase in the number of layers, the model performance drops 
significantly.

In this thesis, we theoretically analyze the mechanism of GCN and try to 
generalize the framework to tackle its intrinsic shortcoming. First, we 
introduce the over-smoothing problem which forbids us building deep GCN 
model. Inspired by the research which compares GCN with Laplacian 
smoothing, we decompose the mathematical operation of GCN into two parts: 
graph convolution among vertices and fully connected network (FCN) on 
features. We also compare GCN with random walks on graph, and propose a 
generalized definition of GCN which accepts all kinds of non-conservative 
broadcasting (e.g. Laplacian smoothing) or conservative diffusion (e.g. 
random walk) on the graph as the convolution operation. Based on the 
generalized framework, we can convenient explain the over-smoothing effect 
using spectral graph theory. Equipped with these understandings, we 
propose two preliminary solutions to the over-smoothing problem: (1) 
slowing down the smoothing by adding an adjustable parameter (Slowed GCN), 
(2) using a learnable generalized graph Laplacian instead of the fixed one 
(Parameterized GCN). Experiments show both methods can outperform GCN by a 
margin in some circumstances, however, they are still not promising in 
effectively learning global structural features and achieving better 
performance when going deep. Comparisons between the original GCN, fully 
connected network (FCN), and the two generalized models are done on the 
Zachary's Karate Club network and the Cora Machine Learning Citation 
network in terms of their embedding quality and prediction accuracy.


Date            : 2 May 2019 (Thursday)

Time            : 15:30 - 16:10

Venue           : Room 5510 (near lifts 25/26), HKUST

Advisor         : Prof. KWOK Tin-Yau James

2nd Reader      : Dr. WONG Raymond Chi-Wing