A graph database stores relationships natively, but the real power comes from analysing those relationships. A friend-of-a-friend query is useful; finding the most influential node in a network of ten thousand users is transformative.
Graph algorithms unlock insights that SQL window functions and recursive CTEs can only approximate. Whether you are ranking web pages, detecting fraud rings, optimising delivery routes, or finding research communities, the same core algorithms apply — and Neo4j ships a production-grade framework for running them at scale: the Graph Data Science (GDS) library.
This article covers the three families of graph algorithms you will reach for most often — pathfinding, centrality, and community detection — with concrete Cypher and GDS examples you can run today.
Prerequisites: GDS and Graph Projections
Before running algorithms, you need the GDS library installed. Neo4j Desktop and Neo4j Aura include it by default. For self-managed instances:
# Download and place the GDS jar in the plugins directory
curl -L -o /var/lib/neo4j/plugins/neo4j-gds.jar \
https://github.com/neo4j/graph-data-science/releases/latest/download/neo4j-gds-2.14.0.jar
GDS operates on in-memory graph projections — a snapshot of your labelled subgraph loaded into memory with a specific topology. You create one with gds.graph.project:
Once projected, you can run any algorithm against it. When you are done, drop it:
CALL gds.graph.drop('myGraph');
Pathfinding: Getting from A to B
Pathfinding algorithms answer the most natural graph question: how do I get from this node to that node?
Shortest Path (BFS)
The simplest pathfinder — breadth-first search — finds the path with the fewest hops (edges), ignoring edge weights:
MATCH (a:Person {name: 'Alice'}), (b:Person {name: 'Bob'})
CALL gds.shortestPath.bfs.stream('myGraph', {
sourceNode: id(a),
targetNode: id(b)
})
YIELD nodeIds, path
RETURN [node IN nodes(path) | node.name] AS route
Use BFS when every edge has equal cost — social network hops, organisational reporting lines, network topologies.
Weighted Shortest Path (Dijkstra)
When edges carry different costs (distance, time, monetary value), Dijkstra's algorithm finds the cheapest path:
MATCH (a:Warehouse {name: 'Berlin'}), (b:Warehouse {name: 'Munich'})
CALL gds.shortestPath.dijkstra.stream('shipmentGraph', {
sourceNode: id(a),
targetNode: id(b),
relationshipWeightProperty: 'cost_eur'
})
YIELD nodeIds, totalCost, path
RETURN [node IN nodes(path) | node.name] AS route, totalCost
Dijkstra has one limitation: it cannot handle negative edge weights. For graphs with negative costs (rare in practice but possible), use the Bellman-Ford variant via gds.shortestPath.bellmanFord.stream.
All Pairs and Single Source Shortest Path
For global analysis — how far is every warehouse from every other warehouse? — run the delta-stepping algorithm, which parallelises well on large graphs:
CALL gds.allPairs.shortestPath.stream('shipmentGraph', {
relationshipWeightProperty: 'cost_eur'
})
YIELD sourceNode, targetNode, distance
RETURN gds.util.asNode(sourceNode).name AS source,
gds.util.asNode(targetNode).name AS target,
distance
ORDER BY distance DESC
LIMIT 10;
Algorithm
Best When
Edge Weights
Complexity
BFS
Fewest hops
Unweighted
O(V + E)
Dijkstra
Cheapest path
Non-negative
O(E + V log V)
Delta-Stepping
All-pairs / large graphs
Non-negative
O(E + V log V) — parallel
Bellman-Ford
Graphs with negative edges
Any
O(V × E)
Yen's k-Shortest Paths
One shortest path is often not enough in production. A logistics platform needs alternatives — the fastest route, the cheapest route, and a fallback that avoids toll roads. Yen's algorithm extends Dijkstra to return the top k distinct paths:
Each successive path is the next-best alternative that shares no more than a configurable overlap with previously found paths. The k parameter controls how many alternatives to produce — each additional path adds roughly the same complexity as a single Dijkstra run.
Production use case: an emergency response system that needs three alternative ambulance routes — fastest, a secondary route avoiding known congestion zones, and a tertiary route with the fewest turns (modelled as a separate edge weight).
A* Shortest Path
When your graph is large and you have geometric coordinates, A* offers a heuristic-guided shortcut. Unlike Dijkstra (which explores equally in all directions), A* uses a distance estimate — typically Euclidean or Manhattan distance — to bias exploration toward the target:
A* is particularly effective in geospatial routing (roads, rail, utilities) where Euclidean distance is a good approximation of remaining path cost. In the worst case — a graph with no geometric structure — A* degrades to Dijkstra.
Algorithm
Edge Weight
Heuristic
Best For
Dijkstra
Required
None
General weighted shortest path
Yen's k
Required
None
Top-k alternative routes
A*
Required
Geometric distance
Geospatial routing on large graphs
Centrality: Who Matters Most?
Centrality algorithms rank nodes by importance. The right metric depends entirely on what "importance" means in your domain.
Degree Centrality
The simplest metric: nodes with the most connections win. A person with 500 LinkedIn connections has higher degree centrality than one with 50.
CALL gds.degree.stream('myGraph')
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS name, score
ORDER BY score DESC
LIMIT 10;
Degree centrality is fast and interpretable but naive — it treats every edge equally. A connection to a nobody counts the same as a connection to the CEO.
PageRank
PageRank improves on degree centrality by weighting incoming edges by the importance of the source. A link from The New York Times is worth more than a link from a personal blog.
CALL gds.pageRank.stream('myGraph', {
maxIterations: 20,
dampingFactor: 0.85
})
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS name, score
ORDER BY score DESC
LIMIT 10;
The damping factor (0.85 by convention) models the probability that a random walker continues following edges versus teleporting to a random node. Lower values increase the influence of the graph's global structure; higher values emphasise local connectivity.
Use PageRank for: web pages, academic citations, social media influence, regulatory risk — any domain where being endorsed by influential nodes is meaningful.
Betweenness Centrality
Betweenness measures how often a node lies on the shortest path between every pair of other nodes. A node with high betweenness is a bridge — remove it and the graph fragments.
CALL gds.betweenness.stream('myGraph')
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS name, score
ORDER BY score DESC
LIMIT 10;
This is the most expensive centrality algorithm — exact computation is O(V × E) for unweighted graphs — but it reveals structural keystones: single points of failure in a network, bottleneck analysts in an organisation, chokepoint routers in a topology.
Closeness Centrality
Closeness measures how quickly a node can reach all others — the average shortest path distance to every other node. High-closeness nodes are optimal broadcast points.
CALL gds.closeness.stream('myGraph')
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS name, score
ORDER BY score DESC
LIMIT 10;
Algorithm
What It Measures
Complexity
Use Case
Degree
Raw connection count
O(V)
Quick social check
PageRank
Influential endorsements
O(I × (E + V))
Ranking content or people
Betweenness
Bridge / bottleneck
O(V × E) — V² with approximation
Infrastructure resilience
Closeness
Reachability speed
O(V × (E + V log V))
Information diffusion
Community Detection: Finding the Clusters
Community detection algorithms partition the graph into groups where nodes are densely connected internally and sparsely connected externally.
Louvain Modularity
Louvain is the workhorse of community detection — fast, scalable to tens of millions of nodes, and requires no prior knowledge of the number of communities.
CALL gds.louvain.stream('myGraph')
YIELD nodeId, communityId, intermediateCommunityIds
RETURN gds.util.asNode(nodeId).name AS name, communityId
ORDER BY communityId;
Each node receives a communityId. Nodes in the same ID are the same community. The algorithm works in two phases: first it optimises modularity locally, then it aggregates the discovered communities into super-nodes and repeats. The intermediateCommunityIds array gives you the hierarchical nesting — useful when communities have sub-communities (teams within departments within organisations).
Label Propagation (LPA)
Label propagation is simpler and faster than Louvain but non-deterministic — repeated runs on the same graph may produce slightly different partitions.
CALL gds.labelPropagation.stream('myGraph', {
maxIterations: 10
})
YIELD nodeId, communityId
RETURN gds.util.asNode(nodeId).name AS name, communityId
ORDER BY communityId;
LPA works by initialising every node with a unique label, then iteratively replacing each node's label with the majority label of its neighbours. It converges quickly (typically 5–10 iterations) and is ideal for initial exploration when you have no prior hypotheses about community structure.
Triangle Counting and Clustering Coefficient
Triangle counting is not a community detection algorithm per se, but it reveals how tightly-knit a neighbourhood is:
CALL gds.triangleCount.stream('myGraph')
YIELD nodeId, triangleCount, coefficient
RETURN gds.util.asNode(nodeId).name AS name,
triangleCount AS triangles,
coefficient
ORDER BY coefficient DESC
LIMIT 10;
The clustering coefficient (0 to 1) measures the fraction of a node's neighbours that are also connected to each other. A coefficient near 1 means "my friends all know each other" — a tight clique. Near 0 means "I am the sole connection between disconnected groups" — a structural bridge, which correlates with high betweenness centrality.
Algorithm
Deterministic
Scalability
Needs K
Best For
Louvain
No*
Excellent (millions)
No
Hierarchical communities
Label Propagation
No
Excellent
No
Fast first pass
Triangle Count
Yes
Moderate
No
Measuring local clustering
K-1 Coloring
Yes
Good
Yes
Constraint satisfaction
*GDS offers louvain.seed with a seed property for pseudo-deterministic runs.
Choosing the Right Algorithm
The best algorithm depends on your question:
Question
Algorithm
"What is the cheapest route?"
Dijkstra / A*
"Who is the most influential person?"
PageRank
"Which is the single point of failure?"
Betweenness centrality
"How can I segment users into groups?"
Louvain / Label Propagation
"How tightly connected is this group?"
Triangle count / clustering coefficient
"Which warehouse should serve which store?"
Closeness centrality
Practical Workflow
A production-grade graph algorithm pipeline follows three phases:
Project — Create a named, filtered, in-memory graph projection tailored to your question. Include only the labels and relationship types that matter; every irrelevant node slows computation.
Mutate — Run algorithms in mutate mode to write results back to the projection as node properties, then inspect distributions, find natural thresholds, and validate assumptions before writing to the live graph.
Once written, you query the results like any other property:
MATCH (p:Person)
WHERE p.pagerank > 0.05
RETURN p.name, p.pagerank
ORDER BY p.pagerank DESC;
Algorithm Output Modes: Stream, Mutate, and Write
Every GDS algorithm supports three output modes, each serving a different stage of the production workflow:
Mode
Behaviour
Use Case
stream
Returns results as Cypher result rows
Exploration, ad-hoc analysis, dashboards
mutate
Stores results in the in-memory projection as a new node property
Chaining algorithms, intermediate results
write
Persists results to the canonical stored graph
Production scores, labels for application queries
The mutate mode is particularly powerful because it lets you chain algorithms: run PageRank, store the score in the projection, then run Louvain weighted by that score — all without leaving the GDS memory space:
Use stream during development to inspect distributions and find natural thresholds. Use mutate when chaining algorithms. Use write only when you are satisfied and need the results in transactional query paths.
Memory Management and Projection Lifecycle
Graph projections live in GDS's dedicated memory space, separate from Neo4j's page cache. A projection that survives beyond its useful life can consume enough memory to degrade transactional performance. Monitor active projections with:
This is indispensable in production environments where you need to validate that a projection fits within available heap before committing to a long-running computation.
Incremental Projections with Cypher Filters
For graphs that change frequently — hourly ingestion pipelines, real-time event streams — rebuilding the entire projection from scratch is wasteful. GDS supports Cypher-based projections that let you filter nodes and relationships at projection time:
CALL gds.graph.project.cypher(
'active-users',
'MATCH (u:User) WHERE u.lastActive > datetime() - duration("P7D") RETURN id(u) AS id',
'MATCH (u1:User)-[:FOLLOWS]->(u2:User)
WHERE u1.lastActive > datetime() - duration("P7D")
RETURN id(u1) AS source, id(u2) AS target'
);
This limits the projection to users active in the last seven days, keeping memory usage bounded and runtime predictable. The Cypher projection syntax also supports complex aggregations — for example, collapsing multi-hop paths into a single projected relationship for algorithms that only work on direct edges.
When to use incremental projections:
Scenario
Full Projection
Incremental (Cypher)
Data changes hourly
Too expensive
Project only recent data
Dataset >100M nodes
Memory-intensive
Filter to relevant subgraph
Multiple algorithm pipelines
One projection per pipeline
Shared filtered projections
Exploration phase
Quick to set up
Overengineered
Production Checklist
When deploying graph algorithms to production, verify each of these:
Projection size — estimate memory with gds.<algo>.estimate before running
Algorithm choice — match the algorithm to the question (see decision table above)
Output mode — use mutate for intermediate results, write for final persistence
Projection lifecycle — drop projections after use; monitor with gds.list()
Incremental updates — use Cypher projections for frequently changing graphs
Determinism — if reproducibility matters, seed Louvain with louvain.seed or use deterministic algorithms (WCC, Triangle Count)
The official Neo4j GDS Manual is the definitive reference — all algorithms documented with memory estimates, complexity analysis, and examples in both Cypher and Python.