Abstract
In large-scale Knowledge Graphs, relationship queries often return empty results when the queried entities exceed a predefined diameter constraint. This paper introduces a query relaxation framework that identifies the largest possible subset of entities—a maximum sub-query—that maintains a compact semantic association. By transforming the subgraph search into a distance-based optimization problem centered around "certificate" nodes, the proposed CertQR+ algorithm achieves significant performance gains over traditional Steiner Tree-based methods.
Introduction
Knowledge Graphs (KGs) such as DBpedia and LinkedMDB serve as rich repositories of semantic information. A common task is finding "Semantic Associations" (SAs)—compact subgraphs that explain the relationships between a set of entities. To ensure these subgraphs are meaningful and computationally manageable, researchers typically impose a diameter constraint ($D$).
However, real-world data often fails to meet strict constraints. If even one entity in a query is distant from the others, the search returns no results. Simply increasing the diameter constraint is often unfeasible; it leads to the "hairball" problem, where results become too noisy, and computational complexity explodes due to the NP-hard nature of finding Steiner Trees.
Methodology: Query Relaxation and Certificates
Instead of relaxing the diameter constraint, the authors propose query relaxation. If the entire set of entities cannot be connected within distance $D$, the system identifies the largest subset (the maximum sub-query) that can.
The Certificate Technique
The core innovation is the "certificate" concept. The authors prove that a relationship exists if there is a "certificate" entity $c$ acting as a central hub. If every entity in the sub-query is within a distance of $\lceil D/2 \rceil$ from $c$ (with specific conditions for odd diameters), a valid SA exists. This shifts the computational burden from complex tree construction to a more efficient "center-point" search.
Algorithms
The paper introduces two primary algorithms:
- CertQR: A baseline BFS-based approach that explores potential certificates from all query entities.
- CertQR+: An optimized best-first search algorithm. It utilizes a priority queue and an estimation function to prioritize paths likely to yield the maximum sub-query.
To further enhance performance, the authors employ "Degree-enhanced" and "Distance-enhanced" heuristics. These help the search prioritize nodes with lower degrees (reducing branching) or those closer to potential certificates.
Experimental Evaluation
The approach was tested on three RDF datasets: DBpedia (5.3M vertices), LinkedMDB (1.3M vertices), and Mondial (8.4K vertices).
Key Results
- Efficiency: CertQR+ outperformed traditional baselines by orders of magnitude. Queries that previously timed out or took hundreds of seconds were resolved in under one second.
- Pruning: On DBpedia, CertQR+ processed only a tiny fraction of the graph compared to exhaustive search, validating the distance-based estimation strategy.
- Sub-query Stability: Experiments showed that for 82% of failing queries on DBpedia, removing just one entity allowed for a successful, compact relationship. This justifies the "relax the query, not the constraint" philosophy.
Conclusion
This research demonstrates that query relaxation is a viable and efficient alternative to relaxing diameter constraints in graph searches. By focusing on "certificates," the CertQR+ algorithm maintains scalability even on massive datasets. Future work includes handling dynamic graphs where distance oracles must be updated frequently and incorporating user-defined weights to prioritize "mandatory" entities in a query.
Summary updated