论文标题
使用代数指纹在大型时间图中查找路径图案
Finding path motifs in large temporal graphs using algebraic fingerprints
论文作者
论文摘要
我们研究了顶点颞图中的模式检测问题家族。特别是，给定一个顶点色的时间图和多种颜色作为查询，我们在图中搜索包含查询中指定的颜色的时间路径。这些类型的问题有多种应用，例如，在推荐游客或在金融交易网络中发现异常行为时。对于我们考虑的模式检测问题的家庭，我们建立了复杂性结果并设计了基于受约束的多线性筛分的代数算法框架。我们证明，我们的解决方案尺度可用于巨大的图形，对于具有五种颜色的多层查询，最多可达10亿个颜色，但对于具有10种颜色的多层查询，尽管存在NP-HARD。我们的实施公开可用，具有实用的边缘线性可扩展性，并得到了高度优化。例如，在具有超过600万个边缘和具有十种颜色的多式查询的现实图形数据集中，我们可以在不到八分钟的haswell台式机上提取最佳解决方案。
We study a family of pattern-detection problems in vertex-colored temporal graphs. In particular, given a vertex-colored temporal graph and a multiset of colors as a query, we search for temporal paths in the graph that contain the colors specified in the query. These types of problems have several applications, for example in recommending tours for tourists or detecting abnormal behavior in a network of financial transactions. For the family of pattern-detection problems we consider, we establish complexity results and design an algebraic-algorithmic framework based on constrained multilinear sieving. We demonstrate that our solution scales to massive graphs with up to a billion edges for a multiset query with five colors and up to hundred million edges for a multiset query with ten colors, despite the problems being NP-hard. Our implementation, which is publicly available, exhibits practical edge-linear scalability and is highly optimized. For instance, in a real-world graph dataset with more than six million edges and a multiset query with ten colors, we can extract an optimum solution in less than eight minutes on a Haswell desktop with four cores.
