Projecting monopartite graphs

What is a monopartite graph?

A monopartite graph contains nodes of a single type (from the algorithm’s perspective) with connections between them.

Consider a social network where all nodes are people, and they have only one type of relationship: -[:FRIENDS_WITH]→

You could also refer to this graph as a 'homogeneous graph' because it has only one node type and one relationship type.

You could project that network with the following command:

MATCH (source:Person)-[r:FRIENDS_WITH]->(target:Person) // (1)
WITH gds.graph.project( // (2)
  'social-network', // (3)
  source, // (4)
  target, // (5)
  {}, // (6)
  {} // (7)
) AS g
RETURN g.graphName, g.nodeCount, g.relationshipCount // (8)

This command would create an in-memory projection that looks something like this:

For this particular graph, we actually want all the nodes to be of the same type, and we have only one type of relationship anyway.

Running an algorithm on this non-specific graph will not change its output.

The default projection behavior

However, let’s return now to our Movies dataset. When we projected it using this command:

MATCH (source:Actor)-[r:ACTED_IN]->(target:Movie) // (1)
WITH gds.graph.project( // (2)
  'actors-graph', // (3)
  source, // (4)
  target // (5)
) AS g
RETURN g.graphName, g.nodeCount, g.relationshipCount // (6)

We projected a graph that looks very similar to our social media graph.

By default, GDS projections ignore node labels.

Even though your source data has Actor and Movie labels, GDS treats this as a monopartite graph:

It is important to be aware of precisely what you are projecting and why.

Why this matters for algorithms

Earlier, we ran degree centrality on this graph. Remember, degree centrality counts the outgoing relationships of every node to rank them by importance.

Running degree centrality on a graph with two labels as if it is a graph with one label doesn’t hugely impact our results.

Degree centrality doesn’t care what your nodes are, and it will count their outgoing relationships all the same.

However, the same is not true when we run other algorithms.

Take PageRank for example. We will deal with PageRank specifically in more detail later. For now, just remember:

Let’s run PageRank on our current graph projection, and see what happens:

CALL gds.pageRank.stream( // (1)
  'actors-graph', // (2)
  {}, // (3)
  {} // (4)
)
YIELD nodeId, score // (5)
RETURN gds.util.asNode(nodeId).name, score // (6)
ORDER BY score DESC // (7)

The returned table shows you the nodeId of each node in one column and the PageRank score they received in the next.

You should notice that almost all of these nodes have received the same PageRank score.

This happens because we are explicitly giving GDS a node structure that looks like this:

We may intuitively think it will interpret the node structure as this:

It won’t.

By default, many algorithms, PageRank included, will treat every single node and relationship the same. They will consider it a 'monopartite' graph, even if it is not.

The reason for this behavior is that most algorithms simply work better on a monopartite graph.

If you want to understand which movie is most important to increase user watch times, introducing actors into that signal will likely dilute it.

Many GDS algorithms will provide better results on two monopartite graphs than on a single graph with many labels. However, this decision is dependent on the use-case.

Projecting a true monopartite graph

To understand how we can fix this, we need to reconsider what it is our projection is asking from the algorithm.

In this case, we want to know the 'most important actors'. We don’t actually care about their movies. Therefore, we need not include their movies at all.

To create a graph of actors and their relationships to each other, we can project this graph:

MATCH (source:Actor)-[:ACTED_IN]->(:Movie)<-[:ACTED_IN]-(target:Actor) // (1)
WITH gds.graph.project( // (2)
  'actors-only', // (3)
  source, // (4)
  target, // (5)
  {}, // (6)
  {} // (7)
) AS g
RETURN g.graphName AS graph, g.nodeCount AS nodes, g.relationshipCount AS rels // (8)

This gives us a new graph that, in theory, looks like this:

GDS has skipped over the intermediate 'Movie' nodes, and has repinned those relationships directly between the actors. Now each actor has greater or fewer degrees between themselves and other actors in the graph.

Still, GDS still sees this graph as generic nodes with generic relationships:

However, let’s see what happens when we run PageRank on this graph.

CALL gds.pageRank.stream( // (1)
  'actors-only', // (2)
  {} // (3)
)
YIELD nodeId, score // (4)
RETURN gds.util.asNode(nodeId).name, score // (5)
ORDER BY score DESC // (6)

Now, PageRank returns Robert De Niro as the most important actor in the graph, and other actors have received descending values based on their relative 'importance'.

Before, PageRank could only use any actor’s relationship to a movie. Every actor connected to a movie would only ever have one relationship to that movie, never directly to each other. That meant that any actors with same number of roles would necessarily be considered as important as each other.

In our current graph, we only consider them as a single social network.

Before, we were trying to treat a 'bipartite' graph (two types) as if it were a 'monopartite' graph (one type). Now, we are projecting a true 'monopartite' graph.

What’s next

You now understand what monopartite graphs are and why GDS creates them by default. You’ve seen how the graph structure affects algorithm results.

In the next lesson, you’ll get hands-on practice creating different types of monopartite projections.