This means that$W_{1}$ and $W_{2}$ are in the same tree in $S$, or in other
words, they are both on the same side from $C_{S}$. But now this cycle is
contained in $F$ (since we only have $F,W_{1},W_{2}$) and since $W_{1}$ and
$W_{2}$ by Lemma 13 are now on the opposite sides of $F$ they are on the
opposite sides to the $C_{S}$, which is impossible since then removing $C_{S}$
leaves $W_{1}$ and $W_{2}$ in the different connectivity components which was
not the case in $S$.

###### Lemma 18

Assume that $S_{i}$ $i\in\\{1,2\\}$ connects to $F$ via a node $u$, $u\in
V(T)$ where $T$ is a tree from the cycle-tree decomposition of $S_{i}$ and
$S_{i}$ has a node of degree three. Then all the nodes from an extended trunk
core of $T$ are embedded monotonically in $\varphi^{\prime}$.

###### Proof

All the nodes from a trunk core of $T$ belong to a trunk core in $S$. This is
because $T$ is contained in some tree $T_{S}$ from a cycle-tree decomposition
of $S$ and thus a trunk core of $T$ is contained in a trunk core of $T_{S}$
since all the support nodes remain support nodes when extending a tree.

So we consider two extensions of $T$-s trunk core $ext_{1}$ and $ext_{2}$.
Let’s say $ext_{1}$ is the one which extends to $F$. Note that $ext_{2}$ was
an extension in $S$ and thus we already have that $trunkCore(T)\cup ext_{2}$
is embedded monotonically by $\varphi^{\prime}$.

The $ext_{1}$ was either a part of an extended trunk core of $T_{S}$ or an
exit-graph in $T_{S}$. This is because it is obviously couldn’t have been a
part of a cycle, since nodes on cycle remain on cycle when the new edge is
added. Neither could it have been a part of the inner simple-graph since then
the end-node of the $trunkCore(T)$ to which $ext_{1}$ is connected was an
inner node of the trunk core meaning that there was two edge-disjoint paths
from it to two support nodes. If those support nodes are in $T$ now the end-
node of $trunkCore(T)$ is an inner trunk core node of $T$ which is nonsense.
Otherwise it is not in $S_{i}$ meaning the path to it goes through $ext_{1}$
since it is the only path connecting $T$ and $F$. But then $ext_{1}$ belongs
to a trunk core in $S$. So $ext_{1}$ was either a part of an exit-graph or a
part of the $trunkCore(T_{S})$. In both cases it is embedded monotonically
with $trunkCore(T)\cup ext_{2}$.

So assume we have $S_{i}$ $i\in\\{1,2\\}$ which connects to $f\in V(F)$ via a
node $u$, $u\in V(T)$ where $T$ is a tree from the cycle-tree decomposition of
$S_{i}$ and $S_{i}$ has a node of degree three. Lemma 18 tells us that $T$-s
extended trunk core was embedded monotonically, say, increasingly starting
from $u$. In this case we embed $F$ the way that $f$ is embedded higher then
every other node from $F$, say, to $level(i)[1]$, and we embed $j$-th node of
an extended trunk core of $T$ to the $level(i+j)[1]$. All the other nodes from
$S_{i}$ we embed the same as they were embedded by $\varphi^{\prime}$
relatively to the nodes of the extended trunk core of $T$.

We now analyze if we obtained a conflict of nodes from $S_{i}$ and $F$ and if
$T$ is embedded respecting strategy 0.C.3.1.

Consider inner simple-graphs of $T$ in order they are connected to the
extended trunk core of $T$ going through the extended trunk core from $u$. We
state that all of them except possibly the first two were inner simple-graphs
in $S$. This is because for a foot of such simple-graph there is a support
node before it (one of the foots of first two simple-graphs) and a support
node or an end-node after it (because it is inner in $S_{+}$). So those
simple-graphs can not conflict with nodes of $F$ since they did not pass
through the levels of foots of first two simple-graphs. They also respect the
strategy 0.C.3.1.

So we only need to orient first two simple-graphs in the way they don’t
conflict with nodes of $F$ and they respect the embedding strategy. This can
be done, since the strategy can be applied to $T\cup\\{f\text{ and its
neighbours}\\}$.

Our last goal in analyzing an embedding of a component with a node of degree
three which starts with a tree is to show that we can’t face incompatibility.
If say, $S_{1}$ is starting with a tree $T$ with increasing order on its
extended trunk core in $S$ then the order on $S_{2}$ (if one exists) is
decreasing (meaning that $S_{2}$ has a decreasing order in $S$ on an extended
trunk core of a tree it starts with or a decreasing order in $S$ on its hands
if $S_{2}$ is just a line-graph). Let’s say $S_{1}$ and $S_{2}$ are connected
to $F$ with nodes $c_{1}\in V(S_{1})$ and $c_{2}\in V(S_{2})$ respectively.

First assume we have $S_{1}$ starting with a tree $T_{1}$ and $S_{2}$ starting
with a tree $T_{2}$. Both $S_{1}$ and $S_{2}$ have a node of degree three. For
$T_{i}$ take a node $u_{i}$ which is a foot of $T_{i}$ other then the one in
$F$ if such exists or the end of the extended trunk core other then the one
connected to $F$. Since $S_{i}$ has a node of degree three, one of those must
exist. A shortest path connecting $u_{1}$ and $u_{2}$ contain both extended
trunk cores of $T_{1}$ and $T_{2}$. Since no path in $\varphi^{\prime}(S)$ is
self-crossing the path $u_{1}-u_{2}$ must be monotone by Lemma 9 since no
nodes of the path can be embedded to the same level with $u_{1}$ and $u_{2}$
(the neighbour of $u_{i}$ is either a cycle node or an exit-graph node). Thus
paths $u_{1}-c_{1}$ and $c_{2}-u_{2}$ have the same order in
$\varphi^{\prime}(S)$ so the extended trunk cores of $T_{1}$ and $T_{2}$ which
are contained in $c_{1}-u_{1}$ and $c_{2}-u_{2}$ have opposite order.

Now consider the case when $S_{1}$ has a node of degree three and starts with
a tree $T$ and $S_{2}$ is just a line-graph. Let’s say that $S_{1}$ connects
to $f_{1}\in V(F)$ and $S_{2}$ connects to $f_{2}\in V(F)$. For $T$ take a
node $u_{1}$ which is a foot of $T$ other then the one in $F$ if such exists
or the end of the extended trunk core other then the one connected to $F$.
Since $S_{1}$ has a node of degree three, one of those must exist. And let’s
say we have an increasing order on the hands of $S_{2}$. Consider the top-most
node of a hand of $S_{2}$ in $\varphi^{\prime}(S)$, let’s call it $u_{2}$.
Note that $u_{2}$ is the top-most node among all $S$ and can share level only
with nodes from exit-graphs. Now consider the shortest path $u_{1}-u_{2}$. It
contains an extended trunk core of $T$. Our goal now is to proof that this
path is monotone, that would imply as in the previous case that $T$-s extended
trunk core and $S_{2}$-s hands have different order. To see that it is
monotone recall that $\varphi^{\prime}$ produces no self-crossing paths and
thus, if the path is not monotone, by Lemma 9 we either have $u_{1}$ sharing
level with some other node from path which is impossible since it is either a
cycle node or a trunk-core end-node. Or $u_{2}$ shares level with some other
node from path which is also impossible since $u_{2}$ is the top-most node
with only nodes from other exit-graphs hands possibly being on its level.

So we discussed what to do if $S_{i}$ connects to the $F$ with a node from
tree from its cycle-tree decomposition. The last case is when it connects to
$F$ with a node of a cycle from its cycle-tree decomposition.

So assume $S_{1}$ connects to a node $f_{1}\in V(F)$ with a cycle $C$-s node,
say $u_{1}$. And let’s assume was the top-most node in $C$ the case when it is
the bottom-most is totally symmetric. We embed $F$ the way $f_{1}$ becomes a
bottom-most node we embed $C$ the way $u_{1}$ is the top most node and it is
under $f_{1}$. We embed the rest of $S_{1}$ relatively to $C$ as it was
embedded by $\varphi^{\prime}$.

Nothing changed in $S_{1}$, so the invariants maintain for it. Therefor our
only goal is to show that we don’t face incompatibility with $S_{2}$.

If $S_{2}$ starts with a cycle $C_{2}$ which connects to $F$ via a node
$u_{2}$ then we conclude that $u_{2}$ was the bottom-most node of $C_{2}$
since there is a path in which connects $u_{1}$ and $u_{2}$ without passing
through other nodes of $C_{1}$ and $C_{2}$.

If $S_{2}$ starts with a tree we act similarly as we did in previous cases
take such node $u_{2}$ that the path $u_{1}-u_{2}$ contains tree-s trunk
core/extended trunk core/hand of an exit graph and we chow that by Lemma 9
path $u_{1}-u_{2}$ should be monotone, since no nodes of it can be embedded to
the same level as $u_{2}$ for the same reasons as before and neither can they
be embedded to the same level with $u_{1}$ since there is a cycle node
embedded to the same level as $u_{1}$. So if, say, $u_{1}$ was the top-most
node of $C$ in $\varphi^{\prime}(S)$ then the path is increasing and thus the
trunk core/extended trunk core/hand of an exit graph is also increasing in
$\varphi^{\prime}(S)$ which is consistent to the fact that it connects to the
top-most node of $F$.

All the actions described above assume that there was a cycle in $S$ already.
If there wasn’t we act as described below.

The new edge $(u,v)$ is in one connectivity component so there is a maximal
cycle containing $u$ and $v$. Let’s take a frame $F$ of that cycle. There are
possibly two connectivity components left when removing $F$ from $S_{+}$,
denote them $S_{1}$ and $S_{2}$. Let’s say that $S_{1}$ connects to $f_{1}\in
V(F)$ and $S_{2}$ connects to $f_{2}\in V(F)$. Moreover we know that $S_{1}$
and $S_{2}$ are trees.

We embed $F$ the way that $f_{1}$ is the top-most node and $f_{2}$ is the
bottom-most node. We then embed $S_{1}$ and $S_{2}$ the way they match
strategy 0.C.3.1 orienting the trunk not to conflict with cycle nodes.

###  0.C.5 Cost of the algorithm

We now want to analyze the cost of actions performed when serving a new edge
within one component. Note that since the resulting embedding is quasi-correct
the cost of serving the request is $O(1)$.

To make an amortized analysis we introduce the concept of scenarios. The
scenario is a reason for node to move in the embedding and thus change its
number. Each scenario has two main properties: the number of times it can
happen to a certain node (denoted with $SC_{N}$) and a cost payed for that
node movement in this scenario (denoted with $SC_{C}$). So the total cost
payed for node movements in this terms is bounded with

$\displaystyle 2n\cdot\sum\limits_{SC\in\mathrm{SCENARIOS}}SC_{N}\cdot SC_{C}$
(74)

Where the first factor $2n$ arises due to the fact that $SC_{N}$ and $SC_{C}$
are defined for one particular node, but we want the total cost.

We propose that we only need to focus on the relative order changes.

###### Lemma 19

If we have two enumerations $h_{1}$ and $h_{2}$ of graph $G$ then the cost of
obtaining $h_{2}$ from $h_{1}$ via swaps is no more than

$\displaystyle|\\{(u,v)\mid u,v\in V(G),\ h_{1}(u)<h_{1}(v)\wedge
h_{2}(u)>h_{2}(v)\\}|$ (75)

###### Proof

We can order nodes of $G$ by $h_{2}$. $h_{1}$ can then be viewed as a
permutation so the statement of the Lemma can be reformulated as ”the swap
distance between a permutation $p$ and an identity permutation is less or
equal the number of inversions in $p$”.

We proof this by induction. The induction would be among the number of
elements in permutations and among the number of inversions in permutations.

The induction base is 0 inversions for each number of elements which is
trivial. We also notice that if there is just one element in the permutation
then this permutation can’t have inversions.

We now assume that our permutation $p$ has $n$ elements and $k$ inversions,
with $k>0$ and $n>1$.

If now $p[1]=1$ then the distance between $p$ and $identity_{n}$ is the
distance between $p^{\prime}$ and $identity_{n-1}$ where
$p^{\prime}[i]=p[i+1]-1$. And since $p^{\prime}$ has the same number of
inversions as $p$ then by the inductive assumption it is less or equal to $k$
which is what we desire.

If $p[1]=i$, $i\neq 1$ then we first spend $i-1$ swaps to bring $i$ to the
position 1 reducing the number of inversions by $i-1$. And then apply the same
idea with $p^{\prime}$ obtaining that the distance from $p^{\prime}$ to an
$identity_{n-1}$ is $k-(i-1)$ and thus we provided the series of swaps to
obtain an $identity_{n}$ from $p$ with $\leq k$.

###### Lemma 20

Suppose $S$ is a connectivity component with a cycle embedded into
$Ladder_{n}$ via $\varphi^{\prime}$ which respects invariants 0.C.4. Suppose
we have a new edge in the connectivity component $S$. We denote $S$ with a new
edge by $S_{+}$. Let’s call the frame of a maximal cycle containing the ends
of the new edge $F$. The connectivity components left when removing $F$ from
$S_{+}$ are $S_{1}$ and $S_{2}$. Suppose that our algorithm embeds $S_{1}$
above $F$.

  1. 1.

If there is a cycle in $F$ that was present in $S$ then all the nodes from
$S_{1}$ were above that cycle in $\varphi^{\prime}(S)$.

  2. 2.

If there is a cycle in $F$ that was present in $S$ then there is a node of
cycle that is top-most for both new and old embeddings.

  3. 3.

For each node $u\in V(S_{1})$ and for each node $v\in V(S_{2})$
$level\langle\varphi^{\prime}(u)\rangle>level\langle\varphi^{\prime}(v)\rangle$
except possibly the first two inner simple-graph nodes of $T_{i}$ if $S_{i}$
connects to $F$ with a tree $T_{i}$ from a cycle-tree decomposition of
$S_{i}$.

###### Proof

Assume $S_{1}$ connects to $F$ via edge $(f_{1},c_{1}),\ f_{1}\in
V(F),c_{1}\in V(S_{1})$ and $S_{2}$ connects to $F$ via edge $(f_{2},c_{2}),\
f_{2}\in V(F),c_{2}\in V(S_{2})$

  1. 1.

We want to prove the following fact: consider component $A$ is connected to
cycle $C$ with edge $(a,c)$, $a\in V(A)$ $c\in V(C)$ and it is embedded above
$C$ by $\varphi_{1}$ and below $C$ by $\varphi_{2}$. Then for each path in $A$
starting from $a$ which is monotone for both $\varphi_{1}$ and $\varphi_{2}$
it has changed its orientation i.e. if it was increasing it is now decreasing
and vice versa. To see this note that $a$ was a top-most node and became the
bottom-most node of the path or vice versa.

For each type of $S_{1}$ our new edge processing strategy maintained an
orientation of some monotone path in $S_{1}$ which can be extended remaining
monotone to the node connected to the cycle. Thus by the fact above it must
remain on the same side of the cycle.

  2. 2.

Denote the cycle in statement by $C$,. Denote by $A$ the component that was
above $C$ in $\varphi^{\prime}(S)$ which contains $S_{1}$. Say it is connected
to $C$ via edge $(a,c)$ $a\in V(A)$ $c\in V(C)$. Then by item 1 node $c$ is
top-most in both embeddings of $S$ and $S_{+}$ since there is a monotonically
increasing path starting from $a$ which does not pass through nodes of $C$.

  3. 3.

If $S_{1}$ and $S_{2}$ are both line-graphs from the proof of compatibility
for line-graphs we know that the must be in the different trees in a cycle-
tree decomposition of $S$ meaning they are separated by cycle and thus their
nodes don’t share levels. Moreover nodes form $S_{1}$ were in the top-most
tree and nodes from $S_{2}$ were in the bottom-most tree, so indeed every node
from $S_{1}$ was embedded higher than every node of $S_{2}$.

For all the other cases on $S_{1}$ and $S_{2}$ in the proof of their
compatibility we build a monotone path which passes through
$c_{2},f_{2},f_{1},c_{1}$. This path is monotonically increasing levels in
$\varphi^{\prime}(S)$ if $S_{1}$ is embedded above $F$ by our algorithm. So
$level\langle\varphi^{\prime}(c_{2})\rangle<level\langle\varphi^{\prime}(c_{1})\rangle$
so our goal now is to analyze what nodes from $S_{1}$ can go under
$level\langle\varphi^{\prime}(c_{1})\rangle$ (the analysis for $S_{2}$ is
symmetric).

If $S_{1}$ connects to $F$ with a cycle or $S_{1}$ is a line-graph no nodes
can go under $c_{1}$.

To analyze the last case on $S_{1}$ we need the following fact: if $S_{2}$
exists then $V(F)$ contains a node of degree three in $S$. This is because
$V(F)$ contains two nodes of degree three in $S_{+}$ namely the foots of
opposite (non adjacent) whiskers and those nodes are not adjacent since the
cycle is of length at least 6. So one of them must have been of degree three
before the new edge.

So assume now $S_{1}$ connects to $F$ with a tree and contains a node of
degree three. From the analysis of compatibility for such $S_{1}$ we know that
$c_{1}$ is either an extended trunk core node or an exit-graph node in $S$. If
it is an exit-graph node, then $S_{2}$ does not exists since if it does there
is a node of degree three in $V(F)$ in $S$ and thus there are two disjoint
paths from $c_{1}$ to nodes of degree three which can’t be for an exit-graph
node.

If now $c_{1}$ is in an extended trunk core node of a tree $T$. If $F$
contains a cycle that was present in $S$ then nodes from $S_{1}$ and $S_{2}$
were separated by this cycle then by item 1 all the nodes from $S_{1}$ were
above that cycle and all the nodes from $S_{2}$ were bellow so the proposal
holds. All the nodes from an extended trunk core of $T$ were above $c_{1}$ in
$S$ so the only possible nodes are the nodes to go below $c_{1}$ are nodes
from inner simple-graphs of $T$. And the inner simple-graphs starting from the
third one can’t cross the first two graphs heads so they can’t cross $c_{1}$
as well.

We are now ready to analyze the cost payed by each node when a new edge in the
connectivity component appears.

######  Scenario 1 (Inner simple-graph reorienting)

The node falls into this scenario if it is a part of an inner simple-graph
which is being reoriented.

###### Lemma 21

The “Inner simple-graph reorienting” scenario costs $O(n)$ for a node and
happens only once for a given node.

###### Proof

Node can’t pay more than $2n$ so $O(n)$ bound is trivial.

The inner simple-graph has only two possible orientations. We change its
orientation only if the current one violates the invariants 0.C.4 thus we will
never get back to it.

######  Scenario 2 (First time on a cycle)

The node falls into this scenario if it was not on a cycle before the new edge
and after the new edge it is.

###### Lemma 22

The “First time on a cycle” scenario happens at most once for each node and
costs $O(n)$.

###### Proof

Trivial.

######  Scenario 3 (Cycle in the frame)

The node falls in this scenario if it is in the cycle which is a part of $F$
and is present in $S$.

###### Lemma 23

The “Cycle in the frame” scenario happens $O(n)$ times for each node and costs
$O(1)$.

###### Proof

Since we have only $O(n)$ edges the $O(n)$ upper bound is trivial.

If the cycle is embedded respecting invariants 0.C.4 with a node specified to
be the top most (which is the case due to the lemma 20) then we have only two
four possibilities for a cycle to be embedded and for each to of them one can
be transformed to another making each node changing the relative order only
with $O(1)$ nodes from cycle which by Lemma 19 gives us $O(1)$ cost per node.

Note also that by Lemma 20 nodes from cycle do not change relative order with
nodes from $S_{1}$ or $S_{2}$ and thus the cost of their inner relative change
is the only cost they need to pay.

So the nodes of $F$ fall into either First time on a cycle scenario or to the
cycle in the frame scenario.

As for the $S_{i}$ nodes we need to consider 2 cases. The nodes are either a
part of first two inner simple-graphs when $S_{i}$ starts from a tree or not.

If yes, and those node change their relative order to the nodes of $S_{i}$
this means that the reorientation of simple-graphs had been performed thus
they fall into Inner simple-graph reorienting scenario. If they did not change
relative order to $S_{i}$ this means they didn’t change the order with
$S_{j}$, $j\in\\{1,2\\}\setminus\\{i\\}$ neither with $F$ so they pay nothing.

As for the nodes from $S_{i}$ that are not the part of first two inner simple-
graphs by the Lemma 20 they didn’t change the relative order with $S_{j}$, by
the embedding strategy they didn’t change the relative order with the nodes
from $S_{i}$ (// consider mirroring? //) accept possibly first two inner-
simple graphs and also by the Lemma 20 they didn’t change the relative order
with the cycle contained in $F$. As for the nodes of $F$ which were not on the
cycle we say that they pay for all the relative order changes.

####  0.C.5.1 New edge between two components

We now define and analyse the behaviour of the algorithm when the edge between
two connectivity components is revealed. The strategy would be to bring the
larger component towards the smaller one.

######  Scenario 4 (Connectivity component movement)

. The node falls in this scenario if its component is a smaller of two between
which the new edge is revealed.

###### Lemma 24

The “Connectivity component movement” scenario for a node happens $O(\log n)$
times and cost $O(n)$.

###### Proof

The size of the component is at least doubled.

We now dive into the case analysis.

We first want to distinguish to cases: either the bigger component has a tree
with a non-empty trunk core or not.

If not that means that there are at most two nodes of degree three. If the new
edge increases the number of degree three nodes from 0 to one, from 1 to 2 or
from 2 to three we say that it is an individual scenario and we can allow the
total reconfiguration according to the 0.C.3.1.

######  Scenario 5 (New degree three node.)

The node falls into this scenario if the new edge increases the number of the
nodes of degree three in the component from 0 to 1, from 1 to 2 or from 2 to
3.

###### Lemma 25

The “New degree three node” scenario can happen $O(1)$ times and costs $O(n)$.

###### Proof

Trivial.

We now assume that there is a tree in the bigger component with a non-empty
trunk core or a cycle with an inner edge. The smaller component can then
connect to:

  1. 1.

The inner node of the trunk core.

  2. 2.

The inner simple-graph node.

  3. 3.

The cycle node.

  4. 4.

The exit-graph node.

In the following analysis the new scenario appear

######  Scenario 6 (No more an exit-graph.)

The node falls into this scenario if it is no longer a part of an exit-graph.

###### Lemma 26

The “No more an exit-graph” scenario happens at most once and costs $O(n)$.

###### Proof

The closest node of degree three to the exit-graph node has only one path to
another degree three node.

Let us discuss all the possible cases.

  1. 1.

If the smaller connectivity component connects to the inner trunk core node
then by Lemma 6 it must be a line-graphs and there for to maintain the quasi-
correctness of the embedding we only to choose its orientation and reorient
its trunk core neighbours. The scenarios engaged here are the connectivity
component movement and inner simple-graph reorienting.

  2. 2.

For the inner simple-graph node the analysis is basically the same as in the
previous case.

  3. 3.

Cases:

     * •

Only cycle

     * •

Cycle and a line-graph

     * •

Cycle and a tree with a degree three node

  4. 4.

Cases:

     * •

Smaller component does not make new nodes of degree three

     * •

It does. Then we reorient the exit-graphs as they are no longer exit-graphs.
This is the no more an exit graph scenario.

##  Appendix 0.D Embedding a general demand graph on a line graph

Here we propose an online algorithm for a general demand graph $G$ assuming
having an oracle algorithm for solving the Bandwidth problem. Given a long
enough request sequence, namely $|\sigma|=\Omega(|E(G)|\cdot|V(G)|^{2})$ the
proposed algorithm has an $O(\lambda\cdot\mathrm{Bandwidth}(G))$ competitive
ratio compared with an optimal offline algorithm. But there is more to it. We
point out that this algorithm is robust in a sense that its maximal cost for
serving a request exceeds the maximal cost of processing the request
(reconfigure + serve) of any online algorithm by at most the factor of
$\lambda$. Moreover, this algorithm pays at most $O(|E(G)|\cdot|V(G)|^{2})$
for reconfiguration in total.

###### Theorem 3.3

Suppose we are given a graph $G$ and an algorithm $B$, that for any subgraph
$S$ of $G$ outputs an embedding $c\in C_{S\rightarrow L_{n}}$ with the
bandwidth less than or equal to $\lambda\cdot\mathrm{Bandwidth}(G)$ for some
$\lambda$. Then, for any sequence of requests $\sigma$ with demand graph $G$
there is an algorithm that serves $\sigma$ with total cost
$O(|E(G)|\cdot|V(G)|^{2}+\lambda\cdot\mathrm{Bandwidth}(G)\cdot|\sigma|)$. If
the number of requests is $\Omega(|E(G)|\cdot|V(G)|^{2})$ each request has
$O(\lambda\cdot\mathrm{Bandwidth}(G))$ amortized cost.

###### Proof

Assume we have processed $i$ requests so far. We get a demand graph built on
edges $E_{i}=\\{\sigma_{0},\ldots,\sigma_{i}\\}$. It induces a subgraph
$S_{i}$ of $G$. We want to maintain the invariant that each $S_{i}$ is
embedded via $c_{i}\in C_{S_{i}\rightarrow L}$ such that bandwidth of $h$ is
no greater than $\lambda\cdot\mathrm{Bandwidth}(G)$. Suppose now the embedding
$c_{i-1}$ of $S_{i-1}$ respects the invariant and we get a new request
$\sigma_{i}$. $\sigma_{i}$ is an edge in $G$, say $(u,v)$. We have two
possibilities: either $\sigma_{i}$ is already in $S_{i-1}$ or not. If
$(u,v)\in E(S_{i-1})$ then $S_{i-1}=S_{i}$ and since $c_{i-1}$ respects the
invariant we know that
$|c_{i-1}(u)-c_{i-1}(v)|\leq\lambda\cdot\mathrm{Bandwidth}(G)$ and hence we
take $c_{i}=c_{i-1}$. If on the opposite $(u,v)\notin E(S_{i-1})$ we take
$c_{i}=B(S_{i})$, as an embedding of $S_{i}$ to the line, and reconfigure the
network from scratch.

Now, we analyse the cost. We perform adjustments only for a new revealed edge
and, thus, there would be no more than $|E(G)|$ reconfigurations. For each
reconfiguration we make at most $|V(G)^{2}|$ migrations, meaning that the
total cost of reconfigurations is at most $|E(G)|\cdot|V(G)|^{2}$. Since we
serve the request after performing a reconfiguration and each configuration
has a bandwidth of at most $\lambda\cdot\mathrm{Bandwidth}(G)$ we state that
we pay no more than $\lambda\cdot\mathrm{Bandwidth}(G)\cdot|\sigma|$ to serve
all the requests.

We now explain how to construct an expensive request sequence, when given an
online algorithm $ON$ to obtain a $\mathrm{Bandwidth}(G)$ request processing
cost lower bound.

###### Lemma 3

Given a demand graph $G$. For each online algorithm $ON$ there is a request
sequence $\sigma_{ON}$ such that $ON$ serves each request from $\sigma_{ON}$
for a cost of at least $\mathrm{Bandwidth}(G)$.

###### Proof

Consider the resulting numeration $\varphi$ of $V(G)$ done by $ON$ after
serving $r\geq 0$ requests. By the definition of bandwidth, there are such
$u,v\in V(G)$ that $|\varphi(u)-\varphi(v)|\geq\mathrm{Bandwidth}(G)$. So, we
let the next request $\sigma_{ON}[r+1]$ be $(u,v)$ making $ON$ pay at least
$\mathrm{Bandwidth}(G)$ for that request.


Sea (Fci) | $0.94\scriptstyle\pm 0.1$ | $\textbf{0.99}\scriptstyle\pm 0.0$ | $0.93\scriptstyle\pm 0.0$ | $\textbf{0.98}\scriptstyle\pm 0.0$ | $\textbf{0.93}\scriptstyle\pm 0.1$ | $0.98\scriptstyle\pm 0.0$ | $0.81\scriptstyle\pm 0.1$ | $0.97\scriptstyle\pm 0.0$ | $\textbf{0.76}\scriptstyle\pm 0.1$ | $\textbf{0.91}\scriptstyle\pm 0.1$
Sea (Gies) | $\textbf{0.95}\scriptstyle\pm 0.0$ | $\textbf{0.99}\scriptstyle\pm 0.0$ | $\textbf{0.94}\scriptstyle\pm 0.0$ | $\textbf{0.98}\scriptstyle\pm 0.0$ | $0.92\scriptstyle\pm 0.0$ | $\textbf{0.98}\scriptstyle\pm 0.0$ | $\textbf{0.85}\scriptstyle\pm 0.1$ | $\textbf{0.98}\scriptstyle\pm 0.0$ | $0.74\scriptstyle\pm 0.1$ | $0.90\scriptstyle\pm 0.1$
10 | 40 | Dcdi-G | $0.70\scriptstyle\pm 0.0$ | $0.85\scriptstyle\pm 0.0$ | $0.74\scriptstyle\pm 0.1$ | $0.85\scriptstyle\pm 0.1$ | $\textbf{0.88}\scriptstyle\pm 0.0$ | $\textbf{0.91}\scriptstyle\pm 0.0$ | $0.56\scriptstyle\pm 0.1$ | $0.66\scriptstyle\pm 0.1$ | $0.53\scriptstyle\pm 0.1$ | $0.64\scriptstyle\pm 0.1$
Dcdi-Dsf | $0.74\scriptstyle\pm 0.1$ | $0.87\scriptstyle\pm 0.1$ | $0.73\scriptstyle\pm 0.1$ | $0.84\scriptstyle\pm 0.0$ | $0.71\scriptstyle\pm 0.1$ | $0.90\scriptstyle\pm 0.0$ | $0.56\scriptstyle\pm 0.1$ | $0.69\scriptstyle\pm 0.1$ | $0.51\scriptstyle\pm 0.0$ | $0.63\scriptstyle\pm 0.1$
Dcd-Fg | $0.37\scriptstyle\pm 0.0$ | $0.58\scriptstyle\pm 0.0$ | $0.45\scriptstyle\pm 0.1$ | $0.61\scriptstyle\pm 0.1$ | $0.45\scriptstyle\pm 0.2$ | $0.58\scriptstyle\pm 0.1$ | $0.49\scriptstyle\pm 0.1$ | $0.63\scriptstyle\pm 0.1$ | $0.63\scriptstyle\pm 0.1$ | $0.73\scriptstyle\pm 0.1$
DiffAn | $0.29\scriptstyle\pm 0.1$ | $0.50\scriptstyle\pm 0.1$ | $0.25\scriptstyle\pm 0.0$ | $0.38\scriptstyle\pm 0.1$ | $0.28\scriptstyle\pm 0.0$ | $0.46\scriptstyle\pm 0.1$ | $0.31\scriptstyle\pm 0.1$ | $0.53\scriptstyle\pm 0.1$ | $0.27\scriptstyle\pm 0.0$ | $0.44\scriptstyle\pm 0.1$
Deci | $0.30\scriptstyle\pm 0.0$ | $0.51\scriptstyle\pm 0.1$ | $0.41\scriptstyle\pm 0.0$ | $0.65\scriptstyle\pm 0.1$ | $0.33\scriptstyle\pm 0.0$ | $0.51\scriptstyle\pm 0.0$ | $0.38\scriptstyle\pm 0.1$ | $0.60\scriptstyle\pm 0.1$ | $0.59\scriptstyle\pm 0.1$ | $0.77\scriptstyle\pm 0.1$
InvCov | $0.36\scriptstyle\pm 0.0$ | $0.48\scriptstyle\pm 0.1$ | $0.34\scriptstyle\pm 0.0$ | $0.49\scriptstyle\pm 0.1$ | $0.37\scriptstyle\pm 0.0$ | $0.48\scriptstyle\pm 0.0$ | $0.39\scriptstyle\pm 0.0$ | $0.54\scriptstyle\pm 0.1$ | $0.26\scriptstyle\pm 0.0$ | $0.34\scriptstyle\pm 0.0$
Fci-Avg | $0.47\scriptstyle\pm 0.1$ | $0.64\scriptstyle\pm 0.0$ | $0.41\scriptstyle\pm 0.1$ | $0.60\scriptstyle\pm 0.0$ | $0.40\scriptstyle\pm 0.0$ | $0.58\scriptstyle\pm 0.0$ | $0.48\scriptstyle\pm 0.1$ | $0.64\scriptstyle\pm 0.1$ | $0.41\scriptstyle\pm 0.1$ | $0.59\scriptstyle\pm 0.1$
Gies-Avg | $0.43\scriptstyle\pm 0.1$ | $0.68\scriptstyle\pm 0.1$ | $0.43\scriptstyle\pm 0.1$ | $0.63\scriptstyle\pm 0.1$ | $0.44\scriptstyle\pm 0.1$ | $0.61\scriptstyle\pm 0.1$ | $0.49\scriptstyle\pm 0.1$ | $0.69\scriptstyle\pm 0.1$ | $0.59\scriptstyle\pm 0.1$ | $0.71\scriptstyle\pm 0.1$
Sea (Fci) | $\textbf{0.93}\scriptstyle\pm 0.0$ | $0.96\scriptstyle\pm 0.0$ | $0.84\scriptstyle\pm 0.0$ | $0.92\scriptstyle\pm 0.0$ | $0.81\scriptstyle\pm 0.0$ | $0.90\scriptstyle\pm 0.0$ | $\textbf{0.81}\scriptstyle\pm 0.0$ | $\textbf{0.89}\scriptstyle\pm 0.0$ | $0.73\scriptstyle\pm 0.1$ | $0.84\scriptstyle\pm 0.0$
Sea (Gies) | $0.92\scriptstyle\pm 0.0$ | $\textbf{0.96}\scriptstyle\pm 0.0$ | $\textbf{0.84}\scriptstyle\pm 0.1$ | $\textbf{0.93}\scriptstyle\pm 0.0$ | $0.83\scriptstyle\pm 0.0$ | $0.90\scriptstyle\pm 0.0$ | $0.79\scriptstyle\pm 0.0$ | $0.88\scriptstyle\pm 0.0$ | $\textbf{0.78}\scriptstyle\pm 0.1$ | $\textbf{0.87}\scriptstyle\pm 0.0$
20 | 20 | Dcdi-G | $0.41\scriptstyle\pm 0.0$ | $0.95\scriptstyle\pm 0.0$ | $0.50\scriptstyle\pm 0.1$ | $0.94\scriptstyle\pm 0.0$ | $0.69\scriptstyle\pm 0.1$ | $0.96\scriptstyle\pm 0.0$ | $0.37\scriptstyle\pm 0.0$ | $0.83\scriptstyle\pm 0.1$ | $0.37\scriptstyle\pm 0.1$ | $0.77\scriptstyle\pm 0.1$
Dcdi-Dsf | $0.48\scriptstyle\pm 0.0$ | $0.95\scriptstyle\pm 0.0$ | $0.55\scriptstyle\pm 0.1$ | $0.93\scriptstyle\pm 0.0$ | $0.33\scriptstyle\pm 0.1$ | $0.90\scriptstyle\pm 0.0$ | $0.37\scriptstyle\pm 0.1$ | $0.79\scriptstyle\pm 0.1$ | $0.35\scriptstyle\pm 0.1$ | $0.82\scriptstyle\pm 0.1$
Dcd-Fg | $0.51\scriptstyle\pm 0.1$ | $0.87\scriptstyle\pm 0.1$ | $0.39\scriptstyle\pm 0.1$ | $0.83\scriptstyle\pm 0.1$ | $0.48\scriptstyle\pm 0.1$ | $0.84\scriptstyle\pm 0.0$ | $0.56\scriptstyle\pm 0.1$ | $0.84\scriptstyle\pm 0.1$ | $0.50\scriptstyle\pm 0.1$ | $0.84\scriptstyle\pm 0.1$
DiffAn | $0.27\scriptstyle\pm 0.1$ | $0.80\scriptstyle\pm 0.0$ | $0.11\scriptstyle\pm 0.0$ | $0.65\scriptstyle\pm 0.1$ | $0.11\scriptstyle\pm 0.0$ | $0.66\scriptstyle\pm 0.1$ | $0.26\scriptstyle\pm 0.2$ | $0.77\scriptstyle\pm 0.1$ | $0.12\scriptstyle\pm 0.0$ | $0.69\scriptstyle\pm 0.1$
Deci | $0.13\scriptstyle\pm 0.1$ | $0.69\scriptstyle\pm 0.1$ | $0.15\scriptstyle\pm 0.1$ | $0.71\scriptstyle\pm 0.1$ | $0.15\scriptstyle\pm 0.0$ | $0.73\scriptstyle\pm 0.0$ | $0.15\scriptstyle\pm 0.1$ | $0.71\scriptstyle\pm 0.1$ | $0.25\scriptstyle\pm 0.1$ | $0.79\scriptstyle\pm 0.1$
InvCov | $0.30\scriptstyle\pm 0.0$ | $0.57\scriptstyle\pm 0.1$ | $0.26\scriptstyle\pm 0.1$ | $0.53\scriptstyle\pm 0.1$ | $0.21\scriptstyle\pm 0.0$ | $0.53\scriptstyle\pm 0.0$ | $0.24\scriptstyle\pm 0.1$ | $0.49\scriptstyle\pm 0.1$ | $0.03\scriptstyle\pm 0.0$ | $0.10\scriptstyle\pm 0.1$
Fci-Avg | $0.63\scriptstyle\pm 0.1$ | $0.84\scriptstyle\pm 0.1$ | $0.44\scriptstyle\pm 0.1$ | $0.78\scriptstyle\pm 0.0$ | $0.43\scriptstyle\pm 0.1$ | $0.79\scriptstyle\pm 0.0$ | $0.60\scriptstyle\pm 0.1$ | $0.86\scriptstyle\pm 0.1$ | $0.47\scriptstyle\pm 0.1$ | $0.78\scriptstyle\pm 0.1$
Gies-Avg | $0.82\scriptstyle\pm 0.1$ | $0.99\scriptstyle\pm 0.0$ | $0.58\scriptstyle\pm 0.1$ | $0.95\scriptstyle\pm 0.0$ | $0.57\scriptstyle\pm 0.1$ | $0.96\scriptstyle\pm 0.0$ | $0.75\scriptstyle\pm 0.1$ | $0.98\scriptstyle\pm 0.0$ | $0.61\scriptstyle\pm 0.1$ | $0.90\scriptstyle\pm 0.0$
Sea (Fci) | $\textbf{0.95}\scriptstyle\pm 0.0$ | $\textbf{1.00}\scriptstyle\pm 0.0$ | $0.91\scriptstyle\pm 0.0$ | $\textbf{0.98}\scriptstyle\pm 0.0$ | $0.87\scriptstyle\pm 0.1$ | $\textbf{0.98}\scriptstyle\pm 0.0$ | $\textbf{0.84}\scriptstyle\pm 0.1$ | $\textbf{0.98}\scriptstyle\pm 0.0$ | $0.70\scriptstyle\pm 0.1$ | $\textbf{0.92}\scriptstyle\pm 0.1$
Sea (Gies) | $0.93\scriptstyle\pm 0.0$ | $1.00\scriptstyle\pm 0.0$ | $\textbf{0.91}\scriptstyle\pm 0.1$ | $0.98\scriptstyle\pm 0.0$ | $\textbf{0.88}\scriptstyle\pm 0.1$ | $0.98\scriptstyle\pm 0.0$ | $0.82\scriptstyle\pm 0.1$ | $0.98\scriptstyle\pm 0.0$ | $\textbf{0.70}\scriptstyle\pm 0.1$ | $0.91\scriptstyle\pm 0.1$
20 | 80 | Dcdi-G | $0.62\scriptstyle\pm 0.1$ | $0.88\scriptstyle\pm 0.0$ | $0.61\scriptstyle\pm 0.1$ | $\textbf{0.89}\scriptstyle\pm 0.0$ | $\textbf{0.76}\scriptstyle\pm 0.1$ | $\textbf{0.94}\scriptstyle\pm 0.0$ | $0.44\scriptstyle\pm 0.1$ | $0.76\scriptstyle\pm 0.0$ | $0.36\scriptstyle\pm 0.0$ | $0.60\scriptstyle\pm 0.0$
Dcdi-Dsf | $0.58\scriptstyle\pm 0.0$ | $0.87\scriptstyle\pm 0.0$ | $0.55\scriptstyle\pm 0.1$ | $0.86\scriptstyle\pm 0.0$ | $0.58\scriptstyle\pm 0.0$ | $0.92\scriptstyle\pm 0.0$ | $0.43\scriptstyle\pm 0.0$ | $0.78\scriptstyle\pm 0.0$ | $0.35\scriptstyle\pm 0.0$ | $0.66\scriptstyle\pm 0.1$
Dcd-Fg | $0.38\scriptstyle\pm 0.1$ | $0.70\scriptstyle\pm 0.1$ | $0.30\scriptstyle\pm 0.0$ | $0.69\scriptstyle\pm 0.0$ | $0.48\scriptstyle\pm 0.1$ | $0.80\scriptstyle\pm 0.1$ | $0.48\scriptstyle\pm 0.1$ | $0.75\scriptstyle\pm 0.0$ | $0.53\scriptstyle\pm 0.1$ | $0.73\scriptstyle\pm 0.1$
DiffAn | $0.18\scriptstyle\pm 0.0$ | $0.55\scriptstyle\pm 0.1$ | $0.15\scriptstyle\pm 0.0$ | $0.44\scriptstyle\pm 0.1$ | $0.16\scriptstyle\pm 0.0$ | $0.53\scriptstyle\pm 0.1$ | $0.19\scriptstyle\pm 0.0$ | $0.56\scriptstyle\pm 0.1$ | $0.15\scriptstyle\pm 0.0$ | $0.38\scriptstyle\pm 0.0$
Deci | $0.21\scriptstyle\pm 0.0$ | $0.58\scriptstyle\pm 0.0$ | $0.24\scriptstyle\pm 0.0$ | $0.64\scriptstyle\pm 0.0$ | $0.26\scriptstyle\pm 0.1$ | $0.66\scriptstyle\pm 0.1$ | $0.30\scriptstyle\pm 0.0$ | $0.68\scriptstyle\pm 0.0$ | $0.41\scriptstyle\pm 0.0$ | $0.75\scriptstyle\pm 0.0$
InvCov | $0.27\scriptstyle\pm 0.0$ | $0.52\scriptstyle\pm 0.0$ | $0.22\scriptstyle\pm 0.0$ | $0.51\scriptstyle\pm 0.0$ | $0.25\scriptstyle\pm 0.0$ | $0.54\scriptstyle\pm 0.0$ | $0.27\scriptstyle\pm 0.0$ | $0.51\scriptstyle\pm 0.1$ | $0.12\scriptstyle\pm 0.0$ | $0.30\scriptstyle\pm 0.0$
Fci-Avg | $0.31\scriptstyle\pm 0.0$ | $0.63\scriptstyle\pm 0.0$ | $0.30\scriptstyle\pm 0.0$ | $0.62\scriptstyle\pm 0.0$ | $0.30\scriptstyle\pm 0.1$ | $0.62\scriptstyle\pm 0.0$ | $0.41\scriptstyle\pm 0.1$ | $0.68\scriptstyle\pm 0.0$ | $0.32\scriptstyle\pm 0.1$ | $0.62\scriptstyle\pm 0.0$
Gies-Avg | $0.51\scriptstyle\pm 0.0$ | $0.87\scriptstyle\pm 0.0$ | $0.43\scriptstyle\pm 0.1$ | $0.78\scriptstyle\pm 0.0$ | $0.47\scriptstyle\pm 0.0$ | $0.81\scriptstyle\pm 0.0$ | $0.52\scriptstyle\pm 0.1$ | $0.82\scriptstyle\pm 0.0$ | $0.47\scriptstyle\pm 0.0$ | $0.73\scriptstyle\pm 0.0$
Sea (Fci) | $0.92\scriptstyle\pm 0.0$ | $\textbf{0.98}\scriptstyle\pm 0.0$ | $\textbf{0.64}\scriptstyle\pm 0.1$ | $0.89\scriptstyle\pm 0.0$ | $0.71\scriptstyle\pm 0.1$ | $0.90\scriptstyle\pm 0.0$ | $0.73\scriptstyle\pm 0.1$ | $0.90\scriptstyle\pm 0.0$ | $0.59\scriptstyle\pm 0.1$ | $0.81\scriptstyle\pm 0.0$
Sea (Gies) | $\textbf{0.92}\scriptstyle\pm 0.0$ | $\textbf{0.98}\scriptstyle\pm 0.0$ | $0.63\scriptstyle\pm 0.1$ | $0.89\scriptstyle\pm 0.0$ | $0.73\scriptstyle\pm 0.1$ | $0.91\scriptstyle\pm 0.0$ | $\textbf{0.77}\scriptstyle\pm 0.1$ | $\textbf{0.92}\scriptstyle\pm 0.0$ | $\textbf{0.62}\scriptstyle\pm 0.1$ | $\textbf{0.84}\scriptstyle\pm 0.0$
Table 15: Causal discovery results on synthetic scale-free datasets, discrete metrics. Each setting encompasses 5 distinct scale-free graphs. The symbol $\dagger$ indicates that Sea was not pretrained on this setting. Details regarding baselines can be found in B.2. $N$ | $E$ | Model | Linear | NN add. | NN non-add. |  Sigmoid† |  Polynomial†
---|---|---|---|---|---|---|---
|  |  |  EdgeAcc $\uparrow$ |  SHD $\downarrow$ |  EdgeAcc $\uparrow$ |  SHD $\downarrow$ |  EdgeAcc $\uparrow$ |  SHD $\downarrow$ |  EdgeAcc $\uparrow$ |  SHD $\downarrow$ |  EdgeAcc $\uparrow$ |  SHD $\downarrow$
10 | 10 | Dcdi-G | $0.85\scriptstyle\pm 0.0$ | $16.6\scriptstyle\pm 1$ | $0.82\scriptstyle\pm 0.2$ | $17.4\scriptstyle\pm 1$ | $0.81\scriptstyle\pm 0.0$ | $16.2\scriptstyle\pm 2$ | $0.71\scriptstyle\pm 0.2$ | $16.9\scriptstyle\pm 5$ | $0.70\scriptstyle\pm 0.2$ | $16.6\scriptstyle\pm 3$
Dcdi-Dsf | $\textbf{0.89}\scriptstyle\pm 0.1$ | $16.2\scriptstyle\pm 2$ | $0.75\scriptstyle\pm 0.1$ | $15.4\scriptstyle\pm 2$ | $0.78\scriptstyle\pm 0.2$ | $16.8\scriptstyle\pm 2$ | $0.80\scriptstyle\pm 0.2$ | $18.1\scriptstyle\pm 2$ | $0.77\scriptstyle\pm 0.2$ | $18.0\scriptstyle\pm 2$
Dcd-Fg | $0.60\scriptstyle\pm 0.1$ | $16.4\scriptstyle\pm 4$ | $0.57\scriptstyle\pm 0.1$ | $22.2\scriptstyle\pm 4$ | $0.57\scriptstyle\pm 0.2$ | $20.0\scriptstyle\pm 3$ | $0.47\scriptstyle\pm 0.3$ | $17.9\scriptstyle\pm 4$ | $0.59\scriptstyle\pm 0.2$ | $16.8\scriptstyle\pm 4$
DiffAn | $0.55\scriptstyle\pm 0.1$ | $9.2\scriptstyle\pm 4$ | $0.49\scriptstyle\pm 0.1$ | $14.6\scriptstyle\pm 4$ | $0.36\scriptstyle\pm 0.2$ | $11.6\scriptstyle\pm 4$ | $0.59\scriptstyle\pm 0.1$ | $7.7\scriptstyle\pm 3$ | $0.42\scriptstyle\pm 0.2$ | $14.8\scriptstyle\pm 6$
Deci | $0.51\scriptstyle\pm 0.2$ | $17.4\scriptstyle\pm 4$ | $0.55\scriptstyle\pm 0.1$ | $17.4\scriptstyle\pm 4$ | $0.58\scriptstyle\pm 0.1$ | $12.0\scriptstyle\pm 1$ | $0.62\scriptstyle\pm 0.2$ | $12.6\scriptstyle\pm 5$ | $0.74\scriptstyle\pm 0.2$ | $8.2\scriptstyle\pm 6$
InvCov | $0.60\scriptstyle\pm 0.2$ | $9.8\scriptstyle\pm 2$ | $0.54\scriptstyle\pm 0.2$ | $12.0\scriptstyle\pm 2$ | $0.54\scriptstyle\pm 0.2$ | $10.8\scriptstyle\pm 2$ | $0.40\scriptstyle\pm 0.1$ | $11.9\scriptstyle\pm 2$ | $0.14\scriptstyle\pm 0.1$ | $17.4\scriptstyle\pm 2$
Fci-Avg | $0.62\scriptstyle\pm 0.2$ | $8.4\scriptstyle\pm 2$ | $0.51\scriptstyle\pm 0.3$ | $7.8\scriptstyle\pm 1$ | $0.45\scriptstyle\pm 0.2$ | $8.0\scriptstyle\pm 2$ | $0.61\scriptstyle\pm 0.2$ | $9.2\scriptstyle\pm 3$ | $0.34\scriptstyle\pm 0.2$ | $9.6\scriptstyle\pm 2$
Gies-Avg | $0.83\scriptstyle\pm 0.1$ | $2.2\scriptstyle\pm 2$ | $0.60\scriptstyle\pm 0.1$ | $6.0\scriptstyle\pm 2$ | $0.75\scriptstyle\pm 0.2$ | $4.2\scriptstyle\pm 2$ | $0.72\scriptstyle\pm 0.1$ | $4.9\scriptstyle\pm 2$ | $0.73\scriptstyle\pm 0.2$ | $5.7\scriptstyle\pm 2$
Sea (Fci) | $0.87\scriptstyle\pm 0.1$ | $\textbf{1.2}\scriptstyle\pm 1$ | $0.93\scriptstyle\pm 0.1$ | $2.0\scriptstyle\pm 1$ | $\textbf{0.96}\scriptstyle\pm 0.1$ | $2.2\scriptstyle\pm 2$ | $0.70\scriptstyle\pm 0.2$ | $4.3\scriptstyle\pm 2$ | $0.82\scriptstyle\pm 0.2$ | $5.3\scriptstyle\pm 2$
Sea (Gies) | $0.85\scriptstyle\pm 0.1$ | $1.4\scriptstyle\pm 0$ | $\textbf{0.96}\scriptstyle\pm 0.1$ | $\textbf{1.8}\scriptstyle\pm 1$ | $0.94\scriptstyle\pm 0.1$ | $\textbf{2.0}\scriptstyle\pm 1$ | $\textbf{0.86}\scriptstyle\pm 0.1$ | $\textbf{3.4}\scriptstyle\pm 2$ | $\textbf{0.83}\scriptstyle\pm 0.1$ | $\textbf{5.0}\scriptstyle\pm 2$
10 | 40 | Dcdi-G | $0.79\scriptstyle\pm 0.1$ | $24.0\scriptstyle\pm 3$ | $0.77\scriptstyle\pm 0.1$ | $27.8\scriptstyle\pm 4$ | $0.82\scriptstyle\pm 0.1$ | $19.6\scriptstyle\pm 2$ | $0.65\scriptstyle\pm 0.1$ | $31.4\scriptstyle\pm 2$ | $0.61\scriptstyle\pm 0.2$ | $32.6\scriptstyle\pm 3$
Dcdi-Dsf | $0.84\scriptstyle\pm 0.0$ | $22.8\scriptstyle\pm 4$ | $0.78\scriptstyle\pm 0.0$ | $24.4\scriptstyle\pm 3$ | $0.83\scriptstyle\pm 0.1$ | $20.4\scriptstyle\pm 2$ | $0.71\scriptstyle\pm 0.1$ | $31.6\scriptstyle\pm 2$ | $0.62\scriptstyle\pm 0.1$ | $33.3\scriptstyle\pm 3$
Dcd-Fg | $0.36\scriptstyle\pm 0.1$ | $24.8\scriptstyle\pm 4$ | $0.41\scriptstyle\pm 0.1$ | $25.2\scriptstyle\pm 4$ | $0.38\scriptstyle\pm 0.2$ | $25.6\scriptstyle\pm 7$ | $0.41\scriptstyle\pm 0.1$ | $23.2\scriptstyle\pm 6$ | $0.54\scriptstyle\pm 0.1$ | $18.5\scriptstyle\pm 3$
DiffAn | $0.40\scriptstyle\pm 0.2$ | $29.8\scriptstyle\pm 7$ | $0.28\scriptstyle\pm 0.1$ | $37.0\scriptstyle\pm 2$ | $0.38\scriptstyle\pm 0.1$ | $32.6\scriptstyle\pm 2$ | $0.45\scriptstyle\pm 0.1$ | $28.0\scriptstyle\pm 6$ | $0.33\scriptstyle\pm 0.1$ | $32.7\scriptstyle\pm 5$
Deci | $0.43\scriptstyle\pm 0.1$ | $27.8\scriptstyle\pm 3$ | $0.66\scriptstyle\pm 0.1$ | $22.6\scriptstyle\pm 3$ | $0.48\scriptstyle\pm 0.1$ | $28.6\scriptstyle\pm 2$ | $0.52\scriptstyle\pm 0.1$ | $22.2\scriptstyle\pm 3$ | $0.66\scriptstyle\pm 0.1$ | $\textbf{13.3}\scriptstyle\pm 3$
InvCov | $0.42\scriptstyle\pm 0.1$ | $36.2\scriptstyle\pm 8$ | $0.50\scriptstyle\pm 0.1$ | $35.2\scriptstyle\pm 3$ | $0.48\scriptstyle\pm 0.1$ | $39.2\scriptstyle\pm 4$ | $0.59\scriptstyle\pm 0.1$ | $33.7\scriptstyle\pm 4$ | $0.34\scriptstyle\pm 0.1$ | $50.8\scriptstyle\pm 5$
Fci-Avg | $0.33\scriptstyle\pm 0.1$ | $23.8\scriptstyle\pm 2$ | $0.28\scriptstyle\pm 0.1$ | $27.2\scriptstyle\pm 2$ | $0.25\scriptstyle\pm 0.1$ | $27.6\scriptstyle\pm 3$ | $0.36\scriptstyle\pm 0.1$ | $26.1\scriptstyle\pm 2$ | $0.24\scriptstyle\pm 0.1$ | $27.3\scriptstyle\pm 2$
Gies-Avg | $0.46\scriptstyle\pm 0.1$ | $21.8\scriptstyle\pm 2$ | $0.50\scriptstyle\pm 0.1$ | $24.4\scriptstyle\pm 1$ | $0.48\scriptstyle\pm 0.2$ | $25.2\scriptstyle\pm 5$ | $0.52\scriptstyle\pm 0.1$ | $22.7\scriptstyle\pm 3$ | $0.64\scriptstyle\pm 0.1$ | $22.5\scriptstyle\pm 2$
Sea (Fci) | $0.88\scriptstyle\pm 0.1$ | $7.0\scriptstyle\pm 2$ | $0.95\scriptstyle\pm 0.0$ | $15.2\scriptstyle\pm 4$ | $\textbf{0.91}\scriptstyle\pm 0.1$ | $15.0\scriptstyle\pm 2$ | $\textbf{0.87}\scriptstyle\pm 0.1$ | $\textbf{13.9}\scriptstyle\pm 2$ | $0.91\scriptstyle\pm 0.0$ | $19.4\scriptstyle\pm 3$
Sea (Gies) | $\textbf{0.88}\scriptstyle\pm 0.1$ | $\textbf{6.6}\scriptstyle\pm 2$ | $\textbf{0.98}\scriptstyle\pm 0.0$ | $\textbf{14.0}\scriptstyle\pm 5$ | $0.88\scriptstyle\pm 0.0$ | $\textbf{14.4}\scriptstyle\pm 3$ | $0.87\scriptstyle\pm 0.0$ | $14.1\scriptstyle\pm 3$ | $\textbf{0.93}\scriptstyle\pm 0.1$ | $19.1\scriptstyle\pm 3$
20 | 20 | Dcdi-G | $0.95\scriptstyle\pm 0.1$ | $40.4\scriptstyle\pm 1$ | $0.92\scriptstyle\pm 0.0$ | $44.8\scriptstyle\pm 7$ | $\textbf{0.96}\scriptstyle\pm 0.1$ | $39.8\scriptstyle\pm 6$ | $\textbf{0.88}\scriptstyle\pm 0.1$ | $41.1\scriptstyle\pm 3$ | $0.79\scriptstyle\pm 0.1$ | $38.4\scriptstyle\pm 5$
Dcdi-Dsf | $\textbf{0.95}\scriptstyle\pm 0.1$ | $40.4\scriptstyle\pm 2$ | $0.92\scriptstyle\pm 0.1$ | $42.4\scriptstyle\pm 7$ | $0.90\scriptstyle\pm 0.0$ | $42.2\scriptstyle\pm 7$ | $0.84\scriptstyle\pm 0.1$ | $41.1\scriptstyle\pm 4$ | $\textbf{0.83}\scriptstyle\pm 0.1$ | $49.3\scriptstyle\pm 17$
Dcd-Fg | $0.68\scriptstyle\pm 0.1$ | $252.2\scriptstyle\pm 21$ | $0.77\scriptstyle\pm 0.1$ | $182.8\scriptstyle\pm 46$ | $0.78\scriptstyle\pm 0.1$ | $181.2\scriptstyle\pm 24$ | $0.70\scriptstyle\pm 0.1$ | $251.3\scriptstyle\pm 42$ | $0.69\scriptstyle\pm 0.1$ | $278.2\scriptstyle\pm 65$
DiffAn | $0.67\scriptstyle\pm 0.1$ | $23.6\scriptstyle\pm 12$ | $0.40\scriptstyle\pm 0.1$ | $42.2\scriptstyle\pm 20$ | $0.42\scriptstyle\pm 0.1$ | $34.0\scriptstyle\pm 10$ | $0.59\scriptstyle\pm 0.1$ | $22.6\scriptstyle\pm 11$ | $0.50\scriptstyle\pm 0.1$ | $46.8\scriptstyle\pm 13$
Deci | $0.50\scriptstyle\pm 0.2$ | $42.0\scriptstyle\pm 5$ | $0.54\scriptstyle\pm 0.1$ | $43.0\scriptstyle\pm 10$ | $0.57\scriptstyle\pm 0.1$ | $40.0\scriptstyle\pm 12$ | $0.51\scriptstyle\pm 0.1$ | $34.7\scriptstyle\pm 7$ | $0.65\scriptstyle\pm 0.1$ | $25.3\scriptstyle\pm 6$
InvCov | $0.54\scriptstyle\pm 0.1$ | $20.6\scriptstyle\pm 1$ | $0.54\scriptstyle\pm 0.1$ | $24.8\scriptstyle\pm 4$ | $0.52\scriptstyle\pm 0.0$ | $26.6\scriptstyle\pm 4$ | $0.50\scriptstyle\pm 0.1$ | $23.9\scriptstyle\pm 5$ | $0.13\scriptstyle\pm 0.0$ | $38.2\scriptstyle\pm 5$
Fci-Avg | $0.67\scriptstyle\pm 0.2$ | $13.8\scriptstyle\pm 1$ | $0.52\scriptstyle\pm 0.1$ | $17.4\scriptstyle\pm 1$ | $0.53\scriptstyle\pm 0.1$ | $17.8\scriptstyle\pm 4$ | $0.65\scriptstyle\pm 0.1$ | $16.7\scriptstyle\pm 4$ | $0.50\scriptstyle\pm 0.1$ | $18.9\scriptstyle\pm 4$
Gies-Avg | $0.82\scriptstyle\pm 0.1$ | $6.4\scriptstyle\pm 3$ | $0.71\scriptstyle\pm 0.0$ | $12.6\scriptstyle\pm 2$ | $0.68\scriptstyle\pm 0.2$ | $13.2\scriptstyle\pm 3$ | $0.75\scriptstyle\pm 0.1$ | $11.4\scriptstyle\pm 4$ | $0.73\scriptstyle\pm 0.1$ | $13.4\scriptstyle\pm 4$
Sea (Fci) | $0.91\scriptstyle\pm 0.1$ | $\textbf{2.6}\scriptstyle\pm 2$ | $\textbf{0.96}\scriptstyle\pm 0.0$ | $4.6\scriptstyle\pm 2$ | $0.93\scriptstyle\pm 0.1$ | $6.4\scriptstyle\pm 3$ | $0.82\scriptstyle\pm 0.1$ | $\textbf{6.7}\scriptstyle\pm 3$ | $0.76\scriptstyle\pm 0.1$ | $10.3\scriptstyle\pm 3$
Sea (Gies) | $0.85\scriptstyle\pm 0.1$ | $4.0\scriptstyle\pm 2$ | $0.95\scriptstyle\pm 0.0$ | $\textbf{3.6}\scriptstyle\pm 2$ | $0.93\scriptstyle\pm 0.1$ | $\textbf{6.2}\scriptstyle\pm 4$ | $0.80\scriptstyle\pm 0.1$ | $7.9\scriptstyle\pm 4$ | $0.82\scriptstyle\pm 0.2$ | $\textbf{9.9}\scriptstyle\pm 3$
20 | 80 | Dcdi-G | $0.83\scriptstyle\pm 0.0$ | $93.0\scriptstyle\pm 9$ | $0.89\scriptstyle\pm 0.1$ | $104.2\scriptstyle\pm 6$ | $\textbf{0.91}\scriptstyle\pm 0.0$ | $67.8\scriptstyle\pm 7$ | $0.78\scriptstyle\pm 0.1$ | $82.5\scriptstyle\pm 7$ | $0.60\scriptstyle\pm 0.1$ | $79.7\scriptstyle\pm 5$
Dcdi-Dsf | $0.84\scriptstyle\pm 0.0$ | $103.2\scriptstyle\pm 7$ | $0.85\scriptstyle\pm 0.1$ | $94.8\scriptstyle\pm 10$ | $0.89\scriptstyle\pm 0.0$ | $63.8\scriptstyle\pm 7$ | $0.78\scriptstyle\pm 0.1$ | $84.4\scriptstyle\pm 7$ | $0.64\scriptstyle\pm 0.1$ | $82.6\scriptstyle\pm 5$
Dcd-Fg | $0.63\scriptstyle\pm 0.1$ | $188.2\scriptstyle\pm 22$ | $0.70\scriptstyle\pm 0.1$ | $187.2\scriptstyle\pm 13$ | $0.78\scriptstyle\pm 0.1$ | $190.2\scriptstyle\pm 23$ | $0.71\scriptstyle\pm 0.1$ | $217.3\scriptstyle\pm 36$ | $0.71\scriptstyle\pm 0.1$ | $234.7\scriptstyle\pm 30$
DiffAn | $0.42\scriptstyle\pm 0.1$ | $110.6\scriptstyle\pm 16$ | $0.30\scriptstyle\pm 0.1$ | $144.6\scriptstyle\pm 10$ | $0.40\scriptstyle\pm 0.1$ | $118.8\scriptstyle\pm 12$ | $0.41\scriptstyle\pm 0.1$ | $99.7\scriptstyle\pm 21$ | $0.21\scriptstyle\pm 0.1$ | $149.4\scriptstyle\pm 10$
Deci | $0.33\scriptstyle\pm 0.1$ | $72.2\scriptstyle\pm 9$ | $0.48\scriptstyle\pm 0.1$ | $81.4\scriptstyle\pm 9$ | $0.48\scriptstyle\pm 0.1$ | $67.0\scriptstyle\pm 8$ | $0.50\scriptstyle\pm 0.1$ | $60.4\scriptstyle\pm 11$ | $0.58\scriptstyle\pm 0.1$ | $\textbf{47.2}\scriptstyle\pm 7$
InvCov | $0.50\scriptstyle\pm 0.0$ | $85.4\scriptstyle\pm 4$ | $0.48\scriptstyle\pm 0.0$ | $94.2\scriptstyle\pm 3$ | $0.53\scriptstyle\pm 0.0$ | $86.6\scriptstyle\pm 3$ | $0.51\scriptstyle\pm 0.1$ | $87.2\scriptstyle\pm 10$ | $0.33\scriptstyle\pm 0.0$ | $116.8\scriptstyle\pm 3$
Fci-Avg | $0.26\scriptstyle\pm 0.0$ | $58.2\scriptstyle\pm 5$ | $0.22\scriptstyle\pm 0.0$ | $58.4\scriptstyle\pm 4$ | $0.26\scriptstyle\pm 0.1$ | $55.0\scriptstyle\pm 7$ | $0.37\scriptstyle\pm 0.0$ | $59.3\scriptstyle\pm 6$ | $0.23\scriptstyle\pm 0.1$ | $62.9\scriptstyle\pm 3$
Gies-Avg | $0.65\scriptstyle\pm 0.0$ | $48.4\scriptstyle\pm 5$ | $0.71\scriptstyle\pm 0.1$ | $53.6\scriptstyle\pm 3$ | $0.68\scriptstyle\pm 0.1$ | $48.0\scriptstyle\pm 3$ | $0.64\scriptstyle\pm 0.1$ | $53.6\scriptstyle\pm 5$ | $0.61\scriptstyle\pm 0.1$ | $54.9\scriptstyle\pm 5$
Sea (Fci) | $0.92\scriptstyle\pm 0.0$ | $19.0\scriptstyle\pm 5$ | $\textbf{0.93}\scriptstyle\pm 0.0$ | $\textbf{48.4}\scriptstyle\pm 4$ | $0.88\scriptstyle\pm 0.1$ | $38.4\scriptstyle\pm 4$ | $0.85\scriptstyle\pm 0.1$ | $37.1\scriptstyle\pm 5$ | $0.86\scriptstyle\pm 0.1$ | $49.8\scriptstyle\pm 5$
Sea (Gies) | $\textbf{0.92}\scriptstyle\pm 0.0$ | $\textbf{17.6}\scriptstyle\pm 3$ | $\textbf{0.93}\scriptstyle\pm 0.0$ | $49.2\scriptstyle\pm 8$ | $0.89\scriptstyle\pm 0.0$ | $\textbf{37.2}\scriptstyle\pm 4$ | $\textbf{0.88}\scriptstyle\pm 0.0$ | $\textbf{35.1}\scriptstyle\pm 6$ | $\textbf{0.89}\scriptstyle\pm 0.0$ | $48.1\scriptstyle\pm 5$

For completeness, we include additional results and analysis.

Table 9 compares the heuristics-based greedy sampler (inverse covariance +
random) with the model uncertainty-based greedy sampler. Runtimes are plotted
in Figure 10. The latter was run on CPU only, since it was non-trivial to
access the GPU within a PyTorch data loader. We ran a forward pass to obtain
an updated selection score every 10 batches, so this accrued over 10 times the
number of forward passes, all on CPU. With proper engineering, this model-
based sampler is expected to be much more efficient than reported. Still, it
is faster than nearly all baselines.

Table 10 and Figure 9 show that the current implementations of Sea can
generalize to graphs up to $4\times$ larger than those seen during training.
With respect to larger graphs, there are two minor issues with the current
implementation. We set an insufficient maximum subset positional embedding
size of 500, and we did not sample random starting subset indices to ensure
that higher-order embeddings are updated equally. We anticipate that
increasing the limit on the number of subsets and ensuring that all embeddings
are sufficiently learned will improve the generalization capacity on larger
graphs. Nonetheless, our current model already obtains reasonable performance
on larger graphs, out of the box.

Due to the scope of this project and computing resources, we did not train
very “big” models in the modern sense. There is much space to scale, both in
terms of model architecture and the datasets covered. Table 11 probes the
generalization limits of the two implementations of Sea in this paper.

We identified that our models, trained primarily on additive noise, achieve
reasonable performance, but do not generalize reliably to causal mechanisms
with multiplicative noise. For example, we tested additional datasets with the
following mechanisms (same format as B.1).

  * •

Sigmoid mix: $y=\sum_{i=1}^{d}W_{i}\cdot\text{sigmoid}(X_{i})\times E$

  * •

Polynomial mix: $y=(W_{0}+XW_{1}+X^{2}W_{2})\times E$

We anticipate that incorporating these data into the training set would
alleviate some of this gap (just as training on synthetic mRNA data enabled us
to perform well there, despite its non-standard data distributions). However,
we did not have time to test this hypothesis empirically.

Dcdi learns a new generative model over each dataset, and its more powerful,
deep sigmoidal flow variant seems to perform well in some (but not all) of
these harder cases.

Tables 12 and 13 report the full results on $N=100$ graphs.

Tables 14 and 15 report our results on scale-free graphs.

Figure 9: mAP on graphs larger than seen during training. Due to an
insufficient maximum number of subset embeddings, we were only able to sample
500 batches, which appears to be too few for larger graphs. These values
correspond to the numbers in Table 10. Figure 10: Runtime for heuristics-based
greedy sampler vs. model uncertainty-based greedy sampler (suffix -l). For
sampling, the model was run on CPU only, due to the difficulty of invoking GPU
in the PyTorch data sampler.