# Hybrid Low-Order and Higher-Order Graph Convolutional Networks

Authors: Fangyuan Lei; Xun Liu; Qingyun Dai; Bingo Wing-Kuen Ling; Huimin Zhao; Yan Liu
Journal: Computational Intelligence and Neuroscience
 (2020)

---

## Abstract

With the higher-order neighborhood information of a graph network, the accuracy of graph representation learning classification can be significantly improved. However, the current higher-order graph convolutional networks have a large number of parameters and high computational complexity. Therefore, we propose a hybrid lower-order and higher-order graph convolutional network (HLHG) learning model, which uses a weight sharing mechanism to reduce the number of network parameters. To reduce the computational complexity, we propose a novel information fusion pooling layer to combine the high-order and low-order neighborhood matrix information. We theoretically compare the computational complexity and the number of parameters of the proposed model with those of the other state-of-the-art models. Experimentally, we verify the proposed model on large-scale text network datasets using supervised learning and on citation network datasets using semisupervised learning. The experimental results show that the proposed model achieves higher classification accuracy with a small set of trainable weight parameters.


---

## Body

## 1. Introduction

Convolutional neural networks (CNNs) have achieved great success in grid structured data such as images and videos [1, 2]. It is attributed to a series of filters of convolutional layers from the CNNs that can obtain local invariant features. Compared to a regularized network, the number of neighbors of a node in a graph network may be different. Therefore, it is difficult to directly implement the filter operator in an irregular network structure [3].In the graph network, the nodes and the connecting edges between them contain abundant network characteristic information. A graph convolutional network (GCN) aggregates the neighborhood nodes to realize continuous information transmission based on a graph network. By making full use of this information, a GCN can effectively achieve tasks such as classification, prediction, and recommendation.A graph convolutional network (GCN) generalizes traditional convolutional neural networks (CNNs) to the graph domain. The GCN methods are mainly divided into two categories [3], the frequency domain-based methods [4–6] and the spatial domain-based methods [7, 8].In the spatial domain, to simulate the convolution operation of the traditional CNN on an image, the convolution operation aggregates the information of the neighborhood nodes [7–10]. Henaff et al. [11] proposed a smoothed parametric spectral filter to realize localization and to preserve the parameters of filters independent of the input dimension. One of the key challenges is that the number of neighborhood nodes in the network irregularly changes.In the frequency domain, Bruna et al. [5] were the first ones to extend CNN-type architectures to graphs. Cao et al. [12] applied a generalized convolutional network to the graph frequency domain using the Fourier transform. In this method, eigenvalue decomposition is performed on the neighborhood matrix. To reduce the computational complexity, Defferrard et al. [13] proposed the Chebyshev polynomial of the eigenvalues of the graph Laplacian to achieve efficient and localized graph convolutional operation filters. Kipf and Welling [6] proposed a classical GCN, which was approximated by a first-order Chebyshev polynomial. This approach reduces the computational complexity but introduces truncation errors. This introduction results in the inability to capture high-level interaction information between the nodes in the graph, and it also limits the capabilities of the model. The information propagation process in the graph is related not only to its first-order neighborhood but also to its higher-order neighborhood.Abu-El-Haija et al. [14, 15] proposed the high-order convolutional network layer on a graph that used linear combination of the high-order neighborhood basis of the GCN [6]. Tiao et al. [16] proposed a Bayesian estimation approach via the stochastic variational inference in the adjacency matrix of the graph. Levie et al. [17] proposed Cayley polynomials to compute the localized regular filters of the interest frequency bands of graphs. Therefore, the rational use of second-order neighborhoods, third-order neighborhoods, and other high-order neighborhood information will be beneficial to classification prediction accuracy [14–16, 18–20].Based on the classical GCN [6], to make full use of the high-order and low-order neighborhood information, we propose a novel hybrid low-order and higher-order graph convolutional network (HLHG). As shown in Figure 1, the graph convolutional layer of our model is simple and effective at capturing the high-order neighborhood information, nonlinearly combining the different order neighborhood information. The contributions are summarized as follows:(1)
We propose a new fusion pooling layer to achieve high-order neighborhood fusion with the low-order neighborhood of graph networks(2)
We propose a low-order neighborhood and high-order neighborhood weight sharing mechanism to reduce the computational complexity and number of parameters of the model(3)
The experimental results show that our HLHG achieves state-of-the-art performance in both the text network classification with supervised learning and the citation network with semisupervised learningFigure 1
The graph convolutional layer of our model. (a) First-order graph convolutional layer of the Kipf and Welling [6] model. The input is Hl−1, the output is Hl, and the trainable parameter is Wl. (b) The 3rd order graph convolutional layer of our HLHG model. Different order neighborhood matrices share the trainable weight.
(a)(b)The rest of the paper is organized as follows. In Section2, the related theoretical basis such as the graph convolution and the high-order graph convolution are introduced. In Section 3, the general information fusion pooling for the high-order neighborhood is presented. Then, the proposed model and its variant are presented. The computational complexity and parameter quantity of the proposed model are also theoretically analyzed. In Section 4, our proposed model is verified and the corresponding analysis are presented. Finally, Section 5 concludes the paper.


## 2. Related Theoretical Background

In this section, the related theoretical basis will be introduced, including the graph convolutional network (GCN).


### 2.1. Graph

Given a graphG, its nodes set V, and its edges E, the graph is represented as G=V,E. If nodes Vi and Vj are connected, then Eij=1; otherwise, Eij=0. The information in the graph propagates along with the edge E. It also applies when considering the network node self-loop, which means that Eii=1. Assuming that the information that is propagated by each node in the graph network is x∈Rr, the information matrix in the graph is X∈Rn×r, where n is the total number of nodes in the graph network and r is the dimension of the information feature. It assumes that if the loop graph network G is represented as G˜, then the adjacency matrix of the graph network G˜ is represented as A˜=A+I. The degree matrix of A˜ in the graph network G˜ is the diagonal matrix, D˜ii=∑jA˜ij.


### 2.2. Graph Convolutional Network

In the given graphG, there are two signals f=f1,…,fnT and g=g1,…,gnT. The graph’s Fourier transforms are defined as f^=ΦTfand g^=ΦTg, where Φ is the orthonormal eigenvalues of the graph Laplacian of graph G. The same as in Euclidean space, the spectral graph convolution operation of f and g is given as an elementwise product as follows:(1)g∗f=ΦΦTg∘ΦTf=ΦG^ΦTf,where G^=diagg^1,…,g^nrepresents the diagonal matrix of g^.Defferrard et al. [13] utilized the k-th order polynomial filters based on Chebyshev to represent the graph convolutional operation of Laplacian G^=∑iαiΛi, where αi denotes the coefficients andΛ represents the eigenvalues of the Laplacian.Kipf and Welling [6] propose the classical graph convolutional neural network model based on the Fourier transform, g∗f=αA˜f. The GCN model approximates the model using a first-order Chebyshev polynomial. The propagation model in the graph network is as follows:(2)Hl+1=σD˜−1/2A˜D˜−1/2HlWl,where Hl denotes the information propagation matrix; Wl represents the trainable weight of layer l; when l=0, H0=X∈Rn×r, which represents the initial input value of the GCN; σ. denotes the activation function. To reduce the computational complexity, the convolution operator in the graph is defined by a simple neighborhood average. However, the convolutional filters are too simple to capture the high-level interaction information between the nodes in the graph. Therefore, the classification accuracy on citation network datasets is low.Abu-El-Haija et al. [14, 15] propose a high-order graph convolutional layer model based on the GCN for semisupervised node classification. The propagation model of the high-order graph convolution is as shown in formula (3). In this model, the transfer function of the l+1-th layer is a column concatenation from the first order to the p order in the l-th layer, which is the linear combination of the high-order neighborhood. In the propagation model, the different order neighborhoods of the same layer use different weight parameters:(3)Hl+1=σB0HlW0l…BpHlWpl,where B=D˜−1/2A˜D˜−1/2. However, as the network layers deepen, the dimensions of Hl+1 will increase and propagate between layers. Therefore, the number of trainable weight parameters will be more, and the training resource will also be increased to learn the optimized dimension of the weight.


## 2.1. Graph

Given a graphG, its nodes set V, and its edges E, the graph is represented as G=V,E. If nodes Vi and Vj are connected, then Eij=1; otherwise, Eij=0. The information in the graph propagates along with the edge E. It also applies when considering the network node self-loop, which means that Eii=1. Assuming that the information that is propagated by each node in the graph network is x∈Rr, the information matrix in the graph is X∈Rn×r, where n is the total number of nodes in the graph network and r is the dimension of the information feature. It assumes that if the loop graph network G is represented as G˜, then the adjacency matrix of the graph network G˜ is represented as A˜=A+I. The degree matrix of A˜ in the graph network G˜ is the diagonal matrix, D˜ii=∑jA˜ij.


## 2.2. Graph Convolutional Network

In the given graphG, there are two signals f=f1,…,fnT and g=g1,…,gnT. The graph’s Fourier transforms are defined as f^=ΦTfand g^=ΦTg, where Φ is the orthonormal eigenvalues of the graph Laplacian of graph G. The same as in Euclidean space, the spectral graph convolution operation of f and g is given as an elementwise product as follows:(1)g∗f=ΦΦTg∘ΦTf=ΦG^ΦTf,where G^=diagg^1,…,g^nrepresents the diagonal matrix of g^.Defferrard et al. [13] utilized the k-th order polynomial filters based on Chebyshev to represent the graph convolutional operation of Laplacian G^=∑iαiΛi, where αi denotes the coefficients andΛ represents the eigenvalues of the Laplacian.Kipf and Welling [6] propose the classical graph convolutional neural network model based on the Fourier transform, g∗f=αA˜f. The GCN model approximates the model using a first-order Chebyshev polynomial. The propagation model in the graph network is as follows:(2)Hl+1=σD˜−1/2A˜D˜−1/2HlWl,where Hl denotes the information propagation matrix; Wl represents the trainable weight of layer l; when l=0, H0=X∈Rn×r, which represents the initial input value of the GCN; σ. denotes the activation function. To reduce the computational complexity, the convolution operator in the graph is defined by a simple neighborhood average. However, the convolutional filters are too simple to capture the high-level interaction information between the nodes in the graph. Therefore, the classification accuracy on citation network datasets is low.Abu-El-Haija et al. [14, 15] propose a high-order graph convolutional layer model based on the GCN for semisupervised node classification. The propagation model of the high-order graph convolution is as shown in formula (3). In this model, the transfer function of the l+1-th layer is a column concatenation from the first order to the p order in the l-th layer, which is the linear combination of the high-order neighborhood. In the propagation model, the different order neighborhoods of the same layer use different weight parameters:(3)Hl+1=σB0HlW0l…BpHlWpl,where B=D˜−1/2A˜D˜−1/2. However, as the network layers deepen, the dimensions of Hl+1 will increase and propagate between layers. Therefore, the number of trainable weight parameters will be more, and the training resource will also be increased to learn the optimized dimension of the weight.


## 3. Method

When the message passes through the graph network, the nodes will receive latent representations from their first-hop nodes and from their N-hop neighbors every time. In this section, we propose a model to nonlinearly aggregate the trainable parameters, which can choose how to mix latent messages from various hop nodes.


### 3.1. General Information Fusion Pooling

The information propagation of the graph network is passed along the edges between the vertices in the graph. It assumes that the graph networkG=V,E is an undirected graph. The general procedure of fusion pooling is described as follows. It assumes that the k-th order neighborhood matrix is Ak=aijk, and the result after the fusion pooling operator is PmaxA0,…,Ak=Zk=zijk, where zijk=maxaij1,aij2,…,aijk) and k represents the hop from the given node.Here, is an example to show how to fuse the different order neighborhoods. For a given adjacency matrixA^, assume that h1 denotes the first-order neighborhood and h2 denotes the second-order neighborhood.Ifh1=A^XW1=1011 and h2=A^2XW1=−1021, then Pmaxh1,h2=1021.In the information dissemination and fusion process, both the first-order neighborhood features and the high-order neighborhood features are fully considered. Therefore, the classification accuracy should be improved.


### 3.2. Our Proposed Model

In Figure2, we propose the high-order graph convolutional network model to fuse the high-order messages that pass through the graph network. The model consists of an input layer, two graph convolutional layers, and an information fusion pooling layer that is connected to the graph convolutional layer. The softmax function is used for the multiclassification output.Figure 2
HLHG mode. The graph convolutional network layer of the HLHG model consists of two convolutional layers and information fusion pooling. The input parameters are from the first-order to then-th order neighborhoods. When n = 1, the model degenerates into a classical graph convolution GCN model. When the neighborhood order is n = 2, it is called the HLHG-2 model, and its input parameters are the 1st order neighborhood and the 2nd order neighborhood. When the neighborhood order is n = 3, it is called the HLHG-3 model, and its input parameters are the 1st order neighborhood, the 2nd order neighborhood, and the 3rd order neighborhood.The proposed model extends the classical GCN model [6] to the graph neural network of higher-order neighborhoods. Each node in the model can get its representation from its neighborhood and integrate messages. The system model is as follows:(4)Y=ℱPmA^σHl+1Wl+1,⋯,A^pσHl+1Wl+1,where p is the order of the neighborhoods, A^p = A^p−1A^, σ. is the activation function, function ℱ. denotes the softmax function. Parameter Wl+1 is the trainable weight parameter of layer l+1 in the graph network, and function Pm. represents Pmax., which denotes the hybrid high-order and low-order of the information fusion. When parameter l is equal to 0, H1=PmaxA^H0W0,⋯,A^pH0W0, which is the output of the first convolutional layer of the graph propagation model. In addition, H0=X∈Rn×r, which represents the initial input of our model.In the preliminary experiment, we found that the two-layer high- and low-order mixed graph convolution is better than the one-level high- and low-order mixed graph convolution, and stacking more layers does not significantly improve the accuracy of the graph recognition task. Therefore, this paper uses a 2-layer graph convolution layer. In further experiments, we validatep=2 and p=3 in equation (4) for our HLHG models. In the supervised learning and unsupervised learning classification tasks, our HLHG models show very good performance and achieve a good balance between the classification accuracy and computational complexity. We also validate that at p=4 and p>4, the classification accuracy is not significantly improved. Therefore, we only analyze and implement our model for p=2 and p=3 in the following sections.In equation (4), the model with p=2, that is, the hybrid model of the 1st and 2nd order neighborhoods, is called the HLHG-2 model. The model with p=3, that is, the hybrid model of the 1st, 2nd, and 3rd order neighborhoods, is called the HLHG-3 model.In the HLHG-2 model, it assumes that the graph convolutional network has 2 convolutional layers and the activation function isRelu. Then, the output Y of the HLHG-2 model can be expressed as follows:(5)Y=ℱPmA^ReluM2W2,A^2ReluM2W2,where M2=PmaxA^XW1,A^2XW1 and Pm denotes the fusion pooling Pmax.The same as with the HLHG-2 model, the output Y of the HLHG-3 model can be expressed as follows:(6)Y=ℱPmA^T,A^2T,A^3T,where T=ReluM3W2 and M3=PmaxA^XW1,A^2XW1,A^3XW1.For a large-scale graph network, it is unacceptable to directly calculateA^3=A^2A^=A^A^A^. Therefore, we calculate A^3XW1=A^A^A^XW1. In general, the dimension of A^X is less than A^, and this procedure avoids large-scale matrix multiplication operations.Therefore, our HLHG model has a 2-layer graph network, and the iterative expression of the 2nd order neighborhood is as follows:(7)Y=softmaxA^ReluHW2,A^2ReluHW2,where H=PmaxA^XW1,A^2XW1. We use Pmax as our fusion pooling operator, which assumes the maximum value in the corresponding element. Algorithm 1 shows how to fuse the different order neighbors.Algorithm 1: Iterative calculation for HLHG-2.
(1)
Inputs:X, A^, and the other parameters. N (number of hidden units), dr (dropout rate), L2 (L2 regularization), es (early stopping), epochs and lr (learning rate).Output: weight parametersW1 and W2.(2)
Randomly generate the trainable weightsW1 and W2;(3)
Iteratively calculate the forward output value(1)
h1=A^XW1, h2=A^2XW1=A^h1(2)
h3=Pmaxh1,h2(3)
h4=Reluh3;(4)
h5=A^h4W2, h6=A^2h5(5)
h7=Pmaxh5,h6(6)
Y=softmaxh7(4)
Calculate the cross entropyL=−∑iy˜ilogqiWe use the multiclassified cross entropy as the loss function of our HLHG model,L=−∑iy˜ilogqi, where Y˜ is the labeled samples. The graph neural network trainable weights W1 and W2 are trained using gradient descent. In each training iteration, we perform the batch gradient descent.


### 3.3. Computational Complexity and Parameter Quantity

In the large-scale graph network, the adjacency matrix isA^∈Rn×n. It is difficult to directly calculate A^p. To reduce the computational complexity, we iteratively calculate A^p. For higher orders, the right to left iterative multiplication procedure is A^pHlWl=A^pHlWl=A^A^p−1HlWl. For example, when p=1, A^1H0=A^X∈Rn×r. When p=2, A^2H1=A^A^X∈Rn×r.In the proposed model, the input feature of the graph network isX∈Rn×r. The weight of the first convolutional layer is W1∈Rr×r1, and the weight of the second layer is W2∈Rr1×r2. Then, the input of the first convolutional layer is H0=X∈Rn×r where the parameter r represents the dimension of the input feature. For example, r1 denotes the number of hidden neurons in the first convolutional layer and r2 denotes the number of hidden neurons in the second convolutional layer. In our HLHG model, the trainable weight parameters are shared in the same convolutional layer. Therefore, in the first convolutional layer, the output dimension after the convolutional operator is the same. That is, A^XW1∈Rn×r1, A^2XW1∈Rn×r1, and A^kXW1∈Rn×r1, where k is the order of the adjacency matrix A^.In thel-th convolutional layer, A^kHlWl∈Rn×rl, where rl denotes the number of hidden neurons in the l-th convolutional layer. It assumes that A^ is a sparse matrix with m nonzero elements. For the l-th convolutional layer of our HLHG, the computational complexity is Orl×k×m×rl−1 and the quantity of trainable weight is Orl×rl−1.The total computational complexity of our HLHG model isO∑ljrl×k×m×rl−1, and the total number of trainable parameters is O∑ljrl×rl−1, where parameter j denotes the total number of convolutional layers and l denotes the l-th convolutional layer. When l=1, r0 represents the feature dimensions of the datasets and rl represents the number of hidden neurons in the l-th convolutional layer. For all the datasets, r0≫rl; therefore, we only consider the first convolutional layer when we compare the computational complexity and number of parameters.Compared to [14], we set fewer filters to maintain a similar computational complexity and the number of parameters is less via weight sharing for both the lower-order and higher-order convolutions.


## 3.1. General Information Fusion Pooling

The information propagation of the graph network is passed along the edges between the vertices in the graph. It assumes that the graph networkG=V,E is an undirected graph. The general procedure of fusion pooling is described as follows. It assumes that the k-th order neighborhood matrix is Ak=aijk, and the result after the fusion pooling operator is PmaxA0,…,Ak=Zk=zijk, where zijk=maxaij1,aij2,…,aijk) and k represents the hop from the given node.Here, is an example to show how to fuse the different order neighborhoods. For a given adjacency matrixA^, assume that h1 denotes the first-order neighborhood and h2 denotes the second-order neighborhood.Ifh1=A^XW1=1011 and h2=A^2XW1=−1021, then Pmaxh1,h2=1021.In the information dissemination and fusion process, both the first-order neighborhood features and the high-order neighborhood features are fully considered. Therefore, the classification accuracy should be improved.


## 3.2. Our Proposed Model

In Figure2, we propose the high-order graph convolutional network model to fuse the high-order messages that pass through the graph network. The model consists of an input layer, two graph convolutional layers, and an information fusion pooling layer that is connected to the graph convolutional layer. The softmax function is used for the multiclassification output.Figure 2
HLHG mode. The graph convolutional network layer of the HLHG model consists of two convolutional layers and information fusion pooling. The input parameters are from the first-order to then-th order neighborhoods. When n = 1, the model degenerates into a classical graph convolution GCN model. When the neighborhood order is n = 2, it is called the HLHG-2 model, and its input parameters are the 1st order neighborhood and the 2nd order neighborhood. When the neighborhood order is n = 3, it is called the HLHG-3 model, and its input parameters are the 1st order neighborhood, the 2nd order neighborhood, and the 3rd order neighborhood.The proposed model extends the classical GCN model [6] to the graph neural network of higher-order neighborhoods. Each node in the model can get its representation from its neighborhood and integrate messages. The system model is as follows:(4)Y=ℱPmA^σHl+1Wl+1,⋯,A^pσHl+1Wl+1,where p is the order of the neighborhoods, A^p = A^p−1A^, σ. is the activation function, function ℱ. denotes the softmax function. Parameter Wl+1 is the trainable weight parameter of layer l+1 in the graph network, and function Pm. represents Pmax., which denotes the hybrid high-order and low-order of the information fusion. When parameter l is equal to 0, H1=PmaxA^H0W0,⋯,A^pH0W0, which is the output of the first convolutional layer of the graph propagation model. In addition, H0=X∈Rn×r, which represents the initial input of our model.In the preliminary experiment, we found that the two-layer high- and low-order mixed graph convolution is better than the one-level high- and low-order mixed graph convolution, and stacking more layers does not significantly improve the accuracy of the graph recognition task. Therefore, this paper uses a 2-layer graph convolution layer. In further experiments, we validatep=2 and p=3 in equation (4) for our HLHG models. In the supervised learning and unsupervised learning classification tasks, our HLHG models show very good performance and achieve a good balance between the classification accuracy and computational complexity. We also validate that at p=4 and p>4, the classification accuracy is not significantly improved. Therefore, we only analyze and implement our model for p=2 and p=3 in the following sections.In equation (4), the model with p=2, that is, the hybrid model of the 1st and 2nd order neighborhoods, is called the HLHG-2 model. The model with p=3, that is, the hybrid model of the 1st, 2nd, and 3rd order neighborhoods, is called the HLHG-3 model.In the HLHG-2 model, it assumes that the graph convolutional network has 2 convolutional layers and the activation function isRelu. Then, the output Y of the HLHG-2 model can be expressed as follows:(5)Y=ℱPmA^ReluM2W2,A^2ReluM2W2,where M2=PmaxA^XW1,A^2XW1 and Pm denotes the fusion pooling Pmax.The same as with the HLHG-2 model, the output Y of the HLHG-3 model can be expressed as follows:(6)Y=ℱPmA^T,A^2T,A^3T,where T=ReluM3W2 and M3=PmaxA^XW1,A^2XW1,A^3XW1.For a large-scale graph network, it is unacceptable to directly calculateA^3=A^2A^=A^A^A^. Therefore, we calculate A^3XW1=A^A^A^XW1. In general, the dimension of A^X is less than A^, and this procedure avoids large-scale matrix multiplication operations.Therefore, our HLHG model has a 2-layer graph network, and the iterative expression of the 2nd order neighborhood is as follows:(7)Y=softmaxA^ReluHW2,A^2ReluHW2,where H=PmaxA^XW1,A^2XW1. We use Pmax as our fusion pooling operator, which assumes the maximum value in the corresponding element. Algorithm 1 shows how to fuse the different order neighbors.Algorithm 1: Iterative calculation for HLHG-2.
(1)
Inputs:X, A^, and the other parameters. N (number of hidden units), dr (dropout rate), L2 (L2 regularization), es (early stopping), epochs and lr (learning rate).Output: weight parametersW1 and W2.(2)
Randomly generate the trainable weightsW1 and W2;(3)
Iteratively calculate the forward output value(1)
h1=A^XW1, h2=A^2XW1=A^h1(2)
h3=Pmaxh1,h2(3)
h4=Reluh3;(4)
h5=A^h4W2, h6=A^2h5(5)
h7=Pmaxh5,h6(6)
Y=softmaxh7(4)
Calculate the cross entropyL=−∑iy˜ilogqiWe use the multiclassified cross entropy as the loss function of our HLHG model,L=−∑iy˜ilogqi, where Y˜ is the labeled samples. The graph neural network trainable weights W1 and W2 are trained using gradient descent. In each training iteration, we perform the batch gradient descent.


## 3.3. Computational Complexity and Parameter Quantity

In the large-scale graph network, the adjacency matrix isA^∈Rn×n. It is difficult to directly calculate A^p. To reduce the computational complexity, we iteratively calculate A^p. For higher orders, the right to left iterative multiplication procedure is A^pHlWl=A^pHlWl=A^A^p−1HlWl. For example, when p=1, A^1H0=A^X∈Rn×r. When p=2, A^2H1=A^A^X∈Rn×r.In the proposed model, the input feature of the graph network isX∈Rn×r. The weight of the first convolutional layer is W1∈Rr×r1, and the weight of the second layer is W2∈Rr1×r2. Then, the input of the first convolutional layer is H0=X∈Rn×r where the parameter r represents the dimension of the input feature. For example, r1 denotes the number of hidden neurons in the first convolutional layer and r2 denotes the number of hidden neurons in the second convolutional layer. In our HLHG model, the trainable weight parameters are shared in the same convolutional layer. Therefore, in the first convolutional layer, the output dimension after the convolutional operator is the same. That is, A^XW1∈Rn×r1, A^2XW1∈Rn×r1, and A^kXW1∈Rn×r1, where k is the order of the adjacency matrix A^.In thel-th convolutional layer, A^kHlWl∈Rn×rl, where rl denotes the number of hidden neurons in the l-th convolutional layer. It assumes that A^ is a sparse matrix with m nonzero elements. For the l-th convolutional layer of our HLHG, the computational complexity is Orl×k×m×rl−1 and the quantity of trainable weight is Orl×rl−1.The total computational complexity of our HLHG model isO∑ljrl×k×m×rl−1, and the total number of trainable parameters is O∑ljrl×rl−1, where parameter j denotes the total number of convolutional layers and l denotes the l-th convolutional layer. When l=1, r0 represents the feature dimensions of the datasets and rl represents the number of hidden neurons in the l-th convolutional layer. For all the datasets, r0≫rl; therefore, we only consider the first convolutional layer when we compare the computational complexity and number of parameters.Compared to [14], we set fewer filters to maintain a similar computational complexity and the number of parameters is less via weight sharing for both the lower-order and higher-order convolutions.


## 4. Experiments

We conduct experiments in order to verify that our HLHG model can be applied to supervised learning and semisupervised learning. On the text network datasets, we compare our model with the state-of-the-art methods using supervised learning. On the citation network datasets, we compare our model with the state-of-the-art methods using semisupervised learning. For all experiments, we construct a 2-layer graph convolutional network of our model using TensorFlow. The code and data are available on GitHub.


### 4.1. Supervised Text Network Classification

We conduct supervised learning on five benchmark text graph datasets to compare the classification accuracy of HLHG with the graph convolutional neural network and other deep learning approaches.


#### 4.1.1. Datasets

In our supervised experiments, the 20-Newsgroups (20NG), Ohsumed, R52 and R8 of Reuters 21578, and Movie Review (MR) are used to verify the proposed models. These datasets are publicly available on the web and are widely used as test-verified datasets. The summary statistic features of the text network are shown in Table1.Table 1
Text network datasets.
DatasetsCDTrTeNR52529,1006,5322,56817,992OH237,4003,3574,04321,55720NG2018,84611,3147,53261,603R887,6745,4852,18915,362MR210,6627,1083,55429,426C indicates the category, D is the total number of texts, Tr is the training set, Te is the test set, and N is the number of vertices of the graph network.These benchmark text datasets were processed by Yao et al. [21], who converted the text datasets into graph network structures. Then, they used preprocessing to construct the adjacency matrix of the graph network input and input parameters. The dataset is divided into a training dataset and a test dataset in the same way.


#### 4.1.2. Baselines and Experimental Setting

We compare our HLHG with the following approaches: the convolutional neural network with pretrained vectors (CNN-rand) [22], the LSTM model with pretrained vectors (LSTM-pre) [23], the predictive text embedding for text classification (PTE) [24], the fast text classifier (fastText) [25], the simple word embedding model with simple pooling strategies (SWEM) [26], the label-embedding attentive model for text classification (LEAM) [27], the graph CNN model with the Chebyshev filter (GCN-C) [13], the graph CNN model with the spline filter (GCN-S) [5], the graph CNN model with the Fourier filter (GCN-F) [11], and the graph convolutional network for text classification (text GCN) [21]. The baseline models were tested by Yao et al. [21].In our HLHG-2 model, we set the dropout rate = 0.2. The learning rate is updated from Adam [28] during the training process. In our model, we set the L2 loss weight as 0, and we adopt early stopping. We set the learning rate to 0.02 for the R8 dataset, and the learning rates of the remaining datasets are all set to 0.01. We set different epochs for different datasets. The number of epochs in the R52 dataset is 350. The number of epochs in the OH and 20NG datasets is 200, and the number in the R8 and MR datasets is 60. In the HLHG-2 model, we set the number of hidden neurons in the 1st convolutional layer as 128 for all datasets.Except for the parameters in Table2, the other parameters are the same as in the HLHG-2 model.Table 2
The hyperparameters in our HLHG-3 model.
DatasetsDropoutLearning rateEpochsR520.60.005950OH0.20.0123020NG0.00.01210R80.20.005300MR0.10.0180For our HLHG-3, we set the number of hidden neurons in the first convolutional layer to 128 except for the MR dataset, which is set to 64. To obtain better training results, we separately set different hyperparameters such as the dropout rate, learning rate, and number of epochs for different datasets (see Table2). In addition, the other parameters of HLHG-3 are the same as those in HLHG-2.We construct the graph network for our HLHG-2 and HLHG-3 models, and the feature matrix and other parameters are the same as those by Yao et al. [21].


#### 4.1.3. Results

We show supervised text classification accuracies for the five datasets in Table3. We demonstrate how our model performs on common splits that were taken from Yao et al.’s study [21].Table 3
Text network classification accuracy.
MethodsR52OH20NGR8MRCNN-rand [22]87.5958.4482.1595.7177.75LSTM [23]85.5441.1365.7193.6875.06LSTM-pre [23]90.4851.1075.4396.0977.33PTE [24]90.7153.5876.7496.6970.23fastText [25]92.8157.7079.3896.1375.14SWEM [26]92.9463.1285.1695.3276.65LEAM [27]91.8458.5881.9193.3176.95GCN-C [13]92.7563.8681.4296.9977.22GCN-S [5]92.7462.82—96.8076.99GCN-F [11]93.2063.04—96.8976.74Text GCN [21]93.5668.3686.3497.0776.74HLHG-2 (ours)94.21 ± 0.1469.16 ± 0.1986.57 ± 0.0897.25 ± 0.1075.95 ± 0.14HLHG-3 (ours)94.33 ± 0.1669.36 ± 0.2486.35 ± 0.2497.25 ± 0.1276.49 ± 0.32Table3 presents the classification accuracies and standard deviations of our models and the benchmark on the text network data. In general, our HLHG-2 and HLHG-3 achieve high levels of performance. Specifically, they achieve the best performances on R52, OH, 20NG, and R8. Compared to the best performing approach, the proposed models yield worse accuracies on the MR dataset. In general, the HLHG-3 and HLHG-2 models perform equally well. More specifically, the 3rd order HLHG has slightly better classification accuracy than the 2nd order HLHG on most datasets. However, the performance difference is not very large. Overall, the proposed architecture with hybrid high- and low-order neighborhoods has good classification performance, which indicates that it effectively preserves the topological information of the graph, and it also obtains a high-quality representation of the nodes.The benchmark test results are copied from [8]. The mean standard deviation of our model is the average of 100 runs.Table4 shows the comparison of the network complexity and the number of parameters with the Text GCN [21]. Our HLHG can match the Text GCN with respect to computational complexity while requiring fewer parameters than the Text GCN. As described in Section 3.3, the number of features in the dataset is much larger than the number of neurons in the hidden convolutional layer. Therefore, we only compare the computational complexity and number of parameters of the first convolutional layer in our HLHG model. In Table 4, Comp. and Params represent the computational complexity and the number of parameters in the first layer of the graph convolutional network, respectively. In the computational complexity results, the first constant denotes the number of neurons in the first convolutional layer and the second constant denotes the order of the adjacency matrix. The parameter m denotes the number of nonzero entries of the sparse regularization adjacency matrix. The parameter r denotes the feature dimension of the nodes in the graph network.Table 4
Comparison of network computational complexity and the number of parameters.
ApproachesComp.ParamsText GCN [21]O (200×1×m×r)O (200×r)HLHG-2 (ours)O (128×2×m×r)O (128×r)HLHG-3 (ours)O (64×3×m×r) (MR dataset)O (64×r) (MR dataset)O (128×3×m×r) (other datasets)O (128×r) (other datasets)In the Text GCN [21], the number of hidden neurons in the first convolutional layer is 200; therefore, the complexity and params are 200. In our HLHG-2 model, 128 denotes the number of hidden neurons in the first convolutional layer and 2 represents the highest order of HLHG-2. In our HLHG-3 model, 128 and 64 denote the number of hidden neurons in the first convolutional layer and 3 represents the highest order of the corresponding model. The result in Table 4 shows that our HLHG-3 model has better computational complexity for the MR dataset. Because of the weight sharing in the different order neighborhoods, our HLHG models require fewer trainable weight parameters. Especially on the MR dataset, the number of parameters is only 1/3 of that of the Text GCN [21].


### 4.2. Semisupervised Node Classification

We conduct semisupervised learning on three benchmark citation network datasets to compare the node classification accuracy of HLHG with some classical approaches and with some graph convolutional neural network approaches. The graph semisupervised learning corresponds to the process of “label” spreading on citation networks.


#### 4.2.1. Datasets

In semisupervised node classification, we use the CiteSeer, Cora, and PubMed citation network datasets [29]. In these citation datasets, the nodes represent the articles that were published in the corresponding journal. The edges between the two nodes represent references from one article to another, and the tags represent the topics of the articles. The citation link constructs an adjacency matrix. Those datasets have low label rates. The summary statistic features of the citation graph are shown in Table 5.Table 5
Citation network datasets.
DatasetsNEFLCCora2708542914330.0527CiteSeer3327473237030.0366PubMed19717443385000.0033N means the number of nodes of citations, E means the number of edges between citations, F means the number of features of the nodes, L denotes the labeling rate, and C denotes the number of classes.


#### 4.2.2. Baselines and Experimental Setting

We compare our HLHG with the same baseline methods as by Abu-El-Haija et al. [15] and Yang et al. [30]. The baselines are as follows: manifold regularization (ManiReg) [31], semisupervised embedding (SemiEmb) [32], label propagation (LP) [33], skip-gram-based graph embeddings (DeepWalk) [34], the iterative classification algorithm (ICA) [35], Planetoid [30], HO [14], and MixHop [15].For the HLHG-2 model, we use the following parameters for the citation datasets (Cora, CiteSeer, and PubMed): 16 (number of hidden units), 0.5 (dropout rate), 0.0005 (L2 regularization), 10 (early stopping), 300 (number of epochs), and 0.01 (learning rate).For tthe HLHG-3 model, we set different numbers of hidden neurons for the different datasets. We set 8 hidden neurons for the CiteSeer dataset to reduce the computational complexity and the number of parameters, and set 10 hidden neurons for the Cora and PubMed datasets to capture richer features. The hyperparameters of the HLHG-3 are set as shown in Table6.Table 6
The hyperparameters of HLHG-3.
DatasetsDropoutLearning rateEarly stoppingEpochsCora0.50.01No500CiteSeer0.50.0055500PubMed0.60.011200


#### 4.2.3. Results

In the semisupervised experiments, we train and test our models on those citation network datasets following the methodology that was proposed by Yang et al. [30]. The classification accuracy is the average of 100 runs with random weight initializations.The benchmark test results were copied from [15, 30]. The mean standard deviation of our model is the average of 100 runs.In Table7, the node classification accuracies that are above the line are copied from Abu-El-Haija [14, 15] and Yang et al. [30]. The values below the line are our HLHG models.  ± represents the standard deviation of 100 runs with different random initializations. These splits utilize only 20 labeled nodes per class during training. We achieve the best test accuracies of 82.7% and 71.5% on the Cora and CiteSeer datasets, respectively. Compared with other high-order graph convolutional neural networks [14, 15] on the same datasets, they get the high-order information using linear combinations of features from farther distances. Our HLHG model acts nonlinearly to get the high-order neighborhood information.Table 7
Citation network classification test accuracy.
ApproachesCoraCiteSeerPubMedManiReg [31]59.560.170.7SemiEmb [32]59.059.671.1LP [33]68.045.363.0DeepWalk [34]67.243.265.3ICA [35]75.169.173.9Planetoid [30]75.764.777.2GCN [6]81.570.379.0HO-3 [14]81.6 ± 0.4771.2 ± 0.9480.0 ± 0.64HO-4 [14]81.6 ± 0.6371.2 ± 0.8480.1 ± 0.65MixHop [15]81.8 ± 0.6271.4 ± 0.8180.0 ± 1.10MixHop (learned) [15]81.9 ± 0.4071.4 ± 0.8180.8 ± 0.58HLHG-2 (ours)82.7 ± 0.2871.5 ± 0.2279.1 ± 0.18HLHG-3 (ours)82.7 ± 0.2971.5 ± 0.3979.3 ± 0.15In Table8, we compare the network complexity and the number of parameters with the other high-order graph convolutional networks and the classic GCN. The result shows that our model has the same computational complexity as other approaches. With respect to the number of parameters, our HLHG-3 model has fewer parameters than the GCN [6]. The reason is that our model shares the weights in the same layer among the different order neighborhood matrixes.Table 8
Comparison of network complexity and number of parameters.
MethodsComp.ParamsGCN [6]O (16×m×r)O (16×r)HO-3 [14]O (10×3×m×r)O (10×3×r)HO-4 [14]O (10×4×m×r)O (10×4×rr)MixHop [15]O (20×2×m×r)O (20×3×r)MixHop (learned) [15]O (20×2×m×r)O (60×r)HLHG-2 (ours)O (16×2×m×r)O (16×r)HLHG-3 (ours)O (8×3×m×r) (CiteSeer)O (8×r) (CiteSeer)O (10×3×m×r) (Cora, PubMed)O (10×r) (Cora, PubMed)


## 4.1. Supervised Text Network Classification

We conduct supervised learning on five benchmark text graph datasets to compare the classification accuracy of HLHG with the graph convolutional neural network and other deep learning approaches.


### 4.1.1. Datasets

In our supervised experiments, the 20-Newsgroups (20NG), Ohsumed, R52 and R8 of Reuters 21578, and Movie Review (MR) are used to verify the proposed models. These datasets are publicly available on the web and are widely used as test-verified datasets. The summary statistic features of the text network are shown in Table1.Table 1
Text network datasets.
DatasetsCDTrTeNR52529,1006,5322,56817,992OH237,4003,3574,04321,55720NG2018,84611,3147,53261,603R887,6745,4852,18915,362MR210,6627,1083,55429,426C indicates the category, D is the total number of texts, Tr is the training set, Te is the test set, and N is the number of vertices of the graph network.These benchmark text datasets were processed by Yao et al. [21], who converted the text datasets into graph network structures. Then, they used preprocessing to construct the adjacency matrix of the graph network input and input parameters. The dataset is divided into a training dataset and a test dataset in the same way.


### 4.1.2. Baselines and Experimental Setting

We compare our HLHG with the following approaches: the convolutional neural network with pretrained vectors (CNN-rand) [22], the LSTM model with pretrained vectors (LSTM-pre) [23], the predictive text embedding for text classification (PTE) [24], the fast text classifier (fastText) [25], the simple word embedding model with simple pooling strategies (SWEM) [26], the label-embedding attentive model for text classification (LEAM) [27], the graph CNN model with the Chebyshev filter (GCN-C) [13], the graph CNN model with the spline filter (GCN-S) [5], the graph CNN model with the Fourier filter (GCN-F) [11], and the graph convolutional network for text classification (text GCN) [21]. The baseline models were tested by Yao et al. [21].In our HLHG-2 model, we set the dropout rate = 0.2. The learning rate is updated from Adam [28] during the training process. In our model, we set the L2 loss weight as 0, and we adopt early stopping. We set the learning rate to 0.02 for the R8 dataset, and the learning rates of the remaining datasets are all set to 0.01. We set different epochs for different datasets. The number of epochs in the R52 dataset is 350. The number of epochs in the OH and 20NG datasets is 200, and the number in the R8 and MR datasets is 60. In the HLHG-2 model, we set the number of hidden neurons in the 1st convolutional layer as 128 for all datasets.Except for the parameters in Table2, the other parameters are the same as in the HLHG-2 model.Table 2
The hyperparameters in our HLHG-3 model.
DatasetsDropoutLearning rateEpochsR520.60.005950OH0.20.0123020NG0.00.01210R80.20.005300MR0.10.0180For our HLHG-3, we set the number of hidden neurons in the first convolutional layer to 128 except for the MR dataset, which is set to 64. To obtain better training results, we separately set different hyperparameters such as the dropout rate, learning rate, and number of epochs for different datasets (see Table2). In addition, the other parameters of HLHG-3 are the same as those in HLHG-2.We construct the graph network for our HLHG-2 and HLHG-3 models, and the feature matrix and other parameters are the same as those by Yao et al. [21].


### 4.1.3. Results

We show supervised text classification accuracies for the five datasets in Table3. We demonstrate how our model performs on common splits that were taken from Yao et al.’s study [21].Table 3
Text network classification accuracy.
MethodsR52OH20NGR8MRCNN-rand [22]87.5958.4482.1595.7177.75LSTM [23]85.5441.1365.7193.6875.06LSTM-pre [23]90.4851.1075.4396.0977.33PTE [24]90.7153.5876.7496.6970.23fastText [25]92.8157.7079.3896.1375.14SWEM [26]92.9463.1285.1695.3276.65LEAM [27]91.8458.5881.9193.3176.95GCN-C [13]92.7563.8681.4296.9977.22GCN-S [5]92.7462.82—96.8076.99GCN-F [11]93.2063.04—96.8976.74Text GCN [21]93.5668.3686.3497.0776.74HLHG-2 (ours)94.21 ± 0.1469.16 ± 0.1986.57 ± 0.0897.25 ± 0.1075.95 ± 0.14HLHG-3 (ours)94.33 ± 0.1669.36 ± 0.2486.35 ± 0.2497.25 ± 0.1276.49 ± 0.32Table3 presents the classification accuracies and standard deviations of our models and the benchmark on the text network data. In general, our HLHG-2 and HLHG-3 achieve high levels of performance. Specifically, they achieve the best performances on R52, OH, 20NG, and R8. Compared to the best performing approach, the proposed models yield worse accuracies on the MR dataset. In general, the HLHG-3 and HLHG-2 models perform equally well. More specifically, the 3rd order HLHG has slightly better classification accuracy than the 2nd order HLHG on most datasets. However, the performance difference is not very large. Overall, the proposed architecture with hybrid high- and low-order neighborhoods has good classification performance, which indicates that it effectively preserves the topological information of the graph, and it also obtains a high-quality representation of the nodes.The benchmark test results are copied from [8]. The mean standard deviation of our model is the average of 100 runs.Table4 shows the comparison of the network complexity and the number of parameters with the Text GCN [21]. Our HLHG can match the Text GCN with respect to computational complexity while requiring fewer parameters than the Text GCN. As described in Section 3.3, the number of features in the dataset is much larger than the number of neurons in the hidden convolutional layer. Therefore, we only compare the computational complexity and number of parameters of the first convolutional layer in our HLHG model. In Table 4, Comp. and Params represent the computational complexity and the number of parameters in the first layer of the graph convolutional network, respectively. In the computational complexity results, the first constant denotes the number of neurons in the first convolutional layer and the second constant denotes the order of the adjacency matrix. The parameter m denotes the number of nonzero entries of the sparse regularization adjacency matrix. The parameter r denotes the feature dimension of the nodes in the graph network.Table 4
Comparison of network computational complexity and the number of parameters.
ApproachesComp.ParamsText GCN [21]O (200×1×m×r)O (200×r)HLHG-2 (ours)O (128×2×m×r)O (128×r)HLHG-3 (ours)O (64×3×m×r) (MR dataset)O (64×r) (MR dataset)O (128×3×m×r) (other datasets)O (128×r) (other datasets)In the Text GCN [21], the number of hidden neurons in the first convolutional layer is 200; therefore, the complexity and params are 200. In our HLHG-2 model, 128 denotes the number of hidden neurons in the first convolutional layer and 2 represents the highest order of HLHG-2. In our HLHG-3 model, 128 and 64 denote the number of hidden neurons in the first convolutional layer and 3 represents the highest order of the corresponding model. The result in Table 4 shows that our HLHG-3 model has better computational complexity for the MR dataset. Because of the weight sharing in the different order neighborhoods, our HLHG models require fewer trainable weight parameters. Especially on the MR dataset, the number of parameters is only 1/3 of that of the Text GCN [21].


## 4.1.1. Datasets

In our supervised experiments, the 20-Newsgroups (20NG), Ohsumed, R52 and R8 of Reuters 21578, and Movie Review (MR) are used to verify the proposed models. These datasets are publicly available on the web and are widely used as test-verified datasets. The summary statistic features of the text network are shown in Table1.Table 1
Text network datasets.
DatasetsCDTrTeNR52529,1006,5322,56817,992OH237,4003,3574,04321,55720NG2018,84611,3147,53261,603R887,6745,4852,18915,362MR210,6627,1083,55429,426C indicates the category, D is the total number of texts, Tr is the training set, Te is the test set, and N is the number of vertices of the graph network.These benchmark text datasets were processed by Yao et al. [21], who converted the text datasets into graph network structures. Then, they used preprocessing to construct the adjacency matrix of the graph network input and input parameters. The dataset is divided into a training dataset and a test dataset in the same way.


## 4.1.2. Baselines and Experimental Setting

We compare our HLHG with the following approaches: the convolutional neural network with pretrained vectors (CNN-rand) [22], the LSTM model with pretrained vectors (LSTM-pre) [23], the predictive text embedding for text classification (PTE) [24], the fast text classifier (fastText) [25], the simple word embedding model with simple pooling strategies (SWEM) [26], the label-embedding attentive model for text classification (LEAM) [27], the graph CNN model with the Chebyshev filter (GCN-C) [13], the graph CNN model with the spline filter (GCN-S) [5], the graph CNN model with the Fourier filter (GCN-F) [11], and the graph convolutional network for text classification (text GCN) [21]. The baseline models were tested by Yao et al. [21].In our HLHG-2 model, we set the dropout rate = 0.2. The learning rate is updated from Adam [28] during the training process. In our model, we set the L2 loss weight as 0, and we adopt early stopping. We set the learning rate to 0.02 for the R8 dataset, and the learning rates of the remaining datasets are all set to 0.01. We set different epochs for different datasets. The number of epochs in the R52 dataset is 350. The number of epochs in the OH and 20NG datasets is 200, and the number in the R8 and MR datasets is 60. In the HLHG-2 model, we set the number of hidden neurons in the 1st convolutional layer as 128 for all datasets.Except for the parameters in Table2, the other parameters are the same as in the HLHG-2 model.Table 2
The hyperparameters in our HLHG-3 model.
DatasetsDropoutLearning rateEpochsR520.60.005950OH0.20.0123020NG0.00.01210R80.20.005300MR0.10.0180For our HLHG-3, we set the number of hidden neurons in the first convolutional layer to 128 except for the MR dataset, which is set to 64. To obtain better training results, we separately set different hyperparameters such as the dropout rate, learning rate, and number of epochs for different datasets (see Table2). In addition, the other parameters of HLHG-3 are the same as those in HLHG-2.We construct the graph network for our HLHG-2 and HLHG-3 models, and the feature matrix and other parameters are the same as those by Yao et al. [21].


## 4.1.3. Results

We show supervised text classification accuracies for the five datasets in Table3. We demonstrate how our model performs on common splits that were taken from Yao et al.’s study [21].Table 3
Text network classification accuracy.
MethodsR52OH20NGR8MRCNN-rand [22]87.5958.4482.1595.7177.75LSTM [23]85.5441.1365.7193.6875.06LSTM-pre [23]90.4851.1075.4396.0977.33PTE [24]90.7153.5876.7496.6970.23fastText [25]92.8157.7079.3896.1375.14SWEM [26]92.9463.1285.1695.3276.65LEAM [27]91.8458.5881.9193.3176.95GCN-C [13]92.7563.8681.4296.9977.22GCN-S [5]92.7462.82—96.8076.99GCN-F [11]93.2063.04—96.8976.74Text GCN [21]93.5668.3686.3497.0776.74HLHG-2 (ours)94.21 ± 0.1469.16 ± 0.1986.57 ± 0.0897.25 ± 0.1075.95 ± 0.14HLHG-3 (ours)94.33 ± 0.1669.36 ± 0.2486.35 ± 0.2497.25 ± 0.1276.49 ± 0.32Table3 presents the classification accuracies and standard deviations of our models and the benchmark on the text network data. In general, our HLHG-2 and HLHG-3 achieve high levels of performance. Specifically, they achieve the best performances on R52, OH, 20NG, and R8. Compared to the best performing approach, the proposed models yield worse accuracies on the MR dataset. In general, the HLHG-3 and HLHG-2 models perform equally well. More specifically, the 3rd order HLHG has slightly better classification accuracy than the 2nd order HLHG on most datasets. However, the performance difference is not very large. Overall, the proposed architecture with hybrid high- and low-order neighborhoods has good classification performance, which indicates that it effectively preserves the topological information of the graph, and it also obtains a high-quality representation of the nodes.The benchmark test results are copied from [8]. The mean standard deviation of our model is the average of 100 runs.Table4 shows the comparison of the network complexity and the number of parameters with the Text GCN [21]. Our HLHG can match the Text GCN with respect to computational complexity while requiring fewer parameters than the Text GCN. As described in Section 3.3, the number of features in the dataset is much larger than the number of neurons in the hidden convolutional layer. Therefore, we only compare the computational complexity and number of parameters of the first convolutional layer in our HLHG model. In Table 4, Comp. and Params represent the computational complexity and the number of parameters in the first layer of the graph convolutional network, respectively. In the computational complexity results, the first constant denotes the number of neurons in the first convolutional layer and the second constant denotes the order of the adjacency matrix. The parameter m denotes the number of nonzero entries of the sparse regularization adjacency matrix. The parameter r denotes the feature dimension of the nodes in the graph network.Table 4
Comparison of network computational complexity and the number of parameters.
ApproachesComp.ParamsText GCN [21]O (200×1×m×r)O (200×r)HLHG-2 (ours)O (128×2×m×r)O (128×r)HLHG-3 (ours)O (64×3×m×r) (MR dataset)O (64×r) (MR dataset)O (128×3×m×r) (other datasets)O (128×r) (other datasets)In the Text GCN [21], the number of hidden neurons in the first convolutional layer is 200; therefore, the complexity and params are 200. In our HLHG-2 model, 128 denotes the number of hidden neurons in the first convolutional layer and 2 represents the highest order of HLHG-2. In our HLHG-3 model, 128 and 64 denote the number of hidden neurons in the first convolutional layer and 3 represents the highest order of the corresponding model. The result in Table 4 shows that our HLHG-3 model has better computational complexity for the MR dataset. Because of the weight sharing in the different order neighborhoods, our HLHG models require fewer trainable weight parameters. Especially on the MR dataset, the number of parameters is only 1/3 of that of the Text GCN [21].


## 4.2. Semisupervised Node Classification

We conduct semisupervised learning on three benchmark citation network datasets to compare the node classification accuracy of HLHG with some classical approaches and with some graph convolutional neural network approaches. The graph semisupervised learning corresponds to the process of “label” spreading on citation networks.


### 4.2.1. Datasets

In semisupervised node classification, we use the CiteSeer, Cora, and PubMed citation network datasets [29]. In these citation datasets, the nodes represent the articles that were published in the corresponding journal. The edges between the two nodes represent references from one article to another, and the tags represent the topics of the articles. The citation link constructs an adjacency matrix. Those datasets have low label rates. The summary statistic features of the citation graph are shown in Table 5.Table 5
Citation network datasets.
DatasetsNEFLCCora2708542914330.0527CiteSeer3327473237030.0366PubMed19717443385000.0033N means the number of nodes of citations, E means the number of edges between citations, F means the number of features of the nodes, L denotes the labeling rate, and C denotes the number of classes.


### 4.2.2. Baselines and Experimental Setting

We compare our HLHG with the same baseline methods as by Abu-El-Haija et al. [15] and Yang et al. [30]. The baselines are as follows: manifold regularization (ManiReg) [31], semisupervised embedding (SemiEmb) [32], label propagation (LP) [33], skip-gram-based graph embeddings (DeepWalk) [34], the iterative classification algorithm (ICA) [35], Planetoid [30], HO [14], and MixHop [15].For the HLHG-2 model, we use the following parameters for the citation datasets (Cora, CiteSeer, and PubMed): 16 (number of hidden units), 0.5 (dropout rate), 0.0005 (L2 regularization), 10 (early stopping), 300 (number of epochs), and 0.01 (learning rate).For tthe HLHG-3 model, we set different numbers of hidden neurons for the different datasets. We set 8 hidden neurons for the CiteSeer dataset to reduce the computational complexity and the number of parameters, and set 10 hidden neurons for the Cora and PubMed datasets to capture richer features. The hyperparameters of the HLHG-3 are set as shown in Table6.Table 6
The hyperparameters of HLHG-3.
DatasetsDropoutLearning rateEarly stoppingEpochsCora0.50.01No500CiteSeer0.50.0055500PubMed0.60.011200


### 4.2.3. Results

In the semisupervised experiments, we train and test our models on those citation network datasets following the methodology that was proposed by Yang et al. [30]. The classification accuracy is the average of 100 runs with random weight initializations.The benchmark test results were copied from [15, 30]. The mean standard deviation of our model is the average of 100 runs.In Table7, the node classification accuracies that are above the line are copied from Abu-El-Haija [14, 15] and Yang et al. [30]. The values below the line are our HLHG models.  ± represents the standard deviation of 100 runs with different random initializations. These splits utilize only 20 labeled nodes per class during training. We achieve the best test accuracies of 82.7% and 71.5% on the Cora and CiteSeer datasets, respectively. Compared with other high-order graph convolutional neural networks [14, 15] on the same datasets, they get the high-order information using linear combinations of features from farther distances. Our HLHG model acts nonlinearly to get the high-order neighborhood information.Table 7
Citation network classification test accuracy.
ApproachesCoraCiteSeerPubMedManiReg [31]59.560.170.7SemiEmb [32]59.059.671.1LP [33]68.045.363.0DeepWalk [34]67.243.265.3ICA [35]75.169.173.9Planetoid [30]75.764.777.2GCN [6]81.570.379.0HO-3 [14]81.6 ± 0.4771.2 ± 0.9480.0 ± 0.64HO-4 [14]81.6 ± 0.6371.2 ± 0.8480.1 ± 0.65MixHop [15]81.8 ± 0.6271.4 ± 0.8180.0 ± 1.10MixHop (learned) [15]81.9 ± 0.4071.4 ± 0.8180.8 ± 0.58HLHG-2 (ours)82.7 ± 0.2871.5 ± 0.2279.1 ± 0.18HLHG-3 (ours)82.7 ± 0.2971.5 ± 0.3979.3 ± 0.15In Table8, we compare the network complexity and the number of parameters with the other high-order graph convolutional networks and the classic GCN. The result shows that our model has the same computational complexity as other approaches. With respect to the number of parameters, our HLHG-3 model has fewer parameters than the GCN [6]. The reason is that our model shares the weights in the same layer among the different order neighborhood matrixes.Table 8
Comparison of network complexity and number of parameters.
MethodsComp.ParamsGCN [6]O (16×m×r)O (16×r)HO-3 [14]O (10×3×m×r)O (10×3×r)HO-4 [14]O (10×4×m×r)O (10×4×rr)MixHop [15]O (20×2×m×r)O (20×3×r)MixHop (learned) [15]O (20×2×m×r)O (60×r)HLHG-2 (ours)O (16×2×m×r)O (16×r)HLHG-3 (ours)O (8×3×m×r) (CiteSeer)O (8×r) (CiteSeer)O (10×3×m×r) (Cora, PubMed)O (10×r) (Cora, PubMed)


## 4.2.1. Datasets

In semisupervised node classification, we use the CiteSeer, Cora, and PubMed citation network datasets [29]. In these citation datasets, the nodes represent the articles that were published in the corresponding journal. The edges between the two nodes represent references from one article to another, and the tags represent the topics of the articles. The citation link constructs an adjacency matrix. Those datasets have low label rates. The summary statistic features of the citation graph are shown in Table 5.Table 5
Citation network datasets.
DatasetsNEFLCCora2708542914330.0527CiteSeer3327473237030.0366PubMed19717443385000.0033N means the number of nodes of citations, E means the number of edges between citations, F means the number of features of the nodes, L denotes the labeling rate, and C denotes the number of classes.


## 4.2.2. Baselines and Experimental Setting

We compare our HLHG with the same baseline methods as by Abu-El-Haija et al. [15] and Yang et al. [30]. The baselines are as follows: manifold regularization (ManiReg) [31], semisupervised embedding (SemiEmb) [32], label propagation (LP) [33], skip-gram-based graph embeddings (DeepWalk) [34], the iterative classification algorithm (ICA) [35], Planetoid [30], HO [14], and MixHop [15].For the HLHG-2 model, we use the following parameters for the citation datasets (Cora, CiteSeer, and PubMed): 16 (number of hidden units), 0.5 (dropout rate), 0.0005 (L2 regularization), 10 (early stopping), 300 (number of epochs), and 0.01 (learning rate).For tthe HLHG-3 model, we set different numbers of hidden neurons for the different datasets. We set 8 hidden neurons for the CiteSeer dataset to reduce the computational complexity and the number of parameters, and set 10 hidden neurons for the Cora and PubMed datasets to capture richer features. The hyperparameters of the HLHG-3 are set as shown in Table6.Table 6
The hyperparameters of HLHG-3.
DatasetsDropoutLearning rateEarly stoppingEpochsCora0.50.01No500CiteSeer0.50.0055500PubMed0.60.011200


## 4.2.3. Results

In the semisupervised experiments, we train and test our models on those citation network datasets following the methodology that was proposed by Yang et al. [30]. The classification accuracy is the average of 100 runs with random weight initializations.The benchmark test results were copied from [15, 30]. The mean standard deviation of our model is the average of 100 runs.In Table7, the node classification accuracies that are above the line are copied from Abu-El-Haija [14, 15] and Yang et al. [30]. The values below the line are our HLHG models.  ± represents the standard deviation of 100 runs with different random initializations. These splits utilize only 20 labeled nodes per class during training. We achieve the best test accuracies of 82.7% and 71.5% on the Cora and CiteSeer datasets, respectively. Compared with other high-order graph convolutional neural networks [14, 15] on the same datasets, they get the high-order information using linear combinations of features from farther distances. Our HLHG model acts nonlinearly to get the high-order neighborhood information.Table 7
Citation network classification test accuracy.
ApproachesCoraCiteSeerPubMedManiReg [31]59.560.170.7SemiEmb [32]59.059.671.1LP [33]68.045.363.0DeepWalk [34]67.243.265.3ICA [35]75.169.173.9Planetoid [30]75.764.777.2GCN [6]81.570.379.0HO-3 [14]81.6 ± 0.4771.2 ± 0.9480.0 ± 0.64HO-4 [14]81.6 ± 0.6371.2 ± 0.8480.1 ± 0.65MixHop [15]81.8 ± 0.6271.4 ± 0.8180.0 ± 1.10MixHop (learned) [15]81.9 ± 0.4071.4 ± 0.8180.8 ± 0.58HLHG-2 (ours)82.7 ± 0.2871.5 ± 0.2279.1 ± 0.18HLHG-3 (ours)82.7 ± 0.2971.5 ± 0.3979.3 ± 0.15In Table8, we compare the network complexity and the number of parameters with the other high-order graph convolutional networks and the classic GCN. The result shows that our model has the same computational complexity as other approaches. With respect to the number of parameters, our HLHG-3 model has fewer parameters than the GCN [6]. The reason is that our model shares the weights in the same layer among the different order neighborhood matrixes.Table 8
Comparison of network complexity and number of parameters.
MethodsComp.ParamsGCN [6]O (16×m×r)O (16×r)HO-3 [14]O (10×3×m×r)O (10×3×r)HO-4 [14]O (10×4×m×r)O (10×4×rr)MixHop [15]O (20×2×m×r)O (20×3×r)MixHop (learned) [15]O (20×2×m×r)O (60×r)HLHG-2 (ours)O (16×2×m×r)O (16×r)HLHG-3 (ours)O (8×3×m×r) (CiteSeer)O (8×r) (CiteSeer)O (10×3×m×r) (Cora, PubMed)O (10×r) (Cora, PubMed)


## 5. Conclusion

In this paper, we propose a hybrid lower-order and higher-order GCN model for the supervised classification of text network datasets and for semisupervised classification in a citation network. In our model, we propose a novel nonlinear information fusion layer to combine the low- and higher-order neighborhoods. To reduce the number of parameters, we propose sharing the weights in the same convolutional layer with different order neighborhoods. Experiments on the two network datasets suggest that HLHG has the capability to fuse higher-order neighborhoods for supervised classification and semisupervised classification. Our model significantly outperforms the benchmarks. We also find that the computational complexity and the number of parameters are less than those of the high-order method. In order to obtain more neighborhood information, we could use more higher-order adjacency matrix. However, the direct use of higher orders may lead to oversmoothing problems. Therefore, in future research work, we will extend our HLHG models to fuse graph attention networks [36] to develop a deeper graph convolutional network.



---

*Source: 3283890-2020-06-23.xml*