Yue Pang's "IFCA: Index-Free Community-Aware Reachability Processing Over Large Dynamic Graphs" was accepted by ICDE 2023.

The reachability query, which checks whether a path exists from a source vertex to a destination vertex on a directed graph, is a fundamental graph query operator. State-of-the-art index-based reachability processing frameworks, which precomputes synopses of partial or complete reachability information offline to speed up online queries, can efficiently handle static graphs. However, the recent advent of highly dynamic graph data renders them increasingly ineffectual. For static indexes, significant overhead occurs when reconstructing them as the graph evolves; for the indexes that support dynamic updates, the maintenance cost is still high when updates are frequent.

To address these challenges, we propose an index-free, community-aware (IFCA) reachability processing framework inspired by efficient Personalized PageRank approximation algorithms, which identifies community structures on-the-fly to accelerate query processing. On top of it, we devise a community contraction technique to bridge the gap between vertices in distinct communities, and a cost-based strategy selection procedure to efficiently handle the resulting reduced graph. We conduct experiments with realistic query workloads over large-scale real dynamic graphs, showing our approach's superior efficiency compared with index-based and index-free state-of-the-art methods.