There are a few things to note. First, graph algorithms are basically the same thing as sparse matrix algorithms, in that the sort of optimization techniques you use for one class carries over nicely to the other class. The second thing is that graph and sparse matrix algorithms are unavoidably heavy on indirect memory accesses. BFS in particular has the property that there's essentially no computation that you can use to hide the memory latency. Which means that GPUs in particular do a bad job on BFS, and that gives you ample room to post 10× speedups over state-of-the-art GPUs.
