Scaling Knowledge Graph Alignment to Millions of Entities

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2106 papers139 conceptsfrozen 2026-10-04

Knowledge graphs (KGs) and ontologies are the backbone of the Semantic Web, but they are often developed in isolation. To create a unified web of data, we must perform entity alignment: identifying when two nodes in different graphs represent the same real-world object.

While matching a few hundred concepts is trivial, modern datasets like SNOMED CT or the integration of Wikipedia with IMDb involve millions of entities. At this scale, traditional algorithms hit a "scalability wall." If you compare every entity in Graph A to every entity in Graph B, the computational complexity is $O(N^2)$. For a million entities, that is a trillion comparisons—a task that leads to the memory exhaustion and execution timeouts frequently cited in the Ontology Alignment Evaluation Initiative (OAEI) reports.

To bridge this gap, researchers have moved away from exhaustive matching toward strategies that intelligently prune the search space and partition the workload.

Pruning the Search Space via Candidate Selection

The most effective way to avoid $O(N^2)$ complexity is to ensure that we only compare entities that have a high probability of matching. This is known as candidate selection or blocking.

Sammy Khalife demonstrates a two-step approach where a fast Information Retrieval (IR) filtering step precedes the expensive graph-based identification. By using lightweight lexical indexes to find potential matches first, the system can ignore 99% of the graph, allowing complex graph kernels to run only on a tiny, relevant subset. Similarly, Runze Fang and the creators of the MIFEA framework use BERT-based semantic analysis to narrow down candidates before applying Graph Convolutional Networks (GCNs) for structural refinement.

Structural Partitioning and Block Updates

Even with good candidates, the structural dependencies in a graph—where the match of a "Parent" node depends on the matches of its "Children"—often require iterative updates that are slow to converge.

Uthayasanker Thayasivam and Prashant Doshi addressed this by introducing Block-Coordinate Descent (BCD) to the alignment process. Instead of updating the entire similarity matrix at once, BCD breaks the problem into smaller "blocks" based on the hierarchy of the ontology (such as the "height" of nodes). By optimizing one block at a time, their system, Optima+, reduced runtimes on complex biomedical datasets from 15 hours to just 23 minutes without losing accuracy.

This "divide-and-conquer" philosophy is also central to Falcon-AO, developed by Wei Hu and colleagues. By partitioning massive hierarchies into manageable sub-graphs, they allow automated tools to process datasets that would otherwise exceed the heap memory of standard hardware.

Greedy Propagation and Structural Reconciliation

Once a few "anchor" matches are found (often through literal string matching), the alignment can be propagated through the graph structure. The intuition is simple: if two nodes are the same, their neighbors are likely the same too.

The SiGMa algorithm, proposed by Simon Lacoste-Julien and his team, leverages this through a "simple greedy matching" approach. Rather than solving a global optimization problem, SiGMa picks the best match in the current frontier and propagates the similarity to adjacent nodes. This local, iterative strategy allows it to align KBs with millions of entities 50x faster than previous methods.

However, structural noise—where one graph is more detailed than another—can lead to errors. Yixin Cao and Zhiyuan Liu developed MuGNN to handle this. Their multi-channel GNN performs "cross-KG pruning," which identifies and ignores structural differences that don't contribute to alignment, ensuring that the propagation doesn't get derailed by inconsistent data modeling.

Maintaining Logic at Scale

As the scale increases, the risk of creating logically inconsistent mappings (e.g., mapping a "Doctor" to a "Hospital") grows. Ernesto Jiménez-Ruiz and Yujiao Zhou tackled this with LogMap 2.0.

LogMap uses "on-the-fly" reasoning to check for logical conflicts as mappings are generated. By integrating an efficient consistency checker directly into the alignment loop, it can process massive clinical frameworks like SNOMED and NCI while ensuring the resulting unified graph remains mathematically sound. This move toward interactive matching—where the system can also ask a human expert to resolve ambiguous high-impact mappings—represents the current frontier in making large-scale alignment robust enough for industrial use.

Papers in this version

Showing 60 of 106 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 95 papers
  2. Version 1 · 2026-10-04 · 106 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_large_scale_ontology_alignment_7b58d87e,
  title = {large-scale ontology alignment},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/large-scale-ontology-alignment/rdr_7b58d87e66cd4186987849d1ac35354d},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_scaling_knowledge_graph_alignment_to_mil_7b58d87e_v1,
  title = {Scaling Knowledge Graph Alignment to Millions of Entities},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/scaling-knowledge-graph-alignment-to-millions-of-entities/rdr_7b58d87e66cd4186987849d1ac35354d/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}