2022Tencent Rhino-bird Open-source Training Program—Angel-Zihan Li-Week2

[1123469]

---

Angel项目第二周进展

当前进展:

• 完成对论文整体的通读以及对结构相似度计算以及构建多层次带权网络部分的精读
• 在个人理解的基础上，基于java语言，对Structure Similarity进行了基本的代码实现
• 对应代码仓库地址：https://github.com/1123469/struc2vec.git
• 对本周代码进行完善，为下一周随机游走构建context graph做准备，同时继续推进对angel编码相关操作的学习

Structure Similarity算法实现基本思路:

• 输入图表示形式采用 adjacency matrix (|V| x | V|)，其中直接相邻顶点间边的权设为1，不直接相邻设为 INF (Integer.MAX_VALUE)
• 方便处理，假设输入图为单个连通分量，且不同顶点间无multiple edges
• 使用Floyd算法获得以上输入图的hopCountResult矩阵，显然在此矩阵中，最大值(单个连通分量，max hop count ！= INF)为此图直径，第i行记录了顶点i到到其他所有顶点的 hop counts
• 一次遍历hopCountResult矩阵，获取图直径以及各顶点度数
• 基于层次计算的思想，自底向上计算得到图结构相似度，最后输入结果为三维矩阵 Integer[k][n][n] structSimi，显然structSimi[k][i][j] = fk(Nodei,Nodej)

算法需要进行的优化:

• Item1：无向图的adjacency matrix为对称矩阵，可以进行相应的矩阵压缩
• Item2：DTW算法可根据论文https://go.exlibris.link/35X6ykDp 优化为快速DTW计算
• Item3：其他代码细节的优化 .etc

遇到的问题:

• Q1：如何解决在上述输入图假设不成立情况下(具有多连通分量以及重边)的结构相似度计算问题
• S1：未解决
• Q2：如何将个人实现的基本java代码，结合angel框架进行实现，并避免一些“重复造轮子”的工作
• S2：继续阅读框架相关编码手册，并积极与导师交流