Directed Graph Topology Inference via Graph Filter Identification

• URL: http://arxiv.org/abs/2606.27455v1
• Date: Thu, 25 Jun 2026 18:25:57 GMT
• Title: Directed Graph Topology Inference via Graph Filter Identification
• Abstract summary: We address the problem of inferring a directed network from nodal measurements generated by a graph convolutional filter.<n>A joint graph filter and topology identification algorithm is also proposed, which alternates between the aforementioned steps to offer improved sample complexity.
• Score: 54.541275287889164
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Generative Diffusion Models of Stochastic Graph Signals [74.4097723209053]
  This paper tackles problems of conditional graph signal generative modeling and tackles them with a single denoising diffusion framework.<n>We learn a reverse diffusion process, parametrized by graph neural networks (GNNs), that draws graph signals conditioned directly on the graph topology and on node-feature side information.<n>We demonstrate our method on two generative tasks: stock price forecasting and optimal wireless resource allocation, with extensive numerical results in both domains.
  arXiv  Detail & Related papers  (2026-07-07T22:02:13Z)
• Grassmanian Interpolation of Low-Pass Graph Filters: Theory and Applications [13.83778274369268]
  Low-pass graph filters are fundamental for signal processing on graphs and other non-Euclidean domains.<n>We suggest a novel algorithm of low-pass graph filter based on Riemannian coordinates in normal coordinates on the Grassmann manifold.<n>We argue that the temporal evolution of the node features may be translated to the evolving graph via a similarity correction to adjust the homophily degree of the network.<n>Second, we suggest a dot product graph family induced by a given static graph which allows to infer improved message passing scheme for node classification facilitated by the filter topology.
  arXiv  Detail & Related papers  (2025-10-27T11:40:14Z)
• A Spectral Interpretation of Redundancy in a Graph Reservoir [51.40366905583043]
  This work revisits the definition of the reservoir in the Multiresolution Reservoir Graph Neural Network (MRGNN)<n>It proposes a variant based on a Fairing algorithm originally introduced in the field of surface design in computer graphics.<n>The core contribution of the paper lies in the theoretical analysis of the algorithm from a random walks perspective.
  arXiv  Detail & Related papers  (2025-07-17T10:02:57Z)
• Signed Graph Learning: Algorithms and Theory [17.374356596021936]
  Real-world data is often represented through the relationships between data samples, forming a graph structure.<n>Current graph learning research has primarily focused on unsigned graphs.<n>We develop a method for capturing a set of smooth signed graph signals.
  arXiv  Detail & Related papers  (2025-07-13T17:33:26Z)
• Diffusion Maps for Signal Filtering in Graph Learning [0.0]
  The paper showcases the effectiveness of this approach through examples involving synthetically generated and real-world temperature sensor data. The results provide new approaches for the analysis and understanding of complex, non-Euclidean data structures.
  arXiv  Detail & Related papers  (2023-12-22T15:17:44Z)
• Supercharging Graph Transformers with Advective Diffusion [28.40109111316014]
  This paper proposes Advective Diffusion Transformer (AdvDIFFormer), a physics-inspired graph Transformer model designed to address this challenge.<n>We show that AdvDIFFormer has provable capability for controlling generalization error with topological shifts.<n> Empirically, the model demonstrates superiority in various predictive tasks across information networks, molecular screening and protein interactions.
  arXiv  Detail & Related papers  (2023-10-10T08:40:47Z)
• Representing Edge Flows on Graphs via Sparse Cell Complexes [6.74438532801556]
  We introduce the flow representation learning problem, i.e., the problem of augmenting the observed graph by a set of cells. We show that this problem is NP-hard and introduce an efficient approximation algorithm for its solution.
  arXiv  Detail & Related papers  (2023-09-04T14:30:20Z)
• Geometric Graph Filters and Neural Networks: Limit Properties and Discriminability Trade-offs [122.06927400759021]
  We study the relationship between a graph neural network (GNN) and a manifold neural network (MNN) when the graph is constructed from a set of points sampled from the manifold. We prove non-asymptotic error bounds showing that convolutional filters and neural networks on these graphs converge to convolutional filters and neural networks on the continuous manifold.
  arXiv  Detail & Related papers  (2023-05-29T08:27:17Z)
• Multilayer Clustered Graph Learning [66.94201299553336]
  We use contrastive loss as a data fidelity term, in order to properly aggregate the observed layers into a representative graph. Experiments show that our method leads to a clustered clusters w.r.t. We learn a clustering algorithm for solving clustering problems.
  arXiv  Detail & Related papers  (2020-10-29T09:58:02Z)
• Joint Inference of Multiple Graphs from Matrix Polynomials [34.98220454543502]
  Inferring graph structure from observations on the nodes is an important and popular network science task. We study the problem of jointly inferring multiple graphs from the observation of signals at their nodes. We propose a convex optimization method along with sufficient conditions that guarantee the recovery of the true graphs.
  arXiv  Detail & Related papers  (2020-10-16T02:45:15Z)
• Offline detection of change-points in the mean for stationary graph signals [55.98760097296213]
  We propose an offline method that relies on the concept of graph signal stationarity. Our detector comes with a proof of a non-asymptotic inequality oracle.
  arXiv  Detail & Related papers  (2020-06-18T15:51:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.