9.1. Approach
125
The corresponding Rayleigh quotient is:
R ˆ
L sns
( f ) =
1
2 ∑
n+2
i, j=1
w
+
i j ( f i − f j ) 2 − w
−
i j ( f i − f j ) 2
∑
n+2
i=1
ˆ
d i f 2
i
=
1
2 ∑
n
i, j=1 A i j ( f i − f j ) 2
∑
n+2
i=1
ˆ
d i f 2
i
+
∑
n
i=1 apw ∗ F i,1 ( f i − f n+1 ) 2
∑
n+2
i=1
ˆ
d i f 2
i
+
∑
n
i=1 apw ∗ F i,2 ( f i − f n+2 ) 2
∑
n+2
i=1
ˆ
d i f 2
i
−
anw( f n+1 − f n+2 ) 2
∑
n+2
i=1
ˆ
d i f 2
i
.
A minimum of the Rayleigh quotient R ˆ
L sns
( f ) corresponds to an embedding that minimizes the total squared distance between connected nodes in the original graphs,
plus the distances of the labelled nodes to the corresponding class-representative
nodes, and maximizes the total squared distance between the two stations, normalized by the modified total degree ˆ
D.
We use the Rayleigh quotient R ˆ
L sns
( f ) as a relaxed version of our objective
function for our graph-based SSL method. Finding the embedding to minimize the
Rayleigh quotient R ˆ
L sns
( f ) is equivalent to finding the eigenvector corresponding to
the smallest eigenvalue of ˆ
L sns . Thus we can use eigendecomposition to find the optimal solution of our objective function. Two-class classification is based on the eigenvector associated with the smallest non-trivial eigenvalue — the nodes are divided
into two groups based on the sign of their corresponding entries in this eigenvector,
and these two groups are predicted to be members of the two classes.
There is also a random-walk interpretation of our approach. For the part of the
graph connected by positive edges, the matrix ˆ
L sns without the class-representative
nodes has the same eigenvectors as the conventional random walk normalized Laplacian matrix L rw = I − D −1 W [84]. A random walk starting from any node wanders
around the graph until it reaches a labelled node, but is then likely to go to the classrepresentative node since the edge to it has high weight. From this perspective, the
random walk measures how likely an unlabelled node is to reach the “nearest” class
representative. In contrast, a random-walk interpretation of activation spreading approaches begins from the labelled nodes. Unlabelled nodes are labelled by the first
random walker that reaches them. When one cluster is small, a random walker from
its labelled node(s) can reach unlabelled nodes in other clusters before the random
walker from their own labelled nodes.
The modified Laplacian matrix ˆ
L sns has most the properties of L sns except for
the range of its eigenvalues. The lower boundary is still −2, but the upper boundary
can exceed 2. The eigendecomposition of ˆ
L sns can be calculated using instead the
symmetric matrix ˆ
D −1/2 (RS −W ) ˆ
D −1/2 . This calculation is fast because the matrix
is symmetric. Since we only need one eigenvector, the complexity of the calculation
is quadratic in n if the matrix is dense, and linear if the matrix is sparse. As we
125
The corresponding Rayleigh quotient is:
R ˆ
L sns
( f ) =
1
2 ∑
n+2
i, j=1
w
+
i j ( f i − f j ) 2 − w
−
i j ( f i − f j ) 2
∑
n+2
i=1
ˆ
d i f 2
i
=
1
2 ∑
n
i, j=1 A i j ( f i − f j ) 2
∑
n+2
i=1
ˆ
d i f 2
i
+
∑
n
i=1 apw ∗ F i,1 ( f i − f n+1 ) 2
∑
n+2
i=1
ˆ
d i f 2
i
+
∑
n
i=1 apw ∗ F i,2 ( f i − f n+2 ) 2
∑
n+2
i=1
ˆ
d i f 2
i
−
anw( f n+1 − f n+2 ) 2
∑
n+2
i=1
ˆ
d i f 2
i
.
A minimum of the Rayleigh quotient R ˆ
L sns
( f ) corresponds to an embedding that minimizes the total squared distance between connected nodes in the original graphs,
plus the distances of the labelled nodes to the corresponding class-representative
nodes, and maximizes the total squared distance between the two stations, normalized by the modified total degree ˆ
D.
We use the Rayleigh quotient R ˆ
L sns
( f ) as a relaxed version of our objective
function for our graph-based SSL method. Finding the embedding to minimize the
Rayleigh quotient R ˆ
L sns
( f ) is equivalent to finding the eigenvector corresponding to
the smallest eigenvalue of ˆ
L sns . Thus we can use eigendecomposition to find the optimal solution of our objective function. Two-class classification is based on the eigenvector associated with the smallest non-trivial eigenvalue — the nodes are divided
into two groups based on the sign of their corresponding entries in this eigenvector,
and these two groups are predicted to be members of the two classes.
There is also a random-walk interpretation of our approach. For the part of the
graph connected by positive edges, the matrix ˆ
L sns without the class-representative
nodes has the same eigenvectors as the conventional random walk normalized Laplacian matrix L rw = I − D −1 W [84]. A random walk starting from any node wanders
around the graph until it reaches a labelled node, but is then likely to go to the classrepresentative node since the edge to it has high weight. From this perspective, the
random walk measures how likely an unlabelled node is to reach the “nearest” class
representative. In contrast, a random-walk interpretation of activation spreading approaches begins from the labelled nodes. Unlabelled nodes are labelled by the first
random walker that reaches them. When one cluster is small, a random walker from
its labelled node(s) can reach unlabelled nodes in other clusters before the random
walker from their own labelled nodes.
The modified Laplacian matrix ˆ
L sns has most the properties of L sns except for
the range of its eigenvalues. The lower boundary is still −2, but the upper boundary
can exceed 2. The eigendecomposition of ˆ
L sns can be calculated using instead the
symmetric matrix ˆ
D −1/2 (RS −W ) ˆ
D −1/2 . This calculation is fast because the matrix
is symmetric. Since we only need one eigenvector, the complexity of the calculation
is quadratic in n if the matrix is dense, and linear if the matrix is sparse. As we