124
Chapter 9. Signed graph-based semi-supervised learning
labelled as the first class, F i = [0, 1] if node x i is labelled as the second class, and
F i = [0, 0] if node x i is not labelled. Then the (n + 2) × (n + 2) adjacency matrix W
of the new graph with extra nodes is defined as:
W =



A
apw ∗ F
apw ∗ F
0
−anw
−anw
0


 .
(9.1)
The modified total degree ˆ
D of the new graph is a (n + 2) × (n + 2) diagonal matrix
with diagonal value:
ˆ
D ii =
n
∑
j=1
|A i j |,
∀i ∈ [1, n],
ˆ
D ii = anw + apw ∗
n
∑
j=1
F i−n, j , ∀i ∈ [n + 1, n + 2].
(9.2)
Let RS be the row sum diagonal matrix of W , that is, RS ii = ∑
n+2
j=1 W i j . Then the
modified signed Laplacian becomes:
ˆ
L sns = ˆ
D
−1 (RS −W )
where RS −W = (D + −W + ) − (D − −W − ).
Thus, the positive part W + of the new graph with extra nodes, a (n + 2) × (n +
2) matrix, is defined as:
W
+ =
A
apw ∗ F
apw ∗ F
0
.
The negative part, the (n + 2) × (n + 2) matrix W − , is defined as:
W
− =







0 · · · 0
0
0
. . .
. . .
. . .
. . .
. . .
0 · · · 0
0
0
0 · · · 0
0
anw
0 · · · 0 anw
0







.
The modified total degree ˆ
D of the new graph is a (n + 2) × (n + 2) diagonal matrix
with diagonal value:
ˆ
D ii =
n
∑
j=1
A i j , ∀i ∈ [1, n]
ˆ
D n+i,n+i = anw + apw ∗
n
∑
j=1
F i j , ∀i ∈ [1, 2]
The modified signed Laplacian becomes:
ˆ
L sns = ˆ
D
−1
(D
+ −W
+ ) − (D
− −W
− )