4 ms·
>You can also lay the graph array order out to minimize cache misses. This is something I've been looking into, but haven't implemented personally. The issue w
by pgera 3y ago
>You can also lay the graph array order out to minimize cache misses. This is something I've been looking into, but haven't implemented personally.
The issue with RCM is that it only works for undirected graphs, from what I remember. I'm less familiar with GNNs, but if you are trying to optimize for arbitrary BFS type traversals, an easy trick is to just do a few traversals from random sources and average the results. This can be used to reorder the graph and works pretty well in practice.
- VHRanger 3y agoRight, RCM assumes a symmetric matrix. Doing something like a single pass of 1d embedding algos like GGVec [1] (note: I wrote the algo, but it's effectively just the GLoVe algo for general graphs) or ProNE (if you have enough RAM) are also very cheap computationally [1] https://github.com/VHRanger/nodevectors https://github.com/VHRanger/nodevectors