চিরায়ত ডিপ লার্নিং ইউক্লিডীয় গ্রিডের ওপর প্রতিষ্ঠিত: ছবি হলো পিক্সেলের ২ডি গ্রিড, আর অডিও বা টেক্সট হলো ১ডি ক্রম। কিন্তু প্রাকৃতিক ও সামাজিক জগতের অধিকাংশ উপাত্ত ইউক্লিডীয় নয়: রাসায়নিক অণু, প্রোটিন গঠন, উদ্ধৃতি নেটওয়ার্ক এবং সোশ্যাল মিডিয়া গ্রাফ ইত্যাদি অনিয়মিত টপোলজিক্যাল গ্রাফ $mathcal{G} = (mathcal{V}, mathcal{E})$ হিসেবে বিদ্যমান। গ্রাফ নিউরাল নেটওয়ার্ক (GNN) এই অনিয়মিত স্পেসে ডিপ লার্নিংকে প্রসারিত করে পারমিউটেশন সমতুল্যতা (Permutation Equivariance) এবং স্থানীয় মেসেজ পাসিং (Message Passing) অ্যালগরিদমের মাধ্যমে।
১. গ্রাফের প্রতিসাম্য ও পারমিউটেশন ইকুইভ্যারিয়েন্স
গ্রাফের নোডগুলোর কোনো নির্দিষ্ট ক্রম বা ইনডেক্স থাকে না। নোডগুলোকে যেকোনো পারমিউটেশন ম্যাট্রিক্স $P$ দিয়ে পুনর্বিন্যস্ত করলেও গ্রাফের অন্তর্নিহিত গঠন অপরিবর্তিত থাকে। ফলে নোড-লেভেল প্রেডিকশনকে $P$-Equivariant হতে হয়: $f(P A P^T, P X) = P f(A, X)$।
২. মেসেজ পাসিং নিউরাল নেটওয়ার্ক (MPNN)
২০১৭ সালে জাস্টিন গিলমার সমস্ত গ্রাফ আর্কিটেকচারকে একটি সর্বজনীন কাঠামোর মধ্যে আবদ্ধ করেন যা তিনটি ধাপে বিভক্ত:
- মেসেজ তৈরি: প্রতিটি প্রতিবেশী নোড $u in mathcal{N}(v)$ থেকে মেসেজ $m_{uv}$ তৈরি করা।
- মেসেজ একত্রীকরণ (Aggregation): প্রতিবেশীদের মেসেজগুলোকে প্রতিসম অপারেশনের ($sum, text{mean}, max$) মাধ্যমে যোগ করা।
- নোড আপডেট: নোডের পূর্ববর্তী অবস্থার সাথে নতুন মেসেজ মিলিয়ে নতুন ভেক্টর $h_v$ নির্ধারণ করা।
৩. প্রধান আর্কিটেকচারসমূহ
- GCN (কিফ ও ওয়েলিং, ২০১৭): ফার্স্ট-অর্ডার স্পেকট্রাল কনভোলিউশন $H^{(k)} = sigma(tilde{D}^{-1/2} tilde{A} tilde{D}^{-1/2} H^{(k-1)} W)$।
- GAT (ভেলিকোভিচ, ২০১৮): প্রতিবেশীদের গুরুত্ব নির্ধারণে গতিশীল সেলফ-অ্যাটেনশন ওজন $alpha_{uv}$ প্রয়োগ।
- GIN (শু ও সহকর্মীরা, ২০১৯): মাল্টিসেট পৃথকীকরণে সক্ষম সর্বাধিক শক্তিশালী আর্কিটেকচার।
৪. ওয়েইসফেইলার-লেহম্যান (1-WL) টেস্ট ও প্রকাশ ক্ষমতার সীমা
২০১৯ সালে কেইয়ুলু শু এবং ক্রিস্টোফার মরিস প্রমাণ করেন যে: যেকোনো মেসেজ পাসিং GNN-এর প্রকাশ ক্ষমতা ক্লাসিক্যাল ১-ওয়েইসফেইলার-লেহম্যান (1-WL) গ্রাফ আইসোমরফিজম টেস্ট দ্বারা সীমাবদ্ধ। ১-ডাব্লিউএল অ্যালগরিদম যে দুটি ভিন্ন গ্রাফকে আলাদা করতে পারে না (যেমন একটি ৬-নোডের রিং বনাম দুটি ৩-নোডের ত্রিভুজ), কোনো স্ট্যান্ডার্ড GNN-ও তাদের পৃথক করতে পারে না। এই সীমাবদ্ধতা ভাঙতে আধুনিক উচ্চ-ক্রমের সাব-গ্রাফ নেটওয়ার্কের প্রয়োজন হয়।
