acceptodds
Under review as a conference paper at ICLR 2027

Deep Ensembles for Graphs with Concise Higher-Order Representations

Abstract

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.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph neural networks, higher-order dependencies, graph ensembles, non-negative matrix factorization, explainable graph learning

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_gUt6OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces CDGE, which combines a regularized low-rank CHON representation with independently trained GNN learners to model path-dependent neighborhoods. Its main contribution is integrating higher-order state compression with graph ensembing, evaluated through link prediction and node classification on Air, Ship and Journal.

Critical strengths
  1. This method addresses a meaningful trade-off between compressing higher-order states and retaining neighorhood diversity for ensemble learning.
  2. State-family residual gating provides an explicit interpolation between shared family information and state-specific messages
  3. substantial reported compression of HON representations, reducing state nodes by approximately 60-83% and edges by 54-82$
  4. Broad baseline comparisions and additional analyses of ensemble size, depth, prediction diversity and compression thresholds.
Critical weaknesses
  1. The effect of compression on low-frequency but predictive contexts is insufficiently evaluated. Rank selection uses count-weighted flow overlap (Eq. (4)), so rare predecessor contexts contribute less to the criterion. Appendix 8 explicitly acknowledges that flow overlap does not guarantee retention of label-relevant differences, but the experiments do not examine this limitation through frequency-stratified reconstruction or downstream results.
  2. The incremental contribution of state-family residual gating is not isolated experimentally. Section 7.15 defines fixed-gate controls (g=0,0.5,1) and a learned gate, but their comparative results are not reported. The DGE–CDGE comparisons change both the graph representation and the message update, leaving it unclear how much improvement comes from CHON compression alone versus the additional gating mechanism
  3. The link-prediction protocol leaves potential leakage unresolved. Positive state pairs are sampled using connecting-edge weights despite those edges being masked, and training-only fitting of CHON is not specified.
Questions for authors
  1. Could you report reconstruction error stratified by predecessor-context frequency, together with a HON-versus-CHON comparison of downstream performance on low-support nodes under matched downstream settings?
  2. Please report the fixed-gate ((g=0,0.5,1)) and learned-gate results on the same CHON, keeping the backbone, learner count, splits, and seeds fixed. How does CHON with (g=1) compare against an otherwise matched HON-based DGE?
  3. Could you provide inference pseudocode for an arbitrary candidate pair without accessing its ground-truth label, and specify the order of data splitting, CHON fitting, and edge masking? In particular, which connecting weights are available after masking, and can held-out transitions influence the counts, priors, ranks, or factors used to construct CHON?
  4. Please reconcile the metric definitions and specify how folds and seeds contribute to the reported mean and standard deviation.

Minor presentation suggestion (NOT a factor in my recommendation): For readability, consider combining the paper and textual appendix into a single PDF. This is entirely optional, as ICLR permits separate supplementary files, and the current arrangement is not a reason for my rating.

1 comment
Reviewer_gUt6OpenReview ↗

Official Comment by Reviewer gUt6

Since the authors did not provide any responses during the rebuttal phase, I stand by my original assessment.

Reviewer_37oKOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
3
Soundness
1
Read review
Paper summary

The authors of this work propose CDGE (Concise Deep Graph Ensemble), a method for learning in sequential data on paths in graphs with higher-order dependencies. The authors specifically discuss the limitation that conventional higher-order networks (HONs) introduce many predecessor-specific state nodes, which comes at the price of high model complexity. The proposed approach combines (i) a regularized low-rank concise higher-order network (CHON) representation that is constructed via convex non-negative matrix factorization with (ii) an ensemble of independently trained GNN learners that sample state-conditioned neighborhoods. The authors evaluate CDGE on three real-world path-based datasets (Air, Ship, and Journal) for link prediction (primary task) and node classification (auxiliary task). Under comparable parameter budgets, CDGE generally outperforms existing GNN baselines. The authors further analyze ensemble size, prediction diversity, and network depth while their results on the small, sparse Journal dataset reveal stability limitations.

Critical strengths
  • The problem is clearly motivated and the use of a model capturing higher-order dependencies in sequence data is a meaningful and sound approach.
  • The paper is generally clearly written and easy to follow.
Critical weaknesses
  • An important first limitation of this work is its poor coverage of prior works that have addressed learning in sequential data on graphs based on various types of models that capture higher-order dependencies. See my comments and Q1 below.

  • A second critical weakness is the poor experimental evaluation, which is below the standard of an ICLR paper in several dimensions, including the choice of benchmark data, baselines or reporting of hyperparameters, see details in Q2 - Q6 below.

  • A third and major weakness of this work is that it constitutes a relatively small contribution over a closely related existing paper published at ICLR 2023, which mainly consists in combining it with another recent work published in 2025, see details in my clarifying question Q6 to the authors below.

Questions for authors
  • Q1: Unfortunately, I consider the coverage of related works to be below the standard required for an ICLR submission. Numerous works have considered the modelling of patterns in sequential data on graphs based on models that capture higher-order dependencies. Some of those models also considered regularization or compression (e.g. via principled Bayesian of frequentist statistical model selection, information-theoretic compression or description length minimization), addressing a similar problem as the authors. Other recent works extended these works to deep learning settings, e.g. in the domain of causality- and ordering-sensitive temporal GNNs, none of which are cited or included as baselines. Yet another class of works capture higher-order dependencies via statistical models in the spirit of higher- or variable-order Markov chains, which notably were not introduced by Xu et al. (2016) as claimed by the authors. I kindly ask the authors to improve their discussion of related works and reconsider the choice of baselines in their experimental evaluation.

  • Q2: Related to the previous comment, I consider the baseline comparisons to be incomplete. The only baselines using higher-order patterns in sequence data are three closely related works HONEM, HO-GNN and different DGE variants which all seem to originate from a specific community of authors. Could the authors clarify why they limited their choice of baselines to this selection of works?

  • Q3: Moreover, I failed to find the references to all of the baseline methods. I think it is standard practice to either include the references in the results table or to add a dedicated paragraph that motivates the choice of baselines and cites the appropriate works. I consider the use of methods as baseline without citing the authors inacceptable. Could the authors explain why they left out citations to works of authors that they build on?

  • Q4: Related to the previous question, it is not clear to me how the inclusion of a large number of static GNN models, which do not capture any temporal patterns in sequential data, contributes to the story of this work. Wouldn't it be more useful to instead include a comparison to standard sequence modelling techniques (e.g. outside the graph setting) or a small transformer model?

  • Q5: I could not follow why the method is evaluated on such a narrow choice of three data sets. Could the authors clarify how the choice of data to be included in this work was made. Why not at least use the full set of data from Krieg et al. 2023? Also, considering the obvious close relation to this previous work it is at least confusing to use the same name for data sets in very different versions. The fact that the data sets Air and Ship - despite using identical names - significantly differ, e.g. in terms of the size, should be clearly stated. Moreover, for some of the data sets and model variants of DGE (e.g. DGE-concat) the performance on AIR reported in the present paper is considerably below that repoerted in the original. Can the authors explain the discrepancy in those numbers?

  • Q6: I believe that some of the claims in the paper are not adequately supported by the experimental evaluation. As an example, an important question is to what extent the CHON compression contributes to the performance. In appendix 7.15 the authors state that for g=1 we “recover the original state message and therefore the ordinary DGE-style update under the same sampling and parameters”. This thus seems to be an obvious control for an ablation, which I however did not find to be reported in the work. Without this control, it is impossible to say whether the observed performance is due to the compression mechanism, the gating, or the different encoder.

  • Q7: Finally, I would like to ask the authors to clarify what they consider to be the key innovations of their work over the following two works:

  • Steven J Krieg et al. Deep Ensembles for Graphs with Higher-Order Dependencies, ICLR 2023

  • R Sahasrabuddhe et al. Concise network models of memory dynamics reveal explainable patterns in path data, Science Advances 2025

Many components described in the present paper, including the core motivation and approach, the core aspects of the theoretical analysis in the appendix, the ensemble variants and the empirical finding about the diversity/accuracy trade-off have already been presented in Krieg et al 2023, while the CHON construction is taken from R Sahasrabuddhe et al 2025. It appears that the key contribution of the present work reduces to replacing the full HON representation with the CHON approach, which is a valid but relatively minor improvement over the state of the art. Could the authors clarify what they consider the key novelty of their work?

Reviewer_AGNGOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

In this paper, the authors propose Concise Deep Graph Ensemble (CDGE), a framework for learning from path data with higher-order dependencies. CDGE first constructs a concise higher-order network (CHON) by regularizing predecessor-conditioned transition matrices and applying convex non-negative matrix factorization. It then trains multiple independent GNN learners on sampled state-conditioned neighborhoods. A state-family residual gate interpolates between family-shared and state-specific messages, and the final prediction is obtained by averaging learner probabilities. The method is evaluated on Air, Ship, and Journal for link prediction and node classification.

Critical strengths
  1. The overall method is technically coherent and well motivated. Combining CHON compression with independently trained GNN learners provides a plausible way to preserve diverse state-conditioned neighborhoods while reducing graph size.
  2. The reported performance is promising. CDGE achieves strong link-prediction results on Air and Ship and competitive node-classification results across the three evaluated datasets.
Critical weaknesses
  1. The experiments do not adequately isolate the contributions of CHON compression, ensembling, and residual gating. A controlled comparison of FON, HON, and CHON with matched single-learner and multi-learner models is missing. The supplement defines fixed-gate controls but does not report their results.
  2. The claimed computational advantage is insufficiently validated. Reductions in graph nodes and edges do not establish end-to-end efficiency when CDGE trains as many as 16 independent learners. The paper lacks numerical comparisons of CHON construction time, total training and inference time and sampling cost against DGE and other higher-order baselines.
Questions for authors
  1. The current version shows limited novelty relative to DGE and existing concise-network methods. The paper needs to state precisely what is new and show that each new part matters on its own.
  2. The empirical scope is too small to support general claims. According to Table 1, the FON graphs have 435 (Air), 621 (Ship) and 22 (Journal) physical nodes, and the largest HON has about 4.6k state nodes and 35k edges. Larger path datasets would be needed, for example web clickstreams, transportation or mobility trajectories.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.