本文由“大数据治理的理论与技术”专题特约编辑杜小勇教授、杨晓春教授和童咏昕教授推荐.
近年来, 异质信息网络上的社区搜索问题已经吸引了越来越多的关注, 而且被广泛应用在图数据分析工作中. 但是现有异质信息网络上的社区搜索问题都没有考虑子图上属性的公平性. 将属性的公平性与异质信息网络上的kPcore挖掘问题相结合, 提出了基于属性公平的异质信息网络上的极大core挖掘问题. 针对该问题, 首先提出了一个子图模型FkPcore. 当对FkPcore进行枚举时, 基础算法Basic-FkPcore遍历了所有路径实例, 并枚举了大量kPcore及其子图. 为了提高算法效率, 提出了Adv-FkPcore算法, 以避免在枚举FkPcore时对所有的kPcore及其子图进行判断. 另外, 为了提高点的
In recent years, community search on heterogeneous information networks has attracted more and more attention and has been widely used in graph data analysis. Nevertheless, the existing community search problems on heterogeneous information networks do not consider the fairness of attributes on subgraphs. This work combines attribute fairness with kPcore mining on heterogeneous information networks and proposes a maximum core mining problem on heterogeneous information networks based on attribute fairness. To solve this problem, a subgraph model called FkPcore is proposed. When enumerating FkPcore, the basic algorithm called Basic-FkPcore traverses all path instances and enumerates a large number of kPcores and their subgraphs. In order to improve the efficiency of the algorithm, an Adv-FkPcore algorithm is proposed to avoid judging all kPcores and their subgraphs when enumerating FkPcores. In addition, in order to improve the acquisition efficiency of P_neighbor, a traversal method with vertex sign (TMS) and a FkPcore enumeration algorithm called Opt-FkPcore based on the TMS algorithm are proposed. A large number of experiments on heterogeneous information networks demonstrate the effectiveness and efficiency of the proposed method.
现实生活中, 很多的网络都是由组件及组件间的相互关系构成的, 比如社交网络、生物信息网络、金融关系网络及计算机网络等, 而这些网络都可以被统称为信息网络[
近年来, 更多的研究者选择将这种信息网络构建为异质信息网络(heterogeneous information network, HIN), 并基于异质信息网络开展了诸多研究[
异质信息网络其实就是具有多种对象和关系类型的网络, 当下, 这种模型已经被广泛用于生物信息网络、社交媒体网络和知识网络等的建模. 如
文献数据的异质信息网络
当前, 网络社区搜索[
在本文工作中, 我们主要研究异质信息网络上的基于属性公平的社区搜索问题. 给定一个异质信息网络
(1) 针对异质信息网络社区搜索问题, 提出了一个基于公平性概念的语义模型FkPcore.
(2) 提出了一个基础算法Basic-FkPcore, 来对异质信息网络中的FkPcore进行枚举.
(3) 结合剪枝技术, 设计了改进算法Adv-FkPcore, 来对无用的遍历过程进行提前剪枝.
(4) 针对点的
(5) 在4个真实异质信息网络数据集上进行了一系列实验, 并证明了我们所提方法的有效性和效率.
本文第1节介绍相关工作. 第2节介绍与问题相关的术语及定义. 第3节介绍FkPcore枚举算法. 第4节对实验结果进行分析. 第5节对全文进行总结.
● 社区搜索
社区搜索问题旨在寻找所有包含给定查询点的稠密子图. 而在对这些子图的凝聚性进行定义时, 大多数工作采用的是最小度数这一度量手段, 它要求子图中的每个点的度数都大于等于
● 基于公平的数据挖掘
属性, 特别是敏感属性的公平性不仅是机器学习领域, 也是图数据挖掘领域一个十分重要的概念. 但是, 当前大部分考虑属性公平性的工作都是在机器学习领域的. Zehlike等人[
在这一节, 我们介绍了本文涉及的几个重要定义, 并进一步对基于属性公平的异质信息网络上的社区搜索问题做了定义.
符号表
符号 | 符号说明 |
对象类型映射函数 | |
关系类型映射函数 | |
对象类型集合 | |
关系类型集合 | |
异质信息网络 |
|
元路径 | |
deg( |
点 |
给定的属性值集合 | |
degmax( |
异质信息网络的网络模式对多种点类型与边类型的连接情况进行了概括, 网络模式中的一条边可能代表了一对一、一对多甚至是多对多的关系.
例如,
以
还是以
证明: 假设存在一个包含
算法1是我们提出的基础算法, 在该算法中, 我们对所有包含查询点
输入: 异质信息网络图
输出: FkPcore集
1.
2. deg(
3.
4.
5.
6.
7. remove
8.
9.
10. deg(
11.
12.
13.
14.
15.
16. Procedure
17.
18.
19.
20. remove
21.
22.
23.
24.
25.
算法1的第1、2行是通过遍历全图获取图
算法1的第3−11行是对不满足度数约束的点进行剪枝, 缩小遍历规模, 提高算法效率.
算法1的第12−15行是对
算法1的第16−25行是对剪枝后的点集
算法1中的kPcoreEnum过程挖掘出了所有由与查询点
结合算法内容, 可以得到算法1的时间复杂度为
以
针对算法1计算代价大这一点, 我们发现, 在kPcoreEnum过程中挖掘出来的所有子图, 其中很可能存在某些子图直接满足FkPcore的条件, 而那些被这些子图所包含的其他子图便没有必要再进行FkPcore的判断.我们将几个发现整理成了如下几个定理, 以尽可能提前终止判定过程.
证明: 对于点集
证明: 如果存在某个
证明: 如果
结合上述内容, 我们提出了改进后的FkPcore挖掘算法——Adv-FkPcore. 算法2的具体过程如下所示.
输入: 异质信息网络图
输出: FkPcore集
1.
2. deg(
3.
4.
5.
6.
7. remove
8.
9.
10. deg(
11.
12.
13.
14.
15.
16. 将
17.
18.
19.
20.
21. Procedure
22.
23.
24.
25.
26.
27.
28.
29.
算法2的第3−13行是利用引理1对图
算法2的第14−18行利用引理2和引理3对点集进行判断, 以提前终止对无用点集的判定过程.
算法2的第21−29行是FkPcore枚举过程, 该过程的第28行则是利用引理4对FkPcore的枚举过程进行剪枝, 以减少无用枚举过程, 提高枚举效率.
以
结合算法内容, 可以得到算法2的时间复杂度为
但是算法2在为所有具有目标类型的节点寻找
针对这个问题, 本文提出了结合点标记的遍历方法(traversal method with vertex sign, TMS), 用以获取点的
输入: 异质信息网络图
输出: 与查询点
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
以
TMS示例
结合上述TMS算法, 我们对算法2进行了优化, 进而得到了下面的Opt-FkPcore算法. 在算法4中, 我们利用TMS算法可以减少path实例的重复性遍历, 提高算法执行效率, 减少计算资源的浪费. 算法4的具体过程如下所示.
输入: 异质信息网络图
输出: FkPcore集
1.
2.
3. deg(
4.
5.
6.
7.
8. remove
9.
10.
11. deg(
12.
13.
14.
15. 将
16.
17.
18.
19.
20. Procedure
21.
22.
23.
24.
25.
26.
27.
28.
算法4利用TMS算法提高了具有目标类型的节点的
我们在4个真实数据集上进行实验, 分别包括Foursquare、DBLP、IMDB和DBpedia. Foursquare有5种点类型, 包含了美国的用户签到信息. DBLP有4种点类型, 包含了计算机科学领域的出版信息. IMDB有4种点类型, 包含了自2000年以来的电影评分信息. DBpedia有4种点类型, 包含了从Wikipedia抓取的信息.
实验数据集
数据集 | 点数 | 边数 | 点类型数 | 元路径数 |
Foursquare | 43 199 | 405 476 | 5 | 20 |
DBLP | 682 819 | 1 951 209 | 4 | 14 |
IMDB | 4 467 806 | 7 597 591 | 4 | 6 |
DBpedia | 5 900 558 | 17 961 887 | 413 | 50 |
为了在异质信息网络中结合属性公平性进行社区的搜索, 我们结合本文设计的几种算法实现了3个对比方法, 分别是BasicFkP、AdvFkP、OptFkP. BasicFkP是结合算法1实现的FkPcore搜索方法. AdvFkP是结合算法2实现的改进算法. OptFkP则是结合TMS算法实现的优化方法. 所有的算法都是用C++实现的. 实验的电脑配置为Intel(R) Core(TM) i5-9500 CPU@3.00 GHZ 16 GB内存, 电脑操作系统版本为Windows 10 X64.
在属性公平性方面, 我们选择以性别信息和国家信息作为实验中涉及的敏感信息, 而所有的实验也是基于这两个属性中的某一个进行的基于属性公平性的社区搜索. 在元路径方面, 我们收集了4个数据集的元路径信息, 如
为了对FkPcore模型进行分析, 我们首先针对FkPcore就不同
FkPcore就不同
本节, 我们在数据集DBLP上进行了查询, 并结合结果进行案例分析. 本节一共进行了两次查询, 查询参数分别为: (1)
结果见
案例分析
参数 | 结果 |
Daniel Genkin, Daniel Gruss, Lu Feng, Luisa Verdoliva | |
Daniel Genkin, Daniel Gruss, Mike Hambury, |
为了说明使用本文方法后, 结果在属性分布上的变化, 我们不考虑属性公平, 使用如下查询参数:
案例分析(不考虑属性公平)
参数 | 结果 |
Daniel Genkin, Daniel Gruss, Mickael Schwarz, Mike Hambury, |
结合
属性分布变化
我们在
不同数据集上各方法运行时间测试
对
不同数据集上各方法可扩展性测试
在本文中, 我们研究了异质信息网络上基于属性公平的社区搜索问题. 针对这个问题, 我们首先提出了基础算法Basic-FkPcore, 但是这种算法的表现并不好. 随后, 我们结合本文提出的4个引理, 对基础算法做了改进, 提出了Adv-FkPcore算法. 最后, 又结合TMS算法提出了优化算法Opt-FkPcore. 我们在4个异质信息网络数据集上的大量实验, 证明了我们所提方法的有效性和效率. 社会上由于性别、户籍差别带来的偏见屡见不鲜, 我们相信, 本文的研究工作势必能为克服社区搜索结果的性别或户籍偏见做出贡献.
本文提出的基于属性公平的社区搜索问题对社区中点的属性进行了严格要求, 在未来, 我们拟针对这一约束条件进行调整, 比如给定一个阈值约束来对社区属性的公平性进行判定. 我们相信, 通过这一手段, 可以获得更多有趣的公平社区.
Sun Y, Han J. Mining heterogeneous information networks: A structural analysis approach. ACM SIGKDD Explorations Newsletter, 2013, 14(2): 20−28.
Lichtenwalter RN, Lussier JT, Chawla NV. New perspectives and methods in link prediction. In: Proc. of the 16th ACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining. 2010. 243−252.
Leroy V, Cambazoglu BB, Bonchi F. Cold start link prediction. In: Proc. of the 16th ACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining. 2010. 393−402.
Huang Z, Zheng Y, Cheng R,
Fang Y, Yang Y, Zhang W,
Zhou H, Zhao ZY, Li C. Survey on representation learning methods oriented to heterogeneous information network. Journal of Frontiers of Computer Science and Technology, 2019, 13(7): 1082−1094 (in Chinese with English abstract).
周慧, 赵中英, 李超. 面向异质信息网络的表示学习方法研究综述. 计算机科学与探索, 2019, 13(7): 1082−1094.
Shi C, Wang RJ, Wang X. Survey on heterogeneous information networks analysis and applications. Ruan Jian Xue Bao/Journal of Software, 2022, 33(2): 598−621 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/6357.htm [doi: 10.13328/j. cnki.jos.006357]
石川, 王睿嘉, 王啸. 异质信息网络分析与应用综述. 软件学报, 2022, 33(2): 598−621. http://www.jos.org.cn/1000-9825/6357.htm [doi: 10.13328/j.cnki.jos.006357].
Liu JW, Shi C, Yang C, Philip SY. Heterogeneous information network based recommender systems: A survey. Journal of Cyber Security, 2021, 6(5): 1−16 (in Chinese with English abstract).
刘佳玮, 石川, 杨成, Philip SY. 基于异质信息网络的推荐系统研究综述. 信息安全学报, 2021, 6(5): 1−16.
Sun Y, Han J, Zhao P, Yin Z, Cheng H, Wu T. Rankclus: Integrating clustering with ranking for heterogeneous information network analysis. In: Proc. of the EDBT. 2009. 565−576.
Sun Y, Norick B, Han J,
Sun Y, Yu Y, Han J. Ranking-based clustering of heterogeneous information networks with star network schema. In: Proc. of the KDD. 2009. 797−806.
Zhou Y, Liu L. Social influence based clustering of heterogeneous information networks. In: Proc. of the KDD. 2013. 338−346.
Fortunato S. Community detection in graphs. Physics Reports, 2010, 486(3-5): 75−174.
Newman ME, Girvan M. Finding and evaluating community structure in networks. Physical Review E, 2004, 69(2): 026113.
Chen L, Liu C, Zhou R,
Cui W, Xiao Y, Wang H, Lu Y, Wang W. Online search of overlapping communities. In: Proc. of the SIGMOD. 2013. 277−288.
Cui W, Xiao Y, Wang H, Wang W. Local search of communities in large graphs. In: Proc. of the SIGMOD. 2014. 991−1002.
Fang Y, Huang X, Qin L, Zhang Y, Zhang W, Cheng R, Lin X. A survey of community search over big graphs. The VLDB Journal, 2020, 29(1): 353−392.
Huang X, Cheng H, Qin L, Tian W, Yu JX. Querying
Kong X, Yu PS, Ding Y,
Shi C, Li Y, Philip SY,
Jamali M, Lakshmanan L. HeteroMF: Recommendation in heterogeneous information networks using context dependent factor models. In: Proc. of the 22nd Int'l Conf. on World Wide Web. 2013. 643−654.
Shi C, Zhou C, Kong X,
Yu X, Ren X, Sun Y,
Verma S, Rubin J. Fairness definitions explained. In: Proc. of the Int'l Workshop on Software Fairness. 2018. 1−7.
Dwork C, Hardt M, Pitassi T,
Jacobs AZ, Wallach H. Measurement and fairness. In: Proc. of the ACM Conf. on Fairness, Accountability, and Transparency. 2021. 375−385.
Friedler SA, Scheidegger C, Venkatasubramanian S. On the (IM) possibility of fairness. arXiv: 1609.07236, 2016.
Bonald T, Massoulié L. Impact of fairness on Internet performance. In: Proc. of the ACM SIGMETRICS Int'l Conf. on Measurement and Modeling of Computer Systems. 2001. 82−91.
Kleinberg J, Ludwig J, Mullainathan S,
Huaizhou SHI, Prasad RV, Onur E,
Mehrabi N, Morstatter F, Saxena N,
Caton S, Haas C. Fairness in machine learning: A survey. arXiv: 2010.04053, 2020.
Savulescu J. Justice, fairness, and enhancement. Annals of the New York Academy of Sciences, 2006, 1093(1): 321−338.
Srivastava M, Heidari H, Krause A. Mathematical notions vs. human perception of fairness: A descriptive approach to fairness for machine learning. In: Proc. of the 25th ACM SIGKDD Int'l Conf. on Knowledge Discovery & Data Mining. 2019. 2459−2468.
Menon AK, Williamson RC. The cost of fairness in binary classification. In: Proc. of the Conf. on Fairness, Accountability and Transparency. PMLR, 2018. 107−118.
Corbett-Davies S, Pierson E, Feller A,
Sun Y, Han J, Yan X,
Fang Y, Yang Y, Zhang W,
Batagelj V, Zaversnik M. An o(
Bonchi F, Khan A, Severini L. Distance-generalized core decomposition. In: Proc. of the ICDM. 2019. 1006−1023.
Seidman SB. Network structure and minimum degree. Social Networks, 1983, 5(3): 269−287.
Sozio M, Gionis A. The community-search problem and how to plan a successful cocktail party. In: Proc. of the KDD. 2010. 939−948.
Zhang Z, Huang X, Xu J, Choi B, Shang Z. Keyword-centric community search. In: Proc. of the ICDE. IEEE, 2019. 422−433.
Cohen J. Trusses: Cohesive subgraphs for social network analysis. Technical Report, 16(3.1), National Security Agency, 2008.
Zhang Y, Yu JX. Unboundedness and efficiency of truss maintenance in evolving graphs. In: Proc. of the SIGMOD. 2019. 1024−1041.
Huang X, Cheng H, Qin L, Tian W, Yu JX. Querying
Yuan L, Qin L, Zhang W,
Huang X, Lakshmanan LVS. Attribute-driven community search. Proc. of the VLDB Endowment, 2017, 10(9): 949−960.
Zehlike M, Bonchi F, Castillo C,
Serbos D, Qi SY, Mamoulis N,
Beutel A, Chen JL, Doshi T,
Pan M, Li RH, Zhang Q,