2025-11-18T15:58:13.889736

A Survey of Graph Unlearning

Said, Tran, Zhao et al.
Graph unlearning emerges as a crucial advancement in the pursuit of responsible AI, providing the means to remove sensitive data traces from trained models, thereby upholding the \textit{right to be forgotten}. It is evident that graph machine learning exhibits sensitivity to data privacy and adversarial attacks, necessitating the application of graph unlearning techniques to address these concerns effectively. In this comprehensive survey paper, we present the first systematic review of graph unlearning approaches, encompassing a diverse array of methodologies and offering a detailed taxonomy and up-to-date literature overview to facilitate the understanding of researchers new to this field. To ensure clarity, we provide lucid explanations of the fundamental concepts and evaluation measures used in graph unlearning, catering to a broader audience with varying levels of expertise. Delving into potential applications, we explore the versatility of graph unlearning across various domains, including but not limited to social networks, adversarial settings, recommender systems, and resource-constrained environments like the Internet of Things, illustrating its potential impact in safeguarding data privacy and enhancing AI systems' robustness. Finally, we shed light on promising research directions, encouraging further progress and innovation within the domain of graph unlearning. By laying a solid foundation and fostering continued progress, this survey seeks to inspire researchers to further advance the field of graph unlearning, thereby instilling confidence in the ethical growth of AI systems and reinforcing the responsible application of machine learning techniques in various domains.
academic

مسح شامل لإلغاء التعلم في الرسوم البيانية

المعلومات الأساسية

  • معرّف الورقة: 2310.02164
  • العنوان: A Survey of Graph Unlearning (مسح شامل لإلغاء التعلم في الرسوم البيانية)
  • المؤلفون: Anwar Said, Ngoc N. Tran, Yuying Zhao, Tyler Derr, Mudassir Shabbir, Waseem Abbas, Xenofon Koutsoukos
  • التصنيف: cs.LG (التعلم الآلي)
  • تاريخ النشر: arXiv أكتوبر 2023 (أحدث إصدار 14 أكتوبر 2025)
  • رابط الورقة: https://arxiv.org/abs/2310.02164

الملخص

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

خلفية البحث والدافع

خلفية المشكلة

  1. متطلبات حماية الخصوصية: مع تطبيق لوائح حماية البيانات (مثل GDPR و CCPA)، يحق للأفراد طلب حذف بياناتهم من نماذج التعلم الآلي
  2. تعقيد بيانات الرسوم البيانية: الترابط بين العقد والحواف في بيانات الرسوم البيانية يجعل الحذف البسيط للبيانات صعباً، لأن المعلومات تنتشر عبر آليات نقل الرسائل إلى العقد البعيدة
  3. الحماية من الهجمات الخصومة: الحاجة إلى إزالة البيانات المحقونة بشكل خبيث من النموذج للحفاظ على سلامة النظام
  4. عدم كفاية الطرق الموجودة: لا يمكن تطبيق طرق إلغاء التعلم التقليدية مباشرة على بيانات الرسوم البيانية

أهمية البحث

  • الامتثال القانوني: تلبية متطلبات لوائح حماية البيانات
  • حماية الخصوصية: حماية المعلومات الشخصية الحساسة من الكشف عنها بواسطة النموذج
  • الحماية الأمنية: مقاومة هجمات تسميم البيانات والهجمات الخصومة الأخرى
  • الذكاء الاصطناعي الأخلاقي: تعزيز تطوير أنظمة ذكاء اصطناعي مسؤولة

القيود الموجودة

  • غياب مسح منهجي شامل لطرق إلغاء التعلم على الرسوم البيانية
  • الطبيعة المترابطة لبيانات الرسوم البيانية تجعل إلغاء التعلم الكامل معقداً
  • صعوبة المقارنة بين الكفاءة والاكتمال
  • غياب معايير تقييم موحدة

المساهمات الأساسية

  1. أول مسح منهجي شامل: توفير أول مراجعة منهجية شاملة لمجال إلغاء التعلم على الرسوم البيانية
  2. تصنيف تفصيلي: تقسيم طرق إلغاء التعلم على الرسوم البيانية إلى فئتين رئيسيتين: إلغاء التعلم الدقيق (Exact Unlearning) وإلغاء التعلم التقريبي (Approximate Unlearning)
  3. تحليل تطبيقات شامل: استكشاف تطبيقات إلغاء التعلم على الرسوم البيانية في عدة مجالات مثل الشبكات الاجتماعية وأنظمة التوصيات والشبكات الطبية
  4. إطار عمل التقييم: توفير طرق لتقييم اكتمال الإلغاء والكفاءة وفائدة النموذج
  5. الاتجاهات المستقبلية: تحديد عدة اتجاهات بحثية واعدة

شرح الطرق

تعريف المهمة

المفاهيم الأساسية

  • تعريف الرسم البياني: G = (V, E, X, Xe)، حيث V مجموعة العقد، E مجموعة الحواف، X مصفوفة ميزات العقد، Xe مصفوفة ميزات الحواف
  • مجموعة الإلغاء: S ⊆ D، تمثل مجموعة فرعية من البيانات التي يجب إلغاؤها
  • الهدف: تحديث معاملات النموذج θ بحيث تكون النتائج مكافئة لإعادة التدريب على D\S

تعريف (ε, δ)-الإلغاء

بالنسبة لمجموعة بيانات ثابتة D ومجموعة إلغاء S وخوارزمية تعلم عشوائية A، تكون خوارزمية الإلغاء U هي (ε, δ)-إلغاء إذا وفقط إذا كان لجميع R ⊆ R:

Pr[A(D \ S) ∈ R] ≤ e^ε Pr[U(A(D), S, D) ∈ R] + δ
Pr[U(A(D), S, D) ∈ R] ≤ e^ε Pr[A(D \ S) ∈ R] + δ

تصنيف أنواع إلغاء التعلم على الرسوم البيانية

1. إلغاء التعلم الاستقرائي (Transductive)

  • إلغاء العقد: إزالة عقدة محددة وجميع اتصالاتها
  • إلغاء الحافة: إزالة حافة محددة مع الحفاظ على العقد
  • إلغاء ميزات العقدة: إزالة ميزات محددة للعقدة

2. إلغاء التعلم الاستنتاجي (Inductive)

  • إلغاء العقد الاستنتاجي: إزالة مجموعة عقد من رسوم بيانية متعددة
  • إلغاء الحافة الاستنتاجي: إزالة مجموعة حواف من رسوم بيانية متعددة
  • إلغاء التعلم على مستوى الرسم البياني: إزالة مثيل رسم بياني كامل

الإطار التقني

طرق إلغاء التعلم الدقيق

  1. إطار عمل SISA: تقسيم بيانات التدريب إلى شرائح، مما يتطلب فقط إعادة تدريب الشرائح المتأثرة
  2. إعادة تدريب المعاملات: تخزين المعاملات التاريخية، وإعادة التدريب من النقطة التي ظهرت فيها البيانات المحذوفة للمرة الأولى
  3. الحلول الشكلية: مثل GraphEditor، التي تحول تدريب GNN إلى مشكلة قابلة للحل التحليلي

طرق إلغاء التعلم التقريبي

  1. الطرق في الإعدادات المحدبة:
    • الاستفادة من مصفوفة Hessian لتحديث المعاملات
    • تقدير دالة التأثير لتقدير تأثير البيانات
    • توفير ضمانات نظرية
  2. الطرق في الإعدادات غير المحدبة:
    • إلغاء الحافة القائم على دالة التأثير (CEU)
    • عمليات الحذف الهرمية (GNNDelete)
    • طرق تقطير المعرفة (GUKD, D2DGN)

الإعداد التجريبي

أبعاد التقييم

1. اكتمال الإلغاء

  • هجمات الاستدلال على العضوية: تقييم ما إذا كانت البيانات المحذوفة لا تزال قابلة للكشف
  • الفروقات في التنبؤ: مقارنة الفروقات بين مخرجات النموذج المحذوف والنموذج المعاد تدريبه
  • الفروقات في المعاملات: مقارنة المسافة الإقليدية لمعاملات النموذج

2. كفاءة الإلغاء

  • التعقيد الزمني: معظم الطرق لها تعقيد خطي بالنسبة لعدد الطبقات وتربيعي بالنسبة لبعد الميزات
  • وقت التنفيذ التجريبي: الوقت الفعلي المطلوب لعملية الإلغاء

3. فائدة النموذج

  • أداء المهام اللاحقة: درجات F1 والدقة و AUROC وغيرها
  • المقارنة مع المعايير: عادة ما تتم المقارنة مع أداء إعادة التدريب من الصفر

مجموعات البيانات

تم تقييم الطرق المذكورة في الورقة على عدة مجموعات بيانات رسوم بيانية:

  • بيانات الشبكات الاجتماعية
  • شبكات الاستشهادات
  • بيانات الجزيئات
  • بيانات أنظمة التوصيات

نتائج التجارب

النتائج الرئيسية

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

  • الطرق الدقيقة: توفر ضمانات إلغاء مثالية لكن بتكلفة حسابية كبيرة
  • الطرق التقريبية: تحقق توازناً بين الكفاءة وجودة الإلغاء

المقارنات الأداء

  • يوجد مقايضة أساسية بين اكتمال الإلغاء والكفاءة الحسابية
  • الطبيعة المترابطة للرسم البياني تجعل الإلغاء المحلي يؤثر على الأداء العالمية
  • أنواع الإلغاء المختلفة (عقدة/حافة/ميزة) لها درجات تعقيد مختلفة

مقارنة الطرق

وفقاً للملخص في الجدول الثاني:

  • طرق نوع SISA تظهر أداءً ممتازاً من حيث الدقة
  • طرق دالة التأثير أكثر كفاءة في إلغاء التعلم التقريبي
  • طرق تقطير المعرفة لها مزايا في الحفاظ على فائدة النموذج

فعالية التطبيقات

  • أنظمة التوصيات: طرق مثل RecEraser تتعامل بفعالية مع إلغاء تفاعلات المستخدم والعنصر
  • الشبكات الاجتماعية: GraphEraser تحقق إلغاءً فعالاً من خلال تقسيم الرسم البياني
  • الحماية من الهجمات: طرق الإلغاء تزيل بفعالية البيانات المحقونة بشكل خبيث

الأعمال ذات الصلة

إلغاء التعلم التقليدي

  • التركيز الرئيسي على البيانات المستقلة والموزعة بشكل متطابق
  • لا يمكن تطبيقها مباشرة على بيانات الرسوم البيانية
  • تفتقر إلى الاعتبار للتبعيات بين البيانات

التعلم الآلي على الرسوم البيانية

  • مهام تصنيف العقد والتنبؤ بالروابط وتصنيف الرسوم البيانية
  • آليات نقل الرسائل تجعل انتشار المعلومات معقداً
  • تتطلب تقنيات إلغاء متخصصة

حماية الخصوصية

  • تطبيق الخصوصية التفاضلية على بيانات الرسوم البيانية
  • دمج التعلم الفيدرالي مع الشبكات العصبية للرسوم البيانية
  • هجمات الاستدلال على العضوية والحماية منها

الخلاصة والنقاش

الاستنتاجات الرئيسية

  1. إلغاء التعلم على الرسوم البيانية هو تقنية حاسمة للذكاء الاصطناعي المسؤول
  2. لكل من الطرق الدقيقة والتقريبية مزايا، ويجب اختيار الطريقة المناسبة بناءً على احتياجات التطبيق
  3. لا تزال معايير التقييم بحاجة إلى مزيد من التحسين والتوحيد
  4. التطبيقات عبر المجالات المختلفة تظهر إمكانات ضخمة

القيود

  1. الجدل حول معايير التقييم: توجد مشاكل موثوقية في طرق التقييم الحالية
  2. تحديات الإعدادات غير المحدبة: معظم نماذج GNN العملية غير محدبة، مما يجعل الضمانات النظرية صعبة
  3. قيود قابلية التوسع: لا تزال كفاءة الإلغاء على الرسوم البيانية الكبيرة بحاجة إلى تحسين
  4. دعم الهياكل المعقدة: الدعم غير كافٍ للرسوم البيانية الموجهة والرسوم البيانية الزمنية وغيرها من الهياكل المعقدة

الاتجاهات المستقبلية

1. التطور التقني

  • إلغاء التعلم التقريبي في الإعدادات غير المحدبة: تطوير طرق إلغاء تنطبق على نماذج GNN المعقدة
  • إطار عمل موحد لإلغاء التعلم على الرسوم البيانية: طرق موحدة تدعم أنواع إلغاء متعددة
  • دعم هياكل الرسوم البيانية المعقدة: التوسع إلى الرسوم البيانية الموجهة والرسوم البيانية الزمنية والرسوم البيانية المعرفية

2. توسيع التطبيقات

  • إلغاء التعلم في النماذج الأساسية: التكيف مع احتياجات إلغاء التعلم لنماذج الرسوم البيانية الأساسية الكبيرة
  • التفاعلات متعددة المستخدمين: معالجة القضايا الأخلاقية لإلغاء بيانات التفاعل بين المستخدمين
  • بيئات الحوسبة الطرفية: إلغاء فعال في البيئات ذات الموارد المحدودة

3. تحسين النظرية

  • طرق الإزالة المعتمدة: توفير ضمانات نظرية أقوى
  • توحيد معايير التقييم: إنشاء إطار عمل موثوق لتقييم الإلغاء
  • تحديد كمي للخصوصية: طرق أكثر دقة لتحديد كمي تسرب الخصوصية

التقييم المتعمق

المزايا

  1. عمل رائد: أول مسح منهجي شامل في مجال إلغاء التعلم على الرسوم البيانية
  2. الشمولية: تغطي الطرق والتطبيقات والتقييم وأبعاد متعددة أخرى
  3. الفائدة العملية: توفر خريطة طريق تقنية واضحة للباحثين والممارسين
  4. النظر المستقبلي: تحديد عدة اتجاهات بحثية قيمة
  5. التنظيم: إنشاء المفاهيم الأساسية وإطار التصنيف للمجال

أوجه القصور

  1. التحليل التجريبي محدود: كورقة استقصائية، تفتقر إلى التحقق التجريبي الجديد
  2. عمق الطرق: يمكن أن يكون وصف التفاصيل التقنية لبعض الطرق المعقدة أعمق
  3. غياب المعايير: غياب اختبارات معايير موحدة ومعايير مقارنة
  4. التحليل النظري: يمكن أن يكون تحليل التعقيد النظري لطرق مختلفة أكثر تفصيلاً

التأثير

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

السيناريوهات المطبقة

  1. التطبيقات الحساسة للخصوصية: المجالات الطبية والمالية وغيرها التي تتطلب حماية خصوصية صارمة
  2. أنظمة الرسوم البيانية الكبيرة: تطبيقات الإنترنت مثل الشبكات الاجتماعية وأنظمة التوصيات
  3. البيئات الخصومة: الأنظمة الحرجة للأمان التي تحتاج إلى مقاومة هجمات تسميم البيانات
  4. متطلبات الامتثال: الأنظمة التي تحتاج إلى الامتثال لقوانين حماية البيانات مثل GDPR

المراجع

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

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