Distributed Graph Learning with Smooth Data Priors

Isabela Cunha Maia Nobre, Mireille El Gheche, Pascal Frossard

Abstract

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.

Introduction

In the field of Graph Signal Processing (GSP), the underlying graph structure is frequently assumed to be known. However, in many real-world scenarios, we possess signals observed at nodes but lack the explicit connections between them. Inferring this graph structure is a critical problem, but traditional centralized approaches incur a significant "communication tax" by requiring all node data to be transmitted to a central server. This overhead is often prohibitive in large-scale wireless sensor networks, privacy-sensitive biological systems, or IoT applications where bandwidth and battery life are constrained.

This paper introduces a novel distributed graph learning framework that explicitly accounts for communication costs. By leveraging local optimization and a "smoothness" data prior—the assumption that signals on connected nodes vary gradually—the proposed algorithm allows nodes to infer their connections locally, communicating only with immediate neighbors.

Methods

The distributed algorithm operates by minimizing a cost function that balances data smoothness with degree constraints to prevent trivial solutions (e.g., all nodes disconnecting). The process is divided into two primary phases:

  1. Smart Initialization: To avoid broadcasting signals to the entire network, nodes use a degree-based heuristic. A node only transmits its signal to its highest-degree neighbor if it hasn't already received data from them. This allows nodes to calculate initial signal distances ($z_{ij} = \|x_i - x_j\|^2$) with minimal transmissions.
  2. Collaborative Optimization:
  3. Local Step: Each node independently performs gradient descent to update its local edge weight estimates.
  4. Global (Symmetry) Step: Since nodes $i$ and $j$ might independently estimate different weights for the same edge ($w_{ij} \neq w_{ji}$), they periodically exchange these estimates and average them to ensure a symmetric, valid graph structure.
Overview of the distributed graph learning process: (a) initialization of distances, (b) local weight estimation, (c) weight exchange, (d) symmetry averaging, and (e) updated weights.

By alternating between these local computations and neighbor-to-neighbor synchronization, the network converges to a global graph structure without a central processor.

Experimental Setup

The framework was benchmarked using synthetic datasets to compare against a known ground truth. Nodes were randomly distributed in a 2D unit square, and a communication graph was established based on a connectivity radius. A target "data graph" was then created as a subgraph of this communication network. For each node, 5,000 smooth signals were generated using a probabilistic model. To evaluate scalability, the number of nodes ($N$) was varied from 150 to 950.

Results and Discussion

The experimental results highlight a significant communication-accuracy trade-off advantage for the distributed approach:

  • Communication Efficiency: In sparse network settings, the distributed algorithm demonstrated substantially lower total communication costs (measured in message counts) compared to centralized baselines. As the network size ($N$) or the number of signals increases, the communication cost of the distributed method grows much more slowly.
  • Accuracy: Performance was measured using the Frobenius norm and Wasserstein distance between the learned and true weight matrices. The distributed model achieved accuracy nearly identical to centralized methods, proving that a global "brain" is not required for high-precision graph inference.
  • Sparsity as a Benefit: The algorithm performs exceptionally well on sparse networks, where the local nature of the optimization matches the physical constraints of the communication graph.

Conclusion

The proposed distributed graph learning framework effectively dodges the centralized communication tax without compromising accuracy. While currently assuming the data graph is a subgraph of the communication graph and focusing on static structures, it provides a scalable foundation for future work in dynamic settings and real-world large-scale sensor networks like urban traffic or power grids.

Summary updated

Abstract

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.
BibTeX
@inproceedings{nobre2022distributed,
  author = {Isabela Cunha Maia Nobre and Mireille El Gheche and Pascal Frossard},
  title = {{Distributed Graph Learning with Smooth Data Priors}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2022},
  url = {https://openreview.net/forum?id=tG1cQs7lKg},
}
Figure