Decentralized Computation of Effective Resistances and Acceleration of Distributed Optimization Algorithms

Bugra Can, Saeed Soori, Necdet Serhat Aybat, Maryam Mehri Dehvani, Mert Gürbüzbalaban

Abstract

The effective resistance (ER) between nodes in a weighted undirected graph is a critical quantity in fields ranging from linear systems to Markov chains. This research develops an efficient, linearly convergent distributed algorithm for computing ER and demonstrates its utility in accelerating distributed optimization. By weighting communication probabilities based on ER, we show that classical consensus iterations can be accelerated by a factor depending on the network structure, particularly in graphs with significant bottlenecks.

The Bottleneck Problem in Distributed Consensus

In distributed systems, agents often need to compute the average of their local values, a task known as the consensus problem. The standard approach is randomized gossiping, where nodes communicate with random neighbors. However, this method suffers from "bottlenecks"—edges that connect dense clusters but are rarely selected under uniform probability distributions.

Figure 1: A standard barbell graph consisting of two dense cliques connected by a single bridge edge, representing a classic network bottleneck.

As seen in the barbell graph above, a uniform random choice will rarely select the bridge edge. Consequently, the two clusters reach internal consensus quickly but take a very long time to synchronize with each other. This research addresses this by treating the network like an electrical circuit and weighting edges by their Effective Resistance.

Effective Resistance as a Weighting Strategy

If every edge in a graph is viewed as a resistor, the ER between two nodes is the voltage drop induced when a unit current is injected at one and extracted at the other. The authors leverage Foster’s Theorem—which states the sum of all ER weights in a graph is $n-1$—to create a robust, normalized probability distribution for node activation.

Key methodological steps include:

  1. ER-Based Gossiping: Activating communication with a probability proportional to the ER of the connecting edge.
  2. Spectral Analysis: Analyzing the spectral gap of the iteration matrix to prove faster convergence.
  3. Distributed Computation: Utilizing a Distributed Randomized Kaczmarz (D-RK) algorithm to allow nodes to estimate ER weights locally without global knowledge.

Performance on Complex Topologies

The paper evaluates these theories using synthetic graph topologies that represent common network challenges, such as the $c$-barbell graph.

Figure 2: A c-barbell graph, which generalizes the bottleneck problem across a chain of multiple dense clusters.

On a standard barbell graph with $n$ nodes, ER-based gossiping is $\Theta(n)$ times faster than uniform gossiping, reducing averaging time from $O(n^3 \log(1/\epsilon))$ to $O(n^2 \log(1/\epsilon))$. The authors prove that for such graphs, ER gossiping is the optimal choice among all symmetric gossip matrices.

Applications in Distributed Optimization

Beyond simple averaging, the ER-based framework accelerates complex distributed optimization algorithms. By improving the underlying consensus step, the researchers demonstrated significant reductions in communication rounds for decentralized machine learning tasks, specifically within the EXTRA and DPGA-W frameworks. This synergy suggests that ER weights are a powerful "building block" for any decentralized algorithm relying on neighbor-to-neighbor information exchange.

Conclusion

While ER weights provide the most significant gains in bottlenecked or community-structured graphs, the development of a decentralized algorithm to compute these weights makes the approach practical for real-world sensor networks and autonomous systems. Future work aims to extend these benefits to directed graphs and dynamic networks where topology may change over time.

Summary updated

Abstract

The effective resistance between a pair of nodes in a weighted undirected graph is defined as the potential difference induced between them when a unit current is injected at the first node and extracted at the second node, treating edge weights as the conductance values of edges. The effective resistance is a key quantity of interest in many applications and fields including solving linear systems, Markov Chains and continuous-time averaging networks. We develop an efficient linearly convergent distributed algorithm for computing effective resistances and demonstrate its performance through numerical studies. We also apply our algorithm to the consensus problem where the aim is to compute the average of node values in a distributed manner based on weighted averaging with immediate neighbors. We show that the distributed algorithm we developed for effective resistances can be used to design a weight matrix which can help pass the information among neighbors more effectively, accelerating the convergence of the classical consensus iterations considerably by a factor depending on the network structure. We also present an application of our effective resistance-based framework to accelerate distributed optimization algorithms including the EXTRA and DPGA-W.
BibTeX
@article{can2019decentralized,
  author = {Bugra Can and Saeed Soori and Necdet Serhat Aybat and Maryam Mehri Dehvani and Mert Gürbüzbalaban},
  title = {{Decentralized Computation of Effective Resistances and Acceleration of Distributed Optimization Algorithms}},
  journal = {IEEE Trans. Control. Netw. Syst.},
  year = {2019},
}
Figure