图计算之聚类系数算法

图
algorithm, pregel, 图计算

图计算的框架简单介绍完后, 可以跟着编写某个具体的图算法来具体熟悉一下图计算本身, 除了之前最典型的 PageRank 作为代表, 今天来看看聚类相关的代表算法之一 — 聚类系数 (Clustering Coefficient)

0x00. 前言

大部分的图算法的上文都有两个方面, 一个是这个图算法是什么意思, 另一个是这个算法对应在图论中的数学定义 / 公式, 为了方便理解, 一般侧重前者, 对数学定义 / 抽象给出参考链接感兴趣可以再细究. (图论可从 wiki 里了解一下)

然后 Neo4j 有出一本图算法的介绍的书, 觉得对入门图计算学习还是有很大帮助的, 网上很多资料也是从这摘取拼凑的, 建议直接阅读官方 PDF 版本

image-20210811160031086

另外, 我自己归纳画了个简图, 合并简化了一些不常用的算法, 大家也可以基于 md 源码自行修改调整.

graph LR

a(Graph Algorithm)-->b(Path - 路径类)-->b1(ShortestPath - 最短路径)
b-->b2(MST - 最小生成树)
b-->b3(CycleDetection - 环路检测)

a(Graph Algorithm)-->c(Community - 社群/聚类)-->c1(ConnectedComponents - 连通分量)
c-->c2(LabelPropagation - 标签传播)
c-->c3(Louvain - 社群发现)
c-->c4(SSC/WCC - 强/弱连通分量)
c-->c5(TriangleCount - 三角计数)
c-->c6(ClusteringCoefficient - 聚集系数)

a(Graph Algorithm)-->d(Centrality - 中心性)-->d1(PageRank - )
d-->d2(Betweenness/Closeness Centrality - 中介/紧密中心性)


a(Graph Algorithm)-->e(Classification - 分类)-->e1
a(Graph Algorithm)-->f(GNN/ML - 炼金)-->f1(RandomWalk - 随机游走)
f-->f2(Node2Vector - )

a(Graph Algorithm)-->g(Similarity - 相似性)-->g1(余弦/Jaccard/Pearson 相似性等)

Greate trend…….

A. 基本概念

聚类系数 (又名聚集系数, 集聚系数), 简单说是表示 Graph 中顶点(Vertices) 聚集程度的一个指标

它另外从图算法的分类中, 聚集系数算属于聚类算法, 另外它可认为是 “三角计数” 的加强版, 实际应用中具有类似的含义, 不过要注意的是不同于三角计数的定义很明确, 就是统计一个点附近有多少个与其相连组成的三角形, 聚类系数的计算公式有多种变化, 这里我们选取图计算框架常用的计算方式/ Wiki 中的来谈.

B. 数学定义

图论原始定义中有一些比较拗口学究的名词说法, 给普通人理解算法本身增加了门槛, 这里我在不影响正确性的前提下, 会对原数学定义 / 名词做一个简单转换和说明, 比如把字母换成更好理解记忆的版本, 详细的形式化证明和各种原名称可查阅原始 paper.

1. 局部聚类 (子图)

首先局部聚类的计算方式和全局有区别, 它更为简洁直接, 以某个点 V 出发, 分母是当前点的出边数, 分子是

对于一个节点来说，紧密性中心性是节点到所有其他节点的最小距离的和的倒数 (1/)

C(v) = 2Tv / Dv(Dv - 1), 其中v 代表当前出发的顶点, Tv (Triangle) 代表此点的三角△计数和, Dv (Degree) 代表当前点的出边数. 也就是如果已知当前点 V 的三角计数结果和它的出度, 算它的聚类系数就是 O(1) 的操作了.

基本的公式介绍就说到这足矣, 详细的算法示例见后文算法核心. (思考: 聚类系数为何是两倍三角数 ÷ 近似出边的平方呢? A: 它是由原始公式化简得来的)

2. 全局聚类 (全图)

简单说这是统计某整个 Graph 中的密集/聚集性, 比如最典型的判断一个图是稠密还是稀疏图, 这就是一个参考依据, 根据计算结果得出的系数, 越大代表图中点分布越稠密, 越低代表图中点分布越稀疏/离散, 它有两种计算的方式:

  1. 计算图中每个点的聚类系数, 然后取平均值则视为全图的聚类系数 (又称做平均聚集系数, 少见)

  2. 计算图中的闭环, 和开环/所有三角形的数相除 ==> C = 闭环三角形个数 / 所有三角形个数 (常见)

这里闭环和开环如何来定义区分呢? 简单说闭三角形就是三边齐全, 开三角形就是缺了1条边的情况, 如下图简单所示:

graph LR

subgraph Open Triangle
a1(a)-->b1(b)
a1-->c1(c)-.缺失.->b1
end

subgraph Closed Triangle
a-->b
a-->c--连通-->b
end

另外要注意的是, 从图中我们需要注意有个比较关键的地方, 就是如何计算三角形, 我们实际的图都是基于有向图来创建, 那么有 3 种判定方式:

  1. 三点之间任意有边相连通, 既认为构成一个三角形 (常用)
  2. 三点之间必须有序首尾相连 a—>b—>c—>a 认定为三角形
  3. 三点之间必须双双互联(双向边), 才认定三角形

最后, 聚集系数显然是一个 “局部/全局” 的除法, 当结果为1, 则说明图中每个点之间都是相连的, 结果为 0 说明图中点完全离散, 没有三角/连通性.

0x01. 算法核心

参考 Graph Algorithm 书中 Chapter 6.2 中举的具体例子, 还挺直观易懂的, 给出下面 4 个图, 分别计算它们的三角数和聚集度:

image-20210811180237540

(以上都是无向图) 最左侧的是代表的是最离散的形式, U 顶点的所有出边间没有任何联系么; 最右侧代表是最密集的方式, U 顶点周围的点边完全关联, 来看看聚集系数计算方式:

首先以图1(最左)为例, C = 0个三角形 / 5条出边 = 0, 然后

在实际的属性图中, 基本都是有向图, 那么聚集系数的算法有和区别呢? 最关键还是在于闭环三角形的判断是否有差异, 也就是说当三个点互相有连接时, 有两类判断:

  • 仅允许形成环路, 满足 A<-->B<-—>C<-->A 才能算为一个闭环三角
  • 只要 A, B, C 三点相互有边连接, 即使没有形成环路, 也认为是闭环三角

(麻烦引用此图的同学, 明确在文中或文尾注明原图出处, 至少请勿在图上打上自己的水印….)

0x02. 具体实现

下面来到正式开发的环节, HugeGraph 里的图计算框架沿用经典的 MR / Pregel 里的设计, 新增任何算法, 都有核心的:

  1. 输入: 当前算法需要什么输入 (通常是读取全图的点边信息)
  2. 计算 (core): 当前算法拿到了每个点边之后如何计算
    • Woker 端 (必选): 这里定义每个顶点要做的主要逻辑, 比如计算它的三角形个数
    • Master 端 (可选): 这里之所以可选也很好理解, 如果我们只需要计算全图每一个点的三角形, 那无需汇聚过程, 就不用编写逻辑, 如果我们需要统计全图或者某个 Label 点的三角形个数, 就需要 Worker 统计后汇聚到 Master 进行汇总.
  3. 输出: 计算完成后是否需要汇聚, 是否需要回写图数据库, 具体输出格式/位置等.

1. Worker 计算逻辑

定义一个算法, 实现核心的 Computation 接口, 它有2个最核心的方法需要实现:

  1. compute0(ComputationContext c, Vertex v): 每个顶点都会执行的第 1 次计算步骤, 这个阶段没有消息分发, 方法只执行一次 (所有点都会被标记为 active)
  2. compute(ComputationContext c, Vertex v, Iterator msg): 只计算标记为 active 的顶点, 是编写核心计算过程的地方, 每轮迭代都会重复执行, 通过迭代器的变化进行消息接收 & 传递.

如果某个算法无需迭代, 直接在第一次初始化计算的时候就可以完结, 那自然就不需要 compute 的编写, 然后还有 name 和 category 的方法需要实现, 这个就是传一个名字和分类标识当前算法, 就不单独说了. 另外有几个可选默认函数: (入参都是 WokerContext)

  • init: 算法初始化方法, 类似 MR 中的 init, 可以把一些初始化做的工作放进来
  • beforeSuperStep: 在每个超级步开始前做的操作,
  • afterSuperStep:
  • close: 算法结束方法, 类似 MR 里的 close, 在所有 superstep 结束后执行1次, 可以做一些收尾操作

下面说一下计算接口里的核心参数 –> ComputationContext 提供的主要方法:

  1. 提供 sendMessage/sendMessages 相关方法, 给指定的顶点 / 邻接顶点 / 全部顶点发送(带条件过滤)的消息, 接收端会在下一个超级步中收到请求
  2. 提供方法返回图中的总顶点/边的数目 (这是谁返回的? master 么)
  3. 提供 superstep 方法返回当前的 superstep 轮数(编号), 从 0 开始 (第1轮的编号是0)
  4. 提供 combiner 方法返回算法的消息合并器, 用于合并一个顶点消息, 在有 Reduce 逻辑的算法里更好理解

n. 测试用例

首先在 computer-test 对应的算法包下创建对应的算法测试类, 例如 PageRankTest, 然后编写相关逻辑, 最后在 AlgorithmTestSuite 中添加对应的测试类名, 这样启动测试时就会带入运行.

这里就先放一下核心的实现代码, 在有三角计数的基础上也容易实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
@Override
public void compute0(ComputationContext context, Vertex vertex) {
    IdList selfId = new IdList();
    selfId.add(vertex.id());

    context.sendMessageToAllEdgesIf(vertex, selfId, (ids, targetId) -> {
        return !ids.get(0).equals(targetId);
    });
    vertex.value(new TriangleCountValue());
}

@Override
public void compute(ComputationContext context, Vertex vertex,
                    Iterator<IdList> messages) {
    Long count = this.triangleCount(context, vertex, messages);
    if (count != null) {
        ((TriangleCountValue) vertex.value()).count(count);
        vertex.inactivate();
    }
}

private Long triangleCount(ComputationContext context, Vertex vertex,
                           Iterator<IdList> messages) {
    IdList neighbors = ((TriangleCountValue) vertex.value()).idList();

    if (context.superstep() == 1) {
        // Collect outgoing neighbors
        Set<Id> outNeighbors = getOutNeighbors(vertex);
        neighbors.addAll(outNeighbors);

        // Collect incoming neighbors
        while (messages.hasNext()) {
            IdList idList = messages.next();
            assert idList.size() == 1;
            Id inId = idList.get(0);
            if (!outNeighbors.contains(inId)) {
                neighbors.add(inId);
            }
        }
        // Save degree to vertex value here (optional)

        // Send all neighbors to neighbors
        for (Id targetId : neighbors.values()) {
            context.sendMessage(targetId, neighbors);
        }
    } else if (context.superstep() == 2) {
        long count = 0L;

        Set<Id> allNeighbors = new HashSet<>(neighbors.values());
        while (messages.hasNext()) {
            IdList twoDegreeNeighbors = messages.next();
            for (Id twoDegreeNeighbor : twoDegreeNeighbors.values()) {
                if (allNeighbors.contains(twoDegreeNeighbor)) {
                    count++;
                }
            }
        }
        return count >> 1;
    }
    return null;
}

上面就是计算的主逻辑, 为了简单实现, 可以直接在输出时使用原本的结果做一个 O(1) 的计算即可:

1
2
3
4
5
6
7
8
9
@Override
public HugeVertex constructHugeVertex(Vertex vertex) {
    HugeVertex hugeVertex = new HugeVertex(null);
    hugeVertex.id(vertex.id().asObject());
    float triangle = ((TriangleCountValue) vertex.value()).count();
    int degree = ((TriangleCountValue) vertex.value()).idList().size();
    hugeVertex.property(this.name(), 2 * triangle / degree / (degree - 1));
    return hugeVertex;
}

0x03. 运行算法

简单写了个算法 demo 之后, 如何运行它呢? 在已有 GraphServer + Etcd + K8s 的基本环境之后, 先尝试来运行一下单元测试, 它里面有最简单的环境模拟, 下面以长江的 twitter-2010 近14亿数据为例, 其他可自行调整:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
apiVersion: hugegraph.baidu.com/v1
kind: HugeGraphComputerJob
metadata:
  namespace: hugegraph-computer-system
  name: &jobName lcc-hdfs
spec:
  jobId: *jobName
  algorithmName: lcc-twitter
  image: imbajin/xxx-algorithm:1.0.0 # test image (or use official version)
  pullPolicy: Always
  workerInstances: 30 # worker 数
  workerCpu: "5"
  workerMemory: "12Gi"
  configMapPaths:
    hdfs-conf: /opt/hdfs_conf
    #stanford-loader-config: /opt/dataset # 斯坦福数据集, 需先挂载
    twitter-loader-config: /opt/dataset # 推特数据集存于hdfs, 需先挂载
  computerConf:
    job.partitions_count: "120" # 分区数, 结合节点和负载情况分配
    job.partitions_thread_nums: "4" # 并行度
    algorithm.params_class: com.baidu.hugegraph.computer.algorithm.community.cc.ClusteringCoefficientParams
    input.source_type: "hugegraph-loader"
    input.loader_struct_path: "/opt/dataset/struct.json"
    input.loader_schema_path: "/opt/dataset/schema.json"

其他文档在 wiki, 日后转移

0x04. 应用场景

聚类系数在学术上的应用定义可以参考 Wiki 的 Small-World-Network, 基于经典的社交 6度分隔网络为起点, 延伸来做复杂分析, 引入了过多其他的图论概念, 这里不详细描述, 感兴趣可自行了解.

聚类系数在实际生产环境应用和三角计数比较相似(通常是结合选一个), 全图聚类系数可以用于判断图的稀疏, 稠密, 用得不多, 更多的是用于局部范围来分析某个点/子图的紧密度 / 关联性, 下面用一个简单和一个具体的例子来一起了解聚类系数的用法

1. 社交关系 (简单)

首先以 QQ/Wechat/Weibo 这类大家耳熟能详的社交关系为例, 至少有两个使用场景:

  • 推荐好友/文章 / 动态等

  • 找出“僵尸”号, 黑灰产号加以定时清理

    先算出 QQ 全图的聚类系数, 比如是 0.2

    数据清洗, 按照各类用户标签(活跃度, 在线时间, 输入字数, 性别, 年龄段) 构建几个典型的子图, 算出聚类系数, 例 0.5

    遍历疑似黑号的清单, 算出聚类系数, 与全图 & 分类子图做对比, 同时满足大量好友 + CC远低于平均值, 认定“僵尸”号

如何实现呢, 简单的说, 通过三角计数可以获取某个人(账户)常联系的好友圈,

2. 电信实时反欺诈中的应用 (具体)

比如典型的例子就是以前 TigerGraph 在 slides 中曾举例用于 在“AI标记电信号码中的诈骗号码” 中的 case:

本质就是区分普通电话, 和诈骗电话的行为习惯, 然后加以打分标记, 超过阈值则标记为可疑/诈骗

  1. 首先, 普通电话和诈骗电话有个最明显的区别,

    • 普通电话呼入多, 呼出很少
    • 诈骗电话呼出很多, 呼入很少

  2. 上述的判断方式简单但是比较粗, 会误伤到比如客服人员, 外卖/快递小哥, 这类服务人员, 它也是 AI 训练里常说的噪点数据, 那么利用图算法之后如何大幅减少这类小比例的特例呢? 我们就需进一步分析两类电话的呼出子图特征:

    • 正常电话: 它通常有一个比较固定的电话拨出圈, 比如 小明 —> 父母 + 小明 —> 妹妹 + 妹妹—>父母, 从而会在局部构成数个(三角/多角)的环型子图. 用聚集系数 / 三角计数来计算, 它应该具有一定的稠密度 / 三角数

    • 诈骗电话: 因为诈骗电话一般为了隐匿都不会真实使用, 它的拨出会非常离散, 很难在多个拨出之间形成稳定密集环状, 那么它的聚集系数/三角数一般就会很低.

那么上面的案例, 就是典型的简单易理解, 相比直接从原始通话数据进行训练存在噪音和误伤的情况, 运用了聚类图算法之后, 从图上进行预处理过滤后, 达到更好的训练效果的代表.

0x05. 性能实测

大数据量下性能测试

数据在 wiki, 日后转移

0x06. 后续优化

复用三角计数核心, 只需要在输出时计算即可, 后续可以先算三角计数后, 直接计算聚集系数 (短期内无需重新加载数据)

参考资料:

  1. Graph Theory - Wikipedia
  2. Cluster Coefficient - Wikipedie
  3. Graph Algorithm - Chapter6.2 Triangle Count and Clustering Coefficient - Neo4j/ORelly
  4. 图算法整体概览 - ZhiHu
  5. Neo4j-CC-Test
  6. Graph Algorithm CC - TigerGraph Doc v3.2
  7. Algorithm Tutorial for TigerGraph - Beader book
  8. AI in Graph Computing - TigerGraph Slide (link miss:)