Graph Algorithms with Neo4j GDS

Graph theory gives us the mathematics; graph algorithms give us the answers. While understanding the structure of a graph is valuable, the real power lies in running algorithms that extract meaning from that structure — finding the shortest path through a network, identifying influential nodes, discovering natural clusters, or predicting future connections.

The Neo4j Graph Data Science (GDS) library provides over 65 production-quality algorithms, exposed as Cypher procedures, covering five major categories:

• Pathfinding — how are things connected?
• Centrality — what's important?
• Community detection — what are the natural groups?
• Similarity — what entities resemble each other?
• Link prediction — what connections might form next?

This article walks through each category with practical examples, using a consistent social network graph so you can see how different algorithms reveal different insights from the same data.

Setting Up

Before running any algorithm, you need to project your Neo4j graph into an in-memory graph catalog. This is a deliberate design choice in GDS — algorithms operate on an optimised, compressed representation of your graph rather than the live database, giving you snapshot isolation and predictable performance.

// Create a sample social network
CREATE (alice:Person {name: 'Alice', age: 34})
CREATE (bob:Person {name: 'Bob', age: 28})
CREATE (carol:Person {name: 'Carol', age: 31})
CREATE (dan:Person {name: 'Dan', age: 45})
CREATE (eve:Person {name: 'Eve', age: 29})
CREATE (frank:Person {name: 'Frank', age: 52})
CREATE (gina:Person {name: 'Gina', age: 37})

CREATE (alice)-[:KNOWS {since: 2015}]->(bob)
CREATE (alice)-[:KNOWS {since: 2018}]->(carol)
CREATE (bob)-[:KNOWS {since: 2016}]->(dan)
CREATE (carol)-[:KNOWS {since: 2019}]->(eve)
CREATE (carol)-[:KNOWS {since: 2020}]->(frank)
CREATE (dan)-[:KNOWS {since: 2017}]->(eve)
CREATE (eve)-[:KNOWS {since: 2021}]->(frank)
CREATE (frank)-[:KNOWS {since: 2022}]->(gina);

// Project into an in-memory graph for GDS
CALL gds.graph.project(
  'social-graph',
  'Person',
  {KNOWS: {orientation: 'UNDIRECTED'}}
);

Once your graph is projected, every algorithm call follows the same pattern: choose a category, pick an algorithm, configure its parameters, and select an execution mode (stream, stats, mutate, or write).

Pathfinding: How Are Things Connected?

Pathfinding algorithms find routes through a graph, optimising for distance, cost, or number of hops. They are the workhorses of logistics, network routing, and dependency analysis.

Shortest Path with Dijkstra

Dijkstra's algorithm computes the shortest (lowest-weight) path between two nodes. In an unweighted graph, it finds the path with the fewest relationships.

// Find the shortest path from Alice to Gina
MATCH (source:Person {name: 'Alice'})
MATCH (target:Person {name: 'Gina'})
CALL gds.shortestPath.dijkstra.stream('social-graph', {
  sourceNode: source,
  targetNode: target,
  relationshipWeightProperty: null
})
YIELD index, sourceNode, targetNode, totalCost, nodeIds, path
RETURN
  index,
  gds.util.asNode(sourceNode).name AS source,
  gds.util.asNode(targetNode).name AS target,
  totalCost,
  [nodeId IN nodeIds | gds.util.asNode(nodeId).name] AS pathNodes
ORDER BY index;

The result shows the path: Alice → Carol → Eve → Frank → Gina (4 hops). Without weights, totalCost equals the hop count.

Minimum Spanning Tree

When you need to connect all nodes in a graph with the minimal total relationship weight, use the Minimum Spanning Tree (MST) algorithm — essential for network design, circuit routing, and cluster analysis.

CALL gds.beta.spanningTree.stream('social-graph', {
  sourceNode: sourceNodeId,
  relationshipWeightProperty: null
})
YIELD nodeId, parentId, parentNodeId
RETURN gds.util.asNode(nodeId).name AS node,
       gds.util.asNode(parentId).name AS parent;

Centrality: What's Important?

Centrality algorithms rank nodes by their importance or influence within the network. These are surprisingly useful — they power everything from search engines (PageRank) to fraud detection (Betweenness Centrality).

PageRank

PageRank measures influence based on both the quantity and quality of incoming connections. A node is important if other important nodes point to it.

CALL gds.pageRank.stream('social-graph', {
  maxIterations: 20,
  dampingFactor: 0.85
})
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS name, score
ORDER BY score DESC;

In our sample graph, Carol scores highest because she connects two otherwise separate clusters — Alice/Bob/Dan on one side and Eve/Frank/Gina on the other. This bridging pattern is precisely what PageRank rewards.

Betweenness Centrality

Betweenness centrality measures how often a node sits on the shortest paths between all other pairs of nodes. High-betweenness nodes are bottlenecks — they control the flow of information (or goods, or money) through the network.

CALL gds.betweenness.stream('social-graph', {})
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS name, score
ORDER BY score DESC;

Betweenness is computationally expensive — O(n·m) time and O(n+m) space — and for large graphs, GDS supports approximation via sampling (samplingSize parameter). The sampling selects source nodes proportional to their degree, which typically yields accurate results with a fraction of the compute cost.

Algorithm	What It Measures	Use Case
PageRank	Quality of incoming links	Search ranking, influence scoring
Betweenness	Bottleneck positioning	Fraud detection, supply chain
Closeness	Average distance to all nodes	Optimal hub location
Degree	Raw connection count	Quick popularity metric

Community Detection: What Are the Natural Groups?

Community detection algorithms find clusters of nodes that are more densely connected internally than to the rest of the network. This is where graph algorithms shine for pattern discovery — finding fraud rings, customer segments, or topic clusters without any labelled training data.

Leiden (Production Quality)

Leiden is the recommended algorithm for community detection in GDS 2026. It improves on the older Louvain algorithm by guaranteeing well-connected communities and avoiding disconnected communities.

CALL gds.leiden.stream('social-graph', {
  includeIntermediateCommunities: false
})
YIELD nodeId, communityId, intermediateCommunityIds
RETURN gds.util.asNode(nodeId).name AS name, communityId
ORDER BY communityId;

Leiden modularity optimises two phases: local movement of nodes between communities (like Louvain), and a refinement step that ensures every community is internally connected. The result is more stable and interpretable clusters.

Label Propagation (Fast, Lightweight)

When speed matters more than precision — for example, in an initial data exploration pass — Label Propagation is a fast, semi-supervised alternative.

CALL gds.labelPropagation.stream('social-graph', {
  maxIterations: 10
})
YIELD nodeId, communityId
RETURN gds.util.asNode(nodeId).name AS name, communityId
ORDER BY communityId;

Algorithm	Quality	Speed	Best For
Leiden	Excellent	Moderate	Production clusters, interpretable results
Louvain	Good	Fast	Large graphs, approximate clusters
Label Propagation	Fair	Very fast	Exploration, seed-driven labelling
Weakly Connected Components	Structural	Instant	Graph connectivity analysis

Similarity: What Resembles What?

Similarity algorithms compute how alike nodes are based on their neighbours or properties. They're fundamental to recommendation engines and entity resolution.

Node Similarity

Node Similarity computes pairwise similarity using metrics like Jaccard or overlap coefficients, based on shared neighbours.

// Find the most similar people in our network
CALL gds.nodeSimilarity.stream('social-graph', {
  similarityMetric: 'JACCARD'
})
YIELD node1, node2, similarity
RETURN gds.util.asNode(node1).name AS person1,
       gds.util.asNode(node2).name AS person2,
       similarity
ORDER BY similarity DESC;

Execution Modes

Every GDS algorithm supports multiple execution modes. Understanding these is critical for building efficient pipelines:

Mode	Behaviour	Use When
stream	Returns results as rows	Inspecting results, piping into Cypher
stats	Returns summary statistics	Monitoring, validation
mutate	Writes result to in-memory graph	Chaining algorithms
write	Persists to Neo4j database	Saving results for queries

A common pattern is chaining: run centrality in mutate mode to compute scores as a node property, then run community detection in stream mode using those scores as weights.

// Two-step pipeline: PageRank → weighted Leiden
CALL gds.pageRank.mutate('social-graph', {
  mutateProperty: 'pageRankScore'
})
YIELD nodePropertiesWritten;

CALL gds.leiden.stream('social-graph', {
  relationshipWeightProperty: 'pageRankScore'
})
YIELD nodeId, communityId
RETURN gds.util.asNode(nodeId).name AS name, communityId;

Choosing the Right Algorithm

The hardest part of using graph algorithms isn't the syntax — it's knowing which one to apply. Here is a decision framework:

1. What question are you solving? — "Find the strongest person" (centrality) vs. "Find the groups" (community) vs. "Find the connection" (pathfinding)
2. How big is your graph? — Leiden scales better than Louvain for very large graphs; Betweenness requires sampling for graphs over 10,000 nodes
3. Are your relationships weighted? — Weighted graphs unlock richer pathfinding but increase algorithm complexity
4. What quality tier do you need? — GDS labels algorithms as production-quality (optimised, fully tested) or experimental (available but evolving)

Next Steps

The GDS library integrates naturally with the Cypher query patterns you already know. Start by projecting your existing Neo4j database, pick a single algorithm from the category that matches your use case, and run it in stream mode to see what your graph reveals.

For a deeper dive into modelling patterns that make these algorithms effective, see Graph Data Modeling Patterns for Neo4j. And if you're interested in how graphs augment AI workflows, Introduction to GraphRAG covers the intersection of graph algorithms with modern retrieval-augmented generation systems.