💬 NLP

Semantic Centroids and Hierarchical Density-Based Clustering for Cross-Document Software Coreference Resolution

This paper presents a hybrid framework for cross-document software coreference resolution that integrates semantic embeddings, knowledge base lookups via FAISS, and HDBSCAN clustering to achieve high F1 scores across multiple shared task subtasks.

Original authors: Julia Matela, Frank Krüger

Published 2026-03-26

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Julia Matela, Frank Krüger

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a librarian trying to organize a massive, chaotic library where thousands of people have written notes about software. The problem? Everyone calls the same software by different names. One person writes "SPSS," another writes "Statistical Package for the Social Sciences," and a third writes "SPSS version 28." To a computer, these look like three completely different things. Your job is to figure out which notes belong to the same software and group them together. This is what the paper calls Cross-Document Coreference Resolution.

The authors, Julia and Frank, built a smart system to solve this puzzle for the "SOMD 2026" competition. Here is how their system works, explained through simple analogies.

1. The Problem: The "Name Game"

In scientific papers, software is mentioned in messy ways. Sometimes it's a full name, sometimes an acronym, and sometimes it's buried in a long sentence with extra details. If you just look at the words, a computer gets confused. It's like trying to find a friend named "Bob" in a crowd where some people call him "Bobby," others "Robert," and some just say "The guy in the red hat."

2. The Solution: A Three-Step Detective Pipeline

The authors created a three-stage detective team to sort through the notes.

Step 1: Giving Everyone a "Mental Portrait" (Semantic Embeddings)

First, the system needs to understand what the software is, not just what it's called.

The Analogy: Imagine taking a photo of every software mention. But instead of a regular photo, the system creates a "mental portrait" (a mathematical vector) that captures the essence of the software.
The Trick: The system knows that the name is the most important part. So, when it creates this portrait, it "doubles down" on the name. If the text says "SPSS," the system repeats "SPSS" in the mental portrait to make sure the name isn't drowned out by the surrounding boring text. This ensures the portrait focuses on the identity of the software.

Step 2: The "Wanted Poster" Database (Knowledge Base & FAISS)

Before looking at the new notes, the system studies the "Gold Standard" notes (the ones we know are correct) to build a Knowledge Base (KB).

The Analogy: Think of this as a "Wanted Poster" wall. For every known software (like "Python" or "R"), the system creates a perfect, average "Wanted Poster" (a centroid) based on all the correct notes it has seen so far.
The Speed Trick: When a new note comes in, the system doesn't look at every single poster one by one (which would take forever). Instead, it uses a super-fast search tool called FAISS. It's like a magical librarian who can instantly point to the most likely match on the wall based on how similar the mental portrait looks.
The Rules:
- If the name matches exactly (e.g., "SPSS" vs "SPSS"), it's a match.
- If the mental portrait is very similar (90%+ match), it's a match.
- If the name matches but the portrait is a bit fuzzy (maybe because of extra noise), the system gives it the benefit of the doubt and matches it anyway.

Step 3: The "Mystery Group" (HDBSCAN Clustering)

What happens if a new note doesn't match any of the "Wanted Posters"? Maybe it's a brand new software, or the name is so weird the system didn't recognize it.

The Analogy: These unmatched notes are sent to a "Mystery Group" room. Here, the system uses a technique called HDBSCAN.
How it works: Instead of forcing these notes into existing groups, the system looks for "clusters of density." Imagine dropping marbles on a table. If a bunch of marbles (notes) are huddled closely together, the system says, "Hey, these look like they belong to the same new software!" It groups them together. If a marble is all alone, it stays alone (an outlier).

3. Handling the "Mountain of Data" (Scalability)

For the hardest part of the competition (Subtask 3), the system had to sort 220,000 notes. If the system tried to compare every note to every other note, it would take years (like trying to shake hands with everyone in a stadium).

The Solution: The authors used a Blocking Strategy.
The Analogy: Instead of mixing everyone in one giant room, they put people into smaller rooms based on simple rules first.
- First, they separate people by "Job Type" (e.g., all "Applications" in one room, all "Plugins" in another).
- Then, within those rooms, they separate people by the first letter of their name (A-Z).
- Now, the system only has to compare people within their small, specific rooms. This makes the job 100 times faster.

4. The Results: A Master Librarian

The system worked incredibly well:

Task 1 (Clean Data): 98% accuracy.
Task 2 (Noisy Data): 98% accuracy.
Task 3 (Huge Data): 96% accuracy.

Even with a massive amount of data, the system ran in just over 2 minutes on a standard computer, proving that you don't need a supercomputer to solve this if you have a smart strategy.

The Big Takeaway

The paper shows that by combining smart math (to understand meaning), fast searching (to find known matches), and grouping logic (to find new patterns), we can automatically organize the chaotic world of software mentions.

The authors also noted an interesting twist: This isn't just about finding who "refers" to whom (like in a story); it's more like disambiguation. It's realizing that "SPSS," "Statistical Package," and "SPSS 28" are all just different masks for the same single software character. Their system successfully peeled back those masks to reveal the true identity of the software.

1. Problem Statement

The paper addresses the Cross-Document Coreference Resolution (CDCR) task for software mentions within scientific corpora. The goal is to cluster mentions from different documents that refer to the same underlying software entity.

Challenges: Software mentions are highly ambiguous (e.g., "SPSS" vs. "Statistical Package for the Social Sciences" vs. "SPSS 28"). Surface forms alone are insufficient for resolution.
Scale: The task involves three subtasks with increasing difficulty:
- Subtask 1: Gold-standard annotated mentions (clean data).
- Subtask 2: Automatically predicted mentions (introduces noise).
- Subtask 3: A massive scale test set (~220,000 mentions), requiring high computational efficiency and scalability.

2. Methodology

The authors propose a hybrid three-stage pipeline that combines semantic embeddings, Knowledge Base (KB) retrieval, and density-based clustering.

A. Semantic Representation & Context Construction

Context String Construction: To mitigate ambiguity, the system constructs a structured context string $c(m)$ $c (m)$ for each mention $m$ $m$ . This string concatenates:
1. The mention surface form (duplicated to increase its weight).
2. The entity type label (e.g., application, plugin).
3. Relational mentions from metadata.
Embedding Model: The context strings are encoded using all-MiniLM-L6-v2, a distilled 6-layer Sentence-BERT model.
- Weighting Strategy: The mention surface form is duplicated in the input string to counteract "semantic drift" caused by long metadata strings, ensuring the embedding remains anchored to the software name.
- Pooling: Token representations are aggregated via attention-mask-weighted mean pooling and L2-normalized to enable efficient inner-product search.

B. Knowledge Base (KB) Centroid Construction

Training Phase: For each gold cluster in the training set, a single centroid vector is computed by averaging the embeddings of all member mentions and re-normalizing. These centroids form a KB of known software identities.
Retrieval: During inference, test mentions are queried against these centroids using FAISS (Facebook AI Similarity Search) for efficient Inner Product (cosine) similarity search.

C. Assignment Strategy (Hybrid Matching)

Test mentions are processed through a hierarchical decision tree:

Exact String Match: If the canonicalized name exists in the KB dictionary (applied primarily in Subtask 3), the mention is assigned immediately.
High-Confidence Semantic Match: If the cosine similarity to the closest KB centroid exceeds a threshold ( $\theta = 0.7$ ), the mention is assigned to that cluster.
Medium-Confidence String-Corroborated Match: If similarity is between 0.5 and 0.7, but the canonical name exists in the KB, the mention is assigned to the existing cluster (handling cases where context noise lowers embedding similarity).
Unmatched Flagging: Mentions failing the above criteria are passed to the clustering stage.

D. Clustering Unmatched Mentions

Algorithm: HDBSCAN (Hierarchical Density-Based Spatial Clustering of Applications with Noise) is used. It does not require a pre-specified number of clusters and handles outliers by assigning them to singleton clusters.
Scalability Blocking (Subtask 3): To handle the $O(n^2)$ $O (n^{2})$ complexity of distance matrix computation, a blocking strategy is employed:
- Mentions are first partitioned by entity type.
- Large blocks (>20,000 mentions) are further split by the first letter of the canonical name.
- HDBSCAN is run independently on these smaller blocks.
Post-Processing: Mentions sharing the same canonical name are merged into a single cluster regardless of HDBSCAN's output, ensuring consistency.

3. Key Contributions

Hybrid Framework: The integration of dense semantic embeddings with a KB centroid retrieval strategy and density-based clustering effectively balances precision (via KB matching) and recall (via HDBSCAN for unseen entities).
Context-Aware Embeddings: The specific technique of duplicating the surface form token within the context string significantly improves the quality of the semantic representation for coreference tasks.
Scalable Architecture: The implementation of a hierarchical blocking strategy allows the system to process over 200,000 mentions (Subtask 3) without GPU acceleration, overcoming the typical scalability bottlenecks of density-based clustering.
Normalization Pipeline: Robust handling of abbreviations and surface-form variations through canonicalization and abbreviation mapping.

4. Results

The system achieved state-of-the-art performance across all subtasks, measured by CoNLL F1 scores:

Subtask 1: 0.98 (Gold-standard data).
Subtask 2: 0.98 (Noisy, auto-extracted data).
Subtask 3: 0.96 (Large-scale data).

Performance Analysis:

Performance remained high despite the noise in Subtask 2 and the scale of Subtask 3.
Scalability: The pipeline demonstrated near-linear scaling for embedding and retrieval stages. The HDBSCAN stage showed non-monotonic behavior due to the blocking strategy (where a single oversized block can dominate runtime), but the overall system completed the 220k mention task in approximately 129 seconds.

5. Significance

Entity Disambiguation vs. Coreference: The authors note that the task behaves more like entity disambiguation (one surface form $\to$ one entity) than classical coreference (one entity $\to$ many surface forms), suggesting future models should leverage this asymmetry.
Efficiency: The system proves that high-accuracy CDCR for software can be achieved on standard CPU hardware using efficient blocking and lightweight transformer models, making it viable for large-scale scientific knowledge graph construction.
Reproducibility: The full pipeline code is publicly available, facilitating further research in software mention detection and resolution.