Skip to content
Tutorials Center
My learning

Topics

Lesson 41 of 48 ยท Advanced Topics

Graph Processing with GraphX and GraphFrames

Process graphs on Spark: property graphs, vertices and edges, GraphX in Scala, GraphFrames in PySpark, PageRank and connected components, with stand-ins.

Some data is about relationships more than rows: who follows whom, which pages link to which, which accounts share a phone number, which road leads to which junction. Such data is a graph: a set of vertices (things) connected by edges (relationships). Questions about graphs are different from the usual table questions: "Which pages are most important?", "Which accounts form a connected ring?", "What is the shortest path between two stations?"

Spark has two ways to answer them at scale: GraphX, a library built into Spark for Scala and Java, and GraphFrames, an add-on package that expresses graphs as DataFrames and works from Python. This lesson explains the property-graph model, then two classic algorithms, PageRank and connected components, and shows how both libraries run them. Spark cannot run on this site, so the real code is read-only; the TryIts implement the same algorithms in plain Python so you can see how they behave.

The property graph model

A property graph attaches data to both parts: every vertex has an id and attributes (a user name), and every edge has a source id, a destination id and attributes (the date of a follow). Edges are directed (A follows B is not B follows A), and two vertices can share several edges.

flowchart LR
    A["Ann"] -->|follows| B["Bo"]
    B -->|follows| C["Cy"]
    C -->|follows| A
    D["Dee"] -->|follows| C
    E["Eli"] -->|follows| F["Flo"]

Ann, Bo, Cy and Dee form one connected piece; Eli and Flo form another.

In a distributed system the graph is just two tables: a vertices table and an edges table. That is the key idea behind both libraries. Graph algorithms become repeated joins and aggregations between these tables, which Spark knows how to distribute.

GraphX (Scala and Java)

GraphX represents a graph as two RDDs, VertexRDD and EdgeRDD. It provides the Graph class, operators such as mapVertices, subgraph and aggregateMessages, a Pregel API for iterative message passing, and built-in algorithms (PageRank, connected components, triangle count, label propagation, shortest paths). It has no Python API, and it is in maintenance mode: it receives bug fixes, not new features.

SCALA
import org.apache.spark.graphx._

val vertices = sc.parallelize(Seq((1L, "Ann"), (2L, "Bo"), (3L, "Cy"), (4L, "Dee"), (5L, "Eli"), (6L, "Flo")))
val edges = sc.parallelize(Seq(Edge(1L, 2L, "follows"), Edge(2L, 3L, "follows"),
                               Edge(3L, 1L, "follows"), Edge(4L, 3L, "follows"),
                               Edge(5L, 6L, "follows")))
val graph = Graph(vertices, edges)

val ranks = graph.pageRank(tol = 0.0001).vertices           // (vertexId, rank)
val components = graph.connectedComponents().vertices        // (vertexId, smallest id in its component)
ranks.join(vertices).collect().foreach(println)

GraphFrames (Python and Scala)

GraphFrames is a separate Spark package (add it with --packages, matching your Spark and Scala versions). A GraphFrame is built from two DataFrames, with required column names: id in the vertices and src and dst in the edges. That makes it natural for PySpark users and lets you combine graph and SQL operations.

Python
from graphframes import GraphFrame

vertices = spark.createDataFrame(
    [(1, "Ann"), (2, "Bo"), (3, "Cy"), (4, "Dee"), (5, "Eli"), (6, "Flo")], ["id", "name"])
edges = spark.createDataFrame(
    [(1, 2, "follows"), (2, 3, "follows"), (3, 1, "follows"), (4, 3, "follows"), (5, 6, "follows")],
    ["src", "dst", "relationship"])

g = GraphFrame(vertices, edges)
g.inDegrees.show()                                           # followers per vertex
ranks = g.pageRank(resetProbability=0.15, maxIter=10)
ranks.vertices.orderBy("pagerank", ascending=False).show()

spark.sparkContext.setCheckpointDir("/tmp/graph-checkpoints") # connectedComponents needs this
g.connectedComponents().show()

GraphFrames also offers motif finding, a pattern-matching language: g.find("(a)-[e]->(b); (b)-[e2]->(a)") returns every pair that follow each other. It has bfs (breadth-first search), shortestPaths, labelPropagation, triangleCount and more. Under the hood many algorithms are joins on the DataFrames, so the join and shuffle costs apply.

PageRank

PageRank was invented to rank web pages. The idea: a page is important if important pages link to it. Every vertex starts with the same rank. In each iteration, every vertex sends a share of its rank along each outgoing edge, and each vertex's new rank is a small base amount plus the sum of what it received, damped by a factor (typically 0.85, which equals a reset probability of 0.15). After enough iterations the ranks stabilize. Vertices with many incoming links from well-ranked vertices score high; a dangling vertex with no outgoing edges needs special handling because its rank would otherwise disappear.

Python PageRank by iteration

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Connected components

A connected component is a group of vertices that can reach each other if edge direction is ignored. Finding them answers questions like "which accounts belong to the same ring" or "how many separate networks do we have". The standard distributed approach labels every vertex with its own id, then repeatedly replaces each label with the smallest label among its neighbors until nothing changes. All vertices in a component end with the same label (the smallest id in it), which is exactly what GraphX and GraphFrames return.

Because each round is a shuffle, the number of rounds matters: it is bounded by the longest shortest path in a component, so very long chains converge slowly. GraphFrames' connectedComponents uses the graphframes algorithm option and requires a checkpoint directory because the lineage would otherwise grow with every round.

Python Connected components by label propagation

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Real versus stand-in. GraphX and GraphFrames partition vertices and edges across executors, run each round as distributed joins or aggregateMessages, and checkpoint between rounds. The stand-ins run in one process on a handful of vertices; they reproduce the algorithms' logic and results, not the distribution. GraphFrames is not part of Spark itself, and its pagerank values use a different normalization than the stand-in, so only the ranking order is comparable.

When a graph database or library is better

Spark graphs shine for batch analytics over very large graphs that live in your data lake: ranking, components, community detection, degree statistics. They are a poor fit for low-latency traversal queries ("friends of friends of this one user, now"), which graph databases such as Neo4j answer from indexed adjacency lists in milliseconds. For graphs that fit in one machine's memory, libraries such as NetworkX or igraph are simpler and faster than a cluster. The same applies as everywhere in Spark: use the cluster when the data needs it. Many workloads can also be written as plain joins: "friends of friends" is a self-join of the edges table on dst = src, and the join lesson covers its costs.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How does a distributed property graph store its data?

    GraphX uses a VertexRDD and an EdgeRDD, GraphFrames uses a vertices DataFrame and an edges DataFrame.
  2. 2. Which library can you use from PySpark?

    GraphX has no Python API. GraphFrames is a separate package with Python and Scala APIs.
  3. 3. What does PageRank assume about important pages?

    Rank flows along edges, so a vertex gains rank from the ranks of the vertices that point to it.
  4. 4. What do all vertices of one connected component share after the algorithm finishes?

    The label is propagated until it stops changing; both GraphX and GraphFrames return the minimum id as the component label.

Summary

  • A property graph is a vertices table plus an edges table, with attributes on both; graph algorithms become repeated joins and aggregations.
  • GraphX (Scala/Java, in maintenance mode) offers Graph, aggregateMessages, Pregel, PageRank and connected components; GraphFrames brings graphs to DataFrames and PySpark (id, src, dst columns, motif finding, bfs).
  • PageRank iterates rank sharing along edges with a damping factor until it stabilizes.
  • Connected components propagate the smallest label until nothing changes; the number of rounds depends on the longest path.
  • Use Spark graphs for large batch analytics; use a graph database for fast traversals and in-memory libraries for small graphs.

Next: put it all together in the Bronze-Silver-Gold ETL project.