Here are a few references that solve problems on very large graphs:

[1] implements work-efficient parallel algorithms for a list of fundamental graph problems. They report times on a O(200B) edge graph on a single multicore.

[2] reports distributed running times for BFS, connectivity, PageRank, and SSSP on a large number of distributed hosts. The times are usually slower than the single-machine times, despite using two orders of magnitude more threads.

[3] Reports connectivity times on a truly large graph that is not publicly available (several trillions of edges).

My feeling is that unless you are at FAANG or a big national lab, the largest graphs that will show up in practice (today) are on the order of billions of edges, and can be solved quickly using single-machine multicores.

[1] https://arxiv.org/abs/1805.05208

[2] https://www.cs.utexas.edu/~roshan/Gluon.pdf

[3] https://arxiv.org/abs/1807.10727

Yes, all these are valid cases. Hence the second part of my question:

Given this, exactly what advantage does a FPGA give? Who is processing ~100 billion edge graphs so many times that you are going to save on power? And is there actually any power savings over a single core anyway?

> what advantage does a FPGA give

basically time and power. FPGAs will most likely be both faster and more power efficient than GPUs and CPUs, the memory point isn't quite relevant, you can have an FPGA board that talks to 32 GB of ram, or an HBM chip with as much memory density and memory bandwidth as a 1080 TI GPU.

> Given this, exactly what advantage does a FPGA give?

Not spending an hour on performing the calculation, I’d guess. An hour for PageRank is probably acceptable, but there are applications where waiting an hour for a result isn’t viable.