# Leveraging Habitat Information for Fine-grained Bird Identification

Tin Nguyen 111footnotemark: 1 Anh Nguyen 2
Auburn University
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Traditional bird classifiers mostly rely on the visual characteristics of
birds. Some prior works even train classifiers to be invariant to the
background, completely discarding the living environment of birds. Instead, we
are the first to explore integrating habitat information, one of the four
major cues for identifying birds by ornithologists, into modern bird
classifiers. We focus on two leading model types: (1) CNNs and ViTs trained on
the downstream bird datasets; and (2) original, multi-modal CLIP [31].
Training CNNs and ViTs with habitat-augmented data results in an improvement
of up to +0.83 and +0.23 points on NABirds and CUB-200, respectively.
Similarly, adding habitat descriptors to the prompts for CLIP yields a
substantial accuracy boost of up to +0.99 and +1.1 points on NABirds and
CUB-200, respectively. We find consistent accuracy improvement after
integrating habitat features into the image augmentation process and into the
textual descriptors of vision-language CLIP classifiers. Code is available at:
https://anonymous.4open.science/r/reasoning-8B7E/.

##  1 Introduction

Test Accuracy on NABirds

Zero-shot Accuracy on NABirds

(Ours) Visual [3] \+ Habitat [3]Visual [3]CLIP [31]

Figure 1: Top: CNN trained on with habitat-augmented data improves accuracy by
+0.83 pts over original data. Bottom: Adding habitat descriptions to CLIP
boosts zero-shot accuracy, exceeding visually-based or class name-only
descriptions by +0.99 pts and +1.90 pts, respectively (details in Tab. 1, 3,
and 4). Note that, both models are tested on NABirds.

Bird identification, despite recent progress, continues to be challenging,
particularly in distinguishing between species with similar appearances, such
as various sparrow species [40]. A promising feature that can address the
issue is habitat, which is recognized as one of four keys to identifying birds
by bird watchers and ornithologists [11, 6, 5]. This is exemplified by species
like the Scott Oriole and Evening Grosbeak (Fig. 2), which are visually
similar but inhabit distinct environments: The former nest and forage in
deserts or cactus flats, whereas the latter breed in pine-oak, pinyon-juniper,
and aspen forests [3].

Early works focus on finding the most discriminative features of birds, giving
rise to part-based models [48, 22, 45]. More recent efforts have expanded to
include additional information like geolocation [10, 24, 37] and textual
descriptions [20, 12] to enhance identification accuracy. [43] made
preliminary efforts to emphasize the significance of background for
classification. Additionally, other researchers have approached the problem by
focusing on habitat classification [42, 16].

Acadian Flycatcher | Least Flycatcher
---|---
(a) Swamp | (b) Edges of Woods

Scott Oriole | Evening Grosbeak
---|---
(c) Desert | (d) Pine-oak Tree

Figure 2: Visual comparison of two bird pairs with similar morphologies but
different habitats: Acadian Flycatcher in swamps vs. Least Flycatcher in
woodland edges; Scott Oriole in deserts vs. Evening Grosbeak in pine-oak
areas. See Appendix Sec. A3.1 for details.

However, to our best knowledge, no prior works explored how to leverage
habitat information to improve bird identification accuracy. Our study
addresses this research gap by introducing novel methodologies for integrating
habitat information into both vision-only and vision-language models,
broadening the scope of bird identification techniques. For vision-only
models, we introduce a technique of superimposing bird images onto their
relevant habitat backgrounds, creating habitat-augmented data for training
purposes. In the vision-language model context, we specifically tailor the
text input to include relevant habitat information, a targeted approach that
contributes to improved accuracy in bird recognition.

In this work, we aim to assess how habitat information influences the
performance of both vision-only and vision-language models in bird
identification. We focus on evaluating two prominent vision-only models,
ResNet-50 [19] trained by [36], and TransFG [18] with a Vision Transformer
(ViT) [14] backbone, each augmented with habitat-specific data. Additionally,
for a vision-language approach, we examine the CLIP model [31], adding habitat
details to textual prompts. This methodology aims to highlight the potential
of habitat integration in enhancing model accuracy, offering a comprehensive
analysis of its impact on ornithological machine learning.

As highlighted by allaboutbirds.org, a leading resource in avian studies,
critical attributes for identifying bird species include shape & size, color
pattern, behavior, and habitat. Consistent with these attributes, our study
demonstrates that the integration of habitat data consistently improves the
performance of both vision-only and vision-language models in bird
identification, thereby validating the significance of this approach. To the
best of our knowledge, our work is the first to demonstrate the effectiveness
of habitat information in bird identification. Our main findings are:

  * •

State-of-the-art vision-only models can be improved in accuracy when training
with habitat-augmented images (_e.g_., +0.23 pts in NABirds for ResNet-50 as
shown in Tab. 1).

  * •

The addition of habitat descriptions to the CLIP model significantly boosts
its zero-shot and few-shot accuracy, with increases of up to +1.1 and +4.63
points respectively (Tabs. 3, 4 and 5).

  * •

State-of-the-art models struggle with images lacking habitat information, such
as FlyBird images. In the NABirds dataset, Non-FlyBird images outperform
FlyBird by +6.92 points in vision-only and +4.10 points in vision-language
models, emphasizing the crucial role of habitat data (Tabs. 6 and 7).

##  2 Related Work

Current methods in fine-grained bird classification have two main branches:
vision-only models, which focus on augmenting visual information through
innovative architectural designs, and vision-language models (VLMs), which
integrate external textual knowledge as an additional modality. Exploring
these branches in detail reveals distinct methodologies and their evolution in
bird classification.

#### Utilizing visual features in vision-only models

Early methods in fine-grained bird classification primarily explored visual
features, such as zooming into particular regions [15], extracting certain
visual features [48, 22, 45]. recent approaches have advanced this field by
concentrating on bird-specific parts or concepts to both enhance and explain
the classification process [18, 28, 13, 27, 32, 44]. These methods have
intensively focused on avian characteristics, yet notably, they have not
incorporated habitat information into their classification frameworks.

#### Adding extra information as another modality

Incorporating additional data types, such as geolocation and time of
observation, has proven beneficial in fine-grained bird classification.
Researchers have found that geographical information, in particular, can
significantly improve classification accuracy [10, 24, 12]. Recently, Visual
Language Models (VLMs) like CLIP [31], FILIP [46], and CoCa [47], which
combine visual and textual data, have shown promising results. These models,
pretrained on large-scale datasets [33, 34], perform comparably to specialized
fine-grained classifiers. [26] found that the foundation model CLIP [31] can
be further amplified by adding more descriptive textual descriptions. However,
these methods have yet to fully explore the use of habitat information, a key
factor in bird identification [7, 25, 38, 1, 2].

#### Background Information

Several studies have emphasized the influence of background in image
classification. For instance, [43] found that changing backgrounds can
significantly affect model accuracy, as models exploit background
correlations. Similarly, [49] demonstrated enhanced object recognition
performance by combining networks trained on both the foreground object and
the background context. In a different approach, [41] developed a contrastive
learning method to mitigate background bias. Building on top of these
insights, our research takes a distinct path by explicitly emphasizing the
recognition of habitat elements in bird identification, an aspect pivotal yet
needs to be explored in the field.

#### Habitat Classification

While [42] conducted a study on recognizing habitat elements in bird images,
their approach did not directly apply this information to bird species
identification. Instead, they developed a classifier for categorizing
different types of habitats, such as stone, water, leafless areas, or trunks.
Our approach, however, diverges significantly. We integrate habitat
information into our dataset through augmentation, enriching the data
associated with each bird species. This strategy allows our model to leverage
habitat context, making more informed and accurate identification decisions.

##  3 Methods

This section presents our proposed habitat-based data augmentation for vision-
only models in Sec. 3.1. Then, we propose a simple approach to include habitat
into bird descriptions for the foundation model CLIP Sec. 3.2.

OriginalAugmented

Mixed-S

Mixed-G Mixed-I

Figure 3: Three augmentation techniques (Mixed-S, Mixed-G, Mixed-I) are
illustrated: Original bird images in the first column, followed by augmented
versions. The first row shows Common Yellow Throat in varying habitats (marsh
to grassland). The second row features it amidst different species sharing the
same habitats. The last row demonstrates Mixed-Irrelevant, placing Black
Footed Albatross (typically found near shores) in forest and grass
backgrounds. Figure 4: Bird classification with vision-only models (CNN, ViT)
utilizes augmented datasets blending original and habitat-augmented images.
The augmented images have more contextual habitat, for instance, the habitats
of Painted Bunting and Scott Oriole are dense brush and arid foothills.

###  3.1 Improve Habitat Understanding in Vision-Only Models with Habitat-
augmented Data

For vision-only models, we evaluate the effectiveness of our habitat-based
augmentation methods on two representative models (Fig. 4): ResNet-50 [36] for
CNN and TransFG [36] for ViT, which employs ViT-B/16 [14] as its backbone.

We introduce three augmentation methods: Mixed-Same(Mixed-S) and Mixed-
Group(Mixed-G), inspired by [43, 17], aimed to enhance habitat diversity.
Moreover, Mixed-Irrelevant(Mixed-I), designed to reduce habitat correlation
with birds, serves as a control in evaluating the impact of habitat diversity
on bird identification.

The essence of our augmentation approach lies in isolating the bird from an
image and seamlessly integrating it into a distinct habitat image. To achieve
this, we generate two specialized image collections. The first, Only Bird
Images, in which birds against a uniform black background; the second, Habitat
Images, images of avian environments with birds removed by LaMa [35]. We
provide an example of these images in Fig. 6. Subsequently, these curated sets
allow us to overlay the Only Bird Images onto the Habitat Images. This
superimposition can include habitats that are either congruent with the bird’s
class, aligned with its broader taxonomic group, or derived from an entirely
different grouping.

#### Mixed-Same (Mixed-S)

We randomly change the background of a bird within its class, this method is
inspired by previous works [43, 17]. Specifically, this entails superimposing
each “Only Bird Image” onto a corresponding “Habitat Image” that shares the
same class index. This process ensures that the bird is depicted against a
variety of backgrounds that are class-consistent, thereby enriching the
dataset with diverse, yet relevant, environmental contexts. An example of this
process for the Common Yellow Throat and Black-footed Albatross is given in
Fig. 3.

#### Mixed-Group (Mixed-G)

In light of the fact that certain avian species share habitats, our approach
involves categorizing birds into clusters based on the similarity of their
environmental settings, concretely, we use k-means [23] to cluster birds into
groups based on their habitat descriptions sourced from allaboutbirds.org[3]
(see algorithm details in Appendix Secs. A2 and A3). This insight has led to
the development of a novel augmentation technique, termed Mixed-Group, which
strategically superimposes each “Only Bird Image” onto a “Habitat Image”
within the same ecological group.

For instance, as illustrated in the second row in Fig. 3, the Common Yellow
Throat is placed onto different habitats of a group including Orange-crowned
Warbler, Savannah Sparrow, Groove-billed Ani, and Florida Jay, these birds
share the same habitat preference for deciduous shrub environments.

We provide some details of habitat groups according to habitat descriptions in
Appendix Sec. A2.

#### Mixed-Irrelevant (Mixed-I)

To understand the importance of habitats to bird recognition, a bird will be
isolated from its own habitat or habitat group and placed into a completely
irrelevant one. In Mixed-Irrelevant, we randomly choose a habitat image from
all classes that are not in the habitat groups of a specific bird to do image
augmentation. Mixed-Irrelevantinjects irrelevant habitat to the training
images, therefore enforcing the model to utilize the bird information only. As
can be seen from Fig. 3, after augmentation, the Black-footed Albatross is
placed in a forest which is completely unnatural because its habitats are on
low, sandy islands, or near shore, and far offshore.

###  3.2 Habitat Understanding in Multimodal Models

Figure 5: Integrating habitat data into CLIP during zero-shot enhances bird
identification. Each class comes with descriptions; CLIP calculates and
averages similarity scores between these and the input image. The class with
the highest softmax score is then predicted.

In terms of multimodal models, we use CLIP (Fig. 5) and investigate its zero-
shot capability in the presence of supplementary habitat descriptions.

Previously, M&V [26], or PEEB [4] employed fine-grained descriptions generated
by LLMs as input prompts to CLIP. Although these descriptors provide rich
information about bird appearance such as color, or shape, they still lack
descriptors describing habitat.

Motivated by this, we employ habitat descriptors sourced from
allaboutbirds.org[3], providing valuable insights into the environments where
each bird species thrives.

##  4 Results

OriginalBlack BackgroundNo BirdBlack BoxesBig Box

Figure 6: Five test scenarios assess model robustness with variations: no
habitat (black background), habitat only (no bird), and obscured bird images.

To establish the broad applicability and impact of the habitat, we evaluate
vision-only models across diverse test sets (refer to Fig. 6) and assess
CLIP’s performance with various description sets (detailed in Sec. 4.2). All
tests were performed using PyTorch [30] on a single NVIDIA V100 GPU.

Table 1:  Accuracy comparison across various CUB and NABirds test sets using ResNet-50 [36] and TransFG [18] models shows Mixed-Sameand Mixed-Group’s effectiveness, especially in challenging scenarios like No Birds, Small Boxes, and Big Box, indicating superior utilization of habitat information. Test Data |  ResNet-50 [36] |  TransFG (ViT/B-16) [18]
---|---|---
Baseline |  Mixed-I | Mixed-G | Mixed-S | Baseline |  Mixed-I | Mixed-G | Mixed-S
CUB (200 classes) | Standard | 86.81 |  86.26 (-0.55) |  87.04(+0.23) | 87.02 | 89.18 |  88.89 (-0.29) | 89.25 |  89.39(+0.21)
No Background | 76.08 |  78.94(+2.86) | 77.8 | 76.75 | 81.74 |  86.99(+5.25) | 86.05 | 85.54
No Birds | 5.51 | 3.45 | 5.29 |  5.99(+0.48) | 6.02 | 5.99 | 4.85 |  6.68(+0.66)
Small Boxes | 75.39 | 72.85 | 74.61 |  75.01 (-0.38) | 86.9 | 87.57 | 87.06 |  87.78(+0.88)
Big Box | 60.41 | 58.84 | 60.7 |  61.10(+0.69) | 77.42 | 77.56 | 77.25 |  78.98(+1.56)
NABirds (555 classes) | Standard | 80.23 |  79.21 (-1.02) |  81.06(+0.83) | 80.72 | 88.42 |  87.76 (-0.66) | 88.67 |  88.75(+0.33)
No Background | 65.18 |  69.18(+4.00) | 67.14 | 67.36 | 80.83 |  85.99(+5.16) | 84.83 | 84.32
No Birds | 3.77 | 1.64 | 3.35 |  3.81(+0.04) | 7.34 | 3.69 | 6.72 |  8.09(+0.75)
Black Boxes | 61.5 | 59.77 | 61.67 |  61.82(+0.32) | 85.21 | 84.48 | 85.37 |  85.47(+0.26)
Big Box | 51.48 | 49.06 |  51.81(+0.33) | 51.76 | 76.67 | 74.60 | 76.41 |  77.66(+0.99)

#### Dataset used in vision-only models

We train and test models on splits of CUB and NABirds, infusing habitat
information into the training process using Mixed-S and Mixed-G methods. Test
outcomes are recorded in Tab. 1.

We also verify the advantage of habitats by testing trained models on the
iNaturalist-birds dataset (1048 classes) featuring several challenges such as
birds being partially occluded, or low lighting conditions (Fig. 7).
Consequently, we derived two subsets, iNaturalist-CUB (200 classes) and
iNaturalist-NABirds (555 classes), to facilitate focused evaluations (see Tab.
4), specifically:

  * •

iNaturalist-CUB which includes 200 classes, with 144 overlapping classes both
presenting in iNaturalist-birds and CUB and 56 classes sourced from CUB only.

  * •

iNaturalist-NABirds which includes 555 classes, with 247 overlapping classes
both presenting in iNaturalist-birds and NABirds and 308 classes sourced from
NABirds only.

Note that, images of overlapping classes are from iNaturalist-birds, while
images of non-overlapping classes are sourced from either CUB or NABirds.

The objective is to determine whether habitat information improves
identification in real-world conditions where birds are occluded or appear
diminutive. The results are detailed in Tab. 2.

Dryocopus Martius (Black Woodpecker)

Pelecanus Crispus (Dalmatian Pelican)

Figure 7: Examples in iNaturalist-birds [39] where the birds Dryocopus Martius
(Black Woodpecker) and Pelecanus Crispus (Dalmatian Pelican) being partially
occluded by trees, poor lighting conditions, and the diminutive size of the
bird.

#### Dataset used in CLIP

CUB, NABirds, and iNaturalist-birds are used to test the performance of CLIP
with a keen focus on the role of habitat information. Habitat details for
dataset classes are meticulously sourced from allaboutbirds.org, a reputable
avian resource.

For CUB, which consists of 200 classes, comprehensive habitat information is
directly obtained for 183 classes. For the remainder, we utilize GPT-3 to
generate the missing habitat data.

In the case of NABirds, the original 555 classes are streamlined to 267
classes for testing. This exclusion arises due to incomplete visual
descriptions for classes that have variations like males, females, and
juveniles.

Lastly, in iNaturalist-birds, out of 1486 classes, habitat information is
successfully gathered for 425 classes, corresponding to the data available on
allaboutbirds.org.

The impact of incorporating habitat descriptions on CLIP’s zero-shot accuracy
for CUB, NABirds, and iNaturalist-birds is shown in Tabs. 3 and 4.

###  4.1 Habitat Information consistently improves classification accuracy of
vision-only models

To investigate the hypothesis that applying habitat-based augmentation
(Mixed-S and Mixed-G) enhances the accuracy of bird identification, we trained
unimodal models, which are ResNet-50 [36], and TransFG [18], with and without
the augmentation strategies, and compare the models trained with augmentations
against their non-augmented counterpart across different test sets of CUB and
NABirds as illustrated in Fig. 6.

Furthermore, to investigate the robustness of our models under complex
conditions - where birds may be partially obscured, or hidden by objects (see
Fig. 7), we tested them on the challenging iNaturalist-CUB and iNaturalist-
NABirds datasets as described in Sec. 4.

#### Experiment

First, we resize input images to 256*256. We fine-tune ResNet-50 from [36]
using a batch size of 64 and a learning rate of $1e^{-4}$ over 20 epochs. For
TransFG [18], we employed a batch size of 8, maintained the learning rate at
$1e^{-5}$, and extended training to 50 epochs. Adam [21] optimizer is employed
with a step learning rate scheduler. The pre-trained models are provided in
Sec. A1. In this experiment, three augmentation techniques Mixed-S, Mixed-G,
and Mixed-I will be compared. For each type of augmentation, we test it with
different test sets, as depicted in Fig. 6, there are five types of test sets:

  * •

Original: Original test sets of CUB or NABirds.

  * •

Black background: Removing the background of the original set.

  * •

No Bird: Crop the birds in the original set and use LaMa [35] to fill in the
cropped region.

  * •

Black Boxes: Put eight small black boxes on the birds.

  * •

Big Box: Put a big black box on the birds.

#### Results

The results in Tab. 1 show that the models trained with Mixed-S and Mixed-G
augmentations consistently enhance the accuracy of bird identification which
means habitat backgrounds really help in bird recognition. Concretely, using
Mixed-G increases the accuracy by +0.23 and +0.83 points compared to not using
any habitat augmentation methods when training ResNet-50 [36] on CUB, and
NABirds, respectively. While training ViT [18] on those datasets, Mixed-S also
gains +0.21, and +0.33 points. Although the gaps are not substantial, they
still suggest that classifiers trained on habitat-augmented datasets might be
more effective at identifying birds.

The results in Tab. 2 also suggest that models trained with Mixed-G and
Mixed-S consistently achieve the highest accuracy on iNaturalist-CUB and
iNaturalist-NABirds. Concretely, in iNaturalist-CUB, there is an average
improvement of +0.76 points in accuracy, while the improvement in iNaturalist-
NABirds is +0.48 points. This shows that in those cases, habitat background
plays an important role in identifying a bird.

Table 2: Performance comparison on iNaturalist-CUB and iNaturalist-NABirds using VisualCorr [36] and TransFG [18] shows Mixed-Groupand Mixed-Sameoutperform Baselineby +0.76 and +0.48 points, respectively, due to added ’habitat’ in training. |  iNaturalist-CUB (200 classes) |  iNaturalist-NABirds (555 classes)
---|---|---
| ResNet-50 | TransFG | ResNet-50 | TransFG
Baseline | 68.23 | 71.38 | 68.59 | 77.93
Mixed-I | 68.17 | 71.45 | 66.95 | 76.39
Mixed-G | 68.49 |  72.5 (+1.12) |  69.03 (+0.44) | 78.25
Mixed-S |  68.62 (+0.39) | 71.89 | 68.63 |  78.45 (+0.52)
Avg $\Delta$ | +0.76 | +0.48

###  4.2 Improving Zero-shot and Few-shot Accuracy with the help of Habitat
Description

To assess habitat efficacy in CLIP, we compare the zero-shot and few-shot
accuracies across CUB (200 classes), NABirds (267 classes), and iNaturalist-
birds (425 classes) both with and without integrating habitat descriptions
into the visual concepts for each category.

#### Experiment

We augment each set of textual descriptions with habitat information, and
examine the improvement of CLIP models. Additionally, in the few-shot context,
our methodology involves the addition of 30 images for each class,
specifically chosen at random from the training dataset.

Note that, we obtain the visual appearance descriptions from three sources,
specifically:

  * •

M&V [26] utilizes GPT-3 [8] to generate visual descriptions of birds.
Sometimes it includes abstract features that are not presented in the image,
such as "This is a medium-sized bird", or "wingspan of up to 3.6 m (12 ft)".
(Appendix A3)

  * •

PEEB [4] leverages GPT-4 [29] to generate descriptions of twelve distinct
parts of birds including wings, tail, eyes, back, forehead, nape, crown, leg,
breast, throat, belly, beak. (Appendix A3)

  * •

Shape, Size, and Color (SSC) [3] descriptions are human-annotated descriptions
and are available on the allaboutbirds.org. (Appendix A3)

Furthermore, in order to be consistent between scientific class names in the
iNaturalist-birds dataset (see Fig. 7), and the common bird names in the
habitat description, we initially substitute common names in habitat
descriptions with their corresponding scientific names. Subsequently, we
inverted this process by replacing the scientific class names with common
names. This approach was based on the premise that CLIP may not effectively
recognize birds’ scientific nomenclature, potentially impairing its accuracy
in generating prompts that contain such terminology.

Motivated by [26], we also modify the standard CLIP input prompt "A photo of a
{c}". into "{c}, which (is/has/etc) {description}." where "{c}" is a class
name. Subsequently, the modified prompts can be fed into CLIP’s text encoder.

#### Results

We conduct comparisons of zero-shot and few-shot accuracy, considering the use
of descriptions with and without habitat information. The results, as
presented in Tabs. 3, 4 and 5, clearly demonstrate that incorporating habitat
descriptions leads to a notable improvement in both settings. For instance, in
the zero-shot context, the combination of Shape, Size, and Color (SSC) and
habitat achieves +1.1 and +0.99 pts improvement in CUB and NABirds,
respectively. Similarly, for the few-shot setting, using M&V descriptions with
habitat also gains +4.63 and +1.09 pts in these two datasets.

Table 3: Zero-shot accuracy on CUB and NABirds with M&V, PEEB, and SSC
descriptions in CLIP models shows habitat integration boosts accuracy across
all descriptions. Average gains with habitat in SSC are +1.1 for CUB and +0.99
for NABirds. Notably, adding habitat to M&V descriptions in CLIP outperforms
class names alone by +2.73 points. CUB (200 classes)
---
|  CLIP [31] |  M&V [26] |  PEEB [4] |  SSC [3]
Habitat | ✗ | ✗ | ✓ | ✗ | ✓ | ✗ | ✓
B/32 | 51.95 | 52.35 | 53.56 | 52.73 | 53.16 | 52.43 | 53.02
B/16 | 56.35 | 57.51 | 58.56 | 57.92 | 58.5 | 57.02 | 58.63
L/14 | 63.08 | 64.03 | 64.27 | 64.31 | 65.17 | 63.81 | 64.91
Avg | 57.96 | 58.80 | 58.32 | 58.94 | 57.75 | 58.85
$\Delta$ | +0.83 | +0.62 | +1.1
NABirds (267 classes that do not have annotation)
B/32 | 49.08 | 49.79 | 51.17 | 50.61 | 51.25 | 49.84 | 50.84
B/16 | 55.28 | 57.29 | 58.06 | 56.87 | 57.59 | 56.12 | 57.07
L/14 | 63.86 | 66.56 | 67.17 | 66.73 | 67.33 | 64.98 | 66.01
Avg | 57.88 | 58.80 | 58.07 | 58.72 | 56.98 | 57.97
$\Delta$ | +0.92 | +0.65 | +0.99
Table 4: Zeroshot Accuracy on iNaturalist-birds (425 classes) in two settings:
common names to scientific names and vice versa. The results show habitat
descriptions enhance zero-shot accuracy across all description sets, with
common names notably yielding higher accuracy. iNaturalist21 - only bird (425
classes, common names to scientific names)
---
| CLIP |  M&V [26] |  PEEB [4] |  SSC [3]
Habitat | ✗ | ✗ | ✓ | ✗ | ✓ | ✗ | ✓
B/32 | 4.22 | 5.92 | 6.83 | 5.21 | 5.80 | 8.72 | 8.84
B/16 | 5.36 | 7.76 | 9.08 | 6.61 | 7.58 | 10.85 | 11.32
L/14 | 7.94 | 11.29 | 13.08 | 9.09 | 10.26 | 14.07 | 14.89
Avg | 8.32 | 9.66 | 6.97 | 7.88 | 11.21 | 11.68
$\Delta$ | +1.34 | +0.91 | +0.47
iNaturalist21 - only bird (425 classes, scientific names to common names)
B/32 | 29.56 | 30.52 | 30.67 | 30.13 | 30.47 | 29.46 | 30.08
B/16 | 35.41 | 36.75 | 37.24 | 36.48 | 37.00 | 35.15 | 36.59
L/14 | 43.54 | 45.47 | 45.93 | 45.51 | 45.90 | 43.74 | 45.03
Avg | 37.58 | 37.95 | 37.37 | 37.79 | 36.12 | 37.23
$\Delta$ | +0.37 | +0.42 | +1.12
Table 5: Few-shot accuracy on CUB and NABirds with M&V, PEEB, and SSC
descriptions in CLIP models, reveals habitat integration enhances accuracy for
all sets. Notably, habitat in M&V descriptions improves by +4.63 for CUB and
+1.09 for NABirds. CUB (200 classes)
---
Description | B/32 | B/16 | L/14 |  Avg $\Delta$
PEEB [4] +Habitat | 59.39 | 71.51 | 78.13 | +1.25
62.93 (+3.54) |  71.66 (+0.15) |  78.18 (+0.05)
M&V [26] +Habitat | 46.43 | 55.02 | 63.24 | +4.63
50.38 (+3.95) |  59.1 (+4.08) |  69.09 (+5.85)
SSC [3] +Habitat | 58.75 | 69.16 | 76.94 | +0.56
59.37 (+0.62) |  69.76 (+0.60) |  77.39 (+0.45)
NABirds (267 classes that do not have annotation)
PEEB [4] +Habitat | 57.29 | 67.65 | 76.06 | +0.19
57.55 (+0.26) |  67.77 (+0.12) |  76.25 (+0.19)
M&V [26] +Habitat | 45.80 | 54.30 | 66.88 | +1.09
47.05 (+1.25) |  55.55 (+1.25) |  67.64 (+0.76)
SSC [3] +Habitat | 53.57 | 65.65 | 74.73 | +0.44
54.13 (+0.56) |  66.17 (+0.52) |  74.96 (+0.23)
Figure 8: Flybird images do not have the habitat cues.

###  4.3 Both vision-only Models and vision-language Models Encountering
Similar Challenges in Bird Identification

To further analyze the joint effects of habitat on bird identification for
vision-only and vision-language, we study how incorporating habit improves
these models. That is, we wonder if both models will benefit from certain
classes that strongly correlate with habitat.

#### Experiment

We experiment on CUB by ranking the class-wise accuracy improvement of each
class on vision-only and vision-language models separately (Fig. 9). Then,
based on the habitat group we proposed in Sec. 3.1, we analyze the classes
that fall into the same habitat group in the top 20 classes for both models.

#### Results

As illustrated in Fig. 9, among the top 20 classes, both models include over
eight classes belonging to the habitat group, as indicated by the gray color
coding. This pattern suggests that both vision-only and vision-language models
encounter similar challenges in identifying these habitat-related classes.
Consequently, this observation emphasizes the significance of integrating
habitat information into both vision-only and vision-language models for
improved classification.

Class-wise improvements using CLIP modelsClass-wise improvements using vision-
only models

Figure 9: Accuracy improvement of the top 20 class-wise for CLIP and vision-
only models on CUB are shown in two charts, with colored bars indicating
shared habitat groupings. Unique classes to each model without habitat matches
are in gray. Eight colors, excluding gray, yellow, and orange, highlight
groups challenging for both models. CLIP struggles with yellow-coded birds,
and vision-only models with the orange-coded group.

###  4.4 Models perform poorly on Fly-bird images

It is challenging to recognize the birds when they are flying [40] (see Fig.
8). With this premise, we design an experiment to investigate the performance
of our models in such scenarios.

#### Fly Birds Detection

For identifying images that feature flying birds, we employ the Mask2Former
model, as outlined in [9]. This panoptic segmentation model first determines
the presence of elements such as rocks, grass, or water in the image.
Subsequently, it assesses whether the sky is depicted. If the sky is indeed
present, the image is classified as containing flying birds; otherwise, it is
categorized as a non-flying bird image.

#### Experiment

In this experiment, CUB and NABirds are examined and we found that the fly-
bird percentage of CUB is 10$\%$, while that of NABirds is 11.4$\%$.
Additionally, CUB and NABirds are divided into FlyBird-CUB, Non-FlyBird-CUB,
and FlyBird-NABirds, non-FlyBird-NABirds, and for all these datasets, we test
the classification accuracy of our models.

#### Results

From Tab. 6, which showcases the results of vision-only models, and Tab. 7
which represents the performance of the CLIP model, several key observations
can be made.

For both models, the Non-FlyBird results consistently achieve higher accuracy
across almost all methods when compared to their FlyBird counterparts.
Concretely, average improvements in CUB are +1.31 and +2.02 points, while in
NABirds the improvements are +6.92 and +4.08 points.

Further insight can be derived in that there is a big gap in accuracy between
Non-FlyBird and FlyBird of NABirds which are +6.92, and +4.08 in vision-only
and CLIP, respectively. This is because there are 11.4% FlyBirds images in
this dataset, and the accuracy improves by a large margin when removing these
images.

Table 6: The table highlights the accuracy of various vision-only models on CUB’s FlyBird and Non-FlyBird (200 classes) and NABirds (555 classes), revealing a consistent trend where Non-FlyBird outperforms FlyBird. | CUB (200 classes) | NABirds (555 classes)
---|---|---
FlyBird |  Non- FlyBird | FlyBird |  Non- FlyBird
ResNet-50 | Baseline | 86.06 |  86.93 (+0.87) | 72.68 |  81.16 (+8.48)
Mixed-S | 85.89 |  87.21 (+1.32) | 72.96 |  81.68 (+8.72)
Mixed-G | 83.97 |  86.55 (+2.58) | 73.96 |  81.95 (+7.99)
Mixed-I | 85.71 |  87.27 (+1.56) | 73.57 |  81.64 (+8.07)
TransFG | Baseline | 88.33 |  89.3 (+0.97) | 83.14 |  89.08 (+5.94)
Mixed-S | 89.02 |  89.47 (+0.45) | 84.28 |  89.31 (+5.03)
Mixed-G | 87.11 |  89.13 (+2.02) | 83.03 |  89.38 (+6.35)
Mixed-I | 88.68 |  89.36 (+0.68) | 84.56 |  89.35 (+4.79)
Avg $\Delta$ | +1.31 | +6.92
Table 7: The table compares CLIP model performances using different descriptions on CUB’s FlyBird and Non-FlyBird (200 classes) and NABirds (267 classes). Descriptions combine habitat with SSC [3], M&V [26], or PEEB [4]. A notable trend is Non-FlyBird’s consistent outperformance over FlyBird. | CUB (200 classes) | NABirds (267 classes)
---|---|---
FlyBird | Non-FlyBird | FlyBird | Non-FlyBird
ViT-B/32 |  SSC +Habitat | 48.43 |  53.36 (+4.93) | 45.75 |  51.5 (+5.75)
M&V +Habitat | 49.83 |  53.88 (+4.05) | 45.47 |  51.16 (+5.69)
PEEB +Habitat | 49.83 |  53.42 (+3.59) | 46.46 |  51.63 (+5.17)
ViT-B/16 |  SSC +Habitat | 57.67 |  58.06 (+0.39) | 54.11 |  57.45 (+3.34)
M&V +Habitat | 58.01 |  58.61 (+0.6) | 54.18 |  58.09 (+3.91)
PEEB +Habitat | 57.49 |  58.4 (+0.91) | 54.82 |  57.71 (+2.89)
ViT-L/14 |  SSC +Habitat | 64.29 |  64.52 (+0.23) | 62.96 |  66.41 (+3.45)
M&V +Habitat | 62.37 |  64.56 (+2.19) | 64.09 |  67.45 (+3.36)
PEEB +Habitat | 63.59 |  64.90 (+1.31) | 64.90 |  67.43 (+3.19)
Avg $\Delta$ | +2.02 | +4.08

##  5 Conclusion and Future Work

#### Limitation

Our work suggests that including habitat information helps to improve bird
recognition but getting correct habitat information for each bird is
challenging due to the inherent variability in avian habitat, which may differ
between nesting, foraging, and other activities, adding complexity to the task
of obtaining precise and comprehensive habitat information. Furthermore, it is
essential to develop a novel methodology that quantifies the respective
contributions of the habitat background and the bird’s presence within an
image, which may be beneficial for understanding cases where occlusion
happens.

#### Future Work

Part-based recognition systems hold promise as a future direction for
improving bird recognition. By breaking down a bird’s image into its
constituent parts, such as beak, wings, tail, and body, habitat, and
recognizing them individually, models can potentially enhance their accuracy
and robustness.

Investigating the transferability of models trained with habitat-informed data
to new geographic regions and diverse ecosystems also remains an essential
aspect of future work.

#### Conclusion

In conclusion, we have demonstrated the pivotal role of habitat information in
enhancing the performance of both vision-only models, including Convolutional
Neural Networks (CNN) and Vision Transformers (ViT), as well as vision-
language models, with particular emphasis on CLIP in the zero-shot setting.

## References

  * fro [2023] Habitat characteristics supporting bird species richness in mid-field woodlots.  _Frontiers_ , 2023.
  * sci [2023] _Habitat Selection in Birds_ , chapter Habitat Selection in Birds.  ScienceDirect, 2023.
  * All About Birds [2023] All About Birds.  All About Birds: Online Bird Guide, 2023.  17 Oct 2023.
  * Anonymous [2023] Anonymous.  Part-based bird classifiers with an explainable, editable language bottleneck.  In _Submitted to The Twelfth International Conference on Learning Representations_ , 2023.  under review.
  * Avian Report [2023] Avian Report.  Understanding bird habitats, 2023.  Accessed: 2023-11-06.
  * Birds & Blooms [2023] Birds & Blooms.  Bird watching by habitat, 2023.  Accessed: 2023-11-06.
  * British Trust for Ornithology [2023] British Trust for Ornithology.  The importance of habitat data, 2023.
  * Brown et al. [2020] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al.  Language models are few-shot learners.  _Advances in neural information processing systems_ , 33:1877–1901, 2020.
  * Cheng et al. [2022] 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.
  * Chu et al. [2019] Grace Chu, Brian Potetz, Weijun Wang, Andrew Howard, Yang Song, Fernando Brucher, Thomas Leung, and Hartwig Adam.  Geo-aware networks for fine-grained recognition.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision Workshops_ , pages 0–0, 2019.
  * Cornell Lab of Ornithology [2023] Cornell Lab of Ornithology.  Four keys to bird identification.  https://www.allaboutbirds.org/news/four-keys-to-bird-identification/, 2023.  Accessed: 2023-11-06.
  * Diao et al. [2022] Qishuai Diao, Yi Jiang, Bin Wen, Jia Sun, and Zehuan Yuan.  Metaformer: A unified meta framework for fine-grained recognition.  _CoRR_ , abs/2203.02751, 2022.
  * Donnelly et al. [2022] Jon Donnelly, Alina Jade Barnett, and Chaofan Chen.  Deformable protopnet: An interpretable image classifier using deformable prototypes.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 10265–10275, 2022.
  * Dosovitskiy et al. [2021] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby.  An image is worth 16x16 words: Transformers for image recognition at scale.  In _9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021_. OpenReview.net, 2021.
  * Fu et al. [2017] Jianlong Fu, Heliang Zheng, and Tao Mei.  Look closer to see better: Recurrent attention convolutional neural network for fine-grained image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 4438–4446, 2017.
  * Garcia-Quintas et al. [2023] Antonio Garcia-Quintas, Amédée Roy, Christophe Barbraud, Hervé Demarcq, Dennis Denis, and Sophie Lanco Bertrand.  Machine and deep learning approaches to understand and predict habitat suitability for seabird breeding.  _Ecology and Evolution_ , 13(9):e10549, 2023.
  * Ghiasi et al. [2021] Golnaz Ghiasi, Yin Cui, Aravind Srinivas, Rui Qian, Tsung-Yi Lin, Ekin D Cubuk, Quoc V Le, and Barret Zoph.  Simple copy-paste is a strong data augmentation method for instance segmentation.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pages 2918–2928, 2021.
  * He et al. [2022] Ju He, Jie-Neng Chen, Shuai Liu, Adam Kortylewski, Cheng Yang, Yutong Bai, and Changhu Wang.  Transfg: A transformer architecture for fine-grained recognition.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , pages 852–860, 2022.
  * He et al. [2016] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 770–778, 2016.
  * He and Peng [2017] Xiangteng He and Yuxin Peng.  Fine-grained image classification via combining vision and language.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 5994–6002, 2017.
  * Kingma and Ba [2015] Diederik P. Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  In _3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings_ , 2015.
  * Lin et al. [2015] Tsung-Yu Lin, Aruni RoyChowdhury, and Subhransu Maji.  Bilinear cnn models for fine-grained visual recognition.  In _Proceedings of the IEEE international conference on computer vision_ , pages 1449–1457, 2015.
  * Lloyd [1982] Stuart Lloyd.  Least squares quantization in pcm.  _IEEE transactions on information theory_ , 28(2):129–137, 1982.
  * Mac Aodha et al. [2019] Oisin Mac Aodha, Elijah Cole, and Pietro Perona.  Presence-only geographical priors for fine-grained image classification.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 9596–9606, 2019.
  * Marini et al. [2019] M. A. Marini et al.  The role of different natural and human-related habitats for the conservation of birds in a high andean lake.  _Link Springer_ , 2019.
  * Menon and Vondrick [2023] Sachit Menon and Carl Vondrick.  Visual classification via description from large language models.  In _The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023_. OpenReview.net, 2023.
  * Nauta et al. [2021] Meike Nauta, Ron van Bree, and Christin Seifert.  Neural prototype trees for interpretable fine-grained image recognition.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 14933–14943, 2021.
  * Nauta et al. [2022] Meike Nauta, Annemarie Jutte, Jesper Provoost, and Christin Seifert.  This looks like that, because… explaining prototypes for interpretable image recognition.  In _Machine Learning and Principles and Practice of Knowledge Discovery in Databases: International Workshops of ECML PKDD 2021, Virtual Event, September 13-17, 2021, Proceedings, Part I_ , pages 441–456. Springer, 2022.
  * OpenAI [2023] OpenAI.  Gpt-4 technical report, 2023.
  * Paszke et al. [2019] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al.  Pytorch: An imperative style, high-performance deep learning library.  _Advances in neural information processing systems_ , 32, 2019.
  * Radford et al. [2021] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al.  Learning transferable visual models from natural language supervision.  In _International conference on machine learning_ , pages 8748–8763. PMLR, 2021.
  * Sacha et al. [2023] Mikołaj Sacha, Dawid Rymarczyk, Łukasz Struski, Jacek Tabor, and Bartosz Zieliński.  Protoseg: Interpretable semantic segmentation with prototypical parts.  In _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision_ , pages 1481–1492, 2023.
  * Schuhmann et al. [2021] Christoph Schuhmann, Richard Vencu, Romain Beaumont, Robert Kaczmarczyk, Clayton Mullis, Aarush Katta, Theo Coombes, Jenia Jitsev, and Aran Komatsuzaki.  Laion-400m: Open dataset of clip-filtered 400 million image-text pairs.  _arXiv preprint arXiv:2111.02114_ , 2021.
  * Schuhmann et al. [2022] Christoph Schuhmann, Romain Beaumont, Richard Vencu, Cade Gordon, Ross Wightman, Mehdi Cherti, Theo Coombes, Aarush Katta, Clayton Mullis, Mitchell Wortsman, et al.  Laion-5b: An open large-scale dataset for training next generation image-text models.  _Advances in Neural Information Processing Systems_ , 35:25278–25294, 2022.
  * Suvorov et al. [2022] Roman Suvorov, Elizaveta Logacheva, Anton Mashikhin, Anastasia Remizova, Arsenii Ashukha, Aleksei Silvestrov, Naejin Kong, Harshith Goka, Kiwoong Park, and Victor Lempitsky.  Resolution-robust large mask inpainting with fourier convolutions.  In _Proceedings of the IEEE/CVF winter conference on applications of computer vision_ , pages 2149–2159, 2022.
  * Taesiri et al. [2022] Mohammad Reza Taesiri, Giang Nguyen, and Anh Nguyen.  Visual correspondence-based explanations improve ai robustness and human-ai team accuracy.  _Advances in Neural Information Processing Systems_ , 35:34287–34301, 2022.
  * Tang et al. [2015] Kevin Tang, Manohar Paluri, Li Fei-Fei, Rob Fergus, and Lubomir Bourdev.  Improving image classification with location context.  In _Proceedings of the IEEE international conference on computer vision_ , pages 1008–1016, 2015.
  * The Cornell Lab [2023] The Cornell Lab.  Inside birding: Habitat, 2023.
  * Van Horn et al. [2021] Grant Van Horn, Elijah Cole, Sara Beery, Kimberly Wilber, Serge Belongie, and Oisin Mac Aodha.  Benchmarking representation learning for natural world image collections.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pages 12884–12893, 2021.
  * Wah et al. [2011] Catherine Wah, Steve Branson, Peter Welinder, Pietro Perona, and Serge Belongie.  The caltech-ucsd birds-200-2011 dataset.  2011\.
  * Wang et al. [2022] Ke Wang, Harshitha Machiraju, Oh-Hyeon Choung, Michael H. Herzog, and Pascal Frossard.  CLAD: A contrastive learning based approach for background debiasing.  In _33rd British Machine Vision Conference 2022, BMVC 2022, London, UK, November 21-24, 2022_ , page 449. BMVA Press, 2022.
  * Wang et al. [2021] Zhaojun Wang, Jiangning Wang, Congtian Lin, Yan Han, Zhaosheng Wang, and Liqiang Ji.  Identifying habitat elements from bird images using deep convolutional neural networks.  _Animals_ , 11(5):1263, 2021.
  * Xiao et al. [2021] Kai Yuanqing Xiao, Logan Engstrom, Andrew Ilyas, and Aleksander Madry.  Noise or signal: The role of image backgrounds in object recognition.  In _9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021_. OpenReview.net, 2021.
  * Xue et al. [2022] Mengqi Xue, Qihan Huang, Haofei Zhang, Lechao Cheng, Jie Song, Minghui Wu, and Mingli Song.  Protopformer: Concentrating on prototypical parts in vision transformers for interpretable image recognition.  _arXiv preprint arXiv:2208.10431_ , 2022.
  * Yang et al. [2018] Ze Yang, Tiange Luo, Dong Wang, Zhiqiang Hu, Jun Gao, and Liwei Wang.  Learning to navigate for fine-grained classification.  In _Proceedings of the European conference on computer vision (ECCV)_ , pages 420–435, 2018.
  * Yao et al. [2022] Lewei Yao, Runhui Huang, Lu Hou, Guansong Lu, Minzhe Niu, Hang Xu, Xiaodan Liang, Zhenguo Li, Xin Jiang, and Chunjing Xu.  FILIP: fine-grained interactive language-image pre-training.  In _The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022_. OpenReview.net, 2022.
  * Yu et al. [2022] Jiahui Yu, Zirui Wang, Vijay Vasudevan, Legg Yeung, Mojtaba Seyedhosseini, and Yonghui Wu.  Coca: Contrastive captioners are image-text foundation models.  _Trans. Mach. Learn. Res._ , 2022, 2022.
  * Zheng et al. [2017] Heliang Zheng, Jianlong Fu, Tao Mei, and Jiebo Luo.  Learning multi-attention convolutional neural network for fine-grained image recognition.  In _Proceedings of the IEEE international conference on computer vision_ , pages 5209–5217, 2017.
  * Zhu et al. [2017] Zhuotun Zhu, Lingxi Xie, and Alan Yuille.  Object recognition with and without objects.  In _Proceedings of the 26th International Joint Conference on Artificial Intelligence_ , page 3609–3615. AAAI Press, 2017.

Leveraging Habitat Information for Fine-grained Bird Identification
Supplementary Material

##  A1 Pretrained models

#### Sources

We download the two pre-trained PyTorch models of ResNet-50, TransFG and three
variants of CLIP (ViT/B-32, ViT/B-16, and ViT/L-14) from:

  * •

ResNet-50 [36]: https://github.com/anguyen8/visual-correspondence-
XAI/tree/main/ResNet-50

  * •

TransFG [18]: https://github.com/TACJu/TransFG

  * •

CLIP [31]: https://github.com/openai/CLIP

Figure A1: The algorithm used in this study to cluster bird species into
groups based on their habitat settings.

##  A2 Constructing Additional Data for Training vision-only Models

###  A2.1 Constructing Habitat Groups

In our study, we implement a text clustering algorithm to analyze and group
birds based on habitat descriptions (see Fig. A1).

The algorithm begins by loading the textual descriptors, which are then
transformed into a vector space using TF-IDF vectorization, excluding common
English stop words for better feature representation.

To determine the optimal number of clusters for k-means, we iteratively
compute the silhouette scores for different cluster counts, selecting the
cluster number that yields the highest score as the most suitable for our
data. With the optimal number of clusters established, we perform k-means
clustering and categorize the descriptions accordingly. Each cluster is then
mapped back to the corresponding bird classes, resulting in a collection of
class clusters.

As detailed in Section 3.1, identifying bird groups based on habitats
facilitates both Mixed-Groupand Mixed-Irrelevantdata augmentation processes.
This categorization also enables a more nuanced analysis of class-wise
accuracy between CLIP and unimodal models, which is further explored in
Section 4.3.

For the CUB dataset, we organize 200 classes into 50 groups, whereas for the
NABirds dataset, 555 classes were clustered into 196 groups.

###  A2.2 Example of Bird Groups and their corresponding habitat descriptions

The group containing the Black-footed Albatross, Heerman Gull, and Elegant
Tern, usually prefers far offshore or sandy island (see Fig. A3 at row 1).

  * •

Black-footed Albatross: Nests on low, sandy islands in the tropical North
Pacific. Forages both near shore (though usually not within sight of land) and
far offshore, in places where upwelling or converging currents concentrate
nutrients and prey at the sea surface.

  * •

Heerman Gull: Nests on rocky islands, mostly in the Gulf of California.
Forages in ocean waters, usually within sight of land, often with terns,
pelicans, cormorants, boobies, and sea lions. Also forages along beaches and
in sheltered harbors and estuaries. Very rare inland.

  * •

Elegant Tern: Nests on beaches and sandy islands. Forages close to the shore
over ocean waters, where currents and upwelling concentrate prey (northern
anchovy in particular). Usually forages within 10 miles of land, and often
within sight of land.

Group containing the Mallard, Seaside Sparrow, Barn Swallow, and Black Tern,
their hangouts usually are ponds, fresh and saltwater marshes (see Fig. A3 at
row 3).

  * •

Mallard: Mallards can live in almost any wetland habitat, natural or
artificial. Look for them on lakes, ponds, marshes, rivers, and coastal
habitats, as well as city and suburban parks and residential backyards.

  * •

Seaside Sparrow: Salt marshes, including brackish marshes and (in the
Everglades) freshwater marshes.

  * •

Barn Swallow: You can find the adaptable Barn Swallow feeding in open habitats
from fields, parks, and roadway edges to marshes, meadows, ponds, and coastal
waters. Their nests are often easy to spot under the eaves or inside of sheds,
barns, bridges and other structures.

  * •

Black Tern: Nests in freshwater marshes and bogs; winters in coastal lagoons,
marshes, and open ocean waters. Migrants may stop over in almost any type of
wetland.

###  A2.3 Augmenting additional data

The core aspect of our proposed augmentation technique involves cropping birds
from their original images and superimposing them onto various backgrounds, a
process detailed in Algorithm 1.

Algorithm 1 Pseudo code for combining a habitat image with a specific bird.

1:Input: $habitat\\_img$, $only\\_bird\\_img$, $mask$.

2: $habitat\\_img$: an image after cropping the bird and inpainting the
missing regions using LaMa [35].

3: $only\\_bird\\_img$: an image of a bird with a black background (bird
only).

4: $mask$: binary mask of the bird in the $only\\_bird\\_img$.

5: $habitat\\_masked$: binary mask of habitat image.

6: $combined\\_img$: Combined image between the $habitat\\_img$ and the bird
in $only\\_bird\\_img$.

7:Output: $combined\\_img$

8:$habitat\\_masked\ \leftarrow$ round($habitat\\_img\ \times(1-mask)$)

9:$img\\_combined\ \leftarrow$ $black\\_img$ \+ $habitat\\_masked$

10:Return: $combined\\_img$

Mixed-Same We implement a random alteration of the bird’s background while
ensuring that it remains within the same class as the original.

Mixed-Group Under this scenario, the background for a bird is carefully chosen
from its own bird group. This selection process is elaborated in Section A2.2.

Mixed-Irrelevant In the Mixed-Irrelevant case, the bird’s background is
randomly selected from groups that are irrelevant or unrelated to the bird’s
original group.

Having established the sources of the habitat images, we can readily apply
Algorithm 1 to generate additional data.

##  A3 Descriptions Types in CLIP

#### Visual descriptions

The visual descriptions used in this study were obtained from three sources:

  * •

M&V [26] utilizes GPT-3 [8] to generate visual descriptions of birds. For
instance, the class Ovenbird has descriptions:

⬇

Ovenbird: {

It is a small, sparrow-like bird,

It is brown or grey with streaks on its breast,

It has a white belly,

It has a black stripe on its head,

It has a long, curved beak,

It has dark eyes,

It has long legs

}

  * •

PEEB [4] leverages GPT-4 [29] to generate descriptions of twelve distinct
parts of birds including wings, tail, eyes, back, forehead, nape, crown, leg,
breast, throat, belly, beak. For instance, the class Orange-crowned Warbler
has descriptions:

⬇

Orange-crowned Warbler: {

back: olivegreen with darker streaks,

beak: small and pointed,

belly: pale yellowishgreen,

breast: pale yellowishgreen with faint streaks,

crown: dull olivegreen,

forehead: dull olivegreen,

eyes: dark brown,

legs: dark grayishbrown,

wings: olivegreen with two pale wing bars,

nape: olivegreen with faint streaks,

tail: brownishgray with white outer feathers,

throat: pale yellowishgreen with faint streaks

}

  * •

Shape, Size, and Color (SSC) [3] descriptions are human-annotated descriptions
and are available on the allaboutbirds.org. For instance, the class Chestnut-
sided Warbler has descriptions:

⬇

Chestnut-sided Warbler: {

shape: An slim warbler with a relatively long tail that it often holds cocked,

or raised above the body line, which makes the tail appear longer still,

size: Larger than a Ruby-crowned Kinglet, smaller than a Song Sparrow

sparrow-sized or smaller,

color: Breeding adults are crisp gray-and-white birds with a yellow crown,

black face markings, and rich chestnut flanks. Males are more richly marked
than

females. In nonbreeding plumage, adults and immatures are bright lime-green

above with a neat white eyering, two wingbars, and pale gray to white
underparts

}

#### Habitat descriptions

Additionally, habitat descriptions were also sourced from
allaboutbirds.org[3]. For instance:
The class Red-headed Woodpecker has habitat description:

⬇

Red-headed Woodpeckers: {

Red-headed Woodpeckers live in pine savannahs and other open forests with
clear

understories. Open pine plantations, treerows in agricultural areas, and
standing

timber in beaver swamps and other wetlands all attract Red-headed Woodpeckers

}

Or, The class Cactus Wren has habitat description:

⬇

Cactus Wren: {

Cactus Wrens live in deserts, arid foothills, coastal sage scrub, and urban
areas

throughout the Southwestern deserts, especially in areas with thorny shrubs,
cholla,

and prickly pear

}

###  A3.1 Differentiating Habitats of Visually Similar Birds

Fig. A2 shows 6 pairs of birds where birds in each pair are visually similar
but they have different habitat hangouts.

Ring-billed Gull | Western Gull
---|---
Beaches | Maritime location

Common Raven | White-necked Raven
---|---
Forest | Desert Regions

Artic Tern | Common Tern
---|---
Treeless Area | Rocky Island

Swamp Sparrow | Chipping Sparrow
---|---
Swamp | Common Backyard

Red-tailed Hawk | Red-shoulder Hawk
---|---
Mountain | Near River

Kentucky Warbler | Canada Warbler
---|---
Near Streams | Deciduous Forests

Figure A2: Comparative visual analysis of two bird species pairs, each
exhibiting similar morphology yet distinct habitats. For example, the Swamp
Sparrow (a) resides in swamps, contrasted with the Chipping Sparrow (b) which
favors the common backyard. On the right, the Red-tailed Hawk (c) is adapted
to mountains, whereas the Red-shoulder Hawk (d) is typically found near
rivers.

Group 1: ”Black-footed Albatross”, ”Heermann Gull”, ”Elegant Tern”

Prefered Habitat: far offshore, sandy island.

Group 2: ”Black-throated Sparrow”, ”Common Raven”, ”Green-tailed Towhee”

Prefered Habitat: scrubby areas, desert scrub.

Group 3: ”Mallard”, ”Seaside Sparrow”, ”Barn Swallow”, ”Black Tern”

Prefered Habitat: ponds, fresh and salt water marshes

Group 4: ”White-necked Raven”, ”Geococcyx”, ”Sage Thrasher”, ”Rock Wren”

Prefered Habitat: Desert regions.

Group 5: ”American Crow”, ”Fish Crow”, ”American Goldfinch”, ”Ring-billed
Gull”

Prefered Habitat: agricultural fields, roadsides.

Group 6: ”Brown Creeper”, ”Whip-poor Will”, ”Scarlet Tanager”, ”Red-eyed
Vireo”, ”Black-and-white Warbler”, ”Black-throated-Blue Warbler”

Prefered Habitat: deciduous forests.

Group 7: ”Gray-crowned-Rosy Finch”, ”Pigeon Guillemot”, ”Glaucous-winged
Gull”, ”Ivory Gull”, ”Slaty-backed Gull”, ”Western Gull”

Prefered Habitat: cliffs, ice field, maritime location.

Figure A3: Seven Bird Species Groups - Each group consists of birds sharing a
common habitat. For example, the 7th group includes Gray-crowned-Rosy Finch,
Pigeon Guillemot, Glaucous-winged Gull, Ivory Gull, Slaty-backed Gull, and
Western Gull, they all prefer cliffs, mountains or beaches.


# Approximately: Independence Implies Vertex Cover

Sariel Har-Peled Department of Computer Science; University of Illinois; 201
N. Goodwin Avenue; Urbana, IL, 61801, USA<EMAIL_ADDRESS>http://sarielhp.org/. Work on this paper was partially supported by a NSF AF
award CCF-1907400.

###### Abstract

We observe that a $(1-{\varepsilon})$-approximation algorithm to Independent
Set, that works for any induced subgraph of the input graph, can be used, via
a polynomial time reduction, to provide a $(1+{\varepsilon})$-approximation to
Vertex Cover. This basic observation was made before, see [BHR11].

As a consequence, we get a PTAS for VC for unweighted pseudo-disks, QQPTAS
111We refer to an $(1\pm{\varepsilon})$-approximation algorithm with running
time of the form $n^{O(\mathrm{poly}(\log\log n,1/{\varepsilon}))}$ as QQPTAS.
The more traditional running time $n^{O(\mathrm{poly}(\log
n,1/{\varepsilon}))}$ is QPTAS (i.e.,quasi-polynomial time approximation
scheme). A PTAS refers to an approximation algorithm with running time of the
form $n^{O(\mathrm{poly}(1/{\varepsilon}))}$. Further mysterious acronyms can
be provided upon request. for VC for unweighted axis-aligned rectangles in the
plane, and QPTAS for MWVC for weighted polygons in the plane. To the best of
our knowledge all these results are new.

##  1 Introduction

#### Background.

Given a graph ${G}=(V,{E})$, a _vertex cover_ (VC) is a set $C\subseteq V$,
that is adjacent to all the edges of ${G}$. The problem of computing a minimum
VC is a classical problem that is NP-Hard [GJ90], and an easy
$2$-approximation algorithm is known (by computing greedily a maximal
matching, and using its vertices). Dinur and Safra [DS05] showed that no
approximation better than $1.3606$ is possible, unless
${{{\color[rgb]{0.0,0.1,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{0.0,0.1,0.0}\textsc{{P}}}}}={{{\color[rgb]{0.0,0.1,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{0.0,0.1,0.0}\textsc{{NP}}}}}$.
This was later improved to $\sqrt{2}-{\varepsilon}\approx 1.41421$ by Khot et
al. [KMS18]. If the unique-game conjecture is true, no approximate better than
$2$ is possible in the general case [KR08].

For geometric intersection graph the problem is easier. Erlebach et al.
[EJS05] gave a PTAS for the intersection graph of weighted fat objects. Har-
Peled and Quanrud [HQ17] provided a PTAS for VC for the unweighted case for
low-density graphs, or polynomial expansion graphs.

#### The observation.

Given an instance of Vertex Cover, one can reduce it in polynomial time into a
dense instance, where the VC is at least half the vertices in the graph (or
half the mass in the weighted case). In such a graph a
$(1-{\varepsilon})$-approximation to the independent set, implies readily a
$(1+{\varepsilon})$-approximation to VC.

#### Outline.

For the sake of completeness, and to provide a relatively self contained
description, we review this reduction (into the dense subgraph), in
excruciating detail, in Section 2. We emphasize, however, that this reduction
is well known – see [CC04, CC08] and references therein. The unweighted case
is somewhat easier, and is described nicely in Cygan et al. [CFK+15, Chapter
2]. We describe the new result and its applications in Section 3.

##  2 Reduction of VC to the dense case

The material covered in this section can be found in [CFK+15, CFK+15, CC04,
CC08] and references therein.

Given a graph ${G}=(V,{E})$, and a weight function $w:V\rightarrow(0,\infty)$,
the _min weight vertex cover_ (MWVC) is the problem of computing the subset
$S_{\mathrm{opt}}\subseteq V$, such that $S_{\mathrm{opt}}$ is adjacent to all
edges in ${G}$, and $\mathrm{vc}^{*}({G})=w(S_{\mathrm{opt}})=\sum_{v\in
S_{\mathrm{opt}}}w(v)$ is the minimum among all such sets. The complement of a
vertex cover is an independent set, and in particular, we have
$\mathrm{vc}^{*}({G})=w({G})-\mathrm{is}^{*}({G})$, where $\mathrm{is}^{*}$ is
the weight of the maximum weight independent set in ${G}$, and
$w({G})=\sum_{v\in V}w(v)$.

A natural starting point for approximation algorithms for VC, is to solve the
associated LP:

min $\displaystyle{\textstyle\sum_{v\in V}w(v)x_{v}}$ (LPVC) s.t.
$\displaystyle x_{u}+x_{v}\geq 1$ $\displaystyle\forall
uv\in{E}\left({{G}}\right)$ $\displaystyle x_{v}\geq 0$ $\displaystyle\forall
v\in V.$

For an assignment $\mathsf{z}=(z_{v})_{v\in V}$, let
$\nu\left({\mathsf{z}}\right)=\sum_{v\in V}w(v)z_{v}$ denote the _value_ of
$\mathsf{z}$.

######  Lemma 2.1.

There is an optimal solution for _( LPVC)_ that is half-integral. That is, for
any $v\in V$, we have $x_{v}\in\\{0,1/2,1\\}$.

###### Proof:

Consider an optimal solution $\mathsf{x}=(x_{v})_{v\in V}$ for (LPVC), Let

$L=\left\\{v\in V\;\middle|\;x_{v}\in(0,1/2)\right\\}\qquad\text{and}\qquad
H=\left\\{v\in V\;\middle|\;x_{v}\in(1/2,1)\right\\}.$

If $w(L)<w(H)$, then consider the assignment

$y_{v}=\begin{cases}x_{v}-{\varepsilon}&v\in H\\\ x_{v}+{\varepsilon}&v\in
L\\\ x_{v}&\text{otherwise},\end{cases}$

where ${\varepsilon}=\min_{v\in L\cup H}|x_{v}-1/2|$. For an edge $uv$, with
$u\in L$ and $v\in H$, we have
$y_{u}+y_{v}=x_{u}+{\varepsilon}+x_{v}-{\varepsilon}=x_{u}+x_{v}\geq 1$. It is
easy to verify, in a similar fashion, that $\mathsf{y}=(y_{v})_{v\in V}$ is a
feasible solution for (LPVC). Furthermore, since $w(L)<w(H)$, we have

$\nu\left({\mathsf{y}}\right)=\sum_{v\in
V}w(v)x_{v}-{\varepsilon}w(H)+{\varepsilon}w(L)=\nu\left({\mathsf{x}}\right)+{\varepsilon}(w(L)-w(H))<\nu\left({\mathsf{x}}\right),$

which is impossible, by the optimality of $\mathsf{x}$. A similar argument
applies if $w(L)>w(H)$. As such, it must be that $w(L)=w(H)$. But then, the
solution $\mathsf{y}$ is also optimal, and it has one more variable assigned a
value of $1/2$ then $\mathsf{x}$. Repeating this argument now to $\mathsf{y}$
till both $L$ and $R$ are empty implies the claim.

######  Lemma 2.2.

An optimal half-integral solution to the linear program _( LPVC)_ can be
computed in $O(n^{3})$ time, where $n=\left|{V}\right|$.

###### Proof:

Let ${K}$ be the bipartite graph over the bipartition
$U_{1}=\left\\{u_{1}\;\middle|\;u\in V\right\\}$ and
$U_{2}=\left\\{u_{2}\;\middle|\;u\in V\right\\}$. Let

${E}\left({{K}}\right)=\left\\{u_{1}v_{2},\,u_{2}v_{1}\;\middle|\;uv\in{E}\left({{G}}\right)\right\\}.$

For any vertex $v_{i}\in U_{1}\cup U_{2}$, its weight is its original weight
$w(v)$.

There is an associated network flow instance – adding a source vertex $s$, and
a sink vertex $t$. Here, the source vertex $s$ is connected to all the
vertices in $U_{1}$. An edge $\left({s,u_{1}}\right)$, for $u_{1}\in U_{1}$,
has capacity $w(u)$. All the edges of $K$ are oriented from $U_{1}$ to
$U_{2}$, with infinite capacity, and an edge $u_{2}t$, for all $u_{2}\in
U_{2}$, has capacity $w(u_{2})=w(u)$. Let ${N}$ denote the resulting instance
of network flow. It is easy to verify that a $s$-$t$ min-cut in ${N}$
corresponds to a minimum weight vertex cover in ${K}$, and vice versa. As
such, compute a max-flow in ${N}$, and let $f$ denote this flow. Given $f$,
the corresponding $s$-$t$ min-cut can be computed in linear time from the
residual network flow of $f$ (i.e., min-cut max-flow theorem). This cut then
can be readily converted into the desired minimum vertex cover
$S_{\mathrm{opt}}$ in ${K}$. Observe that $w(S_{\mathrm{opt}})=|f|$, where
$|f|$ is the value of the flow of $f$. The max-flow computation in this case
can be done in $O(n^{3})$ time using known algorithms [CLRS01].

For a vertex $v\in V\left({{K}}\right)$, let $\chi(v)=1$ if $v\in
S_{\mathrm{opt}}$, and zero otherwise. We set
$x_{v}=\bigl{(}\chi(v_{1})+\chi(v_{2})\bigr{)}/2$, for all $v\in V$. Let
$\mathsf{x}=(x_{v})_{v\in V}$. We have

$\nu\left({\mathsf{x}}\right)=\sum_{v\in
V}w(v)x_{v}=\frac{w(S_{\mathrm{opt}})}{2}.$ (1)

Consider an edge $uv\in{E}\left({{G}}\right)$. Observe that

$\displaystyle x_{u}+x_{v}$
$\displaystyle=\frac{\chi(u_{1})+\chi(u_{2})+\chi(v_{1})+\chi(v_{2})}{2}=\frac{\chi(u_{1})+\chi(v_{2})}{2}+\frac{\chi(u_{2})+\chi(v_{1})}{2}\geq\frac{1}{2}+\frac{1}{2}=1,$

since $S_{\mathrm{opt}}$ is a vertex cover of ${K}$. So
$\mathsf{x}=(x_{v})_{v\in V}$ is a feasible assignment for (LPVC) (and it also
half-integral).

Consider an optimal half-integral assignment $\mathsf{y}=(y_{v})_{v\in V}$ for
LPVC, which exists by Lemma 2.1.. This induces a natural vertex cover for
${K}$. Indeed, if $x_{v}=1/2$ we add $v_{1}$ to a set $T$. Similarly, if
$x_{v}=1$, we add $v_{1}$ and $v_{2}$ to $T$. We claim that $T$ is a vertex
cover for ${K}$. Indeed, for any edge $uv\in{E}\left({{G}}\right)$, we have
that $x_{u}+x_{v}\geq 1$. If $x_{u}=1$ then $u_{1},u_{2}\in T$ and these two
vertices cover the edges $u_{1}v_{2}$ and $u_{2}v_{1}$. A similar argument
applies if $x_{v}=1$. The remaining possibility is that $x_{u}=x_{v}=1/2$, but
then $u_{1},v_{1}\in T$. Which implies that $T$ covers the edges $u_{1}v_{2}$
and $u_{2}v_{1}$. As such, all the edges of ${K}$ are covered by $T$.

Observe that

$2\nu\left({\mathsf{y}}\right)=2\sum_{v\in V}w(v)y_{v}=w(T)\geq
w(S_{\mathrm{opt}})=2\nu\left({\mathsf{x}}\right),$

by Eq. (1). Namely
$\nu\left({\mathsf{y}}\right)\geq\nu\left({\mathsf{x}}\right)$. We conclude
that $\mathsf{x}$ is an optimal solution for (LPVC), and it is also half-
integral.

Given an optimal half-integral solution $\mathsf{x}=(x_{v})_{v\in V}$ for
(LPVC), one can partition the vertices into three sets:

  1. (i)

$V_{0}=\left\\{v\in V\;\middle|\;x_{v}=0\right\\}$,

  2. (ii)

$V_{1/2}=\left\\{v\in V\;\middle|\;x_{v}=1/2\right\\}$, and

  3. (iii)

$V_{1}=\left\\{v\in V\;\middle|\;x_{v}=1\right\\}$.

A few observations about these sets. The set $V_{0}$ is an independent set in
${G}$. Indeed, an edge $uv\in{E}$ with an endpoint $u\in V_{0}$ and an
endpoint in $v\in V_{0}\cup V_{1/2}$ has $x_{u}+x_{v}\leq 0+1/2=1/2$, which is
impossible. As such, for a vertex $v\in V_{0}$, any adjacent edge $vu\in{E}$,
must have $u\in V_{1}$. Namely, there is no edge between a vertex of $V_{0}$
and a vertex $V_{1/2}$. This is known as a _crown decomposition_ , with
$C=V_{0}$ being the “crown”, $R=V_{1/2}$ being the “body”, and $H=V_{1}$ be
the “head”.

We need the weighted version of the Nemhauser-Trotter theorem, which we prove
next.

######  Theorem 2.3 (Nemhauser-Trotter).

Let ${G}$ be a graph with weights $w:V\rightarrow(0,\infty)$. There is a
minimum weight vertex cover $S$ of ${G}$, such that $V_{1}\subseteq S\subseteq
V_{1}\cup V_{1/2}$.

###### Proof:

Let $S_{\mathrm{opt}}$ be the optimal vertex cover, and let
$S=(S_{\mathrm{opt}}\setminus V_{0})\cup V_{1}$. Clearly, $S$ is a vertex
cover, as all the edges adjacent to $V_{0}$ are covered by $V_{1}$. Since
$V_{0}\cup V_{1/2}\cup V_{1}=V$, we have $S=V_{1}\cup S\subseteq V_{1/2}\cup
V_{1}$.

Assume, for the sake of contradiction, that $w(S)>w(S_{\mathrm{opt}})$. We
have

$\displaystyle w(S)=w(S_{\mathrm{opt}})-w\bigl{(}V_{0}\cap
S_{\mathrm{opt}}\bigr{)}+w\bigl{(}V_{1}\setminus
S_{\mathrm{opt}}\bigr{)}>w(S_{\mathrm{opt}})$ $\displaystyle\iff w(V_{0}\cap
S_{\mathrm{opt}})-w(V_{1}\setminus S_{\mathrm{opt}})<0.$

Let ${\varepsilon}<1/2$ be some constant, and for any $v\in V$, let

$y_{v}=\begin{cases}1-{\varepsilon}&v\in V_{1}\setminus S_{\mathrm{opt}}\\\
{\varepsilon}&v\in V_{0}\cap S_{\mathrm{opt}}\\\
x_{v}&\mathrm{otherwise.}\end{cases}$

An easy case analysis shows that the $\mathsf{y}=(y_{v})_{v\in V}$ is a
feasible solution. Indeed, we need to consider only edges $uv$ with at least
one endpoint (say $u$) in $V_{1}\setminus S_{\mathrm{opt}}$, (as these are the
only edges that lost value). There are the following cases to consider:

  1. (i)

$v\in V_{1}$: We have $y_{u}+y_{v}\geq 1-{\varepsilon}+1-{\varepsilon}\geq 1$.

  2. (ii)

$v\in V_{1/2}$: We have $y_{u}+y_{v}=1-{\varepsilon}+1/2\geq 1$.

  3. (iii)

$v\in V_{0}\cap S_{\mathrm{opt}}$: We have
$y_{u}+y_{v}=1-{\varepsilon}+{\varepsilon}=1$.

  4. (iv)

$v\in V_{0}\setminus S_{\mathrm{opt}}$: Both endpoints of $uv$ are outside
$S_{\mathrm{opt}}$, which is impossible.

Observe that $\nu\left({\mathsf{y}}\right)=\sum_{v\in
V}y_{v}=\nu\left({\mathsf{x}}\right)+{\varepsilon}w\left({V_{0}\cap
S_{\mathrm{opt}}}\right)-{\varepsilon}w\left({V_{1}\setminus
S_{\mathrm{opt}}}\right)<\nu\left({\mathsf{x}}\right)$, which is a
contradiction to the optimality of $\mathsf{x}$.

######  Lemma 2.4.

Let ${K}={G}[V_{1/2}]$ be the induced subgraph of ${G}$ over $V_{1/2}$.
Consider any minimum vertex cover $C$ of ${G}[V_{1/2}]$. Then $C\cup V_{1}$ is
a minimum weight vertex cover of ${G}$.

###### Proof:

Let ${H}={G}[V_{0}\cup V_{1/2}]$. Consider any minimum vertex cover $C$ to the
graph ${H}$ and observe that $C\cup V_{1}$ is a vertex cover for ${G}$.
Similarly, given a minimum vertex cover $S_{\mathrm{opt}}$ for ${G}$, consider
the equally priced vertex cover $S=(S_{\mathrm{opt}}\setminus V_{0})\cup
V_{1}$ (see Theorem 2.3), and observe that $S$ is a vertex cover of ${G}$ and
$S\setminus V_{1}$ is a vertex cover for ${H}$. We conclude that computing the
minimum vertex cover for ${G}$, is equivalent to computing the vertex cover
for ${H}$. Since $V_{0}$ is an independent set in ${G}$, and it is connected
to only vertices of $V_{1}$, it follows that $V_{0}$ is a set of isolated
vertices in ${H}$. As such, it is sufficient to compute a minimum vertex cover
for ${G}[V_{1/2}]$.

Observe that $\mathsf{x}$ induces a valid optimal fractional solution for the
induced subgraph graph ${G}[V_{1/2}]$.

######  Lemma 2.5.

Consider any fractional optimal solution $\mathsf{y}$ for the vertex cover of
the graph ${G}[V_{1/2}]$. We have that
$\nu\left({\mathsf{y}}\right)=\nu\left({\mathsf{x}}\right)-w(V_{1})=\sum_{v\in
V_{1/2}}w(v)/2=w(V_{1/2})/2$.

###### Proof:

The assignment $\mathsf{y}$, can be extended into a fractional solution for
${G}$, by setting $y_{v}=1$ if $v\in V_{1}$, and zero otherwise. Similarly,
$\mathsf{x}$ when restricted to $V_{1/2}$ is a valid VC solution for
${G}[V_{1/2}]$. This readily implies the claim, as $\mathsf{x}$ is the optimal
solution for (LPVC).

##  3 The result and some applications

For a weighted graph ${G}$, let $\mathrm{vc}^{*}({G})$ denote the weight of
the minimum weight vertex cover of ${G}$. Similarly, let
$\mathrm{is}^{*}({G})$ be the weight of the maximum weight independent set in
${G}$.

######  Theorem 3.1.

Let ${G}=(V,{E})$ be a graph, with weights on the vertices, and assume that we
are given an algorithm algIS that can compute, in $T(n)$ time, an independent
set $I\subseteq V$, such that $w(I)\geq(1-{\varepsilon})\mathrm{is}^{*}({G})$.
Furthermore, assume that this algorithm works for any induced subgraph of
${G}$. Then, one can compute, in $O\bigl{(}n^{3}+T(n)\bigr{)}$ time, a vertex
cover $C$ of ${G}$, such that $w(C)\leq(1+{\varepsilon})\mathrm{vc}^{*}({G})$.

###### Proof:

Using the algorithm of Lemma 2.4, compute a partition of the vertices of ${G}$
into the three sets $V_{0},V_{1/2},V_{1}$. This reduces ${G}$ into an induced
subgraph ${K}={G}[V_{1/2}]$, such that it is enough to solve the problem on
${K}$. Importantly, for the graph ${K}$, we have the property that the optimal
LP solution (for the relaxation of the LP) assigns all vertices value $1/2$.
That is $\mathrm{vc}^{*}=\mathrm{vc}^{*}({K})\geq w/2$, where $w=\sum_{v\in
V\left({{K}}\right)}w(v)$.

In the following, let $\mathrm{is}^{*}=\mathrm{is}^{*}({K})$. Compute an
independent set $I$ in ${K}$ using algIS. We have that

$w(I)\geq(1-{\varepsilon})\mathrm{is}^{*}=(1-{\varepsilon})(w-\mathrm{vc}^{*}).$

The set $C=V\left({{K}}\right)-I$ is a vertex cover, and we have

$\displaystyle w(C)$ $\displaystyle=w-w(I)\leq
w-(1-{\varepsilon})(w-\mathrm{vc}^{*})={\varepsilon}w+\left({1-{\varepsilon}}\right)\mathrm{vc}^{*}$
$\displaystyle\leq
2{\varepsilon}\,\mathrm{vc}^{*}+\left({1-{\varepsilon}}\right)\mathrm{vc}^{*}=(1+{\varepsilon})\mathrm{vc}^{*},$

since $\mathrm{vc}^{*}\geq w/2$. We have that $C\cup V_{1}$ is a vertex cover
for the original graph. Furthermore, by Lemma 2.4, we have

$w(C\cup
V_{1})=w(C)+w(V_{1})\leq(1+{\varepsilon})\mathrm{vc}^{*}+w(V_{1})\leq(1+{\varepsilon})(w(V_{1})+\mathrm{vc}^{*})=(1+{\varepsilon})\mathrm{vc}^{*}({G}),$

since $\mathrm{vc}^{*}({G})=\mathrm{vc}^{*}+w(V_{1})$ by Lemma 2.4.

###  3.1 Applications

For several cases, efficient $(1+{\varepsilon})$-approximations algorithms are
known:

  1. (i)

A PTAS for the unweighted pseudo-disks [CH12].

  2. (ii)

A QQPTAS is for unweighted rectangles in the plane [CE16].

  3. (iii)

A QPTAS for weighted simple polygons in the plane [AHW19].

Plugging these results into Theorem 3.1, implies the following.

######  Theorem 3.2.

We have the following:

  1. (i)

For the intersection graph of $n$ unweighted pseudo-disk in the plane, a
$(1+{\varepsilon})$-approximation to the minimum vertex cover can be computed
in $n^{O(1/{\varepsilon}^{2})}$ time.

  2. (ii)

For the intersection graph of $n$ unweighted axis-aligned rectangles in the
plane, a $(1+{\varepsilon})$-approximation to the minimum vertex cover can be
computed in $n^{O(\mathrm{poly}(\log\log n,1/{\varepsilon}))}$ time.

  3. (iii)

For the intersection graph of $n$ weighted simple polygons in the plane, a
$(1+{\varepsilon})$-approximation to the minimum weight vertex-cover can be
computed in $n^{O(\mathrm{poly}(\log n,1/{\varepsilon}))}$ time.

#### Acknowledgments.

The author thanks Chandra Chekuri for useful discussions, and Timothy Chan and
C. S. Karthik for pointing out relevant references.

## References

  * [AHW19] Anna Adamaszek, Sariel Har-Peled and Andreas Wiese  “Approximation Schemes for Independent Set and Sparse Subsets of Polygons”  In _J. Assoc. Comput. Mach._ 66.4 New York, NY, USA: ACM, 2019, pp. 29:1–29:40  DOI: 10.1145/3326122
  * [BHR11] Reuven Bar-Yehuda, Danny Hermelin and Dror Rawitz  “Minimum vertex cover in rectangle graphs”  In _Comput. Geom._ 44.6-7, 2011, pp. 356–364  DOI: 10.1016/j.comgeo.2011.03.002
  * [CC04] Miroslav Chlebík and Janka Chlebíková  “Improvement of Nemhauser-Trotter Theorem and Its Applications in Parametrized Complexity”  In _Proc. 9th Scand. Workshop Algorithm Theory (SWAT)_ 3111, Lect. Notes in Comp. Sci.  Springer, 2004, pp. 174–186  DOI: 10.1007/978-3-540-27810-8“˙16
  * [CC08] Miroslav Chlebík and Janka Chlebíková  “Crown reductions for the Minimum Weighted Vertex Cover problem”  In _Discrete Applied Mathematics_ 156.3, 2008, pp. 292–312  DOI: 10.1016/j.dam.2007.03.026
  * [CE16] Julia Chuzhoy and Alina Ene  “On Approximating Maximum Independent Set of Rectangles”  In _Proc. 57th Annu. IEEE Sympos. Found. Comput. Sci.(FOCS)_, 2016, pp. 820–829  DOI: 10.1109/FOCS.2016.92
  * [CFK+15] Marek Cygan et al.  “Parameterized Algorithms”  Springer, 2015  DOI: 10.1007/978-3-319-21275-3
  * [CH12] T.. Chan and S. Har-Peled  “Approximation Algorithms for Maximum Independent Set of Pseudo-Disks”  In _Discrete Comput. Geom._ 48, 2012, pp. 373–392  DOI: 10.1007/s00454-012-9417-5
  * [CLRS01] T.. Cormen, C.. Leiserson, R.. Rivest and C. Stein  “Introduction to Algorithms”  MIT Press / McGraw-Hill, 2001  URL: http://theory.lcs.mit.edu/~clr/
  * [DS05] Irit Dinur and Samuel Safra  “On the hardness of approximating vertex cover”  In _Annals of Mathematics_ 162.1 Annals Math., 2005, pp. 439–485  DOI: 10.4007/annals.2005.162.439
  * [EJS05] T. Erlebach, K. Jansen and E. Seidel  “Polynomial-Time Approximation Schemes for Geometric Intersection Graphs”  In _SIAM J. Comput._ 34.6, 2005, pp. 1302–1323  DOI: 10.1137/S0097539702402676
  * [GJ90] M.. Garey and D.. Johnson  “Computers and Intractability; A Guide to the Theory of NP-Completeness”  W. H. Freeman & Co., 1990
  * [HQ17] Sariel Har-Peled and Kent Quanrud  “Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs”  In _SIAM J. Comput._ 46.6 Society for Industrial & Applied Mathematics (SIAM), 2017, pp. 1712–1744  DOI: 10.1137/16m1079336
  * [KMS18] Subhash Khot, Dor Minzer and Muli Safra  “Pseudorandom Sets in Grassmann Graph Have Near-Perfect Expansion”  In _Proc. 59th Annu. IEEE Sympos. Found. Comput. Sci.(FOCS)_ IEEE Computer Society, 2018, pp. 592–601  DOI: 10.1109/FOCS.2018.00062
  * [KR08] Subhash Khot and Oded Regev  “Vertex cover might be hard to approximate to within $2-\varepsilon$”  In _J. Comput. Sys. Sci._ 74.3, 2008, pp. 335–349  DOI: https://doi.org/10.1016/j.jcss.2007.06.019


# The Rhodes semilattice of a biased graph

Michael J. Gottstein and Thomas Zaslavsky  Department of Mathematics and
Statistics
Binghamton University (SUNY)
Binghamton, New York 13902-6000 USA<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

We reinterpret the Rhodes semilattices $R_{n}(\mathfrak{G})$ of a group
$\mathfrak{G}$ in terms of gain graphs and generalize them to all gain graphs,
both as sets of partition-potential pairs and as sets of subgraphs, and for
the latter, further to biased graphs. Based on this we propose four different
natural lattices in which the Rhodes semilattices and its generalizations are
order ideals.

###### Key words and phrases:

Rhodes semilattice of a group, gain graph, biased graph, partition-potential
pair, balanced closed subgraph

###### 2010 Mathematics Subject Classification:

Primary 06A12, Secondary 05B35, 05C22, 06C10

##  1\. Introduction

The Rhodes semilattice $R_{n}(\mathfrak{G})$ of a group $\mathfrak{G}$,
introduced by John Rhodes for semigroup theory (we refer to [2]), is a partial
ordering of pairs consisting of a partition and a potential system on subsets
of a finite set. We reinterpret the Rhodes semilattices as semilattices of
subgraphs in complete link gain graphs, which are graphs with edges labeled
from the group $\mathfrak{G}$. From this point of view the elements of the
Rhodes semilattice are closed, balanced subgraphs and the ordering is by gain-
graph inclusion. We use this reinterpretation to generalize Rhodes
semilattices to semilattices of closed, balanced subgraphs of any gain graph
and even more generally any biased graph. (All these concepts are defined
below.) Based on our graphic interpretation we propose three natural lattices
that contain the Rhodes semilattice and its generalizations as order ideals.

The graphical interpretation of $R_{n}(\mathfrak{G})$ was initiated by the
second author in a referee’s report on [2] and is mentioned in the published
version; see [2, Remark 6.1]. Here we provide the full generalization
suggested by that insight, with proof. Our partition-potential generalization
of $R_{n}(\mathfrak{G})$ is newly developed by the first author.

##  2\. A new perspective on the Rhodes semilattice

We begin with basic definitions, many of which are from [2], [3], and [5].

A _partial partition_ $\pi=\\{\pi_{1},\ldots,\pi_{j}\\}$ of a set $X$ is a
partition of a subset of $X$. The _support_ $\operatorname{supp}\pi$ is the
union of all blocks of $\pi$. The set of partial partitions of an $n$-element
set is denoted by $\Pi_{n}^{\S}$, which we partially order by refinement,
i.e., $\tau\leq\pi$ if every block of $\tau$ is contained in a block of $\pi$.
The smallest partial partition of $X$ is the empty partition, $\emptyset$; the
largest is the trivial partition, $\\{X\\}$.

For a graph $\Upsilon$ we define the partition of $V(\Upsilon)$ induced by
$\Upsilon$ by $\pi(\Upsilon)=\\{V(D):D\text{ is a component of }\Upsilon\\}$.

Let $X$ be a finite set and $\mathfrak{G}$ a group. Given $I\subseteq X$, we
denote by $\mathfrak{G}^{I}$ the collection of all functions
$\theta:I\rightarrow\mathfrak{G}$; we call such a function a _potential
function_ on $I$. The group acts on the left of $\mathfrak{G}^{I}$ by
$(g\theta)(x)=g\theta(x)$; we call an element of the quotient set
$\mathfrak{G}^{I}/\mathfrak{G}$ a _potential_ for $I$ ([2] calls it a “cross
section”).

A _potential system_ for a partial partition $\pi$ is a collection of
potentials on the blocks of $\pi$. Formally, if $\theta:Y\to\mathfrak{G}$ and
$\eta:Z\to\mathfrak{G}$, where $Y$ and $Z$ are any subsets of $X$ that contain
$\operatorname{supp}\pi$, we write $\eta\sim_{\pi}\theta$ if
$\eta|_{\pi_{i}}\in\mathfrak{G}\cdot\theta|_{\pi_{i}}$ for each block
$\pi_{i}$ in $\pi$; then $\sim_{\pi}$ is an equivalence relation. We denote
the equivalence class of $\theta\in\mathfrak{G}^{I}$ for a partial partition
$\pi$ by $[\theta]_{\pi}$; this is a _potential system_ on $\pi$.

The _Rhodes semilattice_ (see [2, section 3]) is the set of all pairs
$(\pi,[\theta]_{\pi})$ in which $[\theta]_{\pi}$ is a potential system on
$\pi$, which we call _partition-potential pairs_. They are partially ordered
by restriction; that is, $(\tau,[\eta]_{\tau})\leq(\pi,[\theta]_{\pi}])$ if
$\tau$ refines $\pi$ and $[\eta]_{\tau}=[\theta]_{\tau}$. The Rhodes
semilattice has a meet operation defined by
$(\pi,[\theta]_{\pi})\wedge(\tau,[\eta]_{\tau})=(\rho,[\theta]_{\rho})=(\rho,[\eta]_{\rho})$,
where $\rho$ is the partition of
$\operatorname{supp}\rho=\operatorname{supp}\pi\cap\operatorname{supp}\tau$
induced by the equivalence relation $\sim$ defined on
$\operatorname{supp}\rho$ in the following way: $x\sim y$ if and only if there
exist blocks $\tau_{i}$ and $\pi_{j}$ such that $x,y\in\tau_{i}\cap\pi_{j}$
and $\theta(x)^{-1}\theta(y)=\eta(x)^{-1}\eta(y)$. To distinguish this
representation of the Rhodes semilattice from the graphical one to be defined,
we call it the _partition-potential Rhodes semilattice_.

In what follows $\Gamma=(X,E)$ will denote a graph, which may have loops and
multiple edges unless it is said to be simple. If $e\in E$,
$\nu_{\Gamma}(e)=\\{v,w\\}$ means $e$ has endpoints $v,w$ (a multiset to
account for loops). If $\Upsilon\subseteq\Gamma$ is a subgraph, $V(\Upsilon)$
is its vertex set and $E(\Upsilon)$ is its edge set. We will be most
interested in the subgraph induced on a subset $I$ of $X$, which is
$\Gamma{:}I=(I,E{:}I)$ where

$E{:}I=\\{e\in E:\nu_{\Gamma}(e)\subseteq I\\},$

and the subgraph induced by a partial partition $\pi$ of $X$, which is

$\Gamma{:}\pi=\bigcup\\{(\Gamma{:}\pi_{i}):\pi_{i}\in\pi\\}.$

A _gain graph_ , denoted by $\Phi=(\Gamma,\phi,\mathfrak{G})$, is a graph
equipped with a _gain function_ $\phi$. The gain function is defined on the
edges of the graph to the group $\mathfrak{G}$, such that reversing the
direction of an edge inverts the gain. We write $\phi(e;v,w)$ in order to
indicate the sense in which the gain is measured; thus
$\phi(e;w,v)=\phi(e;v,w)^{-1}$. The gain of a path is its edge gain product;
thus a path $P=v_{0}e_{1}v_{1}e_{2}\cdots e_{k}v_{k}$ has gain
$\phi(P)=\phi(e_{1};v_{0},v_{1})\phi(e_{2};v_{1},v_{2})\cdots\phi(e_{k};v_{k-1},v_{k}).$
A circle is called _balanced_ if its gain (considered as a closed path) is
$1$; this property is independent of its representation as a closed path. A
subgraph $\Upsilon$ of a gain graph $\Phi$ is balanced if every circle in
$\Upsilon$ is balanced. It is _closed and balanced_ if it is balanced and
whenever there is a balanced circle $C\subseteq\Phi$ such that $C\setminus
e\in\Upsilon$, then $e\in E(\Upsilon)$.

######  Lemma 2.1.

L1 In a balanced gain graph, the gain of a path depends only on its initial
and final vertices.

###### Proof.

This is implicit in the proof of [3, Lemma 5.3]. ∎

A _potential function_ for a balanced gain graph $\Phi$ is a function
$\theta:V(\Phi)\rightarrow\mathfrak{G}$ such that
$\phi(e;v,w)=\theta(v)^{-1}\theta(w)$ for each edge $e\in\Gamma$.

######  Lemma 2.2.

L2 Let $\Phi$ be a gain graph. There is a potential function $\theta$ for
$\Phi$ if and only if $\Phi$ is balanced. Every potential function in
$[\theta]_{\pi(\Phi)}$ defines the same gains on $\Phi$, and every potential
function defining the gains of $\Phi$ is in $[\theta]_{\pi(\Phi)}$.

###### Proof.

Balance is clear by computing the gain of a circle.

Conversely, we can obtain a potential function for a balanced gain graph
$\Phi$ by choosing a root node $r$ for each component of $\Phi$ and defining
$\theta(v)=\phi(P_{rv})$ where $P_{rv}$ is an $rv$-path in a component of
$\Phi$. This is well defined because the gain function in a balanced gain
graph is path independent.

Suppose $\phi(e)=\theta(v)^{-1}\theta(w)$ and $\eta$ is another potential
function of $\Phi$, then (because the gain function in a balanced subgraph is
path independent) for any path $P_{vw}$ in $\Phi$,
$(\theta(v))^{-1}\theta(w)=\phi(P_{vw})=(\eta(v))^{-1}\eta(w)$. This is true
for every $v,w$ in a block of $\pi(\Phi)$, so by definition
$\eta\in[\theta]_{\pi(\Phi)}$. Conversely, if $\eta\in[\theta]_{\pi(\Phi)}$
then $(\theta(v))^{-1}\theta(w)=(\eta(v))^{-1}\eta(w)$ for any $v,w$ in a
block of $\pi(\Phi)$, so
$\phi(e)=(\theta(v))^{-1}\theta(w)=(\eta(v))^{-1}\eta(w)$. ∎

The _group expansion_ of a graph $\Gamma$ is denoted by
$\mathfrak{G}{\cdot}\Gamma=(V(K_{n}),\mathfrak{G}\times E(\Gamma),\phi)$,
where $\nu_{\mathfrak{G}{\cdot}\Gamma}(g,e)=\nu_{\Gamma}(e)$. To define the
gain of $(g,e)$ we must take account of the endpoints,
$\nu_{\mathfrak{G}{\cdot}\Gamma}(g,e)=\\{v,w\\}$. For the sake of notation,
arbitrarily pick an orientation, $(e;v,w)$, and define $\phi(g,e;v,w)=g$,
$\phi(g,e;w,v)=g^{-1}$ for each $g$. In this notation, $(g,e)$ and
$(g^{-1},e)$ are different edges (unless $g=g^{-1}$) whose gains are

$\displaystyle\phi(g,e;v,w)=g,\ \phi(g,e;w,v)=g^{-1},$
$\displaystyle\phi(g^{-1},e;v,w)=g,\ \phi(g^{-1},e;w,v)=g.$

######  Definition 2.3.

The _graphic Rhodes semilattice of $\mathfrak{G}{\cdot}K_{n}$_, denoted by
$R(\mathfrak{G}{\cdot}K_{n})$, is the family of closed and balanced subgraphs
in $\mathfrak{G}{\cdot}K_{n}$, ordered by inclusion. Its meet operation is
intersection.

######  Theorem 2.4.

The partition-potential Rhodes semilattice $R_{n}(\mathfrak{G})$ is isomorphic
to the graphic Rhodes semilattice $R^{\textrm{b}}(\mathfrak{G}{\cdot}K_{n})$.

###### Proof.

In the natural correspondence between $R_{n}(\mathfrak{G})$ and
$R^{\textrm{b}}(\mathfrak{G}{\cdot}K_{n})$, the pair $(\pi,[\theta]_{\pi})\in
R(\mathfrak{G})$ corresponds to the subgraph of $\mathfrak{G}{\cdot}K_{n}$
whose components are complete subgraphs in each vertex set $\pi_{i}$ with
gains given by any potential function in $[\theta]_{\pi}$. We correspond a
closed and balanced subgraph $B$ of $\mathfrak{G}{\cdot}K_{n}$ to the pair
$(\pi(B),[\theta]_{\pi(B)})$, where $\theta$ is a potential function defining
the gains of $B$. In Theorem 3.6 we prove (in more generality) that this
correspondence is an isomorphism. ∎

Theorem 2.4 shows us how to generalize the Rhodes semilattice to gain and
biased graphs, which we do in the next section.

##  3\. Generalization to gain graphs

Let $\Phi$ be a gain graph with gain group $\mathfrak{G}$ and vertex set $X$.
Let $\pi=\\{\pi_{1},\ldots,\pi_{j}\\}$ be a partial partition of $X$ and
$[\theta]_{\pi}$ a potential system for $\pi$. We define a function
$\mathbf{B}$ from partition-potential pairs to subgraphs of $\Phi$ by

$\mathbf{B}(\pi,[\theta]_{\pi}):=(\operatorname{supp}\pi,\\{e\in
E(\Phi{:}\pi):(\exists i)\ \nu_{\Gamma}(e)=\\{v,w\\}\subseteq\pi_{i},\
\phi(e)=\theta^{-1}(v)\theta(w)\\}).$

This subgraph is well defined, by L2.

We say $(\pi,[\theta]_{\pi})$ is a _$\Phi$ -connected_ partition-potential
pair if $\mathbf{B}(\pi,[\theta]_{\pi_{i}})$ is connected for each
$\pi_{i}\in\pi$.

######  Definition 3.1.

Let $\Phi$ be a gain graph with vertex set $X$ and group $\mathfrak{G}$. The
_partition-potential Rhodes semilattice of $\Phi$_, denoted by $R(\Phi)$, is
the set of all $\Phi$-connected partition-potential pairs of $\Phi$. The meet
operation is the same as it is for $R_{n}(\mathfrak{G})$.

We can see that $R_{n}(\mathfrak{G})=R(\mathfrak{G}{\cdot}K_{n})$, so the
partition-potential Rhodes semilattice of a gain graph is a generalization of
the original Rhodes semilattice.

######  Definition 3.2.

Let $\Phi$ be a gain graph. The _graphic Rhodes semilattice of $\Phi$_,
denoted by $R^{\textrm{b}}(\Phi)$, is the family of closed and balanced
subgraphs, ordered by inclusion. The meet operation is gain graph
intersection.

######  Lemma 3.3.

L3 Let $\Phi$ be a gain graph, $\pi$ a partial partition of $X$, and
$(\pi,[\theta]_{\pi})\in R_{n}(\Phi)$. Then $\mathbf{B}(\pi,[\theta]_{\pi})$
is a closed and balanced subgraph of $\Phi$.

###### Proof.

$\mathbf{B}(\pi,[\theta]_{\pi})$ is balanced because it has gains defined by a
potential function. It is closed because if $v,w$ are in a component of
$\mathbf{B}(\pi,[\theta]_{\pi})$, then the edge $e$ with
$\nu_{\Gamma}(\theta^{-1}(v)\theta(w),e)=\\{v,w\\}$ and gain
$\phi(e;v,w)=\theta^{-1}(v)\theta(w)$, if it exists in $\Phi$, is in
$\mathbf{B}(\pi,[\theta]_{\pi})$ by the definition of $\mathbf{B}$. ∎

######  Lemma 3.4.

L3.5 Let $\Phi$ be a gain graph. $\mathbf{B}$ is a surjection onto the closed
and balanced subgraphs of $\Phi$.

###### Proof.

By L3 we know the image of $\mathbf{B}$ is contained in the set of closed and
balanced subgraphs.

Let $B$ be a closed and balanced subgraph. By L2 there is a potential function
$\theta$ defining its gains. If $e\in B$ then its vertices are in the same
block of $\pi(B)$; it follows that $e$ is in
$\mathbf{B}(\pi(B),[\theta]_{\pi(B)})$, which implies that
$B\subseteq\mathbf{B}(\pi(B),[\theta]_{\pi(B)})$.

Now let $e$ be an edge of $\mathbf{B}(\pi(B),[\theta]_{\pi(B)})$. The vertices
of $e$ are in one block of $\pi(B)$ and its gain
$\phi(e;v,w)=\theta(v)^{-1}\theta(w)$. Since $B$ is closed and $\theta$ is a
potential function for $B$, $e$ is in $B$; therefore
$B=\mathbf{B}(\pi(B),[\theta]_{\pi(B)})$. ∎

######  Lemma 3.5.

L4 Let $\Phi$ be a gain graph. If we restrict the domain of $\mathbf{B}$ to
$R(\Phi)$, then $\mathbf{B}$ is injective.

###### Proof.

Suppose $(\tau,[\eta]_{\tau})\in R(\Phi)$ and $\mathbf{B}(\tau,[\eta])=B$. We
showed in the previous proof that $B=\mathbf{B}(\pi(B),[\theta]_{\pi(B)})$. We
now prove that, if $(\tau,[\eta]_{\tau})\neq(\pi(B),[\theta]_{\pi(B)})$, then
$(\tau,[\eta]_{\tau})\notin R(\Phi)$.

First we observe that every block of $\pi(B)$ must be contained in a block of
$\tau$. Thus, $\pi(B)\leq\tau$. If two blocks $\pi_{i},\pi_{j}\in\pi(B)$ are
contained in the same block $\tau_{k}$, or if some $\pi_{i}\subset\tau_{k}$,
then $\tau_{k}$ does not induce a connected subgraph of $B$; such a partition-
potential pair cannot be in $R(\Phi)$. Thus, the blocks of $\pi(B)$ are in
distinct blocks of $\tau$ and are equal to those blocks; that is,
$\tau=\pi(B)$.

Now L2 implies that $[\theta]_{\tau}=[\theta]_{\pi(B)}$, completing the proof.
∎

######  Theorem 3.6.

Let $\Phi$ be a gain graph. Then $R(\Phi)$ is isomorphic to
$R^{\textrm{b}}(\Phi)$.

###### Proof.

We have shown $\mathbf{B}$ is a bijection. Now we prove it preserves order. By
the definition $(\tau,[\eta]_{\tau})\leq(\pi,[\theta]_{\pi})$ if and only if
each block $\tau_{i}\in\tau$ is contained in some block of $\pi$ and
$\mathfrak{G}{\cdot}\theta|_{\tau_{i}}=\mathfrak{G}{\cdot}\eta|_{\tau_{i}}$.
Equivalently, each component of $\mathbf{B}(\tau,[\eta]_{\tau})$ is contained
in a component of $\mathbf{B}(\pi,[\theta]_{\pi})$; that is,
$\mathbf{B}(\tau,[\eta]_{\tau})\subseteq\mathbf{B}(\pi,[\theta]_{\pi})$. ∎

######  Example 3.7 (Group expansions).

If $\Phi$ is a group expansion we can simplify the description of the graphic
Rhodes semilattice. Suppose $\Gamma$ is a simple graph and $\mathfrak{G}$ is a
group. A subgraph $\Psi\subseteq\Gamma$ is _closed in $\Gamma$_ if, whenever
$e$ is an edge of $\Gamma$ such that $\Psi\cup\\{e\\}$ contains a circle that
contains $e$, then $e$ is in $\Psi$.

For a subgraph $B$ of $\mathfrak{G}{\cdot}\Gamma$, by $p(B)$ we mean the
projection of $B$ onto the underlying graph $\Gamma$. If $B$ is closed and
balanced subgraph, then $p(B)$ is a closed subgraph in $\Gamma$. Conversely,
if $C$ is closed in $\Gamma$ and $[\theta]_{\pi(C)}$ is a potential system on
$\pi(C)$, then $\mathbf{B}(\pi(C)),[\theta]_{\pi(C)})$ is a closed and
balanced subgraph of $\mathfrak{G}{\cdot}\Gamma$.

This shows that the properties of closure and balance for elements of
$R^{\textrm{b}}(\mathfrak{G}{\cdot}\Gamma)$ can be split into closure of the
underlying base graph in $\Gamma$ and an arbitrary choice of potential for
that base graph. If in particular $\Gamma=K_{n}$, the closed subgraphs
correspond bijectively to the partial partitions of the vertex set of $K_{n}$.

##  4\. Generalization to biased graphs

A _biased graph_ is a graph together with a class of circles (edge sets or
graphs of simple closed paths), called _balanced circles_ , such that no theta
subgraph contains exactly two balanced circles. We denote the graph along with
the set of balanced circles by $\Omega=(\Gamma,\mathscr{B})$. We define closed
and balanced subgraphs of a biased graph exactly the same as we did for gain
graphs. A subgraph $\Upsilon$ of a biased graph $\Omega$ is balanced if every
circle in $\Upsilon$ is balanced and is _closed and balanced_ if in addition
whenever there is a balanced circle $C\in\Omega$ such that $C\setminus
e\in\Upsilon$, $C$ is in $\Upsilon$. A gain graph $\Phi$ with underlying graph
$\Gamma$ gives rise to the biased graph
$\langle\Phi\rangle=(\Gamma,\mathscr{B}(\Phi))$ [3, Section 5].

The definition of the graphic Rhodes semilattice of a gain graph depends on
the subgraphs and the balanced circles in the subgraph. Since the balanced
circles of a gain graph define a biased graph, we can readily generalize the
definition of the graphic Rhodes semilattice to biased graphs.

######  Definition 4.1.

Let $\Omega$ be a biased graph. The _Rhodes semilattice of $\Omega$_, denoted
by $R^{\textrm{b}}(\Omega)$, is the family of closed and balanced subgraphs in
$\Omega$ ordered by inclusion.

A difference between bias and gains is that we cannot state a partition-
potential description of balanced subgraphs of a biased graph. This is not a
trivial difference, since not all biased graphs can be given gains; see [3,
Example 5.8].

##  5\. The four lattices

In this section we have a biased graph $\Omega$. We treat a gain graph $\Phi$
as the biased graph $\langle\Phi\rangle$. We propose to embed the Rhodes
semilattice as an order ideal of a lattice. The simplest such lattice is the
first.

######  Definition 5.1.

The _trivial Rhodes lattice_ of $\Omega$, denoted by $\widehat{R}(\Omega)$, is
$R(\Omega)$ with an added top element $\hat{1}$.
$\widehat{R}(\mathfrak{G}{\cdot}K_{n})$ is the Rhodes lattice
$\widehat{R}_{n}(\mathfrak{G})$ defined in [2]. (This lattice is trivial only
from the viewpoint of partially ordered sets; we do not mean it is useless.)

With the benefit of our subgraph interpretation we propose more substantial
kinds of Rhodes lattices.

The frame matroid of $\Omega$ is a matroid $\mathbf{F}(\Omega)$ on the edge
set $E(\Omega)$ [4, Section 2]. We regard each edge set $S$ as the spanning
subgraph $(V(\Omega),S)$. From this viewpoint the flats of $\Omega$ become
frame-closed spanning subgraphs of $\Omega$.

######  Definition 5.2.

The _frame Rhodes lattice_ of $\Omega$, denoted by $R^{\mathbf{F}}(\Omega)$,
is the family of all frame-closed subgraphs of $\Omega$; that is, the set of
all frame-closed spanning subgraphs of all induced subgraphs of $\Omega$.

The lift matroid of $\Omega$ is a matroid $\mathbf{L}(\Omega)$ on the set
$E(\Omega)$ [4, Section 4]. We regard each edge set $S$ as a spanning subgraph
of $\Omega$, $(V(\Omega),S)$. From this viewpoint the flats of $\Omega$ become
spanning subgraphs of $\Omega$ whose edge sets are closed in
$\mathbf{L}(\Omega)$. There is a natural one-point extension of the lift
matroid, called the _complete_ or _extended lift matroid_ , whose balanced
flats are the same as those of $\mathbf{L}(\Omega)$; the following definition
extends to it but we omit the formal definition.

######  Definition 5.3.

The _lift Rhodes lattice_ , denoted by $R^{\mathbf{L}}(\Omega)$, is the family
of all lift-closed subgraphs of $\Omega$; that is, the set of all lift-closed
spanning subgraphs of all induced subgraphs of $\Omega$.

A subgraph $\Upsilon$ is called _balance-closed_ (which does not mean balanced
and does not mean closed in a matroid) if, whenever there is a balanced circle
$C\in\Omega$ such that $C\setminus e\in\Upsilon$, then $C\subseteq\Upsilon$.

######  Definition 5.4.

The _balance-closed Rhodes lattice_ , denoted by $R^{\mathbf{BC}}(\Omega)$, is
the family of balance-closed subgraphs of all induced subgraphs of $\Omega$,
ordered by inclusion.

The graphic Rhodes semilattice is the order ideal of balanced subgraphs in
each of these proposed Rhodes lattices.

We plan to study these lattices in order to draw conclusions about the
structure of the original Rhodes semilattice and the generalizations to gain
and biased graphs.

## References

  * [1] T.A. Dowling, “A class of geometric lattices based on finite groups”. J. Combin. Theory Ser. B 14 (1973), 61–86. Erratum. ibid. 15 (1973), 211.
  * [2] Stuart Margolis, John Rhodes, and Pedro V. Silva, ”On the Dowling and Rhodes lattices and wreath products”. J. Algebra 578 (2021), 55–91.
  * [3] Thomas Zaslavsky, ”Biased graphs. I. Bias, balance and gains”. J. Combin. Theory Ser. B, 47 (1989), 32–52.
  * [4] Thomas Zaslavsky, ”Biased graphs II. The three matroids”, J. Combin. Theory, Ser. B 51 (1991) 46–72.
  * [5] Thomas Zaslavsky, ”Biased graphs. IV: Geometrical realizations”. J. Combin. Theory Ser. B, 89 (2003), no. 2, 231–297.