静5青年讲座 | Improved Streaming Algorithms for Subgraph Counting

Subgraph counting in large graphs is a fundamental problem in computer science. Given an undirected graph G and a small pattern graph H (such as a triangle or a four-cycle), the goal is to count the number of (not necessarily induced) subgraphs of G that are isomorphic to H. These small pattern graphs, often referred to as motifs, play a crucial role in understanding the structural properties of complex networks. In this talk, I will present two multi-pass streaming algorithms for approximately counting subgraphs in the graph stream model, where the input graph G arrives as a stream of edges. The first algorithm approximates the number of occurrences of an arbitrary fixed subgraph H, while the second focuses on the special case of four-cycles. Both algorithms improve upon a sequence of prior results.

彭攀，中国科学技术大学计算机学院特任教授，入选国家级青年人才计划。曾获中国科学院软件研究所博士学位。曾于中国科学院软件所助理研究员，曾于德国多特蒙德工业大学、奥地利维也纳大学做博士后，曾担任英国谢菲尔德大学终身制讲师（助理教授），曾在美国加州大学伯克利分校 Simons 计算理论研究院担任长期访问科学家。主要研究图算法、大数据算法及其在机器学习、数据挖掘等领域的应用。在国际会议及期刊（包括STOC、SODA、SICOMP等）上发表高水平论文50余篇。