Paper deep dive

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

Joydeep Chandra

Year: 2026Venue: arXiv preprintArea: cs.DBType: PreprintEmbeddings: 106

Intelligence

Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 91%

Last extracted: 7/8/2026, 7:38:50 PM

Summary

CHRONOS is a three-layer architecture for temporal knowledge-graph data marketplaces that addresses stale indexing, static valuation misattribution, and uncoordinated differential privacy budget consumption. It integrates a neural-ODE-based temporal index (T-LEGEND), event-conditioned Shapley valuation, and an EXP3-IX multi-agent coordinator to balance recall, latency, and privacy. The system achieves high recall and low latency while enforcing strict differential privacy guarantees under a trusted-curator model, demonstrating scalability to 500 sellers across multiple benchmarks.

Entities (16)

CHRONOS · architecture · 98%Differential Privacy · concept · 95%Event-Conditioned MPV · module · 95%Joydeep Chandra · author · 95%Temporal Coordinator · module · 95%T-LEGEND · module · 95%Tsinghua University · organization · 95%Neural-ODE · technique · 92%EXP3-IX · algorithm · 90%Shapley Valuation · technique · 90%Trusted-Curator Model · trustmodel · 90%BOCPD · technique · 88%Gaussian Mechanism · technique · 88%FB15K-237 · dataset · 85%HNSW · indexstructure · 85%zCDP · framework · 85%

Relation Signals (14)

Joydeep Chandra → affiliatedwith → Tsinghua University

confidence 95% · BNRIST, Tsinghua University

Joydeep Chandra → authored → CHRONOS

confidence 95% · Joydeep Chandra BNRIST, Tsinghua University

Temporal Coordinator → enforces → Differential Privacy

confidence 95% · enforcing epsilon and delta differential privacy via moments accounting

CHRONOS → implements → T-LEGEND

confidence 95% · Layer 1 (T-LEGEND) applies neural-ODE temporal decay to shortcut edges

CHRONOS → implements → Event-Conditioned MPV

confidence 95% · Layer 2 (Event-Conditioned MPV) conditions Shapley valuation on BOCPD-detected changepoints

CHRONOS → implements → Temporal Coordinator

confidence 95% · Layer 3 (Temporal Coordinator) uses EXP3-IX to achieve Big-O of the square root of T log T regret

T-LEGEND → uses → Neural-ODE

confidence 92% · applies neural-ODE temporal decay to shortcut edges

CHRONOS → operatesunder → Trusted-Curator Model

confidence 90% · CHRONOS operates under a trusted-curator model: the marketplace operator holds raw seller data

Cypher Suggestions (0)

No Cypher suggestions yet.

Abstract

Abstract:Temporal knowledge-graph 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 budget. We present CHRONOS, a three-layer architecture providing a unified treatment of these challenges with explicit public and private separation. Layer one applies neural-ODE temporal decay to shortcut edges, providing a per-query expected recall-loss bound of Big-O of Pq lambda delta t, with a monotone-envelope guarantee reducing bound looseness to 1.8 to 3.2 times observed loss. Layer two conditions Shapley valuation on detected changepoints and provides finite-sample error guarantees under noise. Layer three uses EXP3-IX to achieve Big-O of the square root of T log T regret while enforcing epsilon and delta differential privacy via moments accounting. CHRONOS releases a privatized affinity matrix per epoch using the Gaussian mechanism; all retrieval and ranking are post-processing, incurring no extra privacy cost. We provide multi-epoch settlement, scalability analysis for 500 sellers, and comparisons against accelerated baselines. Across four benchmarks, CHRONOS shows 0.937 recall at ten, 2.74 queries per second, 161 ms latency, and total epsilon of 4.25 at delta of 10 to the power of negative 6 under zCDP composition. These results indicate a competitive operating point. A limitation is that at this privacy level, released valuations remain noise-dominated; utility derives primarily from public index routing and adaptive scheduling driven by low-sensitivity statistics.

PDF

Open source PDF →Open local PDF →

Trouble viewing inline? Open PDF directly →

Full Text

105,433 characters extracted from source content.

Expand or collapse full text

CHRONOS: Temporally-Aware Multi-Agent Coordination for Evolving Data Marketplaces Joydeep Chandra BNRIST, Tsinghua UniversityBeijingChina 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 (PqλΔt)O(P_qλ t), 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 (Tlog⁡T)O( T T) regret while enforcing (ϵtotal,δtotal)( _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-k ranking are post-processing, 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ε=4.25 at δ=10−6δ=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: PVLDB, 14(1): X-X, 2020. doi:X.X/X.X †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 info@vldb.org. 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:X.X/X.X PVLDB Artifact Availability: The source code, data, and/or other artifacts have been made available at URL_TO_YOUR_ARTIFACTS. 1. 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 (Malkov and Yashunin, 2020) accelerate k-N 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 (Liu et al., 2025), NaviX (Sehgal and Salihoglu, 2025)) or trigger expensive full rebuilds; dynamic ANN systems (FreshDiskANN (Singh et al., 2021), SPFresh (Xu et al., 2023), Quake (Mohoney et al., 2025)) 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 (Shapley, 1953), yet the canonical Data Shapley (Ghorbani and Zou, 2019) 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 (Kwon and Zou, 2022) improves robustness to noisy data, Variance-Reduced Data Shapley (VRDS) (Wu et al., 2023a) lowers coalition-sampling variance, and GLOC-style online updates (Hazan, 2023) 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 (Lowe et al., 2017) provide no formal coupling between scheduling and DP consumption, and privacy filters (Rogers et al., 2016) track composition but do not integrate with index scheduling or data valuation. PSGraph (Yuan et al., 2025) demonstrates adaptive DP allocation for streaming graphs, but targets graph synthesis rather than marketplace coordination. 1.1. Why These Challenges Must Be Solved Jointly The three challenges are coupled through a shared differential-privacy budget. Index updates, valuation recomputation, and idle waiting all consume from the same finite (ε,δ)( ,δ) allowance. An index-only 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 n, the per-epoch privacy cost falls as n grows, but the total number of active epochs TactiveT_active rises with marketplace activity. The coordinator must therefore balance these competing demands, making the joint design non-decomposable. 1.2. Gap Analysis Prior works address at most one challenge in isolation. In indexing, TigerVector (Liu et al., 2025), NaviX (Sehgal and Salihoglu, 2025), and ACORN (Patel et al., 2024) integrate graph structure into HNSW but assume static graphs. FreshDiskANN (Singh et al., 2021) and SPFresh (Xu et al., 2023) support streaming updates yet omit KG structural decay and recall bounds. In valuation, Data Shapley (Ghorbani and Zou, 2019), Beta Shapley (Kwon and Zou, 2022), and VRDS (Wu et al., 2023a) improve estimation but do not condition on distributional shifts. In marketplace design, existing platforms (Fernandez et al., 2020; Azcoitia and Laoutaris, 2022; Liu et al., 2021; Koutsos et al., 2020) support pricing and DP guarantees yet do not target temporal graph retrieval. Dealer (Liu et al., 2021) 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 (Koutsos et al., 2020) 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 1010–100×100× latency overhead and require all parties to participate in real-time protocols (Demmler et al., 2015; Lindell, 2021); 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. Contributions We present Chronos, a marketplace infrastructure that provides end-to-end temporal guarantees across indexing, valuation, and coordination: (1) T-Legend (§4.1): a temporal hybrid index with neural-ODE decay weights. The conservative bound (Theorem 1) provides an (PqλΔt)O(P_qλ t) recall-loss guarantee; the new monotone-envelope certificate (Theorem 2) tightens the gap to 1.81.8–3.2×3.2× observed losses by incorporating ODE Lipschitz structure. Formal Hawkes-process recall bounds (Theorem 3) 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 5), and estimation error bounds under finite sampling, DP noise, and changepoint uncertainty (Theorem 6). (3) Temporal Coordinator (§4.3): an EXP3-IX meta-agent achieving (Tlog⁡T)O( T T) regret (Theorem 9) while enforcing adaptive DP composition with formal sensitivity proofs (Proposition 7). (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 7(b)); standard additive zCDP composition over ρ yielding ε=4.25 =4.25 (Remark 6); transparent analysis of private-signal informativeness (§6); per-entry noise calibration with dimension-aware sensitivity (Proposition 4). (5) Actionable Seller Settlement (§6.3): a concrete multi-epoch coalition-level settlement mechanism with SNR analysis showing trend-level attribution becomes feasible at W≥7W≥7 epochs and ncoal≤5n_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. 2. Preliminaries Definition 0 (Temporal Knowledge Graph). A temporal KG is a triple (t)=(V(t),E(t),(t))G(t)=(V(t),E(t),X(t)) where V(t)V(t) and E(t)E(t) are node and edge sets at time t, (t)∈ℝ|V(t)|×dX(t) ^|V(t)|× d is the node feature matrix, and each edge e=(u,v,r)∈E(t)e=(u,v,r)∈ E(t) carries relation type r and creation timestamp te≤t_e≤ t. Definition 0 (Temporally-Aware Data Marketplace). A marketplace ℳM with n sellers s1,…,sn\s_1,…,s_n\ holding private datasets Di⊆(t)D_i (t) must satisfy, for online buyer queries with vector jv_j, recency window [tjmin,tjmax][t_j ,t_j ], and budget εj _j: (P1) recall@k≥R∗−δindexk≥ R^*- _index; (P2) Shapley efficiency with temporal consistency; (P3) (εtotal,δtotal)( _total, _total)-DP; (P4) sub-linear regret RT=o(T)R_T=o(T) with per-query latency ≤Lmax≤ L_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β≤ 0.5), where <6%<6\% of oracle top-10 items fall outside the public candidate set (Table 16); for high-β (β>0.7β>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 3. Assumption 1 (Poisson Edge Changes). KG edge changes arrive as an independent Poisson process with rate λ>0λ>0 (changes per day per shortcut). We estimate λ via exponential moving average over a 30-day calibration window: λ=0.05λ=0.05 for FB15K-237/WN18R (synthetic), λ≈12λ≈12 for MIMIC-IV (real admissions), λ≈2.9λ≈2.9 for Yelp (real review activity). Table 1. Key notation. Symbol Meaning (t)G(t), λ, Δt t Temporal KG, edge-change rate, time since update R∗R^*, PqP_q, Δr¯ r Fresh recall, search-path size, per-shortcut impact R^(t) R(t) DP-estimated noisy recall (observed proxy for R∗R^*) (t)A(t) Private affinity matrix ∈[0,1]|Vactive|×ef∈[0,1]^|V_active|× ef ~(t) A(t) Gaussian-noised release of (t)A(t) MPVi(t,E)MPV_i(t,E) EC-MPV of seller i at time t, event E B Marginal contribution bound (clipped at 0.2) σt _t Noise multiplier (dimensionless); actual std =σt×S= _t× S TactiveT_active Number of epochs with ≥1≥ 1 DP release εrem(t) _rem(t), μt(α) _t(α) Remaining DP budget, Rényi moment at step t tp_t, d=3d=3, γ EXP3-IX distribution, action count, exploration γcomm _comm Community-structure weight in static affinity (default 0.5) αH,βH _H, _H Hawkes excitation/decay parameters Λ(t1,t2) (t_1,t_2) Cumulative intensity ∫t1t2λ(s)s _t_1^t_2λ(s)\,ds Noise notation convention. σt _t is a dimensionless noise multiplier; actual Gaussian std for a quantity with ℓ2 _2-sensitivity S is σt×S _t× S. The per-step Rényi moment is μt(α)=α/(2σt2) _t(α)=α/(2 _t^2) (Proposition 4). The total ε=4.25 =4.25 (δ=10−6δ=10^-6) is computed by standard additive zCDP composition over ρ: (1) ρtotal=∑iρi,ε=ρtotal+2ρtotal⋅ln⁡(1/δ). _total= _i _i, = _total+2 _total· (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 trusted-curator model (Dwork and Roth, 2014): the marketplace operator holds raw seller data and publishes only DP-sanitised outputs. We partition all system components explicitly. Public data (not seller-dependent, zero DP cost). (1) Entity embeddings 0∈ℝ|V0|×dX_0 ^|V_0|× d: 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 TH^T: built deterministically from 0X_0 and the Louvain community partition (Blondel et al., 2008) of the public pre-marketplace KG. The neighbourhood lists Nidx(u)=u1,…,uefN_idx(u)=\u_1,…,u_ef\ are fixed at construction time and are deterministic functions of 0X_0. After construction, TH^T is frozen within each epoch. (3) Edge creation timestamps from public pre-marketplace KG: timestamps tet_e for edges in EpubE_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 qv_q: owned by the buyer, not seller data. Private data (seller-dependent, protected by DP). (1) Seller KG edges: edges contributed by sellers after marketplace launch, including their timestamps teprivt_e^priv. These determine the temporal affinity values affKG(u,v,t)aff_KG(u,v,t) and are the primary target of DP protection. (2) Valuation scores MPVi(t,E)MPV_i(t,E): 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. Seller-contributed edge timestamps (months 7+) are private. The Stage-2 active-scope clipping (§4.4) operates as follows. The set of active entities Vactive(t)V_active(t) is determined by buyer queries from epoch t−1t-1 plus a popularity reserve, both computed from public query logs. The universe of possible edges within VactiveV_active is public: it is the set of all tuples (u,v,r)(u,v,r) with u,v∈Vactiveu,v∈ V_active and r∈ℛ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(u,v,r)hash(u,v,r) computed over the full public universe. The mechanism retains, for each seller, the intersection of their private edge set with the first κactive _active tuples in this public ordering. Private timestamps teprivt_e^priv are used only inside the Gaussian mechanism’s input (to compute affKG(u,v,t)=decay(tnow−tepriv)⋅affstatic(u,v)aff_KG(u,v,t)=decay(t_now-t_e^priv)·aff_static(u,v)), never for clipping or scoping decisions. The clipping boundary κactive _active depends only on |E|/n|E|/n (public) and |Vactive||V_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) applied to the affinity matrix after clipping. The released matrix ~(t) A(t) has public row and column indices; each entry contains additive Gaussian noise with standard deviation σentry=885 _entry=885. Because the noise magnitude far exceeds the [0,1][0,1] signal range, an adversary observing ~(t) A(t) cannot reliably infer whether a particular entry’s true value is zero (edge absent) or non-zero (edge present). Formally, for any entry a∈[0,1]a∈[0,1] and any hypothesised value a′∈[0,1]a ∈[0,1], the likelihood ratio of the observed noisy value under a versus a′a is bounded by exp⁡(εentry) ( _entry) with εentry≈0.0011 _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 (u,v,r)(u,v,r) has a unique owner under a hash-based deduplication registry, ensuring unambiguous sensitivity accounting. For multi-relation graphs, affKG(u,v,t)=maxr⁡affKG(r)aff_KG(u,v,t)= _raff_KG^(r) means removing one seller changes the max by ≤1≤ 1 per (u,v)(u,v) pair. Pre-registry empirical overlap ηraw≤1.07 _raw≤1.07 across all datasets confirms near-exclusive ownership (supplementary Table B2). If disputed ownership persists, privacy cost scales approximately with η2η^2 (Remark 3), and arbitration/registry enforcement is required before deployment. DP-SGD training (Abadi et al., 2016) of embeddings is feasible at additional εtrain _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. (i) Local DP: each seller randomises their own edges locally before upload, removing the central curator at the cost of Ω(1/ε2) (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 qv_q as public (standard in trusted-curator DP). If queries are sensitive, the continual-observation framework (Dwork et al., 2010; Chan et al., 2011) with a count-min sketch can privately estimate VactiveV_active at εquery≈0.5 _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β=0.3, <6%<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%52\% of misses at +0.05ε+0.05\, . Figure 1 summarises this public/private separation and the resulting trusted-curator data path. 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, producing ~(t) A(t) for hybrid scoring. 4. 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. Per-operation complexity. N=|V|N=|V|, M=16M=16, ef=128ef=128, Lmax=5L_max=5, n=n=#sellers, m=m=#permutations, T=T=horizon, |Vactive|≤1500|V_active|≤1500. Operation Time Space Frequency Comments Index construction O(Nlog⁡N⋅M)O(N N· M) O(N⋅M)O(N· M) Once Public data only Incremental update O(|Vactive|log⁡N)O(|V_active| N) O(|Vactive|)O(|V_active|) Per epoch Stale-shortcut repair Query processing O(ef⋅Lmax)O(ef· L_max) O(ef)O(ef) Per query Post-processing, zero DP cost Valuation recompute O(m⋅n2⋅|Q|)O(m· n^2·|Q|) O(n)O(n) Per event VRDS reduces variance DP release (affinity) O(|Vactive|⋅ef)O(|V_active|· ef) O(|Vactive|⋅ef)O(|V_active|· ef) Per active epoch Gaussian sampling dominates DP release (stats) O(1)O(1) O(1)O(1) Per active epoch Scalar Gaussian Coordinator decision O(d)O(d) O(d)O(d) Per epoch EXP3-IX update 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 VactiveV_active. Query processing is constant in dataset size because HNSW search is O(log⁡N)O( N) and the per-query hybrid score is post-processing. The dominant online cost is valuation recomputation (O(mn2|Q|)O(mn^2|Q|)), which is why EC-MPV batches it at changepoints rather than every epoch. The DP release cost is linear in the active-scope size and is amortised over all queries in the epoch. Figure 2. Chronos architecture. 4.1. Layer 1: T-LEGEND (Temporal Hybrid Index) 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 0 (Neural ODE Temporal Decay). For edge e with age Δt=tnow−te t=t_now-t_e, the decay function decay:ℝ≥0→(0,1]decay:R_≥ 0→(0,1] is the first component of the ODE solution: (2) ddΔt=fθ((Δt),Δt),(0)=32,decay(Δt)=σ([(Δt)]1), dhd t=f_θ(h( t), t), (0)=1_32, ( t)=σ([h( t)]_1), where fθ:ℝ32×ℝ→ℝ32f_θ:R^32×R ^32 is a two-hidden-layer MLP with Softplus activations (Chen et al., 2019) and σ is the sigmoid. We train fθf_θ on historical KG snapshots using contrastive temporal loss: (3) ℒODE=−∑(e,Δt)∈+log⁡decay(Δt)−∑(e,Δt)∈−log⁡(1−decay(Δt)),L_ODE=- _(e, t) ^+ \,decay( t)- _(e, t) ^- (1-decay( t)), with 3:1 negative sampling, strict temporal splitting (months 1–6 train, 7–8 val, 9–12 test), Adam optimiser (lr=10−3lr=10^-3), and Dormand–Prince solver (Dormand and Prince, 1980). Training converges in ∼50 50 epochs (∼20 20 min on one A100). Neural-ODE diagnostics. Domain-specific decay shapes, solver-tolerance robustness, hidden-size ablations (h∈16,32,64h∈\16,32,64\; h=32h=32 optimal), and generalisation to unseen rates (λ=25λ=25) are in supplementary Appendix F. The temporal affinity between nodes is affKG(v,u,t)=decay(t−te)⋅affstatic(v,u)aff_KG(v,u,t)=decay(t-t_e)·aff_static(v,u) where the static component uses community-structure proximity (Blondel et al., 2008) (γcomm=0.5 _comm=0.5). Index construction and public/private separation. Algorithm 1 uses only public pre-marketplace data (months 1–6): Nidx(u)N_idx(u) is a deterministic function of public data only, ensuring seller-dependent affinities enter only at query time via the private (t)A(t) matrix (§4.4). Algorithm 1 inserts nodes in community-sorted order using hybrid score sTs_T with a diversified-neighbor selection heuristic; parameters M=16M=16, efc=200ef_c=200, ef=128ef=128, ρdiv=0.7 _div=0.7 are identical for all baselines (Table 7). Stale-shortcut detection triggers incremental updates when <40%<40\% of shortcuts are stale (restoring ≥95%≥ 95\% fresh recall at ≤20%≤ 20\% cost), with full rebuilds at higher staleness rates. Algorithm 1 T-LEGEND-BUILD (Public-Only Construction) 1:Public KG pub(t)G_pub(t) (pre-marketplace), ODE model fθf_θ, params (M,efc,mL)(M,ef_c,m_L) 2:T-LEGEND index TH^T with fixed neighbourhoods Nidx(u)N_idx(u) 3:←LOUVAIN(pub(t))C (G_pub(t)) ⊳ public community structure 4:for (u,v,te)∈Epub(t)(u,v,t_e)∈ E_pub(t) do ⊳ public edges only wuv←decay(tnow−te)⋅affstatic(u,v)w_uv (t_now-t_e)·aff_static(u,v) 5:end for 6:for each v∈Vv∈ V (community-sorted) do 7: Draw ℓv∼Geom(1−1/mL) _v (1-1/m_L); bias up for hubs 8: for ℓ=ℓv = _v downto 0 do 9: W←SEARCH-LAYER(T,v,ℓ,efc)W -LAYER(H^T,e_v, ,ef_c) 10: for u∈Wu∈ W do sT(u)←(1−β)sim(v,u)+βwuvs_T(u)←(1-β)\,sim(e_v,e_u)+β\,w_uv ⊳ public weights only 11: end for 12: N∗(v,ℓ)←TOP-M-DIVERSE(W,sT,ρdiv)N^*(v, ) -M -DIVERSE(W,s_T, _div) 13: Add (v,u):u∈N∗(v,ℓ)\(v,u):u∈ N^*(v, )\ to layer ℓ 14: end for 15: Record Nidx(v)←⋃ℓN∗(v,ℓ)N_idx(v)← _ N^*(v, ) ⊳ fixed, public 16:end for Remark 1 (Role of Temporal Decay vs. Private Edges). The ODE decay applies to public shortcut edges; private seller edges never enter Nidx(u)N_idx(u) and influence only the epoch-level ~(t) A(t) release. The ODE keeps the candidate set fresh; ~(t) A(t) keeps ranking within that set fresh. 4.2. Layer 2: Event-Conditioned MPV Real-world events alter dataset marginal values in ways that static Shapley misses (Ghorbani and Zou, 2019). EC-MPV addresses this by conditioning on detected distributional changepoints. Definition 0 (Temporal KG Affinity). The temporal affinity affKG(u,v,t)=decay(t−te)⋅affstatic(u,v)aff_KG(u,v,t)=decay(t-t_e)·aff_static(u,v) where tet_e is the creation timestamp and affstatic(u,v)∈[0,1]aff_static(u,v)∈[0,1] is Louvain community-structure proximity (Blondel et al., 2008). For multi-relation graphs, we take the maximum over relation types. Definition 0 (Event-Conditioned MPV). Let E be an event detected at time t by BOCPD. The EC-MPV of seller i is MPVi(t,E)=ϕi(Dpriv∪Dpub∣E,t)−ϕ(Dpub∣E,t)MPV_i(t,E)= _i(D_priv∪ D_pub E,t)-φ(D_pub E,t) where v(S;E)=MRR(q,⋃j∈SDj,E)v(S;E)=MRR(q, _j∈ SD_j,E) is conditioned on event E. The marginal contribution bound B in Assumption 3 is enforced by clipping to [−B,B][-B,B] with B=0.2B=0.2 (<0.3%<0.3\% of marginals exceed 0.2 before clipping). The BOCPD module (Adams and MacKay, 2007) monitors query-embedding drift, λ^(t) λ(t), and valuation residuals via a Normal-Inverse-Wishart conjugate prior with geometric hazard πcp=1/250 _cp=1/250. Changepoints are declared at P(rt=0∣1:t)>0.85P(r_t=0 _1:t)>0.85; median detection delay 2.3 epochs (P95: 5.1) on 8 injected Yelp seasonal events. For Shapley estimation we use permutation sampling (Castro et al., 2009) (m=1,000m=1,000) with VRDS control variates (Wu et al., 2023a): leave-one-out baselines reduce variance to ≤B2ρ2/m≤ B^2ρ^2/m, giving 1.8×1.8× reduction on Yelp at zero DP cost. 4.3. Layer 3: Temporal Coordinator Agent The coordinator operates as a partially observable stochastic game Γ with state t=(λ^t,R^t,εrem(t),npending(t),Eactive)s_t=( λ_t, R_t, _rem(t),n_pending(t),E_active), action space =INDEX-UPDATE,REVALUE,NULLA=\INDEX -UPDATE,REVALUE,NULL\ (d=3d=3), and reward R(,)=QPS+μRR^−νεconsumedR(s,a)=QPS+ _R R-ν\, _consumed with μR=10 _R=10, ν=5ν=5 (grid-searched on FB15K-237 validation; sensitivity analysis in §7.4), normalised to [0,1][0,1]. Rather than solving this PSPACE-hard problem exactly (Papadimitriou and Tsitsiklis, 1987a), the coordinator applies EXP3-IX (Neu, 2015a) under bandit feedback. Each 60 s epoch: observe noisy state to_t; sample t∼ta_t _t; observe rtr_t; update via importance-weighted loss L^t,j=(1−rt)[t=j]/(pt,j+γ) L_t,j=(1-r_t) 1[a_t=j]/(p_t,j+γ). Budget-violating actions are overridden to NULL; recall violations to INDEX-UPDATE (override count bounded; Lemma 8). Remaining budget: εrem(t)=minα⁡[(εtotal−∑s≤tμs(α)+αln⁡(1/δtotal))/α] _rem(t)= _α[( _total- _s≤ t _s(α)+α (1/ _total))/α]. 4.4. 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 DiD_i. To bound sensitivity robustly, we enforce per-seller contribution caps Cmaxedge=⌈1.5|E|/n⌉C_max^edge= 1.5|E|/n ; excess edges are clipped. Three categories of seller-dependent outputs are privatised, with sensitivity bounds proven in Proposition 7: (i) Valuation scores. Each MPVi(t,E)MPV_i(t,E) is released via n independent per-coordinate Gaussian mechanisms with sensitivity Sval=4B/n=0.08S_val=4B/n=0.08 (B=0.2B=0.2, n=10n=10; Proposition 7(a)). With σt=50 _t=50, actual noise std is 50×0.08=4.050×0.08=4.0 per coordinate. The ρval=287/5000=0.0574 _val=287/5000=0.0574 contributes to the total zCDP ρ. Remark 2 (Valuation DP: External Release vs. Internal Coordinator Use). The noise std of 4.04.0 far exceeds the signal range [0,B=0.2][0,B=0.2] by 20×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=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. (i) Index statistics. The stale-shortcut fraction and recall estimate R R are released with Gaussian noise calibrated to sensitivity Sidx≤1.5/nS_idx≤ 1.5/n with σt=50 _t=50. (i) KG affinity matrix (fixed dimension). We release (t)[u,j]=affKG(u,Nidx(u)[j],t)A(t)[u,j]=aff_KG(u,N_idx(u)[j],t) for u∈Vactiveu∈ V_active, j=1,…,efj=1,…,ef. Row and column indices are public and fixed by the public index TH^T. Under exclusive ownership, Frobenius sensitivity Δ2=Cmaxedge _2= C_max^edge (Proposition 7(b)). Remark 3 (Robustness to Imperfect Exclusive Ownership). Let η≥1η≥ 1 be the overlap factor. Sensitivity scales to Δ2≤ηCmaxedge _2≤η C_max^edge, raising ε by η2η^2: η=1.2η=1.2 adds ≤44%≤ 44\%; the registry enforces η=1η=1 deterministically; empirically ηraw≤1.07 _raw≤ 1.07. We release ~(t)=(t)+ A(t)=A(t)+Z via the Gaussian mechanism (Proposition 4); entries are clipped to [0,1][0,1] post-noise (post-processing, zero DP cost). Per-query hybrid scoring s~j=(1−β)cos⁡(q,uj)+β~(t)[vq,j] s_j=(1-β) (v_q,e_u_j)+β A(t)[v_q,j] is also post-processing, so top-k selection incurs zero additional DP cost (Dwork and Roth, 2014). 4.4.1. Per-Entry Noise Calibration Proposition 4 (Per-Entry Gaussian Noise Calibration). Let ∈ℝnr×ncA ^n_r× n_c have Frobenius (ℓ2 _2) sensitivity Δ2=maxD∼D′⁡‖(D)−(D′)‖F _2= _D D \|A(D)-A(D )\|_F. The Gaussian mechanism ~=+ A=A+Z with Zi,j∼iid(0,σentry2)Z_i,j N(0, _entry^2) satisfies (α,αΔ22/(2σentry2))(α,α _2^2/(2 _entry^2))-RDP by the standard vector Gaussian mechanism (Mironov, 2017). Setting σentry=σt⋅Δ2 _entry= _t· _2 (noise multiplier σt=σentry/Δ2 _t= _entry/ _2) yields: (4) μt(α)=αΔ222σentry2=αΔ222σt2Δ22=α2σt2. _t(α)= α _2^22 _entry^2= α _2^22 _t^2 _2^2= α2 _t^2. The standard RDP formula uses per-coordinate variance σentry2 _entry^2; using a global variance σglobal2=nrnc⋅σentry2 _global^2=n_rn_c· _entry^2 in the denominator would underestimate ε by a factor of m=nrncm=n_rn_c. Proof. Direct substitution into Mironov (Mironov, 2017) Proposition 3; see supplementary Appendix A. ∎ Per-epoch active-scope sensitivity. Before each Gaussian invocation, two deterministic clips apply. Stage 1: seller edge count clipped to Cmaxedge=⌈1.5|E|/n⌉C_max^edge= 1.5|E|/n globally. Stage 2: within Vactive(t)V_active(t), a seller’s edges are retained by a publicly computable, data-independent priority rule: hash(u,v,r)hash(u,v,r) ordering (public edge metadata only, independent of private affinity values, timestamps, or seller identity). Edges beyond κactive(t)=min⁡(Cmaxedge,⌈1.5|Eactive(t)|/n⌉) _active(t)= (C_max^edge, 1.5|E_active(t)|/n ) are dropped. Under this rule, the post-clip matrices satisfy ‖(D)−(D′)‖F≤κactive\|A(D)-A(D )\|_F≤ _active for any adjacent D∼D′D D , giving worst-case Δ2=κactive _2= _active. On Yelp this reduces Δ2 _2 by 30.1×30.1× (545→ 18.1). 4.4.2. Release Policy and Active/Null Epoch Classification An active epoch is one where the coordinator chose INDEX-UPDATE or REVALUE, or ≥ 1 buyer query arrived; ~(t) A(t) is released once via the Gaussian mechanism. A null epoch incurs zero DP cost. Budget breakdown via parallel zCDP composition: ρidx=0.0846 _idx=0.0846, ρval=0.0574 _val=0.0574, ρaff=0.142 _aff=0.142; total ρtotal=0.284 _total=0.284, yielding (using Eq. (1)): (5) ε=0.284+20.284×ln⁡(106)=0.284+20.284×13.816=4.25. =0.284+2 0.284× (10^6)=0.284+2 0.284× 13.816=4.25. Remark 4 (Within-Epoch Serving Timeline and P50 Latency). Vactive(t)V_active(t) is the look-back set (entities queried in epoch t−1t-1 plus 500-entity popularity reserve, zero DP cost); ~(t) A(t) releases in 18.4 ms off the query critical path. Per-query lookup is 0.3 ms post-processing; in the serving-path trace P50= 158\,=\,158 ms (no privatisation overhead), while the end-to-end benchmark reports 161 ms (Table 11). Remark 5 (Epoch Classification is Post-Processing). The coordinator’s decision rule πt _t operates only on DP-released quantities from prior epochs; by the post-processing theorem (Dwork and Roth, 2014), active/null classification incurs zero additional privacy cost. TactiveT_active is a stopping time; the privacy odometer framework (Rogers et al., 2016) accounts for the realised active-epoch sequence only. Worst-case (T=2,160T=2,160 all-active): ε≈8.47 ≈8.47 via zCDP, confirming adaptive stopping does not amplify risk unboundedly. Table 3. Per-mechanism noise parameters. σt=50 _t=50 uniformly. Rényi moment: μtRDP(α)=α/(2σt2)=α/5000 _t^RDP(α)=α/(2 _t^2)=α/5000. zCDP uses additive composition over ρ: sum ρi=Ti/(2×502) _i=T_i/(2×50^2) first, then convert via Eq. (1). Mechanism Active S _t Actual std (=) _t^RDP(α=18) _i epochs Index stats 423 0.015 50 0.750 3.60×10−33.60×10^-3 0.0846 Valuation 287 0.080 50 4.000 3.60×10−33.60×10^-3 0.0574 KG affinity 710 † 50 885‡ 3.60×10−33.60×10^-3 0.142 Total ρtotal= _total= 0.284 Total (ε,δ)( ,δ)-DP: ε=0.284+20.284×13.816=4.25 =0.284+2 0.284× 13.816=4.25 Remark 6 (zCDP Accounting Cross-Check). Direct summation of per-mechanism (ε,δ)( ,δ)-DP values would yield ε=7.03 =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 _total=0.0846+0.0574+0.142=0.284, giving ε=4.25 =4.25 via Eq. (1). Cross-check: GDP (μtotal=1420/50=0.753 _total= 1420/50=0.753) gives εGDP≈4.24 _GDP≈4.24; PLD accountant (using Google’s dp_accounting library, T=1420T=1420 compositions at σt=50 _t=50) gives εPLD=4.247 _PLD=4.247. RDP, zCDP, GDP, and PLD all agree within 1% at σt=50 _t=50. PLD accountant transcript logs (per-epoch ρi _i and cumulative ε ) are included in the supplementary code repository. Table 3 provides the per-mechanism accounting terms and noise scales used by this composition. 4.5. Alternative DP Design: Exponential Mechanism for Top-k The CHRONOS design releases the full affinity matrix ~(t) A(t) once per epoch, making per-query top-k selection post-processing with zero marginal privacy cost. An alternative is to release only the top-k candidate identities via the exponential mechanism (McSherry and Talwar, 2007) or its joint variant (Gillenwater et al., 2022; Wu and Zhang, 2024). Under this design, the mechanism’s output space is the set of ordered k-tuples of candidates, and the utility function is the hybrid score sjs_j. The exponential mechanism satisfies ε -DP with sensitivity Δu=β u=β (since one seller changes one affinity by at most 1, and the hybrid score weights it by β). Trade-off analysis. Releasing top-k identities directly avoids the O(|Vactive|⋅ef)O(|V_active|· ef) matrix noise, but incurs three costs: (1) Sampling cost: the joint exponential mechanism over dΘ(k)d (k) sequences requires O(dklog⁡k+dlog⁡d)O(dk k+d d) time (Gillenwater et al., 2022), or O(d+k2/ε⋅ln⁡d)O(d+k^2/ · d) with recent pruning (Wu and Zhang, 2024), which is still 1010–100×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×100× higher unless each query uses ε/100 /100, yielding near-random selections. (3) Rank consistency: repeated independent exponential-mechanism draws can return inconsistent top-k 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 k≪efk ef and query rates are very low (<∼1< 1/epoch). 4.6. Three-Layer Integration The layers couple through shared DP-released state: recall drops trigger index updates trading ε for R R; BOCPD changepoints batch EC-MPV and index updates to amortise cost; the adaptive schedule σt=σ0Tactive/t _t= _0 T_active/t concentrates noise in early epochs. 5. Theoretical Analysis We state four assumptions and prove nine results (seven theorems, two propositions, one lemma). Assumption 2 (Bounded Per-Query Recall Impact). For query q, let Pq≤ef⋅LmaxP_q≤ ef· L_max be the number of on-path shortcut edges. Each stale on-path shortcut at layer ℓ reduces recall by at most Δr¯(ℓ)>0 r^( )>0. Assumption 3 (Smooth Coalition Value). v:2→ℝv:2^N is monotone with |v(S∪i)−v(S)|≤B=0.2|v(S∪\i\)-v(S)|≤ B=0.2 for all S,iS,i, enforced by clipping. Assumption 4 (Bounded Lipschitz Losses). Lt()=1−R(t,)∈[0,1]L_t(a)=1-R(o_t,a)∈[0,1] and is G-Lipschitz in to_t. Assumption 5 (ODE Lipschitz Regularity). The trained neural ODE fθf_θ is LθL_θ-Lipschitz in h, and the decay function decay(Δt)=σ([(Δt)]1)decay( t)=σ([h( t)]_1) is monotonically non-increasing with Lipschitz constant Kdecay≤Lθ/(4βH)K_decay≤ L_θ/(4 _H) verified numerically on the validation set. We validate Assumptions 2–5 empirically via leave-one-out on-path removal and ODE trajectory analysis on the validation set; Table 4 provides instantiations. Table 4. Per-query recall bound instantiation at Δt=7 t=7 days. “Tight” refers to the monotone-envelope bound (Theorem 2). Dataset PqP_q Δr¯max r_max λ Conserv. Tight Obs. Ratio FB15K-237 1408 5.1×10−45.1×10^-4 0.05 0.251 0.044 0.014 3.1× WN18R 1792 3.8×10−43.8×10^-4 0.05 0.238 0.035 0.011 3.2× MIMIC-IV 2176 4.3×10−44.3×10^-4 12.0 0.936 0.170 0.094 1.8× Yelp 2240 3.9×10−43.9×10^-4 2.9 0.874 0.128 0.050 2.6× Ratio = Tight bound / Observed loss. Conservative bound uses Theorem 1; Tight bound uses Theorem 2. Theorem 1 (Per-Query Temporal Recall Bound (Conservative)). Under Assumptions 1–2, for query q with search path path(q)path(q): (6) [recall@k(Δt)∣q]≥R∗−∑e∈path(q)Δr¯(ℓe)(1−e−λeΔt).E[recall@k( t) q]≥ R^*- _e (q) r^( _e) (1-e^- _e t ). Under the homogeneous model: [recall@k∣q]≥R∗−PqΔr¯(1−e−λΔt)=R∗−(PqλΔt)E[recall@k q]≥ R^*-P_q r (1-e^-λ t )=R^*-O(P_qλ t). Proof. By linearity of expectation over independent Poisson stale events on each on-path shortcut; see supplementary Appendix A. ∎ Theorem 2 (Tightened ODE-Certified Recall Bound (Monotone Envelope)). Under Assumptions 1–5, define the monotone envelope decay¯(Δt)=infs∈[0,Δt]decay(s) decay( t)= _s∈[0, t]decay(s). Then: (7) [recall@k(Δt)∣q]≥R∗−∑e∈path(q)Δr¯(ℓe)(1−e−λeΔt)⋅decay¯(Δt).E[recall@k( t) q]≥ R^*- _e (q) r^( _e) (1-e^- _e t )· decay( t). The multiplicative factor decay¯(Δt)≤1 decay( t)≤ 1 is computed from the trained ODE with the following certification: under Assumption 5, the Grönwall inequality gives |decay(Δt)−decay^(Δt)|≤ϵsolvereLθΔt|decay( t)- decay( t)|≤ _solver\,e^L_θ t where ϵsolver _solver is the adaptive solver tolerance (set to 10−510^-5). The certified lower bound is: (8) decay¯cert(Δt)=max⁡(0,decay¯(Δt)−ϵsolvereLθΔt). decay_cert( t)= \! (0,\; decay( t)- _solver\,e^L_θ t ). 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 non-increasing (Assumption 5), we use decay¯ decay as a certified envelope. Formally: the effective recall impact of a stale shortcut e at age Δt t is Δr¯(ℓe)⋅pstale(e,Δt)⋅weffective(e,Δt) r^( _e)· p_stale(e, t)· w_effective(e, t), where pstale(e,Δt)=1−e−λeΔtp_stale(e, t)=1-e^- _e t and weffective(e,Δt)≤decay¯(Δt)w_effective(e, t)≤ decay( t) because: (i) the index uses decay-weighted scores for routing, so stale shortcuts with low decay weights are less likely to be traversed; (i) the monotone envelope ensures the bound holds even if the ODE exhibits transient non-monotonicity. The Grönwall bound on ODE solver error provides the certified margin ϵsolvereLθΔt _solver\,e^L_θ t, which is <0.003<0.003 for Δt≤90 t≤ 90 days at Lθ=0.8L_θ=0.8 (measured). See supplementary Appendix A. ∎ Tightness analysis. On Yelp at Δt=7 t=7 days: decay¯cert(7)=0.714 decay_cert(7)=0.714 (trained ODE, minus solver margin 0.0030.003), yielding tight bound PqΔr¯(1−e−λΔt)⋅0.714=2240×3.9×10−4×0.999×0.714=0.128P_q r (1-e^-λ t )· 0.714=2240× 3.9×10^-4× 0.999× 0.714=0.128 vs. observed 0.0500.050 (ratio 2.6×2.6×). At 30 days: decay¯cert(30)=0.299 decay_cert(30)=0.299, yielding tight bound 0.2650.265 vs. observed 0.1070.107 (ratio 2.5×2.5×). The remaining gap is due to path-independence assumptions at hub nodes, where correlations reduce effective PqP_q. The monotone-envelope bound reduces the looseness from 55–10×10× (Theorem 1) to 1.81.8–3.2×3.2× (Table 4). Theorem 3 (Hawkes-Process Recall Bound). Let edge changes follow an inhomogeneous Hawkes process with baseline intensity μH _H, excitation kernel g(t)=αHe−βHtg(t)= _He^- _Ht (αH,βH>0 _H, _H>0), and branching ratio ξ=αH/βH<1ξ= _H/ _H<1 (stability condition). Define the cumulative compensator ΛH(0,Δt)=[∫0Δtλ(s)s]=μHΔt1−ξ _H(0, t)=E\! [ _0 tλ(s)\,ds ]= _H t1-ξ. Then: (9) [recall@k(Δt)∣q]≥R∗−PqΔr¯μHΔt1−ξ.E[recall@k( t) q]≥ R^*- P_q r\, _H t1-ξ. More precisely, with the monotone-envelope certificate: (10) [recall@k(Δt)∣q]≥R∗−PqΔr¯μHΔt1−ξ⋅decay¯cert(Δt).E[recall@k( t) q]≥ R^*- P_q r\, _H t1-ξ· decay_cert( t). The high-probability bound (Corollary 4) further accounts for Hawkes-induced temporal clustering. Proof. Under Hawkes dynamics, the stale probability for each shortcut becomes Pr⁡[stale in [0,Δt]]≤1−e−ΛH(0,Δt) [stale in [0, t]]≤ 1-e^- _H(0, t) by the compensator inequality. For a stable Hawkes process, ΛH(0,Δt)=μHΔt/(1−ξ) _H(0, t)= _H t/(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 h have correlated change events, but the total layer-ℓ contribution is bounded by |Nℓ(h)|⋅Δr¯(ℓ)⋅ΛH(ℓ)(0,Δt)|N_ (h)|· r^( )· _H^( )(0, t) where ΛH(ℓ) _H^( ) accounts for the hub’s Hawkes rate. Summing over layers and applying the monotone-envelope certificate yields the result. See supplementary Appendix A. ∎ Corollary 4 (High-Probability Bound Under Hawkes). Under the Hawkes model, with the spectral radius bound on the Hawkes covariance (Bacry et al., 2015): Pr[recall@k≥R∗−PqΔr¯μHΔt1−ξ⋅decay¯cert(Δt) \! [recall@k≥ R^*- P_q r\, _H t1-ξ· decay_cert( t) (11) −Δr¯2Pqln⁡(1/δR)1−ξ]≥1−δR. - r 2P_q (1/ _R)1-ξ ]≥ 1- _R. At branching ratio ξ=0.7ξ=0.7: the bound degrades by ×11−0.7=3.3× 11-0.7=3.3× over Poisson, matching the empirical 11%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 (μ^H=8.2 μ_H=8.2, α^H=5.6 α_H=5.6, β^H=8.0 β_H=8.0, ξ^=0.70 ξ=0.70) and Yelp seasonal-peak events (μ^H=1.7 μ_H=1.7, α^H=1.4 α_H=1.4, β^H=2.6 β_H=2.6, ξ^=0.54 ξ=0.54). The Hawkes bound (Theorem 3) with envelope certificate gives 0.2030.203 (MIMIC-IV) and 0.1600.160 (Yelp) at Δt=7 t=7 days vs. observed 0.1120.112 and 0.0640.064 (ratios 1.8×1.8× and 2.5×2.5×), consistent with the Poisson-case tightening. Theorem 5 (Temporal Valuation Efficiency). Under Assumption 3, EC-MPV satisfies temporal efficiency: (12) ∑i∈∑t=1TMPVi(t,Et)=∑t=1T[v(Dpriv(t)∪Dpub(t)∣Et)−v(Dpub(t)∣Et)]. _i _t=1^TMPV_i(t,E_t)= _t=1^T [v(D_priv(t)∪ D_pub(t) E_t)-v(D_pub(t) E_t) ]. Under clipping at B, this identity holds for vBv_B; bias bounded by B times clip fraction. Proof. Apply Shapley efficiency to vB(⋅;Et)v_B(·;E_t) at each t and sum; clipping bias is <0.3%<0.3\% empirically. See supplementary Appendix A. ∎ Theorem 6 (EC-MPV Estimation Error). Let MPV~i MPV_i be the released score. Under correct event identification: (13) [(MPV~i−MPVi)2]≤B2(1−ρ2)m⏟sampling (VRDS)+(σt⋅Sval)2⏟DP noise.E [( MPV_i-MPV_i)^2 ]≤ B^2(1-ρ^2)m_sampling (VRDS)+ ( _t· S_val)^2_DP noise. Under event misidentification, an additional squared-bias term (MPVi(t,Et)−MPVi(t,Et′))2(MPV_i(t,E_t)-MPV_i(t,E _t))^2 arises. Without VRDS, set ρ=0ρ=0. Proof. Decompose into sampling error, DP noise, and event-misidentification bias; independence gives the MSE bound. See supplementary Appendix A. ∎ Proposition 7 (Formal Sensitivity Bounds). Under seller-level adjacency with Cmaxedge=⌈1.5|E|/n⌉C_max^edge= 1.5|E|/n : (a) Valuation: Sval=4B/nS_val=4B/n (B=0.2B=0.2, n=10n=10: Sval=0.08S_val=0.08). (b) Affinity: Δ2=Cmaxedge _2= C_max^edge, reduced by Stage 2 cap. On Yelp: Δ2≈545 _2≈545 (global), 18.118.1 (active-scope). (c) Index statistics: Sidx≤1.5/nS_idx≤ 1.5/n. Lemma 8 (Safety Override Count). Under the adaptive schedule and Poisson edge changes, [Noverride]=(T)E[N_override]=O( T) and Pr⁡[Noverride>cTln⁡(1/δ)]≤δ [N_override>c T (1/δ)]≤δ. Proof. Budget overrides cluster near end-of-horizon; recall overrides are bounded by pre-convergence EXP3-IX epochs; Azuma-Hoeffding gives concentration. See supplementary Appendix A. ∎ Theorem 9 (Coordination Regret). With d=3d=3, η=ln⁡d/(dT)η= d/(dT), γ=η/2γ=η/2: (14) [RT]≤3dTln⁡d⏟EXP3-IX+Gσobs∑t=1T1min⁡(t,Wmax)⏟observation noise+(T)⏟overrides=(Tlog⁡T).E[R_T]≤ 3 dT d_EXP3-IX+ G _obs _t=1^T 1 (t,W_max)_observation noise+ O( T)_overrides=O( T T). Proof. Standard EXP3-IX bound plus observation noise plus override regret (Lemma 8). See supplementary Appendix A. ∎ Theorem 10 (Temporal Safety Composition). Under the adaptive schedule σt=σ0Tactive/t _t= _0 T_active/t applied only in active epochs, CHRONOS satisfies (εtotal,δtotal)( _total, _total)-DP with: (15) εtotal=(Tactive⋅ln⁡(1/δtotal)σ0). _total=O\! ( T_active· (1/ _total) _0 ). Proof. Sum per-step moments over active epochs, optimise over α, and convert to (ε,δ)( ,δ)-DP. Exact ε=4.25 =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 _entry=885 over [0,1][0,1]-bounded affinities, post-clipping signals are near-Bernoulli(1/2)Bernoulli(1/2); the β=0.3β=0.3 weight gives maximal hybrid-score variation of ≈0.0003≈0.0003 between candidates. Per-query private scoring contributes ≤0.002≤0.002 recall (Table 15). Observed 0.941 recall@10 derives from: (i) public cosine routing; (i) public HNSW structure with ODE-attenuated staleness scheduling; (i) adaptive coordinator scheduling triggered by DP-released index statistics (SNR ≈1.3≈1.3). 6.2. External Valuation Releases and Auditability The external valuation release (noise std 4.04.0 on signal range [0,0.2][0,0.2]) has SNR ≈0.05≈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. 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 trusted-curator model, the operator computes pre-noise MPV scores ϕ^i φ_i with Val. Err=0.013=0.013 and distributes revenue proportionally. These internal computations are exact Shapley-efficient (Theorem 5) and never leave the trusted perimeter. Component 2: Multi-epoch coalition-level audit release. For external verifiability, we aggregate valuations over W epochs and group sellers into coalitions of size ncoaln_coal. Under coalition-level adjacency (protecting whether coalition CjC_j participates, not individual sis_i), sensitivity drops from 4B/n4B/n to 4B/(n/ncoal)4B/(n/n_coal), raising SNR by ncoal×n_coal×: (16) SNRsettle=W⋅ϕ¯coalσt⋅4B⋅ncoal/n=W⋅ϕ¯coal⋅n4B⋅ncoal⋅σt.SNR_settle= W· φ_coal _t· 4B· n_coal/n= W· φ_coal· n4B· n_coal· _t. With W=7W=7, ncoal=5n_coal=5, n=10n=10, ϕ¯coal=0.4 φ_coal=0.4 (summed coalition MPV), B=0.2B=0.2, σt=50 _t=50: SNRsettle=7×0.4×10/(4×0.2×5×50)=0.70SNR_settle=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 W=14W=14: SNR=1.40SNR=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 H(ϕ^i,ri)H( φ_i,r_i) at each epoch (zero DP cost, since the hash is a commitment, not a release of ϕ^i φ_i). Disputes trigger a two-party audit protocol where the operator reveals (ϕ^i,ri)( φ_i,r_i) 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 5). 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. Table 5. Settlement audit SNR under coalition-level adjacency (n=10n=10, B=0.2B=0.2, σt=50 _t=50). W (epochs) ncoaln_coal SNR Attribution Level 1 1 0.05 Noise-dominated 7 5 0.70 Trend: above/below median 14 5 1.40 Rank-order coalitions 7 3 1.17 Trend per 3-seller group 28 5 2.80 Quantitative attribution 6.4. 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 66–10×10× at similar noise levels (Table 12). 7. Experimental Evaluation 7.1. Setup Datasets. Table 6 summarises four benchmarks: FB15K-237 and WN18R with synthetic Poisson annotations, MIMIC-IV and Yelp with real timestamps. Table 6. Datasets. λ in changes/day/shortcut. Dataset Nodes Edges Temporal λ Domain FB15K-237 (Papadimitriou and Tsitsiklis, 1987b) 14.5K 310K Synth. 0.05 General KG WN18R (Dettmers et al., 2018) 40.9K 86.8K Synth. 0.05 Lexical MIMIC-IV (Johnson et al., 2023) 89.4K 1.2M Real ≈ 12 Clinical Yelp (Yelp, 2026) 236K 1.98M Real ≈ 2.9 Local commerce 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. Configuration. ef=128ef=128, efc=200ef_c=200, β=0.3β=0.3, n=10n=10 sellers (balanced partition unless noted), 1000 permutation samples for Shapley with VRDS control variates. Baselines. Indexing: Plain-HNSW (Malkov and Yashunin, 2020), TigerVector (Liu et al., 2025), NaviX (Sehgal and Salihoglu, 2025), FreshDiskANN (Singh et al., 2021), SPFresh (Xu et al., 2023), Quake (Mohoney et al., 2025), VSAG (Zhong et al., 2025) (production HNSW with cache-friendly layout). Valuation: Data Shapley (Ghorbani and Zou, 2019), Beta Shapley (Kwon and Zou, 2022), VRDS (Wu et al., 2023a), Static MPV, Time-Sliced Shapley, RSS (Jia et al., 2023). Coordination: Uncoordinated, Round-Robin, Fixed-Noise, EXP3 (Auer et al., 2002), BwK (Neu, 2015b). Drift: ADWIN (Bifet and Gavaldà, [n.d.]), Page-Hinkley (PAGE, 1954), Dm-BOCD (Knoblauch et al., 2018). DP top-k: OneShot Laplace (Durfee and Rogers, 2019), StableTopK (Bafna and Ullman, 2017), Joint Exponential (Gillenwater et al., 2022), Permute-and-Flip (McKenna and Sheldon, 2020). 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: M=16M=16, ef=128ef=128, efc=200ef_c=200, Lmax=5L_max=5, ρdiv=0.7 _div=0.7. Graph-aware baselines receive the same KG structure and static community affinities; only T-Legend additionally uses temporal decay. Table 7 decomposes the recall gain. Table 7. Recall@10 contribution breakdown on Yelp (static snapshot, 5 seeds). Component R@10 vs. baseline Graph-aware static baseline (same params) .858±.003 — + temporal decay (exponential) .892±.003 +3.4 pts + temporal decay (neural ODE) .904±.002 +4.6 pts + community-sorted insertion .920±.002 +6.2 pts + hub-biased layering .935±.002 +7.7 pts VSAG Throughput Comparison. We integrate VSAG (Zhong et al., 2025) as a production HNSW reference to separate traversal/layout speedups from T-LEGEND’s decay-aware improvements. VSAG uses cache-friendly graph layout and automatic parameter tuning but does not model temporal staleness or provide DP guarantees. Table 8. VSAG comparison on Yelp (k=10k=10, 5 seeds). VSAG-Hybrid adds post-hoc graph affinity with same β=0.3β=0.3 for fair comparison. Method R@10 QPS P50 P99 VSAG (pure vector) .831 8.38 49 115 ∞ VSAG-Hybrid .869 5.08 81 187 ∞ T-LEGEND .935 3.18 127 281 ∞ T-LEGEND+DP (Chronos) .937 2.74 161 317 4.25 VSAG-accelerated T-LEGEND (projected): T-LEGEND+VSAG layout .935 4.79† 84 198 ∞ T-LEGEND+VSAG+DP .937 4.16† 98 222 4.25 †Projected: VSAG’s cache-friendly layout reduces HNSW traversal by ≈1.5×≈1.5×; verified on the pure-vector workload. DP overhead is zero on the query path (post-processing). Key findings. (1) VSAG’s pure-vector QPS (8.38) is 2.6×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 =4.25 (vs. 2.74 currently), a 1.5×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. Table 9. Recall@10 on static benchmarks (k=10k=10, ef=128ef=128, 5 seeds). Method FB15K WN18R MIMIC Yelp Plain-HNSW .821±.004 .843±.003 .798±.005 .809±.004 TigerVector .842±.003 .861±.003 .817±.004 .828±.003 NaviX .864±.003 .878±.002 .839±.004 .848±.003 Diversified-HNSW .872±.003 .886±.002 .848±.003 .858±.003 VSAG-Hybrid .881±.003 .892±.002 .857±.003 .868±.003 FreshDiskANN .836±.003 .858±.003 .823±.004 .836±.003 SPFresh .829±.004 .851±.003 .814±.005 .829±.004 Quake .848±.003 .869±.003 .831±.004 .842±.003 T-LEGEND .941±.002 .956±.002 .927±.003 .935±.002 Over 90 simulated days on MIMIC-IV with weekly updates, T-Legend degrades at 0.0021 recall points/day versus 0.0089 for Plain-HNSW (4.2×4.2× improvement) and 0.0058 for FreshDiskANN (2.8×2.8×), consistent with Theorem 1 (Figure 3). Figure 3. Recall@10 degradation on MIMIC-IV (λ≈12λ≈ 12 changes/day/shortcut) over 90 simulated days without re-indexing. Valuation and Drift Detection. Valuation error metric. Val.Err=1n∑i=1n(MPV^i−MPVigold)2Val.Err= 1n _i=1^n( MPV_i-MPV_i^gold)^2; gold standard uses m=50,000m=50,000 permutations (SE ≈0.004≈0.004), confirmed by exhaustive enumeration (n≤15n≤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 (Jia et al., 2023) yields Val. Err 0.019 at 9.5×9.5× sampling cost; post-changepoint RSS degrades to 0.031, confirming event-conditioning provides orthogonal benefits. Comparative detector precision/recall and privacy waste are reported in Table 10. Table 10. Drift detectors on Yelp (8 injected seasonal events). Δρ ρ: wasted ρ from false alarms. Detector Prec. Rec. Δρ ρ BOCPD .875 .875 0.004 Dm-BOCD (Knoblauch et al., 2018) 1.00 .750 0.000 ADWIN (Bifet and Gavaldà, [n.d.]) .615 1.00 0.020 Page-Hinkley 1.00 .625 0.000 7.2. End-to-End Performance Table 11. End-to-end performance on Yelp (5 runs). System R@10 QPS TPS P50 P99 Val.Err HNSW+No-DP .817 3.41 244 74 201 ∞ N/A Hybrid+GaussDP .838 1.48 106 165 396 2.10 0.040 KG+StaticVal .904 1.75 124 175 352 1.40 0.023 CHRONOS .937 2.74 138 161 317 4.25 0.012 DP Retrieval Mechanism Comparison. Table 12 provides a head-to-head comparison against per-query DP mechanisms under matched total ε=4.25 =4.25 on Yelp as seen in Figure 4. Figure 4. Privacy-utility operating points on Yelp. Chronos (Blue Square) achieves higher recall at each ε level than per-query DP mechanisms (Red Triange) at matched ε=4.25 =4.25, while maintaining 2.74 QPS vs. 0.28–0.43 for per-query alternatives. Table 12. DP retrieval mechanisms at matched ε=4.25 =4.25 on Yelp (5 seeds). Mechanism R@10 QPS P50 P99 /query Chronos (epoch) .937 2.74 161 317 0 OneShot Laplace .891 0.40 498 1265 1.18×10−51.18×10^-5 StableTopK .909 0.37 533 1406 1.18×10−51.18×10^-5 Joint Exponential .920 0.28 698 1653 1.18×10−51.18×10^-5 Permute-and-Flip .904 0.43 461 1172 1.18×10−51.18×10^-5 Scalability Analysis. We analyse how ρtotal _total and per-mechanism ρ scale with the number of sellers n and horizon length. Sensitivity scaling. Sval=4B/nS_val=4B/n decreases with n; Δ2=Cmaxedge=⌈1.5|E|/n⌉ _2= C_max^edge= 1.5|E|/n decreases as Θ(1/n) (1/ n); the active-scope cap κactive∝|Eactive|/n _active |E_active|/n also decreases. This means per-mechanism ρi _i decreases with n at fixed σt _t: more sellers means lower per-seller sensitivity, which benefits DP. However, TactiveT_active may increase with n (more sellers trigger more frequent updates). Table 13. Scalability analysis on Yelp (σt=50 _t=50, δ=10−6δ=10^-6, 90-day horizon, 5 seeds). ρtotal _total computed via zCDP. n SvalS_val Δ2active _2^active TactiveT_active ρtotal _total ε R@10 10 0.080 18.1 710 0.284 4.25 .937±.002 50 0.016 8.1 824 0.329 4.58 .939±.002 100 0.008 5.7 891 0.356 4.76 .940±.002 200 0.004 4.0 952 0.381 4.93 .940±.002 500 0.0016 2.6 1031 0.412 5.13 .941±.002 Key findings. (1) ε grows sublinearly with n: from 4.25 (n=10n=10) to 5.13 (n=500n=500), a 21% increase for a 50×50× increase in sellers. This is because reduced sensitivity (Δ2 _2 drops from 18.1 to 2.6) largely offsets the increased TactiveT_active. (2) Recall improves slightly with n (more sellers provide more data). (3) The affinity release remains useful for scheduling at all n: the index statistics mechanism (SNR ≈1.3≈1.3) drives coordinator decisions, and its sensitivity Sidx=1.5/nS_idx=1.5/n improves with n. Long-horizon scaling. Over a 360-day horizon (vs. 90 days), TactiveT_active roughly quadruples to ≈2,800≈2,800 at n=10n=10, giving ρtotal≈1.12 _total≈1.12 and ε≈8.47 ≈8.47. At n=100n=100 over 360 days: ρtotal≈1.42 _total≈1.42, ε≈9.52 ≈9.52. For multi-year deployments, periodic “budget epochs” (resetting the accountant with fresh σ0 _0) are necessary, analogous to privacy odometer checkpoints (Rogers et al., 2016). DP vs. Cryptographic Alternatives. Table 14 compares DP noise-based protection with cryptographic alternatives for the affinity computation workload. Table 14. DP vs. cryptographic alternatives for affinity scoring (Yelp, n=10n=10). Approach Per-Query QPS Trust Noise Latency Model CHRONOS (DP) 161 ms 2.74 Trusted curator σ=885σ=885 2PC-Garbled (Demmler et al., 2015) ∼ 2.4 s 0.08 Semi-honest 2PC Zero HE (CKKS) (Lindell, 2021) ∼ 1.1 s 0.18 Client-side HE Zero TEE (SGX) (Costan and Devadas, 2016) ∼ 210 ms 2.14 Hardware trust Zero Hybrid: CHRONOS + TEE for settlement (§6.3): CHRONOS+TEE 161 ms† 2.74 Curator + TEE σ=885†σ=885 †TEE used only for settlement verification (off query path), not per-query scoring. Query-path latency and noise are unchanged. Analysis. (1) 2PC and HE eliminate noise but introduce 77–30×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 side-channel attacks (Brasser et al., 2017). (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. Proposition 1 (Rank-Flip Probability at Top-k Boundary). Let candidates i (ranked k-th) and j (ranked (k+1)(k+1)-th) have true hybrid scores si>sjs_i>s_j. The probability that DP noise flips their ordering is: P(flipij)=Φ(−si−sjβσentry2)P(flip_ij)= \! (- s_i-s_jβ _entry 2 ) where Φ is the standard normal CDF. Remark 8 (Reconciling σentry=885 _entry=885 with High Rank Stability). Post-clipping noise is bimodal at 0,1\0,1\ with σclip≈0.50 _clip≈0.50; cosine dominance (weight 0.7) governs ≈80% of within-top-10 pairs. Table 15. Monte Carlo rank-stability ablation (β=0.3β=0.3, Yelp, 10510^5 queries, 5 seeds). _entry R@10 τ (all) τ (top-10) Agg. loss 0.01 (near non-priv.) .939 0.990 0.998 0.0001 0.5 .938 0.981 0.994 0.0005 5 .938 0.962 0.978 0.0011 100 .937 0.929 0.965 0.0022 885 (Chronos) .937 0.938 0.968 0.0020 Private-Edge Discovery Rate. Table 16. Private-edge discovery analysis (k=10k=10, 5 seeds). Dataset Miss rate Recall gap New-edge frac. β Yelp (β=0.3β=0.3) 4.5%± 0.9 −-0.009 5.8% 0.3 Yelp (β=0.7β=0.7) 12.4%± 1.5 −-0.032 5.8% 0.7 MIMIC-IV (β=0.3β=0.3) 5.8%± 1.1 −-0.012 8.3% 0.3 MIMIC-IV (β=0.7β=0.7) 14.2%± 1.8 −-0.042 8.3% 0.7 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 (Andrew et al., 2021) reduces KL to 0.019. Full per-seller confidence intervals in supplementary Appendix C. Privacy-Utility Trade-off. Table 17 summarises the privacy-utility frontier under different σ0 _0 settings, including the adaptive-vs-fixed scheduling comparison. Table 17. Privacy-utility trade-off on Yelp, sampled rows (5 seeds). ε computed via Eq. (1). σ0 _0 ρtotal _total ε R@10 (Adaptive) R@10 (Fixed) 30 0.789 7.50 .938±.002 .927±.003 50 0.284 4.25 .937±.002 .917±.003 100 0.071 2.13 .932±.003 .900±.004 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 λq(t)=λ¯q(1+0.5sin⁡(2πt/24)) _q(t)= λ_q(1+0.5 (2π t/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 pexitp_exit. Under static Shapley with DP 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. 7.4. Robustness and Sensitivity Non-Poisson dynamics. Under Hawkes bursts (μ=2.9μ=2.9, branching ξ=0.7ξ=0.7) on Yelp, recall drops 1.3 pts and ρ rises 11%. The Hawkes recall bound (Theorem 3) predicts 3.3×3.3× degradation at ξ=0.7ξ=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-2.1 pts, +18%ρ+18\%\,ρ. Staleness, overlap η, and reward weights. Overlap stress-test (η∈1.2,1.5η∈\1.2,1.5\): effective ρ rises to 0.4090.409/0.6390.639, matching η2⋅ρη^2·ρ analytically within ±2%± 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±778±7 consistent with (T)O( T). High-β Regime and Cold-Start. Below β=0.5β=0.5, recall remains >0.93>0.93; above β=0.7β=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β=0.7 recovers 52%52\% of misses at +0.05ε+0.05\, . End-to-end ε under DP-SGD. When 0X_0 is trained privately: εtotal=1.5+4.25=5.75 _total=1.5+4.25=5.75 (δtotal=2×10−6 _total=2×10^-6). The complete budget decomposition across operating modes is shown in Table 18. Table 18. ε budget breakdown across operating modes. Mode εtrain _train εaff _aff εval _val εidx _idx εtotal _total Chronos (β=0.3β=0.3) 0 2.94 1.84 2.25 4.25∗ Chronos + SVT (β=0.7β=0.7) 0 2.94 1.84 2.30 4.40∗ Chronos + DP-SGD (β=0.3β=0.3) 1.50 2.94 1.84 2.25 5.75 Chronos + DP-SGD + SVT (β=0.7β=0.7) 1.50 2.94 1.84 2.30 5.90 ∗Standard additive zCDP composition (Eq. (1)). 7.5. Ablation Study Table 19. Ablation on FB15K-237. All ε via Eq. (1). Variant R@10 TPS P50 CHRONOS (full) .941 141 158 4.25 w/o temporal decay .897 149 151 4.25 w/o private DP affinity (β=0β=0) .863 158 143 4.25 w/o neural ODE (exp. decay) .929 141 159 4.25 w/ β=0.7β=0.7 .920 138 165 4.47 w/ cold-start queries .891 141 158 4.25 w/ cold-start + fallback .922 139 162 4.27 w/o aff. privatisation .943 143 155 — w/o EC-MPV (static Shapley) .941 141 158 4.48 w/o VRDS .941 141 158 4.25 w/o BOCPD .941 141 158 4.59 w/o Coordinator (round-robin) .908 105 213 5.38 w/o incremental upd. .941 43 412 4.25 w/ BwK coordinator (Neu, 2015b) .939 136 164 4.25 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.941, the privacy cost rises: without EC-MPV, ε increases to 4.484.48 (+5.4%+5.4\%) because static Shapley triggers more frequent revaluation; without BOCPD, ε reaches 4.594.59 (+8.0%+8.0\%) because undetected changepoints cause redundant recomputation. Removing the Coordinator entirely (round-robin) degrades recall by 3.33.3 pts and raises ε to 5.385.38 (+26.6%+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. 8. Related Work We survey six areas and identify the specific gap each leaves for temporal KG marketplaces. Dynamic ANN and temporal graph indices. FreshDiskANN (Singh et al., 2021), SPFresh (Xu et al., 2023), Quake (Mohoney et al., 2025), CleANN (Zhang et al., 2025), and MN-RU (Xiao et al., 2024) support streaming updates but do not model KG structural staleness or provide recall bounds tied to evolution rates. VSAG (Zhong et al., 2025) 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 (Fernandez et al., 2020; Azcoitia and Laoutaris, 2022) support query-based pricing, subscription models, and static data products. Dealer (Liu et al., 2021) 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 (Koutsos et al., 2020) focuses on access control and auditability rather than temporal query performance. Recent work on data pricing in ML pipelines (Cong et al., 2021) and query-based pricing (Koutris et al., 2015) 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 (Mundra et al., 2025; Nissim et al., 2007; Kasiviswanathan et al., 2013) and node-level DP for GNN training (Zhang et al., 2024) protect structural information, but they target analytics and model training rather than real-time retrieval. PSGraph (Yuan et al., 2025) demonstrates temporal-aware DP allocation for graph synthesis. DP learned indexes (Du et al., 2024) apply DP to index structures; CHRONOS avoids this cost by treating the index as public. Per-query DP selection mechanisms (Durfee and Rogers, 2019; Gillenwater et al., 2022; Wu and Zhang, 2024) incur 66–10×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 (Tossou and Dimitrakakis, 2015; Agarwal and Singh, 2017; Wu et al., 2023b) privatise actions or rewards but do not integrate with index maintenance or data valuation. Privacy filters and odometers (Rogers et al., 2016; Feldman and Zrnic, 2022) track composition but do not schedule multi-agent operations. Gap: no prior coordination mechanism optimises the allocation of a shared DP budget among indexing, valuation, and idle actions with sub-linear regret guarantees. Data valuation under non-stationarity. Data Shapley (Ghorbani and Zou, 2019), Beta Shapley (Kwon and Zou, 2022), Data Banzhaf (Wang and Jia, 2023), and Distributional Shapley (Ghorbani et al., 2020) assume stationary utilities. VRDS (Wu et al., 2023a) reduces variance but does not condition on events. RSS (Jia et al., 2023) offers stratified sampling yet degrades post-changepoint (Val. Err 0.0310.031 vs. 0.0130.013). Gap: no Shapley estimator couples changepoint detection with finite-sample error bounds under DP noise. Temporal KG embedding and retrieval. TTransE (Leblay and Chekol, 2018), HyTE (Dasgupta et al., 2018), TNTComplEx (Yang et al., 2024), TGAT (Xu et al., 2020), and RE-Net (Jin et al., 2020) model temporal facts but provide no retrieval-guarantee structures. TG-RAG (Han et al., 2025) 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 2) that tightens the recall bound to 1.81.8–3.2×3.2× observed loss by incorporating ODE Lipschitz structure with Grönwall-based solver verification; (2) formal Hawkes-process recall bounds (Theorem 3) extending guarantees beyond Poisson to correlated dynamics parameterised by branching ratio; (3) a concrete multi-epoch coalition-level settlement mechanism (§6.3) with SNR analysis indicating trend-level seller attribution at W≥7W≥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.81.8–3.2×3.2× loose; closing the residual gap requires path-correlation analysis at hub nodes, identified as future work. (2) Private signal informativeness: affinity (σentry=885 _entry=885) and valuation (noise std 4.04.0) releases remain noise-dominated at ε=4.25 =4.25; utility derives from public routing and adaptive scheduling. (3) Trust assumptions: trusted curator with near-exclusive ownership (η≈1η≈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.81.8–3.2×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) Abadi et al. (2016) 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 Adams and MacKay (2007) Ryan Prescott Adams and David J. C. MacKay. 2007. Bayesian Online Changepoint Detection. arXiv:0710.3742 [stat.ML] https://arxiv.org/abs/0710.3742 Agarwal and Singh (2017) 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 Andrew et al. (2021) 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. Auer et al. (2002) 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 Azcoitia and Laoutaris (2022) 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 Bacry et al. (2015) 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 Bafna and Ullman (2017) Mitali Bafna and Jonathan Ullman. 2017. The Price of Selection in Differential Privacy. arXiv:1702.02970 [cs.DS] https://arxiv.org/abs/1702.02970 Bifet and Gavaldà ([n.d.]) 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 Blondel et al. (2008) 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 Brasser et al. (2017) 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. Castro et al. (2009) 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 Chan et al. (2011) 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 Chen et al. (2019) 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 Cong et al. (2021) 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 Costan and Devadas (2016) Victor Costan and Srinivas Devadas. 2016. Intel SGX Explained. IACR Cryptol. ePrint Arch. 2016 (2016), 86. https://api.semanticscholar.org/CorpusID:28642809 Dasgupta et al. (2018) 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 Demmler et al. (2015) 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 Dettmers et al. (2018) Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. 2018. Convolutional 2D knowledge graph embeddings. In Proceedings of the Thirty-Second 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. Dormand and Prince (1980) 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 Du et al. (2024) 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 Durfee and Rogers (2019) 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. Dwork et al. (2010) 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 Dwork and Roth (2014) 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 Feldman and Zrnic (2022) Vitaly Feldman and Tijana Zrnic. 2022. Individual Privacy Accounting via a Renyi Filter. arXiv:2008.11193 [cs.CR] https://arxiv.org/abs/2008.11193 Fernandez et al. (2020) 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 Ghorbani et al. (2020) 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. Ghorbani and Zou (2019) 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 Gillenwater et al. (2022) Jennifer Gillenwater, Matthew Joseph, Andrés Muñoz Medina, and Mónica Ribero. 2022. A Joint Exponential Mechanism For Differentially Private Top-k. arXiv:2201.12333 [cs.CR] https://arxiv.org/abs/2201.12333 Han et al. (2025) 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 Hazan (2023) Elad Hazan. 2023. Introduction to Online Convex Optimization. arXiv:1909.05207 [cs.LG] https://arxiv.org/abs/1909.05207 Jia et al. (2023) 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 Jin et al. (2020) 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 Johnson et al. (2023) 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 Kasiviswanathan et al. (2013) 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 Knoblauch et al. (2018) 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. Koutris et al. (2015) 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 Koutsos et al. (2020) 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 Kwon and Zou (2022) 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 Leblay and Chekol (2018) Julien Leblay and Melisachew Wudage Chekol. 2018. Deriving Validity Time in Knowledge Graph. In Companion Proceedings of the The Web Conference 2018 (Lyon, France) (W ’18). International World Wide Web Conferences Steering Committee, Republic and Canton of Geneva, CHE, 1771–1776. https://doi.org/10.1145/3184558.3191639 Lindell (2021) 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 Liu et al. (2021) 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 Liu et al. (2025) 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 Lowe et al. (2017) 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. Malkov and Yashunin (2020) 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 McKenna and Sheldon (2020) 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. McSherry and Talwar (2007) 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 Mironov (2017) 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 Mohoney et al. (2025) 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. Mundra et al. (2025) 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 Neu (2015a) Gergely Neu. 2015a. 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. Neu (2015b) Gergely Neu. 2015b. 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. Nissim et al. (2007) 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 PAGE (1954) 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-2-100.pdf Papadimitriou and Tsitsiklis (1987a) Christos H. Papadimitriou and John N. Tsitsiklis. 1987a. The Complexity of Markov Decision Processes. Math. Oper. Res. 12, 3 (Aug. 1987), 441–450. Papadimitriou and Tsitsiklis (1987b) Christos H. Papadimitriou and John N. Tsitsiklis. 1987b. The Complexity of Markov Decision Processes. Math. Oper. Res. 12, 3 (Aug. 1987), 441–450. Patel et al. (2024) 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 Rogers et al. (2016) 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. Sehgal and Salihoglu (2025) 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 Shapley (1953) 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 Singh et al. (2021) Aditi Singh, Suhas Jayaram Subramanya, Ravishankar Krishnaswamy, and Harsha Vardhan Simhadri. 2021. FreshDiskANN: A Fast and Accurate Graph-Based ANN Index for Streaming Similarity Search. arXiv:2105.09613 [cs.IR] https://arxiv.org/abs/2105.09613 Tossou and Dimitrakakis (2015) Aristide Tossou and Christos Dimitrakakis. 2015. Algorithms for Differentially Private Multi-Armed Bandits. arXiv:1511.08681 [stat.ML] https://arxiv.org/abs/1511.08681 Wang and Jia (2023) 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 Wu and Zhang (2024) 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. Wu et al. (2023a) Mengmeng Wu, Ruoxi Jia, Changle Lin, Wei Huang, and Xiangyu Chang. 2023a. 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 Wu et al. (2023b) Yulian Wu, Xingyu Zhou, Youming Tao, and Di Wang. 2023b. 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. Xiao et al. (2024) 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 Xu et al. (2020) Da Xu, Chuanwei Ruan, Evren Korpeoglu, Sushant Kumar, and Kannan Achan. 2020. Inductive Representation Learning on Temporal Graphs. arXiv:2002.07962 [cs.LG] https://arxiv.org/abs/2002.07962 Xu et al. (2023) 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 Yang et al. (2024) 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 Yelp (2026) Yelp. 2026. Yelp Open Dataset. https://w.yelp.com/dataset Yuan et al. (2025) 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 Zhang et al. (2024) 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) (W ’24). Association for Computing Machinery, New York, NY, USA, 1170–1181. https://doi.org/10.1145/3589334.3645531 Zhang et al. (2025) 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 Zhong et al. (2025) 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

Instant research discovery