Creating Subgraphs from Loaded Graphs

The goal of this guide is to help you understand how to create a subgraph, based on an already loaded graph. First, we will introduce filter expressions, which are two different ways to create a subgraph in PGX. Then we will show how to create a bipartite subgraph based on a vertex collection that specifies the left set of the bipartite graph.

Recap: load a graph into memory

To load a graph, you need a graph config stored in an accessible location that points to a graph that is accessible by PGX. If your graph is not stored on the same machine as the one where PGX runs, make sure that you can access it.

You can read a graph like this:

1 session = pypgx.get_session(session_name="my-session")
2 graph = session.read_graph_with_properties(self.graph_path)

Once the graph is loaded, you can become familiar with the semantics of our filter expressions following the below introduction to understand the concept of filter expressions in PGX.

An introduction to filter expressions

Filter expressions in PGX are expressions that are evaluated for either each vertex or each edge. The expression can define some predicates that a vertex or edge has to fulfill in order to be contained in the result, in this case a subgraph.

This graph is based on the sample graph that is also used for other tutorials and it is part of the PGX download package.

pgx sample graph

The edge filter expression

src.prop1 == 10

conveys that each edge where the source vertex’s property prop1 equals the value 10 will match the expression. The following edges will be matched by this expression:

pgx sample graph highlight 1

which results in the following subgraph:

pgx sample graph subgraph 1

The vertex filter expression

1vertex.prop1 < 10

expresses that each vertex where the property prop1 is less than 10 will match the expression. The following vertices will be matched by this expression:

pgx sample graph vertex highlight

which results in the following subgraph:

pgx sample graph vertex subgraph

Creating a subgraph based on a filter in PGX

Example for creating and using an edge filter

1 subgraph = graph.filter(EdgeFilter("src.prop1 == 10"))

Example for creating and using a vertex filter

1 subgraph = graph.filter(VertexFilter("vertex.prop1 < 10"))

Create a subgraph based on a more complex filter

This example focuses on a slightly more complex filter, which uses some special features of our filter expressions. One such feature is the out_degree function. It calculates the number of outgoing edges for an identifier (src or dst). The following filter expression matches all edges where the destination vertex has an outDegree higher than 1 and an edge property cost higher than 50.

1dst.out_degree > 1 && edge.cost > 50

There is only one edge in the sample graph which matches this filter expression:

pgx sample graph highlight 2

The resulting subgraph looks like this:

pgx sample graph subgraph2

Combining filters

It is also possible to combine vertex filters with edge filters. Both filters are evaluated separately and afterwards merged by either creating a union of the results or by intersecting the results.

Creating a union of two filters

Creating the union of the edge filter:

src.prop1 == 10

and the vertex filter:

1vertex.prop1 < 10

will result in the following graph:

pgx sample graph union 
1 edge_filter = EdgeFilter("src.prop1 == 10")
2 vertex_filter = VertexFilter("vertex.prop1 < 10")
3 filter = edge_filter.union(vertex_filter)
4 subgraph = graph.filter(filter)

Creating an intersection of two filters

Creating the intersection of the filters mentioned above will result in the following graph, that only consists of a single vertex:

pgx sample graph intersection 
1 edge_filter = EdgeFilter("src.prop1 == 10")
2 vertex_filter = VertexFilter("vertex.prop1 < 10")
3 filter = edge_filter.intersect(vertex_filter)
4 subgraph = graph.filter(filter)

Creating a set of vertices or edges using a filter

Instead of using filters to create a subgraph they can also be used to only select a set of vertices or edges from a graph. Creating a vertex set on the sample graph using the vertex filter expression

1vertex.prop1 < 10

will yield the following set:

PgxVertex with ID 99
PgxVertex with ID 333

These sets can for example be used to create a bipartite subgraph.

Example for creating a vertex set

1 vertices = graph.get_vertices(filter_expr=VertexFilter("vertex.prop1 < 10"))

1 edge_set = graph.get_edges(filter_expr=EdgeFilter("src.prop1 == 10"))

Create a bipartite subgraph based on a vertex list

The second way to create a subgraph is to specify a set of vertices and create a bipartite subgraph based on those vertices. The specified vertices will be used as the left-hand side of the bipartite subgraph. A bipartite subgraph only has edges between the left set and the other vertices (essentially the right-hand side), but not in between those groups (e.g. no edges from a left set vertex to another left set vertex and no edges between a right-hand side vertex to another right-hand side vertex). In PGX, vertices that are isolated because all the edges leading to and from it were deleted will not be part of the bipartite subgraph.

This is an example of a bipartite subgraph, without any properties shown:

bipartite sample graph

Given the simple graph example from earlier, we can use PGX to create a bipartite subgraph based on a couple of vertices. Before creating the bipartite subgraph, however, we first need to create a new vertex collection and then fill it with the vertices we want to have on the left-hand side.

1 s = graph.create_vertex_set()
2 s.add_all([128, 99])
3 bipartite = graph.bipartite_sub_graph_from_left_set(s)

When you create the subgraph PGX will automatically create a new boolean vertex property that stores whether a vertex is on the left side or not. You can then specify what the new vertex property should be called. The name must not have been previously used for another vertex property on this graph.

The resulting bipartite subgraph looks like this:

pgx sample graph bipartite

As you may have noticed, the vertex with the ID 1908 is not in the bipartite subgraph. Since the only edge connecting that vertex to the graph was the one from 128 to 1908 that edge would violate the bipartite properties of the subgraph, the edge was removed. The 1908 vertex had no other connection to the graph and was removed as well. Moreover, the edge from the vertex with the ID 128 to the vertex with ID 99 is not present in the bipartite subgraph, because edges are only allowed to go from left to right (and not from right to left).