In many applications where the data is both graph-structured and time-dependent, it is unfeasible to have full knowledge of the data at every time step, even if sufficient memory would be available to store it. In this presentation, I first motivate this problem with examples, to get at a classification of common settings in terms of observability, objective, type of time-dependentness, etc. Next, I sketch approaches for a number of interesting cases where the interaction with the data has a common structure and one can make reasonable assumptions about the underlying process. The presentation is concluded with a set of open questions.