Boost then Convolve: Gradient Boosting Meets Graph Neural Networks
Authors: Sergei Ivanov
Liudmila Prokhorenkova
Venue: ICLR 2021 Poster (2021)
Keywords: GNN
GBDT
graphs
tabular data
heterogeneous data

Abstract: Graph neural networks (GNNs) are powerful models that have been successful in various graph representation learning tasks. Whereas gradient boosted decision trees (GBDT) often outperform other machine learning methods when faced with heterogeneous tabular data. But what approach should be used for graphs with tabular node features? Previous GNN models have mostly focused on networks with homogeneous sparse features and, as we show, are suboptimal in the heterogeneous setting. In this work, we propose a novel architecture that trains GBDT and GNN jointly to get the best of both worlds: the GBDT model deals with heterogeneous features, while GNN accounts for the graph structure. Our model benefits from end-to-end optimization by allowing new trees to fit the gradient updates of GNN. With an extensive experimental comparison to the leading GBDT and GNN models, we demonstrate a significant increase in performance on a variety of graphs with tabular features. The code is available: https://github.com/nd7141/bgnn.

Published as a conference paper at ICLR 2021
BOOST THEN CONVOLVE: GRADIENT BOOSTING MEETS GRAPH NEURAL NETWORKS
Sergei Ivanov
Liudmila Prokhorenkova
Criteo Al Lab; Skoltech
Yandex; HSE University; MIPT
Paris, France
Moscow, Russia
s. wwvvvvvvvcriiei teo. com
ost rot. -erroouuvv--lleeadee-teeee
ABSTRACT
Graph neural networks (GNNs) are powerful models that have been successful in various graph representation learning tasks. Whereas gradient boosted decision trees (GBDT) often outperform other machine learning methods when faced with heterogeneous tabular data. But what approach should be used for graphs with tabular node features? Previous GNN models have mostly focused on networks with homogeneous sparse features and, as we show, are suboptimal in the heterogeneous setting. In this work, we propose a novel architecture that trains GBDT and GNN jointly get the best of both worlds: the GBDT model deals with heterogeneous features, while GNN accounts for the graph structure. Our model benefits from end- to-end optimization by allowing new trees to fit the gradient updates of GNN. With an extensive experimental comparison to the leading GBDT and GNN models, we demonstrate significant increase in performance on a variety of graphs with tabular features. The code is available:
com / nd 7144 /tmm///77///mm
INTRODUCTION
Graph neural networks (GNNs) have shown great success in learning on graph-structured data with various applications in molecular design (Stokes et al., 2020), computer vision (Casas et al. 2019). combinatorial optimization (Mazyavkina et al. 2020), and recommender systems (Sun et al. 2020). The main driving force for progress is the existence of canonical GNN architecture that efficienlly encodes the original input data into expressive representations, thereby achieving high-quality results on new datasets and tasks.
Recent research has mostly focused on GNNs with sparse data representing either homogencous node embeddings (e.g., one-hot encoded graph statistics) or bag-of-words representations. Yet tabular data with detailed information and rich semantics among nodes the graph are more natural for many situations and abundant in real-world AI (Xiao et al. 2019). For example, in social network, each person has socio-demographic characteristics (e.g., age, gender, date of graduation), which largely vary in data type, scale, and missing values. GNNs for graphs with tabular data remain unexplored, with gradient boosted decision trees (GBDTs) largely dominating in applications with such heterogeneous data (Bentéjac et al. 2020).
GBDTs are so successful for tabular data because they possess certain properties: (i) they efficiently learn decision space with hyperplane-like boundaries that are common tabular data; (ii) they are well-suited for working with variables of high cardinality, features with missing values, and of different scale; (iii) they provide qualitative interpretation for decision trees (e.g., by computing decrease in node impurity for every feature) or for ensembles via post-hoc analysis stage (Kaur et al. 2020 (iv) in practical applications, they mostly converge faster even for large amounts of data.
In contrast, a crucial feature of GNNs is that they take into account both the neighborhood information of the nodes and the node features to make a prediction, unlike GBDTs that require additional preprocessing analysis to provide the algorithm with graph summary (e.g., through unsupervised graph embeddings (Hu et al. (220aa).. Moreover, has been shown theoretically that message- passing GNNs can compute any function its graph input that is computable by Turing machine, i.c., GNN is known to be the only learning architecture that possesses universality properties on graphs (approximation (Keriven & Peyré 2019 Maron et al. 2019) and computability (Loukas) 2020

---

Published as a conference paper at ICLR 2021
Furthermore, gradient- learning of neural networks can have numerous advantages over the tree- based approach: (i) relational inductive bias imposed in GNNs alleviates the need to manually engineer features that capture the topology of the network (Battagha al.. 2018); (ii) the end-to-end nature of training neural networks allows multi-stage (Fey et al. 2019) or multi-component (Wang et al. 2020) integration of GNNs in application-dependent solutions; (iii) pretraining representations with graph networks enriches transfer learning for many valuable tasks such as unsupervised domain adaptation (Wu et al. 2020), self-supe learning (Hu al. 2020b), and active learning regimes (Satorras & 2011))
Undoubtedly, there are major benefits in both GBDT and GNN methods. Is possible to get advantages of both worlds? All previous approaches (Arik& & Pfister 2020 Popov et al., [2019] Badirli jt al. 2020) that attempt to combine gradient boosting and neural networks are computationalyy heavy, do not consider graph-structure data, and suffer from the lack of relational bias imposed in GNN architectures, see Appendix [ for more detailed comparison with related literature. To the best of our knowledge, the current work is the first to explore using GBDT models for graph-structured data.
In this paper, we propose a novel learning architecture for graphs with tabular data, BGNN, that combines GBDT's learning tabular node features with GNN that refines the predictions utilizing the graph's 's topology. This allows BGNN to inherit the advantages of gradient boosting methods (heterogeneous learning and interpretability) and graph networks (representation learning and end-to- end training). Overall, our contributions are the following:
(I) We design novel generic architecture that combines GBDT and GNN into a unique pipeline. To the best of our knowledge, this the first work that systematically studies the application of GBDT to graph- graph-structun structured data.
(2) We overcome the challenge of end-to-end training of GBDT by iteratively adding new trees that fit the gradient updates of GNN. This allows us backpropagate the error signal from the topology of the network to GBDT.
(3) We perform an extensive evaluation of our approach against strong baselines in node prediction tasks. Our results consistently demonstrate significant performance improvements on heterogeneous node regression and node classification tasks over a variety of real-world graphs with tabular data.
(4) We show that approach is also more efficient than the ofate-of-the-an art GNN models due to much faster loss convergence during training. Furthermore, learned representations exhibit discemible structure in the latent space, which further demonstrates the expressivity of our approach.
2 BACKGROUND
Let G = (V, be a graph with nodes having features and target labels. In node prediction tasks (classification regression), some target labels are known, and the goal predict the remaining ones. Throughout the text, by lowercase variables x (v E V') or x we denote features of individual nodes, and X represents the matrix of all features for E V. Individual target labels are denoted by Yo. while Y is the vector of known labels.
Graph Neural Networks (GNNs) use both the network's connectivity and the node features to learn latent representations for all nodes v E V. Many popular GNNs use neighborhood aggregation approach, also called the pessage-passing mechanism, where the representation of a node v is updated by applying a non-linear aggregation function of v's neighbors representation (Fey & Lenssen] 2019). Formally, GNN is a differentiable, permutation-invariint function go (G, X) Y. where Y is the vector of predicted labels. Similar to traditional neural networks, GNNs are composed of multiple layers, each representing a non-linear message-passing function:
x COMBINE' (x!-) AGGREGATE" (( ((xx"",,(")) x (w,e) EJ))
where x", is the representation of node e at layer t, and COMBINE' and AGGREGATE are (para- metric) functions that aggregate representations from the local neighborhood of node. Then, the GNN mapping Jo includes multiple layers of aggregation (I.. Parameters of GNN model are optimized with gradient descent by minimizing empirical loss function LYNN(Y, (G X)).
2

---

Published as a conference paper at ICLR 2021
Gradient Boosted Decision Trees (GBDT) is well-known and widely used algorithm that is defined on non- non-graph tabular data (Friedman 2001) and is particularly successful for tasks containing heterogeneous features and noisy data.
The core idea of gradient boosting is to construct a strong model by iteratively adding weak ones (usually decision trees). Formally, at each iteration f of the gradient boosting algorithm, the model f(x) is updated in an additive manner:
ex)(
(2)
where ft-1 is model constructed at the previous iteration, h' is weak learner that is chosen from some family of functions H. and is a learning rate. The weak learner ht E is chosen to approximate the negative gradient of loss function L
w.r.t. the current model's predictions:
O OL(f--1(xi)) (xx)) M1). (x;)
2
ht
arg min KCH
Σ
n(xx))
(3)
The gradient w.r.t. the current predictions indicates how should change these predictions to improve the loss function. Informally, gradient boosting can be thought of as performing gradient descent in functional space.
The set of weak learners H is usually formed by shallow decision trees. Decision trees are built by a recursive partition of the feature space into disjoint regions called leaves. This partition is usually constructed greedily to minimize the loss function (3). Each leaf R, of the tree assigned to a value aj. which estimates the response y in the corresponding region. our case, aj equal to the average negative gradient value in the leaf Rj. To sum up, we can write h(z) = Eg aj (wER))
GBDT MEETS GNN 3
Loss (G
Algorithm 1 Training of BGNN
GNN: Be
Input: Graph G, node features X, targets Y Initialize GBDT targets for epoch i = 1 to N do Train trees GBDT with eq. 2 fr arg min LGBDT ( f
x
Compute update
Pass to GNN
aL[go (G, ()))
0X'
f(X)
f + S+
GBDT:f
New tree:
Train ( steps of GNN on new node features X' +- f(X)
8, X' + arg min LGNN (GoNN(90(()) X',
a.
Update targets for next iteration of GBDT y - X' fXX
Node features
end for Output: Models GBDT and GNN go
Figure 1:
Training of BGNN, steps for one
epoch are numbered.
Gradient boosting approach is successful for learning on tabular data; however, there are challenges of applying GBDT on graph-structured data: (i) how to propagate relational signal, in addition to node features, to otherwise inherently tabular model; and (ii) how to train it together with GNN in an end-to-end fashion. Indeed, optimizations of GBDT and GNN follow different approaches: the parameters of GNN are optimized via gradient descent, while GBDT constructed iteratively, and the decision trees remain fixed after being built (decision trees based on hard splits of the feature space, which makes them non-differentiable).
A straightforward approach would be to train the GBDT model only the node features and then use the obtained predictions, jointly with the original input, as new node features for GNN. this case, the graph-insensitive predictions of GBDT will further be refined by graph neural network.

---

Published as a conference paper at ICLR 2021
This approach (which call Res-GNN) can already boost the performance of GNN for some tasks. However, in this case, the GBDT model completely ignores the graph structure and may miss descriptive features of the graph, providing inaccurate input data GNN.
In contrast, we propose end-to-end training of GBDT and GNN called BGNN (for Boost-GNN), As before, we first apply GBDT and then GNN, but now optimize both of them, taking into account the quality of final predictions. The training of BGNN shown in Figure I Recall that one cannot tune already built decision trees due their discrete structure, so we iteratively update the GBDT model by adding new trees that approximate the GNN loss function.
In Algorithm]] 1 we present the training of BGNN that combines GBDT and GNN for any node-level prediction problem such as semi-supervised node regression or classification. In the first iteration, we build GBDT model f (xx with k decision trees by minimizing the loss function (CBDT((' y) (e.g.. RMSE for regression or cross-entrope for classification) averaged over the train nodes, following the equations (3) Using all predictions f'(X), we update the node features to X' that we pass to GNN. Possible update functions that we experiment with include concatenation with the original node features and their replacement by f (x()). Next, we train a graph neural network go on a graph G with node features X' by minimizing LGNN (ge (G, X'), Y) with steps of gradient descent Importantly, we optimize both the parameters 0 of GNN and the node features X'. Then, we use the difference between the optimized node features X _ and the input node features X' fX) as the target for the next decision trees built by GBDT. If = 1, the difference X X' exactly equals the negative gradient of the loss function w.r.t. the input features X' multiplied by the learning rate ny:
X Xhew= X' 0LGNN (90 (G,X).
0X'
In the second iteration, we train a new GBDT model f with the original input features X but new target labels: X X'. Intuitively, f fits the direction that would improve GNN prediction based on the first predictions f (X).. In other words, GBDT approximates the gradient steps made by GNN for the node features X'. This is regression problem, so here LGBDT is the RMSE loss.
After f² is trained, we combine the predictions f(X) f'() + fx(X and pass the obtained values X' to GNN as node features. GNN model go again does steps of backpropagation and passes the new difference X X' as a target to the next iteration of GBDT. In total, the model is trained for N epochs and outputs GBDT model f X Y and GNN model go (G, X) Y. which can be used for downstream tasks.
Intuitively, BGNN model consists of two consecutive blocks, GBDT and GNN, which trained end-to-end, and therefore can be interpreted from two angles: GBDT as an embedding layer for GNN or GNN as a parametric loss function for GBDT. In the former case, GBDT transforms the original input features X to new node features X', which are then passed to GNN. In the latter case, one can see BGNN as a standard gradient boosted training where GNN acts as a complex loss function that depends on the graph topology.
4 EXPERIMENTS
We have performed a comparative evaluation of BGNN and Res-GNN against a wide variety of strong baselines and previous approaches heterogeneous node prediction problems, achieving significant improvement in performance across all of them. This section outlines our experimental setting, the results on node regression and classification problems, and extracted feature representations.
In our first experiments, we want to answer two questions:
QI Does combination of GBDT and GNN lead to better qualitative results in heterogeneous node regression and classification problems?
Q2 Is the end-to-end training proposed in Algorithm Tettte than a combination of pretrained GBDT with GNN?
To answer these questions, we consider several strong baselines among GBDTs, GNNs, and pure neural networks. CatBoost is a recent GBDT implementation (Prokhorenkova al. 2018 that uses
LGNN is determined by the final task, e.g., RMSE for regression the cross-entropy loss for classification.
4

---

Published as a conference paper at ICLR 2021
oblivious trees weak learners. LightGBM is another GBDT model (Ke et al. extensively in ML competitions. Among GNNs, we tested four state-of-the-ann art recent models that showed superior performance in node prediction tasks: GAT (Velicković et al.] 2018). GCN (Kipf & Welling 2017). AGNN (Theeumparammpi et al. 2018). APPNP (Klicpera et al. 2019). Additionally,
2017) that is used
test the performance of fully-connected neural network FCNN and its end-to-end combination
with GNNs, FCNN-GNN.
We compare these baselines against two proposed approaches: the end-to-end BGNN model and end-to-end Res-GNN. The BGNN model follows Algorithm| and builds each tree approximating the GNN eтror in the previous iteration. In contrast, Res-GNN first trains GBDT model on the training set of nodes and then either appends its predictions for all nodes to the original node features or replaces the original features with the GBDT predictions, after which GNN is trained on the updated features, and GNN's predictions are used to calculate metrics. Hence, Res-GNN is two- stage approach where the training of GBDT is independent of GNN. On the other hand, BGNN trains GBDT and GNN simultaneously in end-to-end fashion. In most of our experiments, the GNN-component FCNN-GNN, Res-GNN, and BGNN based on GAT, while Section 4.3 we analyze consistency of improvements across different GNN models.
We ensure that the comparison done fairly by training each model until the convergence with reasonable set of hyperparameters evaluated the validation set. We run each hyperparameter setting three times and take the average of the results. Furthermore, we have five random splits the data, and the final number represents the average performance of the model for all five random seeds. More details about hyperparameters can be found in Appendix
4.1 NODE REGRESSION
4.1.1 DATASETS
utilize five real-world node regression datasets with different properties outlined in Table [ Four of these datasets are heterogeneous, ie., the input features are of different types, scales, and meaning. For example, for the VK dataset, the node features are both numerical (c.g., last time seen the platform) and categorical (e.g., country of living and university). On the other hand, Wiki dataset is homogeneous, f.e., the node features are interdependent and correspond to the bag-of- words representations of Wikipedia articles. Additional details about the datasets can be found in Appendix
Table 1: Summary of regression datasets.
House
County
VK
Avazu
Wiki
Setting
Heterogeneous
Heterogeneous
Heterogeneous
Heterogeneous 1297
Homogeneous
# Nodes
20640
3217
54028
5201
Edges
182146
12684
213644
54364
198493
# Features/Node
6
14
3148
Mean Target
2.06
5.44
35.47
0.08
27923.86
Min Target
0.14
1.7
13.48
0
16
Max Target
5.00
24.1
118.39
849131
Median Target
1.79
33.83
9225
4.1.2 RESULTS
The results of our comparative evaluation for node regression are summarized Table 2 We report the mean RMSE (with standard deviation) on the test set and the relative gap between RMSE of the GAT model (Veličković et al. 2018) and other methods, i.c., gap = (rm - (Tgnn//r g/ where T' and r'g RMSE of that model and of GAT, respectively.
Our results demonstrate significant improvement of BGNN over the baselines. In particular, in the heterogeneous case, BGNN achieves 8%, 14%, 4%, and 4% reduction of the error for House, County, VK. and Avazu datasets, respectively. Res-GNN model that uses a pretrained CatBoost model for the input of GNN also decreases RMSE, although not much the end-to-end model
5

---

Published as a conference paper at ICLR 2021
Table 2: Summary of our results for node regression. Gap % is relative difference w.r.t. GAT RMSE (the smaller the better). 2 results are highlighted in bold.
Heterogemeons
Homogeneous
House
County
VK
Wiki
Method
RMSE
Gap
RMSE
Gap %
RMSE
Gap %
RMSE
Gap
Gup
GBOT
0.01
0.07
-4.32
3.36
46359 4508
LightGBM
0.63 + 0.01
15.98
1.4 0.07
-3.93
7.2 + 0.21
.0.33
0.1171
0.02
3.27
49915 + 3643
8.71
GAT
0.54 4: 001
1.45 0.06
0.19
0.1134 1: 0.01
45916 1: 4527
0
GNN
GUN
16.77
0.08
2,06
0:19
0.34
0.1141
0.02
0.58
44936 1:
AGNN
0.59 1: 001
8.01
1.45 0.08
-0.19
7.26
4. 0.20
0.54
0.1133 0.02
0.00
45982 1: 3058
0.14
APPNP
0.69 4: 0.01
27.11
1,5
0.11
3.39
13:23
0.12
83.19
0.1127
0.01
-0.65
53426
1: 11,59
16.36
Xx
FONN
0.68 + 0.02
25,49
1.48
0.07
1.56
7.29
4 0.21
1.02
0.118 0.02
4.07
51662 + 2983
12.51
FUNN-GNN
0.53 +: 0.01
-2.48
1.39 0.06
-4.68
7.22
0.20
0.01
0.1114 +: 0.02
-1.82
48491 4: 7889
5.61
Ours
Res-GNN BGNN
0,51 + 0.01
66.39
-8.35
0.1099
46747 +
0.5 + 0.01
.8.15
1.26
0.08
-13.67
6.95 0.21
-38
0.109
0.01
-3.9
49222 + 3743
7.2
BGNN. In the homogeneous dataset Wiki, CatBoost and, subsequently, Res-GNN and BGNN outperformed by the GNN model. Intuitively, when the features are homogeneous, neural network approaches are sufficient to attain the best results. This shows that BGNN leads better qualitative results and its end-to-end training outperforms other approaches in node prediction tasks for graphs with heterogeneous tabular data.
We can also observe that the end-to-end combination FCNN-GNN often leads to better performance than pure GNN. However, its improvement smaller than for BGNN which uses the advantages of GBDT models. Moreover, CatBoost and LightGBM can be effective on their own, but their performance not stable across all datasets. Overall, these experiments demonstrate the superiority of BGNN against other strong models.
4.2 NODE CLASSIFICATION
For node classification, we use five datasets with different properties. Due to the lack of publicly available datasets with heterogeneous node features, we adopt the datasets House class and VK class from the regression task by converting the target labels into several discrete classes. We additionally include two sparse node classification datasets SLAP and DBLP Doming from heterogeneous infor- mation networks (HIN) with nodes having different types. We also include one homogeneous dataset OGB-ArXiv (Hu et al. 2020a). In this dataset, the node features correspond to a 128 -i-dimensional feature vector obtained by averaging the embeddings of words in the title and abstract. Hence, the features are not heterogeneous, and therefore GBDT is not expected to outperform neural network approaches. More details about these datasets can be found in Appendix [
Table 3: Summary of our results for node classification. Gap % is the relative difference w.r.t. GAT accuracy (the higher the better). Top-2 results are highlighted in bold.
Heterogeneour
Homogemeoux
House class
VK class
Slap
DBLP
OGB-ArXiv
Method
Acc.
Gap
Asc.
Gap
Asc.
Gap
Acc.
Gap
Acc.
Gap
CUDE
CatBonst
0.52
-16.82
0.57
-1.26
15.12
0.759 0.03
-5.22
0.45
-36.35
LightGBM
0.55 = 0.00
-11.98
0.579 = 0.01
0.26
0.963 : 0.00
20.3
0.913 :: 0.01
13.73
0.51
-26.97
GAT
0.802 4 0.01
0.70
ONN
GCN
0.6 0.00
-3.98
0.574 = 0.00
-0.6
0.878 + 0.01
9.72
0.428 + 0.04
-66.6
AGNN
0.14:.0001 0.01
-1.73
0.572
1 0.00
-0.79
0.892
1 0.01
11:47
0.794 1: 0.01
-1.02
APPNP
2.19:0000
-0.89
0.573
= 0.00
-0677
0.895 + 0.01
11.79
0.83 + 0.02
3.47
NN
FCNN
0.534 1: 0.01
-14.53
0.567
1. 0.01
-1.72
0.759
0.04
-5.24
0.623 1. 0.02
-22.3
0.50
-28.91
FCNN-GNN
0.64 0.00
0.589 0.00
2.13
0.89
11.11
0.81 + 0.01
0.94
0.71
Ouits
Res-GNN
0.625 0.01
.0.66
0.603
0.00
4.45
0.905
0.01
13.06
0.892 1: 0.01
11.11
0.70
.0.33
BGNN
0.682 + 0.00
9.18
106833 + 0.00
18.3
0.95 + 0.00
18.61
0.889 + 0.01
10.77
0.67
.4.36
As can be seen from Table 3 on the datasets with heterogeneous tabular features (House class and VK class), BGNN outperforms other approaches with significant margin. For example, for the
6

---

Published as a conference paper at ICLR 2021
VK_class dataset BGNN achieves more than 18% of relative increase in accuracy. This demonstrates that learned representations of GBDT together with GNN can be equally useful for node classification setting data with heterogeneous features.
The other two datasets, Slap and DBLP, have sparse bag-of-words features that are particularly challenging for the GNN model. On these two datasets, GBDT is the strongest baseline. Moreover, since FCNN outperforms GNN, we conclude that graph structure does not help, hence BGNN not supposed beat GBDT. This is indeed the case: the final accuracy of BGNN is slightly worse than that of GBDT.
In the homogeneous OGB-ArXiv dataset, FCNN-GNN and GNN achieve the top performance In a nutshell, GBDT does not learn good predictions on
followed by RNs-GNN and BGNN models I the homogeneous input features and therefore reduces the discriminative power GNN. Both cases, with sparse and with homogeneous features, show that the performance of BGNN is on par or higher than of GNN; however, lacking heterogeneous structure the data may make the joint training of GBDT and GNN redundant.
4.3 CONSISTENCY ACROSS DIFFERENT GNN MODELS
Seeing that our models perform significantly better than strong baselines on various datasets, we want to test whether the improvement is consistent different GNN models are used. Thus, we ask:
Q3 Do different GNN models from our approuch of combination with GBDT?
To answer this question, we compare GNN models that include GAT (Veličković et al,, 2018). GCN (Kipf & Welling 2017), AGNN (Thekumparampil al. 2018), and APPNP (Kliepera et al. 2019).
We substitute each of these models to Res-GNN and BGNN and measure the relative change in performance with respect to the original GNN's performance.
-15
-23
GAT
GCN
MPPM
GCN
AGAR
AFRRP
GAT
GCN
AGAN
APPRP
(a) House
(b)
VK
(c)
Avazu
Figure 2: Relative difference for Res-GNN (yellow, diagonal) and BGNN (red, squared) for different GNN architectures w.r.t. GNN RMSE (the smaller the better).
In Figure 2 we report the relative RMSE gap between Res-GNN and BGNN for each of the GNN architectures. i.e., we compute gap (rm //nn)/Tann where Tm and Tyan are RMSE of that model and of GNN respectively. This experiment positively answers and and shows that all tested GNN architectures significantly benefit from the proposed approach. For example, for House dataset the decrease in the mean squared error is 9%, 18%, 19%, and 17% for GAT, GCN, AGNN, and APPNP models respectively. Additionally, one can see that the end-to-end training BGNN (red, squared) leads to larger improvements than naïve combination of CatBoost and GNN in Res-GNN (yellow, diagonal). Exact metrics and training time are in Appendix
4.4 TRAINING TIME
As the previous experiments demonstrated superior quality across various datasets and GNN models, it is important to understand if the additional GBDT part can become a bottleneck in terms of efficiency for training this model on rerl-world datasets. Hence, we ask:
Q4 Do BGNN and Res-GNN models incur a significant increase in training time?
For OGB-ArXiv we used a different implementation of the GAT model to align results with the publicly available leaderboard:

---

Published as a conference paper at ICLR 2021
To answer this question, measure the clock time train each model until convergence, considering early stopping. Table presents training time for each model. We can see that both BGNN and Res-GNN run faster than GNN in most cases. In other words, BGNN and Res-GNN models do nor incur an increase in training time but actually are more efficient than GNN. For example, for VK dataset BGNN and Res-GNN run 3x and 2x faster than GNN, respectively. Moreover, BGNN is consistently faster than another end-to-end implementation FCNN-GNN that uses FCNN instead of CatBoost to preprocess the original input features.
Table 4: Training time (s) in node regression task.
Method
House
County
VK
Wiki
Avazu
GBDT
CatBoost
4 1
2 = 1 + 0
24 4
10 +
2 2 2 0 0 0
LightGBM
3 0
5 3
3 +
GAT
35 2
19 +
42 4
15 + 1
9
GNN
GCN
28 0
18 7
38 + 0
13 +
12 1246 6
AGNN
38 +
28 +
48 +
19 +
14 14
APPNP
68 +
34 + 10
81 +
49 26
24 + 15
Ours NN
FCNN
16 =
2
109 + 35
12 2
2
FCNN-GNN
39 +
21 11
48 2
16 +
14
Res-GNN
36 7 7
7
41 +
31 +
7
BGNN
20 +
4
2 0
16 =
21 7
5 1
The reason for improved efficiency is that BGNN and Res-GNN converge with a much fewer number of iterations demonstrated in Figure 3 We plot RMSE on the test set during training for all models (with winning typerparameters). We can see that BGNN converges within the first ten iterations (for k 20), leading to fast training. In contrast, Res-GNN is similar in terms of convergence to GNN for the first 100 epochs, but then it continues decreasing RMSE unlike GNN that requires much more epochs converge. This behavior similar for other datasets (see Appendix F)
loss
loss
2.0
30
25
1 1.55
20
15
10
10a
10
10'
10
10a
10
10a
10
Iteration
Iteration
(a) House
(b) VK
Figure 3: RMSE on the test set during training for two node regression datasets.
4.5 VISUALIZING PREDICTIONS
To investigate the performance of BGNN, we plot the final predictions of trained models for ob- servations in the training set. Our motivation is to scrutinize which points are correctly classified by different models. Figure displays the predictions of GBDT, GNN, Res-GNN, and BGNN models as well the true target value. To better understand the predictions of the BGNN model, in Figure [c) we show the values predicted by GBDT that was trained as a part of BGNN. This experiment is performed on House dataset, the plots for other datasets show similar trends and can be found in the supplementary materials.
Several observations can be drawn from these figures. First, the true target values change quite smoothly within local neighborhoods; however, there are a few outliers: single red points among many blue points and conversely. These points can mislead the model during the training, predicting
8

---

Published as a conference paper at ICLR 2021
(a) True
(h) GBDT
(c) GNN
An
a5
30
25
20
15
10
105
(d) Res-GNN
(e) GBDT BGNN
(1) BGNN
Figure 4: House dataset. True labels and predictions by trained GBDT, GNN, Res-GNN, and BGNN models (training points only). Point coordinates correspond to BGNN learned representations in the first hidden layer. Color represents the final predictions made by each model.
the wrong target value for many observations in the outliers' local neighborhoods. Hence, it is important for a model make smoothed predictions in the local neighborhoods.
Second, comparing the prediction spaces of GBDT, GNN, Res-GNN, and BGNN models we can observe that predictions for GBDT are much more grainy with large variations in the neighborhoods of the vertices (high quality images can be found in the supplementary materials). Intuitively, because the GBDT model does not have access to the graph structure, it cannot propagate its predictions in the nodes' vicinity. Alternatively. GNN, Res-GNN, and BGNN can extrapolate the outputs among local neighbors, smoothing out the final predictions as seen in Figures [c)) 4(d) 4())
Third, focusing on the values of predictions (color bars on the right of each plot) of GBDT, GNN, and BGNN models we notice that the scale of final predictions for GBDT and BGNN models closely aligned with the true predictions, while GNN's predictions mismatch the true values by large margin. Our intuition is that the expressive power of GBDT learn piecewise decision boundaries common in tabular datasets helps GBDT and BGNN to properly tune its final predictions with respect to the true range values. In contrast, GNN relics solely on ncural layers to learn complex decision rules.
Another observation comes from looking at the values predicted by GBDT trained part of BGNN (see Figure 4(e).. While this GBDT model is initialized using the true target labels, it was not forced to predict the target during the training. Interestingly, this model shows the same trend and clearly captures the regions on high/low target values. On the other hand, GBDT trained as part of BGNN much more conservative: than the true one. We hypothesize that GBDT is trained to scale its predictions to make them more suitable for further improvements by GNN.
all datasets, the range of predicted values significantly smaller
CONCLUSION
We have presented BGNN, novel architecture for learning on graphs with heterogeneous tabular node features. BGNN takes advantages of the GBDT model to build hyperplane decision boundaries that are common for heterogeneous data, and then utilizes GNN to refine the predictions using relational information. Our approach is end-to-end and can be incorporated with any message-passing neural network and gradient boosting method. Extensive experiments demonstrate that the proposed architecture is superior strong existing competitors in terms of accuracy of predictions and training time. possible direction for future research is to analyze whether this approach is profitable for graph-level predictions such as graph classification subgraph detection.

---

Published as a conference paper at ICLR 2021
ACKNOWLEDGMENTS
The authors thank the Anonymous Reviewers for their reviews and Anton Tsitsulin for kindly sharing VK data. Liudmila Prokhorenkova also acknowledge the financial support from the Ministry of Education and Science of the Russian Federation the framework of MegaGrant 175-15-2019-190 and from the Russian President grant supporting leading scientific schools of the Russian Federation NSh-2540.2020.1.
REFERENCES
Sercan O Arik and Tomas Pfister. Tabnet: Attentive interpretable tabular learning. arXiv preprint arXiv:1908. 0744004442222 2020.
Sarkhan Badirli, Xuanqing Liu, Zhengming Xing, Avradeep Bhowmik, and Sathiya S Keerthi. Gradient boosting neural networks: Grownet. arXiv preprini 27X11:2000.07971, 2020.
Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, al. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv:1806.01261, 2018.
Candice Bentéjac, Anna Csörgö, and Gonzalo Martinez-Muñozz A comparative analysis of gradient boosting algorithms. Artificial Intelligence Review, pp. 1-31,20 2020.
Sergio Casas, Cole Gulino, Renjie Liao, and Raquel Urtasun. Spatially-aware graph neural networks for relational behavior forecasting from sensor data. arXiv preprint arXiv: (910.00999000333 2019.
Djork-Ame Clevert, Thomas Unterthiner. and Sepp Hochreiter. Fast and accurate deep network learn- ing by exponential linear units (clus). In 4th International Conference on Learning Representations, 2016.
Feng, Yang Yu, and Zhi-Hua Zhou. Multi-layered gradient boosting decision trees. In Advances in neural information processing systems, pp. 3551-3561, 2018.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv
preprint arXiv: : 02428,. 2019.
Matthias Fey. Jan E Lenssen, Christopher Morris, Jonathan Masci, and Nils Kriege. Deep graph
matching consensus. In International Conference Learning Representations, 2019.
Jerome Friedman. Greedy function approximation: a gradient boosting machine. Annals of statistics, pp. 1189-1232, 2001.
Hussein Hazimeh, Natalia Ponomareva, Petros Mol, Zhenyu Tan, and Rahul Mazumder. The tree ensemble layer: Differentiability meets conditional computation. In 37th International Conference on Machine Learning (ICMI. 2020), 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. In Conference on Neural Information Processing Systems, 2020a.
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. In International Conference on Learning Representations, 2020b.
Junteng Jia and Austin Benson. Outcome correlation graph neural network regression. arXiv preprint arXiv:2002.08277 082744 2020.
Harmanpreet Kaur, Harsha Nori, Samuel Jenkins, Rich Caruana, Hanna Wallach, and Jennifer Wort- Vaughan. Interpreting interpretability: Understanding data scientists' use of interpretability tools for machine learning. In Proceedings of the 2020 CHI Conference on Human Factors in Computing Systems, 2020.
10

---

Published as a conference paper at ICLR 2021
Guolin Ke, Qi 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 30. 2017.
Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks. In Advances in Neural Information Processing Systems, pp. 7092-7101, 2019.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate:
Graph neural networks meet personalized pagerank. In International Conference on Learning Representations, 2019.
Pan Li, Zhen Qin, Xuanhui Wang, and Donald Metzler. Combining decision trees and neural networks for learning-to-rank in personal search. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 2032-2040, 2019.
Andreas Loukas. What graph neural networks cannot learn: depth vs width. In International
Conference on Learning Representations, 2020.
Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the universality of invariant networks. In International conference on machine learning, pp. 4363-4371. PMLR, 2019.
Nina Mazyavkina, Sergey Sviridov, Sergei Ivanov, and Evgeny Burnaev. Reinforcement learning for combinatorial optimization: A survey. arXiv preprint arXiv:2003.03600 2020.
Kelley Pace and Ronald Barry. Sparse spatial autoregressions. Statistics Probability Letters, 33 (3):291-297, 1997.
Ben Peters, Vlad Niculae, and André FT Martins. Sparse eqquence-to-sequence models. In Proceed- ings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. 1504-1519, 2019.
Sergei Popov, Stanislav Morozov, and Artem Babenko. Neural oblivious decision ensembles for deep learning tabular data. In International Conference Leurning Representations, 2019.
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, pp. 6638-6648, 2018.
Yuxiang Ren, Bo Liu, Chao Huang, Peng Dai, Liefeng Bo, and Jiawei Zhang. Heterogeneous deep graph infomax. arXiv preprint 1511:v/911.0853: 2019.
Benedek Rozemberczki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. arXiv preprint arXiv::9099 /3021, 2019.
Victor Garcia Satorras and Joan Bruna Estrach. Few-shot learning with graph neural networks. In International Conference Learning Representations, 2018.
Weiping Song, Chence Shi, Zhiping Xiao, Zhijian Duan, Yewen Xu, Ming Zhang, and Jian Tang. Autoint: Automatic feature interaction learning via self-attentive neural networks. In Proceedings of the 28th ACM International Conference on Information and Knowledge Management, pp. 1161-1170, 2019.
Jonathan M Stokes, Kevin Yang, Kyle Swanson, Wengong Jin, Andres Cubillos-Ruiz, Nina M Donghia, Craig MacNair. Shawn French. Lindsey A Carfrae. Zohar Acker-nc et al. deep learning approach to antibiotic discovery. Cell, 180(4):688-702. 2020.
Jianing Sun, Wei Guo, Dengcheng Zhang, Yingxue Zhang, Florence Regol, Yaochen Hu, Huifeng Guo, Ruiming Tang, Han Yuan, Xiuqiang He, and Mark Coates. A framework for recommending accurate and diverse items using bayesian graph convolutional neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 2039, 2020.
11

---

Published as a conference paper at ICLR 2021
Ke Sun, Zhouchen Lin, and Zhanxing Zhu. Adagen: Adaboosting graph convolutional networks into deep models. arXiv preprint arXiv:1908.05081, 2019.
Kiran K Thekumparampil, Chong Wang, Sewoong Oh, and Li-Jia Li. Attention-based graph neural network for semi-supervised learning. arXiv preprint arXiv::805 0et::888300333.3 03735, 2018.
Anton Tsitsulin, Davide Mottin, Panagiotis Karras, and Emmanuel Müller. Verse: Versatile graph embeddings from similarity measures. In Proceedings of the 2018 World Wide Web Conference, pp. 539-5599--- 548, 2018.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. International Conference on Learning Representations, 2018.
Duo Wang, Mateja Jamnik, and Pietro Lio. Abstract diagrammatic reasoning with multiplex graph networks. In International Conference on Learning Representations, 2020.
Man Wu, Shirui Pan, Chuan Zhou, Xiaojun Chang, and Xingquan Zhu. Unsupervised domain
adaptive graph convolutional networks. In Proceedings of The Web Conference, 2020.
Yuxin Xiao, Zecheng Zhang, Carl Yang, and Chengxiang Zhai Non-local attention learning on large heterogeneous information networks. In 2019 IEEE International Conference Big Data (Big Data), pp. 978-987 IEEE, 2019.
Yongxin Yang, Irene Garcia Morillo, and Timothy M Hospedales. Deep neural decision trees. arXiv preprint IrXiv::808 06988, 2018.
Zhi-Hun Zhou and Ji Feng. Deep forest. National Science Review, 6(1):74-88) 0614--6,111 2019.
12

---

Published as a conference paper at ICLR 2021
A FURTHER RELATED WORK
To the best of our knowledge, there are no approaches combining the benefits of GBDT and GNN models for representation learning on graphs with tabular data. However, there are many attempts to adapt non-graph neural networks for tabular data or to combine them with gradient boosting in different ways.
Several works (Popov et al. 2019; Yang et al. 2018 Zhou & Feng 2019 Feng et al. 2018 Hazimeh
al. 2020) attempt mitigate the non-differentiable nature of decision trees. For example, Popoy et al. 2019) proposed to replace hard choices for tree splitting features and splitting thresholds with their continuous counterparts, using o-entmax transformation (Peters et al. (019). While such an approach becomes suitable for union of decision trees with GNN, the computational burden of training both end-to-end becomes a bottleneck for large graphs.
Another method (Badirli et al. 2020) uses neural networks weak learners for the GBDT model. For graph representation problems such as node regression, one can replace standard neural networks with graph neural networks. However, training different GNN weak classifiers at once would be exhaustive. Additionally, such a combination lacks some advantages of GBDT, like handling heterogeneous and categorical features and missing values. An approach called AdaGCN (Sun et al., 2019) incorporates AdaBoost ideas into the design of GNNs in order to construct deep models. Again, this method does not exploit the advantages of GBDT methods.
Finally, Li et al. (019)) investigated different ways of combining decision-tree-bee neural networks. While the motivation is similar ours - get the benefits of both types of models the paper focuses specifically on learning-to to-rank problems. Additionally, while some of their methods are similar spirit to Res-GNN, they do not update GBDT in an end-to-end manner, which is a substantial contribution of the current research.
models and
B HYPERPARAMETERS
Parameters in brackets {} are selected by hyperparameter search on the validation set.
LightGBM: number of leaves is {15, 63), || 0, boosting type is gbdt, number of epochs is 1000, early stopping rounds is 100.
CatBoost: depth is (4, 6). ||||| O, number of epochs is 1000, early stopping rounds is 100.
FCNN: number of layers is {2. 3}. dropout is {0., 0.5), hidden dimension is 64, number of epochs is 5000, early stopping rounds is 2000.
GNN: dropout rate is {0., 0.5}. hidden dimension is 64, number of epochs is 2000, early stopping
rounds is 200. GAT, GCN, and AGNN models have convolutional layers with dropout and ELU activation function (Clevert et al. 2016). APPNP has two-layer fully-connected neural network with dropout and EL.U activation tollowed by convolutional layer with k 10 and a = 0.1. We use eight heads with eight hidden neurons for GAT model.
Res-GNN: dropout rate is {0., 0.5 hidden dimension 64, number of epochs is 1000, early stopping rounds is 100. We also tune whether to use solely predictions of CatBoost model or append them to the input features. CatBoost model is trained for 1000 epochs.
BGNN: dropout rate is (O., 0.5). hidden dimension is 64, number of epochs is 200, early stopping rounds is 10, number of trees and backward passes per epoch is { [10, 20), depth of the tree is 6. We also tune whether to use solely predictions of CatBoost model or append them to the input features.
For models, we also perform a hyperparameter search on learning rate in {0.1, 0.01 Every hyperparameter setting is evaluated three times and average is taken. We five random splits for train/validation/test with 0.6/0.2/0.2 ratio. The average across five seeds is reported in the tables.
C REGRESSION DATASETS
In House dataset Paaee& & Barry 1997). nodes are the properties, edges connect the proximal nodes, and the target is the property's 's price. We use the publicly available dataset (Pace & Barry 1997) of
13

---

Published as a conference paper at ICLR 2021
all the block groups in California collected from the 1990 Census. We connect each block with at most five of its nearest neighbors if they lie within a ball of a certain radius, as measured by latitude and longitude. We keep the following node features: MedIne, HouseAge, AveRooms, AveBedrms, Population, AveOccup.
County dataset (Jia & Benson 2020) is county-level election map network. Each node is county, and two nodes are connected if they share border. We consider node features coming from the 2016 year. These features include DEM, GOP, MedianIncome, MigraRate, BirthRate, DeathRate, BachelorRate, UnemploymentRate We follow the setup of the original paper and select UnemploymentRate as the target label. We filter out all nodes in the original data if they do not have features.
VK dataset (Tsitsulin et al. 2018) comes from a popular social network where people are mutually connected based on friendships, and the regression problem is to predict the age of person. We use an open-access subsample of the VK social network of the first 1M users | Then, the dataset has been preprocessed to keep only the users who opt in to share their demographic information and preferences: country, city, has mobile, last seen, platform, sew.ssee-llaffom, relation, university.
political, religion id, alcohol, smoking,
Wiki dataset (Rozemberczki et al. 2019) represents page-page network on a specific topic (squirelss) with the task of predicting average monthly traffic. The features are bag-of-words words for informative nouns (3148 in total) that appeared in the main text of the Wikipedia article. The target is the average monthly traffic between October 2017 and November 2018 for each article.
Avazu dataset (Song et al., 2019) represents a device-device network, with two devices being connected if they appear on the same site within the same application. For this dataset, the goal is to predict click-through-rate (CTR) for each device. We take the first 10M rows from the publicly available train log of user clicks We compute CTR for each device id and filter those ids that do not have at least 10 ad displays. We connect two devices if they had ad displays on the same site id from the same application id. The node features are anonymized categories: CI, C14, C15, C16, C17, C18. C19, C20, C21.
D CLASSIFICATION DATASETS
For node classification, we consider three types of node features: sparse (Slap and DBLP), and homogeneous (OGB-ArXiv).
heterogeneous (VK and House),
For House and VK, we transform the original numerical target value with respect to the bin it falls to. More specifically, for VK we consider the classes 20, 20 25, 25 30 ......,, 45 50, >> 50 for the age attribute. Similarly, for House dataset we replace the target value with the bin falls to in the range [1, 1.5, 2, 2.5). Hence, there are and 5 classes for VK and House, respectively.
For datasets with sparse features, we consider two datasets coming from heterogeneous information networks (HIN), where nodes have few different types. A common way represent HIN is through meta-paths, i.e., a collection of all possible paths between nodes of particular type. For example, for citation network, one may specify paths of the type paper-author-pappe paper (PAP) and the type paper- subject-paper (PSP). Then the original graph is ap- proximated as several adjacency matrices for differ- ent types.
Table 5: Summary of classification datasets.
SLAP
DBLP
OGB-ArXiv
Nodes
20419
14475
169343
Edges
172248
40269
1166243
Features
2701
5002
128
Classes
15
4
40
Min Class
103
745
29
Max Class
534
1197
27321
DBLP dataset (Ren et al. (019)) is a network with three node types (authors, papers, conferences) and four target classes of the authors (database, data mining, information retrieval, and machine learning). To obtain a single graph, we use the adjacency matrix for the relation APA, which closely reflects the relationships between authors. Each author has a bag-of-words representation (300 words) of all the abstracts published by the author. Furthermore, for every node, we compute the degrees for all
https: http::/wwwwkk. http///wwwwaagg.geee/e www. ctteruu-ctr-ppe
14

---

Published as a conference paper at ICLR 2021
types of relations and append them additional node features. Namely, we have two additional node features corresponding to degrees for paper nodes in APA and APCPA adjacency matrices.
SLAP dataset (Xiao et al. 2019) is multiple-hut network in bioinformatics that contains node types such as chemical compound, gene, disease, pathway, etc. The goal is to predict one 15 gene types. To obtain single graph,
the adjacency matrix for the relation GG between genes. Each gene has 3000 features that correspond to the extracted gene ontology terms (GO terms). As for DBLP, we compute the degrees for all types of relations and append them as additional node features.
As a dataset with homogeneous node features we consider OGB-ArXiv (Hu et al. 2020a). The node features correspond
728-dimensional feature vector obtained by averaging the embeddings of words in the title and abstract. Note that for this particular dataset we used the implementation of GAT as backbone architecture for GNN, Res-GNN, and BGNN models. This model scored the top place on the leaderboard A summary of statistics for all datasets is outlined in Table
E COMPARISON OF GNN MODELS
In this section, we show the exact RMSE values and time for all tested GNN models on all regression datasets. We consider several state-of-the-arr GNN models that include GAT (Veličković et. 2018) GCN (Kipf & Welling 2017), AGNN (Thekumparampil et al. 2018). and APPNP (Klicpera et al. 2019.
Table demonstrates that for all considered models BGNN and Res-GNN achieve significant increase performance compared to vanilla GNN. Additionally, end-to-end training of BGNN achieves typically better results than straightforward implementation of Res-GNN.
Table 6: Summary of our results for different GNN architectures for node regression.
House
County
VK
Wiki
Avazu
Method
RMSE
Time (s)
RMSE
Time (s)
RMSE
Time (s)
RMSE
Time (s)
RMSE
Time
GON GAT
GNN
Res-GNN
0.54 = 0.01
0.1 + 0.1
56 7
2:
1 0.06
1,33 0.08
1
+
7.07 0.30
7.22 = 0.19
41 +
42 02::44
45916 4527
46747 + 4639
31 +-9
15::1
0.109 noI
0.113 001
9=
2
BGNN
20
6,98 0.21
3745
0.109
7,25
Res-GNN
0.9 0.0
2
1.35 +: 0.09
11 =
7.03 = 0.20
52
44876
3777
21 5:5
0,111 0.02
9=
BGNN
0,54 1: 0.01
41 1 15
1.33 à 0.13
12
7,12 =: 0.21
76 1::1: 6
47426 1: 4112
22 1: 11
0,107 1: 0.01
4 1
APPNP AGNN
GNN
0.59 0.0
5
1,45 0.08
28 1.3
7,26 0.20
48
45982
3058
1::1::
0.113 0.02
14=
0.52
0.111
BGNN
0.49 0.01
1,28 0.08
3
6.89 0.21
$3080
5117
37
0.108 0.02
GNN
0.69 = 0.01
68 +:
1.5+
34 10
13.23
0.12
81 #:3
$3426
4159
49 #:26
0.113 2:113:000 0.01
24
Res-GNN
0.67 2 0.0
58 12
0.12
19:1: 10
13.06 0.17
76
53206 4593
2:
0.110 0.01
15
17:16
50
0,108
15

---

Published as a conference paper at ICLR 2021
F LOSS CONVERGENCE
In Figure 5, we plot RMSE on the test set during training for the remaining datasets - County, Wiki, and Avazu. These results confirm that BGNN converges to its optimal value within the first iterations (for k = 20). Note that on the Wiki dataset, similarly to Figure 3 Res-GNN convergence similar GNN for the first 100 iterations and then the loss of Res-GNN decreases faster than of GNN.
Test
Test loss
30000
46000
Reston
Ranaton
County
(b) Wiki
Avazu
Figure 5: Summary of RMSE of test set during training for node regression datasets.
16


Reviews:
[{"review_id": "bQ6Xdk6o7-o", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 9, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents a new architecture called BGNN (Boost-GNN), which combines the benefits of GNNs (Graph Neural Nets) with GBDTs (Gradient Boosted Decision Trees).\n\nBasic idea:\n* GBDTs work well with *heterogeneous* tabular data.\n* GNNs work well on *graphs* with *homogeneous* sparse features.\n* BGNNs work well on *graphs* where the nodes contain *heterogeneous* tabular data.\n* BGNNs is optimized end-to-end and seems to obtain great SOTA results!\n\nAn example of the data BGNN works well on is in social networks. E.g. each node could be a person with heterogeneous characteristics such as age, gender, graduation date.\n\nThe main trick is in how to train this end-to-end effectively. This is done by iteratively adding trees that fit the GNN gradient updates, allowing the GNN to *backpropagate* into the GBDT.\n\nMore in detail:\n* GBDTs make a prediction for each node in the graph.\n* The GNN reads the output of the GBDTs and corrects the predictions based on the graph structure.\n* When doing gradient descent on the GNN the authors critically also optimize with respect to the input features. The difference between the optimized input features and the original input features becomes the new objective for next round of update on the decision trees.\n\nResults seem very strong across all tasks considered in the paper.\n\nStrengths:\n* The paper presents an interesting and convincing analysis of why GBDTs are so advantageous for tabular data, while GNNs are the best choice for graph data.\n* The combination of GNNs and GBDTs is not trivial. Several papers are cited attempting the combination of neural nets and gradient boosting, but they are reported to be computationally more expensive and not as powerful.\n* The detail about computing updated targets for GBDTs while doing gradient descent on the GNN seems particularly interesting and creative.\n* The results obtained by this paper are impressive, surpassing SOTA models by considerable margins.\n* The paper also finds that representations learned with BGNN have more discernible structure, suggesting that they are more interpretable.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "avkOuSvSBIB", "reviewer": "AnonReviewer3", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Review: This paper proposes a fusion of GBDT and graph neural network that works on graphs with heterogeneous tabular features. Previous approaches are computationally heavy and do not consider graph-structured data and suffer from lack of relational bias imposed in GNNs. The proposed method is a new ensemble tree method which alternates between functional gradient step in GBDT (which train on the current latent features) and SGD training of graph neural network (to generate the latent features which are fed into the subsequent trees).\n\nReasons for score:\n\nOverall, I am leaning toward rejecting this paper. Overall, the paper is an empirically motivated paper focusing on the construction of pipelines which depend on already established methods, GBDT and GNN. Having advantages of both methods is nice, but it is hard to glean why this proposed method works well on theoretical basis.\n\n+Positives:\n- The proposed end-to-end training combining GBDT and GNN is easy to implement and clearly described.\n\n- improving GBDT to work on graph-structured data is a novel idea.\n\n- Comparison in the experimental section considers a handful of state-of-the-art approaches.\n\nConcerns:\n- Experimental results are mainly concerned with regression tasks. Having some results on classification would be nice.\n\n- The contribution of the paper is mainly empirical and offers little intuition on why the proposed method improves upon GNN and GBDT.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "_zmwep6CzBO", "reviewer": "AnonReviewer4", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper aims to learn from graphs with tabular node features. Existing methods are only designed to handle either tabular data, such as gradient boosting decision tree (GBDT), or graph-structured data, such as graph neural networks (GNNs). This paper naturally extends GBDT to deal with graph-structured data and train it together with GNN in end-to-end fashion.\n\nThis paper is clearly written and easy to follow. I enjoyed reading this paper. The idea is clear and well-motivated. The way of combining GBDT and GNN looks natural and reasonable. The essence of GBDT is to approximate the gradient of the undifferentiable part of the model by selecting a weak learner h from H (eq. 2). This proposed training method seems valid and effective on semi-supervised regression.\n\nMy main concern is the proposed method is not working well on semi-supervised classification tasks. It performs worse than CatBoost (pure GBDT method without using the graph) on the two datasets Slap and DBLP for semi-supervised node classification, which is probably why the authors put the experiments in the Appendix. \n\nSince node classification is a benchmark task and, in my opinion, more common and important than semi-supervised regression, I have some doubts of the practicality of the proposed method. \n\n============Post Rebuttal=============================\n\nThanks for the additional experiments and the updates. The new results are informative. \n\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "AgE8-U_1g2S", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "**Summary**\nThe paper proposes a GNN model by incorporating gradient boosting. In the proposed BGNN, the input feature on the graph is learned by the gradient boosting model. The processed feature then becomes a new feature for a GNN model following the gradient boosting. Several experiments demonstrate the improvement of the performance for a tabular feature and graph-structured datasets. The running time of Res-GNN/BGNN is shown to have a significant reduction as compared to the plain GNN methods.\n\n**Comments and questions**\n1.  The paper proposed a simple model combining Boosting and GNN methods, which can effectively learn the heterogeneous features of graph-structured data.\n2.  The performance of BGNN, including the training speed and regression error, is good as compared to the GNNs for datasets with tabular features.\n3.  What is the performance of the proposed model on other node property prediction tasks such as Open Graph Benchmark?\n4. The BGNN has two stages: a gradient boosting for graph features and graph neural networks for graph-structured data, including features plus graph structure. So, the computational time should be the sum of time of GBDT and GNN. Why is the time becoming smaller than the plain GNN for the same datasets?\n5. How many layers do the BGNN exactly use for experiments?\n6. Will the GBDT apply to link prediction tasks? \n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes an interesting architecture that dues Graph Neural Networks (GNN) and Gradient Boosting Decision Tree. This new architecture works on graphs with heterogeneous tabular features and BGNNs work well on graphs where the nodes contain heterogeneous tabular data and is optimized end-to-end and seems to obtain great SOTA results. End to end learning is done by iteratively adding trees that fit the GNN gradient updates, allowing the GNN to backpropagate into the GBDT. All reviewers agreed that the idea is interesting, the paper is well-written, and the results found in the paper are impressive. In addition, author response satisfactorily addressed most of the points raised by the reviewers, and most of them increased their original score. Therefore, I recommend acceptance.
Decision: Accept (Poster)