Progressive Graph Convolutional Networks for Semi-Supervised Node Classification
Negar Heidari Alexandros Iosifidis
cs.LG stat.ML






Progressive Graph Convolutional Networks
for Semi-Supervised Node Classification
    Negar Heidari and Alexandros Iosifidis

Department of Electrical and Computer Engineering, Aarhus University, Denmark

Emails: {negar.heidari, alexandros.iosifidis}@ece.au.dk
    Received: date / Accepted: date
==================================================================================================================================================================================




Graph convolutional networks have been successful in addressing graph-based tasks such as semi-supervised node classification. Existing methods use a network structure defined by the user based on experimentation with fixed number of layers and neurons per layer and employ a layer-wise propagation rule to obtain the node embeddings. Designing an automatic process to define a problem-dependant architecture for graph convolutional networks can greatly help to reduce the need for manual design of the structure of the model in the training process. 
In this paper, we propose a method to automatically build compact and task-specific graph convolutional networks. Experimental results on widely used publicly available datasets show that the proposed method outperforms related methods based on convolutional graph networks in terms of classification performance and network compactness.



Graph-based Learning, Graph Convolutional Networks, Progressive Learning, Semi-Supervised Learning










§ INTRODUCTION


Convolutional Neural Networks (CNNs) <cit.>, as an end-to-end deep learning paradigm, have been very successful in many machine learning and computer vision tasks <cit.>.
While CNNs have high ability to extract latent representations and local meaningful statistical patterns from data, they can only operate on Euclidean data structures such as audio, images and videos which have a form based on 1D, 2D and 3D regular grids, respectively. Recently, there has been an increasing research interest in applying deep learning approaches on non-euclidean data structures, like graphs, which lack geometrical properties, but have high ability to model complex irregular data such as social networks <cit.> citation networks and knowledge graphs <cit.>. 

Motivated by CNNs, the notion of convolution was generalized from grid data to graph structures, which correspond to locally connected data items, by aggregating the node's neighbors' features with its own features <cit.>. Combining such convolutional operator with a data transformation process and hierarchical structures Graph Convolutional Networks (GCNs) are obtained, which can be trained in an end-to-end fashion to optimize an objective defined on individual graph nodes, or the graph as a whole. As an example, the GCN method proposed in <cit.> is a semi-supervised node classification method consisting of two convolutional layers. Each graph convolutional layer learns nodes' features by applying aggregation rule on their corresponding first-order neighbors.
The graph structure can also be learned dynamically <cit.>. 
GCNs, have been successful in various graph mining tasks like node classification, <cit.>, graph classification <cit.>, link prediction <cit.>, and visual data analysis <cit.>. 

One of the main drawbacks of existing GCN-based methods is that they require an extensive hyper-parameter search process to determine a good topology of the network. This process is commonly based on extensive experimentation involving the training of multiple GCN topologies and monitoring their performance on a hold-out set. To avoid such a computationally demanding process, a common practice is to empirically define a network topology and use it for all examined problems (data sets). As an example, a two layer GCN model cannot gain sufficient global information by aggregating the information from just a two-hop neighborhood for each node. Meanwhile, in the reported results of <cit.> it has been shown that adding more layers makes the training process harder and does not necessarily improve the classification performance. It was also shown that the topology of the GCN plays a crucial role in performance which is related to the underlying difficulty of the problem to be solved <cit.>.

Problem-specific design of the neural networks' architecture contributes in improving the performance and the efficiency of a learning system. Recently, methods of finding an optimized network topology have been receiving much attention and many works were proposed to define compact network topologies by employing various learning strategies, such as compressing pre-trained networks, adding neurons progressively to the network, pruning the network's weights and applying weight quantization <cit.>. However, all these methods work with grid data in Euclidean spaces. In this regard, learning a compact topology for GCNs makes a step towards increasing the training efficiency and reducing the computational complexity and storage needed while achieving comparable performance with existing methods. 

In this paper, we propose a method to jointly define a problem-specific GCN topology and optimize its parameters, by progressively growing the network's structure both in width and depth. The contributions of our work are:


	
  * We propose a method to learn an optimized and problem-specific GCN topology progressively without user intervention. The resulting networks are compact in terms of number of parameters, while performing on par, or even better, compared to other recent GCN models. 
	
  * We provide a convergence analysis for the proposed approach, showing that the progressively building GCN topology is guaranteed to converge to a (local) minimum.
	
  * We conduct experiments on widely-used graph datasets and compare the proposed method with recently proposed GCN models to demonstrate both the efficiency and competitive performance of the proposed method. Our experiments include an analysis of the effect of the network's complexity with respect to the underlying complexity of the classification problem, highlighting the importance of network's topology optimization.


The rest of the paper is organized as follows: Section <ref> provides a description of graph-based semi-supervised classification, along with the terminology used in this paper. Section <ref> reviews the GCN method <cit.> as the baseline method of our work. The proposed method is described in detail in section <ref>. The conducted experiments are described in section <ref>, and conclusions are drawn in Section <ref>. 



§ SEMI-SUPERVISED GRAPH-BASED CLASSIFICATION

Let G = (𝒱 ,ℰ) be an undirected graph where 𝒱 and ℰ denote the set of nodes ν_i∈𝒱,  i=1,…,N and the set of edges (ν_i,ν_j)∈ℰ, respectively. 𝐀∈ R^N× N denotes the adjacency matrix of G encoding the node connections. The elements 𝐀_ij can be either binary values, indicating presence or absence of an edge between nodes ν_i and ν_j, or real values encoding the similarity between ν_i and ν_j, based on a similarity measure. Using 𝐀, we define the degree matrix 𝐃 which is a diagonal matrix with elements equal to 𝐃_ii = ∑ _j𝐀_ij. Each node of the graph ν_i is also equipped with a representation 𝐱_i ∈ℝ^D, which is used to form the feature vector matrix 𝐗∈ R^N× D. When such a feature vector for each graph node is not readily available for the problem at hand (e.g. in the case of processing citation graphs), vector-based node representations are learned by using some node embedding method, like <cit.>. 

Traditional graph-based semi-supervised node classification methods <cit.>, learn a mapping from the nodes' feature vectors to labels, which for a C-class classification problem are usually represented by C-dimensional vectors following the 1-of-C encoding scheme. This mapping exploits a graph-based regularization term and it commonly has the form:

    ℒ = ℒ _L(f(𝐗_L), 𝐓_L) + λ f(𝐗)^T𝐋 f(𝐗),

where f(·) denotes the learnable function mapping the D-dimensional node representations to the C-dimensional class vectors, 𝐓_L is a matrix formed by the class label vectors of the labelled nodes which form the matrix 𝐗_L, and 𝐋 = 𝐃 - 𝐀 is the unnormalized graph Laplacian matrix. The first term in (<ref>) is the classification loss of the trained model measured on the labelled graph nodes, and the second term corresponds to graph Laplacian-based regularization incorporating a smoothness prior to the optimization function ℒ. λ > 0 expresses the relative importance of the two terms. By following this approach the labels' information of the labelled graph nodes is propagated over the entire graph. 



§ GRAPH CONVOLUTIONAL NETWORKS


GCNs are mainly categorized into spatial-based and spectral-based methods. 
The spatial-based methods update the features of each node by aggregating its spatially close neighbors' feature vectors. In these methods, the convolution operation is defined on the graph with a specified neighborhood size which propagates the information locally <cit.>. 

The spectral-based GCN methods follow a graph signal processing approach <cit.>. Let us denote by G_θ a filter and by 𝐗 a multi-dimensional signal defined over the N nodes of the graph. The signal transformation using G_θ is given by: 

    G_θ⋆𝐗 = 𝐔 G_θ𝐔^T𝐗,

where ⋆ denotes the convolution operator, 𝐔 is the matrix of eigenvectors of the normalized graph Laplacian 𝐋̃ = 𝐈_N - 𝐃^-1/2𝐀𝐃^-1/2 = 𝐔Λ𝐔^T with Λ being a diagonal matrix having as elements the corresponding eigenvalues, and 𝐔^T 𝐗 being the graph Fourier transform of 𝐗. Since computing the eigen-decomposition of 𝐋̃ is computationally expensive, low-rank approximations using truncated Chebyshev polynomials have been proposed <cit.>. The transformation in (<ref>) corresponds to the building block of a GCN. Followed by an element-wise activation it forms a GCN layer.

The multilayer GCN for semi-supervised node classification was proposed in <cit.> by stacking multiple GCN layers. To achieve a fast and scalable operation a first-order approximation of the spectral graph convolution is proposed leading to:

    G_θ⋆𝐗≈𝐃̃^-1/2𝐀̃𝐃̃^-1/2𝐗𝐖,

where 𝐀̃ = 𝐈_N + 𝐀 and 𝐃̃_ii = ∑_j 𝐀̃_ij. Let us denote by 𝐇^(l) the graph node representations at layer l of the multi-layer GCN. The propagation rule for calculating the graph node representations at layer l+1 is given by:

    𝐇^(l+1) = σ(𝐃̃^-1/2𝐀̃𝐃̃^-1/2𝐇^l𝐖^(l)),

where 𝐖^(l) is the l^th layer weight matrix and σ(·) denotes the activation function, such as ReLU(·), or softmax(·) used for the output layer. For a two layer GCN model this leads to:

    𝐘 = softmax(𝐀̂  ReLU(𝐀̂𝐗𝐖^(1)) 𝐖^(2)),

where 𝐀̂ = (𝐃̃^-1/2𝐀̃𝐃̃^-1/2) and 𝐘∈ℝ^N× C denotes the predicted feature vectors for all the N graph nodes in C classes. The model parameters (𝐖^(0),𝐖^(1)) are finetuned by minimizing the cross entropy loss over the labeled nodes.

One of the drawbacks of all existing GCN methods is that they use a predefined network topology, which is selected either based on the user's experience, or empirically by testing multiple network topologies. In the next section, we describe a method for automatically determining a problem-specific compact GCN topology based on a data-driven approach.






§ PROGRESSIVE GRAPH CONVOLUTIONAL NETWORK
 
PGCN follows a data-driven approach to learn a problem-dependant compact network topology, in terms of both depth and width, by progressively building the network's topology based on a process guided by its performance. That is, the learning process of GCN jointly determines the network's topology and estimates its parameters to optimize the cost function defined at the output of the network. 

The learning process starts with a single hidden layer formed by one block of B neurons equipped with an activation function (e.g. ReLU(·)) and an output layer with C neurons. At iteration t=1, the synaptic weight matrix 𝐖_1^(1)∈ℝ^D× B connecting the input layer to the hidden-layer neurons is initialized randomly. The graph nodes' representations defined at the outputs of the hidden layer 𝐇_1^(1)∈ℝ^N× B, where the index indicates that the one block of B hidden-layer neurons is used, are obtained by using graph convolution:

    𝐇_1^(1)=ReLU(𝐀̂𝐗𝐖_1^(1)).

By setting 𝐇^(1) = 𝐇_1^(1), the network's output for all graph nodes 𝐘∈ℝ^N × C is calculated using a linear transformation as follows: 

    𝐘 = 𝐇^(1)𝐎

where 𝐎∈ℝ^B × C denotes the weight matrix connecting hidden layer to the output layer. The transformation matrix 𝐎 can be calculated by minimizing the regression problem:

    𝒥_1 = 1/2 Tr(𝐎^T𝐎) + λ_1/2𝐇_L^(1)𝐎 - 𝐓_L_F^2,

where Tr(·) denotes the trace operator, λ_1 > 0 denotes the relative importance of model loss, 𝐇_L^(1) denotes the hidden layer representations of the labeled graph nodes and 𝐓_L∈ℝ^N × C is a matrix formed by the labeled nodes' target vectors.

To exploit the information in both the labeled and unlabeled nodes' feature vectors in 𝐇^(1), we can replace the linear regression problem in (<ref>) by a semi-supervised regression problem exploiting the smoothness assumption of semi-supervised learning 
<cit.> expressed by the term:

    f(X)^T𝐋 f(X)
    = Tr(𝐎^T (𝐇^(1))^T 𝐋̃𝐇^(1)𝐎).

Minimization of (<ref>) with respect to 𝐎 leads to node feature vectors at the output of the network which are similar for nodes connected in the graph. To incorporate this property in the optimization problem of (<ref>) the term in (<ref>) is added as a regularizer. Thus, 𝐎 is obtained by minimizing: 

    𝒥_2 = 1/2 Tr(𝐎^T𝐎) + λ_1/2𝐇_L^(1)𝐎 - 𝐓_L_F^2
    
        + λ_2/2N^2 Tr(𝐎^T (𝐇^(1))^T 𝐋̃𝐇^(1)𝐎) ),

where N is the number of all (labeled and unlabeled) graph nodes and λ_2 denotes the relative importance of Laplacian regularization and is set to 1/N^2 which is the natural scale factor to estimate the Laplacian operator empirically <cit.>.

The optimal solution of (<ref>) is obtained by setting ∂𝒥_2/∂𝐎 = 0, and is given by:


    𝐎   =  ( (𝐇^(1))^T (𝐈_N+λ _2/λ _1N^2𝐋̃)𝐇^(1)+1/λ _1𝐈_D^(1) )^-1
       · (𝐇_L^(1))^T𝐓_L


where 𝐈_N∈ℝ^N × N and 𝐈_D^(1)∈ℝ^D^(1)×D^(1) are identity matrices. D^(1) denotes the feature dimension of the first hidden layer which is equal to B in the first iteration. 

After the initialization of both the hidden layer and output layer weights, these are finetuned based on Backpropagation using the loss of the model on the labeled graph nodes. Finally, the model's performance (classification accuracy on the labeled nodes) 𝒜_1 is recorded.

At iteration t=2, the network's topology grows by adding a second block of B hidden layer neurons. We initialize the weights 𝐖_1^(1) connecting the input layer to the first block of hidden layer neurons with finetuned values obtained at iteration t=1, while the weight matrix of the newly added block 𝐖_2^(1) is initialized randomly. The hidden layer representations corresponding to the newly added neurons 𝐇_2^(1) are calculated as in (<ref>) by replacing 𝐖_1^(1) with 𝐖_2^(1). Then, we combine 𝐇^(1) = [𝐇_1^(1), 𝐇_2^(1)] and the output weight matrix 𝐎 is calculated by using (<ref>). 
At this iteration, D^(1) = B+B and 𝐇^(1), 𝐎 are of size N × D^(1) and D^(1)× C, respectively. 


After finetuning all the parameters 𝐖_1^(1), 𝐖_2^(1), 𝐎, and recording the model's performance, the network's progression is evaluated based on the rate of performance improvement given by:

    r=𝒜_2- 𝒜_1/𝒜_1,

where 𝒜_1 and 𝒜_2 denote the model's performance before and after adding the second block of hidden layer neurons. 
If the addition of the second GCN block does not improve the model's performance, i.e. when r < ϵ, the newly added block is removed, and all the model parameters are set to the finetuned values which were obtained at previous iteration. At this point, the progression in the current hidden layer terminates. 

After stopping the progressive learning in the first hidden layer, a new hidden layer is formed which takes as input the previous hidden layers' output. The block-based progression of the newly added hidden layer starts by using a single block of B neurons and repeats in the same way as for the first hidden layer until model's performance converges. 






Let us assume that at iteration t=k, the network's topology comprises of l layers (the input layer corresponds to l=0) and it is growing at the (l+1)^th layer giving as outputs 𝐇^(l+1). Before adding the b^th block formed by B neurons, the weights of all the existing blocks in the network are set to the finetuned values obtained in the previous step. The newly added block in the (l+1)^th hidden layer takes the output of the previous hidden layer 𝐇^(l) as input, and the graph convolutional operation for the b^th block is given by: 

    𝐇_b^(l+1)=ReLU(Â𝐇^(l)𝐖_b^(l+1))

where 𝐇_b^(l+1) and 𝐖_b^(l+1) denote the hidden representation of the newly added block and the randomly initialized synaptic weights connecting the l^th hidden layer to b^th block of (l+1)^th layer, respectively. 
Given 𝐇^(l+1) = [𝐇^(l+1), 𝐇_b^(l+1)] which denotes the hidden representations formed by using both the existing blocks and the newly added block in the (l+1)^th hidden layer, the models' output 𝐘∈ℝ^N × C is calculated using a linear transformation as follows: 

    𝐘 = 𝐇^(l+1)𝐎

where 𝐎∈ℝ^D^(l+1)× C denotes the transformation matrix which is calculated based on semi-supervised linear regression:


    𝐎   =  ( (𝐇^(l+1))^T (𝐈_N +λ _2/λ _1N^2𝐋̃)𝐇^(l+1) + 
    1/λ _1𝐈_D^(l+1))^-1
       · (𝐇_L^(l+1))^T𝐓_L.




Similar to other GCN-based methods, the linear transformation for calculating the models' output in (<ref>) (and (<ref>), respectively) can also be followed by softmax activation (on a node basis) as follows:

    𝐘 = softmax(𝐇^(l+1)𝐎),

and instead of Mean Squared Error (MSE), the Cross-Entropy (CE) loss function can be employed for finetuning the model. 

After the initialization step, the synaptic weights of the existing blocks and all the weight parameters of the newly added block are finetuned with respect to the labeled data using (<ref>). 
The model diagram is shown in Fig. <ref> which indicates the progressive learning process in (l+1)^th layer where a new block is added and after initializing its weights (dashed lines), all the model parameters are finetuned together. Fig. <ref> indicates the graph convolution process which is applied on graph node by a block of the B neurons. This convolution process gets as input the hidden representation matrix of nodes at layer l, 𝐇^(l), and outputs the representation matrix 𝐇^(l+1) at layer l+1. 

To evaluate the network's progression, the model's performance is recorded and the rate of the improvement is given by:

    r_b=𝒜_b- 𝒜_b-1/𝒜_b-1

where 𝒜_b-1 and 𝒜_b denote the classification accuracy before and after adding the b^th block, respectively. 
If the addition of a new GCN block in step k does not improve the model's performance, i.e. when r_b < ϵ_b, the progression of the (l+1)^th layer terminates and all the network parameters are set to the finetuned values obtained in the previous step with b-1 blocks. 
After stopping the block progression for the (l+1)^th layer, the algorithm evaluates whether the network's performance converged using the rate of the performance before and after adding the new hidden layer:

    r_l+1=𝒜_l+1- 𝒜_l/𝒜_l.

When r_l < ϵ_l, the last hidden layer l+1 is removed and the algorithm stops growing the network's topology. 
Here we should note that it is also possible to use other performance metrics, such as model loss, to evaluate the network progression process in (<ref>) and (<ref>).

Algorithm <ref> summarizes the PGCN algorithm. In <ref>, we show that the proposed approach of building GCN layers in a progressive manner converges.










§ EXPERIMENTS
 


 §.§ Datasets

We evaluated the proposed method for semi-supervised node classification task following transductive setting, on three widely-used benchmark datasets, Citeseer, Cora and Pubmed <cit.>, which are standard citation networks.

The citation networks represent published documents as nodes and the citation links between them as undirected edges. Each node in a citation network is represented by a sparse binary Bag-of-Words (BoW) feature vector extracted from articles' abstract and a class label which represents the articles' subject. The symmetric binary adjacency matrix 𝐀 is built using the list of  undirected edges between the nodes and the task to be solved is the prediction of the articles' subject based on the BoW features and their citations to other articles. 

To perform a fair comparison, we follow the same experimental setup as in <cit.> for data configuration and preprocessing.  
The detailed datasets statistics are summerized in Table. <ref>.
For training the model, 20 labeled nodes per class are used for each citation network. In Table. <ref>, label rate denotes the number of training labeled nodes divided by the total number of nodes for each dataset. 
In all datasets, the validation set contains 500 randomly selected samples and the trained model is evaluated on 1000 test nodes.  
The labels of validation set are not used for training the model. Following the transductive learning setup, only the labeled nodes of the training set but all the feature vectors are used for training. The feature vectors are row-normalized. 








 §.§ Competing Methods

We compared the proposed method with the baseline GCN <cit.> and related methods N-GCN <cit.>, GAT <cit.>, GraphNAS <cit.> and Auto-GNN <cit.>. 
N-GCN <cit.> trains a network of GCNs over the neighboring nodes discovered at different distances in random walk. Each GCN module uses a different power of adjacancy matrix 𝐀 like { GCN(𝐀̂^0), GCN(𝐀̂^1), GCN(𝐀̂^2), ..., GCN(𝐀̂^k)}, where 𝐀̂^k indicates the statistics collected from the k^th step of a random walk on the graph. It combines the information from different graph scales by using the weighted sum or the concatenation of all the GCNs' outputs into a final classification layer and finetunes the entire model for semi-supervised node classification. The graph attention network (GAT) <cit.> introduces attention mechanism to GNNs. It assigns different weights to different neighboring nodes implicitly by employing self-attention through an end-to-end neural network architecture. The attention coefficients are shared across all graph edges, so there is no need to capture global graph structure. 

GraphNAS <cit.> and Auto-GNN <cit.> are the most related works to ours which employ neural architecture search (NAS) mechanism to find the best graph neural network architecture automatically. GraphNAS utilizes a recurrent neural network (RNN) as a controller which generates the descriptions of different GNN architectures. The RNN is trained with reinforcement learning which gives feedback, like reward or penalty, to the controller in order to maximize the expected accuracy of the generated GNN architecture.  

Auto-GNN <cit.> is also a NAS-based method which designed a novel parameter sharing method for GNN homogeneous architectures and uses an efficient RNN controller to capture the variations of data representation in GNN which are produced by small modifications made in GNN architecture during the search process. 



 §.§ Experimental settings


We implemented our method in tensorflow <cit.> and trained it using Adam optimizer <cit.> for 300 epochs with learning rate of 0.01. The network weight parameters are initialized randomly using uniform distribution. To handle the effect of randomness on network performance, we ran it 20 times on each dataset. For each dataset, the set of hyper-parameters which leads to best validation performance is selected and the corresponding performance on test set and architectural information are reported. To avoid overfitting, dropout <cit.> and regularization techniques are employed. The L_2 regularization factor is set to 0.0005.
The dropout rate is selected from { 0.1, 0.3, 0.5 } and we apply dropout on the output of hidden layers, not on input features. The regularizer λ_1 is selected from { 10^-1, 1, 10^1} and the size of the block B is selected from {1,5,10,15,20 }. The maximum topology of the network is limited to 10 layers with 100 neurons per layer and the threshold values are set to ϵ_l = ϵ_b = 0.0001. 

The baseline and competing methods also optimized the hyper-parameters on the same data splits. 
The test performance of these methods are reported directly from their papers.
GCN method optimized the hyper-parameters on Cora dataset and used the same set of hyper-parameters for Citeseer and Pubmed datasets too. The two layer GCN is trained for 200 epochs using Adam optimizer with a learning rate of 0.01 and early stoping of step size 10.
GCN with dropout rate of 0.5, hidden layer of 16 neurons and L_2 regularization of 0.0005 is applied on citation datasets. 


N-GCN uses Adam optimizer with learning rate of 0.01 for 600 epochs and L_2 regularization factor is set to 0.001. This method uses a fixed architecture for all datasets. It has 4 blocks of GCN which use different powers of Â: Â^0, Â^1, Â^2, Â^3. Each GCN, as a two layer network with 10 hidden neurons, is replicated three times and the weighted sum of the outputs is introduced to the final classification layer. Similar to our experimental settings, N-GCN is run using 20 different random initializations and the test performance of the model with the highest accuracy on the validation set is reported. 

In GAT method, the hyper-parameters are optimized on Cora dataset and then reused for Citeseer dataset. The L_2 regularization factor and the dropout rate are set to 0.0005, 0.6 respectively for Citeseer and Cora datasets. For pubmed dataset the L_2 regularization factor is set to 0.001. The dropout is applied on both input feature vectors and hidden layers output. 
GAT uses a two layer network architecture. The first layer consists of 8 attention heads, each computing 8 features, followed by ELU <cit.> activation function and the second layer is a single attention head computing C features followed by softmax activation function. The reported results for GAT method is the average of the classification accuracy on the test set after 100 runs. 

The NAS-based methods, GraphNAS and Auto-GNN, train a one-layer LSTM with 100 neurons as a controller using Adam optimizer with a learning rate of 0.0035. The models which are sampled by the controller are trained for 200 epochs with the same hyper-parameter setting used in N-GCN. These methods explore only 2-layer GCN models in their predefined search space which leads to a constrained representation learning capacity for model. 

Both methods totally explore 1000 different architectures to find the optimal graph neural architecture which achieves the best classification accuracy on the validation set. The reported results for GraphNAS method is the average performance of the top 5 architectures on test set and the Auto-GNN method randomly initializes the best found architecture 5 times and reports the average classification accuracy on test set. 
The Auto-GNN method is able to train the models with parameter sharing by transferring the finetuned weights, to a newly sampled architecture while the GraphNAS doesn't employ parameter sharing mechanism and it has a high computational and time complexity for training all 1000 different models from scratch. The results of Auto-GNN method both with and without using parameter sharing mechanism are reported in Table. <ref>. 



 §.§ Results

Table. <ref> shows the performance in terms of classification accuracy for all the methods on the 3 datasets. The best performance is shown in bold fonts for each dataset. 

We evaluate our method with both Cross Entropy (CE) and Mean Squared Error (MSE) loss functions. 
The obtained results in Table. (<ref>) indicate that the proposed method has outperformed the baseline GCN method and other competing methods on Citeseer and Pubmed datasets and it has competitive performance with competing methods on Cora dataset. 
In order to compare the efficiency of our method with competing methods, especially the NAS-based methods, the model sizes, i.e., the number of model parameters, of all trained models are reported in Table. <ref>. Table. <ref> also shows the model architectures which are learned by our proposed method and the fixed model architectures used by the baseline method GCN. 
The results indicate that the network topologies which are learned by the proposed method on all datasets are much more compact compared to the fixed network topologies used by baseline methods, while the classification performance of our compact model is similar or better than others. 
Although the NAS-based methods achieve competitive performance, exploring 1000 different architectures even by using a parameter sharing mechanism leads to an extremely high computation and time cost. To make their application tractable, their practical implementations restrict the search space by fixing the number of hidden layers to 2. Thus, there is no guarantee that they can reveal an optimal topology of the network for achieving a good classification performance on large and complex graph datasets. Contrary to that, the proposed method can efficiently determine the network's topology by determining both the number of layers and neurons per layer.









Fig. <ref> illustrates the t-SNE visualization of learned feature vectors of the Cora dataset from last layer of network before applying the softmax activation. 








 §.§ Analysis on Dataset Statistics

The results of the previous section indicate that all the competing methods perform on par with the baseline GCN which has a simple network architecture. This can be explained by the benchmark dataset statistics. The dataset complexity is defined by the number of labeled nodes N_L and the dimentionality of nodes' feature vectors D, and the ratio N_L/D is extremely small for all the benchmark datasets of Table. <ref>. 
It has been recently shown that even the heavily regularized linear methods can obtain high performance on classification problems on datasets with low complexity <cit.>. Therefore, all the GCN-based methods, with simple or sophisticated network structures, can lead to comparable performance on these widely used benchmark datasets. In  <cit.>, it has been experimentally shown that the performance of the GCN-based methods heavily depends on the underlying difficulty of the problem and non-linear models with more complex structure perform significantly better on datasets with higher N_L/D ratio. That is, it is expected that the difference in performance of various methods will increase when the underlying semi-supervised classification problem becomes more complex.

Here we highlight the importance of optimizing the network structure based on the problem's complexity. We compare the performance of the proposed method with the baseline method GCN <cit.>, by tuning the ratio N_L/D using different input data dimensionalities when 50% of nodes are labeled. We use the same data splits for both methods and follow the same approach as in <cit.> to control the ratio N_L/D by mapping the input data representations to a subspace through random projections. Specifically, we use a random sketching matrix 𝐌_r∈ℝ^D × D' with D' < D, which is drawn from a Normal distribution, to obtain new data representations 𝐗^'∈ℝ^D' as follows: 

    𝐗^' = 1/√(D^')𝐗𝐌_r.

To avoid bias of the performance values obtained for different values of D', we first randomly sample a square matrix 𝐌^'∈ℝ^D × D and subsequently we use its first r = D' columns to map the input data from ℝ^D to its subspace ℝ^D'. Such an approach guarantees that when a subspace of a higher dimensionality is used, it corresponds to an augmented version of the initial (lower-dimensional) subspace. We applied three experiments for each choice of D^' on each dataset and we report the performance on the test data corresponding to the best validation performance. 


Fig. <ref> compares the classification performance of GCN and PGCN methods on all datasets when problems of different difficulty are considered. It can be observed that for all data dimensionalities, our method performs better than the baseline method, while they have a larger difference in classification accuracy in lower dimensionalities, i.e. when the ratio N_L/D is higher. This is in line with the findings of <cit.> indicating that in high-dimensional feature spaces neural network structures tend to perform in similar manners irrespectively to their complexity. On the other hand, when the classification problem is encoded in lower-dimensional feature spaces and, thus, becomes more complex, the structure of the neural network's topology is important. Indeed, as can be observed in Fig. <ref>b, PGCN outperforms GCN with a high margin when the dimensionality D^' of the node representations is low. The comparison of model complexity with respect to number of trainable parameters in Fig. <ref>c shows that both methods have similar complexity when lower-dimensional feature spaces are used on Citeseer and Cora datasets, while PGCN outperforms GCN in terms of classification perfromance. For Pubmed dataset, PGCN outperforms GCN in terms of both model complexity and classification performance in all cases. 



§ CONCLUSION

In this paper, we proposed a method for progressively training graph convolutional networks for semi-supervised node classification which jointly defines a problem-dependant compact topology and optimizes its parameters. The proposed method employs a learning process which utilizes the input to each layer data to grow the network's structure both in terms of depth and width. This is achieved by operating an efficient layer-wise propagation rule leading to a self-organized network structure exploiting data relationships expressed by their vector representations and the adjacency matrix of the corresponding graph structure. Experimental results on three commonly used datasets for evaluating graph convolutional networks on semi-supervised classification indicate that the proposed method outperforms the baseline method GCN and performs on par, or even better, compared to more complex recently proposed methods in terms of classification performance and efficiency. 






§ PROOF OF CONVERGENCE

Here we show that the progressive learning in each layer of the PGCN method converges. Lets assume that 𝐇_k^(l) = [𝐡_1^(l), ..., 𝐡_k^(l)] ∈ℝ^N× (D_1^(l)+...+D_k^(l)) denotes the hidden representations of data produced by using the first k blocks in l^th GCN layer and 𝐎_k^(l)∈ℝ^(D_1^(l)+...+D_k^(l)) × C denotes the finetuned weights connecting all the k blocks of l^th layer to the output layer. We prove that the sequence of graph-regularized MSE, E_k^(l)∈ℝ obtained with 𝐇_k^(l) and 𝐎_k^(l) is monotonically decreasing while it is bounded below by 0.

Given the fixed hidden representation 𝐇_k^(l), the finetuned output weights 𝐎_k^(l) are not necessarily the optimized weights in terms of MSE. 
It can be explained by the following relation: 


    E_k^(l)   = 1/2 Tr(𝐎_k^(l)^T𝐎_k^(l)) 
    + λ_1/2𝐇_L_k^(l)𝐎_k^(l) - 𝐓_L_2^2
       ≥1/2 Tr(𝐎_k^*(l)^T𝐎_k^*(l)) + λ_1/2𝐇_L_k^(l)𝐎_k^*(l) - 𝐓_L_2^2,

where 𝐎_k^*(l) denotes the optimized output weights which are obtained by solving the semi-supervised linear regression problem as follows: 

    𝐎_k^*(l)   =  ( (𝐇_k^(l))^T (𝐈+λ _2/λ _1N^2𝐋̃)𝐇_k^(l)+1/λ _1𝐈_D^(l) )^-1
       ·(𝐇_L_k^(l))^T𝐓_L.


In the next step, when the (k+1)^th block is added to the l^th layer, the new hidden representation of l^th layer would be 𝐇_k+1^(l) =  [ 𝐇_k^(l), 𝐡_k+1^(l)] in which 𝐇_k^(l) is fixed from previous step and 𝐡_k+1^(l) is generated by new randomly initialized weights. The new optimal output weights Ô_k+1^(l)∈ℝ^(D_1^(l)+...+D_k+1^(l)) × C which connect the l^th layer to output layer is initialized according to (<ref>) by substituting 𝐇_k^(l) by 𝐇_k+1^(l). The MSE after adding the (k+1)^th block would be as follows: 

    ℰ_k+1^(l)   =
    1/2 Tr(Ô_k+1^(l)^TÔ_k+1^(l)) + λ_1/2𝐇_L_k+1^(l)Ô_k+1^(l) - 𝐓_L_2^2
       ≤1/2 Tr(Õ^TÕ) + λ_1/2𝐇_L_k+1^(l)Õ- 𝐓_L_2^2
       ∀Õ∈ℝ^(D_1^(l)+...+D_k+1^(l)) × C.


Since (<ref>) holds for all Õ, we can replace 𝐇_k+1^(l), Õ with [ 𝐇_k^(l), 𝐡_k+1^(l) ], [ 𝐎_k^*(l);        0 ] respectively to obtain the following relation:  

    ℰ_k+1^(l)   ≤1/2 Tr(
             [ 𝐎_k^*(l)^T, 0  ]
            [ 𝐎_k^*(l);        0 ]) 
       + λ_1/2 [ 𝐇_k^(l), 𝐡_k+1^(l) ]
            [ 𝐎_k^*(l);        0 ] 
     - 𝐓_L_2^2
       = 1/2 Tr(
    𝐎_k^*(l)^T𝐎_k^*(l)) + λ_1/2𝐇_k^(l)𝐎_k^*(l) 
    - 𝐓_L_2^2
       ≤E_k^(l).


After finetuning the network parameters, the output weights are denoted by 𝐎_k+1^(l) and the MSE would be E_k+1^(l). It has been proven that stochastic gradient descent converges to a local optimum <cit.> with small enough learning rate, so the following relation holds for the MSE:  


    E_k+1^(l)≤ℰ_k+1^(l).

According to (<ref>), (<ref>) we have the following relation:

    E_k+1^(l)≤E_k^(l),

which indicates that the sequence (E_k^(l))_{k} is monotonically decreasing. 

Based on the connection of the linear activation function combined with the mean-square error to the soft-max activation function combined with the cross-entropy criterion and maximum likelihood optimization <cit.>, an analysis following the same steps as above can be used to show that (when the latter is employed) the sequence E_k^(l) is also monotonically decreasing. 

IEEEtran


