🤖 machine learning

Universality and Approximation Rates of Graph Neural Networks with Random Features

تثبت هذه الورقة أن الشبكات العصبية الرسومية ذات تمرير الرسائل التي تمتلك سمات عقد عشوائية جزئياً تتمتع بقدرات تقريب شاملة للدوال الثابتة التبادل والتماثلية على الرسوم البيعية الموجهة ثابتة الحجم، بينما تشتق أيضاً حدوداً عليا نظرية لمعدلات التقريب الخاصة بها بناءً على تعقيد الشبكة.

المؤلفون الأصليون: Lukas Gonon, Thilo Meyer-Brandis, Niklas Weber

نُشر 2026-07-30

📖 5 دقيقة قراءة🧠 قراءة متعمّقة

CC BY 4.0

المؤلفون الأصليون: Lukas Gonon, Thilo Meyer-Brandis, Niklas Weber

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

لغز الحشد متقلب الأشكال

تخيل أنك تحاول تعليم كمبيوتر أن يفهم العالم ليس كمجموعة من البكسلات أو قائمة من الكلمات، بل كشبكة من الروابط. هذا هو عالم الشبكات العصبية الرسومية (GNNs)، وهو فرع من فروع الذكاء الاصطناعي المصمم للتعامل مع البيانات التي تشبه خريطة للأصدقاء، أو الجزيئات، أو مسارات المرور. في هذه الخرائط، الشيء الأكثر أهمية ليس فقط ماهية العنصر الفردي، بل كيفية اتصاله بجيرانه.

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

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

سحر الملصقات العشوائية

سعى مؤلفو هذه الورقة، لوكاس غونون، وتيلو ماير-برانديس، ونيكلاس ويبر، لإثبات أن نوعاً معيناً من الذكاء الاصطناعي الرسومي، يسمى الشبكة العصبية المتكافئة تبادلياً (PENN)، يصبح قوياً للغاية عندما تمنحه ميزات عقد عشوائية. فكر في الـ (PENN) كفريق من المحققين يحاول حل لغز على خريطة. عادةً، إذا بدا مشتبه بهان متطابقان ولديهما نفس الأصدقاء، فلن يستطيع المحققون التمييز بينهما. ولكن إذا أعطيت كل مشتبه به ملصقاً عشوائياً فريداً (ميزة عشوائية)، فسيتمكن المحققون أخيراً من تمييزهما وحل القضية.

الاكتشاف الرئيسي للورقة هو ضمان "كوني". فقد أثبت المؤلفون رياضياً أنه إذا قمت بتغذية هذه الشبكات (PENNs) بملصقات عشوائية، فيمكنها تقريب أي دالة قابلة للقياس على رسم بياني ثابت الحجم بـ احتمالية عالية للغاية. وباللغة البسيطة: إذا كنت تريد من الذكاء الاصطناعي تعلم قاعدة معينة حول شبكة (مثل التنبؤ بما إذا كانت جزيئة معينة سامة أو ما إذا كانت شبكة مالية معرضة للخطر)، ومنحته ما يكفي من الملصقات العشوائية، فهناك بنية (PENN) يمكنها تعلم تلك القاعدة بشكل شبه مثالي. وهذا يظل صحيحاً حتى لو كانت القاعدة فوضوية أو معقدة، وحتى لو كانت البيانات تحتوي على أنواع مختلفة من الميزات المرتبطة بالعقد والحواف.

ما هو "الجيد بما يكفي"؟

لكن الورقة لا تكتفي بالقول "إنها تعمل فحسب"؛ بل تخبرك بمدى ضخامة حجم الذكاء الاصطناعي الذي تحتاجه لإنجاز المهمة. نظر المؤلفون في الدوال السلسة والمنضبطة (من الناحية الرياضية "قابلة للاشتقاق المستمر $k$ من المرات"، حيث $k \ge 2$ ). وقد اشتقوا صيغة لـ معدلات التقريب، وهي أساساً بمثابة حد للسرعة لكيفية تعلم الذكاء الاصطناعي مع زيادة حجمه.

وجدوا أن عمق الشبكة (عدد الطبقات) يحتاج فقط إلى النمو بشكل لوغاريتمي مع طلبك لمزيد من الدقة. وهذا خبر رائع: إذا كنت تريد أن تكون أكثر دقة بمرتين، فلا تحتاج إلى مضاعفة حجم الدماغ؛ بل تحتاج فقط إلى قدر ضئيل جداً من العمق الإضافي. ومع ذلك، فإن عدد الاتصالات (الأوزان غير الصفرية) ينمو بشكل متعدد الحدود مع طلبك لمزيد من الدقة. وتحديداً، تتناسب التعقيدات مع قوة $1/\epsilon$ ، حيث $\epsilon$ هو هامش الخطأ المطلوب. وتشير الورقة إلى أن هذه القوة تعتمد على "سلاسة" القاعدة التي تحاول تعلمها ( $k$ ) وحجم الرسم البياني ( $N$ ). وجوهر الأمر هو أنه بالنسبة للقواعد المعقدة والمتعرجة أو الرسوم البيانية الكبيرة جداً، ستحتاج إلى الكثير من الاتصالات، ولكن بالنسبة للقواعد السلسة، يظل الذكاء الاصطناعي فعالاً.

حيلة "المتوسط" من أجل السلامة

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

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

ماذا يعني هذا للمستقبل

يؤكد المؤلفون بحذر أن هذا إثبات نظري، وليس محاكاة لمجموعة بيانات محددة. لقد أثبتوا رياضياً أن الإمكانية موجودة لتكون هذه النماذج مقربات كونية. كما استبعدوا صراحةً فكرة أنك بحاجة إلى بنيات معقدة ومصممة خصيصاً لتحقيق ذلك؛ فبنية (PENN) القياسية، عند تعزيزها بميزات عشوائية، كافية لذلك.

كما أوضحوا أنه بينما تكسر الميزات العشوائية "التماثل المثالي" لجولة واحدة، إلا أنها لا تكسر "التماثل في التوقع" (المتوسط السلوكي). وهذا يشير إلى أنه من الناحية العملية، يعد استخدام الميزات العشوائية استراتيجية قوية. وتخلص الورقة إلى أن شبكات (PENNs) ذات الميزات العشوائية يجب اعتبارها معياراً قوياً لمهام تعلم الرسوم البيانية. فهي ليست مجرد فضول نظري؛ بل تقدم مخططاً ملموساً ومدعوماً رياضياً لبناء ذكاء اصطناعي رسومي قوي ومرن، قادر على تعلم الأنماط المعقدة في الشبكات التي تتراوح من الجزيئات الكيميائية إلى الأنظمة المالية.

ملخص تقني: الشمولية ومعدلات التقريب للشبكات العصبية الرسومية ذات الميزات العشوائية

بيان المشكلة

حققت الشبكات العصبية الرسومية (GNNs)، وخاصة بنيات تمرير الرسائل، نجاحاً تجريبياً كبيراً ولكنها تواجه قيوداً نظرية فيما يتعلق بقدرتها التعبيرية. فالشبكات العصبية الرسومية القياسية لتمرير الرسائل محدودة باختبار "وايسفايلر-ليمان" من الدرجة الأولى (1-WL)، مما يعني أنها لا تستطيع التمييز بين بعض الهياكل الرسومية غير المتماثلة. وبينما توجد استراتيجيات للتغلب على ذلك — مثل البنيات ذات الرتب العليا أو إثراء ميزات العقد — إلا أن هناك نقصاً في النتائج النظرية الصارمة التي تثبت قدرات التقريب الشامل لبنيات معينة من الشبكات العصبية الرسومية العملية عند تعزيزها بميزات عشوائية. علاوة على ذلك، فإن نتائج الشمولية الحالية غالباً ما تعتمد على فرضيات مقيدة، مثل اشتراط أن تكون الدوال المستهدفة مستمرة، أو أن تكون النطاقات متراصة (compact)، أو أن تكون الميزات ذات أبعاد منتهية، وغالباً ما تفشل في معالجة معدلات التقريب (حدود التعقيد) لهذه النماذج.

المنهجية

يتقصى المؤلفون الشبكات العصبية المتكافئة للتبديل (PENNs)، وهي فئة من الشبكات العصبية الرسومية تعمم العديد من بنيات تمرير الرسائل الشائعة (مثل GCN، وGIN، وGraphSAGE، وGAT). الابتكار المنهجي الجوهري هو تعزيز ميزات العقد القياسية بـ ميزات عقد عشوائية.

تعريف البنية: يعرّف الورقة البحثية الـ PENNs بأنها دوال تتكون من مكونات شبكة عصبية أمامية (FNN) ( $\rho, \phi, \alpha, \psi$ ) تقوم بتجميع المعلومات من الجوار ومن سمات الرسم البياني العالمية. هذه البنية تشمل إطار العمل "التجميع-الدمج-القراءة" (ACR).
الميزات العشوائية: يقدم المؤلفون ميزات عقد عشوائية $R$ توفر "ميزات عقد فريدة محدودة". وهذا يعني أنه باحتمالية عالية (أو بشكل شبه مؤكد)، تمنح الميزات العشوائية معرفات متميزة للعقد المتميزة، مما يكسر التماثل الذي يحد من الشبكات العصبية الرسومية القياسية. كما يستوعب الإطار كلاً من الميزات العشوائية المستقلة والمتماثلة توزيعياً (i.i.d.) والمعرفات الفريدة الحتمية (أو تبديلاتها العشوائية).
إطار التقريب: تستفيد الدراسة من نظريات التقريب الشامل الكلاسيكية للشبكات العصبية الأمامية (مثل Leshno et al., 1993) ولكنها تكيفها مع نطاق الرسوم البيانية. الرؤية الأساسية هي أنه إذا كانت ميزات العقد فريدة، فيمكن تمثيل أي دالة متكافئة للتبديل كمجموعة من الشبكات العصبية الأمامية التي تعمل على هذه الميزات الفريدة.
التكافؤ القائم على التوقع: إدراكاً منها أن التكافؤ للتبديل عبر المسار (pathwise permutation equivariance) ينكسر بسبب الميزات العشوائية الثابتة، يحلل المؤلفون التكافؤ للتبديل في التوقع. ويقترحون حساب متوسط الـ PENNs عبر عدة عينات من الميزات العشوائية المعاد أخذ عيناتها لاستعادة خصائص التكافؤ مع الاحتفاظ بقدرة تعبيرية عالية.

المساهمات الرئيسية

1. نظريات التقريب الشامل

تثبت الورقة أن الـ PENNs المعززة بالميزات العشوائية هي مقربات شاملة للدوال القابلة للقياس والمتكافئة للتبديل والمتغيرة للتبديل على الرسوم البيانية الموجهة ذات الحجم الثابت والميزات متعددة الأبعاد للعقد والحواف.

العمومية: على عكس العمل السابق (مثل Abboud et al., 2020; Puny et al., 2020)، لا تتطلب هذه النتيجة أن تكون الدالة المستهدفة مستمرة، ولا تفترض تراص النطاق أو نهائية فضاء الميزات. وهي تنطبق على الدوال القابلة للقياس في النطاقات غير المحدودة.
بنية ملموسة: يحدد المؤلفون بنية ملموسة (PENNs) تتحقق فيها الشمولية، بدلاً من مجرد التأكيد على وجود بنية مجردة ما.
الاحتمالية: يتحقق التقريب باحتمالية عالية جداً، بشرط أن تولد الميزات العشوائية معرفات عقد فريدة.

2. معدلات التقريب وحدود التعقيد

بالنسبة للدوال القابلة للاشتقاق المستمر $k$ من $k$ مرة ( $k \ge 2$ ) المعرفة على النطاقات المتراصة، تشتق الورقة حدوداً عليا صريحة لتعقيد مكونات الـ PENN المطلوبة لتحقيق خطأ تقريب مرغوب $\varepsilon$ .

العمق: ينمو عدد الطبقات المطلوبة لوغاريتمياً بالنسبة لـ $1/\varepsilon$ ( $O(\log(1/\varepsilon))$ ).
العرض/الأوزان: ينمو عدد الأوزان غير الصفرية حدودياً بالنسبة لـ $1/\varepsilon$ ، وتحديداً كـ $O(\varepsilon^{-c/(k-1)})$ ، حيث يعتمد $c$ على أبعاد الرسم البياني ( $N, d, d'$ ).
لعنة الأبعاد: تعكس الحدود شكلاً من أشكال "لعنة الأبعاد" فيما يتعلق بنطاق الرسم البياني، ولكن شدتها يتم تخفيفها بالنسبة للدوال ذات الانتظام الأعلى ( $k$ ).

3. التكافؤ للتبديل في التوقع

تعالج الورقة المقايضة بين القدرة التعبيرية والتماثل. وبينما لا تكون نسخة واحدة من PENN مع ميزات عشوائية متكافئة للتبديل عبر المسار، يثبت المؤلفون أن توقع مخرجات الـ PENN (بشرط مدخلات الرسم البياني) هو دالة متكافئة للتبديل. علاوة على ذلك، يظهرون أن حساب المتوسط عبر عدد محدود من عينات الميزات العشوائية المستقلة والمتماثلة توزيعياً يحافظ على خاصية التقريب الشامل مع تحسين الانحياز نحو التكافؤ.

النتائج

النظرية 9: تثبت أنه لأي دالة $f$ متكافئة للتبديل وقابلة للقياس ولأي $\varepsilon, \delta > 0$ ، يوجد PENN مع ميزات عشوائية بحيث يكون احتمال تجاوز خطأ التقريب لـ $\varepsilon$ هو $\delta$ على الأكثر.
النظرية 11: تقدم نسخة نظرية القياس لنتيجة الشمولية، وهي قابلة للتطبيق عندما يؤدي توزيع الرسم البياني نفسه إلى ميزات عقد فريدة.
النظرية 16: توضح أن الـ PENN المتوسط (باستخدام $M$ من النسخ المستقلة والمتماثلة توزيعياً من الميزات العشوائية) يحقق أيضاً خاصية التقريب الشامل، مع كون احتمال الخطأ محدوداً بـ $\delta$ .
النظرية 18: تقدم معدلات التقريب الكمية. فهي تثبت أنه بالنسبة للدوال المنتظمة بما يكفي، يمكن لـ PENNs ذات قيود بنيوية محددة (العمق والعرض) تقريب الدالة المستهدفة بشكل موحد باحتمالية عالية. تعكس حدود التعقيد تلك المعروفة للشبكات العصبية الأمامية القياسية.

الأهمية والادعاءات

يدعي المؤلفون أن هذا العمل يسد فجوات جوهرية في الفهم النظري للشبكات العصبية الرسومية (GNNs):

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

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