Neighborhood Convolutional Network: A New Paradigm of Graph Neural Networks for Node Classification

Given a network modeled as an undirected and attributed graph $G=(\mathcal{V},\mathcal{E},\mathbf{X})$, where $\mathcal{V}$ and $\mathcal{E}$ denote the sets of nodes and edges, respectively, and $\mathbf{X}\in\mathbb{R}^{n\times d}$ represents the attribute feature matrix of nodes given that $n$ is the number of nodes and $d$ the dimension of feature vector. Let $\mathbf{A}\in\mathbb{R}^{n\times n}$ represent the adjacency matrix, and the normalized adjacency matrix is defined as $\hat{\mathbf{A}}=\mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2}$, where $\mathbf{D}$ is the diagonal degree matrix given as $\mathbf{D}_{ii}=\sum_{j=1}^{n}\mathbf{A}_{ij}$. $\mathbf{Y}\in\mathbb{R}^{n\times c}$ denotes the label matrix of nodes, where $c$ denotes the number of labels. Given a set of nodes $V_{l}$ whose labels are known, the node classification task is to predict the labels for nodes $V/V_{l}$.

In this paper, we use the edge homophily ratio $\mathcal{H}(G)$ (Zhu et al., 2020; He et al., 2022; Chien et al., 2021) to measure the homophily level of a graph $G$, such that

where $\mathcal{N}_{v_{i}}$ denotes the immediate neighbors of node $v_{i}$. Then, $\mathcal{H}(G)\in[0,1]$ denotes the degree of homophily, where $\mathcal{H}(G)\to 1$ indicates that $G$ has strong homophily and $\mathcal{H}(G)\to 0$ indicates that $G$ has low homophily (strong heterophily).

The key idea of Graph Convolutional Network (GCN) is to apply the first-order approximation of spectral convolution (Defferrard et al., 2016) that aggregates the information of immediate neighbors. A GCN layer can be given as

where $\hat{\tilde{\mathbf{A}}}=\tilde{\mathbf{D}}^{-1/2}\tilde{\mathbf{A}}\tilde{\mathbf{D}}^{-1/2}$ represents the normalized adjacency matrix given that $\tilde{\mathbf{A}}$ is the adjacency matrix with self-loops and $\widetilde{\mathbf{D}}$ is the corresponding diagonal degree matrix, $\mathbf{H}^{(l)}\in\mathbb{R}^{n\times d^{(l)}}$ denotes the representations of nodes in the $l$-th layer, $\mathbf{W}^{(l)}\in\mathbb{R}^{d^{(l)}\times d^{(l+1)}}$ is a learnable parameter matrix, and $\sigma(\cdot)$ represents a non-linear activation function.

According to Equation 2, a GCN layer contains two coupled operations, namely neighborhood aggregation and feature transformation. Such coupled framework could cause the over-smoothing issue (Chen et al., 2020a) and increase the training cost (Wu et al., 2019) when stacking many GCN layers. To address these issues, decoupled GCN (Chien et al., 2021) separates the two operations by removing the activation function and collapsing the parameter matrices between layers. In this way, the model can be regarded as a combination of an aggregation module (also known as a feature propagation module) and a feature transformation module. A general framework of decoupled GCN is given as

where $\boldsymbol{f}_{\theta}$ denotes a neural network (e.g., MLP) with a parameter set $\theta$, $\mathbf{H}^{(k)}\in\mathbb{R}^{n\times d^{\prime}}$ and $\alpha_{k}$ represent the representations of nodes and aggregation weight at step $k$, respectively. Here $K$ is the total propagation step, and $\mathbf{Z}\in\mathbb{R}^{n\times d^{\prime}}$ denotes the output of decoupled GCN.

In the data pre-processing stage, we apply a novel aggregator called grid-like neighborhood aggregator (GNA) to preserve the information of multi-hop neighborhoods for each node that can be effectively used for feature extraction. GNA contains two main steps, namely propagating the features of multi-hop neighborhoods and constructing a grid-like feature matrix. First, GNA utilizes a propagation operation to aggregate the attribute features of neighborhood nodes, such that

where $\mathbf{S}^{(k)}\in\mathbb{R}^{n\times n}$ denotes an aggregation weight matrix at the propagation step $k$, and $\mathbf{S}^{(0)}$ is initialized as the identity matrix $\mathbf{I}_{n}$, such that we consider the nodes themselves as their 0-hop neighborhood node. $\mathbf{B}^{(k)}\in\mathbb{R}^{n\times d}$ represents the features aggregated from the $k$-hop neighborhood nodes.

In this paper, we apply the approximate personalized PageRank (Klicpera et al., 2019a; Dong et al., 2021) to calculate $\mathbf{S}^{(k)}$, given as $\mathbf{S}^{(k)}=(1-\gamma)^{k}\hat{\mathbf{A}}^{k}+\gamma\sum_{i=0}^{k-1}(1-\gamma)^{i}\hat{\mathbf{A}}^{i}$, where $\gamma\in{(0,1]}$ is the teleport probability. Note that the propagation operation can be implemented by various methods according to the actual demands. For instance, we can set $\mathbf{S}^{(k)}=\hat{\mathbf{A}}^{k}$ that utilizes the standard random walk to obtain the features of neighborhood nodes.

In the second step, GNA transfers all the features obtained by the first step into a grid-like feature matrix. Specifically, for node $v$, let $\{\mathbf{B}^{(0)}_{v},\mathbf{B}^{(1)}_{v}$ $,\cdots,\mathbf{B}^{(K)}_{v}\}$ represent the features aggregated by performing the propagation operation on the node. GNA constructs a grid-like feature matrix $\mathbf{T}_{v}\in\mathbb{R}^{(K+1)\times d}$ by stacking $\{\mathbf{B}^{(0)}_{v},\mathbf{B}^{(1)}_{v}$ $,\cdots,\mathbf{B}^{(K)}_{v}\}$ in the ascending order according to the propagation step. In this way, the grid-like feature matrix preserves the feature information of multi-hop neighborhoods from shallow to deep. For instance, the feature vector of the $k$th row in the grid-like feature matrix contains wider extracted information than those of less than $k$th rows. Such design brings non-Euclidean space of independent nodes to order. As a result, more advanced deep learning modules, such as CNN and RNN, can be applied on the grid-like feature matrix to extract more semantic information for nodes.

Note that the whole data pre-processing is non-parametric and can be conducted before the model training process, and therefore it can significantly reduce the training cost. Moreover, by assigning an independent feature matrix for each node, the mini-batch training strategy can be efficiently performed on the training model that guarantees the scalability for large-scale graphs.

In the feature extraction stage, we capture the complex semantic information from the grid-like neighborhood feature matrix by using a CNN-based module. Specifically, we design a neural network block consisting of two convolutional layers with different kernel sizes. For the first convolutional layer, we set the kernel size as $((\lfloor K/2\rfloor+1),1)$ that can capture the semantic association between the features of different hop neighborhoods, where $\lfloor\cdot\rfloor$ denotes the operation of rounding down the value. For the second convolutional layer, the kernel size is set as $(1,1)$ for feature transformation, which is a popular design of CNN in computer vision (He et al., 2016).

In NCN, we first utilize a linear layer to reduce the dimension of the grid-like neighborhood feature matrix since the dimension of attribute features could be very large in some networks. By stacking two proposed neural network blocks, NCN extracts a feature matrix $\mathbf{H}^{N}\in\mathbb{R}^{n\times d^{\prime}}$ that represents the semantic information from multi-hop neighborhoods, given as:

where $\mathbf{T}\in\mathbb{R}^{n\times(K+1)\times d}$ is the grid-like neighborhood feature matrix, $\sigma(\cdot)$ denotes an activation function, and Block1 and Block2 are the two convolutional blocks, respectively.

Note that the design of the neural network block can be flexibly adjusted according to different scenarios. In other words, various convolutional layers can be applied to improve the performance of NCN. We will study the influence of combining a variety of convolutional layers in our future work.

Although the extracted features include rich semantic information of multi-hop neighborhoods, the function of raw attribute features of nodes is seriously weakened. Recent studies (Zhu et al., 2020; Chien et al., 2021; Li et al., 2022) prove that utilizing only the raw attribute features of nodes can also achieve a competitive performance on some graphs. It is because, in some graphs, the raw attribute features of nodes dominate the node labels. Therefore, to accurately predict the labels of nodes, a feasible solution is to learn the representations of nodes by combining the extracted features and the raw attribute features.

To this end, we present an adaptive feature fusion module that can fuse the extracted features and the raw attribute features for different graphs. First, we transfer the raw feature matrix $\mathbf{X}$ into a matrix whose shape is the same as the extracted feature matrix, such that:

where $\mathbf{W_{R}}\in\mathbb{R}^{d\times d^{\prime}}$ denotes a parameter matrix. Then, we apply a learnable weight layer to adaptively calculate the weights for the feature matrices of $\mathbf{H}^{R}$ and $\mathbf{H}^{N}$, given as:

where $||$ denotes the concatenation operation and $\varphi(\cdot)$ is a linear layer with a parameter matrix $\mathbf{W}_{a}\in\mathbb{R}^{2d^{\prime}\times 2}$ shared by all nodes. The output $\mathbf{a}\in\mathbb{R}^{n\times 2}$ denotes the aggregation weight vector in which $\mathbf{a}_{0}$ and $\mathbf{a}_{1}$ are the aggregation weights of $\mathbf{H}^{R}$ and $\mathbf{H}^{N}$, respectively. Based on the aggregation weights, the final representation of nodes is calculated as:

where $\odot$ denotes the element-wise product. In practice, the broadcast mechanism of the programming tools (e.g., Pytorch) guarantees the calculation of Equation 8 by repeating the columns of $\mathbf{a}_{0}$ and $\mathbf{a}_{1}$ for matching the dimensions of $\mathbf{H}^{R}$ and $\mathbf{H}^{N}$ respectively.

Mask Training Additionally, inspired by the famous training technique of Dropout (Srivastava et al., 2014), we propose a training strategy called mask training that randomly sets $\mathbf{a}_{0}$ or $\mathbf{a}_{1}$ to zero during the training process. In this way, NCN can alleviate the over-fitting problem during the training. Specifically, for each training epoch, we randomly partition the training set into three parts $N_{0}$, $N_{1}$ and $N_{2}$ according to the ratios, $\beta$, $\beta$ and $1-2*\beta$, respectively, where $\beta\in[0,0.5)$ is a hyperparameter. We set $\mathbf{a}_{0}=0$ for nodes in $N_{0}$ and $\mathbf{a}_{1}=0$ for nodes in $N_{1}$. Then values of $\mathbf{a}_{0}$ and $\mathbf{a}_{1}$ are kept for the remaining nodes in $N_{2}$.

Following the common setting (Klicpera et al., 2019a; Chien et al., 2021; He et al., 2022), we apply MLP to predict the labels of nodes according to $\mathbf{H}^{F}$, such that:

where $\hat{\mathbf{Y}}\in\mathbb{R}^{n\times c}$ denotes the predicted labels. Then, we utilize the Cross-Entropy loss, which is widely used in the node classification task (Kipf and Welling, 2017; Klicpera et al., 2019a; Chien et al., 2021), to calculate the loss, given that

The overall learning algorithm of NCN is presented in Algorithm 1.

Datasets. We utilize ten widely used datasets, including homophilic graphs and heterophilic graphs for experiments. The homophilic graphs contain Cora, Citeseer, Pubmed, Computers, and Photo (Chien et al., 2021), and the heterophilic graphs include Actor, Squirrel, Chameleon, Texas, and Cornell  (Pei et al., 2020). The statistics of datasets are reported in Table 1, where the edge homophily ratio $\mathcal{H}$ measures the degree of homophily as introduced in Section 2.2.

For the homophilic graphs, Cora, Citeseer and Pubmed are constructed from the citation networks, where nodes represent papers, and edges represent citation relationships between papers. Computer and Photo are extracted from the Amazon co-purchase graph, where nodes represent goods and edges indicate that two goods are frequently bought together.

For the heterophilic graphs, Actor, Squirrel and Chameleon derive from the Wikipedia pages. Actor is the actor-only induced subgraph of the film-director-actor-writer network where nodes correspond to actors, and the edge between two nodes denotes co-occurrence on the same Wikipedia. Squirrel and Chameleon are page-page networks on specific topics in Wikipedia where nodes represent web pages, and edges are mutual links between pages. Cornell and Texas are web page datasets collected from computer science departments of various universities, where nodes represent web pages and edges are hyperlinks between them.

Baselines. We utilize eight state-of-the-art methods of node classification as the baselines for comparison, which are GCN (Kipf and Welling, 2017), GAT (Velikovi et al., 2018), SGC (Wu et al., 2019), APPNP (Klicpera et al., 2019a), LINKX (Lim et al., 2021), GPR-GNN (Chien et al., 2021), BM-GCN (He et al., 2022), and GloGNN (Li et al., 2022). Note that the first four methods apply to homophilic graphs, while the latter four methods are designed for homophilic graphs and heterophilic graphs simultaneously. In addition, we also use MLP as a simple comparison method that only utilizes the attribute features of nodes to predict the node labels.

Settings. We randomly split each dataset into 60%/20%/20% train/val/test three parts for experiments. For the baselines, we use their default hyper-parameters as presented in their papers, and for NCN, we use the grid search method to determine the hyper-parameters. We try the hidden dimension in $\{128,256,512\}$, $\beta$ in $\{0.1,0.2,0.3,0.4\}$, and the propagation steps in $\{2,4,\cdots,10\}$. Parameters are optimized with AdamW (Loshchilov and Hutter, 2019) optimizer, with the learning rate of in $\{1e-3,5e-4,1e-4,\}$ and weight decay in $\{1e-4,1e-5\}$. The batch size is set to 1000. The training process is early stopped within 50 epochs. All experiments are conducted on a Linux server with 1 I9-9900k CPU, 1 RTX 2080TI GPU and 64G RAM.

We adopt accuracy as the evaluation metric for the node classification task to compare the model performance. We run ten times for each method with random splits and report the average results as summarized in Table 2. We can observe that our NCN achieves the best performance on almost all the datasets except Citeseer and Actor. Particularly, NCN outperforms GloGNN, BM-GCN and LINKX, which are powerful methods for node classification on heterophilic graphs, demonstrating the effectiveness of NCN. Although NCN misses the best results on Citeseer and Actor, it still exhibits competitive performances on these datasets. The results confirm that NCN is capable of the node classification task on both homophilic and heterophilic graphs, showing the effectiveness of NCN. Moreover, NCN beats representative decoupled GCNs (APPNP, SGC and GPRGNN) on all the datasets (except behind GPRGNN on Citeseer), indicating that the designs of NCN are beneficial for learning the powerful node representations from the information of multi-hop neighborhoods.

We compare NCN with its two variants on all datasets for evaluating the effectiveness of the key designs in NCN. The two variants of NCN are described as follows

• •

  NCN-w/o-RA: We remove the adaptive feature fusion from NCN, and only the features learned from the neighborhood information is preserved.

• •

  NCN-w/o-Mask: We do not utilize the mask training strategy in this variant.

According to the comparison results in Figure 4, we can find that NCN outperforms the variants on all datasets, demonstrating that the proposed feature fusion module and mask-based training strategy can improve the performance for the node classification task. Furthermore, NCN-w/o-Mask beats NCN-w/o-RA on all datasets, indicating that introducing the original features of nodes plays a vital role in learning meaningful representations of the nodes.

In this subsection, we perform experiments on four datasets to explore the influence of the propagation step $K$ on the performance of NCN. We vary the value of $K$ in $\{2,4,6,8,10\}$ and give the corresponding results in Figure 3. We observe that $K$ affects NCN to a large extent because it determines the range of aggregated information for nodes. For different datasets, the value of $K$ varies for the best performance of NCN because the characteristics of graphs are different. Furthermore, we can also find that setting $K$ less than or equal to 6 could obtain good results. It is because the aggregated information involves too much irrelevant information when $K$ is large that weakens the performance of NCN.

In this subsection, to intuitively demonstrate the effectiveness of our proposed adaptive feature fusion model, we visualize the distribution of the learnable aggregation weights, $a_{0}$ and $a_{1}$ in Equation 8, which measure the importance of the information learned from the node itself and its neighborhoods respectively. We select four representative datasets, including Pubmed, Photo, Squirrel and Chameleon. According to the results of MLP in Table 2, the raw attribute features of nodes are highly correlated to the labels of nodes on Pubmed and Photo. In contrast, the raw attribute features of nodes are not quite irrelevant to the labels of nodes on Squirrel and Chameleon. We randomly select 100 nodes from the test set for each dataset and show the distributions of aggregation weights in Figure 4.

In Figure 4, we can find that the average values of $a_{0}$ and $a_{1}$ are similar on Pubmed and Photo indicating that the raw attribute features and multi-hop neighborhoods are almost equally important for learning the node representations. On the other hand, the values of $a_{1}$ are extremely larger than that of $a_{0}$ on Squirrel and Chameleon, demonstrating that the information of neighborhoods plays a more important role in learning the representations of nodes than the raw attribute features. Therefore, we can conclude that our proposed method can adaptively and effectively learn the aggregation weights according to the characteristics of different graphs.