一种面向图联邦的跨机构全局社区搜索方法

本发明属于联邦计算、图数据挖掘与隐私保护交叉，具体涉及一种面向图联邦的跨机构全局社区搜索方法。

背景技术：

1、在现代数据科学中，图作为刻画实体间复杂依赖关系的基础数据结构，被广泛应用于社交网络分析、金融风控和生物信息挖掘等领域。社区搜索作为图挖掘的核心任务之一，旨在从海量图数据中识别出包含特定查询节点集合且同时满足连通性与高度凝聚性的子图结构。其中，k-core(k核)模型因其具备良好的结构稳定性与理论可解释性，已成为社区搜索中最为经典的技术手段。

2、针对分布式场景下的社区搜索，现有技术已展开了诸多探索，其中以文献[montresor a, de pellegrini f, miorandi d. 分布式k核分解，ieee并行与分布式系统汇刊，2012年]提出的顶点中心迭代方案为代表，其通过计算节点间的多轮局部状态交换来实现全局核心数的迭代收敛，但这类方案天然建立在“底层节点绝对可信且拓扑可见”的前提之上。

3、在现实跨机构协同场景中，受限于数据隐私合规要求，图数据被物理隔离于互不信任的各客户端之中。为解决该安全隐患，文献[araki t, furukawa j. 高吞吐量半诚实安全诚实多数下的三方计算，美国计算机协会，计算机与通信安全会议，2016年]提出引入秘密共享与混淆电路机制，试图在密文域下完成图结构查询；但由于其协议设计诱发了密集的网络通信交互以及沉重的协议转换开销，导致其处理能力仅局限于极小规模的图数据，无法扩展至深度拓扑挖掘任务。

4、综上，在兼顾多方隐私与高计算效率的联邦图环境下，实现精确完备的社区搜索仍面临严峻的技术制约，现有技术至少存在以下缺陷：

5、首先，局部视野导致真实图结构被破坏。单一客户端观测到的局部度数显著低于全局真实度数，若仅凭局部信息进行k-core剪枝，极易误删核心节点，导致真实跨域社区无法被完整识别。

6、其次，频繁交互引发通信灾难。经典k-core分解依赖由外向内的级联剥离，在传统分布式或安全多方计算(mpc)框架下，这种高频的密文或状态交互会引发指数级增长的通信延迟；而联邦学习方案又偏向概率建模，无法满足精确的拓扑约束。

7、最后，边重叠导致统计虚高与精度失效。跨机构间常存在重复的边数据，现有安全聚合协议多仅支持数值求和，导致重叠边被重复累加、节点度数虚高，彻底打破按度数剥离的底层逻辑，造成最终查询结果失效。

技术实现思路

1、鉴于上述问题，为突破图联邦环境下隐私保护与多方协同计算的性能瓶颈，本发明提供了一种面向图联邦的跨机构全局社区搜索方法，通过成对掩码与逻辑二值化技术安全构建去重后的全局压缩图视图，在压缩态下离线完成核心数的级联剥离与层次化索引构建，在线支持基于伪随机标识的轻量级快速检索；在严格保障各参与方本地拓扑隐私及原始节点身份的前提下，实现了精确、完备且极具扩展性的全局联邦社区搜索。

2、一种面向图联邦的跨机构全局社区搜索方法，包括如下步骤：

3、（1）客户端进行隐私对齐，将本地的原始节点标识符映射为统一的伪随机标识，服务器端收集所有客户端的伪随机标识后分配连续的整数索引并构建全局映射表；

4、（2）客户端利用成对掩码技术对本地邻接向量进行加噪，服务器端聚合所有加噪向量，通过逻辑二值化消除重叠边引起的统计偏差后存储，生成节点的全局压缩邻接位图；

5、（3）基于全局压缩邻接位图服务器端利用度数分桶机制在压缩态下执行自底向上的级联剥离，计算出所有节点的全局核心数；

6、（4）基于全局核心数服务器端采用逆序遍历策略动态维护节点连通性，构建具有包含关系的gct(全局核心树)索引及倒排索引；

7、（5）客户端发送加密查询请求，服务器端基于全局映射表通过遍历gct索引和倒排索引，返回脱敏后的目标社区节点集合，客户端解密得到最终的社区。

8、进一步地，所述步骤（1）的具体实现方式如下：

9、s11.各客户端通过diffie-hellman(迪菲-赫尔曼)组密钥交换协议进行多轮交互，共同派生出对服务器端不可见的共享会话密钥；

10、s12.各客户端利用哈希函数及共享会话密钥，对本地节点集中的所有原始标识符进行确定性映射，生成掩码形式的脱敏标识集合并上传至服务器端；

11、s13.服务器端对所有客户端提交的脱敏标识集合执行并集操作以消除重复节点，对其中每个唯一的脱敏标识按字典序分配连续的整数索引，构建全局映射表并分发至所有客户端；

12、s14.各客户端根据所述全局映射表，将本地邻接表中的节点标识转换为对应的连续整数索引。

13、进一步地，所述步骤（2）的具体实现方式如下：

14、s21.对于任一节点，客户端根据其局部邻居集构建局部位向量，并通过diffie-hellman协议与其它客户端协商生成成对的随机种子，进而利用伪随机数生成器生成一致的掩码向量；

15、s22.客户端在上传数据前，利用所述掩码向量对局部位向量进行加噪掩蔽处理，生成掩蔽向量；

16、s23.服务器端收集所有掩蔽向量并进行模加聚合，利用零和性质抵消不同客户端间的掩码噪声，还原出代表边出现次数的全局统计向量；

17、s24.服务器端对全局统计向量执行逻辑二值化处理，生成全局邻接位图，以消除不同客户端重复存储同一条边的统计偏差；

18、s25.服务器端将全局邻接位图划分为多个逻辑数据块，根据块内非零元素的分布稀疏特征自适应选择数组容器、位图容器或游程容器进行压缩编码，生成节点的全局压缩邻接位图。

19、进一步地，所述步骤（3）的具体实现方式如下：

20、s31. 对于任一节点，服务器端通过统计全局压缩邻接位图内有效元素的基数得到初始的精确全局度数，将所有节点索引放入对应的度数桶中，并将当前剥离阈值设为全图最小度数；

21、s32.服务器端检查所有度数小于或等于当前剥离阈值的度数桶，提取待移除节点集合，将集合中节点的全局核心数赋值为当前剥离阈值，并标记为已移除状态；

22、s33.对于已移除的节点，服务器端利用全局压缩邻接位图中的迭代器遍历其所有未被移除的邻居节点索引，并将这些邻居节点的度数减1；

23、s34.若邻居节点更新后的度数降至当前剥离阈值或更低，则将其移入对应的低阶度数桶并加入待移除节点集合，并触发递归式的级联更新与剥离操作；

24、s35.若当前层级不存在可移除节点，则递增当前剥离阈值并重复步骤s32~s34，直至所有节点均被赋予全局核心数。

25、进一步地，所述步骤（4）的具体实现方式如下：

26、s41.服务器端定义gct的树节点为包含唯一标识、核心层级及连通分量节点集的三元组，并通过树边刻画低阶连通分量向高阶连通分量收缩的包含关系；

27、s42.服务器端初始化用于动态维护节点间连通关系的并查集，并将所有节点各自构成一个独立集合，按照全局核心数对所有节点进行降序分桶；

28、s43.按照核心层级从最大核心层级向0递减的逆序遍历策略，对于当前层级中的每个新激活节点，利用全局压缩邻接位图枚举其邻居节点，若邻居节点亦处于活跃状态，则在并查集中执行合并操作；

29、s44.完成当前层级的所有合并操作后，若新生成的最大连通分量由上一层级的一个或多个连通分量合并而成，则建立相应的父子关系，生成gct；

30、s45.服务器端根据节点最终所属的连通分量，将节点挂载到对应的树节点上，并生成用于将节点索引映射至树节点位置的倒排索引。

31、进一步地，所述步骤（5）的具体实现方式如下：

32、s51.客户端接收包含感兴趣的原始节点集合及目标阈值的查询请求，利用共享会话密钥对原始节点集合执行哈希映射，生成脱敏查询集合并发送给服务器端；

33、s52.服务器端接收到脱敏查询集合后，利用全局映射表将其转换为连续整数索引集合；

34、s53.服务器端在倒排索引中进行检索，快速定位查询节点挂载的gct树节点位置，提取该树节点及其所有子树节点中包含的全部节点索引，构成精确的查询结果集并返回给客户端；

35、s54.客户端利用本地保留的原始标识到伪随机标识的映射表，识别出查询结果集中属于自身本地视图的真实节点，完成目标社区结果的解析。

36、一种计算机设备，包括存储器和处理器，所述存储器中存储有计算机程序，所述处理器用于执行该计算机程序以实现上述面向图联邦的跨机构全局社区搜索方法。

37、一种计算机可读存储介质，存储有计算机程序，所述计算机程序被处理器执行时以实现上述面向图联邦的跨机构全局社区搜索方法。

38、基于上述技术方案，本发明具有以下有益技术效果：

39、1.本发明引入基于成对掩码的加噪与逻辑二值化机制，在不泄露任何参与方局部拓扑结构的前提下，完美清除了跨机构数据重叠所带来的边重复计数问题，保证了全局度数计算的绝对准确性，从而实现了精确、完备的全局社区搜索。

40、2.本发明创新性地将全局图转化为压缩位图态，并结合度数分桶机制，在服务器端直接执行自底向上的级联剥离操作；该机制将复杂的k-core迭代剥离与多方交互彻底解耦，免去了传统分布式或安全多方计算中频繁的密文/状态广播，大幅降低了系统的通信开销与同步延迟。

41、3.本发明摒弃了传统的正向实时剥离思路，利用逆序遍历策略离线构建包含父子层级关系的全局核心树及倒排索引，这使得复杂的在线社区搜索过程被降维为轻量级的树状索引匹配，在隐藏客户端查询意图的同时，极大提升了在线响应速度。

42、4.本发明利用group diffie-hellman组密钥交换与哈希映射机制，在客户端间协商出对服务器端完全不可见的共享会话密钥；该机制在生成统一伪随机标识、实现异构图逻辑对齐的同时，从根本上抵御了服务器端的离线频率推断攻击，确保了原始实体身份的高度机密性。