2025-11-14T22:58:11.335175

Revisiting Node Affinity Prediction in Temporal Graphs

Mantri, Feldman, Eliasof et al.
Node affinity prediction is a common task that is widely used in temporal graph learning with applications in social and financial networks, recommender systems, and more. Recent works have addressed this task by adapting state-of-the-art dynamic link property prediction models to node affinity prediction. However, simple heuristics, such as Persistent Forecast or Moving Average, outperform these models. In this work, we analyze the challenges in training current Temporal Graph Neural Networks for node affinity prediction and suggest appropriate solutions. Combining the solutions, we develop NAViS - Node Affinity prediction model using Virtual State, by exploiting the equivalence between heuristics and state space models. While promising, training NAViS is non-trivial. Therefore, we further introduce a novel loss function for node affinity prediction. We evaluate NAViS on TGB and show that it outperforms the state-of-the-art, including heuristics. Our source code is available at https://github.com/orfeld415/NAVIS
academic

إعادة النظر في التنبؤ بتقاربية العقد في الرسوم البيانية الزمنية

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

  • معرّف الورقة: 2510.06940
  • العنوان: Revisiting Node Affinity Prediction in Temporal Graphs
  • المؤلفون: Krishna Sri Ipsit Mantri, Or Feldman, Moshe Eliasof, Chaim Baskin
  • التصنيف: cs.LG (تعلم الآلة)
  • حالة النشر: نسخة أولية. قيد المراجعة
  • رابط الورقة: https://arxiv.org/abs/2510.06940
  • رابط الكود: https://github.com/orfeld415/NAVIS

الملخص

يعتبر التنبؤ بتقاربية العقد مهمة مهمة في تعلم الرسوم البيانية الزمنية، مع تطبيقات واسعة في الشبكات الاجتماعية والشبكات المالية وأنظمة التوصية. على الرغم من أن الأبحاث الحديثة تعالج مهمة التنبؤ بتقاربية العقد من خلال تكييف نماذج التنبؤ بالروابط الديناميكية المتقدمة، إلا أن الطرق الاستكشافية البسيطة (مثل التنبؤ المستمر والمتوسط المتحرك) تتفوق على هذه النماذج المعقدة. تحلل هذه الورقة تحديات التدريب في شبكات الرسوم البيانية العصبية الزمنية الحالية في مهمة التنبؤ بتقاربية العقد، وتقترح حلولاً مناسبة. من خلال دمج هذه الحلول، طور المؤلفون نموذج NAVIS (نموذج التنبؤ بتقاربية العقد باستخدام الحالة الافتراضية)، والذي يحقق التنبؤ بتقاربية العقد من خلال الاستفادة من التكافؤ بين الطرق الاستكشافية ونماذج فضاء الحالة.

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

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

يهدف التنبؤ بتقاربية العقد إلى التنبؤ بقوة التفاعل بين عقدة معينة وجميع العقد الأخرى في الوقت المستقبلي. يختلف هذا عن مهام التنبؤ بالروابط التقليدية. يركز التنبؤ بالروابط على ما إذا كانت حافة معينة ستظهر، بينما يتطلب التنبؤ بالتقاربية ترتيباً كاملاً لجميع الجيران المحتملين، مما يجعل المهمة أكثر تحدياً وأقرب إلى احتياجات التطبيقات العملية.

المشاكل الأساسية

  1. مفارقة الأداء: شبكات الرسوم البيانية العصبية الزمنية (TGNNs) المعقدة لا تؤدي بشكل أفضل من الطرق الاستكشافية البسيطة في مهمة التنبؤ بتقاربية العقد
  2. قيود القدرة التعبيرية: لا يمكن لـ TGNNs الحالية تمثيل العمليات الأساسية البسيطة مثل المتوسط المتحرك
  3. عدم توافق دالة الخسارة: خسارة الإنتروبيا المتقاطعة لا تتطابق مع طبيعة الترتيب لمهام التقاربية
  4. استخدام المعلومات غير الكافي: لا تستفيد TGNNs بشكل كافٍ من الديناميكيات الزمنية العالمية ومعلومات التبعيات طويلة الأجل

الدافع البحثي

اكتشف المؤلفون من خلال التحليل النظري أن الطرق الاستكشافية البسيطة هي في الواقع حالات خاصة من نماذج فضاء الحالة الخطية (SSMs)، مما يوفر أساساً نظرياً لتصميم معماريات TGNN أقوى.

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

  1. المساهمة النظرية: إثبات أن الطرق الاستكشافية البسيطة هي حالات خاصة من نماذج SSM الخطية، وتصميم معمارية TGNN بناءً على هذا الربط يمكنها تعميم الطرق الاستكشافية
  2. الابتكار المعماري: اقتراح نموذج NAVIS، الذي يجمع بين الحالة العالمية الافتراضية وآليات فضاء الحالة الخطية، مما يحل بفعالية مشكلة التنبؤ بتقاربية العقد
  3. تحسين دالة الخسارة: تحليل أوجه القصور في خسارة الإنتروبيا المتقاطعة في التنبؤ بالتقاربية، واقتراح بديل Lambda Loss المستند إلى الترتيب
  4. التحقق التجريبي: التحقق من فعالية الطريقة على معايير TGB وعدة مجموعات بيانات، مع تفوق ثابت على الطرق الموجودة والخطوط الأساسية الاستكشافية

شرح الطريقة

تعريف المهمة

بالنظر إلى رسم بياني ديناميكي بوقت مستمر (CTDG): Gt={(uj,vj,τj,wj)}j=1J(t)G_t = \{(u_j, v_j, \tau_j, w_j)\}_{j=1}^{J(t)}

بالنسبة لعقدة الاستعلام u∈Vu \in V والوقت المستقبلي t+>tt^+ > t، الهدف هو التنبؤ بمتجه درجات التقاربية: s=Fθ(u,Gt,t+)∈R∣V∣s = F_\theta(u, G_t, t^+) \in \mathbb{R}^{|V|}

الأساس النظري

النظرية 1 (نماذج SSM الخطية تعمم الطرق الاستكشافية الأساسية): دع HH تكون مجموعة الطرق الاستكشافية الأساسية (PF, SMA, EMA)، و Flin-SSMF_{\text{lin-SSM}} تكون مجموعة الخرائط التي يمكن تحقيقها بواسطة نموذج SSM خطي، إذاً: H⊊Flin-SSMH \subsetneq F_{\text{lin-SSM}}

النظرية 2 (قيود التعبير في RNN/LSTM/GRU): لا يمكن لوحدات RNN أو LSTM أو GRU القياسية تمثيل أبسط طريقة استكشافية للتنبؤ المستمر (PF)، أي أنه لا توجد معاملات لجميع تسلسلات الإدخال بحيث hi=xih_i = x_i.

معمارية نموذج NAVIS

يستخدم NAVIS آلية فضاء الحالة الخطية للحفاظ على حالة كل عقدة h∈Rdh \in \mathbb{R}^d والحالة العالمية الافتراضية g∈Rdg \in \mathbb{R}^d:

zh = σ(Wxh*x + Whh*hi-1 + bh)
hi = zh ⊙ hi-1 + (1-zh) ⊙ x
zs = σ(Wxs*x + Whs*hi + Wgs*g + bs)  
s = zs ⊙ hi + (1-zs) ⊙ x

حيث:

  • xx: متجه التقاربية السابق
  • hi−1,hih_{i-1}, h_i: الحالة السابقة والحالة المحدثة
  • gg: المتجه العالمي الافتراضي
  • ss: متجه التقاربية المتنبأ به
  • zh,zsz_h, z_s: آليات التحكم التكيفية

الخصائص التصميمية الرئيسية

  1. آلية التحديث الخطية: الحفاظ على التشابه المفاهيمي مع EMA، مع السماح بالتعديل التكيفي في وقت التشغيل
  2. الحالة العالمية الافتراضية: التقاط الاتجاهات العالمية من خلال الحفاظ على مخزن مؤقت لمتجهات التقاربية الأخيرة
  3. التوافق مع آلية t-Batch: لا يعتمد على الحالات المخفية للجيران، مما يدعم المعالجة الدفعية الفعالة
  4. قابلية التوسع: التكيف مع الرسوم البيانية الكبيرة من خلال تقليل خط أنابيب التنبؤ بالتقاربية

تصميم دالة الخسارة

تحليل المشكلة: النظرية 3 (دون الأمثل للإنتروبيا المتقاطعة للترتيب): توجد عدد لا نهائي من الثلاثيات (y,s1,s2)(y, s_1, s_2) حيث rank(s1)=rank(y)\text{rank}(s_1) = \text{rank}(y) و rank(s2)≠rank(y)\text{rank}(s_2) \neq \text{rank}(y)، لكن ℓCE(s1,y)>ℓCE(s2,y)\ell_{CE}(s_1, y) > \ell_{CE}(s_2, y).

الحل: استخدام Lambda Loss: ℓLambda(s,y)=∑yi>yjlog⁡2(11+e−σ(sπi−sπj))δij∣Aπi−Aπj∣\ell_{\text{Lambda}}(s,y) = \sum_{y_i > y_j} \log_2\left(\frac{1}{1 + e^{-\sigma(s_{\pi_i} - s_{\pi_j})}}\right) \delta_{ij} |A_{\pi_i} - A_{\pi_j}|

مع الجمع بين تنظيم الهامش الزوجي: ℓReg(s,y)=∑yi>yjmax⁡(0,−(sπi−sπj)+Δ)\ell_{\text{Reg}}(s,y) = \sum_{y_i > y_j} \max(0, -(s_{\pi_i} - s_{\pi_j}) + \Delta)

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

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

مجموعات بيانات TGB:

  • tgbn-trade: شبكة التجارة الزراعية بين الدول للأمم المتحدة 1986-2016 (255 عقدة، 468,245 حافة)
  • tgbn-genre: شبكة تفاعل المستخدم مع نوع الموسيقى (1,505 عقدة، 17,858,395 حافة)
  • tgbn-reddit: شبكة تفاعل المستخدم مع subreddit (11,766 عقدة، 27,174,118 حافة)
  • tgbn-token: شبكة تفاعل المحفظة مع رموز العملات المشفرة (61,756 عقدة، 72,936,998 حافة)

مجموعات بيانات التنبؤ بالروابط المحولة:

  • Wikipedia: شبكة تفاعل المحرر مع المقالة
  • Flights: شبكة مسارات المطارات أثناء COVID-19
  • USLegis: شبكة التعاون في مجلس الشيوخ الأمريكي
  • UNVote: شبكة التصويت في الجمعية العامة للأمم المتحدة

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

  • المقياس الرئيسي: NDCG@10 (الكسب التراكمي المخفوض المعياري)
  • إعداد التجارب: تقسيم زمني 70%-15%-15%، 50 حقبة، حجم دفعة 200

طرق المقارنة

  • الطرق الاستكشافية: Persistent Forecast, Moving Average, Historical Average
  • طرق TGNN: JODIE, TGAT, CAWN, TCL, GraphMixer, DyGFormer, DyRep, TGN, TGNv2

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

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

الأداء على مجموعات بيانات TGB (NDCG@10):

  • tgbn-trade: NAVIS 0.863 مقابل أفضل خط أساسي TGNv2 0.735 (+17.4%)
  • tgbn-genre: NAVIS 0.520 مقابل أفضل خط أساسي TGNv2 0.469 (+10.9%)
  • tgbn-reddit: NAVIS 0.552 مقابل أفضل خط أساسي TGNv2 0.507 (+8.9%)
  • tgbn-token: NAVIS 0.444 مقابل أفضل خط أساسي TGNv2 0.294 (+51.0%)

الأداء على المجموعات البيانات المحولة:

  • Wikipedia: NAVIS 0.573 مقابل TGNv2 0.433 (+32.3%)
  • Flights: NAVIS 0.499 مقابل TGNv2 0.299 (+66.9%)
  • USLegis: NAVIS 0.347 مقابل TGNv2 0.253 (+37.2%)
  • UNVote: NAVIS 0.952 مقابل TGNv2 0.813 (+17.1%)

الدراسات الاستئصالية

تحقق الدراسات الاستئصالية من أهمية كل مكون:

  • التحديث الخطي للحالة مقابل GRU: 0.863 مقابل 0.850 على tgbn-trade
  • تضمين المتجه العالمي: تحسن حوالي 1-2 نقطة مئوية
  • خسارة الترتيب مقابل الإنتروبيا المتقاطعة: تحسن كبير في الأداء

الاكتشافات الرئيسية

  1. تأكيد مزايا الطرق الاستكشافية: الطرق الاستكشافية البسيطة تتفوق فعلاً على TGNNs المعقدة
  2. أهمية المعلومات العالمية: تلتقط الحالة العالمية الافتراضية اتجاهات مستوى الشبكة بفعالية
  3. توافق دالة الخسارة: خسارة الترتيب الحساسة حاسمة للتنبؤ بالتقاربية
  4. التحسن المتسق: حقق NAVIS تحسناً متسقاً على جميع مجموعات البيانات

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

القدرة التعبيرية للرسوم البيانية الزمنية

يركز البحث التقليدي على القدرة التعبيرية الهيكلية المقاسة بواسطة اختبار WL، بينما تركز هذه الورقة على القدرة التعبيرية الوظيفية، أي القدرة على تمثيل عمليات رياضية محددة.

الطرق الاستكشافية ونماذج فضاء الحالة

اكتشفت الأبحاث الحديثة أن الطرق الاستكشافية البسيطة تتفوق على TGNNs المعقدة في عدة معايير، وتستفيد هذه الورقة لأول مرة بشكل صريح من التكافؤ الشكلي بين الطرق الاستكشافية و SSMs لتصميم المعمارية.

شبكات الرسوم البيانية العصبية الزمنية

تشمل الطرق الموجودة معماريات قائمة على الذاكرة (TGN, DyRep) وغير قائمة على الذاكرة (DyGFormer, GraphMixer)، لكن لا يمكن لأي منها التعامل بفعالية مع الاحتياجات الخاصة للتنبؤ بتقاربية العقد.

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

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

  1. يعود القصور في TGNNs الحالية في التنبؤ بتقاربية العقد إلى قيود القدرة التعبيرية وعدم توافق أهداف التدريب
  2. توفر نماذج فضاء الحالة الخطية إطار عمل نظري لتعميم الطرق الاستكشافية
  3. يحل NAVIS بفعالية مشكلة التنبؤ بتقاربية العقد من خلال الجمع بين الحالة العالمية الافتراضية وخسارة الترتيب الحساسة

القيود

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

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

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

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

المزايا

  1. مساهمة نظرية قوية: إنشاء ربط بين الطرق الاستكشافية و SSMs من خلال إثبات رياضي صارم
  2. تحليل المشكلة العميق: تحليل منهجي لأوجه القصور في TGNNs في التنبؤ بتقاربية العقد
  3. تصميم الطريقة المعقول: تصميم NAVIS له أساس نظري واضح واعتبارات عملية
  4. التجارب الشاملة: التجارب الموسعة على عدة مجموعات بيانات تتحقق من فعالية الطريقة
  5. الكتابة الواضحة: هيكل الورقة واضح، والتفاصيل التقنية موصوفة بدقة

أوجه القصور

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

التأثير

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

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

  1. أنظمة التوصية: التنبؤ بتقاربية المستخدم تجاه المنتجات
  2. الشبكات الاجتماعية: التنبؤ بقوة التفاعل بين المستخدمين
  3. الشبكات المالية: التنبؤ بقوة علاقات التداول
  4. شبكات سلسلة التوريد: التنبؤ بعلاقات التعاون

التقييم الإجمالي: هذه ورقة بحثية عالية الجودة، تكشف من خلال التحليل النظري العميق عن أوجه القصور في الطرق الموجودة وتقترح حلاً فعالاً. تصميم نموذج NAVIS معقول، ونتائج التجارب مقنعة، وله مساهمة إيجابية في مجال تعلم الرسوم البيانية الزمنية. تكمن القيمة الرئيسية للورقة في توفير منظور نظري جديد وإطار عمل طريقة عملي.