graphembedding/deepwalk/README.md

## 项目简介

DeepWalk是一种基于随机游走的图嵌入算法。它通过在图上进行随机游走，采集节点序列，并将这些序列作为训练数据，来学习图中节点的低维表示（embedding）。这些表示可以用于许多图分析任务，例如节点分类、聚类、链路预测等。这个项目在DeepWalk算法的基础上，支持使用别名采样（Alias Sampling）来加速随机游走过程，并增加了使用Softmax进行采样的选项，同时引入了书籍内容的标签游走机制，以增强图嵌入表示的多样性和内容相关性。

### 对标准deepwalk方法的特殊改进

基于以下几个原因：
1. **用户行为的个性化不明显**：当前的书籍推荐没有个性化算法，因此用户曝光的书籍同质化非常严重，导致推荐给用户的书籍存在严重的同质化现象，进而影响用户点击和阅读书籍的多样性。同时，由于平台用户数量较少，因此难以从这种用户行为数据中学习出书籍表征的差异度。
在掌阅 deepwalk 的结果 item 相关性非常好，比如玄幻书籍的相似书就基本都是玄幻、热血这类兴趣点很相似的书，因此书籍详情页的“相似书推荐”也采用了这个方法，并且deepwalk也是其在线推荐系统的绝对主力之一，这一类公司在做deepwalk的时候可能为了避免推荐的茧房效应会做一些策略增加游走的多样性。我们是完全相反的，用户基本上都是在看运营推荐的高热书籍，用户行为没有显著的个性化。
2. **书籍点击量的基尼系数高**：依赖于运营配置进行推荐的书籍基尼系数较高。


因此：

1. 在DeepWalk基础上增加书籍内容标签（tags）游走机制，提高推荐系统的内容多样性，解决推荐结果同质化的问题。通过参数配置，可以在内容相似度和行为相似度之间取得平衡，tags游走的概率越高，推荐结果的内容多样性越好，越低则会受到曝光书籍的同质化问题影响越严重，配置为0则为标准的deepwalk方法。
2. node2vec方法和EGES方法也可以引入书籍的side information，利于冷门书籍的表征学习的准确性。如果仅仅用于书籍表征的学习，本方法相比于node2vec效果更好。EGES的思路也是在deepwalk的基础上补充side information信息让书籍的表征受到tags和categories等属性的影响，具有类似的效果，但是实现复杂度略高。结合数据情况和具体场景，选择在deepwalk的基础上增加书籍内容标签（tags）游走机制作为最终方案。

## 功能模块

1. **图的构建**：从边文件读取图，并为每个节点构建邻居关系。
2. **别名采样表构建**：为每个节点的邻居预处理别名采样表，加速随机游走过程。
3. **Softmax支持**：支持使用Softmax函数对邻居节点进行加权采样，并加入温度（temperature）参数进行控制。
4. **随机游走模拟**：在图中执行多次随机游走，生成序列。
5. **标签游走机制**：支持基于书籍标签的游走，以提高内容相关性。通过节点-标签关联，以一定概率通过标签游走。
6. **多进程支持**：使用并行处理，提升随机游走的效率。
7. **结果保存**：将生成的游走序列保存为文本文件，以便后续的词嵌入模型（如Word2Vec）使用。

## 项目结构

``` 
project/
│
├── deepwalk.py          # DeepWalk的核心代码
├── alias.py             # 用于别名采样的工具函数
├── run.sh               # 运行DeepWalk程序的shell脚本
├── README.md            # 项目说明文档
└── data/
    └── edge.txt         # 示例边文件
``` 

## 依赖库

此项目依赖以下第三方库：
1. numpy：用于矩阵和数组操作
2. networkx：用于图的构建与处理
3. joblib：用于并行处理
4. argparse：用于解析命令行参数
5. multiprocessing：支持多进程处理
6. tqdm：用于显示进度条
7. logging：用于日志记录

## 实现逻辑

1. **构建图**

从给定的边文件中读取数据，构建无向加权图。边文件的格式如下：
``` 
bid1    bid2:weight1,bid3:weight2,...
``` 
每行表示一个节点及其邻居节点列表。每个邻居节点有一个对应的权重值。
代码实现：
``` python
def build_graph_from_edge_file(self, edge_file):
    G = nx.Graph()
    with open(edge_file, 'r') as f:
        for line in f:
            parts = line.strip().split('\t')
            if len(parts) != 2:
                continue
            node, edges_str = parts
            edges = edges_str.split(',')
            for edge in edges:
                nbr, weight = edge.split(':')
                G.add_edge(int(node), int(nbr), weight=float(weight))
    return G
``` 

2. **别名采样表的构建**

为了加速加权随机游走，使用别名采样（Alias Sampling）来为每个节点构建采样表。每个节点的邻居按照边权重进行采样。
代码实现：
``` python
def preprocess_transition_probs(self):
    G = self.graph
    for node in G.nodes():
        unnormalized_probs = [G[node][nbr].get('weight', 1.0) for nbr in G.neighbors(node)]
        norm_const = sum(unnormalized_probs)
        normalized_probs = [float(u_prob) / norm_const for u_prob in unnormalized_probs]
        self.alias_nodes[node] = create_alias_table(normalized_probs)
``` 

3. **Softmax采样支持**

提供了一个选项，允许使用Softmax函数对邻居节点进行加权采样。Softmax函数可以加入温度参数，使得采样更具多样性或更加集中。
代码实现：
``` python
def preprocess_transition_probs__softmax(self, temperature=1.0):
    G = self.graph
    for node in G.nodes():
        unnormalized_probs = [G[node][nbr].get('weight', 1.0) for nbr in G.neighbors(node)]
        normalized_probs = softmax(unnormalized_probs, temperature)
        self.alias_nodes[node] = create_alias_table(normalized_probs)
``` 

4. **标签游走机制**

引入书籍内容标签，以一定概率通过标签进行游走。节点-标签词典包括：
- **node_to_tags**：保存每个节点关联的标签列表（正排索引）。
- **tag_to_nodes**：保存每个标签对应的节点列表（倒排索引）。

游走过程：增加了 `p_tag_walk` 参数，用于控制游走时选择邻居节点和通过标签游走的概率。当通过标签游走时，随机选择一个与当前节点关联的标签，从该标签下的节点中随机选择一个新的节点。

5. **随机游走**

基于别名采样表执行随机游走，并返回游走序列。游走函数根据设定的概率 `p_tag_walk` 来决定是通过邻居游走还是通过标签游走。
代码实现：
``` python
def deepwalk_walk(self, walk_length, start_node):
    G = self.graph
    alias_nodes = self.alias_nodes
    walk = [start_node]
    while len(walk) < walk_length:
        cur = walk[-1]
        cur_nbrs = list(G.neighbors(cur))
        if len(cur_nbrs) > 0:
            idx = alias_sample(alias_nodes[cur][0], alias_nodes[cur][1])
            walk.append(cur_nbrs[idx])
        else:
            break
    return walk
``` 

6. **多进程模拟**

为了提升效率，支持使用多进程进行游走模拟。每个进程负责一部分节点的游走。
代码实现：
``` python
def simulate_walks(self, num_walks, walk_length, workers, output_file):
    G = self.graph
    nodes = list(G.nodes())
    results = Parallel(n_jobs=workers)(
        delayed(self._simulate_walks)(nodes, num_walks // workers, walk_length)
        for _ in range(workers)
    )
    walks = list(itertools.chain(*results))
    self.save_walks_to_file(walks, output_file)
``` 

## 使用说明

1. **环境配置**

首先需要安装项目所依赖的Python库。可以通过以下命令安装：
``` bash
pip install numpy networkx joblib tqdm
``` 

2. **运行DeepWalk**

可以通过命令行运行 deepwalk.py，提供必要的参数：
``` bash
python deepwalk.py --edge-file <path_to_edge_file> --num-walks <num_walks> --walk-length <walk_length> --workers <num_workers> --output-file <output_file> [--use-softmax] [--temperature <temperature>]
``` 

3. **示例**

假设我们有一个边文件 data/edge.txt，并希望使用Softmax加权采样，温度为0.5，进行10次随机游走，游走长度为40，使用4个工作线程。可以通过以下命令运行：
``` bash
python deepwalk.py \
    --edge-file path_to_edge_file.txt \
    --node-tag-file path_to_node_tag_file.txt \
    --num-walks 10 \
    --walk-length 40 \
    --workers 4 \
    --p-tag-walk 0.2 \
    --output-file path_to_output_walks.txt
``` 

4. **使用 run.sh 自动运行**

``` bash
sh run.sh
``` 


## 输出格式

生成的随机游走序列将保存在指定的输出文件中，每一行表示一次游走的结果，格式如下：
``` 
1 2 3 4 5 ...
2 3 4 1 6 ...
...
``` 

## 参考
``` 
[DeepWalk: Online Learning of Social Representations](https://arxiv.org/abs/1403.6652)
``` 

## 代码结构概述

该项目的核心在于对DeepWalk算法的扩展，通过标签游走机制提高了内容推荐的多样性。以下是源码的主要模块：

1. **Graph Construction**：用于从边文件中构建无向图。
2. **Alias Sampling Table Creation**：预处理每个节点的邻居信息以加速随机游走。
3. **Softmax and Temperature Control**：增加了基于Softmax的采样机制，允许通过调整温度参数控制采样的多样性。
4. **Tag-based Walks**：在标准的邻居随机游走基础上，加入了标签游走逻辑，通过内容标签来引导游走路径。
5. **Multiprocessing Support**：利用多进程加速大规模游走模拟，提升算法的执行效率。

## 扩展说明

引入书籍标签游走机制的目的是在现有的基于用户行为的图嵌入算法中加入内容信息，尝试在以下方面提升推荐效果：

- **提高内容多样性**：通过标签游走机制，使得推荐结果不仅基于用户的行为，还考虑到内容相似性。
- **解决同质化问题**：缓解现有推荐系统中由于数据稀疏或用户行为单一导致的同质化现象。
- **兼顾个性化**：在行为相似和内容相似之间取得平衡，使得用户能够获得更具个性化的推荐结果。

## 关键技术点

1. **标签游走机制（Tag-based Walks）**
   - 通过设定 `p_tag_walk` 参数，控制游走时使用标签的概率，默认值为0.2，即20%的游走路径通过标签引导。
   - 标签游走的实现方式是：随机选择一个与当前节点关联的标签，然后从该标签关联的节点集中选择下一个游走节点。这种方式能够有效地利用书籍的内容标签，提高内容推荐的相关性。

2. **Softmax采样与温度控制**
   - Softmax采样增加了温度参数，控制采样结果的多样性。较低的温度值使得采样更倾向于权重较大的邻居，而较高的温度值使得采样结果更为均匀分布。

3. **多进程支持**
   - 为了在大规模数据上提升随机游走的效率，采用了并行处理技术，每个进程负责一部分节点的游走任务。通过这种方式，算法可以充分利用多核CPU的性能，大大加快了图嵌入的训练速度。