[HN Gopher] Vectorizing Graph Neural Networks (2020)
       ___________________________________________________________________
        
       Vectorizing Graph Neural Networks (2020)
        
       Author : brilee
       Score  : 64 points
       Date   : 2023-07-03 13:58 UTC (9 hours ago)
        
 (HTM) web link (www.moderndescartes.com)
 (TXT) w3m dump (www.moderndescartes.com)
        
       | VHRanger wrote:
       | Yes, people working on graph based ML realize quickly that the
       | underlying data structures most originally academic libraries
       | (networkX, PyG, etc.) use are bad.
       | 
       | I wrote about this before [1] and based a node embedding library
       | around the concept [2].
       | 
       | The NetworkX style graphs are laid out as a bunch of items in a
       | heap with pointers to each other. That works at extreme scales,
       | because everything is on a cluster's RAM and you don't mind
       | paying the latency costs of fetch operations. But it makes little
       | sense for graphs with < 5B nodes to be honest.
       | 
       | Here's the dream (remains to be implemented by someone):
       | 
       | Laying out the graph as a CSR sparse matrix makes way more sense
       | because of data locality. You have an array for edges per node,
       | an index pointer array, and then one matrix with a row per edge
       | for edge data, and one matrix with a row per node for node data.
       | Ideally you code the entire thing with apache arrow memory to
       | ease access to other libraries/languages/
       | 
       | At larger scales, you could just leave the CSR array data on NVMe
       | drives, and you'd still operate at 500mb/s random query
       | throughput with hand coded access, ~150mb/s with mmap.
       | 
       | [1] https://www.singlelunch.com/2019/08/01/700x-faster-
       | node2vec-...
       | 
       | [2] https://github.com/VHRanger/nodevectors
        
         | WinLychee wrote:
         | Have seen this coded in practice, holding the entire graph in
         | memory (millions of vertices, billions of edges). It was pretty
         | darn fast.
         | 
         | A question I have wrt memory access for CSR: is the access
         | pattern suboptimal still? While there is less pointer chasing,
         | I believe you are not guaranteed for the edge data of adjacent
         | nodes to be adjacent in memory, thus there is still potential
         | for many cache misses.
         | 
         | Another open question is whether you can further compress the
         | CSR representation. For float-based edge data I think
         | quantization works well, and I believe you can further compress
         | the ROW/COL indices (delta encoding for the former).
         | Compression potentially helps here because you can fit more in
         | cache and can shove more edges into the CPU.
        
           | pgera wrote:
           | > I believe you are not guaranteed for the edge data of
           | adjacent nodes to be adjacent in memory
           | 
           | The edge data of a particular node is contiguous, but yes,
           | the edge data of a collection of nodes is not contiguous. You
           | can reorder (permute) the graph for some metric as a
           | preprocessing step so that you get better locality for your
           | average access pattern. This only works for static graphs
           | though.
           | 
           | > For float-based edge data I think quantization works well,
           | and I believe you can further compress the ROW/COL indices
           | 
           | Yes, index compression is pretty well studied and understood.
           | The challenge here is mostly good compression ratio and high
           | decompression performance. There are a couple of works that
           | I'm aware of that do this for gpus. This repo by Mo Sha et
           | al. (https://github.com/desert0616/GCGT) is pretty good, and
           | I also did some work in this space
           | (https://github.com/pgera/efg).
        
             | WinLychee wrote:
             | Awesome, thanks! Hacking on something in this space atm ;D
        
             | WinLychee wrote:
             | Oh one more question (checked out your repo): why the usage
             | of GPUs here vs CPUs? The possibility of more parallelism
             | when traversing the graph versus CPU?
        
         | Epa095 wrote:
         | You might be interested in duckdb-pgq[1], working on
         | implementing graph queries support in duckdb. There are some
         | papers online about it as well if you are interested.
         | 
         | 1: https://github.com/cwida/duckdb-pgq
        
         | bootsmann wrote:
         | PyG supports sparse adjacency matrices actually, but I remember
         | it being a pain to get right the last time I tried it.
        
           | fock wrote:
           | isn't it the default? At least I have the feeling it was in
           | pre-PyG-days.
        
         | anonymousDan wrote:
         | Does the design differ for training vs inference/prediction?
        
           | VHRanger wrote:
           | Depends on the model application?
           | 
           | If you have to carry around the graph for inference, then you
           | want it compact.
           | 
           | If you just fold the graph into some model, then it doesnt
           | really matter by inference time
        
       ___________________________________________________________________
       (page generated 2023-07-03 23:01 UTC)