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

समय-श्रृंखला ग्राफ़ में नोड सम्बन्धता पूर्वानुमान का पुनर्विचार

मूल जानकारी

  • पेपर ID: 2510.06940
  • शीर्षक: समय-श्रृंखला ग्राफ़ में नोड सम्बन्धता पूर्वानुमान का पुनर्विचार
  • लेखक: 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. सैद्धांतिक योगदान: यह सिद्ध किया कि सरल अनुमानी विधियां रैखिक SSMs के विशेष मामले हैं, और इस संबंध के आधार पर अनुमानी विधियों को सामान्यीकृत करने में सक्षम TGNN आर्किटेक्चर डिजाइन किया गया
  2. आर्किटेक्चर नवाचार: NAVIS मॉडल प्रस्तावित किया, जो वर्चुअल वैश्विक स्थिति और रैखिक स्थिति-स्पेस तंत्र को संयोजित करता है, नोड सम्बन्धता पूर्वानुमान समस्या को प्रभावी ढंग से हल करता है
  3. हानि फलन सुधार: क्रॉस-एंट्रॉपी हानि की सम्बन्धता पूर्वानुमान में कमियों का विश्लेषण किया, क्रमांकन-आधारित Lambda हानि विकल्प प्रस्तावित किया
  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 (रैखिक SSMs मूलभूत अनुमानी को सामान्यीकृत करता है): मान लीजिए 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 हानि का उपयोग करें: ℓ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 epoch, बैच आकार 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: tgbn-trade पर 0.863 बनाम 0.850
  • वैश्विक वेक्टर सहित: लगभग 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 मॉडल का डिजाइन तर्कसंगत है, प्रायोगिक परिणाम प्रेरक हैं, और समय-श्रृंखला ग्राफ़ शिक्षण क्षेत्र में सकारात्मक योगदान देता है। पेपर का मुख्य मूल्य नया सैद्धांतिक दृष्टिकोण और व्यावहारिक विधि ढांचा प्रदान करना है।