Memory-Aware Framework for Efficient Second-Order Random Walk on Large Graphs
Memory-Aware Framework for Efficient Second-Order Random Walk on Large Graphs
复制标题
DOI：
10.1145/3318464.3380562
复制
发表时间：
2020-05
期刊：
影响因子：
--
通讯作者：
Yingxia Shao;Shiyu Huang;Xupeng Miao;B. Cui;Lei Chen
中科院分区：
文献类型：
--
作者：
Yingxia Shao;Shiyu Huang;Xupeng Miao;B. Cui;Lei Chen
二阶随机游走是图分析中的一种重要技术。许多应用程序使用它来捕获图形中的高阶模式，从而提高模型的准确性。然而，这种技术的内存爆炸问题阻碍了它分析大型图表。当处理像Twitter这样的十亿边图时，二阶随机游走的现有解决方案(例如，别名法)可能会占用1796TB的内存。如此高的内存开销来自不知道内存的跨图节点采样策略。为了更好地研究二阶随机游走背景下各种节点采样方法的效率，设计了代价模型，提出了一种遵循接受-拒绝范式的节点采样方法，以更好地平衡内存和时间开销。此外，为了保证二阶随机游走在任意存储预算内的效率，我们在代价模型的基础上提出了一种内存感知框架。该框架应用基于代价的优化器在内存预算内为图中的每个节点分配理想的节点采样方法，同时最小化时间开销。最后，我们为用户提供了通用的编程接口，以便用户可以轻松地受益于内存感知框架。实验表明，我们的内存感知框架在内存方面是健壮的，并且能够通过减少90%的内存开销来获得相当高的效率。
Second-order random walk is an important technique for graph analysis. Many applications use it to capture higher-order patterns in the graph, thus improving the model accuracy. However, the memory explosion problem of this technique hinders it from analyzing large graphs. When processing a billion-edge graph like Twitter, existing solutions (e.g., alias method) of the second-order random walk may take up 1796TB memory. Such high memory overhead comes from the memory-unaware strategies for node sampling across the graph. In this paper, to clearly study the efficiency of various node sampling methods in the context of second-order random walk, we design a cost model, and then propose a new node sampling method following the acceptance-rejection paradigm to achieve a better balance between memory and time cost. Further, to guarantee the efficiency of the second-order random walk within arbitrary memory budgets, we propose a memory-aware framework on the basis of the cost model. The framework applies a cost-based optimizer to assign desirable node sampling method for each node in the graph within a memory budget while minimizing the time cost. Finally, we provide general programming interfaces for users to benefit from the memory-aware framework easily. The empirical studies demonstrate that our memory-aware framework is robust with respect to memory and is able to achieve considerable efficiency by reducing 90% of the memory cost.