كتب الذكاء الاصطناعيمشاريع الذكاء الاصطناعيمقالات الذكاء الاصطناعيمعجم الذكاء الاصطناعياسئلة واجوبة في الذكاء الاصطناعيأكاديمية الذكاء الاصطناعي للأطفالأكاديمية الذكاء الاصطناعيمدرسة رياضيات الذكاء الاصطناعيمختبر الذكاء الاصطناعيمختبر الخوارزميات المستوحاة من الطبيعةأطلس نماذج الذكاء الاصطناعيموسوعة تطبيقات الذكاء الاصطناعيمستكشف مجموعات البيانات للذكاء الاصطناعياختبارات الذكاء الاصطناعيالفايب كودينغدليل البرمجة بالذكاء الاصطناعيمولّد مشاريع الذكاء الاصطناعيمرصد الذكاء الاصطناعيدليل أدوات الذكاء الاصطناعي البحث والنشر الأكاديميمكتبة البرومبتات الأكاديميةمستودع الرسائل والأطاريح في الذكاء الاصطناعيحاسبة الترقية العلميةأكاديمية الوكلاء الذكيينمختبر أخلاقيات الذكاء الاصطناعي والعدالةساحة ألعاب الذكاء الاصطناعيعبقري الذكاء الاصطناعيمختبر التنبؤ بالسلاسل الزمنيةمتحف الذكاء الاصطناعيمختبر الرؤية الحاسوبيةموسوعة شبكات التعلم العميق الحديثةمختبر الشبكات العصبية البيانيةمختبر تحليل الصور الطبيةمختبر معالجة اللغة الطبيعيةمختبر الحوسبة الكمّيةخرائط طريق الذكاء الاصطناعيأكاديمية ماتلاب والذكاء الاصطناعيمصمم الشبكات العصبيةأكاديمية الذكاء الاصطناعي بدون برمجةمختبر الذكاء الاصطناعي الكمّي

نظرية الرسوم الطيفية: مصفوفة لابلاسيان وتحويل فورييه البياني

Spectral Graph Theory: the Laplacian and the Graph Fourier Transform

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

النظرية الطيفية والانتقال إلى المكانيمتقدم30 دقيقة قراءةالدرس 5 من 23

أهداف الدرس

  • تعريف لابلاسيان التجميعي والمطبّع وخصائصهما
  • تفسير القيم الذاتية بوصفها ترددات والمتجهات الذاتية بوصفها أنماطاً على الرسم
  • صياغة تحويل فورييه البياني والالتفاف الطيفي
  • فهم لماذا تعمل GCN مرشحاً منخفض التمرير

1 مصفوفة لابلاسيان

لابلاسيان الرسم (Graph Laplacian) هو L = D − A. تكمن أهميته في الشكل التربيعي: لأي إشارة x على العقد (قيمة لكل عقدة)، xᵀLx يساوي مجموع مربعات الفروق بين قيم العقد المتصلة. أي أنه يقيس «خشونة» الإشارة على الرسم: إذا كانت القيم متقاربة بين الجيران كانت القيمة صغيرة. ولأن الدرجات تتفاوت نستخدم غالباً اللابلاسيان المطبّع المتماثل الذي تقع قيمه الذاتية في المجال [0, 2].

L = D - A,\qquad x^{\top}Lx = \sum_{(i,j)\in E}(x_i-x_j)^2
اللابلاسيان التجميعي وشكله التربيعي الذي يقيس تغيّر الإشارة بين الجيران.
L_{\text{sym}} = I - D^{-\frac12} A D^{-\frac12},\qquad 0=\lambda_1\le\lambda_2\le\dots\le\lambda_n\le 2
اللابلاسيان المطبّع المتماثل ومجال قيمه الذاتية.

2 التحليل الذاتي: ترددات الرسم

لأن L متماثلة شبه موجبة، يمكن تحليلها L = UΛUᵀ، حيث أعمدة U متجهات ذاتية متعامدة وΛ قطرية تحمل القيم الذاتية. المتجه الذاتي المقابل لأصغر قيمة ذاتية (0) ثابت على كل مكوّن متصل: إشارة «ناعمة» تماماً. كلما كبرت القيمة الذاتية تذبذب المتجه الذاتي أكثر بين العقد المتجاورة. لذا تُفهم القيم الذاتية ترددات، والمتجهات الذاتية أنماطاً اهتزازية للرسم، بالضبط كما تفعل الجيوب وجيوب التمام في تحليل فورييه الكلاسيكي.

عدد القيم الذاتية الصفرية يساوي عدد المكونات المتصلة، والقيمة الذاتية الثانية λ₂ (قيمة فيدلر) تقيس مدى ترابط الرسم، ويُستخدم متجهها في التقسيم الطيفي للمجتمعات.

3 تحويل فورييه البياني والالتفاف

تحويل فورييه البياني (Graph Fourier Transform) لإشارة x هو إسقاطها على المتجهات الذاتية: x̂ = Uᵀx، والتحويل العكسي x = Ux̂. وفق مبرهنة الالتفاف، الالتفاف في المجال الأصلي ضرب نقطي في مجال التردد. لذا يُعرّف الالتفاف الطيفي على الرسم بأنه: حوّل الإشارة، اضرب كل مركّب ترددي بمعامل مرشح g(λ)، ثم أعد التحويل.

هذه الصياغة أنيقة لكنها مكلفة: التحليل الذاتي يحتاج O(n³)، والضرب في U كثيف O(n²)، والمرشح المعرّف بقيم حرة لكل تردد غير موضعي ولا ينتقل إلى رسم آخر لأن له أساساً ذاتياً مختلفاً. الدرس التالي يشرح كيف حلّت ChebNet ثم GCN هذه المشكلات.

\hat{x} = U^{\top}x,\qquad x = U\hat{x}
تحويل فورييه البياني وعكسه.
g_\theta \star x = U\, g_\theta(\Lambda)\, U^{\top}x
الالتفاف الطيفي: ترشيح الترددات بالدالة g ثم العودة إلى المجال الأصلي.
xsignalUᵀxgraph FTg_θ(Λ)filterU(·)inverse FTyfilteredL = I − D^-½ A D^-½ = U Λ Uᵀy = U g_θ(Λ) Uᵀ x
الترشيح الطيفي: تحويل فورييه البياني، ثم ضرب في مرشح على القيم الذاتية، ثم التحويل العكسي.

4 الترشيح منخفض التمرير وتفسير GCN

إذا اخترنا g(λ) = 1 − λ نحصل على عملية تُبقي الترددات المنخفضة (القيم الذاتية الصغيرة) وتخمد العالية: مرشح تمرير منخفض (Low-pass). وبالتعويض نجد أن هذا المرشح يساوي ضرب الإشارة في D^{-1/2}AD^{-1/2}، أي متوسط موزون لقيم الجيران. إضافة الحلقات الذاتية (حيلة إعادة التطبيع في GCN) تقلّص المجال الطيفي فتجعل الترشيح أكثر استقراراً.

هذا التفسير يشرح نجاح GCN وفشلها معاً: في الرسوم المتجانسة تكون الفئات «إشارات ناعمة» على الرسم فيفيد الترشيح المنخفض، وتكرار الترشيح مرات كثيرة يمحو كل التفاصيل حتى تتطابق التمثيلات، وهو التنعيم المفرط. وفي الرسوم غير المتجانسة تحمل المعلومة ترددات عالية يحذفها المرشح.

U(I-\Lambda_{\text{sym}})U^{\top}x = D^{-\frac12} A D^{-\frac12}x
المرشح الخطي 1−λ يساوي ضرب الإشارة بمصفوفة الجوار المطبّعة.

خلاصة الدرس

  • اللابلاسيان يقيس نعومة الإشارة على الرسم
  • القيم الذاتية ترددات والمتجهات الذاتية أنماط
  • الالتفاف الطيفي ضرب في مجال التردد، لكنه مكلف وغير موضعي
  • GCN مرشح منخفض التمرير، وهذا يفسر نجاحها في التجانس والتنعيم المفرط مع العمق

تحقّق من فهمك

فكّر في الإجابة أولاً، ثم افتح السؤال لترى الجواب.

كم قيمة ذاتية صفرية للابلاسيان رسم فيه ثلاثة مكونات متصلة؟

ثلاث قيم ذاتية صفرية، واحدة لكل مكوّن.

لماذا لا يُستخدم الالتفاف الطيفي الكامل على الرسوم الكبيرة؟

لأنه يتطلب التحليل الذاتي O(n³) وضرباً كثيفاً O(n²)، ولأن مرشحه غير موضعي ولا ينتقل بين الرسوم.

تابع التعلّم

نماذج في هذا الدرس

مفاهيم مرتبطة

طبّق في المختبر: مختبر الخوارزميات

المراجع

  1. Shuman, D. I., Narang, S. K., Frossard, P., Ortega, A., & Vandergheynst, P. (2013). The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains. IEEE Signal Processing Magazine. DOI: 10.1109/MSP.2012.2235192 · arXiv: 1211.0053مدخل معالجة الإشارات على الرسوم: تحويل فورييه البياني والمرشحات.
  2. Bruna, J., Zaremba, W., Szlam, A., & LeCun, Y. (2014). Spectral Networks and Locally Connected Networks on Graphs. International Conference on Learning Representations (ICLR). arXiv: 1312.6203أول شبكة التفافية طيفية على الرسوم.
  3. Defferrard, M., Bresson, X., & Vandergheynst, P. (2016). Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering. Advances in Neural Information Processing Systems (NeurIPS). arXiv: 1606.09375ChebNet: مرشحات متعددات حدود تشيبيشيف موضعية ورخيصة.
  4. Kipf, T. N., & Welling, M. (2017). Semi-Supervised Classification with Graph Convolutional Networks. International Conference on Learning Representations (ICLR). arXiv: 1609.02907الورقة الأصلية لـ GCN ومصدر التطبيع المتماثل للمصفوفة.
  5. Wu, F., Zhang, T., de Souza, A. H., Fifty, C., Yu, T., & Weinberger, K. Q. (2019). Simplifying Graph Convolutional Networks. International Conference on Machine Learning (ICML). arXiv: 1902.07153SGC: إزالة اللاخطية وضغط K طبقة في ضرب واحد.