As new applications for graph algorithms emerge, there has
been a great deal of research interest in improving graph
processing. However, it is often difficult to understand how
these new contributions improve performance. Execution
time, the most commonly reported metric, distinguishes which
alternative is the fastest but does not give any insight as to
why. A new contribution may have an algorithmic innova-
tion that allows it to examine fewer graph edges. It could
also have an implementation optimization that reduces com-
munication. It could even have optimizations that allow it to
increase its memory bandwidth utilization. More interest-
ingly, a new innovation may simultaneously affect all three
of these factors (algorithmic work, communication volume,
and memory bandwidth utilization). We present the Graph
Algorithm Iron Law (GAIL) to quantify these tradeoffs to
help understand graph algorithm performance.