University of Sydney] ARC Centre of Excellence in Exciton Science, School of
Chemistry, The University of Sydney, NSW 2006, Australia [Sydney Nano] The
University of Sydney Nano Institute, The University of Sydney, NSW 2006,
Australia INM — Leibniz Institute for New Materials] INM — Leibniz Institute
for New Materials, Campus D2 2, 66123 Saarbrücken, Germany University of
Melbourne] ARC Centre of Excellence in Exciton Science, School of Chemistry,
University of Melbourne, Parkville, Victoria 3010, Australia INM — Leibniz
Institute for New Materials] INM — Leibniz Institute for New Materials, Campus
D2 2, 66123 Saarbrücken, Germany University of Melbourne] ARC Centre of
Excellence in Exciton Science, School of Chemistry, University of Melbourne,
Parkville, Victoria 3010, Australia INM — Leibniz Institute for New Materials]
INM — Leibniz Institute for New Materials, Campus D2 2, 66123 Saarbrücken,
Germany [Saarland University]Colloid and Interface Chemistry, Saarland
University, Campus D2 2, 66123 Saarbrücken, Germany University of Sydney] ARC
Centre of Excellence in Exciton Science, School of Chemistry, The University
of Sydney, NSW 2006, Australia [Sydney Nano] The University of Sydney Nano
Institute, The University of Sydney, NSW 2006, Australia

# When Like Destabilizes Like: Inverted Solvent Effects in Apolar Nanoparticle
Dispersions

Debora Monego  [  Thomas Kister  [  Nicholas Kirkwood  [  David Doblas  [
Paul Mulvaney  [  Tobias Kraus  [  Asaph Widmer-Cooper  asaph.widmer-
<EMAIL_ADDRESS>[

##  1 Abstract

We report on the colloidal stability of nanoparticles with alkanethiol shells
in apolar solvents. Small angle X-ray scattering and molecular dynamics
simulations were used to characterize the interaction between nanoparticles in
linear alkane solvents ranging from hexane to hexadecane, including
$4\text{\,}\mathrm{nm}$ gold cores with hexadecanethiol shells and
$6\text{\,}\mathrm{nm}$ cadmium selenide cores with octadecanethiol shells. We
find that the agglomeration is enthalpically driven and that, contrary to what
one would expect from classical colloid theory, the temperature at which the
particles agglomerate increases with increasing solvent chain length. We
demonstrate that the inverted trend correlates with the temperatures at which
the ligands order in the different solvents, and show that the inversion is
due to a combination of enthalpic and entropic effects that enhance the
stability of the ordered ligand state as the solvent length increases. We also
explain why cyclohexane is a better solvent than hexane, despite having very
similar solvation parameters to hexadecane.

##  2 Keywords

nanoparticle, dispersion, apolar, colloidal stability, ligand, solvent,
agglomeration

##  3 Introduction

Inorganic nanoparticles made of metals 1, 2, semiconductors 3, 4, and oxides 5
are now used as functional components in catalysis 6, 7, sensing 8, 9,
photovoltaics 10, 11, and color conversion in white light generation 12, 13,
14. Many applications require the particles to be dispersed individually in
organic solvents or to pass through this stage during processing.

Purely inorganic particles do not form stable dispersions in apolar solvents
because van der Waals (vdW) forces cause attraction and thus agglomeration of
the particles 15. Cores are therefore coated with organic molecules during
synthesis 16, 17, 6, 3 or during subsequent ligand-exchange procedures. The
adsorbed ligands provide steric stabilization and reduce the interfacial
energy of the particles 18.

The colloidal stability of ligand-coated particles in small molecule solvents
is commonly explained with the classical “like dissolves like” rule, whereby
the colloid interaction is assumed to be purely repulsive in solvents that are
good for the tail group of the ligands 19, 20, 21. Reducing the quality of the
solvent, in turn, induces enthalpic attraction between the ligands 22, 23, 24,
25, 26 and is a common way of destabilizing these suspensions 27. Van der
Waals attraction between the cores can also drive agglomeration, even in good
solvents, if the cores are sufficiently large or the ligands are too short 28,
29, 30.

Surprisingly, there appear to be exceptions to the rule of “like dissolves
like” even for small metal and semiconductor particles whose agglomeration
solely depends on the ligand shell 30, 31. Lohman et al. found that gold
nanoparticles with octane- or hexadecanethiol shells were more stable in
alkanes shorter than the ligand chain 32, while Hajiw et al. found that gold
nanoparticles with hexane- or dodecanethiol shells were more stable in
cyclohexane than in heptane or dodecane, respectively 33. In polymer solutions
and melts, where the conformational entropy of free polymer molecules can
drive particle agglomeration 34, 35, colloidal stability does typically
decrease with polymer length 36, 37. However, a purely entropic explanation
seems unlikely in relatively short solvents, like the ones described above,
where the agglomeration is driven by enthalpy.

Here, we have studied the dispersibility of gold and cadmium selenide
nanoparticles in a variety of linear and cyclic alkane solvents using
experiments that characterize their temperature-dependent colloidal stability.
In all cases, colloidal stability decreased as the length of the alkane
solvent approached that of the ligand tail, opposite to the rule of “like
dissolves like”. Further, we found that cyclohexane is a considerably better
solvent for the particles than hexadecane, despite the two solvents having
very similar solvation parameters. Specifically, changing the solvent from
hexadecane to cyclohexane decreased the agglomeration temperature by
$15\text{\,}\mathrm{\SIUnitSymbolCelsius}$. It is important to understand the
origin of such inversions, because the choice of solvents for stable
dispersions of nanoparticles is of considerable practical relevance; it
affects the quality of nanocomposites, nanocrystal assembly 38, and phase
transfer procedures 39, ultimately affecting device processability and
performance.

In order to understand the origin of this behavior, we compared our systematic
experimental data with detailed molecular dynamics simulations. Our results
indicate that the inversion is a consequence of both enthalpic and entropic
effects that together enhance the stability of an attractive ligand state as
the solvent chain length increases. As has been shown previously, ligand
shells composed of linear alkyl tails can undergo an ordering transition in
solution that switches the interaction between the nanoparticles from
repulsive to attractive 25. The temperature of this ligand phase transition is
sensitive to various parameters including the particle dimensions, density of
ligand coverage, and ligand length, often leading to non-linear trends that
cannot be explained using classical colloid theory 40, 30, 31. We show that
even small changes in the solvent structure can strongly impact the ligand
ordering transition and use this insight to explain how particles can have
dramatically different interactions in solvents with almost the same Hamaker,
Hildebrand and Hansen parameters.

##  4 Results and Discussion

Nanoparticles (NP) with Au cores ($4\text{\,}\mathrm{nm}$ and
$7.5\text{\,}\mathrm{nm}$ in diameter) and CdSe cores ($6\text{\,}\mathrm{nm}$
in diameter) were coated with hexadecanethiol (SC_16), dodecanethiol (SC_12),
and octadecanethiol (SC_18) chains, respectively. These particles were
dispersed in linear and cyclic alkane solvents of different chain lengths and
analyzed by in situ small angle X-ray scattering (SAXS) at a concentration of
$2.5\text{\,}\mathrm{mg}\text{\,}{\mathrm{mL}}^{-1}$ (roughly
$3.8\text{\times}{10}^{15}\text{\,}\mathrm{N}\mathrm{P}\mathrm{m}\mathrm{l}^{-1}$).
For all solvents tested, the particles agglomerated below a certain
temperature (Figure 1), which was observed as a peak in the structure factor41
$S(q)$. The agglomeration temperature, $T_{agglo}$, defined as the temperature
at which $20\text{\,}\mathrm{\char 37\relax}$ of the particles had
agglomerated, increased in all cases as the solvent length approached the
ligand length (Figure 1d). Similar results were obtained for
$7.5\text{\,}\mathrm{nm}$ Au cores coated with hexadecanethiol (SC_16) ligands
(see Figure SLABEL:SI_7p5nmSC16 in the Supporting Information). No sign of
solvent freezing was observed in any of the experiments.

Figure 1: Fraction of agglomerated (a) $4\text{\,}\mathrm{nm}$ Au-SC_16, (b)
$6\text{\,}\mathrm{nm}$ CdSe-SC_18, and (c) $7.5\text{\,}\mathrm{nm}$ Au-SC_12
particles, as determined by in situ small angle X-ray scattering. All
particles were dispersed at high temperatures, and agglomeration occurred upon
cooling as indicated by the increase in structure factor. (d) Agglomeration
temperature (where $20\text{\,}\mathrm{\char 37\relax}$ of particles were
agglomerated) as a function of alkane solvent chain length.

These results show that the agglomeration is enthalpically favorable and
entropically unfavorable, with cooling required to destabilize the
dispersions. Extensions of classical colloid theory to describe the colloidal
stability of ligand-coated nanoparticles in solution, for example reference
23, typically include two terms that favor dispersion (the ideal entropy of
mixing and the conformational entropy of the ligands) and two terms that favor
agglomeration (the vdW attraction between the cores and the non-ideal free
energy of mixing). The vdW attraction between the cores is insignificant for
our particles,30 leaving the free energy of mixing as the deciding term in
this classical approach. This can be described by the Flory-Huggins theory
(equations 1 and 2) that quantifies the affinity of the tethered ligands for
the solvent in terms of the ideal entropy of mixing and the Flory $\chi$
parameter (equation 3). In these equations, $d$ is the core diameter,
$\tilde{L}$ is the rescaled ligand length (ligand length divided by core
diameter), $k_{b}$ the Boltzmann’s constant, $T$ the absolute temperature,
$\phi\ =\left(N_{L}\frac{\nu_{L}}{V_{Sh}}\right)^{2}$ is the volume fraction
occupied by the ligand shell, $\nu_{S}$ is the volume of a solvent molecule,
$\nu_{L}$ the volume of a ligand molecule, $N_{L}$ the number of ligands per
nanoparticle, $V_{Sh}$ the volume of the ligand shell, $V_{S}$ is the molar
volume of the solvent, $R$ is the universal gas constant, and $\delta_{L}$ and
$\delta_{S}$ are the Hildebrand solubility parameters for the ligands and
solvent, respectively.

$\frac{G_{mix}}{k_{b}T}=\frac{\pi
d^{3}}{2\nu_{S}}\phi^{2}\left(\frac{1}{2}-\chi\right)\left(\tilde{s}-1-2\tilde{L}\right)^{2};\quad
1+\tilde{L}<x<1+2\tilde{L}$ (1) $\frac{G_{mix2}}{k_{b}T}=\frac{\pi
d^{3}}{\nu_{S}}\phi^{2}\tilde{L}^{2}\left(\frac{1}{2}-\chi\right)\left(3ln\frac{\tilde{L}}{\tilde{s}-1}+2\frac{\tilde{s}-1}{\tilde{L}}-\frac{3}{2}\right);\quad
x<1+\tilde{L}$ (2) $\chi=\frac{V_{S}}{RT}(\delta_{L}-\delta_{S})^{2}+0.34$ (3)

A Flory parameter below $0.5$ indicates that the free energy of mixing of
solvent and ligand is negative and that the two components should
spontaneously mix. Since only the alkane tails of the ligands interact with
the solvent, it seems reasonable to approximate the solubility parameters of
the ligands by those of the unthiolated alkanes, i.e. hexadecane
($16.4\text{\,}{\mathrm{M}\mathrm{Pa}}^{1/2}$) and octadecane
($17.1\text{\,}{\mathrm{M}\mathrm{Pa}}^{1/2}$). Thus, hexadecane is expected
to be a better solvent for these coatings than decane
($\delta_{s}=$15.8\text{\,}{\mathrm{M}\mathrm{Pa}}^{1/2}$$) and hexane
($\delta_{s}=$14.9\text{\,}{\mathrm{M}\mathrm{Pa}}^{1/2}$$) (Hildebrand
parameters from reference 42), even taking into account the reduction in the
ideal entropy of mixing ($\Delta S_{mix}^{ideal}$) as the solvent chain length
increases (see Table SLABEL:SI_Table_SolvParams in the Supporting
Information). A similar conclusion is reached when considering Hamaker
constants or Hansen solubility parameters of the ligand and solvent molecules.
Even if one were to use different solubility parameters for alkyl ligands
bound to nanoparticles, it would remain impossible within this theoretical
framework to explain why cyclohexane is a much better solvent than hexadecane,
since the two have almost identical solubility parameters.

An alternative explanation for deviations from the rule of “like dissolves
like” in short-chain solvents was proposed by Hajiw and co-workers, who
studied the temperature-dependent dispersibility of small Au particles
(roughly $2.3\text{\,}\mathrm{nm}$ in diameter) in a similar range of alkane
solvents.33 They noted that the colloidal stability of polymer-grafted
particles in polymer melts does typically decrease with polymer length and
speculated that similar thermodynamic driving forces may explain such trends
in much shorter solvents. In polymer melts, however, it is the conformational
entropy of the free polymer chains that drives agglomeration. As we shall
show, the solvent conformational entropy ($S_{conf}^{solv}$) in short-chain
solvents is much smaller and unable to explain the observed dispersibility
trends. In order to quantify $S_{conf}^{solv}$, along with enthalpic effects
that are not considered in classical colloid theory, we used molecular
dynamics (MD) simulations (see Methods for details).

MD simulations of $4\text{\,}\mathrm{nm}$ core diameter Au and
$5.8\text{\,}\mathrm{nm}$ CdSe particles in explicit solvent show that upon
cooling, the ligands adopt more extended configurations and cluster together
into ordered bundles in an enthalpically driven process. Snapshots of the
simulations above, at, and below $T_{agglo}$ in the linear alkane solvents are
shown in Figure 2a and in Figure SLABEL:SI_CdSe_snapshots in the Supporting
Information, with solvent molecules hidden for clarity. Similar ligand shell
structures were found for cyclohexane (shown in Figure SLABEL:SI_Cyclohexane
in the Supporting Information). The average dihedral angle of the ligand tails
was used to quantify the ordering transition in the shell, with the results
shown in Figures 2b and 2c. The simulations show that the same ligand shells
“order” at higher temperature in longer alkane solvents for both Au and CdSe
cores. This trend mirrors the experimental results, with the experimentally
observed particle agglomeration temperatures (indicated by large crossed
symbols) always occurring after the ligands have started ordering. These
results indicate that particle agglomeration is driven by the ligand shell
transition regardless of the core material, solvent length or structure,
consistent with our previous findings for similar particles in decane 30 and
with earlier experimental results for much larger silica particles in
hexadecane 44.

Figure 2: (a) Simulation snapshots of $4\text{\,}\mathrm{nm}$ Au particles at
$T_{agglo}$ $\pm$ $30\text{\,}\mathrm{\SIUnitSymbolCelsius}$ in hexane,
decane, and hexadecane. Solvent molecules have been hidden for clarity, with
symbols as shown in the plot legends. The ligands order as the temperature
decreases in a similar way in all solvents. This transition can be quantified
by the average dihedral angle of the ligands, which increases rapidly as they
order for both (b) $4\text{\,}\mathrm{nm}$ Au-SC_16 and (c)
$5.8\text{\,}\mathrm{nm}$ CdSe-SC_18 particles. For comparison, the
experimental agglomeration temperatures have been indicated by large crossed
symbols. The scheme at the bottom left of (c) shows the definition of the
dihedral angle $\phi$.

To explicitly test whether ordering of the ligand shell drives agglomeration
regardless of solvent length, we calculated the potential of mean force
between pairs of $4\text{\,}\mathrm{nm}$ Au particles in explicit hexane and
decane (Figures 3a and 3b, respectively) as a function of separation and
temperature. The overall interaction switched from repulsive to attractive as
the ligands ordered, irrespective of solvent. This change in interaction
between the ligand shells arises from changes in how the ligands interact with
one another and with the solvent as their conformational state changes (see
Figure SLABEL:SI_PMFComponents in the Supporting Information). The ligand-
ligand component (which includes vdW interactions between the ligands) becomes
more attractive as the ligands order, while the ligand-solvent component
(which includes entropy changes involving the solvent) becomes less repulsive.
In contrast, the overall interaction between alkyl ligand shells is always
attractive in the absence of solvent, regardless of their conformational
state, due to the absence of competing ligand-solvent interactions 21,
Waltmann2018, 25, 30. (The relevant results in references 25 and 30 are
located in the Supporting Information of those papers.)

So far, we have established that the nanoparticles agglomerate because the
ligands order and that the enthalpic driving force for both of these processes
is the attractive vdW force that exists between the bound ligands. We now
focus on the thermodynamics of the ligand ordering transition in order to
explain the origin of the inverted trend in agglomeration temperatures. In
particular, we will show that the trend is a consequence of both enthalpic and
entropic effects that together enhance the stability of the attractive ligand
state as the solvent chain length increases. We start by considering a single
nanoparticle and quantifying the dominant enthalpic contributions to the free
energy difference between the disordered and ordered ligand states, i.e. the
vdW interactions between ligand molecules within the same shell ($U_{LL}$) and
between ligand and solvent molecules ($U_{LS}$). These quantities are compared
as a function of temperature and solvent type in Figure 4.

Figure 3: Potentials of mean force calculated for pairs of
$4\text{\,}\mathrm{nm}$ Au-SC_16 particles in (a) hexane and (b) decane, at
temperatures around $T_{agglo}$. Simulation snapshots show the state of the
ligands above and below $T_{agglo}$, at temperatures corresponding to the blue
squares and red triangles, respectively.

We find that the interaction between the ligands follows a similar trend in
all solvents apart from a temperature offset: $U_{LL}$ increases in magnitude
in all cases by
$3\text{\,}$-$4\text{\,}$\mathrm{k}_{\mathrm{b}}\mathrm{T}$\mathrm{/}\mathrm{l}\mathrm{i}\mathrm{g}\mathrm{a}\mathrm{n}\mathrm{d}$
during the transition (Figures 4a and 4c). Statistical analysis of the
interatomic spacings within the ligand shell (see Figure
SLABEL:SI_fll_frequency in the Supporting Information) indicate that the
structure of the ligand shell is almost identical regardless of solvent when
the temperature is expressed relative to $T_{order}$, defined as the
temperature at which the average dihedral angle equals $None$ (which
corresponds roughly to the middle of the transition).

In contrast, we find more substantial differences in the interaction between
ligand and solvent molecules. Figures 4b and 4d show that the ligand-solvent
interaction energy ($U_{LS}$) increases during the ordering transition in
hexadecane (blue arrows) but decreases in decane, hexane and cyclohexane (red,
black and green arrows), with the largest decrease in hexane (around
$2\text{\,}$\mathrm{k}_{\mathrm{b}}\mathrm{T}$\mathrm{/}\mathrm{l}\mathrm{i}\mathrm{g}\mathrm{a}\mathrm{n}\mathrm{d}$).
This means that the change in internal energy driving the ligand shell to
order is reduced in shorter solvents, which partly explains why the particles
are more stable in hexane and cyclohexane than in hexadecane.

The differences in $\Delta U_{LS}$ during the transition are due to subtle
molecular effects. As the ligands order to form dense bundles, the solvent
molecules within the spherical shell occupied by the ligands become confined
to the spaces between the bundles. This results in a similar increase in the
radially averaged solvent density near the core surface in all solvents
(Figures SLABEL:SI_Densities and SLABEL:SI_Cyclohexane in the Supporting
Information), but with very different consequences depending on how well the
solvent molecules pack with the ligand bundles. Hexane and cyclohexane pack
less well with the ordered ligands, resulting in a loss of ligand-solvent
interaction, while hexadecane packs better with the ordered ligands, resulting
in a gain in ligand-solvent interaction (Figures SLABEL:SI_fls_distribution
and SLABEL:SI_Cyclohexane in the Supporting Information).

Figure 4: The energy of interaction between ligand molecules ($U_{LL}$) on
isolated (a) $4\text{\,}\mathrm{nm}$ Au-SC_16 and (c)
$5.8\text{\,}\mathrm{nm}$ CdSe-SC_18 particles increases upon cooling in all
solvents. In contrast, the energy of interaction between ligand and solvent
molecules ($U_{LS}$) decreases in magnitude for shorter chain alkanes and
increases for hexadecane for both (b) Au and (d) CdSe nanoparticles, as
indicated by the solid arrows. All energies are normalized by the number of
ligand molecules on the nanoparticle, $N_{L}$.

Entropic differences between the solvents appear to play an important role
here. It is well known that the lower freezing points of shorter chain alkanes
are partly due to their higher translational entropy per atom.43 Analysis of
the average dihedral angles also reveals that longer alkanes are more extended
both within and outside the ligand shell, as shown in Figure 5a for the
$4\text{\,}\mathrm{nm}$ Au NPs. Similar results are obtained for the CdSe
particles (see Figure SLABEL:SI_CdSeDihedral in the Supporting Information).
These factors may explain why hexadecane is better able than hexane to align
with the ordered ligands (Figure 5b) and thus increase the relative stability
of the ordered state. We note that close alignment of hexadecane with linear
alkyl ligands has also been observed in sum frequency generation spectroscopy
studies of silica nanoparticles 44.

Figure 5: (a) The average dihedral angle for the solvent chains around AuNP
shows that longer alkanes are more extended at a given temperature, both
within the ligand shell (open symbols) and in the bulk solvent region (closed
symbols). This allows hexadecane to better align with and stabilize the
ligands in the ordered state, as seen in (b) snapshots of the ligand-solvent
packing at $T_{order}$ for $4\text{\,}\mathrm{nm}$ Au-SC_16 particles. Ligand
and solvent united-atoms are represented by blue and white spheres,
respectively. The error bars in (a) are smaller than the symbols, and the
lines are a guide to the eye.

To more directly address how entropy affects the ligand ordering transition,
we quantified the difference (between the ordered and disordered ligand
states) in the ideal entropy of mixing ($\Delta S_{mix}^{ideal}$) and in the
conformational entropies of the ligands ($\Delta S_{conf}^{lig}$) and solvent
($\Delta S_{conf}^{solv}$). $\Delta S_{mix}^{ideal}$ is relevant because
ordering of the ligands causes them to demix from the solvent. The change in
entropy due to this demixing was estimated using equations 1 and 2, setting
$\chi=0$ and multiplying by 5 for reasons explained in the Methods. This
yielded values for $-T\Delta S_{mix}^{ideal}$ ranging from roughly 0.3
$k_{b}T$/ligand for hexane to 0.1 $k_{b}T$/ligand for hexadecane, indicating a
decreasing penalty for ordering as the solvent length increases.

The changes in the conformational entropies were estimated using an
information theoretic approach that is described in detail in the Methods.
Both ordered and disordered configurations were generated at the same
temperature, $T_{order}$, in order to exclude contributions due to temperature
differences. This was achieved by scaling the interaction energies between
non-bonded ligand atoms by $\pm$ 5%, which resulted in ligand configurations
similar to those at $T_{order}\mp$ $30\text{\,}\mathrm{K}$. This yielded
values for $-T\Delta S_{conf}^{lig}$ ranging from $2.2-3$ $k_{b}T$/ligand,
with no apparent trend with solvent length. This substantial penalty is the
main reason why ordering of the ligands has to be enthalpically driven. In
comparison, we obtained values for $-T\Delta S_{conf}^{solv}$ ranging from
$0-0.3$ $k_{b}T$/ligand. Again there was no apparent trend with solvent
length, indicating that the conformational entropy of the solvent makes at
best a small contribution to the trend in agglomeration temperatures.

To facilitate comparison, we estimated the equivalent differences in $U_{LL}$
and $U_{LS}$ at $T_{order}$ via linear extrapolation of the data points
obtained above and below the ordering transition, and collected all of the
enthalpic and entropic terms in Table 1. Also included is the substantial
change in the internal energy associated with the ligand dihedral angles
($\Delta U_{dih}^{lig}$), obtained from the same biased simulations as the
conformational entropies. Together, these values indicate that the main
contribution to the inverted trend in the agglomeration temperatures is the
reduction in $\Delta U_{LS}$ as the solvent length increases, with a minor
contribution from the reduction in $-T\Delta S_{mix}^{ideal}$.

Table 1: Major enthalpic and entropic contributions to the difference in free
energy between the ordered and disordered ligand states, expressed in units of
$k_{b}T$/ligand at the ligand ordering temperature $T_{order}$: $U_{LL}$ is
the vdW interaction between the ligands, $U_{LS}$ is the vdW interaction
between the ligands and the solvent, $U_{dih}^{lig}$ is the internal energy
due to the ligand dihedral angles, $S_{mix}^{ideal}$ is the entropy of
demixing the ligands and solvent, while $S_{conf}^{lig}$ and $S_{conf}^{solv}$
are the conformational entropies of the ligands and solvent, respectively.
Negative quantities favor the ordered state while positive ones favor the
disordered one. The quantities highlighted in green are the only ones that
explain the trend in the agglomeration temperatures. The * indicates a value
that was estimated by comparison with the same results obtained for CdSe.
Standard errors are $\pm 0.3$ or smaller. $4\text{\,}\mathrm{nm}$ Au-SC16
---
Solvent | Hexane | Decane | Hexadecane
$T_{order}$ | 290 | 295 | 300
$\Delta U_{LL}$ | -3.8 | -3.7 | -3.5
[HTML]32CB00 $\Delta U_{LS}$ | 4.0 | 2.3 | 1.0∗
$\Delta U_{dih}^{lig}$ | -2.6 | -2.3 | -1.8
[HTML]32CB00 $-T\Delta S_{mix}$ | 0.32 | 0.22 | 0.14
$-T\Delta S_{conf}^{lig}$ | 2.5 | 3.0 | 2.5
$-T\Delta S_{conf}^{solv}$ | 0.00 | 0.00 | 0.30
$5.8\text{\,}\mathrm{nm}$ CdSe-SC18
Solvent | Hexane | Decane | Hexadecane
$T_{order}$ | 300 | 310 | 320
$\Delta U_{LL}$ | -4.4 | -3.5 | -3.1
[HTML]32CB00 $\Delta U_{LS}$ | 4.3 | 2.6 | 1.3
$\Delta U_{dih}^{lig}$ | -1.9 | -1.8 | -1.3
[HTML]32CB00 $-T\Delta S_{mix}$ | 0.54 | 0.37 | 0.25
$-T\Delta S_{conf}^{lig}$ | 2.2 | 2.8 | 2.2
$-T\Delta S_{conf}^{solv}$ | -0.17 | 0.12 | -0.09

Our results also explain why alkanethiol-coated nanoparticles are more stable
in cyclohexane than in hexadecane, despite the two solvents having almost
identical density and solubility parameters. In cyclohexane, the reduction in
$U_{LS}$ upon ordering is greater than in hexadecane (due to poorer packing
with the extended ligands), while the entropic cost of demixing is also
greater due to cyclohexane’s smaller size and thus higher number density. The
ordered ligand state is therefore less stable (relative to the disordered one)
in cyclohexane than in hexadecane, which suppresses the ordering transition
and results in an agglomeration temperature that is even lower than that in
hexane.

Finally, to check whether $S_{conf}^{solv}$ contributes to the trend in
agglomeration temperatures regardless of the conformational state of the
ligands, we calculated the difference in $S_{conf}^{solv}$ between the
solvated $4\text{\,}\mathrm{nm}$ Au nanoparticles and pure solvent with the
same number of solvent molecules. This yielded a similar value in all solvents
for $-T\Delta S_{conf}^{solv}$ of roughly 0.2 $k_{b}T$/ligand when the ligands
were in the disordered state, indicating no substantial contribution to the
trend.

##  5 Conclusions

We have studied the temperature-dependent agglomeration of small apolar
metallic and semiconducting nanoparticles in a range of alkane solvents. We
found that the agglomeration is enthalpically driven, with colloidal
stabilities that run counter to expectations from classical colloid theory.
Increasing the solvent chain length towards that of the ligands resulted in a
_decrease_ in colloidal stability, rather than the expected increase, and the
colloidal stability differed strongly between cyclohexane and hexadecane
despite their almost identical solvation parameters.

While this behavior is reminiscent of colloidal stability in polymer solutions
and melts, the thermodynamic origins are different, with enthalpic rather than
entropic effects dominating in small organic solvents. Simulations show that
the nanoparticles become attractive to one another as the ligands order and
that the temperatures at which the particles agglomerate match the
temperatures at which the ligands order in the various solvents. This
indicates that the experimental results can be understood by considering the
thermodynamics of the ordering transition and, in particular, how well the
various solvents stabilize the ordered state of the ligands relative to the
disordered one.

We found that the ordering transition is driven by vdW attraction between the
ligand tails, and internal energy associated with their dihedral angles, and
opposed by a combination of enthalpic and entropic terms: loss of vdW
interaction between the ligands and solvent, loss of ligand conformational
entropy, and a reduction in the entropy of mixing. Of these, the loss in vdW
interaction with the solvent exhibits the biggest differences, with smaller
losses observed as the solvent length increases due to better packing with the
ordered ligands. The entropic cost of demixing the ligands from the solvent
also exhibits a small decrease as the size of the solvent molecules increases.
Together, these changes increase the relative stability of the ordered ligand
state when the solvent is changed from hexane or cyclohexane to hexadecane,
which explains the experimental results.

We hope that these results will inspire more detailed experimental studies of
ligand morphology and ligand-solvent interactions, which are now possible due
to recent advances in Sum Frequency Generation spectroscopy 44, Nuclear
Magnetic Resonance 45, 46, and Small Angle Neutron Scattering 47. While we
have not considered polar solvents in the present study, we note that linear
-(CH_2)_nX ligands with a variety of terminal X groups can also order in water
48, 49, raising the possibility of similar effects in polar solvents.

##  6 Methods

All chemicals were obtained from Sigma Aldrich (unless noted otherwise) and
used without further purification. The methods were chosen to provides samples
that are as comparable as possible to data published previously 30, 31.

###  6.1 Nanoparticle synthesis

The synthesis of gold nanoparticles (AuNP) with core diameters of
$4\text{\,}\mathrm{nm}$ and $7.5\text{\,}\mathrm{nm}$ was adapted from a
previously described method 30. For AuNPs with a core diameter of
$4\text{\,}\mathrm{nm}$ a mixture of pentane ($\geq$ 98.5%, GC),
$8\text{\,}\mathrm{mL}$ oleylamine (technical grade, 70%), and
$100\text{\,}\mathrm{mg}$ of HAuCl4 (with crystal water) was stirred at
$20\text{\,}\mathrm{\SIUnitSymbolCelsius}$ and
$500\text{\,}\mathrm{rad}\text{\,}{\mathrm{min}}^{-1}$ for
$10\text{\,}\mathrm{min}$ under argon atmosphere. Afterwards a solution of
$40\text{\,}\mathrm{mg}$ tert-butylamine borane (ABCR, 97%) in
$2\text{\,}\mathrm{mL}$ pentane and $2\text{\,}\mathrm{mL}$ oleylamine was
added. The color of the solution immediately changed. After stirring for
$60\text{\,}\mathrm{min}$ at $20\text{\,}\mathrm{\SIUnitSymbolCelsius}$, the
nanoparticles were purified once by precipitating with
$30\text{\,}\mathrm{mL}$ ethanol and centrifugation at
$4000\text{\,}\mathrm{rad}\text{\,}{\mathrm{min}}^{-1}$ for
$5\text{\,}\mathrm{min}$. The precipitated nanoparticles were then redispersed
in $20\text{\,}\mathrm{mL}$ of the appropriate solvent. Gold cores with a
diameter of $7.5\text{\,}\mathrm{nm}$ were produced in benzene instead of
pentane. The mixture of benzene, oleylamine and HAuCl4 was stirred for
$1\text{\,}\mathrm{min}$ before tert-butylamine borane was added. The
resulting dispersion was then purified as above.

Cadmium selenide nanoparticles (CdSeNPs) with core diameters of
$6\text{\,}\mathrm{nm}$ were synthesized as follows. First, three stock
solutions were prepared, a Se injection solution (i), a Cd growth solution
(ii), and a Se growth solution (iii): (i) $0.3265\text{\,}\mathrm{g}$ Se were
dissolved in a mixture of $2.5\text{\,}\mathrm{g}$ trioctylphosphine,
$2.5\text{\,}\mathrm{g}$ octadecene, and $6\text{\,}\mathrm{g}$ oleylamine in
a nitrogen-filled glovebox to give a clear, slightly yellow solution. (ii) A
solution containing $0.17\text{\,}\mathrm{mol}\text{\,}{\mathrm{L}}^{-1}$ of
cadmium was made from $0.22\text{\,}\mathrm{g}$ cadmium oxide,
$0.97\text{\,}\mathrm{g}$ oleic acid, and $6.23\text{\,}\mathrm{g}$
1-octadecene in a 3 neck round bottom flask on a Schlenk line. The solution
was degassed under vacuum ($<$ $1\text{\,}\mathrm{mbar}$) for
$60\text{\,}\mathrm{min}$ at $80\text{\,}\mathrm{\SIUnitSymbolCelsius}$,
heated to $250\text{\,}\mathrm{\SIUnitSymbolCelsius}$ and held until clear,
then cooled to room temperature. Whilst cooling $1.13\text{\,}\mathrm{mL}$ of
oleylamine were added. The final solution was clear and slightly yellow. (iii)
A solution containing $1.7\text{\,}\mathrm{mol}\text{\,}{\mathrm{L}}^{-1}$ of
selenium was prepared by dissolving $0.25\text{\,}\mathrm{g}$ of selenium in
$1.55\text{\,}\mathrm{g}$ trioctylphosphine in a nitrogen-filled glovebox to
give a clear colourless solution.

The synthesis started with $0.22\text{\,}\mathrm{g}$ cadmium oxide,
$3\text{\,}\mathrm{g}$ oleic acid, and $30\text{\,}\mathrm{g}$ octadecene in a
3 neck round bottom flask that was degassed under vacuum ($<$
$1\text{\,}\mathrm{mbar}$) for $60\text{\,}\mathrm{min}$ at
$80\text{\,}\mathrm{\SIUnitSymbolCelsius}$. The mixture was then heated to
$260\text{\,}\mathrm{\SIUnitSymbolCelsius}$ until a clear solution (iv) had
formed. The selenium injection solution (i) was loaded into a
$24\text{\,}\mathrm{mL}$ disposable syringe equipped with a 16 G needle and
rapidly injected into the cadmium solution (iv) at
$260\text{\,}\mathrm{\SIUnitSymbolCelsius}$. The temperature of the reaction
solution was allowed to recover to $250\text{\,}\mathrm{\SIUnitSymbolCelsius}$
where it was held for NP growth. After $20\text{\,}\mathrm{min}$,
$2\text{\,}\mathrm{mL}$ of
$0.17\text{\,}\mathrm{mol}\text{\,}{\mathrm{L}}^{-1}$ cadmium growth stock
(ii) and $0.2\text{\,}\mathrm{mL}$ of
$1.7\text{\,}\mathrm{mol}\text{\,}{\mathrm{L}}^{-1}$ selenium growth stock
(iii) were added dropwise to the reaction. The addition of cadmium and
selenium growth solutions (ii, iii) was continued every
$10\text{\,}\mathrm{min}$. After 3 additions, the reaction was left for a
further $10\text{\,}\mathrm{min}$ at
$250\text{\,}\mathrm{\SIUnitSymbolCelsius}$, then cooled to room temperature.
The NPs were washed three times via precipitation with acetone and resuspended
in toluene.

###  6.2 Nanoparticle characterization

Small Angle X-ray Scattering (Xenocs Xeuss 2.0) and Transmission Electron
Microscopy (JEOL JEM 2010) were used to measure the core size of the NPs as
previously described30. Scattering data from SAXS was analyzed using SASfit
(Version 0.94.6, Paul Scherrer Institute) and TEM micrographs were analyzed
using ImageJ distributed by NIH (Version 1.45s).

Table 2: NPs used for this study, with diameters obtained from transmission electron microscopy and small angle X-ray scattering. Number | d (TEM) | d (SAXS)
---|---|---
Au01 |  4.1 nm $\pm$ $10.0\text{\,}\mathrm{\char 37\relax}$ |  4.1 nm $\pm$ $9.3\text{\,}\mathrm{\char 37\relax}$
Au02 |  7.4 nm $\pm$ $7.4\text{\,}\mathrm{\char 37\relax}$ |  7.5 nm $\pm$ $6.7\text{\,}\mathrm{\char 37\relax}$
CdSe |  5.8 nm $\pm$ $7.1\text{\,}\mathrm{\char 37\relax}$ |  6.0 nm $\pm$ $9.6\text{\,}\mathrm{\char 37\relax}$

###  6.3 Ligand exchange

AuNPs. Ligand exchange on AuNPs was performed as described previously 50.
AuNPs coated with oleylamine were heated to
$80\text{\,}\mathrm{\SIUnitSymbolCelsius}$ and an excess of required
alkanethiol was added. After stirring for further $10\text{\,}\mathrm{min}$,
the particles were purified and redispersed in the appropriate solvent.

CdSeNPs. As-synthesized CdSeNPs were precipitated with acetone/ethanol and
resuspended in a solution of the respective alkanethiol ligand (40 wt-$\%$ in
chloroform) with triethylamine (1 molar equivalent with respect to thiol). The
resulting NP dispersion was heated for 3 hours at
$45\text{\,}\mathrm{\SIUnitSymbolCelsius}$ while stirring. The NPs were then
washed via precipitation with antisolvent and centrifugation (3,300 x g for
$3\text{\,}\mathrm{min}$). The antisolvent was chosen to optimally dissolve
excess ligand: 1:1 (v/v) methanol/ethanol mixture for hexanethiol and
octanethiol ligands, or 1:1 (v/v) acetone/ethanol mixture for dodecanethiol
and longer ligands. The NPs were resuspended again in a solution of ligand (40
wt-$\%$ in chloroform), stirred at $45\text{\,}\mathrm{\SIUnitSymbolCelsius}$
for 2 hours, then washed as before and resuspended in a 0.1 M solution of
ligand in chloroform. After stirring at room temperature for 24-48 hours the
NPs were washed three times and resuspended in pure chloroform. Chambrier et
al. have shown this procedure leads to almost complete displacement ($>$ 92%)
of amines by the alkane thiol ligands 51.

###  6.4 Small Angle X-ray Scattering

Experiments were performed under vacuum using a Xeuss 2.0 from Xenocs SA
(Grenoble, France) equipped with a copper $K_{\alpha}$ X-ray source and a
PILATUS 1M detector from DECTRIS (Baden, Switzerland) using a sample-to-
detector distance of $1235\text{\,}\mathrm{mm}$.

To prevent solvent evaporation during the measurements, the samples (usually a
quantity of $20\text{\,}\mathrm{\SIUnitSymbolMicro l}$ to
$40\text{\,}\mathrm{\SIUnitSymbolMicro l}$) were filled into thin-wall glass
capillaries (diameter of $2\text{\,}\mathrm{mm}$) and sealed with epoxy resin.

For each measurement, the samples were introduced into a temperature
controlled sample holder (Omega CN8200), Peltier-controlled with a temperature
range between $-20\text{\,}\mathrm{\SIUnitSymbolCelsius}$ and
$120\text{\,}\mathrm{\SIUnitSymbolCelsius}$. The measurements started at high
temperature to ensure a fully deagglomerated state. Afterwards the temperature
was first decreased and later increased in
$5\text{\,}\mathrm{\SIUnitSymbolCelsius}$ steps. At each step, the samples
were first equilibrated ($20\text{\,}\mathrm{min}$) followed by an exposition
of $10\text{\,}\mathrm{min}$. Data treatment was carried out as described
elsewhere 52, 30.

###  6.5 Molecular dynamics simulations

Molecular dynamics (MD) simulations with periodic boundary conditions were
used to study $4\text{\,}\mathrm{nm}$ Au nanoparticles and
$5.8\text{\,}\mathrm{nm}$ CdSe nanoparticles covered in 1-hexadecanethiol and
1-octadecanethiol ligands, respectively, in the presence of a variety of
liquid alkanes (n-hexane, n-decane, n-hexadecane and cyclohexane). The sulfur
atoms from the ligands were randomly placed on a spherical shell around the
implicit core ($0.15\text{\,}\mathrm{nm}$ further out) and allowed to find
their optimal positions on this shell while subject to a Coulombic interaction
with relative permittivity $\epsilon$ = $10\text{\,}$ and the RATTLE
constraint53. This produced a shell with approximately equidistant binding
sites, with the sulfur atoms subsequently treated as part of the rigid core of
the particle. The ligands were irreversibly bound to the Au and CdSe cores at
a surface coverage of
$5.5\text{\,}\mathrm{l}\mathrm{i}\mathrm{g}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{s}\mathrm{n}\mathrm{m}^{-2}$,
consistent with thermogravimetric analyses of the experimental samples31. CH_x
groups from ligand and solvent molecules were treated as united atoms and
interacted with one another according to the 12-6 Lennard-Jones (LJ) potential
and with the implicit cores through a 9-3 LJ potential, as previously employed
and described for similar particles25, 54, 31. Additionally, bond stretching,
bond bending, and dihedral torsion terms were considered within each molecule,
with parameters taken from the TraPPE force field family55.

Simulations of systems with up to 165,000 particles were performed using the
LAMMPS molecular dynamics simulation package56, at temperatures ranging from
roughly the freezing point of the respective solvent to values sufficiently
high to have the ligands in the disordered state (up to
$340\text{\,}\mathrm{K}$). Periodic simulation cells containing individual
nanoparticles and the alkane solvent were slowly compressed until the solvent
density far from the NP was equal to the experimental density of the pure
solvent at the chosen temperature. A preliminary run was performed at constant
volume in order to accommodate the particles properly in the simulation cell.
The systems were then equilibrated at constant pressure
($80\text{\,}\mathrm{atm}$) and temperature, maintained with a Nosé-Hoover
thermostat and barostat, for at least $12\text{\,}\mathrm{ns}$. Finally, the
relevant data were accumulated and averaged over production runs of
$1\text{\,}\mathrm{ns}$. Average bulk solvent densities for these runs stayed
within $1\text{\,}\mathrm{\char 37\relax}$ of experimental values for linear
alkanes, and $5\text{\,}\mathrm{\char 37\relax}$ for cyclohexane. Molecular
graphics were produced using Visual Molecular Dynamics (VMD)57.

####  6.5.1 Potentials of mean force

The change in free energy as a pair of $4\text{\,}\mathrm{nm}$ Au particles
was brought together was calculated in both hexane and decane as a potential
of mean force (PMF) using constrained MD. Starting from a non-interacting
separation, the particles were brought together at a rate of
$1\text{\,}\mathrm{\SIUnitSymbolAngstrom}\text{\,}{\mathrm{ns}}^{-1}$. The
particles were allowed to rotate about their centers of mass at each
separation $r$, and subsequent simulations of $10\text{\,}\mathrm{ns}$ or more
were performed in order to adequately sample the PMF. Longer runs were
necessary particularly at and below $T_{order}$, where the ligands were less
mobile. Additionally, in order to allow the ligands to reorganize and find
more stable configurations at these temperatures, we included a thermal
annealing step at separations where the ligand shells overlapped. This was
done by increasing the temperature of these systems by $50\text{\,}\mathrm{K}$
over $1\text{\,}\mathrm{ns}$ and subsequently cooling it back to the initial
temperature over the course of $3\text{\,}\mathrm{ns}$.

The spherical gold cores were assumed to interact with each other via the
Hamaker potential 58, with a Hamaker constant of $2\text{\,}\mathrm{eV}$ 59.
This approach treats the solvent and ligands as a single continuum, with the
interaction constant scaled to include the effect of the hydrocarbon medium.

The PMF between two nanoparticles is given by

$\phi_{MF}(r)=\int_{r}^{\infty}F_{mean}(s)ds$ (4)

Where $F_{mean}$ is the average force in the direction of the line connecting
the two particles and is given by

$F_{mean}(r)=\frac{1}{2}\langle(\vec{F}_{2}-\vec{F}_{1})\cdot\vec{r}\rangle_{NVT}$
(5)

In the above, $\vec{F}_{1}$ and $\vec{F}_{2}$ are the total forces acting on
the first and second NP, respectively, $\vec{r}$ is the unit vector pointing
from one particle’s center to the other’s, and the angular brackets denote an
average in the canonical ensemble.

####  6.5.2 Entropy of mixing

The change in the ideal entropy of mixing due to spatially separating the
ligand and solvent molecules was estimated using equations 1 and 2 by setting
$\chi=0$ and calculating the value at the average core spacing in the
experimental agglomerates ($2.4\text{\,}\mathrm{nm}$). This value was then
multiplied by 5 to roughly convert the entropy change for a pair of touching
particles into the entropy change for an entire particle capable of
accommodating approximately 10 nearest neighbors. The other parameters used
are listed in Table SLABEL:tab:mixing_parameters in the Supporting
Information.

####  6.5.3 Conformational entropies

We employed the correlation corrected multibody local approximation (CC-MLA),
as implemented in the software CENCALC Suarez2013, to estimate changes in the
conformational entropies of the ligand and solvent molecules. The molecular
conformational space was represented in terms of the dihedral angles, which
were discretized into subintervals delimiting the three locally stable
conformational states accessible to them, i.e. trans, gauche(-), and
gauche(+). This transforms the continuous random variable $\theta$ into the
discrete random variable $X$, with a probability mass function $P(X)$, where
$X=\left\\{X_{1},...,X_{M}\right\\}$ and $M$ is the number of dihedral angles.
The entropy can then in principle be calculated as a sum over the $N$ possible
configurations of the system using the expression for the Shannon information
entropy:

$\centering
S_{conform}=-k_{b}\sum^{N}P\left(X\right)\ln{P\left(X\right)}.\@add@centering$
(6)

In practice, obtaining an accurate estimate for $P(X)$ is difficult, because
the number of possible conformers is very large ($\sim 3^{M}$). Direct
application of the Shannon expression would also result in large and
negatively-biased entropies due to correlations between the dihedral angles.
However, an approximation to the total entropy can be obtained by truncating a
mutual information expansion (MIE)60, allowing the Shannon information entropy
to be calculated using a reasonable number of states.

In addition, due to the large number of molecules in our system, each molecule
was treated as an independent system; i.e., a nanoparticle coated with $l$
ligands, each with $d$ dihedral angles, was analysed as $l$ independent
$d$-dimensional spaces. The sum of the entropies of the individual ligands
then provided an approximation for the entropy of the entire nanoparticle.
This approach considered the correlations within each molecule, but ignored
correlations between neighbor molecules, which are stronger for ligands in the
ordered state. The conformational entropy differences that we report for the
ligands therefore represent a lower bound, calculated using fully converged
values from data sampled every $1\text{\,}\mathrm{ps}$ over
$5.5\text{\,}\mathrm{ns}$. While we were not able to fully converge the
absolute solvent entropies using the same number of data points, the entropy
differences converge more rapidly and do appear to be fully converged.

P.M., N.K., D.M. and A.W. were supported by the ARC Centre of Excellence in
Exciton Science (CE170100026). A.W. thanks the Australian Research Council for
a Future Fellowship (FT140101061), and D.M. thanks the University of Sydney
Nano Institute for a Postgraduate Top-Up Scholarship and the Australian
Nanotechnology Network for an Overseas Travel Fellowship. Computational
resources were generously provided by the University of Sydney HPC service,
the National Computational Infrastructure National Facility (NCI-NF) Flagship
program, and the Pawsey Supercomputer Centre Energy and Resources Merit
Allocation Scheme. T.K., D.D. and T.K. thank the DFG Deutsche
Forschungsgemeinschaft for funding. P.M. and T.K. also thank the DAAD for
travel support.

## Supporting Information Available

Supporting Information shows SAXS data, fraction of agglomerated
$7.5\text{\,}\mathrm{nm}$ Au-SC_16 particles, simulation results for CdSe-
SC_18 particles dispersed in linear alkanes and for Au-SC_16 particles in
cyclohexane, radial density distributions of ligand and solvent, individual
contributions to the the PMF (in hexane), and number of ligand-ligand
interactions and ligand-solvent interaction energy as a function of the
separation between interacting pairs. This material is available free of
charge via the Internet at http://pubs.acs.org/.

## References

  * Jana and Peng 2003 Jana, N. R.; Peng, X. Single-Phase and Gram-Scale Routes toward Nearly Monodisperse Au and Other Noble Metal Nanocrystals. _J. Am. Chem. Soc._ 2003, _125_ , 14280–14281
  * Stoeva et al. 2002 Stoeva, S.; Klabunde, K. J.; Sorensen, C. M.; Dragieva, I. Gram-Scale Synthesis of Monodisperse Gold Colloids by the Solvated Metal Atom Dispersion Method and Digestive Ripening and Their Organization into Two- and Three-Dimensional Structures. _J. Am. Chem. Soc._ 2002, _124_ , 2305–2311
  * Peng et al. 1998 Peng, X.; Wickham, J.; Alivisatos, A. P. Kinetics of II-VI and III-V Colloidal Semiconductor Nanocrystal Growth: “Focusing” of Size Distributions. _J. Am. Chem. Soc._ 1998, _120_ , 5343–5344
  * Shim and Guyot-Sionnest 2000 Shim, M.; Guyot-Sionnest, P. n-Type Colloidal Semiconductor Nanocrystals. _Nature_ 2000, _407_ , 981–983
  * Pileni 2003 Pileni, M.-P. The Role of Soft Colloidal Templates in Controlling the Size and Shape of Inorganic Nanocrystals. _Nat. Mater._ 2003, _2_ , 145–150
  * Murray et al. 1993 Murray, C. B.; Norris, D. J.; Bawendi, M. G. Synthesis and Characterization of Nearly Monodisperse CdE (E = S, Se, Te) Semiconductor Nanocrystallites. _J. Am. Chem. Soc._ 1993, _115_ , 8706–8715
  * Haruta 2003 Haruta, M. When Gold Is Not Noble: Catalysis by Nanoparticles. _Chem. Rec._ 2003, _3_ , 75–87
  * Shipway et al. 2000 Shipway, A. N.; Katz, E.; Willner, I. Nanoparticle Arrays on Surfaces for Electronic, Optical, and Sensor Applications. _ChemPhysChem_ 2000, _1_ , 18–52
  * Saha et al. 2012 Saha, K.; Agasti, S. S.; Kim, C.; Li, X.; Rotello, V. M. Gold Nanoparticles in Chemical and Biological Sensing. _Chem. Rev._ 2012, _112_ , 2739–2779
  * Talapin and Murray 2005 Talapin, D. V.; Murray, C. B. PbSe Nanocrystal Solids for n- and p-Channel Thin Film Field-Effect Transistors. _Science_ 2005, _310_ , 86–89
  * Zhao et al. 2015 Zhao, W.; Rovere, T.; Weerawarne, D.; Osterhoudt, G.; Kang, N.; Joseph, P.; Luo, J.; Shim, B.; Poliks, M.; Zhong, C.-J. Nanoalloy Printed and Pulse-Laser Sintered Flexible Sensor Devices with Enhanced Stability and Materials Compatibility. _ACS Nano_ 2015, _9_ , 6168–6177
  * Chen et al. 2006 Chen, H.-S.; Hsu, C.-K.; Hong, H.-Y. InGaN-CdSe-ZnSe Quantum Dots White LEDs. _IEEE Photonics Technol. Lett._ 2006, _18_ , 193–195
  * Chen et al. 2006 Chen, H.-S.; Yeh, D.-M.; Lu, C.-F.; Huang, C.-F.; Shiao, W.-Y.; Huang, C. C., Jian-Jang amd Yang; Liu, I.-S.; Su, W.-F. White Light Generation with CdSe-ZnS Nanocrystals Coated on an InGaN-GaN Quantum-Well Blue/Green Two-Wavelength Light-Emitting Diode. _IEEE Photonics Technol. Lett._ 2006, _18_ , 1430–1432
  * Achermann et al. 2006 Achermann, M.; Petruska, M. A.; Koleske, D. D.; Crawford, M. H.; Klimov, V. I. Nanocrystal-Based Light-Emitting Diodes Utilizing High-Efficiency Nonradiative Energy Transfer for Color Conversion. _Nano Lett._ 2006, _6_ , 1396–1400
  * Korgel and Fitzmaurice 1998 Korgel, B. A.; Fitzmaurice, D. Condensation of Ordered Nanocrystal Thin Films. _Phys. Rev. Lett._ 1998, _80_ , 3531–3534
  * Brust et al. 1994 Brust, M.; Walker, M.; Bethell, D.; Schiffrin, D. J.; Whyman, R. Synthesis of Thiol-Derivatised Gold Nanoparticles in a Two-Phase Liquid–Liquid System. _J. Chem. Soc., Chem. Commun._ 1994, _0_ , 801–802
  * Puntes et al. 2001 Puntes, V. F.; Krishnan, K. M.; Alivisatos, A. P. Colloidal Nanocrystal Shape and Size Control: The Case of Cobalt. _Science_ 2001, _291_ , 2115–2117
  * Napper 1977 Napper, D. Steric Stabilization. _J. Colloid Interface Sci._ 1977, _58_ , 390–407
  * Sigman et al. 2004 Sigman, M. B.; Saunders, A. E.; Korgel, B. A. Metal Nanocrystal Superlattice Nucleation and Growth. _Langmuir_ 2004, _20_ , 978–983
  * Bodnarchuk et al. 2010 Bodnarchuk, M. I.; Kovalenko, M. V.; Heiss, W.; Talapin, D. V. Energetic and Entropic Contributions to Self-Assembly of Binary Nanocrystal Superlattices: Temperature as the Structure-Directing Factor. _J. Am. Chem. Soc._ 2010, _132_ , 11967–11977
  * Schapotschnikow et al. 2008 Schapotschnikow, P.; Pool, R.; Vlugt, T. J. H. Molecular Simulations of Interacting Nanocrystals. _Nano Lett._ 2008, _8_ , 2930–2934
  * Patel and Egorov 2007 Patel, N.; Egorov, S. A. Interactions between Sterically Stabilized Nanoparticles in Supercritical Fluids: A Simulation Study. _J. Chem. Phys._ 2007, _126_ , 054706
  * Khan et al. 2009 Khan, S. J.; Pierce, F.; Sorensen, C. M.; Chakrabarti, A. Self-Assembly of Ligated Gold Nanoparticles: Phenomenological Modeling and Computer Simulations. _Langmuir_ 2009, _25_ , 13861–13868
  * Dalmaschio et al. 2013 Dalmaschio, C. J.; da Silveira Firmiano, E. G.; Pinheiro, A. N.; Sobrinho, D. G.; Farias de Moura, A.; Leite, E. R. Nanocrystals Self-Assembled in Superlattices Directed by the Solvent-Organic Capping Interaction. _Nanoscale_ 2013, _5_ , 5602–10
  * Widmer-Cooper and Geissler 2014 Widmer-Cooper, A.; Geissler, P. Orientational Ordering of Passivating Ligands on CdS Nanorods in Solution Generates Strong Rod-Rod Interactions. _Nano Lett._ 2014, _14_ , 57–65
  * Moura et al. 2015 Moura, F. D.; Bernardino, K.; Dalmaschio, C. J.; Leite, E. R.; Kotov, N. A. Thermodynamic Insights into the Self-Assembly of Capped Nanoparticles Using Molecular Dynamic. _Phys. Chem. Chem. Phys._ 2015, _17_ , 3820–3831
  * Talapin et al. 2001 Talapin, D. V.; Shevchenko, E. V.; Kornowski, A.; Gaponik, N.; Haase, M.; Rogach, A. L.; Weller, H. A New Approach to Crystallization of CdSe Nanoparticles into Ordered Three-Dimensional Superlattices. _Adv. Mater._ 2001, _13_ , 1868
  * Abécassis et al. 2008 Abécassis, B.; Testard, F.; Spalla, O. Gold Nanoparticle Superlattice Crystallization Probed In Situ. _Phys. Rev. Lett._ 2008, _100_ , 115504
  * Khan et al. 2012 Khan, S. J.; Sorensen, C. M.; Chakrabarti, A. Computer Simulations of Nucleation of Nanoparticle Superclusters from Solution. _Langmuir_ 2012, _28_ , 5570–5579
  * Kister et al. 2018 Kister, T.; Monego, D.; Mulvaney, P.; Widmer-Cooper, A.; Kraus, T. Colloidal Stability of Apolar Nanoparticles: The Role of Particle Size and Ligand Shell Structure. _ACS Nano_ 2018, _12_ , 5969–5977
  * Monego et al. 2018 Monego, D.; Kister, T.; Kirkwood, N.; Mulvaney, P.; Widmer-Cooper, A.; Kraus, T. Colloidal Stability of Apolar Nanoparticles: Role of Ligand Length. _Langmuir_ 2018, _34_ , 12982–12989
  * Lohman et al. 2012 Lohman, B. C.; Powell, J. A.; Cingarapu, S.; Aakeroy, C. B.; Chakrabarti, A.; Klabunde, K. J.; Law, B. M.; Sorensen, C. M. Solubility of Gold Nanoparticles as a Function of Ligand Shell and Alkane Solvent. _Phys. Chem. Chem. Phys._ 2012, _14_ , 6509–6513
  * Hajiw et al. 2015 Hajiw, S.; Schmitt, J.; Imperor-Clerc, M.; Pansu, B. Solvent-Driven Interactions between Hydrophobically-Coated Nanoparticles. _Soft Matter_ 2015, _11_ , 3920–3926
  * de Gennes 1980 de Gennes, P. G. Conformations of Polymers Attached to an Interface. _Macromolecules_ 1980, _13_ , 1069–1075
  * Koski et al. 2019 Koski, J. P.; Krook, N. M.; Ford, J.; Yahata, Y.; Ohno, K.; Murray, C. B.; Frischknecht, A. L.; Composto, R. J.; Riggleman, R. A. Phase Behavior of Grafted Polymer Nanocomposites from Field-Based Simulations. _Macromolecules_ 2019, _52_ , 5110–5121
  * Sunday et al. 2012 Sunday, D.; Ilavsky, J.; Green, D. L. A Phase Diagram for Polymer-Grafted Nanoparticles in Homopolymer Matrices. _Macromolecules_ 2012, _45_ , 4007–4011
  * Sunday and Green 2015 Sunday, D. F.; Green, D. L. Thermal and Rheological Behavior of Polymer Grafted Nanoparticles. _Macromolecules_ 2015, _48_ , 8651–8659
  * Zou et al. 2017 Zou, Y.; Ban, M.; Cui, W.; Huang, Q.; Wu, C.; Liu, J.; Wu, H. A General Solvent Selection Strategy for Solution Processed Quantum Dots Targeting High Performance Light-Emitting Diode. _Adv. Funct. Mater._ 2017, _27_ , 1603325
  * Fini et al. 2008 Fini, P.; Depalo, N.; Comparelli, R.; Curri, M. L.; Striccoli, M.; Castagnolo, M.; Agostiano, A. Interactions between Surfactant Capped CdS Nanocrystals and Organic Solvent. _J. Therm. Anal. Calorim._ 2008, _92_ , 271–277
  * Widmer-Cooper and Geissler 2016 Widmer-Cooper, A.; Geissler, P. L. Ligand-Mediated Interactions between Nanoscale Surfaces Depend Sensitively and Nonlinearly on Temperature, Facet Dimensions, and Ligand Coverage. _ACS Nano_ 2016, _10_ , 1877–87
  * Johnson 1959 Johnson, J. E. X-Ray Diffraction Studies of the Crystallinity in Polyethylene Terephthalate. _J. Appl. Polym. Sci._ 1959, _2_ , 205–209
  * Brandrup et al. 1999 Brandrup, J.; Immergut, E. H.; Grulke, E. A. _Polymer Handbook_ ; Wiley-Interscience: New York, 1999; p 2250
  * Costa et al. 2018 Costa, J.; Mendes, A.; Santos, L. Chain Length Dependence of the Thermodynamic Properties of n-Alkanes and their Monosubstituted Derivatives. _J. Chem. Eng. Data_ 2018, _63_ , 1
  * Roke et al. 2006 Roke, S.; Berg, O.; Buitenhuis, J.; Blaaderen, A. V.; Bonn, M. Surface Molecular View of Colloidal Gelation. _Proc. Natl. Acad. Sci. USA_ 2006, _103_ , 13310–13314
  * Roo et al. 2018 Roo, J. D.; Yazdani, N.; Drijvers, E.; Lauria, A.; Maes, J.; Owen, J. S.; Driessche, I. V.; Niederberger, M.; Wood, V.; Martins, J. C.; Infante, I.; Hens, Z. Probing Solvent-Ligand Interactions in Colloidal Nanocrystals by the NMR Line Broadening. _Chem. Mater._ 2018, _30_ , 5485–5492
  * Ruks et al. 2019 Ruks, T.; Beuck, C.; Schaller, T.; Niemeyer, F.; Zähres, M.; Loza, K.; Heggen, M.; Hagemann, U.; Mayer, C.; Bayer, P.; Epple, M. Solution NMR Spectroscopy with Isotope-Labeled Cysteine (13C and 15N) Reveals the Surface Structure of l-Cysteine-Coated Ultrasmall Gold Nanoparticles ($1.8\text{\,}\mathrm{nm}$). _Langmuir_ 2019, _35_ , 767–778
  * Luo et al. 2018 Luo, Z.; Marson, D.; Ong, Q. K.; Loiudice, A.; Kohlbrecher, J.; Radulescu, A.; Krause-Heuer, A.; Darwish, T.; Balog, S.; Buonsanti, R.; Svergun, D. I.; Posocco, P.; Stellacci, F. Quantitative 3D Determination of Self-Assembled Structures on Nanoparticles Using Small Angle Neutron Scattering. _Nat. Commun._ 2018, _9_ , 1343
  * Lane and Grest 2010 Lane, J. M. D.; Grest, G. S. Spontaneous Asymmetry of Coated Spherical Nanoparticles in Solution and at Liquid-Vapor Interfaces. _Phys. Rev. Lett._ 2010, _104_ , 235501
  * Bolintineanu et al. 2014 Bolintineanu, D. S.; Lane, J. M. D.; Grest, G. S. Effects of Functional Groups and Ionization on the Structure of Alkanethiol-Coated Gold Nanoparticles. _Langmuir_ 2014, _30_ , 11075–11085
  * Kister et al. 2016 Kister, T.; Mravlak, M.; Schilling, T.; Kraus, T. Pressure-Controlled Formation of Crystalline, Janus, and Core-Shell Supraparticles. _Nanoscale_ 2016, _8_ , 13377–13384
  * Chambrier et al. 2015 Chambrier, I.; Banerjee, C.; Remiro-Buenamañana, S.; Chao, Y.; Cammidge, A. N.; Bochmann, M. Synthesis of Porphyrin-CdSe Quantum Dot Assemblies: Controlling Ligand Binding by Substituent Effects. _Inorg. Chem._ 2015, _54_ , 7368–7380
  * Schnablegger and Singh 2013 Schnablegger, H.; Singh, Y. _The SAXS Guide: Getting Acquainted with the Principles_ ; Anton Paar GmbH: Graz, Austria, 2013; Vol. 2
  * Andersen 1983 Andersen, H. C. Rattle: A “Velocity” Version of the Shake Algorithm for Molecular Dynamics Calculations. _J. Comput. Phys._ 1983, _52_ , 24–34
  * Pool et al. 2007 Pool, R.; Schapotschnikow, P.; Vlugt, T. J. H. Solvent Effects in the Adsorption of Alkyl Thiols on Gold Structures: A Molecular Simulation Study. _J. Phys. Chem. C_ 2007, _111_ , 10201–10212
  * Martin and Siepmann 1998 Martin, M. G.; Siepmann, J. I. Transferable Potentials for Phase Equilibria. 1. United-Atom Description of n-Alkanes. _J. Phys. Chem. B_ 1998, _102_ , 2569–2577
  * Plimpton 1995 Plimpton, S. Fast Parallel Algorithms for Short-Range Molecular Dynamics. _J. Comput. Phys._ 1995, _117_ , 1–19
  * Humphrey et al. 1996 Humphrey, W.; Dalke, A.; Schulten, K. VMD: Visual Molecular Dynamics. _J. Mol. Graphics_ 1996, _14_ , 33–38
  * Hamaker 1937 Hamaker, H. C. The London-van der Waals Attraction between Spherical Particles. _Physica_ 1937, _4_ , 1058–1072
  * Ederth 2001 Ederth, T. Computation of Lifshitz-van der Waals Forces between Alkylthiol Monolayers on Gold Films. _Langmuir_ 2001, _17_ , 3329–3340
  * Suárez et al. 2011 Suárez, E.; Díaz, N.; Suárez, D. Entropy Calculations of Single Molecules by Combining the Rigid–Rotor and Harmonic-Oscillator Approximations with Conformational Entropy Estimations from Molecular Dynamics Simulations. _J. Chem. Theory Comput._ 2011, _7_ , 2638–2653


# Fast and Exact Enumeration of Deep Networks Partitions Regions

###### Abstract

One fruitful formulation of Deep Networks (DNs) enabling their theoretical
study and providing practical guidelines to practitioners relies on Piecewise
Affine Splines. In that realm, a DN’s input-mapping is expressed as per-region
affine mapping where those regions are implicitly determined by the model’s
architecture and form a partition of their input space. That partition –which
is involved in all the results spanned from this line of research– has so far
only been computed on $2/3$-dimensional slices of the DN’s input space or
estimated by random sampling. In this paper, we provide the first parallel
algorithm that does exact enumeration of the DN’s partition regions. The
proposed algorithm enables one to finally assess the closeness of the commonly
employed approximations methods, e.g. based on random sampling of the DN input
space. One of our key finding is that if one is only interested in regions
with “large” volume, then uniform sampling of the space is highly efficient,
but that if one is also interested in discovering the “small” regions of the
partition, then uniform sampling is exponentially costly with the DN’s input
space dimension. On the other hand, our proposed method has complexity scaling
linearly with input dimension and the number of regions.

##  1 Introduction

Fig. 1: Proposed exact region enumeration depicted as an orange star against
sampling-based region discovery of the partition $\Omega$ depicted as blue
dots for a single hidden layer DN with leaky-ReLU, random parameters and width
$64$ as a function of computation time (x-axis) and number of partition
regions found (y-axis); for a $4$-dimensional input space at the top and
$8$-dimensional input space at the bottom. The proposed Algorithm 1 is able to
dramatically outperform the sampling-based search that has been used
throughout recent studies on CPA DNs.

Deep Networks (DNs) are compositions of linear and nonlinear operators
altogether forming a differentiable functional $f_{{\bm{\theta}}}$ governed by
some trainable parameters ${\bm{\theta}}$ [1]. Understanding the underlying
properties that make DNs the great function approximators that they are
involve many different research directions e.g. the underlying implicit
regularization of architectures [2], or the impact of input and feature
normalization into the optimization landscape [3]. Most existing results
emerge from a few different mathematical formulations. One eponymous example
relies on kernels and emerges from pushing the DN’s layers width to infinity.
In this case, and under some additional assumptions, a closed-form expression
for the DN’s underlying embedding space metric is obtained [4]. With that
form, training dynamics and generalization bounds are amenable to theoretical
analysis [5]. Another line of research considers the case of deep linear
networks i.e. a DN without nonlinearities. In this setting, it is possible to
obtain the explicit regularizer that acts upon the DN’s functional and that
depends on the specifics of the architecture e.g. depth and with [6]. Another
direction, most relevant to our study, proposes to unravel the Continuous
Piecewise Affine (CPA) mapping of standard DNs [7]. In short, one can combine
the fact that (i) the nonlinearities present in most current DNs are
themselves CPA e.g. (leaky-)ReLU, absolute value, max-pooling, (ii) the
interleaved affine mappings preserve the CPA property, and (iii) composition
of CPA mappings remain CPA. Thus, the entire input-output DN is itself a CPA.
From that observation, it is possible to study the DN’s loss landscape [8],
the implicit regularizer of different architectures [9], the explicit
probabilistic distributions of CPA Deep Generative Networks [10, 11], the
approximation rates [12, 13], or even the conditions for adversarial
robustness guarantees [14, 15]. A striking benefit of the CPA viewpoint lies
in the fact that it is an exact mathematical description of the DN’s input-
output mapping without any approximation nor simplification. This makes the
obtained insights and guidelines highly relevant to improve currently deployed
state-of-the-art architectures.

Despite this active recent development of CPA-based results around DNs, one
key challenge remains open. In fact, because under this view one expresses the
DN mapping as a collection of affine mappings –one for each region $\omega$ of
some partition $\Omega$ of their input space– it becomes crucial to compute
that partition $\Omega$ or at least infer some statistics from it. Current
analytical characterizations of $\Omega$ are in fact insufficient e.g.
existing bounds characterizing the number of regions in $\Omega$ are known to
be loose and uninformative [16]. As such, practitioners resort to simple
approximation strategies, e.g. sampling, to estimate such properties of
$\Omega$. Another approach is to only consider $2/3$-dimensional slices of the
DN’s input space and estimate $\Omega$ restricted on that subspace. All in
all, nothing is known yet about how accurate are those approximations at
conveying the underlying properties of the entire partition $\Omega$ that
current theoretical results heavily rely on. In particular, [17] uses
estimates of the partition’s number of region to perform Neural Architecture
Search (NAS), and for which exact computation of the DNN’s partition regions
will further improve the NAS; [11] uses estimates of the partition to adapt
the distribution of deep generative networks (e.g. variational autoencoders)
and for which exact computation of the partition would make their method
exact, and not an approximation

In this paper, we propose a principled and provable enumeration method for DNs
partitions (Algorithm 1) that we first develop for a layer-wise analysis in
Section 2 and then extend to the multilayer case in Section 3. As depicted in
Fig. 1, the proposed method becomes exponentially faster than the sampling-
based strategy to discover the regions $\omega\in\Omega$ as the input
dimensionality increases. Practically, the proposed enumeration method enables
for the first time to measure the accuracy of the currently employed
approximations. Our method is efficiently implemented with a few lines of
codes, leverages parallel computations, and provably enumerates all the
regions of the DN’s partition. Lastly, our method has linear asymptotic
complexity with respect to the number of regions and with respect to the DN’s
input space dimension. This property is crucial as we will demonstrate that
sampling-based enumeration method has complexity growing exponentially with
respect to the DN’s input space dimension as a direct consequence of the curse
of dimensionality [18, 19]. We hope that our method will serve as the baseline
algorithm for any application requiring provable partition region enumeration,
or to assess the theoretical findings obtain from the CPA formulation of DNs.

##  2 Enumeration of Single-Layer Partitions

We now develop the enumeration algorithm for a single DN layer. Because a DN
recursively subdivides the per-layer partition, the single layer case will be
enough to iteratively compute the partition of a multilayer DN as shown in the
next Section 3.

###  2.1 Layer Partitions and Hyperplane Arrangements

We denote the single layer of a DN111without loss of generality we consider
the first layer, although the exact same analysis applies to any layer in the
DN when looking at the partition of its own input space input-output mapping
as $f_{{\bm{\theta}}}:\mathbb{R}^{D}\mapsto\mathbb{R}^{K}$, with
${\bm{\theta}}$ the parameters of the mapping. Without loss of generality, we
consider vectors as inputs since when dealing with images, one can always
flatten them into vectors and reparametrize the layer accordingly. The layer
mapping takes the form

$\displaystyle f_{{\bm{\theta}}}({\bm{x}})=\sigma({\bm{h}}({\bm{x}}))\text{
with }{\bm{h}}({\bm{x}})={\bm{W}}{\bm{x}}+{\bm{b}}$ (1)

where $\sigma$ is a pointwise activation function, ${\bm{W}}$ is a weight
matrix of dimensions $K\times D$, ${\bm{b}}$ is a bias vector of length $K$,
${\bm{h}}({\bm{x}})$ denotes the pre-activation map and lastly ${\bm{x}}$ is
some input from $\mathbb{R}^{D}$. The layer parameters are thus
${\bm{\theta}}\triangleq\\{{\bm{W}},{\bm{b}}$. Although simple, Eq. 1
encompasses most current DNs layers by specifying the correct structural
constraints on the matrix ${\bm{W}}$, e.g. to be circulant for a convolutional
layer. The details on the layer mapping will not impact our results. The CPA
view of DNs [20, 7] consists in expressing Eq. 1 as

$\displaystyle
f_{{\bm{\theta}}}({\bm{x}})=\sum_{\omega\in\Omega}({\bm{A}}_{\omega}{\bm{x}}+{\bm{b}}_{\omega})1_{\\{{\bm{z}}\in\omega\\}},$
(2)

where $\Omega$ is the layer input space partition [21]. Understanding the form
of $\Omega$ will greatly help the development of the enumeration algorithm in
Section 2.2. Given nonlinearities $\sigma$ such as (leaky-)ReLU or absolute
value, it is direct to see that the layer stays linear for a region $\omega$
so that all the inputs within it have the same pre-activation signs. That is,
a region is entirely and uniquely determined by those sign patterns

$\displaystyle f_{{\bm{\theta}}}\text{ affine on
$\omega$}\iff\operatorname{sign}({\bm{h}}({\bm{x}}))=\operatorname{sign}({\bm{h}}({\bm{x}}^{\prime})),\forall({\bm{x}},{\bm{x}}^{\prime})\in\omega^{2},$

where the equality is to be understood elementwise on all of the $K$ entries
of the sign vectors. The only exception arises for degenerate weights
${\bm{W}}$ which we do not consider since any arbitrarily small perturbation
of such degeneracies remove those edge cases. From the above observation
along, it becomes clear that the transition between different regions of
$\Omega$ must occur when a pre-activation sign for some unit
$k\in\\{1,\dots,K\\}$ changes, and because ${\bm{h}}$ is nothing more but an
affine mapping, this sign change for some unit $k$ can only occur when
crossing the hyperplane

$\displaystyle{\mathbb{H}}_{k}\triangleq\\{{\bm{x}}\in\mathbb{R}^{D}:\langle{\bm{W}}_{k,.},{\bm{x}}\rangle+{\bm{b}}_{k}=0\\}.$
(3)

Leveraging Eq. 3 we obtain that $\partial\Omega$, the boundaries of the
layer’s partition, is an hyperplane arrangement as in
$\partial\Omega=\bigcup_{k=1}^{K}{\mathbb{H}}_{k}$.

We are now able to leverage this particular structure of the layer’s partition
to present an enumeration algorithm that will recursively search for all the
regions $\omega\in\Omega$.

###  2.2 Region Enumeration Algorithm

From the previous understanding that the layer’s partition arises from an
hyperplane arrangements involving Eq. 3, we are now able to leverage and adapt
existing enumeration methods for such partitions to obtain all the regions
$\omega\in\Omega$, form which it will become trivial to consider the
multilayer case that we leave for the following Section 3.

Enumerating the regions of the layer $f_{{\bm{\theta}}}$’s partition can be
done efficiently by adapting existing reverse search algorithms [22] optimized
for hyperplane arrangements. In fact, a naive approach of enumerating all of
the $2^{K}$ possible sign patterns ${\bm{q}}\in\\{-1,1\\}^{K}$ and checking if
each defines a non-empty region

$\displaystyle\bigcap_{k=1}^{K}\left\\{{\bm{x}}\in\mathbb{R}^{D}:\left(\langle{\bm{W}}_{k,.},{\bm{x}}\rangle+{\bm{b}}_{k}\right){\bm{q}}_{k}\geq
0\right\\}\overset{?}{=}\emptyset,$

would be largely wasteful. In fact, most of such sign combinations do produce
empty regions e.g. if the partition is central i.e. the intersection of all
the hyperplane is not empty then the total number of regions grows linearly
with $K$ [23] and is thus much smaller than $2^{K}$. Instead, a much more
efficient strategy is to only explore feasible sign patterns in a recursive
tree-like structure. To do so, the algorithm recursively sub-divides a parent
region by the hyperplane of unit $k$. If that hyperplane does not intersect
the current region then we can skip unit $k$ and recurse the sub-division of
that same region by unit $k+1$. On the other hand, if hyperplane $k$ divides
the current region, we consider both sides of it and keep the recursion going
on both sides. We formally summarize the method in Algorithm 1 and present one
illustrative example and comparison against sampling-based region enumeration
in Fig. 1. In particular, we provide the efficiency of the sampling solution
for various configurations in Table 1.

Algorithm 1 Proposed region enumeration method for the single hidden layer
case that recursively searches over the feasible sign patterns ${\bm{q}}$ one
unit at a time, and only explores the branches that coincide with non-empty
region i.e. avoiding the $2^{K}$ total number of possible of combinations. The
step checking for intersection between an hyperplane and a given polytopal
region can be done easily by setting up a linear program with dummy constant
objective, the hyperplane as a linear constraint, and the polytopal region as
inequality constraint; during the feasibility check the test will fail if the
intersection is empty. This algorithm is obtained to provide the results from
Figs. 1 and 1. The algorithm terminates once all the regions of the partition
$\Omega$ have been visited.

1:${\bm{W}}\in\mathbb{R}^{K\times
D},{\bm{b}}\in\mathbb{R}^{K},k\in\\{1,\dots,K\\},{\bm{q}}\in\\{-1,0,1\\}^{k}$

2:if ${\bf k\overset{?}{=}K+1}$ then this branch has reached a leaf, the sign
pattern ${\bm{q}}$ is feasible and can be accumulated into $\Omega$’s current
estimate

3:Check if the hyperplane defined by $({\bm{w}}_{k},{\bm{b}}_{k})$ intersects
the polytopal region defined by
$\bigcap_{j=1}^{k-1}\\{{\bm{x}}\in\mathbb{R}^{D}:(\langle{\bm{w}}_{j},{\bm{x}}\rangle+{\bm{b}}_{j}){\bm{q}}_{j}\geq
0\\}$

4:if NO then unit $j$ is redundant, call the routine again with
$[{\bm{q}}_{j},0]$ as ${\bm{q}}$ and $k+1$ as $k$

5:if YES then unit $j$ splits the region into two, call the routine again with
$[{\bm{q}}_{j},1]$ and $k+1$ and $[{\bm{q}}_{j},-1]$ and $k+1$

6:${\bm{X}}^{(L)}$$\triangleright$ Evaluate loss and back-propagate as usual

Table 1: Comparison of our exact enumeration method versus sampling-based partition discovery for various single layer configurations with random weights and biases. The sampling-based discovery is run $5$ times and we report the average and standard deviation of the number of regions found after sampling. The number of input space sample is obtain so that the computation time of the proposed method is the same as the computation time of the sampling method i.e. for each configuration, both methods have run the exact same amount of time. We observe that for low-dimensional input space, and with the same fixed time-budget, both methods perform similarly and sampling is sufficient to quickly discover all of the layer’s partition. input dim \width | K=16 | K=32 | K=64 | K=128 | K=256
---|---|---|---|---|---
D=2 | enumeration | 16 | 13 | 71 | 127 | 631
sampling |  16 $\pm$0 |  13 $\pm$0 |  67$\pm$0 |  127$\pm$0 |  611 $\pm$2
samp. found | 100% | 100 % | 94 % | 100 % | 96 %
D=4 | enumeration | 54 | 80 | 1107 | 4271 | 95954
sampling |  51 $\pm$0 |  69 $\pm$ 1 |  866$\pm$3 |  3288$\pm$18 |  70635 $\pm$55
samp. found | 94 % | 86 % | 78 % | 77% | 73%
D=8 | enumeration | 24 | 1242 | 8396 | 386566 | -
sampling |  18 $\pm$0 |  543$\pm$2 |  2875$\pm$5 |  136748$\pm$251 | -
samp. found | 75 % | 44 % | 34 % | 35 % | -
Fig. 2: Depiction of the multilayer case which corresponds to a union of
region-constrained hyperplane arrangements and thus which can be studied
directly form the proposed hyperplane arrangement region enumeration. The only
additional step is to first enforce that the search takes place on the
restricted region of interest from the up-to-layer-$\ell$ input space
partition. For example on the left column one first obtains the first layer
partition depicted in black. On each of the enumerated region, a subdivision
will be performed by the next layer; pick any region of interest, compose the
per-region affine mapping (fixed on that region) with the second layer affine
mappings, and repeat the region enumeration algorithm. This discovers the
second subdivision done by the second layer, highlighted in  blue  in the
middle column. This can be repeated to obtain the subdivision of the third
layer, here highlighted in  red  in the right column.

##  3 Enumeration of Multi-Layers Partitions

This section demonstrates how the derivation carried out in Section 2 for the
single layer setting is sufficient to enumerate the partition of a multilayer
DN, thanks to the subdivision process under which the composition of many
layers ultimately form the global DN’s input space partition. We first recall
this subdivision step in Section 3.1 and summarize the enumeration algorithm
in Section 3.2.

###  3.1 Deep Networks are Continuous Piecewise Affine

We specialize the per-layer notations from Section 2 by expliciting the layer
index $\ell$ as $f^{(\ell)}$ for the layer mapping, as
${\bm{\theta}}^{(\ell)}$ for its parameters, and the entire DN’s input-output
mapping is now referred to as
$f_{{\bm{\theta}}}:\mathbb{R}^{D}\mapsto\mathbb{R}^{K}$ with $K$ the output
space dimension. The composition of layers take the form

$\displaystyle
f_{{\bm{\theta}}}=\left(f_{{\bm{\theta}}^{(L)}}^{(L)}\circ\dots\circ
f_{{\bm{\theta}}^{(1)}}^{(1)}\right),$ (4)

where each layer mapping
$f^{(\ell)}:\mathbb{R}^{D^{(\ell)}}\mapsto\mathbb{R}^{D^{(\ell+1)}}$ produces
a feature map; with $D^{(1)}\triangleq D$ and $D^{(L)}\triangleq K$; with
mapping given by Eq. 1, and ${\bm{h}}^{(\ell)}$ denoting the pre-activation
map of layer $\ell$. A key result from [20, 7] is the DN mapping is itself
defined on a partition as in

$\displaystyle
f_{{\bm{\theta}}}({\bm{x}})=\sum_{\omega\in\Omega}({\bm{A}}_{\omega}{\bm{x}}+{\bm{b}}_{\omega})1_{\\{{\bm{z}}\in\omega\\}},$

which is known to be recursively built by each layer subdividing the
previously built partition of the space [21].

###  3.2 Enumerating Union of Hyperplane Arrangements

Considering an arbitrarily deep model can be tackled by understanding the
recurrent subdivision process of a two hidden layer DN and applying the same
principle successively. In this setting, notice that for the (two-layer) DN to
be affine within some region $\omega$ of the DN’s input space, each layer must
stay affine as well. By composition the first layer staying linear does not
ensure that the DN stays linear, but the first layer being nonlinear does
imply that the entire DN is nonlinear. From that, we see that the first
layer’s partition are “coarser” the the entire DN’s partition regions. More
precisely, and following the derivation of [21], we obtain that each layer is
a recursive subdivision of the previously build partition when in our case we
need to search for each region $\omega$ of the first layer’s partition the
regions within it where the second layer stays linear. As a result, the
proposed single hidden layer enumeration method from Section 2 can be applied
recursively as follows. First, compute the first layer partition enumeration.
Then, for each enumerated region with corresponding sign pattern ${\bm{q}}$,
define a new single layer model with
${\bm{h}}({\bm{x}})\triangleq\sigma({\bm{W}}^{(2)}\operatorname{diag}({\bm{q}}){\bm{W}}^{(1)}{\bm{x}}+{\bm{W}}^{(2)}({\bm{q}}\odot{\bm{b}}^{(1)})+{\bm{b}}^{(2)}$
and within $\omega$ apply the single layer enumeration; repeating the process
for all regions –and corresponding sign patterns ${\bm{q}}$ of the previously
found first layer partition. This enumerates the partition of $(f^{(2)}\circ
f^{(1)})$, and the same process can be repeated as many times as there are
layers in the DN; as illustrated in Fig. 2.

##  4 Conclusion and Future Work

In this paper, we provided the first exact enumeration method for Deep
Networks partitions that relies on the existing highly efficient enumeration
method of hyperplane arrangements. In fact, both the hallow and deep
architectures produce partitions that correspond to hyperplane arrangements or
union of restricted hyperplane arrangements. A crucial finding that was
enabled by the proposed method is that sampling-based region enumeration,
which is the only strategy used in current research studies dealing with DNs
and affine splines, is in fact relatively poor at finding the regions of the
DN’s partition. In particular, when using such sampling to estimating some
sensitive statistics e.g. the volume of the smallest region, sampling is
biased and should be avoid in favor of an exact enumeration method.

## References

  * [1] Yann LeCun, Yoshua Bengio, and Geoffrey Hinton,  “Deep learning,”  nature, vol. 521, no. 7553, pp. 436–444, 2015.
  * [2] Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro,  “In search of the real inductive bias: On the role of implicit regularization in deep learning,”  arXiv preprint arXiv:1412.6614, 2014.
  * [3] Yann Le Cun, Ido Kanter, and Sara A Solla,  “Eigenvalues of covariance matrices: Application to neural-network learning,”  Physical Review Letters, vol. 66, no. 18, pp. 2396, 1991.
  * [4] Arthur Jacot, Franck Gabriel, and Clément Hongler,  “Neural tangent kernel: Convergence and generalization in neural networks,”  arXiv preprint arXiv:1806.07572, 2018.
  * [5] Kaixuan Huang, Yuqing Wang, Molei Tao, and Tuo Zhao,  “Why do deep residual networks generalize better than deep feedforward networks?—a neural tangent kernel perspective,”  Advances in neural information processing systems, vol. 33, pp. 2698–2709, 2020.
  * [6] Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro,  “The implicit bias of gradient descent on separable data,”  The Journal of Machine Learning Research, vol. 19, no. 1, pp. 2822–2878, 2018.
  * [7] Randall Balestriero and Richard Baraniuk,  “A spline theory of deep learning,”  in International Conference on Machine Learning. PMLR, 2018, pp. 374–383.
  * [8] Rudolf H Riedi, Randall Balestriero, and Richard G Baraniuk,  “Singular value perturbation and deep network optimization,”  arXiv preprint arXiv:2203.03099, 2022.
  * [9] Randall Balestriero and Richard G Baraniuk,  “From hard to soft: Understanding deep network nonlinearities via vector quantization and statistical inference,”  arXiv preprint arXiv:1810.09274, 2018.
  * [10] Randall Balestriero, Sébastien Paris, and Richard Baraniuk,  “Analytical probability distributions and exact expectation-maximization for deep generative networks,”  Advances in neural information processing systems, vol. 33, pp. 14938–14949, 2020.
  * [11] Ahmed Imtiaz Humayun, Randall Balestriero, and Richard Baraniuk,  “Polarity sampling: Quality and diversity control of pre-trained generative networks via singular values,”  in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2022, pp. 10641–10650.
  * [12] Ingrid Daubechies, Ronald DeVore, Simon Foucart, Boris Hanin, and Guergana Petrova,  “Nonlinear approximation and (deep) relu networks,”  Constructive Approximation, vol. 55, no. 1, pp. 127–172, 2022.
  * [13] Randall Balestriero and Richard G Baraniuk,  “Batch normalization explained,”  arXiv preprint arXiv:2209.14778, 2022.
  * [14] Lily Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsieh, Luca Daniel, Duane Boning, and Inderjit Dhillon,  “Towards fast computation of certified robustness for relu networks,”  in International Conference on Machine Learning. PMLR, 2018, pp. 5276–5285.
  * [15] Aditi Raghunathan, Jacob Steinhardt, and Percy S Liang,  “Semidefinite relaxations for certifying robustness to adversarial examples,”  Advances in Neural Information Processing Systems, vol. 31, 2018\.
  * [16] Herbert Edelsbrunner,  Algorithms in combinatorial geometry, vol. 10,  Springer Science & Business Media, 1987.
  * [17] Wuyang Chen, Xinyu Gong, and Zhangyang Wang,  “Neural architecture search on imagenet in four gpu hours: A theoretically inspired perspective,”  arXiv preprint arXiv:2102.11535, 2021.
  * [18] Richard E Bellman and Stuart E Dreyfus,  Applied dynamic programming, vol. 2050,  Princeton university press, 2015.
  * [19] Mario Köppen,  “The curse of dimensionality,”  in 5th online world conference on soft computing in industrial applications (WSC5), 2000, vol. 1, pp. 4–8.
  * [20] Guido F Montufar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio,  “On the number of linear regions of deep neural networks,”  Advances in neural information processing systems, vol. 27, 2014\.
  * [21] Randall Balestriero, Romain Cosentino, Behnaam Aazhang, and Richard Baraniuk,  “The geometry of deep networks: Power diagram subdivision,”  Advances in Neural Information Processing Systems, vol. 32, 2019\.
  * [22] David Avis and Komei Fukuda,  “Reverse search for enumeration,”  Discrete applied mathematics, vol. 65, no. 1-3, pp. 21–46, 1996\.
  * [23] Richard P Stanley et al.,  “An introduction to hyperplane arrangements,”  Geometric combinatorics, vol. 13, no. 389-496, pp. 24, 2004.