تعلم الرسوم البيانية2014متقدم10 دقيقة قراءة

الشبكات الطيفية والشبكات العميقة محلية الاتصال على الرسوم البيانية

Spectral Networks and Deep Locally Connected Networks on Graphs

Bruna, J. · Zaremba, W. · Szlam, A. · LeCun, Y. — ICLR

المشكلة

تستغل الشبكات العصبية الالتفافية ثلاث خصائص أساسية في الشبكات المنتظمة: الذي يتيح ، والمحلّية التي تسمح بمرشّحات صغيرة الحجم، والبنية متعددة المقاييس التي تمكّن من عمليات التجميع. لكن كثيراً من البيانات الحقيقية تقع على رسوم بيانية غير منتظمة — كالشبكات الاجتماعية، والأسطح ثلاثية الأبعاد، وشبكات الحسّاسات — حيث لا توجد مجموعة إزاحة ثابتة، ولا شبكة بكسلات منتظمة، ولا طريقة واضحة لتمرير مرشّح عبر البنية. أمّا الطبقات كاملة الاتصال فتتجاهل بنية الرسم البياني وتحتاج إلى O(n²) معاملاً، ممّا يجعلها غير عملية على الرسوم البيانية الكبيرة.

الإسهام

تقدّم الورقة بناءين لتعميم الشبكات الالتفافية على الرسوم البيانية. البناء المكاني يعتمد على التجميع الهرمي وحقول الاستقبال المحلية لإنشاء طبقات محلية الاتصال بعدد معاملات O(n). أمّا البناء الطيفي فيعتمد على تحليل القيم والمتّجهات الذاتية للابلاسيان لتعريف الالتفاف في المجال الترددي، ممّا يتيح تعلُّم مرشّحات بعدد O(n) — أو حتى O(1) — من المعاملات لكل خريطة سمات عبر مُضاعِفات طيفية ناعمة. كلا البناءين يدعمان التجميع من خلال تخشين الرسم البياني.

الأثر

الورقة التأسيسية التي أطلقت الشبكات العصبية البيانية الطيفية. أثبتت أن المتّجهات الذاتية للابلاسيان تعمل كأساس فورييه للرسوم البيانية، ممّا فتح الباب أمام الالتفاف على مجالات غير منتظمة. شبكات ChebNet وGCN وكامل سلالة الشبكات البيانية الطيفية تنحدر مباشرةً من هذا العمل. ربطت الورقة بين معالجة الإشارات على الرسوم البيانية والتعلّم العميق، وأشعلت شرارة مجال التعلّم العميق الهندسي.

التقليدية تشبه مفتّش طوابع في مكتب بريد: يمسك ختماً واحداً ويمرّره على صفحة طوابع مرتّبة في شبكة منتظمة، يفحص كل خانة بالأسلوب نفسه.

الآن تخيّل أن الطوابع مبعثرة على خريطة مجعّدة — لا صفوف ولا أعمدة ولا ترتيب. المفتّش لم يعد قادراً على تمرير ختمه بالطريقة المعتادة.

هذه الورقة تقترح حلّين: (1) أعطِ المفتّش عدسة مكبّرة مرنة تتكيّف مع جوار كل عقدة — وهذا هو البناء المكاني، أو (2) افرد الخريطة المجعّدة وحوّلها إلى ترددات موسيقية باستخدام ، رشِّح تلك الترددات، ثم أعِد طيّها — وهذا هو البناء الطيفي.

المشكلة: الشبكات الالتفافية تفترض بنية منتظمة لا تملكها الرسوم البيانية

تستمد الشبكة الالتفافية التقليدية قوّتها من ثلاث خصائص بنيوية في الشبكات المنتظمة:

ثبات الإزاحة — المرشّح نفسه يُطبَّق في كل موضع بفضل ، فينخفض عدد المعاملات من O(n²) إلى O(n).
المحلّية — كل مرشّح لا يرى سوى رقعة صغيرة (مثلاً 3×3)، ممّا يخفض المعاملات أكثر إلى O(S) حيث S هو حجم المرشّح.
متعدد المقاييس — التجميع فوق كتل ثنائية (2×2) يُقلّص الأبعاد المكانية بمعامل 4 في كل طبقة، فيُنتج هرمية طبيعية من السمات.

على الرسم البياني، لا شيء من هذا متاح تلقائياً. لا يوجد مفهوم «يمين» أو «يسار»، وعدد جيران كل عقدة قد يختلف تماماً، ولا توجد طريقة بديهية لتخشين البنية. الشبكة الالتفافية التقليدية ببساطة لا يمكن تطبيقها هنا. فيصبح السؤال: أيّ أجزاء من وصفة الشبكة الالتفافية يمكننا إنقاذها، وكيف؟

افتح في المختبر

يساراً: شبكة منتظمة ينزلق عليها الالتفاف بسلاسة. يميناً: رسم بياني غير منتظم حيث تختلف ارتباطات كل عقدة. بدّل بينهما للمقارنة.

تستيقظ التجربة عند وصولك…

البناء الأول — المكاني: حقول استقبال محلية على الرسوم البيانية

الفكرة هنا مباشرة: حدّد «الجوار» على الرسم البياني بالاعتماد على أوزان الحواف، ثم ابنِ طبقات لا ترى إلا جيران كل عقدة — تماماً كما يرى رقعة صغيرة من الصورة، لكن هنا شكل الرقعة يتغيّر من عقدة لأخرى.

في رسم بياني موزون $G = (\Omega, W)$ ، يُعرَّف جوار العقدة $j$ بوضع عتبة: $N_\delta(j) = \{i : W_{ij} > \delta\}$ . المرشّح هنا عبارة عن مصفوفة متناثرة عناصرها غير الصفرية تقع فقط في مواضع الجيران، فينخفض عدد المعاملات من O(n²) إلى O(S·n) حيث S هو متوسط حجم الجوار.

أمّا التجميع، فيتحقق عبر تجميع هرمي تراكمي: تُدمج العقد المتقاربة في عقد أكبر، ممّا يُنتج نسخاً أخشن من الرسم البياني. كل طبقة تحوّل إشارة على رسم بياني ناعم إلى إشارة على رسم بياني أخشن — وهي نفس المقايضة المعروفة في الشبكات الالتفافية التقليدية: نضحّي بالدقة المكانية مقابل قنوات سمات أكثر.

x_{k+1,j} = L_k \; h\!\left(\sum_{i=1}^{f_{k-1}} F_{k,i,j} \; x_{k,i}\right) \quad (j = 1 \dots f_k)

الطبقة المكانية — ترشيح محلي + تجميع — F_{k,i,j} مرشّح متناثر (غير صفري فقط في مواضع الجيران) · h دالة لاخطية (ReLU) · L_k يجمّع فوق كل عنقود في الرسم البياني المُخشَّن · الخَرج يستبدل العقد المكانية بقنوات سمات

افتح في المختبر

انقر على أي عقدة لترى حقل استقبالها المحلي. لاحظ كيف يختلف شكل الجوار من عقدة لأخرى — بخلاف مرشّح 3×3 الثابت في الشبكات المنتظمة.

تستيقظ التجربة عند وصولك…

البناء الثاني — الطيفي: الالتفاف عبر لابلاسيان الرسم البياني

الملاحظة الجوهرية هنا: على الشبكة المنتظمة، يكافئ الضرب في مجال فورييه. وأساس فورييه على تلك الشبكة ليس سوى لمؤثّر لابلاس.

على الرسم البياني العام، يلعب لابلاسيان الرسم البياني $L = D - W$ الدور نفسه — حيث $D$ هي و $W$ هي . متّجهاته الذاتية $V = [v_0, v_1, \dots, v_{n-1}]$ تمثّل أساس فورييه للرسم البياني، وقيمه الذاتية $\lambda_0 \leq \lambda_1 \leq \dots$ تعبّر عن التردد — أي عن مدى سرعة تغيُّر الإشارة عبر الحواف.

تخيّل الأمر كآلة موسيقية. المتّجه الذاتي الأدنى $v_0$ ثابت القيمة على كل العقد — إنه «النغمة الأساسية» التي تهتزّ فيها كل العقد بتناغم. كلّما صعدنا إلى متّجهات ذاتية أعلى، زاد التذبذب والتقطت بنية أدق، كالنغمات التوافقية. وأي إشارة على الرسم البياني يمكن تفكيكها إلى هذه «النغمات»، تماماً كما نفكّك موجة صوتية إلى تردداتها.

هذا التفكيك هو ما يُمكّن الالتفاف الطيفي: حوّل الإشارة إلى المجال الترددي (اضربها في $V^T$ )، ثم طبِّق مرشّحاً قُطرياً، ثم أعِد التحويل (اضرب في $V$ ).

افتح في المختبر

اسحب المنزلق للتنقل بين المتّجهات الذاتية — من النغمة الأساسية الناعمة إلى التذبذبات عالية التردد.

تستيقظ التجربة عند وصولك…

x_{k+1,j} = h\!\left(V \sum_{i=1}^{f_{k-1}} F_{k,i,j} \; V^T x_{k,i}\right) \quad (j = 1 \dots f_k)

طبقة الالتفاف الطيفي — المعادلة المحورية — V = المتّجهات الذاتية للابلاسيان (أساس فورييه للرسم البياني) · V^T x = تحويل فورييه الأمامي على الرسم البياني · F_{k,i,j} = مرشّح قُطري في المجال الترددي · V(...) = التحويل العكسي إلى مجال الرسم البياني · h = دالة لاخطية

يمكن قراءة المعادلة كخط معالجة من ثلاث مراحل:

تحليل: أسقِط الإشارة على أنماط التردد في الرسم البياني ( $V^T x$ )
ترشيح: اضبط كل تردد بشكل مستقل عبر المرشّح القُطري ( $F$ )
تركيب: أعِد تجميع الترددات المُرشَّحة في إشارة على الرسم البياني ( $V \cdot$ )

كل مرشّح قُطري يملك $d$ معاملاً (واحداً لكل تردد نحتفظ به)، أي $O(n)$ معاملاً لكل . وإذا اقتصرنا على أول $d$ متّجه ذاتي فقط (أي قطع الترددات العالية)، تنخفض التكلفة الحسابية أكثر.

افتح في المختبر

شاهد إشارة تُفكَّك إلى ترددات الرسم البياني، ثم تُرشَّح، ثم يُعاد بناؤها — خط معالجة الالتفاف الطيفي أثناء العمل.

تستيقظ التجربة عند وصولك…

حيلة O(1): المُضاعِفات الطيفية الناعمة

في الشبكات المنتظمة، هناك علاقة ثنائية معروفة: المرشّح المدمج مكانياً له استجابة ترددية ناعمة، والعكس صحيح. برونا وزملاؤه يستغلون هذه الثنائية على الرسوم البيانية: بدلاً من تعلُّم معامل حرّ لكل تردد، يُعبّرون عن المرشّح كمنحنى ناعم يمتدّ فوق الطيف باستخدام استيفاء بالشرائح المكعّبة.

عملياً، العناصر القُطرية $d$ للمرشّح $F$ تُولَّد من $q$ معامل فقط عبر نواة استيفاء $\mathcal{K}$ :

\text{diag}(F_{k,i,j}) = \mathcal{K} \, \alpha_{k,i,j}

مُضاعِف طيفي ناعم عبر الاستيفاء بالشرائح المكعّبة — K = نواة شرائح مكعّبة ثابتة (d × q) · α = معاملات الشريحة القابلة للتعلّم (عددها q فقط!) · إذا كان q ثابتاً بغض النظر عن حجم الرسم البياني ← O(1) معامل لكل مرشّح

افتح في المختبر

قارن بين مرشّح طيفي حرّ (مشوَّش وغير محلّي) ومرشّح ناعم بالشرائح المكعّبة (نظيف ومحلّي). اسحب منزلق النعومة لترى الفرق.

تستيقظ التجربة عند وصولك…

تعمّق: لابلاسيان الرسم البياني كمحلّل ترددات

لابلاسيان الرسم البياني $L = D - W$ يقيس مقدار اختلاف الإشارة بين كل عقدة وجيرانها. لإشارة $x$ معرَّفة على الرسم البياني، يمكن قياس نعومتها بالصيغة التالية:

\|\nabla x\|_W^2 = \sum_i \sum_j W_{ij} [x(i) - x(j)]^2 = x^T L \, x

نعومة الإشارة البيانية عبر الصيغة التربيعية للابلاسيان — قيمة كبيرة ← الإشارة تتغيّر سريعاً عبر الحواف (تردد عالٍ) · قيمة صغيرة ← الإشارة ناعمة والعقد المتجاورة لها قيم متقاربة · المتّجهات الذاتية لـ L مرتّبة حسب القيم الذاتية تُشكّل أساساً متعامداً من الأنعم إلى الأشد تذبذباً

المتّجهات الذاتية و لـ $L$ تكشف لنا عن بنية الإشارة على الرسم البياني:

$v_0$ (قيمة ذاتية 0): المتّجه الثابت — كل العقد تحمل القيمة نفسها، لا تباين. هذا يقابل «المُركَّب المستمر» (DC).
المتّجهات الذاتية المنخفضة: أنماط ناعمة واسعة النطاق — العقد داخل المجتمع الواحد تميل إلى حمل قيم متقاربة.
المتّجهات الذاتية المرتفعة: أنماط تذبذبية سريعة — تغيُّرات حادة بين عقد متجاورة.

النقطة المهمة: على الشبكة المنتظمة، المتّجهات الذاتية للابلاسيان هي بالضبط أساس فورييه المعتاد (الجيب وجيب التمام). لذلك لابلاسيان الرسم البياني هو التعميم الطبيعي: فهو يسترجع تحليل فورييه التقليدي كحالة خاصة.

اختبار سلامة: استعادة الشبكات الالتفافية التقليدية من المنظور الطيفي

تقدّم الورقة ربطاً أنيقاً: إذا بنينا رسماً بيانياً من صور طبيعية باستخدام مصفوفة التغايُر بين البكسلات كمصفوفة أوزان، فإن المتّجهات الذاتية للابلاسيان تتحوّل إلى أساس تحويل جيب التمام المتقطّع (DCT) — وهي بالضبط أنماط فورييه التقليدية على الشبكة المنتظمة. والمؤثّرات القُطرية على هذا الطيف ليست سوى عمليات التفاف.

المعنى واضح: تطبيق البناء الطيفي على شبكة صور منتظمة بأوزان مبنية على التغايُر يسترجع الشبكات الالتفافية التقليدية كحالة خاصة، دون أي معرفة مسبقة ببنية الشبكة. وهذا يؤكّد أن المنهج الطيفي تعميم حقيقي وليس خوارزمية مختلفة.

الفكرة نفسها في شيفرة برمجية

الالتفاف الطيفي على الرسوم البيانية — كاملاًpython

مبسَّط لإظهار الفكرة — ليس التنفيذ الحقيقي.

import numpy as np

def graph_laplacian(W):
    """حساب لابلاسيان الرسم البياني التوافقي L = D - W."""
    D = np.diag(W.sum(axis=1))      # مصفوفة الدرجات
    return D - W

def graph_fourier_basis(L, d=None):
    """المتّجهات الذاتية لـ L = أساس فورييه للرسم البياني، مرتّبة حسب التردد."""
    eigenvalues, V = np.linalg.eigh(L)   # eigh → مرتّبة وحقيقية
    if d is not None:
        V = V[:, :d]                      # احتفظ فقط بأدنى d تردد
        eigenvalues = eigenvalues[:d]
    return eigenvalues, V

def spectral_conv(x, V, F_diag):
    """
    x:      (n,) إشارة على الرسم البياني
    V:      (n, d) أول d نمط فورييه
    F_diag: (d,) مرشّح قُطري قابل للتعلم في المجال الترددي
    """
    x_hat = V.T @ x              # الخطوة 1: تحويل فورييه على الرسم البياني
    x_filtered = F_diag * x_hat  # الخطوة 2: الترشيح في المجال الترددي
    return V @ x_filtered        # الخطوة 3: التحويل العكسي

def smooth_filter(alpha, K):
    """
    توليد مرشّح طيفي ناعم من معاملات الشريحة.
    alpha: (q,) معاملات الشريحة القابلة للتعلم
    K:     (d, q) نواة استيفاء الشرائح المكعّبة الثابتة
    """
    return K @ alpha              # مرشّح ناعم بأبعاد d من q معامل فقط

# مثال: ابنِ رسماً بيانياً، احسب لابلاسيانه، ثم شغّل الالتفاف الطيفي
n = 100
W = np.random.rand(n, n)
W = (W + W.T) / 2                # تناظر
np.fill_diagonal(W, 0)           # بلا حلقات ذاتية
W[W < 0.7] = 0                   # تخفيف الكثافة

L = graph_laplacian(W)
eigenvalues, V = graph_fourier_basis(L, d=30)

x = np.random.randn(n)           # إشارة عشوائية على الرسم البياني
F_diag = np.random.randn(30)     # مرشّح قابل للتعلم (30 معاملاً)
y = spectral_conv(x, V, F_diag)  # الإشارة المُرشَّحة

التجارب: MNIST على مجالات غير منتظمة

اختبر المؤلفون كلا البناءين على نسختين من MNIST لا يمكن فيهما تطبيق الشبكات الالتفافية التقليدية:

MNIST بعد الاختزال — تُختار 400 نقطة عشوائياً من شبكة 28×28، ممّا يدمّر البنية المنتظمة. ثم يُبنى رسم بياني بناءً على القرب المكاني بين هذه النقاط. شبكة المحلية خفّضت الخطأ من 4.11% (أقرب جار) إلى 1.3%، بينما البناء الطيفي الناعم حقّق 1.8% بعدد معاملات أقل بكثير.

MNIST الكروي — تُسقَط الأرقام على 4096 نقطة عشوائية فوق كرة ثلاثية الأبعاد مع تدويرات عشوائية. هذه مسألة أصعب بمراحل (أقرب جار يعطي 19% خطأ مع تدويرات خفيفة، و80% مع تدويرات كاملة). كلا البناءين يتفوقان بوضوح على خط الأساس، ويحقّق البناء الطيفي الناعم أفضل النتائج (50% خطأ تحت تدويرات كاملة مقابل 80% لأقرب جار).

الاستنتاج الأهم: البناء الطيفي الناعم يتفوق باستمرار على النسخة الطيفية الحرة (غير المقيّدة)، ممّا يؤكّد أن فرض النعومة في المجال الترددي يُنتج مرشّحات محلية مكانياً.

افتح في المختبر

قارن معدلات الخطأ وأعداد المعاملات عبر البنيات المختلفة على نسختَي MNIST المختزلة والكروية.

تستيقظ التجربة عند وصولك…

لماذا كانت هذه الورقة مهمّة

الورقة التي فتحت باب التعلم العميق للبيانات البيانية

قبل هذا العمل، كان محصوراً في البنى المنتظمة — الصور والصوت والتسلسلات. ما أثبته برونا وزملاؤه هو أن لابلاسيان الرسم البياني يوفّر الجسر الرياضي لنقل الالتفاف إلى أي بنية غير منتظمة. وتبرز من هذا العمل نتيجتان محوريتان:

الالتفاف الطيفي على الرسوم البيانية التفاف حقيقي — على الشبكات المنتظمة يتحوّل بالضبط إلى التفاف الشبكات الالتفافية التقليدي، ممّا يؤكّد أنه تعميم صادق وليس بديلاً تقريبياً.

المرشّحات الطيفية الناعمة تحقّق محلّية مكانية — الثنائية المعروفة بين النعومة الطيفية والاندماج المكاني تنتقل من تحليل فورييه الكلاسيكي إلى الرسوم البيانية، ممّا يتيح مرشّحات بعدد ثابت O(1) من المعاملات.

2014
هذه الورقة — الشبكات الطيفية (برونا وآخرون)
أول من عرّف الالتفافات الطيفية والمكانية على الرسوم البيانية. قدّمت المتّجهات الذاتية للابلاسيان كأساس فورييه، واقترحت مُضاعِفات طيفية ناعمة لبناء مرشّحات بعدد O(1) من المعاملات.
2016
ChebNet (ديفيرار وآخرون)
استبدلت المرشّحات الطيفية الحرة بتقريبات عبر متعددات حدود تشيبيشيف، ممّا أغنى عن التفكيك الذاتي المُكلِف. النتيجة: مرشّحات محلية فعلياً تعمل ضمن جوار k قفزات.
2017
GCN (كيبف وويلينغ)
اختصرت ChebNet إلى تقريب تشيبيشيف من الرتبة الأولى (قفزة واحدة)، وأضافت حيلة إعادة التسوية، وحقّقت نتائج متقدّمة في تصنيف العقد شبه المُوجَّه. هي الورقة التي نقلت الشبكات العصبية البيانية إلى التيار السائد.
2017
GraphSAGE (هاميلتون وآخرون)
قدّم أسلوباً استقرائياً للتعلّم على الرسوم البيانية يعتمد على اختيار عيّنات من الجيران وتجميع سماتهم، ممّا أغنى عن حساب لابلاسيان الرسم البياني الكامل وقت الاختبار.
2018
GAT (فيلتشكوفيتش وآخرون)
طبّقت شبكات الانتباه البيانية آلية الانتباه على الرسوم البيانية، فتعلّمت أوزاناً تكيّفية بين الجيران تعتمد على البيانات نفسها بدلاً من مرشّحات طيفية أو مكانية ثابتة.
2020
الشبكات البيانية تغزو الجزيئات والفيزياء والتوصيات
أصبحت الشبكات العصبية البيانية الأداة المعتمدة للتنبؤ بخصائص الجزيئات ومحاكاة الفيزياء وأنظمة التوصيات — وكلها مجالات تتوزّع فيها البيانات طبيعياً على رسوم بيانية.

المرجعBruna, Zaremba, Szlam, LeCun. Spectral Networks and Locally Connected Networks on Graphs. ICLR, 2014.

مصطلحات هذه الورقة

الشبكات العصبية الرسومية (البيانية)Graph Neural Network (GNN)
الالتفاف الرسوميGraph Convolution
لابلاسيان الرسم البيانيGraph Laplacian
المجال الطيفيSpectral Domain
المتجه الذاتيEigenvector
القيمة الذاتيةEigenvalue
مصفوفة التجاورAdjacency Matrix
مصفوفة الدرجاتDegree Matrix
تمرير الرسائلMessage Passing
كثير حدود تشيبيشيفChebyshev Polynomial
الحقل الاستقبالي للعصبونReceptive Field
التجميع المكانيPooling
مشاركة الأوزانweight sharing
خريطة السماتFeature Map