Effective and Efficient Federated Tree Learning on Hybrid Data
Authors: Qinbin Li
Chulin Xie
Xiaojun Xu
Xiaoyuan Liu
Ce Zhang
Bo Li
Bingsheng He
Dawn Song
Venue: ICLR 2024 poster (2024)
Keywords: federated learning
Primary area: societal considerations including fairness, safety, privacy

Abstract: Federated learning has emerged as a promising distributed learning paradigm that facilitates collaborative learning among multiple parties without transferring raw data. However, most existing federated learning studies focus on either horizontal or vertical data settings, where the data of different parties are assumed to be from the same feature or sample space. In practice, a common scenario is the hybrid data setting, where data from different parties may differ both in the features and samples. To address this, we propose HybridTree, a novel federated learning approach that enables federated tree learning on hybrid data. We observe the existence of consistent split rules in trees. With the help of these split rules, we theoretically show that the knowledge of parties can be incorporated into the lower layers of a tree. Based on our theoretical analysis, we propose a layer-level solution that does not need frequent communication traffic to train a tree. Our experiments demonstrate that HybridTree can achieve comparable accuracy to the centralized setting with low computational and communication overhead. HybridTree can achieve up to 8 times speedup compared with the other baselines.

Published as a conference paper at ICLR 2024
EFFECTIVE AND EFFICIENT FEDERATED TREE LEARN- ING ON HYBRID DATA
Qinbin Li UC Berkeley
Chulin Xie UTCC
ginbim@berkellyy edu
chulimx2e111imoiss
Xiaojun Xu UIUC xiaojun3illinois.ed
Xiaoyuan Liu UC Berkeley
xiacyuamiueberrkeleeyy edu edu
Ce Zhang
Bo Li
Together AI, University of Chicago cez@uchicago. edu
UIUC, University of Chicago bol bol@uchicago.edi
Bingsheng He
Dawn Song
National University of Singapore hebs@comp nus. edu. sg
UC Berkeley
devnsongeberkkeleyyyo
ABSTRACT
Federated learning has emerged as a promising distributed learning paradigm that facilitates collaborative learning among multiple parties without transferring raw data. However, most existing federated learning studies focus on either horizontal vertical data settings, where the data of different parties are assumed be from the same feature or sample space. In practice, common scenario is the hybrid data setting, where data from different parties may differ both in the features and samples. To address this, propose HybridTree, novel federated learning approach that enables federated tree learning on hybrid data. We observe the existence of consistent split rules in trees. With the help of these split rules, theoretically show that the knowledge of parties can be incorporated into the lower layers of tree. Based that does not need frequent communication traffic to train a tree. Our experiments demonstrate that HybridTree achieve comparable accuracy the centralized setting with low computational and communication overhead. HybridTree can achieve up times speedup compared with the other baselines.
theoretical analysis, we propose layer-level solution
INTRODUCTION
While machine learning models benefit from large training data, data are usually distributed among multiple parties and cannot be transferred due privacy concerns. Federated Learning (FL) (McMa- han et al.) 2016: Kairouz et al. 2019 Yang et al. 2019) has been a popular direction to address the above challenge. Existing FL studies mainly focus horizontal or vertical FL settings. horizontal FL (HFL), the data of each party shares the same feature space but different sample spaces (e.g., keyboard input behavior of different users). vertical FI. (VFL.,, the data of each party shares the same sample space but different feature spaces (e.g., data of bank and insurance company the same user group).
In practical scenarios, hybrid FL is quite common, yet it has not been extensively explored in the current literature. To illustrate this, let's consider a payment network system provider like SWIFT aiming to train model for detecting anomalous transactions. In this case, the provider collaborate with multiple banks, which can contribute user-related features for each transaction. Consequently, the data involved in this setting exhibits hybrid FL configuration, where the data between the

---

Published as a conference paper at ICLR 2024
payment network system and the banks originate from different feature spaces, and the data among different banks stem from distinct sample spaces. The hybrid FL setting is particularly prevalent in real-world applications, especially when dealing with tabular data. Each participating party only possesses partial instances or features of the overall global data, leading to the need for effective strategies leverage such hybrid data for collaborative learning.
On the other hand, the Gradient Boosting Decision Tree (GBDT) is a powerful model, especially for tabular data, which has won many awards in machine learning and data mining competitions (Chen & Guestrin, 2016, Ke et al. 2017). There have been some studies (Cheng et al. 2019 Tian et al. 2020; et al., 2023) that design federated GBDT algorithms in the horizontal or vertical FL setting. However, none of the studies work on the hybrid FL setting. They aggregate the information of all parties when training each tree node, and the aggregation strategy relies on the consistency of sample or feature space between different local data. Moreover, high communication and computation overhead are introduced in these node-level solutions. In the presence of hybrid data setring, challenging design knowledge aggregation mechanism efficiently and effectively.
To solve the above challenge, we provide key insight for federated tree training with our theoretical analysis: parties contribute simple and neat knowledge to FL which are formulated as split rules (meta-rule), and these rules can be incorporated at once in each round. Based on the insight, instead of using node-level solutions that introduce complicated aggregation mechanisms with cryptographic techniques, we design a novel layer-level solution named HybridTree. Hybrid'Tree integrates party- specific knowledge by appending layers the structure. Our experiments show that HybridTTre can achieve comparable accuracy compared with centralized training while achieving up to eight times speedup compared with node-level solutions.
Our work has the following main contributions.
We observe the existence of meta-rules in trees. Based on the observation, propose tree transformation technique to enable the reordering of split points without compromising the model performance, which supports using only specific features for splitting in the last layer.
Motivated by the effectiveness of our tree transformation, propose tree algorithm on hybrid data, which adopts a novel layer-level tree training strategy that incorporates the parties' knowledge by appending layers.
federated
We conduct extensive experiments simulated and natural hybrid federated datasets. Our experiments show that HybridTree is much more efficient than the other baselines with a close accuracy to centralized training.
2 BACKGROUND AND RELATED WORK
2.1 GRADIENT BOOSTING DECISION TREE
GBDT is a popular model which shows superior performance in machine learning competitions (Chen & Guestrin 2016; Ke al. 2017) and real-world applications (Richardson et al. 2007 Kim et al. 2009). It usually achieves better model performance than neural networks for tabular data McElfresh al. 2023) The GBDT model contains multiple decision trees. Each tree has two types of nodes: internal nodes that split the input into left or right with a split condition and leaf nodes that output the prediction values. Given an input instance, the final prediction value computed by summing the prediction values of all trees.
The training of GBDT is a deterministic process. In each iteration, new tree is trained fit the residual between the prediction and the target. Formally, given a loss function é and dataset D [xx, y4 ) GBDT minimizes the following objective function
L >' UVE U.) (((W))
where ÿJ is the prediction value, 2(-)) is a regularization term and 6g denotes the parameter of k-th decision tree. For the complete training process of GBDT, please refer to Appendix B.2
2

---

Published as a conference paper at ICLR 2024
2.2
FEDERATED GBDT
There have been some federated GBDT algorithms (Li et al. 2023; Tian et al. 2020) Cheng et al.
2019: Zhao et al. 2018 Li al., 2020; Fang al., 2021; Wu al. 2020 Wang
2022
Maddock et al. 2022) for horizontal or vertical FL. Most existing studies (Li et al. [2023] Tian
et al. et al. histograms, different parties when training each node. Different techniques such as homomorphic encryption, secure multi-party computation, and differential privacy are used to protect the transferred information. The node-level solutions suffer from frequent communication traffic and additional computation overhead especially when using cryptographic techniques for privacy protection. Several studies (Li et al. 2020] Zhao et al. 2018) for horizontal FL adopt tree-level solutions. They transfer trees in each round, i.e., each party locally trains GBDTs and transfers them the next party for boosting, The tree-level solutions may have severe accuracy loss since only local data is used when training each tree. Also, they are not applicable in vertical FL setting since some parties do not have labels to train the local trees. Moreover, all existing federated GBDT studies do not investigate the hybrid FL setting. We have summarized existing federated GBDT studies in Appendix D
2020 Cheng et al. 2019 Fang al.) 2021 Wu et al. 2020 Wang al.) 2022 Maddock
2022 adopt node-leve solution that merges the knowledge which is usually represented by
2.3 FEDERATED LEARNING ON HYBRID DATA
FL on hybrid data is rarely exploited in the current literature. Zhang et al. (2020) propose to train feature extractor for every feature in clients, and the server aggregates the feature extractors by feature correspondingly. Such feature-level aggregation may incur huge computation and memory overhead when the dimension is high. [Liu et al. (2020) apply transfer learning in a two-party setting. Two parties locally train the neural networks and a mapping function used to associate the local outputs and the labels. Both studies are designed for neural networks and are not applicable to trees.
MOTIVATION AND THEORETICAL SUPPORT
3.1 PROBLEM STATEMENT
In this paper, we consider hybrid FL. setting where multi- ple parties jointly train a GBDT model without transferring data. For case of presentation, we call the parties with the labels as hosts and the parties without labels as guests. For simplicity, host with multiple guests. Specifically, we assume that host seeks the help of N guests who have additional features of samples in the host for FL. (e.g., a payment system seeks the help of banks for fraud detection). We use D' = (x, y) x E Rda } to denote the data of the host and D Dg, [x x E Rd, to denote the data of guest i. We use to denote the instance ID set of the host and Is to denote the instance ID set of guest (I = U.Y I.). Like existing VFL studies (Cheng et al. 2019 Vepakomma et al. 2018), we assume that the data of the host and guests have already been linked (i.e.. the host knows whether a guest has additional features for an instance in its local data), which can be achieved by matching anonymous IDs or
Lubel
Host features
Guest features
Guest party
start from scenario involving single
Host party
Guest party N
Figure 1: Hybrid data partitioning.
record linkage (Gkoulalas- Divanis et al..
2021
3.2
META- AND TREE TRANSFORMATION
As we mentioned in Section 2.2 most existing federated GBDT studies try to aggregate the statistics (e.g., histograms) of each party to update a tree node. When it comes to hybrid FL, one may design a complicated framework that utilizes cryptographic techniques to aggregate the statistics, which would incur large computation and communication overhead. However, is it necessary to use statistics of all parties to update every node? Next, to answer this question, present key insight: meta-rules widely exists in GBDTs Then, we show that we can transform trees to enable layer-level tree updating based on the meta-rules.
3

---

Published as a conference paper at ICLR 2024
P
Fns
Fn.
Y
Y
Y
1
Ph
1
Flu
Fg
F1z
Fg
L2
L
l/2
Ln
L2
Ln
L
Lz
In
(a) Meta-rule:
Fg
(b) Meta-rule: -Fh, O
Fg
Figure 2: Two examples of meta-rules. F is the split condition and L is the leaf value. In (a).
Fg > I.1 exists in both trees. (b), -Fh, - Fg + I.2 exists both trees.
20
Irspectio (h0)
F
Fh
Y
1
F
F
Y
26
L2
L
L2
L
L3
20
DE1-30
ADUI
A
(a) Evidence meta-rules
(b) Tree transformation
Figure 3: (a) The proportion of trees that have the same meta-rules. (b) Fg is split rule with the split feature from guests. F2 is split rule with the split feature from the host. represents leaf nodes.
Existence of Meta-Rules We start by investigating the properties of GBDTs in hybrid federated datasets. We use two datasets provided by PETs prize challenge (DrivenData). The datasets contain synthetic transaction data provided by a payment network system (host) and account data provided by multiple banks (guests). We train a GBDT model with 50 trees in the centralized setting by linking these datasets without privacy constraints. Analyzing the output model, we focus on split rules (i.e., the joint split condition from the root node to the leaf node) involving features from the guests. Interestingly, for these split rules, we observe that the same rule consistently appear over 90% of the trees. We present two examples in Figure 2 In Figure 2a the split rule Fg exists in both trees, i.e., the prediction value is deterministic if Fg is true. In Figure 2b the split rule -Fh, n F2 exists in both trees, i.c., the prediction value is deterministic if -1h, 7 is true. As long as it satisfies the split rule, the prediction value is independent of other features. For the sake of clarity, we define such split rules meta-rules.
Definition 1. (Meta- Given split rule ; n. L' where Fj is split condition, we call S meta-rule if P S) P(ylæ ( Fx)), VF. Fj [1,
In the context of tabular data, it is intuitive that guests often contribute simple and neat knowledge in the form of meta-rules. For example, if banks know that user account has already been closed, then the transactions made by this closed account have high probability of being anomalous. If patient's iWatch records an unstable heart rate in daily life, then the hospital may guess that the patient has heart disease combined with other measurements. To support our assumption, tabular datasets (details of the datasets are available in Section 5.1 to further verify the popularity of meta-rules. For each dataset, train GBDT model with 40 trees in the centralized setting. Figure (arrre33areeeee records the proportion of trees where the same meta-rule that determines the prediction value appears. We observe that most of the trees have the meta-rules in five datasets. Thus, in hybrid FI., to aggregate the knowledge of participants, we focus on how to incorporate the knowledge defined by these meta-rules during training efficiently and effectively.
use four
Tree Transformation based on Meta-Rule Based on the existence of meta-rules, it is not necessary to consider the statistics of all parties when updating each node. We look at a simple tree with depth 2 as shown in Figure 3hlas as example. We have the meta-rule Fg. i.e., the prediction is independent
4

---

Published as a conference paper at ICLR 2024
The best trsins a subtree.
The bost seuds internediate
grests.
Guests train the lower layen.
(b)
value by
Split value by guests
Leaf value
Figure 4: A comparison between node-level solution (a) and our layer-level solution (b). All parties jointly update each node in (a) while each party only updates segmented tree individually in (b).
of features Fj as long as Fg is true. We can transform Tree A to Tree B by reordering the split node Fg into last layer of the tree. We have the following theorems. The proofs are available in Appendix A of the supplementary material.
Theorem 2. Suppose Fg is meta-rule in Tree A. For any input instance E DD we have [x 0 = [[[xx0BB] i.e., the expectation of prediction value of Tree and Tree B are the same.
While the above theorem is based on Figure 3b with tree of depth two, it can easily be extended to the case with a larger depth of trees by considering F; as subtree with split features from guests and Fs, subtree with split features from hosts. To demonstrate that the split point with guest features can be reordered into the last layers while keeping the model performance, we have the following theorem.
Fg is meta-rule in tree 9 where Fg is split condition using the feature from the guests. For any tree path in tree 9 involving the split nodes Sm. we can always reorder the split nodes in the tree path such that Fg tree after the reordering as 8B, we have fx; A = [x 0B) for any input instance x E D.
Theorem 3. Suppose Sm == FI
the last layer. Moreover, naming the
From Theorem 3 based on the meta-rule contributed by the guests, we can reorder the split nodes such that the split feature from guests is in the last layers. Thus, it is not necessary to consider all features as possible split values in each tree node as we can incorporate the knowledge by just using features from guests in the last layers. Based this insight, we propose HybridTree, efficient and effective hybrid federated GBDT algorithm.
OUR METHOD: HYBRIDTREE
In this section, inspired and supported by our tree transformation based on meta-rules, we propose the HybridTree approach. In the training, HybridTree adopts a layer-wise training design, where the host party trains a subtree and the guest parties further update the bottom layers. Then, in the inference, as each tree is divided into multiple parties, the host and guest parties collaboratively build the split path of an input instance and make the prediction. Next, we introduce the training and inference processes in detail.
4.1 HYBRIDTREE TRAINING
Overview Existing node-level solutions for horizontal or vertical FL require all parties to com- municate and jointly update every node as shown in Figure aa). Supported by our theoretical analysis, we design layer-level solution as shown in Figure 4(b), where the host and guests train segmented trees individually without communication during local training. There are three steps in each round. First, the host trains subtree using its local features and labels. Then, the host sends the encrypted gradients of the instances in the last layer guests using additively homomorphic encryption (AHE) (Paillier 1999). Last, guests update the following lower layers of the tree using their local features and receive encrypted gradients, and send back the encrypted prediction values. During each round, the host and guests only communicate twice to incorporate the meta- knoweeeo from guests, which saves lot of communication traffic compared with node-level solutions.
5

---

Published as a conference paper at ICLR 2024
F,
F3
F6
ID
Fb
L1
2.3
-1
X
Y
1
① outputs the prediction position and sands to comesponding guests.
2
Guests predicts the leaf IDs with the reosived position.
F1
N
Y
F2
F3
Fb
Fb
F
F
Fb
Fb
Fb
Fb
Y
|
||Ai|]
|
|
|
Host
Guest
Guest
L
Host gets the prediction value of this distributed tree
Figure 5: The inference process of HybridTrree.
The detailed algorithm shown in Algorithm T Specifically, before training the model, the host initializes the prediction value to zero and generates key pairs for AHE, where the public key is sent to guests (Lines 1-4). For every pair guests, common key is generated and exchanged through Diffie- Hellman key exchange (Merkle 1978), which will be used later for secure aggregation (Bonawitz et al. 2016) (Lines 5-6). In each round, the host updates the gradients of the training data, which is used train subtree (Lines 7-9). The TrainTree() algorithm follows the typical GBDT training algorithm, which we present in Appendix B of the supplementary material. Then, for each last-layer node, the host sends the instance ID and last-layer gradients guests that have the corresponding instances (Lines 10-13). Note that gradients are computed based on the prediction value and the true label, and raw gradients may leak information about the labels. Thus, we apply AHE protect the gradients (Line 11), which supports the addition of encrypted values, After receiving the encrypted gradients, guests can compute the leaf values according to Eq, g while using the public key to sum encrypted gradients (Lines 16-21). After receiving the encrypted leaf values, the host aggregates and decrypts it using the private key and updates the prediction values (Lines 14-15).
In general, there are three steps in the whole training process: 1) The host party updates subtree individually (Lines 1-9); 2) The host party sends the encrypted intermediate results into the guest parties (Lines 10-13); The guest parties update the bottom layers individually and send back the encrypted prediction values (Lines 14-21). Since HybridTree does not require accessing all features and instances when updating each node, it can handle the hybrid data case where each party only has partial instances and features. Moreover, based on our analysis in Section B by updating the bottom layers using the guests' features, the meta-rule knowledge of the guest parties be effectively incorporated.
4.2 HYBRIDTREE INFERENCE
After HybridTree training, the whole model distributed among different parties, and collaborative inference is required to predict input instance like existing vertical FL studies (Cheng et al. (019).. We present the inference process in Figure Still, we assume that test data among different parties have already been linked by ID before inference. First, the host splits the input instance into a last-layer node using its subtree and sends the position of the predicted node to guests that have the instances. Then, the guests further split the instance with the received position and return the predicted leaf location. Last, the server averaged the prediction values of the received locations to get the final prediction value. During the whole prediction process, only two communication times needed and all test instances can be processed in parallel.
4.3 PRIVACY GUARANTEES
We provide the same privacy guarantee as existing vertical federated learning studies on GBDTs (Li et al. 2003 Cheng et al. 2019). We assume that all the parties are honest-but-curious, where they strictly follow the algorithm and do not collude with each other. During the training process, the host only receives the encrypted prediction values from guests and guests only receive the encrypted gradients from the host. Thus, there is no information leakage in the training. During the inference process, the host and guests only receive the predicted node locations from each other, without

---

// Update non-leaf layers Published as a conference paper at ICLR 2024
Algorithm 1:
The HybridTrre training algorithm
Input:
Host dataset DA, = {(x,, y:)]== with instance ID set I, guests' datasets Dr (i [N]), the depth of tree trained by the host Eg, the depth of tree trained by guests Ey. number of trees T, loss function f, regularization term X.
Output: The final model
* Conducted on host +/ HostTrain(Dp, En, Eg T,E);
Yp [0]
// Initialize prediction value to zero
kpubs Epri GencrateKeys()
// Generate homomorphic encryption keys
Send kpub to guests
for every pair of guests (G,, G)) + do
kij- &- DHKey()
// Generate common key through DH key exchange
for t 1.,....
G G 50, 1
// Update gradients // Train a subtree and get k 1. + TeainI'reeL, G, E.)
last-layer nodes
10
for each last-layer node in parallel do
11
|.lll + Enc(G,, kprs) for each guest in parallel do
// Encrypt gradients
13
Send 1 G.; to Guest u // Send intermediate results to guest // Guest updates the bottom
| < GuestTrrain || Eg)
layers
Is
4 yp
// Update prediction values
/* Conducted on guests +/
16 GuestTrain(I, ||]|| Eg):
17 [1) 1. G | + reei [|G (|||,,
18 for each last-layer node do
||Vel Σ, ||G/||
// Compute leaf values | + V +1 E,ky E3 11 Add noises for secure aggregation
29
return 3/-
information about the data or model of the other parties. Note that there may be potential inference attacks and techniques like differential privacy (Dwork 2011) can be applicable (Li ct al. (023). which is out of the scope the paper.
EVALUATION
5.1
EXPERIMENTAL SETTINGS
Datasets We use four datasets in experiments: 1) Two versions of hybrid FL datasets provided by PET's Prize Challenge for anomalous transaction detection. the datasets, one party (i.e., host) holds the synthetic transaction data and the label and multiple parties (i.e., guests) hold the account data. Both datasets have 25 guests. 2) Two simulated hybrid federated learning datasets. We generate these datasets by partitioning the centralized tabular datasets Adult and Cod-rna into multiple subsets randomly. We first divide the dataset vertically to get host dataset and then divide the remaining one horizontally to get multiple guest datasets. The number of guest parties set to 5 for both datasets. For more details about the datasets, please refer to Appendix C. In the experiments of the main paper, all guests share the same feature spaces and different sample spaces. For results on more experimental settings, please refer to Appendix C.
Approaches
We compare the following approaches with HybridTree: 1) ALL-IN: We train a GBDT model the global data without any privacy constraints. This approach represents the upper
7

---

Published as a conference paper at ICLR 2024
Table I: The comparison of model performance between different approaches. For FedTree, Secure- Boost, and Pivot, we run them with every possible guest and report the minimum and maximum model performance achieved.
Hybrid'Tree
SOLO
FedTree
SecureBoost
Pivot
TFL
ALLLIN
AD
0.689
0.492
0.537-0.566
0.537-0.566
0.534-0.561
0.530
0.703
DEV-AD
0.553
0.111
0.412-0.462
0.412-0.462
0.414-0.468
0.397
0.574
Adult
0.832
0.653
0.764-0.788
0.764-0.788
0.755-0.778
0.773
0.853
Cod-rna
0.927
0.690
0.805-08863
0.805-0.863
0.811-0.870
0.884
0.931
The host locally trains a GBDTT model with its local data. This approach represents the lower bound of model performance. 3) 2-party VFL: The host party collaborates with one of the guests conduct vertical federated GBDT. We compare three vertical federated learning studies for GBDTs, including FedTree (Li et al. 2023), SecureBoost (Cheng et al., 2.19), and Pivot (Wu et al. 2020 We run each approach with every possible guest and report the minimum and maximum model performance achieved. Note that is non-trivial to apply the VFL studies to the hybrid data setting with multiple guest parties. 4) TFL: We assume that guests have the labels and adopt a tree-level solution (Zhao et al. 2018 Li et al. 2020) with all parties, i.e., each party trains tree individually and sequentially. We this approach assess the effectiveness of tree-level knowledge aggregation.
bound of model performance. 2) SOLO:
Model and Metrics We train a GBDT model with 50 trees. The learning rate is set to 0.1. The maximum depth is set to 7 for the baselines. The maximum depth for the host is set to 5 and the maximum depth for guests is set to 2 for HybridTree so that the total depth of the tree is 7 to ensure a fair comparison. The regularization term is set to I. For AD and DEV-AD, we use AUPRC (Area Under Precision-Recal Curve) as the metric since these two datasets are highly class-imbalanced. For two simulated datasets, we use classification accuracy as the metric.
We rum experiments on machine with four Intel Xeon Gold 6226R 16-Core CPUs. We fix the number of threads to 10 for each experiment. Due to the page limit, we only present some of the results the main paper. For more experimental results, please refer to Appendix C of the supplementary material.
5.2 MODEL PERFORMANCE
We compare the model performance of HybridTree with the other baselines with the results exhibited in T Given the deterministic nature the GBDT training process, the output remains consistent across multiple runs, rendering the reporting of mean and standard deviation unnecessary. The results reveal that HybridTree's 'ss performance closely mirrors that of ALL-IN, which represents the upper- bound performance without privacy restrictions. Furthermore, HybridTree consistently surpasses the model performance of SOLO, FedTTree, Pivot, and TFL. by a substantial margin. FedTree and Pivot, which relies solely on data from single guest for training, suffers significant accuracy deficit. TFL, on the other hand, adopts a tree-level knowledge aggregation strategy, which falls short in effectiveness since each tree is inherently weak. In contrast, our method skillfully amalgamates the knowledge of guests utilizing a layer-level design.
5.3 TRAINING PERFORMANCE
We contrast the communication and computational efficiency during training of HybridTree and VFL approaches in Table The comparison of inference performance presented Appendix of the supplementary material. We limit our comparison to VFL approaches, other methodologies break the privacy constraints by sharing data/labels and do not impose additional communication or computational burdens. As the table illustrates, HybridTree significantly outperforms FedTree and Pivot in both communication costs and training duration. The communication speed can be accelerated up six times, while the computational speed may see enhancement of up to eight times. HybridTree primarily incorporates lightweight AHE for encryption. These encrypted gradients transmitted only once per tree. Furthermore, cryptographic operations restricted to the lower
8

---

Published as a conference paper at ICLR 2024
Table 2: The training efficiency comparison between HybridTree and VFL approaches. The speedup of HybridTree is computed by comparing FedTree.
Communication size (GB)
Training time (s)
HybridTree
FedTree
SecureBoost
Pivot
speedup
HybridTrce
FedTree
SecureBoost
Pivot
speedup
AD 223.6
1363,9
1389.2
1420.3
6.1x
84.1
595.6
3212.7
316823
7.1x
DEV-AD
142.6
770.1
681.9
792.2
5.4x
58.2
464.9
2856.6
284235
8.0x
Adult
1.55
6.3x
4.3x
Cod-rna
2.84
15.92
20.4
18.5
5.6X
1.0
5,3
24.3
3845
5.3x
0.00
0.00
3.4
0.000
$0.0
8.50
8.70
$.00
8:35
8:00
121
GGuntt
#G.ems
(a) AD
DEV-AD
(c) Adult
Figure 6: Model performance of different approaches by varying the number of guests. We omit SecureBoost as curve overlaps with FedTreee
Table 3: Model performance of different approaches in the multi-host setting.
HybridTree SOLO
FedTree
SecureBoost
Pivot
TFL
ALL-IN
AD
0.682
0.423-0.443
0.498-0.502
0.498-0.504
0.483-0.492
0,512
0.703
DEV-AD
0.548
0.094-0.099
0.389-0.425
0.387-0.423
0.392-0.438
0.366
0.574
Adult 0.828
0.582-0.591
0.712-0.722
0.712-0.722
0.698-0.710
0.730
0.853
Cod-rna
0.911
0.621-0.635
0.784-0.804
0.784-0.804
0.771-0.792
0.821
0.931
layers in HybridTree, in contrast to node-level solutions where they occur every node. As result, HybridTree demonstrates superior efficiency compared to the baselines.
5.4 SCALABILITY
We manipulate the number of guests from 25 to 100 for AD and DEV-AD, and from 5 to 20 for Adult and Cod-rna by randomly dividing each guest dataset into multiple subsets. The corresponding results are presented in Figure Due to the page limit, we leave the results of Cod-rna in Appendix of the supplementary material. From the results, it is evident that HybridTree exhibits significantly more stability than FedTree, Pivot, and TFL. Even when the number of guests is increased, HybridTree well consolidate the knowledge from all parties. In contrast, FedTree, Pivot, and TFL exhibit considcrable degradation in performance when local knowledge limited.
CONCLUSIONS
This paper introduces HybridTree, a new federated GBDT algorithm designed for hybrid data environment, Leveraging our insights into meta-rules, we propose tree transformation capable of reordering split features. Building upon this transformation, we introduce an innovative hybrid tree learning algorithm that integrates the knowledge of guests by directly appending layers. Experimental results demonstrate that HybridTree significantly outperforms other baseline methodologies in terms of efficiency and effectiveness. While HybridTree is designed for GBDT due its popularity, the idea of lever-level training is applicable to other trees. We consider hybrid federated learning on multi-modal data future work.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
This research is supported by the National Research Foundation Singapore and DSO National Laboratories under the AI Singapore Programme (AISG Award No: AISGG-RPP-022-0018) Singapore National Research Foundation funding #053424, ARL funding =W91INF-23-2-013) DARPA funding #1 111774-19499) IC3 industry partners, the National Science Foundation under grant no. 2229876 and funds provided by the National Science Foundation, by the Department of Homeland Security by IBM, and by JPMorgan Chase & Co. Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not reflect the views of the supporting entities.
REFERENCES
Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. Practical secure aggregation for federated learning on user-held data. arXiv preprint arXiv: 1.04482, 2016.
Leo Breiman. Bagging predictors. Machine learning, 24:123 140, 1996.
Tianqi Chen and Carlos Guestrin. Xgboost: A scalable tree boosting system. In Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining, pp. 785-794, 2016.
Kewei Cheng, Tao Fan, Yilun Jin, Yang Liu, Tianjian Chen, Dimitrios Papadopoulos, and Qiang Yang. Secureboost: A lossless federated learning framework, arXiv preprint arXiv:99010088 2019.
DrivenData. U.s. pets prize challenge: Phase 1. URL https: /ww.://///wwwwoo
www drivendata.oog//
compet Come heapaad---eaanni-na-aaaaeeee
Cynthia Dwork. Differential privacy. Encyclopedia of Cryptography and Security, pp. 338-340, 2011.
Wenjing Fang, Derun Zhao, Jin Tan, Chaochao Chen, Chaofan Yu, Li Wang, Lei Wang, Jun Zhou, and Benyu Zhang. Large-scale secure xgb for vertical federated learning. In Proceedings of the 30th ACM International Conference on Information Knowledge Management, pp. 443-452, 2021.
Aris Gikolalas-Divvann Dinusha Vatsalan, Dimitrios Karapiperis, and Murat Kantarcioglu. Modern privacy-preserving record linkage techniques: an overview. IEEE Transactions on Information Forensics and Security, 16:4966-4987, 2021.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. arXiv preprint arXiv:1912.04997 2019.
Guolin Ke, Qi Meng, Thomas Finley, Taifeng Wang. Wei Chen, Weidong Ma, Qiwei Ye, and Tie- Liu. Lightgbm: highly efficient gradient boosting decision tree. Advances in neural information processing systems, 30, 2017.
Soo-Min Kim, Patrick Pantel, Lei Duan, and Scott Gaffney. Improving web page classification by propaappopngation over click graphs. In Proceedings of the 18th ACM conference on Information and knowledge management, pp. 1077-1086. ACM, 2009.
Qinbin Li, Zeyi Wen, and Bingsheng He. Practical federated gradient boosting decision trees. In 2020.
AAAI, pp.
Qinbin Li, Zhaomin Wu, Yanzheng Cai, Yuxuam Han, Ching Man Yung, Tianyuan Fu, and Bingsheng He. Fedtree: A federated learning system for trees. In Proceedings of Machine Learning and Systems, 2023.
Yang Liu, Yan Kang, Chaoping Xing, Tianjian Chen, and Qiang Yang. secure federated transfer learning framework. IEEE Intelligent Systems, 35(4):70-82, 2020.
10

---

Published as a conference paper at ICLR 2024
Samuel Maddock, Graham Cormode, Tianhao Wang, Carsten Maple, and Somesh Jha. Feder- ated boosted decision trees with differential privacy. In Proceedings of the 2022 ACM SIGSAC Conference Computer and Communications Security, pp. 2443-2263,,22 2022.
Duncan McElfresh, Sujay Khandagale, Jonathan Valverde, Ganesh Ramakrishnan, Micah Goldblum, Colin White, et al. When do neural nets outperform boosted trees on tabular data? arXiv preprint arXiv:2305.0283 02997. 2023.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, et al. Communication-efficiene learning of deep networks from decentralized data. arXiv preprint 16Ki::660..05222 2016.
Ralph C Merkle. Secure communications over insecure channels. Communications of the ACM, 21 (4):294-299, 1978.
Pascal Paillier. Public-key cryptosystems based on composite degree residuosity classes. In Advances in CrypolloyyEUROCRRPYPP International Conference on the Theory and Application of Cryptographic Techniques Prague, Czech Republic, May 2-6, 1999 Proceedings 18, pp. 223-238. Springer, 1999.
Matthew Richardson, Ewa Dominowska, and Robert Ragno. Predicting clicks: estimating the click- through rate for new ads. In Proceedings of the 16th international conference World Wide Web, pp. 521-530. ACM, 2007.
Si Si, Huan Zhang, S Sathiya Keerthi, Dhruv Mahajan, Inderjit S Dhillon, and Cho-Jui Hsieh. Gradient boosted decision trees for high dimensional sparse output. In Infernational conference on machine learming, pp. 3182-3190. PMLR, 2017.
Zhihua Tian, Rui Zhang, Xiaoyang Hou, Jian Liu, and Kui Ren. Federboost: Private federated learning for ghdt. arXiv preprint arXiv:201 1. 1.02796, 2020.
Praneeth Vepakomma, Otkrist Gupta, Tristan Swedish, and Ramesh Raskar. Split learning for health: Distributed deep learning without sharing patient data. arXiv preprint 1rXiv:1812.00564
2018.
Rui Wang, Oğuzhan Ersoy, Hangyu Zhu, Yaochu Jin, and Kaitai Liang. Feverless: Fast and secure vertical federated learning based xgboost for decentralized labels. IEEE Transactions on Big Data, 2022.
Yuncheng Wu, Shaofeng Cai, Xiaokui Xiao, Gang Chen, and Beng Chin Ooi. Privacy preserving vertical federated learning for tree-based models. arXiv preprint arXiv:2008.06/77 2020.
Qiang Yang. Yang Liu, Tianjian Chen, and Yongxin Tong. Federated machine learning: Concept and applications. ACM Transactions Intelligent Systems and Technology (T1ST), 10(2):1-19, 2019.
Xinwei Zhang, Wotao Yin, Mingyi Hong, and Tianyi Chen. Hybrid federated learning: Algorithms and implementation. arXiv preprint 2rXiv:2012.12420.. 2020.
Lingchen Zhao, Lihao Ni, Shengshan Hu, Yaniiao Chen, Pan Zhou, Fu Xiao, and Libing Wu. Inprivate digging: Enabling tree-based distributed data mining with differential privacy. In IEEE INFOCOM 2018-IEEE Conference on Computer Communications, pp. 2087-2095. IEFF, 2018

---

Published as a conference paper at ICLR 2024
APPENDICES
we prove the theorems introduced in Section 3 In Appendix B we introduce the algorithmic details training a Appendix C results. In Appendix D
In Appendix A
we present additional experimental details and we discuss the potential broader impacts and limitations of our approach.
A PROOF
Definition 1. (Meta-Rule) Given a split rule S == Di=1 where F, is split condition by feature fj. we call it as meta-rule if P(u|x E S) P(u|x E (Sn FR)) for any Fg not in split rule S. Theorem 2. Suppose Fg. is a meta-rule in Tree A. For any input instance x E DD we have (x AA)l Ex 0g]], i.e., the expectation of prediction value of Tree and Tree B are the same.
Proof. For ease of presentation, we use {F} to denote the instance ID set that satisfies split rule (i.e., {F} == {i|x, F)). We consider the instances sets of three leaf nodes in Tree A.
1) For the instance set {Lg in L1 of Tree A, it will be divided into two sets in Tree B: {2h n Fg in L1 and {-Fh Fg in Lgg The expectation of leaf value L/ is
E(EiE (F, FF 94) 1(F n FFHH
E(L,)
(2)
From Definition we have P(y|x F2) P(y|x (Pn Fg)). Note that gradient is mapping from We have P(g|x E Fg) P(g ( ( Pg).. Thus, we have
| (IFIFFg)
E(E 9t)
E(L))
[F/l
KF FFH
EE (F,) 9h)
(3)
FF
E(LI).
Similarly, we have
(-F, F
E(EiE(F,) 9i) T[-F, n n.H
E(L))
E(CiE((F)) 9:)
(4)
|Fgl
E(LI).
2) For the instance set (-F, Fx) in L2 of Tree A, it will be relocated L/2 of Tree B.
3) For the instance set (-F, 0 F in Lg of Tree A, will relocated to L of Tree B.
Thus, for any instance x. B (x: 0 A E[f(x;0B))
Theorem 3. Suppose Sm := F2, .... n Fg is meta-rule in free 0A where Fg is split condition using the feature from the guests. For any tree path in tree A involving the split nodes Sm. we can always reorder the split nodes in the tree path such that F, is in the last layer. Moreover, naming the tree after the reordering as 0B, we have Exf(x; = Fxf(xx; 0n) for any input instance x E D.
Proof. We use 6g to denote the subtree with root node Fg- For ease presentation, we use Fj, O Fg to denote the given meta-rule, where FA is the split rule with split features from the host. Without loss of generality, we assume that the left child node of F, is a leaf node when F, is true, denoted as La. For every possible partial split rule in the subtree of the right child node Fx Oi Fj. have
12

---

Published as a conference paper at ICLR 2024
Fn1
Fng
Y
N
Fh
Fha
Fgg
N
Y
F
Fg
Fg
F
4
F
L5
N
Y
N
N
R2
L6
L
Fg
L1
Lg
Lg
46
Lg
L
Y
L2
L3
1.
4
L/
A
B
Figure 7: Suppose Fi, Fgg is meta-rule. Tree A can be transformed into Tree B.
P E FL Pf By moving Fg to the last layer of right child node, for each split rule FA Fk. lc generates two new leaf nodes I (F FFFF & Fg) and L' F We have
9s)
E(L))
F n FR n FgH
[ n FR n FgH.
E(E (E 9:) [[F FF F.H
[[F (F))
(5)
E{E (( 9))
[F FFH
E(L)
For L,,, it equivalent to the original tree node -Fy FF
Thus, the expectation of the prediction value remains unchanged for any input instance through transformation.
Based on Theorem 3 we can transform a tree by reordering the split points such that the split points using the guest features the bottom layers. Figure shows example.
B NOTATIONS AND ALGORITHM
B.
NOTATIONS
The notations used in the paper are summarized in Table B.1
B.2
THE GBDT TRAINING ALGORITHM
At the 1-th iteration using second-order approximation following objective function
Si et 2017). GBDT minimizes the
( Σ Uyn o fe(x;; 0.)) ((0,)
(6)
EM.. 11 gafe(x;; 0.) 1 (x, +
where 9: =) 1)) is first order gradient the loss function and ft(-) is the tree function.
GBDT updates tree from the root node to minimize Eq 66) until reaching the specified maximum depth. We use to denote the instance ID set the current node. If the current node is split node,
13

---

Published as a conference paper at ICLR 2024
Table 4: Notations used the paper.
Notation
Decsription
D
Dataset the host party
D
Dataset of guest party
Instance ID
En
The depth of tree trained by the host party
Eg
The depth of tree trained by the guest party
T
Number of trees
Loss function
Hyperparameter
yp
Prediction value vector
Rpub
Publick key of homomorphic encryption
kpri
Private key of homomorphic encryption
G
Guest party i
kjj
Key for guest pair (G,, G₁) generated by DH key exchange
G
First-order gradients in GBDTs
V Leaf values
U Gain of a split
suppose the split value splits into I, and Iz. Then, the gain of the split value defined by the loss reduction after split, which is
U CiEI, gi)2
(Eiet 9i)2
11| [Rl
Since it would be computationally expensive to traverse all possible split values to find the one with the maximum gain, GBDT usually considers small number of cut points possible split candidates. The best split point is selected from these split candidates. If the tree reaches the maximum depth or if the gain remains negative, the current node becomes leaf node. To minimize Bq (6) the optimal leaf value is
Eier 9i
(8)
+
After training tree according to Eq. and Eq. 8 we can update the gradients using the current prediction value and train the next tree until reaching the specified number of trees.
The algorithm for training tree in GBDT, denoted as TrainTree(). is presented in Algorithm 2 When the maximum depth is reached, the leaf' value is computed based on the gradients (Lines 2-4). On the other hand, if the maximum depth is not reached, the algorithm proceeds to calculate the gain for each potential split value (Lines 6-17) and stores the split value with the highest gain. the gain is greater than zero, the instances are split using the recorded split value, and two subtrees are trained as separate branches (Lines 18-20). However, the gain is not greater than zero, the current node does not require further splitting and treated leaf node (Lines 21-23).
14

---

Published as a conference paper at ICLR 2024
Algorithm 2: Train a single tree in GBDT.
Input: Instance ID set I, gradients G, maximum depth E. The final model Tree,, E):
Output:
= then
- V & [I]
// Compute leaf value
set the current node to leaf node with value V
else
Smaz
for every possible split rule F3 do
filæ;
I - fi|z; $ F
S + Ee,, 9.)
10
[I]
S, (E 9.)2
11
1.1
S - S + S
// Compute gain
13
S > Smaz then
set the current node to split node with rule F,
Sman f S
I I
I
18
if Gman > 0 then
19
TreinTree(K Ir, GT E-11 1)
// Train a subtree recursively
TrinTreel GTg. E
21
else
Σier [I]
22
V
set the current node to leaf node with value V
15

---

Published as a conference paper at ICLR 2024
Table 5: Statistics of the datasets.
#training instances
#test instances
#features of host
#features of guests
#guests
AD
4,691,615
705,108
25
DEV-AD
2,993,804
1,003,675
Adult
32,561
16,281
102
21
5
Cod-rna
44,651
14,884
5
C EXPERIMENTS
C.I DATASETS
The dataset statistics are presented in Table To create the host dataset for Adult and Cod-rna we employ a random sampling approach. Specifically, we generate a random number between zero and the total number of features, and assign this sampled number of features to the host dataset. The remaining features are then partitioned randomly and equally into five subsets, resulting in the generation of five guest datasets in the default setting.
C.2 MULTI-HOST SETTING
While we assume there is only one host in our design for simplicity, HybridTree can be easily extended to the multi-host setting, where multiple hosts (c.g., hospitals) collaborate with guests (patients' wearable health devices) for FL.. Each host can follow the HybridTree training process to train a GBDT with the guests that have the corresponding instances of the host. Then, for inference, we can conduct prediction on each GBDT and apply bagging (Breiman) 1996) to aggregate the prediction results of multiple GBDTs. For regression tasks, we average the prediction values of multiple GBDTs as the final prediction value. For classification tasks, we apply max-voting to select the class with the highest voting as the prediction class.
We simulate the multi-host setting by randomly partitioning the host dataset into five subsets. The results of the multi-hos settings shown in Table HybridTree continues to substantially surpass other baseline methods, underscoring the effectiveness of our bagging strategy in a multi- host configuration. Compared the single-host scenario, the performance of other methodologies markedly deteriorates due to the constrained data availability from the host.
C.3 HETEROGENEITY
While the hybrid federated datasets naturally have data heterogeneity among different parties, their heterogeneity cannot be easily quantified and controlled. To assess model performance amidst diverse data heterogeneity, we consolidate the guest datasets into unified global set and divide it into multiple subsets in accordance with the corresponding labels in the host. Specifically, we sample Pk ~ Do (B) and allocate Pk.j proportion of instances from class & to guest j. where (ir denotes the Dirichlet distribution with a concentration parameter 3. The heterogeneity intensifies 3 diminishes. The results for varying / values
depicted in Figure g HybridTree consistently surpasses other baseline methods across all settings. In the case of VFL. performance is contingent upon the data quality of single guest, resulting in instability and substantial error bar.
C.4 OVERLAPPED SAMPLE AND HETEROGENEOUS FEATURE SETTING
In the experiments conducted in the main paper, all guest datasets share the same feature space, and there are no overlapping samples between the guests. However, it is worth noting that our algorithm does impose any specific requirements regarding the feature and sample spaces across guests. To simulate this flexible setting, we introduce a simulation where, for each guest dataset, a random number a generated from the range of [0, d), representing the number of features to be dropped.
https::/// www. csie. ntu edu. http:/see.ett.eee..//o///iiiiiii iibs/ttooooo s/datasets.
16

---

Published as a conference paper at ICLR 2024
3.00
1340
855
1300
00.0
6.00
0.200
0.23
2010
3.20
3.55
644
01
(a) AD
(b) DEV-AD
(c) Adult
Figure 8: Model performance of different approaches by varying heterogeneity. We omit SecureBoost its curve overlaps with FedTree
Table The model performance the setting with overlapped samples and heterogeneous features between different guests.
Hybrid'rree
SOLO
FedTTree
SecureBoost
Pivot
TFL
ALL-IN
AD
0.673
0.492
0.511-0.559
0.510-0.557
0.515-0.547
0.514
0.682
DEV-AD
0.546
0.111
0.389-0.444
0.393-0.443
0.372-0.421
0.384
0.561
Adult
0.801
0.655
0.753-0.782
0.753-0.782
0.759-0.789
0.756
0.820
Cod-mn
0.908
0.690
0.776-0.858
0.776-0.858
0.771-0.845
0.861
0.919
Additionally, an additional | number of samples is assigned from other guest datasets, with 3 drawn randomly from the range of [0, ]. where d denotes the feature dimension and n represents the total number of samples. The results obtained with this simulated setting are presented in Table HybridTree continues outperform the other baselines and achieves performance comparable to centralized training, thus showcasing the robustness of HybridTree in various hybrid data settings.
C.5 OVERHEAD OF HYBRIDTREE
In Table 7 provide detailed breakdown of the training time for HybridTree. A comparison with the ALL-IN approach reveals that the primary computational overhead of HybridTree lies in the update process of the last layers in the guest models. This step involves computations encrypted gradients, which can be computationally expensive. However, thanks to its layer-level design, HybridTree significantly reduces the computation overhead compared to node-level solutions.
C.6 INFERENCE PERFORMANCE
The inference costs of HybridTree and VFL are presented Table 3 Since HybridTree and VFL approaches have similar inference procedure, both approaches have low inference time. In VFL approaches, since each tree node may be distributed host or guests, multiple communication rounds
Table 7: Training overhead of HybridTree compared with ALL-IN.
HybridTree
ALL-IN
Host training time (s)
Guest training time (s)
training time (s)
AD
37.4
45.7
39.8
DEV-AD
28.9
29.3
31.7
Adult
1.1
0.9
1.1
Cod-ma
0.6
0.4
0.6
17

---

Published as a conference paper at ICLR 2024
Table 8: Communication size (MB) and inference time of TrbridTTree and VFL during prediction. The speedup of TreeidTree is computed by comparing to FedTree.
Communication size (MB)
Inference time (8)
Tybeiddree
FedTree
SecureBoost
Pivol
speeduu
HybridTree
FedTTree
SecureBoodt
Pivol
speedup
AD
5.6
16.4
20.5
19.2
2.8x
17.9
22.1
28.4
12528
1.2x
DEV-AD
25.1
Adult
0.28
1,36
1.93
2.51
4.8x
0.92
1.35
2.09
426
1.5x
Cod-ma
0.48
1.64
1,92
2.84
3.4x
0.89
1.37
2.28
498
1.5x
Table 9: The comparison of model performance hetween different approaches. For FedTree, Secure- Boost, and Pivot, we run them with every possible guest and report the minimum and maximum model performance achieved.
HybridTree
SOLO
FedTTree
SecureBoost
Pivot
TFT.
ALL-IN
4 0.671
0.402
0.470-0.476
0.470-0.476
0.458-0.462
0.530
0.703
6 0.682
0.423
0.498-0.502
0.498-0.502
0.496-0.499
0.397
0.574
8
0.689
0,431
0.506-0.511
0.506-0.511
0.498-0.502
0.773
0.853
may be required during an inference path if involves changes in node locations between host and guests. In HybridTree, since tree is divided into two parts, only two communication rounds required. Thus, HybridTree has lower communication overhead than FedTree and Pivot.
C.7 SENSITIVITY STUDY
We change the tree depth from 4 AD and present the results in Table 9 While increasing tree depth can increase the model performance, our approach consistently performs better than the other baselines.
C.8 VERTICAL FEDERATED LEARNING
Our approach is also applicable in the FFL setting, where the number of hosts and guests is exactly one. By merging all guests as single guest, we compare HybridTree with other VFL studies and the results shown in Table I0 and Table II] HybridTree achieve comparable model performance with VFL studies while significantly reducing the training time.
C.9 IMPACT OF THE HOST DATASET
To investigate the impact of changes the host dataset, use the synthetic hybrid FL dataset Adult. Specifically, in the host dataset, we randomly sample 20-100% instances/features to use in training. The results are shown in Table. While reducing the instances/features will reduce the overall performance of all approaches, HybridTreee consistently outperforms the other baselines.
Table 10: The model performance of different approaches in the VFL setting.
HybridTree
FedTree
SecureBoost
Pivot
AD
0.702
0.708
0.708
0.704
DEV-AD
0.594
0.603
0.603
0.597
Adult 0.851
0.862
0.862
0.858
Cod-mna
0.944
0.957
0.957
0.951
18

---

Published as a conference paper at ICLR 2024
Table 11: The training time (s) of different approaches in the VFI setting.
HybridTree
FedTree
SecureBoost
Pivot
speedup
AD
103.7
782.5
4628.4
425698
7.5
DEV-AD
67.4
623.6
3745.9
395720
9.3
Adult
3.2
12.8
101.8
13829
4.0
Cod-rna
1.7
8.1
82.5
6023
4.8
Table 12:
The model performance of different approaches by varying the size of the host dataset.
Proportion
HybridTrree
SOLO
FedTTree
SecureBoost
Pivot
TFL
ALL-IN
20%
0.778
0.598
0.712-0.73
0.712-0.732
0.709-0.728
0.723
0,794
#instances
50%
0.786
0.61
0.726-0.742
0.726-0.742
0.723-0.735
0.73
0.805
80%
0.814
0.636
0.749-0.776
0.745-0.776
0.723-0.754
0.762
0.832
100%
0.832
0.653
0.764-0.788
0.764-0.788
0.752-0.789
0.773
0.853
20%
0.602
0.424
0.541-0.561
0.541-0.561
0.535-0.558
0.542
0.621
ffeatures
0.724
0.552
0.655-0.679
0.655-0.678
0.659-0.678
0.669
0.742
80%
0.771
0.592
0.704-0.735
0.704-0.735
0.698-0.728
0.713
0.791
100%
0.832
0.653
0.764-0.788
0.764-0.788
0.762-0.784
0.773
0.853
C.10 RESULTS OF COD-RNA
The results of cod-rna with different numbers of guests and levels of heterogeneity are presented in Figure 9 corresponding to Section 5.4 and Section C,3 of the main paper. HybridTree still outperforms the other baselines this dataset.
D DISCUSSIONS
Broader Impact Federated learning offers compelling avenue that fosters multi-party collabora- tion, and our approach propels this direction step further. Our approach encourages collaborative learning between heterogeneous parties to provide better services for people while preserving data privacy. However, our approach rests upon the premise of trust amongst the participating parties. In cireumstances where collusion among multiple parties occurs, there lies the potential risk of inferring sensitive information from other parties. Thus, ensuring the integrity of the system is paramount prior any real-world deployment.
Limitations Our method is well-suited for tabular data, as it allows for the representation of knowl- edge through meta-rules. However, when dealing with image, text, and graph data, the knowledge inherent in these types of data often cannot be casily captured by rule-based expressions, rendering our method less applicable in those cases. One interesting future direction is to combine deep neural networks (DNNs) with trees, where DNNs are trained locally extract the low-dimensional representations, and trees are trained in the federated setting to classify the representations. This hybrid approach holds promise for addressing the challenges associated with image, text, and graph data in the context of hybrid federated learning.
Related Work We have summarized the related work on federated GBDT' Section Here we compare HybridTreee and related federated GBDT studies in Table [3 We can observe that HybridTree is the first federated GBDT algorithm on hybrid data setting. Moreover, instead using node-level tree-level knowledge aggregation in existing studies, HybridTree adopts layer-level aggregation that effectively and efficiently incorporates the knowledge of guest parties by appending layers, which makes it more practical.
19

---

Published as a conference paper at ICLR 2024
0.90
0.90
0.85
AUPRC
AUPRC
0.80
0.80
HyartsTree SOLO TFL
HybrisThoc
0.75
0.75
ALL-N
All-N
RedTiee
0.7
Pivot
10
100
10
0.1
Guests
(a) scalability
(b) heterogencity
Figure 9: Experiments on scalability and heterogeneity of HybridTree on Cod-rna. We omit Secure- Boost as its curve overlaps with FedTree.
Table 13: Comparison between HybridTree and other federated GBDT studies.
Setting
Knowledge aggregation
Horizontal
Vertical
Hybrid
node-level
tree-level
layer-level
SecureBoost CCeng et al.
2019
X
X
X
FedTree (i al. 2023
/
/
x
/
X
Federboost Tian al.
2020
/
/
X
/
X
X
TFL (Zhao et al
2018
/
X
X
X
/
SimFL (Li et al.
2020
/
X
X
X
/
Secure XGB (Fng et al.
2021]
X
X
/
X
Pivot (Wu 2020
X
X
X
Feverless Wang et al. 2022
X
x
X
X
FBDT-DP Maddock et al.
2022
/
X
X
/
X
X
HybridTree
X
x
X
20


Reviews:
[{"review_id": "fUREj2eLet", "reviewer": "Reviewer_KFHq", "summary": "The paper presents HybridTree, an innovative algorithm tailored for federated learning within the framework of Gradient Boosting Decision Trees (GBDT) in a hybrid data context. It introduces a novel tree transformation technique that can reorder split features based on insights from meta-rules. This transformation is key to the development of the hybrid tree learning algorithm, which is capable of incorporating knowledge from different sources (guests) by appending new layers to the decision trees.", "questions": "Please see the weakness.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The main innovation of this work lies in the development of a tree transformation strategy that can reorder split features to accommodate a federated learning environment. This is particularly relevant for scenarios where data privacy and distribution are concerns.\n\n2. By introducing a new layer-level training algorithm, HybridTree, they address the integration of knowledge from multiple participants (referred to as \"guests\") in the federated model without compromising on data privacy.\n\n3. The authors conduct extensive experiments on multiple datasets. The empirical results show that the proposed method outperforms the baselines significantly in model performance.", "weaknesses": "Even though the proposed method can handle hybrid features, the features have to be tabular data. This might not be the constraint of this paper but rather the limitation of the tree-based methods. However, maybe the authors can consider the scenarios where clients have multi-modal data, where the data modalities are hybrid across clients.", "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": "", "extra_scores": {}}, {"review_id": "ZX1MtOqL4n", "reviewer": "Reviewer_3ksq", "summary": "This work proposed a novel tree learning protocol for the hybrid FL settings where data are distributed both by features and by samples, a scenario that is less explored. The proposed method does not need frequent communication between parties and exhibits comparable accuracy to the centralized setting.", "questions": "1. Does a \"meta-rule\" have to include the last layer of a tree? Fig 1& 2 both show that they include the last layer. However, Definition 1 shows it has additional layers F_k, which seems to be inconsistent. \n\n2. How does the algorithm deal with trees that have mixed splits from both host party and guest party? Figure 3 only demonstrates a simple example that the guest splits appear in the bottom layers, but what if guest splits appear near the root, followed by intervened and alternative host and guest splits? More complicated examples will help to demonstrate how the framework works.", "limitations": "", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. This work targets at a hybrid FL setting, where vertical FL setting integrates with horizontal setting. The setting has practical applications in many industrial areas but are less studied in research.\n\n2. The observation of the existence of meta-rule is novel and leads to the development of a communication efficiency tree-based FL algorithm.", "weaknesses": "1. The paper is not very well-presented and is hard to follow. First of all,  it is unclear in the hybrid setting considered, what are the relative relations of the guest parties? In the introduction, it appears that they share the same feature space but have different sample IDs, however, in 3.1 they appear to have different dimensions and unclear alignment. It is suggested that the paper properly define the problem setting. A figure on how data is partitioned by different parties would also help.  Secondly, the algorithm is very messy with many undefined variables and notations, making it also hard to process. It is also not clear how features from different guests are used in a collaborative manner in the approach due to the above issues on presentation. \n\n2. The experimental results are biased. 1) The paper compares its model performance using data from multiple guests against FedTree and Pivot using data from one guest, therefore the model performance gap is largely due to the utilization of additional data parties, not to the benefits of the algorithm. To be fair, the paper should compare them under the same settings, that is, multiple guests and host. 2) Important baselines such as Secureboost[1] is missing.  3) the model performance of the proposed methods still appear to be \na little inferior to the centralized setting, not exactly \"comparable\" as claimed. It is important to understand whether the proposed method is \"lossless\" or \"lossy\" and why. I think more detailed examinations and explanations are needed here. \n\n[1] Cheng, Tao Fan, Yilun Jin, Yang Liu, Tianjian Chen, Dimitrios Papadopoulos, and Qiang Yang. Secureboost: A lossless federated learning framework, 2019", "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": "", "extra_scores": {}}, {"review_id": "SKRQTKY3nF", "reviewer": "Reviewer_whfr", "summary": "This paper introduces HybridTree, a novel federated learning approach tailored for hybrid data environments, where data from different parties vary in both features and samples.  HybridTree facilitates federated tree learning by capitalizing on consistent split rules observed in trees, allowing the integration of knowledge from different parties into the lower layers of a tree. Using these insights, the paper proposes a layer-level solution to train trees without the need for heavy communication. Experimentally, HybridTree has shown comparable accuracy to centralized models while substantially reducing computational and communication overhead. In comparison to other baselines, it can achieve up to an 8-fold speedup.", "questions": "1. \"Eq 2\" —> \"Eq (2)\"\n2. $D_{G_i}= \\{ x \\} (x \\in R^{ d_{g_i}})$ —> $D_{G_i}= \\{ x | x \\in R^{ d_{g_i}}\\} $,  $D_H= { x, y } (x \\in {R^{d_h}})$ —> $D_H= \\{ x, y | x \\in R^{d_h}\\} $\n3. \"Last, guests update the following lower layers of the tree using their local features and received encrypted gradients and send back the encrypted prediction values.\" —> \"Last, guests update the following lower layers of the tree using their local features and **receive** encrypted gradients**,** and send back the encrypted prediction values.\"\n4. \"Then, the gain of the split value is defined by the loss reduction after split, which is\" —>\"Then, the gain of the split value is defined by the loss reduction after **the split**, which is\" \n5. \"The best-split point is selected among these split candidates. When reaching the maximum depth or the gain is always negative, the current node will become a leaf node.\" —> \"The **best split** point is selected from these candidates. If the tree reaches the maximum depth or **if** the gain remains negative, the current node becomes a leaf node.\"\n6. \"FL on hybrid data is rarely exploited in the current literature. Zhang et al. (2020) proposes to…. Liu et al. (2020) applies transfer\" —> \"Zhang et al. (2020) **propose** to…. Liu et al. (2020) **apply** transfer\"\n\n7. “For simplicity, we start from a single-host with multi-guest setting” —>  “For simplicity, we start from a single-host with multi-guest setting” —> \"For simplicity, we start from a scenario involving a single host with multiple guests.\"", "limitations": "", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The problem studied in this paper is interesting and important. This work proposes federated tree models on hybrid data, which expands the scope of current FL frameworks and makes an important contribution to the FL community.\n2. This paper is original and technically sound. The main claims regarding the proposed setting are well supported in the methodology and experimental parts.", "weaknesses": "1. The paper is not easy to follow.\n2. It is better to provide more analysis or explanation on the training process in section 4.1 to let readers well understand how HybridTree handles hybrid data and makes their contribution to the improvement.\n3. Although there is a relatively thorough literature review in the related work part, I prefer to see a discussion on the relation of this work, especially the specific methods.\n4. Some minor errors, see below.", "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": "", "extra_scores": {}}, {"review_id": "ndf5WnvTby", "reviewer": "Reviewer_2kKa", "summary": "The paper addresses federated learning with hybrid tabular data, where data from different parties may differ both in the features\nand samples. The common framework for this kind of settings is federated learning using gradient boosting decision trees (GBDT). However, existing solutions suffer from high communication and computation overhead. The paper introduces HybridTree, a GBDT-based approach with some clever design. The higher layers of a HybridTree follows a standard GBDT design, exploring host features. The lower layers of the HybridTree are distributed among the guests. This is a form of bagging where each guest contributes one tree to the bag, utilising only the local data of the guest. At each HybridTree training iteration, there are $k$ bags corresponding to $k$ endpoints of the host (sub)tree.\nExperiments on simulated and natural hybrid federated datasets show that the HybridTree can be up to 8 times faster than existing approaches, while maintaining the level of accuracy close to when all data are not protected by privacy and low communication overhead.", "questions": "I do not have any major question.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "The paper has good motivation and good overview. The first part of the paper consists of a demonstration of the existence and abundance of meta rules in federated learning using GBDT, which provides clues about where to improve upon existing approaches, and the theoretical contribution, i.e. theorem 2 and 3, albeit being rather simple and straightforward from the mathematical point of view, provides an interesting view on how the following HybridTree algorithm tackles the inefficiency of existing approaches.\n\nThe second part of the paper, the introduction of the HybridTree algorithm, in my view is a clever and efficient use of boosting and bagging under the context of privacy preserving of federated learning. HybridTree is like 2D boosting with 1 dimension resembling GBDT addressing global (host) data, and with the other dimension spanning across local (guest) data, eliminating guest-guest communications and mitigating guest-host communications.\n\nExperiments on both simulated and hybrid federated datasets are appear adequate for the problem that the paper addresses, with results favouring HybridTree with reasonable gaps over existing approaches.", "weaknesses": "I only have a few minor complaints about presentation, which makes it difficult to follow in the first read:\n\n1. Definition 1 needs revising. At the beginning $S$ is defined as an intersection of split conditions but at the end you have split conditions not in $S$. It is intuitively understandable but it is mathematically incorrect.\n\n2. In Figure 2b, you could have mentioned that $(L'_1, L'_2, L'_3, L'_4)$ can be $(L_1, L_2, L_1, L_3)$ as an example, and the audience would understand Theorem 2 better.\n\n3. I did not understand theorem 3 at first. How does a meta rule that \"ended by $F_g$ differ from a meta rule where $F_g$ is the last layer? Aren't they the same thing? Does the intersection operator here suggest ordering as well? After reading the proof of theorem 3, I understood what the author(s) meant. In any path from the root node to a leaf node, there is a possibility that a guest split condition stays above a host split condition, you just want transform the tree so that such possibility does not exist, is that right? If so, I suggest to restate theorem 3 in a way that is more understandable.\n\n4. What has caught me a surprise is that theorem 3 is not used in a conventional way. Instead of using theorem 3 to improve upon a given tree, the authors redesign a new tree where guest split conditions are always below host split conditions. This is a good point that appears to have been presented somewhat lightly in the paper.\n\n5. In my view, the flow of the paper could better if the authors presented the HybridTree inference before presenting the HybridTree training. Once the audience knows how inference works, the training components make much more sense.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)