GraphFrames User Guide (Python)

This notebook demonstrates examples from the GraphFrames User Guide.

Requirements

This notebook requires Databricks Runtime for Machine Learning.

Create GraphFrames

Users can create GraphFrames from vertex and edge DataFrames.

• Vertex DataFrame: A vertex DataFrame should contain a special column named "id" which specifies unique IDs for each vertex in the graph.
• Edge DataFrame: An edge DataFrame should contain two special columns: "src" (source vertex ID of edge) and "dst" (destination vertex ID of edge).

Both DataFrames can have arbitrary other columns. Those columns can represent vertex and edge attributes.

Create the vertices first:

And then some edges:

Create a graph from these vertices and these edges:

Basic graph and DataFrame queries

GraphFrames provide several simple graph queries, such as node degree.

Also, since GraphFrames represent graphs as pairs of vertex and edge DataFrames, it is easy to make powerful queries directly on the vertex and edge DataFrames. Those DataFrames are made available as vertices and edges fields in the GraphFrame.

The incoming degree of the vertices:

The outgoing degree of the vertices:

The degree of the vertices:

You can run queries directly on the vertices DataFrame. For example, we can find the age of the youngest person in the graph:

You can also run queries on the edges DataFrame. For example, count the number of follow relationships in the graph:

Motif finding

Using motifs you can build more complex relationships involving edges and vertices. The following cell finds the pairs of vertices with edges in both directions between them. The result is a DataFrame, in which the column names are given by the motif keys.

See the GraphFrame User Guide for more details on the API.

Because the result is a DataFrame, more complex queries can be built on top of the motif. The following cell finds all the reciprocal relationships in which one person is older than 30:

Stateful queries

Most motif queries are stateless and simple to express, as in the examples above. The next example demonstrates a more complex query that carries state along a path in the motif. Such queries can be expressed by combining GraphFrame motif finding with filters on the result where the filters use sequence operations to operate over DataFrame columns.

For example, suppose you want to identify a chain of 4 vertices with some property defined by a sequence of functions. That is, among chains of 4 vertices a->b->c->d, identify the subset of chains matching this complex filter:

• Initialize state on path.
• Update state based on vertex a.
• Update state based on vertex b.
• Same for c and d.

If final state matches some condition, then the filter accepts the chain. The following code snippets demonstrate this process. The code identifies chains of 4 vertices where at least 2 of the 3 edges are “friend” relationships. In this example, the state is the current count of “friend” edges. In general, it could be any DataFrame Column.

Subgraphs

GraphFrames provides APIs for building subgraphs by filtering on edges and vertices. These filters can be composed together, for example the following subgraph only includes people who are more than 30 years old and have friends who are more than 30 years old.

Standard graph algorithms

GraphFrames comes with a number of standard graph algorithms built in:

• Breadth-first search (BFS)
• Connected components
• Strongly connected components
• Label Propagation Algorithm (LPA)
• PageRank (regular and personalized)
• Shortest paths
• Triangle count

Breadth-first search (BFS)

Search from "Esther" for users of age < 32.

You can also limit the search by edge filters and maximum path lengths.

Connected components

Compute the connected component membership of each vertex and return a DataFrame with each vertex assigned a component ID. The GraphFrames connected components implementation can take advantage of checkpointing to improve performance.

Strongly connected components

Compute the strongly connected component (SCC) of each vertex and return a DataFrame with each vertex assigned to the SCC containing that vertex.

Label Propagation

Run static Label Propagation Algorithm for detecting communities in networks.

Each node in the network is initially assigned to its own community. At every superstep, nodes send their community affiliation to all neighbors and update their state to the most frequent community affiliation of incoming messages.

LPA is a standard community detection algorithm for graphs. It is very inexpensive computationally, although (1) convergence is not guaranteed and (2) one can end up with trivial solutions (all nodes are identified into a single community).

PageRank

Identify important vertices in a graph based on connections.

Shortest paths

Computes shortest paths to the given set of landmark vertices, where landmarks are specified by vertex ID.

Triangle count

Computes the number of triangles passing through each vertex.