Semi-Blind inference of topologies and dynamical processes over dynamic graphs

Vassilis N. Ioannidis, Yanning Shen, Georgios B. Giannakis

Research output: Contribution to journalArticle

1 Citation (Scopus)

Abstract

A task of major practical importance in network science is inferring the graph structure from noisy observations at a subset of nodes. Available methods for topology inference typically assume that the process over the network is observed at all nodes. However, application-specific constraints may prevent acquiring network-wide observations. Alleviating the limited flexibility of existing approaches, this work advocates structural models for graph processes and develops novel algorithms for joint inference of the network topology and processes from partial nodal observations. Structural equation models (SEMs) and structural vector autoregressive models (SVARMs) have well documented merits in identifying even directed topologies of complex graphs; while SEMs capture contemporaneous causal dependencies among nodes, SVARMs further account for time-lagged influences. A batch solver is proposed that iterates between inferring directed graphs that 'best' fit the sequence of observations, and estimating the network processes at reduced computational complexity by leveraging tools related to Kalman smoothing. To further accommodate delay-sensitive applications, an online joint inference approach is put forth that even tracks time-evolving topologies. Furthermore, we specify novel conditions for identifying the network topology given partial observations. We prove that the required number of observations for unique identification reduces significantly when the network structure is sparse. Numerical tests with synthetic as well as real datasets corroborate the effectiveness of the proposed approach.

Original languageEnglish (US)
Article number8662630
Pages (from-to)2263-2274
Number of pages12
JournalIEEE Transactions on Signal Processing
Volume67
Issue number9
DOIs
StatePublished - May 1 2019

Fingerprint

Topology
Directed graphs
Set theory
Computational complexity

Keywords

  • Directed graphs
  • Graph signal reconstruction
  • Structural (vector) equation models
  • Topology inference

Cite this

Semi-Blind inference of topologies and dynamical processes over dynamic graphs. / Ioannidis, Vassilis N.; Shen, Yanning; Giannakis, Georgios B.

In: IEEE Transactions on Signal Processing, Vol. 67, No. 9, 8662630, 01.05.2019, p. 2263-2274.

Research output: Contribution to journalArticle

@article{45bce942353e490db27fc2069ef5210a,
title = "Semi-Blind inference of topologies and dynamical processes over dynamic graphs",
abstract = "A task of major practical importance in network science is inferring the graph structure from noisy observations at a subset of nodes. Available methods for topology inference typically assume that the process over the network is observed at all nodes. However, application-specific constraints may prevent acquiring network-wide observations. Alleviating the limited flexibility of existing approaches, this work advocates structural models for graph processes and develops novel algorithms for joint inference of the network topology and processes from partial nodal observations. Structural equation models (SEMs) and structural vector autoregressive models (SVARMs) have well documented merits in identifying even directed topologies of complex graphs; while SEMs capture contemporaneous causal dependencies among nodes, SVARMs further account for time-lagged influences. A batch solver is proposed that iterates between inferring directed graphs that 'best' fit the sequence of observations, and estimating the network processes at reduced computational complexity by leveraging tools related to Kalman smoothing. To further accommodate delay-sensitive applications, an online joint inference approach is put forth that even tracks time-evolving topologies. Furthermore, we specify novel conditions for identifying the network topology given partial observations. We prove that the required number of observations for unique identification reduces significantly when the network structure is sparse. Numerical tests with synthetic as well as real datasets corroborate the effectiveness of the proposed approach.",
keywords = "Directed graphs, Graph signal reconstruction, Structural (vector) equation models, Topology inference",
author = "Ioannidis, {Vassilis N.} and Yanning Shen and Giannakis, {Georgios B.}",
year = "2019",
month = "5",
day = "1",
doi = "10.1109/TSP.2019.2903025",
language = "English (US)",
volume = "67",
pages = "2263--2274",
journal = "IEEE Transactions on Signal Processing",
issn = "1053-587X",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "9",

}

TY - JOUR

T1 - Semi-Blind inference of topologies and dynamical processes over dynamic graphs

AU - Ioannidis, Vassilis N.

AU - Shen, Yanning

AU - Giannakis, Georgios B.

PY - 2019/5/1

Y1 - 2019/5/1

N2 - A task of major practical importance in network science is inferring the graph structure from noisy observations at a subset of nodes. Available methods for topology inference typically assume that the process over the network is observed at all nodes. However, application-specific constraints may prevent acquiring network-wide observations. Alleviating the limited flexibility of existing approaches, this work advocates structural models for graph processes and develops novel algorithms for joint inference of the network topology and processes from partial nodal observations. Structural equation models (SEMs) and structural vector autoregressive models (SVARMs) have well documented merits in identifying even directed topologies of complex graphs; while SEMs capture contemporaneous causal dependencies among nodes, SVARMs further account for time-lagged influences. A batch solver is proposed that iterates between inferring directed graphs that 'best' fit the sequence of observations, and estimating the network processes at reduced computational complexity by leveraging tools related to Kalman smoothing. To further accommodate delay-sensitive applications, an online joint inference approach is put forth that even tracks time-evolving topologies. Furthermore, we specify novel conditions for identifying the network topology given partial observations. We prove that the required number of observations for unique identification reduces significantly when the network structure is sparse. Numerical tests with synthetic as well as real datasets corroborate the effectiveness of the proposed approach.

AB - A task of major practical importance in network science is inferring the graph structure from noisy observations at a subset of nodes. Available methods for topology inference typically assume that the process over the network is observed at all nodes. However, application-specific constraints may prevent acquiring network-wide observations. Alleviating the limited flexibility of existing approaches, this work advocates structural models for graph processes and develops novel algorithms for joint inference of the network topology and processes from partial nodal observations. Structural equation models (SEMs) and structural vector autoregressive models (SVARMs) have well documented merits in identifying even directed topologies of complex graphs; while SEMs capture contemporaneous causal dependencies among nodes, SVARMs further account for time-lagged influences. A batch solver is proposed that iterates between inferring directed graphs that 'best' fit the sequence of observations, and estimating the network processes at reduced computational complexity by leveraging tools related to Kalman smoothing. To further accommodate delay-sensitive applications, an online joint inference approach is put forth that even tracks time-evolving topologies. Furthermore, we specify novel conditions for identifying the network topology given partial observations. We prove that the required number of observations for unique identification reduces significantly when the network structure is sparse. Numerical tests with synthetic as well as real datasets corroborate the effectiveness of the proposed approach.

KW - Directed graphs

KW - Graph signal reconstruction

KW - Structural (vector) equation models

KW - Topology inference

UR - http://www.scopus.com/inward/record.url?scp=85063585795&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85063585795&partnerID=8YFLogxK

U2 - 10.1109/TSP.2019.2903025

DO - 10.1109/TSP.2019.2903025

M3 - Article

AN - SCOPUS:85063585795

VL - 67

SP - 2263

EP - 2274

JO - IEEE Transactions on Signal Processing

JF - IEEE Transactions on Signal Processing

SN - 1053-587X

IS - 9

M1 - 8662630

ER -