خصائص الرسوم: الدرجة والمسارات والمركزية والتجانس
Graph Properties: Degree, Paths, Centrality and Homophily
مقاييس الرسوم التي يحتاجها كل باحث قبل بناء أي نموذج: توزيع الدرجات، والمسافات والقطر، ومعامل التجمع، والمركزيات، والمكونات المتصلة، ونسبة التجانس التي تحدد إلى حد كبير هل ستنجح GCN البسيطة أم لا.
أهداف الدرس
- حساب الدرجة والكثافة ومعامل التجمع لرسم صغير
- فهم مقاييس المركزية الأساسية (الدرجة، البينية، القرب، المتجه الذاتي/PageRank)
- حساب نسبة التجانس على مستوى الروابط والعقد
- ربط هذه الخصائص بقرارات تصميم النموذج
1 الدرجة وتوزيعها
درجة العقدة (Degree) عدد روابطها، وفي الرسم الموجه نميز الدرجة الداخلة والخارجة. توزيع الدرجات في كثير من الشبكات الحقيقية ذو ذيل طويل: قلة من العقد (المحاور Hubs) لها آلاف الروابط وأغلب العقد لها عدد قليل. هذا مهم لـ GNN لأن العقدة المحورية تستقبل رسائل كثيرة فيطغى عليها التجميع بالمجموع، ولأن الطبقة التي تعتمد على المتوسط تعامل عقدة لها جاران كعقدة لها ألف جار. التطبيع في GCN والمقيّسات في PNA جاءا أساساً لمعالجة هذا التفاوت.
\rho = \frac{2|E|}{n(n-1)}2 المسافات والقطر والمكونات
المسافة بين عقدتين طول أقصر مسار بينهما، وقطر الرسم أطول هذه المسافات. إذا كان قطر الرسم 10 وكانت المعلومة المطلوبة لعقدة ما على بعد 8، فإن GNN من طبقتين لن تراها أبداً، وتحتاج 8 طبقات على الأقل مع ما يجلبه العمق من مشكلات. والمكونات المتصلة (Connected Components) أجزاء الرسم المنفصلة عن بعضها؛ لا تنتقل أي رسالة بين مكونين، ولذلك تتعلم العقد في مكوّن صغير منعزل من خصائصها فقط.
3 معامل التجمع والمثلثات
معامل التجمع المحلي (Clustering Coefficient) لعقدة نسبة الروابط الموجودة فعلاً بين جيرانها إلى كل الروابط الممكنة بينهم، أي «هل أصدقائي أصدقاء بعضهم؟». الشبكات الاجتماعية عالية التجمع. معلومة مهمة: GNN القياسية التي تعتمد على انتقال الرسائل لا تستطيع عدّ المثلثات في الحالة العامة، لأنها محدودة بقوة اختبار Weisfeiler-Lehman، ولهذا تضاف أحياناً عدّادات البنى الفرعية خصائصَ إضافية.
C_i = \frac{2\,T_i}{d_i(d_i-1)}4 المركزية
\pi = \alpha\, e_i + (1-\alpha)\, D^{-1}\!A^{\top}\pi- مركزية الدرجة: الأهمية بعدد الروابط.
- مركزية البينية (Betweenness): كم مساراً أقصر يمر بالعقدة؛ العقد الجسرية عالية البينية وهي غالباً مواضع الانضغاط المفرط.
- مركزية القرب (Closeness): مقلوب متوسط المسافة إلى بقية العقد.
- مركزية المتجه الذاتي وPageRank: العقدة مهمة إذا ارتبطت بعقد مهمة. PageRank الشخصي أساس نموذج APPNP.
5 التجانس وعدم التجانس
التجانس (Homophily) ميل العقد المتصلة إلى الانتماء للفئة نفسها: الأوراق تقتبس أوراقاً في موضوعها، والأصدقاء يتشاركون الاهتمامات. نقيسه على مستوى الروابط بنسبة الروابط التي تصل عقدتين من الفئة نفسها. في Cora تقارب هذه النسبة 0.81، بينما تنخفض كثيراً في رسوم مثل Texas وChameleon (عدم التجانس Heterophily)، حيث يرتبط المحتالون بضحاياهم لا ببعضهم، وترتبط البروتينات المختلفة وظيفياً.
هذه النسبة من أهم ما تحسبه قبل التدريب: GCN تفترض ضمنياً التجانس لأنها تنعّم التمثيلات بين الجيران، وفي الرسوم غير المتجانسة قد تتفوق عليها MLP لا ترى الرسم إطلاقاً. ستعود إلى هذا في درس عدم التجانس.
h_{\text{edge}} = \frac{\left|\{(i,j)\in E : y_i = y_j\}\right|}{|E|}import torch
from torch_geometric.datasets import Planetoid
from torch_geometric.utils import homophily, degree
data = Planetoid(root="data", name="Cora")[0]
print("edge homophily:", homophily(data.edge_index, data.y, method="edge"))
deg = degree(data.edge_index[0], data.num_nodes)
print("mean degree:", deg.mean().item(), "max degree:", deg.max().item())خلاصة الدرس
- توزيع الدرجات غير المتوازن يؤثر في اختيار دالة التجميع والتطبيع
- قطر الرسم يحدد العمق اللازم لوصول المعلومة
- GNN القياسية لا تعد المثلثات عموماً
- نسبة التجانس مؤشر مبكر على ملاءمة GCN وأخواتها
تحقّق من فهمك
فكّر في الإجابة أولاً، ثم افتح السؤال لترى الجواب.
لماذا تُحسب نسبة التجانس قبل اختيار النموذج؟
لأن النماذج التي تنعّم التمثيلات بين الجيران (مثل GCN) تفترض أن الجيران متشابهون؛ إذا كانت النسبة منخفضة فقد تضر الرسائل أكثر مما تنفع.
ما علاقة مركزية البينية بالانضغاط المفرط؟
العقد الجسرية التي تمر بها مسارات كثيرة تُجبر على ضغط معلومات أجزاء واسعة من الرسم في متجه ثابت الطول، وهذا هو الانضغاط المفرط.
تابع التعلّم
نماذج في هذا الدرس
مفاهيم مرتبطة
المراجع
- Zhu, J., Yan, Y., Zhao, L., Heimann, M., Akoglu, L., & Koutra, D. (2020). Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs. Advances in Neural Information Processing Systems (NeurIPS). arXiv: 2006.11468H2GCN: فصل تمثيل العقدة عن جيرانها والجيران من الرتبة الثانية.
- Gasteiger, J. (Klicpera), Bojchevski, A., & Günnemann, S. (2019). Predict then Propagate: Graph Neural Networks meet Personalized PageRank. International Conference on Learning Representations (ICLR). arXiv: 1810.05997APPNP: فصل التنبؤ عن الانتشار عبر PageRank الشخصي.
- Hamilton, W. L. (2020). Graph Representation Learning. Synthesis Lectures on Artificial Intelligence and Machine Learning, Morgan & Claypool. DOI: 10.2200/S01045ED1V01Y202009AIM046كتاب تعليمي شامل في تمثيل الرسوم وانتقال الرسائل.
- Platonov, O., Kuznedelev, D., Diskin, M., Babenko, A., & Prokhorenkova, L. (2023). A critical look at the evaluation of GNNs under heterophily: Are we really making progress?. International Conference on Learning Representations (ICLR). arXiv: 2302.11640كشف التكرارات في Chameleon وSquirrel واقترح مجموعات بديلة مثل roman-empire.
