arXiv CSopen access

CHRONOS: Temporally-Aware Multi-Agent Coordination for Evolving Data Marketplaces

CHRONOS: Temporally-Aware Multi-Agent Coordination for Evolving Data Marketplaces Joydeep Chandra

BNRIST, Tsinghua University Beijing, China

arXiv:2605.23887v1 [cs.DB] 22 May 2026

ABSTRACT Temporal knowledge-graph (KG) data marketplaces face three coupled failures in static designs: stale hybrid index shortcuts reduce recall as edges evolve, stationary Shapley pricing misattributes value after distribution shifts, and uncoordinated agents over-consume a shared differential-privacy (DP) budget. We present CHRONOS, a trusted-curator, three-layer architecture that provides a unified treatment of these challenges with explicit public/private separation. Layer 1 (T-LEGEND) applies neural-ODE temporal decay to shortcut edges and provides a per-query expected recall-loss bound of O (𝑃𝑞 𝜆Δ𝑡), with a tighter ODE-certified monotone-envelope guarantee reducing bound looseness to 1.8–3.2× observed loss (Theorem 1). We also provide analysis under Hawkes dynamics (Theorem 2). Layer 2 (Event-Conditioned MPV) conditions Shapley valuation on BOCPD-detected changepoints and provides finite-sample error guarantees under coalition sampling and DP noise. Layer 3 (Temporal Coordinator) uses EXP3-IX over three scheduling actions, √ achieving O ( 𝑇 log𝑇 ) regret while enforcing (𝜖total, 𝛿 total )-DP via moments accounting. CHRONOS releases a fixed-dimension privatised affinity matrix once per active epoch with the Gaussian mechanism; all per-query retrieval and top-𝑘 ranking are postprocessing, so they incur no extra privacy cost. We also provide a multi-epoch coalition-level settlement mechanism for actionable seller payouts, scalability analysis up to 500 sellers, and comparison against VSAG-style accelerated baselines. Across four benchmarks, CHRONOS shows 0.937 recall@10, 2.74 queries/s, P50 latency 161 ms, and total 𝜖 = 4.25 at 𝛿 = 10−6 under standard zCDP composition over 𝜌. These results indicate a competitive joint recall/latency/privacy operating point. A key limitation is that at this privacy level, externally-released valuations and affinity scores remain noise-dominated; utility derives primarily from public index routing and adaptive scheduling driven by low-sensitivity DP statistics. PVLDB Reference Format: Joydeep Chandra. CHRONOS: Temporally-Aware Multi-Agent Coordination for Evolving Data Marketplaces. PVLDB, 14(1): XXX-XXX, 2020. doi:XX.XX/XXX.XX PVLDB Artifact Availability:

The source code, data, and/or other artifacts have been made available at URL_TO_YOUR_ARTIFACTS.

1

1.1 This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this license. For any use beyond those covered by this license, obtain permission by emailing [email protected]. Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment. Proceedings of the VLDB Endowment, Vol. 14, No. 1 ISSN 2150-8097. doi:XX.XX/XXX.XX

INTRODUCTION

Consider a pharmaceutical company querying a temporal KG marketplace for drug-gene interaction data. The KG evolves daily as new clinical-trial results add edges, retracted findings delete them, and regulatory approvals change entity attributes. The buyer needs recent, high-quality data for a machine-learning model and expects fair compensation to be distributed among contributing data sellers. Three intertwined challenges arise immediately. The indexing challenge. Hybrid vector-graph indices such as HNSW [45] accelerate 𝑘-NN queries via shortcut edges built at construction time. When the underlying KG evolves, these shortcuts become stale, silently degrading recall. Existing systems either ignore staleness (TigerVector [43], NaviX [59]) or trigger expensive full rebuilds; dynamic ANN systems (FreshDiskANN [61], SPFresh [69], Quake [49]) handle vector updates but do not model graph-structural staleness or provide recall bounds tied to KG evolution rates. The valuation challenge. Fair attribution of query utility to data sellers requires Shapley axioms [60], yet the canonical Data Shapley [28] assumes a stationary characteristic function. After a disease outbreak or regulatory change, marginal dataset values shift sharply; static valuations then distort marketplace incentives. Beta Shapley [39] improves robustness to noisy data, Variance-Reduced Data Shapley (VRDS) [65] lowers coalition-sampling variance, and GLOC-style online updates [31] provide gradient-based valuations without full recomputation, but none of these methods models event-driven distributional shifts. The coordination challenge. A production marketplace runs concurrent agents sharing a finite DP budget. Without coordination, simultaneous demands exhaust it prematurely. Existing multi-agent frameworks [44] provide no formal coupling between scheduling and DP consumption, and privacy filters [58] track composition but do not integrate with index scheduling or data valuation. PSGraph [72] demonstrates adaptive DP allocation for streaming graphs, but targets graph synthesis rather than marketplace coordination.

Why These Challenges Must Be Solved Jointly

The three challenges are coupled through a shared differentialprivacy budget. Index updates, valuation recomputation, and idle waiting all consume from the same finite (𝜀, 𝛿) allowance. An indexonly system would exhaust the budget on frequent rebuilds, leaving none for valuation. A valuation-only system would trigger

recompute after every changepoint, starving index maintenance. An uncoordinated system would face simultaneous demands from concurrent agents and exhaust the budget prematurely. Because the sensitivity of each mechanism depends on the number of sellers 𝑛, the per-epoch privacy cost falls as 𝑛 grows, but the total number of active epochs 𝑇active rises with marketplace activity. The coordinator must therefore balance these competing demands, making the joint design non-decomposable.

1.2

𝜀=4.25 (Remark 6); transparent analysis of private-signal informativeness (§6); per-entry noise calibration with dimensionaware sensitivity (Proposition 1). (5) Actionable Seller Settlement (§6.3): a concrete multi-epoch coalition-level settlement mechanism with SNR analysis showing trend-level attribution becomes feasible at 𝑊 ≥7 epochs and 𝑛 coal ≤5. (6) Comprehensive evaluation (§7): four datasets; VSAG-accelerated throughput comparison (Table 8); scalability to 500 sellers (Table 13); head-to-head DP retrieval comparison at matched 𝜀 (Table 12); DP-vs-crypto cost analysis (Table 14); seller-skew stress tests; three drift detectors; five coordination strategies.

Gap Analysis

Prior works address at most one challenge in isolation. In indexing, TigerVector [43], NaviX [59], and ACORN [57] integrate graph structure into HNSW but assume static graphs. FreshDiskANN [61] and SPFresh [69] support streaming updates yet omit KG structural decay and recall bounds. In valuation, Data Shapley [28], Beta Shapley [39], and VRDS [65] improve estimation but do not condition on distributional shifts. In marketplace design, existing platforms [6, 26, 38, 42] support pricing and DP guarantees yet do not target temporal graph retrieval. Dealer [42] provides an endto-end DP model marketplace, but assumes static data and does not couple indexing with valuation under a shared privacy budget. Agora [38] focuses on access control and auditability rather than temporal query performance. Cryptographic alternatives such as MPC or TEEs can eliminate DP noise, yet they introduce 10–100× latency overhead and require all parties to participate in real-time protocols [18, 41]; we compare these costs in Table 14. No existing system couples index freshness with valuation correctness within a differentially private multi-agent framework for temporal knowledge graphs.

1.3

2

PRELIMINARIES

Definition 1 (Temporal Knowledge Graph). A temporal KG is a triple G(𝑡) = (𝑉 (𝑡), 𝐸 (𝑡), X(𝑡)) where 𝑉 (𝑡) and 𝐸 (𝑡) are node and edge sets at time 𝑡, X(𝑡) ∈ R |𝑉 (𝑡 ) | ×𝑑 is the node feature matrix, and each edge 𝑒 = (𝑢, 𝑣, 𝑟 ) ∈ 𝐸 (𝑡) carries relation type 𝑟 and creation timestamp 𝑡𝑒 ≤ 𝑡. Definition 2 (Temporally-Aware Data Marketplace). A marketplace M with 𝑛 sellers {𝑠 1, . . . , 𝑠𝑛 } holding private datasets 𝐷𝑖 ⊆ G(𝑡) must satisfy, for online buyer queries with vector v 𝑗 , recency window [𝑡 𝑗min, 𝑡 𝑗max ], and budget 𝜀 𝑗 : (P1) recall@𝑘 ≥ 𝑅 ∗ −𝛿 index ; (P2) Shapley efficiency with temporal consistency; (P3) (𝜀 total, 𝛿 total )DP; (P4) sub-linear regret 𝑅𝑇 = 𝑜 (𝑇 ) with per-query latency ≤ 𝐿max . Scope. Chronos targets embedding-rich temporal KG marketplaces with a substantial public ontology prior to seller participation. Guarantees are strongest in the embedding-dominated regime (𝛽 ≤ 0.5), where <6% of oracle top-10 items fall outside the public candidate set (Table 16); for high-𝛽 (𝛽 > 0.7), miss rates reach 12–14% (Table 16), with corresponding behaviour discussed in the robustness analysis. Key notation is summarised in Table 1. We adopt the Poisson edge-change model as the baseline (Assumption 1), with formal Hawkes extensions in Theorem 4.

Contributions

We present Chronos, a marketplace infrastructure that provides end-to-end temporal guarantees across indexing, valuation, and coordination:

Assumption 1 (Poisson Edge Changes). KG edge changes arrive as an independent Poisson process with rate 𝜆 > 0 (changes per day per shortcut). We estimate 𝜆 via exponential moving average over a 30day calibration window: 𝜆=0.05 for FB15K-237/WN18RR (synthetic), 𝜆≈12 for MIMIC-IV (real admissions), 𝜆≈2.9 for Yelp (real review activity).

(1) T-Legend (§4.1): a temporal hybrid index with neural-ODE decay weights. The conservative bound (Theorem 2) provides an O (𝑃𝑞 𝜆Δ𝑡) recall-loss guarantee; the new monotone-envelope certificate (Theorem 3) tightens the gap to 1.8–3.2× observed losses by incorporating ODE Lipschitz structure. Formal Hawkesprocess recall bounds (Theorem 4) extend guarantees beyond Poisson to correlated dynamics parameterised by branching ratio. (2) Event-Conditioned MPV (§4.2): Shapley valuation conditioned on BOCPD-detected changepoints with drift-aware validity horizons, a temporal efficiency identity (Theorem 6), and estimation error bounds under finite sampling, DP noise, and changepoint uncertainty (Theorem 7). (3) Temporal √ Coordinator (§4.3): an EXP3-IX meta-agent achieving O ( 𝑇 log𝑇 ) regret (Theorem 10) while enforcing adaptive DP composition with formal sensitivity proofs (Proposition 8). (4) Fixed-Dimension DP Pipeline with Standard Accounting (§3, §4.4): explicit public/private separation; epoch-level Gaussian privatisation of a fixed-dimension affinity matrix (Proposition 8(b)); standard additive zCDP composition over 𝜌 yielding

Noise notation convention. 𝜎𝑡 is a dimensionless noise multiplier; actual Gaussian std for a quantity with ℓ2 -sensitivity 𝑆 is 𝜎𝑡 × 𝑆. The per-step Rényi moment is 𝜇𝑡 (𝛼) = 𝛼/(2𝜎𝑡2 ) (Proposition 1). The total 𝜀=4.25 (𝛿=10−6 ) is computed by standard additive zCDP composition over 𝜌: ∑︁ √︁ 𝜌 total = 𝜌𝑖 , 𝜀 = 𝜌 total + 2 𝜌 total · ln(1/𝛿). (1) 𝑖

3

TRUST MODEL AND PUBLIC/PRIVATE SEPARATION

A rigorous DP design requires a precise delineation of what is public and what is private. CHRONOS operates under a trustedcurator model [24]: the marketplace operator holds raw seller data 2

Table 1: Key notation. Symbol

Meaning

G (𝑡 ), 𝜆, Δ𝑡 ¯ 𝑅 ∗ , 𝑃𝑞 , Δ𝑟 𝑅ˆ (𝑡 ) A(𝑡 ) e ) A(𝑡 MPV𝑖 (𝑡, 𝐸 ) 𝐵 𝜎𝑡 𝑇active 𝜀 rem (𝑡 ), 𝜇𝑡 (𝛼 ) p𝑡 , 𝑑=3, 𝛾 𝛾 comm 𝛼 𝐻 , 𝛽𝐻 Λ(𝑡 1 , 𝑡 2 )

Temporal KG, edge-change rate, time since update Fresh recall, search-path size, per-shortcut impact DP-estimated noisy recall (observed proxy for 𝑅 ∗ ) Private affinity matrix ∈ [0, 1] |𝑉active |×𝑒 𝑓 Gaussian-noised release of A(𝑡 ) EC-MPV of seller 𝑖 at time 𝑡 , event 𝐸 Marginal contribution bound (clipped at 0.2) Noise multiplier (dimensionless); actual std = 𝜎𝑡 × 𝑆 Number of epochs with ≥ 1 DP release Remaining DP budget, Rényi moment at step 𝑡 EXP3-IX distribution, action count, exploration Community-structure weight in static affinity (default 0.5) Hawkes excitation/decay parameters ∫𝑡 Cumulative intensity 𝑡 2 𝜆 (𝑠 ) 𝑑𝑠 1

and publishes only DP-sanitised outputs. We partition all system components explicitly. Public data (not seller-dependent, zero DP cost). (1) Entity embeddings X0 ∈ R |𝑉0 | ×𝑑 : pre-trained on historical KG snapshots from months 1–6 (the “pre-marketplace” period) before any seller participation begins, and frozen at deployment. No seller-contributed edges from the operational period are used in embedding training. (2) HNSW index structure H𝑇 : built deterministically from X0 and the Louvain community partition [10] of the public pre-marketplace KG. The neighbourhood lists 𝑁 idx (𝑢) = {𝑢 1, . . . , 𝑢𝑒 𝑓 } are fixed at construction time and are deterministic functions of X0 . After construction, H𝑇 is frozen within each epoch. (3) Edge creation timestamps from public pre-marketplace KG: timestamps 𝑡𝑒 for edges in 𝐸 pub (months 1–6) are public metadata. Post-launch seller-edge timestamps are private and never enter Stage-2 clipping directly (see below). (4) Buyer query vectors v𝑞 : owned by the buyer, not seller data. Private data (seller-dependent, protected by DP). (1) Seller KG edges: edges contributed by sellers after marketplace priv launch, including their timestamps 𝑡𝑒 . These determine the temporal affinity values aff KG (𝑢, 𝑣, 𝑡) and are the primary target of DP protection. (2) Valuation scores MPV𝑖 (𝑡, 𝐸): depend on seller coalitions. (3) Index staleness statistics: depend on which seller-contributed edges have changed. Public/private timestamp delineation. Edge creation timestamps for the pre-marketplace KG (months 1–6) are public. Sellercontributed edge timestamps (months 7+) are private. The Stage-2 active-scope clipping (§4.4) operates as follows. The set of active entities 𝑉active (𝑡) is determined by buyer queries from epoch 𝑡−1 plus a popularity reserve, both computed from public query logs. The universe of possible edges within 𝑉active is public: it is the set of all tuples (𝑢, 𝑣, 𝑟 ) with 𝑢, 𝑣 ∈ 𝑉active and 𝑟 ∈ R, where R is the public relation-type ontology. A seller’s private data is the subset of this universe that they actually contributed. The priority rule for retaining seller edges uses a public hash hash(𝑢, 𝑣, 𝑟 ) computed over the full public universe. The mechanism retains, for 3

each seller, the intersection of their private edge set with the first priv 𝜅 active tuples in this public ordering. Private timestamps 𝑡𝑒 are used only inside the Gaussian mechanism’s input (to compute priv aff KG (𝑢, 𝑣, 𝑡) = decay(𝑡 now − 𝑡𝑒 ) · aff static (𝑢, 𝑣)), never for clipping or scoping decisions. The clipping boundary 𝜅 active depends only on |𝐸|/𝑛 (public) and |𝑉active | (public). Why clipping does not leak edge existence. The clipping step is sensitivity bounding, not a privacy mechanism. The actual privacy guarantee comes from the Gaussian mechanism (§4.4) ape plied to the affinity matrix after clipping. The released matrix A(𝑡) has public row and column indices; each entry contains additive Gaussian noise with standard deviation 𝜎entry =885. Because the noise magnitude far exceeds the [0, 1] signal range, an adversary e cannot reliably infer whether a particular entry’s observing A(𝑡) true value is zero (edge absent) or non-zero (edge present). Formally, for any entry 𝑎 ∈ [0, 1] and any hypothesised value 𝑎 ′ ∈ [0, 1], the likelihood ratio of the observed noisy value under 𝑎 versus 𝑎 ′ is bounded by exp(𝜀 entry ) with 𝜀 entry ≈0.0011 per entry, which is dominated by the overall zCDP accounting. Thus the hash-based clipping rule does not circumvent the DP guarantee. DP guarantee scope. Seller-level adjacency protects all private data; public components incur zero DP cost. Each edge (𝑢, 𝑣, 𝑟 ) has a unique owner under a hash-based deduplication registry, ensuring unambiguous sensitivity accounting. For multi-relation graphs, (𝑟 ) aff KG (𝑢, 𝑣, 𝑡)= max𝑟 aff KG means removing one seller changes the max by ≤ 1 per (𝑢, 𝑣) pair. Pre-registry empirical overlap 𝜂 raw ≤1.07 across all datasets confirms near-exclusive ownership (supplementary Table B2). If disputed ownership persists, privacy cost scales approximately with 𝜂 2 (Remark 3), and arbitration/registry enforcement is required before deployment. DP-SGD training [1] of embeddings is feasible at additional 𝜀 train cost (supplementary Appendix C). Limitation: single trusted curator and fixed public structure. The trusted-curator model requires one operator to hold all raw seller data, narrowing applicability in multi-platform settings. Two concrete extensions relax this: (i) two-server model: one server holds private seller edges; the second holds the public index; neither observes the full affinity matrix. The fixed-dimension epoch-level release is compatible with additive secret sharing over the two parties. (ii) Local DP: each seller randomises their own edges locally before upload, removing the central curator at the cost of Ω(1/𝜀 2 ) more data for the same utility. We identify the two-server extension as the primary trust-relaxation path; protocol details are provided, while implementation and small-scale validation are left to future work. Limitation: query privacy. Chronos treats buyer queries v𝑞 as public (standard in trusted-curator DP). If queries are sensitive, the continual-observation framework [13, 23] with a count-min sketch can privately estimate 𝑉active at 𝜀 query ≈0.5/36 h. Realism of fixed public structure. The trusted-curator design targets embedding-rich marketplaces (pharmaceutical, clinical, product-graph) where seller edges enrich affinity weights on a structurally stable public graph. At 𝛽=0.3, <6% of oracle top-10 items fall outside the public candidate set (Table 16). When miss rates are unacceptable (high-𝛽), the SVT prototype recovers 52% of misses

Algorithm 1 T-LEGEND-BUILD (Public-Only Construction) Require: Public KG Gpub (𝑡 ) (pre-marketplace), ODE model 𝑓𝜃 , params (𝑀, 𝑒 𝑓𝑐 , 𝑚𝐿 ) Ensure: T-LEGEND index H𝑇 with fixed neighbourhoods 𝑁 idx (𝑢 ) 1: C ← LOUVAIN( Gpub (𝑡 ) ) ⊲ public community structure 2: for (𝑢, 𝑣, 𝑡𝑒 ) ∈ 𝐸 pub (𝑡 ) do ⊲ public edges only 𝑤𝑢𝑣 ← decay(𝑡 now −𝑡𝑒 ) · aff static (𝑢, 𝑣) 3: end for 4: for each 𝑣 ∈ 𝑉 (community-sorted) do 5: Draw ℓ𝑣 ∼ Geom(1−1/𝑚𝐿 ); bias up for hubs 6: for ℓ = ℓ𝑣 downto 0 do 7: 𝑊 ← SEARCH-LAYER(H𝑇 , e𝑣 , ℓ, 𝑒 𝑓𝑐 ) 8: for 𝑢 ∈ 𝑊 do 𝑠𝑇 (𝑢 ) ← (1−𝛽 ) sim(e𝑣 , e𝑢 ) + 𝛽 𝑤𝑢𝑣 ⊲ public weights only 9: end for 10: 𝑁 ∗ (𝑣, ℓ ) ← TOP-𝑀-DIVERSE(𝑊 , 𝑠𝑇 , 𝜌 div ) 11: Add { (𝑣, 𝑢 ) : 𝑢 ∈ 𝑁 ∗ (𝑣, ℓ ) } to layer ℓ 12: end for Ð 13: Record 𝑁 idx (𝑣) ← ℓ 𝑁 ∗ (𝑣, ℓ ) ⊲ fixed, public 14: end for

Figure 1: Public/private data flow under the trusted-curator model. Public components (yellow) construct the frozen index and cosine routing at zero DP cost; private seller edges (blue) enter only through the four-stage Gaussian pipeline, e for hybrid scoring. producing A(𝑡) at +0.05 𝜀. Figure 1 summarises this public/private separation and the resulting trusted-curator data path.

We train 𝑓𝜃 on historical KG snapshots using contrastive temporal loss:

4

LODE = −

THE CHRONOS ARCHITECTURE

Chronos comprises three tightly coupled layers (Figure 2). Buyer queries arrive at a Query Gateway and are forwarded to Layer 1 for retrieval while being logged to an event stream monitored by Layer 3. Layer 2 conditions valuations on changepoints inferred from that stream. Layer 3 schedules all operations while enforcing the shared DP budget. Table 2 summarises the time and space complexity of each CHRONOS operation. Index construction is a one-time offline cost on public data; incremental updates repair only stale shortcuts within 𝑉active . Query processing is constant in dataset size because HNSW search is 𝑂 (log 𝑁 ) and the per-query hybrid score is postprocessing. The dominant online cost is valuation recomputation (𝑂 (𝑚𝑛 2 |𝑄 |)), which is why EC-MPV batches it at changepoints rather than every epoch. The DP release cost is linear in the activescope size and is amortised over all queries in the epoch.

4.1

(𝑒,Δ𝑡 ) ∈ P +

T-Legend employs a neural-ODE temporal decay that continuously down-weights shortcut edges linking stale KG structure, enabling the index to degrade gracefully rather than failing silently. Definition 3 (Neural ODE Temporal Decay). For edge 𝑒 with age Δ𝑡 = 𝑡 now − 𝑡𝑒 , the decay function decay : R ≥0 → (0, 1] is the first component of the ODE solution: h(0) = 132,

log decay(Δ𝑡) −

∑︁

log(1−decay(Δ𝑡)),

(𝑒,Δ𝑡 ) ∈ P −

(3) with 3:1 negative sampling, strict temporal splitting (months 1–6 train, 7–8 val, 9–12 test), Adam optimiser (lr=10−3 ), and Dormand– Prince solver [20]. Training converges in ∼50 epochs (∼20 min on one A100). Neural-ODE diagnostics. Domain-specific decay shapes, solvertolerance robustness, hidden-size ablations (ℎ∈{16, 32, 64}; ℎ=32 optimal), and generalisation to unseen rates (𝜆=25) are in supplementary Appendix F. The temporal affinity between nodes is aff KG (𝑣, 𝑢, 𝑡) = decay(𝑡 − 𝑡𝑒 ) · aff static (𝑣, 𝑢) where the static component uses communitystructure proximity [10] (𝛾 comm =0.5). Index construction and public/private separation. Algorithm 1 uses only public pre-marketplace data (months 1–6): 𝑁 idx (𝑢) is a deterministic function of public data only, ensuring sellerdependent affinities enter only at query time via the private A(𝑡) matrix (§4.4). Algorithm 1 inserts nodes in community-sorted order using hybrid score 𝑠𝑇 with a diversified-neighbor selection heuristic; parameters 𝑀=16, 𝑒 𝑓𝑐 =200, 𝑒 𝑓 =128, 𝜌 div =0.7 are identical for all baselines (Table 7). Stale-shortcut detection triggers incremental updates when < 40% of shortcuts are stale (restoring ≥ 95% fresh recall at ≤ 20% cost), with full rebuilds at higher staleness rates.

Layer 1: T-LEGEND (Temporal Hybrid Index)

𝑑h = 𝑓𝜃 (h(Δ𝑡), Δ𝑡), 𝑑Δ𝑡

∑︁

Remark 1 (Role of Temporal Decay vs. Private Edges). The ODE decay applies to public shortcut edges; private seller edges never e release. The enter 𝑁 idx (𝑢) and influence only the epoch-level A(𝑡) e ODE keeps the candidate set fresh; A(𝑡) keeps ranking within that set fresh.

decay(Δ𝑡) = 𝜎 ([h(Δ𝑡)] 1 ),

(2) where 𝑓𝜃 : R32 ×R → R32 is a two-hidden-layer MLP with Softplus activations [14] and 𝜎 is the sigmoid. 4

Table 2: Per-operation complexity. 𝑁 =|𝑉 |, 𝑀=16, 𝑒 𝑓 =128, 𝐿max =5, 𝑛=#sellers, 𝑚=#permutations, 𝑇 =horizon, |𝑉active |≤1500. Operation Index construction Incremental update Query processing Valuation recompute DP release (affinity) DP release (stats) Coordinator decision

Time

Space

Frequency

𝑂 (𝑁 log 𝑁 · 𝑀 ) 𝑂 ( |𝑉active | log 𝑁 ) 𝑂 (𝑒 𝑓 · 𝐿max ) 𝑂 (𝑚 · 𝑛 2 · |𝑄 | ) 𝑂 ( |𝑉active | · 𝑒 𝑓 ) 𝑂 (1) 𝑂 (𝑑 )

𝑂 (𝑁 · 𝑀 ) 𝑂 ( |𝑉active | ) 𝑂 (𝑒 𝑓 ) 𝑂 (𝑛) 𝑂 ( |𝑉active | · 𝑒 𝑓 ) 𝑂 (1) 𝑂 (𝑑 )

Once Per epoch Per query Per event Per active epoch Per active epoch Per epoch

Comments Public data only Stale-shortcut repair Post-processing, zero DP cost VRDS reduces variance Gaussian sampling dominates Scalar Gaussian EXP3-IX update

Figure 2: Chronos architecture.

4.2

Layer 2: Event-Conditioned MPV

Real-world events alter dataset marginal values in ways that static Shapley misses [28]. EC-MPV addresses this by conditioning on detected distributional changepoints. Definition 4 (Temporal KG Affinity). The temporal affinity aff KG (𝑢, 𝑣, 𝑡) = decay(𝑡 − 𝑡𝑒 ) · aff static (𝑢, 𝑣) where 𝑡𝑒 is the creation timestamp and aff static (𝑢, 𝑣) ∈ [0, 1] is Louvain community-structure proximity [10]. For multi-relation graphs, we take the maximum over relation types. Definition 5 (Event-Conditioned MPV). Let 𝐸 be an event detected at time 𝑡 by BOCPD. The EC-MPV of seller 𝑖 is MPV𝑖 (𝑡, 𝐸) = Ð 𝜙𝑖 (𝐷 priv ∪𝐷 pub | 𝐸, 𝑡)−𝜙 (𝐷 pub | 𝐸, 𝑡) where 𝑣 (𝑆; 𝐸) = MRR(𝑞, 𝑗 ∈𝑆 𝐷 𝑗 , 𝐸) is conditioned on event 𝐸. 5

The marginal contribution bound 𝐵 in Assumption 3 is enforced by clipping to [−𝐵, 𝐵] with 𝐵=0.2 (<0.3% of marginals exceed 0.2 before clipping). ˆ The BOCPD module [2] monitors query-embedding drift, 𝜆(𝑡), and valuation residuals via a Normal-Inverse-Wishart conjugate prior with geometric hazard 𝜋 cp =1/250. Changepoints are declared at 𝑃 (𝑟𝑡 =0 | o1:𝑡 ) > 0.85; median detection delay 2.3 epochs (P95: 5.1) on 8 injected Yelp seasonal events. For Shapley estimation we use permutation sampling [12] (𝑚=1,000) with VRDS control variates [65]: leave-one-out baselines reduce variance to ≤ 𝐵 2 𝜌 2 /𝑚, giving 1.8× reduction on Yelp at zero DP cost.

4.3

e [𝑣𝑞 , 𝑗] is also post-processing, so top-𝑘 selection incurs zero 𝛽 A(𝑡) additional DP cost [24].

Layer 3: Temporal Coordinator Agent

The coordinator operates as a partially observable stochastic game Γ with state s𝑡 = (𝜆ˆ𝑡 , 𝑅ˆ𝑡 , 𝜀 rem (𝑡), 𝑛 pending (𝑡), 𝐸 active ), action space A = {INDEX-UPDATE, REVALUE, NULL} (𝑑=3), and reward 𝑅(s, a) = QPS + 𝜇𝑅 𝑅ˆ − 𝜈 𝜀 consumed with 𝜇𝑅 =10, 𝜈=5 (grid-searched on FB15K237 validation; sensitivity analysis in §7.4), normalised to [0, 1]. Rather than solving this PSPACE-hard problem exactly [55], the coordinator applies EXP3-IX [51] under bandit feedback. Each 60 s epoch: observe noisy state o𝑡 ; sample a𝑡 ∼ p𝑡 ; observe 𝑟𝑡 ; update via importance-weighted loss 𝐿ˆ𝑡,𝑗 = (1−𝑟𝑡 ) 1 [a𝑡 =𝑗]/(𝑝𝑡,𝑗 + 𝛾). Budget-violating actions are overridden to NULL; recall violations to INDEX-UPDATE (override count bounded; Lemma 9). Remaining Í budget: 𝜀 rem (𝑡) = min𝛼 [(𝜀 total − 𝑠 ≤𝑡 𝜇𝑠 (𝛼) + 𝛼 ln(1/𝛿 total ))/𝛼].

4.4

4.4.1

Per-Entry Noise Calibration.

Proposition 1 (Per-Entry Gaussian Noise Calibration). Let A ∈ R𝑛𝑟 ×𝑛𝑐 have Frobenius (ℓ2 ) sensitivity Δ2 = max𝐷∼𝐷 ′ ∥A(𝐷) − 2 e = A+Z with 𝑍𝑖,𝑗 iid A(𝐷 ′ )∥ 𝐹 . The Gaussian mechanism A ∼ N (0, 𝜎entry ) 2 satisfies (𝛼, 𝛼Δ22 /(2𝜎entry ))-RDP by the standard vector Gaussian mechanism [48]. Setting 𝜎entry = 𝜎𝑡 · Δ2 (noise multiplier 𝜎𝑡 = 𝜎entry /Δ2 ) yields:

𝜇𝑡 (𝛼) =

𝛼Δ22

2 2𝜎entry

=

𝛼Δ22

2𝜎𝑡2 Δ22

=

𝛼 . 2𝜎𝑡2

(4)

2 The standard RDP formula uses per-coordinate variance 𝜎entry ; using 2 2 a global variance 𝜎global = 𝑛𝑟 𝑛𝑐 · 𝜎entry in the denominator would underestimate 𝜀 by a factor of 𝑚 = 𝑛𝑟 𝑛𝑐 .

Fixed-Dimension DP Pipeline

The DP model is the linchpin of CHRONOS and requires careful treatment. We adopt seller-level adjacency: two states are adjacent if they differ by one seller’s entire dataset 𝐷𝑖 . To bound sensitivity edge robustly, we enforce per-seller contribution caps 𝐶 max = ⌈1.5|𝐸|/𝑛⌉; excess edges are clipped. Three categories of seller-dependent outputs are privatised, with sensitivity bounds proven in Proposition 8: (i) Valuation scores. Each MPV𝑖 (𝑡, 𝐸) is released via 𝑛 independent per-coordinate Gaussian mechanisms with sensitivity 𝑆 val =4𝐵/𝑛=0.08 (𝐵=0.2, 𝑛=10; Proposition 8(a)). With 𝜎𝑡 =50, actual noise std is 50×0.08=4.0 per coordinate. The 𝜌 val =287/5000=0.0574 contributes to the total zCDP 𝜌.

Proof. Direct substitution into Mironov [48] Proposition 3; see supplementary Appendix A. □ Per-epoch active-scope sensitivity. Before each Gaussian invocation, two deterministic clips apply. Stage 1: seller edge count edge clipped to 𝐶 max =⌈1.5|𝐸|/𝑛⌉ globally. Stage 2: within 𝑉active (𝑡), a seller’s edges are retained by a publicly computable, data-independent priority rule: hash(𝑢, 𝑣, 𝑟 ) ordering (public edge metadata only, independent of private affinity values, timestamps, or seller identity). edge Edges beyond 𝜅 active (𝑡)= min(𝐶 max , ⌈1.5|𝐸 active (𝑡)|/𝑛⌉) are dropped. √ Under this rule, the post-clip matrices satisfy ∥A(𝐷)−A(𝐷 ′ ) ∥ 𝐹 ≤ 𝜅 active √ ′ for any adjacent 𝐷∼𝐷 , giving worst-case Δ2 = 𝜅 active . On Yelp this reduces Δ2 by 30.1× (545→18.1).

Remark 2 (Valuation DP: External Release vs. Internal Coordinator Use). The noise std of 4.0 far exceeds the signal range [0, 𝐵=0.2] by 20×, making externally-released valuations noise-dominated. This reflects the utility-privacy trade-off of DP in high-sensitivity regimes. The Val. Err=0.013 in Table 19 measures internal Shapley estimation accuracy before DP noise. Under the trusted-curator model, the coordinator uses pre-noise estimates for scheduling. The DP mechanism releases noisy valuations to external parties solely for auditability and non-disclosure guarantees, not for accurate point estimation. For actionable seller payouts, we introduce a concrete multi-epoch coalition-level settlement mechanism in §6.3.

4.4.2 Release Policy and Active/Null Epoch Classification. An active epoch is one where the coordinator chose INDEX-UPDATE or e is released once via the REVALUE, or ≥1 buyer query arrived; A(𝑡) Gaussian mechanism. A null epoch incurs zero DP cost. Budget breakdown via parallel zCDP composition: 𝜌 idx =0.0846, 𝜌 val =0.0574, 𝜌 aff =0.142; total 𝜌 total =0.284, yielding (using Eq. (1)): √︁ √ 𝜀 = 0.284 + 2 0.284 × ln(106 ) = 0.284 + 2 0.284 × 13.816 = 4.25. (5)

(ii) Index statistics. The stale-shortcut fraction and recall estiRemark 4 (Within-Epoch Serving Timeline and P50 Latency). mate 𝑅ˆ are released with Gaussian noise calibrated to sensitivity 𝑉active (𝑡) is the look-back set (entities queried in epoch 𝑡−1 plus 500𝑆 idx ≤ 1.5/𝑛 with 𝜎𝑡 =50. e (iii) KG affinity matrix (fixed dimension). We release A(𝑡) [𝑢, 𝑗] = entity popularity reserve, zero DP cost); A(𝑡) releases in 18.4 ms off the query critical path. Per-query lookup is 0.3 ms post-processing; in aff KG (𝑢, 𝑁 idx (𝑢) [ 𝑗], 𝑡) for 𝑢 ∈ 𝑉active , 𝑗=1, . . . , 𝑒 𝑓 . Row and column the serving-path trace P50 = 158 ms (no privatisation overhead), while indices are public and fixed by the public√︃index H𝑇 . Under exclusive the end-to-end benchmark reports 161 ms (Table 11). edge ownership, Frobenius sensitivity Δ2 = 𝐶 max (Proposition 8(b)). Remark 5 (Epoch Classification is Post-Processing). The Remark 3 (Robustness to Imperfect Exclusive Ownership). coordinator’s decision rule 𝜋𝑡 operates only on DP-released quantities √︃ edge from prior epochs; by the post-processing theorem [24], active/null Let 𝜂 ≥ 1 be the overlap factor. Sensitivity scales to Δ2 ≤ 𝜂 𝐶 max , 2 classification incurs zero additional privacy cost. 𝑇active is a stopping raising 𝜀 by 𝜂 : 𝜂=1.2 adds ≤ 44%; the registry enforces 𝜂=1 detertime; the privacy odometer framework [58] accounts for the realised ministically; empirically 𝜂 raw ≤ 1.07. active-epoch sequence only. Worst-case (𝑇 =2,160 all-active): 𝜀≈8.47 e = A(𝑡) + Z via the Gaussian mechanism (PropoWe release A(𝑡) via zCDP, confirming adaptive stopping does not amplify risk unsition 1); entries are clipped to [0, 1] post-noise (post-processing, boundedly. zero DP cost). Per-query hybrid scoring 𝑠˜𝑗 = (1−𝛽) cos(v𝑞 , e𝑢 𝑗 ) + 6

Table 4: Per-query recall bound instantiation at Δ𝑡=7 days. “Tight” refers to the monotone-envelope bound (Theorem 3).

Table 3: Per-mechanism noise parameters. 𝜎𝑡 =50 uniformly. Rényi moment: 𝜇𝑡RDP (𝛼) = 𝛼/(2𝜎𝑡2 ) = 𝛼/5000. zCDP uses additive composition over 𝜌: sum 𝜌𝑖 = 𝑇𝑖 /(2×502 ) first, then convert via Eq. (1).

Dataset

Mechanism

Active epochs

S

𝝈𝒕

Actual std

𝝁 𝒕RDP (𝜶 =18)

𝝆𝒊

Index stats Valuation KG affinity

423 287 710

0.015 0.080 †

50 50 50

0.750 4.000 885‡

3.60×10 −3 3.60×10 −3 3.60×10−3

0.0846 0.0574 0.142

𝜌 total =

0.284

Total √ Total (𝜀, 𝛿 )-DP: 𝜀 = 0.284 + 2 0.284 × 13.816 = 4.25

FB15K-237 WN18RR MIMIC-IV Yelp

𝑃𝑞 1408 1792 2176 2240

¯ max Δ𝑟 5.1×10−4

3.8×10 −4 4.3×10 −4 3.9×10 −4

𝜆

Conserv.

Tight

Obs.

Ratio

0.05 0.05 12.0 2.9

0.251 0.238 0.936 0.874

0.044 0.035 0.170 0.128

0.014 0.011 0.094 0.050

3.1× 3.2× 1.8× 2.6×

Ratio = Tight bound / Observed loss. Conservative bound uses Theorem 2; Tight bound uses Theorem 3.

4.6

Three-Layer Integration

The layers couple through shared DP-released state: recall drops ˆ BOCPD changepoints batch trigger index updates trading 𝜀 for 𝑅; EC-MPV and index updates to amortise cost; the adaptive schedule √︁ 𝜎𝑡 =𝜎0 𝑇active /𝑡 concentrates noise in early epochs.

Remark 6 (zCDP Accounting Cross-Check). Direct summation of per-mechanism (𝜀, 𝛿)-DP values would yield 𝜀=7.03, which is loose because it ignores the sub-additivity of (𝜀, 𝛿)-DP under composition. Using zCDP: 𝜌 total = 0.0846 + 0.0574 +√0.142 = 0.284, giving 𝜀=4.25 via Eq. (1). Cross-check: GDP (𝜇 total = 1420/50=0.753) gives 𝜀 GDP ≈4.24; PLD accountant (using Google’s dp_accounting library, 𝑇 =1420 compositions at 𝜎𝑡 =50) gives 𝜀 PLD =4.247. RDP, zCDP, GDP, and PLD all agree within 1% at 𝜎𝑡 =50. PLD accountant transcript logs (per-epoch 𝜌𝑖 and cumulative 𝜀) are included in the supplementary code repository.

We state four assumptions and prove nine results (seven theorems, two propositions, one lemma).

Table 3 provides the per-mechanism accounting terms and noise scales used by this composition.

Assumption 3 (Smooth Coalition Value). 𝑣 : 2 N → R is monotone with |𝑣 (𝑆 ∪ {𝑖}) − 𝑣 (𝑆)| ≤ 𝐵=0.2 for all 𝑆, 𝑖, enforced by clipping.

4.5

5

THEORETICAL ANALYSIS

Assumption 2 (Bounded Per-Query Recall Impact). For query 𝑞, let 𝑃𝑞 ≤ 𝑒 𝑓 · 𝐿max be the number of on-path shortcut edges. Each ¯ (ℓ ) > 0. stale on-path shortcut at layer ℓ reduces recall by at most Δ𝑟

Assumption 4 (Bounded Lipschitz Losses). 𝐿𝑡 (a) = 1−𝑅(o𝑡 , a) ∈ [0, 1] and is 𝐺-Lipschitz in o𝑡 .

Alternative DP Design: Exponential Mechanism for Top-𝑘

e once The CHRONOS design releases the full affinity matrix A(𝑡) per epoch, making per-query top-𝑘 selection post-processing with zero marginal privacy cost. An alternative is to release only the top-𝑘 candidate identities via the exponential mechanism [47] or its joint variant [29, 64]. Under this design, the mechanism’s output space is the set of ordered 𝑘-tuples of candidates, and the utility function is the hybrid score 𝑠 𝑗 . The exponential mechanism satisfies 𝜀-DP with sensitivity Δ𝑢 = 𝛽 (since one seller changes one affinity by at most 1, and the hybrid score weights it by 𝛽). Trade-off analysis. Releasing top-𝑘 identities directly avoids the 𝑂 (|𝑉active | ·𝑒 𝑓 ) matrix noise, but incurs three costs: (1) Sampling cost: the joint exponential mechanism over 𝑑 Θ(𝑘 ) sequences requires 𝑂 (𝑑𝑘 log 𝑘 + 𝑑 log 𝑑) time [29], or 𝑂 (𝑑 + 𝑘 2 /𝜀 · ln 𝑑) with recent pruning [64], which is still 10–100× slower than post-processing a pre-released matrix. (2) Per-query cost: because the exponential mechanism is invoked per query, the privacy budget composes over queries rather than epochs; at 100 queries/epoch, 𝜀 would be 100× higher unless each query uses 𝜀/100, yielding near-random selections. (3) Rank consistency: repeated independent exponentialmechanism draws can return inconsistent top-𝑘 sets across similar queries, degrading user experience. For these reasons, CHRONOS adopts the epoch-level matrix release despite its high per-entry noise, because the noise is offset by zero per-query overhead and compositional efficiency. The exponential-mechanism alternative is preferable only when 𝑘 ≪ 𝑒 𝑓 and query rates are very low (< ∼1/epoch).

Assumption 5 (ODE Lipschitz Regularity). The trained neural ODE 𝑓𝜃 is 𝐿𝜃 -Lipschitz in h, and the decay function decay(Δ𝑡) = 𝜎 ([h(Δ𝑡)] 1 ) is monotonically non-increasing with Lipschitz constant 𝐾decay ≤ 𝐿𝜃 /(4𝛽𝐻 ) verified numerically on the validation set. We validate Assumptions 2–5 empirically via leave-one-out onpath removal and ODE trajectory analysis on the validation set; Table 4 provides instantiations. Theorem 2 (Per-Query Temporal Recall Bound (Conservative)). Under Assumptions 1–2, for query 𝑞 with search path path(𝑞): ∑︁
¯ (ℓ𝑒 ) 1 − 𝑒 −𝜆𝑒 Δ𝑡 . (6) E[recall@𝑘 (Δ𝑡) | 𝑞] ≥ 𝑅 ∗ − Δ𝑟 𝑒 ∈path(𝑞)

¯ 1− Under the homogeneous model: E[recall@𝑘 | 𝑞] ≥ 𝑅 ∗ − 𝑃𝑞 Δ𝑟
−𝜆Δ𝑡 ∗ 𝑒 = 𝑅 − O (𝑃𝑞 𝜆Δ𝑡). Proof. By linearity of expectation over independent Poisson stale events on each on-path shortcut; see supplementary Appendix A. □ Theorem 3 (Tightened ODE-Certified Recall Bound (Monotone Envelope)). Under Assumptions 1–5, define the monotone envelope decay(Δ𝑡) = inf 𝑠 ∈ [0,Δ𝑡 ] decay(𝑠). Then: ∑︁
¯ (ℓ𝑒 ) 1 −𝑒 −𝜆𝑒 Δ𝑡 · decay(Δ𝑡). E[recall@𝑘 (Δ𝑡) | 𝑞] ≥ 𝑅 ∗ − Δ𝑟 𝑒 ∈path(𝑞)

(7) 7

The multiplicative factor decay(Δ𝑡) ≤ 1 is computed from the trained ODE with the following certification: under Assumption 5, the Grönˆ wall inequality gives |decay(Δ𝑡) − decay(Δ𝑡)| ≤ 𝜖solver 𝑒 𝐿𝜃 Δ𝑡 where 𝜖solver is the adaptive solver tolerance (set to 10−5 ). The certified lower bound is:   decaycert (Δ𝑡) = max 0, decay(Δ𝑡) − 𝜖solver 𝑒 𝐿𝜃 Δ𝑡 . (8)

Corollary 5 (High-Probability Bound Under Hawkes). Under the Hawkes model, with the spectral radius bound on the Hawkes covariance [7]: " ¯ 𝜇𝐻 Δ𝑡 𝑃𝑞 Δ𝑟 Pr recall@𝑘 ≥ 𝑅 ∗ − · decaycert (Δ𝑡) 1−𝜉 # √︁ ¯ 2𝑃𝑞 ln(1/𝛿𝑅 ) Δ𝑟 − ≥ 1 − 𝛿𝑅 . (11) 1−𝜉

Proof. The key insight is that when a shortcut becomes stale, its contribution to recall loss is attenuated by the decay weight the index assigns to it. Since the decay is monotonically nonincreasing (Assumption 5), we use decay as a certified envelope. Formally: the effective recall impact of a stale shortcut 𝑒 at age Δ𝑡 is ¯ (ℓ𝑒 ) · 𝑝 stale (𝑒, Δ𝑡) ·𝑤 effective (𝑒, Δ𝑡), where 𝑝 stale (𝑒, Δ𝑡) = 1 −𝑒 −𝜆𝑒 Δ𝑡 Δ𝑟 and 𝑤 effective (𝑒, Δ𝑡) ≤ decay(Δ𝑡) because: (i) the index uses decayweighted scores for routing, so stale shortcuts with low decay weights are less likely to be traversed; (ii) the monotone envelope ensures the bound holds even if the ODE exhibits transient nonmonotonicity. The Grönwall bound on ODE solver error provides the certified margin 𝜖solver 𝑒 𝐿𝜃 Δ𝑡 , which is <0.003 for Δ𝑡 ≤ 90 days at 𝐿𝜃 = 0.8 (measured). See supplementary Appendix A. □

1 = 3.3× over At branching ratio 𝜉=0.7: the bound degrades by × 1−0.7 Poisson, matching the empirical 11% 𝜀 rise in §7.4 and the 1.3-point recall drop under Hawkes bursts.

Remark 7 (Hawkes Validation). We fit Hawkes parameters ˆ to MIMIC-IV admission bursts (𝜇ˆ𝐻 =8.2, 𝛼ˆ𝐻 =5.6, 𝛽ˆ𝐻 =8.0, 𝜉=0.70) ˆ and Yelp seasonal-peak events (𝜇ˆ𝐻 =1.7, 𝛼ˆ𝐻 =1.4, 𝛽ˆ𝐻 =2.6, 𝜉=0.54). The Hawkes bound (Theorem 4) with envelope certificate gives 0.203 (MIMIC-IV) and 0.160 (Yelp) at Δ𝑡=7 days vs. observed 0.112 and 0.064 (ratios 1.8× and 2.5×), consistent with the Poisson-case tightening. Theorem 6 (Temporal Valuation Efficiency). Under Assumption 3, EC-MPV satisfies temporal efficiency:

Tightness analysis. On Yelp at Δ𝑡=7 days: decaycert (7) = 0.714 (trained ODE, minus solver margin 0.003), yielding tight bound
¯ 1 − 𝑒 −𝜆Δ𝑡 · 0.714 = 2240 × 3.9×10−4 × 0.999 × 0.714 = 0.128 𝑃𝑞 Δ𝑟 vs. observed 0.050 (ratio 2.6×). At 30 days: decaycert (30) = 0.299, yielding tight bound 0.265 vs. observed 0.107 (ratio 2.5×). The remaining gap is due to path-independence assumptions at hub nodes, where correlations reduce effective 𝑃𝑞 . The monotone-envelope bound reduces the looseness from 5–10× (Theorem 2) to 1.8–3.2× (Table 4).

𝑇 ∑︁ ∑︁ 𝑖 ∈ N 𝑡 =1

¯ 𝜇𝐻 Δ𝑡 𝑃𝑞 Δ𝑟 E[recall@𝑘 (Δ𝑡) | 𝑞] ≥ 𝑅 − . 1−𝜉 More precisely, with the monotone-envelope certificate: ¯ 𝜇𝐻 Δ𝑡 𝑃𝑞 Δ𝑟 · decaycert (Δ𝑡). E[recall@𝑘 (Δ𝑡) | 𝑞] ≥ 𝑅 ∗ − 1−𝜉

𝑇 ∑︁   𝑣 (𝐷 priv (𝑡)∪𝐷 pub (𝑡) | 𝐸𝑡 )−𝑣 (𝐷 pub (𝑡) | 𝐸𝑡 ) . 𝑡 =1

(12) Under clipping at 𝐵, this identity holds for 𝑣 𝐵 ; bias bounded by 𝐵 times clip fraction. Proof. Apply Shapley efficiency to 𝑣 𝐵 (·; 𝐸𝑡 ) at each 𝑡 and sum; clipping bias is < 0.3% empirically. See supplementary Appendix A. □

Theorem 4 (Hawkes-Process Recall Bound). Let edge changes follow an inhomogeneous Hawkes process with baseline intensity 𝜇𝐻 , excitation kernel 𝑔(𝑡) = 𝛼 𝐻 𝑒 −𝛽𝐻 𝑡 (𝛼 𝐻 , 𝛽𝐻 > 0), and branching ratio 𝜉 = 𝛼 𝐻 /𝛽𝐻 < 1 (stability h∫ condition). i Define the cumulative Δ𝑡 𝜇𝐻 Δ𝑡 compensator Λ𝐻 (0, Δ𝑡) = E 0 𝜆(𝑠) 𝑑𝑠 = 1−𝜉 . Then: ∗

MPV𝑖 (𝑡, 𝐸𝑡 ) =

 𝑖 be the reTheorem 7 (EC-MPV Estimation Error). Let MPV leased score. Under correct event identification: 2 2    𝑖 − MPV𝑖 ) 2 ≤ 𝐵 (1 − 𝜌 ) + (𝜎𝑡 · 𝑆 val ) 2 . E ( MPV 𝑚 | {z } | {z } sampling (VRDS)

(9)

(13)

DP noise

Under event misidentification, an additional squared-bias term (MPV𝑖 (𝑡, 𝐸𝑡 )− MPV𝑖 (𝑡, 𝐸𝑡′ )) 2 arises. Without VRDS, set 𝜌=0. Proof. Decompose into sampling error, DP noise, and eventmisidentification bias; independence gives the MSE bound. See supplementary Appendix A. □

(10)

The high-probability bound (Corollary 5) further accounts for Hawkesinduced temporal clustering.

Proposition 8 (Formal Sensitivity Bounds). Under seller-level edge adjacency with 𝐶 max = ⌈1.5|𝐸|/𝑛⌉: (a) √︃Valuation: 𝑆 val = 4𝐵/𝑛 (𝐵=0.2,

Proof. Under Hawkes dynamics, the stale probability for each shortcut becomes Pr[stale in [0, Δ𝑡]] ≤ 1 − 𝑒 −Λ𝐻 (0,Δ𝑡 ) by the compensator inequality. For a stable Hawkes process, Λ𝐻 (0, Δ𝑡) = 𝜇𝐻 Δ𝑡/(1−𝜉) in expectation. The key subtlety is that Hawkes events are not independent across shortcuts sharing hub nodes. We handle this via a union-bound argument over layers: shortcuts at layer ℓ sharing a hub ℎ have correlated change events, but the total layer¯ (ℓ ) · Λ (ℓ ) (0, Δ𝑡) where ℓ contribution is bounded by |𝑁 ℓ (ℎ)| · Δ𝑟 𝐻 Λ𝐻(ℓ ) accounts for the hub’s Hawkes rate. Summing over layers and applying the monotone-envelope certificate yields the result. See supplementary Appendix A. □

edge

𝑛=10: 𝑆 val =0.08). (b) Affinity: Δ2 = 𝐶 max , reduced by Stage 2 cap. On Yelp: Δ2 ≈545 (global), 18.1 (active-scope). (c) Index statistics: 𝑆 idx ≤ 1.5/𝑛. Lemma 9 (Safety Override Count). Under √ the adaptive schedule and Poisson edge changes, E[𝑁 ] = O ( 𝑇 ) and Pr[𝑁 override > override √︁ 𝑐 𝑇 ln(1/𝛿)] ≤ 𝛿. Proof. Budget overrides cluster near end-of-horizon; recall overrides are bounded by pre-convergence EXP3-IX epochs; AzumaHoeffding gives concentration. See supplementary Appendix A. □ 8

√︁ Theorem 10 (Coordination Regret). With 𝑑=3, 𝜂= ln 𝑑/(𝑑𝑇 ), 𝛾=𝜂/2:

Table 5: Settlement audit SNR under coalition-level adjacency (𝑛=10, 𝐵=0.2, 𝜎𝑡 =50).

𝑇 ∑︁ √ √︁ √ 1 E[𝑅𝑇 ] ≤ 3 𝑑𝑇 ln 𝑑 + 𝐺𝜎obs + O ( 𝑇 ) = O ( 𝑇 log𝑇 ). √︁ | {z } min(𝑡,𝑊max ) | {z } 𝑡 =1 EXP3-IX | {z } overrides observation noise

𝑊 (epochs)

𝑛 coal

SNR

Attribution Level

1 7 14 7 28

1 5 5 3 5

0.05 0.70 1.40 1.17 2.80

Noise-dominated Trend: above/below median Rank-order coalitions Trend per 3-seller group Quantitative attribution

SNRsettle =

𝑊 · 𝜙¯coal 𝑊 · 𝜙¯coal · 𝑛 = . 𝜎𝑡 · 4𝐵 · 𝑛 coal /𝑛 4𝐵 · 𝑛 coal · 𝜎𝑡

(14)

Proof. Standard EXP3-IX bound plus observation noise plus override regret (Lemma 9). See supplementary Appendix A. □ Theorem 11 (Temporal Safety Composition). Under the adap√︁ tive schedule 𝜎𝑡 = 𝜎0 𝑇active /𝑡 applied only in active epochs, CHRONOS satisfies (𝜀 total, 𝛿 total )-DP with: ! √︁ 𝑇active · ln(1/𝛿 total ) 𝜀 total = O . (15) 𝜎0

by 𝑛 coal ×:

With 𝑊 =7, 𝑛 coal =5, 𝑛=10, 𝜙¯coal =0.4 (summed coalition MPV), 𝐵=0.2, 𝜎𝑡 =50: SNRsettle =7×0.4×10/(4×0.2×5×50)=0.70, making trend-level attribution feasible (above/below median contribution distinguishable at 95% confidence). At𝑊 =14: SNR=1.40, enabling rank-ordering of coalitions. Component 3: Cryptographic escrow (optional). For sellers requiring individual-level audit, the pre-noise valuations can be placed in a hash-committed escrow: the operator publishes 𝐻 (𝜙ˆ𝑖 , 𝑟𝑖 ) at each epoch (zero DP cost, since the hash is a commitment, not a release of 𝜙ˆ𝑖 ). Disputes trigger a two-party audit protocol where the operator reveals (𝜙ˆ𝑖 , 𝑟𝑖 ) to a neutral arbiter who verifies the commitment. This does not replace DP (the arbiter sees exact values) but provides contractual accountability. Revenue reconciliation. Total revenue distributed internally (Component 1) must match the Shapley efficiency sum (Theorem 6). The coalition audit release (Component 2) provides external evidence that the internal distribution is “approximately correct” at coalition granularity. Table 5 shows SNR across configurations.

Proof. Sum per-step moments over active epochs, optimise over 𝛼, and convert to (𝜀, 𝛿)-DP. Exact 𝜀=4.25 verified by zCDP closed-form (Eq. (5)). See supplementary Appendix A. □

6

INFORMATIVENESS OF PRIVATE RELEASES

A transparent assessment requires acknowledging fundamental DP limitations at the chosen parameters.

6.1

Private Affinity Signal

With 𝜎entry =885 over [0, 1]-bounded affinities, post-clipping signals are near-Bernoulli(1/2); the 𝛽=0.3 weight gives maximal hybridscore variation of ≈0.0003 between candidates. Per-query private scoring contributes ≤0.002 recall (Table 15). Observed 0.941 recall@10 derives from: (i) public cosine routing; (ii) public HNSW structure with ODE-attenuated staleness scheduling; (iii) adaptive coordinator scheduling triggered by DP-released index statistics (SNR ≈1.3).

6.2

6.4

External Valuation Releases and Auditability

Operational Implications

The CHRONOS design prioritises: (1) system-level utility via public components; (2) adaptive scheduling via low-sensitivity DP statistics; (3) formal privacy guarantees; (4) actionable settlement via multi-epoch coalition aggregation. The private affinity signal contributes minimally to per-query accuracy. This trade-off is by design: per-query DP selection degrades QPS by 6–10× at similar noise levels (Table 12).

The external valuation release (noise std 4.0 on signal range [0, 0.2]) has SNR ≈0.05. Sellers receive values dominated by DP noise, serving only non-disclosure and plausible-deniability guarantees. For actionable revenue settlement, see §6.3.

6.3

(16)

Actionable Seller Settlement Mechanism

The trade-off between DP noise and seller-facing attribution is addressed through a three-component settlement mechanism. Component 1: Internal pre-DP settlement. Under the trustedcurator model, the operator computes pre-noise MPV scores 𝜙ˆ𝑖 with Val. Err=0.013 and distributes revenue proportionally. These internal computations are exact Shapley-efficient (Theorem 6) and never leave the trusted perimeter. Component 2: Multi-epoch coalition-level audit release. For external verifiability, we aggregate valuations over 𝑊 epochs and group sellers into coalitions of size 𝑛 coal . Under coalition-level adjacency (protecting whether coalition 𝐶 𝑗 participates, not individual 𝑠𝑖 ), sensitivity drops from 4𝐵/𝑛 to 4𝐵/(𝑛/𝑛 coal ), raising SNR

7 EXPERIMENTAL EVALUATION 7.1 Setup Datasets. Table 6 summarises four benchmarks: FB15K-237 and WN18RR with synthetic Poisson annotations, MIMIC-IV and Yelp with real timestamps. Hardware. 2× Xeon Gold 6348 (56 cores), 512 GB RAM, 2× A100 80 GB; Ubuntu 22.04, CUDA 12.1, PyTorch 2.1, torchdiffeq 0.2.3. All results averaged over 5 seeds (mean ± std). Reproducibility. Code, checkpoints, DP accountant transcript (PLD logs), and baseline configuration/deviation logs will be released upon acceptance. 9

Table 6: Datasets. 𝜆 in changes/day/shortcut.

Table 8: VSAG comparison on Yelp (𝑘=10, 5 seeds). VSAGHybrid adds post-hoc graph affinity with same 𝛽=0.3 for fair comparison.

Dataset

Nodes

Edges

Temporal

𝝀

Domain

FB15K-237 [56] WN18RR [19] MIMIC-IV [34] Yelp [71]

14.5K 40.9K 89.4K 236K

310K 86.8K 1.2M 1.98M

Synth. Synth. Real Real

0.05 0.05 ≈12 ≈2.9

General KG Lexical Clinical Local commerce

Table 7: Recall@10 contribution breakdown on Yelp (static snapshot, 5 seeds). Component Graph-aware static baseline (same params) + temporal decay (exponential) + temporal decay (neural ODE) + community-sorted insertion + hub-biased layering

R@10

𝚫 vs. baseline

.858±.003 .892±.003 .904±.002 .920±.002 .935±.002

— +3.4 pts +4.6 pts +6.2 pts +7.7 pts

Method

R@10

QPS

P50

P99

𝜺

VSAG (pure vector) VSAG-Hybrid T-LEGEND T-LEGEND+DP (Chronos)

.831 .869 .935 .937

8.38 5.08 3.18 2.74

49 81 127 161

115 187 281 317

∞ ∞ ∞ 4.25

VSAG-accelerated T-LEGEND (projected): T-LEGEND+VSAG layout .935 4.79† T-LEGEND+VSAG+DP .937 4.16†

84 98

198 222

∞ 4.25

† Projected: VSAG’s cache-friendly layout reduces HNSW traversal by ≈1.5× ; verified on the

pure-vector workload. DP overhead is zero on the query path (post-processing).

Table 9: Recall@10 on static benchmarks (𝑘=10, 𝑒 𝑓 =128, 5 seeds).

Configuration. 𝑒 𝑓 =128, 𝑒 𝑓𝑐 =200, 𝛽=0.3, 𝑛=10 sellers (balanced partition unless noted), 1000 permutation samples for Shapley with VRDS control variates. Baselines. Indexing: Plain-HNSW [45], TigerVector [43], NaviX [59], FreshDiskANN [61], SPFresh [69], Quake [49], VSAG [75] (production HNSW with cache-friendly layout). Valuation: Data Shapley [28], Beta Shapley [39], VRDS [65], Static MPV, Time-Sliced Shapley, RSS [32]. Coordination: Uncoordinated, Round-Robin, FixedNoise, EXP3 [5], BwK [52]. Drift: ADWIN [9], Page-Hinkley [54], Dm-BOCD [36]. DP top-𝑘: OneShot Laplace [22], StableTopK [8], Joint Exponential [29], Permute-and-Flip [46]. Research Questions. We organise the evaluation around six explicit research questions: RQ1: Does neural-ODE temporal decay improve recall over static and exponential-decay baselines, and how tight are the theoretical bounds? RQ2: Does EC-MPV with BOCPD conditioning improve valuation accuracy after distributional shifts compared to static Shapley? RQ3: Does the Temporal Coordinator reduce privacy-budget waste compared to uncoordinated and round-robin strategies? RQ4: How does CHRONOS scale with the number of sellers and horizon length in terms of 𝜀 and recall? RQ5: What is the privacy-utility trade-off of the epoch-level Gaussian mechanism compared to per-query DP alternatives at matched 𝜀? RQ6: How do realistic marketplace dynamics (buyer arrival skew, seller competition, and pricing sensitivity) affect end-to-end performance? Baseline Fairness Verification. All index baselines use identical parameters: 𝑀=16, 𝑒 𝑓 =128, 𝑒 𝑓𝑐 =200, 𝐿max =5, 𝜌 div =0.7. Graphaware baselines receive the same KG structure and static community affinities; only T-Legend additionally uses temporal decay. Table 7 decomposes the recall gain. VSAG Throughput Comparison. We integrate VSAG [75] as a production HNSW reference to separate traversal/layout speedups from T-LEGEND’s decay-aware 10

Method

FB15K

WN18RR

MIMIC

Yelp

Plain-HNSW TigerVector NaviX Diversified-HNSW VSAG-Hybrid FreshDiskANN SPFresh Quake T-LEGEND

.821±.004 .842±.003 .864±.003 .872±.003 .881±.003 .836±.003 .829±.004 .848±.003 .941±.002

.843±.003 .861±.003 .878±.002 .886±.002 .892±.002 .858±.003 .851±.003 .869±.003 .956±.002

.798±.005 .817±.004 .839±.004 .848±.003 .857±.003 .823±.004 .814±.005 .831±.004 .927±.003

.809±.004 .828±.003 .848±.003 .858±.003 .868±.003 .836±.003 .829±.004 .842±.003 .935±.002

improvements. VSAG uses cache-friendly graph layout and automatic parameter tuning but does not model temporal staleness or provide DP guarantees. Key findings. (1) VSAG’s pure-vector QPS (8.38) is 2.6× higher than T-LEGEND (3.18), but recall is 10.4 pts lower because VSAG lacks temporal KG scoring. (2) VSAG-Hybrid (post-hoc affinity) closes 3.8 pts of the gap but remains 6.6 pts below T-LEGEND, confirming that decay-aware construction (not just layout) drives the recall advantage. (3) Projected VSAG-accelerated T-LEGEND would achieve 4.16 QPS at 𝜀=4.25 (vs. 2.74 currently), a 1.5× speedup from layout alone. Integration requires adapting VSAG’s auto-tuner to respect ODE-weighted edges and is identified as engineering work. Recall Results. Table 9 reports recall@10 on static benchmarks. Over 90 simulated days on MIMIC-IV with weekly updates, TLegend degrades at 0.0021 recall points/day versus 0.0089 for PlainHNSW (4.2× improvement) and 0.0058 for FreshDiskANN (2.8×), consistent with Theorem 2 (Figure 3). Valuation and Drift Detection. Í ˆ 𝑖 − MPVgold ) 2 ; Valuation error metric. Val.Err = 𝑛1 𝑛𝑖=1 ( MPV 𝑖 gold standard uses 𝑚=50,000 permutations (SE ≈0.004), confirmed by exhaustive enumeration (𝑛≤15) within 0.002. EC-MPV captures abrupt value shifts missed by static methods. EC-MPV+VRDS achieves the lowest estimation error (0.013 vs. 0.024 baseline). RSS [32] yields Val. Err 0.019 at 9.5× sampling cost; postchangepoint RSS degrades to 0.031, confirming event-conditioning

Figure 3: Recall@10 degradation on MIMIC-IV (𝜆 ≈ 12 changes/day/shortcut) over 90 simulated days without reindexing.

Figure 4: Privacy-utility operating points on Yelp. Chronos (Blue Square) achieves higher recall at each 𝜀 level than perquery DP mechanisms (Red Triange) at matched 𝜀=4.25, while maintaining 2.74 QPS vs. 0.28–0.43 for per-query alternatives.

Table 10: Drift detectors on Yelp (8 injected seasonal events). Δ𝜌: wasted 𝜌 from false alarms. Detector

Prec.

Rec.

Δ𝜌

BOCPD Dm-BOCD [36] ADWIN [9] Page-Hinkley

.875 1.00 .615 1.00

.875 .750 1.00 .625

0.004 0.000 0.020 0.000

Table 12: DP retrieval mechanisms at matched 𝜀=4.25 on Yelp (5 seeds).

Table 11: End-to-end performance on Yelp (5 runs). System

R@10

QPS

TPS

P50

P99

𝜺

Val.Err

HNSW+No-DP Hybrid+GaussDP KG+StaticVal CHRONOS

.817 .838 .904 .937

3.41 1.48 1.75 2.74

244 106 124 138

74 165 175 161

201 396 352 317

∞ 2.10 1.40 4.25

N/A 0.040 0.023 0.012

R@10

QPS

P50

P99

𝜺/query

Chronos (epoch) OneShot Laplace StableTopK Joint Exponential Permute-and-Flip

.937 .891 .909 .920 .904

2.74 0.40 0.37 0.28 0.43

161 498 533 698 461

317 1265 1406 1653 1172

0 1.18×10 −5 1.18×10 −5 1.18×10 −5 1.18×10 −5

Table 13: Scalability analysis on Yelp (𝜎𝑡 =50, 𝛿=10−6 , 90-day horizon, 5 seeds). 𝜌 total computed via zCDP.

provides orthogonal benefits. Comparative detector precision/recall and privacy waste are reported in Table 10.

7.2

Mechanism

𝑛

𝑆 val

Δactive 2

𝑇active

𝜌 total

𝜀

R@10

10 50 100 200 500

0.080 0.016 0.008 0.004 0.0016

18.1 8.1 5.7 4.0 2.6

710 824 891 952 1031

0.284 0.329 0.356 0.381 0.412

4.25 4.58 4.76 4.93 5.13

.937±.002 .939±.002 .940±.002 .940±.002 .941±.002

End-to-End Performance with 𝑛 at fixed 𝜎𝑡 : more sellers means lower per-seller sensitivity, which benefits DP. However, 𝑇active may increase with 𝑛 (more sellers trigger more frequent updates). Key findings. (1) 𝜀 grows sublinearly with 𝑛: from 4.25 (𝑛=10) to 5.13 (𝑛=500), a 21% increase for a 50× increase in sellers. This is because reduced sensitivity (Δ2 drops from 18.1 to 2.6) largely offsets the increased 𝑇active . (2) Recall improves slightly with 𝑛 (more sellers provide more data). (3) The affinity release remains useful for scheduling at all 𝑛: the index statistics mechanism (SNR ≈1.3) drives coordinator decisions, and its sensitivity 𝑆 idx = 1.5/𝑛 improves with 𝑛.

DP Retrieval Mechanism Comparison. Table 12 provides a head-to-head comparison against per-query DP mechanisms under matched total 𝜀=4.25 on Yelp as seen in Figure 4. Scalability Analysis. We analyse how 𝜌 total and per-mechanism 𝜌 scale with the number of sellers 𝑛 and horizon length. √︃ edge

Sensitivity scaling. 𝑆 val = 4𝐵/𝑛 decreases with 𝑛; Δ2 = 𝐶 max = √ ⌈1.5|𝐸|/𝑛⌉ decreases as Θ(1/ 𝑛); the active-scope cap 𝜅 active ∝ |𝐸 active |/𝑛 also decreases. This means per-mechanism 𝜌𝑖 decreases

√︁

11

Table 15: Monte Carlo rank-stability ablation (𝛽=0.3, Yelp, 105 queries, 5 seeds).

Table 14: DP vs. cryptographic alternatives for affinity scoring (Yelp, 𝑛=10). Noise

𝝈entry

R@10

𝝉 (all)

𝝉 (top-10)

Agg. loss

Trusted curator Semi-honest 2PC Client-side HE Hardware trust

𝜎=885 Zero Zero Zero

0.01 (near non-priv.) 0.5 5 100 885 (Chronos)

.939 .938 .938 .937 .937

0.990 0.981 0.962 0.929 0.938

0.998 0.994 0.978 0.965 0.968

0.0001 0.0005 0.0011 0.0022 0.0020

Hybrid: CHRONOS + TEE for settlement (§6.3): CHRONOS+TEE 161 ms† 2.74 Curator + TEE

𝜎=885†

Approach

Per-Query Latency

QPS

Trust Model

CHRONOS (DP) 2PC-Garbled [18] HE (CKKS) [41] TEE (SGX) [16]

161 ms ∼2.4 s ∼1.1 s ∼210 ms

2.74 0.08 0.18 2.14

Table 16: Private-edge discovery analysis (𝑘=10, 5 seeds).

† TEE used only for settlement verification (off query path), not per-query scoring. Query-path

latency and noise are unchanged.

Long-horizon scaling. Over a 360-day horizon (vs. 90 days), 𝑇active roughly quadruples to ≈2,800 at 𝑛=10, giving 𝜌 total ≈1.12 and 𝜀≈8.47. At 𝑛=100 over 360 days: 𝜌 total ≈1.42, 𝜀≈9.52. For multi-year deployments, periodic “budget epochs” (resetting the accountant with fresh 𝜎0 ) are necessary, analogous to privacy odometer checkpoints [58]. DP vs. Cryptographic Alternatives. Table 14 compares DP noise-based protection with cryptographic alternatives for the affinity computation workload. Analysis. (1) 2PC and HE eliminate noise but introduce 7–30× latency overhead per query, making them impractical for real-time retrieval at marketplace scale. (2) TEE-based computation (Intel SGX, AMD SEV) achieves near-DP latency (210 ms) with zero noise, but requires hardware trust assumptions and is vulnerable to sidechannel attacks [11]. (3) The most practical hybrid is CHRONOS for real-time queries (tolerating noise for speed) with TEE-based settlement verification for auditability (no noise where it matters for payouts). This aligns with the settlement mechanism in §6.3: Component 3 (cryptographic escrow) can use TEE attestation for commitment verification. (4) For workloads that can tolerate higher latency (e.g., batch analytics), HE-based exact affinity computation is viable and composable with CHRONOS’s public index structure. Rank Stability Under DP Noise.

Dataset

Miss rate

Recall gap

New-edge frac.

𝜷

Yelp (𝛽=0.3) Yelp (𝛽=0.7) MIMIC-IV (𝛽=0.3) MIMIC-IV (𝛽=0.7)

4.5%±0.9 12.4%±1.5 5.8%±1.1 14.2%±1.8

−0.009 −0.032 −0.012 −0.042

5.8% 5.8% 8.3% 8.3%

0.3 0.7 0.3 0.7

Table 17: Privacy-utility trade-off on Yelp, sampled rows (5 seeds). 𝜀 computed via Eq. (1). 𝜎0

𝜌 total

𝜀

R@10 (Adaptive)

R@10 (Fixed)

30 50 100

0.789 0.284 0.071

7.50 4.25 2.13

.938±.002 .937±.002 .932±.003

.927±.003 .917±.003 .900±.004

Table 17 summarises the privacy-utility frontier under different 𝜎0 settings, including the adaptive-vs-fixed scheduling comparison.

7.3

Realistic Marketplace Dynamics (RQ6)

Standard benchmark partitions assume balanced seller contributions and uniform query rates. We evaluate two realistic distortions. Buyer arrival skew. We model buyer arrivals as a non-homogeneous Poisson process with hourly rate 𝜆𝑞 (𝑡) = 𝜆¯𝑞 (1 + 0.5 sin(2𝜋𝑡/24)) to simulate diurnal patterns. Under this skew, uncoordinated baseline exhausts 80% of its budget during peak hours (10:00–14:00), leaving only 20% for overnight queries. The Temporal Coordinator shifts 34% of index-update actions to off-peak periods by pre-allocating budget, reducing peak-hour budget exhaustion to 52% and improving worst-case P99 latency from 412 ms to 289 ms. Seller competition and pricing sensitivity. We simulate a duopolistic sub-market where two sellers contribute substitutable edges (same entity pairs, overlapping relations). When seller A increases contribution quality (lower noise, fresher timestamps), seller B’s Shapley share drops non-linearly: a 20% quality improvement by A causes B’s share to fall 31% under static Shapley, but only 18% under EC-MPV because the event-conditioned recompute captures A’s quality shift and rebalances marginal contributions within the same epoch. This confirms that static pricing creates misaligned incentives in competitive settings, whereas EC-MPV reduces incentive distortion by 42%. Valuation accuracy and seller retention. We simulate seller dropout: sellers whose MPV falls below a threshold for 3 consecutive epochs exit with probability 𝑝 exit . Under static Shapley with DP

Proposition 12 (Rank-Flip Probability at Top-𝑘 Boundary). Let candidates 𝑖 (ranked 𝑘-th) and 𝑗 (ranked (𝑘+1)-th) have true hybrid scores 𝑠𝑖 > 𝑠 𝑗 . The probability that DP noise flips their ordering is: ! 𝑠𝑖 − 𝑠 𝑗 𝑃 (flip𝑖 𝑗 ) = Φ − √ 𝛽𝜎entry 2 where Φ is the standard normal CDF. Remark 8 (Reconciling 𝜎entry =885 with High Rank Stability). Post-clipping noise is bimodal at {0, 1} with 𝜎clip ≈0.50; cosine dominance (weight 0.7) governs ≈80% of within-top-10 pairs. Private-Edge Discovery Rate. Seller Skew and Revenue-Share Analysis. Under 80/20 skew, the dominant seller’s revenue share is 0.62 unclipped vs. 0.48 after clipping; adaptive clipping [4] reduces KL to 0.019. Full per-seller confidence intervals in supplementary Appendix C. Privacy-Utility Trade-off. 12

Table 19: Ablation on FB15K-237. All 𝜀 via Eq. (1).

Table 18: 𝜀 budget breakdown across operating modes. Mode

𝜀 train

𝜀 aff

𝜀 val

𝜀 idx

𝜀 total

Variant

R@10

TPS

P50

𝜺

Chronos (𝛽=0.3) Chronos + SVT (𝛽=0.7) Chronos + DP-SGD (𝛽=0.3) Chronos + DP-SGD + SVT (𝛽=0.7)

0 0 1.50 1.50

2.94 2.94 2.94 2.94

1.84 1.84 1.84 1.84

2.25 2.30 2.25 2.30

4.25∗ 4.40∗ 5.75 5.90

CHRONOS (full) w/o temporal decay w/o private DP affinity (𝛽=0) w/o neural ODE (exp. decay) w/ 𝛽 = 0.7 w/ cold-start queries w/ cold-start + fallback w/o aff. privatisation w/o EC-MPV (static Shapley) w/o VRDS w/o BOCPD w/o Coordinator (round-robin) w/o incremental upd. w/ BwK coordinator [52]

.941 .897 .863 .929 .920 .891 .922 .943 .941 .941 .941 .908 .941 .939

141 149 158 141 138 141 139 143 141 141 141 105 43 136

158 151 143 159 165 158 162 155 158 158 158 213 412 164

4.25 4.25 4.25 4.25 4.47 4.25 4.27 — 4.48 4.25 4.59 5.38 4.25 4.25

∗ Standard additive zCDP composition (Eq. (1)).

noise (std 4.0), false-positive exits (noise pushing a legitimate seller below threshold) occur at 12%/epoch. EC-MPV+VRDS reduces this to 4%/epoch by conditioning on actual distributional shifts rather than noise fluctuations. The coordinator further reduces exit rate to 2.5%/epoch by batching revaluation at genuine changepoints, cutting unnecessary DP spend.

8 7.4

Non-Poisson dynamics. Under Hawkes bursts (𝜇=2.9, branching 𝜉=0.7) on Yelp, recall drops 1.3 pts and 𝜌 rises 11%. The Hawkes recall bound (Theorem 4) predicts 3.3× degradation at 𝜉=0.7, consistent with the observed 1.3-point drop. Under sinusoidal trends, degradation is only 0.5 pts and 4%. Under block-homogeneous Poisson: −2.1 pts, +18% 𝜌. Staleness, overlap 𝜂, and reward weights. Overlap stresstest (𝜂∈{1.2, 1.5}): effective 𝜌 rises to 0.409/0.639, matching 𝜂 2 ·𝜌 analytically within ±2%. Safety overrides and epoch duration. Over 2,160 epochs on MIMIC-IV: budget overrides 47 (2.2%), recall √ overrides 12 (0.6%), cumulative regret 78±7 consistent with O ( 𝑇 ). High-𝛽 Regime and Cold-Start. Below 𝛽=0.5, recall remains > 0.93; above 𝛽=0.7, recall drops sharply. Cold-start entities lose 4.7 pts under privatisation; fallback mode recovers 3.1 pts. SVT prototype at 𝛽=0.7 recovers 52% of misses at +0.05 𝜀. End-to-end 𝜀 under DP-SGD. When X0 is trained privately: 𝜀 total = 1.5 + 4.25 = 5.75 (𝛿 total = 2×10−6 ). The complete budget decomposition across operating modes is shown in Table 18.

7.5

RELATED WORK

We survey six areas and identify the specific gap each leaves for temporal KG marketplaces. Dynamic ANN and temporal graph indices. FreshDiskANN [61], SPFresh [69], Quake [49], CleANN [74], and MN-RU [67] support streaming updates but do not model KG structural staleness or provide recall bounds tied to evolution rates. VSAG [75] offers production-grade layout; our Table 8 shows layout speedups are complementary to, not substitutes for, decay-aware construction. None of these systems integrates DP guarantees. Gap: no hybrid index provides per-query recall bounds and DP-compatible public/private separation. Data marketplaces and pricing. Commercial and academic marketplaces [6, 26] support query-based pricing, subscription models, and static data products. Dealer [42] provides an end-to-end DP model marketplace but assumes static data and does not couple indexing with valuation under a shared privacy budget. Agora [38] focuses on access control and auditability rather than temporal query performance. Recent work on data pricing in ML pipelines [15] and query-based pricing [37] do not address non-stationary valuations or index freshness. Gap: no marketplace platform couples temporal indexing, event-conditioned valuation, and coordinated DP-budget management. DP on graphs and private retrieval. Edge-level DP for graph statistics [35, 50, 53] and node-level DP for GNN training [73] protect structural information, but they target analytics and model training rather than real-time retrieval. PSGraph [72] demonstrates temporal-aware DP allocation for graph synthesis. DP learned indexes [21] apply DP to index structures; CHRONOS avoids this cost by treating the index as public. Per-query DP selection mechanisms [22, 29, 64] incur 6–10× QPS degradation (Table 12). Gap: no prior work amortises DP cost epoch-wide for hybrid vector-graph retrieval while bounding sensitivity via seller-level adjacency. DP-aware coordination and bandits. Privacy-preserving bandits [3, 62, 66] privatise actions or rewards but do not integrate with index maintenance or data valuation. Privacy filters and odometers [25, 58] track composition but do not schedule multi-agent operations. Gap: no prior coordination mechanism optimises the

Robustness and Sensitivity

Ablation Study

Ablation interpretation and coupling evidence. The ablation rows address the concern that the three layers are co-located rather than co-designed. While removing EC-MPV or BOCPD leaves recall unchanged at .941, the privacy cost rises: without EC-MPV, 𝜀 increases to 4.48 (+5.4%) because static Shapley triggers more frequent revaluation; without BOCPD, 𝜀 reaches 4.59 (+8.0%) because undetected changepoints cause redundant recomputation. Removing the Coordinator entirely (round-robin) degrades recall by 3.3 pts and raises 𝜀 to 5.38 (+26.6%), confirming that the Coordinator is the lynchpin coupling index freshness, valuation accuracy, and budget efficiency. These results show that T-LEGEND alone delivers high recall, but the full CHRONOS system is required to maintain that recall at minimal privacy cost. 13

allocation of a shared DP budget among indexing, valuation, and idle actions with sub-linear regret guarantees. Data valuation under non-stationarity. Data Shapley [28], Beta Shapley [39], Data Banzhaf [63], and Distributional Shapley [27] assume stationary utilities. VRDS [65] reduces variance but does not condition on events. RSS [32] offers stratified sampling yet degrades post-changepoint (Val. Err 0.031 vs. 0.013). Gap: no Shapley estimator couples changepoint detection with finite-sample error bounds under DP noise. Temporal KG embedding and retrieval. TTransE [40], HyTE [17], TNTComplEx [70], TGAT [68], and RE-Net [33] model temporal facts but provide no retrieval-guarantee structures. TG-RAG [30] retrieves temporal subgraphs for LLM reasoning without formal DP or recall bounds. Gap: none combines temporal semantics with approximate nearest-neighbour guarantees and privacy accounting.

9

CONCLUSION

Chronos is a three-layer architecture for temporally-aware data marketplaces under a trusted-curator model. Our main technical contributions are sixfold: (1) a monotone-envelope certificate (Theorem 3) that tightens the recall bound to 1.8–3.2× observed loss by incorporating ODE Lipschitz structure with Grönwall-based solver verification; (2) formal Hawkes-process recall bounds (Theorem 4) extending guarantees beyond Poisson to correlated dynamics parameterised by branching ratio; (3) a concrete multiepoch coalition-level settlement mechanism (§6.3) with SNR analysis indicating trend-level seller attribution at 𝑊 ≥7 epochs; (4) scalability analysis to 500 sellers (Table 13) showing that 𝜀 grows sublinearly; (5) a head-to-head VSAG comparison (Table 8) separating layout speedups from decay-aware recall gains; and (6) DP-vs-crypto cost analysis (Table 14) situating the DP design within the broader privacy-mechanism landscape. Overall, these results show that the proposed architecture achieves a consistent recall/latency/privacy trade-off under the stated trust and privacy assumptions. Limitations. (1) Remaining bound gap: the monotone-envelope bound is 1.8–3.2× loose; closing the residual gap requires pathcorrelation analysis at hub nodes, identified as future work. (2) Private signal informativeness: affinity (𝜎entry =885) and valuation (noise std 4.0) releases remain noise-dominated at 𝜀=4.25; utility derives from public routing and adaptive scheduling. (3) Trust assumptions: trusted curator with near-exclusive ownership (𝜂≈1); two-server extensions are currently design-level and require prototype validation. Open problems. (1) DP-safe dynamic candidate expansion. (2) Closing the residual 1.8–3.2× bound gap via hub-correlation analysis. (3) Full two-server implementation with additive secret sharing. (4) End-to-end query privacy under continual observation. (5) Alternative valuation mechanisms (Banzhaf values) with lower DP sensitivity.

REFERENCES [1] Martin Abadi, Andy Chu, Ian Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. 2016. Deep Learning with Differential Privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security (Vienna, Austria) (CCS ’16). Association for Computing Machinery, New York, NY, USA, 308–318. https://doi.org/10.1145/2976749.2978318 [2] Ryan Prescott Adams and David J. C. MacKay. 2007. Bayesian Online Changepoint Detection. arXiv:0710.3742 [stat.ML] https://arxiv.org/abs/0710.3742 14

[3] Naman Agarwal and Karan Singh. 2017. The Price of Differential Privacy For Online Learning. arXiv:1701.07953 [cs.LG] https://arxiv.org/abs/1701.07953 [4] Galen Andrew, Om Thakkar, H. Brendan McMahan, and Swaroop Ramaswamy. 2021. Differentially private learning with adaptive clipping. In Proceedings of the 35th International Conference on Neural Information Processing Systems (NIPS ’21). Curran Associates Inc., Red Hook, NY, USA, Article 1335, 12 pages. [5] Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert E. Schapire. 2002. The Nonstochastic Multiarmed Bandit Problem. SIAM J. Comput. 32, 1 (2002), 48–77. https://doi.org/10.1137/S0097539701398375 arXiv:https://doi.org/10.1137/S0097539701398375 [6] Santiago Andrés Azcoitia and Nikolaos Laoutaris. 2022. A Survey of Data Marketplaces and Their Business Models. SIGMOD Rec. 51, 3 (Nov. 2022), 18–29. https://doi.org/10.1145/3572751.3572755 [7] Emmanuel Bacry, Iacopo Mastromatteo, and Jean-François Muzy. 2015. Hawkes processes in finance. arXiv:1502.04592 [q-fin.TR] https://arxiv.org/abs/1502. 04592 [8] Mitali Bafna and Jonathan Ullman. 2017. The Price of Selection in Differential Privacy. arXiv:1702.02970 [cs.DS] https://arxiv.org/abs/1702.02970 [9] Albert Bifet and Ricard Gavaldà. [n.d.]. Learning from Time-Changing Data with Adaptive Windowing. 443–448. https://doi.org/10.1137/1.9781611972771.42 arXiv:https://epubs.siam.org/doi/pdf/10.1137/1.9781611972771.42 [10] Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. 2008. Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment 2008, 10 (Oct. 2008), P10008. https://doi.org/10.1088/1742-5468/2008/10/p10008 [11] Ferdinand Brasser, Urs Müller, Alexandra Dmitrienko, Kari Kostiainen, Srdjan Capkun, and Ahmad-Reza Sadeghi. 2017. Software grand exposure: SGX cache attacks are practical. In Proceedings of the 11th USENIX Conference on Offensive Technologies (Vancouver, BC, Canada) (WOOT’17). USENIX Association, USA, 11. [12] Javier Castro, Daniel Gómez, and Juan Tejada. 2009. Polynomial calculation of the Shapley value based on sampling. Comput. Oper. Res. 36, 5 (May 2009), 1726–1730. https://doi.org/10.1016/j.cor.2008.04.004 [13] T.-H. Hubert Chan, Elaine Shi, and Dawn Song. 2011. Private and Continual Release of Statistics. ACM Trans. Inf. Syst. Secur. 14, 3, Article 26 (Nov. 2011), 24 pages. https://doi.org/10.1145/2043621.2043626 [14] Ricky T. Q. Chen, Yulia Rubanova, Jesse Bettencourt, and David Duvenaud. 2019. Neural Ordinary Differential Equations. arXiv:1806.07366 [cs.LG] https: //arxiv.org/abs/1806.07366 [15] Zicun Cong, Xuan Luo, Pei Jian, Feida Zhu, and Yong Zhang. 2021. Data Pricing in Machine Learning Pipelines. arXiv:2108.07915 [cs.LG] https://arxiv.org/abs/ 2108.07915 [16] Victor Costan and Srinivas Devadas. 2016. Intel SGX Explained. IACR Cryptol. ePrint Arch. 2016 (2016), 86. https://api.semanticscholar.org/CorpusID:28642809 [17] Shib Sankar Dasgupta, Swayambhu Nath Ray, and Partha Talukdar. 2018. HyTE: Hyperplane-based Temporally aware Knowledge Graph Embedding. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing (Brussels, Belgium). Association for Computational Linguistics, 2001–2011. http://aclweb.org/anthology/D18-1225 [18] Daniel Demmler, Thomas Schneider, and Michael Zohner. 2015. ABY – A Framework for Efficient Mixed-Protocol Secure Two-Party Computation. In Proceedings of the 2015 Network and Distributed System Security Symposium (NDSS). Internet Society. https://doi.org/10.14722/ndss.2015.23113 [19] Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. 2018. Convolutional 2D knowledge graph embeddings. In Proceedings of the ThirtySecond AAAI Conference on Artificial Intelligence and Thirtieth Innovative Applications of Artificial Intelligence Conference and Eighth AAAI Symposium on Educational Advances in Artificial Intelligence (New Orleans, Louisiana, USA) (AAAI’18/IAAI’18/EAAI’18). AAAI Press, Article 221, 8 pages. [20] J.R. Dormand and P.J. Prince. 1980. A family of embedded Runge-Kutta formulae. J. Comput. Appl. Math. 6, 1 (1980), 19–26. https://doi.org/10.1016/0771-050X(80) 90013-3 [21] Jianzhang Du, Tilak Mudgal, Rutvi Rahul Gadre, Yukui Luo, and Chenghong Wang. 2024. Differentially Private Learned Indexes. arXiv:2410.21164 [cs.DB] https://arxiv.org/abs/2410.21164 [22] David Durfee and Ryan Rogers. 2019. Practical differentially private top-k selection with pay-what-you-get composition. In Proceedings of the 33rd International Conference on Neural Information Processing Systems. Curran Associates Inc., Red Hook, NY, USA, Article 317, 11 pages. [23] Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum. 2010. Differential privacy under continual observation. In Proceedings of the Forty-Second ACM Symposium on Theory of Computing (Cambridge, Massachusetts, USA) (STOC ’10). Association for Computing Machinery, New York, NY, USA, 715–724. https://doi.org/10.1145/1806689.1806787 [24] Cynthia Dwork and Aaron Roth. 2014. The Algorithmic Foundations of Differential Privacy. Vol. 9. Now Publishers Inc., Hanover, MA, USA. 211–407 pages. https: //doi.org/10.1561/0400000042

[25] Vitaly Feldman and Tijana Zrnic. 2022. Individual Privacy Accounting via a Renyi Filter. arXiv:2008.11193 [cs.CR] https://arxiv.org/abs/2008.11193 [26] Raul Castro Fernandez, Pranav Subramaniam, and Michael J. Franklin. 2020. Data market platforms: trading data assets to solve data problems. Proc. VLDB Endow. 13, 12 (July 2020), 1933–1947. https://doi.org/10.14778/3407790.3407800 [27] Amirata Ghorbani, Michael P. Kim, and James Zou. 2020. A distributional framework for data valuation. In Proceedings of the 37th International Conference on Machine Learning (ICML’20). JMLR.org, Article 331, 10 pages. [28] Amirata Ghorbani and James Zou. 2019. Data Shapley: Equitable Valuation of Data for Machine Learning. arXiv:1904.02868 [stat.ML] https://arxiv.org/abs/ 1904.02868 [29] Jennifer Gillenwater, Matthew Joseph, Andrés Muñoz Medina, and Mónica Ribero. 2022. A Joint Exponential Mechanism For Differentially Private Top-𝑘 . arXiv:2201.12333 [cs.CR] https://arxiv.org/abs/2201.12333 [30] Jiale Han, Austin Cheung, Yubai Wei, Zheng Yu, Xusheng Wang, Bing Zhu, and Yi Yang. 2025. RAG Meets Temporal Graphs: Time-Sensitive Modeling and Retrieval for Evolving Knowledge. arXiv:2510.13590 [cs.IR] https://arxiv.org/ abs/2510.13590 Introduction to Online Convex Optimization. [31] Elad Hazan. 2023. arXiv:1909.05207 [cs.LG] https://arxiv.org/abs/1909.05207 [32] Ruoxi Jia, David Dao, Boxin Wang, Frances Ann Hubis, Nick Hynes, Nezihe Merve Gurel, Bo Li, Ce Zhang, Dawn Song, and Costas Spanos. 2023. Towards Efficient Data Valuation Based on the Shapley Value. arXiv:1902.10275 [cs.LG] https: //arxiv.org/abs/1902.10275 [33] Woojeong Jin, Meng Qu, Xisen Jin, and Xiang Ren. 2020. Recurrent Event Network: Autoregressive Structure Inference over Temporal Knowledge Graphs. arXiv:1904.05530 [cs.LG] https://arxiv.org/abs/1904.05530 [34] Alistair E. W. Johnson, Lucas Bulgarelli, Lu Shen, Anne Gayraud, Sipanje Eraslan, Emma Rocheteau, Qinmei Huang, Jidong Cheng, Benjamin Moody, Li-wei H. Lehman, Matthew P. Lungren, Tom J. Pollard, Steven Horng, Leo Anthony Celi, and Roger G. Mark. 2023. MIMIC-IV, a freely accessible electronic health record dataset. Scientific Data 10, 1 (2023), 1. https://doi.org/10.1038/s41597-022-01899-x [35] Shiva Prasad Kasiviswanathan, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. 2013. Analyzing graphs with node differential privacy. In Proceedings of the 10th Theory of Cryptography Conference on Theory of Cryptography (Tokyo, Japan) (TCC’13). Springer-Verlag, Berlin, Heidelberg, 457–476. https://doi.org/ 10.1007/978-3-642-36594-2_26 [36] Jeremias Knoblauch, Jack Jewson, and Theodoros Damoulas. 2018. Doubly robust Bayesian inference for non-stationary streaming data with β-divergences. In Proceedings of the 32nd International Conference on Neural Information Processing Systems (Montréal, Canada) (NIPS’18). Curran Associates Inc., Red Hook, NY, USA, 64–75. [37] Paraschos Koutris, Prasang Upadhyaya, Magdalena Balazinska, Bill Howe, and Dan Suciu. 2015. Query-Based Data Pricing. J. ACM 62, 5, Article 43 (Nov. 2015), 44 pages. https://doi.org/10.1145/2770870 [38] Vlasis Koutsos, Dimitrios Papadopoulos, Dimitris Chatzopoulos, Sasu Tarkoma, and Pan Hui. 2020. Agora: A Privacy-aware Data Marketplace. In 2020 IEEE 40th International Conference on Distributed Computing Systems (ICDCS). 1211–1212. https://doi.org/10.1109/ICDCS47774.2020.00156 [39] Yongchan Kwon and James Zou. 2022. Beta Shapley: a Unified and Noise-reduced Data Valuation Framework for Machine Learning. arXiv:2110.14049 [cs.LG] https://arxiv.org/abs/2110.14049 [40] Julien Leblay and Melisachew Wudage Chekol. 2018. Deriving Validity Time in Knowledge Graph. In Companion Proceedings of the The Web Conference 2018 (Lyon, France) (WWW ’18). International World Wide Web Conferences Steering Committee, Republic and Canton of Geneva, CHE, 1771–1776. https://doi.org/ 10.1145/3184558.3191639 [41] Yehuda Lindell. 2021. Fast Secure Two-Party ECDSA Signing. J. Cryptol. 34, 4 (Oct. 2021), 38. https://doi.org/10.1007/s00145-021-09409-9 [42] Jinfei Liu, Jian Lou, Junxu Liu, Li Xiong, Jian Pei, and Jimeng Sun. 2021. Dealer: an end-to-end model marketplace with differential privacy. Proc. VLDB Endow. 14, 6 (Feb. 2021), 957–969. https://doi.org/10.14778/3447689.3447700 [43] Shige Liu, Zhifang Zeng, Li Chen, Adil Ainihaer, Arun Ramasami, Songting Chen, Yu Xu, Mingxi Wu, and Jianguo Wang. 2025. TigerVector: Supporting Vector Search in Graph Databases for Advanced RAGs. In Companion of the 2025 International Conference on Management of Data (Berlin, Germany) (SIGMOD/PODS ’25). Association for Computing Machinery, New York, NY, USA, 553–565. https://doi.org/10.1145/3722212.3724456 [44] Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, Pieter Abbeel, and Igor Mordatch. 2017. Multi-agent actor-critic for mixed cooperative-competitive environments. In Proceedings of the 31st International Conference on Neural Information Processing Systems (Long Beach, California, USA) (NIPS’17). Curran Associates Inc., Red Hook, NY, USA, 6382–6393. [45] Yu A. Malkov and D. A. Yashunin. 2020. Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs. IEEE Trans. Pattern Anal. Mach. Intell. 42, 4 (April 2020), 824–836. https://doi. org/10.1109/TPAMI.2018.2889473 [46] Ryan McKenna and Daniel Sheldon. 2020. Permute-and-flip: a new mechanism for differentially private selection. In Proceedings of the 34th International Conference

on Neural Information Processing Systems (Vancouver, BC, Canada) (NIPS ’20). Curran Associates Inc., Red Hook, NY, USA, Article 17, 11 pages. [47] Frank McSherry and Kunal Talwar. 2007. Mechanism Design via Differential Privacy. In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS ’07). IEEE Computer Society, USA, 94–103. https: //doi.org/10.1109/FOCS.2007.41 [48] Ilya Mironov. 2017. Rényi Differential Privacy. In 2017 IEEE 30th Computer Security Foundations Symposium (CSF). IEEE, 263–275. https://doi.org/10.1109/ csf.2017.11 [49] Jason Mohoney, Devesh Sarda, Mengze Tang, Shihabur Rahman Chowdhury, Anil Pacaci, Ihab F. Ilyas, Theodoros Rekatsinas, and Shivaram Venkataraman. 2025. Quake: adaptive indexing for vector search. , Article 9 (2025), 17 pages. [50] Pranay Mundra, Charalampos Papamanthou, Julian Shun, and Quanquan C. Liu. 2025. Practical and Accurate Local Edge Differentially Private Graph Algorithms. arXiv:2506.20828 [cs.DS] https://arxiv.org/abs/2506.20828 [51] Gergely Neu. 2015. Explore no more: improved high-probability regret bounds for non-stochastic bandits. In Proceedings of the 29th International Conference on Neural Information Processing Systems - Volume 2 (Montreal, Canada) (NIPS’15). MIT Press, Cambridge, MA, USA, 3168–3176. [52] Gergely Neu. 2015. Explore no more: improved high-probability regret bounds for non-stochastic bandits. In Proceedings of the 29th International Conference on Neural Information Processing Systems - Volume 2 (Montreal, Canada) (NIPS’15). MIT Press, Cambridge, MA, USA, 3168–3176. [53] Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. 2007. Smooth sensitivity and sampling in private data analysis. In Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing (San Diego, California, USA) (STOC ’07). Association for Computing Machinery, New York, NY, USA, 75–84. https: //doi.org/10.1145/1250790.1250803 [54] E. S. PAGE. 1954. CONTINUOUS INSPECTION SCHEMES. Biometrika 41, 1-2 (06 1954), 100–115. https://doi.org/10.1093/biomet/41.1-2.100 arXiv:https://academic.oup.com/biomet/article-pdf/41/1-2/100/1243987/41-1-2100.pdf [55] Christos H. Papadimitriou and John N. Tsitsiklis. 1987. The Complexity of Markov Decision Processes. Math. Oper. Res. 12, 3 (Aug. 1987), 441–450. [56] Christos H. Papadimitriou and John N. Tsitsiklis. 1987. The Complexity of Markov Decision Processes. Math. Oper. Res. 12, 3 (Aug. 1987), 441–450. [57] Liana Patel, Peter Kraft, Carlos Guestrin, and Matei Zaharia. 2024. ACORN: Performant and Predicate-Agnostic Search Over Vector Embeddings and Structured Data. Proc. ACM Manag. Data 2, 3, Article 120 (May 2024), 27 pages. https://doi.org/10.1145/3654923 [58] Ryan Rogers, Aaron Roth, Jonathan Ullman, and Salil Vadhan. 2016. Privacy odometers and filters: pay-as-you-go composition. In Proceedings of the 30th International Conference on Neural Information Processing Systems (Barcelona, Spain) (NIPS’16). Curran Associates Inc., Red Hook, NY, USA, 1929–1937. [59] Gaurav Sehgal and Semih Salihoglu. 2025. NaviX: A Native Vector Index Design for Graph DBMSs With Robust Predicate-Agnostic Search Performance. arXiv:2506.23397 [cs.IR] https://arxiv.org/abs/2506.23397 [60] Lloyd S. Shapley. 1953. A Value for n-Person Games. Princeton University Press, Princeton, NJ. 307–318 pages. https://doi.org/10.1515/9781400881970-018 [61] Aditi Singh, Suhas Jayaram Subramanya, Ravishankar Krishnaswamy, and Harsha Vardhan Simhadri. 2021. FreshDiskANN: A Fast and Accurate GraphBased ANN Index for Streaming Similarity Search. arXiv:2105.09613 [cs.IR] https://arxiv.org/abs/2105.09613 [62] Aristide Tossou and Christos Dimitrakakis. 2015. Algorithms for Differentially Private Multi-Armed Bandits. arXiv:1511.08681 [stat.ML] https://arxiv.org/abs/ 1511.08681 [63] Jiachen T. Wang and Ruoxi Jia. 2023. Data Banzhaf: A Robust Data Valuation Framework for Machine Learning. arXiv:2205.15466 [cs.LG] https://arxiv.org/ abs/2205.15466 [64] Hao Wu and Hanwen Zhang. 2024. Faster differentially private top-k selection: a joint exponential mechanism with pruning. In Proceedings of the 38th International Conference on Neural Information Processing Systems (Vancouver, BC, Canada) (NIPS ’24). Curran Associates Inc., Red Hook, NY, USA, Article 2266, 27 pages. [65] Mengmeng Wu, Ruoxi Jia, Changle Lin, Wei Huang, and Xiangyu Chang. 2023. Variance reduced Shapley value estimation for trustworthy data valuation. Comput. Oper. Res. 159, C (Nov. 2023), 9. https://doi.org/10.1016/j.cor.2023.106305 [66] Yulian Wu, Xingyu Zhou, Youming Tao, and Di Wang. 2023. On private and robust bandits. In Proceedings of the 37th International Conference on Neural Information Processing Systems (New Orleans, LA, USA) (NIPS ’23). Curran Associates Inc., Red Hook, NY, USA, Article 1511, 13 pages. [67] Wentao Xiao, Yueyang Zhan, Rui Xi, Mengshu Hou, and Jianming Liao. 2024. Enhancing HNSW Index for Real-Time Updates: Addressing Unreachable Points and Performance Degradation. arXiv:2407.07871 [cs.IR] https://arxiv.org/abs/ 2407.07871 [68] Da Xu, Chuanwei Ruan, Evren Korpeoglu, Sushant Kumar, and Kannan Achan. 2020. Inductive Representation Learning on Temporal Graphs. 15

arXiv:2002.07962 [cs.LG] https://arxiv.org/abs/2002.07962 [69] Yuming Xu, Hengyu Liang, Jin Li, Shuotao Xu, Qi Chen, Qianxi Zhang, Cheng Li, Ziyue Yang, Fan Yang, Yuqing Yang, Peng Cheng, and Mao Yang. 2023. SPFresh: Incremental In-Place Update for Billion-Scale Vector Search. In Proceedings of the 29th Symposium on Operating Systems Principles (Koblenz, Germany) (SOSP ’23). Association for Computing Machinery, New York, NY, USA, 545–561. https: //doi.org/10.1145/3600006.3613166 [70] Jinfa Yang, Xianghua Ying, Yongjie Shi, and Bowei Xing. 2024. Tensor decompositions for temporal knowledge graph completion with time perspective•. Expert Syst. Appl. 237, PA (March 2024), 12. https://doi.org/10.1016/j.eswa.2023.121267 [71] Yelp. 2026. Yelp Open Dataset. https://www.yelp.com/dataset [72] Quan Yuan, Zhikun Zhang, Linkang Du, Min Chen, Mingyang Sun, Yunjun Gao, Michael Backes, Shibo He, and Jiming Chen. 2025. PSGraph: Differentially Private Streaming Graph Synthesis by Considering Temporal Dynamics.

arXiv:2412.11369 [cs.CR] https://arxiv.org/abs/2412.11369 [73] Qiuchen Zhang, Hong kyu Lee, Jing Ma, Jian Lou, Carl Yang, and Li Xiong. 2024. DPAR: Decoupled Graph Neural Networks with Node-Level Differential Privacy. In Proceedings of the ACM Web Conference 2024 (Singapore, Singapore) (WWW ’24). Association for Computing Machinery, New York, NY, USA, 1170–1181. https://doi.org/10.1145/3589334.3645531 [74] Ziyu Zhang, Yuanhao Wei, Joshua Engels, and Julian Shun. 2025. CleANN: Efficient Full Dynamism in Graph-based Approximate Nearest Neighbor Search. arXiv:2507.19802 [cs.DB] https://arxiv.org/abs/2507.19802 [75] Xiaoyao Zhong, Haotian Li, Jiabao Jin, Mingyu Yang, Deming Chu, Xiangyu Wang, Zhitao Shen, Wei Jia, George Gu, Yi Xie, Xuemin Lin, Heng Tao Shen, Jingkuan Song, and Peng Cheng. 2025. VSAG: An Optimized Search Framework for Graph-Based Approximate Nearest Neighbor Search. , 14 pages. https: //doi.org/10.14778/3750601.3750624

16