# From Quantum Graph Computing to Quantum Graph Learning: A Survey

Yehui Tang1 Junchi Yan1111 Correspondence author is Junchi Yan. Edwin Hancock2
1Department of CSE, and MoE Key Lab of Artificial Intelligence, Shanghai Jiao
Tong University
2Department of Computer Science, University of York
{yehuitang<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Quantum computing (QC) is a new computational paradigm whose foundations
relate to quantum physics. Notable progress has been made, driving the birth
of a series of quantum-based algorithms that take advantage of quantum
computational power. In this paper, we provide a targeted survey of the
development of QC for graph-related tasks. We first elaborate the correlations
between quantum mechanics and graph theory to show that quantum computers are
able to generate useful solutions that can not be produced by classical
systems efficiently for some problems related to graphs. For its
practicability and wide-applicability, we give a brief review of typical graph
learning techniques designed for various tasks. Inspired by these powerful
methods, we note that advanced quantum algorithms have been proposed for
characterizing the graph structures. We give a snapshot of quantum graph
learning where expectations serve as a catalyst for subsequent research. We
further discuss the challenges of using quantum algorithms in graph learning,
and future directions towards more flexible and versatile quantum graph
learning solvers.

##  1 Introduction

Quantum computing (QC), whose foundations relate to quantum physics, harnesses
the computational power derived from the properties of quantum mechanics to
perform calculations. Quantum computing has attracted wide attention from both
industry and academia for its promising prospective of exponentially
accelerating the traditional approaches Liu et al. (2021); Zlokapa et al.
(2021) as well as naturally exploring the physical systems Preskill (2018);
Hegade et al. (2021).

Benefiting from the unique characteristics of quantum mechanics, which are
totally different from the classical systems, such as superposition,
interference, and entanglement, quantum computing has potential superiority in
many calculation tasks. The most remarkable step is taken by Shor (1994) that
demonstrates two mathematical problems - integer factorization and discrete
logarithm - can be solved efficiently by using quantum computers, whereas no
efficient classical method is known. Furthermore, Grover (1996) points to
another valuable evidence, showing the quantum advantage of searching and
retrieving target values in unstructured databases quadratic faster than the
most effective classical method.

The potential advantages of quantum computers arouse researchers’ curiosity in
solving the problem of graph theory. Early works concentrate on exploiting the
quantum computational power to produce effective solutions to graph
theoretical problems. We classify such quantum algorithms as quantum graph
computing. Two families of graph theoretical problems have been studied
extensively. One family relates to graph representations of combinatorial
optimization problems which are thought to be exponentially hard for classical
computers Moylett et al. (2017). Another family comprises extracting patterns
and finding hidden structures within a number of graphs Chang et al. (2018).
Most of these problems are NP-hard if not even harder, or practically
intractable for large-scale settings for the exact solution. A number of
quantum based algorithms focus on reformulating some of these problems into
computationally solvable forms of quantum computers Calude et al. (2017).
Besides, these algorithms try to use the associated properties of quantum
mechanics to solve problems efficiently and find the exact solution.

More recently modern graph learning techniques has revolutionized graph
analytics tasks such as node classification Kipf and Welling (2017) and graph
classification Chen et al. (2020). Meanwhile, fueled by the advent of quantum
hardware and the high-performance quantum simulation frameworks, an increasing
amount of literature on quantum machine learning has been proposed in recent
years, showing the quantum potential of both acceleration of the computational
process and improvement of the performance. With the power of data, quantum
machine learning has the potential of finding atypical but useful patterns
that classical systems are not considered to be able to generate effectively
Huang et al. (2021). It seems an attractive direction towards combining the
expressive ability of classical graph learning techniques with the power of
quantum computing. We call it quantum graph learning. In this paper, we give a
snapshot of quantum graph learning and hope that it can inspire more in-depth
research.

There are reviews on quantum computing and quantum machine learning. Montanaro
(2016); Biamonte et al. (2017) overview quantum algorithms that have the
potential speed-ups. They mainly review idealized quantum algorithms that
efficiently perform linear algebraic operations. Adedoyin et al. (2018)
conducts a survey focused on the gate-model quantum computer. Preskill (2018)
reports quantum algorithms that can be executed on the current quantum
hardware and the future potential of quantum computing is discussed. Dunjko
and Briegel (2018) investigates the interaction between machine learning,
artificial intelligence and quantum mechanics. Cerezo et al. (2020) limits the
scope within the quantum algorithms based on parameterized quantum circuits.
In summary, existing surveys have not fully reflected the state-of-the-art
development of quantum computing, especially for graph algorithms. Our survey
focuses on quantum algorithms on graphs, from quantum graph computing to
quantum graph learning, which we believe is an emerging field.

##  2 Quantum Graph Computing

There are three common paths intersecting quantum computing and graph theory.
First, some works consider an underlying graph structure consisting of nodes
connected by edges and perform quantum evolution on this structure, in which
an important quantum paradigm is Hamiltonian encoding. Second, the
relationship between the transition rules of a graph and the randomness of the
quantum representation is explored from the point of view of utilizing the
superposition and entanglement of quantum states to characterize the
properties of graphs, e.g., quantum random walks. In this case, the quantum
states preserve the features of nodes and edges of the original graph as well
as its topology information. Another way to build quantum graph solvers is the
employment of quantum search, which, in most cases, provides quadratic
acceleration over traditional exhaustive search methods. Here we discuss the
synergy of these three areas.

###  2.1 Hamiltonian Encoding based Solvers

One approach to developing universal quantum computing is adiabatic quantum
computing (AQC), which relies on the adiabatic theorem that evaluates the
continuous-time evolution of a quantum system. To describe the dynamics of an
arbitrary quantum system, a class of Hamiltonians is defined

$H=\sum_{i<j}J_{ij}\sigma_{i}^{z}\sigma_{j}^{z}+\sum_{i}h_{i}\sigma_{i}^{z}+\sum_{i}g_{i}\sigma_{i}^{x},$
(1)

where $\sigma^{z}$, $\sigma^{x}$ are Pauli matrices. Broadly speaking, Eq. 1
can be viewed as a transverse-field Ising model and such model is QMA-complete
Albash and Lidar (2018). The first two terms push the quantum bit (qubit) to
be either $|0\rangle$ or $|1\rangle$, whereas the last pushes the state to a
superposition. An outside measurement leads to the collapse from superposition
to a deterministic state. These foundations give the ability for quantum
computers to handle certain problems that can not be efficiently solved
classically. To implement such models in a real physical process, quantum
annealing (QA) captures the relaxation of the adiabatic conditions and
controls the continuous-time evolution at finite temperature and in open
environments. Machines performing QA at the hardware level attempt to minimize
the energy determined by the Hamiltonian, and the output of an anneal is a
low-energy ground state, which consists of an Ising spin for each qubit where
the eigenvalues $\\{+1,-1\\}$ of Pauli matrix $\sigma^{z}$ correspond to the
binary constraint of the properties of classical Ising model Ushijima-Mwesigwa
et al. (2017). This is closely related to the quadratic unconstrained binary
optimization (QUBO) problem - a combinatorial optimization problem that can be
applied to many graph theoretical problems.

Many NP-hard problems can be expressed as the minimization of the energy of
the Hamiltonian as the form of Eq. 1 e.g. graph partitioning, graph coloring,
vertex cover and clique finding Lucas (2014). Therefore, varieties of
contributions concentrate on relaxing and reformulating these graph-related
combinatorial optimization problems into the QUBO formulation and utilizing QA
to quickly approach the exact solution. The method in Chams et al. (1987)
converts the graph coloring problem to graph partitioning and employs
simulated annealing to screen the better solution of the problem. Different
annealing schemes are exploited in Silva et al. (2020). These schemes dominate
traditional techniques for certain types of graphs with the cost of long
computing time. To transform a set of constraints to the energy minimization
problem, penalty terms associated with the constraints should be added to the
QUBO quadratic expression Silva et al. (2020). Besides, reduction and
approximation are necessary for space efficient. Their work demonstrates that
the quantum annealer can more reliably approach the optimal solution and
produce better heuristics for graph coloring under specific settings.

Existing quantum hardware can only control a relatively small number of
qubits, which is far from the size for large-scale data processing. In
addition, it is difficult to fully embed real-world optimization problems on
quantum devices as a consequence of poor connectivity between arbitrary
couples of qubits. As a result, the qubit connectivity in quantum hardware
rarely matches the QUBO form described by the underlying graph structure. To
overcome these problems, the authors of Bass et al. (2018) present a
heterogeneous algorithm that uses classical co-processing to preprocess the
primitive problem and randomly selects a large number of possible solutions,
after which the reduced form of the max clique problem corresponding to the
largest possible solutions can be encoded into the quantum annealer for
accelerating the searching process. In Pelofske et al. (2019), a decomposition
alternative divides a big input graph into multiple smaller subgraphs that fit
the quantum annealer to further improve the adaptability. Other applications
also show the benefits of using Hamiltonian to encode and solve graph related
problems including graph isomorphism problem Calude et al. (2017); Ushijima-
Mwesigwa et al. (2017) and vertex cover problem Pelofske et al. (2019).
Likewise, recent works demonstrate quantum annealing has potential advantages
over classical approaches ranging from optimization Brady et al. (2021) to
machine learning Nath et al. (2021). However, it is difficult to ensure the
final quantum state to be the ground state, meaning that the final solution is
probably not optimal. Besides, with the increase of the size of the system and
the complexity of the problem, it seems reasonable to expect the annealing
time to scale exponentially for problems with exponentially small gaps,
especially for NP-hard problems Albash and Marshall (2021).

###  2.2 Quantum Random Walks based Solvers

Another way to represent the topological information of graphs in quantum
information is quantum random walks (QRWs). Motivated by the widespread use of
classical random walks, QRWs view a graph as a collection of nodes in either
real or complex space, among which the correlations between two nodes are
indicated by edges. The Walker evolves in a quantum mechanical manner over
time by characterizing its initial distribution in terms of the amplitudes of
quantum states. Compared with classical random walks, where the stochastic
transition matrix determines the random patterns, the randomness of QRWs
depends on the reversible unitary translation. No internal information could
be obtained until the final states are measured. Readers are referred to Kempe
(2003); Venegas-Andraca (2012) for introductions on QRWs. Here, we provide a
brief overview of the two types of QRWs with typical progress on solving graph
related tasks.

#### Discrete Time Quantum Random Walks

One way to intersperse quantum effects with random walks is the discrete time
quantum random walks (DT-QRWs). Let $\mathcal{H}_{P}$ be the Hilbert space
spanned by the positions of the nodes, and $\mathcal{H}_{C}$ be the
‘coin’-space whose dimension is usually equivalent to the maximal degree of
the graph Kempe (2003). The state of the whole graph can be described by the
space $\mathcal{H}=\mathcal{H}_{C}\otimes\mathcal{H}_{P}$. Suppose that a
unitary operator $C$ determines the possibility of the diffusing direction,
and $S$ indicates the conditional transition of the system, the DT-QRWs of
step $T$ is defined as the transformation $U^{T}$, and $U$ is written as
$U=S\cdot(C\otimes I)$, where $I$ is the identity matrix Venegas-Andraca
(2012). By repeating the succession of unitary translation $U$, i.e.,
transforming the state $|\psi_{t}\rangle=U|\psi_{t-1}\rangle$ iteratively with
timestamp $t$, the distribution of the walker can be encoded in the final
state. Measuring the coin-register of the walk in the computational basis
states will output the classical information of the probability distribution.

#### Continuous Time Quantum Random Walks

Another way to model the quantum diffusing is the continuous time quantum
random walks (CT-QRWs). For the general classical random walk in the form of
the differential equation, the probability distribution at time $t$ of node
$i$ is: $\frac{dp_{i}(t)}{dt}=-\sum_{j}H_{i,j}p_{j}(t),$ where matrix $H$ is
an analogue to the classical transition matrix, whereas each entry of $H$ is
the possibility of jumping from node $i$ to node $j$. Solving the equation we
obtain $\vec{p}(t)=e^{-Ht}\vec{p}(0)$, and Farhi and Gutmann (1998) extends
this concept to quantum case by using the Hamiltonian to establish the
continuous evolution $U(t)=e^{-iHt}$. If we start in some initial state
$|\psi_{0}\rangle$, evolve it under $U$ for a time $t$ and measure the
positions of the resulting state we obtain a probability distribution over the
nodes of the graph Kempe (2003). In contract to the classical random walks,
quantum diffusion is a reversible process and it does not converge to a
stationary distribution in general, and an average distribution called Cesaro
limit $\vec{c}^{t}$ is introduced to obtain a stationary distribution:
$\vec{c}_{i}^{t}=\frac{1}{t}\sum_{s=1}^{t}\vec{p}_{i}^{s}$.

#### Overview of QRWs-based Solvers

These ideas of quantum diffusion are generalized to develop varieties of graph
solvers for graph theoretical problems. QRWs often induce an asymmetric
probability distribution mainly due to their intrinsic interference pattern
and unusual collapse characteristics. It is evident that the interference
pattern of QRWs is much more intricate than the Gaussian obtained in the
classical case Kempe (2003). The first attempt to develop an exponential
separation of classical and quantum random walks is given by Childs et al.
(2002). They construct a binary glue tree and demonstrate that DT-QRWs are
able to penetrate the graph in polynomial time. Childs and Eisenberg (2005)
develops an algorithm based on DT-QRWs for more general subgraph finding
problems, i.e., L-subset distinctness in polynomial time for a small size of
the subgraph. More intricate tasks including graph matching and graph
distinction can also be handled using the quantum inference of QRWs Emms et
al. (2009b, a). Although there are many correlations between CT-QRWs and DT-
QRWs, the authors of Kempe (2005) find that in the hypercube case, the hitting
time of DT-QRWs is exponentially faster than that of classical random walks,
whereas the CT-QRWs do not converge to the uniform distribution at all. The
relationship between the transition pattern of CT-QRWs and the spectrum of a
regular graph is revealed by Ren et al. (2011), which characterizes the
capacity of the Ihara zeta function in distinguishing graphs. It is shown in
Emms et al. (2009c) that node embeddings produced by the hitting time
associated with the CT-QRWs tend to capture more structural information.

###  2.3 Quantum Search based Solvers

The quantum search algorithm, also known as Grover’s algorithm, is first
proposed by Grover (1996) at the theoretical level. This algorithm
incorporates a superposition of all possible states related to the problem.
Then a unitary operator is used to change the amplitudes of each state while
maximizing the amplitudes of the desired state which can be extracted by
measuring. It is especially suitable for the application scenarios where a set
of specific solutions are searched and retrieved in a huge number of
candidates. For the function whose output size is $N$, the quantum search
algorithm finds the desired input value by using just $O(\sqrt{N})$
evaluations of the function with high probability. In particular, many graph
theoretical problems are NP-hard if not even tougher, and the search space
grows exponentially with the problem’s size. It is reasonable to handle these
problems in terms of quantum computing power.

It is shown in Dürr et al. (2006) that quantum search algorithm decreases the
query complexity further for certain graph problems including spanning tree,
connectivity, strong connectivity and single source shortest path. In Hillery
et al. (2010), the search is performed by quantum random walks to find the
marked clique of a complete graph. A novel quantum search architecture Černỳ
(1993) is developed to solve the travelling salesman problem (TSP). However,
Greenwood (2001) points out this scheme does not mean quantum computers can
solve arbitrary NP-hard problems in polynomial time since the number of qubits
to represent the superposition states is astronomical. An efficient quantum
approach proposed by Srinivasan et al. (2018) combines the quantum phase
estimation algorithm Kitaev (1996) with the quantum search algorithm to solve
the TSP. It provides a quadratic speedup over the classical brute force
method. A breakthrough to achieve quantum speedups for TSP and several NP-hard
problems presented by Ambainis et al. (2019) integrates Grover’s algorithm
with classical dynamic programming. Despite the fact that quantum search has
the potential to solve various complex graph related problems, developing a
quantum algorithm that promises to be faster than the best classical algorithm
remains difficult, as classical techniques do not always rely on exhaustive
search.

##  3 Classic Graph Learning

We provide background on classic graph learning. It in general attempts to
assign a vector representation to each of the (sub)graphs, preserving both
structural information and node features.

###  3.1 Factorization based Embedding Approaches

By representing the graph’s edges and connected nodes as low-dimensional
vectors that preserve global properties of the graph, the subsequent graph
analytics tasks can be easily addressed by employing mature machine learning
algorithms Goyal and Ferrara (2018). Here we introduce the factorization based
approaches and discuss their pros and cons.

Matrix Factorization based Approaches There are a variety of graph learning
approaches that represent the correlations between nodes by factorizing the
matrix that contains the graph information to obtain the embedding. Different
tasks require the factorization of matrices with different properties. Graph
Laplacian eigenmaps Belkin and Niyogi (2001) constructs a low-dimensional
representation for each node while keeping the smoothness of the distinctness
of connected nodes. To circumvent the loss of local topology information, a
Cauchy graph embedding method developed by Luo et al. (2011) is employed to
preserve the similarity relationships of the original graph data, and
introduce a more effective objective function to emphasize the similarity
efficacy. However, the factorization of the matrix of the graph with massive
nodes often requires huge computing resources. Ahmed et al. (2013) proposes a
factorization technique that relies on graph partitioning to enhance
scalability.

Random Walk based Approaches Random walk statistics is widely used to capture
the graph properties. The latent representation of the node that captures the
local structure information is condensed into the low-dimensional feature
vector by performing a diffusing process. DeepWalk Perozzi et al. (2014)
generates the training data in terms of compressing the graph structure into a
text like corpus using random walk, and trains the graph learner to maximize
the occurrence probability of neighbors in the walk. Node2vec Grover and
Leskovec (2016) employs biased random walk to make a trade-off between
breadth-first (BFS) and depth-first (DFS) graph searches, resulting in higher-
quality and more informative embeddings than DeepWalk. Qiu et al. (2018) shows
that many random walk based approaches also perform implicit matrix
factorization, since the requirement of the specific adjacent matrix or
Laplacian matrix before performing learning. Most of these methods are
inherently transductive.

###  3.2 Graph Kernel Methods

Inspired by the kernel methods which utilize a linear classifier to solve non-
linear problems, graph kernel methods have been widely used for graph-level
tasks, e.g., classification and clustering. They directly compare the
structures of the subgraphs by defining a user-specific similarity metric or a
meaningful distance measurement on graphs. In contrast to the factorization
based approaches representing the graph information as low-dimensional
vectors, graph kernel methods characterize graph features implicitly in a high
dimensional space. It involves performing pairwise comparisons between local
substructures centered at every node.

Most early graph kernel works belong to the family of R-convolution kernels
Haussler (1999). More recently, Tian et al. (2019) shows a kernel-based
framework to produce hidden representations of nodes, bridging the gap between
graph kernel methods and graph neural networks. Chen et al. (2020) combines
the message passing mechanism with the graph kernel and constructs a
convolutional kernel network to represent the graph effectively. The high
computational complexity of graph kernel methods suppresses their
applicability. While it is still valuable to study the theoretical framework
behind the graph learning approaches using graph kernel methods due to their
inherent transparency and interpretability.

###  3.3 Graph Neural Networks

For graph learning, Graph neural networks (GNNs) are a type of deep learning
method for extracting the pattern of graph structural data, which dominate the
literature.

Recurrent Graph Neural Networks The initial trial of the GNNs is recurrent
graph neural networks whose foundations relate to the information diffusion
mechanism. In the prototype Scarselli et al. (2008) of recurrent graph neural
networks, the node hidden embedding is updated by the adjacent neighbors. This
process continues until a stable equilibrium is reached. A gated recurrent
unit (GRU) is used as a recurrent function in a gated graph neural network
(GGNN) Li et al. (2016), restricting the recurrence to a few steps.

Convolutional Graph Neural Networks A number of convolutional graph neural
networks can be categorized into a general framework named Message Passing
Neural Network (MPNN) Gilmer et al. (2017). The forward pass of these models
has two phases - an aggregation phase and an update phase - that run
iteratively to let information propagate further. The aggregation phase serves
to detect (multiple) patterns in multiple sub-regions of the input graph,
while the update phase generally consists of pooing functions that collapse
the hidden features of interrelated sub-regions into a new vector
representation. Some studies perform graph convolution operation building upon
the signal processing on graphs Shuman et al. (2013).

Category | Method | Attribute | Embedding | Input | Layer | Readout | Application
---|---|---|---|---|---|---|---
QK-based | QJSK Bai et al. (2015) | ✗ | ✓ | C | Q & C | Tomography | Graph Classification
GBSK Schuld et al. (2020) | ✗ | ✓ | C | Q & C | Estimation | Graph Classification
SFGK Kishi et al. (2021) | ✗ | ✓ | C | Q & C | Swap Test | Graph Classification
QEK Henry et al. (2021) | ✗ | ✓ | C | Q & C | Tomography | Graph Classification
Shallow Circuit | QGNN Verdon et al. (2019) | ✗ | ✓ | Q | Q | Tomography | Graph Isomorphism
QGCN Zheng et al. (2021) | ✓ | ✗ | Syn. | Q & C | Estimation | Graph Classification
DQGNN Ai et al. (2022) | ✓ | ✗ | C | Q & C | Tomography | Graph Classification
EQGC Mernyei et al. (2021) | ✗ | ✓ | Syn. | Q & C | Estimation | Graph Classification
QNN Beer et al. (2021) | ✗ | ✓ | Q | Q | Estimation | Network Embedding
Hybrid Deep | QWNN Dernbach et al. (2018) | ✓ | ✓ | C | Q & C | Tomography | Node Classification
QSGCNN Bai et al. (2021) | ✓ | ✓ | C | Q & C | Tomography | Graph Classification
QSCNN Zhang et al. (2019) | ✓ | ✓ | C | Q & C | Tomography | Node Classification
QGCNN Chen et al. (2021) | ✓ | ✗ | C | Q & C | Estimation | Graph Classification
HQGNN Tüysüz et al. (2021) | ✗ | ✓ | C | Q & C | Estimation | Link Prediction

Table 1: Comparison between quantum graph learning methods and their
application. Although most of these methods employ the topology embedding that
incorporates structural information into the quantum representation, node
attributes are not considered in some research. The input data is classical
(C), quantum (Q) or synthetic (Syn.). For the methods with classical or
synthetic inputs, the classical layer is inevitably introduced to preprocess
the graph data or assist the quantum computer to update the model parameters.
The readout operation is the interaction transforming the quantum information
into the classical expression, where the tomography may require an
exponentially large number of measurements, whereas a small amount of
measurements is necessary for estimation of the probability outcomes and swap
test.

##  4 Quantum Graph Learning

Recently many quantum machine learning algorithms have been proposed that
either promise quantum speed-ups over their classical counterparts Liu et al.
(2021); Zlokapa et al. (2021), or have the potential of finding atypical but
useful patterns that classical systems are not considered to be able to
generate effectively Cong et al. (2019); Huang et al. (2021). With the
development of quantum devices and high-performance quantum simulation
frameworks, there is an increasing interest in building novel quantum
algorithms to help solve near-term applications for practical problems. A
variety of quantum analogues to the classical machine learning models have
been proposed. Advanced contributions have taken the first step. For instance,
Harrow et al. (2009) proposes an exponentially fast algorithm for efficiently
solving linear equations. Based on this, the quantum support vector machine
(QSVM) presented by Rebentrost et al. (2014) can handle binary classification
problems on a quantum computer with complexity logarithmic in the size of the
vectors and the number of training examples. The practical implementation of
QSVM for recognizing handwritten characters is completed by Li et al. (2015).
To realize more intricate tasks, the quantum convolutional neural network
(QCNN) Cong et al. (2019) generates excitement around the possibility of
efficiently analyzing quantum data via performing convolutional and pooling
operations in quantum systems.

Although quantum algorithms have the potential to tackle graph problems
efficiently, quantum computing for graph learning is still in its early
stages. The literature is relatively sparse and lacks formal rationale for the
model selections. In the following, we show some progress of leveraging
quantum physics to extract graph structural information, bringing up new
possibilities for quantum computing applications. The main characteristics and
differences of these methods are summarized in Tab. 1.

###  4.1 Quantum Kernel based Graph Learning

Similar to the classical graph kernel methods, quantum kernels (QK) on graphs
aim to decompose the graph into substructures and compare the similarity
between each pair of substructures specified in terms of their quantum
representations. The Quantum Jensen–Shannon Graph Kernel (QJSK) Bai et al.
(2015) infers the graph properties using the density matrix description
constructed by CT-QRWs. The authors develop an aligned version of the QJSK to
preserve the permutation invariance and more correspondence information
between pairs of nodes in the graph. Additionally, they generalize their ideas
by probing the graph structure using the DT-QRWs Bai et al. (2017). In Schuld
et al. (2020), the authors present the potential of encoding the graph
information in the quantum Hilbert space using the derivation of Gaussian
Boson Samplers Kernel (GBSK). The information of all possible subgraphs can be
obtained by sampling instead of counting the appearance of specific
substructures classically. A specific kernel encoding the feature of all
subgraphs (SFGK) Kishi et al. (2021) investigates how to utilize the power of
quantum superposition to encode every subgraph into a feature space. The major
disadvantage of their model is that the similarity between the superposition
states is hard to estimate, thereby limiting the model capacity. The
Hamiltonian encoding approach is further exploited in the Quantum Evolution
Kernel (QEK) Henry et al. (2021) to represent the topology of the input graph.
A particular graph kernel generated by performing the quantum evolution
followed by a carefully chosen observable is able to characterize graphs in a
real quantum computer.

###  4.2 Shallow Circuit Graph Learning

Most classic graph learning techniques are motivated by graph-free models such
as kernel methods and CNNs. New generalizations and definitions of important
operations have been developed to handle the complexity of graph data Wu et
al. (2020). As a result, some studies use quantum computing to efficiently
duplicate procedures resulting from classic graph learning. It seems to be
essential to build effective embedding approaches that encode the classical
data into their quantum representations while keeping as much of the original
information as possible Huang et al. (2021); Schuld (2021). Besides, the
embedding phase contributes the most nonlinear transformations Schuld and
Killoran (2019) and is the basis of the quantum speed-ups claimed by many
quantum machine learning algorithms Biamonte et al. (2017). Therefore, new
methods should be developed to handle embedding efficacy. For learning on
graphs, the permutation invariance of node orderings should be also carefully
considered when transforming original graphs into their quantum expressions.
The shallow circuit learning method is a kind of quantum algorithm based on
the current noisy intermediate-scale quantum (NISQ) devices, which encodes the
original data into their quantum representations and approximates the
objective function by adjusting the learnable gate circuit parameters Schuld
(2021). Generally the shallow circuit can be divided into two parts where the
embedding circuit is responsible for encoding the data into quantum Hilbert
space and the following parameterized processing circuit is used to extract
hidden features from the feature space.

Verdon et al. (2019) introduces a quantum graph neural network (QGNN) that
treats the interaction of qubits as the nodes connected by edges. The entire
graph thereby can be expressed by a quadratic Hamiltonian, which implies that
we can think about quantum circuits with graph-theoretic properties. Their
numerical results limited to small-scale experiments show several potential
applications such as spectral clustering and graph isomorphism classification.
While more recently, it has been successfully applied to graphs with node
features in Zheng et al. (2021); Ai et al. (2022). However, their methods
suffer the computational cost as a result of quantum tomography, resulting in
the massive resource overhead. Mernyei et al. (2021) constructs an equivalent
quantum graph circuit (EQGC) whose topology preserves permutation invariance
of the input graph. But the number of the qubits scales linearly with the
number of nodes, and the prediction accuracy closely depends on the fidelity
of the measurements. An alternative approach devised by Beer et al. (2021)
uses qubits as neurons to characterize the graph as quantum states. They
design a quantum neural network (QNN) trained on a well-designed loss
evaluated by the fidelity of quantum representations of connected nodes.

###  4.3 Hybrid Deep Graph Learning

While GNNs represent state-of-the-art classical machine learning for a range
of benchmark tasks on graphs, there is no clear proof of quantum advantages
for tasks on classical graph-related datasets in extant quantum neural
networks. Therefore, some experts pin their hopes on developing approaches
that combine the expressiveness of the classical learning methods with the
power of quantum modules to improve the performance of existing models. A
hierarchical neural network based on QRWs (QWNN) is developed by Dernbach et
al. (2018) with a series of coins. The different setting of coins allows the
quantum walks to behave differently in terms of extracting various properties
of graphs. A classical diffusion process is employed to intersperse the
information along with the composite form of position distribution generated
by different quantum walks. Another quantum information propagation approach
presented by Bai et al. (2021) captures the multi-scale node features by
employing the mixing matrix of CT-QRWs instead of directly using the adjacency
matrix. QRWs are employed to select the more relevant neighbors of the center
node to achieve a more efficient information diffusion process in the quantum
subgraph convolutional neural network (QSCNN) Zhang et al. (2019). Chen et al.
(2021) develops a composite model (QGCNN) to perform convolutional and pooling
operations on graphs in which the parameterized quantum circuit tailed by the
fully connected neural network is used to approximate the learning function. A
hybrid GNN (HQGNN) is applied for particle track reconstruction Tüysüz et al.
(2021), consisting of variational circuits to improve expressiveness.

##  5 Challenges and Outlook

Though quantum graph computing and quantum graph learning have proven their
potential in various learning tasks, challenges still exist due to the
restricted scale of current quantum computational devices, instability of
quantum states and complexity of yielding numerical results by measurement. We
outlook three directions for the future researches.

Encoding Reliability It is necessary to develop an effective approach to
encode the graph into quantum representation while preserving the structural
information and node’s and edge’s features. Besides, the success of (deep)
neural networks relies on the nonlinear activation functions to enhance the
expression ability, whereas the evolution of the quantum physics is linearly
unitary transformation Schuld and Petruccione (2018). Therefore, it is also
important to consider more nonlinear effects while embedding classical data.

Data-driven and Adaptivity The goal of developing classical learning methods
is to be independent of experts and easy to be migrated to other tasks, and
the same is true for quantum machine learning. However, most existing quantum
computing methods are theory-oriented and knowledge-driven. A recent study
Huang et al. (2021) demonstrates the potential of enhancing quantum algorithms
using the power of data. The further study of data-driven quantum graph
algorithms will be possible to provide a more valuable reference for solving
graph theoretical and graph learning problems.

Computational Efficiency The cost landscapes of training quantum algorithms
are generally non-convex, making it difficult to establish general guarantees
about the computational expense of the optimizations Cerezo et al. (2020). The
process of embedding structural information into quantum expression will
inevitably introduce additional ancilla qubits Zheng et al. (2021) and
entanglement between qubits Verdon et al. (2019), which further makes quantum
circuits more difficult to model. These problems may be avoided by ingenious
circuit design and efficient gradient calculation.

## References

  * Adedoyin et al. [2018] A. Adedoyin, J. Ambrosiano, P. Anisimov, A. Bärtschi, W. Casper, G. Chennupati, C. Coffrin, H. Djidjev, D. Gunter, S. Karra, et al.  Quantum algorithm implementations for beginners.  arXiv:1804.03719, 2018.
  * Ahmed et al. [2013] A. Ahmed, N. Shervashidze, S. Narayanamurthy, V. Josifovski, and A. J. Smola.  Distributed large-scale natural graph factorization.  In WWW, 2013.
  * Ai et al. [2022] X. Ai, Z. Zhang, L. Sun, J. Yan, and E. Hancock.  Decompositional quantum graph neural network.  arXiv:2201.05158, 2022.
  * Albash and Lidar [2018] T. Albash and D. A. Lidar.  Adiabatic quantum computation.  Reviews of Modern Physics, 2018.
  * Albash and Marshall [2021] T. Albash and J. Marshall.  Comparing relaxation mechanisms in quantum and classical transverse-field annealing.  Physical Review Applied, 2021.
  * Ambainis et al. [2019] A. Ambainis, K. Balodis, J. Iraids, M. Kokainis, K. Prūsis, and J. Vihrovs.  Quantum speedups for exponential-time dynamic programming algorithms.  In SODA, 2019.
  * Bai et al. [2015] L. Bai, L. Rossi, A. Torsello, and E. R. Hancock.  A quantum jensen–shannon graph kernel for unattributed graphs.  Pattern Recognition, 2015.
  * Bai et al. [2017] L. Bai, L. Rossi, L. Cui, Z. Zhang, P. Ren, X. Bai, and E. Hancock.  Quantum kernels for unattributed graphs using discrete-time quantum walks.  Pattern Recognition Letters, 2017.
  * Bai et al. [2021] L. Bai, Y. Jiao, L. Cui, L. Rossi, Y. Wang, P. Yu, and E. Hancock.  Learning graph convolutional networks based on quantum vertex information propagation.  IEEE TKDE, 2021.
  * Bass et al. [2018] G. Bass, C. Tomlin, V. Kumar, P. Rihaczek, and J. Dulny.  Heterogeneous quantum computing for satellite constellation optimization: solving the weighted k-clique problem.  Quantum Science and Technology, 2018.
  * Beer et al. [2021] K. Beer, M. Khosla, J. Köhler, and T. J. Osborne.  Quantum machine learning of graph-structured data.  arXiv:2103.10837, 2021.
  * Belkin and Niyogi [2001] M. Belkin and P. Niyogi.  Laplacian eigenmaps and spectral techniques for embedding and clustering.  In NeurIPS, 2001.
  * Biamonte et al. [2017] J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, and S. Lloyd.  Quantum machine learning.  Nature, 2017.
  * Brady et al. [2021] L. T. Brady, C. L. Baldwin, A. Bapat, Y. Kharkov, and A. V. Gorshkov.  Optimal protocols in quantum annealing and quantum approximate optimization algorithm problems.  Physical Review Letters, 2021.
  * Calude et al. [2017] C. S. Calude, M. J. Dinneen, and R. Hua.  Qubo formulations for the graph isomorphism problem and related problems.  Theoretical Computer Science, 2017.
  * Cerezo et al. [2020] M. Cerezo, A. Poremba, L. Cincio, and P. J. Coles.  Variational quantum fidelity estimation.  Quantum, 2020.
  * Černỳ [1993] V. Černỳ.  Quantum computers and intractable (np-complete) computing problems.  Physical Review A, 1993.
  * Chams et al. [1987] M. Chams, A. Hertz, and D. De Werra.  Some experiments with simulated annealing for coloring graphs.  EJOR, 1987.
  * Chang et al. [2018] W.-L. Chang, Q. Yu, Z. Li, J. Chen, X. Peng, and M. Feng.  Quantum speedup in solving the maximal-clique problem.  Physical Review A, 2018.
  * Chen et al. [2020] D. Chen, L. Jacob, and J. Mairal.  Convolutional kernel networks for graph-structured data.  In ICML, 2020.
  * Chen et al. [2021] S. Y.-C. Chen, T.-C. Wei, C. Zhang, H. Yu, and S. Yoo.  Hybrid quantum-classical graph convolutional network.  arXiv:2101.06189, 2021.
  * Childs and Eisenberg [2005] A. M. Childs and J. M. Eisenberg.  Quantum algorithms for subset finding.  Quantum Info. Comput., 2005.
  * Childs et al. [2002] A. M. Childs, E. Farhi, and S. Gutmann.  An example of the difference between quantum and classical random walks.  Quantum Information Processing, 2002.
  * Cong et al. [2019] I. Cong, S. Choi, and M. D. Lukin.  Quantum convolutional neural networks.  Nature Physics, 2019.
  * Dernbach et al. [2018] S. Dernbach, A. Mohseni-Kabir, S. Pal, and D. Towsley.  Quantum walk neural networks for graph-structured data.  In Complex Networks and Their Applications, 2018.
  * Dunjko and Briegel [2018] V. Dunjko and H. J. Briegel.  Machine learning & artificial intelligence in the quantum domain: a review of recent progress.  Reports on Progress in Physics, 2018.
  * Dürr et al. [2006] C. Dürr, M. Heiligman, P. HOyer, and M. Mhalla.  Quantum query complexity of some graph problems.  SIAM Journal on Computing, 2006.
  * Emms et al. [2009a] D. Emms, R. C. Wilson, and E. R. Hancock.  Graph matching using the interference of continuous-time quantum walks.  Pattern Recognition, 2009.
  * Emms et al. [2009b] D. Emms, R. C. Wilson, and E. R. Hancock.  Graph matching using the interference of discrete-time quantum walks.  IVC, 2009.
  * Emms et al. [2009c] D. M. Emms, R. C. Wilson, and E. R. Hancock.  Graph embedding using a quasi-quantum analogue of the hitting times of continuous time quantum walks.  Quantum Information & Computation, 2009.
  * Farhi and Gutmann [1998] E. Farhi and S. Gutmann.  Quantum computation and decision trees.  Physical Review A, 1998.
  * Gilmer et al. [2017] J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl.  Neural message passing for quantum chemistry.  In ICML, 2017.
  * Goyal and Ferrara [2018] P. Goyal and E. Ferrara.  Graph embedding techniques, applications, and performance: A survey.  Knowledge-Based Systems, 2018.
  * Greenwood [2001] G. W. Greenwood.  Finding solutions to np problems: Philosophical differences between quantum and evolutionary search algorithms.  In CEC. IEEE, 2001.
  * Grover and Leskovec [2016] A. Grover and J. Leskovec.  node2vec: Scalable feature learning for networks.  In KDD, 2016.
  * Grover [1996] L. K. Grover.  A fast quantum mechanical algorithm for database search.  In STOC, 1996.
  * Harrow et al. [2009] A. W. Harrow, A. Hassidim, and S. Lloyd.  Quantum algorithm for linear systems of equations.  Physical review letters, 2009.
  * Haussler [1999] D. Haussler.  Convolution kernels on discrete structures.  Technical report, Department of Computer Science, University of California, 1999.
  * Hegade et al. [2021] N. N. Hegade, K. Paul, Y. Ding, M. Sanz, F. Albarrán-Arriagada, E. Solano, and X. Chen.  Shortcuts to adiabaticity in digitized adiabatic quantum computing.  Physical Review Applied, 2021.
  * Henry et al. [2021] L.-P. Henry, S. Thabet, C. Dalyac, and L. Henriet.  Quantum evolution kernel: Machine learning on graphs with programmable arrays of qubits.  Physical Review A, 2021.
  * Hillery et al. [2010] M. Hillery, D. Reitzner, and V. Bužek.  Searching via walking: How to find a marked clique of a complete graph using quantum walks.  Physical Review A, 2010.
  * Huang et al. [2021] H.-Y. Huang, M. Broughton, M. Mohseni, R. Babbush, S. Boixo, H. Neven, and J. R. McClean.  Power of data in quantum machine learning.  Nat. Commun., 2021.
  * Kempe [2003] J. Kempe.  Quantum random walks: an introductory overview.  Contemporary Physics, 2003.
  * Kempe [2005] J. Kempe.  Discrete quantum walks hit exponentially faster.  Probab. Theory Relat. Fields, 2005.
  * Kipf and Welling [2017] T. N. Kipf and M. Welling.  Semi-supervised classification with graph convolutional networks.  In ICLR, 2017.
  * Kishi et al. [2021] K. Kishi, T. Satoh, R. Raymond, N. Yamamoto, and Y. Sakakibara.  Graph kernels encoding features of all subgraphs by quantum superposition.  arXiv:2103.16093, 2021.
  * Kitaev [1996] A. Y. Kitaev.  Quantum measurements and the abelian stabilizer problem.  Electron. Colloquium Comput. Complex., 1996.
  * Li et al. [2015] Z. Li, X. Liu, N. Xu, and J. Du.  Experimental realization of a quantum support vector machine.  Physical review letters, 2015.
  * Li et al. [2016] Y. Li, D. Tarlow, M. Brockschmidt, and R. Zemel.  Gated graph sequence neural networks.  In ICLR, 2016.
  * Liu et al. [2021] Y. Liu, S. Arunachalam, and K. Temme.  A rigorous and robust quantum speed-up in supervised machine learning.  Nature Physics, 2021.
  * Lucas [2014] A. Lucas.  Ising formulations of many np problems.  Frontiers in physics, 2014.
  * Luo et al. [2011] D. Luo, C. H. Ding, F. Nie, and H. Huang.  Cauchy graph embedding.  In ICML, 2011.
  * Mernyei et al. [2021] P. Mernyei, K. Meichanetzidis, and İ. İ. Ceylan.  Equivariant quantum graph circuits.  arXiv:2112.05261, 2021.
  * Montanaro [2016] A. Montanaro.  Quantum algorithms: an overview.  npj Quantum Information, 2016.
  * Moylett et al. [2017] D. J. Moylett, N. Linden, and A. Montanaro.  Quantum speedup of the traveling-salesman problem for bounded-degree graphs.  Physical Review A, 2017.
  * Nath et al. [2021] R. K. Nath, H. Thapliyal, and T. S. Humble.  A review of machine learning classification using quantum annealing for real-world applications.  SN Computer Science, 2021.
  * Pelofske et al. [2019] E. Pelofske, G. Hahn, and H. Djidjev.  Solving large maximum clique problems on a quantum annealer.  In QTOP. Springer, 2019.
  * Perozzi et al. [2014] B. Perozzi, R. Al-Rfou, and S. Skiena.  Deepwalk: Online learning of social representations.  In KDD, 2014.
  * Preskill [2018] J. Preskill.  Quantum computing in the nisq era and beyond.  Quantum, 2018.
  * Qiu et al. [2018] J. Qiu, Y. Dong, H. Ma, J. Li, K. Wang, and J. Tang.  Network embedding as matrix factorization: Unifying deepwalk, line, pte, and node2vec.  In WSDM, 2018.
  * Rebentrost et al. [2014] P. Rebentrost, M. Mohseni, and S. Lloyd.  Quantum support vector machine for big data classification.  Physical review letters, 2014.
  * Ren et al. [2011] P. Ren, T. Aleksić, D. Emms, R. C. Wilson, and E. R. Hancock.  Quantum walks, ihara zeta functions and cospectrality in regular graphs.  Quantum Information Processing, 2011.
  * Scarselli et al. [2008] F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini.  The graph neural network model.  IEEE Trans. Neural Netw., 2008.
  * Schuld and Killoran [2019] M. Schuld and N. Killoran.  Quantum machine learning in feature hilbert spaces.  Physical review letters, 2019.
  * Schuld and Petruccione [2018] M. Schuld and F. Petruccione.  Supervised learning with quantum computers.  Springer, 2018.
  * Schuld et al. [2020] M. Schuld, K. Brádler, R. Israel, D. Su, and B. Gupt.  Measuring the similarity of graphs with a gaussian boson sampler.  Physical Review A, 2020.
  * Schuld [2021] M. Schuld.  Supervised quantum machine learning models are kernel methods.  arXiv:2101.11020, 2021.
  * Shor [1994] P. W. Shor.  Algorithms for quantum computation: discrete logarithms and factoring.  In FOCS. Ieee, 1994.
  * Shuman et al. [2013] D. I. Shuman, S. K. Narang, P. Frossard, A. Ortega, and P. Vandergheynst.  The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains.  IEEE Signal Process. Mag., 2013.
  * Silva et al. [2020] C. Silva, A. Aguiar, P. M. Lima, and I. Dutra.  Mapping graph coloring to quantum annealing.  Quantum Machine Intelligence, 2020.
  * Srinivasan et al. [2018] K. Srinivasan, S. Satyajit, B. K. Behera, and P. K. Panigrahi.  Efficient quantum algorithm for solving travelling salesman problem: An ibm quantum experience.  arXiv:1805.10928, 2018.
  * Tian et al. [2019] Y. Tian, L. Zhao, X. Peng, and D. Metaxas.  Rethinking kernel methods for node representation learning on graphs.  NeurIPS, 2019.
  * Tüysüz et al. [2021] C. Tüysüz, C. Rieger, K. Novotny, B. Demirköz, D. Dobos, K. Potamianos, S. Vallecorsa, J.-R. Vlimant, and R. Forster.  Hybrid quantum classical graph neural networks for particle track reconstruction.  Quantum Machine Intelligence, 2021.
  * Ushijima-Mwesigwa et al. [2017] H. Ushijima-Mwesigwa, C. F. Negre, and S. M. Mniszewski.  Graph partitioning using quantum annealing on the d-wave system.  In PMES, 2017.
  * Venegas-Andraca [2012] S. E. Venegas-Andraca.  Quantum walks: a comprehensive review.  Quantum Information Processing, 2012.
  * Verdon et al. [2019] G. Verdon, T. McCourt, E. Luzhnica, V. Singh, S. Leichenauer, and J. Hidary.  Quantum graph neural networks.  arXiv:1909.12264, 2019.
  * Wu et al. [2020] Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and S. Y. Philip.  A comprehensive survey on graph neural networks.  IEEE TNNLS, 2020.
  * Zhang et al. [2019] Z. Zhang, D. Chen, J. Wang, L. Bai, and E. R. Hancock.  Quantum-based subgraph convolutional neural networks.  Pattern Recognition, 2019.
  * Zheng et al. [2021] J. Zheng, Q. Gao, and Y. Lü.  Quantum graph convolutional neural networks.  In Chinese Control Conference. IEEE, 2021.
  * Zlokapa et al. [2021] A. Zlokapa, H. Neven, and S. Lloyd.  A quantum algorithm for training wide and deep classical neural networks.  arXiv:2107.09200, 2021.


# ShadowRefiner: Towards Mask-free Shadow Removal via Fast Fourier Transformer

Wei Dong1 Han Zhou1∗ Yuqiong Tian1 Jingke Sun1 Xiaohong Liu2 Guangtao Zhai2
Jun Chen1∗
1McMaster University 2Shanghai Jiao Tong University
<EMAIL_ADDRESS>{zhouh115, tiany86<EMAIL_ADDRESS>
{xiaohongliu<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Shadow-affected images often exhibit pronounced spatial discrepancies in color
and illumination, consequently degrading various vision applications including
object detection and segmentation systems. To effectively eliminate shadows in
real-world images while preserving intricate details and producing visually
compelling outcomes, we introduce a mask-free Shadow Removal and Refinement
network (ShadowRefiner) via Fast Fourier Transformer. Specifically, the Shadow
Removal module in our method aims to establish effective mappings between
shadow-affected and shadow-free images via spatial and frequency
representation learning. To mitigate the pixel misalignment and further
improve the image quality, we propose a novel Fast-Fourier Attention based
Transformer (FFAT) architecture, where an innovative attention mechanism is
designed for meticulous refinement. Our method wins the championship in the
Perceptual Track and achieves the second best performance in the Fidelity
Track of NTIRE 2024 Image Shadow Removal Challenge. Besides, comprehensive
experiment result also demonstrate the compelling effectiveness of our
proposed method. The code is publicly available:
https://github.com/movingforward100/Shadow_R.

Figure 1: Our test results on NTIRE 2024 Image Shadow Removal Challenge [38].
Our proposed method is the champion in the Perceptual Track and achieves the
second best performance in the Fidelity Track.

††∗ Han Zhou and Jun Chen are corresponding authors

##  1 Introduction

Shadow-affected images typically emerge under scenarios where the light source
is either partially or completely blocked, leading to spatial variations in
color and illumination distortions. The objective of shadow removal is to
enhance the visibility within shadow regions and achieve illumination
consistency across both shadow and non-shadow areas, whilst preserving the
integrity of naturalistic details. Such enhancement is pivotal for improving
the performance of a plethora of downstream applications such as object
detection, tracking, and segmentation systems [15, 7, 44, 34].

Numerous traditional methodologies proposed for image shadow removal are
predominantly designed around physics-based illumination models [17, 12].
Despite their theoretical underpinnings, these approaches generally exhibit
limited effectiveness of removing shadows from real-world, shadow-affected
images. This limitation largely stems from the difficulty in establishing an
accurate physical correlation between shadow areas and their unblemished
counterparts, rendering these traditional techniques less effective in
practical scenarios.

Recently, learning-based approaches have emerged as a formidable mainstream
within the domain of shadow removal, capitalizing on the substantial modeling
capability inherent in deep learning frameworks [23, 24, 41, 46]. These
methodologies can be bifurcated into mask-based [31] and mask-free shadow
removal strategies, contingent upon their dependence on shadow masks for
guidance. Compared to the latter, mask-based shadow removal strategies not
only employ pairs of shadow-affected and shadow-free images but also integrate
the location information of shadow regions, either provided by benchmark
datasets or generated through pre-trained mask prediction models, as learning
guidance. The introduction of precise shadow location enables these models to
concentrate on unraveling the complex mappings between shadow regions and
their clean counterparts, thereby achieving exceptional performance on shadow
removal.

Nonetheless, the dependency on mask information unveils critical challenges to
mask-based methods. Firstly, the acquisition of precise shadow masks is
notably challenging [27]. Accurate shadow masks provided in public datasets
are typically obtained under simply scenarios, such as a single person
standing in a wide-open square. In contrast, for complex scenes, as
exemplified by the WSRD and WSRD+ datasets [36], annotating images with
appropriate masks or employing pre-trained models to predict accurate masks
proves to be impractical. Secondly, the absence of precise shadow masks
markedly undermines the performance of mask-based models, substantially
hindering their applicability to complex real-world data.

Latest advancements in mask-free shadow removal methodologies often leverage
generative strategies [48] to learn the mappings between shadow-affected and
shadow-free images. However, the adoption of frequency domain analysis remains
largely under-explored within the sphere of shadow removal studies. Notably,
several innovative works that integrate spatial and frequency representations
has shown promising results in the broader field of image restoration, such as
dehazing and low-light image enhancement task [51, 19], suggesting a potential
direction for future exploration for shadow removal.

In this paper, we introduce a novel mask-free model that integrates spatial
and frequency domain representations for image shadow removal, which achieves
compelling performance on NTIRE 2024 Image Shadow Removal Challenge [38], as
illustrated in Fig. 1. Specifically, we propose a Shadow Removal and
Refinement architecture, termed ShadowRefiner, with two specific modules:
Shadow Removal module and Refinement module. In the Shadow Removal module, we
design a shadow removal U-Net [32] branch with the backbone of ConvNext [28]
blocks. Besides, a frequency branch similar to [51] equipped with high-
frequency, low-frequency representations, and large receptive field, is also
leveraged in our Shadow Removal module. Preliminary experiment results,
however, indicate obvious pixel misalignment between the output of Shadow
Removal module and the ground truth, manifesting as pronounced detail
deterioration and compromised color consistency. To this end, we introduce a
Fast-Fourier Attention based Transformer (FFAT) as the Refinement module,
distinguished by its innovative attention mechanism, which significantly
enhances the model’s capacity to remove shadows while producing results that
are simultaneously high in fidelity and visually appealing.

Our contributions are three-folds:

$\diamond$ We introduce an innovative mask-free shadow removal approach that
initially clear shadow via spatial and frequency representation learning and
further refined by our proposed frequency attention based transformer
architecture .

$\diamond$ To mitigate the pixel misalignment, we introduce a Fast Fourier
Transformer network endowed with a novel frequency attention mechanism,
achieving superior performance on recovering texture details and maintaining
color consistency.

$\diamond$ Extensive experiments across multiple shadow removal benchmarks, as
well as the highly competitive outcomes achieved in the NTIRE 2024 Image
Shadow Removal Challenge (ranking first and second in the Perceptual Track and
Fidelity Track, respectively), underscore the remarkable performance of our
proposed ShadowRefiner model.

\begin{overpic}[width=491.89041pt]{section/figure/shadow--final.pdf}
\end{overpic} Figure 2: The overall architecture of our model. In the Shadow
Removal module, besides the DWT-FFC branch proposed in [51, 1], we design a
ConvNext-based U-Net architecture with $7\times 7$ depth-wise convolution in
each resolution. In the Refinement module, we design a new attention mechanism
(Fast-Foruier Attention, FFA) different from common attention operations in
transformers to further enhance texture details.

##  2 Related Work

Mask-based Image Shadow Removal. Mask-based methods can be categorized into
two main types: feature-based and deep learning-based. Feature-based methods
rely on techniques such as color constancy [50], texture analysis and edge
detection [2, 43]. Gryka  _et al_. [14] first introduce a learning-based
method using a supervised regression algorithm to automatically remove umbra
and penumbra shadows. Wang  _et al_. [40] propose ST-CGAN, an end-to-end
framework that integrates shadow detection and removal using two stacked
Conditional Generative Adversarial Networks (CGANs). Bao  _et al_. [3] propose
S2Net that emphasizes semantic guidance and refinement for image integrity.
This method uses shadow masks to guide shadow removal, with semantic-guided
blocks transferring data from non-shadow to shadow areas, effectively
eliminating shadows while preserving clean regions. He  _et al_. [18] design
Mask-ShadowNet, which ensures global illumination consistency through Masked
Adaptive Instance Normalization (MAdaIN) and adaptively refines features using
aligner modules. Additionally, Fu  _et al_. [11] introduce FusionNet, which
generates fusion weight maps to eliminate shadow traces further using a
boundary-aware RefineNet. However, these methods heavily rely on the accuracy
of the input shadow masks. The complexity and variability of real-world
scenarios could pose challenges in generating precise shadow masks,
potentially affecting the performance of these methods in practical
applications.

Mask-free Image Shadow Removal. Fan  _et al_. [9] introduce an end-to-end deep
convolutional neural network consisting of an encoder-decoder network for
predicting the shadow scale factor and a small refinement network for
enhancing edge details. Chen  _et al_. [5] design a CANet which utilizes a
two-stage process for shadow removal, employing a Contextual Patch Matching
(CPM) module to identify matching pairs between shadow and non-shadow patches
and a Contextual Feature Transfer (CFT) mechanism to transfer contextual
information, effectively eliminating shadow influence. Vasluianu  _et al_.
[37] introduce Ambient Lighting Normalization (ALN) to improve image
restoration under complex lighting and propose IFBlend that enhances images by
maximizing Image-Frequency joint entropy without relying on shadow
localization. Liu  _et al_. [25] propose a shadow-aware decomposition network
to separate illumination and reflectance layers, followed by a bilateral
correction network for lighting adjustment and texture restoration.

Transformer-based Image Restoration. Transformer based networks, usually adopt
self-attention mechanisms to understand the relationships between different
components and demonstrate high superiority in handling long dependencies,
have shown state-of-the-art performance on image restoration. SwinIR [22], a
famous backbone for image restoration, is designed based on several residual
Swin Transformer [26] blocks. With the backbone of Vision Transformer [39],
DehazeFormer [35] is proposed for dehazing task. Recently, a lightweight
transformer architecture [4] is proposed for low-light image enhancement based
on Retinex theory.

##  3 Methods

Methods |  Mask-free | ISTD [40] | ISTD+ [21] | WSRD+ [36]
---|---|---|---|---
PSNR$\uparrow$ | SSIM$\uparrow$ | LPIPS$\downarrow$ | PSNR$\uparrow$ | SSIM$\uparrow$ | LPIPS$\downarrow$ | PSNR$\uparrow$ | SSIM$\uparrow$ | LPIPS$\downarrow$
DHAN [6] | No | 24.86 | 0.919 | 0.0535 | 27.88 | 0.917 | 0.0529 | 22.39 | 0.796 | 0.1049
BMNet [52] | No | 29.02 | 0.923 | 0.0529 | 31.85 | 0.932 | 0.0432 | 24.75 | 0.816 | 0.0948
FusionNet [11] | No | 25.84 | 0.712 | 0.3196 | 27.61 | 0.725 | 0.3123 | 21.66 | 0.752 | 0.1227
SADC [45] | No | 29.22 | 0.928 | 0.0403 | — | — | — | — | — | —
ShadowFormer [16] | No | 30.47 | 0.928 | 0.0418 | 32.78 | 0.934 | 0.0385 | 25.44 | 0.820 | 0.0898
DCShadowNet [20] | Yes | 24.02 | 0.677 | 0.4423 | 25.50 | 0.694 | 0.4237 | 21.62 | 0.593 | 0.4744
Refusion [29] | Yes | 25.13 | 0.871 | 0.0571 | 26.28. | 0.887 | 0.0437 | 22.32 | 0.738 | 0.0937
ShadowRefiner (Ours) | Yes | 28.75 | 0.916 | 0.0521 | 31.03 | 0.928 | 0.0426 | 26.04 | 0.827 | 0.0854

Table 1: Quantitative comparisons with SOTA methods. Our ShadowRefiner
significantly outperforms other mask-free methods across three benchmarks.
Compared to mask-based methods, our ShadowRefiner achieves comparable or even
better performance (WSRD+ dataset). [Key: Best performance among mask-free
models, Best performance among mask-based methods]

###  3.1 ConvNext based U-Net for Shadow Removal

In order to achieve satisfactory shadow removal performance, powerful deep-
learning networks are pivotal to extracting important features from shadow-
affected images and modeling the mapping from shadow-affected and clean
images. In this work, we introduce a ConvNext-based U-Net architecture, where
multi-scale ConvNext blocks function as strong encoders for robust latent
feature learning.

As shown in Fig. 2, the ConvNext-based U-Net serves as the primary component
in the Shadow Removal module, and the DWT-FFC branch [51, 8] is incorporated
as an auxiliary branch. The contributions of each branch is provided in Sec.
4.4.

Specifically, our ConvNext-based U-Net encompasses three downsampling layers
and each downsampling operation is followed by several ConvNext blocks to
feature extraction. Given a latent feature $\mathbf{F}_{in}$, the ConvNext
block first adopts a $7\times 7$ depthwise convolution, which functions
similar to the self-attention mechanism in Transformers. Then the Layer
Normalization (LN) is applied before two $1\times 1$ convolutions, which are
equivalent to MLP block in Transformer. Besides, only one GELU function is
leveraged between two $1\times 1$ convolutions inspired by the fact that
Transformer MLP block incorporates only one activation function.

For the decoding process, the latent feature is aggregated using one attention
block [30] and several upsampling operations are utilized to recover the
latent feature to their original resolution. In each upsampling layer, there
are one pixel-shuffle operation and one attention block. Besides, encoder
features are transferred to the decoding process via skip-connection.

In Stage I, we only optimizing the Shadow Removal module and the training
objective is shown as below:

${L}_{loss}={L}_{1}+{\alpha}{L}_{SSIM}+{\beta}{L}_{Percep}+{\gamma}{L}_{adv}$
(1)

where ${L}_{1}$, ${L}_{SSIM}$ and ${L}_{Percep}$ represent the $L1$ loss, MS-
SSIM loss [51], and perceptual loss [33], respectively. In addition, we
leverage the discriminator proposed in [13] (not provided in Fig. 2) to
calculate the adversarial loss (${L}_{adv}$). $\alpha$, $\beta$, and $\gamma$
are set to $0.2$, $0.01$, and $0.0005$ for the optimization.

Figure 3: Visual comparisons on the ISTD dataset [40]. Compared to other
methods, our ShadowRefiner successfully remove shadows without incorporating
artifacts.

###  3.2 Fast-Fourier Attention Transformer based Refinement

Early experimental results suggest that our proposed ConvNext-based U-Net can
effectively remove shadows, but distinct shadow contours remain, as
illustrated in Fig. 6. In order to further refine image details and maintain
color consistency, we introduce an efficient transformer architecture with a
novel frequency attention mechanism, as shown in Fig. 2. Similar to [47], our
Refinement module adopts a encoder-decoder architecture, and our proposed FFAT
blocks are utilized at each resolution level in both encoding and decoding
process.

Given a latent feature $\mathbf{F}$, FFAT block first utilize $1\times 1$
point-wise convolution and $3\times 3$ depth-wise convolution to generate
three features: $\mathbf{Q,K,V}$. Instead of directly leveraging these
features for attention calculation, we apply Fast Fourier Transform to
$\mathbf{Q,K}$ to calculate their frequency correlation $\mathbf{A}_{F}$ based
on their frequency domain representations ($\mathcal{F}(\mathbf{Q})$,
$\mathcal{F}(\mathbf{K})$) by:

$\mathbf{A}_{F}=\mathcal{F}(\mathbf{Q})\mathcal{F}(\mathbf{K})^{\prime},$ (2)

where $\mathcal{F}(\cdot)$ represents the FFT process and $(\cdot)^{\prime}$
denotes the transpose operation. Then, the spatial correlation between
$\mathbf{Q}$ and $\mathbf{K}$ can be obtained by the inverse FFT operation
($\mathcal{F}^{-1}(\cdot)$) and a layer normalization ($\mathcal{LN}$).
Finally, the aggregated feature $\mathbf{F}_{A}$ and the final output of our
FFAT block $\mathbf{F}_{out}$ can be estimated as:

$\begin{split}&\mathbf{F}_{A}=\mathcal{LN}(\mathcal{F}^{-1}(\mathbf{A}_{F}))\mathbf{V}\\\
&\mathbf{F}_{out}=\mathrm{Conv}_{1\times
1}(\mathbf{F}_{A})+\mathbf{F}.\end{split}$ (3)

Compared to the global attention mechanism in Transformer and other attention
strategy [10], our FFAT blocks can not only effectively capture long-
dependencies, but also demonstrate stronger representation learning with high
efficiency. This advantage stems from the frequency domain feature learning
and frequency attention calculation process. To train our FFAT-based
Refinement module, we first fix the Shadow Removal module and remove the
adversarial loss in Eq. 1 for optimization.

Figure 4: Visual comparisons on the ISTD+ dataset[21]. Obviously, our
ShadowRefiner excels in maintaining color consistency and recovering structure
details

Team | PSNR$\uparrow$ | SSIM$\uparrow$ | LPIPS$\downarrow$ | MOS$\uparrow$ | Fianl Rank$\downarrow$
---|---|---|---|---|---
Shadow_R (Ours) | 24.578 | 0.832 | 0.098 | 7.750 | 1
LVGroup_HFUT | 24.232 | 0.821 | 0.082 | 7.519 | 2
USTC_ShadowTitan | 24.042 | 0.827 | 0.104 | 7.444 | 3
ShadowTech Innovators | 24.810 | 0.832 | 0.111 | 7.438 | 4
GGBond | 23.050 | 0.809 | 0.089 | 7.400 | 5
PSU Team | 22.219 | 0.731 | 0.132 | 7.400 | 6
LUMOS | 24.783 | 0.832 | 0.110 | 7.163 | 7
IIM_TTI | 22.955 | 0.806 | 0.093 | 7.160 | 8
AiRiA_Vision | 21.902 | 0.689 | 0.238 | 6.825 | 9
HKUST-VIP_Lab_01 | 22.284 | 0.788 | 0.135226084 | 6.619 | 10

Table 2: Final ranking (top 10 teams) of Perceptual Track in NTIRE 2024 Shadow
Removal Challenge. Our solution achieves the best performance among all 19
submitted solutions. [Key: Best, Second Best, $\uparrow(\downarrow)$: The
larger (smaller) represents the better performance].

##  4 Experiments

###  4.1 Datasets and Implementation Details

Datasets. We evaluate our proposed method on WSRD+ [36], ISTD [40], and ISTD+
[21] datasets. WSRD+ dataset, as the enhanced version of the WSRD dataset with
improved pixel-alignment, is used as the benchmark dataset for NTIRE 2024
Image Shadow Removal Challenge. This dataset consists of 1200 high-resolution
image pairs. The training set, validation set, and test set are split in
proportions of 10:1:1, and we train our model on the training set and evaluate
the performance on the validation set. ISTD dataset contains 1870 image
triplets obtained from 135 distinct scenarios, of which 1330 are assigned for
training and the remaining 540 are for testing. ISTD+ dataset is a color-
adjusted version of ISTD and it has the same number and structure as the ISTD
dataset.

Implementation Details. One RTX 2080Ti GPU is used to execute the two-stage
training of our method. For data augmentation, we implement random cropping of
patches with dimensions of $384\times 384$, combined with random rotations of
$90$, $180$, or $270$ degrees, as well as vertical and horizontal flipping.
The Adam optimizer with the default hyper-parameters, where $\beta_{1}$ and
$\beta_{2}$ are set to $0.9$ and $0.999$ respectively, is utilized for
optimization. In Stage I, only Shadow Removal module is optimized and the
learning rate is initially set to $1\times 10^{-4}$ and is gradually reduced
to $6.25\times 10^{-6}$. In Stage II, we adopt a constant learning of $1\times
10^{-5}$ to simultaneously update the Shadow Removal module and Refinement
module.

Evaluation Metrics. To comprehensively evaluate the performance of various
shadow removal methods, three metrics are adopted for quantitative comparison:
The Peak Signal to Noise Ratio (PSNR), the Structural Similarity Index (SSIM)
[42], and Learned Perceptual Image Patch Similarity (LPIPS) [49] to assess the
pixel-level accuracy and perceptual quality.

###  4.2 Comparison with State-of-the-Art Methods

We compare our proposed method with several State-of-the-art (SOTA)
algorithms. Specifically, several mask-free methods including Refusion [29],
DCShadowNet [20] and recent proposed mask-based approaches including
ShadowFormer [16], SADC [45] are adopted for comparison.

Quantitative Results. As documented in Tab. 1, our ShadowRefiner demonstrates
superior performances compared to other mask-free methods across three
datasets. On the ISTD dataset [40], there is a marked improvement of 3.62 dB
in PSNR, a 0.045 increase in SSIM, and a 0.005 decline in LPIPS. On the ISTD+
dataset [21], we observe a 4.75 dB increase in PSNR and a 0.041 increase in
SSIM. Besides, our ShadowRefiner yields a 3.72 dB increase in PSNR, a 0.089
increase in SSIM, and a 0.008 decline in LPIPS on the WSRD+ dataset [38].
Furthermore, compared to mask-based methods, which require shadow mask
information and naturally outperform mask-based models, our mask-free
ShadowRefiner is capable to generate comparable results on ISTD and ISTD+
datasets. Moreover, on WSRD+ dataset where precise mask image is unavailable,
though a mask prediction method proposed in [6] is utilized to assist these
mask-based models, our ShadowRefiner achieves superior performance than the
best mask-based approach (ShadowFormer [16]), demonstrating that our
ShadowRefiner can work effectively in complex scenarios.

Qualitative Comparisons. Visual comparisons on ISTD dataset, ISTD+ dataset and
WSRD+ dataset are reported in Fig. 3, 4, and 5, respectively. Obviously, the
results of our method closely match GT images in both color and detail
preservation. For instance, in Fig. 3 row 3, our ShadowRefiner removes the
shadow without introducing artifacts or discoloration, issues commonly seen
with other methods. In Fig. 4 row 2, our method skillfully adjusts the shadow
areas on the pavement, effectively lightening the shadows to blend with the
sunlit parts without distorting the underlying patterns or hues. Moreover, for
images featuring toys and colorful objects shown in Fig. 5, our ShadowRefiner
restores the vivid colors and intricate patterns that are obscured by shadows
in the input images.

Figure 5: Our results on the validation set of WSRD+ dataset [36]. Our method
performs well on color and detail recovery.

###  4.3 Performance on NTIRE 2024 Shadow Removal Challenge (Fidelity and
Perceptual Track)

According to the challenge report [38], our model is the first place of
Perceptual Track and the second place of Fidelity Track with the highest SSIM
(0.832) and Mean Opinion Scor (MOS, 7.750) and competitive PSNR (24.58),
demonstrating advanced performance of our method on shadow removal task. We
also report the result of our method for the official validation and test data
used in NTIRE 2024 Shadow Removal Challenge as Fig. 1 and Fig. 5. We can see
that our ShadowRefiner achieves notably satisfying shadow removal effect in
pictures of different scenarios. For example, the shadow in the first image in
Fig. 1 is completely eliminated, retaining the integrity of the scattered toy
blocks in their original layout. Additionally, the color consistency between
toys initially positioned in shadowed areas and those under direct
illumination attests to the high fidelity in color reproduction. The
restoration of the final image depicting a dog conveys a sense of uniform,
soft lighting across the entire subject, further exemplifying ShadowRefiner’s
capability to enhance illumination homogeneity.

Configurations | PSNR$\uparrow$ | SSIM$\uparrow$ | LPIPS$\downarrow$
---|---|---|---
ShadowRefiner (Ours) | 26.04 | 0.827 | 0.0854
w/o Refinement module | 25.54 | 0.816 | 0.0886
w/ Restormer module [47] | 25.68 | 0.818 | 0.0878
only ConvNext-based U-Net | 25.29 | 0.810 | 0.0914
only DWT-FFC branch | 23.36 | 0.791 | 0.1016

Table 3: The ablation results on WRSD+ dataset. Each component in our
ShadowRefiner help achieve competitive performance on shadow removal task, and
our proposed Refinement module performs better than Restormer. Figure 6:
Visual ablation comparisons on the WSRD+ dataset.

###  4.4 Ablation Study

In this section, we conduct several ablation experiments on WSRD+ dataset
[36].

Importance of FFAT based Refinement module. To study the contribution of the
Refinement module and our proposed FFAT blocks, we first remove the Refinement
module to figure out its contribution for the outstanding performance of our
method provided in Tab. 1. The quantitative result is reported in Tab. 3,
which demonstrates removing Refinement module leads to obviously degraded
performance. Then, we replace our Refinement module with Restormer module [47]
and we notice a marked decrease in PSNR (0.36 dB $\downarrow$) and SSIM (0.009
$\downarrow$) and a discernible increase of LPIPS (0.0024 $\uparrow$). Visual
comparisons provided in Fig. 6 also demonstrate our Refinement module can help
generate more visually appealing results compared to the Restormer module.
This ablation experiment underscore the importance of our proposed Refinement
module for satisfactory shadow removal performance.

Contributions of ConvNext-based U-Net. Based on the configuration for Tab. 3
row 2, we implement several further adaptations to illustrate the
effectiveness of ConvNext-based U-Net and the DWT-FFC branch leveraged in the
Shadow Removal module. By separately comparing row 4 and row 5 to row 2 in
Tab. 3, we can conclude that adopting a two-branch architecture in the Shadow
Removal module help achieve more pleasant performance than single branch.
Moreover, compared to the DWT-FFC branch, the enhanced performance of the
ConvNext-based U-Net architecture highlights its predominant role within the
Shadow Removal module.

##  5 Conclusion

In this paper, we propose ShadowRefiner, a novel mask-free model for shadow
removal task. Specifically, the Shadow Removal module with ConvNext-based
U-Net is firstly introduced to extract spatial and frequency representations
and effectively learning the mapping between shadow-affected and clean images.
Then, we design a novel transformer module based on Fast Fourier Attention
Transformer to enhance color and structure consistency. Extensive experiments
demonstrate ShadowRefiner significantly outperforms the current mask-free
methods and its capacity is comparable to mask-based shadow removal
approaches. Furthermore, our method wins the championship in the Perceptual
Track and ranks second in the Fidelity Track of NTIRE 2024 Image Shadow
Removal Challenge.

## References

  * Ancuti et al. [2023] Codruta O Ancuti, Cosmin Ancuti, Florin-Alexandru Vasluianu, Radu Timofte, et al.  NTIRE 2023 hr nonhomogeneous dehazing challenge report.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops_ , 2023.
  * Arbel and Hel-Or [2011] Eli Arbel and Hagit Hel-Or.  Shadow removal using intensity surfaces and texture anchor points.  In _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 2011.
  * Bao et al. [2022] Qiqi Bao, Yunmeng Liu, Bowen Gang, Wenming Yang, and Qingmin Liao.  S2net: Shadow mask-based semantic-aware network for single-image shadow removal.  In _IEEE Transactions on Consumer Electronics_ , 2022.
  * Cai et al. [2023] Yuanhao Cai, Hao Bian, Jing Lin, Haoqian Wang, Radu Timofte, and Yulun Zhang.  Retinexformer: One-stage retinex-based transformer for low-light image enhancement.  In _Proceedings of the IEEE International Conference on Computer Vision (ICCV)_ , 2023.
  * Chen et al. [2021] Zipei Chen, Chengjiang Long, Ling Zhang, and Chunxia Xiao.  Canet: A context-aware network for shadow removal.  In _Proceedings of the IEEE International Conference on Computer Vision (ICCV)_ , 2021.
  * Cun et al. [2020] Xiaodong Cun, Chi-Man Pun, and Cheng Shi.  Towards ghost-free shadow removal via dual hierarchical aggregation network and shadow matting gan.  In _Proceedings of the AAAI Conference on Artificial Intelligence (AAAI)_ , 2020.
  * Dong et al. [2018] Wei Dong, Han Zhou, and Dong Xu.  A new sclera segmentation and vessels extraction method for sclera recognition.  In _2018 10th International Conference on Communication Software and Networks (ICCSN)_ , 2018.
  * Dong et al. [2024] Wei Dong, Han Zhou, Ruiyi Wang, Xiaohong Liu, Guangtao Zhai, and Jun Chen.  DehazeDCT: Towards effective non-homogeneous dehazing via deformable convolutional transformer.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops (CVPR Workshops)_ , 2024.
  * Fan et al. [2019] Hui Fan, Meng Han, and Jinjiang Li.  Image shadow removal using end-to-end deep convolutional neural networks.  In _Applied Sciences_ , 2019.
  * Fu et al. [2024] Kang Fu, Peng Yicong amd Zhang Zicheng, Qihang Xu, Xiaohong Liu, Jia Wang, and Guangtao Zhai.  Attentionlut: Attention fusion-based canonical polyadic lut for real-time image enhancement.  _arXiv preprint arXiv:2401.01569_ , 2024.
  * Fu et al. [2021] Lan Fu, Changqing Zhou, Qing Guo, Felix Juefei-Xu, Hongkai Yu, Wei Feng, Yang Liu, and Song Wang.  Auto-exposure fusion for single-image shadow removal.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2021.
  * Gong and Cosker [2016] Han Gong and Darren Cosker.  Interactive removal and ground truth for difficult shadow scenes.  In _JOSA_ , 2016.
  * Goodfellow et al. [2020] Ian J. Goodfellow, Pouget-Abadie Jean, Mehdi Mirza, Bing Xu, Warde-Farley David, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.  Generative adversarial networks.  In _Association for Computing Machinery_ , 2020.
  * Gryka et al. [2015] Maciej Gryka, Michael Terry, and Gabriel J Brostow.  Learning to remove soft shadows.  In _ACM Trans. Graph._ , 2015.
  * Guang et al. [2016] Guan Guang, Xingang Wang, Wenqi Wu, Han Zhou, and Yuanyuan Wu.  Real-time lane-vehicle detection and tracking system.  In _Chinese Control and Decision Conference (CCDC)_ , 2016.
  * Guo et al. [2023] Lanqing Guo, Siyu Huang, Ding Liu, Hao Cheng, and Bihan Wen.  Shadowformer: Global context helps image shadow removal.  In _Proceedings of the AAAI Conference on Artificial Intelligence (AAAI)_ , 2023.
  * Guo et al. [2012] Ruiqi Guo, Qiqyun Dai, and Derek Hoiem.  Paired regions for shadow detection and removal.  In _IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI)_ , 2012.
  * He et al. [2021] Shengfeng He, Bing Peng, Junyu Dong, and Yong Du.  Mask-shadownet: Toward shadow removal via masked adaptive instance normalization.  In _IEEE Signal Processing Letters_ , 2021.
  * Jiang et al. [2023] Hai Jiang, Ao Luo, Songchen Han, Haoqiang Fan, and Shuaicheng Liu.  Low-light image enhancement with wavelet-based diffusion models.  In _Siggraph Asia_ , 2023.
  * Jin et al. [2021] Yeying Jin, Aashish Sharma, and Robby T. Tan.  Dc-shadownet: Single-image hard and soft shadow removal using unsupervised domain-classifier guided network.  In _Proceedings of the IEEE International Conference on Computer Vision (ICCV)_ , 2021.
  * Le and Samaras [2019] Hieu Le and Dimitris Samaras.  Shadow removal via shadow image decomposition.  In _Proceedings of the IEEE International Conference on Computer Vision (ICCV)_ , 2019.
  * Liang et al. [2021] Jingyun Liang, Jiezhang Cao, Guolei Sun, Kai Zhang, Luc Van Gool, and Radu Timofte.  Swinir: Image restoration using swin transformer.  In _Proceedings of the IEEE International Conference on Computer Vision Workshops (ICCV Workshops)_ , 2021.
  * Liu et al. [2019] Xiaohong Liu, Yongrui Ma, Zhihao Shi, and Jun Chen.  Griddehazenet: Attention based multi-scale network for image dehazing.  In _Proceedings of the IEEE International Conference on Computer Vision (ICCV)_ , 2019.
  * Liu et al. [2022a] Xiaohong Liu, Zhihao Shi, Zijun Wu, Jun Chen, and Guangtao Zhai.  Griddehazenet+: An enhanced multi-scale network with intra-task knowledge transfer for single image dehazing.  _IEEE Transactions on Intelligent Transportation Systems_ , 2022a.
  * Liu et al. [2024] Yuhao Liu, Zhanghan Ke, Ke Xu, Fang Liu, Zhenwei Wang, and Rynson W. H. Lau.  Recasting regional lighting for shadow removal.  _arXiv preprint arXiv:2402.00341_ , 2024.
  * Liu et al. [2021a] Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo.  Swin transformer: Hierarchical vision transformer using shifted windows.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2021a.
  * Liu et al. [2021b] Zhihao Liu, Hui Yin, Xinyi Wu, Zhenyao Wu, Yang Mi, and Song Wang.  From shadow generation to shadow removal.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2021b.
  * Liu et al. [2022b] Zhuang Liu, Hanzi Mao, Chao-Yuan Wu, Christoph Feichtenhofer, Trevor Darrell, and Saining Xie.  A convnet for the 2020s.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2022b.
  * Luo et al. [2023] Ziwei Luo, Fredrik K. Gustafsson, Zheng Zhao, et al.  Refusion: Enabling large-size realistic image restoration with latent-space diffusion models.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops (CVPR Workshops)_ , 2023.
  * Qin et al. [2020] Xu Qin, Zhilin Wang, Yuanchao Bai, Xiaodong Xie, and Huizhu Jia.  Ffa-net: Feature fusion attention network for single image dehazing.  In _Proceedings of the AAAI Conference on Artificial Intelligence (AAAI)_ , 2020.
  * Qu et al. [2017] Liangqiong Qu, Jiandong Tian, Shengfeng He, Yandong Tang, and Rynson W. H. Lau.  Deshadownet: A multi-context embedding deep network for shadow removal.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2017.
  * Ronneberger et al. [2015] Olaf Ronneberger, Philipp Fischer, and Thomas Brox.  U-net: Convolutional networks for biomedical image segmentation.  In _Medical Image Computing and Computer-Assisted Intervention_ , 2015.
  * Simonyan and Zisserman [2014] Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition.  _arXiv preprint arXiv:1409.1556_ , 2014.
  * Sindagi et al. [2020] Vishwanath A. Sindagi, Poojan Oza, Rajeev Yasarla, and Vishak M. Patel.  Prior-based domain adaptive object detection for hazy and rainy conditions.  In _Proceedings of the European Conference on Computer Vision (ECCV)_ , 2020.
  * Song et al. [2023] Yuda Song, Zhuqing He, Hui Qian, and Xin Du.  Vision transformers for single image dehazing.  In _IEEE Transactions on Image Processing (TIP)_ , 2023.
  * Vasluianu et al. [2023] Florin-Alexandru Vasluianu, Tim Seizinger, and Radu Timofte.  Wsrd: A novel benchmark for high resolution image shadow removal.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops (CVPR Workshops)_ , 2023.
  * Vasluianu et al. [2024a] Florin-Alexandru Vasluianu, Tim Seizinger, Zongwei Wu, Rakesh Ranjan, and Radu Timofte.  Towards image ambient lighting normalization.  In _arXiv preprint arXiv:2403.18730_ , 2024a.
  * Vasluianu et al. [2024b] Florin-Alexandru Vasluianu, Tim Seizinger, Zhuyun Zhou, Zongwei Wu, Cailian Chen, Radu Timofte, et al.  NTIRE 2024 image shadow removal challenge report.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops (CVPR Workshops)_ , 2024b.
  * Vaswani et al. [2017] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, and Łukasz Kaiserand Illia Polosukhin.  Attention is all you need.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2017.
  * Wang et al. [2018] Jifeng Wang, Xiang Li, and Jian Yang.  Stacked conditional generative adversarial networks for jointly learning shadow detection and shadow removal.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2018.
  * Wang et al. [2021] Wenyi Wang, Jun Hu, Xiaohong Liu, Jiying Zhao, and Jianwen Chen.  Single image super-resolution based on multi-scale structure and nonlocal smoothing.  _EURASIP Journal on Image and Video Processing_ , 2021.
  * Wang et al. [2004] Zhou Wang, Alan C. Bovik, Hamid R. Sheikh, and Eero P. Simoncelli.  Image quality assessment: From error visibility to structural similarity.  In _IEEE Transactions on Image Processing (TIP)_ , 2004.
  * Wu et al. [2020] Minghu Wu, Rui Chen, and Ying Tong.  Shadow elimination algorithm using color and texture features.  In _Computational Intelligence and Neuroscience_ , 2020.
  * Xu et al. [2022] Dong Xu, Wei Dong, and Han Zhou.  Sclera recognition based on efficient sclera segmentation and significant vessel matching.  In _The Computer Journal_ , 2022.
  * Xu et al. [2024] Yimin Xu, Mingbao Lin, Hong Yang, Fei Chao, and Rongrong Ji.  Shadow-aware dynamic convolution for shadow removal.  In _Pattern Recognition_ , 2024.
  * Yin et al. [2019] Xiangyu Yin, Xiaohong Liu, and Huan Liu.  Fmsnet: Underwater image restoration by learning from a synthesized dataset.  In _International Conference on Artificial Neural Networks (ICANN)_ , 2019.
  * Zamir et al. [2022] Syed Waqas Zamir, Aditya Arora, Salman Khan, Munawar Hayat, Fahad Shahbaz Khan, and Ming-Hsuan Yang.  Restormer: Efficient transformer for high-resolution image restoration.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2022.
  * Zhang et al. [2020] Ling Zhang, Chengjiang Long, Xiaolong Zhang, and Chunxia Xiao.  Ris-gan: Explore residual and illumination with generative adversarial networks for shadow removal.  In _Proceedings of the AAAI Conference on Artificial Intelligence (AAAI)_ , 2020.
  * Zhang et al. [2018] Richard Zhang, Phillip Isola, Alexei A Efros, Eli Shechtman, and Oliver Wang.  The unreasonable effectiveness of deep features as a perceptual metric.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2018.
  * Zhao et al. [2018] Yunfeng Zhao, Chris Elliott, Huiyu Zhou, and Karen Rafferty.  Pixel-wise illumination correction algorithms for relative color constancy under the spectral domain.  In _IEEE International Symposium on Signal Processing and Information Technology (ISSPIT)_ , 2018.
  * Zhou et al. [2023] Han Zhou, Wei Dong, Yangyi Liu, and Jun Chen.  Breaking through the haze: An advanced non-homogeneous dehazing method based on fast fourier convolution and convnext.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops (CVPR Workshops)_ , 2023.
  * Zhu et al. [2022] Yurui Zhu, Zeyu Xiao, Yanchi Fang, Xueyang Fu, Zhiwei Xiong, and Zheng-Jun Zha.  Efficient model-driven network for shadow removal.  In _Proceedings of the AAAI Conference on Artificial Intelligence (AAAI)_ , 2022.