Graphembed

该 crate 的目的是提供对带正权重边和可能附加到节点的离散标签的有向或无向图的嵌入。

• 嵌入方法

  • 对于没有附加到节点/标签的数据的简单图，我们提供了 2 个 (rust) 模块 nodesketch 和 atp。还提供了一个具有基于链接预测验证选项的简单可执行文件。

  • gkernel 模块专门用于附加到节点/边的离散标签的图。我们使用 petgraph crate 进行图描述。该算法基于在 nodesketch 模块中使用的散列策略的扩展。
    在无向的情况下，此模块还计算整个图的全球嵌入向量。 它仍然处于早期版本。

• 为了补充嵌入，我们还提供了图的核分解。请参阅 structure 模块。

方法

此 crate 中使用的嵌入算法基于以下论文：

• nodesketch

NodeSketch：基于递归草图的高效图嵌入 KDD 2019。 https://dl.acm.org/doi/10.1145/3292500.3330951
D. Yang,P. Rosso,Bin-Li, P. Cudre-Mauroux.

它基于基于最近算法 probminhash 的敏感散列的多跳邻域识别。请参阅 arxiv 或 ieee-2022。

该算法根据边的权重和点到点的距离为每个点的邻居分配一个概率分布。然后，通过将此分布散列来构建一个由节点标识符组成的（离散）嵌入向量。
嵌入向量之间的距离是 Jaccard 距离，因此对于对称嵌入，我们得到嵌入空间上的真实距离。

还实现了该论文的扩展，以获取有向图的非对称嵌入。相似性也基于给定节点的（进入或离开）集的散列，但此时差异不再是距离（无对称性和与三角不等式的某些差异）。

使用该算法，3百万个节点和1亿条边的 orkut 图在 8 核笔记本电脑上不到 10 分钟内嵌入。.

• gkernel

  我们使用与nodesketch相同的方案，但我们对节点标签进行哈希处理，因此嵌入向量是节点id或标签的汇总，这些节点通过进入或离开节点的边流动。

• atp

不对称传递性保持图嵌入 2016
M. Ou, P Cui, J. Pei, Z. Zhang 和 W. Zhu.

目标是提供一个不对称图嵌入，并估计嵌入的精度与维度的函数关系。

我们使用Adamic-Adar图的矩阵表示。（必须指出，在图核文献中，一个节点通过其连接的配对数来衡量节点称为资源分配）。不对称嵌入是通过图的Adamic-Adar表示的左右奇异向量获得的。源节点与左奇异向量相关，目标节点与右奇异向量相关。
相似度度量是点积，因此它不是一个范数。
svd通过随机化近似，如Halko-Tropp 2011所述，在annembed crate中实现。

核心分解算法

• 密度友好分解

通过凸规划进行大规模分解 2017
M.Danisch T.H Hubert Chan 和 M.Sozio

将图分解成节点最大密集组的实现和使用结构化方式评估嵌入质量。请参阅模块 validation 和关于 Orkut 图嵌入的注释，其中我们可以使用与图一起提供的社区数据来分析嵌入边长度的行为。
特别是，如图orkut.md 和示例目录中所示，嵌入到社区内部的边长通常小于跨越块边界的嵌入边长，请参阅结果。

一些数据集

无标签

小型数据集在数据子目录中给出（使用7z压缩）以运行测试。
大型数据集可以从SNAP数据集合https://snap.stanford.edu/data下载

一些小型测试图在数据子目录中提供

• 对称图

  • 悲惨世界 http://konect.cc/networks/moreno_lesmis。
    这是维克多·雨果小说《悲惨世界》中人物共现的图。

  • p2p-Gnutella08.txt.gz https://snap.stanford.edu/data/p2p-Gnutella08.html

• 不对称图

  • wiki-vote https://snap.stanford.edu/data/wiki-Vote.html 7115个节点 103689条边

  • Cora : http://konect.cc/networks/subelj_cora 引用网络 23166个节点 91500条边

一些较大的数据测试供用户下载

这些图用于以下结果。

请注意，可能需要将Windows转换为Linux行结束符，请参阅dos2unix实用程序。
可能需要将数据从Tsv格式转换为Csv格式，然后才能由程序读取。

• 对称

  • youtube. 节点：1 134 890 边：2 987 624 https://snap.stanford.edu/data/com-Youtube.html
  • orkut. 节点：3 072 441 边：117 185 083 https://snap.stanford.edu/data/com-Orkut.html

• 不对称

  • twitter as tested in Hope http://konect.cc/networks/munmun_twitter_social 465017个节点 834797条边

一些结果

ATP和nodesketch模块的结果

上述数据集的嵌入和链接预测评估结果见文件resultats.md。对orkut图的嵌入进行更全局的分析，结果见文件orkut.md

一些定性评论

• 对于使用随机SVD的嵌入，只要相应的特征值继续显著下降，增加嵌入维度是有趣的。

• munmun_twitter_social图表明，将有向图视为无向图在链接预测AUC方面会产生显著不同的结果。

广义SVD

广义SVD的实现作为模块gsvd的副产品。

安装和使用

安装

该crate提供三个特性，由annembed依赖项要求，以指定您想使用哪个版本的lapack。
例如，编译是通过以下命令完成的：cargo build --release --features="openblas-system"来使用与openblas的动态链接。选择一个特性是强制性的，以提供所需的线性代数库。

使用

• 依赖于矩阵计算的Hope嵌入将图的规模限制在大约几十万个节点。它本质上是非对称的。尽管如此，它仍然可以访问表示图的Adamic Adar矩阵的谱，从而得到在$R^{n}$中有效嵌入所需的维度。

• Sketching嵌入对于大型图来说要快得多，但嵌入到一个由节点ID序列组成的空间中，这些序列配备了Jaccard距离。

• embed模块可以一次性接受嵌入和可能的有效性命令（链接预测任务）。
  通用语法是

  embed file_description [validation_command --validation_arguments] sketching mode --embedding_arguments
  例如

    embed --csv ./Data/Graphs/Orkut/com-orkut.ungraph.txt  --symetric "true" validation --nbpass 5 --skip 0.15 sketching --decay 0.2  --dim 200 --nbiter 5
  

  详见embed模块的文档。像往常一样使用cargo doc --no-deps。

• 使用环境变量RUST_LOG可以通过log和env_logger crates在不同级别（调试、信息、错误）提供一些信息。