论文标题
Subgraph2Vec：高度矢量化的树类式纸
SubGraph2Vec: Highly-Vectorized Tree-likeSubgraph Counting
论文作者
论文摘要
子图计数旨在计算给定网络g（v，e）中的模板t的发生。它是一个强大的图形分析工具，已经在不同域中找到了现实世界中的应用程序。已知缩放子图计数问题是内存界定的，并且具有指数复杂性在计算上具有挑战性。尽管可扩展的并行算法以几种图形问题（例如三角形计数和pagerank）而闻名，但这对于计数复杂的子图并不常见。在这里，我们应对这一挑战并研究相关的无环图或树。我们提出了一种新型的矢量化子图计数算法，称为subgraph2vec，以及共享内存和分布式实现：1）通过最大程度地减少邻居遍历来降低算法复杂性； 2）在线性代数内核上实现高度向量化的实现，以显着提高性能和硬件利用率。 3）Subgraph2Vec通过数量级和一个节点上的数量级和最高660倍提高了最先进的工作的整体性能。 4）在分布式模式下以分布式模式下的Subgraph2Vec可以将模板尺寸扩展到20，并保持良好的可扩展性。 5）启用CPU和GPU的可移植性。
Subgraph counting aims to count occurrences of a template T in a given network G(V, E). It is a powerful graph analysis tool and has found real-world applications in diverse domains. Scaling subgraph counting problems is known to be memory bounded and computationally challenging with exponential complexity. Although scalable parallel algorithms are known for several graph problems such as Triangle Counting and PageRank, this is not common for counting complex subgraphs. Here we address this challenge and study connected acyclic graphs or trees. We propose a novel vectorized subgraph counting algorithm, named Subgraph2Vec, as well as both shared memory and distributed implementations: 1) reducing algorithmic complexity by minimizing neighbor traversal; 2) achieving a highly-vectorized implementation upon linear algebra kernels to significantly improve performance and hardware utilization. 3) Subgraph2Vec improves the overall performance over the state-of-the-art work by orders of magnitude and up to 660x on a single node. 4) Subgraph2Vec in distributed mode can scale up the template size to 20 and maintain good strong scalability. 5) enabling portability to both CPU and GPU.
