REVIEW 2 major objections 2 minor 44 references
Directed Graph Topology Inference via Graph Filter Identification
T0 review · 2 major / 2 minor · reviewed 2026-06-29 · grok-4.3
Pith's one-line read The diffusion filter is identifiable from output measurements and input covariance priors under spectral diversity assumptions on the inputs, enabling recovery of the directed graph topology via a sparse commuting shift.
desk verdict The paper extends filter-based topology inference to directed graphs with correlated inputs via quadratic identification plus a commuting sparse shift, plus a joint alternating algorithm. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The graph convolutional filter as a polynomial of the graph-shift operator, identified via quadratic equations under Stiefel manifold constraints, followed by finding a sparse commuting shift for topology inference.
What would settle it
A counterexample where two different graph filters produce identical output covariance matrices for the same set of input covariances would show the identifiability claim does not hold.
Extended reading notes
Core claim
We show that the diffusion filter, defined as a polynomial in the graph-shift operator, can be identified by solving quadratic matrix equations derived from output covariances and known input statistics, provided the input covariances satisfy spectral diversity. The network topology is then recovered by identifying a sparse admissible shift operator that commutes with the estimated filter.
Load-bearing premise
The input signal covariances must have sufficiently diverse spectra to ensure the quadratic equations uniquely determine the filter coefficients.
Editorial extensions
If this is right
- The topology of directed graphs can be inferred from nodal measurements without requiring white input excitations or joint diagonalizability of shift and covariance.
- A joint alternating algorithm between filter and topology steps achieves better sample complexity than separate identification.
- The method applies to real-world problems such as urban mobility analysis and portfolio optimization.
- Recovery succeeds when the estimated filter admits a sparse polynomial representation in the graph shift.
Reading between the lines
- If input covariances lack spectral diversity, multiple filters may fit the data, leading to ambiguity in topology recovery.
- The commuting condition could be relaxed or combined with other priors for graphs with additional structure.
- Tests on larger real networks could reveal scalability limits of the Stiefel-constrained optimization.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper addresses inferring directed graph topologies from nodal measurements generated by linear diffusion dynamics, modeled as a polynomial graph convolutional filter (with unknown coefficients) applied to a graph-shift operator, excited by an ensemble of independent but arbitrarily correlated input signals. It first identifies the diffusion filter from output measurements and input covariance priors by solving a system of quadratic matrix equations, shown to be identifiable under spectral-diversity assumptions on the input covariances; this is recast as smooth quadratic minimization on the Stiefel manifold. Topology recovery then reduces to finding a sparse, admissible shift operator that commutes with the estimated filter. A joint alternating algorithm is proposed to improve sample complexity, with numerical validation on synthetic digraphs and real-data applications including urban mobility and portfolio optimization.
Significance. If the identifiability result and commuting-shift recovery hold, the work extends graph topology inference to the directed case with correlated excitations, moving beyond the undirected/white-input settings common in prior literature. The spectral-diversity condition and manifold-constrained formulation provide a concrete route to filter identification, while the joint alternating scheme offers a practical improvement in sample efficiency. These elements, combined with the real-data case studies, position the contribution as relevant for network inference tasks in signal processing and machine learning.
major comments (2)
- [identifiability section] § on identifiability (around the quadratic matrix equations): the claim that spectral diversity on input covariances renders the system identifiable requires an explicit uniqueness argument showing that distinct filter coefficient vectors cannot produce the same output covariances under the given assumptions; without this step-by-step derivation or a supporting lemma, the transition from the quadratic equations to unique recovery remains unverified in the provided text.
- [topology recovery] Topology recovery paragraph (commuting shift step): the assertion that a sparse admissible shift commuting with the estimated filter uniquely recovers the graph-shift operator needs a supporting argument or counter-example exclusion showing that no other admissible sparse operators satisfy the commutativity condition; this step is load-bearing for the end-to-end claim but currently lacks explicit verification beyond the standard polynomial-in-shift property.
minor comments (2)
- [abstract] The abstract and introduction would benefit from a brief statement of the precise spectral-diversity condition (e.g., distinct eigenvalues or rank conditions on the input covariance matrices) to make the identifiability claim immediately checkable.
- [numerical tests] Numerical experiments section: reporting the exact number of Monte Carlo trials, the range of sample sizes tested, and quantitative metrics (e.g., edge recovery F1 or normalized error) for both the filter identification and topology recovery stages would strengthen reproducibility.
Simulated Author's Rebuttal
We thank the referee for the constructive feedback and detailed review of our manuscript. We address each major comment point by point below, providing clarifications and indicating where revisions will be made to strengthen the presentation.
read point-by-point responses
-
Referee: [identifiability section] § on identifiability (around the quadratic matrix equations): the claim that spectral diversity on input covariances renders the system identifiable requires an explicit uniqueness argument showing that distinct filter coefficient vectors cannot produce the same output covariances under the given assumptions; without this step-by-step derivation or a supporting lemma, the transition from the quadratic equations to unique recovery remains unverified in the provided text.
Authors: We appreciate the referee's observation. The manuscript derives identifiability by showing that the system of quadratic matrix equations admits a unique solution for the filter coefficients when the input covariances satisfy the spectral-diversity condition, as the distinct eigenvalues prevent different coefficient vectors from yielding identical output covariances. However, we agree that an explicit step-by-step uniqueness argument would improve clarity and verifiability. In the revised version we will insert a supporting lemma immediately after the quadratic equations that formally proves uniqueness under the stated assumptions, including the necessary algebraic steps. revision: yes
-
Referee: [topology recovery] Topology recovery paragraph (commuting shift step): the assertion that a sparse admissible shift commuting with the estimated filter uniquely recovers the graph-shift operator needs a supporting argument or counter-example exclusion showing that no other admissible sparse operators satisfy the commutativity condition; this step is load-bearing for the end-to-end claim but currently lacks explicit verification beyond the standard polynomial-in-shift property.
Authors: We thank the referee for this comment. The topology recovery step relies on the fact that any admissible sparse shift commuting with the estimated filter must be a polynomial in the true graph-shift operator, combined with the structural constraints (sparsity and admissibility) to enforce uniqueness. While the polynomial-in-shift property is standard, we acknowledge that an explicit argument excluding other candidate sparse commuting operators would make the claim more rigorous. We will add a short proposition in the topology-recovery section that shows, under the problem assumptions, no other admissible sparse operator satisfies the commutativity condition. revision: yes
Circularity Check
No significant circularity
full rationale
The derivation proceeds from external output measurements and input covariance priors to identify the diffusion filter via a system of quadratic equations shown identifiable under spectral-diversity assumptions on those priors; topology recovery then applies the independent structural constraint that the shift must commute with the recovered filter (forcing it to be a polynomial in the shift). No step reduces by construction to a fitted parameter renamed as prediction, a self-citation chain, or a self-definitional loop; the commuting condition is a standard algebraic consequence of the polynomial filter model rather than an ansatz or fitted input. The paper is therefore self-contained against its stated external data and assumptions.
Assumptions & free parameters
assumptions (2)
- domain assumption Observations are outputs of a graph convolutional filter (polynomial in the graph-shift operator) excited by independent graph signals with arbitrarily correlated nodal components.
- domain assumption Spectral-diversity assumptions on the input covariances render the quadratic matrix equations identifiable.
Cite this review
Pith. "Pith review of Directed Graph Topology Inference via Graph Filter Identification." pith.science (2026). https://pith.science/paper/SIZF7M3A
@misc{pith2026260627455,
author = {Pith},
title = {Pith review of: Directed Graph Topology Inference via Graph Filter Identification},
year = {2026},
howpublished = {\url{https://pith.science/paper/SIZF7M3A}},
note = {Machine review of arXiv:2606.27455}
}
read the original abstract
We address the problem of inferring a directed network from nodal measurements generated by linear diffusion dynamics on the sought graph. Observations are modeled as the outputs of a graph convolutional filter, i.e., a polynomial (with unknown coefficients) of a local diffusion graph-shift operator encoding the latent graph topology, excited with an ensemble of independent graph signals with arbitrarily-correlated nodal components. Unlike prior efforts that considered undirected graphs and white signal excitations, here the graph-shift operator and the observations' covariance matrix are not simultaneously diagonalizable. In this challenging context, we first rely on measurements of the output signals along with prior statistical information on the inputs to identify the diffusion filter. Such system identification problem involves solving a system of quadratic matrix equations, which we show is identifiable under spectral-diversity assumptions on the input covariances. For algorithmic purposes we recast it as a smooth quadratic minimization subject to Stiefel manifold constraints. Subsequent identification of the network topology given the graph filter estimate boils down to finding a sparse and structurally admissible shift that commutes with the given filter, thus, forcing the latter to be a polynomial in the sought graph-shift operator. A joint graph filter and topology identification algorithm is also proposed, which alternates between the aforementioned steps in a mutually reinforcing fashion to offer improved sample complexity. Numerical tests corroborate the effectiveness of the proposed algorithms in recovering synthetic digraphs and real-data case studies, and illustrate their potential utility on urban mobility analyses as well as portfolio optimization.
Figures
Figures from the paper (2 more)
Reference graph
Works this paper leans on
-
[1]
Directed network topology inference via graph filter identification,
R. Shafipour, S. Segarra, A. G. Marques, and G. Mateos, “Directed network topology inference via graph filter identification,” inIEEE Data Science Wrkshp. (DSW), Lausanne, Switzerland, Jun. 4-6, 2018
2018
-
[2]
Graph signal processing: Overview, challenges, and ap- plications,
A. Ortega, P. Frossard, J. Kova ˇcevi´c, J. M. F. Moura, and P. Van- dergheynst, “Graph signal processing: Overview, challenges, and ap- plications,”Proc. IEEE, vol. 106, no. 5, pp. 808–828, 2018
2018
-
[3]
Graphs, convolutions, and neural networks: From graph filters to graph neural networks,
F. Gama, E. Isufi, G. Leus, and A. Ribeiro, “Graphs, convolutions, and neural networks: From graph filters to graph neural networks,”IEEE Signal Process. Mag., vol. 37, no. 6, pp. 128–138, 2020
2020
-
[4]
Discrete signal processing on graphs,
A. Sandryhaila and J. Moura, “Discrete signal processing on graphs,” IEEE Trans. Signal Process., vol. 61, no. 7, pp. 1644–1656, Apr. 2013
2013
-
[5]
Signal processing on directed graphs,
A. G. Marques, S. Segarra, and G. Mateos, “Signal processing on directed graphs,”IEEE Signal Process. Mag., vol. 37, no. 6, pp. 99– 116, Nov. 2020
2020
-
[6]
Peters, D
J. Peters, D. Janzing, and B. Sch ¨olkopf,Elements of Causal Inference: Foundations and Learning Algorithms. MIT Press, 2017
2017
-
[7]
Stationary graph processes and spectral estimation,
A. G. Marques, S. Segarra, G. Leus, and A. Ribeiro, “Stationary graph processes and spectral estimation,”IEEE Trans. Signal Process., vol. 65, no. 22, pp. 5911–5926, Aug. 2017
2017
-
[8]
Identifying the topology of undirected networks from diffused non-stationary graph signals,
R. Shafipour, S. Segarra, A. G. Marques, and G. Mateos, “Identifying the topology of undirected networks from diffused non-stationary graph signals,”IEEE Open J. Signal Process., vol. 2, pp. 171–189, Mar. 2021
2021
Show all 44 references
-
[9]
Boumal,An Introduction to Optimization on Smooth Manifolds
N. Boumal,An Introduction to Optimization on Smooth Manifolds. Cambridge University Press, 2023
2023
-
[10]
Topology identi- fication and learning over graphs: Accounting for nonlinearities and dynamics,
G. B. Giannakis, Y . Shen, and G. V . Karanikolas, “Topology identi- fication and learning over graphs: Accounting for nonlinearities and dynamics,”Proc. IEEE, vol. 106, no. 5, pp. 787–807, 2018
2018
-
[11]
Connecting the dots: Identifying network structure via graph signal processing,
G. Mateos, S. Segarra, A. G. Marques, and A. Ribeiro, “Connecting the dots: Identifying network structure via graph signal processing,”IEEE Signal Process. Mag., vol. 36, no. 3, pp. 16–43, May 2019
2019
-
[12]
Disentangling neurodegeneration with brain age gap prediction models: A graph signal processing perspective,
S. Sihag, G. Mateos, and A. Ribeiro, “Disentangling neurodegeneration with brain age gap prediction models: A graph signal processing perspective,”IEEE Signal Process. Mag., vol. 42, no. 4, pp. 58–77, Jul. 2025
2025
-
[13]
E. D. Kolaczyk,Statistical Analysis of Network Data: Methods and Models. New York, NY: Springer, 2009
2009
-
[14]
Sparse inverse covariance estimation with the graphical lasso,
J. Friedman, T. Hastie, and R. Tibshirani, “Sparse inverse covariance estimation with the graphical lasso,”Biostatistics, vol. 9, no. 3, pp. 432– 441, 2008
2008
-
[15]
Proximal-gradient algorithms for tracking cascades over social networks,
B. Baingana, G. Mateos, and G. B. Giannakis, “Proximal-gradient algorithms for tracking cascades over social networks,”IEEE J. Sel. Topics Signal Process., vol. 8, pp. 563–575, Aug. 2014
2014
-
[16]
Tensor decompositions for identifying directed graph topologies and tracking dynamic networks,
Y . Shen, B. Baingana, and G. B. Giannakis, “Tensor decompositions for identifying directed graph topologies and tracking dynamic networks,” IEEE Trans. Signal Process., vol. 65, no. 14, pp. 3675–3687, Jul. 2017
2017
-
[17]
Topology identification of directed graphs via joint diagonalization of correlation matrices,
Y . Shen, X. Fu, G. B. Giannakis, and N. D. Sidiropoulos, “Topology identification of directed graphs via joint diagonalization of correlation matrices,”IEEE Trans. Signal Inf. Process. Netw., vol. 6, pp. 271–283, 2020
2020
-
[18]
A covariance matching approach to graph topology identification,
Y . Han, R. T. Rajan, and G. Leus, “A covariance matching approach to graph topology identification,”arXiv preprint arXiv:2601.15999 [eess.SP], 2026
2026
-
[19]
DAGs with NO TEARS: Continuous optimization for structure learning,
X. Zheng, B. Aragam, P. K. Ravikumar, and E. P. Xing, “DAGs with NO TEARS: Continuous optimization for structure learning,”Advances Neural Inf. Process. Syst., vol. 31, 2018
2018
-
[20]
CoLiDE: Concomitant linear DAG estimation,
S. S. Saboksayr, G. Mateos, and M. Tepper, “CoLiDE: Concomitant linear DAG estimation,”Intl. Conf. Learn. Repr., 2024
2024
-
[21]
Beta oscillations in a large-scale sensorimotor cortical net- work: Directional influences revealed by Granger causality,
A. Brovelli, M. Ding, A. Ledberg, Y . Chen, R. Nakamura, and S. L. Bressler, “Beta oscillations in a large-scale sensorimotor cortical net- work: Directional influences revealed by Granger causality,”PNAS, vol. 101, pp. 9849–9854, 2004
2004
-
[22]
Learning Laplacian matrix in smooth graph signal representations,
X. Dong, D. Thanou, P. Frossard, and P. Vandergheynst, “Learning Laplacian matrix in smooth graph signal representations,”IEEE Trans. Signal Process., vol. 64, no. 23, pp. 6160–6173, Aug. 2016
2016
-
[23]
Signal processing on graphs: Causal modeling of unstructured data,
J. Mei and J. M. F. Moura, “Signal processing on graphs: Causal modeling of unstructured data,”IEEE Trans. Signal Process., vol. 65, no. 8, pp. 2077–2092, Apr. 2017
-
[24]
How to learn a graph from smooth signals,
V . Kalofolias, “How to learn a graph from smooth signals,” inIntl. Conf. Artif. Intel. Stat. (AISTATS). J Mach. Learn. Res., 2016, pp. 920–929
2016
-
[25]
Network topology inference from spectral templates,
S. Segarra, A. Marques, G. Mateos, and A. Ribeiro, “Network topology inference from spectral templates,”IEEE Trans. Signal Inf. Process. Netw., vol. 3, no. 3, pp. 467–483, Aug. 2017
2017
-
[26]
Characterization and inference of graph diffusion processes from ob- servations of stationary signals,
B. Pasdeloup, V . Gripon, G. Mercier, D. Pastor, and M. G. Rabbat, “Characterization and inference of graph diffusion processes from ob- servations of stationary signals,”IEEE Trans. Signal Inf. Process. Netw., vol. 4, no. 3, pp. 481–496, 2017
2017
-
[27]
Learning heat diffusion graphs,
D. Thanou, X. Dong, D. Kressner, and P. Frossard, “Learning heat diffusion graphs,”IEEE Trans. Signal Inf. Process. Netw., vol. 3, no. 3, pp. 484–499, Sept 2017
2017
-
[28]
Learning graphs from data: A signal representation perspective,
X. Dong, D. Thanou, M. Rabbat, and P. Frossard, “Learning graphs from data: A signal representation perspective,”IEEE Signal Process. Mag., vol. 36, no. 3, pp. 44–63, 2019
2019
-
[29]
Learning graphs from smooth and graph-stationary signals with hidden variables,
A. Buciulea, S. Rey, and A. G. Marques, “Learning graphs from smooth and graph-stationary signals with hidden variables,”IEEE Trans. Signal Inf. Process. Netw., vol. 8, pp. 273–287, 2022
2022
-
[30]
Online discriminative graph learning from multi-class smooth signals,
S. S. Saboksayr, G. Mateos, and M. Cetin, “Online discriminative graph learning from multi-class smooth signals,”Signal Processing, vol. 186, p. 108101, 2021
2021
-
[31]
Accelerated graph learning from smooth signals,
S. S. Saboksayr and G. Mateos, “Accelerated graph learning from smooth signals,”IEEE Signal Process. Lett., vol. 28, pp. 2192–2196, 2021
2021
-
[32]
Inferring directed network topologies via tensor factorization,
Y . Shen, B. Baingana, and G. B. Giannakis, “Inferring directed network topologies via tensor factorization,” inAsilomar Conf. on Signals, Systems, and Computers, Pacific Grove, CA, Nov. 6-9, 2016
2016
-
[33]
Network topology inference from non-stationary graph signals,
R. Shafipour, S. Segarra, A. G. Marques, and G. Mateos, “Network topology inference from non-stationary graph signals,” inIEEE Intl. Conf. Acoust., Speech and Signal Process. (ICASSP), New Orleans, LA, Mar. 5-9, 2017
2017
-
[34]
Block coordinate descent on smooth mani- folds: Convergence theory and twenty-one examples,
L. Peng and R. Vidal, “Block coordinate descent on smooth mani- folds: Convergence theory and twenty-one examples,”arXiv preprint arXiv:2305.14744 [math.OC], 2023
2023
-
[35]
Robust graph filter identification and graph denoising from signal observations,
S. Rey, V . M. Tenorio, and A. G. Marqu ´es, “Robust graph filter identification and graph denoising from signal observations,”IEEE Trans. Signal Process., vol. 71, pp. 3651–3666, 2023
2023
-
[36]
Online topology inference from streaming stationary graph signals with partial connectivity information,
R. Shafipour and G. Mateos, “Online topology inference from streaming stationary graph signals with partial connectivity information,”Algo- rithms, vol. 13, no. 9, 2020
2020
-
[37]
Joint inference of multiple graphs from matrix polynomials,
M. Navarro, Y . Wang, A. G. Marques, C. Uhler, and S. Segarra, “Joint inference of multiple graphs from matrix polynomials,”J. Mach. Learn. Res., vol. 23, no. 1, Jan. 2022
2022
-
[38]
Logspect: Feasible graph learning model from stationary signals with recovery guarantees,
S. Liu, L. Zhu, and A. M.-C. So, “Logspect: Feasible graph learning model from stationary signals with recovery guarantees,” inAdvances Neural Inf. Process. Syst., vol. 36, 2023, pp. 80 142–80 164
2023
-
[39]
Projection onto a simplex,
Y . Chen and X. Ye, “Projection onto a simplex,”arXiv preprint arXiv:1101.6081, 2011
2011 arXiv
-
[40]
H. H. Bauschke, P. L. Combetteset al.,Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, 2011, vol. 408
2011
-
[41]
Proximal alternating linearized minimization for nonconvex and nonsmooth problems,
J. Bolte, S. Sabach, and M. Teboulle, “Proximal alternating linearized minimization for nonconvex and nonsmooth problems,”Math. Program., vol. 146, no. 1–2, pp. 459–494, 2014
2014
-
[42]
On Kruskal’s uniqueness condi- tion for the CAMDECOMP/PARAFAC decomposition,
A. Stegeman and N. D. Sidiropoulos, “On Kruskal’s uniqueness condi- tion for the CAMDECOMP/PARAFAC decomposition,”Linear Algebra Appl., vol. 420, no. 2, pp. 540–552, Jan. 2007
2007
-
[43]
Global rates of convergence for nonconvex optimization on manifolds,
N. Boumal, P.-A. Absil, and C. Cartis, “Global rates of convergence for nonconvex optimization on manifolds,”IMA J. Numerical Analysis, vol. 39, no. 1, pp. 1–33, 2019
2019
-
[44]
Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward–backward splitting, and regularized Gauss–Seidel methods,
H. Attouch, J. Bolte, and B. F. Svaiter, “Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward–backward splitting, and regularized Gauss–Seidel methods,” Math. Program., vol. 137, no. 1–2, pp. 91–129, 2013. 14 SUPPLEMENTARYMATERIAL ...
2013
Reviewed June 29, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.