Distributed Graph Learning with Smooth Data Priors
This work addresses the challenge of graph learning in distributed settings where data collection is costly, offering a solution for applications like sensor networks or decentralized systems.
The paper tackles the problem of learning graphs from distributed signal observations under smoothness assumptions, proposing a distributed optimization algorithm that reduces communication costs while maintaining accuracy comparable to centralized methods, especially scaling well in sparse networks.
Graph learning is often a necessary step in processing or representing structured data, when the underlying graph is not given explicitly. Graph learning is generally performed centrally with a full knowledge of the graph signals, namely the data that lives on the graph nodes. However, there are settings where data cannot be collected easily or only with a non-negligible communication cost. In such cases, distributed processing appears as a natural solution, where the data stays mostly local and all processing is performed among neighbours nodes on the communication graph. We propose here a novel distributed graph learning algorithm, which permits to infer a graph from signal observations on the nodes under the assumption that the data is smooth on the target graph. We solve a distributed optimization problem with local projection constraints to infer a valid graph while limiting the communication costs. Our results show that the distributed approach has a lower communication cost than a centralised algorithm without compromising the accuracy in the inferred graph. It also scales better in communication costs with the increase of the network size, especially for sparse networks.