Distributed Graph analytics is being widely used in various domains for analyzing large real-world graphs. There have been numerous efforts to build distributed frameworks for graph analytics aimed at improving scalability. These frameworks enable the processing of huge graphs that do not fit in the memory of a single machine by imposing message-passing overhead among a cluster of multiple machines, underutilizing the available computing resources. To mitigate this, we present Expressway, a technique to identify important edges, i.e., Highways, that play a key role in delivering the results for their boundary vertices. Expressway first runs the queries using only Highways, reducing the number of edges that needed to be processed during the execution of a graph query significantly. Thus, it can be accomplished in each machine separately in the cluster, avoiding the message-passing overheads. Then Expressway takes the results from running the query on Highways and initializes the vertices to these values, enabling faster convergence of graph algorithms. Our experiments show applying Expressway on the state-of-the-art frameworks results in up to $4.08\times$ speedup over the single-query framework and up to $4.04\times$ speedup over the framework to run a batch of concurrent graph queries.

Simultaneous evaluating a batch of iterative graph queries on a distributed system enables amortization of high communication and computation costs across multiple queries. As demonstrated by our prior work on MultiLyra [BigData'19], batched graph query processing can deliver significant speedups and scale up to batch sizes of hundreds of queries.In this paper, we greatly expand the applicable scenarios for batching by developing BEAD, a system that supports Batching in the presence of Evolving Analytics Demands. First, BEAD allows the graph data set to evolve (grow) over time, more vertices (e.g., users) and edges (e.g., interactions) are added. In addition, as the graph data set evolves, BEAD also allows the user to add more queries of interests to the query batch to accommodate new user demands. The key to the superior efficiency offered by BEAD lies in a series of incremental evaluation techniques that leverage the results of prior request to "fast-foward" the evaluation of the current request.We performed experiments comparing batching in BEAD with batching in MultiLyra for multiple input graphs and algorithms. Experiments demonstrate that BEAD's batched evaluation of 256 queries, following graph changes that add up to 100K edges to a billion edge Twitter graph and also query changes of up to 32 new queries, outperforms MultiLyra's batched evaluation by factors of up to 26.16 × and 5.66 × respectively.

Having reliable and stable connectivity to the Internet dramatically depends on how Border Gateway Protocol (BGP) can avoid bad-behaviour events by detecting them on time. Despite a lot of efforts have gone into detecting BGP anomalies during the last decade, it is still a challenging issue due to emerging new abnormal behaviours both from the attackers and network misconfigurations. In this work, we propose a Neural Network classifier to detect the abnormal BGP events caused by worm attacks in the network. The results show that our method outperforms the previous work in both generality and accuracy.

Large scale iterative graph processing has become increasingly important due to its use in analyzing large realworld networks (e.g., internet topology, social networks). Due to their scalability, distributed systems are an attractive platform for graph processing. However, the irregular power-law degree distribution of such large graphs creates many challenges for efficiently managing iterative workloads on a distributed system. We observe that in current algorithms during each iteration an active vertex is processed exactly once. In this work we demonstrate that by processing less expensive low-degree vertices more frequently we can cause more expensive high-degree vertices to be processed less frequently leading to faster algorithm convergence. Our experiments demonstrate that both the number of iterations and total execution times are reduced significantly for multiple iterative graph algorithms (PageRank, NumPaths, SSSP) on billion vertex input graphs (Friendster and Twitter).

Graph analytics is being increasingly used for analyzing large scale networks representing entities and relationships in many domains. Various distributed graph processing frameworks have been developed to deliver scalable performance for evaluation of individual iterative graph queries. In practice though, we may need to evaluate many queries. In this paper we develop MultiLyra, a distributed framework that efficiently evaluates a batch of graph queries. To deliver high performance, this system is designed to amortize the communication and synchronization costs of distributed query evaluation across multiple queries. Our experiments with MultiLyra for four iterative algorithms on a cluster of four 32-core machines show the following. Basic batching technique for amortizing communication and synchronization costs yield maximum speedups ranging from 3.08× to 5.55× across different batch sizes, algorithms and input graphs. After employing optimizations that improve scalability of expensive phases and perform reuse across the distributed computation, the improved maximum speedups range from 7.35× to 11.86×. MultiLyra also delivers superior scalabilty than the Quegel batch processing system.