A prediction data generation device includes a storage device and a processor, and generates prediction data in which a node of a directed graph is defined and a link of the directed graph is defined by a transition of the node. The prediction data is used as an input of a transition prediction process predicting a transition of the node. The processor is configured to execute a storage update process updating the prediction data in order and storing the updated prediction data in the storage device in accordance with an update of the data group along with elapse of time. The storage update process includes at least one of a process of increasing the number of observations of the node when a node per category is previously known, or a process of increasing the number of observations of the link when a link per category is previously known.