Internal table/database type to use to represent network graph data

[makkus]

Recently I've been thinking about how to best represent network data within kiara. Up until now, we've been using either one (edge information) or two (edge & node information) Apache Arrow tables so far, which works ok, but is a bit clunky to work with because the code we'll write will always be conditional, testing whether node information is available or not.

This most likely won't go away entirely, but I've been thinking that it might be a better idea to use a sqlite database instead of 2 Arrow tables for the purpose of graph data.

Advantages:

• data is always represented/serialized into a single file (sqlite db file)
• we can have one or two tables created within that sqlite database, depending on whether we have node information or not
• query patterns when working with network graphs usually suit row-based data layout better than a columnar layout (like Arrow has), so I imagine overall performance for network-related modules would be better (could be even much better -- but that would have to be verified)
• sqlite query engine is probably more powerful than anything available for Apache Arrow at the moment

Disadvantages:

• Apache Arrow files and bytestreams would probably be a bit better for interoperability
• conversion of Apache Arrow tables to Pandas Dataframes is easier/less expensive than sqlite tables

One thing to mention: it should be relatively simple to create modules that can convert from sqlite to Arrow Tables and vice versa. This is something I wanted to implement anyway, independently of this issue.

[makkus]

I've done a little bit more digging, and I like the idea of using sqlite database to store all data related to a network graph more and more.

There is a simple Python project that already does a bit of the groundwork: https://github.com/dpapathanasiou/simple-graph/tree/main/python

And since @yaslena mentioned that she is unsure which of the Python network libraries to use by default, it might be a good idea to use sqlite to store the data in a format that is easy to query in the 'traditional' way (using sql), but provide 'adapters' that create Python objects for any of the relevant graphing libraries (networkx, python-igraph, networkit, ...) when needed.

This works because all data items in kiara are immutable/read-only, and the advantage would be that we don't have to decide on any one of those networking libaries within our modules. We would just use the one that is best suited for the job at hand, and once the work is finished we'd store the result (if it is a new/changed network graph) using a sqlite db again.

[makkus]

So, I've refactored the data type (to be released in the next version), and it works like this:

• backed by an sqlite database, with 2 tables: 'nodes', 'edges'
• nodes table:
  • 2 mandatory columns:
    • _id (int): generated index, starting from 0
    • _label (varchar): the label of each node, if not provided through other means, the value will be the stringified value of the _id column
• edges table:
  • 2 mandatory columns:
    • _source (int): the node id of the starting point of the edge
    • _target (int): the node id of the end point of the edge
• both tables can have other, arbitrary columns containing node or edge properties, the only rule is that they can't start with an _ (columns starting with that indicate internally required and in some cases generated data)
• the network_data type only contains node and edge information, which can be interpreted as graph in different ways: unidrected, directed, multi, ... In some cases certain interpretations do not make sense, even though kiara would allow the user/developer to do that.
• module developers will in most cases interact with an instance of the NetworkData Python class, which contains convenience methods to 'load' a Python graph object from the underlying database (check the as_xxx_graph methods for what type of class can be loaded -- at the moment it's networkx and rustworkx graph classes, but in the future we can support other libraries)
• it's up to the developer to do that as efficiently as possible (for example, don't request node/edge attributes if they are not required for what you try to do, as they'd only occupy memory for no reason), the preference here is (depending on what is required:
  • use sql directly
  • use a rustworkx graph object
  • use a networkx graph object