<figure><img src="image_1.png" /></figure>

HAL
open science

# The f-Adjusted Graph Laplacian: a Diagonal Modification with a Geometric Interpretation

Sven Kurras, Ulrike von Luxburg, Gilles Blanchard

► To cite this version:

Sven Kurras, Ulrike von Luxburg, Gilles Blanchard. The f -Adjusted Graph Laplacian: a Diagonal Modification with a Geometric Interpretation. 31st International Conference on Machine Learning (ICML 2014), 2014, Beijing, China. pp.1530-1538. hal-03371231

HAL Id: hal-03371231

https://hal.science/hal-03371231

Submitted on 8 Oct 2021

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# The f-Adjusted Graph Laplacian:
a Diagonal Modification with a Geometric Interpretation

Sven Kurras
Ulrike von Luxburg

Department of Computer Science, University of Hamburg, Germany

Gilles Blanchard

Department of Mathematics, University of Potsdam, Germany

KURRAS@INFORMATIK.UNI-HAMBURG.DE
LUXBURG@INFORMATIK.UNI-HAMBURG.DE

GILLES.BLANCHARD@MATH.UNI-POTSDAM.DE

## Abstract

Consider a neighborhood graph, for example a *k*-nearest neighbor graph, that is constructed on sample points drawn according to some density *p*. Our goal is to re-weight the graph's edges such that all cuts and volumes behave as if the graph was built on a different sample drawn from an alternative density $\bar{p}$. We introduce the *f*-adjusted graph and prove that it provides the correct cuts and volumes as the sample size tends to infinity. From an algebraic perspective, we show that its normalized Laplacian, denoted as the *f*-adjusted Laplacian, represents a natural family of diagonal perturbations of the original normalized Laplacian. Our technique allows to apply any cut and volume based algorithm to the *f*-adjusted graph, for example spectral clustering, in order to study the given graph as if it were built on an inaccessible sample from a different density. We point out applications in sample bias correction, data uniformization, and multi-scale analysis of graphs.

## 1. Introduction

Assume that we are given a neighborhood graph $G$, say a *k*-nearest neighbor graph, based on a sample $x_1, ..., x_n$ of points drawn according to some probability density $p$. Many properties of $p$ reflect in properties of $G$. However, we are actually interested in another density $\bar{p}$ that differs from $p$ in some known aspects, but we cannot access a sample from $\bar{p}$. For example, $p$ may be biased in some way known to us. How could we correct for such a bias if we

just have access to the given graph $G$, but not to the underlying sampling mechanism? In order to tackle this problem, our general strategy is to transform $G$ into another graph $\bar{G}$ that “reflects properties of $\bar{p}$”, although the vertices still refer to the original sample points distributed according to $p$. We focus on volume and cut properties, as these are used in a large variety of machine learning algorithms. Our goal is that volumes and cuts of $\bar{G}$ reveal the same information on $\bar{p}$ as another graph would do that is directly built on a sample from $\bar{p}$. We provide a solution that provably achieves this goal in the limit of increasing sample size. We first define a vector $f$ of vertex weights that reflects the continuous volume properties of $\bar{p}$. Then we “merge” these vertex weights into $G$ by re-weighting its edges in such a way that the modified graph $\bar{G}$ attains $f$ as its degree vector. Any such “merging operation” implicitly sets all volumes in $\bar{G}$ corresponding to $\bar{p}$. The crux is to construct a merging operation that simultaneously ensures that the cut weights in $\bar{G}$ correspond to the continuous cut properties of $\bar{p}$. We provide such an operation by defining $\bar{G}$ as the “f-adjusted graph of $G$”.

The above delineates the *geometric interpretation* of *f*-adjusting. It allows to think of transforming $G$ into $\bar{G}$ as of modifying the underlying density from $p$ to $\bar{p}$. This provides all the intuition that we need in order to choose $f$ in a meaningful way and to interpret volumes and cut weights in the *f*-adjusted graph. Although this motivation is purely geometric, it turns out that *f*-adjusting also has appealing algebraic properties. We denote by the term “*f*-adjusted Laplacian” the normalized Laplacian matrix of the *f*-adjusted graph. The *algebraic interpretation* shows that all *f*-adjusted Laplacians that can be obtained from $G$ represent a natural family of diagonal perturbations of the normalized Laplacian of $G$. Thus we can think of transforming $G$ into $\bar{G}$ as of a meaningful modification along the main diagonal of the original normalized Laplacian. The algebraic results do not require that $G$ is a geometric graph.

<footnote>Proceedings of the 31st International Conference on Machine Learning, Beijing, China, 2014. JMLR: W&CP volume 32. Copyright 2014 by the author(s).</footnote>
These interpretations allow us to apply f-adjusting to a variety of problems from machine learning:

(a) Correcting for sampling bias: we obtain a method to correct for a sampling bias in graph-based algorithms.

(b) Spectral clustering: although $G$ is built on a fixed sample drawn from $p$, we can apply spectral clustering as if the graph were built on another sample drawn from density $\bar{p}$.

(c) Multi-scale analysis: the original density $p$ can be modified in various ways, for example by a convolution. Let $k_h$ denote some convolution kernel of bandwidth $h$. Estimates on $p * k_h$ can be extracted from the graph by averaging over neighborhoods. f-adjusting can then be applied in order to merge these estimates into edge weights appropriately, so that the new volumes and cut weights represent $p * k_h$.

(d) Manifold learning and clustering: there is a complicated interplay between the geometric structure of the data and the sampling density. It can be helpful to separate these two aspects, for example if we are interested in a function $f$ of which we only know $f(x_i)$ with $x_i$ sampled according to some unknown sampling density on a manifold. We would like to remove the artifacts induced by the sampling density and construct a situation that looks like as if the sample points $x_i$ were distributed uniformly.

## 2. Applications

Before we dive into the theoretical analysis, we motivate the reader by two example applications.

### 2.1. Removing density information

In some scenarios the sample distribution does not provide the structural information that we are interested in. For example in sea temperature recording or general wireless sensor networks one has to deal with measurement values $t_i$ at random spatial positions $x_i$. The goal is to study the measurement values without any bias introduced by their random positions. If the measurements were taken at uniform positions, then one could apply spectral clustering. But any non-uniform spatial distribution distorts all cut weights. There is no obvious mechanism to compensate for this influence. We demonstrate this effect in an image segmentation task. The classical spectral clustering for image data on a $d$-dimensional grid (Shi & Malik, 2000) constructs an $r$-graph of radius $r$ on the pixel positions. Edge weights are defined by the products $w_{ij} := \text{sim}_s(x_i, x_j) \cdot \text{sim}_v(t_i, t_j)$ of spatial similarities $\text{sim}_s(x_i, x_j) := \exp(-0.5\|x_i - x_j\|^2/\sigma_s^2)$ and value similarities $\text{sim}_v(t_i, t_j) := \exp(-0.5\|t_i - t_j\|^2/\sigma_v^2)$. The normalized cuts in the resulting graph provide useful clustering information on the intensity values. But this only holds because the spatial similarities of a grid have a uni-

<figure><img src="image_3.png" /><figcaption>Figure 1. Top left: original image of a cloud, unknown to us. Top right: 5000 sample points drawn from two Gaussians, colors indicating intensity values. We can access data only at these positions. Bottom left: spectral image clustering applied to the non-uniform sample positions. We show the heat plot of the NCut score vector (eigenvector that solves the relaxed minimum normalized cut problem). The scores are biased to a wrong segmentation. Bottom right: heat plot of the NCut score vector of our density-corrected graph. It separates the cloud from its background because the spatial bias is removed.</figcaption></figure>

form impact on the product in $w_{ij}$. It does not generalize to the case where the sample positions are distributed non-uniformly. In this case the spatial similarities distort the cut weights and hence the clustering result in an undesired way. Consider the image in Figure 1 (top left), and assume that its intensity values are not given at the positions of a grid, but only at sample positions drawn from an aggregation of two Gaussians (top right). In order to remove the spatial unbalancedness, we suggest to proceed as follows:

(1) Build the neighborhood graph $G$ on the sample points from only their spatial similarities $w_{ij} := \text{sim}_s(x_i, x_j)$.

(2) With $\mathbf{d}$ the vector of vertex degrees, create the $\mathbf{d}^{-1}$-adjusted graph $\bar{G}$. It provides the edge weights $\bar{w}_{ij}$. We show below that these weights remove the density information from the original volumes and cut weights of $G$.

(3) Define the final edge weights by $\bar{w}_{ij} \cdot \text{sim}_v(t_i, t_j)$.

(4) Apply spectral clustering to the resulting graph.

This approach removes the influence of the spatial distribution from the final edge weights. It solely considers intensity values. Figure 1 (bottom right) shows that this leads to the correct segmentation, whereas the biased segmentation provided by the original graph is not correct (bottom left).

### 2.2. Correcting for a sampling bias

Consider a data set in which some areas are known to be over- or underrepresented. For example, a poll among shop
<figure><img src="image_4.png" /><figcaption>Figure 2. Top left: exemplary sample from true density $\bar{p}$ that we cannot access. Top right: 3000 sample points from biased density $p = b \cdot \bar{p}$ that underrepresents around $x \approx 0$. This is the sample we can access. Middle right: cut weights of vertical cuts at $x \in [-4, 4]$, for a single graph drawn from each the true and the biased density, and for the $\mathbf{db}^{-2}$-adjusted graph. Bottom right: same, averaged over 20 runs. Middle left: heat plot of the NCut score vector of the biased graph, giving the wrong vertical cut. Bottom left: heat plot of the NCut score vector of the $\mathbf{db}^{-2}$-adjusted graph. It identifies the correct clusters, since the bias is removed.</figcaption></figure>

customers in the morning will particularly have the ages 20 to 30 being underrepresented. How can we correct for this in a graph-based learning scenario? Let $p = b \cdot \bar{p}$ denote the erroneous density that we can access under some bias $b: \mathbb{R}^d \to \mathbb{R}_{>0}$ and $\bar{p}$ the true density that we cannot access. Using our framework, one can use any estimate of $b$ in order to compensate for the bias. This can be achieved by the f-adjusted graph for $\mathbf{f} = \mathbf{db}^{-2} := (d_i/b(x_i)^2)_i$. It provides volumes and cut weights just as if the sample points were drawn from $\bar{p}$ instead of $p$. Since f-adjusting does not require any coordinates of the sample points, the bias $b$ can also be given as external knowledge on the vertices.

Consider the example in Figure 2. It shows two Gaussians (top left) that are underrepresented around $x \approx 0$ due to bias $b(x, y) = \min\{1, (2+3|x|)/8\}$ (top right). The minimum normalized cut of a graph built on the biased sample is misdirected by this bias to the wrong vertical clusters (middle left). However, the f-adjustment appropriately “re-pairs” the volumes and cut weights in the graph. Now the correct horizontal cut is revealed (bottom left).

### 3. The f-Adjusted Graph Laplacian

In this section we formally define the f-adjusted graph and its Laplacian. f-adjusting addresses two goals. The first goal is to re-weight the edges of a given graph in such a way that the new degree vector equals the vector $\mathbf{f}$. This implicitly sets the volumes of all vertex subsets according to $\mathbf{f}$. The second goal is to provide a geometric interpretation that simultaneously relates the new cut weights to $\mathbf{f}$. As shown in Section 5, f-adjusting indeed fits both volumes and cut weights to $\mathbf{f}$ in a way that allows for a geometric interpretation: both quantities represent one and the same modified underlying density.

#### 3.1. Graph notation

For any matrix $A = [a_{ij}]_{ij} \in \mathbb{R}^{n \times n}$ let $A \ge 0$ denote that all entries are non-negative. For vector $\mathbf{b} \in \mathbb{R}^n$ we refer by $\mathrm{diag}(\mathbf{b}) \in \mathrm{diag}(\mathbb{R}^n)$ to the corresponding diagonal matrix. For any $q \in \mathbb{R}$ we define $\mathbf{b}^q := (b_i^q)_i$ element-wise, as well as the product $\mathbf{bc} := (b_i c_i)_i$ of vectors $\mathbf{b}, \mathbf{c} \in \mathbb{R}^n$. We define the set of **graph matrices** as $\mathbf{W} := \{X \in \mathbb{R}^{n \times n} | X = X^T, X1 > 0\}$. We also study its generalization to the set of **weak graph matrices** $\mathbf{W}_{\odot} := \{X \in \mathbb{W} + \mathrm{diag}(\mathbb{R}^n) | X1 > 0\}$, whose elements further allow for negative diagonal entries as long as all row sums remain positive. Obviously $\mathbb{W} \subset \mathbf{W}_{\odot}$. To each $\mathbf{W} \in \mathbf{W}_{\odot}$ there corresponds an undirected weighted graph $\mathcal{G}(\mathbf{W}) := (V, E, \mathbf{W})$ that has $\mathbf{W}$ as its weighted adjacency matrix, and edge set $E := \{ij | w_{ij} \neq 0\}$. The degree of vertex $i \in V$ is $d_i := \sum_{j \in V} w_{ij} > 0$, leading to the all-positive degree vector $\mathbf{d} = \mathbf{W}1$. The volume of $S \subseteq V$ is defined as $\mathrm{vol}_G(S) := \sum_{i \in S} d_i$. Any partition $V = S \cup \bar{S}$ is a cut of weight $\mathrm{cut}_G(S, \bar{S}) := \sum_{i \in S, j \in \bar{S}} w_{ij}$. For the two frequently used vectors $\mathbf{f} = (f_i)_i$ and $\mathbf{d} = (d_i)_i$ we set $\mathbf{F} := \mathrm{diag}(\mathbf{f})$ and $\mathbf{D} := \mathrm{diag}(\mathbf{d})$.

#### 3.2. Definition of the f-adjusted graph

From now on fix some $\mathbf{W} \in \mathbb{W}$ and set $\mathbf{G} := \mathcal{G}(\mathbf{W})$. There are two straightforward methods for modifying $\mathbf{G}$'s edge weights (= entries in $\mathbf{W}$) in order to fit all vertex degrees (= row/column sums of $\mathbf{W}$) to some prescribed vector $\mathbf{f}$. f-adjusting combines these two methods because they mutually compensate their respective drawbacks.

**f-selflooping.** The naive strategy to adjust the vertex degrees of the graph $\mathcal{G}(\mathbf{W})$ to any prescribed vector $\mathbf{f} \in \mathbb{R}_{>0}^n$ is by modifying selfloops: fix all off-diagonal entries in $\bar{\mathbf{W}}$, and set its main diagonal such that the row sums equal $\mathbf{f}$:

$$ \mathbf{W}_{\odot} := \mathbf{W} - \mathbf{D} + \mathbf{F} \in \mathbf{W}_{\odot}. $$

This yields the vertex degrees $\mathbf{W}_{\odot}1 = \mathbf{f}$ exactly. We refer to $\mathcal{G}(\mathbf{W}_{\odot})$ as the f-selflooped graph. Despite of its positive row sums, this approach can force some entries on the
main diagonal of $W_f^\circ$ to take negative values. We can fix this by considering $cf$-selflooping for $c > 0$. This yields vertex degrees $W_{cf}^\circ 1 = cf$, and it is straightforward to see that the main diagonal of $W_{cf}^\circ$ is non-negative if and only if $c \ge \max_{i \in V}\{(d_i - w_{ii})/f_i\}$. The drawback is that selfloop weights only affect volumes but not the cut weights. In general there is no relation between volumes and cut weights in the $f$-selflooped graph.

**f-scaling.** Another natural strategy to adapt the row sums of $W$ to any prescribed vector $f \in \mathbb{R}_{>0}^n$ is by proportional scaling, that is by considering $FD^{-1}W$. This matrix yields the row sums $f$ exactly, but is not symmetric in general. For that reason, we use a (multiplicative) symmetrization:

$$ \tilde{W}_f := \sqrt{FD^{-1}W} \sqrt{FD^{-1}} \in W. $$

We refer to $\mathcal{G}(\tilde{W}_f)$ as the $f$-scaled graph. The drawback of this approach is that its degree vector $\tilde{d} = \tilde{W}_f 1$ does not equal $f$ exactly, since $\tilde{d}_i = \sum_{j \in V} w_{ij} \sqrt{(f_i f_j)/(d_i d_j)}$ differs from $f_i$ in general. In the following let $\tilde{D}_f := \text{diag}(\tilde{d})$.

**f-adjusting.** For any $f \in \mathbb{R}_{>0}^n$ and $c > 0$, we combine both approaches by first applying $f$-scaling, followed by $cf$-selflooping. This defines the weak graph matrix

$$ \overline{W}_{f,c} := \tilde{W}_f - \tilde{D}_f + cF \in W_{\odot}. $$

We refer to $\mathcal{G}(\overline{W}_{f,c})$ as the $(f, c)$-adjusted graph of $G$, and for the case $c = 1$ simply as the $f$-adjusted graph. All vertex degrees are positive because $\overline{W}_{f,c} 1 = cf > 0$. The $(f, c)$-adjusted graph has no negative selfloop if and only if $c \ge \max_{i \in V}\{(d_i - \tilde{w}_{ii})/f_i\} =: c^*$. In this case it holds that $\overline{W}_{f,c} \in W$. Although this definition of $f$-adjusting appears somewhat artificial at the first glance, it reveals appealing properties in its algebraic and geometric interpretation.

**f-adjusted Laplacian.** For $W \in W$, the unnormalized Laplacian matrix $L(W) := D - W$ and the normalized Laplacian matrix $\mathcal{L}(W) := I - \tilde{W}_1$ are powerful and well-studied objects (see Chung, 1997). We define

$$ \mathcal{L}_f(W) := \mathcal{L}(\overline{W}_{f,1}) $$

for any $f \in \mathbb{R}_{>0}^n$ as the $f$-adjusted Laplacian of $\mathcal{G}(W)$.

## 4. Algebraic Interpretation

All diagonal modifications of the form $W + X \in W_\odot$ for $X \in \text{diag}(\mathbb{R}^n)$ obviously represent all possible self-loop modifications of $W$, that is $f$-selflooping for every $f \in \mathbb{R}_{>0}^n$. In this section, we derive a similar result for the normalized Laplacian: all diagonal modifications of the form $\mathcal{L}(W) + X \in \mathcal{L}(W_\odot)$ characterize all possible $f$-adjustments of $W$. In this sense, $f$-adjusting deals with diagonal modifications of the normalized Laplacian just in the same way as $f$-selflooping deals with diagonal modifications of the adjacency matrix. This shows that $f$-adjusting is a natural graph modification. All proofs and further details are provided in the supplement.

### 4.1. $(f, c)$-adjusting is as powerful as $f$-adjusting

The following lemma shows that it is sufficient to focus on $f$-adjusting in order to study every $(f, c)$-adjusting.

**Lemma 4.1 (Scaling Relation).** For all $W \in W$, $f \in \mathbb{R}_{>0}^n$ and $c > 0$ it holds that

$$ \mathcal{L}(\overline{W}_{f,1}) = c \cdot \mathcal{L}(\overline{W}_{f,c}). $$

Consequently, every $\mathcal{L}(\overline{W}_{f,c})$ has the same eigenvectors as $\mathcal{L}(\overline{W}_{f,1})$, with all eigenvalues scaled by $c^{-1}$. In particular the order of the eigenvalues is preserved. This implies further that $\mathcal{L}(\overline{W}_{f,c})$ inherits many spectral properties from $\mathcal{L}(\overline{W}_{f,c^*})$ such as its positive semi-definiteness and that $\sqrt{f}$ is an eigenvector to eigenvalue 0 whose multiplicity matches the number of connected components in $\mathcal{G}(W)$. For that reason, the spectral analysis of any $(f, c)$-adjusted graph can be reduced to the $f$-adjusted graph. In particular it does not matter whether or not it has negative selfloops.

### 4.2. $f$-adjustments are diagonally modified Laplacians

The next lemma shows that every $f$-adjustment represents a meaningful modification along the main diagonal of $\mathcal{L}(W)$.

**Lemma 4.2 (Diagonally Modified Laplacian).** For all $W \in W$ and $f \in \mathbb{R}_{>0}^n$ it holds that

$$ \mathcal{L}_f(W) = \tilde{D}_f F^{-1} - \tilde{W}_1. $$

The main insight provided by Lemma 4.2 is that we can think of $f$-adjusting as of replacing the identity matrix in $\mathcal{L}(W) = I - \tilde{W}_1$ with the new matrix $\tilde{D}_f F^{-1}$. Its diagonal entries reflect the relative deviation $\tilde{d}/f$ between the intended new degrees $f$ and the degrees $\tilde{d}$ that are obtained by $f$-scaling without subsequent $f$-selflooping. Note that $f$-scaling alone does not reveal any clear relation to $\mathcal{L}(W)$, only its combination with the subsequent $f$-selflooping collapses down to this “simple” algebraic form. We denote any modification along the main diagonal of a matrix as a diagonal modification. Whenever it exceeds just a tiny perturbation, it has a strong non-linear impact on the spectrum: the eigenvalues can only loosely and abstractly be bounded by Horn’s inequalities (Bhatia, 2001), and nothing is known on the impact on the eigenvectors.

### 4.3. Diagonally modified Laplacians are $f$-adjustments

Lemma 4.2 shows that every $f$-adjusting can be understood as a diagonal modification of the form $\mathcal{L}(W) + X = \mathcal{L}(A)$ for some $X \in \text{diag}(\mathbb{R}^n)$ and $A \in W_\odot$. This rises the question whether also the converse is true: does every such diagonal modification imply that $A$ is an $f$-adjustment of $W$? The following theorem gives a positive answer.
**Theorem 4.3 (Complete Characterization).** For any $W \in \mathbb{W}$ with $\mathcal{L}(W) \neq 0$ consider all solutions $(X, A, c) \in \text{diag}(\mathbb{R}^n) \times \mathbb{W}_{\ominus} \times \mathbb{R}$ of the equation

$$ \mathcal{L}(W) + X = c \cdot \mathcal{L}(A). $$

For $c \le 0$ no solution exists. For $c > 0$, all solutions are given by $A = \bar{W}_{f,c}$ and $X + I = \tilde{D}_f F^{-1} = Z$ for any choice of $f \in \mathbb{R}^n_{>0}$. For connected $\mathcal{G}(W)$, choosing $f$ is equivalent to choosing any $Z \in \text{diag}(\mathbb{R}^n_{>0})$ with spectral radius $\rho(Z^{-1}\tilde{W}_1) = 1$. This determines $\sqrt{f}$ uniquely (up to scaling) as the eigenvector corresponding to the simple eigenvalue 1 of the matrix $Z^{-1}\tilde{W}_1$.

Theorem 4.3 gives two further results for connected graphs:

(i) In order to transform $\mathcal{L}(W)$ by a diagonal modification into another normalized Laplacian matrix, we are free to orient the identity matrix in $\mathcal{L}(W) = I - \tilde{W}_1$ toward any “direction” $Y \in \text{diag}(\mathbb{R}^n_{>0})$. But at the same time this determines only a single possible “distance” $\mu := \rho(Y^{-1}\tilde{W}_1)$ for which indeed it holds that $\mu Y - \tilde{W}_1 \in \mathcal{L}(\mathbb{W}_{\ominus})$, because only then $\rho((\mu Y)^{-1}\tilde{W}_1) = 1$. Moreover, it follows that $\mu Y - \tilde{W}_1 = \mathcal{L}(\bar{W}_{f,1})$, where $\sqrt{f}$ is the eigenvector of $(\mu Y)^{-1}\tilde{W}_1$ corresponding to the simple eigenvalue 1.

(ii) We get deeper insights into the structure of the deviation error $\bar{d}/f$ under $f$-scaling: given any vector of relative deviations $\xi \in \mathbb{R}^n_{>0}$, there exists a unique (up to scaling) vector $f \in \mathbb{R}^n_{>0}$ that satisfies $\bar{d}/f = \alpha\xi$ for a unique $\alpha > 0$. In particular this implies that no vector $f \neq d$ can be obtained by $f$-scaling exactly as the new degree vector $\bar{d}$, not even up to scaling, because the zero-deviation case $\xi = 1$ is already reached for $f = d$.

These two results generalize to unconnected graphs by applying them individually to each connected component. In particular the uniqueness is affected in the way that $f$ may be scaled individually within each connected component.

## 4.4. Application: f-adjusted spectral clustering

We are going to show that the spectral clustering technique generalizes to weak graph matrices. This allows to apply it to any $f$-adjusted graph. Spectral clustering of a connected graph $G = (V, E, W)$ relies on a relaxation for solving the NP-hard problem of minimizing the normalized cut value

$$ \text{NCut}(S, \bar{S}) = \text{cut}_G(S, \bar{S}) (\text{vol}_G(S)^{-1} + \text{vol}_G(\bar{S})^{-1}) $$

over all $S \subseteq V$ and $\bar{S} := V \setminus S$. Instead of the optimal characteristic vector, the relaxation determines a real-valued score vector $s := \sqrt{D^{-1}v_2}$, where $v_2$ denotes the second smallest eigenvector of $\mathcal{L}(W)$. Thresholding is used to define $S$ from $s$. We refer to $s$ as the **NCut score vector**. Variants use multiple smallest eigenvectors $v_2, v_3, \dots, v_\ell$ for embedding vertex $i \in V$ in $\mathbb{R}^{\ell-1}$ at the $i$'th coordinate entries of $v_2, \dots, v_\ell$, and then apply for example $k$-means on the embedded points in order to identify $k$ clusters.

Since the $(f, c^*)$-adjusted graph has no negative selfloops, we can apply any spectral clustering technique to $\mathcal{G}(\bar{W}_{f,c^*})$ as usual. Lemma 4.1 shows that $\mathcal{L}(\bar{W}_{f,c^*})$ and $\mathcal{L}_f(W)$ share the same eigenvectors in the same order. Thus, the NCut score vector does not change by considering $\mathcal{L}_f(W)$ instead of $\mathcal{L}(\bar{W}_{f,c^*})$. Consequently, in all variants of spectral clustering we can simply replace $\mathcal{L}(W)$ by $\mathcal{L}_f(W)$ for any $f \in \mathbb{R}^n_0$ in order to study the normalized cuts of the graphs $\mathcal{G}(\bar{W}_{f,c^*})$ for all $c > 0$ simultaneously, even though they contain negative selfloops for $c < c^*$.

# 5. Geometric Interpretation

Assume that we are given a graph $G$ plus the meta-information that it is some neighborhood graph built on an unknown sample from an unknown density. Our goal is to infer from $G$ about structural properties of the underlying density. The additional meta-information allows to interpret certain quantities in $G$, such as volumes and cut weights, in a meaningful way.

In the following we show that our modification of $G$ still keeps the geometric interpretation of volumes and cut weights in the modified graph $\bar{G}$. Thus we can think of modifying edge weights as of modifying the underlying density, although the unknown sample points remain fixed at their original positions. These insights provide answers to the following questions: how to interpret clustering results for $\bar{G}$? How to choose $f$ in a meaningful way? Can we use $f$ to “merge” external information into the graph in order to extract hidden information from $G$?

## 5.1. Geometric graphs

In a random geometric graph, each vertex $i \in V$ is identified with a sample point $x_i \in \mathbb{R}^d$ drawn i.i.d. according to some continuous probability density $p: \mathcal{X} \to \mathbb{R}$ on a compact domain $\mathcal{X} \subseteq \mathbb{R}^d$. The edge set and weights are given from the construction of a neighborhood graph on these sample points. Prominent choices are:

(i) the **Gaussian graph**: the complete graph with Gaussian weights $w_{ij} = \exp(-\frac{1}{2}\|x_i - x_j\|^2/\sigma^2)$)

(ii) the **unweighted r-graph**, which has an edge $ij$ of unit weight if and only if $\|x_i - x_j\| \le r$

(iii) the **Gaussian weighted kNN graph**, which has an edge $ij$ of Gaussian weight if and only if $x_j$ is among the nearest $k$ neighbors of $x_i$ or vice versa.

The results in this section refer to the limit case $n \to \infty$. We consider the following **convergence conditions**: for the Gaussian graph we require that $n \to \infty$, $\sigma \to 0$, $n\sigma^{d+1}/\log n \to \infty$. For the $r$-graph that $n \to \infty$, $r \to 0$, $nr^{d+1}/\log n \to \infty$. For the Gaussian weighted $k$NN graph that $n \to \infty$, $k \to \infty$, $k/\log n \to \infty$, $n\sigma^{d+1} \to \infty$, $(k/n)^{1/d} \ge \sigma^\alpha$ for some $\alpha \in ]0, 1[$.
We require that the following regularity conditions are satisfied: $\mathcal{X}$ has a smooth boundary with bounded curvature. $p$ is twice differentiable with bounded gradient, and bounded away from zero, that is $p(x) \ge p_{\min} > 0$ for $x \in \mathcal{X}$.

## 5.2. Different views on graphs

We introduce a distinction between three different “views” on the graph. These views help us to interpret graph modifications in terms of modifications applied to the underlying probability distribution.

**Discrete graph view.** This is the well-known setting of the discrete graph with $\text{cut}_G$ and $\text{vol}_G$ as introduced in Section 3.1. Specifically, we do not have access to the information about the underlying space. This is the standard situation for algorithms like spectral clustering or Isomap. In particular, in the graph view we cannot evaluate index sets of the form $\{i \mid x_i \in A\}$ where $A$ is a subset of $\mathbb{R}^d$.

**Continuous space view.** Here we define volumes and cuts with respect to the underlying density $p$. Specifically, we define the **p-volume** of a measurable $A \subseteq \mathcal{X}$ as $\text{vol}_p(A) := p(A) = \int_A p(x) \, dx$. Given a hyperplane $H$, we interpret it as a cut of the underlying space in the two half-spaces denoted by $H^+$ and $H^-$. We denote its corresponding **p-weight** as $\text{cut}_p(H) := \int_H p(x) \, dx$. In this work we focus on cuts induced by hyperplanes. We believe that all stated results can be generalized to any other cut surfaces that are sufficiently regular.

**Interspace view.** This view “mediates” between the discrete and continuous world. Its objects are not accessible to algorithms on graphs, but they serve as a theoretical construction to express the relationships between discrete and continuous cuts and volumes. In this view, we assume that we can evaluate index sets of the form $V(A) := \{i \mid x_i \in A\} \subseteq V$ where $A$ is a subset of $\mathbb{R}^d$. For any vector $\mathbf{d}$ and any sample drawn from $p$, we refer to $\text{vol}_{\mathbf{d}}(A) := \text{vol}_G(V(A)) = \sum_{x_i \in A} d_i$ as the **interspace volume** of $A$ with respect to vector $\mathbf{d}$. Intuitively, it sums over the degrees as provided in the discrete graph view, while the sum is indexed by the sample points as provided by the continuous space view. Moreover, let $\text{cut}_W(H) := \text{cut}_G(V(H^-), V(H^+)) = \sum_{x_i \in H^-, x_j \in H^+} w_{ij}$ denote the **interspace cut weight** of the cut $H$ with respect to weight matrix $W$. Again, it sums over the edge weights as in the graph view, while the sums are indicated by the sample points in the space view.

## 5.3. Geometric problem statement

We already stated the problem informally as modifying a given neighborhood graph from density $p$ such that its volumes and cuts “looks like” those of a neighborhood graph

from an alternative density $\bar{p}$. We are now ready to state this requirement formally by using the interspace view concept.

**Geometric Graph Adjustment Problem** Given a neighborhood graph $G = (V, E, W)$ built on a sample from density $p: \mathcal{X} \to \mathbb{R}$, and a second density $\bar{p}: \mathcal{X} \to \mathbb{R}$. How can we define a modified graph $\bar{G} = (\bar{V}, \bar{E}, \bar{W})$ such that, in the limit case, $\text{vol}_{\bar{d}}(A) \approx \text{vol}_{\bar{p}}(A)$ for all measurable sets $A \subseteq \mathcal{X}$ and $\text{cut}_{\bar{W}}(H) \approx \text{cut}_{\bar{p}}(H)$ for all cuts $H$?

The vertex set and the corresponding sample points remain fixed throughout the modification. All that is allowed to change are edges and edge weights. As the term modification indicates, $\bar{G}$ should stay “similar” to $G$. This can be quantified in different ways. Here, we focus on the constraint that the edge sets $\bar{E}$ and $E$ coincide up to selfloops.

It is well known that $|V(A)|$ is proportional to $p(A)$ in expectation and that the degree $d_i$ of vertex $i$ can serve, up to global scaling, as a consistent estimate of the underlying density $p(x_i)$ at sample point $x_i$. This motivates the following obvious approach to fit $\bar{G}$'s interspace volumes to $\bar{p}$-volumes: determine $f_i$ proportional to $\bar{p}(x_i)$, and use $\mathbf{f}$-selfflooping to let the modified graph $\bar{G}$ attain $\mathbf{f}$ as its degree vector. However it is not obvious how to define $\bar{G}$ such that further the interspace cut weights in $\bar{G}$ correspond to $\bar{p}$-weights. We will see in the following that this is provided by $\mathbf{f}$-scaling. Since $\mathbf{f}$-adjusting combines both approaches, it provides both goals simultaneously. Moreover, if we want to avoid negative selfloops in $\bar{G}$, then we can apply $(\mathbf{f}, c^*)$-adjusting, which keeps all cut weights and volume proportions intact; it just scales all volumes by $c^*$.

## 5.4. Convergence of f-adjusted volumes

Recall that the interspace volume of any $A \subseteq \mathbb{R}^d$ is defined as $\text{vol}_d(A) = \sum_{x_i \in A} d_i$. This expression already shows how we can intuitively think of discrete vertex degrees as a weight distribution on the underlying space: the positions of the sample points are distributed according to density $p$, and each sample point is additionally weighted by $d_i$. Since the degree $d_i$ can serve as a density estimate for $p(x_i)$, this weighting brings in an additional factor $p$. Therefore we expect that the interspace volume $\text{vol}_d(A)$ behaves like the $p^2$-volume $\int_A p^2(x) \, dx$ in the limit case. Moreover, if we consider any graph modification that changes the original degree vector $\mathbf{d}$ into $\mathbf{f}$, then this affects the above expression by replacing each individual $d_i$ by $f_i$, while the index set $\{i \mid x_i \in A\}$ remains the same. Thus, if the new vertex degrees $f_i$ are given as $f_i := f(x_i)$ for some continuous function $f: \mathcal{X} \to \mathbb{R}_{>0}$ then we expect that the interspace volume $\text{vol}_f(A)$ behaves like the $fp$-volume $\int_A f(x)p(x) \, dx$ in the limit case. Indeed this intuition is correct. The following proposition shows that the interspace volume and the continuous $fp$-volume are proportionally related as $n \to \infty$.
**Proposition 5.1. (Interspace Volumes)** Let $G$ be a geometric graph based on $n$ vertices drawn according to $p$. Denote its degree vector by $\mathbf{d}$ and let $f : \mathcal{X} \to \mathbb{R}_{>0}$ be a continuous function. Define the vector $\mathbf{f} := (f(x_i))_i$, and let $\bar{G}$ be any graph modification of $G$ that attains the degrees $\bar{\mathbf{d}} = \mathbf{f}$. Then, under the convergence conditions mentioned above, for any measurable $A \subset \mathbb{R}^d$, $C \cdot \text{vol}_{\bar{\mathbf{d}}}(A) \to \text{vol}_{f,p}(A)$ almost surely as $n \to \infty$, where $C$ is a scaling constant that depends on $n, d$.

This result shows that we can modify the graph such that the interspace volume of the new graph corresponds to any density $\bar{p}$ we would like, as long as $\bar{p}$ is absolutely continuous with respect to $p$ (that is, sets $A$ with $p(A) = 0$ also have $\bar{p}(A) = 0$). In Section 5.6 and Section 2 we outline a number of important consequences and applications.

### 5.5. Convergence of f-adjusted cut weights

In order to study the cut weights after $(\mathbf{f}, c)$-adjusting, we can solely focus on $\mathbf{f}$-scaling, since it provides exactly the same cut weights. Again we can derive the intuition from the interspace view: let $\text{cut}_W(H) = \sum_{x_i \in H^{-}, x_j \in H^{+}} w_{ij}$ denote the interspace cut weight according to any hyperplane $H$. $\mathbf{f}$-scaling replaces each edge weight $w_{ij}$ in this sum by the new weight $\tilde{w}_{ij} := w_{ij} \cdot \sqrt{(f_i f_j)/(d_i d_j)}$. Assume that the original interspace cut weight $\text{cut}_W(H)$ behaves like the $p^2$-weight $\int_H p^2(x) dx$ in the limit. Then we expect due to $\sqrt{(f_i f_j)/(d_i d_j)} \sim f p^{-1}$ that the modified interspace cut weight $\text{cut}_{\tilde{W}}(H)$ behaves like the $fp$-weight $\int_H f(x)p(x) dx$. The following proposition makes this intuition explicit, by relating the interspace cut weights after $\mathbf{f}$-scaling to the continuous $fp$-weights.

**Proposition 5.2. (Interspace Cuts)** Let $G$ be a geometric graph based on $n$ vertices drawn according to $p$. Denote its degree vector by $\mathbf{d}$ and let $f: \mathcal{X} \to \mathbb{R}_{>0}$ be a continuous function that is twice differentiable and has bounded gradient. Define the vector $\mathbf{f} := (f(x_i))_i$, and let $\bar{G}$ be the corresponding $\mathbf{f}$-scaled graph with weight matrix $\tilde{W}_f$. Consider a hyperplane $H$ in $\mathbb{R}^d$. Then, under the convergence conditions mentioned above, $C \cdot \text{cut}_{\tilde{W}_f}(H) \to \text{cut}_{f,p}(H)$ almost surely as $n \to \infty$, where $C$ is a scaling constant that depends on $n, d$.

The proofs of both propositions in this section are based on the arguments in Maier et al. (2009), who study volumes and cut weights in neighborhood graphs.

Note that the results on the interspace cut weights are perfectly aligned with the results on the interspace volumes in the sense that both share the same integrand $\int f(x)p(x)dx$. Since $\mathbf{f}$-adjusting provides the same cut weights as $\mathbf{f}$-scaling, and further degree vector $\mathbf{f}$, we get that the interspace volumes and interspace cuts of the $\mathbf{f}$-adjusted graph both converge to the continuous $fp$-volumes and $fp$-cuts, respectively (up to scaling).

Further, $(\mathbf{f}, c)$-adjusting simply puts another global scaling factor $c$ on all volumes.

### 5.6. Interesting consequences

The intuitive interpretation of the geometric results is as follows: the continuous volumes and cuts change under $\mathbf{f}$-adjusting from $\int p^2$ to $\int fp$. This implies a number of interesting special cases:

(1) In the original graph (case $\mathbf{f} = \mathbf{d}$), both interspace volumes and interspace cuts correspond to the continuous quantities of the density $p^2$. This shows that the original notion of volume and cut in the graph has an artifact in the geometric setting in the sense that it does not correspond to volumes according to the original density, but to the squared density. See below for an illustration.

(2) $\mathbf{f}$-adjusting to uniform vertex degrees $\mathbf{f} = 1$ corresponds to the continuous quantities of the original density $p$. This choice removes the artifact of (1).

(3) $\mathbf{f}$-adjusting to inverse degrees $\mathbf{f} = \mathbf{d}^{-1}$ corresponds to a continuous density that is uniform. This can be used to remove density information altogether and make the underlying volumes behave “uniformly”. The density removal application in Section 2.1 relies on this strategy.

(4) More generally, all three above cases are modifications of the form $f(x) = g(p(x))$ for some $g: \mathbb{R}_{>0} \to \mathbb{R}_{>0}$. In practice, we can replace the $p(x)$ inside $g$ by any density estimate (such as the degrees in the original graph). If, additionally, $g(\alpha x) = \text{const}(\alpha)g(x)$ for all $\alpha > 0$, then any global scaling factor of the density estimate simply translates in a global scaling factor of the continuous quantities. This approach describes the target density $\bar{p}$ implicitly, relative to $p$. See the supplement for an application to the biased random walks studied by Zlatić et al. (2010), and for further details on the implicit definition of $\bar{p}$ from $p$.

(5) For any twice differentiable function $f: \mathcal{X} \to \mathbb{R}_{>0}$, define the new degree vector $\mathbf{f} = (f(x_i))_i$. In this setting, interspace cuts and volumes correspond to the quantities as provided by the density $\mathbf{f} \cdot p$. This case is particularly interesting for spatial corrections of biased sample data, as in Section 2.2, or if sample coordinates are known.

**Anomaly in Volumes and Cuts** As mentioned above in (1), cuts and volumes in the original graph represent integrals over the squared density $p^2$. To illustrate this anomaly, we consider in Figure 3 the density $p: [0, 1]^2 \to \mathbb{R}$, $p(x, y) = 2x$. Let $G = (V, E, W)$ denote the 200-NN graph built on 5000 sample points drawn from $p$ with Gaussian weighted edges ($\sigma = 0.03$).

**Volume anomaly:** assume that we want to partition $V$ into $L \cup R$ by splitting the sample points at some $x \in [0, 1]$ into vertices to its left $L$ and to its right $R$. The split point should be such that $L$ and $R$ cover the same probability
mass of the underlying density $p$. The correct approach is then to choose $L$ and $R$ such that $|L| \approx |R|$, which defines $x_2$ in Figure 3. In contrast to that, constraining to $\text{vol}_G(L) \approx \text{vol}_G(R)$ expands low density regions, since the split point $x_3$ is now implicitly set according to the squared density. Constraining to $\sum_{i \in L} d_i^{-1} \approx \sum_{j \in R} d_j^{-1}$ gives $x_1$. This lets $L$ and $R$ cover the same uniform amount of $p$'s support $\{x \in \mathbb{R}^d | p(x) > 0\}$, hiding any other density information. Note that the analytically expected value of $x_i$ is $0.5^{1/i}$, which gives roughly $(0.5, 0.71, 0.79)$.

**Cut weight anomaly:** consider vertical cuts at all positions $x \in [0.1, 0.9]$. Fitting a cubic polynomial $ax^3+bx^2+cx+d$ to the cut weights of the original graph gives, averaged over 10 runs, the coefficients $(-0.06, 1.30, -0.04, 0.01)$, which clearly shows the quadratic behavior. For the **1-adjusted** graph we get $(-0.08, -0.08, 1.13, -0.11)$, which is basically linear as expected, since it corresponds to $p$ without squaring. Finally, the **d**$^2$-adjusted graph provides $(1.21, 0.16, -0.06, 0.01)$ which has a significant cubic term as expected, since its cuts integrate over $p^3$.

Whenever we are interested in $p$ (which is usually the case), we must *not* consider the original graph, but the **1-adjusted** graph, as it provides the desired volumes and cuts. In particular, spectral clustering of a sample drawn from $p$ approximates the normalized cut of $p^2$, not of $p$. We can remove this artifact by replacing the typically used normalized Laplacian $\mathcal{L}(W)$ with the **1-adjusted** Laplacian $\mathcal{L}_1(W)$. But note that squaring $p$ can be *beneficial* for the clustering result, since it emphasizes high density clusters. However, we are no longer restricted to squaring: we can approximate the normalized cut of the modified density $p^r$ for any $r \in \mathbb{R}$ simply by taking the $d^{r-1}$-adjusted Laplacian for spectral clustering.

## 6. Further Related Work

Another approximative strategy to change the degree vector of a graph to some vector $f$ is iterative matrix scaling. Pukelsheim (2014) presents recent results on Iterative Proportional Fitting, which scales row and column sums alternately to $f$ until convergence. Knight et al. (2014) study a multiplicative symmetrization for $f = 1$. Iterative matrix scaling allows for a statistical interpretation, as it converges to the relative entropy closest solution among all non-negative matrices that provide the degree vector $f$ (Csiszar, 1975). However, in contrast to $f$-adjusting, no geometric interpretation of the resulting cut weights is known.

Bapat et al. (2001) study diagonal modifications of the unnormalized Laplacian. Note that $L(W) + X \notin L(W_\odot)$ for all $X \neq 0$, hence no diagonal modification of the unnormalized Laplacian represents the unnormalized Laplacian of any other graph. Nevertheless, diagonal modifications of $L(W)$ can provide useful meta-information

<figure><img src="image_5.png" /><figcaption>**Figure 3.** Left: 5000 sample points with heat colors indicating the degrees in the weighted kNN-graph. Dotted lines mark from left to right the estimated split points ($x_1, x_2, x_3 \approx (0.51, 0.7, 0.77)$) as described in text. Right: polynomials fitted to the cut weights of a single instance of the original graph $G$, its **1-adjustment** and its **d**$^2$-adjustment, for vertical cuts at $x \in [0.1, 0.9]$.</figcaption></figure>

on $G$. Wu et al. (2012) consider this diagonal modification for $X \ge 0$, and show how to interpret $(L(W) + X)^{-1}X$ as meaningful random walk absorption probabilities on $G$.

## 7. Discussion

We introduce $f$-adjusting as a transformation of a given graph $G$ into another graph $\bar{G}$. We show that $f$-adjusting corresponds to a natural diagonal modification of the normalized Laplacian that further allows for a clear geometric interpretation in terms of a density shift.

The *algebraic interpretation* shows that $f$-adjusting represents all diagonal modifications of $\mathcal{L}(W)$ of the form $\mathcal{L}(W) + X \in \mathcal{L}(W_\odot)$. This is the normalized Laplacian's pendant to the fact that $f$-selflooping represents all diagonal modifications of $W$ of the form $W + X \in W_\odot$. Thus, $f$-adjusting acts on the normalized Laplacian in the same way as $f$-selflooping acts on the adjacency matrix.

For the *geometric interpretation* we introduce an explicit distinction between three different views on a graph. In particular the interspace view is a helpful tool, since it serves as a bridge between the discrete graph world and the continuous world of density functions beneath. In terms of these views we express how $f$-adjusting represents a modification applied to the underlying density $p$. As a result, volumes and cuts in $\bar{G}$ refer to well-specified continuous quantities. This allows to apply any volume and cut based algorithm to the graph as if it were drawn according to another distribution.

More experiments and details can be found in the supplementary material.

**Acknowledgements** This research is supported by the German Research Foundation via the Research Unit 1735 "Structural Inference in Statistics: Adaptation and Efficiency" and grant LU1718/1-1.
References

Bapat, R. B., Kirkland, S. J., and Pati, S. The perturbed Laplacian matrix of a graph. *Linear and Multilinear Algebra*, 49(3):219–242, 2001.

Bhatia, R. Linear Algebra to Quantum Cohomology: The Story of Alfred Horn’s Inequalities. *The American Mathematical Monthly*, 108(4):289–318, 2001.

Chung, F. R. K. *Spectral Graph Theory*. American Mathematical Society, 1997.

Csiszar, I. *I*-Divergence Geometry of Probability Distributions and Minimization Problems. *The Annals of Probability*, 3(1):146–158, 1975.

Knight, P., Ruiz, D., and Uçar, B. A Symmetry Preserving Algorithm for Matrix Scaling (to appear). *SIAM Journal on Matrix Analysis and Applications*, 2014.

Maier, M., von Luxburg, U., and Hein, M. Influence of graph construction on graph-based clustering measures. In *Neural Information Processing Systems (NIPS)*, 2009.

Pukelsheim, F. Biproportional scaling of matrices and the iterative proportional fitting procedure. *Annals of Operations Research*, 215(1):269–283, 2014.

Shi, J. and Malik, J. Normalized Cuts and Image Segmentation. *IEEE Trans. Pattern Anal. Mach. Intell.*, 22(8): 888–905, 2000.

Wu, X., Li, Z., So, A., Wright, J., and Chang, S. Learning with Partially Absorbing Random Walks. In *Neural Information Processing Systems (NIPS)*, 2012.

Zlatić, V., Gabrielli, A., and Caldarelli, G. Topologically biased random walk and community finding in networks. *Physical Review E*, 82(6):066109, 2010.
# The f-Adjusted Graph Laplacian:
a Diagonal Modification with a Geometric Interpretation
(Supplement)

Sven Kurras

KURRAS@INFORMATIK.UNI-HAMBURG.DE

Ulrike von Luxburg

LUXBURG@INFORMATIK.UNI-HAMBURG.DE

Department of Computer Science, University of Hamburg, Germany

Gilles Blanchard

GILLES.BLANCHARD@MATH.UNI-POTSDAM.DE

Department of Mathematics, University of Potsdam, Germany

This supplement consists of three sections. Section A provides further applications that were skipped from the paper. Section B provides all proofs for paper's Section 4 (Algebraic Interpretation), including several further details. Section C provides details for paper's Section 5 (Geometric Interpretation).

## A. Further Applications

The first application studies a certain approach of biased random walks from our new geometric perspective. The second application deals with Semi-Supervised Learning.

### A.1. Topologically biased random walks

f-adjusting a graph changes most of the properties of the random walk on the graph. The stationary distribution is now obviously proportional to f rather than d. Hitting times and commute times are affected as well. Zlatić et al. (2010) study what they call “vertex centered biased random walks”: implicitly they modify the random walk matrix $P = D^{-1}W$ in a way that can be represented as $\tilde{P}_f = \tilde{D}_f^{-1}\tilde{W}_f$ for $\tilde{W}_f$ being the f-scaled graph with $f = d \odot \exp(2\beta \cdot d/\|d\|_\infty)$, where $\odot$ denotes the Hadamard product and $\exp(\cdot)$ is applied entry-wise. They observe that their particular choice leads to much better clustering results. They conclude this from studying eigenvalues and eigenvectors of the symmetrization $\tilde{D}_f^{-1/2}\tilde{W}_f\tilde{D}_f^{-1/2}$. Since these quantities correspond to the eigenvalues and eigenvectors of $\mathcal{L}(\tilde{W})$, their approach can be understood in terms of normalized cuts of the f-scaled graph. Based on our analysis, we can now give an intuitive explanation of their approach: their new random walk aims at studying the modified density $\tilde{p}(x) = \exp(2\beta \cdot p(x)/p_{max}) \cdot p(x)^2$. Hence, they amplify high-density regions in space exponentially stronger than low-density regions, which drastically strengthens any density cluster structure. Of course this only works to a certain extent, because it runs into the same problem as studying the density $p^r$ for large $r$: suppose that A and B denote disjoint geometric areas of two different clusters at slightly different “density plateaus”, that is, there exist $a < b$ such that the level sets to every threshold $t \in [a, b]$ only show, say, A but not B. For any moderate bias/amplification (“small $\beta > 0$”, or “small $r > 1$”), A and B are both emphasized over any much lower density areas between them. However, since A and B lie on different plateaus, they are affected in an increasingly different way for a larger amplification. If the amplification is too strong, then B is suppressed like other low-density areas, since A is favored too much over anything else.

Further, note that the exponential scaling in the modified random walk is applied to $p^2$ instead of $p$. Our technique suggests that applying the modification $f = \exp(\beta \cdot d/\|d\|_\infty)$ is a more natural choice, since it applies the intended exponential influence directly on $p$. This implies to study the modified density $\tilde{p}(x) = \exp(\beta \cdot p(x)/p_{max}) \cdot p(x)$, without squaring. Finally, one could fix the influence of the deviation $\tilde{d} \neq f$ on the spectrum by considering $\mathcal{L}_f(W)$ everywhere instead of $\mathcal{L}(\tilde{W}_f)$.
## A.2. Semi-Supervised Learning (SSL)

### A.2.1. MERGING VERTEX WEIGHTS INTO EDGE WEIGHTS

Assume that we have additional knowledge given as vertex weights. For example in network traffic analysis one has to deal with both edge congestion and vertex congestion. Moreover, it has been shown by Montenegro (2003) and Kannan et al. (2006) that considering both edge bottlenecks and vertex bottlenecks simultaneously can drastically improve mixing time bounds for random walks. However, many algorithms focus only on edge similarities, so does label propagation. In order to make the vertex weights visible to the algorithm, we have to transform them into edge weights. The trivial strategy of introducing selfloops does not affect label propagation at all, since selfloops do not change the probabilities of the random trajectories. Our framework suggests to merge vertex weights into edge weights via f-adjusting (where only the implied f-scaling takes an influence on label propagation).

<figure><img src="image_6.png" /><figcaption>**Figure 1.** Label propagation on original graph (left) and f-adjusted graph (right), showing Label Propagation on the two moons data set with one labeled point per class (shown in blue). Black squares mark misclassified vertices.</figcaption></figure>

As an example, consider the two-moons dataset for an unweighted 10NN graph on 1000 vertices with one labeled vertex per cluster. Label propagation alone provides the rather bad results in Figure 1 (left). Now we add additional knowledge by computing a measure of local centrality for each vertex: denote by $N_3(i)$ the set of vertices that have shortest path distance exactly 3 to vertex $i$. Let $\varphi_i$ be the sum of all pairwise shortest path distances between any two vertices in $N_3(i)$. Then $\varphi_i^{-1}$ penalizes those vertices that lie close to sharp cluster boundaries. Incorporating these vertex weights by f-adjusting with $f_i := \exp(-5 \cdot \phi_i)$ gives the almost perfect result for label propagation on the adjusted graph (Figure 1, right).

### A.2.2. LABEL PROPAGATION LIMIT BEHAVIOR

The soft labels computed by the label propagation algorithm in case of few labeled vertices tend to be flat, with sharp spikes at the labeled vertices. In this situation, a meaningful threshold is increasingly difficult to find (Nadler et al., 2009). Figure 2 (left) illustrates this problem for a Gaussian-weighted 50NN-graph on 2000 points ($x_i, y_i, z_i$) sampled from $N(\mu, 1) \times N(0, 1) \times N(0, 0.1)$, where $\mu \in \{0, 4\}$ for the 1000 points of each class, respectively. For each class, a single vertex (denoted as $\ell_a$ resp. $\ell_b$) near to $\mu$ is labeled.

<figure><img src="image_7.png" /><figcaption>**Figure 2.** Soft threshold values $s$ of label propagation on original graph (left) and f-adjusted graph (right). Both graphs are built on the same sample drawn from two Gaussians, where each Gaussian is labeled by a single label point near to its center.</figcaption></figure>

Figure 2 (right) shows the soft labels for the f-adjusted graph with $f_i := d_i \cdot \exp(-4 \cdot \min\{hd(i, \ell_a), hd(i, \ell_b)\})$, wherein $hd(x, y)$ denotes the hop-distance, that is the smallest number of edges on an $xy$-path in $G$. This adjustment can be interpreted as extending the areas of attraction from single points (the labeled ones) to larger sets (neighborhoods around labeled points). This biases the label propagation algorithm towards any labeled vertex, providing a sharp separation in the soft labels. Instead of hd, any other distance measure can be used, for example some quantity that is derived from a coarser cluster structure.
## B. Algebraic Interpretation

First we summarize the notation. Then we derive some general properties of weak graph matrices. Finally, we put some effort into proving the main result of the algebraic interpretation, Theorem 4.3.

### B.1. Notation

By the term **graph matrix** we refer to any element of $\mathbb{W} := \{X \in \mathbb{R}_{\ge 0}^{n \times n} | X = X^T, X1 > 0\}$. We generalize this to $\mathbb{W}_{\odot} := \{X \in \mathbb{W} + \text{diag}(\mathbb{R}^n) | X1 > 0\} = \{X \in \mathbb{R}_{\ge 0}^{n \times n} + \text{diag}(\mathbb{R}^n) | X = X^T, X1 > 0\}$, the set of **weak graph matrices**, whose elements further allow for negative diagonal entries as long as all row sums remain positive. Obviously $\mathbb{W} \subset \mathbb{W}_{\odot}$.

Every weak graph matrix $W \in \mathbb{W}_{\odot}$ corresponds to an undirected weighted graph $\mathcal{G}(W) := (V, E, W)$ that has $W$ as its weighted adjacency matrix, and edge set $E := \{ij | w_{ij} \neq 0\}$. With $\mathbf{d} := W1$ and $D := \text{diag}(\mathbf{d})$, we define the unnormalized Laplacian $L(W) = [l_{ij}] := D - W$ and the normalized Laplacian $\mathcal{L}(W) = [\ell_{ij}] := \sqrt{D^{-1}L(W)\sqrt{D^{-1}}} = I - \sqrt{D^{-1}W}\sqrt{D^{-1}}$. If all off-diagonal entries of $W$ are zero, then all vertices in $\mathcal{G}(W)$ are isolated (each with a positive selfloop attached). We refer to this special case as a **trivial graph**. A graph is trivial if and only if $L(W) = \mathcal{L}(W) = 0$. It is non-trivial if and only if $n > 1$ and $w_{ij} \neq 0$ for some $i \neq j$.

For $\mathbf{f} \in \mathbb{R}_{>0}^n$ and $c > 0$ we define the following (weak) graph matrices

$$ \text{for } W \in \mathbb{W} \quad : \quad \mathbf{f}\text{-scaled} \quad \tilde{W}_{\mathbf{f}} := \sqrt{FD^{-1}}W\sqrt{FD^{-1}} \in \mathbb{W} \quad \text{where } F := \text{diag}(\mathbf{f}) $$

$$ \text{for } W \in \mathbb{W}_{\odot} \quad : \quad \mathbf{f}\text{-selflooped} \quad W_{\mathbf{f}}^{\circ} := W - D + F \in \mathbb{W}_{\odot} $$

$$ \text{for } W \in \mathbb{W} \quad : \quad (\mathbf{f}, c)\text{-adjusted} \quad \overline{W}_{\mathbf{f},c} := \tilde{W}_{\mathbf{f}} - \tilde{D}_{\mathbf{f}} + cF \in \mathbb{W}_{\odot} \quad \text{where } \tilde{D}_{\mathbf{f}} := \text{diag}(\tilde{W}_{\mathbf{f}}1). $$

We consider the matrix decorations $\tilde{\gamma}$, $\circ$ and $\overline{\gamma}$ as operators on the matrix $W$, with the indices $\mathbf{f}$ and $c$ as additional parameter values. For example, for any matrix $A \in \mathbb{W}$ and any vector $\mathbf{x} \in \mathbb{R}_{>0}^n$ we get that $A_{\mathbf{x}}^{\circ} := A - \text{diag}(A1) + \text{diag}(\mathbf{x})$. Note that $(\mathbf{f}, c)$-adjusting is equal to $\mathbf{f}$-scaling followed by $c\mathbf{f}$-selflooping, that is $\overline{W}_{\mathbf{f},c} = (\tilde{W}_{\mathbf{f}})_{c\mathbf{f}}^{\circ}$.

For $W \in \mathbb{W}$, we define the **f-adjusted Laplacian** $\mathcal{L}_{\mathbf{f}}(W)$ as the normalized Laplacian of the f-adjusted graph,

$$ \mathcal{L}_{\mathbf{f}}(W) := \mathcal{L}(\overline{W}_{\mathbf{f},1}). $$

We study some of its properties in the following. In particular, Lemma 4.2 shows that $\mathcal{L}_{\mathbf{f}}(W)$ is a diagonal modification of $\mathcal{L}(W)$, that is $\mathcal{L}_{\mathbf{f}}(W) = \mathcal{L}(W) + X$ for some $X \in \text{diag}(\mathbb{R}^n)$.

### B.2. General properties of weak graph matrices

$\mathbb{W}$ is closed under $\mathbf{f}$-scaling: $W \in \mathbb{W} \Rightarrow \tilde{W}_{\mathbf{f}} \in \mathbb{W}$. However, $\mathbb{W}_{\odot}$ is not closed under $\mathbf{f}$-scaling, since for example $W = \begin{pmatrix} -5 & 6 \\ 6 & 3 \end{pmatrix} \in \mathbb{W}_{\odot}$ would give that $\tilde{W}_1 = \begin{pmatrix} -5 & 2 \\ 2 & 1/3 \end{pmatrix} \notin \mathbb{W}_{\odot}$. For that reason, we consider $\mathbf{f}$-scaling and $\mathbf{f}$-adjusting only applied to non-weak graph matrices.

$\mathbb{W}_{\odot}$ is closed under $\mathbf{f}$-selflooping, but $\mathbb{W}$ is not: for example $W = \begin{pmatrix} 0 & 2 \\ 2 & 0 \end{pmatrix} \in \mathbb{W}$ gives that $W_1^{\circ} = \begin{pmatrix} -1 & 2 \\ 2 & -1 \end{pmatrix} \notin \mathbb{W}$. However, we achieve some sense of closedness of $\mathbb{W}$ when restricting to $c\mathbf{f}$-selflooping for $c \ge c_{W,\mathbf{f}}^*$ as defined in the next proposition.

**Proposition B.1.** Let $W \in \mathbb{W}_{\odot}$, $\mathbf{f} \in \mathbb{R}_{>0}^n$ and $c > 0$. Define $c_{W,\mathbf{f}}^* := \max_{i \in V}\{(d_i - w_{ii})/f_i\} \ge 0$. Then it holds that $W_{c\mathbf{f}}^{\circ} \in \mathbb{W}$ if and only if $c \ge c_{W,\mathbf{f}}^*$.

*Proof.* From $W_{c\mathbf{f}}^{\circ} = W - D + cF$ we get that $W_{c\mathbf{f}}^{\circ}$ has no negative selfloop if and only if $w_{ii} - d_i + c f_i \ge 0$ for all $i \in V$. In the case $c \ge c_{W,\mathbf{f}}^*$ we get that $w_{ii} - d_i + c f_i \ge w_{ii} - d_i + \max_{i \in V}\{(d_i - w_{ii})/f_i\} \cdot f_i = \max_{i \in V}\{(d_i - w_{ii})\} - (d_i - w_{ii}) \ge 0$ for all $i \in V$. For $c < c_{W,\mathbf{f}}^*$, choose $k \in \{i \in V | (d_i - w_{ii})/f_i = c_{W,\mathbf{f}}^*\}$, and get that $w_{kk} - d_k + c f_k < w_{kk} - d_k + c_{W,\mathbf{f}}^* \cdot f_k = w_{kk} - d_k + (d_k - w_{kk})/f_k \cdot f_k = 0$. □
Remark 1. It holds that $c_{W,f}^* = 0$ if and only if $W$ is trivial (because then $d_i = w_{ii}$ for all $i \in V$).

Remark 2. For non-trivial $W \in W_\odot$ and any $f \in \mathbb{R}_{>0}^n$ we get the non-trivial partition:

$$ \{W_{cf}^{\circ} | c > 0\} = \underbrace{\{W_{cf}^{\circ} | 0 < c < c_{W,f}^{*}\}}_{\subseteq W_{\odot}\setminus W} \cup \underbrace{\{W_{cf}^{\circ} | c \ge c_{W,f}^{*}\}}_{\subseteq W}. $$

**Fact B.2.** For every $W \in W_\odot$ it holds that $W_{cd}^{\circ} \in W$ for all positive $c \ge c_{W,d}^*$.

*Proof.* For trivial $W$ this is obvious, and for non-trivial $W$ this follows from Remark 2. $\square$

**Fact B.3.** For every $W \in W$, $f \in \mathbb{R}_{>0}^n$ and $c, a > 0$ it holds that $\tilde{W}_{af} = a \cdot \tilde{W}_f$ and that $\overline{W}_{af,c} = a \cdot \overline{W}_{f,c}$.

*Proof.* By definition we get that $\tilde{W}_{af} = \sqrt{aFD^{-1}}W\sqrt{aFD^{-1}} = a\sqrt{FD^{-1}}W\sqrt{FD^{-1}} = a \cdot \tilde{W}_f$, which further implies that $\tilde{D}_{af} = a \cdot \tilde{D}_f$. It follows that $\overline{W}_{af,c} = \tilde{W}_{af} - \tilde{D}_{af} + caF = a \cdot (\tilde{W}_f - \tilde{D}_f + cF) = a \cdot \overline{W}_{f,c}$. $\square$

Let us summarize some easy facts on the main diagonal of $L(W) = [l_{ij}]$ and $\mathcal{L}(W) = [\ell_{ij}]$ without proofs:

**Fact B.4.** For $W \in W$ it holds for all $i \in V$ that:

(i) $0 \le w_{ii} \le d_i$, $0 \le w_{ii}/d_i \le 1$

(ii) $l_{ii} = d_i - w_{ii} \in [0, d_i]$ with $l_{ii} = 0$ if and only if $i$ is an isolated vertex.

(iii) $\ell_{ii} = 1 - w_{ii}/d_i \in [0, 1]$ with $\ell_{ii} = 0$ if and only if $i$ is an isolated vertex.

These results generalize to weak graph matrices (now $w_{ii} < 0$ is possible) as follows:

**Fact B.5.** For $W \in W_\odot$ it holds for all $i \in V$ that:

(i) $-\infty < w_{ii} \le d_i$, $-\infty < w_{ii}/d_i \le 1$

(ii) $l_{ii} = d_i - w_{ii} \in [0, \infty)$ with $l_{ii} = 0$ if and only if $i$ is an isolated vertex, and $l_{ii} > d_i$ if and only if $i$ has a negative selfloop.

(iii) $\ell_{ii} = 1 - w_{ii}/d_i \in [0, \infty)$ with $\ell_{ii} = 0$ if and only if $i$ is an isolated vertex, and $\ell_{ii} > 1$ if and only if $i$ has a negative selfloop.

Trivially it holds that $W = W_{d}^{\circ}$. The next lemma shows how $W$ and $W_{cd}^{\circ}$ are related for all $c > 0$.

**Lemma B.6.** For all $W \in W_\odot$ it holds that $\mathcal{L}(W) = c \cdot \mathcal{L}(W_{cd}^{\circ})$ for all $c > 0$.

*Proof.* $\mathcal{L}(W_{cd}^{\circ}) = \sqrt{(cD)^{-1}(cD - (W - D + cD))}\sqrt{(cD)^{-1}} = c^{-1}\sqrt{D^{-1}(D - W)\sqrt{D^{-1}}} = c^{-1}\mathcal{L}(W)$. $\square$
This easy yet powerful lemma gives that all normalized Laplacians in {$\mathcal{L}(W_{cd}^\circ) | c > 0$} share the same eigenvectors with their corresponding eigenvalues simply scaled according to $c$. This implies for example that positive semi-definiteness of $\mathcal{L}(W)$ and $\mathcal{L}(W)$ generalizes to non-weak graph matrices, as the next lemma shows.

**Lemma B.7.** For $W \in \mathbb{W}_\odot$ it holds that $\mathcal{L}(W)$ is positive semi-definite. Further, 0 is an eigenvalue of $\mathcal{L}(W)$ with multiplicity equal to the number of connected components in $\mathcal{G}(W)$, and $\sqrt{\mathbf{d}}$ a corresponding eigenvector.

*Proof.* Adding/Removing selfloops does not affect the number of connected components. Thus, all results follow directly from Lemma B.6 and Fact B.2, since there exists $c > 0$ with $W_{cd}^\circ \in \mathbb{W}$ and $\mathcal{L}(W) = c \cdot \mathcal{L}(W_{cd}^\circ)$. All stated properties are well-known for non-weak graph matrices. $\square$

It is obvious that $A = cW$ implies that $\mathcal{L}(A) = \mathcal{L}(W)$. The following lemma shows that for connected graph matrices furthermore equivalence holds.

**Lemma B.8.** Let $n > 1$. For connected $\mathcal{G}(W) \in \mathcal{G}(\mathbb{W}_\odot)$ and any $A \in \mathbb{W}_\odot$ it holds that $\mathcal{L}(W) = \mathcal{L}(A)$ if and only if $A = c \cdot W$ for some $c > 0$.

*Proof.* “$\Leftarrow$”. $A = cW$ for $c > 0$ yields $\mathcal{L}(A) = I - \sqrt{(cD)^{-1}}cW\sqrt{(cD)^{-1}} = I - \sqrt{D^{-1}W}\sqrt{D^{-1}} = \mathcal{L}(W)$. “$\Rightarrow$”. Let $[\ell_{ij}] := \mathcal{L}(W) = \mathcal{L}(A) =: [\ell_{ij}^A]$. Further let $\mathbf{t} := A1 > 0$. First, we show that $\mathbf{t} = \alpha\mathbf{d}$ for some $\alpha > 0$. By Lemma B.7 we get that $\sqrt{\mathbf{d}}$ is the unique (up to scaling) eigenvector of $\mathcal{L}(W)$ to the eigenvalue 0, similarly $\sqrt{\mathbf{t}}$ for $\mathcal{L}(A)$. Hence, if $\mathbf{t} \neq \alpha\mathbf{d}$ for all $\alpha \in \mathbb{R}$, then $\mathcal{L}(W) \neq \mathcal{L}(A)$, since they differ in their first eigenspace. Otherwise we may choose a positive $\alpha$ and get that $t_i = \alpha \cdot d_i$ for all $i \in V$.

For every $i \neq j$ we get from $\ell_{ij} = w_{ij}/\sqrt{d_i d_j} = a_{ij}/\sqrt{t_i t_j} = \ell_{ij}^A$ that $a_{ij} = w_{ij} \cdot \sqrt{t_i t_j (d_i d_j)^{-1}} = \alpha \cdot w_{ij}$. For $i = j$ we get from $\ell_{ij} = (d_i - w_{ii})/d_i = (t_i - a_{ii})/t_i = \ell_{ij}^A$ that $d_i - w_{ii} = d_i - a_{ii}/\alpha$, hence $a_{ii} = \alpha \cdot w_{ii}$. $\square$

*Remark 3.* With Fact B.3 this lemma also gives that $\mathcal{L}_f(W) = \mathcal{L}_{\alpha f}(W)$ for all $\alpha > 0$. Further, for connected $\mathcal{G}(W)$, even the opposite holds: $\mathcal{L}_f(W) = \mathcal{L}_g(W)$ if and only if $\mathbf{f} = \alpha\mathbf{g}$ for some $\alpha \in \mathbb{R}_{>0}$.

### B.3. f-adjustments are diagonally modified Laplacians

The following two lemmas are stated in the paper. Their proofs are straightforward.

**Lemma 4.1 (Scaling Relation).** For all $W \in \mathbb{W}$, $\mathbf{f} \in \mathbb{R}_{>0}^n$ and $c > 0$ it holds that

$$ \mathcal{L}(\overline{W}_{\mathbf{f},1}) = c \cdot \mathcal{L}(\overline{W}_{\mathbf{f},c}). $$

*Proof.* This can be seen from $\overline{W}_{\mathbf{f},1} = (\tilde{W}_{\mathbf{f}})^\circ_{\mathbf{c}\mathbf{f}}$ and applying Lemma B.6 to $\tilde{W}_{\mathbf{f}}$, or directly as follows:

$$ \begin{align*} c \cdot \mathcal{L}(\overline{W}_{\mathbf{f},c}) &= c \cdot \sqrt{(cF)^{-1}}(cF - (\tilde{W}_{\mathbf{f}} - \tilde{D}_{\mathbf{f}} + cF))\sqrt{(cF)^{-1}} \\ &= \sqrt{F^{-1}(F - (\tilde{W}_{\mathbf{f}} - \tilde{D}_{\mathbf{f}} + F))\sqrt{F^{-1}}} \\ &= \mathcal{L}(\overline{W}_{\mathbf{f},1}) \end{align*} $$

$\square$
**Lemma 4.2 (Diagonally Modified Laplacian).** For all $W \in \mathbb{W}$ and $f \in \mathbb{R}_{>0}^n$ it holds that

$$ \mathcal{L}_f(W) = \tilde{D}_f F^{-1} - \tilde{W}_1. $$

*Proof.* Right from the definitions we get that:

$$ \begin{aligned} \mathcal{L}_f(W) &= I - \sqrt{F^{-1}(\tilde{W} - \tilde{D}_f + F)\sqrt{F^{-1}}} \\ &= I - \sqrt{F^{-1}\sqrt{FD^{-1}W}\sqrt{FD^{-1}}\sqrt{F^{-1}}} + \tilde{D}_f F^{-1} - I \\ &= \tilde{D}_f F^{-1} - \sqrt{D^{-1}W}\sqrt{D^{-1}} \end{aligned} $$

*Remark 4.* Recall that $\mathcal{L}(W) = I - \tilde{W}_1$, hence

$$ \mathcal{L}_f(W) = \mathcal{L}(W) - \underbrace{(I - \tilde{D}_f F^{-1})}_{\in \mathrm{diag}(\mathbb{R}^n)} =: \mathcal{L}(W) - \mathrm{diag}(\mathbf{h}) $$

for $\mathbf{h} := (I - \sqrt{F^{-1}D^{-1}W}\sqrt{FD^{-1}})\mathbf{1}$, where $\mathbf{h} = (h_i)_i$ can be expressed element-wise as:

$$ h_i = 1 - \sum_{j=1}^{n} w_{ij} \frac{\sqrt{f_j/f_i}}{\sqrt{d_i d_j}}. $$

*Remark 5.* The trivial relation $\mathcal{L}_d(W) = \mathcal{L}(W)$ is attained for $\mathbf{h} = (I - D^{-1}W)\mathbf{1} = \mathbf{0}$, which is noteworthy, since $D^{-1}W$ is the random walk transition matrix.

## B.4. Diagonally modified Laplacians are f-adjustments

We are now going to prove two lemmas that finally lead to our main result.

**Lemma B.9 (Characterization of f-adjusted Laplacians).** For connected $\mathcal{G}(W) \in \mathcal{G}(\mathbb{W})$ let

$$ \Lambda := \{ \mathcal{L}_f(W) \mid \mathbf{f} \in \mathbb{R}_{>0}^n \} $$

denote the Laplacian orbit of W under f-adjusting. Further let

$$ \Lambda' := \{ Z - \tilde{W}_1 \mid Z \in \mathrm{diag}(\mathbb{R}_{>0}^n), \rho(Z^{-1}\tilde{W}_1) = 1 \} $$

for $\rho(\cdot)$ the Perron root of its argument. Then it holds that $\Lambda = \Lambda'$ with the relation $Z = \tilde{D}_f F^{-1}$, wherein $\sqrt{\mathbf{f}}$ is the unique (up to scaling) right eigenvector of $Z^{-1}\tilde{W}_1$ to eigenvalue 1.

*Proof.* It is well-known that $\mathcal{G}(W)$ is connected if and only if $W$ is irreducible. This implies, for any choice of $Z \in \mathrm{diag}(\mathbb{R}_{>0}^n)$, that $Z^{-1}\tilde{W}_1$ is irreducible (and non-negative), too, since it has the same non-zero-pattern as $W$. This allows to apply various aspects of the Perron-Frobenius-Theorem (PFT), see for example Stańczak et al. (2006) for an overview.

$\Lambda \subseteq \Lambda'$: fix any $\mathcal{L}_f(W) \in \Lambda$ for some $\mathbf{f} > 0$ and set $Z := \tilde{D}_f F^{-1} \in \mathrm{diag}(\mathbb{R}_{>0}^n)$. We prove that $\rho(Z^{-1}\tilde{W}_1) = 1$ by finding an all-positive eigenvector $\mathbf{x}$ to the following eigenvalue problem:

$$ Z^{-1}\sqrt{D^{-1}W}\sqrt{D^{-1}}\mathbf{x} = \mathbf{x}. \qquad (*) $$
We propose that $\sqrt{f}$ is such an eigenvector. Plugging $\tilde{D}_f = \text{diag}(\sqrt{FD^{-1}W}\sqrt{FD^{-1}1})$ into $\tilde{D}_f F^{-1} = Z$ element-wise, gives with $Z = \text{diag}(z_1, \dots, z_n)$ that

$$ \begin{align*} \tilde{D}_f F^{-1} &= Z \\ \Leftrightarrow \quad & \sum_{j=1}^{n} \frac{w_{ij}}{\sqrt{d_i d_j}} \cdot \sqrt{f_j} = z_i \cdot \sqrt{f_i} \quad \text{for all } i = 1, \dots, n \tag{**} \\ \Leftrightarrow \quad & \sqrt{D^{-1}W} \sqrt{D^{-1}} \sqrt{f} = Z \sqrt{f} \\ \Leftrightarrow \quad & Z^{-1} \sqrt{D^{-1}W} \sqrt{D^{-1}} \sqrt{f} = \sqrt{f} \end{align*} $$

Thus $\sqrt{f}$ is indeed a solution to $(\star)$, hence an all-positive (right) eigenvector of $Z^{-1}\tilde{W}_1$ to the (existing) eigenvalue 1. By PFT, there is exactly one eigenvalue providing all-positive eigenvectors. Further it determines the spectral radius and is simple. Thus, we have that $\rho(Z^{-1}\tilde{W}_1) = 1$ and that the corresponding left and right eigenvectors are unique (up to scaling). With Lemma 4.2 we get that $Z = \tilde{D}_f F^{-1}$ is a valid choice for $Z$ to represent $\mathcal{L}_f(W)$ as an element in $\Lambda'$.

$\Lambda' \subseteq \Lambda$: fix any $Z - \tilde{W}_1 \in \Lambda'$ for some $Z \in \text{diag}(\mathbb{R}_{>0}^n)$ with $\rho(Z^{-1}\tilde{W}_1) = 1$. By irreducibility of $Z^{-1}\tilde{W}_1$, there exists by PFT a unique (up to scaling) all-positive solution $\hat{x}$ of $(\star)$. By defining $f := \hat{x}^2$ we get that $\sqrt{f}$ is a solution to the eigenvalue problem $(\star)$. From $(\star\star)$ we see that this is equivalent to $Z = \tilde{D}_f F^{-1}$. Thus, we get that $Z - \tilde{W}_1 = \tilde{D}_f F^{-1} - \tilde{W}_1 = \mathcal{L}_f(W) \in \Lambda$ for this unique (up to scaling) choice of $f$. $\square$

**Remark 6.** This lemma generalizes to unconnected graphs as follows: there is a permutation $P$ of rows and columns such that $W' = PWP^T$ has block diagonal form, wherein each block-submatrix is irreducible. Thus, all above arguments can be carried out on each block individually, by restricting $f$ to just the entries belonging to that block (= connected component). This relaxes the uniqueness in the way, that now $f$ may be scaled by an individual scaling factor chosen independently for each connected component.

We have shown that f-adjusting can be understood as a diagonal modification of the form $\mathcal{L}(W) + X = \mathcal{L}(A)$ for some $X \in \text{diag}(\mathbb{R}^n)$ and $A \in \mathbb{W}_\odot$. So far the question is left open if further the converse is true: does every such diagonal modification imply that $A$ is an f-adjustment of $W$? We now answer this in the affirmative.

**Lemma B.10 (Characterization of Diagonally Modified Laplacians).** Let $W \in \mathbb{W}$. Then $\mathcal{L}(W) + X = \mathcal{L}(A)$ holds true for $X \in \text{diag}(\mathbb{R}^n)$ and $A \in \mathbb{W}_\odot$ if and only if $A$ is an f-adjustment of $W$ for some $f \in \mathbb{R}_{>0}^n$. Formally,

$$ \Lambda = \{ \mathcal{L}(W) + X \mid X \in \text{diag}(\mathbb{R}^n), \mathcal{L}(W) + X \in \mathcal{L}(\mathbb{W}_\odot) \} $$

with $\Lambda$ the Laplacian orbit of $W$ under f-adjusting.

*Proof.* "$\subseteq$". This direction is clear by Lemma 4.2.

"$\supseteq$". With $Y := X + I$ we have that $\mathcal{L}(A) = Y - \sqrt{D^{-1}W}\sqrt{D^{-1}} =: [\ell_{ij}^A]$ for some $A \in \mathbb{W}_\odot$. First we want to show that this implies that $Y = \text{diag}(y_1, \dots, y_n)$ has an all-positive diagonal. Fix any $i \in V$. From $A \in \mathbb{W}_\odot$ and Fact B.5 it follows that $\ell_{ii}^A \ge 0$, and from $W \in \mathbb{W}$ that $w_{ii} \ge 0$. Thus, we get from $\ell_{ii}^A = y_i - w_{ii}/d_i \ge 0$ that $y_i \ge w_{ii}/d_i \ge 0$. Thus $y_i$ is non-negative. Now assume that $y_i = 0$. This implies that $w_{ii} = 0$, hence $\ell_{ii}^A = 0$, so $i$ must be an isolated vertex in $\mathcal{G}(A)$. However, in $\mathcal{G}(W)$ vertex $i$ cannot be isolated, since $w_{ii} = 0$ implies by the positive degree constraint that $w_{ij} > 0$ for some $j \ne i$. For such $j$ it holds that $-a_{ij}/\sqrt{d_i^A d_j^A} = \ell_{ij}^A = \ell_{ij} = -w_{ij}/\sqrt{d_i d_j} < 0$, hence that $a_{ij} > 0$ in contradiction to $i$ being an isolated vertex in $A$. Therefore, $y_i > 0$ for all $i \in V$.

In the following we assume w.l.o.g. that $W$ is connected, since all arguments can be applied to each connected component individually, independent of all other components.

Lemma B.9 gives that for any all-positive diagonal matrix $Y$ (in particular as chosen above) there exists some $\alpha > 0$ and some f-adjustment $\overline{W}_f := M_\alpha \in \mathbb{W}_\odot$ for some $f \in \mathbb{R}_{>0}^n$ such that $\mathcal{L}(M_\alpha) = \alpha Y - \sqrt{D^{-1}W}\sqrt{D^{-1}} \in \Lambda$. We now show
that for no $\beta \neq \alpha$ any $M_{\beta} \in W_{\odot}$ with $\mathcal{L}(M_{\beta}) = \beta Y - \sqrt{D^{-1}W}\sqrt{D^{-1}}$ exists. This finally implies that $M_1$ itself is the f-adjustment of $W$, which gives that $\mathcal{L}(A) = \mathcal{L}(M_1) \in \Lambda$.

Therefore, fix any $M_{\beta} \in W_{\odot}$ with $\mathcal{L}(M_{\beta}) = \beta Y - \sqrt{D^{-1}W}\sqrt{D^{-1}}$ for some $\beta \in \mathbb{R}$. Setting $\epsilon := \beta - \alpha$ gives that $\mathcal{L}(M_{\beta}) = \beta Y - \sqrt{D^{-1}W}\sqrt{D^{-1}} = \mathcal{L}(M_{\alpha}) + \epsilon Y$. Now assume that $\epsilon > 0$. By Lemma B.7, $\mathcal{L}(M_{\beta})$ is positive semi-definite with $v := \sqrt{M_{\beta}\mathbf{1}}$ an all-positive eigenvector to the eigenvalue 0. We get the contradiction $0 = v^T\mathcal{L}(M_{\beta})v = v^T\mathcal{L}(M_{\alpha})v + \epsilon v^T Y v > 0$, because $v^T\mathcal{L}(M_{\alpha})v \ge 0$ by positive semi-definiteness of $\mathcal{L}(M_{\alpha})$, and $\epsilon v^T Y v > 0$ by all-positivity of $v$ and $Y$. Now assume that $\epsilon < 0$. Let $w := \sqrt{M_{\alpha}\mathbf{1}}$ denote the all-positive eigenvector of $\mathcal{L}(M_{\alpha})$ to the eigenvalue 0. We get the contradiction $0 \le w^T\mathcal{L}(M_{\beta})w = w^T\mathcal{L}(M_{\alpha})w + \epsilon w^T Y w < 0$, because $w^T\mathcal{L}(M_{\alpha})w = 0$, and $\epsilon w^T Y w < 0$ by all-positivity of $w$ and $Y$, and the first inequality due to positive semi-definiteness of $\mathcal{L}(M_{\beta})$. Thus, for no $\epsilon \neq 0$ any graph matrix of this form exists. $\square$

Now we have all ingredients to prove our main result on the algebraic interpretation of f-adjusting:

**Theorem B.11 (Complete Characterization for Connected Graphs).** For $n > 1$ and connected $\mathcal{G}(W) \in \mathcal{G}(W)$ consider all solutions $(X, A, c) \in \text{diag}(\mathbb{R}^n) \times W_{\odot} \times \mathbb{R}$ of the equation

$$ \mathcal{L}(W) + X = c \cdot \mathcal{L}(A). $$

For $c \le 0$ no solution exists. For $c > 0$, all solutions are given by $A = \overline{W}_{f,c}$ and $X + I = \tilde{D}_{f}F^{-1} = Z$ for any choice of $f \in \mathbb{R}^n_{>0}$. This is equivalent to choosing any $Z \in \text{diag}(\mathbb{R}^n_{>0})$ with Perron root $\rho(Z^{-1}\tilde{W}_1) = 1$, which determines $\sqrt{f}$ as the unique (up to scaling) right Perron eigenvector.

*Proof.* Let $\mathcal{L}(W) := [\ell_{ij}]$ and $\mathcal{L}(A) := [\ell_{ij}^A]$. Since $W$ is non-trivial, there exist $i \neq j$ with $w_{ij} > 0$, hence $\ell_{ij} < 0$. The case $c < 0$ would imply that $\ell_{ij}^A > 0$, which is impossible for all $A \in W_{\odot}$. The case $c = 0$ would imply that $\mathcal{L}(W) + X = 0$, hence that all off-diagonal elements in $W$ are zero, in contradiction to being non-trivial. Thus, no solutions for $c \le 0$ exist.

Now consider the case $c = 1$, that is any solution of the form $\mathcal{L}(W)+X = \mathcal{L}(A)$. We get from Lemma B.10 that every such solution corresponds to fixing some $f \in \mathbb{R}^n_{>0}$ and setting $A := \overline{W}_{f,1}$. This implies by Lemma 4.2 that $X + I = \tilde{D}_{f}F^{-1}$. It remains to show that this is equivalent to choosing $Z \in \text{diag}(\mathbb{R}^n_{>0})$ with the desired properties. For fixed $f$, we get from Lemma B.9 that $\tilde{D}_{f}F^{-1} = X + I = Z$ for some $Z \in \text{diag}(\mathbb{R}^n_{>0})$ with Perron eigenvalue $\rho(Z^{-1}\tilde{W}_1) = 1$ and $\sqrt{f}$ the corresponding right Perron eigenvector. The other way round, Lemma B.9 gives that choosing any $Z \in \text{diag}(\mathbb{R}^n_{>0})$ with $\rho(Z^{-1}\tilde{W}_1) = 1$ implies by setting $X := Z - I$ that $\mathcal{L}(W) + X = \mathcal{L}(A)$ for $A = \overline{W}_{f,1}$, and further that $Z = \tilde{D}_{f}F^{-1}$ with $\sqrt{f}$ being determined as the unique (up to scaling) right Perron eigenvector.

Now consider the case $c > 0$, that is $\mathcal{L}(W)+X = c \cdot \mathcal{L}(A)$ for $X \in \text{diag}(\mathbb{R}^n)$ and $A \in W_{\odot}$. From $c \cdot \mathcal{L}(A) \stackrel{B.6}{=} \mathcal{L}(A_{c-1,A_1}^o)$ we get that $\mathcal{L}(W)+X$ equals the normalized Laplacian of a weak graph matrix. Thus, $\mathcal{L}(W)+X \stackrel{B.10}{=} \mathcal{L}(\overline{W}_{g,1})$ for some $g \in \mathbb{R}^n_{>0}$. This gives that $\mathcal{L}(A) = c^{-1}\mathcal{L}(\overline{W}_{g,1}) \stackrel{4.1}{=} \mathcal{L}(\overline{W}_{g,c})$. Thus we have that $A \stackrel{B.8}{=} \alpha \cdot \overline{W}_{g,c} \stackrel{B.3}{=} \overline{W}_{\alpha g, c}$ for some $\alpha > 0$. So $A$ is the $(f, c)$-adjustment of $W$ for $f := \alpha g$. It follows as before that $X + I = \tilde{D}_{g} \text{diag}(g)^{-1} = \tilde{D}_{f}F^{-1} = Z$ for some $Z \in \text{diag}(\mathbb{R}^n_{>0})$ with Perron eigenvalue $\rho(Z^{-1}\tilde{W}_1) = 1$ and $\sqrt{g}$ a corresponding right Perron eigenvector as well as $\sqrt{f} = \sqrt{\alpha g}$ another one, unique up to scaling.

For the other way round, choose any $f \in \mathbb{R}^n_{>0}$ (or equivalently any $Z \in \text{diag}(\mathbb{R}^n_{>0}))$. Setting $A := \overline{W}_{f,c}$ implies that $\mathcal{L}(\overline{W}_{f,1}) \stackrel{4.1}{=} c \cdot \mathcal{L}(A) = \mathcal{L}(W) + X$, hence by Lemma 4.2 that $X + I = \tilde{D}_{f}F^{-1}$. $\square$

*Remark 7.* For arbitrary $c > 0$, the theorem implies that $\mathcal{L}(W) + X = c \cdot \mathcal{L}(A)$ is a solution if and only if $c \cdot \mathcal{L}(A) = c \cdot \mathcal{L}(\overline{W}_{f,c}) = \mathcal{L}(\overline{W}_{f,1}) = \mathcal{L}_{f}(W)$ for the specific vector $f$, that is if and only if $\mathcal{L}(W) + X \in \mathcal{L}(W_{\odot})$.
Remark 8. From the special case $c = 1$ we get that all solutions $(X, A) \in \text{diag}(\mathbb{R}^n) \times W_\odot$ of the equation $\mathcal{L}(W) + X = \mathcal{L}(A)$ are given by $\mathcal{L}(W) + X = \mathcal{L}_f(W)$ for every $f \in \mathbb{R}_{>0}^n$. Furthermore, $f$ and $X$ are related to each other by $\rho((X + I)^{-1}\tilde{W}_1) = 1$ with $X + I \in \text{diag}(\mathbb{R}_{>0}^n)$ and $\sqrt{f}$ the corresponding eigenvector.

In our paper we state Theorem B.11 slightly different as follows:

**Theorem 4.3 (Complete Characterization).** For any $W \in W$ with $\mathcal{L}(W) \neq 0$ consider all solutions $(X, A, c) \in \text{diag}(\mathbb{R}^n) \times W_\odot \times \mathbb{R}$ of the equation

$$ \mathcal{L}(W) + X = c \cdot \mathcal{L}(A). $$

For $c \le 0$ no solution exists. For $c > 0$, all solutions are given by $A = \overline{W}_{f,c}$ and $X + I = \tilde{D}_f F^{-1} = Z$ for any choice of $f \in \mathbb{R}_{>0}^n$. For connected $G(W)$, choosing $f$ is equivalent to choosing any $Z \in \text{diag}(\mathbb{R}_{>0}^n)$ with spectral radius $\rho(Z^{-1}\tilde{W}_1) = 1$. This determines $\sqrt{f}$ uniquely (up to scaling) as the eigenvector corresponding to the simple eigenvalue 1 of the matrix $Z^{-1}\tilde{W}_1$.

Remark 9. All diagonal modifications of $W$ with $W + X \in W_\odot$ obviously correspond to $f$-selflooping, that is modifying selfloops in any possible way. Theorem 4.3 shows a similar result for the normalized Laplacian, namely that all diagonal modifications of $\mathcal{L}(W)$ with $\mathcal{L}(W) + X \in \mathcal{L}(W_\odot)$ correspond to $f$-adjusting for every $f \in \mathbb{R}_{>0}^n$. This shows that $f$-adjusting is a very natural graph modification.
C. Geometric Interpretation

In this section we provide more details on the convergence of the modified interspace quantities to their corresponding
modified continuous quantities. Both our propositions are already motivated in the paper in terms of the sum expressions
that define the interspace volumes and cut weights, respectively.

The proofs heavily rely on the arguments in Maier et al. (2009), where the convergence of interspace volumes and cut
weights to their corresponding continuous quantities is proven for different types of neighborhood graphs, for a fixed
density $p: \mathcal{X} \to \mathbb{R}_{>0}$. They show that volumes and cut weights refer to the continuous quantities $\int p^2$ in the limit. They
study different types of neighborhood graphs for a single density $p$. In contrast to that, we relate two neighborhood graphs
of the same type, but according to different densities $p$ and $\tilde{p} = fp$ to each other.

The limit quantities $\int p^2$ combine two different effects, each rising one factor of $p$. These two effects are:

(i) one factor $p$ comes from the sampling mechanism, which distributes the sample points according to $p$

(ii) another factor $p$ refers to the weighted degrees in the original graph, which serve as a density estimate on $p$

This gets particularly apparent in the interspace view. In light of this we ask the question: “Can we modify these effects by
modifying edge weights in the given graph?”

The first effect (i) cannot be modified by us, since the unknown sample is fixed. Therefore, the positions of the sample
points are always determined by a sampling mechanism according to $p$. However, we observe that the second effect (ii)
is not required to refer to degrees that estimate $p$. It can be chosen to represent any other function $f$ on the underlying
space (as long as it satisfies the same technical assumptions that are made on $p$). Since we have access to the graph, we
can change its degrees by changing its edge weights plus adding selfloops in any way that we want. This gives us the
opportunity to influence the second effect freely.

There is no geometric interpretation of volumes and cuts under arbitrary modifications applied to the graph. But if we
modify the degrees and the cut weights by f-adjusting, and if we further assume that f is determined by any suitable
continuous function $f$, then we can interpret the resulting volumes and cuts in $\bar{G}$ in terms of $\int fp$, compared to their
original interpretation as $\int p^2$ in $G$.

Technically, we achieve this by sneaking in a new term corresponding to $f$ everywhere along the proofs in Maier et al.
(2009). This allows for “changing” the limit quantities $\int p^2$ into any $\int \bar{p} = \int fp$, for free to choose $f$. The full proofs
would cover at least 10 pages, and mainly deal with technical considerations on boundary effects. For that reason, we
decided to just sketch the general proof strategies here. The interested reader is referred to Maier et al. (2009).

**Proposition 5.1. (Interspace volumes)** Let $G$ be a geometric graph based on $n$ vertices drawn according to $p$. Denote
its degree vector by $\mathbf{d}$ and let $f: \mathcal{X} \to \mathbb{R}_{>0}$ be a continuous function. Define the vector $\mathbf{f} := (f(x_i))_i$, and let $\bar{G}$
be any graph modification of $G$ that attains the degrees $\bar{\mathbf{d}} = \mathbf{f}$. Then, under the convergence conditions mentioned
above, for all measurable $A \subset \mathbb{R}^d$, $C \cdot \text{vol}_{\bar{\mathbf{d}}}(A) \to \text{vol}_{f \cdot p}(A)$ almost surely as $n \to \infty$, where $C$ is a scaling constant
that depends on $n, \mathbf{d}$.

*Proof Sketch.* The general line of argument is to decompose the deviations in bias and variance term. The convergence of the bias term is straightforward to see, the convergence of the variance term can be proved by concentration arguments. $\square$

**Proposition 5.2. (Interspace cuts)** Let $G$ be a geometric graph based on $n$ vertices drawn according to $p$. Denote its
degree vector by $\mathbf{d}$ and let $f: \mathcal{X} \to \mathbb{R}_{>0}$ be a continuous function that is twice differentiable and has bounded gradi-
ent. Define the vector $\mathbf{f} := (f(x_i))_i$, and let $\bar{G}$ be the corresponding $f$-scaled graph with weight matrix $\bar{W}_{\mathbf{f}}$. Consider
a hyperplane $H$ in $\mathbb{R}^d$. Then, under the convergence conditions mentioned above, $C \cdot \text{cut}_{\bar{W}_{\mathbf{f}}}(H) \to \text{cut}_{f \cdot p}(H)$ almost
surely as $n \to \infty$, where $C$ is a scaling constant that depends on $n, \mathbf{d}$.
*Proof Sketch.* The variance part can be solved by concentration arguments. For the bias term, we need to count the edges in the graph that cross the hyperplane $H$. The main ingredient therefore is that we can control the distance of connected points in the graph, with high probability. By concentration arguments we know that with high probability, each point $x$ is connected to all points within a certain distance $r_x$, and is not connected to points exceeding a certain distance $R_x$. For counting edges, we then need to compute the probability mass of the intersection of those balls with the given hyperplane $H$. $\square$

*Remark 10.* We believe that all results generalize from hyperplanes to any other cut surfaces that are sufficiently regular.

*Remark 11.* A nice consequence of our modification is that we can implicitly define $f$ relatively to $p$, just by defining $f$ as a modification applied to $d$ in the graph. For example, and as argued below, $f := d^r$ refers implicitly to defining the underlying function $f := \beta \cdot p^{r+1}$ for some global scaling factor $\beta$ that only depends on $r$, the sample size $n$ and the intrinsic dimension $d$. This approach is only limited by the fact that the degrees $d$ do not estimate $p$ exactly, since they provide estimates that are proportional to $p$. Precisely, $d_i = \alpha_{n,d} \cdot p(x_i)$ for some global scaling factor $\alpha_{n,d}$ that depends on $n$ and $d$. Usually $n$ is known, but as long as we do not know $d$, we have to make sure that the unknown estimation factor $\alpha_{n,d}$ passes our modification just as another global scaling factor, without introducing some distortion. For example, in the case $f = d^r$ we get that the implicitly defined function $f$ equals $f = \alpha_{n,d}^{r+1} \cdot p^{r+1} = \text{const} \cdot p^{r+1}$ as intended. However, if we define $f := a d^2 + b d + c \mathbf{1}$ for $a, b, c \in \mathbb{R}_{>0}$, then the implicitly defined function $f$ would not refer to $f = ap^2 + bp + c$, but to $f = a\alpha_{n,d}^2 p^2 + b\alpha_{n,d} p + c$ instead. Hence the unknown estimation factor $\alpha_{n,d}$ introduces a distortion that implies that $f$ cannot be represented as $f = \gamma(ap^2 + bp + c)$ for any scaling factor $\gamma$.

Note that $f = d^r$ is not the only valid choice of implicitly defining $f$ in terms of $p$. See for example Section A.1.

Moreover, if $d$ is given as prior information, or from some estimate on the intrinsic dimension, then we can determine $\alpha_{n,d}$ and use it to define $f$ implicitly from $p$ in much more various ways. For example, if we want to study $ap^2 + bp + c$, then defining the new degrees by $f := a d^2 + b \alpha_{n,d} d + c \alpha_{n,d}^2 \mathbf{1}$ would indeed represent $f = a \alpha_{n,d}^2 p^2 + b \alpha_{n,d}^2 p + \alpha_{n,d}^2 c = \text{const} \cdot (ap^2 + bp + c)$ as intended. Hence any good estimate on the intrinsic dimension allows for more powerful ways of how to define $f$ from $p$ implicitly, in order to study volumes and cuts according to $\int fp$.
References

Kannan, R., Lovász, L., and Montenegro, R. Blocking Conductance and Mixing in Random Walks. *Combinatorics, Probability and Computing*, 15(4):541–570, 2006.

Maier, M., von Luxburg, U., and Hein, M. Influence of graph construction on graph-based clustering measures. In *Neural Information Processing Systems (NIPS)*, 2009.

Montenegro, R. Faster Mixing for Conductance Methods. Technical report, 2003.

Nadler, B., Srebro, N., and Zhou, X. Statistical analysis of semi-supervised learning: The limit of infinite unlabelled data. In *Neural Information Processing Systems (NIPS)*, 2009.

Stańczak, S., Wiczanowski, M., and Boche, H. Chapter 1: On the Perron Root of Irreducible Matrices. In *Resource Allocation in Wireless Networks*, volume 4000 of *Lecture Notes in Computer Science*. 2006.

Zlatić, V., Gabrielli, A., and Caldarelli, G. Topologically biased random walk and community finding in networks. *Physical Review E*, 82(6):066109, 2010.