<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">% !TEX root = main.tex

\section{D-Cliques}
\label{section:d-cliques}

In this section, we introduce D-Cliques, a topology
designed to compensate for data heterogeneity. We also present some
modifications of D-SGD that leverage some properties of the proposed
topology and allow to implement a successful momentum scheme.

\subsection{Intuition}

To give the intuition behind
our approach, let us consider the neighborhood of a single node in a grid
topology similar to that of Figure~\ref{fig:grid-IID-vs-non-IID}, represented
on Figure~\ref{fig:grid-iid-vs-non-iid-neighbourhood}.
Nodes are distributed randomly in the grid and the colors of a node represent
the proportion of each class in its local dataset. In the homogeneous
setting, the label distribution is the same across
nodes: in the example shown in Figure~\ref{fig:grid-iid-neighbourhood}, all classes
are represented in equal proportions. This is not the case in the
heterogeneous setting: in the
extreme case of label distribution skew shown in
Figure~\ref{fig:grid-non-iid-neighbourhood}, each
node actually holds examples of a single class.

From the point of view of the center node, a single training step of D-SGD is
equivalent to sampling a mini-batch five times larger from the union of the
local distributions of all illustrated nodes.
In the homogeneous case, since gradients are computed from examples of all
classes,
the resulting averaged gradient  points in a direction that tends to reduce
the loss across all classes. In contrast, in the heterogeneous case, only a
subset
of classes are
represented in the immediate neighborhood of the node, thus the gradients will
be biased towards these classes.
Importantly, as the distributed averaging algorithm takes several steps to
converge, this variance persists across iterations as the locally computed
gradients are far from the global average.\footnote{One could perform a
sufficiently large number of
averaging steps between each gradient step, but this is too costly in
practice.} This can significantly slow down
convergence speed to the point of making decentralized optimization
impractical.

\begin{figure}[t]
     \centering
     \begin{subfigure}[b]{0.18\textwidth}
         \centering
         \includegraphics[width=\textwidth]{../figures/grid-iid-neighbourhood}
\caption{\label{fig:grid-iid-neighbourhood} Homogeneous data}
     \end{subfigure}
     \hspace*{.5cm}
     \begin{subfigure}[b]{0.18\textwidth}
         \centering
         \includegraphics[width=\textwidth]{../figures/grid-non-iid-neighbourhood}
\caption{\label{fig:grid-non-iid-neighbourhood}  Heterogeneous data}
     \end{subfigure}
        \caption{Neighborhood in a grid.}
        \label{fig:grid-iid-vs-non-iid-neighbourhood}
\end{figure}

In D-Cliques, we address label distribution skew by
carefully designing a
network topology composed of \textit{locally representative cliques} and 
\textit{sparse inter-clique
connections}.

\subsection{Constructing Locally Representative Cliques}

D-Cliques constructs a topology in which each node is part of a \emph{clique} 
(i.e., a subset of nodes such that the induced subgraph is fully connected)
such that the label distribution in each clique is
close to the global label distribution. Formally, for a label $y$ and a
clique composed of nodes $C\subseteq N$, we denote by $p_C(y)=
\frac{1}{|C|}\sum_{i\in C} p_i(y)$ the distribution of $y$ in $C$
and by $p(y)=\frac{1}{n}\sum_{i\in N} p_i(y)$ its global distribution.
We measure the \textit{skew} of $C$ by the sum
of the absolute differences of $p_C(y)$ and $p(y)$:
\begin{equation}
\label{eq:skew}
        \textit{skew}(C) =\
    \sum_{l=1}^L | p_C(y = l) - p(y = l) |.
\end{equation}


% D-Cliques constructs a topology in which each node $i \in N$ is
% part of a \textit{clique} $C$ such that the clique distribution $D_C =
% \bigcup\limits_{\substack{i \in C}} D_i$ is close to that of the global
% distribution $D = \bigcup\limits_{\substack{i \in N}} D_i$. We measure the
% closeness of $D_C$ to $D$ using its \textit{skew}, i.e. the sum of the
% differences in the probabilities that a sample $(x,y)$ belongs to a given class in $D_C$ and $D$: 
% \begin{equation}
% \label{eq:skew}
% \begin{split}
%         \textit{skew}(C) =\
%     \sum\limits_{\substack{l=1}}^L | p(y = l~|(x,y) \sim D_C) - \\ p(y = l~|
%     (x,y) \sim D) |
% \end{split}
% \end{equation}

To efficiently construct a set of cliques with small skew, we propose
Greedy-Swap (Algorithm~\ref{Algorithm:D-Clique-Construction}). The parameter
$M$ gives the maximum size of cliques and allows to control the intra-clique
communication costs. We start by initializing cliques at random. Then, for
a certain number of steps $K$, we randomly pick two cliques and swap two of
their nodes so as to decrease the sum of skews of the two cliques. The swap is
chosen randomly among the ones which decrease the skew, hence
this algorithm can be seen as a form of randomized greedy algorithm.
We note that this algorithm only requires
the knowledge of the label distribution $p_i(y)$ at each node $i$. For the
sake of
simplicity, we assume that D-Cliques are constructed from the global
knowledge of these distributions, which can easily be obtained by
decentralized averaging in a pre-processing step. 

\begin{algorithm}[t]
   \caption{D-Cliques Construction via Greedy Swap}
   \label{Algorithm:greedy-swap}
   \begin{algorithmic}[1]
        \STATE \textbf{Require:} maximum clique size $M$, max steps $K$, set
        of all nodes $N = \{ 1, 2, \dots, n \}$,
        % \STATE $\textit{skew}(S)$: skew of subset $S \subseteq N$ compared to the global distribution (Eq.~\ref{eq:skew}), 
        % \STATE $\textit{intra}(DC)$: edges within cliques $C \in DC$,
        % \STATE $\textit{inter}(DC)$: edges between $C_1,C_2 \in DC$ (Sec.~\ref{section:interclique-topologies}),
         % \STATE $\textit{weights}(E)$: set weights to edges in $E$ (Eq.~\ref{eq:metro}).
         % \STATE ~~
         \STATE $DC \leftarrow []$ %\COMMENT{Empty list}
         \WHILE {$N \neq \emptyset$}
         \STATE $C \leftarrow$ sample $M$ nodes from $N$ at random
         \STATE $N \leftarrow N \setminus C$; $DC.\text{append}(C)$
         \ENDWHILE
         \FOR{$k \in \{1, \dots, K\}$}
        \STATE $C_1,C_2 \leftarrow$ random sample of 2 elements from $DC$
          \STATE $s \leftarrow \textit{skew}(C_1) + skew(C_2)$
        \STATE $\textit{swaps} \leftarrow []$
        \FOR{$i \in C_1, j \in C_2$}
          \STATE $s' \leftarrow \textit{skew}(C_1\setminus\{i\}\cup\{j\})
          + \textit{skew}(C_2 \setminus\{i\}\cup\{j\})$\hspace*{-.05cm}
          \IF {$s' &lt; s$}
            \STATE \textit{swaps}.append($(n_1, n_2)$)
          \ENDIF
        \ENDFOR
        \IF {len(\textit{swaps}) $&gt; 0$}
          \STATE $(n_1,n_2) \leftarrow$ random element from $
          \textit{swaps}$ 
          \STATE $C_1 \leftarrow C_1 \setminus\{j\}\cup\{i\}; C_2 \leftarrow C_2 \setminus\{j\}\cup\{i\}$
        \ENDIF
         \ENDFOR
         \STATE $G \leftarrow$ graph composed of the cliques in $DC$
        \RETURN $G$
   \end{algorithmic}
\end{algorithm}

% \begin{algorithm}[h]
%    \caption{D-Cliques Construction: Greedy Swap}
%    \label{Algorithm:D-Clique-Construction}
%    \begin{algorithmic}[1]
%         \STATE \textbf{Require:} Max clique size $M$, Max steps $K$,
%         \STATE Set of all nodes $N = \{ 1, 2, \dots, n \}$,
%         \STATE $\textit{skew}(S)$: skew of subset $S \subseteq N$ compared to the global distribution (Eq.~\ref{eq:skew}), 
%         \STATE $\textit{intra}(DC)$: edges within cliques $C \in DC$,
%         \STATE $\textit{inter}(DC)$: edges between $C_1,C_2 \in DC$ (Sec.~\ref{section:interclique-topologies}),
%          \STATE $\textit{weights}(E)$: set weights to edges in $E$ (Eq.~\ref{eq:metro}).
%          \STATE ~~
%          \STATE $DC \leftarrow []$ \COMMENT{Empty list}
%          \WHILE {$N \neq \emptyset$}
%          \STATE $C \leftarrow$ sample $M$ nodes from $N$ at random
%          \STATE $N \leftarrow N \setminus C$; $DC.append(C)$
%          \ENDWHILE
%          \FOR{$k \in \{1, \dots, K\}$}
%         \STATE $C_1,C_2 \leftarrow$ sample 2 from $DC$ at random
%         \STATE $\textit{swaps} \leftarrow []$
%         \FOR{$n_1 \in C_1, n_2 \in C_2$}
%           \STATE $s \leftarrow skew(C_1) + skew(C_2)$
%           \STATE $s' \leftarrow \textit{skew}(C_1-n_1+n_2) + \textit{skew}(C_2 -n_2+n_1)$
%           \IF {$s' &lt; s$}
%             \STATE \textit{swaps}.append($(n_1, n_2)$)
%           \ENDIF
%         \ENDFOR
%         \IF {\#\textit{swaps} $&gt; 0$}
%           \STATE $(n_1,n_2) \leftarrow$ sample 1 from $\textit{swaps}$ at random
%           \STATE $C_1 \leftarrow C_1 - n_1 + n_2; C_2 \leftarrow C_2 - n_2 + n1$
%         \ENDIF
%          \ENDFOR
%         \RETURN $(weights(\textit{intra}(DC) \cup \textit{inter}(DC)), DC)$
%    \end{algorithmic}
% \end{algorithm}

The key idea of D-Cliques is that because the clique-level label distribution
$p_C(y)$
 is representative of the global distribution $p(y)$,
the local models of nodes across cliques remain rather close. Therefore, a
sparse inter-clique topology can be used, significantly reducing the total
number of edges without slowing down the convergence. We discuss
choices for this inter-clique topology in the next section.

\subsection{Adding Sparse Inter-Clique Connections}
\label{section:interclique-topologies}

\begin{figure}[t]
    \centering
    \includegraphics[width=0.20\textwidth]{../figures/fully-connected-cliques}
    \caption{\label{fig:d-cliques-figure} D-Cliques (fully-connected
    cliques) example with 1 class/node.}
\end{figure}
\todo{AB: if time, could add fig of another inter-clique topology (ring,
fractal or small-world)}

Second, to ensure a global consensus and convergence, 
 \textit{inter-clique connections}
 are introduced by connecting a small number of node pairs that are
 part of  different cliques. In the following, we introduce up to one inter-clique 
 connection per node such that each clique has exactly one
edge with all other cliques, see Figure~\ref{fig:d-cliques-figure} for the
corresponding D-Cliques network in the case of $n=100$ nodes and $L=10$
classes. We will explore sparser inter-clique topologies in
Section~\ref{section:interclique-topologies}.

So far, we have used a fully-connected inter-clique topology for D-Cliques,
which has the advantage of bounding the
\textit{path length}\footnote{The \textit{path length} is the number of edges on the path with the shortest number of edges between two nodes.} to $3$ between any pair of nodes. This choice requires $
\frac{n}{c}(\frac{n}{c} - 1)$ inter-clique edges, which scales quadratically
in the number of nodes $n$ for a given clique size $c$\footnote{We consider \textit{directed} edges in the analysis: the number of undirected edges is half and does not affect asymptotic behavior.}. This can become significant at larger scales when $n$ is
large compared to $c$.

We first measure the convergence speed of inter-cliques topologies whose number of edges scales linearly with the number of nodes. Among those, the \textit{ring} has the (almost) fewest possible number of edges: it
uses $\frac{2n}{c}$ inter-clique edges but its average path length between nodes 
also scales linearly.
We also consider another topology, which we call \textit{fractal}, that provides a
logarithmic
bound on the average path length. In this hierarchical scheme, 
cliques are assembled in larger groups of $c$ cliques that are connected internally with one edge per
pair of cliques, but with only one edge between pairs of larger groups. The
topology is built recursively such that $c$ groups will themselves form a
larger group at the next level up. This results in at most $c$ edges per node 
if edges are evenly distributed: i.e., each group within the same level adds 
at most $c-1$ edges to other groups, leaving one node per group with $c-1$ 
edges that can receive an additional edge to connect with other groups at the next level.
Since nodes have at most $c$ edges, $n$ nodes have at most $nc$ edges, therefore
the number of edges in this fractal scheme indeed scales linearly in the number of nodes.

Second, we look at another scheme 
in which the number of edges scales in a near, but not quite, linear fashion.
We propose to connect cliques according to a
small-world-like topology~\cite{watts2000small} applied on top of a
ring~\cite{stoica2003chord}. In this scheme, cliques are first arranged in a
ring. Then each clique adds symmetric edges, both clockwise and
counter-clockwise on the ring, with the $m$ closest cliques in sets of
cliques that are exponentially bigger the further they are on the ring (see
Algorithm~\ref{Algorithm:Smallworld} in the appendix for
details on the construction). This ensures a good connectivity with other
cliques that are close on the ring, while still keeping the average
path length small. This scheme uses $\frac{n}{c}*2(m)\log(\frac{n}{c})$ inter-clique edges and
therefore grows in the order of $O(n\log(n))$ with the number of nodes.

Overall, D-Cliques ensures that the degree
of each node in the network remains low and balanced, making the topology
well-suited to
decentralized federated learning. 

\subsection{Optimizing with Clique Averaging and Momentum}
\label{section:clique-averaging-momentum}

In this section, we present Clique Averaging. This feature, when added to D-SGD,
removes the bias caused by the inter-cliques edges of
D-Cliques. We also show how it can be used to successfully implement momentum
for non-IID data.

\subsubsection{Clique Averaging: Debiasing Gradients from Inter-Clique Edges}
\label{section:clique-averaging}

While limiting the number of inter-clique connections reduces the
amount of messages traveling on the network, it also introduces its own
bias.
Figure~\ref{fig:connected-cliques-bias} illustrates the problem on the
simple case of two cliques connected by one inter-clique edge (here,
between the green node of the left clique and the pink node of the right
clique). Let us focus on node A. With weights computed as in \eqref{eq:metro},
node A's self-weight is $\frac{12}
{110}$, the weight between A and the green node connected to B is
$\frac{10}{110}$, and
all other neighbors of A have a weight of $\frac{11}{110}$. Therefore, the
gradient at A is biased towards its own class (pink) and against the green
class. A similar bias holds for all other nodes
without inter-clique edges with respect to their respective classes. For node
B, all its edge weights (including its self-weight) are equal to $\frac{1}
{11}$. However, the green class is represented twice (once as a clique
neighbor and once from the inter-clique edge), while all other classes are
represented only once. This biases the gradient toward the green class. The
combined effect of these two sources of bias is to increase the variance
of the local models across nodes.

\begin{figure}[t]
         \centering
         \includegraphics[width=0.3\textwidth]{../figures/connected-cliques-bias}
\caption{\label{fig:connected-cliques-bias} Illustrating the bias induced by
inter-clique connections (see main text).}
\end{figure}

We address this problem by adding \emph{Clique Averaging} to D-SGD
(Algorithm~\ref{Algorithm:Clique-Unbiased-D-PSGD}), which essentially
decouples gradient averaging from model averaging. The idea is to use only the
gradients of
neighbors within the same clique to compute the average gradient,
providing an equal representation to all classes. In contrast, all neighbors'
models, including those across inter-clique edges, participate in the model
averaging step as in the original version.

\begin{algorithm}[t]
   \caption{D-SGD with Clique Averaging, Node $i$}
   \label{Algorithm:Clique-Unbiased-D-PSGD}
   \begin{algorithmic}[1]
        \STATE \textbf{Require} initial model parameters $\theta_i^{(0)}$, learning
        rate $\gamma$, mixing weights $W$, mini-batch size $m$, number of
        steps $K$
        \FOR{$k = 1,\ldots, K$}
          \STATE $S_i^{(k)} \gets \text{mini-batch of $m$ samples drawn
          from~} D_i$
          \STATE $g_i^{(k)} \gets \frac{1}{|\textit{Clique}(i)|}\sum_{j \in 
          \textit{Clique(i)}}  \nabla F(\theta_j^{(k-1)}; S_j^{(k)})$
          \STATE $\theta_i^{(k-\frac{1}{2})} \gets \theta_i^{(k-1)} - \gamma g_i^{(k)}$ 
          \STATE $\theta_i^{(k)} \gets \sum_{j \in N} W_{ji}^{(k)} \theta_j^{(k-\frac{1}{2})}$
        \ENDFOR
   \end{algorithmic}
\end{algorithm}


\subsubsection{Implementing Momentum with Clique Averaging}
\label{section:momentum}

Efficiently training high capacity models usually requires additional
optimization techniques. In particular, momentum~\cite{pmlr-v28-sutskever13}
increases the magnitude of the components of the gradient that are shared
between several consecutive steps, and is critical for deep convolutional networks like
LeNet~\cite{lecun1998gradient,quagmire} to converge quickly. However, a direct
application of momentum in a non-IID setting can actually be very detrimental.
As illustrated in Figure~\ref{fig:d-cliques-cifar10-momentum-non-iid-effect}
for the case of LeNet on CIFAR10 with 100 nodes, D-Cliques with momentum
even fails to converge. Not using momentum actually gives a faster
convergence, but there is a significant gap compared to the case of a single
IID node with momentum.

Clique Averaging (Section~\ref{section:clique-averaging})
allows us to compute an unbiased momentum from the
unbiased average gradient $g_i^{(k)}$ of Algorithm~\ref{Algorithm:Clique-Unbiased-D-PSGD}:
\begin{equation}
v_i^{(k)} \leftarrow m v_i^{(k-1)} +  g_i^{(k)}.
\end{equation}
It then suffices to modify the original gradient step to use momentum:
\begin{equation}
\theta_i^{(k-\frac{1}{2})} \leftarrow \theta_i^{(k-1)} - \gamma v_i^{(k)}.
\end{equation}

% \section{Scaling the Interclique Topology}
% \label{section:interclique-topologies}

</pre></body></html>