epic(performance): polish scale and performance for remaining M4 analyst algorithms

[cursor]

Tracker Purpose

Coordinate scale and performance polish for every public analyst algorithm that
was not already covered by the finite M4 compute-kernel batch
(#342 cosine KNN / cosine / filtered KNN, #343 PageRank, #344 Node2Vec walk generation).

This tracker is a native child of #335 and is blocked by one issue per remaining
algorithm. It expands M4 beyond the original finite close ledger by explicit
maintainer/user request after #345.

Already shipped (do not duplicate)

• pagerank — perf(exec): parallelize PageRank updates deterministically #343
• knn, cosine, filtered_knn — perf(exec): parallelize exact cosine KNN by canonical source #342
• node2vec walk corpus — perf(exec): parallelize Node2Vec walk generation deterministically #344 (training polish tracked separately below)

Shared prerequisites (do not re-implement)

• feat(api): define a bounded embedded execution resource policy #337 embedded resource policy / private ComputePool
• perf(exec): consume persisted CSR without edge-scale hash-map expansion #340 CSR-native adjacency views
• perf(exec): shape analyst outputs directly into bounded Arrow batches #341 bounded Arrow shaping
• test(performance): establish the M4 embedded baseline and entry gate #334 / test(performance): reconcile final M4 exit evidence and scale claims #345 evidence methodology

Child algorithms

Family	by=	Bottleneck class
rank	adamic_adar	pairwise neighborhood aggregate
rank	article_rank	CPU-bound iterative ranking
rank	betweenness	BFS-heavy Brandes betweenness
rank	celf	influence-maximization lazy forward search
rank	closeness	BFS-heavy all-sources closeness
rank	clustering_coefficient	local triangle/wedge counting
rank	common_neighbors	pairwise neighborhood aggregate
rank	degree	degree scan / normalization
rank	eigenvector	CPU-bound iterative eigenvector
rank	harmonic_closeness	BFS-heavy all-sources harmonic closeness
rank	hits_authority	CPU-bound iterative HITS
rank	hits_hub	CPU-bound iterative HITS
rank	k_core	core-decomposition peeling
rank	preferential_attachment	pairwise neighborhood aggregate
rank	resource_allocation	pairwise neighborhood aggregate
rank	total_neighbors	pairwise neighborhood aggregate
rank	triangles	local triangle counting
cluster	approximate_max_k_cut	combinatorial local-search cut
cluster	biconnected	DFS-heavy biconnected components
cluster	components	Union-Find / BFS components
cluster	fastgreedy	agglomerative modularity hierarchy
cluster	girvan_newman	repeated edge-betweenness (BFS-heavy)
cluster	hdbscan	density clustering on embeddings
cluster	infomap	flow / random-walk clustering
cluster	k_core_decomposition	core-decomposition peeling
cluster	k_means	embedding-space iterative clustering
cluster	label_propagation	label-propagation iterations
cluster	leading_eigenvector	spectral / modularity bisection
cluster	leiden	multilevel community refinement
cluster	louvain	multilevel modularity optimization
cluster	modularity_optimization	single-level modularity local moves
cluster	speaker_listener	overlapping label propagation (SLPA)
cluster	spinglass	spin-glass / MCMC community
cluster	strongly_connected	Tarjan SCC (DFS-heavy)
cluster	walktrap	random-walk distance clustering
similar	filtered_node_similarity	O(N·C) filtered Jaccard similarity
similar	node_similarity	O(N²) Jaccard neighborhood similarity
path	astar	heuristic SSSP
path	bellman_ford	edge-relax iterative SSSP
path	bfs	BFS traversal
path	delta_stepping	bucketed SSSP (serial today; natural parallel candidate)
path	dfs	DFS traversal
path	dijkstra	priority-queue SSSP
path	dijkstra_all_pairs	all-pairs Dijkstra
path	floyd_warshall	O(N³) all-pairs shortest paths
path	gomory_hu_tree	repeated max-flow / cut tree
path	max_flow	max-flow
path	max_flow_edges	max-flow edge assignment
path	min_cost_max_flow	min-cost max-flow
path	min_cost_max_flow_edges	min-cost max-flow edge assignment
path	min_cut	min-cut / max-flow dual
path	min_cut_edges	min-cut edge assignment
path	min_steiner_tree	exact Steiner subset search
path	prize_collecting_steiner_tree	exact prize-Steiner subset search
path	random_walk	random-walk generation
path	transitive_closure	reachability / transitive closure
path	yens	k-shortest paths (repeated Dijkstra)
matching	max_bipartite_matching	bipartite matching
matching	max_cardinality_matching	general-graph blossom matching
matching	max_weight_matching	weighted blossom matching
embedding	fast_random_projection	sparse random-projection embedding
embedding	graphsage	embedding train (neighbor aggregation)
embedding	hashgnn	embedding train (hashing GNN)
embedding	node2vec	embedding train (serial skip-gram after parallel walks)
analyze	articulation_points	DFS low-link / cut vertices
analyze	bridges	DFS low-link / cut edges
analyze	chromatic_number	exact coloring search
analyze	conductance	partition cut metric
analyze	count_automorphisms	IR / backtracking automorphism search
analyze	dag_longest_path	DAG DP longest path
analyze	dag_longest_path_weighted	weighted DAG DP
analyze	dyad_census	pairwise dyad enumeration
analyze	edge_coloring	greedy edge coloring
analyze	euler_circuit	Euler tour construction
analyze	euler_path	Euler path construction
analyze	find_cycles	Johnson simple-cycle enumeration
analyze	has_euler_circuit	degree / connectivity check
analyze	has_euler_path	degree / connectivity check
analyze	is_dag	topological / cycle check
analyze	is_planar	planarity test
analyze	k1_coloring	greedy distance-1 coloring
analyze	maximum_spanning_tree	MST (Kruskal-style)
analyze	minimum_k_spanning_tree	k distinct spanning-tree enumeration
analyze	minimum_spanning_tree	MST (Kruskal-style)
analyze	modularity	partition modularity score
analyze	node_coloring	greedy vertex coloring
analyze	topological_sort	Kahn topological order
analyze	transitivity	global triangle / triad ratio
analyze	triad_census	triad enumeration
analyze	triangle_count	global triangle counting

Count: 90 child issues.

Closure

Close this tracker when every child is closed through merged work or an explicit
evidence-backed disposition, then reassess #335.

Related Issues

• epic(performance): close M4 embedded performance and scale #335 — M4 close tracker; this issue blocks it.
• test(performance): establish the M4 embedded baseline and entry gate #334 / test(performance): reconcile final M4 exit evidence and scale claims #345 — evidence contract.
• feat(api): define a bounded embedded execution resource policy #337 / perf(exec): consume persisted CSR without edge-scale hash-map expansion #340 / perf(exec): shape analyst outputs directly into bounded Arrow batches #341 — shared infrastructure.

[coderabbitai]

🔗 Related PRs

#485 - test(performance): establish M4 embedded entry baseline (#334) [merged]
#492 - perf(exec): parallelize PageRank updates deterministically (#343) [open]
#493 - perf(exec): parallelize Node2Vec walk generation (#344) [open]
#494 - perf(exec): parallelize exact cosine KNN by source (#342) [open]
#496 - test(performance): reconcile M4 exit evidence and scale claims (#345) [closed]

---

📝 Issue Planner

_{Check the box below or use the @coderabbitai plan command to generate an implementation plan and prompts that you can use with your favorite coding assistant.}

• Create Plan

---

🧪 Issue enrichment is currently in open beta.

You can configure auto-planning by selecting labels in the issue_enrichment configuration.

To disable automatic issue enrichment, add the following to your .coderabbit.yaml:

issue_enrichment:
  auto_enrich:
    enabled: false

💬 Have feedback or questions? Drop into our discord!