# Bayesian Binary Search
## 2 Methodology
### Probabilistic Bisection Step
The total capacity of the channel \(\{u,v\}\) is defined as \(c_{\{u,v\}}=y_{(u,v)}+y_{(v,u)}\). We are provided with the total channel capacities \(c_{\{u,v\}}\) for all channels in the graph, but we only know the individual values \(y_{(u,v)}\) for a subset of edges. Note that knowing\(y_{(u,v)}\) allows us to determine \(y_{(v,u)}\), since \(y_{(v,u)}=c_{\{u,v\}}-y_{(u,v)}\). Therefore, we can focus on predicting \(y_{(u,v)}\). Moreover, since we are given \(c_{\{u,v\}}\) for all edges, and we know that \(0\leq y_{(u,v)}\leq c_{\{u,v\}}\), we also have that \(y_{(u,v)}=p_{(u,v)}c_{\{u,v\}}\), where \(0\leq p_{(u,v)}\leq 1\). Intuitively, \(p_{(u,v)}\) is the proportion of the channel capacity which belongs to the \((u,v)\) direction. From this, we see that we focus on predicting \(p_{(u,v)}\), and then use it to obtain \(y_{(u,v)}\). Therefore, our primary task is to predict \(p_{(u,v)}\) for all edges where it is not observed. #### 3.2.2 Data Collection and Preprocessing

The data used in this experiment are a combination of publicly available information from the Lightning Network and crowdsourced information from nodes in the network. A snapshot of the network from 15 December 2023 was used in this experiment. Balance information for each node is represented by its local balance, recorded at one-minute intervals over the preceding hour. These data were converted into a probability density function (PDF) through Kernel Density Estimation. Subsequently, a balance value was sampled from each PDF, serving as the representative local balance for the corresponding channel within the dataset. ### Methodology

The following section outlines the details of our modeling approach. #### 3.3.1 Modeling

We will predict \(p_{(u,v)}\) by learning a parametric function:

\[\hat{p}_{(u,v)}=f_{\Theta}(u,v,G,\mathbf{x}_{u},\mathbf{x}_{v},\mathbf{e}_{(u,v)},c_{\{u,v\}})\]

where \(\Theta\) are learnable weights, \(\mathbf{x}_{u},\mathbf{x}_{v}\), and \(\mathbf{e}_{(u,v)}\) are the node and edge features, respectively, while \(c_{\{u,v\}}\) is the capacity of the channel. While several choices are possible for \(f_{\Theta}\), such as multi-layer perceptrons ([22]) or Graph Neural Networks, we focus on random forests for this work given their simplicity and efficacy. In particular, our random forest (RF) model operates on the concatenation of the features of the source and destination nodes as well as the edge features:

\[\hat{p}_{(u,v)}=\text{RF}(x_{u}||z_{u}||x_{v}||z_{v}||e_{(u,v)})\]

The model was trained using a Mean Squared Error loss. #### 3.3.2 Node Features

* **Node Feature Flags** A vector of 0-1 indicating which of the features each node supports. For example, feature flag #19, the wumbo flag. * **Capacity Centrality** The node's capacity divided by the network's capacity. This indicates how much of the network's capacity is incident to a node. * **Fee Ratio** Ratio of the mean cost of a node's outgoing fees to the mean cost of its incoming fees. #### 3.3.3 Edge Features

* **Time Lock Delta:** The number of blocks a relayed payment is locked into an HTLC. * **Min HTLC:** The minimum amount this edge will route (denominated in millisats). * **Max HTLC msat:** The maximum amount this edge will route (denominated in millisats). * **Fee Rate millimsat:** Proportional fee to route a payment along an edge (denominated in millimilisats). * **Fee Base mast:** Fixed fee to route a payment along an edge (denominated in millisats). #### 3.3.4 Positional Encodings

Positional encoding is essential for capturing the structural context of nodes, as graphs lack inherent sequential order. Utilizing eigenvectors of the graph Laplacian matrix as positional encodings provides a robust solution to this challenge. These eigenvectors highlight key structural patterns, enriching node features with information about the overall topology of the graph [23].