# Implementing the LDBC Graphalytics benchmark **URL:** \ **Category:** Usage\ **Tags:** C\ **Created:** [21 August 2020 10:22 UTC](https://igraph.discourse.group/t/implementing-the-ldbc-graphalytics-benchmark/417 "2020-08-21T10:22:27Z")\ **Posts on this page:** 15\ **Page:** 1
**Author:** ![szarnyasg](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/szarnyasg/32/339_2.png) [@szarnyasg](https://igraph.discourse.group/u/szarnyasg)\ **Post date:** [21 August 2020 10:22 UTC](https://igraph.discourse.group/t/implementing-the-ldbc-graphalytics-benchmark/417/1 "2020-08-21T10:22:27Z")
Dear igraph forum members, I’d like to start an implementation of the [LDBC Graphalytics benchmark](https://ldbc.github.io/ldbc_graphalytics_docs/graphalytics_spec.pdf) on top of igraph’s C API. The typical challenges for implementing this benchmark have mostly do to with the specific algorithms prescribed by the specification. The ones that could work out of the box: - Connected components (WCC), single-source shortest path (SSSP) are quite unambigious in general so they are usually trivial to implement. - The BFS algorithm requires the “levels” of the nodes. I think this is called `rank` in `igraph_bfs`. The ones that are more problematic: - The PageRank algorithm treats dangling vertices different from others, following the approach of the [“Ranking the Web Frontier”](http://ambuehler.ethz.ch/CDstore/www2004/docs/1p309.pdf) paper. This seems unsupported by igraph. - The LCC (local clustering coefficient) algorithm, a.k.a. transitivity, has a directed variant in Graphalytics. I think this is not supported in igraph. - The CDLP (community detection using label propagation) algorithm uses a deterministic variant which requires the selection of the “min mode” label (i.e. the smallest value of the most common label) among the neighbours. I don’t think this is currently supported in `igraph_community_label_propagation`. Additionally, loading the data from the vertex/edge files usually takes a bit of “data hammering”. I’d like to start this project in September, preferably as a student project. Let me know if you have any comments or suggestions. Gabor Szarnyas ---
**Author:** ![szhorvat](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/szhorvat/32/3_2.png) [@szhorvat](https://igraph.discourse.group/u/szhorvat)\ **Post date:** [21 August 2020 11:06 UTC](https://igraph.discourse.group/t/implementing-the-ldbc-graphalytics-benchmark/417/2 "2020-08-21T11:06:06Z")
> [@szarnyasg](#): > > The BFS algorithm requires the “levels” of the nodes. I think this is called `rank` in `igraph_bfs` . Do you mean the level in the BFS tree, i.e. distance from root? Is that not the same as (unweighted) SSSP? > [@szarnyasg](#): > > The LCC (local clustering coefficient) algorithm, a.k.a. transitivity, has a directed variant in Graphalytics. I think this is not supported in igraph. There is more than one way to generalize this to directed graphs, and we have not yet decided which variant(s) to include. If you have any thoughts on this, let us know (here or in [Generalization of transitivity to directed graphs · Issue #1218 · igraph/igraph · GitHub](https://github.com/igraph/igraph/issues/1218)) > [@szarnyasg](#): > > The CDLP (community detection using label propagation) algorithm uses a deterministic variant which requires the selection of the “min mode” label (i.e. the smallest value of the most common label) among the neighbours. I don’t think this is currently supported in `igraph_community_label_propagation` . @vtraag, any input on this? ---
**Author:** ![szarnyasg](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/szarnyasg/32/339_2.png) [@szarnyasg](https://igraph.discourse.group/u/szarnyasg)\ **Post date:** [21 August 2020 11:08 UTC](https://igraph.discourse.group/t/implementing-the-ldbc-graphalytics-benchmark/417/3 "2020-08-21T11:08:41Z")
> [@szhorvat](#): > > Do you mean the level in the BFS tree, i.e. distance from root? Is that not the same as (unweighted) SSSP? Yes it is the same problem. What’s the preferred way of doing this in igraph? I will comment on the transitivity issue. ---
**Author:** ![szhorvat](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/szhorvat/32/3_2.png) [@szhorvat](https://igraph.discourse.group/u/szhorvat)\ **Post date:** [21 August 2020 11:12 UTC](https://igraph.discourse.group/t/implementing-the-ldbc-graphalytics-benchmark/417/4 "2020-08-21T11:12:56Z")
You can use [`igraph_shortest_paths`](https://igraph.org/c/doc/igraph-Structural.html#igraph_shortest_paths). I would expect it to be more efficient than `igraph_bfs`, which retains more information about the BFS tree (I have not tested their performance!). ---
**Author:** ![vtraag](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/vtraag/32/38_2.png) [@vtraag](https://igraph.discourse.group/u/vtraag)\ **Post date:** [21 August 2020 19:34 UTC](https://igraph.discourse.group/t/implementing-the-ldbc-graphalytics-benchmark/417/5 "2020-08-21T19:34:56Z")
> [@szarnyasg](#): > > The CDLP (community detection using label propagation) algorithm uses a deterministic variant which requires the selection of the “min mode” label (i.e. the smallest value of the most common label) among the neighbours. I don’t think this is currently supported in `igraph_community_label_propagation` . I don’t understand the reason for doing this. It of course is a clear way to break ties, but it is also more likely to lead to overly large communities (although that is a general problem of LPA anyway). Do you have any particular reference that this is a good idea and preferred over breaking the tied randomly? Another consideration is that the current implementation is asynchronous, and nodes are updated in a random order. Hence, even if breaking ties would be changed, it would still not be deterministic. Of course, this can be solved by seeding the RNG. However, from your description, the objective might actually be to get identical results across implementations. That would then require identical RNG implementations, but that might be going to far. Can you elaborate on the requirement of making it deterministic? > [@szarnyasg](#): > > Yes it is the same problem. So the SSSP and the BFS are not run as separate benchmarks then? After all, they are identical problems. ---
**Author:** ![szarnyasg](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/szarnyasg/32/339_2.png) [@szarnyasg](https://igraph.discourse.group/u/szarnyasg)\ **Post date:** [21 August 2020 19:53 UTC](https://igraph.discourse.group/t/implementing-the-ldbc-graphalytics-benchmark/417/6 "2020-08-21T19:53:40Z")
> I don’t understand the reason for doing this. It of course is a clear way to break ties, but it is also more likely to lead to overly large communities (although that is a general problem of LPA anyway). Do you have any particular reference that this is a good idea and preferred over breaking the tied randomly? The tie-breaking rule for selecting the minimum value isn’t there to ensure better communities. Instead, its sole purpose is to ensure determinism. It is not very realistic and it also gave me some headache during the GraphBLAS implementation. See [Section 2.3.4 Community Detection using Label Propagation (CDLP)](https://ldbc.github.io/ldbc_graphalytics_docs/graphalytics_spec.pdf#page=16) in the spec for the formal specification of the propagation rule. > So the SSSP and the BFS are not run as separate benchmarks then? After all, they are identical problems. SSSP is only executed for data sets with edge weights. For data sets without edge weights, the SSSP algorithm is skipped. ---
**Author:** ![tamas](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/tamas/32/1261_2.png) [@tamas](https://igraph.discourse.group/u/tamas)\ **Post date:** [21 August 2020 19:58 UTC](https://igraph.discourse.group/t/implementing-the-ldbc-graphalytics-benchmark/417/7 "2020-08-21T19:58:37Z")
> [@vtraag](#): > > Another consideration is that the current implementation is asynchronous, and nodes are updated in a random order. Asynchronous updates were suggested in the preprint of the label propagation algorithm on [arXiv](https://arxiv.org/pdf/0709.2938.pdf) - I don’t know whether the final publication is identical, but most likely it is. Basically, the authors argue that synchronous updates are discouraged because it may cause oscillations if the graph contains (near-)bipartite subgraphs. ---
**Author:** ![vtraag](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/vtraag/32/38_2.png) [@vtraag](https://igraph.discourse.group/u/vtraag)\ **Post date:** [21 August 2020 21:03 UTC](https://igraph.discourse.group/t/implementing-the-ldbc-graphalytics-benchmark/417/8 "2020-08-21T21:03:48Z")
> [@tamas](#): > > synchronous updates are discouraged because it may cause oscillations if the graph contains (near-)bipartite subgraphs. Yes, this was also my understanding indeed. From the graphylitics specs it seems that a synchronous version would also be required (in addition to the tie breaking requirement). Perhaps I don’t fully understand it, but why should a benchmark include an algorithm that in, that particular implementation, is actually never going to be used? ---
**Author:** ![tamas](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/tamas/32/1261_2.png) [@tamas](https://igraph.discourse.group/u/tamas)\ **Post date:** [21 August 2020 21:58 UTC](https://igraph.discourse.group/t/implementing-the-ldbc-graphalytics-benchmark/417/9 "2020-08-21T21:58:58Z")
Well, on one hand I totally understand the need for eliminating randomness from benchmarks where possible – it easily becomes unmanageable (in terms of time / computational effort) if you need to average the runtime of an algorithm over, say, 10000 runs in order to get a reliable estimate of its real performance. On the other hand, there are graph algorithms where randomness is inherently needed for the algorithm to work as intended. The original label propagation algorithm of Raghavan et al is one such example. In the manuscript, the authors even propose to run the algorithm several times in order to discover alternative solutions when the community structure is not clear-cut (which also implies that there is not even a single “correct” solution that one could use to validate an implementation of the algorithm). In my opinion, these algorithms are not well-suited for benchmarks because you lose the very essence of the algorithm if you eliminate non-determinism. Label propagation was probably chosen because it scales up to larger graphs easily due to its nearly linear nature. I’m saying “nearly” because you need an extra BFS step if you want to ensure connectedness for the detected communities. And also because it is probably much easier to implement in a distributed manner over large graphs. ---
**Author:** ![vtraag](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/vtraag/32/38_2.png) [@vtraag](https://igraph.discourse.group/u/vtraag)\ **Post date:** [22 August 2020 07:44 UTC](https://igraph.discourse.group/t/implementing-the-ldbc-graphalytics-benchmark/417/10 "2020-08-22T07:44:35Z")
> [@tamas](#): > > I totally understand the need for eliminating randomness from benchmarks where possible Yes, I agree. > [@tamas](#): > > these algorithms are not well-suited for benchmarks because you lose the very essence of the algorithm if you eliminate non-determinism Exactly! It seems a bit strange to me to require an algorithm that is only implemented for the sole purpose of the benchmark. > [@tamas](#): > > it is probably much easier to implement in a distributed manner over large graphs. This is probably another reason why a synchronous implementation would be required. ---
**Author:** ![szarnyasg](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/szarnyasg/32/339_2.png) [@szarnyasg](https://igraph.discourse.group/u/szarnyasg)\ **Post date:** [22 August 2020 13:31 UTC](https://igraph.discourse.group/t/implementing-the-ldbc-graphalytics-benchmark/417/11 "2020-08-22T13:31:13Z")
Regarding determinism, I understand your stance. Adding a new algorithm, optimizing it, then maintaining it is probably too much of a burden if its sole purpose is to be used in a benchmark. I wasn’t part of the team when the benchmark was designed in 2014-2016 but since then, I’ve had many discussions with members of the original team. They have emphasized that one of their guiding principles for designing the benchmark was ensuring deterministic behaviour because it makes both the performance comparison and the validation of results easier. This is so important that the fact that the algorithms in benchmark are deterministic is mentioned right away in the abstract of the [Graphalytics VLDB paper](http://www.vldb.org/pvldb/vol9/p1317-iosup.pdf). The team also told me that some algorithms, such as forest fire and a spring-based graph layout (visualization) algorithm were discarded from the benchmark as they couldn’t be made deterministic in a meaningful way. From a benchmarking perspective, CDLP is an interesting algorithm because it collects the labels from the neighbours of a vertex and pushes them through a non-trivial aggregation function, “random mode value”, which makes for a more complicated access pattern than the one used in BFS/SSSP/PageRank. By making it deterministic, this aggregation function becomes “min mode value” which is even more difficult. For reference, the matrix-based GraphBLAS implementations of BFS/SSSP/PageRank use matrix-vector multiplication; the non-deterministic CDLP would need an adjacency matrix-diagonal matrix multiplication with row-wise reduce (but I have not yet implemented this), while the deterministic CDLP implementation also needs sorting; and LCC needs matrix-matrix multiplication. It may very well be the case that deterministic CDLP algorithm does not make a whole lot of sense for practical graph analytics – after all, there was no network scientist involved in the design of the benchmark. According to the Graphalytics VLDB paper, the algorithms in the benchmarks were selected after surveying 168 “graph analysis articles published in ten representative conferences on databases, high-performance computing, and distributed systems (e.g., VLDB, SIGMOD, SC, PPoPP)”, so there’s a clear bias for algorithms that are used in core system engineering (DB/HPC, parallel programming) papers. In the benchmark implementation efforts so far, libraries either didn’t have a CDLP algorithm or had fairly simple ones. When a library didn’t have a CDLP algorithm, we just implemented a deterministic one. For the ones with an existing CDLP/LPA algorithm, we could adjust them to ensure deterministic behaviour, typically by adding an if condition and a few lines of code. It seems that neither is the case for igraph, which [uses](https://github.com/igraph/igraph/blob/eca5e809aab1aa5d4eca1e381389bcde9cf10490/src/community.c#L2382-L2664) a fairly sophisticated CDLP algorithm. So… for the time being, we might opt to skip this algorithm and focus on the other algorithms instead. The Graphalytics specification is still released as “v1.0 draft” and there are no audited benchmarks yet, so, in theory, the specification can be adjusted. This would need thorough discussions with the Graphalytics team and approval from the LDBC board but it is possible. We would still need some way of validating results, e.g. the researcher/auditor running the benchmark should sample the nodes and ascertain whether the community structure is roughly as expected. Let us know if you have any suggestions for this. PS: I found the comment about the oscillation very interesting. I have actually witnessed this when running the deterministic CDLP algorithm in [small graphs](http://mit.bme.hu/~szarnyas/grb/graphblas-introduction.pdf#page=120), now I know why it happens. ---
**Author:** ![szhorvat](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/szhorvat/32/3_2.png) [@szhorvat](https://igraph.discourse.group/u/szhorvat)\ **Post date:** [4 February 2021 16:24 UTC](https://igraph.discourse.group/t/implementing-the-ldbc-graphalytics-benchmark/417/12 "2021-02-04T16:24:24Z")
@szarnyasg igraph 0.9 is expected to be released in less than 2 week. It would be nice to look into benchmarking after that. Do you have an update on this, did you find an interested student? ---
**Author:** ![szarnyasg](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/szarnyasg/32/339_2.png) [@szarnyasg](https://igraph.discourse.group/u/szarnyasg)\ **Post date:** [4 February 2021 23:52 UTC](https://igraph.discourse.group/t/implementing-the-ldbc-graphalytics-benchmark/417/13 "2021-02-04T23:52:08Z")
@szhorvat unfortunately, I haven’t found an interested student. I drafted a Python script to implement the benchmark in December. I got this far: [igraph-graphalytics.py · GitHub](https://gist.github.com/szarnyasg/3a1961918f48ed4e5f47d30ae2c72956) BFS, SSSP, and WCC work fine. The rest would require some development - CDLP: deterministic choice of label, LCC: support a directed definition, PageRank: different stopping criterion (fixed number of iterations vs. reaching a fixed point). Adjusting these seems doable but non-trivial. Do you see any of changes regarding these algorithms in v0.9? PS: the Graphalytics specification is now on arXiv: [[2011.15028] The LDBC Graphalytics Benchmark](https://arxiv.org/abs/2011.15028) ---
**Author:** ![szhorvat](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/szhorvat/32/3_2.png) [@szhorvat](https://igraph.discourse.group/u/szhorvat)\ **Post date:** [5 February 2021 09:18 UTC](https://igraph.discourse.group/t/implementing-the-ldbc-graphalytics-benchmark/417/14 "2021-02-05T09:18:42Z")
I’d say the first priority would be to set up a reliable benchmarking framework and methodology. Benchmarking is not easy. At the moment we all work on laptops, which are often unstable. For some reason, with igraph’s existing benchmark programs I was having a lot of difficulty getting consistent results, and I’m not sure why (see `tests/benchmarks/igraph_random_walk.c`). Perhaps my laptop is just usntable (thermal throttling?) But that won’t explain why _this_ benchmark behaves worse than others … Since you have have worked extensively with benchmarks, some advice/guidance/tips would be very welcome! I assume that benchmarking on laptops is just not the right way. Regarding the algorithms, from the above discussion it seems in order to be able to support consistent and deterministic benchmarking, Graphalytics had to choose some algorithm variants which are not the best for practical use. Therefore the way forward is not to include them into igraph directly, but to implement them _using_ igraph (in C of course) as a separate program. I think that they would still be a very useful benchmark for us as they exercise parts of the library. - CDLP — According to the discussion above, the Graphalytics version is not justified from a usefulness/practicality (as opposed to benchmarking) perspective. Thus this will need a separate implementation. - LCC — There are many possible generalizations of the clustering coefficient to directed graphs. We simply need more time come up with a sufficiently general approach that will allow computing multiple reasonable variants. Likely the Graphalytics version will be among these too. - PageRank: Graphalytics seems to use power iteration, so this too needs to be implemented separately. Power iteration is not the best or most robust way to compute PageRank (at least for graphs that fit in memory). igraph does not use it anymore (it was removed from 0.9). The old (now discarded) implementation can be used as a starting point for writing a separate benchmarking-specific version. ---
**Author:** ![szarnyasg](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/szarnyasg/32/339_2.png) [@szarnyasg](https://igraph.discourse.group/u/szarnyasg)\ **Post date:** [6 February 2021 14:46 UTC](https://igraph.discourse.group/t/implementing-the-ldbc-graphalytics-benchmark/417/15 "2021-02-06T14:46:28Z")
I have recently discussed microbenchmarking with the author of the Efficient Java Matrix Library. Basically, using a well-cooled desktop/workstation machine is the minimum required setup for meaningful microbenchmarks. The ideal way to go would be a bare-metal server with Xeon/EPYC CPUs. - [JMH For Automated Runtime Regression Check · Issue #94 · lessthanoptimal/ejml · GitHub](https://github.com/lessthanoptimal/ejml/issues/94#issuecomment-752646939) - [Microbenchmarking calls for idealized conditions – Daniel Lemire's blog](https://lemire.me/blog/2018/01/16/microbenchmarking-calls-for-idealized-conditions/) - [Microbenchmarking is hard: virtual machine edition – Daniel Lemire's blog](https://lemire.me/blog/2018/01/21/microbenchmarking-is-hard-virtual-machine-edition/) The cited PageRank paper is indeed somewhat ambiguous. However, I haven’t been able to find a better paper to cite for the Graphalytics benchmark. (The Graphalytics VLDB paper only cited the original PageRank paper which handles dangling vertices in a crude way by removing them during computation.) Another citation I can think of is the [Adaptive Methods for the Computation of PageRank](https://academic.microsoft.com/paper/2108272874/) paper. I agree that having Graphalytics-specific implementations is a good approach and I’m glad to assist with these, I might be able invest some time in coding these during the spring. I have a bunch of deadline in the next two weeks but I will pick up this thread afterwards.