Sparse Mutual Information Graph Averaging for Improving Random Indexing Embeddings

# Sparse Mutual Information Graph Averaging for Improving Random Indexing Embeddings
Source: [https://arxiv.org/html/2608.05724](https://arxiv.org/html/2608.05724)
###### Abstract

Sparse word embedding pipelines can avoid dense co\-occurrence matrix materialization, dense factorization, and gradient training while still relying on sparse global corpus statistics\. This paper studies Random Indexing \(RI\) vectors refined by weighted averaging on a sparse Positive Pointwise Mutual Information \(PPMI\) graph\. On a fairytales corpus, the covered semantic analogy set consists of 272 Google family\-category questions\. On this family subset, PPMI top\-KKgraph averaging repairs a weak RI initialization, improving accuracy from 19\.4±\\pm0\.7% to 30\.7±\\pm2\.9% across five seeds\. Under the single tested runs, the same neighborhood averaging reduces family\-subset analogy accuracy for PPMI\+SVD \(singular value decomposition\), Binary\+SVD, CBOW, and Skip\-gram\. Thus the method is not competitive with neural baselines on text8 and gives near\-zero strict similarity correlation on SimLex\-999\. While Bloom filter sketches underperform RI in the tested configuration, we find that PPMI graph averaging with top\-KKpruning is a useful non\-gradient repair for weak RI embeddings\. On the fairytales dataset, PPMI top\-KK=50 graph averaging improves RI with accuracy going from 19\.4±\\pm0\.7% to 30\.7±\\pm2\.9%, and performing best with a seed42 of 34\.6%\.

## IIntroduction

Word embeddings are a foundational component of natural language processing, representing words as dense vectors that capture semantic relationships\. Standard methods for constructing these representations fall into two families: count\-based methods that factorize large co\-occurrence matrices, and predictive methods that train neural models through gradient descent\. Both families have produced strong results, but both also require either global matrix operations or repeated parameter updates over large vocabularies, making them expensive in memory and compute\.

Sparse graph\-based methods provide a narrower alternative\. They avoid dense co\-occurrence matrix materialization, dense factorization, and gradient training, but they still construct sparse global corpus statistics such as document frequency, co\-occurrence marginals, and Positive Pointwise Mutual Information \(PPMI\) weights\. The practical appeal is sparse computation and reproducibility, not strict locality or maximal accuracy\.

This paper investigates one such pipeline\. Word vectors are initialized from co\-occurrence encodings and refined through weighted neighborhood averaging on a sparse graph\. The pipeline requires no dense matrix decomposition, no backpropagation, and no gradient\-trained parameters, but it still has hyperparameters including context window size, embedding dimension, random\-index sparsity, PMI shiftkk, top\-KKpruning, minimum count, damping strengthα\\alpha, propagation depth, and normalization\. The central question is narrower than whether graph averaging is universally useful: can sparse PPMI averaging improve or repair a weak initialization? May it reduce useful structure that is already present?

The results show that a PPMI top\-KKgraph substantially improves Random Indexing \(RI\) on the small fairytales benchmark, but the gain is seed\-sensitive and all covered semantic questions fall into a single family category\. The same averaging step reduces accuracy for stronger fitted embeddings under the single tested runs, the method remains far behind neural baselines on text8, and the best analogy configuration performs poorly on strict similarity\. Bloom filter initialization is included as a negative result for the tested configuration because its OR\-style accumulation may discard frequency information that Random Indexing preserves\.

Experiments use the Google analogy test set\[[7](https://arxiv.org/html/2608.05724#bib.bib7)\], SimLex\-999\[[5](https://arxiv.org/html/2608.05724#bib.bib5)\], and WordSim\-353\[[6](https://arxiv.org/html/2608.05724#bib.bib6)\]on a fairytales corpus and a Wikipedia\-derived text8 sub\-corpus\. Section II reviews related work\. Section III describes the datasets\. Section IV presents the method\. Section V describes the evaluation protocol\. Section VI reports results\. Section VII discusses limitations\. Section VIII concludes\.

## IIRelated Work

### II\-AWord Embeddings

Word2Vec\[[1](https://arxiv.org/html/2608.05724#bib.bib1)\]introduced two influential architectures for predictive word embedding\. CBOW predicts a target word from its surrounding context by averaging context vectors, while Skip\-gram predicts context words from a target word\. Both are trained with negative sampling and have become standard baselines\. GloVe\[[2](https://arxiv.org/html/2608.05724#bib.bib2)\]is a count\-based method that combines global co\-occurrence statistics with a weighted least\-squares objective\.

The relationship between count\-based and predictive methods has been studied extensively\. Baroni et al\.\[[3](https://arxiv.org/html/2608.05724#bib.bib3)\]found that predictive models outperformed count\-based methods on many intrinsic tasks\. Levy and Goldberg\[[15](https://arxiv.org/html/2608.05724#bib.bib15)\]showed that Skip\-gram with negative sampling implicitly factorizes a shifted pointwise mutual information matrix, connecting the two families mathematically\. Levy et al\.\[[4](https://arxiv.org/html/2608.05724#bib.bib4)\]further showed that many performance differences between methods are explained by hyperparameter choices rather than fundamental architectural differences\.

### II\-BSparse and Memory\-Efficient Methods

Random Indexing\[[9](https://arxiv.org/html/2608.05724#bib.bib9),[18](https://arxiv.org/html/2608.05724#bib.bib18)\]is the most relevant sparse baseline for this work\. It assigns each word a sparse random vector and accumulates context evidence additively by adding the random vectors of neighboring words\. This additive property preserves frequency information: a context word that appears 100 times near a target has 100 times more influence than one that appears once\. This is a key contrast with Bloom filter OR\-based accumulation, which is monotone and does not preserve frequency\.

Bloom\-based and hash\-based embedding ideas have appeared in prior work primarily for compression purposes\. Serra and Karatzoglou\[[16](https://arxiv.org/html/2608.05724#bib.bib16)\]used Bloom\-style hashing to build compact embedding tables for sparse binary inputs in recommender systems\. Svenstrup et al\.\[[17](https://arxiv.org/html/2608.05724#bib.bib17)\]proposed hash embeddings that share parameters across vocabulary entries to reduce memory\. These methods optimize for memory reduction rather than semantic geometry, which is a different objective from ours\.

Recent work on matmul\-free language modeling\[[20](https://arxiv.org/html/2608.05724#bib.bib20)\]has explored eliminating matrix multiplications from transformer architectures entirely\. Randomized linear algebra methods\[[21](https://arxiv.org/html/2608.05724#bib.bib21)\]have demonstrated that many machine learning computations can be performed using compressed approximate representations\. These directions further motivate asking how far sparse, non\-gradient embedding construction can go without dense factorization\.

### II\-CGraph Diffusion and Oversmoothing

Graph\-based post\-processing methods are closely related to the diffusion stage\. Retrofitting\[[10](https://arxiv.org/html/2608.05724#bib.bib10)\]adjusts pre\-trained word vectors to conform to an external lexical knowledge graph\. In the graph neural network literature, repeated neighborhood aggregation is known to produce oversmoothing, in which node representations converge to a common value\. The damping mechanism used here is related to APPNP\[[11](https://arxiv.org/html/2608.05724#bib.bib11)\], which uses personalized PageRank\-style propagation with a residual connection to the original features\. In our recurrence,α\\alphais the smoothing strength and1−α1\-\\alphais the residual weight\.

Post\-processing techniques that improve the geometry of learned embeddings are also relevant\. Mu and Viswanath\[[14](https://arxiv.org/html/2608.05724#bib.bib14)\]demonstrated that discarding the top principal components of embedding matrices improves performance on similarity and analogy tasks by mitigating anisotropy\. The per\-dimension robust scaling employed here addresses a related phenomenon: after diffusion, individual coordinates frequently exhibit heavy\-tailed distributions that distort cosine\-based similarity\.

## IIIDatasets

### III\-AFairytales Corpus

The fairytales corpus is derived from the Fairy Tales from Around the World collection on Kaggle \(sourced from Project Gutenberg\)\.111Fairy Tales from Around the World, Kaggle dataset,[https://www\.kaggle\.com/datasets/annbengardt/fairy\-tales\-from\-around\-the\-world](https://www.kaggle.com/datasets/annbengardt/fairy-tales-from-around-the-world)\(accessed May 1, 2024\)\.After tokenization and lemmatization with spaCy it contains 1,383,029 tokens and a vocabulary of 18,254 distinct words spanning 149,860 sentence units\.

This corpus is small and domain\-specific\. Semantic analogy coverage is only 272 of 8,869 questions \(3\.1%\), all from the Google benchmark’s family category\. Semantic accuracy estimates therefore have high variance and narrow scope\. A change of one correctly answered question corresponds to approximately 0\.4 percentage points\.

### III\-BText8 Sub2m Corpus

The text8 sub2m corpus is obtained by subsampling the standard text8 Wikipedia excerpt to approximately two million tokens\.222The text8 corpus is the first 100 MB of a cleaned English Wikipedia dump, lowercased and reduced to 27 character types, distributed by M\. Mahoney at[http://mattmahoney\.net/dc/textdata\.html](http://mattmahoney.net/dc/textdata.html)\(accessed May 1, 2024\)\. The Sub2m subset used here consists of the first approximately two million tokens of text8\.After identical preprocessing it contains 2,000,007 tokens and a vocabulary of 20,181 words\. Analogy coverage is substantially higher: 8,946 of 10,675 syntactic questions \(83\.8%\) and 506 of 8,869 semantic questions \(5\.7%\)\.

The cross\-corpus comparison is confounded by sentence units\. Fairytales averages 9\.2 tokens per sentence unit, while text8 averages 46\.9 tokens per unit and has no true sentence boundaries\. Since context windows are clipped at these units, co\-occurrence density differs systematically across corpora\.

### III\-CCorpus Statistics

Semantic coverage and syntactic coverage report the fraction of the Google analogy test set that is answerable given each corpus vocabulary: an analogy question is covered only if all four of its words appear in the vocabulary\. These counts are computed by us during evaluation rather than supplied with the corpora, and the evaluation procedure is described in Section[V](https://arxiv.org/html/2608.05724#S5)\. Coverage is low for the fairytales corpus because its small vocabulary excludes many of the geographic and grammatical terms used in the Google questions\.

TABLE I:Corpus statistics and analogy benchmark coverage\.The fairytales syntactic coverage value in Table[I](https://arxiv.org/html/2608.05724#S3.T1)is independent of the 18\.8% seed\-42 Random Indexing semantic accuracy reported later; the former is a coverage ratio and the latter is 51 correct answers among 272 valid semantic questions\.

## IVMethod

### IV\-AOverview

The pipeline comprises three stages: initialization, diffusion, and normalization\. The ablation study in Section VI indicates that graph construction and normalization strongly affect final quality\. No dense co\-occurrence matrix is materialized, and no dense factorization or gradient training is performed\. The method still constructs sparse global co\-occurrence statistics and propagates through a sparse graph operator\. All graph operations are performed via sparse edge\-list accumulations, so working memory scales linearly with vocabulary size and embedding dimension plus graph edges\.

### IV\-BNeighborhood Construction

For diffusion graphs, each occurrence of a target wordwwcollects context words inside a symmetric window of radiusr=8r=8clipped at sentence boundaries\. The resulting co\-occurrence information is stored as a sparse directed graph represented by three arrays: source indices, destination indices, and edge weights\. The graph is directed because the weighting scheme conditions on the target word\. Table[II](https://arxiv.org/html/2608.05724#S6.T2)lists the window used by each reported artifact; the reported RI\+PPMI result combines a Random Indexing initialization built with window 10 and a PPMI graph built with window 8\.

### IV\-CTarget\-Conditioned Edge Weighting

Co\-occurrence edges are weighted using a target\-conditioned scheme that combines local frequency with a global rarity term\. For each target wordww, a pseudo\-document is formed by aggregating all context windows centered onww\. For a neighbornnofww, the weight is defined as

T​\[w,n\]=TF​\[w,n\]×IDF​\[n\],T\[w,n\]=\\text\{TF\}\[w,n\]\\times\\text\{IDF\}\[n\],
where

TF​\[w,n\]=count​\(n​in contexts of​w\)\|contexts of​w\|\\text\{TF\}\[w,n\]=\\frac\{\\text\{count\}\(n\\text\{ in contexts of \}w\)\}\{\|\\text\{contexts of \}w\|\}
and

IDF​\[n\]=log⁡\(1\+\|𝒱\|1\+DF​\[n\]\)\+1\.\\text\{IDF\}\[n\]=\\log\\left\(\\frac\{1\+\|\\mathcal\{V\}\|\}\{1\+\\text\{DF\}\[n\]\}\\right\)\+1\.
HereDF​\[n\]\\text\{DF\}\[n\]is the number of distinct target words that havennas a neighbor at least once, and\|𝒱\|\|\\mathcal\{V\}\|is the vocabulary size\. This follows the standard smoothed\-IDF form used in scikit\-learn\-style TF\-IDF implementations\[[8](https://arxiv.org/html/2608.05724#bib.bib8)\]\. The smoothed IDF term guarantees strictly positive weights\. The resulting graph is directed because the weightT​\[w,n\]T\[w,n\]is conditioned on the targetww\.

For the PPMI graph, the implementation counts directed co\-occurrencesc​\(w,n\)c\(w,n\)inside the same clipped window, discards pairs with count below two, and estimates

PMIk​\[w,n\]=log⁡\(c​\(w,n\)​Cc​\(w,∗\)​c​\(∗,n\)\)−log⁡k,\\text\{PMI\}\_\{k\}\[w,n\]=\\log\\left\(\\frac\{c\(w,n\)C\}\{c\(w,\*\)c\(\*,n\)\}\\right\)\-\\log k,whereC=∑w,nc​\(w,n\)C=\\sum\_\{w,n\}c\(w,n\),c​\(w,∗\)c\(w,\*\)is the target row count, andc​\(∗,n\)c\(\*,n\)is the context column count\. The reported PPMI runs usek=1k=1, so there is no shift beyond positive truncation\. Edge weights arePPMI​\[w,n\]=max⁡\(PMIk​\[w,n\],0\)\\text\{PPMI\}\[w,n\]=\\max\(\\text\{PMI\}\_\{k\}\[w,n\],0\), followed by top\-KKrow pruning withK=50K=50\. In that configuration,T​\[w,n\]T\[w,n\]in the update equations denotes the pruned PPMI edge weight rather than TF\-IDF\.

### IV\-DBloom Filter Initialization

Each target word is assigned an all\-zero bit vector of lengthmm, following the Bloom filter data structure\[[19](https://arxiv.org/html/2608.05724#bib.bib19)\]\. For each of its top\-20 context neighbors \(ranked by edge weight\),hhhash functions are applied using MurmurHash3 with seeds0,…,h−10,\\dots,h\-1, and the corresponding bit positions modulommare set\. Bits are recoded from\{0,1\}\\\{0,1\\\}to\{−1,\+1\}\\\{\-1,\+1\\\}prior to diffusion\. The experiments usem=200m=200bits andh=5h=5hash functions\.

In the corrected tested configuration, Bloom initialization still underperforms Random Indexing \(Table[IV](https://arxiv.org/html/2608.05724#S6.T4)\)\.333A previous Bloom implementation applied MurmurHash3 to target strings instead of neighbors and handled negative hashes incorrectly, producing all\-zero vectors for much of the vocabulary\. The corrected results are reported here as a reproducibility note rather than as part of the method definition\.

### IV\-ERandom Indexing Initialization

Each word is assigned a sparse random vector of dimensionddcontaining exactly eight nonzero entries drawn uniformly from\{−1,\+1\}\\\{\-1,\+1\\\}\. Context vectors are accumulated additively: for every occurrence of a target word, the random vectors of its context neighbors are added to the target, with optional TF\-IDF scaling in the weighted variant\. This additive scheme preserves frequency information, in contrast to the monotone OR accumulation used by Bloom filters\. Because Random Indexing already injects co\-occurrence evidence through neighbor\-vector accumulation, the later PPMI graph step injects co\-occurrence evidence a second time; this is best interpreted as a repair of a weak RI initialization rather than a clean post\-processing result for arbitrary embeddings\.

### IV\-FIterative Embedding Update

At each iteration, every word vector is replaced by a weighted average of its neighbors’ vectors from the previous iteration\. Let𝐕\(t\)\\mathbf\{V\}^\{\(t\)\}denote the embedding matrix at depthtt\. For each wordww,

𝐌\(t\)​\[w\]=∑n∈N​\(w\)T​\[w,n\]⋅𝐕\(t\)​\[n\]∑n∈N​\(w\)T​\[w,n\],\\mathbf\{M\}^\{\(t\)\}\[w\]=\\frac\{\\sum\_\{n\\in N\(w\)\}T\[w,n\]\\cdot\\mathbf\{V\}^\{\(t\)\}\[n\]\}\{\\sum\_\{n\\in N\(w\)\}T\[w,n\]\},
whereN​\(w\)N\(w\)is the neighbor set ofwwandT​\[w,n\]T\[w,n\]is the edge weight\. This is equivalent to multiplying by a row\-normalized sparse graph operator𝐏\\mathbf\{P\}\. Words with no neighbors retain zero rows in𝐏\\mathbf\{P\}and are carried by the residual term when damping is enabled\. All updates are synchronous\.

Algorithm 1Residual Graph Diffusion Used for PPMI Runs0:Initial vectors

𝐕0\\mathbf\{V\}\_\{0\}, row\-normalized graph operator

𝐏\\mathbf\{P\}, iterations

NN, damping factor

α\\alpha
0:Final embeddings

𝐕\\mathbf\{V\}
𝐕\(0\)←𝐕0\\mathbf\{V\}^\{\(0\)\}\\leftarrow\\mathbf\{V\}\_\{0\}
for

t=0t=0to

N−1N\-1do

𝐌\(t\)←𝐏𝐕\(t\)\\mathbf\{M\}^\{\(t\)\}\\leftarrow\\mathbf\{P\}\\mathbf\{V\}^\{\(t\)\}
𝐕\(t\+1\)←\(1−α\)​𝐕0\+α​𝐌\(t\)\\mathbf\{V\}^\{\(t\+1\)\}\\leftarrow\(1\-\\alpha\)\\mathbf\{V\}\_\{0\}\+\\alpha\\mathbf\{M\}^\{\(t\)\}
endfor

return

Normalize​\(𝐕\(N\)\)\\text\{Normalize\}\(\\mathbf\{V\}^\{\(N\)\}\)

Repeated application of Algorithm[1](https://arxiv.org/html/2608.05724#alg1)defines the depth\-NNdiffusion operator\. Reported PPMI runs use residual mixing before terminal normalization, and robust scaling is applied once after the final propagation step\.

Let\|𝒱\|\|\\mathcal\{V\}\|be the vocabulary size,EEthe number of directed graph edges,ddthe embedding dimension, andNNthe number of diffusion steps\. Each step touches each nonzero edge once and accumulates add\-dimensional vector, givingO​\(E​d\)O\(Ed\)time for propagation\. Row normalization costsO​\(\|𝒱\|​d\)O\(\|\\mathcal\{V\}\|d\), while exact per\-coordinate median and percentile computation for robust scaling adds an implementation\-dependent quantile cost across\|𝒱\|\|\\mathcal\{V\}\|values for each dimension\. The propagation recurrence therefore costsO​\(N​E​d\)O\(NEd\)plus the terminal normalization and quantile\-scaling cost\. Working memory isO​\(\|𝒱\|​d\+E\)O\(\|\\mathcal\{V\}\|d\+E\)when the graph is stored sparsely\. With top\-KKpruning,E≤K​\|𝒱\|E\\leq K\|\\mathcal\{V\}\|\.

### IV\-GNormalization

The normalization operator used before evaluation is applied in the following order:

1. 1\.Row\-wiseℓ2\\ell\_\{2\}normalization: 𝐯w←𝐯w‖𝐯w‖2\+ϵ\.\\mathbf\{v\}\_\{w\}\\leftarrow\\frac\{\\mathbf\{v\}\_\{w\}\}\{\\\|\\mathbf\{v\}\_\{w\}\\\|\_\{2\}\+\\epsilon\}\.
2. 2\.Per\-dimension robust scaling\. For each coordinatejj, compute the median and interquartile range \(IQR\) across all word vectors and apply vw,j←vw,j−medianjIQRj\+ϵ\.v\_\{w,j\}\\leftarrow\\frac\{v\_\{w,j\}\-\\text\{median\}\_\{j\}\}\{\\text\{IQR\}\_\{j\}\+\\epsilon\}\.
3. 3\.A second row\-wiseℓ2\\ell\_\{2\}renormalization\.

The three\-stage procedure is denoted collectively byNormalize​\(⋅\)\\text\{Normalize\}\(\\cdot\)in Algorithm[1](https://arxiv.org/html/2608.05724#alg1)\. Robust scaling is employed rather than z\-score normalization because diffusion frequently produces heavy\-tailed marginal distributions; the ablation in Section VI indicates thatℓ2\\ell\_\{2\}normalization alone after diffusion is detrimental\.

### IV\-HPersonalized PageRank \(PPR\) Damping Variant

Repeated un\-damped diffusion produces oversmoothing: representations converge toward a common centroid and lose discriminative power\. Although the pipeline supports multiple iterations, semantic accuracy peaks early and then declines for the tested configurations\. This mirrors well\-documented behavior in graph neural networks, where shallow propagation often outperforms deep propagation on node classification and representation tasks\[[12](https://arxiv.org/html/2608.05724#bib.bib12),[13](https://arxiv.org/html/2608.05724#bib.bib13)\]\. To mitigate oversmoothing when multiple steps are used, a residual connection to the original initialization is introduced:

𝐕\(t\+1\)=\(1−α\)⋅𝐕\(0\)\+α⋅diffuse​\(𝐕\(t\)\),\\mathbf\{V\}^\{\(t\+1\)\}=\(1\-\\alpha\)\\cdot\\mathbf\{V\}^\{\(0\)\}\+\\alpha\\cdot\\text\{diffuse\}\(\\mathbf\{V\}^\{\(t\)\}\),where𝐕\(0\)\\mathbf\{V\}^\{\(0\)\}is held fixed throughout propagation andα∈\[0,1\]\\alpha\\in\[0,1\]controls the strength of smoothing\. This is the recurrence in Algorithm[1](https://arxiv.org/html/2608.05724#alg1)\.

### IV\-IGPU Implementation

Diffusion is implemented via sparse scatter\-add operations in CuPy\. The graph is represented by three arrays \(source indices, destination indices, and weights\)\. Accumulation uses float64 for numerical stability\. Per\-iteration complexity isO​\(E⋅d\)O\(E\\cdot d\), whereEEis the number of edges\. All experiments were executed on an NVIDIA RTX 5060 \(8 GB\)\.

## VEvaluation

### V\-AWord Analogy Test

Evaluation uses the Google Semantic\-Syntactic Word Relationship test set\[[7](https://arxiv.org/html/2608.05724#bib.bib7)\]\. For an analogy tuple\(a,b,c,d\)\(a,b,c,d\), the predicted fourth word is

d^=arg⁡maxw∉\{a,b,c\}⁡cos⁡\(𝐯​\(w\),𝐯​\(b\)−𝐯​\(a\)\+𝐯​\(c\)\)\.\\hat\{d\}=\\arg\\max\_\{w\\notin\\\{a,b,c\\\}\}\\cos\(\\mathbf\{v\}\(w\),\\mathbf\{v\}\(b\)\-\\mathbf\{v\}\(a\)\+\\mathbf\{v\}\(c\)\)\.A prediction is counted as correct whend^=d\\hat\{d\}=d\. Analogies containing any out\-of\-vocabulary word are discarded\. For fairytales, the headline metric is the covered family\-category semantic subset because it is the only covered semantic category\. Fairytales syntactic coverage exists, but existing outputs place the selected seed42 RI\+PPMI run at only 1\.4% on 2,006 valid syntactic questions, so syntactic accuracy is treated as a limitation check rather than as the positive result\. We report both semantic and syntactic accuracy on text8 because syntactic coverage is large enough to provide a higher\-power comparison\.

### V\-BWord Similarity Benchmarks

SimLex\-999\[[5](https://arxiv.org/html/2608.05724#bib.bib5)\]consists of 999 word pairs with human annotations of strict semantic similarity\. WordSim\-353\[[6](https://arxiv.org/html/2608.05724#bib.bib6)\]consists of 353 pairs annotated for broader semantic relatedness\. For both benchmarks, performance is measured by the Spearman rank correlation between human scores and cosine similarities induced by the embeddings\.

### V\-CBaselines

All methods use 200\-dimensional vectors\. Table[II](https://arxiv.org/html/2608.05724#S6.T2)summarizes the settings\.

## VIResults

We evaluate the full pipeline on the fairytales corpus using the Google analogy task as the main metric, supplemented by SimLex\-999 and WordSim\-353\. The fairytales analogy metric is a narrow family\-subset result because all 272 covered semantic questions belong to the Google benchmark’s family category\. All methods are configured with 200\-dimensional vectors unless otherwise noted; Table[II](https://arxiv.org/html/2608.05724#S6.T2)summarizes the exact settings\. Our finding is that TF\-IDF weighted diffusion alone does not improve most methods, while PPMI graph diffusion with top\-K=50K=50pruning repairs Random Indexing from 19\.4±\\pm0\.7% to 30\.7±\\pm2\.9% across five seeds\.

![Refer to caption](https://arxiv.org/html/2608.05724v1/x1.png)Figure 1:Fairytales family\-subset analogy accuracy\. TF\-IDF graph diffusion marginally improves RI but reduces accuracy for most other initializations; PPMI graph diffusion with top\-K=50K=50pruning reports the five\-seed RI\+PPMI mean rather than the best seed\.TABLE II:Baseline methods and reported context windows\. Diffused rows use a graph window of 8 unless otherwise noted\. SVD denotes Singular Value Decomposition\.### VI\-AComparison of Embedding Methods

Figure[1](https://arxiv.org/html/2608.05724#S6.F1)and Table[III](https://arxiv.org/html/2608.05724#S6.T3)present the headline result\. TF\-IDF weighted diffusion marginally improves seed42 Random Indexing from 18\.8% to 19\.1% but reduces family\-subset accuracy for PPMI\+SVD, Binary\+SVD, CBOW, and Skip\-gram under the single tested runs\. In contrast, replacing the TF\-IDF graph with a PPMI graph, pruning each row to its topK=50K=50neighbors, and applying light PPR damping \(α=0\.3\\alpha=0\.3, one step\) improves the five\-seed RI mean from 19\.4±\\pm0\.7% to 30\.7±\\pm2\.9%, with range 28\.3–34\.6% and a mean gain of 11\.3 percentage points\. The seed42 run reaches 34\.6% \(94/272\), with a question\-bootstrap 95% confidence interval of \[29\.0, 40\.1\]\. The same seed42 RI\+PPMI output reports 1\.4% syntactic accuracy on 2,006 valid syntactic questions\. Theα\\alpha, depth, and top\-KKsettings were selected from sweeps on the same Google analogy benchmark reported here, so these results should be read as exploratory rather than as held\-out model selection\. The bootstrap interval only resamples questions for one favorable seed; it does not capture seed selection, baseline uncertainty, category coverage, or benchmark\-driven hyperparameter selection\. Coverage is narrow: all 272 covered fairytales semantic questions belong to thefamilycategory\.

TABLE III:Fairytales family\-subset analogy accuracy and similarity scores before and after graph diffusion\. The Raw, Post, andΔ\\Deltacolumns are family\-subset semantic analogy accuracy \(%\)\. RI TF\-IDF rows are single runs using random seed 42 \(“seed42”\)\. The RI\+PPMI row reports the mean and sample standard deviation over five RI seeds \(0, 7, 42, 123, and 999\), each refined by the PPMI top\-K=50K=50graph with light PPR damping \(α=0\.3\\alpha=0\.3, one step\)\. The RI\+PPMI Post value shown \(30\.7%\) is the five\-seed mean; the single best seed \(seed42\) reaches 34\.6%, with a question\-bootstrap 95% confidence interval of \[29\.0, 40\.1\] over 272 validfamilyquestions\. In the SimLex and WordSim columns, each cell contains two Spearmanρ\\rhovalues written as raw/post, i\.e\. the correlation before diffusion and after diffusion respectively; these are two separate scores, not a fraction\. For example, RI TF\-IDF SimLex “\-0\.056/0\.093” meansρ=−0\.056\\rho=\-0\.056on the raw vectors andρ=0\.093\\rho=0\.093after diffusion\. RI\+PPMI similarity uses seed42 post\-diffusion vectors\. SimLex uses 889 of 999 valid pairs and WordSim uses 225 of 353 valid pairs for all fairytales rows\.
### VI\-BBloom Filters versus Random Indexing

The Bloom result is a negative result for the tested corrected configuration \(m=200m=200,h=5h=5, top\-20 neighbors\), not a broad claim about all Bloom\-style sketches\. The performance gap is consistent with several possible factors: loss of frequency information under OR accumulation, hash collisions at moderate bit density, and distortion of cosine geometry after bipolar recoding\. Isolating each factor would require a separate ablation\.

TABLE IV:Bloom filter vs\. Random Indexing initialization on fairytales family\-subset analogies \(%\)\. Diffusion uses the PPMI top\-K=50K=50graph\. The RI row reports the five\-seed mean; Bloom is a single corrected configuration\.
### VI\-CEffect of Normalization

Table[V](https://arxiv.org/html/2608.05724#S6.T5)partially ablates normalization and graph\-construction choices when applied to the Random Indexing \(TF\-IDF\) initialization\. Robust scaling alone improves the no\-diffusion baseline on both corpora\. Adding a diffusion step with onlyℓ2\\ell\_\{2\}normalization reduces accuracy, indicating that plainℓ2\\ell\_\{2\}normalization after neighborhood averaging can remove useful signal\. TF\-IDF diffusion plus robust scaling is only neutral or marginal on RI, reaching 19\.1% on fairytales and 5\.3% on text8\. PPR damping on the TF\-IDF graph improves fairytales RI to 26\.1% atα=0\.5\\alpha=0\.5and three steps, but the strongest RI repair comes from the PPMI top\-K=50K=50graph: 30\.7±\\pm2\.9% on fairytales \(best seed 34\.6%\) and 12\.6% on text8\. Table[VI](https://arxiv.org/html/2608.05724#S6.T6)provides text8 baselines for comparison\.

TABLE V:Effect of normalization and graph construction on RI analogy accuracy \(%\)\. Fairytales values are family\-subset semantic accuracies\. The PPMI fairytales row reports a five\-seed mean; other fairytales ablation rows are seed42 single runs\.TABLE VI:Text8 sub2m analogy accuracy \(%\) for selected baselines and the RI\+PPMI pipeline\. Valid columns report the number of evaluated Google analogy questions covered by each vocabulary\.On text8, RI\+PPMI is not competitive at scale\. CBOW and Skip\-gram are substantially higher on semantic accuracy, though their 380 valid semantic questions differ from the 506 valid semantic questions covered by the RI and SVD vocabularies\. RI\+PPMI reaches only 1\.4% syntactic accuracy on 8,946 covered questions\. The larger\-corpus results therefore fail to match neural baselines rather than merely weakening the fairytales pattern, and the neural baselines are single\-run comparisons\.

### VI\-DPPR Damping and Similarity

Repeated diffusion without damping quickly leads to oversmoothing \(Figure[2](https://arxiv.org/html/2608.05724#S6.F2)\)\. Performance peaks early and then collapses for most initializations\. On the TF\-IDF graph, the best PPR setting for fairytales RI isα=0\.5\\alpha=0\.5with three steps, reaching 26\.1%\. This improves over ordinary TF\-IDF diffusion but remains below the 30\.7% PPMI five\-seed mean and the 34\.6% best seed\. The similarity results in Table[III](https://arxiv.org/html/2608.05724#S6.T3)also show that strict similarity \(SimLex\-999\) and broader relatedness \(WordSim\-353\) do not move uniformly under diffusion\. The seed42 RI\+PPMI run improves WordSim to 0\.264 after rounding from 0\.2638, while the RI TF\-IDF post\-diffusion WordSim value rounds to the same number from 0\.2640\. Its SimLex correlation is only 0\.020, worse than the RI TF\-IDF post\-diffusion score of 0\.093 and worse than every raw non\-RI baseline\.

![Refer to caption](https://arxiv.org/html/2608.05724v1/x2.png)Figure 2:Effect of repeated TF\-IDF diffusion steps on fairytales family\-subset accuracy\. Plain TF\-IDF diffusion oversmooths quickly, while PPR damping partially mitigates the collapse\.
### VI\-ERuntime Comparison

Table[VII](https://arxiv.org/html/2608.05724#S6.T7)reports wall\-clock training time for each method on the fairytales corpus\. All methods were timed on the same machine \(RTX 5060, 8 GB\)\. The RI\+PPMI time was measured using the actual pipeline behind the reported result: Random Indexing initialization followed by PPMI graph construction and one residual averaging step withK=50K=50,α=0\.3\\alpha=0\.3, and forced graph\-cache recomputation\.444A reproducibility detail is that SVD and RI initialization runs used window 10 following their defaults, while diffusion graphs used window 8\. This window size difference affects co\-occurrence density and should be noted when interpreting runtime and accuracy comparisons\.

TABLE VII:Wall\-clock training time on fairytales corpus\. Accuracy reports raw/pre\-diffusion family\-subset accuracy for consistency; the RI\+PPMI final mean is 30\.7±\\pm2\.9%\.These timings do not support a speed claim\. CBOW, Binary\+SVD, and PPMI\+SVD are faster than the RI\+PPMI pipeline under these runs, while Skip\-gram is slower\. The comparison is also confounded by window choices, so it should not be used as a clean cross\-method accuracy comparison\. The useful conclusion is narrower: graph construction quality, especially PPMI weighting with top\-KKpruning, matters more than simply applying TF\-IDF diffusion to an existing embedding\.

### VI\-FMemory Analysis

The best fairytales PPMI graph contains 279,150 directed edges after top\-K=50K=50pruning\. With\|𝒱\|=18,254\|\\mathcal\{V\}\|=18\{,\}254andd=200d=200, a single float32 embedding matrix requires about 14\.6 MB, while a float64 working matrix requires about 29\.2 MB\. A CSR graph with float64 weights and 32\-bit indices requires about 3\.4 MB for edge values, column indices, and row pointers\. The core working state is therefore roughly 62 MB for two float64 embedding matrices plus the graph, or about 91 MB if an additional accumulator matrix is materialized\. The JSON files used in the experiments are larger because they store decimal text for reproducibility; they are not required by the algorithm itself\. The result establishes the sparse working\-state scale of RI\+PPMI\. We do not report a sparse versus sparse memory ratio against PPMI\+SVD because the experiment logs do not contain measured peak memory for that baseline\.

## VIILimitations

The positive result is narrow\. On fairytales, all 272 covered semantic questions come from the Google benchmark’s family category, so the headline metric is family\-subset analogy accuracy rather than broad semantic analogy accuracy\. Fairytales syntactic coverage is larger at 2,006 valid questions, but the selected seed42 RI\+PPMI run reaches only 1\.4% syntactic accuracy\. The PPMI graph hyperparameters were selected from sweeps on the same analogy benchmark that is reported, so the result is exploratory and not a held\-out selection result\.

The reported RI\+PPMI configuration also mixes context windows: the Random Indexing initialization used window 10, while the PPMI graph used window 8\. This follows the existing experiment outputs and is disclosed rather than equalized\. On text8, RI\+PPMI is not competitive with the single\-run CBOW and Skip\-gram baselines, and the semantic valid\-question counts differ across vocabularies\. The best analogy configuration remains weak on strict similarity, with SimLexρ=0\.020\\rho=0\.020for seed42 RI\+PPMI\. Finally, the Bloom result covers only the tested corrected configuration \(m=200m=200,h=5h=5, top\-20 neighbors\); broader claims about Bloom\-style embedding sketches would require additional sweeps\.

## VIIIConclusion

A sparse embedding pipeline based on global PPMI graph construction and iterative graph averaging was examined\. It avoids dense co\-occurrence matrix materialization, dense factorization, and gradient training, but it still constructs sparse global co\-occurrence statistics and a sparse graph operator\. The experiments highlight three main observations\.

First, Bloom filter sketches underperform Random Indexing in the tested corrected configuration\. The performance difference is consistent with loss of frequency information under OR accumulation and distortion of cosine geometry after bipolar recoding, but this mechanism remains a hypothesis because the factors were not isolated\.

Second, PPMI graph construction with top\-KKpruning is a useful repair for weak RI embeddings, not a generally competitive embedding method\. On the fairytales dataset, RI improves from 19\.4±\\pm0\.7% to 30\.7±\\pm2\.9% with a PPMI top\-K=50K=50graph, performing the best with a seed of 34\.6%\. That result is narrow: all 272 covered semantic questions are in thefamilycategory, and the seed42 bootstrap interval \[29\.0, 40\.1\] is broad\. On text8 sub2m, RI\+PPMI reaches 12\.6% semantic and 1\.4% syntactic accuracy, below the reported neural baselines\.

Third, in the single tested runs, diffusion reduced accuracy for stronger fitted embeddings under the tested settings\. It reduces PPMI\+SVD from 26\.8% to 19\.9%, Binary\+SVD from 29\.0% to 19\.5%, CBOW from 25\.7% to 12\.9%, and Skip\-gram from 22\.1% to 19\.1%\. The best analogy configuration is also weak on strict similarity: seed42 RI\+PPMI has SimLexρ=0\.020\\rho=0\.020\. Future work should explore richer graph construction techniques, adaptive schedules for the damping parameterα\\alpha, and evaluation on downstream tasks, while treating low\-resource and domain\-specific settings as hypotheses rather than established application wins\.

## Code Availability

## References

- \[1\]T\. Mikolov, K\. Chen, G\. Corrado, and J\. Dean\.Efficient estimation of word representations in vector space\.InICLR Workshop, 2013\.
- \[2\]J\. Pennington, R\. Socher, and C\. D\. Manning\.GloVe: Global vectors for word representation\.InEMNLP, 2014\.
- \[3\]M\. Baroni, G\. Dinu, and G\. Kruszewski\.Don’t count, predict\! A systematic comparison of context\-counting vs\. context\-predicting semantic vectors\.InACL, 2014\.
- \[4\]O\. Levy, Y\. Goldberg, and I\. Dagan\.Improving distributional similarity with lessons learned from word embeddings\.Transactions of the Association for Computational Linguistics, 3:211–225, 2015\.
- \[5\]F\. Hill, R\. Reichart, and A\. Korhonen\.SimLex\-999: Evaluating semantic models with \(genuine\) similarity estimation\.Computational Linguistics, 41\(4\):665–695, 2015\.
- \[6\]L\. Finkelstein, E\. Gabrilovich, Y\. Matias, E\. Rivlin, Z\. Solan, G\. Wolfman, and E\. Ruppin\.Placing search in context: The concept revisited\.InWWW, 2001\.
- \[7\]T\. Mikolov, W\.\-t\. Yih, and G\. Zweig\.Linguistic regularities in continuous space word representations\.InNAACL\-HLT, 2013\.
- \[8\]F\. Pedregosa, G\. Varoquaux, A\. Gramfort, V\. Michel, B\. Thirion, O\. Grisel, M\. Blondel, P\. Prettenhofer, R\. Weiss, V\. Dubourg, J\. Vanderplas, A\. Passos, D\. Cournapeau, M\. Brucher, M\. Perrot, and E\. Duchesnay\.Scikit\-learn: Machine learning in Python\.Journal of Machine Learning Research, 12:2825–2830, 2011\.
- \[9\]P\. Kanerva, J\. Kristoferson, and A\. Holst\.Random indexing of text samples for latent semantic analysis\.InCognitive Science Society, 2000\.
- \[10\]M\. Faruqui, J\. Dodge, S\. K\. Jauhar, C\. Dyer, E\. Hovy, and N\. A\. Smith\.Retrofitting word vectors to semantic lexicons\.InNAACL\-HLT, 2015\.
- \[11\]J\. Klicpera, A\. Bojchevski, and S\. Günnemann\.Predict then propagate: Graph neural networks meet personalized PageRank\.InICLR, 2019\.
- \[12\]Q\. Li, Z\. Han, and X\. Wu\.Deeper insights into graph convolutional networks for semi\-supervised classification\.InAAAI, 2018\.
- \[13\]K\. Oono and T\. Suzuki\.Graph neural networks exponentially lose expressive power for node classification\.InICLR, 2020\.
- \[14\]J\. Mu and P\. Viswanath\.All\-but\-the\-top: Simple and effective postprocessing for word representations\.InICLR, 2018\.
- \[15\]O\. Levy and Y\. Goldberg\.Neural word embedding as implicit matrix factorization\.InNIPS, 2014\.
- \[16\]E\. Serra and A\. Karatzoglou\.Getting deep recommenders fit: Bloom embeddings for sparse binary input/output\.InRecSys, 2018\.
- \[17\]D\. Svenstrup, J\. M\. Hansen, and O\. Winther\.Hash embeddings for efficient word representations\.InNIPS Workshop, 2017\.
- \[18\]M\. Sahlgren\.An introduction to random indexing\.InMethods of Information Extraction and Retrieval, 2005\.
- \[19\]B\. H\. Bloom\.Space/time trade\-offs in hash coding with allowable errors\.Communications of the ACM, 13\(7\):422–426, 1970\.
- \[20\]R\.\-J\. Zhu, Y\. Zhang, E\. Sifferman, T\. Sheaves, Y\. Wang, D\. Richmond, P\. Zhou, and J\. K\. Eshraghian\.Scalable matmul\-free language modeling\.arXiv preprint arXiv:2406\.02528, 2024\.
- \[21\]N\. Halko, P\. G\. Martinsson, and J\. A\. Tropp\.Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions\.SIAM Review, 53\(2\):217–288, 2011\.