一句话：提出 VExpand 算子与完整引擎 VertexSurge，在十亿边图上高效执行变长图模式匹配。
变长图模式匹配（VLGPM）需要判断两个匹配顶点之间是否存在可变数目的连接边，对社交网络、银行转账等动态复杂网络分析至关重要，但现有图数据库主要针对单跳子图匹配优化，难以在大图上高效支持 VLGPM。本文提出 VertexSurge，其核心是面向微架构优化的变长扩展（VExpand）算子，高效计算两个顶点集合间的可达性矩阵，从而应对变长匹配带来的顶点数量激增；同时结合多集合交集进行模式匹配、基于规则的查询规划以及磁盘卸载，实现完整的 VLGPM 引擎。在真实图数据集和代表性模式上的实验表明，VertexSurge 在 VLGPM 上显著优于现有系统，能够应对大规模图模式匹配挑战。
Variable-Length Graph Pattern Matching (VLGPM) is a critical functionality in graph databases, pivotal for identifying patterns where the number of connecting edges between two matched vertices is variable. This function plays a vital role in analyzing complex and dynamic networks such as social networks or bank transfers networks, where relationships can vary extensively in both length and structure. However, despite its importance, current graph databases, optimized primarily for single-hop subgraph matching, struggle with VLGPM over large graphs. To bridge this gap between essential user requirements and the lack of efficient support in existing systems, we introduce VertexSurge. Central to VertexSurge is an innovative variable-length expand (VExpand) operator, which incorporates several microarchitecture-friendly optimizations to efficiently compute the reachability matrix between two sets of vertices. These optimizations enable VertexSurge to handle the surge of vertex count due to variable length with high performance. Additionally, VertexSurge combines VExpand with effective multi-set intersection for pattern matching, ruled-based planning, and disk offloading for large datasets, to implement a full-fledged VLGPM engine. Our evaluations with real-world graph datasets and representative patterns demonstrate that VertexSurge significantly outperforms existing systems in VLGPM, validating its efficacy in handling large-scale graph pattern matching challenges.
@inproceedings{XieZLCJ024,
title = {VertexSurge: Variable Length Graph Pattern Match on Billion-edge Graphs},
author = {Weiyu Xie and MingXing Zhang and Xia Liao and Kang Chen and Jinlei Jiang and YongWei Wu},
booktitle = {ASPLOS},
year = {2024},
doi = {10.1145/3622781.3674173}
}