Source-linked AI summary
Automated Tree Knowledge Graph Construction using Ontology Expansion and Retrieval from Vietnamese History Textbooks
Ket Doan Nguyen, Minh N. H. Nguyen
TL;DR
The paper addresses missing methods for automatic Vietnamese KG construction with ontology expansion and limited systematic evaluation of hierarchical retrieval. It builds and evaluates an end-to-end pipeline using controlled extraction, a synthetic benchmark, and three traversal strategies. Top-Down with structure exceeds the vector baseline by 4.7 percentage points in NDCG@10, while structural information can hurt queries that do not need context.
Problem
Vietnamese educational KG construction and systematic evaluation of retrieval strategies over hierarchical structures remain insufficiently addressed.
Method
The paper constructs a hierarchical KG with controlled ontology expansion and evaluates Top-Down, Horizontal, and Bottom-Up traversal on a synthetic Vietnamese benchmark.
Results
Top-Down with structure improves NDCG@10 by 4.7 percentage points over the vector baseline.
Takeaways & Limitations
Tree-structural information provides value beyond flat cosine similarity, but can degrade retrieval when structural context is unnecessary.
Takeaways & Limitations
The study is limited to high school history textbooks and a relatively small automatically constructed graph, and expert-annotated extraction and retrieval benchmarks remain important.
Abstract
from arXiv · showhide
Hierarchical Knowledge graph (KG)-based retrieval augmented generation (RAG) has emerged as a powerful approach for supporting large language models with structured knowledge. However, there are primary challenges: (i) the lack of methods for automatic KG construction using ontology expansion for low-resource languages such as Vietnamese, (ii) the absence of systematic evaluation for knowledge retrieval strategies leveraging the hierarchical structures. In this paper, we propose an end-to-end pipeline for KG construction and retrieval strategies evaluation. In the KG construction, we employ a three-phase hybrid relation extraction pipeline: intra-batch deduplication via Union-Find, approximate cross-batch search, and LLM extraction with a centroid filter that reduces prompts combined with a five-step dual-LLM validator to prevent bloated ontology. A two-tier architecture consists of unmergeable structural nodes to preserve the document structure and mergeable content nodes. The retrieval evaluation consists of three graph traversal strategies: Top-Down, Horizontal, and Bottom-Up, which are evaluated on a synthetically generated benchmark of 1,210 Vietnamese queries from 109 subgraphs, categorized by five query directions. In this paper, we construct the tree knowledge graph from Vietnamese high school History textbooks (nearly 400 pages) to produce 750 nodes and 4,341 semantic edges with controlled ontology growth from 40 to 41 types. Among experimental graph traversal strategies, the Top-Down strategy with structure surpasses the vector baseline by 4.7 percentage points in NDCG@10. As a result, tree-structural information provides valuable information beyond flat cosine similarity but degrades performance when the query does not require structural context.
1 Introduction
The paper addresses the lack of Vietnamese educational KG construction methods and compares hierarchical retrieval strategies. It proposes controlled ontology expansion, benchmark generation, and multi-directional graph traversal evaluation.
- History learning requires structured reasoning across events, people, dates, and causal chains rather than isolated keyword matching.
- The paper proposes hierarchical KG construction with controlled ontology expansion for Vietnamese educational content.
- The ontology uses 26 general and 14 history-specific relation types, while centroid filtering reduces prompts by 50%.
- A five-step dual-LLM validator prevents 87.5% of duplicate relations during ontology construction.
- The benchmark contains 1,210 Vietnamese queries from 109 subgraphs, categorized by five query directions and hierarchical relevance labels.
- Top-Down, Horizontal, and Bottom-Up traversal strategies are evaluated with 12 methods across four cutoff thresholds and five query directions.
2 Related Work
Prior work applies GraphRAG and LLM-based KG construction, but Vietnamese textbook KGs and systematic hierarchical retrieval comparisons remain underdeveloped. The paper targets controlled ontology growth and graded, direction-aware retrieval evaluation.
- GraphRAG follows relational paths for question answering, while existing systems use different traversal mechanisms over graphs and hierarchical structures.
- LLM-based document KG construction commonly combines embedding filtering with extraction, but rapid ontology expansion can create duplicate relation types.
- Educational KG studies compare construction directions and use LLMs to fill missing curriculum relations, but enrichment differs from construction.
- CRAG contains 4,409 question-answer pairs for flat-text and entity-level QA, but lacks graded relevance labels.
- The paper identifies three open challenges: controlled low-resource KG construction, graded direction-aware benchmarking, and traversal comparison on hierarchical Vietnamese textbook graphs.
3 Tree Knowledge Graph Construction using Ontology Expansion
The construction pipeline converts Vietnamese textbook documents into a hierarchical KG, enriches its structure, and extracts relations with filtering and controlled ontology expansion. Structural nodes preserve document organization while content nodes support semantic processing.
- Pipeline stages: The system has four construction stages: document parsing, knowledge-tree enrichment, embedding generation, and relation extraction.
- Pipeline stages: Document parsing creates unmergeable structural nodes and mergeable content nodes from PDF-derived hierarchical trees.
- Pipeline stages: Post-order traversal summarizes child content into structural nodes, and embeddings are then generated for graph nodes.
- Implementation: The resulting KG is stored in ArangoDB for benchmark generation and retrieval.
- Ontology design: The ontology begins with 40 relation types organized into 26 general and 14 history-specific types, allowing domain-specific replacement while retaining the general layer and pipeline.
- Relation extraction: Pre-filtering merges highly similar node pairs, sends intermediate similarities to LLM classification, and keeps low-similarity pairs separate.
- Relation extraction: Centroid scoring selects the top 15 relation types from 40 and reduces prompt size by nearly 50%.
- Relation extraction: A weak LLM classifies node pairs using filtered candidates, while dual-LLM validation addresses novel relations that duplicate existing types.
4 Graph Retrieval-Augmented Generation Strategies
The paper evaluates three graph traversal strategies for hierarchical Graph-RAG, combining semantic similarity with structural and relational information. Top-Down descends from structural nodes, Horizontal crosses semantic relation edges, and Bottom-Up aggregates evidence from content nodes to their parents.
- Three traversal strategies are evaluated: Top-Down, Horizontal, and Bottom-Up.Top-Down moves from structural nodes to content, Horizontal follows semantic relations, and Bottom-Up aggregates content evidence at parent nodes.
- Top-Down Strategy: Top-Down selects matching sections semantically, then collects content nodes throughout each section’s subtree.Its variants use cosine similarity, Reciprocal Rank Fusion, and optionally maximal marginal relevance for ranking.
- Horizontal Strategy: Horizontal traverses one-hop semantic edges between tree branches to connect information distributed across different sections.It ranks seed and extended content nodes using cosine similarity, RRF, or a restricted set of three relation types.
- Bottom-Up Strategy: Bottom-Up retrieves similar content nodes, follows inbound edges to their parents, and ranks parent nodes using child evidence.Only children scoring at least the parent-specific median threshold are selected for aggregation.
- Bottom-Up Strategy: Bottom-Up aggregation combines average child similarity with logarithmic scaling by the number of relevant children, while E3c additionally applies RRF.The logarithmic factor is intended to avoid explosion from dense parent nodes.
5 Benchmark Generation Pipeline
The benchmark pipeline converts selected knowledge-graph subgraphs into graded Vietnamese queries covering five information-seeking directions. It selects and bounds subgraphs, generates queries with an LLM, and applies multi-step quality control.
- The pipeline converts the constructed KG into a benchmark with graded relevance labels for five query directions.The benchmark is generated from the graph to evaluate the retrieval strategies.
- Fig. 3 reports 1,210 Vietnamese queries generated through SEED–ENRICH–BOUND subgraph selection, five query directions, and seven-step quality control.The figure caption describes the benchmark-generation stages and final query count.
- Three-Phase Subgraph Selection: SEED collects core content from a selected L5 node, while ENRICH adds one-hop cross-section content and associated parent and child nodes.ENRICH selects at most two sections ranked by the number of relations between content nodes.
- Three-Phase Subgraph Selection: BOUND filters relations among the collected core and enriched nodes to form a closed subgraph.
- Five Query Directions: The five directions are Neutral, Top-down, Horizontal, Bottom-up, and Cross-section, representing single-node, within-section, cross-section, summary-level, and comparison queries.
- Query Generation and Quality Control: Generated outputs include queries, relevant nodes, relevance levels, directions, and confidence scores, followed by seven-step verification and confidence-based spot checks.Verification checks node existence, relevance, duplicates, direction validity, and quota compliance.
6 Experiments and Results
The experiments evaluate a Vietnamese textbook benchmark and compare hierarchical retrieval strategies with lexical, vector, and hybrid baselines. Top-Down retrieval leads overall, while performance varies substantially by cutoff and query direction.
- Benchmark and evaluation: 1,210 Vietnamese queries were generated from 109 subgraphs and evaluated with three-level relevance labels using NDCG@K, Recall@K, Precision@K, and MRR.The benchmark contains 1,182 clean queries and 28 flagged queries; NDCG is the main metric at K = {1, 3, 5, 10}.
- Benchmark and evaluation: The graph contains 750 nodes and 5,372 edges, including 1,031 tree-structural edges and 4,341 semantic edges.Its structure includes 3 roots, 263 structural nodes, 484 content nodes, 15 chapters, 28 lessons, 109 sections, and 111 subsections.
- Overall retrieval ranking: TopDown RRF achieves NDCG@10 of 0.8397 and Recall@10 of 0.9053, improving over the B1 vector baseline by 4.7 and 8.7 percentage points, respectively.It outperforms the other retrieval methods for all reported metrics, while Bottom-Up E3c achieves the highest MRR at 0.9331.
- Overall retrieval ranking: Horizontal E2a outperforms B1 by 0.86 percentage points in NDCG, whereas E2b drops 6.7 percentage points relative to E2a.The reported drop is associated with overlapping information between seed and extended nodes introducing noise in RRF.
- Cutoff analysis: At K = 1, Bottom-Up obtains the highest score, but from K≥3 Top-Down leads as propagated seed scores improve coverage within the selected section.At K = 10, E1b exceeds B1 by 4.7 points; higher K extends recall while lowering NDCG@10 and Precision relative to K = 1.
- Strategy × query direction: Performance differs by query direction: E1b leads TD at 0.876 and BU at 0.878, E2a leads HZ at 0.861, and B3 leads NT at 0.962.For NT, E1b drops to 0.741 because structural traversal spreads results across irrelevant nodes; CS is the most challenging direction.
7 Discussions
The study reports promising Graph-RAG results for Vietnamese history textbooks while identifying important evaluation and scope limitations. Its evidence is limited to a relatively small textbook-derived graph and an automated benchmark.
- Limitations: The study was validated on high school history textbooks using an automated benchmark, resulting in a relatively small scale of nodes and relations.The authors identify expert-annotated benchmarks for extraction and retrieval evaluation as important for improving experimental consistency.
- Limitations: Hand-tuned thresholds may affect the performance of graph retrieval systems.The authors propose extending the pipeline to other domains and developing more efficient retrieval strategies for increasingly complex queries.