Graph Learning over Partially Observed Diffusion Networks: Role of Degree Concentration
This work examines the problem of graph learning over a diffusion network when data can be collected from a limited portion of the network (partial observability). The main question is to establish technical guarantees of consistent recovery of the subgraph of probed network nodes, i) despite the presence of unobserved nodes; and ii) under different connectivity regimes, including the dense regime where the probed nodes are influenced by many connections coming from the unobserved ones. We ascertain that suitable estimators of the combination matrix (i.e., the matrix that quantifies the pairwise interaction between nodes) possess an identifiability gap that enables the discrimination between connected and disconnected nodes. Fundamental conditions are established under which the subgraph of monitored nodes can be recovered, with high probability as the network size increases, through universal clustering algorithms. This claim is proved for three matrix estimators: i) the Granger estimator that adapts to the partial observability setting the solution that is exact under full observability ; ii) the one-lag correlation matrix; and iii) the residual estimator based on the difference between two consecutive time samples. A detailed characterization of the asymptotic behavior of these estimators is established in terms of an error bias and of the identifiability gap, and a sample complexity analysis is performed to establish how the number of samples scales with the network size to achieve consistent learning. Comparison among the estimators is performed through illustrative examples that show how estimators that are not optimal in the full observability regime can outperform the Granger estimator in the partial observability regime. The analysis reveals that the fundamental property enabling consistent graph learning is the statistical concentration of node degrees.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringGraph LearningSimilar Papers 제목 키워드 기반
Synthesis of Partially Observed Jump-Diffusion Systems via Control Barrier Functions
In this paper, we study formal synthesis of control policies for partially observed jump-diffusion systems against complex logic specifications. Given a state estimator, we utilize a discretization-free approach for form…
Neural Algorithms for Graph Navigation
The application of deep reinforcement learning (RL) to graph learning and meta-learning admits challenges from both topics. We consider the task of one-shot, partially observed graph navigation, acknowledging and addres…
Deep Reinforcement LearningGraph LearningMeta-Learningreinforcement-learning+1Leveraging Graph Diffusion Models for Network Refinement Tasks
Most real-world networks are noisy and incomplete samples from an unknown target distribution. Refining them by correcting corruptions or inferring unobserved regions typically improves downstream performance. Inspired b…
DenoisingStyle TransferNeural Message Passing Induced by Energy-Constrained Diffusion
Learning representations for structured data with certain geometries (observed or unobserved) is a fundamental challenge, wherein message passing neural networks (MPNNs) have become a de facto class of model solutions. I…
Inductive BiasDeep ZakaiJ: Structured Filtering for Jump-Diffusion Time Series Forecasting
Time series driven by unobserved latent states frequently exhibit abrupt jump discontinuities whose timing and magnitude cannot be predicted from observed history alone. Classical jump-diffusion models offer a principled…
Time Series Forecasting