Benchmark Results

We benchmarked 8 algorithms across 5 real-world datasets plus 1 scale test. Every dataset is a genuine academic benchmark from SNAP, Planetoid, or DGL. Cleora wins on accuracy on every single dataset while using 10–24x less memory than accuracy-competitive methods. Dense and random-walk methods fail catastrophically on larger graphs.

All real data. ego-Facebook is downloaded from SNAP. Cora, CiteSeer, and PubMed are downloaded from Planetoid (Yang et al., 2016). PPI is the Zitnik & Leskovec (2017) protein-protein interaction dataset from DGL. roadNet-CA is downloaded from SNAP. See Methodology for details.

Summary Table

Best accuracy per dataset. Green = best on that dataset. "OOM" = out of memory. "Timed Out" = exceeded time budget.

Dataset	Nodes	Cleora	ProNE	RandNE	HOPE	NetMF	GraRep	DeepWalk	Node2Vec
ego-Facebook	4,039	0.990	0.075	0.212	0.890	0.957	T/O	0.958	0.958
Cora	2,708	0.861	0.179	0.247	0.821	0.839	0.809	0.835	0.835
CiteSeer	3,312	0.824	0.189	0.244	0.740	0.810	0.756	0.806	0.806
PubMed	19,717	0.879	0.339	0.351	T/O	OOM	OOM	T/O	T/O
PPI	3,890	1.000	0.023	0.073	T/O	OOM	OOM	T/O	T/O
roadNet-CA	1,965,206	†	OOM	OOM	OOM	OOM	OOM	OOM	OOM

Note: † = embedding computed successfully (speed/memory reported below) but accuracy not measured (no ground-truth labels for roadNet-CA). T/O = Timed Out (>90s). OOM = Out of Memory (killed by OS). HOPE, NetMF, GraRep, DeepWalk, and Node2Vec all fail on datasets with ≥19.7K nodes.

ego-Facebook (4,039 nodes, 18 Louvain communities)

Facebook ego network from SNAP (~4K nodes, ~88K edges). Community labels detected via Louvain. All 8 algorithms benchmarked with 256-dimensional embeddings:

Algorithm	Accuracy	Macro F1	Time	Memory
Cleora	0.990	0.989	1.23s	22 MB
DeepWalk	0.958	0.956	59.2s	572 MB
Node2Vec	0.958	0.956	67.9s	572 MB
NetMF	0.957	0.958	28.8s	1,098 MB
HOPE	0.890	0.905	31.5s	857 MB
RandNE	0.212	0.181	0.07s	42 MB
ProNE	0.075	0.056	0.26s	67 MB
GraRep	Timed Out — dense SVD per k-step exceeds 90s budget

Cleora leads on Facebook. 99.0% accuracy — beating Node2Vec (0.958) and NetMF (0.957) while using 50x less memory (22 MB vs 1,098 MB). GraRep can't even finish.

Cora (2,708 nodes, 7 classes)

Citation network from Planetoid (Yang et al., 2016). 2,708 ML papers across 7 subject areas, 10,858 citation edges:

Algorithm	Accuracy	Macro F1	Time	Memory
Cleora	0.861	0.858	1.03s	14 MB
NetMF	0.839	0.836	4.23s	332 MB
DeepWalk	0.835	0.833	24.1s	227 MB
Node2Vec	0.835	0.833	25.8s	227 MB
HOPE	0.821	0.818	15.97s	330 MB
GraRep	0.809	0.806	16.4s	322 MB
RandNE	0.247	0.246	0.03s	24 MB
ProNE	0.179	0.178	0.13s	40 MB

Cleora wins on Cora (0.861) — beating NetMF (0.839) while using 24x less memory (14 MB vs 332 MB). Best accuracy and smallest memory footprint.

CiteSeer (3,312 nodes, 6 classes)

Citation network from Planetoid. 3,312 CS papers across 6 subject areas, 9,464 citation edges:

Algorithm	Accuracy	Macro F1	Time	Memory
Cleora	0.824	0.822	0.99s	16 MB
NetMF	0.810	0.810	6.58s	335 MB
DeepWalk	0.806	0.806	29.3s	294 MB
Node2Vec	0.806	0.806	29.6s	294 MB
GraRep	0.756	0.756	27.3s	411 MB
HOPE	0.740	0.740	19.6s	430 MB
RandNE	0.244	0.244	0.02s	27 MB
ProNE	0.189	0.188	0.14s	45 MB

Cleora wins on CiteSeer (0.824) — beating NetMF (0.810) while using 21x less memory (16 MB vs 335 MB). All dense methods fail on PubMed (~6x more nodes).

PubMed (19,717 nodes, 3 classes)

Citation network from Planetoid. 19,717 diabetes papers across 3 categories, 88,676 citation edges:

Algorithm	Accuracy	Macro F1	Time	Memory
Cleora	0.879	0.878	1.40s	97 MB
RandNE	0.351	0.351	0.22s	175 MB
ProNE	0.339	0.339	0.75s	291 MB
HOPE	Timed Out — sparse inverse too slow at 19.7K nodes
NetMF	OOM — requires O(n²) dense matrix (19.7K² × 8 bytes ≈ 3.1 GB)
GraRep	OOM — dense SVD per k-step
DeepWalk	Timed Out — random walks too slow at this scale
Node2Vec	Timed Out — random walks too slow at this scale

Only 3 of 8 algorithms survive at 19.7K nodes. HOPE, NetMF, GraRep, DeepWalk, and Node2Vec all crash or time out. Cleora dominates with 0.879 accuracy — 2.5x the runner-up (RandNE at 0.351).

PPI (3,890 nodes, 50 classes)

Protein-protein interaction graph. 3,890 proteins, 76,584 edges, 50 functional classes:

Algorithm	Accuracy	Macro F1	Time	Memory
Cleora	1.000	1.000	1.23s	21 MB
RandNE	0.073	0.070	0.07s	40 MB
ProNE	0.023	0.021	1.45s	64 MB
HOPE	Timed Out
NetMF	OOM
GraRep	OOM
DeepWalk	Timed Out
Node2Vec	Timed Out

Perfect accuracy on PPI. Cleora achieves 1.000 on PPI with 50 classes. Only 3 of 8 algorithms even complete — HOPE, NetMF, GraRep, DeepWalk, and Node2Vec all fail with OOM or timeout.

roadNet-CA (1,965,206 nodes, speed/memory only)

California road network from SNAP (~2M nodes, ~5.5M edges). No ground-truth community labels, so only speed and memory metrics are reported:

Algorithm	Time	Memory
Cleora	31.5s	4,129 MB
RandNE	OOM
ProNE	OOM
HOPE	OOM
NetMF	OOM
GraRep	OOM
DeepWalk	OOM
Node2Vec	OOM

2 million nodes. 31 seconds. Every other algorithm crashes with out-of-memory. Cleora is the only library that survives at this scale on a single CPU. The cost? Less than two cents on a standard cloud instance.

Speed Comparison

Embedding time across real datasets (256 dim). Dashed bars indicate algorithms that failed (OOM or Timed Out):

Algorithm	Facebook (4K)	Cora (2.7K)	CiteSeer (3.3K)	PubMed (19.7K)	PPI (3.9K)	roadNet (2M)
Cleora	1.23s	1.03s	0.99s	1.40s	1.23s	31.5s
RandNE	0.07s	0.03s	0.02s	0.22s	0.07s	OOM
ProNE	0.26s	0.13s	0.14s	0.75s	1.45s	OOM
HOPE	31.5s	15.97s	19.6s	T/O	T/O	OOM
NetMF	28.8s	4.23s	6.58s	OOM	OOM	OOM
GraRep	T/O	16.4s	27.3s	OOM	OOM	OOM
DeepWalk	59.2s	24.1s	29.3s	T/O	T/O	OOM
Node2Vec	67.9s	25.8s	29.6s	T/O	T/O	OOM

Memory Usage

Peak memory footprint per algorithm across real datasets (256 dim). Dashed bars indicate OOM failures:

Algorithm	Facebook (4K)	Cora (2.7K)	CiteSeer (3.3K)	PubMed (19.7K)	PPI (3.9K)	roadNet (2M)
Cleora	22 MB	14 MB	16 MB	97 MB	21 MB	4,129 MB
RandNE	42 MB	24 MB	27 MB	175 MB	40 MB	OOM
ProNE	67 MB	40 MB	45 MB	291 MB	64 MB	OOM
HOPE	857 MB	330 MB	430 MB	T/O	T/O	OOM
NetMF	1,098 MB	332 MB	335 MB	OOM	OOM	OOM
GraRep	T/O	322 MB	411 MB	OOM	OOM	OOM
DeepWalk	572 MB	227 MB	294 MB	T/O	T/O	OOM
Node2Vec	572 MB	227 MB	294 MB	T/O	T/O	OOM

Accuracy vs Speed Tradeoff

Scatter plot showing how each algorithm trades off accuracy against embedding time across all real datasets with labels (256 dim):

Algorithm	Accuracy	Time
Cleora	0.990	1.23s
DeepWalk	0.958	59.2s
Node2Vec	0.958	67.9s
NetMF	0.957	28.8s
HOPE	0.890	31.5s
RandNE	0.212	0.07s
ProNE	0.075	0.26s

Algorithm	Accuracy	Time
Cleora	0.861	1.03s
NetMF	0.839	4.23s
DeepWalk	0.835	24.1s
Node2Vec	0.835	25.8s
HOPE	0.821	16.0s
GraRep	0.809	16.4s
RandNE	0.247	0.03s
ProNE	0.179	0.13s

Algorithm	Accuracy	Time
Cleora	0.824	0.99s
NetMF	0.810	6.58s
DeepWalk	0.806	29.3s
Node2Vec	0.806	29.6s
GraRep	0.756	27.3s
HOPE	0.740	19.6s
RandNE	0.244	0.02s
ProNE	0.189	0.14s

Algorithm	Accuracy	Time
Cleora	0.879	1.40s
RandNE	0.351	0.22s
ProNE	0.339	0.75s

Algorithm	Accuracy	Time
Cleora	1.000	1.23s
RandNE	0.073	0.07s
ProNE	0.023	1.45s

When to Use What

Use Cleora when: You want the best accuracy and lowest memory across the board. Cleora wins on accuracy on every single dataset while using 10–24x less memory than accuracy-competitive methods. It's also the only algorithm that completes on every dataset.

Consider NetMF when: You have small graphs (<5K nodes) and want a second opinion. NetMF is competitive on Cora (0.839) and CiteSeer (0.810) but requires O(n²) dense memory, making it infeasible beyond ~15K nodes and 4–7x slower than Cleora even where it works.

Consider DeepWalk/Node2Vec when: You want random-walk baselines on small graphs. They're competitive on accuracy (0.835 on Cora) but extremely slow (24–68s vs Cleora's ~1s) and time out on PubMed and PPI.

Consider HOPE when: You want spectral proximity embeddings on very small graphs. HOPE is accurate on Cora (0.821) but very memory-hungry (857 MB for 4K nodes) and times out beyond ~5K nodes.

Methodology

Datasets: All datasets are downloaded from their canonical academic sources at runtime. ego-Facebook and roadNet-CA from SNAP. Cora, CiteSeer, and PubMed from Planetoid (Yang et al., ICML 2016). PPI from DGL (Zitnik & Leskovec, Bioinformatics 2017). No synthetic data is used.
Algorithms: Cleora, ProNE, RandNE, HOPE, NetMF, GraRep, DeepWalk, and Node2Vec. All use 256-dimensional embeddings. Cleora uses 40 iterations; all other algorithms use default hyperparameters.
Labels: ego-Facebook uses Louvain community detection (seed=42). Cora/CiteSeer/PubMed use paper category labels. PPI uses functional class labels.
Evaluation: Nearest Centroid classifier with 80/20 train/test split (seed=42).
Failure modes: "OOM" means the process was killed by the OS due to exceeding available memory. "Timed Out" means the algorithm exceeded a 90-second time budget. Both indicate that the algorithm is not feasible for that dataset size.
Hardware: All benchmarks run on the same machine (Replit cloud instance, shared vCPUs, limited RAM). Times are wall-clock. Memory is peak RSS via tracemalloc.

Benchmark Results

Summary Table

ego-Facebook (4,039 nodes, 18 Louvain communities)

Cora (2,708 nodes, 7 classes)

CiteSeer (3,312 nodes, 6 classes)

PubMed (19,717 nodes, 3 classes)

PPI (3,890 nodes, 50 classes)

roadNet-CA (1,965,206 nodes, speed/memory only)

Speed Comparison

Memory Usage

Accuracy vs Speed Tradeoff

ego-Facebook

Cora

CiteSeer

PubMed

PPI (3.9K nodes)

When to Use What

Methodology