Semiblind subgraph reconstruction in Gaussian graphical models
This work addresses the challenge of subgraph reconstruction in applications like social network analysis and sensor networks, where incomplete data leads to false edges, but it is incremental as it builds on existing Gaussian graphical model methods.
The paper tackles the problem of accurately estimating a subgraph of a Gaussian graphical model when only partial and noisy information about the complementary subgraph is available, as in social networks or sensor networks, and proposes a penalized likelihood approach with a convex-concave iterative optimization algorithm to address this semiblind scenario.
Consider a social network where only a few nodes (agents) have meaningful interactions in the sense that the conditional dependency graph over node attribute variables (behaviors) is sparse. A company that can only observe the interactions between its own customers will generally not be able to accurately estimate its customers' dependency subgraph: it is blinded to any external interactions of its customers and this blindness creates false edges in its subgraph. In this paper we address the semiblind scenario where the company has access to a noisy summary of the complementary subgraph connecting external agents, e.g., provided by a consolidator. The proposed framework applies to other applications as well, including field estimation from a network of awake and sleeping sensors and privacy-constrained information sharing over social subnetworks. We propose a penalized likelihood approach in the context of a graph signal obeying a Gaussian graphical models (GGM). We use a convex-concave iterative optimization algorithm to maximize the penalized likelihood.