نظرية الرسوم الطيفية: مصفوفة لابلاسيان وتحويل فورييه البياني
Spectral Graph Theory: the Laplacian and the Graph Fourier Transform
الأساس الرياضي الذي خرجت منه الشبكات الالتفافية البيانية: مصفوفة لابلاسيان وصيغها المطبّعة، وتحليلها الذاتي، ومعنى «التردد» على الرسم، وتحويل فورييه البياني، والترشيح الطيفي، ولماذا يُعدّ ضرب مصفوفة الجوار المطبّعة مرشح تمرير منخفض.
أهداف الدرس
- تعريف لابلاسيان التجميعي والمطبّع وخصائصهما
- تفسير القيم الذاتية بوصفها ترددات والمتجهات الذاتية بوصفها أنماطاً على الرسم
- صياغة تحويل فورييه البياني والالتفاف الطيفي
- فهم لماذا تعمل 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)^2L_{\text{sym}} = I - D^{-\frac12} A D^{-\frac12},\qquad 0=\lambda_1\le\lambda_2\le\dots\le\lambda_n\le 22 التحليل الذاتي: ترددات الرسم
لأن 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}x4 الترشيح منخفض التمرير وتفسير 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خلاصة الدرس
- اللابلاسيان يقيس نعومة الإشارة على الرسم
- القيم الذاتية ترددات والمتجهات الذاتية أنماط
- الالتفاف الطيفي ضرب في مجال التردد، لكنه مكلف وغير موضعي
- GCN مرشح منخفض التمرير، وهذا يفسر نجاحها في التجانس والتنعيم المفرط مع العمق
تحقّق من فهمك
فكّر في الإجابة أولاً، ثم افتح السؤال لترى الجواب.
كم قيمة ذاتية صفرية للابلاسيان رسم فيه ثلاثة مكونات متصلة؟
ثلاث قيم ذاتية صفرية، واحدة لكل مكوّن.
لماذا لا يُستخدم الالتفاف الطيفي الكامل على الرسوم الكبيرة؟
لأنه يتطلب التحليل الذاتي O(n³) وضرباً كثيفاً O(n²)، ولأن مرشحه غير موضعي ولا ينتقل بين الرسوم.
تابع التعلّم
نماذج في هذا الدرس
مفاهيم مرتبطة
المراجع
- 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مدخل معالجة الإشارات على الرسوم: تحويل فورييه البياني والمرشحات.
- 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أول شبكة التفافية طيفية على الرسوم.
- 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: مرشحات متعددات حدود تشيبيشيف موضعية ورخيصة.
- Kipf, T. N., & Welling, M. (2017). Semi-Supervised Classification with Graph Convolutional Networks. International Conference on Learning Representations (ICLR). arXiv: 1609.02907الورقة الأصلية لـ GCN ومصدر التطبيع المتماثل للمصفوفة.
- 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 طبقة في ضرب واحد.
