Deep Ensembles for Graphs with Higher-order Dependencies
Authors: Steven Krieg
William Burgis
Patrick Soga
Nitesh Chawla
Venue: ICLR 2023 poster (2023)
Keywords: graph neural networks
higher order networks
deep ensembles
representation learning
semisupervised learning

Abstract: Graph neural networks (GNNs) continue to achieve state-of-the-art performance on many graph learning tasks, but rely on the assumption that a given graph is a sufficient approximation of the true neighborhood structure. In the presence of higher-order sequential dependencies, we show that the tendency of traditional graph representations to underfit each node's neighborhood causes existing GNNs to generalize poorly. To address this, we propose a novel Deep Graph Ensemble (DGE), which captures neighborhood variance by training an ensemble of GNNs on different neighborhood subspaces of the same node within a higher-order network structure. We show that DGE consistently outperforms existing GNNs on semisupervised and supervised tasks on six real-world data sets with known higher-order dependencies, even under a similar parameter budget. We demonstrate that learning diverse and accurate base classifiers is central to DGE's success, and discuss the implications of these findings for future work on GNNs.

Published as a conference paper at ICLR 2023
DEEP ENSEMBLES FOR GRAPHS WITH HIGHER-ORDER DEPENDENCIES
Steven J. Krieg, William C. Burgis, Patrick M. Soga, & Nitesh V. Chawla' Lucy Family Institute for Data and Society University of Notre Dame Notre Dame, IN 46556
{skrieg, wburgis, psoga, nww.wlajend.ee...
ABSTRACT
Graph neural networks (GNNs) continue to achieve state-of-the-art performance on many graph learning tasks, but rely on the assumption that given graph is a sufficient approximation of the true neighborhood structure. When system con- tains higher-order sequential dependencies, we show that the tendency tradi- tional graph representations to underfit each node's 's neighborhood causes existing GNNs to generalize poorly. To address this, we propose a novel Deep Graph En- semble (DGE), which captures neighborhood variance by training an ensemble of GNNs on different neighborhood subspaces the same node within a higher- order network representation. We show that DGE consistently outperforms isting GNNs on semisupervised and supervised tasks on six real-world data sets with known higher-order dependencies, even under similar parameter budget. We demonstrate that diverse and accurate base classifiers are central to DGE's success, and discuss the implications of these findings for future work on ensem- bles of GNNs.
INTRODUCTION
Graph neural networks (GNNs) solve learning tasks by propagating information through each node's neighborhood in a graph (Zhou et al., 2020; Wu et al., 2020). Most present work on GNNs assumes that a given graph
sufficient approximation of the underlying neighborhood structure. But growing body of work has challenged this assumption by showing that traditional graphs often can- not capture the higher-order structure and dynamics that govern many real-world systems (Lam- biotte et al., 2019; Battiston et al., 2020; Porter, 2020; Torres et al., 2021; Battiston et al., 2021). In the present work, we couple GNNs with a specific family of graphs, higher-order networks (HONs), which encode sequential higher-order dependencies (i.e., conditional probabilities that cannot be explained by a first-order Markov model) in a graph structure. traditional graph, which call first-order network (FON), represents system by decomposing it into set of pairwise edges, so the only way to infer polyadic interactions is via transitive paths over adjacent nodes. When higher-order dependencies are present, these Markovian paths underfit the true neighborhood (Scholtes, 2017) and can thus produce many false positive interactions between nodes (Lambiotte al., 2019). To address this limitation, Xu al. (2016) proposed HON that creates conditional nodes to more accurately encode the observed higher-order interactions. By preserving this ad- ditional information in the graph structure, HONs have produced new insights in studies of user behavior (Chierichetti et al., 2012), citation networks (Rosvall et al., 2014), human mobility and navigation patterns (Scholtes et al., 2014; Peixoto & Rosvall, 2017), the spread of invasive species Saebi et al. (2020b), anomaly detection (Saebi et al., 2020d), disease progression (Krieg et al., 2020b), and more (Koher et al., 2016; Peixoto & Rosvall, 2017: Scholtes, 2017: Lambiotte et al., 2019; Saebi et al., 2020a). However, their use with GNNs has not been thoroughly explored.
As Figure I illustrates, the tendency of FONs to underfit has consequences for GNNs, which typi- cally compute representations by recursively pooling features from each node's neighbors. In order
"Corresponding author.

---

Published as a conference paper at ICLR 2023
g
GNN
A2
GNN learns similar
representations for A and B, despite differences in the observed paths
A
AC A
E
A C D C A
ACDCA
ACDCA
BCECB
A
CIA
D
-CCI
To learn a representation for C, GNN must aggregate neighborhoods of both CIA and CJB
BCECB
heiA
BCECB
hoge
BC
observed paths
B
C
E
B
CIB
GNN
Figure 1: A toy example of challenges faced by GNNs in modeling systems with higher-order dependencies. A FON (G1) underfits the higher-order dependencies in the observed paths. Con- sequently, a GNN will learn similar representations for A and B, since they share the same 2-hop neighborhood in Gr A HON (Gk, with k = 2 in this example) uses conditional nodes to encode higher-order dependencies. For example, node C|A represents the observed dependency that C only interacts with D when it also interacts with A (note that in real-world systems, G5 rarely breaks the graph into multiple components). However, computing a representation for then requires a GNN to aggregate multiple local neighborhoods. Colors depict node features.
to maximize GNN performance, we must ensure that local neighborhoods capture the true distri- bution of interactions in the system. To enable GNNs to utilize the additional information encoded HONs, we propose a novel Deep Graph Ensemble (DGE), which uses independent GNNs to exploit variance in higher-order node neighborhoods and learn effective representations in graphs with oigher-order dependencies. The key contributions of our work include:
1. We analyze the data-level challenges that fundamentally limit the ability of existing GNNs to learn effective models of systems with higher-order dependencies.
2. We introduce the notion of neighborhood subspaces by showing that neighhorhoods in HON are analogous to feature subspaces of first-order neighborhoods. Borrowing from ensemble methods, then propose DGE to exploit the variance in these subspaces.
3. We experimentally evaluate DGE against eight state-of-the-art baselines on six real-world data sets with known higher-order dependencies, and show that, even with similar param- eter budgets, DGE consistently outperforms baselines on semisupervised (node classifica- tion) and supervised (link prediction) tasks.'
4. We demonstrate that DGE's ability to train accurate and diverse classifiers is central to strong performance, and show that ensembling multiple GNNs with separate parameters is consistent way maximize the trade-off between accuracy and diversity.
2 BACKGROUND AND PRELIMINARIES
2.1 HIGHER- NETWORKS
Let S = (S,, S2, } be a set of observed paths (e.g., flight itineraries, disease trajectories, user clickstreams), where each S, (81, ..., Sm)) is sequence of entities (e.g., airports, diagnosis codes, or web pages). Let A US denote the set of entities across all sequences. By using a graph summarize S. can model the global function of each entity in the system and solve a number of useful learning problems. For example, we can predict disease function via node classification interactions between airports using link prediction. However, there is large space of possible graphs that can represent S. We consider two: FON, and the HON introduced by Xu al. (2016). In a FON 91 EI), the node set V A (or, more generally, the mapping f V + A is bijective), and the edge set ε1 is the set of node pairs (u, v) E Vi x V that are adjacent elements
least one S;.
"oode and 3 data sets are availahle https: : /ttpt/ggttbb.tt/// com/s hwmmsjkriigg/// /dge "This is distinct from sequence models like transformers, which typically predict an entity's local function within single sequence.
2

---

Published as a conference paper at ICLR 2023
In HON Gk Ex) with order k > 1, each node is sequence of entities w' (ai,..., "m-1.'m) where each of E 1/1 and m S k. We define o'm as the base node, and in practice use the notation v' d'n (a,,..,, d'n-1 to emphasize that each u' E V/ represents a base node whose current state is conditioned on a set of predecessors. Each node can have a different number of predecessors, and conditional node with m is only created if the conditional dis- tribution of paths it encodes sufficiently reduces the entropy of the graph (Saebi et al., 2020d). This means that V& S A#; or, more generally, the mapping f V2 + A injective but not necessarily bijective. We define 2 = (u' E V&, a'm = u as the higher-order family of u (including itself), and call each v' E 1 a relative of u (in Figure 1, for example, C|A and CJB are the relatives of C). Like E the edge set & is the set of node pairs (u, v) E V& x VE that are adjacent in at least one S, In both HONs and FONs, edges are directed such that (u, v) A (v, u) and weighted via wg Ex R2 where 0 indicates missing edge. By creating conditional nodes, a HON can express higher-order interactions while remaining a graph, since each edge is still a 2-tuple. For example, consider that passengers who fly from Atlanta to Chicago are much more likely to fly back to Atlanta than to New York, and vice versa. A HON can encode this dependency by creating the conditional nodes "Chicago| Athicago/Atlanta" AAtlanta" and "Chicago New York", which changes the topology and flow of information within local neighborhoods (Rosvall et al., 2014). Choosing which conditional nodes and edges create is non-trivial problem; readers interested in more details can refer to Krieg et al. (2020a), who proposed the procedure that we used in this study.
Related graph-based models The term "higher-order" is also used in the literature to refer the analysis of polyadic structures within graphs (Benson et al., 2016), as well GNNs that are able to distinguish these structures (Morris et al., 2019; Li al., 2020; Schnake et al., 2021). These studies rely on the same assumptions as other GNNs, i.e., that a graph is a sufficient approximation of the neighborhood structure. Despite similarities in terminology, HONs are primarily concerned with the question of initial representation (i.e., how should the graph be constructed?) rather than downstream analysis of an existing graph, and thus address a fundamentally different- -thouh complementary problem (Lambiotte et al., 2019). HONs are also distinct from other formalisms like hypergraphs and simplicial complexes in that they encode conditional distributions that govern higher-order paths (via conditional nodes and directed, weighted edges), and therefore represent different kinds of systems (Battiston et al., 2020; Porter, 2020; Torres et al., 2021; Battiston et al., 2021). Some very recent works have shown that aggregators based on paths (via random walks) can improve the expressiveness of GNNs (Eliasof et al., 2022: Jin et al., 2022b), but these still rely on the graph structure guide path sampling. This further motivates the use of representations like HONs, which are designed to consistently and accurately encode higher-order paths for downstream learning tasks (Rosvall al., 2014; Xu et al.. 2016; Sacbi al., 2020d; Krieg et al.. 2020a). To our knowledge, only one study has previously used GNNs with HONs (Jin et al., 2022a); however, as we discuss in Section 3, its proposed method has critical shorteomings.
2.2
GRAPH NEURAL NETWORKS
A generic GNN computes hidden vector representation for node u at timestamp I according to:
(+) COMBINE (1. (t-1), (( v N(u)))))
(1)
where N/()) is the neighborhood of u in a graph G. What typically distinguishes GNNs is how they define COMBINE and AGGREGATE, and how they represent (u) (Xu et al., 2019; Zhou et al., 2020; Wu et al., 2020). By recursively pooling features via Eq. 1, GNNs implicitly construct higher- order neighborhoods across transitive paths. This allows nonadjacent nodes to share information they are close in the graph (Li et al., 2018; Chen al., 2020); however, we will demonstrate, when higher-order dependencies are present, assuming transitivity leads GNNs that are trained on FONs to generalize poorly.
In this work, we do not reformulate Eq. I and are agnostic toward its particular implementation. We instead abstract GNN as a function that takes a single node as input and returns either the final hidden representation h(4) or, in a supervised setting, a vector of predicted label probabilities y.:
GNN( = h or GNN(u)= 8... We always assume that 9 contains initial node features (x.,. Yu E V} and that GNN(.) is parame- terized by weights 0, but for simplicity we omit them from our notation.
3

---

Published as a conference paper at ICLR 2023
GNN
CIA
C
CIA
A
CIA
GNN
Pk
CIB
B
CIB
CIA
sample relatives from S with replacement
compute GNN
pool GNN outputs
GNN
outputs
Figure 2: Overview of DGE. Given a HON Gs. DGE computes outputs for each base node u by a) resampling relatives from u's higher-order family 2 via sampling distribution Pt b) computing outputs for each sampled relative using independent GNN modules, and c) pooling the outputs.
GNN ensembles Ho (1998) and Breiman (2001) showed that training an ensemble of shallow learners on random subspaces could exploit variance in the feature space and improve performance, and Dietterich (2000) demonstrated that these ensembles are most potent when the predictions of their base classifiers are accurate and diverse. Deep ensembles have typically been used with random weight initializations to improve uncertainty estimation and robustness (Lakshminarayanan et al., 2017: Fort al., 2019; Wasay & Idreos, 2020), which has benefited GNNs via mechanisms like multi-head attention (Veličković et al., 2018; Brody et al., 2022: Hou et al., 2021), but very few works have directly explored ensembles of GNNs. Some recent exceptions have suggested that ensembling subgraphs could benefit GNNs (Zeng et al., 2021; Tang et al., 2021; Lin et al., 2022).
DEEP GRAPH ENSEMBLES FOR HIGHER-ORDER NETWORKS
3.1 WHY ENSEMBLES?
There are a number of design challenges (CHs) we must address in order to realize the joint potential of GNNs and HONs. In HON, entities are represented by non-fixed number of conditional nodes (CHI); for example, represented by one node. Conditional nodes typically have different neighborhoods (CH2); for example, in Figure 1, CIA and C have different neighbors. Further, they may vary importance (i.e.. degree) in the graph (CH3) (Xu et al., 2016; Saebi et al., 2020d). To address these challenges, one intuitive idea is to reformulate Eq. so that it computes a representation for u by sampling neighbors from any of u's relatives. However, this fails to address CH2 because GNN would aggregate the samples without considering differences between relatives. Another idea to compute representations for each relative separately, then pool them via a permutation-invarian function like an elementwise MEAN, as proposed for HO-GNN by Jin et al. (2022a). But this does not address CH3, since all relatives would contribute equally the final representation. Moreover, if we assume that all relatives in higher-order family share the same (or similar) features, this solution will overrepresent features associated with larger higher-order families. In order propose a method that comprehensively addresses these challenges, we first consider the following relationship.
Figure C is represented by two nodes but A, B, D. and E are each only
Theorem 1. Let G1 and GR be FON and HON, respectively, both constructed from the same input S. Let Ni (u) and Ni(u)) denote the neighborhoods of any node u G1 and GR, respectively. Let AGGREGATE() represent any symmetric neighborhood aggregation function. If V1 and u' E S2 then AGGREGATE(NN (u')) a biased estimator of AGGREGATE(M((U))
We prove Theorem in Appendix A. Intuitively, we observe that HONs are constructed such that Na (u') C (M),,, and u' only exists in GR if the expectation of random walker differs substantially (measured via KL-divergence) from u in G1 (Saebi et al., 2020d; Krieg et al., 2020a). Consequently, these differences in neighborhood structure will shift the expectation of the features gathered by AGGREGATE(NN A typical strategy for training a single GNN would involve attempting to eliminate this variance via some sampling method the graph. We instead take ensemble
4

---

Published as a conference paper at ICLR 2023
approach and propose to regularize the model via multiple GNNs that err in different ways. Toward this end, and inspired by feature subspace methods (Ho, 1998; Breiman, 2001), we call Na((a) a neighborhood subspace of (u).
Remark result from Theorem also relates to the expressiveness of an aggregator over neigh- borhoods in Gk- Consider two nodes u, V E V1 whose rooted subgraphs (i.e., neighborhoods) are non-isomorphic but are not distinguishable by the aggregator in G1- As long there exists some v' E 2 (excluding u itself), then we know that, since it is a biased estimator, the aggregator can distinguish u' from in Gx- It follows transitively that the aggregator can also distinguish u' from n. is possible that there also exists some r' E S that cannot be distinguished from v', but this would be extremely unlikely occur over all pairs of relatives in S and 2 We can thus improve the expressiveness of the model by allowing the information from nodes in O to contribute to the final representation for each u.
Guided by these observations, we propose to address the CHs outlined above by training an ensemble of GNNs { 1GNN1, GNN2, .... G Given set of training nodes D C V1, we generate bootstraps for all u D and S é (i.e., each bootstrap contains exactly one relative of each training node). This constraint allows us to avoid the feature overrepresentation problem, address CHI by sampling with replacement, and address CH2 by training each GNN; on different neighborhood subspaces as represented in D To solve CH3, we weight the sampling probability for each relative u' according to the normalized out-degree of its higher-order family:
(D D ...., D(9) } subject to the constraint that ( n N
OUTDEGR (w')
Pt (v/) Eveny OUTDEG&("")
where u E D and (u') the weighted out-degree of u' in GG. Because weighted out-degree in 9r is the frequency with which u' appears in S (Krieg et al., 2020a). it is natural measure of the importance of u' with respect to the rest of the higher-order family Ω D C & consists of node pairs for an edge task, we modify Eq. 3 slightly. For each edge (u, v) E D, we resample a single pair of relatives (u', r') with probability according to the normalized weights of all edges between relatives of and D:
wx(u', v')
ph (u,
(4)
(um x (wu(u","" v²))"
3.2 TRAINING AND INFERENCE
Let ( denote the relative of u that was sampled for the hh bootstrap. We consider a supervised or semisupervised setting, in which our goal is to predict class probabilities ý. for each u E D such that some loss minimized w.r.t. ground truth yu. We propose three methods for computing y.:
y_ = a (CONCAT(( (GNN, v. w) and GNN, (u') = (6.0
(5a)
8n = a MEEN (INEAN((GNN,UU)) (GNN,(D!".. w) and (N) = (3.9)
(5b)
8n MEAN -MEEAMMMNNN.OOO (D),
and GNN. = "
(Sc)
where a is a non-linear activation, CONCAT is vector concatenation, MEAN is elementwise mean, T is the transpose of x, (6.4) E IR' represents the hidden state of node u' in the th (final) layer of GNN, and d is the number of hidden units (we assume d is fixed for all GNN,). Using c to denote the number of classes, for Eq. 5a we have W E Rdéxe, and for Eq. 5h we have W E Rdxe. We refer Eq. 5a as DGE-concat, Eq. 5b DGE-pool, and Eq. 5c DGE-bag.
In DGE--concat and DGE-pool each GNN outputs hidden representations, which are concatenated or pooled, respectively, before computing the logits. This means that they can be trained in end-to-end fashion as a single neural network with parallel but independent GNN modules. During forward pass, each GNN; only computes representations for the nodes in D In DGE- bag, on the other hand, each GNN outputs class probabilities, which means that each GNN is trained independently
5

---

Published as a conference paper at ICLR 2023
Table 1: Summary of graphs used in node classification and link prediction experiments.
Name
[S]
[Vi
|&1]
[22
[2]
# classes
H(G1)
H(G2)
Air
17.1m
416
13,735
7.461
236,806
10
0.351
0.288
T2D
0.8m
908
314,352
5,462
367,530
16
0.099
0.099
Wiki
76.2k
4,179
70,662
5,584
84,806
10
0.366
0.375
Mag
3.8m
4.079
1,873,279
9,568
1,957,602
4
0.323
0.336
Mag+
8.1m
17,428
5,098,787
192,204
7,980,026
6
0.292
0,310
Ship
54.9k
5,586
369,952
8,586
422,426
38
0.477
0.489
and their predictions are simply averaged to compute the final probabilities. We also designed an attention-based pooling method, but found that it did not generalize well (Appendix D).
One important question is whether all GNN; should share parameters. In other words, is an ensemble necessary, or is it sufficient use single, more complex model (Abe et al., 2022)? We evaluated this question experimentally, and use DGE-concat",, DGE-pool*, and DGE-bag" to denote shared- parameter variants of Eqs. 5a, 5b, and 5c, respectively. For DGE-concat* and DGE-pool*, adjusted our training procedure so that, during backpropagation, each parameter was updated once according to its contribution to the summed loss across all ( For DGE-bag*, this meant that each GNN, was essentially pretrained on D(f-1), Since each GNN, shares parameters, none of these variants are true ensembles. Instead, they are single models that synthesize representations for conditional nodes via a READOUT function (Wu et al., 2020) on each higher-order family. DGE-pool* is similar to HO-GNN (Jin al., 2022a). which uses single GNN and computes representation for each u via the mean of all its relatives (rather than a weighted sample) in 2 We also considered one final variant, DGE-batch* which does not for training. Instead, it uses Eq. to sample a new set of relatives for each batch. Then, during inference, we use the same procedure as DGE-bag: resample relatives for each node and compute their outputs via Eq. 5c. DGE-batch? thus drops any resemblance to an ensemble, instead addressing CHI, CH2, and CH3 entirely via batch sampling.
fixed of bootstraps
Figure 2 summarizes the components of DGE: resampling l relatives for each entity via Eq. 3, computing a node representation for each sampled relative via Eq. 2, and pooling the computed representations via Eq. 5a, 5b, or 5c. In general, DGE's computational cost is linear with the cost of the base GNN and the ensemble size E, since we are essentially constructing copies of that GNN (or, in the case of shared parameters, repeating l forward passes per example). For given node u, the additional cost of sampling and pooling l relatives is O (DE]) and O(E), respectively, which are trivial compared to the costs of Eq. 2 (Wu et al., 2020). Additionally, the one-time cost of constructing GR increases linearly with (Krieg et al., 2020a). Since we used G2 in our experiments, there was marginal overhead for graph construction as compared to G1.
4 EXPERIMENTAL RESULTS AND DISCUSSION
4.1 EXPERIMENTAL SETUP
We used GON (Krieg et al., 2020a) to construct FONs (Gi) and HONs with k = 2 (G2) for six real-world data sets with known higher-order dependencies: flight itineraries for airline passengers in the United States (Air) (Rosvall et al., 2014), disease trajectories for type 2 diabetes patients in Indiana (T2D) (Krieg et al., 2020b), clickstreams of users playing the Wikispeedia game (Wiki) (West et al., 2009), readership trajectories for a large online magazine (Mag and a larger version, Mag+, for node classification only) (Wang et al., 2020), and global shipping routes (Ship) (Saebi et al.. 2020c). Table 1 summarizes their key characteristics, including average homophily H (see Appendix G for details). We discuss additional details and preprocessing steps in Appendix B.
We evaluated several baselines, including GCN (Kipf& & Welling, 2017), GAT (Veličković et al., 2018). 8). GraphSAGE (Hamilton et al., 2017). GIN (Xu et al., 2019) and GATv2 (Brody et al., 2022), and SEAL (Zhang & Chen, 2018) (link prediction only). Other noteworthy baselines are Graph- SAINT (Zeng et al., 2020) which samples a different subgraph for each training iteration (Hu et al., 2020); GCNII (Chen al., 2020), which uses residual connections to address over-smoothing: and

---

Published as a conference paper at ICLR 2023
Table 2: Node classification results (micro FI). Bold font indicates the best result for each data set.
Model
Air
T2D
Wiki
Mag
Mag+
Ship
GCN
0,818 0.03
0.480
0.02
0.643 + 0.01
0.796 0.01
0.710 = 0.01
0.746 0.0
GCNII
0.839 0.05
0,511
= 0.02
0,654 + 0.02
0,801 = 0.01
0.712 = 0.01
0.770 o.l
GAT
0.804 1 0.03
0.282 1: 0.10
0.639 1: 0.02
0.487
0.06
0.511 1: 0.02
0.745 am
GATv2
0.838 0.03
0.292 0.07
0.643 1 0.03
0.495 0.05
0.527 1 0.02
0.747 am
GraphSAGE
0.781 = 0.04
0.654 = 0.04
0.625 + 0.02
0.808 = 0.02
0.689 = 0.01
0.796 + 0.01
GIN
0.745 0.02
0.673 0.04
0.636 + 0.02
0.826 0.02
0.722 = 0.00
0.801 =001
GraphSAINT
0.802 + 0.02
0.600 + 0.07
0.664 0.01
0.821 0.02
0.719 = 0.01
0.803 0.0
PathGCN
0.846 0.02
0.523 0.03
0.616 +
0.735 0.02
0.622 =
0.781 000
HONEM
0.805 + 0.04
0.566 + 0.02
0.588 0.01
0.728 0.02
0.620 = 0.011
0.750 + 0.
HO-GNN
0.822 0.02
0.436 0.03
0.581 0.00
0.785 0.01
0.702 +
0.787
DGE-coneat
0,825 0.04
0.501 0.06
0.615 = 0.02
0.790
0.02
0.681 = 0.04
0.828 =
DGE-concat
0.810 0.04
0,439 = 0.03
0,577 + 0.02
0.761
+ 0.02
0.642 = 0.01
0,809 + 0.01
DGE-pool
0.839 0.03
0.735 1 0.03
0.671 1.00
0.860 1: 0.01
0.722 1 0.01
0.808 0.
DGE-poo!*
0.865 0.02
0.555 0.07
0,599 0.04
0.775 0.01
0.671 1 0.01
0.767 0.2
DGE-bag
0.856 = 0.02
0.770 = 0.04
0.681 0.00
0.871
0.01
0.769 = 0.01
0.840 0.01
DGE-bag*
0.766 0.04
0.719
0.04
0.644.0..0
0.841 0.02
0.739
= 0.01
0.825 0.01
DGE-batch*
0.764 + 0.03
0.646 = 0.01
0.623 0.01
0.818 0.01
0.742 = 0.00
0.812 + 0.01
* shared parameters
Table 3: Link prediction results (AUPRC), Bold font indicates the best result for each data set.
Model
Air
T2D
Wiki
Mag
Ship 0.887 = 0.01
0.818 = 0.02
0.818 + 0.00
0.834 + 0.01
0.879 0.00
Best baseline
(SEAL)
(HONEM)
(SEAL)
(HO-GNN)
(SEAL)
DGE-coneat
0.886 + 0.01
0.815 1: 0.01
0.774 +: 0.01
0.802 + 0.00
0.910 ::2 0.00
DGE-concat*
0.856 0.01
0.779 1: 0.01
0.712 1: 0.02
0.769 0.01
0.904 1  0.00
DGE-pool
0.851 = 0.02
0.920 + 0.00
0,838 + 0.03
0.913 = 0.00
0.898 = 0.00
DGE-pool*
0.845 0.01
0.901 0.00
0,802 + 0.06
0.898 0.00
0.815
DGE-bag
0.887 = 0.00
0.907
+ 0.00
0.876 0.01
0.921 = 0.00
0.895 = 0.00
DGE-bag*
0.862 0.02
0.894 0.00
0,856
0.916
1:2 0.891
DGE-batchi
0.853 + 0.03
0.871 + 0.01
0.830 + 0.01
0.887 0.00
0.865 + 0.00
* shared parameters
PathGCN (Eliasof et al., 2022), which learns spatial operators paths sampled via random walks. We also evaluated two baselines designed specifically for HONs: HONEM, a matrix factorization method (Sacbi al., 2020a), and HO-GNN (Jin al., 2022a). All baselines used G input (we also evaluated each baseline using G2 as input, details are in Appendix E). We manually tuned each model (details in Appendix C). For DGE, unless noted otherwise, we fixed poon--ooinng variant of GraphSAGE as the base GNN, since a) it performed reasonably well as procedure intuitively complements the relative sampling and pooling used by DGE. We used Python 3.7.3 and Tensorfow 2.4.1 for all experiments, and utilized Stellargraph 1. 1.2.1 (Data61, 2018) for the implementation DGE.
16 and used the
a baseline on all six data sets, and its
4.2 EXPERIMENTAL RESULTS
Node classification and link prediction On the node classification task (Table 2), DGE-bag out- performed all other methods on five data sets and was second to DGE-pool* on Air. DGE-pool per- formed only slightly worse than DGE-bag in all cases, but DGE-concat did not generalize well and performed poorly in all cases except Ship. This suggests that our relative sampling procedure was ef- fective in conjunction with ensembling (DGE-bag), but not effective regularizing single fully- connected network against the variance in Gy- Since concatenation depends heavily on the position of each relative in the vector representation, DGF-coneat overfit nodes that had many relatives.

---

Published as a conference paper at ICLR 2023
Air
T2D
Wiki
Mag
4.0-
Test loss
layers
2.0
0.0
GCN
GCNI
GraphSAGE
GIN
GraphSAINT
DGik-bag
GCN
GONI
GraphSAGE
GIN
GraphSAINT
DGE-bag
GCN
GONII
Graphi
GIN
Graph
DGE-bag
GCN
GCNII
GraphS
GIN
GraphSAINT
DGE-bag
Figure 3: Node classification loss as a function of model depth. Error bars are standard deviation.
Sharing parameters typically reduced performance for each DGE variant, excepting DGE-pool on Air. We discuss this observation in Section 4.3, The differences between HO-GNN and DGE em- phasize the importance of accounting for both the variance in neighborhood subspaces in Gs as well as the differences in importance between relatives. Some baselines were occasionally competitive: GCNII, GATv2, and PathGCN performed relatively well on Air, and GCNII and GraphSAINT per- formed relatively well on Wiki, However, on Mag and especially T2D, DGE- outperformed all baselines by a significant margin. PathGCN and the full-batch models struggled T2D, likely due to its high density-
that there are many transitive and false positive paths in G1- Low ho- mophily may also have contributed their poor performance (Zhu et al., 2020) (see discussion in Appendix G). GAT and GATv2 performed especially poorly on the dense graphs, likely because they compute attention weights (instead of using the given edge weights) and were thus more susceptible to overfitting. The link prediction results, summarized in Table 3, tell similar story. Because of its strong performance, we focus the remainder of our analysis on DGE-bag. For details on training time and convergence for all models, please see Appendix F.
Model size For the baselines, increasing the number of GNN layers typically increased general- ization error (Figure 3). For DGE-bag, the test loss decreased with increased model depth in all but one case (layer 3 on T2D). These results support the findings of Lambiotte et al. (2019) that tran- sitively inferring paths in FON cannot account for higher-order dependencies, and our hypothesis that GNNs trained on Gi will overfit on non-existent paths. The exception to this pattern was Wiki, on which many models performed best with 3 layers. This difference is perhaps because Wiki was the sparsest graph, meaning that the likelihood of sampling false positive path is relatively low. However, DGE-bag still produced the lowest test error all depths.
In order to ensure that DGE's performance was not simply due to using more expensive model, we compared DGE-bag to the strongest baselines several parameter budgets (Table 4; results for Wiki and Mag are available in Appendix E). DGE-bag underperformed with the smallest budgets, since each base learner was too weak and underfit. We found that sharing parameters (DGE-bag resolved this issue and produced strong results on T2D, Wiki, and Mag. However, with a moderate parameter budget, DGE-bag consistently outperformed other models. Again, for most baselines, increasing model depth simply caused caused them overfit and decreased performance.
4.3 ENSEMBLE DIVERSITY AND PARAMETER SHARING
The variants of DGE that used separate parameters generally performed best. To understand this observation, we draw from prior work on ensembles, which has established that ensembles are most potent when the individual classifiers have low eтror and high disagreement (Dietterich, 2000). As Figure shows, DGE-bag consistently produced classifiers that were both diverse and accurate. The shared-parameter variants often produced classifiers that were either diverse or accurate, but not both. We observed similar results for Air, Wiki, and Mag (Appendix E). These results reflect node classification performance (Table 2) and support several important conclusions. First, the high dis- agreement in DGE-bas demonstrates that treating higher-order relatives as neighborhood subspaces successfully introduced variance into the model. Second, the low mean error for DGE-bag demon- strates that ensembling GNNs with separate parameters effectively captured and exploited this vari- ance. Third, sharing parameters (i.e., using a single, more complex model) did not achieve the same
8

---

Published as a conference paper at ICLR 2023
Table 4: Node classification results (mean micro Fl for 5-fold cross validation) under various pa- rameter budgets. Bold font indicates the best result for each budget and data set.
Total parameters (Air)
Total parameters (T2D)
Model
Layers
10k
50k
100k
500k
Im
10k
50k
100k
500k
Im
GCNII
2
0.78
0.79
0.80
0.80
0.80
0.43
0.47
0.47
0.49
0.50
4
0.77
0.78
0.78
0.79
0.79
0.43
0.47
0.50
0.51
0.51
8
0.74
0.76
0.76
0.76
0.76
0.45
0.49
0.49
0.51
0.51
GATv2
2
0.66
0.73
0.80
0.82
0.83
0.11
0.14
0.17
0.18
0.18
4
0.49
0.38
0.62
0.71
0.75
0.10
0.12
0.14
0.14
0.15
GIN
2
0.74
0.74
0.75
0.75
0.75
0.54
0.64
0.67
0.66
0.67
4
0.63
0.72
0.73
0.73
0.73
0.36
0.38
0.38
0.44
0.46
GraphSAINT
2
0.71
0.75
0.75
0.76
0.77
0.45
0.56
0.59
0.60
0.61
4
0.60
0.64
0.68
0.74
0.74
0.25
0.27
0.28
0.28
0.28
DGE-bag
2
0.68
0.79
0.81
0.83
0.86
0.47
0.66
0.73
0.75
0.77
DGE-bag"
2 0.70
0.76
0.80
0.81
0.81
0.65
0.70
0.70
0.71
0.71
DGE-bag
DGE-bag*
DGE-pool*
DGE-batch*
Mean test loss
3.0
2.0
0.6
0.8
1.0
0.6
0.8
1.0
0.6
0.8
1.0
0.6
0.8
1.0
K
K
K
K
Figure 4: Mean node classification loss for all pairs of the é = 16 base GNNs within each testing fold on T2D, plotted as a function Cohen's kappa (lower values indicate lower agreement). Each point represents one pair of GNNs in the ensemble. All plots contain the same number of points.
effect. DGE-poo]* outperformed DGE-bag on Air because the classifiers were accurate enough to make up for the lack disagreement. This may because Air had larger higher- families than other data sets, so each bootstrap was less representative of the true neighborhood. However, using separate parameters each GNN-a true ensemble approach-wve was most consistently effective way to balance the trade-off between accuracy and diversity.
LIMITATIONS, OTHER RELATED WORK, AND FUTURE DIRECTIONS
DGE's empirical success has implications for multiple research areas. Most broadly, we suggest that ensembling techniques for GNNs have been underexplored. However, generalizing our findings is complicated by the fact that DGE relies on the HON to supply the neighborhood variance, which in turn limited to representing sequential data. Our results also suggest that the task of designing informed graph representations like HONs essential and has been previously overshadowed by downstream learning algorithms. Other research on higher-order models has made progress toward this end, but much work remains to generalize these models and the types of dependencies they can represent. One area we consider promising for future work is graph structure learning. At present, HONs are constructed in unsupervised fashion, but future work could overcome this limitation by inferring the graph structure that best solves the given task (Brugere & Berger-Wolf Wolf, 2020; Chen & Wu, 2022). Unfortunately, most standard data sets for GNN tasks are pre-constructed graphs, meaning that any higher-order dependencies (sequential or otherwise) have already been lost before learning begins. By integrating graph construction into the learning process and continuing to de- velop more powerful GNNs, we will increase our capacity to model higher-order relationships and expand the frontier of machine learning on graphs.

---

Published as a conference paper at ICLR 2023
REFERENCES
Taiga Abe, E Kelly Buchanan, Geoff Pleiss, Richard Zemel, and John Cunningham. Deep ensem- bles work, but are they necessary? arXiv preprint arXiv:2202.0660 2022.
Federico Battiston, Giulia Cencetti, Iacopo lacopini, Vito Latora, Maxime Lucas, Alice Patania, Jean-Gabriel Young, and Giovanni Petri. Networks beyond pairwise interactions: structure and dynamics. Physics Reports, 874:1-92, 2020.
Federico Battiston, Enrico Amico, Alain Barrat, Ginestra Bianconi, Guilherme Ferraz de Arruda, Benedetta Franceschiello, lacopo lacopini, Sonia Kéfi, Vito Latora, Yamir Moreno, et al. The physics of higher-order interactions in complex systems. Nature Physics, 17910):093--109, 2021.
Austin R Benson, David F Gleich, and Jure Leskovec. Higher-order organization of complex net- works. Science, 353(6295: 2016.
Leo Breiman. Random forests. Machine learning, 45(1):5-32, 2001.
Shaked Brody, Uri Alon, and Eran Yahav. How attentive are graph attention networks? International Conference Learning Representations, 2022.
Ivan Brugere and Tanya Y Berger-Wolf, Inferring network structure from data. arXiv preprint arXiv:2004.02046, 2020.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph con- volutional networks. In International Conference on Machine Learning, pp. 1725-1735, PMLR, 2020.
Yu Chen and Lingfei Wu. Graph neural networks: Graph structure learning. In Graph Neural Networks: Foundations, Frontiers, and Applications, pp. 297-321. Springer, 2022.
Flavio Chierichetti, Ravi Kumar, Prabhakar Raghavan, and Tamas Sarlos. Are web users really markovian? In Proceedings of the 21 international conference on World Wide Web, pp. 609- 618, 2012.
CSIRO's Data61.
Stellargraph machine learning library.
https://githutt com/
stallargrapphssteelarrgggg 2018.
Thomas G Dietterich. Ensemble methods in machine learning. In International workshop multi- ple classifier systems, pp. 1-15. Springer, 2000.
Moshe Eliasof, Eldad Haber, and Eran Treister. pathgen: Learning general graph spatial operators from paths. In International Conference Machine Learning, pp. 5878-5891 PMLR, 2022.
Stanislav Fort, Huiyi Hu, and Balaji Lakshminarayanan. Deep ensembles: A loss landscape per-
spective. arXiv preprint 1rXiv:1912.02757, 2019.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Tin Kam Ho. The random subspace method for constructing decision forests. IEEE transactions on pattern analysis and machine intelligence, 20(8):832-84) 1998.
Xiaochen Hou, Peng Qi, Guangtao Wang, Rex Ying. Jing Huang, Xiaodong He, and Bowen Zhou. Graph ensemble learning over multiple dependency trees for aspect-level sentiment classification. arXiv preprint arXiv:2103. 11794, 2021.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:22118 1121188-22113 2020.
Di Jin, Yingli Gong, Zhiqiang Wang, Zhizhi Yu, Dongxiao He, Yuxiao Huang, and Wenjun Wang. Graph neural network for higher-order dependency networks. In Proceedings of the ACM Web Conference 2022, pp. 1622-1633 1630, 2022a.
10

---

Published as a conference paper at ICLR 2023
Di Jin, Rui Wang, Meng Ge, Dongxiao He, Xiang Li, Wei Lin, and Weixiong Zhang. Raw-gnn: Random walk aggregation based graph neural network. arXiv preprint arXivv2206.1399) 2022b.
Thomas N. Kipf and Max Welling. Semi Semi-supervised classification with graph convolutional net-
works. In International Conference on Learning Representations (ICLR). 2017.
Andreas Koher, Hartmut HK Lentz, Philipp Hövel, and Igor M Sokolov. Infections temporal networks-4 matrix-based approach. PloS one, 11(4):=051209, 2016.
Steven Krieg, Peter M Kogge, and Nitesh V Chawla. Growhon: A scalable algorithm for growing higher-order networks of sequences. In International Conference on Complex Networks and Their Applications, pp. 485-494 Springer, 2020a.
Steven Krieg, Daniel Robertson, Meeta P Pradhan, and Nitesh V Chawla. Higher-order net- works of diabetes comorbidities: Disease trajectories that matter. In 2020 IEEE International Conference on Healthcare Informatics (ICHI), pp. 1-11. IEEE, 2020b.
Balaji Lakshminarayanan. Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. Advances in neural information processing systems, 30, 2017.
Renaud Lambiotte, Martin Rosvall, and Ingo Scholtes. From networks to optimal higher-order models of complex systems. Nature physics, 15(4)3313-300, 2019.
Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning. Advances in Neural Information Processing Systems, 33:4465-44788 2020.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Thirty-Second AAAI conference artificial intelligence, 2018.
Qi Lin, Shuo Yu, Ke Sun, Wenhong Zhao, Osama Alfarraj, Amr Tolba, and Feng Xia. Robust graph neural networks via ensemble learning. Mathematics, 10(8):1300, 2022.
Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pp. 4602-4609, 2019.
Tiago P Peixoto and Martin Rosvall. Modelling sequences and temporal networks with dynamic community structures. Nature communications, 8(1):582, 2017.
Mason A Porter. Nonlinearity+ networks: A 2020 vision. In Emerging Frontiers in Nonlinear
Science, pp. 131-159. Springer, 2020.
Martin Rosvall, Alcides V Esquivel, Andrea Lancichinetti, Jevin West, and Renaud Lambiotte. Memory in network flows and its effects on spreading dynamics and community detection. Nature communications, 5:4630, 2014.
Mandana Saebi, Giovanni Luca Ciampaglia, Lance M Kaplan, and Nitesh V Chawla. Honem: learning embedding for higher order networks. Big Data, 2(4):255-269, 2020a.
Mandana Saebi, Jian Xu, Salvatore R Curasi, Erin K Grey, Nitesh V Chawla, and David M Lodge. Network analysis of ballast-mediated species transfer reveals important introduction and dispersal patterns in the arctic Scientific reports, 10(1): 1-15, 2020b.
Mandana Saebi, Jian Xu, Erin K Grey, David Lodge, James Corbett, and Nitesh Chawla. Higher- order patterns of aquatic species spread through the global shipping network. Plos one, 15(7): c0220353, 2020c.
Mandana Saebi, Jian Xu, Lance M Kaplan, Bruno Ribeiro, and Nitesh V Chawla. Efficient modeling of higher-order dependencies in networks: from algorithm to application for anomaly detection. EPJ Data Science, 911):1,, 2020d.
11

---

Published as a conference paper at ICLR 2023
Thomas Schnake, Oliver Eberle, Jonas Lederer, Shinichi Nakajima, Kristof T Schutt, Klaus- Muelerr, and Gregoire Montavon. Higher-order explanations of graph neural networks via relevant walks. IEEE Transactions on Pattemn Analysis & Machine Intelligence, pp. 2021.
Ingo Scholtes. When is a network a network? In Proceedings of the 23rd ACM SIGKDD Interna- lional Conference on Knowledge Discovery and Data Mining, pp. 1037-1046. ACM, 2017.
Ingo Scholtes al. Causality-driven slow-down and speed-up of diffusion in non-markovian tem- poral networks. Nature communications, 5:5024, 2014.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint 18/00566 2018.
Mark D Spalding, Helen E Fox, Gerald R Allen, Nick Davidson, Zach A Ferdaña, MAX Finlayson, Benjamin S Halpern, Miguel A Jorge, AL Lombana, Sara A Lourie, et al. Marine ecoregions of the world: bioregionalization of coastal and shelf areas. BioScience, 57(7):573-583, 2007.
Hui Tang, Xun Liang, Bo Wu, Zhenyu Guan, Yuhui Guo, and Xiangping Zheng. Graph ensemble networks for semi-supervised embedding learning. In International Conference on Knowledge Science, Engineering and Management, pp. 408 420. Springer, 2021.
Leo Torres, Ann S Blevins, Danielle Bassett, and Tina Eliassi-Rad. The why, how, and when of representations for complex systems. SIAM Review, 63(3):435-485, 2021.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lio, and Yoshua
Bengio. Graph attention networks. International Conference on Learning Representations, 2018.
Daheng Wang, Meng Jiang. Munira Syed, Oliver Conway, Vishal Juneja, Sriram Subramanian, and Nitesh V Chawla. Calendar graph neural networks for modeling time structures in spatiotemporal user behaviors. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 2581-2589, 2020.
Abdul Wasay and Stratos Idreos. More or less: When and how to build convolutional neural network ensembles. In International Conference on Learning Representations, 2020.
Robert West, Joelle Pineau, and Doina Precup. Wikispeedia: An online game for inferring semantic distances between concepts. In Twenty-First International Joint Conference on Artificial Intelli- gence, 2009.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Yu Philip. A comprehensive survey graph neural networks. IEEE transactions neural networks and learning systems, 32(1):4-24, 2020.
Jian Xu, Thanuka L Wickramarathne, and Nitesh V Chawla. Representing higher-order dependen- cies in networks. Science advances, 2 2016.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference Learning Representations, 2019. URL https: / //openreview..o./m/m/// wwweenreieewnet//fooeee /tt/ reridddryGG633 ryGs6iA5Km.
Yang Yang, Ryan N Lichtenwalter, and Nitesh V Chawla. Evaluating link prediction methods. Knowledge and Information Systems, 45(3):751-782, 2015.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- saint: Graph sampling based inductive learning method. International Conference on Learning Representations, 2020.
Hanqing Zeng, Muhan Zhang, Yinglong Xia, Ajitesh Srivastava, Andrey Malevich, Rajgopal Kan- nan, Viktor Prasanna, Long Jin, and Ren Chen. Decoupling the depth and scope of graph neural networks. Advances in Neural Information Processing Systems, 34:19665-19679, 2021.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. Advances in neural information processing systems, 31, 2018.
12

---

Published as a conference paper at ICLR 2023
Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applica- tions. Al Open, 1:57-81, 2020.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, 33:7793- -804, 2020.
13


Reviews:
[{"review_id": "aoMIBhJyhM", "reviewer": "Reviewer_mus1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes an ensemble of GNNs that exploits variance in the neighborhood subspaces of nodes in graphs with higher-order dependencies and consistently outperforms baselines on semisupervised and supervised learning tasks.\n\nThe title and abstract looked interesting so I was expecting to see some interesting results, but the content is quite disappointing. The method/theory is too vague to be useful. Authors should answer my following concerns\n\n1. Just given a normal graph from arbitrary domains, what do you do?\n2. The conditional node, how do you decide if you want to condition?\n3. What's the benefit of condition? The similar argument doesn't make sense\n4. For regular gnn, how do you use ensemble to make them better?", "summary_of_the_review": "This paper proposes an ensemble of GNNs that exploits variance in the neighborhood subspaces of nodes in graphs with higher-order dependencies and consistently outperforms baselines on semisupervised and supervised learning tasks.\n\nThe title and abstract looked interesting so I was expecting to see some interesting results, but the content is quite disappointing. The method/theory is too vague to be useful. Authors should answer my following concerns\n\n1. Just given a normal graph from arbitrary domains, what do you do?\n2. The conditional node, how do you decide if you want to condition?\n3. What's the benefit of condition? The similar argument doesn't make sense\n4. For regular gnn, how do you use ensemble to make them better?", "strength_and_weaknesses": "Title and abstract looked interesting\n\n\n\n1. Just given a normal graph from arbitrary domains, what do you do?\n2. The conditional node, how do you decide if you want to condition?\n3. What's the benefit of condition? The similar argument doesn't make sense\n4. For regular gnn, how do you use ensemble to make them better?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "Sncm0SxerCd", "reviewer": "Reviewer_Ku1Z", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper discusses and proposed one ensemble method of GNN. The key idea is based on the high-order relationship of a target node. The proposed idea is relatively easy to understand and implement, which indicates that future researchers can easily generalize it. The proposed methods also outperform baselines.", "summary_of_the_review": "It's a good paper for me. The paper provides some insight and builds the connection between high-order relationships and ensemble methods. But I think more discussion is needed. Meanwhile, the experiment part only includes the 1-WL test model, which is not persuasive since it's obvious a higher-order relationship will have a better performance. Also, the runtime comparison may also show the advantage of the proposed model.", "strength_and_weaknesses": "The high-level idea is easy to understand, traditional GNN work can't handle the high-order relationship. In this work, the authors proposed a new ensemble method, which indicates that the aggregation of the target node's neighbor is a biased estimator of the aggregation of the target node. The proof is also technically sound. The paper also builds a connection between ensemble methods and GNN, which can be useful to large-scale graphs in future research.\n\nQuestions: \n\nActually, the high-order relationship (i.e., high-order WL test) has been discussed in many previous works. Previous work, e.g., [1], [2], and other works, both discuss the high-order relationship. These works already show better performance compared with the 1-WL model(e.g., GIN, GCN, ...). However, the problem is that we don't have enough computational resources for the higher-order relationship(since we need to sample a subgraph for a target node, which is both time and space consuming). Thus, I wonder does the sampling part in this paper share the same limitations. Or maybe it's more efficient/faster than other high-order WL test based models.\n\nAnother concern is the expression power of the proposed model. More discussion regarding the expression power will be appreciated. By far we only know that it's a biased estimator. \n\n[1] Link Prediction Based on Graph Neural Networks\n[2] Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "P2xF6kaW5w", "reviewer": "Reviewer_tGTJ", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposed Deep Graph Ensemble (DGE) to learn effective representations of higher-order networks (HONS). HON is the networks that encode sequential higher-order dependencies. The authors conduct node classification and link prediction to evaluate DGE in comparison to graph neural networks on six datasets.", "summary_of_the_review": "Overall, I am leaning towards rejection. My major concern is the novelty and the lack of comparison with related works. If you address my concerns, I will raise my score. ", "strength_and_weaknesses": "**Strengths**\n\n(1) This paper addresses interesting research topic : higher-order networks (HONs), which encoder sequential higher-order dependencies.\n\n**Weakness**\n\n(1) I think that the novelty of this paper is limited. The proposed method is similar to path-based graph neural networks (e.g., pathGCN [1]) or random-walk based graph neural networks (e.g., RAW-GNN [2]). \n\n(2) Also, the authors construct graph from the sequential data (paths) and then use GrowHON to construct HONs. I think HON seems very similar to paths (a sequence of nodes). Please clarify what the difference is between HON and paths.  \n\n(3) Since the input datasets used in experiments are sequential data, it would be better to compare proposed DGE with the model for representing sequential data. Also, more comparison with path-based graph neural networks such as pathGCN [1] have to be included.\n\n(4) Can you show qualitative analysis for DGE to verify why it is appropriate approach to deal with HON?\n\n---\n\n[1] Eliasof, Moshe, Eldad Haber, and Eran Treister. \"pathGCN: Learning General Graph Spatial Operators from Paths.\" ICML 2022.\n\n[2] Jin, Di, et al. \"RAW-GNN: RAndom Walk Aggregation based Graph Neural Network.\" IJCAI 2022.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "4Fn99CrqQe3", "reviewer": "Reviewer_3FqL", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this work, the authors propose Deep Graph Ensemble (DGE) to tackle the additional information available in higher order networks $-$ something which standard Message Passing GNNs methods are unable to process without loss of information. The authors propose to do this by leveraging an ensemble of standard MPNNs - which are used to solve the 3 design challenges associated with HONs  $-$ variable number of conditional nodes, different and potentially non-overlapping neighborhoods, and the importance of the nodes. The authors then present results of the DGE (with different aggregation strategies", "summary_of_the_review": "Unfortunately, in the current state , the weaknesses of the paper out weigh the strengths. However, I am happy to increase my scores if the authors can answer the questions appropriately.", "strength_and_weaknesses": "**Strengths:**\n1. The idea towards using GNNs to solve problem on HONs is interesting as well as identifying different ways to use the HON to construct the inputs for the GNNs\n2. Most sections of the paper are well written and clear\n\n**Weaknesses, corresponding suggestions and questions**\n1. Unfortunately, to the reader it appears like the work is present as the first work of using GNN's for higher order networks and has altogether missed relevant GNNs works on Higher order networks - both comparing against them  e.g. [1]. Please compare and contrast with this work - and other appropriate related works.\n2. The paragraph on total model size comparison is unclear and appears to be unfair as well. Firstly, why limit the number of GNN layers in the baseline GNN models? The provided image in Fig 4 is also hard to read - and appears like until the budget is increased considerably the baseline models appear to do better.  Moreover, it is unclear how to select the right number of GNNs ($l$) to be used in the ensemble - can this be written as a function of the graph statistics?.\n3. Standard GNNs are known to suffer in the link prediction task and are not representative baselines - as has been widely studied and documented. Please add comparison with a method such as [2]\n4. What happens if you perform simple GNN ensembling - same input graph for all GNNs in the ensemble - but with neighborhood sampling (using MEAN, POOL, etc) without using your proposed training procedure? How does this compare?\n\n**Minor:**\n1. A drawback of the proposed approach - from the results in the appendix - it appears like that the DGE takes longer to converge - in terms of epochs how big is the difference? Are these all with the same parameter budgets as well?\n2. DGE-pool and DGE-concat (Even without shared parameters) seems to perform worse than the baselines models in most cases - is there any reasoning for this? Please address this in Section 4.3\n\n**References:**\n1. Jin, Di, et al. \"Graph Neural Network for Higher-Order Dependency Networks.\" Proceedings of the ACM Web Conference 2022. 2022.\n2. Zhang, Muhan, and Yixin Chen. \"Link prediction based on graph neural networks.\" Advances in neural information processing systems 31 (2018).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster