IM-META: Influence Maximization Using Node Metadata in Networks With Unknown Topology

In real-world applications of influence maximization (IM), the network structure is often unknown. Thus, we may identify the most influential seed nodes by exploring only a part of the underlying network given a small budget for node queries. Motivated by the fact that collecting node metadata is more cost-effective than investigating the relationship between nodes via queried nodes, we propose IM-META, an end-to-end solution to IM in networks with unknown topology by retrieving information from queries and node metadata. However, using such metadata to aid the IM process is not without risk due to the noisy nature of metadata and uncertainties in connectivity inference. To tackle these challenges, we formulate a new IM problem that aims to find both seed nodes and queried nodes. In IM-META, we develop an effective method that iteratively performs three steps: 1) we learn the relationship between collected metadata and edges via a Siamese neural network model, 2) we select a number of inferred confident edges to construct a reinforced graph, and 3) we identify the next node to query by maximizing the inferred influence spread using our topology-aware ranking strategy. By querying only 5% of nodes, IM-META reaches 93% of the upper bound performance.