Collaborative and Confidential Junction Trees for Hybrid Bayesian Networks

Thank you for the insightful review. Please see our reply to the outlined points. We would be happy to clarify any unclear or unaddressed aspects.

Weaknesses

[W1] No mention of Multiply Sectioned Bayesian Networks

Performing loopy belief propagation over Multiply Sectioned Bayesian Networks would (indeed) break the strong root constraint and lead to poor inference quality in hybrid domains. Furthermore, loopy belief propagation entails sending more messages (due to the iterative nature of the algorithm) and is proven to converge only on graphs with at most one cycle [1]. We will update the related work section with this information.

[W2] Is there a privacy leak over threshold variables?

Please see the answer to Q2.

[W3] Possible data leak in two-party scenario

Indeed, when only two parties are involved, the proposed method does not protect the private posterior of interface variables, as doing so is impossible. Intuitively, consider computing the sum of $N$ secret numbers $x_1, ..., x_N$ (Equations 7 and 8 in the paper). If $N>2$ a certain party $i$ knows $x_i$ and $y = \sum^N_{j = 1}x_j$ from which party $i$ cannot reconstruct the values of $x_{j \neq i}$. If $N=2$, party $i$ can reconstruct $x_j = (x_i + x_j) - x_i = y - x_i$. Similar reasoning also holds for products.

The work from Kearns et al. [2] builds upon this basic idea to explore the limitations of confidentiality in Bayesian Networks and specific methodologies including sum-product message passing. Notably, that work establishes a generalized definition for confidentiality in Bayesian Network applications (Definition 1 from [2]):

Let $\Pi$ be any protocol for the $k$ parties to jointly compute the value $y = f(x_1, ... ,x_k)$ from their $n$-bit private inputs. We say that $\Pi$ is privacy-preserving if for every $1 \leq i \leq k$, anything that party $i$ can compute in polynomial time in $n$ following the execution of $\Pi$, they could also compute in polynomial time given only their private input $x_i$ and the value $y$.

We abide by this definition which we include in Appendix B.

Questions

[Q1] How does the protocol work with 3+ parties?

The junction tree forms 2 star networks corresponding to discrete and continuous variables, respectively (as also remarked by the reviewer), joined via their hubs (i.e., the interface cliques). Please note that, as stated in the paper, the Junction Tree dictates the computational logic within the protocol, not the actual distribution of data across parties. Thus, an interface clique is not centralized or controlled by any party. Instead, parties solve inference collaboratively over this clique.

[Q2] How are threshold variables protected?

Unlike interface variables, whose protection depends on homomorphic encryption and secret sharing during alignment and inference, threshold variables are not shared between parties and only used locally. We will better emphasize this aspect in the methodology section.

[Q3] What is the “#Arc” field in the datasets table?

"#Arc" in Table 5 refers to the number of edges in the original network. It describes the number of relationships between variables in the network. However, having more edges does not necessarily imply an increase in the number of parameters (#Params column) reported in the same table. #Params depends on the network's edge distribution and the representations of variables. For instance, a discrete binary variable with two binary parents will require $2^3=8$ parameters. Whereas, one discrete variable with one parent both with three states will require $3^2=9$ parameters.

Limitations

[L1] Cost is exponential in the number of variables in each party

Per the nature of discrete Bayesian Networks, inference is NP-Hard. However, our algorithm is agnostic to the inference algorithm used locally by each party. Thus, instead of the Variable Elimination (as employed in our experiments) parties could indeed autonomously harness auxiliary junction trees for local inference exponential in the tree-width instead of the number of variables. Note that using nested Junction Trees would not affect communication costs.

[L2] Undermentioned caveats in two-party case

As correctly identified by the reviewer, there is an unavoidable confidentiality leak in the two-party case. We will update the paper's method section to emphasize the phenomenon. More specifically, the issue stems from the need to disclose the output of a bijective function with two inputs, with one of the inputs also being known beforehand. Thus, no secure multiparty computation technique, including homomorphic encryption, can address the issue. Please refer to the answer of W3 for additional details.

References

[1] Zivan, Roie, Omer Lev, and Rotem Galiki. "Beyond trees: Analysis and convergence of belief propagation in graphs with multiple cycles." AAAI Conference on Artificial Intelligence (AAAI), 2020.

[2] Kearns, Michael, Jinsong Tan, and Jennifer Wortman. "Privacy-preserving belief propagation and sampling." Advances in Neural Information Processing Systems 20 (NeurIPS), 2007.

My original comments were mostly minor and my questions were answered accordingly and as expected.

After reading other reviews, particularly rRs9 thoughts on impact and novelty and the issue being addresed, I don't see a clear reason to not accept and have raised my score accordingly.

Thank you for your valuable comments and feedback. It's helpful for us to further improve this work. Please see our reply to the highlighted weaknesses. We will be happy to follow up on any of the points.

Weaknesses

[W1] No high-level proof of confidentiality

Below, we outline why both of Hybrid CCJT's collaborative phases preserve confidentiality during inference:

1. Collaborative Discrete Inference CPD tables of interface variables (say, $X$) are "augmented" to allocate space for all parents of $X$ $\text{pa}(X)$, some of which might be private. This step is required to ensure the correct outcome of HE, CPD product, and CPD normalization as in Equation 4. We show that this step does not leak any information about such private parent variables by proving that their marginals yield a uniform distribution $\mathcal U(\Omega(\text{pa}(X)))$. Where $\Omega(X)$ is the set of states of variable $X$. We prove this in Proposition B.2. Then, we prove that, after message passing, the marginal over these parent variables remains uniform. This ensures no information about such private variables leaks at inference time. We prove this in Proposition B.5. Furthermore, note that parties encrypt the names of variables and their states to enhance confidentiality further.
2. Collaborative Continuous Inference Unlike discrete variables, continuous counterparts do not require computing and correctly applying normalization factors potentially defined over private factors. Thus, continuous private variables are inherently protected during alignment. At inference time, the means and variances of shared continuous variables are calculated using multi-party secret sharing, which updates the parameters of such shared continuous interface variables. This approach inherently safeguards the information of private variables, as they are not involved in the update process.

[W2] Missing implementation details on the inference protocol

We will prepare a more detailed explanation of the inference protocol in the methodology section and a more detailed pseudocode and a diagram to be included in the appendix. The inference is divided in three steps (of which two are collaborative) and follows the logic of the Lauritzen algorithm [1].

1. Collaborative Continuous Inference The first step requires marginalizing continuous variables and finding the strong marginals over the threshold variables. Recall that threshold variables are the discrete variables with at least one continuous child. In short, we aim at computing $P[T|\Gamma = e]$, where $T$ is the set of threshold variables and $\Gamma = e$ is some continuous evidence. To do so, parties collaboratively compute the updated parameters of interface continuous variables given the set of continuous evidences as in

$${\mu}(X) = \sum_{i \in \mathbb P} w_i\mu_i(X), \quad \sigma(X) = \sum_{i \in \mathbb P} [w_i\sigma_{i}(X)] + \sum_{i \in \mathbb P}[w_i(\mu - \mu_{i}(X))^2 ]$$

where the parameters $\mu_i$ and $\sigma_i$ are obtained locally by computing $P[I_\Gamma | \Gamma=e]$. Once these new parameters are obtained, they can help compute the marginals over the threshold variables by just marginalizing all the continuous variables.

2. Collaborative Discrete Inference Once parties find the marginals of threshold variables, the querying party needs to find the strong marginals over the remaining discrete variables. For this, parties compute $P[I_\Delta | \Delta = e]$, the posterior of discrete interface variables given their discrete evidence. The querying party receives these posteriors and merge them via secret sharing to find the geometric mean:

$$P[I_\Delta] = \prod_{i \in \mathbb P} P_i[I_\Delta]^{w_i}$$

The querying party can then use this factor to update its local probability distribution via sum-product message passing [2] (Equation 2 from the paper). For a more detailed explanation on the sum-product message passing please refer to Section 10.2 in the book of Koller [3].

3. Local query At this point in the protocol, the querying party can find the posterior of any variable it owns. For discrete variables, the posterior is found by marginalizing non-target variables, as in a normal junction tree. For continuous variables, the posterior is found by marginalizing all non-threshold variables and performing weak marginalization:

$$P[X] = \mathcal N\Bigl(X; \sum_{s \in \Omega(\Delta_{Q})}P[\mathcal T_Q=s] \mu_{s}(X), \sum_{s \in \Omega(\Delta_{Q})}P[\mathcal T_Q=s] \{\sigma_{s}(X) + (\mu - \mu_{s}(X))^2\} \Bigr)$$

[W3] Limited communication cost analysis on hybrid domains

We repeated the experiments from Table 1 with new variable splits to derive further insights in the communication costs of Hybrid CCJT. In Table C isolates the communication costs of Discrete and Continuous collaborative inference. This allows us to better analyze the communication costs gains obtained by natively handling continuous data. Furthermore, we report standard deviation measurement of communication costs.

Table C: Communication cost split for discrete and continuous variables

References

[1] Lauritzen, Steffen L., and Frank Jensen. "Stable local computation with conditional Gaussian distributions." Statistics and Computing (SC), 2001.

[2] Shenoy, Prakash P., and Glenn Shafer. "Axioms for probability and belief-function propagation." Machine intelligence and pattern recognition, 1990.

[3] Koller, Daphne, and Nir Friedman. "Probabilistic graphical models: principles and techniques". MIT Press, 2009.

Thank you for your positive feedback. Please see our reply to the limitations, weaknesses, and questions. We look forward to any further comments.

Weaknesses

[W1] Underspecified security guarantee scope in main text

We will update the abstract and introduction to mention the semi-honest, non-collusion setting. Moreover, in the second paragraph of subsection 3.2, we will visually highlight the "semi-honest" denomination alongside the existing one for the "adversarial model".

[W2] Underemphasized practical assumptions for data alignment in main text

We will explicitly enumerate the assumptions for successful alignment. Namely, as correctly identified by the reviewer, shared variables across parties should have (i) the same name when defining identical concepts, and (ii) the same discrete states or continuous measurement units. Furthermore, we will also point to an appendix with a misalignment-related discussion based on the Q3 answer below.

[W3] Undercontextualized $331\times$ communication improvement claim

We concur that the $331\times$ communication improvement is in a scenario that heavily favours the proposed method. We will additionally report the median ($10.4\times$) communication improvement observed alongside the maximum in the abstract and introduction for a fairer presentation.

Questions

[Q1] What is the computational overhead of the cryptographic tools the protocol employs?

The protocol relies on private set intersection, secret sharing (additive/product-based), and homomorphic encryption (HE) at different points in its lifecycle. Among the enumerated cryptographic tools, only HE involves a significant computational overhead, while the primary bottleneck for the others is network latency. HE is used exclusively during discrete factor alignment. The results below split the HE computation time across:

1. Context Generation: Generation of HE keys and parameters.
2. Encrypted Column Summation: The actual HE-encrypted computation; used to compute column normalization factors (i.e., $\alpha$ in Equation 4 in the paper).
3. CPD combination: Alignment of party CPDs based on the HE-computation outputs.

We report the per-factor mean and standard deviation of each HE substep and the total time required for all factors.

Table A: Results on discrete datasets (10% overlap):

As expected, substep 2, i.e., encrypted column summation, is the most time-consuming one, taking up to 96 seconds in the worst-case scenario, but remains under one second in 6 out of 10 experiment scenarios. Its time requirements increase overall with the number of parties sharing factors. In contrast, substeps 1 and 3, i.e., context generation and CPD combination, run in under one second and one millisecond, respectively. Moreover, we note that the HE procedure represents a one-off setup cost, after which parties may perform unlimited queries until one of them updates their local network.

Table B: Results on hybrid datasets (30% overlap):

When dealing with hybrid domains, we notice that encryption takes significantly more time on the discretized variants. While Hybrid CCJT maintains the entire encryption process under one second for both Sangiovese and Healthcare datasets, $\Delta$-CCJT's encryption cost grows as the discretization coarseness is reduced (i.e., more states). These results also reaffirm the gains in memory and communication costs of natively handling CLG variables compared to discretizing them, as further highlighted in our answer to Q2.

We will add the above tables and discussion as a new appendix.

[Q2] Is local marginalization in Equation 9 the primary reason for improved communication efficiency?

Equation 9's local marginalization is the primary reason for improved communication when only considering discrete variables. When incorporating continuous variables, a significant portion of Hybrid CCJT's efficiency also comes from reducing the representation space from $O(2^N)$ states required by the discretization used in $\Delta$-CCJT or CCBNet, down to $O(N^2)$ parameters required by representing continuous variables in the canonical form.

For more details on the canonical representation of CLG variables, please see Appendix C of the paper. Table 1 from the paper contains quantitative results on the improvements given by Equation 9 (i.e., $\Delta$-CCJT vs CCBNet; for example, $15.5\times$ on average for 5 states) and natively handling CLG variables (i.e., Hybrid CCJT vs $\Delta$-CCJT; for example, $1.9\times$ on average for 5 states).

[Q3] How does the protocol handle data representation inconsistencies?

While the current protocol assumes no data representation inconsistencies, the name-matching procedure is flexible in being updated to mitigate such issues. Inconsistencies can appear at the level of variable definition (parties using different names for the same concept) or their representation (state/measurement mismatches for discrete and continuous variables, respectively).

Some possible mitigation strategies are:

• parties giving synonyms for variable names;
• normalizing variable names (e.g., as lowercase);
• for state alignment mismatches in discrete variables, states not present in all parties could get mapped to a single miscellaneous state;
• for measurement unit mismatches in continuous variables, parties could update their local representations to an agreed-upon unit.

We will update Appendix H with the above discussion.

Limitations

[L1] No detailed computation time analysis (for cryptographic primitives)

The computation complexity of homomorphic encryption in solving an overlap is $O(L \cdot N \log(N))$, bounded by $L$ chained multiplications of a size $N$ ciphertext. $L$ is the maximum number of parties in an overlap. $N$ is a power of two (in the range $2^{10}$--$2^{15}$), derived from the desired precision, the maximum output scale, and $L$. Successive multiplications increase complexity linearly [1]. The cost of a single multiplication is linearithmic [2].

In our implementation, solving a private set intersection between two parties is $O(m \log(m))$ time, where $m$ is the maximum number of variables among the two parties.

For an empirical overview of homomorphic encryption overhead, please refer to our answer to Q1.

[L2] Data misalignment issues insufficiently addressed

Please see the answer to Q2.

[L3] Scalability concerns not fully explored

We acknowledge that larger-scale tests on continuous and hybrid networks would be beneficial. We note, however, that the primary determiner of our method's scalability compared to a centralized approach is the total number of overlaps and the number of parties involved in each. The sizes of each party's local network or the number of parties are not the bottleneck. For time complexity, see the answer to L1. For communication overhead, cost is predominantly related to processing discrete variables. As evidenced by our main evaluation results and our reply to L3 of Reviewer HuYN, continuous variables have much lower communication requirements, making them even less of an issue for scaling.

Moreover, in our motivating example, we expect overlap percentages to be lower than 30% as covered in our experiments. Also, in such settings with highly specialized participants, at most a handful of parties would model most concepts. Thus, the insights from our experiments with up to 8 parties remain relevant. However, we acknowledge that other setups are also plausible (e.g., a central concept modeled by many parties).

References

[1] Cheon, Jung Hee, et al. "Homomorphic encryption for arithmetic of approximate numbers." International conference on the theory and application of cryptology and information security (ASIACRYPT), 2017.

[2] Al Badawi, Ahmad, et al. "OpenFHE: Open-source fully homomorphic encryption library." 10th workshop on encrypted computing & applied homomorphic cryptography (WAHC), 2022.