In this talk we will characterize the challenges of distributed computation on natural graphs in the context of existing graph-parallel abstractions. I will then introduce the PowerGraph abstraction which exploits the internal structure of graph programs to address these challenges. Leveraging the PowerGraph abstraction, I will then introduce a new approach to distributed graph placement and representation that exploits the structure of power-law graphs. I will discuss the performance of these new techniques on large-scale real-world problems demonstrating order of magnitude gains. Finally, I will present ongoing work on expressing graph computation within classical database systems.