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. एल्गोरिदम अनरोलिंग मॉडल-संचालित और डेटा-संचालित का संयोजन करने के लिए एक नया दृष्टिकोण प्रदान करता है
  3. मौजूदा कार्य केवल सकारात्मक अप्रत्यक्ष ग्राफ का उपयोग करते हैं, जटिल स्पेस-टाइम संबंधों को प्रभावी ढंग से मॉडल नहीं कर सकते

मुख्य योगदान

  1. मिश्रित ग्राफ एल्गोरिदम अनरोलिंग का पहला प्रस्ताव: अप्रत्यक्ष ग्राफ (स्थान) और निर्देशित ग्राफ (समय) को जटिल स्पेस-टाइम संबंधों को मॉडल करने के लिए जोड़ता है
  2. नवीन निर्देशित ग्राफ नियमितकरण पद: निर्देशित ग्राफ लैप्लासियन नियमितकरण (DGLR) और निर्देशित ग्राफ कुल भिन्नता (DGTV) डिजाइन किया
  3. हल्का व्याख्यायोग्य ट्रांसफॉर्मर: ADMM एल्गोरिदम अनरोलिंग के माध्यम से पैरामीटर में भारी कमी (केवल PDFormer का 6.4%)
  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
  • ट्रांसफॉर्मर विधियां: PDFormer, STAEformer
  • अनुकूली ग्राफ विधियां: Graph WaveNet, AGCRN
  • सरल रैखिक मॉडल: STID, SimpleTM

कार्यान्वयन विवरण

  • भविष्यवाणी अवधि: 30/60/120 मिनट (6/12/24 कदम)
  • ऐतिहासिक विंडो: 60 मिनट (12 कदम)
  • अनुकूलक: Adam, सीखने की दर 5×10⁻⁴
  • हानि फलन: Huber हानि (δ=1)
  • हार्डवेयर: NVIDIA GeForce RTX 3090

प्रयोगात्मक परिणाम

मुख्य परिणाम

डेटासेटअवधियह विधिसर्वश्रेष्ठ आधारभूतपैरामीटर तुलना
PEMS0330min26.10/17.03/18.8523.71/15.05/18.1634K vs 531K
PEMS0360min27.67/17.46/17.7225.56/15.97/15.49(6.4% पैरामीटर)
METR-LA60min12.34/5.18/11.8011.96/5.49/9.65

मुख्य निष्कर्ष

  1. पैरामीटर दक्षता: PDFormer के केवल 6.4% पैरामीटर का उपयोग करके प्रतिस्पर्धी प्रदर्शन प्राप्त करें
  2. दीर्घकालीन पूर्वानुमान लाभ: भविष्यवाणी अवधि जितनी लंबी होगी, सर्वश्रेष्ठ विधि के साथ प्रदर्शन का अंतर उतना ही कम होगा
  3. डेटा दक्षता: डेटा की कमी की स्थिति में अधिक स्थिर प्रदर्शन

विलोपन प्रयोग

वेरिएंटPEMS03 (RMSE/MAE/MAPE)METR-LA (RMSE/MAE/MAPE)
पूर्ण मॉडल27.67/17.46/17.7212.34/5.18/11.80
DGTV के बिना27.78/17.85/17.9012.36/5.40/12.31
DGLR के बिना30.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. ट्रांसफॉर्मर विधियां: समय और स्थान आयामों को अलग से संभालने के लिए दोहरे ट्रांसफॉर्मर
  3. सरल रैखिक मॉडल: जटिल मॉडल की प्रभावशीलता को चुनौती देते हैं

एल्गोरिदम अनरोलिंग

  • अनुकूलन एल्गोरिदम पुनरावृत्ति को तंत्रिका परतों में अनरोल करना
  • गणितीय व्याख्यायोग्यता और डेटा-संचालित क्षमता दोनों को जोड़ता है
  • छवि प्रसंस्करण में सफल अनुप्रयोग

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

  1. मिश्रित ग्राफ एल्गोरिदम अनरोलिंग ने सफलतापूर्वक हल्का व्याख्यायोग्य ट्रैफिक पूर्वानुमान मॉडल प्राप्त किया
  2. निर्देशित ग्राफ भिन्नात्मक पद ने प्रभावी रूप से समय कारण संबंधों को पकड़ा
  3. पैरामीटर में भारी कमी के साथ प्रतिस्पर्धी प्रदर्शन बनाए रखा

सीमाएं

  1. दूरी सीमा: सीखी गई महालनोबिस दूरी गैर-नकारात्मक है, जबकि पारंपरिक स्व-ध्यान नकारात्मक हो सकता है
  2. ग्राफ विरलता: वास्तविक सड़क कनेक्शन पर आधारित ग्राफ की कनेक्टिविटी को सीमित करता है
  3. निश्चित समय विंडो: पूर्वनिर्धारित समय विंडो पर्याप्त लचीला नहीं हो सकता है

भविष्य की दिशाएं

  1. हस्ताक्षरित दूरी और अधिक जटिल ग्राफ मॉडलिंग तक विस्तार
  2. अनुकूली समय विंडो सीखना
  3. अन्य स्पेस-टाइम पूर्वानुमान कार्यों में अनुप्रयोग

गहन मूल्यांकन

शक्तियां

  1. सैद्धांतिक नवाचार: निर्देशित ग्राफ के लिए पहली बार आवृत्ति अवधारणा परिभाषित की और संबंधित नियमितकरण पद डिजाइन किए
  2. विधि नवीनता: मिश्रित ग्राफ एल्गोरिदम अनरोलिंग ट्रांसफॉर्मर डिजाइन के लिए नया दृष्टिकोण प्रदान करता है
  3. व्यावहारिक मूल्य: पैरामीटर में उल्लेखनीय कमी व्यावहारिक तैनाती के लिए महत्वपूर्ण है
  4. व्याख्यायोग्यता: प्रत्येक परत अनुकूलन एल्गोरिदम पुनरावृत्ति के अनुरूप है, स्पष्ट गणितीय अर्थ है

कमियां

  1. प्रदर्शन व्यापार: कुछ मेट्रिक्स पर अभी भी सर्वश्रेष्ठ आधारभूत विधि से कम नहीं है
  2. लागू क्षेत्र: मुख्य रूप से ट्रैफिक पूर्वानुमान को सत्यापित किया गया है, अन्य स्पेस-टाइम कार्यों में सामान्यीकरण अज्ञात है
  3. सैद्धांतिक विश्लेषण: अभिसरण और जटिलता का सैद्धांतिक विश्लेषण अभाव

प्रभाव

  1. शैक्षणिक योगदान: ग्राफ संकेत प्रसंस्करण और ट्रांसफॉर्मर डिजाइन के लिए नया दृष्टिकोण प्रदान करता है
  2. व्यावहारिक मूल्य: हल्का विशेषता मोबाइल डिवाइस और संसाधन-सीमित वातावरण के लिए उपयुक्त है
  3. पुनरुत्पादनीयता: खुला स्रोत कोड प्रदान करता है, प्रयोगात्मक सेटअप विस्तृत है

लागू परिदृश्य

  1. संसाधन-सीमित वातावरण: मोबाइल डिवाइस, किनारे कंप्यूटिंग
  2. वास्तविक समय पूर्वानुमान प्रणाली: तेजी से प्रतिक्रिया की आवश्यकता वाली ट्रैफिक प्रबंधन प्रणाली
  3. व्याख्यायोग्य AI अनुप्रयोग: मॉडल पारदर्शिता की आवश्यकता वाली सुरक्षा-महत्वपूर्ण प्रणाली

संदर्भ

पेपर कई महत्वपूर्ण कार्यों का हवाला देता है, जिनमें शामिल हैं:

  • ट्रांसफॉर्मर मूल पेपर (Vaswani et al., 2017)
  • एल्गोरिदम अनरोलिंग सर्वेक्षण (Monga et al., 2021)
  • ग्राफ संकेत प्रसंस्करण आधार (Ortega et al., 2018)
  • ट्रैफिक पूर्वानुमान संबंधित कार्य (Li et al., 2017; Yu et al., 2018)

समग्र मूल्यांकन: यह ट्रैफिक पूर्वानुमान क्षेत्र में नवीन कार्य है, जो एल्गोरिदम अनरोलिंग विचार को मिश्रित ग्राफ सेटिंग तक सफलतापूर्वक विस्तारित करता है, प्रदर्शन बनाए रखते हुए पैरामीटर में भारी कमी करता है। हालांकि कुछ मेट्रिक्स पर सुधार की गुंजाइश है, लेकिन इसकी हल्की और व्याख्यायोग्य विशेषताएं इसे महत्वपूर्ण व्यावहारिक मूल्य और शैक्षणिक महत्व प्रदान करती हैं।