State-Space Network Topology Identification from Partial Observations
Pith reviewed 2026-05-25 16:39 UTC · model grok-4.3
The pith
Subspace techniques recover the topology of linear dynamical networks from partial observations even when input and state networks differ.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The central claim is that the topological structure of a deterministic continuous-time linear dynamical system can be recovered from input-output observations using extended subspace methods, with guarantees holding even if the input network differs from the state interaction network. This is supported by an algorithm based on alternating projections that identifies a consistent network topology from data and prior information, and the algorithm is proven to converge.
What carries the argument
Extended subspace identification methods applied to the state-space formulation of the network process, which enable recovery of the system matrix from partial observations.
If this is right
- The method provides recovery guarantees for the state interaction topology separate from the input network.
- An alternating projections algorithm converges to a topology consistent with the observed dynamics and prior structure.
- Partial observations suffice for identification without requiring full state measurements.
- The approach unifies traditional network control theory with signal processing on graphs.
Where Pith is reading between the lines
- This approach could extend to discrete-time systems or time-varying topologies if the subspace methods are adapted accordingly.
- It opens the possibility of applying similar techniques to nonlinear or stochastic network processes by relaxing the deterministic linear assumption.
- Practical deployment might involve testing the method on real sensor network data where topology is partially known.
Load-bearing premise
The underlying system must be a deterministic continuous-time linear dynamical system for which the topology is identifiable through extended subspace methods from partial observations.
What would settle it
Observing that the algorithm outputs a topology which, when used to simulate the system, produces dynamics inconsistent with new input-output measurements would falsify the recovery claim.
Figures
read the original abstract
In this work, we explore the state-space formulation of a network process to recover, from partial observations, the underlying network topology that drives its dynamics. To do so, we employ subspace techniques borrowed from system identification literature and extend them to the network topology identification problem. This approach provides a unified view of the traditional network control theory and signal processing on graphs. In addition, it provides theoretical guarantees for the recovery of the topological structure of a deterministic continuous-time linear dynamical system from input-output observations even though the input and state interaction networks might be different. The derived mathematical analysis is accompanied by an algorithm for identifying, from data, a network topology consistent with the dynamics of the system and conforms to the prior information about the underlying structure. The proposed algorithm relies on alternating projections and is provably convergent. Numerical results corroborate the theoretical findings and the applicability of the proposed algorithm.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript develops a state-space approach to network topology identification for deterministic continuous-time LTI systems. It extends subspace identification methods to recover the state-interaction topology from partial input-output observations, even when this topology differs from the input network. Theoretical recovery guarantees are claimed under the modeling assumptions, accompanied by an alternating-projections algorithm that enforces consistency with the dynamics and prior structural information; the algorithm is stated to be provably convergent, with numerical results offered in support.
Significance. If the guarantees are rigorous, the work supplies a unified perspective linking classical subspace realization to graph-based network inference, with the explicit distinction between input and state networks as a useful modeling feature. The provision of a convergent algorithm that incorporates prior topology information is a concrete strength, as is the focus on partial observations.
minor comments (3)
- [Abstract and § on theoretical analysis] The abstract and introduction assert theoretical guarantees and convergence without enumerating the precise assumptions (e.g., observability, controllability, or persistence-of-excitation conditions) required for the subspace step to recover the labeled state topology rather than an equivalent realization; these should be stated explicitly in the main theoretical section.
- [Numerical results section] Numerical experiments are referenced but lack reported quantitative metrics, baseline comparisons, or error statistics; tables or figures should include these to allow assessment of practical performance.
- [Preliminaries] Notation for the state-interaction matrix versus the input matrix should be clarified early to avoid confusion when the two networks differ.
Simulated Author's Rebuttal
We thank the referee for their positive assessment of the manuscript and for recommending minor revision. We appreciate the recognition of the work's contributions, including the unified perspective linking subspace methods to graph-based inference and the convergent alternating-projections algorithm.
Circularity Check
No significant circularity; derivation extends external subspace methods
full rationale
The paper borrows subspace techniques from system identification literature and extends them to network topology identification, providing new theoretical guarantees for recovery under the continuous-time LTI modeling assumption. The abstract and description explicitly separate the input and state networks and rely on alternating projections for the algorithm. No self-definitional steps, fitted inputs renamed as predictions, or load-bearing self-citations are present in the material; the central claims rest on external benchmarks with independent analysis, making the chain self-contained.
Axiom & Free-Parameter Ledger
axioms (2)
- domain assumption The underlying process is a deterministic continuous-time linear dynamical system
- domain assumption Subspace techniques from system identification can be extended to recover network topology from partial observations
Lean theorems connected to this paper
-
IndisputableMonolith/Cost/FunctionalEquation.leanwashburn_uniqueness_aczel unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
subspace techniques... extended observability matrix O_α... alternating projections... cospectral graphs C_λ_S
-
IndisputableMonolith/Foundation/RealityFromDistinction.leanreality_from_one_distinction unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
first-order differential graph model... state-space... deterministic continuous-time linear dynamical system
What do these tags mean?
- matches
- The paper's claim is directly supported by a theorem in the formal canon.
- supports
- The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
- extends
- The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
- uses
- The paper appears to rely on the theorem as machinery.
- contradicts
- The paper's claim conflicts with a theorem or certificate in the canon.
- unclear
- Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.
Reference graph
Works this paper leans on
-
[1]
New york city taxi analysis wit h graph signal processing,
J. A. Deri and J. M. Moura, “New york city taxi analysis wit h graph signal processing,” in Proc. of the IEEE Conf. on Sig. and Inf. Process. (GLOBALSIP) , 2016, pp. 1275–1279
work page 2016
- [2]
-
[3]
Reactive oxygen gene network of plan ts,
F. Mittler, et al., “Reactive oxygen gene network of plan ts,” Trends in Plant Science , vol. 9, no. 10, pp. 490–498, 2004
work page 2004
-
[4]
Signal processing techniques for interpolation in graph structured data,
S. K. Narang, A. Gadde, and A. Ortega, “Signal processing techniques for interpolation in graph structured data,” in Proc. IEEE Int. Conf. Acoust., Speech Signal Process. (ICASSP) . IEEE, 2013, pp. 5445–5449
work page 2013
-
[5]
Adaptive Graph Signal Processing: Algorithms and Optimal Sampling Strategies
P . Di Lorenzo, P . Banelli, E. Isufi, S. Barbarossa, and G. L eus, “Adaptive graph signal processing: Algorithms and opt imal sampling strategies,” arXiv preprint arXiv:1709.03726, 2017
work page internal anchor Pith review Pith/arXiv arXiv 2017
-
[6]
Signal recovery on graphs: Fundamental limits of sampling strategi es,
S. Chen, R. V arma, A. Singh, and J. Kovaˇ cevi´ c, “Signal recovery on graphs: Fundamental limits of sampling strategi es,” IEEE Trans. Sig. and Inf. Proc. over Netw., vol. 2, no. 4, pp. 539–554, 2016
work page 2016
-
[7]
D. I. Shuman, S. K. Narang, P . Frossard, A. Ortega, and P . V andergheynst, “The emerging field of signal processing on gr aphs: Extending high-dimensional data analysis to networks and other irregular domains,” IEE E Sig. Proc. Mag. , vol. 30, no. 3, pp. 83–98, 2013
work page 2013
-
[8]
Autoregre ssive moving average graph filtering,
E. Isufi, A. Loukas, A. Simonetto, and G. Leus, “Autoregre ssive moving average graph filtering,” IEEE Trans. Signal Process, vol. 65, no. 2, pp. 274–288, 2017. COUTINO ET AL. STA TE-SPACE NETWORK TOPOLOGY IDENTIFICA TION FROM PARTIAL OBSERV A TIONS 15 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 5.5 PSfrag replacements States Graph Inputs Graph (a) 0 2 4 6 8 10 12 14 0 2...
work page 2017
-
[9]
Advances in distribute d graph filtering,
M. Coutino, E. Isufi, and G. Leus, “Advances in distribute d graph filtering,” IEEE Transactions on Signal Processing , 2019
work page 2019
-
[10]
Matched signal detection on graphs: Theory and app lication to brain imaging data classification,
C. Hu, J. Sepulcre, K. A. Johnson, G. E. Fakhri, Y . M. Lu, a nd Q. Li, “Matched signal detection on graphs: Theory and app lication to brain imaging data classification,” NeuroImage, vol. 125, pp. 587–600, 2016
work page 2016
-
[11]
Subgraph detection using gra ph signals,
S. P . Chepuri and G. Leus, “Subgraph detection using gra ph signals,” in Proc. of the 50th Asilomar Conf. Sig., Syst. and Comp. , 2016, pp. 532–534
work page 2016
-
[12]
Blind graph topolog y change detection,
E. Isufi, A. S. Mahabir, and G. Leus, “Blind graph topolog y change detection,” Signal processing letters , vol. 25, no. 5, pp. 655–659, 2018
work page 2018
-
[13]
How to learn a graph from smooth signals ,
V . Kalofolias, “How to learn a graph from smooth signals ,” in Artificial Intelligence and Statistics , 2016, pp. 920–929
work page 2016
-
[14]
G. Mateos, S. Segarra, and A. G. Marques, “Inference of g raph topology,” Cooperative and Graph Signal Processing: Principles and Ap plications (PM Djuric and C. Richard, eds.), Amsterdam, Netherlands: Else vier, 2018
work page 2018
-
[15]
Ne twork topology inference from spectral templates,
S. Segarra, A. G. Marques, G. Mateos, and A. Ribeiro, “Ne twork topology inference from spectral templates,” IEEE Transactions on Signal and Information Processing over Networks , 2017
work page 2017
-
[16]
Multi-kernel based nonlinear models for connectivi ty identification of brain networks,
G. Karanikolas, G. B. Giannakis, K. Slavakis, and R. M. L eahy, “Multi-kernel based nonlinear models for connectivi ty identification of brain networks,” in Proc. of the IEEE Int. Conf. on Acoust. Speech and Sig. Proces s. (ICASSP) , 2016, pp. 6315–6319
work page 2016
-
[17]
Kernel-base d structural equation models for topology identification of directed networks,
Y . Shen, B. Baingana, and G. B. Giannakis, “Kernel-base d structural equation models for topology identification of directed networks,” IEEE Trans. on Sig. Process., vol. 65, no. 10, pp. 2503–2516, 2017
work page 2017
-
[18]
Closed Form Solutions of Combinatorial Graph Laplacian Estimation under Acyclic Topology Constraints
K.-S. Lu and A. Ortega, “Closed form solutions of combin atorial graph laplacian estimation under acyclic topology constraints,” arXiv preprint arXiv:1711.00213, 2017
work page internal anchor Pith review Pith/arXiv arXiv 2017
-
[19]
Topology identification of weight ed complex dynamical networks,
J. Zhou and J.-a. Lu, “Topology identification of weight ed complex dynamical networks,” Physica A: Statistical Mechanics and Its Applications , vol. 386, no. 1, pp. 481–491, 2007
work page 2007
-
[20]
Tensor decom positions for identifying directed graph topologies and tr acking dynamic networks,
Y . Shen, B. Baingana, and G. B. Giannakis, “Tensor decom positions for identifying directed graph topologies and tr acking dynamic networks,” IEEE Trans. on Sig. Process. , vol. 65, no. 14, pp. 3675–3687, 2017
work page 2017
-
[21]
N etwork topology inference from non-stationary graph signa ls,
R. Shafipour, S. Segarra, A. G. Marques, and G. Mateos, “N etwork topology inference from non-stationary graph signa ls,” in Proc. of the IEEE Int. Conf. on Acoust. Speech and Sig. Process. (ICASSP) , 2017, pp. 5870–5874
work page 2017
-
[22]
Co nnecting the dots: Identifying network structure via graph signal processing,
G. Mateos, S. Segarra, A. G. Marques, and A. Ribeiro, “Co nnecting the dots: Identifying network structure via graph signal processing,” IEEE Signal Processing Magazine, vol. 36, no. 3, pp. 16–43, 2019
work page 2019
-
[23]
Topolo gy identification and learning over graphs: Accounting for n onlinearities and dynamics,
G. B. Giannakis, Y . Shen, and G. V . Karanikolas, “Topolo gy identification and learning over graphs: Accounting for n onlinearities and dynamics,” Proceedings of the IEEE , vol. 106, no. 5, pp. 787–807, 2018
work page 2018
-
[24]
A. P . Dempster, “Covariance selection,” Biometrics, pp. 157–175, 1972
work page 1972
-
[25]
S. L. Lauritzen, Graphical models . Clarendon Press, 1996, vol. 17
work page 1996
-
[26]
Optimal graph- filter design and applications to distributed linear networ k operators,
S. Segarra, A. Marques, and A. Ribeiro, “Optimal graph- filter design and applications to distributed linear networ k operators,” IEEE Trans. Signal Process, 2017
work page 2017
-
[27]
Model selection and estimation in th e gaussian graphical model,
M. Y uan and Y . Lin, “Model selection and estimation in th e gaussian graphical model,” Biometrika, vol. 94, no. 1, pp. 19–35, 2007
work page 2007
-
[28]
A Unified Framework for Structured Graph Learning via Spectral Constraints
S. Kumar, J. Ying, J. V . d. M. Cardoso, and D. Palomar, “A u nified framework for structured graph learning via spectral constraints,” arXiv preprint arXiv:1904.09792, 2019
work page internal anchor Pith review Pith/arXiv arXiv 1904
-
[29]
Semi-bli nd inference of topologies and signals over graphs,
V . N. Ioannidis, Y . Shen, and G. B. Giannakis, “Semi-bli nd inference of topologies and signals over graphs,” in 2018 IEEE Data Science W orkshop (DSW). IEEE, 2018, pp. 165–169
work page 2018
-
[30]
Semi-blind inference of topologies and dynamical processes over dynamic graphs,
——, “Semi-blind inference of topologies and dynamical processes over dynamic graphs,” IEEE Transactions on Signal Processing , 2019
work page 2019
-
[31]
Studying the human brain anatomical network via diffusion-weighted mri and graph theory,
Y . Iturria-Medina, R. C. Sotero, E. J. Canales-Rodr´ ıg uez, Y . Alem´ an-G´ omez, and L. Melie-Garc´ ıa, “Studying the human brain anatomical network via diffusion-weighted mri and graph theory,” Neuroimage, vol. 40, no. 3, pp. 1064–1076, 2008
work page 2008
-
[32]
J. A. Hertz, Introduction to the theory of neural computation . CRC Press, 2018
work page 2018
-
[33]
A tutorial on chemical reaction network dyn amics,
D. Angeli, “A tutorial on chemical reaction network dyn amics,” European journal of control , vol. 15, no. 3-4, pp. 398–406, 2009
work page 2009
-
[34]
F. R. Chung, Spectral graph theory . American Mathematical Soc., 1997, no. 92. COUTINO ET AL. STA TE-SPACE NETWORK TOPOLOGY IDENTIFICA TION FROM PARTIAL OBSERV A TIONS 16
work page 1997
-
[35]
On projection algorit hms for solving convex feasibility problems,
H. H. Bauschke and J. M. Borwein, “On projection algorit hms for solving convex feasibility problems,” SIAM review, vol. 38, no. 3, pp. 367–426, 1996
work page 1996
-
[36]
Detecting strange attractors in turbulenc e,
F. Takens, “Detecting strange attractors in turbulenc e,” in Dynamical systems and turbulence, W arwick 1980 . Springer, 1981, pp. 366–381
work page 1980
-
[37]
Subspace-based methods for the identificat ion of linear time-invariant systems,
M. Viberg, “Subspace-based methods for the identificat ion of linear time-invariant systems,” Automatica, vol. 31, no. 12, pp. 1835–1851, 1995
work page 1995
-
[38]
Prediction error estimation methods,
L. Ljung, “Prediction error estimation methods,” Circuits, Systems and Signal Processing , vol. 21, no. 1, pp. 11–21, 2002
work page 2002
-
[39]
Diffusion and elastic equations on networks,
S.-Y . Chung, Y .-S. Chung, and J.-H. Kim, “Diffusion and elastic equations on networks,” Publications of the Research Institute for Mathematical Sc iences, vol. 43, no. 3, pp. 699–726, 2007
work page 2007
-
[40]
Discrete signal proces sing on graphs,
A. Sandryhaila and J. M. Moura, “Discrete signal proces sing on graphs,” IEEE Trans. Signal Process , vol. 61, no. 7, pp. 1644–1656, 2013
work page 2013
-
[41]
Graph signal processing: Overview, challenges, and applications,
A. Ortega, P . Frossard, J. Kovaˇ cevi´ c, J. M. Moura, andP . V andergheynst, “Graph signal processing: Overview, challenges, and applications,” Proceedings of the IEEE , vol. 106, no. 5, pp. 808–828, 2018
work page 2018
-
[42]
N. J. Higham, Functions of matrices: theory and computation . Siam, 2008, vol. 104
work page 2008
-
[43]
Random walks on graphs: A survey,
L. Lov´ asz et al. , “Random walks on graphs: A survey,” Combinatorics, Paul erdos is eighty , vol. 2, no. 1, pp. 1–46, 1993
work page 1993
-
[44]
Forecast ing time series with varma recursions on graphs,
E. Isufi, A. Loukas, N. Perraudin, and G. Leus, “Forecast ing time series with varma recursions on graphs,” arXiv preprint arXiv:1810.08581 , 2018
-
[45]
Subspace methods in system identification,
M. Viberg, “Subspace methods in system identification, ” IF AC Proceedings V olumes, vol. 27, no. 8, pp. 1–12, 1994
work page 1994
-
[46]
K. Ogata and Y . Y ang, Modern control engineering . Prentice hall India, 2002, vol. 4
work page 2002
-
[47]
M. V erhaegen and V . V erdult, Filtering and system identification: a least squares approa ch. Cambridge university press, 2007
work page 2007
-
[48]
M. V erahegen and P . Dewilde, “Subspace model identifica tion. part i: The output-error state-space model identifica tion class of algorithm,” Int. J. Control, vol. 56, pp. 1187–1210, 1992
work page 1992
-
[49]
A unifying theorem for t hree subspace system identification algorithms,
P . V an Overschee and B. De Moor, “A unifying theorem for t hree subspace system identification algorithms,” Automatica, vol. 31, no. 12, pp. 1853–1864, 1995
work page 1995
-
[50]
Springer Science & Business Media, 2012
——, Subspace identification for linear systems: TheoryImpleme ntationApplications. Springer Science & Business Media, 2012
work page 2012
-
[51]
Sparsest network s upport estimation: A submodular approach,
M. Coutino, S. Chepuri, and G. Leus, “Sparsest network s upport estimation: A submodular approach,” in 2018 IEEE Data Science W orkshop , 2018
work page 2018
-
[52]
State-spa ce based network topology identification,
M. Coutino, E. Isufi, T. Maehara, and G. Leus, “State-spa ce based network topology identification,” in Information Theory and Applications W orkshop (ITA), 2019
work page 2019
-
[53]
M. Chu, G. Golub, and G. H. Golub, Inverse eigenvalue problems: theory, algorithms, and appl ications. Oxford University Press, 2005, vol. 13
work page 2005
-
[54]
Devlin, Sets, functions, and logic: an introduction to abstract mat hematics
K. Devlin, Sets, functions, and logic: an introduction to abstract mat hematics. Chapman and Hall/CRC, 2003
work page 2003
-
[55]
A. E. Brouwer and W. H. Haemers, Spectra of graphs . Springer Science & Business Media, 2011
work page 2011
-
[56]
G. H. Golub and C. F. V an Loan, Matrix computations . JHU press, 2012, vol. 3
work page 2012
-
[57]
The projected gradient met hod for least squares matrix approximations with spectral c onstraints,
M. T. Chu and K. R. Driessel, “The projected gradient met hod for least squares matrix approximations with spectral c onstraints,” SIAM Journal on Numerical Analysis , vol. 27, no. 4, pp. 1050–1060, 1990
work page 1990
-
[58]
Numerical methods for solving inverse eigenv alue problems for nonnegative matrices,
R. Orsi, “Numerical methods for solving inverse eigenv alue problems for nonnegative matrices,” SIAM Journal on Matrix Analysis and Applications , vol. 28, no. 1, pp. 190–212, 2006
work page 2006
-
[59]
Local convergence for alternating and averaged nonconvex projections
A. Lewis, R. Luke, and J. Malick, “Local convergence for alternating and averaged nonconvex projections,” arXiv preprint arXiv:0709.0109 , 2007
work page internal anchor Pith review Pith/arXiv arXiv 2007
-
[60]
An information flow model for conflict and fission in small groups,
W. W. Zachary, “An information flow model for conflict and fission in small groups,” Journal of anthropological research , vol. 33, no. 4, pp. 452–473, 1977
work page 1977
-
[61]
Dynamical systems that sort lists, dia gonalize matrices, and solve linear programming problems,
R. W. Brockett, “Dynamical systems that sort lists, dia gonalize matrices, and solve linear programming problems, ” Linear Algebra and its applications , vol. 146, pp. 79–91, 1991
work page 1991
-
[62]
Matrix differential equations: A continuou s realization process for linear algebra problems,
M. T. Chu, “Matrix differential equations: A continuou s realization process for linear algebra problems,” Nonlinear analysis , vol. 18, pp. 1125–1146, 1992. COUTINO ET AL. STA TE-SPACE NETWORK TOPOLOGY IDENTIFICA TION FROM PARTIAL OBSERV A TIONS 17 IX. A PPENDIX A. Proof Theorem 2 We construct the proof of the convergence of the method with a rguments si...
work page 1992
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.