[NetworkX] Benchmark of memory footprint, IO, and performance

[acezen]

1. Systems

system	single or distributed	multi-threads	performance or flexibility	static or dynamic
NetworkX	single	no	flexibility	dynamic
graphscope.nx	distributed	yes	in-between	dynamic

2. Memory Consumption

Use undirected Erdõs-Rényi random graphs, G(n, m), where n represents the number of nodes, and m represents the number of edges in the graph.

Graph size	Memory usage [MB]	-
(Nodes, Edges)	NetworkX	graphscope.nx
(1M, 10M)	3,789	4,474
(1M, 100M)	33,280	21,196
(10M, 100M)	36,864
(50M, 500M)	174,080	116,326

3. Graph basic Operations

We measure execution times of basic graph operations for an Erdõs-Rényi random graph G(n, m).

generation graph execution time(seconds)

Graph size	NetworkX	graphscope.nx
(1M, 10M)	45.8	228
(1M, 100M)	482s	2920

edge existence operation (seconds)

Edges are random, the number of tests is equal to the number of total edges in the graph.	Graph size	Execution time [seconds]	-
(Nodes, Edges)	NetworkX	graphscope.nx
(1M, 10M)	20.027	36,541

delete nodes operation (seconds)

Execution times for deleting 10% of nodes and their corresponding edges from Erdős-Rényi random graph G(1M, 10M).

Graph size	NetworkX	graphscope.nx(one by one)	graphscope.nx(batch)
(1M, 10M)	2.79812	0.078031 * 100000	0.83415 + 3.97145( 0.61 + 3.36) = 4.8056 \n preprocess + op_eval

delete all nodes

• DynamicFragment: 9.36018s = 0.75626(python) + 8.60392(engine)
• DynamicFragment with MutableCSR: 0.85872s = 0.75626 + 0.102458

adding nodes operation (seconds)

Execution times for adding 10% of random generated nodes to Erdős-Rényi random graph G(1M, 10M).

Graph size	NetworkX	graphscope.nx
(1M, 10M)	0.09270	0.88083 + 1.61759(0.85 + 0.75) = 2.498424 \n preprocess + op.eval

• DynamicFragment: 0.1311659s = 0.09925(python) + 0.03191(engine)
• DynamicFragment with MutableCSR: 0.14536s = 0.09925 + 0.046112

delete edges operation (seconds)

Execution times for deleting 10% of edges from Erdős-Rényi random graph G(1M, 10M).

Graph size	NetworkX	graphscope.nx(one by one)	graphscope.nx(batch)
(1M, 10M)	2.11016	0.083911 * 1000000	4.2661 + 11.19209(3.44 + 7.75) = 15.45819 \n preprocess + op.eva

Refactor

• DynamicFragment: 2.93367s = 0.89577(python) + 2.0379(engine)
• DynamicFragment with MutableCSR: 2.16236s = 0.89577(python) + 1.26659(engine)

  adding edges operation (seconds)

  Execution times for adding 10% of random generated edges to Erdős-Rényi random graph G(1M, 10M).

Graph size	NetworkX	graphscope.nx
(1M, 10M)	3.1571	0.3(append) + 0.35(json.dumps) + 5.7(engine) = 6.35
(1M, 10M) add with data { weight=0.5, type="edge"}	3.4257	0.5243 (append) + 1.235(json dumps) + 6.45（engine) = 8.2153
(1M, 10M) add with random edges and new nodes	10.257	0.355(append) + 0.345(json dumps) + 6.524(engine) = 7.224
(50M, 500M)	212.259021	17.7618(append) + 18.1837(json.dumps) + 165.252(engine) = 201.196

profiling of graphscope.nx add_edge operation

• op prepare (5.5188) = 3.2486 (edges dumps to json and append to cache) + 1.14379(put edges to proto payload) + 1.12640(attrs to dict)
• op.eval (14.9556) = 3.5524(rpc: client to engine) + 11.4032(op exec in engine)
  • op exec in engine(11.4032) = 0.042 (get edges from op params) + 8.1323 (parse from edge json and transform to gid) + 2.97676( insert the edges)

optimization 1： dumps the cache to one json str

• op prepare(0.823) = 0.292(append to cache time) + 0.3614( dumps to json) + 0.01005(puts to proto payload)
• op.eval(11.48919) = 0.3(rpc: client to engine) + 11.0829(op execution time in engine)
  • op execution in engine(11.0829) = 0.0032(get json string from op params) + 5.19305(parse json to dynamic) + 2.66777(process the edges: oid to gid) + 2.96967 (insert the edges)

optimization 2: parse json with nlomann-json

• op execution in engine( 5.70104) = 0.00296(get json string from op params) + 0.438243 (parse json with nlomann-json) + 1.98785(convert json to dynamic and process the edges) + 3.01865(insert the edges)

rapidjson (engine)

• 0.05009 (parse json with rapidjson) + 1.5485(convert json to dynamic and process the edges) + 3.13879(insert the edges)

full rapidjson (engine)

• 0.05009 (parse json with rapidjson) + 0.23190(process the edges) + 2.47478( insert the edges)

Refactor (e2e)

• DynamicFragment: 3.97089s = 1.18806(python) + 2.782837(engine)
• DynamicFragment with MutableCSR: 2.30002 = 1.18806(python) + 1.11197(engine)

json.dumps vs pickle.dumps

Edge size	json.dumps	pickle.dumps
1M	0.3614	0.47275
1M with data {weight=0.5, type="edge"}	1.235	0.6837
50M	18.1837	19.79538

4. Graph Algorithms

ego-twitter

algorithm	NetworkX	graphscope.nx (built-in)	graphscope.nx (forward)
pagerank	6.03	2.25	413
sssp length	1.64	4.73s	206
average clustering coefficient	85	2.98
closeness_centrality	> 15h
betweeness centrality	>15h

LiveJournal

algorithm	NetworkX	graphscope.nx (built-in)	graphscope.nx (forward)
pagerank
sssp length
average clustring coefficient
closeness_centrality
betweeness centrality

[acezen]

dataset

datagen-7_5-fb

loading time:

• networkx: 155.5723s
• graphscope.nx(arrow): 14.04830
• graphscope.nx(dynamic): loding 14.04830 + converting 100.4237

sssp

computation time

• networkx: 90.4353s
• graphscope.nx(arrow): 14.353s
• graphscope.nx(dynamic): 48.846s

pagerank

computaion time

• networkx: 171.16753s
• graphscope.nx(arrow): 0.787912
• graphscope.nx(dynamic): 34.7546

  e2e time

  • networkx: 290.8341s
  • graphscope.nx(arrow): 14.8462s
  • graphscope.nx(dynamic): 159s

hits

computaion time

• networkx: 1167.4622s
• graphscope.nx(arrow): 13.54430s
• graphscope.nx(dynamic): 148s

wcc

computaion time

• networkx: 25.4373s
• graphscope.nx(arrow): 2.0527s
• graphscope.nx(dynamic): 17.685s

[acezen]

Found a tool to do benchmark of popular graph / network packages FYI: https://github.com/timlrx/graph-benchmarks

graph-tool benchmark https://graph-tool.skewed.de/performance

[acezen]

snap benchmark: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5361061/

[acezen]

reference:

SNAP benchmark

To evaluate system performance on a real-world graph, we used a friendship graph of the LiveJournal online social network [Leskovec and Krevl 2014] (About 4.8M nodes and 69M edges).

Measured execution times for common graph analytics operations:

• PageRank ( the time it takes to perform 10 iterations)
• clustering coefficient
• weakly connected components
• extracting 3-core of a network
• testing edge existence
• SSSP

Networkit benchmark

Datasets

Algorithms

• BFS
• WCC
• cluster coefficient
• core-decomposition
• calculating the diameter
• community detection
• page rank
• betweeness algorithms

ref: https://github.com/networkit/networkit/tree/master/benchmark

Datasets (bold means selected）:

Name	Type	n	m	Source
fb-Caltech36	Social (friendship)	769	16,656	(Traud et al., 2012)
PGPgiantcompo	Social (trust)	10,680	24,316	(Boguna et al. 2014)
CoAuthorsDBLP	Coauthorship (science)	299,067	977,676	(Bader et al., 2014)
fb-Texas84	Social (friendship)	36,371	1,590,655	(Traud et al., 2012)
Foursquare	Social (friendship)	639,014	3,214,986	(Zafarani and Liu, 2009)
Lastfm	Social (friendship)	1,193,699	4,519,020	(Zafarani and Liu, 2009)
wiki-Talk	Social	2,394,385	4,659,565	(Leskovec and Krevl, 2014)
Flickr	Social (friendship)	639,014	55,899,882	(Zafarani and Liu, 2009)
in-2004	Web	1,382,908	13,591,473	(Boldi et al., 2004)
Actor-collaboration	Collaboration (film)	382,219	15,038,083	(Kunegis, 2013)
eu-2005	Web	862,664	16,138,468	(Boldi et al., 2004)
Flickr-growth-u	Social (friendship)	2,302,925	33,140,017	(Kunegis, 2013)
Con-fiber big	Brain (connectivity)	591,428	46,374,120	http://openconnecto.me
LiveJournal	Social (friendship)	4.8M	69M	Leskovec and Krevl 2014
Twitter	Social (followership)	15,395,404	85,331,845	(Zafarani and Liu, 2009)
uk-2002	Web	18,520,486	261,787,258	(Boldi et al., 2004)
uk-2007-05	Web	105,896,555	3,301,876,564	(Boldi et al., 2004)

Algorithms:

• Pagerank
• clustering coefficient
• weakly connected components
• betweeness algorithms (fb-Texas84, in-2004)
• k-core
• SSSP

Graph-tool benchmark

Dataset: PGP web of trust network N=39,796 vertices and E=301,498 edges

Algorithms:

• SSSP
• clustering
• PageRank
• K-core
• Minimun spanning tree
• Betweenness

ref: https://graph-tool.skewed.de/performance

timlrxx benchmark

Datasets:

• Amazon product co-purchasing network from March 2 2003, 262k nodes, 1.2m edges
• Web graph from Google, 875k nodes, 5.1m edges
• Pokec online social network, 1.6m nodes, 30.6m edges

Algorithms:

• single source shortest path
• page rank
• k-core decomposition
• strongly connected components

[acezen]

rapidjson::Value vs folly::Dynamic

NUM = 100000000

folly::dynamic

Create Int objects: 5180901483 nanoseconds Read Int objects: 40 nanoseconds Create double objects: 5152739898 nanoseconds Read double objects: 40 nanoseconds Create string objects: 5960905406 nanoseconds Read string objects: 469619201 nanoseconds Create dict objects: 97816101798 nanoseconds Read dict objects: 75542622651 nanoseconds MEM: 58.4g

parseJson and toJson (1M edges) parseJson: 12.5208 s toJson: 2.78841 s

rapidjsonValue

Create Int objects: 4375781716 nanoseconds Read Int objects: 54 nanoseconds Create double objects: 4361932757 nanoseconds Read double objects: 335556902 nanoseconds Create string objects: 5096663566 nanoseconds Read string objects: 67 nanoseconds Create dict objects: 31279850071 nanoseconds Read dict objects: 3407108904 nanoseconds MEM: 65.9g

parseJson and toJson (1M edges) parseJson: 0.197372 s toJson: 0.17069 s

[acezen]

Refactor

traverse

graph	DynamicFragment	DynamicFragment(MutableCSR)	MutableFragment	DynamicProjectedFragment
livejournal	10.371	0.010999	0.0105071	0.0104051

pagerank

graph	DynamicFragment	DynamicFragment(MutableCSR)
twitter	0.112367	0.01387
gnm random(1M, 10M)	0.287429	0.02356
livejounal	1.91776	0.169634

[acezen]

Iterate nodes / edges performance with data caching

iterate nodes

cnt = 0
for n in G.nodes:
    cnt = cnt + 1

graph	NetworkX	graphscope.nx	graphscope.nx without cache
gnm (1M, 10M)	0.06205149s	0.211255s	18.986365s

profiling

• fetch node cache from engine: 0.108541s
• deserialize json: 0.037926s
• iteration time: 0.064788s

I/O asynchronize

cnt = 0
for n in G.nodes:
    for i in range(100):
        cnt = cnt + 1

graph	NetworkX	graphscope.nx
gnm (1M, 10M)	3.22714s	3.270931s

cnt = 0
for n in G.nodes:
    cnt = cnt + 1

graph	NetworkX	graphscope.nx
datagen-7_8_zf (16M, 41M)	0.82825s	2.76879s
soc-livejounal(5M, 69M)	0.43554s	0.28923s

cnt = 0
for n in G.nodes:
    for i in range(10):
         cnt = cnt + 1

graph	NetworkX	graphscope.nx
datagen-7_8_zf (16M, 41M)	7.91136s	9.296s
soc-livejounal(5M, 69M)	2.59347s	2.35384s

iterate edges

cnt = 0
for u in G.adj:
     for v in G.adj[n]:
          cnt = cnt + 1

graph	NetworkX	graphscope.nx	graphscope.nx without cache
gnm (1M, 10M)	4.150698s	12.957603s	> 1200s

profiling

• fetch node cache: 0.108541 + loads json: 0.037926
• fetch neighbors cache: 5.1671934 + loads json: 3.501857
• iteration time: 4.16324

I/O asynchronize

graph	NetworkX	graphscope.nx
gnm (1M, 10M)	4.150698s	8.10182

cnt = 0
for u in G.adj:
     for v in G.adj[n]:
          for i in range(10):
              cnt = cnt + 1

graph	NetworkX	graphscope.nx
gnm (1M, 10M)	13.50960s	17.04617

cnt = 0
for u in G.adj:
     for v in G.adj[n]:
           cnt = cnt + 1

graph	NetworkX	graphscope.nx
datagen-7_8_zf (16M, 41M)	26.178357s	45.2949s
soc-livejounal(5M, 69M)	15.71435s	19.19453s