Efficient Reachability Query in Hypergraphs

Computing the reachability between two vertices is a fundamental problem in graph analysis. However, existing studies mainly focus on general graphs, where an edge connects exactly two vertices. Group-based connections, such as a group of authors collaborating on the same paper, naturally exist in the real world and can be modelled as hypergraphs. It is critical to leverage group-based information to better characterise the relationships between vertices in hypergraphs. To fill the gap, we propose a novel model called threshold-reachability, by considering the overlap of adjacent hyperedges in paths. Specifically, given a hypergraph H = (V, E), two vertices 𝑢, 𝑣 ∈ V and a positive integer 𝑘, we say that 𝑢 can reach 𝑣 with threshold 𝑘, if there exists a hyperpath 𝑃(𝑒_𝑢, 𝑒_𝑣) between hyperedges 𝑒_𝑢 and 𝑒_𝑣, formed by a sequence of hyperedges such that 𝑖) 𝑢 ∈ 𝑒_𝑢, 𝑣 ∈ 𝑒_𝑣, and 𝑖𝑖) any two adjacent hyperedges in 𝑃(𝑒_𝑢, 𝑒_𝑣) share at least 𝑘 common vertices. To be more generalised, we investigate the max-reachability problem in this paper, which aims to compute the largest threshold for which the given vertices are reachable. To solve this problem efficiently, we extend the 2-hop labelling framework and develop the HL-index that follows a novel vertex-to-hyperedge index paradigm designed. We propose an effective method for constructing a minimal HL-index with several optimisation techniques to support the index construction. We also design a lightweight neighbour-index to avoid repeatedly exploring neighbour relationships in hypergraph and hence support efficient hypergraph traversal. Finally, comprehensive experiments on 16 real-world datasets are conducted to demonstrate the efficiency and scalability of our proposed techniques.