Dynamic graphs, whose topologies are defined by a time-evolving set of nodes or entities and corresponding edges or relationships between such entities, are an important field of study across many scientific domains. Often, it is desirable to learn graph topologies when nodes and edges in the graph’s topology are only partially observed across time. Uncovering these unknown relationships between known and new entities can be framed as a link prediction problem of a time-varying, partially observed graphical network. In this work, we propose a modeling strategy to learn a dynamic graph’s underlying structure with quantifiable uncertainties, when connections in the graph are only partially known. Using this framework, we learn the graph's changing topology via a Markov process and demonstrate how it can be used to predict trajectories of the partially observed dynamic graph. We further discuss the computational challenges of such an approach, and how they might be overcome within a scientific computing framework.