# Stable Diffusion-based Data Augmentation for Federated Learning with Non-IID
Data

Mahdi Morafah  University of California San DiegoUSA ,  Matthias Reisser
Qualcomm AI ResearchUSA ,  Bill Lin  University of California San DiegoUSA and
Christos Louizos  Qualcomm AI ResearchNetherlands

(2024)

###### Abstract.

The proliferation of edge devices has brought Federated Learning (FL) to the
forefront as a promising paradigm for decentralized and collaborative model
training while preserving the privacy of clients’ data. However, FL struggles
with a significant performance reduction and poor convergence when confronted
with Non-Independent and Identically Distributed (Non-IID) data distributions
among participating clients. While previous efforts, such as client drift
mitigation and advanced server-side model fusion techniques, have shown some
success in addressing this challenge, they often overlook the root cause of
the performance reduction—the absence of identical data accurately mirroring
the global data distribution among clients. In this paper, we introduce “Gen-
FedSD” a novel approach that harnesses the powerful capability of state-of-
the-art text-to-image foundation models to bridge the significant Non-IID
performance gaps in FL. In Gen-FedSD, each client constructs textual prompts
for each class label and leverages an of-the-shelf state-of-the-art pre-
trained Stable Diffusion model to synthesize high-quality data samples. The
generated synthetic data is tailored to each client’s unique local data gaps
and distribution disparities, effectively making the final augmented local
data IID. Through extensive experimentation, we demonstrate that Gen-FedSD
achieves state-of-the-art performance and significant communication cost
savings across various datasets and Non-IID settings.

Federated Learning, Non-IID Data, Stable Diffusion, Foundation Models

††copyright: acmlicensed††journalyear: 2024††publicationmonth: May††doi:
XXXXXXX.XXXXXXX††conference: International Workshop on Federated Foundation
Models for the Web 2024 ; May 14, 2024; Singapore

##  1\. Introduction

Federated Learning (FL) has emerged as a promising framework enabling
decentralized training of machine learning models. It allows, under the
orchestration of a central server, for a massive amount of edge devices to
collaborate in training the model, while keeping the client’s data local
(McMahan et al., 2017; Kairouz et al., 2021). However, FL struggles with a
significant performance degradation and slow convergence when confronted with
Non-Independent and Identically Distributed (Non-IID) data distributions among
participating clients (a.k.a data heterogeneity) (Zhao et al., 2018; Li et
al., 2022a; Zhu et al., 2021b; Haddadpour and Mahdavi, 2019).

Numerous studies have been conducted to address the challenge of data
heterogeneity. Some studies propose modifications in the local objectives of
the clients to prevent the deviation of locally trained models from the global
model (Zhao et al., 2018; Karimireddy et al., 2020; Li et al., 2021).
Meanwhile, others introduce server-side model fusion techniques (Lin et al.,
2020; Sattler et al., 2021; Yurochkin et al., 2019; Wang et al., 2020b). While
prior endeavors have exhibited some enhancements in addressing the challenge
of data heterogeneity, a crucial foundational issue remains unaddressed.
Specifically, clients lack access to identical data that accurately represent
the global data distribution. This is the primary factor to the substantial
performance degradation from the ideal Independent and Identically Distributed
(IID) data distribution in FL.

Recently, several works have proposed data augmentation techniques to
construct IID data for each client’s local data. Zhao et al. (2018) used an
auxiliary public dataset to augment each client’s local data. However, this
can introduce an additional set of challenges; firstly, there could be an
inherent domain difference between the local and public data and, secondly,
gathering this public data may be extremely difficult in practice (Zhu et al.,
2021a; Zhang et al., 2023a). Alternatively, other methods suggest synthesizing
the local data using techniques such as dataset distillation (Wang et al.,
2018) and sharing it with other clients (Zhou et al., 2020; Yoon et al., 2021;
Shin et al., 2020; Hu et al., 2022). Nonetheless, this approach may raise
privacy concerns, and the synthesized data might not exhibit high quality,
which limits its effectiveness.

In this paper, we introduce a novel “Generative Federated Learning with Stable
Diffusion” (Gen-FedSD) , leveraging pre-trained state-of-the-art Stable
Diffusion (SD) (Rombach et al., 2022) to address the Non-IID challenge in FL.
In Gen-FedSD, clients construct textual prompts of the entire class labels and
employ a pre-trained state-of-the-art SD model to synthesize high-quality data
samples via the constructed input text prompts. The locally generated images
are tailored to fill the data gaps and distribution disparities of each
client, effectively aligning local data distributions with the global one, so
as to emulate the IID setting.

We empirically evaluate Gen-FedSD on CIFAR-10 and CIFAR-100 datasets under
various Non-IID settings. We make three observations. (1) Gen-FedSD
significantly enhances accuracy by at least 12% and 6% on CIFAR-10 and
CIFAR-100 datasets, respectively, under mild data heterogeneity. (2) As the
heterogeneity levels increase, Gen-FedSD exhibits even more pronounced
performance improvements. Notably, under extreme data heterogeneity, we
observe accuracy improvements of at least 20% and 7% for the CIFAR-10 and
CIFAR-100 datasets. (3) Gen-FedSD accelerates convergence and reduces
communication costs. Additionally, we investigate the impact of two different
prompt designs for image generation and find that prompt diversity can further
enhance the performance of Gen-FedSD.

Organization. The rest of the paper is organized as follows. In section 2 we
review the related works. In section 3 we discuss the necessary background on
diffusion models, image generation using Stable Diffusion, and federated
learning. In section 4 we explain our proposed method. In section 5 we present
our experimental results, and finally in section 6 we conclude our work and
discuss future works.

##  2\. Related Works

Data Heterogeneity in FL. FedAvg was first introduced by McMahan et al. (2017)
and has shown to be successful in several applications (Chen et al., 2019;
Ramaswamy et al., 2019; Feng et al., 2020; Saputra et al., 2019).
Unfortunately, the performance of FedAvg drops significantly in presence of
data heterogeneity due to clients’ local models drifting from the global model
(Zhao et al., 2018; Karimireddy et al., 2020). Several studies attempt to
mitigate the client drift issue by various techniques. FedProx (Li et al.,
2020) introduces a proximal term during local training to constrain the
deviation of local model weights from the global model. FedNova (Wang et al.,
2020a) proposes a weighting strategy in the server-side averaging to reduce
the bias in the solution. Scaffold (Karimireddy et al., 2020) employs control
variates to correct the drift in local updates, and FedOpt (Reddi et al.,
2020) proposed federated versions of adaptive optimizers by replacing the
server-side averaging with a gradient-based server optimizer. Other approaches
such as server-side model fusion techniques (Lin et al., 2020; Sattler et al.,
2021; Yurochkin et al., 2019; Wang et al., 2020b), neuron matching techniques
(Yurochkin et al., 2019; Wang et al., 2020b; Li et al., 2022a; Singh and
Jaggi, 2020) and personalization (Kulkarni et al., 2020; Deng et al., 2020;
Collins et al., 2021; Morafah et al., 2023; Hanzely et al., 2020; Vahidian et
al., 2023) have been explored.

Data Augmentation in FL. Although prior works have shown some success in
addressing data heterogeneity, they often overlooked the primary factor that
clients do not have access to data that accurately mirrors the global data
distribution. To address this, several works have proposed techniques to
augment clients’ local data with either an auxiliary public dataset (Zhao et
al., 2018) or synthetic data (Zhou et al., 2020; Yoon et al., 2021; Shin et
al., 2020; Hu et al., 2022). Unfortunately, forming an auxiliary public
dataset may be extremely difficult in practice (Zhu et al., 2021a; Zhang et
al., 2023a), and it can introduce additional heterogeneity due to its domain
difference with the clients’ local private data. Other works propose
techniques to synthesize the clients’ local private data and share it with the
server or other clients (Goetz and Tewari, 2020; Zhou et al., 2020; Yoon et
al., 2021; Shin et al., 2020; Hu et al., 2022). For example, Yoon et al.
(2021) proposed for a client to exchange the updated model parameters as well
as its mashed (or averaged) data, Shin et al. (2020) proposed a XorMixup
technique to encode each clients’ local data and share it with the server, and
in (Hu et al., 2022) each client learns and transmits a light-weight synthetic
dataset to the server. However, this approach can compromise the privacy and
the performance improvement is low due to the low quality of the synthesized
data. Training a GAN in FL and utilizing it to synthesize data has been also
explored by Jeong et al. (2018); Zhu et al. (2021a). However, training a GAN
in FL under data heterogeneity can lead to poor performance and low quality
image generation. Our work departs from the limitations of prior work by
leveraging a state-of-the-art pre-trained stable diffusion model to synthesize
high-quality images. Gen-FedSD circumvents challenges associated with training
generative models in FL and eliminates the privacy risks of prior approaches
by generating the data at the client level.

Diffusion Models. Recently, Diffusion Models (DM) (Ho et al., 2020; Nichol and
Dhariwal, 2021) have gained increasing interest in the field of generative
modeling. They demonstrate state-of-the-art image synthesis quality and,
compared to GANs, offer greater stability during training and scalability
(Dhariwal and Nichol, 2021; Stypulkowski et al., 2024; Rombach et al., 2022;
Ho et al., 2022; Sauer et al., 2023). DMs have been applied to various image
processing applications, including super-resolution, image inpainting, and
semantic segmentation (Saharia et al., 2022c; Li et al., 2022b; Saharia et
al., 2022a; Baranchuk et al., 2021). Notably, there has been a recent
development of high-resolution text-to-image DMs such as Stable Diffusion (SD)
(Rombach et al., 2022), DALL-E 2 (Ramesh et al., 2022), Imagen (Saharia et
al., 2022b), and GLIDE (Nichol et al., 2021). Recent works have demonstrated
that augmenting training data with synthetic data generated using text-to-
image DMs improves zero-shot and few-shot image classification performance (He
et al., 2022; Trabucco et al., 2023), as well as ImageNet classification
accuracy and robustness (Azizi et al., 2023; Sariyildiz et al., 2022; Bansal
and Grover, 2023).

##  3\. Background

Figure 1. Overview of Gen-FedSD.

###  3.1. Diffusion Models

Diffusion Models (DMs) (Ho et al., 2020; Nichol and Dhariwal, 2021) operate by
gradually transforming a clean image into pure noise through a process of
forward diffusion, followed by learning to recover the original clean image
from the pure noise in reverse diffusion. In the forward diffusion process, a
Gaussian noise with zero mean and variance $\beta_{t}$ is slowly added in $T$
timesteps to degrade a clean image (${\bm{x}}_{0}\sim q({\bm{x}}_{0})$) and
ultimately converge into pure Gaussian noise at step $T$ (${\bm{x}}_{T}$). The
noisy image at each timestep $t$ from the previous timestep $t-1$ can be
derived using the following equation:

$\displaystyle
q({\bm{x}}_{t}|{\bm{x}}_{t-1})=\mathcal{N}({\bm{x}}_{t};\sqrt{1-\beta_{t}}{\bm{x}}_{t-1},\beta_{t}{\bm{I}}),$

where $t\in[1,T]$ and $0<\beta_{1:T}<1$ denote the noise scale scheduling. In
the reverse diffusion process, a noise predictor model
${\bm{\varepsilon}}_{\theta}$ is trained to predict the noise
${\bm{\varepsilon}}_{t}$ at each timestep $t$ using the following loss
function:

$\displaystyle\mathcal{L}={\mathbb{E}}_{t,{\bm{x}}_{0},{\bm{\varepsilon}}}[\left\|{\bm{\varepsilon}}_{t}-{\bm{\varepsilon}}_{\theta}({\bm{x}}_{t},t)\right\|_{2}^{2}].$

For further information about DMs, we refer readers to (Yang et al., 2023; Cao
et al., 2024).

###  3.2. Image Generation using Stable Diffusion

Stable Diffusion (SD) is a type of Latent Diffusion Model (LDM) (Rombach et
al., 2022) where the denoising process occurs in the latent space of robust
pre-trained Variational Autoencoders (VAEs) (Kingma and Welling, 2013; Razavi
et al., 2019), as opposed to the original pixel space. Notably, SD
incorporates cross-attention layers into its model architecture, providing the
capability for general conditioning inputs on image generation, such as text
or bounding boxes. To generate an image using input text, SD utilizes the pre-
trained CLIP text encoder (Radford et al., 2021) to obtain text embeddings.
Subsequently, these text embeddings are fed into the model and cross-attention
layers, serving as a conditioning signal for image generation. In our work,
each client leverages a state-of-the-art pre-trained SD to generate its
missing data points, relative to the global data distribution, via input text
prompts. For more detailed discussion about text-to-image DMs we refer readers
to (Zhang et al., 2023b).

###  3.3. Federated Learning

In federated learning, a set of clients denoted as $S$ collaborate to train a
machine learning model $f(\cdot;{\bm{\theta}})$ under the orchestration of a
central server. At each communication round $r$, a random fraction $C\in(0,1]$
of clients is selected. The server then distributes the global model’s
parameters ${\bm{\theta}}_{r}^{g}$ to the selected clients $S_{r}$ and each
client $k\in S_{r}$ independently updates the model based on its private
dataset ${\mathcal{D}}_{k}$. Subsequently, the clients transmit the updated
parameters ($\\{{\widehat{\bm{\theta}}_{k}}\\}_{k\in S_{r}}$) back to the
sever to update the global model. FedAvg (McMahan et al., 2017), which has
been the de facto federated learning method, employs a straightforward
aggregation for updating the global model, as denoted below:

$\displaystyle{\bm{\theta}}_{r+1}^{g}=\sum_{k\in|S_{r}|}\frac{|{\mathcal{D}}_{k}|}{\sum_{k\in|S_{r}|}|{\mathcal{D}}_{k}|}{\widehat{\bm{\theta}}_{k}}.$

This process continues for a total of $R$ communication rounds.

##  4\. Gen-FedSD

###  4.1. Overview

Figure 1 illustrates the overall process of Gen-FedSD, which consists of three
key steps. First, the clients receive all the class labels’ names from the
server. Second, the clients apply prompt engineering techniques to transform
the received class labels’ names into text prompts. In the third step, the
clients utilize a state-of-the-art pre-trained SD to synthesize custom images,
addressing local data distribution disparities and gaps. Subsequently, the
clients augment their local data with the generated synthetic data and
initiate the federation. The following sections provide detailed explanations
for each step.

(a)

(b)

Figure 2. Illustration of clients data distribution for the CIFAR-10 dataset
before and after augmentation with Gen-FedSD. In this example, 20 clients are
utilized, partitioning CIFAR-10 Non-IID with a Dirichlet distribution
(Dir(0.5)). Prior to augmentation, the local distributions of clients are
heterogeneous (a), whereas after augmentation, the unique gaps in each
client’s local distribution are filled, resulting in a final locally augmented
dataset that is independent and identically distributed (IID) for each client
(b).

###  4.2. Steps 1-2: Client-level Prompt Generation

Utilizing the received class labels’ names from the server, the clients
generate text prompts that describe each class. Various prompt engineering
techniques exist, including the use of Large Language Models (LLMs) (Zhang et
al., 2023a) or CLIP (Radford et al., 2021). Interested readers can refer to
(Gu et al., 2023) for a more comprehensive exploration of these techniques.
Given that Stable Diffusion employs the CLIP text encoder for prompt intake,
we adopt the original prompt engineering technique used for CLIP in our work.
To obtain prompts, we apply natural language templates $\mathcal{M}$ proposed
in CLIP to a given class label $y$. For instance, if $M(y)=$ ”a photo of a
$y$” where $M\subset\mathcal{M}$ and the class label is $y=\text{cat}$, the
prompt would be ”this is a photo of a cat.”

###  4.3. Step 3: Client-level Data Generation and Augmentation

In this step, the clients leverage a state-of-the-art pre-trained SD (Rombach
et al., 2022) to synthesize images in a manner that effectively renders their
local data IID. Specifically, for client $k$, let the class labels it owns be
$\mathcal{Y}_{in}=\\{y|y\in{\mathcal{D}}_{k}\\}$, and the class labels it does
not own be $\mathcal{Y}_{out}=\\{y|y\notin{\mathcal{D}}_{k}\\}$. The total
class labels are denoted as
$\mathcal{Y}=\mathcal{Y}_{in}\cup\mathcal{Y}_{out}$. The client determines the
maximum number of images per class it has across all classes it owns
$n_{max}$, i.e., $n_{max}=\underset{y\in\mathcal{Y}_{in}}{\mathrm{max}}\
|\\{y\in D^{i}_{train}\\}|$, and generate $n_{max}-|\\{y\in D_{k}\\}|$
synthetic data for the classes it owns and $n_{max}$ synthetic data for the
classes it does not own. This ensures that the final augmented local dataset
$D_{aug}$, which combines the entire generated synthetic dataset $D_{syn}$
with the local dataset $D_{local}$ (i.e., $D_{aug}=D_{local}\cup D_{syn}$),
becomes IID. To illustrate this further, consider an example where a client
has 250 images of cats and 100 images of dogs, and the total global classes
are cat, dog, and frog. The generated synthetic dataset for this client will
include 150 images of dogs and 250 images of frogs. Figure 2 visualizes the
local data distribution of clients before and after augmentation for a
CIFAR-10 dataset example. After clients augmented their local dataset, they
start the federation and locally train the global model on their augmented
local datasets $D_{aug}$. Algorithm 1 outlines the dataset generation process
for each client.

Remarks. It is noteworthy to mention the following remarks:

  * •

The privacy implications of our proposed method are equivalent to FedAvg and
most existing FL methods that require model exchanges between the server and
clients. Notably, sharing the total classes’ names with the clients does not
pose any privacy issues. In FL, the server possesses the knowledge of the
total classes’ names in order to design the neural network architecture but
lacks any information about the local private dataset of each client. In our
method, the server only shares the total classes’ names with the clients, and
clients construct their local synthesized data based on their specific data
distribution disparities.

  * •

On-device inference of foundational models such as CLIP and SD is feasible.
Recently, Qualcomm Technologies, Inc. has publicly released a demo for on-
device inference of Stable Diffusion
111https://www.qualcomm.com/news/onq/2023/02/worlds-first-on-device-
demonstration-of-stable-diffusion-on-android.

Algorithm 1 Data Generation for Each Client

0: Stable Diffusion Model SD, client $k$, $\mathcal{Y}$, $\mathcal{Y}_{in}$,
$\mathcal{Y}_{out}$, prompt templates $\mathcal{M}$.

1: $n_{max}\leftarrow\underset{y\in\mathcal{Y}_{in}}{\mathrm{max}}\ |\\{y\in
D_{k}\\}|$

2: $D_{syn}\leftarrow\emptyset$

3: for each $y\in\mathcal{Y}$ do

4: if $y\in\mathcal{Y}_{out}$ then

5: $D\leftarrow$ generate $n_{max}$ synthetic data by prompting
$\text{SD}(M(y))$

6: else if $y\in\mathcal{Y}_{in}$ then

7: $D\leftarrow$ generate $n_{max}-|\\{y\in D_{k}\\}|$ synthetic data by
prompting $\text{SD}(M(y))$

8: end if

9: $D_{syn}\leftarrow D_{syn}\cup D$

10: end for

##  5\. Experiments

###  5.1. Experimental Setup

Dataset and Architecture. We conduct experiments on CIFAR-10 and CIFAR-100
(Krizhevsky et al., 2009) datasets. CIFAR-10 contains 50,000 32$\times$32 RGB
images across 10 different classes with a 10,000 test dataset. CIFAR-100
contains 50,000 32$\times$32 RGB images of 100 distinct objects with a 10,000
test dataset. We adopt the smallest version of compact convolutional
transformer (CCT-2) (Hassani et al., 2021) in our experiments for both CIFAR10
and CIFAR-100 datasets.

Compared Methods and Evaluation Metric. We compare our method against four
state-of-the-art FL algorithms, including FedAvg (McMahan et al., 2017),
FedProx (Li et al., 2020), FedNova (Wang et al., 2020a), and Scaffold
(Karimireddy et al., 2020). We use the average global model’s top-1 accuracy
on the test dataset over the last $10$ rounds as the evaluation metric
(Morafah et al., 2023). We run each experiment 3 times with different random
seeds and report the mean and standard deviation.

FL Settings. For both CIFAR-10 and CIFAR-100 datasets, we simulate a federated
learning setting with 100 clients, sample rate 0.1, local batch size 64, and
AdamW local optimizer. The number of communication rounds for CIFAR-10 and
CIFAR-100 is 100 and 200, respectively. We also fix the number local updates
to 150 and 100 for CIFAR-10 and CIFAR-100, respectively 222Fixing the number
of local updates is an algorithmic choice in our setting to have a fair
comparison.. We realize data heterogeneity using Dirichlet distribution with
concentration paramter $\alpha$, where lower $\alpha$ results into more
heterogeneous data partitions. More details about Dirichlet-based data
partitioning can found in (Li et al., 2021; Morafah et al., 2023).

Image Generation Settings. We download the “CompVis/stable-diffusion-v1-4”
pre-trained Stable Diffusion model checkpoint to generate the images. We adopt
20 inference steps and a guidance scale of 7.

Prompt Templates. Data diversity has been shown to enhance model
generalization in both visual (Chen et al., 2020) and language domains
(Radford et al., 2019). Employing diverse prompts is a method to generate a
wider variety of images (Shipard et al., 2023; He et al., 2022). In our
experiment, we utilize two different prompt designs: (1) Without a diverse
prompt design, i.e., employing a fixed template (’a photo of a class’). (2)
With a diverse prompt design, where for each image generation, a prompt
template is randomly selected from a pool of options 333The pool of prompt
options is adopted from the original CLIP implementation, available at
https://github.com/openai/CLIP/blob/main/data/prompts.md..

Implementation. We implement our code using the FedZoo open source library
(Morafah et al., 2023) in PyTorch. For Stable Diffusion, we use the open
source Diffusers (von Platen et al., 2022a) library from Hugging Face.

###  5.2. Performance Evaluation

Tables 1 and 2 show the results on CIFAR-10 and CIFAR-100 for the two
different prompt templates we discussed, respectively. We can make several
interesting observations.

All vanilla FL baselines suffer significantly from data heterogeneity, and the
performance degradation is more significant for higher heterogeneity levels.
Furthermore, vanilla-FedProx, -FedNova, and -Scaffold are more severely
affected by data heterogeneity compared to FedAvg, specially on CIFAR-100
dataset. This further points out the importance of addressing data
heterogeneity problem in federated learning. Surprisingly, Gen-FedSD by simply
augmenting the clients local dataset with synthetic images to make them IID
substantially enhances the performance for each FL baseline. For example, the
performance of Scaffold has been improved by $34\%$ on CIFAR-100 Dir(0.05),
and FedProx has been improved by $41\%$ on CIFAR-10 Dir(0.1). This clearly
demonstrate the effectiveness of Gen-FedSD to address the data heterogeneity
problem by successfully filling in the clients’ unique local distribution
mismatches. Another interesting observation is that while vanilla-FedProx,
-FedNova, and -Scaffold underperform vanilla-FedAvg, they outperform FedAvg
when Gen-FedSD is applied on many cases. Additionally, it is worth
highlighting that Ged-FedSD with diverse prompt templates achieves better
performance compared to without diverse prompt templates on many cases. This
verifies that diverse prompt templates can result into diversified data
generation and enhanced generalization of the models.

Table 1. Performance results on CIFAR-10 dataset.

Baseline | Vanilla/Gen-FedSD | Dir (0.5) | Dir (0.1) | Dir (0.05)
---|---|---|---|---
FedAvg | Vanilla |  $58.57\pm 0.77$% |  $37.98\pm 1.53$% |  $25.78\pm 0.94$%
+Gen-FedSD (w/o diversity) |  $\bm{70.70\pm 0.62}$% |  $\bm{58.69\pm 1.71}$% |  $\bm{54.38\pm 1.93}$%
+Gen-FedSD (w diversity) |  $\bm{71.41\pm 0.45}$% |  $\bm{61.21\pm 1.74}$% |  $\bm{56.42\pm 0.35}$%
FedProx | Vanilla |  $27.42\pm 1.84$% |  $20.51\pm 1.79$% |  $18.05\pm 1.98$%
+Gen-FedSD (w/o diversity) |  $\bm{70.26\pm 0.14}$% |  $\bm{61.59\pm 0.98}$% |  $\bm{54.85\pm 0.95}$%
+Gen-FedSD (w diversity) |  $\bm{71.01\pm 0.17}$% |  $\bm{61.43\pm 1.27}$% |  $\bm{59.41\pm 0.76}$%
FedNova | Vanilla |  $28.52\pm 1.01$% |  $24.61\pm 1.24$% |  $19.37\pm 2.12$%
+Gen-FedSD (w/o diversity) |  $\bm{70.06\pm 0.34}$% |  $\bm{61.45\pm 1.29}$% |  $\bm{55.85\pm 2.19}$%
+Gen-FedSD (w diversity) |  $\bm{71.06\pm 0.10}$% |  $\bm{63.82\pm 0.09}$% |  $\bm{57.92\pm 0.97}$%
Scaffold | Vanilla |  $26.65\pm 0.45$% |  $17.71\pm 1.71$% |  $14.14\pm 1.48$%
+Gen-FedSD (w/o diversity) |  $\bm{76.39\pm 0.10}$% |  $\bm{67.46\pm 1.17}$% |  $\bm{59.04\pm 2.35}$%
+Gen-FedSD (w diversity) |  $\bm{76.61\pm 0.26}$% |  $\bm{67.09\pm 0.04}$% |  $\bm{61.91\pm 3.31}$%

Table 2. Performance results on CIFAR-100 dataset.

Baseline | Vanilla/Gen-FedSD | Dir (0.5) | Dir (0.1) | Dir (0.05)
---|---|---|---|---
FedAvg | Vanilla |  $40.36\pm 0.39$% |  $30.38\pm 0.78$% |  $24.52\pm 0.37$%
+Gen-FedSD (w/o diversity) |  $\bm{46.45\pm 0.30}$% | $\bm{36.23\pm 0.78\%}$ |  $\bm{31.42\pm 0.24}$%
+Gen-FedSD (w diversity) |  $\bm{46.91\pm 0.50}$% |  $\bm{37.06\pm 0.20}$% |  $\bm{31.91\pm 0.25}$%
FedProx | Vanilla |  $10.39\pm 1.27$% |  $8.12\pm 0.72$% |  $6.57\pm 0.07$%
+Gen-FedSD (w/o diversity) |  $\bm{47.36\pm 0.03}$% |  $\bm{39.69\pm 0.18}$% |  $\bm{35.29\pm 0.80}$%
+Gen-FedSD (w diversity) |  $\bm{47.44\pm 0.10}$% |  $\bm{39.22\pm 0.31}$% |  $\bm{36.14\pm 0.55}$%
FedNova | Vanilla |  $8.71\pm 1.31$% |  $7.48\pm 0.48$% |  $6.83\pm 0.19$%
+Gen-FedSD (w/o diversity) |  $\bm{46.98\pm 0.03}$% |  $\bm{39.24\pm 0.41}$% |  $\bm{35.86\pm 0.14}$%
+Gen-FedSD (w diversity) |  $\bm{47.44\pm 0.50}$% |  $\bm{39.83\pm 0.33}$% |  $\bm{36.10\pm 0.27}$%
Scaffold | Vanilla |  $4.49\pm 0.33$% |  $3.32\pm 0.05$% |  $2.63\pm 0.22$%
+Gen-FedSD (w/o diversity) |  $\bm{52.25\pm 0.33}$% |  $\bm{42.70\pm 0.61}$% |  $\bm{36.79\pm 0.11}$%
+Gen-FedSD (w diversity) |  $\bm{52.43\pm 0.06}$% |  $\bm{43.77\pm 0.02}$% |  $\bm{38.42\pm 0.02}$%

Table 3. Communication costs required to reach the designated target accuracy
for CIFAR-10 dataset.

Baseline | Vanilla/Gen-FedSD | Dir (0.5) | Dir (0.1) | Dir (0.05)
---|---|---|---|---
FedAvg | Vanilla |  $567.44$ MB |  $408.56$ MB |  $340.46$ MB
+Gen-FedSD (w/o diversity) |  $\bm{22.69}$ MB |  $\bm{22.69}$ MB |  $\bm{22.69}$ MB
+Gen-FedSD (w diversity) |  $\bm{22.69}$ MB |  $\bm{22.69}$ MB |  $\bm{22.69}$ MB
FedProx | Vanilla |  $1588.84$ MB |  $1134.89$ MB |  $499.35$ MB
+Gen-FedSD (w/o diversity) |  $\bm{22.69}$ MB |  $\bm{22.69}$ MB |  $\bm{22.69}$ MB
+Gen-FedSD (w diversity) |  $\bm{22.69}$ MB |  $\bm{22.69}$ MB |  $\bm{22.69}$ MB
FedNova | Vanilla |  $907.91$ MB |  $453.95$ MB |  $794.42$ MB
+Gen-FedSD (w/o diversity) |  $\bm{22.69}$ MB |  $\bm{22.69}$ MB |  $\bm{22.69}$ MB
+Gen-FedSD (w diversity) |  $\bm{22.69}$ MB |  $\bm{22.69}$ MB |  $\bm{22.69}$ MB
Scaffold | Vanilla |  $794.42$ MB |  $1361.87$ MB |  $1134.89$ MB
+Gen-FedSD (w/o diversity) |  $\bm{22.69}$ MB |  $\bm{22.69}$ MB |  $\bm{22.69}$ MB
+Gen-FedSD (w diversity) |  $\bm{22.69}$ MB |  $\bm{22.69}$ MB |  $\bm{22.69}$ MB

###  5.3. Communication Cost

To measure the communication cost, we set specific target accuracies and
evaluate each baseline on the number of communication costs required to reach
these targets. Specifically, we set the target accuracies to 25% for Dir(0.5),
20% for Dir(0.1), and 18% for Dir(0.05). Table 3 presents the communication
costs of the baselines on the CIFAR-10 dataset in MB 444The communication cost
evaluation for CIFAR-100 dataset cannot be accomplished since the performance
results of all the baselines except FedAvg is very poor. Hence, we only
conduct the evaluation on the CIFAR-10 dataset. As evident from the table,
Gen-FedSD demonstrates significant reductions in communication costs across
all levels of data heterogeneity compared to the vanilla baselines.

##  6\. Conclusion and Future Works

In this work, we introduce “Gen-FedSD,” a novel data augmentation technique
leveraging pre-trained state-of-the-art Stable Diffusion to tackle the
challenge of data heterogeneity in federated learning. Gen-FedSD customizes
images for each client based on its unique data distribution disparities,
aiming to make it independent and identically distributed (IID) with respect
to the global data distribution. Our experiments demonstrate that Gen-FedSD
substantially enhances the performance of several state-of-the-art federated
learning algorithms across diverse datasets and Non-IID scenarios.

For future work, it would be valuable to explore different prompt engineering
techniques and factors affecting image generation quality. Further
investigations into other sources of non-iidness and how the method could be
adapted would be intriguing extensions for future research.

##  Appendix A Supplementary Materials

###  A.1. Further Experimental Settings

FL Settings and Hyper-parameters. Tables 4 and 5 summarize the details of FL
settings and hyper-parameters that we used in our federated learning
experiments for CIFAR-10 and CIFAR-100, respectively.

Table 4. Federated learning settings and hyper-parameters for CIFAR-10.

Name | Value
---|---
Dataset | CIFAR-10
Architecture | CCT-2
# parameters | 283,723
Number of Clients | 100
Sample rate | 0.1
local batch size | 64
local update iterations | 150
local optimizer | AdamW
local learning rate | 5e-4
local weight decay | 3e-2

Table 5. Federated learning settings and hyper-parameters for CIFAR-100.

Name | Value
---|---
Dataset | CIFAR-100
Architecture | CCT-2
# parameters | 295,333
rounds | 200
Number of Clients | 100
Sample rate | 0.1
local batch size | 64
local update iterations | 100
local optimizer | AdamW
local learning rate | 6e-4
local weight decay | 6e-2

Dataset Generation Setting. We utilized Stable Diffusion (Rombach et al.,
2022) model and the pre-trained stable-diffusion-v1-4 checkpoint from
huggingface available at https://huggingface.co/CompVis/stable-diffusion to
generate data. We used the inference code in the diffusers (von Platen et al.,
2022b) library. Table 6 summarizes the hyper-parameters we used to generated
data using Stable Diffusion.

Table 6. Inference settings for data generationg.

Name | Value
---|---
Model | Stable Diffusion
Pre-trained | “CompVis/stable-diffusion-v1-4”
torch_dtype | torch.float16
Scheduler | DPMSolverMultistepScheduler
num_inference_stepss | 20
guidance_scale | 7

Prompt Templates. We followed original CLIP prompt templates 555The prompts
are available at the official Github repository:
https://github.com/openai/CLIP/blob/main/data/prompts.md.. Table 7 summarizes
the prompt templates that we used for CIFAR-10 and CIFAR-100 datasets.

Table 7. CIFAR-10 and CIFAR-100 Prompt Templates ’a photo of a {class}.’, ’a
blurry photo of a {class}.’, ’a black and white photo of a {class}.’, ’a low
contrast photo of a {class}.’, ’a high contrast photo of a {class}.’, ’a bad
photo of a {class}.’, ’a good photo of a {class}.’, ’a photo of a small
{class}.’, ’a photo of a big {class}.’, ’a photo of the {class}.’, ’a blurry
photo of the {class}.’, ’a black and white photo of the {class}.’, ’a low
contrast photo of the {class}.’, ’a high contrast photo of the {class}.’, ’a
bad photo of the {class}.’, ’a good photo of the {class}.’, ’a photo of the
small {class}.’, ’a photo of the big {class}.’,

## References

  * (1)
  * Azizi et al. (2023) Shekoofeh Azizi, Simon Kornblith, Chitwan Saharia, Mohammad Norouzi, and David J Fleet. 2023.  Synthetic data from diffusion models improves imagenet classification.  _arXiv preprint arXiv:2304.08466_ (2023).
  * Bansal and Grover (2023) Hritik Bansal and Aditya Grover. 2023.  Leaving reality to imagination: Robust classification via generated datasets.  _arXiv preprint arXiv:2302.02503_ (2023).
  * Baranchuk et al. (2021) Dmitry Baranchuk, Ivan Rubachev, Andrey Voynov, Valentin Khrulkov, and Artem Babenko. 2021.  Label-efficient semantic segmentation with diffusion models.  _arXiv preprint arXiv:2112.03126_ (2021).
  * Cao et al. (2024) Hanqun Cao, Cheng Tan, Zhangyang Gao, Yilun Xu, Guangyong Chen, Pheng-Ann Heng, and Stan Z Li. 2024.  A Survey on Generative Diffusion Models.  _IEEE Transactions on Knowledge and Data Engineering_ (2024).
  * Chen et al. (2019) Mingqing Chen, Rajiv Mathews, Tom Ouyang, and Françoise Beaufays. 2019.  Federated learning of out-of-vocabulary words.  _arXiv preprint arXiv:1903.10635_ (2019).
  * Chen et al. (2020) Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. 2020.  A simple framework for contrastive learning of visual representations. In _International conference on machine learning_. PMLR, 1597–1607.
  * Collins et al. (2021) Liam Collins, Hamed Hassani, Aryan Mokhtari, and Sanjay Shakkottai. 2021.  Exploiting shared representations for personalized federated learning. In _International conference on machine learning_. PMLR, 2089–2099.
  * Deng et al. (2020) Yuyang Deng, Mohammad Mahdi Kamani, and Mehrdad Mahdavi. 2020.  Adaptive personalized federated learning.  _arXiv preprint arXiv:2003.13461_ (2020).
  * Dhariwal and Nichol (2021) Prafulla Dhariwal and Alexander Nichol. 2021.  Diffusion models beat gans on image synthesis.  _Advances in neural information processing systems_ 34 (2021), 8780–8794.
  * Feng et al. (2020) Jie Feng, Can Rong, Funing Sun, Diansheng Guo, and Yong Li. 2020.  PMF: A privacy-preserving human mobility prediction framework via federated learning.  _Proceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies_ 4, 1 (2020), 1–21.
  * Goetz and Tewari (2020) Jack Goetz and Ambuj Tewari. 2020.  Federated learning via synthetic data.  _arXiv preprint arXiv:2008.04489_ (2020).
  * Gu et al. (2023) Jindong Gu, Zhen Han, Shuo Chen, Ahmad Beirami, Bailan He, Gengyuan Zhang, Ruotong Liao, Yao Qin, Volker Tresp, and Philip Torr. 2023.  A systematic survey of prompt engineering on vision-language foundation models.  _arXiv preprint arXiv:2307.12980_ (2023).
  * Haddadpour and Mahdavi (2019) Farzin Haddadpour and Mehrdad Mahdavi. 2019.  On the convergence of local descent methods in federated learning.  _arXiv preprint arXiv:1910.14425_ (2019).
  * Hanzely et al. (2020) Filip Hanzely, Slavomír Hanzely, Samuel Horváth, and Peter Richtárik. 2020.  Lower bounds and optimal algorithms for personalized federated learning.  _Advances in Neural Information Processing Systems_ 33 (2020), 2304–2315.
  * Hassani et al. (2021) Ali Hassani, Steven Walton, Nikhil Shah, Abulikemu Abuduweili, Jiachen Li, and Humphrey Shi. 2021.  Escaping the big data paradigm with compact transformers.  _arXiv preprint arXiv:2104.05704_ (2021).
  * He et al. (2022) Ruifei He, Shuyang Sun, Xin Yu, Chuhui Xue, Wenqing Zhang, Philip Torr, Song Bai, and Xiaojuan Qi. 2022.  Is synthetic data from generative models ready for image recognition?  _arXiv preprint arXiv:2210.07574_ (2022).
  * Ho et al. (2020) Jonathan Ho, Ajay Jain, and Pieter Abbeel. 2020.  Denoising diffusion probabilistic models.  _Advances in neural information processing systems_ 33 (2020), 6840–6851.
  * Ho et al. (2022) Jonathan Ho, Chitwan Saharia, William Chan, David J Fleet, Mohammad Norouzi, and Tim Salimans. 2022.  Cascaded diffusion models for high fidelity image generation.  _The Journal of Machine Learning Research_ 23, 1 (2022), 2249–2281.
  * Hu et al. (2022) Shengyuan Hu, Jack Goetz, Kshitiz Malik, Hongyuan Zhan, Zhe Liu, and Yue Liu. 2022.  Fedsynth: Gradient compression via synthetic data in federated learning.  _arXiv preprint arXiv:2204.01273_ (2022).
  * Jeong et al. (2018) Eunjeong Jeong, Seungeun Oh, Hyesung Kim, Jihong Park, Mehdi Bennis, and Seong-Lyun Kim. 2018.  Communication-efficient on-device machine learning: Federated distillation and augmentation under non-iid private data.  _arXiv preprint arXiv:1811.11479_ (2018).
  * Kairouz et al. (2021) Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. 2021\.  Advances and open problems in federated learning.  _Foundations and Trends® in Machine Learning_ 14, 1–2 (2021), 1–210.
  * Karimireddy et al. (2020) Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. 2020.  Scaffold: Stochastic controlled averaging for federated learning. In _International conference on machine learning_. PMLR, 5132–5143.
  * Kingma and Welling (2013) Diederik P Kingma and Max Welling. 2013.  Auto-encoding variational bayes.  _arXiv preprint arXiv:1312.6114_ (2013).
  * Krizhevsky et al. (2009) Alex Krizhevsky, Geoffrey Hinton, et al. 2009\.  Learning multiple layers of features from tiny images.  (2009).
  * Kulkarni et al. (2020) Viraj Kulkarni, Milind Kulkarni, and Aniruddha Pant. 2020.  Survey of personalization techniques for federated learning. In _2020 Fourth World Conference on Smart Trends in Systems, Security and Sustainability (WorldS4)_. IEEE, 794–797.
  * Li et al. (2022b) Haoying Li, Yifan Yang, Meng Chang, Shiqi Chen, Huajun Feng, Zhihai Xu, Qi Li, and Yueting Chen. 2022b.  Srdiff: Single image super-resolution with diffusion probabilistic models.  _Neurocomputing_ 479 (2022), 47–59.
  * Li et al. (2022a) Qinbin Li, Yiqun Diao, Quan Chen, and Bingsheng He. 2022a.  Federated learning on non-iid data silos: An experimental study. In _2022 IEEE 38th International Conference on Data Engineering (ICDE)_. IEEE, 965–978.
  * Li et al. (2021) Qinbin Li, Bingsheng He, and Dawn Song. 2021.  Model-contrastive federated learning. In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_. 10713–10722.
  * Li et al. (2020) Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. 2020.  Federated optimization in heterogeneous networks.  _Proceedings of Machine learning and systems_ 2 (2020), 429–450.
  * Lin et al. (2020) Tao Lin, Lingjing Kong, Sebastian U Stich, and Martin Jaggi. 2020.  Ensemble distillation for robust model fusion in federated learning.  _Advances in Neural Information Processing Systems_ 33 (2020), 2351–2363.
  * McMahan et al. (2017) Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. 2017.  Communication-efficient learning of deep networks from decentralized data. In _Artificial intelligence and statistics_. PMLR, 1273–1282.
  * Morafah et al. (2023) Mahdi Morafah, Weijia Wang, and Bill Lin. 2023.  A Practical Recipe for Federated Learning Under Statistical Heterogeneity Experimental Design.  _IEEE Transactions on Artificial Intelligence_ (2023).
  * Nichol et al. (2021) Alex Nichol, Prafulla Dhariwal, Aditya Ramesh, Pranav Shyam, Pamela Mishkin, Bob McGrew, Ilya Sutskever, and Mark Chen. 2021.  Glide: Towards photorealistic image generation and editing with text-guided diffusion models.  _arXiv preprint arXiv:2112.10741_ (2021).
  * Nichol and Dhariwal (2021) Alexander Quinn Nichol and Prafulla Dhariwal. 2021.  Improved denoising diffusion probabilistic models. In _International Conference on Machine Learning_. PMLR, 8162–8171.
  * Radford et al. (2021) Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. 2021\.  Learning transferable visual models from natural language supervision. In _International conference on machine learning_. PMLR, 8748–8763.
  * Radford et al. (2019) Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. 2019\.  Language models are unsupervised multitask learners.  _OpenAI blog_ 1, 8 (2019), 9.
  * Ramaswamy et al. (2019) Swaroop Ramaswamy, Rajiv Mathews, Kanishka Rao, and Françoise Beaufays. 2019.  Federated learning for emoji prediction in a mobile keyboard.  _arXiv preprint arXiv:1906.04329_ (2019).
  * Ramesh et al. (2022) Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen. 2022.  Hierarchical text-conditional image generation with clip latents.  _arXiv preprint arXiv:2204.06125_ 1, 2 (2022), 3.
  * Razavi et al. (2019) Ali Razavi, Aaron Van den Oord, and Oriol Vinyals. 2019.  Generating diverse high-fidelity images with vq-vae-2.  _Advances in neural information processing systems_ 32 (2019).
  * Reddi et al. (2020) Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečnỳ, Sanjiv Kumar, and H Brendan McMahan. 2020.  Adaptive federated optimization.  _arXiv preprint arXiv:2003.00295_ (2020).
  * Rombach et al. (2022) Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer. 2022.  High-resolution image synthesis with latent diffusion models. In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_. 10684–10695.
  * Saharia et al. (2022a) Chitwan Saharia, William Chan, Huiwen Chang, Chris Lee, Jonathan Ho, Tim Salimans, David Fleet, and Mohammad Norouzi. 2022a.  Palette: Image-to-image diffusion models. In _ACM SIGGRAPH 2022 Conference Proceedings_. 1–10.
  * Saharia et al. (2022b) Chitwan Saharia, William Chan, Saurabh Saxena, Lala Li, Jay Whang, Emily L Denton, Kamyar Ghasemipour, Raphael Gontijo Lopes, Burcu Karagol Ayan, Tim Salimans, et al. 2022b.  Photorealistic text-to-image diffusion models with deep language understanding.  _Advances in Neural Information Processing Systems_ 35 (2022), 36479–36494.
  * Saharia et al. (2022c) Chitwan Saharia, Jonathan Ho, William Chan, Tim Salimans, David J Fleet, and Mohammad Norouzi. 2022c.  Image super-resolution via iterative refinement.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ 45, 4 (2022), 4713–4726.
  * Saputra et al. (2019) Yuris Mulya Saputra, Dinh Thai Hoang, Diep N Nguyen, Eryk Dutkiewicz, Markus Dominik Mueck, and Srikathyayani Srikanteswara. 2019.  Energy demand prediction with federated learning for electric vehicle networks. In _2019 IEEE global communications conference (GLOBECOM)_. IEEE, 1–6.
  * Sariyildiz et al. (2022) Mert Bulent Sariyildiz, Karteek Alahari, Diane Larlus, and Yannis Kalantidis. 2022.  Fake it till you make it: Learning (s) from a synthetic ImageNet clone.  _arXiv preprint arXiv:2212.08420_ (2022).
  * Sattler et al. (2021) Felix Sattler, Tim Korjakow, Roman Rischke, and Wojciech Samek. 2021.  Fedaux: Leveraging unlabeled auxiliary data in federated learning.  _IEEE Transactions on Neural Networks and Learning Systems_ (2021).
  * Sauer et al. (2023) Axel Sauer, Dominik Lorenz, Andreas Blattmann, and Robin Rombach. 2023.  Adversarial Diffusion Distillation.  _arXiv preprint arXiv:2311.17042_ (2023).
  * Shin et al. (2020) MyungJae Shin, Chihoon Hwang, Joongheon Kim, Jihong Park, Mehdi Bennis, and Seong-Lyun Kim. 2020.  Xor mixup: Privacy-preserving data augmentation for one-shot federated learning.  _arXiv preprint arXiv:2006.05148_ (2020).
  * Shipard et al. (2023) Jordan Shipard, Arnold Wiliem, Kien Nguyen Thanh, Wei Xiang, and Clinton Fookes. 2023.  Diversity is Definitely Needed: Improving Model-Agnostic Zero-shot Classification via Stable Diffusion. In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_. 769–778.
  * Singh and Jaggi (2020) Sidak Pal Singh and Martin Jaggi. 2020.  Model fusion via optimal transport.  _Advances in Neural Information Processing Systems_ 33 (2020), 22045–22055.
  * Stypulkowski et al. (2024) Michal Stypulkowski, Konstantinos Vougioukas, Sen He, Maciej Zieba, Stavros Petridis, and Maja Pantic. 2024.  Diffused heads: Diffusion models beat GANs on talking-face generation. In _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision_. 5091–5100.
  * Trabucco et al. (2023) Brandon Trabucco, Kyle Doherty, Max Gurinas, and Ruslan Salakhutdinov. 2023.  Effective data augmentation with diffusion models.  _arXiv preprint arXiv:2302.07944_ (2023).
  * Vahidian et al. (2023) Saeed Vahidian, Mahdi Morafah, Weijia Wang, Vyacheslav Kungurtsev, Chen Chen, Mubarak Shah, and Bill Lin. 2023.  Efficient distribution similarity identification in clustered federated learning via principal angles between client data subspaces. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 37. 10043–10052.
  * von Platen et al. (2022a) Patrick von Platen, Suraj Patil, Anton Lozhkov, Pedro Cuenca, Nathan Lambert, Kashif Rasul, Mishig Davaadorj, and Thomas Wolf. 2022a.  Diffusers: State-of-the-art diffusion models.  https://github.com/huggingface/diffusers.
  * von Platen et al. (2022b) Patrick von Platen, Suraj Patil, Anton Lozhkov, Pedro Cuenca, Nathan Lambert, Kashif Rasul, Mishig Davaadorj, and Thomas Wolf. 2022b.  Diffusers: State-of-the-art diffusion models.
  * Wang et al. (2020b) Hongyi Wang, Mikhail Yurochkin, Yuekai Sun, Dimitris Papailiopoulos, and Yasaman Khazaeni. 2020b.  Federated learning with matched averaging.  _arXiv preprint arXiv:2002.06440_ (2020).
  * Wang et al. (2020a) Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H Vincent Poor. 2020a.  Tackling the objective inconsistency problem in heterogeneous federated optimization.  _Advances in neural information processing systems_ 33 (2020), 7611–7623.
  * Wang et al. (2018) Tongzhou Wang, Jun-Yan Zhu, Antonio Torralba, and Alexei A Efros. 2018.  Dataset distillation.  _arXiv preprint arXiv:1811.10959_ (2018).
  * Yang et al. (2023) Ling Yang, Zhilong Zhang, Yang Song, Shenda Hong, Runsheng Xu, Yue Zhao, Wentao Zhang, Bin Cui, and Ming-Hsuan Yang. 2023.  Diffusion models: A comprehensive survey of methods and applications.  _Comput. Surveys_ 56, 4 (2023), 1–39.
  * Yoon et al. (2021) Tehrim Yoon, Sumin Shin, Sung Ju Hwang, and Eunho Yang. 2021.  Fedmix: Approximation of mixup under mean augmented federated learning.  _arXiv preprint arXiv:2107.00233_ (2021).
  * Yurochkin et al. (2019) Mikhail Yurochkin, Mayank Agarwal, Soumya Ghosh, Kristjan Greenewald, Nghia Hoang, and Yasaman Khazaeni. 2019.  Bayesian nonparametric federated learning of neural networks. In _International conference on machine learning_. PMLR, 7252–7261.
  * Zhang et al. (2023b) Chenshuang Zhang, Chaoning Zhang, Mengchun Zhang, and In So Kweon. 2023b.  Text-to-image diffusion model in generative ai: A survey.  _arXiv preprint arXiv:2303.07909_ (2023).
  * Zhang et al. (2023a) Tuo Zhang, Tiantian Feng, Samiul Alam, Dimitrios Dimitriadis, Mi Zhang, Shrikanth S. Narayanan, and Salman Avestimehr. 2023a.  GPT-FL: Generative Pre-trained Model-Assisted Federated Learning.  arXiv:2306.02210 [cs.LG]
  * Zhao et al. (2018) Yue Zhao, Meng Li, Liangzhen Lai, Naveen Suda, Damon Civin, and Vikas Chandra. 2018.  Federated learning with non-iid data.  _arXiv preprint arXiv:1806.00582_ (2018).
  * Zhou et al. (2020) Yanlin Zhou, George Pu, Xiyao Ma, Xiaolin Li, and Dapeng Wu. 2020.  Distilled one-shot federated learning.  _arXiv preprint arXiv:2009.07999_ (2020).
  * Zhu et al. (2021b) Hangyu Zhu, Jinjin Xu, Shiqing Liu, and Yaochu Jin. 2021b.  Federated learning on non-IID data: A survey.  _Neurocomputing_ 465 (2021), 371–390.
  * Zhu et al. (2021a) Zhuangdi Zhu, Junyuan Hong, and Jiayu Zhou. 2021a.  Data-free knowledge distillation for heterogeneous federated learning. In _International conference on machine learning_. PMLR, 12878–12889.


# On the Difference of Atom-Bond Sum-Connectivity and Atom-Bond-Connectivity
Indices

Akbar Alia,***Corresponding author, Ivan Gutmanb, Izudin Redžepovićc,
Jaya Percival Mazorodzed, Abeer M. Albalahia,
Amjad E. Hamzaa

###### Abstract

The atom-bond-connectivity (ABC) index is one of the well-investigated degree-
based topological indices. The atom-bond sum-connectivity (ABS) index is a
modified version of the ABC index, which was introduced recently. The primary
goal of the present paper is to investigate the difference between the
aforementioned two indices, namely $ABS-ABC$. It is shown that the difference
$ABS-ABC$ is positive for all graphs of minimum degree at least $2$ as well as
for all line graphs of those graphs of order at least $5$ that are different
from the path and cycle graphs. By means of computer search, the difference
$ABS-ABC$ is also calculated for all trees of order at most $15$.

##  1 Introduction

In this paper we consider finite simple graphs (i.e., graphs without directed,
weighted, and multiple edges, and without self-loops). Let $G$ be such a
graph. In order to avoid trivialities, it will be assumed that $G$ is
connected. Its vertex set is $\mathbf{V}(G)$ and its edge set is
$\mathbf{E}(G)$. The order and size of $G$ are $|\mathbf{V}(G)|=n$ and
$|\mathbf{E}(G)|=m$, respectively. By an $n$-vertex graph, we mean a graph of
order $n$. The degree $d_{u}=d_{u}(G)$ of the vertex $u\in\mathbf{V}(G)$ is
the number of vertices adjacent to $u$. The edge connecting the vertices $u$
and $v$ will be denoted by $uv$. A vertex with degree one is known as a
pendent vertex.

For graph-theoretical terminology and notation used without being defined, we
refer the readers to the books [8, 9, 27]

In the early years of mathematical chemistry, Milan Randić invented a
topological index [25] that eventually became one of the most successfully
applied graph-based molecular structure descriptors [21, 22, 26]. It is
nowadays called “connectivity index” or “Randić index” and is defined as

$R=R(G)=\sum_{uv\in\mathbf{E}(G)}\frac{1}{\sqrt{d_{u}\,d_{v}}}\,.$

Much later, Zhou and Trinajstić [28] proposed to consider the variant of the
connectivity index, in which multiplication is replaced by summation, named
“sum-connectivity index”, defined as

$SC=SC(G)=\sum_{uv\in\mathbf{E}(G)}\frac{1}{\sqrt{d_{u}+d_{v}}}\,.$

The same authors examined the relations between $R$ and $SC$ [29].

In 1998, Estrada et al. [12] conceived another modification of the
connectivity index, called “atom-bond-connectivity index”, defined as

$ABC=ABC(G)=\sum_{uv\in\mathbf{E}(G)}\sqrt{\frac{d_{u}+d_{v}-2}{d_{u}\,d_{v}}}\,.$

This molecular descriptor differs from the original connectivity index by the
expression $d_{u}+d_{v}-2$, which is just the degree of the edge $uv$ (=
number of edges incident to $uv$).

Soon it was established that the $ABC$ index has valuable applicative
properties [16]. Its mathematical features were also much investigated, see
the recent papers [11, 14, 20], the review [3], and the references cited
therein. Especially intriguing is the fact that the apparently simple problem
of finding the connected $n$-vertex graph(s) with minimum $ABC$ index remained
unsolved for about a decade [18].

Quite recently, the sum-connectivity analogue of the $ABC$ index was put
forward, defined as

$ABS=ABS(G)=\sum_{uv\in\mathbf{E}(G)}\sqrt{\frac{d_{u}+d_{v}-2}{d_{u}+d_{v}}}$

and named “atom-bond sum-connectivity index” [4]. Until now, only a limited
number of properties of the $ABS$ index were determined. In [4], the authors
determined graphs having the minimum/maximum values of the $ABS$ index among
all (i) general graphs (ii) (molecular) trees, with a fixed order; parallel
results for the case of unicyclic graphs were obtained in the paper [5], where
chemical applications of the $ABS$ index were also reported. (The general
$ABS$ index corresponding to the general $ABC$ index [13, 10, 6] was also
proposed in [5]; besides, see [1, 2].) Alraqad et al. [7] addressed the
problem of finding graphs attaining the minimum $ABS$ index over the class of
all trees having given order or/and a fixed number of pendent vertices.
Additional detail about the known mathematical properties of the $ABS$ index
can be found in the recent papers [15, 19, 23, 24].

As well known, if a graph $G$ has components $G_{1}$ and $G_{2}$, then
$ABC(G)=ABC(G_{1})+ABC(G_{2})$ and $ABS(G)=ABS(G_{1})+ABS(G_{2})$. As a
consequence of this, denoting by $P_{2}$ the graph of order 2 and size 1, the
following holds.
(a) If $G$ is any graph, and $G^{+}$ is a graph whose components are $G$, an
arbitrary number of isolated vertices, and an arbitrary number of
$P_{2}$-graphs, then $ABC(G)=ABC(G^{+})$ and $ABS(G)=ABS(G^{+})$.
(b) if $G^{++}$ is a graph whose components are $G$, an arbitrary number of
isolated vertices, an arbitrary number of $P_{2}$-graphs, and an arbitrary
number of cycles of arbitrary size, then

$ABC(G)-ABS(G)=ABC(G^{++})-ABS(G^{++}).$

In order to avoid these trivialities, in what follows we consider only
connected graphs. An obvious question is how the two closely related molecular
descriptors $ABC$ and $ABS$ are related. In this paper, we provide some
answers to this question. More precisely, we prove that the difference $ABS-
ABC$ is positive for all graphs of minimum degree at least $2$ as well as for
all line graphs of those graphs of order at least $5$ that are different from
the path and cycle graphs. We also calculate the difference $ABS-ABC$ for all
trees of order at most $15$ by utilizing computer software.

##  2 Main Results

We start this section with a simple but notable result that if the minimum
degree of a graph $G$ is at least $2$ then the ABS index of $G$ cannot be
lesser than the ABC index of $G$.

######  Proposition 2.1.

Let $G$ be a connected non-trivial graph of order $n$, without pendent
vertices. Then

$ABC(G)\leq ABS(G).$

Equality holds if and only if $G\cong C_{n}$, where $C_{n}$ is the $n$-vertex
cycle.

###### Proof.

For every edge $uv\in E(G)$, note that $d_{u}\,d_{v}\geq d_{u}+d_{v}$ with
equality if and only if $d_{u}=d_{v}=2$ because $\min\\{d_{u},d_{v}\\}\geq 2$.

If the order of a graph $G$ is one or two, then the equality $ABC(G)=ABS(G)=0$
holds in a trivial manner.

######  Proposition 2.2.

Let $G$ be a connected graph possessing a vertex $x$ of degree $2$. Construct
the graph $G^{\star}$ by inserting a new vertex $y$ on an edge incident to
$x$. Evidently, the degree of $y$ is also $2$. Then

$ABC(G)-ABS(G)=ABC(G^{\star})-ABS(G^{\star})\,.$ (1)

###### Proof.

Bearing in mind the way in which the graph $G^{\star}$ was constructed, we see
that

$ABC(G^{\star})=ABC(G)+\sqrt{\frac{d_{x}+d_{y}-2}{d_{x}\,d_{y}}}=ABC(G)+\frac{1}{\sqrt{2}}$

and

$ABS(G^{\star})=ABS(G)+\sqrt{\frac{d_{x}+d_{y}-2}{d_{x}+d_{y}}}=ABS(G)+\frac{1}{\sqrt{2}}\,.$

Proposition 2.2 implies that if there is a graph $G$ of order $n$, possessing
a vertex of degree 2, for which $ABC(G)-ABS(G)=\Theta$, then for any $p\geq 1$
there exist graphs of order $n+p$ with the same $\Theta$-value.

The situation with graphs possessing pendent vertices is much less simple. In
what follows we present our results pertaining to trees. By means of computer
search we established the following.

######  Observation 2.3.

(a) All trees of order $n$ , $3\leq n\leq 10$, have the property $ABC>ABS$.
(b) The smallest tree for which $ABC<ABS$ is depicted in Fig. 1. For $n=11$,
this tree is unique satisfying $ABC<ABS$.
(c) For $n=12,13,14$, and $15$, there exist, respectively, $6,31,134$, and
$564$ distinct $n$-vertex trees for which $ABC<ABS$.
(d) The tree depicted in Fig. 1 possess vertices of degree $2$. Therefore,
from Proposition 2.2 it follows that there exist $n$-vertex trees with
property $ABS>ABC$ for any $n\geq 11$.

Figure 1: The smallest tree for which $ABC<ABS$.

######  Observation 2.4.

No tree of order $n$ , $3\leq n\leq 15$, has the property $ABC=ABS$. However,
there is a family of four $15$-vertex trees, shown in Fig. 2, whose $ABC$\-
and $ABS$-values are remarkably close. For each of these trees: $ABC\approx
10.184232$ and $ABS\approx 10.184135$.

Figure 2: A family of trees with nearly equal $ABC$\- and $ABS$-values.

Next, we show that the inequality $ABS>ABC$ is satisfied by a reasonably large
class of graphs, namely by the line graphs. If $G$ is the line graph of a
connected $n$-vertex graph $K$ such that $2\leq n\leq 4$, then from the
discussion made in the previous part of this section one can directly obtain
the classes of graphs satisfying (i) $ABS(G)>ABC(G)$, (ii) $ABS(G)<ABC(G)$,
(iii) $ABS(G)=ABC(G)$. Consequently, we assume that $n\geq 5$.

######  Theorem 2.5.

If $G$ is the line graph of a connected $n$-vertex graph $K$ such that $n\geq
5$ and that $K\not\in\\{P_{n},C_{n}\\}$, then $ABS(G)>ABC(G)$.

In order to prove Theorem 2.5, we need some preparations.

A decomposition of a graph $G$ is a class $\mathcal{S}_{G}$ of edge-disjoint
subgraphs of $G$ such that
$\cup_{S\in\mathcal{S}_{G}}\mathbf{E}(S)=\mathbf{E}(G)$. By a clique in a
graph $G$, we mean a maximal complete subgraph of $G$. A branching vertex in a
graph is a vertex of degree at least $3$. By a pendent edge of a graph, we
mean an edge whose one of the end-vertices is pendent and the other one is
non-pendent. For $r\geq 2$, a path $u_{1}\cdots u_{r}$ in a graph is said to
be pendent if $\min\\{d_{u_{1}},d_{u_{r}}\\}=1$,
$\max\\{d_{u_{1}},d_{u_{r}}\\}\geq 3$, and $d_{u_{i}}=2$ for $2\leq i\leq
r-1$. If $P:u_{1}\cdots u_{r}$ is a pendent path in a graph with
$d_{u_{r}}\geq 3$, we say that $P$ is attached with the vertex $u_{r}$. Two
pendent paths of a graph are said to be adjacent if they have a common
(branching) vertex. A triangle of a graph $G$ is said to be odd if there is a
vertex of $G$ adjacent to an odd number of its vertices.

For the proof of Theorem 2.5 we need the following well-known result:

######  Lemma 2.6.

[17] A graph $G$ is the line graph of a graph if and only if the star graph of
order $4$ is not an induced subgraph of $G$, and if two odd triangles have a
common edge then the subgraph induced by their vertices is the complete graph
of order $4$.

We can now start with the proof of Theorem 2.5.

###### Proof of Theorem 2.5.

Since $K\not\cong P_{n}$, the graph $G$ has at least one cycle. If $G$ is one
of the two graphs $H_{1},H_{2},$ depicted in Fig. 3, then one can directly
verify that $ABS>ABC$ holds. In what follows, we assume that
$G\not\in\\{H_{1},H_{2}\\}$.

Figure 3: The graphs $H_{1}$ and $H_{2}$ mentioned in the proof of Theorem
2.5.

Consider the difference

$ABS(G)-ABC(G)=\sum_{uv\in\mathbf{E}(G)}\left(\sqrt{\frac{d_{u}+d_{v}-2}{d_{u}+d_{v}}}-\sqrt{\frac{d_{u}+d_{v}-2}{d_{u}\,d_{v}}}\,\right)$

and define a function $f$ of two variables $x$ and $y$ as

$f(x,y)=\sqrt{\frac{x+y-2}{x+y}}-\sqrt{\frac{x+y-2}{xy}}$

where $y\geq x\geq 1$ and $y\geq 2$. Note that the function $f$ is strictly
increasing (in both $x$ and $y$). Also, if $x$ and $y$ are integers satisfying
the inequalities $y\geq x\geq 1$ and $y\geq 2$, then the inequality $f(x,y)<0$
holds if and only if $x=1$. Thus,

$-0.129757\approx\frac{1}{\sqrt{3}}-\frac{1}{\sqrt{2}}=f(1,2)\leq f(1,y)<0$

for every $y\geq 2$. Also,

$f(x,y)\geq f(2,3)=\sqrt{\frac{3}{5}}-\frac{1}{\sqrt{2}}\approx
0.0674899>f(2,2)=0$

for $y\geq x\geq 2$ and $y\geq 3$. Furthermore, we have $f(1,2)+f(2,y)>0$ for
every $y\geq 5$. Thus, if either $G$ has no pendent paths or every pendent
path of $G$ has length at least $2$, which is attached with a vertex of degree
at least $5$, then $ABS(G)-ABC(G)>0$. In the remaining proof, we assume that
$G\not\in\\{H_{1},H_{2}\\}$ and that $G$ either has at least one pendent path
of length $1$ or it has at least one pendent path of length at least $2$,
which is attached with a vertex of degree $3$ or $4$.

Let $H^{\prime}$ be the graph depicted in Fig. 4, i.e., $H^{\prime}$ is
obtained from two disjoint graphs $H_{1}$ and $H$ by identifying their
vertices $z$ and $z^{\prime}$.

Figure 4: The graphs $H_{1}$, $H$, and $H^{\prime}$ mentioned in the proof of
Theorem 2.5.

Fact 1. If $G\cong H^{\prime}$, then the sum of the contributions of the edges
of $H_{1}$ in $G$ to the difference $ABS(G)-ABC(G)$ is positive.

It is a well-known fact that the line graph $G$ can be decomposed into
cliques, such that every edge of $G$ lies on exactly one clique and every non-
pendent vertex of $G$ lies on exactly two cliques. Also, by Lemma 2.6, $G$
contains no pair of adjacent pendent paths/edges and hence the number of
pendent edges/paths of $G$ is at most
$\left\lfloor\,|\mathbf{E}(G)|/2\right\rfloor$. Bearing this in mind, we
decompose $G$ into connected subgraphs $G_{1},\ldots,G_{k}$ in such a way that
every $G_{i}$ contains at most one pendent path of $G$, such that:

(a)

if $G_{i}$ contains a pendent path of $G$ of length $1$ such that the
branching vertex (in $G$) of the considered path has a neighbor of degree $2$
in $G$, then $G_{i}$ is induced by the vertices of the mentioned path and the
vertices adjacent to the branching vertex (in $G$) of the mentioned path (for
an example, see $G_{4}$ in Fig. 5(b));

(b)

if $G_{i}$ has a pendent path of length at least $2$ in $G$ or if $G_{i}$
contains a pendent path of $G$ of length $1$ such that the branching vertex
(in $G$) of the considered path has no neighbor of degree $2$ in $G$, then
$G_{i}$ consists of the mentioned path together with exactly one additional
edge incident with the branching vertex (in $G$) of the mentioned path (for an
example, see Fig. 5).

Figure 5: (a) A tree $T$, its line graph $L(T)$, and a decomposition of $L(T)$
into three connected subgraphs $G_{1},G_{2},G_{3}$. (b) A tree $T$, its line
graph $L(T)$, and a decomposition of $L(T)$ into four connected subgraphs
$G_{1},G_{2},G_{3},G_{4}$.

In order to complete the proof, it is enough to show that the sum of
contributions of all edges of $G_{i}$ (in $G$) to the difference
$ABS(G)-ABC(G)$ is positive. If a subgraph $G_{i}$ of $G$ contains no pendent
vertex of $G$ then certainly, the sum of contributions of all edges of $G_{i}$
(in $G$) to the difference $ABS(G)-ABC(G)$ is positive.

Case 1: a subgraph $G_{i}$ contains a pendent path of $G$ of length $1$, such
that the branching vertex (in $G$) of the considered path has a neighbor of
degree $2$ in $G$.

Let $P:v_{1}v_{2}$ be the pendent path of $G$ contained in $G_{i}$, where
$d_{v_{1}}(G)=1$ and $d_{v_{2}}(G)\geq 3$. Note that every neighbor of $v_{2}$
different from $v_{1}$ in $G$ has degree at least $d_{v_{2}}(G)-1$ in $G$ (by
Lemma 2.6). Thus, $d_{v_{2}}(G)=3$ in the case under consideration. Recall
that $G\not\in\\{H_{1},H_{2}\\}$ (see Fig. 3). Consequently, $G_{i}\cong
H_{1}$ and hence by Fact 1, the sum of contributions of all edges of $G_{i}$
to the difference $ABS(G)-ABC(G)$ is positive.

Case 2: a subgraph $G_{i}$ has a pendent path of $G$ of length $1$, such that
the branching vertex (in $G$) of the considered path has no neighbor of degree
$2$ in $G$.

Note that $G_{i}$ is a path of length $2$ in this case. Let
$G_{i}:v_{1}v_{2}v^{\prime}$, where $v_{1}v_{2}$ is a pendent path of $G$,
$d_{v_{1}}(G)=1$, and $d_{v_{2}}(G)\geq 3$. If $d_{v_{2}}(G)\geq 4$, then the
sum of contributions of all edges of $G_{i}$ to the difference $ABS(G)-ABC(G)$
is positive because $d_{v^{\prime}}(G)\geq d_{v_{2}}(G)-1$ (by Lemma 2.6) and
$f(1,y)+(y-1,y)>0$ for every $y\geq 4$. Next, assume that $d_{v_{2}}(G)=3$.
Since $d_{v^{\prime}}(G)\geq 3$ in the considered case, the sum of
contributions of all edges of $G_{i}$ to the difference $ABS(G)-ABC(G)$ is
again positive because $f(1,3)+f(3,y)>0$ for all $y\geq 3$.

Case 3: a subgraph $G_{i}$ has a pendent path of length at least $2$ in $G$.

Note that $G_{i}$ is itself a path. Let $G_{i}:v_{1}v_{2}\cdots
v_{r}v^{\prime}$, where $v_{1}v_{2}\cdots v_{r}$ ($r\geq 3$) is a pendent path
of $G$, $d_{v_{1}}(G)=1$, and $d_{v_{r}}(G)\in\\{3,4\\}$, because $G$ has no
pendent path of length at least $2$, which is attached with a vertex of degree
at least $5$ (see the paragraph appears right before the definition of
$H^{\prime}$ (before Fact 1)).

Subcase 3.1: $d_{v_{r}}(G)=3$.

The vertex $v^{\prime}$ has degree at least $2$ (in $G$) and
$f(1,2)+f(2,3)+f(3,y)\geq f(1,2)+f(2,3)+f(2,3)>0$ for $y\geq 2$. Thus, the sum
of contributions of all edges of $G_{i}$ (in $G$) to the difference
$ABS(G)-ABC(G)$ is positive.

Subcase 3.2: $d_{v_{r}}(G)=4$.

In this case, the vertex $v^{\prime}$ has degree at least $3$ (in $G$) and
$f(1,2)+f(2,4)+f(4,y)\geq f(1,2)+f(2,4)+f(3,4)>0$ for $y\geq 3$. Thus, the sum
of contributions of all edges of $G_{i}$ (in $G$) to the difference
$ABS(G)-ABC(G)$ is again positive.

This completes the proof of Theorem 2.5.

######  Theorem 2.7.

Let $G$ be a connected graph of size $m$. If the number of pendent vertices of
$G$ is at most $\lfloor m/2\rfloor$ and the number of vertices of degree $2$
in $G$ is zero, then

$ABS(G)>ABC(G).$

###### Proof.

Consider the function $f$ defined in the proof of Theorem 2.5. Here,

$-0.10939\approx\frac{1}{\sqrt{2}}-\sqrt{\frac{2}{3}}=f(1,3)\leq f(1,y)<0$

for every $y\geq 3$. Also,

$f(x,y)\geq f(3,3)=\sqrt{\frac{2}{3}}-\frac{2}{3}\approx 0.14983$

for $y\geq x\geq 3$. Let $p$ denote the number of pendent vertices of $G$.
Then, $m-p\geq p$. Now, by keeping in mind these observations, we have

$\displaystyle ABS(G)-ABC(G)$
$\displaystyle=\sum_{uv\in\mathbf{E}(G);\,d_{u}=1}\left(\sqrt{\frac{d_{u}+d_{v}-2}{d_{u}+d_{v}}}-\sqrt{\frac{d_{u}+d_{v}-2}{d_{u}\,d_{v}}}\,\right)$
$\displaystyle+\sum_{\begin{subarray}{c}uv\in\mathbf{E}(G);\\\
\min\\{d_{u},d_{v}\\}\geq
3\end{subarray}}\left(\sqrt{\frac{d_{u}+d_{v}-2}{d_{u}+d_{v}}}-\sqrt{\frac{d_{u}+d_{v}-2}{d_{u}\,d_{v}}}\,\right)$
$\displaystyle\geq\sum_{\begin{subarray}{c}uv\in\mathbf{E}(G);\\\
d_{u}=1\end{subarray}}\left(\frac{1}{\sqrt{2}}-\sqrt{\frac{2}{3}}\right)+\sum_{\begin{subarray}{c}uv\in\mathbf{E}(G);\\\
\min\\{d_{u},d_{v}\\}\geq
3\end{subarray}}\left(\sqrt{\frac{2}{3}}-\frac{2}{3}\right)$
$\displaystyle=p\left(\frac{1}{\sqrt{2}}-\sqrt{\frac{2}{3}}\right)+(m-p)\left(\sqrt{\frac{2}{3}}-\frac{2}{3}\right)$
$\displaystyle\geq
p\left(\frac{1}{\sqrt{2}}-\sqrt{\frac{2}{3}}\right)+p\left(\sqrt{\frac{2}{3}}-\frac{2}{3}\right)$
$\displaystyle>0.$

######  Theorem 2.8.

Let $G$ be a connected graph of size $m$ such that if $v\in V(G)$ is a vertex
of degree $2$ then $v$ has no neighbor of any of the degrees $2$, $3$, $4$. If
the number of pendent vertices of $G$ is at most $\lfloor m/2\rfloor$, then

$ABS(G)>ABC(G).$

###### Proof.

Consider the function $f$ defined in the proof of Theorem 2.5. Recall that

$-0.129757\approx\frac{1}{\sqrt{3}}-\frac{1}{\sqrt{2}}=f(1,2)\leq f(1,y)<0$

for every $y\geq 2$. Also, $f(x,y)\geq
f(2,5)=\sqrt{\frac{5}{7}}-\frac{1}{\sqrt{2}}\approx 0.138047$ for $y\geq x\geq
2$ with $y\geq 5$ and $f(x,y)\geq f(3,3)>f(2,5)$ for $y\geq x\geq 3$. Let $P$
denote the set of pendent edges of $G$. Then, $|\mathbf{E}(G)\setminus
P|\geq|P|$. Now, by keeping in mind the above observations, we have

$\displaystyle ABS(G)-ABC(G)$ $\displaystyle=\sum_{uv\in\mathbf{E}(G)\setminus
P}\left(\sqrt{\frac{d_{u}+d_{v}-2}{d_{u}+d_{v}}}-\sqrt{\frac{d_{u}+d_{v}-2}{d_{u}\,d_{v}}}\,\right)$
$\displaystyle+\sum_{uv\in
P}\left(\sqrt{\frac{d_{u}+d_{v}-2}{d_{u}+d_{v}}}-\sqrt{\frac{d_{u}+d_{v}-2}{d_{u}\,d_{v}}}\,\right)$
$\displaystyle\geq\sum_{uv\in\mathbf{E}(G)\setminus
P}\left(\sqrt{\frac{5}{7}}-\frac{1}{\sqrt{2}}\right)+\sum_{uv\in
P}\left(\frac{1}{\sqrt{3}}-\frac{1}{\sqrt{2}}\right)$
$\displaystyle=|\mathbf{E}(G)\setminus
P|\left(\sqrt{\frac{5}{7}}-\frac{1}{\sqrt{2}}\right)+|P|\left(\frac{1}{\sqrt{3}}-\frac{1}{\sqrt{2}}\right)$
$\displaystyle\geq|P|\left(\sqrt{\frac{5}{7}}-\frac{1}{\sqrt{2}}\right)+|P|\left(\frac{1}{\sqrt{3}}-\frac{1}{\sqrt{2}}\right)$
$\displaystyle>0.$

##  3 Conclusion and Some Open Problems

In this paper, we considered the difference between atom-bond-connectivity
($ABC$) and atom-bond sum-connectivity ($ABS$) indices. In the case of graphs
without pendent vertices, finding the sign of this difference is trivially
easy (see Proposition 2.1). On the other hand, in the case of graphs
possessing pendent vertices, especially for trees, this difference becomes
perplexed and the complete solution of the problem awaits additional studies.

Denote the difference $ABC-ABS$ by $\Theta$. By means of computer search we
found that for trees with $n\leq 15$ vertices (except in the trivial cases
$n=1,2$), $\Theta=0$ never happens. It would be of some interest to extend
this finding to higher values of $n$, or to discover a tree (or a graph with
minimum degree $1$) for which $\Theta=0$.

Let $T_{n}$ be the number of trees of order $n$, and $t_{n}$ the number of
trees of order $n$ for which $\Theta<0$. We know that $t_{n}/T_{n}>0$ for
$n\geq 11$. It is an open problem what the value of
$\lim_{n\to\infty}t_{n}/T_{n}$ is, especially whether it is equal to zero or
to unity.

Acknowledgment: This research has been funded by the Scientific Research
Deanship, University of Ha’il, Saudi Arabia, through project number RG-23
019.

## References

  * [1] A. M. Albalahi, Z. Du, A. Ali, On the general atom-bond sum-connectivity index, AIMS Math. 8 (2023) 23771–23785.
  * [2] A. M. Albalahi, E. Milovanović, A. Ali, General atom-bond sum-connectivity index of graphs, Mathematics 11 (2023) #2494.
  * [3] A. Ali, K. C. Das, D. Dimitrov, B. Furtula, Atom-bond connectivity index of graphs: a review over extremal results and bounds, Discrete Math. Lett. 5 (2021) 68–93.
  * [4] A. Ali, B. Furtula, I. Redžepović, I. Gutman, Atom-bond sum-connectivity index, J. Math. Chem. 60 (2022) 2081–2093.
  * [5] A. Ali, I. Gutman, I. Redžepović, Atom-bond sum-connectivity index of unicyclic graphs and some applications, Electron. J. Math. 5 (2023) 1–7.
  * [6] R. Abreu-Blaya, R. Reyes, J. M. Rodríguez, J. M. Sigarreta, Inequalities on the generalized atom bond connectivity index, J. Math. Chem. 59 (2021) 775–791.
  * [7] T. A. Alraqad, I. Ž. Milovanović, H. Saber, A. Ali, J. P. Mazorodze, Minimum atom-bond sum-connectivity index of trees with a fixed order and/or number of pendent vertices, arXiv:2211.05218 [math.CO].
  * [8] J. A. Bondy, U. S. R. Murty, Graph Theory, Springer, London, 2008.
  * [9] G. Chartrand, L. Lesniak, P. Zhang, Graphs & Digraphs, CRC Press, Boca Raton, 2016.
  * [10] K. C. Das, J. M. Rodríguez, J. M. Sigarreta, On the generalized ABC index of graphs, MATCH Commun. Math. Comput. Chem. 87 (2022) 147–169.
  * [11] D. Dimitrov, Z. Du, A solution of the conjecture about big vertices of minimal-ABC trees, Appl. Math. Comput. 397 (2021) #125818.
  * [12] E. Estrada, L. Torres, L. Rodríguez, I. Gutman, An atom-bond connectivity index: modelling the enthalpy of formation of alkanes, Indian J. Chem. Sec. A 37 (1998) 849–855.
  * [13] B. Furtula, A. Graovac, D. Vukicević, Augmented Zagreb index, J. Math. Chem. 48 (2010) 370–380.
  * [14] N. Ghanbari, On the Graovac-Ghorbani and atom-bond connectivity indices of graphs from primary subgraphs, Iranian J. Math. Chem. 13 (2022) 45–72.
  * [15] K. J. Gowtham, I. Gutman, On the difference between atom-bond sum-connectivity and sum-connectivity indices, Bull. Cl. Sci. Math. Nat. Sci. Math. 47 (2022) 55–65.
  * [16] I. Gutman, J. Tošović, S. Radenković, S. Marković, On atom–bond connectivity index and its chemical applicability, Indian J. Chem. A 51 (2012) 690–694.
  * [17] F. Harary, Graph Theory, Addison-Wesley, Reading, 1969.
  * [18] S. A. Hosseini, B. Mohar, M. B. Ahmadi, The evolution of the structure of ABC-minimal trees, J. Combin. Theory Ser. B 152 (2022) 415–452.
  * [19] Y. Hu, F. Wang, On the maximum atom-bond sum-connectivity index of trees, MATCH Commun. Math. Comput. Chem., in press.
  * [20] M. N. Husin, S. Zafar, R. U. Gobithaasan, Investigation of atom-bond connectivity indices of line graphs using subdivision approach, Math. Prob. Engin. 2022 (2022) #6219155.
  * [21] L. B. Kier, L. H. Hall, Molecular Connectivity in Chemistry and Drug Research, Academic Press, New York, 1976\.
  * [22] L. B. Kier, L. H. Hall, Molecular Connectivity in Structure–Activity Analysis, Wiley, New York, 1986.
  * [23] P. Nithya, S. Elumalai, S. Balachandran, S. Mondal, Smallest ABS index of unicyclic graphs with given girth, J. Appl. Math. Comput., available online at https://doi.org/10.1007/s12190-023-01898-0.
  * [24] S. Noureen, A. Ali, Maximum atom-bond sum-connectivity index of $n$-order trees with fixed number of leaves, Discrete Math. Lett. 12 (2023) 26–28.
  * [25] M. Randić, On characterization of molecular branching, J. Am. Chem. Soc. 97 (1975) 6609–6615.
  * [26] M. Randić, M. Novič, D. Plavšić, Solved and Unsolved Problems in Structural Chemistry, CRC Press, Boca Raton, 2016.
  * [27] S. Wagner, H. Wang, Introduction to Chemical Graph Theory, CRC Press, Boca Raton, 2018.
  * [28] B. Zhou, N. Trinajstić, On a novel connectivity index, J. Math. Chem. 46 (2009) 1252–1270.
  * [29] B. Zhou, N. Trinajstić, Relations between the product- and sum-connectivity indices, Croat. Chem. Acta 83 (2012) 363–365.