[Feature/improvement] Faster/more scalable graph algorithms with GraphBLAS

[bergkvist]

Recent radical innovation

There has been some radical innovation in graph processing the last few years

GraphBLAS efficiently represents and operates on graphs as sparse matrices. It provides building blocks for creating performant - and highly parallel/scalable graph algorithms.

I think pandapower could benefit greatly in some ways from utilizing GraphBLAS (in terms of performance/scalability)

Potential use cases

Connected Components

FastSV from the litterature review is ~20x faster than the NetworkX implementation for a network with ~300,000 buses/lines - and that is in single threaded, blocking mode. The algorithm is close to being embarrassingly parallel

Short Circuit Analysis

Since graph edges in GraphBLAS can be complex numbers - this might be a perfect fit for circuit analysis/simplifications. The complex number of an edge can represent its impedance.

Other Graph related problems

I'm guessing there are probably more graph-related things in pandapower that could become faster and more scalable with GraphBLAS.

Litterature review

(2017) SuiteSparse:GraphBLAS: graph algorithms in the language of linear algebra

GraphBLAS takes advantage of sparse matrices, as well as the fact that graph operations can be effectively represented by linear algebra. The implementation is written in C.

• (Source code/GitHub)

---

(Jan 2019) LAGraph: library plus a test harness for collecting algorithms that use the GraphBLAS

While GraphBLAS provides the linear algebra primitives for building more complex graph algorithms - LAGraph collects efficient algorithms built on top of GraphBLAS.

• (Source code/GitHub)

---

(Aug 2019) GraphBLAST: A High-Performance Linear Algebra-based Graph Framework on the GPU

GraphBLAST is a GPU implementation of GraphBLAS

• (Source code/GitHub)

---

(Oct 2019) FastSV: a distributed memory connected-component algorithm with fast convergence

Significantly faster alternative to pandapower.topology.connected_components

• (Source code/GitHub)

---

(Jun 2019) pygraphblas: GraphBLAS for Python

Python binding for GraphBLAS

• (Source code/GitHub)

---

[FlorianShepherd]

Hi @bergkvist ,

nice idea. I also wrote an interface for the graph tool a while ago:
https://github.com/e2nIEE/pandapower/blob/4a3dc519ab33a5de9baf6fe75d3156bdb432861c/pandapower/topology/graph_tool_interface.py

since networkx was too slow for my case as well. There is just some licensing issue and also it doesn't work so easily on windows. I'm not sure about apache 2.0 and GraphBLAS but it looks definitely cool

Best
Florian

[lthurner]

Looks good. One question: how easy/difficult can GraphBLAS be installed on Unix/Windows respectively?

[bergkvist]

On Ubuntu/Debian: https://packages.debian.org/sid/libgraphblas3

sudo apt install libgraphblas3

On Arch Linux/Manjaro:

yay graphblas

Building from source on Linux, and probably also macOS (requires CLang)

On a 2-core laptop-cpu this can take as much as a couple of hours, so this is probably something you'd want to avoid doing on installation. Precompiled binaries/shared libraries are around 50MB in size on Linux.

# The "stable" branch is default, so no need to switch branch after cloning
git clone https://github.com/DrTimothyAldenDavis/GraphBLAS
cd GraphBLAS
make JOBS=8
sudo make install

After running `sudo make install`, the following files/symlinks will appear in the file system:

/usr/local/lib/
  - libgraphblas.so.3.3.3
  - libgraphblas.so.3
  - libgraphblas.so

/usr/local/include/
  - GraphBLAS.h

I've created a Docker image that contains shared libraries/header files (and nothing else) for GraphBLAS and LAGraph here: https://hub.docker.com/r/bergkvist/lib-lagraph

---

Building from source on Windows

http://mit.bme.hu/~szarnyas/grb/GraphBLAS_UserGuide.pdf (page 216)

[bergkvist]

Just discovered that GraphBLAS is available on conda-forge. It is not available here for Windows, but this is only a matter of time.

https://anaconda.org/conda-forge/graphblas

I created an issue for Windows support here: conda-forge/graphblas-feedstock#8

[bergkvist]

Update: pygraphblas is now available on conda-forge, since 19 hours ago.

[lthurner]

Cool, then installation shouldn't be an issue.

About the potential use cases:

Connected Components
FastSV from the litterature review is ~20x faster than the NetworkX implementation for a network with ~300,000 buses/lines - and that is in single threaded, blocking mode. The algorithm is close to being embarrassingly parallel

Its true that we have a connected component based on networkx in the topology. However, inside the power flow, we use scipy adjancy matrix search to check for disconnected components:

pandapower/pandapower/auxiliary.py

Lines 404 to 432 in 1e7842b

	def _check_connectivity(ppc):
	"""
	Checks if the ppc contains isolated buses. If yes this isolated buses are set out of service
	:param ppc: pypower case file
	:return:
	"""
	br_status = ppc['branch'][:, BR_STATUS] == True
	nobranch = ppc['branch'][br_status, :].shape[0]
	nobus = ppc['bus'].shape[0]
	bus_from = ppc['branch'][br_status, F_BUS].real.astype(int)
	bus_to = ppc['branch'][br_status, T_BUS].real.astype(int)
	slacks = ppc['bus'][ppc['bus'][:, BUS_TYPE] == 3, BUS_I]
	# we create a "virtual" bus thats connected to all slack nodes and start the connectivity
	# search at this bus
	bus_from = np.hstack([bus_from, slacks])
	bus_to = np.hstack([bus_to, np.ones(len(slacks)) * nobus])
	adj_matrix = sp.sparse.coo_matrix((np.ones(nobranch + len(slacks)),
	(bus_from, bus_to)),
	shape=(nobus + 1, nobus + 1))
	reachable = sp.sparse.csgraph.breadth_first_order(adj_matrix, nobus, False, False)
	# TODO: the former impl. excluded ppc buses that are already oos, but is this necessary ?
	# if so: bus_not_reachable = np.hstack([ppc['bus'][:, BUS_TYPE] != 4, np.array([False])])
	bus_not_reachable = np.ones(ppc["bus"].shape[0] + 1, dtype=bool)
	bus_not_reachable[reachable] = False
	isolated_nodes, pus, qus, ppc = _set_isolated_nodes_out_of_service(ppc, bus_not_reachable)
	return isolated_nodes, pus, qus

Since scipy implements this search in C++ libraries internally, its also pretty fast compared to networkx. Can you compare this regarding performance as well?

Short Circuit Analysis
Since graph edges in GraphBLAS can be complex numbers - this might be a perfect fit for circuit analysis/simplifications. The complex number of an edge can represent its impedance.

With a matrix based solution you can compute short-circuit currents for faults at all buses in parallel. I doubt that doing a graph search for each bus will outperform a matrix based approach to be honest. Also it will only work in a radial network and not in a meshed one. So I doubt this a good fit for graph based analysis in general.

[rbolgaryn]

Hi @bergkvist @lthurner @FlorianShepherd

any updates?

[bergkvist]

Seems related (considering it depends on GraphBLAS/SuiteSparse): https://github.com/BDonnot/lightsim2grid