Fast Content-Aware Influence Maximization Query Answering by Labeling Index

In this paper, we study the Content-Aware Influence Maximization (CAIM) query-answering problem. Given the abundant research on the IM problem, CAIM is one of its most practical variants. In the CAIM problem, network edge probabilities change according to the content (topic) of the item being spread. The query-answering task, therefore, requires efficiently finding a set of seed nodes that maximizes the item's influence spread. Although SOTA IM methods can achieve nearlinear time complexity, repeatedly executing them for each query is still prohibitively expensive when the number of queries is large. In this paper, we propose a novel labeling-based index approach. To the best of our knowledge, this is the first index framework for dealing with the CAIM query-answering task. By constructing a space-efficient data structure for the index, we pre-store content-aware reachability information. A Reachability Table Estimation (RTE) method is developed, which can compute the lower bound of the reachability probability for any pair of nodes and any topic, with a time complexity dependent only on the number of topics. In addition, we design a scalable pruning mechanism (PRTE) to further speed up the estimation, as well as a lazy-forward-based greedy algorithm for seed node selection. Extensive experiments are conducted on real-world datasets. The results demonstrate that the proposed index-based methods can achieve influence spread performance comparable to SOTA IM methods, while speeding up the query-answering time by several orders of magnitude. We hope this work can open abundant future directions for other query-answering tasks of IM variants, or on uncertain graphs, from an index-based perspective.