یادگیری گراف زمانی در سال 2024

این پست وبلاگ منتخبی از پیشرفت‌های هیجان‌انگیز در TGL را پوشش می‌دهد و در عین حال به مسیرهای تحقیقاتی برای سال 2024 اشاره می‌کند. همچنین از محققان برجسته می‌خواهیم نظرشان را در مورد آینده TGL ارائه دهند. هدف این وبلاگ ارائه مراجع و نقطه شروع برای کسانی است که می‌خواهند در مورد یادگیری گراف‌های زمانی بیشتر بیاموزند. لطفاً هر گونه پیشرفت دیگری که در مورد آن هیجان زده هستید در بخش نظرات با ما در میان بگذارید. برای پیشرفت در یادگیری گراف، پست وبلاگ عالی مایکل گالکین را بررسی کنید.

فهرست مطالب:

۱. معیار گراف زمانی

۲. معماری‌های جدید برای پیش‌بینی پیوند

۳. گراف‌های فضایی و زمانی و یادگیری عمیق گراف برای پردازش سری‌های زمانی

۴. گراف دانش زمانی

۵. یادگیری گراف زمانی آگاه از علیت

۶. روش‌های گراف زمانی قابل توضیح

۷. حملات خصمانه به گراف‌های زمانی

۸. کتابخانه‌ها و معیارها

معیار گراف زمانی

یکی از نیروهای محرک توسعه سریع یادگیری ماشین بر روی گراف‌ها، در دسترس بودن معیارهای استاندارد و متنوعی مانند معیار گراف باز[1] (OGB)، معیار گراف برد بلند[2] و GraphWorld[3] است. با این حال، این معیارها برای گراف‌های ثابت طراحی شده اند و فاقد اطلاعات مهر زمانی دقیق مورد نیاز برای یادگیری گراف‌های زمانی هستند. بنابراین، پیشرفت در یادگیری گراف‌های زمانی به دلیل فقدان مجموعه داده‌های با کیفیت بالا و همچنین عدم ارزیابی مناسب که منجر به عملکرد بیش از حد خوش بینانه می‌شود، متوقف شده است.

برای رفع این شکاف، معیار گراف زمانی (TGB) اخیرا ارائه شده است که شامل مجموعه‌ای از مجموعه داده‌های معیار چالش برانگیز و متنوع برای ارزیابی واقعی، قابل تکرار و قوی برای یادگیری ماشین در گراف‌های زمانی است. TGB یک بسته[4] pypi برای دانلود و پردازش خودکار نه مجموعه داده از پنج دامنه مجزا با حداکثر 72 میلیون لبه و 30 میلیون مهر زمانی ارائه می‌کند. TGB همچنین ارزیابی استانداردی را با انگیزه برنامه های واقعی ارائه می‌دهد.

TGB شامل وظایف سطح پیوند و گره و مقایسه تجربی گسترده مدل‌های TG در تمام مجموعه‌های داده است. اولین کار، وظیفه پیش‌بینی ویژگی پیوند پویا است که خاصیت (اغلب وجود) پیوند بین یک جفت گره را در زمان آینده پیش‌بینی می‌کند. در TGB، این کار به عنوان یک مسئله رتبه‌بندی مدل شده و با متریک میانگین رتبه متقابل فیلتر شده[5] (MRR) ارزیابی می‌شود. نتایج نشان می‌دهد که رتبه‌بندی مدل‌ها به طور قابل‌توجهی در میان مجموعه داده‌ها با نسبت‌های مختلف لبه‌های مجموعه آزمون که هرگز در طول آموزش مشاهده نمی‌شوند، متفاوت است. علاوه بر این، با استفاده از نمونه‌های منفی بیشتر (لبه‌های عدم وجود) در ارزیابی، عملکرد مدل بدتر می‌شود. جالب توجه است که میزان کاهش عملکرد در مدل‌ها نیز متفاوت است.

در کار پیش‌بینی ویژگی گره پویا، هدف پیش‌بینی ویژگی یک گره در یک زمان معین است. به طور خاص، ما بر روی وظیفه پیش‌بینی گره‌ها تمرکز می‌کنیم که نحوه تغییر اولویت کاربر نسبت به موارد مختلف در طول زمان را مدل می‌کند. در اینجا، ما از سود تجمعی تنزیل شده نرمال شده 10 مورد برتر (NDCG@10) برای مقایسه ترتیب نسبی اقلام پیش‌بینی شده با حقیقت پایه استفاده می‌کنیم. جالب توجه است، ما متوجه شدیم که اکتشافی منفرد از مدل‌های TG موجود بهتر عمل می‌کند و این نیاز به مدل‌های بیشتر با تمرکز بر وظایف سطح گره در آینده را برجسته می‌کند. تابلوی امتیازات TGB عمومی است و می توانید مدل خود را از طریق فرم گوگل ارسال کنید. برای جزئیات بیشتر به پست وبلاگ TGB توسط نویسندگان این وبلاگ مراجعه کنید[6].

معماری‌های جدید برای پیش‌بینی پیوند

"پیش‌بینی پیوند در قلمرو یادگیری گراف زمانی چالش مهمی ایجاد می‌کند. الگوریتم‌های یادگیری باید فراتر از قدرت بیان محدودی که معمولاً در معماری‌های ارسال پیام سنتی مانند GNN یافت می‌شود، گسترش یابد. علاوه بر این، آنها باید بر کارایی محاسباتی تأکید کنند. یک جنبه مهم این اطمینان از تأخیر کم در پاسخ به یک پیوند بین قدرت پیش‌بینی مدل و سرعت پیش‌بینی بیانگر آن است. یک محیط داده پویا و پیچیده." – پان لی، استادیار موسسه فناوری جورجیا

نظرسنجی اخیر توسط Longa و همکاران[7] یک نمای کلی از GNN های زمانی ارائه می‌دهد. بسیاری از رویکردها معماری‌های تخصصی را برای پیش‌بینی پیوند پویا پیشنهاد می‌کنند، که اغلب با هدف گرفتن ویژگی‌ها یا همبستگی‌های ساختاری مهم است. به عنوان مثال، لو و همکاران[8] با هدف مدل‌سازی صریح همسایگی مشترک مجموعه‌ای از گره‌ها برای پیش‌بینی پیوند آینده، جایی که آنها مدل شبکه زمانی آگاه از همسایگی[9] (NAT) را طراحی کردند. همسایگی مشترک توسط رویکردهای مبتنی بر شبکه عصبی گراف سنتی (GNN) گرفته نمی‌شود زیرا بردارهای تعبیه گره به طور مستقل برای هر گره تولید می‌شوند. در مثال زیر، گره v و w دارای زمینه‌های ساختاری یکسانی هستند، بنابراین از دید GNNها قابل تشخیص نیستند. در واقعیت، پیوند بین گره u و v در t₃ به احتمال زیاد به دلیل قانون بسته شدن سه گانه شکل می‌گیرد در حالی که این برای پیوند بین u و w در t₃ مطمئن نیست. در مقایسه، NAT یک بازنمایی همسایگی از نوع فرهنگ لغت جدید را اقتباس کرد که اطلاعات محله k-hop را ثبت می‌کند و امکان ساخت سریع ویژگی‌های ساختاری همسایگی مشترک چندین گره را می‌دهد. بازنمایی فرهنگ لغت توسط یک تکنیک کَش کارآمد به نام N-cache حفظ می شود. N-cache به NAT اجازه می‌دهد تا ویژگی‌های همسایگی مشترک را برای دسته‌ای از جفت گره‌ها برای پیش‌بینی پیوند سریع بسازد.

تعبیه‌های GNN گره v و w یکسان خواهند بود. منبع تصویر: لو و همکاران 2022

دوم، یو و همکاران[10] با پیشنهاد DyGFormer، یک معماری جدید مبتنی بر ترانسفورمر برای یادگیری گراف‌های زمانی، هدف خود را به دست آوردن وابستگی‌های زمانی طولانی مدت داشته باشید. با توجه به یک پرس و جو بین گره u و گره v در زمان t، اولین گام استخراج تعاملات اول پرش تاریخی گره u و v قبل از زمان t است. این شامل رمزگذاری‌های همسایه‌ها، پیوندها، فواصل زمانی و همچنین فرکانس‌های ظاهر هر همسایه از u و v می‌شود. فرض این است که اگر u و v همسایه‌های تاریخی مشترک‌تری در گذشته داشته باشند، احتمال تعامل آنها در آینده بیشتر است. پس از رمزگذاری فعل و انفعالات تاریخی در یک دنباله، سپس به چند تکه تقسیم می‌شود و به یک ترانسفورمر برای گرفتن وابستگی‌های زمانی وارد می‌شود.

چارچوب DyGFormer منبع تصویر: یو و همکاران 2023

سوال دیگر این است که آیا واقعاً به معماری‌های مدل پیچیده برای شبکه‌های زمانی نیاز داریم؟ در مقاله‌ای با همین نام، Cong و همکاران[11] ضرورت استفاده از ماژول های رایج در یادگیری نمودارهای زمانی مانند شبکه عصبی بازگشتی (RNN) و مکانیسم توجه به خود را بررسی کردند. آنها نشان دادند که این ماژول‌ها همیشه برای پیش‌بینی لینک پویا ضروری نیستند. به طور خاص، مدل GraphMixer پیشنهادی آنها کاملاً مبتنی بر پرسپترون‌های چند لایه (MLPs) و میانگین ادغام همسایه است در حالی که به شدت در برابر خطوط پایه با RNN و توجه به خود عمل می‌کند. GraphMixer شامل سه ماژول است: یک رمزگذار پیوند اطلاعات پیوندهای زمانی را خلاصه می‌کند، یک رمزگذار گره اطلاعات را از گره‌ها استخراج می‌کند و یک دسته‌بندی پیوند که اطلاعات بالا را برای پیش‌بینی ترکیب می‌کند. جالب است که Cong و همکاران استدلال کرد که یک تابع رمزگذاری زمان قابل آموزش می‌تواند باعث بی‌ثباتی در طول آموزش شود و در عوض یک تابع رمزگذاری زمان ثابت z(t) = cos(tω) را انتخاب کرد که در آن ویژگی‌های ثابت تفاوت نسبی بین دو مهر زمانی را همانطور که در زیر نشان داده شده است، نشان می‌دهد.

تابع رمزگذاری زمان ثابت برای تبدیل t به بردار cos(tω). محور x بعد برداری و محور y مقدار کسینوس است. منبع تصویر: Cong et al. 2023

در نهایت، سورش و همکاران[12] اشاره کرد که روش‌های موجود، دقت را به‌طور مستقل نسبت به پیوندهای آینده به حداکثر می‌رسانند، و این واقعیت را نادیده می‌گیرند که پیوندهای آینده اغلب بین یکدیگر وابستگی دارند. این زمانی دیده می‌شود که کاربر از بین لیستی از موارد برای خرید یا مجموعه‌ای از کاربران برای اتصال در یک شبکه اجتماعی انتخاب می‌کند. بنابراین، سورش و همکاران پیش‌بینی پیوند پویا را به‌عنوان یک مسئله رتبه‌بندی در نظر بگیرد و برای رتبه‌بندی (TGRank) شبکه گراف زمانی را پیشنهاد کند تا رتبه‌بندی را در فهرستی از نامزدها یاد بگیرد. خط لوله TGRank در زیر نشان داده شده است. پرس و جو وظیفه اکنون شامل یک گره مرکزی s (در مثال) با مجموعه‌ای از گره‌های کاندید (همه گره‌های دیگر در زیرگراف) است و هدف این است که محتمل‌ترین نامزد را به عنوان مقصد گره s رتبه‌بندی کنیم. برای این منظور، TGRank سه مرحله را دنبال می‌کند. ابتدا، گره s متفاوت از سایر گره‌ها برچسب‌گذاری می‌شود. سپس، GNNها برای انتشار برچسب گره مرکزی به هر نامزد رتبه‌بندی استفاده می‌شوند. این مرحله انتشار برچسب پارامتری شده، مهرهای زمانی، تعدد و همچنین ویژگی‌های تعاملات تاریخی را در طول شبکه از گره مرکزی تا همه نامزدها جمع‌آوری می‌کند و قدرت بیان بیشتری را برای پیش‌بینی پیوند فراهم می‌کند. در نهایت، از یک باخت از نظر فهرست برای بهینه‌سازی رتبه‌بندی مشترک در میان نامزدها استفاده می‌شود. از نظر تجربی، همچنین نشان داده شده است که با از دست دادن رتبه‌بندی فهرستی، مدل‌های محبوب مانند TGN و TGAT نیز بهتر از راه‌اندازی اولیه خود با از دست دادن دسته‌بندی باینری عمل می‌کنند.

خط لوله TGRank. گره مرکزی گره s است. منبع تصویر: Suresh et al. 2023

گراف‌های فضایی و زمانی و یادگیری عمیق گراف برای پردازش سری‌های زمانی

"پیش‌بینی‌های ما اساساً بر روی مرتبط‌ترین مشاهدات معقول است، اما همیشه ساده نیست، زیرا روابط داده‌های مرتبط اغلب در دید آشکار پنهان می‌شوند. رونمایی از آنها یک چالش فریبنده است، به‌ویژه زمانی که پویا هستند یا شامل بیش از دو نهاد می‌شوند." – دانیله زامبون، پست داک در آزمایشگاه هوش مصنوعی سوئیس IDSIA

در انجمن یادگیری گراف زمانی، اصطلاح گراف فضایی-زمانی اغلب برای نشان دادن گراف با توپولوژی ثابت و ویژگی‌های گره استفاده می‌شود که در طول زمان، معمولاً در مراحل زمانی گسسته مربوط به مشاهدات نمونه‌گیری منظم تغییر می‌کنند. اخیراً مسئله پردازش داده‌ها با چنین ساختاری از دیدگاه متفاوتی در نظر گرفته می‌شود، یعنی با در نظر گرفتن ویژگی گره پویا به عنوان سری‌های زمانی و یال‌ها به عنوان وابستگی‌های عملکردی در میان دنباله‌های مشاهدات[13]. از این منظر، که به طور قابل توجهی از بسیاری از تنظیمات مورد بحث در این پست وبلاگ منحرف است، بازنمایی‌های مبتنی بر گراف مکانی-زمانی امکان پردازش مجموعه‌های سری‌های زمانی همبسته را با بهره‌گیری از سوگیری‌های معماری معمول شبکه‌های عصبی گراف فراهم می‌کنند.

سری‌های زمانی همبسته با اطلاعات جانبی رابطه‌ای منبع تصویر: Cini et al. 2023، توسط نویسندگان.

چنین مجموعه‌ای از سری‌های زمانی همبسته را می‌توان توسط حسگرها، چه فیزیکی و چه غیر فیزیکی، تولید کرد. یک مثال در حوزه ترافیک است، جایی که سری‌های زمانی ممکن است با خوانش حسگرهایی که تعداد وسایل نقلیه عبوری از یک چهارراه را اندازه‌گیری می‌کنند مطابقت داشته باشد. هر حسگر با یک گره متفاوت مطابقت دارد و یک ماتریس مجاورت را می‌توان به دست آورد، به عنوان مثال، با پیوستن به یک لبه فقط آن دسته از حسگرهایی که مستقیماً توسط یک بخش جاده متصل هستند. علاوه بر پیش‌بینی ترافیک[14]، این بازنمایی‌ها در طیف گسترده‌ای از برنامه‌های پردازش سری زمانی از پایش کیفیت هوا[15] (چن و همکاران 2021) و تجزیه و تحلیل انرژی[16] (Cini و همکاران 2023) تا تجزیه و تحلیل داده‌های زیست‌پزشکی[17] (ژانگ و همکاران ۲۰۲۲) و پردازش داده‌های مالی[18] (ماتسوناگا و همکاران 2019) استفاده شده‌اند.

نمونه‌ای از سری‌های زمانی مرتبط از حوزه ترافیک. منبع تصویر: آموزش در ECML PKDD 2023 توسط نویسندگان[19].

برای پردازش این داده‌ها، چارچوب استاندارد ارسال پیام باید به‌روزرسانی شود تا بتواند دنباله‌ای از مشاهدات از همسایگی هر گره را مدیریت کند. این کار را می‌توان به راحتی با جایگزینی عملگرهای مناسب (یعنی توابع پیام و به‌روزرسانی) با اپراتورهایی که قادر به پردازش داده‌ها در امتداد بعد زمانی هستند، به عنوان مثال، سلول‌های مکرر[20] (سئو و همکاران 2018)، پیچش‌های مکانی-زمانی[21] (وو و همکاران 2019) و معماری‌های مبتنی بر توجه[22] (ماریسکا و همکاران 2019) انجام داد. مدل‌های به‌دست‌آمده به‌عنوان شبکه‌های عصبی گراف مکانی-زمانی[23] (STGNNs) شناخته می‌شوند و تحقیقات زیادی برای ارائه معماری‌های مؤثر انجام شده است (به مینگ و همکاران 2023 مراجعه کنید[24]). یکی از مزایای اصلی استفاده از STGNN این است که از مجموعه پارامترهای یکسانی می‌توان برای پیش‌بینی هر زیر مجموعه سری‌های زمانی استفاده کرد، در حالی که وابستگی‌ها را در طول پردازش در نظر گرفت. این یک مزیت بزرگ نسبت به مدل‌های استاندارد پیش‌بینی سری‌های زمانی چند متغیره است که معمولاً باید هر سری زمانی را به‌طور جداگانه پیش‌بینی کنند یا از اشتراک‌گذاری پارامتر صرف نظر کنند. STGNNهای ترکیبی، با برخی پارامترهای خاص سری زمانی، نیز می توانند در نظر گرفته شوند و همانطور که در مقاله اخیر NeurIPS نشان داده شده[25]، اغلب از مدل‌هایی که در آن همه پارامترها مشترک هستند، بهتر عمل می‌کنند. علاوه بر معماری مدل، بازنمایی‌های مبتنی بر گراف، همانطور که توسط زامبون و همکاران[26] نشان داده شده است، همچنین می‌توانند در ارزیابی بهینه بودن یک مدل پیش‌بینی با تمرکز تحلیل همبستگی مکانی-زمانی به گره‌های به هم پیوسته کمک کنند.

یک شبکه عصبی گراف مکانی-زمانی. تصویر توسط نویسندگان

چالش‌های متعددی در این زمینه وجود دارد که از برخورد با سری‌های زمانی نمونه‌برداری نامنظم[27] و داده‌های از دست رفته شروع می‌شود. در واقع، هر دو در هنگام برخورد با سیستم‌های فیزیکی-سایبری واقعی پدیده‌های کاملاً رایجی هستند. خوشبختانه، مدل‌های مبتنی بر گراف در این زمینه نیز مفید هستند، به عنوان مثال اجازه می‌دهند بازسازی را بر اساس مشاهدات در حسگرهای همسایه شرط[28] کنیم. مقیاس‌پذیری یکی دیگر از نگرانی‌های اصلی است، زیرا بر خلاف GNN‌های استاندارد، ارسال پیام اغلب به صورت w.r.t. انجام می‌شود. هر مرحله زمانی معماری‌های مقیاس‌پذیر موجود بیشتر به نمونه‌برداری فرعی[29] و/یا ویژگی‌های گره از پیش محاسبه‌شده[30] متکی هستند. زمانی که هیچ اطلاعات مربوط به رابطه قبلی در دسترس نباشد، چالش یادگیری یک گراف نهفته مستقیماً از سری‌های زمانی است. برای مثال، با یادگیری مستقیم یک ماتریس مجاورت[31] (به عنوان مثال، وو و همکاران 2019) یا تحت یک چارچوب احتمالی، با تکیه بر ترفندهای پارامترسازی مجدد[32] و برآوردگرهای مبتنی بر امتیاز، مسئله حل شده است[33].

یک شبکه عصبی گراف مکانی-زمانی مقیاس‌پذیر منبع[34] تصویر: Cini et al. 2023. توسط نویسندگان

از آنجایی که این موضوع در پست وبلاگ‌های گذشته پوشش داده نشد، هدف در اینجا ارائه یک نمای کلی از تنظیمات و مسائل قابل مدل‌سازی بود. جهات بسیاری در حال حاضر، از مدل‌های فضای حالت گراف[35] و فیلترهای کالمن گراف[36] گرفته تا مدل‌های فضا-زمان مبتنی بر انتشار[37] و پیوسته[38] در حال بررسی هستند. اگر علاقه‌مند به دانستن بیشتر و/یا استفاده از این مدل‌ها در عمل هستید، مقاله آموزشی جامعی در این زمینه منتشر شده است. همچنین می توانید Torch Spatiotemporal (tsl)، کتابخانه را برای ساخت خطوط لوله پردازش سری زمانی مبتنی بر گراف بررسی کنید[39].

· مقاله آموزشی: یادگیری عمیق گراف برای پیش‌بینی سری‌های زمانی[40]

· کتابخانه: Torch Spatiotemporal (TSL)

گراف دانش زمانی

در کنفرانس‌های برتر ML امسال به‌طور شگفت‌انگیزی تعداد کمی مقالات موقتی KG وجود داشت: TILP[41] در استخراج قوانین زمانی رقابتی با روش‌های عصبی، و کار تئوری توسط Chen و Wang[42] برای اندازه‌گیری بیان GNN‌های زمانی. در واقع، جالب‌ترین مقالات (برای من) در مورد این موضوع در کارگاه TGL در NeurIPS’23 یافت شد (یک دلیل دیگر برای اینکه شما محل برگزاری را دنبال کنید!)، به عنوان مثال، پیش‌بینی فواصل زمانی آینده توسط Pop و Kostylev[43]، یا شناسایی نشت در مجموعه داده‌های معیار معیار توسط Pan و همکاران[44]. در نهایت، KG یکپارچه شهری[45] (UUKG) توسط Ning و همکاران را به عنوان نگاهی تازه به مجموعه داده‌های موقت KG که در واقع معنای عملی دارند و یک مورد استفاده - مدل‌سازی جریان‌های حمل‌ونقل در شهر هستند، بیان می‌کنم.

UUKG بزرگ‌ترین مسئله کوچک شدن انجمن KG زمانی را نشان می‌دهد - فقدان وظایف و مجموعه داده‌های عملا مهم که در آن امکان نشان دادن کاربرد الگوی مدل‌سازی داده در وظایف دنیای واقعی وجود دارد. یعنی افزودن 1% MRR/Hits@10 به معیارهای تعبیه‌شده KG 10 ساله، این روزها در مقایسه با موفقیت‌های یادگیری[46] عمیق هندسی در زیست‌شناسی یا علم مواد (یا در مقایسه با LLM‌ها، اما این یک داستان برای یک روز دیگر است) بی‌فایده است. امیدواریم، مجموعه داده‌های کاربردی عملاً مفید مشابه UUKG را ببینیم.

شاید یکی دیگر از مناطق مجاور که در آن KGهای زمانی ممکن است تفاوت ایجاد کنند، گراف‌های ناهمگن (که معمولاً لبه‌های تایپ شده دارند) باشد که در صنعت بسیار مورد استفاده قرار می‌گیرند. به عنوان مثال، RelBench[47] اخیر (معیار یادگیری عمیق رابطه‌ای) یک مسئله پیش‌بینی زمانی را بر روی پایگاه داده‌های رابطه‌ای فرموله می‌کند که می‌تواند به راحتی به KG یا هایپرگراف تبدیل شود.

یادگیری گراف زمانی آگاه از علیت

انیشتین گفت: فلش زمان فقط در یک جهت پرواز می‌کند. … و کدام یک از ما که این فرصت را به ما داد، روز یا ساعتی را که برای اولین بار عشق یا خلسه را شناختیم، یا انتخابی را که برای همیشه آینده ما را تغییر داد و زندگی‌ای که ممکن بود داشتیم را نفی کند، دوباره زنده نکند؟ چنین فرصت‌هایی به ندرت داده می‌شود. - گرگ ایلز، بازی آرام

یکی از دلایل جالب بودن یادگیری گراف زمانی[48] این است که - بسته به داده‌های موجود - به دیدگاه‌های متفاوتی نیاز دارد. به عنوان مثال، داده‌های گراف‌های زمانی را با مهرهای زمانی با وضوح بالا (احتمالاً پیوسته) در نظر بگیرید. در چنین داده‌هایی، تکنیک‌های یادگیری گراف زمان گسسته که از دنباله‌ای از گراف‌های عکس فوری استفاده می‌کنند، نیاز به دانه‌بندی درشت زمان دارند، که در آن هر عکس فوری شامل یال‌هایی است که در یک بازه زمانی مشخص رخ می‌دهند. این دانه درشت اجازه می‌دهد تا تکنیک‌های یادگیری گراف (ایستا) را به داده‌های سری زمانی تعمیم دهیم. اما یک مسئله اصلی را معرفی می‌کند: هر عکس فوری اطلاعات مربوط به ترتیب زمانی رخ دادن یال‌ها را که پایه و اساس مسیرهای علّی یا رعایت زمان است را دور می‌اندازد (کمپ و همکاران[49] 2000). مانند مسیرها در گراف‌های استاتیک، مسیرهای رعایت زمان مهم هستند زیرا به ما می‌گویند کدام گره‌ها می‌توانند به طور غیرمستقیم بر یکدیگر تأثیر بگذارند. در زیر، ما این را در یک گراف زمانی ساده با دو یال بدون جهت (a,b) و (b,c) که به ترتیب در زمان‌های t₁ و t₂ رخ می‌دهند، نشان می‌دهیم. اگر (a,b) قبل از (b,c) اتفاق بیفتد، a می‌تواند از طریق مسیری که به زمان احترام می‌گذارد (که با رنگ بنفش نشان داده شده است) که از b می‌گذرد، به‌طور علّی روی c تأثیر بگذارد. اگر ترتیب زمانی یال‌ها معکوس شود، a نمی‌تواند به طور علّی بر c تأثیر بگذارد، زیرا هر تأثیری باید در زمان به عقب منتشر شود. توجه داشته باشید که جهت‌گیری تأثیر از a به c به دلیل پیکان جهت‌دار زمان و علیرغم اینکه هر دو یال بدون جهت هستند. علاوه بر این، در حالی که دو یال (a,b) و (b,c) در یک گراف ایستا و جمع‌آوری شده زمان حاکی از یک مسیر گذرا از a via b به c (بنفش) و بالعکس (نارنجی) است، این برای گراف‌های زمانی صادق نیست.

مسیر رعایت زمان از گره a به گره c. تصویر توسط نویسندگان

چندین کار نشان داده‌اند که - به دلیل پیکان زمان - توپولوژی عِلی گراف‌های زمانی، یعنی اینکه کدام گره‌ها احتمالاً می‌توانند از طریق مسیرهای رعایت زمان بر یکدیگر تأثیر بگذارند، به شدت با همتایان ساکن خود متفاوت است و پیامدهای جالبی برای گسترش اپیدمی[50] (فیتزنر و همکاران ۲۰۱۳) سرعت[51] (شولتز و همکاران 2014)، مرکزیت گره[52] (روسوال و همکاران 2014)، یا تشخیص انجمن[53] (لامبیوته و همکاران 2019) دارد. آیا می‌توانیم روش‌های یادگیری عمیق را از الگوهای توپولوژی عِلی گراف‌های زمانی آگاه کنیم؟ پیشرفت‌های ارائه‌شده در این سال نشان می‌دهد که این می‌تواند بر اساس مدل‌هایی به دست آید که بازنمایی‌های استاتیک رایج گراف‌های زمانی را تعمیم می‌دهند. یک گراف وزنی جمع‌آوری شده با زمان را در نظر بگیرید، که در آن یک یال (جهت‌دار) (a,b) با وزن پنج نشان می‌دهد که (a,b) پنج بار در یک گراف زمانی رخ داده است. چنین گراف وزنی و تجمیع زمان در پایین پانل 2 در شکل زیر نشان داده شده است.

خط لوله برای پیش‌بینی مرکزیت‌های زمانی گره‌ها در یک گراف زمانی. منبع تصویر: هیگ و همکاران[54]، توسط نویسندگان

هر یال در گراف زمانی، مسیری است که زمان را رعایت می‌کند و طول آن یک است. بنابراین، یک گراف وزنی جمع‌آوری‌شده زمان، با یک مدل مرتبه اول برای توپولوژی علّی یک گراف زمانی مطابقت دارد، که مسیرهای با رعایت زمان طول یک را ثبت می‌کند. از ترتیب زمانی لبه‌ها غفلت می‌کند، زیرا ما فقط تعداد دفعات وقوع هر یال را محاسبه می‌کنیم. تبدیل گراف خطی ما را قادر می‌سازد این ایده را به ** مدل‌های آگاه از علیت تعمیم دهیم که یادگیری گراف زمانی را تسهیل می‌کنند: ما به سادگی یال‌ها را در گراف مرتبه اول با گره‌های یک گراف مرتبه دوم جایگزین می‌کنیم، یعنی یال‌های (a,b) و (b,c) را به ترتیب به گره‌های a→b و b→c تبدیل می‌کنیم. در گراف مرتبه دوم به دست آمده (گراف بالایی در پانل 2 در شکل را ببینید)، می‌توانیم از یال‌ها برای نشان دادن مسیرهای با زمان به طول دو استفاده کنیم، یعنی یال (a→b، b→c) - نشان‌دهنده تأثیر علّی بر c - از طریق b است. با این حال، ترتیب معکوس لبه‌ها شامل نمی‌شود. اگر لبه‌ها به ترتیب معکوس رخ دهند، (a→b، b→c) را در بر نمی‌گیریم. نکته مهم این است که چنین گراف مرتبه دومی به ترتیب زمانی یال‌ها حساس است، در حالی که یک گراف مرتبه اول اینگونه نیست! در شولتز[55]، 2017، این به مرتبه‌های بالاتر تعمیم داده می‌شود، که مدل‌های گراف De Bruijn مرتبه k-ام را برای توپولوژی عِلی نگرش گراف زمانی به دست می‌دهد.

قرکاجیجا[56] و همکاران نشان داده‌اند که ارسال پیام عصبی در چنین گراف‌های درجه بالاتر De Bruijn یک معماری شبکه عصبی گراف آگاه از علیت را برای گراف‌های زمانی ایجاد می‌کند. هیگ و شولتز[57] با تکیه بر این شبکه‌های عصبی گراف De Bruijn (DBGNN)، در پوستری در کارگاه TGL در سال ۲۰۲۴، به چالش پیش‌بینی بین و نزدیکی مرکزی گره‌ها می‌پردازند. از آنجایی که آنها تحت تأثیر پیکان زمان هستند، مرکزیت گره‌های زمانی می‌توانند به شدت با مرکزیت‌های ایستا متفاوت باشند. علاوه بر این، محاسبه آنها پرهزینه است! این با آموزش یک مدل DBGNN در اولین بازه زمانی یک گراف زمانی، سپس با استفاده از مدل آموزش‌دیده برای پیش‌بینی مرکزیت‌های زمانی در داده‌های باقی‌مانده مورد بررسی قرار می‌گیرد. رویکرد کلی در بالا نشان داده شده است. نتایج تجربی امیدوارکننده هستند و پتانسیل یادگیری گراف آگاه از علیت را نشان می‌دهند. همچنین امیدواریم در سال 2024 شاهد توجه بیشتر انجمن در یادگیری ساختار عِلی بر روی گراف‌های زمانی باشیم.

به یادگیری گراف‌های زمانی آگاه از علیت علاقه دارید؟ سپس یک خبر خوب وجود دارد! تکنیک‌های بالا در کتابخانه منبع باز pathpyG[58]، که بر پایه PyG[59] ساخته می‌شود، پیاده‌سازی می‌شوند. یک ویدیوی مقدماتی و یک آموزش[60] موجود است. یک سخنرانی ضبط شده که در گروه خواندن گراف زمانی ارائه می‌شود[61]، مقدمه‌ای عمیق از تحقیق زیربنایی را ارائه می‌دهد.

روش‌های گراف زمانی قابل توضیح

"مهم‌ترین داده‌های ساختاریافته گراف در تنظیمات دنیای واقعی ماهیت زمانی دارند. مدل‌های گراف زمانی قابل توضیح این پتانسیل را دارند که سوالات طولانی‌مدت در مورد استراتژی‌ها و دانش موثر را آشکار کنند که می‌توان از آنها برای پیش‌بینی‌های زمانی استفاده کرد، امکان استخراج بینش از مدل‌های یادگیری عمیق و کمک به کشف علمی و پیش‌بینی را فراهم کرد." - رکس یانگ، استادیار دانشگاه ییل

در سال 2023 اولین رویکردها برای توضیح روش‌های GNN زمانی مشاهده شد. توضیح دهندگان برای کاربردهای پرمخاطره مانند تشخیص تقلب و پیش‌بینی پیشرفت بیماری در مراقبت‌های بهداشتی مهم هستند. شیا و همکاران[62] T-GNNEexplainer را به عنوان اولین توضیح دهنده طراحی شده برای مدل‌های گراف زمانی پیشنهاد کرد. T-GNNEexplainer مدل-آگنوستیک است و رویدادهای مهم را از مجموعه‌ای از رویدادهای نامزد پیدا می‌کند تا به بهترین شکل پیش‌بینی مدل را توضیح دهد. شیا و همکاران مسئله شناسایی زیرمجموعه‌ای از توضیح رویدادها را به‌عنوان یک مسئله بهینه‌سازی ترکیبی با جستجو در زیر مجموعه‌ای از گراف زمانی در اندازه معین در نظر بگیرید. برای مقابله با این موضوع، T-GNNExplainer از یک چارچوب کاوشگر-ناوبر استفاده می‌کند. ناوبر از چندین رویداد هدف آموزش دیده است تا همبستگی‌های استقرایی بین رویدادها را ثبت کند در حالی که کاوشگر ترکیب خاصی از رویدادها را بر اساس جستجوی درخت مونت کارلو، از جمله انتخاب گره، گسترش گره، شبیه‌سازی پاداش و پشتیبان جستجو می‌کند. اینکه کدام رویدادها هرس می‌شوند از ناوبر استنباط می‌شود. گراف زیر چارچوب T-GNNExplainer را نشان می‌دهد.

چارچوب T-GNNEexplainer. منبع تصویر: شیا و همکاران 2023

اخیراً چن و همکاران. استدلال کرد که برای ایجاد توضیحات قابل فهم انسانی برای رویدادهای گراف زمانی، توضیح باید رویدادهایی باشد که از نظر زمانی نزدیک و از لحاظ مکانی مجاور با پیش‌بینی هستند که به آنها توضیح منسجم می‌گویند. استفاده از موتیف‌های زمانی، زیرساخت‌های تکرار شونده در گراف زمانی، یک راه‌حل طبیعی برای ایجاد توضیحات منسجم برای گراف‌های زمانی است. این به این دلیل است که موتیف‌های زمانی عوامل بسیار مهمی هستند که روند تولید رویدادهای آینده را هدایت می‌کنند. در مثال زیر، قانون پیوست ترجیحی[63] (اغلب تسهیل کننده اثر اینفلوئنسر در تجارت الکترونیک) و قانون بسته شدن سه گانه[64] (قوانین دوست مشترک را در شبکه‌های اجتماعی توضیح می‌دهد) توضیحات منسجم و قابل قبولی را تشکیل می‌دهند.

توضیحات منسجم از نظر زمانی تقریبی و از لحاظ مکانی مجاور هستند. منبع تصویر: Chen et al. 2023

بنابراین، چن و همکاران[65] TempME، یک توضیح دهنده جدید مبتنی بر موتیف زمانی برای شناسایی موتیف‌های زمانی مهم برای توضیح GNNهای زمانی را پیشنهاد کرد. چارچوب TempME در شکل زیر نشان داده شده است. ابتدا، موتیف‌های زمانی پیرامون پیش‌بینی هدف استخراج می‌شوند. سپس این موتیف‌های نامزد از طریق رمزگذار موتیف کدگذاری می‌شوند که از ناشناس‌سازی رویداد، ارسال پیام و ادغام گراف برای ایجاد یک تعبیه برای هر موتیف استفاده می‌کند. سپس، بر اساس اصل تنگنای اطلاعات، TempME امتیازهای اهمیت را به این موتیف‌ها اختصاص می‌دهد که هم با دقت توضیح و هم فشرده‌سازی اطلاعات محدود می‌شوند. در نهایت، توضیحات با نمونه‌گیری از توزیع برنولی بر اساس امتیاز اهمیت ساخته شده است.

چارچوب TempME، اعداد روی لبه‌ها نشان دهنده ترتیب زمانی هستند. اعتبار تصویر: چن و همکاران. 2023

حملات خصمانه به گراف‌های زمانی

"از آنجایی که گراف‌های زمانی برای استفاده در کارهای مهم مانند تشخیص تقلب پذیرفته می‌شوند، درک نقاط شکست آنها در حملات خصمانه مهم است. درک و تعیین کمیت چنین نقاط کور اولین گام برای ایجاد مدل‌های GNN زمانی قوی و قابل اعتماد است. چنین تلاش‌هایی برای اطمینان از پذیرش این مدل‌ها در صنعت ضروری است." – سریجان کومار، استادیار موسسه فناوری جورجیا

حملات خصمانه می‌تواند حریم خصوصی مشتریان را هدف قرار دهد یا بر تصمیمات حیاتی در سیستم‌های مالی تأثیر بگذارد. از آنجایی که مدل‌های گراف زمانی برای برنامه‌هایی مانند سیستم‌های توصیه و تشخیص تقلب به کار گرفته می‌شوند، بررسی حملات و طراحی مکانیسم‌های دفاعی برای مدل‌های TG مهم است. چن و همکاران اولین حمله خصمانه را برای پیش‌بینی پیوند پویا به نام حمله گرادیان آگاه به زمان[66] (TGA) برای گراف‌های پویا زمانی گسسته پیشنهاد کرد. TGA تعداد محدودی از پیوندها را از شبکه اصلی مجدداً سیم‌کشی می‌کند و با ارزش‌ترین پیوندها به پیوند پیش‌بینی شده توسط اطلاعات گرادیان تولید شده توسط مدل TG تعیین می‌شود.

مروری بر حمله Perturbation آگاه از دینامیک زمانی. مهاجم می‌تواند در حالی که از شناسایی فرار می‌کند، پیش‌بینی مدل را تغییر دهد. منبع تصویر: شارما و همکاران 2023[67]

اخیرا، شارما و همکاران استدلال کرد که حملات مؤثر بر روی گراف‌های زمانی باید هم آشفتگی‌های لبه و هم زمانی را بهینه کنند و در عین حال تکامل گراف اصلی را حفظ کنند. این به این دلیل است که حملات شدیدی که تکامل گراف را مختل می‌کنند به راحتی با روش‌های تشخیص ناهنجاری شناسایی می‌شوند. بنابراین، شارما و همکاران حملات حفظ تکامل بر روی گراف‌های دینامیکی زمان گسسته را به عنوان محدودیت آشفتگی آگاه از دینامیک زمانی[68] (TDAP) فرموله کرد. TDAP ادعا می‌کند که اغتشاشات اضافه شده در یک مُهر زمانی معین باید فقط کسری کوچک از تعداد واقعی تغییرات نسبت به مهر زمانی قبلی باشد. نشان داده شده است که TDAP سرعت تغییر را هم در ساختار و هم در فضاهای تعبیه شده حفظ می‌کند. نمای کلی TDAP در شکل زیر نشان داده شده است. شارما و همکاران سپس یک روش حمله جدید به نام Temporal Dynamics-Aware Projected Gradient Descent (TD-PGD) پیشنهاد می‌کند که نشان داده شده است که دارای یک عملگر طرح ریزی شکل بسته تحت محدودیت TDAP است. یک نسخه آنلاین از TD-PGD نیز پیشنهاد شده است که در آن اختلالات را می توان در زمان واقعی اضافه کرد. در نهایت، به طور تجربی نشان داده شده است که اغتشاشات محدود شده با TDAP می‌توانند با روش‌های تشخیص ناهنجاری مبتنی بر تعبیه از حملات فرار کنند.

کتابخانه‌ها و معیارها

در سال 2023 شاهد فشار قابل توجهی به سمت کتابخانه‌های استاندارد و معیارهای یادگیری گراف‌های زمانی بودیم. TGB[69] یک معیار باز و استاندارد شده برای وظایف سطح گره و پیوند فراهم می‌کند. DyGLib[70] یک کتابخانه است که شامل خطوط لوله آموزشی استاندارد، رابط‌های کدگذاری توسعه‌پذیر و استراتژی‌های ارزیابی جامع برای یادگیری گراف‌های زمانی است. ژانگ و همکاران[71] مفهوم جدید Live Graph Lab[72] را معرفی کرد که گراف‌های زنده را بر اساس تراکنش‌های بلاک چین ارائه می‌دهد. با مجموعه‌ای از ابزارها برای دانلود، تجزیه، تمیز کردن و تجزیه و تحلیل تراکنش‌های بلاک چین، Live Graph Lab به محققان این فرصت را می‌دهد تا داده‌های گراف زمانی به روز را در هر زمان استخراج کرده و از آن برای تجزیه و تحلیل یا آزمایش استفاده کنند. ژو و همکاران[73] متوجه شدیم که حافظه گره مورد استفاده در مدل‌های TG به اندازه دسته‌ای کوچک است و باید به طور همزمان در همه مربی‌ها نگهداری شود. بنابراین، آنها DistTGL[74]، یک راه‌حل کارآمد و مقیاس‌پذیر برای آموزش TGNNهای مبتنی بر حافظه بر روی خوشه‌های GPU توزیع شده را پیشنهاد کردند. فعال کردن آموزش چند GPU در مجموعه داده‌های بزرگ یک جهت مهم برای استقرار مدل‌های TG در مجموعه داده‌های بزرگ است. ما یک لیست به روز شده از کتابخانه‌ها و معیارها برای یادگیری گراف‌های زمانی ارائه می‌دهیم: