I think having graph compression would make sense when the amount of bandwidth saved for bandwidth bound program out-weigh the cost of spending extra compute capabilities to compress or decompress the graph. In other words, the saved memory bandwidth enables processors to do more compute because they are not limited by the memory bandwidth any more.

@gohan2021 I agree with this! I'm not sure how to reason about computing that threshold, though – are there any widely used heuristics?

Agreed with the above, that's also what the plots two slides ahead show, where graph compression helps when 40 cores are available but not when there's only 1 core. I think computing the threshold probably just comes down to some trial-and-error, as long as you're bandwidth-bound.

Is it possible to do aggregate data analytics over the graph but instead return an approximate answer with an error guarantee and reduce the cost by a significant amount?

In the Saxpy part of assignment 1 I said: If bandwidth is already saturated by a single thread, [one] thing to try to improve the performance of the program might be to compress the data so that more values can travel to and from memory at once This was marked as incorrect ("There isn't really a way to improve performance of saxpy.")

What's the difference here?

Graph operations are bandwidth bound because for each iteration there usually isn't too much work (arithmetic) being done for that given node and its edges, but the graph does have to load lots of nodes and edges from memory almost at random across the entire graph