Incremental Graph Construction Enables Robust Spectral Clustering of Texts

This paper introduces an incremental $k$-NN graph construction method that guarantees connectivity by design, thereby enabling robust spectral clustering of text embeddings that outperforms standard approaches in low-$k$ regimes where disconnected components typically degrade performance.

The Gist

Imagine you are organizing a massive library of books, but instead of reading the titles, you only have a vague "feeling" of what each book is about. You want to group similar books together on shelves. This is essentially what spectral clustering does with text: it tries to sort documents into topics based on how similar they feel to each other.

To do this, computers build a map (a graph) where every book is a dot, and lines connect dots that are similar. The problem? The standard way of drawing these lines often leaves some books stranded on isolated islands, completely cut off from the rest of the library. If a book is on an island, the computer can't figure out which shelf it belongs to, and the whole sorting system breaks down.

Here is a simple breakdown of the paper's solution, using some everyday analogies.

The Problem: The "Island" Effect

The researchers looked at how computers usually build these maps. They use a rule called k-NN (k-Nearest Neighbors). Think of it like this:

• The Rule: "Every book must be connected to its 5 closest neighbors."
• The Flaw: In a huge, messy library, if you only look at the 5 closest books, you might miss a bridge to the next section.
• The Result: You end up with a map full of disconnected islands. Some books are in a group of 10, others in a group of 50, and some are alone. If the computer tries to sort these islands, it fails because it can't see the big picture. To fix this, you usually have to increase the number of neighbors (say, connect to 50 books), but that makes the map so crowded and heavy that the computer gets slow and confused.

The Solution: The "One-by-One" Builder

The authors propose a new way to build the map, which they call Incremental Graph Construction.

Imagine you are building a bridge across a river, but you can only lay one plank at a time, and you can only connect to the planks you've already laid down.

1. Start Small: You place the first few planks (books) down.
2. Add One by One: You bring in the next book. Instead of looking at every book in the library to find its friends, you only look at the books already on the bridge.
3. Connect Immediately: You tie the new book to its k closest friends among the ones already there.
4. The Magic: Because every new book must connect to the existing group, you can never create an island. The bridge grows continuously, ensuring everyone is connected to the main path.

Why This Matters

• No More Islands: Even if you only connect to 2 or 3 neighbors (a very sparse, fast map), the graph is guaranteed to be one single, connected piece.
• Speed: It's much faster to build. You don't have to scan the whole library every time; you just look at what's already there.
• Better Sorting: When they tested this on real text data (like news articles and scientific papers), their method sorted the documents much better than the old method, especially when using small numbers of connections.

The "Surprise" Finding

The researchers also tested adding a "safety net" called a Minimum Spanning Tree (MST). In the old days, experts thought you needed this complex safety net to ensure everything was connected.

• The Result: They found that their simple "one-by-one" building method worked just as well, or even better, without the safety net. Adding the extra complexity actually made the sorting slightly worse in some cases. It turns out, sometimes the simplest path is the best one.

The Takeaway

This paper introduces a clever, simple trick for organizing data. Instead of trying to see the whole picture at once (which leads to broken maps), they build the map step-by-step, ensuring that every new piece of information is immediately linked to the whole.

In short: They found a way to organize a chaotic library so that no book is ever left alone on an island, using a method that is faster, simpler, and more robust than the traditional approach.

Technical Summary

Here is a detailed technical summary of the paper "Incremental Graph Construction Enables Robust Spectral Clustering of Texts."

1. Problem Statement

The paper addresses a fundamental fragility in spectral clustering when applied to text embeddings. Spectral clustering relies on constructing a neighborhood graph (typically a $k$-Nearest Neighbor or $k$-NN graph) where nodes represent documents and edges represent similarity.

• The Disconnection Issue: Standard $k$-NN graphs constructed on realistic, high-dimensional text datasets often result in disconnected components (isolated subgraphs) when using practical sparsity levels (small $k$).
• Theoretical Limit: Theoretical analysis suggests that for a graph of $N$ points to be connected with high probability, $k$ must be at least $\approx 5.1774 \cdot \log N$. For a dataset of only 300 points, this requires $k > 30$, which is far higher than typical values used in practice.
• Consequences: In spectral clustering, each connected component can only be assigned to a single cluster. If the number of disconnected components equals or exceeds the desired number of clusters, the algorithm degenerates, rendering the clustering trivial or ineffective.
• High-Dimensional Challenges: Text embeddings (e.g., from SentenceTransformers) often use cosine distance in high-dimensional spaces. This makes $\epsilon$-threshold graphs unstable (sensitive to small parameter changes) and exacerbates the "curse of dimensionality," where distance metrics lose geometric meaning.

2. Methodology

The authors propose a novel Incremental $k$-NN Graph Construction Algorithm that guarantees graph connectivity by design, regardless of the value of $k$.

Core Algorithm (Algorithm 1)

Instead of searching for the $k$ nearest neighbors among all $N$ nodes simultaneously (which can leave isolated nodes if they are far from the main cluster), the algorithm builds the graph sequentially:

1. Initialization: Start with the first $k$ nodes as the initial set of vertices $V$.
2. Iterative Insertion: For each subsequent node $x_t$ (where $t > k$):
   • Identify the $k$ nearest neighbors of $x_t$ only among the nodes already present in the graph ($V$).
   • Add edges connecting $x_t$ to these $k$ neighbors.
   • Add $x_t$ to $V$.
3. Result: Since every new node connects to at least one existing node (specifically $k$ nodes), the graph remains connected throughout the construction process.

Theoretical Proof

The authors provide an inductive proof of connectedness:

• Base Case: The first $k+1$ nodes form a single connected component because the $(k+1)$-th node connects to all previous $k$ nodes.
• Inductive Step: Adding any new node $x_i$ to an already connected graph connects it to $k$ existing nodes, thereby extending the single connected component to include $x_i$.
• Conclusion: The final graph of $N$ vertices is guaranteed to have exactly one connected component.

Downstream Application

The constructed graph is used for Spectral Clustering via Laplacian Eigenmaps:

• The graph adjacency matrix is converted into a Laplacian matrix.
• Eigenvectors corresponding to the smallest eigenvalues are extracted to create a low-dimensional embedding.
• $k$-means clustering is performed on these embeddings.
• The authors note that because the graph is connected, the first eigenvector is constant; thus, they utilize the second set of eigenvectors for clustering.

3. Key Contributions

1. Guaranteed Connectivity: The primary contribution is an algorithmic modification that ensures the neighborhood graph is connected for any $k \ge 1$, eliminating the risk of degenerate spectral clustering.
2. Incremental Capability: Unlike standard $k$-NN which requires global recomputation if new data arrives, this method supports incremental updates. New documents can be added by linking them only to the existing graph, making it suitable for streaming data scenarios.
3. Efficiency: The algorithm reduces computational complexity during construction by searching for neighbors only within the currently processed subset of nodes, rather than the entire dataset.
4. Robustness to Ordering: The authors demonstrate that while the graph structure depends on the order of node insertion, the resulting clustering performance is highly stable (low variance) across different random orderings.

4. Experimental Results

The method was evaluated on six text datasets from the Massive Text Embedding Benchmark (MTEB), using SentenceTransformer embeddings (all-MiniLM-L12-v2).

• Performance in Low-$k$ Regime:
  • Standard $k$-NN graphs frequently produced disconnected components for $k \le 20$ on several datasets (e.g., TwentyNewsgroups, Reddit).
  • The Incremental approach significantly outperformed standard $k$-NN in these low-$k$ regimes, achieving higher V-measure scores (a harmonic mean of homogeneity and completeness).
  • For example, on the TwentyNewsgroups dataset, the incremental method achieved a V-measure of 32.89% at $k=1$, whereas standard $k$-NN scored only 7.19% (due to massive disconnection).
• Performance in High-$k$ Regime:
  • As $k$ increased (e.g., $k > 15$), standard $k$-NN graphs eventually became connected. In these scenarios, the incremental method's performance matched the standard $k$-NN, showing no degradation.
• Stability:
  • Ten runs with randomized node orderings showed a standard deviation in clustering performance of < 1% (often < 0.5%), confirming the method's robustness to input ordering.
• Ablation Studies:
  • Embedding Models: Larger embedding models (e.g., gte-large, bge-base-en-v1.5) yielded better results, but the incremental construction remained superior to standard $k$-NN in low-$k$ settings regardless of the model.
  • MST Integration: The authors tested adding a Minimum Spanning Tree (MST) to the incremental graph. Results showed that adding MST did not improve performance and, in some cases (like TwentyNewsgroups), slightly degraded it. This suggests the incremental connectivity is sufficient and global MST features are redundant or potentially noisy for this specific task.

5. Significance and Future Work

• Practical Impact: The method allows practitioners to use very sparse graphs (small $k$) for spectral clustering without fear of disconnection. This is crucial for memory efficiency and speed in large-scale text clustering.
• Streaming Data: The incremental nature of the algorithm opens the door for real-time clustering of streaming text data, a task where standard spectral clustering is traditionally infeasible due to the need for global graph reconstruction.
• Future Directions:
  • Exploring approximate $k$-NN search (e.g., HNSW) to further speed up the incremental construction.
  • Leveraging the incremental property for temporal community detection and dynamic graph updates.
  • Investigating strategies to mitigate potential suboptimal connections formed by nodes processed early in the sequence.

In summary, the paper presents a simple yet powerful modification to graph construction that solves the connectivity problem in spectral clustering, enabling robust, efficient, and scalable text analysis.