2025-11-20T09:28:14.240195

Lightweight and Interpretable Transformer via Mixed Graph Algorithm Unrolling for Traffic Forecast

Qi, Do, Liu et al.
Unlike conventional "black-box" transformers with classical self-attention mechanism, we build a lightweight and interpretable transformer-like neural net by unrolling a mixed-graph-based optimization algorithm to forecast traffic with spatial and temporal dimensions. We construct two graphs: an undirected graph $\mathcal{G}^u$ capturing spatial correlations across geography, and a directed graph $\mathcal{G}^d$ capturing sequential relationships over time. We predict future samples of signal $\mathbf{x}$, assuming it is "smooth" with respect to both $\mathcal{G}^u$ and $\mathcal{G}^d$, where we design new $\ell_2$ and $\ell_1$-norm variational terms to quantify and promote signal smoothness (low-frequency reconstruction) on a directed graph. We design an iterative algorithm based on alternating direction method of multipliers (ADMM), and unroll it into a feed-forward network for data-driven parameter learning. We insert graph learning modules for $\mathcal{G}^u$ and $\mathcal{G}^d$ that play the role of self-attention. Experiments show that our unrolled networks achieve competitive traffic forecast performance as state-of-the-art prediction schemes, while reducing parameter counts drastically. Our code is available in https://github.com/SingularityUndefined/Unrolling-GSP-STForecast .
academic

محول خفيف الوزن وقابل للتفسير عبر فك تشفير خوارزمية الرسم البياني المختلط للتنبؤ بحركة المرور

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

  • معرّف الورقة: 2505.13102
  • العنوان: Lightweight and Interpretable Transformer via Mixed Graph Algorithm Unrolling for Traffic Forecast
  • المؤلفون: Ji Qi, Mingxiao Liu, Tam Thuc Do, Yuzhe Li, Zhuoshi Pan, Gene Cheung, H. Vicky Zhao
  • التصنيف: cs.LG cs.AI eess.SP
  • تاريخ النشر: 12 أكتوبر 2025 (arXiv v2)
  • رابط الورقة: https://arxiv.org/abs/2505.13102

الملخص

تقترح هذه الورقة نموذج محول خفيف الوزن وقابل للتفسير قائم على فك تشفير خوارزمية الرسم البياني المختلط للتنبؤ بحركة المرور. بخلاف محولات "الصندوق الأسود" التقليدية، يبني هذا النهج شبكة عصبية تشبه المحول قابلة للتفسير من خلال فك تشفير خوارزمية تحسين الرسم البياني المختلط. يبني النموذج رسمين بيانيين: رسم بياني غير موجه Gu\mathcal{G}^u يلتقط الارتباطات الجغرافية المكانية، ورسم بياني موجه Gd\mathcal{G}^d يلتقط العلاقات الزمنية. من خلال تصميم حدود تباين معايير ℓ2\ell_2 و ℓ1\ell_1 جديدة لتحديد وتعزيز سلاسة الإشارة على الرسم البياني الموجه، وتصميم خوارزمية تكرارية بناءً على طريقة الاتجاهات المتناوبة للمضاعفات (ADMM)، يتم فكها كشبكة تغذية أمامية لتعلم المعاملات المدفوع بالبيانات. تُظهر التجارب أن النموذج يحافظ على أداء تنبؤ حركة مرور تنافسية مع تقليل عدد المعاملات بشكل كبير.

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

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

التنبؤ بحركة المرور هو مشكلة نمذجة بيانات زمكانية مهمة تتطلب التقاط:

  1. الارتباط المكاني: الارتباط بين محطات المراقبة القريبة جغرافياً
  2. الاعتماد الزمني: تأثير الملاحظات التاريخية على المستقبل

قيود الطرق الموجودة

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

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

  1. الحاجة الملحة للصناعة إلى نماذج خفيفة الوزن
  2. فك تشفير الخوارزمية (Algorithm Unrolling) يوفر نموذجاً جديداً يجمع بين النهج المدفوع بالنموذج والمدفوع بالبيانات
  3. الأعمال الموجودة تستخدم فقط رسوماً بيانية موجبة غير موجهة، مما يفشل في نمذجة العلاقات الزمكانية المعقدة بفعالية

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

  1. أول اقتراح لفك تشفير خوارزمية الرسم البياني المختلط: دمج الرسوم البيانية غير الموجهة (المكانية) والموجهة (الزمنية) لنمذجة العلاقات الزمكانية المعقدة
  2. حدود تنظيم رسم بياني موجه مبتكرة: تصميم منظم لابلاسيان الرسم البياني الموجه (DGLR) والتباين الكلي للرسم البياني الموجه (DGTV)
  3. محول خفيف الوزن وقابل للتفسير: تحقيق تقليل كبير في المعاملات (6.4% فقط من PDFormer) من خلال فك تشفير خوارزمية ADMM
  4. مساهمة نظرية: إثبات أن تعريف التردد للرسم البياني الموجه يتحلل إلى ترددات فورييه الكلاسيكية في حالة الرسم البياني الخطي الموجه غير المرجح

شرح الطريقة

تعريف المهمة

بالنظر إلى ملاحظات من N محطة مراقبة على T+1 خطوة زمنية سابقة، التنبؤ بحالة حركة المرور للخطوات S الزمنية القادمة. الإدخال هو إشارة زمكانية مراقبة جزئياً y∈RMy \in \mathbb{R}^M، والإخراج هو إشارة زمكانية كاملة x∈RN(T+S+1)x \in \mathbb{R}^{N(T+S+1)}.

بناء الرسم البياني المختلط

الرسم البياني غير الموجه Gu\mathcal{G}^u

  • ربط العقد في مواقع جغرافية قريبة في نفس الوقت
  • التقاط الارتباط المكاني
  • استخدام مصفوفة التجاور المتماثلة WuW^u

الرسم البياني الموجه Gd\mathcal{G}^d

  • الاتصال من عقدة في الوقت τ\tau إلى عقد نفس الموقع في الأوقات τ+1,...,τ+W\tau+1, ..., \tau+W
  • التقاط العلاقات السببية الزمنية
  • استخدام مصفوفة التجاور غير المتماثلة WdW^d

تصميم حدود التباين للرسم البياني الموجه

حد معيار ℓ2\ell_2: منظم لابلاسيان الرسم البياني الموجه (DGLR)

xTLrdx=xT(Lrd)TLrdx=∥x−Wrdx∥22x^T\mathcal{L}_r^d x = x^T(L_r^d)^T L_r^d x = \|x - W_r^d x\|_2^2

حيث Lrd=I−WrdL_r^d = I - W_r^d هي مصفوفة لابلاسيان المشي العشوائي، و Wrd=(Dd)−1WdW_r^d = (D^d)^{-1}W^d هي مصفوفة التجاور العشوائية الصفية.

حد معيار ℓ1\ell_1: التباين الكلي للرسم البياني الموجه (DGTV)

∥Lrdx∥1=∑j∈Sˉ∣xj−∑iwj,ixi∣\|L_r^d x\|_1 = \sum_{j \in \bar{S}} |x_j - \sum_i w_{j,i} x_i|

دالة الهدف للتحسين

min⁡x∥y−Hx∥22+μuxTLux+μd,2xTLrdx+μd,1∥Lrdx∥1\min_x \|y - Hx\|_2^2 + \mu_u x^T L^u x + \mu_{d,2} x^T \mathcal{L}_r^d x + \mu_{d,1} \|L_r^d x\|_1

حيث HH هي مصفوفة العينة، و μu,μd,2,μd,1\mu_u, \mu_{d,2}, \mu_{d,1} هي معاملات الوزن.

تصميم خوارزمية ADMM

من خلال إدخال متغير مساعد ϕ\phi، يتم تحويل مشكلة التحسين إلى: min⁡x,ϕ∥y−Hx∥22+μuxTLux+μd,2xTLrdx+μd,1∥ϕ∥1\min_{x,\phi} \|y - Hx\|_2^2 + \mu_u x^T L^u x + \mu_{d,2} x^T \mathcal{L}_r^d x + \mu_{d,1} \|\phi\|_1s.t. ϕ=Lrdx\text{s.t. } \phi = L_r^d x

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

  1. مشكلة xx الفرعية: حل النظام الخطي من خلال طريقة التدرج المترافق
  2. مشكلة ϕ\phi الفرعية: عملية الحد الناعم ϕiτ+1=sign(δ)⋅max⁡(∣δ∣−ρ−1μd,1,0)\phi_i^{\tau+1} = \text{sign}(\delta) \cdot \max(|\delta| - \rho^{-1}\mu_{d,1}, 0) حيث δ=(Lrd)ixτ+1−ρ−1γiτ\delta = (L_r^d)_i x^{\tau+1} - \rho^{-1}\gamma_i^\tau

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

تعلم الرسم البياني غير الموجه (UGL)

استخدام مسافة ماهالانوبيس لحساب التشابه بين العقد: du(i,j)=(fiu−fju)TM(fiu−fju)d^u(i,j) = (f_i^u - f_j^u)^T M (f_i^u - f_j^u)

يتم حساب أوزان الحافة من خلال دالة أسية معايرة: wi,ju=exp⁡(−du(i,j))∑l∈Niexp⁡(−du(i,l))∑k∈Njexp⁡(−du(k,j))w_{i,j}^u = \frac{\exp(-d^u(i,j))}{\sqrt{\sum_{l \in \mathcal{N}_i} \exp(-d^u(i,l))} \sqrt{\sum_{k \in \mathcal{N}_j} \exp(-d^u(k,j))}}

تعلم الرسم البياني الموجه (DGL)

حساب أوزان الحافة الموجهة بطريقة مماثلة باستخدام مصفوفة القياس PP.

معمارية الشبكة

تنفيذ كل تكرار من ADMM كطبقة عصبية:

  • 5 كتل ADMM، كل كتلة بها 25 طبقة
  • إدراج وحدة تعلم الرسم البياني قبل كل كتلة
  • استخدام آلية الانتباه متعددة الرؤوس (4 وحدات تعلم رسم بياني متوازية)

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

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

  • METR-LA: بيانات سرعة حركة المرور في لوس أنجلوس، 207 عقدة، 1315 حافة
  • PEMS03: بيانات تدفق حركة المرور، 358 عقدة، 547 حافة
  • فترة العينة: 5 دقائق
  • تقسيم البيانات: 6:2:2 (تدريب:التحقق:اختبار)

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

  • RMSE: جذر متوسط مربع الخطأ
  • MAE: متوسط الخطأ المطلق
  • MAPE: متوسط نسبة الخطأ المطلق

طرق المقارنة

تشمل 6 فئات من طرق الأساس:

  • قائمة على النموذج: VAR
  • طرق GNN: STGCN, STSGCN
  • طرق GAT: GMAN, ST-Wave
  • طرق Transformer: PDFormer, STAEformer
  • طرق الرسم البياني التكيفي: Graph WaveNet, AGCRN
  • نماذج خطية بسيطة: STID, SimpleTM

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

  • مدة التنبؤ: 30/60/120 دقيقة (6/12/24 خطوة)
  • نافذة تاريخية: 60 دقيقة (12 خطوة)
  • محسّن: Adam، معدل التعلم 5×10⁻⁴
  • دالة الخسارة: خسارة Huber (δ=1)
  • الأجهزة: NVIDIA GeForce RTX 3090

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

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

مجموعة البياناتالمدةطريقتناأفضل أساسمقارنة المعاملات
PEMS0330 دقيقة26.10/17.03/18.8523.71/15.05/18.1634K مقابل 531K
PEMS0360 دقيقة27.67/17.46/17.7225.56/15.97/15.49(6.4% من المعاملات)
METR-LA60 دقيقة12.34/5.18/11.8011.96/5.49/9.65

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

  1. كفاءة المعاملات: استخدام 6.4% فقط من معاملات PDFormer لتحقيق أداء تنافسية
  2. ميزة التنبؤ طويل الأجل: كلما زادت مدة التنبؤ، قل الفرق في الأداء مع أفضل طريقة
  3. كفاءة البيانات: أداء أكثر استقراراً في حالات ندرة البيانات

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

المتغيرPEMS03 (RMSE/MAE/MAPE)METR-LA (RMSE/MAE/MAPE)
النموذج الكامل27.67/17.46/17.7212.34/5.18/11.80
بدون DGTV27.78/17.85/17.9012.36/5.40/12.31
بدون DGLR30.89/20.02/21.1012.41/5.35/12.20
رسم بياني زمني غير موجه27.52/17.87/18.8212.51/5.42/12.11

تُظهر النتائج:

  • حد DGLR هو الأكثر حرجاً لتحسين الأداء
  • حد DGTV له أيضاً مساهمة واضحة
  • نمذجة الرسم البياني الموجه أفضل من النمذجة غير الموجهة

التحقق النظري

النظرية 3.1 تثبت: بالنسبة للرسم البياني الخطي الموجه غير المرجح، لابلاسيان الرسم البياني الموجه المتماثل Lrd=(Lrd)TLrd\mathcal{L}_r^d = (L_r^d)^T L_r^d يعادل مصفوفة لابلاسيان الرسم البياني الخطي غير الموجه، مما يتحقق من معقولية تعريف التردد.

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

نماذج خفيفة الوزن

  • نماذج اللغة الكبيرة: تكيف LoRA منخفض الرتبة، تكميم المعاملات
  • تحسين الكلام: الانتباه الذاتي السببي المحلي
  • معالجة الصور: معالجة قناة YUV المنفصلة

طرق التنبؤ بحركة المرور

  1. طرق GNN: STGCN, Graph WaveNet وغيرها، التركيز على نمذجة المساحة
  2. طرق Transformer: محول مزدوج يعالج الأبعاد الزمكانية بشكل منفصل
  3. نماذج خطية بسيطة: تطعن في فعالية النماذج المعقدة

فك تشفير الخوارزمية

  • فك تشفير تكرارات خوارزمية التحسين كطبقات عصبية
  • يجمع بين القابلية للتفسير الرياضي والقدرة المدفوعة بالبيانات
  • تطبيقات ناجحة في معالجة الصور

الاستنتاج والمناقشة

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

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

القيود

  1. قيود المسافة: مسافة ماهالانوبيس المتعلمة غير سالبة، بينما الانتباه الذاتي التقليدي يمكن أن يكون سالباً
  2. تناثر الرسم البياني: الاتصال المحدود بناءً على الاتصالات الطرقية الحقيقية يحد من اتصالية الرسم البياني
  3. نافذة زمنية ثابتة: قد تكون النافذة الزمنية المحددة مسبقاً غير مرنة كافية

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

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

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

المميزات

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

أوجه القصور

  1. مقايضة الأداء: لا تزال أقل من أفضل طرق الأساس في بعض المقاييس
  2. نطاق التطبيق: التحقق الرئيسي على التنبؤ بحركة المرور، القابلية للتعميم على مهام زمكانية أخرى غير معروفة
  3. التحليل النظري: نقص التحليل النظري للتقارب والتعقيد

التأثير

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

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

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

المراجع

تستشهد الورقة بأعمال مهمة متعددة، بما في ذلك:

  • ورقة Transformer الأصلية (Vaswani et al., 2017)
  • مسح فك تشفير الخوارزمية (Monga et al., 2021)
  • أساسيات معالجة إشارات الرسم البياني (Ortega et al., 2018)
  • الأعمال ذات الصلة بالتنبؤ بحركة المرور (Li et al., 2017; Yu et al., 2018)

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