گراف نیورل نیٹ ورکس میں ٹوپولوجی بیداری کو سمجھنا: عمومی اور ساختی اثرات پر

لنکس کی میز

خلاصہ اور 1 تعارف

2 متعلقہ کام

3 فریم ورک

4 اہم نتائج

5 مختصر ترین راستے کے فاصلے پر ایک کیس اسٹڈی

6 نتیجہ اور بحث، اور حوالہ جات

7 تھیوریم کا ثبوت 1

8 تھیوریم کا ثبوت 2

9 Eq کو حل کرنے کا طریقہ کار۔ (6)

10 اضافی تجربات کی تفصیلات اور نتائج

11 دیگر ممکنہ درخواستیں۔

خلاصہ

کمپیوٹر ویژن اور مشین لرننگ کے بہت سے مسائل کو گرافس پر سیکھنے کے کاموں کے طور پر بنایا گیا ہے، جہاں گراف نیورل نیٹ ورکس (GNNs) گراف اسٹرکچرڈ ڈیٹا کی نمائندگی کو سیکھنے کے لیے ایک غالب ٹول کے طور پر ابھرے ہیں۔ GNNs کی ایک اہم خصوصیت ان کا گراف ڈھانچے کا ان پٹ کے طور پر استعمال ہے، جس سے وہ گرافس کی موروثی ٹاپولوجیکل خصوصیات سے فائدہ اٹھا سکتے ہیں- جنہیں GNNs کی ٹوپولوجی آگاہی کہا جاتا ہے۔ GNNs کی تجرباتی کامیابیوں کے باوجود، عمومی کارکردگی پر ٹوپولوجی بیداری کے اثر و رسوخ کی تلاش نہیں کی گئی، خاص طور پر نوڈ لیول کے کاموں کے لیے جو ڈیٹا کے آزاد اور یکساں طور پر تقسیم (IID) ہونے کے مفروضے سے ہٹ جاتے ہیں۔ GNNs کی ٹاپولوجی بیداری کی قطعی تعریف اور خصوصیت، خاص طور پر مختلف ٹاپولوجیکل خصوصیات کے بارے میں، ابھی تک واضح نہیں ہے۔ یہ مقالہ کسی بھی ٹاپولوجیکل خصوصیت میں GNNs کی ٹاپولوجی بیداری کو نمایاں کرنے کے لیے ایک جامع فریم ورک متعارف کرایا ہے۔ اس فریم ورک کا استعمال کرتے ہوئے، ہم GNN جنرلائزیشن کی کارکردگی پر ٹوپولوجی بیداری کے اثرات کی تحقیقات کرتے ہیں۔ اس مروجہ عقیدے کے برعکس کہ GNNs کی ٹوپولوجی بیداری کو بڑھانا ہمیشہ فائدہ مند ہوتا ہے، ہمارا تجزیہ ایک اہم بصیرت کو ظاہر کرتا ہے: GNNs کی ٹوپولوجی بیداری کو بہتر بنانا نادانستہ طور پر ساختی گروپوں میں غیر منصفانہ عمومیت کا باعث بن سکتا ہے، جو کچھ منظرناموں میں مطلوب نہیں ہو سکتا ہے۔ مزید برآں، ہم مختلف بینچ مارک ڈیٹاسیٹس پر اندرونی گراف میٹرک، مختصر ترین راستے کا فاصلہ استعمال کرتے ہوئے کیس اسٹڈی کرتے ہیں۔ اس کیس اسٹڈی کے تجرباتی نتائج ہماری نظریاتی بصیرت کی تصدیق کرتے ہیں۔ مزید برآں، ہم گراف ایکٹیو لرننگ میں کولڈ اسٹارٹ کے مسئلے سے نمٹنے کے لیے اپنے فریم ورک کی عملی قابل اطلاقیت کا مظاہرہ کرتے ہیں۔

1 تعارف

کمپیوٹر ویژن اور مشین لرننگ میں بہت سے مسائل کو گرافس پر سیکھنے کے کاموں کے طور پر بنایا گیا ہے۔ مثال کے طور پر، سیمنٹک سیگمینٹیشن میں، گراف مختلف تصویری خطوں کے درمیان تعلقات کا نمونہ بناتے ہیں، درستگی اور سیاق و سباق سے آگاہ سیگمنٹیشن کو بڑھاتے ہیں۔ گراف نیورل نیٹ ورکس (GNNs) مشین لرننگ ماڈلز کی ایک غالب کلاس کے طور پر ابھرے ہیں جو خاص طور پر گراف ساختہ ڈیٹا کی نمائندگی سیکھنے کے لیے بنائے گئے ہیں۔ انہوں نے مختلف ڈومینز جیسے کیمسٹری [10]، حیاتیات [37]، سوشل نیٹ ورکنگ [6، 22]، منظر گراف کی تخلیق [46، 51] اور بصری تعلق کا پتہ لگانے میں گراف سے متعلق مسائل کی ایک وسیع رینج کو حل کرنے میں کافی کامیابی کا مظاہرہ کیا ہے۔ [24,43,49]۔ GNNs کی ایک متعین خصوصیت یہ ہے کہ وہ خصوصیت جمع کرنے کے لیے گراف ڈھانچے پر پیغام کے ذریعے ایک مقامی نقطہ نظر کا استعمال کرتے ہیں۔ یہ GNNs کو بنیادی گراف کے ڈھانچے سے ساختی معلومات یا انحصار (جسے ٹوپولوجی آگاہی کہا جاتا ہے) کو محفوظ رکھنے کے قابل بناتا ہے، جس سے وہ نوڈ کی درجہ بندی جیسے کاموں میں انتہائی مؤثر ثابت ہوتے ہیں۔ تصویر 1 GNNs کے سیکھنے کے مجموعی عمل کی وضاحت کرتا ہے۔

ان کی عملییت اور صلاحیت کے باوجود، GNNs کے بارے میں نظریاتی فہم کا فقدان ہے، خاص طور پر نیم زیر نگرانی نوڈ کی درجہ بندی کی ترتیب میں جہاں ڈیٹا کے درمیان انحصار دوسرے مشین لرننگ ماڈلز سے نمایاں طور پر مختلف ہے [25]۔ اس ترتیب میں، مقصد ڈیٹا اور لیبل والے نوڈس کے ایک چھوٹے سیٹ کے درمیان، بقیہ نوڈس کے لیبل کی پیشین گوئی کرنے کے لیے، گراف ڈھانچے کے ذریعے حاصل کردہ تعلقات کو فائدہ اٹھانا ہے۔ GNNs کے زیادہ تر موجودہ نظریاتی مطالعات نے GNNs کے پیغام پاس کرنے کے طریقہ کار اور Weisfeiler-Lehman isomorphism test [19] کے درمیان تعلق پر توجہ مرکوز کی ہے، جس کا مقصد GNNs کی سیکھی ہوئی نمائندگیوں میں مختلف گراف ڈھانچے میں فرق کرنے کی صلاحیت کو سمجھنا ہے، GNNs کی اظہاری طاقت کے طور پر۔ اظہار خیال کے مطالعے سے متاثر ہو کر، یہ عام طور پر خیال کیا جاتا ہے کہ ٹوپولوجی کی آگاہی میں اضافہ عالمی طور پر فائدہ مند ہے اور بہت سے مطالعات GNNs کو سیکھے ہوئے نمائندگی میں مزید ساختی خصوصیات کو محفوظ رکھنے کے قابل بنانے پر مرکوز ہیں [29, 33, 48]۔

تاہم، جیسا کہ GNNs ان پٹ کے طور پر گراف ڈھانچے پر زیادہ انحصار کرتے ہیں اور حساس (آگاہ) ہوتے ہیں، وہ ڈیٹا کے اندر مخصوص ساختی ذیلی گروپوں (ٹریننگ سیٹ سے ساختی مماثلت کے لحاظ سے گروپ کردہ الگ ڈیٹا سب سیٹ) کی طرف مختلف عمومی کارکردگی کی نمائش کر سکتے ہیں۔ مختلف ساختی ذیلی گروپوں میں GNN جنرلائزیشن کی مقدار کو سٹرکچرل سب گروپ جنرلائزیشن [25] کہا جاتا ہے۔ اس طرح کے تحفظات GNN کی درخواست اور ترقی میں اہم ہیں۔ مثال کے طور پر، پروٹین-پروٹین کے تعامل کے نیٹ ورک کے اندر، یہ ساختی ذیلی گروپ مختلف مالیکیولر کمپلیکس کی نمائندگی کر سکتے ہیں، جو تعامل کی پیشین گوئیوں کی درستگی کو متاثر کرتے ہیں۔ اسی طرح، تربیت کے لیے نمونے لینے کی حکمت عملی وضع کرتے وقت یہ سمجھنا ضروری ہے کہ GNNs کی ٹوپولوجی بیداری کس طرح عامیت کو متاثر کرتی ہے۔ GNNs کی عمومی کارکردگی جس حد تک گراف ڈیٹا کی مخصوص ساختی خصوصیات سے متاثر ہوتی ہے وہ تربیتی ڈیٹاسیٹس کی تشکیل کا فیصلہ کرنے میں اہم ہے۔ اس کی اہمیت کے باوجود، GNNs کی ٹاپولوجی بیداری اور اس کے سٹرکچرل سب گروپ جنرلائزیشن کے درمیان تعلق کی سمجھ کا ابھی بھی فقدان ہے۔ مزید برآں، GNNs کی ٹاپولوجی بیداری کو نمایاں کرنا ایک چیلنج ہے، خاص طور پر اس بات پر غور کرتے ہوئے کہ مختلف ڈومینز اور کام الگ الگ ساختی پہلوؤں کو ترجیح دے سکتے ہیں۔ لہذا، مختلف ڈھانچے کے سلسلے میں GNNs کی ٹوپولوجی بیداری کا اندازہ لگانے کے لیے ایک ورسٹائل فریم ورک کی ضرورت ہے۔

اس خلا کو دور کرنے کے لیے، اس مقالے میں، ہم نیم زیر نگرانی نوڈ کی درجہ بندی کے تناظر میں ساختی ذیلی گروپ کی عمومی کاری اور GNNs کی ٹاپولوجی بیداری کے درمیان تعلق کا مطالعہ کرنے کے لیے تخمینی میٹرک ایمبیڈنگ پر مبنی ایک نیا فریم ورک تجویز کرتے ہیں۔ مجوزہ فریم ورک مختلف ساختی ذیلی گروپوں کے حوالے سے GNNs کے ساختی ذیلی گروپ کو عام کرنے کی تحقیقات کی اجازت دیتا ہے۔ مزید ٹھوس طور پر، اس کام کی اہم شراکتوں کا خلاصہ ذیل میں کیا گیا ہے۔

1. ہم GNNs کے ساختی ذیلی گروپ عمومی اور ٹوپولوجی بیداری کے درمیان تعامل کو جانچنے کے لیے اندازاً میٹرک ایمبیڈنگ کا استعمال کرتے ہوئے ایک ناول، ڈھانچہ-ایگنوسٹک فریم ورک تجویز کرتے ہیں۔ یہ فریم ورک ورسٹائل ہے، مختلف ساختی اقدامات کو ایڈجسٹ کرتا ہے جیسے مختصر ترین راستے کا فاصلہ، اور اس کے لیے صرف اسی ساختی پیمائش کی ضرورت ہوتی ہے۔ کلیدی عوامل کا اندازہ لگانے میں اس کی سادگی اسے وسیع پیمانے پر منظرناموں پر قابل اطلاق اور عام بناتی ہے۔

2. اپنے فریم ورک کے اندر باضابطہ تجزیے کے ذریعے، ہم GNN ٹوپولوجی بیداری اور ان کی عمومی کارکردگی (Theorem 1) کے درمیان ایک واضح ربط قائم کرتے ہیں۔ ہم یہ بھی ظاہر کرتے ہیں کہ جب کہ بہتر ٹوپولوجی بیداری سے GNN اظہاریت کو فروغ ملتا ہے، اس کے نتیجے میں عمومی کارکردگی کی ناہمواری پیدا ہو سکتی ہے، جو ذیلی گروپوں کو تربیتی سیٹ سے زیادہ ساختی طور پر ملتے جلتے ہیں (تھیورم 2)۔ اس طرح کی ساختی جائیداد نقصان دہ ہو سکتی ہے (غیر منصفانہ مسائل کا باعث بنتی ہے) یا مفید (ڈیزائن کے فیصلوں سے آگاہ کرنا) منظر نامے کے لحاظ سے۔ یہ اس مروجہ عقیدے کو چیلنج کرتا ہے کہ ٹوپولوجی بیداری میں اضافہ عالمی سطح پر GNNs [29, 33, 48] کو فائدہ پہنچاتا ہے، جس میں ٹوپولوجی بیداری اور عمومی کارکردگی کے درمیان تعلق پر غور کرنے کی اہمیت پر زور دیا جاتا ہے۔

3. ہم اپنے فریم ورک کی توثیق اس کی عملییت اور مطابقت کو اجاگر کرتے ہوئے، مختصر ترین راستے کے فاصلے پر کیس اسٹڈی کے ذریعے کرتے ہیں۔ نتائج ہمارے نظریاتی نتائج کی تصدیق کرتے ہیں، یہ ظاہر کرتے ہیں کہ مختصر ترین راستے کے فاصلوں کے بارے میں زیادہ آگاہی کے ساتھ GNNs تربیتی سیٹ کے قریب ورٹیکس گروپس کی درجہ بندی کرنے میں سبقت لے جاتے ہیں۔ مزید برآں، ہم یہ ظاہر کرتے ہیں کہ ہمارے فریم ورک اور نتائج کے عملی مضمرات کو اجاگر کرتے ہوئے، گراف ایکٹیو لرننگ [11,15] میں کولڈ اسٹارٹ کے مسئلے کو کم کرنے کے لیے ہمارے نتائج کو کس طرح لاگو کیا جا سکتا ہے۔