Performance

Compressed Sparse Row (CSR) Representation

The core data structure in caugi is a compressed sparse row (CSR) representation of the graph. CSR representations store, for each vertex, a contiguous slice of neighbor IDs with a pointer (offset) array that marks the start and end of each slice. This format is memory-efficient for sparse graphs. The caugi graph object also stores important query information directly, allowing parent, child, and neighbor queries to be done in \(\mathcal{O}(1)\) time. This yields a larger memory footprint, but the trade-off is that queries are extremely fast.

Mutation and Lazy Building

The caugi graph objects are expensive to build. This is the performance downside of using caugi. Each time we make a modification to a caugi graph object, we need to rebuild the graph completely since the graph object is immutable by design. This has complexity \(\mathcal{O}(|V| + |E|)\), where \(V\) is the vertex set and \(E\) is the edge set.

However, the graph object will only be rebuilt when the user either calls build() directly or queries the graph. Therefore, you do not need to worry about wasting compute time by iteratively making changes to a caugi graph object, as the graph rebuilds lazily when queried. By doing this, caugi graphs feel mutable, but, in reality, they are not.

By doing it this way, we ensure

• that the graph object is always in a consistent state when queried and
• that queries are as fast as possible,

while keeping the user experience smooth.

Relational Queries

Direct neighbor lookups (parents, children) are \(O(1)\) for caugi, igraph, bnlearn, and Tetrad—they all maintain adjacency tables. pgmpy is a thin wrapper over NetworkX’s predecessor/successor lookups. pcalg and ggm scan a row or column of the adjacency matrix on each call (\(O(n)\)), with ggm paying noticeably more R-level overhead. dagitty is the outlier: it re-derives neighbors from its string DSL representation each call and pays a linear-in-edges cost.

bench_parents <- function(graphs, fx) {
  v <- fx$test_node
  v_idx <- match(v, graphs$nodes)

  calls <- list(
    caugi = bquote(caugi::parents(graphs$cg, .(v))),
    igraph = bquote(igraph::neighbors(graphs$ig, .(v), mode = "in")),
    bnlearn = bquote(bnlearn::parents(graphs$bn, .(v))),
    dagitty = bquote(dagitty::parents(graphs$dg, .(v))),
    ggm = bquote(ggm::pa(.(v), graphs$am)),
    pcalg = bquote(pcalg::searchAM(graphs$amat_pag, .(v_idx), type = "pa"))
  )

  run_bench(calls, "parents", fx)
}

bench_children <- function(graphs, fx) {
  v <- fx$test_node
  v_idx <- match(v, graphs$nodes)

  calls <- list(
    caugi = bquote(caugi::children(graphs$cg, .(v))),
    igraph = bquote(igraph::neighbors(graphs$ig, .(v), mode = "out")),
    bnlearn = bquote(bnlearn::children(graphs$bn, .(v))),
    dagitty = bquote(dagitty::children(graphs$dg, .(v))),
    ggm = bquote(ggm::ch(.(v), graphs$am)),
    pcalg = bquote(pcalg::searchAM(graphs$amat_pag, .(v_idx), type = "ch"))
  )

  run_bench(calls, "children", fx)
}

As you can see from the plots, Tetrad is fastest (sub-microsecond), with pgmpy and caugi close behind; all three stay flat as \(n\) grows, as do igraph and bnlearn. The cost of pcalg’s \(O(n)\) row scan, hidden at small \(n\), becomes visible by \(n = 10000\), where it climbs to a few tenths of a millisecond. ggm and dagitty pay the most for re-deriving neighbors on every call: by \(n = 1000\) they are already one to two orders of magnitude slower than the rest, and both are skipped at \(n = 10000\) (their lines simply stop). For the front-runners the absolute times are tiny and the gaps between them mostly reflect dispatch overhead differences between Python, R, and Java rather than anything that matters in practice.

Ancestors and Descendants

These require transitive closure (BFS/DFS over the directed graph). Here caugi’s CSR pays off—both forward and reverse adjacency are precomputed, so traversal is tight pointer-chasing in Rust.

bench_ancestors <- function(graphs, fx) {
  v <- fx$test_node
  v_idx <- match(v, graphs$nodes)

  calls <- list(
    caugi = bquote(caugi::ancestors(graphs$cg, .(v))),
    igraph = bquote(igraph::subcomponent(graphs$ig, .(v), mode = "in")),
    bnlearn = bquote(bnlearn::ancestors(graphs$bn, .(v))),
    dagitty = bquote(dagitty::ancestors(graphs$dg, .(v))),
    pcalg = bquote(pcalg::searchAM(graphs$amat_pag, .(v_idx), type = "an"))
  )

  run_bench(calls, "ancestors", fx)
}

bench_descendants <- function(graphs, fx) {
  v <- fx$test_node
  v_idx <- match(v, graphs$nodes)

  calls <- list(
    caugi = bquote(caugi::descendants(graphs$cg, .(v))),
    igraph = bquote(igraph::subcomponent(graphs$ig, .(v), mode = "out")),
    bnlearn = bquote(bnlearn::descendants(graphs$bn, .(v))),
    dagitty = bquote(dagitty::descendants(graphs$dg, .(v))),
    pcalg = bquote(pcalg::searchAM(graphs$amat_pag, .(v_idx), type = "de"))
  )

  run_bench(calls, "descendants", fx)
}

caugi is the most consistent here: sub-millisecond on every fixture for both ancestors and descendants, and barely moving as \(n\) grows. igraph::subcomponent() and pgmpy’s NetworkX-backed traversal also stay fast across the grid. Descendants on the dense \(n = 10000\) fixture is where the design differences blow up: Tetrad takes about ten seconds, while pcalg and bnlearn reach several hundred milliseconds—caugi finishes the same query in roughly a tenth of a millisecond, a five-orders-of-magnitude gap to Tetrad. dagitty is again one to two orders of magnitude slower than the front-runners on the sizes it can handle, paying its DSL-reparsing cost on every call, and is skipped at \(n = 10000\).

Markov Blanket

The Markov blanket of a node \(v\) is parents(v) ∪ children(v) ∪ parents(children(v)). caugi, bnlearn, and Tetrad have direct accessors backed by adjacency tables; dagitty re-derives it from its DSL representation each call; pgmpy walks NetworkX edges. pcalg and ggm do not expose a Markov-blanket helper and are omitted.

bench_markov_blanket <- function(graphs, fx) {
  v <- fx$test_node

  calls <- list(
    caugi = bquote(caugi::markov_blanket(graphs$cg, .(v))),
    bnlearn = bquote(bnlearn::mb(graphs$bn, .(v))),
    dagitty = bquote(dagitty::markovBlanket(graphs$dg, .(v)))
  )

  run_bench(calls, "markov_blanket", fx)
}

caugi, pgmpy, and bnlearn all resolve Markov blankets in microseconds across the entire grid, and Tetrad stays well under a millisecond too. dagitty is the outlier, climbing into the hundreds of milliseconds on the dense \(n = 1000\) fixture because it re-derives the blanket from its DSL representation on every call; it is skipped at \(n = 10000\).

D-Separation

For each fixture we pick a random (X, Y) pair and compute a minimal d-separator Z with caugi::minimal_separator()—that is, a smallest set of nodes whose conditioning blocks every path between X and Y in the DAG. The same triple (X, Y, Z) is then passed to every package’s d-separation routine, so every package answers “is X ⫫ Y | Z?” on identical inputs. Tetrad uses the m-separation generalisation (equivalent on DAGs). pcalg::dsep() follows Lauritzen’s moralization-based test on a graphNEL.

bench_dsep <- function(graphs, fx) {
  if (is.null(fx$dsep)) {
    return(NULL)
  }

  x <- fx$dsep$x
  y <- fx$dsep$y
  z <- unlist(fx$dsep$z)

  calls <- list(
    caugi = bquote(caugi::d_separated(graphs$cg, .(x), .(y), .(z))),
    bnlearn = bquote(bnlearn::dsep(graphs$bn, .(x), .(y), .(z))),
    dagitty = bquote(dagitty::dseparated(graphs$dg, .(x), .(y), .(z))),
    pcalg = bquote(pcalg::dsep(.(x), .(y), .(z), graphs$gNEL))
  )

  run_bench(calls, "d_separated", fx)
}

caugi is the clear winner here, staying near a tenth of a millisecond on every fixture, including the dense \(n = 10000\) graph. pgmpy is the runner-up, within a few milliseconds throughout. This is the one operation where Tetrad’s compiled code does not save it: its m-separation routine explores paths in a way that scales badly on dense graphs, reaching over a second at \(n = 1000\) and roughly nine seconds at \(n = 10000\)—a striking example of an algorithmic choice dominating the language advantage. Among the R packages, bnlearn and pcalg pay to build a moralized graph on each call (pcalg into the hundreds of milliseconds at \(n = 1000\), slowest of the three R competitors), and dagitty re-parses its DSL; all three are skipped at \(n = 10000\).

Subgraph Extraction

Subgraph extraction is where we explicitly test graph building performance. For caugi we time subgraph(cg, nodes) |> build() together so the CSR rebuild cost is captured. igraph, bnlearn, pgmpy, and Tetrad all return adjacency-backed subgraphs without an analogous index rebuild step. pcalg exposes no native subgraph constructor (users typically call graph::subGraph() on the underlying graphNEL), so it is omitted here.

bench_subgraph <- function(graphs, fx) {
  sub <- unlist(fx$subgraph_nodes)

  calls <- list(
    caugi = bquote({
      sg <- caugi::subgraph(graphs$cg, .(sub))
      caugi::build(sg)
    }),
    igraph = bquote(igraph::subgraph(graphs$ig, .(sub))),
    bnlearn = bquote(bnlearn::subgraph(graphs$bn, .(sub)))
  )

  run_bench(calls, "subgraph", fx)
}

caugi and igraph are the only packages that stay in the low-single-digit milliseconds at \(n = 10000\) (around 1-2 ms). The two run neck-and-neck: caugi is ahead at \(n = 100\) and \(n = 1000\), while igraph edges it out on the largest fixture—remarkably close given that caugi pays for a full CSR rebuild on every call. Everyone else is one to three orders of magnitude slower on the largest fixtures, copying nodes and edges into a fresh object each call: pgmpy reaches tens to hundreds of milliseconds, Tetrad several hundred, and bnlearn over two seconds. The takeaway is that even though caugi graphs are nominally expensive to construct, the rebuild after subgraph() is fast enough to beat adjacency-list constructors that rebuild no indexes at all.