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
Knowledge Graphs (KGs) such as Wikidata, DBpedia, and YAGO have become foundational for modern AI applications. However, their massive scale—often encompassing billions of facts—presents significant challenges. For humans, these graphs are "black boxes" that are difficult to explore or understand without prior knowledge. For machines, the sheer volume of data creates bottlenecks in query optimization and model training.
Extractive KG summarization addresses these issues by distilling a large KG into a concise, representative subgraph. Unlike "grouping-based" methods that merge nodes into abstract "super-nodes," extractive summarization selects an optimal subset of the original graph. This ensures the resulting "graph snippet" remains a valid graph, immediately compatible with existing software and intuitive for human interpretation.
A Taxonomy of Extractive Summarization
The survey introduces a comprehensive taxonomy of extractive methods, broadly divided into two categories: static (context-independent) and dynamic (user-biased).
Static Summarization
Static methods aim to capture the intrinsic characteristics of a KG regardless of a specific user query.
- Pattern Coverage: These algorithms identify representative data patterns. They range from simple class/property counts to complex Entity Description Patterns (EDPs) and Link Patterns (LPs) that describe how types of entities typically interact.
- Answer Coverage: These methods predict which parts of the graph are most likely to be queried. Approaches use graph topology (such as PageRank or Centrality) or analyze historical Query Logs to prioritize "popular" edges and nodes.
Dynamic Summarization
Dynamic methods are customized based on a user’s immediate information needs.
- Query-Biased: When a user enters keywords, these methods find a cohesive subgraph connecting those terms. The paper highlights the use of Group Steiner Tree (GST) algorithms, which aim to find the minimum-weight tree that connects all query keywords.
- Personalized: These tailor the summary to a user's long-term interests or specific "seed entities," often using spreading activation or random walks to find related content.
Key Insights and Applications
A central theme in the survey is the trade-off between expressivity and complexity. While higher-order structural patterns (like EDPs) provide more accurate summaries, they significantly increase computational cost. Furthermore, a high-quality summary must be cohesive—it should not just be a collection of "important" nodes, but a semantically connected subgraph.
Extractive summaries serve as "graph snippets," analogous to text snippets in web search. They have proven effective in several areas:
- Query Optimization: Improving the efficiency of federated KG queries by providing accurate join cardinality estimations using only a fraction of the original data.
- User Comprehension: Helping researchers understand unfamiliar KGs faster and complete complex SPARQL queries more accurately than when using raw metadata alone.
Future Directions
The authors identify several critical gaps in the current state-of-the-art:
- The Neural Gap: Most current methods rely on symbolic logic. There is a significant opportunity to apply Graph Neural Networks (GNNs) to learn what constitutes a "good" summary.
- Lack of Supervision: Most summarization is unsupervised. Semi-supervised learning using a small amount of labeled "gold standard" summaries could bridge the quality gap.
- Generative Summarization: Beyond extraction, future work could use Large Language Models (LLMs) to generate natural language descriptions or hybrid representations of KGs.
- Collaborative Extraction: Systems could learn to assemble new summaries from previously stored snippets for similar tasks, rather than summarizing from scratch.
Conclusion
Extractive KG summarization is a vital tool for making large-scale knowledge graphs accessible and efficient. By providing a systematic taxonomy and identifying key research frontiers, this survey lays the groundwork for the next generation of graph distillation techniques.
Summary updated