TL;DR
This paper introduces a novel Bayesian approach to infer network structures and system dynamics from input-output graph signal pairs. By leveraging annealed Langevin dynamics and graph neural networks, the method effectively incorporates prior knowledge about graph distributions, leading to more accurate estimations than traditional methods, especially when dealing with partially known network topologies.
What Problem Does This Paper Address?
Many real-world systems can be modeled as signals propagating on a network, where the network's structure (its adjacency matrix) and the dynamics of signal propagation (the graph filter) are unknown. Traditional methods often focus on point estimation (like maximum likelihood) and struggle to incorporate prior knowledge about the network's structure beyond simple sparsity. This paper tackles the challenge of simultaneously inferring both the network topology and the parameters of a generic graph filter, particularly when only a portion of the network's connections are known. A key difficulty is how to effectively leverage a dataset of existing graphs to inform the inference process, even if these graphs have different sizes.
Methods
The core of the proposed method is a Bayesian sampling algorithm based on annealed Langevin dynamics. Instead of finding a single "best" estimate (like in maximum likelihood or MAP estimation), this approach draws samples from the posterior distribution of the unknown parameters (network adjacency matrix $A$ and filter parameters $\theta$).
Here's a breakdown of the key techniques:
- System Model: The system is defined by a graph filter $h(\cdot)$ with unknown parameters $\theta$, applied to a graph with adjacency matrix $A$. The observed output signal $y$ is related to the input signal $x$ by $y = h(A)x + \epsilon$, where $\epsilon$ is noise. The adjacency matrix $A$ is only partially known, with some entries observed ($A^O$) and others unknown ($A^U$).
- Bayesian Inference: The problem is framed as inferring the posterior distribution $p(A, \theta | X, Y)$.
- Annealed Langevin Dynamics: This is a Markov Chain Monte Carlo (MCMC) method that generates samples from a target distribution by simulating a stochastic differential equation. The "annealed" aspect refers to gradually reducing noise levels during the sampling process, allowing the algorithm to explore the space of continuous variables that approximate the discrete graph structure. This is crucial because direct sampling from a discrete distribution is challenging.
- Graph Neural Networks (GNNs) for Prior Knowledge: To incorporate prior information from a dataset of graphs, the authors train a permutation-equivariant GNN (EDP-GNN). This GNN learns to estimate the score function ($\nabla \log p(A)$) of the prior graph distribution. This learned score function is then used within the Langevin dynamics to guide the sampling towards plausible graph structures. This is a key innovation, as it allows the use of prior knowledge from graphs of varying sizes.
- Joint Estimation: The algorithm jointly estimates the adjacency matrix $A$ and the filter parameters $\theta$. While Langevin dynamics are used for $A$, a standard gradient descent (specifically, Adam optimizer) is used for $\theta$, maximizing the likelihood of the observed data.
Datasets
- Training Data: The paper uses two types of datasets for training the GNN that learns the prior graph distribution:
- Synthetic Grid Graphs: Generated with varying sizes and random edge additions.
- Real-world Deezer Ego-nets: Collected from the music streaming service Deezer.
- Evaluation Data: The experiments are conducted on similar synthetic grid graphs and real-world Deezer ego-nets.
Key Insights and Ideas
- Sampling vs. Point Estimation: Shifting from point estimation (MAP, MLE) to sampling from the posterior distribution offers a more robust way to handle uncertainty and incorporate prior knowledge, especially in complex inverse problems like network inference.
- GNNs as Score Function Estimators: Using GNNs to learn the score function of a graph distribution is a powerful way to encode structural priors. This approach bypasses the need for an explicit, closed-form expression for the prior distribution $p(A)$, which is often unavailable.
- Handling Heterogeneous Graphs: The GNN-based prior allows for incorporating knowledge from graphs of different sizes, a significant advantage over methods that require fixed-size inputs.
- Generic Graph Filters: The framework is designed to work with any differentiable graph filter, making it broadly applicable to various network diffusion processes (e.g., heat diffusion, consensus).
Key Results
The paper demonstrates that incorporating prior knowledge through the GNN-based annealed Langevin dynamics significantly improves estimation performance compared to methods that do not use prior information or rely solely on likelihood.
- Improved Accuracy: In both synthetic grid graphs and real-world ego-nets, the proposed "Langevin posterior" method consistently outperforms "Langevin likelihood" (which uses no prior) and a standard Adam optimizer (which enforces sparsity but lacks rich prior information).
- Performance Gains: The F1-score for estimating the unknown adjacency matrix ($A^U$) and the normalized RMSE for the graph filter coefficients ($\theta$) are consistently better with the proposed method. For example, in Figure 1 (grid graphs), the F1-score for $A^U$ is notably higher for the Langevin posterior method across varying numbers of input-output pairs ($K$).
- Scalability: The method shows improved performance as the number of available input-output pairs ($K$) increases, indicating its practical utility.
Limitations and Future Work
- Computational Cost: Annealed Langevin dynamics, while powerful, can be computationally intensive, especially for large networks or complex filters. The paper mentions running T=300 steps per noise level.
- Theoretical Guarantees: The authors state that current work includes formulating theoretical guarantees for their approach.
- Further Comparisons: Future work will involve more extensive simulations on diverse synthetic and real-world datasets and comparisons against other state-of-the-art topology inference methods.
- Discrete Nature of Graphs: While annealed Langevin dynamics approximates the discrete graph structure, the final output is obtained by projecting the continuous estimate onto {0, 1}. Further exploration into handling discrete variables more directly could be beneficial.
Summary updated