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 (কম্পিউটেশনাল ভাষাবিজ্ঞান)
  • প্রকাশনার সময়: ২০২৪ সালের ১৪ অক্টোবর (arXiv প্রাক-প্রিন্ট)
  • পেপার লিঙ্ক: https://arxiv.org/abs/2510.12434

সারসংক্ষেপ

জ্ঞান হাইপারগ্রাফ (Knowledge Hypergraphs, KHs) পুনরুদ্ধার-বর্ধিত প্রজন্ম (RAG) এর জন্য একটি উদীয়মান জ্ঞান প্রতিনিধিত্ব ফর্ম হিসাবে, একাধিক সত্তার সম্পর্ককে কাঠামোগত ফর্মে মডেল করার একটি প্যারাডাইম প্রদান করে। তবে, বিদ্যমান KH-ভিত্তিক RAG পদ্ধতিগুলি তিনটি প্রধান সীমাবদ্ধতার সম্মুখীন: স্থির পুনরুদ্ধার পরিকল্পনা, অ-অভিযোজনশীল পুনরুদ্ধার সম্পাদন এবং KH কাঠামোগত শব্দার্থের অগভীর ব্যবহার, যা কার্যকর বহু-হপ প্রশ্নোত্তরের ক্ষমতা সীমিত করে। এই সীমাবদ্ধতাগুলি অতিক্রম করার জন্য, এই পেপারটি PRoH প্রস্তাব করে—একটি গতিশীল জ্ঞান হাইপারগ্রাফ পরিকল্পনা এবং যুক্তিবিদ্যা কাঠামো। PRoH তিনটি মূল উদ্ভাবন অন্তর্ভুক্ত করে: (1) প্রসঙ্গ-সচেতন পরিকল্পনা মডিউল, যা স্থানীয় KH প্রতিবেশী স্কেচ করে কাঠামোগত যুক্তিবিদ্যা পরিকল্পনা প্রজন্মকে গাইড করে; (2) কাঠামোগত প্রশ্ন বিয়োজন প্রক্রিয়া, যা উপ-প্রশ্নগুলিকে অভিযোজনশীল বহু-ট্র্যাজেক্টরি অন্বেষণের জন্য গতিশীলভাবে বিকশিত নির্দেশিত অ্যাসাইক্লিক গ্রাফ (DAG) হিসাবে সংগঠিত করে; (3) সত্তা-ওজনযুক্ত ওভারল্যাপ (EWO) নির্দেশিত যুক্তিবিদ্যা পথ পুনরুদ্ধার অ্যালগরিদম, যা শব্দার্থগতভাবে সুসংগত হাইপারেজ ট্রাভার্সালকে অগ্রাধিকার দেয়।

গবেষণা পটভূমি এবং প্রেরণা

সমস্যা সংজ্ঞা

ঐতিহ্যবাহী RAG সিস্টেমগুলি প্রধানত শব্দার্থগত সাদৃশ্যের জন্য পুনরুদ্ধারের উপর নির্ভর করে, অনেক তথ্য ক্ষেত্রে অন্তর্নিহিত কাঠামোগত সম্পর্ক জ্ঞান ক্যাপচার করতে পারে না এবং প্রায়শই অপ্রয়োজনীয় বা শব্দযুক্ত সামগ্রী পুনরুদ্ধার করে। যদিও গ্রাফ-ভিত্তিক RAG জ্ঞান গ্রাফ (KG) এর মাধ্যমে এটি উন্নত করে, বেশিরভাগ বিদ্যমান কাঠামো শুধুমাত্র দুটি সত্তা জড়িত সম্পর্ক মডেল করে, বাস্তব বিশ্বে অনেক সম্পর্ক প্রকৃতিতে n-ary হওয়ার বৈশিষ্ট্য উপেক্ষা করে।

গুরুত্ব বিশ্লেষণ

বাস্তব বিশ্বের অনেক সম্পর্ক একাধিক সত্তা জড়িত, যেমন "Mario + Rabbids Kingdom Battle নিন্টেন্ডো এবং ইউবিসফ্টের মধ্যে প্রথম প্রধান সহযোগিতা" এই সম্পর্ক একযোগে তিনটি সত্তা সংযুক্ত করে। এই n-ary সম্পর্কগুলিকে একাধিক বাইনারি এজে বিয়োজন করা অনিবার্যভাবে মূল কাঠামো এবং শব্দার্থগত তথ্যের ক্ষতির দিকে পরিচালিত করে।

বিদ্যমান পদ্ধতির সীমাবদ্ধতা

বিদ্যমান KH-ভিত্তিক RAG পদ্ধতিগুলি তিনটি প্রধান সীমাবদ্ধতা উপস্থাপন করে:

  1. স্থির পুনরুদ্ধার পরিকল্পনা: পূর্বনির্ধারিত হার্ডকোডেড পুনরুদ্ধার পাইপলাইনের উপর নির্ভর করে, প্রশ্নের বিষয়বস্তু বা গ্রাফ প্রসঙ্গ নির্বিশেষে একই অপারেশন ক্রম প্রয়োগ করে
  2. অ-অভিযোজনশীল পুনরুদ্ধার সম্পাদন: একবার, অ-পুনরাবৃত্তিমূলক পুনরুদ্ধার পদ্ধতি গ্রহণ করে, মধ্যবর্তী যুক্তিবিদ্যা ফলাফল ব্যবহার করে পুনরুদ্ধার অপ্টিমাইজ করতে পারে না
  3. গ্রাফ কাঠামো শব্দার্থের অগভীর ব্যবহার: প্রধানত হাইপারেজগুলিকে সাধারণ লিঙ্ক বা প্রাসঙ্গিক পাঠ্য ব্লক অ্যাক্সেস করার রুটিং মেকানিজম হিসাবে বিবেচনা করে, হাইপারেজে এনকোড করা সমৃদ্ধ সম্পর্ক শব্দার্থ উপেক্ষা করে

মূল অবদান

  1. PRoH কাঠামো প্রস্তাব: একটি গতিশীল জ্ঞান হাইপারগ্রাফ RAG কাঠামো, যা বহু-হপ প্রশ্নোত্তরের জন্য হাইপারগ্রাফের প্রকাশনীয় ক্ষমতা সম্পূর্ণভাবে ব্যবহার করে
  2. প্রসঙ্গ-সচেতন পরিকল্পনা প্রক্রিয়া: অন্তর্নিহিত জ্ঞান হাইপারগ্রাফ স্কেচ করে এবং সম্ভাব্য যুক্তিবিদ্যা পরিকল্পনা তৈরি করার একটি পরিকল্পনা প্রক্রিয়া
  3. EWO-নির্দেশিত যুক্তিবিদ্যা পথ পুনরুদ্ধার কৌশল: জ্ঞান হাইপারগ্রাফের জন্য সূক্ষ্ম-দানাদার, শব্দার্থ-সচেতন অন্বেষণ কৌশল
  4. উল্লেখযোগ্য কর্মক্ষমতা উন্নতি: একাধিক জ্ঞান ক্ষেত্রে SOTA কর্মক্ষমতা অর্জন, F1 স্কোর গড়ে ১৯.৭৩% বৃদ্ধি, প্রজন্ম মূল্যায়ন (G-E) স্কোর ৮.৪১% বৃদ্ধি

পদ্ধতি বিস্তারিত

কাজের সংজ্ঞা

প্রশ্ন q এবং জ্ঞান হাইপারগ্রাফ H = (V, E) দেওয়া, হাইপারগ্রাফ RAG কে H থেকে প্রশ্ন-প্রাসঙ্গিক জ্ঞান (তথ্য সেট F) পুনরুদ্ধার করতে হবে, তারপর q এবং F এর উপর ভিত্তি করে উত্তর a(q) তৈরি করতে হবে।

মডেল স্থাপত্য

PRoH কাঠামোতে চারটি প্রধান উপাদান রয়েছে:

1. গ্রাফ নির্মাণ এবং সূচকীকরণ

  • KH নির্মাণ: নথি থেকে হাইপারেজ নিষ্কাশন, সত্তা সনাক্তকরণ এবং KH নির্মাণের জন্য HyperGraphRAG পদ্ধতি গ্রহণ করে
  • সমার্থক হাইপারেজ বর্ধন: গ্রাফ সংযোগযোগ্যতা বৃদ্ধির জন্য তিন-পদক্ষেপ প্রক্রিয়ার মাধ্যমে সমার্থক হাইপারেজ যোগ করে:
    • সত্তা জোড়ার কোসাইন সাদৃশ্য গণনা করা
    • সাদৃশ্য উপগ্রাফ গঠন এবং সংযুক্ত উপাদান গণনা করা
    • সমার্থক সত্তা নির্ধারণ করতে LLM ব্যবহার করা এবং সমার্থক হাইপারেজ যোগ করা

2. গ্রাফ অ্যাঙ্করিং

  • বিষয় সত্তা সনাক্তকরণ: মূল শব্দ নিষ্কাশনের জন্য LLM ব্যবহার করে, সাদৃশ্য ম্যাচিংয়ের মাধ্যমে প্রার্থী সত্তার সাথে লিঙ্ক করে
  • লক্ষ্য হাইপারেজ ম্যাচিং: প্রশ্নের শব্দার্থের সাথে সম্পর্কিত হাইপারেজ পুনরুদ্ধার করে
  • প্রশ্ন উপগ্রাফ নির্মাণ: বিষয় সত্তা এবং লক্ষ্য হাইপারেজের Dmax-হপ প্রতিবেশীর ইউনিয়ন নিষ্কাশন করে

3. যুক্তিবিদ্যা পরিকল্পনা আরম্ভকরণ

  • প্রশ্ন উপগ্রাফ স্কেচ: পরিকল্পনা প্রসঙ্গ গ্রাফ Hp নির্মাণ করে, LLM কে কাঠামোগত ইনপুট প্রদান করে
  • প্রাথমিক যুক্তিবিদ্যা পরিকল্পনা প্রজন্ম: পরিকল্পনা প্রসঙ্গের উপর ভিত্তি করে যুক্তিবিদ্যা পরিকল্পনা তৈরি করে
  • যুক্তিবিদ্যা DAG নির্মাণ: যুক্তিবিদ্যা পরিকল্পনা একটি নির্দেশিত অ্যাসাইক্লিক গ্রাফ হিসাবে প্রতিনিধিত্ব করে, ন্যূনতম প্রতিনিধিত্ব পেতে Hasse হ্রাস প্রয়োগ করে

4. যুক্তিবিদ্যা প্রক্রিয়া

  • অবস্থা স্থান অনুসন্ধান: DAG অবস্থায় অনুসন্ধান সমস্যা হিসাবে যুক্তিবিদ্যা মডেল করে
  • অবস্থা রূপান্তর: বর্তমান স্তরের উপ-প্রশ্ন সমাধান করে পরবর্তী অবস্থায় রূপান্তরিত করে
  • গতিশীল DAG অপ্টিমাইজেশন: মধ্যবর্তী উত্তরের উপর ভিত্তি করে যুক্তিবিদ্যা DAG গতিশীলভাবে অপ্টিমাইজ করে

প্রযুক্তিগত উদ্ভাবন পয়েন্ট

সত্তা-ওজনযুক্ত ওভারল্যাপ (EWO) স্কোরিং

EWO অ্যালগরিদম দুই-পদক্ষেপ গণনার মাধ্যমে অনুসন্ধান দিকনির্দেশনা নির্বাচন গাইড করে:

  1. সত্তা স্কোরিং:
EW(v|qj) = {
    LLMScore(v, qj), if SE(v|qj) ≥ θemb
    0, otherwise
}
  1. হাইপারেজ স্কোরিং:
EWO(e'|q,e) = Aggregate({SE(v,q) | v ∈ V(e) ∩ V(e')})

কাঠামোগত প্রশ্ন বিয়োজন

  • উপ-প্রশ্নগুলিকে রৈখিক ক্রম নয় বরং গতিশীলভাবে বিকশিত DAG হিসাবে সংগঠিত করে
  • একাধিক প্রার্থী উত্তর এবং একাধিক যুক্তিবিদ্যা ট্র্যাজেক্টরির সহাবস্থান সমর্থন করে
  • স্থানীয় ত্রুটি থেকে পুনরুদ্ধার অনুমতি দেয়

পরীক্ষামূলক সেটআপ

ডেটাসেট

  • KHQA ডেটাসেট: চিকিৎসা, কৃষি, কম্পিউটার বিজ্ঞান, আইন এবং মিশ্র পাঁচটি ক্ষেত্র অন্তর্ভুক্ত করে
  • দীর্ঘ-পরিসীমা প্রশ্ন সম্প্রসারণ: বহু-হপ যুক্তিবিদ্যা ক্ষমতা মূল্যায়নের জন্য প্রতিটি ক্ষেত্রে অতিরিক্ত ২০০টি ৩-৬ হপ দীর্ঘ-পরিসীমা প্রশ্ন তৈরি করা হয়

মূল্যায়ন মেট্রিক্স

  • F1 স্কোর: উত্তর নির্ভুলতা পরিমাপ করে
  • পুনরুদ্ধার সাদৃশ্য (R-S): পুনরুদ্ধার সামগ্রীর গুণমান মূল্যায়ন করে
  • প্রজন্ম মূল্যায়ন (G-E): উত্পাদিত উত্তরের গুণমান মূল্যায়ন করে

তুলনামূলক পদ্ধতি

  • LLM-only: শুধুমাত্র LLM অন্তর্নিহিত জ্ঞান ব্যবহার করে
  • StandardRAG: ঐতিহ্যবাহী ব্লক-ভিত্তিক RAG
  • PathRAG: পথ-ভিত্তিক RAG পদ্ধতি
  • HippoRAG2: নিউরোবায়োলজি-অনুপ্রাণিত দীর্ঘমেয়াদী স্মৃতি পদ্ধতি
  • HyperGraphRAG: বর্তমান SOTA হাইপারগ্রাফ RAG পদ্ধতি

বাস্তবায়ন বিবরণ

  • LLM: GPT-4o-mini
  • এমবেডিং মডেল: text-embedding-3-small
  • মূল পরামিতি: পরিকল্পনা গভীরতা dp=3, KH অন্বেষণ গভীরতা সীমা dmax=3, প্রাথমিক পরিকল্পনা সংখ্যা n0=2

পরীক্ষামূলক ফলাফল

প্রধান ফলাফল

PRoH সমস্ত ক্ষেত্রে F1 এবং G-E স্কোরে SOTA কর্মক্ষমতা অর্জন করেছে:

ক্ষেত্রHyperGraphRAG F1PRoH F1বৃদ্ধি
চিকিৎসা35.3552.94+49.7%
কৃষি33.8956.67+67.2%
কম্পিউটার বিজ্ঞান31.3054.15+73.0%
আইন43.8158.81+34.2%
মিশ্র48.7169.16+42.0%

বিয়োজন পরীক্ষা

বিয়োজন পরীক্ষা প্রতিটি উপাদানের গুরুত্ব প্রদর্শন করে:

  • EWO নির্দেশনা অপসারণ: F1 সর্বোচ্চ ৫.৩% হ্রাস
  • সমার্থক একীকরণ অপসারণ: F1 সর্বোচ্চ ৫.২% হ্রাস
  • পরিকল্পনা প্রসঙ্গ অপসারণ: F1 সর্বোচ্চ ৫.৮% হ্রাস
  • লক্ষ্য হাইপারেজ ম্যাচিং অপসারণ: F1 সর্বোচ্চ ৮.৬% হ্রাস

দীর্ঘ-পরিসীমা যুক্তিবিদ্যা কর্মক্ষমতা

দীর্ঘ-পরিসীমা বহু-হপ প্রশ্নোত্তর কাজে, PRoH শক্তিশালী স্থিতিস্থাপকতা প্রদর্শন করে, গড় F1 বৃদ্ধি ২৬.৬৮%, কম্পিউটার বিজ্ঞান ক্ষেত্রে সর্বোচ্চ বৃদ্ধি ৪৪.৮৭%।

দক্ষতা বিশ্লেষণ

PRoH-L ভেরিয়েন্ট টোকেন ব্যবহারের পরিমাণ উল্লেখযোগ্যভাবে হ্রাস করার সময় প্রতিযোগিতামূলক কর্মক্ষমতা বজায় রাখে, কৃষি ক্ষেত্রে টোকেন ৩০.০৭% হ্রাস করার সময় F1 ১৬.৫৮% বৃদ্ধি করে।

সম্পর্কিত কাজ

গ্রাফ-ভিত্তিক RAG

বিদ্যমান গ্রাফ-ভিত্তিক RAG পদ্ধতিগুলি জ্ঞান গ্রাফের মাধ্যমে আরও নির্ভুল পুনরুদ্ধার এবং সম্পর্ক-সচেতন যুক্তিবিদ্যা বাস্তবায়ন করে, কিন্তু বেশিরভাগ বাইনারি সম্পর্ক প্রতিনিধিত্বে সীমাবদ্ধ।

জ্ঞান হাইপারগ্রাফ RAG

HyperGraphRAG এবং Hyper-RAG এর মতো প্রাথমিক সিস্টেমগুলি উচ্চ-ক্রম সম্পর্ক ক্যাপচার করতে হাইপারেজ নিষ্কাশন করে, কিন্তু এখনও হিউরিস্টিক একবার পুনরুদ্ধার পাইপলাইনের উপর নির্ভর করে, প্রসঙ্গ-সচেতনতা এবং পুনরাবৃত্তিমূলক যুক্তিবিদ্যা ক্ষমতার অভাব রয়েছে।

উপসংহার এবং আলোচনা

প্রধান উপসংহার

PRoH প্রসঙ্গ-সচেতন পরিকল্পনা, কাঠামোগত পুনরাবৃত্তিমূলক প্রশ্ন বিয়োজন এবং EWO-নির্দেশিত যুক্তিবিদ্যা পথ পুনরুদ্ধার প্রবর্তন করে, বিদ্যমান KH-ভিত্তিক RAG পদ্ধতির তিনটি প্রধান সীমাবদ্ধতা সফলভাবে সমাধান করে, একাধিক জ্ঞান ক্ষেত্রে উল্লেখযোগ্য কর্মক্ষমতা উন্নতি অর্জন করে।

সীমাবদ্ধতা

  1. গণনামূলক জটিলতা: গতিশীল পরিকল্পনা এবং অবস্থা স্থান অনুসন্ধান অতিরিক্ত গণনামূলক ওভারহেড আনতে পারে
  2. পরামিতি সংবেদনশীলতা: একাধিক হাইপারপ্যারামিটার (যেমন dp, dmax, n0) বিভিন্ন ক্ষেত্রের জন্য সামঞ্জস্য প্রয়োজন
  3. গ্রাফ গুণমান নির্ভরতা: কর্মক্ষমতা প্রাথমিক জ্ঞান হাইপারগ্রাফের গুণমান এবং সম্পূর্ণতার উপর অত্যন্ত নির্ভরশীল

ভবিষ্যত দিকনির্দেশনা

  1. আরও দক্ষ অবস্থা স্থান অনুসন্ধান কৌশল অন্বেষণ করা
  2. অভিযোজনশীল পরামিতি সমন্বয় প্রক্রিয়া গবেষণা করা
  3. বৃহত্তর স্কেলের জ্ঞান হাইপারগ্রাফ এবং আরও জটিল যুক্তিবিদ্যা কাজে সম্প্রসারণ করা

গভীর মূল্যায়ন

সুবিধা

  1. শক্তিশালী উদ্ভাবনী: প্রথমবারের মতো গতিশীল পরিকল্পনা এবং যুক্তিবিদ্যার KH-RAG কাঠামো প্রস্তাব করে, বিদ্যমান পদ্ধতির মূল সীমাবদ্ধতা সমাধান করে
  2. উল্লেখযোগ্য প্রযুক্তিগত অবদান: EWO স্কোরিং প্রক্রিয়া এবং কাঠামোগত প্রশ্ন বিয়োজন হাইপারগ্রাফ বৈশিষ্ট্যের জন্য গুরুত্বপূর্ণ উদ্ভাবন
  3. ব্যাপক পরীক্ষা: একাধিক ক্ষেত্র এবং দীর্ঘ-পরিসীমা যুক্তিবিদ্যা কাজ অন্তর্ভুক্ত করে, বিয়োজন পরীক্ষা ব্যাপক
  4. স্পষ্ট কর্মক্ষমতা উন্নতি: SOTA পদ্ধতির তুলনায় উল্লেখযোগ্য এবং সামঞ্জস্যপূর্ণ উন্নতি

অপূর্ণতা

  1. উচ্চ জটিলতা: পদ্ধতিতে একাধিক মডিউল এবং পরামিতি রয়েছে, যা প্রকৃত স্থাপনার সুবিধা প্রভাবিত করতে পারে
  2. গণনামূলক খরচ বিশ্লেষণ অপর্যাপ্ত: যদিও টোকেন ব্যবহার বিশ্লেষণ প্রদান করা হয়, বিস্তারিত সময় জটিলতা বিশ্লেষণের অভাব রয়েছে
  3. সীমিত সাধারণীকরণ যাচাইকরণ: পরীক্ষা প্রধানত নির্দিষ্ট KHQA ডেটাসেটে কেন্দ্রীভূত

প্রভাব

  1. একাডেমিক মূল্য: KH-RAG ক্ষেত্রে নতুন গবেষণা দিকনির্দেশনা এবং প্রযুক্তিগত কাঠামো প্রদান করে
  2. ব্যবহারিক মূল্য: জটিল বহু-হপ যুক্তিবিদ্যা প্রয়োজনীয় প্রয়োগ পরিস্থিতিতে গুরুত্বপূর্ণ মূল্য রয়েছে
  3. পুনরুৎপাদনযোগ্যতা: বিস্তারিত অ্যালগরিদম বর্ণনা এবং বাস্তবায়ন বিবরণ প্রদান করে

প্রযোজ্য পরিস্থিতি

PRoH বিশেষভাবে উপযুক্ত:

  1. জটিল বহু-হপ যুক্তিবিদ্যা প্রয়োজনীয় প্রশ্নোত্তর সিস্টেম
  2. একাধিক সত্তা সম্পর্ক জড়িত জ্ঞান-নিবিড় কাজ
  3. যুক্তিবিদ্যা পথ ব্যাখ্যাযোগ্যতার প্রতি প্রয়োজনীয় প্রয়োগ পরিস্থিতি

তথ্যসূত্র

পেপারটি ৪০টি সম্পর্কিত তথ্যসূত্র উদ্ধৃত করে, যা গ্রাফ-ভিত্তিক RAG, জ্ঞান হাইপারগ্রাফ, বহু-হপ যুক্তিবিদ্যা এবং অন্যান্য সম্পর্কিত ক্ষেত্রের গুরুত্বপূর্ণ কাজ অন্তর্ভুক্ত করে, গবেষণার জন্য একটি দৃঢ় তাত্ত্বিক ভিত্তি প্রদান করে।