PaperlayerView exact revision on arXiv

Source-linked AI summary

Enabling Knowledge Graph Understanding at Scale with the EXplore Your Graphs ENgine (EXYGEN)

Harshdeep Singh, Yurui Zhu, Giovanni Colavizza, Matteo Romanello

arXiv:2609.11569v1cs.AIcs.LG

TL;DR

EXYGEN addresses KGQA’s dependence on KG-specific supervision and the scalability limits of metadata generation. It combines structured KG context with retrieval-augmented text-to-SPARQL generation, then uses predicate-coverage-aware sampling to scale metadata construction. The approach reaches EMRelEx = 0.419 without fine-tuning, while sampling reduces runtime by over 80× on large graphs but remains limited by exemplar dependence and evaluation scope.

  • Problem

    EXYGEN addresses dependence on costly KG-specific supervision and the limited scalability of metadata generation for LLM-based KGQA.

  • Method

    The framework integrates VoID, ShEx, retrieved triples, and question-query exemplars in a RAG pipeline, and uses predicate-coverage-aware parallel graph sampling for metadata generation.

  • Results

    DeepSeek-V3.1 reaches EMRelEx = 0.419 without fine-tuning, while predicate-coverage-aware sampling cuts metadata-generation time by over 80× on GESIS and OpenCitations Meta.

  • Takeaways & Limitations

    Structured schema context and lightweight prompting can reduce reliance on fine-tuning for scalable conversational KG access, while sampling is necessary for schema-rich graphs such as ORKG.

  • Takeaways & Limitations

    The approach depends on curated question-query exemplars, assumes descriptive labels for retrieval, and has not been validated beyond SciQA and three KGs.

Abstract

from arXiv · show

We present EXYGEN (EXplore Your Graphs ENgine), a framework for knowledge graph (KG) understanding that enables conversational access to KGs at scale. We address two questions in sequence. First, how effectively can LLMs perform text-to-SPARQL generation given only automatically derived structured metadata and small graph samples, rather than task-specific fine-tuning? We integrate VoID descriptions and ShEx schemas into a retrieval-augmented generation (RAG) pipeline and ablate KG-derived context on the SciQA benchmark. Our best configuration -- combining ShEx schemas, retrieved triples, and example question-query pairs -- reaches an exact match of 0.419 on execution results without any LLM fine-tuning. We further find that lexical metrics such as F1 poorly predict query correctness, and that larger general-purpose LLMs can outperform smaller code-specialized ones once given sufficient context. Second, we ask how to generate the structured metadata that this method relies on from very large KGs, where KG metadata generation becomes computationally intractable. We introduce a predicate-coverage-aware parallel graph sampling strategy that preserves structural diversity while remaining computationally tractable. On OpenCitations Meta and GESIS, it retains high predicate coverage with minimal triple loss and reduces runtime by over 80x; on ORKG, sampling is not just faster but the only tractable path to obtain complete metadata. Together, these results show that structured schema context and lightweight prompting can substantially reduce reliance on fine-tuning for scalable conversational access to KGs, though closing the remaining gap to fully fine-tuned approaches will likely require reducing dependence on curated question-query exemplars -- whether through synthetic generation or an execution-feedback-driven approach -- and validating these findings beyond a single benchmark.

1. Introduction

The paper addresses two limitations of LLM-based KGQA: dependence on KG-specific supervision and the poor scalability of metadata generation. It proposes testing KG-derived context for fine-tuning-free text-to-SPARQL generation and developing scalable metadata generation through graph sampling.

  • 1. Introduction: EXYGEN targets KGQA methods that depend on costly KG-specific supervision and metadata generation that becomes computationally prohibitive at scale.These limitations motivate the paper’s two research questions: whether automatically derived context can replace task-specific fine-tuning, and how the required metadata can be generated efficiently.
  • 1. Introduction: VoID and ShEx provide structured, class-specific schema constraints for the LLM without requiring task-specific supervision.VoID describes dataset statistics, while ShEx expresses them as concise shape definitions.
  • 1. Introduction: The first research question tests whether existing LLMs can generate text-to-SPARQL queries without task-specific fine-tuning from automatically extracted KG-derived context.The context includes endpoint metadata, retrieved triples, and example question-query pairs.
  • 1. Introduction: The paper contributes an ablation study of VoID, ShEx, retrieved triples, and few-shot question-query pairs in a RAG pipeline benchmarked with open-weight LLMs on SciQA.This evaluates how different forms of KG-derived context affect fine-tuning-free text-to-SPARQL generation.
  • 1. Introduction: The second contribution is a predicate-coverage-aware parallel graph sampling strategy for generating VoID and ShEx metadata beyond existing scalability limits.The strategy is designed for knowledge graphs whose size makes conventional metadata generation infeasible.

2. Related work

Related work covers LLM-based KGQA and graph sampling, positioning EXYGEN’s fine-tuning-free text-to-SPARQL method alongside supervised approaches and structural sampling techniques. Prior sampling research evaluates methods by how well they preserve graph properties while reducing analysis costs.

  • KG question answering: Earlier KGQA systems translated natural-language questions into SPARQL through engineered pipelines involving entity linking, relation detection, and template-based query construction.These systems were effective on established encyclopedic graphs but struggled to generalize.
  • KG question answering: LLM-based KGQA has divided into KG-specific fine-tuning and more flexible approaches for generating SPARQL from natural language.Prior systems include fine-tuned models for specialized domains and methods using execution-based rewards for query construction and correction.
  • Graph sampling: Graph sampling methods are evaluated by whether they preserve structural properties such as degree distributions, connected components, hop plots, and clustering coefficients.This evaluation framework supports comparing sampling strategies beyond runtime alone.
  • Graph sampling: Some prior evidence suggests that sampling 15% of an original graph can faithfully represent its macro-level structure.This result concerns macro-level representation rather than the metadata-generation setting studied by EXYGEN.
  • Graph sampling: Random-walk sampling is computationally tractable and sensitive to local connectivity but can be biased toward densely connected regions.Metropolis-Hastings methods address this by accepting or rejecting transitions to optimize sampling behavior.
  • Graph sampling: Hypergraph-based sampling extends sampling to higher-order relational structures through a degree-biased strategy parameterized by α.Higher α values favor high-degree nodes assumed to contribute disproportionately to structural coherence.

3. Data

The paper evaluates its KGQA method on SciQA and its metadata-generation strategy on three knowledge graphs with different sizes and schema structures. OpenCitations Meta and GESIS have comparatively flat bibliographic schemas, whereas ORKG has a fine-grained ontology with many class–predicate combinations.

  • 3. Data: The data section links SciQA to evaluation of context-based text-to-SPARQL generation and the three large graphs to evaluation of metadata-generation sampling.The two datasets support the paper’s two research questions.
  • 3.1. SciQA: SciQA contains 2,565 natural-language question-SPARQL query pairs grounded in ORKG, divided into training, validation, and test sets.The splits contain 1,795 training pairs, 257 validation pairs, and 513 test pairs.
  • 3.1. SciQA: SciQA combines handcrafted and automatically generated question-query pairs and targets a multilingual, domain-specific KG less likely to appear in LLM pretraining data.Answers are retrieved from ORKG through a Virtuoso SPARQL endpoint.
  • 3.2. Large-scale knowledge graphs: The scalability experiments use OpenCitations Meta, GESIS, and ORKG, containing 4.94 billion, 97.52 million, and 1.13 million triples, respectively.These graphs provide substantially different scales for testing metadata-generation methods.
  • 3.2. Large-scale knowledge graphs: OpenCitations Meta and GESIS have comparatively flat bibliographic schemas, while ORKG encodes a fine-grained ontology of research contributions, comparisons, and scholarly claims.ORKG therefore has a much larger space of class–predicate combinations relative to its triple count.

4. Text-to-SPARQL Generation with KG-Derived Contexts

EXYGEN combines automatically generated VoID and ShEx metadata with retrieved triples and question-query examples in a RAG pipeline for fine-tuning-free text-to-SPARQL generation. On SciQA, richer context—especially ShEx plus QQP and additional sources—substantially improves executable and exact query results, while F1 can misrepresent correctness.

  • 4.1. Creation of VoID description: EXYGEN generates VoID and ShEx artifacts from KGs, indexes them for semantic retrieval, and supplies retrieved context to an LLM before SPARQL generation and execution.Large graphs can use representative sampling instead of full traversal.
  • 4.2. Extraction of ShEx schema: ShEx schemas provide class-specific constraints for SPARQL generation after VoID statistics are converted into shape definitions.The conversion derives property value types and cardinalities from VoID statistics.
  • 4.5. Results & Error Analysis: 0 Exact Match (Relaxed) is obtained for all models in NoCtx, VoID, ShEx, and Retrieved Triples, except DeepSeek with QQP, which reaches 50/513 ≈0.097.High executability in some isolated-context settings therefore does not guarantee correct results.
  • 4.5. Results & Error Analysis: 0.419 EMRelEx is achieved by DeepSeek with VoID+ShEx+Retrieved triples+QQP, the best result in the table by a wide margin.This configuration combines ShEx with multiple context sources and records zero prefix mismatches.
  • 4.5. Results & Error Analysis: 0.000, 0.001, and 0.000 executability occur for Qwen2.5-3B, Qwen3-30B, and DeepSeek when VoID+Retrieved triples+QQP omits ShEx.The same configurations show PrefMis values of 0.980, 0.988, and 0.869, respectively.

5. Scaling Metadata Generation to Large Knowledge Graphs

EXYGEN scales structured metadata generation by sampling large knowledge graphs with predicate-aware parallel walks, preserving coverage while reducing computational cost. Across graphs, sampling offers strong efficiency gains and is the only viable route for complete metadata generation on ORKG.

  • Sampling Results: Semantic similarity achieves GESIS’s highest predicate coverage of 57.86% and lowest missing-triple rate of 0.42%, but with substantially higher runtime.The comparison is reported in the representative sampling results table.
  • Sampling Results: OpenCitations Meta reaches 76.64% predicate coverage with 0.0049% missing triples, and semantic similarity below 0.6 achieves this in 2.41 minutes.Multiple configurations attain the same near-optimal coverage, while omitted predicates are mainly administrative or ontological.
  • Sampling Strategy: Two-hop parallel walks with per-hop pruning provide the best trade-off, while degree-based selection adds overhead and semantic similarity improves representativeness at embedding cost.The strategy parallelizes walks across multiple start nodes and trades runtime against coverage through predicate-aware sampling.
  • Full Graph vs. Sampled Metadata Generation: Over 80× faster metadata generation is achieved for GESIS, while OpenCitations Meta falls from 64 minutes to 11 seconds using sampled subgraphs.GESIS drops from roughly 19 minutes to under 14 seconds; OCM uses 331 of 604 full-graph queries.
  • Full Graph vs. Sampled Metadata Generation: ORKG requires an estimated 18 million full-graph queries and is the only case where sampling is the sole viable path to complete metadata.Its schema complexity drives query volume, requiring an 18% representative sample and 43 minutes for sampled generation.
  • Full Graph vs. Sampled Metadata Generation: Sampling is calibrated to predicate-coverage targets, enabling complete and consistent VoID and ShEx descriptors for each target graph rather than best-effort incomplete metadata.This distinguishes the approach from strategies that tolerate incomplete metadata across endpoint collections.

6. Conclusions and future work

EXYGEN combines KG-grounded context for fine-tuning-free text-to-SPARQL generation with predicate-coverage-aware sampling for scalable metadata generation. The results show strong execution-based performance and major runtime reductions, while retaining limitations around exemplars, URI semantics, downstream validation, and evaluation scope.

  • EMRelEx = 0.419 is achieved by DeepSeek-V3.1 with metadata, retrieved triples, and few-shot exemplars, while ShEx alone yields execution rates above 0.97 for larger models.Without exemplars, no context configuration produces a correct result; removing ShEx collapses executability.
  • Over 80× runtime reduction is achieved on GESIS and OpenCitations Meta reaches 11 seconds from 64 minutes, with most predicates covered and negligible triple loss.ORKG remains infeasible for full-graph metadata generation because its fine-grained ontology would require an estimated 18 million queries.
  • EXYGEN extends practical metadata generation across million- to billion-triple knowledge graphs through support for several triple-store backends.
  • The approach remains dependent on curated exemplars, assumes descriptive property and class labels, and has not established how sampled metadata affects downstream accuracy or generalizes beyond SciQA and three KGs.Future work includes broader validation and execution-feedback-driven query refinement.

Declaration on Generative AI

The authors disclose using Claude during preparation to paraphrase, reword, and check grammar and spelling. They state that assisted content was reviewed and verified by the authors.

  • Claude was used for paraphrasing, rewording, writing-style improvement, and grammar and spelling checks.
  • The authors reviewed, edited, and verified all AI-assisted content and retained responsibility for its accuracy, originality, and final form.
Loading 2609.11569v1…