2014/05/07 by Abdul Quamar, Quamar, Abdul, Amol Deshpande +3
Computer Science · #Advanced Graph Neural Networks #Cloud Computing and Resource Management #Databases (cs.DB) #FOS: Computer and information sciences #Graph Theory and Algorithms #Social and Information Networks (cs.SI)
paper · pdf · doi:10.48550/arxiv.1405.1499
openalex publication_date 2014/05/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
There is an increasing interest in executing complex analyses over large graphs, many of which require processing a large number of multi-hop neighborhoods or subgraphs. Examples include ego network analysis, motif counting, personalized recommendations, and others. These tasks are not well served by existing vertex-centric graph processing frameworks, where user programs are only able to directly access the state of a single vertex. This paper introduces NSCALE, a novel end-to-end graph processing framework that enables the distributed execution of complex subgraph-centric analytics over large-scale graphs in the cloud. NSCALE enables users to write programs at the level of subgraphs rather than at the level of vertices. Unlike most previous graph processing frameworks, which apply the user program to the entire graph, NSCALE allows users to declaratively specify subgraphs of interest. Our framework includes a novel graph extraction and packing (GEP) module that utilizes a cost-based optimizer to partition and pack the subgraphs of interest into memory on as few machines as possible. The distributed execution engine then takes over and runs the user program in parallel, while respecting the scope of the various subgraphs. Our experimental results show orders-of-magnitude improvements in performance and drastic reductions in the cost of analytics compared to vertex-centric approaches.