We start from $4\times 4=16$ possible shifts between categories, but I claim
we only need to consider $\binom{4}{2}=6$ of these. Because all non-zero edges
are assumed to have the same magnitude (or equivalently for now we neglect to
consider changes in magnitude), any shift from the same category to itself can
be assumed to be the “identity” shift that does nothing. Hence any objective
function, reasonable or not, will register no change in values for any of
these $4$ “identity” shifts. This leaves $16-4=12$ shifts to consider.

After Shift trivial sign agreement trivial sign disagreement non-trivial sign
agreement non-trivial sign disagreement Before Shift trivial sign agreement no
change ? ? ? trivial sign disagreement ? no change ? ? non-trivial sign
agreement ? ? no change ? non-trivial sign disagreement ? ? ? no change

Table 8.B.2: Taking “identity” shifts into account

For the remaining $12$ shifts, note that we only need to consider $12/2=6$
shifts due to the elementary fact that $x_{1}\leq x_{2}$ if and only if
$x_{2}\geq x_{1}$. For example, how an objective function changes in response
to a shift from a trivial sign agreement to a non-trivial sign disagreement
completely determines how it changes in response to a shift from a non-trivial
sign disagreement to a trivial sign agreement.

After Shift trivial sign agreement trivial sign disagreement non-trivial sign
agreement non-trivial sign disagreement Before Shift trivial sign agreement no
change ? ? ? trivial sign disagreement opposite of value across diagonal no
change ? ? non-trivial sign agreement opposite of value across diagonal
opposite of value across diagonal no change ? non-trivial sign disagreement
opposite of value across diagonal opposite of value across diagonal opposite
of value across diagonal no change

Table 8.B.3: Pointing out redundant specifications.

Elementary considerations already determine how a “reasonable” objective
should behave for $4$ of the $6$ non-redundant shifts. Namely, it’s clear that
when shifting from any “agreement” to any “disagreement” that a “reasonable”
dissimilarity $\mathscr{D}$ function should not decrease and that a
“reasonable” similarity $\mathscr{S}$ function should not increase. I will
write “$\mathscr{D}\underline{\uparrow}\,,\mathscr{S}\underline{\downarrow}$”
to indicate a non-decreasing change in value for a “reasonable” dissimilarity
$\mathscr{D}$/a non-increasing change in value for a “reasonable” similarity
$\mathscr{S}$.

This is equivalent to the stipulation that, when shifting from any
“disagreement” to any “agreement”, a “reasonable” dissimilarity $\mathscr{D}$
function should not increase and that a “reasonable” similarity $\mathscr{S}$
function should not decrease. I will write
“$\mathscr{D}\underline{\downarrow}\,,\mathscr{S}\underline{\uparrow}$” to
indicate a non-increasing change in value for a “reasonable” dissimilarity
$\mathscr{D}$/a non-decreasing change in value for a “reasonable” similarity
$\mathscr{S}$.

After Shift trivial sign agreement trivial sign disagreement non-trivial sign
agreement non-trivial sign disagreement Before Shift trivial sign agreement no
change $\mathscr{D}\underline{\uparrow}\,,\mathscr{S}\underline{\downarrow}$ ?
$\mathscr{D}\underline{\uparrow}\,,\mathscr{S}\underline{\downarrow}$ trivial
sign disagreement
$\mathscr{D}\underline{\downarrow}\,,\mathscr{S}\underline{\uparrow}$ no
change $\mathscr{D}\underline{\downarrow}\,,\mathscr{S}\underline{\uparrow}$ ?
non-trivial sign agreement opposite of value across diagonal
$\mathscr{D}\underline{\uparrow}\,,\mathscr{S}\underline{\downarrow}$ no
change $\mathscr{D}\underline{\uparrow}\,,\mathscr{S}\underline{\downarrow}$
non-trivial sign disagreement
$\mathscr{D}\underline{\downarrow}\,,\mathscr{S}\underline{\uparrow}$ opposite
of value across diagonal
$\mathscr{D}\underline{\downarrow}\,,\mathscr{S}\underline{\uparrow}$ no
change

Table 8.B.4: Trivial considerations taken into account.

Note that technically it’s redundant to specify the behavior of both a
“reasonable” dissimilarity $\mathscr{D}$ and a “reasonable” similarity
$\mathscr{S}$, because one should transform to the other via a non-increasing
transformation474747 If a function $\psi$ is monotone nonincreasing,
$x_{1}\leq x_{2}\implies\psi(x_{1})\geq\psi(x_{2})$ for all $x_{1},x_{2}$,
then given a dissimilarity function
$\mathscr{D}:\mathscr{G}_{[S]}\times\mathscr{G}_{[S]}\to\mathbb{R}$,
$\psi(\mathscr{D})$ is always a similarity function, and likewise given a
similarity function
$\mathscr{S}:\mathscr{G}_{[S]}\times\mathscr{G}_{[S]}\to\mathbb{R}$ one has
that $\psi(\mathscr{S})$ is always a dissimilarity function. The analysis of
dissimilarity functions can always be reduced to the analysis of similarity
functions, and vice versa. . I note both behaviors explicitly for the sake of
expositional clarity, not mathematical necessity.

#####  8.B.5 Choices Available After Imposing “Trivial” Constraints

Comparing with table 8.B.4, we see that this leaves only two kinds of shifts
for which the behavior of a “reasonable” objective function is not trivially
determined. Both remaining shifts are shifts “within agreement or
disagreement”, and “between non-triviality and triviality”.

First, there is the shift from a trivial sign disagreement to a non-trivial
sign disagreement (or equivalently in the sense of table 8.B.3 the shift from
a non-trivial sign disagreement to a trivial sign disagreement).

Second, there is the shift from a trivial sign agreement to a non-trivial sign
agreement (or equivalently in the sense of table 8.B.3 the shift from a non-
trivial sign agreement to a trivial sign agreement).

Comparing the principles mentioned in section 2, we see that:

  1. 1.

the “double penalization principle” from section 2.5 is the choice espoused
herein to address shifts from a trivial sign disagreement to a non-trivial
sign disagreement, and

  2. 2.

the “sparsity savviness principle” from section 2.7 is the choice espoused
herein to address shifts from a trivial sign agreement to a non-trivial sign
agreement.

What the “correct” behavior for “reasonable” objectives for these two kinds of
shifts is perhaps more arguable or subjective than for the others. Certainly
the terminology “trivial” and “non-trivial” belies the opinions espoused
herein. Namely, shifting from a “trivial” disagreement to a “non-trivial”
disagreement should “amplify” the disagreement, and therefore correspond to a
non-decrease for a dissimilarity $\mathscr{D}$ function/a non-increase for a
similarity $\mathscr{S}$ function, i.e.
$\mathscr{D}\underline{\uparrow}\,,\mathscr{S}\underline{\downarrow}$.
Likewise, shifting from a “trivial” agreement to a “non-trivial”
agreement484848Again, ceteris paribus, not (yet) taking magnitude differences
into account. should “amplify” the agreement, and therefore correspond to a
non-increase for a dissimilarity $\mathscr{D}$ function/a non-decrease for a
similarity $\mathscr{S}$ function, i.e.
$\mathscr{D}\underline{\downarrow}\,,\mathscr{S}\underline{\uparrow}$.

#####  8.B.6 “Composability” Constraints for Objective Functions

One can argue fairly strongly on the basis of preferring “consistency”,
“composability”, “continuity” of behavior of “rational” objectives for the
double penalization principle.

Sparsity-savviness is compatible with the argument for “composability”
constraints on “rational” objectives, but is also not supported by the
argument.

This is analogous to another discrepancy between the double penalization
principle and the sparsity-savviness principle. Namely, double penalization is
straightforwardly compatible with how to reasonably penalize considering
magnitude differences whereas sparsity-savviness is not. See section 8.B.7
below for a further discussion of this.

I believe that both discrepancies in fact share the same underlying cause.
Unfortunately however I am not currently sure how to make any of this precise
enough to falsify or confirm.

Consider the following undirected network:

Figure 8.B.2: Spoke graph for the “edit” relationships of the four single-edge
comparisons.

Each node represents a different category of single-edge comparison, cf. again
table 8.B.1. Two nodes are connected if one can be transformed to another by
changing, or “editing”, one of the two signs in the comparison to an “adjacent
sign”. By “adjacent sign” I mean $\\{-,0\\}$ or $\\{0,+\\}$, corresponding to
the ordering of the signs on the number line. For example, starting with a
trivial agreement, $(0,0)$, making the second edge positive $(0,+)$
corresponds to a trivial sign disagreement, as does making the first edge
negative, $(-,0)$. However making both the second edge positive and the first
edge negative, $(-,+)$, is considered two changes or “edits”, and therefore
non-trivial sign disagreement is not adjacent to trivial sign agreement, but
rather separated by a path of length two. This is similar in spirit to the
“edit distance” discussed in [LPR19], but more abstract and with a different
definition of “edits”.

This spoke graph implies additional consistency conditions for a “reasonable”
objective function to satisfy, besides the “trivial” ones from table 8.B.4.
Namely, given a shift between categories corresponding to a path of length
two, there are potentially two distinct “reasonable” behaviors implied by
figure 8.B.2: (1) the behavior corresponding to the “direct jump” from the
beginning of the path to the end of the path, (2) the behavior (if uniquely
defined) corresponding to the composition of the behaviors of the two “edits”
constituting the path. Requiring these two potentially distinct behaviors to
coincide is the “composability” criterion for “rational” objectives alluded to
above.

There are six directed paths of length two in the network from figure 8.B.2,
corresponding to three undirected paths of length two (cf. table 8.B.3 again
for why undirected suffices):

  1. 1.

A path between “trivial agreements” and “non-trivial agreements”,

  2. 2.

a path between “trivial agreements” and “non-trivial disagreements”, and

  3. 3.

a path between “non-trivial agreements” and “non-trivial disagreements”.

The last two belong to the “trivial” shifts from table 8.B.4 while the first
does not.

Looking at all $\binom{3}{2}=3$ pairs of these three undirected paths, we see
that neither of the two pairs that include the relevant path provide
unambiguous guidance for the behavior separating “trivial agreements” and
“non-trivial agreements” via the “composability” criterion. Cf. figures 3(a)
and 3(b) below. Hence, as mentioned before, “composability” neither provides
an argument for, nor an argument against, the sparsity-savviness principle.
Therefore one must look to other reasons to justify the Sparsity-Savviness
Principle as a desideratum.

(a) These two paths fail to usefully constrain any unknown shift, even if we
determined the shift between trivial and non-trivial disagreements.

(b) These two paths also fail to usefully constrain any unknown shift, even if
we determined the shift between trivial and non-trivial disagreements.

Figure 8.B.3: Using only the “trivial” behavior and the “composability”
criterion, no useful constraints emerge for the shift between trivial
agreement and non-trivial agreement.

However, the third pair of undirected paths provides an unambiguous choice of
behavior for one of the two shifts not decided by “trivial” considerations
alone. Cf. figure 8.B.4 below. Thus “composability” argues strongly in favor
of requiring the double penalization principle.

Figure 8.B.4: The “trivial” behavior combined with the “composability”
criterion suggest only one possible option for the behavior of the unknown
shift. Thus the double penalization principle is highly motivated.

Technically the constraint from figure 8.B.4, that going from trivial
agreements to non-trivial disagreements never increases similarity, can be
satisfied without imposing the double penalization principle. Doing so would
require extra work however. Namely, for a given objective, one would have to
demonstrate that the first step (trivial agreements to trivial disagreements)
of the two part path from trivial agreements to non-trivial disagreements
would always non-increase similarity more than any increase in similarity that
might possibly occur during the second step (trivial disagreements to non-
trivial disagreements), i.e. that the change corresponding to the first step
would always be large enough to cancel out that from the second step and thus
able to determine the overall trend by itself.

On the other hand, as figure 8.B.4 demonstrates, if we only consider objective
functions to be “rational” when shifts from trivial disagreements to non-
trivial disagreements non-decrease dissimilarity
$\mathscr{D}\underline{\uparrow}$ (i.e. non-increase similarity
$\mathscr{S}\underline{\downarrow}$), no extra work is ever required to
satisfy the “composability” constraint. Restricting to such objective
functions of course corresponds to requiring that the double penalization
principle be satisfied.

#####  8.B.7 Taking Magnitude Differences into Account

The above subsections limited the discussion to unweighted (weights $\pm 1$)
networks, both to simplify the discussion and to serve as a starting point for
understanding the general weighted case. Preliminary steps towards the latter
goal are taken in this section.

I conjecture (cf. section 8.B.6) that the greater compatibility of the double
penalization principle, compared to the sparsity-savviness principle, with
both (i) the “composability” constraint and (ii) consideration of magnitude
differences, has one underlying cause.

(Assume in what follows that $x,y,z_{1},z_{2}>0$.) In the general case where
non-zero magnitudes can have values besides $1$, a non-trivial sign agreement
(between the corresponding edges of the compared networks) of the form
$(+z_{1},+z_{2})$ could very well deserve a penalty, depending on the size of
the magnitude difference $|z_{1}-z_{2}|$. This is in explicit contrast to the
unweighted case, where in the analogous situation $|z_{1}-z_{2}|=0$ always.

Of course, in both the unweighted and weighted cases, a non-trivial sign
disagreement of the form $(+x,-y)$ always deserves a penalty. To summarize:

  * •

In the unweighted case from before, there are never penalties arising from
magnitude differences of non-trivial agreements, so there is no need to
consider how to balance those with the penalties arising from sign differences
of non-trivial disagreements.

  * •

In the weighted case, we now must consider both kinds of penalties.

We need to consider whether, and to what extent, the ability to impose
penalties for both of these kinds of differences might come at the expense of
one another. This occurs especially when considering changes in the objective
functions for shifts from non-trivial agreements $(+z_{1},+z_{2})$ to non-
trivial disagreements $(+x,-y)$ (and vice versa). To answer that, we need to
know when the penalty for $(+z_{1},+z_{2})$ smaller or larger than that for
$(+x,-y)$.

According to the “composability” constraint, for “rational” objective
functions the change in value when shifting from $(+z_{1},+z_{2})$ to
$(+x,-y)$ should correspond to “composing”494949I.e. not necessarily
additively, but at least monotonically. the changes in value associated with
any “path” from $(+z_{1},+z_{2})$ to $(+x,-y)$.

(a) Generalized “composability” criteria for weighted and signed networks.

(b) Generalized “composability” criteria that already apply for weighted and
unsigned networks.

Figure 8.B.5: Generalized “composability” criteria for weighted networks.

Figure 5(a) depicts what those possible paths are. Here are two explicitly:

$\begin{array}[]{rcccccl}(+z_{1},+z_{2})&\to&(+x,+z_{2})&\to&(+x,0)&\to&(+x,-y)\\\
\operatorname{NTA}&\to&\operatorname{NTA}&\to&\operatorname{TDA}&\to&\operatorname{NTDA}\end{array}$
(8.B.5)

$\begin{array}[]{rcccccccl}(+z_{1},+z_{2})&\to&(0,+z_{2})&\to&(0,0)&\to&(+x,0)&\to&(+x,-y)\\\
\operatorname{NTA}&\to&\operatorname{TDA}&\to&\operatorname{TA}&\to&\operatorname{TDA}&\to&\operatorname{NTDA}\end{array}$
(8.B.6)

(In the above, “NTA” stands for “non-trivial agreement”, “NTDA” stands for
“non-trivial disagreement”, “TA” stands for “trivial agreement”, and “TDA”
stands for “trivial disagreement”.) We can get the remaining paths by
switching e.g. the roles of $z_{1}$ and $z_{2}$, or of $x$ and $y$. I don’t
believe that doing so alters any of the following conclusions.

In figure 5(a), all of the unknown values (“?”) that depend on how the
magnitudes of $z_{1}$, $z_{2}$, $x$, and $y$ compare correspond to the
following shifts (zero-step and one-step paths):

$\begin{array}[]{rcl}(+z_{1},+z_{2})&\to&(+x,+z_{2}\\\
\operatorname{NTA}&\to&\operatorname{NTA}\end{array}$ (8.B.7)

$\begin{array}[]{rcl}(+z_{1},+z_{2})&\to&(0,+z_{2})\\\
\operatorname{NTA}&\to&\operatorname{TDA}\end{array}$ (8.B.8)

$\begin{array}[]{rcl}(+x,+z_{2})&\to&(+x,0)\\\
\operatorname{NTA}&\to&\operatorname{TDA}\end{array}$ (8.B.9)

How to weight the changes in the objective function value corresponding to
each shift, and whether the changes are increases or decreases in penalty,
depends on what the specific magnitudes are, and which functions we choose for
computing penalties as a function of magnitude differences. These are what
determine the “?” arrows in figure 5(a).

None of these choices have anything to do with the double penalization
principle. The double penalization principle only dictates the behavior of the
arrows on the bottom of figure 5(a), namely that they should not decrease
dissimilarity. This amounts to making the gray dashed arrow, which corresponds
to both $(+x,0)\to(+x,-y)$ and $(0,-y)\to(+x,-y)$, another blue, similarity
non-increasing arrow, in addition to the arrows corresponding to
$(0,0)\to(+x,-y)$, $(0,0)\to(+x,0)$, and $(0,0)\to(0,y)$.

In fact all of the uncertain arrows correspond to choices that already have to
be made for purely unsigned networks. Cf. figure 5(b). Thus, if we are already
starting with a choice of objective function for weighted unsigned networks,
we are already mostly done as long as we impose the “composability”
constraint. In other words, in order to determine the “?” arrow from non-
trivial disagreements to non-trivial agreements (and reverse) for weighted and
signed networks, i.e. the shifts $(+z_{1},+z_{2})\leftrightarrow(+x,-y)$, all
we need to do is:

  * •

settle on a choice of comparison function for unsigned weighted networks to
start with – this settles the other three “?” arrows (again cf. figure 5(b)),

  * •

ensure that the gray dashed arrow at the bottom of figure 5(a) is determined
(most likely by insisting that the double penalization principle be
satisfied),

  * •

and require the “composability” constraint from section 8.B.6 above be
satisfied.

At no point do we ever have to explicitly or directly compare penalties for
non-trivial agreements and non-trivial disagreements, because their implicit
relative weighting follows from the three ingredients above, all of which we
would have already demanded anyway.

Hence, whether the double penalization principle is satisfied is not directly
relevant for determining implicit relative weighting of penalties for NTAs and
and NTDAs.

What instead determines that implicit relative weighting is the original
comparison function for unsigned and unweighted networks that we start with,
as well as how we ensure that monotonic “composability” is satisfied. We
should not need to directly compare NTA and NTDA penalties if we are starting
from and extending an objective function for unsigned networks. More
concretely:

  * •

the weighting of the NTA penalties relative to trivial agreements and
disagreements should be determined by the original objective function for
weighted, unsigned networks that is being extended, and

  * •

the weighting of the NTDA penalties relative to trivial agreements and
disagreements should be determined by the means of satisfying the double
penalization principle.

Then whatever ensures “composability” will then step in to use the above two
points to implicitly determine the relative weighting of the NTA and NTDA
penalties.

Of course, the devil is in the details. One would usually hope that monotonic
“composability” can be ensured for the signed extension in the same way it was
ensured for the unsigned version, thus requiring no extra work. However, given
how vaguely “composability” is “defined” herein, this guidance is currently at
best of limited use to a practitioner. To be more unambiguous, in the case of
entrywise-$L_{1}$ relative error and Jaccard similarity, this monotone
“composability” follows from the additivity of the expressions in the
numerators. I am not even entirely certain it is satisfied for the other
objectives, and may not be. Still, I hope the overall guiding principle is
still at least heuristically useful.

It seems that the compatibility of the double penalization principle with the
“composability” constraint implies that it can be satisfied without making any
explicit choice of “relative weighting” between (i) penalties for sign
differences and (ii) penalties for magnitude differences. In contrast, the
fact that the sparsity-savviness principle does require such a choice of
“relative weighting” seems to then imply its lack of inherent compatibility
with the “composability” constraint (roughly the contrapositive statement).
Again, as mentioned before, I am currently not sure how to make these
conjectures precise enough to falsify.

#####  8.B.8 Precise Formulation of Double Penalization Principle

Given a network with mixed-sign edge weights $\mathcal{G}$, as well as a
subset $E\subseteq\mathcal{E}(\mathcal{G})$, define the “erased edges network”
or “zeroed out edges network” $\mathcal{O}_{E}(\mathcal{G})$ as the network
with mixed-sign edge weights such that

$\mathcal{N}(\mathcal{O}_{E}(\mathcal{G}))=\mathcal{N}(\mathcal{G})\,,\quad\mathcal{E}(\mathcal{O}_{E}(\mathcal{G}))=\mathcal{E}(\mathcal{G})\setminus
E\,,\quad
A_{\mathcal{O}_{E}(\mathcal{G})}:=\begin{cases}A_{\mathcal{G}}(e)&e\not\in
E\,,\\\ 0&e\in E\end{cases}\,.$ (8.B.10)

Sometimes it helps to think of $\mathcal{O}_{E}(\mathcal{G})$ as a “sub-
network” of the original network $\mathcal{G}$. It can also be useful to think
of $\mathcal{O}_{E}(\mathcal{G})$ as a “sparsifying perturbation” of the
original network $\mathcal{G}$.

A “non-trivial sign disagreement” between two networks with mixed-sign edge
weights $\mathcal{G}_{1},\mathcal{G}_{2}$ occurs for a given edge
$e\in\mathcal{E}(\mathcal{G}_{1})\cap\mathcal{E}(\mathcal{G}_{2})$ if and only
if
${\operatorname{sign}(A_{\mathcal{G}_{1}}(e))\not=\operatorname{sign}(A_{\mathcal{G}_{2}}(e))}$.
Recall how, by definition, that an edge $e$ is in the edge set
$\mathcal{E}(\mathcal{G})$ of a given network $\mathcal{G}$,
$e\in\mathcal{E}(\mathcal{G})$, if and only if $A_{\mathcal{G}}(e)\not=0$. In
particular, a “trivial sign disagreement” between two networks with mixed-sign
edge weights $\mathcal{G}_{1},\mathcal{G}_{2}$ occurs for a given edge $e$ if
and only if
$\operatorname{sign}(A_{\mathcal{G}_{1}}(e))\not=\operatorname{sign}(A_{\mathcal{G}_{2}}(e))$
and either $\operatorname{sign}(A_{\mathcal{G}_{1}}(e))=0$ or
$\operatorname{sign}(A_{\mathcal{G}_{2}}(e))=0$, but not both, i.e. either
$e\not\in\mathcal{E}(\mathcal{G}_{1})$ or
$e\not\in\mathcal{E}(\mathcal{G}_{2})$ (but not both). Similarly, a “trivial
sign agreement” between two networks with mixed-sign edge weights
$\mathcal{G}_{1},\mathcal{G}_{2}$ occurs for a given edge $e$ if and only if
both $e\not\in\mathcal{E}(\mathcal{G}_{1})$ and
$e\not\in\mathcal{E}(\mathcal{G}_{2})$, i.e.
${\operatorname{sign}(A_{\mathcal{G}_{1}}(e))=0=\operatorname{sign}(A_{\mathcal{G}_{2}}(e))}$.
Finally, a “non-trivial sign agreement” between two networks with mixed-sign
edge weights $\mathcal{G}_{1},\mathcal{G}_{2}$ occurs for a given edge $e$ if
and only if $e\in\mathcal{E}(\mathcal{G}_{1})\cap\mathcal{E}(\mathcal{G}_{2})$
and
$\operatorname{sign}(A_{\mathcal{G}_{1}}(e))=\operatorname{sign}(A_{\mathcal{G}_{2}}(e))$.

Observe how, given a non-trivial sign disagreement for an edge
$e\in\mathcal{E}(\mathcal{G}_{1})\cap\mathcal{E}(\mathcal{G}_{2})$, there are
two erasures of $e$ that would replace the non-trivial sign disagreement with
a trivial sign disagreement, namely (1) erasing $e$ in $\mathcal{G}_{1}$ but
not in $\mathcal{G}_{2}$, and (2) erasing $e$ in $\mathcal{G}_{2}$ but not in
$\mathcal{G}_{1}$. The motivating idea behind the “Double Penalization
Principle” is that we should never “reward” non-trivial sign disagreements
over trivial sign disagreements. The penalty associated with a non-trivial
sign disagreement should be no less severe than either of the two penalties
that are associated with the two trivial sign disagreements resulting from
erasing the corresponding edge. This idea is illustrated in figure 8.2 above.

For two networks $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ with mixed-sign edge
weights, their “set of non-trivial sign disagreements”
$\mathscr{E}_{\pm}(\mathcal{G}_{1},\mathcal{G}_{2})\subseteq\mathcal{E}(\mathcal{G}_{1})\cap\mathcal{E}(\mathcal{G}_{2})$
is the set of “shared” edges such that

$\mathscr{E}_{\pm}(\mathcal{G}_{1},\mathcal{G}_{2}):=\\{e\subseteq\mathcal{E}(\mathcal{G}_{1})\cap\mathcal{E}(\mathcal{G}_{2}):\operatorname{sign}(A_{\mathcal{G}_{1}}(e))\not=\operatorname{sign}(A_{\mathcal{G}_{2}}(e))\\}\,.$
(8.B.11)

A dissimilarity function $\mathscr{D}$ satisfies the “weak double penalization
principle” (figure 8.B.6, contrast figure 8.2 above) if and only if, given two
networks with mixed-sign edge weights $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$,
for every pair of subsets
$E_{1},E_{2}\subseteq\mathscr{E}_{\pm}(\mathcal{G}_{1},\mathcal{G}_{2})$ with
$E_{1}\cap E_{2}=\emptyset$, one has that

$\mathscr{D}(\mathcal{G}_{1},\mathcal{G}_{2})\geq\mathscr{D}(\mathcal{O}_{E_{1}}(\mathcal{G}_{1}),\mathcal{O}_{E_{2}}(\mathcal{G}_{2}))\,,$
(8.B.12)

i.e. replacing non-trivial sign disagreements with trivial sign disagreements
can only decrease the dissimilarity, but never increase it. Observe that the
condition that $E_{1}\cap E_{2}=\emptyset$ is what enforces that we are always
replacing non-trivial sign disagreements with trivial sign disagreements. If
we removed the condition that $E_{1}\cap E_{2}=\emptyset$, we would also be
including the replacement of non-trivial sign disagreements by trivial sign
agreements.

Figure 8.B.6: Schematic for weak double penalization principle.

Note that based on the weak double penalization property being satisfied alone
it is a priori unclear for which
$E_{1},E_{2}\subseteq\mathscr{E}_{\pm}(\mathcal{G}_{1},\mathcal{G}_{2})$,
$E_{1}\cap E_{2}=\emptyset$ the minimum

$\min_{\begin{subarray}{c}E_{1},E_{2}\subseteq\mathscr{E}_{\pm}(\mathcal{G}_{1},\mathcal{G}_{2})\\\
E_{1}\cap
E_{2}=\emptyset\end{subarray}}\mathscr{D}(\mathcal{O}_{E_{1}}(\mathcal{G}_{1}),\mathcal{O}_{E_{2}}(\mathcal{G}_{2}))$
(8.B.13)

is satisfied, although a minimizer must exist due to the finiteness of the
optimization space.

Given two networks $\mathcal{G}_{1},\mathcal{G}_{2}$ with mixed-sign edge
weights, their “set of trivial sign disagreements” is
$\mathcal{E}(\mathcal{G}_{1})\Delta\mathcal{E}(\mathcal{G}_{2})$, i.e.
$(\mathcal{E}(\mathcal{G}_{1})\setminus\mathcal{E}(\mathcal{G}_{2}))\sqcup(\mathcal{E}(\mathcal{G}_{2})\setminus\mathcal{E}(\mathcal{G}_{1}))$.
Then a dissimilarity function $\mathscr{D}$ is called “monotonic” if and only
if, for any two networks with mixed-sign edge weights $\mathcal{G}_{1}$,
$\mathcal{G}_{2}$, and every
$E_{1}\subseteq\mathcal{E}(\mathcal{G}_{1})\setminus\mathcal{E}(\mathcal{G}_{2})$
and every
$E_{2}\subseteq\mathcal{E}(\mathcal{G}_{2})\setminus\mathcal{E}(\mathcal{G}_{1})$,
one has

$\mathscr{D}(\mathcal{G}_{1},\mathcal{G}_{2})\geq\mathscr{D}(\mathcal{O}_{E_{1}}(\mathcal{G}_{1}),\mathcal{O}_{E_{2}}(\mathcal{G}_{2}))\,,$
(8.B.14)

i.e. replacing trivial sign disagreements with trivial sign agreements can
only decrease the dissimilarity, but never increase it.

Observe how, when considering unsigned (weighted) networks as special cases of
networks with mixed-sign edge weights such that all nonzero edges are
positive, all sign disagreements are trivial sign disagreements. Moreover, the
monotonicity property is obviously desirable in that case. The monotonicity
property says that replacing true misses with either false hits or false
misses (cf. terminology from section 4.3.1) should always increase the
dissimilarity. This interpretation remains valid in the case of general
networks with mixed-sign edge weights, because trivial sign agreements always
correspond to true misses, and trivial sign disagreements always correspond to
false hits or false misses.

The monotonicity property implies (is it also equivalent to?) the relationship

$\mathscr{D}(\mathcal{G}_{1},\mathcal{G}_{2})=\max_{\begin{subarray}{c}E_{1}\subseteq\mathcal{E}(\mathcal{G}_{1})\setminus\mathcal{E}(\mathcal{G}_{2})\\\
E_{2}\subseteq\mathcal{E}(\mathcal{G}_{2})\setminus\mathcal{E}(\mathcal{G}_{1})\end{subarray}}\mathscr{D}(\mathcal{O}_{E_{1}}(\mathcal{G}_{1}),\mathcal{O}_{E_{2}}(\mathcal{G}_{2}))\,.$
(8.B.15)

Claim: The monotonicity property implies (is it also equivalent to?)

$\mathscr{D}(\mathcal{O}_{\mathcal{E}(\mathcal{G}_{1})\setminus\mathcal{E}(\mathcal{G}_{2})}(\mathcal{G}_{1}),\mathcal{O}_{\mathcal{E}(\mathcal{G}_{2})\setminus\mathcal{E}(\mathcal{G}_{1})}(\mathcal{G}_{2}))=\min_{\begin{subarray}{c}E_{1}\subseteq\mathcal{E}(\mathcal{G}_{1})\setminus\mathcal{E}(\mathcal{G}_{2})\\\
E_{2}\subseteq\mathcal{E}(\mathcal{G}_{2})\setminus\mathcal{E}(\mathcal{G}_{1})\end{subarray}}\mathscr{D}(\mathcal{O}_{E_{1}}(\mathcal{G}_{1}),\mathcal{O}_{E_{2}}(\mathcal{G}_{2}))\,.$
(8.B.16)

A dissimilarity function $\mathscr{D}$ is said to satisfy the “(strong) double
penalization principle” if and only if, (1) $\mathscr{D}$ is monotonic, and
(2) given any two networks with mixed-sign edge weights $\mathcal{G}_{1}$ and
$\mathcal{G}_{2}$, for every pair of subsets
$E_{1},E_{2}\subseteq\mathscr{E}_{\pm}(\mathcal{G}_{1},\mathcal{G}_{2})$ (i.e.
possibly but not necessarily $E_{1}\cap E_{2}\not=\emptyset$) one has that

$\mathscr{D}(\mathcal{G}_{1},\mathcal{G}_{2})\geq\mathscr{D}(\mathcal{O}_{E_{1}}(\mathcal{G}_{1}),\mathcal{O}_{E_{2}}(\mathcal{G}_{2}))\,,$
(8.B.17)

i.e. replacing non-trivial sign disagreements with either trivial sign
disagreements or trivial sign agreements can only decrease the similarity, but
never increase it505050 Without the possible loophole of replacing trivial
sign disagreements with trivial sign agreements nevertheless somehow being
able to increase the dissimilarity, which I think might technically be
permitted if we only required (8.B.17) without also explicitly requiring
$\mathscr{D}$ to be monotonic, albeit I’m not certain. .

Claim: A dissimilarity function $\mathscr{D}$ satisfies the (strong) double
penalization principle if and only if $\mathscr{D}$ both is monotonic and
satisfies the weak double penalization principle.

More important is the following:

> Claim: A dissimilarity function $\mathscr{D}$ satisfies the (strong) double
> penalization principle if and only if $\mathscr{D}$ satisfies the
> monotonicity property on both the positive and negative parts
> simultaneously.

To the extent that the monotonicity property is highly motivated, perhaps even
“trivially” so, for unsigned networks, the truth of the above claim would then
imply that the (strong) double penalization principle is correspondingly
strongly motivated for signed networks.

Observe how the double penalization principle is agnostic about whether (i)
[the dissimilarity increase for replacing a trivial sign agreement with a
trivial sign disagreement] is larger or smaller than (ii) [the dissimilarity
increase for replacing a trivial sign disagreement with a non-trivial sign
disagreement], i.e. it is agnostic about the “relative weighting” of the
dissimilarity increases associated with each kind of replacement. The double
penalization principle only requires that both kinds of replacement do not
decrease the dissimilarity. Combined together, both requirements then imply
that replacing a trivial sign agreement with a non-trivial sign disagreement
also not decrease the dissimilarity.

Non-trivial sign disagreements correspond to a false hit or false miss for
both the positive parts and the negative parts of the networks (cf. the
sections 3.4 and 4.3.1 for relevant terminology). Thus the double penalization
principle requires that a false hit/miss for the positive parts of the
networks can not be combined with a false miss/hit for the negative parts of
the network to decrease the dissimilarity.

The double penalization property implies (is it also equivalent to?) the
relationship

$\mathscr{D}(\mathcal{G}_{1},\mathcal{G}_{2})=\max_{\begin{subarray}{c}E_{1},E_{2}\subseteq\mathscr{E}_{\pm}(\mathcal{G}_{1},\mathcal{G}_{2})\end{subarray}}\mathscr{D}(\mathcal{O}_{E_{1}}(\mathcal{G}_{1}),\mathcal{O}_{E_{2}}(\mathcal{G}_{2}))\,.$
(8.B.18)

Claim: the double penalization property implies (is it also equivalent to?)

$\mathscr{D}(\mathcal{O}_{\mathscr{E}_{\pm}(\mathcal{G}_{1},\mathcal{G}_{2})}(\mathcal{G}_{1}),\mathcal{O}_{\mathscr{E}_{\pm}(\mathcal{G}_{1},\mathcal{G}_{2})}(\mathcal{G}_{2}))=\min_{\begin{subarray}{c}E_{1},E_{2}\subseteq\mathscr{E}_{\pm}(\mathcal{G}_{1},\mathcal{G}_{2})\end{subarray}}\mathscr{D}(\mathcal{O}_{E_{1}}(\mathcal{G}_{1}),\mathcal{O}_{E_{2}}(\mathcal{G}_{2}))\,.$
(8.B.19)

For two networks $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ with mixed-sign edge
weights, their “set of non-trivial sign agreements”
$\mathscr{E}_{=}(\mathcal{G}_{1},\mathcal{G}_{2})\subseteq\mathcal{E}(\mathcal{G}_{1})\cap\mathcal{E}(\mathcal{G}_{2})$
is the set of “shared” edges such that

$\mathscr{E}_{=}(\mathcal{G}_{1},\mathcal{G}_{2}):=\\{e\subseteq\mathcal{E}(\mathcal{G}_{1})\cap\mathcal{E}(\mathcal{G}_{2}):\operatorname{sign}(A_{\mathcal{G}_{1}}(e))=\operatorname{sign}(A_{\mathcal{G}_{2}}(e))\\}\,.$
(8.B.20)

A similarity function $\mathscr{S}$ is “sparsity-savvy” if and only if, for
any given networks with mixed-sign edge weights $\mathcal{G}_{1}$ and
$\mathcal{G}_{2}$, for every subset
$E\subseteq\mathscr{E}_{=}(\mathcal{G}_{1},\mathcal{G}_{2})$ one has that

$\mathscr{S}(\mathcal{G}_{1},\mathcal{G}_{2})\geq\mathscr{S}(\mathcal{O}_{E}(\mathcal{G}_{1}),\mathcal{O}_{E}(\mathcal{G}_{2}))\,,$
(8.B.21)

i.e. that replacing a trivial sign agreement with a non-trivial sign agreement
at most only increase the similarity, but never decrease it. Cf. section 2.7.
In particular we can’t “game” the similarity by considering only sparse
networks, or removing common edges, or “embedding networks” into spaces with
higher numbers of nodes (i.e. adding completely disconnected nodes, or adding
blocks of all $0$’s to the adjacency matrices). Keep in mind that this
property is not actually entirely trivial, at least for weighted networks.
This is because the difference in magnitudes for a trivial sign agreement is
always $0$, whereas the difference in magnitudes for a non-trivial sign
agreement can be arbitrarily large. So the requirement is actually
substantial/not to be taken for granted.

When considering unsigned (weighted) networks as special cases of signed
networks whose nonzero edges are positive, there are no non-trivial sign
disagreements, i.e. all sign disagreements are trivial sign disagreements. The
sparsity-savviness principle says that replacing true hits with true misses
should never increase the similarity. Such an interpretation remains valid in
the case of general signed (weighted) networks. Even then non-trivial sign
agreements always correspond to true hits for either the positive subnetworks
or for the negative subnetworks (cf. the definitions in sections 3.4 and
4.3.1).

sign agreement sign disagreement trivial $\\{(TM_{+},TM_{-})\\}$
$\\{(FH_{+},TM_{-}),(TM_{+},FH_{-}),(FM_{+},TM_{-}),(TM_{+},FM_{-})\\}$ non-
trivial $\\{(TH_{+},TM_{-}),(TM_{+},TH_{-})\\}$
$\\{(FH_{+},FM_{-}),(FM_{+},FH_{-})\\}$

For the sake of clarity and comparison, let’s consider the analogous binary
classification notions for unsigned networks:

| sign agreement | sign disagreement
---|---|---
trivial | $\\{(TM)\\}$ | $\\{(FH),(FM)\\}$
non-trivial | $\\{(TH)\\}$ | do not exist

Note that the characteristics for unsigned networks should emerge as a special
case of those for general signed networks, and indeed they do.

Definition: Given $S\times S$ matrices, a distance metric
$d:\mathbb{R}^{[S]\times[S]}\times\mathbb{R}^{[S]\times[S]}\to[0,\infty)$ is a
function satisfy the axioms (1) for any matrices $\mathbf{M}_{1}$ and
$\mathbf{M}_{2}$ one has $d(\mathbf{M}_{1},\mathbf{M}_{2})=0$ if and only if
$\mathbf{M}_{1}=\mathbf{M}_{2}$, (2)
$d(\mathbf{M}_{1},\mathbf{M}_{2})=d(\mathbf{M}_{2},\mathbf{M}_{1})$ for any
matrices $\mathbf{M}_{1}$ and $\mathbf{M}_{2}$, and (3)
$d(\mathbf{M}_{1},\mathbf{M}_{3})\leq
d(\mathbf{M}_{1},\mathbf{M}_{2})+d(\mathbf{M}_{2},\mathbf{M}_{3})$ for any
matrices $\mathbf{M}_{1}$, $\mathbf{M}_{2}$, and $\mathbf{M}_{3}$. The
distance metric is said to turn $\mathbb{R}^{[S]\times[S]}$ into a “metric
space”.

Claim: Given a dissimilarity function $\mathscr{D}$ such that for any
$\mathcal{G}_{1},\mathcal{G}_{2}\in\mathscr{G}_{[S]}$ one has that

${\mathscr{D}(\mathcal{G}_{1},\mathcal{G}_{2})=d(\mathbf{A}_{\mathcal{G}_{1}},\mathbf{A}_{\mathcal{G}_{2}})}$

for some distance metric $d$ on the space of matrices, then $\mathscr{D}$ (a)
is monotone, and (b) satisfies the (strong) double penalization property.

In particular, when using dissimilarity functions directly derived from
distance metrics on arbitrary matrices, we don’t have to worry much. This
isn’t necessarily true if the distance metric is only defined for non-negative
matrices (corresponding to unsigned networks).

Definition: A distance metric $d$ on the space of unsigned networks with known
node correspondences $\mathscr{G}_{[S]}^{\geq 0}$ satisfies the axioms (1) for
any unsigned networks $\mathcal{U}_{1}$ and $\mathcal{U}_{2}$ one has
$d(\mathcal{U}_{1},\mathcal{U}_{2})=0$ if and only if
$\mathcal{U}_{1}=\mathcal{U}_{2}$ , (2)
$d(\mathcal{U}_{1},\mathcal{U}_{2})=d(\mathcal{U}_{2},\mathcal{U}_{1})$ for
any unsigned networks $\mathcal{U}_{1}$ and $\mathcal{U}_{2}$, and (3)
$d(\mathcal{U}_{1},\mathcal{U}_{3})\leq
d(\mathcal{U}_{1},\mathcal{U}_{2})+d(\mathcal{U}_{2},\mathcal{U}_{3})$ for any
unsigned networks $\mathcal{U}_{1}$, $\mathcal{U}_{2}$, and $\mathcal{U}_{3}$.

Claim: Given a dissimilarity function $\mathscr{D}$ such that for any
$\mathcal{G}_{1},\mathcal{G}_{2}$ one has that

${\mathscr{D}(\mathcal{G}_{1},\mathcal{G}_{2})=d(\mathcal{M}(\mathcal{G}_{1}),\mathcal{M}(\mathcal{G}_{2}))}$

for some distance metric $d$ on unsigned networks, where
$\mathcal{M}(\mathcal{G})$ denotes the magnitude skeleton of $\mathcal{G}$,
then in general $\mathscr{D}$ does not satisfy515151 It may still satisfy
monotonicity – honestly I’m not sure either way.  the double penalization
principle.

Even starting with the most “well-behaved” dissimilarity functions on unsigned
networks, dissimilarity functions for general networks with mixed-sign edge
weights derived from the “projection procedure” will not satisfy this basic
“well-behavedness” property.

However, we should still have the following

Claim: Given a dissimilarity function $\mathscr{D}$ such that for any
$\mathcal{G}_{1},\mathcal{G}_{2}$ one has that

${\mathscr{D}(\mathcal{G}_{1},\mathcal{G}_{2})=c_{1}d(\mathcal{G}_{1}^{+},\mathcal{G}_{2}^{+})+c_{2}d(\mathcal{G}_{1}^{-},\mathcal{G}_{2}^{-})}$

for $c_{1},c_{2}\geq 0$, $c_{1}$ and $c_{2}$ are allowed to depend on
$\mathcal{G}_{1}$ and $\mathcal{G}_{2}$, and $d$ is a distance metric on
unsigned networks, then $\mathscr{D}$ will satisfy the double penalization
principle.

The above claim only applies to conic (i.e. non-negative) combinations of
dissimilarity functions. However I believe that the analogous claim for
similarity functions is true as well (or at least have been implicitly
assuming as much):

Claim: Given a $\mathscr{S}$ function such that for any
$\mathcal{G}_{1},\mathcal{G}_{2}$ one has that

${\mathscr{S}(\mathcal{G}_{1},\mathcal{G}_{2})=c_{1}\mathcal{S}(\mathcal{G}_{1}^{+},\mathcal{G}_{2}^{+})+c_{2}\mathcal{S}(\mathcal{G}_{1}^{-},\mathcal{G}_{2}^{-})}$

for $c_{1},c_{2}\geq 0$, $c_{1}$ and $c_{2}$ are allowed to depend on
$\mathcal{G}_{1}$ and $\mathcal{G}_{2}$, and $\mathcal{S}$ is a similarity
function on unsigned networks satisfying the (similarity function version of)
monotonicity, then $\mathscr{S}$ will satisfy the (strong) double penalization
property.

I think the above claim is true, or at the very least it seems I have been
implicitly assuming as much. Similarly (pun unintended) it seems I have also
been implicitly assuming

Claim: Given a $\mathscr{S}$ function such that for any
$\mathcal{G}_{1},\mathcal{G}_{2}$ one has that

${\mathscr{S}(\mathcal{G}_{1},\mathcal{G}_{2})=c_{1}\mathcal{S}(\mathcal{G}_{1}^{+},\mathcal{G}_{2}^{+})+c_{2}\mathcal{S}(\mathcal{G}_{1}^{-},\mathcal{G}_{2}^{-})}$

for $c_{1},c_{2}\geq 0$, $c_{1}$ and $c_{2}$ are allowed to depend on
$\mathcal{G}_{1}$ and $\mathcal{G}_{2}$, and $\mathcal{S}$ is a similarity
function on unsigned networks satisfying the sparsity-savviness property, then
$\mathscr{S}$ will satisfy the sparsity-savviness property.

#####  8.B.9 Continuity with respect to Magnitude

Consider the plane ($\mathbb{R}^{2}$) with coordinates denoted $(a,i)$, “$a$”
for “actual”, “$i$” for “inferred”. The first coordinate corresponds to the
weight of the edge of the actual network in a single-edge comparison, whereas
the second coordinate corresponds to the weight of the edge of the inferred
network in a single-edge comparison.

Then we can divide/partition the plane into $4$ regions:

  1. 1.

$\\{(a,i):(a>0\text{ and }i>0)\text{ or }(a<0\text{ and }i<0)\\}\,.$ (8.B.22)

These are the non-trivial sign agreements. Geometrically on the plane, these
correspond to the interiors of the upper right and lower left quadrants.

  2. 2.

$\\{(a,i):(a>0\text{ and }i<0)\text{ or }(a<0\text{ and }i>0)\\}\,.$ (8.B.23)

These are the non-trivial sign disagreements. Geometrically on the plane these
correspond to the interiors of the upper left and lower right quadrants.

  3. 3.

$\\{(a,i):(a=0\text{ and }i\not=0)\text{ or }(a\not=0\text{ and }i=0)\\}\,.$
(8.B.24)

These are the trivial sign disagreements. Geometrically on the plane these
correspond to the union of the $a$ and $i$ axes with the origin removed.

  4. 4.

$\\{(a,i):a=0\text{ and }i=0\\}=\\{(0,0)\\}\,.$ (8.B.25)

These are the trivial sign agreements. Geometrically on the plane these
correspond to the origin.

Figure 8.B.7 illustrates this heuristically:

Figure 8.B.7: The “single-edge comparison plane” described in the main text.

Now consider any continuous function $[0,1]\to\mathbb{R}^{2}$,
$t\mapsto(a(t),i(t))$, a so-called path. For any such path, we can look at the
sequence of above regions that it passes through. Close inspection reveals
that the set of all such allowable sequences corresponds to the set of all
possible paths (in the graph-theoretic sense) in the undirected network from
figure 8.B.2. (At least when prohibiting diagonal movements in the immediate
vicinity of the origin, something which is admittedly better motivated in the
unweighted case.)

The continuity/composability property, at least intuitively speaking or
heuristically or roughly, corresponds to requiring that for any such path in
the “single-edge comparison plane”, and any given objective function, its
values are continuous as a function of the $t$-parametrized family of graph
comparisons corresponding to any given edge in the graph-comparison, and the
start and end points.

Specifically, say we are comparing the actual graph $\mathcal{G}_{*}$ and the
inferred graph $\hat{\mathcal{G}}$. We focus on some particular edge
$e\in[S]\times[S]$. This corresponds to a tuple $(a,i)=(e_{*},\hat{e})$, where
$e_{*}:=A_{\mathcal{G}_{*}}(e)$ and $\hat{e}:=A_{\hat{\mathcal{G}}}(e)$. Then
we can choose some path $[0,1]\to\mathbb{R}^{2}$ with $(e_{*},\hat{e})$ as the
starting point, i.e. $(a(0),i(0))=(e_{*},\hat{e})$. Then this gives us a
parameterized family of tuples of networks, where each $t\in[0,1]$ gets sent
to $(\mathcal{G}_{*}(t),\hat{\mathcal{G}}(t))$, again with
$(\mathcal{G}_{*}(0),\hat{\mathcal{G}}(0))=(\mathcal{G}_{*},\hat{\mathcal{G}})$,
and where $A_{\mathcal{G}_{*}(t)}(e)=a(t)$ and
$A_{\hat{\mathcal{G}}(t)}(e)=i(t)$ (the values of the adjacency function are
assumed unchanged for all other edges). Composing this parameterized family of
tuples of networks with our objective function, we are asking for the
composite function $[0,1]\to\mathbb{R}$ to be continuous, irrespective of
which edge we choose, and which path $[0,1]\to\mathbb{R}^{2}$ was chosen.

Call such a path “coordinate-wise non-decreasing” if, for all $t_{1}<t_{2}$ in
$[0,1]$, we have both $a(t_{1})\leq a(t_{2})$ and $i(t_{1})\leq i(t_{2})$.

Of course, when we consider unweighted network, there is no longer any
“continuous plane” of pairs of edge weight values to send paths into. But we
still would like to consider “discretized paths” where the only allowed
“discretized paths” correspond again to paths (in the graph-theoretic sense)
in the undirected network from figure 8.B.2.

Also of course in the case of weighted networks, non-trivial sign agreements
are no longer straightforward. In other words, even when the signs (non-
trivially) agree, we can now still have differences in magnitude which we
would usually want to penalize as well. The only places in the region of non-
trivial sign agreements where we don’t have magnitude disagreements are along
the intersection with the line $a=i$. This corresponds to a line with slope
$1$. In general, any line with slope bounded in between $0$ and $+\infty$
passes through the two quadrants defining the region of non-trivial sign
agreements and thus corresponds to a certain departure (possibly null when the
slope is $1$) from absence of magnitude of disagreement. (Hypothetically we
could choose to associate this with the non-negative projective line, but
that’s probably a topic for another time.) In the limits as the slopes
approach either $0$ or $+\infty$, we have that the non-trivial sign agreements
actually approach trivial sign disagreements. Therefore, continuity combined
with the desire to penalize trivial sign disagreements require us to penalize
at least some non-trivial sign agreements. (Again this is restricted only to
the case of weighted networks, which is the only context where non-zero
magnitude differences are possible for non-trivial sign agreements.)

While all of this certainly poses some complications for the sparsity-
savviness principle, in particular probably requiring that it can only be
satisfied in some asymptotic sense which we won’t bother to attempt to
precisely define, it actually does not pose any challenges or complications
for satisfying a (continuous version of) the double penalization principle. To
discuss this, it probably makes sense to begin by discussing a continuous
version of monotonicity (i.e. comparing trivial sign agreements with trivial
sign disagreements in the case of weighted networks). The main idea however is
that (the continuous version of525252But then presumably also as a consequence
the discretized version) the double penalization principle does not require
any constraints on the behavior of paths passing through the quadrants
corresponding to non-trivial sign agreements. It only regulates paths which
pass from trivial sign-disagreements to non-trivial sign disagreements, to
ensure they display analogous monotonicity behavior to paths from trivial sign
agreements to trivial sign disagreements. (I.e. how the objective function
behaves in the upper right and lower left quadrants is irrelevant.)

Consider any path starting from $(0,0)$ and such that either $a(t)=0$ or
$i(t)=0$ for all $t\in[0,1]$ (but not both). Then for the coordinate of the
path that is not constant and identically $0$, assume that it is monotone
(non-decreasing or non-increasing, it does not matter which). Then any
dissimilarity $\mathscr{D}$ satisfying the continuous monotonicity property
will monotonically non-decrease along any such path. I.e. making one of the
edge counterparts being compared increasingly nonzero should only worsen the
score.

Now the double penalization principle is motivated by the fact that, when
looking at any point in the non-trivial sign disagreement quadrants (lower
right or upper left), projecting the point onto the closed quadrant $\\{a\geq
0\text{ and }i\geq 0\\}$ represents the point as a trivial disagreement for
the positive part of the network, whereas projecting the point onto the closed
quadrant $\\{a\leq 0\text{ and }i\leq 0\\}$ portrays it as a trivial
disagreement for the negative part of the network. So intuitively speaking, we
would like, at least for paths which are suitably coordinate-wise monotone
restricted within one of the non-trivial sign disagreement quadrants, for the
objective function to “obey monotonicity for both the positive and negative
parts”, i.e. for a dissimilarity function to monotonically non-decrease.
Again, this is not at all a restriction on the behavior in the non-trivial
sign agreement quadrants and thus whether the objective satisfies the double
penalization principle is completely independent of e.g. the relative
weighting of sign errors versus magnitude errors. Cf. the figure 8(a), where
the lighter shaded areas indicate the regions that the (strong and continuous)
double penalization principle implies should correspond to greater
dissimilarity values than the corresponding large white dots.

(a) Large white dot has smallest dissimilarity compared to everything in the
corresponding lightened regions. Additionally white dots indicate the
direction of “increasing isoclines of dissimilarity”.

(b) Examples of paths to which the continuous double penalization principle
applies. Large white dots are the start points of the paths, arrows indicate
the end points and directions of the paths.

Figure 8.B.8: Schematic depiction of continuous version of double penalization
principle.

In the lower right quadrant, a suitable path to which the continuous version
of the double penalization principle applies is one for which $a(0)\geq 0$ and
$i(0)\leq 0$, and then for all $t_{1},t_{2}\in[0,1]$ with $t_{1}<t_{2}$,
$a(t_{1})\leq a(t_{2})$ and $i(t_{1})\geq i(t_{2})$. (If the path coordinate
functions are differentiable, then basically we are requiring that
$a^{\prime}(t)\geq 0$ whereas $i^{\prime}(t)\leq 0$.) Likewise, in the upper
left quadrant, suitable paths are those for which $a(0)\leq 0$ and $i(0)\geq
0$ and such that for all $t_{1},t_{2}\in[0,1]$ with $t_{1}<t_{2}$ we have
$a(t_{1})\geq a(t_{2})$ and $i(t_{1})\leq i(t_{2})$. (If the path coordinate
functions are differentiable, then basically we are requiring that
$a^{\prime}(t)\leq 0$ and $i^{\prime}(t)\geq 0$.) Then for all such paths, the
(continuous version of) the double penalization principle requires that a
dissimilarity function monotonically non-decrease with $t$. (I feel like
requiring the objective to be continuous along with requiring the discretized
definition above should be equivalent to this continuous version of the double
penalization principle, but if it’s true the formal argument would be very
technical and boring so I at least currently will not bother.) Notice in
particular that the continuous version of the double penalization principle
does not require the dissimilarity to increase (non-decrease) fastest or
slowest along a specific choice of this class of paths, only that it be
monotonically non-decreasing along all of them. (If we assume the start and
end points of all of the paths under consideration are the same, then only the
“rate of change” along the paths can differ, because obviously then the net
difference between the values of the dissimilarity function at the beginning
and end of the path must be the same.)

The figure 8(b) indicates examples of such allowable trajectories.

#####  8.B.10 Considerations for Generalized Networks

The arguments and notions of e.g. the monotonicity principle, double
penalization principle, or sparsity-savviness principle, do not inherently
need the comparison functions be defined for “discrete”, finite networks. To
clarify the “true” underlying ideas, what follows is a preliminary attempt to
demonstrate their generalizability to other comparison functions. Hopefully
this will be a preliminary step towards future work that makes all of the
concepts and principles expressed in this chapter precise enough to be
falsifiable.

######  8.B.10.1 Generalized Edge Spaces

Let a locally compact Polish space535353 Equivalent to a locally compact
second-countable Hausdorff space (a.k.a. “LCCB” space), among other
characterizations.  $E$ correspond to a “generalized edge space”.

Examples:

  * •

For a (finite) network, $E=[S]\times[S]$ (equipped with the usual
discrete545454 Like the discrete topology for $\mathbb{N}\times\mathbb{N}$,
this is also the same as the Euclidean subspace topology inherited from
$\mathbb{R}^{2}$.  topology).

  * •

For an infinite network, $E=\mathbb{N}\times\mathbb{N}$ (equipped with the
usual discrete topology).

  * •

For a graphon, $E=[0,1]\times[0,1]$ (equipped with the usual Euclidean
subspace topology).

######  8.B.10.2 Generalized Edge/Adjacency Functions

Given a “generalized edge space $E$”, i.e. a locally compact Polish space, a
“generalized edge (adjacency) function” $A:E\to\mathbb{R}$ will be interpreted
as a continuous function $E\to\mathbb{R}$.

Note that in the case that the topology of $E$ is discrete, then all functions
$E\to\mathbb{R}$ are continuous. However, this is a meaningful restriction
e.g. in the graphon case. Analysis extending these notions to general Borel-
measurable functions (or showing that such an extension is impossible) is left
to future work.

Note that because $E$ is locally compact Polish, and $\mathbb{R}$ is Polish,
the space of all continuous functions $C(E,\mathbb{R})$ is itself a Polish
space when equipped with the standard compact-open topology and, moreover, is
an exponential object in the category of topological spaces (in particular
evaluation of functions is continuous).

######  8.B.10.3 Indicators as Pointwise Limits

######  Lemma 8.7.

Let $(X,\tau)$ be a topological space, $Y\subseteq X$. Assume that the
indicator function $\mathbb{I}\\!\left\\{Y\right\\}:X\to[0,1]$ can be written
as the monotone non-decreasing pointwise limit of some sequence of continuous
functions $f_{n}:X\to[0,1]$, i.e. for all $x\in X$ one has
$\lim\limits_{n\to\infty}f_{n}(x)=\mathbb{I}\\!\left\\{Y\right\\}(x)$ and for
all $n_{1},n_{2}\in\mathbb{N}$, $n_{1}\leq n_{2}$, $f_{n_{1}}(x)\leq
f_{n_{2}}(x)$. Then $Y$ must be (1) open and (2) $F_{\sigma}$.

###### Proof of Lemma 8.7

First, note that $\\{1\\}$ and $\\{0\\}$ are closed subsets of $[0,1]$,
whereas as $[0,1)$ and $(0,1]$ are open subsets $[0,1]$.

By definition, the inverse image of $\\{1\\}$ under
$\mathbb{I}\\!\left\\{Y\right\\}$ is exactly the set $Y$, so the sets of
values where the $f_{n}$ equal $1$ must approach $Y$. Because the $f_{n}$ are
monotone increasing and bounded above by $1$, for $n_{1}\leq n_{2}$ we must
have $f_{n_{1}}^{-1}(\\{1\\})\subseteq f_{n_{2}}^{-1}(\\{1\\})$, i.e. the
inverse images of $\\{1\\}$ under the $f_{n}$ must be non-decreasing as well
and thus “approach $Y$ from the inside”. More concretely:

$Y=\bigcup_{n=1}^{\infty}f_{n}^{-1}(\\{1\\})=\left(\bigcap_{n=1}^{\infty}f_{n}^{-1}([0,1))\right)^{c}\,,$
(8.B.26)

with the last equality following from DeMorgan’s Law. Because all of the
$f_{n}$ are continuous, the $f_{n}^{-1}(\\{1\\})$ are all closed and the
$f_{n}^{-1}([0,1))$ are all open. Hence $Y$ is the countable union of closed
sets, thus $F_{\sigma}$. (Equivalently $Y$ is the complement of a countable
intersection of open sets, i.e. the complement of a $G_{\delta}$ set.)

At the same time, the inverse image of $\\{0\\}$ under
$\mathbb{I}\\!\left\\{Y\right\\}$ is the set $Y^{c}$, so the sets of values
where the $f_{n}$ equal $0$ must approach $Y^{c}$. Because the $f_{n}$ are
monotone increasing and bounded below by $0$, for $n_{1}\leq n_{2}$ we must
have $f_{n_{1}}^{-1}(\\{0\\})\supseteq f_{n_{2}}^{-1}(\\{0\\})$, i.e. the
inverse images of $\\{0\\}$ under the $f_{n}$ must be non-increasing and thus
“approach $Y^{c}$ from the outside”. More concretely:

$Y=(Y^{c})^{c}=\left(\bigcap_{n=1}^{\infty}f_{n}^{-1}(\\{0\\})\right)^{c}=\bigcup_{n=1}^{\infty}f_{n}^{-1}((0,1])\,,$
(8.B.27)

with the last equality again following from DeMorgan’s Law. Again because all
of the $f_{n}$ are continuous, the $f_{n}^{-1}(\\{0\\})$ are all closed and
the $f_{n}^{-1}((0,1])$ are all open. The arbitrary intersection of closed
sets is closed, and the arbitrary union of open sets is open, so (8.B.27)
means that $Y$ is the complement of a closed set, or equivalently an open set.
$\square$

######  Corollary 3.

Let $(X,\tau)$ be a topological space, $Z\subseteq X$. Assume that the
indicator function $\mathbb{I}\\!\left\\{Z\right\\}:X\to[0,1]$ can be written
as the monotone non-increasing pointwise limit of some sequence of continuous
functions $g_{n}:X\to[0,1]$, i.e. for all $x\in X$ one has
$\lim\limits_{n\to\infty}g_{n}(x)=\mathbb{I}\\!\left\\{Z\right\\}(x)$ and for
all $n_{1},n_{2}\in\mathbb{N}$, $n_{1}\leq n_{2}$, $g_{n_{1}}(x)\geq
g_{n_{2}}(x)$. Then $Z$ must be (1) closed and (2) $G_{\delta}$.

Proof of Corollary 3: Take $Y:=Z^{c}$ and $f_{n}:=1-g_{n}$. These satisfy the
hypotheses of Lemma 8.7. Because $Y=Z^{c}$ is open and $F_{\sigma}$, it
follows that its complement $Z$ must be closed and $G_{\delta}$. $\square$

######  8.B.10.4 $\sigma$-compact subsets

######  Lemma 8.8.

Let $X$ be a $\sigma$-compact and Hausdorff555555 Hausdorffness is technically
somewhat overkill. Because a closed subset of a compact set is always compact,
all we need is for all compact sets to be closed (a so-called “KC space”), and
even then only for one direction. That being said, Hausdorffness is a much
weaker assumption than the assumption that $E$ be a locally compact Polish
space.  space. Then a subset $Y$ is $\sigma$-compact565656 Because compactness
is an “intrinsic” topological property, i.e. $Z\subseteq X$ is compact in its
subspace topology if and only if it is compact in the “ambient” topology of
$X$, the same is also true of $\sigma$-compactness. For other properties we
would need to be more careful and specify whether we meant in the subspace
topology of $Y$ or in the “ambient” topology of $X$.  if and only if $Y$ is
$F_{\sigma}$.

###### Proof of Lemma 8.8

$(\implies)$ Assume $Y$ is $\sigma$-compact, i.e.
$Y=\bigcup_{n=1}^{\infty}\tilde{K}_{n}$ with all $\tilde{K}_{n}$ compact.
Because the $\tilde{K}_{n}$ are compact, they are closed. So $Y$ is the
countable union of closed sets, i.e. $F_{\sigma}$.

$(\impliedby)$ Assume $Y$ is $F_{\sigma}$, i.e.
$Y=\bigcup_{n=1}^{\infty}F_{n}$ with all $F_{n}$ closed. Because $X$ is
$\sigma$-compact, $X=\bigcup_{m=1}^{\infty}K_{m}$ with all $K_{m}$ compact.
Then because $X\cap Y=Y$, we have that

$Y=\bigcup_{m=1}^{\infty}\bigcup_{n=1}^{\infty}(K_{m}\cap F_{n})\,.$

Because the $K_{m}$ are compact and the $F_{n}$ are closed, for all $m$ and
$n$ we have that $K_{m}\cap F_{n}$ is compact. Therefore $Y$ is the countable
union of compact sets, i.e. $\sigma$-compact. $\square$

######  8.B.10.5 Relevant Facts

  * •

Locally compact Polish spaces are (by definition) metrizable, and metrizable
spaces are perfectly normal (because they are normal and closed sets are
$G_{\delta}$).

  * •

Locally compact and second-countable implies $\sigma$-compact, all Polish
spaces are second-countable, so locally compact Polish spaces are
$\sigma$-compact.

  * •

In a metrizable space open sets are575757This is dual to the aforementioned
fact that closed sets are $G_{\delta}$. $F_{\sigma}$, thus by Lemma 8.8 and
the above facts we know that every open subset of a locally compact Polish
space is $\sigma$-compact.

######  8.B.10.6 Approximating Open Indicators from Below

######  Lemma 8.9.

Let $U$ be an open subset of a locally compact Polish space $E$. Then there
exists a monotone non-decreasing sequence of continuous functions
$f_{n}:E\to[0,1]$ such that the indicator
$\mathbb{I}\\!\left\\{U\right\\}:E\to[0,1]$ is the pointwise limit, i.e. for
all $e\in E$ one has
$\lim\limits_{n\to\infty}f_{n}(e)=\mathbb{I}\\!\left\\{U\right\\}(e)$ and for
all $n_{1},n_{2}\in\mathbb{N}$, $n_{1}\leq n_{2}$, $f_{n_{1}}(e)\leq
f_{n_{2}}(e)$. (Using Lemma 8.7 it follows that the existence of such a
sequence exactly characterizes open subsets of $E$.)

###### Proof of Lemma 8.9

This seems to only585858 Specifically that $E$ be perfectly normal. However,
$E$ is perfectly normal if and only if it is normal and every closed set is
$G_{\delta}$, every closed set is $G_{\delta}$ if and only if every open set
is $F_{\sigma}$, so $E$ is perfectly normal if and only if it is normal and
all open subsets are $F_{\sigma}$. In particular metrizability is not directly
relevant here, even though all metrizable spaces are perfectly normal. That
being said, known counterexamples of perfectly normal spaces that are not
metrizable, e.g. the Arens-Fort space or the Sorgenfrey line, are all fairly
“weird” and thus not likely to be relevant to the practice of data science.
require that $E$ be normal and that all open subsets be $F_{\sigma}$. First,
using the fact that $U$ open is $F_{\sigma}$, write
$U=\bigcup\limits_{n=1}^{\infty}F_{n}$ with all $F_{n}$ closed595959We can
assume without loss of generality that the sequence of closed sets is
increasing, by taking $\tilde{F}_{n}:=\bigcup\limits_{m\leq n}F_{m}$ if
necessary, noting the fact that the union of finitely many closed sets is
again always closed.. Next follows an induction argument.

For the base case where $n=1$, note that the fact that $E$ is perfectly normal
means Urysohn’s lemma can be applied to the closed sets $F_{1}$ and $U^{c}$ in
such a way to give a continuous function $f_{1}:=g_{1}:E\to[0,1]$ such that
$g_{1}(e)=0$ for all $e\in U^{c}$, $g_{1}(e)=1$ for all $e\in F_{1}$, and
(this is the part requiring $E$ to be perfectly normal) $0<g_{1}(e)<1$ for all
$e\in U\setminus F_{1}$. Because there are no $n$ smaller than $1$, the
monotonicity requirement is vacuously satisfied.

Now assume for $n\geq 1$ the induction hypothesis holds that for all $m\leq n$
there exists a continuous $f_{m}:E\to[0,1]$ such that $f_{m}(e)=0$ for all
$e\in U^{c}$, $f_{m}(e)=1$ for all $e\in F_{m}$, $0<f_{m}(e)<1$ for all $e\in
U\setminus F_{m}$, and that for all $n_{1},n_{2}\leq n$ with $n_{1}\leq n_{2}$
that one has for all $e\in E$ that $f_{n_{1}}(e)\leq f_{n_{2}}(e)$. To prove
the claim, we now need to show that there exists a continuous
$f_{n+1}:E\to[0,1]$ such that $f_{m+1}=0$ for all $e\in U^{c}$, $f_{n+1}(e)=1$
for all $e\in F_{n+1}$, $0<f_{n+1}(e)<1$ for all $e\in U\setminus F_{n+1}$,
and that for all $m\leq n$ that for all $e\in E$ one has $f_{m}(e)\leq
f_{n+1}(e)$.

Because $E$ is perfectly normal, again Urysohn’s lemma can be applied to the
closed sets $F_{n+1}$ and $U^{c}$ in such a way to give a continuous function
$g_{n+1}:E\to[0,1]$ such that $g_{n+1}(e)=0$ for all $e\in U^{c}$,
$g_{n+1}(e)=1$ for all $e\in F_{n+1}$, and $0<g_{n+1}(e)<1$ for all $e\in
U\setminus F_{n+1}$. Now define $f_{n+1}:=\max\\{g_{n+1},f_{n}\\}$. As the
maximum of two continuous functions, $f_{n+1}$ is itself continuous. Likewise,
because for all $e\in U^{c}$ we have that $f_{n}(e)=g_{n+1}(e)=0$, we also
have that $f_{n+1}(e)=0$ for all $e\in U^{c}$. Because $f_{n}(e)\leq 1$ for
all $e\in E$, and $g_{n+1}(e)=1$ for all $e\in F_{n+1}$, it follows that for
all $e\in F_{n+1}$ one has

$f_{n+1}(e)=\max\\{f_{n}(e),g_{n+1}(e)\\}=\max\\{f_{n}(e),1\\}=1\,.$

Finally, because $F_{n}\subseteq F_{n+1}$, we have that $U\setminus
F_{n+1}\subseteq U\setminus F_{n}$, so $0<f_{n}(e)<1$ for all $e\in U\setminus
F_{n}$ in turn implies that $0<f_{n}(e)<1$ for all $e\in U\setminus F_{n+1}$.
Therefore

$0<f_{n+1}(e)=\max\\{f_{n}(e),g_{n+1}(e)\\}<1$

for all $e\in U\setminus F_{n+1}$. Therefore we have proven the induction
step.

The only claim that remains to be verified is that for all $e\in E$ one has
$\lim\limits_{n\to\infty}f_{n}(e)=\mathbb{I}\\!\left\\{U\right\\}(e)$. This of
course splits into two cases: first verifying that, for all $e\in U^{c}$, that
$\lim\limits_{n\to\infty}f_{n}(e)=\mathbb{I}\\!\left\\{U\right\\}(e)=0$, and
second verifying that, for all $e\in U$, that
$\lim\limits_{n\to\infty}f_{n}(e)=\mathbb{I}\\!\left\\{U\right\\}(e)=1$.

For the first verification, note that by definition of the $f_{n}$ we have
that for all $e\in U^{c}$ one has $f_{n}(e)=0$. Therefore for every $e\in
U^{c}$ the corresponding sequence $\\{f_{n}(e)\\}$ is the constant sequence
$0$, which obviously converges and with $0$ as its limit.

For the second verification observe that, because the $F_{n}$ are assumed to
be increasing, i.e. $F_{n+1}\supseteq F_{n}$ for all $n$, and that
$\bigcup\limits_{n=1}^{\infty}F_{n}=U$ (i.e. we can’t have the $F_{n}$
“stabilize” at some proper subset of $U$) that for every $e\in U$ there must
exist some $n_{e}$ such that for all $n\geq n_{e}$, $e\in F_{n}$. Thus for all
$n\geq n_{e}$, by definition of the $f_{n}$ we have that $f_{n}(e)=1$. Thus
for every $e\in U$ the sequence $\\{f_{n}(e)\\}$ equals $1$ for all but
finitely many terms, again obviously forcing the sequence to converge and to
the limit $1$.

###### Comments about Approximating Open Indicators from Below

In the case that $E$ is locally compact Polish, as explained above it follows
that $E$ is both locally compact and $\sigma$-compact. Because the finite
union of compact sets is again compact, being $\sigma$-compact is equivalent
to equaling an increasing countable union of compact sets. Because any open
subset of a locally compact space is again locally compact, any open subset of
$E$ is locally compact. Likewise, in a locally compact Polish space any open
set is $F_{\sigma}$ and $F_{\sigma}$ subsets of all $\sigma$-compact spaces
are themselves $\sigma$-compact, thus any open subset of $E$ is also
$\sigma$-compact. Therefore we can assume without loss of generality in the
case that $E$ is a locally compact Polish space that the increasing sequence
of closed sets whose union equals the open subset $U$ consists exclusively of
compact sets, and that for each $n$ we have $K_{n+1}\supseteq
Int(K_{n+1})\supseteq K_{n}$, where $Int(K_{n+1})$ denotes the topological
interior (with respect to either $E$ or $U$, both notions coincide because $U$
is open). Such “(strong) exhaustions by compact sets” can be technically
useful.

######  8.B.10.7 Use for Censoring Subsets

Let $U$ be an open subset of a “generalized edge space” $E$, i.e. a locally
compact Polish space $E$. Given a monotonically non-decreasing sequence of
continuous functions $f_{n}:E\to[0,1]$ which converge pointwise to the
indicator function of $U$, it follows that the sequence of functions $1-f_{n}$
are a non-increasing sequence of continuous functions which converge pointwise
to the indicator function of $U^{c}$. If we replace/augment such a convergent
sequence to get a convergent net indexed by the directed set $[0,1]$, then we
get non-increasing (as $t$ in creases) functions that converge pointwise to
the indicator of $U^{c}$ as $t\to 1$. Re-indexing by $1-t$, we get non-
decreasing (as $t$ increases) functions that converge pointwise to the
indicator of $U^{c}$ as $t\to 0$. The details of this will be explained below,
but this is to be interpreted as progressively removing the “censoring” of the
subset $U$ as $t$ increases, approaching no censoring as $t\to 1$, and full
censoring as $t\to 0$. While the important aspect for definitions is that the
“easing of censoring” is done monotonically, it is also nice to know that this
can be constructed in a way that is continuous.

Specifically, first consider the sequence $t_{n}$ defined on $[0,1]$, and
converging towards $0$, defined for all $n\in\mathbb{N}$ such that606060 This
is probably the simplest example, but any monotonically decreasing sequence
bounded within $[0,1]$ with $t_{0}=1$ and whose limit is $0$ will work.
$t_{n}=2^{-n}$. Define “censoring functions” $\xi_{t}:E\to[0,1]$ for all
$t\in[0,1]$ as follows. First, $\xi_{0}$ is the constant function identically
equal to $1$ for all $e\in E$. Then for all $n\geq 1$, define $\xi_{t_{n}}$ to
be $\xi_{t_{n}}:=1-f_{n}$. Then for any other value of $t\in[0,1]$, first
identify the $m\in\mathbb{N}$ such that
$t_{m}=\sup_{n\in\mathbb{N}}\\{t_{n}:t_{n}<t\\}$. Such an $m$ must exist
because the $t_{n}$ are monotonically decreasing and thus there can only be
finitely many of them greater than $t$. Then basically define $\xi_{t}$ as the
corresponding “interpolation” between $\xi_{t_{m-1}}$ and $\xi_{t_{m}}$, i.e.

$\xi_{t}=\frac{(t_{m}-t)}{(t_{m}-t_{m-1})}\xi_{t_{m-1}}+\frac{(t_{m}-t_{m-1})-(t_{m}-t)}{(t_{m}-t_{m-1})}\xi_{t_{m}}\,.$

From these definitions it follows that:

  * •

the $\xi_{t}$ are all continuous for $t>0$ (being the convex combination of
continuous functions),

  * •

as $t\to 1$ the $\xi_{t}$ approach the constant function identically equal to
$1$,

  * •

as $t\to 0$ the $\xi_{t}$ approach the (discontinuous) indicator function of
$U^{c}$ (which equals $0$ on $U$ and $1$ everywhere else),

  * •

the $\xi_{t}$ are monotonically non-decreasing as $t$ increases, i.e. for all
$t_{1}<t_{2}$ we have for all $e\in E$ that
$\xi_{t_{1}}(e)\leq\xi_{t_{2}}(e)$.

Thus the $\xi_{t}$ define a continuous “homotopy” from complete censoring of
$U$ as $t\to 0$ to no “censoring” at all as $t\to 1$. For $t>0$, the
$\xi_{t}\in C(E,\mathbb{R})$ (i.e. are continuous), so their graph-loci are
closed subsets of $E\times\mathbb{R}$. Thus I expect, i.e. conjecture and have
not rigorously verified, that we would have a homotopy, in the rigorous sense
of a continuous function $[0,1]\to(E\times\mathbb{R}$) connecting the graph-
loci of the $\xi_{t}$ for $t>0$ with (as $t\to 0$) the closed subset of
$E\times\mathbb{R}$ that equals
$(U^{c}\times\\{1\\})\cup(\partial(U)\times[0,1])\cup(U\times\\{0\\})$ (which
contains, but is a strict superset of, the graph-locus of the discontinuous
indicator function of $U$). Here $\partial(U)$ equals the topological boundary
of $U$, i.e. the closure of $U$ minus the interior of $U$, or equivalently
$U^{c}$ (which is closed and thus equals its own closure) minus its interior
(because the topological boundary of any subset equals that of its
complement).

######  8.B.10.8 Monotone Uncensoring of $U\subseteq E$

######  Definition 8.B.10.1.

A family of functions $(\xi_{t}:E\to\mathbb{R})_{t\in[0,1]}$ such that

  * •

for all $t>0$ we have $\xi_{t}\in C(E,\mathbb{R})$ (i.e. $\xi_{t}$ is
continuous),

  * •

the graph-loci of the $\xi_{t}$ “vary continously with $t$,

  * •

as $t\to 1$ the $\xi_{t}$ approach the constant function $1:E\to\mathbb{R}$
pointwise,

  * •

as $t\to 0$ the $\xi_{t}$ approach the indicator function of $U^{c}$
pointwise,

  * •

the $\xi_{t}$ are pointwise monotonically non-decreasing as $t$ increases.

I claim to have demonstrated previously that such a monotone uncensoring
exists for any open subset $U\subseteq E$, and that satisfying the first
condition (that the $\xi_{t}$ be continuous for $t>0$) requires that
$U\subseteq E$ be open.

######  8.B.10.9 Comments about Monotone Uncensorings

Future work should probably seek to determine whether there is a sensible way
to require the $\xi_{t}$ for $t>0$ to only be Borel-measurable, rather than
necessarily continuous. Again, we showed above that “continuous” monotone
uncensorings should only exist for open subsets of $E$, so one question such
future work would have to address is which kinds of subsets of $E$ would admit
“measurable” monotone uncensorings.

The definition of (continuous) monotone uncensoring is used to define the
(continuous versions of the) monotonicity property and double penalization
property for comparison functions of (generalized) networks. Thus it is
important to verify that such families of functions actually do exist.

When $E$ has the discrete topology (and thus every subset is open), the
condition that $U$ be open is obviously not at all restrictive.

[chapters]

### References

  * [AEE92] Jorge Aragón, David Eberly, and Shelly Eberly, _Existence and uniqueness of the maximum likelihood estimator for the two-parameter negative binomial distribution_ , Statistics & Probability Letters 15 (1992), no. 5, 375–379.
  * [AGH+17] Rachael E. Antwis, Sarah M. Griffiths, Xavier A. Harrison, Paz Aranega-Bou, Andres Arce, Aimee S. Bettridge, Francesca L. Brailsford, Alexandre de Menezes, Andrew Devaynes, Kristian M. Forbes, Ellen L. Fry, Ian Goodhead, Erin Haskell, Chloe Heys, Chloe James, Sarah R. Johnston, Gillian R. Lewis, Zenobia Lewis, Michael C. Macey, Alan McCarthy, James E. McDonald, Nasmille L. Mejia-Florez, David O’Brien, Chloé Orland, Marco Pautasso, William D. K. Reid, Heather A. Robinson, Kenneth Wilson, and William J. Sutherland, _Fifty important research questions in microbial ecology_ , FEMS Microbiology Ecology 93 (2017), no. 5, 1–10.
  * [AML+17] Marco Tulio Angulo, Jaime A Moreno, Gabor Lippner, Albert-László Barabási, and Yang-Yu Liu, _Fundamental limitations of network reconstruction from temporal data_ , J. R. Soc. Interface 14 (2017), no. 127, 20160966 (en).
  * [AML19] Marco Tulio Angulo, Claude H. Moog, and Yang-Yu Liu, _A theoretical framework for controlling complex microbial communities_ , Nature Communications 10 (2019), no. 1, 1–12.
  * [AN72] Krishna B. Athreya and Peter E. Ney, _Multi-type branching processes_ , Branching Processes, Springer Berlin Heidelberg, Berlin, Heidelberg, 1972, pp. 181–228.
  * [Ans50] F. J. Anscombe, _Sampling Theory of the Negative Binomial and Logarithmic Series Distributions_ , Biometrika 37 (1950), no. 3/4, 358–382.
  * [APRL+20] Ricardo Andrade-Pacheco, Francois Rerolle, Jean Lemoine, Leda Hernandez, Aboulaye Meïté, Lazarus Juziwelo, Aurélien F. Bibaut, Mark J. van der Laan, Benjamin F. Arnold, and Hugh J. W. Sturrock, _Finding hotspots: development of an adaptive spatial sampling approach_ , Scientific Reports 10 (2020), no. 1, 1–12.
  * [Arn10] Ludwig Arnold, _Random dynamical systems_ , Springer monographs in mathematics, Springer, Berlin, Germany, December 2010 (en).
  * [BA02] Kenneth P. Burnham and David R. Anderson, _Advanced issues and deeper insights_ , Model Selection and Multimodel Inference: A Practical Information-Theoretic Approach, Springer New York, New York, NY, 2002, pp. 267–351.
  * [BBI20] Jacob T Barlow, Said R Bogatyrev, and Rustem F Ismagilov, _A quantitative sequencing framework for absolute abundance measurements of mucosal and lumenal microbial communities_ , Nat. Commun. 11 (2020), no. 1, 2590 (en).
  * [BBM99] Andrew Barron, Lucien Birgé, and Pascal Massart, _Risk bounds for model selection via penalization_ , Probability Theory and Related Fields 113 (1999), no. 3, 301–413.
  * [BEG+18] Liana T Burghardt, Brendan Epstein, Joseph Guhlin, Matt S Nelson, Margaret R Taylor, Nevin D Young, Michael J Sadowsky, and Peter Tiffin, _Select and resequence reveals relative fitness of bacteria in symbiotic and free-living environments_ , Proc. Natl. Acad. Sci. U. S. A. 115 (2018), no. 10, 2425–2430 (en).
  * [BGF01] Dean Billheimer, Peter Guttorp, and William F Fagan, _Statistical interpretation of species composition_ , Journal of the American Statistical Association 96 (2001), no. 456, 1205–1214.
  * [BKK16] Eyal Bairey, Eric D Kelsic, and Roy Kishony, _High-order species interactions shape ecosystem diversity_ , Nat. Commun. 7 (2016), no. 1, 12285 (en).
  * [BMK+18] Alex Bishara, Eli L Moss, Mikhail Kolmogorov, Alma E Parada, Ziming Weng, Arend Sidow, Anne E Dekas, Serafim Batzoglou, and Ami S Bhatt, _High-quality genome sequences of uncultured microbes by assembly of read clouds_ , Nat. Biotechnol. 36 (2018), no. 11, 1067–1075 (en).
  * [BML+15] Surojit Biswas, Meredith McDonald, Derek S Lundberg, Jeffery L Dangl, and Vladimir Jojic, _Learning microbial interaction networks from metagenomic count data_ , Lecture Notes in Computer Science, Lecture notes in computer science, Springer International Publishing, Cham, 2015, pp. 32–43.
  * [Bou20] Djallel Bouneffouf, _Computing the dirichlet-multinomial log-likelihood function_ , 2020.
  * [Bow84] Kimiko O. Bowman, _Extended Moment Series and the Parameters of the Negative Binomial Distribution_ , Biometrics 40 (1984), no. 1, 249–252.
  * [Bre73] R. P. Brent, _Algorithms for Minimization Without Derivatives_ , Prentice-Hall, Englewood Cliffs, N.J, 1973.
  * [BSJAB19] A Barizien, M S Suryateja Jammalamadaka, G Amselem, and Charles N Baroud, _Growing from a few cells: combined effects of initial stochasticity and cell-to-cell variability_ , J. R. Soc. Interface 16 (2019), no. 153, 20180935 (en).
  * [BSM+21] Alexander P Browning, Jesse A Sharp, Tarunendu Mapder, Christopher M Baker, Kevin Burrage, and Matthew J Simpson, _Persistence as an optimal hedging strategy_ , Biophys. J. 120 (2021), no. 1, 133–142 (en).
  * [CdC+17] Daniel T. Chiu, Andrew J. deMello, Dino Di Carlo, Patrick S. Doyle, Carl Hansen, Richard M. Maceiczyk, and Robert C.R. Wootton, _Small but perfectly formed? successes, challenges, and opportunities for microfluidics in the chemical and biological sciences_ , Chem 2 (2017), no. 2, 201–223.
  * [CG19] Neil Convery and Nikolaj Gadegaard, _30 years of microfluidics_ , Micro and Nano Engineering 2 (2019), 76–91.
  * [CHL+20] Ashley R Coenen, Sarah K Hu, Elaine Luo, Daniel Muratore, and Joshua S Weitz, _A primer for microbiome time-series analysis_ , Front. Genet. 11 (2020), 310 (en).
  * [CK21] Genís Calderer and Marieke L Kuijjer, _Community detection in large-scale bipartite biological networks_ , Front. Genet. 12 (2021), 649440 (en).
  * [CM12] Dong Chen and Hans-Georg Müller, _Nonlinear manifold representations for functional data_ , The Annals of Statistics 40 (2012), no. 1, 1–29.
  * [CM13] Jeng-Min Chiou and Hans-Georg Müller, _Linear manifold modelling of multivariate functional data_ , Journal of the Royal Statistical Society: Series B (Statistical Methodology) 76 (2013), no. 3, 605–626.
  * [CMR21] Julien Chiquet, Mahendra Mariadassou, and Stéphane Robin, _The poisson-lognormal model as a versatile framework for the joint analysis of species abundances_ , Frontiers in Ecology and Evolution 9 (2021), 1–17.
  * [CNd+15] David J. Collins, Adrian Neild, Andrew deMello, Ai-Qun Liu, and Ye Ai, _The poisson distribution and beyond: methods for microfluidic droplet production and single cell encapsulation_ , Lab on a Chip 15 (2015), no. 17, 3439–3459.
  * [Cor09] Heather J Cordell, _Detecting gene-gene interactions that underlie human diseases_ , Nat. Rev. Genet. 10 (2009), no. 6, 392–404 (en).
  * [Cow84] Wayne R. Cowell (ed.), _Sources and development of mathematical software_ , Prentice-Hall Series in Computational Mathematics, Cleve Moler, Advisor, Prentice-Hall, Upper Saddle River, NJ 07458, USA, 1984.
  * [CP89] Suzanne J. Clark and Joe N. Perry, _Estimation of the Negative Binomial Parameter $\kappa$ by Maximum Quasi -Likelihood_, Biometrics 45 (1989), no. 1, 309–316.
  * [Cra46] Harald Cramer, _Mathematical methods of statistics (PMS-9), volume 9_ , Princeton Landmarks in Mathematics and Physics, Princeton University Press, Princeton, NJ, March 1946 (en).
  * [CY18] Kieran R Campbell and Christopher Yau, _Uncovering pseudotemporal trajectories with covariates from single cell and bulk expression data_ , Nat. Commun. 9 (2018), no. 1, 1–12 (en).
  * [CZPA09] Andrzej Cichocki, Rafal Zdunek, Anh Huy Phan, and Shun-Ichi Amari, _Nonnegative Matrix and Tensor Factorizations_ , John Wiley & Sons, Ltd, September 2009.
  * [DA21] Cyrille L Delley and Adam R Abate, _Modular barcode beads for microfluidic single cell genomics_ , Sci. Rep. 11 (2021), no. 1, 10857 (en).
  * [DH15] Robert M. Dorazio and Margaret E. Hunter, _Statistical models for the analysis and design of digital polymerase chain reaction (dpcr) experiments_ , Analytical Chemistry 87 (2015), no. 21, 10886–10893.
  * [DiSd17] Oliver J. Dressler, Xavier Casadevall i Solvas, and Andrew J. deMello, _Chemical and biological dynamics using droplet-based microfluidics_ , Annual Review of Analytical Chemistry 10 (2017), no. 1, 1–24.
  * [DM21] Paromita Dubey and Hans-Georg Müller, _Modeling time-varying random objects and dynamic networks_ , Journal of the American Statistical Association (2021), 1–16.
  * [ECR16] Stephen P. Ellner, Dylan Z. Childs, and Mark Rees, _Data-driven modelling of structured populations_ , Springer International Publishing, 2016.
  * [Efr82] Bradley Efron, _Maximum Likelihood and Decision Theory_ , The Annals of Statistics 10 (1982), no. 2, 340 – 356.
  * [ELW+20] Amir Erez, Jaime G Lopez, Benjamin G Weiner, Yigal Meir, and Ned S Wingreen, _Nutrient levels and trade-offs control diversity in a serial dilution ecosystem_ , eLife 9 (2020), e57790.
  * [ESGVS21] Sylvie Estrela, Alicia Sanchez-Gorostiaga, Jean Cc Vila, and Alvaro Sanchez, _Nutrient dominance governs the assembly of microbial communities in mixed nutrient environments_ , Elife 10 (2021), e65948 (en).
  * [EVL+22] Sylvie Estrela, Jean C C Vila, Nanxi Lu, Djordje Bajić, Maria Rebolleda-Gómez, Chang-Yu Chang, Joshua E Goldford, Alicia Sanchez-Gorostiaga, and Álvaro Sánchez, _Functional attractors in microbial community assembly_ , Cell Syst. 13 (2022), no. 1, 29–42.e7 (en).
  * [FFD08] Paul G. Falkowski, Tom Fenchel, and Edward F. Delong, _The microbial engines that drive earth’s biogeochemical cycles_ , Science 320 (2008), no. 5879, 1034–1039.
  * [FHT10] Jerome H. Friedman, Trevor Hastie, and Rob Tibshirani, _Regularization paths for generalized linear models via coordinate descent_ , Journal of Statistical Software 33 (2010), no. 1, 1–22.
  * [Fie11] Stephen E Fienberg, _The analysis of contingency tables: From chi-squared tests and log-linear models to models of mixed membership_ , Stat. Biopharm. Res. 3 (2011), no. 2, 173–184 (en).
  * [FM14] Charles K. Fisher and Pankaj Mehta, _Identifying Keystone Species in the Human Gut Microbiome from Metagenomic Timeseries Using Sparse Linear Regression_ , PLoS ONE 9 (2014), no. 7, e102451.
  * [FR12] Karoline Faust and Jeroen Raes, _Microbial interactions: from networks to models_ , Nature Reviews Microbiology 10 (2012), no. 8, 538–550.
  * [GCLF18] Didier Gonze, Katharine Z Coyte, Leo Lahti, and Karoline Faust, _Microbial communities as dynamical systems_ , Current Opinion in Microbiology 44 (2018), 41–49.
  * [GCS+21] Xinzhou Ge, Yiling Elaine Chen, Dongyuan Song, Meilu McDermott, Kyla Woyshner, Antigoni Manousopoulou, Ning Wang, Wei Li, Leo D Wang, and Jingyi Jessica Li, _Clipper: p-value-free FDR control on high-throughput data from two conditions_ , Genome Biol. 22 (2021), no. 1, 288 (en).
  * [GFP14] Lisa Goers, Paul Freemont, and Karen M. Polizzi, _Co-culture systems and technologies: taking synthetic biology to the next level_ , Journal of The Royal Society Interface 11 (2014), no. 96, 20140065.
  * [GHG+18] Xuefeng Gao, Bich-Tram Huynh, Didier Guillemot, Philippe Glaser, and Lulla Opatowski, _Inference of significant microbial interactions from longitudinal metagenomics data_ , Front. Microbiol. 9 (2018), 2319 (en).
  * [GL12] Susan Gruber and Mark van der Laan, _tmle: An r package for targeted maximum likelihood estimation_ , Journal of Statistical Software 51 (2012), no. 13, 1–35.
  * [GLB+18] Joshua E Goldford, Nanxi Lu, Djordje Bajić, Sylvie Estrela, Mikhail Tikhonov, Alicia Sanchez-Gorostiaga, Daniel Segrè, Pankaj Mehta, and Alvaro Sanchez, _Emergent simplicity in microbial community assembly_ , Science 361 (2018), no. 6401, 469–474 (en).
  * [Gor94] Louis Gordon, _A Stochastic Approach to the Gamma Function_ , The American Mathematical Monthly 101 (1994), no. 9, 858.
  * [GR18] Jacqueline Goordial and Jennifer Ronholm, _Metagenomics meets read clouds_ , Nat. Biotechnol. 36 (2018), no. 11, 1049–1051 (en).
  * [Gre81] Ulf Grenander, _Abstract inference_ , Probability & Mathematical Statistics S., John Wiley & Sons, Nashville, TN, March 1981 (en).
  * [GRHW12] Mira T. Guo, Assaf Rotem, John A. Heyman, and David A. Weitz, _Droplet microfluidics for high-throughput biological assays_ , Lab on a Chip 12 (2012), no. 12, 2146–2155.
  * [GW11] Andrew Golightly and Darren J. Wilkinson, _Bayesian parameter inference for stochastic biochemical network models using particle markov chain monte carlo_ , Interface Focus 1 (2011), no. 6, 807–820.
  * [GWDM21] Akshit Goyal, Tong Wang, Veronika Dubinkina, and Sergei Maslov, _Ecology-guided prediction of cross-feeding interactions in the human gut microbiome_ , Nat. Commun. 12 (2021), no. 1, 1335 (en).
  * [GWV+11] David E Graham, Matthew D Wallenstein, Tatiana A Vishnivetskaya, Mark P Waldrop, Tommy J Phelps, Susan M Pfiffner, Tullis C Onstott, Lyle G Whyte, Elizaveta M Rivkina, David A Gilichinsky, Dwayne A Elias, Rachel Mackelprang, Nathan C VerBerkmoes, Robert L Hettich, Dirk Wagner, Stan D Wullschleger, and Janet K Jansson, _Microbes in thawing permafrost: the unknown variable in the climate change equation_ , The ISME Journal 6 (2011), no. 4, 709–712.
  * [Har53] Frank Harary, _On the notion of balance of a signed graph._ , Michigan Mathematical Journal 2 (1953), no. 2, 143 – 146.
  * [HCBNM02] C Huber-Carol, N Balakrishnan, M Nikulin, and M Mesbah (eds.), _Goodness-of-fit tests and model validity_ , 2002 ed., Statistics for Industry and Technology, Birkhäuser, Cambridge, MA, March 2002 (en).
  * [HCSB20] Joshua G Harrison, W John Calder, Vivaswat Shastry, and C Alex Buerkle, _Dirichlet-multinomial modelling outperforms alternatives for analysis of microbiome and other ecological count data_ , Mol. Ecol. Resour. 20 (2020), no. 2, 481–497 (en).
  * [HCT+19] Ryan H. Hsu, Ryan L. Clark, Jin Wen Tan, John C. Ahn, Sonali Gupta, Philip A. Romero, and Ophelia S. Venturelli, _Microbial interaction network inference in microfluidic droplets_ , Cell Systems 9 (2019), no. 3, 229–242.e4.
  * [HdlTCD91] J J Holland, J C de la Torre, D K Clarke, and E Duarte, _Quantitation of relative fitness and great adaptability of clonal populations of RNA viruses_ , J. Virol. 65 (1991), no. 6, 2960–2967 (en).
  * [HE15] Tailen Hsing and Randall Eubank, _Theoretical foundations of functional data analysis, with an introduction to linear operators_ , John Wiley & Sons, Ltd, May 2015.
  * [HFH21] Shion Hosoda, Tsukasa Fukunaga, and Michiaki Hamada, _Umibato: estimation of time-varying microbial interaction using continuous-time regression hidden Markov model_ , Bioinformatics 37 (2021), no. Supplement_1, i16–i24.
  * [HFJS10] Robin J. Hogan, Christopher A. T. Ferro, Ian T. Jolliffe, and David B. Stephenson, _Equitability Revisited: Why the ’Equitable Threat Score’ Is Not Equitable_ , Weather and Forecasting 25 (2010), no. 2, 710–726.
  * [HFZ18] Ning Hao, Yang Feng, and Hao Helen Zhang, _Model selection for high-dimensional quadratic regression via regularization_ , Journal of the American Statistical Association 113 (2018), no. 522, 615–625.
  * [HK12] Lajos Horváth and Piotr Kokoszka, _Inference for functional data with applications_ , Springer New York, 2012.
  * [HMvdW+20] Charles R. Harris, K. Jarrod Millman, Stéfan J van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río, Mark Wiebe, Pearu Peterson, Pierre Gérard-Marchant, Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant, _Array programming with NumPy_ , Nature 585 (2020), 357–362.
  * [HRM+19] Spencer Havis, Jonathan Rangel, Sujina Mali, Abiodun Bodunrin, Zina Housammy, Rene Zimmerer, Jesse Murphy, William R Widger, and Steven J Bark, _A color-based competition assay for studying bacterial stress responses in micrococcus luteus_ , FEMS Microbiol. Lett. 366 (2019), no. 5, fnz054 (en).
  * [HS02] A. R. Humphries and A. M. Stuart, _Deterministic and random dynamical systems: theory and numerics_ , Modern Methods in Scientific Computing and Applications (Anne Bourlioux, Martin J. Gander, and Gert Sabidussi, eds.), Springer Netherlands, Dordrecht, 2002, pp. 211–254.
  * [HTF09] Trevor Hastie, Robert Tibshirani, and Jerome Friedman, _The elements of statistical learning_ , Springer New York, 2009.
  * [Hun07] J. D. Hunter, _Matplotlib: A 2d graphics environment_ , Computing in Science & Engineering 9 (2007), no. 3, 90–95.
  * [HZ17] Ning Hao and Hao Helen Zhang, _A note on high-dimensional linear regression with interactions_ , The American Statistician 71 (2017), no. 4, 291–297.
  * [IBK06] E. L. Ionides, C. Bretó, and A. A. King, _Inference for nonlinear dynamical systems_ , Proceedings of the National Academy of Sciences 103 (2006), no. 49, 18438–18443.
  * [IYAR17] David I. Inouye, Eunho Yang, Genevera I. Allen, and Pradeep Ravikumar, _A review of multivariate distributions for count data derived from the poisson distribution_ , WIREs Computational Statistics 9 (2017), no. 3, 1–25.
  * [Joh04] Valen E Johnson, _A bayesian $\chi$2 test for goodness-of-fit_, Ann. Stat. 32 (2004), no. 6, 2361–2384 (en).
  * [Kee10] Robert W. Keener, _Theoretical statistics_ , Springer New York, 2010.
  * [KKK+11] Danai Koutra, Tai-You Ke, U. Kang, Duen Horng (Polo) Chau, Hsing-Kuo Kenneth Pao, and Christos Faloutsos, _Unifying guilt-by-association approaches: Theorems and fast algorithms_ , Machine Learning and Knowledge Discovery in Databases (Berlin, Heidelberg) (Dimitrios Gunopulos, Thomas Hofmann, Donato Malerba, and Michalis Vazirgiannis, eds.), Springer Berlin Heidelberg, 2011, pp. 245–260.
  * [KKO+19] Jared Kehe, Anthony Kulesa, Anthony Ortiz, Cheri M. Ackerman, Sri Gowtham Thakku, Daniel Sellers, Seppe Kuehn, Jeff Gore, Jonathan Friedman, and Paul C. Blainey, _Massively parallel screening of synthetic microbial communities_ , Proceedings of the National Academy of Sciences 116 (2019), no. 26, 12804–12809.
  * [KL08] Charles Kooperberg and Michael Leblanc, _Increasing the power of identifying gene x gene interactions in genome-wide association studies_ , Genet. Epidemiol. 32 (2008), no. 3, 255–263 (en).
  * [KMP+07] Yann Karlen, Alan McNair, Sébastien Perseguers, Christian Mazza, and Nicolas Mermod, _Statistical significance of quantitative pcr_ , BMC Bioinformatics 8 (2007), no. 1, 131.
  * [KOK+20] Jared Kehe, Anthony Ortiz, Anthony Kulesa, Jeff Gore, Paul C. Blainey, and Jonathan Friedman, _Positive interactions are common among culturable bacteria_ , bioRxiv (2020), 169474.
  * [KP10] Peter E Kloeden and Eckhard Platen, _Numerical solution of stochastic differential equations_ , Stochastic Modelling and Applied Probability, Springer, Berlin, Germany, December 2010 (en).
  * [KR21] Piotr Kokoszka and Matthew Reimherr, _Introduction to functional data analysis_ , Chapman & Hall/CRC Texts in Statistical Science, Taylor & Francis, London, England, June 2021.
  * [Kri20] William E. Krinsman, _Tensor algebra and its applications to data science and statistics_ , Master’s thesis, University of California, Berkeley, 2020.
  * [KSV+16] Danai Koutra, Neil Shah, Joshua T. Vogelstein, Brian Gallagher, and Christos Faloutsos, _DeltaCon_ , ACM Transactions on Knowledge Discovery from Data 10 (2016), no. 3, 1–43.
  * [KTS+15] Arto Klami, Abhishek Tripathi, Johannes Sirola, Lauri Väre, and Frederic Roulland, _Latent feature regression for multivariate count data_ , Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics (San Diego, California, USA) (Guy Lebanon and S. V. N. Vishwanathan, eds.), Proceedings of Machine Learning Research, vol. 38, PMLR, 09–12 May 2015, pp. 462–470.
  * [KvVDH10] Balint Kintses, Liisa D van Vliet, Sean RA Devenish, and Florian Hollfelder, _Microfluidic droplets: new integrated workflows for biological experiments_ , Current Opinion in Chemical Biology 14 (2010), no. 5, 548–555.
  * [LBG10] Fraser Lewis, Adam Butler, and Lucy Gilbert, _A unified approach to model selection using the likelihood ratio test_ , Methods in Ecology and Evolution 2 (2010), no. 2, 155–162.
  * [LC98] Erich L Lehmann and George Casella, _Theory of point estimation_ , 2 ed., Springer Texts in Statistics, Springer, New York, NY, September 1998 (en).
  * [LE13] Todd P Lagus and Jon F Edd, _A review of the theory, methods and recent applications of high-throughput single-cell droplet microfluidics_ , Journal of Physics D: Applied Physics 46 (2013), no. 11, 114005.
  * [LHYA16] Freeman Lan, John R Haliburton, Aaron Yuan, and Adam R Abate, _Droplet barcoding for massively parallel single-molecule deep sequencing_ , Nat. Commun. 7 (2016), 11784 (en).
  * [Lid79] William Z. Lidicker, _A clarification of interactions in ecological systems_ , BioScience 29 (1979), no. 8, 475–477.
  * [LLLW11] Tao Lu, Hua Liang, Hongzhe Li, and Hulin Wu, _High-dimensional ODEs coupled with mixed-effects modeling techniques for dynamic gene regulatory network identification_ , Journal of the American Statistical Association 106 (2011), no. 496, 1242–1258.
  * [LPR19] Jose V Lopez, Raquel S Peixoto, and Alexandre S Rosado, _Inevitable future: space colonization beyond earth with microbes first_ , FEMS Microbiology Ecology 95 (2019), no. 10, 1–9.
  * [LR20] Keli Liu and Feng Ruan, _A self-penalizing objective function for scalable interaction detection_ , 2020.
  * [LS07] James O. Lloyd-Smith, _Maximum Likelihood Estimation of the Negative Binomial Dispersion Parameter for Highly Overdispersed Data, with Applications to Infectious Diseases_ , PLoS ONE 2 (2007), no. 2, e180.
  * [LS09] F. William Lawvere and Stephen H. Schanuel, _Conceptual Mathematics: A First Introduction to Categories_ , Cambridge University Press, Cambridge, UK New York, 2009.
  * [LS19] Leo Lahti and Sudarshan Shetty, _microbiome r package_ , 2012-2019.
  * [LYS+19] Hsiao-Han Lin, Manda Yu, Manoj Kumar Sriramoju, Shang-Te Danny Hsu, Chi-Te Liu, and Erh-Min Lai, _A high-throughput interbacterial competition screen identifies ClpAP in enhancing recipient susceptibility to type VI secretion system-mediated attack by agrobacterium tumefaciens_ , Front. Microbiol. 10 (2019), 3077 (en).
  * [MBH+14] Simeone Marino, Nielson T Baxter, Gary B Huffnagle, Joseph F Petrosino, and Patrick D Schloss, _Mathematical modeling of primary succession of murine intestinal microbiota_ , Proc. Natl. Acad. Sci. U. S. A. 111 (2014), no. 1, 439–444 (en).
  * [MGH80] Jorge J. Moré, Burton S. Garbow, and Kenneth E. Hillstrom, _User guide for MINPACK-1_ , Tech. Report ANL-80-74, Argonne National Laboratory, Argonne, IL, USA, August 1980.
  * [MGSD19] Andrew McDavid, Raphael Gottardo, Noah Simon, and Mathias Drton, _Graphical models for zero-inflated single cell gene expression_ , Ann. Appl. Stat. 13 (2019), no. 2, 848–873 (en).
  * [MH13] Paul J. McMurdie and Susan Holmes, _phyloseq: An r package for reproducible interactive analysis and graphics of microbiome census data_ , PLOS ONE 8 (2013), no. 4, 1–11.
  * [MJS20] R S MacKay, S Johnson, and B Sansom, _How directed is a directed network?_ , R. Soc. Open Sci. 7 (2020), no. 9, 201138 (en).
  * [MKBDB00] A F Marée, W Keulen, C A Boucher, and R J De Boer, _Estimating relative fitness in viral competition experiments_ , J. Virol. 74 (2000), no. 23, 11067–11072 (en).
  * [MMV+08] Jerome Mounier, Christophe Monnet, Tatiana Vallaeys, Roger Arditi, Anne-Sophie Sarthou, Arnaud Helias, and Francoise Irlinger, _Microbial Interactions within a Cheese Microbial Community_ , Applied and Environmental Microbiology 74 (2008), no. 1, 172–181.
  * [MRH20] Kinga Matula, Francesca Rivello, and Wilhelm T. S. Huck, _Single-cell analysis using droplet microfluidics_ , Advanced Biosystems 4 (2020), no. 1, 1900188.
  * [MSH+08] Ramamurthy Mani, Robert P. St.Onge, John L. Hartman, Guri Giaever, and Frederick P. Roth, _Defining genetic interaction_ , Proceedings of the National Academy of Sciences 105 (2008), no. 9, 3461–3466.
  * [MSH+19] Clarisse Marotz, Anukriti Sharma, Greg Humphrey, Neil Gottel, Christopher Daum, Jack A Gilbert, Emiley Eloe-Fadrosh, and Rob Knight, _Triplicate PCR reactions for 16S rRNA gene amplicon sequencing are unnecessary_ , Biotechniques 67 (2019), no. 1, 29–32 (en).
  * [MTFH16] Ahmad Mahmood, Oğuz Can Turgay, Muhammad Farooq, and Rifat Hayat, _Seed biopriming with plant growth promoting rhizobacteria: a review_ , FEMS Microbiology Ecology 92 (2016), no. 8, 1–14.
  * [MWC19] Michael R McLaren, Amy D Willis, and Benjamin J Callahan, _Consistent and correctable bias in metagenomic sequencing experiments_ , eLife 8 (2019), e46923.
  * [MXS17] Babak Momeni, Li Xie, and Wenying Shou, _Lotka-volterra pairwise modeling fails to capture diverse pairwise microbial interactions_ , eLife 6 (2017), e25051.
  * [Nak97] Eiji Nakashima, _Some Methods for Estimation in a Negative-Binomial Model_ , Annals of the Institute of Statistical Mathematics 49 (1997), no. 1, 101–115.
  * [NW18] Deborah A Neher and Thomas R Weicht, _A plate competition assay as a quick preliminary assessment of disease suppression_ , J. Vis. Exp. (2018), no. 140, e58767 (en).
  * [OTN+17] Otso Ovaskainen, Gleb Tikhonov, Anna Norberg, F. Guillaume Blanchet, Leo Duan, David Dunson, Tomas Roslin, and Nerea Abrego, _How to make more out of community data? a conceptual framework and its implementation as models and software_ , Ecology Letters 20 (2017), no. 5, 561–576.
  * [PE00] Mercedes Pascual and Stephen P. Ellner, _Linking ecological patterns to environmental forcing via nonlinear time series models_ , Ecology 81 (2000), no. 10, 2767–2780.
  * [PGB21] Vincent Prost, Stéphane Gazut, and Thomas Brüls, _A zero inflated log-normal model for inference of sparse microbial association networks_ , PLOS Computational Biology 17 (2021), no. 6, e1009089.
  * [Pie90] Walter W. Piegorsch, _Maximum Likelihood Estimation for the Negative Binomial Dispersion Parameter_ , Biometrics 46 (1990), no. 3, 863–867.
  * [PM17] Nathan T. Porter and Eric C. Martens, _The Critical Roles of Polysaccharides in Gut Microbial Ecology and Physiology_ , Annual Review of Microbiology 71 (2017), no. 1, 349–369.
  * [Pow70] M. J. D. Powell, _A Hybrid Method for Nonlinear Equations_ , Numerical Methods for Nonlinear Algebraic Equations (P. Rabinowitz, ed.), Gordon and Breach, 1970.
  * [PPG+10] Maya L Petersen, Kristin E Porter, Susan Gruber, Yue Wang, and Mark J van der Laan, _Diagnosing and responding to violations in the positivity assumption_ , Statistical Methods in Medical Research 21 (2010), no. 1, 31–54.
  * [PSG+21] Prapti Pattanayak, Sachin Kumar Singh, Monica Gulati, Sukriti Vishwas, Bhupinder Kapoor, Dinesh Kumar Chellappan, Krishnan Anand, Gaurav Gupta, Niraj Kumar Jha, Piyush Kumar Gupta, Parteek Prasher, Kamal Dua, Harish Dureja, Deepak Kumar, and Vijay Kumar, _Microfluidic chips: recent advances, critical strategies in design, applications and future perspectives_ , Microfluid. Nanofluidics 25 (2021), no. 12, 99 (en).
  * [QMT+17] Xiaojie Qiu, Qi Mao, Ying Tang, Li Wang, Raghav Chawla, Hannah A Pliner, and Cole Trapnell, _Reversed graph embedding resolves complex single-cell trajectories_ , Nat. Methods 14 (2017), no. 10, 979–982 (en).
  * [QSyL+08] Yan Qi, Yasir Suhail, Yu yi Lin, Jef D. Boeke, and Joel S. Bader, _Finding friends and enemies in an enemies-only network: A graph diffusion kernel for predicting novel genetic interactions and co-complex membership from yeast genetic interactions_ , Genome Research 18 (2008), no. 12, 1991–2004.
  * [RDC+06] Daniel C. Reuman, Robert A. Desharnais, Robert F. Costantino, Omar S. Ahmad, and Joel E. Cohen, _Power spectra reveal the influence of stochasticity on nonlinear population dynamics_ , Proceedings of the National Academy of Sciences 103 (2006), no. 49, 18860–18865.
  * [RGG+21] Morteza Roodgar, Benjamin H Good, Nandita R Garud, Stephen Martis, Mohan Avula, Wenyu Zhou, Samuel M Lancaster, Hayan Lee, Afshin Babveyh, Sophia Nesamoney, Katherine S Pollard, and Michael P Snyder, _Longitudinal linked-read sequencing reveals ecological and evolutionary responses of a human gut microbiome during antibiotic treatment_ , Genome Res. 31 (2021), no. 8, 1433–1446 (en).
  * [RH17] James Ramsay and Giles Hooker, _Dynamic data analysis_ , Springer New York, 2017\.
  * [RHCC07] J. O. Ramsay, G. Hooker, D. Campbell, and J. Cao, _Parameter estimation for differential equations: a generalized smoothing approach_ , Journal of the Royal Statistical Society: Series B (Statistical Methodology) 69 (2007), no. 5, 741–796.
  * [RHG09] James Ramsay, Giles Hooker, and Spencer Graves, _Functional data analysis with R and MATLAB_ , Springer New York, 2009.
  * [Rob55] Herbert Robbins, _A Remark on Stirling’s Formula_ , The American Mathematical Monthly 62 (1955), no. 1, 26–29.
  * [RP85] G. J. S. Ross and D. A. Preece, _The Negative Binomial Distribution_ , Journal of the Royal Statistical Society. Series D (The Statistician) 34 (1985), no. 3, 323–335.
  * [RS05] J. O. Ramsay and B. W. Silverman, _Functional data analysis_ , Springer New York, 2005.
  * [SBT+13] Richard R Stein, Vanni Bucci, Nora C Toussaint, Charlie G Buffie, Gunnar Rätsch, Eric G Pamer, Chris Sander, and João B Xavier, _Ecological modeling from time-series inference: insight into dynamics and stability of intestinal microbiota_ , PLoS Comput. Biol. 9 (2013), no. 12, e1003388 (en).
  * [Sco92] David Scott, _Multivariate Density Estimation : Theory, Practice, and Visualization_ , John Wiley & Sons, New York, Chicester, 1992.
  * [SCZ17] Luoran Shang, Yao Cheng, and Yuanjin Zhao, _Emerging droplet microfluidics_ , Chemical Reviews 117 (2017), no. 12, 7964–8040.
  * [Sel13] Peter Selinger, _Lecture notes on the lambda calculus_ , 2013.
  * [Ser80] Robert J Serfling, _Approximation theorems of mathematical statistics_ , Wiley Series in Probability and Statistics, Wiley-Interscience, Newy York, September 1980 (en).
  * [SFB14] Eric K. Sackmann, Anna L. Fulton, and David J. Beebe, _The present and future role of microfluidics in biomedical research_ , Nature 507 (2014), no. 7491, 181–189.
  * [Skl14] Max Sklar, _Fast MLE Computation for the Dirichlet Multinomial_ , 2014.
  * [SkM20] Somayeh Sohrabi, Nour kassir, and Mostafa Keshavarz Moraveji, _Droplet microfluidics: fundamentals and its advanced applications_ , RSC Advances 10 (2020), no. 46, 27560–27574.
  * [SL21] Dongyuan Song and Jingyi Jessica Li, _PseudotimeDE: inference of differential gene expression along cell pseudotime with well-calibrated p-values from single-cell RNA sequencing data_ , Genome Biol. 22 (2021), no. 1, 124 (en).
  * [SMY+12] George Sugihara, Robert May, Hao Ye, Chih-Hao Hsieh, Ethan Deyle, Michael Fogarty, and Stephan Munch, _Detecting causality in complex ecosystems_ , Science 338 (2012), no. 6106, 496–500 (en).
  * [SP10] Skipper Seabold and Josef Perktold, _statsmodels: Econometric and statistical modeling with python_ , 9th Python in Science Conference, 2010.
  * [SS19] Lauren Speare and Alecia N Septer, _Coincubation assay for quantifying competitive interactions between vibrio fischeri isolates_ , J. Vis. Exp. (2019), no. 149, e59759 (en).
  * [SSB+17] Yu Shang, Johannes Sikorski, Michael Bonkowski, Anna-Maria Fiore-Donno, Ellen Kandeler, Sven Marhan, Runa S Boeddinghaus, Emily F Solly, Marion Schrumpf, Ingo Schöning, Tesfaye Wubet, Francois Buscot, and Jörg Overmann, _Inferring interactions in complex microbial communities from nucleotide sequence data and environmental parameters_ , PLoS One 12 (2017), no. 3, e0173765 (en).
  * [Str85] Helmut Strasser, _Mathematical theory of statistics: Statistical experiments and asymptotic decision theory_ , De Gruyter, 1985.
  * [SW62] L. R. Shenton and P. A. Wallington, _The Bias of Moment Estimators with an Application to the Negative Binomial Distribution_ , Biometrika 49 (1962), no. 1/2, 193–204.
  * [SWMD17] Justin D Silverman, Alex D Washburne, Sayan Mukherjee, and Lawrence A David, _A phylogenetic transform enhances analysis of compositional microbiota data_ , Elife 6 (2017), e21887 (en).
  * [TCG+14] Cole Trapnell, Davide Cacchiarelli, Jonna Grimsby, Prapti Pokharel, Shuqiang Li, Michael Morse, Niall J Lennon, Kenneth J Livak, Tarjei S Mikkelsen, and John L Rinn, _The dynamics and regulators of cell fate decisions are revealed by pseudotemporal ordering of single cells_ , Nat. Biotechnol. 32 (2014), no. 4, 381–386 (en).
  * [TF08] Wei-Chang Tian and Erin Finehout, _Introduction to Microfluidics_ , Microfluidics for Biological Applications, Springer US, 2008, pp. 1–34.
  * [TITP19] Mattia Tantardini, Francesca Ieva, Lucia Tajoli, and Carlo Piccardi, _Comparing Methods for Comparing Networks_ , Scientific Reports 9 (2019), no. 1, 1–19.
  * [TKA20] Giuseppe Torrisi, Reimer Kühn, and Alessia Annibale, _Percolation on the gene regulatory network_ , Journal of Statistical Mechanics: Theory and Experiment 2020 (2020), no. 8, 083501.
  * [TLHL08] Shia-Yen Teh, Robert Lin, Lung-Hsin Hung, and Abraham P. Lee, _Droplet microfluidics_ , Lab on a Chip 8 (2008), no. 2, 198–220.
  * [Tre06] Nickolay T Trendafilov, _The dynamical system approach to multivariate data analysis_ , J. Comput. Graph. Stat. 15 (2006), no. 3, 628–650 (en).
  * [TRKS+17] Daniel Taylor-Rodríguez, Kimberly Kaufeld, Erin M. Schliep, James S. Clark, and Alan E. Gelfand, _Joint species distribution modeling: Dimension reduction using dirichlet processes_ , Bayesian Analysis 12 (2017), no. 4, 939–967.
  * [TVL+22] Daniel Taylor, Nia Verdon, Peter Lomax, Rosalind J Allen, and Simon Titmuss, _Tracking the stochastic growth of bacterial populations in microfluidic droplets_ , Physical Biology 19 (2022), no. 2, 026003.
  * [UF13] Shahid Ullah and Caroline F Finch, _Applications of functional data analysis: A systematic review_ , BMC Med. Res. Methodol. 13 (2013), no. 1, 43 (en).
  * [Vaa98] A. W. van der Vaart, _Asymptotic statistics_ , Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press, 1998.
  * [VCF+18] Ophelia S Venturelli, Alex V Carr, Garth Fisher, Ryan H Hsu, Rebecca Lau, Benjamin P Bowen, Susan Hromada, Trent Northen, and Adam P Arkin, _Deciphering microbial interactions in synthetic human gut microbiome communities_ , Molecular Systems Biology 14 (2018), no. 6, 1–19.
  * [vdLPH07] Mark J. van der Laan, Eric C Polley, and Alan E. Hubbard, _Super learner_ , Statistical Applications in Genetics and Molecular Biology 6 (2007), no. 1, 1–21.
  * [vdLR11] Mark J. van der Laan and Sherri Rose, _Targeted learning_ , Springer New York, 2011.
  * [vdLR18] , _Targeted learning in data science_ , Springer International Publishing, 2018.
  * [VGO+20] Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Kern, Eric Larson, C J Carey, İlhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1.0 Contributors, _SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python_ , Nature Methods 17 (2020), 261–272.
  * [Was21] Michael L. Waskom, _seaborn: statistical data visualization_ , Journal of Open Source Software 6 (2021), no. 60, 3021.
  * [WBGLR+21] Deborah Weighill, Marouen Ben Guebila, Camila Lopes-Ramos, Kimberly Glass, John Quackenbush, John Platig, and Rebekka Burkholz, _Gene regulatory network inference as relaxed graph matching_ , Proceedings of the AAAI Conference on Artificial Intelligence 35 (2021), no. 11, 10263–10272.
  * [WCM16] Jane-Ling Wang, Jeng-Min Chiou, and Hans-Georg Müller, _Functional data analysis_ , Annual Review of Statistics and Its Application 3 (2016), no. 1, 257–295.
  * [WFY84] Linda J. Willson, J. Leroy Folks, and J. H. Young, _Multistage Estimation Compared with Fixed-Sample-Size Estimation of the Negative Binomial Parameter k_ , Biometrics 40 (1984), no. 1, 109–117.
  * [WFY86] L. J. Willson, J. L. Folks, and J. H. Young, _Complete sufficiency and maximum likelihood estimation for the two-parameter negative binomial distribution_ , Metrika 33 (1986), no. 1, 349–362.
  * [Whi06] George M. Whitesides, _The origins and the future of microfluidics_ , Nature 442 (2006), no. 7101, 368–373.
  * [Wic16] Hadley Wickham, _ggplot2: Elegant graphics for data analysis_ , Springer-Verlag New York, 2016.
  * [Wil18] Darren J Wilkinson, _Stochastic modelling for systems biology_ , 3 ed., Chapman & Hall/CRC Mathematical and Computational Biology, CRC Press, London, England, November 2018.
  * [WL02] Michael Wagner and Alexander Loy, _Bacterial community composition and function in sewage treatment systems_ , Current Opinion in Biotechnology 13 (2002), no. 3, 218–227.
  * [WL15] Michael J Wiser and Richard E Lenski, _A comparison of methods to measure fitness in escherichia coli_ , PLoS One 10 (2015), no. 5, e0126210 (en).
  * [WM20] Peter Wills and François G. Meyer, _Metrics for graph comparison: A practitioner’s guide_ , PLOS ONE 15 (2020), no. 2, e0228728.
  * [Woo10] Simon N. Wood, _Statistical inference for noisy nonlinear ecological dynamic systems_ , Nature 466 (2010), no. 7310, 1102–1104.
  * [WPW+15] Kelly M Wetmore, Morgan N Price, Robert J Waters, Jacob S Lamson, Jennifer He, Cindi A Hoover, Matthew J Blow, James Bristow, Gareth Butland, Adam P Arkin, and Adam Deutschbauer, _Rapid quantification of mutant fitness in diverse bacteria by sequencing randomly bar-coded transposons_ , MBio 6 (2015), no. 3, e00306–15 (en).
  * [WSCR03] Lance A Waller, David Smith, James E Childs, and Leslie A Real, _Monte carlo assessments of goodness-of-fit for ecological simulation models_ , Ecol. Modell. 164 (2003), no. 1, 49–63 (en).
  * [XAF+17] Yandong Xiao, Marco Tulio Angulo, Jonathan Friedman, Matthew K. Waldor, Scott T. Weiss, and Yang-Yu Liu, _Mapping the ecological networks of microbial communities_ , Nature Communications 8 (2017), no. 1, 1–12.
  * [YEJ+07] Takehito Yoshida, Stephen P Ellner, Laura E Jones, Brendan J. M Bohannan, Richard E Lenski, and Nelson G Hairston, _Cryptic population dynamics: Rapid evolution masks trophic interactions_ , PLoS Biology 5 (2007), no. 9, e235.
  * [YHV13] Danni Yu, Wolfgang Huber, and Olga Vitek, _Shrinkage estimation of dispersion in Negative Binomial models for RNA-seq experiments with small sample size_ , Bioinformatics 29 (2013), no. 10, 1275–1282.
  * [YRCS06] Joshua S. Yuan, Ann Reed, Feng Chen, and C. Neal Stewart, _Statistical analysis of real-time pcr data_ , BMC Bioinformatics 7 (2006), no. 1, 85\.
  * [YS14] Peng Yu and Chad A. Shaw, _An efficient algorithm for accurate computation of the dirichlet-multinomial log-likelihood function_ , Bioinformatics 30 (2014), no. 11, 1547–1554.
  * [YSP+19] Sukhwan Yoon, Bongkeun Song, Rebecca L Phillips, Jin Chang, and Min Joon Song, _Ecological and physiological implications of nitrogen oxide reduction pathways on greenhouse gas emissions in agroecosystems_ , FEMS Microbiology Ecology 95 (2019), no. 6, 1–15.
  * [YWSJ08] Joshua S. Yuan, Donglin Wang, and C. Neal Stewart Jr., _Statistical methods for efficiency adjusted real-time pcr quantification_ , Biotechnology Journal 3 (2008), no. 1, 112–123.
  * [Zho18] Mingyuan Zhou, _Nonparametric Bayesian Negative Binomial Factor Analysis_ , Bayesian Analysis 13 (2018), no. 4, 1065–1093.
  * [ZHSL12] Or Zuk, Eliana Hechter, Shamil R Sunyaev, and Eric S Lander, _The mystery of missing heritability: Genetic interactions create phantom heritability_ , Proc. Natl. Acad. Sci. U. S. A. 109 (2012), no. 4, 1193–1198 (en).
  * [ZW17] Pingan Zhu and Liqiu Wang, _Passive and active droplet generation with microfluidics: a review_ , Lab on a Chip 17 (2017), no. 1, 34–75.
  * [ZYLS18] Chen Zhang, Hao Yan, Seungho Lee, and Jianjun Shi, _Dynamic multivariate functional data modeling via sparse subspace learning_ , 2018.
  * [ZZZS17] Yiwen Zhang, Hua Zhou, Jin Zhou, and Wei Sun, _Regression models for multivariate count data_ , Journal of Computational and Graphical Statistics 26 (2017), no. 1, 1–13.

###  Appendix A.1 Relevant Background on Differential Equations

The goals of the simulations were to follow the precedent of prior work
[VCF+18] [FM14] [MBH+14] [SBT+13] [MMV+08] in postulating a likelihood model
similar to the generalized Lotka-Volterra equations (cf. again section 7.5),
while also being more biologically realistic in both (i) not having any
restrictions on interaction coefficients (which would seem to be arbitrary
from a biological point of view), and (ii) addressing the capacity for
nutrient depletion and waste product accumulation to moderate changes in
population size, something which seems especially relevant, and even
inappropriate to ignore, inside of the highly resource-limited (oligotrophic)
environment of a microfluidic droplet.

####  1 Exponential Growth: Unlimited Resources

The exponential differential equation describes the idealized situation where
the rate of change in the population is directly proportional to the current
number of cells:

$\frac{\mathrm{d}n}{\mathrm{d}t}=rn\,,$ (1.1)

which is equivalent (for populations with more than zero cells) to the even
simpler equation:

$\frac{\mathrm{d}(\log n)}{\mathrm{d}t}=r\,.$ (1.2)

The second form emphasizes how this idealized situation corresponds to what is
often referred to as a constant growth (or decay) rate.

####  2 Nutrient Limitation and Indirect Interactions

The exponential model is often considered adequate for describing the growth
under copiotrophic conditions immediately following the initial lag phase.
However, since the effects of nutrient depletion and waste product
accumulation increase with the size of the population, for large enough
populations it becomes unrealistic to model the population size’s effect on
the rate of change as being constant. Instead an additional multiplicative
factor can be included to describe how growth is expected to slow down as
nutrients are depleted and waste products accumulate:

$\frac{\mathrm{d}(\log x)}{\mathrm{d}t}=r\left(1-\frac{x}{K}\right)\,.$ (2.1)

This is called the logistic differential equation. As the population size
continues to approach the constant $K$, growth slows down (asymptotically)
towards nothing, causing $K$ to represent an upper bound on the total possible
population size. This upper bound is often referred to as the carrying
capacity of the environment which supports the population.

Assuming that the population sizes of any given strain do not affect the
population sizes of the other strains, it is straightforward to model the
simultaneous exponential growth of multiple strains via a system of
differential equations:

$\frac{\mathrm{d}(\log n^{(s)})}{\mathrm{d}t}=r_{s}\,.$ (2.2)

When still assuming that the population sizes of different strains do not
affect one another, it is also straightforward in exactly the same manner to
model the simultaneous logistic growth of multiple strains using a system of
differential equations:

$\frac{\mathrm{d}(\log
n^{(s)})}{\mathrm{d}t}=r_{s}\left(1-\frac{n^{(s)}}{K_{s}}\right)\,.$ (2.3)

The above system of equations (2.3) is unrealistic, however, inasmuch as it
assumes not only that the population sizes of different strains do not
directly affect one another, but also because it assumes that the environment
has a separate carrying capacity for each strain, independent of that for all
other strains.

Especially in an environment like the interior of a single droplet in a
microfluidics experiment, the same nutrient supply will often be common/shared
among all strains, and the accumulation of waste products will affect all
strains simultaneously. In other words, in a limited resource environment
strains will almost always interact with each other at least indirectly, with
the indirect interactions being mediated by the nutrient supply and
concentration of waste products. Therefore it is often more realistic to
assume a single carrying capacity for the total aggregate population size of
all strains in the environment. The following system of equations better
models the aforementioned situation:

$\frac{\mathrm{d}(\log
n^{(s)})}{\mathrm{d}t}=r_{s}\left(1-\frac{\sum_{{\sigma}}n^{({\sigma})}}{K}\right)\,,$
(2.4)

since as the total aggregate population size of all strains (asymptotically)
approaches the common and shared carrying capacity $K$ of the environment, the
growth of all strains will simultaneously slow (asymptotically) towards zero.
It is worth noting though that in practice different strains can have wildly
varying metabolisms, such that what constitutes a nutrient or a harmful waste
product could differ substantially between strains, and making the above
description overly simplistic. For examples of models accounting for the
potentially different metabolisms of different strains, see e.g. [EVL+22],
[GWDM21], [ESGVS21], [ELW+20], [GLB+18], or [MXS17]. (For an overview, see
[GCLF18].) However, fully addressing this issue falls outside of the scope of
the current manuscript and is left for future work.

#####  2.1 Comparison with Previous Work

The paper [MBH+14] uses equations analogous to (2.3), with $K_{s}=K$ for all
$s$ for a common $K$, and claims that this alone is sufficient alone to
enforce the constraint that $\sum_{{\sigma}}n^{({\sigma})}\leq K$ always.
However, that does not seem to be true. As far as I can tell, with an equation
of that form alone, there is no reason at all why the (logarithmic)
derivatives of all strains should approach $0$ as
$\sum_{{\sigma}}n^{({\sigma})}\to K$. If the growth rates do not
asymptotically approach $0$ as the total population sizes
$\sum_{{\sigma}}n^{({\sigma})}$ of all strains approaches the supposedly
common carrying capacity $K$, then there is no reason to expect in general
that $\sum_{{\sigma}}n^{({\sigma})}\leq K$.

For example, based on (2.3), as $n^{(s_{1})}\to K/2$ and $n^{(s_{2})}\to K/2$
the growth rates of $s_{1}$ and $s_{2}$ would not seem to be approach $0$. Yet
under those circumstances $\sum_{{\sigma}}n^{({\sigma})}\leq K$. Hence, absent
a flaw in the above reasoning, it seems clear that (2.3) is incapable of
enforcing a common carrying capacity constraint shared by all strains
simultaneously.

In contrast, it is obviously the case for the proposed equation (2.4) that the
growth rates of all strains will asymptotically approach $0$ as
$\sum_{{\sigma}}n^{({\sigma})}\to K$.

####  3 Direct Interactions

Even focusing on the initial regime where diminishing nutrient supplies and
increasing waste product concentrations have not yet become significant
factors affecting growth, the assumption in (2.2) that the growth of any given
strain’s population is unaffected by the population sizes of other strains can
still be unrealistic. This is of course because of direct interactions between
different strains of microbes, which can either support or inhibit their
growth, and which are the primary focus of interest of the current manuscript.
The generalized Lotka-Volterra equations seek to account for direct
interactions by adding to (2.2) a linear interaction term:

$\frac{\mathrm{d}(\log
n^{(s)})}{\mathrm{d}t}=r_{s}+\sum_{\sigma=1}^{S}\alpha_{\sigma
s}n^{(\sigma)}\,.$ (3.1)

The model describes interactions between different strains through the
magnitude and sign of the coefficients in the portion of the affine
expressions above which are a linear combination of the population sizes of
all of the strains. Positive coefficients correspond to mutualistic
interactions between strains whereas negative coefficients correspond to
antagonistic interactions between strains.

####  4 Combining Indirect and Direct Interactions

The simulations used in this paper seek to capture both indirect and direct
interactions between microbial strains by combining models (2.4) and (3.1)
above in a straightforward way:

$\frac{\mathrm{d}(\log
n^{(s)})}{\mathrm{d}t}=\left(r_{s}+\sum_{\sigma=1}^{S}\alpha_{\sigma
s}n^{(\sigma)}\right)\left(1-\frac{\sum_{{\sigma}}n^{(\sigma)}}{K}\right)\,.$
(4.1)

This preserves the property that the change in population size will slow
towards zero as the total aggregate population size approaches the
environment’s carrying capacity, while still retaining ability for the
population sizes of various strains to directly affect one another. This makes
sense even in the case of antagonistic interactions, since as the growth of
the antagonizing strain slows towards zero (along with the growth of all
growing strains), one would expect that the magnitude of the antagonizing
interaction would also slow towards zero, making it sensible for the decay in
the population size in the antagonized strain to slow towards zero as well.

Also, unlike the regular generalized Lotka-Volterra equations, it is intended
that, for any possible choice of direct interaction coefficients, the
population sizes of any solutions will remain bounded for any initial
condition for which the carrying capacity of the aggregate population is not
exceeded. (Cf. for example [VCF+18] which excludes certain combinations of
coefficient values to prevent the possibility of blow-up. To me that seems
arbitrary from a purely biological point of view.) This is an additional
source of realism for (4.1), since there does not seem to be any a priori
biological reason for why certain combinations of values of interaction
coefficients should be prohibited. This quote from [MBH+14] is precedent for
the above viewpoint on parameter constraints:

> One approach to improving parameter estimation is to superimpose constraints
> on the parameters; however, unless these constraints can be justified both
> biologically and mathematically, they should not be enforced because the
> results can be greatly affected.

#####  4.1 Comparison with Previous Work

Note that the derivation of (4.1) given above is not the first attempt to
combine logistic growth constraints with gLV-like direct interactions. Notably
[MBH+14] proposes an equation of the form (modulo logarithms and differences
in notation):

$\frac{\mathrm{d}(\log
n^{(s)})}{\mathrm{d}t}=r_{s}\left(1-\frac{n^{(\sigma)}}{K}\right)+\sum_{\sigma=1}^{S}\alpha_{\sigma
s}n^{(\sigma)}\,.$ (4.2)

In section 2.1 above I already explained why the proposed implementation of a
common carrying capacity in (4.2) does not seem to enforce the intended
constraint $\sum_{{\sigma}}n^{({\sigma})}\leq K$. Let us apply the fix
proposed in 2.1, namely switching the attempted carrying capacity
implementation from a form similar to (2.3) to a form similar instead to
(2.4):

$\frac{\mathrm{d}(\log
n^{(s)})}{\mathrm{d}t}=r_{s}\left(1-\frac{\sum_{{\sigma}}n^{(\sigma)}}{K}\right)+\sum_{\sigma=1}^{S}\alpha_{\sigma
s}n^{(\sigma)}\,.$ (4.3)

However (4.3) also seems to fail to enforce the intended constraint
$\sum_{{\sigma}}n^{({\sigma})}\leq K$, for the same reason that (2.3) does.
Namely, without distributing the “logistic factor” across the entire
expression, which is done in (4.1), again there does not seem to be any reason
why we should have for (4.3) that all growth rates simultaneously approach $0$
as $\sum_{{\sigma}}n^{({\sigma})}\to K$. In contrast, (4.1) was explicitly
designed so that all growth rates simultaneously approach $0$ as
$\sum_{{\sigma}}n^{({\sigma})}\to K$. Hence it seems much more plausible to me
that (4.1) enforces the intended constraint $\sum_{{\sigma}}n^{({\sigma})}\leq
K$, whereas I do not see why either (4.2) or (4.3) would. Thus (4.1) seems to
be an improvement on previous work.

####  5 Common Framework

All of the above systems of equations fit into the following framework:

$\frac{\mathrm{d}(\log
n^{(s)})}{\mathrm{d}t}=G_{s}(n^{(1)},\dots,n^{(S)})\left(1-\frac{H_{s}(n^{(1)},\dots,n^{(S)})}{K_{s}}\right)\,,$
(5.1)

where $G_{s}$ corresponds to the growth of the given strain under idealized
conditions, and $H_{s}$ is a quantity for which the external environment
imposes some finite carrying capacity $K_{s}$, such that $H_{s}\rightarrow
K_{s}$ causes all changes in the population size of strain $s$ to slow towards
zero. For equations (2.2), (2.3), and (2.4), one has that $G_{s}=r_{s}$,
whereas for equations (3.1) and (4.1) one has instead that
$G_{s}=r_{s}+\sum_{\sigma=1}^{S}\alpha_{\sigma s}n^{(\sigma)}$. For equations
(2.2) and (3.1) one has that $H_{s}=0$, for equation (2.3) one has that
$H_{s}=n^{(s)}$, and for equations (2.4) and (4.1) one has instead that
$H_{s}=\sum_{{\sigma}}n^{(\sigma)}$ as well as that $K_{s}=K$ for all
$s\in[S]$ for a given fixed constant $K$.

Of course in order for its effect on changes in the population size of strain
$s$ to have any clear interpretation as an external limitation on the
magnitude of changes in the system, one needs that $0\leq H_{s}\leq K_{s}$ so
that the factor multiplying $G_{s}$ is always a value between $0$ and $1$. As
mentioned already before, $H_{s}=\sum_{{\sigma}}n^{(\sigma)}$ satisfies this
property in equations (2.4) and (4.1), or at least for the region of phase
space between the two hyperplanes $\sum_{{\sigma}}n^{(\sigma)}=0$ and
$\sum_{{\sigma}}n^{(\sigma)}=K$ (recall that $K_{1}=\dots=K_{S}=K$ for these
equations). This is fine since the aformentioned region is the only
biologically realistic/sensible/meaningful region of phase space anyway, and
any solution of (4.1) beginning in that region will remain inside that region
for all time.

####  6 “Competitive Lotka-Volterra Equations”

There is at least one other similar system of differential equations intended
to model both the direct interactions corresponding to the system (3.1) and
external limitations due to finiteness of nutrient supply and the accumulation
of waste products, which is often called the “Competitive Lotka-Volterra
equations”. For the competitive Lotka-Volterra equations, using the general
framework of (5.1) one has

$G_{s}=r_{s}\,,\quad\quad\quad H_{s}=\sum_{{\sigma}=1}^{S}\alpha_{\sigma
s}n^{(\sigma)}\,.$ (6.1)

Apart from the issue that $K_{s}$ may have different values for different
strains (which can easily be rectified), a bigger issue with these equations,
and why they were not used for these simulations, is that there is no way to
guarantee that $0\leq H_{s}\leq 1$, at least not without restrictions on the
interaction coefficients which from a biological point of view would be
arbitrary. Moreover $H_{s}=\sum_{{\sigma}=1}^{S}\alpha_{\sigma s}n^{(\sigma)}$
does not correspond to any scientifically meaningful or experimentally
observable quantity, making the meaning of the restrictions imposed on the
growth of strain $s$ by the $(1-H_{s}/K_{s})$ factor difficult, if not
impossible, to give any scientifically meaningful interpretation. In contrast,
$H_{s}=\sum_{{\sigma}}n^{(\sigma)}$ is not only possible to measure
experimentally, but is probably easier to measure than any of the $n^{(s)}$