Creating Property Graphs in Julia

If the FBI knocks at your door one day and finds you guilty of not knowing how to make a property graph in Julia, this article could help.

But what is a property graph?

It’s basically the graph data structure except that each node and edge can have its own properties and properties can be multi-variate.

That means you can have a Person node that can have the properties name, age, criminal records etc. And you can have an edge between a Person and another Person, and that edge can have properties like felony, theft, assault, etc.

Why Julia?

It’s cool and fast.

The Graph Interface

The folks at JuliaGraphs came up with a very elegant “interface” for defining graphs. Essentially, a graph in Julia is just a “type” — like everything else in Julia (I’m not kidding, there’s no concept of a ‘value’ in Julia; everything is a type). If you want to make your own custom graph with functionality that Graphs.jl does not provide, then you simply create your own type like so:

using Graphs

# AbstractGraph is an abstract type from Graphs.jl
# all graphs need to inherit from it
struct CustomGraph{T<:Any} <: AbstractGraph{T}
	n::T
end

# initialize
g = CustomGraph(1) # you could put any other argument since type is Any

There are no strict requirements on what fields the struct has to have, since the behavior of the type is going to determined entirely by the methods defined on it (that’s multiple dispatch for ya).

If you define no methods for your type, the default implementations from Graphs.jl will kick in.

Property Graphs

Now, how do you actually make property graphs?

Using MetaGraphs.

MetaGraphs is just a more specialized version of the Graphs.jl interface. It has weights (specifically, MetaWeights) which can be defined on nodes and edges.

Here’s a sample “property graph” implementation:

using MetaGraphs

# Create 5 nodes -- canonically, 1, 2, 3, 4, 5
mdg = MetaDiGraph(5) # bi-directional version of MetaGraph

# add edges to the graph
add_edge!(mdg, 1, 2) # creates and edge between node 1 and 2
add_edge!(mdg, 2, 3) # so on
add_edge!(mdg, 3, 4)
add_edge!(mdg, 4, 5)

# add properties to the vertices
set_prop!(mdg, 1, :name, "A")
set_prop!(mdg, 2, :name, "B")
set_prop!(mdg, 3, :name, Dict(:name => "C", :age => 20))
set_prop!(mdg, 4, :name, Dict(:name => "D", :age => 30))
set_prop!(mdg, 5, :name, "E")

# add properties to the edges
set_prop!(mdg, 1, 2, :weight, 1.0)
set_prop!(mdg, 2, 3, :weight, 2.0)
set_prop!(mdg, 3, 4, :weight, 3.0)
set_prop!(mdg, 4, 5, :weight, 4.0)

As you can see, we can add multi-variate properties. If you want to print out the edges in the Cypher format:

for e ∈ edges(mdg) # you can write ∈ using \in<tab> or just write 'in' -- works the same
    println("($(src(e)) { name: $(get_prop(mdg, src(e), :name))})-[:HAS_EDGE { weight: $(get_prop(mdg, e, :weight))}]->($(dst(e)) { name: $(get_prop(mdg, dst(e), :name))})")
end

And this will print out (line spaces added for clarity):

(1 { name: A})-[:HAS_EDGE { weight: 1.0}]->(2 { name: B})

(2 { name: B})-[:HAS_EDGE { weight: 2.0}]->(3 { name: Dict{Symbol, Any}(:age => 20, :name => "C")})

(3 { name: Dict{Symbol, Any}(:age => 20, :name => "C")})-[:HAS_EDGE { weight: 3.0}]->(4 { name: Dict{Symbol, Any}(:age => 30, :name => "D")})

(4 { name: Dict{Symbol, Any}(:age => 30, :name => "D")})-[:HAS_EDGE { weight: 4.0}]->(5 { name: E})

Now the HAS_EDGE relationship type is not exactly in the graph, but you can imagine we can easily incorporate this by subtyping the AbstractSimpleEdge or any other, more specialized, abstract type defined by any community project which suits your use case the most and have a property in it which indicates the kind of relationship.

Since our edge-weights in the example above are of Number type, we can also perform out-of-box graph analytics like so:

# In the Julia REPL
julia> betweenness_centrality(mdg) # this is a function in Graphs.jl
5-element Vector{Float64}:
 0.0
 0.25
 0.3333333333333333
 0.25
 0.0
julia> dijkstra_shortest_paths(mdg, 1)
Graphs.DijkstraState{Float64, Int64}(
	[0, 1, 2, 3, 4],
	[0.0, 1.0, 3.0, 6.0, 10.0],
	[Int64[], Int64[], Int64[], Int64[], Int64[]], [
	1.0, 1.0, 1.0, 1.0, 1.0],
	Int64[]
)

Of course, if your edge-weights are of a custom type then you will either have to implement these functions to cater for those weights or you can do some Julia type magic to make your custom weights work like a numerical type.

To sum it up, here’s what you need to do:

1. Learn the Graphs.jl interface. It’s a bunch of functions and types, it’s worth learning exactly how those functions are supposed to mesh together.
2. Add the MetaGraphs package to your Julia project and roll with it.
3. If you want something even more specific, you can inherit from AbstractMetaGraph type defined in the MetaGraphs project and add whatever type or semantic constraints you desire.
4. Appreciate the beauty of Julia’s type system.

Tell the FBI folks you got it.