Combining preprocessing methods and adversarial learning for fair link prediction

doi:10.11772/j.issn.1001-9081.2024081117

Abstract

Abstract:

Link prediction is a crucial task in network analysis that explores interactions between entities and forecasts new potential relationships in evolving networks. However， link prediction may generate biases， especially concerning links between entities with sensitive attributes. For example， the issue of “filter bubble”， which amplify the isolation of publicly accessible information and reduce diversity for online users. To address these challenges， ALFLP （Adding Link and Adversarial Learning for Fair Link Prediction） method was proposed after combining preprocessing stage methods and processing stage methods for addressing “filtering bubble” issue from the perspective of algorithmic fairness. In preprocessing stage， by adding links to disadvantaged link groups， the difference in link density between different groups was reduced. In processing stage， the output of the preprocessing stage was input into the adversarial learning-based method， and the generator and discriminator were played together to promote more inter-group links， thereby alleviating the “filter bubble” situation. Experimental results on real datasets pokec_n and pokec_z show that compared with baseline methods such as Jaccard， ALFLP method has the AUC index improved by about 12 and 10 percentage points respectively， and the modred index improved by about 0.14 and 0.10 respectively. It can be seen that ALFLP method can achieve a good balance between fairness and prediction accuracy.

Key words: link prediction, fairness, filter bubble, preprocessing, adversarial learning

摘要：

链接预测是网络分析的一项重要任务，它研究个体之间的相互作用，并推断在未来不断发展的网络中可能出现的新关系；然而，在链接预测过程中可能存在偏见，特别是当涉及包含某些敏感属性的个体之间的链接时，如引发“过滤气泡”的效应，这一效应表现为在线用户公开信息的隔离程度加剧、多样性降低。针对上述问题，从算法公平性的角度缓解“过滤气泡”问题，将预处理阶段的方法和处理阶段的方法相结合，进而提出ALFLP （Adding Link and Adversarial Learning for Fair Link Prediction）方法。在预处理阶段，通过向劣势链接群组添加链接，减小不同群组的链接密度差异；在处理阶段，将预处理阶段的输出输入至基于对抗学习的方法，并通过生成器与鉴别器相互博弈，促进更多组间链接，缓解“过滤气泡”问题。在真实数据集pokec_n和pokec_z上的实验结果表明，与基线方法（如Jaccard）相比，ALFLP方法的AUC指标分别提高了约12和10个百分点，而modred指标分别提高了约0.14和0.10。可见，ALFLP方法能在公平性和预测准确性之间实现较好的权衡。

关键词: 链接预测, 公平性, 过滤气泡, 预处理, 对抗学习

CLC Number:

TP391.1

Yifeng PENG, Yan ZHU. Combining preprocessing methods and adversarial learning for fair link prediction[J]. Journal of Computer Applications, 2025, 45(8): 2566-2571.

彭一峰, 朱焱. 结合预处理方法和对抗学习的公平链接预测[J]. 《计算机应用》唯一官方网站, 2025, 45(8): 2566-2571.

Figures/Tables 9

Fig. 1 Structure of ALFLP

Tab. 1 Node quantities of different age stages

pokec_n数据集		pokec_z数据集
年龄	节点数	年龄	节点数
<18	19 708	<18	19 558
18~35	40 439	18~35	41 194
>35	6 422	>35	7 044

Tab. 2 Basic Information of datasets

pokec_n数据集		pokec_z数据集
统计指标	数量	统计指标	数量
节点数	66 082	节点数	67 435
链接数	516 784	链接数	617 765
年龄段-1节点数	19 479	年龄段-1节点数	19 392
年龄段-2节点数	40 260	年龄段-2节点数	41 056
年龄段-3节点数	6 343	年龄段-3节点数	6 987
组内链接数	406 384	组内链接数	491 241
组间链接数	110 400	组间链接数	126 524
添加组间链接数	49 024	添加组间链接数	61 588

Tab. 3 Experimental result comparison of different link weight calculation methods

链接权重方法	AUC↑	modred↑
CN	0.912 4	-0.033 5
AA	0.912 4	-0.027 8
CAR	0.916 3	-0.018 6
CAA	0.914 4	-0.021 8
LNB_CN	0.912 4	-0.029 8
LNB_AA	0.915 7	-0.031 1
LNB_CAR（本文方法）	0.914 2	-0.018 0

Tab. 4 Experimental result comparision of different methods（pokec_n dataset）

类别	方法	AUC↑	modred↑	time/s
链接预测方法	Jaccard	0.800 3	-0.056 3	—
	Adamic-Adar	0.800 7	-0.056 3	—
	Node2Vec	0.921 3	-0.049 5	388.9
公平感知的链接预测	Fairwalk	0.919 0	0.002 7	508.5
	FLiP	0.913 7	0.083 0	549.8
	ALFLP（本文方法）	0.9240	0.090 4	547.5

Tab. 5 Experimental result comparision of different methods（pokec_z dataset）

类别	方法	AUC↑	modred↑	time/s
方法链接预测	Jaccard	0.821 4	0.006 0	—
	Adamic-Adar	0.821 7	-0.048 4	—
	Node2Vec	0.932 5	-0.044 2	390.5
公平感知的链接预测	Fairwalk	0.925 3	0.004 6	516.6
	FLiP	0.919 9	0.074 4	550.7
	ALFLP（本文方法）	0.921 0	0.110 9	547.8

Fig. 2 Influence of β on AUC and modred （α=0.1）

Fig. 3 Influence of α on AUC and modred （β=0.2）

Tab. 6 Time and space complexity of different methods

方法	时间复杂度	空间复杂度
Jaccard	$O (N)$	$O (N)$
Adamic-Adar	$O (N)$	$O (N)$
Node2Vec	$O (E × N × (D × H + H 2) + M × D + T × M × L)$	$O (N × (D + H) + M × L)$
Fairwalk	$O (E × N × (D × H + H 2) + M × D + T × M × L × d)$	$O (N × (D + H) + M × L)$
FLiP	$O (E × N × D 2 + M × D + T × M × L)$	$O (N × D + M × L)$
ALFLP（本文方法）	$O (E × (N × (D × H + H 2) + M × D) + T × M × L)$	$O (N × (D + H) + M × L)$

Tab. 6 Time and space complexity of different methods

方法	时间复杂度	空间复杂度
Jaccard	$O (N)$	$O (N)$
Adamic-Adar	$O (N)$	$O (N)$
Node2Vec	$O (E × N × (D × H + H 2) + M × D + T × M × L)$	$O (N × (D + H) + M × L)$
Fairwalk	$O (E × N × (D × H + H 2) + M × D + T × M × L × d)$	$O (N × (D + H) + M × L)$
FLiP	$O (E × N × D 2 + M × D + T × M × L)$	$O (N × D + M × L)$
ALFLP（本文方法）	$O (E × (N × (D × H + H 2) + M × D) + T × M × L)$	$O (N × (D + H) + M × L)$

References 15

[1]	MASROUR F， TAN P N， ESFAHANIAN A H， et al. Attributed network representation learning approaches for link prediction［C］// Proceedings of the 2018 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. Piscataway： IEEE， 2018： 560-563.
[2]	PARISER E. The filter bubble： what the Internet is hiding from you［M］. New York： Penguin Press， 2011.
[3]	薛堯云. 算法推荐机制下的短视频“过滤气泡”问题研究：以抖音为例［J］. 新媒体研究， 2019， 5（14）：21-22.
	XUE Y Y. Research on the “filter bubble” problem in algorithm recommendation mechanism under short video： taking Douyin as an example［J］. New Media Research， 2019， 5（14）：21-22.
[4]	HOFSTRA B， CORTEN R， VAN TUBERGEN F， et al. Sources of segregation in social networks： a novel approach using Facebook［J］. American Sociological Review， 2017， 82（3）： 625-656.
[5]	虞鑫，王金鹏. 从技术到受众：信息茧房效应的研究取向与发展进路［J］.青年记者， 2024（4）：78-83.
	YU X， WANG J P. From technology to audience： research orientations and development pathways of the information cocoon effect［J］. Youth Journalist， 2024（4）：78-83.
[6]	HARDT M， PRICE E， SREBRO N. Equality of opportunity in supervised learning［C］// Proceedings of the 30th International Conference on Neural Information Processing Systems. Red Hook： Curran Associates Inc.， 2016： 3323-3331.
[7]	DWORK C， HARDT M， PITASSI T， et al. Fairness through awareness［C］// Proceedings of the 3rd Innovations in Theoretical Computer Science Conference. New York： ACM， 2012： 214-226.
[8]	SAXENA A， FLETCHER G， PECHENIZKIY M. HM-EIICT： fairness-aware link prediction in complex networks using community information［J］. Journal of Combinatorial Optimization， 2022， 44（4）： 2853-2870.
[9]	RAHMAN T， SURMA B， BACKES M， et al. Fairwalk： towards fair graph embedding［C］// Proceedings of the 28th International Joint Conference on Artificial Intelligence. California： ijcai.org， 2019： 3289-3295.
[10]	GROVER A， LESKOVEC J. node2vec： scalable feature learning for networks［C］// Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2016： 855-864.
[11]	KHAJEHNEJAD A， KHAJEHNEJAD M， BABAEI M， et al. CrossWalk： fairness-enhanced node representation learning［C］// Proceedings of the 36th AAAI Conference on Artificial Intelligence. Palo Alto： AAAI Press， 2022： 11963-11970.
[12]	MASROUR F， WILSON T， YAN H， et al. Bursting the filter bubble： fairness-aware network link prediction［C］// Proceedings of the 34th AAAI Conference on Artificial Intelligence. Palo Alto： AAAI Press， 2020： 841-848.
[13]	LI Y， WANG X， NING Y， et al. FairLP： towards fair link prediction on social network graphs［C］// Proceedings of the 16th International AAAI Conference on Web and Social Media. Palo Alto： AAAI Press， 2022： 628-639.
[14]	LIU Z， ZHANG Q M， LÜ L， et al. Link prediction in complex networks： a local naïve Bayes model［J］. Europhysics Letters， 2011， 96（4）： No.48007.
[15]	TAKAC L， ZABOVSKY M. Data analysis in public social networks［EB/OL］. ［2024-06-22］..