2025-11-17T05:52:13.175509

Accelerated Evolving Set Processes for Local PageRank Computation

Huang, Luo, Xiao et al.
This work proposes a novel framework based on nested evolving set processes to accelerate Personalized PageRank (PPR) computation. At each stage of the process, we employ a localized inexact proximal point iteration to solve a simplified linear system. We show that the time complexity of such localized methods is upper bounded by $\min\{\tilde{\mathcal{O}}(R^2/ε^2), \tilde{\mathcal{O}}(m)\}$ to obtain an $ε$-approximation of the PPR vector, where $m$ denotes the number of edges in the graph and $R$ is a constant defined via nested evolving set processes. Furthermore, the algorithms induced by our framework require solving only $\tilde{\mathcal{O}}(1/\sqrtα)$ such linear systems, where $α$ is the damping factor. When $1/ε^2\ll m$, this implies the existence of an algorithm that computes an $\ epsilon $-approximation of the PPR vector with an overall time complexity of $\tilde{\mathcal{O}}\left(R^2 / (\sqrtαε^2)\right)$, independent of the underlying graph size. Our result resolves an open conjecture from existing literature. Experimental results on real-world graphs validate the efficiency of our methods, demonstrating significant convergence in the early stages.
academic

عمليات المجموعات المتطورة المعجلة لحساب PageRank المحلي

المعلومات الأساسية

  • معرّف الورقة: 2510.08010
  • العنوان: Accelerated Evolving Set Processes for Local PageRank Computation
  • المؤلفون: Binbin Huang, Baojian Zhou, Luo Luo, Deqing Yang, Yanghua Xiao (جامعة فودان)
  • التصنيف: cs.LG
  • المؤتمر: المؤتمر الـ 39 حول أنظمة معالجة المعلومات العصبية (NeurIPS 2025)
  • رابط الورقة: https://arxiv.org/abs/2510.08010v2

الملخص

تقترح هذه الورقة إطار عمل جديد قائم على عمليات المجموعات المتطورة المتداخلة (nested evolving set processes) لتسريع حساب PageRank المخصص (PPR). في كل مرحلة، يتم استخدام تكرار نقطة تقريبية غير دقيقة محلية لحل نظام خطي مبسط. تُظهر الدراسة أن الحد الأعلى لتعقيد الوقت لمثل هذه الطرق المحلية هو min⁡{O~(R2/ε2),O~(m)}\min\{\tilde{\mathcal{O}}(R^2/ε^2), \tilde{\mathcal{O}}(m)\} للحصول على تقريب ε للمتجه PPR، حيث m يمثل عدد الحواف في الرسم البياني و R ثابت محدد بواسطة عملية المجموعات المتطورة المتداخلة. الخوارزمية المستحثة من الإطار تتطلب فقط حل O~(1/α)\tilde{\mathcal{O}}(1/\sqrt{α}) من هذه الأنظمة الخطية، حيث α هو عامل التخفيف. عندما يكون 1/ε2≪m1/ε^2 \ll m، هذا يعني وجود خوارزمية يمكنها حساب تقريب ε لمتجه PPR بتعقيد وقت إجمالي قدره O~(R2/(αε2))\tilde{\mathcal{O}}(R^2/(\sqrt{α}ε^2))، مستقل عن حجم الرسم البياني الأساسي.

خلفية البحث والدافع

تعريف المشكلة

يُعرّف متجه PageRank المخصص (PPR) π ∈ ℝⁿ كما يلي:

(I - (1-α)(I + AD⁻¹)/2)π = αeₛ

حيث eₛ هو متجه الأساس القياسي المقابل لعقدة المصدر s، و α ∈ (0,1) هو عامل التخفيف، و A و D هما مصفوفة المجاورة ومصفوفة الدرجة للرسم البياني غير الموجه G(V,E) على التوالي.

دافع البحث

  1. الأهمية: PPR هو أداة أساسية في تحليل الرسوم البيانية، مع تطبيقات واسعة في التجميع المحلي، نمذجة عمليات الانتشار، وشبكات الرسوم البيانية العصبية
  2. القيود الحالية:
    • الطرق القياسية مثل APPR لها تعقيد زمني قدره O(1/(αε))
    • تواجه الطرق المعجلة تحديات في كسر الرتابة المتبقية بسبب حدود الزخم
    • قد تصل الطرق المعجلة الحالية إلى الرسم البياني بأكمله، مما يؤدي إلى تعقيد زمني قدره O(m/√α)
  3. مسائل مفتوحة: هل توجد طريقة محلية معجلة بتعقيد زمني يعتمد على 1/√α بدلاً من 1/α؟

المساهمات الأساسية

  1. إطار عمل AESP: يقترح إطار عمل عمليات المجموعات المتطورة المعجلة (AESP)، باستخدام O~(1/α)\tilde{O}(1/\sqrt{α}) من عمليات المجموعات المتطورة القصيرة بدلاً من عملية واحدة طويلة
  2. الضمانات النظرية: يؤسس تعقيد زمني قدره O~(vol(St)/(αγt))\tilde{O}(\text{vol}(S_t)/(\sqrt{α}γ_t))، مطابقة لحدود التسريع المتوقعة في الأدبيات الموجودة
  3. ضمانات المحلية: يثبت حد أعلى لـ vol(St)/γt\text{vol}(S_t)/γ_t قدره min⁡{O(R2/ε2),2m}\min\{O(R^2/ε^2), 2m\}، مما يحقق تعقيداً مستقلاً عن حجم الرسم البياني عندما يكون 1/ε2≪m1/ε^2 \ll m
  4. التحقق التجريبي: يتحقق من فعالية الطريقة على رسوم بيانية حقيقية واسعة النطاق، مما يوضح تأثير التسريع الكبير في المراحل المبكرة

شرح الطريقة

تعريف المهمة

بالنظر إلى معامل الدقة ε، تصميم خوارزمية محلية لحساب تقريب ε π̂ يرضي ∥D−1(π^−π)∥∞≤ε\|D^{-1}(π̂ - π)\|_∞ ≤ ε، مع تجنب الوصول إلى الرسم البياني بأكمله.

الفكرة الأساسية: عمليات المجموعات المتطورة المتداخلة

1. إعادة صياغة المشكلة

إعادة صياغة النظام الخطي كمشكلة تحسين محدبة بقوة:

min f(x) = (1/2)x⊤Qx - αx⊤D^(-1/2)b

حيث Q = ((1+α)/2)I - ((1-α)/2)D^(-1/2)AD^(-1/2)، والقيم الذاتية λ(Q) ∈ α,1.

2. تعريف ESP المتداخل

في تكرار الحلقة الخارجية t، يحافظ المحل المحلي M على سلسلة من مجموعات نشطة {S_t^(k)}_{k≥0} على تكرارات الحلقة الداخلية k، مع تحديثات مقتصرة على العقد في المجموعة النشطة.

3. قواعد تحديث AESP

x^(t) = M(φ_t, y^(t-1), η, α, b, G)
y^(t) = x^(t) + β_t(x^(t) - x^(t-1))

حيث β_t هو وزن الزخم، و M هو المشغل المحلي.

المشغل التقريبي غير الدقيق المحلي

LOCGD (Local Gradient Descent)

z_t^(k+1) = z_t^(k) - (2∇h_t(z_t^(k)) ∘ 1_{S_t^k})/(1 + α + 2η)

مجموعة العقد النشطة: Stk={u:∣∇uht−1/2(zt(k))∣≥εt}S_t^k = \{u : |∇_u h_t^{-1/2}(z_t^{(k)})| ≥ ε_t\}

LOCAPPR (Local APPR)

تحديث على مستوى الإحداثيات لـ ui∈Stku_i ∈ S_t^k:

z_t^(k_{i+1}) = z_t^(k_i) - (2∇h_t(z_t^{(k_i)}) ∘ 1_{u_i})/(1 + α + 2η)

نقاط الابتكار التقني

  1. الحفاظ على الرتابة: من خلال حل نظام خطي PPR منتظم برقم شرط ثابت، يضمن الانخفاض الرتيب لـ ℓ₁-norm للتدرج المقاس بـ D^{1/2}
  2. التحكم في المحلية: إدخال ثابت R لتحديد حدود نسبة التدرج في عملية ESP المتداخلة
  3. التوازن بين التسريع والمحلية: تحقيق توازن بين اعتماد رقم الشرط 1/α وتعقيد الوقت لكل جولة O(R²/ε²)

إعداد التجارب

مجموعات البيانات

تستخدم التجارب 19 رسم بياني من العالم الحقيقي، تتراوح الأحجام من صغيرة إلى ضخمة جداً:

  • نطاق متوسط: com-dblp (317K عقدة، 1M حافة)
  • نطاق كبير: ogb-mag240m (244M عقدة، 1.7B حافة)، ogbn-papers100M (111M عقدة، 1.6B حافة)
  • أخرى: com-friendster، wiki-en21 وغيرها

مقاييس التقييم

  • قياس الخطأ: log⁡∥D−1(π^−π)∥∞\log \|D^{-1}(π̂-π)\|_∞
  • قياس الكفاءة: عدد العمليات، وقت التشغيل
  • نسبة التسريع: تحسن الأداء بالنسبة إلى طرق الأساس

طرق المقارنة

  • APPR: خوارزمية PageRank الشخصية التقريبية القياسية
  • APPR-opt: APPR باستخدام حجم الخطوة الأمثل
  • LOCGD: الانحدار المتدرج المحلي
  • ASPR: PageRank الشخصي المتناثر المعجل
  • FISTA: خوارزمية الانكماش والعتبة التكرارية السريعة

تفاصيل التنفيذ

  • عامل التخفيف: α = 0.01، 0.1
  • عتبة الدقة: ε = 10⁻⁶
  • اختيار عشوائي لـ 5 عقد مصدر للاختبار
  • تنفيذ Python مع تسريع numba

نتائج التجارب

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

أداء الرسوم البيانية الكبيرة

على أربعة رسوم بيانية كبيرة (ogb-mag240m، ogbn-papers100M، com-friendster، wiki-en21):

  • AESP-LOCAPPR يُظهر أفضل أداء، بفضل تحديثات الإحداثيات عبر الإنترنت
  • التسريع المبكر: تحقق طرق AESP تقاربًا أسرع من طرق الأساس في المراحل المبكرة
  • تقليل العمليات: تقليل 2-10 مرات في عدد العمليات مقارنة بـ APPR

تحليل الاعتماد على α

عندما يكون α صغيراً، يسرع AESP الطرق المحلية القياسية بشكل كبير:

  • اختبار في النطاق α ∈ 10⁻³، 10⁻¹
  • تزداد نسبة التسريع مع انخفاض α، مما يتحقق من الاعتماد على √α
  • انخفاض كبير في وقت التشغيل وعدد العمليات

مقارنة استراتيجيات التهيئة

مقارنة ثلاث استراتيجيات تهيئة لـ z_t^(0):

  1. البدء البارد: z_t^(0) = 0
  2. التقدير السابق: z_t^(0) = x^(t-1)
  3. تهيئة الزخم: z_t^(0) = y^(t-1) (موصى به)

تُظهر استراتيجية تهيئة الزخم أفضل أداء، مما يتطلب أقل عدد من تكرارات الحلقة الخارجية.

تجارب الاستئصال

تحليل الثابت R

  • يبقى R ثابتاً صغيراً (1.0-1.4) عبر 19 رسم بياني
  • R غير حساس لحجم الرسم البياني ورقم الشرط
  • يتحقق من معقولية افتراض R المحدود في التحليل النظري

تحليل نسبة vol(S_t)/γ_t

التحقق التجريبي من الحد النظري vol(St)/γt≤min⁡{Ct0/εt,2m}\text{vol}(S_t)/γ_t ≤ \min\{C_t^0/ε_t, 2m\}.

الأعمال ذات الصلة

طرق حساب PPR

  • الطرق التكرارية: طريقة التدرج المترافق، طريقة Chebyshev، تعقيد O(m/√α)
  • الطرق المحلية: APPR (O(1/(αε)))، طرق متغيرة (O(1/((α+μ²)ε)))
  • محاولات التسريع: FISTA، الاقتران الخطي يكسر الرتابة، لا يمكن ضمان المحلية

عمليات المجموعات المتطورة

  • المفهوم الذي قدمه Morris و Peres، يُستخدم لتحليل أوقات الخلط
  • طريقة Chebyshev المحلية لـ Zhou وآخرون، لكن تفتقر إلى ضمانات التقارب

التحسين المعجل

  • إطار عمل Catalyst: طريقة نقطة تقريبية معجلة غير دقيقة
  • تكييف هذه الورقة مع الطرق المحلية، مع الحفاظ على الرتابة

الخلاصة والمناقشة

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

  1. اختراق نظري: تحقيق أول تسريع محلي قابل للإثبات لحساب PPR، مع تحسين تعقيد الوقت من O(1/α) إلى O(1/√α)
  2. الجدوى العملية: عندما يكون ε ≥ 1/√m، يكون تعقيد الخوارزمية مستقلاً عن حجم الرسم البياني
  3. العمومية: يمكن توسيع الإطار إلى الأشكال المتغيرة والمشاكل ذات الصلة الأخرى

القيود

  1. حد الثابت R: لا يمكن تحديد R بشكل عام باستخدام حجم الرسم البياني أو معاملات الإدخال
  2. الاعتماد على ε²: عندما يكون ε < 1/√m، ينخفض الحد المحلي إلى O(m/√α)
  3. الفجوة بين النظرية والممارسة: قد يؤدي التقدير المحافظ لـ ε_t إلى حدود دون المستوى الأمثل

الاتجاهات المستقبلية

  1. تحسين الحدود: استكشاف ما إذا كان يمكن تحقيق التعقيد المتوقع O(1/(√αε))
  2. القضاء على الاعتماد على R: من خلال القيود أو إعادة التشغيل التكيفية
  3. توسيع التطبيقات: تطبيق التقنيات على PPR ثنائي الاتجاه وتقدير PPR أحادي المصدر

التقييم المتعمق

المميزات

  1. مساهمة نظرية كبيرة: حل التخمين المفتوح في الأدبيات، وإنشاء ضمانات نظرية صارمة
  2. قوة الابتكار الطريقة: دمج ذكي لإطار عمل Catalyst مع عمليات المجموعات المتطورة المحلية
  3. تجارب شاملة: التحقق على 19 رسم بياني بأحجام مختلفة، من صغيرة إلى ضخمة جداً
  4. الكتابة الواضحة: الاشتقاق الرياضي صارم، وصف الخوارزمية مفصل

أوجه القصور

  1. قيود الجدوى: عندما يكون ε صغيراً جداً، لا تكون المزايا واضحة، مشكلة تحديد R تؤثر على التطبيق العملي
  2. تعقيد التنفيذ: تزيد البنية المتداخلة وضبط المعاملات من صعوبة التنفيذ
  3. المقارنة غير الشاملة: تفتقر إلى مقارنة مفصلة مع أحدث الطرق المعجلة

التأثير

  1. القيمة الأكاديمية: توفير أفكار جديدة لتسريع خوارزميات الرسوم البيانية، ذات أهمية نظرية كبيرة
  2. القيمة العملية: لديها إمكانية التطبيق في تحليل الرسوم البيانية واسعة النطاق وأنظمة التوصيات
  3. قابلية إعادة الإنتاج: الكود مفتوح المصدر، إعدادات التجارب مفصلة

السيناريوهات المناسبة

  1. تحليل الرسوم البيانية الكبيرة: خاصة عندما لا تكون متطلبات الدقة عالية جداً (ε ≥ 1/√m)
  2. أنظمة التوصيات في الوقت الفعلي: تحتاج إلى حساب سريع لنقاط الأهمية المحلية
  3. شبكات الرسوم البيانية العصبية: كخطوة معالجة مسبقة لحساب أهمية العقد

المراجع

تستشهد هذه الورقة بـ 52 مرجعاً ذا صلة، تغطي حساب PPR والتحسين المعجل والخوارزميات المحلية وغيرها من المجالات المهمة، مما يوفر أساساً نظرياً متيناً للبحث.

التقييم الشامل: هذه ورقة عالية الجودة تجمع بين النظرية والممارسة، محققة تقدماً كبيراً في مشكلة تسريع حساب PPR المهمة. على الرغم من وجود بعض القيود النظرية، فإن ابتكارها وجدواها العملية تجعلها مساهمة مهمة في هذا المجال.