Signal/Collect: Graph Algorithms for the (Semantic) Web
📜 Abstract
The Semantic Web graph is growing at an incredible pace, enabling opportunities to discover new knowledge by interlinking and analyzing previously unconnected data sets. This confronts researchers with a conundrum: Whilst the data is available the programming models that facilitate scalability and the infrastructure to run various algorithms on the graph are missing. Some use MapReduce – a good solution for many problems. However, even some simple iterative graph algorithms do not map nicely to that programming model requiring programmers to shoehorn their problem to the MapReduce model. This paper presents the Signal/Collect programming model for synchronous and asynchronous graph algorithms. We demonstrate that this abstraction can capture the essence of many algorithms on graphs in a concise and elegant way by giving Signal/Collect adaptations of various relevant algorithms. Furthermore, we built and evaluated a prototype Signal/Collect framework that executes algorithms in our programming model. We empirically show that this prototype transparently scales and that guiding computations by scoring as well as asynchronousity can greatly improve the convergence of some example algorithms. We released the framework under the Apache License 2.0 (at http://www.ifi.uzh.ch/ddis/research/sc).
✨ Summary
Summary
The paper introduces Signal/Collect, a vertex-and-edge programming model for iterative computation over typed graphs. Vertices maintain state and collect incoming signals; edges compute and transmit signals from source vertices to targets. The model supports synchronous bulk-synchronous execution, score-guided execution, asynchronous execution, custom schedulers, multiple vertex and edge types, weighted edges, conditional computation phases, and aggregation.
The authors demonstrate the model with single-source shortest path, RDFS subclass inference, vertex coloring, PageRank, and loopy belief propagation. Their prototype, implemented in Scala, parallelizes computations across worker threads on a shared-memory machine and can initialize graph structures from SPARQL queries. Experiments report near-linear speedup for one large shortest-path workload, substantial reductions in PageRank work through score-guided execution on some graphs, and cases where eager asynchronous execution converges while synchronous execution does not. The evaluation is limited because the prototype was initially single-machine and shared-memory, and because only a small set of algorithms and graph structures was tested. (code.garrettmills.dev)
Subsequent influence
The work was followed by a substantially expanded Signal/Collect publication, which generalized the application scope and reported a distributed implementation capable of processing a graph with more than 1.4 billion vertices and 6.6 billion edges on eight machines. (journals.sagepub.com) The project’s later documentation continues to describe distributed execution, score-guided signaling and collecting, convergence detection, and asynchronous processing as core features. (uzh.github.io) The programming model also influenced subsequent graph-processing software, including the Clojure/ClojureScript fabric infrastructure, which explicitly describes itself as Signal/Collect-inspired. (github.com) Later graph-processing and temporal-graph publications cite the paper as part of the development of vertex-centric and asynchronous graph-processing systems. (doi.org)