# SSIG: A Visually-Guided Graph Edit Distance for Floor Plan Similarity

Casper C. J. van Engelenburg1, 2, Seyran Khademi1, 2, Jan C. van Gemert2
1AiDAPT Lab, 2Computer Vision Lab, Delft University of Technology
{c.c.j.vanengelenburg, s.khademi<EMAIL_ADDRESS>
###### Abstract

††This paper is published as a workshop paper at ICCV 2023

We propose a simple yet effective metric that measures structural similarity
between visual instances of architectural floor plans, without the need for
learning. Qualitatively, our experiments show that the retrieval results are
similar to deeply learned methods. Effectively comparing instances of floor
plan data is paramount to the success of machine understanding of floor plan
data, including the assessment of floor plan generative models and floor plan
recommendation systems. Comparing visual floor plan images goes beyond a sole
pixel-wise visual examination and is crucially about similarities and
differences in the shapes and relations between subdivisions that compose the
layout. Currently, deep metric learning approaches are used to learn a pair-
wise vector representation space that closely mimics the structural
similarity, in which the models are trained on similarity labels that are
obtained by Intersection-over-Union (IoU). To compensate for the lack of
structural awareness in IoU, graph-based approaches such as Graph Matching
Networks (GMNs) are used, which require pairwise inference for comparing data
instances, making GMNs less practical for retrieval applications. In this
paper, an effective evaluation metric for judging the structural similarity of
floor plans, coined SSIG (Structural Similarity by IoU and GED), is proposed
based on both image and graph distances. In addition, an efficient algorithm
is developed that uses SSIG to rank a large-scale floor plan database. Code
will be openly available.

##  1 Introduction

Floor plans, as one of the most celebrated media for communicating and
thinking in architectural design, are horizontal orthographic projections of a
particular building’s floor. Floor plans are simple but powerful
representations of space, conveying a richness of information about the
compositional structure of buildings – the shapes, proportions, and relations
between the building’s individual subdivisions. The compositional structure of
a building is a key factor in the architectural quality.

The multi-modal nature of floor plans as pictorial (as images), graphical (as
a set of geometrical entities), and topological (as graphs) entities, leverage
different data modeling and machine learning frameworks for digital
representation and machine understanding in the domain of architectural
design. In particular, floor plan synthesis, such as floor plan generation [9,
10, 18] or style transfer [1], has often been explored. Another major research
line is that of architectural element recognition in which the goal is to
automatically learn to extract geometrical features from floor plan images
_e.g_. walls or furniture [7, 3, 14].

Despite the developments in the generative models for floor plans, there have
been few valuable attempts at developing data-driven methods to reason about
floor plans, such as floor plan retrieval by effectively comparing data
instances _i.e_. measuring similarity. As found by [13], structural similarity
judgment for floor plans is a challenging task – it is multi-faceted and is
about the shapes and proportions, visual features, and relations between the
floor plan’s subdivisions. Generally speaking, comparing floor plans is about
finding commonalities in the underlying structure, hence referred to as
structural similarity.

The most effective methods for measuring structural similarity between floor
plans rely on deeply learned vector representations with the goal to make the
feature vector space reflect structural similarity _i.e_. the distance between
feature vectors is small for structurally similar floor plans and vice versa.
To train such models, [8] propose to use weakly supervised deep metric
learning setup by obtaining similarity labels through Intersection-over-Union
(IoU). To compensate for the lack of structural awareness in IoU, [13, 4] use
Graph Matching Networks (GMNs) [6] that naturally embed topological
information in the feature vectors. Besides the fact that GMNs hinder the
practical usability [22], we believe that simpler frameworks could learn
similarly effective vector representations when the objective is better
aligned with structural similarity in the first place. In our work, we develop
an improved objective and opt for simplicity. We start by investigating the
merits and bottlenecks of well-known image- and graph-based similarity
metrics.

The Intersection-over-Union (IoU) is often used as an evaluation metric to
measure structural similarity _e.g_. to find similar or matching pairs for
deep metric learning models [13, 4], to evaluate the accuracy of structural
reasoning algorithms [7], or to evaluate the output diversity of generative
models [9]. In this paper, we show how IoU fails to robustly measure
structural similarity because 1) IoU is overly sensitive to geometric
perturbations in the image representation of a floorplan and 2) IoU is often
unable to identify important differences in the connectivity between space
subdivisions such as doors, walls, openings.

Floor plans have been successfully modelled as graphs [9, 13], which allows
for graph matching algorithms to compute a distance (similarity) between a
pair of graphs. For example, the Graph Edit Distance (GED) computes the
minimum cost of converting a source graph into another (isomorphic to it)
target graph [17]. For example, [9] uses GED to check the compatibility
between generated layouts. Although GED effectively captures topological
similarity and with that addresses some of IoU’s limitations, we show that GED
has inherent limitations when used for measuring structural similarity.

Independently, image- and graph-based similarity metrics lack to holistically
capture the structural similarity between floor plans. Therefore, instead of
treating images and graphs in isolation, we propose an evaluation metric that
ascertains closeness based on the floor plans’ corresponding image and graph,
called SSIG. In addition, an efficient algorithm based on SSIG is used to rank
RPLAN [26], a large-scale floor plan database, on structural similarity. Our
contributions include:

  * •

A study on the distributions and correlations between IoU and GED on a large-
scale floor plan database, with one main finding: IoU and GED independently
fail to robustly capture structural similarity.

  * •

A proposed simple yet powerful measure for the structural similarity of floor
plans.

  * •

An effective ranking technique to sort a large floor plan database, hence
developing a starting point for proper evaluation and training of floor plan
retrieval models.

##  2 Related works

#### Floor plan representations.

Floor plans are digitally represented in various ways that each emphasize
different components of interest _e.g_. as images allowing to model fine-
grained details such as materialization and furniture [21, 5], geometries that
explicitly model the shapes, proportions and locations of the shapes of the
subdivisions [13], and graphs that model the relations between the
subdivisions [9, 13, 18, 12].

#### Floor plan analysis.

Traditional approaches on floor plan analysis – or similar data such as
documents [28] or UIs [2] – involve primitive heuristics to approximate a
floor plan distance and are, hence, instance-specific [11]. More recently,
two-step approaches became the standard to approximate similarity of floor
plans [27, 16, 20, 23, 21, 19, 25, 12], in which the first step involves
extracting relevant features from an image _e.g_. a graph representation of
the room connectivity [12] and the second step computes a distance based on
the extracted features _e.g_. a subgraph matching algorithm for graph
similarity [16]. Besides the fact that the two-step approaches are prone to
error propagation, the two-step approaches assume that the extracted features,
such as the access graph, completely and accurately capture all aspects of
floor plans. In our work, we challenge this assumption, particularly
concerning semantic image and access graph representations of floor plans.

#### Structural similarity by Graph Neural Networks.

Recently, Graph Neural Networks (GNN) have been proposed to learn floor plan
similarity [13, 8, 4], learning floor plan vector representations in an end-
to-end fashion. Most successfully, [4, 13] leverage Graph Matching Networks
(GMN) [6] in combination with weakly-supervised labels based on the IoU. Due
to the cross-graph information sharing in GMNs, [13] found that GMNs
compensate for the lack of structural awareness in IoU and naturally learn to
embed the structural commonalities in the vector representations. A critical
shortcoming of GMNs is that vector representations cannot be computed in
isolation, therefore limiting the practical usability. We believe that the
main reason that cross-graph information sharing is needed is that essentially
the wrong objective is injected – that is to mimic a distance metric inspired
by IoU. We show that our metric, which is a combination between visual- and a
graph-inspired similarity scores, can be leveraged to rank a floor plan
database for which the retrievals share similar characteristics as to the
works in [13].

##  3 Method

In this section, we develop a simple yet effective strategy to numerically
approximate structural similarity between floor plans. Formally, we seek a
similarity function $s\left(\cdot,\cdot\right)$ between two floor plans
$p_{1}$ and $p_{2}$:

$s\left(p_{1},p_{2}\right):\mathcal{P}\times\mathcal{P}\rightarrow\mathbb{R}^{+},$
(1)

in which $\mathcal{P}$ is the (mathematical) space of a floor plan.
$\mathcal{P}$ can be multi-modal _e.g_. a joint space of images and graphs:
$\mathcal{P}=\mathbb{R}^{H\times W\times 3}\times\mathcal{G}$. The goal is to
make $s$ closely mimic the structural similarity between floor plans: the
larger the structural similarity the larger $s$ and vice versa.

The section is split into three main parts. The first part explores the
modeling and attribution of floor plans, (Subsec. 3.1). The second part
investigates known and frequently used image- and graph-based similarity
metrics (Subsec. 3.2, 3.3). The third part describes the new similarity metric
(Subsec. 3.4), and provides an algorithm that can efficiently rank a floor
plan dataset (Subsec. 3.5).

###  3.1 Floor plan representations

In this work, we consider three well-known floor plan representations: 1) the
pictorial image, 2) the semantic image, and 3) the access graph.

Figure 1:  Floor plan representations. Left: Pictorial image. Center: Semantic
image. Right: Access graph.

#### Pictorial image

Conventionally, floor plans are modeled as images. All floor plan images that
are either grayscale or RGB and do not contain any categorial information at
pixel level about the semantics of the subdivisions are referred to as
pictorial images, $I\in\mathcal{I}=\mathbb{R}^{H\times W(\times 3)}$ (Fig. 1,
Left).

#### Semantic image

Floor plans are structured arrangements consisting of subdivisions – areas
such as a living room or bathroom, openings such as doors or windows, and
separators such as walls or railings. All floor plans that have categorical
labels for subdivision areas and/or semantic information encoded at pixel
level are referred to as semantic images in our definition,
$X\in\mathcal{X}=\\{0,1,\ldots,N_{c}\\}^{H\times W}$, in which $N_{c}$ is the
number of subdivision categories (Fig. 1, Center). In the semantic image
representation, pixel values correspond to subdivision categories _e.g_. 1
$\leftarrow$ ”living room”, 2 $\leftarrow$ ”bathroom”, 16 $\leftarrow$
”internal wall”, etc.

#### Access graph

Floor plans often have clearly identifiable relations between subdivisions
_e.g_. access information between two rooms by means of a door. Even though
semantic images efficiently capture the shapes and categories of the
subdivisions, semantic image maps do not explicitly define the relations
between the subdivisions.

Instead, floor plans can be attributed an access graph, directly laying bare
the topological structure of the subdivisions (Fig. 1, Right). Formally, a
graph is defined as a 4-tuple $g=\left(N,E,\mu,\nu\right)$, in which $N$ is a
finite set of nodes, $E$ is the set of edges, and $\mu$ and $\nu$ are the node
and edge labelling functions respectively [15]. The nodes in an access graph
correspond to the areas, and the edges to connections between the areas.

Depending on the use-case and feature accessibility, the nodes and edges can
have (one or several) attributes. Usually, room-type information is encoded on
the nodes, and edges are only present if a door is in between two rooms, hence
edges do not have an attribute [9, 18, 24]. Even though we agree that access
connectivity is the most important relation between rooms, an important
relation is disregarded: room adjacency. Room adjacency is an influential
factor _e.g_. for decisions around privacy, structural integrity, and
function. Access graphs, in the remainder of this work, have therefor a
connectivity-type attribute, which is either ”door” or ”adjacent”.

Proposed by [8], it is noteworthy to mention that several approaches compute
the edge features. Specifically, edge features between two nodes are computed
by pairwise geometric features, such as the ratio between areas or the
relative position.

###  3.2 Intersection-over-Union

Figure 2:  Visual- and graph-based similarity metrics for floor plans. A) IoU
can be directly used as a measure for similarity between semantic image
representations. mIoU between the semantic images is computed through Eq. 3
(floor plans have 3 semantic labels); in this case being 0.90 which is a
relatively high number. B) nGED is computed through Eqs. 5 and 6: GED equals
the shortest edit path which is 2; the orders of the graphs are both 3, hence
nGED $=2/9$. When $\gamma=0.4$ (a typical value),
$1-\text{nGED}\left(g_{1},g_{2}\right)^{\gamma}\approx 0.45$. The visual-based
similarity ($0.90$) and graph-based ($0.45$) similarity scores are
significantly different which indicates that in some cases IoU and GED
negatively correlate in ”seeing” similarity.

The Intersection-over-Union (IoU) is not considered a proper distance metric,
but it is a well-adopted evaluation metric for tasks where measuring the
overlap between regions or sets is important, such as in object detection or
segmentation tasks. In turn, IoU is often used as a measure for estimating
structural similarity in various applications related to floor plans _e.g_.
for finding similar or matching floor plan pairs for similarity learning [13,
4], evaluating the accuracy of segmentation algorithms [7], or to check the
diversity of outputs in floor plan generation [9]. The IoU is commonly defined
as the fraction between the amount of overlap and the union of two binary
images $X_{1}$ and $X_{2}$ $\in\\{0,1\\}^{H\times W}$:

$\text{IoU}\left(X_{1},X_{2}\right)=\frac{X_{1}\cap X_{2}}{X_{1}\cup X_{2}}.$
(2)

When more classes are present in an image _e.g_. in the case of semantic
images ($X_{1},X_{2}\in\mathcal{X}$), IoU is computed per class and the
results are aggregated to find the final score. For example, the mean IoU
(mIoU) computes the average IoU, with respect to the ground truth, across the
different classes, therefore treating every class similarly regardless of its
proportion to the image size.

$\text{mIOU}\left(X_{1},X_{2}\right)=\frac{1}{N_{c}}\sum_{c=1}^{N_{c}}\text{IoU}\left(X_{1}==c,X_{2}==c\right),$
(3)

where $N_{c}$ is the number of classes.

Even though IoU is a powerful metric that in part is suitable for
approximating structural similarity between floor plans, IoU frequently fails
on both extremes: 1) false-negative: low IoU - high structural similarity, and
2) false-positive: high IoU - low structural similarity. 1) IoU is over-
sensitive to irrelevant geometric perturbations in the image _e.g_.
translation, rotations, and scale. For example, when identical floor plans are
centered at different locations in an image, the IoU will be low; falsely
indicating that the floor plans are not structurally similar. 2) IoU
frequently fails to correctly identify the connectivity in floor plans _e.g_.
small ”air gaps” between rooms are hardly identified by IoU yet are indicative
of structural characteristics (see example in Fig. 2).

###  3.3 Graph Edit Distance

The Graph Edit Distance (GED) [17], is another measure to judge similarity
between floor plans, used for _e.g_. compatibility of generated layouts [10]
or for floor plan retrieval [12]. GED is a metric that quantifies the
similarity (dissimilarity) between two graphs by computing the minimum cost of
transforming one graph $g_{1}$ into (a graph isomorphic to) $g_{2}$ in terms
of a sequence of edit operations $\left(e_{1},e_{2},\ldots,e_{j}\right)$,
referred to as the edit path. Edit operations typically include node and edge
deletions, insertions, and substitutions, which can have different costs.
Given a set of graph edit operations $e_{i}$ and associated costs
$c_{i}\left(e_{i}\right)$, the $\text{GED}\left(g_{1},g_{2}\right)$ is
formally defined as,

$\text{GED}\left(g_{1},g_{2}\right)=\min_{\left(e_{1},e_{2},\ldots,e_{j}\right)\in\pi\left(g_{1},g_{2}\right)}\sum_{j=1}^{k}c_{j}\left(e_{j}\right),$
(4)

in which $\pi\left(g_{1},g_{2}\right)$ denotes the set of edit paths that
transforms $g_{1}$ into (a graph isomorphic to) $g_{2}$. In our work, all edit
operations have the same cost, hence Eq. 4 becomes,

$\text{GED}\left(g_{1},g_{2}\right)=\min_{k}\left(e_{1},e_{2},\ldots,e_{k}\right),$
(5)

such that
$\left(e_{1},e_{2},\ldots,e_{k}\right)\in\pi\left(g_{1},g_{2}\right)$. GED in
this case is equivalent to the smallest number of edit operations. To
normalize the GED between 0 and 1, we define the Normalized Graph Edit
Distance (nGED) by dividing GED with the product of the orders111Note that Eq.
6 does not strictly normalizes GED. Even so, for floor plans _e.g_., in [26],
nGED will always be below 1. Furthermore, the product of the orders, instead
of for example the sum, nicely spreads the nGED distributions. – the number of
nodes – of the graphs ($\left|N_{1}\right|$ and $\left|N_{2}\right|$):

$\text{nGED}\left(g_{1},g_{2}\right)=\frac{\text{GED}\left(g_{1},g_{2}\right)}{\left|N_{1}\right|\cdot\left|N_{2}\right|}.$
(6)

nGED can be used as of measure of closeness between the topology of two floor
plans, in which a small nGED suggests that two floor plans share topological
characteristics, which could be, for example, indicative of commonalities in
flow or function between two buildings.

nGED has several limitations. First of all, the amount of different floor
plans possible for a particular access graph is huge, for which many
corresponding floor plans pairs are not structurally similar (see Fig. 3).
Second, it is unclear which edit costs align with structural similarity: Is
the removal of a node or an edge more costly? Does the node label matter? etc.
Third, nGED is compute-heavy which limits its use in real-time systems _e.g_.
floor plan retrieval in search engines. We elaborate more on the shortcomings
in Subsec. 4.2.

In Subsec. 4.3 we investigate the trends and correlations between nGED and
mIoU on RPLAN [26] empirically.

Figure 3:  Graph to image examples. Each row represents an access graph
(column 1) and several randomly selected corresponding floor plans semantic
images (columns 2 - 5).

###  3.4 A Visually-guided Graph Edit Distance

Independently, IoU and GED fail to holistically capture structural similarity
between floor plans. Therefore, instead of treating images and graphs
separately, we propose a metric that ascertains closeness based on the
semantic image and access graph. We define the similarity between a pair of
floor plans $(p_{1},p_{2})$,
$p_{i}=(X_{i},g_{i})\in\mathcal{X}\times\mathcal{G}$, as

$\text{SSIG}\left(p_{1},p_{2}\right)=\frac{\text{mIoU}\left(X_{1},X_{2}\right)+\left(1-\text{nGED}\left(g_{1},g_{2}\right)^{\gamma}\right)}{2}.$
(7)

Coined as SSIG (Structural Similarity by IoU and GED), 7 essentially computes
a weighted average between a IoU-based and a nGED-based similarity metric.
$\gamma\in\mathbb{R}^{+}$ is a weight that allows to tune between the
relevance of nGED w.r.t. mIoU: the higher $\gamma$ the less influence nGED and
vice versa.222Note that nGED $\in(0,1)$, hence increasing the power term
decreases nGED. For example for RPLAN [26], the mIoU and nGED distributions
are balanced when $\gamma=0.4$. Specifically, balanced distributions here
means that the IoU and nGED probability density functions have as much overlap
as possible.

###  3.5 Efficient algorithm for ranking

Even for small graphs, GED is a compute-heavy measure, usually taking several
seconds per floor plan pair. When SSIG is used for evaluation, pair mining, or
direct floor plan retrieval on large datasets, the time constrain hugely
limits practical usage. We propose an algorithm that drastically speeds up
retrieval and finds structurally similar pairs relatively fast.

First, mIoU is computed for every combination of floor plan pairs in the
dataset. Second, only the $n$ (set between 50 and 100) best scoring pairs on
mIoU for each floor plan identity are kept. Third, the SSIG is computed for
each remaining pair. Fourth, the corresponding lists for each floor plan
identity are ranked on SSIG in descending order.

The algorithm assumes that the best matches (highest SSIG scores) are found in
the $n$-best mIoU pairs. In the next session, we empirically find that the
assumption generally holds if $n$ is large enough. In Subsec. 4.4, we show
that for ranking RPLAN, the assumption holds for relatively small $n$. For a
dataset with size $N$ (usually between 10k and 100k), the algorithm is orders
of magnitude faster than brute-forcing through it.

An assessment of the ranking algorithm and relation to floor plan retrieval
systems are provided in the following section (Sec. 4).

##  4 Results and Evaluation

###  4.1 Data

In this paper, RPLAN [26] is used for analysis and evaluation. RPLAN is a
large-scale dataset containing floor plan images with semantically segmented
areas, consisting of $>$80k single-unit apartments across Asia. We further
cleaned the dataset, where there were several apartments with rooms without
any doors _i.e_. disconnected in terms of the topology. Moreover, apartments
are removed that are not fully connected and/or for which our graph extraction
algorithm cannot reliably compute the corresponding access graphs. The cleaned
dataset contains $\sim$56k apartments. Furthermore, we found that RPLAN
contains many (near) duplicates. For evaluation of the ranking algorithm
(Subsec. 4.4), we remove the (near) duplicates to reduce clutter in the
results. Duplicates are removed by a threshold on mIoU,
$\tau_{\text{IoU}}=0.87$. Duplicates are not removed when assessing the
distributions and correlations of mIoU and nGED.

###  4.2 Distributions

To understand the relations between the pairwise similarity measures (mIoU and
nGED) and how they relate to structural similarity, we start by investigating
the probability density functions of the pairwise similarity measures
($p_{\text{IoU}}$ and $p_{\text{GED}}$, respectively). $p_{\text{IoU}}$ and
$p_{\text{GED}}$ are approximated by computing IoU and GED for over a million
randomly sampled floor plan pairs. For brevity, we use ”IoU” and ”GED” instead
of ”mIoU” and ”nGED”.

#### IoU

IoU is computed according to Eq. 3 and across all subdivision categories
except for the ”background”. The histogram of the distribution is provided in
Fig. 4 in the middle left plot in blue. The mean of the distribution is around
0.25 which means that on average approximately 25% of the pixels are
overlapping. We also plot the IoU distribution for the 50 best-scoring
examples on IoU per floor plan identity, shown in orange. As expected,
compared to the full IoU distribution, the mean is significantly shifted. The
spike around 1.0 can be attributed to the many (near) duplicates in the
dataset.

To give an idea of the diversity of floor plan samples, Fig. 4 (top row)
highlights floor plans with different ’originality’ scores. The originality is
computed by the average IoU score for a given sample with all remaining
samples. The more right ($\approx$ 0.1) the more original _i.e_. seldom and
the more left ($\approx$ 0.4) the less original _i.e_. more frequent.
Generally speaking, the originality positively correlated mostly with the
complexity of the shapes of both the rooms and boundaries.

Figure 4:  IoU and GED distributions and originality. The two plots in the
center illustrate the distributions of IoU (left) and GED (right): blue
depicts the distribution over all samples and orange only considers the top-50
on IoU. An indication of semantic image originality (based on the average IoU)
is given on the top and one for the graph originality (based on the base graph
occurrence) is given on the bottom: originality increases going from left to
right.

#### GED

nGED is computed according to Eqs. 5 and 6 and hence cost for node and edge
deletions, insertions, and substitutions are kept the same. The histogram of
the full distribution is illustrated in Fig. 4 in the middle right plot in
blue. We also plot the GED distribution for the 50 best scoring examples on
IoU per floor plan identity, shown in orange. Surprisingly, both full and
top-50 distributions are nearly similar, revealing a weak (if at all)
correlation between IoU and GED. The weak correlation is further investigated
in the next section.

Figure 5:  Distribution of base graphs. The plot on the top provides the
distribution of base graphs (in descending order of occurrence) for base
graphs that at least occur 9 times. On the bottom, the base graphs are plotted
for several randomly picked floor plans. For some of the base graphs, we
indicate the position in the distribution through the colored boxes.

It is worth noting that there are only 50 unique GED values in our population
of random pairs. The limited range of GED values can be attributed to:

Firstly, the amount of floor plan pairs that share the same underlying base
graph – all possible graphs present in the dataset for which each pairwise
combination is isomorphic: $g_{1}$ is isomorphic to $g_{2}$ – is relatively
large. To make our point, we sort all base graphs based on the number of
corresponding floor plans and show the huge imbalance between base graph
occurrences (see Fig. 5). For example, more than 25% of the data ($\approx$14k
samples) correspond to the 100 most prominent base graphs only. Visualized in
Fig. 4 (bottom row) and similar to the IoU originality scores, we score floor
plans on graph originality as well. Graph originality is based on the number
of corresponding floor plans for a given base graph: the more original the
fewer floor plans per base graph. While the main patterns of graph originality
are to be more closely investigated, on average the number of nodes as well as
edges slightly increase with originality.

Secondly, revealed empirically by the graph originality distribution, the
distribution of topology – the graph’s structure – alone is small because the
graphs are limited in size (number of connections) and order (number of
subdivisions). Furthermore, the topological types are limited as well.
Typically, access graphs are confined to be flower-like and thus centered
around a single node. The central node is usually the living room and/or
hallway.

Indeed, the majority of floor plans stem from a limited collection of base
graphs, and only a few node and edge attributes are considered, leading to the
ineffectiveness of measuring structural similarity solely based on graph
similarity.

###  4.3 Correlations

The correlation between IoU and GED is further investigated. The 2D density
map of IoU and GED is depicted in Fig. 6 and plotted as a heatmap. We define a
positive correlation when increments in visual similarity _i.e_. higher IoU
result in increments in the graph-based similarity _i.e_. lower GED.
Effectively we measure the correlation between IoU and negative GED. The
heatmap shows for increasing IoU ranges that GED distributions shift towards
lower values, hence the correlation between IoU and GED is positive. To be
precise, the Pearson correlation coefficient is 0.503 between mIoU and -nGED,
hence GED and IoU are moderately correlated. However, the overlapping regions
between GED distributions for different IoU ranges are often large.
Specifically, IoU and GED oppose each other 38% of the time – opposition here
means that a higher IoU results in a higher GED or that a lower IoU results in
a lower GED. Several examples in which IoU and GED oppose each other are given
in Fig. 7.

Figure 6:  2D density map of IoU and GED as heatmap. A moderate correlation
(0.503) between IoU and -GED is found. The distribution is, however, widely
spread indicating that IoU and GED often fail to predict one another with
confidence.

From the triplets shown in Fig. 7, many characteristics of IoU and GED rise to
the surface. For an anchor, we define pos@IoU as the positive (IoU high) and
neg@IoU as the negative query (IoU low). The same holds for pos@GED (GED low)
and neg@GED (GED high). Most prominent is the sensitivity of IoU w.r.t. the
overall shape of the building: in all cases, the overall shape between the
anchor and the pos@IoU are nearly identical and slightly different for the
pos@GED. On the other hand, the number of rooms is often different between the
anchor and pos@IoU while (nearly) always equivalent between the anchor and
pos@GED: placing or removing rooms is detrimental for GED but in many cases
does not hurt IoU so much. Another difference between pos@IoU and pos@GED is
the fact that changes in the room shapes – especially to the central space –
are not penalized by GED yet detrimental for IoU. The examples reveal the
difficulty of measuring the structural similarity of floor plans. Apparently,
both measures independently cannot fully grasp structural similarity.

Figure 7:  Negative examples between IoU and GED on RPLAN. IoU is sensitive to
the scales and shape of the room while GED captures the connections between
the rooms.

###  4.4 Floor plan retrieval

We evaluate our ranking algorithm provided in Subsec. 3.5 and qualitatively
compare the retrievals to independent IoU- and GED-based rankings, and to
retrievals based on a deeply learned metric [13].

We start by finding a proper value for $n$ – the number of samples (when
ranked on IoU) considered for further SSIG assessment. In Fig. 9, the
distributions for IoU, GED, and SSIG are provided for various values of $n$.
In our observation, for relatively large values of SSIG ($>$0.7) every linear
increase in $n$ adds fewer samples every time. We found for RPLAN that values
of $n$ $>$= 50 seldom change the top-10 on SSIG. Compared to measuring SSIG on
the whole dataset, SSIG only needs to be computed 50 times. We believe that
IoU, at least in the case of RPLAN, is a proper first step to find
correspondences in structural similarity coarsely, while GED is a proper help
to measure structural similarity on a finer level. Hence, we refer to our
ranking method as a visually-guided graph edit distance.

Figure 8:  Retrieval results of our method. The most left is the query and to
the right are the retrievals. The red and blue transparent boxes indicate the
IoU and GED ranks, respectively.  Figure 9:  IoU, GED, and SSIG distributions
for various $n$. The different colors indicate different $n$. Particularly
interesting is the fact that the mean of both IoU and SSIG drastically
decreases for increasing $n$.

Our algorithm is compute-efficient w.r.t. GMNs. Depending on the size and
originality of the floor plan’s corresponding access graphs, our algorithm
takes between 1 and 5 s on a single CPU per unseen sample to fully rank it.
Compared to LayoutGMN, the same computation takes approximately 1500 s. Hence,
our algorithm is compute-efficient w.r.t. GMNs.

Randomly picked retrievals (top 10) of our method are shown in Fig. 8 and
compared against IoU- and GED-only ranks. In red and blue are IoU and GED
ranks, respectively. Not surprisingly the SSIG, IoU, and GED ranks are quite
different which can be attributed to the fact that the correlation between IoU
and GED is only weakly positive (see Subsec. 4.3). Compared to IoU- and GED-
only retrievals, it can be seen that SSIG indeed compensates for ’failures’ in
IoU and GED. For example in the last row of Fig. 8, the first 4 retrieval
results, even though having a low IoU value, are compensated by GED, while the
5th retrieval is compensated by IoU, even though having a low GED value.
Similar compensation for failures can be found back in the retrievals of
deeply learned metrics, see [13, 4, 8].

##  5 Conclusion and future work

In this work, we showed that image- as well as graph-based similarity metrics
alone are likely not enough to robustly measure structural similarity between
floor plans. We overcome the shortcomings by combining IoU and GED into one
metric, called SSIG. We qualitatively showed that a floor plan database which
is ranked on SSIG shares similar characteristics to results of state-of-the-
art methods that use GMNs to compute the ranking.

This work is however limited to investigating IoU and GED and does not
consider other well-known image- and graph-based similarity metrics. Moreover,
we did not conduct any user study to rigorously assess our claims further. In
future studies we hope to address both limitations.

The formulation of similarity as defined in Eq. 1 is setup in a task-agnostic
manner - the formulation addresses floor plan similarity as a single overall
measure. In many cases, however, a more realistic way to setup similarity
might be dynamic (_e.g_., based on categories), hence, allowing for different
similarity scores across multiple use cases whether used in floor plan
tailored search engines, evaluation of floor plan generation, etc. Our aim is
to work on such formulations in the future.

We believe that SSIG will pave a way towards improved data-driven research on
floor plans, such as for providing a more natural objective to train deep
metric learning frameworks that do not necessarily require information sharing
across branches.

## References

  * [1] Stanislas Chaillou.  AI + Architecture | Towards a New Approach.  Harvard University, Jan. 2019.
  * [2] Biplab Deka, Zifeng Huang, Chad Franzen, Joshua Hibschman, Daniel Afergan, Yang Li, Jeffrey Nichols, and Ranjitha Kumar.  Rico: A Mobile App Dataset for Building Data-Driven Design Applications.  In Proceedings of the 30th Annual ACM Symposium on User Interface Software and Technology, UIST ’17, pages 845–854, New York, NY, USA, Oct. 2017. Association for Computing Machinery.
  * [3] Shreyas Hampali, Sinisa Stekovic, Sayan Deb Sarkar, Chetan S. Kumar, Friedrich Fraundorfer, and Vincent Lepetit.  Monte Carlo Scene Search for 3D Scene Understanding.  In 2021 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 13799–13808, Nashville, TN, USA, June 2021. IEEE.
  * [4] Jiongchao Jin, Zhou Xue, and Biao Leng.  SHRAG: Semantic Hierarchical Graph for Floorplan Representation.  In 2022 International Conference on 3D Vision (3DV), pages 271–279, Sept. 2022.  ISSN: 2475-7888.
  * [5] Rasika Khade, Krupa Jariwala, Chiranjoy Chattopadhyay, and Umapada Pal.  A rotation and scale invariant approach for multi-oriented floor plan image retrieval.  Pattern Recognition Letters, 145:1–7, May 2021.
  * [6] Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals, and Pushmeet Kohli.  Graph Matching Networks for Learning the Similarity of Graph Structured Objects.  In Proceedings of the 36th International Conference on Machine Learning, pages 3835–3845. PMLR, May 2019.  ISSN: 2640-3498.
  * [7] Chen Liu, Jiajun Wu, Pushmeet Kohli, and Yasutaka Furukawa.  Raster-To-Vector: Revisiting Floorplan Transformation.  In 2017 Proceedings of the IEEE International Conference on Computer Vision, pages 2195–2203, 2017.
  * [8] Dipu Manandhar, Dan Ruta, and John Collomosse.  Learning Structural Similarity of User Interface Layouts Using Graph Networks.  In Andrea Vedaldi, Horst Bischof, Thomas Brox, and Jan-Michael Frahm, editors, Computer Vision – ECCV 2020, volume 12367, pages 730–746. Springer International Publishing, Cham, 2020.  Series Title: Lecture Notes in Computer Science.
  * [9] Nelson Nauata, Kai-Hung Chang, Chin-Yi Cheng, Greg Mori, and Yasutaka Furukawa.  House-GAN: Relational Generative Adversarial Networks for Graph-Constrained House Layout Generation.  In Andrea Vedaldi, Horst Bischof, Thomas Brox, and Jan-Michael Frahm, editors, Computer Vision – ECCV 2020, Lecture Notes in Computer Science, pages 162–177, Cham, 2020. Springer International Publishing.
  * [10] Nelson Nauata, Sepidehsadat Hosseini, Kai-Hung Chang, Hang Chu, Chin-Yi Cheng, and Yasutaka Furukawa.  House-GAN++: Generative Adversarial Layout Refinement Network towards Intelligent Computational Agent for Professional Architects.  pages 13632–13641, 2021.
  * [11] Lawrence O’Gorman and Rangachar Kasturi.  Executive briefing: document image analysis.  IEEE Computer Society Press, Los Alamitos, Calif, 1997.
  * [12] Hyejin Park, Hyegyo Suh, Jaeil Kim, and Seungyeon Choo.  Floor plan recommendation system using graph neural network with spatial relationship dataset.  Journal of Building Engineering, page 106378, Mar. 2023.
  * [13] Akshay Gadi Patil, Manyi Li, Matthew Fisher, Manolis Savva, and Hao Zhang.  LayoutGMN: Neural Graph Matching for Structural Layout Similarity.  In 2021 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 11043–11052, Nashville, TN, USA, June 2021. IEEE.
  * [14] Morteza Rahbar, Mohammadjavad Mahdavinejad, Amir H. D. Markazi, and Mohammadreza Bemanian.  Architectural layout design through deep learning and agent-based modeling: A hybrid approach.  Journal of Building Engineering, 47:103822, Apr. 2022.
  * [15] Pau Riba, Andreas Fischer, Josep Lladós, and Alicia Fornés.  Learning graph edit distance by graph neural networks.  Pattern Recognition, 120:108132, Dec. 2021.
  * [16] Qamer Uddin Sabri, Johannes Bayer, Viktor Ayzenshtadt, Syed Saqib Bukhari, Klaus-Dieter Althoff, and Andreas Dengel.  Semantic Pattern-based Retrieval of Architectural Floor Plans with Case-based and Graph-based Searching Techniques and their Evaluation and Visualization:.  In Proceedings of the 6th International Conference on Pattern Recognition Applications and Methods, pages 50–60, Porto, Portugal, 2017. SCITEPRESS - Science and Technology Publications.
  * [17] Alberto Sanfeliu and King-Sun Fu.  A distance measure between attributed relational graphs for pattern recognition.  IEEE Transactions on Systems, Man, and Cybernetics, SMC-13(3):353–362, May 1983.  Conference Name: IEEE Transactions on Systems, Man, and Cybernetics.
  * [18] Mohammad Amin Shabani, Sepidehsadat Hosseini, and Yasutaka Furukawa.  HouseDiffusion: Vector Floorplan Generation via a Diffusion Model with Discrete and Continuous Denoising, Nov. 2022.  arXiv:2211.13287 [cs].
  * [19] Divya Sharma and Chiranjoy Chattopadhyay.  High-level feature aggregation for fine-grained architectural floor plan retrieval.  IET Computer Vision, 12(5):702–709, 2018.  _eprint: https://onlinelibrary.wiley.com/doi/pdf/10.1049/iet-cvi.2017.0581.
  * [20] Divya Sharma, Chiranjoy Chattopadhyay, and Gaurav Harit.  A unified framework for semantic matching of architectural floorplans.  In 2016 23rd International Conference on Pattern Recognition (ICPR), pages 2422–2427, Dec. 2016.
  * [21] Divya Sharma, Nitin Gupta, Chiranjoy Chattopadhyay, and Sameep Mehta.  DANIEL: A Deep Architecture for Automatic Analysis and Retrieval of Building Floor Plans.  In 2017 14th IAPR International Conference on Document Analysis and Recognition (ICDAR), volume 01, pages 420–425, Nov. 2017.  ISSN: 2379-2140.
  * [22] Chia-Ying Shih and Chi-Han Peng.  Floor Plan Exploration Framework Based on Similarity Distances, Nov. 2022.  arXiv:2211.07331 [cs].
  * [23] Yuki Takada, Naoto Inoue, Toshihiko Yamasaki, and Kiyoharu Aizawa.  Similar floor plan retrieval featuring multi-task learning of layout type classification and room presence prediction.  In 2018 IEEE International Conference on Consumer Electronics (ICCE), pages 1–6, Jan. 2018.  ISSN: 2158-4001.
  * [24] Hao Tang, Zhenyu Zhang, Humphrey Shi, Bo Li, Ling Shao, Nicu Sebe, Radu Timofte, and Luc Van Gool.  Graph Transformer GANs for Graph-Constrained House Generation, Mar. 2023.  arXiv:2303.08225 [cs].
  * [25] Markus Weber, Christoph Langenhan, Thomas Roth-Berghofer, Marcus Liwicki, Andreas Dengel, and Frank Petzold.  a.SCatch: Semantic Structure for Architectural Floor Plan Retrieval.  In Isabelle Bichindaritz and Stefania Montani, editors, Case-Based Reasoning. Research and Development, Lecture Notes in Computer Science, pages 510–524, Berlin, Heidelberg, 2010. Springer.
  * [26] Wenming Wu, Xiao-Ming Fu, Rui Tang, Yuhan Wang, Yu-Hao Qi, and Ligang Liu.  Data-driven interior plan generation for residential buildings.  ACM Transactions on Graphics, 38(6):234:1–234:12, Nov. 2019.
  * [27] Mantaro Yamada, Xueting Wang, and Toshihiko Yamasaki.  Graph Structure Extraction from Floor Plan Images and Its Application to Similar Property Retrieval.  In 2021 IEEE International Conference on Consumer Electronics (ICCE), pages 1–5, Jan. 2021.  ISSN: 2158-4001.
  * [28] Xu Zhong, Jianbin Tang, and Antonio Jimeno Yepes.  PubLayNet: largest dataset ever for document layout analysis, Aug. 2019.  arXiv:1908.07836 [cs].


# Computational ghost imaging of moving objects with random speed

Xiaoyu Nie  Texas A&M University, College Station, Texas 77843, USA  Xi’an
Jiaotong University, Xi’an, Shaanxi 710049, China  Xingchen Zhao  Texas A&M
University, College Station, Texas 77843, USA  Tao Peng<EMAIL_ADDRESS>Texas A&M University, College Station, Texas 77843, USA  Marlan O. Scully
Texas A&M University, College Station, Texas 77843, USA  Baylor University,
Waco 76706, USA

###### Abstract

We show that a recently developed computational ghost imaging method based on
the pink noise speckle pattern has a strong ability to image moving objects.
To examine our scheme’s unique ability and application scope, we
experimentally image an object moving with the random speed at variable
amplitudes. We show that the pink noise speckle pattern can effectively image
moving objects when the traditional methods fail. The results provide
promising potential applications for ghost imaging in remote sensing.

††preprint: APS/123-QED

##  I Introduction

Ghost imaging (GI) Pittman1995Optical ; bennink2002two ; chen2009lensless , a
practice with single-pixel imaging, possesses advanced features comparing to
the conventional photographing. Since it applies the second-order correlation
algorithm to photo reconstruction, the GI method can be immune to the media’s
interference and strong environmental noise. To further ameliorate and
simplify the system, computational ghost imaging (CGI) bromberg2009ghost ;
shapiro2008computational  is proposed, where one light path usually recording
speckles without passing objects is alternated by loading pre-generated
patterns in computer memories onto the digital micro-mirror devices (DMD).
Thus, CGI uses a single element detector to reconstruct images by sequentially
recording the correlation between a set of intensity and their corresponding
patterns, which has non-conventional applications such as wide spectrum
imaging radwell2014single ; Yang2017Ghost , depth mapping sun2016single , and
sub-Rayleigh imaging kuplicki2016high ; chen2017sub ; sprigg2016super .

However, unlike conventional photographing, which only needs to take one
snapshot of the object, CGI requires many samplings to reconstruct a high-
quality image. The minimum number of sampling is proportionate to the total
number of pixels projecting on objects Katz2009Compressive . It is, therefore,
natural to require that the object stays steady when illuminated by a sequence
of patterns. The image quality is determined by both the exposure time of each
frame and the number of frames, i.e., the total integration time. The image
could be blurred or even destroyed if the target is moving. Previously, many
schemes have been proposed to improve the speed of CGI wang2016fast ;
gong2016three ; xu20181000 ; jiang2019scan  or reducing the sampling rate to
the sub-Nyquist region sun2017russian ; lyu2017deep ;
luo2018orthonormalization ; He2018Ghost . Other effects have been made to
image objects with motion, using linear correlation algorithm li2011lensless ,
working in the Fourier domain zhang2013improving , or using entangled photons
magana2013compressive . When the object moves with an unknown constant speed
in various motion modes, it has been shown that compensation of the motion can
be made therefore retrieve the images li2014ghost ; li2015ghost ;
jiao2019motion . Under the condition that the sampling rate of GI is faster
than the refreshing motion rate of the image, a clear GI can be gradually
obtained sun2019gradual . However, imaging a moving object in general without
any prior knowledge of the motion is still quite challenging. We recently
developed a method to customize the speckle patterns for CGI in the spatial
frequency domain, i.e., the generation of colored noise speckle patterns
li2021sub ; nie2020noise . Colored noise generally has non-zero cross-
correlation between neighborhood pixels as compared with the white noise. In
particular, the pink noise speckle pattern has shown ability to image in a
variety of noisy environments nie2020noise .

This work aims to minimize the sampling number and improve the signal-to-noise
ratio (SNR) using the synthesized pink noise speckle patterns, when imaging a
moving object with an unknown variable speed. The results were compared to the
traditional white noise speckle patterns. The unique ability and scope of its
applications are demonstrated by several comparisons where the target moves at
a random speed with ranges 0${mm}$, 0.4${mm}$, 0.9${mm}$, and 1.8${mm}$. Our
results demonstrate that CGI with pink noise is effective in capturing
randomly moving targets, while conventional CGI fails..

##  II Computational ghost imaging of moving object

The experimental setup is shown in Fig. 1. A CW laser is used to illuminate
the DMD. The pattern generated by the DMD is then imaged onto the the target.
A lens (L3) is used to image the transmitted light from the target onto the
CCD plane. The CCD can be used to monitor the first order image as well as a
bucket detector in the CGI system. The DMD contains tiny pixel-mirrors, each
measuring 16 $\mu{m}$ by 16 $\mu{m}$. Each 4 by 4 DMD pixels are used as an
independently changeable noise speckle pixel. In our experiment, the size of
the noise patterns is 54 by 98 independent pixels. The object is made into a
Flight shape which contains totally around 2000 independent pixels. In the
measurement, The maximum movements of object are made to be 0, 2, 5, and 10
independent pixels on the patterns projected to CCD. The speed and
acceleration of object have a random number at every moment. The maximum value
of the speed is $500~{}mm/s$ and the maximum value of the acceleration is
$500~{}mm/s^{2}$. The integration time of the CCD is $200~{}\mu s$ for each
frame.

Figure 1: Schematic of the setup for a CGI experiment. A CW laser is expended
then reflected by a DMD where the noise patterns are loaded. The patterns are
imaged by a lens (L2) to the object plane. The Flight shaped object is put
moves with random speed on a stage. Another lens (L3) is used to image the
object plane to the CCD, which can be used as a bucket detector.

The noise patterns used in our experiment are binary patterns. For pink noise
speckle patterns, the power spectrum density is defined by
${I_{(\omega)}}\sim{\omega^{-1}}$ nie2020noise . Conventional white noise with
power spectrum density ${I_{(\omega)}}\sim{\omega^{0}}$ is also used in our
experiments as a comparison. Together with randomly conjugated symmetric
phases, an inverse Fourier transformation on the spectrum defined above
creates gray-scale ([0, 255]) pink noise patterns. The gray-scale patterns are
then converted to binary patterns before applied to the DMD, by defining the
pixels over 127.5 to be 1, and pixels below 127.5 to 0. The 2D speckle
patterns of white and pink noise are shown in Fig. 2(a) and (b). The 2D
spatial frequency distributions of white and pink noise are shown in Fig. 2(c)
and (d). We choose one pixel randomly from the pink noise patterns and
calculate its auto-correlation and cross-correlation. Pink noise’s spectral
intensity distribution leads to a significantly positive correlation between
pixels close to each other, as shown in Fig. 2(e) and (f). This unique
positive cross-correlation is why the pink noise CGI can be employed with
reconstructing moving objects, as shown below.

Figure 2: A typical two-dimensional noise speckle pattern, its two-dimensional
spatial frequency distribution, and one-dimensional cross correlation between
pixels for white noise patterns (a), (c), and (e), and pink noise patterns
(b), (d), and (f).

In CGI algorithms, we should collect a series of light intensity while
sampling. The value of each proportionate to the transmitted pattern
distribution at the sample position. The light intensity at the bucket
detector is

$\displaystyle\
I_{\mathrm{i}}\sim\sum\limits_{\widetilde{x},\widetilde{y}}{T(\widetilde{x},\widetilde{y})P_{\mathrm{i}}(\widetilde{x},\widetilde{y})},$
(1)

Where $T$ represents the object transmission function, $P_{\mathrm{i}}$ is the
$i$th noise pattern, ${(\widetilde{x},\widetilde{y})}$ is the pixel notation
of patterns on the object plane. For ${(x,y)=(\widetilde{x},\widetilde{y})}$,
the intensity of ${P(\widetilde{x},\widetilde{y})}$ approximately
proportionate to ${P(x,y)}$, weakened due to light propagation. Using the
estimated light intensity, we get

$\displaystyle g^{(2)}_{p}(x,y)$ $\displaystyle=\left\langle
P(x,y)I\right\rangle-\left\langle P(x,y)\right\rangle\left\langle
I\right\rangle$ (2) $\displaystyle=\langle\Delta P(x,y)\Delta I\rangle$ (3)
$\displaystyle=\frac{1}{N}\langle\Delta
P_{\mathrm{i}}(x,y)\sum\limits_{\widetilde{x},\widetilde{y}}T(\widetilde{x},\widetilde{y})\Delta
P_{\mathrm{i}}(\widetilde{x},\widetilde{y})\rangle$ (4)
$\displaystyle\propto\sum\limits_{\widetilde{x},\widetilde{y}}T(\widetilde{x},\widetilde{y})\langle\Delta
P(x,y)\Delta P(\widetilde{x},\widetilde{y})\rangle,$ (5)

where $N$ is the total number of noise patterns, and ${(x,y)}$ is the pixel
notation of patterns in the computer. ${\left\langle\Delta P(x,y)\Delta
P(\widetilde{x},\widetilde{y})\right\rangle}$ is the correlation between the
pixels at position $(\widetilde{x},\widetilde{y})$ and $(x,y)$. For commonly
used white noise or speckles in CGI, only when
${(\widetilde{x},\widetilde{y})=(x,y)}$ we get ${\left\langle\Delta
P(x,y)\Delta P(\widetilde{x},\widetilde{y})\right\rangle=1}$, otherwise
${\left\langle\Delta P(x,y)\Delta
P(\widetilde{x},\widetilde{y})\right\rangle=0}$. Therefor, each point
${(x,y)}$ in the reconstructed image is only contributed by the auto-
correlation, thus hard to suppress the environmental noise with a limited
number of sampling. On the contrary, for the pink noise CGI, in addition to
the contribution from terms where ${(\widetilde{x},\widetilde{y})=(x,y)}$,
${\left\langle\Delta P(x,y)\Delta
P(\widetilde{x},\widetilde{y})\right\rangle=1}$, the term whose
${(\widetilde{x},\widetilde{y})}$, ${(x,y)}$ are neighbours also make
contributions because their cross-correlation ${\left\langle\Delta
P(x,y)\Delta P(\widetilde{x},\widetilde{y})\right\rangle>0}$. Thus, the
intensity of every point ${(x,y)}$ in the reconstructed image is derived by
adding up both auto-correlation and cross-correlation. Here, the cross-
correlation was defined by ${\left\langle\Delta P(x,y)\Delta
P(\widetilde{x},\widetilde{y})\right\rangle}$. Consequently, the pink noise
CGI can reconstruct the image when the equivalent static sampling number drops
if the target moves. Meanwhile, the pink noise CGI can suppress the external
noise and enhance the visibility, which can be reflected in the SNR.

##  III Experiment results

In the experiment, we set the distance of motion as 0${mm}$, 0.4${mm}$,
0.9${mm}$, and 1.8${mm}$, which correspond to 0, 2, 5, and 10 independent
changeable pixels of noise patterns projected on the CCD surface,
respectively. For each group, pink noise and white noise are applied, and CGI
results are achieved from variable sampling numbers
($N=1000,2000,5000,10000$). Also, we introduce SNR to justify the quality of
results. The definition of SNR is

${SNR}=\frac{\mu_{\mathrm{sig}}}{\sigma_{\mathrm{sig}}}.$ (6)

where the $\mu_{\mathrm{sig}}$ is the average signal value and the
$\sigma_{\mathrm{sig}}$ is the standard deviation of the signal.

Figure 3: Results by sampling 10000 patterns. (a) White noise CGI result with
static target. (b) White noise CGI result with displacement = 0.9${mm}$. (c)
Pink noise CGI result with static target. (d) Pink noise CGI result with
displacement = 0.9${mm}$.

The main results are shown in Fig. 3. The results in the first column are
reconstructed images with a static target, the second column has results
achieved when the target moves with displacement = 0.9${mm}$. The first and
second row are done with white noise and pink noise speckle patterns,
respectively. It is clear that the pink noise CGI has a much higher SNR than
the white noise CGI, due to the non-zero cross-correlation from the pink noise
pattern. When the target is moving, the equivalent total sampling at each
position decreases significantly. Thus, the auto-correlation of the white
noise is not enough to suppress environmental noise within a limited number of
patterns under the circumstance of a moving object, as shown in Fig. 3(b). On
the other hand, the pink noise pattern can still give a clear image of the
object, as shown in Fig. 3(d).

Figure 4: Retrieved images with an object displacement of 0.4${mm}$. The
number of sampling is 1000, 2000, 5000, and 10000 in each column, left to
right. (a-d): results of white noise CGI. (e-h): results of pink noise CGI.

To further exam our method and explore the advantages of the pink noise
speckle patterns, we also measure the target with a displacement of 0.4${mm}$
under different sample rates. The results are shown in Fig. 4. The sampling
number varies from 1000 to 10000. Fig. 4 (a-d) are white noise CGIs and Fig. 4
(e-h) are pink noise CGIs. From Fig. 4 (e) and (f), we can see that the shape
of the object could be determined by pink noise CGI even the sampling number
is 1000, and becomes much clearer when N gets bigger but still under Nyquist
limit (5292 in our experiment). Nevertheless, the retrieved images from white
noise CGI shown in Fig. 4 (a) and (b) are totally blurred, not clear even when
${N=5000}$ and $10000$ in Fig. 4 (c) and (d). The results also have poor
visibility as compared with the pink noise cases.

Figure 5:  Signal-to-noise ratio with respect to sampling number and
displacement, where pink noise CGIs are solid lines and white noise CGIs are
dashed lines.

Lastly, in Fig. 5, we plot the SNR of the retrieved CGIs with respect to
different sampling numbers (1000, 2000, 5000, and 10000) and different
displacements (0${mm}$, 0.4${mm}$, 0.9${mm}$, and 1.8${mm}$), for both white
and pink noise images. The solid lines are for pink noise measurements, and
dashed lines are for white noise measurements. We see that pink noise always
has a much higher SNR than white noise with measurements made under the same
displacement, 4 times higher when ${N=1000}$, for instance. For both cases,
the SNR decreases when the displacement increases, as expected.

##  IV Conclusion

In this work, we have developed a practice based on the pink noise pattern in
the CGI system to reconstruct images of a moving object, indicated by the
simultaneously improved SNR and fewer sampling numbers. Experimentally, the
SNR of pink noise CGI is usually 4 to 5 times higher than the SNR of white
noise CGI, especially when the sample rate is low. Our scheme takes advantage
of the positive cross-correlation, which is unique to the pink noise pattern,
giving the robustness of overcoming the environmental noise, decreasing the
sampling number, and further ameliorating the quality of imaging. Namely,
reducing the number of patterns on DMD, directly shortening the time spent on
the image reconstruction process.

We note here that, due to the cross-correlation, a low level of edge’s
sharpness is the main disadvantage of pink noise CGI. Further amelioration can
be done with orthonormalization method sun2017russian ;
luo2018orthonormalization  and deep learning technique lyu2017deep ;
He2018Ghost , which may also further decrease the sampling rate of the
measurements.

In conclusion, this work provides a good solution to obtain images of a moving
target with unknown random speed. The strategy has broad application prospects
in target tracking, object recognition and remote sensing.

## Funding

Air Force Office of Scientific Research (Award No. FA9550-20-1-0366 DEF),
Office of Naval Research (Award No. N00014-20-1-2184), Robert A. Welch
Foundation (Grant No. A-1261), National Science Foundation (Grant No.
PHY-2013771).

## Acknowledgments

X. N. thanks A. Svidzinsky for his kind help during his visit to IQSE, Texas
A&M University.

## Declaration of competing interest

The authors declare that they have no known competing financial interests or
personal relationships that could have appeared to influence the work reported
in this paper.

## References

  * (1) T. B. Pittman, Y. H. Shih, D. V. Strekalov, A. V. Sergienko, Optical imaging by means of two-photon quantum entanglement, Physical Review A 52 (5) (1995) R3429–R3432.
  * (2) R. S. Bennink, S. J. Bentley, R. W. Boyd, “two-photon” coincidence imaging with a classical source, Physical Review Letters 89 (11) (2002) 113601.
  * (3) X.-H. Chen, Q. Liu, K.-H. Luo, L.-A. Wu, Lensless ghost imaging with true thermal light, Optics Letters 34 (5) (2009) 695–697.
  * (4) Y. Bromberg, O. Katz, Y. Silberberg, Ghost imaging with a single detector, Physical Review A 79 (5) (2009) 053840.
  * (5) J. H. Shapiro, Computational ghost imaging, Physical Review A 78 (6) (2008) 061802\.
  * (6) N. Radwell, K. J. Mitchell, G. M. Gibson, M. P. Edgar, R. Bowman, M. J. Padgett, Single-pixel infrared and visible microscope, Optica 1 (5) (2014) 285–289.
  * (7) Z. Yang, Z. Nan, Y. Sun, Y. Yu, Ghost imaging for online angiography, Translational Neuroscience and Clinics (2017).
  * (8) M.-J. Sun, M. P. Edgar, G. M. Gibson, B. Sun, N. Radwell, R. Lamb, M. J. Padgett, Single-pixel three-dimensional imaging with time-based depth resolution, Nature Communications 7 (1) (2016) 1–6.
  * (9) K. Kuplicki, K. W. C. Chan, High-order ghost imaging using non-rayleigh speckle sources, Optics Express 24 (23) (2016) 26766–26776.
  * (10) X.-H. Chen, F.-H. Kong, Q. Fu, S.-Y. Meng, L.-A. Wu, Sub-rayleigh resolution ghost imaging by spatial low-pass filtering, Optics Letters 42 (24) (2017) 5290–5293.
  * (11) J. Sprigg, T. Peng, Y. Shih, Super-resolution imaging using the spatial-frequency filtered intensity fluctuation correlation, Scientific Reports 6 (2016) 38077.
  * (12) O. Katz, Y. Bromberg, Y. Silberberg, Compressive ghost imaging, Applied Physics Letters 95 (13) (2009) 739.
  * (13) L. Wang, S. Zhao, Fast reconstructed and high-quality ghost imaging with fast walsh–hadamard transform, Photonics Research 4 (6) (2016) 240–244.
  * (14) W. Gong, C. Zhao, H. Yu, M. Chen, W. Xu, S. Han, Three-dimensional ghost imaging lidar via sparsity constraint, Scientific Reports 6 (1) (2016) 1–6.
  * (15) Z.-H. Xu, W. Chen, J. Penuelas, M. Padgett, M.-J. Sun, 1000 fps computational ghost imaging using led-based structured illumination, Optics Express 26 (3) (2018) 2427–2434.
  * (16) S. Jiang, X. Li, Z. Zhang, W. Jiang, Y. Wang, G. He, Y. Wang, B. Sun, Scan efficiency of structured illumination in iterative single pixel imaging, Optics Express 27 (16) (2019) 22499–22507.
  * (17) M.-J. Sun, L.-T. Meng, M. P. Edgar, M. J. Padgett, N. Radwell, A russian dolls ordering of the hadamard basis for compressive single-pixel imaging, Scientific Reports 7 (1) (2017) 1–7.
  * (18) M. Lyu, W. Wang, H. Wang, H. Wang, G. Li, N. Chen, G. Situ, Deep-learning-based ghost imaging, Scientific Reports 7 (1) (2017) 1–6.
  * (19) B. Luo, P. Yin, L. Yin, G. Wu, H. Guo, Orthonormalization method in ghost imaging, Optics Express 26 (18) (2018) 23093–23106.
  * (20) Y. He, G. Wang, G. Dong, S. Zhu, H. Chen, A. Zhang, Z. Xu, Ghost imaging based on deep learning, Scientific Reports 8 (1) (2018) 6469.
  * (21) H. Li, J. Xiong, G. Zeng, Lensless ghost imaging for moving objects, Optical Engineering 50 (12) (2011) 127005.
  * (22) C. Zhang, W. Gong, S. Han, Improving imaging resolution of shaking targets by fourier-transform ghost diffraction, Applied Physics Letters 102 (2) (2013) 021111\.
  * (23) O. S. Magana-Loaiza, G. A. Howland, M. Malik, J. C. Howell, R. W. Boyd, Compressive object tracking using entangled photons, Applied Physics Letters 102 (23) (2013) 231104.
  * (24) E. Li, Z. Bo, M. Chen, W. Gong, S. Han, Ghost imaging of a moving target with an unknown constant speed, Applied Physics Letters 104 (25) (2014) 251120.
  * (25) X. Li, C. Deng, M. Chen, W. Gong, S. Han, Ghost imaging for an axially moving target with an unknown constant speed, Photonics Research 3 (4) (2015) 153–157.
  * (26) S. Jiao, M. Sun, Y. Gao, T. Lei, Z. Xie, X. Yuan, Motion estimation and quality enhancement for a single image in dynamic single-pixel imaging, Optics Express 27 (9) (2019) 12841–12854.
  * (27) S. Sun, J.-H. Gu, H.-Z. Lin, L. Jiang, W.-T. Liu, Gradual ghost imaging of moving objects by tracking based on cross correlation, Optics Letters 44 (22) (2019) 5594–5597.
  * (28) Z. Li, X. Nie, F. Yang, X. Liu, D. Liu, X. Dong, X. Zhao, T. Peng, M. S. Zubairy, M. O. Scully, Sub-rayleigh second-order correlation imaging using spatially distributive colored noise speckle patterns, Opt. Express 29 (13) (2021) 19621–19630.
  * (29) X. Nie, F. Yang, X. Liu, X. Zhao, R. Nessler, Z. Li, T. Peng, M. S. Zubairy, M. O. Scully, Noise-free computational ghost imaging with pink noise speckle patterns, arXiv preprint arXiv:2009.14390 (2020).


scaletikzpicturetowidth[1]

# FIID homomorphisms and entropy inequalities

Endre Csóka  Alfréd Rényi Institute of Mathematics, Reáltanoda u. 13-15., 1053
Budapest, Hungary<EMAIL_ADDRESS>and  Zoltán Vidnyánszky  Eötvös Loránd
University, Institute of Mathematics, Pázmány Péter stny. 1/C, 1117 Budapest,
Hungary<EMAIL_ADDRESS>
###### Abstract.

We investigate the existence of FIID homomorphisms from regular trees to
finite graphs. Using entropy inequalities we show that there are graphs with
arbitrarily large chromatic number to which there is no FIID homomorphism from
a $3$-regular tree.

###### 2020 Mathematics Subject Classification:

Primary 03E25, Secondary

The second author was supported by Hungarian Academy of Sciences Momentum
Grant no. 2022-58 and National Research, Development and Innovation Office
(NKFIH) grants no. 113047, 129211.

##  1\. Introduction

In the past decade, a large amount of work has been aimed at the understanding
of _factor of i.i.d. (FIID)_ processes in general and FIID tree colorings in
particular (see, e.g., [5, 3, 4, 2, 12, 13, 14, 15, 16, 22, 18, 24]). Roughly
speaking (for the formal definition, see Section 2), we consider a $d$-regular
tree on which we want to solve a graph theoretic problem such as vertex
coloring, perfect matching, or finding a maximal independent set, etc. The
solution has to respect the automorphisms of the tree but it is allowed to use
uniformly distributed independent random reals at every vertex. One of the
most important feautre of FIID processes that they can be applied with an
arbitrarily small error to $d$-regular graphs with large essential girth
(i.e., to $d$-regular graphs which contain a small number of cycles). Random
$d$-regular graphs have large essenial girth, and the optimum of many
optimization problems on these random graphs are often attained by FIID
processes.

Motivated by the question of proper colorings, one can formulate the next
general problem (here, $T_{d}$ stands for the $d$-regular tree).

######  Problem 1.1.

Is it possible to characterize the finite graphs $H$ to which $T_{d}$ admits
an FIID homomorphism?

Obtaining an affirmative answer, i.e., a complete characterization, seems to
be an overly optimistic goal: despite a significant amount of effort, already
the existence of homomorphisms of $T_{3}$ to concrete, small graphs is still
open. For example, a negative answer in the case of $H=C_{5}$ would suggest
that large (finite) $3$-regular random graphs do not admit a homomorphism to
$C_{5}$, answering the notoriously hard pentagon problem of Nešetřil [21].

In this paper, we provide a simple argument based on entropy inequalities to
exclude homomorphisms to certain graphs, showing the following.

######  Theorem 1.2.

Let $r\in\mathbb{N}$ be arbitrary. There exists a constant
$C_{r}\in\mathbb{N}$ such that there is no FIID homomorphism from $T_{3}$ to
any $r$-regular graph $H$ with girth at least $C_{r}$.

###  1.1. Discussion and some corollaries

[17, Problem 8.12] asks for the characterization of finite graphs $H$ to which
each $d$-regular acyclic Borel graph admits a Borel homomorphism. As FIID
processes on $T_{3}$ can be considered as measurable maps from a fixed
$3$-regular Borel graph, our theorem gives some information about this problem
as well.

######  Corollary 1.3.

There exists a $3$-regular acyclic Borel graph, which does not admit a Borel
homomorphism to any finite $r$-regular graph $H$ with girth at least $C_{r}$.

Connected to the problem of Kechris and Marks and a generalization of Marks’
determinacy method [20], in [10] (see also [11]) it was shown that there are
graphs $H$ with chromatic number $2d-2$ such that there is no Borel
homomorphism from a $d$-regular acyclic Borel graph to $H$. By classical
results of Bollobás [7], for any $g$ there is an $r$-regular graph $H$ with
girth at least $g$ and $\chi(H)\geq\frac{r}{2\log r}$. Thus, using our main
result, we can eliminate the $2d-2$ upper bound discussed above:

######  Corollary 1.4.

There are graphs of arbitrarily large chromatic number to which there is no
FIID homomorphism from $T_{3}$.

By the correspondence developed in [10] and [6] (see also [23]) between
descriptive combinatorics and local algorithms, we get the following.

######  Corollary 1.5.

There is no $o(\log n)$-round randomized local algorithm which outputs a
homomorphism from an acyclic graph with degrees $\leq 3$ of size $n$ to an
$r$-regular graph of girth at least $C_{r}$.

Thus, entropy inequalities provide a novel way of proving local model lower
bounds for homomorphism problems on trees, and these bounds, to our knowledge,
could not be attained by Brandt’s round elimination method [9].

Acknowledgments. We are very grateful to Ágnes Backhausz, Jan Grebík and
Viktor Harangi for their insightful suggestions.

##  2\. Preliminaries

We will describe two equivalent ways of talking about FIID processes. The
classical definition is as follows. Let $\Gamma$ be a group acting on
measurable spaces $(X,\mathcal{B})$ and $(Y,\mathcal{C})$. A map $\phi:X\to Y$
is _$\Gamma$ -equivariant_ if for all $x\in X$ and $\gamma\in\Gamma$ we have

$\phi(\gamma\cdot x)=\gamma\cdot\phi(x).$

A measurable equivariant map is called a _$\Gamma$ -factor_. If $\mu$ is a
measure on $(X,\mathcal{B})$ and $\phi:X\to Y$ is a $\Gamma$-factor, the
measure $\phi_{*}\mu$ is called a _$\Gamma$ -factor of $\mu$_.

Let $T_{d}$ stand for the $d$-regular tree and $Aut(T_{d})$ be its
automorphism group. If $S$ is a set, $Aut(T_{d})$ acts on $S^{V(T_{d})}$ by
the _(left-)shift action_ , that is,

$(\gamma\cdot x)(v):=x(\gamma^{-1}\cdot v).$

Let $\mu$ be the uniform measure on the space $[0,1]^{V(T_{d})}$, that is, the
product of the Lebesgue measures on each copy of $[0,1]$. An _FIID process_ is
an $Aut(T_{d})$-factor of $\mu$ on $S^{V(T_{d})}$, where $S$ is finite and
$[0,1]^{V(T_{d})}$ and $S^{V(T_{d})}$ are considered with the algebra of
Lebesgue-measurable sets. An _FIID homomorphism to a graph $H$_ is an FIID
process on $V(H)^{V(T_{d})}$ such that for $\mu$ almost every
$x\in[0,1]^{V(T_{d})}$ the image $\phi(x)$ is a homomorphism from $T_{d}$ to
$H$.

A slightly different view is the following. One can define a graph on the
space $[0,1]^{V(T_{d})}$ as follows: fix a “root”, i.e., a distinguished
element $v_{0}\in V(T_{d})$. Let $\\{x,y\\}$ form an edge in $\mathcal{G}$ if
there is an automorphism $\psi\in Aut(T_{d})$ such that $x\circ\psi=y$ and
$(\psi(v_{0}),v_{0})\in E(T_{d})$. It is easy to see that there is a $\mu$ co-
null Borel set on which $\mathcal{G}$ is $d$-regular, acyclic and Borel.
Moreover, there is a correspondence between FIID homomorphisms to some $H$ in
the above sense and Borel homomorphisms of $\mathcal{G}$ to $H$ defined on a
co-null set: indeed, evaluating the factor map at the root yields the latter
kind of homomorphism, and conversely, given an a.e. defined Borel homomorphism
$h$ from $\mathcal{G}$ to $H$ we get a factor map $\phi$ by letting
$\phi(x)(v)=h(\gamma^{-1}\cdot x)$, where $\gamma$ is arbitrary in
$Aut(T_{d})$ with $\gamma(v_{0})=v$.

###  2.1. Entropy inequalities.

Recall that if $X$ is a discrete random variable, the _entropy of $X$_ is
defined by

$h(X)=-\sum_{x}\mathbb{P}(X=x)\ln\mathbb{P}(X=x),$

(if $\mathbb{P}(X=x)=0$ then the corresponding product is considered to be
$0$), while for two such variables $X,Y$ on the same space we define the
_conditional entropy_ by

$h(X|Y)=-\sum_{x,y}\mathbb{P}(X=x,Y=y)\ln\frac{\mathbb{P}(X=x,Y=y)}{\mathbb{P}(Y=y)}.$

It is clear that

$h(X,Y)=h(X)+h(X|Y),$

where $h(X,Y)$ stands for the _joint entropy_ of $X$ and $Y$, that is, the
entropy of the joint distribution of $X$ and $Y$.

Now observe that for any $F\subset V(T_{d})$ finite an FIID homomorphism to
$H$ gives rise to an $V(H)^{F}$ valued discrete random variable. It follows
from the $Aut(T_{d})$ equivariance that this variable only depends on the
$Aut(T_{d})$-orbit of $F$. Thus, for an FIID homomorphism we can consider the
entropy of the image in $H$ of a random vertex, random edge, random neighbor,
denote these by $h_{f}(\leavevmode\hbox to2.6pt{\vbox
to2.6pt{\pgfpicture\makeatletter\hbox{\hskip 1.3pt\lower-1.3pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }
{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.1pt}{0.0pt}\pgfsys@curveto{1.1pt}{0.60751pt}{0.60751pt}{1.1pt}{0.0pt}{1.1pt}\pgfsys@curveto{-0.60751pt}{1.1pt}{-1.1pt}{0.60751pt}{-1.1pt}{0.0pt}\pgfsys@curveto{-1.1pt}{-0.60751pt}{-0.60751pt}{-1.1pt}{0.0pt}{-1.1pt}\pgfsys@curveto{0.60751pt}{-1.1pt}{1.1pt}{-0.60751pt}{1.1pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}),h_{f}(\leavevmode\hbox
to2.6pt{\vbox to8.29pt{\pgfpicture\makeatletter\hbox{\hskip
1.3pt\lower-4.14545pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } {}{{}}{}{{{}}{}{}{}{}{}{}{}{}}
{}{}{{{}}{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{-2.84544pt}\pgfsys@moveto{1.1pt}{-2.84544pt}\pgfsys@curveto{1.1pt}{-2.23793pt}{0.60751pt}{-1.74544pt}{0.0pt}{-1.74544pt}\pgfsys@curveto{-0.60751pt}{-1.74544pt}{-1.1pt}{-2.23793pt}{-1.1pt}{-2.84544pt}\pgfsys@curveto{-1.1pt}{-3.45296pt}{-0.60751pt}{-3.94545pt}{0.0pt}{-3.94545pt}\pgfsys@curveto{0.60751pt}{-3.94545pt}{1.1pt}{-3.45296pt}{1.1pt}{-2.84544pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{-2.84544pt}\pgfsys@lineto{0.0pt}{2.84544pt}\pgfsys@moveto{1.1pt}{2.84544pt}\pgfsys@curveto{1.1pt}{3.45296pt}{0.60751pt}{3.94545pt}{0.0pt}{3.94545pt}\pgfsys@curveto{-0.60751pt}{3.94545pt}{-1.1pt}{3.45296pt}{-1.1pt}{2.84544pt}\pgfsys@curveto{-1.1pt}{2.23793pt}{-0.60751pt}{1.74544pt}{0.0pt}{1.74544pt}\pgfsys@curveto{0.60751pt}{1.74544pt}{1.1pt}{2.23793pt}{1.1pt}{2.84544pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{2.84544pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}),h_{f}(\leavevmode\hbox
to2.6pt{\vbox to7.19pt{\pgfpicture\makeatletter\hbox{\hskip
1.3pt\lower-3.04544pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }
{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{2.84544pt}\pgfsys@moveto{1.1pt}{2.84544pt}\pgfsys@curveto{1.1pt}{3.45296pt}{0.60751pt}{3.94545pt}{0.0pt}{3.94545pt}\pgfsys@curveto{-0.60751pt}{3.94545pt}{-1.1pt}{3.45296pt}{-1.1pt}{2.84544pt}\pgfsys@curveto{-1.1pt}{2.23793pt}{-0.60751pt}{1.74544pt}{0.0pt}{1.74544pt}\pgfsys@curveto{0.60751pt}{1.74544pt}{1.1pt}{2.23793pt}{1.1pt}{2.84544pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{2.84544pt}\pgfsys@fillstroke\pgfsys@invoke{
} {}{{}}{}
{}{}{}\pgfsys@moveto{0.0pt}{-2.84544pt}\pgfsys@lineto{0.0pt}{2.84544pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}),$ respectively.

The following fundamental result is shown in [3, 8, 23] in various
generalities (see also [1]).

######  Theorem 2.1.

For any FIID homomorphism $f$ (or more generally, FIID process) on $T_{3}$ we
have

$\frac{4}{3}h_{f}(\leavevmode\hbox to2.6pt{\vbox
to2.6pt{\pgfpicture\makeatletter\hbox{\hskip 1.3pt\lower-1.3pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }
{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.1pt}{0.0pt}\pgfsys@curveto{1.1pt}{0.60751pt}{0.60751pt}{1.1pt}{0.0pt}{1.1pt}\pgfsys@curveto{-0.60751pt}{1.1pt}{-1.1pt}{0.60751pt}{-1.1pt}{0.0pt}\pgfsys@curveto{-1.1pt}{-0.60751pt}{-0.60751pt}{-1.1pt}{0.0pt}{-1.1pt}\pgfsys@curveto{0.60751pt}{-1.1pt}{1.1pt}{-0.60751pt}{1.1pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}})\leq
h_{f}(\leavevmode\hbox to2.6pt{\vbox
to8.29pt{\pgfpicture\makeatletter\hbox{\hskip 1.3pt\lower-4.14545pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } {}{{}}{}{{{}}{}{}{}{}{}{}{}{}}
{}{}{{{}}{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{-2.84544pt}\pgfsys@moveto{1.1pt}{-2.84544pt}\pgfsys@curveto{1.1pt}{-2.23793pt}{0.60751pt}{-1.74544pt}{0.0pt}{-1.74544pt}\pgfsys@curveto{-0.60751pt}{-1.74544pt}{-1.1pt}{-2.23793pt}{-1.1pt}{-2.84544pt}\pgfsys@curveto{-1.1pt}{-3.45296pt}{-0.60751pt}{-3.94545pt}{0.0pt}{-3.94545pt}\pgfsys@curveto{0.60751pt}{-3.94545pt}{1.1pt}{-3.45296pt}{1.1pt}{-2.84544pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{-2.84544pt}\pgfsys@lineto{0.0pt}{2.84544pt}\pgfsys@moveto{1.1pt}{2.84544pt}\pgfsys@curveto{1.1pt}{3.45296pt}{0.60751pt}{3.94545pt}{0.0pt}{3.94545pt}\pgfsys@curveto{-0.60751pt}{3.94545pt}{-1.1pt}{3.45296pt}{-1.1pt}{2.84544pt}\pgfsys@curveto{-1.1pt}{2.23793pt}{-0.60751pt}{1.74544pt}{0.0pt}{1.74544pt}\pgfsys@curveto{0.60751pt}{1.74544pt}{1.1pt}{2.23793pt}{1.1pt}{2.84544pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{2.84544pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}).$

The next theorem follows from the fact that large random $3$-regular graphs
have independence ratio $<\frac{1}{2}$ ([7]) together with the observation
that FIID processes can be “emulated” on random regular graphs (see [19,
Section 4]).

######  Theorem 2.2.

The size of the largest FIID independent set in $T_{3}$ is bounded away from
$\frac{1}{2}$. In particular, there is some $c_{0}>0$ such that if $f$ is a
FIID partial $2$-coloring of $T_{3}$ then $\mu(dom(f))<1-c_{0}$.

##  3\. Proof of the theorem

Now we state and prove a more precise version of our result. Let
$C_{r}>r^{\frac{3}{c_{0}}}$, where $c_{0}$ is the constant from Theorem 2.2.

######  Theorem 3.1.

Assume that $H$ is an $r$-regular graph with girth $\geq C_{r}$. Then there is
no FIID homomorphism from $T_{3}$ to $H$.

###### Proof.

Assume that $f$ is a FIID homomorphism to the $r$-regular graph $H$. We start
with estimating the vertex entropy.

######  Lemma 3.2.

$h_{f}(\leavevmode\hbox to2.6pt{\vbox
to2.6pt{\pgfpicture\makeatletter\hbox{\hskip 1.3pt\lower-1.3pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }
{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.1pt}{0.0pt}\pgfsys@curveto{1.1pt}{0.60751pt}{0.60751pt}{1.1pt}{0.0pt}{1.1pt}\pgfsys@curveto{-0.60751pt}{1.1pt}{-1.1pt}{0.60751pt}{-1.1pt}{0.0pt}\pgfsys@curveto{-1.1pt}{-0.60751pt}{-0.60751pt}{-1.1pt}{0.0pt}{-1.1pt}\pgfsys@curveto{0.60751pt}{-1.1pt}{1.1pt}{-0.60751pt}{1.1pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}})\leq 3\ln r$.

###### Proof.

Observe that

$h_{f}(\leavevmode\hbox to2.6pt{\vbox
to8.29pt{\pgfpicture\makeatletter\hbox{\hskip 1.3pt\lower-4.14545pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } {}{{}}{}{{{}}{}{}{}{}{}{}{}{}}
{}{}{{{}}{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{-2.84544pt}\pgfsys@moveto{1.1pt}{-2.84544pt}\pgfsys@curveto{1.1pt}{-2.23793pt}{0.60751pt}{-1.74544pt}{0.0pt}{-1.74544pt}\pgfsys@curveto{-0.60751pt}{-1.74544pt}{-1.1pt}{-2.23793pt}{-1.1pt}{-2.84544pt}\pgfsys@curveto{-1.1pt}{-3.45296pt}{-0.60751pt}{-3.94545pt}{0.0pt}{-3.94545pt}\pgfsys@curveto{0.60751pt}{-3.94545pt}{1.1pt}{-3.45296pt}{1.1pt}{-2.84544pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{-2.84544pt}\pgfsys@lineto{0.0pt}{2.84544pt}\pgfsys@moveto{1.1pt}{2.84544pt}\pgfsys@curveto{1.1pt}{3.45296pt}{0.60751pt}{3.94545pt}{0.0pt}{3.94545pt}\pgfsys@curveto{-0.60751pt}{3.94545pt}{-1.1pt}{3.45296pt}{-1.1pt}{2.84544pt}\pgfsys@curveto{-1.1pt}{2.23793pt}{-0.60751pt}{1.74544pt}{0.0pt}{1.74544pt}\pgfsys@curveto{0.60751pt}{1.74544pt}{1.1pt}{2.23793pt}{1.1pt}{2.84544pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{2.84544pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}})=h_{f}(\leavevmode\hbox
to2.6pt{\vbox to2.6pt{\pgfpicture\makeatletter\hbox{\hskip
1.3pt\lower-1.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }
{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.1pt}{0.0pt}\pgfsys@curveto{1.1pt}{0.60751pt}{0.60751pt}{1.1pt}{0.0pt}{1.1pt}\pgfsys@curveto{-0.60751pt}{1.1pt}{-1.1pt}{0.60751pt}{-1.1pt}{0.0pt}\pgfsys@curveto{-1.1pt}{-0.60751pt}{-0.60751pt}{-1.1pt}{0.0pt}{-1.1pt}\pgfsys@curveto{0.60751pt}{-1.1pt}{1.1pt}{-0.60751pt}{1.1pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}})+h_{f}(\leavevmode\hbox
to2.6pt{\vbox to7.19pt{\pgfpicture\makeatletter\hbox{\hskip
1.3pt\lower-3.04544pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }
{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{2.84544pt}\pgfsys@moveto{1.1pt}{2.84544pt}\pgfsys@curveto{1.1pt}{3.45296pt}{0.60751pt}{3.94545pt}{0.0pt}{3.94545pt}\pgfsys@curveto{-0.60751pt}{3.94545pt}{-1.1pt}{3.45296pt}{-1.1pt}{2.84544pt}\pgfsys@curveto{-1.1pt}{2.23793pt}{-0.60751pt}{1.74544pt}{0.0pt}{1.74544pt}\pgfsys@curveto{0.60751pt}{1.74544pt}{1.1pt}{2.23793pt}{1.1pt}{2.84544pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{2.84544pt}\pgfsys@fillstroke\pgfsys@invoke{
} {}{{}}{}
{}{}{}\pgfsys@moveto{0.0pt}{-2.84544pt}\pgfsys@lineto{0.0pt}{2.84544pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}|\leavevmode\hbox
to2.6pt{\vbox to2.6pt{\pgfpicture\makeatletter\hbox{\hskip
1.3pt\lower-1.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }
{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.1pt}{0.0pt}\pgfsys@curveto{1.1pt}{0.60751pt}{0.60751pt}{1.1pt}{0.0pt}{1.1pt}\pgfsys@curveto{-0.60751pt}{1.1pt}{-1.1pt}{0.60751pt}{-1.1pt}{0.0pt}\pgfsys@curveto{-1.1pt}{-0.60751pt}{-0.60751pt}{-1.1pt}{0.0pt}{-1.1pt}\pgfsys@curveto{0.60751pt}{-1.1pt}{1.1pt}{-0.60751pt}{1.1pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}),$

by the relationship between conditional entropy and joint entropy discussed
above. Since $H$ is $r$-regular, given the image of a vertex, there are only
$r$-many possibilities for choosing its neighbor. In particular, as the
entropy is maximized when the probabilities of the outcomes are equal, the
conditional entropy $h_{f}(\leavevmode\hbox to2.6pt{\vbox
to7.19pt{\pgfpicture\makeatletter\hbox{\hskip 1.3pt\lower-3.04544pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }
{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{2.84544pt}\pgfsys@moveto{1.1pt}{2.84544pt}\pgfsys@curveto{1.1pt}{3.45296pt}{0.60751pt}{3.94545pt}{0.0pt}{3.94545pt}\pgfsys@curveto{-0.60751pt}{3.94545pt}{-1.1pt}{3.45296pt}{-1.1pt}{2.84544pt}\pgfsys@curveto{-1.1pt}{2.23793pt}{-0.60751pt}{1.74544pt}{0.0pt}{1.74544pt}\pgfsys@curveto{0.60751pt}{1.74544pt}{1.1pt}{2.23793pt}{1.1pt}{2.84544pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{2.84544pt}\pgfsys@fillstroke\pgfsys@invoke{
} {}{{}}{}
{}{}{}\pgfsys@moveto{0.0pt}{-2.84544pt}\pgfsys@lineto{0.0pt}{2.84544pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}|\leavevmode\hbox
to2.6pt{\vbox to2.6pt{\pgfpicture\makeatletter\hbox{\hskip
1.3pt\lower-1.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }
{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.1pt}{0.0pt}\pgfsys@curveto{1.1pt}{0.60751pt}{0.60751pt}{1.1pt}{0.0pt}{1.1pt}\pgfsys@curveto{-0.60751pt}{1.1pt}{-1.1pt}{0.60751pt}{-1.1pt}{0.0pt}\pgfsys@curveto{-1.1pt}{-0.60751pt}{-0.60751pt}{-1.1pt}{0.0pt}{-1.1pt}\pgfsys@curveto{0.60751pt}{-1.1pt}{1.1pt}{-0.60751pt}{1.1pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}})$ is bounded by $\ln
r$. Thus,

$h_{f}(\leavevmode\hbox to2.6pt{\vbox
to8.29pt{\pgfpicture\makeatletter\hbox{\hskip 1.3pt\lower-4.14545pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } {}{{}}{}{{{}}{}{}{}{}{}{}{}{}}
{}{}{{{}}{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{-2.84544pt}\pgfsys@moveto{1.1pt}{-2.84544pt}\pgfsys@curveto{1.1pt}{-2.23793pt}{0.60751pt}{-1.74544pt}{0.0pt}{-1.74544pt}\pgfsys@curveto{-0.60751pt}{-1.74544pt}{-1.1pt}{-2.23793pt}{-1.1pt}{-2.84544pt}\pgfsys@curveto{-1.1pt}{-3.45296pt}{-0.60751pt}{-3.94545pt}{0.0pt}{-3.94545pt}\pgfsys@curveto{0.60751pt}{-3.94545pt}{1.1pt}{-3.45296pt}{1.1pt}{-2.84544pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{-2.84544pt}\pgfsys@lineto{0.0pt}{2.84544pt}\pgfsys@moveto{1.1pt}{2.84544pt}\pgfsys@curveto{1.1pt}{3.45296pt}{0.60751pt}{3.94545pt}{0.0pt}{3.94545pt}\pgfsys@curveto{-0.60751pt}{3.94545pt}{-1.1pt}{3.45296pt}{-1.1pt}{2.84544pt}\pgfsys@curveto{-1.1pt}{2.23793pt}{-0.60751pt}{1.74544pt}{0.0pt}{1.74544pt}\pgfsys@curveto{0.60751pt}{1.74544pt}{1.1pt}{2.23793pt}{1.1pt}{2.84544pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{2.84544pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}})\leq
h_{f}(\leavevmode\hbox to2.6pt{\vbox
to2.6pt{\pgfpicture\makeatletter\hbox{\hskip 1.3pt\lower-1.3pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }
{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.1pt}{0.0pt}\pgfsys@curveto{1.1pt}{0.60751pt}{0.60751pt}{1.1pt}{0.0pt}{1.1pt}\pgfsys@curveto{-0.60751pt}{1.1pt}{-1.1pt}{0.60751pt}{-1.1pt}{0.0pt}\pgfsys@curveto{-1.1pt}{-0.60751pt}{-0.60751pt}{-1.1pt}{0.0pt}{-1.1pt}\pgfsys@curveto{0.60751pt}{-1.1pt}{1.1pt}{-0.60751pt}{1.1pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}})+\ln r.$

Combining this with Theorem 2.1, i.e., with

$\frac{4}{3}h_{f}(\leavevmode\hbox to2.6pt{\vbox
to2.6pt{\pgfpicture\makeatletter\hbox{\hskip 1.3pt\lower-1.3pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }
{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.1pt}{0.0pt}\pgfsys@curveto{1.1pt}{0.60751pt}{0.60751pt}{1.1pt}{0.0pt}{1.1pt}\pgfsys@curveto{-0.60751pt}{1.1pt}{-1.1pt}{0.60751pt}{-1.1pt}{0.0pt}\pgfsys@curveto{-1.1pt}{-0.60751pt}{-0.60751pt}{-1.1pt}{0.0pt}{-1.1pt}\pgfsys@curveto{0.60751pt}{-1.1pt}{1.1pt}{-0.60751pt}{1.1pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}})\leq
h_{f}(\leavevmode\hbox to2.6pt{\vbox
to8.29pt{\pgfpicture\makeatletter\hbox{\hskip 1.3pt\lower-4.14545pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } {}{{}}{}{{{}}{}{}{}{}{}{}{}{}}
{}{}{{{}}{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{-2.84544pt}\pgfsys@moveto{1.1pt}{-2.84544pt}\pgfsys@curveto{1.1pt}{-2.23793pt}{0.60751pt}{-1.74544pt}{0.0pt}{-1.74544pt}\pgfsys@curveto{-0.60751pt}{-1.74544pt}{-1.1pt}{-2.23793pt}{-1.1pt}{-2.84544pt}\pgfsys@curveto{-1.1pt}{-3.45296pt}{-0.60751pt}{-3.94545pt}{0.0pt}{-3.94545pt}\pgfsys@curveto{0.60751pt}{-3.94545pt}{1.1pt}{-3.45296pt}{1.1pt}{-2.84544pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{-2.84544pt}\pgfsys@lineto{0.0pt}{2.84544pt}\pgfsys@moveto{1.1pt}{2.84544pt}\pgfsys@curveto{1.1pt}{3.45296pt}{0.60751pt}{3.94545pt}{0.0pt}{3.94545pt}\pgfsys@curveto{-0.60751pt}{3.94545pt}{-1.1pt}{3.45296pt}{-1.1pt}{2.84544pt}\pgfsys@curveto{-1.1pt}{2.23793pt}{-0.60751pt}{1.74544pt}{0.0pt}{1.74544pt}\pgfsys@curveto{0.60751pt}{1.74544pt}{1.1pt}{2.23793pt}{1.1pt}{2.84544pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{2.84544pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}),$

and rearranging, we get the desired inequality. ∎

Now we show that

######  Lemma 3.3.

There exists a set $S\subset V(H)$ such that $|S|<C_{r}$ and
$\mu(f^{-1}(S))\geq 1-c_{0}$.

###### Proof.

For $v\in V(H)$ let $p_{v}=\mu(f^{-1}(v))$. Take the set $S$ of vertices of
$H$ having the first $C_{r}-1$ largest $p_{v}$ values. Now, assume
$\mu(f^{-1}(S))<1-c_{0}$. Then

$h_{f}(\leavevmode\hbox to2.6pt{\vbox
to2.6pt{\pgfpicture\makeatletter\hbox{\hskip 1.3pt\lower-1.3pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }
{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.1pt}{0.0pt}\pgfsys@curveto{1.1pt}{0.60751pt}{0.60751pt}{1.1pt}{0.0pt}{1.1pt}\pgfsys@curveto{-0.60751pt}{1.1pt}{-1.1pt}{0.60751pt}{-1.1pt}{0.0pt}\pgfsys@curveto{-1.1pt}{-0.60751pt}{-0.60751pt}{-1.1pt}{0.0pt}{-1.1pt}\pgfsys@curveto{0.60751pt}{-1.1pt}{1.1pt}{-0.60751pt}{1.1pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}})\geq\sum_{v\not\in
S}-p_{v}\ln p_{v}\geq-c_{0}\ln\frac{1}{C_{r}},$

and by Lemma 3.2 we have

$3\ln r\geq c_{0}\ln C_{r},$

so

$C_{r}\leq r^{\frac{3}{c_{0}}},$

contradicting the choice of $C_{r}$. ∎

In order to finish the proof, observe that as the girth of $H$ is $\geq
C_{r}$, the set $S$ induces an acyclic graph in $H$. Let $c$ be a $2$-coloring
of this graph. Then $c\circ f|_{f^{-1}(S)}$ is a partial FIID $2$-coloring of
$T_{3}$ with domain of size $\geq 1-c_{0}$ contradicting Theorem 2.2.

∎

##  4\. An open problem

A satisfying negative answer to Problem 1.1 would be to establish that given a
finite graph $H$, deciding the existence of an FIID homomorphism from $T_{3}$
to $H$ is computationally hard. In order to achieve this, one must come up
with ways to ensure the existence of FIID homomorphisms and conversely, to
exclude these as well. We believe that it might be possible to use entropy
inequalities prove the latter part of such results. However, our knowledge
about the former seems to be seriously lacking, in particular, we know only
examples of graphs $H$ to which $T_{3}$ admits an FIID homomorphism which are
“close” to complete graphs.

######  Problem 4.1.

Find sufficient conditions on $H$ for the existence of FIID homomorphisms from
$T_{d}$ to $H$. Is it true that if there is an FIID homomorphism from $T_{3}$
to $H$ then $H$ must contain a triangle?

## References

  * [1] Á. Backhausz, B. Gerencsér, and V. Harangi.  Entropy inequalities for factors of iid.  Groups, Geometry, and Dynamics, 13(2):389–414, 2018.
  * [2] Á. Backhausz, B. Gerencsér, V. Harangi, and M. Vizer.  Correlation bounds for distant parts of factor of iid processes.  Combin. Probab. Comput., 27(1):1–20, 2018.
  * [3] Á. Backhausz and B. Szegedy.  On large-girth regular graphs and random processes on trees.  Random Structures & Algorithms, 53(3):389–416, 2018.
  * [4] Á. Backhausz and B. Virag.  Spectral measures of factor of i.i.d. processes on vertex-transitive graphs.  Ann. Inst. Henri Poincaré Probab. Stat., 53(4):2260–2278, 2017\.
  * [5] F. Bencs, A. Hrusková, and L. M. Tóth.  Factor of iid schreier decoration of transitive graphs.  arXiv:2101.12577, 2021.
  * [6] A. Bernshteyn.  Distributed algorithms, the lovász local lemma, and descriptive combinatorics.  Inventiones mathematicae, pages 1–48, 2023.
  * [7] B. Bollobás.  The independence ratio of regular graphs.  Proceedings of the American Mathematical Society, 83(2):433–436, 1981.
  * [8] L. P. Bowen.  A measure-conjugacy invariant for free group actions.  Annals of mathematics, pages 1387–1400, 2010.
  * [9] S. Brandt.  An automatic speedup theorem for distributed problems.  In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019, pages 379–388, 2019.
  * [10] S. Brandt, Y.-J. Chang, J. Grebík, C. Grunau, V. Rozhoň, and Z. Vidnyánszky.  Local problems on trees from the perspectives of distributed algorithms, finitary factors, and descriptive combinatorics.  arXiv preprint arXiv:2106.02066, 2021.
  * [11] S. Brandt, Y.-J. Chang, J. Grebík, C. Grunau, V. Rozhoň, and Z. Vidnyánszky.  On homomorphism graphs.  arXiv preprint arXiv:2111.03683, 2021.
  * [12] E. Csóka, B. Gerencsér, V. Harangi, and B. Virág.  Invariant gaussian processes and independent sets on regular graphs of large girth.  Random Structures & Algorithms, 47(2):284–303, 2015.
  * [13] D. Gamarnik and M. Sudan.  Limits of local algorithms over sparse random graphs.  Proceedings of the 5-th Innovations in Theoretical Computer Science conference, ACM Special Interest Group on Algorithms and Computation Theory, 2014.
  * [14] V. Harangi and B. Virág.  Independence ratio and random eigenvectors in transitive graphs.  Ann. Probab., 43(5):2810–2840, 2015.
  * [15] A. E. Holroyd, R. Lyons, and T. Soo.  Poisson splitting by factors.  Ann. Probab., 39(5):1938–1982, 2011.
  * [16] C. Hoppen and N. Wormald.  Local algorithms, regular graphs of large girth, and random regular graphs.  Combinatorica, 38(3):619–664, 2018.
  * [17] A. S. Kechris and A. S. Marks.  Descriptive graph combinatorics.  2015\.  Available at http://math.ucla.edu/~marks/.
  * [18] R. Lyons.  Factors of iid on trees.  Combin. Probab. Comput., 26(2):285–300, 2017.
  * [19] R. Lyons.  Factors of iid on trees.  Combinatorics, Probability and Computing, 26(2):285–300, 2017.
  * [20] A. S. Marks.  A determinacy approach to Borel combinatorics.  J. Amer. Math. Soc., 29(2):579–600, 2016.
  * [21] J. Nesetril.  Aspects of structural combinatorics (graph homomorphisms and their use).  Taiwanese Journal of Mathematics, 3(4):381–423, 1999.
  * [22] M. Rahman and B. Virág.  Local algorithms for independent sets are half-optimal.  Ann. Probab., 45(3):1543–1577, 2017.
  * [23] M. Rahman and B. Virág.  Local algorithms for independent sets are half-optimal.  2017\.
  * [24] Á. Timár.  Tree and grid factors for general point processes.  Electron. Comm. Probab., 9(53–59).