jeanfeydy
commented
2 years ago Hi @Jostarndt,
Thanks for your kind words :-)
To answer your questions, out-of-the-box, yes, KeOps computes all pair-wise values for filter-values F(x[i], y[j]). This default behavior has quadratic complexity O(#i * #j) but an extremely good “constant” as long as F is not too complex - as a rule of thumb, less than 50-100 arithmetic operations.
In practice, this means that the default “bruteforce” mode of KeOps has two main use cases:
- Performing computations on (batches of) relatively small “point clouds”. If
#iand#jare smaller than ~10k, bruteforce computations may surprisingly be faster than sparse ones, even for very “local” operators. GPUs really aren’t optimized for sparse computations. - Implementing message-passing layers that are global with long-range interactions - instead of being “super-sparse” with a narrow perceptive field. In my opinion, this is the main contribution of KeOps to the field of geometric deep learning: we don’t need to restrict ourselves to layers where points only communicate with 64 neighbors - out of thousands of points.
Going further, KeOps also supports block-wise sparsity masks: it is actually possible to “skip” unnecessary computations using a “coarse” description of your connectivity structure. This is especially useful if you manipulate “graphs” with more than 10k nodes.
With respect to your question about max(), it is fully supported - although not yet differentiable I think? A work-around is discussed here. LogSumExps (fully differentiable) are usually a better option anyway. Is there anything else you would like to know?
With respect to code examples:
- Indeed, I forgot to turn some of the benchmarks of our NeurIPS papers into clean tutorials… I’m not on my laptop right now, but I will upload them somewhere tonight: even if they are not super clean, this will be better than nothing.
- On the other hand, I have published several papers on geometric deep learning with KeOps, and they may provide you with some inspiration. The most interesting piece of code too look at is probably the file geometry_processing.py in the dMaSIF repository by @FreyrS in our CVPR and MLDD papers on protein docking.
Does this answer your questions? Please let me know if you would like to know anything :-)
Best regards, Jean
Hey there, first of all: thank you very much for your amazing work, i am super impressed by and happy about KeOps. On your homepages section I stumbled upon message passing layers as a possible application, and am not sure if I understood everything correctly. Unfortunately there is no tutorial on this topic given, so I thought just asking here might be an option - sorry if this should have been clear by reading your NeurIPS paper, but I have some difficulties. So maybe a longer example including code could be helpful to me and further enlarge your audience.
One of my main questions concerns the concrete meaning of semi-symbolic in the context of message passing. If I follow your example of message passing, and update some aggregation
a_iby a sum of filter over neighbors by multiplying a sparse adjacency matrixAwith a filter-vectorF, which might be computationally expensive. Does KeOps actually compute also the plenty unnecessary (due to the sparsity ofA) entries in the filter-vectorF? Or does "semi-symbolic" mean that the sparsity prevents the unnecessary computations? Or how would you suggest this summation to be done?My next question regarding the same would be: what If i do not want a summation but some nonlinear aggregation, such as max - is there any suggested implementation for this with KeOps I havent found yet?
And is there any way to access code of your comparison of KeOps and pytorch-geometric regarding this?
I would extremely appreciate it to further understand KeOps as it seems to deliver exactly what I am looking for, thank you very much for the so far incredible documentation and programming you did!