# If At First You Don’t Succeed:
Test Time Re-ranking for Zero-shot, Cross-domain Retrieval

Finlay G. C. Hudson
Department of Computer Science
University of York
York, United Kingdom
<EMAIL_ADDRESS>William A. P. Smith
Department of Computer Science
University of York
York, United Kingdom
<EMAIL_ADDRESS>
###### Abstract

In this paper we propose a novel method for zero-shot, cross-domain image
retrieval in which we make two key contributions. The first is a test-time re-
ranking procedure that enables query-gallery pairs, without meaningful shared
visual features, to be matched by incorporating gallery-gallery ranks into an
iterative re-ranking process. The second is the use of cross-attention at
training time and knowledge distillation to encourage cross-attention-like
features to be extracted at test time from a single image. When combined with
the Vision Transformer architecture and zero-shot retrieval losses, our
approach yields state-of-the-art results on the Sketchy and TU-Berlin sketch-
based image retrieval benchmarks. However, unlike many previous methods, none
of the components in our approach are engineered specifically towards the
sketch-based image retrieval task - it can be generally applied to any cross-
domain, zero-shot retrieval task. We therefore also show results on zero-shot
cartoon-to-photo retrieval using the Office-Home dataset.

##  1 Introduction

The problem of zero-shot, cross-domain retrieval involves matching a query
image of an unseen class against a set of gallery images of a different domain
to the query. Common domains of interest include photos, sketches, cartoons,
clip art, schematics and maps. Retrieval amounts to ranking the gallery images
against the query according to some similarity measure. This is particularly
challenging in the zero-shot, cross-domain setting since correctly matched
query-gallery pairs may contain no shared visual features. Instead, they may
only match in an abstract semantic sense but since the class is unseen, the
model may not have learnt appropriate semantic concepts that enable matching.

This provides the motivation for the first ingredient to our proposed
approach. The initial ranking based on similarities between the embeddings of
the visual features of the query and gallery images will contain a mixture of
correct and incorrect matches. However, the incorrect matches will not be
ranked highly if ranked against correct, highly-ranked gallery images. Since
gallery-gallery ranks depend on comparing visual features within the same
domain, the problem is simplified and we are able to extract more
semantically-meaningful matches. This allows initially highly-ranked gallery
images to be penalised and moved down the query-gallery ranked list. Iterating
this process enables discovery of gallery images that are more distantly
connected to the query via multiple gallery-gallery matches.

Figure 1: Re-ranking rationale: (A) is a sketch of an ornate wooden door while
(B) is a modern glass sliding door, these images share almost no visual
similarities, only semantic similarities. Re-ranking at test-time can help
bridge the visual gap by exploiting relationships between same-domain gallery
images (C, D).

We provide a concrete example in Figure 1 for a query sketch against gallery
photos (though note that our approach is not limited to sketch-photo
retrieval). The query sketch of some wooden doors (A) initially assigns a low
rank to the gallery glass doors (B), even though they both belong to the same
class. However, the gallery image of the church doors (C) contains similar
visual features to the sketch (e.g. curved door shape, wooden material). The
church doors contain some similarity to the glass doors (both are within door
frames) however the shape and materials are different and so (B) is ranked
relatively low in the gallery-gallery ranks for (C). However, the gallery
image of the street house doors (D) are similar enough to (C) to be highly
ranked (both contain a wooden door within a door frame) and, in turn, the
house doors (D) are similar enough to the glass doors (B) to be highly ranked
in the gallery-gallery ranks for (D) (rectangular door, within door frame).
Our iterative re-ranking process is able to discover such connections and
raise the rank position of difficult matches such as (B) against a very
different query (A).

The second novel ingredient to our method is the use of cross-attention, i.e.
conditioning attention on one image by another. This is an important mechanism
when working across domains. The ability to relate aspects of one domain to
another allows the model a greater understanding of relationships between the
domains. For example, when human infants are learning a relationship between a
natural image and a representation of that image (this can be sound, sketch,
cartoon, text etc) the two stimuli are often presented at the same time, such
as a child’s book with an image of a cow and a “moo” sound being produced.
Cross-attention allows for this mode of learning to occur. In order for
retrieval to remain tractable at test time, we use knowledge distillation at
training time in order to encourage our model to extract similar features
given only single domain images as are extracted using cross-attention.
Intuitively, this encourages the network to seek features from a query image
that will be useful for retrieving the range of positive matches in the other
domain.

We combine these two contributions with the Vision Transformer [6]
architecture and commonly used losses for zero-shot retrieval. We achieve
state-of-the-art results on the TU-Berlin Extended [7] and Sketchy Extended
[16, 13] datasets as well as showing that the method generalises beyond
sketch-based retrieval using the Office-Home [24] dataset for cartoon-based
retrieval. A full implementation of our method along with pretrained model
weights will be made available upon acceptance.

###  1.1 Related Work

#### ZS-SBIR

Sketch-based image retrieval involves retrieving images from a large gallery
of photos that semantically best match an input query sketch. _Zero-shot_
sketch-based image retrieval (ZS-SBIR) is a special case in which the sketch
and gallery image classes are never seen during train time. The requirement of
zero-shot ensures that the model cannot over-fit to the training set by
learning very specific aspects of classes but instead has to learn the
semantic understanding of how a sketch can relate to an image; making it more
representative of a real-world use case, whereby any category of image could
be presented to the model. To help guide the model into learning a semantic
relationship existing approaches attempt to use a joint representation space,
to bridge the gap between the domains. [8, 5, 14] showcase the use of word
embeddings to generate a semantic link between images but as [23] suggests the
use of word embeddings is not practical for many real-world use cases, with it
being often difficult to describe a whole image by a single word or short
phrase. [20, 32, 26] generate edge-maps from the photographic images to
imitate sketches while [15] utilises a Cycle-GAN [34] to convert the sketches
to a photograph-like modality. The use of edge maps makes the solution task
specific, if sketches were changed to cartoons this method would no longer
work. Both edge maps and GANs also come with the issue of adding extra noise
to the system, either by making a poor choice for which edges to map or by the
GAN not having learnt good enough representations to create accurate images.
Our cross-attention based method aims to create semantic links without the
requirement of extra input generation.

#### Cross-Attention

Within SBIR, cross-attention has been explored [1] but is far from a common
feature used in the field with it being stated in [23] that attention
mechanisms did not yield better results, with it assumed that the model learnt
to pay attention without any extra modules. However, in other research that
pertains to multiple domains [33, 29, 30], cross-attention has proven useful.
[30] in particular show how transformer networks can be adapted to allow for
cross-attention to be directly incorporated into the model to assist the
model’s ability to learn domain relationships. Inspired by the approach of
[30] we show the benefit of using cross-attention within ZS-SBIR.

#### Knowledge Distillation

Knowledge Distillation [9] is a student/teacher approach to learning, with the
teacher generally having a broader knowledge base to attempt to stop the
student, with a narrower knowledge base, overfitting. With the zero-shot
nature of ZS-SBIR it is common for approaches to use models pretrained on
large datasets to ensure “catastrophic forgetting” [12] does not happen. This
attempts to ensure the fine-tuned model keeps a more general understanding
when exposed to never before seen classes. Within SBIR, a common
implementation of knowledge distillation [25, 22, 23] is to use a large
network pretrained on ImageNet [4], a dataset with 1000 classes of diverse
photographic images. While this method of implementation showed promise in
these mentioned works, we did not manage to get any positive impact within our
training pipeline. We hypothesise that this could be due to the teacher
network, only having been exposed to photographs and no other domain, biasing
the model to have greater understanding of this domain compared to the sketch
domain. We present a novel cross-attention method of knowledge distillation
with no requirement of pretrained models. Allowing the model to learn balanced
representations across domains, while not requiring extra training of a
classification layer to bridge the semantic gap between $C_{\text{teacher}}$
and $C_{\text{student}}$, with $C$ representing unique categories.

#### Re-Ranking

SBIR is, in essence, a ranking problem. A model’s success is determined by
whether it can rank images of the same class as a query sketch higher than
images from other classes. Re-ranking is often required during test time when
a sketch only includes detail that may be relevant to a subset of images in a
class but not all, and similarities between classes can only be obtained from
the detailed real-world image domain, presented in Figure 1. Methods of re-
ranking in SBIR commonly utilise clustering of images [26, 27], with the
rationale being that if a model ranks many images from the same cluster
highly, that can be used as an indication that all images in the cluster
should be highly ranked, hence re-ranking occurs and improves the image’s
ranking. Clustering has the shortcoming that it often has to be tuned for
specific use cases. Hyper-parameters such as number of clusters or number of
points per cluster vary the results wildly. If there are too many clusters,
there is a loss of semantic similarity, whereas if there are too few clusters
then the clusters fail to present any meaning. In a cross-domain setting, a
cluster centre of the same class may be far from a query domain image in
visual feature space yet still be semantically related. In this paper we
present a novel re-ranking approach that does not rely on clustering.

#### Vision Transformers

The use of vision transformers has become common practice within computer
vision tasks, originally outlined in [6], they now outperform CNNs in many
different experimental paradigms [2, 3]. Crucially for this work, they have
been shown to outperform CNNs within SBIR also [18]. Their ability to attain
global image-wise attention grants the possibility to look beyond local
features and assess relationships within an image without the relationship
being contiguous. This becomes an important tool when working with images with
little feature description such as a sketch. Sketches are not drawn to be
geometrically accurate but to be representations of what they are trying to
convey. A sketch that contains four legs, a round body and a horn gives a
human enough information to assume that it is a Rhino that has been drawn.
But, without understanding how these features combine in the “bigger picture”,
local attention would just assess that these are four long lines, a circle and
spiky shape and would not comprehend what the sketch is trying to represent.

##  2 Methodology

We begin by formulating the problem and introducing our notations. We then
describe our architecture, the losses used during training and our test-time
re-ranking strategy.

###  2.1 Problem Formulation

Consider a training set of $N$ images
$\mathcal{X}=\\{(x_{i}^{m},y_{i})|y_{i}\in
C_{\text{train}},m\in\\{A,B\\}\\}_{i=1}^{N}$ drawn from two different image
domains, $A$ and $B$. Each training pair comprises an image
$x_{i}^{m}\in\mathbb{R}^{H\times W\times 3}$ and a corresponding class label
$y_{i}$ drawn from a set of possible classes $C_{\text{train}}$. Dissimilarity
between images is defined by a distance function
$d(x_{i}^{m},x_{j}^{m})=\|f_{\theta}(x_{i}^{m})-f_{\theta}(x_{j}^{m})\|_{2}$
which measures Euclidean distance between embeddings of the images by an
embedding function $f_{\theta}:\mathbb{R}^{H\times W\times
3}\rightarrow\mathbb{R}^{D}$ where $D$ is the dimensionality of the embedding,
$\theta$ the parameters of $f$ and $\|f_{\theta}(x_{i}^{m})\|_{2}=1$ (i.e.
embeddings are L2 normalised).

At test time, we are provided with a _query_ image, $x_{q}^{A}$ of domain $A$
and a _gallery_ of $G$ images of domain $B$,
$\mathcal{G}=\\{x_{i}^{B}\\}_{i=1}^{G}$. The goal is to solve this cross-
domain retrieval problem by ranking the gallery images according to similarity
to the query image. In the zero-shot case, the classes of both $x_{q}^{A}$ and
all elements of $\mathcal{G}$ are unknown but are drawn from
$C_{\text{train}}$, with $C_{\text{train}}\cap C_{\text{test}}=\varnothing$ \-
i.e. neither query nor gallery classes have been observed during training.
Each query is treated independently and information cannot be shared between
query images within a test set.

Our objective is to learn the parameters $\theta$ such that the embedded
features perform well for the task of zero-shot, cross-domain retrieval. This
is essentially a metric learning problem.

Figure 2: Overview of architecture and train versus test operation. At
training time, pairs of images are used to compute cross-attention to
supervise the cross-attention distillation loss. At test time, individual
images are embedded and ranked followed by our re-ranking process.

###  2.2 Architecture

In practice, our embedding network is a Vision Transformer (ViT) model [6]. We
modify the architecture to enable cross-attention within the attention layer
of the transformer (inspired by [30]) and add a classification head. Our
architecture is shown in Figure 2 for both train and test time modes of
operation. During training time, we utilise _cross entropy loss_ , _cross-
domain hard example triplet loss_ and our novel _cross-attention knowledge
distillation loss_. During test time we introduce our novel _iterative re-
ranking_ approach to leverage gallery set relationships to improve query-based
gallery retrieval.

###  2.3 Loss Functions

We train the ViT network to minimise a weighted sum of three losses:

$L_{\text{total}}={\lambda_{\text{Triplet}}}L_{\text{Triplet}}+{\lambda_{\text{CaD}}}L_{\text{CaD}}+{\lambda_{\text{CE}}}L_{\text{CE}}$
(1)

where the $\lambda$ are the weights and the individual losses are:

  * •

$L_{\text{Triplet}}$: cross-domain hard example triplet loss;

  * •

$L_{\text{CaD}}$: cross-attention distillation loss;

  * •

$L_{\text{CE}}$: cross entropy loss.

We now describe each of these losses in more detail.

#### Cross-Domain Hard Example Triplet Loss

Triplet loss is commonly used within zero-shot tasks as it allows for metric
learning of a feature space such that a cluster of elements from one class are
far apart from the feature space representations of other classes. It is hoped
that this structure is preserved even for unseen classes. The basic triplet
loss [17] was extended by the MATHM method [10] to better apply to the cross-
domain setting. The idea is to form triplets within domain A and within domain
B but also across domains A and B. This ensures that the model is learning a
feature space representation that clusters within-class and separates between-
class for both domains. Another feature of this loss is that it selects the
hardest examples per iteration. This is to ensure the model is constantly
learning and does not always get triplet sets that it has already managed to
easily separate.

Given anchor (anc), positive class match (pos) and negative class match (neg)
images from both domains, we define the triplet loss in terms of the domains
of the anchor and positive images as:

$L_{\text{T}}(m_{1},m_{2})=\text{ReLU}(D(x^{m_{1}}_{\text{anc}},x^{m_{2}}_{\text{pos}})-D(x^{m_{1}}_{\text{anc}},x^{m_{2}}_{\text{neg}})+\epsilon),$
(2)

where $\epsilon$ is the margin. We then define our cross-domain hard example
triplet loss as the sum of the within and between domain triplets:

$L_{\text{Triplet}}=L_{\text{T}}(A,A)+L_{\text{T}}(B,B)+L_{\text{T}}(A,B)+L_{\text{T}}(B,A).$
(3)

Figure 3: Overview of proposed iterative re-ranking approach. Initial query-
gallery ranks (a) incorporate information from gallery-gallery ranks (b).
Images ranked high in gallery-gallery ranked lists for images with low query-
gallery rank (c) are penalised when distances are updated (d).

#### Cross-Attention Knowledge Distillation Loss

The idea of _cross-attention_ is to condition the attention used to extract
features from one image on another image. For example, if image A only
contains part of an object, whereas image B contains the whole object, the
cross-attention for image B conditioned on A may only attend to the part of
the object visible in A. This can be particularly useful in a cross-domain
setting where, for example, a sketch or cartoon may lack many visual features
present in a photograph of the same class.

Cross-attention is naturally supported as an extension of the self-attention
mechanism in a ViT. Whereas in self-attention the query, key and value all
come from the same image, in cross-attention we use the query from one image
and the key and value of the paired image, i.e.

$F(A,B)=\frac{(Q_{A}K_{B}^{\top})}{\sqrt{d_{k}}}V_{B}.$ (4)

Standard self-attention is then simply a special case of cross-attention in
which both images are the same, i.e. $F(A,A)$.

We use cross-attention at train time. However, at test time, this would
require computing a different set of query features conditioned on every
gallery image, which is computationally expensive. We propose a cheaper test-
time alternative with the additional benefit that it outperforms the more
expensive test time cross-attention. The idea is to use knowledge distillation
to train a self-attention based ViT (the student) to extract similar features
to a cross-attention based ViT (the teacher) that gets to see cross-domain
pairs of images. The intuition is as follows. Consider a query image from a
domain such as sketch or cartoon with cross-attention against photographs. The
teacher network will learn to extract features from one domain that are useful
for matching against the features present in the conditioning image from the
other domain. The student network will learn to extract features that _on
average_ are useful for matching against _typical images from the other
domain_.

Knowledge distillation losses typically operate on the class logits outputted
by a network. In the zero-shot setting, specific classes are less useful and
we instead apply knowledge distillation on self-attention feature space
outputs. Specifically, consider a pair of images $A$ and $B$ from two
different domains, we compute the distillation loss [9] between
$F_{\text{teacher}}(B,A)$ and $F_{\text{student}}(A,A)$ and between
$F_{\text{teacher}}(A,B)$ and $F_{\text{student}}(B,B)$, where $F$ denotes the
feature output from the final self-/cross-attention block. We use a
temperature parameter of $1$.

#### Cross Entropy Loss

Both the triplet loss and distillation loss operate in the feature embedding
space, with reference only to the feature embeddings of the images within the
current mini-batch. This means that these losses do not have access to any
information that is shared between batches. For this reason, we add a
classification head for the classes in $C_{\text{train}}$ and including a
supervised classification cross entropy loss for both domains. We find that
this improves zero-shot performance. Note that the classification head is
discarded at test time and only the feature embedding space used for zero-shot
retrieval.

###  2.4 Test-time Re-ranking

At test time, gallery images are ranked based on their similarity to a query
image. This is done using Euclidean distance to measure dissimilarity in the
image feature embedding space. However, since cross-domain feature comparison
is very difficult, we propose a novel re-ranking scheme which enables correct
class gallery images, that are initially low ranked, to be moved higher up the
ranked list based on gallery-gallery comparisons. Note that the classes of the
query and gallery images remain unknown and we perform re-ranking
independently for each query image.

Method | Dims | TU-Berlin Ext. |  | Sketchy Ext. |  | Sketchy Ext. [31] Split
---|---|---|---|---|---|---
mAP@all | Prec@100 | Prec@200 |  | mAP@all | Prec@100 | Prec@200 |  | mAP@all | mAP@200 | Prec@100 | Prec@200
SBTKNet [31] | 512 | 0.48 | 0.60 | / |  | 0.55 | 0.69 | / |  | / | 0.50 | / | 0.59
SAKE [14] | 64 | 0.475 | 0.599 | / |  | 0.547 | 0.692 | / |  | / | 0.356 | / | 0.477
TVT [21] | 384 | 0.484 | 0.662 | / |  | 0.648 | 0.796 | / |  | / | 0.531 | / | 0.618
NAVE [28] | 512 | 0.493 | 0.607 | / |  | 0.613 | 0.725 | / |  | / | / | / | /
ACNet [15] | 512 | 0.577 | 0.658 | / |  | / | / | / |  | / | 0.517 | / | 60.8
doodle2search [5] | 4096 | 0.109 | / | 0.121 |  | 0.369 | / | 0.370 |  | / | / | / | /
RPKD [22] | 512 | 0.486 | 0.612 | / |  | 0.613 | 0.723 | / |  | / | 0.502 | / | 0.598
PSKD [25] | 384 | 0.502 | 0.662 | / |  | 0.688 | 0.786 | / |  | / | 0.560 | / | 0.645
GTZSR [8] | 256 | 0.703 | 0.779 | 0.790 |  | 0.686* | 0.725* | 0.726* |  | / | / | / | /
OWN [baseline] | 768 | 0.695 | 0.720 | 0.718 |  | 0.777 | 0.810 | 0.806 |  | 0.682 | 0.747 | 0.737 | 0.722
OWN [RE-RANK] | 768 | 0.742 | 0.739 | 0.740 |  | 0.821 | 0.833 | 0.832 |  | 0.750 | 0.776 | 0.773 | 0.764

Table 1: A performance evaluation of our model against SOTA and standard
baseline approaches within ZS-SBIR using TU-Berlin [7] and Sketchy datasets.
We use both common test-set splits suggested for Sketchy. “/” represented
metrics not reported in original published papers. “*” represents when we are
not certain of which Sketchy dataset split the paper used.

Our idea is to iteratively update the query-gallery distances by exploiting
gallery-gallery distances. The updated distances are used to re-rank the
gallery images against the query. The re-ranking process is implemented as
follows:

  1. 1.

Initialise iteration $t:=0$ and distance measure to Euclidean distance in
feature embedding space:

$d^{(0)}(x^{A}_{q},x^{B}_{i}):=\|f_{\theta}(x^{A}_{q})-f_{\theta}(x^{B}_{i})\|_{2}$

  2. 2.

Pre-compute all gallery-gallery distances in feature embedding space,
$D(x^{B}_{i},x^{B}_{j})$, $\forall x^{B}_{i},x^{B}_{j}\in\mathcal{G}$, and,
for every gallery image, rank every other gallery image in ascending order of
distance. $r_{ij}$ is the rank of gallery image $j$ against gallery image $i$.

  3. 3.

Rank gallery images against query in ascending order using current query-
gallery distance measure $d^{(t)}(\cdot,\cdot)$. $r^{(t)}_{qi}$ is the rank of
gallery image $i$ against query.

  4. 4.

Update query-distances by adding penalties that depend on previous query-
gallery ranking as well as gallery-gallery ranks:

$d^{(t+1)}(x^{A}_{q},x^{B}_{i}):=\\\
d^{(t)}(x^{A}_{q},x^{B}_{i})+\beta\sum_{j=1}^{M}\alpha[r^{(t)}_{qi}]\gamma
r_{ji}\|f_{\theta}(x^{B}_{i})-f_{\theta}(x^{B}_{j})\|_{2},$ (5)

where $\alpha$ is a function that take ranks as input and returns a scale:

$\alpha[r]=\begin{cases}0.01r&\text{if }r\leq K\\\
1.0&\text{otherwise}\end{cases}.$ (6)

$\gamma$ scales the influence of gallery-gallery ranks, we use $\gamma=0.01$.
$\beta$ weights the overall influence of re-ranking on the original distances,
we use $\beta=0.1$. $K$ is a parameter beyond which query-gallery ranks incur
a high penalty - we use $K=16$.

  5. 5.

If not converged, set $t:=t+1$ and return to step 3.

An overview of our re-ranking method is shown in Figure 3. In the example
shown, the initial query-gallery ranking (a) places an incorrect match high in
the list (marked in red). For every gallery image, we now consider their
gallery-gallery ranks (b). In (c) we highlight the positions of two highly
ranked examples in the other gallery ranked lists. Item 3 is an incorrect
match. This is indicated by the fact that it appears high in the ranked list
of gallery images that are themselves ranked low against the query (items 150
and 151). This will incur a high penalty for item 3 in its updated distance to
query. Item 4 however is a correct match and this is indicated by appearing
high in the ranked list of gallery images that are themselves ranked high
against the query (items 1, 2 and 5). This will incur a small penalty for item
4. Once the distances have been updated, we re-rank (d) and the incorrect
match moves further down the query-gallery ranked list.

##  3 Experiments

Figure 4: Examples showing result of re-ranking. For each query sketch the top
row relates to the original output while the row below is the re-ranked
output. Correct matches are shown in green, incorrect in red.

#### Datasets

We evaluated our methodology on Sketchy Extended and TU-Berlin Extended, two
commonly used datasets for the task of ZS-SBIR. The original Sketchy dataset
[16] contained 12,500 photographic images and 75,479 sketch images covering
125 different classes. [13] extended this dataset, adding another 60,502
photographic images bringing their total to 73,002. [19] randomly selected 25
classes to set as a test set, however as [31] noted, some of these classes
have crossover with classes within ImageNet [4] and since it is common
practice for models within SBIR to be initialised with weights pretrained on
ImageNet, it did not match the zero-shot assumption. Hence, they propose a
test set of 21 classes, carefully selected to not match image classes within
ImageNet to assert models are tested in as close to a zero-shot manner as
possible. Both of these test setups will be evaluated on for this paper. TU-
Berlin [7] contains 204,489 photographic images and 20,000 sketch images
covering 250 different classes. Following, [19], 30 classes are selected to be
a test set.

#### Metrics

In accordance with most state-of-the-art baseline implementations we will
report both the mean Average Precision at k (mAP@k) and Precision at k
(Prec@k) results. Due to the longevity of this topic of research, rank
thresholds for which to measure the mAP and Prec have changed. We try to
report all variations of k that appear in other work to give a consistent
evaluation.

#### Implementation Details

We initialised our ViT model with pretrained ImageNet weights and used
patchsizes of 14x14 and feature dimensions of 768. An Adam [11] optimiser was
employed with a weight decay of 0.0005. All pretrained layers are set to have
a learning rate of 0.00001 while additional layers are initialised with a
learning rate of 0.0001 Trained for 80 epochs (6400 iterations) with a
batchsize of 80 used. We employ a “mixup” strategy each epoch to change image
pairings throughout training, giving the model a wide variation of examples.

###  3.1 Baseline Comparisons

We report the ZS-SBIR performance of our approach against both state of the
art and standard baseline implementations in Table 1. Our approach outperforms
on almost all baseline metrics, except for precision within TU-Berlin. Our mAP
on TU-Berlin dataset outperforms baseline by 4%, due to TU-Berlin on average
having around 930 images per class within the test set this shows our re-
ranking is successfully improving the rank of many of the correct instances
but not getting as many within the top 200 to beat previous results.

| SAKE - Sketchy Ext. [31] |  | Own Model - Office-Home
---|---|---|---
mAP@all | Prec@100 |  | mAP@all | Prec@25
Baseline | 0.470 | 0.621 |  | 0.723 | 0.777
Re-Ranking | 0.546 | 0.672 |  | 0.790 | 0.767

Table 2: Cols 2-3: Improvement of SAKE [14] model output on Sketchy Ext. [13] with our proposed Re-Ranking method. Cols 4-5: Office-Home [24] dataset improvement with our proposed Re-Ranking method. Triplet Loss | Cross Attention | Re-Ranking | TU-Berlin Ext. | Sketchy Ext. | Sketchy Ext. [31] Split
---|---|---|---|---|---
mAP@all | Prec@100 | mAP@all | Prec@100 | mAP@all | Prec@100
N | N | N | 0.553 | 0.635 | 0.621 | 0.722 | 0.459 | 0.555
Y | N | N | 0.693 | 0.720 | 0.776 | 0.808 | 0.681 | 0.735
Y | Y | N | 0.695 | 0.720 | 0.777 | 0.810 | 0.682 | 0.737
Y | Y | Y | 0.742 | 0.739 | 0.821 | 0.833 | 0.750 | 0.773
Table 3: Ablation study showcasing impact of components. Figure 5: Examples
showing result of Office-Home re-ranking. For each query sketch the top row
relates to the original output while the row below is the re-ranked output.
Correct matches are shown in green, incorrect in red.

###  3.2 Ablation Study

In this section we evaluate the contribution of different components within
our proposed method as well as analysing how our model across different image
domains and how our re-ranking method can act as a “plug-in” to other
retrieval implementations and improve test time results.

#### Different Image Domains

A consideration throughout our research development was that we did not want
our solution to be only applicable for sketches and photographs. Real-world
situations could involve retrieving the best gallery images from all sorts of
image query domains. One domain of image we focus on in this ablation study is
cartoon imagery. Office-Home [24] includes photographic images and cartoons.
We use our re-ranking approach to confirm that our method is not only
applicable to sketches and photographs but can be used to get high retrieval
success from other domains. For this experiment we split the 65 classes into
55 classes for train and 10 classes for test, doing our upmost to ensure test
classes were as far removed from ImageNet classifications as possible. Due to
this being a small dataset there were only around 70 images per class so we
report results on mAP@all and Prec@25. Presented in Table 2 cols 4-5, we show
a large increase in mAP@all results ($\sim$7%) as well as a smaller but still
significant increase in Prec@25 ($\sim$2%). Example results shown in Fig. 5

#### Impact of Components

In Table 3, we assess the impacts of the main components of our
implementation. Our Cross-Attention Knowledge Distillation gives a minor
improvement on all datasets, allowing the model to make slightly better cross
domain representations that if it was not included. Our Re-ranking approach
gives a large increase of around 5-7% on the benchmark datasets. This
highlights the approaches ability to bridge the semantic gap between sketch
and images.

#### Re-ranking with Another Model

We designed our re-ranking method to be able to be applied and improve results
from any method within SBIR. To highlight this we choose the seminal SAKE [14]
implementation and compare baseline outputs with the outputs of our re-ranking
module. Table 2 cols 2-3 shows the improvement gained from using our re-
ranking, with a greater-than 7% mAP improvement.

##  4 Conclusions

We propose both a novel train time method and test time method for retrieval
tasks across different domains. We showcase the success of our method within
the zero-shot sketch-based image retrieval task while emphasising the
versatility of our method within the ablation studies. We utilise cross-
attention within the model to present a method of knowledge distillation that
does not require a pretrained model with its inherent bias. During test time
we showcase how a non-cluster based re-ranking method can exploit semantic
relationships within-domain to improve cross-domain ranking. We observe our
model being competitive against ZS-SBIR baselines across multiple datasets
with all mAP@all metrics being beaten by a significant margin. With regards to
future work, the information within patches of the model output could be
leveraged to have more specific feature space relationships between images
rather than only comparing spatially averaged features. This could allow for a
better semantic understanding of what elements of an image are important for
representing the category of the image.

## References

  * [1] Ushasi Chaudhuri, Biplab Banerjee, Avik Bhattacharya, and Mihai Datcu.  Crossatnet-a novel cross-attention based framework for sketch-based image retrieval.  Image and Vision Computing, 104:104003, 2020.
  * [2] Bowen Cheng, Ishan Misra, Alexander G Schwing, Alexander Kirillov, and Rohit Girdhar.  Masked-attention mask transformer for universal image segmentation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1290–1299, 2022.
  * [3] Stéphane Cuenat and Raphaël Couturier.  Convolutional neural network (cnn) vs vision transformer (vit) for digital holography.  In 2022 2nd International Conference on Computer, Control and Robotics (ICCCR), pages 235–240. IEEE, 2022.
  * [4] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In 2009 IEEE conference on computer vision and pattern recognition, pages 248–255. Ieee, 2009.
  * [5] Sounak Dey, Pau Riba, Anjan Dutta, Josep Llados, and Yi-Zhe Song.  Doodle to search: Practical zero-shot sketch-based image retrieval.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 2179–2188, 2019.
  * [6] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  In International Conference on Learning Representations, 2021.
  * [7] Mathias Eitz, James Hays, and Marc Alexa.  How do humans sketch objects?  ACM Transactions on graphics (TOG), 31(4):1–10, 2012.
  * [8] Sumrit Gupta, Ushasi Chaudhuri, Biplab Banerjee, and Saurabh Kumar.  Zero-shot sketch based image retrieval using graph transformer.  In 2022 26th International Conference on Pattern Recognition (ICPR), pages 1685–1691. IEEE, 2022.
  * [9] Geoffrey Hinton, Oriol Vinyals, and Jeff Dean.  Distilling the knowledge in a neural network.  stat, 1050:9, 2015.
  * [10] Zongheng Huang, Yifan Sun, Chuchu Han, Changxin Gao, and Nong Sang.  Modality-aware triplet hard mining for zero-shot sketch-based image retrieval.  arXiv preprint arXiv:2112.07966, 2021.
  * [11] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  arXiv preprint arXiv:1412.6980, 2014.
  * [12] James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Grabska-Barwinska, et al.  Overcoming catastrophic forgetting in neural networks.  Proceedings of the national academy of sciences, 114(13):3521–3526, 2017.
  * [13] Li Liu, Fumin Shen, Yuming Shen, Xianglong Liu, and Ling Shao.  Deep sketch hashing: Fast free-hand sketch-based image retrieval.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2862–2871, 2017.
  * [14] Qing Liu, Lingxi Xie, Huiyu Wang, and Alan L Yuille.  Semantic-aware knowledge preservation for zero-shot sketch-based image retrieval.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 3662–3671, 2019.
  * [15] Hao Ren, Ziqiang Zheng, Yang Wu, Hong Lu, Yang Yang, Ying Shan, and Sai-Kit Yeung.  Acnet: Approaching-and-centralizing network for zero-shot sketch-based image retrieval.  IEEE Transactions on Circuits and Systems for Video Technology, 2023\.
  * [16] Patsorn Sangkloy, Nathan Burnell, Cusuh Ham, and James Hays.  The sketchy database: learning to retrieve badly drawn bunnies.  ACM Transactions on Graphics (TOG), 35(4):1–12, 2016.
  * [17] Florian Schroff, Dmitry Kalenichenko, and James Philbin.  Facenet: A unified embedding for face recognition and clustering.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 815–823, 2015.
  * [18] Omar Seddati, Stéphane Dupont, Saïd Mahmoudi, and Thierry Dutoit.  Transformers and cnns both beat humans on sbir.  arXiv preprint arXiv:2209.06629, 2022.
  * [19] Yuming Shen, Li Liu, Fumin Shen, and Ling Shao.  Zero-shot sketch-image hashing.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3598–3607, 2018.
  * [20] Jianqiang Sheng, Fei Wang, Baoquan Zhao, Junkun Jiang, Yu Yang, and Tie Cai.  Sketch-based image retrieval using novel edge detector and feature descriptor.  Wireless Communications and Mobile Computing, 2022, 2022.
  * [21] Jialin Tian, Xing Xu, Fumin Shen, Yang Yang, and Heng Tao Shen.  Tvt: Three-way vision transformer through multi-modal hypersphere learning for zero-shot sketch-based image retrieval.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 2370–2378, 2022.
  * [22] Jialin Tian, Xing Xu, Zheng Wang, Fumin Shen, and Xin Liu.  Relationship-preserving knowledge distillation for zero-shot sketch based image retrieval.  In Proceedings of the 29th ACM International Conference on Multimedia, pages 5473–5481, 2021.
  * [23] Osman Tursun, Simon Denman, Sridha Sridharan, Ethan Goan, and Clinton Fookes.  An efficient framework for zero-shot sketch-based image retrieval.  Pattern Recognition, 126:108528, 2022.
  * [24] Hemanth Venkateswara, Jose Eusebio, Shayok Chakraborty, and Sethuraman Panchanathan.  Deep hashing network for unsupervised domain adaptation.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 5018–5027, 2017.
  * [25] Kai Wang, Yifan Wang, Xing Xu, Xin Liu, Weihua Ou, and Huimin Lu.  Prototype-based selective knowledge distillation for zero-shot sketch based image retrieval.  In Proceedings of the 30th ACM International Conference on Multimedia, pages 601–609, 2022.
  * [26] Luo Wang, Xueming Qian, Xingjun Zhang, and Xingsong Hou.  Sketch-based image retrieval with multi-clustering re-ranking.  IEEE Transactions on Circuits and Systems for Video Technology, 30(12):4929–4943, 2019.
  * [27] Luo Wang, Xueming Qian, Yuting Zhang, Jialie Shen, and Xiaochun Cao.  Enhancing sketch-based image retrieval by cnn semantic re-ranking.  IEEE transactions on cybernetics, 50(7):3330–3342, 2019.
  * [28] Wenjie Wang, Yufeng Shi, Shiming Chen, Qinmu Peng, Feng Zheng, and Xinge You.  Norm-guided adaptive visual embedding for zero-shot sketch-based image retrieval.  In IJCAI, pages 1106–1112, 2021.
  * [29] Xiyu Wang, Pengxin Guo, and Yu Zhang.  Domain adaptation via bidirectional cross-attention transformer.  arXiv preprint arXiv:2201.05887, 2022.
  * [30] Tongkun Xu, Weihua Chen, WANG Pichao, Fan Wang, Hao Li, and Rong Jin.  Cdtrans: Cross-domain transformer for unsupervised domain adaptation.  In International Conference on Learning Representations, 2021.
  * [31] Sasi Kiran Yelamarthi, Shiva Krishna Reddy, Ashish Mishra, and Anurag Mittal.  A zero-shot framework for sketch based image retrieval.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 300–317, 2018.
  * [32] Yu-Wei Zhan, Xin Luo, Yongxin Wang, Zhen-Duo Chen, and Xin-Shun Xu.  Three-stream joint network for zero-shot sketch-based image retrieval.  arXiv preprint arXiv:2204.05666, 2022.
  * [33] Fuzhong Zheng, Weipeng Li, Xu Wang, Luyao Wang, Xiong Zhang, and Haisu Zhang.  A cross-attention mechanism based on regional-level semantic features of images for cross-modal text-image retrieval in remote sensing.  Applied Sciences, 12(23):12221, 2022.
  * [34] Jun-Yan Zhu, Taesung Park, Phillip Isola, and Alexei A Efros.  Unpaired image-to-image translation using cycle-consistent adversarial networks.  In Proceedings of the IEEE international conference on computer vision, pages 2223–2232, 2017.

## Appendix

### Iterative Behaviour of Re-ranking

As mentioned, our re-ranking method is an iterative approach; updated ranks
are used to recompute the query-gallery distances which in turn update the
ranks. In Figure 6 we illustrate the iterative behaviour of re-ranking. We
plot the mAP@all performance metric for Office-Home versus the number of
iterations of re-ranking. Observe that the ranking (and hence metric)
converges by around 600 iterations with most of the improvement concentrated
in the first 20 iterations.

### Further Examples of ZS-SBIR Results with Re-ranking

In Figure 7 and Figure 8 we showcase some further results of our re-ranked
top-10 retrieval. Figure 7 highlights some of the successes of our re-ranking
approach on the TU-Berlin dataset. One particular example to draw attention to
is the sketch of a horse (located at the bottom of the figure). The model has
assessed this sketch as being very similar to the handgun, ranked in 7th
place, for understandable reasons. The handgun shares a very similar shape to
that of the sketched horse head, but very little similarity with the highly
ranked photographs, so our re-ranking method successfully moves this incorrect
image out of the top 10 rankings.

Figure 8 shows failure cases of our re-ranking method where it actually harms
retrieval performance of the model. Our re-ranking is less successful when
only a small subset of the top results are correctly ranked, weighting the
very top examples more highly in its re-ranking method. However, as the top
example (banana sketch) shows, even when the top 2 are correct the method can
still fail to improve the rankings. This could be due to these images not
having many photo domain similarities with photos of the same class so the re-
ranking fails to move any of the same class up the ranks and, in fact, moves
some of the correct class examples down the ranked list.

Figure 6: Convergence of re-ranking approach.

Figure 7: Extended examples of re-ranking improving ranking with TU Berlin
dataset. For each query sketch the top row relates to the original output
while the row below is the re-ranked output. Correct matches are shown in
green, incorrect in red Figure 8: Examples of re-ranking harming the ranking
with TU Berlin dataset. For each query sketch the top row relates to the
original output while the row below is the re-ranked output. Correct matches
are shown in green, incorrect in red


# Characterization of the Firm-Firm Public Procurement Co-Bidding Network from
the State of Ceará (Brazil) Municipalities

Marcos Lyra  Tribunal de Contas do Estado do Ceará, Rua Sena Madureira,
60055-080, Fortaleza, Brazil  NOVA Information Management School (NOVA IMS),
Universidade Nova de Lisboa, Campus de Campolide, 1070-312 Lisboa, Portugal
António Curado  NOVA Information Management School (NOVA IMS), Universidade
Nova de Lisboa, Campus de Campolide, 1070-312 Lisboa, Portugal  Bruno Damásio
NOVA Information Management School (NOVA IMS), Universidade Nova de Lisboa,
Campus de Campolide, 1070-312 Lisboa, Portugal  Fernando Bação  NOVA
Information Management School (NOVA IMS), Universidade Nova de Lisboa, Campus
de Campolide, 1070-312 Lisboa, Portugal  Flávio L. Pinheiro  NOVA Information
Management School (NOVA IMS), Universidade Nova de Lisboa, Campus de
Campolide, 1070-312 Lisboa, Portugal<EMAIL_ADDRESS>
###### Abstract

Fraud in public funding can have deleterious consequences for the economic,
social, and political well-being of societies. Fraudulent activity associated
with public procurement contracts accounts for losses of billions of euros
every year. Thus, it is of utmost relevance to explore analytical frameworks
that can help public authorities identify agents that are more susceptible to
incur in irregular activities. Here, we use standard network science methods
to study the co-biding relationships between firms that participate in public
tenders issued by the $184$ municipalities of the State of Ceará (Brazil)
between 2015 and 2019. We identify $22$ groups/communities of firms with
similar patterns of procurement activity, defined by their geographic and
activity scopes. The profiling of the communities allows us to highlight
groups that are more susceptible to market manipulation and irregular
activities. Our work reinforces the potential application of network analysis
in policy to unfold the complex nature of relationships between market agents
in a scenario of scarce data.

Public Procurement; Network Analysis; Data Mining; Co-bidding Network; Brazil

††preprint: TBD

## Introduction

Despite the weight of public procurement in governmental budgets [1], it is
still one of the activities that is most vulnerable to corruption [2, 3]. In
that context, corruption can have many forms [4] and occur at any point in the
procurement cycle—from the pre-tendering to the tendering and the past-award
phases—making it difficult to detect and measure [5, 6, 7]. In Brazil alone,
corruption in procurement contracts can represent an additional $20\%$ to
$30\%$ of the expected price, which represents losses of around 200 billion
Reais annually [8]. Likewise, in Europe, it is estimated that losses are of
around 5B Euros annually [9]. Naturally, these losses undermine the ability of
governments and public authorities to push-forward essential investments in
health, education, infrastructure, security, housing, and social services [10,
11]. Unsurprisingly, there is a considerable effort to develop analytical
solutions to understand and mitigate the effects of corruption in the public
procurement process [12]. Recently, the increasing availability of open data
concerning public administration activities [13] has renewed the scientific
community’s efforts on uncovering the hidden connections between participating
agents and how their relationships can link to fraudulent activities [14, 15].

One of the most challenging aspects of identifying corruption in the context
of public procurement contracts is related to the lack of labeled data. Hence,
it is often impossible to know which instances correspond to corruption [16].
In that sense, past works have approached this problem from an unsupervised
learning perspective, meaning that they look to extract from the data more
information about the relationships between the involved parties and, thus,
flag groups of agents with patterns associated with a high risk of corruption.
In that sense, a fundamental principle in public procurement is that of
transparency in bidding [17, 4, 18, 19]. In that sense, competition leads to
greater efficiency for the public sector. As such, firms that developed the
necessary relationships to achieve leverage to manipulating a tender process
at a high risk of corrupting the procurement process [20].

Figure 1:  Panel a), graphical representation of the process employed to infer
the Firm-Firm co-bidding network. Panel b), comparison between the frequency
of bidders per tender in the original data set (gray) and in the working data
set (red) after filters have been applied. Panel c), comparison between the
frequency of bids per firm in the original data set (gray) and in the working
data set (red) after filters have been applied. In panel b) and c) dashed line
represents the OLS regression lines, the domain of the line indicates the
domain used for fitting the curve.

An open issue remains, can the communities identified from firms co-biding
patterns allow us to highlight groups of firms that are more susceptible to
collusion and market manipulation? The use of network analysis for the study
of corruption is not new [21, 22, 23]. In the context of public procurement,
past studies can be divided into two main groups: 1) works that explore
bipartite relationships between public bodies and firms [24, 25]; and 2)
studies that explore firm-firm co-biding relationships in public tenders [26,
27, 28, 29]. Both approaches have their merits, and each is more suitable to
identify different mechanics underlying the manipulation of the procurement
process. For instance, bipartite relationships are suitable to identify fraud
that stems from bribes and influence ties; while firm-firm relationships are
more suited to identify cartels and collusion. Despite these, the use of
network analysis to study the relationship between firms in procurement bids
is a relatively new venture [27], and more evidence is required in order to
have a clear picture of the universality of existing patterns and mechanics
across cultural and socio-economic contexts.

Here, we use methods from network science and complexity sciences to map and
characterize the co-bidding network [16, 30, 31, 27] between firms that
participated in public tenders issued by the $184$ municipalities of the state
of Ceará (Brazil). In that sense, we provide a characterization of the
relationships between competing firms and identify the major communities of
firms that often compete for tenders with similar scope. Moreover, we argue
that some of such communities have characteristics that place them at a higher
risk of market manipulation and irregular activities often associated with
corruption.

## Data

We use data from Tribunal de Contas do Estado Ceará (Brazil) covering public
tenders issued by the 184 municipalities of the State of Ceará between 2015 to
2019. Each observation informs about the bid of a firm to a tender and whether
the bid was one of the winning bids. It also includes information about the
municipality that issued the tender, and whether a firm won a contract. Hence,
the data is naturally represented through a bipartite nature [32], which
connects firms to tenders (see Figure 1a). The data set contains $196,608$
observations that account for the bids of $45,502$ firms to $84,835$ tenders.

Information about the firms and tenders is anonymized, and bidding values are
not available. Moreover, the data set does not contain information about which
contracts/firms have been investigated in the past for irregularities.

## Network Inference

Since we are interested in studying the relationships between firms we focus
on the Firm-Firm projection. We estimate the projection from the co-bidding
patterns of firms [30] using the Jaccard similarity coefficient [33, 34, 35,
16]. Figures 1a shows a graphical illustration of the structure of the data
and depicts the steps conducted in order to infer the Firm-Firm network from
the original Tender-Firm bipartite structure.

In order to infer the Firm-Firm co-bidding network, we start by discarding all
firms that did not bid at least once during each year of analysis. By doing
so, we are able to extract the core of active firms, while removing firms with
sporadic activity. Figure 1b and 1c compare the original ($P_{\text{ALL}}$)
with the filtered data set ($P_{\text{Sample}}$). In particular, showing that
filtering tends to remove excess participants from tenders, while it does not
affect the distribution of the number of bids done by each firm. Likewise, we
refer to firms present in the firm-firm co-biding network as Established
firms. The final working data set includes $1,906$ firms, which account for
$72,078$ bids to $39,523$ tenders.

Figure 2: Panel a) shows the degree distribution, $D(k)$. The dashed black
line represents the best exponential distribution fitted to the tail ($k>5$)
of the empirical distribution. Panel b) shows the average clustering
coefficient average per degree, $C(k)$. The dashed black line shows the best
linear fit. Results have been estimated from the entire graph.

Hence, next, we compute the centered Jaccard coefficient [35] is between each
pair of firms, which can be computed as:

$J^{c}_{ij}=\frac{\sum_{k}b_{it}b_{jt}}{\sum_{k}(b_{it}+b_{jt}-b_{it}b_{jt})}-\frac{p_{i}p_{j}}{p_{i}+p_{j}-p_{i}p_{j}},$
(1)

where $b_{ik}$ is one if if firm $i$ made a bid to tender $t$, being zero
otherwise; and $p_{i}$ is the fraction of tenders in which firm $i$
participated ($p_{i}=\sum_{k}b_{it}$. The second term in Equation 1 provides
the expected number of observations when the bids from both firms are
independent and identically distributed through a Bernoulli process [35].
Hence, the centered Jaccard coefficient allows us to distinguish between
positive and negative associations between firms.

Finally, we estimate the significance of the computed $J^{c}_{ij}$ (i.e., to
test the hypothesis that $J^{c}_{ij}>0$). To that end, we bootstrap a null
distribution ($\hat{J}_{ij}$) of centered Jaccard coefficient for each by
generating an ensemble of $1000$ randomizations of the initial bipartite
network. Data was randomized in order to ensure that the number of bids
observed per firm and per year remained constant while keeping constant the
number of firms bidding to each tender. Then, using statistical inference
methods [36], we estimate the p-value associated with $J^{c}_{ij}$ by
calculating the upper tail probability of obtaining a value equal or greater
than $J^{c}_{ij}$ from the cumulative frequency of the null-distribution
$\hat{J}_{ij}$. We discard links with $p$-value $>0.05$.

Figure 3: Graphical representation of the Firm-Firm network, which relates
firms with similar bidding pattern. In order to build the network we consider
only the most active firms, and edges with a significant Jaccard similarity
index. Represented is the giant component with some relevant disconnected
components. Nodes in the giant component are colored according to one of the
eight major communities (out of $22$) identified using the Louvain algorithm
[37]. The presented partition of the network achieves a modularity of $0.61$.

The resulting firm-firm co-bidding network contains $1,529$ nodes and $12,892$
edges. Relationships are treated as undirected and unweighted, identifying
firms that have a similar pattern of bidding. The network exhibits an average
degree of $16.86$, with a cluster coefficient of $0.52$ [38], and $56$
connected components. Figure 2 shows the Degree Distribution (panel 2a) decays
exponentially with the degree. Meaning that the underlying mechanics of co-
bidding can be approximated with a random attachment process [39]. However,
the average clustering coefficient shows an inverse relationship with the
degree (panel 2b), suggesting the existence of some level of hierarchy in the
structure of the network. It is noteworthy to mention that the largest
connected component contains $1,141$ nodes, $10,630$ edges, and a clustering
coefficient of $0.43$.

## Results and Discussion

Figure 3 presents the giant component of the firm-firm co-bidding network. In
particular, we highlight the eight largest communities (nodes are colored
accordingly). Using the Louvain algorithm [37] we identified $22$ communities
with a modularity of $0.66$. We refer to these communities as $C_{1}$,
$C_{2}$,…,$C_{22}$, whose index is ordered in descending order to the number
of firms in the communities. The high modularity of the network is, however,
unsurprisingly and can be explained by the fact that the network represents
firms in different markets characterized by the different nature of contracts
(e.g., works, services, etc) in different regions. As indicated in Figure 3,
the largest communities divide the network into two major groups of firms that
operate mostly in the northern (Red, Blue, and Green) and south (Purple and
Yellow) regions of the state of Ceará, but also on contracts that deliver Food
services (Blue and Purple) or construction works (Red and Yellow).
Interestingly, the remaining communities highlighted identify firms that
compete at state-wide level (Pink and light Blue) and one particular instance
of a community (Violet) operating in a small region (Jaguaribe) and a single
contract type (Food services). Hence, the network highlights competing markets
and provides a characterization that is interpretable.

As discussed above, communities in Firm-Firm network structures can be used to
identify market segments. In limiting scenarios, cases in which firms form
”echo chambers” or highly dense communities, it also allows us to flag groups
of firms that present a high risk of collusion and procurement manipulation.
In other words, corruption. As such, next, we explore the use of network
science as an approach to classify the communities of firms that might be of
interest to investigate deeper by the authorities of interest.

Figure 4: Characterization of the ten largest communities by the diversity of
bids done by region and type. Panel a) shows the distribution of bids within
each community by geographical region (left) and contract/tender type (right).
For each community we compute the Simpson’s diversity index
($\lambda_{\text{reg}}$ and $\lambda_{\text{serv}}$). Panel b) compares
communities by their diversity of contracts in terms of regional span and
type. Note that in panel a) we only show results for the ten largest
communities, which are representative of the results. Communities not
identified by a color code in Figure 2 are shown in gray in panel b), in the
particular community $C_{14}$ corresponds to the gray clique easily
identifiable in the bottom left of the network in Figure 3.

### Activities Diversity

We start by looking at the regional diversity on which firms performed their
activities (e.g., bid on tenders), and also the diversity of the type of
contracts that they bid to. While a firm with low diversity in both regional
reach and contract-type can simply indicate a firm that is narrow in both
scope and domain, the existence of clear groups (i.e., a community of firms)
that share such indicator can highlight more a troublesome scenario. In
particular, it can indicate the conditions for firms to coordinate and
cooperate to control a specific market in a specific regional context, and
should be investigated with further care. To that end, we start by estimating
the Simpson’s diversity index111In some fields the Simpson’s index is also
known as the Herfindahl index. for each community, which can be computed as

$\lambda^{C_{i}}_{\text{cat}}=\sum_{t\in\gamma}(p_{C_{i}}^{t})^{2}$ (2)

where $p_{C_{i}}^{t}$ corresponds to the fraction of bids done in a
procurement contract of type $\gamma:${Consumables Health, Services,
Construction, Events, Food, Fuel,…} or regions type $\gamma:${Metropolinana,
Norte, Sul, Noroeste,…} by the firms in community $C_{i}$, $\forall
i\in\\{1,2,...,21,22\\}$. The quantity $p_{C_{i}}^{t}$ is normalized per
community, so that $\sum_{t}p_{C_{i}}^{t}=1.0$. We estimate
$\lambda^{C_{i}}_{\text{cat}}$ independently for each community ($C_{i}$), and
for contracts according to the region that issue the tender and the tender
contract type (e.g., services, food, tenancy, constraction, etc). Our choice
of the Simpson’s index over other alternatives (e.g., entropy) is due to its
straightforward interpretation: the probability that two bids from a community
are in the same category (e.g., region or contract type).

Figure 4a illustrates the empirical distributions ($p_{C_{i}}^{t}$) of
procurement activity for the ten largest communities. We show the results for
both the Regional distribution of activities and by Contract Type. Blue colors
denote a low relative frequency of bids, while red identifies a high
frequency. These indicators allow us to infer the degree of specialization and
agglomeration of a community. In particular, we find that Community 8
($C_{8}$) activities are agglomerated in a single region (Jaguaribe) and firms
specialize in one type of contract (Food). The same conclusion can also be
inferred from the high levels of $\lambda^{C_{8}}_{\text{cat}}$, which means
that Community 8 has low diversity of activity distribution. Figure 4b
compares all the $22$ communities in terms of the two diversity indicators
defined above. We find a clustering of communities in the bottom left
quadrant— a low level of agglomeration and specialization—that we associate
with healthy markets composed of firms that, on average, have a diversified
portfolio of activities and regional distribution. In contrast, in the top
right quadrant, we find communities that rely on procurement contracts of a
single type and agglomerated in a small number of regions.

The combination of these two diversity indicators, at the community level,
provides a powerful feature to identify groups of firms that can dominate over
a niche market or, in the worst case, develop undesirable leverage, as a
group, in negotiating procurement contracts. Hence, lowering the desirable
efficiency that public procurement aims at achieving in the tendering process.
However, it is important to stress that these metrics are just indicative of
potential problems, and thus the true nature of the activities of the firms in
each community should be carefully investigated by the corresponding local
authorities.

### Bidding Coordination

Figure 5: Characterization by bidding activity. Panel a) shows the average
number of single bids per community (i.e., the average of the number of times
a firm in a community participated in a tender as the single bidder). We
compare the values of each company with the average of the entire population
of firms (horizontal red line). Panel b) shows the average number of bidders
in tenders that firms within a community typically participates. We normalize
the value obtained for each community by the number of firms in that
community. The horizontal red line shows the threshold that marks the size of
the community

To further investigate the risk/susceptibility of market manipulation by
firms, we next look at the propensity that each community has in participating
in ”single bidder” contracts. Another pattern often associated with corruption
and loss of efficiency. Hence, what is the susceptibility of each community to
such practice? To answer that question, we start by investigating the average
number of times, per community, that a firm is the single bidder of a tender.
Figure 5a shows the results for all $22$ communities in the largest component
of the Firm-Firm network. Traditionally a higher level of single bidders would
be the main indicator of market manipulation. However, at the community level,
both very low and very high levels are indicative of unusual activity. In
particular, if we set as a baseline number of single bids by a typical firm.
The reason being that low levels indicate the risk of coordination (e.g.,
firms participating coherently in the same contracts) while high levels can
sign the prevalence of less competitive markets. Overall, of the largest 10
communities, only Community 8 exhibits low levels of single bidders, a pattern
extended to Communities 14 and 21 as well.. In contrast, we see that community
12 strongly deviates from the average with average value of single bidding
that is roughly four times larger than the average.

In addition, it is important to look at the average number of bidders per
tender in order to assess the potential existence of coherent behavior, that
is, coordination between the firms in a community. To that end, for each
community, we estimate the average number of bids per tender, which we
normalize by the size of the community (i.e., the number of firms in a
community). Interestingly, Figure 5b shows that in Community 8 firms
participated tend to participate in tenders with a number of participating
firms that matches almost exactly the size of the community. While, in some
cases—Communities 14 and 19—the numbers are several times larger. Noteworthy
to mention that this analysis is biased by the size of the communities, so the
expectation would be to see a smoothly increasing relationship, with the
largest community achieving the smallest value, and in the limiting case of a
community with a single firm we would obtain the maximum. However, it is clear
that in some cases–Communities 8, 14, and 19– there are clear deviations.

## Conclusions

In this manuscript, we explore the potential of mining a large data set of
public tenders collected from the activity of firms to compete for procurement
contracts issued by the municipalities of the State of Ceará (Brazil). By
matching firms with similar bidding patterns, we have inferred a firm-firm
network comprising a total of $1,141$ nodes and $10,630$ edges.

We show that we are able to identify communities of firms with similar bidding
patterns. The network exhibits a high modular structure partitioned in $22$
communities. These communities cluster firms that have a similar scope in
procurement activity both in the nature of the contracts they celebrate and in
the regional reach of their activities. Moreover, we look at two diversity
indicators—regional diversity and procurement contract nature diversity—as a
sign of the potential of certain communities to develop leverage over the
procurement process. In other words, in affecting the expected efficiency of
the market. Finally, we look at the sizes of the tenders, first by looking at
the abundance of single bidders in communities, and secondly by looking at the
average number of bidders in each tender. Overall we have identified on a
particular community (Community 8) that combines several undesirable
properties. Community 8 involves a group of firms that offers Food services in
the region of Jaguarabe. They have an unusually low number of single bids; the
average number of participating firms per tender matches the number of firms
in the community, and they exhibit a high specialization and agglomeration in
their activities.

Finally, it is important to highlight some shortcomings in our analysis and
future working directions. The lack of pre-labeled data on past cases of
corruption largely limited our ability to make any causal link between the
network structure, its motifs, and the location of firms in the network with
irregular procurement behavior. In that sense, our results are merely
exploratory and show the potential of combining network science methods with
descriptive statistics to highlight relevant groups of firms according to
their activity pattern in a data-scarce environment. Future works should look
at the evolution of the network, that is, if a larger temporal window is
available, to capture the evolution and segregation of communities of interest
but also of their parametric path in terms of the diversity of their
activities.

## Acknowledgments

MSL was financially supported by Tribunal de Contas do Estado do Ceará through
a Phd scholarship. BD, FLP, and FB acknowledge the financial support provided
by FCT Portugal under the project UIDB/04152/2020 - Centro de Investigação em
Gestão de Informação (MagIC). The authors are thankful to Tribunal de Contas
do Estado do Ceará for sharing the data for this study. The authors are
thankful to Cristian Candia for the useful discussions and insights. The
findings, interpretations, and conclusions expressed by the authors in this
work do not necessarily reflect the views of the Tribunal de Contas of Ceará.

## References

  * [1] Oecd.stat.: Government at a glance—2017 edition: public procurement, https://stats.oecd.org/Index.aspx?QueryId=78413, accessed: 2021-03-14.
  * Murray [2014] J. G. Murray, Procurement fraud vulnerability: a case study, EDPACS the EDP audit, control and security newsletter 49, 7 (2014).
  * OECD [2015] OECD, Preventing corruption in public procurement, https://www.oecd.org/gov/public-procurement/integrity/ (2015).
  * Angulo Garzaro [2018] N. Angulo Garzaro, Eu competition law and public procurement: Competition-driven limits imposed to public bodies when they source goods, works and services, Works and Services (April 9, 2018) (2018).
  * Mufutau [2016] O. V. Mufutau, G. O. nad Mojisola, Detection and prevention of contract and procurement, fraud crtalyst to organization profitability, Journal of Business and Management 18, 09 (2016).
  * Rustiarini  _et al._ [2019] N. Rustiarini, T. Sutrisno, N. Nurkholis, and W. Andayani, Why people commit public procurement fraud? the fraud diamond view, Journal of Public Procurement 19, 345 (2019).
  * Whiteman [2019] R. Whiteman, Fraud and corruption tracker, The Chartered Institute of Public Finance and Accountancy – CIPFA (2019).
  * Zeferino [2020] L. F. Zeferino, A corrupção na construção de edifícios públicos no brasil: análise de instrumentos inibidores e facilitadores na etapa de projeto arquitetônico, (2020).
  * Hafner  _et al._ [2016] M. Hafner, J. Taylor, E. Disley, S. Thebes, M. Barberi, M. Stepanek, and M. Levi,  _The Cost of Non-Europe in the Area of Organised Crime and Corruption: Annex II-Corruption_ (RAND, 2016).
  * Søreide [2002] T. Søreide,  _Corruption in public procurement. Causes, consequences and cures_ (Chr. Michelsen Intitute, 2002).
  * Beittel  _et al._ [2019] J. S. Beittel, P. Meyer, and et al.,  _Combating Corruption in Latin America: Congressional Considerations_ (Congressional Research Service, 2019).
  * Fazekas  _et al._ [2018] M. Fazekas, L. Cingolani, and B. Tóth, Innovations in objectively measuring corruption in public procurement, in  _Helmut K. Anheier, Matthias Haber, Mark A. Kayser (Eds.). Governance Indicators. Approaches, Progress, Promise._ (Oxford, UK: Oxford University Press, 2018) Chap. 7, pp. 154–185.
  * Curado  _et al._ [2020] A. Curado, B. Damásio, S. Encarnação, C. Candia, and F. L. Pinheiro, Scaling behavior of public procurement activity, arXiv preprint arXiv:2007.15276 (2020).
  * Herrera [2019] M. D. Herrera, Using social network analysis in open contracting data to detect corruption and collusion risks, Eindhoven University of Technology - Department of Mathematics and Computer Science (2019).
  * Kertész and Wachs [2021] J. Kertész and J. Wachs, Complexity science approach to economic crime, Nature Reviews Physics 3, 70 (2021).
  * Wachs and Kertész [2019] J. Wachs and J. Kertész, A network approach to cartel detection in public auction markets, Scientific reports 9 (2019).
  * Adjei-Bamfo  _et al._ [2019] P. Adjei-Bamfo, T. Maloreh-Nyamekye, and A. Ahenkan, The role of e-government in sustainable public procurement in developing countries: A systematic literature review, Resources, Conservation and Recycling 142, 189 (2019).
  * Nowrousian [2019] B. Nowrousian, Combatting public procurement criminality or simple rules for complex cases, Journal of Financial Crime (2019).
  * Spagnolo [2012] G. Spagnolo, Reputation, competition, and entry in procurement, International Journal of Industrial Organization 30, 291 (2012).
  * Hanák and Serrat [2018] T. Hanák and C. Serrat, Analysis of construction auctions data in slovak public procurement, Advances in Civil Engineering 2018 (2018).
  * Lauchs  _et al._ [2011] M. Lauchs, R. Keast, and N. Yousefpour, Corrupt police networks: uncovering hidden relationship patterns, functions and roles, Policing & society 21, 110 (2011).
  * Chang [2018] Z. Chang, Understanding the corruption networks revealed in the current chinese anti-corruption campaign: A social network approach, Journal of Contemporary China 27, 735 (2018).
  * Grassi  _et al._ [2019] R. Grassi, F. Calderoni, M. Bianchi, and A. Torriero, Betweenness to assess leaders in criminal networks: New evidence using the dual projection approach, Social Networks 56, 23 (2019).
  * Fazekas and Tóth [2016] M. Fazekas and I. J. Tóth, From corruption to state capture: A new analytical framework with empirical applications from hungary, Political Research Quarterly 69, 320 (2016).
  * Wachs  _et al._ [2019] J. Wachs, T. Yasseri, B. Lengyel, and J. Kertész, Social capital predicts corruption risk in towns, Royal Society open science 6, 182103 (2019).
  * Toth  _et al._ [2014] B. Toth, M. Fazekas, A. Czibik, and I. Toth, Toolkit for detecting collusive bidding in public procurement with examples from hungary, Corruption Research Center Budapest (2014).
  * Reeves-Latour and Morselli [2017] M. Reeves-Latour and C. Morselli, Bid-rigging networks and state-corporate crime in the construction industry, Social Networks 51, 158 (2017).
  * Morselli and Ouellet [2018] C. Morselli and M. Ouellet, Network similarity and collusion, Social Networks 55, 21 (2018).
  * Wachs  _et al._ [2020] J. Wachs, M. Fazekas, and J. Kertész, Corruption risk in contracting markets: A network science perspective, International Journal of Data Science and Analytics , 1 (2020).
  * Piccolo  _et al._ [2018] S. Piccolo, S. Lehmann, and A. Maier, Design process robustness: a bipartite network analysis reveals the central importance of people, Design Science 4 (2018).
  * Ramalho  _et al._ [2020] H. M. B. Ramalho, A. T. C. Almeida, and A. A. Fraga, Detection of suspected collusion cases in public biddings: an application of the a priori machine learning algorithm for the state of paraiba, in  _Teroria e Prática em Administração - TPA_ , Vol. 10 (2020) pp. 5–22, 2nd ed.
  * Fierăscu [2017] S. I. Fierăscu, The networked phenomenon of state capture: Network dynamics, unintended consequences, and business-political relations in hungary, Central European University (2017).
  * Veech [2013] J. A. Veech, A probabilistic model for analysing species co-occurrence, Global Ecology and Biogeography 22, 252 (2013).
  * Mainali  _et al._ [2017] K. P. Mainali, S. Bewick, P. Thielen, T. Mehoke, F. P. Breitwieser, S. Paudel, A. Adhikari, J. Wolfe, E. V. Slud, D. Karig, _et al._ , Statistical analysis of co-occurrence patterns in microbial presence-absence datasets, PLoS One 12, e0187132 (2017).
  * Chung  _et al._ [2019] N. C. Chung, B. Miasojedow, M. Startek, and A. Gambin, Jaccard/tanimoto similarity test and estimation methods for biological presence-absence data, BMC bioinformatics 20, 1 (2019).
  * Gotelli [2000] N. J. Gotelli, Null model analysis of species co-occurrence patterns, Ecology 81, 2606 (2000).
  * Blondel  _et al._ [2008] V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre, Fast unfolding of communities in large networks, Journal of statistical mechanics: theory and experiment 2008, P10008 (2008).
  * Newman  _et al._ [2020] M. E. Newman, G. T. Cantwell, and J.-G. Young, Improved mutual information measure for clustering, classification, and community detection, Physical Review E 101, 042304 (2020).
  * Albert and Barabási [2002] R. Albert and A.-L. Barabási, Statistical mechanics of complex networks, Reviews of modern physics 74, 47 (2002).
  * Note [1] In some fields the Simpson’s index is also known as the Herfindahl index.