شبكة تماثل الرسوم (GIN)
Graph Isomorphism Network
GNN مصممة لتبلغ القدرة التمييزية لاختبار Weisfeiler–Lehman (1-WL)، باستخدام تجميع بالمجموع وMLP في التحديث.
نظرة عامة
| الاسم | شبكة تماثل الرسوم – Graph Isomorphism Network |
|---|---|
| سنة الظهور | 2019 |
| الباحثون | Keyulu Xu، Weihua Hu، Jure Leskovec، Stefanie Jegelka |
| الورقة الأصلية | How powerful are graph neural networks? arXiv |
| نوع البيانات | رسوم بيانية |
| المجالات | الحوسبة العلمية، تعلم البيانات البيانية |
| الكلفة الحسابية | $O(|E|d+Nd^2)$ لكل طبقة. |
| حجم البيانات | آلاف الرسوم الصغيرة (مجموعات TU وOGB الجزيئية). |
المشكلة التي تحلها
لم يكن واضحاً نظرياً ما حدود قدرة GNN على التمييز بين الرسوم المختلفة، ولماذا تفشل بعض دوال التجميع (المتوسط والأقصى) في حالات بسيطة.
الخلفية والتطور
ما قبلها: الشبكة الالتفافية البيانية، جراف سيج، Weisfeiler–Lehman test
- 2019
أثبت Xu وزملاؤه أن قوة GNN محدودة باختبار 1-WL، واقترحوا GIN التي تبلغ هذا الحد. [مرجع]
الفكرة الأساسية
لكي تكون دالة التجميع حقنية (injective) على المجموعات المتعددة (multisets)، يستخدم المجموع بدل المتوسط أو الأقصى، ثم MLP كمقرب عام للدوال. المعامل $\epsilon$ يميّز العقدة نفسها عن جيرانها.
المخطط التفاعلي
مخطط توضيحي مبسّط بأبعاد مثال صغير، وليس رسماً مطابقاً لكل تفاصيل التنفيذ الأصلي. اضغط أي طبقة لترى وظيفتها وأبعادها والعملية الرياضية.
اختر طبقة من المخطط.
المكونات
| المكوّن | الوظيفة |
|---|---|
| Sum aggregation | مجموع تمثيلات الجيران |
| Self term | $(1+\epsilon)h_v$ |
| MLP | طبقتان خطيتان مع BatchNorm وReLU |
| Graph readout | مجموع تمثيلات العقد في كل طبقة ثم ربطها |
| Classifier | لتصنيف الرسم |
المعادلات
1. تحديث GIN
| $\epsilon^{(k)}$ | عدد قابل للتعلم أو ثابت |
| $\mathrm{MLP}$ | مقرب عام للدوال |
2. قراءة الرسم
| $\|$ | ربط عبر الطبقات |
آلية العمل خطوة بخطوة
- تُجمع تمثيلات الجيران بالمجموع.
- يضاف تمثيل العقدة مضروباً بـ $1+\epsilon$.
- يمر الناتج بـ MLP.
- تتكرر الطبقات.
- يُجمع تمثيل الرسم من كل الطبقات ويُصنّف.
المزايا والقيود
المزايا
- أقوى تمييزياً من GCN وGraphSAGE ضمن عائلة MPNN.
- أداء قوي في تصنيف الرسوم الجزيئية.
القيود
- لا تتجاوز حد 1-WL (لا تميز بعض الرسوم المنتظمة).
- المجموع قد يسبب قيماً كبيرة في الرسوم الكثيفة.
متى تُستخدم؟ ومتى لا؟
تناسب
- تصنيف الرسوم كاملة (جزيئات، بروتينات).
لا تناسب
- عندما يتطلب التمييز خصائص تتجاوز 1-WL مثل عدّ الحلقات؛ جرّب نماذج أعلى رتبة أو ترميزات موضعية.
التطبيقات
| المجال | الاستخدام |
|---|---|
| الحوسبة العلمية | التنبؤ بسمية الجزيئات أو فعاليتها. |
| تعلم البيانات البيانية | تصنيف الرسوم في المعايير القياسية. |
كود PyTorch
كود تعليمي مبسّط يعمل على بيانات اصطناعية صغيرة، يغطي: الاستيراد، وتعريف النموذج، والبيانات، والتمرير الأمامي، والخسارة، والمُحسِّن، وحلقة التدريب، والتقييم، والاستدلال. ليس التنفيذ الكامل للبحث الأصلي.
# Graph Isomorphism Network (GIN) لتصنيف الرسوم
# مثال تعليمي مبسّط بـ PyTorch (ليس التنفيذ الأصلي الكامل للبحث): بيانات اصطناعية صغيرة،
# يعمل على المعالج المركزي (CPU) خلال ثوانٍ. الأرقام التي يطبعها تخص هذا المثال فقط.
# 1) استيراد المكتبات
import torch
import torch.nn as nn
import torch.nn.functional as F
torch.manual_seed(0)
# 2) تعريف النموذج
class GINLayer(nn.Module):
def __init__(self, d_in, d):
super().__init__()
self.eps = nn.Parameter(torch.zeros(1))
self.mlp = nn.Sequential(nn.Linear(d_in, d), nn.ReLU(), nn.Linear(d, d))
def forward(self, h, A):
return self.mlp((1 + self.eps) * h + A @ h) # (1+ε)h_v + Σ h_u
class GIN(nn.Module):
def __init__(self, d_in=1, d=32, n_classes=2, L=3):
super().__init__()
self.layers = nn.ModuleList([GINLayer(d_in if i == 0 else d, d) for i in range(L)])
self.out = nn.Linear(d_in + L * d, n_classes)
def forward(self, graphs):
outs = []
for X, A in graphs:
h, reads = X, [X.sum(0)]
for layer in self.layers:
h = F.relu(layer(h, A)); reads.append(h.sum(0)) # قراءة بالمجموع لكل طبقة
outs.append(torch.cat(reads))
return self.out(torch.stack(outs))
# 3) إعداد البيانات
# الفئة 0: حلقة (cycle)؛ الفئة 1: نجمة (star). سمة كل عقدة = 1، فالبنية وحدها تميز الفئتين.
def cycle(n):
A = torch.zeros(n, n)
for i in range(n): A[i, (i + 1) % n] = A[(i + 1) % n, i] = 1
return A
def star(n):
A = torch.zeros(n, n); A[0, 1:] = 1; A[1:, 0] = 1
return A
def make(m):
G, y = [], []
for _ in range(m):
n, c = int(torch.randint(5, 12, (1,))), int(torch.randint(0, 2, (1,)))
G.append((torch.ones(n, 1), cycle(n) if c == 0 else star(n))); y.append(c)
return G, torch.tensor(y)
G_train, y_train = make(160)
G_test, y_test = make(40)
model = GIN()
# 4) الخسارة والمحسّن
loss_fn = nn.CrossEntropyLoss()
opt = torch.optim.Adam(model.parameters(), lr=1e-2)
# 5) حلقة التدريب بدفعات من الرسوم
for epoch in range(30):
model.train()
perm = torch.randperm(len(G_train))
for i in range(0, len(perm), 16):
b = perm[i:i + 16]
loss = loss_fn(model([G_train[j] for j in b]), y_train[b])
opt.zero_grad(); loss.backward(); opt.step()
if epoch % 10 == 0: print(f"epoch {epoch} loss={loss.item():.4f}")
# 6) التقييم
model.eval()
with torch.no_grad():
acc = (model(G_test).argmax(1) == y_test).float().mean().item()
print(f"test accuracy = {acc:.3f}")
# 7) الاستدلال: حلقة من 7 عقد
with torch.no_grad():
print("cycle-7 predicted class:", model([(torch.ones(7, 1), cycle(7))]).argmax(1).item())
نُفّذ هذا الكود بتاريخ 2026-11-20 في 5.3 ثانية (PyTorch (CPU), Python 3 – local build machine).
من مخرجاته:
test accuracy = 1.000
عدد المعاملات القابلة للتدريب في المثال: model = 5٬543.
هذه النتائج لبيانات اصطناعية صغيرة وعدد حقب قليل، وتُثبت أن الكود يعمل فقط؛ لا تقارنها بالنتائج المنشورة.
جرّب وتعمّق
- مستكشف الشبكات البيانية
- أطلس نماذج الذكاء الاصطناعي قسم آخر في الموقع
- مختبر الشبكات العصبية البيانية قسم آخر في الموقع
معماريات مرتبطة
الشبكة الالتفافية البيانية
Graph Convolutional Network (GCN)
طبقة بيانية بسيطة تأخذ متوسطاً مطبّعاً لتمثيلات العقدة وجيرانها ثم تطبق تحويلاً خطياً مشتركاً، وهي تقريب من الدرجة الأولى للالتفاف الطيفي.
جراف سيج
GraphSAGE
إطار استقرائي يتعلم دوال تجميع لجوار عيّني من الجيران، فيستطيع حساب تمثيلات لعقد جديدة لم ترها الشبكة أثناء التدريب.
محوّل الرسوم البيانية
Graph Transformer (GT)
تطبيق الانتباه الذاتي على عقد الرسم مع ترميزات موضعية أو بنيوية (مثل متجهات لابلاسيان الذاتية) كي يعرف النموذج بنية الرسم، فيتجاوز قيود الجوار المحلي.
الشبكات العصبية المتكافئة
Equivariant Neural Networks (ENN)
شبكات تُبنى بحيث يتحول خرجها بطريقة محددة عندما يتحول الدخل بتناظر ما (دوران، إزاحة، انعكاس، تبديل)، فلا تحتاج إلى تعلم هذا التناظر من البيانات، وتعمم إلى وضعيات لم ترها.
لا توجد نتائج مطابقة للمرشحات.
أفكار بحثية
- دمج ترميزات موضعية (Laplacian PE) مع GIN لتجاوز حد 1-WL في رسوم جزيئية.
اقتراحات للانطلاق وليست فجوات بحثية مؤكدة؛ راجع الأدبيات الحديثة قبل اعتمادها.
اختبر فهمك
لماذا تستخدم GIN المجموع بدلاً من المتوسط؟
لماذا؟ المتوسط يعطي النتيجة نفسها لـ {1,1} و{1}.
ما الحد الأعلى النظري لقدرة GIN التمييزية؟
لماذا؟ أثبت المؤلفون أن MPNN لا تتجاوز 1-WL وأن GIN تبلغه.
مع $\epsilon=0$ و$h_v=2$ وجيران $1,1,3$، ما دخل MLP؟
لماذا؟ $(1+0)\cdot2+1+1+3=7$.
المراجع
Xu, K., Hu, W., Leskovec, J., & Jegelka, S. (2019). How powerful are graph neural networks?. International Conference on Learning Representations (ICLR). https://arxiv.org/abs/1810.00826
Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., & Dahl, G. E. (2017). Neural message passing for quantum chemistry. International Conference on Machine Learning (ICML), PMLR 70, 1263–1272. https://arxiv.org/abs/1704.01212
