Branch-Free Encrypted Path Reasoning: Summing All Knowledge-Graph Paths Instead of Pruning Them

Homomorphic encryption lets a server compute on data it cannot read. Modern schemes such as CKKS (an approximate-arithmetic lattice scheme) pack thousands of numbers into one ciphertext, in independent "slots". One operation then acts on all slots at once, so densely filled ciphertexts become cheap per item. The catch is that moving data between slots requires a "rotation", which is far more expensive than arithmetic. Multi-hop reasoning over knowledge graphs, which follows chains of relations such as drug → targets → gene → regulates → pathway, has the opposite problem. The number of candidate paths grows roughly as degree to the power of hops. Every practical plaintext method copes by pruning, that is, by discarding unpromising branches based on intermediate scores. Under encryption the server cannot see those scores. It must either compute every branch anyway or leak which branches it dropped.

This note argues that the encrypted setting should drop pruning altogether. A plaintext result already shows that the sum over all bounded-length relation paths can be computed exactly by dynamic programming in time polynomial in the number of nodes, not exponential in path length (Compositional Learning of Embeddings for Relation Paths in Knowledge Base and Text). That computation has no branches and repeats identical arithmetic at every node, which is exactly what slot-packed ciphertexts want. We propose to build the encrypted version and to design its slot layout so that relation weights cost no rotations. We also aim to make the remaining rotation cost depend on a padded, public bandwidth bound and not on the degree of the largest hub entity.

Core Claim

Multi-hop scoring of relation paths over a private, encrypted knowledge graph can match plaintext accuracy at practical latency. Two layout decisions make this possible.

First, entities are scored with diagonal relation matrices (the Bilinear-Diag model, where each relation is an elementwise reweighting of an embedding vector). If embedding dimensions run along the slots, applying a relation becomes a slot-wise multiply with zero rotations. The server's plaintext weights can also be folded into the encrypted adjacency in advance, so each hop costs the running state about one multiplicative level.

Second, all rotations come from neighbor aggregation. Each rotated copy of the state is reused across every relation type and every path type that shares a prefix. The rotation count therefore no longer grows with the number of relation types. After the client relabels nodes and splits hubs into bounded-degree virtual copies, it grows only with the number of nonzero adjacency diagonals, padded to a public bound.

Concretely, for a path type $\pi = (r_1,\dots,r_L)$ we evaluate the recursion

$$h^{(l)}_v \;=\; w_{r_l} \odot c_v \odot \sum_{u:\,(u,r_l,v)\in\mathcal{G}} h^{(l-1)}_u,$$

where $h^{(l)}_v \in \mathbb{R}^D$ is the summed representation of all length-$l$ paths of the given type ending at node $v$, $w_{r_l}$ is the diagonal of relation $r_l$, and $c_v$ is an intermediate-node parameter. This form is adapted from the "paths + nodes" variant of ALL-PATHS. The final score of a query pair $(s,t)$ is an inner product of $h^{(L)}_t$ with a learned target vector. The number of operations scales with edges × hops × $D$, not with $d^L$, because the dynamic program sums over node sequences one hop at a time.

Relation to Prior Work

The closest system is Penguin. It encrypts both the adjacency matrix and the node features of a graph and evaluates graph convolutional networks (GCNs) under CKKS. Its two-dimensional node/feature packing minimizes rotations at a node-to-feature ratio of about 2. Its "interleaved assembly" step repacks ciphertexts when feature width shrinks. Penguin supplies our threat model and much of our packing toolkit. It also motivates the work, because its latency rises to "thousands of seconds" on Pubmed. Our setting differs in three ways. Penguin handles a single homogeneous adjacency with dense feature transforms (which need rotations), one to two hops, and no relation types. We handle a multi-relational adjacency with diagonal transforms, several hops, and explicit hub handling.

ALL-PATHS supplies the method. On NCI-PID it reports that exhaustive enumeration at length 5 would need $4.0\times10^{18}$ memory units, against $1.9\times10^9$ for dynamic programming. It also shows that modeling paths and intermediate nodes raises MAP from 28.56 (plain Bilinear-Diag) to 39.31. ALL-PATHS is entirely plaintext and assumes free random access. We contribute the slot layout, the depth budget, and the leakage analysis.

EinHops automates tensor-contraction layouts under CKKS. It is a candidate compiler substrate, but it does not address sparse, degree-skewed adjacency.

The pruning-based plaintext methods act as constraints. NuTrea uses look-ahead subtree backup. CRFR uses actor-critic fragment search. DC-MLMH samples paths and takes a majority vote. All three rely on data-dependent branching, which an oblivious server cannot exploit, so we do not try to port them. The observation that hubs cause sudden spikes in branching (Shen et al.) is the reason a naive worst-case-degree layout would be mostly zero padding.

Research Program

The setting follows Penguin. A client, for example a hospital holding a private biomedical graph, encrypts the subgraph relevant to a batch of queries: topology, relation types, and entity embeddings. A server holds a trained path model in plaintext and returns encrypted scores. Before encrypting, the client runs a cheap local extraction of the L-hop node set around the query entities. This set grows with the number of nodes, not paths. The client caps it by splitting hubs, then pads it to one of a few public size classes.

The layout places $D$ embedding dimensions contiguously in slots. Blocks of $B$ nodes share a ciphertext, and independent queries fill any spare slots, as in CryptoNets. Within a block, neighbor aggregation uses the generalized diagonal method. For each nonzero node offset $j$, the server rotates the state by $jD$ slots and multiplies it by the encrypted $j$-th diagonal of each relation's adjacency. That diagonal has the server's $w_r \odot c_v$ already multiplied in. Each rotated copy is computed once and reused by every relation and by every path type in a prefix tree of the $K$ scored path types.

The client does two things to keep the number of offsets small. It relabels nodes with a bandwidth-reducing ordering. It replaces any entity with degree above a threshold $\tau$ by $\lceil \deg/\tau \rceil$ virtual copies placed in different blocks, whose partial sums are recombined by a fixed, public number of extra rotations. The offset count is padded to a public bound for each size class, so the server learns only the size class.

We will analyze three properties. The first is rotation count as a function of offsets, block count, and $K$. The second is multiplicative depth, which we expect to be about one level per hop plus a constant, because the weights are folded into the adjacency; this should allow $L\le 3$ without bootstrapping at $N=16384$, to be verified. The third is exact leakage: size class and public bounds only.

Baselines

The naive reference point is the same dynamic program run under CKKS with a straightforward layout. One relation adjacency is encrypted per relation, worst-case-degree padding is used, and rotations are not shared across relations. This shows how much of any gain comes from layout as opposed to encryption alone. Run in plaintext, the same recursion gives the accuracy ceiling. We will reproduce ALL-PATHS+NODES on NCI-PID. The paper reports MAP 39.31 and Hits@10 52.53, and the encrypted system should land within about half a MAP point of our own plaintext reproduction.

The strongest existing encrypted competitor is Penguin, extended to relation-typed adjacency as a relational GCN with $L$ layers and dense per-relation weights. It uses Penguin's two-dimensional packing and interleaved assembly, with tuned node and feature block sizes. It is the strongest competitor because it is the only cited system that encrypts both topology and features at 128-bit security. Penguin reports a 10.62× speedup over earlier homomorphic matrix baselines and 0.24 s amortized per node on Cora, but no multi-relational number. We will therefore run both systems ourselves on identical padded subgraphs, the same CKKS parameter set, the same hardware, the same library, and the same parameter-search budget. Beating it means lower end-to-end latency and fewer rotations per query at equal or better MAP on NCI-PID. We also want the advantage to widen as the number of relation types grows.

Two ablations isolate our ingredients. The first removes rotation sharing across relations, which tests whether the rotation count really stops growing with the number of relation types. The second removes hub splitting and relabeling, which tests whether hubs then force worst-case padding.

Why not just…?

Why not just run Penguin as a multi-relational GCN? This is the most serious threat, because a linear relational GCN computes something close to our recursion. The differences are concrete. Penguin's dense feature transform needs rotations at every layer, and its packing ratio does not account for relation types. The head-to-head comparison above decides the question. If extended Penguin matches our latency, our contribution reduces to hub splitting and the proof that pruning is unnecessary, and we will report it that way.

Why not just have the client count relation paths locally and send encrypted counts to a linear model on the server? Counting typed paths requires no model weights, so the client can do it in plaintext. The server would then evaluate only a cheap encrypted linear head. This would plausibly work if path counts carried most of the signal. The file has no reported number for count-only features on NCI-PID. ALL-PATHS does show that intermediate-node parameters, which live inside the sum and belong to the server, are part of what lifts MAP to 39.31. We will train a count-feature model on the same splits. A gap under one MAP point would mean the encrypted dynamic program is not worth its cost.

Why not just prune obliviously with an approximate top-k, or run NuTrea inside a hardware enclave? Oblivious beam search needs polynomial approximations of comparisons at every hop, which consume depth, and it still touches every branch. Enclaves run pruning at native speed, but traversal access patterns leak structure, and TEE-X notes that enclave-hosted models remain exposed under several threat models. We will include an encrypted beam-search variant using minimax-polynomial comparison as a measured baseline. We will not argue against enclaves beyond stating the different threat model.

Proposed Experiments

The primary benchmark is NCI-PID link prediction using the KB-only graph. The text-mention extension is too large for the first round. We report MAP and Hits@10 against the plaintext reproduction, together with latency per query, amortized latency per batch, rotations, levels consumed, and memory. For FB15k-237 and WordNet, Lacuna holds no reported result for this path model, so we will establish plaintext references ourselves. Cora and Citeseer serve only as a latency sanity check against Penguin's published operating point, with relation count set to 1. Synthetic power-law graphs with controlled maximum degree form the hub stress test.

Three results would be decisive. The first is accuracy parity: encrypted MAP within 0.5 of plaintext at $L\le3$. The second concerns rotation scaling. Rotations should stay flat as the number of relation types rises from 1 to 100, while the extended Penguin baseline grows. Rotations should also track the padded offset bound and not $d_{\max}$ on the stress graphs. The third is the count-feature check. If client-side path counting comes within one MAP point, the proposal's premise fails.