Cross-links Matter for Link Prediction: Rethinking the Debiased GNN from a Data Perspective
Authors: Zihan Luo
Hong Huang
Jianxun Lian
Xiran Song
Xing Xie
Hai Jin
Venue: NeurIPS 2023 poster (2023)
Keywords: Cross-links
Debias
Graph Neural Networks
Link Prediction

Abstract: Recently, the bias-related issues in GNN-based link prediction have raised widely spread concerns. In this paper, we emphasize the bias on links across different node clusters, which we call cross-links, after considering its significance in both easing information cocoons and preserving graph connectivity. Instead of following the objective-oriented mechanism in prior works with compromised utility, we empirically find that existing GNN models face severe data bias between internal-links (links within the same cluster) and cross-links, and this inspires us to rethink the bias issue on cross-links from a data perspective. Specifically, we design a simple yet effective twin-structure framework, which can be easily applied to most of GNNs to mitigate the bias as well as boost their utility in an end-to-end manner. The basic idea is to generate debiased node embeddings as demonstrations, and fuse them into the embeddings of original GNNs. In particular, we learn debiased node embeddings with the help of augmented supervision signals, and a novel dynamic training strategy is designed to effectively fuse debiased node embeddings with the original node embeddings. Experiments on three datasets with six common GNNs show that our framework can not only alleviate the bias between internal-links and cross-links, but also boost the overall accuracy. Comparisons with other state-of-the-art methods also verify the superiority of our method.

Cross-links Matter for Link Prediction: Rethinking the Debiased GNN from a Data Perspective
Zihan Luo', Hong Huang', Jianxun Lian", Xiran Song', Xing Xie Hai Jin' National Engineering Research Center for Big Data Technology and System, Service Computing Technology and Systems Laboratory, Cluster and Grid Computing Lab,
School of Computer Science and Technology,
Huazhong University of Science and Technology, Wuhan, China Microsofft Research Asia, Beijing, China {zihanluo, honghuang, xiransong, hjj Anjnstuuuttt.. en, {j jaaxuun... 1ian, xingx] @mi wwwsoot..ccoommmmmmmmmmmmmooooot com
Abstract
Recently, the bias-related issues in GNN-based link prediction have raised widely spread concerns. In this paper, we emphasize the bias on links across different node clusters, which we call cross-links, after considering its significance in both easing information cocoons and preserving graph connectivity. Instead of following the objective-orientee orrieted mechanism in prior works with compromised utility, we empirically find that existing GNN models face severe data bias between internal- links (links within the same cluster) and cross-links, and this inspires to rethink the bias issue on cross-links from data perspective. Specifically, we design a simple yet effective twin-structure framework, which can be easily applied to most GNNs to mitigate the bias as well as boost their utility in an end-to-end manner. The basic idea is to generate debiased node embeddings demonstrations and fuse them into the embeddings of original GNNs. In particular, we learn debiased node embeddings with the help of augmented supervision signals, and novel dynamic training strategy designed to effectively fuse debiased node embeddings with the original node embeddings. Experiments GNNs show that our framework can not only alleviate the bias between internal- links and cross-links but also boost the overall accuracy. Comparisons with other state-of-the- methods also verify the superiority of our method.
three datasets with six common
Introduction
Recently, due the strong capability in learning the latent representation of graph structure data, Graph Neural Networks (GNNs)-based link pre- diction methods have received increasing research interests and show excellent performance in bioinformatics [6],
Opimane
Atrewless
mendation systems 33
34
Craeelike
LadFM
Internaldisko
However, these link prediction methods often prioritize performance without considering potential bias the sensitive attributes of nodes, such as genders or regions, thus leading social risks the creation of informa-
and knowledge graph 24
40
Figure 1: A toy graph for illustrating the concept of topological communities. The proportions of two kinds of links also are provided on the right.
Hong Huang is the corresponding author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

tion cocoons. For instance, in social recommendations, models tend to recommend users with friends belonging to the same region, limiting users' opportunities connect with the outside world [46]. Similarly, in political news recommendations, recommenders prefer to deliver content that aligns with users' partisan beliefs, filtering out different perspectives and narrowing users' scopes [3]. To
tackle these issues, researchers have put forward several solutions. For example, FLIP (28] employs adversarial learning to encourage the model to predict outcomes that are independent of sensitive attributes. Similarly, CFC 4 aims to debias the node embeddings with compositional adversarial constraints. FairAdj [20] learns edge weights to generate a fair adjacency matrix, which is used for
subsequent link prediction tasks. UGE [38] explores unbiased node embeddings from unobserved graph, and proposes two kinds of methods based on reweighting and regularization constraints.
Although these methods make great progress in mitigating the bias in link prediction, there are two issues remaining unsolved: 1) All these methods generally modify the objec-
Community ID
tive functions, like adding regularization constraints 4 28
or reweighting (38] for mitigating the bias. However, the
mechanism of simply modifying objective function may in-
17
fluence the optimization trajectory of the model and result in convergence towards a sub-optimal status. The experimental trade-off between debias and utilitty on multiple prior works 2, 28 38] also supports this claim. 2) Existing methods simply focus sensitive attributes of nodes while ignoring the bias based on graph topology. In fact, due to GNNs' heavy dependence the aggregation of neighborhood messages, for the link prediction tasks, GNNs tend to wire new links inside the local community") internal-links, while ignoring the links connecting different communities (denoted as cross-links), and this kind of bias may leave the graph in danger of being trapped in information cocoons or disconnected 21 28) as shown in Figure T Empirical evidence can also be provided in Figure 2 in which we illustrate the top 10 commonest labels' distributions in different communities. It can be seen that each community contains its own specific information pattern (26), making challenging for one single community to encompass all diverse information in network. This observation implics the propensity of graphs form information cocoons with insufficient cross-links as bridge Motivated by these findings, we aim to design GNN model that could boost the link prediction performance on cross-links and mitigate the bias between internal- and cross-links without sacrificing utility.
Top 10 communest label
Figure 2: Distributions for top 10 la- bels in 10 different communities de- tected by Louvain on LastFM
2 (denoted as
By rethinking the problem of bias between internal- and cross-links with a fresh insight from the data perspective, we statistics the proportion of internal-links and cross-links in three real-world datasets in Figure [ and we can find that the number of internal-links far exceeds that of cross- links. This kind of data bias may be further enlarged and perpetuated by stacking GNN aggregation operations and finally leads to a biased link prediction. In light of this, we propose a simple yet effective twin-structure framework, which consists of two independent GNN models to mitigate the bias between interna-linns and cross-links. Specifically, we first divide the whole graph into multiple communities that share similar topological locations and differentiate links into internal-linke and cross-links. After that, in order to alleviate the data bias between internal-links and -ross-links, supervision augmentation based on multiple rules is proposed to increase the supervised signals for cross-links, which could help the GNNs to better capture the patterns of cross-links and further generate debiased node embeddings. Subsequently, to avoid utility degradation, we design an embedding fusion module to merge original node embeddings and debiased node embeddings with a dynamic training strategy. In this way, the embedding fusion module could effectively preserve the performance of internal-ling links while alleviating the bias between internal-ling llink and rinks.links. Our main contributions can be summarized as follows:
We reveal a significant link prediction bias based on the graph topology, i.e. the bias between internal-links and cross cross-links, and design a model-agnostic framework, which can help most of the GNNs address such bias without compromising utility.
Generally. it refers cluster of nodes that enjoy similar topological location, which can be detected by community detection algorithms. In this paper, we deploy the Louvain algorithm 2 method. Further analysis elaborating the role of cross- cross-links is provided in Section A of the Appendix.
as the default detection

---

We propose three core components in our framework, including supervision augmentation, twins- GNN, and embedding fusion module. The combination of supervision augmentation and twins- GNN can generate debiased embeddings from data aspect as demonstrations, while the embedding fusion module can effectively filter out the noise and preserve the utility of GNN.
We evaluate our method on three real-world datasets with six common GNNs as base models and as well as compare them with other state-of-the-an baselines. The experimental results consistently demonstrate that our framework could effectively reduce the bias between internal-linke and cross-links with even improved overall performance.
2 Related Work
Link Prediction As one of the most important applications in graph learning, link prediction
algorithms have received extensive attention in the last two decades [3 12 14 29]. The traditional link prediction methods are mainly based on some heuristic metrics on the graph structure, such as link prediction methods such as DeepWalk [29]. Node2Vec [12] and LINE [36] have also emerged. With the
CN (25), AA M. and Jaccard coefficient. In recent years, shallow embedding-
powerful capability in representation learning on graph structure data, GNNs have achieved great For example, LightGCN discovers the redundancy of non- aon-inner activation and feature transformation and achieves better performance on recommendations [4]. PPRGo [ uses a Personalized Page Rank matrix to efficiently approximate the multi-hop aggregation, which breaks the classical message-passing paradigm of GNNs. Following LightGCN, UltraGCN (27 approximates the infinite-layer aggregation for better recommendations. Besides, instead of learning from the whole graph, another line of research focuses on learning from relatively small subgraphs, such as SEAL [4] and SUREL+ 42). which also achieve remarkable performance in link prediction.
progress in link prediction tasks as well 3 14
37
48
Bias Related Issues in GNNs Recently, bias-related issues have been widely concerned in graph neural networks, termed as "debias" or "fairness". Concentrating on node classification tasks, there is a branch of works on achieving fair results that are uncorrelated with sensitive attributes. including FairGNN (8). Fair [39], EDITS (9]. and EqGNN (32). As for bias in link prediction, based on node2vec [2], Fairwalk (30 proposes a more fair random walk strategy, but fails to avoid the decrease in models' utility after achieving satisfactory fairness. Both FLIP 28 and CFC 4 try to mitigate the dyadic bias by proposing adversarial constraints in the loss function. Li et al. [20] designed model named FairAdj, which could generate a fair adjacency matrix with different edge weights to address the dyadic bias with competitive utility. Similar to FairAdj, UGE (38] derives unbiased embeddings from an unobserved graph that involves no sensitive attribute information. However, all these methods modify the original objective functions and face trade-off between debias and utility.
3 Methodologies
3.1 Problem Formulation
In this work, graph is denoted by g (V, and it consists of N |V] vertices and |8| links. In the real world, nodes on the graph spontaneously form local communities (26). such as social circles in social networks, and various bundles of also-buy items on product graphs. We use C(v) N to denote the community membership of a given node v and define cross-links and internal-links:
Definition 1. Cross-links and Internal-links Given a link (u, v). it belongs to cross-links Eor if its endpoints' memberships satisfy C(u) & C(v); otherwise, it belongs to internal-linke Ein as it satisfies C(u)= C(v). So according to the endpoints' memberships, the links & in graph could be divided into e,, and Ear two sets exclusively, i.e. Ei, E = Ø and & E =.
Centering on the link prediction based on GNNs, each node will be mapped to an D dimensional embedding vector TR. by GNN encoder. The dot product score of a pair of nodes' embeddings implies the GNN model's confidence on whether there will be a potential link between two given vertices. Our goal is mitigate the bias between internal-links and cross-links, i.e.:
Definition Bias between internal-links and cross-links (Bias). Given a trained GNN model, confidence matrix P E IRNNN can be inferred by calculating the dot product of endpoints'
3

---

embeddings, and a higher Puv indicates that model predicts that it very likely exists link between node and node v. Let the notation M represent an evaluation metric in link prediction tasks, and we use the difference between two kinds of links' average performance to define the bias:
Bias = E[M(P)E = Einl - -Ei((P) = -Erll
Task definition. To address such bias, a GNN recommender should balance the performance on internal-links and cross-links links, so that the final model could show equivalent capability mining true internal-links and cross-links. The goal of this paper is to design model-agnostic framework, which can enhance the embedding ability of given GNN model so that the bias metrics are reduced while the accuracy metrics are at least not decreased:
(P)))) < (ias(M((Plz)),, M(P 2 M(PIZ')
(2)
where Z' represents the original node embeddings given by GNN, and represents the node embeddings enhanced by our framework.
3.2 Framework Overview
We propose a twin-structure GNN-enhancement framework, which can reduce the bias between cross- links and internal-links without hurting the overall performance. An overview of our framework is il- lustrated in Figure 3 Its key components include supervision augmentation, Twins GNNs, and bedding fusion module. Details will be provided in the following sections. In traditional graph embed- ding models, existing links on the graph are used as supervision signals. In our framework, we first gen- erate a certain number of pseudo cross-links and form the augmented supervision signals. Then, we use two GNNs with the same architecture to model the two sets of supervision signals (original supervision and augmented supervision) independently, leading to original node embeddings and debiased node embeddings. Lastly, to avoid the impact of noise during supervision augmentation, an embedding fusion module is proposed, which ensures that the final embeddings will retain the merits of both original node embeddings and debiased node embeddings.
0
Final loss
Embedding Fusion
Original
Debins
600-000
Bee e
Auxiliary loss
Auxiliary loss
GNN
GNN
Original Supervision
Angioeered Supersisor
Figure 3: The overview of our framework
3.3 Supervision Augmentation
As revealed in Figure in most datasets, usually the vast majority of links on the graph are internal- links, and this kind of disparity may cause the learned model to be biased to internal-links while neglecting the performance of the cross-links in order to obtain better overall metrics. Therefore, we design an augmentation step to alleviate the supervision signal sparsity issue.
Jaccard based augmentation. Inspired from the concept of edge strength [1 set of K pairs of nodes {(02, 01),... ..., (ūx, 0k}}, ), which satisfy C(ū.) + C(t.). Vi E [1,..., K}, and have the top K highest Jaccard coefficient score I (û, 0), are wired as pseudo cross- cooss-likss. Specifically, the J(ū, 0) can be formulated as:
((()
0) = W(O)UN(()
(3)
and K = k (|EmnI-EErr) where & is a size K, and (.)) represents the neighbor nodes of a given node. J(.-)) measures the proportion of common neighbors between two nodes, and intuitively, a pair of nodes with more common neighbors
to control the supervision augmentation
more likely to form a potential link, which ensures the high confidence of augmented signals.
Random walk based augmentation. However, when network is extremely dense, adopting Jaccard- based augmentation will consume too much computing resource due to the "neighbor explosion" issue. What's more, the Jaccard-baa supervision augmentation may easily only cover nodes around the border of communities, and nodes in the center of community may still fail to benefit from the

---

augmentation. To solve these problems, we propose a new supervision augmentation method based on random walks. Specifically, we take random walks in the original graph, and each pair of nodes (ū, 0) that appear in the same walk path will be recorded. Next, cross-community node pairs, i.e., C(ū)= * C(O), with the top K highest co-occurrence frequency will be screened out as augmented supervision signals. Similarly, K = k (|Ein ( represents the supervision augmentation size.
Note that, we only generate pseudo supervision signals, and the original graph structure, which is used for message passing in GNNs, remains unchanged. We believe that the lack of supervision plays a much more important role in causing the bias between internal-links and cross-links and adding supervision signals is a more straightforward way to alleviate this kind of bias. Let E" denote the newly constructed edge set. The original supervision signals, which are the original links on the graph. are denoted by go, and the final augmented supervision signals are denoted by Ed = 0 U U
3.4 Twins GNNs
Recently, the retrieval-basse learning paradigm, in which the core idea is to provide supporting examples that can be used references for the model, has extracted increasing research interest in the field of natural language processing (35]. Inspired by this, it would be promising way to generate debiased node embeddings as references for our framework to mitigate the bias between internal-links and cross-links. Specifically, we let o and E to guide the training of two twin GNNs, respectively. The two twin GNNs share the same model architecture but have independent sets of parameters. To this end, the twin-structure GNNs could generate two kinds of embeddings named original node embeddings zo and debiased node embeddings ZA, respectively. In order to make sure that the twin-structure GNNs could precisely generate original embeddings and debiased embeddings for further embedding fusion, we follow the literature [4 34 and employ one of the most classic loss functions in recommendation systems BPRLoss to design our two auxiliary loss functions for the twin-structure GNNs, which can be generalized as:
L
1 [g]
Σ (u,D)EE
logorruu Ta,6)
(4)
where & could be 0 or EA depending on the type of generated embeddings, and the auxiliary loss functions, are denoted as _ and LA, respectively. a is an activation function like sigmoid. (u, 8) denotes a negative sample, and Fu,v denotes the prediction score of a given node pair (u, v). Note that, other alternative loss functions with multiple negative samples can be also easily deployed to our method, which is determined by the practitioners according to their practical applications. Intuitively, with the balanced proportion of two types of links in EA after supervision augmentation, the debiased node embeddings Zd could show excellent capability in eliminating the bias between internal-links and cross-links. The debiased node embeddings Z will become a good demonstration for subsequent embedding fusion modules in the further learning of final embeddings.
3.5 Embedding Fusion
Although we set several heuristic rules in Section 3.3 to ensure that the generated signals have high confidence, the supervision augmentation stage will inevitably introduce noise. Thus, Z is trained with impure supervision. If fusing A into z in naive way, such simple averaging, although the performance on the cross-links can be improved, the internal-links' will be considerably degraded.
Thus, we adopt an embedding fusion module F(-) that merges two kinds of embeddings, i.e. original node embeddings zo and debiased node embeddings ZA, to refine meaningful information from the debiased embeddings and fuse them into the original embeddings:
H. = CONCAT(Z) 2
(5)
Z. = F(H, 0F) = W2 (W H, + b1) + b2
(6)
where W1 E Dx2D, b, E RD, We E DXD, by E R are the trainable parameters of F(-), and can be abbreviated as OF for conciseness. a is the activation function and D is the embedding dimension. Note that, both 2 and Z are output embeddings from GNN models supervised by auxiliary loss, and we believe that there is no need to further deploy a complex network during embedding fusion, hence we simply show a 2 2-layer MLP in 6).
5

---

As the core component of our framework, we argue that the final embeddings Z after embedding fusion function F-)) should filter signal noise in E while preserving as much correct augmented information as possible. Therefore, we optimize embedding fusion module F.)) and twin-GNNs by minimizing the following objective function
c = 1001 100
1
Σ (u,blEgo
log - ru,e)
Algorithm Proposed training process
Input: Graph G with link set E Hyper- Hyper-parameters: a, 3, and T,, learning rate 70, 7-1
Output: Twin GNNs' parameters g 0 and embedding fusion module parameters & 1: Randomly initialize twins GNN models with 8 A embedding fusion module with 6F
2: Split G into [C] communities and categorize links into internal- and cross-links.
3: Select augmented supervision signals E by the Jaccard coefficient co-occurrence frequency.
4: while not converged do
5: Compute _ and L by Eq.(4)
6: Update twins GNN models: 1 + 10 +70
VooLo 0 444. Von
7:
Compute learning rate 7/ and step size S. by (8)
8:
for step = S; do
9:
Compute C by Eq.(7)
10:
Update embedding fusion module: 0F + Of +ot VF
Update twins GNN models: 80 80 + o -ooL A 0 + +7p van end for end while
12:
return 0 AA AA, FF
14:
Algorithm 2 Proposed inference process
Input: Graph 9 with link set g Trained Twin GNNs' parameters 80 8A, and embedding fusion
module parameters 8F
Get node embeddings zo through parameters 8
2: Get node embeddings ZA through parameters 6-1
3: Get node embeddings Z through combining 70 and 7 with embedding fusion module OF
4: Evaluation through test node pairs with node embeddings Z
3.6 Implementation Algorithms
For a better understanding of our method, here we summarize the detailed training process and inference process, and the pseudo codes are provided in Algorithm 1 and Algorithm 2, respectively,
Firstly, during the preprocessing stage, C |C] communities are detected through Louvain algorithm [2] and all links are categorized into internal-links or cross-links, respectively (line 2). In addition, newly constructed supervision signals E are also generated during supervision augmentation (line 3). After that, original node embeddings z and debiased node embeddings 4 are generated by minimizing the auxiliary loss functions Section (.44 (lines 5-6) with learning rate 7 and 7 respectively. The two sets of generated embeddings will be forwarded the embedding fusion module F(-) to get the final embeddings = F(Zo, zza), and minimize the final loss function with multiple training steps (lines 8-12.) Essentially, the embedding fusion module F(-) is highly related to the quality of original embeddings zo and debiased embeddings Z thus we introduce dynamic training strategy to avoid excessive training for embedding fusion module when z and Z have not been stable yet. Specifically, the learning rate 7,"" and training step S, for F(.) at epoch is:
Training process:
1
Ff = aas
S, 5 (+e-((-))
(8)
1 (te-
where or B, and are
to control the learning rate, training steps, and the epoch that F()) can believe the quality of input embeddings have been stable, respectively.

---

Inference process: During the inference stage, we use the node embeddings Z for evaluation (line 4), which are the output of the embedding fusion module. Specifically, we first get node embeddings z and Z through the trained twins GNN in advance (lines 1-2), and then perform embedding fusion operation (line 3) to get the final node emheddings Z.
4 Experiment
4.1 Experimental Settings
Datasets. We conduct our experiments on three real-world networks from SNAFfland RecBold public datasets. Specifically, to verify our framework's 's extendibility, we choose two kinds of networks according the types of interaction between nodes, including user-user (Epinions, DBLP), and user-item (LastFM). Epinions is who-trust-whon social network extracted from
Table 1: Dataset Statistics
47
Datasets
Users
Items
Interactions
Density
Type
Epinions
75,879
508,837
0.000088
User user
DBLP
317,080
1,049,866
0,000010
User-user
LasFFM
1,892
17,632
92,834
0.002783
User-item
the online review site Epinions.com. Each node represents a consumer, and each directed link represents a consumer-to-consume collected from the DBLP computer science bibliography, and two author nodes are connected if they used to publish at least one paper together. LastFM dataset contains users' listening information from the Last.fm online music system and each listening event represents a user-artist interaction. The detailed statistics for these three datasets reported in Table and other experimental settings on datasets are described in Section B in the Appendix.
trust connection. DBLP is co-author social network, which is
Base models. Because our proposed method is model-agnostic framework, which is compatible with almost all CGNN-based link prediction models, here we choose six common and effective GNNs as our base models, including GraphSAGE 13) GIN AI, GAT [37]. LightGCN [14), PPRGo 3 and UltraGCN (77. We verify if our framework could mitigate the bias between internal-links and cross-links without hurting the original overall performance.
Reproducibility. All experiments are run on machines with the same configuration: Intel(R) (e)n(R) CPU E5-2680 and Tesla V100 GPU with 32GB memory. How to detect the communities of network not the research focus of this paper, and here we apply the Louvain algorithm (2 to detect the communities in a graph after considering its high speed and effectiveness. Other alternative community detection algorithms and papeemprraeeters will be discussed in the Appendix. The source code and data are available at https: htaps:///gtthinn giggtu........ com/ www/cocl Cttp:/CCCooocss////ccc/oooocolll codes Crosss-rsss--io links -Bas
4.2
Main Results
In this part, show the performance of our method in terms of both link prediction utility and debias effectiveness after applying it to various GNN models.
The main results on three datasets are reported in Table 2 For Epinions and DBLP, we use Jaccard- based augmentation here, and considering the high density of LastFM, we use random walk-baser augmentation. More results with random walk-based augmentation on Epinions and DBLP are listed in Section in the Appendix for reference. The internal-links performance (Internal.), cross-links performance (Cross.), and overall performance (Overall) are calculated on internal-links in the test set, the cross-ling links in the test set, and the whole test set respectively. To verify our method's 's capability of addressing the bias, Bias in Eq. (I) is also computed to evaluate the performance difference between internal- and cross-links. Table shows the results of our approach and base models, and we can have the following observations:
The performance of internal-linke outperforms that of cross-links under all settings, which indicates the link prediction bias between internal-links and cross-links is widespread. Note that, after proposing our framework, we can only ease this kind of bias to some extent, which inspires us the reasons for the poor performance cross-links may not only come from the data perspective, and we leave this problem as a future work.
httpe::/anap.sttanfon wdw/data/////ee/eaa/////aaaaaaaa hata//dat//index... index. hhtml httpe://reebolle.o/Iddeee html
7

---

Table 2: Link prediction performance (Hits 50) of internal-links, tross-links, and the whole link set of our methods and corresponding base models on three real-world datasets. The results are reported in percentage (%). We bold the results when our framework improves the base GNN model.
Epinions
DBLP
LasIFM
Internal:1
Cross.t
Overali"
Blas
Internal.1
Cross1
Overall
Blas]
Internul.1
Cross.t
Overall"
Biox]
SAGE
Orig.
31,68
28.91
30.69
2.77
69.27
14.62
56.41
$4.65
32.84
14,84
26.80
18.00
Debias
36.98
34.45
36,08
1,63
77.18
31.54
66.23
45.64
32.73
15.13
26,80
17.60
GIN
Orig.
33.49
30.97
32.59
2.52
56.66
16.86
47.29
39.80
33.63
16.91
28.00
16.72
40.56
1.26
26.58
12.25
Orig.
39,30
34,90
37,73
4.40
66.25
22.47
55,91
43.78
32.28
12.76
25.70
19.52
Debias
39,58
36.13
38.35
3,45
75.66
37.46
66.66
38.20
34.24
16.32
28.20
17.92
Otig.
42,86
28.75
37,83
14.11
85.71
11.14
75.28
44.58
34.81
17.51
29.00
17.33
PPRGo
Debias
47.44
42.34
45.62
5.10
55.64
N2.32
34.90
35.14
19.88
30,00
15.26
LightGCN
Orig.
46,43
37.31
43.11
9.32
85,95
47,41
76,88
38.54
38.16
16.62
30,90
21.54
Debias
51.49
45.31
49.29
6.18
93.55
65.33
86,90
28.22
38.31
17,51
31.30
20.80
UlraGCN
Orig.
30.62
5.81
21.78
24.81
95.74
63.82
88.22
31.92
32.73
15.73
27.10
17.00
Debias
16.89
After proposing our method, all base models get improved on both internal-links and cross-links in most cases, which results in an improvement in the overall performance. The reasons for this impressive improvement are two-fold. For one thing, supervision augmentation directly helps boost the performance of cross-links. For another. the augmented supervisions play a regularization role in the learning of node embeddings, thus, the overall quality of representations can be improved.
The increase of cross-links is much higher than that of internal-links, and this contributes to the decrease of bias. For instance, when our framework is applied to LightGCN on DBLP, the performance of internal-links improves from 85.95% to 93.55%, and the performance of cross-links improves from 47.41 1% to 65.33%, thus the bias decreases from 38.54% to 28.22%.
4.3 Ablation Study
In this section, we want to explore: 1) the impact of supervision augmentation on our framework; 2) the impact of the embedding fusion module on our frame- work; 3) the impact of two auxiliary loss functions in Eq. (4: 4) the impact of dy- namic training strategy during training embedding fusion module. As an exam- ple, we show the results LightGCN on two datasets in Table 3 All results are based on Jaccard- augmentation.
Table 3: Ablation studies with LightGCN as the base model. The results (Hits@ reported in percent- age (%). The best results are bold, and the runner-up is underlined.
Epinions
DBLP
Interna. ?
Cross.t
Overall
Intemal.
Cross.1
Overall
Original
46.43
37.11
43.11
85.95
47.41
76.88
Ours
51.49
45.31
49.29
93.55
65.33
86.90
Augment
49.43
40.97
46.27
92.76
60.97
85,24
Rusion
46.39
44.87
72.92
71.53
Auxiliary
41.55
46.75
85.31
We first replace the augmented cross- links signals, which are selected through
Dynamic
41.58
93.09
Jaccard coefficient, with random node pairs across different communities, and denote this variant as "-Augment", There are two main observations: 1) After adding random- auggee-d signals, the overall performance still shows a significant improvement compared to the base model, which indicates that the embedding fusion module can effectively filter out useful information from the augmented embeddings and fuse it into the original embeddings; 2) Compared with our framework, the random-augment -auuom-augeented muggmet framework demonstrates unsatisfactory results on reducing the performance disparity between cross-links and internal-links, such as slightly reducing this kind of bias on Epin- ions dataset from 9.32% (46.43% 37.11%) to 8.46% (49.43% 40.97%), and this indicates the importance of our supervision augmentation method on debias.
Secondly, after removing the embedding fusion module (denoted as "-Fusion"), although the cross- links performance of LightGCN gets significant improvement, i.e., from 37.11% 11% to 46.39% on the Epinions dataset and from 47.41 % 66.97% on the DBLP dataset, the internal-links performance and overall performance get severe influence comparing with our framework. Especially on DBLP, the internal-links performance of LightGCN deceased by 13.03% (from 85.95% to 72.92%). while our framework could even slightly improve the performance of internal-links. It indicates that, after proposing the embedding fusion module, our framework could effectively filter out noisy augmented signals to avoid performance deterioration.
8

---

Finally, after discarding the two auxiliary loss functions of twin GNNs in Eq. ("-Auxiliary Loss") or setting fixed learning rate > and training step S in the embedding fusion module (" "--ynamic")) all metrics deteriorate slightly compared to our proposed framework. This matches our expectation, because both the lack of guidance from auxiliary loss and fixed training strategy would inevitably influence the quality of two sets of input embeddings, thus influencing the final embeddings.
4.4 Comparison with Other Competitors
In this section, we aim to compare our methods with several powerful competitors on reducing the bias be- tween internal-links and cross-links. Specifically, we choose five highly related methods as our baselines, including Falk [30], CFC [4].
Table Comparison with several competitors on both utility and debias. The average results (in Hits @ 50) are reported in percentage (%) after repeating each method three times. The best results are bold, and the runner-up is underlined.
Epinions
LasFFM
Uverall
Bias
Overall
Dios
Overall
Baas.
FairWalk
23.75
80.00
FairAdj [20]. FLIP (28), and UGE
CRC
27.35 04
201
+00
54.22 21
40.37 16
24.28 +.0.
12.79 +.0.
FurrAdj
[38. and replace the required sen- sitive attributes in these methods with community memberships detected by Louvain algorithm (2 in advance. To be fair, all models' embedding dimensions are 64, and other details on hyper-paramett listed in Section B in the Appendix for saving space. Note that, due to the algorithm's 's requirement on the multiplication of the adjacency matrix, FairAdj reports "OOM" errors when deployed on Epinions and DBLP. For comparison, we report the results of GraphSAGE [13] trained with our framework (denoted as Bebias-SAGEs The same as Section [.2 we take Jaccard- augmentation
FLIP
05
4.5 40.5
5523+11 13
45.05 1.1
22.75 +.04
18:23 +.5
UGB
27 1.30 0.2
34.66
54.36
25,50
0.7
GraphSSGGE
30.69 0.9
2.77
56.11
$4.65
26,80 1.0.
18.00 1 0.6
Debins-SaGE
36.8 + 0.7
163 0.2
66.23
1.9
45.64
17
26,90 1 0.4
17.00 t 0.3
are
on Epinions and DBLP and take random walk-based augmentation on LastFM.
As is shown in Table 4 our method achieves state-of-the-art results overall performance with top-ranking debias results. Especially on the DBLP dataset, our method's overall performance far exceeds that of all other baselines, while achieving the best results in reducing the bias between internal-links and cross-links. We believe the reasons are two-fold: 1) With the model-agnostic design of our framework, we could easily deploy our method on many powerful GNN models. 2) Instead of adding extra constraints in the loss function or modifying the objective functions, our method aims at addressing the bias between internal-links and cross-links from data perspective, and the supervision augmentation plays a regularization role in boosting the overall performance.
4.5 Empirical Findings on Easing Information Cocoons
With emphasizing the performance on cross-links, one merit of our model is the potential capability to ease information cocoons, which can be empirically verified from the following two aspects.
Debiased Recommendation. In this part, we further explicitly reveal whether our framework can provide debiased recommendations for nodes to ease the information cocoons. In detail, we train several powerful GNN models, including Light- GCN (1, PPRGo BI and UltraGCN [27] Epinions and DBLP. Next, we randomly select 2000 source nodes and observe the average pro- portion of internal-links in their historical data and their recommendation lists given by GNNs. As is shown in Figure the recommendation lists given by GNN models significantly mag- nify the nodes' original preference on internal- links. From the perspective of the users (or nodes receiving recommendations) such biased recommendations will distort users' true pref- erence by ignoring their niche interests (cross- links) while emphasizing the mainstream inter- ests (internal-links), and make users feel con- fined to limited domains. For comparison, we provide the results of our enhanced GNN models as well, and it can be seen that after proposing method (denoted as "Ours"), the distributions of
His.
Rec.
Oars.
0.9
0.7
0.7
Foa
PYRCH
UghitiON
(a) Epinions
(b) DBLP
Figure 4: The internal-links proportion of histori- cal distribution and multiple GNNs' recommenda- tions before and after applying our method. "His.", "Rec.", and "Ours." denote the historical interac- tions, original recommendations, and our debiased recommendations, respectively.

---

Modutty-o
Modurity
Matorry
Basc
Modaity 0.323
Modaiit 0.40
Madanio
Moduray
Xindarie 0.068
Matura 0.7%
Ours
(a) Epinions
(b) DBLP
(c) LastFM
Figure 5: The visualization of subgraphs reconstructed by the embeddings learned through the base model (above) and ours (below). Note that, each column shows the visualization of the same subgraph, and subgraphs generated by our approach show minor topological isolation phenomenons.
recommendations become closer to that of historical data, which indicates that our approach could effectively address GNN models' biased recommendation and thus ease the information cocoons.
Visualization of Breaking Filter Bubbles. To visualize our proposed framework's 's effect on allevi- ating information cocoons, use Gephi to show the graphs reconstructed by node embeddings learned through the base model and our model, respectively. To be specific, we take UltraGCN shown for in the Gephi platform are set to be the same, and the visualization results reflect the natural layout of the reconstructed networks. The visualization results are shown in Figure 5 and node colors represent the community tags. To better understand also provide the modularity value in each subgraph, which measures
27 as the base model here and only subset of nodes from different communities conciseness. Note that, all the
the visualization results, the strength of the division of a network. It can be seen that after proposing our framework, except for some extreme outliers, the connections between most communities are becoming closer, and the isolation between communities is broken down. The reduced modularity values can also support our claims. These results indicate that the embedding generated by our model can effectively facilitate the generation of tross-links in a network, thus alleviating information cocoons.
5 Conclusion
In this paper, we aim to address the bias in GNN-based link prediction, especially the bias based on cross-links (links cross communities) after considering its specific roles in easing information cocoons and connecting different communities. We further break the paradigm of modifying objective functions in prior works while pursuing debiased performance, and turn to address the bias issue cross-links from a data perspective, which could effectively alleviate the bias by even boosting models' prediction utility. Specifically, by borrowing the concept in retrieval- based learning paradigms, debiased node embeddings are generated as demonstrations. An embedding fusion module with dynamic training strategies is also proposed to ensure that the final embeddings could retain the merits of both original embeddings and debiased embeddings. Experiments on three real-world datasets with six base GNNs indicate that our framework could not only reduce the performance disparity between internal-lini and cross-links but also significantly improve the overall performance, and further alleviate the potential information cocoons.
Limitations & Discussions. Firstly, although we have greatly reduced the bias between internal-linke and links, the experimental results indicate that the bias is not clearly eliminated, which implies that data bias may not be the only reason. What's 's more, despite the supervision augmentation having potential regularization effect, and leading improved performance internal-links, currently lack theoretical underpinnings and rigorous analysis for this phenomenon. However, we find some potential connections between work and counterfactual learning. In our settings, supervision samples for GNN learning, This
augmentation will introduce plenty of moobserved/couuttriacce kind of counterfactual learning may help GNN to better capture the intrinsic relationships between pair of nodes, thus giving a more accurate prediction.
hattps://eepi..org
10

---

Acknowledgement
The work is supported by the National Natural Science Foundation of China (No.62172174, No.61932004).
References
[1] L. A. Adamic and Adar, Friends and neighbors on the web. Social networks, 25(3):111-20 2003.
[2] V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and Lefebvre. Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment, 2000(00))P100)) 2008.
[3] A. Bojchevski, J. Kliepera, Perozzi, Kapoor, Blais, Rózemberczki, M. Lukasik, and S. Günnemann. Scaling graph neural networks with approximate pagerank. In Proceedings of the 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, CA. USA, August 23-27, 2020, pages 2464-2473. ACM, 2020.
[4] A. J. Bose and W. L.. Hamilton. Compositional fairness constraints for graph embeddings. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 715-724. PMLR, 2019.
[5] T. Caliński and J. Harabasz. A dendrite method for cluster analysis. Communications in Statistics-theon theory and Methods, 3(1):1-27, 1974.
[6] U. Chitra and C. Musco. Analyzing the impact of filter bubbles on social network polarization. In Proceedings of the 13th ACM International Conference on Web Search and Data Mining, Houston, TX, USA, February 3-7, 2020, pages 115-123. ACM, 2020.
[7] M. Coşkun and M. Koyutürk. Node similarity-based graph convolution for link prediction in biological networks. Bioinformatics, 37(23):4501-4508 2021.
[8] E. Dai and Wang. Say no to the discrimination: Learning fair graph neural networks with limited sensitive attribute information. In Proceedings of the 14th ACM International Conference on Web Search and Data Mining, Virtual Event, Isruel, March 12, 2021, pages 680-688 ACM, 2021.
[9] Y. Dong, N. Liu, B. Jalaian, and J. Li. EDITS: modeling and mitigating data bias for graph neural networks. In Proceedings of the ACM Web Conference 2022, Virtual Event, Lyon, France, April 25 29, 2022, pages 1 ACM, 2022.
[10] Y. Ge, S. Zhao, H. Zhou, C. Pei, F. Sun, W. Ou, and Y. Zhang. Understanding echo chambers in e-commerce recommender systems. In Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR 2020, Virtual Event, China, July 25-30, 2020, pages 2261-2270 ACM, 2020.
[11] M. S. Granovetter. The strength of weak ties. American Journal of Sociology, 7866):1300-1380 1973.
[12] A. Grover and J. Leskovec. node2vec: Scalable feature learning for networks. Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA, August 13-17, 2016, pages 855-864 ACM, 2016.
[13] W. L. Hamilton, Z. Ying, and J. Leskovec. Inductive representation learning on large graphs In Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, NeurIPS 2017, December 4-9, 2017, Long Beach, CA, USA, pages 1024-1034, 2017.
[14] X. He, K. Deng, X. Wang, Y. Li, Y. Zhang, and M. Wang. Lightgen: Simplifying and powering graph convolution network for recommendation. In Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR 2020, Virtual Event, China, July 25-30, 2020, pages 669-648. ACM, 2020.
11

---

[15] W. Hu, M. Fey, M. Zitnik. Y. Dong, H. Ren, B. Liu, M. Catasta, and J. Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, NeurlPS 2020, December 12, 2020, virtual, 2020.
[16] K. Jha S. Saha, and H. Singh. Prediction of protein-protein interaction using graph neural networks. Scientific Reports, 12(1):8360, 2022.
[17] G. Karypis and V. Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput., 20(1):359-399 1998.
[18] W. O. Kermack and A. G. McKendrick. A contribution to the mathematical theory of epidemics. Proceedings of the Royal Society of London. Series A, Containing papers of a mathematical and physical character, 115(772):700-721, 1927.
[19] T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In Proceedings of the 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, OvenRevi 2017.
[20] Li, Wang. Zhao, Hong, and H. Liu. On dyadic faireess: Exploring and mitigating bias in graph connections. In Proceedings of the 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021.
[21] Z. Li, Y. Dong, C. Gao, Y. Zhao, D. Li, J. Hao, K. Zhang, Y. Li, and Z. Wang. Breaking filter bubble: A reinforcement learning framework of controllable recommender system. In Proceedings of the ACM Web Conference 2023, WWW 2023, Austin, 7X, USA, 30 April 2023- 4 May 2023, pages 4041 4-440. ACM, 2023.
[22] G. Linden, Smith, and York. Amazon.com com recommendations: Item-to-item collaborative filtering. IEEE Internet Comput., 7(1):76-80, 2003.
[23] P. Liu, K. Shivaram, A. Culotta, M. A. Shapiro, and M. Bilgic. The interaction between political typology and filter bubbles in news recommendation algorithms. In Proceedings of the Web Conference 2021, Virtual Event Ljubljana, Slovenia, April 19-23, 2021, pages 3791-3801. ACM/ / IW3C2, 2021.
[24] S. Liu, B. C. Grau, I. Horrocks, and E. V. Kostylev. INDIGO: gnn based inductive knowledge graph completion using pair-wise encoding. In Proceedings of the Advances in Neural Infor- mation Processing Systems 34: Annual Conference on Neural Information Processing Systems 1021, NeurlPS 2021, December 6-14, 2021, virtual, pages 2034 2045, 2021.
[25] F. Lorrain and H. C. White. Structural equivalence of individuals in social networks. The Journal of Mathematical Sociology, 1(1):49-80) 1971.
[26] Z. Luo, J. Lian, H. Huang, H. Jin, and X. Xie. Ada-gnn: Adapting local patterns for improving graph neural networks. In Proceedings of the 15th ACM International Conference on Web Search and Data Mining, Virtual Event Tempe, AZ, USA, February 21 25, 2022, pages 638-647. ACM, 2022.
[27] K. Mao, J. Zhu, X. Xiao, B. Lu, Z. Wang, and X. He. Ultragen: Ultra simplification of graph convolutional networks for recommendation. In Proceedings of the 30th ACM International Conference on Information and Knowledge Management, Virtual Event, Queensland, Australia, November 1 2021, pages 1253-1262. ACM, 2021.
[28] F. Masrour, T. Wilson, H. Yan, P. Tan, and A. Esfahanian. Bursting the filter bubble: Fairness- aware network link prediction. In Proceedings of the 34th AAAI Conference on Artificial Intelligence, AAAI 2020, New York, NY, USA, February 7-12, 2020, pages 841-848. AAAI Press, 2020.
[29] B. Perozzi, R. Al-Rfou, and S. Skiena. Deepwalk: online learning of social representations. In Proceedings of the 20th ACM SIGKDD International Conference Knowledge Discovery and Data Mining, KDD '4, New York, NY, USA August 24- 27, 2014, pages 701-710. ACM, 2014.
12

---

[30] T. Rahman, B. Surma, M. Backes, and Y. Zhang. Fairwalk: Towards fair graph embedding. In Proceedings of the 38th International Joint Conference on Artificial Intelligence, IJCAI-19. pages 3289-3295. International Joint Conferences on Artificial Intelligence Organization, 7 2019.
[31] Y. Shen, Y. Wu, Y. Zhang. C. Shan, J. Zhang, K. B. Letaief, and D. Li. How powerful is graph convolution for recommendation? In Proceedings of the 30th ACM International Conference on Information and Knowledge Management, Virtual Event, Queensland, Australia, November 5, 2021, pages 1619-1629. ACM, 2021.
[32] U. Singer and K. Radinsky. Eagan: Equalized node opportunity in graphs. In Proceedings of the 36th AAAI Conference on Artificial Intelligence, AAAI 2022, February 22 MMrch 1, 2022, pages 1533-8341. AAAT Press, 2022.
[33] X. Song. Lian, H. Huang, Luo, W. Zhou, X. Lin, M. Wu, Li, X. Xie, and H. Jin. xgen: An extreme graph convolutional network for large-scale social link prediction. In Proceedings of the ACM Web Conference 2023, WWW 2023, Austin, TX, USA, 30 April 2023 May 2023, pages 349-359. ACM, 2023.
[34] X. Song, J. Lian, H. Huang, M. Wu, H. Jin, and X. Xie. Friend recommendations with self- rescaling graph neural networks. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. Washington, DC. USA, August 14 18, 2022, pages 3909-39 3919. ACM, 2022.
[35] Y. Su, Y. Wang, D. Cai, S. Baker, A. Korhonen, and N. Collier. PROTOTYPE-TO-STYE: dialogue generation with style-aware editing on retrieval memory. JEEE ACM Trans. Audio Speech Lang, Process., 29:2152-2161, 2021.
[36] J. Tang, M. Qu, M. Wang, M. Zhang, J. Yan, and Q. Mei. LINE: lcage-scale information network embedding. In Proceedings of the 24th International Conference on World Wide Web, WWW 2015, Florence, Italy, May 18-22, 2015, pages 1067-1077 ACM, 2015.
[37] P. Velickovic, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio. Graph attention networks. In Proceedings of the 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, OpenReview.net, 2018
[38] N. Wang, L. Lin, J. Li, and H. Wang. Unbiased graph embedding with biased graph observations. In Proceedings of the ACM Web Conference 2022, Virtual Event, Lyon, France, April 25 29, 2022, pages
ACM, 2022.
[39] Y. Wang, Y. Zhao, Y. Dong. H. Chen, J. Li, and T. Derr. Improving faireess in graph neural networks via mitigating sensitive attribute leakage. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, August 14 18, 2022, pages 1938 1948.194...0 ACM, 2022.
[40] H. Wei, H. Huang, T. Zhang, X. Shi, and H. Jin. Enhance temporal knowledge graph completion via time-aware attention graph convolutional network. In Proceedings of European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2022, Grenoble, France, September 19-23, 2022, Part II, pages 122-137. Springer, 2022.
[41] K. Xu, W. Hu, J. Leskovec, and S. Jegelka. How powerful are graph neural networks? In Proceedings of the 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
[42] H. Yin, M. Zhang, J. Wang, and P. Li. Surel+: Moving from walks to sets for scalable subgraph- based graph representation learning. In Proceedings of the 49th International Conference on Very Large Data Bases, VLDB 2023, Vancouver, Canada, August 28 September 1, 2023, page 1139-2948. aug 2023.
[43] Yun, S. Kim, J. Lee, J. Kang, and H. J. Kim. Neo-gnns: Neighborhood overlap-aware graph neural networks for link prediction. In Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 64,, 2021, virtual, pages 13683-13699 2021.
13

---

[44] M. Zhang and Y. Chen. Link prediction based on graph neural networks. In Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 5171-5181, 2018.
[45] M. Zhang, P. Li, Y. Xia, K. Wang, and Jin. Labeling trick: A theory of using graph neural networks for multi-node representation learning. In Proceedings of the Advances in Neural Information Processing Systems 34: Anmual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pages 9061-9073, 2021.
[46] T. Zhao, G. Liu, D. Wang, W. Yu, and M. Jiang. Learning from counterfactual links for link prediction. In Proceedings of the International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Balfimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 26911-26926. PMLR, 2022.
[47] W. X. Zhao, S. Mu, Y. Hou, Z. Lin, Y. Chen, X. Pan, Y. H. Wang. C. Tian, Y. Min, Z. Feng, X. Fan, Chen, P. Wang, W. Ji, Y. Li, Wang, and J. Wen. Recbole: Towards unified, comprehensive and efficient framework for recommendation algorithms. In Proceedings of the 30th ACM International Conference on Information and Knowledge Management, Virtual Event, Queensland, Australia, November 1 5, 2021, pages 4653 66634666. ACM, 2021.
[48] W. Zhou, H. Huang, R. Shi, X. Song. X. Lin, X. Wang, and H. Jin. Temporal heterogeneous information network embedding via semantic evolution. IEEE Transactions on Knowledge and Data Engineering, pages 1-12, 2023.
14

---

A Further Analysis on the Role of Cross-links
A.1 The relationship between cross-links and information cocoons
To fully understand the relationship between cross-links and information cocoons, we conduct the following experiments for analysis.
Experimental settings. Based on the communities detected by Louvain algorithm [2] in advance, get the internal- -inns and cross-links of network, and here take Epinions and DBLP, two real-world social networks as examples. The detailed dataset information is described in Section 4.1. Next, borrow the concept of message propagation from the Friedkin-Johnsen dynamics model [6] and revise its formula to simulate the information propagation with randomly initialized node embeddings:
Z + ENEN, Way WayZ ZJ
z
I +1
where Z denotes the embedding of node i at iteration t, and N₁ represent the neighbors of node i. Wy is manually controllable reweight scaler determined by the type of link (i.j). each iteration, each node will update its embedding with the weighted average embeddings from its neighbors and itself. For simulating the lack of cross-links, we weaken the role cross-links in information propagation by tuning the for cross-links from 1 to O, and setting w for internal-links to 1.
We further use Haiisski-aaabbaz (CH) index [5] [0] to measure the extent of the information cocoons phenomenon in a network, which can be calculated as follows:
CH Store
20 beratton
200
CHc (Z')
N C-1
100
100
Hursipox
Henatker
Haretions
(10)
Humsikos
(Z')
M. OL 0. 85
03
Reweight Scaler
Reweight Scaler
where SSWc and SSBc are functions to measure within-cluster dispersion and between-cluster dispersion, respectively [10). N denotes the num- ber of nodes, and C' denotes the number of com- munities. A higher CH index score indicates that node embeddings are more polarized among com- munities, which further illustrates the extent of the information cocoon problem in the current net- work.
(a) Epinions
(b) DBLP
Figure Cl: The distribution of CH index score wrt. the weight of cross-links during propaga- tion. A higher value indicates more severe infor- mation cocoons. The dashed lines indicate the CH index score under a normal setting.
Experimental results and analysis. In Figure CT we show the CH index scores with node embed- dings at different propagation iteration t, and we can observe that, the information propagation weight w for cross-links decreases, the CH index score increases consistently and far exceeds that in normal settings (w = 1), which indicates that the final node embeddings present more serious polarization problems among communities. Since the information in a single community is relatively limited shown in Figure 2, the information cocoon problem actually becomes more severe with the lack of cross-links.
A.2 The relationship between cross-links and graph conectivity
By borrowing the concept of network diffusion, we try to explore the role of cross-links in graph connectivity in this part. Specifically, we apply a classic model network diffusion: the SI model 18). to simulate the process of information propagation. In this model, each node is randomly initialized with a status called susceptible or infected at the beginning. During the diffusion iteration process, SI assumes that each infected node could infect its susceptible neighbors with probability p. and once a node becomes infected, it stays infected until the end of network diffusion, i.. there are no more new infected nodes in new iteration.
In order to provide a clear and vivid illustration, we take one of the most representative social networks Zachary's 's karate club as an example. All nodes are divided into four non-overlapping
https://en. walkipedia.org/wweee http://awrrrrgiiii///aaaaaaa/a/a http://ee/__aaata_llull
15

---

(a) Original graph
(b) Drop links randomly
(c) Drop cross-links
Figure C2: The visualization of diffusion simulation with SI model. Red nodes denote infected nodes, and green nodes represent susceptible nodes. (a) The original graph of the karate club. Nodes with the same color denote community. (b) Infected graph after dropping some random edges. (c) Infected graphs after dropping some cross-links.
communities by Louvain algorithm 2 in advance, and node #0, which stands for the instructor in this club, initialized as the only infected node at iteration O. We further randomly remove 80% cross-links in the graph before starting the simulation. For getting more convincing conclusion, the network diffusion process on a graph with the same number of random edges removed is also simulated for comparison.
The final visualization results are shown in Figure It can be seen that although we remove some edges randomly from the whole graph, the infected node #0 still propagates its information to almost all nodes in the club (red nodes in the figure) successfully. contrast, after removing the same number of cross-links, there appears to be obvious information isolation phenomenon, and nearly half the nodes remain susceptible. In other words, cross-links plays a role bridging two different communities during network diffusion, and it would be hard for node to send receive messages from other communities without enough cross-links. In this way, the existence of cross-links plays key role in preserving graph connectivity.
B Additional Experimetal Settings
B.1
Base Models and Baselines
Here we introduce additional details for the base models and baselines used in our experiments. (1) Base models
GraphSAGE 13: GraphSAGE is an inductive learning framework for generating node embed- dings, which samples fixed number of neighbors during aggregation to alleviate the "neighborhood explosion" issues.
GIN 41: GIN a graph neural network that theoretically as powerful as Weisfeiler-LLhhman test with injective aggregation, combination, and readout functions.
GAT 37 GAT deploys the attention mechanism during aggregation to capture the neighborhood information with different weights.
PPRGo[3]: By utilizing Personalized Page Rank matrix to approximate the propagation and aggregation steps with multi-layer graph convolution, PPRGo greatly improves the efficiency and effectiveness on large graphs.
LightGCN empirically finds the redundancy of feature transformation and non-linear activation functions, and greatly simplifies the model architecture with even higher performance on the recommendation tasks.
LightGCN 14
UltraGCN 27
Based on LightGCN, UltrAGNN further theoretically simplifies the model archi- tecture with approximating the infenite-layer information propagation and aggregation.
(2) Baselines
16

---

Fair Walk [30]: Instead of random walk in node2vec, FairWalk chooses its next hop by consider- ing the sensitive attributes in the neighborhood, which successfully mitigates the unfairness related to the sensitive attribute.
CFC A: To ensure that the learned embeddings are not correlated with sensitive attributes, such age gender, CFC introduces adversarial framework enforce faimess constraints.
FairAdj [20]: With learning to assign each edge with different weights, FairAdj generates a fair adjaceney matrix and greatly improves the dyadic fairness with comparable utility in link prediction tasks.
FLIP 28 Concentrating on bursting the filter bubbles in social networks from dyadic fairness perspective, FLIP also utilizes an adversarial learning framework to generate non-sensitive node embeddings for further link prediction.
UGE (38]: UGE aims at learning unbiased graph embeddings from an unobserved graph, which involves no sensitive information, and further derives three kinds of variants namely UGE-w, UGE-r, and UGE-c.
B.2 Evaluation Metric
In this work, we apply Hits@50, which is widely adopted in other research 43 45 and OGB leaderboard [15], as our main evaluation metric to measure the link prediction performance of different GNN models. The Hits@50 can be computed by:
Nenat
Hits@50
Σ
T(ranks < 50)
(11)
Neest i=1
where Niest represents the sample size of test set, and represents an indicator function. rank; denotes the similarity ranking of the ith sample.
B.3 Reproducibility
Dataset. For each dataset, we randomly sample and remove 5% of links in the original graph to construct the validation set and test set, and the remaining links are treated as the training set. Each true sample will be ranked among set of 100000 randomly sampled negative links for evaluation Note that, there is no side information, such as node features or link attributes, involved during our experiments, and we assign each node on the graph with learnable embedding vector for training.
Hypee-parameters. As a aagnss-c framework, we deploy six kinds of GNN models as backbones, including GraphSAGE [3]. GIN 41), GAT (37), PPRGo [3) LightGCN [14), and UltraGCN (27]. For all these models, we set the output embedding dimension as 64. The layer the embedding fusion module is set to 1. The learning rates for twin GNNs are both set as 0.001 after grid search. As for the hyper-parameters in (8), a is set to be 0.005, and T is selected from ( (10, 25, 50) depending on the datasets and base models, and B is set to be 20. Augmentation ratio k is searched from (0.75, 1.0, 1.25| for each dataset. Both weight decay and dropout rate are set to
In particular, for GraphS AGE, we adopt mean-pooling during aggregation; for GIN, we apply linear layer to update node features and use max-pooling during aggregation; for GAT, we use attention heads in each layer; for PPRGo, we set a as 0.3, the walk length as 100; for LightGCN, we set the layer number as 2 and use the final layer's output as embeddings; for UltraGCN, we set the number of negative samples 64, À as 0.8,
3.5.
For Fairwalk, we follow the settings in the original paper and the walk number 20, and the window length to 80; for CFC, we set the training steps of the discriminator as 5; for FairAdj, we set T3 15 and À to 10; for FLIP, we take the suggestions in the original implementation. and the settings are a0..1), 1), 3(0.2); for UGE, we deploy the weighting-baat based variant as our baseline given that there no non-sensitive attribute in our settings.
B.4 Details on LastFM Dataset
Due to the heterogeneity of the recommendation datasets, is hard to directly deploy community de- tection algorithms on the original networks and define the corresponding internal-links and cross-links.
Here follow the evaluation protocol in OGB [15]. which is widely used in research.
17

---

To this end, inspired by ItemCF [22 311. we first generate an hemm-tte graph according to the co-occurrence relationship. For example, given pair of items <. 01, 1/2 >. if they both have interactions with user и at least O times, where O is a hyperparameter to control the con- fidence of generated item-item graph, there will form a link between UI and U2. Next, we can de- ploy our framework on the generated iiem-item graph for learning debiased item embeddings I RIVIXD, where |V] represents the num- ber of items and D represents the embedding dimension. After that, item similarity matrix I | is calculated, which is further used for the final recommendation:
Table Cl:
The comparison between our implemen- tations and normal implementations on LastFM. The average results are reported after repeating each method five times.
LastFM (Hits@ @0)
Original
29.82% + 0.25
LightGCN
Ours 29.30% + 0.21
Original
28.50% + 0.28
UlraGCN
Ours
27.32% + 0.19
P=AxI
(12)
where E R denotes the predicted confidence matrix between users and items, and A E | represents the adjacency matrix of the original user-item graph.
In order to prove that our implementation will not affect the performance of the original GNN models, we compare our implementation (denoted as "Ours"), where O is set to be 1, with GNNs trained on the user-item graph normally (denoted as "Original") in Table CI The results indicate that our implementation does not sacrifice the capability of base GNN models severely adapt our framework.
C Further Experiments and Analysis
C.1 Hyper-parameter Analysis
As the core component in our frame- work, supervision augmentation plays key role in mitigating the bias between internal-links and cross-links. To explore its impact in a finer granularity, we vary
Hits@950
80
Hits@500
the augmentation ratio & and see how
Internal. Cries Drwnall
Internal Cross
the performance of our method changes. Specifically, we take LightGCN as the base model and investigate the perfor- mance on internal-links (Internal.), cross- links (Cross.), and the whole link set (Overall) by varying 0.75, 1, 1.25). Without losing generality, here we take Jaccard- based supervision augmentation. As shown in Figure C3 the performance of the two kinds of links increasingly improves as k grows, accompanied by steady decrease in the difference between them. This is expected because we introduce a large amount of augmented cross- links signals mitigate the bias. And when & reaches 1, which means | As E the framework gradually converges to a stable status. Empirically, a setting k = 1 would be a near-optimal option.
Overall
0.00
0.75
1.25
k
(a) Epinions
(b) DBLP
(0, 0.25, 0.5,
Figure C3: The impact of augmentation size
C.2 Alternative Community Detection Algorithm
In this part, we aim to conduct an ablation study on different community detection methods to prove the usefulness of our proposed framework. Since emphasize the bias from topological perspective, we prefer to use the community detection algorithm based on graph structure. Specifically, to illustrate the universality of our framework, algorithm as an ablation study, and the results on three GNNs are shown in Table C2 Specifically, the number of communities is set be 50 in advance for METIS, and all other hyper-parameters
conduct experiments based the METIS [17]
are set to be the same as that in Louvain-based experiments, which can be found in Section B.3. All results are based on Jaccard-baas based augmentation.
18

---

The results indicate that, although we change the community detec- tion algorithm, our framework still successfully mitigates the bias be- tween internal-linde and cross-links, and achieves competitive results com- pared with the Louvain-basee results, which verifies our work's compatibil- ity.
Table C2: Ablation study with METIS community detection algorithm on two real-world datasets (Hits@50)
Eginiuss
DELP
Internal.
Croic
Ovaallt
Rias]
Innered
Crows
Ovemll]
Bros]
$6.97
19:48
30.75
17.49
69.82
19.00
$4.28
50,50
SANGE
39.06
28.08
35,89
10.13
65.22
GAT
18.35
34.77
31.15
3,56
39.96
36.8
38,06
3,88
68.81
VRRaOON
27:27
11.02
20.77
1566
46.04
8.74
C.3 Supervision Augmentation Analysis
In Section 3.3, we design two kinds of data augmentation methods for generating pseudo cross-links supervision signals. Intuitively, if the pseudo supervision signals have high confidence level, they can provide significant benefits to our framework. To this end, we aim to verify our hypothesis and analyze the impact of different supervision augmentation methods on our framework.
We first statistic the average hop dis- tance between the node pairs gener- ated with different supervision aug- mentation methods. As shown Ta- ble C3 since we only choose node pairs with the most common neigh- bors in Jaccard-based augmentation, the hop distance fixed to 2. When we use random walk-based augmen- tation, the average distance increases consistently two datasets, which verifies its effectiveness in covering nodes that not located in the boundary of communities.
Table C3: The average hop distance between node pairs gen- erated by different supervision augmentation methods
Epinions
DBLP
Jaccard based
2.00
2.00
Random walk basod
2.69
3.14
Link prediction performance (Hits @ 50) of internal- links, cross-links, and the whole link set of our methods with random walk based augmentation and corresponding base models on two world datasets. The results are reported in percentage (%). We bold the results when our framework i improves the base GNN model.
Table C4:
Table C4 further presents the per- formance of our framework with random walk-based augmentation, which literally described Sec- tion 3.3. Specifically, for providing fair comparison, all thyper-parametrrs parameters in random walk-base experiments, including augmentation ratio and others set to be the same as that in Jaccard- based experiments. Com- pared to Table 2, it can be shown that the random walk-based framework shows less improvement cross-links, which results in worse debias results. This observation be explained by the hop distance Table C3 which implies that the random walk-based augmentation may have lower confidence due the longer topological distance between node pairs. However, compared with the base GNNs, the random walk-based framework can still consistently reduce the bias between interna-llinks and cross- cross-links with improved overall performance.
Epiniooss
DBLP
Ovenil
Oscrall:
Okip
31.63
25.91
30.60
2.77
69.27
14.62
56.41
54.65
SAGE
GIN
Odi
33.49
30,91
32.59
2.52
56.66
15.80
47.29
39,80
38.35
37.42
68.12
32.07
99.64
GAT
30.30
34.90
37.75
4.40
66.25
22.47
55.94
43.78
40.02
37.98
75.03
64.94
42.95
37.85
41.14
75.28
44.58
48.36
43.49
90.48
49.51
80.47
42.08
LigheON
85995
Fai..
48.15
48.45
45.41
7.65
92.16
57.55
$4.01
34.11
95.74
Feir $2.16
$1.99
$2.10
0.17
96.47
66.25
89.38
30.22
19


Reviews:
[{"review_id": "Mk4eJW9q1a", "reviewer": "Reviewer_6Hpo", "summary": "This paper addresses the issue of bias in GNN link prediction and proposes a twin-structure framework to mitigate the bias and improve performance. The framework includes an embedding fusion module and a debias module, which work together to reduce the bias between cross-links and internal-links without hurting overall performance. Experiments on three datasets with six different GNNs show that the proposed framework can both alleviate the bias and boost the overall GNN performance.\n", "questions": "1. Any efficiency analysis/convergence analysis/time complexity analysis for better understanding the complexity of the proposed framework compared to standard supervised training.\n\n2. For the mentioned limitation of not having a theoretical analysis. Any ideas about how to approach it? Are there any potential connections to any existing GNN analysis framework?\n", "limitations": "Two limitations are mentioned. 1. The bias is not completely eliminated. 2. Lacking theoretical understanding. I think pointing out these limitations is a plus and both limitations can trigger meaningful future work.\n", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The paper addresses an important issue of bias in GNN-based link prediction and proposes a novel framework to mitigate the bias.\n- The experiment results show that the proposed framework almost always provides both debias and performance gain, even on different GNNs.\n- The twin-structure and embedding fusion is simple and clear.\n- Limitations are discussed and code is provided for reproducibility\n", "weaknesses": "- Paper presentation can be improved. For example, Figure 5 is too small, numbers are hard to read and colors are hard to distinguish. Also, if space permits, I feel like moving Algorithm 1 in Appendix to the main body would be better.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for these insightful and enlightening comments. Specifically, we aims to address the concerns of the reviewer with the following responses.\n\n------\n\n### [About the presentation (W1)]\n\nAccording to the official guidelines of NeurIPS 2023, accepted papers are allowed to add one extra page for the camera-ready version. In this way, we would increase the figure size and font size in Figure 5, and relocate Algorithm 1 from the Appendix to the main text if our work is accepted at last.\n\n------\n\n### [About the efficiency of our model (Q1)]\n\nThanks for your comment, and we would like to analyze the efficiency of our model through the following two perspectives:\n\n1. **Time complexity analysis is provided.** Before the time complexity analysis, we would like to give some notations first:\n\n   | Notations          | Descriptions                                            |\n   | ------------------ | ------------------------------------------------------- |\n   | $\\mathcal{E}_{in}$ | The set of internal-links in the graph.                 |\n   | $\\mathcal{E}_{cr}$ | The set of cross-links in the graph.                    |\n   | $k$                | The augmentation ratio.                                 |\n   | $S_t$              | The training step for training embedding fusion module. |\n\n   As a model-agnostic framework, we assume a specific GNN model requires time *T* to finish the training on a single sample. Then, the time complexity of the base models can be denoted as:\n\n     $T _{base}=(|\\mathcal{E} _{in}|+|\\mathcal{E} _{cr}|)*T$\n\n   while the time complexity of our method is: \n\n    $\\begin{align}T _{our} &=(S _t+2)*(|\\mathcal{E} _{in}|+|\\mathcal{E} _{cr}|)*T+k(|\\mathcal{E} _{in}|-|\\mathcal{E} _{cr}|)*T  \\\\\\  &<(S _t+2) * (|\\mathcal{E} _{in}| + |\\mathcal{E} _{cr}|)*T + k(|\\mathcal{E} _{in}|+|\\mathcal{E} _{cr}|)*T \\\\\\ &=(S _t + 2 + k)*T _{base} \\end{align}$\n\n   where $k$ is the augmentation ratio, which is fixed to 1 or 1.25 in advance. It can be seen that, for each epoch, the upper bound of our algorithm's time complexity is highly dependent on $S_t$. **Fortunately, in our experiments, we deploy a dynamic training strategy, which would set $S_t$ to a relatively small value to avoid unnecessary time expenses at the beginning of training.** To be concrete, for each dataset, the value of $S_t$ starts at 1 at the initial epochs and slowly increases to 20 as the training progresses.\n\n2. **Convergence analysis is provided.** We further provide the convergence analysis of our models and two base models on Epinions dataset. The results on GAT and LightGCN are illustrated in Figure R1 in the uploaded PDF. From the observation we can find that, **despite the additional time our model requires to achieve convergence, the results demonstrate that we are able to attain comparable performance to the base models within a similar timeframe.** We believe that the main reason for this observation is our dynamic training strategy, which sets a relatively small $S_t$ at the beginning of training, thus greatly reducing the time expenses.\n\n------\n\n### [About the theoretical analysis (Q2)]\n\nWe believe this is a very inspiring question and we list some existing techniques that may have potential connections with our work. \n\n1. **Counterfactual learning.** There might be some potential connections between our work and counterfactual learning [1]. In our settings, supervision augmentation will introduce plenty of unobserved/counterfactual samples for GNN learning. To be specific, in this paper, we could regard node pairs as contexts $\\mathcal{C}$, structural information like community memberships as the treatment $\\mathcal{T}$, and the presence of links as the outcome $\\mathcal{O}$.\n\n     The conventional GNN-based link predictor typically follows the formulation $\\mathcal{O}=f(\\mathcal{C}, \\mathcal{T})$. By incorporating counterfactual samples, the objective transforms into finding a GNN model that satisfies $\\mathcal{O}=f(\\mathcal{C}, \\hat{\\mathcal{T}})$, where the distribution of treatment has changed. In this manner, optimization guided by these two objectives inherently aids the GNN in more effectively capturing the underlying relationships between node pairs and enhancing its robustness to noise or unessential treatment, thus yielding more accurate predictions.\n\n2. **Multi-modal fusion.** Multi-modal fusion refers to the process of combining information from multiple distinct sources or modalities to enhance the representation of machine learning. In our work, the twin GNNs actually play two distinct roles in mining graph data, and the embedding fusion may increase the whole model's robustness to noise and variations. \n\n[1] Zhao et al. Learning from Counterfactual Links for Link Prediction. ICML 2022: 26911-26926 \n\n------\n\nWe sincerely appreciate the efforts and valuable feedback provided by the reviewer. We genuinely hope that our responses have addressed your concerns and contributed to a better understanding of our research. If you have any further questions or confusion, please do not hesitate to reach out to us. We would be more than willing to assist and provide further clarification."}, {"review_id": "DIXtmIB2Ti", "reviewer": "Reviewer_sQxV", "summary": "The paper introduces a twin-structure framework for mitigating bias in link prediction methods based on Graph Neural Networks. Current link prediction approaches often prioritize performance without considering biases on sensitive attributes of nodes, leading to social risks and information cocoons. The proposed framework divides the graph into communities, distinguishing internal-links from cross-links, and employs supervision augmentation to increase signals for cross-links, generating debiased node embeddings. An embedding fusion module preserves the performance of internal-links while alleviating bias between them and cross-links. Experimental results on real-world datasets demonstrate the framework's effectiveness in reducing bias and improving overall link prediction performance compared to state-of-the-art baselines.", "questions": "* The paper doesn't mention subgraph-based GNN for link prediction. One reason may be those GNNs are not applicable for large graphs and not fast enough for recommendation systems. But I'm just curious does the cross-link matter for those kind of GNNs for link prediction?\n* In equation 4 and 7, there seems to be only one negative edge for each positive edge. Why not use some K as hyperparameter? If more than one negative edge per positive one, how will the equations become?\n* How to use this framework in the inference step? Do you use augmentation, or just use $Z^O$?\n* In Table 3, model without fusion can get best cross-link performance, does that mean cross-links don't matter too much?\n", "limitations": "yes", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "* The framework author propose can achieve good improvement on a lot of GNNs.\n* The logic of this paper is easy to understand.\n* The paper conduct experiments on large datasets.", "weaknesses": "* The paper doesn't mention subgraph-based GNN for link prediction.\n* The algorithm is not so clear about how to inference.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your constructive and meticulous comments! We have carefully examined the mentioned issues and have prepared the following rebuttal to address these concerns.\n\n------\n\n### [About subgraph-based GNNs (W1, Q1)]\n\n1. **The reasons for not using subgraph-based GNNs.** Subgraph-based GNNs are usually time-consuming due to excessive subgraph extraction operations, and this issue might be severe when they face large graphs. In light of this, we mainly choose several efficient and effective GNNs as base models. However, we will make sure that more subgraph-based GNNs will be discussed in the final version.\n2. **The experiments of classical subgraph-based GNN are provided.** To validate if cross-links also matter for subgraph-based GNNs, we opt for a highly classic subgraph-based GNN link prediction model, SEAL [1], for experiments. Specifically, we conduct experiments on the Epinions and DBLP datasets and employed the Louvain algorithm for community detection. The experimental results are presented in Table R3 in the uploaded PDF. It can be seen that, as a classic subgraph-based GNN link prediction model, SEAL also faces significant performance bias between cross-links and internal-links. This observation further verifies the pervasive existence of cross-link bias issues.\n\n[1] Zhang et al. Link Prediction Based on Graph Neural Networks. NeurIPS 2018: 5171-5181.\n\n------\n\n### [About the details of inference (W2, Q3)]\n\nThanks for pointing out this issue. During the Inference stage, we use the node embedding $Z$ for evaluation, which is the output of the embedding fusion module. For better understanding and eliminating potential confusion, **we provide the inference details in Algorithm 1 in the uploaded PDF**.\n\n\n\n------\n\n### [About the loss functions (Q2)]\n\nIn this work, we have followed the literature [2] and [3] and **employed one of the most classic loss functions in recommendation systems - BPRLoss** as our loss function. Generally, in BPRLoss, there is only one negative sample for each positive sample. However, we concur with the reviewer that incorporating multiple negative samples may positively contribute to improving link prediction performance.  Since the loss function is not the primary focus of our research, we could design other alternative loss functions to handle the situation of multiple negative samples, and we provide two kinds of formulations below: \n\n- $\\mathcal{L}=-\\sum_{\\langle u, v\\rangle \\in \\mathcal{E}^O}\\enspace\\sum_{\\langle u, \\hat{v}\\rangle \\notin \\mathcal{E}^O}\\enspace\\log(\\sigma(r_{u,v}-r_{u, \\hat{v}}))$ , where $\\sigma$ is an activation function like sigmoid.\n\n- $\\mathcal{L} = - \\sum_{\\langle u,v\\rangle \\in \\mathcal{E}^O} \\enspace \\log \\frac{\\exp(r_{u,v} / \\tau)}{\\sum_{\\langle u, \\hat{v}\\rangle \\notin \\mathcal{E}^O} \\enspace \\exp(r_{u, \\hat{v}} / \\tau)}$, where $\\tau$ is the temperature parameter.\n\nBoth two loss functions aim at maximizing the prediction scores between positive node pairs while minimizing that between negative node pairs. **Note that, all these mentioned loss functions can be easily deployed to our method, which is determined by the practitioners according to their practical applications**. We will make this claim more clear in the final version.\n\n[2] He et al. LightGCN: Simplifying and Powering Graph Convolution Network for Recommendation. SIGIR 2020: 639-648.\n\n[3] Wu et al. Self-supervised Graph Learning for Recommendation. SIGIR 2021: 726-735.\n\n------\n\n### [About the concerns on ablation study (Q4)]\n\nIt seems that there are some misunderstandings about the \"-fusion\" in the ablation study and cross-links, and we would like to help you have a better comprehension from the following two key points:\n\n1. **The role of embedding fusion.** Embedding fusion module is designed to assist GNNs in mitigating the impact of noise introduced by data augmentation. While standalone supervision augmentation can effectively aid in model debiasing, it may affect the overall performance of the model. In the ablation study, we remove the embedding fusion module and **reserve the supervision augmentation, which is denoted as \"-fusion\"**. As a result, in Table 3, **\"-fusion\" achieves the best debias performance -- the lowest Bias**, **while the overall performance is affected.** \n2. **The significance of cross-links.** As demonstrated in Figure 1, the proportion of cross-links in our utilized dataset is relatively small; however, they actually play a significant role in eliminating information cocoons and ensuring graph connectivity as we analyzed in Appendix B.\n\n------\n\nWe sincerely appreciate the reviewer's dedication and insightful comments. We hope that our responses have effectively tackled your concerns and enhanced your comprehension of our study. If you have additional questions or confusion, please feel free to contact us without hesitation. We are more than willing to be engaged in a new discussion and offer assistance."}, {"review_id": "elHUXto7xz", "reviewer": "Reviewer_a1aW", "summary": "The authors aim to explore the issue of bias in the link prediction task for GNNs. Specifically, they develop methods to mitigate the bias resulting from graph topology - on internal links versus cross-community links. Their work relies on debiasing node embeddings and a fusion component that retains aspects of both the original and the debiased node embeddings. The main goal is to ensure that the implicit creation of information silos does not degrade link prediction performance. The overall architecture borrow from retrieval model literature and is designed to be partially agnostic to model choice.", "questions": "See above", "limitations": "The authors address the fact that bias is not entirely eliminated by their procedure and that theoretical support does not yet exist for their contribution. The work has a positive societal impact as the key goal is to reduce bias.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The problem is significant enough in that enough research has been devoted to it in earlier literature, and that topology-induced bias is an interesting direction to consider.\n\n2. The authors experiment on a number of baselines to show the relative superiority of their method. They also include a number of ablation studies to show the effectiveness of their architecture.\n\n\n3. The architecture is model agnostic and allows for plugging in more powerful GNN models, for example.\n\n\n4. The loss function of the link prediction objective does not have to be modified (supported by a regularizer) and so the loss surface is not directly affected. Instead, supervised augmentation provides a kind of regularizing effect.\n", "weaknesses": "1. The main weakness of the paper is the small variety of datasets that the experiments have been run on. Ideally there should be multiple kinds of graphs, varying by size (nodes, edges), or even types of communities, their strength or internal cohesiveness and the degree to which they overlap. In comparison, the number of baselines is acceptable. The authors could add more graphs, for e.g. from the SNAP repository and experiment on more graph parameters like the above. Further, synthetic datasets generated by a particular model could help serve as a baseline and also possibly study the evolution of such cross-community bias in social networks.\n\n3. While community detection is done mainly via the Louvain algorithm, one could consider clustering based on node features and other methods such as stochastic block model as another baseline.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Sincere thanks for the reviewer's thorough evaluation and constructive comments. With respect to the reviewer's insightful feedback, we have organized our rebuttal as follows:\n\n------\n\n### [About the datasets (W1)]\n\nWe would like to address the concerns to the datasets utilized in our paper from the following two aspects:\n\n1. **The reasons for choosing social networks and recommendation networks.** As we analyzed in Appendix B.1, cross-links are highly essential due to their significance in easing information cocoons such as filter bubbles and echo chambers. These information cocoons widely exist among social networks and recommendation scenarios. In this way, we only utilized these two types of datasets in our work. \n\n2. **Additional experiments on two real-world datasets are provided.** In fact, our approach can potentially be applied to other types and sizes of datasets as well. In particular, we further investigate the performance of our method on the **Amazon dataset** (from SNAP) and the **Cora dataset**. **The corresponding experimental results based on two kinds of supervision augmentation methods are given in Table R5-R6 in the uploaded PDF.** So far, the datasets we have utilized are summarized in the table below:\n\n   |          | Users   | Items   | Interactions | Type      | Scenario               |\n   | -------- | ------- | ------- | ------------ | --------- | ---------------------- |\n   | Epinions | 75,879  | -       | 508,837      | User-User | Social Network         |\n   | DBLP     | 317,080 | -       | 1,049,866    | User-User | Co-author Network      |\n   | Cora     | -       | 2,078   | 5,278        | Item-Item | Citation Network       |\n   | Amazon   | -       | 334,863 | 925,872      | Item-Item | Co-purchase Network    |\n   | LastFM   | 1,892   | 17,632  | 92,834       | User-Item | Recommendation Network |\n\n   It can be observed that, we conduct experiments on five different kinds of datasets, with graph sizes ranging from 2.1k to 334.8k. The experimental results on all these datasets consistently verify the effectiveness of our model.\n\n3. **Additional experiments on a synthetic dataset are provided.** We additionally employ the *Stochastic Block Model* (SBM) to generate a synthetic dataset. In particular, the synthetic dataset comprises 4000 nodes and 56128 edges, and we perform experiments using two powerful GNN models: GraphSAGE and GAT. The corresponding results are displayed in Table R7 within the uploaded PDF. **Notably, our approach also consistently outperforms the baseline models in terms of both utility and debias on the synthetic dataset.**\n\n\n\n------\n\n### [About the community detection algorithms (W2)]\n\nWe agree with the reviewer that the community detection methods are important for our work, and we would like to address the reviewer's concerns from the following two perspectives:\n\n1. **The reasons for using Louvain algorithms and Metis algorithms.** As we highlight in the introduction, our study primarily concentrates on the link prediction bias based on the graph topology. Consequently, we do not use community detection methods based on node features in our experiments and use two kinds of community detection methods based on graph topology namely Louvain and Metis (mentioned in Appendix D.2).\n2. **Additional investigations on other community detection algorithms are provided.** To further illustrate the robustness of our approach to community detection methods, in addition to the Metis algorithm mentioned in Appendix D.2, we implement the LPA algorithm for community detection. **The experimental results on LPA are presented in Table R8 in the uploaded PDF**. It can be seen that, although we deploy different community detection method, our method still demonstrate strong capability in easing the bias between cross-links and internal-links with even improved link prediction utility.\n\n------\n\nWe sincerely appreciate the efforts and valuable feedback provided by the reviewer. We genuinely hope that our responses have addressed your concerns and contributed to a better understanding of our research. If you have any further questions or confusion, please do not hesitate to reach out to us. We would be more than willing to assist and provide further clarification."}, {"review_id": "rJEWcxzqeo", "reviewer": "Reviewer_Nju4", "summary": "This work finds that current GNN methods have severe data bias because GNNs like to connect new links inside the local neighbors and ignore the distant ones. To address this problem, the authors investigate the bias across different communities and propose a general framework. In this framework, the authors devise three key components, including supervision augmentation, twins-GNN, and embedding fusion module. To display the effectiveness of either component, the authors perform the ablation study, and with all of them, the Debias model has a promotion on three datasets compared with six GNN backbones.", "questions": "+ This paper uses Jaccard-based augmentation for Epinions and DBLP, and random walk based augmentation for LastfFM because of LastfFM’s high density. Moreover, the authors detail the analysis of two augmentations, but how can we decide which is better before the link prediction experiments?", "limitations": "Yes. The authors acknowledge that the data bias might not be the mere reason, and the supervision augmentation lacks theoretical analysis.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "+ The idea of rethinking the data bias, especially the fact that existing GNN models tend to connect local neighbors, is novel and has basic value.\n+ The writing is clear and easy to follow. \n+ The framework has a strong generality that can be applied to most GNNs (six examples used in this paper). \n+ The framework is an end-to-end framework and is easy to accomplish.\n", "weaknesses": "- The clusters should be pre-computed by some community detection algorithms (Louvain algorithm in this main content and METIS algorithm in the appendix); however, the impact of the quality of the community detection is unknown, and the results vary greatly under different community detection algorithms.\n- The promotion of link prediction on DBLP and LastFM seems not to be apparent, especially the bias is still very high. (This phenomenon is referred to by the authors in the limitation part.)\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are sincerely grateful to the reviewer for the careful evaluation and insightful comments.  We would like to address the concerns raised in the feedback in the following responses.\n\n------\n\n### [About the impact of community detection algorithms (W1)]\n\nBy comparing the experimental resulst based on Louvain algorithm (Table 2) and Metis algorithm (Table C2 in Appendix D.2), it can be observed that different community detection methods have limited influence on the overall performance of GNN, primarily affecting the debiasing effectiveness. This is mainly due to the sample variations in cross-links and internal-links obtained from different community detection methods. **However, our method consistently demonstrates a certain degree of debiasing capability across different community detection algorithms.** In practical application scenarios, users can define cross-links and internal-links based on their specific requirements, and subsequently employ our approach for training purposes.\n\n------\n\n### [About the choice of supervision augmentation (Q1)]\n\nIn particular, the choice of supervision augmentation method should primarily be determined by the characteristics of the dataset, such as its density. Additionally, as we highlight when introducing random walk based augmentation, when the communities within the graph are quite extensive, relying solely on Jaccard-based augmentation may inadvertently focus mostly on nodes at the boundaries of communities. Consequently, in such cases, a more effective supervision augmentation strategy would be random walk based methods.\n\nOverall, in this paper, **we have presented two simple yet effective supervision augmentation methods**, both centered around the concept of identifying highly potential cross-links within the graph that have not been observed yet, and we acknowledge the possibility of exploring alternative and potentially more efficient methods in our future work.\n\n------\n\n### [About the limited debias performance (W2)]\n\nAs we mentioned in the limitation, we observe that the bias between cross-links and internal-links is only mitigated in a limited degree. In this way, we believe that the data bias between internal-links and cross-links may not be the only reason for the poor performance on cross-links, and the performance bias may come from multiple causes such as inbalanced data distributions, GNNs' biased aggregation operations and so on. We sincerely hope that our work can provide a new debias direction for other researchers and we leave the unexplored perspectives as our future work. \n\n------\n\nWe sincerely appreciate the efforts and valuable feedback provided by the reviewer. We genuinely hope that our responses have addressed your concerns and contributed to a better understanding of our research. If you have any further questions or confusion, please do not hesitate to reach out to us. We would be more than willing to assist and provide further clarification."}, {"review_id": "EchHAm31Vw", "reviewer": "Reviewer_Lg87", "summary": "This paper addresses the bias between internal links and cross-links by augmenting cross-links and combining two models consisting of the original and debiased models. Specifically, the authors show that the number of cross-links is fewer than internal links in three real-world datasets. Thus, with Jaccard coefficient score, they augment cross-links and train a debiased model on the augmented graphs. To resolve the trade-off between utility and fairness, they fuse the representation of the original model (which is trained on the original graph), and the debiased model. In experiments, they show that the proposed method resolves the bias and even improves the overall performance.", "questions": "- In the ablation study, I’m interested in the experimental details for “-Augment”. I understand it as this policy randomly chooses connections among possible cross-links (Not including internal-links). If not, it would be more persuasive to show the comparison with the policy I described.\n- In Table 4, it would be more persuasive to provide the performance of internal-links and cross-links, as shown in Table 2, and 3.\n- It is difficult to understand Figure 2. Could you provide a more detailed description of  Figure 2?", "limitations": "The authors provide several limitations in the main paper. However, as I mentioned in Weakness, it would be better additionally to address other issues such as the applicability to heterophilous graphs.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- In contrast with the existing methods, the authors mainly target the bias based on graph topology.\n- The suggested method mitigates the bias without compromising performance on several datasets under various architectures.", "weaknesses": "- It seems insufficient to demonstrate that internal-links are more common than cross-links based solely on three datasets. For heterophilous graphs, cross-links would be more prevalent when each node label is regarded as a community. In this case, it is more reasonable to augment internal-links, but the suggested method is not able to do it.\n- The rationale for supervision augmentation, which is the core component to resolve the bias, seems weak. Why is the Jaccard coefficient score better than other options? Due to its formulation, it would be difficult to augment the connections between a node with a high degree and a node with a low degree. However, using an edge predictor does not have this limitation and is a more simple approach. (Specifically, train an edge predictor and predict edges with this predictor. Then, choose edges based on the confidence of the predictor.)\n- The performance of models without fusion is inferior to base models in Table 3. Since supervision augmentation is the core component to mitigate the bias, this component is more important than other components, but it is weak. Based on this observation, it is probable that using UGE as a debiased model would show better performance than the current approach. (Slight tuning is needed to combine UGE.) Then, the contribution of this paper would be marginal.\n- Comparing baselines only under GraphSAGE seems insufficient. Could you compare the proposed method with UGE under LightGCN and GAT, too?\n- The datasets used in this paper are quite different from the baselines such as FairAdj and UGE. UGE uses  Pokec-z, Pokec-n, and MovieLens-1M, while FairAdj utilizes Oklahoma97, UNC28, Facebook#1684, Cora, Citeseer, and Pubmed. Are there any reasons to evaluate the methods on different datasets? According to FairAdj, Cora, Citeseer, and Pubmed have more internal-links than cross-links. Thus, the performance superiority on these graphs can further support the effectiveness of the proposed method.\n- The connections between sentences in the abstract seem unnatural.\n\nMinor issues\n\n- In line 24, “research concerns” seems unnatural. I recommend “research interests”.\n- In line 394, “Epilogue” seems non-academic expression. I recommend “Conclusion”.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### [About the concerns on heterophilous graphs (W1)]\n\n1. **Additional statistics on multiple heterophilous graphs are provided.** To validate the data bias on heterophilous graphs, we conduct community detection with Louvain algorithm on six datasets that have low homogeneity ratios (Hom. Ratio). Specifically, we follow the definition of homogeneity ratio in [1]: $Hom. Ratio=\\frac{\\sum_{\\langle u, v\\rangle\\in|\\mathcal{E}|}\\mathbb{1}(y_u=y_v)}{|\\mathcal{E}|}$. \n\n   where $\\mathcal{E}$ denotes the edge set,  $y_u$ represents the label of  node $u$ and $\\mathbb{1}(\\cdot)$ is an indicator function. The numbers of internal-links and cross-links are illustrated in Table R1 within the uploaded PDF. It can be seen that, even in datasets with low homogeneity ratios, cross-links still significantly fall short of internal-links. **This observation further supports that the data bias between internal-links and cross-links is widely existed in the real world, even in heterophilous graphs.**\n\n2. **Our model's flexibility to augment internal-links.** In fact, the fundamental idea of our approach is to focus on the minority group in the data and then find out high-confidence, unobserved samples for supervision augmentation. **In this way, even if in a context where the number of cross-links exceeds that of internal-links, we can also handle this situation by simply reversing the criteria within the supervision augmentation**, thus augmenting the corresponding minority. \n\n[1] Du et al. GBK-GNN: Gated Bi-Kernel Graph Neural Networks for Modeling Both Homophily and Heterophily. WWW 2022.\n\n------\n\n### [About the concerns on supervision augmentation (W2)]\n\nSince we need to train a separate edge predictor for supervision augmentation, we believe that this kind of approach may potentially inherit the data bias between cross-links and internal-links, thereby limiting its effectiveness in mining unobserved cross-links. In contrast, the heuristic methods in our paper require no training process, inherently sidestepping the risk of introducing bias from data. What's more, the experimental results also prove that the methods based on Jaccard coefficient and random walk are simple yet effective. \n\n------\n\n### [About the concerns on ablation study and baseline UGE (W3, W4)]\n\n1. It seems that there might have been a slight misunderstanding regarding the Ablation study.  As a core component in our model, the embedding fusion module is designed to assist GNNs in mitigating the impact of noise introduced by data augmentation. While standalone data augmentation can effectively aid in model debiasing, it may affect the overall performance of the model. In the ablation study, we remove the embedding fusion module and reserve the supervision augmentation, which is denoted as \"-fusion\". As a result, in Table 3, **\"-fusion\" achieves the best debias performance -- the lowest Bias**, **while the overall performance is affected.** \n\n2. **Additional comparisons based on other base GNNs are provided.** As for the comparisons of UGE, we have further implemented UGE on GAT and LightGCN. The results are displayed in Table R4 within the uploaded PDF. As observed, due to the modifications in the objective functions, although UGE can achieve the best debias performance in certain instances, **it is unable to prevent noticeable utility degradation** compared to our methods. **This kind of debias achieved with sacrificing utility is not the admirable goal of our work.**\n\n------\n### [About the concerns of datasets (W5)]\n\nWe would like to address the reviewer's concerns related to the datasets from the following two aspects:\n\n1. **The reasons for choosing datasets.** In fact,  **it seems that a universally acknowledged benchmark has not been established yet in the prior work**. To be precise, we statistic the datasets in the prior works in Table R2 within the uploaded PDF, and it can be seen that different methods actually utilize different datasets. Therefore, given the graph scale in the real world, we choose three relatively large datasets from SNAP and RecBole. \n\n2. **Additional comparisons on the official datasets are provided.** For validating our method's effectiveness, we further conduct experiments and compare the performance of our method with baselines on their official datasets. The results are shown in Table R9 in the uploaded PDF. From the table we can observe that, on the official datasets, **our proposed method still consistently outperforms UGE and FairAdj on both debias and utility**, which further verifies our method's superiority.\n\n------\n\n### [About the concerns on presentation and clarification (W6, Q1, Q2, Q3)]\n\n1. **The details of ablation study \"-Augment\".** In our \"-Augment\" setting, we randomly select an equal number of cross-links, without including internal-links in these randomly chosen edges. We will enhance the corresponding descriptions in the final version.\n\n2. We will consider elaborating on the results of Table 4 in the final version (one additional page is permitted for the accepted paper).\n\n3. **Additional descriptions about Figure 2.** \n\n   We would like to help you have a comprehensive understanding of Figure 2 by describing the following three aspects:\n\n   - **Experimental settings:** In Figure 2, we initially apply the Louvain algorithm to cluster the item-item graph in the LastFM dataset. Subsequently, for conciseness, we randomly sample 10 clusters and statistic the number of the top 10 commonest labels across the entire graph. \n   - **Observations:** These results are visualized as a heatmap in Figure 2. It can be seen that each community contains its own specific information pattern, i.e. specific label distributions.\n   - **Conclusions:** It's impossible for one single community to encompass all diverse information in a network. This implies the propensity of graphs to form information cocoons with insufficient cross-links as bridges, which further verifies the significance of cross-links."}]

Author rebuttal:
## Response for All Reviewers

We sincerely appreciate the dedication and effort put forth by all the reviewers. We hope that our responses have effectively addressed your concerns and contributed to a deeper understanding of our research. **Due to space limitations, we have included most of the experimental results (figures and tables) in the attached PDF, with corresponding references provided in the rebuttal.** If you have additional questions or confusion, please feel free to contact us without hesitation. We would sincerely like to provide more information and clarification if necessary.

Meta-review: This paper tackles the issue of bias in GNN link prediction and introduces a twin-structure framework to alleviate the bias and enhance performance. Reviewers concur that the proposed twin-structure and embedding fusion are both straightforward and clear. The experimental results on extensive datasets demonstrate that the proposed framework effectively addresses bias and leads to performance improvements.

However, reviewers have also raised concerns regarding the efficiency of the proposed model, the limited diversity of datasets, the theoretical analysis, certain missing details, and the overall clarity of the paper. The authors' responses have managed to address a portion of the reviewers' concerns, and as a result, some reviewers have subsequently revised their scores. Based on these considerations, I recommend acceptance.
Decision: Accept (poster)