SecureBoost+ : Large Scale and High-Performance Vertical Federated Gradient Boosting Decision Tree

Suppose we train a binary-classification task, we have $n_{i}$ samples, $n_{f}$ features, every feature has $n_{b}$ bins, the tree depth is $d$, and then there are $n_{n}=2^{d}$ nodes. We have a rough cost estimate for building a decision tree in SecureBoost:

• •

  The ciphertext computation cost: ciphertext histogram computation + bin cumsum:

  (8)

  $$cost_{comp}=2\times n_{i}\times d+2\times n_{n}\times n_{f}\times n_{b}$$

• •

  The encryption and decryption cost: $g\&h$ encryption + split-info decryption:

  (9)

  $$cost_{ende}=2\times n_{i}+2\times n_{b}\times n_{f}\times n_{n}$$

• •

  The communication cost: encrypted $g\&h$ + split-infos batches:

  (10)

  $$cost_{comm}=2\times n_{i}+2\times n_{b}\times n_{f}\times n_{n}$$

We first introduce GH Packing. From SecureBoost, we notice that gradient and hessian have the same operations in the process of histogram construction and split-finding: the gradient and hessian of a sample will be encrypted at the same time, and the encrypted gradient and hessian will go to the same bucket, but be added to different indices. The gradient and hessian of a split-info will also be decrypted together.

The Paillier(Paillier, 1999) is a homomorphic encryption algorithm used in SecureBoost. During training, a key length of 1024 or 2048 is usually used. When 1024 key length is used, the upper bound on the positive integer allowed in encryption is usually 1023 bits in length. This upper bound is much larger than the gradient and hessian at fixed points. As a result, a lot of plaintext space is wasted in the encryption process. Inspired by recently proposed gradient quantization and gradient batching techniques (Zhang et al., 2020), we adopt a GH(gradient: $g$ and hessian: $h$) Packing method in our work. We bundle $g$ and $h$ using bit arithmetic: We move g to the left by a certain number of bits and then add h to it.

For example, in a binary-classification task, the range of $g$ is $[-1,1]$, $g_{max}=1$ and the range of $h$ is $[0,1]$, $h_{max}=1$. Considering that g might be negative, we can offset g to ensure that it is a positive number. In the classification case, the offset number $g_{off}$ for $g$ will be $1$. In the split finding step, we can remove the offset number when recovering $g,h$.

After offsetting $g$, we adopt a fixed-point encoding strategy to encode $g$ and $h$, which is shown in equation 12, where $r$ is usually 53. Then, we can pack $g$ and $h$ into one large positive number. To avoid overflowing aggregation results during histogram calculation, we need to reserve more bits for $g$ and $h$. Assuming we have $n_{i}$ instances, we need to make sure that no cumulative gradients and hessians in the histogram will be larger than $g_{cmax}$ and $h_{cmax}$ in equation 11. Therefore, we assign $b_{g}$ bits for $g$ and $b_{h}$ bits for $h$ in equation 11:

Finally, we calculate a large positive number $gh$ and homomorphic encryption ciphertext $[[gh]]$ as follow:

Figure 1 shows details of the GH packing process. The active party synchronizes $[[gh]]$ ciphertext to the passive party. The passive party only needs to calculate one ciphertext per sample when constructing the histogram, while in SecureBoost, it needs to calculate two ciphertexts per sample. From the GH Packing optimization, the whole ciphertext computation cost is reduced by half.

Although the GH packing algorithm uses a lot of plaintext space, the plaintext space is not fully utilized. Remind that we usually have a 1023 bit-length integer as the plaintext upper bound when using a 1024-bit key length in the Paillier (Paillier, 1999). Assuming instances number $n$ is $1,000,000$, $r$ is $53$, we will assign $74$ bits for $g$ and $73$ bits for $h$, according to equation 11. The $b_{gh}$ is 147, which is still less than 1023.

To fully use the plaintext space, we can perform ciphertext compression on the passive parties. This technique utilizes the property of our built-in HE algorithm, which is that an addition operation or a scalar multiplication operation is less costly than a decryption operation. We use addition and multiplication operations to compress several encrypted numbers in split-info into one encrypted number and make sure that the plaintext space is fully utilized. The idea of this method is the same as the GH Packing method: we multiply a ciphertext $C$ by $2^{b_{gh}}$, shifting its plaintext by ${b_{gh}}$ bits to the left. Then, we can add another ciphertext to it, compressing the two ciphertexts into one. We can repeat this process until no more bits are left in the plaintext space to compress, as shown in equation 13. Once the active party receives an encrypted number, it only needs to decrypt one encrypted number to recover several $gh$ statistical results and reconstruct split-info.

In the case above, given a 1023 bit-length plaintext space and $b_{gh}$ of 147, We are able to compress $\lfloor 1023/147\rfloor=6$ split points into 1. By using ciphertext compression, decryption operations and decryption time can be reduced by up to 6 times. On the other hand, the communication cost of encrypted split-info is also reduced by up to 6 times. Figure 2 illustrates the process of ciphertext compression.

Histogram subtraction is a classic optimization technique in the histogram-based tree algorithms. When splitting nodes, samples are distributed to either the left or right nodes. The parent histogram is obtained for each feature by adding the set of histograms of the left and right children nodes. To take advantage of this property, in SecureBoost+, both the active and passive parties cache the histogram of the previous layer. When growing from the current layer, the active and passive parties first calculate the histogram of nodes with fewer samples and finally obtain the histogram of sibling nodes by histogram subtraction with the previous layer cache information. Since the ciphertext histogram calculation for passive parties is always the largest overhead, the ciphertext histogram subtraction will greatly speed up the calculation, and at least half of the ciphertext calculation is reduced.

Let’s go back to cost estimates. In more detail, suppose we use paillier encryption algorithm with 1024 key length, we have 1 million instances and 2,000 features, tree depth is 5, bin number is 32, the precision parameter $r$ of equation 12 is 53.

With GH packing and histogram subtraction optimization, ciphertext histogram computation cost is reduced by 4 times and operations in bin cumsum is reduced by half.

The ciphertext computation cost is calcualted by:

We compare the values of the equation (8) and (14), the ciphertext computation cost is reduced by 75%.

Because we pack gradients $g$ and $h$ together, the encryption/decryption operation is reduced by half. Under current paillier encryption setting, we can compress $\eta_{s}=[1023\div 147]=6$ ciphertexts into one ciphertext, then we get:

The communication cost is:

We compare the values of the equations (15), (16), and the equations (9), (10), the cost is reduced by 78%.

From the estimation, we can see that ciphertext operation optimization is theoretically effective.

In the Mix Tree Mode, every party will build a certain number of trees using their local features, and this procedure repeats until the max epoch is reached or the stop condition is met.

When the active party builds a decision tree, the active party simply builds the tree locally. When the tree is built in the passive party, the relevant passive party receives the encrypted g/h, assisted by the active party, to find the best split point. The structure of the tree and split point is retained on the passive party, while the leaf weight is retained on the active party. This mode is suitable for vertical federated learning under data balancing. In this way, the number of interactions and communication costs can be significantly reduced, thus speeding up training. Figure 3 demonstrates the mix tree training process.

The Layered Tree Mode is another optimization mechanism, which is designed for vertical federated learning under data balancing.

Similar to The Mix Tree Mode, the active and the passive party are responsible for different layers in the tree when building a decision tree. Every decision tree has in total $h=h_{active}+h_{passive}$ layers. The passive party will be responsible for building the first $h_{passive}$ layers, assisted by the active party. The active party will build the next $h_{active}$ layers. All trees will be built in this ’layered’ manner. In this way, the number of interactions and communication costs can be significantly reduced, thus speeding up training. Figure 4 demonstrates the layered tree training process.

We propose a split gain function for multi-output decision tree. Given a $l$ label multi-classification task, we use g and h to denote the gradient/hessian vectors which have $l$ elements, each element corresponds to the $g$/$h$ of each label. In a multi-output decision tree, every leaf obtains an output w, which also has $l$ elements. We rewrite the equation 3:

where $\textbf{y}_{i},\hat{\textbf{y}}^{(t-1)}_{i}$ are ont-hot label vector and predict score vector, H is the hessian matrix. In SecureBoost-MO, we use cross-entropy as the multi-classification loss function, so H is a diagonal matrix. By minimizing $L^{(t)}$, we get

as the weight function and the split gain function:

SecureBoost-MO is based on the above leaf weight and split gain function.

The splitting finding process of Multi-output boosting tree has basically the same as that of the standard GBDT trees, but there are two differences:

• •

  In standard GBDT trees bin values are scalar $g$, $h$ values. When calculating the histogram in MO-trees, aggregated terms in the bin are g, h vectors.

• •

  When calculating the split gain and leaf weights, we use mo-gain, mo-weight equation (18), (20).

As a result, in the vertical federated learning scenario, we need to design a new structure that supports encryption, decryption of g, h vectors, and support operations in the histogram calculation, histogram subtraction, and split-info building.

To fulfill this requirement, we design a Multi-Class packing algorithms based on our ciphertext optimization framework. Remind that $b_{gh}$ represent the plaintext bit length for a pair of $g$, $h$. For a HE schema that has a plaintext space of $\iota$ bits, and we have $k$ classes in total, we can pack:

classes in a ciphertext, and in total we need:

integers to pack gh vectors of an instance. With this strategy, we are able to pack g and h vectors of a sample into a small amount of integers and then we encrypt them to yiled a ciphertext vector. Details of the above process are shown in Algorithm 1.

Figure 6 gives an intuitive illustration of Multi-Class GH Packing.

Following, we can describe the split-finding procedure of SecureBoost-MO:

• •

  At the beginning, the active party calculates the multi-classification gradient and hessian vectors for each instances. The active party packs and encrypts them using Algorithm 1, and gets a matrix [GH] which contains encrypted ciphertext vectors.

• •

  The active party sends [GH] to all the passive parties. The passive parties calculate histograms and construct split-info directly on ciphertext vectors.

• •

  The active party decrypts split-info and recovers accumulated g, h vectors using Algorithm 2 and finds out global optimal split node.

We conduct experiments to compare the training time of SecureBoost+ with ciphertext operation optimization, and SecreuBoost on the four binary classification data sets. We only consider the time spent on tree building and ignore the time spent on non-tree building, such as time spent on data I/O, feature engineering and evaluation. For both SecureBoost+ and SecreuBoost, we both build 25 trees, and calculate the average time spent on each tree. The results are showed in Figure 7. We can see that the proposed SecureBoost+ obviously outperforms SecureBoost: In the four datasets, Secureboost+ are 6.63x, 6.03x, 7.33x, 22x faster than SecureBoost. From the experimental results, we can find that with the increase of the number of instances and feature dimension, SecureBoost+ will have more obvious advantages.

In order to evaluate the impact of ciphertext operation optimization on the model performance, we compare the model performance of SecureBoost+, XGBoost and SecureBoost. We use AUC score as the model performance evaluation metric. The results are shown in Table 2. From the results, we can see that SecureBoost+ performs just as well as XGBoost and SecureBoost in this setting.

We conduct experiments to compare the training time of SecureBoost+ with two training mechanism optimizations, SecreuBoost+ with ciphertext operation optimization, and SecureBoost on the four binary classification datasets. The results are showed in Figure 7. It shows the average tree building time spent on each tree. It is no doubt that SecureBoost+ with the mix tree mode or layered tree mode will build tree faster than SecureBoost+ with ciphertext operation optimization only, and also faster than SecureBoost. This is because it skips global split-finding and inter-party communications with certain strategies. In the four datasets, SecureBoost+_Mix are 1.65x, 1.96x, 1.60x, 1.58x faster than SecureBoost+_Ciphertext, while SecureBoost+_Mix are 10.96x, 11.80x, 11.69x, 35.30x faster than SecureBoost. In the four datasets, SecureBoost+_Layered are 1.15x, 1.13x, 1.10x, 1.37x faster than SecureBoost+_Ciphertext., while SecureBoost+_Layered are 7.64x, 6.83x, 8.09x, 30.77x faster than SecureBoost.

We will pay much attention to the model performance of SecureBoost+ with the mix tree mode and the layered tree mode since their strategies intentionally skip the global split finding on every tree node. The results are shown in Table 2. SecureBoost+_Mix and SecureBoost+_Layered have slight performance loss compared to XGBoost and SecureBoost+_Ciphertext, but the losses are very small. According to our experimental analysis, the two mode sometimes require a few more trees to catch up with the performances of SecureBoost+_Ciphertext. But from the result of Epsilon data set, we believe that the two training mechanism can obviously accelerate training when the data set contains high dimensional features and features are balanced distributed.

As shown in Figure 8, in the multi-classification training task with 25 epoches, SecureBoost+_Ciphertext needs to build 275, 175 and 250 trees respectively in the Sensorless, Covtype, SVHN datasets, while SecureBoost-MO only needs to build 38, 37, 47 trees respectively. The tree numbers of SecureBoost-MO is far less than SecureBoost+_Ciphertext.

We conduct experiments to compare the training time of SecureBoost-MO with SecureBoost+_Ciphertext on the three multi-classification datasets. It should be noted that in this experiment, the time is the total training time, not the training time for each tree. In the SecureBoost+_Ciphertext, we run 25 epoch, which has 275 trees in the Sensorless dataset, while in the SecureBoost-MO, we need to build 38 trees to achieve the similar model performance. The results are showed in Figure 9. We can see that SecureBoost-MO obviously outperforms SecureBoost+_Ciphertext: In the three datasets, SecureBoost-MO are 3.92x, 3.72x, 1.57x faster than SecureBoost+_Ciphertext.

We use accuracy scores as the model performance evaluation metric in the multi-classification tasks. The results are shown in Table 3. The results show that SecureBoost+_Ciphertext has relatively better accuracy scores than XGBoost in some datasets, and SecureBoost-MO performs as well as SecureBoost+_Ciphertext.