Directed Graph Topology Inference via Graph Filter Identification

Rasoul Shafipour ∗ , Andrei Buciulea ∗ , Member, IEEE , Santiago Segarra, Senior Member, IEEE, Antonio G. Marques, Senior Member, IEEE, and Gonzalo Mateos, Senior Member, IEEE · 2026

Read Directed Graph Topology Inference via Graph Filter Identification by Rasoul Shafipour ∗ , Andrei Buciulea ∗ , Member, IEEE , Santiago Segarra, Senior Member, IEEE, Antonio G. Marques, Senior Member, IEEE, and Gonzalo Mateos, Senior Member, IEEE (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-27455.txt.

Introduction

Shafipour leads a team inferring the wiring of a directed network from node measurements alone. Signals diffuse across the hidden graph through a graph filter, a polynomial of the graph's shift operator with unknown coefficients. Unlike classic undirected settings, the operator and the data covariance share no common basis, and input signals may be linked across nodes. The filter is pinned down first, from outputs plus input statistics. In 2026, the resulting equations are shown identifiable under spectral-diversity assumptions.

Optimisation over a Stiefel manifold solves it smoothly. Topology recovery then seeks a sparse shift that commutes with the identified filter. An alternating joint algorithm improves sample use by letting the two stages reinforce each other. Tests on test graphs and real data, including urban mobility and portfolio cases, confirm the recovery. Directed influence networks become readable from behaviour alone. Hidden wiring leaves readable traces.

Catalog record

CREATORRasoul Shafipour ∗ , Andrei Buciulea ∗ , Member, IEEE , Santiago Segarra, Senior Member, IEEE, Antonio G. Marques, Senior Member, IEEE, and Gonzalo Mateos, Senior Member, IEEE
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE95 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.27455

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Directed Graph Topology Inference via Graph Filter Identification ∗ The first two authors contributed equally. Work in this paper was supported in part by the NSF awards CCF-1750428 and CCF-2340481; the Spanish AEI (AEI/10.13039/501100011033) grant PID2022-136887NB-I00; and the Community of Madrid via IDEA-CM (TEC-2024/COM-89) and the Ellis Madrid Unit. R. Shafipour is with NVIDIA. A. Buciulea and A. G. Marques are with the Dept. of Signal Theory and Comms., King Juan Carlos University. S. Segarra is with the Dept. of Electrical and Computer Eng., Rice University. G. Mateos is with the Dept. of Electrical and Computer Eng., University of Rochester. Emails: [email protected], [email protected], [email protected], [email protected], and [email protected]. Part of the results in this paper were presented at the 2018 IEEE Data Science Workshop [ 35 ] . Rasoul Shafipour ∗ , Andrei Buciulea ∗ , Member, IEEE , Santiago Segarra, Senior Member, IEEE, Antonio G. Marques, Senior Member, IEEE, and Gonzalo Mateos, Senior Member, IEEE 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. I Introduction Machine learning and signal processing over graphs offer a rich toolbox for extracting actionable information from relational data. Upon modeling the data domain as a graph and the nodal observations at hand as graph signals, the graph signal processing (GSP) body of work has contributed innovative models that relate the properties of the signals with those of the graph, along with algorithms that fruitfully leverage graph-induced priors and inductive biases. Arguably, most early GSP efforts dealt with undirected networks. Such graphs are equivalently represented by symmetric matrices whose (well-behaved) spectral properties can be used to define transforms, convolutional operators, and even non-linear parametric architectures to learn from graph signals [ 24 , 13 ] . Their scarcer adoption notwithstanding, directed graph (digraph) models are more adequate (and, in fact, more accurate) for a number of applications. Information networks such as scientific citations or the Web itself are typically directed, and flows in technological (e.g., transportation, power, communication) networks are oftentimes one-directional. The presence of directionality plays a critical role when the measurements taken in those networks need to be processed to remove noise, outliers and artifacts, and this requires new tools and algorithms that do not rely on symmetric graph operators [ 32 , 20 ] . More abstractly, when the graph encodes (often unknown) relations between observed variables, directionality is vital to identify the nodes representing causes and their effects; see e.g., [ 27 ] . Beyond causal discovery, there is a need for methodological advances to tackle challenging digraph topology identification problems. I-A Recovering the Fundamental Structure of Signals Consider a network represented as a weighted digraph {\mathcal{G}} , with a node set {\mathcal{N}} of known cardinality N , and an edge set {\mathcal{E}} of ordered pairs of elements in {\mathcal{N}} . The edge weights A_{ij}\in{\mathbb{R}} such that A_{ij}\neq 0 for all (i,j)\in{\mathcal{E}} are collected in the (generally non-symmetric) adjacency matrix {\mathbf{A}} . As a more general algebraic descriptor of network structure, one can define a graph-shift operator (GSO) {\mathbf{S}}\in{\mathbb{R}}^{N\times N} as any matrix having the same sparsity pattern as that of {\mathcal{G}} [ 32 ] . Accordingly, {\mathbf{S}} can be viewed as a local diffusion operator. Our focus in this paper is on identifying digraphs that explain the structure of a random signal. Formally, let {\mathbf{y}}=[y_{1},...,y_{N}]^{\top}\in{\mathbb{R}}^{N} be a graph signal in which the i th element y_{i} denotes the signal value at node i of an unknown digraph {\mathcal{G}} with shift operator {\mathbf{S}} . Further suppose that we are given a zero-mean signal {\mathbf{x}} with covariance matrix {\mathbf{C}}_{\mathbf{x}}={\mathbb{E}}\left[{\mathbf{x}}{\mathbf{x}}^{\top}\right] . We say that the sparse digraph {\mathbf{S}} represents the structure of the signal {\mathbf{y}} if there exists a diffusion process in the GSO {\mathbf{S}} – modeled as a polynomial graph filter – that generates the observation {\mathbf{y}} from the input signal {\mathbf{x}} via linear filtering, i.e., \textstyle{\mathbf{y}}\ =\ \alpha_{0}\prod_{l=1}^{\infty}({\mathbf{I}}-\alpha_{l}{\mathbf{S}}){\mathbf{x}}\ =\ \big(\sum_{l=0}^{\infty}\beta_{l}{\mathbf{S}}^{l}\big)\,{\mathbf{x}}, (1) for some set of parameters \{\alpha_{l}\} , or equivalently \{\beta_{l}\} . While {\mathbf{S}} encodes only one-hop interactions, each successive application of the GSO in ( 1 ) percolates {\mathbf{x}} over {\mathcal{G}} . The justification to say that {\mathbf{S}} represents the structure of {\mathbf{y}} is that we can think of the edges of {\mathbf{S}} as direct (one-hop), directional relations between the elements of the signal. The diffusion described by ( 1 ) generates indirect relations, for instance, longer-range statistical dependencies in the covariance matrix {\mathbf{C}}_{\mathbf{y}}={\mathbb{E}}\left[{\mathbf{y}}{\mathbf{y}}^{\top}\right] . Our goal is to exploit this model to recover the fundamental relations described by {\mathbf{S}} from a set {\mathcal{Y}} of independent realizations of a random signal {\mathbf{y}} along with prior knowledge of {\mathbf{C}}_{\mathbf{x}} . The required statistical information about {\mathbf{x}} is the price paid to accommodate non-stationary processes {\mathbf{y}} with respect to (w.r.t.) (possibly) asymmetric GSOs [ 19 , 36 ] . I-B Paper Outline and Contributions In Section II , we formulate the problem of identifying a GSO that explains the fundamental structure of a random signal diffused on a digraph. We advocate an innovative two-step approach whereby: i) given independent output observations and prior information on the input statistics, we identify the graph convolutional filter; and ii) given the filter estimate along with structural constraints on the GSO, we recover the topology of the digraph via convex optimization. In Section III , we address the problem of identifying the diffusion filter [cf. i)], which entails solving a system of quadratic matrix equations formed using the available information on the input along with output signal measurements. We show that the set of feasible filters is related to the square roots of the observations’ covariance matrix, and that such a set is markedly larger than its counterpart for symmetric filters [ 36 ] . Conditions under which the system identification task admits a unique solution are derived as well (Section III-A ). Building on

Read the complete text