Graph partition and PPR sparsification

Two library services (no MCP tool) for graphs given as adjacency lists (number[][], node ids 0..n-1, treated as undirected and unweighted).

Use

import { MincutService, SparsificationService } from 'agentdb/controllers';

const mincut = new MincutService({ algorithm: 'stoer-wagner' });
await mincut.initialize();
const cut = await mincut.stoerWagnerMincut(adjacency);
// cut.algorithm === 'stoer-wagner-wasm' when the native path ran
// cut.partitions: [sideA, sideB], cut.cutSize, cut.cutEdges: [u, v][] (u < v, each edge once)

const ppr = new SparsificationService({ method: 'ppr', topK: 20 });
const top = await ppr.sparsify(seedNode, adjacency);
// top.method === 'ppr-napi' | 'ppr-wasm' | 'ppr-fallback'; top.topKIndices; top.scores (Float32Array)

Check which path ran: mincut.getBackend() returns 'wasm' or 'fallback'; ppr.getPprRuntime() returns 'napi', 'wasm' or 'fallback'.

Know the costs

• Min cut construction grows about quadratically: ~0.15 s at 1,000 nodes, ~0.35 s at 2,000, ~1.7 s at 4,000, ~6.5 s at 8,000. It also grows with edges: ~2.2 s at 2,000 nodes / 51k edges, ~15 s for a 1,000-node complete graph (500k edges). Graphs above wasmMaxNodes (default 2000) or wasmMaxEdges (default 20,000) use the fallback. Raise them only for one-off analysis: new MincutService({ algorithm: 'stoer-wagner', wasmMaxNodes: 8000, wasmMaxEdges: 100000 }).
• A global min cut is often one low-degree node against the rest. That is the correct answer, not a balanced split. partition() with maxPartitionSize set splits any larger side into equal chunks (algorithm gains +bounded), which is what partitionedAttention uses. stoerWagnerMincut() never splits.
• Results are cached by graph content, so a repeated query on the same graph is free.
• Native PPR runs 20 power iterations and keeps the mass of a node with no edges on that node. The fallback drops it, so scores differ on graphs with dead-end nodes.
• AttentionService.sparseAttention() and partitionedAttention() call these services, so they pick up the native paths too.

Don't

• Don't read cutSize from algorithm: 'karger' or 'flow-based' as a global min cut. Karger is randomized, and flow-based is an s-t cut between nodes 0 and n-1.
• Don't pass object-keyed adjacency ({0: [1]}). Pass arrays.