Our proposed IM-META method, consisting of two phases for (I) network discovery and (II) seed set selection, tackles the aforementioned challenges by judiciously establishing new design principles, as illustrated in Fig. REF . As our main contributions, IM-META iteratively performs the following three steps for network discovery. As the first step of each iteration, we infer a set of probabilities of unexplored edges using both the node metadata and the currently explored subgraph. To this end, we design a minimally supervised learning architecture using the explored small-size subgraph as training data, which is based on a Siamese neural network model that is capable of learning the relationship between collected metadata and edge prediction. By learning embeddings that accurately capture the homophily effect of information diffusion networks, which reveals the tendency of an individual node to associate with similar other nodes, our trained Siamese neural network inductively maps new input data (i.e., unexplored nodes) whose connectivity information to the training data (i.e., explored nodes) is unknown. The learned embedding acts as a feature selection (or dimensionality reduction) module that captures the latent representation of collected data. As the second step, we generate a reinforced weighted graph by seamlessly combining the edge probabilities inferred in the previous step with the current explored subgraph. Toward this end, we select only a limited number of confidence edges based on the intuitions that i) using a large portion of uncertain edges leads to an accumulation of noise in the subsequent processes and that ii) this edge selection also reduces the computational complexity. As the third step, we select a queried node as the last step of an iteration for network discovery. As one of our main contributions, instead of choosing a queried node based on high degree centrality in the observable subgraph, we propose our own topology-aware ranking strategy for query node selection. Specifically, the proposed ranking measure balances between the degree centrality of a target node and its geodesic distance to potential seeds. The node selected from this ranking strategy at each query step potentially leads to a high expected influence spread. After the network discovery phase, we finally select a set of seed nodes similarly as in the standard IM problem [1]}, [2]}, [3]}, [4]}.
An analysis of the computational complexity of our IM-META method shows that the complexity is dominated by the seed set selection phase rather than the network discovery phase and falls within the same bound as that of a greedy algorithm that works on the fully known network.
