Projecting bipartite and multipartite graphs

What is a bipartite graph?

A bipartite graph is one whose nodes can be divided into exactly two distinct, non-overlapping sets, where connections only occur between sets—never within them.

Think of it as a graph "of two parts."

Example: Customers purchasing products:

(:Customer)-[:PURCHASED]->(:Product)
(:Customer)-[:PURCHASED]->(:Product)
(:Customer)-[:PURCHASED]->(:Product)

In this structure:

The same is true of our (:Actor)-[:ACTED_IN]→(:Movie) projection:

The defining characteristic is that you can cleanly separate all nodes into two groups where every relationship crosses the divide and no node connects to any other node on the same side.

What is a multipartite graph?

A multipartite graph is simply an extension of the concept to three, four, or more non-overlapping sets.

Here’s an example from the Movies dataset:

This graph has four node types and multiple relationship types:

Each node type forms a distinct set, and every relationship crosses between sets—no Actor connects to another Actor, no Movie to another Movie, and so on.

What is a heterogeneous graph?

A heterogeneous graph is a graph with multiple node types and/or relationship types, where nodes of the same type may connect to each other.

The Movies example above is both multipartite and heterogeneous—it has multiple node and relationship types, and happens to have no within-set connections.

But if we added (:Actor)-[:FRIENDS_WITH]→(:Actor) relationships, the graph would still be heterogeneous—but it would no longer be multipartite, because actors would now connect to other actors.

All multipartite graphs are heterogeneous, but not all heterogeneous graphs are multipartite.

Recap: Structure vs Labels

Remember the key distinction from the previous lessons:

Structure = how nodes actually connect

Labels = what GDS knows about node/relationship types

By default, GDS creates unlabelled projections. The structure remains unchanged, but GDS loses awareness of which nodes are which type.

When labels matter

In the previous lessons, we saw that PageRank fails on bipartite structures—not because of missing labels, but because of the structure itself. Adding labels wouldn’t fix PageRank on a bipartite graph.

So when do labels matter?

Labels matter when:

Labels don’t matter when:

Preserving labels in projections

To preserve labels, use the configuration parameters in your projection:

MATCH (source:Actor)-[r:ACTED_IN]->(target:Movie) // (1)
WITH gds.graph.project( // (2)
  'actors-movies-labelled', // (3)
  source, // (4)
  target, // (5)
  {
    sourceNodeLabels: labels(source), // (6)
    targetNodeLabels: labels(target), // (7)
    relationshipType: type(r) // (8)
  },
  {}
) AS g
RETURN g.graphName, g.nodeCount, g.relationshipCount // (9)

Key configuration parameters:

Now GDS creates a labelled bipartite projection:

The structure is unchanged—still bipartite. But now GDS knows which nodes are Actors and which are Movies.

Creating multipartite projections

The same configuration works for three or more node types:

MATCH (source)-[r]->(target) // (1)
WHERE (source:Actor OR source:Movie OR source:User OR source:Genre)
  AND (target:Actor OR target:Movie OR target:User OR target:Genre) // (2)
WITH gds.graph.project( // (3)
  'movies-multipartite', // (4)
  source, // (5)
  target, // (6)
  {
    sourceNodeLabels: labels(source), // (7)
    targetNodeLabels: labels(target), // (8)
    relationshipType: type(r) // (9)
  },
  {}
) AS g
RETURN g.graphName, g.nodeCount, g.relationshipCount // (10)

This preserves all four node types and their relationship types in a single labelled projection.

Algorithms designed for bipartite graphs

Some algorithms are specifically designed to work with bipartite structures, not against them.

Node Similarity compares nodes based on their shared neighbours—perfect for bipartite graphs where one set of nodes connects to another.

Let’s see it in action. First, project Users and Movies:

MATCH (source:User)-[r:RATED]->(target:Movie) // (1)
WITH gds.graph.project( // (2)
  'user-rated-movie', // (3)
  source, // (4)
  target, // (5)
  {
    sourceNodeLabels: labels(source), // (6)
    targetNodeLabels: labels(target), // (7)
    relationshipType: type(r) // (8)
  },
  {}
) AS g
RETURN g.graphName, g.nodeCount, g.relationshipCount // (9)

This creates a labelled bipartite projection:

Running Node Similarity

Node Similarity finds nodes that share many neighbours. In a bipartite graph, it compares nodes on one side based on their connections to the other side.

CALL gds.nodeSimilarity.write( // (1)
  'user-rated-movie', // (2)
  {
    writeRelationshipType: 'SIMILAR', // (3)
    writeProperty: 'score' // (4)
  })
YIELD nodesCompared, relationshipsWritten // (5)

Understanding the results

Let’s verify what Node Similarity created. First, check if it created any User-to-Movie similarity relationships:

MATCH (u:User)-[r:SIMILAR]->(m:Movie) // (1)
RETURN u, r, m // (2)
LIMIT 1 // (3)

This returns no results. Why?

Node Similarity only considers nodes similar if they share neighbours. In our bipartite structure:

The algorithm respects the bipartite structure: it compares nodes within each partition based on their shared connections across the partition.

Now let’s see the relationships it did create:

MATCH path = (u1:User)-[s:SIMILAR]->(u2:User)-[:RATED]->(m:Movie) // (1)
RETURN path // (2)
LIMIT 10 // (3)

You should see User nodes connected by SIMILAR relationships:

Node Similarity found Users who rated similar Movies and created direct User-to-User relationships based on that pattern.

Always check whether your algorithm expects monopartite or handles bipartite structures.