Topology Optimization based Graph Convolutional Network

1 Introduction

Objects in real world, which is usually modeled by nodes in typical graphs/networks, are likely to be connected in various approaches. For example, people are connected through social network and online social networks. Computers are connected via intranets and Internet. Proteins are connected by the existence of electrostatic forces. To explore the characteristics and mechanisms of these networks, network analysis is introduced [Newman, 2003]. In network analysis, node classification, which is also named as network partition, community detection and graph clustering, is one of the most widely studied topic [Fortunato, 2010; Fortunato and Hric, 2016; Tao et al., 2017].

∗Corresponding author.

Figure 1: The difference between Graph Convolutional Networks (GCN) and our proposed TO-GCN. Learnable variables are shown with a background color. GCN takes the given network topology A and node feature X as input and only learns the parameters of FCNW with label Z. TO-GCN jointly learns the network topology O (red line and disk) and the parameters of the FCN W to fully explore the labels information Z.

Classical node classification is developed based on the utilization of the network topology. Although they contribute significantly in understanding the characteristics and mechanisms of the networks, their performances are typically unsatisfactory due to the sparsity properties of the networks and the noises in the networks. To improve the performances, numerous side information is adopted. Among them, label and content information are the most commonly utilized [Tu et al., 2016; Yang et al., 2013]. By effectively exploiting the labels and network topology, label propagation [Zhu et al., 2003] achieves a great performance boost. Many algorithms are later proposed to utilize the pairwise constraint information, which is another kind of supervised information in the form of must-link and cannot-link [Lu and Peng, 2013]. By exploring the correlations between node feature and network topology structure, node classification task in attributed networks has achieved great success and performance improvement [Wang et al., 2016].

Recently, many efforts have been made to resolve the task of semi-supervised node classification in attributed networks, which predicts the labels by exploiting the network topology, node features and labels. Motivated by the success of deep learning [Goodfellow et al., 2016], especially the convolutional neural networks (CNNs) [Krizhevsky et al., 2012], researchers extend CNNs to process the irregular graph data, e.g., graphs and manifolds. Among these extensions, Graph Convolutional Networks (GCN), which simplifies ChebNet [Defferrard et al., 2016], has attracted a large amount of attentions due to its simplicity and high performance [Kipf and Welling, 2017]. As shown in Figure 1(A), GCN is equivalent to smoothing the node features in the neighbourhoods and process them with a fully connected network (FCN). The success of GCN is yielded by the network topology, which is shown in [Li et al., 2018], and the label information, which is only employed to train the parameters in FCN.

Unfortunately, GCN has not fully exploited the potential of the network topology and the flexibility of the FCN is also limited. Specifically, the given network topology is not optimal due to certain sparsity and noises. Some nodes in one class may not be close, while other nodes belonging to different classes may be directly connected. These phenomenons have not been taken into considerations by GCN. On the other hand, the flexibility of GCN is limited compared to CNN. Typically, CNN consists of two learnable components, convolutional layers (including pooling layers) and fully connected layers. The former one can be regarded as the feature extractor with learnable filters, while the latter one is equivalent to a learnable classifier. On the contrary, the filters A in GCN are fixed and only the classifier is learnable (Figure 1(A)).

To better utilize the network topology via refinement and improve the flexibility of the network, we propose a novel Topology Optimization based Graph Convolutional Networks (TO-GCN). As shown in Figure 1(B), the given labels are utilized to simultaneously and jointly learn the network topology and the parameters of the FCN, which provides more flexibility compared to GCN.

Specifically, with the given labels being the pairwise constraints (must-link and cannot-link), the network topology is refined to satisfy the pairwise constraints and predict the unknown labels according to the given labels. To measure the consistencies between the learned network topology and pairwise constraints, constraint propagation is formulated as a minimization of an objective function with the refined topology being the parameters. This model is optimized with respect to the refined topology and the parameters of FCN. Analysis of the joint optimization algorithm indicates that the learned topology is affected by both the given constraints and classification results.

Our main contributions are summarized as follows:

• We analyze the impact of network topology to the performance of semi-supervised node classification in attributed networks and demonstrate that the label information has not been fully explored in most of the existing methods.
• We propose a novel Topology Optimization based Graph

Convolutional Networks (TO-GCN), which jointly learns the network topology and the parameters of the FCN with respect to the given labels.

• We provide an analysis of the joint optimization algorithm to demonstrate its superiority compared to the straightforward separate optimization approach.

2 Backgrounds andMotivations

2.1 Notations and Definitions

Define an attributed network as G = (V,E,X) with nodes/vertices V = {v1, v2, ..., vN} and edges E = {e1, e2, ..., eM}. The attributes of all the vertices are represented as an attribute matrix X ∈ RN×F , where the nth row of which, xn ∈ R1×F , corresponds to the attributes of vertex vn in the form of a F-dimensional vector. The network topology is represented by an adjacency matrix A = [aij] ∈ RN×N . The elements in the adjacency matrix possess binary value, i.e., aij = 1, if an edge exists between the vertices vi and vj, and vice versa. D = diag(d1, d2, ..., dN), where dn = ∑j anj is the degree of vertex vn, is the degree matrix.

In general, semi-supervised node classification predicts the labels Y ∈ {0, 1}N×C of the vertices in V , given the network G = (V,E,X) and some labelled nodes in set Vl in the form of Z = [Znc] ∈ {0, 1}N×C , where C is the number of classes and Znc = 1 if and only if the vertex vn belongs to cth class.

2.2 Label Propagation

The semi-supervised node classification originates from graph-based semi-supervised learning, which makes full use of the limited number of labels by exploring the graph structure. The philosophy behind them is the assumption that nearby vertices on a graph tend to share the same label. Thus, they can be formulated as minimizing the objective function

where wij is the similarity between the vertices vi and vj.

Unfortunately, most of the graph-based semi-supervised learning algorithms ignore either network topology or node feature. When the node features are neglected, some methods like LPA [Raghavan et al., 2007] only exploit the label propagation on the network (topology information), i.e., wij = aij , which is an element in the adjacency matrix. Other methods propagate the labels in similarity graph, which is constructed from the node features without taking the topological information into consideration [Zhu et al., 2003]. In the similarity graph, wij = exp (||xi -xj||22 /σ2 ) is the similarity calculated between the vertices vi and vj with reference to their features. The process of the label propagation in graph can be seen as refining the graph structure with the given labels.

2.3 Graph Convolutional Neural Networks

Recently, semi-supervised node classification algorithms tend to improve the performance by jointly considering the network topology and node attributes (graph data) due to their necessity. Inspired by the successful applications of deep learning to the regular grid data (e.g. images and videos), researchers consider to adopt the deep learning techniques to process the irregular graph data (e.g. graphs or manifolds) [Defferrard et al., 2016; Duvenaud et al., 2015; Niepert et al., 2016; Hamilton et al., 2017; Scarselli et al., 2009; Xu et al., 2019]. To alleviate this difficulty, spectral approaches apply the convolution operation directly to the spectrum of the graph (i.e., the singular values of graph Laplacian) by treating the node attributes as signals in graph according to the spectral graph theory.

where U and Λ represent the singular vectors and singular values of the graph Laplacian L = D-1/2 (D - A)D-1/2 , i.e., L = UΛU T , respectively.

Unfortunately, the high computational complexity of singular value decomposition (SVD) prevents the spectral approaches from being applied to large graphs. To overcome this deficit, may simplifications have been proposed. ChebNet [Defferrard et al., 2016] approximates the spectral filter with P th order Chebyshev polynomials as gθ ∗ x = ∑Pp=0 θ′pTp(L)x, where Tp and θp are the Chebyshev polynomials and coefficients, respectively. GCN (Kipf and Welling 2017) further simplifies ChebNet as

by constraining the Chebyshev polynomials with 1st order and the largest singular values with 2, where I denotes the identity matrix. By denoting ˜ A = A+I and ˜Dnn = ∑j ˜ Anj and generalizing one input channel x and one spectral filters θ to F input channels X and C spectral filters Θ ∈ RF×C , GCN becomes

where σ(.) is the nonlinear activation function, such as softmax or ReLU, as shown in Figure 1(A). According to the experiments, stacking two GCNs, which is shown in Eq. (5), will provide the best performance.

where ˆ A = ˜D- 1 2 ˜ A ˜D- 12 . The parameters Θ(0) and Θ(1) can be calculated by minimizing the cross-entropy errors of the labeled nodes

where Vl denotes the set of labelled nodes. Recent literature [Li et al., 2018] indicates that the graph convolution operation ˜D- 1 2 ˜ A ˜D- 12X in GCN is equivalent to a Laplacian smoothing operation applied to the local neighbourhood, i.e., the graph convolution operation is essentially averaging the node attributes in a local neighbourhood with weight 1 √didj ,

where di is the degree of node vi.

Graph attention network (GAT) [Veliˇckovi´c et al., 2018] extends GCN by imposing the attention mechanism [Bahdanau et al., 2015] to the neighbouring weight assignment and formulates the weight between vertices vn and vk as

where c(x, y) is the self-attention with a shared attentional mechanism c : RC × RC → R. As can be observed, GAT is equivalent to estimating the edge weights according to the attribute similarities between the connected nodes.

Mixture model networks (MoNet) [Monti et al., 2017] unifies some convolutional operations on non-Euclidean structured data (graph or manifold) as mixture CNNs.

2.4 Motivation

After the review of the existing schemes, the main drawbacks of these methods, label propagation (LP) and graph convolutional networks (GCN), are summarized that three kinds of information are not fully utilized by the existing approaches.

LP predicts the labels by combining either the network topology or node features with the given labelled nodes. Obviously, LP approaches have not fully explored all the available information, including the network topology, node features and given labels.

GCN in Eq. (4), which is represented in Figure 1(A), can be rewritten as

where the first term is the given graph Laplacian without the parameters, and the second term is the fully connected network (FCN) which directly employs the node features as inputs. [Li et al., 2018] claims that the classification performance is significantly improved compared to GCN without the Laplacian smoothing term (first term). Therefore, the given network topology (for Laplacian smoothing) plays a very important roles in the classification task.

Based on the above observation in [Li et al., 2018], we further obtain that "A clearer network (community) structure will improve the performance of semi-supervised node classification". The presence of community (modular/cluster) structures, in which the nodes are densely connected within the communities and seldomly connected across the communities, is a common property of networks. For better illustration, we conduct experiments on three attributed networks, Cora, Citeseer and PubMed, with the same attribute matrix and labelled nodes yet three different network topologies.

• FCN only utilize the node features without the graph convolution operation;
• GCN takes the given network topology A as input;
• GCN-GT employs the ground truth membership matrix G = [gij] ∈ {0, 1}N×N , where gij = 1 if and only if the vertices vi and vj are in the same class.

It is obvious that the community structure of GCN-GT is clearer than that of GCN, and the community structure of GCN is clearer than that of FCN.

As can be observed in Table 1, the performance is improved when the network structure becomes clear. This certainly reveals that a refined network topology will benefit the classification performance. However, the network topology is fixed in GCN, which limits the flexibility of the network. Some previous work have shown that the network structure can be improved with the labels [Zhu et al., 2003; Lu and Peng, 2013]. However, the given label information has not been properly integrated with the network topology in GCN. Therefore, GCN has not fully utilized the given label information.

3 Topology Optimization based Graph Convolutional Networks

The existing work reviewed in Section 2 motivates us to refine the network topology. Although there exists previous methods, which refine the network topology with the given labels, these label information has not been fully exploited. Therefore, in this paper, we consider to utilize the given labels to simultaneously and jointly refine the network topology and learn the parameters of the FCN. The flow chart of our proposed method is shown in Figure 1(B). In this section, our network topology refinement method is firstly introduced. Then, the proposed Topology Optimization based Graph Convolutional Networks (TO-GCN) is presented, followed by the optimization algorithm. Finally, the analysis of TO-GCN is given from the model and optimization perspectives.

3.1 Network Topology Refinement

To refine the network topology with the given labels and maintain the topology to be non-negative, the refinement is modeled as a label propagation process. With the assumption that the nearby vertices in a graph tend to share the same label, Eq. (1) can be reformed to

where Vl stands for the set of labelled vertices, zn ∈ {0, 1}1×K and yn ∈ {0, 1}1×K are the ground-truth and predicted labels of the vertex vn. The nth rows of Y and Z are yT n and zT n , respectively. L = D - A is the graph Laplacian of network with the adjacency matrix A. By relaxing the elements in Y to be in RN×K , the constrained integer optimization in Eq. (9) can be relaxed to

Its optimal Y ∗ is also the optimal solution to the following problem according to [Wang et al., 2012]

By denoting Q = [Qij ] = ZZ T ∈ {0, 1}N×N , Qij equals to 1 (must-link constraint) if and only if the vertices vi and vj belong to the same class based on the given labels Z. Since the refinement is achieved with the given label information instead of directly obtaining the node label Y , we let O = [Oij ] = Y Y T ∈ RN×N as the refined network topology and rewritten Eq. (11) as

The must-link constraints (the pairs of nodes belong to the same class) are preserved during the transformation from Eq. (10) to Eq. (11). However, the cannot-link constraints (the pairs of nodes belong to different classes), which reduce the similarity (edge weight) between the nodes belonging to different classes, are ignored during the transformation. Therefore, Eq. (12) is revised to penalize the high similarities between the nodes from different classes as

Let G = [Gij] ∈ {0, 1}N×N , where Gij = 1 if and only if the vertices vi and vj belong to different classes. Then, the objective function of our network topology refinement method becomes

where Q and G are the pairwise constraint matrices and can be obtained from the given label matrix Z. By minimizing Eq. (13), the given topology A is refined to O with the help of the given labels.

3.2 Topology Optimization based Graph Convolutional Networks

To exploit the network topology refinement in GCN, a straightforward approach, which is named P-GCN, is to simply perform the refinement in Eq. (13) at first, and then perform GCN on the refined network topology.

However, this approach is sub-optimal, because the pre-processed refined topology only facilitates the semisupervised node classification by providing a high modular network structure while ignoring its direct impact to the classification results. Detailed analysis is provided at the end of this section.

Therefore, Topology Optimization based Graph Convolutional Networks (TO-GCN) is proposed to jointly learn the network topology and the parameters of a fully connected network (FCN) as shown in Figure 1(B). Similar to GCN, the cross-entropy loss in Eq. (6) is adopted to measure the classification errors, and the final objective function is

where the first term is the classification loss and the second is the topology refinement loss. H = [Hnc] ∈ RN×C is the prediction matrix and

where W = {W (0) ,W (1) } is the parameters of FCN.

3.3 Optimization

To jointly learn the refined network topology O and FCN parameters W, we alternatively update one at a time while fix the other. When the refined network topology O is fixed, the updating of the FCN parameters W is identical to the updating procedures in GCN, and we thus omit the details of it. For convenience, the process of updating O with fixed W is described in details.

Although the second and third terms in Eq. (14) both possess analytical solutions, the gradient decent approach is still adopted to optimize Eq. (14), because the first term does not have a close-form solution. Since the Laplacian matrix L and the constraints matrices G and Q are symmetric, the gradient of Lrefine with respect to O is

where L + αG - λQ can be computed in advance, since it does not vary in each iteration.

Then, we compute the gradient of Lclassify with respect to O. For simplicity, we consider the one-layer convolution operation i.e., H = softmax (OXW). Note that the prediction of the node vn, Hn = softmax (OnB), will only be affected by On, the nth row of the topology matrix, where B = XW is fixed when W is fixed. Thus, the gradient of Lclassify with respect to Onk is equivalent to that of Lclassify(n) = (- ∑Cc=1 Znc log(Hnc)) with respect to Onk, as shown in Eq. (14). According to the Chain Rule,

where Hnc = softmax(Tnc) and Tnc = ∑k OnkBkc. Since

where δcp is the Kronecker delta and δcp = 1 if and only if c = p, then

Besides, since ∂Tnp ∂Onk = Bkp, then,

and it can be transformed to the matrix form

since B = XW. By combining Eqs. (15) and (16), the total gradient in the matrix form is

Tips for Implementation: To speedup the optimization, the refined network topology O is firstly initialized by minimizing Eq. (13) without considering the backward-propagation of the classification errors. Besides, the updating rule in Eq. (17) is only applied to update the weights of the existing edges and the must-link constraints, i.e., A + Q. Thus, the complexity of TO-GCN is O(M) instead of O(N 2 ), where N and M are the numbers of nodes and edges, respectively.

Remark: The extra cost of the learnable graph is the topology updating in Eq. (17). For efficiency, the topology is initialized via constrained propagation, as shown in Eq. (13), and the updating in Eq. (17) is only applied to update the weights of the existing edges and the must-link constraints. Therefore, the increased computations are linearly proportional to the number of edges. and the proposed TO-GCN can be applied to large-scale networks.

3.4 Insights

Here, we introduce some insights of the proposed method to further illustrate the superiority of TO-GCN and the advantage of jointly learning the refined network topology and parameters of the FCN.

From the Model Perspective

To elaborate the advantage of our proposed TO-GCN against GCN, they are both compared to the Convolution Neural Network (CNN). CNN consists of two learnable components: convolutional layers (including pooling layers) and fully connected layers. The former layers can be regarded as the feature extractor with learnable filters, while the latter layers are equivalent to a learnable classifier. In our proposed TO-GCN (Figure 1(B)), the learnable network topology O can be regarded as the learnable filters while FCN with parameters W is equivalent to the learnable classifier. Therefore, TOGCN and CNN are similar. On the contrary, the filters A is fixed and only the classifier is learnable in GCN (Figure 1(A)). Therefore, TO-GCN is more flexible than GCN.

From the Optimization Perspective

The updating rule of O in Eq. (17) consists of three terms whose roles are elaborated in details as follows.

The first term is the main difference between the straightforward approach and the joint learning mechanism. S = [Snk] = (H -Z)W T XT can be regarded as the correlation between the prediction error Z -H and the prediction from node attributes XW. Snk can then be written as

where hn and zn represent the predicted and ground-truth label vectors of the vertex vn, respectively.

Then, we analyze the role of Snk. If the ground truth and the predicted label of node vn are identical, then Snk = 0. Otherwise, if the ground truth and the predicted label of node vn are i and j, respectively, then

Snk can be rewritten as Snk = -xk(w.i - w.j), where w.j is the j th column of W. Since xkw.j is the confidence of node vk being classified into class j, xk(w.j - w.i) is the confidence difference of node vk being classified into classes i and j based on the node attributes xk. Therefore, updating O with S = (H -Z)W T XT reduces the weights Onk if the classification result of vk makes vn being misclassified.

The second term is the combination of the graph Laplacian and constraint matrix, which reveals the impact of the constraints to the refined network. The third term is to guarantee the updating process to be performed regularly.

Overall, by jointly learning the refined network topology and the parameters of FCN, the network topology is refined by both the given constraints and classification results. Therefore, TO-GCN is better than the straightforward P-GCN.

4 Evaluations

In this section, we evaluate the proposed TO-GCN with extensive experiments on real attributed networks and provide some visualizations for better illustrations.

4.1 Datasets and Setup

As in previous work, three citation networks, in which the vertices and edges are documents and undirected citations respectively, are utilized for performance evaluation. Node attributes are the bag-of-words representations of documents. Each node is assigned a label based on its discipline. The statistics of the networks, Cora, CiteSeer and PubMed, are summarized in Table 2. Following the setup in [Yang et al., 2016] and [Kipf and Welling, 2017], the network topology, the features of all the nodes and the labels of 20 nodes per class are available for training. The performance of all the baseline methods are evaluated on 1,000 test nodes with 500 additional nodes for validation. Note that the balancing parameter between Lclassify and Lrefine are not employed, which is equivalent to set the balancing parameter to be 1. α and λ, which are the hyperparameters for cannot-link and must-link constraints, are set according to the results of the validation set.

4.2 Baselines

Our proposed model are compared to 10 state-of-the-art approaches, including multilayer perceptron (MLP), label propagation (LP) [Zhu et al., 2003], semi-supervised embedding (SemiEmb) [Weston et al., 2012], manifold regularization (ManiReg) [Belkin et al., 2006], graph embedding (DeepWalk) [Perozzi et al., 2014], iterative classification algorithm (ICA) [Lu and Getoor, 2003], graph-based semi-supervised learning framework (Planetoid) [Yang et al., 2016], graph convolution with Chebyshev filters [Defferrard et al., 2016], graph convolutional networks (GCN) [Kipf and Welling, 2017], and mixture model networks (MoNet) [Monti et al., 2017]. All the results of the baseline approaches are either from their original papers or obtained with their original codes and default settings. To show the superiority of the joint learning strategy, TO-GCN is also compared to the straightforward version, P-GCN, where the refined topology matrix is pre-computed and fed into GCN.

4.3 Results Analysis

As shown in Table 3, the results of semi-supervised node classification indicate that the proposed TO-GCN consistently outperforms other state-of-the-art methods and the straightforward P-GCN. The superior performance of TOGCN demonstrates that both the proposed topology refinement and the jointly learning mechanism are vital to the performance improvements. As can be observed, the performance improvement for the Pubmed network is limited, because the network topology has not been appropriately refined due to the messy structure of Pubmed and the small dimensions of the features. The former aspect causes the constraint propagation to be inefficient, while the latter one affects the learnable weights obtained from the backward propagated classification error. To demonstrate the robustness of the proposed TO-GCN compared to GCN, an experiment is conducted on Cora by adding 3% noisy edges are conducted. The accuracy degradations of GCN and TO-GCN are 11.2% and 8.7%, respectively, which also verifies the superiority of TO-GCN.

4.4 Visualizations

To elaborate the results with more intuitions, we intend to present more insights of the learned adjacency matrix. Since the network is sparse, it is difficult to effectively visualize the learned adjacency matrices of the above three networks. Therefore, we conduct these visualizations on medium-sized Cornell network from the WebKB dataset. It consists of 195 connected webpages, which are classified into 5 classes. Each webpage is annotated by 1703-dimensional binary-valued word attributes. Since the dimensions of node content are much larger than the number of nodes, the dimensions of node content are reduced to 50 via PCA to prevent the overfitting problem. 10% of the nodes are randomly selected for training. The results are introduced in Figure 2. The nodes are re-ordered according to the ground-truth labels, and the color brightness indicates the weights of the edges. The structure of the learned graph is the combination of network topology and the constraints constructed form the labels. During the training process, the weights of the edges are refined by the pairwise constraints and the back-propagation of the classifier. As can be observed, the weights of inter-class edges (orange boxes) are significantly reduced while those of intraclass edges (cyan boxes) remain at a high level (Figure 2(D)).

5 Conclusions

In this paper, we observe that the network topology (both the structure and weights) contributes significantly in semisupervised node classification. A clear community structure (modularity) of network usually induces a high classification accuracy. Besides of this observation, existing approaches have not fully utilized the potentials of three types of information, including network topology, node features and given labels. Therefore, we propose a novel Topology Optimization based Graph Convolutional Networks (TO-GCN) to fully utilize these three types of information by jointly refining the network topology and learning the parameters of FCN. Extensive experiments on real attributed networks demonstrate the superior performance of the proposed TO-GCN against the state-of-the-arts.

Acknowledgments

This work was supported in part by the National Key R&D Program of China (No.2017YFC0820106), in part by the National Natural Science Foundation of China under Grant 61503281, Grant 61802391, Grant 61772361, Grant U1636214, Grant U1605252, in part by the Foundation for Innovative Research Groups through the National Natural Science Foundation of China under Grant 61421003, in part by the Key Program of the Chinese Academy of Sciences (No. QYZDB-SSW-JSC003), and in part by the Fundamental Research Funds for the Central Universities.