NetworkIt and GraphAr

[adsharma]

networkit is a popular open source library with a large number of interesting graph algorithms.

For billion scale graphs, the library spends more time loading the graph into memory vs actually running the algorithm. It would be interesting to implement a variant of the library that takes GraphAr as input.

Some of these ideas have already been implemented. Details in networkit/networkit#1335.

What remains:

• Fix memory management in CoarseningGraphView
• Figure out how to maintain the Graph (immutable, arrow based) and GraphW (mutable, std::vector based) graph implementations.

This architecture is not fully aligned with the goals of the networkit project. But it's closer to the concepts in this library.

The proposed interface:

            graph = nk.graph.Graph.fromCSR(
                n_nodes, directed, indices_arrow, indptr_arrow
            )

should be compatible with GraphAr. If not, please let me know what changes you need.

[yangxk1]

@adsharma Hi, this is a very good idea! I will also read networkit in detail. For interface, my initial idea is still to use graphInfo (metadata of graph). This is because vertex/edge/propery may be stored in different paths in GAR, and there is no need to read all columns. We can refer to chunk_reader.h, mid_level_reader_example

[adsharma]

@yangxk1 Thanks for the pointer. Even though networkit is written in C++, 99% of the usage is via the python API.

I noticed that GraphAr has a pyspark interface using poetry. Any plans for a general python wrapper (independent of pyspark) around the C++ API? uv is becoming very popular in the community. Love to see it supported.

While it's possible to integrate with my fork of networkit at the C++ level, the biggest bang for the buck is via:

import graphar
import networkit as nk

metadata = graphar.GraphInfo.Load(path)
graph = nk.graph.Graph.fromGraphAr(metadata)  # implementation could leverage fromCSR()

[yangxk1]

GAR has a python cli, it uses pybind11 to bind C++. It is still under development.

[adsharma]

I meant something similar to GAR cli, but allows people to use uv + "import graphar" to access functionality.

Proof of concept here. Happy to a send a PR.

[yangxk1]

Sorry for the delayed reply! Your idea is really cool. Since both this and the GAR CLI are written in Python, use pybind11, and are user-facing, would it make sense to merge them? I will be looking forward to this PR. However I am not good at python project, I hope @SemyonSinchenko @lixueclaire can give some suggestions

[adsharma]

Yes, having shared cmake makes sense. I'm a bit tied up this week. Will get something out next week.

[yangxk1]

Proof of concept here. Happy to a send a PR.

Hi @adsharma , We hope to build python SDK for schema yaml as soon as possible. I noticed that you have already done some work. Maybe you can start a preliminary PR, and then we will improve it based on your work.