HGEN: Heterogeneous Graph Ensemble Networks

1 Introduction

Ensemble learning that combines multiple base models to enhance predictive performance has achieved remarkable success across diverse domains, from weather forecasting [Molteni et al., 1996] and online trading [Sun et al., 2023] to image classification [Yang et al., 2023a] and recent prompt-based ensembling in Large Language Models [Zhang et al., 2024]. While individual models often struggle with generalization and overfitting, ensemble learning harnesses the diversity of base models to improve robustness, reduce variance, and achieve superior accuracy.

Despite its wide adoption, ensemble learning has been mostly studied in the context of i.i.d. data, leaving its application to data with complex interdependencies such as graphs relatively underexplored. Early studies such as graph representation ensembling [Goyal et al., 2020] fused node embeddings from multiple graph learning models through concatenation. Subsequent methods such as stacking-based frameworks [Chen et al., 2022] proposed multi-level classifiers to aggregate representations for tasks like link prediction. More recent efforts such as Graph Ensemble Neural Network (GEN) [Duan et al., 2024] integrated ensemble learning directly within Graph Neural Networks (GNNs), performing ensemble operations throughout the training process rather than solely at the prediction stage. To further improve robustness and mitigate overfitting and adversarial attacks, recent methods such as Graph Ensemble Learning (GEL) [Lin et al., 2022] introduced serialized knowledge passing and multilayer DropNode strategies to promote diversity, while GNN-Ensemble [Wei et al., 2023] employed substructurebased training to defend against adversarial perturbations.

While these methods have advanced ensemble learning for homogeneous graphs, they falter in dealing with heterogeneous graphs, which are commonly observed in real-world applications, such as social networks [Fu et al., 2020], citation networks [Tang et al., 2008], urban networks [Houssou et al., 2019], and biomedical networks [Jin et al., 2024]. Indeed, ensemble learning on heterogeneous graphs has three unique challenges as follows. 1) Graph heterogeneity, where diverse node and edge types necessitate specialized techniques such as meta-path [Zhang et al., 2019] or attention-based [Xiao et al., 2019] models to extract meaningful relationships and patterns, 2) Base learner accuracy, where the non-uniform structure of heterogeneous graphs requires accurate base learners to ensure reliable ensemble performance, and 3) Base learner diversity, where ensuring diverse learners is crucial for robust and generalized predictions, given the varied nature of heterogeneous graphs.

To address these challenges, we propose HGEN, a novel ensemble learning framework with solid theoretical foundation for heterogeneous graphs. HGEN is tailored to accommodate various mainstream graph learners, such as Graph Convolutional Networks (GCNs), Graph Attention Networks (GATs), and GraphSAGE, offering a flexible and efficient solution for complex networked data. Specifically, HGEN simultaneously enhances learner accuracy and diversity by devising a regularized allele GNN framework, which employs feature and edge dropping to generate diverse GNNs from heterogeneous graphs. This enhances generalization by encouraging different perspectives of the graph for promoting diversity across base learners. To further improve accuracy, a residual-attention mechanism is incorporated to enable adaptive ensemble weighting, allowing base learners to aggregate allele GNNs derived from perturbed graph structures while favoring more informative graphs. Unlike existing serialized or boosting-based ensemble methods, which can be computationally expensive hence impractical for large graphs, HGEN adopts a bagging strategy, enabling a balance between computational efficiency and scalability through parallelization.

Specific contributions of this paper includes the following:

1. HGEN is the first framework to enable ensemble learning for heterogeneous graphs, tackling the unique challenges posed by their complexity and diversity.
2. A novel attention-based aggregation that dynamically adjusts weights based on the contributions of base graph learners is proposed. A residual attention mechanism is to refine ensemble weighting further, enhancing adaptability and improving overall predictive accuracy.
3. Our theoretical analysis substantiates the convergence of HGEN, and that its magnitude of correlation regularization overweighs na¨ıve voting.
4. Empirical study on five real-world heterogeneous networks validates the effectiveness of HGEN over the recent arts, where the datasets establish a new benchmark for heterogeneous graph ensemble learning.

2 ProblemDefinition

Let G = (V, E, X, Y ) denote a heterogeneous graph, where V is the set of nodes, E is the set of edges, X is the feature matrix for the nodes of a certain targeted type, and Y is the one hot encoding label matrix for those target nodes. Denote T v as the set of node types and T e as the set of edge types, where ti ∈ T v is the node type i and ei,j ∈ T e is the edge type that connects the node type from ti to tj.

Define ϕ : V ↦→ T v that maps the node from V to its node type, and φ : E ↦→ T e that maps the edges from E to its edge type. A meta-path P is a relational sequence (ei,jej,k . . . ek,jej,i) that is symmetric. Given a specific metapath Pi, we can construct a homogeneous graph equipped with an adjacency matrix Ai ∈ 1n×n where Ai[j, k] = 1 ⇐⇒ ∃ p = (vj, . . . , vk) such that edges in the path p match the meta-path Pi, formally presented as follows.

Given graph G and a target node type tι ∈ T v , with Vtι ⊂ V being the target node set containing n target nodes, a simple graph learner such as GNN can only learn from a homogeneous graph. Our goal is to enable ensemble learning of multiple GNNs to predict the label Y for the target node set Vtι so to maximize the classification accuracy and AUC values.

3 Proposed Framework

The proposed HGEN ensemble learning framework, in Figure 1, uses meta-paths to extract multiple disparate homogeneous graphs from the heterogeneous graph, such that base graph learners like GCN, GAT, or GraphSAGE can be trained from the extracted graphs to form an ensemble. Two major components of HGEN to enhance base learner accuracy and diversity are presented in Sections 3.1 and 3.3, respectively, followed by the analysis. Main steps of HGEN are outlined in Algorithm 1 in Appendix.

3.1 HGEN Base Learner Accuracy Enhancement

Allele Graph Neural Network Learning

For each meta-path Pi, we extract a homogeneous graph Gi = (Ai,Xi) consisting of target nodes and its adjacency matrix denoted by Ai and nodal features Xi. Although GNNs under certain conditions such as Lipschitz graph filters are stable [Gama et al., 2020], most GNNs intend have unstable learning outcomes, especially when trained with limited samples with random initialization. This motivates us to devise allele graph neural networks for ensemble learning, where alleles refer to variant GNN networks learned from the same source. Therefore, we propose to augment each meta-path graph by using node feature dropout, as follows.

where b is the dropout rate, σ(·) is the non-linear activation function, Xi is the original node features, W 0 i is the projection learnable parameters, and H(0) i is the embedding output prepared for graph learning. Instead of using more sophisticated graph augmentation approaches, our ablation study in Sec. 4 will soon demonstrate that feature dropout outperforms other alternatives. This is also consistent with previous observations where feature dropout often outperforms node or edge dropout [Shu et al., 2022].

After applying base graph learner GNN to augmented meta-path graph ˜Gi = (Ai, ˜Xi), we can obtain one base learner. For each meta-path Pi, we apply different initializations and dropout to obtain k base GNN models. With m meta-paths, a total of (k ∗ m) base GNNs are created. Each single base GNN consists of a single linear projection layer projecting raw feature input X along and multiple graph filtering layers aggregating embeddings with corresponding adjacency matrix Ai. The projection layer is a simple linear layer projecting raw features with a random feature dropout followed by a nonlinear-activation. For the message passing scheme, we used three different backbones: graph convolution layer, graph attention layer, and GraphSAGE layer to show the effects of base model variants. In general, any standard message passing scheme can fit into the framework.

In the following, we outline the j th GNN from the ith meta-path Pi using GCN, and the layer-wise aggregation of the node information is as follows:

with Di denoting the degree matrix of (Ai + I), W (l) i,j as the learnable parameters for the convolution layer l. With L graph convolution layers in total l ∈ {1, · · · , L}, the GCN outputs of the final node embeddings for the j th GNN from the ith meta-path Pi is represented as H(L) i,j .

3.2 Intra Fusion for eachMeta-Path Residual-Attention for Allele GNN Fusion

The allele GNNs each learns from an augmented meta-path graph, conveying unique information of the underlying metapath semantics and the network heterogeneity. As the first key step of the ensemble learning process, a fusion mechanism is introduced to consolidate embedding features from allele GNNs to adaptively adjust weight of respective GNNs.

Instead of directly learning GNN weights, we introduce a residual-attention mechanism which borrows residual network's [He et al., 2015] unique strength of learning identity mapping that is hard to directly learn from highly nonlinear functions. The residual mechanism provides a good precondition or initial points that guarantee easy learning on recovering shallow layer results. Meanwhile, it is known that the attention mechanism is highly non-linear and could be difficult to learn a uniform weight distribution. Inspired by the residual mechanism and its success in image recognition [Wang et al., 2017], we propose a residual-attention approach for the first ensemble stage that ensures an easy learning of allele GNN aggregation, which is shown to be a simple mechanism serving as a good precondition analogy to identity mapping.

Specifically, for each meta-path Pi, our model leverages multiple single GNN to learn the embeddings. To aggregate the final embeddings of multiple GNNs, a residual-attention based fusion mechanism is designed as follows:

where Θ ∈ Rn×k is the learned residual attention with meta-path Pi, where n denotes number of target nodes and k denotes the number of allele GNNs for each meta-path. ¯Θ is the row average of learned Θ. ˆΘ is the broadcasting difference between Θ and ¯Θ, which is zero-centered. Θ↑ = max(ˆΘ) and Θ↓ = min(ˆΘ) are the corresponding maximal and minimal attention scores over row. ˜Θ is the final minimax version of residual attention. The min-max residual attention adaptively adjusts the weights/influence of each base learner. Strong learners making more correct predictions are promoted with higher weights, while weaker learners have lower weights, allowing the model to mitigate the impact of errors without explicit error detection.

Residual-Attention Fusion. In order to fuse embeddings from allele GNNs which are derived from the same metapath graph, we employ a residual-attention mechanisms, as defined in Eq. (6), where ˜Θ[:, i]+ 1k is the node-wise attention and + is the broadcasting plus over nodes as follows.

As the results of the residual-attention, H ·∪ i is used to denote the aggregated node embeddings for meta-path Pi after residual-attention fusion. It is worth noting that the residualattention in Eq. (6) does not involve any learnable parameters. The attention in Eq. (5) learns respective parameters to regulate the residual-attention fusion.

3.3 HGEN Base Learner Diversity Enhancement

After obtaining the final embedding H ·∪ i for each meta-path Pi, we project the embedding to the output class dimension with a linear layer decoder. Finally, we use summation to bag the prediction for each meta-path to obtain final prediction:

where a mean pooling operator MP(·) is used to obtain graph embeddings ˜Hi ∈ Rf over H ·∪ i for each meta-path Pi. Denote the stacked version of all meta-paths ˜Hi as ˜H ∈ Rm×f . A correlation matrix is computed quantifying the inter correlation among meta-paths:

where S ∈ Rm×m is the correlation matrix for evaluating inter meta-path relation. We applied L1 norm on S as regularization loss to ensure more independent embeddings learned among all meta-paths. The final objective function of the HGEN is then defined by Eq. (9).

We evaluated the impact of correlation regularization term by varying its weight coefficient λ as indicated in Eq. (9). A larger λ enforces greater sparsity in the correlation matrix, encouraging base learners trained from different metapath graphs to be more independent. To assess this effect, we examined the ensemble performance across different metapaths for λ ∈ {0, 0.1, 0.5}, as shown in Fig. 4(c) . The violin plots visualize the distribution of ensemble performance. As λ increases, the spread (i.e., width) of the distributions becomes larger, suggesting that models trained from individual meta-paths produce increasingly diverse predictions. This validates that the correlation-regularization term positively contributes to diversity between ensemble models.

3.4 Theoretical Analysis

Complexity. Algorithm 1 in Appendix lists the major steps of HGEN which takes a heterogeneous graph as input, learns allele GNNs from meta-path graphs, and outputs predictions for target nodes. Given m meta-paths and k allele GNNs for each meta-path, with an average of e number of edges for each meta-path. Denote training a single GNN time complexity is T with T at least linearly scaled to O(nf + e). The asymptotic complexity of the HGEN is then at least O(m ∗ (kT ) + m ∗ (k ∗ nf). With m ∗ k ∗ nf roughly the time for the residual attention computation and m ∗ (kT) for each individual GNN training. Since nf ≤ T , we should approximately have c ∗ m ∗ (kT) time complexity and asymptotically O(m ∗ (kT )) time complexity. With the assumption that m, k ≪ T, the total complexity of the ensemble model is linearly scalable.

We report the wallclock runtime performance by assessing the average training time per epoch across ensemble sizes in Fig. 4(b) . We observe a linear increase of runtime w.r.t. ensemble size in all five datasets. Besides, on larger graphs, the increasing trend of average training time per epoch w.r.t. increasing number of nodes and edges is also linear. The two results suggest scalability of HGEN in both ensemble size and graph size, attesting its practicability for large-scale graph learning. We also conduct experiments by using a large Freebase dataset containing 40,000 nodes and four different magnitude datasets, with the results illustrated in Fig. 4(d) . We observe that the attention in HGEN could introduce slight overhead, but it remains constant and does not scale up with the graph size. If we remove this attention mechanism, the runtime of HGEN will be on a par with the naive ensemble baseline. The extra runtime is mainly required from computing the attention, it will remain manageable for large graphs.

Convergence & Superiority Than Naive Voting. In the following, we derive a Theorem and two remarks, which assert the convergence of HGEN, and its superiority compared to simple voting based ensemble. Detailed derivations are reported in Supplement D.

Theorem 1. Denoted by L′ = - ∑i yi log(yi) the crossentropy loss accumulated by by minimizing the objective Eq. (9) over t training iterations. The cumulative loss ℓ at the t-th iteration satisfies:

where Wt and W mlp t represent the learnable parameters of base graph learner and the weights of MLP at the t-th iteration, respectively; W mlp ∗ is the optimal MLP weights and η′ the step size. L is the Lipschitz constant. Denoted by h ·∪ij the (i, j)-th entry of the fused node embedding matrix H ·∪ j , whose magnitude is bounded by:

Remark 1. Consider the immediate loss lt(Wt) that holds lt(Wt) ≤ L′ (Wt, W mlp ∗ ) + ∥W mlp t -W mlp ∗ ∥ 2η′ t + m·f·max |h ·∪ij |2 t . We observe limt→∞(L′ (Wt,W mlp ∗ ) - lt(Wt)) = 0, where lt(Wt) is approaching its optimal status as t goes larger. This suggests that the learning process of using MLP to ensemble the resultant node embeddings of base graph learners is stabilizing and improving over time, indicating convergence.

Remark 2. The θ-weighted ensemble strategy in HGEN enjoys a magnified term ∥S∥1 hence strengthen the regularization effect through the aggregated embedding , because range(h ·∪ij ) ≥ range(˜h ·∪ij ), where ˜h ·∪ij ∈ (µ - 4σ - √tηL, µ + 4σ+ √tηL) is the (i, j)-th entry of the fused node embedding matrix generated from na¨ıve voting, and ˜Θi,j ∈ [0, 1], ∀i, j. This means that HGEN provides a broader range of possible embedding values compared to the na¨ıve voting, thereby resulting in more flexible and informative embeddings, which helps improve overall performance and generalization.

4 Experiment

4.1 Benchmark Datasets

Five heterogeneous graphs from real applications are used as benchmark datasets. Their statistics and detailed descriptions are deferred to Supplement B of Appendix due to page limits.

4.2 Baselines

We compare our HGEN with some state-of-art baselines including heterogeneous graph embedding models.

• HAN [Xiao et al., 2019] leverages node- and semanticlevel attention mechanisms to learn heterogeneous node embeddings from different meta-paths.
• Ensemble-GNN is a variant of the state-of-the-art ensemble learning method for homogeneous graphs [Wei et al., 2023], which combines predictions from multiple GNNs through voting. To make the method [Wei et al., 2023] working for hoterogeneous graphs, we use meta-paths to generate homogenerous graphs, and apply the method [Wei et al., 2023] for ensemble learning (predictions are generated using GCN, GraphSAGE, and GAT). After training, the predictions across all GNNs and meta-paths are aggregated through voting to determine the final prediction.
• Transformer-GNN uses a transformer architecture to combine embeddings from different GNNs (GCN, GraphSAGE, and GAT) for each meta-path. Once predictions are generated for a meta-path, they are stacked and integrated to produce the final prediction, ensuring an effective fusion of heterogeneous graph information.
• SeHGNN [Yang et al., 2023b] is a heterogeneous graph representation learning that precomputes neighbor aggregation using a lightweight mean aggregator and avoids repeated computations during training. SeHGNN extends the receptive field with long meta-paths and fuses features through a transformer-based module.
• NaiveWeighting-GNN is a variant of the proposed HGEN. It uses the same architecture and loss function (and regularizer) as HGEN to guide learning but replaces the residual-attention fusion of HGEN using a simple mean average to aggregate all allele GNNs. Its comparision to HGEN can demonstrate the advantage of the residual-attention fusion, compared to simple voting.

4.3 Implementation Details

We perform a grid search with selected range of hyperparameters including hidden dimension, layer size, dropping rate, number of individual GNN, and control rate for regularizer. We choose Adam [Kingma and Ba, 2014] as our optimizer. We fix the learning rate, weight decay, the number of epochs and apply early stopping mechanism. For each method, we report the average accuracy and roc-auc score across five random seeds. All experiments are run on desktop workstations equipped with Nvidia GeForce RTX 2080 Ti.

4.4 Results and Analysis

Variants and Baseline Comparison. Table 1 reports the results of the experiment on five datasets with different baselines, our proposed method, and variants over three individual message passing backbones, including graph convolution network (GCN), graph attention network (GAT), and GraphSAGE. Within the same message passing scheme, it can be observed that our proposed HGEN consistently performs better over other baselines with 95% confidence level on IMDB, Business, ACM, and Urban datasets, and scores on top along with the GCN-Ensemble method on DBLP dataset, proving the superiority of our framework.

Compared to all baselines (excluding NaiveWeighting GNN, which is HGEN's variant), HGEN performs consistently better over all datasets with 95% confidence level. For GCN backbones, HGEN beats all other variants over IMDB, Business, ACM, and Urban dataset and performs on top along with weighted GCN over DBLP dataset. For GAT backbones, our methods is on par with TransformerGAT and weighted GAT over Urban and ACM datasets and outperforms others in the rest of datasets. This shows the advantage and necessity of our individual components.

Note, HGEN is statistically significantly better than GNNEnsemble on 25 out of 30 occasions (across all five datasets). Although both of them are graph ensemble learning methods, GNN-ensemble's base learners are not regulated by the global objective function and there is no constraint to enhance base learner diversities. This results in suboptimal base learners with low accuracies and diversity.

Comparing HGEN and its variant NaiveWeightingGNN , the results show that HGEN is statistically significantly better than NaiveWeighting-GNN on 17 out of 30 occasions (across all five datasets), asserting the advantage of the proposed residual-attention for allele GNN fusions, compared to naive voting. This is also consistent with our theoretical analysis in Section 3.3 which asserts that the Θ-weighted ensemble strategy strengthens the regularization effects due to its larger range of h ·∪ij , compared to naive voting.

Ablation Study on Allele GNNs &Meta-paths. In order to validate the impact of allele GNNs on HGEN's ensemble learning results, we report mean and variance for allele GNNs leaner and HGEN in Figures 5(a) and 5(b), where the blue violin plots represents allele GNN models' accuracies (mean and variance), and the the orange violin plots show the corresponding final accuracy of HGEN. For each dataset, the results are reported by increasing the number of meta-paths. Figures 5(a) and 5(b) show that the variance of the blue plots is significantly larger than that of the orange plots. This suggests that individual allele GNN models exhibits larger variability and diversity in their predictions, a preferable setting for ensemble learning. As a result, the final accuracy, after ensemble, shows a more stable and consistent result.

As we add more meta-paths, more GNNs are obtained. Each GNN model learns different aspects of the data, improving the overall robustness of the model. However, while individual GNNs show more diversity, their performance can still be limited by the inherent biases or weaknesses of each model. Meanwhile, when comparing individual GNN accuracy and HGEN final accuracy, we observe that the ensemble results have a much higher accuracy, showing the success of our residual attention ensemble approach. Using attention mechanisms, HGEN learns dynamic weights to each metapath, focusing on capturing and fusing individual GNN's advantage in the learning process. By enforcing diversity across models from different meta-paths through the ∥S∥1, HGEN strengthens their embedding fusion range(h ·∪ij ) as we have theoretically analyzed in Section 3.3, and therefore improves the final prediction results.

Ablation Study on Augmentations & Regularizer.

Table 2 reports the results of HGEN using different augmentations (feature/edge dropout), combined with the regularizer across various datasets. Feature dropping diversifies individual GNNs by enabling a broader range of learning process, which improves the models' capacity for generalization. The regularizer ensures predictive consistency by enforcing constraints which further enhances model performance. These combined effects make the framework particularly suitable for handling heterogeneous graphs. We observed that the Urban dataset benefits significantly from the regularizer and feature dropping, showcasing their utility in domains characterized by high heterogeneity and noise.

4.5 Case Study Analysis

To demonstrate why and how HGEN outperforms baselines, we carry out case studies on each benchmark dataset to compare samples on which HGEN makes correct classification whereas rivals (i.e. HAN [Xiao et al., 2019]) make mistakes, and report the case study on DBLP in Figure 6 (case studies of rest datasets are reported in Supplement C). For each dataset, points represent samples which are color-coded based on their ground-truth class. Circled points are correctly classified by HGEN but misclassified by HAN.

Taking DBLP dataset in Figure 6 as an example, it can be observed that the circled points are mostly around the edges of the clusters, meaning boundary or difficult cases for separation. The proposed HGEN can correctly identify boundary points for each class that the HAN method incorrectly classify. Similar phenomena can be observed from other four datasets. In fact, this is one of the frequently observed advantages that are naturally brought about by ensemble learning [Ross et al., 2020; Polikar, 2006].

5 Conclusion

This paper proposed HGEN, a novel ensemble learning framework for heterogeneous graphs. Unlike existing ensemble methods that focus mainly on homogeneous graphs, HGEN addresses the unique challenges posed by graph heterogeneity, including various node and edge types, and the need for accurate and diverse base learners. By leveraging a regularized allele GNN framework, HGEN enhances generalization through feature dropping techniques, promoting diversity among base learners. The residual-attention mechanism further enables adaptive ensemble weighting, ensuring improved predictive performance through dynamic aggregation of allele GNNs.

Ethical Statement

This is basic ML research and entails no ethical issues.

Acknowledgments

This work has been supported in part by the National Science Foundation (NSF) under Grant Nos IIS-2236578, IIS-2236579, IIS-2302786, IIS-2441449, IOS-2430224, and IOS-2446522, the Science Center for Marine Fisheries (SCeMFiS), and the Commonwealth Cyber Initiative (CCI).