📊 statistics

Directed Graph Topology Inference via Graph Filter Identification

This paper proposes a novel framework for inferring directed graph topologies from nodal measurements generated by linear diffusion dynamics by first identifying a graph convolutional filter through quadratic matrix equations and then recovering the sparse graph-shift operator that commutes with the filter, a method validated on both synthetic and real-world datasets.

Original authors: Rasoul Shafipour, Andrei Buciulea, Santiago Segarra, Antonio G. Marques, Gonzalo Mateos

Published 2026-06-29

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Rasoul Shafipour, Andrei Buciulea, Santiago Segarra, Antonio G. Marques, Gonzalo Mateos

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to figure out the layout of a secret, one-way street system in a city you've never visited. You can't see the roads, and you don't have a map. All you have are a bunch of "tracers" (like smoke or dye) that you release into the system at different times, and you watch where they end up.

This paper is about a new mathematical method to reverse-engineer that hidden map of one-way streets (a directed graph) just by watching how things flow through it.

Here is the breakdown of their approach, using simple analogies:

The Core Problem: The "Black Box" City

In many real-world networks—like how information spreads on the internet, how traffic moves in a city, or how stock prices influence each other—the connections are one-way. A tweet from Person A might influence Person B, but not the other way around.

The authors want to find these one-way connections. They assume the network works like a diffusion machine:

You put in some "input" (like a rumor or a stock trade).
The network processes it through a series of steps (like a filter).
You get an "output" (the rumor spreading or the stock price changing).

The challenge is: You know the input and the output, but you don't know the machine (the network map) or the recipe (the filter) inside the machine.

The Two-Step Detective Work

The authors propose a clever two-step strategy to solve this puzzle.

Step 1: Reverse-Engineering the "Recipe" (The Filter)

First, they ignore the map and try to figure out the recipe the machine uses to turn input into output.

The Analogy: Imagine you are trying to figure out a chef's secret sauce recipe. You don't know the ingredients (the map), but you have many different batches of soup (inputs) and you taste the final result (outputs).
The Trick: The paper says if you use enough different types of soup ingredients (statistically diverse inputs), you can mathematically deduce the exact recipe (the graph filter) that was used, even if you don't know the kitchen layout yet. They treat this as a complex math puzzle involving "manifolds" (which is just a fancy way of saying they are navigating a curved mathematical space to find the best fit).

Step 2: Finding the "Map" (The Topology)

Once they have the recipe (the filter), they use it to find the actual roads (the network topology).

The Analogy: Now that you know the sauce recipe, you look at the kitchen to see which pots and pans (nodes) are connected by which pipes (edges).
The Rule: The recipe must be consistent with the pipes. If the recipe says "mix A and B," there must be a pipe connecting A to B. The authors look for the simplest map (the one with the fewest pipes) that makes the recipe work. They also ensure the pipes only go one way, matching the real-world nature of the data.

The "Closed-Loop" Upgrade

The paper introduces a "Pro" version of this method called Joint Identification.

The Analogy: Instead of doing Step 1 then Step 2 separately, imagine a detective who constantly updates their theory. "Okay, I think the map looks like this, so the recipe must be that. But wait, if the recipe is that, maybe the map is actually this."
They let the two steps talk to each other. The map estimate helps refine the recipe, and the recipe estimate helps refine the map. This "feedback loop" allows them to solve the puzzle with fewer samples (less data) than doing it the old way.

Real-World Tests

The authors didn't just do math on paper; they tested their "detective work" on real data:

New York City Traffic: They used Uber pickup data to map how people move between neighborhoods.
- Result: Their method correctly identified that traffic flows out of Manhattan toward airports and residential areas in the evening, and flows in from other boroughs in the morning. Older methods that assumed two-way streets (like a roundabout) missed these crucial one-way patterns.
Stock Market: They used stock prices to see how companies influence each other.
- Result: They built a portfolio of stocks based on their inferred map. Because their map was more accurate at capturing who influences whom, the resulting investment portfolio made more money than portfolios built using older, less accurate maps.

Why This Matters

Previous methods mostly worked for "two-way" relationships (like a friendship where A likes B and B likes A). This paper provides the first robust toolkit for figuring out one-way relationships (like a boss giving orders to an employee, or a virus spreading from person A to B).

In short: They invented a way to look at the "before" and "after" of a complex system and mathematically reconstruct the invisible, one-way roads that connect it, using a feedback loop to get the answer faster and more accurately.

Technical Summary: Directed Graph Topology Inference via Graph Filter Identification

Problem Statement
The paper addresses the challenge of inferring the topology of a directed graph (digraph) from nodal measurements generated by linear diffusion dynamics. Unlike prior work focused on undirected graphs with white signal excitations, this problem considers a general setting where:

The underlying network is a directed graph with a non-symmetric graph-shift operator (GSO), $S$ .
The observed signals, $y$ , are generated by a graph convolutional filter (a polynomial of $S$ ) acting on input signals, $x$ .
The input signals are not necessarily white; they possess arbitrary correlations described by known covariance matrices $C_{x,m}$ .
The filter coefficients and the graph structure are unknown.

The core difficulty arises because, for directed graphs, the GSO and the observation covariance matrix are not simultaneously diagonalizable, rendering standard spectral-based approaches for undirected graphs inapplicable. The goal is to recover the sparsest valid GSO $S$ that explains the observed data given prior statistical knowledge of the inputs.

Methodology
The authors propose a two-step inference framework, followed by a joint optimization approach to improve sample complexity.

Step 1: Asymmetric Diffusion Filter Identification
- Formulation: The problem is modeled as a system of quadratic matrix equations: $C_{y,m} = H C_{x,m} H^\top$ , where $H$ is the unknown filter and $C_{y,m}$ is the estimated output covariance.
- Identifiability: The authors establish that the filter $H$ is identifiable (up to sign ambiguity) if the input covariances exhibit sufficient spectral diversity. Specifically, Theorem 1 proves that with $M=4$ processes, uniqueness is guaranteed if the input eigenbases are sufficiently distinct and eigenvalues satisfy specific Kruskal-rank conditions.
- Algorithm: To solve this non-convex system, the problem is recast as a smooth quadratic minimization subject to Stiefel manifold constraints (orthogonality constraints on rotation matrices). An Inexact Alternating Minimization (IAM) algorithm is developed, utilizing Riemannian gradient descent for the manifold-constrained variables and closed-form updates for the filter $H$ .
Step 2: Digraph Topology Inference
- Formulation: Given the estimated filter $\hat{H}$ , the goal is to find a sparse GSO $S$ such that $HS = SH$ (commutativity), ensuring $H$ is a polynomial in $S$ .
- Algorithm: The authors formulate this as a convex $\ell_1$ -norm minimization problem with a relaxed commutativity constraint. A Proximal Gradient (PG) algorithm is employed, which efficiently handles the sparsity constraint and the structural constraints (e.g., non-negative weights, no self-loops) via a custom proximal operator.
Joint Identification (Closed-Loop)
- To improve performance, the authors propose a joint formulation that alternates between filter identification and topology inference. This "closed-loop" approach uses the current estimate of $S$ to regularize the filter estimation and vice versa.
- Convergence: A provably convergent algorithm (Algorithm 3) is presented, which alternates between Proximal Gradient steps for $S$ , Riemannian gradient steps for the manifold variables, and Euclidean gradient steps for $H$ . Theoretical analysis confirms convergence to a critical point under mild assumptions.

Key Contributions

Generalization to Directed Graphs: The work extends graph filter identification from symmetric (undirected) to asymmetric (directed) operators, addressing the non-diagonalizability of the GSO and output covariance.
Identifiability Theory: The paper provides rigorous conditions (Theorem 1) under which an asymmetric diffusion filter is uniquely identifiable from second-order statistics of multiple input-output processes, highlighting the necessity of spectral diversity in inputs.
Novel Algorithms:
- An IAM algorithm for filter identification on the Stiefel manifold.
- A Proximal Gradient method for recovering sparse directed topologies.
- A joint, closed-loop algorithm that mutually reinforces filter and topology estimation.
Convergence Guarantees: The paper provides a convergence analysis for the joint non-convex problem involving $\ell_1$ -sparsity, manifold constraints, and commutativity coupling, utilizing the Kurdyka–Łojasiewicz (KL) property.

Experimental Results
The proposed methods were evaluated on synthetic data and real-world case studies:

Synthetic Data: Experiments on Erdős–Rényi, Barabási–Albert, and Stochastic Block Model graphs demonstrate that the closed-loop (joint) approach significantly outperforms the open-loop (two-step) approach, particularly when the number of input processes ( $M$ ) or samples ( $P$ ) is limited. The joint method achieves near-perfect support recovery with fewer samples than the open-loop method.
Real-World Data (Urban Mobility): Applied to Uber pickup data in New York City, the algorithm inferred a directed mobility graph. Unlike undirected models, the proposed method captured asymmetric traffic flows, correctly identifying dominant outbound flows from Manhattan to residential boroughs and airports, consistent with evening commute patterns.
Real-World Data (Portfolio Optimization): In a financial application using stock data, graphs inferred by the proposed method led to portfolios with significantly higher returns compared to baselines (GFI, TITD) and uniform allocation, under both inverse-degree and inverse-eigenvector centrality weighting strategies.

Significance and Claims
The paper claims that its primary significance lies in providing a unified framework for directed network topology inference that does not rely on the restrictive assumption of graph stationarity (which implies symmetry). By leveraging the structural relationship between graph filters and shift operators, the method recovers the fundamental causal or directional relations in a network.

The authors note that while the approach is effective, it comes with trade-offs: it requires multiple input processes to ensure identifiability and involves cubic computational complexity ( $O(N^3)$ ) per iteration. The paper positions itself as a methodological advance for applications where directionality is critical, such as causal discovery, transportation networks, and financial dependency modeling, offering a more accurate alternative to symmetric graph learning tools.