# Visual-Tactile Multimodality for Following Deformable Linear Objects Using
Reinforcement Learning

Leszek Pecyna1, Siyuan Dong2 and Shan Luo3 This work was supported by the
EPSRC project “ViTac: Visual-Tactile Synergy for Handling Flexible Materials”
(EP/T033517/1).1Leszek Pecyna is with the smARTLab, Department of Computer
Science, University of Liverpool, Liverpool L69 3BX, United Kingdom. Email:
<EMAIL_ADDRESS>Dong is with the Paul G. Allen School of
Computer Science & Engineering, University of Washington, Seattle, WA, USA.
Email<EMAIL_ADDRESS>Luo is with the Department of
Engineering, King’s College London, London WC2R 2LS, United Kingdom. Email:
<EMAIL_ADDRESS>
###### Abstract

Manipulation of deformable objects is a challenging task for a robot. It will
be problematic to use a single sensory input to track the behaviour of such
objects: vision can be subjected to occlusions, whereas tactile inputs cannot
capture the global information that is useful for the task. In this paper, we
study the problem of using vision and tactile inputs together to complete the
task of following deformable linear objects, for the first time. We create a
Reinforcement Learning agent using different sensing modalities and
investigate how its behaviour can be boosted using visual-tactile fusion,
compared to using a single sensing modality. To this end, we developed a
benchmark in simulation for manipulating the deformable linear objects using
multimodal sensing inputs. The policy of the agent uses distilled information,
e.g., the pose of the object in both visual and tactile perspectives, instead
of the raw sensing signals, so that it can be directly transferred to real
environments. In this way, we disentangle the perception system and the
learned control policy. Our extensive experiments show that the use of both
vision and tactile inputs, together with proprioception, allows the agent to
complete the task in up to 92% of cases, compared to 77% when only one of the
signals is given. Our results can provide valuable insights for the future
design of tactile sensors and for deformable objects manipulation.

##  I Introduction

Humans and animals explore and interact with their environment through a
variety of senses of a different modality. In some cases, we are able to
observe the integration of different modalities when one signal affects the
perception of other sensory inputs. An example of such multi-modal influence
is the McGurk effect [1], in which humans’ perception of particular sounds is
affected by visual cues. Touch and vision are especially used by humans during
object identification and manipulation. This can be seen in neuropsychological
studies on fMRI data, which shows that both visual and haptic signals are
processed in a cross-modal fashion during some of these tasks [2, 3].

In contrast, most of the artificial systems are based on a single modality
when performing their tasks and often different types of algorithms are
developed to approach particular modalities. As robots are operating in a more
complex and dynamic environments, it can be expected that the usage of variety
of sensing modalities will play more important role for them [4].

One of the situations when the environment becomes more complicated, and
multimodal perception might help in better comprehension of it, is
manipulation of flexible objects. As such, contour following of Deformable
Linear Objects (DLOs) is a common task performed by humans, e.g., cable
following. We perform this by grasping a cable between the thumb and the
forefinger and slide the fingers to the target position [5]. This task is
quite common in our daily life, for example, when untangling the cables or
when following the cable to find its plug-end.

Cable following can be a challenging task for artificial systems as the cable
shape is changing dynamically while the gripper is sliding. Moreover,
different cables/ropes can be characterized by different stiffness and
friction, and their starting shape might be complex and undetermined (kinks,
intersections, etc.). Due to these challenges, most of the research concerning
DLO manipulation uses some additional constraints, e.g., a object is placed on
a table [6, 7].

Figure 1: Manipulation goal: the gripper starts from the fixed end of the
rope/cable (on the left) and follows it, up to its tail end (on the right).

Training a Reinforcement Learning (RL) agent in a simulated environment, in
many aspects, is a desirable approach as the environment can be explored
through an extensive number of episodes without possibility of damaging a
robot. However, simulation of sliding and realistic grasping is a challenging
task itself. For this reason, most of prior works on flexible object
manipulation utilize a firm grasp, i.e., the section or a point of the object
is fixed to the gripper and cannot move in relation to it [8, 9]. In our work,
we cannot use such an approach as the gripper is sliding along the object,
instead we aim to modulate the grasping force while the hand is moving.

In this paper, we create an RL agent for a cable/rope following task in a
simulated environment and investigate how its behaviour can be boosted using
visual-tactile fusion, compared to using a single sensing modality. As shown
in Fig. 1, we have both visual and tactile perspectives of the state of the
deformable linear object in the gripper. The robot agent’s goal is to pick up
the object at its fixed end and follows it up to its tail end. We chose this
task, as sliding along DLOs is not well explored, especially when it comes to
simulation, and it is a good candidate for research concerning visual-tactile
synergy as both of the signals can provide useful information to complete the
task.

To the best of our knowledge, this is the first study to use both vision and
tactile inputs for the task of cable following. We used distilled information
as the observations of the agent, e.g., the object pose in both visual and
tactile perspectives, instead of the raw visual images or tactile data. In
this way, the trained agent can be directly transferred to real environments,
and the learned control policy can be disentangled from the perception system.
Through our extensive experiments, we find that when both vision and tactile
inputs, together with proprioception, are used, the agent can complete the
task (reach the end of the cable and hold it) in up to 92% of cases, compared
to the best result of 77% with a single sensory input used (for vision); and
when two signals were used – 89% (for vision and proprioception).

##  II Related Work

###  II-A Visual-Tactile Multimodality

Vision and touch are two main important senses used for object manipulation.
They have been widely used in robotics but, in most of the cases, with only
one sensory input used [10, 4]. In the resent years, there have been several
studies aiming to combine both of these inputs. Many of them concentrate on
sensing, rather than on manipulation, like feature sharing or feature
extraction [11, 12]. When it comes to object manipulation itself, even when
both of the senses are utilised, in many cases, one input type supports
another one, and is used in a specific sub-task, e.g., tactile sensing can
help to verify the contact with the object (several examples of that are
provided in [10]). Hence, they are not used simultaneously together.

It seems to be less common to extract features from the sensors and use them
together in the control scheme. In [13] multiple sensory inputs are integrated
in a grasping stability task (of mugs and bottles). In [14] in-hand object
location is estimated from joint sensors, and [15] covers object pose
estimation. The work presented herein follows the idea where the extracted
features are used simultaneously together.

###  II-B DLO Following

There have been several studies concerning contour following of rigid objects
that utilise vision [16] or tactile sensing [17, 18]. From the point of view
of flexible object following, that utilise tactile sensors, there are two
works [19] and [5]. The first [19] proposes a reinforcement learning approach
to close a deformable ziplock bag using BioTac sensors. The robot grasps and
follows the edge of the bag using a constant grasping force. The authors used
Contextual Multi-Armed Bandits (C-MAB) RL algorithm to train the robot to
close the bag in a discreet time steps with a maximum velocity of 0.5 cm/s
(trapezoidal velocity profiles). The second [5], which is the most relevant to
our work from the point of view of the task, presents a control framework that
uses a real-time tactile feedback from a GelSight sensor [20] to accomplish
the task of cable following. To achieve that, the authors designed a parallel
gripper with a servo motor actuator. Also, in their study, only the tactile
signal was used, but the gripping force was modulated. The authors did not use
the RL approach in that case, instead they used two controllers: PD – for
cable grip control, and LQR – for cable pose control. Compared to the
decoupled controllers in [5], in this work we control both the gripping force
and the end-effector pose simultaneously using the RL policy.

##  III Problem Statement

The goal of the presented DLO following task is to grasp the cable/rope at the
beginning end with the gripper, and follow it – using an appropriate grasping
force – to its tail end. The task should finish by holding the object close to
its finishing end. The beginning of the rope is firmly held by the second
gripper (it is attached to a point in space in the simulator). The problem is
illustrated in Fig. 1.

In many aspects, this task is similar to the one presented in [5]. There are,
however, many differences: we performed the training in a simulator (we are
planning to test our model on a real platform in the next stages of our work);
we use data from both vision and tactile sensors (in [5] only tactile signal
was used); our model uses an RL algorithm (compared to decoupled PD and LQR
controllers in [5]). Also, we do not perform re-grasping procedure111This
procedure was not not part of the controller task in [5] and it was used when
the gripper recognises it is loosing the cable and when the robot reaches its
workspace limits., instead, we finish training episode when the DLO falls from
the gripper. We assume no plug at the end of the cable (which allowed cable-
end recognition by the tactile sensor in [5]). Hence, in our case, we expect
the vision to play a principal role in the object-end identification. As our
task is conducted in the simulator, the parameters we chose can make the
object properties correspond to those of a cable or a rope, which can be much
softer than the cable used in [5].

Our model of DLO manipulation is defined as finite-horizon, discounted Markov
decision process (MDP) represented by a tuple of ($\mathcal{S}$,
$\mathcal{A}$, $p$, $\mathcal{R}$). The state space $\mathcal{S}$ and action
space $\mathcal{A}$ are assumed to be continuous. State transition probability
$p$, represents the probability density of the next state
$s_{t+a}\in\mathcal{S}$ given the current state $s_{t}\in\mathcal{S}$ and
action $a_{t}\in\mathcal{A}$. $\mathcal{R}$ is an immediate reward emitted by
the environment on each transition. The details about the agent’s actions and
state space (observations), as well as, the definition of a reward function
implementation are provided in the next section.

##  IV Methodology

In this section we present our methodology for implementation and usage of an
RL agent to solve the task of DLO following. We first describe the model, its
architecture, what observations it uses and what actions the agent can make.
Next, we present the reward function that is set to promote the behaviour of
reaching the object-end and staying there. Finally, we explain how our model
performance is evaluated.

###  IV-A Agent Description

In our study we use Soft Actor-Critic (SAC) [21, 22] that provides state-of-
the-art performance in continuous control tasks (like robotic manipulation).
SAC combines sample efficient off-policy method with ability to operate in a
continuous action and state spaces.

####  IV-A1 Model Architecture

Figure 2: DLO following task with the RL policy.

The model is composed of an actor network and a critic which is made of two
Q-value networks (to combat the problem of overestimation of Q-values).

Both Q-value networks and the policy network are MLPs with two hidden layers
of 1,024 neurons with ReLU activation function. The actor takes as an input
the state and outputs the mean and covariance for the Gaussian distribution
that represents the policy [22]. From that the action is sampled. The Q-value
network input is made of actions together with observation space and produces
single value (Q-value). The model’s general scheme of interaction with the
environment can be seen in Fig. 2.

####  IV-A2 Observations

In general, observations we use in our model can be divided in three
categories as shown in Fig. 3.

  * •

Kinematic (proprioceptive): it provides the information about position of the
gripper in the space ($x$ and $y$ coordinates) and its closure state (variable
from 0 to 1, where 0 corresponds to the situation where gripper is fully open
and 1 where it is fully closed). It is an array of 3 components:
$O_{G}=[x_{G},y_{G},c_{G}]$.

  * •

Tactile: Described more in Section V-B, it is composed of an angle and
position of the DLO in relation to the gripper: $O_{T}=[\vartheta_{T},y_{T}]$.

  * •

Visual: Described more in Section V-C, the visual input is composed of 4
components: information if the cable is visible on the right side of the
gripper, how confident is the angle, the angle, and the $y$ position of of the
cable in relation to the gripper: $O_{V}=[v_{V},q_{V},\vartheta_{V},y_{V}]$.

Figure 3: Illustration of state variables (observations) available for the
model.

####  IV-A3 Actions

As the gripper is supposed to move freely in the $x$-$y$ space, our action
array is composed of target displacements in these directions. Apart from
that, the agent is able to modify the closing force of the grip hence the
array of action is composed of: $A=[\Delta x_{g},\Delta y_{g},c_{G}]$. As the
time step is constant in the simulation (set to 0.01 s) these $\Delta x$ and
$\Delta y$ values directly correspond to velocities of the gripper. The
simulator allows to set how many time steps are executed after each action
step, in our case this was set to 8. We limit these values (by scaling the
output of the agent) to keep the speed of the gripper in a feasible range for
the real robot and also to assure better RL training. After some preliminary
experiments we chose maximal values of $\Delta x$ and $\Delta y$ to be 0.0025,
which corresponds to the velocity of 0.25 m/s.

####  IV-A4 Reward

Our reward can be represented by partial rewards and defined as:

$R_{t}=\begin{cases}R_{move}+R_{end},&\text{if }n_{h}\neq 0\\\
P_{fall},&\text{if }n_{h}=0\end{cases}$

where $R_{move}$ is a reward for moving towards the end of the DLO; $R_{end}$
is the reward for being close to the end of the rope; $P_{fall}$ is the
penalty for dropping it; $n_{h}$ is a number of particles being held by the
gripper.

The partial rewards are defined as follows:

$R_{move}=\alpha_{move}(d_{t}-d_{t-1})$

where $\alpha_{move}$ is the weight of that reward, $d_{t}$ is the distance
(in meters) at the current time step $t$. In the simulation, it is calculated
as:

$d_{t}=\frac{p_{i}L_{c}}{n_{c}}$

where $p_{i}$ is the average value of indexes of particles being held by the
gripper, $L_{c}$ is the length of the rope, and $n_{c}$ is number of particles
that the rope is made of.

$R_{end}$ is given only when the gripper is closer than 20 particles from the
end of the object and it is increasing linearly when fingers approach the
end222Quadratic function was also tested..

$R_{end}=\begin{cases}\alpha_{end}(p_{i}+20-n_{c}),&\text{if
}p_{i}>n_{c}-20\\\ 0,&\text{otherwise}\end{cases}$

$P_{fall}$ is a constant value,, together with $\alpha_{move}$ and
$\alpha_{end}$, was chosen through a hyperparameter search. These values were
set to $P_{fall}=-0.5$, $\alpha_{move}=10$, and $\alpha_{end}=\frac{1}{20}$.

####  IV-A5 Evaluation Metrics

We evaluate the performance of our model using several metrics. One of them is
to classify each of the completed episodes in one of the categories:

  * •

Hold the end – the gripper follows the DLO till its end, it stays there and
holds the object. This is the goal behaviour. We defined being at the end as
the situation when the gripper holds any of the last 10 particles.

  * •

Stop before – the gripper did not reach close to the end but it did not drop
the object.

  * •

Reach end but drop – the gripper reached the end of the DLO (last 10
particles) but failed to keep the object.

  * •

Drop before – the gripper dropped the DLO earlier, without reaching its end.

Apart from this classification, two more metrics are used:

  * •

Time spent at the end – we check how long (i.e., how many time steps) the
gripper spends at the end of the DLO (at any of 10 last particles).

  * •

How far it goes – we check how close to the end of the DLO gripper reached (we
measure this distance from the end of the object as the length of the rope is
randomised). The distance is measured in particles.

##  V Experiment Setup

We simplified our observations to scalars (e.g. angles and positions). This
allows relatively simple assessment of what piece of information is useful.
Ensuring that the observations are not influenced by the process of
information extraction from the real images. This approach could potentially
help us to avoid domain shift in the future Sim-to-Real transfer. It also
makes this method more general, allowing its application with different types
of sensors.

###  V-A Simulation

For a simulator we use Nvidia Flex – a particle based simulation technique
[23, 24], wrapped in SoftGym [9] \- which is a set of benchmarks. SofGym
provides a set of simulated environments and agents, it uses PyFlex [25] that
provides Python interface for Nvidia Flex, and Gym [26], a toolkit for
developing and comparing reinforcement learning algorithms.

Figure 4: Frames from the simulated environment. On the left – the beginning
of the task where the cable falls freely; on the right – the gripper finished
the task and holds the cable’s end.

We constructed a new task and environment in SoftGym based on “rope flatten”
task. We assumed the usage of a camera and a gripper with tactile sensors,
based on that we amend the environment. We use two capsule-shape objects to
simulate GelTip sensors [27]. We adjusted how the gripper can move and
introduced a new way of gripping rope’s (or a cable’s) particles (Section
V-D). The screenshots from the simulator, with an example of the rope
configuration at the beginning and at the end of the task, can be seen in Fig.
4.

###  V-B Tactile sensors

The sensor provides us with an angle $\vartheta_{T}$ of the cable with the
gripper’s $x$ axis as presented in Fig. 3, and with the position of the cable
in the $y$ direction (along the finger). In the case of GelSight sensor, these
angles and positions can be obtained using the algorithms described in [20].
We use particles’ positions (between gripper’s fingers) in the simulator to
calculate these values (we fit the line to the centres of these particles and
use its angle and its intersection with $y$ axis). In the case of the real
sensor, the precision depends on the normal force, this is well illustrated in
[5] (for the GelSight sensor), where the controller is adapting the gripping
force taking into account tactile quality. Bearing in mind that in some of the
experiments presented herein we added a random noise – proportional to the
gripper closure – to the measured angle and position.

$\vartheta_{T}=\vartheta_{T,nom}+(1-c_{G})\vartheta_{noise},$
$y_{T}=y_{T,nom}+(1-c_{G})y_{noise},$

where $\vartheta_{noise}$ and $y_{noise}$ are sampled from the normal
distributions with different standard deviations (depending on assumed
sensitivity); $\vartheta_{T,nom}$ and $y_{T,nom}$ are the nominal values.
These are calculated based on the positions of the DLO particles between the
grippers fingers.

There are two reasons why we imitate the finger-like sensors in our
simulations. First, we are planning to use GelTip sensors in the future
experiments with the robot. Second, due to the nature of the simulator – a
cable/rope is made of particles connected with springs in the Nvidia Flex
environment – rectangular-shape fingers are causing unwanted behaviour of the
rope which is difficult to overcome (in general, the corner of the sensor was
getting between particles and the gripper was pulling the cable), hence, more
rounded shape is more appropriate for this simulation task.

###  V-C Camera

Figure 5: Possible occlusions in rope visibility caused by the gripper
(capsule in the simulation).

We assumed the usage of a top view camera. Similarly as with tactile data, we
extract and use the position and angle of the rope from the camera image. We
use the position and angle of the rope on the right from the gripper (in the
direction of motion) as presented in Fig. 3 – $\vartheta_{v}$ and $y_{v}$
variables. The camera’s top view can be subjected to gripper and cable
occlusions, and not always the position and angle of the cable are visible in
the image as illustrated in Fig. 5 (top row). Hence, we also include the
information if the cable is visible from the right – $v_{v}$, and how far
continuously it goes to the right – the confidence about the angle – $q_{v}$.

###  V-D Gripper

The gripper can move in $x$ and $y$ directions and close or open the grip,
similarly as in [5]. We implemented the process of gripping with variant
gripping force in the simulated environment. This task is not trivial and in
most simulations it is implemented by attaching the object being held to the
gripper without taking into account possibility of sliding or such factors as
friction. This was the case of the original environments implemented in
SoftGym [9]. As the rope is in fact simulated as particles connected by
springs, simple decreasing of the gap between two capsules (that we used to
represent the gripper’s fingers) was causing unnatural behaviours – the
gripper was getting caught between the particles holding them firmly.

Instead of doing that, our intention was to modify the friction between the
DLO and the fingers. This, on the other hand, was not straight forward because
the friction parameters are global in the simulator. To this end, we modify
the value of the inverse mass of the rope’s particles that were between the
fingers, and amended their positions according to the grippers’ movement. This
is similar to the approach in the original environments of the SoftGym, where
the inverse mass was set to 0 and the position was set to follow the gripper –
causing that the particle was fully attached to it.

Assuming that the closing action is scaled between 0 and 1 and that the
gripper changes the friction (or rather the inverse mass of hold particles)
when that value is above 0.5 but the full closure appear at 0.9, the inverse
mass can be expressed by the equation:

$w_{p}=max(2.25w_{p,nom}-2.5w_{p,nom}max(c_{G},0.5),0)$

where $w_{p,nom}$ is the nominal value of the inverses mass of DLO particles
used in the simulator.

###  V-E Randomisation

To allow our agent to operate in different environments we randomised variety
of parameters in the simulation. This randomisation makes the agent to better
generalize the task and could allow Real-to-Sim transfer even when the real
environment, e.g., cable parameters, are quite different from these in the
simulation.

We randomised:

  * •

Length of the cable (uniform, from 30 to 60 particles);

  * •

DLO starting position – we pick the rope in a random place and place it in a
random location, we repeat that 4 times before each episode;

  * •

DLO stretch stiffness (uniform, from 0.8 to 1.4);

  * •

Bending stiffness (uniform, from 0.8 to 2.4);

  * •

Friction coefficient (uniform, from 0.04 to 0.3);

The ranges of these parameters were chosen empirically in the simulator.
Changing some of them in a bigger range would require to decrease the
simulation step, which extends the training time. In these ranges the
simulation was stable and at the same time we could observe different
interactions between the gripper and the DLO.

###  V-F Training the agent

In the training, we used a batch size of 128, learning rates for actor and
critic of 0.001, 1,000 initial steps (with no agent updates), horizon length
for each episode of 150 steps, and the maximum number of training steps was
set to 50,000. The reward discount was set to $\gamma=0.99$.

##  VI Results

To test the proposed methods and investigate how different sensory inputs
contribute to the rope following task, we conducted multiple experiments.
First, we compared the behavior of the agent and its performance when only one
of the signals is provided. Next, we conducted similar experiments using two
out of three inputs. Following that we performed the ablation studies where we
trained the agent with all three inputs but we tested it excluding one of the
signal. At the end, we check the agent’s performance when different
sensitivity of the tactile sensor is used – different randomisation when the
gripper is open.

All the results are collected in such a way that every 200 training steps we
evaluate agent performance using 10 random environments (with a random DLO
properties and configuration). We repeat the whole training 10 times for
different random seeds (this way we train 10 different independent agents).
The results presented in the paper are the average values from these 10
independent training sessions together with 95% confidence margin. The curves
were additionally smoothed using a windows of size 5 (the average of 5
following results).

###  VI-A Training Performance When a Single Sensory Input is Provided

Figure 6: Episode outcome. Each subplot corresponds to a different sensory
input: tactile, kinematic, vision, or all. The curves were collected from 10
independent training sessions, shading represents 95% confidence range. Figure
7: Agent’s performance evaluation when one type of the input is used. Each
subplot corresponds to a different metrics (episode reward and percentage of
targeted outcome: Hold the end were also included). The curves were collected
from 10 independent training sessions, shading represents 95% confidence
range.

We first analyze the results obtained when only one of the inputs was used
(tactile, visual or kinematic). These are compared with the results when all
three signals are provided together. Fig. 6 shows the outcome of RL agent
behaviour; how often the task was finalized in a most desired way: Hold the
end; or how frequently other 3 outcomes were observed (described more in
Section. IV-A5). We can see that the behaviour of the agent changes
significantly depending on the input signal. Only the vision input allows the
model to stop and hold the DLO at the appropriate moment (Hold the end). This
was expected, as both T and K signals do not hold information that allows to
identify the end of the object. This is, however, improved when all the
signals are used together, in that case, the agent is able to obtain much
better performance faster. As the kinematic signal does not provide any
information about the DLO itself the agent prefers to not follow along the
object and stops prematurely. Simulations with a tactile input show similar
behaviour but the agent relatively often tends to follow the object till the
end and drops it after that.

The results from particular modalities are compared more directly in the Fig.
7. Each curve represents different type of inputs and each subplot shows
different type of metrics. In the figure, we also included episode collective
reward and the most desired outcome: Hold the end. The best mean results for
each modality are 12%, 11%, 77% and 92% (Hold the end), respectively for T, K,
V and All333As we mentioned before, the results in figures are smoothed for
better readability so listed results might not be directly visible..

These results allow us to make a clear conclusion that the agent with a visual
input outperforms the agents trained with other signal types. However, it is
also clear that when other inputs are included this performance is improved.
We can also see that both kinematic and tactile inputs help in sliding along
DLO (How far it goes subplot)444This edge following is fully possible with a
tactile signal but it is not preferred by the agent due to the penalty for
cable dropping which happens when it reaches the end..

###  VI-B Training Performance When Two Sensory Inputs Are Provided

Figure 8: Episode outcome. Each subplot corresponds to a different combination
of sensory input: tactile and kinematic, vision and kinematic, tactile and
vision, or all. The curves were collected from 10 independent training
sessions, shading represents 95% confidence range. Figure 9: Agent’s
performance evaluation when two types of inputs are used. Each subplot
corresponds to a different metrics (episode reward and percentage of targeted
outcome: Hold the end were also included). The curves were collected from 10
independent training sessions, shading represents 95% confidence range.

Figures 8 and 9 are created in the same manner as the figures in the earlier
subsection. As expected, we can observe better performance of the training
when two sensory inputs are used. When we compare the V subplot from Fig. 6
with subplots V + K and T + V presented here, we can see that each of the
inputs (T or K) provides some improvement.

Again, we can see that the visual signal plays a crucial role and only when it
is included in the input the agent is more often successfully performing Hold
the end behaviour. The best mean results for each paired-modalities are 16%,
89.0%, 77% and 92% (Hold the end), respectively for T + K, V + K, T + V and
All.

In the case of How far it goes metric, any combination that contains visual
input (V + T or T + V) allows to achieve relatively high performance, similar
to the one with All signals.

###  VI-C Ablation studies

Figure 10: Performance of the agent when trained with all of the sensory
inputs but some of the inputs were not provided in the testing phase. On the
left subplot – episode reward in a particular case; on the right – comparing
ablation studies (when tested without T or V) with all signal case and with
the case when the model was trained from the beginning without one of the
inputs. Error bars and shading correspond to 95% confidence range.

We trained the agent using all of the inputs (T + V + K), however, whenever
the model was tested we did not provide one of the signals. The performance of
the agent is presented in the left subplot in Fig. 10, where we show the mean
value of collective episode reward. We can see that removal of V signal caused
the biggest drop in performance. Ablation of T input, on the other hand, was
insignificant and the results are almost the same as with that signal. This
implies that the tactile input is in some way complementary.

To investigate the influence of the tactile signal, we present our ablation
studies on a training development plot (Fig. 10, top right). The curve with
removed signal is obtained in a way that the the agent is trained with all
inputs but every 200 steps is tested with a tactile-free signal555We use the
same agent for tactile-free and all signals tests, hence, the curve has a very
similar characteristic. The difference in performance is more visible when
checking other metrics.. We can see that removal of T input has practically no
impact on the reward. These results were compared with the session where
tactile input was not used at all during the training. The results are
interesting as we can see that the model which has access to additional
tactile information in the training phase can learn faster and obtain better
performance than the model trained without tactile signal T (both agents are
tested without T input). Possible explanation is that the DLO angle
information (which is more certain in the case of tactile input) is useful in
the training process to interpret and take advantage of the position
information. Similar observation is even more evident when the visual signal
is removed (Fig. 10, bottom right). The agent that was trained with all
signals performs much better without visual input compared to the model that
was trained without vision.

###  VI-D Tactile Sensitivity Study

Figure 11: Performance of the agent (episode reward) when different
sensitivity of the tactile sensor was assumed (sensitivity vary depending on
the grasping force). Error bars correspond to 95% confidence range.

As described in Section V-B, we took into account in our studies the impact of
tactile sensor sensitivity. We included the random noise in the tactile input
that was equal to zero when the gripper was using maximum gripping force and
was increasing with gripper opening. Fig. 11 shows the results for different
sensitivity and when the tactile input is not included at all. Full
randomisation when no grip corresponds to the situation where the standard
deviation of aforementioned randomisation was set such high that angle should
be practically not useful to estimate the real orientation of the rope
($\sigma$ in that case was set to 0.5) and position should be very unreliable
(we set $\sigma$ to 0.002). In that case, we can see that the agent was not
able to learn to use that input (during the 50,000 steps training) – the
reward was as good as in the case of lack of tactile input. However, we can
observe improvement of the agent performance when partial randomisation was
used if the K input was provided together with T. This shows that such less
sensitive input can be used by the agent but only with the information about
the gripper’s closure, which allows to evaluate the reliability of the tactile
signal.

##  VII Conclusions and Future Works

In this paper, we investigated the use of both vision and tactile inputs in
completing a task of following deformable linear object. We introduced a
benchmark in simulation and studied how an RL agent’s behaviour can be boosted
using visual-tactile fusion, compared to using single sensing inputs. We also
conducted ablation studies where the agent, trained with a larger amount of
signals, was tested with fewer inputs. Our results show the importance of
multimodality and each sensing modality plays a different role in completing
the task. In our particular task, the vision played a crucial role in
finishing the task and finding the end of the cable. Without vision the agent
prefers to finish the movement prematurely. We also see the importance of
kinematic input which allows the agent to know where it is. Tactile input in
some aspect was redundant with visual input. However, as we showed, it was
also important for the agent to go further along the cable. The importance of
the tactile signal is more significant when vision is not available (in real-
life situations this can be quite common due to obstacles).

The results presented in this paper provide useful insights for future designs
of tactile sensors and for deformable objects manipulation. The presented
approach can provide guidance in the process of simulating tasks where sliding
or touching of flexible materials is required. One of future works will be to
adapt the trained agent on a real platform. Thanks to the usage of the
distilled information, such transfer of knowledge should be much less affected
by a domain shift. The research also has potential to be extended to more
complex tasks, where we manipulate other objects (e.g., a cloth – edge
following) or we train the agent to achieve a different goal (e.g., wrapping a
cable around the pin).

## References

  * [1] H. McGurk and J. MacDonald, “Hearing lips and seeing voices,” _Nature_ , vol. 264, no. 5588, pp. 746–748, 1976.
  * [2] T. W. James, G. K. Humphrey, J. S. Gati, P. Servos, R. S. Menon, and M. A. Goodale, “Haptic study of three-dimensional objects activates extrastriate visual areas,” _Neuropsychologia_ , vol. 40, no. 10, pp. 1706–1714, 2002\.
  * [3] R. Blake, K. V. Sobel, and T. W. James, “Neural synergy between kinetic vision and touch,” _Psychological science_ , vol. 15, no. 6, pp. 397–402, 2004\.
  * [4] S. Luo, N. F. Lepora, U. Martinez-Hernandez, J. Bimbo, and H. Liu, “Vitac: Integrating vision and touch for multimodal and cross-modal perception,” _Frontiers in Robotics and AI_ , vol. 8, 2021.
  * [5] Y. She, S. Wang, S. Dong, N. Sunil, A. Rodriguez, and E. Adelson, “Cable manipulation with a tactile-reactive gripper,” _The International Journal of Robotics Research_ , vol. 40, no. 12-14, pp. 1385–1401, 2021.
  * [6] M. Yan, Y. Zhu, N. Jin, and J. Bohg, “Self-supervised learning of state estimation for manipulating deformable linear objects,” _IEEE robotics and automation letters_ , vol. 5, no. 2, pp. 2372–2379, 2020.
  * [7] J. Zhu, B. Navarro, P. Fraisse, A. Crosnier, and A. Cherubini, “Dual-arm robotic manipulation of flexible cables,” in _2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2018, pp. 479–484.
  * [8] Y. Li, D. Xu, Y. Yue, Y. Wang, S.-F. Chang, E. Grinspun, and P. K. Allen, “Regrasping and unfolding of garments using predictive thin shell modeling,” in _2015 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2015, pp. 1382–1388.
  * [9] X. Lin, Y. Wang, J. Olkin, and D. Held, “Softgym: Benchmarking deep reinforcement learning for deformable object manipulation,” in _Conference on Robot Learning_. PMLR, 2021, pp. 432–448.
  * [10] S. Luo, J. Bimbo, R. Dahiya, and H. Liu, “Robotic tactile perception of object properties: A review,” _Mechatronics_ , vol. 48, pp. 54–67, 2017.
  * [11] W. Yuan, S. Wang, S. Dong, and E. Adelson, “Connecting look and feel: Associating the visual and tactile properties of physical materials,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2017, pp. 5580–5588.
  * [12] S. Luo, W. Yuan, E. Adelson, A. G. Cohn, and R. Fuentes, “Vitac: Feature sharing between vision and tactile sensing for cloth texture recognition,” in _2018 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2018, pp. 2722–2727.
  * [13] Y. Bekiroglu, D. Song, L. Wang, and D. Kragic, “A probabilistic framework for task-oriented grasp stability assessment,” in _2013 IEEE International Conference on Robotics and Automation_. IEEE, 2013, pp. 3040–3047.
  * [14] P. Hebert, N. Hudson, J. Ma, and J. Burdick, “Fusion of stereo vision, force-torque, and joint sensors for estimation of in-hand object location,” in _2011 IEEE International Conference on Robotics and Automation_. IEEE, 2011, pp. 5935–5941.
  * [15] J. Bimbo, P. Kormushev, K. Althoefer, and H. Liu, “Global estimation of an object’s pose using tactile sensing,” _Advanced Robotics_ , vol. 29, no. 5, pp. 363–374, 2015.
  * [16] F. Lange, P. Wunsch, and G. Hirzinger, “Predictive vision based control of high speed industrial robot paths,” in _Proceedings. 1998 IEEE International Conference on Robotics and Automation (Cat. No. 98CH36146)_ , vol. 3. IEEE, 1998, pp. 2646–2651.
  * [17] N. Chen, H. Zhang, and R. Rink, “Edge tracking using tactile servo,” in _Proceedings 1995 IEEE/RSJ International Conference on Intelligent Robots and Systems. Human Robot Interaction and Cooperative Robots_ , vol. 2. IEEE, 1995, pp. 84–89.
  * [18] B. Ward-Cherrier, N. Pestell, L. Cramphorn, B. Winstone, M. E. Giannaccini, J. Rossiter, and N. F. Lepora, “The tactip family: Soft optical tactile sensors with 3d-printed biomimetic morphologies,” _Soft robotics_ , vol. 5, no. 2, pp. 216–227, 2018.
  * [19] R. B. Hellman, C. Tekin, M. van der Schaar, and V. J. Santos, “Functional contour-following via haptic perception and reinforcement learning,” _IEEE transactions on haptics_ , vol. 11, no. 1, pp. 61–72, 2017.
  * [20] W. Yuan, S. Dong, and E. H. Adelson, “Gelsight: High-resolution robot tactile sensors for estimating geometry and force,” _Sensors_ , vol. 17, no. 12, p. 2762, 2017.
  * [21] T. Haarnoja, A. Zhou, P. Abbeel, and S. Levine, “Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor,” in _International conference on machine learning_. PMLR, 2018, pp. 1861–1870.
  * [22] T. Haarnoja, A. Zhou, K. Hartikainen, G. Tucker, S. Ha, J. Tan, V. Kumar, H. Zhu, A. Gupta, P. Abbeel, _et al._ , “Soft actor-critic algorithms and applications,” _arXiv preprint arXiv:1812.05905_ , 2018.
  * [23] M. Müller, B. Heidelberger, M. Hennix, and J. Ratcliff, “Position based dynamics,” _Journal of Visual Communication and Image Representation_ , vol. 18, no. 2, pp. 109–118, 2007.
  * [24] M. Macklin, M. Müller, N. Chentanez, and T.-Y. Kim, “Unified particle physics for real-time applications,” _ACM Transactions on Graphics (TOG)_ , vol. 33, no. 4, pp. 1–12, 2014.
  * [25] Y. Li, J. Wu, R. Tedrake, J. B. Tenenbaum, and A. Torralba, “Learning particle dynamics for manipulating rigid bodies, deformable objects, and fluids,” _arXiv preprint arXiv:1810.01566_ , 2018.
  * [26] G. Brockman, V. Cheung, L. Pettersson, J. Schneider, J. Schulman, J. Tang, and W. Zaremba, “Openai gym,” 2016.
  * [27] D. F. Gomes, Z. Lin, and S. Luo, “Geltip: A finger-shaped optical tactile sensor for robotic manipulation,” in _2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2020, pp. 9903–9909.


# Reconstruction of geometric random graphs with the Simple algorithm

Clara Stegehuis111Department of Electrical Engineering, Mathematics and
Computer Science, University of Twente, The Netherlands $\&$ Lotte
Weedage††footnotemark:

###### Abstract

Graph reconstruction can efficiently detect the underlying topology of massive
networks such as the Internet. Given a query oracle and a set of nodes, the
goal is to obtain the edge set by performing as few queries as possible. An
algorithm for graph reconstruction is the Simple algorithm [16], which
reconstructs bounded-degree graphs in $\tilde{O}(n^{3/2})$ queries. We extend
the use of this algorithm to the class of geometric random graphs with
connection radius $r\sim n^{k}$, with diverging average degree. We show that
for this class of graphs, the query complexity is $\tilde{O}(n^{2k+1})$ when
$k>3/20$. This query complexity is up to a polylog$(n)$ term equal to the
number of edges in the graph, which means that the reconstruction algorithm is
almost edge-optimal. We also show that with only $n^{1+o(1)}$ queries it is
already possible to reconstruct at least $75\%$ of the non-edges of a
geometric random graph, in both the sparse and dense setting. Finally, we show
that the number of queries is indeed of the same order as the number of edges
on the basis of simulations.

Keywords: Random geometric graphs, randomized algorithms, graph reconstruction

##  1 Introduction

Given only the set of nodes of a graph, how can one, with as little
information as necessary, reconstruct all edges in this graph? This problem is
called the _graph reconstruction problem_ : how to fully reconstruct a graph
using a minimal number of queries. The exact nature of the query oracle used
in these problems can vary, but in general such oracles have a node or a pair
of nodes as input and the output gives some information on this node or pair
of nodes.

A motivating example for the graph reconstruction problem is the discovery of
the topology of the Internet [17] at different levels, such as the autonomous
systems (AS) level or the router level. The discovery of these topologies is
necessary for e.g. routing purposes or assessing the robustness of the
network. However, as the network is huge and links might change over time, it
is infeasible to execute too many time- and energy-consuming queries on the
network. Thus, it is desirable to use as few queries as possible to
reconstruct the network. As the internet showcases a large spatial dependency
[5], we aim to understand how the presence of an underlying network geometry
can help in fast reconstruction.

A popular method to obtain the topology of the Internet is  traceroute. This
method reveals the path that a packet chooses from source to destination over
the internet. By performing traceroute queries from sufficiently many
different sources and destinations, one can reconstruct the complete network
topology [17]. In general, traceroute resembles a _shortest-path_ oracle that
reveals the shortest path between a queried source and target. However, while
traceroute might provide the full shortest path, often this information is not
available due to e.g. privacy [14] or the size of the network and the paths
[4]. In these cases, often a distance oracle, where only the length of the
shortest path is given, is more realistic and reliable.

The Simple algorithm, introduced in [16], is a randomized algorithm that can
fully reconstruct general bounded-degree graphs on $n$ nodes in
$\tilde{O}(n^{5/3})$222$\tilde{O}(f(n))=O(f(n)\text{polylog}(n))$ distance
queries. In this paper, we extend the use of the Simple algorithm, until now
only valid for sparse, bounded-degree graphs with a maximum degree up to
$O(\log(n))$, to the class of geometric random graphs with growing average
degrees. We show how the Simple algorithm can reconstruct geometric random
graphs (GRGs) on $n$ nodes with connection radius $r\sim n^{k}$ with a query
complexity of $\tilde{O}(n^{2k+1})$ when $\frac{3}{20}\leq k<\frac{1}{2}$ and
$\tilde{O}(n^{3/2-4k/3})$ for smaller $k$. Thus, for dense geometric random
graphs with $k\geq\frac{3}{20}$, this algorithm results in an almost _optimal_
reconstruction: the query complexity for reconstruction is of the same order
(multiplied by a log-term) as the number of edges. The results presented in
this paper provide the first bounds on query complexity for reconstruction of
dense graphs with unbounded maximum degree. Moreover, we show that for both
dense and sparse geometric random graphs, the first step of the Simple
algorithm - where all nodes are queried with a small set of seed nodes -
already identifies $75\%$ of the non-edges of the graph.

The set-up of this paper is as follows. In Section 2 we provide an overview of
the literature on graph reconstruction, followed by a discussion of the Simple
algorithm and the random graph model we will use throughout this paper in
Section 3. Then, in Section 4 we prove our main results on the number of
queries needed to reconstruct geometric graphs and prove our results.

##  2 Related work

### Query oracles.

An important aspect of the graph reconstruction problem is the choice of
oracle. Some of these queries classify as _global_ query oracles: they receive
as input a node and output all shortest paths [4, 20] or all distances to
other nodes [13]. _Local_ query oracles, such as the shortest-path oracle [18]
and the distance oracle [14], receive as input a node pair and output the
nodes on the shortest path or the length of the shortest path between this
node pair, respectively. In a similar manner, the _kth-hop_ oracle [2] outputs
the $k$-th node on the shortest path between a given node pair, and the
_betweenness_ oracle [1] has a third input node, and tells whether this node
lies on the shortest path between the other two nodes. Lastly, the _maximal
independent set_ oracle receives a subset of nodes as input and outputs any
maximal independent set in the induced subgraph of this set of nodes [15].

Motivated by the reconstruction of Internet networks, our focus is on the
local type of oracle: the distance oracle. In the rest of this paper,
therefore, we focus only on distance queries.

### Graph reconstruction algorithms.

A trivial upper bound reconstructing general graphs using the distance oracle
is $O(n^{2})$. Indeed, in the worst case examples of a complete graph or an
empty graph, all pairs of nodes need to be queried [18]. Without knowledge of
the graph structure, graph reconstruction therefore always takes $O(n^{2})$
queries in the worst case.

Most results about graph reconstruction are therefore on special cases of
graph classes that do not contain these worst-case example. Specifically,
bounded-degree, connected graphs have been investigated thoroughly. The
algorithm proposed in [14] requires $\tilde{O}(n^{3/2})$ queries, given a
maximum degree $\Delta$ of $O(\text{polylog}(n))$. This randomized algorithm
is based on Voronoi cell decomposition: nodes in the graph are grouped into
equal-sized clusters that then can be reconstructed independently. In [16] the
authors propose a simpler algorithm that uses in expectation $\tilde{O}(n)$
queries in random $\Delta$-regular graphs and $\tilde{O}(n^{5/3})$ queries in
general bounded degree graphs. In case of bounded degree chordal graphs, there
exist reconstruction algorithms that have a query complexity of
$O(\Delta^{2}n\log^{2}(n))$[19]. For the class of $k-$chordal graphs - graphs
without cycles of length at least $k+1$ \- an exact reconstruction algorithm
is given in [3] with a query complexity of $O(n\log(n))$.

A common element of the above-mentioned graphs is that the considered graphs
have bounded degree, often contain only a few cycles, and have no underlying
geometry. However, real-world networks are often defined based on their
underlying geometry, such as Internet networks on the _Point of Presence_
(PoP) level or router level [17].

Lastly, graph reconstruction often goes hand-in-hand with graph verification
[14]. In reconstruction, the goal is to find all edges and non-edges of a
graph $\mathcal{G}$. For verification one obtains a graph $\hat{\mathcal{G}}$
in the same class of graphs as $\mathcal{G}$, and one has to verify that it is
equal to $\mathcal{G}$. Graph verification is important for example in error
detection and detecting anomalous network behaviour [8]. A trivial upper bound
on the verification complexity is the reconstruction complexity, as one can
always reconstruct the entire graph $\mathcal{G}$ to verify whether the two
graphs are the same. For some specific graphs however, graph verification has
a lower query complexity than graph reconstruction. For graphs with a maximum
degree $\Delta\leq n^{o(1)}$, the greedy algorithm in [14] verifies graphs
using the distance oracle in $O(n^{1+o(1)})$, while the reconstruction
algorithm has a query complexity of $\tilde{O}(n^{3/2})$. Similarly,
verification of chordal graphs with maximum degree $\Delta$ can be done in
$O(\delta^{2}n\log(n))$ distance queries compared to
$O(\delta^{2}n\log^{2}(n))$ for reconstruction [19].

### Graph embedding.

Related to network reconstruction is the retrieval of the locations of the
nodes in a network with underlying geometry, given only the edge list. Finding
an embedding of a graph can be seen as the opposite of graph reconstruction as
edges are given and the objective is to find locations of the nodes. In [11,
10, 9] the authors propose algorithms to retrieve the geometric embedding of
the nodes in a geometric random graph (without knowing the original embedding)
up to a displacement of $O(\sqrt{\log(n)})$ for dense graphs. Contrary to the
graph reconstruction problem, here the adjacency matrix is known, while the
locations of the nodes and the connection radius $r$ are unknown. The
localization algorithm proposed in [11] is based on computing an estimate for
$r$, which is then used to approximate the Euclidean distance based on the
graph distance. However, while these algorithms give a precise location of the
node, they all require knowledge of the edge list of the graph. Therefore,
such a localization algorithm cannot be used for graph reconstruction.

##  3 Model and main results

In this paper, we consider a geometric random graph $\mathcal{G}(n,r)=(V,E)$
consisting of $n=|V|$ nodes. Nodes that are located within radius $r$ of each
other connect, considering a Euclidean distance measure. The locations of the
nodes $v\in V$ are distributed by a Poisson point process (PPP) $\Phi$ with
intensity 1 on a two-dimensional $[0,\sqrt{n}]\times[0,\sqrt{n}]$ square with
torus boundary conditions. To simplify notation, we identify the node $u\in V$
and its position $(x_{u},y_{u})\in\Phi$ both by $u$ and will use the words
node and point interchangeably. We denote the graph or shortest path distance
between node $u$ and $v$ with $d_{G}(u,v)$, and the Euclidean distance between
the two nodes with $d_{E}(u,v)$ .

We define a thinning $\Phi_{S}$ on $\Phi$ as a randomly-chosen sample of the
nodes in $\Phi$, resulting in a new PPP with intensity $\lambda_{s}$. Due to
the nature of the PPP, the number of nodes in any area $A$, defined as $N(A)$
or $N_{s}(A)$, respectively, is Poisson distributed.

The Simple algorithm is an algorithm designed to recover connected general
bounded degree graphs [16] (Algorithm 1). As a query oracle, the algorithm
applies _distance_ queries. For every queried pair, the oracle returns the
number of edges on the shortest path between node $u$ and $v$. As a result,
the algorithm returns the full edge set of the graph and has query complexity
$\tilde{O}(n^{5/3})$. Although faster algorithms exist for general graph
reconstruction (e.g. [14]), we specifically analyze this algorithm as it is
easy to follow and we can show that it performs asymptotically optimal on
GRGs.

Algorithm 1 Simple$(V,s)$, from [16]. The function Query$(u,v)$ returns the
number of edges on the shortest path between node $u$ and $v$.

1:$S\leftarrow$ sample of $s$ nodes uniformly and independently at random from
$V$

2:for $u\in S$ and $v\in V$ do

3: Query$(u,v)$

4:end for

5:$\hat{E}\leftarrow$ set of node pairs $\\{a,b\\}\subseteq V$ such that, for
all $u\in S$, $|d_{G}(u,a)-d_{G}(u,b)|\leq 1$

6:for $\\{a,b\\}\in\hat{E}$ do

7: Query$(a,b)$

8:end for

9:return set of node pairs $\\{a,b\\}\in\hat{E}$ such that $d_{G}(a,b)=1$

The Simple algorithm consists of two steps. First it calculates the shortest
path distance between the seeds and every other node in the graph. Based on
these queries, Line 5 decides whether a node is _distinguishable_ or not,
where distinguishable is defined as follows [16]:

######  Definition 1 (distinguishable).

We call a node pair $u,v\in V$ distinguishable if there is a seed $s\in S$
such that the condition in Algorithm 1 line 5 is not satisfied, i.e.

$\displaystyle|d_{G}(s,u)-d_{G}(s,v)|>1.$ (1)

If (1) is satisfied for a seed $s\in S$, we say this seed distinguishes the
node pair $u,v$. The seed $s$ is then called a distinguisher for node pair
$u,v$.

When a pair of nodes $\\{a,b\\}$ is distinguishable, this means that the
shortest path distances from seed $s$ to $a$ and from $s$ to $b$ differ by
more than one. In that case, there cannot be an edge between node $a$ and $b$.
Suppose $d_{G}(s,a)<d_{G}(s,b)$: if there would have been an edge between node
$a$ and $b$, this edge would have been in the shortest path from $s$ to $b$
and the difference between the two graph distances would be 1. Then, in the
second step, all pairs of nodes that are not distinguishable are queried again
to check whether there is an edge between them or not.

The proof that Simple fully reconstructs random regular graphs is heavily
based on the fact that the graph is tree-like, which is not the case for GRGs.
Thus, to analyze the query complexity of the Simple algorithm for GRGs, we use
results from [9] to leverage the connection between the graph distance and the
Euclidean distance to reconstruct the graph.

######  Theorem 1 (Theorem 3.9 from [9]).

There exist absolute constants $C_{1},C_{2}$ and $c$ such that, for all $n\geq
1$, all $r\geq C_{1}\sqrt{\log n}$, with probability at least $1-C_{2}/n^{2}$,
all pairs of nodes $u,v$ satisfy

$\displaystyle\left\lfloor\frac{d_{E}(u,v)}{r}\right\rfloor\leq
d_{G}(u,v)\leq\left\lfloor\frac{d_{E}(u,v)+\kappa}{r}\right\rfloor,$ (2)

where

$\displaystyle\kappa=c\left(\frac{d_{E}(u,v)}{r^{4/3}}+\frac{\log
n}{r^{1/3}}\right).$ (3)

This theorem was proven for random geometric graphs on the square
$[0,\sqrt{n}]^{2}$. The proof is based on a greedy algorithm in which the
authors construct a _greedy path_ between the nodes $u$ and $v$. Starting from
node $x_{0}=u$, they choose node $x_{i+1}$ as the neighbor of $x_{i}$ that has
the smallest distance to node $v$. The authors then show that the length of
this constructed path from $u$ to $v$ is at most the upper bound in (2). This
upper bound is based on the probability that there is a node in the
intersection of the ball with radius $r$ around $x_{i}$ and the ball with
radius $a_{t}$ around $v$, where $a_{t}$ is chosen such that the intersection
area is $\ln(2)$. Since none of the methods and concepts used in this proof
are based on the boundary conditions of the square area, the theorem is not
specific to geometric random graphs on a square but also holds when the
underlying space is toroidal.

We rewrite Theorem 1 to provide an upper bound and a lower bound for the
Euclidean distance between nodes $u$ and $v$, given a constant $c$ and graph
distance $t\coloneqq d_{G}(u,v)$. This yields

$\displaystyle d_{E}(u,v)$
$\displaystyle\geq\frac{r\left(tr^{4/3}-c\log(n)\right)}{c+r^{4/3}}\eqqcolon\ell_{n}(t),$
(4) $\displaystyle d_{E}(u,v)$ $\displaystyle\leq r(t+1)\eqqcolon u_{n}(t),$
(5)

for $t\geq 1$.

We now introduce our main results about the query complexity of GRG
reconstruction using the Simple algorithm [16].

######  Theorem 2.

Consider a connected geometric random graph $\mathcal{G}(n,r)$ on
$[0,\sqrt{n}]^{2}$ with torus boundary conditions and connection radius $r>0$.

  * •

When $r\sim n^{k}$, $0<k<\frac{1}{2}$, the Simple algorithm gives with high
probability a full reconstruction of $\mathcal{G}(n,r)$ in
$\tilde{O}\left(n^{2k+1}\right)$ distance queries if $\frac{3}{20}\leq
k<\frac{1}{2}$ and $\tilde{O}\left(n^{3/2-4k/3}\right)$ distance queries if
$0<k<\frac{3}{20}$.

  * •

When $r=o(\sqrt{n}),r\geq C_{1}\sqrt{\log(n)}$ for an absolute constant
$C_{1}$, the Simple algorithm gives with high probability a full
reconstruction of $\mathcal{G}(n,r)$ in $\tilde{O}\left(n^{3/2}\right)$
distance queries.

With this theorem, we extend the capabilities of the Simple algorithm to a
specific type of random graphs. We show that the Simple algorithm fully
reconstructs dense geometric random graphs with growing degree in an almost
optimal number of distance queries. Indeed, the GRG contains
$\tilde{O}(n^{2k+1})$ edges in expectation. Compared to the guaranteed query
complexity of $\tilde{O}(n^{5/3})$ of the Simple algorithm, our complexity
bound for geometric random graphs shows an enormous improvement. For sparser
GRGS with connection radius $r=O(\sqrt{\log(n)})$, we show that the Simple
algorithm fully reconstructs the graphs in $\tilde{O}(n^{3/2})$. This result
is again an improvement on the complexity bound of the Simple algorithm, and
matches the complexity bound described in [14] for bounded-degree graphs.
Here, we give an outline of the proof of Theorem 2. In Section 4 we provide
the necessary lemmas and give a proof. The proof is based on two parts:

  1. 1.

For every node $u\in V$, we show that there exist at least four seeds that are
at most Euclidean distance $d$ from node $u$ (Lemma 1), where the value of $d$
depends on $k$.

  2. 2.

We then show in Lemma 2 that after the initialization step in Simple, all node
pairs that have Euclidean distance more than
$r+2w_{n}(t_{\textup{max}})\log(n)$ are distinguished by the seed set, where
$t_{\textup{max}}$ is the maximal graph distance given Euclidean distance $d$.
Consequently, in the second step of the algorithm only the pairs of nodes that
are at Euclidean distance of at most $r+2w_{n}(t_{\textup{max}})\log(n)$ have
to be queried.

By combining the two observations, we can determine the number of queries that
is needed to fully reconstruct the graph. This number is equal to the number
of seed queries, i.e., the number of seeds times the number of nodes combined
with the number of queries in the second step of the algorithm.

The results in Theorem 2 are only almost edge-optimal for dense GRGs as we
rely in the proof on a number of seeds of order $n^{\epsilon}$, with
$\epsilon<1$ non-negative. However, our simulations show that in practice
often only four seeds are enough to fully reconstruct the graph in an almost
edge-optimal number of queries, both in sparse ($r=O(\sqrt{\log(n)})$) and in
dense ($r\sim n^{k}$) GRGs (Figure 6). Although Theorem 2 does not show full
reconstruction in edge-optimal time for sparse graphs with $r=O(\sqrt{n})$, we
can show that with only $n^{1+o(1)}\log(n)$ queries, the Simple algorithm
detects at least $75\%$ of the non-edges with high probability:

######  Theorem 3.

Consider a geometric random graph $\mathcal{G}(n,r)$ on $[0,\sqrt{n}]^{2}$
with torus boundary conditions and $r>C_{1}\sqrt{\log(n)}$ for a constant
$C_{1}>0$. With a seed set $S$ consisting of
$|S|=\log(n)n^{\epsilon},0<\epsilon<1$ randomly chosen nodes, the first step
of the Simple algorithm can detect at least $75\%$ of the non-edges in
expectation.

Here, we sketch an outline of the proof given in Section 5. We first define
four optimal locations for four seed nodes on the torus that maximize the
distance between any two seeds in Lemma 3. In Lemma 4 we show that we can
detect at least $75\%$ of the non-edges given the presence of four seeds at
the optimal seed locations.

Then, in Lemma 5, we show that there is a seed in $S$ that is at most
Euclidean distance $y$ apart from each optimal location when
$|S|=n^{\epsilon}\log(n)$. Finally, combining Lemmas 4 and 5 we show that
these near-optimal seed locations result in at least $75\%$ of the non-edges
detected.

##  4 Proof of Theorem 2

In this section, we prove Theorem 2 using the following two lemmas. As a seed
set $S$, we choose a random sample of all nodes in $V$. The set $S$ can be
regarded as a thinning of the Poisson point process underlying the GRG with
resulting intensity $\lambda_{s}$ for some $\lambda_{s}<1$.

The following lemma shows that for all nodes in the GRG, we can find four seed
nodes in $S$ that are at most at Euclidean distance $d$ from that respective
node.

######  Lemma 1.

Suppose that $\Phi$ is a Poisson point process on the torus $[0,\sqrt{n}]^{2}$
with intensity $1$ and that $S$ is a seed set consisting of a thinning of
$\Phi$ with resulting intensity $\lambda_{s}=\log(n)n^{\epsilon-1}$ for some
$\epsilon\in(0,1)$. Let $d=n^{a}$ for $a\in(0,1/2)$. For all $v\in V$, when
$2a+\epsilon\geq 1$, with high probability there exists a set $S_{v}\subseteq
S$ with $|S_{v}|\geq 4$ such that such that $d_{E}(v,s)\leq d$ for all $s\in
S_{v}$ when $n\rightarrow\infty$.

###### Proof.

Let $v\in V$ and define $\mathcal{B}_{v}$ as the event that there are at least
four seeds at Euclidean distance at most $d$ from node $v$. The probability of
this event is

$\displaystyle\mathbb{P}(\mathcal{B}_{v})=\mathbb{P}(N_{s}(\pi d^{2})\geq 4)$
$\displaystyle=1-e^{-\lambda_{s}\pi d^{2}}\sum_{i=0}^{3}\frac{(\lambda_{s}\pi
d^{2})^{i}}{i!}.$ (6)

By the union bound, the probability that this event occurs for every point
$v\in V$ is bounded by

$\displaystyle\mathbb{P}\left(\bigcap_{v\in
V}\mathcal{B}_{v}\right)=1-\mathbb{P}\left(\bigcup_{v\in
V}\mathcal{B}^{c}_{v}\right)$ $\displaystyle\geq 1-\sum_{v\in
V}\mathbb{P}(\mathcal{B}^{c}_{v})$ (7) $\displaystyle=1-ne^{-\lambda_{s}\pi
d^{2}}\sum_{i=0}^{3}\frac{(\lambda_{s}\pi d^{2})^{i}}{i!}.$ (8)

As defined in the lemma, $d=n^{a}$ and $\lambda_{s}=\log(n)n^{\epsilon-1}$.
Therefore,

$\displaystyle\mathbb{P}\left(\bigcap_{v\in V}\mathcal{B}_{v}\right)\geq
1-n^{1-\pi
n^{2a+\epsilon-1}}\sum_{i=0}^{3}\frac{\left(\pi\log(n)n^{2a+\epsilon-1}\right)^{i}}{i!}.$
(9)

When $n\rightarrow\infty$, (9) tends to 1 as long as $2a+\epsilon\geq 1$. ∎

In addition to guaranteeing that there are at least four seeds at Euclidean
distance at most $d$ from every node $v\in V$, we also ensure that every seed
node is located in another sector of the circle of radius $d$ around node $v$.
Therefore, we specify the sector in which each of the four seeds (Figure 1)
around the nodes in $V$ has to lie in the following corollary.

######  Corollary 1.

Lemma 1 also holds for every $v\in V$ with the following extra condition on
the configuration of the seeds $\\{s_{1},s_{2},s_{3},s_{4}\\}\subseteq S_{x}$:

$\displaystyle\varphi(v,s_{1})$
$\displaystyle\in\left[\frac{\pi}{2},\frac{3\pi}{4}+\alpha\right],$
$\displaystyle\varphi(v,s_{2})$
$\displaystyle\in\left[\pi,\frac{5\pi}{4}\right],$
$\displaystyle\varphi(v,s_{3})$
$\displaystyle\in\left[\frac{3\pi}{2},\frac{7\pi}{4}+\alpha\right],$
$\displaystyle\varphi(v,s_{4})$
$\displaystyle\in\left[0,\frac{\pi}{4}\right],$ (10)

where $\varphi(v,s)$ is the angle between the horizontal axis and the line
between node $v$ and seed $s$.

Figure 1: Regions in which the four seeds are located.

###### Proof.

As in Lemma 1, the seed nodes follow a PPP with intensity $\lambda_{s}$.
However, instead of computing the probability that there are at least four
seeds in a circle with radius $d$ around node $v$, we restrict these four
seeds to be in a specific sector of the circle, where every sector has area
$\pi/8d^{2}$. We define $\tilde{\mathcal{B}}_{v}$ as the event that these four
(disjoint) sectors of size $\pi/8d^{2}$ all contain at least one seed:

$\displaystyle\mathbb{P}\left((\tilde{\mathcal{B}}_{v})^{c}\right)$
$\displaystyle=\mathbb{P}(\text{no four disjoint areas of size $\pi/8d^{2}$
contain at least one seed})$ $\displaystyle=\mathbb{P}(\text{0, 1, 2 or 3
disjoint areas contain at least one seed})$
$\displaystyle=\left(\mathbb{P}\left(N_{s}\left(\frac{\pi}{8}d^{2}\right)=0\right)\right)^{4}+{4\choose
3}\mathbb{P}(N_{s}\left(\frac{\pi}{8}d^{2}\right)\geq
1)\left(\mathbb{P}\left(N_{s}\left(\frac{\pi}{8}d^{2}\right)=0\right)\right)^{3}$
$\displaystyle\hskip 28.45274pt+{4\choose
2}\left(\mathbb{P}\left(N_{s}\left(\frac{\pi}{8}d^{2}\right)\geq
1\right)\right)^{2}\left(\mathbb{P}\left(N_{s}\left(\frac{\pi}{8}d^{2}\right)=0\right)\right)^{2}$
$\displaystyle\hskip 28.45274pt+{4\choose
1}\left(\mathbb{P}\left(N_{s}\left(\frac{\pi}{8}d^{2}\right)\geq
1\right)\right)^{3}\mathbb{P}\left(N_{s}\left(\frac{\pi}{8}d^{2}\right)=0\right)$
$\displaystyle=e^{-\frac{\pi}{8}\lambda_{s}d^{2}}\left(5-6e^{-\frac{\pi}{8}\lambda_{s}d^{2}}+4e^{-\frac{\pi}{4}\lambda_{s}d^{2}}-2e^{-\frac{3\pi}{8}\lambda_{s}d^{2}}\right).$
(11)

Taking the union bound as in (8) gives

$\displaystyle\mathbb{P}\left(\bigcap_{v\in V}\tilde{\mathcal{B}}_{v}\right)$
$\displaystyle=1-\mathbb{P}\left(\bigcup_{v\in
V}{\left(\tilde{\mathcal{B}}_{v}\right)^{c}}\right)\geq
1-\sum_{x\in\Phi}\mathbb{P}\left(\left(\tilde{\mathcal{B}}_{v}\right)^{c}\right)$
$\displaystyle=1-ne^{-\frac{\pi}{8}\lambda_{s}d^{2}}\left(5-6e^{-\frac{\pi}{8}\lambda_{s}d^{2}}+4e^{-\frac{\pi}{4}\lambda_{s}d^{2}}-2e^{-\frac{3\pi}{8}\lambda_{s}d^{2}}\right).$
(12)

This probability tends to one as well when $2a+\epsilon\geq 1$. Thus, Lemma 1
also holds for the given restriction on seed locations. ∎

Now, we show that every pair of node $u,v\in V$ has a distinguisher, which
connects our previous observations to Line 5 of the Simple algorithm and gives
an indication of the number of node pairs that are distinguishable given the
seed set $S$.

######  Lemma 2.

For every pair of nodes $u,v\in V$ there is a seed $s\in S$ that can
distinguish $u,v$ when $d_{E}(u,v)\geq 2w_{n}(t_{\textup{max}})\log(n)+r$,
where

$\displaystyle w_{n}(t_{\textup{max}})$
$\displaystyle=\frac{cd}{r^{4/3}}+r+\frac{c\log(n)}{r^{1/3}},$ (13)

for a constant $c>0$. We define $t_{\textup{max}}$ as the maximal graph
distance between two nodes given Euclidean distance $d$

$\displaystyle
t_{\textup{max}}=\frac{d(c+r^{4/3})}{r^{7/3}}+\frac{c\log(n)}{r^{4/3}}.$ (14)

###### Proof.

We choose a seed $s\in S$ that is Euclidean distance $\tilde{d}\leq d$ away
from node $u$ and as far as possible from node $v$. We define
$t_{1}=d_{G}(u,s)$ and $t_{2}=d_{G}(v,s)$, where $t_{1}\leq t_{2}$. The seed
$s$ distinguishes $u$ and $v$ if $|t_{1}-t_{2}|>1$, which means that
$t_{1}+2\leq t_{2}$. By using Theorem 1 to bound $t_{1}$ and $t_{2}$ in terms
of the Euclidean distances we obtain

$\displaystyle t_{1}$
$\displaystyle\leq\left\lfloor\frac{\tilde{d}}{r}+\frac{c\left(\frac{\tilde{d}}{r^{4/3}}+\frac{\log
n}{r^{1/3}}\right)}{r}\right\rfloor=\frac{\tilde{d}}{r}\left(1+\frac{c}{r^{4/3}}\right)+\frac{c\log(n)}{r^{4/3}},$
(15) $\displaystyle t_{2}$
$\displaystyle\geq\left\lfloor\frac{d_{E}(s,v)}{r}\right\rfloor\geq\frac{d_{E}(s,v)}{r}-1,$
(16)

given a constant $c>0$.

Now, we show that $t_{1}+2\leq t_{2}$, which can be achieved by showing that
$r(t_{1}+3)\leq d_{E}(s,v)$ in light of (16). We first rewrite the left-hand
side of this inequality to

$\displaystyle r(t_{1}+3)$
$\displaystyle\leq\tilde{d}\left(1+\frac{c}{r^{4/3}}\right)+\frac{c\log(n)}{r^{1/3}}+3r.$
(17)

The Euclidean distance between node $v$ and seed $s$ is

$\displaystyle
d_{E}(s,v)=\sqrt{\tilde{d}^{2}+(2w_{n}(t_{\textup{max}})\log(n)+r)^{2}-2\tilde{d}^{2}(2w_{n}(t_{\textup{max}})\log(n)+r)\cos(\alpha)},$
(18)

where $\alpha$ denotes the angle between the line $u,v$ and $u,s$ (Figure 2).
Since the four seeds are located in the four regions defined in Corollary 1,
we compute an upper bound of $d_{E}(s,v)$ when $\alpha=\frac{5\pi}{8}$,

$\displaystyle d_{E}(s,v)$
$\displaystyle\leq\sqrt{\tilde{d}^{2}+(2w_{n}(t_{\textup{max}})\log(n)+r)^{2}-2\tilde{d}(2w_{n}(t_{\textup{max}})\log(n)+r)\cos\left(\frac{5\pi}{8}\right)}$
$\displaystyle=\sqrt{\tilde{d}^{2}+(2w_{n}(t_{\textup{max}})\log(n)+r)^{2}+2\tilde{d}(2w_{n}(t_{\textup{max}})\log(n)+r)\sin\left(\frac{\pi}{8}\right)}.$
(19)

Figure 2: Worst case location of the furthest seed $s$ relative to $v$.

The difference between the square of (19) and (17) is equal to

$\displaystyle d_{E}(s,v)^{2}-\left(r(t_{1}+3)\right)^{2}$
$\displaystyle=4r^{2}\left(\log^{2}(n)+\log(n)-2\right)+2\tilde{d}r\left(\sin\left(\frac{\pi}{8}\right)(2\log(n)+1)-3\right)$
$\displaystyle\hskip
14.22636pt+2cr^{2/3}\left(4\log^{2}(n)+2\log(n)-3\right)\log(n)$
$\displaystyle\hskip
14.22636pt+\frac{2c\tilde{d}}{r^{1/3}}\left(2\log(n)\left(\frac{2d}{\tilde{d}}\log(n)+\sin\left(\frac{\pi}{8}\right)+\left(\frac{d}{\tilde{d}}-1\right)\right)-3\right)$
$\displaystyle\hskip
14.22636pt+\frac{2c\tilde{d}^{2}}{r^{4/3}}\left(\frac{2d}{\tilde{d}}\sin\left(\frac{\pi}{8}\right)\log(n)-1\right)$
$\displaystyle\hskip
14.22636pt+\frac{c^{2}}{r^{8/3}}\big{(}4d\log^{2}(n)+h^{2}+2hr\log(n)\left(\frac{4d}{\tilde{d}}\log^{2}(n)-1\right)$
$\displaystyle\hskip
56.9055pt+r^{2}\log^{2}(n)\left(4\log^{2}(n)-1\right)\big{)},$ (20)

The difference in (20) is always positive for $n$ sufficiently large since
$d/\tilde{d}\geq 1$, implying that $d_{E}(s,v)\geq r(t_{1}+3)$, and therefore
$t_{1}+2\leq t_{2}$. Thus, we have shown that all nodes that are at least at
Euclidean distance $w_{n}(t_{\textup{max}})\log(n)+r$ apart can be
distinguished by a seed in $S$. ∎

We now have all building blocks to prove Theorem 2.

###### Proof of Theorem 2.

Let $\mathcal{G}(n,r)$ be a geometric random graph on $[0,\sqrt{n}]^{2}$ with
torus boundary conditions and $r\sim n^{k}$ , $k\in(0,1/2)$. By Lemmas 1 and
2, all node pairs that have Euclidean distance larger than
$2w_{n}(t_{\textup{max}})\log(n)+r$ are distinguishable, based on a seed set
of $|S|=\log(n)n^{\epsilon}$ randomly-chosen nodes, with $\epsilon\in(0,1)$.
Thus, the set of non-distinguishable node pairs that are queried in the second
step of the Simple algorithm (Line 6) can be upper bounded by the set of all
node pairs nodes that are at most Euclidean distance
$2w_{n}(t_{\textup{max}})\log(n)+r$ apart.

Let us determine the number of queries that still have to be performed. We
define the event
$\mathcal{C}_{v}:=\\{N_{c}\geq(1+\delta)\mathbb{E}(N_{c})\\}$, where $N_{c}$
is equal to the number of nodes in a circle around node $v$ with radius
$2w_{n}(t_{\textup{max}})\log(n)+r$. Using the Chernoff bound, we have:

$\displaystyle\mathbb{P}(\mathcal{C}_{v})$
$\displaystyle=\mathbb{P}(N_{c}\geq(1+\delta)\mathbb{E}(N_{c}))\leq
e^{-\delta^{2}\mathbb{E}(N_{c})/2},$ (21) $\displaystyle\mathbb{E}(N_{c})$
$\displaystyle=\pi\left(2w_{n}(t_{\textup{max}})\log(n)+r\right)^{2},$ (22)

with $w_{n}(t_{\textup{max}})$ as given in (13). By the union bound, the
probability that this holds for all $v\in V$ is bounded by:

$\displaystyle\mathbb{P}\left(\bigcup_{v\in V}\mathcal{C}_{v}\right)$
$\displaystyle\leq n\mathbb{P}(N_{c}\geq(1+\delta)\mathbb{E}(N_{c}))\leq
ne^{-\delta^{2}\mathbb{E}(N_{c})/2}$ $\displaystyle\leq n^{1-\delta^{2}\pi
w_{n}(t_{\textup{max}})},$ (23)

where the last line follows as an upper bound since $\mathbb{E}(N_{c})>2\pi
w_{n}(t_{\textup{max}})\log(n)>1$. Therefore, (23) tends to $0$ when
$n\rightarrow\infty$ for any constant $\delta>0$. Thus, with high probability,
there are at most $(1+\delta)\mathbb{E}(N_{c})$ nodes at Euclidean distance
$2w_{n}(t_{\textup{max}})\log(n)+r$.

Finally, we compute the number of queries to fully reconstruct the graph using
the Simple algorithm. For every seed, we have to query all nodes, resulting in
a total of $n\times\log(n)n^{\epsilon}$ queries (Lemma 1). Then, in the second
step of the algorithm, we only query the indistinguishable node pairs, of
which there are at most $(1+\delta)\mathbb{E}(N_{c})$ with high probability.
Thus, the second step uses at most $n\times(1+\delta)\mathbb{E}(N_{c})$
queries with high probability, which is of order

$\displaystyle
O\left(n\times(1+\delta)\pi\left(2w_{n}(t_{\textup{max}})\log(n)+r)^{2}\right)\right)=\tilde{O}\left(\max\left\\{\frac{n^{2a+1}}{r^{8/3}},\frac{n^{a+1}}{r^{1/3}},nr^{2}\right\\}\right),$
(24)

filling in (13) and $d=n^{a}$.

The total query complexity of the Simple algorithm is equal to the number of
initial queries from the seed set combined with the number of queries needed
to distinguish all node pairs, which gives

$\displaystyle\tilde{O}\left(n^{1+\epsilon}\right){+}\tilde{O}\left(\max\left\\{\frac{n^{2a+1}}{r^{8/3}},\frac{n^{a+1}}{r^{1/3}},nr^{2}\right\\}\right){=}\tilde{O}\left(\max\left\\{n^{1+\epsilon},\frac{n^{2a+1}}{r^{8/3}},\frac{n^{a+1}}{r^{1/3}},nr^{2}\right\\}\right).$
(25)

When $r=o(\sqrt{n})$, (25) simplifies to:

$\displaystyle\tilde{O}\left(\max\left\\{n^{1+\epsilon},n^{2a+1}\right\\}\right)=\tilde{O}\left(n^{3/2}\right),$
(26)

for $a=1/4$ and $\epsilon=1/2$, satisfying $2a+\epsilon\geq 1$. In the dense
regime with $r\sim n^{k},0<k<\frac{1}{2}$, we have

$\displaystyle\tilde{O}\left(\max\left\\{n^{1+\epsilon},\frac{n^{2a+1}}{r^{8/3}},\frac{n^{a+1}}{r^{1/3}},nr^{2}\right\\}\right)$
$\displaystyle=\tilde{O}\left(\max\left\\{n^{1+\epsilon},n^{2a+1-8k/3},n^{a+1-5k/3},n^{2k+1}\right\\}\right),$
$\displaystyle=\begin{cases}\tilde{O}\left(n^{3/2-4k/3}\right),\hskip
22.76228pt&\text{if }0<k\leq\frac{3}{20},\\\
\tilde{O}\left(n^{2k+1}\right),&\text{if
}\frac{3}{20}<k<\frac{1}{2},\end{cases}$ (27)

with the following values for $a$ and $\epsilon$:

$\displaystyle a=\begin{cases}\frac{1}{4}+\frac{2}{3}k,\hskip
22.76228pt&\text{if }0<k<\frac{3}{20},\\\ \frac{5}{12}-\frac{4}{9}k&\text{if
}\frac{3}{20}<k<\frac{1}{2},\end{cases}\hskip
5.69046pt\epsilon=\begin{cases}\frac{1}{2}-\frac{4}{3}k,\hskip
22.76228pt&\text{if }0<k<\frac{3}{20},\\\ \frac{1}{12}+\frac{13}{9}k&\text{if
}\frac{3}{20}<k<\frac{1}{2}.\end{cases}$ (28)

∎

##  5 Proof of Theorem 3

The proof of Theorem 3 is based on detecting the non-edges by finding all
distinguishable node pairs given four optimal seed locations, which we
introduce in the following lemma.

Figure 3: Optimal circle packing for 4 circles on a flat torus.

######  Lemma 3 (Optimal seed locations [12]).

The following four seed nodes
$S^{\textup{opt}}=\\{\tilde{s}_{1},\tilde{s}_{2},\tilde{s}_{3},\tilde{s}_{4}\\}$
with corresponding locations

$\displaystyle\tilde{s}_{1}$ $\displaystyle=(0,0),$ (29)
$\displaystyle\tilde{s}_{2}$
$\displaystyle=\left(\frac{1}{2}\sqrt{n},\frac{1}{2}\sqrt{n(7-4\sqrt{3})}\right),$
(30) $\displaystyle\tilde{s}_{3}$
$\displaystyle=\left(\frac{1}{2}\sqrt{n}(\sqrt{3}-2),\frac{1}{2}\sqrt{n}\right),$
(31) $\displaystyle\tilde{s}_{4}$
$\displaystyle=\left(\frac{1}{2}\sqrt{3n}(\sqrt{3}-1),\frac{1}{2}\sqrt{3n}(\sqrt{3}-1)\right)$
(32)

are called optimal seed locations, since the minimum distance between any of
the four seed nodes is maximized and equal to:

$\displaystyle x_{n}=\frac{\sqrt{6}-\sqrt{2}}{2}\sqrt{n}.$ (33)

Given a seed node $s\in S$ and a $t>1$, we classify two sets of nodes: (1)
nodes for which the graph distance to $s$ will always be _smaller_ than $t$
and (2) nodes for which the graph distance to $s$ will always be _larger_ than
$t+1$. Consequently, any node pair with one node from both sets will be
distinguishable by seed $s$. We call these two sets the lower and upper bound
set and define these using (4) - (5):

######  Definition 2 (Lower and upper bound set).

The lower bound set $L_{s}(t)$ of seed $s$ given the graph distance $t$ is the
set of nodes in which the graph distance to seed $s$ is smaller than $t$,

$\displaystyle L_{s}(t)$ $\displaystyle=\\{v\,|\,d_{E}(v,s)<\ell_{n}(t)\\}.$
(34)

Similarly, the upper bound set $U_{s}(t)$ of seed $s$ given graph distance $t$
is the set of nodes in which the graph distance to seed $s$ is larger than
$t+1$,

$\displaystyle U_{s}(t)$ $\displaystyle=\\{v\,|\,d_{E}(v,s)>u_{n}(t+1)\\}.$
(35)

######  Lemma 4.

Consider a connected geometric random graph $\mathcal{G}(n,r)$ on
$[0,\sqrt{n}]^{2}$ with torus boundary conditions and four seed nodes added at
the locations of Definition 3. Querying these seeds with all nodes results in
recovery of at least $75\%$ of the non-edges in expectation, for all $r>0$.

###### Proof.

Given four seeds
$S^{\text{opt}}=\\{\tilde{s}_{1},\tilde{s}_{2},\tilde{s}_{3},\tilde{s}_{4}\\}$
with optimal seed locations given by Lemma 3. By Definition 1, a pair of nodes
$u,v\in V$ is distinguishable by $s\in S^{\textup{opt}}$ when
$|d_{G}(u,s)-d_{G}(v,s)|>1$. Combining this with the lower and upper bound set
of definition 2, we define the set $\bar{E}_{s}(t)=\\{(u,v)|(u,v)\in
L_{s}(t)\times U_{s}(t)\\}$ as the set of distinguishable node pairs for graph
distance $t$ and seed $s$. Note that this set is directional, i.e. we define
$(u,v)$ as a different node pair than $(v,u)$, for ease of notation and
analysis. As a consequence, there are in total $n(n-1)$ possible node pairs.

We are interested in the number of all distinguishable node pairs, the non-
edges of the graph, which equals the size of the union of the sets
$\bar{E}_{s}(t)$ for all $t$ and $s\in S$:

$\displaystyle\left|\bigcup_{t}\bigcup_{s\in
S^{\textup{opt}}}\bar{E}_{s}(t)\right|$
$\displaystyle=\left|\bigcup_{t}\bigcup_{s\in S^{\textup{opt}}}L_{s}(t)\times
U_{s}(t)\right|$ $\displaystyle=\sum_{t}\left|\bigcup_{s\in
S^{\textup{opt}}}\left(L_{s}(t)\backslash L_{s}(t-1)\right)\times
U_{s}(t)\right|$ $\displaystyle=\sum_{t}\left|\bigcup_{s\in
S^{\textup{opt}}}\bar{L}_{s}(t)\times U_{s}(t)\right|.$ (36)

In the second step we have split the lower bound sets into rings to ensure
that these sets do not overlap for different $t$. To simplify notation, we
define these rings as $\bar{L}_{s}(t)\coloneqq L_{s}(t)\backslash L_{s}(t-1)$.

We choose a maximum graph distance $\tilde{t}$ such that

$\displaystyle 2\ell_{n}(\tilde{t}_{1})=x_{n},$ (37)

with $x_{n}$ as defined in (33). Solving (37) gives:

$\displaystyle\tilde{t}_{1}=\frac{4cr\log(n)+\sqrt{n}\left(\sqrt{6}-\sqrt{2}\right)\left(c+r^{4/3}\right)}{4r^{7/3}}$
(38)

As the sets $\bar{E}_{s}(t)$ are disjoint for all $s$ as long as
$t\leq\tilde{t}$,

$\displaystyle\sum_{t=1}^{\lfloor\tilde{t}_{1}\rfloor}\left|\bigcup_{s\in
S^{\textup{opt}}}\bar{L}_{s}(t)\times U_{s}(t)\right|$
$\displaystyle=4\sum_{t=1}^{\lfloor\tilde{t}\rfloor}\left|\bar{L}_{s_{1}}(t)\times
U_{s_{1}}(t)\right|$
$\displaystyle=4\sum_{t=1}^{\lfloor\tilde{t}\rfloor}\left|\bar{L}_{s_{1}}(t)\right|\cdot\left|U_{s_{1}}(t)\right|.$
(39)

Since nodes are distributed as a Poisson point process, the number of nodes in
disjoint regions are independent. Moreover, we define $\ell_{n}(0)=0$. Now, we
can bound the expected number of non-distinguishable node pairs by

$\displaystyle\mathbb{E}(|\bar{E}|)$ $\displaystyle\geq
4\sum_{t=1}^{\lfloor\tilde{t}\rfloor}\left(\pi^{2}\left(\ell_{n}(t)^{2}-\ell_{n}(t-1)^{2}\right)u_{n}(t+1)^{2}\right)$
$\displaystyle\geq\frac{2\pi(\tilde{t}-1)r^{10/3}}{3\left(c+r^{4/3}\right)^{2}}\big{(}2\pi
c\left(2\tilde{t}^{2}+11\tilde{t}+24\right)r^{2}\log(n)-12cn\log(n)$
$\displaystyle\hskip
113.81102pt-\pi\left(3\tilde{t}^{3}+11\tilde{t}^{2}+5\tilde{t}-24\right)r^{10/3}+6n(\tilde{t}-1)r^{4/3}\big{)},$
(40)

where the inequality follows since $\lfloor\tilde{t}\rfloor\geq\tilde{t}-1$.
Finally, filling in $\tilde{t}$ as (38) yields

$\displaystyle\mathbb{E}\left(\left|\bar{E}\right|\right)$
$\displaystyle\geq\frac{\pi\left(16-8\sqrt{3}-7\pi+4\sqrt{3}\pi\right)r^{8/3}}{8\left(c+r^{4/3}\right)^{2}}n^{2}+o(n^{2}),$
(41)

since $r<\sqrt{n}$. When $n\rightarrow\infty$ (and so does $r$), the
percentage of node pairs that is distinguishable is

$\displaystyle\frac{\mathbb{E}(|\bar{E}|)}{n(n-1)}\xrightarrow{n\rightarrow\infty}\frac{\pi(16-8\sqrt{3}-7\pi+4\sqrt{3}\pi)}{8}\approx
0.753.$ (42)

Thus, the number of non-edges that we detect after querying all nodes in the
graph with four seeds equals at least $75\%$ of the total number of non-edges.

∎

In Lemma 4 we assume that the seed nodes are at specific locations. However,
as we do not know the locations of the nodes, such seeds may not exist, and
even if they do, we are not able to select them. In the following lemma we
show, similarly to Lemma 1, that with in total $n^{\epsilon}$ seeds, there are
four seeds that are at most distance $y$ away from the four specified optimal
locations.

######  Lemma 5.

Suppose that $\Phi_{s}$ is a Poisson point process on $[0,\sqrt{n}]^{2}$ with
intensity $\lambda_{s}=\log(n)n^{\epsilon-1}$. We take $y=n^{b}$ for
$b\in(0,1/2)$. When $2b+\epsilon\geq 1$, with high probability there exist
$s_{i}\in S$ with $i=1,2,3,4$, such that $d_{E}(s_{i},\tilde{s_{i}})\leq y$
and $n\rightarrow\infty$ for $\tilde{s_{i}}\in\tilde{S}$.

###### Proof.

We define $\mathcal{B}_{\tilde{s}}$ as the event that there is at least one
point $s\in S$ at Euclidean distance at most $y$ from the optimal seed
$\tilde{s}\in\tilde{S}$. The probability of this event is

$\displaystyle\mathbb{P}(\mathcal{B}_{s})=\mathbb{P}(N_{s}(\pi y^{2})\geq 1)$
$\displaystyle=1-e^{-\lambda_{s}\pi y^{2}}.$ (43)

By the union bound, the probability that this event occurs for all four points
$\tilde{s}\in\tilde{S}$ is bounded by

$\displaystyle\mathbb{P}\left(\bigcap_{\tilde{s}\in\tilde{S}}\mathcal{B}_{\tilde{s}}\right)=1-\mathbb{P}\left(\bigcup_{\tilde{s}\in\tilde{S}}\bar{\mathcal{B}}_{\tilde{s}}\right)$
$\displaystyle\geq
1-\sum_{\tilde{s}\in\tilde{S}}\mathbb{P}(\bar{\mathcal{B}}_{\tilde{s}})=1-4e^{-\lambda_{s}\pi
y^{2}}.$ (44)

As $y=n^{b}$ and $\lambda_{s}=\log(n)n^{\epsilon-1}$,

$\displaystyle\mathbb{P}\left(\bigcap_{\tilde{s}\in\tilde{S}}B_{v}\right)\geq
1-4n^{-\pi n^{2b+\epsilon-1}}.$ (45)

When $n\rightarrow\infty$, (45) tends to 1 as long as $2b+\epsilon\geq 1$, so
these seeds exist with high probability. The circles with radius $y$ around
the four optimal seed locations will not overlap, so $|S|\geq 4$. ∎

Now, we combine the above lemma’s to prove Theorem 3.

###### Proof of Lemma 3.

In Theorem 4 we have shown that when there are four seeds at the optimal
locations, we can reconstruct at least $75\%$ of the non-edges. We now have a
seed set $S$ that is random sample of size
$\log(n)n^{\epsilon},\epsilon\in(0,1)$ of the node set and we define
$S^{(4)}=\\{s_{1},s_{2},s_{3},s_{4}\\}\subseteq S$ as the four seed nodes that
are closest to the optimal seed locations from Lemma 3. By Lemma 5, we know
that with high probability the four seeds $S^{(4)}$ are at most Euclidean
distance $y=n^{b}$ away from the optimal seed locations, where
$2b+\epsilon\geq 1$. Similar to Theorem 4, we compute the number of
distinguishable node pairs $|\bar{E}|$ as

$\displaystyle|\bar{E}|=\left|\bigcup_{t}\bigcup_{s\in
S}\bar{E}_{s}(t)\right|$ $\displaystyle\geq\left|\bigcup_{t}\bigcup_{s\in
S^{(4)}}\bar{E}_{s}(t)\right|$ $\displaystyle=\sum_{t}\left|\bigcup_{s\in
S^{\textup{opt}}}\bar{L}_{s}(t)\times U_{s}(t)\right|.$ (46)

Again, $\cap_{s\in S^{(4)}}\bar{E}_{s}(t)$ has to be empty, which means in
this setting that we choose the maximal graph distance $\tilde{t}$ such that

$\displaystyle u_{n}(\tilde{t}+1)+\ell_{n}(\tilde{t})=x_{n}-2y,$ (47)

since two seeds in $S^{(4)}$ are always Euclidean distance at least
$x_{n}-2y$. Then

$\displaystyle\tilde{t}=\frac{2cr\log(n)+\left(\sqrt{n}(\sqrt{6}-\sqrt{2})-4(r+2y)\right)\left(c+r^{4/3}\right)}{2\left(cr+2r^{7/3}\right)}.$
(48)

Then, we can follow the same steps as in (39) – (41), resulting in the same
limit as in (42), provided that $y=n^{b}<\frac{1}{2}$ and $r<\sqrt{n}$. Thus
with $n\times|S|=n^{\epsilon+1}\log(n)$ queries we can already reconstruct at
least $75\%$ of the non-edges in expectation. ∎

##  6 Simulations

We now compare our theoretical results to simulations and explore the
performance of the algorithm in practice. For all simulations, we show the
average results over 100 iterations. The dashed lines in the plots show the
theoretical bound on the complexity (up to a constant factor).

Figure 4: Simulated query complexity of the Simple algorithm for a GRG with
$r\sim n^{k}$, $k=0.1$ and $k=0.3$. The upper dashed line represents the
theoretical query complexity (up to a constant) from Theorem 2.

First, we compare the query complexity to the theoretical bound for a dense
GRG with $r=n^{k}$, where $k=0.1$ and $k=0.3$. Figure 4 shows that the
theoretical query complexity is indeed an upper bound on the simulated query
complexity. Moreover, in practice, the growth rate of the query complexity of
the Simple algorithm is closer to the number of edges than to
$\tilde{O}(n^{2k+1})$ or $\tilde{O}(n^{3/2-4k/3})$. Thus, the Simple algorithm
indeed results in almost optimal reconstruction.

Figure 5: Simulated query complexity of the Simple algorithm for a GRG with
$r\sim n^{0.3}$ on a torus and on a square. The upper dashed line represents
the theoretical query complexity $n^{2k+1}$ (up to a constant) from Theorem 2
and the lower dashed line is the number of edges in the toroidal GRG.

To simplify the proof, we have assumed torus boundary conditions for the GRG.
Figure 5 shows the difference in query complexity for a GRG on a torus and a
GRG on a square. The GRG on the torus performs slightly better in terms of
query complexity compared to the GRG on a square. This is explained by the
fact that a torus does not have a boundary and estimating graph distances
between nodes close to the boundary is hard [9] than far from the border.
However, both on the square and on the torus, the query complexity follows our
complexity bound. Therefore, it is reasonable to assume that the Simple
algorithm has a similar query complexity for GRGs on a square. With some extra
work, one could prove this result similarly to the proof of Theorem 2.

Figure 6: Simulated query complexity of the Simple algorithm for different
seed sizes, based on a GRG with $k=0.3$ and $n=2000$. The seed size used in
Theorem 2 corresponds to $|S|=386$.

Figure 6 plots the query complexity of Simple for different seed set sizes. In
our results, we use a seed set of size $\log(n)n^{\epsilon}$, with $\epsilon$
as defined in (28). However, the smallest number of queries is obtained with a
smaller seed size. This observation confirms our hypothesis that it is
possible to reconstruct the graph in even less shortest path queries with only
a few seeds.

In Figure 7 we compare the Simple algorithm for a random regular graph and the
GRG, where we choose the degree for the random regular graph such that it is
equal to the average degree in the GRG. As the proven query complexity in [16]
holds for sparse graphs while Theorem 2 only holds for dense geometric random
graphs, we compare the RRG and the GRG both in the sparse regime (Figure
7(a)), and in the dense regime (Figure 7(b)).

Note that the two plots in Figure 7 show different comparisons: in the sparse
regime, for both the RRG and GRG we keep the degree constant at $\Delta=50$,
which means that $r$ in the GRG is variable, while in the dense regime, we fix
the radius $r=n^{k}$ and change the degree of the RRG accordingly. Figure 7(b)
shows that indeed, the GRG outperforms the random regular graph in query
complexity in a dense setting. This trend is also observed in a sparse setting
in Figure 7(a), indicating that even in a sparse setting with bounded degree
one could prove a lower query complexity than $\tilde{O}(n^{5/3})$ in the case
of geometric random graphs.

(a) $r=\sqrt{\Delta/(n\pi)}$, where $\Delta=50$ and $|S|=4$.

(b) $r=n^{0.3}$.

Figure 7: Simulated query complexity of the Simple algorithm for a GRG with a
random regular graph with similar average degree, in a sparse and dense
setting.

(a) Sparse GRG, $r=2\sqrt{\log(n)}$.

(b) Dense GRG, $r=n^{k}$.

Figure 8: Percentage of discovered non-edges after the first step in the
Simple algorithm.

Finally, we confirm the results of Lemma 3 in Figure 8 and show that with the
given seed set $S$, where $|S|=n^{\epsilon}\log(n)$, $\epsilon=k$, querying
the nodes with all seeds already results in identifying at least $75\%$ of the
non-edges, for both dense and sparse graphs. In particular, the simulations
show that for large $n$, approximately $95\%$ of the non-edges is identified.
For the sparse regime, we chose $|S|=4$. Figure 8(a) shows that in practice,
almost all non-edges are found after the first step in the Simple algorithm.
The difference between our theoretical bound of $75\%$ and the simulation
results is mainly due to the fact that the lower and upper bound as given in
Theorem 1 are not tight.

##  7 Conclusion

In this paper, we have shown that the Simple algorithm can provide a fast
reconstruction of dense geometric random graphs, whereas until now only
results were known for sparse bounded-degree graphs. Moreover, we prove that
the Simple algorithm is almost optimal for the class of geometric random
graphs, as the query complexity asymptotically matches the number of edges.

We have shown that the underlying geometry of the GRG helps in fast
reconstruction, due to the local character of edges (i.e., nodes are only
connected if they are close). Due to the local edge property, we have shown
that querying only 4 seed nodes with all nodes in the graph already results in
at least $75\%$ of the non-edges detected. Therefore, we conjecture that the
Simple algorithm also efficiently reconstructs other types of geometric random
graphs, such as the hyperbolic random graph, which is possibly an even better
representation of the Internet topology [6], or the geometric inhomogeneous
random graph [7].

Another future research direction could be to design algorithms to
_approximately_ recover the graph, for example by terminating the Simple
algorithm after a given number of queries, or only query a selection of nodes.
For the verification problem, it would be interesting to investigate whether
it is possible to obtain a lower query complexity for approximate recovery.

## References

  * [1] M. Abrahamsen, G. Bodwin, E. Rotenberg, and M. Stöckel, Graph reconstruction with a betweenness oracle, in 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016.
  * [2] R. Afshar, M. T. Goodrich, P. Matias, and M. C. Osegueda, Mapping networks via parallel kth-hop traceroute queries, in 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022), Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022.
  * [3] P. Bastide and C. Groenland, Optimal distance query reconstruction for graphs without long induced cycles, arXiv preprint arXiv:2306.05979, (2023).
  * [4] Z. Beerliova, F. Eberhard, T. Erlebach, A. Hall, M. Hoffmann, M. Mihal’ak, and L. S. Ram, Network discovery and verification, IEEE Journal on selected areas in communications, 24 (2006), pp. 2168–2181.
  * [5] M. Boguna, I. Bonamassa, M. De Domenico, S. Havlin, D. Krioukov, and M. Á. Serrano, Network geometry, Nature Reviews Physics, 3 (2021), pp. 114–135.
  * [6] M. Boguná, F. Papadopoulos, and D. Krioukov, Sustaining the internet with hyperbolic mapping, Nature communications, 1 (2010), p. 62.
  * [7] K. Bringmann, R. Keusch, and J. Lengler, Geometric inhomogeneous random graphs, Theoretical Computer Science, 760 (2019), pp. 35–54.
  * [8] R. Castro, M. Coates, G. Liang, R. Nowak, and B. Yu, Network tomography: Recent developments, (2004).
  * [9] V. Dani, J. Díaz, T. P. Hayes, and C. Moore, Reconstruction of random geometric graphs: Breaking the $\omega$ (r) distortion barrier, European Journal of Combinatorics, (2023), p. 103842.
  * [10] V. Dani, J. Díaz Cort, T. P. Hayes, and C. Moore, Improved reconstruction of random geometric graphs, in 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022, pp. 48–1.
  * [11] J. Diaz, C. McDiarmid, and D. Mitsche, Learning random points from geometric graphs or orderings, Random Structures & Algorithms, 57 (2020), pp. 339–370.
  * [12] W. Dickinson, D. Guillot, A. Keaton, and S. Xhumari, Optimal packings of up to five equal circles on a square flat torus, Beiträge zur Algebra und Geometrie/Contributions to Algebra and Geometry, 52 (2011), pp. 315–333.
  * [13] T. Erlebach, A. Hall, M. Hoffmann, and M. Mihal’ák, Network discovery and verification with distance queries, in Italian Conference on Algorithms and Complexity, Springer, 2006, pp. 69–80.
  * [14] S. Kannan, C. Mathieu, and H. Zhou, Graph reconstruction and verification, ACM Transactions on Algorithms (TALG), 14 (2018), pp. 1–30.
  * [15] C. Konrad, C. O’Sullivan, and V. Traistaru, Graph reconstruction via mis queries, arXiv preprint arXiv:2401.05845, (2024).
  * [16] C. Mathieu and H. Zhou, A simple algorithm for graph reconstruction, Random Structures & Algorithms, (2023).
  * [17] R. Motamedi, R. Rejaie, and W. Willinger, A survey of techniques for internet topology discovery, IEEE Communications Surveys & Tutorials, 17 (2014), pp. 1044–1065.
  * [18] L. Reyzin and N. Srivastava, Learning and verifying graphs using queries with a focus on edge counting, in Algorithmic Learning Theory: 18th International Conference, ALT 2007, Sendai, Japan, October 1-4, 2007. Proceedings 18, Springer, 2007, pp. 285–297.
  * [19] G. Rong, W. Li, Y. Yang, and J. Wang, Reconstruction and verification of chordal graphs with a distance oracle, Theoretical Computer Science, 859 (2021), pp. 48–56.
  * [20] S. Sen and V. Muralidhara, The covert set-cover problem with application to network discovery, in International Workshop on Algorithms and Computation, Springer, 2010, pp. 228–239.