# Improving performance of network sampling/inference algorithm

**URL:** <https://discourse.julialang.org/t/improving-performance-of-network-sampling-inference-algorithm/45536>\
**Category:** General Usage\
**Created:** [August 25, 2020, 8:38pm UTC](https://discourse.julialang.org/t/improving-performance-of-network-sampling-inference-algorithm/45536 "2020-08-25T20:38:13Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![Adam\_Haber](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/adam_haber/32/9242_2.png) [@Adam\_Haber](https://discourse.julialang.org/u/Adam_Haber)\
**Post date:** [August 25, 2020, 8:38pm UTC](https://discourse.julialang.org/t/improving-performance-of-network-sampling-inference-algorithm/45536/1 "2020-08-25T20:38:13Z")

</div>

Hi,

I’m trying to write a Julia package that does roughly what R’s [ergm](https://cran.r-project.org/web/packages/ergm/ergm.pdf) package does: fit, simulate and diagnose exponential-family models of networks. R’s ergm is an excellent and a very mature package, and I’m definitely not trying to port all of it; I’m aiming for a blend of different functionalities from the ergm ecosystem that would suit my needs (and hopefully the needs of other Julia users interested in network modelling). The main motivation is “hackability” - adjusting ergm to my needs was difficult, and I want something that would allow me to extend/tweak existing functionality in a high-level language without compromising performance.

I have an initial working version [here](https://github.com/adamhaber/ergmjl), and so far I wasn’t able to get close to the performance of R’s ergm sampling/inference algorithms (written mostly in C); I’ve read several performance guides that were previously suggested on this forum, and tried to use different macros to get additional speedups, but I’ve reached a point where I would really appreciate feedback from more experienced Julia users (I’m quite new to the language).

In case anyone’s interested:

- `base.jl` contains the main data structure, and various functions to compute graph and ERGM change statistics.
- `inference.jl` contains an implementation of the double MH sampler from Liang, 2010.
- `sa.jl` contains an implementation of the Stochastic Approximation algorithm from the appendix of Snijders, 2002.
- Notebooks contain various experiments and comparisons with R’s ergm using `RCall`.

Most of this work was already done by @opera_malenky, who previously discussed the data structure on [this](https://discourse.julialang.org/t/trying-to-identify-possible-optimizations-or-errors-in-a-graph-algorithm/19998) thread; I’ve added the `sa.jl` file and other small changes.

I’d be happy to provide further details regarding the code/algorithms/anything else that might be helpful.

---

<div class="post-metadata">

**Author:** ![opera\_malenky](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/opera_malenky/32/8213_2.png) [@opera\_malenky](https://discourse.julialang.org/u/opera_malenky)\
**Post date:** [August 27, 2020, 3:22pm UTC](https://discourse.julialang.org/t/improving-performance-of-network-sampling-inference-algorithm/45536/2 "2020-08-27T15:22:09Z")

</div>

Although I wrote some of that early code for research, and didn’t focus on optimization too much, I did plenty of benchmarking while testing different things.

One thing I do recall is that both that code and statnet use the same approach (IIRC) for getting the overall subgraph counts (toggling a tie “off”, counting how the network statistics change, going to the next tie, repeat). I found that the Julia code was much faster than statnet at just getting a simple count of graph statistics (see the `subgraphcount` function [here](https://github.com/adamhaber/ergmjl/blob/master/base.jl)).

But for some reason, my original code was always significantly slower than statnet at generating new random graphs (which are an important part of most of the ergm estimation algorithms out there), which would be the `rgraph` function in the [repository](https://github.com/adamhaber/ergmjl/blob/master/base.jl).

But, of course, the algorithms for that original code and what statnet uses (by default) for generating random graphs are different – statnet uses a TNT (tie-no-tie) sampler, as opposed to just naively iterating over each edge – and I never quite compared how long it took the two sets of code to generate new graphs that were sufficiently uncorrelated with the original graph, so it may be that simply comparing the raw time to generate X number of new graphs was a misleading metric… however, I never really dug into that.

Another aspect is that statnet’s network objects use (IIRC) an edgelist representation, instead of a matrix-based representation. I did that because the code is dominated by finding/changing specific edges. Those operations are very fast in a matrix, but a lot slower in an edgelist; however, it could be that something about the way statnet generates random graphs is much more amenable to an edgelist format (I tend to doubt it, but it’s a possibility).

Anyway, I’m especially curious if anyone sees ways to speed up either the `rgraph` or `change_scores` functions.

I’m reasonably sure that most of the various `delta_` functions for particular subgraph change scores are about as fast as they could be. However, this is where the algorithm spends most of it’s time, so if anyone **does** see a way to speed those up – especially the `_ttriple` and `_ctriple` functions, which are the most computationally expensive – it would be a big boost.

---

<div class="post-metadata">

**Author:** ![Jakob](https://avatars.discourse-cdn.com/v4/letter/j/71c47a/32.png) [@Jakob](https://discourse.julialang.org/u/Jakob)\
**Post date:** [October 26, 2020, 12:12pm UTC](https://discourse.julialang.org/t/improving-performance-of-network-sampling-inference-algorithm/45536/3 "2020-10-26T12:12:25Z")

</div>

In case you don’t know it yet, I recently stumbled over [this](https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3845520/) paper, which has some information on the internal graph representation used by the `ergm` package (section 4). Apparently they use nodewise edgelists separated for incoming and outgoing edges in some binary tree format. I’m not sure how that in theory compares on computing statistics and edge access to something like `LightGraph`’s adjacency list model.