  Influence maximization (IM) is the task of finding the most important nodes
in order to maximize the spread of influence or information on a network. This
task is typically studied on static or temporal networks where the complete
topology of the graph is known. In practice, however, the seed nodes must be
selected before observing the future evolution of the network. In this work, we
consider this realistic ex ante setting where $p$ time steps of the network
have been observed before selecting the seed nodes. Then the influence is
calculated after the network continues to evolve for a total of $T>p$ time
steps. We address this problem by using statistical, non-negative matrix
factorization and graph neural networks link prediction algorithms to predict
the future evolution of the network and then apply existing influence
maximization algorithms on the predicted networks. Additionally, the output of
the link prediction methods can be used to construct novel IM algorithms. We
apply the proposed methods to eight real-world and synthetic networks to
compare their performance using the Susceptible-Infected (SI) diffusion model.
We demonstrate that it is possible to construct quality seed sets in the ex
ante setting as we achieve influence spread within 87\% of the optimal spread
on seven of eight network. In many settings, choosing seed nodes based only
historical edges provides results comparable to the results treating the future
graph snapshots as known. The proposed heuristics based on the link prediction
model are also some of the best-performing methods. These findings indicate
that, for these eight networks under the SI model, the latent process which
determines the most influential nodes may not have large temporal variation.
Thus, knowing the future status of the network is not necessary to obtain good
results for ex ante IM.
