BiG-index: Scaling Massive Graph Searches via Semantic Hierarchies

TL;DR

Keyword search on massive knowledge graphs is notoriously slow due to structural complexity and scale. BiG-index breaks this bottleneck by using ontologies to "simplify" graph labels and bisimulation to "compress" the graph structure. It is a generic framework that acts as a turbocharger for existing algorithms like Blinks and r-clique, slashing query times by up to 50% without losing result accuracy.

Background: The Scalability Wall

Knowledge graphs like YAGO and DBpedia contain millions of entities and tens of millions of facts. Traditional keyword search algorithms (which find the minimal subtrees or clusters connecting keywords) often perform redundant computations. For example, if a query looks for researchers at a university, the algorithm might separately explore "Harvard," "Stanford," and "MIT" subgraphs, even if their internal structures are nearly identical.

The authors' core insight: Why search a massive, granular graph when you can search a compact, generalized version?

Methodology: Summarization through "Generalization"

BiG-index builds a hierarchy of summary graphs. The process involves two alternating steps:

1. Label Generalization: Using an ontology (e.g., "Harvard" $\to$ "University"), node labels are replaced with higher-level types.
2. Structural Summarization: Nodes with the same generalized labels and the same "neighbor structure" are collapsed into a single "supernode" using Backward Bisimulation.

The Cost Model

Summarization isn't free. If you generalize too much (e.g., everything $\to$ "Thing"), you get a tiny graph, but every query will return "false positives" that need expensive filtering. BiG-index uses a cost model to find the "sweet spot": $extcost(G,C)=\alpha imesextcompress(G,C)+(1-\alpha )imesextdistort(G,C)$ This balances the storage/speed benefits of compression against the "distortion" (the effort to distinguish specialized nodes later).

Querying the Hierarchy

When a user inputs keywords, BiG-index:

1. Generalizes the keywords to an optimal layer in the hierarchy.
2. Runs the search algorithm (e.g., Blinks) on the smaller summary graph.
3. Specializes the results: It maps the summarized paths back to the original data graph.

To avoid the "re-exploration" problem during specialization, the authors propose a Path-Based Answer Generation (Algorithm 4). Instead of verifying individual nodes, it verifies entire paths between "joint vertices" (nodes with high connectivity), significantly reducing intermediate partial answers.

Experimental Battlecard

The authors tested BiG-index on YAGO3, DBpedia, and IMDB.

• Blinks Optimization: On YAGO3, query time dropped by ~61.8%.
• r-clique Optimization: On DBpedia, query time improved by ~19.6%.
• Size: The index fits in memory much more easily than the full graph; YAGO3's first layer is only ~28% of the original size.

Critical Insight: Beyond Structural Compression

The brilliance of BiG-index lies in its orthogonality. It doesn't propose a new "search algorithm"; it proposes a better "search space." By utilizing the path-preserving nature of bisimulation, it ensures that if a path exists in the original graph, a representative exists in the summary. This makes it a "drop-in" performance booster for any existing keyword search logic.

Limitations & Future Work

While powerful, the framework's efficiency depends on the quality of the ontology. If the data graph and ontology have low overlap (as seen with DBpedia and the YAGO ontology), the compression gains are less dramatic. Future research could explore automated ontology induction—learning the hierarchy directly from the data when a schema isn't provided.

Conclusion

BiG-index represents a significant step forward in graph indexing. By marrying the semantic wisdom of ontologies with the mathematical rigor of bisimulation, it provides a scalable, generic solution for the "large graph keyword search" problem. For engineers building search layers over RDF or social networks, this hierarchical approach is the new gold standard.