skip to main content

Attention:

The NSF Public Access Repository (PAR) system and access will be unavailable from 11:00 PM ET on Thursday, February 13 until 2:00 AM ET on Friday, February 14 due to maintenance. We apologize for the inconvenience.


Title: Identifying Undirected Network Structure via Semidefinite Relaxation
We address the problem of inferring an undirected graph from nodal observations, which are modeled as non-stationary graph signals generated by local diffusion dynamics on the unknown network. We propose a two-step approach where we first estimate the unknown diffusion (graph) filter, from which we recover the eigenvectors of the so-called graph-shift operator (a matrix representation of the graph). We then estimate the eigenvalues by imposing desirable properties on the graph to be recovered. To carry out the initial system identification step, we assume that second-order statistics of the inputs are available. While such quadratic filter identification problem boils down to a non-convex fourth order polynomial minimization, we propose a semidefinite relaxation with provable performance guarantees. Finally, numerical tests illustrate the use of the proposed algorithm to unveil urban mobility patterns.  more » « less
Award ID(s):
1750428
PAR ID:
10087936
Author(s) / Creator(s):
; ; ;
Date Published:
Journal Name:
2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)
Page Range / eLocation ID:
4049-4053
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. We address the problem of inferring a directed network from nodal observations of graph signals generated by linear diffusion dynamics on the sought graph. Observations are modeled as the outputs of a linear graph filter (i.e., a polynomial on a local diffusion graph-shift operator encoding the unknown graph topology), excited with an ensemble of independent graph signals with arbitrarily-correlated nodal components. In this context, we first rely on observations of the output signals along with prior statistical information on the inputs to identify the diffusion filter. Such problem entails solving a system of quadratic matrix equations, which we recast 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. Preliminary numerical tests corroborating the effectiveness of the proposed algorithms in recovering synthetic and real-world digraphs are provided. 
    more » « less
  2. This paper considers the problem of inferring the topology of a graph from noisy outputs of an unknown graph filter excited by low-rank signals. Limited by this low-rank structure, we focus on the community detection problem, whose aim is to partition the node set of the unknown graph into subsets with high edge densities. We propose to detect the communities by applying spectral clustering on the low-rank output covariance matrix. To analyze the performance, we show that the low-rank covariance yields a sketch of the eigenvectors of the unknown graph. Importantly, we provide theoretical bounds on the error introduced by this sketching procedure based on spectral features of the graph filter involved. Finally, our theoretical findings are validated via numerical experiments in both synthetic and real-world graphs. 
    more » « less
  3. Correspondence identification is essential for multi-robot collaborative perception, which aims to identify the same objects in order to ensure consistent references of the objects by a group of robots/agents in their own fields of view. Although recent deep learning methods have shown encouraging performance on correspondence identification, they suffer from two shortcomings, including the inability to address non-covisibility in collaborative perception that is caused by occlusion and limited fields of view of the agents, and the inability to quantify and reduce uncertainty to improve correspondence identification. To address both issues, we propose a novel uncertainty-aware deep graph matching method for correspondence identification in collaborative perception. Our method formulates correspondence identification as a deep graph matching problem, which identifies correspondences based upon graph representations that are constructed from robot observations. We propose new deep graph matching networks in the Bayesian framework to explicitly quantify uncertainty in identified correspondences. In addition, we design novel loss functions in order to explicitly reduce correspondence uncertainty and perceptual non-covisibility during learning. We evaluate our method in the robotics applications of collaborative assembly and multi-robot coordination using high-fidelity simulations and physical robots. Experiments have validated that, by addressing uncertainty and non-covisibility, our proposed approach achieves the state-of-the-art performance of correspondence identification. 
    more » « less
  4. This article presents an online parameter identification scheme for advection-diffusion processes using data collected by a mobile sensor network. The advection-diffusion equation is incorporated into the information dynamics associated with the trajectories of the mobile sensors. A constrained cooperative Kalman filter is developed to provide estimates of the field values and gradients along the trajectories of the mobile sensors so that the temporal variations in the field values can be estimated. This leads to a co-design scheme for state estimation and parameter identification for advection-diffusion processes that is different from comparable schemes using sensors installed at fixed spatial locations. Using state estimates from the constrained cooperative Kalman filter, a recursive least-square (RLS) algorithm is designed to estimate unknown model parameters of the advection-diffusion processes. Theoretical justifications are provided for the convergence of the proposed cooperative Kalman filter by deriving a set of sufficient conditions regarding the formation shape and the motion of the mobile sensor network. Simulation and experimental results show satisfactory performance and demonstrate the robustness of the algorithm under realistic uncertainties and disturbances. 
    more » « less
  5. This paper deals with the problem of blind identification of a graph filter and its sparse input signal, thus broadening the scope of classical blind deconvolution of temporal and spatial signals to irregular graph domains. While the observations are bilinear functions of the unknowns, a mild requirement on invertibility of the filter enables an efficient convex formulation, without relying on matrix lifting that can hinder applicability to large graphs. On top of scaling, it is argued that (non-cyclic) permutation ambiguities may arise with some particular graphs. Deterministic sufficient conditions under which the proposed convex relaxation can exactly recover the unknowns are stated, along with those guaranteeing identifiability under the Bernoulli-Gaussian model for the inputs. Numerical tests with synthetic and real-world networks illustrate the merits of the proposed algorithm, as well as the benefits of leveraging multiple signals to aid the (blind) localization of sources of diffusion. 
    more » « less