بولينورمر: تحويلة رسمية تعبيرية متعددة الحدود في الزمن الخطي

أصبحت نماذج المحولات الرسومية (Graph Transformers (GTs)) معملاً واعداً يتفوق نظريًا على الشبكات العصبية الرسومية التي تعتمد على تمرير الرسائل (GNNs). ومع ذلك، فإن النماذج النموذجية لـ GTs تمتلك على الأقل تعقيدًا تربيعيًا، وبالتالي لا يمكنها التوسع إلى الرسوم البيانية الكبيرة. وعلى الرغم من وجود عدة نماذج خطية لـ GTs تم اقتراحها مؤخرًا، إلا أنها لا تزال تتخلف عن نماذج GNN في عدة مجموعات بيانات رسمية شهيرة، مما يثير قلقًا جوهريًا بشأن التعبير العملي لها. ولتحقيق توازن بين التعبيرية والقابلية للتوسع في نماذج GTs، نقترح "بولينورمر" (Polynormer)، وهي نموذج GT يمتلك تعبيرًا متعدد الحدود وتعقيدًا خطيًا. يُبنى بولينورمر على نموذج أساسي جديد يتعلم متعدد حدود من الدرجة العالية على الميزات المدخلة. ولتمكين هذا النموذج الأساسي من التماثل التبادلي (permutation equivariant)، ندمجه بشكل منفصل مع البنية التحتية للرسم البياني والميزات العقدية، مما يؤدي إلى نماذج انتباه متماثلة محليًا وعالميًا. وبذلك، يعتمد بولينورمر على نموذج انتباه خطي من المستوى المحلي إلى العالمي لتعلم متعددات حدود متماثلة من الدرجة العالية، حيث تُحدَّد معاملاتها بواسطة نقاط الانتباه. وقد تم تقييم بولينورمر على 13 مجموعة بيانات، تشمل رسومًا بيانية متماثلة (homophilic) وغير متماثلة (heterophilic)، بما في ذلك رسوم بيانية ضخمة تحتوي على ملايين العقد. وتشير نتائج التجارب الواسعة إلى أن بولينورمر يتفوق على أفضل النماذج الحالية من نماذج GNN وGT في معظم المجموعات، حتى دون استخدام دوال تنشيط غير خطية.