SStaGCN: Simplified stacking based graph convolutional networks

Given an undirected graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ with nodes $v_{i}\in\mathcal{V}$ and edges $(v_{i},v_{j})\in\mathcal{E}$, let $A\in\mathbb{R}^{N\times N}$ denote the adjacency matrix, where $N$ is the total number of nodes. The corresponding degree matrix is denoted as $\mathbf{D}$, with $\mathbf{D}_{ii}=\sum_{j}A_{ij}$. For an undirected graph, it is evident that $A_{ij}=A_{ji}$.

In conventional GCN models for semi-supervised node classification, the node embeddings with two convolutional layers are computed as follows:

Here, $Z\in\mathbb{R}^{N\times K}$ represents the final embedding matrix (output logits) of the nodes prior to the softmax operation, where $K$ is the number of classes. The feature matrix $X\in\mathbb{R}^{N\times d}$ contains node features, with $d$ as the input dimension. We define $\hat{A}=\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}$, where $\tilde{A}=A+I$ (with $I$ as the identity matrix) and $\tilde{D}$ is the degree matrix of $\tilde{A}$.

Furthermore, $W^{(0)}\in\mathbb{R}^{d\times H}$ is the weight matrix for the input-to-hidden layer with $H$ hidden features, and $W^{(1)}\in\mathbb{R}^{H\times K}$ is the weight matrix for the hidden-to-output layer. Notably, the standard GCN model in Eq. (1) applies $\hat{A}$ to $X$ repeatedly, which leads to all node features becoming indistinguishable due to excessive smoothing.

Stacking is a well-known and widely used ensemble machine learning algorithm that integrates models in a hierarchical framework [43]. It employs a meta-learning algorithm to optimally combine predictions from two or more base machine learning models. A traditional stacking model consists of multiple base models and a meta-model that integrates the base models’ predictions. Each base model is trained on the dataset and produces individual predictions. The meta-model then learns to best combine these predictions, typically using a straightforward approach to provide a cohesive interpretation of the base models’ outputs. As a result, linear models, such as linear regression for regression tasks and logistic regression for classification tasks, are often chosen as meta-models.

As noted above, GCNs may blend node features from different clusters, which can lead to suboptimal predictions. Therefore, it is essential to aggregate node information effectively to improve predictive accuracy. Inspired by the traditional stacking approach and the work in [17, 39], we aim to reduce computational cost by using only the base models from the stacking method and then aggregating their outputs to derive the nodes’ attributes. Specifically, our proposed method operates as follows: in the first layer, we obtain $X^{\prime}$ by passing $X\in\mathbb{R}^{N\times d}$ (the feature matrix) through $k$ base classifiers.

Next, we obtain the preliminary classification results $X^{\prime}_{i}$ by passing $X$ through each base classifier $h_{i}(X)$ for $i=1,\cdots,k$. Then, we apply an aggregation method to produce the final output results, i.e.,

where $g(\cdot)$ denotes the aggregation method, which is designed to combine attribute values into a single representative value. Common aggregation methods include mean, attention, or voting approaches.

Mean: mean operator takes the element-wise mean of the components $X^{\prime}_{1},\cdots,X^{\prime}_{k}$.

Attention [40]: The attention mechanism has been widely applied in various fields of deep learning, including image processing [29], speech recognition [1], and natural language processing [47]. This concept is inspired by the way humans focus attention selectively. Let the query vector $V$ represent the output of the base classifiers, and let the query vector $Y$ denote the data label. We then compute the attention coefficients between $Y$ and $V$ as follows:

where $\cos$ denotes cosine similarity. Finally, the input ${\tilde{X}}$ of the graph convolutional layer is aggregated by considering the following sum with attention scores $a_{i}$, $i=1,\cdots,k$.

Voting [33]: The voting method is the most straightforward approach in ensemble learning, aiming to select one or more “winning” predictions. In this work, our goal is to select the most common prediction among the outputs of the base classifiers, using a majority voting approach. In cases where categories appear with equal frequency, a category will be chosen at random.

This brings us to a novel GCN model, SStaGCN, specifically designed to handle diverse types of graph-structured data by effectively integrating stacking, aggregation, and the vanilla GCN model [19]. In SStaGCN, the first layer leverages base models from the stacking approach, while the second layer applies an aggregation method—such as mean, attention, or voting—to enhance the feature extraction capabilities of standard GCN models. The aggregated data is then used as input to the convolutional layer, which produces the final predictions. The workflow of the proposed model is presented in Algorithm 1 and Fig. 1. This prompts the question: is there a theoretical guarantee for the proposed approach?

In this section, we provide a theoretical generalization analysis of the proposed approach. In the following analysis, we assume that both the adjacency matrix $A$ and the feature matrix $X$ are fixed.

In learning theory, the risk of a function $f$ over the unknown population distribution $\mathbb{P}$ is measured by

where $L$ is the loss function defined as a map: $L:\mathcal{X}\times\mathcal{Y}\rightarrow\mathbb{R}^{+}$, Given a training data and adjacency matrix $A$, the objective is to estimate parameters $(W^{(0)},W^{(1)})$ from model (1) based on empirical data. Concretely, we attempt to minimize the empirical risk functional over some function class $\mathcal{F}$,

where $\{(\tilde{{\bf x}}_{j},y_{j})^{m}_{j=1}\}$ is the labeled sample achieved from the original training data $\{({\bf x}_{j},y_{j})^{m}_{j=1}\}$ via stacking and aggregation. Typically, the clustering algorithms will only produce discernible node features. Hence, if $\|{\bf x}_{i}\|\leq R,i=1,\cdots,N$, the stacking and aggregation mechanisms will not make $\tilde{\bf x}_{i}$, $i=1,\cdots,N$ violate the constraints, i.e., $\|\tilde{\bf x}_{i}\|\leq R,i=1,\cdots,N$. Now we are in position to present the theoretical generalization bound.

where $\|\cdot\|_{F}$ is the Frobenius norm, $M_{s}=\max_{i\in[N]}|\hat{A}_{iv}|$ with $v\in N(i)$.

To evaluate the performance of the proposed SStaGCN model across various types of graph-structured data, we utilize six real-world datasets for a semi-supervised node classification task. This includes three commonly used citation networks—Cora, CiteSeer, and Pubmed [35]—and three heterogeneous tabular datasets: House$\_$class, VK$\_$class, and DBLP [17]. These heterogeneous tabular datasets differ from those in [42], containing graph data with diverse edge and node types.

In the citation networks, nodes represent documents, and undirected edges denote citation relationships between documents. Node features correspond to representative words in the documents, while the label rate indicates the percentage of node labels used for training. The Cora dataset comprises $2708$ nodes, $5429$ edges, $7$ classes, and $1433$ node features; CiteSeer has $3327$ nodes, $4732$ edges, $6$ classes, and $3703$ node features; and Pubmed includes $19717$ nodes, $4438$ edges, and $3$ classes. We use $140$, $120$, and $60$ nodes for training in Cora, CiteSeer, and Pubmed, respectively, and allocate $1000$ nodes for testing and $500$ nodes for cross-validation. This data split matches that used in GCN, Graph Attention Network (GAT, [41]), and GWNN [45].

According to [17], House$\_$class and VK$\_$class datasets are derived from House and VK datasets, where target labels are converted into discrete classes due to limited availability of publicly accessible heterogeneous graph-structured data. In these heterogeneous tabular datasets, features are independently defined and vary in type, scale, and meaning. The VK dataset represents a popular social network, with node features that are both numerical (e.g., last active time) and categorical (e.g., country and university affiliation). Similar to [17], we categorize age into bins: $<20$, $20–25$, $25–30$, $\cdots$, $45–50$, $>50$. For the House dataset, we categorize target values within the range $[1.0,1.5,2.0,2.5]$, resulting in five classes for House$\_$class and seven for VK$\_$class. In the DBLP dataset, we construct a single graph by focusing on the APA (author-paper-author) meta-path. Each dataset is divided into training, validation, and testing splits in a $0.6/0.2/0.2$ ratio across five random seeds.

Details about the citation networks and heterogeneous tabular datasets are presented in Table 1 and Table 2, respectively.

We compare SStaGCN with four classical graph convolutional networks—ChebyNet, GCN [19], GAT, and APPNP [21]—as well as two ensemble-based GCN models: AdaGCN and BGNN.

As shown in Fig. 1, the proposed SStaGCN model consists of four layers, with the first and second layers referred to as the stacking and aggregation layers, respectively. The stacking layer utilizes base models from the stacking method, incorporating a combination of seven classical classifiers: KNN, Random Forest, Naive Bayes, Decision Tree, SVC [30], GBDT [12], and Adaboost [11]. These classifiers are widely used in classical machine learning for their strengths in handling different task types.

In the aggregation layer, we employ three aggregation methods: mean, attention, and voting. For the mean approach, we calculate the average output from the stacking layer, rounding it as needed. In the attention mechanism, we treat the label data as vector $Y$, use the stacking layer’s predicted output as the query vector $V$, and compute attention coefficients accordingly. For the voting method, we apply hard voting from ensemble learning [34].

The output of the aggregation layer serves as the input to the first layer of a two-layer GCN. In our configuration, the GCN has 16 hidden units and uses the Adam optimizer [18] by default, with cross-entropy as the loss function. The learning rate is set to $\gamma=0.01$, the number of iterations ${\rm itr}=500$, weight decay at $5e-4$, and a dropout rate of $0$.

The results of the comparative evaluation for node classification are summarized in Tables 3-11. In these tables, SStaGCN (Mean) refers to the use of the mean aggregation mechanism in the second layer of SStaGCN, while SStaGCN (Attention) and SStaGCN (Voting) correspond to the attention and voting mechanisms, respectively. We report the accuracy, macro F1-score, and training time on the test set for the proposed SStaGCN model and other methods. The experimental results demonstrate a significant improvement of the SStaGCN model over the baselines. Specifically, for the three public citation networks, SStaGCN (Voting) achieves an improvement in accuracy (and F1-score) of approximately $8\%$ ($8\%$), $12\%$ ($17\%$), and $13\%$ ($12\%$) for the Cora, CiteSeer, and Pubmed datasets, respectively. For the heterogeneous tabular datasets, SStaGCN (Voting) shows an improvement in accuracy (and F1-score) of about $9\%$ ($9\%$), $21\%$ ($21\%$), and $6\%$ ($5\%$) for the House$\_$class, VK$\_$class, and DBLP datasets, respectively.

AdaGCN performs poorly on the heterogeneous tabular datasets, possibly because AdaGCN is designed for deeper GCN architectures, which may mix node features from different clusters as the GCN layers deepen. SStaGCN, by contrast, enhances the performance of GCN, providing better results across distinct types of graph-structured data. Additionally, the paired t-test results in Table 7 indicate that the proposed SStaGCN model significantly outperforms the simplified stacking and other GCN models.

This impressive improvement can be explained as follows:

The stacking and aggregation steps in SStaGCN provide a dimensionality reduction effect, making the graph data more discernible. For example, in the Cora dataset, the feature size reduces from $2708\times 1433$ to $2708\times 7$ after stacking and aggregation. This results in a relatively smaller $d_{1}$, as discussed in Remark 1, significantly enhancing both the predictive power and computational efficiency of the subsequent graph convolution model.

In the aggregation step of the SStaGCN model, the mean and attention mechanisms somewhat disrupt the pre-classification results, making them less suitable for feature extraction, whereas the voting mechanism preserves these results. Consequently, experimental results demonstrate that SStaGCN (Voting) is more effective across the six datasets.

Simplified stacking can effectively extract useful attributes but overlooks graph structure information, while GCN models are limited in feature extraction. Therefore, the SStaGCN model combines the strengths of simplified stacking and GCN, achieving both higher classification accuracy and reduced computational cost.

Tables 8 and 9 present a comparison of training times between SStaGCN and other methods. BGNN achieves the fastest runtime on the three citation networks, followed closely by our SStaGCN method. However, SStaGCN runs faster than other methods on the heterogeneous tabular datasets, with the exception of the DBLP dataset. We attribute this to the extra computation time required for the stacking and aggregation steps, which ultimately enhance efficiency when feeding the feature outputs into the GCN model.

To demonstrate the effect of stacking and aggregation steps in the proposed model, we provide a t-SNE visualization [27] in Figs. 2(a) and 3(a). These figures show that the combination of stacking and aggregation effectively extracts features, enhancing the discriminative power of the graph data.

Table 10 suggests that using all seven classifiers is unnecessary. For example, on the Cora dataset, the combination of KNN, Random Forest, and Naive Bayes achieves the highest accuracy with minimal computational cost (only 3 seconds). This indicates that each of the seven classifiers has unique strengths suited to different tasks. However, selecting the optimal combination of base models remains an open area for theoretical analysis.

To further illustrate the impact of simplified stacking on the over-smoothing problem, we conduct an additional experiment on this topic. In Fig. 4(a), we observe that a conventional GCN tends to blend node features from different clusters as the number of convolutional layers increases. However, as shown in Fig. 5(a) and Table 11³³3The number of layers excludes those included in the stacking and aggregation parts of SStaGCN, which consist of only two layers., the proposed SStaGCN effectively mitigates the over-smoothing phenomenon and enhances accuracy.

Overall, these experiments demonstrate the superiority of SStaGCN model over competitors.

To further illustrate the performance of SStaGCN, we plot the final classification features of GCN, AdaGCN, BGNN, and our SStaGCN. Fig. 6(a) (for CiteSeer) and Fig. 7(a) (for DBLP) display the final classification features of each method on these datasets. As shown in these figures, the proposed SStaGCN misclassifies relatively fewer points, while GCN, AdaGCN, and BGNN result in more misclassified classes.