JuliaGraphs Logo The JuliaGraphs Ecosystem: build fast -- don’t break things

James Fairbanks (GTRI, @fairbanksjp, jpfairbanks.com) and Seth Bromberger, (LLNL, bromberger.com)

London Bridges

JuliaGraphs: An ecosystem for all graph theory

  • Core Data structures for implementing algorithms
  • Network Science and Network Analytics and Operations Research
  • I/O for standard formats GraphIO.jl
  • Visualization GraphPlot.jl

Scope of JuliaGraphs

  • All graph theory from counting paths to spectral graph theory
  • Sequential and Parallel Algorithms up to multi-core
  • Flexible APIs and implementations to support diverse data structures
  • Balance Math and CS perspectives on this shared field

The JuliaGraphs Ecosystem

file:///img/graph.plot.svg

Interesting Applications in the JuliaGraphs Ecosystem

  • Probabilistic Programming: BayesNets, Mamba.jl, DiffEQBayes

  • Image Processing: ImageQuilting, Image Segmentation

  • Economics: Dolo, BasisMatries, DSGE, CompEcon, StateSpaceRoutines, Augur

  • Biology: Bio.jl

  • Symbolic Math: Treeview, ExprOptimization

Abstraction

Enables multiple implementations:

  1. SimpleGraph: the standard adjacency list you know and love
  2. StaticGraph: allows for better performance if you don't need to modify the graph.
  3. Weighted graphs: weights integrated as a first class concept
  4. Metagraphs: why should edge and vertex metadata be limited to weights?
  5. Evolving graphs: storing the entire history of a graph over time

MetaGraphs

You can read graphs from DataFrames using GraphDataFrameBridge

julia> using DataFrames
julia> using GraphDataFrameBridge

julia> df = DataFrame(Dict(:start => ["a", "b", "a", "d"],
                      :finish => ["b", "c", "e", "e"],
                      :weights => 1:4,
                      :extras => 5:8))

4×4 DataFrame
│ Row │ extras │ finish │ start │ weights │
├────┼─────┼─────┼─────┼──────┤
│ 1   │ 5      │ b      │ a     │ 1       │
│ 2   │ 6      │ c      │ b     │ 2       │
│ 3   │ 7      │ e      │ a     │ 3       │
│ 4   │ 8      │ e      │ d     │ 4       │

Graphs from DataFrames

Meta Graphs can convert any dataframe into a graph database!

# MetaGraph with `weight` attribute set and
# `:extras` values stored as attributes.
julia> mgw = MetaGraph(df, :start, :finish,
                       weight=:weights,
                       edge_attributes=:extras)
{5, 4} undirected Int64 metagraph with Float64 weights defined by :weight (default weight 1.0)

julia> props(mgw, 1, 2)
Dict Symbol → Any with 2 entries
  :extras → 5
  :weight → 1

Evolving Graphs

Evolving Graphs @weijianzhang, Evolving Graphs

  1. @matbesancon made a PR to EG to get support for all LG API functions
  2. Easy to join the LG Network of packages

Parallelism

GSOC

@SohamTamba, SohamTamba

  • Breadth First Search
  • Floyd Warshall All Pairs Shortest Paths

Grand Unified Theory of Parallel Algorithms

  1. Parallel Graph Algorithms are complicated, hardware $\times$ data complexity $\times$ application
  2. Data Layout cirtical for performance
  3. Not all algorithms are optimal on the same data layout

We need a unified theory of parallel resources and algorithm selection looking to DiffEQ.jl for guidance (2.0 roadmap).

Automatically reason about interactions between graph type, graph data, and compute resources to choose best algorithm available.

Ecosystem Integrations

  1. Interaction between JuliaGraphs and JuliaOpt ecosystems
  2. Minimizing LightGraphs dependencies by extracting out optimization based algorithms
  3. GraphDataFrameBridge connects to JuliaGraphs to Dataverse
  4. Each ecosystem defines basic types in a lightweight library, but we have $\#ecosystems^2$ possible integrations. Which is better than $\#pkg^2$.

Numerical Methods

  1. Big problems from moving ARPACK out of STDLIB
  2. Even if we only rely on basic things they can break.
  3. The Julia Community must develop sustainable methods for funding Core OSS Libraries

Academic Pubs

JuliaGraphs is mature. We spent most of our time this year writing papers with LG rather than on LG.

  •     RV EH JF BS Integrating Productivity-Oriented Programming Languages with High-Performance Data Structures, HPEC 2017, Implements AbstractGraph on a C/OpenMP parallel graph toolkit
  •      RV JF BS Performance Effects of Dynamic Graph Data Structures in Community Detection Algorithms, HPEC 2018, Uses Multiple Dispatch to enable analysis of data structures
  •      Julio Hoffman Mendes et. al, Stochastic Simulation by Image Quilting of Process-based Geological Models, Computers & Geosciences, Uses LG to quilt images with high fidelity
  •      Ollin Demian Langle Chimal, Complex Network Analysis of Political Data, Uses LG to construct a temporal weighted network and apply a self developed algorithm for community detection in order to study coalition dynamics

LightGraphs.jl 1.0 Stability Plan

With the release of LightGraphs.jl v1.0 we are adopting SemVer:

  1. No breaking changes to external API before 2.0
  2. Any script that runs now and does not depend on internal implementations, will continue to run.
  3. Any additional features will get a X.Y+1.0 version bump

Caveats:

  1. If a function computes A solution to a problem then we don't guarantee you will always get the same solution to the problem (ex. BFS)
  2. New interfaces still being refined are separated off in LightGraphs.Experimental currently graph isomorphism.

Conclusion

shipping it

  1. Good year for graphs in Julia
  2. 1.0 is out
  3. Hackathon tomorrow

Discussion

You can find us on

  • github.com/JuliaGraphs: issues and PRs
  • Discourse: help from the broader community
  • Slack #graphs channel: chat and commentary
  • twitter.com/@fairbanksjp: hot takes.