[1]Adrien Noury

1]Laboratoire Charles Coulomb (L2C), Univ. Montpellier, CNRS, Montpellier,
France 2]Institute of Physics of Azerbaijan National Academy of Sciences,
Baku, Azerbaijan 3]Laboratoire Interdisciplinaire de Physique, Univ. Grenoble
Alpes & CNRS, Grenoble, France

# Quantifying the performances of SU-8 microfluidic devices: high liquid water
tightness, long-term stability, and vacuum compatibility

Said Pashayev  Romain Lhermerout  Christophe Roblin  Eric Alibert  Jerome
Barbat  Rudy Desgarceaux  Remi Jelinek  Edouard Chauveau  Saïd Tahir  Vincent
Jourdan  Rasim Jabbarov  Francois Henn<EMAIL_ADDRESS>[  [  [

###### Abstract

Despite several decades of development, microfluidics lacks a sealing material
that can be readily fabricated, leak-tight under high liquid water pressure,
stable over a long time, and vacuum compatible. In this paper, we report the
performances of a micro-scale processable sealing material for
nanofluidic/microfluidics chip fabrication, which enables us to achieve all
these requirements. We observed that micrometric walls made of SU-8
photoresist, whose thickness can be as low as 35 µm, exhibit water pressure
leak-tightness from 1.5 bar up to 5.5 bar, no water porosity even after 2
months of aging, and are able to sustain under $10^{-5}$ mbar vacuum. This
sealing material is therefore reliable and versatile for building microchips,
part of which must be isolated from liquid water under pressure or vacuum.
Moreover, the fabrication process we propose does not require the use of
aggressive chemicals or high-temperature or high-energy plasma treatment. It
thus opens a new perspective to seal microchips where delicate surfaces such
as nanomaterials are present.

##  1 Introduction

Sealing is one of the inevitable processes in micro and nanofluidic chip
fabrication. Ideally, low-temperature sealing methods are desirable to use
with sensitive materials and avoid the thermal expansion of substrates. Also
important is to achieve elevated burst pressure tightness, both for the
reliability of the device and to operate small channels with large fluidic
resistance. Additionally, microfluidics is gaining popularity for highly
sensitive mass measurements in liquid environments to weigh biomolecules,
single cells, etc. In this measurement, experiments are carried out in a
vacuum with microfluidic nanomechanical resonators [17, 31]. Therefore, low-
temperature bonding, high liquid water pressure leak-tight, vacuum compatible,
microscale processable material is requested.
Various methods are used in microfluidics such as plasma bonding [33], thermal
fusion [32], and anodic bonding [10], in order to seal conformal materials
like PDMS, non-conformal materials like plastics, or hard surfaces (e.g.
glass, silicon wafers). These materials and methods typically require at least
one of the following conditions: activation of the extremely clean surfaces,
and surface chemistry [30, 15]. So far, PDMS has been the most common material
in chip sealing. However, this material has several drawbacks such as the
adsorption of hydrophobic molecules, poor stability after surface treatment,
swelling by organic solvents, vapor water permeability, and breaking under
high-pressure operations [21, 27]. Moreover, sealing with PDMS requires
activating at least one of the surfaces, typically using O2 plasma. This can
limit its application because surface activation can damage any delicate
material used on the surfaces, such as nanomaterial [18].
Photoresists such as SU-8, when used as an adhesive material to bond hard
surfaces, might present better performances than PDMS while allowing bonding
substrates without surface activation or high temperature. Indeed, SU-8 is an
epoxy-based negative tone photoresist, developed by IBM in the mid-1990s, and
initially used as an inexpensive mold maker. Soon after it was used for the
fabrication of high aspect ratio MEMS [16] and later became a widely used
material in microfluidics, particularly for replica molding PDMS or other
polymers [12]. Interestingly, SU-8 being photosensitive allows forming of
patterns by photolithography with micrometric dimensions, very well suited for
microfluidics. SU-8 is also used as both a structural material and an
intermediate layer for adhesive bonding [24], exhibiting excellent physical
and optical properties, good chemical stability, and low porosity [22].
However, its leak-tightness while it is submitted to a liquid under pressure,
stability, and vacuum compatibility is still to be quantified. Furthermore,
SU-8 can be subject to outgassing, as reported from mass spectrometry and gas
chromatography techniques [19]. This clearly indicates that a hard bake is
needed to boost the cross-linking degree of the resin, to remove the remaining
initial constituents, and hence to provide the best performance when it has to
be used under vacuum.
Bonding strength measurements are mainly based on three methods: tensile
strength [8], burst pressure [6], and liquid leakage [1]. The bonding devices
where SU-8 was used as an adhesive material had been mainly tested with the
tensile strength method. It was reported that the bonding strength was in the
range of from 10 bar [2] up to 450 bar [29]. However, the tensile strength
method does not provide practical information on device performance in use
conditions. The most practical method to quantify the strength of the bonding
and assess the functionality of a microfluidic chip is the liquid burst
pressure test. The liquid burst pressure tightness of the SU-8-based devices
when it is used as an adhesive material has been reported as ranging from 1
bar [26] when bonding PDMS layers up to the highest 38 bar [14] when bonding
glass substrates. The durability of the so far reported SU-8-based device was
1-2 days [22]. In comparison, the performances of the PDMS-based devices were
reported with the tensile strength from 3.2 bar [5] up to 20 bar [11], with
the liquid burst pressure method from $\sim$2 bar [9] up to the highest 8.5
bar [11], when adhesion is enhanced by plasma pre-treatment of the surfaces
and the durability from 3 days [28] or the longest of 1 month [4].

To the best of our knowledge, the quantitative analysis of SU-8 microfluidic
device durability, ionic leakage, and water vapor leakage under vacuum has not
been reported.

In this work, we propose an easy and permanent sealing process to quantify the
bonding performance of the microfluid device when SU-8 is used as an adhesive
material to bond glass with silicon/silicon dioxide or quartz. The sample
fabrication and bonding require basic clean room facilities and low
temperatures. Since our goal is to develop the sealing process of microchips,
our investigation focuses on the search for the thinnest possible wall of SU-8
that can exhibit high-pressure tightness, high vacuum compatibility, and no
liquid water porosity over a long time. The latter criterion is checked using
an original and very sensitive method based on ionic conduction measurements.
The sealing method investigated here is non-destructive, reliable, versatile,
and does not require the use of aggressive chemicals, high temperatures, or
high-energy plasma treatment. It provides up to 5.5 bar liquid water burst
pressure leak-tightness, vacuum compatibility, and extremely low liquid
porosity over long times.

##  2 Materials and Methods

###  2.1 SU-8 patterning.

SU-8 preparation is performed in the cleanroom. Because of its improved
adhesion to glass (as specified by the manufacturer i.e., Kayaku -
MicroChem®), we employed SU-8-3025 instead of the more widely used SU-8-20xx
series. Optimal adhesion is obtained using Omnicoat (Kayaku - MicroChem®) as a
primer. A 4 mm thick glass substrate is used to fabricate SU-8 patterns.
First, it is milled to allow the subsequent placement of capillaries of 1.6 mm
diameter for the fluidic connection (Figure 1). In the case of ionic
conductivity measurements, two holes are additionally drilled to insert
Ag/AgCl electrodes (Figure 3). Surface cleanliness of the substrate is ensured
by Piranha cleaning (3:1 ratio H2SO4:H2O2). Then, Omnicoat primer is spin-
coated in 2 steps: first at 500 rpm for 5 s and then at 3000 rpm for 30 s and
baked at 200 °C for 2.5 minutes. The substrate is cooled down to 70 °C and a
few milliliters of SU-8 are poured all over the substrate. This temperature is
recommended in order to remove bubbles [20]. Once the reaction between the
Omnicoat primer and the SU-8 is complete, the substrate is cooled down to room
temperature and spin-coated in 2 steps: first at 500 rpm for 5 s and then at
2000 rpm for 30 s. The SU-8 coated substrate is then baked at 100 °C for 35
minutes and slowly cooled down to room temperature. The coating is exposed for
45 s to 365 nm UV photolithography, with a power density of 5.8 □ through a
photolithography mask. A second baking treatment at two different
temperatures, i.e., 70° C during 2.5 min and 100 °C during 6.5 min, is
applied, followed by slowly cooling down to room temperature. Finally, the
pattern of SU-8 is developed for 15 minutes in SU-8 Developer (Kayaku -
MicroChem®) and rinsed with isopropanol. The height of the so-obtained SU-8
pattern is 35 µm.

###  2.2 Device assembling, Bonding & Fluidic connections

The SU-8 pattern on the glass substrate is bonded on a Si/SiO2 wafer to form
the reservoirs to be tested. We used Si wafer with 90 nm SiO2 dry oxide. The
Si wafer was not treated with Omnicoat or any adhesion promotor. 2 mm thick
brass rectangular frames are placed on either side and maintained with 4
screws (Figure 1c). The influence of pressure applied on the SU-8 pattern is
assessed by observing optically the device (Figure S1). This crucial step is
strictly controlled to obtain homogeneity by observing
interferences/reflectivity with an optical microscope in order to ensure the
adhesion of the SU-8 wall on both the glass substrate and the wafer and to
avoid any deformation of the pattern. The last step of the process consists of
thermal treatment at 200 °C for 2 hours. It allows us to obtain surfaces that
are completely in contact with the SU-8 pattern (Figure S1c). Noteworthy,
during this baking step the thickness of the SU-8 layer extends compare to its
fabrication thickness from 20 µm to 35 µm, 30 µm to 50 µm, 60 µm to 85 µm, and
100 µm to 135 µm. Note that the frames are kept after bonding and during all
experiments reported here. After assembly, a capillary is inserted into the
milling area of the glass substrate and sealed with Stycast 2850FT epoxy glue.
The device is left at 65 °C for 2 hours in order to let the Stycast ensure
efficient sealing.

##  3 Results and discussion

###  3.1 Liquid water pressure tightness

Water pressure leak-tightness is visually assessed with an optical microscope,
change in the contrast/reflectivity indicates the presence of water outside of
the SU-8 reservoir. A schematic of the setup is shown in Figure 1a. Our
process allows us to build a SU-8 reservoir whose wall thickness is as small
as 35 µm. The pattern is designed on the glass substrate in order to form a
microfluidic reservoir. This reservoir is filled with water at a pressure
piloted by an Elveflow® OB1 MK3+ pressure controller. We tested SU-8 wall
thicknesses ranging from 135 µm down to 35 µm. The given two boundary
dimensions are set by our method of chip assembly. 135 µm is the maximum
compressible structure (given the large area of our device) that can be
assembled, while 35 µm is the minimum structure below which the SU-8 rolls
during assembly.

(a)

(b)

(c)

Figure 1: Liquid water pressure leak-tightness measurement setup. (a)
Schematic of the setup. A pressure controller allows applying water pressure
to the SU-8 reservoir. A binocular microscope is used for visual observation
of the material’s performance. (b) 3D artistic view of the device. (c)
Photography of the device with frames added to improve bonding of the
material, and capillary for fluidic connection to the pressure controller.

(a)

(b)

Figure 2: Liquid water burst pressure leak-tightness. (a) Liquid water burst
pressure distribution for 10 devices with 85 µm thick SU-8 wall. (b) Water
burst pressure distribution for various SU-8 wall thicknesses.

The burst pressure distribution measured for ten devices with 85 µm thick SU-8
walls is plotted in Figure 2. In Figure 2, we report the burst pressure
distribution obtained for various values of SU-8 wall thickness. The symbols
represent the mean, maximum, and minimum values of the burst pressure for each
corresponding SU-8 wall thickness. The device’s performance was measured for
each applied pressure over 1 hour. One of the main outcomes is that the water
pressure tightness does not depend on the SU-8 wall thickness. The absence of
a trend of leak-tightness versus width (Figure 2) is an indication that the
resistance to pressure is more governed by random imperfections of the surface
and dust rather than porosities. Another interesting feature of our SU-8
devices is that they can sustain pressures ranging from 1.5 bar up to 5.5 bar.
The defects during sample assembling might also explain the scattering
observed in Figure 2.

###  3.2 Liquid water Porosity, Ageing, and Vacuum compatibility

To test the liquid porosity of the SU-8 wall, we propose an original and
extremely sensitive method based on the measurement of ionic conduction
between two reservoirs filled with an electrolyte and separated by a SU-8
wall. Indeed, it can be assumed that if the wall exhibits percolating paths
through the entire thickness then an ionic current will be observed between
both reservoirs. Knowing that ionic currents as low as 1 pA were reported from
extremely small porosities such as carbon nanotubes ($\sim$ 1 nm) [34], it can
be assumed that in our case nanoporosity can be detected if a similar ionic
current measurement method is used.

Figure 3: Schematic of the setup designed to measure the ionic conductivity
between 2 micro-reservoirs filled with Milli-Q water or KCl electrolyte and
separated by a SU-8 wall.

For that purpose, patterns of SU-8 walls were designed with 2 reservoirs on
the glass substrate and assembled with an electrically insulating piece of
quartz in order to lower the ionic noise [7]. The ionic current is measured
via 2 Ag/AgCl electrodes placed in each micro reservoir and tightly sealed
with Stycast glue in order to avoid electrolyte leak (Figure 3).
Finally, the electrodes are connected to a high-impedance source-amplifier
(Keithley 2636B), which enables to the measurement of currents in the pA
range.

(a)

(b)

(c)

Figure 4: Ionic conductivity measurement between two micro-reservoirs filled
with either 300 mbar Milli-Q water or KCl electrolyte and separated by a SU-8
wall. (a) A typical example of a current/voltage plot obtained with a KCl
$10^{-3}$ M electrolyte and a SU-8 wall of $w$, $l$, $h$ equal to 85 µm, 10800
µm, 29 µm. (b) Log-log plot of the ionic conductivity versus KCl concentration
for two SU-8 walls with different thicknesses. The dashed line with a slope
equal to 1 represents the behavior expected for bulk ionic conductivity, i.e.,
Kolhrausch’s law (Equation 2). (c) Conductivity normalized by its initial
value as a function of time for SU-8 walls of 3 different thicknesses (KCl
concentration of 0.1 M).

First, blank measurement is carried out when both reservoirs are filled with
Milli-Q water© whose resistivity is very high, about 18 MΩ. Then, reservoirs
are filled with KCl electrolytes at various concentrations. The resistance R
of the SU8 wall is readily determined from the current/voltage plot which
follows Ohm’s law, as can be seen in Figure 4. Then the conductivity $\sigma$
of the wall is calculated using the following equation:

$\sigma=\frac{w}{Rlh}$ (1)

where $w$, $l$, and $h$ are the thickness, length, and height of the SU-8 wall
after baking respectively. The ionic conductivity of our set-up filled with
Milli-Q water is found to be about 1 µ and seems independent of the SU-8 wall
thickness (Figure 4). The dependence of the ionic conductivity with the ionic
concentration in the log-log scale is reported in Figure 4. We observe that
the conductance does not follow the Kohlrausch’s law for bulk conductivity of
diluted electrolytes, i.e.,

$\sigma=\sum_{i}\lambda_{i}C_{i}$ (2)

where λ$i$ and C$i$ are the molar conductivity and the concentration of the
solvated ion $i$ respectively. Indeed, the log-log dependence would match with
a straight line of slope 1 if Kohlrausch’s law was obeyed. The evolution
observed here for device S#1 ($w$=85 µm) is similar to the usual behavior
reported for ionic conductivity through nanopores, i.e., a power law
dependence of the ionic conductivity with the ionic concentration at low
concentration, with an exponent much lower than 1 or even as low as 0.14. We
also observe a flat slope for the conductivity of S#2 ($w$=50 µm) as a
function of the concentration. The fact that reducing dimension leads to the
absence of transport is an indication that transport occurs through
fabrication defects rather than porosities.
In addition, the comparison of the ionic conductivity obtained here with the
one reported for similar walls made of PDMS shows that the SU-8 resin is
similar or even less permeable to electrolytes and hence to water (Table S1).
The measurement of the ionic conductivity as a function of time (Figure 4)
shows that there is no significant aging effect over up to 16 weeks, while we
may expect a constant decrease or increase of the ionic conductivity if the
nanoporosity was closing or opening when it is filled with the electrolyte.
This shows that our SU-8 wall remains watertight for a longer period of time
than usually observed on micrometric walls made of other materials [13].

Finally, we assessed the ability of SU-8 to operate fluidics under a vacuum.
Noteworthy, it must be recalled that curing SU-8 at 200° C for 2 hours
significantly increases the reticulation rate of the resin, hence it is
essential to limit outgassing as much as possible [19]. The proposed set-up
used for this test is schematically drawn in Figure 5. It works on the
principle of the so-called pressure rising method in dynamic vacuum [25]. In
brief, the aim is to see an increase in the cell pressure while introducing
water inside the test reservoir. The pressure rise would indicate a leak. The
device as shown in Figure 1 is mounted inside a vacuum chamber under a
secondary vacuum, i.e., $5\times 10^{-5}$ mbar. First, we verify that the
presence of the SU-8 device does not significantly degrade the vacuum in the
cell. Then, the reservoir is filled with liquid water under pressure and the
change in the gauge level is recorded. It is observed that applying a pressure
of 1.5 bar on water for one hour does not induce any decrease of the vacuum
which remains constant at $5\times 10^{-5}$ mbar under pumping. This means
that the outgassing from SU-8 and the SU-8 porosity to water must be extremely
small.

Figure 5: Schematic of the vacuum setup. The device is mounted in the chamber
and SU-8 performance is tested with applying liquid water pressure under a
secondary vacuum

We now estimate the leak rate $Q_{leak}$ of particles, passing through our
SU-8 device into the cell: $Q_{leak}$=$P_{cell}$$\times$$D_{leak}$, with
$P_{cell}$ the pressure at the level of the cell (as measured with our Gauge)
and $D_{leak}$ the debit in volume at a given pressure, expressed in $L\cdot
s^{-1}$.
Since the pressure in the cell is not changing over the leak test, one can
write that the effective pumping speed at the level of the cell compensates
for the leak rate of our device and the outgassing from the cell:
$D_{leak}+D_{outgassing}=D_{cell}$. For the sake of simplicity, we will
estimate an upper bond of $D_{leak}$ by writing:

$D_{leak}\leq D_{cell}$ (3)

To compute $D_{cell}$, we recall that the flux of particles $Q$ is equal
everywhere (from the cell to the pump) an can be written as:

$Q=P_{cell}\times D_{cell}=P_{pump}\times D_{pump}=C(P_{cell}-P_{pump})$ (4)

Where $P_{cell}/P_{pump}$ and $D_{cell}/D_{pump}$ are respectively the
pressure and the debit in volume at the level of the cell/pump, $C$ is the
conductance of the circuit connecting the cell to the pump (pipes and valve).
From Equation 4, we can write:
$\frac{1}{C}+\frac{1}{D_{pump}}=\frac{1}{D_{cell}}$ it comes

$D_{cell}=C\frac{D_{pump}}{C+D_{pump}}$ (5)

$D_{pump}$ $\sim$ 85 $Ls^{-1}$ is obtained from the datasheet of our pump.
Because $D_{pump}$ is constant for pressures below $10^{-4}\,mbar$, we
approximate that $D_{pump}(P_{pump})$ $\sim$ $D_{pump}(P_{cell})$. We will see
in what follows that $D_{cell}$ is anyway dominated by $C$.
We now need to compute $C$, which is composed of 2 terms: $C_{pipes}$ and
$C_{valve}$. From the datasheet of our valve, $C_{valve}=160\,L\cdot s^{-1}$.
$C_{pipes}$ is given in the molecular regime by [3]
$C_{pipes}=\frac{d^{3}}{L}\sqrt{\frac{2\pi k_{B}T}{m_{N_{2}}}}$, thus:
$C_{pipes}=16.2\,L\cdot s^{-1}$ where $L=2.4\,m$ and $d=6\,cm$ are length and
diameter of the pipes respectively.
Finally, $\frac{1}{C}=\frac{1}{C_{pipes}}+\frac{1}{C_{valve}}$ and $C\sim$
$14.7\,L\cdot s^{-1}$.
Injecting in Equation 5 we get $D_{cell}$ $\sim$ $12.5\,Ls^{-1}$.
And finally, Equation 4 gives us $Q=P_{cell}\times D_{cell}$ $\sim$ $6.3\times
10^{-4}\pm 1.9\times 10^{-4}\,mbar\cdot L\cdot s^{-1}$, with the error bar
being set by resolution of the Gauge.
The calculated upper bond of the leak rate is better than the leak rate
corresponding to the water vapor leak tightness which is in the range of
$10^{-3}\,mbar\cdot L\cdot s^{-1}$ [23].

##  4 Conclusion

We reported that micrometric walls made of SU-8 resin with thicknesses as low
as 35 µm exhibit liquid water pressure leak tightness from 1.5 bar up to 5.5
bar and no porosity even after 2 months of aging. We also find that SU-8 can
be operated under a secondary vacuum as a microfluidic seal with no
degradation of the vacuum (neither outgassing of the SU-8 nor liquid water or
gas permeability). Moreover, the fabrication process we propose requires
neither aggressive chemical nor high temperature nor high energy plasma
treatment. It thus opens a new perspective to seal microchips when sensitive
surfaces or materials have to be used.

## Author Contributions

A.N, S.P., F.H. and R.L. conceived the experiment. S.P. fabricated the samples
with the help of J.B, E.C., S.T., R.J, R.D., R.L. and C.R. S.P. carried out
the experiment with inputs from V.J. and E.A. A.N., F.H. and R.J supervised
the work. All authors have read and agreed to the manuscript.

## Conflicts of interest

There are no conflicts of interest to declare.

## Acknowledgments

We acknowledge financial support from CNRS-MITI (France) through a ’Momentum’
grant. SP acknowledges support from ANAS (Azerbaijan) for the Ph.D.
scholarship. The work was partly supported by the French Renatech network. A
CC-BY public copyright license has been applied by the authors to the present
document and will be applied to all subsequent versions up to the Author
Accepted Manuscript arising from this submission, in accordance with the
grant’s open access conditions.

Supplementary information

## References

  *   * Abidin et al [2019] Abidin U, Daud NASM, Le Brun V (2019) Replication and leakage test of polydimethylsiloxane (pdms) microfluidics channel. AIP Conference Proceedings 2062(1):020064. 10.1063/1.5086611, URL https://aip.scitation.org/doi/abs/10.1063/1.5086611, https://aip.scitation.org/doi/pdf/10.1063/1.5086611
  * Admassu et al [2021] Admassu D, Durowade T, Gao W, et al (2021) Adhesive wafer bonding of micro-actuators with su-8 photoresist. Microsystem Technologies 27:3293–3297. 10.1007/s00542-020-05097-w, URL https://doi.org/10.1007/s00542-020-05097-w
  * Agilent Technologies [2022] Agilent Technologies I (2022) Vacuum and Leak Detection Reference Formulas, Properties, and Glossary. Agilent Technologies, Inc., USA, training Guide, Cat. No. 5994-5366EN
  * Baraket et al [2013] Baraket A, Zine N, Lee M, et al (2013) Development of a flexible microfluidic system based on a simple and reproducible sealing process between polymers and poly(dimethylsiloxane). Microelectronic Engineering 111:332–338. https://doi.org/10.1016/j.mee.2013.02.059, URL https://www.sciencedirect.com/science/article/pii/S0167931713001706
  * Bhattacharya et al [2005] Bhattacharya S, Datta A, Berg J, et al (2005) Studies on surface wettability of poly(dimethyl) siloxane (pdms) and glass under oxygen-plasma treatment and correlation with bond strength. Journal of Microelectromechanical Systems 14(3):590–597. 10.1109/JMEMS.2005.844746
  * Borók et al [2021] Borók A, Laboda K, Bonyár A (2021) Pdms bonding technologies for microfluidic applications: A review. Biosensors 11(8):292. 10.3390/bios11080292, URL http://dx.doi.org/10.3390/bios11080292
  * Bsawmaii et al [2023] Bsawmaii L, Delacou C, Meance S, et al (2023) In preparation. Unpublished
  * Chow et al [2004] Chow W, Lei K, Shi G, et al (2004) Micro fluidic channel fabrication by pdms-interface bonding. Proceedings of SPIE - The International Society for Optical Engineering 5275:141–148. 10.1117/12.532382
  * Gonzalez-Gallardo et al [2021] Gonzalez-Gallardo C, Díaz Díaz A, Casanova-Moreno J (2021) Improving plasma bonding of pdms to gold-patterned glass for electrochemical microfluidic applications. Microfluidics and Nanofluidics 25:20. 10.1007/s10404-021-02420-3, URL https://doi.org/10.1007/s10404-021-02420-3
  * Gray et al [1999] Gray B, Jaeggi D, Mourlas N, et al (1999) Novel interconnection technologies for integrated microfluidic systems. Sensors and Actuators A: Physical 77(1):57–65. https://doi.org/10.1016/S0924-4247(99)00185-5, URL https://www.sciencedirect.com/science/article/pii/S0924424799001855
  * Hammami et al [2022] Hammami S, Oseev A, Bargiel S, et al (2022) Microfluidics for high pressure: Integration on gaas acoustic biosensors with a leakage-free pdms based on bonding technology. Micromachines 13(5):755. 10.3390/mi13050755, URL https://doi.org/10.3390/mi13050755
  * Kamande et al [2015] Kamande JW, Wang Y, Taylor AM (2015) Cloning su8 silicon masters using epoxy resins to increase feature replicability and production for cell culture devices. Biomicrofluidics 9 3:036502
  * Klammer et al [2006] Klammer I, Hofmann MC, Buchenauer A, et al (2006) Long-term stability of pdms-based microfluidic systems used for biocatalytic reactions. Journal of Micromechanics and Microengineering 16(11):2425. 10.1088/0960-1317/16/11/025, URL https://dx.doi.org/10.1088/0960-1317/16/11/025
  * Lima et al [2013] Lima RS, Carneiro Leão PAG, Monteiro AM, et al (2013) Glass/su-8 microchip for electrokinetic applications. ELECTROPHORESIS 34(20-21):2996–3002. https://doi.org/10.1002/elps.201300167, URL https://analyticalsciencejournals.onlinelibrary.wiley.com/doi/abs/10.1002/elps.201300167, https://analyticalsciencejournals.onlinelibrary.wiley.com/doi/pdf/10.1002/elps.201300167
  * Liu et al [2021] Liu P, Lv Z, Sun B, et al (2021) A universal bonding method for preparation of microfluidic biosensor. Microfluidics and Nanofluidics 25
  * Lorenz et al [1997] Lorenz H, Despont M, Fahrni N, et al (1997) Su-8: a low-cost negative resist for mems. Journal of Micromechanics and Microengineering 7:121–124
  * Martín-Pérez et al [2019] Martín-Pérez A, Ramos D, Tamayo J, et al (2019) Real-time particle spectrometry in liquid environment using microfluidic-nanomechanical resonators. In: 20th International Conference on Solid-State Sensors, Actuators and Microsystems & Eurosensors, pp 2146–2149, 10.1109/TRANSDUCERS.2019.8808536
  * Mathur et al [2012] Mathur A, Roy S, Hazra K, et al (2012) Oxygen plasma assisted end-opening and field emission enhancement in vertically aligned multiwall carbon nanotubes. Materials Chemistry and Physics 134(1):425–429. https://doi.org/10.1016/j.matchemphys.2012.03.012, URL https://www.sciencedirect.com/science/article/pii/S0254058412002532
  * Melai et al [2009] Melai J, Salm C, Wolters R, et al (2009) Qualitative and quantitative characterization of outgassing from su-8. Microelectronic Engineering 86(4):761–764. https://doi.org/10.1016/j.mee.2008.11.008, URL https://www.sciencedirect.com/science/article/pii/S0167931708005248
  * MEMScyclopedia [1999] MEMScyclopedia (1999) Su-8: Thick photo-resist for mems. URL http://memscyclopedia.org/su8.html
  * Mukhopadhyay [2007] Mukhopadhyay R (2007) When pdms isn’t the best. Analytical Chemistry 79(9):3248–3253. 10.1021/ac071903e, URL https://doi.org/10.1021/ac071903e, https://doi.org/10.1021/ac071903e
  * Narayan et al [2018] Narayan S, Bae K, Lehn R, et al (2018) Low-pressure bonding of monolithic su-8 microfluidic devices. Journal of Micromechanics and Microengineering 28(12):125001. 10.1088/1361-6439/aae322, URL https://dx.doi.org/10.1088/1361-6439/aae322
  * Rottländer et al [2016] Rottländer H, Umrath W, Voss G (2016) Fundamentals of Leak Detection. Leybold Vacuum Products Division, Cologne, Germany, cat. No. 199 79_VA.02
  * Salvo et al [2012] Salvo P, Verplancke R, Bossuyt F, et al (2012) Adhesive bonding by su-8 transfer for assembling microfluidic devices. Microfluidics and Nanofluidics 13:987–991
  * Silverio et al [2022] Silverio V, Guha S, Keiser A, et al (2022) Overcoming technological barriers in microfluidics: Leakage testing. Frontiers in bioengineering and biotechnology 10:958582. 10.3389/fbioe.2022.958582
  * Sip and Folch [2010] Sip CG, Folch A (2010) Irreversible integration of su-8 microstructures into pdms devices
  * Sollier et al [2011] Sollier E, Murray C, Maoddi P, et al (2011) Rapid prototyping polymers for microfluidic devices and high pressure injections. Lab Chip 11:3752–3765. 10.1039/C1LC20514E, URL http://dx.doi.org/10.1039/C1LC20514E
  * Song et al [2018] Song K, Zhang H, Zhang W, et al (2018) Enhancement of the surface free energy of pdms for reversible and leakage-free bonding of pdms–ps microfluidic cell-culture systems. Microfluid Nanofluid 22:135. 10.1007/s10404-018-2152-3, URL https://doi.org/10.1007/s10404-018-2152-3
  * Steigert et al [2008] Steigert J, Brett O, Müller C, et al (2008) A versatile and flexible low-temperature full-wafer bonding process of monolithic 3d microfluidic structures in su-8. Journal of Micromechanics and Microengineering 18(9):095013. 10.1088/0960-1317/18/9/095013, URL https://dx.doi.org/10.1088/0960-1317/18/9/095013
  * Temiz et al [2015] Temiz Y, Lovchik RD, Kaigala GV, et al (2015) Lab-on-a-chip devices: How to close and plug the lab? Microelectronic Engineering 132:156–175. https://doi.org/10.1016/j.mee.2014.10.013, URL https://www.sciencedirect.com/science/article/pii/S0167931714004456
  * Thomas P. et al [2007] Thomas P. B, Michel G, Scott M. K, et al (2007) Weighing of biomolecules, single cells and single nanoparticles in fluid. Nature 446
  * Tsao and DeVoe [2009] Tsao CW, DeVoe DL (2009) Bonding of thermoplastic polymer microfluidics. Microfluidics and Nanofluidics 6:1–16
  * Xu et al [2013] Xu Y, Wang C, Li L, et al (2013) Bonding of glass nanofluidic chips at room temperature by a one-step surface activation using an o2/cf4 plasma treatment. Lab on a Chip 13:1048–1052. 10.1039/C3LC41345D, URL http://dx.doi.org/10.1039/C3LC41345D
  * Yazda et al [2017] Yazda K, Tahir S, Michel T, et al (2017) Voltage-activated transport of ions through single-walled carbon nanotubes. Nanoscale 9:11976–11986. 10.1039/C7NR02976D, URL http://dx.doi.org/10.1039/C7NR02976D


them within a width limit. The DD-BD approach proposed in the present paper,
on the other hand, can be applied to reduced DDs, and the separation of merged
nodes, if needed, will be performed naturally through the separation
operation. We illustrate this difference in the following example.

###### Example 7.1

Consider the final iteration of a BD algorithm with a master problem
$\max\\{z\,|\,\bm{x}\in\mathcal{P}\\}$ where
$\mathcal{P}\subseteq\mathbb{Z}^{n}$ is represented by DD $\mathcal{D}_{1}$ of
Figure 8(a). Assume that the following two optimality cuts are added

$\displaystyle z\leq 3x_{1}+2x_{2}$ (9a) $\displaystyle z\leq-3x_{1}-5x_{2}+3$
(9b)

It is clear that both points $(0,0)$ and $(1,0)$ give an optimal solution with
optimal value $z^{*}=0$. Since $\mathcal{D}_{1}$ is a reduced DD, the approach
of van der Linden (2017) cannot be directly applied to obtain the optimal
solution. It is suggested in that work that, when merging occurs, the
component-wise maximum of the reward tuple for merging nodes must be selected
as the reward tuple of the merged node. This operation guarantees that the
final reward value is an upper-bound for the optimal reward value. Applying
this operation here, however, creates an infinite loop without converging to a
solution, as demonstrated next. We record the reward value for inequalities
(9a) and (9b), respectively, in a tuple $(r^{1}(u),r^{2}(u))$ for each node
$u$. For the root node, we have the reward tuple $(0,3)$ according to
Algorithm 3. For the path including the 1-arc at the first layer, the reward
of the end-node is $(3,0)$. Similarly, the path including the 0-arc at the
first layer has the end-node reward $(0,3)$. The component-wise maximum yields
the reward of $(3,3)$ for the merged node in the middle. The reward at the
terminal node is $(3,3)$, giving the optimal value $\bar{z}=3$. While
$\bar{z}$ is an upper-bound for $z^{*}$, it can already be separated by the
current optimality cuts (9a) and (9b) for both feasible solutions. As a
result, the BD approach cannot refine it any further and is stuck at this
iteration.

For the DD-BD approach of Algorithm 1, we represent the master problem as
$\mathcal{M}=\max\\{z\,|\,\bm{x}\in\mathcal{P},z\in[-M,M]\\}$ where valid
bounds are imposed on $z$ variable. A restricted DD $\mathcal{D}_{2}$ can be
created for $\mathcal{M}$ using the equivalence class argument of Section 2.3
as given in Figure 8(b). Next, we may simply refine the DD through a
sequential separation with respect to optimality cuts (9a) and (9b), as shown
in Figures 9(a) and 9(b). It is easy to verify that a longest path in the
resulting DD gives either point $(0,0)$ or $(1,0)$ with the optimal value
$z^{*}=0$. Since these solutions give the optimal value of the problem,
Algorithm 1 is terminated due to bound pruning conditions in line 17.

(a) $\mathcal{D}_{1}$ without continuous variable

(b) $\mathcal{D}_{2}$ with continuous variable

Figure 8: DD representation of the master problem of Example 7.1

(a) Separation wrt (9a)

(b) Separation wrt (9b)

Figure 9: Separation of optimality cuts for the master problem of Example 7.1

We conclude this section by showing that the DD-BD approach of Algorithm 1 is
a generalization of the cost-tuple approach of Algorithm 3, since the latter
can be viewed as a special case of the former when the underlying DD is not
reduced.

###### Proposition 7.2

Consider the master problem $\max\\{z\,|\,\bm{x}\in\mathcal{P}\\}$ of a MIP
with a bounded $\mathcal{P}\subseteq\mathbb{Z}^{n}$, and let
$\mathcal{D}=(\mathcal{U},\mathcal{A},l(\cdot))$ be the DD representing
$\mathcal{P}$, with a property that each node (except the terminal) has a
unique incoming arc, and the terminal receives a unique arc from each node of
the previous layer. Let inequalities of the form
$z\leq\bm{\alpha}^{j}\bm{x}+\alpha_{0}^{j}$, for $j\in J$, represent the set
of optimality cuts to be added at the current iteration of the BD algorithm.
Define
$\bar{\mathcal{D}}=(\bar{\mathcal{U}},\bar{\mathcal{A}},\bar{l}(\cdot))$ to be
the DD constructed from $\mathcal{D}$ by adding a layer representing $z$
variable as the last arc layer. Then, the reward value obtained from Algorithm
3 applied to $\mathcal{D}$ is equal to the optimal value obtained from
Algorithm 1 when applied to $\bar{\mathcal{D}}$.

###### Proof 7.3

Proof. We first describe the relation between $\mathcal{D}$ and
$\bar{\mathcal{D}}$. All nodes and arcs from layer one to layer $n-1$ are
similar in both DDs, i.e., $\mathcal{A}_{i}=\bar{\mathcal{A}}_{i}$ for $i\in
N\setminus\\{n\\}$ and $\mathcal{U}_{i}=\bar{\mathcal{U}}_{i}$ for $i\in N$.
The difference is that $\bar{\mathcal{D}}$ has an extra layer that represents
$z$ variable. This layer is created as follows. For each node
$u\in\bar{\mathcal{U}}_{n}$, we create a node $v\in\bar{\mathcal{U}}_{n+1}$,
and connect them with an arc $a\in\bar{\mathcal{A}}_{n}$ with the same label
as the unique arc connecting the replica of node $u$ in $\mathcal{U}_{n}$ to
the terminal node of $\mathcal{D}$. Then, for each node
$v\in\bar{\mathcal{U}}_{n+1}$, we create two arcs with labels $-M$ and $M$ in
layer $\bar{\mathcal{A}}_{n+1}$ that connect $v$ to the terminal node in
$\bar{\mathcal{D}}$. These label values represent some valid lower and upper
bounds for variable $z$. According to Algorithm 1, $\bar{\mathcal{D}}$ is
refined with respect to the optimality cuts, and then the longest path is
found over the refined DD weighted by the objective function rates. To perform
the refinement, the solution set satisfying each optimality cut is modeled by
a DD called threshold diagram; see Bergman et al. (2016) for an exposure to
threshold diagrams. The last layer of such DDs corresponds to variable $z$ and
contains two arcs with labels representing a lower and upper bound for $z$.
Since for each node $v\in\bar{\mathcal{U}}_{n+1}$, there exists a unique arc-
specified path
$\mathrm{P}=(a_{1},\dotsc,a_{n})\in\bar{\mathcal{A}}_{1}\times\dotsc\times\bar{\mathcal{A}}_{n}$
from the root node to $v$, it follows from the assumption that the threshold
diagrams have the same structure as $\bar{\mathcal{D}}$, with the difference
that the upper bound label on arcs connecting $v$ to the terminal is computed
as $M^{j}(v)=\sum_{i=1}^{n}\alpha^{j}_{i}l_{a_{i}}+\alpha_{0}^{j}$ for each
optimality cut $j\in J$. As a result, refining $\bar{\mathcal{D}}$ with
respect to the optimality cuts reduces to intersecting label value intervals
associated with arcs at the last layer, which are of the form $[-M,M^{j}(v)]$
for each node $v\in\bar{\mathcal{U}}_{n+1}$. This intersection yields the
lower bound label $-M$, and the upper bound label $M(v)=\min_{j\in J}M^{j}(v)$
for pair of arcs connected to $v$ in the last layer of the refined DD. Note
that $M(v)$ is equal to $r(v)$ as computed in Algorithm 3. Finally, to find
the longest path on the refined $\bar{\mathcal{D}}$, all arcs in layers
$1$–$n$ are assigned zero weight and arcs in the last layer are assigned
weight 1 deduced from the objective function of the master problem. Therefore,
the length of the longest $r$-$t$ path in $\bar{\mathcal{D}}$ is computed as
$w^{*}=\max_{v\in\bar{\mathcal{U}}_{n+1}}M(v)$, which is equal to $r^{*}$
obtained from Algorithm 3. Since $\bar{\mathcal{D}}$ represents an exact DD
for the master problem and has been refined with respect to optimality cuts,
$w^{*}$ is returned as the output of Algorithm 1.


# Cross-Discourse and Multilingual Exploration of Textual Corpora with the
DualNeighbors Algorithm

Taylor Arnold
University of Richmond
Mathematics and Computer Science
28 Westhampton Way
Richmond, VA, USA
<EMAIL_ADDRESS>
&Lauren Tilton
University of Richmond
Rhetoric and Communication Studies
28 Westhampton Way
Richmond, VA, USA
<EMAIL_ADDRESS>

(20 June 2018)

###### Abstract

Word choice is dependent on the cultural context of writers and their
subjects. Different words are used to describe similar actions, objects, and
features based on factors such as class, race, gender, geography and political
affinity. Exploratory techniques based on locating and counting words may,
therefore, lead to conclusions that reinforce culturally inflected boundaries.
We offer a new method, the DualNeighbors algorithm, for linking thematically
similar documents both within and across discursive and linguistic barriers to
reveal cross-cultural connections. Qualitative and quantitative evaluations of
this technique are shown as applied to two cultural datasets of interest to
researchers across the humanities and social sciences. An open-source
implementation of the DualNeighbors algorithm is provided to assist in its
application.

##  1 Introduction

00footnotetext:  This work is licensed under a Creative Commons Attribution
4.0 International License. License details:
http://creativecommons.org/licenses/by/4.0/

Text analysis is aided by a wide range of tools and techniques for detecting
and locating themes and subjects. Key words in context (KWiC), for example, is
a method from corpus linguistics for extracting short snippets of text
containing a predefined set of words (Luhn, 1960; Gries, 2009). Systems for
full text queries have been implemented by institutions such as the Library of
Congress, the Social Science Research Network, and the Internet Archive
(Cheng, ). As demonstrated by the centrality of search engines to the
internet, word-based search algorithms are powerful tools for locating
relevant information within a large body of textual data.

Exploring a collection of materials by searching for words poses a potential
issue. Language is known to be highly dependent on the cultural factors that
shape both the writer and subject matter. As concisely described by Foucault
(1969), “We know perfectly well that we are not free to say just anything,
that we cannot simply speak of anything, when we like or where we like; not
just anyone, finally, may speak of just anything.” Searching through a corpus
by words and phrases reveals a particular discourse or sub-theme but can make
it challenging to identify a broader picture. Collections with multilingual
data pose an extreme form of this challenge, with the potential for important
portions of a large corpus to go without notice when using traditional search
techniques.

Table 1: Nearest neighbors of the English word “school” in a multilingual
embedding space.

Our works build off of recent research in word embeddings to provide a novel
exploratory recommender system that ensures recommendations can cut across
discursive and linguistic boundaries. We define two similarity measurements on
a corpus: one based on word usage and another based on multilingual word
embeddings. For any document in the corpus, our DualNeighbors algorithm
returns the nearest neighbors from each of these two similarity measurements.
Iteratively following recommendations through the corpus provides a coherent
way of understanding structures and patterns within the data.

The remainder of this article is organized as follows. In Section 2 we first
give a brief overview of prior work in the field of word embeddings,
recommender systems, and multilingual search. We then provide a concise
motivation and algorithmic description of the DualNeighbors algorithm in
Sections 3 and 4. Next, we qualitatively (Section 5) and quantitatively
(Section 6) assess the algorithm as applied to (i) a large collection of
captions from an iconic archive of American photography, and (ii) a collection
of multilingual Twitter news feeds. Finally, we conclude with a brief
description of the implementation of our algorithm.

##  2 Related Work

###  2.1 Word Embeddings

Given a lexicon of terms $L$, a word embedding is a function that maps each
term into a $p$-dimensional sequence of numbers (Mikolov et al., 2013b). The
embedding implicitly describes relationships between words, with similar terms
being projected into similar sequences of numbers (Goldberg and Levy, 2014).
Word embeddings are typically derived by placing them as the first layer of a
neural network and updating the embeddings by a supervised learning task
(Joulin et al., 2017). General purpose embeddings can be constructed by using
a generic training task, such as predicting a word as a function of its
neighbors, over a large corpus (Mikolov et al., 2013a). These embeddings can
be distributed and used as an input to other text processing tasks. For
example, the pre-trained fastText embeddings provide $300$-dimensional word
embeddings for $157$ languages (Grave et al., 2018).

While there is meaningful information in the distances between words in an
embedding space, there is no particular significance attached to each of its
dimensions. Recent work has drawn on this degree of freedom to show that two
independently trained word embeddings can be aligned by rotating one embedding
to match another. When two embeddings from different languages are aligned, by
way of matching a small set of manual translations, it is possible to embed a
multilingual lexicon into a common space (Smith et al., 2017). Table 1 shows
the nearest word neighbors to the English term ‘school’ in six different
languages. The closest neighbor in each language is an approximate translation
of the term; other neighbors include particular types of schools and different
word forms of the base term.

###  2.2 Word Embedding Recommendations

The ability of word embeddings to capture semantic similarities make them an
excellent choice for improving query and recommendation systems. The word
movers distance of Kusner et al. (2015) uses embeddings to describe a new
document similarity metric and Li et al. (2016) uses them to extend topic
models to corpora containing very short texts. Works by Ozsoy (2016) and
Manotumruksa et al. (2016) utilize word embeddings as additional features
within a larger supervised learning task. Others have, rather than using pre-
trained word embeddings, developed techniques for learning item embeddings
directly from a training corpus (Barkan and Koenigstein, 2016; Vasile et al.,
2016; Biswas et al., 2017).

Our approach most closely builds off of the query expansion techniques of
Zamani and Croft (2016) and De Boom et al. (2016). In both papers, the words
found in the source document are combined with other terms that are close
within the embedding space. Similarity metrics are then derived using standard
probabilistic and distance-based methods, respectively. Both methods are
evaluated by comparing the recommendations to observed user behavior.

###  2.3 Multilingual Cultural Heritage Data

Indexing and linking multilingual cultural heritage data is an important and
active area of research. Much of the prior work on this task has focused on
the use of semantic enrichment and linked open data, specifically through
named entity recognition (NER). Named entities are often written similarly
across languages, making them relatively easy points of reference to link
across multilingual datasets (Pappu et al., 2017). De Wilde et al. (2017)
recently developed MERCKX, a system for combining NER and DBpedia for the
semantic enrichment of multilingual archive records, built off of a
multilingual extension of DBpedia Spotlight (Daiber et al., 2013). To the best
of our knowledge, multilingual word embeddings have not been previously
adapted to the exploration of cultural heritage datasets.

##  3 Goal and Approach

Our goal is to define an algorithm that takes a starting document within a
corpus of texts and recommends a small set of thematically or stylistically
similar documents. One can apply this algorithm to a particular text of
interest, select one of the recommendations, and then re-apply the algorithm
to derive a new set of document suggestions. Following this process
iteratively yields a method for exploring and understanding a textual corpus.
Ideally, the collection of recommendations should be sufficiently diverse to
avoid getting stuck in a particular subset of the corpus.

Our approach to producing document recommendations, the DualNeighbors
algorithm, constructs two distinct similarity measurements over the corpus and
returns a fixed number of closest neighbors from each similarity method. The
first measurement uses a standard TF-IDF (term-frequency, inverse document
frequency) matrix along with cosine similarity. We call the nearest neighbors
from this set the word neighbors; these assure that the recommendations
include texts that are very similar and relevant to the starting document. In
the second metric we replace terms in the search document by their closest $M$
other terms within a word embedding space. The transformed document is again
compared to the rest of the corpus through TF-IDF and cosine similarity. The
resulting embedded neighbors allow for an increased degree of diversity and
connectivity within the set of recommendations. For example, using Table 1,
the embedding neighbors for a document using the term “school” could include
texts referencing a “university” or “kindergarten”.

The DualNeighbors algorithm features two crucial differences compared to other
word-embedding based query expansion techniques. Splitting the search
explicitly into two types of neighbors allows for a better balance between the
connectivity and diversity of the recommended documents. Also, replacing the
document with its closest word embeddings, rather than augmenting as other
approaches have done, significantly improves the diversity of the recommended
documents. Additionally, by varying the number of neighbors displayed by each
method, users can manually adjust the balance between diversity and relevance
in the results. The effect of these distinctive differences are evaluated in
Table 3 and Section 6.

##  4 The DualNeighbors Algorithm

Here, we provide a precise algorithmic formulation of the DualNeighbors
algorithm. We begin with a pre-determined lexicon $L$ of lemmatized word
forms. For simplicity of notation we will assume that words are tagged with
their language, so that the English word “fruit” and French word “fruit” are
distinct. Next, we take a (possibly multilingual) $p$-dimensional word
embedding function, as in Section 2.1. For a fixed neighborhood size $M$, we
can define the neighborhood function as a function $f$ that maps each term in
$L$ to a set of new terms in the lexicon by associating each word in $L$ with
its $M$ closest (Euclidiean) neighbors. The DualNeighbors algorithm is then
given by:

  1. 1.

Inputs: A textual corpus $C$, document index of interest $\tilde{i}$, a
lexicon $L$, word neighbor function $f$, and desired number word neighbors
$N_{w}$ and embedded neighbors $N_{e}$ to return.

  2. 2.

First, apply tokenization, lemmatization, and part-of-speech tagging models to
each element in the input corpus $C$. Filter the word forms to those found in
the set $L$. Then write the corpus $C$ as

$\displaystyle C$ $\displaystyle=\\{c_{i}\\}_{i=1}^{n},\quad
c_{i}=\\{w_{i,k_{i}}\\}_{k_{i}},\quad w_{i,k_{i}}\in L,\quad 1\leq
k_{i}\leq|L|$ (1)

  3. 3.

For each document $i$ and element $j$ in the lexicon, compute the $n\times|L|$
dimensional binary term frequency matrix $Y$ and TF-IDF matrix $X$ according
to

$\displaystyle Y_{i,j}$ $\displaystyle=\begin{cases}1,&l_{j}\in c_{i}\\\
0,&\text{else}\end{cases}$ $\displaystyle
X_{i,j}=Y_{i,j}\times\log\frac{n}{\sum_{i}Y_{i,j}}.$ (2)

  4. 4.

Simlarly, compute the embedded corpus $E$ as

$\displaystyle E$ $\displaystyle=\\{e_{i}\\},\quad
e_{i}=\bigcup_{k_{i}}f(w_{k_{i}}).$ (3)

Define the the embedded binary term frequency matrix $Y^{emb}$ and TF-IDF
matrix $X^{emb}$ as

$\displaystyle Y^{emb}_{i,j}$ $\displaystyle=\begin{cases}1,&l_{i}\in e_{i}\\\
0,&\text{else}\end{cases}$ $\displaystyle X^{emb}_{i,j}$
$\displaystyle=Y^{emb}_{i,j}\times\log\frac{n}{\sum_{i}Y_{i,j}}.$ (4)

  5. 5.

Compute the $n\times n$ document similarity matrices $S$ and $S^{emb}$ using
cosine similarity, for $i\neq i^{\prime}$, as

$\displaystyle S_{i,i^{\prime}}$
$\displaystyle=X_{i^{\prime}}X^{t}_{i}/\sqrt{X^{t}_{i}X_{i}}$ $\displaystyle
S^{emb}_{i,i^{\prime}}=X^{emb}_{i^{\prime}}X^{t}_{i}/\sqrt{X^{t}_{i}X_{i}},$
(5)

where $X_{i}$ is the $i$th row vector of the matrix $X$ and $S_{i,i}$ and
$S^{emb}_{i,i}$ are both set to zero.

  6. 6.

Output: The recommended documents associated with document $\tilde{i}$ are
given by:

$\displaystyle\texttt{TopN}\left(N_{w},S_{i,{\tilde{i}}}\right)\bigcup\texttt{TopN}\left(N_{e},S^{emb}_{i,{\tilde{i}}}\right)$
(6)

where $\texttt{TopN}(k,x)$ returns the indices of the largest $k$ values of
$x$.

In practice, we typically start with Step 2 of the algorithm to determine an
appropriate lexicon $L$ and cache the similarity matrices $S$ and $S^{emb}$
for the next query. In implementation and examples, the multilingual fastText
word embeddings of (Grave et al., 2018) used. Details of the implementation of
the algorithm are given in Section 7.

Figure 1: Example visualization of the DualNeighbors algorithm. Item 1 is the
starting point, items 2-4 are the first three word neighbors, and 5-8 are the
first four embedding neighbors.

##  5 Qualitative Evaluation

Caption |  Top-3 Word Neighbors |  Top-3 Embedding Neighbors
---|---|---
Grading and bunching carrots in the field. Yuma County, Arizona |  $\bullet$ Bunching carrots in the field. Yuma County, Arizona |  $\bullet$ Roadside display of pumpkins and turnips and other vegetables near Berlin, Connecticut
|  $\bullet$ Bunching carrots. Imperial County, California |  $\bullet$ Hartford, Connecticut… Mrs. Komorosky picking cucumbers
|  $\bullet$ Bunching carrots, Edinburg, Texas |  $\bullet$ Pumpkins and turnips near Berlin, Connecticut
Brownsville, TX. Charro Days fiesta. Children. |  $\bullet$ Brownsville, Texas. Charro Days fiesta. |  $\bullet$ Picnic lunch at May Day-Health Day festivities…
|  $\bullet$ Visitor to Taos fiesta, New Mexico |  $\bullet$ Spectators at childrens races, Labor Day celebration …
|  $\bullet$ Bingo at fiesta, Taos, New Mexico |  $\bullet$ Detroit, Michigan. Child in toddler go-cart
Imperial Brands shareholders revolt over CEO’s pay rise |  $\bullet$ Evening Standard urged to declare Osborne’s job with Uber shareholder |  $\bullet$ Bruno Le Maire à Wall Street pour attirer les investisseurs …
|  $\bullet$ Uber CEO Travis Kalanick should have gone years ago |  $\bullet$ Pierre Bergé : Le Monde perd l’un de ses actionnaires
|  $\bullet$ £37bn paid to shareholders should have been invested |  $\bullet$ Le pacte d’actionnaires de STX France en question
Cannes 2017: Eva Green and Joaquin Phoenix on |  $\bullet$ Five looks to know about from the SAG red carpet |  $\bullet$ Festival de Cannes 2017: Bella Hadid, rouge écarlate sur le tapis
the red carpet |  $\bullet$ Baftas 2017: the best of the red carpet fashion |  $\bullet$ À New York, tapis rouge pour Kermit la grenouille
|  $\bullet$ Emmys 2016 fashion: the best looks on the red carpet |  $\bullet$ Sur tapis rouge
Table 2: Two FSA-OWI captions and two tweets from the Guardian versus Le
Figaro corpora along with the top-3 word and embedding neighbors.

###  5.1 FSA-OWI Captions

Our first example applies the DualNeighbors algorithm to a corpus of captions
attached to approximately ninety thousand photographs taken between 1935 and
1943 by the U.S. Federal Government through the Farm Security Administration
and Office of War Information (Baldwin, 1968). The collection remains one of
the most historically important archives of American photography
(Trachtenberg, 1990). The majority of captions consist of a short sentence
describing the scene captured by the photographer. Photographic captions
mostly come from notes taken by individual photographers; the style and
lexicon is substantially variable across the corpus.

An example of the connections this method gives are shown in Table 2. For
example, the word neighbors of the caption about the farming of carrots
consists of other captions related to carrots. The embedding neighbors link to
captions describing other vegetables, including pumpkins, cucumbers and
turnips. Because of the correlation between crop types and geography, the
embedding neighbors allow the search to extend beyond the U.S. South into the
Northeast. Similarly, the caption about fiestas (a Spanish term often used to
describe events in Hispanic/Latino communities) becomes linked to similar
festivals in other locations by way of its embedding neighbors. By also
including a set of word neighbors, we additionally see other examples of
events within various communities across the Southwestern U.S..

Figure 1 shows the images along with the captions for a particular starting
document. In the first row, the word neighbors show depictions of two older
African American midwives, one in rural Georgia by Jack Delano in 1941 and
another by Marion Post Walcott in 1939. The second row contains captions and
images of embedding neighbors. Among these are two Fritz Henle photographs of
white nurses training to assist with an appendectomy, taken in New York City
in 1943. These show the practice of medicine in the U.S. from two different
perspectives. Using only straightforward TF-IDF methods, there would otherwise
have been no obvious link between these two groups of images. The two sets
were taken over a year apart by different photographers in different cities.
None of the key terms in the two captions match each other. It would be
difficult for a researcher looking at either photograph to stumble on the
other photograph without sifting through tens of thousands of images. The
embedding neighbors solves this problem by linking the two related but
distinct terms used to describe the scenes. Both rows together reveal the wide
scope of the FSA-OWI corpus and the broad mandate given to the photographers.
The DualNeighbors algorithm, therefore, illuminates connections that would be
hidden by previous word-based search and recommender systems.

###  5.2 News Twitter Reports

Our second corpus is taken from Twitter, consisting of tweets by news
organizations in the year 2017 (Littman et al., 2017). We compare the center-
left British daily newspaper The Guardian and the center-right daily French
newspaper Le Figaro. Twenty thousand tweets were randomly selected from each
newspaper, after removing retweets and anything whose content was empty after
removing hashtags and links. We used a French parser and word embedding to
work with the data from Le Figaro and an English parser and embedding to
process The Guardian headlines (Straka et al., 2016).

|  |  | FSA-OWI | Twitter
---|---|---|---|---
| $N_{w}$ | $N_{e}$ | $\lambda_{2}$ | u.c. | dist | $d_{0.9}^{in}$ | $\text{ego}_{0.1}$ | $\lambda_{2}$ | u.c. | dist | $d_{0.9}^{in}$ | $\text{ego}^{(3)}_{0.1}$
| 12 | 0 | 0.002 | 25.1% | 9.8 | 27 | 17 | $\cdot$ | 57.6% | 7.3 | 25 | 16
Q. Replacement | 11 | 1 | 0.011 | 15.7% | 8.4 | 26 | 77 | 0.028 | 11.1% | 7.3 | 26 | 84
10 | 2 | 0.023 | 15.5% | 8.1 | 25 | 124 | 0.046 | 11.0% | 7.2 | 27 | 110
9 | 3 | 0.038 | 16.3% | 7.9 | 24 | 158 | 0.056 | 12.2% | 7.1 | 28 | 129
8 | 4 | 0.047 | 17.8% | 7.8 | 23 | 189 | 0.070 | 14.6% | 7.0 | 29 | 134
7 | 5 | 0.056 | 20.4% | 7.8 | 22 | 217 | 0.077 | 17.0% | 7.0 | 29 | 139
6 | 6 | 0.061 | 23.8% | 7.8 | 20 | 238 | 0.085 | 20.6% | 7.0 | 30 | 137
Q. Expansion | 11 | 1 | 0.002 | 26.8% | 9.2 | 26 | 50 | 0.028 | 21.0% | 8.2 | 25 | 61
10 | 2 | 0.002 | 31.7% | 9.3 | 25 | 53 | 0.024 | 31.7% | 8.9 | 25 | 68
9 | 3 | 0.002 | 35.5% | 9.6 | 24 | 56 | 0.020 | 42.5% | 10.2 | 26 | 65
8 | 4 | 0.002 | 40.8% | 9.8 | 22 | 59 | 0.010 | 54.2% | 15.8 | 26 | 61
7 | 5 | 0.003 | 47.0% | 10.8 | 21 | 62 | 0.013 | 59.9% | 2.3 | 26 | 56
6 | 6 | 0.004 | 52.9% | 10.4 | 20 | 64 | 0.014 | 60.3% | 1.5 | 25 | 51
Table 3: Connectivity metrics for similarity graphs. All examples relate each
item to twelve neighbors, with $N_{w}$ word neighbors and $N_{e}$ embedding
neighbors. For comparison, we show the results using both query replacement
(as described in the DualNeighbors algorithm) and with the query expansion
method suggested in the papers discussed in Section 2.2. The metrics give the
(undirected) spectral gap $\lambda_{2}$, the proportion of directed pairs of
items that are unconnected across directed edges (u.c.), the average distance
(dist) between connected pairs of items, the 90th percentile of the in-degree
($d_{0.9}^{in}$), and the 10th percentile of the number of neighbors within
three links ($\text{ego}^{(3)}_{0.1}$).

In Table 2 we see two examples of the word and embedding nearest neighbors.
The first tweet shows how the English word “shareholders” is linked both to
its closest direct translation (“actionnaires”) as well as the more generic
“investisseur”. In the next example the embedding links the search term to its
most direct translation. “Red carpet” becomes “tapis rouge”. Once translated,
we see that the themes linked to by both newspapers are similar, illustrating
the algorithm’s ability to traverse linguistic boundaries within a corpus.
Joining headlines across these two newspapers, and by extension the longer
articles linked to in each tweet, makes it possible to compare the coverage of
similar events across national, linguistic, and ideological boundaries. The
connections shown in these two examples were only found through the use of the
implicit translations given by the multilingual word embeddings as implemented
in the DualNeighbors algorithm.

##  6 Quantitative Evaluation

###  6.1 Connectivity

We can study the set of recommendations given by our algorithm as a network
structure between documents in a corpus. This is useful because there are many
established metrics measuring the degree of connectivity within a given
network. We will use five metrics to understand the network structure induced
by our algorithm: (i) the algebraic connectivity, a measurement of whether the
network has any bottlenecks (Fiedler, 1973), (ii) the proportion of document
pairs that can be reached using edges, (iii) the average minimum distance
between connected pairs of documents, (iv) the distribution of in-degrees, the
number of other documents linking into a given document (Even and Tarjan,
1975), and (v) the distribution of third-degree ego scores, the number of
documents that can be reached by moving along three or fewer edges (Everett
and Borgatti, 2005). The algebraic connectivity is defined over an undirected
network; the other metrics take the direction of the edge into account.

Table 3 shows the five connectivity metrics for various choices of $N_{w}$ and
$N_{e}$. All of the examples use a total of $12$ recommendations for
consistency. Generally, we see that adding more edges from the (query
expansion) word embedding matrix produces a network with a larger algebraic
connectivity, lower average distance between document pairs, and larger third-
degree ego scores. The distribution of in-degrees becomes increasingly
variable, however, as more edges get mapped to a small set of hubs (documents
linked to from a very large number of other documents). These two effects
combine so that the most connected network using both corpora have $10$ edges
from word similarities and $2$ edges from the word embedding logic. Generally,
including at least one word embedding edges makes the network significantly
more connected. The hubness of the network slowly becomes an issue as the
proportion of embedding edges grows relative to the total number of edges.

To illustrate the importance of using query replacement in the word embedding
neighbor function, the table also compares our approach (query replacement) to
that of query expansion. That is, what happens if we retain the original term
in the embedding neighbor function $f$, as used in Equation 3, rather than
replacing it. Table 3 shows that the query replacement approach of the
DualNeighbors algorithm provides a greater degree of connectivity across all
five metrics and any number of embedding neighbors $N_{e}$. Therefore, this
modification serves as an important contribution and distinguishing feature of
our approach.

###  6.2 Relevance

It is far more difficult to quantitatively assess how relevant the
recommendations made by our algorithm are to the starting document. The degree
to which an item is relevant is subjective. Also, our goal is to find links
across the corpus that share thematic similarities but also cut across
languages and discourses, so a perfect degree of similarity between
recommendations is not necessarily ideal. In order to make a quantitative
assessment of relevancy, we constructed a dataset of $3,000$ randomly
collected links between documents from each of our two corpora. We hand-
labelled whether or not the link appeared to be ‘valid’. This was done
according to whether the links between any of the terms used to link the two
texts together used the terms in the same word sense. For example, we flagged
as an invalid connection a link between the word “scab” used to describe a
skin disease and “scab” as a synonym for strikebreaker. While a link being
‘valid’ does not guarantee that there will be an interesting connection
between two documents, it does give a relatively unambiguous way of measuring
whether the links found are erroneous or potentially interesting.

| FSA-OWI | Twitter
---|---|---
Pos. | TF-IDF | Emb. | TF-IDF | Emb.
1-3 | 0.88% | 2.66% | 6.34% | 9.52%
4-8 | 1.27% | 2.54% | 9.09% | 10.32%
9-12 | 5.17% | 3.16% | 9.40% | 13.55%
Table 4: Taking a random sample of 3000 links from each corpus, the proportion
of links between terms that were hand-coded as ‘invalid’ organized by corpus,
neighbor type, and the position of the link in the list of edges. See Section
6.2 for the methodology used to determine validity.

The results of our hand-tagged dataset are given in Table 4, with the
proportion of invalid links grouped by corpus, edge type, and the position of
the edge within the list of possible nearest neighbors. Overall, we see that
the proportion of valid embedding neighbors is nearly as high as the word
neighbors across both corpora and the number of selected neighbors. This is
impressive because there are many more ways that the word embedding neighbors
can lead to invalid results. The results of Table 4 illustrate, however, that
the embedding neighbors tend to find valid links that use both the source and
target words in the same word sense. This is strong evidence that the
DualNeighbors algorithm increases the connectivity of the recommendations
through meaningful cross-discursive and multilingual links across a corpus.

##  7 Implementation

To facilitate the usage of our method in the exploration of textual data, we
provide an open-source implementation of the algorithm in the R package
cdexplo.111The package can be downloaded and installed from
https://github.com/statsmaths/cdexplo The package takes raw text as an input
and produces an interactive website that can be used locally on a user’s
computer; it therefore requires only minimal knowledge of the R programming
language. For example, if a corpus is stored as a CSV file with the text in
the first column, we can run the following code to apply the algorithm with
$N_{w}$ equal to $10$ and $N_{e}$ equal to $2$:

library(cdexplo)data <\- read.csv("input.csv")anno <\- cde_annotate(data)link
<\- cde_dual_neigh(anno, nw = 10, ne = 2)cde_make_page(link,
"output_location")The source language and presence of metadata, including
possible image URLs, will be automatically determined from the input, but can
also be manually specified. The image in Figure 1 is a screen-shot from the
output of the package applied to the FSA-OWI caption corpus.

##  8 Conclusions

We have derived the DualNeighbors algorithm to assist in the exploration of
textual datasets. Qualitative and quantitative analyses have illustrated how
the algorithm cuts across linguistic boundaries and improves the connectivity
of the recommendation algorithm without a significant decrease to the
relevancy of the returned results.

Language is impacted by cultural factors surrounding the writer and their
subject. Syntactic and lexical choices serve as strong signals of class, race,
education, and gender. The ability to connect and transcend the boundaries
constructed by language while exploring textural data offers a powerful new
approach to the study of cultural datasets. Our open-source implementation
assists in the application of the DualNeighbors approach to new corpora.
Furthermore, the computed recommendations can be directly adapted as a
recommendation algorithm for digital public projects, allowing the exploratory
benefits afforded by our technique to be available to a wider audience.

One avenue for extending the DualNeighbors algorithm is to further refine the
process of constructing a lexicon and corresponding word embedding. Most of
the errors we detected in the experiment in Section 6.2 were the result of
proper nouns and noun phrases that do not make sense when embedding each
individual word. Recent work has shown that better pre-processing can
alleviate some of these difficulties Trask et al. (2015). We also noticed,
particularly over the jargon-heavy Twitter news corpus, that many key phrases
were missing from our embedding mapping. Research on sub-word Bojanowski et
al. (2017) and character level embeddings Santos and Zadrozny (2014); Zhang et
al. (2015) could be used to address terms that are outside of the specified
lexicon.

## Acknowledgements

We thank an anonymous reviewer whose comments suggested an additional
motivation for our work. These suggestions have been incorporated into the
final version of the paper.

## References

  * Baldwin (1968) Sidney Baldwin. 1968.  Poverty and politics; the rise and decline of the farm security administration.
  * Barkan and Koenigstein (2016) Oren Barkan and Noam Koenigstein. 2016.  Item2vec: neural item embedding for collaborative filtering.  In _Machine Learning for Signal Processing (MLSP), 2016 IEEE 26th International Workshop on_ , pages 1–6. IEEE.
  * Biswas et al. (2017) Arijit Biswas, Mukul Bhutani, and Subhajit Sanyal. 2017.  Mrnet-product2vec: A multi-task recurrent neural network for product embeddings.  In _Joint European Conference on Machine Learning and Knowledge Discovery in Databases_ , pages 153–165. Springer.
  * Bojanowski et al. (2017) Piotr Bojanowski, Edouard Grave, Armand Joulin, and Tomas Mikolov. 2017.  Enriching word vectors with subword information.  _Transactions of the Association for Computational Linguistics_ , 5:135–146.
  * (5) Brenton Cheng.  Searching through everything.  _Internet Archive Blog_ , (26 October 2016).
  * Daiber et al. (2013) Joachim Daiber, Max Jakob, Chris Hokamp, and Pablo N Mendes. 2013.  Improving efficiency and accuracy in multilingual entity extraction.  In _Proceedings of the 9th International Conference on Semantic Systems_ , pages 121–124. ACM.
  * De Boom et al. (2016) Cedric De Boom, Steven Van Canneyt, Thomas Demeester, and Bart Dhoedt. 2016.  Representation learning for very short texts using weighted word embedding aggregation.  _Pattern Recognition Letters_ , 80:150–156.
  * De Wilde et al. (2017) Max De Wilde, Simon Hengchen, et al. 2017.  Semantic enrichment of a multilingual archive with linked open data.  _Digital Humanities Quarterly_.
  * Even and Tarjan (1975) Shimon Even and R Endre Tarjan. 1975.  Network flow and testing graph connectivity.  _SIAM journal on computing_ , 4(4):507–518.
  * Everett and Borgatti (2005) Martin Everett and Stephen P Borgatti. 2005.  Ego network betweenness.  _Social networks_ , 27(1):31–38.
  * Fiedler (1973) Miroslav Fiedler. 1973.  Algebraic connectivity of graphs.  _Czechoslovak mathematical journal_ , 23(2):298–305.
  * Foucault (1969) Michel Foucault. 1969.  _L’archéologie du savoir_.  Gallimard, Paris, France.
  * Goldberg and Levy (2014) Yoav Goldberg and Omer Levy. 2014.  word2vec explained: Deriving mikolov et al.’s negative-sampling word-embedding method.  _arXiv preprint arXiv:1402.3722_.
  * Grave et al. (2018) Edouard Grave, Piotr Bojanowski, Prakhar Gupta, Armand Joulin, and Tomas Mikolov. 2018.  Learning word vectors for 157 languages.  In _Proceedings of the International Conference on Language Resources and Evaluation (LREC 2018)_.
  * Gries (2009) Stefan Th Gries. 2009.  _Quantitative corpus linguistics with R: A practical introduction_.  Routledge, London, England.
  * Joulin et al. (2017) Armand Joulin, Edouard Grave, Piotr Bojanowski, and Tomas Mikolov. 2017.  Bag of tricks for efficient text classification.  In _Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 2, Short Papers_ , pages 427–431. Association for Computational Linguistics.
  * Kusner et al. (2015) Matt Kusner, Yu Sun, Nicholas Kolkin, and Kilian Weinberger. 2015.  From word embeddings to document distances.  In _International Conference on Machine Learning_ , pages 957–966.
  * Li et al. (2016) Chenliang Li, Haoran Wang, Zhiqian Zhang, Aixin Sun, and Zongyang Ma. 2016.  Topic modeling for short texts with auxiliary word embeddings.  In _Proceedings of the 39th International ACM SIGIR conference on Research and Development in Information Retrieval_ , pages 165–174. ACM.
  * Littman et al. (2017) Justin Littman, Laura Wrubel, Daniel Kerchner, and Yonah Bromberg Gaber. 2017.  News outlet tweet ids.
  * Luhn (1960) Hans Peter Luhn. 1960.  Key word-in-context index for technical literature (kwic index).  _Journal of the Association for Information Science and Technology_ , 11(4):288–295.
  * Manotumruksa et al. (2016) Jarana Manotumruksa, Craig Macdonald, and Iadh Ounis. 2016.  Modelling user preferences using word embeddings for context-aware venue recommendation.  _arXiv preprint arXiv:1606.07828_.
  * Mikolov et al. (2013a) Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. 2013a.  Efficient estimation of word representations in vector space.  _arXiv preprint arXiv:1301.3781_.
  * Mikolov et al. (2013b) Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. 2013b.  Distributed representations of words and phrases and their compositionality.  In _Advances in neural information processing systems_ , pages 3111–3119.
  * Ozsoy (2016) Makbule Gulcin Ozsoy. 2016.  From word embeddings to item recommendation.  _arXiv preprint arXiv:1601.01356_.
  * Pappu et al. (2017) Aasish Pappu, Roi Blanco, Yashar Mehdad, Amanda Stent, and Kapil Thadani. 2017.  Lightweight multilingual entity extraction and linking.  In _Proceedings of the Tenth ACM International Conference on Web Search and Data Mining_ , pages 365–374. ACM.
  * Santos and Zadrozny (2014) Cicero D Santos and Bianca Zadrozny. 2014.  Learning character-level representations for part-of-speech tagging.  In _Proceedings of the 31st International Conference on Machine Learning (ICML-14)_ , pages 1818–1826.
  * Smith et al. (2017) Samuel L Smith, David HP Turban, Steven Hamblin, and Nils Y Hammerla. 2017.  Offline bilingual word vectors, orthogonal transformations and the inverted softmax.  _arXiv preprint arXiv:1702.03859_.
  * Straka et al. (2016) Milan Straka, Jan Hajic, and Jana Straková. 2016.  Udpipe: Trainable pipeline for processing conll-u files performing tokenization, morphological analysis, pos tagging and parsing.  In _LREC_.
  * Trachtenberg (1990) Alan Trachtenberg. 1990.  _Reading American Photographs: Images as History-Mathew Brady to Walker Evans_.  Macmillan, London, England.
  * Trask et al. (2015) Andrew Trask, Phil Michalak, and John Liu. 2015.  sense2vec-a fast and accurate method for word sense disambiguation in neural word embeddings.  _arXiv preprint arXiv:1511.06388_.
  * Vasile et al. (2016) Flavian Vasile, Elena Smirnova, and Alexis Conneau. 2016.  Meta-prod2vec: Product embeddings using side-information for recommendation.  In _Proceedings of the 10th ACM Conference on Recommender Systems_ , pages 225–232. ACM.
  * Zamani and Croft (2016) Hamed Zamani and W Bruce Croft. 2016.  Estimating embedding vectors for queries.  In _Proceedings of the 2016 ACM International Conference on the Theory of Information Retrieval_ , pages 123–132. ACM.
  * Zhang et al. (2015) Xiang Zhang, Junbo Zhao, and Yann LeCun. 2015.  Character-level convolutional networks for text classification.  In _Advances in neural information processing systems_ , pages 649–657.


* [21] Ramesh Hariharan, Telikepalli Kavitha, and Debmalya Panigrahi.  Efficient algorithms for computing all low _s-t_ edge connectivities and related problems.  In Symposium on Discrete Algorithms (SODA), pages 127–136. SIAM, 2007.  URL: http://dl.acm.org/citation.cfm?id=1283383.1283398.
  * [22] John E. Hopcroft and Robert Endre Tarjan.  Dividing a graph into triconnected components.  SIAM J. Comput., 2(3):135–158, 1973.  doi:10.1137/0202012.
  * [23] Wenyu Jin and Xiaorui Sun.  Fully dynamic s-t edge connectivity in subpolynomial time (extended abstract).  In Annual Symposium on Foundations of Computer Science FOCS, pages 861–872. IEEE, 2021.  doi:10.1109/FOCS52979.2021.00088.
  * [24] Wojciech Nadara, Mateusz Radecki, Marcin Smulewicz, and Marek Sokolowski.  Determining 4-edge-connected components in linear time.  In European Symposium on Algorithms (ESA), volume 204 of LIPIcs, pages 71:1–71:15, 2021.  doi:10.4230/LIPIcs.ESA.2021.71.
  * [25] Hiroshi Nagamochi and Toshihide Ibaraki.  Algorithmic Aspects of Graph Connectivity, volume 123 of Encyclopedia of Mathematics and its Applications.  Cambridge University Press, 2008.  doi:10.1017/CBO9780511721649.
  * [26] Mihai Pătraşcu and Mikkel Thorup.  Planning for fast connectivity updates.  In Symposium on Foundations of Computer Science (FOCS), pages 263–271. IEEE Computer Society, 2007.  doi:10.1109/FOCS.2007.54.
  * [27] Seth Pettie, Thatchaphol Saranurak, and Longhui Yin.  Optimal vertex connectivity oracles.  In ACM SIGACT Symposium on Theory of Computing (STOC), pages 151–161. ACM, 2022.  doi:10.1145/3519935.3519945.
  * [28] Johannes A. La Poutré.  Maintenance of 2- and 3-edge-connected components of graphs II.  SIAM J. Comput., 29(5):1521–1549, 2000.  doi:10.1137/S0097539793257770.
  * [29] Johannes A. La Poutré, Jan van Leeuwen, and Mark H. Overmars.  Maintenance of 2- and 3-edge- connected components of graphs I.  Discret. Math., 114(1-3):329–359, 1993.  doi:10.1016/0012-365X(93)90376-5.
  * [30] Robert Endre Tarjan.  Depth-first search and linear graph algorithms.  SIAM J. Comput., 1(2):146–160, 1972.  doi:10.1137/0201010.
  * [31] Robert Endre Tarjan.  Efficiency of a good but not linear set union algorithm.  J. ACM, 22(2):215–225, 1975.  doi:10.1145/321879.321884.
  * [32] Yung H. Tsin.  Yet another optimal algorithm for 3-edge-connectivity.  J. Discrete Algorithms, 7(1):130–146, 2009.  doi:10.1016/j.jda.2008.04.003.
  * [33] Jeffery R. Westbrook and Robert Endre Tarjan.  Maintaining bridge-connected and biconnected components on-line.  Algorithmica, 7(5&6):433–464, 1992.  doi:10.1007/BF01758773.