# Graph Reconstruction from Path Correlation Data

Gregory Berkolaiko  Department of Mathematics, Texas A&M University, College
Station, TX 77843-3368  ,  Nick Duffield  Department of Electrical and
Computer Engineering, Texas A&M University, College Station, TX 77843  ,
Mahmood Ettehad  Department of Mathematics, Texas A&M University, College
Station, TX 77843-3368  and  Kyriakos Manousakis  Perspecta Labs, Basking
Ridge, NJ 07920

###### Abstract.

A communication network can be modeled as a directed connected graph with edge
weights that characterize performance metrics such as loss and delay. Network
tomography aims to infer these edge weights from their pathwise versions
measured on a set of intersecting paths between a subset of boundary vertices,
and even the underlying graph when this is not known. In particular, temporal
correlations between path metrics have been used infer composite weights on
the subpath formed by the path intersection. We call these subpath weights the
Path Correlation Data.

In this paper we ask the following question: when can the underlying weighted
graph be recovered knowing only the boundary vertices and the Path Correlation
Data? We establish necessary and sufficient conditions for a graph to be
reconstructible from this information, and describe an algorithm to perform
the reconstruction. Subject to our conditions, the result applies to directed
graphs with asymmetric edge weights, and accommodates paths arising from
asymmetric routing in the underlying communication network. We also describe
the relationship between the graph produced by our algorithm and the true
graph in the case that our conditions are not satisfied.

This material is based upon work supported by DARPA and by the National
Science Foundation under Grant DMS-1410657. The views, opinions and/or
findings expressed are those of the authors and should not be interpreted as
representing the official views or policies of the Department of Defense or
the U.S. Government.

Keywords: network tomography, end-to-end measurement, covariance, logical
trees, asymmetric routing, unicast probing

##  1\. Introduction

###  1.1. Background and Motivation

Graphs and Communication Networks. The problem that we study originates in
performance measurement of packet communications networks. These are modeled
as a a weighted directed graph $\mathcal{G}=(V,E,\mathcal{W})$ in which the
vertex set $V$ represents routers, the edges $E$ represent directed links
between routers, and the edge weights $\mathcal{W}$ characterize performance
metrics of the associated links. A subset $V^{B}\subset V$ of vertices
represents the “boundary” of the network where the measurements are performed.
We assume that there is a fixed directed path $\mathcal{P}(b,b^{\prime})$
connecting each boundary node pair $b,b^{\prime}\in V^{B}$ and that one can
measure the common portion of any two paths.

More specifically, we will assume one can measure the length of the following:
the path between any two boundary nodes, the common part of the two paths from
a boundary node to any two other boundary nodes, as well as the common part of
the paths to a boundary node from any two other boundary nodes. This set of
measurements we will call the Path Correlation Data (PCD). We establish
necessary and sufficient conditions — which turn out to be rather natural —
for the reconstruction of a graph from its PCD and present an algorithm to
achieve it. In the case when the underlying graph violates the
reconstructibility conditions, we describe the result of the algorithm — it
turns out to be the “simplest” routing network that produces the observed PCD.

Network Tomography and the Inversion Problem. The form of our model and the
assumptions we make originate from a body of work developed under the term
Network Tomography [19] that seeks to infer link metrics and even the
underlying network topology from the measured metric values on paths
traversing the network between a set of routers at the network boundary,
represented by $V^{B}$. This setting is similar to other graph reconstruction
problems, such as tomography of electrical resistance networks (see, e.g., [8,
6]), optical networks [10], and graph reconstruction from Schrödinger-type
spectral data (see, e.g., [3, 4]). However, in a communication network model
there is a single path between given origin and destination, in contrast to
the electrical current flowing between two points a resistive medium via all
possible paths. In this sense, our model is more similar to combinatorial
reconstruction problems [1, 15].

In many practical cases the communication network metrics are additive in the
sense that the sum of metric values over links in a path corresponds to the
same performance metric for the path. Examples of additive metrics include
mean packet delay, log packet transmission probability, and variances in an
independent link metric model. For additive metrics, a putative solution to
the network tomography problem attempts to invert a linear relation expression
between the set of path metrics $\mathcal{D}$ and the link metrics
$\mathcal{W}$ in the form

(1) $\mathcal{D}=\mathcal{A}\mathcal{W}$

Here $\mathcal{A}$ is the incidence matrix of links over paths,
$\mathcal{A}_{\mathcal{P},\ell}$ is 1 if path $\mathcal{P}$ traverses link
$\ell$, and zero otherwise. The linear system (1) is generally
underconstrained in real-life networks, and hence does not admit a unique
solution [9]. To overcome this deficiency, one approach has been to impose
conditions on the possible solutions, typically through sparseness,
effectively to find the “simplest” explanation of the observed path metrics;
see [12, 2]. A different approach in the similar problem of traffic matrix
tomography has been to reinterpret (1) as applying to bi-modal measurements of
packet and bytes counts [17], or of empirical means and variances then
imposing constraints between these based on empirical models [19, 20].
However, the high computational complexity of this approach makes it
infeasible for real-world communications networks [21], although quasi-
likelihood methods offer some reduction in complexity [16]. A related approach
known as Network Kriging seeks to reduce dimensionality in the path set by
assumption on prior covariances [9].

Correlations and Trees. More relevant for the work of this paper has been the
idea to exploit correlations between metrics on different paths that occur due
to common experience of packets on their intersection. One variant uses
multicast probing [7] or emulations thereof [14]. Another variant exploits the
fact that variances of some measurable packet statistics are both additive and
independent over links. If $\mathcal{D}$ is such a variance-based metric, then
$\text{Cov}(\mathcal{D}_{P_{1}},\mathcal{D}_{P_{2}})=\text{Var}(\mathcal{D}_{P_{1}\cap
P_{2}})$ where $\mathcal{D}_{P}$ denotes the metric value across path $P$; see
[13].

We abstract both these cases into a unified data model in which for every
triple $b$, $b_{1}$ and $b_{2}$ of boundary vertices, we can measure, via
covariances of the packet statistics, the metric of the intersection
$P=\mathcal{P}(b,b_{1})\cap\mathcal{P}(b,b_{2})$ as well as to the metric of
the intersection $P=\mathcal{P}(b_{1},b)\cap\mathcal{P}(b_{2},b)$. The results
of such measurements we will denote by $\operatorname{PCD}(b\prec
b_{1},b_{2})$ and $\operatorname{PCD}(b_{1},b_{2}\succ b)$ correspondingly. We
remark that we use the symbols $\prec$ and $\succ$ here not as binary
comparison operators but as pictograms meant to evoke the topological
structure of the corresponding pair of paths. The totality of such
measurements we call the path correlation data. Note that we will not, in
general, assume that the paths are symmetric; the path $\mathcal{P}(b,b_{1})$
may be different topologically from the path $\mathcal{P}(b_{1},b)$. As a
consequence, the values $\operatorname{PCD}(b\prec b_{1},b_{2})$ and
$\operatorname{PCD}(b_{1},b_{2}\succ b)$ are in general different. We will
assume that the function $\operatorname{PCD}$ is measured exactly; see below
for a brief discussion of possible sources of error and the techniques for
error-correction.

Under fairly general conditions that will be in force in this paper, the
problem has a natural formulation in terms of trees. First assume, that for
each $b,b_{1},b_{2}\in V^{B}$, the intersection
$\mathcal{P}(b,b_{1})\cap\mathcal{P}(b,b_{2})$ is connected. Second, assume
that the metric $\mathcal{D}$ is path increasing, i.e.,
$\mathcal{D}(\mathcal{P})<\mathcal{D}(\mathcal{P}^{\prime})$ for
$\mathcal{P}\subsetneq\mathcal{P}^{\prime}$. As shown in [11], the quantities
$\\{\operatorname{PCD}(b\prec b_{1},b_{2}):b_{1},b_{2}\in V^{B}\\}$ give rise
to an embedded logical weighted tree rooted at $b$ (called “source tree”). The
tree is computed iteratively by finding node pairs $(b_{1},b_{2})$ of maximal
$\operatorname{PCD}(b\prec b_{1},b_{2})$ and identifying each such pair with a
branch point in the logical tree. Each logical link is assigned a weight equal
to the difference between the values of $\text{PCD}(b\prec\cdot,\cdot)$
associated with its end points. Similarly, the quantities
$\operatorname{PCD}(b_{1},b_{2}\succ b)$ give rise to an embedded logical tree
with a single receiver $b$ and the sources $V^{B}\setminus\\{b\\}$. Such trees
are called “receiver trees”. Under the assumed conditions, our problem can be
restated as how to recover the underlying weighted graph from the set of
logical source and receiver trees rooted at every $b\in V^{B}$.

Summary of the Results. The main contribution of this paper, Theorem 2.1, is
to show that under natural conditions, a weighted directed graph $\mathcal{G}$
can be recovered knowing only the graph’s Path Correlation Data (PCD). The
conditions under which Theorem 2.1 holds are (i) each edge is traversed by at
least one path in $\mathcal{P}$; (ii) each non-boundary node is nontrivial in
the sense that in-degree and out-degree are not both equal $1$; and (iii) each
non-boundary node $x$ is nonseparable in the sense that the set of paths
$\mathcal{P}(x)\subset\mathcal{P}$ that pass through $x$ cannot be partitioned
into two or more subsets with non intersecting end point sets. Our result
holds without the assumption of weight symmetry (defined as requiring the
existence of the reverse of any edge in $G$, having the same weight) or path
symmetry (defined as the paths in either direction between two boundary nodes
traversing the same set of edges). We prove the correctness of our
reconstruction algorithm (Algorithm 1) under the stated assumptions.

Our solution does not assume that link weights are symmetric. Neither do we
assume that that paths in either direction between two endpoints are
symmetric: they are not required to traverse the same set of internal (i.e.
non-boundary) vertices. This level of generality reflects networking practice,
in which non-symmetric routing is employed for policy reasons including
performance and revenue optimization [18]. However, in the cases where
symmetric paths can be assumed a priori, this knowledge enlarges the set of
reconstructible networks. We therefore pay special attention to this case,
providing alternative definitions of the _nontrivial_ and _nonseparable_
vertices and a separate proof of the correctness of Algorithm 1 (which
requires a one-line change). We also establish the correctness of a second,
more customized Algorithm 2 which applies only in the case of symmetric
weights and paths, and which is computationally less expensive than Algorithm
1 applied to this case.

Inference from Inconsistent Data. Before describing our approach in more
detail, we note that practical network measurement may provision data with
imperfect consistency. For example, input data may be provided in the form of
weighted trees computed from packet measurement over time intervals that are
not perfectly aligned, so that the metric of a path
$\mathcal{P}(b,b^{\prime})$ may be reported differently in the source tree
from $b$ and the receiver tree to $b^{\prime}$. Even with aligned intervals,
deviations from the model and statistical fluctuations due to finitely many
probe packets may result in inconsistency. To enable our proposed algorithm to
operate with such data, we propose to compute a PCD that is a least-squares
fit to inconsistent tree data. This extension and associated error sensitivity
analysis is described in the forthcoming companion paper [5].

###  1.2. An example of a communication network

To illustrate the information available to an observer in our model, consider
the network graph schematically shown in Fig. 1. It is assumed that the end-
to-end measurements are possible among the boundary vertices
$V^{B}=\\{b_{1},...,b_{6}\\}$. The three versions of the same graph shown
contain information about the paths between the given source ($b_{1}$, $b_{2}$
and $b_{3}$, correspondingly) and the corresponding set of receivers
$V^{B}\setminus\\{b_{i}\\}$; the links belonging to these paths are
highlighted in thicker lines.

Figure 1. Alternative selections of the source and the corresponding routing
paths (bold edges).

From the point of view of an external observer, the routing paths on the graph
are hidden but can be reconstructed, to a certain extent, by the measurements
with a fixed source and alternating receivers, represented in our setting by
queries to the $\operatorname{PCD}$ function. As Fig. 2 shows, the trees
reconstructed from PCD are _logical_ trees where the edges represent the
amalgamated versions of the actual physical edges. For example, the logical
tree labeled $(SLb_{3})$ has a direct edge from $b_{3}$ to $b_{6}$, whereas
the actual route, shown in $(Sb_{3})$ passes through an internal node. Since
this node does not feature as a junction in the tree $(Sb_{3})$, it will not
be detected from the PCD. Moreover each internal vertex in the original graph
has multiple appearances in the logical trees with no identifying information
attached to them. Correctly identifying multiple representation of the same
internal node will be the central challenge of this work.

Figure 2. Representation of PCD on the network graph through the set of
observed logical source trees for sources $b_{1}$ to $b_{6}$.

The information form logical source trees (Fig. 2) is only enough for
reconstruction of special class of network graph, namely the symmetric one
where both the routing and edge weights are symmetric. When this is not the
case, the measurements of the form $\text{PCD}(b_{1},b_{2}\succ b)$ will be
essential to reconstruct _logical receiver trees_ shown in Fig. 3. Those
contain information about the paths with the selected receiver $b$ and with
the source set $V^{B}\setminus\\{b\\}$.

Figure 3. Representation of PCD on the network graph through the set of
observed logical receiver trees for receivers $b_{1}$ to $b_{6}$.

To summarize, the main goal in this paper is to develop a practical algorithm
to reconstruct the original graph from set of measurements information of the
form $\text{PCD}(b_{1}\prec b_{2},b_{3})$ and $\text{PCD}(b_{2},b_{3}\succ
b_{1})$ for $b_{1},b_{2},b_{3}\in V^{B}$ and to establish necessary and
sufficient conditions for the successful reconstruction.

###  1.3. Outline of paper

The outline of the paper is as follows. In Section 2 we state the definitions
and assumptions concerning the network topology and path measurements. We then
state our main Theorem 2.1 concerning the reconstruction of the general non-
symmetric weighted graph under these assumptions. The proof of Theorem 2.1
will proceed by establishing that a computation codified as Algorithm 1
reconstructs the topology under the stated assumptions, as established in
Section 3 for non-symmetric routing. We also discuss the operation of
Algorithm 1 on graphs that do not satisfy some assumptions of Theorem 2.1, and
the relation of the output to the true graph. The flow of Algorithm 1 is
slightly modified if the routing is symmetric. This case is considered in
Section 4. We also present a modified Algorithm 2, suitable _only_ for the
case of symmetric paths. We conclude in Section 5 with a discussion of
possible future work.

##  2\. Problem Statement and the Main Result

In this section we set up our model and formulate our results. Informally, we
have a graph with some metric assigned to directed edges and a subset of
vertices that is declared to be the “boundary” (denoted by $b_{1}$, $b_{2}$
etc) where the observations are made. We assume there is a fixed path
(“route”) between each ordered pair of boundary vertices (“source” to
“receiver”). We further assume that the metric is such that we can measure the
length of any route and also the length of the common part of any two routes
starting at the same source or any two routes coming into the same receiver.
These assumptions and the reconstruction problem are made precise below.

###  2.1. Problem Setup

######  Definition 1.

A network graph $\mathcal{N}=(\mathcal{G},V^{B},\mathcal{P})$ is an edge-
weighted graph $\mathcal{G}=(V,E,\mathcal{W})$ together with a set
$V^{B}\subset V$ of _boundary vertices_ and the paths $\mathcal{P}$ between
them. In detail,

  * •

$V$ is a finite set of vertices,

  * •

$E\subset V\times V$ is the set of directed edges (no loops or multiple edges
are allowed),

  * •

$\mathcal{W}:E\to\mathbb{R}_{+}$ are the edge weights,

  * •

$V^{B}$ is an arbitrary subset of $V$

  * •

there is a path $\mathcal{P}(b,b^{\prime})$ between any pair of boundary
vertices $b\neq b^{\prime}$; each path $\mathcal{P}(b,b^{\prime})$ is simple
and assumed to be fixed for the duration of observation of the network. The
paths are assumed to have the _tree consistency property_ : for any $b_{1}$,
$b_{1}^{\prime}$, $b_{2}$ and $b_{2}^{\prime}$ in $V^{B}$ the intersection
$\mathcal{P}(b_{1},b_{1}^{\prime})\cap\mathcal{P}(b_{2},b_{2}^{\prime})$ is
connected.

Figure 4. An example of the violation of the tree consistency property. The
paths $\mathcal{P}(b,b_{1})$ and $\mathcal{P}(b,b_{2})$ first diverge and then
meet again.

We will assume that a path $\mathcal{P}(b,b^{\prime})$ does not pass through
any other boundary vertices. This is done for convenience only; a graph can be
easily made to satisfy this condition by “drawing out” the boundary vertices
from the bulk of the graph as shown in Fig. 5. The vertices that do not belong
to the boundary we will call _internal vertices_ and use the notation
$V^{I}=V\setminus V^{B}$.

Figure 5. A graph (square with no diagonals) with the path
$\mathcal{P}(b_{1},b_{3})$ going through $b_{2}$. The same graph with the
boundary vertices drawn out.

We remark that we do not assume that the weights are symmetric:
$\mathcal{W}_{x,y}$ is generally different from $\mathcal{W}_{y,x}$. We also
do not need to assume that the paths are symmetric. However, since the latter
case is important in applications and allows for a simplified reconstruction
algorithm, we will devote some time to its separate treatment, in particular
in Definition 7 and Section 4.

Let us consider some implications of the tree consistency property. Consider
two paths, $\mathcal{P}(b,b_{1})$ and $\mathcal{P}(b,b_{2})$ with some
distinct $b,b_{1},b_{2}\in V^{B}$. The tree property implies that the paths
can be written as

(2) $\displaystyle\mathcal{P}(b,b_{1})$
$\displaystyle=[b,x_{1},x_{2},...,x_{j},y_{1},y_{2},...,b_{1}]$ (3)
$\displaystyle\mathcal{P}(b,b_{2})$
$\displaystyle=[b,x_{1},x_{2},...,x_{j},z_{1},z_{2},...,b_{2}],$

where the vertex sets $\\{y_{1},y_{2},...\\}$ and $\\{z_{1},z_{2},...\\}$ are
disjoint, see Fig. 6(a).

Similarly tree consistency property applied to paths $\mathcal{P}(b_{1},b)$
and $\mathcal{P}(b_{2},b)$ implies that

(4) $\displaystyle\mathcal{P}(b_{1},b)$
$\displaystyle=[b_{1},y_{1},y_{2},...,y_{i},x_{1},x_{2},...,b]$ (5)
$\displaystyle\mathcal{P}(b_{2},b)$
$\displaystyle=[b_{2},z_{1},z_{2},...,z_{j},x_{1},x_{2},...,b],$

with disjoint $\\{y_{1},y_{2},...,y_{m}\\}$ and $\\{z_{1},z_{2},...,z_{n}\\}$,
see Fig. 6(b).

######  Definition 2.

The vertex $x_{j}$ in equations (2)–(3) is called the $(b\prec
b_{1},b_{2})$-junction. Note that the set $\\{x_{1},...,x_{j}\\}$ is allowed
to be empty in which case $b$ acts as the junction. The vertex $x_{1}$ in
equations (4)–(5) is called the $(b_{1},b_{2}\succ b)$-junction.

Figure 6. (a) $x_{j}=(b\prec b_{1},b_{2})$-junction, (b)
$x_{1}=(b_{1},b_{2}\succ b)$-junction.

We remark that we use symbols $\prec$ and $\succ$ not as relational operators
but as separators in the list of 3 vertices which are pictorially similar to
the path configurations in Figure 6.

To specify the graph reconstruction problem we will be solving we need to
define the set of _measurements_ available to us. The length of a path is
defined as the sum of the weights $\mathcal{W}$ of its edges; we will denote
the length by $|\cdot|$. We consider a single vertex as a zero-length path;
the length of an empty set is also set to be zero. This allows us to assign
length to an intersection of two paths between boundary vertices which is
either empty or a single vertex or a connected subpath.

The totality of the measurements we can make will be called the Path
Correlation Data (PCD). In includes, for all $b,b_{1},b_{2}\in V^{B}$,

  * •

the length $|\mathcal{P}(b,b_{1})|$,

  * •

the length $\left|\mathcal{P}(b,b_{1})\cap\mathcal{P}(b,b_{2})\right|$, which
we will denote by $\operatorname{PCD}(b\prec b_{1},b_{2})$,

  * •

the length $\left|\mathcal{P}(b_{1},b)\cap\mathcal{P}(b_{2},b)\right|$, which
we will denote by $\operatorname{PCD}(b_{1},b_{2}\succ b)$.

Thus we can directly measure the distance from $b\in V^{B}$ to any $(b\prec
b_{1},b_{2})$-junction, or from the $(b_{1},b_{2}\succ b)$-junction to $b$. We
can also infer the distance from the $(b\prec b_{1},b_{2})$-junction to
$b_{1}$, or from $b_{1}$ to the $(b_{1},b_{2}\succ b)$-junction, see Fig. 7.

Figure 7. Various distances we can measure from Path Correlation Data (PCD).
Here $\delta=\operatorname{PCD}(b,\prec b_{1},b_{2})$ and
$\gamma=\operatorname{PCD}(b_{1},b_{2}\succ b)$.

Our principal question is thus: _Which network graphs
$(\mathcal{G},V^{B},\mathcal{P})$ can be reconstructed from their path
correlation data and how does one accomplish this?_

###  2.2. Some obvious necessary conditions

Before we state our result and the associated reconstruction algorithm, let us
consider examples that show some obvious necessary conditions we need to
impose on the network graph $\mathcal{N}=(\mathcal{G},V^{B},\mathcal{P})$ in
order to be able to reconstruct it.

######  Example 1.

Consider the network graphs in Fig. 8, with $V^{B}=\\{u,v,w\\}$ and with the
routing paths indicated by dashed lines. None of the routing paths pass
through the edge $e=(u,w)$ therefore the length of this edge cannot influence
the Path Correlation Data in any way. Conversely, the length of the edge $e$
(and even its existence) cannot be inferred from the PCD.

Figure 8. Failure to recover the edge $e=(u,w)$: the graphs (a) and (b) will
produce the same PCD since none of the paths pass through the extra edge.

.

######  Example 2.

Consider the network graphs in Fig. 9 with boundary vertex set
$V^{B}=\\{u,w\\}$. In the left graph the length of the edge $(x,u)$ will never
appear in the PCD on its own, without being added to the length of the edge
$(x,w)$. Therefore, it will be impossible to reconstruct the location of the
vertex $x$, and even detect it at all. This will be the case for any internal
vertex of degree 2.

Figure 9. Failure to recover the internal vertex $x$: the graphs (a) and (b)
will produce the same PCD as long as the sum of the lengths of $(u,x)$ and
$(x,w)$ in the graph (a) is equal to the length of the edge $(u,w)$ in the
graph (b).

######  Example 3.

Consider the network graphs in Fig. 10 with the boundary vertex set

(6) $V^{B}=\\{u_{1},v_{1},u_{2},v_{2}\\}.$

In Fig. 10(a) the paths $\mathcal{P}(u_{1},v_{1})$ and
$\mathcal{P}(u_{2},v_{2})$ intersect at an internal vertex $x$, while in Fig.
10(b) they do not have any vertices in common. However, the two graphs will
produce the same PCD and will be indistinguishable.

Figure 10. Failure to recover the integrity of the vertex $x$: the graphs (a),
(b) and (c) will produce the same PCD since the path between $u_{1}$ and
$v_{1}$ is in no way correlated to the path between $u_{2}$ and $v_{2}$.

The reader will undoubtedly observe that the vertices $x_{1}$ and $x_{2}$ in
Fig. 10(b) will not be detected, and the graph in Fig. 10(c) is the “minimal”
graph which will have the same PCD. By making the graph structure more
complicated one can easily construct an example where $x$, $x_{1}$ and $x_{2}$
will act as junctions for some pairs of paths and thus will be detectable, see
Fig. 11, but the two graphs are still not distinguishable from their PCD.

Figure 11. A more complicated example of failure to recover the integrity of
the vertex $x$.

Thus the real problem is that in the left graph in Fig. 11 there are two
families of paths going through the internal vertex $x$ that do not interact
in any way.

###  2.3. Statement of the main result

The main result of this paper is that the necessary conditions illustrated by
examples in Section 2.2 are in fact sufficient for the reconstruction! We
start by formalizing (and naming) the conditions we observed.

######  Definition 3.

An edge is called _unused_ if there is no path in $\mathcal{P}$ containing it.

We remark that if there are no unused edges in a network graph, each internal
vertex has at least one incoming and at least one outgoing edge.

######  Definition 4.

An internal vertex $x$ is called _trivial_ if it has only one incoming and
only one outgoing edge (i.e. edges of the form $(y_{1},x)$ and $(x,y_{2})$
correspondingly).

We remark that if there are no unused edges, then there are at least two paths
through every non-trivial internal vertex.

######  Definition 5.

For an internal vertex $x\in V^{I}$, let $S_{x}\subset V^{B}$ to be the set of
the sources and $R_{x}\subset V^{B}$ be the set of the receivers whose paths
pass through $x$. More precisely,

$\begin{split}S_{x}&=\big{\\{}b\in V^{B}:\exists\hat{b}\in V^{B},\
x\in\mathcal{P}(b,\hat{b})\big{\\}}\\\ R_{x}&=\big{\\{}\hat{b}\in
V^{B}:\exists b\in V^{B},\ x\in\mathcal{P}(b,\hat{b})\big{\\}}.\end{split}$

######  Definition 6.

A vertex $x\in V^{I}$ is called _separable_ if there are disjoint non-empty
partitions $S_{x}=S_{x}^{1}\cup S_{x}^{2}$ and $R_{x}=R_{x}^{1}\cup R_{x}^{2}$
with the property that

(7) $b\in S_{x}^{j},\ \hat{b}\in R_{x}^{j^{\prime}}\mbox{ with }j\neq
j^{\prime}\quad\Rightarrow\quad x\notin\mathcal{P}(b,\hat{b}).$

An example of a separable vertex is shown in Fig. 12. The partition sets here
are $S^{1}=\\{b_{1}\\}$, $S^{2}=\\{b_{2}\\}$, $R^{1}=\\{b_{3},b_{4}\\}$ and
$R^{2}=\\{b_{5},b_{6}\\}$.

Figure 12. Paths through a separable vertex $x$ and its separation into
$x_{1}$ and $x_{2}$.

Finally, if the graph has symmetric routing we need to modify the conditions
slightly but the resulting reconstructibility theorem will stay the same.
Naturally, symmetric routing is an extra piece of information and more graphs
are reconstructable in this case. The natural setting for the problem with
symmetric routing is a non-directed graph, but since we still allow non-
symmetric edge weights, we will keep the edges directed. As a result, edges
come in pairs which correspond to undirected edges splitting into two directed
ones. This is formalized in the definition of a “network graph with symmetric
routing” below.

######  Definition 7.

We will say that the network graph
$\mathcal{N}=(\mathcal{G},V^{B},\mathcal{P})$ has _symmetric routing_ if

  * •

for all $x,y\in V$, $(x,y)\in E$ implies $(y,x)\in E$ and

  * •

for all $b,b^{\prime}\in V^{B}$, the path $\mathcal{P}(b,b^{\prime})$ is the
reversal of the path $\mathcal{P}(b^{\prime},b)$, namely

(8)
$\mathcal{P}(b,b^{\prime})=[b,x_{1},x_{2},\ldots,x_{j},b^{\prime}]\quad\Rightarrow\quad\mathcal{P}(b^{\prime},b)=[b^{\prime},x_{j},x_{j-1},\ldots,x_{1},b].$

######  Definition 8.

A vertex $x\in V^{I}$ in a network graph with symmetric routing is _trivial_
if it has two (or less) adjacent vertices. A vertex $x\in V^{I}$ in a network
graph with symmetric routing is _separable_ if there is a disjoint partition
$S_{x}=S_{x}^{1}\cup S_{x}^{2}$ so that

(9) $b_{1}\in S_{x}^{1},\ b_{2}\in S_{x}^{2}\quad\Rightarrow\quad
x\notin\mathcal{P}(b_{1},b_{2}).$

We can now state our Main Theorem. We stress that the statement of the theorem
applies uniformly to network graphs with or without symmetric routing, the
differences being absorbed by the definitions above. We will still need to
provide two separate (but similar!) proofs.

######  Theorem 2.1 (Main Theorem).

Let $(\mathcal{G},V^{B},\mathcal{P})$ be a network graph. If

  1. (1)

no edge $e\in E$ is unused,

  2. (2)

no $x\in V^{I}$ is trivial,

  3. (3)

no $x\in V^{I}$ is separable,

then $(\mathcal{G},V^{B},\mathcal{P})$ is uniquely reconstructable from its
Path Correlation Data (PCD).

To put it more generally, in every class of network graphs with the same PCD,
there is a unique network graph which satisfies the above conditions.

The theorem will be proved constructively, by presenting a reconstruction
algorithm and verifying its result. The second part, which posits not only
uniqueness but also the existence of the reconstructed graph, means, in
practical terms, that even when given PCD from a graph that does not satisfy
the conditions, the algorithm will terminate and produce a “nearby” result
which does.

###  2.4. Comments on the algorithm for non-symmetric routing

The algorithm for the case of non-symmetric routing (Algorithm 1) works by
discovering the internal vertices and reconstructing the routing paths in the
format

(10)
$\mathcal{R}(b,\hat{b})=[(b,0),\,(x_{1},\delta_{1}),\,(x_{2},\delta_{2}),\ldots,\,(\hat{b},\delta)],$

where $\delta_{i}$ is the cumulative distance from $b$ to $x_{j}$ along the
path (naturally, $\delta=|\mathcal{P}(b,\hat{b})|$). Once every path is
complete, the edges can be read off as pairs of consecutive vertices appearing
in a path. The internal vertices are discovered as junctions. The main
difficulty lies in identifying different junctions that correspond to the same
vertex. This is done by a depth-first search in the function UpdatePath.

Algorithm 1 Reconstruction of the network graph
$(\mathcal{G},V^{B},\mathcal{P})$

1:for $b_{1},b_{2}\in V^{B}$ do $\triangleright$ Initialization

2: $\mathcal{R}(b_{1},b_{2})=[(b_{1},0),(b_{2},|\mathcal{P}(b_{1},b_{2})|)]$

3:end for

4:for $b_{1},b_{2},b_{3}\in V^{B}$ do $\triangleright$ Main Loop

5: create label $a$

6: $\delta=\operatorname{PCD}(b_{1}\prec b_{2},b_{3})$

7: UpdatePath($\mathcal{R}(b_{1},b_{2}),a,\delta$)

8: if “symmetric routing” then $a^{\prime}=a$ else create label $a^{\prime}$

9:
$\delta^{\prime}=|\mathcal{P}(b_{2},b_{1})|-\operatorname{PCD}(b_{2},b_{3}\succ
b_{1})$

10: UpdatePath($\mathcal{R}(b_{2},b_{1}),a^{\prime},\delta^{\prime}$)

11:end for

12:Read off the graph from reconstructed paths $\mathcal{R}$. $\triangleright$
Return the result

13:

14:function UpdatePath($\mathcal{R}(u,v),a,\delta$) $\triangleright$ Recursive
Function

15: if $\exists\,(\cdot,\delta)\in\mathcal{R}(u,v)$ then return

16: insert $(a,\delta)$ into $\mathcal{R}(u,v)$

17: $\delta^{\prime}=|\mathcal{P}(u,v)|-\delta$

18: for $z\in V^{B}$ do

19: if $\operatorname{PCD}(u\prec v,z)\geq\delta$ then
UpdatePath($\mathcal{R}(u,z),a,\delta$)

20: if $\operatorname{PCD}(u,z\succ v)\geq\delta^{\prime}$ then
UpdatePath($\mathcal{R}(z,v),a,|\mathcal{P}(z,v)|-\delta^{\prime}$)

21: end for

22:end function

The following comments might be in order. In lines 5–6 $a$ is the label for
the vertex that is the $(b_{1}\prec b_{2},b_{3})$-junction and $\delta$ is the
distance from $b_{1}$ to $a$ along the path $\mathcal{P}(b_{1},b_{2})$. In
lines 8–9 $a^{\prime}$ is the label for the $(b_{2},b_{3}\succ
b_{1})$-junction and $\delta^{\prime}$ is the distance from $b_{2}$ to
$a^{\prime}$ along the path $\mathcal{P}(b_{2},b_{1})$. If we know a priori
that the routing is symmetric, the $(b_{1}\prec b_{2},b_{3})$-junction and the
$(b_{2},b_{3}\succ b_{1})$-junction are the same vertex and can receive the
same label.

Line 15 checks if there is already a vertex distance $\delta$ from $b_{1}$ (if
there is, label $a$ is unused). Finally, the loop starting on line 18 looks
for any other paths that the vertex with label $a$ must belong to. Here we
rely heavily on the tree consistency property.

Figure 13. Insertion of internal vertex $x$ in the reconstructed paths, (a)
$\mathcal{R}(u,z)$, and (b) $\mathcal{R}(z,v)$ by fulfillment of conditions 19
and 20 respectively called by line 7 of Algorithm 1.

Some further code improvements are possible. Creating and then discarding
unused labels can be avoided either by performing a check similar to line 15
in the main loop or, more elegantly, by making $a$ an optional argument to the
function UpdatePath and creating a label after line 15 if no $a$ was supplied.
Additionally, if the edge weights are symmetric, the call to
$\operatorname{PCD}$ in line 9 can be avoided by using
$\operatorname{PCD}(b_{2},b_{3}\succ b_{1})=\operatorname{PCD}(b_{1}\prec
b_{2},b_{3})=\delta$.

Finally, a crude upper bound on complexity of the algorithm (in terms of label
insertions into various $\mathcal{R}$) is $|V^{I}|\times|V^{B}|^{2}$ i.e. the
product of number of internal vertices and the square number of boundary
vertices of the graph.

##  3\. Proof of the Reconstruction: Non-Symmetric Paths

The proof of Theorem 2.1 has three parts, with very similar arguments in each
part. To facilitate the proof, we first state and prove an auxiliary lemma.

######  Lemma 3.1.

Let $x$ be an arbitrary _non-separable_ internal vertex and let $A:V^{B}\times
V^{B}\to\\{\mathrm{T},\mathrm{F}\\}$ be a Boolean property (predicate) that is
defined on the pairs $\left(b,b^{\prime}\right)$ such that
$x\in\mathcal{P}(b,b^{\prime})$. Assume $A$ is non-constant (i.e. true on some
paths and false on some others). Define $S_{x}^{1}$ to be the set of the
sources of the paths through $x$ for which $A$ is true and $S_{x}^{2}$ to be
the set of the sources of the paths for which $A$ is false. Define $R_{x}^{1}$
and $R_{x}^{2}$ analogously. More formally,

(11) $\begin{split}S_{x}^{1}&=\left\\{b\in S_{x}:\exists b^{\prime}\in
R_{x}\,\Big{[}x\in\mathcal{P}(b,b^{\prime})\,\wedge\,A\left(b,b^{\prime}\right)\Big{]}\right\\},\\\
S_{x}^{2}&=\left\\{b\in S_{x}:\exists b^{\prime}\in
R_{x}\,\Big{[}x\in\mathcal{P}(b,b^{\prime})\,\wedge\,\neg
A\left(b,b^{\prime}\right)\Big{]}\right\\},\\\
R_{x}^{1}&=\left\\{b^{\prime}\in R_{x}:\exists b\in
S_{x}\,\Big{[}x\in\mathcal{P}(b,b^{\prime})\,\wedge\,A\left(b,b^{\prime}\right)\Big{]}\right\\},\\\
R_{x}^{2}&=\left\\{b^{\prime}\in R_{x}:\exists b\in
S_{x}\,\Big{[}x\in\mathcal{P}(b,b^{\prime})\,\wedge\,\neg
A\left(b,b^{\prime}\right)\Big{]}\right\\}.\end{split}$

Then $S_{x}^{1}\cap S_{x}^{2}$ and $R_{x}^{1}\cap R_{x}^{2}$ cannot both be
empty.

###### Proof.

Since $A$ is not always false, the sets $S_{x}^{1}$ and $R_{x}^{1}$ are non-
empty; since $A$ is not always true, $S_{x}^{2}$ and $R_{x}^{2}$ are non-
empty. Furthermore, it is easy to see that

(12) $S_{x}^{1}\cup S_{x}^{2}=S_{x}\qquad\mbox{and}\qquad R_{x}^{1}\cup
R_{x}^{2}=R_{x}.$

Assume that $S_{x}^{1}\cap S_{x}^{2}=R_{x}^{1}\cap R_{x}^{2}=\emptyset$. Then
we are in a position to use non-separability of the vertex $x$ and to conclude
that there is a path (without loss of generality) from $b_{1}\in S_{x}^{1}$ to
$b_{2}\in R_{x}^{2}$. But this path either has property $A$ or it does not. In
the former case, $b_{2}\in R_{x}^{1}$ and in the latter $b_{1}\in S_{x}^{2}$,
contradicting the assumption of disjointedness. ∎

###### Proof of Theorem 2.1: unique reconstructability.

We will now verify that, given the PCD from a graph that satisfies the
conditions of the Theorem, the algorithm will produce the correct
reconstruction. It is straightforward to check that the algorithm places a
label for a vertex $x$ only in the reconstructions of paths that actually
contain $x$ and with the right value of the cumulative distance $\delta$. Thus
it remains to show that

  * •

every vertex $x$ has at least one label created for it

  * •

the reconstructed paths are not missing any vertices.

  * •

no more than one label is created for each vertex

Then we will read off sequential pairs of vertices from the reconstructed
paths to identify edges. Since there are no missing vertices in $\mathcal{R}$,
the edges thus reconstructed will correspond to actual edges in $E$. By
condition 1 of the theorem, every edge will appear in at least one
$\mathcal{R}(u,v)$ and will therefore be reconstructed.

Let $x$ be an arbitrary internal vertex. We would like to show the algorithm
will create a label for $x$ and place it in some reconstructed path containing
$x$.

Fix an arbitrary path through $x$ and denote the edges that the path visits
while going through $x$ by $e_{1}=(x_{1},x)$ and $e_{2}=(x,x_{2})$. We will
now use Lemma 3.1 with the property $A=A\left(b,b^{\prime}\right)$ defined as
the statement “the path $\mathcal{P}(b,b^{\prime})$ passes through _both_
$e_{1}$ and $e_{2}$”, or, in other words

(13) $A\left(b,b^{\prime}\right)=\text{``$\mathcal{P}(b,b^{\prime})$ can be
written as $[b,\ldots,x_{1},x,x_{2},\ldots,b^{\prime}]$''}.$

There is at least one path on which $A$ is true. Since $x$ is non-trivial and
each of its incident edges belongs to at least one simple path, there is at
least one other path passing through $x$ and _not_ containing both $e_{1}$ and
$e_{2}$. Therefore we can apply Lemma 3.1 and conclude that one of the pairs
$S_{x}^{1}$ and $S_{x}^{2}$ or $R_{x}^{1}$ and $R_{x}^{2}$ are not disjoint.

Without loss of generality, consider a boundary vertex $b\in S_{x}^{1}\cap
S_{x}^{2}$. Let $\mathcal{P}_{1}(b,b_{1})$ be a path containing both $e_{1}$
and $e_{2}$ and $\mathcal{P}_{2}(b,b_{2})$ be a path that passes through $x$
but does not contain both $e_{1}$ and $e_{2}$. Since both $\mathcal{P}_{1}$
and $\mathcal{P}_{2}$ contain $b$ and $x$, they must coincide from $b$ to $x$
by the tree consistency property. Therefore, $\mathcal{P}_{2}$ contains
$e_{1}$ and can not contain $e_{2}$. We conclude that $\mathcal{P}_{1}$ and
$\mathcal{P}_{2}$ diverge exactly at $x$, see Fig. 14. In other words, $x$ is
the $(b\prec b_{1},b_{2})$-junction and a label will be created for it in the
main loop. This label will be placed into $\mathcal{R}(b^{\prime},b_{1})$
unless there is already another label corresponding to $x$ there.

Figure 14. Two paths through a vertex $x$. The path $\mathcal{P}(b,b_{1})$
contains both $e_{1}$ and $e_{2}$ and the $\mathcal{P}(b,b_{2})$ does not.

We will now prove that each reconstructed path contains labels for all
vertices composing the actual path. Assume the contrary: there is a path whose
reconstruction does not contain a label for an internal vertex $x$. Define the
property $A$ by

(14) $A\left(b,b^{\prime}\right)=\text{``$\exists
a(x)\in\mathcal{R}(b,b^{\prime})$''}.$

We have already proved that a label for $x$ will be placed in _some_ path;
together with our assumption it means that $A$ is non-constant and we can
apply Lemma 3.1.

If there is a vertex $b\in S_{x}^{1}\cap S_{x}^{2}$ then we can find
$b_{1}^{\prime},b_{2}^{\prime}\in V^{B}$ such that
$\mathcal{P}(b,b_{1}^{\prime})$ and $\mathcal{P}(b,b_{2}^{\prime})$ both pass
through $x$ but $\mathcal{R}(b,b_{1}^{\prime})$ has a label corresponding to
$x$ and $\mathcal{R}(b,b_{2}^{\prime})$ does not. By the tree consistency
property, the two paths coincide from $b$ to at least $x$, therefore
$\text{PCD}(b\prec b_{1}^{\prime},b_{2}^{\prime})\geq\delta$, where $\delta$
is the distance from $b$ to $x$ along the path
$\mathcal{P}(b,b_{1}^{\prime})$. However, the label $a(x)$ was placed into
$\mathcal{R}(b,b_{1}^{\prime})$ by a call to UpdatePath with this $\delta$.
This would trigger the condition on line 19 with $w=b_{2}^{\prime}$ and the
same label would be placed into $\mathcal{R}(b,b_{2}^{\prime})$, a
contradiction. The case when $R_{x}^{1}\cap R_{x}^{2}$ is non-empty is treated
similarly but this time condition on line 20 ensures the transfer of the
label.

The last step of the proof of reconstruction is to check that only one label
is created for any vertex. Assume the contrary, there is a vertex $x$ which
has at least two different labels corresponding to it appearing in different
reconstructed paths. Fix one of the labels $a(x)$ and define property $A$ by

(15)
$A\left(b,b^{\prime}\right)=\text{``$a(x)\in\mathcal{R}(b,b^{\prime})$''}.$

This definition of $A$ is very similar to eq. (14), but here $a(x)$ is some
fixed label, whereas in (14) it was _any_ label of $x$.

By Lemma 3.1 and without loss of generality, there is a vertex $b\in
S_{x}^{1}\cap S_{x}^{2}$. This means that there is a path
$\mathcal{P}(b,b_{1})$ with the label $a(x)$ and a path $\mathcal{P}(b,b_{2})$
with a label $a^{\prime}(x)$ different from $a(x)$ (we remark that we have
already shown that each reconstructed path contains labels for all its
vertices). As before, the two paths coincide from $b$ to at least $x$,
therefore $\text{PCD}(b\prec b_{1}^{\prime},b_{2}^{\prime})\geq\delta$, where
$\delta$ is the distance from $b$ to $x$ along the path
$\mathcal{P}(b,b_{1}^{\prime})$. During the execution of the algorithm, one of
the labels was placed in its respective path first. But then the condition on
line 19 would be triggered and the same label would be copied to the other
path, before the other label is created. We have thus arrived to a
contradiction. ∎

###### Proof of Theorem 2.1: reconstruction of a non-compliant graph.

We will now consider the output of the algorithm in case the PCD was created
by the network graph $(\mathcal{G},V^{B},\mathcal{P})$ that violates some of
the conditions of the Theorem. We will show that there is a “compliant”
network graph that has the same PCD and which will therefore serve as the
output of the algorithm.

We start from the network graph $\mathcal{N}=(\mathcal{G},V^{B},\mathcal{P})$
and apply the following “cleaning” operations to them (the order is
important): (1) remove all unused edges, (2) split each separable vertex into
2 or more non-separable vertices111See Remark 3.2 below for a detailed
discussion of why such a splitting exists., (3) remove each trivial vertex by
merging its incident edges into one edge. The only adjustments needed to the
paths $\mathcal{P}$ is to choose the correct copies of the split vertices. The
set of boundary vertices remains the same.

An example of performing these operations is shown in Fig. 15. In particular,
the internal vertex $x$ fails the non-separability condition, which is seen by
defining the disjoint partitions

$\displaystyle S=S^{1}\cup S^{2}=\\{b_{1},b_{3}\\}\cup\\{b_{2}\\}$
$\displaystyle R=R^{1}\cup R^{2}=\\{b_{2}\\}\cup\\{b_{1},b_{3}\\}$

Figure 15. Cleaning of a graph: (a) the original graph (b) removing unused
edge $e=(b_{2},b_{3})$ (c) splitting the vertex $x$ into $x_{1}$ and $x_{2}$,
(d) removing trivial vertices $y$ and $x_{2}$. The edges that have no
direction marked on them run in both directions.

We remark that splitting a separable vertex may require duplicating some
incoming or outgoing edges, see Fig. 12, in which case the weights get
duplicated too. The edges will be duplicated only if both resulting edges are
present in some paths; thus no unused edges will be created.

Suppose an internal vertex got split into $x_{1}$ and $x_{2}$. It follows from
the definition of the separable vertex that if $x\in\mathcal{P}(b,b_{1})$ and
$x\in\mathcal{P}(b,b_{2})$ before the split, then after the split either both
paths contain $x_{1}$ or both of them contain $x_{2}$. Therefore the length of
each intersection of the form $\mathcal{P}(b,b_{1})\cap\mathcal{P}(b,b_{2})$
remains unchanged after a split. The same applies to any pair of paths
$x\in\mathcal{P}(b_{1},b)$ and $x\in\mathcal{P}(b_{2},b)$. We conclude that
the PCD remains unchanged by the operations above.

We denote the network graph so obtained by $\mathcal{N}^{C}$ (for “compliant”
or “cleaned”). It is easy to see that $\mathcal{N}^{C}$ satisfies the
conditions of the Theorem and will therefore be reconstructed from its PCD by
the algorithm. However, the PCD of $\mathcal{N}^{C}$ is the same as the PCD of
$\mathcal{N}$. Therefore, given the PCD of $\mathcal{N}$, the algorithm will
return the network graph $\mathcal{N}^{C}$. This logic is illustrated by Fig.
16.

Figure 16. Flow of the proof of the reconstruction of a non-compliant graph:
$C$ is the operations that produce the corresponding compliant network graph
$\mathcal{N}^{C}$, the Path Correlation Data of both graphs is the same.

.

∎

######  Remark 3.2.

In the proof above we implicitly assumed that there exists a unique maximal
splitting of a vertex into non-separable parts. We outline the proof of this
fact. Fix $x$ and define equivalence relations $\overset{S}{\sim}$ and
$\overset{R}{\sim}$ on $S_{x}$ and $R_{x}$ correspondingly by letting

(16) $\displaystyle b_{1}\overset{S}{\sim}b_{2}\qquad$
$\displaystyle\mbox{if}\qquad\exists\hat{b}:\
x\in\mathcal{P}(b_{1},\hat{b})\mbox{ and }x\in\mathcal{P}(b_{2},\hat{b}),$
(17) $\displaystyle\hat{b}_{1}\overset{R}{\sim}\hat{b}_{2}\qquad$
$\displaystyle\mbox{if}\qquad\exists b:\ x\in\mathcal{P}(b,\hat{b}_{1})\mbox{
and }x\in\mathcal{P}(b,\hat{b}_{2}),$

and closing each one by transitivity. It is easy to see that they are “dual”
in the following sense: if $x\in\mathcal{P}(b_{1},\hat{b}_{1})$ and
$x\in\mathcal{P}(b_{2},\hat{b}_{2})$ then

(18)
$b_{1}\overset{S}{\sim}b_{2}\quad\Leftrightarrow\quad\hat{b}_{1}\overset{R}{\sim}\hat{b}_{2}.$

As a consequence, there is a natural one-to-one correspondence between the
equivalence classes of $\overset{S}{\sim}$ and the equivalence classes of
$\overset{R}{\sim}$. These equivalence classes provide the finest separation
of the vertex $x$. To be more precise, the disjoint partitions

(19) $\displaystyle
S_{x}=[b_{1}]_{S}\cup[b_{2}]_{S}\cup\ldots\cup[b_{m}]_{S},$ (20)
$\displaystyle
R_{x}=[\hat{b}_{1}]_{R}\cup[\hat{b}_{2}]_{R}\cup\ldots\cup[\hat{b}_{m}]_{R},$

satisfy condition (9). Here $[\cdot]_{S}$ and $[\cdot]_{R}$ denote equivalence
classes with respect to $\overset{S}{\sim}$ and $\overset{R}{\sim}$ and
$x\in\mathcal{P}(b_{j},\hat{b}_{j})$ for every $j$.

Furthermore, if the nonempty partitions $S_{x}=S_{x}^{1}\cup S_{x}^{2}$ and
$R_{x}=R_{x}^{1}\cup R_{x}^{2}$ satisfy Definition 6 then for any $b\in
S_{x}$, either $[b]_{S}\subset S_{x}^{1}$ or $[b]_{S}\subset S_{x}^{2}$, and
similarly for $R$.

##  4\. Symmetric Paths

Reconstruction of network graph with the prior knowledge that the routing is
symmetric (the edge weights may not be symmetric) has the advantage of being
able to reconstruct a wider class of network graphs. In the following we
present the proof of unique reconstruction of network graph with symmetric
routing if the conditions of the main Theorem are satisfied. The only
differences on the required conditions for exact recovery are contained in
definition 8 for the non-triviality and non-separability of internal vertex.
We start with an appropriate modification of Lemma 3.1.

######  Lemma 4.1.

Let $x$ be an arbitrary _non-separable_ internal vertex and let $B$ be a non-
constant _symmetric_ Boolean property (predicate) that is defined on the pairs
$\left(b,b^{\prime}\right)$ such that $x\in\mathcal{P}(b,b^{\prime})$ and
$x\in\mathcal{P}(b^{\prime},b)$. Define $S_{x}^{1}$ to be the set of the
sources of the paths through $x$ for which $B$ is true and $S_{x}^{2}$ to be
the set of the sources of the paths for which $B$ is false. More formally,

(21) $\begin{split}S_{x}^{1}&=\left\\{b\in S_{x}:\exists b_{1}\in
V^{B}\,\Big{[}x\in\mathcal{P}(b,b_{1})\,\wedge\,B\left(b,b_{1}\right)\Big{]}\right\\},\\\
S_{x}^{2}&=\left\\{b\in S_{x}:\exists b_{2}\in
V^{B}\,\Big{[}x\in\mathcal{P}(b,b_{2})\,\wedge\,\neg
B\left(b,b_{2}\right)\Big{]}\right\\}\end{split}$

Then $S_{x}^{1}\cap S_{x}^{2}$ cannot be empty.

###### Proof.

For symmetric routing the receiver $R_{x}$ and the source set
$S_{x}=S_{x}^{1}\cup S_{x}^{2}$ coincide. Assume that $S_{x}^{1}\cap
S_{x}^{2}=\emptyset$. Then using the non-separability of vertex $x$, there is
a path from $b_{1}\in S_{x}^{1}$ to $b_{2}\in S_{x}^{2}$. But this path either
has property $B$ or it does not.

  * •

In the former case, we use symmetry of $B(b_{1},b_{2})$ to conclude $b_{2}\in
S_{x}^{1}$.

  * •

In the latter case $B(b_{1},b_{2})$ is false, thereby $b_{1}\in S_{x}^{2}$,

either way, contradicting the assumption of disjointedness. ∎

Now we are in the position to apply Lemma 4.1 to prove the unique
reconstruction of network graph with symmetric routing. While the proof steps
are very similar to the ones discussed in proving Theorem 2.1, the main
difference here is to ensure that the Boolean function $B$ is symmetric.

###### Proof of unique reconstructability for symmetric routing.

Every vertex $x$ has at least one label created for it. For an internal vertex
$x$, fix an arbitrary path $\mathcal{P}_{0}$ through $x$ and denote the
vertices that the path visits before and after getting to $x$ by $x_{1}$ and
$x_{2}$. Denote by

$\displaystyle\Lambda_{x}:=\big{\\{}(x_{1},x),(x,x_{1}),(x,x_{2}),(x_{2},x)\big{\\}}\subseteq
E$

the subset of edges contains $x$ and either $x_{1}$ or $x_{2}$ as the other
end vertex. Define the property $B=B(b,b^{\prime})$ as the statement

(22) $B\left(b,b^{\prime}\right)=\text{``$\mathcal{P}(b,b^{\prime})$ satisfies
$|\mathcal{P}(b,b^{\prime})\cap\Lambda_{x}|=2$''},$

in other words, $B$ is true if the path can be written as a sequence

$\displaystyle\mathcal{P}(b,b^{\prime})=[b,\ldots,x_{1},x,x_{2},\ldots,b^{\prime}]\quad\text{or}\quad\mathcal{P}(b,b^{\prime})=[b,\ldots,x_{2},x,x_{1},\ldots,b^{\prime}].$

Due to the symmetric routing assumption on the network graph, function $B$
will be true for the reverse path $\mathcal{P}(b^{\prime},b)$ as well. Because
of our choice of $x_{1}$ and $x_{2}$, there are at least two paths on which
$B$ is true, namely $\mathcal{P}_{0}$ and its reversal. Since vertex $x$ is
non-trivial, there exists vertex $x_{3}$ adjacent to $x$ and a path
$\mathcal{P}^{\prime}$ passing through $(x,x_{3})$ or $(x_{3},x)$ on which $B$
is false. Therefore we can apply 4.1 and conclude that $S_{x}^{1}$ and
$S_{x}^{2}$ are not disjoint.

Consider a boundary vertex $b\in S_{x}^{1}\cap S_{x}^{2}$, and let
$\mathcal{P}_{1}(b,b_{1})$ and $\mathcal{P}_{2}(b,b_{2})$ be the two paths
where $B$ is true and false respectively. By the tree property, the two paths
follow same set of edges before diverging exactly at $x$ because $B$ is false
on $\mathcal{P}_{2}$. As a result $x$ is the $(b\prec b_{1},b_{2})$-junction
and a label will be created for it in the main loop of Algorithm 1. This label
will be placed in both reconstructed paths $\mathcal{R}(b,b_{1})$ and
$\mathcal{R}(b_{1},b)$ unless there is already another label corresponding to
$x$ there.

The reconstruction paths are not missing any vertices. Fix an internal vertex
$x$ and define the property

(23) $B\left(b,b^{\prime}\right)=\text{``$\exists a(x)$ such that
$a(x)\in\mathcal{R}(b,b^{\prime})$ and $a(x)\in\mathcal{R}(b^{\prime},b)$''},$

which is clearly symmetric by its definition. We emphasis that
$\mathcal{R}(b,b^{\prime})$ and $\mathcal{R}(b^{\prime},b)$ are required to
contain the same label for $x$. We already proved that a label will be created
for $x$, and when the first label is created, it will be placed into a path
and its reversal. Therefore $B$ is true on some paths. We will prove that this
$B$ holds for all paths $(b,b^{\prime})$ containing $x$. This will establish
not only that the reconstructed paths are not missing any vertices, but also
that the labels in $\mathcal{R}(b^{\prime},b)$ are the same as in
$\mathcal{R}(b,b^{\prime})$.

Assume the contrary: $B$ fails for some path. We apply Lemma 4.1 and let $b\in
S_{x}^{1}\cap S_{x}^{2}$. Then there exist $b_{1},b_{2}\in R_{x}$ so that a
representation $\hat{a}(x)$ exists in both $\mathcal{R}(b,b_{1})$ and
$\mathcal{R}(b_{1},b)$ while $B$ is false on $(b,b_{2})$. The latter implies
that $\hat{a}(x)$ cannot be present in both reconstructed paths
$\mathcal{R}(b,b_{2})$ or $\mathcal{R}(b_{2},b)$. This can be summarized as
follows:

(24) $\exists\hat{a}(x)\mbox{ such that }\\\
\hat{a}(x)\in\mathcal{R}(b,b_{1})\mbox{ and
}\hat{a}(x)\in\mathcal{R}(b_{1},b)\mbox{ and
}\Big{(}\hat{a}(x)\not\in\mathcal{R}(b,b_{2})\mbox{ or
}\hat{a}(x)\not\in\mathcal{R}(b_{2},b)\Big{)}.$

Now without loss of generality, assume that
$\hat{a}(x)\not\in\mathcal{R}(b_{2},b)$. The same arguments as in the proof of
Theorem 2.1 guarantee that $\text{PCD}(b_{1},b_{2}\succ
b)\geq\delta^{\prime}$, where $\delta^{\prime}$ is the distance from $x$ to
$b$. Therefore the insertion of the representation $\hat{a}(x)$ into
$\mathcal{R}(b_{2},b)$ will be attempted by triggering the condition in line
20 for $z=b_{2}$ within the call of the function
UpdatePath$(\mathcal{R}(b_{1},b),\hat{a},\cdot)$. Since
$\hat{a}(x)\not\in\mathcal{R}(b_{2},b)$, we conclude that there is another
label $a^{\prime}(x)\in\mathcal{R}(b_{2},b)$, placed there earlier by a call
to UpdatePath$(\mathcal{R}(b_{2},b),a^{\prime},\cdot)$. But then the condition
in line 20 will be triggered with $z=b_{1}$ and the label $a^{\prime}$ will be
placed into $\mathcal{R}(b_{2},b)$, in contradiction to our assumptions.

The last step of the proof is to show that no more than one label is created
for each vertex. For a fixed label $a(x)$ of vertex $x$, define the property

(25)
$B\left(b,b^{\prime}\right)=\text{``$a(x)\in\mathcal{R}(b,b^{\prime})$''}.$

which is symmetric since we already proved that property (23) holds for all
paths containing $x$. By Lemma 4.1 there exists $b\in S_{x}^{1}\cap S_{x}^{2}$
where the representation $a(x)\in\mathcal{R}(b,b_{1})$ and
$a^{\prime}(x)\in\mathcal{R}(b,b_{2})$ are distinct. But the two paths pass
same set of edges at least up to vertex $x$, i.e. $\text{PCD}(b\prec
b_{1},b_{2})\geq\delta$, where $\delta$ is the distance from $b$ to $x$ along
the path $\mathcal{P}(b,b_{1})$. The execution of algorithm places one of the
labels in its respective path first. As a result, before any new label for $x$
is created, condition on line 19 will have been triggered and copied the label
to other paths. This is contradiction to the assumption of existence of two
different labels of $x$ in the set of reconstructed paths. ∎

Finally, for graphs with symmetric routing where the exact reconstruction
conditions are not met, similar discussion as in Theorem 2.1 proves the
uniqueness of the reconstruction result. The main point here is that cleaning
operations preserve the symmetric routing on the graph. Moreover the compliant
graph $\mathcal{N}^{C}$ satisfies the exact reconstruction conditions with
same PCD as the one for original graph $\mathcal{N}$.

###  4.1. Specialized algorithm for symmetric routing

We have shown that the reconstruction Algorithm 1 is universal: it covers both
the general non-symmetric network and also graphs with symmetric routing.
However, having the prior information that the routing on the network is
symmetric makes it possible to call the recursive function UpdatePath less.
This is due to the symmetric routing property that if an internal vertex $x$
is inserted in reconstruction path $\mathcal{P}(u,v)$ for $u,v\in V^{B}$ then
this vertex should also inserted in the reverse path $\mathcal{P}(v,u)$ with
appropriate distance from root $v$ (this is not generally true for non-
symmetric routing case). To take advantage of this feature we propose
Algorithm 2 as a specialized version of the reconstruction algorithm for the
graphs with symmetric routing.

Compared to the Algorithm 1, the new algorithm calls the recursive function
twice less (as can be seen by comparing the main loops of the two algorithms).
The change in the number of calls of reconstruction function is compensated by
adding line 14 in the new algorithm where the label of internal vertex which
is inserted in the given path will be inserted in the reverse one as well.

It should be pointed out that although less calls of main reconstruction
function makes the algorithm computationally more effective, from the point of
view of mathematical complexity (in terms of insertions of a vertex into a
reconstructed path), the two algorithms can be considered the same.

Algorithm 2 Reconstruction of a network graph with symmetric routing

1:for $b_{1},b_{2}\in V^{B}$ do $\triangleright$ Initialization

2: $\mathcal{R}(b_{1},b_{2})=[(b_{1},0),(b_{2},|\mathcal{P}(b_{1},b_{2})|)]$

3:end for

4:for $b_{1},b_{2},b_{3}\in V^{B}$ do $\triangleright$ Main Loop

5: create label $a$

6: $\delta=\text{PCD}(b_{1}\prec b_{2},b_{3})$

7: $\delta^{\prime}=\text{PCD}(b_{2},b_{3}\succ b_{1})$

8: UpdatePath($\mathcal{R}(b_{1},b_{2}),a,\delta,\delta^{\prime}$)

9:end for

10:Read off the graph from reconstructed paths $\mathcal{R}$. $\triangleright$
Return the result

11:

12:function UpdatePath($\mathcal{R}(u,v),a,\delta,\delta^{\prime}$)
$\triangleright$ Recursive Function

13: if $\exists\,(\cdot,\delta)\in\mathcal{R}(u,v)$ then return

14: insert $(a,\delta)$ into $\mathcal{R}(u,v)$

15: insert $(a,|\mathcal{P}(v,u)|-\delta^{\prime})$ into $\mathcal{R}(v,u)$

16: for $z\in V^{B}$ do

17: if $\operatorname{PCD}(u\prec v,z)\geq\delta$ then
UpdatePath($\mathcal{R}(u,z),a,\delta,\delta^{\prime}$)

18: if $\operatorname{PCD}(v\prec u,z)\geq\gamma^{\prime}$ then
UpdatePath($\mathcal{R}(v,z),a,|\mathcal{P}(v,u)|-\delta^{\prime},|\mathcal{P}(u,v)|-\delta$)

19: end for

20:end function

###  4.2. Reconstruction example

In the following example, we will show how having the prior information of
symmetric routing will help to uniquely reconstruct the network graph shown in
Fig. 17(a). The selected routing among the boundary vertices
$V^{B}=\\{b_{1},b_{2},b_{3}\\}$ follows the sequence
$\mathcal{P}(b_{i},b_{j})=[b_{i},x_{i},x_{j},b_{j}]$ for $i,j=1,2,3$. From the
measurement point of view, the PCD on the graph is represented as the set of
observed logical trees in Fig. 18.

If there is no information on the symmetry of routing, then we can not
conclude that $a_{1}=a_{4}$, $a_{2}=a_{5}$ and $a_{3}=a_{6}$. The resulting
reconstruction will be the graph appearing in Fig. 17(b).

Figure 17. (a) An example of a network graph. To avoid clutter, the edges with
no specified direction are assumed to go in both directions with the same
weight, (b) reconstructed network

We remark that such geometry is fairly realistic if we, for example, consider
the vertices $b_{j}$ to be internet service providers (ISPs) who are eager to
push the traffic addressed outside their network to other ISPs as soon as
possible. Still, the reconstruction does not match the graph we had
originally.

Figure 18. Representation of PCD on the network example through set of logical
source and receiver trees.

However, the reconstruction _is possible_ if we know a priori that the routes
are symmetric, as they are in this example. Then the paths going out of a
given source $b$ and the paths going to $b$ acting as the receiver have
exactly the same topology. This additional information allows us to identify
$a_{1}=a_{4}$, $a_{2}=a_{5}$ and $a_{3}=a_{6}$ in Fig. 17(b) and thus recover
the original graph. Since symmetric routing networks appear in applications,
we expect the optimized Algorithm 2 to be a practical value.

###  4.3. The effect of symmetric edge weights

Symmetric network graph for which both the routing on the graph and edge
weights are symmetric can be considered as a special class of general
networks. For this class of networks, similar to the graphs with symmetric
routing (see eq. 8), same set of edges are passed in the two reverse paths
$\mathcal{P}_{1}(u,v)$ and $\mathcal{P}_{2}(v,u)$. Additionally, the symmetric
edge weights property implies that for any vertex $x\in\mathcal{P}_{1}$, then
$|\mathcal{P}(v,x)|=|\mathcal{P}(u,v)|-|\mathcal{P}(u,x)|$. In other words,
path $\mathcal{P}_{2}$ is fully identified by the available information form
the path $\mathcal{P}_{1}$. This property of symmetric networks implies that
$\text{PCD}(v,w\succ u)=\text{PCD}(u\prec v,w)$, and as a result the
information from path correlation data encoded in the form of $(u\prec
v,w)$-junctions can be applied to identify the information for the $(v,w\succ
u)$-junctions. From the reconstruction point of view, same conditions are
required for exact reconstruction of graphs with symmetric edge weights as
discussed in previous sections and thereby Algorithm 2 can be applied for
reconstruction purposes.

##  5\. Conclusion and Future Work

In this paper, we solve the problem of reconstructing a network graph from the
measurements of PCD: the common length of any two paths sharing an origin or a
destination. It has been recently demonstrated that such measurements can be
collected from the ambient traffic, without encumbering the network with
specialized probing packets.

We establish necessary and sufficient conditions for a network graph to be
reconstructible and describe the reconstruction algorithm. When the
reconstruction is attempted on a graph violating those conditions, the result
of our algorithm is a minimal graph fitting the available data. More
precisely, among the network graphs that have the same PCD, the reconstructed
graph has the minimal number of links, no vertices of degree 2 and the minimal
average degree among vertices of degree 3 or more. Our framework is general
and no assumption is made on the symmetricity of routing or edge weights of
original graph is required. However, for graphs with symmetric routing less
restrictive conditions are shown to apply and a more specialized algorithm is
presented.

A possible direction for future work is to explore extending the class of
reconstructible graphs by making additional measurements. The most important
obstacle to overcome is the non-separability condition. Violation of this
condition leads to multiple representations, in the reconstructed graph, of a
single vertex. For example, for the network shown in Fig. 1, 2 and Fig. 3, the
application of the algorithm will result a network in Fig. 19. All internal
vertices except $u$ are recovered correctly, whereas the original vertex $u$
separates into two representative vertices $u^{\prime}$ and $u^{\prime\prime}$
in the reconstructed graph. In future work we will explore whether extending
the weight model to include vertex weights may allow correct identification of
the separable vertices. The motivation for such model is that load at a
switch, e.g. due to network attacks, may introduce performance degradation
that affects not just the traffic through a given link or router interface,
but all the packets traversing the switch. Finally, as mentioned in the
introduction, in work to be reported elsewhere [5], we explain how the methods
of the current paper can be extended to Path Correlation Data in which
sampling and measurement noise leads to inconsistencies in path weights
reported for different paths.

Figure 19. Separation of the internal vertex $u$ in the reconstructed network.

## References

  * [1] N. Alon, Y. Caro, I. Krasikov, and Y. Roditty.  Combinatorial reconstruction problems.  J. Combin. Theory Ser. B, 47(2):153–161, 1989.
  * [2] Vijay Arya and Darryl Veitch.  Sparsity without the complexity: Loss localisation using tree measurements.  In Robert Bestak, Lukas Kencl, Li Erran Li, Joerg Widmer, and Hao Yin, editors, NETWORKING 2012, pages 289–303, Berlin, Heidelberg, 2012\. Springer Berlin Heidelberg.
  * [3] M. I. Belishev.  Recent progress in the boundary control method.  Inverse Problems, 23(5):R1–R67, 2007.
  * [4] M. I. Belishev and N. Wada.  On revealing graph cycles via boundary measurements.  Inverse Problems, 25(10):105011, 21, 2009.
  * [5] G. Berkolaiko, N. Duffield, M. Ettehad, and K. Manousakis.  Manuscript in preparation.  2018\.
  * [6] L. Borcea, V. Druskin, A. V. Mamonov, and F. Guevara Vasquez.  Pyramidal resistor networks for electrical impedance tomography with partial boundary measurements.  Inverse Problems, 26(10):105009, 36, 2010.
  * [7] R. Caceres, N. G. Duffield, J. Horowitz, and D. F. Towsley.  Multicast-based inference of network-internal loss characteristics.  IEEE Transactions on Information Theory, 45(7):2462–2480, Nov 1999\.
  * [8] Margaret Cheney, David Isaacson, and Jonathan C. Newell.  Electrical impedance tomography.  SIAM Review, 41(1):85–101, 1999.
  * [9] D. B. Chua, E. D. Kolaczyk, and M. Crovella.  Network kriging.  IEEE Journal on Selected Areas in Communications, 24(12):2263–2272, Dec 2006.
  * [10] Francis J. Chung, Anna C. Gilbert, Jeremy G. Hoskins, and John C. Schotland.  Optical tomography on graphs.  Inverse Problems, 33(5):055016, 21, 2017.
  * [11] N. G. Duffield, J. Horowitz, F. Lo Presti, and D. Towsley.  Multicast topology inference from measured end-to-end loss.  IEEE Transactions on Information Theory, 48(1):26–45, Jan 2002\.
  * [12] Nick G. Duffield.  Network tomography of binary network performance characteristics.  IEEE Transactions on Information Theory, 52(12):5373–5388, 2006\.
  * [13] Nick G. Duffield and Francesco Lo Presti.  Network tomography from measured end-to-end delay covariance.  IEEE/ACM Trans. Netw., 12(6):978–992, 2004.
  * [14] Nick G. Duffield, Francesco Lo Presti, Vern Paxson, and Donald F. Towsley.  Network loss tomography using striped unicast probes.  IEEE/ACM Trans. Netw., 14(4):697–710, 2006.
  * [15] Steven N. Evans and Daniel Lanoue.  Recovering a tree from the lengths of subtrees spanned by a randomly chosen sequence of leaves.  Adv. in Appl. Math., 96:39–75, 2018.
  * [16] Gang Liang and Bin Yu.  Maximum pseudo likelihood estimation in network tomography.  IEEE Transactions on Signal Processing, 51(8):2043–2053, Aug 2003\.
  * [17] Harsh Singhal and George Michailidis.  Identifiability of flow distributions from link measurements with applications to computer networks.  Inverse Problems, 23(5):1821–1849, 2007.
  * [18] Renata Teixeira, Aman Shaikh, Tim Griffin, and Jennifer Rexford.  Dynamics of hot-potato routing in IP networks.  SIGMETRICS Perform. Eval. Rev., 32(1):307–319, June 2004.
  * [19] Y. Vardi.  Network tomography: Estimating source-destination traffic intensities from link data.  Journal of the American Statistical Association, 91(433):365–377, 1996.
  * [20] B. Yu, J. Cao, D. Davis, and S. Vander Wiel.  Time-varying network tomography: router link data.  In 2000 IEEE International Symposium on Information Theory (Cat. No.00CH37060), pages 79–, 2000.
  * [21] Yin Zhang, Matthew Roughan, Nick Duffield, and Albert Greenberg.  Fast accurate computation of large-scale ip traffic matrices from link loads.  In Proceedings of the 2003 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS ’03, pages 206–217, New York, NY, USA, 2003. ACM.