# Structure from Voltage

Robi Bhattacharjee111Department of Informatics, University of California San
Diego, 9500 Gilman Dr, La Jolla, CA 92093, United States Alexander
Cloninger222Department of Mathematics, University of California San Diego,
9500 Gilman Dr, La Jolla, CA 92093, United States Yoav Freund333Department of
Computer Science and Engineering, University of California San Diego, 9500
Gilman Dr, La Jolla, CA 92093, United States Andreas Oslandsbotn444Department
of Informatics, University of Oslo, Problemveien 7, 0315 Oslo, Norway
555Simula Research Laboratory, Kristian Augusts gate 23, 0164 Oslo, Norway

###### Abstract

Data is often represented as point clouds embedded in high-dimensional space,
with an intrinsic structure that concentrates on or close to lower-dimensional
sets. Dimensionality reduction is a field dedicated to uncovering these lower-
dimensional structures to mitigate the curse of dimensionality. Since the
intrinsic structure can be highly non-linear. Non-linear dimensionality
reduction techniques are necessary.

A prominent technique for non-linear dimensionality reduction is spectral
graph embeddings such as Laplacian eigenmaps (LP). The challenge with these
techniques is that they rely on calculating the eigenfunctions of a large
matrix that scales with the number of data points. These operations are
expensive and hard to parallelize and typically require the data to be stored
in memory.

In this paper, we propose a scalable non-linear dimensionality strategy that
is easy to parallelize. The approach we propose is based on the notion of a
localized voltage function defined on a graph constructed on the point cloud.
This is closely connected to the strategy used to define the effective
resistance (ER) on graphs. Unfortunately, it has been shown that when vertices
correspond to a sample from a distribution over a metric space, the limit of
the ER between distant points converges to a trivial quantity that holds no
information about the graph’s structure.

To circumvent this, we propose the notion of grounded resistor graphs, in
which the source vertex in ER is replaced with a source region, and the sink
vertex is replaced with a universal ground vertex that is connected to all
points by a fixed constant resistor. We then show that the energy-minimizing
voltage over this new construction converges towards a non-trivial solution in
the large sample limit. These voltage solutions are both localized near their
source regions and can be solved independently. Finally, we present
preliminary results, both theoretical and numerical, demonstrating how these
solutions can be used to provide low-dimensional embeddings for the underlying
space.

##  1 Introduction

Dimensionality reduction is the problem of finding a low dimensional
representation for locations in a point cloud. The importance of finding
efficient algorithms to solve this problem has increased with the availability
of datasets with millions of data points and thousands of dimensions.

Principal component analysis (PCA) is a very effective and efficient algorithm
for linear dimensionality reduction. In particular, PCA depends on the shape
of the point cloud only through the covariance matrix, and the transformations
it produces are linear. However, large and complex point clouds typically
exhibit non-linear structures, which makes traditional PCA insufficient.
Because of this, the field of non-linear dimensionality reduction (NLDR) has
emerged as a very active and productive area of research (see Section 1.1).

One approach to NLDR is to view the point cloud as a sample from an underlying
distribution and to characterize the Laplace-Beltrami operator (LBO) over that
distribution. Two prominent representatives of this line of work are Eigen
maps [1] and Diffusion maps [2], both of these algorithms are based on finding
the eigenfunctions of the LBO.

Computing these eigen-functions for a point cloud of size $n$ requires
computational time of $O(n^{3})$ on one computer and is hard to parallelize.
As a result, finding these vectors for point clouds larger than 100,000 is
impractical with current computers. Furthermore, typical implementations of
the calculations of these vectors require all of the data to be stored in a
single computer. The underlying reason that all of the data has to be
available at the same time is that typical eigen-functions are “global”, by
which we mean that for most eigen-functions $f$ one can find pairs of points
$a,b$ such that the distance $d(a,b)>r$ for some large value of $r$ and at the
same time $|f(a)|>\gamma$ and $|f(b)|>\gamma$ for some large $\gamma$. In this
work, we suggest characterizing the LBO on the point cloud using local
functions instead. We say that a function $g$ is local if for any pair of
points $a,b$ such that $d(a,b)>r$ either $|g(a)|<\epsilon$ or
$|g(b)|<\epsilon$ for some small $\epsilon$.

The eigenvectors of the LBO are solutions of homogeneous systems of equations.
Meanwhile, to construct local functions, one needs non-homogeneous solutions,
i.e., pointwise constraints. To help our intuition, we follow Doyle and Snell
[3] in using resistor circuits to model the graph Laplacian. In this setting,
one can define the non-homogeneous constraints by choosing two vertices: a
“source vertex” whose voltage is fixed to one, and a “sink vertex” whose
voltage is fixed to zero. The remaining vertices are “floating” or
“unconstrained” and the voltages on those nodes are set by minimizing the
energy dissipated by the circuit.

The minimal energy solution determines the current flowing from the source to
the sink. In turn, the reciprocal of the current determines the effective
resistance (ER). The ER is well-defined for discrete graphs. However, it
becomes trivial and uninformative when considering point clouds in a metric
space and letting the number of points increase to infinity, as shown by Von-
Luxburg et al. [4]. The first contribution of this paper is to show that this
problem can be alleviated by considering the effective resistance between
pairs of small regions rather than pairs of points. Keeping the regions fixed
as the number of points increases to infinity produces non-trivial limits that
can be used for NLDR.

A natural approach at this point is to use the voltage functions for different
source-sink location pairs as an alternative to the eigenvector
representation. Unfortunately, the resulting voltage functions are not local
if the sink and the source are far from each other. To ensure that the
functions are local, we introduce a particular form of the resistor graph,
namely the “grounded resistor graph”. A resistor graph is transformed into a
grounded resistor graph by adding a single node, the “ground”, connected to
each node in the original graph. The voltage functions are generated by
selecting a source and using the ground as the sink. The result is voltage
functions that are one at their respective source and strictly decreasing away
from it.

We consider sources to be landmarks and use the associated voltage function to
measure the divergence from the landmark 666This divergence is not a metric
because it is not symmetric. On the sum of the divergence from $A$ to $B$ with
the divergence from $B$ to $A$ is a metric, and this metric is the effective
resistance in the grounded graph.. We propose using the divergences from a
small fixed set of landmarks as a dimensionality-reducing mapping. To
represent a non-landmark location, we measure its divergence from each
landmark, and that set of distances uniquely identifies the location of the
point. Moreover, If the point cloud lies on a $k$-dimensional manifold, then
the divergence to the nearest $k+1$ locations uniquely identify the location.
Thus the identity of the close landmarks, together with the distances from
those landmarks, can be used as a low-dimensional representation of the
location.

Our contributions can be summarized as follows:

  * •

We alleviate the problem described by Von-Luxburg et al. [4] by appropriately
scaling the resistances as the sample size grows.

  * •

We prove the existence, convergence to a non-trivial limit, and shape
properties of the grounded metric voltage function.

  * •

We derive an analytical solution for the grounded metric voltage on the sphere
and support these solutions by numerical experiments.

  * •

We show the results of a few experiments on real-world data sets, including
MNIST and Frey-face data sets.

The rest of the paper is organized as follows. In section 2, we introduce the
notion of a grounded resistor graph. While section 3 extends this to the
metric graph and the grounded resistor graph on metric spaces. In section 4,
we discuss the limitations of LE and ER in the large-data metric-graph limit
and compare them to our method, which overcomes these limitations. In section
5, we theoretically analyze the grounded metric graph and show existence,
convergence, and shape properties of the voltage solution. In section 6 we
show theoretically how the voltage solution can be used to embed the sphere
and support our result with numerical experiments. In Section 7 we discuss
computational advantages with the metric voltage function while in Section 8
we conclude and discuss future work.

###  1.1 Relations to other work

In this section, we give a brief overview of related work.

#### Related work on non-linear dimensionality reduction

The published literature on NLDR is vast; see the survey [5]. Below is a non-
exhaustive list of some of the significant approaches.

  * •

Kernel based The kernel-PCA [6] method generalizes the classical linear PCA to
non-linear problems.

  * •

Manifold based methods rely on the assumption that the point cloud lies on a
low dimensional manifold and use ideas from differential geometry. These
include ISOMAP [7] that uses shortest paths as an approximation to geodesics,
and Locally linear embeddings [8] uses local linear approximations of
manifold.

  * •

Optimization based Direct optimization method use gradient descent algorithms
to improve an initial embedding. These include t-SNE [9], UMAP [10], force-
based algorithms [11], and LDLE [12].

  * •

Laplacian based are based on the Laplace-Beltrami operator. These include
Laplacian eigen-maps [1, 13] and Diffusion maps [2]

There are various overlaps and combinations of these categories. For example,
it has been shown that Laplacian based methods correspond to kPCA with
particular choices of the kernel [14]. Similarly, Laplacian based methods have
been used to initialize optimization based methods [15].

#### Related work on effective resistance

The ER was introduced as a distance function on graphs by Klein et al. [16].
Since then, it has proven a useful tool for capturing structural
characteristics of graphs, with numerous applications, such as phylogenetic
networks [17], detecting community structure [18], distributed control [19],
graph edge sparsification [20], and measuring cascade effects [21] e.g. in
power grids [22, 23, 24].

##  2 Resistor Graphs

In this section, we introduce the notion of a grounded resistor graph, which
will serve as our fundamental tool for analyzing graphs along with the spaces
from which they are sampled. We first review several key ideas and concepts
about resistor graphs.

###  2.1 General Resistor Graphs

Let $({X},{W})$ be an undirected, weighted graph with nodes
${X}=\\{x_{1},\ldots,x_{n}\\}$, and edge weights ${W}_{i,j}$. Let the voltage
${v}$ be a function ${v}:{X}\rightarrow\mathbb{R}$. The energy of the voltage
${v}$ is defined as

$E({v})\doteq\sum_{x_{i},x_{j}\in
X}{W}_{i,j}({v}(x_{i})-{v}(x_{j}))^{2}={v}^{T}{L}{v}$ (2.1)

where ${L}=D-{W}$ is the Laplacian matrix, and $D$ is a diagonal matrix such
that $D_{ii}=\sum_{j}{W}_{ij}$.

It is easy to see that, with no constraints, the minimal energy is zero, and
that zero energy is attained for any ${v}$ where all of the entries are equal;
$v(x_{i})=v$ for all vertices in the graph. Therefore, to obtain a non-trivial
voltage distribution on the graph, it is necessary to constrain the system.
This motivates the Energy Minimizing Voltage (EMV), which is the main object
we study in this paper.

######  Definition 2.1 (EMV).

The energy-minimizing voltage of a weighted graph $(X,W)$ with respect to
source and sink nodes $X^{s}$ and $X^{g}$, is the solution to the following
optimization problem:

$\displaystyle\begin{split}\min_{v}&\quad\sum_{x_{i},x_{j}\in
X}{W}_{i,j}({v}(x_{i})-{v}(x_{j}))^{2}\\\ \text{Subject to}&\quad
v(x_{i})=1\quad\forall x_{i}\in X^{s},\quad v(x_{i})=0\quad\forall x_{i}\in
X^{g},\end{split}$

where ${X}^{s}$ are the source nodes and ${X}^{g}$ the sink nodes.

The EMV owes its name to a helpful interpretation of the graph as an
electrical network. In the following, we give a brief description of this
view, while more details can be found in Doyle and Snell [3].

##### Electric networks:

The EMV can be thought of as the voltage in an electrical network, where the
graph corresponds to the underlying electric circuit. In this view, each
vertex has an associated voltage ${v}(x_{i})$ and each edge $(x_{i},x_{j})$
has associated a non-negative resistance $R_{i,j}=\frac{1}{W_{i,j}}$ and a
signed current $J_{i,j}=-J_{j,i}$. Furthermore, Ohm’s law relates the current
and resistance at an edge with the voltages at the vertices connected by the
edge. The relation can be written as

${v}(x_{i})-{v}(x_{j})=R_{i,j}J_{i,j}\quad\text{or alternatively}\quad
J_{i,j}=W_{ij}({v}(x_{i})-{v}(x_{j})).$ (2.2)

Meanwhile, from Kirchhoff’s law, the sum of currents entering a node $i$ must
be zero, namely

$\sum_{j\sim i}J_{i,j}=J_{ext,i},$ (2.3)

where $I_{ext,i}$ is an external current that can be either a source, a sink
or zero if the node is un-constrained (no external source applied). Combining
these laws we have that

$(Lv)_{i}=\sum_{j\sim i}W_{ij}(v(x_{i})-v(x_{j}))=J_{ext,i}$ (2.4)

from which it is easy to see that the EMV in Definition 2.1 can be attained.
In particular, the constraints on the source and ground voltages can be
enforced by the external current.

Because of this, we can interpret Equation (2.1) as the energy dissipated in a
circuit in the form of heat when no power is injected. With no external
source, it is clear that this energy is zero. Meanwhile, the constrained
system in Definition (2.1) corresponds to a circuit connected to an external
source for which a non-trivial minimal energy voltage vector exists.

###  2.2 Grounded Resistor Graphs

Computing the EMV over arbitrary choices of sources ${X}^{s}$ and sinks
${X}^{g}$ can reveal aspects of the global structure of a graph – for example,
measuring the total current that flows from ${X}^{s}$ to ${X}^{g}$ can give a
measure of the connectivity between these two sets. In this work, we are
particularly interested in the case where ${X}^{s}$ is a small set of closely
connected vertices, and ${X}^{g}$ is selected to reveal the local structure of
the graph around ${X}^{s}$. Motivated by this, we introduce the idea of a
grounded resistor graph, which replaces the set of sink nodes ${X}^{g}$ with a
dummy node $g$ that represents a universal sink. We refer to this sink as the
grounding node.

######  Definition 2.2 (Grounded resistor graph).

Let $(X,W)$ be a weighted graph. Then its grounded graph with grounded weight
$\rho$, $(X,W,\rho)$, is the graph in which the extra node, $g$, is connected
to all vertices with an edge of weight $\rho$.

Here, we don’t consider $g$ as a node of $X$ as its behavior is completely
determined by the weight $\rho$. As we will see later, it will be convenient
to keep $X,W$ unchanged when considering the grounded graph. Because
everything is connected to the ground, the EMV over $(X,W,\rho)$ will
naturally decay to $0$ on nodes far from the source. We define the grounded
EMV as follows.

######  Definition 2.3 (Grounded EMV).

$\displaystyle\begin{split}\min_{v:X\rightarrow[0,1]}&\sum_{i,j\in
X}W_{ij}(v(x_{i})-v(x_{j}))^{2}+\sum_{i}\rho v^{2}(x_{i})\\\ \text{Subject
to}&\quad v(x_{i})=1\quad\text{for all}\quad x_{i}\in{X}^{s}.\end{split}$

Here, the term $\sum_{i}\rho v(x_{i})$ represents the amount of energy
corresponding to the edges connecting each node to the ground vertex.
Furthermore, we exclude the ground node from $v$ because it is always defined
to have a voltage of $0$. For a given source $X^{s}$, we can describe the
solution of the EMV using the grounded weight matrix
$\widetilde{D}^{-1}\widetilde{W}^{(s)}$. Here
$\widetilde{D}\in\mathbb{R}^{n\times n}$ is a diagonal matrix with $D_{ii}=1$
for $x_{i}\in X^{s}$ and otherwise
$\widetilde{D}_{ii}=\rho+\sum_{j=1}^{n}W_{ij}$. Furthermore,
$\widetilde{W}^{(s)}\in\mathbb{R}^{n\times n}$ is defined as

$\widetilde{W}^{(s)}_{ij}=\begin{cases}1,&\text{if}\quad
i=j,x_{i}\in{X}^{s}\\\ 0,&\text{if}\quad i\neq j,x_{i}\in{X}^{s}\\\
W_{ij},&\text{otherwise}.\end{cases}$

We note that the source is incorporated by $\widetilde{W}^{(s)}$ and
$\widetilde{D}$ incorporates the effect of the grounding node through the
additional $\rho$ in the sum. With the definition of the grounded weight
matrix we have from Lemma 2.4 that the solution to the grounded EMV can be
written as:

######  Lemma 2.4.

The solution to the EMV in Def. 2.3 is the unique voltage function
$v^{*}:X\to[0,1]$, which satisfies
$v^{*}=\widetilde{D}^{-1}\widetilde{W}^{(s)}v^{*}$ and $v^{*}(x_{i})=1$ for
all $x_{i}\in{X}^{s}$.

The motivation for writing the EMV in this way will become clear later when we
introduce the metric

######  Remark 2.5.

We note that the sum of the $i$-th row of $\widetilde{W}^{(s)}$ is
$1/(1+\rho/\sum_{i}W_{ij})$ where $1/\rho$ is the resistance to ground. This
relation highlights the importance of the ground node because
$\rho/\sum_{i}W_{ij}\approx 0$ means a trivial solution since the rows sum to
one. Therefore, as the large graph limit means increasing $\sum_{i}W_{ij}$,
tuning of $\rho$ can be used as a counterweight. Furthermore, as we will show,
the voltage decay away from the source is tightly linked to the magnitude of
$\rho$.

##  3 Grounded Resistor Graphs over Metric Spaces

We focus on a special type of graphs, namely graphs constructed from samples
drawn from a distribution over a metric space. Let $(M,d)$ be a compact metric
space and $\mu$ the probability measure over $M$. Let the kernel function
$k:M\times M\rightarrow[0,1]$ be a function that defines what it means for two
points to be ”near” each other. Two commonly used kernel functions are:

  * •

The radial kernel: $k_{r}(x,y)=\mathbf{1}(d(x,y)\leq r)$ where $r>0$ is some
fixed radius.

  * •

The Gaussian kernel: $k_{\sigma}(x,y)=\exp(\frac{-d(x,y)^{2}}{2\sigma^{2}}),$
where $\sigma>0$ is the fixed temperature parameter.

Let $X_{n}=\\{x_{1},\cdots,x_{n}\\}$ be a sample of points $x_{i}\in M$ drawn
i.i.d. from $\mu$. Our main idea is to construct a weighted grounded graph,
$({X}_{n},W,\rho)$ by connecting points $x_{i},x_{j}$ by weights
$W_{ij}\propto k(x_{i},x_{j})$, and by utilizing a grounded weight
proportional to $\rho$. Then, if $M^{s}\subseteq M$ is a local region in $M$,
we can leverage the EMV over the grounded graph to understand the structure of
$M$ nearby $M^{s}$.

Figure 1: Example of resistance scaling. (a) Number of edges connecting $T$
and $T^{\prime}$ for $m=1$ point sampled from each region. (b) Number of edges
connecting $T$ and $T^{\prime}$ for $m=3$ points sampled from each region.
Notice that the number of edges between these regions is $m^{2}$.

To do so, it is essential that our computations converge towards a non-trivial
solution as the number of sampled points, $n$, goes towards infinity. In
particular, it is necessary for $W,\rho$ to appropriately scale as $n$
changes. It is therefore natural to demand that the physical properties of the
graph, embodied by the resistance, current and voltage, should remain
relatively stable as $n$ increases. Thus, it is crucial to understand how the
edge resistances should scale with the number of points sampled.

##### Scaling based on regional density

To this end, consider two small regions $T$ and $T^{\prime}$ such that
$k(x,x^{\prime})>0$ for all $x\in T$ and $x^{\prime}\in T^{\prime}$. Note,
these are not necessarily sources and sinks, just two small regions. For
simplicity let $k(x,x^{\prime})$ be constant, which means each edge has equal
resistance $R=1/k(x,x^{\prime})$. Our goal is to keep the resistances between
these two regions constant as the number of points changes. For a fixed
$X_{n}$, on average there are $m$ points $x\in S_{n}=\left\\{{x\in X_{n}:x\in
T}\right\\}$ and $m$ points $x^{\prime}\in S_{n}^{\prime}=\left\\{{x\in
X_{n}:x\in T^{\prime}}\right\\}$. This results in $m^{2}$ edges between $T$
and $T^{\prime}$. This means the total resistance between these regions is
$R/m^{2}$, given that these edges are connected in parallel.

The issue here is that, once we move to a denser sample $X_{2n}$ there will
be, on average, $2m$ points in $S_{2n}$ and $S_{2n}^{\prime}$ respectively.
This will create a net resistance $\frac{1}{4}R/m^{2}$, which means the
resistance between these physical regions $T,T^{\prime}$ is decreasing and
will go to 0 as $n$ goes to infinity. We illustrate this construction in
Figure 1.

Based on these considerations, we formally define the grounded metric resistor
graph, illustrated in Fig. 2.

######  Definition 3.1 (Grounded metric resistor graph).

Let $X_{n}=\\{x_{1},x_{2},\dots,x_{n}\\}\sim\mu$ be a set of points sampled
from data distribution $\mu$ over $M$, $k:M\times M\to[0,1]$ be a kernel
similarity function, and $\rho_{g}$ be a fixed scaling constant for the
grounded weight. Then the grounded metric resistor graph, $(X_{n},W,\rho)$, is
the weighted graph defined with grounded weight, $\rho=\frac{\rho_{g}}{n}$,
and edge weights $(W)_{ij}=\frac{k(x_{i},x_{j})}{n^{2}}$.

Next, we can define the grounded EMV for a region $M^{s}$ by considering all
points inside $M^{s}$ as sources.

######  Definition 3.2 (Grounded metric voltage function).

Let $M^{s}\subseteq M$ be any set, $\rho$ be a constant, and $(X_{n},W,\rho)$
be the corresponding grounded resistor graph constructed from
$X_{n}\sim\mu^{n}$. We define the grounded metric voltage function with
respect to $M^{s}$, denoted $v_{n}^{*}:X_{n}\rightarrow[0,1]$, as the grounded
EMV with respect to $X^{s}=M^{s}\cap X_{n}$.

Figure 2: An example of a grounded graph with red nodes denoting ${X}^{s}$ and
the blue node $g$ for the terminating ground node. Note that all points are
connected to the ground.

##  4 Outlining our method and comparing to existing work

We propose to use the grounded voltage function from Definition 3.2 as an
embedding tool. The idea is to distribute sources (landmarks) across the point
cloud we want to embed and, for each source, solve for an independent grounded
voltage function. With $d$-independent voltages, we can construct a
$d$-dimensional embedding, a strategy we call Localized voltage eigenmaps
(LVE).

In the remainder of this paper, we will establish the theoretical foundations
for LVE. However, before we do this, we will outline two existing approaches,
namely the effective resistance (ER) and the Laplacian eigenmaps (LE), and
explain how our method improves on these schemes.

###  4.1 Effective resistance

The ER is a measure for calculating distances on graphs [16]. It arises
naturally from the electrical system interpretation by considering each node
pair $(l,k)$ as a source-sink connection and enforcing a unit current between
them. The standard formulation of ER follows by enforcing these constraints on
Equation (2.4), which gives

$R^{eff}_{lk}=v(x_{l})-v(x_{k})=(e_{l}-e_{k})^{\top}L^{\dagger}(e_{l}-e_{k})=\left\|{z_{l}-z_{k}}\right\|^{2},$
(4.1)

where the effective resistance $R^{eff}_{lk}$ is an euclidean distance matrix
[25]. The last term in Eq. (4.1) shows how the ER can be considered an
n-dimensional embedding with $z_{l}=\Lambda^{-1/2}V^{\top}e_{l}$ for
$L=V\Lambda V^{\top}$. The advantage of ER is that the distance between nodes
can be computed without explicitly calculating the voltage functions $v$.
Instead, it suffices to solve for $L^{\dagger}$, the pseudo-inverse of $L$.
Methods have also been proposed for distributed computation [26].

##### Effective resistance as an EMV

We can relate the ER to the grounded voltage function by re-formulating the ER
as the solution to an EMV optimization problem. For a node pair $(l,k)$, the
voltage function defining the effective resistance
$R_{lk}^{eff}=v(x_{l})-v(x_{k})$ is the solution to the following minimization
problem.

$\displaystyle\begin{split}\min_{v:X\rightarrow\mathbb{R}}\quad&\sum_{i,j}W_{ij}(v(x_{i})-v(x_{j}))^{2}-\sum_{i\in(l,k)}J_{i}v(x_{i})\\\
\text{Subject to}\quad&J_{i}=1;\,\,i=l,\quad
J_{i}=-1;\,\,i=k\quad\text{and}\quad J_{i}=0\quad\text{otherwise}.\end{split}$
(4.2)

By considering Ohm’s law $J_{ij}=(v_{j}-v_{i})/R_{ij}$ with $v_{j}=0$,
$R_{ij}=\rho$ and summing over all nodes instead of $(l,k)$, the relation to
the grounded EMV becomes clear.

##### Limitations with the effective resistance

The problem with the ER, demonstrated by [4], is that the distance between
nodes connected by a path converges in the large graph limit to a trivial
quantity which only depends on the degree of the end-nodes.

###  4.2 Laplacian eigenmaps

Laplacian Eigenmaps is a widely used tool for finding a $d<n$ dimensional
representation of the $n$ nodes on a graph. The goal is to assign coordinates
$z_{k}\in\mathbb{R}^{d}$ to each node $k$, so nearby points on the graph
remain close. This is done by the following: for $l=1,\dots,d$ solve

$\displaystyle\begin{split}\min_{v^{(l)}:X\rightarrow\mathbb{R}}\quad&\sum_{i,j}W_{ij}(v^{(l)}(x_{i})-v^{(l)}(x_{j}))^{2}\\\
\text{Subject to}\quad&v^{(l)}\perp v^{(l^{\prime})}\quad\text{and}\quad
v^{(l)}\perp 1.\end{split}$ (4.3)

To avoid the trivial solution $v^{(l)}=1$, the constraint $v^{(l)}\perp 1$ is
enforced. Meanwhile, the orthogonality constraint $v^{(l)}\perp
v^{(l^{\prime})}$ is introduced to avoid solving for the same function $d$
times. It turns out that the minimizing set, satisfying these constraints, are
the first $d$ eigenfunctions of $L$, modulo the first, which turns the
optimization into an eigenvalue problem.

##### Laplacian eigenmaps as an electrical network

The eigenfunctions that solves the LE problem satisfies trivially
$L^{(l)}=\lambda_{l}Dv^{(l)}$. By thinking of the right-hand side as an
external current
$J_{ext,l}=\lambda_{l}Dv^{(l)}=\lambda_{l}(d_{1}v^{(l)}(x_{1}),\dots,d_{n}v^{(l)}(x_{n}))^{\top}$
we can think of each $v^{(l)}$ as a voltage over the nodes, that satisfies
Kirchhoff’s and Ohm’s law through Equation (2.4).

This means that the LE optimization problem in Equation (4.3) can be
considered an EMV defined over an electrical resistor graph, where constraints
are: no current accumulation due to $v^{(l)}\perp 1$ and orthogonality between
each voltage solution. Furthermore, the interpretation of the external current
$J_{ext,i}$ is that for each voltage function $v^{(l)}$, the nodes in the
graph can act as a source or a sink depending on the sign of $v^{(l)}(x_{k})$
at node $k$. In particular, we note that there are no constraints on the
locality of these sources and sink nodes.

##### Limitations with Laplacian eigenmaps

An important limitation of LE is the orthogonality condition, which prevents
the eigenvectors from being computed independently, preventing distributed
computation. Furthermore, the Laplacian eigenvectors are typically global and,
therefore, expensive to compute. By global, we mean in this context that the
eigenfunctions have non-zero support almost everywhere on the graph, meaning
we effectively need all nodes to compute the eigenfunctions. We can understand
this global behavior from the electrical network interpretation because, as we
have seen, the source and sink nodes are not confined to specific regions of
the graph, and because of this, neither are the voltage solutions.

###  4.3 Advantages of the grounded metric voltage function

In this paper, we are motivated by making an embedding for metric spaces,
which requires a computationally cheap and non-trivial solution in the large
graph limit. As we have seen, both LE and ER face limitations in this limit;
The ER suffers from a trivial solution; Whereas the LE is prevented from
distributed computations and suffers from high computational complexity.
Because of these limitations, both LE and ER are in their traditional form,
prevented from being used in the metric graph setting. In this paper, we show
that embedding using the grounded voltage function has the potential to
overcome these limitations.

##### Overcoming the limitations of LE

As we show in Section 5.2, combining a localized source with a universal
ground creates a localized voltage solution, reducing computational
complexity. Furthermore, the grounded voltage functions are free of dependency
conditions, such as the orthogonality condition enforced by LE, allowing
distributed computations.

##### Overcoming the limitations of ER

As apparent from Eq. (4.2) there is a close connection between the ER and the
grounded EMV. Therefore, one could expect a trivial limit also for the
grounded voltage function. However, as we show in Sections 5.1 and 5.3, the
grounded metric voltage function converges to a non-trivial limit as the
number of samples goes to infinity. This non-trivial limit is achieved because
we think of each node in the graph as a region with a density instead of
individual points, a view discussed in detail in Section 3. In particular,
this view introduces region-based scaling and sources that cover a finite
region instead of the point sources used in the ER setting.

Figure 3 illustrates the difference between using a point source and a
regional source whose strength increases proportionally with the number of
samples. We demonstrate this with four algorithms across different numbers of
points sampled from the same metric space. All of these are done without the
universal grounding node but with a source at $s=(0.1,0.1)$ and a sink at
$g=(0.7,0.7)$. Both source and sink regions are of radius $0.1$. We compute
voltage curves through the following four methods: (PM) the power method
described in Lemma 2.4; (RegionER) ER using a source vector $e_{X^{s}}$ where
the voltage curve is

$\displaystyle
v=L^{\dagger}\left(e_{X^{s}}-e_{X^{g}}-(p_{s}-p_{g})\right),\quad
e_{X^{s}}(x)=\begin{cases}1,&\textnormal{ if }x\in X^{s}\\\ 0,&\textnormal{
else}\end{cases},\quad e_{X^{g}}(x)=\begin{cases}1,&\textnormal{ if }x\in
X^{g}\\\ 0,&\textnormal{ else}\end{cases},$

where $p_{s}=\frac{1}{|X|}\sum_{x\in X}e_{X^{s}}(x)$ is the density of the
source, same for $p_{g}$ and the sink. The mean is subtracted so that the
total external current is mean 0; (DensityER) ER using an indicator source
vector $e_{s}$ localized at the exact source node $s\in X^{s}$, an equivalent
sink vector $e_{g}$, and the voltage curve

$v=L^{\dagger}\left(p_{s}\cdot e_{s}-p_{g}\cdot e_{g}-(p_{s}-p_{g})\right),$

where the mean is subtracted so that the total external current is mean 0;
(ER) standard ER using the indicator source vector $e_{s}$, the equivalent
sink vector $e_{g}$, and the voltage curve $v=L^{\dagger}(e_{s}-e_{g})$. It is
clear from Figure 3 that using a source region instead of a source point (even
if that point is weighted by the local density) is critical to attaining a
nontrivial limit as the number of points increases.

|  |  |
---|---|---|---
|  |  |
PM | RegionER | DensityER | ER
Figure 3: Trivial Limit of ER: (top) $2^{11}$ points, (bottom) $2^{15}$
points.

Finally, Figure 4 summarizes our contribution compared to the LE and ER
schemes.

Figure 4: Illustration of our contribution

##  5 Analysis of the grounded metric voltage function

Let $v_{n}^{*}$ be the grounded metric voltage function from Def. 3.2. In this
section, we show that this voltage function converges to a non-trivial
function as the sample size increase and provide shape bounds on the voltage
decay away from the source.

###  5.1 Convergence of the grounded metric voltage function

We start by showing that $v_{1}^{*},v_{2}^{*},\dots$ converge as our sample
size increases. Our first step is to define the voltage function formally,
${v}^{*}:M\to\mathbb{R}$, that they converge to. To this end, we start with an
explicit expression for $v_{n}^{*}$ which follows directly from Lemma 2.4.

######  Proposition 5.1.

Let $M^{s}\subseteq M$ be a source subset, $X_{n}\sim\mu^{n}$ be a finite
sample, $X^{s}=M^{s}\cap X_{n}$ be the set of source nods, and $\rho$ be a
scaling constant. Let $v_{n}^{*}$ be the induced grounded metric voltage over
$(X_{n},W,\rho)$. Then, for all $x_{i}\in X_{n}$, we have

$v_{n}^{*}(x_{i})=\frac{\sum_{x_{j}\in
X^{s}}k(x_{i},x_{j})+\sum_{x_{j}\in{X}_{n}\setminus
X^{s}}v_{n}^{*}(x_{j})k(x_{i},x_{j})}{\rho+\sum_{{\bm{\mathsf{x}}}_{j}\in{X}_{n}}k(x_{i},x_{j})},$

along with $v^{*}_{n}(x_{i})=1$ for $x_{i}\in{X}^{s}$.

###### Proof.

Follows from Lemma 2.4, by writing each element in the voltage vector
explicitly, for a given choice of kernel $k$ as weights.

∎

Proposition 5.1 suggests a natural limit object for $v_{n}^{*}$.

######  Theorem 5.2.

Let $M$ be a metric space, and $M^{s}$ denote a measurable set of source
vertices. Let $\rho>0$ be a scaling constant. Then there exists a unique map
$v^{*}:M\to[0,1]$ such that $v^{*}(x)=1$ for all $x\in M_{1}$ and the
following holds for all $x\in M\setminus M^{s}$:

$v^{*}(x)=\frac{\int_{M^{s}}k(x,y)d\mu(y)+\int_{M\setminus
M^{s}}v^{*}(y)k(x,y)d\mu(y)}{\rho+\int_{M}k(x,y)d\mu(y)}.$

Finally, to prove convergence, we must extend our solutions, $v_{n}^{*}$ over
grounded metric resistor graphs to the entire metric space $M$.

######  Definition 5.3.

Let $v_{n}^{*}$ be the EMV over grounded graph $(X_{n},W,\rho)$. For all $x\in
M$, we define the extension of $v_{n}^{*}$ as the map $v_{n}^{*}:M\to[0,1]$
satisfying the following: $v_{n}^{*}(x)=1$ if $x\in M^{1}$, and otherwise,

$v_{n}^{*}(x)=\frac{\sum_{i=1}^{n}k(x,x_{i})v_{n}^{*}(x_{i})}{\sum_{i=1}k(x,x_{i})}.$

######  Theorem 5.4.

Fix $\rho$ and $M_{1}\subseteq M$. Let $v_{n}^{*}$ denote the extension of the
EMV over the grounded graph, $(X_{n},W,\rho)$, and $v^{*}$ denote the limit
object described in Theorem 5.2. Then for any $x\in M$, the sequence
$v_{1}^{*}(x),v_{2}^{*}(x),\dots$ converges to $v^{*}(x)$ in probability
(taken over the randomness of sampling $X_{n}\sim\mu^{n}$).

###  5.2 Bounding the shape of the voltage function

We have shown that the grounded metric voltage converges to a non-trivial
function in the large sample limit. In this section, we want to gain insights
into the shape of this voltage function. Throughout this analysis we assume
the radial kernel $k(x,y)=d(||x-y||\leq r)$, and restrict the analysis to the
unit sphere $S^{d-1}$. Furthermore, we assume a uniform density and use the
Lebesgue measure, $\mu(A)=vol(A)$ to have a distribution to draw from.

We want to build a grounded metric graph on the sphere. Suppose the source
region $M_{1}$ consists of the density contained in a ball $B(x_{s},r_{s})$ of
radius $r_{s}$ centered on the source landmark $x_{s}$, where $x_{s}$ is a
point on the sphere. We can then construct a grounded metric resistor graph as
described in Def 3.1, with resistance to ground $\rho$. In the previous
sections, we showed that a non-trivial voltage function
$v^{*}:S^{d-1}\to[0,1]$ exists for this setting. For our configuration, we
denote this function $\lambda$. When the dimension $d$ is fixed, this function
is determined by three parameters, namely the source radius $r_{s}$, the
kernel radius $r$, and resistance to ground $\rho$. In this setting, we have
the following bounds on the shape of the grounded metric voltage function:

######  Theorem 5.5.

Let $z\coloneqq d_{M}(x_{s},x)=\arccos(\langle x_{s},x\rangle)$ be the
geodesic distance from the source landmark $x_{s}$ to a point $x$ in the unit
sphere. Furthermore, let $\phi(r)\coloneqq d_{m}(x_{c},x)$ be the arch-length
(geodesic) between two points that have euclidean distance $r$, where $r$ is
also the radius of the kernel $k$ used to construct the grounded metric graph.
Let $r_{s},r,\rho$ be fixed. It then exists a unique map
$\lambda:S^{d-1}\to[0,1]$ satisfying the following properties:

$\lambda(x)=\frac{\int_{B(0,r_{s})}k(x,y)d\mu(y)+\int_{S^{d-1}}k(x,y)\in
d(y\in S^{d-1}\setminus B(0,r_{s}))\lambda(y)d\mu(y)}{\rho+a}$

for $x\notin B(0,r)$ where $a$ denotes the volume of the ball of radius $r$,
$\lambda(x)=1$ for $x\in B(0,r)$ and for $t\in[1,\infty)$

  * •

$\lambda$ is radially symmetric and monotonically decreasing in distance
outside of $B(0,r_{s})$. In particular, there exists a function $h$ such that
$\lambda(x)=h(z)$.

  * •

(Upper Bound) For $z\geq 2r$, $h(z+t\phi(r))\leq\exp{(-t\ln{(1+2\rho/a)})}$.

  * •

(Lower Bound) There exists a constant $\Gamma$ s.t.
$h(z+t\phi(r/2))\geq\exp{(-t\ln{((a+\rho)/\Gamma)}}$

Theorem 5.5 shows that the voltage function $\lambda$ is essentially bounded
between two functions that exponentially decay with respect to
$z=d_{M}(x_{s},x)$, the geodesic distance from $x$ to the source landmark
located at $x_{s}$. We also note that the result in Theorem 5.5 can easily be
translated to a Disk in $\mathbb{R}^{d}$ by replacing the geodesic distance
with the euclidean distance. This holds because the symmetry arguments used to
derive the result for a sphere are also true for a disk. Corollary 5.6
summarize this result.

######  Corollary 5.6.

For a Disk in $\mathbb{R}^{d}$ we have the result in Theorem 5.5, with the
geodesic replaced by the euclidean distance, s.t. $z=d(x_{s},x)$, and the
following bounds on $h$:

  * •

(Upper Bound) For $z\geq 2r$, $h(z+tr)\leq\exp{(-t\ln{(1+2\rho/a)})}$.

  * •

(Lower Bound) There exists a constant $\Gamma$ s.t.
$h(z+tr)\geq\exp{(-2t\ln{((a+\rho)/\Gamma)}}$

###  5.3 Examples

We demonstrate the convergence of the grounded metric graph voltage on several
basic examples in Figure 5.

|  |
---|---|---
|  |
|  |
Figure 5: Grounded metric graph voltage. Top: ${X}_{1}$ on $[2,3]$ with large
$\rho$ to encourage fast decay. Middle: ${X}_{1}$ on $[2,3]$ with small $\rho$
to encourage slow decay. Bottom: ${X}_{1}$ centered at $(.1,.1)$ with radius
$0.1$ with large $\rho$. Left: $n=2^{11}$, Center: $n=2^{13}$, Right:
$n=2^{15}$

The first is on the 1D line $[0,3]$, where ${X}_{1}$ is a source of radius
$0.5$ on the interval $[2,3]$, and the sink ${X}_{0}$ is of radius $0.5$ on
the interval $[0,1]$. The second example is on the 2D unit square, with the
source and sink on opposite corners of the square. In both cases, the
Laplacian is formed with radius $r=0.05$, and the number of points range from
$2^{11},2^{13},2^{15}$. We also vary $\rho$ to demonstrate the effect of the
ground radius on the speed of decay of the voltage. In all cases, the voltage
function is strictly non-increasing away from the source.

##  6 Embedding using localized voltage functions

In this section, we show how the grounded metric voltage function from Def.
3.2 can be used as an embedding tool for various manifolds. The experiments in
section 5.3 along with Thm. 5.5 demonstrate, for a unit sphere $S^{d-1}$ and a
disk in $\mathbb{R}^{d}$, a consistent decay of the voltage solution away from
the source. The advantage of this behavior is that the voltage solution gives
information about how far other points in $M$ are from the source vertex;
points with high voltages must be close, whereas points with low voltages must
be far. Our idea is that the decay property can be used to construct an
embedding using a selection of independent voltage functions generated by
sources distributed across the manifold.

Our first step is to show theoretically that an embedding exists for the unit
sphere $S^{d-1}$. With a basis in the discussion in [27] on spherical
principal components analysis, we argue that there exists a large family of
manifolds that can be approximated locally by sphere segments, which makes
this result apply to a variety of cases beyond $S^{d-1}$. We illustrate the
method’s applicability on several manifolds, including a sphere and the MNIST
data set.

###  6.1 Embedding of a unit sphere $S^{d-1}$

We show theoretically that we can embed the unit sphere, $S^{d-1}$, using
ground voltage vectors from $d$ voltage sources. We will use a disk kernel $k$
with bandwidth $0<r<1$, and we will also take source radius $r_{s}=r$. We
begin with the notion of an $\epsilon$-injective embedding. We will also
assume that our data distribution over $S^{d-1}$ is the uniform distribution.

######  Definition 6.1.

Let $f:X\to Z$ be a map between metric spaces $X,Z$. For $\epsilon>0$, we say
that $f$ is $s$-injective if

$d(x,x^{\prime})>\epsilon\implies f(x)\neq f(x^{\prime}).$

Our goal will be to find an $\epsilon$-injective embedding of $S^{d-1}$. To do
so, we consider the standard embedding of $S^{d-1}$ in $\mathbb{R}^{d}$, and
let $||x-x^{\prime}||$ denote the $\ell_{2}$ distance between points
$x,x^{\prime}$. Note that because the distance metric completely determines
our voltage functions, it follows that any result for this setting will carry
over to any isometric embedding of $S^{d-1}$.

Next, we characterize voltage functions over $S^{d-1}$. We let
$\angle(x,x^{\prime})$ denote the angle between them on the sphere. That is
$\angle(x,x^{\prime})=\arccos\langle x,x^{\prime}\rangle.$ We also let
$r^{\prime}=\angle(x,x^{\prime}):||x-x^{\prime}||=r,$ denote the angle between
two points with an $\ell_{2}$ distance of $r$.

######  Theorem 6.2.

Let $x_{0}\in S^{d-1}$ be an arbitrary point, and let $v_{0}$ be the grounded
voltage function centered at $x_{0}$ with ground resistance $\rho$, source
radius $r_{s}=r$, and kernel function $k$ being the disk kernel with bandwidth
$r$. Then there exists a function $f:[0,\pi]\to 1$ with the following
properties.

1\. $f$ fully determines $v_{0}$. That is, $v_{0}(x)=f(\angle(x_{0},x))$ for
all $x\in S^{d-1}$).

2\. $f$ satisfies $f(\theta)>f(\theta^{\prime})$, for all
$\theta^{\prime}>\theta+r$

###### Proof.

Property 1 immediately holds due to the rotational symmetry of the sphere
about $x_{0}$. Furthermore, by the radial symmetry of the sphere, the same
function $f$ must suffice for all $x_{0}\in S^{d-1}$.

To show property 2, we first show that $f$ is weakly monotonic, that is
$f(\theta)\geq f(\theta^{\prime})$ if $\theta\leq\theta^{\prime}$. To do so,
let $A_{*},b_{*}$ be the operator and function from Definition B.1 such that
$v_{0}=A_{*}v_{0}+b_{*}$. As we showed earlier, we have that

$v_{0}=\sum_{i=0}^{\infty}A_{*}^{i}b_{0}.$

Thus, it suffices to show that all of the partial sums of this series are
weakly monotonic. We do so through induction.

The base case is trivial as $b_{0}$ is clearly weakly monotonic with respect
to the geodesic distance. For the inductive step, suppose that
$v_{0}^{n}=\sum{i=0}^{n}A_{*}^{i}b_{0}$ is weakly monotonic. Fix any
$\theta\leq\theta^{\prime}$ and let $x,x^{\prime}\in S^{d-1}$ be points such
that $\angle(x_{0},x)=\theta,\angle(x_{0},x^{\prime})=\theta^{\prime}$, and
$x_{0},x,x^{\prime}$ all lie on a great circle (that is, along a geodesic).

Let $B$ denote the disk of radius $r$ centered at $x$ intersected with
$S^{d-1}$, and $B^{\prime}$ denote the analogous disk for $x^{\prime}$. The
key observation is that $B^{\prime}$ is precisely the reflection of $B$ across
the perpendicular bisector of $x,x^{\prime}$ in $S^{d-1}$. Furthermore, this
reflection is clearly an isometry and preserves the uniform measure $\mu$ over
$S^{d-1}$. We let $\tau$ denote this reflection. Finally, observe that for all
$y\in B\setminus(B\cap B^{\prime})$,

$\angle(x_{0},y)\leq\angle(x_{0},\tau(y)).$

This holds even in the extreme case where $x^{\prime}$ is the antipodal point
to $x_{0}$.

We now substitute $\tau$ into the equation $v_{0}^{n+1}=A_{*}v_{0}^{n}+b_{*}$.
Doing so, we have

$\begin{split}v_{0}^{n+1}(x^{\prime})&=A_{*}v_{0}^{n}(x^{\prime})+b_{*}(x^{\prime})=\frac{\int_{B^{\prime}}k(x^{\prime},y)v_{0}^{n}(y)d\mu(y)}{\rho+\int_{B^{\prime}}k(x^{\prime},y)d\mu(y)}+b_{*}(x^{\prime})\\\
&=\frac{\int_{B}k(x^{\prime},y)v_{0}^{n}(\tau(y))d\mu(y)}{\rho+\int_{B^{\prime}}k(x^{\prime},y)d\mu(y)}+b_{*}(x^{\prime})\\\
&\leq\frac{\int_{B}k(x^{\prime},y)v_{0}^{n}(y)d\mu(y)}{\rho+\int_{B^{\prime}}k(x^{\prime},y)d\mu(y)}+b_{*}(x^{\prime})=v_{0}^{n+1}(x),\end{split}$

with the inequalities holding from our observations about $\tau$.

Finally, having shown that $v_{0}$ is weakly monotonic, we now turn to
Property 2. Fix $\theta,\theta^{\prime}$ and let $x,x^{\prime}$ be such that
$\angle(x_{0},x)=\theta$, $\angle(x_{0},x^{\prime})=\theta^{\prime}$. The key
observation is that for all $y\in B(x^{\prime},r)$, $\angle(x_{0},y)>\theta$.
This is from simple geometry as $\theta^{\prime}>\theta+r^{\prime}$. Thus, it
consequently follows that $v_{0}(y)\leq v_{0}(x)$ for all such $y$.
Substituting this, we have that

$\begin{split}v_{0}(x^{\prime})&=A_{*}v_{0}(x^{\prime})+b_{*}(x^{\prime})=\frac{\int_{B^{\prime}}k(x^{\prime},y)v_{0}(y)d\mu(y)}{\rho+\int_{B^{\prime}}k(x^{\prime},y)d\mu(y)}+b_{*}(x^{\prime})\\\
&\leq\frac{\int_{B^{\prime}}k(x^{\prime},y)v_{0}(x)d\mu(y)}{\rho+\int_{B^{\prime}}k(x^{\prime},y)d\mu(y)}+b_{*}(x^{\prime})\\\
&\leq
v_{0}(x)\frac{\int_{B^{\prime}}k(x^{\prime},y)d\mu(y)}{\rho+\int_{B^{\prime}}k(x^{\prime},y)d\mu(y)}+b_{*}(x^{\prime})\\\
\end{split}$

with the last inequality holding since $b_{*}(x^{\prime})=0$ as $x^{\prime}$
cannot be inside the source region as $\angle(x_{0},x^{\prime})>r^{\prime}$. ∎

We now show how to obtain an $\epsilon$-injective embedding of $S^{d-1}$.

######  Theorem 6.3.

Let $e_{1},\dots,e_{d}$ denote the standard normal basis of
$\mathbb{R}^{d-1}$, and associate them as voltage sources on $S^{d-1}$. Let
$v_{1},\dots,v_{d}$ denote their respective voltage functions using a disk
kernel of radius $r$ (and a source radius of $r$). Then the map

$x\mapsto(v_{1}(x),\dots,v_{d}(x))$

is an $r^{\prime}\sqrt{d}$-injective map, where $r^{\prime}\in[0,\pi]$ denote
the angle subtending a chord of length $r$ on the unit circle.

###### Proof.

Let $x,x^{\prime}$ be arbitrary points on $S^{d-1}$ with
$||x-x^{\prime}||>r\sqrt{d}$. Let $\theta_{i}$ denote the geodesic angle
distance of $x$ from $e_{i}$, and $\theta_{i}^{\prime}$ be the same for
$x^{\prime}$. It follows that

$\sum_{i=1}^{d}(\cos\theta_{i}-\cos\theta_{i}^{\prime})^{2}>r^{2}d.$

Thus, for some $i$, we must have
$(\cos\theta_{i}-\cos\theta_{i}^{\prime})^{2}>r^{2}$. WLOG, this holds for
$i=1$. Applying this, we have

$\begin{split}r^{\prime
2}&<(\cos\theta_{1}-\cos\theta_{1}^{\prime})^{2}=(2\sin\frac{\theta_{1}+\theta_{1}^{\prime}}{2}\sin\frac{\theta_{1}^{\prime}-\theta_{1}}{2})^{2}\\\
&\leq
4\sin^{2}\frac{\theta_{1}^{\prime}-\theta_{1}}{2}\leq(\theta_{1}^{\prime}-\theta_{1})^{2}.\end{split}$

Thus $\theta_{1}^{\prime}-\theta_{1}>r^{\prime}$ which implies
$v_{1}(x^{\prime})\neq v_{1}(x)$, as desired. ∎

###  6.2 Examples

To support our theoretical results, we show numerically how the grounded
metric voltage function can be utilized to embed the unit sphere. Furthermore,
we illustrate our method on two real-world data sets, namely the Frey faces
data-set [28, Accessed: 2022-09-30] and MNIST [29].

In the experiments, we build an embedding by computing $m$ independent voltage
functions $v^{(i)}_{n}$ from $m$ different sources $\widetilde{x}_{i}$
(landmarks), selected randomly from the manifold. From these voltages we then
construct an $m$ dimensional embedding
$Z=(v^{(1)}_{n},\dots,v^{(m)}_{n})\in\mathbb{R}^{n\times m}$. Since $m>3$ for
our experiments, the embeddings can not be visualized directly. Because of
this, we create a projection of the embedding into $d\leq 3$ dimensions using
$X_{d}=U_{d}\Lambda_{d}\in\mathbb{R}^{n\times d}$, which corresponds to a
multi-dimensional scaling embedding (MDS) [30]. Here $Z_{s}=U\Lambda V^{\top}$
is a centering of $Z$ and $U_{d},\Lambda_{d}$ are the $d$ leading eigenvectors
and eigenvalues.

##### Unit sphere experiment

We consider the embedding of the two first quadrants of the unit sphere
$S^{3}$. Using $n=2^{13}$ points sampled i.i.d. from this sphere segment we
calculate the voltage for $m=\\{3,5,7,9\\}$ sources. In Fig. 6 we show the
results from running these experiments. We see that increasing the number of
sources gives an increasingly better embedding, which demonstrates the
robustness of this algorithm w.r.t. choosing more sources than the intrinsic
dimension.

(a) Sphere segment 3 sources  (b) Sphere segment 5 sources  (c) Sphere segment
7 sources  (d) Sphere segment 9 sources

(e) Embedding 3 sources  (f) Embedding 5 sources  (g) Embedding 7 sources  (h)
Embedding 9 sources

Figure 6: Illustration of the embedding of the two first quadrants of a sphere
using localized voltage sources. The yellow and red colored regions correspond
to the sources. The upper row is the true manifold and the lower row is the
recreation using $m=\\{3,5,7,9\\}$ sources. In order to align the embedding
with the initial data we used orthogonal Procrustes analysis [30].

##### Frey-face experiment

The Frey face data set is taken from [28, Accessed: 2022-09-30] and consists
of $1965$ images of size $20\times 28$ of Brendan Frey’s face. We generate two
embeddings using respectively $m=\\{3,10\\}$ landmark sources selected
randomly from the images. Fig. 7 illustrates a 2-dimensional projection of
these embeddings. From the figure we see that the images are clustered based
on facial expressions. In particular, the images tend towards landmarks with a
similar expression and change gradually as you move away. Comparing Fig. 7a
and Fig. 7b, we see that additional landmarks open up local clusters by
spreading the images out in between.

(a) Embedding with 3 landmarks  (b) Embedding with 10 landmarks

Figure 7: Embedding of the Frey-face dataset. Larger images corresponds to
landmarks.

##### MNIST experiment

The MNIST data-set we use is taken from [28, Accessed: 2022-09-30] and
consists of $60000$ $28\times 28$ images of handwritten digits. For our
experiment, we extract $5000$ images from each of the digits $\\{3,4\\}$. From
each digit, we also select at random $m=5$ landmarks. Fig. 8 illustrates the
embedding. In particular, Fig. 8a shows how the embedding separates digit $3$
and $4$. Furthermore, we can see how the orientation/rotation of the digits
determines their clustering, especially apparent for digit $4$. Selecting a
subset of the landmarks, see Fig. 8b, we make a local embedding of their
neighborhood as shown in Fig. 8c.

(a) MNIST embedding with 10 landmarks  (b) Select a subset of landmarks and
their neighborhood  (c) Local embedding of neighborhood of selected landmarks

Figure 8: Embedding of digit 3 and 4 from the MNIST dataset suing 10 landmarks
and 5000 samples from each digit.

##  7 A note on computational efficiency

We have seen how the grounded metric voltage function decays exponentially
with the distance from the source. This property can be thought of as a
localization property, as the voltage will be negligible on most of the graph,
except for finite support around the source.

The advantage of this localization is that when computing the voltage, only a
subset of the graph needs to be used for any given source, reducing both
memory and computational requirements. Importantly, the finite support of the
voltage solution is a great alternative to traditional methods such as
Laplacian eigenmaps, which rely on the computation of eigenfunctions that are
typically global (meaning computations relies on the entire graph).

In the following, we characterize the effective support of the voltage
solution and its dependency on the parameters of the grounded metric graph.
Let $M_{1}$ be a source region of radius $r$ as defined in Def. 3.1.
Furthermore, let $f:M\rightarrow[0,1]$ be a radially symmetric function over
the metric space $(M,d)$ such that $f(x)=h(d(x_{1},x))$. For $\tau>0$ and
$x_{1}\in M_{1}$ we say that $f$ is localized around $x_{1}$ with support
radius $r_{supp}$ if for $d(x_{1},x)>r$,

$h(x)\geq\tau\quad\text{for}\quad d(x_{1},x)\leq r_{supp}\quad\text{and}\quad
h(x)<\tau\quad\text{for}\quad d(x_{1},x)>r_{supp}.$

######  Corollary 7.1.

(Locality of the voltage solution) Consider a disk in $\mathbb{R}^{d}$. As a
consequence of the exponential decay of the grounded metric voltage described
in Theorem 5.5 and Corollary 5.6, the voltage solution will be localized
around the source region $M_{1}$, with a support radius bounded by $r_{l}\leq
r_{supp}\leq r_{u}$ where

$r_{l}\coloneqq\frac{\frac{r}{2}\log{1/\tau}}{\log{(Cr^{d}+\rho)/\Gamma}}\quad\text{and}\quad
r_{u}\coloneqq\frac{r\log{1/\tau}}{\log{(1+\rho/Cr^{d})}}.$

From Corollary 7.1 it follows that the support of the voltage solution is
restricted to a subset of the manifold, centered around the source. In
particular, we see how the resistance to ground $1/\rho$ plays a crucial role
in its relation to the effective support. Namely, as the resistance to ground
decrease to zero, i.e. $\rho\rightarrow\infty$, then the effective support
will also go to zero $r_{supp}\rightarrow 0$. The intuition here is that, with
zero resistance to the ground, the ground drains all the current. Similarly,
when the resistance to the ground goes to infinity, i.e. $\rho\rightarrow 0$
then the effective support goes to infinity $r_{supp}\rightarrow\infty$. This
demonstrates the importance of the grounding node in achieving localized
effective support for the voltage solution.

##  8 Conclusion and future work

In this paper, we have demonstrated how the grounded metric voltage function
holds promise as a tool for low-cost and distributed embedding of manifolds.
The goal of this paper has been to establish a theoretical basis for further
development of this embedding strategy. In particular, we have shown
existence, convergence, and shape properties and demonstrated how the voltage
captures local structure of the manifold.

There are three main directions for expanding on this work. First, we are
interested in exploring the potential of constructing low-dimensional
embeddings of data sets using grounded voltage functions. While we took the
first steps in this direction in this paper (with theoretical results on the
sphere and experiments over the sphere, MNIST, and Frey-faces), we are
actively working towards more general results over arbitrary manifolds and
more extensive real-world data sets.

Second, we are interested in the computational aspect of this technique – the
local nature of the grounded voltage function suggests that distributed
computation approaches are viable. Thus, one important problem is to develop
algorithms that can provably and empirically leverage this. Finally, we are
interested in describing the limiting operator of our approach.

## References

  * [1] Mikhail Belkin and Partha Niyogi.  Laplacian eigenmaps for dimensionality reduction and data representation.  Neural Computation, 15(6):1373–1396, 2003.
  * [2] R. R. Coifman, S. Lafon, A. B. Lee, M. Maggioni, B. Nadler, F. Warner, and S. W. Zucker.  Geometric diffusions as a tool for harmonic analysis and structure definition of data: Diffusion maps.  In Proceedings of the National Academy of Sciences, volume 102, pages 7426–7431, 2005.
  * [3] Peter G Doyle and J Laurie Snell.  Random walks and electric networks, volume 22.  American Mathematical Soc., 1984.
  * [4] Ulrike Luxburg, Agnes Radl, and Matthias Hein.  Getting lost in space: Large sample analysis of the resistance distance.  In Advances in Neural Information Processing Systems, volume 23. Curran Associates, Inc., 2010.
  * [5] Laurens Van Der Maaten, Eric Postma, Jaap Van den Herik, et al.  Dimensionality reduction: a comparative review.  Journal of machine learning research, 10(66-71):13, 2009.
  * [6] Sebastian Mika, Bernhard Schölkopf, Alex Smola, Klaus-Robert Müller, Matthias Scholz, and Gunnar Rätsch.  Kernel PCA and de-noising in feature spaces.  In M. Kearns, S. Solla, and D. Cohn, editors, Advances in Neural Information Processing Systems, volume 11. MIT Press, 1998.
  * [7] Joshua B. Tenenbaum, Vin de Silva, and John C. Langford.  A global geometric framework for nonlinear dimensionality reduction.  Science, 290(5500):2319–2323, 2000.
  * [8] Sam T. Roweis and Lawrence K. Saul.  Nonlinear dimensionality reduction by locally linear embedding.  Science, 290(5500):2323–2326, 2000.
  * [9] Laurens Van der Maaten and Geoffrey Hinton.  Visualizing data using t-SNE.  Journal of machine learning research, 9(11):2579–2605, 2008.
  * [10] Leland McInnes, John Healy, and James Melville.  UMAP: Uniform manifold approximation and projection for dimension reduction.  arXiv preprint arXiv:1802.03426, 2018.
  * [11] Stefan Steinerberger and Yulan Zhang.  t-SNE, forceful colorings, and mean field limits.  Research in the Mathematical Sciences, 9(3):42, 2022.
  * [12] Dhruv Kohli, Alexander Cloninger, and Gal Mishne.  LDLE: Low distortion local eigenmaps.  Journal of machine learning research, 22:282–1, 2021.
  * [13] Mikhail Belkin and Partha Niyogi.  Towards a theoretical foundation for laplacian-based manifold methods.  Journal of Computer and System Sciences, 74(8):1289–1308, 2008\.
  * [14] Jihun Ham, Daniel D Lee, Sebastian Mika, and Bernhard Schölkopf.  A kernel view of the dimensionality reduction of manifolds.  In Proceedings of the 21st international conference on Machine learning, page 47, 2004.
  * [15] Dmitry Kobak and George C Linderman.  Initialization is critical for preserving global data structure in both t-SNE and UMAP.  Nature biotechnology, 39(2):156–157, 2021.
  * [16] Douglas J Klein and Milan Randić.  Resistance distance.  Journal of mathematical chemistry, 12(1):81–95, 1993.
  * [17] Stefan Forcey and Drew Scalzo.  Phylogenetic networks as circuits with resistance distance.  Frontiers in Genetics, 11:1177, 2020.
  * [18] Teng Zhang and Changjiang Bu.  Detecting community structure in complex networks via resistance distance.  Physica A: Statistical Mechanics and its Applications, 526:120782, 2019.
  * [19] Prabir Barooah and Joao P. Hespanha.  Graph effective resistance and distributed control: Spectral properties and applications.  In Proceedings of the 45th IEEE Conference on Decision and Control, pages 3479–3485, 2006.
  * [20] Daniel A Spielman and Nikhil Srivastava.  Graph sparsification by effective resistances.  SIAM Journal on Computing, 40(6):1913–1926, 2011.
  * [21] Sotharith Tauch, William Liu, and Russel Pears.  Measuring cascade effects in interdependent networks by using effective graph resistance.  In 2015 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), pages 683–688, 2015.
  * [22] Yakup Koç, Martijn Warnier, Piet Van Mieghem, Robert E. Kooij, and Frances M.T. Brazier.  The impact of the topology on cascading failures in a power grid model.  Physica A: Statistical Mechanics and its Applications, 402:169–179, 2014.
  * [23] Xiangrong Wang, Yakup Koç, Robert E. Kooij, and Piet Van Mieghem.  A network approach for power grid robustness against cascading failures.  In 2015 7th International Workshop on Reliable Networks Design and Modeling (RNDM), pages 208–214, 2015.
  * [24] Guido Cavraro and Vassilis Kekatos.  Graph algorithms for topology identification using power grid probing.  IEEE Control Systems Letters, 2(4):689–694, 2018.
  * [25] Arpita Ghosh, Stephen Boyd, and Amin Saberi.  Minimizing effective resistance of a graph.  SIAM Review, 50(1):37–66, 2008.
  * [26] Iqra Altaf Gillani and Amitabha Bagchi.  A queueing network-based distributed laplacian solver for directed graphs.  Information Processing Letters, 166:106040, 2021.
  * [27] Didong Li, Minerva Mukhopadhyay, and David B Dunson.  Efficient manifold and subspace approximations with spherelets.  arXiv preprint arXiv:1706.08263, 2017.
  * [28] Internet.  Sam Roweis.  https://cs.nyu.edu/~roweis/data.html, 2022.  Accessed: 2022-09-30.
  * [29] Li Deng.  The mnist database of handwritten digit images for machine learning research.  IEEE Signal Processing Magazine, 29(6):141–142, 2012.
  * [30] Ivan Dokmanic, Reza Parhizkar, Juri Ranieri, and Martin Vetterli.  Euclidean distance matrices: Essential theory, algorithms, and applications.  IEEE Signal Processing Magazine, 32(6):12–30, 2015.

##  Appendix A Proof of Lemma 2.4

To prove Lemma 2.4 we first include some notation. Let $s\in X^{s}$ be the
source node, $g$ the ground node, and $e_{i}\in\mathbb{R}^{n+1}$ the indicator
of node $i$.

###### Proof.

The constraints $v(s)=1$ and $v(g)=0$ can be written as $v^{\top}e_{s}=1$ and
$v^{\top}e_{g}=0$ respectively. We apply these constraints using the
Lagrangian multipliers $\lambda_{s}$ and $\lambda_{g}$, which gives
$f(v)=v^{\top}Lv-\lambda_{s}v^{\top}e_{s}-\lambda_{g}v^{\top}e_{g}$. When
equating the derivative of $f$ to zero, and using $Lv=(D-W)v=D(v-D^{-1}Wv)$ we
can write this equation as

$v=D^{-1}Wv+D^{-1}\lambda_{s}e_{s}-D^{-1}\lambda_{g}e_{g}.$ (A.1)

Since we enforce $v(s)=1$ on the source node, it follows that row $s$ in Eq.
(A.1) is $\lambda_{s}=d_{ss}-(Wv)_{s}$. Similarly, we have for row $g$ that
$\lambda_{g}=(Wv)_{g}$. It follows,
$v=\widetilde{D}^{-1}\widetilde{W}^{(s)}v$, where

$\widetilde{W}^{(s)}_{ij}=\begin{cases}1,&\text{if}\quad i=j,x_{i}\in X^{s}\\\
0,&\text{if}\quad i\neq j,x_{i}\in X^{s}\\\
W_{ij},&\text{otherwise},\end{cases}$

and $\widetilde{D}\in\mathbb{R}^{n\times n}$ is a diagonal matrix with
$D_{ii}=1$ for $x_{i}\in X^{s}$ and
$\widetilde{D}_{ii}=\rho+\sum_{j=1}^{n}w_{ij}$ otherwise. Note that the
$n+1$’th row and column (row and column of the ground) are dropped, since the
voltage on the ground is always zero anyway. If we have more source nodes in
$X^{s}$, these can be incorporated similarly by applying Lagrangian
multipliers $\lambda_{i}v_{i}e_{i}$ for each $i\in X^{s}$. ∎

##  Appendix B Proofs from Section 5

Throughout this section, we treat $M^{s}$ as fixed so as to avoid cumbersome
notation addressing the source region. Furthermore, because $v_{n}^{*}$ and
$v^{*}$ are defined to equal $1$ over $M^{s}$, we will reinterpret them as
maps $M\setminus M^{s}\to[0,1]$. Any such map $v$ can be immediately
transformed into a map over all $M$ by including $v(x)=1$ for all $x\in
M^{s}$.

###  B.1 Proof of Theorem 5.2

We begin by expressing Proposition 5.1 with an affine transformation.

######  Definition B.1.

Let $\mu$ be a measure over $M$, and let $v:M\setminus M^{s}\to\mathbb{R}$ be
a measurable map. Then define $A_{\mu}v:M\setminus M^{s}\to\mathbb{R}$ and
$b_{\mu}:M\setminus M^{s}\to\mathbb{R}$ as

$(A_{\mu}v)(x)=\frac{\int_{M\setminus
M^{s}}k(x,y)v(y)d\mu(y)}{\rho+\int_{M}k(x,y)d\mu(y)}\quad\text{and}\quad
b_{\mu}(x)=\frac{\int_{M^{s}}k(x,y)d\mu(y)}{\rho+\int_{M}k(x,y)d\mu(y)}.$

Together, we let $T_{\mu}v=A_{\mu}v+b_{\mu}.$

Thus, to prove Theorem 5.2, it suffices to show that for any choice of $\mu$,
there exists a unique map $v^{*}:M\setminus M^{s}\to\mathbb{R}$ that satisfies
$T_{\mu}v^{*}=A_{\mu}v^{*}+b_{\mu}$. To this end, the key idea will be to
leverage that $A_{\mu}$ is a contraction.

######  Definition B.2.

Let $\mathcal{F}$ denote the space of measurable functions $f:M\to\mathbb{R}$.
Define $||f||_{\infty}$ as

$||f||_{\infty}=\sup_{x\in X}|f(x)|.$

Furthermore, the $\ell_{\infty}$ distance between two functions $f,g$ is
defined as $||f-g||_{\infty}.$

It is well known that $\mathcal{F}$ is a closed metric space under the
$\ell_{\infty}$ metric. We now show that $A_{\mu}$ is a contraction with
respect to the $\ell_{\infty}$-metric.

######  Lemma B.3.

For any measurable function $f:M\to\mathbb{R}$,

$||A_{\mu}f||_{\infty}\leq\frac{1}{1+\rho}||f||_{\infty}$

###### Proof.

This follows from algebraic manipulations. We have

$\begin{split}\sup_{x\in M}|(A_{\mu}f)(x)|&=\sup_{x\in M\setminus
M^{s}}\frac{\int_{M\setminus
M^{s}}k(x,y)f(y)d\mu(y)}{\rho+\int_{M}k(x,y)d\mu(y)}\leq\sup_{x\in
M}\frac{\int_{M\setminus
M^{s}}k(x,y)||f||_{\infty}d\mu(y)}{\rho+\int_{M}k(x,y)d\mu(y)}\\\
&=||f||_{\infty}\sup_{x\in M}\left(\frac{\int_{M\setminus
M^{s}}k(x,y)d\mu(y)}{\rho+\int_{M}k(x,y)d\mu(y)}\right)\leq||f||_{\infty}\frac{1}{1+\rho},\end{split}$

with the last inequality holding since $k$ has range $[0,1]$ by assumption. ∎

We now prove Theorem 5.2.

###### Proof.

Set $u_{0}:M\setminus M^{s}\to\mathbb{R}$ as the $0$ function. That is
$u_{0}(x)=0$ for all $x$. For $i\geq 1$, define
$u_{i}=A_{\mu}(u_{i-1})+b_{\mu}$. We claim that this defines a Cauchy sequence
over $\mathcal{F}$ (Definition B.2). To see this, observe that for any $i\geq
1$,

$\begin{split}||u_{i+1}-u_{i}||_{\infty}&=||(A_{\mu}u_{i}+b_{\mu})-(A_{\mu}u_{i-1}+b_{\mu})||_{\infty}=||A_{\mu}(u_{i}-u_{i-1})||_{\infty}\leq
C||u_{i}-u_{i+1}||_{\infty}\end{split}$

with the last inequality holding by Lemma B.3. This implies that the distances
between consecutive elements of our sequence decrease geometrically. Since
$\mathcal{F}$ is closed with respect to $\ell_{\infty}$, it follows that this
sequence converges to some function $v$.

Next, we show $v$ satisfies $v=A_{\mu}v+b_{\mu}$. Fix any $\epsilon>0$. Then
there exists $n$ such that $||v-u_{n}||_{\infty},||v-u_{n+1}||<\epsilon$. It
follows that

$\begin{split}||v-(A_{\mu}v+b_{\mu})||_{\infty}&\leq||v-u_{n+1}||_{\infty}+||(A_{\mu}v+b_{\mu})-u_{n+1}||_{\infty}\\\
&\leq\epsilon+||(A_{\mu}v+b_{\mu})-(A_{\mu}u_{n}+b_{\mu})||_{\infty}=\epsilon+||A_{\mu}(v-u_{n})||_{\infty}\leq\epsilon+\frac{\epsilon}{1+\rho}.\end{split}$

Since $\epsilon$ was arbitrary, it follows that $v=A_{\mu}v+b_{\mu}$.

Next, to show $v$ has range $[0,1]$, we simply observe that $u_{n}$ has range
$[0,1]$ for all $n$. This can be shown by induction on $n$. The base case
clearly holds, and for the inductive step, observe that
$(A_{\mu}v_{n})(x),b_{\mu}(x)\geq 0$ $k$ is always non-negative which implies
$v_{n+1}(x)=(A_{\mu}v_{n})(x)+b_{\mu}(x)\geq 0$. To show that it is at most
$1$, we have

$\begin{split}v_{n+1}(x)&=(A_{\mu}v_{n})(x)+b_{\mu}(x)=\frac{\int_{M}k(x,y)v_{n}(y)d\mu(y)}{\rho+\int_{M}k(x,y)d\mu(y)}\leq\frac{\int_{M}k(x,y)d\mu(y)}{\rho+\int_{M}k(x,y)d\mu(y)}\leq
1.\end{split}$

Finally, to show uniqueness, suppose that $v^{\prime}$ also satisfies
$v^{\prime}=A_{\mu}v^{\prime}+b_{\mu}$. Then we have

$\begin{split}||v-v^{\prime}||_{\infty}&=||(A_{\mu}v+b_{\mu})-(A_{\mu}v^{\prime}+b_{\mu})||_{\infty}=||A_{\mu}(v-v^{\prime})||_{\infty}\leq\frac{1}{1+\rho}||v-v^{\prime}||_{\infty}.\end{split}$

which implies $||v-v^{\prime}||_{\infty}=0$ as desired. ∎

###  B.2 Proof of Theorem 5.4

We begin by observing that the extended voltage solution (Definition 5.3 for a
finite sample $S$ exhibits similar behavior to the voltage solution over a
measure $\mu$. The key idea is to define the measure $\mu_{S}$ over $M$ as the
measure induced by the uniform distribution over $S$.

######  Definition B.4.

Let $S=\\{x_{1},x_{2},\dots,x_{n}\\}$ be a finite set of $n$ points from $M$.
Then $\mu_{S}$ is the measure on $M$ defined as

$\mu_{S}(P)=\frac{1}{n}\sum_{i=1}^{n}\mathbbm{1}(x_{i}\in P),$

for all measurable sets $P$.

By substituting $\mu_{S}$ into Definitions B.4 and B.1, we have

$v_{n}^{*}=A_{\mu_{S}}v_{n}^{*}+b_{\mu_{S}}.$

Here note that we are considering its restriction to $M-M^{s}$ as discussed in
the beginning of this section. Furthermore, the existence and uniqueness of
$v$ follow directly Theorem 5.2.

We now desire to show that as the sample size increases to infinity,
$v_{n}^{*}$ pointwise converges towards $v^{*}$. To prove this, we begin by
showing that for large values of $n$, $T_{\mu_{S}}$ serves as an approximation
for $T_{\mu}$ when applied to $v^{*}$.

######  Lemma B.5.

Let $x\in M\setminus M^{s}$ be a point, and $\epsilon>0$ be a real number.
Then

$\Pr_{S\sim\mu^{n}}\left[\big{|}(T_{\mu}v^{*})(x)-(T_{\mu_{S}}v^{*})(x)\big{|}>\epsilon\right]<4\exp(-\frac{n\rho^{2}\epsilon^{2}}{9}).$

###### Proof.

Let $y\sim\mu$, and $Y=k(x,y)v^{*}(y)\mathbbm{1}(y\notin
M^{s})+k(x,y)\mathbbm{1}(y\in M^{s}).$ Let $Y_{1},Y_{2},\dots,Y_{n}$ are i.i.d
copies of $Y$. Since $k,v^{*}$ both have ranges in $[0,1]$, it follows that
$Y$ has range $[0,1]$ as well. It follows by Hoeffding’s inequality that

$\begin{split}\Pr\left[\left|\mathbb{E}[Y]-\frac{1}{n}\sum_{i=1}^{n}Y_{i}\right|>\rho\epsilon\right]<2\exp\left(-n\rho^{2}\epsilon^{2}\right).\end{split}$

Similarly, we let $Z$ denote the random variable $k(x,y)$, $y\sim\mu$ and
$Z_{1},\dots,Z_{n}$ be i.i.d copies of $Z$. We also have

$\begin{split}\Pr\left[\left|\mathbb{E}[Z]-\frac{1}{n}\sum_{i=1}^{n}Z_{i}\right|>\rho\epsilon\right]<2\exp\left(-n\rho^{2}\epsilon^{2}\right).\end{split}$

Next, we express $(T_{\mu}v^{*})(x)$ and $(T_{\mu_{S}}v^{*})(x)$ in terms of
these variables. We have,

$\begin{split}(T_{\mu}v^{*})(x)&=\frac{\int_{M^{s}}k(x,y)d\mu(y)+\int_{M\setminus
M^{s}}k(x,y)v^{*}(y)d\mu(y)}{\rho+\int_{M}k(x,y)d\mu(y)}=\frac{\mathbb{E}[Y]}{\rho+\mathbb{E}[Z]}.\end{split}$

Similarly,

$(T_{\mu_{S}}v^{*})(x)=\frac{\frac{1}{n}\sum Y_{i}}{\rho+\frac{1}{n}\sum
Z_{i}}.$

We will now use these expressions to bound the difference between
$(A_{\mu}u+b_{\mu})(x)$ and $(A_{\mu_{S}}(u)+b_{\mu_{S}})(x)$ in terms of
$Z,Y,Z_{i},Y_{i}$. For convenience, let

$\Delta=\max\left(|\frac{1}{n}\sum Y_{i}-\mathbb{E}[Y]|,|\frac{1}{n}\sum
Z_{i}-\mathbb{E}[Z]|\right).$

Then we have

$\begin{split}|(A_{\mu}u)(x)-(A_{\mu_{S}}u)(x)|&=\left|\frac{\mathbb{E}[Y]}{\rho+\mathbb{E}[Z]}-\frac{\frac{1}{n}\sum
Y_{i}}{\rho+\frac{1}{n}\sum Z_{i}}\right|.\end{split}$

To bound this, we split the difference into two parts. We have

$\begin{split}\left|\frac{\mathbb{E}[Y]}{\rho+\mathbb{E}[Z]}-\frac{\frac{1}{n}\sum
Y_{i}}{\rho+\mathbb{E}[Z]}\right|&\leq\frac{\Delta}{\rho},\end{split}$

$\begin{split}\left|\frac{\frac{1}{n}\sum
Y_{i}}{\rho+\mathbb{E}[Z]}-\frac{\frac{1}{n}\sum Y_{i}}{\rho+\frac{1}{n}\sum
Z_{i}}\right|&\leq\frac{(\frac{1}{n}\sum
Y_{i})\Delta}{(\rho+\mathbb{E}[Z])(\rho+\frac{1}{n}\sum
Z_{i})}\leq\frac{\Delta}{\rho}.\end{split}$

Similarly, we can also show that
$|(b_{\mu}-b_{\mu_{S}})(x)|\leq\frac{\Delta}{\rho}.$ Applying a union bound
for the deviations of $Y$ and $Z$, we see that $\Delta>\frac{\rho}{3}$ with
probability at most $4\exp(-\frac{n\rho^{2}\epsilon^{2}}{9})$. ∎

Next, we show how to adapt Lemma B.5 to hold uniformly over the entire sample
$S$. To do so, we first define a type of metric over the space of functions on
$M$.

######  Definition B.6.

Let $S=\\{x_{1},\dots,x_{n}\\}\subset M$ be a set of points, and let
$u:M\setminus M^{s}\to\mathbb{R}$ be a function. Then
$||u||_{S}=\max_{x_{i}\in M\setminus M^{s}}|u(x_{i})|$ is the largest absolute
value of $u$ over $S$.

######  Lemma B.7.

Let $S=\\{x_{1},\dots,x_{n}\\}\sim\mu^{n}$, and $\epsilon>0$ be a real number.
Then for $n>\frac{6}{\epsilon\rho}$,

$\Pr_{S\sim\mu^{n}}\left[||v^{*}-T_{\mu_{S}}v^{*}||_{S}>\epsilon\right]<4n\exp\left(-\frac{(n-1)\rho^{2}\epsilon^{2}}{36}\right).$

###### Proof.

Fix $x_{i}\in M\setminus M^{s}$. It suffices to show that
$|(T_{\mu}v^{*})(x_{i})-(T_{\mu_{S}}v^{*})(x_{i})|>\epsilon$ with probability
at most $4\exp\left(-\frac{(n-1)\rho^{2}\epsilon^{2}}{36}\right)$. To do so,
we essentially apply Lemma B.5. The only difficulty is that $S$ and $x_{i}$
are no longer independent as $x_{i}\in S$. To resolve this, we observe that
$x_{i}$ is independent from $S\setminus x_{i}$, and use this to bound the
difference. Applying this, we have,

$\begin{split}|(T_{\mu}v^{*})(x_{i})-(T_{\mu_{S\setminus
x_{i}}}v^{*})(x_{i})|&\leq\left|(T_{\mu}v^{*})(x_{i})-(T_{\mu_{S\setminus
x_{i}}}v^{*})(x_{i})\right|+\left|(T_{\mu_{S\setminus
x_{i}}}v^{*})(x_{i})-(T_{\mu_{S}}v^{*})(x_{i})\right|.\end{split}$

The former term can be directly bounded using Lemma B.5. Because $x_{i}$ and
$S\setminus x_{i}$ are independent, we have that with probability at most
$4\exp\left(-\frac{(n-1)\rho^{2}\epsilon^{2}}{36}\right)$,

$\left|(T_{\mu}v^{*})(x_{i})-(T_{\mu_{S\setminus
x_{i}}}v^{*})(x_{i})\right|>\frac{\epsilon}{2}.$

It thus suffices to show that the latter term is at most $\frac{\epsilon}{2}$.
To do so, we split $Tv^{*}$ into $Au+b$ for both $\mu_{S}$ and
$\mu_{S\setminus x_{i}}.$ Using the same variables, $Y,Y_{j},Z,Z_{j}$ as in
the proof of Lemma B.5 (and substituting $x=x_{i}$), we have

$\begin{split}\left|A_{\mu_{S\setminus
x_{i}}}v^{*}(x_{i})-A_{\mu_{S}}v^{*}(x_{i})\right|&=\left|\frac{\frac{1}{n-1}\sum_{j\neq
i}Y_{j}}{\rho+\frac{1}{n-1}\sum_{j\neq i}Z_{j}}-\frac{\frac{1}{n}\sum
Y_{j}}{\rho+\frac{1}{n}\sum Z_{j}}\right|\\\
&\leq\left|\frac{\frac{1}{n}+\frac{1}{n}\sum
Y_{j}}{\rho-\frac{1}{n}+\frac{1}{n}\sum Z_{j}}-\frac{\frac{1}{n}\sum
Y_{j}}{\rho+\frac{1}{n}\sum Z_{j}}\right|\leq\frac{2}{n\rho},\end{split}$

with the last inequality coming from the same manipulations applied in the
proof of Lemma B.5. We can similarly show that

$\left|b_{\mu_{S\setminus
x_{i}}}(x_{i})-b_{\mu_{S}}(x_{i})\right|\leq\frac{1}{n\rho}.$

However, since $n>\frac{6}{\epsilon\rho}$, it follows that
$|T_{\mu_{S\setminus
x_{i}}}(u)(x_{i})-T_{\mu_{S}}(u)(x_{i})|\leq\frac{\epsilon}{2},$ as desired. ∎

We are now prepared to prove Theorem 5.4.

###### Proof.

Let $S\sim\mu^{n}$ be a sample of $n$ i.i.d points, and let $v_{n}^{*}$ be its
corresponding voltage solution. By using natural analogs to Theorem 5.2 and
Lemma B.3, we immediately have that for any map $u:M\to[0,1]$,
$||A_{\mu_{S}}u||_{S}\leq\frac{1}{1+\rho}||u||_{S}$, and the sequence
$\\{T_{\mu_{S}}^{m}u\\}_{m\geq 1}$ converges pointwise to $v_{n}^{*}$. We also
have that the norm induced by Definition B.6 induces a metric over the space
of maps $M\setminus M^{s}\to\mathbb{R}$.

Next, by Lemmas B.5 and B.7, with probability $1-2\exp(O(-n))$ over $S$, both
of their desired bounds hold for some given point $x\in M$. Using this, along
with the fact that $v^{*},v_{n}^{*}$ are the fixed points of $T_{\mu}$,
$T_{\mu_{S}}$, we have,

$\begin{split}|v^{*}(x)-v_{n}^{*}(x)|&=|T_{\mu}v^{*}(x)-T_{\mu_{S}}v_{n}^{*}(x)|\leq|T_{\mu}v^{*}(x)-T_{\mu_{S}}v^{*}(x)|+|T_{\mu_{S}}v^{*}(x)-T_{\mu_{S}}v_{n}^{*}(x)|\\\
&\leq\epsilon+|A_{\mu_{S}}v^{*}(x)-A_{\mu_{S}}v_{n}^{*}(x)|\leq\epsilon+\frac{\sum_{x_{i}\in
M\setminus
M^{s}}k(x,x_{i})|v^{*}(x_{i})-v_{n}^{*}(x_{i})|}{\rho+\sum_{x_{i}}k(x,x_{i})}\\\
&\leq\epsilon+|v^{*}-v_{n}^{*}|_{S}\leq\epsilon+|v^{*}-T_{\mu_{S}}v^{*}|_{S}+\sum_{i=1}^{\infty}|T_{\mu_{S}}^{i}v^{*}-T_{\mu_{S}}^{i+1}v^{*}|_{S}\leq\epsilon+\frac{\epsilon}{\rho},\end{split}$

Since $\epsilon$ is arbitrary, the claim follows as $\rho$ is a fixed
constant. ∎

##  Appendix C Proofs on the shape and support of the GMV

###  C.1 Proof of Theorem 5.5

In this section, we prove Theorem 5.5. First, we establish existence, radial
symmetry, and monotonicity regarding $\lambda$. Let $A_{\nu}$ and $b_{\nu}$ be
as defined in Definition B.1, with $M=S^{d-1}$ and $M^{s}=B(0,r_{s})$. The
existence of $\lambda(x)=v^{*}(x)$, where
$v^{*}(x)=(A_{\mu}v^{*})(x)+b_{\mu}$, then follows straightforwardly from
Theorem 5.2. Meanwhile, from Section B, we have already established that
$v^{*}(x)$ corresponds to a local average of its neighbors, which implies that
$\lambda$ must be strictly non-increasing away from the source. Furthermore,
due to the radial symmetry of the sphere and the kernel $k$, it follows that
also $A_{\mu}$ and $b_{\mu}(x)$ are radially symmetric. Moreover, in Section B
we establish that $v_{n+1}(x)=(A_{\mu}v_{n})(x)+b_{\mu}$ converges to $v^{*}$.
With $v_{0}$ radially symmetric, it follows that also $\lambda$ must be
radially symmetric. Finally, we examine the upper and lower bounds.

###### Proof.

(Theorem 5.5) We have already shown that $\lambda$ exists and is radially
symmetric (meaning $h$ exists) and that $h$ is strictly non-increasing. We now
prove the bounds on $h$.

##### Upper bound:

Let $x$ be a point on the sphere, and $z=d_{m}(x_{s},x)$ be the geodesic
distance from the source landmark $x_{s}$. Furthermore, since we consider the
unit sphere, we have for two points on the sphere ,whose euclidean distance is
$r$, that $d_{M}(x_{i},x_{j})=\arccos(\langle x_{i},x_{j}\rangle)=\phi(r)$.

The key idea is now to bound the integral, $\int_{M}k(x,y)v(y)d\mu(y)$. To do
so, observe that by the definition of $k$, this integral is only non-zero over
the ball $B(x,r)$. Furthermore, at most half of the probability mass of this
ball satisfies $v(y)\geq v(x)$, and all points inside this ball satisfy
$v(y)\leq h(z-\phi(r))$ as $z-\phi(r)$ is the closest that any point in this
ball gets to the origin. Thus, bounding the expectation, we have

$\int_{M}k(x,y)v(y)d\mu(y)\leq\frac{a}{2}h(z-r)+\frac{a}{2}h(z).$

Substituting this, we have that

$\begin{split}h(z)&=v(x)=T_{\mu}v(x)=\frac{\int_{M}k(x,y)v(y)d\mu(y)}{\rho+a}\leq\frac{\frac{a}{2}h(z-\phi(r))+\frac{a}{2}h(z)}{\rho+a}.\end{split}$

With $z=z^{\prime}+\phi(r)$ the upper bound can be written as
$h(z+\phi(r))\leq C_{u}h(z)$ where $C_{u}=1/(1+2\rho/a)$. Recursion of this
expression gives $h(z+t\phi(r))\leq C_{u}^{t}h(z)$. We now let $z=z_{1}$ where
$z_{1}$ defines the center of the source, since $h(z_{1})=1$ this gives
$h(z+t\phi(r))\leq\exp{(-t\ln{(1+2\rho/a)})}$.

##### Lower Bound:

We use a similar strategy as we did with the upper bound. This time, we let
$\Gamma$ the probability mass of the ball $B(x,r)$ that consists of points $y$
for which $||y||\leq z-\phi(r/2)$. While this value depends on $z$, it can be
lower bounded by the case in which $||z||=\phi(r)$. This constant thus equals
the intersection volume between 2 $d$-dimensional spheres. Using this
constant, we see that

$\int_{M}k(x,y)v(y)d\mu(y)\geq\Gamma h(z-\phi(r/2)).$

Substituting this, we have

$\begin{split}h(z)&=v(x)=T_{\mu}v(x)=\frac{\int_{M}k(x,y)v(y)d\mu(y)}{\rho+a}\geq\frac{\Gamma
h(z-\phi(r/2))}{\rho+a},\end{split}$

We now treat the lower bound similarly to the upper bound. Here
$h(z+t\phi(r/2))\geq C_{l}^{t}$ where $C_{l}=\Gamma/(a+\rho)$, which gives
$h(z+t\phi(r/2))\geq\exp{(-t\ln{((a+\rho)/\Gamma)}}$. ∎

###  C.2 Proof of Corollary 7.1

Consider a disk in $\mathbb{R}^{d}$. Let $z=z_{1}$ where $z_{1}$ defines the
center of the source, $h(z_{1})=1$. We are interested in the radial distance
$r_{supp}$ from $z_{1}$ such that $h(z_{1}+r_{supp})\geq\tau$. Let
$r_{supp}=tr$. From Corollary 5.6 we then have that

$h_{u}(r_{supp})\coloneqq\exp{\left({-\frac{r_{supp}}{r}\ln{(1+2\rho/a)}}\right)}\quad\text{and}\quad
h_{l}(r_{supp})\coloneqq\exp{\left({-2\frac{r_{supp}}{r}\ln{((a+\rho)/\Gamma}}\right)}$

The upper bound for $r_{supp}$ should therefore be
$r_{s,u}=\max\\{r_{supp}:h_{u}(z_{1}+r_{supp})\geq\tau\\}$. Similarly the
lower bound should be
$r_{s,l}=\max\\{r_{supp}:h_{l}(z_{1}+r_{supp})\geq\tau\\}$. Solving for
$r_{supp}$ we find that $h_{l}(r_{supp})\geq\tau$ and
$h_{u}(r_{supp})\geq\tau$ implies

$\displaystyle\begin{split}r_{supp}\leq\frac{\frac{r}{2}\log{1/\tau}}{\log{(Cr^{d}+\rho)/\Gamma}}\quad\text{and}\quad
r_{supp}\leq\frac{r\log{1/\tau}}{\log{(1+\rho/Cr^{d})}}.\end{split}$

respectively. Here we used that $a=Cr^{d}$ as it is the volume of a $d$
dimensional sphere. From the definition of $r_{s,l}$ and $r_{s,u}$ the result
follows.