# Fair Correlation Clustering

Saba Ahmadi The first two authors have contributed equally to this work.
Department of Computer Science,
University of Maryland,
<EMAIL_ADDRESS>Sainyam Galhotra††footnotemark:  Barna Saha  University of
California Berkeley, USA
<EMAIL_ADDRESS>Schwartz Roy  Technion - Israel Institute of Technology
<EMAIL_ADDRESS>
###### Abstract

In this paper we study the problem of correlation clustering under fairness
constraints. In the classic correlation clustering problem, we are given a
complete graph where each edge is labeled positive or negative. The goal is to
obtain a clustering of the vertices that minimizes disagreements –- the number
of of negative edges trapped inside a cluster plus positive edges between
different clusters. We consider two variations of fairness constraint for the
problem of correlation clustering where each node has a color, and the goal is
to form clusters that do not over-represent vertices of any color.

The first variant aims to generate clusters with minimum disagreements, where
the distribution of a feature (e.g. gender) in each cluster is same as the
global distribution. For the case of two colors when the desired ratio of the
number of colors in each cluster is $1:p$, we get
$\mathcal{O}(p^{2})$-approximation algorithm. Our algorithm could be extended
to the case of multiple colors. We prove this problem is NP-hard.

The second variant considers relative upper and lower bounds on the number of
nodes of any color in a cluster. The goal is to avoid violating upper and
lower bounds corresponding to each color in each cluster while minimizing the
total number of disagreements. Along with our theoretical results, we show the
effectiveness of our algorithm to generate fair clusters by empirical
evaluation on real world data sets.

##  1 Introduction

The ubiquitous use of Machine learning tools for everyday decision making has
brought the issue of fairness to the forefront. Many automated algorithms were
shown to have implicit biases against certain demographies. In order to build
machine learning algorithms that are inclusive, unbiased and helpful to the
entire population, the recent years have seen a surge of research related to
fairness. Many of the typical application scenarios where fairness has been
identified to be crucial (e.g. lending, marketing, job selection etc.)
requires clustering large datasets with sensitive features. These datasets
often come as a network. In order to incorporate fairness into clustering, the
seminal work by Chierichetti, Kumar, Lattanzi, and Vassilvitskii [14] proposed
that each cluster has proportional representation from different demographic
groups.They designed new approximation algorithms for the classic k-center and
k-median clustering objectives with this notion of fairness. Subsequently,
Schmidt, Schwiegelshohn, and Sohler [26] extended the framework to k-means
clustering. While these works study clustering algorithms over a metric space,
many clustering applications work over network data, and that calls for
designing graph clustering algorithms that are fair to all demographies. In a
very recent work, Kleindessner, Samadi, Awasthi and Morgenstern consider the
problem of fair spectral clustering [23]. They prove rigorous theoretical
bounds for their algorithms over the stochastic block model. However, the
analysis over arbitrary networks is still not known. In particular, the use of
triangle inequalities makes the analysis of metric based fair clustering
easier compared to graph clustering where the metricity is lacking.

In this paper, we consider a fair variant of the classic optimization problem
of correlation clustering. Correlation clustering is one of the most widely
used clustering paradigms, and as claimed by Bonchi et al. [8] “arguably the
most natural formulation of clustering”. Given a set of objects and a pairwise
similarity measure between them, the objective is to partition the objects so
that, to the best possible extent, similar objects are put in the same cluster
and dissimilar objects are put in different clusters. This is represented by
constructing a complete graph where edges are either labeled positive (similar
objects) or negative (dissimilar objects). The edges can also be weighted. An
algorithm for correlation clustering aims to minimize the disagreements among
vertices, calculated as the weight of negative edges trapped inside a cluster
plus positive edges between different clusters. As it just requires a
definition of similarity, it can be applied broadly to a wide range of
problems in different contexts such as social network analysis, data mining,
computational biology, business and marketing [27, 8, 20].

Similar to other clustering algorithms, the known algorithms for correlation
clustering may produce significantly biased output. In this work, we initiate
a study of a fair variant of the correlation clustering problem where each
vertex has a given feature, and the goal is to make sure that the distribution
of the features is the same as the global distribution in each cluster. This
is the same notion of fairness studied by Chierichetti et al. [14], Bercea et
al. [7] and Bera et al. [6] on k-center and k-median. In another variation,
the goal is to make sure the number of nodes of a specific feature $c_{i}$ in
a cluster of size $n$ is between $\frac{n}{q_{i}},\frac{n}{p_{i}}$ where
$p_{i}\leq q_{i}\in\mathcal{Z}^{\geq 1}$, and $p_{i},q_{i}$ are specified per
each feature $c_{i}$. This later model was originally proposed by Ahmadian,
Epasto, Kumar and Mahdian [2] with only the upper bound and later Bera et al.
[6] generalized it to consider lower bound (both $p_{i}$ and $q_{i}$). Having
a lower bound ensures that every color is represented in each cluster. They
studied the $k$-center problem under this framework. In all our algorithms, we
maintain the fairness constraints strictly, and optimize the objective
function. That is, we give exact approximation algorithms, as opposed to bi-
criteria approximation.

###  1.1 Contributions & Roadmap

Our contributions are as follows.

For the first fairness variant, we can assume that each node has a color and
the goal is to keep the distribution of the colors in each cluster same as the
global distribution. First we show our results for the case of $2$ colors, and
later we extend the results to an arbitrary number of colors. Our approach for
$2$ colors has some similarities to the approach proposed by Chierichitti et
al. [14] for the k-center and k-median problems. The analysis of fair clusters
with centroid based objectives leverages triangle inequality to bound the
total objective value of the returned clusters. However, calculating the total
disagreements for correlation clustering requires us to analyze the graph
properties, leading to a completely different analysis as compared to [14].

Assume nodes in the input graph are either red or blue and the goal is to have
a ratio of $1:p$ of the number of red nodes to the number of blue nodes, where
$p\in\mathcal{Z}^{\geq 1}$. In Section 5.1, we design a new algorithm with the
following guarantees:

######  Theorem 1.

Given a complete unweighted graph $G(V,E)$ where edges are labeled positive or
negative, and the nodes are either red or blue where the ratio of number of
red nodes to the number of blue nodes is $1:p$ for $p\in\mathcal{Z}^{\geq 1}$,
there exists an algorithm which gives a clustering with ratio $1:p$ of number
of red to blue nodes in each cluster and at most $\mathcal{O}(p^{2})\cdot OPT$
disagreements.

Before explaining the general result for handling a ratio of $1:p$, in Section
4, we explain a warm-up scenario where the desired ratio of red to blue in
each cluster is $1:1$. In this section, the following theorem is proved:

######  Theorem 2.

Given a complete unweighted graph $G(V,E)$ where edges are labeled positive or
negative, and the nodes are either red or blue, with an equal number of red
and blue nodes, there exists an algorithm which gives a clustering with equal
number of red and blue nodes in each cluster and at most $(3\alpha+4)\cdot
OPT$ disagreements, where $\alpha$ is the best approximation ratio for
correlation clustering on a complete unweighted graph with minimizing
disagreements objective.

Our results could be generalized to multiple colors and in Section 5.1, a
glimpse of the proof of the following theorem is provided. We delegate the
complete proof to the Appendix.

######  Theorem 3.

Given a complete unweighted graph $G(V,E)$ where edges are labeled positive or
negative, and each node has exactly one of the colors
$\\{c_{1},\cdots,c_{|\mathcal{C}|}\\}$, and the ratio of the number of nodes
of color $c_{1}$ to color $c_{i}$ is $1:p_{i}$ $(\forall
1<i\leq|\mathcal{C}|)$, where $p_{i}\in\mathcal{Z}^{\geq 1}$, there exists an
algorithm where the distribution of colors in each cluster is the same as the
global distribution, and the total number of disagreemnts is at most
$\mathcal{O}((\max_{i=1}^{|\mathcal{C}|}\\{p_{i}\\})^{2}\cdot|\mathcal{C}|^{2})\cdot
OPT$.

In Section 5.4, we prove NP-hardness of fair correlation clustering problem on
complete unweighted graphs even for $2$ colors. Note that the hardness result
does not directly follow from the hardness result of the original correlation
clustering.

In Section 5.3, we consider the fairness model studied by Ahmadian et al. [2]
for $k$-center problem without over-representation. We are inspired by their
definition of over-representation, and show the following theorem holds:

######  Theorem 4.

Given a complete unweighted graph $G(V,E)$ where edges are labeled positive or
negative, and nodes are colored red or blue, and two ratios $1:p,1:q$ where
$p,q\in\mathcal{Z}^{\geq 1},p\leq q$, where ratio of the total number of red
nodes to the total number of blue nodes is between $1:q$ and $1:p$, there
exists an algorithm which gives a clustering where the ratio of number of red
nodes to blue nodes in each cluster is between $1:q$ and $1:p$, and the total
number of disagreements is at most $\mathcal{O}(q^{2})\cdot OPT$.

We can extend Theorem 4 to the case with multiple colors.

######  Theorem 5.

Given a complete unweighted graph $G(V,E)$ where edges are labeled positive or
negative, and each node has exactly one of the colors
$\\{c_{1},\cdots,c_{\mathcal{C}}\\}$, and two ratios $1:p_{i},1:q_{i}$ for
each color $c_{i}$ where $p_{i},q_{i}\in\mathcal{Z}^{\geq 1},p_{i}\leq q_{i}$,
where ratio of the total number of nodes of color $c_{1}$ to the total number
of nodes of color $c_{i}$ needs to be between $1:q_{i}$ and $1:p_{i}$, there
exists an algorithm which gives a clustering where $\forall
1<i\leq|\mathcal{C}|$, the ratio of number of nodes of color $c_{1}$ to color
$c_{i}$ in each cluster is between $1:q_{i}$ and $1:p_{i}$, and the total
number of disagreements is at most
$\mathcal{O}((\max_{i=1}^{|\mathcal{C}|}\\{q_{i}\\})^{2})\cdot OPT$.

In Section 6, we perform an extensive evaluation on real world datasets to
demonstrate the unfair results generated by the classical correlation
clustering algorithm and evaluate the ability of our algorithm to generate
fair clusters without much loss of solution quality.

##  2 Related Work

Introduced by Bansal, Blum and Chawla in 2004 [4], correlation clustering has
received tremendous attention in the past decade. The problem is NP-complete,
and a series of follow-up work have resulted in better approximation ratio,
generalization to weighted graphs etc. [3, 11, 13]. This problem captures a
wide range of applications including clustering gene expression patterns [5,
19], and the aggregation of inconsistent information [18].

The research in fairness in machine learning has focused on two main
directions, coming up with proper notions of fairness and designing fair
algorithms. The first direction includes results on statistical parity [22],
disparate impact [17], and individual fairness [16]. Second direction includes
a bulk of work including fair rankings [10], fair clusterings [14, 25, 7, 6,
2], fair voting [9], and fair optimization with matroid constraints [15].

Puleo and Milencovic [24] studied a new version of correlation clustering,
where the objective was to make sure the maximum number of disagreements on
each vertex is minimized. Their motivation was to make sure individuals are
treated fairly. The result was improved by Charikar et al. [12]. In a
subsequent work, Ahmadi et al. [1] studied the local correlation clustering
problem where the objective was to make sure the maximum number of
disagreements on each cluster is minimized, and the communities are treated
fairly. Their result was improved by Kalhan et al. [21].

Chierichetti et al. [14] extended the notion of disparate impact to k-center
and k-median, and studied these problems for the case of two groups. Their
result was later generalized to multiple groups by Rösner and Schmidt [25]. In
this work, we generalize the notion of disparate impact to correlation
clustering for multiple colors, and our goal is to make sure the distribution
of colors in each cluster is identical to the global distribution. Next, we
extend the model introduced by Ahmadian et al. [2] on $k$-center to
correlation clustering to show no color is over or under represented in each
cluster.

##  3 Preliminaries

In the correlation clustering problem, an input graph $G(V,E)$ is given where
each edge is labeled positive or negative. The goal is to obtain a clustering
that minimizes the total number of disagreements, defined as the number of
negative edges trapped inside a cluster plus positive edges that are cut
between clusters.

Inspired by the recent developments on fairness in machine learning, we define
a fair variant of correlation clustering problem. In fair correlation
clustering problem, given an input graph $G(V,E)$ each node has a color from
set of colors $\\{c_{1},\cdots,c_{|\mathcal{C}|}\\}$. The desired ratio of the
number of nodes from color $c_{1}$ to color $c_{i}$ is $1:p_{i},\forall 1\leq
i\leq|\mathcal{C}|$ where $\forall 1\leq
i\leq|\mathcal{C}|:p_{i}\in\mathcal{Z}^{\geq 1}$. The goal is to find a
clustering which gaurantees the desired ratios in each cluster while
minimizing the total number of disagreements. First, we study fair correlation
clustering problem for $2$ colors and then extend it to an arbitrary number of
colors.

In Section 5.3, we consider the problem of given an instance of correlation
clustering where nodes are either red or blue and the ratio of the number of
red nodes to blue nodes is between $1:q,1:p$, where $p,q\in\mathcal{Z}^{\geq
1},p\leq q$. The goal is to form a clustering where the ratio of the number of
red nodes to blue nodes in each cluster is between $1:q$ and $1:p$. Throughout
the paper, we use $OPT$ interchangeably for the optimum solution and minimum
number of disagreements.

##  4 Warmup: 2 Colors with Ratio 1:1

Algorithm 1 Fair Correlation Clustering

1: Input: $G(V=V_{B}\cup V_{R},E=E^{+}\cup E^{-})$

2: $E^{\prime}\leftarrow\phi$

3: for $u\in V_{B}$ do

4: for $v\in V_{R}$ do

5: $E^{\prime}\leftarrow E^{\prime}\cup(u,v)$

6: $w(u,v)\leftarrow\sum\limits_{w\in
V\setminus\\{u,v\\}}\mathbbm{1}_{(u,w)\in E^{+},(v,w)\in
E^{-}}+\mathbbm{1}_{(u,w)\in E^{-},(v,w)\in E^{+}}$

7: end for

8: end for

9: $\mathcal{C}^{\prime}\leftarrow ClassicCorrClust(V_{R},E\cap V_{R}\times
V_{R})$

10: $M\leftarrow\texttt{min-weight-matching}(V,E^{\prime},w)$

11: $\forall v\in V_{B}$, assign $v$ to same cluster as $M(v)$

12: return $\mathcal{C}^{\prime}$

The goal is to find a clustering which minimizes the total number of
disagreements, and the number of red and blue vertices in each cluster are
equal. We show a constant approximation algorithm for this problem.

Algorithm 1 presents our approach to generate clusters that obey the fairness
constraint while minimizing the total disagreements. First, a weighted
bipartite graph from $V_{B}$ to $V_{R}$ is constructed (lines 2-8) in the
following way: consider a pair of vertices $(x,y)$ where $x\in V_{B}$ and
$y\in V_{R}$, weight of this edge $w(x,y)$ is initially set to zero. If
$(x,y)$ is a negative edge, increase $w(x,y)$ by $1$. For each vertex $z\in
V\setminus\\{x,y\\}$, if the labels of edges $(z,x)$ and $(z,y)$ are
different, increase $w(x,y)$ by $1$ (line 6). In this way, $w(x,y)$ shows how
much the total disagreement increases if $x$ and $y$ are clustered together.
Run an $\alpha$-approximation algorithm for minimizing disagreements on
$V_{R}$ with no fairness constraints (line 9). Since $V_{R}\subset G$ and
there are no fairness constraints on $V_{R}$, $OPT_{V_{R}}\leq OPT_{G}$. Next,
find a minimum weighted matching $M$ from $V_{B}$ to $V_{R}$ (line 10). In the
end assign each blue vertex to the same cluster as its matched red node (line
11), and return the new clustering. Let $w(M)$ denote weight of this matching.
First, we show the following lemma holds:

######  Lemma 1.

$w(M)\leq 2\cdot OPT_{G}$.

###### Proof.

Consider the optimal solution, and construct an arbitrary matching where both
endpoints of each matched edge are in the same cluster. Call this matching
$M^{\prime}$ and assign weights to each matched edge as described in Algorithm
1. First, we show $w(M^{\prime})\leq 2\cdot OPT_{G}$. Consider an edge
$(v_{i},v_{j})$, if they are matched by the $M^{\prime}$, $M^{\prime}$ and
$OPT$ are paying the same cost for this edge, since the matching is paying for
this edge if and only if it is a negative edge trapped inside a cluster, in
this case $OPT$ is also paying for it. Assume the case where $v_{i},v_{j}$ are
not matched in $M^{\prime}$. Let’s assume $v_{i}$ is matched to
$v_{i^{\prime}}$, and $v_{j}$ is matched to $v_{j^{\prime}}$. The matching
$M^{\prime}$ could pay for the edge $(v_{i},v_{j})$ at most twice, once if the
edges $(v_{i},v_{j})$ and $(v_{i^{\prime}},v_{j})$ have disagreeing labels,
and once if $(v_{i},v_{j})$ and $(v_{i},v_{j^{\prime}})$ have disagreeing
labels. Therefore, $w(M^{\prime})\leq 2\cdot OPT$. Therefore $w(M)\leq
w(M^{\prime})\leq 2\cdot OPT$ since we are finding a min cost matching $M$. ∎

Now consider the $\alpha$-approximation for $V_{R}$, and put each blue vertex
in the same cluster as their matched red vertex (line 11). In the following we
show this algorithm gives a $3\alpha+4$-approximation.

###  4.1 Analysis:

Consider vertices $x,x^{\prime}\in V_{R}$ and $y,y^{\prime}\in V_{B}$, where
$(x,y)\in M$ and $(x^{\prime},y^{\prime})\in M$ (Figure 1(a)). In the
following, we show that we can pay for all the disagreements within our
$(3\alpha+4)\cdot OPT$ budget.

(a) Warm-up example

(b) General case

Figure 1: Example set of matched nodes for our algorithm.

Case 1: If a disagreement happens on a matched edge $(x,y)$, meaning $(x,y)$
is a negative edge, it is counted in $w(M)$.

Case 2: If a disagreement is on $(x^{\prime},y)$, two cases may arise:

  * •

Case 2.1: If $(x^{\prime},y)$ and $(y^{\prime},y)$ have the same label, since
$x^{\prime}$ and $y^{\prime}$ are in the same cluster, having a disagreement
on $(x^{\prime},y)$ implies having a disagreemt on $(y^{\prime},y)$.
Therefore, if we double the budget needed to pay for the mistakes in $V_{R}$,
we can also pay for the mistakes of this type.

  * •

Case 2.2: If $(x^{\prime},y)$ and $(y^{\prime},y)$ do not have the same label,
we are making exactly one mistake on these two edges and the min cost matching
$M$ is paying for it.

Case 3: If a disagreement occurs on $(x,x^{\prime})$, the following cases
might happen:

  * •

Case 3.1: If $(x,x^{\prime})$, $(x^{\prime},y)$ have different labels, we are
making exactly one mistake on these two edges and the min cost matching $M$ is
paying for it.

  * •

Case 3.2: If $(x^{\prime},x)$ and $(x^{\prime},y)$ have the same labels, two
cases might happen:

    * –

Case 3.2.1: $(x^{\prime},y)$ and $(y,y^{\prime})$ have the same labels. In
this case, $(x^{\prime},x)$ and $(y^{\prime},y)$ have the same labels, and
$x^{\prime}$, $y^{\prime}$ are in the same cluster, also $x,y$ are in the same
cluster. Therefore, there is a disagreement on $(x^{\prime},x)$ if and only if
there is a disagreement on $(y,y^{\prime})$. By adding another $\alpha\cdot
OPT$ to the budget, we can pay for these types of disagreements.

    * –

Case 3.2.2: $(x^{\prime},y)$ and $(y^{\prime},y)$ have different labels. In
this case, exactly one mistake occured on $(x^{\prime},y)$ and
$(y,y^{\prime})$ and matching was paying for it. If no mistakes occures on
$(x^{\prime},y)$, there will be no mistake on $(x,x^{\prime})$ as well. If a
disagreement happens on $(x^{\prime},y)$, then a disagreement occurs on
$(x^{\prime},x)$. Since $M$ is paying for the disagreement occured on
$(x^{\prime},y)$, doubling the cost of $M$ in the budget pays for the mistake
on $(x,x^{\prime})$ as well.

At the end, we get a $3\alpha+4$-approximation algorithm, which complete proof
of Theorem 2.

##  5 Generalization

In this section, we generalize the previously considered model to allow the
ratio of colors to be $1:p$ where $p\in\mathcal{Z}^{\geq 1}$ in Section 5.1
and allow more than 2 colors in Section 5.2.

###  5.1 2 Colors with Ratio 1:p

The algorithm for this case is similar to Algorithm 1 with a minor difference;
the matching $M$ constructed from $V_{R}$ to $V_{B}$ is a $b$-matching where
the degrees of vertices in $V_{R}$ are $p$, and the degrees of vertices in
$V_{B}$ are $1$. Let $w(M)$ denote weight of this matching.

######  Lemma 2.

$w(M)\leq 2p\cdot OPT$.

###### Proof.

Consider the $OPT$ solution, and construct an arbitrary $b$-matching
$M^{\prime}$ from red nodes to blue nodes where degree of each red node is
$p$, and degree of each blue node is $1$, and for each matched edge both its
endpoints belong to the same cluster. Call this matching $M^{\prime}$. First,
we show $w(M^{\prime})\leq 2p\cdot OPT_{G}$. Consider an edge between
arbitrary vertices $v_{i}$ and $v_{j}$, such that they are not matched in
$M^{\prime}$. If a disagreement occurs on the edge between $(v_{i},v_{j})$ in
$OPT_{G}$, this disagreement could have been counted at most $2p$ times in
$w(M^{\prime})$. Therefore $w(M^{\prime})\leq 2p\cdot OPT_{G}$. Since $M$ is a
min cost $b$-matching satisfying degree constraints: $w(M)\leq
w(M^{\prime})\leq 2p\cdot OPT_{G}$ ∎

The algorithm is as following: run an $\alpha$-approximation correlation
clustering on a subset of $G$ which includes the red vertex from each hyper-
node (i.e. a collection of matched nodes). In the following, we show we can
pay for all the disagreements within a
$\Big{(}(p^{2}+2p)\cdot\alpha+4p^{2}\Big{)}\cdot OPT$ budget.

Case 1: In Figure 1(b), consider a disagreement between a red vertex ($r_{1}$)
and a blue ($b_{3}$) node from different hyper-nodes. Two cases might happen:

  * •

Case 1.1: If edges $(r_{1},b_{3})$ and $(r_{1},r_{2})$ have disagreeing
labels, then cost of the edge $(r_{2},b_{3})$ counted in the matching is
paying for it.

  * •

Case 1.2: If edges $(r_{1},b_{3})$ and $(r_{1},r_{2})$ have the same signs,
the disagreement on $(r_{1},b_{3})$ could be charged to the edge
$(r_{1},r_{2})$. The number of such edges charged to $(r_{1},r_{2})$ is at
most $2p$.

Case 2: There exists disagreement between two blue nodes from different hyper-
nodes, like $(b_{1},b_{3})$ in Figure 1(b).

  * •

Case 2.1: Edges $(b_{1},b_{3})$ and $(r_{1},b_{3})$ are disagreeing. Then the
cost of edge $(r_{1},b_{1})$ included in the cost of the matching is paying
for it.

  * •

Case 2.2: Edges $(b_{1},b_{3})$ and $(r_{1},b_{3})$ have the same labels and
have different labels with $(r_{1},r_{2})$. We charge the disagreement on
$(b_{1},b_{3})$ to the edge $(r_{2},b_{3})$. There are $p$ choices for
$b_{1}$, therefore at most $p$ edges of this type, plus the edge
$(r_{1},b_{3})$ are charged to the edge $(r_{2},b_{3})$, whereas $M$ is paying
$1$ for the disagreement between $(r_{1},r_{2})$ and $(r_{1},b_{3})$.
Therefore, we need to account for $p+1$ times the matching cost to account for
all edges of this type.

  * •

Case 2.3: Edges $(b_{1},b_{3}),(r_{1},b_{3}),(r_{1},r_{2})$ all have the same
labels. There are $p^{2}$ choices for a pair of blue nodes like
$(b_{1},b_{3})$, and disagreements on these edges could be charged to
$(r_{1},r_{2})$.

Algorithm 2 Fair Correlation Clustering for Multiple Colors

1: Input: $G(V=V_{c_{1}}\cup V_{c_{2}}\cdots\cup
V_{c_{\mathcal{C}}},E=E^{+}\cup E^{-})$

2: for $1<i\leq|\mathcal{C}|$ do

3: $E^{\prime}_{i}\leftarrow\phi$

4: for $u\in V_{c_{i}}$ do

5: for $v\in V_{c_{1}}$ do

6: $E^{\prime}_{i}\leftarrow E^{\prime}_{i}\cup(u,v)$

7: $w(u,v)\leftarrow\sum\limits_{w\in
V_{i}\setminus\\{u,v\\}}\mathbbm{1}_{(u,w)\in E^{+},(v,w)\in
E^{-}}+\mathbbm{1}_{(u,w)\in E^{-},(v,w)\in E^{+}}$

8: end for

9: end for

10: $M_{i}\leftarrow\texttt{min-weight-b-matching}(V_{1}\cup
V_{c_{i}},E^{\prime}_{i},w)$

11: end for

12: $\mathcal{C}^{\prime}\leftarrow ClassicCorrClust(V_{c_{1}},E\cap
V_{c_{1}}\times V_{c_{1}})$

13: for $1<i\leq|\mathcal{C}|$ do

14: $\forall v\in V_{c_{i}}$, assign $v$ to same cluster as $M_{i}(v)$

15: end for

16: return $\mathcal{C}^{\prime}$

Case 3: A disagreement between two blue nodes in the same hyper-node, $b_{1}$
and $b_{2}$ which means $(b_{1},b_{2})$ is a negative edge. If $(r_{1},b_{1})$
is positive then $(r_{1},b_{2})$’s contribution in the matching cost captures
it. Similarly, if $(r_{1},b_{2})$ is a positive edge then the
$(r_{1},b_{2})$’s contribution in matching cost captures this. If both
$(r_{1},b_{1})$ and $(r_{1},b_{2})$ are negative edges then we can charge both
the edges $1/2$. The total number of times an edge $(r_{1},b_{1})$ is charged
is at most $p-1$ as there can be a maximum of $p-1$ negative edges from
$b_{1}$.

There are a total of $p^{2}+2p$ charges on edges between red nodes (Cases 1.2
and 2.3) accounting for the total cost to be $(p^{2}+2p)C$, where $C$ is the
correlation clustering objective on red vertices. Similarly, we charge each
matched edge at most $p+1$ times their weight in Case 2.2 and at most $p-1$
times their weight in Case 3, the total contribution to the final objective is
$2p\cdot w(M)$. All charges required to handle cases 1.1 and 2.1 do not add
any additional cost to the objective as they are already accounted for edges
considered in $2p\cdot w(M)$. Hence, the total objective value of returned
clusters is at most:

$(p^{2}+2p)C+(p+1)\cdot w(M)\leq\Big{(}(p^{2}+2p)\cdot\alpha+2p\times
2p\Big{)}\cdot OPT$

Therefore the approximation ratio is $\mathcal{O}(p^{2})$, and this completes
proof of Theorem 1.

###  5.2 Multiple Colors

Our results could be extended to the case of multiple colors. Assume there are
$\mathcal{C}$ colors $\\{c_{1},c_{2},\cdots,c_{|\mathcal{C}|}\\}$, and the
ratio of number of nodes of color $c_{1}$ to color $c_{i}$ is $1:p_{i}$
($\forall 1<i\leq|\mathcal{C}|$), where $p_{i}\in\mathcal{Z}^{\geq 1}$. In
this case, we get an approximation ratio of
$\mathcal{O}((\max_{i=1}^{|\mathcal{C}|}\\{p_{i}\\})^{2}\cdot|\mathcal{C}|^{2})$.
Algorithmm 2 is a generalization of Algorithm 1. In this algorithm a set of
$b$-matchings $\\{M_{i}:1<i\leq|\mathcal{C}|\\}$ are constructed. Each
matching $M_{i}$ is between nodes of color $c_{1}$ and $c_{i}$ and degree of
each node of color $c_{1}$ is $p_{i}$, and degree of each node of color
$c_{i}$ is $1$. Analysis of this algorithm is similar to the analysis of the
algorithm for $2$ colors, and we delegate the complete proof to Appendix.

###  5.3 Avoiding Over-representation

In this section, we consider the model defined by Ahmadian et al. [2] for
$k$-center problem. Their goal is to make sure given a parameter
$0\leq\alpha\leq 1$, maximum fraction of nodes in a cluster having a specific
color is at most $\alpha$ times the size of the cluster. We consider the
following problem: consider two colors red and blue. Our goal is to make sure
the ratio of the number of red nodes to the number of blue nodes in each
cluster is between $1:q$ and $1:p$ where $1\leq p\leq q$ and
$p,q\in\mathcal{Z}^{\geq 1}$. The algorithm discussed in Section 5.1 could be
modified to handle this variation of the problem in the following way: when
finding a minimum cost $b$-matching $M$, put the degree constraint on each red
node to be between $p$ and $q$, and let the degree constraint on each blue
node to be $1$. Therefore in the minimum cost matching $M$, each connected
component has $1$ red node and at least $p$ and at most $q$ blue nodes. The
rest of the algorithm is similar to the algorithm discussed in Section 5.1.
Using a similar analysis, it could be seen the approximation ratio is
$\mathcal{O}(q^{2})$. We show a sketch of the proof and discard full proof to
the supplementary material.

###### Proofsketch.

Given the optimum solution $OPT$, we show a $b$-matching $M^{\prime}$ could be
constructed where endpoints of each matched edge belong to the same cluster,
and the degree of each red node is at least $p$ and at most $q$. In the $OPT$
solution, in each cluster, the ratio of the number of red to blue nodes is
between $1:q$ and $1:p$. Consider a specific cluster $\mathcal{X}$ in the
$OPT$ solution, let $n_{r},n_{b}$ denote the number of red and blue nodes in
this cluster respectively. Therefore, $n_{r}\cdot p\leq n_{b}\leq n_{r}\cdot
q$. Construct a $b$-matching from red nodes to blue nodes in $\mathcal{X}$ as
following: assign $p$ distinct blue nodes to each red node. If any blue nodes
are left un-assigned, assign them to any red node with matched degree less
than $q$. Since $n_{b}\leq q\cdot n_{r}$, a $b$-matching satisfying degree
constraints in each cluster of $OPT$ could be constructed. $M^{\prime}$ is the
union of the $b$-matchings formed in all the clusters. Similar to the proof of
Lemma 2, we can show $w(M)\leq w(M^{\prime})\leq 2q\cdot OPT$. The rest of the
proof is along the same lines as proof of Theorem 1, and the algorithm outputs
a clustering with at most $\mathcal{O}(q^{2})\cdot OPT$ disagreements. ∎

In the case of multiple colors, where the goal is that in each cluster the
ratio of the number of nodes of color $c_{1}$ to color $c_{i}$ be between
$1:p_{i}$ and $1:q_{i}$ where $\forall 1<i\leq|\mathcal{C}|,p_{i}\leq q_{i}$
and $p_{i},q_{i}\in\mathcal{Z}^{\geq 1}$, Algorithm 2 could be modified to
handle this case: in each iteration, find a minimum cost weighted $b$-matching
$M_{i}$ where the degree of each node of color $c_{1}$ is between $p_{i}$ and
$q_{i}$, and the degree of each node of color $c_{i}$ is $1$. In the
supplemetary material we show this algorithm obtains an approximation ratio of
$\mathcal{O}((\max_{i=1}^{|\mathcal{C}|}\\{q_{i}\\})^{2}\cdot|\mathcal{C}|^{2})$
on the number of disagreements.

###  5.4 Hardness

Consider a complete graph $G(V,E=E^{+}\cup E^{-})$. Consider a new complete
graph $H$ of $2|V|$ nodes which is contructed by duplicating the nodes of $G$
(say V and $V^{\prime}=\\{u^{\prime}\mid u\in V\\}$). We can assume the nodes
of $V$ to be colored blue and $V^{\prime}$ can be considered as the mirror
image of $V$ colored red. Each pair of nodes $u,v\in V$ are connected in the
same way as $E$. A positive edge is added between $u$ and $u^{\prime}$ for all
$u\in V$, where $u^{\prime}$ is the mirror image of $u$. For all $u\in
V,v^{\prime}\in V^{\prime}$, the edge between $(u,v^{\prime})$ has the same
label as $(u,v)$ where $v$ is the mirror of $v^{\prime}$. The graph $H$
restricted to vertices $V^{\prime}$ is referred to as
$G^{\prime}(V^{\prime},E^{\prime})$ (as shown in Figure 2).

Figure 2: Hardness example.

Consider a clustering of $H$ with equal number of red and blue vertices in
each cluster (say $\mathcal{C}^{\prime}$). Now, we calculate the disagreements
on the edges between nodes of $V$ and $V^{\prime}$ to bound the total
disagreements of $\mathcal{C}^{\prime}$. A disagreement edge
$(u^{\prime},v^{\prime})\in E^{\prime}$ will lead to the following scenarios.

  * •

Case 1: If $(u^{\prime},v^{\prime})\in E^{-}$: Therefore nodes $u^{\prime}$
and $v^{\prime}$ belong to same cluster.

    * –

Case 1.1: If $u,v$ belong to the same cluster as $u^{\prime}$ and
$v^{\prime}$, then edges $(u,v^{\prime})$ and $(u^{\prime},v)$ are mistakes.

    * –

Case 1.2: $u$ belongs to same cluster as $u^{\prime}$ and $v^{\prime}$ but $v$
belongs to a different cluster. Edges $(v,v^{\prime})$ and $(u,v^{\prime})$
are the mistakes.

    * –

Case 1.3: $u$ and $v$ belong to different cluster from $u^{\prime}$ and
$v^{\prime}$, edges $(u,u^{\prime})$ and $(v,v^{\prime})$ are mistakes

  * •

Case 2: If $(u^{\prime},v^{\prime})$ is a positive edge. This means
$u^{\prime}$ and $v^{\prime}$ belong to different clusters.

    * –

Case 2.1: If $u$ belongs to same cluster as $u^{\prime}$ and v belongs to same
cluster as $v^{\prime}$ then edges $(u,v^{\prime})$ and $(u^{\prime},v)$ are
the mistakes.

    * –

Case 2.2: If $u$ belongs to different cluster from $u^{\prime}$ and $v$
belongs to different cluster from $v^{\prime}$ then $(u,u^{\prime})$ and
$(v,v^{\prime})$ are the mistakes.

    * –

Case 2.3: If $u$ belongs to different cluster from $u^{\prime}$ and
$v,v^{\prime}$ belong to the same cluster:

      * *

Case 2.3.1: If $u$ and $v^{\prime}$ belong to different clusters then
$(u,v^{\prime})$ and $(u,u^{\prime})$ are mistakes.

      * *

Case 2.3.2: If $u$ and $v^{\prime}$ belong to the same cluster then
$(u,u^{\prime})$ and $(u^{\prime},v)$ are mistakes.

This shows that for every disagreement $(u^{\prime},v^{\prime})\in
E^{\prime}$, there exist at least 2 disagreements in the edges between
$\\{u^{\prime},v^{\prime}\\}$ and $\\{u,v\\}$:
$(u,v^{\prime}),(u^{\prime},v),(u,u^{\prime})$ and $(v,v^{\prime})$. If the
disagreements on the subgraph of $H$ limited to $(V^{\prime},E^{\prime})$ is
$O_{G^{\prime}}$, then the total disagreements on the edges between $V$ and
$V^{\prime}$ is at least $2O_{G^{\prime}}$. Hence, the total disagreements of
$\mathcal{C}^{\prime}$ is atleast $3O_{G^{\prime}}+O_{G}$, where $O_{G}$ is
the disagreements on subgraph limited to $G(V,E)$. Symmetrically performing
the above mentioned analysis on $(u,v)\in E$, the total disagreements of
$\mathcal{C}^{\prime}$ is atleast $3O_{G}+O_{G^{\prime}}$. Hence the total
disagreements of $\mathcal{C}^{\prime}$ is at least
$\max\\{3O_{G^{\prime}}+O_{G},3O_{G}+O_{G^{\prime}}\\}$, which is minimized
when $O_{G}=O_{G^{\prime}}=OPT_{G}$. This is minimized when each red node and
its mirror image belong to the same cluster. By discarding the nodes of
$V^{\prime}$ from the optimal solution of $H$, we get the optimal solution of
classical correlation clustering on $G$.

##  6 Experiments

In this section, we empirically evaluate our algorithm along with some
baselines on real world datasets. We show that the clusters generated by
classical correlation clustering algorithm are unfair and our algorithm
returns fair clusters without much loss in the quality of the clusters.

Datasets. We consider the following datasets.

Bank111https://archive.ics.uci.edu/ml/datasets/Bank+Marketing. This dataset
comprises of phone call records of a marketing campaign run by a Portuguese
bank. The _marital_ status of the clients is considered feature to ensure
fairness.

Adult222https://archive.ics.uci.edu/ml/datasets/adult. Each record in the
dataset represents a US citizen whose information was collected during 1994
census. We consider the feature _sex_ for fairness.

Medical Expenditure333https://meps.ahrq.gov/mepsweb/. The dataset contains
medical information of various patients collected for research purposes. The
_race_ attribute is considered for fairness.

Compas444https://github.com/propublica/compas-analysis. The dataset comprises
of records of criminal trials used to analyze criminal recidivism. We consider
race attribute for fairness.

Each record in the above mentioned datasets are considered as the nodes of the
graph and the edge sign is determined by attribute simialrity between the
nodes. We consider a sample of 1000 nodes in the above datasets for our
experiments.

Figure 3: Comparison of total disagreements for the different baselines with a
constraint of ratio of two colors to be between 1:1 and 1:2. Figure 4:
Distribution of nodes of different colors in top 5 clusters generated by the
algorithms.

Baselines. We compare the quality of clusters returned by our algorithm with
the following baselines focussed towards minimizing disagreements and ensure
fairness. (i) CC – The classical correlation clustering algorithm [3] that
guarantees a 3-approximation of the optimal solution but does not ensure
fairness (iii) wMatch – It generates a matching between nodes of different
color as discussed in Algorithm 1 (iv) uFairCC – Same as our algorithm with a
difference that the matching component considers unit weight on inter-color
edge. (v) CCMerge – This algorithm runs classical correlation clustering
algorithm to generate initial clusters and then greedily add nodes to the
clusters in decreasing size, so as to ensure fairness constraints.

All the algorithms were implemented by us in Python using the networkx library
on a 64GB RAM server. We run each algorithm 5 times and report average
results. We calculate the total disagreements of the returned clusters to
evaluate their quality. We denote our algorithm by FairCC.

###  6.1 Solution Quality

This section compares the quality of clusters returned by the different
algorithms for the specified distribution of features in each cluster.

Fair proportion Figure 3 compares the total disagreements of the clusters
returned by different algorithms. We observe similar trends across all the
datasets. The clusters returned by CC do not obey the fairness constraint but
all the other techniques ensure fairness. Across all datasets, FairCC achieves
the minimum value of total disagreements as compared to the baselines that
ensure fairness. Additionally, the loss in quality of clusters to achieve
fairness as compared to CC is quite low. The matching returned by wMatch is
same as that of FairCC but it achieves poor quality due to a number of
positive edges going across the different components. The CCMerge algorithm
ends up merging nodes which are connected by negative edges to ensure
fairness, thereby losing on quality. uFairCC is same as our proposed solution
except that the matching component between nodes of different colors does not
consider weights. Superior performance of FairCC as compared to uFairCC
justifies the benefit of our construction of a weighted bipartite graph to
match nodes of different colors.

Figure 4 shows distribution of top-5 clusters generated by CC and FairCC on
Adult and Compas. The skew in distribution of the nodes of two colors in the
clusters demonstrates the extent of unfairness in the results generated by
classical correlation clustering algorithm. On the other hand, FairCC achieves
the required fairness constraint in all clusters without losing much in
quality. On increasing the range of plausible fraction of two colors, the
total disagreements of FairCC go down but the trends remain similar.

Multiple colors Figure 5 compares the performance of FairCC with other
baselines. Similar to the case of 2 colors, the quality of FairCC is not much
worse than that of CC and is better than any other baseline. This comparison
does not plot CCMerge as it does not generate clusters that obey fairness.

Figure 5: Comparison of clusters returned by our algorithm and baselines for
instances with more than two colors for Adult dataset. We omit CCMerge as it
does not generate fair clusters.

Running Time FairCC runs in two stages. The first stage identifies a weighted
matching between the nodes of different color followed by correlation
clustering on one of the color. On all the datasets, our algorithm ran in less
than 10 minutes. For a graph of $n$ nodes, with the increase in number of
colors the size of subgraph constructed for matching reduces and total running
time does not increase.

##  7 Conclusions

In this paper we studied the problem of fairness in clustering. We considered
correlation clustering on complete graphs with color constraints to ensure
balance and fairness in applications. We obtained combinatorial approximation
algorithms for two models. In the first model the goal is to keep distribution
of colors in each cluster the same as global distribution while approximately
optimizing correlation clustering objective, e.g. minimizing disagreements. In
the second model, the goal was to make sure no colors are over-represented or
under-represented in each formed cluster while approximately minimizing total
number of disagreements. In our experiments we showed our algorithms are
effective on real world datasets. Future work could explore extension of our
model to general graphs. Obtaining approximation algorithms which achieve
better bounds are also of immediate interest.

## References

  * Ahmadi et al. [2019] Ahmadi, S., Khuller, S., and Saha, B.  Min-max correlation clustering via multicut.  In _International Conference on Integer Programming and Combinatorial Optimization_ , pp. 13–26. Springer, 2019.
  * Ahmadian et al. [2019] Ahmadian, S., Epasto, A., Kumar, R., and Mahdian, M.  Clustering without over-representation.  In _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, pp. 267–275, 2019.
  * Ailon et al. [2008] Ailon, N., Charikar, M., and Newman, A.  Aggregating inconsistent information: ranking and clustering.  _Journal of the ACM (JACM)_ , 55(5):1–27, 2008\.
  * Bansal et al. [2004] Bansal, N., Blum, A., and Chawla, S.  Correlation clustering.  _Machine learning_ , 56(1-3):89–113, 2004.
  * Ben-Dor et al. [1999] Ben-Dor, A., Shamir, R., and Yakhini, Z.  Clustering gene expression patterns.  _Journal of computational biology_ , 6(3-4):281–297, 1999.
  * Bera et al. [2019] Bera, S., Chakrabarty, D., Flores, N., and Negahbani, M.  Fair algorithms for clustering.  In _Advances in Neural Information Processing Systems_ , pp. 4955–4966, 2019.
  * Bercea et al. [2018] Bercea, I. O., Groß, M., Khuller, S., Kumar, A., Rösner, C., Schmidt, D. R., and Schmidt, M.  On the cost of essentially fair clusterings.  _arXiv preprint arXiv:1811.10319_ , 2018.
  * Bonchi et al. [2014] Bonchi, F., Garcia-Soriano, D., and Liberty, E.  Correlation clustering: from theory to practice.  In _Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining_ , pp. 1972–1972, 2014.
  * Celis et al. [2017a] Celis, L. E., Huang, L., and Vishnoi, N. K.  Multiwinner voting with fairness constraints.  _arXiv preprint arXiv:1710.10057_ , 2017a.
  * Celis et al. [2017b] Celis, L. E., Straszak, D., and Vishnoi, N. K.  Ranking with fairness constraints.  _arXiv preprint arXiv:1704.06840_ , 2017b.
  * Charikar et al. [2005] Charikar, M., Guruswami, V., and Wirth, A.  Clustering with qualitative information.  _Journal of Computer and System Sciences_ , 71(3):360–383, 2005.
  * Charikar et al. [2017] Charikar, M., Gupta, N., and Schwartz, R.  Local guarantees in graph cuts and clustering.  In Eisenbrand, F. and Koenemann, J. (eds.), _Integer Programming and Combinatorial Optimization_ , pp. 136–147, Cham, 2017. Springer International Publishing.
  * Chawla et al. [2015] Chawla, S., Makarychev, K., Schramm, T., and Yaroslavtsev, G.  Near optimal lp rounding algorithm for correlationclustering on complete and complete k-partite graphs.  In _Proceedings of the forty-seventh annual ACM symposium on Theory of computing_ , pp. 219–228, 2015.
  * Chierichetti et al. [2017] Chierichetti, F., Kumar, R., Lattanzi, S., and Vassilvitskii, S.  Fair clustering through fairlets.  In Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R. (eds.), _Advances in Neural Information Processing Systems 30_ , pp. 5029–5037. Curran Associates, Inc., 2017.  URL http://papers.nips.cc/paper/7088-fair-clustering-through-fairlets.pdf.
  * Chierichetti et al. [2019] Chierichetti, F., Kumar, R., Lattanzi, S., and Vassilvtiskii, S.  Matroids, matchings, and fairness.  In _The 22nd International Conference on Artificial Intelligence and Statistics_ , pp. 2212–2220, 2019.
  * Dwork et al. [2012] Dwork, C., Hardt, M., Pitassi, T., Reingold, O., and Zemel, R.  Fairness through awareness.  In _Proceedings of the 3rd innovations in theoretical computer science conference_ , pp. 214–226, 2012.
  * Feldman et al. [2015] Feldman, M., Friedler, S. A., Moeller, J., Scheidegger, C., and Venkatasubramanian, S.  Certifying and removing disparate impact.  In _proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining_ , pp. 259–268, 2015.
  * Filkov & Skiena [2004] Filkov, V. and Skiena, S.  Integrating microarray data by consensus clustering.  _International Journal on Artificial Intelligence Tools_ , 13(04):863–880, 2004.
  * Guo et al. [2008] Guo, J., Hüffner, F., Komusiewicz, C., and Zhang, Y.  Improved algorithms for bicluster editing.  In Agrawal, M., Du, D., Duan, Z., and Li, A. (eds.), _Theory and Applications of Models of Computation_ , pp. 445–456, Berlin, Heidelberg, 2008\. Springer Berlin Heidelberg.  ISBN 978-3-540-79228-4.
  * Hou et al. [2016] Hou, J. P., Emad, A., Puleo, G. J., Ma, J., and Milenkovic, O.  A new correlation clustering method for cancer mutation analysis.  _Bioinformatics_ , 32(24):3717–3728, 2016.
  * Kalhan et al. [2019] Kalhan, S., Makarychev, K., and Zhou, T.  Improved algorithms for correlation clustering with local objectives.  _arXiv preprint arXiv:1902.10829_ , 2019.
  * Kamishima et al. [2012] Kamishima, T., Akaho, S., Asoh, H., and Sakuma, J.  Fairness-aware classifier with prejudice remover regularizer.  In _Joint European Conference on Machine Learning and Knowledge Discovery in Databases_ , pp. 35–50. Springer, 2012.
  * Kleindessner et al. [2019] Kleindessner, M., Samadi, S., Awasthi, P., and Morgenstern, J.  Guarantees for spectral clustering with fairness constraints.  _arXiv preprint arXiv:1901.08668_ , 2019.
  * Puleo & Milenkovic [2018] Puleo, G. J. and Milenkovic, O.  Correlation clustering and biclustering with locally bounded errors.  _IEEE Transactions on Information Theory_ , 64(6):4105–4119, 2018.
  * Rösner & Schmidt [2018] Rösner, C. and Schmidt, M.  Privacy preserving clustering with constraints.  _arXiv preprint arXiv:1802.02497_ , 2018.
  * Schmidt et al. [2018] Schmidt, M., Schwiegelshohn, C., and Sohler, C.  Fair coresets and streaming algorithms for fair k-means clustering.  _arXiv preprint arXiv:1812.10854_ , 2018.
  * Veldt et al. [2018] Veldt, N., Gleich, D. F., and Wirth, A.  A correlation clustering framework for community detection.  In _Proceedings of the 2018 World Wide Web Conference_ , pp. 439–448, 2018.

##  Appendix A Supplementary Material

###  A.1 Proof of Theorem 3

The following lemma could be proved similar to the way Lemma 2 was proved.

######  Lemma 3.

In each matching $M_{i}$ constructed in Algorithm 2, $w(M_{i})\leq 2p_{i}\cdot
OPT$.

Let $p_{\max}=\max_{i=1}^{|\mathcal{C}|}\\{p_{i}\\}$. In the following we show
how to pay for all the disagreements within a
$\mathcal{O}((p_{\max})^{2}\cdot|\mathcal{C}|^{2})\cdot OPT$ budget. For
simplicity we assume color $c_{1}$ is red, and there are at least two other
colors blue $(c_{2})$ and green $(c_{3})$. Consider the following cases:

Case 1: This case is similar to Case $1$ in Section 5.1. Consider a
disagreement between a red vertex (let’s say $r_{1}$), and a node of a
different color (let’s say blue node $b_{3}$) such that $r_{1}$ and $b_{3}$
are not matched by matching $M_{2}$. Let’s assume $M_{2}$ matches $b_{3}$ to
$r_{2}$.

  * •

Case 1.1: If edges $(r_{1},b_{3})$ and $(r_{1},r_{2})$ have disagreeing
labels, then cost of the edge $(r_{2},b_{3})$ counted in the $w(M_{2})$ is
paying for it.

  * •

Case 1.2: If edges $(r_{1},b_{3})$ and $(r_{1},r_{2})$ have the same signs,
the disagreement on $(r_{1},b_{3})$ could be charged to the edge
$(r_{1},r_{2})$. The number of such edges charged to $(r_{1},r_{2})$ is
$2p_{2}$ (and $2p_{i}$ in general if instead of $b_{3}$ we considered a node
of color $c_{i}$).

Case 2: There exists a disagreement between two non-red nodes from two
different hyper nodes, let’s say between nodes $b_{1}$, $g_{1}$. Let’s assume
$b_{1}$ is matched to $r_{1}$ by $M_{2}$ (the matching between red and blue
nodes), and $g_{1}$ is matched to $r_{2}$ by $M_{3}$ (the matching between red
and green nodes).

  * •

Case 2.1: Edges $(b_{1},g_{1})$ and $(r_{1},g_{1})$ are disagreeing. Then the
cost of edge $(r_{1},b_{1})$ included in the cost of $w(M_{2})$ is paying for
it.

  * •

Case 2.2: Edges $(b_{1},g_{1})$ and $(r_{1},g_{1})$ have the same labels and
have different labels with $(r_{1},r_{2})$. We charge the disagreement on
$(b_{1},g_{1})$ and $(r_{1},g_{1})$ to the edge $(r_{2},g_{1})$. There are
$(|\mathcal{C}|-1)\cdot p_{\max}$ choices for $b_{1}$ which are all the nodes
that are matched to $r_{1}$ in all the matchings
$M_{2},\cdots,M_{|\mathcal{C}|}$. Therefore in this case, at most
$(|\mathcal{C}|-1)\cdot p_{\max}+1$ edges, are charged to the edge
$(r_{2},g_{1})$, when the matching edge between $(r_{2},g_{1})$ is paying $1$
for the disagreement between $(r_{1},r_{2})$ and $(r_{1},g_{1})$.

  * •

Case 2.3: Edges $(b_{1},g_{1}),(r_{1},g_{1}),(r_{1},r_{2})$ all have the same
labels. We charge disagreements on these edges to $(r_{1},r_{2})$. There are
at most $((|\mathcal{C}|-1)\cdot p_{\max})^{2}$ choices for a pair of non-red
nodes like $(b_{1},g_{1})$, charged to $(r_{1},r_{2})$.

Case 3: This case captures the disagreement between two non-red nodes in the
same hyper-node and is similar to Case $3$ in Section 5.1.

There are a total of $((|\mathcal{C}|-1)\cdot p_{\max})^{2}+2p_{\max}$ charges
on edges between red nodes (Cases 1.2 and 2.3) accounting for the total cost
to be $(((|\mathcal{C}|-1)\cdot p_{\max})^{2}+2p_{\max})C$, where $C$ is the
correlation clustering objective on red vertices. Similarly, we charge each
matched edge $|\mathcal{C}|\cdot p_{\max}+1$ times (Case 2.2) and $p_{\max}-1$
times (Case 3), thereby contributing
$\sum_{i=2}^{|\mathcal{C}|}((|\mathcal{C}|+1)\cdot p_{\ max})\cdot w(M_{i})$
to the final objective. Considering Lemma 3, we can conclude the approximation
ratio is $\mathcal{O}((p_{\max})^{2}\cdot|\mathcal{C}|^{2})$, and this
completes proof of Theorem 3.

Note: When $p_{max}=1$, we can perform classical correlation clustering on
nodes of any color $C_{i}\in\mathcal{C}$ and pick the one that has minimum
value. This optimization helps improve the approximation of case 2.3 by
reducing the dependence from $|\mathcal{C}|^{2}$ to $|\mathcal{C}|$.

###  A.2 Proof of Theorem 4

######  Lemma 4.

$w(M)\leq 2q\cdot OPT$.

###### Proof.

Given the optimum solution $OPT$, we can show a $b$-matching $M^{\prime}$
could be constructed where endpoints of each matched edge belong to the same
cluster, and the degree of each red node is at least $p$ and at most $q$. In
the $OPT$ solutin, in each cluster, the ratio of the number of red to blue
nodes is between $1:q$ and $1:p$. Consider a specific cluster $\mathcal{X}$ in
the $OPT$ solution, let $n_{r},n_{b}$ denote the number of red and blue nodes
in this cluster respectively. Therefore, $n_{r}\cdot p\leq n_{b}\leq
n_{r}\cdot q$. Construct a $b$-matching inside $\mathcal{X}$ as following:
first assign $p$ distinct blue nodes to each red node in $\mathcal{X}$. If any
blue nodes in $\mathcal{X}$ are left un-assigned, assign them to any red node
in $\mathcal{X}$ which is assigned to less than $q$ blue nodes. Since
$n_{b}\leq q\cdot n_{r}$, we can find a $b$-matching with desired properties
in each cluster of the $OPT$ solution. $M^{\prime}$ is the union of the
$b$-matchings formed in all the clusters. First, we show $w(M^{\prime})\leq
2q\cdot OPT_{G}$. Consider an edge between arbitrary vertices $v_{i}$ and
$v_{j}$, such that they are not matched in $M^{\prime}$. If a disagreement
occurs on the edge between $(v_{i},v_{j})$ in $OPT_{G}$, this disagreement
could have been counted at most $2q$ times in $w(M^{\prime})$. Therefore
$w(M^{\prime})\leq 2q\cdot OPT_{G}$. Since $M$ is a min cost $b$-matching
satisfying degree constraints:

$w(M)\leq w(M^{\prime})\leq 2q\cdot OPT_{G}$

∎

The algorithm is as following: run an $\alpha$-approximation correlation
clustering on a subset of $G$ which includes the red vertex from each hyper-
node (i.e. a collection of matched nodes). In the following, we show we can
pay for all the disagreements within a
$\Big{(}(q^{2}+2q)\cdot\alpha+4q^{2}\Big{)}\cdot OPT$ budget.

Case 1: In Figure 1(b), consider a disagreement between a red vertex ($r_{1}$)
and a blue ($b_{3}$) node from different hyper-nodes. Two cases might happen:

  * •

Case 1.1: If edges $(r_{1},b_{3})$ and $(r_{1},r_{2})$ have disagreeing
labels, then cost of the edge $(r_{2},b_{3})$ counted in the matching is
paying for it.

  * •

Case 1.2: If edges $(r_{1},b_{3})$ and $(r_{1},r_{2})$ have the same signs,
the disagreement on $(r_{1},b_{3})$ could be charged to the edge
$(r_{1},r_{2})$. The number of such edges charged to $(r_{1},r_{2})$ is at
most $2q$.

Case 2: There exists a disagreement between two blue nodes from two different
hyper-nodes, like $(b_{1},b_{3})$ in Figure 1(b).

  * •

Case 2.1: Edges $(b_{1},b_{3})$ and $(r_{1},b_{3})$ are disagreeing. Then the
cost of edge $(r_{1},b_{1})$ included in the cost of the matching is paying
for it.

  * •

Case 2.2: Edges $(b_{1},b_{3})$ and $(r_{1},b_{3})$ have the same labels and
have different labels with $(r_{1},r_{2})$. We charge the disagreement on
$(b_{1},b_{3})$ to the edge $(r_{2},b_{3})$. There are $p$ choices for
$b_{1}$, therefore at most $p$ edges of this type, plus the edge
$(r_{1},b_{3})$ are charged to the edge $(r_{2},b_{3})$, when $M$ is paying
$1$ for the disagreement between $(r_{1},r_{2})$ and $(r_{1},b_{3})$.
Therefore, we need to account for at most $q+1$ times the matching cost to
account for all edges of this type.

  * •

Case 2.3: Edges $(b_{1},b_{3}),(r_{1},b_{3}),(r_{1},r_{2})$ all have the same
labels. There are at most $q^{2}$ choices for a pair of blue nodes like
$(b_{1},b_{3})$, and disagreements on these edges could be charged to
$(r_{1},r_{2})$.

Case 3: A disagreement between two blue nodes in the same hyper-node, $b_{1}$
and $b_{2}$ which means $(b_{1},b_{2})$ is a negative edge. If $(r_{1},b_{1})$
is positive then $(r_{1},b_{2})$’s contribution in the matching cost captures
it. Similarly, if $(r_{1},b_{2})$ is a positive edge then the
$(r_{1},b_{2})$’s contribution in matching cost captures this. If both
$(r_{1},b_{1})$ and $(r_{1},b_{2})$ are negative edges then we can charge both
the edges $1/2$. The total number of times an edge $(r_{1},b_{1})$ is charged
is at most $q-1$ as there can be a maximum of $q-1$ negative edges from
$b_{1}$.

There are a total of $q^{2}+2q$ charges on edges between red nodes (Cases 1.2
and 2.3) accounting for the total cost to be $(q^{2}+2q)C$, where $C$ is the
correlation clustering objective on red vertices. Similarly, we charge each
matched edge at most $q+1$ times their weight in Case 2.2 and at most $q-1$
times their weight in Case 3, the total contribution to the final objective is
at most $(2q)\cdot w(M)$. All the charges required to handle cases 1.1 and 2.1
do not add any additional cost to the objective as they are already accounted
for the edges considered in $(2q)\cdot w(M)$. Hence, the total objective value
of returned clusters is at most:

$(q^{2}+2q)C+(q+1)\cdot w(M)\leq\Big{(}(q^{2}+2q)\cdot\alpha+2q\times
2q\Big{)}\cdot OPT$

Therefore the approximation ratio is $\mathcal{O}(q^{2})$, and this completes
proof of Theorem 4.

###  A.3 Proof of Theorem 5

Algorithm 2 could be modified to handle this scenario. We need to find a min
cost $b$-matching $M_{i}$ in each iteration where degree of each node of color
$c_{1}$ needs to be between $p_{i}$ and $q_{i}$, and degree of each node of
color $c_{i}$ needs to be $1$. By applying Lemma 4 to each matching $M_{i}$,
one can see $w(M_{i})\leq 2q_{i}\cdot OPT$.

Next, we run an $\alpha$-approximation on the nodes of color $c_{1}$, and for
each fixed vertex $u$ of color $c_{1}$, all the vertices that are matched to
$u$ using any of the matchings $\\{M_{2},\cdots,M_{|\mathcal{C}|}\\}$ go to
the same cluster as $u$.

Let $q_{max}=\max\\{q_{2},\cdots,q_{|\mathcal{C}|}\\}$. In the following we
show how to pay for all disagreements within a
$\mathcal{O}((q_{\max}^{2})\cdot|\mathcal{C}|^{2})\cdot OPT$ budget. For
simplicity let’s assume color $c_{1}$ is red, and there are at least two other
colors blue $(c_{2})$ and green $(c_{3})$. Consider the following cases:

Case 1: Consider a disagreement between a red vertex (let’s say $r_{1}$), and
a node of a different color (let’s say blue node $b_{3}$) such that $r_{1}$
and $b_{3}$ are not matched by matching $M_{2}$. Let’s assume $M_{2}$ matches
$b_{3}$ to $r_{2}$.

  * •

Case 1.1: If edges $(r_{1},b_{3})$ and $(r_{1},r_{2})$ have disagreeing
labels, then cost of the edge $(r_{2},b_{3})$ counted in the $w(M_{2})$ is
paying for it.

  * •

Case 1.2: If edges $(r_{1},b_{3})$ and $(r_{1},r_{2})$ have the same signs,
the disagreement on $(r_{1},b_{3})$ could be charged to the edge
$(r_{1},r_{2})$. The number of such edges charged to $(r_{1},r_{2})$ is at
most $2q_{2}$ (and $2q_{i}$ in general if instead of $b_{3}$ we considered a
node of color $c_{i}$).

Case 2: There exists a disagreement between two non-red nodes from two
different hyper nodes, let’s say between nodes $b_{1}$, $g_{1}$. Let’s assume
$b_{1}$ is matched to $r_{1}$ by $M_{2}$ (the matching between red and blue
nodes), and $g_{1}$ is matched to $r_{2}$ by $M_{3}$ (the matching between red
and green nodes).

  * •

Case 2.1: Edges $(b_{1},g_{1})$ and $(r_{1},g_{1})$ are disagreeing. Then the
cost of edge $(r_{1},b_{1})$ included in the cost of $w(M_{2})$ is paying for
it.

  * •

Case 2.2: Edges $(b_{1},g_{1})$ and $(r_{1},g_{1})$ have the same labels and
have different labels with $(r_{1},r_{2})$. We charge the disagreement on
$(b_{1},g_{1})$ and $(r_{1},g_{1})$ to the edge $(r_{2},g_{1})$. There are
$(|\mathcal{C}|-1)\cdot q_{\max}$ choices for $b_{1}$ which are all the nodes
that are matched to $r_{1}$ in all the matchings
$M_{2},\cdots,M_{|\mathcal{C}|}$. Therefore in this case, at most
$(|\mathcal{C}|-1)\cdot q_{\max}+1$ edges, are charged to the edge
$(r_{2},g_{1})$, when the matching edge between $(r_{2},g_{1})$ is paying $1$
for the disagreement between $(r_{1},r_{2})$ and $(r_{1},g_{1})$.

  * •

Case 2.3: Edges $(b_{1},g_{1}),(r_{1},g_{1}),(r_{1},r_{2})$ all have the same
labels. We charge disagreements on these edges to $(r_{1},r_{2})$. There are
at most $((|\mathcal{C}|-1)\cdot q_{\max})^{2}$ choices for a pair of non-red
nodes like $(b_{1},g_{1})$, charged to $(r_{1},r_{2})$.

Case 3: This case captures the disagreement between two non-red nodes in the
same hyper-node and is similar to Case $3$ in Section 5.1.

There are a total of $((|\mathcal{C}|-1)\cdot q_{\max})^{2}+2q_{\max}$ charges
on edges between red nodes (Cases 1.2 and 2.3) accounting for the total cost
to be $(((|\mathcal{C}|-1)\cdot q_{\max})^{2}+2q_{\max})C$, where $C$ is the
correlation clustering objective on red vertices. Similarly, we charge each
matched edge $|\mathcal{C}|\cdot q_{\max}+1$ times (Case 2.2) and $q_{\max}-1$
times (Case 3), thereby contributing
$\sum_{i=2}^{|\mathcal{C}|}((|\mathcal{C}|+1)\cdot q_{\ max})\cdot w(M_{i})$
to the final objective. Considering Lemma 3, we can conclude the approximation
ratio is $\mathcal{O}((q_{\max})^{2}\cdot|\mathcal{C}|^{2})$, and this
completes proof of Theorem 3.


# ATGNN: Audio Tagging Graph Neural Network

Shubhr Singh, Christian J. Steinmetz, Emmanouil Benetos, , Huy Phan and Dan
Stowell SS and CS are supported jointly by UK Research and Innovation and
Queen Mary University of London under grant EP/S022694/1. This work was
supported by the Engineering and Physical Sciences Research Council [grant
number EP/V062107/1].SS, CJ and EB are with the School of Electronic
Engineering and Computer Science, Queen Mary University of London, UK (e-mail:
{s.shubhr, c.j.steinmetz, emmanouil.benetos}@qmul.ac.uk). HP is with Amazon
Alexa, Cambridge, MA 02142, USA (e-mail: huypq@amazon.co.uk). DS is with
Tilburg University, Bijsterveldenlaan, 5037 AB Tilburg, Netherlands (e-mail:
d.stowell@tilburguniversity.edu).The work was done when HP was at the School
of Electronic Engineering and Computer Science, Queen Mary University of
London, UK and prior to joining Amazon.

###### Abstract

Deep learning models such as CNNs and Transformers have achieved impressive
performance for end-to-end audio tagging. Recent works have shown that despite
stacking multiple layers, the receptive field of CNNs remains severely
limited. Transformers on the other hand are able to map global context through
self-attention, but treat the spectrogram as a sequence of patches which is
not flexible enough to capture irregular audio objects. In this work, we treat
the spectrogram in a more flexible way by considering it as graph structure
and process it with a novel graph neural architecture called ATGNN. ATGNN not
only combines the capability of CNNs with the global information sharing
ability of Graph Neural Networks, but also maps semantic relationships between
learnable class embeddings and corresponding spectrogram regions. We evaluate
ATGNN on two audio tagging tasks, where it achieves 0.585 mAP on the FSD50K
dataset and 0.335 mAP on the AudioSet-balanced dataset, achieving comparable
results to Transformer based models with significantly lower number of
learnable parameters.

###### Index Terms:

Audio tagging, Graph Neural Networks, Computational sound scene analysis

##  I Introduction

Environmental sounds carry a rich and complex mixture of information, which is
organised and categorised by the human auditory system into distinct concepts
known as sound events  (e.g. dog bark, door slam, car passing by). The advent
of deep learning models such as convolutional neural networks (CNNs)
revolutionised the research field of image classification and achieved state
of the art on numerous audio classification & tagging benchmarks as well [1].

In recent times, Transformer-based models [2, 3] have demonstrated superior
performance over CNNs in audio tagging and classification tasks. This can be
attributed to their unique capability to capture global context by employing
self-attention mechanisms, treating spectrograms as sequences of patches.
Despite the appealing advantages of Transformers, their usage comes with a
trade-off as they tend to incur substantial computational costs during both
training and inference stages [4].

Sound events can be conceptualized as compositions of multiple regions in the
spectrogram that are interlinked to form a coherent representation of the
event. This underlying structure naturally lends itself to a graph-based
representation, where each region in the spectrogram becomes a node, and the
relationships between these regions are captured through edges. Graphs provide
a flexible structure as compared to grid or sequences of patches and also open
the potential for harnessing label correlation information, enhancing the
overall predictive capabilities. Label co-occurrence graphs (LG) [5] represent
the relationships and co-occurrence patterns among different labels in a
dataset. LG has been used to improve the performance of models in multi-label
image recognition [5] as well as in audio tagging [6]. Keeping the benefits of
graph structure in mind and given the recent success of graph based models in
image classification [7, 8], we propose the Audio Tagging graph neural network
(ATGNN), an end-to-end graph convolution network for audio tagging
applications.

In our approach, we begin by extracting features from an input spectrogram
using a backbone CNN. Each element of the resulting feature map is then
considered as an individual node. To enable effective communication between
distant patches in the original spectrogram, we dynamically construct edges
between nodes based on their similarity in the feature space, facilitating the
exchange of information across different regions of the spectrogram, allowing
our model to capture and leverage complex dependencies.

In addition to employing graph processing in the feature space, our approach
incorporates learnable label embeddings, serving a dual purpose in capturing
two distinct relationships. Firstly, these embeddings facilitate the modelling
of semantic relationships across class labels, enabling the model to
comprehend the underlying correlations between different sound event
categories. Secondly, the label embeddings establish cross-domain
relationships between spectrogram regions and label embeddings, establishing
connections between the labels and regions of interest in the spectrogram,
enhancing the overall discriminative capability of our model.

There has been a steady increase in the adoption of GNNs for audio tasks such
as speech emotion recognition (SER) [9], speaker diarisation [10, 11], audio
tagging [12, 6].

Our research is different from prior works as it leverages spectrogram graph
structures to effectively utilize inter-region relationships, and applies an
end-to-end approach to concurrently learn label correlations and label-
spectrogram interactions.

The main contribution of this paper is therefore summarised as follows: (i) We
model the spectrogram as a graph structure and propose an end-to-end graph
based model for audio tagging. (ii) To the best of our knowledge, this is the
first attempt to simultaneously model correlations between labels and
spectrograms, as well as between labels themselves, in an end-to-end fashion
without relying on previously established correlations and demonstrates the
effectiveness of the methodology on two widely used audio tagging datasets.

Figure 1: ATGNN: The input spectrogram is passed through a CNN backbone and a
k-nearest neighbour graph is constructed with the the feature map pixel as
nodes. The patch nodes are updated with graph convolution across $M$ PGN
blocks and then fed into an MLG block where cross-correlation between
learnable label embeddings and patch nodes is learnt. Each label node connects
to its nearest patch nodes and is updated using graph convolution. The LLG
block maps label-label correlation using a learned adjacency matrix. A stack
of PGN and MLG blocks is used to refine the patch and label embeddings and is
combined for final prediction.

##  II Model architecture

ATGNN consists of three blocks: Patch GNN (PGN), Patch-Label GNN (PLG), and
Label-Label GNN (LLG). The PGN block models the correlation across different
patches of the input mel-spectrogram. The PLG block models captures the
relationship between input patches & label embeddings and the LLG block models
the correlation between different label embeddings. Following the convention
of [8], we refer to the stack of single PLG and LLG block as a Multi-Label GNN
(MLG) block.

###  II-A PGN: Patch GNN

The input spectrogram with size $F\times T\times 1$ is first divided into $N$
patches, where $F$ denotes the frequency axis dimension and $T$ denotes the
time axis dimension. Instead of directly splitting and flattening images into
tokens based on a linear patch embedding layer as used in Audio Spectrogram
Transformer (AST) [2], a CNN based backbone is adopted for extraction of
patches. Input $X\in\mathbb{R}^{F\times T\times 1}$ is transformed to a
feature map $X_{t}\in\mathbb{R}^{M}$, where $M=\left(F/p\ \times\
T/p\right)\times D$, with $p$ as the reduction ratio and $D$ as the feature
dimension. The resulting feature map is flattened as
$\mathbb{R}^{FT/p^{2}\times D}$ and summed with a learnable positional
encoding. The flattened feature map can be viewed as a set of unordered nodes
from which a $k$-nearest neighbour graph is constructed based on Euclidean
distance between nodes. The graph is further updated by a graph convolution
layer, which can exchange information between neighbouring nodes through
message passing operation. Specifically, node $x_{i}$ is updated using max-
relative graph convolution [13]:

$g(\cdot)=x^{{}^{\prime\prime}}=[x_{i},\max(x_{j}-x_{i})\ |\
j\in\textit{N}(x_{i})]$ (1)
$h(\cdot)=x^{{}^{\prime}}=x^{{}^{\prime\prime}}W_{update},$ (2)

where $N(x_{i})$ are the neighbours of the node $x_{i}$ and $x^{{}^{\prime}}$
and $x^{{}^{\prime\prime}}$ denote updated node embeddings through different
update operations. Combination of (1) and (2) is termed as GraphConv. A linear
layer is applied to each node before and after GraphConv to increase feature
diversity and avoid oversmoothing, followed by nonlinear activation. The
updated graph convolution operation can be denoted by

$y_{i}=\sigma(GraphConv(W_{in}x_{i}))W_{out}+x_{i},$ (3)

where $y_{i}$ denotes the updated node embedding, $\sigma$ denotes non
linearity, $W_{in}$ and $W_{out}$ are weights of fully connected layers
applied before and after GraphConv. Similar to Transformer models [14], a
feed-forward layer network (FFN) is applied to each node embedding. FFN
essentially comprises two linear layers with a non-linear activation between
the layers. The combination of GraphConv followed by FFN layer comprises a
single PGN block.

In order to stack multiple PGN layers and avoid oversmoothing due to depth,
dilated aggregation is adopted for the GraphConv operation. Dilated
convolutions were proposed in [15] as an alternative to max pool operations.
Specifically, for an input graph $G=(V,E)$ with dilated $k$-NN and $d$ as the
dilation rate, the dilated $k$-NN returns the $k$ nearest neighbors within the
$k\times d$ neighborhood region by skipping every $d$ neighbors. Dilated
aggregation helps in maintaining feature diversity and reduces the over-
smoothing across graph layers.

The PGN block architecture has two flavours, namely isotropic and pyramid [8].
Isotropic architecture is used by Transformer styled models where the feature
dimension remains constant across layers whereas pyramid architecture is
primarily used in CNN based architectures like ResNet [16], where feature maps
are down-sampled across subsequent layers.

Isotropic architecture —  The number of nodes for this architecture is set to
$N=FT/256$, depending on the value of $F$ and $T$. The number of $k$ in $k$-NN
is linearly increased from $k$ to $2\cdot k$ across the layers.

Pyramid architecture —  The pyramid architecture is used to generate multi-
scale feature maps to exploit the compositional hierarchies of the input,
where higher level features are obtained by composition of local level
features captured in the initial layers. In addition to the learnable
positional embedding, a relative positional encoding similar to [17] is used
in the pyramid model. For node $i$ and $j$, if the positional encoding is
$e_{i}$ and $e_{j}$, then their relative positional distance between them is
$e_{i}^{\mathsf{T}}e_{j}$. This distance is added to the feature embedding
distance to construct the $k$-NN graph [7].

###  II-B PLG: Patch-Label GNN

The PLG block maps the correlation between patch and label embeddings, where
patch embeddings $X=\\{x_{1},x_{2},\ldots,x_{N}\\}\in\mathbb{R}^{N\times C}$
are the output of $M$ PGN blocks and
$L=\\{l_{1},l_{2},\ldots,l_{S}\\}\in\mathbb{R}^{S\times C}$ are the learnable
label embeddings with dimensionality $C$ and $S$ number of classes. Each label
node connects to its $k_{plg}$ patch node neighbours measured by Euclidean
distance, post which max-relative graph convolution is used to update the
label nodes as follows:

$l_{i}^{{}^{\prime\prime}}=[l_{i},\max(l_{i}-x{j})\ |\ j\in N(l_{i})]$ (4)
$l_{i}^{{}^{\prime}}=l_{i}+l_{i}^{{}^{\prime\prime}}W_{l-update}$ (5)

where $l_{i}$ is the $i$-th label node and $W_{l-update}\in\mathbb{R}^{S\times
S}$ is the learnable update matrix for label nodes. The label embeddings are
updated by message passing from the corresponding label nodes, which builds
the correlation between the spectrogram regions and the label embeddings.

###  II-C LLG: Label-Label GNN

The LLG block is used to map correlation between different label embeddings.
The updated label embeddings from PLG blocks are used as nodes in a fully
connected graph and each node is updated by aggregating information from the
other nodes in the following manner:

$\hat{L}=AL^{{}^{\prime}}+L^{{}^{\prime}},$ (6)

where
$L^{{}^{\prime}}=[l_{1}^{{}^{\prime}},l_{2}^{{}^{\prime}},\ldots,l_{S}^{{}^{\prime}}]\in
R^{S\times C}$ are updated label embeddings from the PLG block. $A\in
R^{S\times S}$ is a learnable adjacency matrix with random initialisation.
$\hat{L}=[\hat{l_{1}},\hat{l_{2}},\ldots,\hat{l_{S}}]\in R^{S\times C}$ is the
matrix of refined label node embeddings. $A$ is learnt during training of the
model and captures the latent label correlations.

###  II-D Prediction

The final output of the PGN block is aggregated via global average pooling and
a set of $1\times 1$ convolution layers with nonlinear activation are applied
to obtain the final patch logits:

$Y_{patch}=Conv_{p}(AvgPool(X_{patch})),$ (7)

where $Y_{patch}\\!\in\\!\mathbb{R}^{1\times S}$ denotes the final patch
logits. $Conv_{p}$ denotes the set of $1\\!\times\\!1$ convolution layer,
$AvgPool$ denotes the average pooling operation applied on the final output
$X$of the PGN block.

For label nodes, a readout function $R$ projects each of the $S$ label
embeddings $l_{i}^{{}^{\prime}}$ using a projection matrix
$W^{p}\in\mathbb{R}^{S\times d}$ where $W^{p}_{i}$ is the learned output
vector for $l^{{}^{\prime}}_{i}$. This is akin to applying a separate linear
layer to map the presence of each label in the given input:

$\hat{y}_{i}=W^{p}_{i}l_{i}^{{}^{\prime}\mathsf{T}}.$ (8)

The classification score of each label embedding are concatenated as
$\hat{Y}\\!=\\![\hat{y}_{1},\hat{y}_{2},\ldots,\hat{y}_{S}]$
$\in\mathbb{R}^{1\times S}$. The final score is obtained as:

$Y=sigmoid(Y_{patch}+\hat{Y}).$ (9)

##  III Experiments

###  III-A Datasets

We evaluated the proposed models on two commonly used datasets: AudioSet [18]
and FSD50K [19]. AudioSet is a large scale weakly labelled audio event dataset
of over 2 million 10-second audio clips extracted from YouTube videos. The
audio events in the datasets are categorised into 527 predefined labels with
each audio clip containing one or more audio events. We use the balanced
subset of this dataset comprising 20550 training samples and 1887 evaluation
samples. FSD50K [19] is a publicly available weakly labelled dataset
comprising sound event audio clips categorized across 200 classes drawn from
the AudioSet ontology. The dataset comprises 3 subsets: training, validation
and evaluation subset consisting of 37134, 4170 and 10231 samples
respectively. The audio clips in the dataset are of variable length, ranging
from 0.3 to 30s.

###  III-B Training pipeline

In order to conduct a fair evaluation, we adopted the training pipeline from
[20], details of which are as follows:

Data Preprocessing —  The audio files were first resampled to 16 kHz and a
short-time Fourier transform (STFT) with a window size of 25ms and hop length
of 10 ms, was applied to each audio clip in order to compute a spectrogram.
Subsequently, a 128-dimensional mel filter bank was applied followed by a
logarithmic operation to extract its log-mel spectrogram. Due to variability
in audio clip duration, we applied zero-padding to achieve sample-wise uniform
length of 1024 frames for FSD50K and 1056 for AudioSet experiments.

Model details —  The PGN block of the proposed models was initialised with
ImageNet pre-trained weights from [7] for all the experiments. The MLG blocks
were trained from scratch. The terms “iso” and “pyr” respectively denote
isometric and pyramid versions of the PGN block. The pyramid model has two
different sizes - small (s) and medium (med). In case of pyramid model, a
stage-wise approach was followed where each stage consists of $M$ PGN blocks
followed by $P$ MLG blocks. In case of pyr-s, we found the best results with
$M=[2,2,6,2]$ and $P=[1,1,3,1]$. For pyr-med, best results were achieved with
$M=[2,2,16,2]$ and $P=[1,1,6,1]$. In our experiments, we varied $k$ from 9 to
20 as shown in Table I for the PGN block and observed that the $k$ values did
not change the results significantly, hence for all experiments we used $k$
and $k_{plg}$ $=9$.

TABLE I: Mean Average Precision vs $k$-NN values for PGN block k | 9 | 12 | 15 | 18 | 20
---|---|---|---|---|---
mAP | 57.9 | 57.7 | 57.7 | 57.9 | 57.6

Balanced Sampling —  We adopted a random balanced sampling approach for
FSD50K, where each audio clip is assigned a sampling weight such that higher
weight is assigned to clips containing rare events. For more details, refer to
[20].

Data Augmentation —  We used mixup [21] data augmentation (mixup ratio $=0.5$)
and time-frequency masking [22] with maximum time mask of 192 frames and
maximum frequency mask of 48 bins for all the experiments.

Label Enhancement —  Label noise is prevalent in both FSD50K and AudioSet,
hence we adopted the enhanced labels proposed in [20].

Training details —  We used an initial learning rate of 5e-4 and linear
learning rate warm-up strategy for the first 1,000 iterations. The learning
rate was halved every 5 epochs after the 10th epoch for FSD50K experiments and
after every 5 epochs after the 35th and 10th epoch for the AudioSet
experiments. All models were trained for 50 epochs on FSD50K and 60 epochs on
AudioSet with batch size of 24 along with the Adam optimizer [23] and binary
cross-entropy.

##  IV Results and Discussion

In this section we present the results of our experiments. Tables II and III
showcase the results obtained on the evaluation set of AudioSet balanced and
FSD50k. We primarily compare ATGNN with AST and PSLA models, both of which
have achieved SOTA results on AudioSet and FSD50k. It can be seen from Table
II that the isometric version of ATGNN achieves comparable performance to AST
and outperforms the PSLA model, wheres both the pyramid versions outperform
AST model. Our results for AST differs from the results reported in the
original paper [2] due to mismatch in our training set size with [20], hence
it was not possible to use the label enhancement files provided by [20].

TABLE II: Results on AudioSet-balanced. $\ast$ indicates our run. Model | #Params | mAP
---|---|---
PANNS [24] | 81.0 M | 0.278
PSLA [20] $\ast$ | 13.6 M | 0.308
AST [2] $\ast$ | 88.7 M | 0.330
ATGNN-iso$\ast$ | 38.7 M | 0.330
ATGNN-pyr-s$\ast$ | 36.4 M | 0.335
ATGNN-pyr-s (-MLG)$\ast$ | 36.4 M | 0.331
ATGNN-pyr-med$\ast$ | 62.7 M | 0.336
ATGNN-pyr-med (-MLG)$\ast$ | 62.7 M | 0.332
TABLE III: Results on FSD50K. $\ast$ indicates our run. Model | #Params | mAP
---|---|---
FSD50K Baseline [19] | 0.27M | 0.434
Wav2CLIP [25] | - | 0.431
Audio Transformers [26] | 2.3M | 0.537
PSLA [20]$\ast$ | 13.6M | 0.559
AST [2]$\ast$ | 88.7M | 0.572
ATGNN-iso$\ast$ | 38.7M | 0.570
ATGNN-pyr-s$\ast$ | 36.4M | 0.583
ATGNN-pyr-s (-MLG)$\ast$ | 36.4M | 0.579
ATGNN-pyr-med$\ast$ | 62.7M | 0.585
ATGNN-pyr-med$\ast$(-MLG) | 62.7M | 0.580

The results are similar for the FSD50K dataset as well where the isometric
architecture is competent with AST and the pyramid architecture outperforms
PSLA and AST. As shown in Tables II and III, the MLG block brings an
additional benefit of $\approx 0.4$ mAP to the overall score, implying that
the SGN block can be used as a standalone model for obtaining comparable
results to the SOTA models for audio classification tasks.

##  V Conclusions

We presented an end-to-end GNN model that learns feature and label
correlations for audio tagging. This model uses a CNN for local feature
extraction, and graph convolution operations for global context mapping.
Crucially, it learns cross-correlations between label and feature embeddings,
consistently surpassing state-of-the-art models on two major audio
classification benchmarks. Future work will explore beyond patch-based graph
construction, considering classical methods like visibility graphs for time
series or innovative concepts like treating the spectrogram as a 3D-point
cloud. Additionally, the adoption of multi-range edges could enable nuanced
spatial interactions, with local edges for detailed relations and long-range
edges for signal harmonics.We hope our work encourages consideration of graph-
based models as alternate representation learning methodologies, alongside
convolution and attention-based architectures, for audio classification tasks.

## References

  * [1] S. Hershey, S. Chaudhuri, D. P. Ellis, J. F. Gemmeke, A. Jansen, R. C. Moore, M. Plakal, D. Platt, R. A. Saurous, B. Seybold _et al._ , “Cnn architectures for large-scale audio classification,” in _2017 ieee international conference on acoustics, speech and signal processing (icassp)_. IEEE, 2017, pp. 131–135.
  * [2] Y. Gong, Y.-A. Chung, and J. Glass, “Ast: Audio spectrogram transformer,” _arXiv preprint arXiv:2104.01778_ , 2021.
  * [3] K. Koutini, J. Schlüter, H. Eghbal-zadeh, and G. Widmer, “Efficient training of audio transformers with patchout,” _arXiv preprint arXiv:2110.05069_ , 2021.
  * [4] X. Liu, H. Peng, N. Zheng, Y. Yang, H. Hu, and Y. Yuan, “Efficientvit: Memory efficient vision transformer with cascaded group attention,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2023, pp. 14 420–14 430.
  * [5] Z.-M. Chen, X.-S. Wei, P. Wang, and Y. Guo, “Multi-label image recognition with graph convolutional networks,” in _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , 2019, pp. 5177–5186.
  * [6] H. Shrivastava, Y. Yin, R. R. Shah, and R. Zimmermann, “Mt-gcn for multi-label audio-tagging with noisy labels,” in _ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2020, pp. 136–140.
  * [7] K. Han, Y. Wang, J. Guo, Y. Tang, and E. Wu, “Vision gnn: An image is worth graph of nodes,” in _NeurIPS_ , 2022.
  * [8] R. Yao, S. Jin, W. Liu, C. Qian, P. Luo, and J. Wu, “Ml-vig: Multi-label image recognition with vision graph convolutional network.”
  * [9] J. Liu, Y. Song, L. Wang, J. Dang, and R. Yu, “Time-frequency representation learning with graph convolutional network for dialogue-level speech emotion recognition.” in _Interspeech_ , 2021, pp. 4523–4527.
  * [10] Y. Kwon, H.-S. Heo, J.-w. Jung, Y. J. Kim, B.-J. Lee, and J. S. Chung, “Multi-scale speaker embedding-based graph attention networks for speaker diarisation,” in _ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2022, pp. 8367–8371.
  * [11] J. Wang, X. Xiao, J. Wu, R. Ramamurthy, F. Rudzicz, and M. Brudno, “Speaker diarization with session-level speaker embedding refinement using graph neural networks,” in _ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2020, pp. 7109–7113.
  * [12] Y. Sun and S. Ghaffarzadegan, “An ontology-aware framework for audio event classification,” in _ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2020, pp. 321–325.
  * [13] G. Li, M. Muller, A. Thabet, and B. Ghanem, “Deepgcns: Can gcns go as deep as cnns?” in _Proceedings of the IEEE/CVF international conference on computer vision_ , 2019, pp. 9267–9276.
  * [14] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin, “Attention is all you need,” _Advances in neural information processing systems_ , vol. 30, 2017.
  * [15] F. Yu and V. Koltun, “Multi-scale context aggregation by dilated convolutions,” _arXiv preprint arXiv:1511.07122_ , 2015.
  * [16] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016, pp. 770–778.
  * [17] Z. Liu, Y. Lin, Y. Cao, H. Hu, Y. Wei, Z. Zhang, S. Lin, and B. Guo, “Swin transformer: Hierarchical vision transformer using shifted windows,” in _Proceedings of the IEEE/CVF international conference on computer vision_ , 2021, pp. 10 012–10 022.
  * [18] J. F. Gemmeke, D. P. Ellis, D. Freedman, A. Jansen, W. Lawrence, R. C. Moore, M. Plakal, and M. Ritter, “Audio set: An ontology and human-labeled dataset for audio events,” in _2017 IEEE international conference on acoustics, speech and signal processing (ICASSP)_. IEEE, 2017, pp. 776–780.
  * [19] E. Fonseca, X. Favory, J. Pons, F. Font, and X. Serra, “Fsd50k: an open dataset of human-labeled sound events,” _IEEE/ACM Transactions on Audio, Speech, and Language Processing_ , vol. 30, pp. 829–852, 2021.
  * [20] Y. Gong, Y.-A. Chung, and J. Glass, “PSLA: Improving audio tagging with pretraining, sampling, labeling, and aggregation,” _IEEE/ACM Transactions on Audio, Speech, and Language Processing_ , vol. 29, pp. 3292–3306, 2021. [Online]. Available: https://doi.org/10.1109%2Ftaslp.2021.3120633
  * [21] H. Zhang, M. Cisse, Y. N. Dauphin, and D. Lopez-Paz, “mixup: Beyond empirical risk minimization,” _arXiv preprint arXiv:1710.09412_ , 2017.
  * [22] D. S. Park, W. Chan, Y. Zhang, C.-C. Chiu, B. Zoph, E. D. Cubuk, and Q. V. Le, “Specaugment: A simple data augmentation method for automatic speech recognition,” _arXiv preprint arXiv:1904.08779_ , 2019.
  * [23] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” _arXiv preprint arXiv:1412.6980_ , 2014.
  * [24] Q. Kong, Y. Cao, T. Iqbal, Y. Wang, W. Wang, and M. D. Plumbley, “Panns: Large-scale pretrained audio neural networks for audio pattern recognition,” _IEEE/ACM Transactions on Audio, Speech, and Language Processing_ , vol. 28, pp. 2880–2894, 2020.
  * [25] H.-H. Wu, P. Seetharaman, K. Kumar, and J. P. Bello, “Wav2clip: Learning robust audio representations from clip,” in _ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2022, pp. 4563–4567.
  * [26] P. Verma and J. Berger, “Audio transformers: Transformer architectures for large scale audio understanding. adieu convolutions,” _arXiv preprint arXiv:2105.00335_ , 2021.