Deep Gaussian Markov Random Fields for Graph-Structured Dynamical Systems

Probabilistic inference in high-dimensional state-space models is computationally challenging. For many spatiotemporal systems, however, prior knowledge about the dependency structure of state variables is available. We leverage this structure to develop a computationally efficient approach to state estimation and learning in graph-structured state-space models with (partially) unknown dynamics and limited historical data. Building on recent methods that combine ideas from deep learning with principled inference in Gaussian Markov random fields (GMRF), we reformulate graph-structured state-space models as Deep GMRFs defined by simple spatial and temporal graph layers. This results in a flexible spatiotemporal prior that can be learned efficiently from a single time sequence via variational inference. Under linear Gaussian assumptions, we retain a closed-form posterior, which can be sampled efficiently using the conjugate gradient method, scaling favourably compared to classical Kalman filter based approaches

Paper

References (65)

Scroll for more · 38 remaining

Similar papers

Peer review

Reviewer Upf66/10 · confidence 4/52023-07-02

Summary

This paper proposes a Gaussian model for graph-temporal data, with two sorts of sparseness in the precision matrix: blockwise due to an assumed Markov property in time, and within blocks due to assumed sparse graph structures. To achieve inference and parameter learning the paper proposes a two-stage approach with parameter learning done via VI and final posterior (mean) inference with CG. The variational distribution has a suitable structure that reflects the temporal sparseness of the model.

Strengths

The presented model is a very natural and ubiquitous one, so the setting is well motivated. There are no other approaches that I am aware of that solve this particular situation. The approach is certainly valid. I found this paper easy to read and well explained. Rather than solve the inference problem with a Kalman-style algorithm (as in [1]) this paper proposes a two-stage approach of using VI for parameter learning and then CG for the final posterior (mean). I initially thought this was a rather strange thing to do, but on reflection I see that it is quite a good idea in this setting. I wonder whether this has more general application. The design of the posterior distribution is well chosen to capture the (exact?) posterior while reducing the computation complexity of the naive approach.

Weaknesses

The experiments section is rather weak and is comes across more as a unit test than a proper evaluation: the data is drawn from exactly the correct model class, and the primary comparison is to a model that is the same but missing the temporal dependencies. There is not comparison on real data, or on simulated data with any other approach except extremely simple AR/MA/ARMA models. The approach of [1] is applicable for the temporal part of this setting, and for a 30x30 grid it is feasible to take the 900 dimensional dense representation. This would have made a useful comparison. In terms of novelty, the extension the spatio-temporal regime is not a huge leap, and is already arguably already in the DGMRF model class already. Most of VI is introduced in [40], so the novelty there is not that great. While the setting is general, to enable fast determinant the form of the spatial layer is actually quite restricted. For a general spatial graph the approach would be no better than kalman approaches.

Questions

With the extension propose on 267 it would seem to me that the variational distribution contains the exact posterior. Is this correct? If so, then the CG could surely be omitted if the VI was run to convergence (e.g. with an annealing learning rate). I assume the variational distribution is learned by direct gradient descent on the parameters. This would be rather inefficient if the matrices are ill conditioned. Does the natural gradient approach of [1] work here? The motivation for the two-stage approach is that "parameter estimation becomes computationally prohibitive in high dimensional settings". [57] shows that doing the (truncated) CG algorithm also gives the marginal likelihood log det term with a good approximation. I feel that this is relevant work which should be discussed. [57] Scalable Log Determinants for Gaussian Process Kernel Learning, Dong, Eriksson, Nickisch, Bindel, Wilson, NeurIPS 2017 Typo: 371 extend -> extent

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The approach is limited to Gaussian models, and in this case exact inference is available if the problem is small enough, so the method is only relevant for larger data. It is not really made clear in the experiments how large is feasible, and whether the two stage approach really works on real rather than simulated data.

Reviewer k13T4/10 · confidence 2/52023-07-04

Summary

The paper extends Gaussian Random Fields with precision-based spatiotemporal structure.

Strengths

Clarity: The paper is professionally written, with flawless math. The method is technical and dense, and there are many parts to it. It would have been useful to include illustrations, perhaps in the supplements. Originality: The paper has moderate novelty. The idea of using spatial and temporal precisions to model random fields is very apt, but these ideas are also well known in general. Quality: The method is principled and well derived.

Weaknesses

The experimental evaluation is insufficient. There is only a single simple advection example, which is effectively a toy case. There are no real world experiments. Unfortunately a paper like this really needs a real world’y experiment to show that the method has transferable performance. The paper is really good, but I’m leaning on rejection for this reason alone. The performance is good, but incremental. I’m happy with the neural network variant performance, but there is something wrong if the advection model (that matches the true system perfectly!) can’t fit the simple dynamics, nor improve over neural network. I wonder if this is a sampling or data scarcity issue. The results are a black box. The purpose of this work is to learn temporal causalities, and spatial couplings. Yet, neither are shown! The paper needs to illustrate what kind of structures the system has learnt, and show if they are accurate or useful, and demonstrate transferable insights.

Questions

None

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

No issues

Reviewer LAkB6/10 · confidence 4/52023-07-06

Summary

The author extend work on deep Gaussian Markov random field to a spatio-temporal setting. Earlier it has been explored in spatial and graphical setting. The authors show how to retain the sparsity structure of the previous work, which is need to be computationally feasible. They also show the various types of temporal structure can be built in this framework.

Strengths

The extension to a spatio-temporal models is of course very important as many datasets have both a spatial and temporal structure. Also that the methods are computationally feasible is paramount as the complexity spatio-temporal models tend to be very large. Each part of the paper is clear written.

Weaknesses

The main weakness for me is the validation of the method only a single simulated data set is rather weak. If I understand it correctly you are comparing your method to either a pure time series model (AR, MA, ARMA) or a pure spatial (DGMRF?) this does not seems like a fair comparison. Something simple like a AR processes with spatial noise is standard in statistics.

Questions

In Figure 2 to the right should w be from 6-10 in the it says 6-9,12? Also how come mae is decreasing when w is increasing? Why is the average value of the simulations very negative in appendix in the colorbar the value ranges from -35 to -40. Have you added a mean in the other models, so they can compensate for this? You should also be able to get the marginal posterior distributions for your model how does they look for the simulations?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

.

Reviewer 9F966/10 · confidence 4/52023-07-24

Summary

This work extends DGMRF to account for temporal dependency in data with a SSM reformulation. With necessary assumptions, the proposed method produces accurate posterior, competitive performance to DGMRF and faster inference to Kalman smoother.

Strengths

- The method extends DGMRF to account for temporal dependency in data. - It has been shown that the method has low computational complexity and good scalability. - The method produces higher accurate posterior comparing to DGMRF and other transitional TS models.

Weaknesses

- Since the method is extending to dynamical systems, DGMRF is a bit of "strawman". The method should be also compared with other filter/smoother e.g. deep KL, ensemble KL, particle smoothing and etc. - Though the posterior was evaluated in the manuscript, the dynamical model (F) wasn't. It is very often that you got a decent posterior but learned a "bad" F (in terms of forecasting). - Only the posterior mean was evaluated. It is unclear how good the posterior variance is. - The variational posterior should be compared to the true posterior in an example where the latter is accessible analytically or via sampling. - Only one synthetic example is not sufficient for evaluating the method thoroughly. It is unclear how it generalizes.

Questions

- Were the observation parameters $H$ and $\xi$ trainable or fixed at the true values? - Were the hyperparameters such as state noise and observation noise trainable or fixed at the true values?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

4 excellent

Limitations

The technical limitations were discussed in the last section.

Reviewer k13T2023-08-11

resp

Thanks for the response. Including a new experiment is beneficial for the paper, but I am worried that this is too much changes to the paper during review period. Similarly I would prefer the method and results to not change during this time either: the paper should have converged before submission. Finally, my concerns about learned structured insights remain. For these reasons I still vote for rejection, although I am raising my score to 4.

Authorsrebuttal2023-08-11

Response to k13T

Thank you for taking the time to carefully consider our changes and engage in a discussion with us. First, we would like to point out that while the results (Table 2 in original paper, Table 1 in provided PDF) did change, our proposed method as described in the submitted paper did not. The improved numbers are merely a result of improving the actual implementation (addressing issues like numerical instabilities). Second, we have included the real-world experiment and the additional spatiotemporal AR baseline during the rebuttal phase to directly address concerns raised by the reviewers. We would like to point out that Neurips facilitates uploading an extra PDF page with figures and tables for this exact purpose. This, in our opinion, indicates that additions and changes that improve the submitted paper are clearly encouraged. In any case, we appreciate that our changes were acknowledged as beneficial for the paper in general. Regarding the structural insights that can be gained using our method, we will come back to you soon to provide details on how we are planning to evaluate the learned structures. We would be glad to engage in further discussion with you about this.

Authorsrebuttal2023-08-18

Evaluation of learned dynamics

To address remaining concerns regarding the learned structures, we have now compared the learned transitions for different ST-DGMRF models trained on the advection-diffusion dataset with the true data-generating process, which we have access to in this case. In particular, we extracted the stencil for an arbitrary point on the lattice (all points are equivalent) from the true transition matrix as well as from the learned ones. We then compared them qualitatively by visualizing the local graph structure and the corresponding weights of the stencil. Finally, we computed the Pearson correlation coefficient and the MAE between learned and ground truth weights. We find that for all ST-DGMRF variants the learned transition model is very close to the ground truth. The more temporal layers are used, the better the agreement. Moreover, even with only 2 temporal layers we learn an adequate approximation of the true transition, with Pearson correlation coefficients remaining above 0.87 (p << 0.01) and MAE remaining below 0.025 (ground truth weights range between -0.26 and 0.36), for both the advection-diffusion and the neural network transition models respectively. This is in good agreement with the corresponding posterior evaluation (Table 1 in the provided PDF). We are planning to incorporate these results in the main text of the paper. (also replied to 9F96)

Reviewer 9F962023-08-11

Thank the authors for the response. > We added a spatiotemporal ST-AR baseline (see general rebuttal) to address this limitation. Unfortunately, other more complex filter/smoother approaches are more difficult to apply in the setting we are considering. For example, deep Kalman filtering with KVAE [17] requires the definition of a suitable encoder mapping from high-dimensional observations to a latent space. In settings where the pattern of missing observations varies over time, this requires some initial imputation or a smart way to inform the encoder about this pattern, and thus falls beyond the scope of this paper. On the other hand, ensemble or particle filter approaches typically rely on an established dynamics model (as discussed in line 82-88). While we have such a dynamics model available for the advection-diffusion dataset, applying ensemble or particle filtering would simply converge towards the true posterior distribution, which we have access to, and therefore would, in our opinion, not form a very useful comparison. - It could be the example to compare with the true posterior. - Missing observations is not a must for every example, is it? - There are variational methods learning the, e.g. [Frigola 2014](https://papers.nips.cc/paper_files/paper/2014/hash/139f0874f2ded2e41b0393c4ac5644f7-Abstract.html) and [Naesseth 2017](https://arxiv.org/abs/1705.11140). Dual Kalman filter could also learn the dynamical model. Fig 1. bottom. Three methods perfectly overlap for input data?

Authorsrebuttal2023-08-17

>- It could be the example to compare with the true posterior. To do this, we have now implemented the Ensemble Kalman Smoother with an advection-diffusion transition model matching the data-generating process. We used $10^4$ ensemble members (the maximum feasible on our machine). Fixing the velocity and diffusion parameters to the true values, we obtain the following results: $MAE_{\mu}$ = 0.0512$\tiny{\pm 0.0019}$, $RMSE_{\mu}$ = 0.0654$\tiny{\pm 0.0028}$, $MAE_{\sigma}$ = 0.0041$\tiny{\pm 0.0000}$, $RMSE_{\sigma}$ = 0.0045$\tiny{\pm 0.0000}$, $CRPS$ = 0.1025$\tiny{\pm 0.0029}$ As expected, the estimated posterior is very close to the true posterior. For a more appropriate comparison with our approach, we used a state augmentation approach to estimate the velocity and diffusion parameters jointly with the system states. In contrast to the ST-DGMRF approach, we consider initial and transition noise parameters to be fixed in order to avoid divergence of the EnKS. This yields the following results: $MAE_{\mu}$ = 0.1249$\tiny{\pm 0.1423}$, $RMSE_{\mu}$ = 0.1925$\tiny{\pm 0.2504}$, $MAE_{\sigma}$ = 0.0046$\tiny{\pm 0.0011}$, $RMSE_{\sigma}$ = 0.0061$\tiny{\pm 0.0031}$, $CRPS$ = 0.1624$\tiny{\pm 0.1226}$ While $MAE_{\sigma}, RMSE_{\sigma}$ are lower than with our approach, $MAE_{\mu}, RMSE_{\mu}$ are slightly higher than with the ST-DGMRF model with $L_{\text{temporal}}=4$. Note that $MAE_{\sigma}$ and $RMSE_{\sigma}$ are expected to increase as well when considering the noise parameters unknown. Reducing the ensemble size by half, increases $MAE_{\mu}$ and $RMSE_{\mu}$ further to 0.1647$\tiny{\pm} 0.1274$ and 0.2244$\tiny{\pm 0.1765}$ respectively. >- Missing observations is not a must for every example, is it? You are right, missing observations are not a must. However, settings with partially observed system states are a focus of our paper and one of the main motivations for developing our approach (see lines 15-25), which is why we designed our experiments accordingly. >- There are variational methods learning the, e.g. [Frigola 2014](https://papers.nips.cc/paper_files/paper/2014/hash/139f0874f2ded2e41b0393c4ac5644f7-Abstract.html) and [Naesseth 2017](https://arxiv.org/abs/1705.11140). Dual Kalman filter could also learn the dynamical model. Thank you for sharing these very interesting papers with us. Using Gaussian processes in combination with variational inference, as done in Frigola 2014, is indeed a very promising approach. However, their application seems (so far) limited to small systems (e.g. one variable and its derivative). Applying such an approach to large systems with interacting components would require designing a suitable GP transition with both high-dimensional input and high-dimensional output. This seems beyond the scope of this paper. >Fig 1. bottom. Three methods perfectly overlap for input data? Yes, this is expected because the input data points $\mathbf{y}$ are given to all these methods at inference time. Unless the observation noise is set very high, the estimated posterior $p(\mathbf{x}\mid\mathbf{y})$ will thus be very close to the observed values at these points for all considered methods. If you have any further questions, we would be happy to answer them.

Authorsrebuttal2023-08-18

Evaluation of learned dynamics

> Though the posterior was evaluated in the manuscript, the dynamical model (F) wasn't. It is very often that you got a decent posterior but learned a "bad" F (in terms of forecasting). We have now compared the learned transitions for different ST-DGMRF models trained on the advection-diffusion dataset with the true data-generating process, which we have access to in this case. In particular, we extracted the stencil for an arbitrary point on the lattice (all points are equivalent) from the true transition matrix as well as from the learned ones. We then compared them qualitatively by visualizing the local graph structure and the corresponding weights of the stencil. Finally, we computed the Pearson correlation coefficient and the MAE between learned and ground truth weights. We find that for all ST-DGMRF variants the learned transition model is very close to the ground truth. The more temporal layers are used, the better the agreement. Moreover, even with only 2 temporal layers we learn an adequate approximation of the true transition, with Pearson correlation coefficients remaining above 0.87 (p << 0.01) and MAE remaining below 0.025 (ground truth weights range between -0.26 and 0.36), for both the advection-diffusion and the neural network transition models respectively. This is in good agreement with the corresponding posterior evaluation (Table 1 in the provided PDF). We are planning to incorporate these results in the main text of the paper. (also replied to k13T)

Reviewer 9F962023-08-18

Thank you for the responses. You have addressed my questions. I have raised the score to 6.

Reviewer Upf62023-08-17

Comment

I thank the authors for the extensive and detailed reply. My questions were addressed satisfactorily. An implementation of [1] is at https://github.com/secondmind-labs/markovflow, thought it may be quite difficult to use. I continue to be broadly in favour of the paper.

Program Chairsdecision2023-09-21

Decision

Accept (poster)

© 2026 NYSGPT2525 LLC