文章背景

题目：《node2vec》:Scalable Feature Learning for Networks
来源：ACM SIGKDD 2016
作者：Aditya Grover、Jure Leskovec(都是stanford cs)

Abstract

1. 动机：前人工作没有捕获连接模式的多样性，本文将维护节点的邻域。

2. 贡献：

   • 拓展了邻域的概念
   • 设计了有偏差的随机游走，这对不同邻域都有效
   • 是前人”严格定义邻域”的泛化，证明了“拓展邻域的概念”可以更丰富表达

3. 适用场景：多标签分类任务、链接预测任务

4. 适用于有向\无向，有权重\无权重的图。

1.Introduction

1. 节点两种属性：
   • 同质性(属于同一个社区;homophily)
   • 结构角色(比如是中心节点;structural role)
   • 在真实场景中，这两种属性是混合的

Present work

1. node2vec属于半监督

2. 使用了word2vec中的skip-gram,SGD
   

3. 最大化节点邻域的可能性(likelihood)
4. 使用了2阶随机游走
5. 关键贡献是对节点的邻域做了更为灵活的定义
6. 扩张方面：也对边做了embedding，即对边进行向量表示。(其实就是对边的两个点的embedding做二元运算)
7. 对标算法：DeepWalk LINE
8. 模型性能：多标签提升了26.7%,连接预测提升了12.6%。甚至只用了10%的数据时，效果也很好。
9. 可并行化计算，可扩展到大规模网络(几百万节点)

Contribution

没什么干货

2.Related work

1. skim-gram是基于分布式假设的：在相似上下文中出现的单词有相似的含义，即相似的单词出现在相似的上下文中。（感觉这两句话是一个意思）
2. node2vec优势：前人工作的模型效果强依赖于对节点的采样策略，node2vec设计了一个灵活的评价函数，可以不强依赖于特定的采样策略，并且增加了超参数可以用于调节采样空间。
3. 最后一段好像是在说DNN的思想和缺陷。

3.Feature learning framework

1. 基于两点假设：
   • 独立性假设
   • 对称性假设

3.1Classic search strategies

1. BFS探索的是结构性，DFS探索的是同质性。
2. BFS优点：减小方差，但是探索的范围太小
   DFS优点：没有捕获连接中的依赖关系的实质，高方差，路径太深就没有代表性了、依赖关系也会变得复杂。

3.2node2vec

1. 参数q控制了DFS和BFS之间的平衡。
2. 本文的随机游走是2阶的Markovian。(没有证明，我也不太清楚)
3. 随机游走的好处：
   • 内存开销小
   • 时间复杂性低

4.Experiments

实验章节还是非常严谨的，只是现在和我的实现无关，因此粗看，后续要细看一下这个实验部分。

我自己的一些想法

1. 在3.Feature learning framework中做出了对称性的假设，但我觉得后文其实没有用上。
   要是让我做，可能需要设计一个考虑方向的评价函数。

2. 在3.1Classic search strategies中，我不认为“BFS探索的是结构性”。
   

文章背景

题目：《LINE:Large-scale Information Network Embedding》
来源：World Wide Web2015
作者：Jian Tang等

Abstract

1. 动机：处理更大规模的图。
2. 优势：可适用于有向/无向、有权重／无权重 的图。+ 以下两点创新。
3. 两点创新：
   • 新的评价函数：既关注了局部信息，也关注了全局信息。(first-order和second-order)
   • 边采样方法：突破了SGD的限制，既快又好，还使得可处理规模更大。
4. 适用场景：语言网络、社交网络、引用网络
5. 处理规模：百万点+十亿边 单机几个小时就处理完

Introduction

1. first-order:边直接相连，真实场景中很稀疏。

2. second-order:共享邻居的节点。有相同**邻居社区**的两个节点，它俩也应该是相似的。
   

3. 关系：second-order可以补充first-order的稀疏性，并且保留了网络的全局结构。
4. SGD缺陷：边的权重有很高的方差，梯度乘上这些大权重的话容易引起梯度爆炸。
   本文提出的edge-smapling将权重作为被选中的概率，然后将所有的边转化为binary边，消除了梯度爆炸问题。

Related work

deepwalk缺陷：

1. 没有说明具体保留了图的什么性质。（我觉得说清楚了，就是二阶性质啊）
2. 做出了假设：second-order更高的两个点有更相似的embedding。
3. 使用了DFS，而本文使用了BFS，更接近second-order。(我还是觉得DFS好一些，更符合word2vec)
4. 只能处理无权边。

4.LINE:

4.1Model Description

4.1.1 first-order

只能处理无向边

4.1.2 second-order

1. 有向\无向 均可。
2. 每个点都有两个角色：自己本身和作为其他点的邻居。
3. second-order在LINE中是单向定义，即最大化v_j是v_i邻居的概率。

4.1.3 Combineing first-order and second-order proximities

1. 目前的策略是分别训练，然后拼接
2. 后续方案可能是联合训练

4.2Model Optimization

1. 负采样，由于公式4需要遍历整个节点集合-计算量大，因此采用negative sampling。
2. second-order具体更新时，只更新了中心节点i的embedding。

4.2.1Optimization via Egde Sampling

1. 动机：避免梯度爆炸
2. 采样过程：从原始边集中进行采样，选中的概率和边的权重正相关。
3. 原理：通过概率采样，既将有权边转化成无权边，又考虑到了权重的作用。
4. 预处理过程中采用了alias table来简化采样过程，好像比较有用，具体不清楚。

4.3Discuss

1. 本文认为second-order严重依赖邻居，对于出度小的节点不友好，因此还采样了邻居的邻居作为邻居。
2. 对于新添加的点，使用老点对新点进行更新，并且维持老点的embedding不变。我对公式10有疑问。

5实验

设置：

1. 数据集：一个语言网络、两个社交网络、两个引用网路。
2. Baseline: Graph factorization、DeepWalk、使用SGD的LINE、使用edge-sampling的LINE、结合了first-order和dsecond-order的LINE。
3. 最终都对embedding进行了归一化。
4. 单机多线程。

结论：

1. second-order比first-order更能抓住单词之间的语义关系。
2. Deepwalk在语言模型中表现不好，是因为忽视了边的权重，这很重要。
3. 使用SGD的LINE在语言模型中发生了梯度爆炸。
4. second-order和first-order可以互补。
5. 社交网络中first-order比second-order重要。
6. 社交网络比语言网络更稀疏。
7. second-order对稀疏场景的处理不如first-order。
8. second-order对degree低的点效果也不好。
9. embedding的维度太大时，效果会变差。
10. 扩展性方面，差不多可以达到线性加速，但是模型效果还是很稳定的。

6.Conclusion

1. second-order和first-order可以互补;
2. edge-sampling可以解决SGD的限制；
3. LINE又快又好；
4. 未来准备探索更高的order,还探索异构图(点的类型不同)

我自己的想法

1. Introduction中为什么说second-order可以保留了网络的全局结构？
2. (已解决)Introduction中：SGD中，为什么边的权重要乘以梯度？答案请看4.2。
3. Related work中：DFS vs. BFS 到底谁好？
4. second-order具体更新时，可以既更新中心节点i的embedding，又更新邻居节点j的embedding吗？我觉得是可以的啊，每次固定一个即可！
5. 公式1和公式4的区别在哪里？ p1和p2的经验概率公式的区别又在哪里？我觉得没有对应起来！！公式4根本看不出来与方向有关啊,而且并不能描述出neighborhood的属性，要是我做的话，我会选取节点v的两个相邻节点m和n,然后看U_m和U_n的关系。
6. 不理解公式10。
7. 采样方法中，BFS是取代DFS，还是作为DFS的补充？

文章背景

题目：《DeepWalk:Online Learning of Social Representations》
来源：ACM SIGKDD2014
作者：Bryan Perozzi、Rami AI-Rfou、Steven Skiena

Abstract

1. 动机：对网络中每个节点进行低维向量表示。
2. 一句话概括思路：首先在节点之间进行有截断的随机游走获得节点序列，这时节点可以看作是单词，序列可以看作是句子；然后用NLP的方式对随机游走的输出进行训练，最终获得每个节点的低维向量表示。
   因此对于该框架：输入是图，输出是每个节点的低维向量表示。
3. 适用场景：多标签网络分类任务——BlogCatalog、Flickr、Youtube。文章说它还可以用于异常检测。
4. 特点:
   • 稀疏性: 针对稀疏场景，可以提升10%的F1；在一些实验中，DeepWalk仅适用60%的数据就超过了已有方法。
   • 可扩展性：在线学习、增量学习、可并行化。
   • 无监督。

1.Introduction

贡献点：

1. 利用了深度学习(DL)对图进行表示。学习到了图的结构规律的表达。
2. 效果：针对稀疏场景，可以提升10%的F1；在一些实验中，DeepWalk仅适用60%的数据就超过了已有方法。
3. 并行性：算法是并行实现的。

3.Learning social representations

1. 适应性：增量学习
2. 低维向量之间的距离应该表示为两个节点的相似性，这样可以用于社团发现。
3. 低维表示泛化能力更强，加速训练和预测。
4. 低维向量表示是连续表示。因此对于社团之间的边界区分比较平滑，增强了分类的鲁棒性。

3.1 Random Walks

优势：

1. 易于并行化：不同线程读入同一个图，但是异步可以输出不同的线路。
2. 增量学习：图发生小变化时，只需要对改动区域进行随机游走即可，不必重新计算整个图。迭代地进行增量学习，最终即使整个图发生变化，训练也不受影响。

3.2 Connection: Power laws

1. 一条没有被证明的结论：如果连通图的度分布遵循幂律（即无标度），我们观察到顶点出现在短随机游走中的频率也将遵循幂律分布。
   我自己理解的幂律分布：多数词被提及的次数很少，很少的词被提及了很多次。
2. 一条可能已经被证明了的贡献：因为NLP符合幂律分布，网络结构也符合幂律分布，因此适用于NLP的方法同样可以用于处理网络结构。

4.Method

4.1Overview

语料集：随机游走序列的集合。
单词表：节点集合。

4.2Algorithm

####4.2.1 skipgram
skipgram最大化了一个窗口中单词共现的概率。
####4.2.2 hierarchical softmax
文章真正使用的方法。

4.3Parallelizability

1. 可以并行化的理由：低频词是稀疏的。
2. 并行化方法：因此使用ASGD，多线程单机器。
3. 效果：线性加速，模型效果基本不受到影响。

4.4Algorithm variants

两种：streaming和non-random walks

1. streaming:不必看到整个图，局部图直接可以用来更新。
2. non-random walks:有的网络不必使用random walk,直接利用本来的顺序更好，比如句子中本来是有顺序的，skipgram是可以利用到这种顺序信息的。

5.Experimental design

代码和数据都开源了。
介绍了数据集和baseline。

6.Experiments

6.1Multi-label classification

使用了one-vs-other logistic regression

6.2Parameter sensitivity

6.2.1Effect of dimensionality

1. 最优维度d依赖于训练数据大小。
2. 模型效果依赖于迭代次数(最少30次)。

6.2.2Effect of sampling frequency

开始迭代次数越高越好，后来增加迭代次数不能带来更明显的收益。

8.Conclusion

1. 只利用局部信息，不必看到完整的图
   适用于多标签分类任务
2. 可输入更大规模的图
   可并行化
3. Deepwalk得到的结论反过来可以用于优化NLP

我自己的一些想法

1. 4.2中提及随机游走的长度不必都相同(虽然实验中它是固定的)，那长度是否会影响训练效果呢，又如何判断什么时候结束随机游走？（路线：长度是否会影响训练效果—>如何选取每次的长度，即什么时候应该结束）
2. 4.2中提及restart没有用，但好像node2vec中提及了这个作用，后续注意一下吧。
3. word2vec中为什么窗口中单词的顺序不重要？
4. deepwalk利用word2vec的skipgram和hierarchical softmax是否有区别？我猜应该有。
5. deepwalk和word2vec的本质目的到底是否相同？deepwalk是探寻节点之间的相似性，用于社团发现。word2vec是去寻找近义词或者反义词。如果是这样的话，两个方法之间还是有一点不同的呀！
6. 4.3中我承认的分布是稀疏的，但是也是稀疏的吗？为什么可以同时使用无锁更新？

1. python打印路径，这几个命令在tb.py当中执行：

1
2
3
4
5
6
7

print '*'*20
print os.getcwd() #假设是A执行了tb.py,则打印A的所在路径(以tb.py结尾)
print '*'*20
print sys.path[0] #打印tb.py的路径(不以tb.py，以tb.py的父亲的路径结尾)
print '*'*20
print sys.argv[0] #打印tb.py的路径,相对路径执行脚本则会返回相对路径,绝对路径执行脚本则返回绝对路径(以tb.py结尾)

1. sudo nmap ip 可以查看远程服务器哪些服务,但是不准确，因为一般是通过端口推断服务类型的；

2. 端口检测
   2.1 ss -antup|grep 9000这个在本机查看哪些端口都开通了哪些服务，比较准确；
   2.2 lsof -i | grep :80查看端口被谁占用
   2.3 sudo iptables -nvL可以查看防火墙的设置

3. 一般来说，一个端口只能对应一个服务。

4. 服务器满了怎么办？ 比较有用的命令：

   du -h –max-depth=1 .
   ls -lh 显示大小kb、M、GB
   lsof |grep deleted
   mac : du -hd1 | sort -h

5. find -type d | grep -v ‘自定义排除的文件名称’|xargs rm -r

6. 我在脚本A里nohup的方式运行一个脚本B，然后A一直循环，现在我kill A或者ctr+c结束A，那么B结束吗？

7. 自己搭建的博客

   nginx(反向代理)：接收端口(监听)——80 转发到2368端口
   Ghost：接收端口——2368，并且设置host为0.0.0.0，代表了本机所拥有的全部ip,意思其实就是本机

   mysql:接收端口——3306 发送端口——

8. hosts文件的优先级高于DNS查询。

9. strace命令还是挺有用的，常用来跟踪进程执行时的系统调用和所接收的信号。

10. 安装之前请先更新

1
2
3

sudo apt-get update
sudo apt-get upgrade
sudo apt-get update

11. 阿里云的服务器本来就是虚拟化出来的，并是真正的物理服务器，所以在这上面跑程序或设计东西，要时刻注意！！

12. ssh分发密匙a主机输入ssh-copy-id root@...

13. wget -e use_proxy=yes -e http_proxy=$proxy http://www.gutenberg.org/cache/epub/132/pg132.txt\

14. sudo iptables -I INPUT -p tcp –dport 33333 -j ACCEPT
    sudo iptables -nvL

15. curl myip.ipip.net 查询ip和运营商

16. 关于压缩
    压缩： tar jpg.tar.gz *.jpg
    tar -cvf lr_minibatch_set.tar lr_minibatch local.conf lr_task.conf load_data_final.sh cache_data/ log/ conf/
    解压：tar -xvf

17. 循环执行命令watch:

18. 总核数 = 物理CPU个数 X 每颗物理CPU的核数
    总逻辑CPU数 = 物理CPU个数 X 每颗物理CPU的核数 X 超线程数
    查看物理CPU个数:

1
2
3

cat /proc/cpuinfo| grep "physical id"| sort| uniq| wc -l
```  
查看每个物理CPU中core的个数(即核数)

cat /proc/cpuinfo| grep “cpu cores”| uniq

1

查看逻辑CPU的个数  

cat /proc/cpuinfo| grep “processor”| wc -l

1
2
3
4
5
6
7
8
9
10
11
12
13
14

19. 在linux系统中"."代表当前目录，"*"代表匹配任意文件

20. markdown在每一行末尾打两个空格然后回车下一行继续写就可以在显示的时候自动换行了。

21. git:  
git rm -r --cached .

22. ```rsync -avz 文件夹或文件名称 mqq@ip:/home/svn/hbsun``` 或者 ```Use rsync -a backup/ backupArchives/ instead. After that rm -rf backup/*.```

23. 使用-e选项对脚本的执行进行检查，一旦出错就不会继续执行了。
    `#!/usr/bin/env bash -e`
    
24. [后台执行命令](https://www.cnblogs.com/zzyoucan/p/7764590.html)    

nohup command > myout.file 2>&1 &
nohup python dis_mnist.py > myout.file 2>&1 &;exit

1

25. [rsync传输指定端口](https://stackoverflow.com/questions/4549945/is-it-possible-to-specify-a-different-ssh-port-when-using-rsync)

rsync -avz -e ‘ssh -p 22003’ /Applications/PyCharm.app/Contents/helpers/ [email protected]:/home/hbsun/.pycharm_helpers

1
2

26. [pycharm的console bug:](https://youtrack.jetbrains.com/issue/PY-18029)

ssh -N -L 4444:localhost:22 [email protected] -p 22003

1
2
3
4
5
6

27. [做深度学习需要知道哪些linux指令](https://zhuanlan.zhihu.com/p/60612900)

28. xclient.info

29. 验证端口是否可以被访问：

python3 -m http.server

30. [iterm2如何集成tmux：注意有bug，不必加 -CC](https://toutiao.io/posts/q86tnu/preview)

31. [网络monitor](https://www.vpser.net/manage/iftop.html)

32. [ifstat -l :查看本地socket通信](https://www.cnblogs.com/fjping0606/p/4702650.html)

33. ```iostat 2 100000``` 查看io状况

34. 测试跨机带宽	
1
2
server端：iperf -s -p 3028
client端：iperf -c 162.105.146.116 -p 3028


35. [操控网络吞吐](https://netbeez.net/blog/how-to-use-the-linux-traffic-control/)

36. [python时间统计有点坑](http://jeremybai.github.io/blog/2015/06/10/time_vs_clock)

37. 监控linux资源可以使用IBM的nmon，一个全搞定。
38. dstat可以汇总cpu、disk、network、paging、system。mac下使用`ifstat`即可。或者glances命令。
39. [学习正则表达式的网站](https://regexone.com/problem/matching_decimal_numbers)、[正则可视化网站](https://regexr.com/)、![](http://cdn.hbsun.top/FmwXuv3_wYmCLfVEyJaroHzSsC_L)
40. pwdx查看程序启动路径
41. 从vim中切换出来：`ctrl+z`。切换回vim:或者先`jobs -l`，或者直接`fg`。
42. fuser命令可以找出文件被哪个进程使用。《鸟叔》P532。
43. [brew安装](https://zhuanlan.zhihu.com/p/146001246)

1. 按格式查看csv：csvcut user_logs_part.csv | csvlook

2. CSVKIT——处理csv文件的瑞士军刀 - 简书

1. markdown转化成doc:pandoc test.md -o test.docx

1. volatile的可见性是指每当有其他线程对变量发生改动后，我这个线程在读取的时候都是最新值。

1. Grape为什么可以使得我们只需要顺序编写算法就可以了，他在系统方面做了哪些创新，理论保证是什么？之前就没有人提出过局部求解的概念吗？

1. spyder的路径：/Users/mac/.spyder-py3