Dual-Pass Cosine Thresholding Combined with Asymmetric MkNN Symmetrization for Hub-Node Suppression
High-Dimensional Hubness in Lexical Semantic Networks
In dense vector spaces derived from large language model embeddings (e.g., 768 to 3072 dimensions), high-dimensional geometry induces a phenomenon known as the hubness problem. Due to the concentration of distances in high dimensions, certain points intrinsically become nearest neighbors to a disproportionately large fraction of the dataset. When building a graph-based keyword cluster tool, this mathematical artifact manifests as semantic “super-hubs”—broad, generic, or polysemous terms that bridge otherwise isolated, highly specific topical clusters.
Left unmitigated, these hub nodes inflate node degrees, distort modularity landscapes, and trigger catastrophic failure modes in downstream community detection algorithms. A naive graph constructed purely on pairwise cosine similarities causes the Leiden or Louvain algorithms to fuse distinct search intents into single, unwieldy giant components. Mitigating this topology requires a targeted sparsification strategy that decouples true semantic affinity from structural hubness bias.
The Structural Role of Sparsification and MkNN
To establish stable boundaries across enterprise-scale keyword corpora, semantic graphs must undergo rigorous topological pruning prior to modularity optimization. The operational principles of this pipeline build directly upon the foundational mechanics outlined in Graph Sparsification and Mutual k-Nearest Neighbor Pruning to Prevent Leiden Giant Component Formation. In high-density search term spaces, however, standard bidirectional mutual nearest neighbor constraints are frequently either too destructive—causing excessive fragmentation of legitimate tail-topic cliques—or too permissive when high-degree hub nodes dominate local neighborhoods.
Dual-pass thresholding combined with asymmetric symmetrization creates an engineered edge-filtering pipeline. By modulating cosine thresholds across both global and local density regimes and enforcing directed neighbor reciprocity with a parameterized hubness penalty, the graph preserves sparse local sub-topologies while systematically severing high-dimensional bridge artifacts.
Dual-Pass Cosine Thresholding Mechanics
Standard thresholding relies on a global cutoff ($tau_{global}$), retaining all edges where $cos(u, v) ge tau_{global}$. This fails uniformly across keyword spaces: dense semantic neighborhoods retain hundreds of redundant edges, while low-density, highly specialized long-tail clusters are prematurely disconnected. The dual-pass approach applies two distinct filtration phases to dynamically condition the edge set $E$.
Pass 1: Coarse Global Support Pruning
Given the pairwise cosine similarity matrix $S in mathbb{R}^{|V| times |V|}$, the first pass eliminates absolute semantic noise. The global threshold $tau_{global}$ is set conservatively (e.g., $tau_{global} in [0.45, 0.60]$ depending on embedding geometry), producing an initial sparse candidate matrix $S^{(1)}$:
$$S^{(1)}_{ij} = begin{cases} S_{ij} & text{if } S_{ij} ge tau_{global} \ 0 & text{otherwise} end{cases}$$
This pass acts as an asymptotic safety rail, purging non-viable negative semantic pairs before executing more compute-intensive local neighborhood assessments.
Pass 2: Dynamic Local Distributional Thresholding
The second pass calculates a localized, node-specific threshold $tau_{local}(u)$ based on the distribution of similarities within each node’s candidate edge list. For each node $u$, let $mu_u$ and $sigma_u$ be the mean and standard deviation of non-zero similarity scores in $S^{(1)}_{u*}$. The edge $(u, v)$ is retained only if it exceeds an adaptive distributional hurdle:
$$tau_{local}(u) = mu_u + alpha cdot sigma_u$$
where $alpha$ is a tuning parameter controlling neighborhood selectivity (typically $alpha in [0.5, 1.5]$). An edge survives Pass 2 if it clears the local criterion from at least one perspective:
$$S^{(2)}_{uv} = begin{cases} S^{(1)}_{uv} & text{if } S^{(1)}_{uv} ge min(tau_{local}(u), tau_{local}(v)) \ 0 & text{otherwise} end{cases}$$
This dual-pass mechanism prevents high-density regions from saturating the graph with redundant transitivity while shielding delicate, low-variance tail keywords from total structural starvation.
Asymmetric MkNN Symmetrization Formulation
Once edges survive dual-pass thresholding, they are mapped into a directed $k$-nearest neighbor graph $G_{dir} = (V, E_{dir})$, where a directed edge $(u to v)$ exists if $v$ is among the top-$k$ most similar surviving neighbors of $u$.
Traditional Mutual $k$-Nearest Neighbor (MkNN) constructs an undirected edge only if the connection is bidirectional: $(u to v) in E_{dir} land (v to u) in E_{dir}$. While standard MkNN aggressively crushes hubs, it also over-fragments low-density regions where asymmetric search queries point to broader category nodes without reciprocation.
The Asymmetric Symmetrization Kernel
To overcome this limitation, asymmetric MkNN introduces a directional rank-decay kernel. Let $r(u to v) in {1, 2, dots, k}$ represent the ordinal rank of $v$ in the filtered neighbor list of $u$. If $v$ does not appear in $u$’s top-$k$, $r(u to v) = infty$. An asymmetry metric is formulated via the geometric mean of directed ranks, penalized by the target node’s global in-degree $d_{in}(v)$ in $G_{dir}$:
$$H(v) = log_2(1 + d_{in}(v))$$
Here, $H(v)$ quantifies the empirical hubness of node $v$. The final undirected edge weight $W_{uv}$ is computed as:
$$W_{uv} = begin{cases}
S_{uv} cdot expleft( -frac{|r(u to v) – r(v to u)|}{min(r(u to v), r(v to u))} right) cdot frac{1}{sqrt{H(u) cdot H(v)}} & text{if } (u to v) in E_{dir} lor (v to u) in E_{dir} \
0 & text{otherwise}
end{cases}$$
This formulation enforces three critical topological properties:
- Symmetric Reciprocity Preference: When $r(u to v) approx r(v to u)$, the exponential penalty approaches $1.0$, prioritizing mutually matched keywords.
- Soft Recovery of Asymmetric Edges: Nodes that are legitimate sub-variants of a parent entity are retained even if unidirectional, but their weight is scaled down relative to the rank disparity.
- Dynamic Hub Suppression: The term $frac{1}{sqrt{H(u) cdot H(v)}}$ heavily penalizes connections to nodes with disproportionately high incoming link volumes, effectively neutralizing high-dimensional attraction basins.
Algorithmic Pipeline and Graph Convergence
Implementing this graph transformation inside a production-grade keyword cluster tool requires strict separation of pipeline stages to manage computational complexity:
- Approximate Nearest Neighbor (ANN) Retrieval: Construct an initial metric index (e.g., via Hierarchical Navigable Small World graphs or HNSW) using inner product or cosine distance. Retrieve $k_{initial} = 3k$ candidate neighbors per keyword.
- Vectorized Pass 1 Filtration: Discard all candidates below the baseline scalar $tau_{global}$.
- Local Distribution Profiling (Pass 2): Compute localized $mu_u$ and $sigma_u$ vectors natively over the sparse candidate CSR matrix; eliminate edges falling below the localized threshold $tau_{local}$.
- Directed In-Degree Calculation: Formulate the directed top-$k$ adjacency matrix and accumulate node-level in-degrees $d_{in}$ across the corpus to derive hubness vectors $H$.
- Asymmetric Symmetrization: Evaluate directional rank pairs for all surviving non-zero coordinates and assign the regularized edge weights $W_{uv}$.
- Pruning Isolated Components: Remove dangling nodes with zero remaining incident edges, routing them to an unassigned cluster buffer or re-evaluating them against relaxed semantic constraints.
Downstream Topological Impact on Community Detection
The combination of dual-pass filtering and asymmetric symmetrization shifts the graph’s degree distribution from a scale-free power-law topology (dominated by high-degree hub nodes) toward an exponential or bounded degree distribution. When applying community detection algorithms such as the Leiden method (optimizing Constant Potts Model or modularity quality functions), this tailored degree structure produces deterministic performance enhancements:
- Elimination of Spurious Centralities: Hub terms no longer accumulate artificial betweenness centrality, preventing the aggregation of semantically distinct concepts into monolithic partitions.
- Resolution Parameter Sensitivity: The modularity landscape becomes significantly smoother, allowing the resolution parameter $gamma$ to cleanly dictate cluster granularity without triggering abrupt giant-component coalescence.
- Granular Topical Coherence: Sub-intent clusters (e.g., commercial transactional queries versus informational diagnostic queries) remain cleanly separated in the resulting graph partitions, directly improving the structural utility of the output clustering hierarchy.