Low-dependency TypeScript graph algorithms for citation network analysis: novel exploration, MI variants, and path ranking.
- Exploration algorithms: BASE, DOME, EDGE, HAE, PIPE, SAGE, REACH, MAZE + 6 variants (TIDE, LACE, WARP, FUSE, SIFT, FLUX) + baselines
- MI variants: Jaccard, Adamic-Adar, SCALE, SKEW, SPAN, ETCH, NOTCH, Unified Adaptive
- Path ranking: PARSE + baselines (Katz, Communicability, PageRank, etc.)
- Seed selection: GRASP, STRIDE, CREST, SPINE, CRISP, BRISK, BASIL, PRISM, OMNIA, Stratified
- Subgraph extraction: ego-network, k-core, k-truss, motif, induced, filter
- Optional WebGPU acceleration
- Async support: Generator coroutine protocol, sync/async runners, all algorithms available as
*Asyncvariants
pnpm add graphwiseimport { AdjacencyMapGraph, dome, parse, jaccard } from "graphwise";
const graph = AdjacencyMapGraph.undirected();
// add nodes and edges...
const result = dome(graph, seeds);
const ranked = parse(graph, result.paths, { mi: jaccard });Boundary-free Adaptive Seeded Expansion (BASE) discovers the neighbourhood around seed nodes without any configuration. You provide seeds and a priority function; BASE expands outward, visiting the most interesting nodes first and recording paths when search frontiers from different seeds collide. It stops naturally when there is nothing left to explore — no depth limits, no size thresholds, no parameters to tune.
Three key properties:
-
Priority-ordered exploration: the vertex with globally minimum priority
$\pi(v)$ is expanded next across all frontiers - Frontier collision detection: when a vertex is reached by multiple frontiers, the connecting path is recorded
- Implicit termination: halts when all frontier queues are empty; no depth bound or size threshold
Explores low-connectivity nodes before hubs. In a social network, DOME visits niche specialists before reaching the well-connected influencers, discovering the quiet corners of the graph before the busy crossroads.
where
| Algorithm | Priority Function | Phases |
|---|---|---|
| DOME | Degree (hub deferral) | 1 |
| EDGE | Local neighbourhood type entropy | 1 |
| HAE | User-supplied type entropy (generalises EDGE) | 1 |
| PIPE | Path potential (neighbours visited by other frontiers) | 1 |
| SAGE | Salience accumulation from discovered paths | 2 |
| REACH | Rolling MI estimates of discovered path quality | 2 |
| MAZE | PIPE + SAGE + adaptive termination | 3 |
| TIDE | Sum of node + all-neighbour degrees | 1 |
| LACE | Average MI to same-frontier visited nodes | 1 |
| WARP | Cross-frontier bridge score | 1 |
| FUSE | Weighted degree + MI blend | 1 |
| SIFT | MI threshold with degree fallback | 1 |
| FLUX | Density-adaptive strategy switching | 1 |
Finds nodes that sit at the boundary between different kinds of things. If a person's friends include scientists, artists, and engineers (high type diversity), EDGE visits them early — they are likely bridges between communities.
where
Rushes towards nodes that are about to connect two search frontiers. When expanding from multiple seeds, PIPE detects that a node's neighbours have already been reached by another seed's frontier — meaning a connecting path is one step away.
where
Learns from its own discoveries. Phase 1 explores by degree (like DOME). Once the first path is found, SAGE switches to Phase 2: nodes that appear in many discovered paths get top priority, guiding expansion towards structurally rich regions.
where
Uses the quality of already-discovered paths to steer future exploration. Phase 1 explores by degree. Once paths are found, REACH asks "which unexplored nodes look structurally similar to the endpoints of my best paths?" and prioritises those — seeking more of what already worked.
where
Combines the best of PIPE and SAGE across three phases. First, it races to find initial paths using path potential (like PIPE). Then it refines exploration using salience feedback (like SAGE). Finally, it decides when to stop based on whether it's still discovering diverse, high-quality paths.
Phase 1 uses path potential until
Avoids dense clusters by looking at total neighbourhood connectivity. A node surrounded by other well-connected nodes gets deferred; a node in a quiet corner of the graph gets explored first.
Related to EDGE but uses raw degree sums rather than entropy.
Explores towards nodes that are most similar to what the frontier has already seen. If a candidate node shares many neighbours with the explored region, it gets priority — building outward from a coherent core.
Related to HAE but uses MI to visited nodes rather than type entropy.
Aggressively prioritises nodes that look like they will connect two search frontiers, regardless of their degree. If a node's neighbours have been visited by another seed's search, it gets top priority.
Related to PIPE but omits the degree numerator, making it more aggressive at prioritising bridge nodes.
Balances two signals simultaneously: how connected a node is (degree) and how strongly it relates to the explored region (MI). The weight
Related to SAGE but uses continuous blending rather than two-phase transition.
Acts as a gate: nodes with MI above a threshold get MI-based priority (explore the promising ones); nodes below the threshold get deferred with a large degree-based penalty (ignore the unpromising ones). A binary version of REACH's continuous approach.
Related to REACH but uses a hard threshold instead of continuous MI-weighted priority.
Adapts its strategy to the local topology of each node. In dense regions it uses low-degree-first exploration (like EDGE); near frontier boundaries it uses bridge detection (like PIPE); in sparse regions it falls back to degree ordering (like DOME). Different parts of the graph are explored with different strategies simultaneously.
Related to MAZE but adapts spatially (per-node) rather than temporally (per-phase).
| Algorithm | Priority Function | Description |
|---|---|---|
| BFS | Discovery order (FIFO) | Standard breadth-first search |
| DFS | Negative iteration (LIFO) | Depth-first exploration |
| Frontier-Balanced | Round-robin across frontiers | Fair inter-frontier distribution |
| Random Priority | Seeded hash (FNV-1a) | Null hypothesis baseline |
| k-Hop | BFS with depth limit |
Fixed-depth ego-network extraction |
| Random Walk | Stochastic neighbour selection | Random walk with restart ( |
Path Aggregation Ranked by Salience Estimation (PARSE) ranks discovered paths by asking "how consistently strong is every edge along this path?" It uses the geometric mean of per-edge MI scores, which means one weak link drags down the entire path — unlike arithmetic mean where a strong edge can compensate for a weak one. A 10-hop path with consistently good edges scores the same as a 2-hop path with equally good edges.
where
MI variants answer the question "how strongly are two connected nodes related?" Each measures the overlap between their neighbourhoods, then optionally weights by structural properties like density, degree rarity, clustering, or entity type. PARSE uses these as per-edge scores in its geometric mean.
What fraction of combined neighbours do two nodes share? If Alice and Bob know 3 of the same people out of 10 total acquaintances between them, their Jaccard score is 0.3.
Counts shared neighbours, but recognises that sharing a rare connection is more meaningful than sharing a popular one. If two researchers both cite a niche paper, that says more about their relationship than both citing a famous textbook.
Adjusts for graph density. In a dense network where everyone knows everyone, sharing neighbours is expected and less meaningful. In a sparse network, the same overlap is rare and significant. SCALE divides Jaccard by density to make scores comparable across differently-dense regions.
where
Rewards edges between rare (low-degree) nodes and penalises edges involving hubs. Like TF-IDF in search engines: a connection between two niche nodes is more informative than a connection between two mega-hubs that connect to everything.
where
Rewards edges that bridge separate communities and penalises edges within tight-knit groups. If both endpoints sit in dense clusters where everyone knows everyone (high clustering coefficient), the edge is probably redundant. If at least one endpoint is a bridge between groups, the edge is structurally interesting.
where
Boosts edges of rare types. If a graph has 1000 "knows" edges but only 5 "mentors" edges, a mentoring relationship is worth more than an acquaintanceship. ETCH multiplies Jaccard by the log-rarity of the edge type.
Requires edge-type annotations; falls back to Jaccard when unavailable.
Boosts edges connecting rare node types. In a graph with 500 people but only 10 organisations, an edge involving an organisation is more distinctive. NOTCH multiplies Jaccard by the log-rarity of both endpoint types.
where
| Measure | Formula | Description |
|---|---|---|
| Cosine Similarity | Neighbourhood vector cosine; more tolerant of degree asymmetry than Jaccard | |
| Sorensen-Dice | Harmonic mean variant of Jaccard; equivalent to F1-score | |
| Resource Allocation | Like Adamic-Adar but without the log; penalises hubs more aggressively | |
| Overlap Coefficient | Fraction of smaller neighbourhood that is shared; less sensitive to degree asymmetry | |
| Hub Promoted | Promotes hub connections; edges involving high-degree nodes score higher |
| Measure | Formula |
|---|---|
| Katz Index | |
| Communicability | |
| Resistance Distance | |
| Jaccard Arithmetic Mean | |
| Degree-Sum | |
| Widest Path | |
| PageRank | Stationary distribution of random walk with damping |
| Betweenness | Fraction of shortest paths through node |
| Hitting Time |
|
| Shortest Path | Hop count on unweighted graphs |
| Random | Uniform random score (null baseline) |
Graph-agnostic Representative seed pAir Sampling picks starting points for exploration algorithms. Given a graph you have never seen before, GRASP streams through its edges, samples a representative set of nodes, clusters them by structural role (hubs, bridges, peripherals), and returns seed pairs that cover the full range of structural diversity — without loading the entire graph into memory.
Three phases:
-
Reservoir sampling: stream graph edges; maintain a reservoir of
$N$ nodes -
Structural features: for each sampled node compute
$\log(\deg + 1)$ , clustering coefficient, approximate PageRank -
Cluster and sample: MiniBatchKMeans into
$K$ groups; sample within-cluster and cross-cluster pairs
import { ... } from 'graphwise'; // Everything
import { ... } from 'graphwise/graph'; // Graph data structures
import { ... } from 'graphwise/exploration'; // Exploration algorithms
import { ... } from 'graphwise/ranking'; // PARSE + baselines
import { ... } from 'graphwise/ranking/mi'; // MI variants
import { ... } from 'graphwise/seeds'; // Seed selection
import { ... } from 'graphwise/traversal'; // Graph traversal
import { ... } from 'graphwise/structures'; // Data structures
import { ... } from 'graphwise/extraction'; // Subgraph extraction
import { ... } from 'graphwise/utils'; // Utilities
import { ... } from 'graphwise/gpu'; // WebGPU acceleration
import { ... } from 'graphwise/schemas'; // Zod schemas
import { ... } from 'graphwise/async'; // Async runners & protocolAll algorithms are available as *Async variants for use with remote or lazy graph data sources:
import { domeAsync, parseAsync, jaccardAsync } from "graphwise";
import type { AsyncReadableGraph } from "graphwise/graph";
// Your async graph implementation
const remoteGraph: AsyncReadableGraph = createRemoteGraph();
const result = await domeAsync(remoteGraph, seeds, {
signal: controller.signal,
onProgress: (stats) => console.log(stats),
});
const ranked = await parseAsync(remoteGraph, result.paths, {
mi: jaccardAsync,
});pnpm build # Build ESM + CJS + UMD
pnpm test # Run tests
pnpm test:coverage # Run tests with coverage
pnpm typecheck # Type check only
pnpm lint # Run ESLint
pnpm validate # Full QA: typecheck + lint + test + build