AutoMine: harmonizing high-level abstraction and high performance for graph mining
AutoMine: harmonizing high-level abstraction and high performance for graph mining
复制标题
DOI：
10.1145/3341301.3359633
复制
发表时间：
2019-10
期刊：
影响因子：
--
通讯作者：
Daniel Mawhirter;Bo Wu
中科院分区：
文献类型：
--
作者：
Daniel Mawhirter;Bo Wu
旨在识别图的结构模式的图形挖掘算法通常比图表计算算法（例如广度首次搜索）更为复杂。研究人员已经实施了几个具有高级和灵活界面的系统，该系统可定制用于解决图形挖掘问题。但是，我们发现，对于三角计数，最简单的图形挖掘问题之一，这样的系统可能比直接算法的单线程实现速度要慢几倍。在本文中，我们揭示了最先进的图形挖掘系统严重效率低下的根本原因以及解决绩效问题的挑战。我们构建了Automine，这是一种单机系统，可为大型图形挖掘应用提供高级接口和高性能。汽车的新颖性来自1）子图模式的新表示和2）汇编技术，它们会自动生成有效的采矿代码，并从高级抽象中最大程度地减少内存消耗。我们对8个不同尺度的8个真实图表上的3个图挖掘系统进行了广泛的评估。我们的实验结果表明，汽车通常会产生多个数量级的性能，并且可以处理现有系统无法处理的非常大的图形。
Graph mining algorithms that aim at identifying structural patterns of graphs are typically more complex than graph computation algorithms such as breadth first search. Researchers have implemented several systems with high-level and flexible interfaces customized for tackling graph mining problems. However, we find that for triangle counting, one of the simplest graph mining problems, such systems can be several times slower than a single-threaded implementation of a straightforward algorithm. In this paper, we reveal the root causes of the severe inefficiencies of state-of-the-art graph mining systems and the challenges to address the performance problems. We build AutoMine, a single-machine system to provide both high-level interfaces and high performance for large-scale graph mining applications. The novelty of AutoMine comes from 1) a new representation of subgraph patterns and 2) compilation techniques that automatically generate efficient mining code with minimized memory consumption from a high-level abstraction. We have extensively evaluated AutoMine against 3 graph mining systems on 8 real-world graphs of different scales. Our experimental results show that AutoMine often produces several orders of magnitude better performance and can process very large graphs existing systems cannot handle.