Does your graph need a confidence boost?  Convergent boosted smoothing on graphs with tabular node features
Authors: Jiuhai Chen
Jonas Mueller
Vassilis N. Ioannidis
Soji Adeshina
Yangkun Wang
Tom Goldstein
David Wipf
Venue: ICLR 2022 Spotlight (2022)
Keywords: Graph Neural Network
Boosting
Node classification
Tabular Data

Abstract: Many practical modeling tasks require making predictions using tabular data composed of heterogeneous feature types (e.g., text-based, categorical, continuous, etc.).  In this setting boosted decision trees and related ensembling techniques generally dominate real-world applications involving iid training/test sets.  However, when there are relations between samples and the iid assumption is no longer reasonable, it remains unclear how to incorporate these dependencies within existing boosting pipelines.  To this end, we propose a generalized framework for combining boosted trees and more general model ensembling techniques, with graph propagation layers that share  node/sample information across edges connecting related samples.  And unlike previous efforts to integrate graph-based models with boosting, our approach is anchored to a principled meta loss function such that provable convergence can be guaranteed under relatively mild assumptions. Across a variety of benchmarks involving non-iid graph data with tabular node features, our framework achieves comparable or superior performance.

Published as a conference paper at ICLR 2022
DOES YOUR GRAPH NEED A CONFIDENCE BOOST? CONVERGENT BOOSTED SMOOTHING ON GRAPHS WITH TABULAR NODE FEATURES
Jiuhai Chen
Jonas Mueller & Vassilis N. loannidis Soji Adeshina
University of Maryland
Amazon
Yangkun Wang
Tom Goldstein University of Maryland
David Wipf Amazon
Shanghai Jiao Tong University
ABSTRACT
For supervised learning with tabular data, decision tree ensembles produced via boosting techniques generally dominate real-world applications involving iid train- ing/test sets. However for graph data where the iid assumption is violated due to structured relations between samples, it remains unclear how to best incorpo- rate this structure within existing boosting pipelines. To this end, we propose a generalized framework for iterating boosting with graph propagation steps that share node/sample information across edges connecting related samples. Unlike previous efforts to integrate graph-based models with boosting, our approach is anchored in principled meta loss function such that provable convergence can be guaranteed under relatively mild assumptions. Across a variety of non-iid graph datasets with tabular node features, our method achieves comparable or superior performance than both tabular and graph neural network models, as well as exist- ing hybrid strategies that combine the two. Beyond producing better predictive performance than recently proposed graph models, our proposed techniques are easy to implement, computationally more efficient, and enjoy stronger theoretical guarantees (which make our results more reproducible).
INTRODUCTION
Tabular data consists of observations stored as rows of a table, where multiple numetic/categorical features are recorded for each observation, one per column. Models for tabular data must learn to output accurate predictions solely from (potentially high-dimensional or sparse) sets of heterogeneous feature values. For learning from tabular data, ensembles of decision trees frequently rank on the top of model leaderboards, as they have proven to be highly performant when trained via multi-round boosting algorithms that progressively encourage the learner to focus more on "difficult" examples predicted inaccurately in earlier rounds (Bansal, 2018; Elsayed et al., 2021; Fakoor et al., 2020; Huang al., 2020b; Ke al., 2017; Prokhorenkova et al., 2018). Boosted trees thus form the cornerstone of supervised learning when rows of table are independent and identically distributed (iid).
However, the iid assumption is severely violated for graph structured data (Chami et al., 2020), in which nodes store features/labels that are highly correlated with those of their neighbors. Many methods have been proposed to account for the graph structure during learning, with graph neural neiworky (GNN) becoming immensely popular in recent years (Scarselli et al., 2008; Wang et al., 2019; Zhou al., 2020a). Despite their success, modern GNNs suffer from various issues (Alon Yahav, 2021; Oono & Suzuki, 2019): they are complex both in their implementation and the amount of required computation (Faber et al., 2021; Huang et al., 2020a; Shchur et al., 2018), and limited theoretical guarantees exist regarding their performance (Garg et al., 2020; Li & Cheng, 2021; Zhou et al., 2020b). Furthermore, the sample complexity of sophisticated GNN models and their ability handle rich node features may be worse than simpler models like those used for tabular data (Faber et al., 2021; Huang et al., 2020a; Shchur et al., 2018).
the convergence of their training
Work done during internship Amazon Web Services Shanghai AT Lab

---

Published as a conference paper at ICLR 2022
Graph datasets store tabular feature vectors, along with additional edge information. Despite the close relationship between graph and tabular data, there has been little work on how to adapt powerful boosting methods consider how to best leverage tabular models for non-iid node classification/eegression tasks in graphs. We focus settings where each node is associated with tabular (numericc/ctegorical) features æ and labels y. and the goal is to predict the labels of certain nodes. Straightforward application of tabular modeling (in which nodes are treated as iid examples) will produce learned mapping where training and inference are uninformed by how nodes are arranged in the graph.
sharpest tool for dissecting tabular data to account for edges. Here
To account for the graph structure, we introduce simple graph propagation operations into the defimition of a modified, non-iid boosting loss function, such that edge information can be exploited to improve model accuracy relative to classical alternatives (Friedman, 2001). We refer to the resulting algorithm as EBBS which stands for efficient bilevel boosted smoothing, whereby the end-to-end training of a bilevel loss such that values of the boosted base model f ebb and flow across the input graph producing smoothed predictor f. And unlike an existing adaptation of boosting for graph data (Ivanov& & Prokhorenkova, 2021), our approach is simpler (no GNN or other auxiliary model required), produces more accurate predictions on benchmark datasets, and enjoys reliable convergence guarantees.
BACKGROUND
Consider a graph G with set of vertices, i.c nodes, V & {ui, U2,..., vn. whose connectivity is described by the edge set & {(0), v2) V V}, where the tuple of nodes (v,, 21)) implies a relationship among e and uy. The edge set is represented by the adjacency matrix A = (aiz Inx E R=x" whose entry aig nonzero if (mi, w3) E E. node prediction tasks, each node o; associated with a feature vector æ; E Redo as well as label yı E RR that might hold discrete or continuous values (corresponding to classification or regression tasks). In certain cases we have access to the labels at only a subset of nodes (eee with L C V. Given iec the connectivity of the graph E, and the feature values of all nodes {ær Jiv, our task is predict the labels of the unlabeled nodes {y,) tukeeu with = VV C. the most straightforward application, a tabular model may simply be fit to dataset {(x; yz) hee, disregarding that the observations model is then independently applied to each x; for i E U. Of course this naive approach may fare poorly as it fails to leverage &, but we note that it empirically performs better than one might expect on certain graph datasets (where perhaps each æ; contains sufficiently rich information to infer the corresponding y, or nodes connected & only exhibit weak correlation in their features or labels) (Faber et al., 2021; Huang et al., 2020a; Ivanov & Prokhorenkova, 2021).
not iid. For prediction, the learned
2.1 GRADIENT BOOSTED DECISION TREES (GBDT)
GBDT represents a popular model for iid (non-graph) tabular data (Friedman, 2001), whereby remarkably accurate predictions are produced by ensemble of weak learners. Formally, at each iteration of boosting, the current ensemble model (z) is updated in an additive manner via
((+))()) f(0 (x) + ()) (t))
where 11(9) (a:) is a weaker learner selected from some candidate function space H (typically decision trees), and (+()) is the learning rate calculated with the aid of line search. The weak learner h(t)) e H is chosen to approximate the pseudo-residuals given by the negative gradient of some loss function & w.r.t the current model's predictions. This involves solving
m
ally,, (xx)) h h(x,) (x))
(t) arg min NEH
(1)
where {a;, y; 1m is a set of m training points. Decision trees are constructed by a recursive partition of feature space into Jr disjoint regions Rı..... RJ,, to minimize the loss function (1)
and predict constant value byt in each region Ry. The output of (z)())) can be written as the sum: 1110 Σ bR, (x), where 1 is the indicator notation. Many efficient GBDT implementations are available today (Ke et al., 2017; Prokhorenkova et al., 2018; Wen et al., 2019),
2

---

Published as a conference paper at ICLR 2022
and these models easily be trained for nonstandard prediction tasks via custom loss functions (Elsayed et al., 2021; Li et al., 2007; Velthoen et al., 2021).
2.2 PRIOR ATTEMPTS TO COMBINE BOOSTING WITH GRAPH NEURAL NETWORKS
The AdaGCN model from Sun et al. (2019) proposes a GNN architecture motivated by the structure of AdaBoost iterations; however, this approach is not actually designed to handle tabular data. More related to our work is the boosted graph neural network (BGNN) approach from Ivanov & Prokhorenkova (2021), which proposes novel architecture that jointly trains GBDT and GNN models. Within this framework, GBDT extracts predictive information from node features and the GNN accounts for the graph structure, achieving significant performance increase on various graph datasets with tabular features.
In the first iteration, BGNN builds a GBDT model ( (a) over the training node features that treated essentially as iid tabular data. Using all GBDT predictions, BGNN then concatenates these with the original node features and subsequently uses these as inputs GNN model. Next, the GNN is trained with / steps of gradient descent to optimize network parameters as well as the input node features themselves by hackpropagating gradients entirely through the GNN into input space. BGNN uses the difference between the optimized node features and input node features as new target value for the next decision tree in the subsequent boosting round. After GBDT has been updated with the addition of the new tree, it makes predictions that are used to augment the node features for subsequent use in the GNN, and the process repeats until some stopping criteria is met.
While BGNN has thus far demonstrated promising empirical results, there is guarantee of conver- gence or even cost function descent. Our EBBS model addresses this issue through fully integrated alternative described in Section 3, which enjoys convergence guarantees provided in Section 4. Be- sides its favorable analytical properties, EBBS naturally supports a suite of graph-based regularizers promoting different properties described in Section 3.4, empirically achieves higher accuracy, and is less prone to overfitting without careful hyperparamette--uniig since the graph is accounted for via a simple regularizer instead of an additional parameterized GNN model. Appendix B provides further discussion about the connection between EBBS and BGNN, highlighting key technical differences.
END-TO-END INTEGRATION OF GRAPH PROPAGATION AND BOOSTING
In this section describe our method for combining GBDT with graph-aware propagation layers. We first deseribe a general family of propagation layers that mimic gradient descent steps along a principled graph-regularized loss, followed by the derivation of bilevel optimization algorithm that exploits these layers. In terms of notation, we will henceforth use m, to reference the i-th row of an arbitrary matrix M.
3.1 GRAPH- AWARE PROPAGATION LAYERS INSPIRED BY GRADIENT DESCENT
Recently there has been surge of interest in GNN architectures with layers defined with respect to the minimization of a principled class of graph-regularized energy functions (Klicpera et al., 2018; Ma et al., 2020; Pan al., 2021; Yang et al., 2021; Zhang et al., 2020; Zhu et al., 2021). In this context, the basic idea is to associate each descent step along an optimization trajectory (e.g.. gradient descent step, power iteration. or related), with GNN layer, such that aggregate, the forward GNN pass can be viewed as minimization of the original energy. Hence GNN training can benefit from the inductive bias afforded by energy function minimizers (or close approximations thereof) whose specific form can be controlled by trainable parameters.
The most common instantiation of this framework, with roots in Zhou al. (2004), begins with the energy
Z Z
Z f (x: 0) + Atr Z LZ
where À is a trade-off parameter, Z E R is a learnable embedding of d-dimensional features across nodes, and (X; 0) denotes base model (parameterized by 0) that computes initial target embedding based on the dn-dimensional node features X E Xdo. We also define the graph Laplacian of G as L Raxa, meaning L D A, where D represents the degree matrix.
3

---

Published as a conference paper at ICLR 2022
Intuitively, solutions of (2) reflect balance between proximity f (X; (x:0 0) and minimal quadratic
differences across graph edges as enforced by the trace term tr 2 LZ Σ (iJtEE || و 2
more general regularization factors are considered Section 3.4. On the positive side, (2) can be solved in closed-form via
f (X:0) _ arg min (z( p (x;0), with P - A
Z
However, for large graphs the requisite inverse is not fracsically-eeasible to compute, and instead iterative approximations are preferable. To this end, we may initialize as Z (0) = (X; 0), and then proceed to iteratively descend in the direction of the negative gradient. Given that
(Z) 2 + 2Z - 2f (X:0),
(4)
az
the k-th iteration of gradient descent becomes
(h Z (k-1) a + 1) (1) :
(5)
where serves as the effective step size. Given that L is generally sparse, computation of (5) can leverage efficient sparse matrix multiplications, and we may also introduce modifications such as Jacobi preconditioning to speed convergence (Axelsson, 1996; Yang et al., 2021). Furthermore, based on well-known properties of gradient descent, l is sufficiently large and small enough, then
(x:0) 7 (X:0) & p [f (x:0)),
where the operator p()) (.) computes gradient steps via (5). The structure of these propagation steps, as well as related variants based on normalized modifications of gradient descent, equate to principled GNN layers, such as those used by GCN (Kipf & Welling, 2016), APPNP (Kliepera et al., 2018), and many others, which can be trained within broader bilevel optimization framework as described next.
3.2 FROM GRAPH-AWARE PROPAGATION TO BILEVEL OPTIMIZATION
Given that the updated embeddings f(() (X; 0) represent graph regularized version of the base estimator f (X; O), we obtain a natural candidate predictor for application to downstream tasks such node classification. Of course this presupposes that the parameters A can be suitably trained, particularly in an end-to-end manner that accounts for the propagation operator p(k) To this end, we can insert f(() (X;0) within an application meta-loss given by
D Σ
m7
(x:0)] y3.)
where g IRd + R is some differentiable node-wise function, possibly an identity mapping, with c-dimensional output. Additionally, f(() (X:0); is the i-th row of f(() (X: f), m < n is the number of labeled nodes and D is some discriminator function, c.g., cross-entropy for classification, squared error for regression. We may then optimize efa (0) over θ to obtain our final predictive model.
In prior work (Klicpera et al., 2018; Ma et al., 2020; Pan et al., 2021; Yang et al., 2021; Zhang et al., 2020; Zhu et al., 2021), 1), this type of bilevel optimization framework has been adopted to either unify and explain existing GNN models, or motivate alternatives by varying the structure of p(k) However, in all cases date that we are aware of, has been assumed that f (X: 0) is differentiable, typically either a linear function or an MLP. Hence because p(k) is also differentiable, e (0) /00 can be computed to facilitate end-to-end training via stochastic gradient descent (SGD). In contrast, to accommodate tabular data, we instead choose to define f (X; 0) via decision trees such that SGD is no longer viable. Consequently, we turn to gradient boosting as outlined next.
3.3 BILEVEL BOOSTING
Let (99) denote the gradient boosting parameters that have accumulated through iteration such that
f(X; o())) represents the weighted summation of weak learners from 1,...,4. L. We also assume that
4

---

Published as a conference paper at ICLR 2022
f(X: is separable across nodes, i.e. rows of X, such that (with some abuse of notation w.r.t. the domain f) we have f(X; ) f(a;; (()). The next gradient boosting iteration proceeds by computing the function-space gradient R(!)
(0()) 05(x;000
a (0 of ( 0(0)
aP(h)
[ (x:0())
l:m
0f(k) (x; (x:00) 0(0) 05(X;
af(a) (X; 0(0))
0f (x;
where p(k) [ (x:0())
refers to the first m rows of p(k) [
x00 For illustration
1:m
purposes, consider the special case where D is the squared enror and is identity operator, in which case (8) reduces to
7(h) (x:0 - v.) 0p(() [ (x: (x:0
R = 2
(9)
0f xx (x:
which as - oc, will simplify to
(x((x -v:) (wi) RD = 2 Σ
(10)
This can be viewed as graph-aware, smoothed version of the pseudo-residuals obtained from standard gradient boosting applied to the squared-error loss. Next, we fit the best weak learner to approximate these gradients by minimizing the quadratic loss
h (1) arg min MEH
p h(x;) Σ
(1I)
over all nodes n. Note that unlike in the canonical gradient boosting setting where function-space gradients are only needed over the training samples, for EBBS we must fit the weak-learners to gradients from both the training and lest nodes." This is because graph propagation allows the base predictor from test node to influence the smoothed prediction applied to the labeled training nodes. Finally, we update the base predictor model by adding a new weak learner ((() via
((=t)))))))) = ((x; 0(1) + (0.))) Vi I...., n.
(12)
where (9()) is the learning rate chosen by line search and (++1) fort) ,100, 1,0, The iterative steps of EBBS are summarized in Algorithm 1.
Algorithm 1: Efficient Bilevel Boosted Smoothing (EBBS)
Input: Feature matrix {X} and target {y,} (i=l....m);
Initialize fXx (()) = 0
for i 0, 7" do Propagate over the graph compute F(t) (x; (00) via (6);
Compute the function-space gradient (pseudo-residual) ( using (8);
Execute (11) to find the best weak-learner h(();
Update the new base model [(X; ((;0((++)) via (12)
end
Output: 0
'This is also one of the key differences between EBBS and BGNN, in that the latter does not fit the gradients that originate from test nodes; see supplementary for details.
5

---

Published as a conference paper at ICLR 2022
3.4 BROADER FORMS OF PROPAGATION
Kernelized EBBS. Kernel methods have powered traditional machine learning by modeling nonlin- ear relations among data points by (implicitly) mapping them high-dimensional space (Schölkopf & Smola, 2002). Laplacian kernels constitute the graph counterpart of popular cranslaion-invariann kernels in Euclidean space (Smola & Kondor, 2003). The Laplacian kernel matrix is defined as K := r (L). where denotes the psedoinverse, and the choice of matrix-valuuee function r(-) deter- mines which kernel being used (and which properties of node features are being promoted (Ioannidis et al., 2018)). With a chosen Laplacian kernel, the objective in (2) can be rewritten more generally as
Ez _ 2 - f (x:0)1 + Atr ZT k'
(13)
This allows EBBS utilize more flexible regularizers than (2), such as the diffusion kernel (Smola Kondor, 2003), where matrix inversion can be avoided by noticing that tr| tr[ K Z] tr| Z r r(L) Z.] EBBS (Algorithm 1) can thus be applied with any positive semi-definite graph kernel and our subsequent convergence results (Theorem 1) will still hold.
Adaptations for Heterophily Graphs. For heterophily graphs (Zhu et al., 2020a;b), quadratic regularization may be overly sensitive to spurious edges, so we can adopt more general energy functions of the form
Ez - Z (x:00
E p (11:- 1 25112)
(14)
(.EEE
as proposed in Yang et al. (2021). In this expression IR+ + R is some potentially nonlinear function, typically chosen be concave and non-decreasing so as to contribute robustness w.r.t edge uncertainty. The resulting operator p()) can then be derived using iterative reweighted least squares, which results in principled form of graph attention.
Label-Aware Error Smoothing. Huang et al. (2020a) have shown that the prediction errors of a fixed MIP (or related model) can be smoothed via a regularized loss similar to (2), and this produces competitive node classification accuracy. The key difference is to replace the base model f(X;; 0) in (2) with the error E A M @ (Y -((X;)) 8), where Y E Rxee is a matrix of labels and M is a mask with i-th row equal ones if 22 L and zero otherwise. The optimal revised solution of (2) then becomes p* E analogous (3), with efficient approximation p(*) [E] that spreads the original errors across graph edges. To update the final predictions, this smoothed error is added back to the original base model leading to the final smoothed estimator
f(x:0) = f( + p(() [M O (Y - (():
(15)
While Huang et al. (2020a) treat this estimator fixed postprocessing step, it can actually be plugged into a meta-loss for end-to-end EBBS optimization just as before (per the analysis in Section 3.2 and the differentiability of (15) w.r.t f). Although potential limitation of this strategy is that the label dependency could increase the risk of overfitting, various counter-measures can be introduced to mitigate this effect (Wang et al., 2021). Moreover, this approach cannot be extended inductive (or unsupervised) settings where no labels are available at test time.
4 CONVERGENCE ANALYSIS OF EBBS
We next consider the convergence of Algorithm 1 given that generally speaking, methods with guaranteed convergence tend to be more reliable, reproducible, and computationally efficient. Let
fg (0) denote the loss from (7) with p()) set to p' such that f(8) becomes f (i.e., as k + do with sufficiently small). We further define the optimal boosting parameters applied to this loss as
0" arg min Eg (0), A
(16)
where θ denotes the space of possible parameterizations as determined by the associated family of weak learners H. In analyzing the convergence of EBBS, we seek to bound the gap between the value
of the ideal loss ég (0"), and the approximation ((()) that is actually achievable for finite values of l and t. In doing so, we must account for the interplay between three factors:

---

Published as a conference paper at ICLR 2022
1. The embedding-space gradients from the lower-level loss Eg (Z) that form p(k)
2. The higher-level function-space gradients Rd that are endemic to any GBDT-based method, but that in our situation uniquely depend both training and test samples because of the graph propagation operator p(k)
3. The approximation error introduced by the limited capacity of each weak learner that is tasked with fitting the aforementioned function-space gradients.
We explicitly account for these factors via the following result, which establishes convergence guarantees w.r.t. both k and f. Note that to enhance the convergence rate w.r.t. I, we apply Nesterov's acceleration method (Nesterov, 2003) to each boosting iteration as proposed in Lu al. (2020).
Theorem 1. Let D v) u v12 g(u) u. and || + I|/2 in the loss from (7). Then for all 2 0 and 2 O, there exists a constant I E (0, 1] and с > such that the iterations of Algorithm auugmetted with the momentum factor from Lu el al. (2020) and associated momentum parameter @ 5 4412. satisfy
f (00 (o())) S O + e
(17)
The proof, which builds upon ideas from Lu & Mazumder (2020), is deferred to the supplementary. Remark 1. The quantity represents what referred to as the minimum cosine angle or MCA (as proposed in Lu et al. (2020) and modified in Lu & Mazumder (2020)), which relates to the minimum angle between any candidate residual and the best-fitting weak learner. For example, for strong learners the MCA will be near one, and we can execute near exact gradient descent in functional space. Please see supplementary for further details.
Remark 2. While Theorem I is currently predicted on a quadratic meta-loss, this result can likely be extended to other convex (but not necessarily strongly convex) alternatives, albeit with possibly weaker convergence rates. In contrast, BGNN is predicated on a highly-nonconver GNN-based loss, and similar convergence guarantees are unlikely to exist. This is especially true given that the function-spe spacee gradients used by BGNN are only computed on the training set, such that there is no assurance that each boosting step will not increase the final loss. More specifically, the perturbation of test point embeddings that feed into the subsequent GNN layers (as introduced with each BGNN boosting iteration) is not taken into account. Please see the supplementary for further details regarding the differences between BGNN and EBBS.
Remark 3. Theorem 1 also holds when the meta-loss from (7) defined w.r.t any positive semi- definite kernel from Section 3.4 or the predictor from (15). . In contrast, the situation is more nuanced when applying a nonconvex regularizer as in (14) (see supplementary for further details).
Corollary 1. Let D(u, v) = 1llu-lll --e g(u) u. || in the loss from (7). Additionally, a penalty factor (X 0) is added to (7). Then for all k 2 0 and t 2 0, there exists a constant
-
[0, 1) and >> O such that the iterations of Algorithm I are such that
c (0') e/ (0
I <0(3* cc
(18)
Remark 4. The quantity B is related to the density week learners in the function space of predictors and the property of bilevel loss (7). In particular, Lu & Mazunder (2020), is finite value related to the largest singular value of P. which can be found in supplementury.
: where I is the MCA as defined in
EXPERIMENTS
This section describes the datasets, baseline models and experimental details, followed by comparative empirical results.
Setup. To study the empirical effectiveness of our methods, we apply them in numerous node regression and classification tasks and compare with various tabular and GNN models. Generally, which class of method fares best will depend on the particular properties of a graph dataset (Faber al., 2021; Huang et al., 2020a). Our benchmarks specifically focus on graph datasets with rich
7

---

Published as a conference paper at ICLR 2022
Regression
Classification
Method
House
County
VK
Avazu
Slap
DBLP
CS
Phy
GAT
0.54
1.45
7.22
0.1134
80.1
80.2
91.6
95.4
GCN
0.63
1.48
7.25
0.1141
87.8
42.8
92.3
95.4
AGNN
0.59
1.45
7.26
0.1134
89.2
79.4
92.7
96.9
APPNP
0.69
1.50
13.23
0.1127
89.5
83.0
93.2
96.6
CatBoost
0.63
1.39
7.16
0.1172
96.3
91.3
91.9
94.6
CalBoost+
0.54
1.25
6.96
0.1083
96.2
90.7
94.6
96.4
BGNN
0.50
1.26
6.95
0,1090
95.0
88.9
92.5
96.4
EBBS (ours)
0,45
1.11
6.90
0.1062
96.3
91.3
94.9
96.9
Table 1: Root mean squared error (RMSE) of different methods for node regression; accuracy (%) of different methods for node classification. Top results are boldfaced, all of which are statistically significant. Please see supplementary for standard errors and further details, as well as Figure I below. Additionally, the BGNN model results are based on conducting separate hyperparameter sweep for every data set and every random seed. In contrast, EBBS results are based on fixed parameters across random seeds and are mostly shared across datasets.
node features, which entail an important class of applications. For node regression, we consider four real-word graph datasets adopted from Ivanov & Prokhorenkova (2021): House, County, VK, and Avazu, with different types of data for node features. For node classification, we consider two more datasets from Ivanov & Prokhorenkova (2021), 1): SLAP and DBLP, which stem from heterogencous information networks (HIN), We also consider the Coauthor-CS and Coauthor-Phy datasets (Shchur et al., 2018), which are from the KDD Cup 2016 challenge and based on the Microsoft Academic Graph. We chose these because they involve relatively large graphs with original sparse features, as opposed to low-dimensional projections (e.g. of originally text features) that are often better handled with just regular MI b-seed GNNs related.2 2 For contrast though, we also include OGB-ArXiv (Hu et al., 2020) with low-dimensional homogeneous node features favorable to GNNs.
We compare our proposed methods against various alternatives, starting with purely tabular baselines in which the graph structure is ignored and models are fit to node features as if they were iid. Here we consider CatBoost, a high- performarfo GBDT implementation with sophisticated strategies for handling categorical features and avoiding overfitting (Prokborenkova et al., 2018). We also evaluate popular GNN models: GCN (Kipf & Welling, 2016), GAT (Veličković et al., 2017), AGNN (Thekumparampil et al., 2018) and APPNP (Kliepera et al., 2018). Finally, we compare against the hybrid approach, BGNN (Ivanov & Prokhorenkova, 2021), 1), which combines GBDT and GNN architectures for
via end-to-end training and represents the current SOTA for poosting-plus-tabiie graph data. Our specific GBDT implementation of EBBS is based on top of CatBoost, where we interleave the boosting rounds of CatBoost with proposed propagation steps that define the effective loss used for training. The supplementary contains comprehensive details about our datasets, models/hhperppaamnttrss, and overall experimental setup.
1.5
Cathoott
Cardozak
BOWN
LEGS
OGB-ArXiv
1.4
Method
MLP
CatBoost
BGNN
EBBS
SOTA
1.3
Accuracy
55.50
51.0
67.0
70.10
74.31
1.2
Table Accuracy results on the OGB-ArXiv dataset. As mentioned in the text, the OGB- ArXiv node features are not generally favorable to boosted tree models. SOTA is taken from the OGB leaderboard.
11
Figure 1: RMSE v.s. random seed for County
dataset.
Results. In Table I we present the results for the various node regression and node classification benchmarks. Here EBBS outperforms various baselines across datasets. The baseline GNN models are all clearly challenged by the tabular features in these datasets, with the exception of Coauthor-CS and Coauthor-Phy where GNNs perform reasonably well as expected.
Atthoug tabular graph data for node classification is avaely-a in industry, unfortunately there is currently little aubicly-available. real-world data that can be used for benchmarking.
8

---

Published as a conference paper at ICLR 2022
BGNN
FBBS
10
20
30
40
50
10
20
30
40
50
teration
Figure 2:
Performance BGNN vs. EBBS after each boosting iteration on the VK dataset. Each model uses the hyperparameter values that performed best on the County dataset.
Importantly, all bold-faced results reported in Table 1 are significant once we properly account for the trial-to-trial variability induced by the random training splits shared across all methods; see supplementary for full presentation of standard errors and related analysis. Briefly here, for classification results, bold-faced results are statistically significant with respect to standard errors. In contrast, for node regression the standard errors for some datasets are bit larger relative to the EBBS improvement gap, but this turns out to spurious artifact of the shared trial-to-trial variance. More specifically, EBBS actually outperforms all other methods across all trials on all regression benchmarks, such that a stable performance gap is maintained even while the absolute RMSE of methods may vary for different training splits. While full details are deferred to the supplementary. in Figure we plot the RMSE for five random splits of the County dataset, observing that EBBS outperforms the other baselines across every instance.
Additionally, as a natural ablation of our end-to-end bilevel boosting model, we consider fitting GBDT in the usual fashion (to just the node features without edge information) and subsequently applying EBBS-like graph propagation post hoc, only after all GBDT boosting rounds have already finished. We refer to this approach CatBoost+, which be viewed EBBS without end-to-end training. Table and Figure 1 show that our EBBS bilevel boosting, with propagation interleaved inside each boosting round, outperforms post-hoc application of the same propagation the end of boosting. This is not true however for BGNN, which in aggregate performs similarly to CatBoostt.
Note also that for SLAP and DBLP, BGNN worse than CatBoost, likely because the graph structure is not sufficiently helpful for these data, which also explains why most GNN baselines perform relatively poorly. Nonetheless, EBBS still achieves comparable results with CatBoost, revealing that it may be more robust to non-ideal use cases. Additionally, for Coauthor-CS and Coauthor-Phy we observe that EBBS produces competitive results supporting the potential favorability of EBBS relative to GNN models when applied to certain graphs with high dimensional and sparse node features.
Proceeding further, given that the OGB-ArXiv node features are homogeneous, low-dimensional embeddings of an original text-based source, which are not generally well-suited for GBDT models, we would not expect BGNN or EBBS to match the SOTA achievable by GNNs. This conjecture is supported by the superiority of the MLP baseline over CatBoost in Table 2. Even so, observe that EBBS still more robust relative to BGNN in this setting. Finally, to showcase the relative stability of EBBS relative BGNN, we store the model hyperparameters that performed best on the County dataset and then trained the respective models on VK data. The resulting training curves are shown in Figure where BGNN exhibits some degree of relative instability. This suggests that in new application domains it may conceivably be easier to adapt EBBS models.
6 DISCUSSION
This paper considered various forms of graph propagation to facilitate the application of tabular modeling to node prediction tasks graph-structured data. We developed a simple yet highly accurate model by interleaving propagation steps with boosting rounds in GBDT. And unlike BGNN, which relies on separate boosting and GNN training steps with no unified loss, our method fully integrates graph propagation within the actual definition of single bi-level boosting objective. This allows us to establish converge guarantees and avoids the complexity of separate trainable GBDT and GNN modules. Note also that our EBBS algorithm is not specific to GBDT, but also be used boost arbitrary weak learners including neural networks (Cortes et al., 2017) or heterogeneous collections (Parnell al., 2020).

---

Published as a conference paper at ICLR 2022
REFERENCES
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations, 2021.
Owe Axelsson. Iterative Solution Methods. Cambridge University Press, 1996.
Shivam Bansal. Data science trends kaggle. https://www. kaggle com/ /s/sshiii vamb
data-aca sc cecinenc-teende on--ooo----- kagkaagglee.o 1445. vas
2018.
Ines Chami, Sami Abu-El-Haija, Bryan Perozzi, Christopher Ré, and Kevin Murphy. Machine learning on graphs: model and comprehensive taxonomy. arXiv preprint arXiv:2005.03675 2020.
Corinna Cortes, Xavier Gonzalvo, Vitaly Kuznetsov, Mehryar Mohri, and Scott Yang. Adanet: adaptive structural learning of artificial neural networks. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 874-883, 2017.
Shereen Elsayed, Daniela Thyssens, Ahmed Rashed, Lars Schmidt-Thieme, and Hadi Samer Jo- maa. Do we really need deep learning models for time series forecasting? arXiv preprint arXiv:2101.02118, 2021.
Lukas Faber, Yifan Lu, and Roger Wattenhofer. Should graph neural networks use features, edges, or both? arXiv preprint arXiv:2103.068855 2021.
Rasool Fakoor, Jonas W Mueller, Nick Erickson, Pratik Chaudhari, and Alexander Smola. Fast, accurate, and simple models for tabular data via augmented distillation. Advances in Neural Information Processing Systems, 33, 2020.
Jerome H Friedman. Greedy function approximation: a gradient boosting machine. Annals of statistics, pp. 1189-1232, 2001.
Vikas Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. In International Conference Machine Learning, pp. 3419-3430. PMLR, 2020.
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. arXiv preprint arXiv:2005.00687 2020.
Qian Huang, Horace He, Abhay Singh. Ser-Nam Lim, and Austin Benson. Combining label propa- gation and simple models out-performs graph neural networks. arXiv preprint arXiv:2010.1399 2020a.
Xin Huang, Ashish Khetan, Milan Cvitkovic, and Zohar Karnin. Tabtransformer: Tabular data modeling using contextual embeddings. arXiv preprint arXiv:2012.06668, 2020b.
V. loannidis, M. Ma, A. Nikolakopoulos, G. B. Giannakis, and D. Romero. Kernel-based inference of functions on graphs. Comminiello and J. Principe (eds.), Adaptive Learning Methods for Nonlinear System Modeling. Elsevier, 2018.
Sergei Ivanov and Liudmila Prokhorenkova. Boost then convolve: Gradient boosting meets graph neural networks. arXiv preprint arXiv:2101.086 2021.
Guolin Ke, Meng, Thomas Finley, Taifeng Wang, Wei Chen, Weidong Ma, Qiwei Ye, and Tie- Yan Liu. LightGBM: A highly efficient gradient boosting decision tree. In Advances in Neural Information Processing Systems, 2017.
Thomas Kipf and Max Welling, Semi-supervised classification with graph convolutional networks.
arXiv preprint 11V.:066900290., 2016.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph
neural networks meet personalized pagerank. arXiv preprint 18 2018.
10

---

Published as a conference paper at ICLR 2022
Ping Li, Qiang Wu, and Christopher Burges. Mcrank: Learning to rank using multiple classification and gradient boosting. Advances in neural information processing systems, 20:897-904 2007.
Xue Li and Yuanzhi Cheng. Understanding the message passing in graph neural networks via power iteration clustering. Neural Networks, 140:130- 100:130-13,, 2021.
Haihao Lu and Rahul Mazumder. Randomized gradient boosting machine. SIAM Journal on
Optimization, 3064):2780-2888, 2020.
Haihao Lu, Sai Praneeth Karimireddy, Natalia Ponomareva, and Vahab Mirrokni. Accelerating
gradient boosting machines. International Conference on Artificial Intelligence and Statistics, pp. 516-526. PMLR, 2020.
Yao Ma, Xiaorui Liu, Tong Zhao, Yozen Liu, Jiliang Tang, and Neil Shah. A unified view on graph neural networks as graph signal denoising, arXiv preprint arXiv:2010.01777, 2020.
Yurii Nesterov. Introductory lectures convex optimization: A basic course, volume 87. Springer Science & Business Media, 2003.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. arXiv preprint 1905, 10947, 2019.
Xuran Pan, Shiji Song, and Gao Huang. A unified framework for convolution-basse graph neural networks, 2021. URL https: opwnrevieww net/ forum? ?iduumiddiii 2edzz=uUMM UMD -- Fb9Bt.
Thomas Parnell, Andreea Anghel, Malgorzata Lazuka, Nikolas Ioannou, Sebastian Kurella, Peshal Agarwal, Nikolaos Papandreou, and Haralampos Pozidis. Snapboost: A heterogeneous boosting machine. Advances in Neural Information Processing Systems, 33, 2020.
Liudmila Prokhorenkova, Gleb Gusev, Aleksandr Vorobev, Anna Veronika Dorogush, and Andrey Gulin. CatBoost: unbiased boosting with categorical features. In Advances in Neural Information Processing Systems, 2018.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61-80) 2008
B. Schölkopf and A. J. Smola. Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. MIT Press, 2002.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint arXiv:1811.05880 2018
A. J. Smola and R. I. Kondor. Kernels and regularization on graphs. Learning Theory and Kernel Machines, pp. 144 158. Springer, 2003.
Ke Sun, Zhanxing Zhu, and Zhouchen Lin. Adagen: Adaboosting graph convolutional networks into deep models. arXiv preprint arXiv: 17Xiv:1908.05081, 2019.
Kiran K TTekumpprampil, Chong Wang, Sewoong Oh, and Li-Jia Li. Attention-based graph neural network for semi-supervised learning. arXiv preprint arXiv: 2018.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 10903, 2017.
Jasper Velthoen, Clément Dombry, Juan-Juan Cai, and Sebastian Engelke. Gradient boosting for extreme quantile regression. arXiv preprint Stt:::2003000000 2021.
Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, et al. Deep graph library: A graph-centric, highly-performant package for graph neural networks. arXiv preprint arXiv:1909.013:1 2019.
Yangkun Wang, Jiarui Jin, Weinan Zhang, Yong Yu, Zheng Zhang, and David Wipf. Bag of tricks for node classification with graph neural networks. arXiv preprint arXiv:2 133513355, 2021.
11

---

Published as a conference paper at ICLR 2022
Zeyi Wen, Jiashuai Shi, Bingsheng He, Jian Chen, Kotagiri Ramamohanarao, and Qinbin Li. Exploit- ing gpus for efficient gradient boosting decision tree training. IEEE Transactions on Parallel and Distributed Systems, 30(12):27062171 2717,, 2019.
Yongyi Yang, Tang Liu, Yangkun Wang, Jinjing Zhou, Quan Gan, Zhewei Wei, Zheng Zhang, Zengfeng Huang, and David Wipf. Graph neural networks inspired by classical iterative algorithms. arXiv preprint arXiv:2103.066 03.006644, 2021.
Hongwei Zhang, Tijin Yan, Zenjun Xie, Yuanqing Xia, and Yuan Zhang. Revisiting graph convolu- tional network on semi-supervised node classification from an optimization perspective. arXiv preprint arXiv:2009. 1 11469, 2020.
Dengyong Zhou, Olivier Bousquet, Thomas Navin Lal, Jason Weston, and Bernhard Schölkopf. Learning with local and global consistency. Advances in Neural Information Processing Systems, 2004.
Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: review of methods and applications. Al Open, 1:57-81, 2020a.
Kuangqi Zhou, Yanfei Dong, Kaixin Wang, Wee Sun Lee, Bryan Hooi, Huan Xu, and Jiashi Feng. Understanding and resolving performance degradation graph convolutional networks. arXiv preprint ar Xiix:0066007107 2020b.
Jiong Zhu, Ryan A Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K Ahmed, and Danai Koutra. Graph neural networks with heterophily. arXiv preprint arXiv:2009. 13566, 2020a.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. In Advances in Neural Information Processing Systems, NeurlPS, 2020b.
Meiqi Zhu, Xiao Wang, Chuan Shi, Houye Ji, and Peng Cui. Interpreting and unifying graph neural networks with an optimization framework. arXiv preprint arXiv:2101.11855 2021.
12

---

Supplementary Materials
A ASSESSING STATISTICAL SIGNIFICANCE OF RESULTS
Table SI shows the mean squared error of different methods for node regression with error bars. While the gains of EBBS may appears insignificant relative to the emror bars, this is not actually the case upon closer inspection. Because we used shared training and testing splits for different methods, compare how much of this variance is merely caused by different splits while the relative performance is preserved. We would like to point out that the error bars shown in Table S1 merely reflect shared trial-to-trial variability that does not significantly influence relative performance. To this end, below we present the results of each trial for all datasets. For each random seed, we use the fixed training and testing split and show the performance for different methods. From Table S2, we observe that EBBS outperforms BGNN across every instance. Regarding the classification task shown in Table S3, EBBS outperforms BGNN by a significant amount even if we take into account the reported error bars.
Regression
Method
House
County
VK
Avazu
GAT
0.54 0.01
1.45 + 0.06
7.22 + 0.29
0.1134 + 0.01
GCN
0.63 + 0.01
1.48 0.08
7.25 0.19
0.1141 0.02
AGNN
0.59 = 0.01
1.45 + 0.08
7.26 0.20
0.1134 + 0.02
APPNP
0.69 = 0.01
1.50 0.11
13.23 + 0.12
0.1127 = 0.01
CatBoost
0.63 = 0.01
1.39 + 0.07
7.16 + 0.20
0.1172 + 0.02
CatBoost+
0.54 = 0.01
1.25 0.11
6.96 0.21
0.1083 + 0.02
BGNN
0.50 - 0.01
1.26 0.08
6.95 0.21
0.1090 0.01
EBBS (ours)
0.45 = 0.01
1.11 + 0.09
6.90 + 0.23
0.1062 = 0.01
Table S1: Mean squared error of different methods for node regression. Top results are boldfaced.
B ANALYSIS OF THE DIFFERENCES BETWEEN EBBS AND BGNN
Although EBBS is clearly quite related to BGNN as discussed in the main text, there remain significant differences as follows:
Integrated Loss: EBBS integrates both the boosting module and graph propagation within single unified bi-level objective function, which allows for meaningful convergence guarantees. In contrast, the BGNN boosting rounds are not actually minimizing unified objective function (due to changing GNN parameters each round), which restricts the possibility of convergence guarantees. In BGNN, trainable module stacked on top of GBDT, and both the GNN and GBDT are updated with their respective losses by iterating back-and-forth during training. In contrast, the EBBS setup is different, with only single unchanging GBDTTbbase objective involved at a high level. In fact, we can view even the EBBS graph propagation step as being fully integrated within the actual definition of a single static GBDT training objective. To illustrate this more explicitly, the EBBS objective from
the GNN is treated
172
D
X (x;0), B.).
(19)
is equivalent to plugging parameterized GBDT predictive model into the fixed training loss. There is no need to iterate back-and-fore between adding weak learners to f(X; 0) and separate GNN parameter updates because all trainable parameters are inside of the function f(X; 0), and standard gradient boosting can be used with the above loss. Of course as we know, standard gradient boosting iterations involve fitting function space gradients using quadratic loss, which is exactly (11) in our paper. And while of course (11) keeps changing as the gradients change, the objective (19) upon which these gradients based does not. If we reinterpret BGNN from a similar perspective, then

---

Published as a conference paper at ICLR 2022
Regression
Dataset
Method
Seed 1
Seed
Seed 3
Seed 4
Seed 5
CatBoost CatBoost+
0.62
0.63
0.62
0.63
0.64
0.53
0.55
0,53
0.54
0.56
House
BGNN
0.49
0.51
0.49
0.52
0.50
EBBS
0.44
0.46
0.44
0.46
0.46
CatBoost
1.38
1.53
1.30
1.39
1.36
CatBoost+
1.26
1.45
1.16
1.21
1.14
County
BGNN EBBS
1.28
1.43
1.26
1.17
1.19
1.11
1.28
1.09
1.05
1.03
CatBoost
7.13
7.29
7.48
7.20
6.84
CatBoost+
6.88
7.07
7.24
7.01
6.60
VK
BGNN
6.90
7.05
7.26
6.98
6.60
EBBS
6.82
7.01
7.21
6.92
6.54
CatBoost
0.1046
0.1057
0.1133
0.1515
0.1111
Avazu
CatBoost+
0.0970
0.0992
0.1057
0.1400
0.0998
BGNN
0.0979
0.0992
0.1082
0.1332 0.1331
0.0999
EBBS
0.0967
0.0990
0.1045
0.0979
Table S2: Mean squared error of different methods for different random seeds, which presents different training and testing splits. Top results boldfaced.
Classification
Method
Slap
DBLP
Coauthor- CS
Coauthor-Phr
GAT
80.1 1.0
80.2 + 1.0
91.55 + 0.5
95.4 + 0.1
GCN
87.8 1.0
42.8 4.0
92.32 + 0.4
95.4 0.1
AGNN
89.2 1.0
79.4
1.0
92.65 +
96.9 0.1
APPNP
89.5 + 1.0
83.0 + 2.0
93.2 + 0.1
96.6 + 0.2
CatBoost
96.3 0.0
91.3
1.0
91.9 0,2
CatBoost+
96.2 - 0.3
90.7 4 1.1
94.6 + 0.1
96.4 1 0.1
BGNN
95.0 0.0
88.9 1.0
92.5 0.2
96.4 0.0
EBBS (ours)
96.3 0.4
91.3 0.6
94.9 0.2
96.9
Table S3: Accuracy (%) of different methods for node classification. Top results are boldfaced.
each time the GNN parameters updated, the implicit loss by the BGNN boosting step, analogous to (19) above, would change.
Incorporating Test Nodes During Training: a second key difference is the fact that in BGNN, input features of nodes in the test set are only used to predict test node labels for passage to the GNN; they not used to approximate gradients/residuals evaluated testing nodes during the selection of GBDT weak learners. contrast, the GBDT objective function in EBBS itself explicitly depends on test node input features because these features propagate over the graph to influence training node predictions as defined via (19). When training our EBBS model, gradient information from test nodes (or least those receiving significant signal) must be passed back to the boosting module. Or stated differently, unlike standard boosting as applied to iid training samples, we must predict function -pacionn-ppceeeeeeee gradients/residuals across all nodes when adding each new weak learner. This because the input to the propagation operator (k)) includes features from all nodes (both training and testing), and why (11) involves summation over all testing nodes, not just the training nodes.
Impact of Multiple SGD Steps: During each round of BGNN training, multiple SGD steps applied to both update GNN parameters and GNN inputs (whereas there is no similar operation in EBBS). These multiple inner iterations, while needed for GNN training and the presented empirical
14

---

Published as a conference paper at ICLR 2022
Regression
Method
House
County
VK
Avazu
BGNN
0.50 + 0.01
1.26 0.08
6.95
0.21
0.1090 + 0.01
BGNN(1 SGD step per iter.)
0,56 + 0.01
1.34 = 0.09
7.28
+ 0.23
0.110 + 0.02
BGNN(no end-to-end train)
0.51 + 0.01
1.33 4 0.08
7.07 + 0.20
0.1095 + 0.01
Table S4: Ablation study for BGNN with one step of gradient step per iteration.
BGNN
BGNN
RMSF
10
20
30
40
50
Iteration
Iteration
EBBS
10
20 20
40 50
Itoration
Figure S1: Performance of BGNN vs. EBBS after each boosting iteration on the VK dataset. The left BGNN uses the hyperparameter values that performed best the County dataset. The right BGNN uses the hyperparameter values that performed best on the VK dataset. EBBS uses the hyperparameter values that performed best on the County dataset. These results suggest that EBBS can be run with mostly shared hyperparameters across all datasets.
results, do not explicitly account for the outer-loop boosting in fully integrated fashion. While BGNN can be executed with single SGD step per iteration, this alone not adequate for establishing convergence and it comes at the cost of decreased empirical performance. Table S4 compares BGNN performance using only a single gradient step per iteration, where results are obtained using a full sweep of all BGNN hyperparameters (as per the authors' published code). These results show that BGNN performance can degrade with only single SGD step, to the extent that simply training CatBoost plus separate GNN model on top (i.e., BGNN without end-to-end training, called Res- GNN by Ivanov & Prokhorenkova (2021)) performs just as well, and possibly better on VK.
grid search over many hyperparameter combinations using each separate validation data set to achieve the results reported by Ivanov & Prokhorenkova (2021). Table S5 and Figure SI demonstrates that EBBS can be run with mostly shared hyperparameters across all datasets while still performing well.
In part due the above issues, the BGNN model relies
C EMPIRICAL CONVERGENCE OF EBBS
In this section, we visualize the losses on the training and validation data over the course of training iterations. Here we consider the County dataset as well as three methods: EBBS, EBBS with momentum and BGNN. For BGNN, we first evaluated different hyperparameter settings on the validation data, and then show the loss curves the BGNN model with the best hyperparameters. Over each epoch, BGNN performs 10 or 20 steps of gradient descent to train its GNN model. In order to compare our method fairly, we unfold BGNN's 's inner loop of GNN training, and plot the loss after BGNN has performed oscillates heavily over the course of its iterations. In contrast, the loss of EBBS (pink line and orange lines) decreases monotonically, revealing empirical convergence of EBBS as guaranteed by Theorem
step of gradient descent. Figure S2 shows the loss of BGNN (blue line)
15

---

Published as a conference paper at ICLR 2022
Training Validation
8
with
DGNN
6
loss
4
2
50
100
150
200
250
Iteration
Figure $2: Training and validation losses vs. number of iterations for the County dataset (regression).
1.55
1.30
1.45
1.35
1.30
1.20
1.15
1.10
Ay
Figure S3: RMSE vs. different value of Xy for County dataset.
Comparing EBBS with momentum (pink line) and EBBS without momentum (orange line) reveals that Nesterov's 's acceleration method can speed the convergence of our first-order boosting method.
D EXPERIMENT DETAILS
D.1 DATASETS
node features are the property, edges connect the neighbors and target is the price of the house. County: each node a county and edges connect two counties sharing a border, the target is the unemployment rate for county. VK: each node is person and edges connect two people based on the friendships, the target is the age of node. Avazu: each node is device and edges connect two devices if they appear on the same site with the same application, the target the click- brick-through-ree of a node. DBLP: node feature represent authors, paper and conferences and target is to predict one of the classes (database, data mining, information retrieval and machine learning). SLAP: node features represent network bioinformatics such chemical compound, gene and pathway, the goal to predict one of 15 gene type. Coauthor: nodes are authors and an edge connects two authors co-authored paper. Node features represent paper keywords for each author's papers, and the goal to predict which fields of study for each author.
House:
For House, County, Vk. Avazu, DBLP and SLAP, Ivanov & Prokhorenkova (2021) introduce how to construct the graph model based on tabular data. Furthermore, we randomly split each dataset (train validation test 6 2 2), and repeat all experiments with five different splits reporting the
16

---

Published as a conference paper at ICLR 2022
average performance (and its standard deviation) over the five replicates. For fair comparison, the same splits and random seed as used for BGNN.
D.2 BASELINE DETAILS
For regression tasks: GNN baselines are from Ivanov & Prokhorenkova (2021).
For classification tasks: GNN baselines for Slap and DBLP are taken from Ivanov & Prokhorenkova (2021). For Coauthor-CS and Coauthor-Phy, we implement the GNN models via the DGL framework (Wang et al., 2019). For GCN, GAT, and AGNN we train 3 layer models with a hidden node representation of 256. APPNP is implemented with layer MLP before the final message passing layer. We use mini-batch training with neighbor sampling, with fanout of 15 at each layer, to construct the training subgraph for each mini-batch, We do not tune the typer-parameters for these models. All models are trained with the Adam optimizer with learning rate of 5e-3. The results presented for each are the average of runs on the dataset.
D.3 MODEL HYPERPARAMETERS
We smooth the node features and concatenate the smoothed values with the original feature values for regression task. Here R is the weight from (13) and k₂ is the number of propagation steps. For all regression models, we choose X₂ 20 and k = 5; for classification we do not use smoothed node features.
EBBS Model. We consider the following hyperparamters:
Ay. by: We propagate over the graph to compute (X; (()) via (6), where Xy is the weight in (2) (or analogously the more general (13)) and ky is the number of propagation steps.
Smoothing Type: For the graph propagation required to computed (x; we choose label smoothing via (6), error smoothing using (15) or both of them.
Boosting Tree LR: The learning rate of our GBDT model.
Additionally, encode categorical features as numerical variables via the CatBoost Encoder" Ivanov Prokhorenkova (2021). For regression tasks, the number of training epochs 1000, early stopping rounds is 100. For classification tasks, the number of training epochs is 200, early stopping rounds 20. Throughout all experiments, we just used the simple Laplacian kernel for simplicity, and reserve exploration of alternative kernels in diverse settings for future work. For each iteration, CatBoost to find the best weak-learner. All hyperparameter settings are listed in Table S5, and were chosen manually based on validation scores in preliminary experiments. We also an approach from (Wang et al., 2021) to mitigate the data leakage problem.
Dataset
X
ky
Smoothing Type
Boosting Tree LR
House
2.0
5
label and error label and error
0.2
County
2.0
5
0.2
VK
50.0
2
eтror
0.05
Avazu
2.0
5
label and error
0.1
Classification (all)
2.0
5
label
1.0
Table S5: Hyperparameter settings used for EBBS, which are shared across all random seeds/dataset- splits. We emphasize here that all BGNN results (the SOTA model for graph data with tabular node features) follow the code from https: : //ittti hub. com/nee ht////d11//// 0077111/bgnnn /bgnn, which executes costly independent sweep over hyperparameters for each dataset and for each random seed/dataset-split to achieve the reported performance.
17

---

Published as a conference paper at ICLR 2022
E TECHNICAL DETAILS REGARDING CONVERGENCE
To proceed in quantifiable way, rely the concept of minimal cosine angle (MCA) defined in Lu Mazumder (2020); Lu et al. (2020).
Definition 1. Given a set of K weak learners, let B E R denote the matrix of predictions of every weak learner over each sample, both training and lesting." Then the MCA of this set of weak-learners is defined as
r
min max cos(b.g.r) PER" JE[L....]]
(20)
where b.g denotes the j-th column of B.
Per this definition, I (0, 1] can be viewed an estimate of the "density" of the weak learners in the prediction space, with larger values associated with higher density. We also require the definition of a-smooth and j--strongly convex functions:
Definition 2. A loss function Cly. f) a-smooth for any y and any fi and fz, we have that
32(y,
fly, fi) S Cly, f2)
a 2 f2)². 0f (fi f2)
Furthermore, Cly. f) is p-strongly convex for any y and any f1 and f2. we have that
Cly, f1) 2 Cly, fe) f2)
0f (fi f2) M (fi F2)
2
We then apply these definitions obtain two intermediate results that will be leveraged for the main proof:
Lemma 1. The energy function (2) is a-smooth and u-strongly convex, with a = m (AL I) and μ m (XL + I). where F (XL + I) and o (>L + represent the largest and smallest singular values of XL + respectively.
The proof is straightforward and follows from computing the Hessian of (z Additionally, since L is the Laplacian of G, it is positive-semidefnite such that we have < < S a < +00.
next turn to the meta-loss (7). Note that if (0) = f(x:0) then the operator p(k) collapses to matrix, meaning [f)][[(X;( = ((k) f(x; 0), where p(k) e Raxn, This observation then leads
the following:
Lemma 2. Let D(u)= 1|u| g(u) u, IIL 11 the loss from (7), then we have el is a0*) smooth,, with ((h) = T T (t)) where o Fuaax p() represents the largest singular values of operator ((k) the subscript m indicates the first m rows or elements of a matrix or vector respectively. Moreover, we have < (k) < +o0 for any 0.
The proof is also straightforward given that (kk) converges to (AL + +1+11111 for any [ 1
and the largest singular value of p(k) is finite.
We now proceed to specific results related to convergence in the main paper.
Theorem 1. Let D(u, v) || v1 g(u) u, and |IL + I| 1 in the loss from (7). Then for all 2 0 and 2 0, there exists a constant T E (0, 1] and c > such that the iterations of Algorithm augmented with the momentum factor from Lu et al. (2020) and associated momentum
parameter < 2-|z, satisfy
6 (0" (k) (
< O + ck.
(21)
'In the original definition, the MCA only concerns training samples; however, for our situation we must consider all samples due to gradient propagation over the whole graph from the perspective of the weak leamerrs function space.
18

---

Published as a conference paper at ICLR 2022
Proof. Given the stated assumptions, and the initialization Z (0) discussed above and in the main text, the loss from (7) reduces <(h)) (0)
f(hh X: 0); yi
Σ
p(h) 0X: -
p Tim f (X;
(22)
where the subscript 1 mn indicates the first rows or elements of matrix vector respectively.
Lemma implies that e is -mmoohh. We may then apply gradient boosting machine convergence results from Lu et al. (2h20)[T 4.1] that apply to this setting. Specifically, assuming constant step-size rule with (A/(A) and momentum parameter Φ S TM /(4 + r2), where denotes the value of the corresponding MCA defined above, it follows that
(K) 20(1 1)2 11(x;00\1
((k) (0*) S (k) (0())) - -
(23)
for all / 1 O.
Furthermore, based Bubeck (2014)[Theorem 3.10], Lemma and the step-size 1/0, can establish that the descent iterations from (6), which reduce (2), will satisfy
p (k) (Xx:0)
Se #* | -(x
(24)
where p A Pi:m for all variants. Since this bound must hold for any value of f (X; 0). by choosing f (X:0) = I, we can infer that
p( -p"
--11 S -e-
5* 1
(25)
or equivalently
p(()_ p- - # |!o) p'
(26)
2
Denote f(k) (X:0*) ) as the optimal solution of (k) From (23), it follows that
2 ((k) p(a) (x:0") - ÿ S
(k)
((()) f (x:011) 7
20(1 + 1)3 (ll((((()))) 0')
(27)
where y - Vim analogous to P. Denote (X:0) the optimal solution of E7. Since (()) (X: 0*)
is the optimal solution of ((k) we also have that
2
p (x:0) (x) 7 S
(h)) (xx00) - 7
1
(DIN) P*) f(x:0') + P'
-1 -B1
(28)
2
(D p') 1(x:0') 0")
P" (xx:0)) 4
2
2 (D P') f (x:0)
P p''(Xx0') 1
Adding (27) and (28) then leads
p(()) (x;010)
(2)
2
+ -P' (x
7 2
f(X; 0*)
+
20( + 1)2
2
+ p' (x) - 71
+2
(p - s (x:00)
P S (x;0")
(29)
19

---

Published as a conference paper at ICLR 2022
And by changing the order of terms, we can produce
2
plh)s f (x:010)
P" p')((;00))
(kk)
2 +
[(X:
(p(t) - -P-) / (x; 00)
2Φ(t + 1)2
+ 2 (D())
P*) f (x:07)
p"j 3
2
o(k)
12
(p(t) - -p-) 1:11 f (x:
5(X:0) 0")
+
(30)
2Φ(t + 1)3
2
(p()) -P')
11
f
1(:00')
P'f (xx() 4
< 0
1
+ 0 (5$))
+0 30(e= #/)
12
0 + co ck
where c 1 and we have applied (25) and (26) in producing the second-to-late inequality. And finally, since f (X:0) 0") is the optimal solution of Ez. we also have
2
p's - 3/ s
p' f (x:0())- - -9
1 - p (x)
(p" - p( f (x(0(0)
(31)
2
2
| plll) (x:010)
+ 2 (p' p(l)) f (x; 000)
-
And by changing the order of terms, we arrive at
- 3/ 2 - |p'1(X:00)- y
p(t)) / (x (x:000)
2 - (p' o (x
2 - (p''-((t)) f (x: (x: || |(t) (x: xx)
2
2 - O
(32)
Combining (30) and (32), we have
- s La (((0))))((0)))))) s so
from which it follows that
1 t (2t0))))) s o (
((() (0 - Eg (0r)
(33)
which concludes the proof.
To prove the Corollary 1, we introduce Lemma 3 firstly.
Lemma 3. Let D(u)= |u] g(u) u, | + -1 in the loss from (7). Additionally, penalty factor =x] 0) ||3- is added to (7), then we have (()) is (k)) -mooohh and p-strongly convex,
where af (8) maxx ( (P(. 1.m) and μr c. Moreover, we have O < p g(k)) < +00 for any k 'z 0.
20

---

Published as a conference paper at ICLR 2022
The proof is also straightforward given the stated assumptions, the loss from (7) reduces to (0)
P
1/mm
((k) (x(x0)),; - v.) + {l) =
1ime
f(X;0)
(34)
VEI
((A) 1im
Denote ((A)
then we have ((h) is ( smoothh and j-sstronlyy convex, where ((k)
VeIn
max (P*))
and j E.
The proof of Corollary 1 resembles the proof of Theorem 1. Since the bilevel loss (7) is a-smooth and ju-strongly convex, we can apply gradient boosting machine convergences results from Lu Mazumder (2h20]T 4.1] : let g be a(0) -moooh and j-strrongly convex, consider Gradient Boosting Machine with constant step-size rule with 1/a(k), If T denotes the value of the corresponding MCA, then for all t 2 we have that
4 (0 - (1))) (0)) S
P o(R)
r
( -
(0))
(35)
The remaining part of proof is the same with the proof of Theorem
ADDITIONAL REFERENCES FOR THE SUPPLEMENTARY
S. Bubeck. Convex optimization: Algorithms and complexity. arXiv preprint arXiv: 1405.44405.4980. 2014.
S. Ivanov and L. Prokhorenkova. Boost then convolve: Gradient boosting meets graph neural networks. arXiv preprint arXiv:2101.0854) 2021.
H. Lu and R. Mazumder. Randomized gradient boosting machine. SIAM Journal Optimization, 30(4) 2020.
H. Lu, S. P. Karimireddy, N. Ponomareva, and V. Mirrokni. Accelerating gradient boosting machines. In International Conference Artificial Intelligence and Statistics, pages 516-526. PMLR, 2020.
M. Wang. D. Zheng, Ye, Q. Gan, M. Li, X. Song, Zhou, C. Ma, L. Yu, Y. Gai, al. Deep graph library: A graph-centric, 2019.
package for graph neural networks. arXiv preprint
21


Reviews:
[{"review_id": "s4JzamkkTj", "reviewer": "Reviewer_Mnik", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "The notation used is easy to understand, as is the mathematical explanation in section 3, which is presented in a comprehensive but concise manner.\n\"for EBBS we must fit the weak-learners to gradients from both the training and test nodes\". This is the sentence that I am most concerned about, as the use of test data in the training phase may render the results obtained invalid. Although the authors give their own explanation of why the test nodes should also be used during training, i.e. for the propagation of information in the graph, if the test labels are used during the train there is no longer any separation between train and test. I have this doubt because the labels are used to calculate function-space gradients. Is this correct?\n\nAlgorithm 1 could be described in a little more detail.\n\nThe analysis of the convergence of the method by theorem is very good. The remarks connected to the theorem are interesting, but could have been treated in more detail (they are in part in the supplements).\nIf experiments are done with different random seeds (as stated), then results in Table 1 should be reported with their corresponding standard deviation or confidence interval.\nWhy are some results reported with different decimal places in the table? I am talking specifically about the CS column, but also for the Slap, DBLP and Phy columns one decimal place could be added.\nIf the datasets were taken from Ivanov & Prokhorenkova (2021), why was Wiki not taken? The reason should be that, being a homogeneous dataset, then, as explained by Ivanov & Prokhorenkova (2021), \"neural network approaches are sufficient to achieve the best results\". It would still be interesting as a comparison. Also as a comparison with them, the House and VK datasets could also be used for classification. They also report the standard deviation of all results.\nAlso, the results in the table match those of Ivanov & Prokhorenkova (2021), but I do not understand why their LightGBM results row has become the CatBoost row in this article for the Slap, DBLP and OGB-ArXiv datasets. Is this perhaps an error?\nAlthough the difference between OGB-ArXiv and the other datasets is properly explained, I think it still makes sense to put those results together with the others in Table 1.\n\"Although tabular graph data for node classification is widely-available in industry, unfortunately there is currently little publicly-available, real-world data that can be used for benchmarking.\"\nThis sentence is very vague and I am not fully convinced of its veracity.\n\nThe mention of the method called CatBoost+ is interesting, but it is given too little space. Why is it not considered in \"ours\"? If the idea is picked up by some other work, let it be mentioned properly.\n\"revealing that it may be more robust to non-ideal use cases\". That's why it might be interesting to add homogenous datasets and see if it applies there too.\nWhile in the main part it says \"This suggests that in new application domains it may conceivably be easier to adapt EBBS models\", in the supplements it says \"It shows EBBS can be run with mostly shared hyperparameters across all datasets\". I don't think there are enough experiments/results to say that, but I'd stick with \"suggest\" in the supplementary materials as well. Maybe add a sentence about the possibility of exploring this area more in future work.\n\nAfter the rebuttal I have strengthen my opinion on the quality of the paper. I believe it is a nice contribution to the field.", "summary_of_the_paper": "The authors propose a new method for integrating graph-based models with boosting. This is done using the typical method involving residuals and weak-learners, but adding a step where information is propagated in the graph. The approach is also simple, as no GNNs or other auxiliary models are required. It is also shown how the meta-loss introduced by the authors provides convergence given some moderate assumptions. According to the experiments reported, the proposed model is better than the current state of the art in the considered domain.", "summary_of_the_review": "The work is well structured, with a good theoretical basis to support the proposed methodology. The empirical results are very promising, although the small amount of datasets combined with the lack of confidence intervals does not allow for meaningful conclusions to be drawn.\nThe only major doubt concerns the use of test data in the training phase, which may have compromised the whole experiment.", "strength_and_weaknesses": "", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "koVNRsw7P6h", "reviewer": "Reviewer_zcK6", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Strength\n- The approach nicely defines a single objective that the model (graph propagation + decision trees) optimizes.\n- Empirically, there is a nice improvement over the existing BGNN.\n\nWeakness:\n- The studied problem does not seem particularly novel to me, especially given BGNN. Given BGNN, the scope seems a bit narrow to me (although I acknowledge that the authors solve the problem in a potentially better way than the BGNN paper).\n\nComments/questions:\n- I am curious to see the result of XGBoost + C&S (e.g., use XGBoost as the base predictor in C&S).\n- Does the framework supports any propagation rules beyond (6)? I would be curious to see how general the method is.\n", "summary_of_the_paper": "In this paper, the authors present a new approach to combine the boosted decision tree classifiers with a graph propagation model, which is important in handling table input data. The approach casts the graph propagation as an optimization problem, where the input node features are generated by boosted decision trees. The gradient can be taken in the functional space to learn the decision trees to minimize a unified loss. The final algorithm is shown to minimize the unified loss in a principled manner. The superior performance is demonstrated over the existing BGNN model.\n", "summary_of_the_review": "Overall, the approach seems sound and principled, although the scope is a bit narrow. Hence, I will give the weak accept. I would also like the authors to address my comments/questions.", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "YaLwz-64qed", "reviewer": "Reviewer_ahft", "summary": "", "questions": "", "limitations": "", "rating": 8, "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** This paper investigates tabular, graph-based data for classification and regression tasks. The proposed approach is an end-to-end, bilevel, combination of label propagation and boosting. The authors contribute not only an empirical analysis of the proposed approach on 8 datasets demonstrating the effectiveness of the proposed approach as well as a theoretical analysis. \n\n**Merits** I believe that this is a strong paper that clearly outlines a proposed approach for boosting in this non-iid setting of graph data. The proposed approach has a convergence guarantee and is shown to be very effective empirically. Overall, this seems to be a strong result. The supplemental material seems to give statistical significance of the improvements shown. Compared to the best previous method BGNN, combining boosting and GNNs, EBBS achieves stronger empirical results. The algorithms and theoretical results are discussed as well. \n\n**Weaknesses** Here are a few concerns / suggestions:\n* It could perhaps be made stronger by including some of the additional analysis that is in the supplemental material that investigates the trade-offs and ablations of the approaches, in the main body of the text. \n* I think that the paper could be made much stronger with a simple motivating (perhaps synthetic) example that illustrates where and when EBBS can be useful compared to competing methods. While convergence guarantees and motivations are described, a clear simple example (which might further be useful in using ablations to identify contributions of different parts of the solution) could strength the paper. \n\n**Minor Notes**\n* Why is \"GraphData\" one word in the title?\n* Figure 1 would be easier to read if Y-axis was the same in both plots", "summary_of_the_paper": "Following in the success of boosting methods for tabular data, this paper introduces a new boosting approach for data that graph-based with tabular features. The proposed approach, efficient bilevel boosted smoothing (EBBS), has convergence guarantees as well as empirical successes compared to competing methods. ", "summary_of_the_review": "This paper provides both theoretical and empirical results for a boosting method for graph structured data. The results appear to advance the state of the art and the submission seems to have valuable contributions.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "LIFatu0WFjC", "reviewer": "Reviewer_omBE", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "Strengths:  This paper proposes EBBS, efficient bilevel boosted smoothing, a novel way to combine GNN and Gradient boosting for learning tabular graph data. The addressed problem of integrating boosting into GNNs is very interesting to me. Also learning over tabular graph data should receive a wide audience given its importance in the industry. Empirical experiments show EBBS outperforms baseline methods on multiple node classification and node regression datasets. \n\nWeakness: In my opinion, the main weaknesses are in writing/presentation and reproducibility.\nFirst, I feel the writing of Section 3 can be improved to avoid readers' confusion. For example\n  - We can be more clear about how Eq 2 is rooted in Zhou et al 2004. In fact, I didn't get it when I checked the referenced paper. \n  - In (2), are both Z and \\theta learnable? \n  - P is binded twice, once in P* (Eq 3) and once in P^{k} (Eq 6)\n  - In Eq 7, what is for inner level optimization and what is for outer level optimization?\n  - Is \"Graph-Aware Propagation Layers\" terminology used in the literature?\nSecond, it seems that the proposed method EBBS will be incorporating test nodes during training. Will this cause test information to leak into the training process? Is there any specific preprocessing to avoid leaking? Is EBBS easy to implement?\n\n\nMinor issues (typos, formats): \n- \"on top model leaderboards\" -> on the top of model leaderboards\n- the template seems a bit different from the normal one, especially the font and the colour of the citation text\n- \"whereby the end-to-end training of a bilevel loss is such that values of the boosted base model f ebb and flow across the input graph producing a smoothed predictor f\" -> not sure if there is a grammar issue \n- \"use mi and to reference\" -> delete \"and\" ", "summary_of_the_paper": "This paper proposes a new way to integrate graph-based models with boosting based on principled meta loss, named EBBS. In experiments, the proposed method outperforms tabular baselines, GNN baselines, and some hybrid strategies like BGNN over some node classification/regression datasets.", "summary_of_the_review": "Overall, I like the problem the paper aims to address - how to better combine GNN with boosting methods for learning on tabular data. The paper proposes a novel way to address this problem, which is based on a principled meta-loss. Empirical results show the effectiveness of the results. I feel the paper can be improved more by iterating on the formulations in Sec 3.", "strength_and_weaknesses": "", "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": "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": {}}]

Author rebuttal:

Meta-review: The paper addresses a problem encountered in many real-world applications, i.e. the treatment of tabular data, composed of heterogeneous feature types, where samples are not i.i.d. In this case, learning is more effective if the typically successful approach for i.i.d. data (boosted decision trees + committee techniques) is combined with GNN to take into account the dependencies between samples. The main contribution of the paper with respect to previous work in the field is the introduction of a principled approach to pursue such integration. One important component of the proposed approach is played by the definition of a specific bi-level loss (efficient bilevel boosted smoothing) that allows for convergence guarantees under mild assumptions. Both theoretical and experimental contributions are sound and convincing, justifying the claimed merits of the proposed approach. Another strong point is the fact that the proposed approach is general and amenable to support a broad family of propagation rules. One weakness with the original submission was presentation, mainly because some key information was confined into the supplementary material. The revised version addressed this problem and added some more empirical results that confirmed the superiority of the proposed approach.
Finally, the fact that learning over tabular graph data is very important in Industry, the proposed approach may be of interest for a wide audience.
Decision: Accept (Spotlight)