ملخص تقني: CHRONOS

1. بيان المشكلة

تواجه أسواق بيانات الرسوم البيانية المعرفية (KG) الزمنية ثلاثة إخفاقات مترابطة عند تصميمها بهياكل ثابتة:

1. فهرسة متقادمة (Stale Indexing): تعتمد فهارس المتجهات والرسوم البيانية الهجينة (مثل HNSW) على حواف مختصرة يتم بناؤها عند التأسيس. ومع تطور الرسم البياني المعرفي (إضافة أو إزالة الحواف)، تصبح هذه الاختصارات متقادمة، مما يؤدي إلى تدهور صامت في الاستدعاء (Recall). تفشل الأنظمة الديناميكية الحالية في معالجة تحديثات المتجهات، لكنها تفشل أيضاً في نمذجة تقادم البنية الهيكلية للرسم البياني أو توفير حدود للاستدعاء مرتبطة بمعدلات التطور.
2. تقييم غير مستقر (Stationary Valuation): يعتمد الإسناد العادل للبيانات عادةً على قيم شابلي (Shapely values)، والتي تفترض دالة خصائص ثابتة. في الأسواق المتطورة، تؤدي التحولات التوزيعية (مثل تفشي الأمراض أو التغييرات التنظيمية) إلى تغير حاد في القيم الهامشية لمجموعات البيانات. يؤدي التقييم الثابت إلى سوء إسناد القيمة، مما يشوه حوافز السوق.
3. ميزانية خصوصية غير منسقة (Uncoordinated Privacy Budget): تعمل أسواق الإنتاج الوكلاء المتزامنين الذين يتشاركون ميزانية خصوصية تفاضلية (DP) محدودة. بدون تنسيق، تؤدي الطلبات المتزامنة لتحديثات الفهرس، وإعادة حساب التقييم، ومعالجة الاستعلامات إلى استنفاد الميزانية قبل أوانها. تفتقر الأطر الحالية إلى الربط الرسمي بين الجدولة واستهلاك الخصوصية التفاضلية (DP).

هذه التحديات غير قابلة للتفكيك لأن تحديثات الفهرس، وإعادة حساب التقييم، والانتظار، كلها تستهلك من نفس المخصص المحدود $(\epsilon, \delta)$.

2. المنهجية: بنية CHRONOS

CHRONOS هو بنية مكونة من ثلاث طبقات تحت إدارة قيم أمين (Curator) موثوق، توفر معالجة موحدة لهذه التحديات مع فصل صريح بين العام والخاص.

الطبقة 1: T-LEGEND (الفهرس الهجين الزمني)

تطبق T-LEGEND تلاشي زمنياً عبر المعادلات التفاضلية العصبية (Neural-ODE) على الحواف المختصرة، مما يسمح للفهرس بالتدهور تدريجياً بدلاً من الفشل الصامت.

• الآلية: تقوم المعادلة التفاضلية العصبية (Neural ODE) بنمذجة تلاشي فائدة الحافة بمرور الوقت ($\Delta t$). دالة التلاشي هي المكون الأول لحل المعادلة التفاضلية، ويتم تدريبها على لقطات تاريخية للرسم البياني المعرفي باستخدام فقدان زمني تبايني (Contrastive temporal loss).
• الفصل بين العام والخاص: يتم بناء هيكل الفهرس ($H_T$) وقوائم الجوار بشكل حتمي من بيانات عامة سابقة للسوق (التضمينات المجمدة وتقسيمات المجتمع). الحواف التي يساهم بها البائعون لا تغير طوبولوجيا الفهرس، بل تؤثر فقط على مصفوفة التقارب الخاصة على مستوى الحقبة (Epoch-level).
• الضمان النظري: يوفر النظام حداً متوقعاً لفقدان الاستدعاء لكل استعلام قدره $O(P_q \lambda \Delta t)$. يعمل شهادة الغلاف الرتيب (Monotone-envelope certificate) على تضييق هذا الحد، مما يقلل الفجوة بين الحد النظري والفقد الملحوظ إلى 1.8–3.2$\times$. كما تم توسيع الحدود الرسمية لتشمل ديناميكيات هاوكس (Hawkes dynamics) للتعامل مع تغيرات الحواف المترابطة.

الطبقة 2: التقييم المشروط بالأحداث (EC-MPV)

تقوم هذه الطبقة بضبط تقييم شابلي بناءً على نقاط التغير التوزيعي المكتشفة بواسطة BOCPD (الكشف عبر الإنترنت عن نقاط التغير البايزي).

• الآلية: بدلاً من إعادة الحساب المستمر، يتم تجميع التقييمات وتكييفها مع الأحداث المكتشفة ($E$). يتم حساب المساهمة الهامشية للبائع كـ $\phi_i(D_{priv} \cup D_{pub} | E, t) - \phi(D_{pub} | E, t)$.
• الكفاءة: تستخدم تقنية تقليل التباين في "شابلي للبيانات" (VRDS) مع متغيرات التحكم لخفض تباين أخذ العينات.
• الضمانات: يوفر النظام ضمانات خطأ لعينة محدودة تحت أخذ عينات التحالف وضجيج الخصوصية التفاضلية (DP)، مع هوية كفاءة زمنية تضمن أن مجموع التقييمات يساوي القيمة الإجمالية لمساهمة البيانات الخاصة.

الطبقة 3: المنسق الزمني (Temporal Coordinator)

وكيل ميتا (Meta-agent) يقوم بجدولة العمليات (تحديث الفهرس، إعادة التقييم، أو "لا شيء") لفرض ميزانية DP المشتركة.

• الخوارزمية: يستخدم EXP3-IX (خوارزمية متعددة الأذرع) عبر ثلاثة إجراءات جدولة.
• الندم (Regret): يحقق ندماً قدره $O(\sqrt{T \log T})$ مع فرض $(\epsilon_{total}, \delta_{total})$-DP عبر حسابات اللحظات (Moments accounting).
• إدارة الميزانية: يوازن بين الطلبات المتنافسة، مما يضمن عدم استنزاف صيانة الفهرس وعمليات التقييم لبعضهما البعض. يقوم بإلغاء الإجراءات التي قد تنتهك الميزانية، وتحويلها إلى "لا شيء" أو "تحديث الفهرس" كإجراءات حماية.

آلية الخصوصية: خط معالجة DP ذو أبعاد ثابتة

يستخدم CHRONOS فصلاً صارماً بين العام والخاص:

• العام: التضمينات، هيكل الفهرس، ومتجهات الاستعلام لا تكلف أي قيمة DP.
• الخاص: حواف البائعين، درجات التقييم، وإحصائيات تقادم الفهرس محمية.
• سياسة الإصدار: يقوم النظام بإصدار مصفوفة تقارب ذات أبعاد ثابتة ومخصخصة ($\tilde{A}(t)$) مرة واحدة لكل حقبة نشطة باستخدام آلية غاوس (Gaussian mechanism).
• المعالجة اللاحقة: يتم إجراء جميع عمليات الاسترجاع وتصنيف أعلى-$k$ كمعالجة لاحقة للمصفوفة المشوشة. وبالتالي، فهي لا تكلف أي تكلفة خصوصية إضافية.
• المحاسبة: يستخدم النظام حساب التكوين الجمعي القياسي zCDP عبر $\rho$، محققاً إجمالي $\epsilon = 4.25$ عند $\delta = 10^{-6}$ عبر آليات متعددة (إحصائيات الفهرس، التقييم، والتقارب).

آلية التسوية (Settlement Mechanism)

لمعالجة الطبيعة التي يهيمن عليها الضجيج في إصدارات التقييم الخارجية (حيث الانحراف المعياري للضجيج $\gg$ الإشارة)، يقدم CHRONOS آلية تسوية على مستوى التحالف متعدد الحقبات. من خلال تجميع التقييمات عبر $W$ من الحقبات وتجميع البائعين في تحالفات، تتحسن نسبة الإشارة إلى الضجيج (SNR)، مما يسمح بالنسب الاتجاهي (مثل التمييز بين المساهمة فوق أو تحت المتوسط) عند $W \ge 7$ حقبات.

3. النتائج الرئيسية

أُجريت التجارب على أربعة معايير: FB15K-237، WN18RR (اصطناعي)، MIMIC-IV، وYelp (واقعي).

• الأداء: يحقق CHRONOS 0.937 recall@10 على Yelp بسرعة 2.74 استعلام/ثانية وزمن وصول P50 يبلغ 161 مللي ثانية.
• استقرار الاستدعاء: في MIMIC-IV، يتدهور T-LEGEND بمعدل 0.0021 نقطة استدعاء/يوم فقط، وهو تحسن بمقدار 4.2$\times$ عن Plain-HNSW و2.8$\times$ عن FreshDiskANN.
• المفاضلة بين الخصوصية والمنفعة: عند مطابقة $\epsilon=4.25$، يتفوق CHRONOS بشكل كبير على آليات الاستعلام لكل استعلام (مثل OneShot Laplace وJoint Exponential)، والتي تعاني من انخفاض في QPS بمقدار 6–10$\times$ (0.28–0.43 مقابل 2.74).
• القابلية للتوسع: يتوسع النظام ليصل إلى 500 بائع. مع زيادة عدد البائعين ($n$)، تقل الحساسية ($\propto 1/\sqrt{n}$)، مما يؤدي إلى نمو إجمالي $\epsilon$ بشكل دون خطي (من 4.25 عند $n=10$ إلى 5.13 عند $n=500$).
• تأثير التنسيق: إزالة المنسق الزمني (باستخدام التدوير Round-robin) يؤدي إلى تدهور الاستدعاء بمقدار 3.3 نقطة وزيادة $\epsilon$ بنسبة 26.6%، مما يؤكد ضرورة التصميم المشترك.
• المقارنة مع VSAG: بينما يوفر VSAG (وهو HNSW إنتاجي) سرعة QPS خام أعلى، إلا أنه يفتقر إلى تسجيل الرسم البياني المعرفي الزمني. من المتوقع أن يؤدي دمج تخطيط VSAG مع بناء T-LEGEND المدرك للتلاشي إلى تسريع بمقدار 1.5$\times$ دون التضحية بالاستدعاء.

4. الأهمية والادعاءات

يدعي البحث أن CHRONOS يمثل أول نظام يربط بين حداثة الفهرس، صحة التقييم، وإدارة ميزانية DP المنسقة ضمن إطار عمل متعدد الوكلاء للرسوم البيانية المعرفية الزمنية.

• المعالجة الموحدة: يثبت أن هذه التحديات الثلاثة لا يمكن حلها بمعزل عن بعضها؛ بل يتطلب الأمر تصميماً مشتركاً لمنع استنفاد الميزانية وتدهور الأداء.
• الدقة النظرية: يقدم العمل حدود استدعاء رسمية (نظريات 2-4) تدمج هياكل Lipschitz للمعادلات التفاضلية وعمليات هاوكس، متجاوزاً الافتراضات الساكنة.
• الخصوصية العملية: يضع نقطة تشغيل قابلة للتطبيق للاسترجاع عالي المنفعة ومنخفض زمن الوصول تحت قيود DP صارمة من خلال استغلال هياكل الفهرس العامة وتوزيع تكاليف DP على الحقبات بدلاً من كل استعلام.
• تسوية قابلة للتنفيذ: يقدم آلية ملموسة لمدفوعات البائعين توفق بين الضجيج العالي لإصدارات DP والحاجة إلى إسناد عادل، باستخدام تجميع التحالف لاستعادة الإشارة.

5. المحددات

يقر المؤلفون صراحةً بعدة محددات:

• رخاوة الحدود: يظل حد الغلاف الرتيب أضعف بمقدار 1.8–3.2$\times$ من الفقد الملحوظ؛ ويتطلب سد هذه الفجوة تحليل ارتباط المسار عند العقد المركزية (Hub nodes).
• الإشارات المهيمن عليها الضجيج: عند مستوى الخصوصية المختار ($\epsilon=4.25$)، تهيمن الضوضي على التقييمات ونقاط التقارب المنشورة خارجياً. تستمد المنفعة في النظام قيمتها أساساً من توجيه الفهرس العام والجدولة التكيفية المدفوعة بإحصائيات DP منخفضة الحساسية، وليس من الإشارة الخاصة نفسها.
• نموذج الثقة: يعتمد التصميم الحالي على أمين (Curator) موثوق يحتفظ بجميع بيانات البائعين الخام. تم اقتراح امتدادات لـ (Two-server) و(Local DP) كعمل مستقبلي، لكنها لم تُنفذ أو تُختبر بالكامل في هذه الدراسة.
• خصوصية الاستعلام: تُعامل استعلامات المشتري كبيانات عامة. إذا كانت الاستعلامات حساسة، فستكون هناك حاجة لآليات إضافية (مثل Count-min sketches)، وهي ليست جزءاً من التقييم الأساسي.