A Survey on Extractive Knowledge Graph Summarization: Applications, Approaches, Evaluation, and Future Directions

Xiaxia Wang, Gong Cheng

Abstract

With the continuous growth of large Knowledge Graphs (KGs), extractive KG summarization becomes a trending task. Aiming at distilling a compact subgraph with condensed information, it facilitates various downstream KG-based tasks. In this survey paper, we are among the first to provide a systematic overview of its applications and define a taxonomy for existing methods from its interdisciplinary studies. Future directions are also laid out based on our extensive and comparative review.

Introduction

As Knowledge Graphs (KGs) grow to massive scales, they become increasingly difficult for both humans to browse and machines to process efficiently. This survey provides the first systematic overview of extractive KG summarization—the art of distilling a large KG into a concise, representative subgraph that preserves the original data's meaning and structure for applications like search, query optimization, and data exploration.

An example of a Knowledge Graph containing entities, types, and relationships.

The Discovery Challenge

Knowledge Graphs like Wikidata or DBpedia contain billions of facts, but their sheer size and diversity create a "discovery challenge." A user looking for a specific dataset or a machine trying to optimize a query shouldn't have to process the entire graph to understand its contents.

While previous research often focused on "grouping-based" summarization (merging similar entities into "super-nodes"), this paper focuses on extractive summarization. The goal is to select an optimal subgraph (a "snippet") from the original KG. This approach ensures the summary is "faithfully represented"—it looks and acts exactly like the original KG, making it immediately compatible with existing tools and easily understood by humans.

Taxonomy of Methods

The authors categorize extractive summarization methods into a clear taxonomy based on whether the summary is "Static" (fixed for a given KG) or "Dynamic" (tailored to a specific user or query).

Taxonomy of extractive KG summarization methods.

Static Summarization

These methods aim to capture the "essence" of a KG regardless of the specific user context.

  • Pattern Coverage: These focus on representing the diversity of data. They range from simple counts of classes and properties to complex Entity Description Patterns (EDPs) and Link Patterns (LPs) that capture how entities are typically connected.
  • Answer Coverage: These use graph topology (like PageRank or indegree) or historical query logs to identify the most "central" or "frequently asked for" parts of the graph.

Dynamic Summarization

These methods are context-aware and generate summaries on-the-fly.

  • Query-Biased: When a user enters keywords (e.g., "Titanic," "US"), these methods find a compact, cohesive subgraph that connects those terms, often using combinatorial optimization techniques like the Group Steiner Tree problem.
  • Personalized: These tailor the summary to a specific "seed entity" of interest or a user's personal query history.

Key Insights and Ideas

  • The Granularity Trade-off: There is a fundamental tension between simplicity and accuracy. Summaries based on simple class/property counts are easy to compute but miss structural nuances. Higher-order patterns (like EDPs) provide better characterization but significantly increase computational complexity.
  • From Heuristics to Optimization: Early methods relied on simple "heuristics" (like picking nodes with the most edges). Modern approaches have shifted toward formal optimization problems (like Maximum Coverage or Steiner Trees) to ensure the summary is both representative and structurally cohesive.
  • The "Snippet" as a UI Element: The paper emphasizes that extractive summaries serve as "KG snippets" in search engines, allowing users to "preview" a dataset's content before committing to an expensive download or complex query.

Datasets and Infrastructure

While this is a survey paper, the authors highlight critical infrastructure used to evaluate these methods:

  • BANDAR: A recently published benchmark containing thousands of real-world KGs, specifically designed for evaluating KG snippet generation.
  • Wikidata: A primary example of a massive, multi-domain KG that necessitates these summarization techniques for practical reuse.

Key Results and Evaluation

The paper synthesizes a decade of research into a unified framework. Key findings include:

  • Structural Importance: Methods that consider the connections between entities (Link Patterns) consistently outperform those that treat entities as isolated points.
  • Efficiency vs. Quality: While Steiner Tree-based methods produce the most cohesive summaries, they are NP-hard. The field is currently focused on developing approximation algorithms (like PrunedCBA) that can handle million-scale KGs in real-time.
  • Evaluation Maturity: The field has moved beyond simple "coverage" metrics to "extrinsic evaluation"—testing if a summary actually helps a user write a SPARQL query faster or helps a machine optimize a federated join.

Future Directions

The authors identify several "blind spots" in current research:

  • The Neural Gap: Most current methods are symbolic and heuristic-based. There is a massive opportunity to apply Graph Neural Networks (GNNs) to learn what makes a "good" summary.
  • Generative Summarization: With the rise of Large Language Models (LLMs), the authors suggest exploring generative models that can describe KGs in natural language while remaining grounded in the extractive subgraph.
  • Supervised Learning: Most current tools are unsupervised because labeled "gold standard" summaries are hard to create. Developing semi-supervised or self-supervised pipelines is a high-priority future direction.

Summary updated

Abstract

With the continuous growth of large Knowledge Graphs (KGs), extractive KG summarization becomes a trending task. Aiming at distilling a compact subgraph with condensed information, it facilitates various downstream KG-based tasks. In this survey paper, we are among the first to provide a systematic overview of its applications and define a taxonomy for existing methods from its interdisciplinary studies. Future directions are also laid out based on our extensive and comparative review.
BibTeX
@inproceedings{wang2024survey,
  author = {Xiaxia Wang and Gong Cheng},
  title = {{A Survey on Extractive Knowledge Graph Summarization: Applications, Approaches, Evaluation, and Future Directions}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=vW8CVlu6Id},
}
Figure