Geoscience Reference
In-Depth Information
48 CHAPTER 5. GRAPH-BASED SEMI-SUPERVISEDLEARNING
value of the harmonic function at vertex
i
,
f(
x
i
)
, is the probability that a particle starting at vertex
i
eventually reaches a positive labeled vertex (see Figure 5.3(b)).
1
R =
ij
w
ij
1
1
+1 volt
0
0
i
(a) The electric network interpretation
(b) The random walk interpretation
Figure 5.3:
The harmonic function can be interpreted as the voltages of an electric network, or the
probability of reaching a positive vertex in an absorbing random walk on the graph.
=
y
i
for the labeled vertices
i
=
1
...l
, and some arbitrary value for the unlabeled vertices. Iteratively
update each unlabeled vertex's
f
value with the weighted average of its neighbors:
There is an iterative procedure to compute the harmonic function in (5.7). Initially, set
f(
x
i
)
l
+
u
j
=
1
w
ij
f(
x
j
)
l
+
u
j
f(
x
i
)
←
.
(5.10)
1
w
ij
=
It can be shown that this iterative procedure is guaranteed to converge to the harmonic function,
regardless of the initial values on the unlabeled vertices. This procedure is sometimes called label
propagation, as it “propagates” labels from the labeled vertices (which are fixed) gradually through
the edges to all the unlabeled vertices.
Finally, let us discuss the closed-form solution for the harmonic function.The solution is easier
to present if we introduce some matrix notation. Let
W
be an
(l
+
u)
×
(l
+
u)
weight matrix, whose
i, j
-th element is the edge weight
w
ij
. Because the graph is undirected,
W
is a symmetric matrix.
Its elements are non-negative. Let
D
ii
=
l
+
u
j
=
1
w
ij
be the weighted degree of vertex
i
, i.e., the
sum of edge weights connected to
i
.Let
D
be the
(l
+
u)
×
(l
+
u)
diagonal matrix by placing
D
ii
,i
=
1
...l
+
u
on the diagonal. The unnormalized graph Laplacian matrix
L
is defined as
L
=
D
−
W.
(5.11)
(f (
x
1
),...,f(
x
l
+
u
))
be the vector of
f
values on all vertices. The regularizer in (5.7) can
be written as
Let
f
=
l
+
u
1
2
f
L
f
.
w
ij
(f (
x
i
)
−
f(
x
j
))
2
=
(5.12)
i,j
=
1
