Skip to content
بازگشت به نتایج جست‌وجو

پیش‌بینی پیوند — استنتاج پیوندهای گمشده و آینده در شبکه‌ها

سال
2003
نوع
Network inference task

این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید

اندازه قلم

چه کاری انجام می‌دهد؟

پیش‌بینی پیوند، وظیفه‌ای در تحلیل شبکه است که تخمین می‌زند کدام پیوندها در یک گراف مشاهده‌شده گمشده‌اند یا کدام پیوندها در آینده احتمالاً تشکیل خواهند شد. این مفهوم که توسط Liben-Nowell و Kleinberg (2003, 2007) به‌صورت رسمی تعریف شده است، طیف وسیعی از رویکردها را در بر می‌گیرد — از شاخص‌های ساده شباهت ساختاری مانند همسایگان مشترک، ضریب ژاکارد، و Adamic-Adar، تا روش‌های تجزیه ماتریس و شبکه‌های عصبی گراف (GNN) — و با استفاده از AUC و میانگین دقت (Average Precision) ارزیابی می‌شود تا نسبت شدیداً نامتوازن پیوندهای واقعی به پیوندهای غیرموجود را در نظر بگیرد.

شهود پشت روش

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

تاریخ

این وظیفه به‌طور رسمی توسط Liben-Nowell و Kleinberg در مقاله SODA سال 2003 و نسخه گسترش‌یافته آن در JASIST سال 2007 تعریف شد، جایی که آن‌ها شاخص‌های ساده شباهت ساختاری را بر روی شبکه‌های هم‌تألیفی محک زدند و نشان دادند که توپوگرافی به‌تنهایی سیگنال پیش‌بینی‌کننده قوی حمل می‌کند. کارهای بعدی، این وظیفه را به مدل‌های تجزیه ماتریس و مدل‌های مولد احتمالی گسترش دادند. این حوزه توسط Zhang و Chen (2018) که چارچوب Seal را پیشنهاد کردند — استخراج زیرگراف‌های احاطه‌کننده محلی و طبقه‌بندی آن‌ها با یک GNN — به‌طور قابل‌توجهی پیشرفت کرد و نشان داد که ویژگی‌های ساختاری آموخته‌شده به‌طور مداوم از شاخص‌های شباهت دست‌ساز در شبکه‌های معیار متنوع، بهتر عمل می‌کنند.

چه زمانی استفاده شود

پیش‌بینی پیوند برای هر مسئله‌ای که در آن شبکه ناقص یا در حال تحول است و هدف بازیابی یا پیش‌بینی پیوندهاست، مناسب است. سناریوهای مناسب شامل توصیه اتصالات جدید در شبکه‌های اجتماعی، پیش‌بینی استنادات یا همکاری‌های آینده، استنتاج برهم‌کنش‌های پروتئین-پروتئین، و تکمیل گراف‌های دانش است. این روش به حداقل 50 گره و تراکم کافی از پیوندهای مشاهده‌شده نیاز دارد تا الگوهای ساختاری قابل یادگیری باشند. هنگامی که کمتر از 20 گره در دسترس است، تحلیل مرکزیت انتخاب مطمئن‌تری است. بخش مشاهده‌شده گراف باید نماینده باشد؛ اگر مکانیسم نمونه‌برداری به‌شدت سوگیرانه باشد، پیوندهای استنتاج‌شده ممکن است به‌جای ساختار واقعی، منعکس‌کننده مصنوعات نمونه‌برداری باشند.

محدودیت‌ها و ملاحظات

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

شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.

نقاط قوت

  • طیف وسیعی از پیچیدگی را پوشش می‌دهد — شاخص‌های ساده ژاکارد یا Adamic-Adar نیازی به آموزش ندارند و مستقیماً بر روی توپوگرافی گراف کار می‌کنند، در حالی که روش‌های مبتنی بر GNN الگوهای ساختاری پیچیده را یاد می‌گیرند.
  • شاخص‌های شباهت بدون مدل، سریع، قابل تفسیر و در گراف‌های پراکنده با سیگنال آموزشی محدود، قوی هستند.
  • رویکردهای GNN به‌خوبی در دامنه‌های مختلف (اجتماعی، بیولوژیکی، گراف دانش) تعمیم می‌یابند و توپوگرافی مرتبه بالاتر را ثبت می‌کنند.
  • چارچوب ارزیابی AUC/AP در برابر عدم توازن شدید کلاس بین پیوندهای واقعی و غیرموجود، قوی است.

کاربردها

  • توصیه دوست یا اتصال در شبکه‌های اجتماعی (People You May Know فیس‌بوک، لینکدین).
  • پیش‌بینی همکاری‌های تحقیقاتی آینده یا روابط استنادی در شبکه‌های دانشگاهی.
  • استنتاج برهم‌کنش‌های پروتئین-پروتئین گمشده در شبکه‌های بیولوژیکی از داده‌های آزمایشی ناقص.
  • تکمیل گراف‌های دانش با پیش‌بینی روابط بین موجودیت‌ها.
  • پیش‌بینی برهم‌کنش دارو-هدف در شبکه‌های داروشناسی.

چگونه کار می‌کند

چگونه کار می‌کند

1

شبکه از پیوندهای مشاهده‌شده تشکیل شده و با استفاده از یک تقسیم‌بندی زمانی یا تصادفی به مجموعه‌های آموزش و آزمون تقسیم می‌شود. تقسیم‌بندی زمانی هر زمان که مُهر زمانی در دسترس باشد، ارجحیت دارد زیرا از نشت اطلاعات جلوگیری می‌کند: پیوندهای آینده نباید مدل را از پیوندهای گذشته مطلع کنند. گراف آموزش، تنها گرافی است که روش امتیازدهی می‌تواند مشاهده کند.

2

از آنجایی که اکثریت قریب به اتفاق جفت گره‌ها به هم متصل نیستند، ارزیابی هر جفت غایب غیرعملی است. یک استراتژی نمونه‌برداری منفی، مجموعه‌ای از پیوندهای غیرموجود را برای استفاده به عنوان مثال‌های منفی انتخاب می‌کند. اندازه و استراتژی نمونه‌برداری (تصادفی، نمونه‌برداری منفی سخت، متعادل بر اساس درجه) به‌طور قابل‌توجهی بر عملکرد اندازه‌گیری‌شده تأثیر می‌گذارند و باید در کنار نتایج گزارش شوند.

3

به هر جفت کاندید، یک امتیاز احتمال اختصاص داده می‌شود. شاخص‌های ساختاری، امتیاز را از توپوگرافی گراف مشاهده‌شده محاسبه می‌کنند — همسایگان مشترک، تعداد همسایگان مشترک را می‌شمارد، ژاکارد آن تعداد را بر اجتماع نرمال می‌کند، و Adamic-Adar همسایگان مشترک را با معکوس لگاریتم درجه آن‌ها وزن‌دهی می‌کند. روش‌های تجزیه ماتریس، ماتریس مجاورت را به عوامل نهفته تجزیه می‌کنند که حاصلضرب نقطه‌ای آن‌ها احتمال پیوند را تقریب می‌زند. روش‌های مبتنی بر GNN، به‌ویژه چارچوب Seal از Zhang و Chen (2018)، زیرگراف‌های محلی اطراف هر جفت کاندید را استخراج کرده و یک طبقه‌بند گراف را برای تمایز پیوندهای واقعی از پیوندهای جعلی آموزش می‌دهند و الگوهای ساختاری مرتبه بالاتر را که شاخص‌های ساده از دست می‌دهند، ثبت می‌کنند.

4

پیش‌بینی‌ها بر اساس امتیاز رتبه‌بندی شده و با پیوندهای مثبت و منفی نگه‌داشته‌شده مقایسه می‌شوند. AUC-ROC، احتمال اینکه یک جفت مثبت تصادفی بالاتر از یک جفت منفی تصادفی رتبه‌بندی شود را اندازه‌گیری می‌کند. میانگین دقت (AP) دقت را در طول رتبه‌بندی کامل خلاصه می‌کند و زمانی که مثال‌های مثبت کمیاب هستند، آموزنده‌تر است. هر دو معیار باید گزارش شوند؛ دقت به‌تنهایی تحت عدم توازن شدید کلاس گمراه‌کننده است.

دام‌های رایج

  • نشت پیوندهای آینده به گراف آموزش — همیشه از تقسیم‌بندی‌های زمانی یا کاملاً تصادفی استفاده کنید و تأیید کنید که هیچ پیوند آزمون در ماتریس مجاورت آموزش ظاهر نمی‌شود.
  • گزارش صرفاً دقت؛ از آنجایی که پیوندهای غایب بسیار بیشتر از پیوندهای واقعی هستند، دقت تقریباً بی‌معنی است — همیشه AUC و AP را گزارش دهید.
  • نادیده گرفتن استراتژی نمونه‌برداری منفی هنگام مقایسه روش‌ها؛ تغییر نمونه‌برداری می‌تواند رتبه‌بندی بین مدل‌ها را معکوس کند.
  • اعمال پیش‌بینی پیوند بر روی گراف‌های با کمتر از 20 گره — با این تعداد گره کم، الگوهای ساختاری برای ارائه پیش‌بینی‌های قابل اعتماد بسیار پراکنده هستند؛ به‌جای آن تحلیل مرکزیت را ترجیح دهید.
  • در نظر گرفتن گراف مشاهده‌شده سوگیرانه به عنوان یک نمونه نماینده — اگر پیوندهای مشاهده‌شده به‌طور سیستماتیک انواع گره خاصی را حذف کنند، پیش‌بینی‌ها این سوگیری را به ارث خواهند برد.

پرسش‌های متداول

کدام رویکرد را انتخاب کنم — یک شاخص شباهت یا یک GNN؟

شاخص‌های شباهت (همسایگان مشترک، ژاکارد، Adamic-Adar) نقطه شروع خوبی هستند: آن‌ها نیازی به آموزش ندارند، قابل تفسیر هستند و در گراف‌های پراکنده به‌خوبی عمل می‌کنند. روش‌های مبتنی بر GNN مانند Seal در شبکه‌های با ساختار مرتبه بالاتر پیچیده، بهتر از شاخص‌ها عمل می‌کنند اما به تعداد کافی پیوند برچسب‌دار و منابع محاسباتی بیشتری نیاز دارند. هنگامی که داده‌ها محدود هستند یا تفسیرپذیری مهم است، با شاخص‌ها شروع کنید.

چگونه گراف را برای ارزیابی بدون نشت اطلاعات تقسیم کنم؟

اگر پیوندهای شما دارای مُهر زمانی هستند، از تقسیم‌بندی زمانی استفاده کنید: بر روی پیوندهای مشاهده‌شده قبل از یک زمان برش آموزش دهید و بر روی پیوندهای تشکیل‌شده پس از آن آزمون کنید. بدون مُهر زمانی، کسری تصادفی از پیوندها را به‌عنوان مثبت نگه دارید و تعداد مساوی یا ثابتی از پیوندهای غیرموجود را به‌عنوان منفی نمونه‌برداری کنید و اطمینان حاصل کنید که هیچ پیوند نگه‌داشته‌شده‌ای در ماتریس مجاورت آموزش ظاهر نمی‌شود.

چرا AUC بر دقت ترجیح داده می‌شود؟

در هر شبکه واقعی، تعداد پیوندهای غایب بسیار بیشتر از تعداد پیوندهای حاضر است — اغلب چندین مرتبه بزرگی. یک مدل پیش‌پاافتاده که برای هر جفت 'بدون پیوند' را پیش‌بینی می‌کند، به دقت نزدیک به کامل دست می‌یابد در حالی که هیچ چیز مفیدی را پیش‌بینی نمی‌کند. AUC-ROC و میانگین دقت معیارهای مبتنی بر رتبه‌بندی هستند که نسبت به این عدم توازن حساس نیستند و مستقیماً کیفیت رتبه‌بندی را اندازه‌گیری می‌کنند.

آیا پیش‌بینی پیوند را می‌توان بر روی گراف‌های جهت‌دار یا وزن‌دار اعمال کرد؟

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

روش‌های مرتبط

منابع

  1. Liben-Nowell, D. & Kleinberg, J. (2007). The Link-Prediction Problem for Social Networks. Journal of the American Society for Information Science and Technology, 58(7), 1019-1031.

    باز کردن مرجع DOI
    کپی شد.
  2. Zhang, M. & Chen, Y. (2018). Link Prediction Based on Graph Neural Networks. Advances in Neural Information Processing Systems (NeurIPS), 31.

    باز کردن مرجع انتشار
    کپی شد.