of the final sensor. As imaging information is typically 2D and spectral data
1D, a 3D sensor array would be required to achieve a single-shot wide-field
spectral imaging instrument. Such sensors unfortunately do not exist, but
there are multiple possibilities to address this challenge: The most obvious
one is a scanning approach, where a single-mode nonlinear interferometer is
used the measure the spectral properties and the focused idler beam is scanned
over the sample for spatial information. This approach is relatively simple
and robust and scanning can be fast and is routinely used in scanning
confocal/fluorescence microscopes. Another approach is to sequentially take
wide-field images at different wavelengths either by spectral filtering[60] or
tuning the emission wavelength of SPDC e.g. by temperature tuning the
crystal[62]. In principle, other approaches are also possible and potentially
useful, depending on the application. These include Fourier-domain
spectroscopy imaging approaches or hybrid schemes (for example, one spatial
and one spectral dimension on a CMOS camera and scanning one remaining spatial
dimension by moving the sample.)

##  7 Designing a setup for a specific application

As discussed in Sec.5, sensing based on induced coherence without induced
emission relies on particle correlations. These (classical and quantum)
correlations depend on the physical properties of the experimental setup. In
the case of SPDC, for example, the bandwidth of the pump laser together with
the length of the nonlinear crystal determine the spectral entanglement of the
twin photons. Similarly the transverse spatial properties of the pump beam
together with the dimensions of the nonlinear crystal determine the spatial
entanglement. We emphasize, however, that spectral and spatial entanglement
are not necessary for imaging with undetected photons. Classical correlations
are enough.

###  7.1 Wavelength considerations

Before getting started, the frequency range for probing the sample and for the
detection need to be chosen, while also considering the resulting pump
frequency given by energy conservation. It useful to consider a number of
trade-offs and boundary conditions for this multi-parameter selection.

For the selection of the probing wavelength a range of special interest is the
mid-IR region. Here, ro-vibrational molecular absorption lines, which are both
strong and very specific for the type of molecule that is probed, are
excellently suited for (bio-)chemical analysis by spectroscopic measurements.
As a consequence of the transparency range of commonly used nonlinear crystals
like ppKTP, ppLN or ppSLT, one can access wavelengths up to $\sim 5\mu m$ ,
which contains important wavelengths used for gas sensing as well as the CH-
stretch region around 3.45$\mu m$, which is useful for the identification and
analysis of organic compounds, including (micro)plastics, lipids in tissue or
collagen. Using nonlinear IR crystals such as AGS or opGAP, longer wavelengths
in the so called "fingerprint region" (up to 12$\mu m$) can be generated and
used.

Longer wavelengths scatter much less than shorter wavelength. This is useful,
for example, for OCT to perform 3D-imaging into otherwise strongly scattering
media like ceramics[61]. Here the specific wavelength is less important than
the bandwidth, which defines the axial resolution. Depending on the specific
application a large bandwidth is also relevant for spectroscopy or spectral
imaging. Large bandwidths will be achieved if one matches the probing and
detection wavelength’s group indices in the nonlinear crystal[89].
Interestingly, this can typically be achieved in ppKTP, ppLN and ppSLT for a
sensing wavelength in the mid-IR group-velocity matched with a wavelength in
the NIR or SWIR [89]. This strategy can also be applied for IR crystals like
AGS (via angle phase-matching) or opGAP. This allows a certain design freedom
to also accommodate other criteria in the wavelength choices, such as specific
pump wavelength, water-absorption windows or the availability or cost of
optical elements necessary.

Another possibly interesting choice for the sensing wavelength is the UV. This
can increase the maximal resolution by leveraging the lower Abbe-limit for UV-
Photons, while detecting in the technologically easier VIS/NIR region (see
secs.5.2.3 and 5.3.3). Also, spectral imaging in the UV has applications in
bio-imaging. The challenge here is the generation of photon pairs. In SPDC the
pump wavelength needs to be shorter than the sensing wavelength, which has
limitations due to the transparency ranges for dielectric nonlinear crystals.
A possible route around this is to use Spontanteous Four-Wave Mixing in gas-
filled hollow-core fibers[98].

For the optimal choice of detection wavelength using Si-based CCD- and CMOS-
sensors and cameras the detection wavelength should be chosen below $\sim
900$nm. Above this wavelength the quantum efficiency of Si-based sensors
typically drops quickly and vanishes above the Si bandgap ($\sim 1100$nm.)

###  7.2 Pump lasers

Having selected the probing and detection wavelength automatically, the pump-
wavelength is automatically determined via energy conservation. Selecting a
suitable pump laser is highly important, with availability, maximum power,
coherence length, beam-quality and cost as the main criteria for selection.
Especially when using spatial entanglement, the pump beam needs to be of high
quality. For spectroscopic application, the laser bandwidth (associated with
the coherence length) needs to be below the target spectral resolution one
wants to achieve. The same is true (in the time-domain) for OCT applications.

####  7.2.1 Spatial properties

Perfect momentum correlation would ideally be obtained for a plane wave pump,
which obviously cannot be generated perfectly experimentally. However, this
fact is an excellent guideline to what spatial properties of the pump beam are
important for imaging applications: Ideally the pump beam is as spatially
coherent as possible, its wave-front flat and with an only slowly varying
amplitude.

Lasers differ strongly in their beam quality depending on their type. Typical
gas, solid state, and fiber lasers have very good beam quality, whereas most
diode lasers (popular for their compactness and efficiency) have a far less
ideal beam quality. This can be remedied, if the pump laser we plan to use is
filtered spatially before pumping the nonlinear interferometer. We can either
use a 4f system with a pinhole in the Fourier plane or couple the laser beam
into a single mode fiber. If the filter parameters are optimally matched to
the incoming beam, only the higher order modes will be removed and the
fundamental mode will be transmitted. Clearly, the losses in both methods will
depend on the initial beam quality. One should take into account those losses
when estimating the required laser power.

####  7.2.2 Spectral properties

The spectral properties of the pump laser are essential for spectroscopy, OCT
and spectral imaging, but it should be kept in mind that the coherence length
of the pump can affect also the applications which are not directly related to
spectral measurements (see Sec.88.2-8.3). Interestingly, because of the
typical spectral-angular correlations in SPDC from a bulk crystal the spectral
properties of the pump laser can affect the spatial properties of the SPDC.
Therefore it is advisable to choose laser with coherence length as large as
possible, whenever available, and carefully consider the effects of using
lasers with a shorter coherence length. Another important feature can be
wavelength stability, which if not sufficient can influence spectral/axial
calibration of the spectroscopy/OCT data.

###  7.3 Transverse spatial correlations

The crucial element in the design of the interferometer for a given
application is to provide correlations in the degree of freedom of interest.
Spatial entanglement is in general not necessary for the applications of
induced coherence without induced emission that we discuss in this tutorial
(please see the explanation in Sec.5.1 and Fig.7). As shown in Secs.5.2.3 and
5.3.3, the resolution of the image is directly affected by the spatial
correlations at the plane in which the sample is placed with respect to the
crystal(s).

The transverse momentum correlations in SPDC can be thought of as a
consequence of the transverse momentum conservation in this process[47]. The
sum of momenta of signal and idler photons equals the momentum of the pump
photon. As a consequence, if the nonlinear crystal was pumped with a plane
wave, which has a well-defined momentum, we’d obtain the perfect momentum
correlation of the photon pair. Knowing the momentum of the signal photon, we
could predict the momentum of the idler photon. Physically realizable beams
have a finite spatial extent and as a consequence, their momentum distribution
has to have a finite width. This uncertainty of the momentum of the pump beam
translates to imperfect correlations of signal and idler beams. Knowing the
momentum of the signal photon, we can predict the range of idler photon
momenta; the correlation is not perfect. The better the pump beam can be
approximated by a plane wave, the sharper the momentum correlation between the
idler and signal photons.

In SPDC transverse position correlations are quite sensitive to the crystal
length[47]. The shorter the crystal length, the sharper the transverse
position correlations between signal and idler.

###  7.4 Nonlinear crystals

There is a wide range of nonlinear crystals that have been used for SPDC and
therefore are in principle suited for nonlinear interferometers, such as
ppKTP, ppLN, ppSLT, BBO, BiBO, AGS just to name a few. However, when choosing
a crystal optimally suited for the targeted application there are a number of
important criteria to consider:

  * •

Achievable phase-matching - without phase-matching either by angle/bi-
refringent or quasi-phasematching, no SPDC can be generated efficiently
(except in ultra-thin crystals).

  * •

Suitable transparency range - the crystal should be highly transparent for the
used wavelengths.

  * •

Brightness (nonlinear coefficient) - high brightness (i.e. a large photon-
rate) will lead to desirable short measurement times.

  * •

Large bandwidth - the bandwidth determines both spectral range in spectroscopy
applications as well as axial resolution in OCT and should therefor be as
large as possible for those.

  * •

Crystal length and aperture - the maximum length co-determines the brightness
trading-off with the bandwidth; the size aperture defines (together with the
selected wavelengths) the number of spatial modes that for a certain length
crystal can be generated and used for imaging[87].

  * •

General commercial availability and cost - important criterion for real-world
applications. Typically, however, pump laser and final sensor will have a more
poignant influence on the cost.

###  7.5 Cameras

Typically, Si-based detectors are used for detecting the signal photons, as
the detection wavelength is often purposefully chosen to lie in their
sensitivity range. If cameras are used, sCMOS cameras are often preferable to
the EMCCD cameras, because typically a photon flux per pixel of more then
10-100photons/s can be easily achieved, and sCMOS cameras feature a better SNR
at such illumination levels than EMCCDs and can have more and smaller pixels.
In general, the number of illuminated pixels (magnification onto the camera)
should be chosen such that 1 spatially resolved element corresponds to 2-3
Pixels. Having more pixels per resolved element, does not bring any benefit,
but on the contrary increases the amount of total readout and dark noise from
the camera and therefore lowers the SNR.

##  8 Experimental guidelines: tips and tricks

Most of the tips and tricks we provide below for the ZWM mandel setup, also
apply to the SU(1,1) interferometer in the low gain regime, such as those
illustrated in Figs.3, 14b and 4. Notice that in the setup in Fig.4b all three
fields, signal, idler and pump, go through the imaged object, which will lead
to further effects not described in this tutorial.

###  8.1 Building and aligning a Zou-Wang-Mandel interferometer

Setting up a Zou-Wang-Mandel interferometer can be challenging because the
alignment needs to be performed with SPDC light, not with bright laser beams.
Moreover, correlations required for the multimode sensing applications can
result in a low degree of spatial and spectral coherence of the individual
photon beams. As a consequence, the visibility of interference depends
critically on transverse and longitudinal shifts between the interfering
beams[99, 100]. In this section, we give some tips and tricks for building and
aligning a Zou-Wang-Mandel Interferometer, such as those in Figs.2 and 8.

####  8.1.1 Controlling the relative phase and power between pair emissions at
the two sources

In principle, a $50:50$ beam splitter could be used to split the pump beam in
the ZWM interferometer and the phase between the interferometric arms could be
scanned by shifting this beam splitter or one of the mirrors, as shown in
Fig.2. In practice, however, it is advantageous to have fine-tuned control of
the relative pump power illuminating the crystals. In order to do this, we
recommend using a half-waveplate ($HWP_{1}$) followed by a polarizing beam
splitter ($PBS$) instead of $BS_{1}$, as shown in Fig.8. Rotating $HWP_{1}$
not only enables finding the optimal ratio of powers for the maximal
visibility, but also can be used to aid alignment, by directing all the pump
power to one of the crystals. This can be helpful for example when overlapping
the SPDC beams from both crystals. Fig.8 also shows another half-waveplate
($HWP_{2}$) at $45^{\circ}$ placed in one of the pump paths, which guarantees
that both crystals are pumped with the same polarization.

It is also useful to be able to shift the interferometric phase without
touching any mirrors or beamsplitters. For that, one can use a single quarter-
waveplate ($QWP$) set at zero degrees before the PBS and rotated around its
vertical axis. Alternatively, one can place before the PBS a combination of
another half-waveplate sandwiched between two $QWP$s at $45^{\circ}$. The
interferometric phase is then tuned by rotating the sandwiched $HWP$.

###  8.2 Temporal alignment

####  8.2.1 From indistinguishability to zero-delay requirements

In building any interferometer, it is necessary to adjust the combined path
lengths to within the coherence length of the detected light in order to
observe interference. In the language of quantum information, this condition
is due to the requirement of path indistinguishability [33]. Let us consider
the ZWM interferometer shown in Fig.2, and denote $l_{P_{1}}$ and $l_{P_{2}}$
as the optical path lengths of the pump from $BS_{1}$ to nonlinear sources
$Q_{1}$ and $Q_{2}$, respectively. We will denote $l_{I_{1}}$ as the idler
optical path in between the two sources, and we shall label the signal $S_{1}$
($S_{2}$) optical path length from $Q_{1}$ ($Q_{2}$) to $BS_{2}$ as
$l_{S_{1}}$ ($l_{S_{2}}$). Two path length requirements can be formulated
[101]:

$\displaystyle\delta l_{1}=l_{P_{1}}+l_{I_{1}}-l_{P_{2}}<l_{coh-pump};$ (88)
$\displaystyle\delta l_{2}=l_{I_{1}}+l_{S_{2}}-l_{S_{1}}<l_{coh-signal},$ (89)

where $l_{coh-pump}$ and $l_{coh-signal}$ are the pump and signal field
coherence lengths, respectively.

These conditions can be understood intuitively, by analyzing how the two
interfering alternatives (emissions from the two crystals) could be
distinguished.To find the first condition (Eq.88), we consider a pulsed
excitation of the two crystals. We require the idler photon generated in the
first crystal to arrive at the second crystal together with the pump pulse, so
that the idler photons generated in the two crystals overlap in time. Strictly
speaking, it is the coherence length of the pump laser, not the pulse length
that governs the second condition. Note that condition (Eq.88) is valid for
the case of excitation using so-called continuous wave (CW) lasers. To find
the second condition, (Eq.89) let’s consider a single pair of photons
generated in one of the crystals. If we were to detect both photons, we could
measure the time difference between their arrival at the detectors and, if
this time was different for the two pairs, we could distinguish between the
two alternatives. Note, however, that even if we do not detect idler photons,
just the possibility of obtaining welcher weg information is enough to inhibit
interference in the signal.

We stress again that it is not relevant in this reasoning if we actually
perform the measurements required to distinguish the alternatives or not. The
mere possibility of performing such measurements precludes the observation of
interference or in the intermediate case reduces the visibility of
interference fringes. For a detailed theoretical treatment please refer to
[41, 101, 102].

####  8.2.2 Finding the zero delay using the fringe visibility or spectral
interference

In order to adjust path lengths for the conditions expressed above, one can
maximize the visibility of interference fringes as a function of an optical
delay added in the signal, idler and/or pump modes, or, alternatively, by
observing the spectrum of the interfering signal beams from the two crystals.
We recommend this latter strategy if interference is not immediately seen in
the detector/camera. The non-zero path length difference $\delta l$
(corresponding to non-zero optical delay difference $\tau$ in the
interferometer) results in the appearance of spectral interference fringes
with the period given by $\frac{2\pi}{\tau}$. The effect of the spectrometer
is as if one had many bandpass filters, one for each wavelength to within the
spectral resolution of the equipment. In other words, the effective coherence
length of the fields in the equations above is larger than that which most
bandpass filters can provide. Therefore, one sees interference in the
spectrometer before one can observe interference in the detector. If the
resolution of the spectrometer is high enough to resolve the fringes for a
given delay, it is straightforward to minimize the optical path length
difference, by maximizing the period of spectral interference fringes up to a
point when the entire spectrum is in phase. In other words, as the
interferometer path lengths are adjusted, the interference fringes become
spectrally wider in the spectrometer. In fact, their width is inversely
proportional to the path length difference $\delta l$. Of course, the broader
spectrum results in shorter coherence length and in the requirements for the
observation of interference becoming more stringent.

####  8.2.3 Spectral bandpass filters for the initial alignment

Because SPDC in general produces broadband fields, it is useful to use narrow
bandpass filters at the detectors in order to have a workable signal coherence
length. The narrower the interference filter in front of the camera the easier
the alignment is. Nevertheless, the final alignment needs to be performed with
a spectral bandwidth broad enough for the final application.

###  8.3 Spatial alignment

####  8.3.1 Alignment of the imaging systems

Imaging requires multiple imaging and/or Fourier transform optical systems
(Fig.8). Each of these lenses or off-axis parabolic mirror systems has to be
aligned separately. In the case of perfectly aligned imaging systems in the
interferometer we should obtain an unmodulated intensity profile at the
camera. Misalignments in the setup can in turn lead to the appearance of
intensity fringes at the camera plane, which for the case of the momentum
correlation enabled QIUP setup were studied in [103]. In the ZWM
interferometer, misalignment of the signal field can, to a certain extent, be
”compensated” with the misalignment of the idler field. This is quite
unfortunate because one can end up with sub-optimal interference visibility.

Typically the dichroic mirrors and beam splitters allow one to perform the
initial alignment of the setup using the pump beams. In this case, the
alignment is not different than that of the standard Mach-Zehnder
interferometer. Later the idler beams need to be overlapped to ensure the
indistinguishability of the idler photons generated in the two crystals. It is
convenient to overlap the two beams by monitoring them in two complementary
bases, for example at an image plane of the crystal and at a Fourier plane of
the crystals. For this alignment it is very helpful to have two lenses on
flipper mounts just in front of the camera, one that images onto the camera
the crystal plane and the other performing the Fourier transform of the
electric field at the crystal plane.

In certain designs (see for example [87]), beams with very different
wavelengths pass through certain imaging components. In such cases chromatic
aberrations need to be minimized by using achromatic lenses or replacing the
lenses with off-axis parabolic mirrors.

####  8.3.2 Coupling between spatial and temporal alignment by thick lenses

We often describe optical setups using thin lens approximation. In practice,
when we want to minimize the distances in the setup, we use lenses with short
focal lengths. Such lenses, because of their thickness, introduce a
significant delay that depends on the distance from the optical axis. This can
lead to complications when aligning the setup if one is not careful to always
keep the optical axis of the propagating fields aligned with the center of the
lenses.

Standard lens alignment procedures are helpful here: preparing a laser beam
along the propagation direction of the beam of interest and making sure that
the beam pointing direction is not modified when an extra lens is introduced
and at the same time that the back-reflection from the lens surface comes back
very close to the source. If back-reflections from both surfaces of a lens are
visible, it suffices to overlap them.

####  8.3.3 Spatial partial incoherence of the signal and idler beams

In the case of spatially multimode SPDC, which is necessary for widefield
imaging, individual signal and idler beams are spatially partially incoherent.
This has profound implications for the design of the experimental setup, as
partially incoherent light propagates differently than perfectly coherent
light. In particular, one should expect a much larger illumination area on the
object (FoV) than if these were propagating coherent Gaussian fields. In other
words multimode SPDC light doesn’t form a beam that can be treated as a laser
beam, the latter being fully spatially coherent.

####  8.3.4 Using an auxiliary laser beam to stimulate emission into idler and
signal beams for easier alignment

Parametric downconversion can be induced (stimulated) by aligning an auxiliary
laser source with at least one of the downconverted beams generated in the
crystals. The process of stimulated parametric downconversion is a useful tool
for the alignment of the ZWM or SU(1,1) interferometer (Fig.7b) because it
significantly increases the intensity of the detected signal and allows one to
increase the coherence length of the PDC light. Moreover, if the stimulating
laser has a larger coherence length than the band pass filter used in front of
the camera, the resulting longer coherence length of the stimulated beams
allows the experimentalist to focus on the spatial part of alignment before
dealing with the fine adjustment of the optical path lengths (temporal
alignment).

Stimulated emission inherits also the spatial coherence properties of the
stimulating beam, therefore the stimulation with coherent laser beams results
in a down-converted beam with a narrower angular spread than in the case of
the spontaneously emitted light. When spots from the two crystals are being
overlapped at the camera, the smaller spread translates to a possibility of a
more precise alignment. Therefore it is particularly useful to combine the
stimulated emission with monitoring the Fourier and image planes.

The "trick" of using a seed laser can also be used for imaging via induced
coherence with induced emission, as was demonstrated in ref.[80]. Their setup
is illustrated in Fig.7(b). The sample is illuminated with the seeding laser.
Detection, pumping and seeding wavelengths are chosen according to one’s
needs, taking into consideration the availability of lasers, crystals and
detectors. Notice that cheaper cameras can be used, as the signal is much
brighter than in the case of spontaneous down-conversion.

###  8.4 Loss within the interferometer

In a standard interferometer, loss in one of the arms can be compensated for
by introducing an equal loss in the other arm. It is a distinguishing feature
of the ZWMI and other interferometers based on induced coherence without
induced emission, that losses in the idler arm between the two crystals lead
to a reduction in the mutual coherence of the two signal beams and therefore
cannot be compensated. As a consequence, it is essential to minimize the
losses in the path between the two crystals (or equivalent paths in the
designs different than ZWM), as the transmission of this arm sets the upper
bound for interference fringe visibility.

To sum up, in the ZWM experiment, losses in the idler path between the crystal
(refer to Fig. 1) control the mutual coherence between the signal beams and
cannot be compensated for, whereas the losses in other arms do not affect the
coherence and can be compensated.

##  9 Outlook

One of the most important ways to categorize various types of interferometers
(both linear and nonlinear) is how they measure up against specific
limitations, and whether or not they exceed them. Based on what application is
in mind for a device it can be measured up against one, or more, of several
types of limits on the ability of the device to perform specific tasks –
typically related to the sensitivity, signal-to-noise ratio, and/or
resolution.

With this in mind, there are a number of interesting directions where the
field is headed. Firstly it will have a major impact when experimental
techniques improve sufficiently to robustly enter the high-gain regime. Sub-
shot-noise performances in different sensing arrangements, as well as
compensating SNR reductions due to losses and in general much higher photon-
rates, leading to shorter measurement times, will be in focus then. Moreover,
extending the wavelengths that are covered into the finger-print region beyond
6$\mu m$ as well as further improving techniques in the THz region.

Moreover, a number of further interferometric sensing and imaging techniques
could be adapted for nonlinear interferometers, such as tomographic holography
for 3D imaging, a combination of coherence gating (with a broadband source)
and holography, to achieve optical sectioning as well as aperture synthesis
techniques like Fourier ptychography. Finally combining nonlinear
interferometry with super-resolution techniques might lead to novel imaging
modalities to be explored.

In addition to applications to imaging and metrology, the study of ZWM-type
nonlinear interferometers have had important implications to fundamental
quantum physics. The ZWM-interferometer has already been used to study quantum
complementarity and its connection to spatial coherence [32, 40] and partial
polarization [104, 105]. Similar setups have been recently used to measure
twin-photon correlations [49, 48] and entanglement [106, 107]. Generalizations
of the ZWM-experiment have led to the discovery of novel methods of generating
multi-particle and/or high-dimensional entangled states [108, 109, 110].
Therefore, further studies of such nonlinear interferometers will potentially
result in new research direction in fundamental quantum physics and quantum
information science.

Acknowledgments We thank Inna Kviatkovsky, Helen M Chrzanowski, Victoria
Borish, Jorge Fuenzalida, Armin Hochrainer, and Anton Zeilinger for numerous
discussions. G.B.L. acknowledges support from the Brazilian National Council
for Scientific and Technological Development (CNPq), from the Fundação de
Amparo à Pesquisa do Estado do Rio de Janeiro - FAPERJ, and from the
Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES - Brasil) –
Finance Code 001. R.L. acknowledges the funding by the Foundation for Polish
Science within the FIRST TEAM project ‘Spatiotemporal photon correlation
measurements for quantum metrology and super-resolution microscopy’ co-
financed by the European Union under the European Regional Development Fund
(POIR.04.04.00-00-3004/17-00). S.R. acknowledges funding from Deutsche
Forschungsgemeinschaft (RA 2842/1-1) as well as from Bundesministerium fuer
Bildung und Forschung (BMBF) within projects QUIN (13N15402) and SimQPla
(13N15944). Disclosures The authors declare no conflicts of interest.

## References

  * [1] G. Brida, M. Genovese, and I. R. Berchera, “Experimental realization of sub-shot-noise quantum imaging,” Nature Photonics 4, 227–230 (2010).
  * [2] J. Sabines-Chesterking, A. McMillan, P. Moreau, S. Joshi, S. Knauer, E. Johnston, J. Rarity, and J. Matthews, “Twin-beam sub-shot-noise raster-scanning microscope,” Optics express 27, 30810–30818 (2019).
  * [3] G. Triginer Garces, H. M. Chrzanowski, S. Daryanoosh, V. Thiel, A. L. Marchant, R. B. Patel, P. C. Humphreys, A. Datta, and I. A. Walmsley, “Quantum-enhanced stimulated emission detection for label-free microscopy,” Applied Physics Letters 117, 024002 (2020).
  * [4] C. Casacio, L. Madsen, A. Terrasson, M. Waleed, K. Barnscheidt, B. Hage, M. Taylor, and W. Bowen, “Quantum-enhanced nonlinear microscopy,” Nature 594, 201 (2021).
  * [5] I. F. Santos, M. A. Sagioro, C. H. Monken, and S. Pádua, “Resolution and apodization in images generated by twin photons,” Physical Review A 67, 033812 (2003).
  * [6] I. F. Santos, L. Neves, G. Lima, C. Monken, and S. Pádua, “Generation and detection of magnified images via illumination by entangled photon pairs,” Physical Review A 72, 033802 (2005).
  * [7] O. Schwartz, J. M. Levitt, R. Tenne, S. Itzhakov, Z. Deutsch, and D. Oron, “Superresolution microscopy with quantum emitters,” Nano letters 13, 5832–5836 (2013).
  * [8] A. Classen, J. von Zanthier, M. O. Scully, and G. S. Agarwal, “Superresolution via structured illumination quantum correlation microscopy,” Optica 4, 580–587 (2017).
  * [9] M. Unternährer, B. Bessire, L. Gasparini, M. Perenzoni, and A. Stefanov, “Super-resolution quantum imaging at the heisenberg limit,” Optica 5, 1150–1154 (2018).
  * [10] R. Tenne, U. Rossman, B. Rephael, Y. Israel, A. Krupinski-Ptaszek, R. Lapkiewicz, Y. Silberberg, and D. Oron, “Super-resolution enhancement by quantum image scanning microscopy,” Nature Photonics 13, 116–122 (2019).
  * [11] V. Giovannetti, S. Lloyd, and L. Maccone, “Advances in quantum metrology,” Nature photonics 5, 222–229 (2011).
  * [12] E. Polino, M. Valeri, N. Spagnolo, and F. Sciarrino, “Photonic quantum metrology,” AVS Quantum Science 2, 024703 (2020).
  * [13] G. Tóth and I. Apellaniz, “Quantum metrology from a quantum information science perspective,” Journal of Physics A: Mathematical and Theoretical 47, 424006 (2014).
  * [14] A. G. White, J. R. Mitchell, O. Nairz, and P. G. Kwiat, ““interaction-free” imaging,” Physical Review A 58, 605 (1998).
  * [15] D. Klyshko, “Effect of focusing on photon correlation in parametric light scattering,” Zh. Eksp. Teor. Fiz 94, 82–90 (1988).
  * [16] A. Belinskii and D. Klyshko, “Two-photon optics: diffraction, holography, and transformation of two-dimensional signals,” Soviet Journal of Experimental and Theoretical Physics 78, 259–262 (1994).
  * [17] T. Pittman, Y. Shih, D. Strekalov, and A. V. Sergienko, “Optical imaging by means of two-photon quantum entanglement,” Physical Review A 52, R3429 (1995).
  * [18] A. Gatti, E. Brambilla, and L. Lugiato, “Quantum imaging,” Progress in Optics 51, 251–348 (2008).
  * [19] K. W. C. Chan, M. N. O’Sullivan, and R. W. Boyd, “Two-color ghost imaging,” Physical Review A 79, 033808 (2009).
  * [20] R. S. Aspden, D. S. Tasca, R. W. Boyd, and M. J. Padgett, “Epr-based ghost imaging using a single-photon-sensitive camera,” New Journal of Physics 15, 073032 (2013).
  * [21] P.-A. Moreau, E. Toninelli, T. Gregory, and M. J. Padgett, “Imaging with quantum states of light,” Nature Reviews Physics 1, 367–380 (2019).
  * [22] G. B. Lemos, V. Borish, G. D. Cole, S. Ramelow, R. Lapkiewicz, and A. Zeilinger, “Quantum imaging with undetected photons,” Nature 512, 409–412 (2014).
  * [23] M. Lahiri, R. Lapkiewicz, G. B. Lemos, and A. Zeilinger, “Theory of quantum imaging with undetected photons,” Physical Review A 92, 013832 (2015).
  * [24] B. Viswanathan, G. B. Lemos, and M. Lahiri, “Position correlation enabled quantum imaging with undetected photons,” Optics letters 46, 3496–3499 (2021).
  * [25] G. B. Lemos, V. Borish, S. Ramelow, R. Lapkiewicz, G. Cole, and A. Zeilinger, “Quantum imaging with undetected photons,” United States of America US Patent 9,557.262 B2 (2017).
  * [26] G. B. Lemos, V. Borish, S. Ramelow, R. Lapkiewicz, G. Cole, and A. Zeilinger, “Quantum imaging with undetected photons,” European Union EP Patent 2 887 137 B1 (2018).
  * [27] B. Chen, C. Qiu, S. Chen, J. Guo, L. Q. Chen, Z. Y. Ou, and W. Zhang, “Atom-light hybrid interferometer,” Phys. Rev. Lett. 115, 043602 (2015).
  * [28] P. Lähteenmäki, G. S. Paraoanu, J. Hassel, and P. J. Hakonen, “Coherence and multimode correlations from vacuum fluctuations in a microwave superconducting cavity,” Nature communications 7, 1–7 (2016).
  * [29] D. E. Bruschi, C. Sabín, and G. S. Paraoanu, “Entanglement, coherence, and redistribution of quantum resources in double spontaneous down-conversion processes,” Phys. Rev. A 95, 062324 (2017).
  * [30] Z. J. Ou, _Quantum Optics for Experimentalists_ (World Scientific Publishing Company, 2017).
  * [31] R. P. Feynman, R. B. Leighton, and M. Sands, _The Feynman Lectures on Physics Vol.III_ (Addison-Wesley, 1964).
  * [32] L. Mandel, “Coherence and indistinguishability,” Optics letters 16, 1882–1883 (1991).
  * [33] B.-G. Englert, “Fringe visibility and which-way information: An inequality,” Physical review letters 77, 2154 (1996).
  * [34] E. C. G. Sudarshan and T. Rothman, “The two-slit interferometer reexamined,” American Journal of Physics 59, 592–595 (1991).
  * [35] K. P. Zetie, S. F. Adams, and R. M. Tocknell, “How does a mach-zehnder interferometer work?” Physics Education 35, 46–48 (2000).
  * [36] H. Rauch and S. A. Werner, _Neutron Interferometry: Lessons in Experimental Quantum Mechanics, Wave-Particle Duality, and Entanglement_ , vol. 12 (Oxford University Press, USA, 2015).
  * [37] H.-A. Bachor, T. C. Ralph, S. Lucia, and T. C. Ralph, _A guide to experiments in quantum optics_ , vol. 1 (Wiley Online Library, 2004).
  * [38] A. C. Elitzur and L. Vaidman, “Quantum mechanical interaction-free measurements,” Foundations of Physics 23, 987–997 (1993).
  * [39] P. Kwiat, H. Weinfurter, T. Herzog, A. Zeilinger, and M. A. Kasevich, “Interaction-free measurement,” Physical Review Letters 74, 4763 (1995).
  * [40] X. Y. Zou, L. J. Wang, and L. Mandel, “Induced coherence and indistinguishability in optical interference,” Phys. Rev. Lett. 67, 318–321 (1991).
  * [41] L. Wang, X. Zou, and L. Mandel, “Induced coherence without induced emission,” Phys. Rev. A 44, 4614 (1991).
  * [42] H. M. Wiseman and K. Molmer, “Induced coherence with and without induced emission,” Phys. Lett. A 270, 245–248 (2000).
  * [43] M. Lahiri, A. Hochrainer, R. Lapkiewicz, G. B. Lemos, and A. Zeilinger, “Nonclassicality of induced coherence without induced emission,” Physical Review A 100, 053839 (2019).
  * [44] M. I. Kolobov, E. Giese, S. Lemieux, R. Fickler, and R. W. Boyd, “Controlling induced coherence for quantum imaging,” Journal of Optics 19, 054003 (2017).
  * [45] Z. Ou, L. Wang, X. Zou, and L. Mandel, “Coherence in two-photon down-conversion induced by a laser,” Physical Review A 41, 1597 (1990).
  * [46] L. Wang, X. Zou, and L. Mandel, “Observation of induced coherence in two-photon downconversion,” JOSA B 8, 978–980 (1991).
  * [47] S. P. Walborn, C. Monken, S. Pádua, and P. S. Ribeiro, “Spatial correlations in parametric down-conversion,” Physics Reports 495, 87–139 (2010).
  * [48] A. Hochrainer, M. Lahiri, R. Lapkiewicz, G. B. Lemos, and A. Zeilinger, “Quantifying the momentum correlation between two light beams by detecting one,” Proceedings of the National Academy of Science 114, 1508–1511 (2016).
  * [49] M. Lahiri, A. Hochrainer, R. Lapkiewicz, G. B. Lemos, and A. Zeilinger, “Twin photon correlations in single-photon interference,” Physical Review A 96 96, 013822 (2017).
  * [50] M. A. Horne, A. Shimony, and A. Zeilinger, “Two-particle interferometry,” Physical Review Letters 62, 2209 (1989).
  * [51] B. Yurke, S. L. McCall, and J. R. Klauder, “Su (2) and su (1, 1) interferometers,” Physical Review A 33, 4033 (1986).
  * [52] T. J. Herzog, J. G. Rarity, H. Weinfurter, and A. Zeilinger, “Frustrated two-photon creation via interference,” Phys. Rev. Lett. 72, 629–632 (1994).
  * [53] M. Chekhova and Z. Ou, “Nonlinear interferometers in quantum optics,” Advances in Optics and Photonics 8, 104–155 (2016).
  * [54] A. Burlakov, M. Chekhova, D. Klyshko, S. Kulik, A. Penin, Y. Shih, and D. Strekalov, “Interference effects in spontaneous two-photon parametric scattering from two macroscopic regions,” Physical Review A 56, 3214 (1997).
  * [55] A. Zajonc, L. Wang, X. Zou, and L. Mandel, “Quantum eraser,” Nature 353, 507–508 (1991).
  * [56] P. G. Kwiat, A. M. Steinberg, and R. Y. Chiao, “Three proposed “quantum erasers”,” Physical Review A 49, 61 (1994).
  * [57] F. Hudelist, J. Kong, C. Liu, J. Jing, Z. Y. Ou, and W. Zhang, “Quantum metrology with parametric amplifier- based photon correlation interferometers,” Nature Communications 5, 1–6 (2014).
  * [58] D. A. Kalashnikov, A. V. Paterova, S. P. Kulik, and L. A. Krivitsky, “Infrared spectroscopy with visible light,” Nature Photonics (2016).
  * [59] T. S. Iskhakov, S. Lemieux, A. Perez, R. W. Boyd, G. Leuchs, and M. V. Chekhova, “Nonlinear interferometer for tailoring the frequency spectrum of bright squeezed vacuum,” Journal of Modern Optics 63, 64–70 (2015).
  * [60] I. Kviatkovsky, H. M. Chrzanowski, E. G. Avery, H. Bartolomaeus, and S. Ramelow, “Microscopy with undetected photons in the mid-infrared,” Science Advances 6, eabd0264 (2020).
  * [61] A. Vanselow, P. Kaufmann, I. Zorin, B. Heise, H. M. Chrzanowski, and S. Ramelow, “Frequency-domain optical coherence tomography with undetected mid-infrared photons,” Optica 7, 1729–1736 (2020).
  * [62] A. V. Paterova, S. M. Maniam, H. Yang, G. Grenci, and L. A. Krivitsky, “Hyperspectral infrared microscopy with visible light,” Science advances 6, eabd0460 (2020).
  * [63] A. Rojas-Santana, G. J. Machado, D. Lopez-Mago, and J. P. Torres, “Frequency-correlation requirements on the biphoton wave function in an induced-coherence experiment between separate sources,” Phys. Rev. A 102, 053711 (2020).
  * [64] A. Vallés, G. Jiménez, L. J. Salazar-Serrano, and J. P. Torres, “Optical sectioning in induced coherence tomography with frequency-entangled photons,” Phys. Rev. A 97, 023824 (2018).
  * [65] C. Gerry and P. Knight, _Introductory quantum optics_ (Cambridge university press, 2005).
  * [66] P. A. M. Dirac, “The quantum theory of the emission and absorption of radiation,” Proceedings of the Royal Society of London 114, 243–265 (1927).
  * [67] W. H. Louisell, “Amplitude and phase uncertainty relations,” Phys. Letters 7 (1963).
  * [68] L. Susskind and J. Glogower, “Quantum mechanical phase and time operator,” Physics Physique Fizika 1, 49 (1964).
  * [69] S. Barnett and D. Pegg, “On the hermitian optical phase operator,” Journal of Modern Optics 36, 7–19 (1989).
  * [70] J. W. Noh, A. Fougères, and L. Mandel, “Measurement of the quantum phase by photon counting,” Phys. Rev. Lett. 67, 1426–1429 (1991).
  * [71] Z. Ou, “Fundamental quantum limit in precision phase measurement,” Physical Review A 55, 2598 (1997).
  * [72] S. Pirandola, B. R. Bardhan, T. Gehring, C. Weedbrook, and S. Lloyd, “Advances in photonic quantum sensing,” Nature Photonics 12, 724–733 (2018).
  * [73] D. Braun, G. Adesso, F. Benatti, R. Floreanini, U. Marzolino, M. W. Mitchell, and S. Pirandola, “Quantum-enhanced measurements without entanglement,” Reviews of Modern Physics 90, 035006 (2018).
  * [74] N. R. Miller, S. Ramelow, and W. N. Plick, “Versatile super-sensitive metrology using induced coherence,” Quantum 5, 458 (2021).
  * [75] W. N. Plick, J. P. Dowling, and G. S. Agarwal, “Coherent-light-boosted, sub-shot noise, quantum interferometry,” New Journal of Physics 12, 083014 (2010).
  * [76] F. Hudelist, J. Kong, C. Liu, J. Jing, Z. Ou, and W. Zhang, “Quantum metrology with parametric amplifier-based photon correlation interferometers,” Nature communications 5, 3049 (2014).
  * [77] Z. Ou and X. Li, “Quantum su(1,1) interferometers: Basic principles and applications,” APL Photonics 5 (2020).
  * [78] W. Du, J. Kong, J. Jia, S. Ming, C.-H. Yuan, J. Chen, Z. Ou, M. W. Mitchell, and W. Zhang, “Su (2)-in-su (1, 1) nested interferometer,” arXiv preprint arXiv:2004.14266 (2020).
  * [79] E. Giese, S. Lemieux, M. Manceau, R. Fickler, and R. W. Boyd, “Phase sensitivity of gain-unbalanced nonlinear interferometers,” Physical Review A 96, 053863 (2017).
  * [80] A. C. Cardoso, L. Berruezo, D. F. Ávila, G. B. Lemos, W. M. Pimenta, C. H. Monken, P. L. Saldanha, and S. Pádua, “Classical imaging with undetected light,” Physical Review A 97, 033827 (2018).
  * [81] C. H. Monken, P. S. Ribeiro, and S. Pádua, “Transfer of angular spectrum and image formation in spontaneous parametric down-conversion,” Phys. Rev. A 57, 3123 (1998).
  * [82] G. B. Lemos, P. H. S. Ribeiro, and S. P. Walborn, “Optical integration of a real-valued function by measurement of a stokes parameter,” J. Opt. Soc. Am. A 31, 704 (2014).
  * [83] J. Fuenzalida, A. Hochrainer, G. B. Lemos, E. Ortega, R. Lapkiewicz, M. Lahiri, and A. Zeilinger, “Resolution of quantum imaging with undetected photons,” Quantum 6, 646 (2022).
  * [84] L. Mandel and E. Wolf, _Optical coherence and quantum optics_ (Cambridge university press, 1995).
  * [85] B. Viswanathan, G. B. Lemos, and M. Lahiri, “Resolution limit in quantum imaging with undetected photons using position correlations,” Optics Express 29 (23), 38185–38198 (2021).
  * [86] M. Born and E. Wolf, _Principles of Optics: Electromagnetic Theory of Propagation, Interference and Diffraction of Light_ (Cambridge University Press, 1999), 7th ed.
  * [87] I. Kviatkovsky, H. M. Chrzanowski, and S. Ramelow, “Mid-infrared microscopy via position correlations of undetected photons,” Optics Express 30, 5916 (2022).
  * [88] M. Reichert, X. Sun, and J. W. Fleischer, “Quality of spatial entanglement propagation,” Physical Review A 95, 063836 (2017).
  * [89] A. Vanselow, P. Kaufmann, H. M. Chrzanowski, and S. Ramelow, “Ultra-broadband spdc for spectrally far separated photon pairs,” Opt. Lett. 44, 4638–4641 (2019).
  * [90] M. Kutas, B. Haase, P. Bickert, F. Riexinger, D. Molter, and G. von Freymann, “Terahertz quantum sensing,” Science Advances 6 (2020). Publisher: American Association for the Advancement of Science _eprint: https://advances.sciencemag.org/content/6/11/eaaz8065.full.pdf.
  * [91] A. Paterova, H. Yang, C. An, D. Kalashnikov, and L. Krivitsky, “Measurement of infrared optical constants with visible photons,” New Journal of Physics 20, 043015 (2018).
  * [92] S. Töpfer, M. Gilaberte Basset, J. Fuenzalida, F. Steinlechner, J. P. Torres, and M. Gräfe, “Quantum holography with undetected light,” Science advances 8, eabl4301 (2022).
  * [93] W. Choi, C. Fang-Yen, K. Badizadegan, S. Oh, N. Lue, R. R. Dasari, and M. S. Feld, “Tomographic phase microscopy,” Nature methods 4, 717–719 (2007).
  * [94] A. Vallés, G. Jiménez, L. J. Salazar-Serrano, and J. P. Torres, “Optical sectioning in induced coherence tomography with frequency-entangled photons,” Phys. Rev. A 97, 023824 (2018).
  * [95] A. V. Paterova, H. Yang, C. An, D. A. Kalashnikov, and L. A. Krivitsky, “Tunable optical coherence tomography in the infrared range using visible photons,” Quantum Science and Technology 3, 025008 (2018).
  * [96] J. Fujimoto and W. Drexler, “Introduction to Optical Coherence Tomography,” in _Optical Coherence Tomography: Technology and Applications,_ W. Drexler and J. G. Fujimoto, eds. (Springer, Berlin, Heidelberg, 2008), Biological and Medical Physics, Biomedical Engineering, pp. 1–45.
  * [97] G. J. Machado, G. Frascella, J. P. Torres, and M. V. Chekhova, “Optical coherence tomography with a nonlinear interferometer in the high parametric gain regime,” Applied Physics Letters 117, 094002 (2020).
  * [98] S. Lopez-Huidobro, M. Lippl, N. Y. Joly, and M. V. Chekhova, “Fiber-based biphoton source with ultrabroad frequency tunability,” Optics Letters 46, 4033 (2021).
  * [99] G. Barbosa, “Degree of visibility in experiments of induced coherence without induced emission: a heuristic approach,” Physical Review A 48, 4730 (1993).
  * [100] T. Grayson and G. Barbosa, “Spatial properties of spontaneous parametric down-conversion and their effect on induced coherence without induced emission,” Physical Review A 49, 2948 (1994).
  * [101] L. Wang, “Investigation of induced coherence with and without induced emission,” Ph.D. thesis, The University of Rochester (1992).
  * [102] X. Zou, “Nonclassical interference effects of down-converted photons,” Ph.D. thesis, The University of Rochester (1993).
  * [103] A. Hochrainer, M. Lahiri, R. Lapkiewicz, G. B. Lemos, and A. Zeilinger, “Interference fringes controlled by noninterfering photons,” Optica 4, 341–344 (2017).
  * [104] M. Lahiri, “Wave-particle duality and polarization properties of light in single-photon interference experiments,” Physical Review A 83, 045803 (2011).
  * [105] M. Lahiri, A. Hochrainer, R. Lapkiewicz, G. B. Lemos, and A. Zeilinger, “Partial polarization by quantum distinguishability,” Physical Review A 95, 033816 (2017).
  * [106] M. Lahiri, R. Lapkiewicz, A. Hochrainer, G. B. Lemos, and A. Zeilinger, “Characterizing mixed-state entanglement through single-photon interference,” Physical Review A 104, 013704 (2021).
  * [107] G. B. Lemos, R. Lapkiewicz, A. Hochrainer, M. Lahiri, and A. Zeilinger, “Measuring mixed state entanglement through single-photon interference,” arXiv preprint arXiv:2009.02851 (2020).
  * [108] M. Krenn, A. Hochrainer, M. Lahiri, and A. Zeilinger, “Entanglement by path identity,” Physical Review Letters 118, 080401 (2017).
  * [109] M. Lahiri, “Many-particle interferometry and entanglement by path identity,” Phys. Rev. A 98, 033822 (2018).
  * [110] J. Kysela, M. Erhard, A. Hochrainer, M. Krenn, and A. Zeilinger, “Path identity as a source of high-dimensional entanglement,” Proceedings of the National Academy of Sciences 117, 26118–26122 (2020).

sample


# REVECA – Rich Encoder-decoder framework for Video Event CAptioner

Jaehyuk Heo, YongGi Jeong, Sunwoo Kim, Jaehee Kim, Pilsung Kang
School of Industrial & Management Engineering, Korea University
Seoul, Korea
{jaehyuk_heo, ygjeong27, sunwoo_kim, jaehee_kim<EMAIL_ADDRESS>Corresponding author

###### Abstract

We describe an approach used in the Generic Boundary Event Captioning
challenge at the Long-Form Video Understanding Workshop held at CVPR 2022. We
designed a Rich Encoder–decoder framework for Video Event CAptioner (REVECA)
that utilizes spatial and temporal information from the video to generate a
caption for the corresponding the event boundary. REVECA uses frame position
embedding to incorporate information before and after the event boundary.
Furthermore, it employs features extracted using the temporal segment network
and temporal-based pairwise difference method to learn temporal information. A
semantic segmentation mask for the attentional pooling process is adopted to
learn the subject of an event. Finally, LoRA is applied to fine-tune the image
encoder to enhance the learning efficiency. REVECA yielded an average score of
50.97 on the Kinetics-GEBC test data, which is an improvement of 10.17 over
the baseline method. Our code is available in
https://github.com/TooTouch/REVECA.

##  1 Introduction

Recently, video understanding tasks such as video action recognition [13, 4]
and video captioning [18, 6] have been proposed for learning a model so as to
understand a series of semantic content in a video. However, most video
understanding tasks focus on predicting predefined actions or summarizing the
content of a given video; there is no task that tries to distinguish the
semantic content in a long-form video [12]. The Kinetics-GEBD dataset was
proposed to fill this gap, allowing the model to learn to recognize distinct
semantic events within the long-form video [12]. Generic Event Boundary
Captioning (GEBC), the main task considered in this study, involves verbally
describing the subject based on the boundary and also the changes in the
subject’s state before and after the boundary. To support this task, the
Kinetics-GEBC dataset has recently been released [17].

Vision-language models for learning data such as Kinetics-GEBC can be grouped
into three representative structures: (1) a single encoder-based model [20],
(2) a dual encoder-based model [8], and (3) an encoder–decoder-based structure
[15]. In this report, we design the Rich Encoder–decoder framework for Video
Event CAptioner (REVECA) that elaborates additional spatial and temporal
information to Contrastive Captioners (CoCa) [19], a recently proposed
integrated video captioning framework. The proposed REVECA achieved a
significantly improved performance for the Kinetics-GEBC dataset compared to
the benchmark models provided in the competition.

##  2 Related Works

Wang and Gao [17] used the UniVL as a two-stream architecture [8] and the
ActBERT as a one-stream architecture [20] for GEBC. UniVL is a dual encoder
vision-language framework. It is trained to align the representation of the
two encoders using the outputs extracted using the encoder of vision and
language. UniVL performs video caption generation by learning using the cross
encoder and decoder. ActBERT is a single encoder vision-language framework.
ActBERT uses language and vision data as the inputs to a single encoder to
reflect multimodal information in the same representation space using multi-
head attention and then learns language data using masked language modeling.

Figure 1: Architecture of proposed rich encoder–decoder framework. Frame
features are calculated by element-wise addition of frame position embedding
and segmentation embedding to Image Encoder output. Aggregated frame features
for generic events are obtained by concatenating frame features included in
each boundary and then concatenating them with TPD and TSN features for
multimodal text decoder’s cross-attention operation.

Recently, a unified various vision-language framework named CoCa was proposed
[19]. CoCa uses an image encoder, unimodal text decoder, and multimodal text
decoder to learn vision-language data in a single stage and utilizes two
objective functions together. Our approach is based on CoCa but uses certain
different components within the framework. ActBERT-revised proposed in [17]
used the region of interest (RoI) features extracted by the Faster-RCNN [10]
to use the information on the subjects existing in the video. However, as RoI
is information that includes subjects and unspecified areas, we use the
semantic segmentation mask to indicate the exact area of the subject.

##  3 Approach

We used CoCa as the basic architecture and utilized additional features for
more granular visual information. Fig. 1 shows the overall architecture of the
proposed REVECA. We fine-tuned the image encoder by applying LoRA [5], a
method that shows more effective training performance when the entire model is
fine-tuned using only a small number of trainable parameters [5].

###  3.1 Temporal Information

Frame Aggregation In CoCa, features for each frame are aggregated by
attentional pooling to generate a video-level feature [19]. However, we
preserved three distinct types of information in the proposed REVECA for the
GEBC challenge: (1) Before, (2) Boundary, and (3) After. Each frame feature
extracted by the image encoder is stacked in Eq. 1:

$F=[EN_{img}(f_{1}),EN_{img}(f_{2}),\cdots,EN_{img}(f_{N_{f}})],$ (1)

where $f_{i}$ is the i-th frame, $N_{f}$ is the number of frames, and
$EN_{img}$ is the image encoder. $[\cdot,\cdot]$ indicates the concatenation
of the frames.

As the [CLS] token embedding of the image encoder is used to calculate the
contrastive loss with the [CLS] token embedding of the unimodal text decoder
[19], the [CLS] token embeddings of the image encoder for all frames are
represented by the average of the [CLS] tokens of all images as given in Eq.
2:

$CLS=\frac{1}{N_{f}}\sum_{i=1}^{N_{f}}CLS_{i}.$ (2)

Frame Position Embedding We used a frame position embedding
$E_{p}\in\mathbb{R}^{N_{f}\times d}$ to inject sequential information of
Before, Boundary, and After features where $d$ is the dimension of the image
encoder. The frame position embedding as shown in Fig. 1 is added to the frame
features given in Eq. 1.

Temporal-based Pairwise Difference (TPD) As the frame-level differences are
found to be effective for detecting Generic Events [17], we also employed the
TPD as given in Eq. 3:

$\displaystyle TPD=[[F_{i}-F_{j}],[F_{i}-F_{b}],[F_{b}-F_{j}]],$ (3)
$\displaystyle\forall_{i}\in N_{bef},\forall_{j}\in N_{aft},$

where $F_{b}$ denotes the frame features of the boundary $b$. $N_{bef}$ is the
number of frames before the boundary whereas $N_{aft}$ is the number of frames
after the boundary. We applied the TPD using [CLS] token embedding of the
image encoder instead of frame features because applying TPD directly to the
frame features might disturb the training process owing to the high
dimensionality. The TPD features calculated by the [CLS] token embedding of
the attentional pooling are concatenated with the output of the attentional
pooling for the frame features as given in Eq. 1:

$F_{TPD}=[F,TPD].$ (4)

Temporal Segment Network (TSN) [16] We utilized the official TSN features in
the GEBC challenge as an additional input to the multimodal text decoder to
increase the action recognition performance of video data. Here,
2048-dimensional TSN features are extracted before and after the boundary
using the pre-trained TSN in [17]. We applied the TSN feature to the linear
projection layer and represented it in the same dimension as the embedding
dimension of the multimodal text decoder. TSN features were then concatenated
with the results of Eq. 4:

$F_{TPD,TSN}=[F_{TPD},TSN].$ (5)

$F_{TPD,TSN}$ is used as an input for cross-attention in the multimodal text
decoder.

###  3.2 Spatial information

Semantic Segmentation Mask We use semantic predictions as additional input to
incorporate more information based on semantic granularity. Pre-trained
Mask2Former [2], which achieved state-of-the-art performance in various
segmentation tasks, was employed as the segmentation predictor, and we stored
predictions in advance for all sampled frames. We fed pixel-level predictions
to a patch embedding layer constructed separately, not a patch embedding layer
used in the image encoder, and then added it to the image encoder output shown
in Eq. 1.

##  4 Experiments

###  4.1 Implementation Details

Training setup Our model took 25 hours to train on a GPU server with six A100
GPUs for 10,000 steps. We used a batch size of eight per GPU. Adafactor
optimizer [11] was used with $\beta_{1}=0.9$ and a weight decay ratio of
$0.01$. We warmed up the learning rate for the first 300 steps with 3% of the
incremental steps. We chose our model based on the top-1 token accuracy of the
validation dataset.

Dataset Each boundary in the video clip has two sampling ranges before and
after the boundary timestamp. We sampled ten frames as the maximum range for
before and after the boundary. The resolution of the input frame was
$224\times 224$, and the max token length was set to 128.

Model We used the ViT-L/16 [3] as the image encoder, which was pre-trained on
the ImageNet-21k (14 million images, 21,843 classes) at the resolution of
$224\times 224$. In addition, the GPT2-small [9] was used as the unimodal and
multimodal decoder. The number of queries for the attentional pooling layer
was set to 16. As the CoCa decoder generates the unimodal and multimodal text
representations simultaneously, contrastive as well as generative objectives
are applied:

$\mathcal{L}_{CoCa}=\lambda_{Con}\cdot\mathcal{L}_{Con}+\lambda_{Cap}\cdot\mathcal{L}_{Cap}.$

We used the ratio of $1:0.1$ for the loss weighting hyper-parameters
$\lambda_{Cap}$ and $\lambda_{Con}$.

LoRA For memory efficiency, we applied LoRA to our query, key, value, and the
output projection layer with a rank of 8 ($\alpha=8$) and dropout probability
of 0.1.

Caption generation We set the max generation token length to 128. Beam search
was used to generate captions in our experiments with a beam size of 10 and
five beam groups.

Evaluation We used CIDEr [14], SPICE [1], and ROUGE-L [7] metrics to evaluate
our model, all of which are commonly used in image or video captioning tasks.

###  4.2 Results

We optimized the hyperparameters based on validation performance as described
in Sec. 4. The submitted final model was trained based on the integrated
training and validation data.

In order to validate the performance of our model, four models that were
tested on GEB+ were selected as the baseline models for comparison. As
presented in Tab. 1, the proposed REVECA yielded an average score of 50.97,
which is 10.17 higher than ActBERT-revised, the best among the baseline
models. More specifically, the performance improvement against ActBERT-revised
in terms of CIDEr, SPICE, and ROUGE-L is 19.2, 5.14, and 6.19, respectively.

Method | Avg. | CIDEr | SPICE | ROUGE-L
---|---|---|---|---
CNN + LSTM | 29.94 | 49.73 | 13.62 | 26.46
Robust Change Captioning | 34.16 | 58.56 | 16.34 | 27.57
UniVL-revised | 36.64 | 65.74 | 18.06 | 26.12
ActBERT-revised | 40.80 | 74.71 | 19.52 | 28.15
REVECA (our model) | 50.97 | 93.91 | 24.66 | 34.34
Table 1: Our final submission results to the Kinetic-GEBC Challenge at CVPR
2022 LOVEU workshop.

##  5 Conclusion

In this report, we propose REVECA, which attempts to incorporate rich spatial
and temporal information using CoCa, a unified framework of the vision-
language model, as a base architecture. Experimental results show that the
proposed REVECA can achieve better performance than conventional vision-
language benchmark models. Our model achieves approximately 25% performance
improvement over the current SOTA model.

A limitation of our model is that it focuses more on information about vision.
If more sophisticated information extracted from text data is incorporated, we
expect the performance of the proposed REVECA to be further boosted.

## References

  * [1] Peter Anderson, Basura Fernando, Mark Johnson, and Stephen Gould.  SPICE: semantic propositional image caption evaluation.  In European Conference on Computer Vision, ECCV, 2016.
  * [2] Bowen Cheng, Ishan Misra, Alexander G. Schwing, Alexander Kirillov, and Rohit Girdhar.  Masked-attention mask transformer for universal image segmentation.  In Conference on Computer Vision and Pattern Recognition, CVPR, 2022.
  * [3] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby.  An image is worth 16x16 words: Transformers for image recognition at scale.  In International Conference on Learning Representations, ICLR, 2021.
  * [4] Christoph Feichtenhofer, Haoqi Fan, Jitendra Malik, and Kaiming He.  Slowfast networks for video recognition.  In International Conference on Computer Vision, ICCV, 2019.
  * [5] Edward J. Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, and Weizhu Chen.  Lora: Low-rank adaptation of large language models.  In International Conference on Learning Representations, ICLR, 2022.
  * [6] Ranjay Krishna, Kenji Hata, Frederic Ren, Li Fei-Fei, and Juan Carlos Niebles.  Dense-captioning events in videos.  In International Conference on Computer Vision, ICCV, 2017.
  * [7] Chin-Yew Lin.  ROUGE: A package for automatic evaluation of summaries.  In Text Summarization Branches Out, 2004.
  * [8] Huaishao Luo, Lei Ji, Botian Shi, Haoyang Huang, Nan Duan, Tianrui Li, Jason Li, Taroon Bharti, and Ming Zhou.  Univl: A unified video and language pre-training model for multimodal understanding and generation.  arXiv preprint arXiv:2002.06353, 2020.
  * [9] Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever.  Language Models are Unsupervised Multitask Learners, 2019.
  * [10] Shaoqing Ren, Kaiming He, Ross B. Girshick, and Jian Sun.  Faster R-CNN: towards real-time object detection with region proposal networks.  In Advances in Neural Information Processing Systems 28, 2015.
  * [11] Noam Shazeer and Mitchell Stern.  Adafactor: Adaptive learning rates with sublinear memory cost.  In International Conference on Machine Learning, ICML, 2018.
  * [12] Mike Zheng Shou, Stan Weixian Lei, Weiyao Wang, Deepti Ghadiyaram, and Matt Feiszli.  Generic event boundary detection: A benchmark for event segmentation.  In International Conference on Computer Vision, ICCV, 2021.
  * [13] Du Tran, Heng Wang, Lorenzo Torresani, Jamie Ray, Yann LeCun, and Manohar Paluri.  A closer look at spatiotemporal convolutions for action recognition.  In Conference on Computer Vision and Pattern Recognition, CVPR, 2018.
  * [14] Ramakrishna Vedantam, C. Lawrence Zitnick, and Devi Parikh.  Cider: Consensus-based image description evaluation.  In Conference on Computer Vision and Pattern Recognition, CVPR, 2015.
  * [15] Oriol Vinyals, Alexander Toshev, Samy Bengio, and Dumitru Erhan.  Show and tell: A neural image caption generator.  In Conference on Computer Vision and Pattern Recognition, CVPR, 2015.
  * [16] Limin Wang, Yuanjun Xiong, Zhe Wang, Yu Qiao, Dahua Lin, Xiaoou Tang, and Luc Van Gool.  Temporal segment networks for action recognition in videos.  Trans. Pattern Anal. Mach. Intell., TPAMI, 2019.
  * [17] Yuxuan Wang and Difei Gao.  Geb+: A benchmark for generic event boundary captioning, grounding and text-based retrieval.  arXiv preprint arXiv:2204.00486, 2022.
  * [18] Jun Xu, Tao Mei, Ting Yao, and Yong Rui.  MSR-VTT: A large video description dataset for bridging video and language.  In Conference on Computer Vision and Pattern Recognition, CVPR, 2016.
  * [19] Jiahui Yu, Zirui Wang, Vijay Vasudevan, Legg Yeung, Mojtaba Seyedhosseini, and Yonghui Wu.  Coca: Contrastive captioners are image-text foundation models.  arXiv preprint arXiv:2205.01917, 2022.
  * [20] Linchao Zhu and Yi Yang.  Actbert: Learning global-local video-text representations.  In Conference on Computer Vision and Pattern Recognition, CVPR, 2020.


A Novel Model for Distributed Big Data Service Composition using Stratified
Functional Graph Matching
Carlos R. Rivero♮ and Hasan M. Jamil♭
♮Department of Computer Science, Rochester Institute of Technology, USA

<EMAIL_ADDRESS>
♭Department of Computer Science, University of Idaho, USA

<EMAIL_ADDRESS>
###### Abstract

A significant number of current industrial applications rely on web services.
A cornerstone task in these applications is discovering a suitable service
that meets the threshold of some user needs. Then, those services can be
composed to perform specific functionalities. We argue that the prevailing
approach to compose services based on the “all or nothing” paradigm is
limiting and leads to exceedingly high rejection of potentially suitable
services. Furthermore, contemporary models do not allow “mix and match”
composition from atomic services of different composite services when binary
matching is not possible or desired. In this paper, we propose a new model for
service composition based on “stratified graph summarization” and “service
stitching”. We discuss the limitations of existing approaches with a
motivating example, present our approach to overcome these limitations, and
outline a possible architecture for service composition from atomic services.
Our thesis is that, with the advent of Big Data, our approach will reduce
latency in service discovery, and will improve efficiency and accuracy of
matchmaking and composition of services.

##  1 Introduction

Since the advent of the World Wide Web, a significant number of companies have
relied on web services to expose and share their products and services, and
manage their activities. One of the most important tasks in current industrial
applications that use web services consists of discovering suitable services
that meet some threshold of the user needs, which is usually referred to as
service matchmaking [24]. The expected output of this task is a ranking of
available services that meet the matching threshold of the user needs sorted
by relevance. In the event a single service is not available that atomically
satisfies the user needs, multiple atomic services are usually strung together
to design a composite service that amounts to a process known as service
composition [4].

In the context of Big Data, it can be argued that in addition to the size of
the data, the variability and the number of candidate repositories or services
pose a significant challenge for users toward efficiently finding and using
them. We posit that the sheer number of candidate services make it necessary
to automate the process of service matchmaking and composition since a large
number of services may potentially satisfy user needs [20], often partially.

While atomic service matching or composing atomic services based on the “all
or nothing” model [4] covers many applications, services requiring components
of two or more web services cannot be composed currently due to technical
hurdles. We believe disallowing partial service matching, and service
composition using such partial matchings limit the applicability of service
composition in real-world scenarios, since they lead to exceedingly high
rejection of potentially suitable services. Allowing “mix and match” of parts
of services will enlarge the class of applications that can be modeled or the
services that can be supported, i.e., instead of matching a single service, it
is possible that the best solution to some user needs may entail the
composition of parts of several services in a meaningful way.

In this paper, we present a new approach to service matchmaking and
composition that, to the best of our knowledge, is the first that addresses
distributed, fine grain and approximate service discovery and composition in
the context of Big Data. In our approach, we represent services as graphs, and
use “graph summarization” to describe them at multiple layers. We then use the
resulting stratified graphs to match services at different description
granularity to improve precision and recall. While we view the graph matching
technique based on stratified graph summaries and the issue of graph
summarization as an orthogonal research and leave them outside the scope of
this paper, we believe that developing such algorithms are possible along the
lines of [23, 5, 15, 27, 13], though not trivial. Furthermore, we also propose
to allow composing services from partial matches of services and stitch them
together to architect a new service. Such an approach will allow composing
parts of atomic services not possible in contemporary models.

As a motivation for our approach, we use an example from the benchmarking
domain to illustrate the salient features of our service matching model. We
also use this example to discuss the limitations of the existing models and
show how we can be overcome them. We also briefly present a possible
representation model for service description that will allow partial matching
and our proposed “service stitching” as we envision it. While we are agnostic
about the standards to choose, we use features borrowed from BPMN and OWL-S to
represent service description workflow graphs for the time being. Finally, our
thesis is that, our approach will effectively reduce latency in service
discovery, improve efficiency and accuracy of service matchmaking and
composition by taking different layers of abstraction into account, and by
composing best-fitting services from disparate services.

The remainder of the paper is organized as follows: related research is
presented in Section 2 followed by a motivating example in Section 3 where we
discuss the merits of our approach in relation to the limitations of current
approaches. In Sections 4 and 5 respectively we describe our idea of service
matchmaking and composition. We wrap up our presentation by presenting our
overall conceptual model in Section 6 before concluding in Section 7.

##  2 Related Research

Sycara et al. [24] successfully demonstrated that including semantic
annotations over services improve service matchmaking and composition. In
semantic web, several models such as OWL-S [18] and WSMO [26] support such
annotations. Interestingly, many service matchmaking and composition
approaches that use semantic annotations are based on graph matching [12, 10],
and an upward trend in leveraging graph matching is clearly visible (e.g.,
[17, 4]).

Graph matching currently is a very active area of research which can broadly
be classified into two groups: exact and subgraph matching, and approximate
matching. Exact matchers aim to find those structurally isomorphic subgraphs
that exactly match a specific query. Some of the prominent systems include
GraphQL [7], Turbo${}_{\mbox{iso}}$ [6], and NetQL [22]. Approximate graph
matching, on the other hand, focuses on finding those subgraphs that
approximately match a specific query within a degree of deviation. Such
matching are useful when the query graph is tentative, or data sets are noisy
or encomplete. Some of the well regarded systems in approximate matching
include TALE [25], SAPPER [28] and TraM [1].

Currently, a new direction of research in graph summarization is also taking
root [11, 23, 5, 15, 27, 13] that has significant potential in service
matchmaking as we advocate in this paper. While the main focus remains on
summarization of graphs based on types (node or edge type), efforts are also
underway to summarize graphs to discover functional similarity or equivalence
(e.g., [16]). Such functional summarization of graphs have been instrumental
in designing equivalent workflow design policies for commercial applications
[14], and can be a powerful tool for service matching based on functional
equivalence [19, 9].

While the logic based service description representation (e.g., [10, 10]) are
different than the graph based representations in OWL-S (e.g., [4]), neither
are flexible enough to accommodate errors or closeness in form of approximate
matching. In real life applications, where large number of diverse services
are possible, it is difficult to imagine user queries to deterministic in
terms of its needs with respect to available descriptions of services. Most
likely scenario is that most services will fail to match when an expectation
(a query) is submitted and several components of multiple services when strung
together may satisfy that need. In this paper, we take the position that an
approximate graph matching over stratified summarized graphs of web service
descriptions will yield a more realistic and effective service discovery that
will allow service stitching to orchestrate a target service from multiple
partially matched services. In the remainder of the paper we introduce such a
model.

##  3 A Motivating Example

Let us consider an application where a user wishes to study the performance of
a number of query engines for benchmarking, each of which has an entry point
by means of which queries can be issued. In addition to the entry points, it
is necessary to use a set of queries to test the engines. These queries
require data that can be given as input or can be randomly generated according
to a given schema. During the benchmarking task, the performance of each query
engine is measured based on a given performance variable, such as the time
used or memory consumed by the engine to execute the queries over the data.
Finally, the expected output is a ranking in which the engines are sorted
according to their performance. In our recent research, we have actually
successfully applied such an approach to benchmark SPARQL engines over RDF
data in [21], where we devised a statistical evaluation methodology to compare
those engines side by side. In this paper, we leverage an abstraction of this
approach to focus on the benchmarking of relational engines by means of SQL
queries as follows.

In this example, assume that there exists a service that takes a relational
table, a set of SQL queries and a set of engine entry points as input, and it
outputs a relational table that contains the time consumed by each query
engine to execute the queries over the input data. Figure 1 shows an example
of a model to describe the inputs and outputs of this service called the query
execution service. If a user wishes to use such a service, Figure 2 shows an
example of a model that describes the user needs. Note that the query topology
is different from the description topology, and the name of the nodes and
edges are not the same. Due to these dissimilarities, current service
matchmakers will reject the query execution service as a candidate match. The
main reasons being a mismatch in topology and semantics, which is extremely
difficult to resolve using existing technologies including approximate graph
matching [4].

Figure 1: Sample model of the Query execution service.

To overcome these limitations, it is necessary to take into account the
semantic and topological disparities for a successful matchmaking. For
instance, if it is possible to partially match the semantics of a relational
table, the system should output such a service as a potential candidate with a
estimate of semantic closeness. Although the matching process will be involved
and significantly complicated, but doing so will improve the matching quality,
precision and recall.

Figure 2: Sample model of the user needs.

Once we allow flexible matching, we can consider allowing heterogeneity, and a
“service stitching” paradigm in which we allow services to be composed by
accepting partial services from different sources. For example, let us assume
that the input data format user wants to use for the query execution service
is in text format while the service itself requires it in tabular format. This
mismatch could be easily resolved by using an auxiliary service for format
conversion without rejecting the match. This can be made possible if the
semantic descriptions for the services (input output behavior of each of the
nodes in the service description graphs) are available, and if we allow
plugging in external components into a service.

Finally, once we allow external plug-ins, we should be able to actually
generalize this concept to allow extracting partial services from a
description, and stitch several such partial descriptions to compose an
entirely new service to meet a user need. Though challenging, such an approach
will allow orchestrating services that does not exist even though the
components needed do. The idea is detailed in the remainder of the paper in
detail.

##  4 Functional Graph Summarization for Service Matching

We illustrate our approach to flexible service matching using a high level
abstraction of the example of relational query engine benchmarking in [21]. In
which, the process of benchmarking has two critical steps: The first step
consists of executing a set of queries over a supplied data set using the
engines being tested. In the second step, we analyze the performance of the
engines, so we need a method to compare the values of the performance variable
that we obtained in the previous step. We consider these values as samples of
an unknown random variable, so we use Kruskal-Wallis’s H test [8] to determine
if there are statistically significant differences among the performance
variable for the engines under test. If there is no performance difference
among the engines, it means that they all behave statistically identically
with respect to the performance variable. Otherwise, we use Wilcoxon’s signed
rank test [8] to rank the engines according to their performance. Taking
inspiration from this methodology, we devised the three composite service
descriptions represented in the form of graphs in Figure 3.

(a) Visualizing the performance of query engines using random data.

(b) Ranking of query engines using Wilcoxon’s signed-ranked test.

(c) Comparison of samples using Student’s t-test.

Figure 3: Examples of composite services and their summarizations.

Figure 3(a) presents a composite service whose goal is to visualize the
performance of a set of query engines based on some randomly generated data.
In this figure, atomic services are represented as oval rectangles, and input
and output data are represented as rectangles with folding corners. In this
representation, data nodes are shown to have three fields: 1) the name (N) of
the input/output data; 2) the format (F) of the data, which can be CSV,
relational, XML, or RDF, to mention a few; and 3) the semantics (S) of the
data, which describes the contents of the data node. We then use a set of pre-
defined labels to describe the functionalities of these graphs and their
components as follows.

Let us assume that we have a distinguished set of labels $\cal L$. Each label
$l\in\cal L$ represents a well understood concept in real life, such as
“Student’s t-test”, or “Ranking”. To be able to associate a concept with a
graph that captures its spirit, we use the function $\mathchar 256\relax:{\cal
L}\mapsto 2^{\mathbf{G}}$, where $\mathbf{G}$ is a set of graph descriptions
of the form $\langle G,D\rangle$ such that $G$ is a graph and $D$ is its input
output behavior described in terms of data, format, analytical tools and other
needs for the graph to function according to its specification (as shown in
Figure 3). Note that a concept may map to a set of such graphs that are likely
implementations of that concept. The selection of anyone of these graphs
largely depends on how well the input output behavior of the graph matches
with the expected behavior. The inverse function $\mathchar
262\relax:\mathbf{G}\mapsto{\cal L}$, on the other hand, associates with each
graph description a conceptual label that describes it uniquely.

We say, a graph description corresponding to a service is atomic when no sub-
graph of it are mapped to a conceptual label in $\cal L$, i.e., a description
is self-contained and indivisible. Otherwise, it is called composite –
composed of atomic and other composite descriptions. For example, the
(composite) service in Figure 3(a) comprises of three atomic services: 1)
Random data generation that automatically generates a set of random relational
data based on a set of input parameters. 2) All query executor which takes a
number of SQL queries, a set of relational raw data and a set of query engine
endpoints as input, and outputs the performance of the engines111Note that the
queries and the data must be related, which is represented as an edge
connecting both data nodes. Also note that the engine endpoints are modeled as
URLs.. 3) The Data visualizer is responsible for plotting the performance
results in a set of charts. These atomic services are at the lowest level of
representation of the composite service in Layer 2 in Figure 3(a).
Additionally, this service is summarized into two different layers of
abstraction. In Layer 1, Random data generation and All query executor have
been grouped into a single composite service called Random data query
executor. In other words, the data nodes have been summarized containing their
formats and some of their semantics. In Layer 0, the whole service has been
summarized into two nodes: a data node that represents some input data in SQL
format, and another composite service called Random results visualizer.

Figures 3(b) and 3(c) show two similar services at three different levels of
summarization. The first of which implements the service in Figure 3(a) using
Wilcoxon’s signed-ranked test, while the second implements it using Kruskal-
Wallis’s H test and Student’s t-test. Now assume that a non-expert user
expresses her need to benchmark a set of query engines and rank them according
to their performance as the query graph shown in Figure 4(a), expressed
equivalently at two different layers of detail or summarization. To find a
matching service, we can contemplate using an approximate graph matcher to
identify the candidate services that match with this query graph and the
degree to which they match. Regardless of the query at Layer 1 or Layer 0, we
can expect a matcher to fail or return a poor match with any of the three
services in Figure 3 due to vastly different topology or labels. But a more
smarter matcher that takes into account the semantic meaning of the labels,
and is able to consider summarized concepts will be able to recognize a
possible match. For instance, this query will not match well with the service
in Figure 3(a) at Layer 0, but it will partially match if we compare Layer 1
of the query with Layer 2 of the service, i.e., both contains a Query
execution service. With respect to the service in Figure 3(b), the query will
partially match at Layers 0 and 1, i.e., Engine comparator node, and Query
executor and Ranker nodes, respectively. Regarding the service in Figure 3(c),
it is possible to match the single node at Layer 0 (Sample comparator and
Engine comparator). At Layer 1, it will partially match with the output nodes
since both are rankers. The main observation here is that the query should not
fail, and we should be able to find a match despite the disparity in the
details of the service description, or the query posed.

(a) Query executor and ranker.

(b) Execute queries, analyze the differences and rank them.

Figure 4: Sample queries of user needs.

If we now consider the queries in Figure 4(b), in which the user specifically
wants to use Kruskal-Wallis’s H test to analyze the differences between the
engines, and use Wilcoxon’s signed-ranked test to rank the engines according
to their performance, we quickly discover that regardless of version of the
query in Layer 1 or Layer 0 is submitted, it will fail. In this case, the
query in Layer 1 will partially match with the service in Figure 3(a) at Layer
2, and with the service in Figure 3(b) at Layers 0 and 1. Furthermore, while
the service in Figure 3(c) will not match at Layer 0 with the query, but the
query at Layer 1 will match with the Layer 2 description of the service. Thus,
it is important to note that while no service matches the query enough in
Figure 4(b), it is possible to orchestrate a service by combining components
of different services in a meaningful way, which we advocate in this paper.

Figure 5: Example of a best-fitting composite service (thick arrows represent
format conversions among the data).

##  5 Service Stitching

Our main goal is to gain the ability to match or orchestrate services with
respect to a query described with well understood concepts in the form of a
specialized graph from a large set of service descriptions, also represented
using graphs. In contrast to most existing approaches, we allow service
descriptions to be as detail as possible and at the discretion of the designer
and service provider but aim to compensate for any omission in detail to
return a successful match. This approach removes the limitations imposed by
current systems in two ways.

First, the topology of the service description graphs need not match the query
graph structurally so long we are able to match them conceptually at different
summarization levels using the functions $\mathchar 256\relax$ and $\mathchar
262\relax$. For this to be successful, we primarily insist upon a well
understood vocabulary of concepts, and a mechanism to roll-up and drill-down
the summarization hierarchy of the description and query graphs to find a
match, using a process we call stratified graph matching. As we have mentioned
at the outset, we consider research in stratified graph matching to be
orthogonal to our presentation here and needs further investigation. The
advantage afforded by this approach is particularly liberating for the service
providers. For instance, the disigner of the service in Figure 3(c) can now
choose to expose it at any level and not worry about its possible match with a
query. Instead, she is now free to focus on the details on how best she can
describe the service as one single description.

Second, service discovery based on stratified graph matching also inspired a
novel approach to service orchestration at the finest granularity, we call
service stitching. Stacking up multiple services in a pipeline to compose a
complex service manually is not new. What is new in service stitching is that
a query can now be directly mapped to multiple services using the same
principle of stratified graph matching because we are allowed to look for
services elsewhere in a piecewise fashion, in this instance laterally. With a
slight engineering, we can also allow partial services in a description to be
invoked.

For example, consider again the query shown in Figure 4(b) consisting three
concepts that match with the atomic services in Figures 3(a), 3(b), and 3(c),
respectively, but not as single service. We can visualize connecting the
output of the Kruskal-Wallis’s H test sample checker service in Figure 3(c)
with the input of the Wilcoxon’s signed-ranked test ranker service in Figure
3(b), since the former outputs the difference analysis and the latter takes
this analysis as input, i.e., the output/input data share the same semantics.
The ability to stitch partial services to construct a target service will
hinge upon our ability to enter and exit a desired points in a service
description graph, a practice not allowed in current service implementations.
However, in our approach, all graph descriptions include input out behaviors
and thus includes the building blocks needed to support service stitching as
detailed in the following section.

Figure 6: Conceptual model. Figure 7: Sample instantiation of our conceptual
model.

##  6 Conceptual Model

We hinted on stitching Kruskal-Wallis’s H test with the Wilcoxon’s signed-
ranked test ranker services in the previous section. Since the Kruskal-
Wallis’s H test sample checker in Figure 3(c) expects the input samples in RDF
format, and the All query executor service in Figure 3(a) outputs the data in
relational format, a suitable conversion service is required to make them
compatible. Once we are able to stick in such conversions, we are able to
orchestrate the service in Figure 5 (format conversions shown as thick
arrows). Therefore, we assume that we have a database of converter services is
available to facilitate simple heterogeneity resolution, e.g., from relational
data to RDF [3], or from XML files to relational data [2], to mention just a
few.

To support the system we envisioned in the previous sections, a new conceptual
model for service description and matching is required. Figure 6 presents an
UML-like conceptual model that can be used in this context, which allows to
represent that a composite service is composed of a number of atomic services.
Each atomic service has a number of inputs and outputs, which can be
automatically transformed by means of converters. Finally, each composite
service, atomic service, input/output data, and converter is related to a
semantic description that allows us to automatically perform the matchmaking
and composition of atomic services.

It is important to note that our model is agnostic to the implementation of
the system, i.e., it can be used in conjunction with BPMN or OWL-S processes
to describe workflows. In this context, our approach has similarities with the
description of processes in OWL-S, for instance, atomic, simple and composite
processes in OWL-S can be seen as our service descriptions at Layer 2, the
summarization of the services in the different abstraction layers, and our
composite services, respectively. Furthermore, OWL-S relies on bindings to
specify how the atomic processes are connected, which is also similar to our
specification on how to connect two or more atomic services.

For the semantic descriptions of the atomic services in our conceptual model,
it is possible to use any of the existing approaches in the literature, such
as OWL-S or WSMO. We have included in our conceptual model the Name, Format
and Semantics fields that we have used in previous sections to motivate our
approach; however, this is a clear point of variability of our conceptual
model since, depending on the scenario, it is necessary to use different
semantics, and it could be suitable to use one specific approach to add
semantic annotations to the services.

To illustrate the use of our conceptual model, we present a sample
instantiation in Figure 7. In this instantiation, we have used OWL-S to model
the semantics of the input/output data. It corresponds to a part of the
composition of atomic services in Figure 5, specifically, how we transform
from the output data of the All query executor service to the input data of
the Wilcoxon’s signed-ranked test ranker service, which are represented as a
relational table and a CSV file, respectively. Note that the Relational to CSV
converter has access to the semantic descriptions of both the relational table
and the CSV file, which are used to perform the conversion between them.

##  7 Conclusions

In this paper, we presented a novel approach to service matchmaking and
composition to deal with the limitations imposed by current service discovery
practices. Our approach relies on representing services and user needs as
graphs, which are matched using approximate graph matching based on functional
graph summarization. The advocated approach expects to leverage developments
in 1) functional summarization of graphs based on well understood concepts, 2)
stratified graph matching based on functional summarization, 3) partial
service invocation in a service description graph, and 4) service stitching,
as we have outlined. The conceptual model we have introduced supports the
envisioned functionalities. While the research challenges introduced are
significant and ongoing, our thesis is that once these challenges are
addressed, we will be in a position to discover services in an unprecedented
manner, scale and at a more finer level to meet the challenges of emerging
applications in large scale data integration in the age of big data.

## References

  * [1] M. S. Amin, R. L. Finley, and H. M. Jamil.  Top-k similar graph matching using TraM in biological networks.  IEEE/ACM Trans. Comput. Biology Bioinform., 9(6):1790–1804, 2012\.
  * [2] M. Atay, A. Chebotko, D. Liu, S. Lu, and F. Fotouhi.  Efficient schema-based XML-to-relational data mapping.  Inf. Syst., 32(3):458–476, 2007.
  * [3] S. Auer, S. Dietzold, J. Lehmann, S. Hellmann, and D. Aumueller.  Triplify: light-weight linked data publication from relational databases.  In WWW, pages 621–630, 2009.
  * [4] A. Cuzzocrea and M. Fisichella.  Discovering semantic web services via advanced graph-based matching.  In SMC, pages 608–615, 2011.
  * [5] N.-Q. Doan, H. Azzag, and M. Lebbah.  Self-organizing map and tree topology for graph summarization.  In ICANN (2), pages 363–370, 2012.
  * [6] W.-S. Han, J. Lee, and J.-H. Lee.  Turbo${}_{\mbox{iso}}$: towards ultrafast and robust subgraph isomorphism search in large graph databases.  In SIGMOD Conference, pages 337–348, 2013.
  * [7] H. He and A. K. Singh.  Graphs-at-a-time: query language and access methods for graph databases.  In SIGMOD Conference, pages 405–418, 2008.
  * [8] M. Hollander and D. A. Wolfe.  Nonparametric Statistical Methods.  Wiley-Interscience, 1999.
  * [9] Z. Huma, C. Gerth, G. Engels, and O. Juwig.  A uml-based rich service description language for automatic service discovery of heterogeneous service partners.  In Forum at the 24${}^{\mbox{th}}$ International Conference on Advanced Information Systems Engineering, pages 90–97, 2012.
  * [10] M. Klusch, B. Fries, and K. P. Sycara.  OWLS-MX: A hybrid semantic web service matchmaker for OWL-S services.  J. Web Sem., 7(2):121–133, 2009.
  * [11] D. Koutra, U. Kang, J. Vreeken, and C. Faloutsos.  VOG: summarizing and understanding large graphs.  In SIAM International Conference on Data Mining, pages 91–99, 2014.
  * [12] U. Küster, B. König-Ries, M. Stern, and M. Klein.  DIANE: an integrated approach to automated service discovery, matchmaking and composition.  In WWW, pages 1033–1042, 2007.
  * [13] K. LeFevre and E. Terzi.  Grass: Graph structure summarization.  In SDM, pages 454–465, 2010.
  * [14] G. Liang and S. K. Lau.  Towards more flexible internal workflow change: Weakly equivalence concept for inter-organizational workflow design.  In 9th IEEE International Conference on E-Commerce Technology, pages 141–148, 2007.
  * [15] Z. Liu, J. X. Yu, and H. Cheng.  Approximate homogeneous graph summarization.  JIP, 20(1):77–88, 2012.
  * [16] H. Ma and H. Ren.  The new methods for constructing matching-equivalence graphs.  Discrete Mathematics, 307(1):125–131, 2007.
  * [17] S. Ma and J. Lee.  A graph-based approach to web service matchmaking.  In Asia-Pacific Software Engineering Conference, pages 796–801, 2012.
  * [18] D. L. Martin, M. H. Burstein, D. V. McDermott, S. A. McIlraith, M. Paolucci, K. P. Sycara, D. L. McGuinness, E. Sirin, and N. Srinivasan.  Bringing semantics to web services with OWL-S.  In World Wide Web, pages 243–277, 2007.
  * [19] A. V. Paliwal, B. Shafiq, J. Vaidya, H. Xiong, and N. R. Adam.  Semantics-based automated service discovery.  IEEE T. Services Computing, 5(2):260–275, 2012.
  * [20] J. Rao and X. Su.  A survey of automated web service composition methods.  In SWSWPC, pages 43–54, 2004.
  * [21] C. R. Rivero, I. Hernández, D. Ruiz, and R. Corchuelo.  Benchmarking data exchange among semantic-web ontologies.  IEEE Trans. Knowl. Data Eng., 25(9):1997–2009, 2013.
  * [22] C. R. Rivero and H. M. Jamil.  On isomorphic matching of large disk-resident graphs using an XQuery engine.  In ICDE Workshops, To be published, 2014.
  * [23] M. Shoaran, A. Thomo, and J. H. Weber-Jahnke.  Zero-knowledge private graph summarization.  In BigData Conference, pages 597–605, 2013.
  * [24] K. P. Sycara, M. Paolucci, A. Ankolekar, and N. Srinivasan.  Automated discovery, interaction and composition of semantic web services.  J. Web Sem., 1(1):27–46, 2003.
  * [25] Y. Tian and J. M. Patel.  TALE: A tool for approximate large graph matching.  In ICDE, pages 963–972, 2008.
  * [26] T. Vitvar, J. Kopecký, J. Viskova, and D. Fensel.  WSMO-lite annotations for web services.  In ESWC, pages 674–689, 2008.
  * [27] N. Zhang, Y. Tian, and J. M. Patel.  Discovery-driven graph summarization.  In ICDE, pages 880–891, 2010.
  * [28] S. Zhang, J. Yang, and W. Jin.  SAPPER: Subgraph indexing and approximate matching in large graphs.  PVLDB, 3(1):1185–1194, 2010.