  Real-world graphs are constantly evolving, which demands updates of the
previous analysis results to accommodate graph changes. By using the memoized
previous computation state, incremental graph computation can reduce
unnecessary recomputation. However, a small change may propagate over the whole
graph and lead to large-scale iterative computations. To address this problem,
we propose Layph, a two-layered graph framework. The upper layer is a skeleton
of the graph, which is much smaller than the original graph, and the lower
layer has some disjointed subgraphs. Layph limits costly global iterative
computations on the original graph to the small graph skeleton and a few
subgraphs updated with the input graph changes. In this way, many vertices and
edges are not involved in iterative computations, significantly reducing the
communication overhead and improving incremental graph processing performance.
Our experimental results show that Layph outperforms current state-of-the-art
incremental graph systems by 9.08X on average (up to 36.66X) in response time.
