تمثيل الرسوم: المصفوفات والقوائم والخصائص
Representing Graphs: Matrices, Lists and Features
كيف يُخزَّن الرسم البياني داخل الحاسوب وداخل مكتبات مثل PyTorch Geometric: مصفوفة الجوار الكثيفة والمتفرقة، وقائمة الروابط (COO)، ومصفوفة الخصائص، والرسوم الموجهة والموزونة والمتعددة، ولماذا يحدد التمثيل كلفة الذاكرة والحساب.
أهداف الدرس
- بناء مصفوفة الجوار ومصفوفة الدرجات لرسم صغير يدوياً
- التحويل بين مصفوفة الجوار وقائمة الروابط وصيغة edge_index في PyG
- فهم الفرق بين الرسوم الموجهة وغير الموجهة والموزونة والمتعددة
- تقدير كلفة التخزين الكثيف مقابل المتفرق
1 مصفوفة الجوار
لرسم فيه n عقدة، مصفوفة الجوار A مصفوفة مربعة n×n يكون فيها A_ij = 1 إذا وُجد رابط من العقدة i إلى العقدة j، و0 خلاف ذلك. في الرسم غير الموجه تكون المصفوفة متماثلة (A = Aᵀ)، وفي الرسم الموزون يوضع وزن الرابط بدل الواحد. مجموع الصف i هو درجة العقدة، ونجمع الدرجات في مصفوفة قطرية D.
لمصفوفة الجوار خاصية جبرية مفيدة: العنصر (i, j) في القوة A^k يساوي عدد المسارات بطول k من i إلى j. لهذا يُفهم تكديس k طبقة من GNN على أنه وصول إلى الجيران حتى المسافة k.
A_{ij}=\begin{cases}1 & (i,j)\in E\\ 0 & \text{otherwise}\end{cases},\qquad D_{ii}=\sum_j A_{ij}\left(A^{k}\right)_{ij} = \#\{\text{walks of length } k \text{ from } i \text{ to } j\}2 التخزين المتفرق وقائمة الروابط
معظم الرسوم الحقيقية متفرقة جداً: في شبكة اقتباس فيها مئة ألف ورقة قد يكون لكل ورقة عشرة روابط في المتوسط، أي أن مصفوفة الجوار الكثيفة تحوي عشرة مليارات خلية أغلبها أصفار. لذلك تخزن المكتبات الرسم بقائمة الروابط (Edge List) أو بصيغة الإحداثيات (COO): مصفوفة 2×|E| صفها الأول المصادر وصفها الثاني الوجهات. هذه بالضبط صيغة edge_index في PyTorch Geometric.
تنبيه مهم: في PyG يُخزَّن الرابط غير الموجه مرتين (i→j وj→i)، لذلك يكون عدد الروابط في توثيق المجموعات ضعف عدد الروابط غير الموجهة. هذا يفسر لماذا تذكر بعض المصادر أن Cora فيها 5,429 رابطاً وتذكر PyG أنها 10,556.
import torch
from torch_geometric.data import Data
# رسم مثلث غير موجه: 0-1، 1-2، 2-0 (كل رابط في الاتجاهين)
edge_index = torch.tensor([[0, 1, 1, 2, 2, 0],
[1, 0, 2, 1, 0, 2]], dtype=torch.long)
x = torch.tensor([[1.0, 0.0], [0.0, 1.0], [1.0, 1.0]]) # خصائص العقد n×F
data = Data(x=x, edge_index=edge_index)
print(data.num_nodes, data.num_edges) # 3 6
print(data.is_undirected()) # True3 مصفوفة الخصائص
إلى جانب البنية تحمل كل عقدة متجه خصائص طوله F، فنحصل على مصفوفة X حجمها n×F. في Cora مثلاً كل ورقة ممثلة بمتجه ثنائي طوله 1,433 يدل على وجود كلمات من قاموس ثابت. وقد تحمل الروابط خصائص E_attr حجمها |E|×F_e، مثل نوع الرابطة الكيميائية (أحادية، ثنائية، عطرية).
حين لا تتوفر خصائص للعقد يمكن استعمال متجه ثابت (كل العقد واحد) أو ترميز الدرجة أو ترميز one-hot لهوية العقدة. الخيار الأخير يجعل النموذج تحويلياً (Transductive) لأنه لا يعمم إلى عقد لم يرها.
4 أنواع الرسوم
اختيار النوع جزء من النمذجة وليس تفصيلاً تقنياً: تحويل رسم موجه إلى غير موجه مثلاً قد يحسّن الأداء في تصنيف العقد لأنه يضاعف الرسائل، لكنه يمحو معلومة الاتجاه.
- غير موجه: العلاقة متبادلة (صداقة، رابطة كيميائية).
- موجه: للعلاقة اتجاه (اقتباس، متابعة، تحويل مالي).
- موزون: لكل رابط شدة (مسافة، تكرار تفاعل).
- متعدد العلاقات: أكثر من نوع رابط بين العقد (رسوم المعرفة).
- غير متجانس: أنواع مختلفة من العقد (مستخدم، منتج، متجر).
- ثنائي التجزئة (Bipartite): الروابط فقط بين مجموعتين (مستخدمون ومنتجات).
- ديناميكي: تتغير العقد والروابط مع الزمن.
5 الكلفة الحسابية للتمثيل
التخزين الكثيف يكلف O(n²) ذاكرة بغض النظر عن عدد الروابط، والتخزين المتفرق يكلف O(|E|). وعملية الضرب A·X تكلف O(n²F) كثيفة و O(|E|F) متفرقة. لهذا تعتمد كل مكتبات GNN الحديثة على عمليات التجميع المتفرق (scatter / segment) بدل ضرب المصفوفات الكثيفة، إلا في الرسوم الصغيرة جداً أو في نماذج التجميع الكثيف مثل DiffPool.
\text{Dense: } O(n^{2})\qquad\text{Sparse (COO): } O(|E|)خلاصة الدرس
- مصفوفة الجوار تعرّف البنية، وقواها تعد المسارات
- المكتبات تخزن الرسوم متفرقة بصيغة edge_index (COO)
- الرابط غير الموجه يُعدّ مرتين في PyG
- خصائص العقد X وخصائص الروابط جزء أساسي من المدخل
تحقّق من فهمك
فكّر في الإجابة أولاً، ثم افتح السؤال لترى الجواب.
رسم غير موجه فيه 4 عقد و5 روابط. كم عموداً في edge_index بصيغة PyG؟
10 أعمدة، لأن كل رابط غير موجه يُخزَّن في الاتجاهين.
ماذا يعني العنصر (A³)_{ij}؟
عدد المسارات (walks) التي طولها 3 من العقدة i إلى العقدة j.
تابع التعلّم
نماذج في هذا الدرس
مفاهيم مرتبطة
المراجع
- Hamilton, W. L. (2020). Graph Representation Learning. Synthesis Lectures on Artificial Intelligence and Machine Learning, Morgan & Claypool. DOI: 10.2200/S01045ED1V01Y202009AIM046كتاب تعليمي شامل في تمثيل الرسوم وانتقال الرسائل.
- Fey, M., & Lenssen, J. E. (2019). Fast Graph Representation Learning with PyTorch Geometric. ICLR 2019 Workshop on Representation Learning on Graphs and Manifolds. arXiv: 1903.02428المكتبة المستخدمة في خادم Python الاختياري ومصدر إحصاءات مجموعات البيانات.
- PyG Team. PyTorch Geometric documentation. Official documentation. pytorch-geometric.readthedocs.ioالتوثيق الرسمي للمكتبة؛ منه أُخذت جداول إحصاءات المجموعات (الإصدار 2.8.1).
- Ma, Y., & Tang, J. (2021). Deep Learning on Graphs. Cambridge University Press. DOI: 10.1017/9781108924184كتاب مرجعي يغطي الأسس الطيفية والمكانية والتطبيقات.
