privora-graph

Mathematical Foundations & Proofs in PrivoraGraph

This document derives the formal privacy, bi-temporal graph, and Byzantine resilience guarantees implemented and property-tested across privora-graph.


1. Subsampled Gaussian Rényi Differential Privacy (RDP) & DP-SGD

In src/privora_graph/privacy/dp_sgd.py, every training record $x_i$ in mini-batch $\mathcal{B}_t$ (Poisson subsampling rate $q = B / N$) has its exact individual parameter gradient clipped in $L_2$ norm before Gaussian perturbation:

\[\bar{g}_i = g_i \cdot \min\!\left(1, \frac{C}{\|g_i\|_2}\right), \qquad \tilde{g}_t = \frac{1}{B}\!\left(\sum_{i \in \mathcal{B}_t} \bar{g}_i + \mathcal{N}(0, \sigma^2 C^2 I)\right)\]

Because $|\sum_{i \in \mathcal{B}} \bar{g}i - \sum{i \in \mathcal{B}’} \bar{g}i|_2 \le C$ for any adjacent datasets $D, D’$ differing in one record, the exact integer-order Rényi divergence $D\alpha(\mathcal{M}(D) | \mathcal{M}(D’))$ of order $\alpha \in {2, \dots, 64}$ satisfies the Mironov-Talwar-Zhang (2019) binomial expansion:

\[\rho(\alpha; q, \sigma) = \frac{1}{\alpha - 1} \log \sum_{k=0}^{\alpha} \binom{\alpha}{k} (1 - q)^{\alpha - k} q^k \exp\!\left(\frac{k(k - 1)}{2 \sigma^2}\right)\]

By linear additivity of Rényi divergence under adaptive sequential composition across $T$ steps and the tight Balle et al. (AISTATS 2020) conversion theorem, the final mechanism satisfies $(\varepsilon(\delta), \delta)$-Differential Privacy with:

\[\varepsilon(\delta) = \min_{\alpha \in \{2,\dots,64\}} \left\{ T \cdot \rho(\alpha; q, \sigma) + \frac{\log(1/\delta) + (\alpha - 1)\log(1 - 1/\alpha) - \log \alpha}{\alpha - 1} \right\}\]

2. Bi-Temporal Point-in-Time Algebra & Simplex-Conserving CSR PageRank

2.1 Snodgrass SQL:2011 Bi-Temporal Isolation (graph_engine.py)

Every relational assertion $e = (u, r, v, [v_0, v_1), [\tau_0, \tau_1))$ separates real-world validity $[v_0, v_1)$ from ledger belief $[\tau_0, \tau_1)$. The snapshot operator $\mathcal{S}(G; T_{\text{valid}}, T_{\text{tx}})$ retains $e$ iff:

\[(v_0 \le T_{\text{valid}} < v_1) \;\land\; (\tau_0 \le T_{\text{tx}} < \tau_1)\]

Consequently, any retroactive restatement or forensic filing recorded at $\tau_0 > T_{\text{tx}}$ (even with backdated $v_0 \le T_{\text{valid}}$) satisfies $\tau_0 \le T_{\text{tx}} = \text{False}$ and is mathematically excluded from $\mathcal{S}(G; T_{\text{valid}}, T_{\text{tx}})$, guaranteeing zero point-in-time lookahead leakage.

2.2 Dangling-Mass Conserving Personalized PageRank (csrc/privora_kernels.cpp)

Let $P$ denote the row-normalized active transition matrix and $\mathcal{D} = {u : \sum_v w_{u,v} = 0}$ the set of sink/dangling nodes. Defining the stochastic operator:

\[\pi^{(k+1)} = (1 - \beta)\!\left(P^\top \pi^{(k)} + \Big(\sum_{u \in \mathcal{D}} \pi_u^{(k)}\Big) s\right) + \beta s, \qquad \beta \in (0, 1), \quad \sum_i s_i = 1\]
  1. Exact Probability Simplex Conservation: Summing coordinates yields $\mathbf{1}^\top \pi^{(k+1)} = (1-\beta)(1 - d_k + d_k) + \beta = 1$ at every iteration (verified via Hypothesis to < 1e-8).
  2. Contraction Mapping: Because $| \mathcal{T}(x) - \mathcal{T}(y) |_1 \le (1 - \beta) | x - y |_1$, Banach’s Fixed-Point Theorem guarantees unique geometric convergence at rate $(1 - \beta)^k$.

3. Byzantine-Resilient Aggregation (robust_fed.py)

Given $K$ federated silos containing $f < K / 2$ arbitrary Byzantine adversaries: