2025-11-12T08:22:09.411485

PRoH: Dynamic Planning and Reasoning over Knowledge Hypergraphs for Retrieval-Augmented Generation

Zai, Tan, Wang et al.

Knowledge Hypergraphs (KHs) have recently emerged as a knowledge representation for retrieval-augmented generation (RAG), offering a paradigm to model multi-entity relations into a structured form. However, existing KH-based RAG methods suffer from three major limitations: static retrieval planning, non-adaptive retrieval execution, and superficial use of KH structure and semantics, which constrain their ability to perform effective multi-hop question answering. To overcome these limitations, we propose PRoH, a dynamic Planning and Reasoning over Knowledge Hypergraphs framework. PRoH incorporates three core innovations: (i) a context-aware planning module that sketches the local KH neighborhood to guide structurally grounded reasoning plan generation; (ii) a structured question decomposition process that organizes subquestions as a dynamically evolving Directed Acyclic Graph (DAG) to enable adaptive, multi-trajectory exploration; and (iii) an Entity-Weighted Overlap (EWO)-guided reasoning path retrieval algorithm that prioritizes semantically coherent hyperedge traversals. Experiments across multiple domains demonstrate that PRoH achieves state-of-the-art performance, surpassing the prior SOTA model HyperGraphRAG by an average of 19.73% in F1 and 8.41% in Generation Evaluation (G-E) score, while maintaining strong robustness in long-range multi-hop reasoning tasks.

academic

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

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

معرّف الورقة: 2510.12434
العنوان: PRoH: Dynamic Planning and Reasoning over Knowledge Hypergraphs for Retrieval-Augmented Generation
المؤلفون: Xiangjun Zai, Xingyu Tan, Xiaoyang Wang, Qing Liu, Xiwei Xu, Wenjie Zhang
التصنيف: cs.CL (اللسانيات الحاسوبية)
تاريخ النشر: 14 أكتوبر 2024 (نسخة arXiv المسبقة)
رابط الورقة: https://arxiv.org/abs/2510.12434

الملخص

تمثل الرسوم البيانية الفائقة للمعرفة (Knowledge Hypergraphs, KHs) شكلاً ناشئاً من أشكال تمثيل المعرفة لتوليد معزز بالاسترجاع (RAG)، وتوفر نموذجاً لنمذجة العلاقات متعددة الكيانات في شكل منظم. ومع ذلك، تعاني الطرق الحالية القائمة على KH من ثلاث قيود رئيسية: التخطيط الثابت للاسترجاع، والتنفيذ غير التكيفي للاسترجاع، والاستخدام السطحي لدلالات بنية KH، مما يحد من قدرتها على الإجابة على أسئلة متعددة الخطوات بفعالية. للتغلب على هذه القيود، تقترح هذه الورقة PRoH - إطار عمل ديناميكي للتخطيط والاستدلال على الرسوم البيانية الفائقة للمعرفة. يتضمن PRoH ثلاث ابتكارات أساسية: (1) وحدة تخطيط تدرك السياق، من خلال تحديد الحي المحلي لـ KH لتوجيه توليد خطط الاستدلال المنظمة؛ (2) عملية تحليل الأسئلة المنظمة، التي تنظم الأسئلة الفرعية كرسم بياني موجه غير دوري (DAG) متطور ديناميكياً لتحقيق الاستكشاف المتعدد المسارات التكيفي؛ (3) خوارزمية استرجاع مسار الاستدلال الموجهة بالتداخل المرجح للكيانات (EWO)، التي تعطي الأولوية لاجتياز الحواف الفائقة المتماسكة دلالياً.

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

تعريف المشكلة

تعتمد أنظمة RAG التقليدية بشكل أساسي على التشابه الدلالي للاسترجاع، وغير قادرة على التقاط معرفة العلاقات المنظمة المتأصلة في العديد من مجالات المعلومات، وغالباً ما تسترجع محتوى زائداً أو مزعجاً. على الرغم من أن RAG القائم على الرسوم البيانية يحسن هذه المشكلة من خلال الرسوم البيانية للمعرفة (KG)، إلا أن معظم الأطر الموجودة تنمذج فقط العلاقات التي تتضمن كيانين، متجاهلة الطبيعة n-ary للعديد من العلاقات في العالم الحقيقي.

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

تتضمن العديد من العلاقات في العالم الحقيقي كيانات متعددة، مثل "Mario + Rabbids Kingdom Battle هو أول تعاون رئيسي بين Nintendo و Ubisoft"، وهذه العلاقة تربط ثلاثة كيانات في نفس الوقت. سيؤدي تحليل هذه العلاقات n-ary إلى حواف ثنائية متعددة حتماً إلى فقدان المعلومات الهيكلية والدلالية الرئيسية.

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

تعاني طرق RAG القائمة على KH من ثلاث قيود رئيسية:

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

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

اقتراح إطار عمل PRoH: إطار عمل ديناميكي لـ RAG على الرسوم البيانية الفائقة للمعرفة، يستفيد بالكامل من القدرة التعبيرية للرسوم البيانية الفائقة للإجابة على أسئلة متعددة الخطوات
آلية التخطيط التي تدرك السياق: آلية تخطيط من خلال تحديد الرسم البياني الفائق للمعرفة الأساسي وتوليد خطط استدلال قابلة للتنفيذ
استراتيجية استرجاع مسار الاستدلال الموجهة بـ EWO: استراتيجية استكشاف دقيقة الحبيبات وتدرك الدلالات موجهة نحو الرسوم البيانية الفائقة للمعرفة
تحسن أداء كبير: تحقيق أداء متقدمة (SOTA) على مجالات معرفية متعددة، مع متوسط تحسن في درجة F1 بنسبة 19.73%، وتحسن درجة التقييم التوليدي (G-E) بنسبة 8.41%

شرح الطريقة

تعريف المهمة

بالنظر إلى سؤال q ورسم بياني فائق للمعرفة H = (V, E)، يحتاج RAG الفائق إلى استرجاع المعرفة ذات الصلة بالسؤال من H (مجموعة الحقائق F)، ثم توليد إجابة a(q) بناءً على q و F.

معمارية النموذج

يتضمن إطار عمل PRoH أربع مكونات رئيسية:

1. بناء الرسم البياني والفهرسة

بناء KH: استخدام طريقة HyperGraphRAG لاستخراج الحواف الفائقة من المستندات وتحديد الكيانات وبناء KH
تحسين الحواف الفائقة المترادفة: إضافة حواف فائقة مترادفة من خلال عملية من ثلاث خطوات لتحسين اتصال الرسم البياني:
- حساب تشابه جيب التمام لأزواج الكيانات
- تشكيل رسم بياني فرعي للتشابه وحساب المكونات المتصلة
- استخدام نموذج لغة كبير (LLM) لتحديد الكيانات المترادفة وإضافة حواف فائقة مترادفة

2. تثبيت الرسم البياني

تحديد الكيانات الموضوعية: استخدام LLM لاستخراج الكلمات الرئيسية، والربط بالكيانات المرشحة من خلال مطابقة التشابه
مطابقة الحواف الفائقة المستهدفة: استرجاع الحواف الفائقة ذات الصلة دلالياً بالسؤال
بناء الرسم البياني الفرعي للسؤال: استخراج اتحاد الحي البعيد Dmax للكيانات الموضوعية والحواف الفائقة المستهدفة

3. تهيئة خطة الاستدلال

تحديد الرسم البياني الفرعي للسؤال: بناء رسم بياني سياق التخطيط Hp، وتوفير مدخلات منظمة لـ LLM
توليد خطة الاستدلال الأولية: توليد خطة استدلال بناءً على سياق التخطيط
بناء DAG الاستدلال: تمثيل خطة الاستدلال كرسم بياني موجه غير دوري، وتطبيق الاختزال Hasse للحصول على تمثيل أدنى

4. عملية الاستدلال

البحث في فضاء الحالة: نمذجة الاستدلال كمشكلة بحث على حالات DAG
انتقال الحالة: الانتقال إلى الحالة التالية من خلال حل الأسئلة الفرعية في المستوى الحالي
تحسين DAG الديناميكي: تحسين DAG الاستدلال ديناميكياً بناءً على الإجابات الوسيطة

نقاط الابتكار التقني

تقييم التداخل المرجح للكيانات (EWO)

تقوم خوارزمية EWO بتوجيه اختيار اتجاه البحث من خلال حساب من خطوتين:

تقييم الكيان:

EW(v|qj) = {
    LLMScore(v, qj), if SE(v|qj) ≥ θemb
    0, otherwise
}

تقييم الحافة الفائقة:

EWO(e'|q,e) = Aggregate({SE(v,q) | v ∈ V(e) ∩ V(e')})

تحليل الأسئلة المنظم

تنظيم الأسئلة الفرعية كـ DAG متطور ديناميكياً بدلاً من تسلسل خطي
دعم التعايش المتزامن لإجابات مرشحة متعددة ومسارات استدلال متعددة
السماح بالتعافي من الأخطاء المحلية

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

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

مجموعة بيانات KHQA: تغطي خمسة مجالات: الطب والزراعة وعلوم الحاسوب والقانون والمختلط
توسيع الأسئلة طويلة المدى: توليد 200 سؤال إضافي بطول 3-6 خطوات لكل مجال لتقييم قدرة الاستدلال متعدد الخطوات

مقاييس التقييم

درجة F1: قياس دقة الإجابة
تشابه الاسترجاع (R-S): تقييم جودة المحتوى المسترجع
التقييم التوليدي (G-E): تقييم جودة الإجابة المولدة

طرق المقارنة

LLM فقط: استخدام المعرفة الكامنة في LLM فقط
StandardRAG: RAG تقليدي قائم على الكتل
PathRAG: طريقة RAG قائمة على المسارات
HippoRAG2: طريقة الذاكرة طويلة المدى المستوحاة من علم الأعصاب
HyperGraphRAG: طريقة RAG الفائقة الحالية المتقدمة (SOTA)

تفاصيل التنفيذ

نموذج اللغة: GPT-4o-mini
نموذج التضمين: text-embedding-3-small
المعاملات الرئيسية: عمق التخطيط dp=3، حد عمق استكشاف KH dmax=3، عدد الخطط الأولية n0=2

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

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

حقق PRoH أداء متقدمة (SOTA) في درجات F1 و G-E على جميع المجالات:

المجال	F1 لـ HyperGraphRAG	F1 لـ PRoH	التحسن
الطب	35.35	52.94	+49.7%
الزراعة	33.89	56.67	+67.2%
علوم الحاسوب	31.30	54.15	+73.0%
القانون	43.81	58.81	+34.2%
المختلط	48.71	69.16	+42.0%

تجارب الاستئصال

تظهر تجارب الاستئصال أهمية كل مكون:

إزالة توجيه EWO: انخفاض F1 بحد أقصى 5.3%
إزالة دمج المترادفات: انخفاض F1 بحد أقصى 5.2%
إزالة سياق التخطيط: انخفاض F1 بحد أقصى 5.8%
إزالة مطابقة الحواف الفائقة المستهدفة: انخفاض F1 بحد أقصى 8.6%

أداء الاستدلال طويل المدى

في مهام الإجابة على الأسئلة متعددة الخطوات طويلة المدى، يظهر PRoH متانة قوية، مع متوسط تحسن في F1 بنسبة 26.68%، وأعلى تحسن في مجال علوم الحاسوب بنسبة 44.87%.

تحليل الكفاءة

يحافظ متغير PRoH-L على أداء تنافسية مع تقليل كبير في استخدام الرموز، مع تقليل الرموز بنسبة 30.07% في مجال الزراعة مع تحسن F1 بنسبة 16.58%.

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

RAG القائم على الرسوم البيانية

تحقق طرق RAG القائمة على الرسوم البيانية الموجودة استرجاعاً أكثر دقة واستدلالاً يدرك العلاقات من خلال الرسوم البيانية للمعرفة، لكن معظمها يقتصر على تمثيل العلاقات الثنائية.

RAG الفائق للمعرفة

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

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

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

يحل PRoH بنجاح القيود الثلاثة الرئيسية لطرق RAG القائمة على KH من خلال إدخال التخطيط الذي يدرك السياق، وتحليل الأسئلة المنظم والتكراري، واسترجاع مسار الاستدلال الموجه بـ EWO، مما يحقق تحسناً كبيراً في الأداء عبر مجالات معرفية متعددة.

القيود

التعقيد الحسابي: قد يؤدي البرمجة الديناميكية والبحث في فضاء الحالة إلى تكاليف حسابية إضافية
حساسية المعاملات: تتطلب معاملات متعددة (مثل dp و dmax و n0) ضبطاً لمجالات مختلفة
الاعتماد على جودة الرسم البياني: تعتمد الأداء بشكل كبير على جودة واكتمال الرسم البياني الفائق للمعرفة الأولي

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

استكشاف استراتيجيات بحث فضاء حالة أكثر كفاءة
البحث في آليات ضبط المعاملات التكيفية
التوسع إلى رسوم بيانية فائقة للمعرفة أكبر حجماً ومهام استدلال أكثر تعقيداً

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

المميزات

ابتكار قوي: أول إطار عمل KH-RAG يقترح التخطيط الديناميكي والاستدلال، ويحل القيود الأساسية للطرق الموجودة
مساهمات تقنية كبيرة: آلية تقييم EWO وتحليل الأسئلة المنظم هما ابتكارات مهمة موجهة نحو خصائص الرسوم البيانية الفائقة
تجارب شاملة: تغطي مجالات متعددة ومهام استدلال طويلة المدى، مع تجارب استئصال شاملة
تحسن أداء واضح: تحسن كبير وثابت مقارنة بطرق SOTA

أوجه القصور

التعقيد المرتفع: تتضمن الطريقة مكونات ومعاملات متعددة، مما قد يؤثر على سهولة النشر العملي
تحليل التكلفة الحسابية غير كافٍ: على الرغم من توفير تحليل استخدام الرموز، إلا أنه يفتقر إلى تحليل تعقيد الوقت التفصيلي
التحقق من القابلية للتعميم محدود: تركز التجارب بشكل أساسي على مجموعة بيانات KHQA المحددة

التأثير

القيمة الأكاديمية: توفير اتجاه بحث جديد وإطار عمل تقني لمجال KH-RAG
القيمة العملية: ذات أهمية كبيرة في سيناريوهات التطبيقات التي تتطلب استدلالاً معقداً متعدد الخطوات
القابلية للتكرار: توفير وصف خوارزمي تفصيلي وتفاصيل تنفيذية

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

يناسب PRoH بشكل خاص:

أنظمة الإجابة على الأسئلة المعقدة التي تتطلب استدلالاً متعدد الخطوات
المهام الكثيفة بالمعرفة التي تتضمن علاقات متعددة الكيانات
سيناريوهات التطبيقات التي تتطلب قابلية تفسير مسار الاستدلال

المراجع

تستشهد الورقة بـ 40 مرجعاً ذا صلة، تغطي الأعمال المهمة في مجالات RAG القائم على الرسوم البيانية والرسوم البيانية الفائقة للمعرفة والاستدلال متعدد الخطوات، مما يوفر أساساً نظرياً متيناً للبحث.