1. A method implemented by data processing apparatus, the method comprising: receiving, during a first superstep, streaming graph input that comprises continuous input of first graph updates for updating the state of an existing graph, the existing graph comprising a plurality of vertices and edges, and each first graph update specifying a vertex and a message; scheduling, during the first superstep, the first graph updates for processing during a second superstep that is subsequent to the first superstep; providing, during the first superstep, the first graph updates as input to a graph computation for the existing graph; determining that the graph computation has completed processing for the first superstep, and in response: initiating the second superstep; and processing, during the second superstep, each first graph update scheduled for processing during the second superstep; and providing, during the second superstep, graph output based at least in part on the first graph updates.