Chapter 1. Introduction

This chapter provides an introduction to the available graph algorithms, and instructions for installation and use.

This library provides efficiently implemented, parallel versions of common graph algorithms for Neo4j 3.x, exposed as Cypher procedures.

Releases are available here: https://github.com/neo4j-contrib/neo4j-graph-algorithms/releases

1.1. Algorithms

Graph algorithms are used to compute metrics for graphs, nodes, or relationships.

They can provide insights on relevant entities in the graph (centralities, ranking), or inherent structures like communities (community-detection, graph-partitioning, clustering).

Many graph algorithms are iterative approaches that frequently traverse the graph for the computation using random walks, breadth-first or depth-first searches, or pattern matching.

Due to the exponential growth of possible paths with increasing distance, many of the approaches also have high algorithmic complexity.

Fortunately, optimized algorithms exist that utilize certain structures of the graph, memoize already explored parts, and parallelize operations. Whenever possible, we’ve applied these optimizations.

1.1.1. Centralities

These algorithms determine the importance of distinct nodes in a network:

1.1.2. Community detection

These algorithms evaluate how a group is clustered or partitioned, as well as its tendency to strengthen or break apart:

1.1.3. Path finding

These algorithms help find the shortest path or evaluate the availability and quality of routes:

1.1.4. Similarity

These algorithms help calculate the similarity of nodes:

1.1.6. Preprocessing

These are utility functions and procedures that transform data for use further along the data pipeline:

These procedures work either on the whole graph, or on a subgraph filtered by label and relationship-type. You can also use filtering and projection using Cypher queries.

1.2. Installation

Download graph-algorithms-algo-[version].jar from the matching release and copy it into your $NEO4J_HOME/plugins directory.

Because the algorithms use the lower level Kernel API to read from, and to write to Neo4j, for security purposes you will also have to enable them in the configuration:

  1. Add the following to your $NEO4J_HOME/conf/neo4j.conf file:

    dbms.security.procedures.unrestricted=algo.*
  2. Restart Neo4j
  3. To see a list of all the algorithms, run the following query:

    CALL algo.list()

1.3. Usage

These algorithms are exposed as Neo4j procedures. They can be called directly from Cypher in your Neo4j Browser, from cypher-shell, or from your client code.

For most algorithms there are two procedures:

  • algo.<name> - this procedure writes results back to the graph as node-properties, and reports statistics.
  • algo.<name>.stream - this procedure returns a stream of data. For example, node-ids and computed values.

    For large graphs, the streaming procedure might return millions, or even billions of results. In this case it may be more convenient to store the results of the algorithm, and then use them with later queries.

We can project the graph we want to run algorithms on with either label and relationship-type projection, or cypher projection.

diag dbeb4a8fcb27edebd07f64ae62959559

The projected graph model is separate from Neo4j’s stored graph model to enable fast caching for the topology of the graph, containing only relevant nodes, relationships and weights. The projected graph model does not support multiple relationships between a single pair of nodes. During projection, only one relationship between a pair of nodes per direction (in, out) is allowed in the directed case, but two relationships are allowed for BOTH the undirected cases.

1.3.1. Label and relationship-type projection

We can project the subgraph we want to run the algorithm on by using the label parameter to describe nodes, and relationship-type to describe relationships.

The general call syntax is:

CALL algo.<name>('NodeLabel', "RelationshipType", {config})

For example, PageRank on DBpedia (11M nodes, 116M relationships):

CALL algo.pageRank('Page','Link',{iterations:5, dampingFactor:0.85, write: true, writeProperty:'pagerank'});
// YIELD nodes, iterations, loadMillis, computeMillis, writeMillis, dampingFactor, write, writeProperty

CALL algo.pageRank.stream('Page','Link',{iterations:5, dampingFactor:0.85})
YIELD node, score
RETURN node.title, score
ORDER BY score DESC LIMIT 10;

1.3.1.1. Huge graph projection

The default label and relationship-type projection has a limitation of 2 billion nodes and 2 billion relationships, so if our project graph is bigger than this we need to use a huge graph projection. This can be enabled by setting graph:'huge' in the config.

The general call syntax is:

CALL algo.<name>('NodeLabel', "RelationshipType", {graph: "huge"})

For example, PageRank on DBpedia:

CALL algo.pageRank('Page','Link',{iterations:5, dampingFactor:0.85, writeProperty:'pagerank',graph:'huge'});
YIELD nodes, iterations, loadMillis, computeMillis, writeMillis, dampingFactor, writeProperty

1.3.2. Cypher projection

If label and relationship-type projection is not selective enough to describe our subgraph to run the algorithm on, we can use Cypher statements to project subsets of our graph. Use a node-statement instead of the label parameter and a relationship-statement instead of the relationship-type, and use graph:'cypher' in the config.

Relationships described in the relationship-statement will only be projected if both source and target nodes are described in the node-statement. Relationships that don’t have both source and target nodes described in the node-statement will be ignored.

We can also return a property value or weight (according to our config) in addition to the ids from these statements.

Cypher projection enables us to be more expressive in describing our subgraph that we want to analyse, but might take longer to project the graph with more complex cypher queries.

The general call syntax is:

CALL algo.<name>(
  'MATCH (n) RETURN id(n) AS id',
  "MATCH (n)-->(m) RETURN id(n) AS source, id(m) AS target",
  {graph: "cypher"})
  • The first query MATCH (n) RETURN id(n) AS id returns node ids. The Cypher loader expects the query to return an id field.
  • The second query MATCH (n)-→(m) RETURN id(n) AS source, id(m) AS target returns pairs of node ids that have a relationship between them in our projected graph. The Cypher loader expects the query to return source and target fields. We can also return an optional weight field.

Note that in both queries we use the id function to return the node id.

For example, PageRank on DBpedia:

CALL algo.pageRank(
'MATCH (p:Page) RETURN id(p) as id',
'MATCH (p1:Page)-[:Link]->(p2:Page) RETURN id(p1) as source, id(p2) as target',
{graph:'cypher', iterations:5, write: true});

Cypher projection can also be used to project a virtual (non-stored) graph. Here is an example of how to project an undirected graph of people who visited the same web page and run the Louvain community detection algorithm on it, using the number of common visited web pages between pairs of people as relationship weight:

CALL algo.louvain(
'MATCH (p:Person) RETURN id(p) as id',
'MATCH (p1:Person)-[:Visit]->(:Page)<-[:Visit]-(p2:Person)
RETURN id(p1) as source, id(p2) as target, count(*) as weight',
{graph:'cypher', iterations:5, write: true});

1.4. Graph loading

As it can take some time to load large graphs into the algorithm data structures, you can pre-load graphs and then later refer to them by name for several graph algorithms. After usage they can be removed from memory to free resources used:

// Load graph
CALL algo.graph.load('my-graph','Label','REL_TYPE',{graph:'heavy',..other config...})
  YIELD name, graph, direction, undirected, sorted, nodes, loadMillis, alreadyLoaded,
        nodeWeight, relationshipWeight, nodeProperty, loadNodes, loadRelationships;

// Info on loaded graph
CALL algo.graph.info('my-graph')
  YIELD name, type, exists, removed, nodes;

// Use graph
CALL algo.pageRank(null,null,{graph:'my-graph',...})


// Remove graph
CALL algo.graph.remove('my-graph')
  YIELD name, type, exists, removed, nodes;

1.5. Building locally

Currently aiming at Neo4j 3.x (with a branch per version):

git clone https://github.com/neo4j-contrib/neo4j-graph-algorithms
cd neo4j-graph-algorithms
git checkout 3.3
mvn clean install
cp algo/target/graph-algorithms-*.jar $NEO4J_HOME/plugins/
$NEO4J_HOME/bin/neo4j restart