Deep Ensembles for Graphs with Concise Higher-Order Representations

Graph neural networks (GNNs) can be limited by the expressiveness of first-order graph representations when applied to data with higher-order path dependencies. Although conventional higher-order networks (HONs) preserve path context, they introduce many predecessor-specific state nodes, thereby increasing model complexity. To address this issue, we propose CDGE, which combines a regularized low-rank concise higher-order network (CHON) representation with an ensemble of independently trained GNN learners. This design compresses the state space while preserving differences in state-conditioned neighborhoods. We evaluate CDGE on link prediction and node classification tasks using three real-world datasets: Air, Ship, and Journal. Under comparable parameter budgets, CDGE generally outperforms existing GNN baselines on both tasks while substantially reducing the numbers of nodes and edges in the HON representation. Further analyses show that predictive diversity and accuracy among independent learners, together with a moderate ensemble size, are key to CDGE's effectiveness. These findings provide useful guidance for the design of GNN ensembles for data with higher-order path dependencies. Code is available at https://anonymous.4open.science/r/sr-cdge-reproducible-code-071F.