Connectivity-Aware Link Analysis for Skewed Graphs

Link analysis is a fundamental task for graph analytics, as it enables the identification of important nodes and patterns in the graph. Link analysis algorithms typically require traversing the graph and accessing the links of each node. However, for graphs with a skewed degree distribution, the computing efficiency of link analysis is severely constrained due to irregular connectivity, which results in randomized memory accesses and high cache miss ratio. In this paper, we conduct a thorough investigation into skewed graphs' structural characteristics, focusing on their interaction with the computational patterns observed in link analysis algorithms and the underlying hardware architecture. Generalizing the understanding, we develop a novel framework named Mixen. Mixen applies a lightweight filtering procedure to enhance graph locality and reschedule computations. Different graph components are selectively processed under distinctive paradigms. Thereby, Mixen allows for efficient graph traversal and performance optimization. We evaluate Mixen on modern multicore systems, comparing its performance to state-of-the-art frameworks across various graphs and algorithms. The results indicate that Mixen significantly outperforms its counterparts. Over the best-performing alternative, Mixen achieves a 3.42x speedup in execution time. Furthermore, we explore the design space of Mixen, examining its trade-offs and the correlation with cache-memory dynamics.