# Neural Graph Generator: Feature-Conditioned Graph Generation using Latent
Diffusion Models

Iakovos Evdaimon1 Giannis Nikolentzos2 Michail Chatzianastasis1 Hadi Abdine1
and Michalis Vazirgiannis1,3
1École Polytechnique, IP Paris, France
2University of Peloponnese, Greece
3KTH Royal Institute of Technology, Sweden

###### Abstract

Graph generation has emerged as a crucial task in machine learning, with
significant challenges in generating graphs that accurately reflect specific
properties. Existing methods often fall short in efficiently addressing this
need as they struggle with the high-dimensional complexity and varied nature
of graph properties. In this paper, we introduce the Neural Graph Generator
(NGG), a novel approach which utilizes conditioned latent diffusion models for
graph generation. NGG demonstrates a remarkable capacity to model complex
graph patterns, offering control over the graph generation process. NGG
employs a variational graph autoencoder for graph compression and a diffusion
process in the latent vector space, guided by vectors summarizing graph
statistics. We demonstrate NGG’s versatility across various graph generation
tasks, showing its capability to capture desired graph properties and
generalize to unseen graphs. This work signifies a significant shift in graph
generation methodologies, offering a more practical and efficient solution for
generating diverse types of graphs with specific characteristics.

##  1 Introduction

In recent years, the field of machine learning on graphs has witnessed an
extensive growth, mainly due to the availability of large amounts of data
represented as graphs. Indeed, graphs arise naturally in several application
domains such as in social networks, in chemo-informatics and in bio-
informatics. One of the most challenging tasks of machine learning on graphs
is that of graph generation [Zhu et al., 2022]. Graph generation has attracted
a lot of attention recently and its main objective is to create novel and
realistic graphs. For instance, in chemo-informatics, graph generative models
are employed to generate novel, realistic molecular graphs which also exhibit
desired properties (e. g., high drug-likeness) [Jin et al., 2018, Zang and
Wang, 2020].

Recently, there is a surge of interest in developing new graph generative
models, and most of the proposed models typically fall into one of the
following five families of models: (1) Auto-Regressive models; (2) Variational
Autoencoders; (3) Generative Adversarial Networks; (4) Normalizing Flows; and
(5) Diffusion models. These models can capture the complex structural and
semantic information of graphs, but focus mainly on specific types of graphs
such as molecules [Hoogeboom et al., 2022], proteins [Ingraham et al., 2019],
computer programs [Brockschmidt et al., 2019] or patient trajectories
[Nikolentzos et al., 2023]. Traditionally, in different application domains,
there is a need for generating graphs that exhibit specific properties (e. g.,
degree distribution, node triangle participation, community structure, etc.).
The different models that are commonly employed to generate these graphs, such
as the Erdős–Rényi model and the Barabási-Albert model, capture one or more
network properties but neglect others. For example, the Barabási-Albert model
can generate graphs with a specific degree distribution, but ignores the rest
of the graph’s properties.

Recent graph generative models have improved in accurately representing
various properties of real-world graphs. Nonetheless, to produce graphs
adhering to specific properties, it is necessary first to compile a dataset of
graphs that display these characteristics before proceeding to train the model
using this dataset. Thus, to generate different types of graphs, different
models need to be trained, which is impractical. This work aims to fill this
gap. Specifically, we develop a neural network model, so-called Neural Graph
Generator (NGG), to generate graphs that exhibit specific properties. We
capitalize on recent advances in latent diffusion models to perform vector-
conditioned graph generation. The model applies the diffusion process not to
the graph data but instead to an encoded latent representation of the graph.
We produce vectors that contain a summary of the statistics of each graph (e.
g., number of nodes, number of edges, clustering coefficient, etc.). Those
vectors guide the denoising part of the diffusion process. We first pre-train
a variational graph autoencoder which we use to map graphs into vectors and
map vectors into graphs. The diffusion is performed in the space of vectors.
To generate new graphs that exhibit specific properties, we sample a vector
from the standard normal distribution, and we denoise this vector, while
denoising is guided by the vector of graph properties. Once the noise has been
removed from the vector, we feed the emerging vector into the decoder of the
pre-trained variational graph autoencoder to produce a graph. The proposed
model is evaluated in the task of graph generation conditioned on graph
properties. Our results indicate that the NGG model can indeed generate graphs
whose properties are similar to the ones that are given as input to the model.
To summarize, our work makes the following contributions:

  * (i)

We introduce Neural Graph Generator, a novel graph generative model which
leverages latent diffusion for conditional graph generation. This model
represents a significant shift from traditional graph generation methods,
focusing on prompting with a vector that includes a set of diverse properties
of the graph.

  * (ii)

We introduce a large-scale dataset of synthetic graphs that covers several
different types of graphs on which our model was trained. This dataset can be
used for pre-training any graph generative model in the future.

  * (iii)

We extensively evaluate our model across various graph generation tasks,
demonstrating its effectiveness in capturing specific graph properties,
generalizing to larger graphs, and generating graphs from subsets of
properties.

  * (iv)

We release the pre-trained autoencoder, the pre-trained latent diffusion
model, and the synthetic dataset of 1M graphs which are likely to be useful
for both practitioners and the scientific community
111https://github.com/iakovosevdaimon/Graph-Generator/.

##  2 Related Work

#### Graph Generative Models.

For the problem of graph generation, as discussed above, most models belong to
one of the following five families: (1) Auto-regressive models; (2)
Variational autoencoders; (3) Generative adversarial networks; (4) Normalizing
flows; and (5) Diffusion models. Auto-regressive models assume a specific node
ordering and generate graphs in a sequential fashion. GraphRNN [You et al.,
2018], GraphGen [Goyal et al., 2020] and GraphGen-Redux [Bacciu and Podda,
2021] are three examples of auto-regressive models. GraphRNN generates nodes
and its associated edges sequentially, while the other two models generate
edges and their endpoint nodes sequentially. Variational autoencoders consist
of two modules. First, the encoder which maps the input data to a space that
corresponds to the parameters of a Gaussian distribution. Typically, this
distribution is encouraged to be similar to the standard normal distribution.
Second, the decoder which maps from the latent space to the input space. In
the graph domain, GraphVAE [Simonovsky and Komodakis, 2018] is a model whose
encoder is an instance of a message passing graph neural network, while its
decoder is a simple multi-layer perceptron. There are models that embed graphs
into distributions different from Gaussian such as DGVAE [Li et al., 2020]
which utilizes the Dirichlet distributions as priors on the latent variables
and the latent variables represent graph cluster memberships. Variational
autoencoders have also achieved success in the field of chemoinformatics [Jin
et al., 2018, Samanta et al., 2020]. Similar to variational autoencoders,
generative adversarial networks also consist of two main components, a
generator whose objective is to generate realistic samples and a discriminator
whose objective is to distinguish real samples from synthetic ones. Most
models from this family typically consist of a generator that takes vectors
sampled from a standard normal distribution and processes them with a multi-
layer perceptron to generate a graph, and of a discriminator which is an
instance of a message passing graph neural network [De Cao and Kipf, 2018,
Pölsterl and Wachinger, 2021]. Architectures based on normalizing flows
explicitly model a probability distribution by leveraging a method that uses
the change-of-variable law of probabilities to transform a simple distribution
into a complex one by a sequence of invertible and differentiable mappings.
Normalizing flows can be applied to graphs by designing message passing
mechanisms that are exactly reversible [Liu et al., 2019]. Such models have
been applied to molecular data. For example, MoFlow [Zang and Wang, 2020]
generates chemical bonds through a Glow-based model, and atoms given bonds
using a graph conditional flow. Diffusion models gradually add noise to the
input data in the forward diffusion process, and then learn to remove the
noise in the reverse diffusion process. There exist models that add Gaussian
noise to the graph’s adjacency matrix and binarize the continuous values of
the output of the reverse diffusion process to produce valid graphs [Niu et
al., 2020, Jo et al., 2022]. More recent models apply a discrete diffusion
process that progressively adds noise by adding or removing edges and changing
the nodes’ and/or edges’ types [Vignac et al., 2023].

#### Conditional Graph Generation.

One of the main objectives of graph generative models is conditional
generation, which is the process of generating a graph that satisfies a
specific label or property. Typically, a conditional code is introduced that
explicitly controls the property of generated graphs. Such models are popular
in the field of chemo-informatics where novel molecules that possess desired
chemical properties (e. g., high binding affinity against a target protein)
need to be generated. For variational autoencoders, a simple approach is to
feed the concatenation of the conditional code and the latent graph
representation to the decoder [Simonovsky and Komodakis, 2018]. The
conditional code can also be concatenated to node representations sampled from
a single distribution [Yang et al., 2019]. In models that generate new nodes
and edges sequentially, once a new node is created, its feature vector must be
initialized, and the conditional code could be concatenated to that feature
vector [Li et al., 2018a]. There exist models whose message passing scheme is
modified to include the conditional code [Li et al., 2018b]. MOOD [Lee et al.,
2023] utilizes the gradient of a property prediction network to guide the
sampling process to domains that are likely to satisfy specific properties.
There are also models that employ regularization schemes to learn disentangled
representations where each dimension focuses on a specific property [Du et
al., 2022].

#### Latent Diffusion Models.

Diffusion models are generative models that have recently gained significant
attention [Ho et al., 2020, Sohl-Dickstein et al., 2015, Vincent, 2011].
Diffusion models have achieved state-of-the-art performance in several tasks
such as in conditional image generation [Dhariwal and Nichol, 2021, Song et
al., 2020], image colorization [Saharia et al., 2022a] and image super
resolution [Saharia et al., 2022b], just to name a few. Latent diffusion
models were introduced to reduce the computational complexity of diffusion
models. These models use some autoencoding component to project input data (e.
g., images) into some latent space and perform the diffusion process in that
space [Rombach et al., 2022]. Latent diffusion models can thus be trained on
limited computational resources while retaining the quality of diffusion
models. Latent diffusion models have been applied to different problems such
as image synthesis [Rombach et al., 2022], video synthesis [Blattmann et al.,
2023] and image reconstruction [Takagi and Nishimoto, 2023]. Recently, latent
diffusion models have been introduced in the molecular geometry domain, and
have been evaluated in the task of 3D molecule generation [Xu et al., 2023],
but also for generating protein backbone structures [Fu et al., 2023]. These
two works are the closest to our method. Even though architecture-wise our
model is similar to the models presented in these papers, we follow an
entirely different research direction and focus on conditional generation of
general graphs (similar to traditional graph generators) instead of certain
classes of graphs such as molecules and proteins.

##  3 Neural Graph Generator

In this section, we first introduce some key notation for graphs, and we then
present the two main components of the proposed NGG model: ($1$) the
variational graph autoencoder which produces a compressed latent
representation for each graph; and ($2$) the diffusion model which performs
diffusion in the latent space and which can be conditioned on various inputs
(vector of graph properties in our case). An overview of the proposed model is
given in Figure 1.

Figure 1: Overview of the proposed architecture. The variational graph
autoencoder is responsible for generating a compressed latent representation
for each graph. Those representations are fed to the diffusion model which
operates in that latent space. The denoising process is conditioned on a
vector that contains the graph’s properties. The output of the diffusion model
is passed on to the decoder which generates a graph.

###  3.1 Notation

Let $[n]=\\{1,\ldots,n\\}\subset\mathbb{N}$ for $n\geq 1$. Let $G=(V,E)$ be an
undirected graph, where $V$ is the set of nodes and $E$ is the edge set. We
will denote by $n$ the number of vertices and by $m$ the number of edges, i.
e., $n=|V|$ and $m=|E|$. The neighborhood $\mathcal{N}(v)$ of a node $v$ is
the set of all vertices adjacent to $v$. Hence,
$\mathcal{N}(v)=\\{u\,|\,(v,u)\in E\\}$ where $(v,u)$ is an edge between the
vertices $v$ and $u$ of $V$. The adjacency matrix
$\mathbf{A}\in\mathbb{R}^{n\times n}$ of a graph $G$ is a symmetric (typically
sparse) matrix that is used to encode edge information in the graph. The
element of the $i^{th}$ row and $j^{th}$ column is equal to the weight of the
edge between the vertices $v_{i}$ and $v_{j}$ if such an edge exists, and $0$
otherwise. The degree $d(v)$ of a node $v$ is equal to the number of edges
that are adjacent to the node, i. e., $d(v)=|\mathcal{N}(v)|$. In different
applications, nodes of graphs are annotated with feature vectors. We use
$\mathbf{X}\in\mathbb{R}^{n\times d}$ to denote the node features where $d$ is
the feature dimension size. The feature of a given node $v_{i}$ corresponds to
the $i^{th}$ row of $\mathbf{X}$.

###  3.2 Graph Compression

To map graphs into low-dimensional representations, we capitalize on previous
work, and we use an autoencoder [Simonovsky and Komodakis, 2018]. More
precisely, given a graph $G$, the encoder $\mathcal{E}$ encodes the graph into
a latent representation $\mathbf{z}=\mathcal{E}(G)$, and the decoder
$\mathcal{D}$ reconstructs the graph from the latent representation, giving
$\hat{G}=\mathcal{D}(\mathbf{z})=\mathcal{D}(\mathcal{E}(G))$, where
$\mathbf{z}\in\mathbb{R}^{d}$.

The encoder $\mathcal{E}$ corresponds to a message passing neural network
which consists of GIN layers [Xu et al., 2019]. Node representations are
updated as follows:

$\mathbf{h}_{v}^{(k)}=\text{MLP}^{(k)}\Bigg{(}\Big{(}1+\epsilon^{(k)}\Big{)}\mathbf{h}_{v}^{(k-1)}+\sum_{u\in\mathcal{N}(v)}\mathbf{h}_{u}^{(k-1)}\Bigg{)}$

where $k$ denotes the layer and $\epsilon$ is a trainable parameter. Note that
the nodes are initially annotated with features extracted from the
eigenvectors of the normalized Laplacian matrix. These features are stored in
matrix $\mathbf{X}$, while $\mathbf{h}_{v}^{(0)}$ is equal to the row of
matrix $\mathbf{X}$ that corresponds to node $v$. To produce a representation
for the entire graph, we use the sum operator as follows:

$\mathbf{h}_{G}=\sum_{v\in V}\mathbf{h}_{v}^{(K)}$

where $K$ is the number of layers. To avoid arbitrarily high-variance latent
spaces, we actually use a variational autoencoder. We thus use fully-connected
layers $\text{MLP}_{\mu},\text{MLP}_{\sigma}$, to embed the graphs into the
parameters of a Gaussian distribution. We also add the standard regularization
term into the loss function which imposes a slight penalty towards a standard
normal distribution on the learned latent representations. Then, the vector
$\mathbf{z}$ is sampled from the learned Gaussian distribution:

$\boldsymbol{\mu}=\text{MLP}_{\mu}(\mathbf{h}_{G}),\qquad\boldsymbol{\sigma}=\text{MLP}_{\sigma}(\mathbf{h}_{G}),\qquad\mathbf{z}=\boldsymbol{\mu}+\boldsymbol{\sigma}\odot\mathbf{\epsilon}$

where $\odot$ denotes element-wise multiplication, and $\mathbf{\epsilon}$ is
a random noise vector sampled from $\mathcal{N}(0,\mathbf{I})$.

The decoder $\mathcal{D}$ takes the vector $\mathbf{z}$ as input and
reconstructs the input graph. We experiment with a simple MLP decoder that
consists of a series of fully connected layers. Specifically, the decoder is
implemented as follows:

$\hat{\mathbf{A}}=\text{MLP}_{\mathcal{D}}(\mathbf{z})$

Note that $\hat{\mathbf{A}}$ is an $(n_{\text{max}}\times
n_{\text{max}})$-dimensional matrix where $n_{\text{max}}$ is a pre-defined
maximum graph size. In fact, the MLP outputs the upper triangular part of this
matrix, and from this $\hat{\mathbf{A}}$ is constructed. Similar to prior work
[De Cao and Kipf, 2018], we found that pre-defining the maximum graph size
makes the model significantly faster and also easier to optimize. Note that
$\hat{\mathbf{A}}$ contains continuous values and has a probabilistic
interpretation since each element represents the probability that two nodes
are connected by an edge. To produce a discrete object, we use the straight-
through Gumbel-Softmax [Jang et al., 2017], i. e., we use a sample from a
categorical distribution in the forward pass, while the relaxed values are
utilized in the backward pass. The matrix $\hat{\mathbf{A}}$ is then compared
with the adjacency matrix of the input graph $\mathbf{A}$ to compute the
reconstruction loss.

To compute the reconstruction loss, following previous work, we could employ
some graph matching algorithm to compare each input graph against the
corresponding reconstructed graph [Simonovsky and Komodakis, 2018]. However,
such algorithms are expensive to compute, while we also found empirically that
we can achieve similar (or even higher) levels of performance if we just
impose a specific ordering on the nodes of each graph and compare the
reconstructed adjacency against the adjacency that follows this ordering. In
general, a node ordering that is effective for one type of graphs might not be
effective for other types of graphs. For instance, in the task of molecule
generation, certain canonical orderings are more effective than others [Li et
al., 2018a]. Since our dataset consists of graphs that exhibit very different
properties from each other, in order to create a general graph generative
model, we experimented with the following node orderings: (1) nodes are sorted
by degree (from higher to lower); (2) ordering corresponds to BFS/DFS tree’s
default ordering, which is descending by node degree and rooted at the node
with the highest degree; and (3) nodes are sorted by Pagerank scores (from
higher to lower).

###  3.3 Latent Diffusion Model

Once the autoencoder is trained, we can use the encoder $\mathcal{E}$ to embed
graphs into a low-dimensional latent space. Those embeddings are expected to
capture both local and global properties of input graphs. The main advantage
of latent diffusion models over standard diffusion models is their efficiency.
The smaller latent space representation makes executing the diffusion process
much faster. This allows the models to be trained on a single or a few GPUs
instead of hundreds of GPUs. Indeed, recent diffusion models for graphs
[Vignac et al., 2023] operate on adjacency tensors (i. e., tensors of
dimension $n\times n\times d$), and thus are expensive to train, while it is
also expensive to generate new graphs.

Latent diffusion models consist of two main components: (1) a noise model; and
(2) a denoising neural network. The noise model $q$ progressively corrupts the
latent representation of the input graph $\mathbf{z}$ to create a sequence of
increasingly noisy vectors $(\mathbf{z}_{1},\ldots,\mathbf{z}_{T})$.
Specifically, the forward process $q$ samples some noise from a Gaussian
distribution at each time step $t$, which is added to the representation of
the previous time step as follows:

$q(\mathbf{z}_{t}|\mathbf{z}_{t-1})=\mathcal{N}\big{(}\mathbf{z}_{t};\sqrt{1-\beta_{t}}\mathbf{z}_{t-1},\beta_{t}\mathbf{I}\big{)}$

where $\beta_{t}$ is a known variance schedule and
$0<\beta_{1}<\ldots\beta_{T}<1$. Note that the forward process $q$ is fixed,
and thus, $\mathbf{z}_{t}$ can be obtained directly from $\mathbf{z}$ during
training. Specifically, we have that:

$q(\mathbf{z}_{t}|\mathbf{z})=\mathcal{N}\big{(}\mathbf{z}_{t};\sqrt{\bar{a}_{t}}\mathbf{z},(1-\bar{a}_{t})\mathbf{I}\big{)}$

where $\bar{a}_{t}=\prod_{i=1}^{t}a_{i}$ and $a_{t}=1-\beta_{t}$. Note that if
the schedule is set appropriately, $\mathbf{z}_{T}$ is pure Gaussian noise.
The second component of the latent diffusion model (i. e., the denoising
neural network) is responsible for predicting the added noise for a given time
step $t$. To train the denoising neural network $\epsilon_{\theta}$, the
following function is minimized:

$\begin{split}L_{\text{LDM}}&=\mathbb{E}_{\mathcal{E(G)},\epsilon\sim\mathcal{N}(0,1),t}\Big{[}\big{|}\big{|}\epsilon-\epsilon_{\theta}(\mathbf{z}_{t},t)\big{|}\big{|}_{2}^{2}\Big{]}\\\
&=\mathbb{E}_{\mathcal{E(G)},\epsilon\sim\mathcal{N}(0,1),t}\Big{[}\big{|}\big{|}\epsilon-\epsilon_{\theta}(\sqrt{\bar{a}_{t}}\mathbf{z}+\sqrt{(1-\bar{a}_{t})}\epsilon,t)\big{|}\big{|}_{2}^{2}\Big{]}\end{split}$

We implement the denoising neural network $\epsilon_{\theta}$ as an MLP.
First, we use sinusoidal positional embeddings to produce a unique
representation for each time step $t$. Then, we feed vector $\mathbf{z}_{t}$
to the MLP and in each hidden layer of the MLP, we add the positional
embedding to the latent representation.

Once the denoising neural network $\epsilon_{\theta}$ is trained, to generate
new data, we sample a vector of pure noise $\mathbf{z}_{T}$ from a Gaussian
distribution, and then use the neural network to gradually denoise it (using
the conditional probability it has learned). The denoised vector can then be
transformed into a graph with a single pass through the decoder $\mathcal{D}$.

###  3.4 Conditioning

The ability to condition graph generation on local and global properties of
graphs is crucial for the success of our work. Latent diffusion models are
capable of modeling conditional distributions. Specifically, text, images, or
other inputs can be encoded into the latent space and used to condition the
model to generate outputs with desired properties. Given some condition code
$\mathbf{c}$, diffusion models are capable of modeling the conditional
distribution $p(\mathbf{z}|\mathbf{c})$ by using a conditional neural network
$\epsilon_{\theta}(\mathbf{z}_{t},t,\tau_{\theta}\big{(}\mathbf{c})\big{)}$ as
follows:

$L_{\text{LDM}}=\mathbb{E}_{\mathcal{E(G)},\epsilon\sim\mathcal{N}(0,1),t}\Big{[}\big{|}\big{|}\epsilon-\epsilon_{\theta}\big{(}\mathbf{z}_{t},t,\tau_{\theta}(\mathbf{c})\big{)}\big{|}\big{|}_{2}^{2}\Big{]}$

where $\epsilon_{\theta}$ and $\tau_{\theta}$ are neural network models that
are jointly optimized. The architecture of $\tau_{\theta}$ depends on the
conditioning modality. As already discussed, the condition code is a vector of
properties of the graph. Thus, we use an MLP as the condition encoder
$\tau_{\theta}$ to compute $\mathbf{y}$ as follows:

$\mathbf{y}=\text{MLP}_{c}(\mathbf{c})$

Then, we concatenate vectors $\mathbf{z}$ and $\mathbf{y}$ and feed them into
the denoising neural network. We experimented with other operations (e. g.,
addition, element-wise product), but in preliminary experiments, concatenation
led to better results than the other operations.

The condition code consists of $15$ local and global properties of the input
graph. Those properties are listed in Table 4 in Appendix A. Those specific
$15$ properties were chosen mainly because they cover a broad range of graph
properties and they can give insights about the structure of the graph.
Furthermore, the properties can be computed efficiently in polynomial time.

##  4 Experimental Evaluation

We train and evaluate the NGG model on a dataset that contains $1$M synthetic
graphs. We consider that the evaluation encompasses three distinct scenarios.
Initially, we assess the model’s performance on our original dataset.
Subsequently, we evaluate its capabilities when trained on graphs containing
up to $50$ nodes, test its adaptability to larger graphs with more than $50$
nodes, and examine its generalization performance. Lastly, we randomly conceal
between $1$ to $8$ properties of some of the input graphs (i. e., number of
nodes, edges, density, etc.), treating them as missing values not provided by
the user. Subsequently, we retrain the model and assess its performance on the
test set, repeating the process of concealing a random number of graph
properties.

#### Dataset.

We train and evaluate the NGG model on a dataset that contains $1$M synthetic
graphs, where each graph contains at most $100$ nodes. To create the dataset,
we use different types of graph generators. This allows us to construct graphs
from different families and thus, cover a wide range of values of the
considered properties. Each synthetic graph belongs to one of the following
$17$ families of graphs: (1) paths; (2) cycles; (3) wheels; (4) stars; (5)
ladders; (6) lollipops; (7) Erdős-Rényi random graphs; (8)
Newman–Watts–Strogatz small-world graphs; (9) Watts–Strogatz small-world
graphs, (10) random $d$-degree regular graphs; (11) Barabási–Albert graphs;
(12) dual Barabási–Albert graphs; (13) extended Barabási–Albert graphs; (14)
graphs generated using the Holme and Kim algorithm; (15) random lobsters; (16)
stochastic block model graphs; and (17) random partition graphs. More details
about the constructed dataset are given in Appendix A. The generated graphs in
our dataset are devoid of self-loops, isolated nodes, and multigraphs are also
excluded.

#### Experimental setup.

With regard to the variational autoencoder, the encoder $\mathcal{E}$ consists
of $2$ layers, the hidden dimension size is set equal to $64$, while the input
graphs are embedded into $32$-dimensional vectors. We imposed an ordering on
the nodes based on the BFS tree’s default ordering. The decoder $\mathcal{D}$
consists of $3$ layers and the hidden dimension size is set to $256$. The
output of $\mathcal{D}$ is a $100^{2}$-dimensional vector and is transformed
into an adjacency matrix of dimension $(100\times 100)$. Thus, the model can
handle graphs of up to $100$ nodes. We also initially annotate the nodes of
each graph with $10$-dimensional spectral features (from the eigenvectors
associated with the $10$ smallest eigenvalues of the normalized Laplacian
matrix). For the latent diffusion model, we set the number of timesteps $T$
equal to $500$, while we use a cosine schedule for adding noise at each time
step. The denoising neural network $\epsilon_{\theta}$ consists of $3$ layers,
the hidden dimension size is equal to $512$, while the size of the output is
set to $128$. To train both models, we use the Adam optimizer and we set the
learning rate to $0.001$. The batch size is set to $256$. We set the number of
epochs of the variational autoencoder to $200$, while the number of epochs of
the latent diffusion model to $100$. Overall, the variational autoencoder
consists of $2,640,492$ parameters, while the diffusion model consists of
$973,088$ parameters. Thus, in total, the NGG model consists of $3,613,580$
parameters.

#### Evaluation and baseline.

Given a collection of graphs $\\{G_{1},G_{2},\ldots,G_{N}\\}$ that belong to
the test set, we use the trained generative model to produce another
collection of graphs $\\{\hat{G}_{1},\hat{G}_{2},\ldots,\hat{G}_{N}\\}$. To
generate each graph of the new collection, we sample pure noise from a
Gaussian distribution and use the neural network to gradually denoise it,
while the whole denoising process is conditioned on the vector of properties
of the corresponding graph of the test set $G_{i}$. Once the noise has been
removed, the emerging vector is transformed into a graph $\hat{G}_{i}$ with a
single pass through $\mathcal{D}$. Note, however, that we are not interested
in comparing the generated graphs against the corresponding graphs of the test
set, but we are interested in finding whether the properties of the generated
graphs match the properties of the corresponding graphs of the test set.
Therefore, for each generated graph $\hat{G}_{i}$, we compute a vector where
each component is the value of each one of the $15$ considered properties.
Then, this vector is compared against the vector of properties of $G_{i}$. We
use two different metrics: ($1$) the mean absolute error (MAE); and ($2$) the
symmetric mean absolute percentage error (SMAPE), which we use instead of the
mean absolute percentage error (MAPE) because we have values equal to zero or
close to zero. SMAPE values range from $0\%$ to $100\%$, while lower values
indicate better performance, as they represent a smaller percentage difference
between the predicted and actual values. We calculate the aforementioned
metrics by taking into account all $15$ properties and applying z-score
normalization to them.

We also use a variant of the variational autoencoder (VGAE) as a baseline
where the process is conditioned on vector of properties $\mathbf{c}$ for
controlled sampling by concatenating the vector with the graph’s latent
representation.

Table 1: Within distribution performance of the proposed NGG model and the baseline model in terms of the considered properties. Property | VGAE | NGG
---|---|---
| MAE | SMAPE |  | MAE | SMAPE
# nodes |  | 24.22 | 25.18 |  | 2.63 | 3.09
# edges |  | 701.99 | 66.48 |  | 62.33 | 8.44
Density |  | 0.32 | 52.13 |  | 0.04 | 7.23
Min. degree |  | 13.95 | 64.52 |  | 11.61 | 49.46
Max. degree |  | 14.59 | 22.32 |  | 1.59 | 3.55
Avg. degree |  | 18.99 | 58.60 |  | 1.64 | 6.68
Assortativity coefficient |  | 0.30 | 61.32 |  | 0.11 | 39.10
# triangles |  | 10,356.20 | 99.91 |  | 1,026.44 | 24.38
Avg. # triangles formed by an edge |  | 8.85 | 66.52 |  | 9.44 | 68.32
Max. # triangles formed by an edge |  | 539.03 | 83.97 |  | 49.26 | 16.66
Avg. local clustering coefficient |  | 0.29 | 35.04 |  | 0.08 | 15.42
Global clustering coefficient |  | 0.36 | 58.12 |  | 0.05 | 14.07
Max. $k$-core |  | 15.07 | 54.51 |  | 1.66 | 8.61
# communities |  | 1.74 | 21.86 |  | 0.96 | 12.34
Diameter |  | 3.73 | 31.31 |  | 2.40 | 15.96
All |  | 0.80 | 55.96 |  | 0.23 | 21.05

###  4.1 Within Distribution Performance

In this experiment, we split the constructed dataset into a training, a
validation and a test set. Then, we train the proposed NGG model and the
baseline on the training set. We choose the models that achieve the lowest
loss on the validation set and we evaluate their performance on the test set.
More specifically, the $1$M samples are split into training, validation, and
test sets with a $80:10:10$ split ratio, respectively. Thus, the training set
contains $800,000$ samples, while each of the validation and test sets contain
$100,000$ samples. Each one of the three sets preserves approximately the
proportions of each graph type. Table 1 illustrates the MAE and SMAPE achieved
by NGG and VGAE for each property individually and for all properties together
(last row). First of all, we observe that the proposed NGG model outperforms
VGAE in terms of almost all considered properties. Secondly, we notice that
NGG accurately captures most of the properties, while it struggles with the
minimum degree, the number of triangles, and the average and the maximum
number of triangles formed by an edge.

Table 2: Performance Comparison of NGG and Baseline Model under Different
Conditions: Out-of-Distribution Performance (trained on graphs with up to 50
nodes and evaluated on larger graphs) and Within-Distribution Performance with
Masking Applied to some Condition Vector Elements.

Property | Out of Distribution | Masked
---|---|---
VGAE | NGG | VGAE | NGG
| MAE | SMAPE |  | MAE | SMAPE |  | MAE | SMAPE |  | MAE | SMAPE
# nodes |  | 15.48 | 18.76 |  | 6.68 | 6.66 |  | 25.70 | 26.05 |  | 27.30 | 27.54
# edges |  | 355.79 | 60.12 |  | 99.09 | 11.31 |  | 785.20 | 49.83 |  | 832.26 | 52.90
Density |  | 0.28 | 48.10 |  | 0.07 | 10.74 |  | 0.27 | 34.04 |  | 0.29 | 36.65
Min. degree |  | 12.59 | 67.12 |  | 7.95 | 41.49 |  | 13.96 | 57.71 |  | 13.36 | 57.50
Max degree |  | 4.46 | 7.95 |  | 2.93 | 4.64 |  | 23.97 | 35.17 |  | 26.04 | 38.06
Avg. degree |  | 14.34 | 51.23 |  | 3.11 | 9.27 |  | 18.83 | 40.84 |  | 20.17 | 43.77
Assortativity coefficient |  | 0.29 | 65.66 |  | 0.72 | 47.57 |  | 0.46 | 60.98 |  | 0.43 | 65.18
# triangles |  | 3,913.93 | 83.79 |  | 1,482.23 | 27.21 |  | 15,101.24 | 74.92 |  | 15,956.96 | 79.93
Avg . # triangles formed by an edge |  | 7.78 | 54.99 |  | 17.93 | 74.95 |  | 9.11 | 49.11 |  | 17.73 | 77.18
Max . # triangles formed by an edge |  | 278.36 | 64.51 |  | 83.15 | 17.71 |  | 709.65 | 66.55 |  | 762.29 | 71.23
Avg. local clustering coefficient |  | 0.26 | 26.01 |  | 0.09 | 15.91 |  | 0.33 | 40.78 |  | 0.36 | 44.69
Global clustering coefficient |  | 0.27 | 46.16 |  | 0.07 | 14.44 |  | 0.32 | 41.89 |  | 0.34 | 44.34
Max k-core |  | 11.39 | 52.05 |  | 2.28 | 9.99 |  | 16.93 | 42.96 |  | 17.99 | 45.76
# communities |  | 2.64 | 27.47 |  | 1.02 | 12.32 |  | 1.86 | 22.98 |  | 1.96 | 23.40
Diameter |  | 3.52 | 29.98 |  | 2.55 | 16.61 |  | 3.40 | 23.82 |  | 3.31 | 24.19
All |  | 0.96 | 56.13 |  | 0.54 | 28.89 |  | 0.77 | 42.14 |  | 0.78 | 42.88

###  4.2 Out of Distribution Generalization

In many scenarios, machine learning models fail to generalize to unseen data.
Thus, in this second experiment, we study whether the proposed NGG model and
the baseline model can generate graphs whose properties’ values are different
from the ones the models were trained on (i.e. out of distribution).
Specifically, we train the two models on graphs of up to $40$ nodes and also
on graphs that consist of more than $60$ nodes. Then, the models are evaluated
on the rest of the graphs (i. e., graphs of size from $41$ nodes to $59$
nodes). The results of this experiment are illustrated in Table 2 (Left). We
observe that the proposed NGG model still outperforms the VGAE model in this
experiment. However, the VGAE model can generate graphs that better capture
the average number of triangles formed by an edge than NGG. Furthermore, we
can also see that both models achieve a bit lower levels of performance
compared to their corresponding performance reported in Table 1. This is not
surprising since the model is trained on graphs that are larger or smaller
than the ones on which it is evaluated.

###  4.3 Conditioning on Subset of Properties

Since a practitioner might be interested only in a handful of properties, and
not in all $15$ of them, we also investigate whether the proposed model can
generate graphs providing only a subset of the properties. Within each batch,
we randomly choose if the properties of each sample would be masked, treating
some of the elements of their associated condition vector as missing values as
follows. For each one of the chosen samples, we randomly choose $i$ elements
(without replacement) where $i\in\\{1,2,\ldots,8\\}$ and replace the values of
those elements with a value equal to $-100$. Note that we also corrupt
similarly the samples of the test set at inference time. We then compare the
observed properties of the condition vector against the corresponding
properties of the generated samples to compute the three evaluation metrics.
The obtained results are shown in Table 2 (Right). We observe that the
baseline model outperforms the proposed NGG model, only by a small margin
though. Furthermore, the model achieves significantly worse levels of
performance compared to the ones reported in Table 1. While the proposed model
generally proves effective in the task of graph generation, its performance
diminishes when only a subset of the considered properties are available,
failing to achieve the same levels of performance as when all properties are
present.

(a) Generated graph that emerged from condition vector $\mathbf{c}_{1}$

(b) Generated graph that emerged from condition vector $\mathbf{c}_{2}$

Figure 2: Example of two graphs generated by the proposed NGG model given
condition vectors $\mathbf{c}_{1}$ and $\mathbf{c}_{2}$.

###  4.4 Examples of Generated Graphs

We will next give two examples of graphs generated by the proposed NGG model.
To generate the two graphs, we used the model that was trained on $80\%$ of
the entire dataset. For ease of presentation, we decided to generate two
graphs that both consist of $15$ nodes. However, the second graph is much more
dense than the first graph. Specifically, we utilized the following two
condition vectors:

$\begin{split}\mathbf{c}_{1}&=\setcounter{MaxMatrixCols}{15}\begin{pmatrix}15&34&0.32&2&8&4.5&-0.046&17&1.5&8&0.4&0.35&4&4&4\\\
\end{pmatrix}^{\top}\\\
\mathbf{c}_{2}&=\setcounter{MaxMatrixCols}{15}\begin{pmatrix}15&94&0.89&10&14&12.5&-0.149&329&10.5&80&0.9&0.9&10&2&2\end{pmatrix}^{\top}\end{split}$

where each dimension corresponds to one of the 15 properties respectively. The
above two vectors gave rise to the two graphs that are shown in Figure 2. The
corresponding communities for each generated graph are also illustrated (node
color denotes the community to which the node belongs). We observe that one
generated graph indeed consists of $15$ nodes, while the other consists of
$16$ nodes. Furthermore, the graph shown in Figure 2(a) is indeed sparse,
while the one shown in Figure 2(b) is dense. We also computed the values of
the considered properties for both graphs and these are given below:

$\begin{split}\hat{\mathbf{c}}_{1}&=\setcounter{MaxMatrixCols}{15}\begin{pmatrix}15&25&0.23&1&7&3.3&-0.380&8&0.96&3&0.43&0.32&2&3&4\end{pmatrix}^{\top}\\\
\hat{\mathbf{c}}_{2}&=\setcounter{MaxMatrixCols}{15}\begin{pmatrix}16&108&0.9&3&15&13.5&-0.148&458&12.7&93&0.97&0.97&14&2&2\end{pmatrix}^{\top}\end{split}$

We can see that for most properties, their actual values are close to the ones
that were utilized for generating the two graphs. To summarize, those results
provide a qualitative validation of the proposed NGG model. We also visually
inspected several other graphs and it turns out that the proposed model can
generate graphs that approximately exhibit the desired properties.

###  4.5 Uniqueness of Generated Graphs

We also investigated whether given a vector of properties, the proposed NGG
model can generate non-isomorphic graphs. Specifically, we randomly chose $50$
condition codes, and for each code, we used the model to produce $100$ graphs.
We then tested every pair of these graphs for isomorphism ($9900/2$ pairs in
total for each condition code). We found that all generated graphs are unique,
i. e., there was no pair of isomorphic graphs. Therefore, the NGG model seems
to also produce diverse sets of graphs.

##  5 Conclusion

We introduced the Neural Graph Generator, a conditional latent diffusion model
for efficient and accurate graph generation. NGG represents a significant new
paradigm, adeptly generating graphs with specific, user-defined properties, a
task that has long challenged traditional models. We demonstrated the ability
of NGG to generalize in graphs than those in the training set, and the ability
to handle missing values in the condition vector. Nevertheless, GNN models,
while powerful, struggle to capture specific properties like triangles or
cycles, thus affecting the performance of our model. Future work will focus on
exploring the model’s applicability in various real-world scenarios.

## References

  * [Bacciu and Podda, 2021] Bacciu, D. and Podda, M. (2021).  GraphGen-Redux: A Fast and Lightweight Recurrent Model for labeled Graph Generation.  In Proceedings of the 2021 International Joint Conference on Neural Networks, pages 1–8.
  * [Blattmann et al., 2023] Blattmann, A., Rombach, R., Ling, H., Dockhorn, T., Kim, S. W., Fidler, S., and Kreis, K. (2023).  Align your Latents: High-Resolution Video Synthesis with Latent Diffusion Models.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 22563–22575.
  * [Brockschmidt et al., 2019] Brockschmidt, M., Allamanis, M., Gaunt, A. L., and Polozov, O. (2019).  Generative Code Modeling with Graphs.  In 7th International Conference on Learning Representations.
  * [De Cao and Kipf, 2018] De Cao, N. and Kipf, T. (2018).  MolGAN: An implicit generative model for small molecular graphs.  arXiv preprint arXiv:1805.11973.
  * [Dhariwal and Nichol, 2021] Dhariwal, P. and Nichol, A. (2021).  Diffusion Models Beat GANs on Image Synthesis.  In Proceedings of the 35th International Conference on Neural Information Processing Systems, pages 8780–8794.
  * [Du et al., 2022] Du, Y., Guo, X., Shehu, A., and Zhao, L. (2022).  Interpretable Molecular Graph Generation via Monotonic Constraint.  In Proceedings of the 2022 SIAM International Conference on Data Mining, pages 73–81.
  * [Fu et al., 2023] Fu, C., Yan, K., Wang, L., Au, W. Y., McThrow, M., Komikado, T., Maruhashi, K., Uchino, K., Qian, X., and Ji, S. (2023).  A Latent Diffusion Model for Protein Structure Generation.  In Proceedings of the 2nd Learning on Graphs Conference.
  * [Goyal et al., 2020] Goyal, N., Jain, H. V., and Ranu, S. (2020).  GraphGen: A Scalable Approach to Domain-agnostic Labeled Graph Generation.  In Proceedings of The Web Conference 2020, pages 1253–1263.
  * [Ho et al., 2020] Ho, J., Jain, A., and Abbeel, P. (2020).  Denoising Diffusion Probabilistic Models.  In Proceedings of the 34th International Conference on Neural Information Processing Systems, pages 6840–6851.
  * [Hoogeboom et al., 2022] Hoogeboom, E., Satorras, V. G., Vignac, C., and Welling, M. (2022).  Equivariant Diffusion for Molecule Generation in 3D.  In Proceedings of the 39th International Conference on Machine Learning, pages 8867–8887.
  * [Ingraham et al., 2019] Ingraham, J., Garg, V. K., Barzilay, R., and Jaakkola, T. (2019).  Generative models for graph-based protein design.  In Proceedings of the 33rd International Conference on Neural Information Processing Systems, pages 15820–15831.
  * [Jang et al., 2017] Jang, E., Gu, S., and Poole, B. (2017).  Categorical Reparameterization with Gumbel-Softmax.  In 5th International Conference on Learning Representations.
  * [Jin et al., 2018] Jin, W., Barzilay, R., and Jaakkola, T. (2018).  Junction Tree Variational Autoencoder for Molecular Graph Generation.  In Proceedings of the 35th International Conference on Machine Learning, pages 2323–2332.
  * [Jo et al., 2022] Jo, J., Lee, S., and Hwang, S. J. (2022).  Score-based Generative Modeling of Graphs via the System of Stochastic Differential Equations.  In Proceedings of the 39th International Conference on Machine Learning, pages 10362–10383.
  * [Lee et al., 2023] Lee, S., Jo, J., and Hwang, S. J. (2023).  Exploring Chemical Space with Score-based Out-of-distribution Generation.  In Proceedings of the 40th International Conference on Machine Learning, pages 18872–18892.
  * [Li et al., 2020] Li, J., Yu, J., Li, J., Zhang, H., Zhao, K., Rong, Y., Cheng, H., and Huang, J. (2020).  Dirichlet Graph Variational Autoencoder.  In Proceedings of the 34th International Conference on Neural Information Processing Systems, pages 5274–5283.
  * [Li et al., 2018a] Li, Y., Vinyals, O., Dyer, C., Pascanu, R., and Battaglia, P. (2018a).  Learning Deep Generative Models of Graphs.  arXiv preprint arXiv:1803.03324.
  * [Li et al., 2018b] Li, Y., Zhang, L., and Liu, Z. (2018b).  Multi-objective de novo drug design with conditional graph generative model.  Journal of Cheminformatics, 10:1–24.
  * [Liu et al., 2019] Liu, J., Kumar, A., Ba, J., Kiros, J., and Swersky, K. (2019).  Graph Normalizing Flows.  In Proceedings of the 33rd International Conference on Neural Information Processing Systems, pages 13578–13588.
  * [Nikolentzos et al., 2023] Nikolentzos, G., Vazirgiannis, M., Xypolopoulos, C., Lingman, M., and Brandt, E. G. (2023).  Synthetic electronic health records generated with variational graph autoencoders.  NPJ Digital Medicine, 6(1):83.
  * [Niu et al., 2020] Niu, C., Song, Y., Song, J., Zhao, S., Grover, A., and Ermon, S. (2020).  Permutation Invariant Graph Generation via Score-Based Generative Modeling.  In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, pages 4474–4484.
  * [Pölsterl and Wachinger, 2021] Pölsterl, S. and Wachinger, C. (2021).  Adversarial learned molecular graph inference and generation.  In Proceedings of the 2020 European Conference on Machine Learning and Knowledge Discovery in Databases, pages 173–189.
  * [Rombach et al., 2022] Rombach, R., Blattmann, A., Lorenz, D., Esser, P., and Ommer, B. (2022).  High-Resolution Image Synthesis with Latent Diffusion Models.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10684–10695.
  * [Saharia et al., 2022a] Saharia, C., Chan, W., Chang, H., Lee, C., Ho, J., Salimans, T., Fleet, D., and Norouzi, M. (2022a).  Palette: Image-to-Image Diffusion Models.  In ACM SIGGRAPH 2022 Conference Proceedings, pages 1–10.
  * [Saharia et al., 2022b] Saharia, C., Ho, J., Chan, W., Salimans, T., Fleet, D. J., and Norouzi, M. (2022b).  Image Super-Resolution via Iterative Refinement.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(4):4713–4726.
  * [Samanta et al., 2020] Samanta, B., De, A., Jana, G., Gómez, V., Chattaraj, P., Ganguly, N., and Gomez-Rodriguez, M. (2020).  NeVAE: A Deep Generative Model for Molecular Graphs.  Journal of Machine Learning Research, 21(114):1–33.
  * [Simonovsky and Komodakis, 2018] Simonovsky, M. and Komodakis, N. (2018).  GraphVAE: Towards Generation of Small Graphs Using Variational Autoencoders.  In Proceedings of the 27th International Conference on Artificial Neural Networks, pages 412–422.
  * [Sohl-Dickstein et al., 2015] Sohl-Dickstein, J., Weiss, E., Maheswaranathan, N., and Ganguli, S. (2015).  Deep Unsupervised Learning using Nonequilibrium Thermodynamics.  In Proceedings of the 32nd International Conference on Machine Learning, pages 2256–2265.
  * [Song et al., 2020] Song, Y., Sohl-Dickstein, J., Kingma, D. P., Kumar, A., Ermon, S., and Poole, B. (2020).  Score-Based Generative Modeling through Stochastic Differential Equations.  In 8th International Conference on Learning Representations.
  * [Takagi and Nishimoto, 2023] Takagi, Y. and Nishimoto, S. (2023).  High-resolution image reconstruction with latent diffusion models from human brain activity.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 14453–14463.
  * [Vignac et al., 2023] Vignac, C., Krawczuk, I., Siraudin, A., Wang, B., Cevher, V., and Frossard, P. (2023).  Digress: Discrete denoising diffusion for graph generation.  In 11th International Conference on Learning Representations.
  * [Vincent, 2011] Vincent, P. (2011).  A connection between score matching and denoising autoencoders.  Neural computation, 23(7):1661–1674.
  * [Xu et al., 2019] Xu, K., Hu, W., Leskovec, J., and Jegelka, S. (2019).  How Powerful are Graph Neural Networks?  In 7th International Conference on Learning Representations.
  * [Xu et al., 2023] Xu, M., Powers, A. S., Dror, R. O., Ermon, S., and Leskovec, J. (2023).  Geometric Latent Diffusion Models for 3D Molecule Generation.  In Proceedings of the 40th International Conference on Machine Learning, pages 38592–38610.
  * [Yang et al., 2019] Yang, C., Zhuang, P., Shi, W., Luu, A., and Li, P. (2019).  Conditional Structure Generation through Graph Variational Generative Adversarial Nets.  In Proceedings of the 33rd International Conference on Neural Information Processing Systems, pages 1340–1351.
  * [You et al., 2018] You, J., Ying, R., Ren, X., Hamilton, W., and Leskovec, J. (2018).  GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models.  In Proceedings of the 35th International Conference on Machine Learning, pages 5708–5717.
  * [Zang and Wang, 2020] Zang, C. and Wang, F. (2020).  MoFlow: An Invertible Flow Model for Generating Molecular Graphs.  In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 617–626.
  * [Zhu et al., 2022] Zhu, Y., Du, Y., Wang, Y., Xu, Y., Zhang, J., Liu, Q., and Wu, S. (2022).  A Survey on Deep Graph Generation: Methods and Applications.  In Proceedings of the 1st Learning on Graphs Conference, pages 47:1–47:21.

##  Appendix A Dataset Details

The distribution of the samples per family of graphs is illustrated in Table
3.

Table 3: Distribution of samples per graph type
Type of graph | Number of samples | Proportion
---|---|---
Barabási–Albert random graph | 250,136 | 25.01%
Watts–Strogatz small-world graph | 204,280 | 20.43%
stochastic block model graph | 125,468 | 12.55%
Erdős-Rényi graph | 122,568 | 12.26%
dual Barabási–Albert random graph | 122,568 | 12.26%
extended Barabási–Albert model graph | 122,568 | 12.26%
Newman-Watts-Strogatz small-world graph | 122,567 | 12.26%
Holme and Kim algorithm for growing graphs with powerlaw degree distribution and approximate average clustering | 122,567 | 12.26%
Random Lobster graph | 81,713 | 8.17%
random partition graph | 81,713 | 8.17%
Random $d$-degree regular graph | 7,000 | 0.7%
Lollipop graph | 4,145 | 0.41%
Path graph | 91 | 0.01%
Cycle graph | 91 | 0.01%
Star graph | 91 | 0.01%
Wheel graph | 91 | 0.01%
Ladder graph | 46 | 0.0046%

The $15$ considered graph properties and their description are listed in Table
4.

Table 4: Description of the $15$ considered graph properties.

Property | Range |  Description
---|---|---
# nodes | [2,100] |  Count of individual vertices or entities in a graph.
# edges | [1,4950] |  Count of connections or relationships between nodes in the graph.
Density | [0.01,1] |  A measure of how interconnected a graph is, calculated as the number of actual edges over the total possible edges.
Min. degree | [1,99] |  Minimum degree is the smallest degree among all nodes.
Max. degree | [1,99] |  Maximum degree is the largest degree among all nodes.
Avg. degree | [1,99] |  Mean degree across all nodes.
Assortativity coefficient | [-1,1] |  A measure of the tendency of nodes to connect with others of similar degree. Positive values suggest a preference for connections between nodes of similar degrees.
# triangles | [0, 161700] |  Number of sets of three nodes that form a closed loop (triangle) in the network.
Avg. # triangles formed by an edge | [0, 98] |  Average number of triangles each edge participates in.
Max. # triangles formed by an edge | [0, 4851] |  Highest number of triangles a single edge is part of.
Avg. local clustering coefficient | [0, 1] |  A measure of the extent to which nodes in a neighborhood tend to form clusters or cliques.
Global clustering coefficient | [0, 1] |  A measure of the overall tendency of nodes to form clusters in the entire graph, reflecting the global structure of the network.
Max. $k$-core | [0, 99] |  Largest subgraph where each node has at least $k$ neighbors within the subgraph.
# communities | [0, 50] |  Number of clusters of nodes (communities) in the graph.
Diameter | [0, 99] |  Maximum distance between any pair of nodes in the graph.


Transverse Single-Spin Asymmetries of Midrapidity $\pi^{0}$ and $\eta$ Mesons
in $\sqrt{s_{NN}}=200$ GeV $p^{\uparrow}+$Au and $p^{\uparrow}+$Al Collisions
from PHENIX

Dillon Fitzgerald for the PHENIX Collaboration

University of Michigan, Ann Arbor

> Understanding the spin structure of the proton is of large interest to the
> nuclear physics community and it is one of the main goals of the spin
> physics program at the Relativistic Heavy Ion Collider (RHIC). Measurements
> from data taken by the PHENIX detector with transverse ($p^{\uparrow}+p$,
> $p^{\uparrow}$ \+ Al, $p^{\uparrow}$ \+ Au) proton polarization play an
> important role in this, in particular, due to the leading order access to
> gluons in polarized protons. Transverse single-spin asymmetries (TSSAs)
> provide insight into initial and final state spin-momentum and spin-spin
> parton-hadron correlations. In addition to possible final state
> contributions, $\pi^{0}$ and $\eta$ TSSAs access both quark and gluon
> correlations in the polarized proton. Furthermore, the $p^{\uparrow}+A$ data
> from RHIC provides an opportunity to study the effect of TSSAs in the
> presence of additional nuclear matter. Midrapidity $\pi^{0}$ and $\eta$
> mesons are measured at PHENIX by detecting the 2$\gamma$ decay with the
> electromagnetic calorimeter (EMCal) in the central arm spectrometer, which
> has fine granularity for the resolution of separate decay photons. New
> results for TSSAs of midrapidity $\pi^{0}$ and $\eta$ mesons in
> $\sqrt{s_{NN}}=200$ GeV $p^{\uparrow}$ \+ Au and $p^{\uparrow}$ \+ Al
> collisions from the 2015 running year will be presented, and compared with
> the recent $\sqrt{s}=200$ GeV $p^{\uparrow}+p$ results.

> PRESENTED AT
>
> DIS2023: XXX International Workshop on Deep-Inelastic Scattering and Related
> Subjects,
> Michigan State University, USA, 27-31 March 2023
>

##  1 Introduction

The complex nature of hadronic bound states lead to spin-momentum and spin-
spin correlations analogous to the fine and hyperfine structure in atomic
bound states. Transverse single-spin asymmetries (TSSAs) provide insight into
these correlations [1], with measurements at hadron-hadron colliders providing
leading-order access to gluons. TSSAs measure azimuthal modulations of
produced particles in collisions involving polarized hadrons, and are defined
as

$A_{N}(\phi)=\frac{\sigma^{\uparrow}(\phi)-\sigma^{\downarrow}(\phi)}{\sigma^{\uparrow}(\phi)+\sigma^{\downarrow}(\phi)}=A_{N}\cos\phi,$
(1)

where $\sigma^{\uparrow,\downarrow}(\phi)$ correspond to transversely
polarized cross sections for different spin orientations. Negligible
contributions to such observables were predicted from perturbatively
calculable hard scattering coefficients ( $<1\%$) [2]. While more recent
calculations suggest possible modest contributions at 2 loops [3], this is
still far less than the large magnitudes of observed TSSAs across several
collision energies and experiments [4, 5, 6, 7].

Figure 1: Transverse single-spin asymmetries for $\pi^{+}$ (red circles) and
$\pi^{-}$ (black triangles) as a function of $x_{F}=2p_{z}/\sqrt{s}$ for
several different experiments with different collision energies. The
asymmetries grow as large as $40\%$ in magnitude as $x_{F}$ increases, with
opposing sign for $\pi^{+}$ and $\pi^{-}$.

This implies that the mechanism behind the observed TSSAs is nonperturbative.
Two theoretical frameworks have been developed in which the nonperturbative
elements of the asymmetry calculations lead to the large TSSAs observed in
nature: (1) Higher twist effects and (2) Transverse momentum dependent
functions. In the former, power-suppressed terms by the hard scale $Q$ in the
factorization expansion are considered, so the collinear factorization scheme
is preserved, and only a hard scale is needed for the measurement for which
the $p_{T}$ of the measured particle is taken as a proxy. In the latter,
standard collinear parton distribution functions (PDFs) and fragmentation
functions (FFs) are extended to depend on the transverse momentum of partons
within hadrons or in the process of hadronization. In the TMD approach, both a
hard scale ($Q$) and a soft scale ($k_{T}$) must be measured with sufficient
scale separation ($Q>>k_{T}$). Recent TSSAs measurements in polarized $p+p$
collisions at the Relativistic Heavy Ion Collider (RHIC) and the possible
mechanisms contributing to them can be found in Refs. [8, 9, 10, 11, 12, 13,
14, 15, 16]. The TSSAs here are presented as a function of $p_{T}$, making the
higher twist formalism applicable in this case.

In $p^{\uparrow}+A$ collisions, the underlying partonic origins of the
asymmetry could be affected by the presence of a heavy nucleus, making it
particularly interesting to compare TSSAs in various collision systems and
rapidity regions. In a factorized picture, the heavy nucleus should have no
effect on initial-state spin-momentum correlations leading to observed
asymmetries, while final-state spin-momentum correlations can be affected due
to the transport through more nuclear matter and a more complex QCD
environment. On the other hand, in a picture where factorization is broken,
interactions with the nuclear remnant may have some effect on the observed
asymmetry [17, 18]. Recently the theoretical community has proposed comparing
forward hadron TSSAs in $p^{\uparrow}+p$ and $p^{\uparrow}+A$ collisions to
investigate the interplay between spin physics and low-x physics, in
particular, to probe gluon saturation effects in the nucleus [19]. These type
of measurements have been performed at RHIC for forward charged hadrons [20,
21], and forward $J/\psi$ mesons [22] by the PHENIX experiment and forward
neutral pions by the STAR experiment [23]. Strong nuclear dependence was
observed in the case of forward charged hadron production by PHENIX, while
only a moderate dependence was observed by STAR for the $\pi^{0}$ measurement,
despite it being even farther forward in rapidity. Far forward neutron TSSAs
were also measured by PHENIX [24, 25], where nuclear dependence was observed
and understood to be due to the interplay of electromagnetic interactions in
ultra-peripheral collisions and hadronic interactions. These proceedings,
following the work in Ref. [26], show the first measurement of midrapidity
TSSAs in $p^{\uparrow}+A$ collisions for both $\pi^{0}$ and $\eta$ production.
The measurements are also compared with those for midrapidity $\pi^{0}$ and
$\eta$ production from $p^{\uparrow}+p$ collisions from Ref. [11], revealing
no observed nuclear modification in $p^{\uparrow}+A$ collisions.

##  2 Analysis Methods

The data for the measurement were taken in 2015 at RHIC with total integrated
luminosities of approximately 202 and 690 nb-1 for $\sqrt{s_{NN}}=200$ GeV
$p^{\uparrow}$ \+ Au and $p^{\uparrow}$ \+ Al collisions, respectively.
Transverse single-spin asymmetries were measured for both
$\pi^{0}\rightarrow\gamma\gamma$ and $\eta\rightarrow\gamma\gamma$ production
at midrapidity ($|\eta|<0.35$) using the electromagnetic calorimeters (EMCal)
in the central arm spectrometers at PHENIX. An EMCal trigger was used in
coincidence with a minimum bias trigger to select high $p_{T}$ photons for
this analysis. In addition, tracks measured by the drift and pad chambers in
the central arm spectrometer that are associated with an EMCal cluster are
vetoed to remove background from charged particles. For more information
regarding the PHENIX detector subsystems relevant for this measurement, and
the selection criteria placed on the $\pi^{0}\rightarrow\gamma\gamma$ and
$\eta\rightarrow\gamma\gamma$ candidates, see Ref. [26], where the measurement
is described in detail. Figure 2 shows the diphoton invariant mass
distributions around the $\pi^{0}$ and $\eta$ peaks for photon pairs within
$4<p_{T}<5$ GeV/$c$ in the west central arm spectrometer in $p^{\uparrow}$ \+
Au and $p^{\uparrow}$ \+ Al collisions.

Figure 2: Invariant mass distributions around the
$\pi^{0}\rightarrow\gamma\gamma$ peak in (a) $p^{\uparrow}$ \+ Au collisions
and (b) $p^{\uparrow}$ \+ Al collisions and around the
$\eta\rightarrow\gamma\gamma$ peak in (c) $p^{\uparrow}$ \+ Au collisions and
(d) $p^{\uparrow}$ \+ Al collisions for photon pairs within $4<p_{T}~{}[{\rm
GeV}/c]<5$ in the west central-arm spectrometer from Ref. [26]. The blue
leftward-hatched regions are the signal peaks, used for quantifying yields for
the $A^{N}$ calculations, the red rightward-hatched regions are the side
bands, used to quantify yields for the $A_{N}^{\rm BG}$ calculations, and the
green solid curves correspond to fits to the combinatorial background, used in
calculating the background fractions ($r$).

Once the $\pi^{0}\rightarrow\gamma\gamma$ and $\eta\rightarrow\gamma\gamma$
samples are curated, TSSAs can be calculated from yields shown in the blue
leftward hatched region of Fig. 2 using the “relative luminosity” formula,
which is equivalent to Eq. 1 with additional correction factors for the proton
beam polarization fraction and the azimuthal detector coverage of the central
arm spectrometers at PHENIX. It is defined as

$A_{N}=\frac{1}{P\left<|\cos\phi|\right>}\frac{{N^{\uparrow}}-\mathcal{R}{N^{\downarrow}}}{{N^{\uparrow}}+\mathcal{R}{N^{\downarrow}}},$
(2)

where $P$ is the beam polarization, and $\mathcal{R}$ is the relative
luminosity, defined as the ratio of integrated luminosities between the
bunches with $\uparrow$ and $\downarrow$ spin states.
$\left<|\cos\phi|\right>$ is the azimuthal acceptance factor of the detector,
calculated separately for each $p_{T}$ bin and spectrometer arm, and $N$
refers to the yields, with the arrows referring to the up ($\uparrow$) or down
($\downarrow$) polarization of the proton beam. The measured asymmetries were
corrected for background as follows,

$A_{N}^{\rm sig}=\frac{A_{N}-r\cdot A_{N}^{\rm BG}}{1-r},$ (3)

where $A_{N}$ is the asymmetry calculated in the signal region with Equation
2, $r$ is the background fraction under the $\pi^{0}$ or $\eta$ peaks,
calculated from the background fits, and $A_{N}^{\rm BG}$ is the background
asymmetry, which was evaluated in the side bands on both sides of the
$\pi^{0}$ and $\eta$ peaks. The background asymmetry was consistent with zero
across collision systems and particle species for the entire measured $p_{T}$
range. Details on cross-checks and systematic studies can be found in Ref.
[26].

##  3 Results

The TSSA ($A_{N}$) for midrapidity $\pi^{0}$ and $\eta$ mesons are shown in
Fig. 3, with the $\pi^{0}$ results shown in panel (a), and the $\eta$ results
shown in panel (b). The asymmetries for $p^{\uparrow}$ \+ Au and
$p^{\uparrow}$ \+ Al collisions from Ref. [26] are plotted with blue circles
and green squares respectively. The $p^{\uparrow}+A$ results are plotted
alongside the $p^{\uparrow}+p$ results from Ref. [11], shown in black diamonds
for comparison. All asymmetries in Fig. 3 are consistent with zero, meaning
there is no nuclear modification of the TSSA observed at midrapidity.

Figure 3: Transverse single-spin asymmetry for (a) $\pi^{0}$ and (b) $\eta$
mesons in $p^{\uparrow}$ \+ Au collisions (blue circles), and $p^{\uparrow}$
\+ Al collisions (green squares) from Ref. [26], shown alongside the same
measurement in $p^{\uparrow}+p$ collisions from Ref. [11] (black diamonds).
The error bars represent the statistical uncertainty ($\sigma^{\rm stat}$)
while the boxes represent the total systematic uncertainty ($\sigma^{\rm
syst}$).

##  4 Summary

TSSA measurements in $p^{\uparrow}+A$ collisions using the 2015 RHIC data have
yielded surprises and led to many open questions in the spin physics
community. Presented were the results from the first midrapidity TSSA
measurement from the 2015 RHIC $p^{\uparrow}+A$ data, in particular, for
midrapidity ($|\eta|<0.35$) $\pi^{0}\rightarrow\gamma\gamma$ and
$\eta\rightarrow\gamma\gamma$ production in $\sqrt{s_{NN}}=200$ GeV
$p^{\uparrow}$+Au and $p^{\uparrow}$+Al collisions [26]. This measurement
serves as an important milestone in our understanding of the modification of
such observables in the presence of additional nuclear matter.

## References

  * [1] M. Anselmino, A. Mukherjee, and A. Vossen.  Transverse spin effects in hard semi-inclusive collisions.  Prog. Part. Nucl. Phys., 114:103806, 2020.
  * [2] G. L. Kane, J. Pumplin, and W. Repko.  Transverse Quark Polarization in Large-${p}_{T}$ Reactions, $e^{+}e^{-}$ Jets, and Leptoproduction: A Test of Quantum Chromodynamics.  Phys. Rev. Lett., 41:1689, Dec 1978.
  * [3] S. Benic, Y. Hatta, H.-n. Li, and D.-J. Yang.  Single-spin asymmetries at two loops.  Phys. Rev. D, 100(9):094027, 2019.
  * [4] R. D. Klem, J. E. Bowers, H. W. Courant, H. Kagan, M. L. Marshak, E. A. Peterson, K. Ruddick, W. H. Dragoset Jr., and J. B. Roberts.  Measurement of Asymmetries of Inclusive Pion Production in Proton Proton Interactions at 6 and 11.8 GeV/c.  Phys. Rev. Lett., 36:929, 1976.
  * [5] D. L. Adams et al.  Analyzing power in inclusive $\pi^{+}$ and $\pi^{-}$ production at high $x_{F}$ with a 200-GeV polarized proton beam.  Phys. Lett. B, 264:462, 1991.
  * [6] C. E. Allgower et al.  Measurement of analyzing powers of $\pi^{+}$ and $\pi^{-}$ produced on a hydrogen and a carbon target with a 22-GeV/$c$ incident polarized proton beam.  Phys. Rev. D, 65:092008, 2002.
  * [7] I. Arsene et al.  Single Transverse Spin Asymmetries of Identified Charged Hadrons in Polarized $p+p$ Collisions at $\sqrt{s}$ = 62.4 GeV.  Phys. Rev. Lett., 101:042001, 2008.
  * [8] U. Acharya et al.  Improving constraints on gluon spin-momentum correlations in transversely polarized protons via midrapidity open-heavy-flavor electrons in $p^{\uparrow}+p$ collisions at $\sqrt{s}=200$ GeV.  arXiv:2204.12899.
  * [9] U. Acharya et al.  Transverse-single-spin asymmetries of charged pions at midrapidity in transversely polarized $p{+}p$ collisions at $\sqrt{s}=200$ GeV.  Phys. Rev. D, 105(3):032003, 2022.
  * [10] U. Acharya et al.  Probing Gluon Spin-Momentum Correlations in Transversely Polarized Protons through Midrapidity Isolated Direct Photons in $p^{\uparrow}+p$ Collisions at $\sqrt{s}$=200 GeV.  Phys. Rev. Lett., 127(16):162001, 2021.
  * [11] U. Acharya et al.  Transverse single-spin asymmetries of midrapidity $\pi^{0}$ and $\eta$ mesons in polarized $p+p$ collisions at $\sqrt{s}=200$ GeV.  Phys. Rev. D, 103(5):052009, 2021.
  * [12] U. Acharya et al.  Transverse momentum dependent forward neutron single spin asymmetries in transversely polarized $p+p$ collisions at $\sqrt{s}$ = 200 GeV.  Phys. Rev. D, 103(3):032007, 2021.
  * [13] M. Abdallah et al.  Azimuthal transverse single-spin asymmetries of inclusive jets and identified hadrons within jets from polarized $pp$ collisions at $\sqrt{s}$ = 200 GeV.  Phys. Rev. D, 106(7):072010, 2022.
  * [14] J. Adam et al.  Measurement of transverse single-spin asymmetries of $\pi^{0}$ and electromagnetic jets at forward rapidity in 200 and 500 GeV transversely polarized proton-proton collisions.  Phys. Rev. D, 103(9):092009, 2021.
  * [15] L. Adamczyk et al.  Transverse spin-dependent azimuthal correlations of charged pion pairs measured in p↑+p collisions at $\sqrt{s}$ = 500 GeV.  Phys. Lett. B, 780:332–339, 2018.
  * [16] L. Adamczyk et al.  Azimuthal transverse single-spin asymmetries of inclusive jets and charged pions within jets from polarized-proton collisions at $\sqrt{s}=500$ GeV.  Phys. Rev. D, 97(3):032004, 2018.
  * [17] T. C. Rogers and P. J. Mulders.  No Generalized TMD-Factorization in Hadro-Production of High Transverse Momentum Hadrons.  Phys. Rev. D, 81:094006, 2010.
  * [18] T. C. Rogers.  Extra spin asymmetries from the breakdown of transverse-momentum-dependent factorization in hadron-hadron collisions.  Phys. Rev. D, 88(1):014002, 2013.
  * [19] Z. B. Kang and F. Yuan.  Single Spin Asymmetry Scaling in the Forward Rapidity Region at RHIC.  Phys. Rev. D, 84:034019, 2011.
  * [20] C. Aidala et al.  Nuclear Dependence of the Transverse Single-Spin Asymmetry in the Production of Charged Hadrons at Forward Rapidity in Polarized $p+p$, $p+$Al, and $p+$Au Collisions at $\sqrt{s_{{}_{NN}}}=200$ GeV.  Phys. Rev. Lett., 123(12):122001, 2019.
  * [21] N. J. Abdulameer et al.  Transverse single-spin asymmetry of midrapidity charged hadrons in $p$$+$Au and $p$$+$Al collisions at $\sqrt{s_{{}_{NN}}}=200$ GeV.  arXiv:2303.07191.
  * [22] C. Aidala et al.  Single-spin asymmetry of $J/\psi$ production in $p+p$, $p+$Al, and $p+$Au collisions with transversely polarized proton beams at $\sqrt{s_{{}_{NN}}}=200$ GeV.  Phys. Rev. D, 98(1):012006, 2018.
  * [23] J. Adam et al.  Comparison of transverse single-spin asymmetries for forward $\pi^{0}$ production in polarized $pp$, $p\rm{Al}$ and $p\rm{Au}$ collisions at nucleon pair c.m. energy $\sqrt{s_{\mathrm{NN}}}=200$ GeV.  Phys. Rev. D, 103(7):072005, 2021.
  * [24] C. Aidala et al.  Nuclear Dependence of the Transverse-Single-Spin Asymmetry for Forward Neutron Production in Polarized $p+A$ Collisions at $\sqrt{{s}_{NN}}=200$ GeV.  Phys. Rev. Lett., 120(2):022001, 2018.
  * [25] U. Acharya et al.  Transverse single spin asymmetries of forward neutrons in $p+p$, $p+$Al and $p+$Au collisions at $\sqrt{s_{{}_{NN}}}=200$ GeV as a function of transverse and longitudinal momenta.  Phys. Rev. D, 105(3):032004, 2022.
  * [26] N. J. Abdulameer et al.  Transverse single-spin asymmetry of midrapidity $\pi$0 and $\eta$ mesons in p+Au and p+Al collisions at sNN=200 GeV.  Phys. Rev. D, 107(11):112004, 2023.


# A note on distance variance for categorical variables

Qingyang Zhang
Department of Mathematical Sciences, University of Arkansas, AR 72701
Email<EMAIL_ADDRESS>
###### Abstract

This study investigates the extension of distance variance, a validated spread
metric for continuous and binary variables [Edelmann et al., 2020, Ann. Stat.,
48(6)], to quantify the spread of general categorical variables. We provide
both geometric and algebraic characterizations of distance variance, revealing
its connections to some commonly used entropy measures, and the variance-
covariance matrix of the one-hot encoded representation. However, we
demonstrate that distance variance fails to satisfy the Schur-concavity axiom
for categorical variables with more than two categories, leading to
counterintuitive results. This limitation hinders its applicability as a
universal measure of spread.

Keywords: Categorical data; measures of spread; distance variance; entropy

##  1 Introduction

Quantifying the spread of data is a fundamental task in statistics and various
scientific disciplines. For continuous variables, well-established measures
like variance, trimmed variance, and interquartile range (IQR) are readily
available. However, measuring spread for categorical (nominal) variables poses
a unique challenge, because these variables lack inherent order or a direct
numerical representation. Traditional approaches for categorical variables,
such as the Gini index, focus on the level of uncertainty associated with
random sampling. Newer measures based on penalty functions are more
attractive, as they can be interpreted in terms of prediction [1, 2]. Despite
these advancements, a universal measure of spread that seamlessly applies to
both continuous and categorical variables remains elusive.

Since the seminal work of Székely et al. (2007), distance correlation analysis
has gained popularity among statisticians and practitioners. This correlation
metric is distribution-free and can handle diverse variable types, including
categorical variables and random vectors [3, 4, 5]. Notably, distance
correlation shares a conceptual similarity with Pearson’s correlation. It can
be expressed as distance covariance normalized by distance variance. Edelmann
et al. (2020) explored the distance variance as a potential spread measure for
continuous and binary data [6]. Importantly, they demonstrated that distance
variance satisfies Bickel & Lehmann’s three axioms [7], solidifying its
potential as a valid measure of spread. Motivated by the pursuit of a
universal spread metric, this paper investigates the applicability of distance
variance to quantify the spread of general categorical variables.

We begin with the mathematical expressions of this metric. Let $X$ be a
categorical variable taking values from $\\{1,~{}...,~{}K\\}$ with probability
mass function $P(X=k)=\pi_{k}$, where $\pi_{k}>0$ and
$\sum_{k=1}^{K}\pi_{k}=1$. A one-hot encoded representation of $X$ is
$\mathbf{Z}=(I\\{X=1\\},...,I\\{X=K\\})^{T}$. The distance variance of $X$
based on Euclidean distance, i.e.,
$d(x_{1},~{}x_{2}):=|\mathbf{z}_{1}-\mathbf{z}_{2}|_{2}=0$ if $x_{1}=x_{2}$
and $\sqrt{2}$ otherwise, can be expressed as follows ([5], eq. 3)

$\displaystyle\mathcal{V}(X)$
$\displaystyle=\left\\{E[d^{2}(X_{1},~{}X_{2})]+E^{2}[d(X_{1},~{}X_{2})]-2E[d(X_{1},~{}X_{2})d(X_{1},~{}X_{3})]\right\\}^{\frac{1}{2}}$
$\displaystyle=\sqrt{2}\left[\left(\sum_{k=1}^{K}\pi_{k}^{2}\right)^{2}+\sum_{k=1}^{K}\pi_{k}^{2}-2\sum_{k=1}^{K}\pi_{k}^{3}\right]^{\frac{1}{2}},$
(1)

where $(X_{1},~{}X_{2},~{}X_{3})$ are three independent copies of $X$.
Interestingly, for categorical variables, distance variance is invariant (up
to a constant) of the choice of distance metrics. For instance, the
$\alpha$-distance variance [3] can be expressed as

$\displaystyle\mathcal{V}_{\alpha}(X)$
$\displaystyle=\left\\{E[d^{2\alpha}(X_{1},~{}X_{2})]+E^{2}[d^{\alpha}(X_{1},~{}X_{2})]-2E[d^{\alpha}(X_{1},~{}X_{2})d^{\alpha}(X_{1},~{}X_{3})]\right\\}^{\frac{1}{2}}$
$\displaystyle=2^{\frac{\alpha}{2}}\left[\left(\sum_{k=1}^{K}\pi_{k}^{2}\right)^{2}+\sum_{k=1}^{K}\pi_{k}^{2}-2\sum_{k=1}^{K}\pi_{k}^{3}\right]^{\frac{1}{2}}.$

The distance variance based on the Gaussian kernel with bandwidth
$\sigma^{2}$, i.e.,
$d(x_{1},~{}x_{2}):=\kappa(\mathbf{z}_{1},\mathbf{z}_{2})=\exp(-|\mathbf{z}_{1}-\mathbf{z}_{2}|_{2}/\sigma^{2})$,
is also equivalent to $\mathcal{V}(X)$

$\displaystyle\mathcal{V}_{\kappa}(X,\sigma^{2})$
$\displaystyle=\left\\{E[\kappa^{2}(\mathbf{Z}_{1},~{}\mathbf{Z}_{2})]+E^{2}[\kappa(\mathbf{Z}_{1},~{}\mathbf{Z}_{2})]-2E[\kappa(\mathbf{Z}_{1},~{}\mathbf{Z}_{2})\kappa(\mathbf{Z}_{1},~{}\mathbf{Z}_{3})]\right\\}^{\frac{1}{2}}$
$\displaystyle=\left(1-e^{-\frac{\sqrt{2}}{\sigma^{2}}}\right)\left[\left(\sum_{k=1}^{K}\pi_{k}^{2}\right)^{2}+\sum_{k=1}^{K}\pi_{k}^{2}-2\sum_{k=1}^{K}\pi_{k}^{3}\right]^{\frac{1}{2}}.$

More generally, it can be shown that for any two constants $c_{1}\neq c_{2}$,
such that $|X_{1}-X_{2}|=c_{1}$ if $X_{1}=X_{2}$ and $c_{2}$ otherwise, the
distance variance is equivalent to $\mathcal{V}(X)$ up to a constant (proof is
provided in the Appendix). Throughout this paper, we refer to $\mathcal{V}(X)$
based on Euclidean distance, unless otherwise stated. Given a sequence of
independent and identically distributed (i.i.d.) samples of $X$, an unbiased
estimate of $\mathcal{V}^{2}(X)$ can be computed as follows ([8], page 14)

$\displaystyle\widehat{\mathcal{V}^{2}(X)}=$
$\displaystyle\frac{n^{3}}{(n-1)(n-2)(n-3)}\left(1-\sum_{k=1}^{K}\widehat{\pi}_{k}^{2}\right)^{2}-\frac{2n^{2}}{(n-2)(n-3)}\sum_{k=1}^{K}\widehat{\pi}_{k}^{3}$
$\displaystyle-\frac{n(n-6)}{(n-2)(n-3)}\sum_{k=1}^{K}\widehat{\pi}_{k}^{2}-\frac{n(n+2)}{(n-2)(n-3)},$

where $n$ is the sample size and $\widehat{\pi}_{k}$ is the maximum likelihood
estimate of $\pi_{k}$. The estimate $\widehat{\mathcal{V}^{2}(X)}$ is
essentially a fourth-order U-statistics, which is asymptotical normal.
Standard methods for U-statistics such as Jackknifing can be directly applied
for hypothesis testing purpose [9].

While the validity and usefulness of distance variance as a spread metric is
well-established for continuous and binary variables, its suitability for
multi-category variables (i.e., with $K\geq 3$ categories) remains unexplored.
One challenge lies in interpreting $\mathcal{V}(X)$, which involves three
independent samples $(X_{1},~{}X_{2},~{}X_{3})$. This complexity makes a
straightforward interpretation difficult. This paper addresses two key
questions:

  * Q1.

How can we interpret distance variance for general categorical variables in
intuitive ways?

  * Q2.

Is distance variance a valid measure of spread for general categorical
variables?

For Q1, we propose alternative interpretations of distance variance using
matrix norms and inter-point distances, offering a more intuitive
understanding. Unfortunately, for Q2, we show that distance variance is not a
valid measure of spread for variables with more than two categories, and its
misuse can lead to counterintuitive results.

The remainder of this paper is structured as follows: Section 2 characterizes
distance variance and proposes a broad class of spread measures based on these
characterizations. Section 3 first introduces a set of axioms, then
demonstrates that distance variance violates the condition of strict Schur-
concavity. Section 4 discusses the findings and concludes the paper.

##  2 Geometric and algebraic characterizations for distance variance

In this section, we give two intuitive interpretations of distance variance.
These interpretations reveal important connections between the distance
variance $\mathcal{V}(X)$, the variance-covariance matrix of $\mathbf{Z}$ and
some popular entropy measures. We further propose a class of similar measures
with potential applications as spread metrics. The validity of these proposed
measures is discussed in Section 3. For clarity, we denote the $L_{p}$-norm
for vectors by $|\cdot|_{p}$ and for matrices by $\|\cdot\|_{p}$ throughout
the paper.

###  2.1 Geometric characterization

For notational convenience, we define $\mathbf{Z}(k)$ as the one-hot encoded
representation of $X=k$, i.e., $\mathbf{Z}(k)$ is a vector with 1 in its $k$th
position and 0 elsewhere. For example, when $K=3$,
$\mathbf{Z}(1)=(1,~{}0,~{}0)$, $\mathbf{Z}(2)=(0,~{}1,~{}0)$,
$\mathbf{Z}(3)=(0,~{}0,~{}1)$. The mean vector,
$E(\mathbf{Z})=(\pi_{1},~{}...,~{}\pi_{K})$, can be considered as the
geometric center of $[\mathbf{Z}(1),~{}...,~{}\mathbf{Z}(K)]$. Interestingly,
we find that the squared distance variance, $\mathcal{V}^{2}(X)$, is closely
related to the distances between each ${Z}(k)$ and the geometric center
$E(\mathbf{Z})$. Specifically, it can be expressed as

$\mathcal{V}^{2}(X)=2\sum_{k=1}^{K}\pi^{2}_{k}|\mathbf{Z}(k)-E(\mathbf{Z})|_{2}^{2}.$
(2)

###### Proof.

$\displaystyle\sum_{k=1}^{K}\pi^{2}_{k}|\mathbf{Z}(k)-E(\mathbf{Z})|_{2}^{2}$
$\displaystyle=\sum_{k=1}^{K}\pi^{2}_{k}\left[(1-\pi_{k})^{2}+\sum_{k^{\prime}=1}^{K}\pi^{2}_{k^{\prime}}-\pi^{2}_{k}\right]$
$\displaystyle=\sum_{k=1}^{K}\pi^{2}_{k}(1-\pi_{k})^{2}+\left(\sum_{k=1}^{K}\pi^{2}_{k}\right)^{2}-\sum_{k=1}^{K}\pi^{4}_{k}$
$\displaystyle=\left(\sum_{k=1}^{K}\pi^{2}_{k}\right)^{2}+\sum_{k=1}^{K}\pi^{2}_{k}-2\sum_{k=1}^{K}\pi^{3}_{k}$
$\displaystyle=\frac{1}{2}\mathcal{V}^{2}(X).$

∎

Equation 2 reveals that the squared distance variance can be interpreted as a
weighted average of the squared distances between each category and the
geometric center. Figure 1 illustrates this for two specific cases, $K=2$ and
$K=3$.

Figure 1: Geometric interpretations of distance variance for $K=2$ and $K=3$,
where $d_{k}$ represents the Euclidean distance between $\mathbf{Z}(k)$ and
$E(\mathbf{Z})$.

Motivated by the geometric interpretation of $\mathcal{V}^{2}(X)$, we propose
a generalized version

$\Delta_{g}(X,~{}w,~{}l,~{}p)=\sum_{k=1}^{K}w(\pi_{k})|\mathbf{Z}(k)-E(\mathbf{Z})|_{p}^{l},$

where the subscript $g$ denotes the geometric extension. The squared distance
variance is a special case with $p=2$, $l=2$, $w(\pi_{k})=\pi^{2}_{k}$.
Another special case is the Gini index (also known as Rényi entropy),
$G(X)=1-\sum_{k=1}^{K}\pi_{k}^{2}$, when $p=1$, $l=1$ and $w(\pi_{k})=\pi_{k}$
or $w(\pi_{k})=1+\pi_{k}$.

Furthermore, for $p=1$, $l=1$, and a specific weighting function
$w(\pi_{k})=1/(m-1)\cdot\sum_{q=0}^{m-1}\pi^{q}_{k}$, where $m>1$,
$\Delta_{g}(X,~{}w,~{}l,~{}p)$ coincides with Tsallis entropy [10], defined as

$H_{m}(X)=\frac{1}{m-1}\left(1-\sum_{k=1}^{K}\pi_{k}^{m}\right).$

Notably, Tsallis entropy encompasses several well-known entropy measures. This
includes the Gini index $H_{2}(X)$ and Shannon entropy, obtained as the limit
of Tsallis entropy when $m$ approaches 1, $H_{1}(X):=\lim_{m\rightarrow
1}H_{m}(X)=-\sum_{k=1}^{K}\pi_{k}\log\pi_{k}$. Another intriguing special case
of $\Delta_{g}(X,~{}w,~{}l,~{}p)$ is the extropy, defined as
$J(X)-\sum_{k=1}^{K}(1-\pi_{k})\log(1-\pi_{k})$. Extropy acts as the
complementary dual of Shannon entropy (see Lad et al., 2015 for a detailed
discussion on entropy and extropy). Within our framework, it’s straightforward
to verify that $J(X)$ aligns with $\Delta_{g}(X,~{}w,~{}l,~{}p)$ when $p=1$,
$l=1$ and $w(\pi_{k})=-\log(1-\pi_{k})$.

In addition to these established entropy measures, our framework allows for
the construction of many new metrics through various combinations of $l$, $p$
and $w$. The general validity of $\Delta_{g}(X,~{}w,~{}l,~{}p)$ will be
explored in Section 3.

###  2.2 Algebraic characterization

A key distinction between distance variance and existing measures such as
Tsallis entropy and extropy lies in the functional expression. Distance
variance incorporates terms like $\pi_{k}\pi_{k^{\prime}}$ (where $k\neq
k^{\prime}$) that arise in the first term of Equation 1, while other measures
rely solely on marginal probabilities $\pi_{k}$. Note that
$\mbox{Cov}(I\\{X=k\\},~{}I\\{X=k^{\prime}\\})=-\pi_{k}\pi_{k^{\prime}}$ for
any $k\neq k^{\prime}$. This suggests a strong connection between distance
variance and the variance-covariance matrix of the one-hot encoded
representation, given by

$V(\mathbf{Z})=\begin{bmatrix}\pi_{1}(1-\pi_{1})&-\pi_{1}\pi_{2}&\dots&-\pi_{1}\pi_{K}\\\
-\pi_{2}\pi_{1}&\pi_{2}(1-\pi_{2})&\dots&-\pi_{2}\pi_{K}\\\
\vdots&\vdots&\ddots&\vdots\\\
-\pi_{K}\pi_{1}&-\pi_{K}\pi_{2}&\dots&\pi_{K}(1-\pi_{K})\end{bmatrix}.$

Furthermore, the squared covariance terms in $\mathcal{V}^{2}(X)$ suggest a
close relationship between distance variance and the $L_{2}$-norm (Frobenius
norm) of $V(\mathbf{Z})$. In fact, a direct relationship can be established

$\mathcal{V}(X)=\sqrt{2}\|V(\mathbf{Z})\|_{2}.$ (3)

###### Proof.

$\displaystyle\|V(\mathbf{Z})\|^{2}_{2}$
$\displaystyle=\sum_{k=1}^{K}\pi_{k}^{2}(1-\pi_{k})^{2}+\sum_{k=1}^{K}\sum_{k^{\prime}\neq
k}\pi_{k}^{2}\pi_{k^{\prime}}^{2}$
$\displaystyle=\sum_{k=1}^{K}\pi_{k}^{2}(1-\pi_{k})^{2}+\left(\sum_{k=1}^{K}\pi_{k}^{2}\right)^{2}-\sum_{k=1}^{K}\pi_{k}^{4}$
$\displaystyle=\left(\sum_{k=1}^{K}\pi_{k}^{2}\right)^{2}+\sum_{k=1}^{K}\pi_{k}^{2}-2\sum_{k=1}^{K}\pi_{k}^{3}$
$\displaystyle=\frac{1}{2}\mathcal{V}^{2}(X).$

∎

Equation 3 reveals that distance variance is equivalent to the $L_{2}$-norm of
the variance-covariance matrix. Naturally, one may consider a possible
extension using $L_{p}$ norms of $V(\mathbf{Z})$

$\Delta_{a}(X,p)=\|V(\mathbf{Z})\|_{p}=\left\\{\sum_{k=1}^{K}\pi_{k}^{p}(1-\pi_{k})^{p}+\left[\sum_{k=1}^{K}\pi_{k}^{p}\right]^{2}-\sum_{k=1}^{K}\pi_{k}^{2p}\right\\}^{1/p},$

where the subscript $a$ represents algebraic extension. Two immediate special
cases are

$\displaystyle\Delta_{a}(X,p=1)$
$\displaystyle=\|V(\mathbf{Z})\|_{1}=2H_{2}(X),$ (4)
$\displaystyle\Delta_{a}(X,p=\infty)$
$\displaystyle=\|V(\mathbf{Z})\|_{\infty}=\max_{1\leq k\leq
K}(\pi_{k}-\pi^{2}_{k}).$ (5)

Equation 4 indicates that the Gini index (or Rényi entropy) aligns with the
$L_{1}$-norm of $V(\mathbf{Z})$. It is also noteworthy that
$\Delta_{a}^{p}(X,p)$ is a special case of the more general framework
$\Delta_{g}(X,~{}w,~{}l,~{}p)$ when $l=p$ and $w(\pi_{k})=\pi_{k}^{p}$.
Therefore, in Section 3, we will focus on exploring the validity of the
broader concept $\Delta_{g}(X,~{}w,~{}l,~{}p)$.

##  3 Validity and counterintuitive results

To assess the validity of distance variance and related measures for
categorical variables, we suggest a set of axioms for spread measures based on
majorization and Schur-concavity [11]. We begin with the notations. Let
$\mathcal{S}^{d}=\\{(x_{1},~{}...,~{}x_{d}),~{}\min_{1\leq i\leq d}x_{i}\geq
0,~{}\sum_{i=1}^{d}x_{i}=1\\}$ be the simplex of dimension $d$. Majorization
is a concept used to describe how spread out a discrete probability
distribution is. For $\pi,~{}\pi^{\prime}\in S^{K}$, $\pi$ is said to be
majorized by $\pi^{\prime}$, denoted by $\pi\prec\pi^{\prime}$, if the
following condition is satisfied

$\sum_{k=i}^{K}\pi_{(k)}\leq\sum_{k=i}^{K}\pi^{\prime}_{(k)},~{}i=2,...,K,$

where $\pi_{(1)}\leq\pi_{(2)}\leq...\leq\pi_{(K)}$ and
$\pi^{\prime}_{(1)}\leq\pi^{\prime}_{(2)}\leq...\leq\pi^{\prime}_{(K)}$
represent the components of $\pi$ and $\pi^{\prime}$ sorted in ascending
order. We say $\pi$ is strictly majorized by $\pi^{\prime}$, denoted by
$\pi\prec_{s}\pi^{\prime}$, if there exists at least one index $i$ such that
$\sum_{k=i}^{K}\pi_{(k)}<\sum_{k=i}^{K}\pi^{\prime}_{(k)}$.

This definition extends to vectors of different lengths by appending zeros to
the shorter vector. An immediate observation is

$(\frac{1}{K},~{}...,~{}\frac{1}{K})\prec(\frac{1}{K-1},~{}...,~{}\frac{1}{K-1},~{}0)\prec...(\frac{1}{2},~{}\frac{1}{2},~{}0,~{}...,~{}0)\prec(1,~{}0,~{}...,~{}0).$

To illustrate majorization further, consider two examples:

######  Example 1.

$\left(1/3,~{}1/3,~{}1/3\right)\prec\left(1/2,~{}1/2,~{}1/4\right)$ because
$1/3<1/2$ and $1/3+1/3<1/2+1/4$. The second distribution has higher
probability mass concentrated in two categories, indicating less spread.

######  Example 2.

$\left(1/6,~{}1/6,~{}2/6,~{}2/6\right)\prec\left(1/10,~{}2/10,~{}3/10,~{}4/10\right)$
because $2/6<4/10$, $2/6+2/6<3/10+4/10$, and $1/6+2/6+2/6<2/10+3/10+4/10$.
Again, the second distribution has a more concentrated probability mass,
demonstrating less spread.

We propose a set of axioms for spread measures, denoted by $\Delta(\pi)$ or
$\Delta(X)$ for a categorical variable $X$ with probability distribution
$\pi$. These axioms aim to capture the concept of how spread out a
distribution is across its categories.

  * (A1)

$\Delta(\pi)\geq 0$, where the equality holds if and only if there exists a
single category $k$ such that $\pi_{k}=1$.

  * (A2)

$\Delta(\pi)$ is continuously differentiable.

  * (A3)

If $\pi\prec_{s}\pi^{\prime}$, $\Delta(\pi)>\Delta(\pi^{\prime})$.

######  Remark 1.

In the terminology of Marshall & Olkin (1979), a functional satisfying A3 is
said to be strictly Schur-concave (strictly increases as $\pi$ becomes more
uniform). For continuously differentiable functions (as assumed in A2), strict
Schur-covavity can be verified using partial derivatives (Marshall & Olkin,
1979, Theorem A.4.b, page 85). To be specific, let
$\Delta_{(k)}=\partial\Delta/\partial\pi_{k}$ and
$\Delta_{(k,k^{\prime})}=\partial^{2}\Delta/\partial\pi_{k}\partial\pi_{k^{\prime}}$
be the first- and second-order partial derivatives of $\Delta$, necessary and
sufficient conditions for $\Delta$ to be strictly Schur-concave are (1)
$\Delta$ is twice differentiable and symmetric (2)
$\Delta_{(k)}(\pi)>\Delta_{(k^{\prime})}(\pi)$ for $\pi_{k}<\pi_{k^{\prime}}$
(3) $\Delta_{(k)}(\pi)=\Delta_{(k^{\prime})}(\pi)$ implies
$\Delta_{(k,k)}(\pi)+\Delta_{(k^{\prime},k^{\prime})}(\pi)-\Delta_{(k,k^{\prime})}(\pi)-\Delta_{(k^{\prime},k)}(\pi)<0$.

######  Remark 2.

None of the proposed axioms necessarily imply the others. For example, A3
(Schur-concavity) in general does not guarantee A2 (continuous
differentiability).

######  Remark 3.

Some existing spread measures, like D-dispersion (Gilula & Haberman, 1995,
Definition 1), incorporate symmetry as an axiom. In our axioms, A3 inherently
implies symmetry. Let $\pi_{perm}$ be a permutation of $\pi$. As $\Delta$ is
Schur-concave and $\pi\prec\pi_{perm}$, we have
$\Delta(\pi)\geq\Delta(\pi_{perm})$. On the other hand, as
$\pi_{perm}\prec\pi$, we have $\Delta(\pi_{perm})\geq\Delta(\pi)$, therefore
$\Delta(\pi_{perm})=\Delta(\pi)$.

######  Remark 4.

Our axioms differ from the existing ones. For instance, A3 implies Shannon’s
second axiom regarding monotonicity (to be specific,
$\Delta(1/K,~{}...,~{}1/K)$ is a monotonically increasing function of the
dimension $K$). However, a measure satisfying A1-A3 might not satisfy
Shannon’s third axiom regarding additivity

$\Delta(\pi_{1},~{}...,~{}\pi_{k-1},~{}t\pi_{k},~{}(1-t)\pi_{k},~{}\pi_{k+1},~{}...,~{}\pi_{K})=\Delta(\pi)+\pi_{k}\Delta(t,~{}1-t),$

for any $\pi_{k}\in[0,~{}1]$, any $t\in[0,~{}1]$ and any positive integer $K$.
In his seminal paper, Shannon elegantly showed that the entropy function
$\Delta(\pi)=-\sum_{k=1}^{K}\pi_{k}\log\pi_{k}$ is the only function that
fulfills all his axioms. Additionally, A2 is a stronger condition compared to
the continuity required by D-dispersion. However, continuous differentiability
is necessary for verifying strict Schur-concavity. Finally, a D-dispersion
that is also strictly concave satisfies strict Schur-concavity.

We now examine the validity of some well-known measures. First, it is
straightforward to verify that Shannon entropy, extropy and Tsallis entropy
$(m>1)$ all satisfy the three axioms. Taking Tsallis entropy as an example, A1
is satisfied as $\sum_{k=1}^{K}\pi^{m}_{k}\leq\sum_{k=1}^{K}\pi_{k}$ (equality
holds only when $K=1$). Additionally, $H_{m}(\pi)$ is symmetric and twice
differentiable with partial derivative $H_{m(k)}(\pi)=-m\pi_{k}^{m-1}/(m-1)$,
therefore $H_{m(k)}(\pi)>H_{m(k^{\prime})}(\pi)$ for
$\pi_{k}<\pi_{k^{\prime}}$. Finally, the second-order partial derivatives are
$H_{m(k,~{}k)}(\pi)=-m\pi_{k}^{m-2}$ and $H_{m(k,~{}k^{\prime})}(\pi)=0$,
therefore
$H_{m(k,k)}(\pi)+H_{m(k^{\prime},k^{\prime})}(\pi)-H_{m(k,k^{\prime})}(\pi)-H_{m(k^{\prime},k)}(\pi)<0$.
As a special case of Tsallis entropy when $m=2$, Gini index also qualifies as
a valid measure.

For $K=2$, distance variance can be expressed as $2\sqrt{2}\pi(1-\pi)$ (same
as variance up to a constant), which satisfies the three axioms. However, for
$K\geq 3$, distance variance does not satisfy A3, suggesting that it is not a
valid measure of spread for general categorical variables. Figures 2 and 3
illustrate some counterintuitive results. Figure 2 demonstrates that for
equally probable distributions, $\pi_{k}=1/K$, distance variance peaks at
$K=2$ and progressively decreases to 0 with increasing $K$. Figure 3 presents
another example where a distribution with equal probabilities (case 2)
exhibits lower variability according to distance variance compared to a
distribution with unequal probabilities (case 1).

Figure 2: Distance variance of equal-probability distributions with
$K=1,~{},2~{},3,~{}4$. Figure 3: Distance variance of two distributions
($K=6$): Case 1 - $(1/2,~{}1/4,~{}1/8,~{}1/16,~{}1/32,~{}1/32)$; Case 2 -
equal probabilities.

Within the extended class $\Delta_{g}(X,~{}w,~{}l,~{}p)$, we find that when
$p=1$ (average $L_{1}$ distance), it is easier to construct new spread
measures that satisfy the three axioms. For $p\geq 2$, constructing valid
measures becomes mathematically more challenging. For $p=1$, the following new
metrics satisfy all three axioms. These metrics have simple expression and it
is likely that many more such metrics exist

  * •

$\sum_{k=1}^{K}\exp{(\pi_{k})}(1-\pi_{k})$, i.e., $l=1$,
$w(\pi_{k})=\exp{(\pi_{k})}$.

  * •

$\sum_{k=1}^{K}\sin(\pi_{k})(1-\pi_{k})$, i.e., $l=1$,
$w(\pi_{k})=\sin(\pi_{k})$.

##  4 Discussion and conclusions

Edelmann et al. (2020) established distance variance, a quantity derived from
distance correlation analysis, as a valuable spread measure for continuous and
binary data. This work explores its potential as a universal metric by
investigating its applicability to nominal variables with more than two
categories. Our findings reveal that, unfortunately, distance variance in its
current form is not a valid measure of spread for general categorical
variables. Misusing it can lead to counterintuitive results. Therefore, when
applied to categorical data, distance variance should not be interpreted as
spread, but rather as an average weighted distance to the geometric center, or
the $L_{2}$-norm (Frobenius norm) of the variance-covariance matrix based on
the one-hot encoded representation of the categorical variable.

This work focuses on distance variance based on binary distances. A natural
question arises: could alternative, non-binary distance metrics based on
category probabilities make distance variance a valid spread measure? van de
Velden et al. (2023) summarized several such metrics for categorical variables
that could be explored within the framework of distance variance. For
instance, Lin (1998) proposed a metric that gives more weight to matches on
frequent values and lower weight to mismatches on infrequent values:

$d(k,~{}k^{\prime})=\frac{\log(\pi_{k})+\log(\pi_{k^{\prime}})-2\log(\pi_{k}+\pi_{k^{\prime}})}{2\log(\pi_{k}+\pi_{k^{\prime}})}.$

Similarly, Boriah et al. (2008) introduced the inverse occurrence frequency
(IOF) distance, which increases with the co-occurrence frequency of
categories, akin to the inverse document frequency concept in information
retrieval. Replacing binary distances with such frequency-dependent metrics
might lead to a new form of distance variance that satisfies our proposed
axioms for spread. This remains an open question for future investigation.

## Acknowledgement

The work was supported by an NSF DBI Biology Integration Institute (BII) grant
(award no. 2119968; PI-Alrubaye).

## Competing Interests

The author has declared that no competing interests exist.

## Appendix

### Derivation of $\mathcal{V}(X)$ for arbitrary distances

Define $d(x_{1},~{}x_{2})=c_{1}$ if $x_{1}=x_{2}$ and
$d(x_{1},~{}x_{2})=c_{2}$ if $x_{1}\neq x_{2}$, we have

$\displaystyle E\left[d(X_{1},~{}X_{2})\right]$
$\displaystyle=c_{1}P(X_{1}=X_{2})+c_{2}P(X_{1}\neq X_{2})$
$\displaystyle=c_{1}\sum_{k=1}^{K}\pi^{2}_{k}+c_{2}\left(1-\sum_{k=1}^{K}\pi^{2}_{k}\right),$
$\displaystyle E\left[d^{2}(X_{1},~{}X_{2})\right]$
$\displaystyle=c^{2}_{1}P(X_{1}=X_{2})+c^{2}_{2}P(X_{1}\neq X_{2})$
$\displaystyle=c^{2}_{1}\sum_{k=1}^{K}\pi^{2}_{k}+c^{2}_{2}\left(1-\sum_{k=1}^{K}\pi^{2}_{k}\right),$

and

$\displaystyle E\left[d(X_{1},~{}X_{2})d(X_{1},~{}X_{3})\right]$
$\displaystyle=c^{2}_{1}P(X_{1}=X_{2}=X_{3})+c^{2}_{2}P(X_{1}\neq
X_{2},~{}X_{1}\neq X_{3})+2c_{1}c_{2}P(X_{1}=X_{2},~{}X_{1}\neq X_{3})$
$\displaystyle=c^{2}_{1}\sum_{k=1}^{K}\pi^{3}_{k}+c^{2}_{2}\sum_{k=1}^{K}\pi_{k}(1-\pi_{k})^{2}+c_{1}c_{2}\left[1-\sum_{k=1}^{K}\pi^{3}_{k}-\sum_{k=1}^{K}\pi_{k}(1-\pi_{k})^{2}\right].$

Summarizing the results above, the distance variance of $X$ can be expressed
as

$\mathcal{V}(X,~{}c_{1},~{}c_{2})=|c_{1}-c_{2}|\left[\left(\sum_{k=1}^{K}\pi_{k}^{2}\right)^{2}+\sum_{k=1}^{K}\pi_{k}^{2}-2\sum_{k=1}^{K}\pi_{k}^{3}\right]^{\frac{1}{2}}.$

## References

  * [1] Gilula, Z. & Haberman, S. (1995). Dispersion of categorical variables and penalty functions: Derivation, estimation, and comparability. Journal of the American Statistical Association, 90(432): 1447-1452
  * [2] Haberman, S. (1982). Analysis of dispersion of multinomial responses. Journal of the American Statistical Association, 77: 568-580
  * [3] Székely, G.J., Rizzo, M.L. & Bakirov, N.K. (2007). Measuring and testing dependence by correlation of distances. Annals of Statistics, 35(6): 2769-2794
  * [4] Shen, C. et al. (2022). The Chi-square test of distance correlation. Journal of Computational and Graphical Statistics, 31(1): 254-262
  * [5] Zhang, Q. (2019). Independence test for large sparse contingency tables based on distance correlation. Statistics and Probability Letters, 148(2019): 17-22
  * [6] Edelmann, D. et al. (2020). The distance standard deviation. Annals of Statistics, 48(6): 3395-3416
  * [7] Bickel, P. & Lehmann, E. (2012). Descriptive statistics for nonparametric models, IV. Spread. Selected Works in Probability and Statistics, Springer, New York
  * [8] Zhang, Q. (2024). On the properties of distance covariance for categorical data: Robustness, sure screening, and approximate null distributions. arXiv:2403.17882
  * [9] Arvesen, J. (1969). Jackknifing U-Statistics. Annals of Mathematical Statistics, 40(6): 2076-2100
  * [10] Tsallis, C. (1988). Possible generalization of Boltzmann-Gibbs statistics. Journal of Statistical physics, 52(1): 479-487
  * [11] Marshall, A. & Olkin, I. (1979). Inequalities: theory of majorization and its applications, Academic Press, San Deigo, CA
  * [12] Shannon, C. (1948). A mathematical theory of communication. The Bell System Technical Journal, 27(1948): 379-423
  * [13] Lad, F. et al. (2015). Extropy: Complementary dual of entropy. Statistical Science, 30(1): 40-58
  * [14] van de Velden, M. et al. (2023). A general framework for implementing distances for categorical variables. arXiv:2301.02190
  * [15] Lin, D. (1998) An information-theoretic definition of similarity. Proceedings of the Fifteenth International Conference on Machine Learning, San Francisco, CA, USA: Morgan Kaufmann Publishers, 296-304
  * [16] Boriah, S. et al. (2008). Similarity measures for categorical data: A comparative evaluation. Proceedings of the 2008 SIAM international conference on data mining, 243-254