我在考虑为nebula的go语法增加sample能力。

当前火热的GNN中,采样是一个基本需求。我认为nebula可以在增加语义的情况下满足在线GNN的需求。

如下语法:

GO from 1,2,3 over friend with friend.weight * random() as r order by $.r limit 40 | yield average($-.feature)

目前我在考虑这个方向,这样的语义会和steps有冲突。在我的观察中,steps能力很弱,或许可以考虑忽略这个语义?

2 个赞

是指对边采样?

对,需要定制采样方式。GNN常见的有topk/random/random by weight.

1 个赞

我们N度拓展的语法都是基于PIPE的,你可以看下PIPE的用法。N STEPS在你说的场景不适用。你提出的语法我们是这样做的:
GO FROM 1,2,3 OVER friend YIELD friend.weight AS r, friend._dst as id, | SAMPLE N | GO FROM $-.id OVER …

这个示例是一个两度扩展,示例中的SAMPLE N就是你所说的采样。你可以实现TOP K,其实就是ORDER + LIMIT。也可以是等概率采样,或者其他采样方式。

我们当前版本已经在存储层通过配置的形式为大点做了一个采样的截断优化,但是没有在语法层提供这样的支持。
[nGQL]Need sample n & tail n · Issue #1902 · vesoft-inc/nebula · GitHub 这个issue是我们之前考虑的提供采样的语法,但是目前还没有实现。我们非常欢迎您为nebula提交代码。 :grinning:

1 个赞

通过pipe语法存在歧义。当前的实现是把1,2,3的目标点都拿出来,然后总体采样。确实GNN存在这样的采样方式。

更常见的方式则是对每一个点延伸出来的边进行采样。可以参考graphsage。将order by和limit内置在go语法中,则是规避歧义:层级采样/点级采样。

当然还有采样下推的考虑,否则对gnn这种大吞吐量的采样需求,是无法满足的

你说的对。目前支持的是一层输出的总体处理。针对点级的处理,这个需要在语法上进行丰富。还有算子下推,目前1.0只支持filter下推。这些需求我们是考虑在QE2.0中处理,QE2.0正在开发中。

我这里尝试在内部fork的代码中增加相关能力,保持关注和沟通。

首先非常感谢这个想法,非常有价值和支持。

其次,你能分享一些可参考的(比如各种GNN的实现)语法吗,因为语法设计很容易导致描述能力问题(有些场景描述得很别扭)或者是边界问题(边界产生歧义)。

没问题,随时欢迎提问。

我认为目前真正可以工业使用的GNN只有graphsage以及其简单扩展。

这里是其原理

分为训练和更新过程。目前训练过程有ouler/alibaba graph learn等产品可以得到一个模型。我更关心更新(特别是在线更新)过程。

目前都是2跳,即K=2,sample数量一般是50这个水平,每个点存储的feature大概是一个100的float向量。

通过采用可以认为是一个三层的塔形结构,layer2是目标点,layer1有50个点,layer0有2500个点,如果叶子节点不足则忽略,不关心是否重复。

每一个点的feature可以由其孩子节点的feature这样计算:激活函数(concat(agg(children.feature), self.feature)*矩阵)。最终layer2的点得到的feature需要被保留。

因此我期待的语法是:

// batch采样

GO from 1,2,3 over friend with random() * friend.weight as r order by $.r limit 50 yield $-._id as u, $$._id as f | GO from $-.f over click with random() * click.weight as r order by $.r limit 50 yield $-.u , $-.f, $$._id as i;

//layer0的aggregate

fetch vertex 1,2,3 yield agg(User.feature) as H_N

//其余计算在client做
//当然最好还是能够支持所有tensor计算减少网络消耗。tensor的网络消耗是性能瓶颈。

算法如图

dgl的nodeflow抽象如图:
sampling.nodeflow

1 个赞

如下是我最理想情况下的语句。目前我用NumCpp这个库封装了tensor的运算符,用ndarray来描述。语法方面面临如下几个问题,还请赐教:

·参考cypher增加with语义,方便定义sample算子。
·order by和limit下推
·常量定义的语法
·按我的目前观察,这个语义还不支持:$-.i.feature。其中i是表中一个字段,表示vid。

// batch采样子图
$graph = GO from 1,2,3 over friend with random() * friend.weight as r order by r limit 50 yield $-._id as u, $$._id as f | GO from $-.f over click with random() * click.weight as r order by r limit 50 yield $-.u , $-.f, $$._id as i;
// 常量
const var W0 = ndarray(“float”, [[1,2,3],[3,4,5]]);
const var W1 = ndarray(“float”, [[1,2,3],[3,4,5]]);
// layer0->layer1聚合
$graph_agg_0 = $graph | group by $-.u, $-.f yield $-.u, $.f, sigmoid(concat($-.u.feature, agg($-.i.feature)) * W0) as feature;
// layer1->layer2聚合
$graph_agg_1 = $graph_agg_0 | group by $-.u, yield $-.u, sigmoid(concat($-.f.feature, agg($-.feature)) * W1) as feature;
// 更新feature
$graph_agg_1 | update vertex $-.u User.feature values ($-.feature);