I am trying to re-implement (in Julia) some old C++ code I wrote a while ago to do certain operations on graphs, however, I’m not confident the performance is as good as I remember it… I was hoping someone might be able to take a look at the MWE below and let me know if they see anything out of place, bad form, etc.
To briefly describe the code, I have an algorithm that is dominated by access, searches, edge additions, and edge removals on a graph. I need to loop over every single dyad in a graph multiple times - each time performing a set of calculations on the graph where we compare a graph with the tie to one without.
using BenchmarkTools, LightGraphs
# Change in number of edges when toggling a particular edge
function delta_edge(G, i, j)
@inbounds if i == j
return 0.0
elseif G[i,j]
return -1.0
else
return 1.0
end
end
# Change in number of mutual dyads when toggling an edge
function delta_mutual(g, i, j)
@inbounds if i == j
return 0.0
elseif !g[j, i]
return 0.0
elseif !g[i, j]
return 1.0
else
return -1.0
end
end
# Change in number of transitive triples when toggling an edge
# For a given dyad (i,j), loop over all third parties and see how many
# such triples are created/destroyed.
# This scales badly with graph size (expected), but should still be a bit better.
function delta_ttriple(g, i, j)
@inbounds if i == j
return 0.0
else
c = 0
for k in 1:size(g)[1]
c += (g[j, k] && g[i, k]) + (g[k, j] && g[i, k]) + (g[k, j] && g[k, i])
end
if g[i,j]
return -convert(Float64, c)
else
return convert(Float64, c)
end
end
end
# Mutating function to toggle an edge and return a small vector of graph change statistics
function toggle!(x, g, i, j)
@inbounds x[1] = delta_edge(g, i, j)
@inbounds x[2] = delta_mutual(g, i, j)
@inbounds x[3] = delta_ttriple(g, i, j)
end
# Function to just iterate over all dyads in the graph, but only do "heavy"
# calculations for ones that have edges. This doesn't do anything, but uses
# the same basic operations as the "real" function.
function partial_single_loop!(x, g)
n = size(g)[1]
@inbounds for j in 1:n
for i in 1:n
!g[i, j] && continue
toggle!(x, g, i, j)
if rand() < 0.5
g[i, j] = !g[i, j]
end
end
end
end
# Iterate over all pairs of vertices in the graph
# Since the graph has a density of ~0.05, this means performing
# about 20x the number of operations than the previous function,
# on average.
function full_single_loop!(x, g)
n = size(g)[1]
@inbounds for j in 1:n
for i in 1:n
toggle!(x, g, i, j)
if rand() < 0.5
g[i, j] = !g[i, j]
end
end
end
end
# Loop over the graph multiple (K) times
# If K = 5, I'd expect to see ~100x slower speed
# than the first function, on average, and ~5x
# slower than the second function.
function multi_loop!(x, g, K)
n = size(g)[1]
@inbounds for k in 1:K
for j in 1:n
for i in 1:n
toggle!(x, g, i, j)
if rand() < 0.5
g[i, j] = !g[i, j]
end
end
end
end
end
# Generate some test data and benchmark
g1 = erdos_renyi(200, 0.05; is_directed = true)
a1 = convert(Array{Bool, 2}, collect(adjacency_matrix(g1)))
x1 = zeros(3)
@btime partial_single_loop!($x1, $a1)
x1 = zeros(3)
@btime full_single_loop!($x1, $a1)
x1 = zeros(3)
@btime multi_loop!($x1, $a1, 5)
#=
Timings:
(1) ~18us to cover ~2000 edges
(2) ~14ms to cover ~40k dyads
(3) ~72ms to cover 40k dyads 5 times
=#
None of the functions allocate.
My main interest is in getting the “multi_loop” function much, much faster - if possible.
When I benchmark the version where I just loop over the edges of the graph, it’s very, very fast (exactly as expected). However, moving to cover the full set of dyads scales badly. Naively, if the first function takes ~ 18us to do 2k operations, it seems odd that the last function should take 72ms to do 200k of the same operations. (Although at least the scaling seems about right going from the second to the third function.)
Any way, if anyone has suggestions for this sort of code, let me know. It’s not slow, but it’s reaching the borderline of usability, in what is a pretty small graph; I want to make sure I’m not doing something wrong.
(FWIW, I tried using LightGraphs first; it was a bit slower for small graphs and much faster for large graphs, as expected… as long as I didn’t need to remove an edge in the algorithm. As soon as I did that, performance tanked by a couple of orders of magnitude…)
