الشبكات العصبية للرسم البياني

الشبكات العصبية للرسم البياني أو الشبكة العصبية الشبكية (بالانجليزية: Graph Neural Network) هي نوع من أنواع الشبكات العصبية الاصطناعية المستخدمة في معالجة البيانات التي يمكن تمثيلها من خلال الرسوم البيانية.

الرسوم البيانية تتكون بالعادة من عدد محدود من العقد أو النقاط الموصول بينها بخطوط أو أسهم.

اللبنات الأساسية للشبكة العصبية لـلرسوم البيانية. $(1)$ طبقة التبديل المتكافئ (المزدوج). $(2)$ طبقة التجميع المحلية. $(3)$ طبقة التجميع (أو القراءة) الشاملة. تشير الألوان إلى الميزات .

بشكل عام في التعلم العميق الهندسي (بالانجليزية: Geometry Deep Learning) يمكننا تكييف بنية أي نوع من البيانات على شكل رسوم بيانية فعلى سبيل المثال يمكننا اعتبار الشبكات العصبية الالتفافية (بالانجليزية: Convolutional Neural Network) على أنها عبارة عن رسوم بيانية بحيث تتمثل من خلالها كل نقطة (بكسل) في الصورة على شكل عقدة في الرسوم البيانية. أو كمثال آخر يمكننا تمثيل الكلمات في الجمل على شكل عقد للرسم البياني.

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

تشمل تطبيقات الشبكات العصبية للرسوم البيانية: الشبكات الاجتماعية، والشبكات المتعلقة بالتضمين والاقتباس، والبيولوجيا الجزيئية، والكيمياء، والفيزياء ومشاكل التحسين الاندماجي الصعب NP.

هناك العديد من المكتبات المفتوحة التي تقوم بإنشاء أو التعامل مع الشبكات العصبية للرسوم البيانية مثل باي تورش وتنسرفلو وجارب.

معمارية البناء

يتم تنفيذ هذه الطبقات الأساسية عند بناء الشبكات العصبية للرسوم البيانية:

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

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

الرسوم البيانية غير المتماثلة التي لا يمكن تمييزها بواسطة الشبكات العصبية للرسوم البيانية. تشير الألوان إلى ميزات العقدة.

طبقات تمرير الرسالة

تحديث تمثيل العقدة في طبقة الشبكة العصبية لتمرير الرسائل. العقدة $\mathbf {x} _{0}$ تتلقى الرسائل المرسلة من جميع جيرانها المباشرين $\mathbf {x} _{1}$ إلى $\mathbf {x} _{4}$ . الرسائل تحسب عبر وظيفة الرسائل $\phi$، والتي تمثل ميزات كل من المرسل والمستقبل.

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

لنفترض أن الرسم البياني $G=(V,E)$، حيث $V$ هي مجموعة العقد و $E$ هي مجموعة الحواف أو الروابط بين العقد. يمثل $N_{u}$ العقد المجاورة لعقدة $u\in V$ . بالإضافة إلى ذلك، تعبر $\mathbf {x} _{u}$ عن مجموعة الخصائص للعقدة $u\in V$، و $\mathbf {e} _{uv}$ تمثل خصائص الروابط بين $(u,v)\in E$ . فيمكن التعبير عن طبقة تبادل الرسائل من خلال:

$\mathbf {h} _{u}=\phi \left(\mathbf {x_{u}} ,\bigoplus _{v\in N_{u}}\psi (\mathbf {x} _{u},\mathbf {x} _{v},\mathbf {e} _{uv})\right)$

حيث $\phi$ و $\psi$ عبارة عن دالتين قابلتين للاشتقاق (على سبيل المثال، الشبكات العصبية الاصطناعية)، و $\bigoplus$ هو عامل تجميع ثابت للتبديل يمكنه قبول عدد كبير ومختلف من المدخلات (على سبيل المثال، مجموع العناصر، أو الوسط الحسابي، أو الحد الأقصى). وعلى سبيل الخصوص، $\phi$ و $\psi$ تشيران على التوالي إلى وظيفتي التحديث والتراسل. ولذلك، في المجموعة الحسابية لـطبقة تبادل الرسائل، تقوم عُقد الرسم البياني بتحديث تمثيلاتها من خلال تجميع الرسائل المستلمة من جيرانها.

مخرجات طبقة أو عدة طبقات من تبادل الرسائل$\mathbf {h} _{u}$ هي تمثيلات لكل عقدة $u\in V$ في الرسم البياني. يمكن استخدام تمثيلات العقدة في أي مهمة نهائية، مثل تصنيف العقدة / الرسم البياني أو التنبؤ بالحافة. والتي يمكن استخدامها في تصنيف العقد أو تصنيف الرسم البياني أو التنبؤ بالروابط بين هذه العقد. تجميع هذه التمثيلات من العقد المباشرين على هذا النحو سيكدس مجموعة من طبقات تبادل الرسائل عند كل عقدة بحيث يجعلها قادرة على التواصل مع عقد أبعد. من حيث المبدأ، للتأكد من أن كل عقدة تتلقى معلومات من كل العقد الأخرى، ستحتاج كل عقدة إلى تكديس عدد من طبقات تبادل الرسائل مساوية لقيمة عدد العقد الموجودة في طريق الوصول لأبعد نقطة عن تلك العقدة باستخدام أقصر طريق في الرسم البياني (قطر الرسم البياني). ومع ذلك، فإن تكديس العديد من طبقات تبادل الرسائل قد يتسبب في حدوث مشكلات مثل التسوية الزائدة والإفراط في السحق. تشير التسوية المفرطة إلى مشكلة عدم إمكانية تمييز تمثيلات العقدة. ويشير الإفراط في السحق إلى عنق الزجاجة الذي تم إنشاؤه عن طريق الضغط على التبعيات بعيدة المدى في تمثيلات ذات حجم ثابت. يمكن للإجراءات المضادة مثل تخطي الاتصالات (كما هو الحال في الشبكات العصبية المتبقية)، وقواعد التحديث المحدود والقفز المعرفي أن يخفف من التسوية الزائدة. ويمكن أن يؤدي تعديل الطبقة النهائية لتكون طبقة متجاورة تمامًا، أي من خلال اعتبار الرسم البياني كرسم بياني كامل، على التخفيف من الانهيار المفرط في المشكلات التي تتطلب تبعيات بعيدة المدى.

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

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

تم تقديم الشبكة الالتفافية للرسم البياني (GCN) لأول مرة بواسطة توماس كيبف وماكس ويلنج في عام 2017.

وتمثل هذه الطبقة صورة طيفية أولية عن الرسم البياني.

يعبر عن الشبكة الالتفافية للرسم البياني من خلال:

$\mathbf {H} =\sigma \left({\tilde {\mathbf {D} }}^{-{\frac {1}{2}}}{\tilde {\mathbf {A} }}{\tilde {\mathbf {D} }}^{-{\frac {1}{2}}}\mathbf {X} \mathbf {\Theta } \right)$

$\mathbf {H}$: مصفوفة تمثيلات العقد $\mathbf {h} _{u}$.

$\mathbf {X}$: مصفوفة ميزات العقدة $\mathbf {x} _{u}$.

$\sigma (\cdot )$: علاقة تنشيط مثل (ReLU).

${\tilde {\mathbf {A} }}$ و${\tilde {\mathbf {D} }}$: تشيران على التوالي لمصفوفتي تجاور الرسم البياني ودرجة الرسم البياني (بوجود الحلقات الذاتية في كلا المصفوفتين).

$\mathbf {\Theta }$: مصفوفة العوامل القابلة للتدريب.

يمكن تحديد ${\tilde {\mathbf {A} }}=\mathbf {A} +\mathbf {I}$ و ${\tilde {\mathbf {D} }}_{ii}=\sum _{j\in V}{\tilde {A}}_{ij}$.

تشير $\mathbf {I}$ إلى مصفوفة الوحدة. يضمن وجود هذه المعايرة أن تكون قيم ${\tilde {\mathbf {D} }}^{-{\frac {1}{2}}}{\tilde {\mathbf {A} }}{\tilde {\mathbf {D} }}^{-{\frac {1}{2}}}$ محددة ضمن $[0,1]$ لتجنب عدم الاستقرار العددي.

يتمثل أحد قيود هذه الشبكات في عدم سماحها بتعيين ميزات حافة متعددة الأبعاد $\mathbf {e} _{uv}$. ومع ذلك، من الممكن ربط الأوزان العددية $w_{uv}$ بأي حافة $A_{uv}=w_{uv}$ عن طريق تعيين قيم غير صفرية في المصفوفة المجاورة مساوية لوزن الحافة المقابلة.

شبكة التركيز للرسوم البيانية

تم تقديم شبكة الانتباه بالرسم البياني بواسطة بيتر فيليكوفيك وآخرين في عام 2018.

شبكة التركيز للرسم البياني عبارة عن مزيج من الشبكات العصبية للرسم البياني وطبقة التركيز. يساعد وجود هذه الطبقة في الشبكات العصبية الرسومية على التركيز على المعلومات المهمة في البيانات بدلاً من التركيز على البيانات بأكملها.

يمكن التعبير عن شبكة التركيز للرسوم البيانية متعددة الرؤوس على النحو التالي:

$\mathbf {h} _{u}={\overset {K}{\underset {k=1}{\Big \Vert }}}\sigma \left(\sum _{v\in N_{u}}\alpha _{uv}\mathbf {W} ^{k}\mathbf {x} _{v}\right)$

$K$: عدد رؤوس التركيز.

${\Big \Vert }$: تسلسل المتجه.

$\alpha _{ij}$: هي معاملات التركيز.

$\sigma (\cdot )$: علاقة تنشيط مثل (ReLU).

$W^{k}$: مصفوفة عوامل رؤوس التركيز القابلة للتدريب بالنسبة للطبقة النهائية من طبقات التركيز، يتم حساب متوسط المخرجات من كل رأس تركيز قبل تطبيق وظيفة التنشيط. رسميًا، يمكن كتابة هذه الطبقة النهائية على النحو التالي:

$\mathbf {h} _{u}=\sigma \left({\frac {1}{K}}\sum _{k=1}^{K}\sum _{v\in N_{u}}\alpha _{uv}\mathbf {W} ^{k}\mathbf {x} _{v}\right)$

التركيز في التعلم الآلي هو أسلوب محاكاة للانتباه المعرفي. في سياق التعلم على الرسوم البيانية، معامل الانتباه $\alpha _{uv}$ يقيس مدى أهمية العقدة $u\in V$ بالنسبة إلى عقدة أخرى $v\in V$ .

تُتُحسب معاملات التركيز المعيارية على النحو التالي:

$\alpha _{uv}={\frac {\exp({\text{LeakyReLU}}\left(\mathbf {a} ^{T}[\mathbf {W} \mathbf {h} _{u}\Vert \mathbf {W} \mathbf {h} _{v}\Vert \mathbf {e} _{uv}]\right))}{\sum _{z\in N_{u}}\exp({\text{LeakyReLU}}\left(\mathbf {a} ^{T}[\mathbf {W} \mathbf {h} _{u}\Vert \mathbf {W} \mathbf {h} _{z}\Vert \mathbf {e} _{uz}]\right))}}$

$\mathbf {a}$: هو متجه الأوزان القابلة للتعلم.

$\cdot ^{T}$: يشير إلى التبديل.

${\text{LeakyReLU}}$: هي ReLU معدل.

يتم معايرة معاملات التركيز لجعلها قابلة للمقارنة بسهولة عبر العقد المختلفة.

يمكن رؤية الشبكات الالتفافية للرسوم البيانية كحالة خاصة لـشبكة التركيز حيث معاملات الانتباه غير قابلة للتعلم، ولكنها ثابتة وتساوي أوزان الحافة $w_{uv}$ .

الشبكة العصبية للرسوم البيانية المتسلسلة ذات البوابات

تتم تقديم الشبكة العصبية لتسلسل الرسم البياني بواسطة يوجيا لي وآخرين. في عام 2015. تم توسيع وتعديل صياغة هذه الشبكة بواسطة سكارسيلي وآخرين لإخراج التسلسلات. يتم تنفيذ إطار عمل تمرير الرسائل كقاعدة تحديث لخلية وحدة متكررة ذات بوابة.

يمكن التعبير عن هذه الشبكة من خلال:

$\mathbf {h} _{u}^{(0)}=\mathbf {x} _{u}\,\Vert \,\mathbf {0}$

$\mathbf {m} _{u}^{(l+1)}=\sum _{v\in N_{u}}\mathbf {\Theta } \mathbf {h} _{v}$

$\mathbf {h} _{u}^{(l+1)}={\text{GRU}}(\mathbf {m} _{u}^{(l+1)},\mathbf {h} _{u}^{(l)})$

أين $\Vert$ يشير إلى تسلسل المتجه.

$\mathbf {0}$:: متجه صفري.

$\mathbf {\Theta }$:: هي مصفوفة من العوامل القابلة للتعلم.

${\text{GRU}}$: عبارة عن خلية وحدة متكررة ذات بوابة (بالإنجليزية: Gated recurrent unit).

$l$: فهرس التسلسل.

طبقات التجميع المحلية

تعمل طبقات التجميع المحلية على زيادة اختزال الرسم البياني. تم تقديم واقتراح العديد من استراتيجيات التجميع المحلية القابلة للتعلم. لكل حالة، المدخل هو الرسم البياني الأولي الذي يتم تمثيله بواسطة مصفوفة $\mathbf {X}$ التي تحمل ميزات العقدة ومصفوفة $\mathbf {A}$ التي تمثل المصفوفة المجاورة للرسم البياني. والناتج هو المصفوفة الجديدة $\mathbf {X} '$ من ميزات العقدة ومصفوفة مجاورة للرسم البياني الجديد $\mathbf {A} '$ .

تجميع أعلى قيم لإسقاط العقد

أولا نجعل

$\mathbf {y} ={\frac {\mathbf {X} \mathbf {p} }{\Vert \mathbf {p} \Vert }}$

بحيث $\mathbf {p}$ متجه الاسقاط القابل للتعلم. ويتم حساب قيمة هذا الاسقاط (ليس كمتجه).

يمكن بعد ذلك التعبير عن هذه الطبقة على النحو التالي:

$\mathbf {X} '=(\mathbf {X} \odot {\text{sigmoid}}(\mathbf {y} ))_{\mathbf {i} }$

$\mathbf {A} '=\mathbf {A} _{\mathbf {i} ,\mathbf {i} }$

$\mathbf {i} ={\text{top}}_{k}(\mathbf {y} )$ وهي المجموعة الفرعية من العقد ذات أعلى قيم إسقاط، وتشير $\odot$ إلى ضرب المصفوفة حسب العنصر، و ${\text{sigmoid}}(\cdot )$ هي وظيفة السيني التي تجعل متجه الإسقاط قابلا للتدريب عن طريق الانتشار المتراجع والتي تنتج مخرجات منفصلة. يتم الاحتفاظ بالعقد ذات أعلى درجات إسقاط في مصفوفة التجاور الجديدة $\mathbf {A} '$.

تجميع التركيز الذاتي

بداية نجعل

$\mathbf {y} ={\text{GNN}}(\mathbf {X} ,\mathbf {A} )$

حيث ${\text{GNN}}$ هي الطبقة المكافئة لأي من طبقات التبديل السابقة.

هذه الطبقة يمكن التعبير عنها من خلال:

$\mathbf {X} '=(\mathbf {X} \odot \mathbf {y} )_{\mathbf {i} }$

$\mathbf {A} '=\mathbf {A} _{\mathbf {i} ,\mathbf {i} }$

حيث $\mathbf {i} ={\text{top}}_{k}(\mathbf {y} )$ كما أشرنا لها سابقا، و$\odot$ هي ضرب المصفوفة حسب العنصر.

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

التطبيقات

طيّ البروتين

الشبكات العصبية للرسم البياني هي إحدى اللبنات الأساسية لبرنامج ألفا-فولد، وهو برنامج ذكاء اصطناعي طورته شركة جوجل: ديب-مايند لحل مشكلة طي البروتين في علم الأحياء. حقق هذا البرنامج المركز الأول في العديد من المسابقات.

الشبكات الاجتماعية

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

الاستمثال التوافقي

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

رابط خارجي

https://distill.pub/2021/gnn-intro/