社交媒体网络已经遍布全球，并且每天都在增长。对于一个社交网络，你知道一些人的兴趣，你想预测其他人的兴趣，这样我们就可以有针对性地进行营销活动。为此，我们可以使用叫标签传播的基于图的半监督机器学习技术。在本文中，我将通过一些示例和示例代码解释标签传播过程。

什么是标签传播？

标签传播算法(LPA)是一种迭代算法，通过在数据集中传播标签，将标签分配给未标记的点。该算法由Xiaojin Zhu和Zoubin Ghahramani于2002年首次提出。LPA属于转换学习，因为我们要预测已经给出的未标记数据点的标签。

假设我们有一个如下所示的网络，其中有两个标签类“interested in cricket”（对板球感兴趣）和“not interested in cricket”（对板球不感兴趣）。所以问题是，我们能预测剩下的人是否对板球感兴趣吗？

为了让LPA在这种情况下起作用，我们需要做一个假设，通过边连接的两个节点的边具有相似性。也就是说，如果两个人是连在一起的，这意味着这两个人很有可能拥有相同的兴趣。我们可以做出这样的假设，因为人们倾向于与有相似兴趣的人交往。

在图中随机游走

考虑图1中给出的示例图，其中我们有2个标签类(红色和绿色)和4个着色的节点(每个类2个)。我们想预测节点4的标签。

我们可以在图中随机行走，从节点4开始，直到遇到任何标记节点。当我们到达一个标记节点时，我们停止游走。因此，这些标记的节点被称为吸收状态。让我们考虑所有可能的从节点4出发的路径。在所有可能的路径中，以下路径将以绿色节点结束。

1. 4 → 9 → 15 → 16
2. 4 → 9 → 13 → 14
3. 4 → 9 → 13 → 15 → 16
4. 4 → 9 → 15 → 13 → 14

下面的路径以红色的节点结束。

1. 4 → 7 → 8
2. 4 → 7 → 6 → 5 → 1
3. 4 → 5 → 1
4. 4 → 5 → 6 → 7 → 8
5. 4 → 2 → 1

基于从节点4开始的所有可能的随机游走，我们可以看到大多数的游走都以红色节点结束。我们可以把结点4涂成红色。这是LPA背后的基本直觉。

数学公式

Xₗ是所有节点的标签的集合，Yₗ是已标记数据的one-hot标签。假设有{1,…,C}类标签，Xᵤ 是未标记的顶点，我们不知道Yᵤ是什么，因此Yᵤ是全0的。

我们通过下面的公式来表示随机游走。

在矩阵形式下，等式是下面这样的：

如果我们可以计算概率转移矩阵T，我们可以计算所有未标记节点的标签概率。

如何计算概率转移矩阵？

考虑具有吸收状态的示例图，如图4所示。对于每个节点，我们需要计算跳转到其他节点的概率。当我们到达吸收状态时，当我们被困在吸收状态(在图中表示为一个自循环)时，游走结束。这是一个无向图，所以我们可以向任何方向移动。

假设从一个节点转移到它的邻居的概率是等可能的，我们可以把T写为：

从节点1到节点1的概率是1，因为节点1是吸收状态。从节点1，我们不能到达任何其他节点。因此从节点1到达其他节点的概率为0。同样的方法也适用于节点2。

从节点4，可以转到节点1、3和5。因此，从节点4移动到节点1、3和5的概率相等，每个节点的概率为0.33。类似地，从节点5，我们可以以每个节点0.5的概率移动到节点4和6。

注意，我们可以使用图的度矩阵(D)和邻接矩阵(A)计算T，使用下面的公式。

T = D⁻¹A

现在注意，我们可以分解矩阵T，如图6所示。

• Tₗₗ — 从已标记节点到已标记节点的概率
• Tₗᵤ — 从已标记节点到未标记节点的概率
• Tᵤₗ — 从未标记节点到已标记节点的概率
• Tᵤᵤ — 从未标记节点到未标记节点的概率

注意：Tₗₗ是一个单位矩阵，Tₗᵤ是零矩阵，因为我们不能从已标记的节点离开，因为它们是吸收状态。

如果我们将矩阵T和自己相乘t次，然后t趋于∞会发生什么？你可以在MATLAB中输入这个矩阵然后得到 T¹⁰⁰。你会得到这样的结果。

当你把T的次方的数量提高，概率将停止变化(饱和)，并得到稳定的转移概率。现在可以看到，只有前两列包含非零值，其余的都是零。

我们可以用数学的方法来描述它。

得到最后的答案

最后，带标签的矩阵是这样的，我们可以得到带标签节点的标签向量和未带标签节点的标签向量。

现在让我们考虑图4中的示例图2，我们希望预测未标记节点的标签。利用MATLAB的结果，我们可以得到如下的标签。

对于每个未标记节点，我们分配概率最大的类标签。但是，可以看到节点5出现红色和绿色的概率是相等的。因此，我们最终的标记图将如图10所示。

示例代码

创建图：

from igraph import *

node_count = 7

# Create graph
g = Graph()

# Add vertices
g.add_vertices(node_count)

for i in range(len(g.vs)):
    g.vs[i]["id"]= i
    g.vs[i]["label"]= str(i+1)

edges = [(0,3), (2,3), (3,4), (4,5), (5,6), (5,1)]

g.add_edges(edges)

g.simplify(multiple=True, loops=False, combine_edges=None)

out_fig_name = "graph_plot.png"

visual_style = {}

# Define colors for nodes
node_colours = ["red", "green", "grey", "grey", "grey", "grey", "grey"]
g.vs["color"] = node_colours

# Set bbox and margin
visual_style["bbox"] = (500,500)
visual_style["margin"] = 17

# # Scale vertices based on degree
# outdegree = g.outdegree()
visual_style["vertex_size"] = 25

# Set vertex lable size
visual_style["vertex_label_size"] = 8

# Don't curve the edges
visual_style["edge_curved"] = False

# Set the layout
layout_1 = g.layout_fruchterman_reingold()
visual_style["layout"] = layout_1

# Plot the graph
plot(g, out_fig_name, **visual_style)

得到度矩阵和逆

import numpy as np
from numpy.linalg import inv

D = np.matrix(np.array([[1,0,0,0,0,0,0], [0,1,0,0,0,0,0], [0,0,1,0,0,0,0], [0,0,0,3,0,0,0], [0,0,0,0,2,0,0], [0,0,0,0,0,3,0], [0,0,0,0,0,0,1]]))
Dinv = inv(D)

得到邻接矩阵

A = np.matrix(np.array([[1,0,0,0,0,0,0], [0,1,0,0,0,0,0], [0,0,0,1,0,0,0], [1,0,1,0,1,0,0], [0,0,0,1,0,1,0], [0,1,0,0,1,0,1], [0,0,0,0,0,1,0]]))

D的逆和A相乘

S = Dinv*A

标签传播算法

import sys

def LabelPropagation(T, Y, diff, max_iter, labelled):
    
    # Initialize
    Y_init = Y
    Y1 = Y
    
    # Initialize convergence parameters
    n=0
    current_diff = sys.maxsize
    
    # Iterate till difference reduces below diff or till the maximum number of iterations is reached
    while current_diff > diff or n < max_iter:
        
        current_diff = 0.0
        # Set Y(t)
        Y0 = Y1
        
        # Calculate Y(t+1)
        Y1 = T*Y0
        
        # Clamp labelled data
        for i in range(Y_init.shape[0]):
            if i in labelled:
                for j in range(Y_init.shape[1]):
                    if i!=j:
                        Y1.A[i][j] = Y_init.A[i][j]
        
        # Get difference between values of Y(t+1) and Y(t)
        for i in range(Y1.shape[0]):
            for j in range(Y1.shape[1]):
                current_diff += abs(Y1.A[i][j] - Y0.A[i][j])
        
        n += 1
        
    return Y1

运行标签传播算法:

%%time
Y = np.matrix(np.array([[1,0], [0,1], [0,0], [0,0], [0,0], [0,0], [0,0]]))
L = LabelPropagation(S, Y, 0.0001, 100, [0,1])

未标记节点的标签：

L.argmax(1)

最后的想法

LPA使用已标记节点的标签作为基础，并尝试预测未标记节点的标签。然而，如果最初的标签是错误的，这可能会影响标签的传播过程，错误的标签可能会被传播。为了解决这个问题，我们引入了标签扩展，在学习无标签节点的标签的同时也学习有标签节点的标签。这也是一种标签校正的应用。你可以从Dengyong Zhou等人的文章Learning with Local and Global Consistency中了解更多关于标签传播的信息。