Residual2Vec: Debiasing graph embedding with random graphs
Authors: Sadamori Kojaku
Jisung Yoon
Isabel Constantino
Yong-Yeol Ahn
Venue: NeurIPS 2021 Poster (2021)
Keywords: Negative Sampling
Debiasing
Graph embedding
Random walks

Abstract: Graph embedding maps a graph into a convenient vector-space representation for graph analysis and machine learning applications. Many graph embedding methods hinge on a sampling of context nodes based on random walks. However, random walks can be a biased sampler due to the structural properties of graphs. Most notably, random walks are biased by the degree of each node, where a node is sampled proportionally to its degree. The implication of such biases has not been clear, particularly in the context of graph representation learning. Here, we investigate the impact of the random walks' bias on graph embedding and propose residual2vec, a general graph embedding method that can debias various structural biases in graphs by using random graphs. We demonstrate that this debiasing not only improves link prediction and clustering performance but also allows us to explicitly model salient structural properties in graph embedding.

Residual2Vec: Debiasing graph embedding with random graphs
Sadamori Kojaku', Jisung Yoon', Isabel Constantino", Yong- Yeol A.n
CCenter for Complex Networks and Systems Research, Luddy School Informatics, Computing and Engincering, Indiana University, USA
2 Department of Industrial Management and Engineering Pohang University of Science and Technology, South Korea
Inddiaaa University Network Science Institute Indiana University, USA
*Connection Science Massachusetts Institute of Technology, USA
{skojaku, imconsta, yyahn]@iu. jisung, yown920mmil.cccoomoo
Abstract
Graph embedding maps graph into convenient vector-space represen- tation for graph analysis and machine learning applications. Many graph embedding methods hinge on a sampling of context nodes based on random walks. However, random walks can be a biased sampler due the structural properties of graphs. Most notably, random walks are biased by the degree of each node, where node is sampled proportionally to its degree. The implication of such biases has not been clear, particularly in the context of graph represenlation learning. Here, we investigate the impact of the random walks' bias on graph embedding and propose residual2ver, general graph embedding method that can debias various structural biases graphs by using random graphs. We demonstrate that this debiasing not only improves link prediction and clustering performance but also allows us to explicitly model salient structural properties in graph embedding.
Introduction
On average, your friends tend to be more popular than you. This is a mathematical necessity known as the friendship paradoz, which arises due a sampling bias, i.e., popular people have many friends and thus likely to be your friend list [. Beyond being fun trivia, the friendship paradox is a fundamental property biased sampling that preferentially samples nodes based on nodes' degree (i.e., the number of neighbors). The fact that random walk is used as the default sampling paradigm across many graph embedding methods raiscs important questions: what the implications of this sampling bias in graph embedding? If it undesirable, how can we debias it?
graphs: following an edge
Graph embedding maps graph into dense vector representation, enabling direct application of many machine learning algorithms graph analysis 2 widely used framework is to turn graph into "sentence of nodes" and then feed the sentence to G A crucial difference from word embedding is that, rather than using given
word2vec
35th Conference on Neural Information Processing Systems (NeurIPS 2021).

---

A
B
Trajectory of random walks
200
400
600
800
1000
t
Fraction of core nodes in the graph
0.2
0.6
1.0
Time spent in core node
200
400
600
800
1000
Core
Periphery
Time
Figure Random walks have a strong preference lowards hubs. (A) toy graph generated by a stochastic block model with core-periphery structure, where core nodes have more neighbors than peripheral nodes 18 (B) Random walkers preferentially visit nodes with
many neighbors, generating trajectory that overrepresents the core nodes.
sentences, graph embedding methods generate synthetic "sentences" from given graph. In other words, the gencration of synthetic "sentences" in graph is an implicit modeling decision 7 which most graph embedding methods take for granted. A common approach for generating sentences from a graph is based on random walks, which randomly traverse nodes by following edges. The friendship paradox comes into play when walker follows edge (e.g., friendship tie): it is more likely to visit a node with many neighbors (e.g., popular individual). As an example, consider a graph with core-periphery structure, where core nodes have more neighbors than periphery (Fig. [A). Although core nodes are the minority, they become the majority in the sentences generated by random walks (Fig. [B). This is because core nodes have more neighbors than periphery and thus are likely to be neighbor of other nodes, which is manifestation of the friendship paradox. Then, how does the sampling bias affect the embodding?
Previous approaches to mitigate the degree bias in embedding based modifying random walks or the post-transformaaion by itself has an implicit bias arising from the optimization algorithm- skip-gram negative sampling (SGNS) which happens to negale the bias due to the friendship paradox. To leverage this debiasing feature further, we propose more general framework, residual2vec, that can also compensate for other systematic biases in random walks. We show that residual2vec performs better than conventional embedding methods in link prediction and community detection tasks. Using a citation graph of 260k journals, we demonstrate that the biases from random walks overshadow the salient features of graphs. By removing the bias, residual2vec better captures the characteristics of journals such as the impact factor and journal subject. The python code of residual2voe is available GitHub 17
the embedding 86 Here we show that word2vec
2 Built-in debiasing feature of SGNS word2vec
2.1 Background: SGNS word2vec
Consider sentence of words (I1, T2, .3,...) composed of N unique words. word2vec associates the fth word I with words in its surrounding Tt-T,.... I1-1, T44T, which are referred to context words, determined by prescribed window size T. For center-context word pair (i,j), word2vec models conditional probability
exp(u, v,)
Pizv(ili)
(1)
Σx= exp(u, v,y)"
where u. E KR Xx1 are emdedding veclors representing word center and context words, respectively, and is the embedding dimension. An approach to fit Pway is the maximum likelihood estimation, which is computationally expensive because Pw2y involves the sum

---

over all words. Alternatively, several heuristics have been proposed, among which negative sampling is the most widely used 3
Negative sampling trains word2vec as follows. Given a sentence, a center-context word pair (i.j) is sampled and labeled Y, = 1. Additionally, one samples & random word & as candidate context words from a noise distribution po(e), and then labels (i, E) as Y 0. In general, popular choice of the noise distribution po(() is based on word frequency, ie., po(() x Pa(é)7, where Pa(e) is the fraction of word & in the given sentence, and is syper-paramettr. Negative sampling trains u, and Vy such that its label Y, is well predicted by logistic regression model
PYs = 1; ui, v,) + exp( - u, 0y)
(2)
by maximizing its log-likelihood.
2.2 Implicit debiasing by negative sampling
Negative sampling efficiently produces a good representation G An often overlooked fact is that negative sampling is a simplified version of Noise Contrastive Estimation (NCE) 19
and this simplification biases the model estimation. In the following, we show that this estimation bias gives rise to built-in debiasing feature of SGNS word2vee.
Noise contrastive estimation NCE is a generic estimator for probability model Pn. of the form 19
();0)
(m(x)) Evex f(x::0)
33)
where f is a non-negative function of data in the set of all possible values of x. word2vec (Eq. [1] is a special case of Pm, where f(z) = exp(z) and æ u, By. NCE estimates Pm by solving the same task negative campling-cassifyinng a positive example and randomly sampled negative examples using logistic regression- -uu based on Bayesian
framework 19 20) Specifically, as prior knowledge, we know that in 1+K k pairs are taken from the given data, which can be expressed as prior probabilities
19 20
k
P(У, =) k+1 P(Y, 0)
(4)
++1
Assuming that the given data generated from Pu., the positive example (Y, =1) and the negative examples (Y, = 0) are sampled from Pm and po(j), respectively
19 20 i.c.,
P = 1) P.. (u. By), PUJY, 0) = po(j)-
(5)
Substituting Eqs. and an example j
into the Bayes rule yields the posterior probability for Y, given
19 20
PUIY, = 1) 1) Evelo,1) P PULY y) P(Y, v)
Pm (m( vz)
PaCe (Y, 11))
(6)
Pm (u! 11) + kpplo)
which can be rewritten with a sigmoid function as
PNCEE (Y; 1lj) 1+ kpplk))PPmmmmeeee (u,))) v,) 1 exp [- In su 0z) + In pn +c]
where = In k + In Er'E f(x') is constant. NCE Iearns Pm by the logistic regression based on Eq. 7 The key feature NCE is that it is an asymptomatically unbiased estimator of
Pm whose bias goes zero the number of training examples goes infinity
19
Estimation bias of negative sampling In the original paper of word2vee G. the authors simplified NCE into negative sampling by dropping ln po()) + e in Eq. 7 because it reduced the computation and yielded a good word embedding. the following, we show the impact of this simplification on the final embedding.
3

---

We rewrite PNS (i.., Eq. ① in the form of PNCE (i.e., Eq. 7 as
1
PNs(Y, = =1; = expp(-u;30 02))
exp uu Uj + In po(o)) c) + In
1 1xeep) -In l'u ((,',,,)))))),),}{{)) 0;) + li) +c]
Equation (8) makes clear the relationship between negative sampling and NCE: negative sampling is the NCE with f(u, 0z) = exp (u. u + lmpo(j) + +c) and noise distribution Po 21. Bearing mind that NCE is the asymptomatically unbiased estimator of Eq. 3
and substituting f(u, 0z) into Eq. (3), we show that SGNS word2vec is an asymptomatically unbiased estimator for probability model:
PSNNS (j Po(j) exp exp(u,
N
where 2; := Σ poli") exp(ue uy)). y'=1
(9)
Z
Equation 9 clarifies the role of noise distribution po. Noise probability po serves baseline for w2v and word similarity u, vj represents the deviation from po(j), or equivalently the characteristics of words not captured in Po(j). Notably, basclinc po(j) Pa())) is determined by word frequency Xa(i) and thus negates the word frequency bias. This realization-thun we can explicitly use noise distribution to obtain "residual" information is the motivation for our method, residual2vec.
Residual2vec graph embedding
We assume that the given graph is undirected and weighted, although our results can be generalized to directed graphs (see Supplementary Information). We allow multi-edges (i.c., multiple edges between the same node pair) and self-loops, and consider unweighted graphs as weighted graphs with all edge weight set to one 22 23
3.1 Model
The presence of Po(j) effectively negates the bias in random walks due to degree. This bias dictates that, for a sufficiently long trajectory of random walks in undirected graphs, the frequency Pa(j) of node is proportional to degree dj (i.e., the number of neighbors) irrespective the graph structure 24. Now, if we set y = bascline po(z) = Pa(j) matches exactly with the node frequency in the trajectory, negating the bias due to degree. But, are free to choose any Po- This consideration leads us to residualêtec model:
Pi ()) Poli 1) exp(u, U.))
(10)
Z
where we explicitly model baseline transition probability denoted by Poli 1). In doing so, we can obtain the residual information that is not captured in Po. Figure 2 shows the framework of residual2vec. To negate bias, we consider "null" graphs, where edges are randomized while keeping the property inducing the bias intact 22 23 Then, we compute Po either analytically or by running random walks in the null graphs. The Po then used as the noise distribution to train SGNS word2vec.
Random graph models Among many models for random graph 25 31 here we focus on the degree-cor corrected stochastic block model (dcSBM), which can be reduced to many fundamental random graph models with certain paramcter choices 28 With the dcSBM, one partitions nodes into B groups and randomizes edges while preserving (i) the degree of cach node, and (ii) the number of inter-/inee aater-/intra-gron group edges. Preserving such group connectivity useful to negale biases arising from less relevant group structure such as bipartite and multilayer structures. The dcSBM can be mapped to many canonical ensembles that preserve the expectation of structural properties. fact, when B 1, the dcSBM is reduced the soft configuration model that preserves the degree of each node average, with self-loops

---

Chaice of null model (random graphs, e.g. dcSBM)
Baseline probabilty
Matrix factorization
Po 8)
u. B/ In Pa(i ()
PdO (6)
Analytic solution (11)
Random graph generation
Output embedding
Sentence generator (Random walks)
Input graph
Empirical probability Pa ())
Sentence generator (Random walks or other analytical solutions)
Figure 2: residual2vec framework. We first choose an explicit "null" model (e.g., dcSBM random graph). By rumning random walks in the input and random graphs, "sentences of nodes" are generated and then compared to extract the residual information not in the random graphs. The final embedding encodes the residual information. Probabilities Pa and Po(j i) can be computed analytically in many cases. For instance, we use the analytical solution for dcSBM (i.e., Pa(j 6) and Polj i)) instead of simulating actual random walks.
Table 1: Baseline probability Poli i) for the dcSBM along with its special cases.
Canonical random graph models
Ardös-Rény' model for multigraphas 25
The soft configuration model
deSBM
28
Po(i (4)
1/N
N d Σ> de
dzD
T
P SBM
94.03
node2vec (7 = 0.75)
4
Algorithm
DeepWalk
NetMF (7 = 1) 32
and multi-edges allowed 31 Furthermore, by setting B = 1 and d, constant, the dcSBM reduced to the Erdös-Rényí Rényi model for multigraphs that preserves the number of edges on average, with self-loops and multi-edges allowed. In the dcSBM, the edge weights follow Poisson distribution and thus take integer valuos.
Suppose that the nodes in the given graph have B discrete labels (e.g., gender), and we want to remove the structural bias associaled with the labels. If no such label is available, all nodes are considered to have the same label (i.e, B = 1). We fit the dcSBM with B groups, where each group consists of the nodes with the same label. The dcSBM generates random graphs that preserve the number of edges within and between the groups (e.g., assortativity by gender types). We can calculate Po(j without explicitly generating random graphs (Supplementary Information)
dj Dgj
1 T
PoLli)
P
(11)
SBM
9::9;
where node has degree dy and belongs to group Jj, D, = =N dgō(ge.g). g), and 8 is Kronecker delta. The entry PSBM of matrix PAвM = (PSBM) E BxB is the fraction of edges to group g' in Dg- Table I lists Poli i) for the special classes of the dcSBM. See Supplementary Information for the step-by-step derivation.
Other graph embedding as special cases of residual2vee residual2vec can be considered as a general framework to understand structural graph embedding methods because many existing graph embedding methods are special cases of residual2vec. node2vec and NetMF use SGNS word2vec with ()( Pa()), This po(j) is equivalent to the baseline for the soft configuration model (31, where each node has degree d'. DeepWalk also based on word2vec but trained with unbiased estimator (i.e., the hierarchical softmax).
5

---

Because negative sampling with po(5) 1/N is unbiased 19 20 DeepWalk is equivalent to residual2vec with the Prdös-Rénys random graphs for multigraphss
3.2 Residual2vec matrix factorization
Many structural graph embedding methods implicitly factorize a matrix to find embed- dings 32 residual2vec also be described as factorizing matrix R which captures residual pointwise mutual information. Just like a Kth order polynomial function can be fit to K points without errors, can fit word2vec to the given data without errors when the embedding dimension K is equal to the nunber of unique words N 30 In other words, Pa () = Pivv i), V K N. By substituting Przv ()) = Po exp(u: u,)/2/, we obtain
Pa(i exp (u, Uj In Po(j i) - In Pa a))
Pal 1 = Σラ Palj' 1) exp (u, vy Po
(12)
In Pa(j" ())
In The equality holds if exp(u, v, + In Poli - Pali i)) = for all and j. where q; is constant. The solution not unique because c; can be any real value. We choose o; = to obtain solution in the simplest form, yielding matrix R that residual2vec factorizes:
R₂ = u u, = Pali i) - In Poli 1).
(13)
Matrix R. has an Information-thhorede interpretation. We rewrite
Rs in Pa(i,) - In Poli,j) In Pa(i.) In Poli,j) + In Pali) - In Pol). (14) Pa(i) Po(i)P(s)
Pa(i)
Po(i)
The dcSBM preserves the degree of each node and thus has the same the degree bias with the given graph, ie., Pa(t) = Po( (Supplementary Information), which leads
R1j PMI (1.5) PMI.I, (i,5), where PM.,r(i,)) In P(i,)) P()P())
(15)
PMI-p(i,j) is the pointwise mutual information that measures the correlation between center and context j under joint distribution P(i,j), i.e, PMIr((i, = i and j appear independently, and (M.,r(i, > 0 otherwise. In sum, Riy reflects residual pointwise mutual information of í and j from the mull model.
3.3 Efficient matrix factorization
Although we assume that N = K above, in practice, we want to find a compact vector representation (i.e., K N) that still yields a good approximation 30 There are several computational challenges in factorizing R. First, R is ill-defined for any node pair (i,j) that never appears because R. = In -c0. Second, R. often a dense matrix with O(N)) space complexity. For these issues, a common remedy is truncation 30 32
Rs max(R.j, 0).
(16)
This truncation discards negative node associations (R:; < 0) while keeping the positive associations (R,z 0) based on the idea that negative associations are common, and thus
are less informative 322 In both word and graph embeddings. the truncation substantially
reduces the computation cost of the matrix factorization 30 32
We factorize R (Riz) into embedding vectors 24 and Uy such that u,J, 02 ~ Ra by using the truncated singular value decomposition (SVD). Specifically, factorize R by R Piet diag(01,02, "2,,..,,Kkk + Fightt where P (Gleft) ) E R and $ right (otight) )a N are the left and right singular vectors of R associated with the K largest maenitude, respectively. Then, we compute u, and my by
singular values (kI)...ok)
uas = oleft, : Uik of
1-a right with a = 0.5 following the previous studies 30 32
0sk
The analytical computation of Pa(j i) is expensive because scales as OTT where T is the window size 32 Alternatively, one can simulate random walks to estimate Palj ())

---

Table 2: List of empirical graphs and structural properties. Variables N and M indicate the number of nodes and edges, respectively.
Network
N
Assortativity
Max. degree
Clustering coef.
Ref.
Airport
3,188
18,834
-0.02
0.498
331
Protein-Protteie
3,852
37.840
-0.10
593
0.148
34
Wikipedia vote
7,066
100.736
-0.08
1063
0.142
50
Coauthorship (HepTh)
6,638
24,827
0.24
65
0,482
Citation (DBLP)
12,494
49,594
-0.05
713
0.118
37
Coanthorship (AstroPh)
17,903
197,031
0:20
504
0.633
36
Yet. both approaches require O(N2) space complexity. Here, reduce the time and space complexity by the block approzimation that approximates the given graph by the dcSBM with B groups (we set B = 1, 000) and then computes an approximated Pa(j i). The block approximation reduces the time and space complexity to O((N + +MB TD²) and O(NBB) for graph with N nodes and M odges, respectively, with high accuracy (the average Pearson correlation of 0.85 for the graphs in Table 2). See Supplementary Information for the block approximation.
4 Results
We test residual2ve 2vec using link prodiction and community detection benchmarks 22 38
We use the soft configuration model 31 as the null graph for residual2ves denoted by r2v-config, which yields a degree-debiased embbedding. The soft configuration model allows self-loops and multi-edges sosigges--hihhh are not present in the graphs used in the benehmarks and thus is not perfectly compatible with the benchmark graphs. Nevertheless, because the multi-edges and self-loops are rare in the case of sparse graphs, the soft configuration model has been widely used for sparse graphs without multi-edges and self-loops 23 (1 39
40
As basclines, use (i) three random-walke walk-based methods, node2vec and FairWalk 16 (ii) two matrix-factorization based methods, Glove and Laplacian
DeepWalk 3
eigenmap (LEM) 42 and (iii) the graph convolutional network (GCN) 43 the graph attention and GraphSAGE 45 For all random-walle based methods, we run 10
networks (GAT)
walkers per node lor 80 steps and set T 10 and training iterations to 5. We set the parameters of node2vec by p= and E (0.5, 1,2]. For Glove, we input the sentences generated by random walks. We use two-layer GCN, GraphSAGE, and GAT implemented in StellarGraph package 46 with the parameter sets (e.g.. the number of layers and activation function) used in [3
45 Because node features are not available in the benchmarks, we
alternatively use degree and eigenvectors for the k smallest eigenvalues of the normalized Laplacian matrix because they are useful for link prediction and clustering 47 48
We
set K to dimension K (i.c., K K). Increasing K does not improve performance much (Supplementary Information).
Link prediction Link prediction task is to find missing edges based on graph structure. basic task for various applications such as recommending friends and products 4 40 49
The link prediction task consists of the following three steps. First, given a graph, a fraction 0.5) of edges randomly removed. Second, the edge-removed graph is embedded using a graph embedding mothod. Third, the removed edges are predicted based on a likelihood score calculated based on the generated embedding. In the edge removal process, we keep edges in a minimum spanning tree of the graph to ensure that the graph is a connected component. 4.40 This is because predicting edges between disconnected graphs an ill-defined (ask because each disconnected component has no relation to the other.
We leverage both embedding u, and baseline probability Po(ili) to predict missing edges. Specifically, we calculate the prediction score by u, uj + + 2j. where we set 2; = In Po(jl)) for residual2vec because In Po(jli)) has the same unit as u, uy (Supplementary Information). Glove has a bias term that is equivalent to z; Therefore, we set 2; to the bias term for Glove. Other methods do not have the parameter that corresponds to and thus set z =0 We measure the performance by the area under the curve of the receiver operating characteristics (AUC-ROC) for the prediction scores, with the removed edges and the same

---

Link prediction
Community detection
Airport
Wikipedia
C Protein Protein
0.95
0.9
0.8-
0.90
0.85
0.6
AUC-ROC
0.80
0.5
AUC-ROC
0.0
0.2
0.4
0.6
0.8
1.0
1-
Coauthorship (AstroPh)
Coauthorship (HepTh)
Citation (DALP) P)
1.0
0.95
0.8
H
0.85
0.6
0.5
28
0.5
0.6
0,7
Dimension. K
Mixing parameter, J
Qivoor fig offect
rodeZnc
Chos (alo olbc)
GogASAGE
-0-12 corliy
180
GAT
-e-recctiec (pen)
Parnak
DCH
(p=1)
Oihere
rA0KSher 10
Figure 3: Performance for link prediction and community detection. We average AUC-ROC values over 30 runs with different random seeds and compute the 90% confidence interval by a bootstrapping with 10a resamples. For link prediction, some underperforming models are not shown. See Supplemantary Information for the full results. r2v-config consistently performs the best nearly the best for all graphs in both benchmarks, as indicated by the higher AUC-ROC values.
number of randomly sampled non-existent edges being the positive and negative classes, respectively. We perform the benchmark for the graphs in Table 2
r2v-config performs the best or nearly the best for all graphs (Figs. 3A-F), It consistently outperforms other random walk-based methods in all cases despite the fact that node2vec and r2v-config train the same model. The two methods have two key differences. First, r2v-config uses baseline Po(E i) = Pa()), whereas node2vec uses Po i) x P that does not exactly fit to the degree bias. Second, r2v-config optimizes the model based on a matrix factorization, which often yields a better embedding than the stochast ic gradient descent algorithm used in node2vec 32 The performance of residual2vec is substantially improved when incorporating offset 2;, which itself is a strong predictor as indicated by the high AUC-ROC.
Community detection We use the Lancichinetti detection benchmark 388 The LFR benchmark generates graphs having groups of densely connected nodes (i.e., communities) with a power-law degree distribution with a prescribed exponent We set 7= 3 to generate the degree heterogeneous graphs. See Supplementary Information for the case of degree homogeneous graphs. In the LFR benchmark, each node has, on average, a specified fraction μ of neighbors in different communities. We generate graphs of N = 000 nodes with the paramcters used in Ref. 38 and embed the graphs to K= 64 dimensional space. We evaluate the performance by randomll sampling 10, 000 node pairs and calculate the AUC-ROC for their cosine similarities, with nodes in the same and different communities being the positive and negalive classes, respectively. A large AUC value indicates that nodes in the same community tend to have a higher similarity than those in different communities.
(LFR) community
As μ increases from zero, the AUC for all methods decreases because nodes have more neighbors in different communities. DeepWalk and LEM have a small AUC value even at J 0.05. 12v-config consistently achieves the highest or the socond-highest AUC.
Case study Can debiasing reveal the salient structure of graphs more clearly? We construct journal citation graph using citation data between 1900 and 2019 indexed in the Web of
8

---

A
Glove
node2vec
12v-deSBM
Year of journals
Joumals
1920
1940
1960
1980
2000
Journe Yher pear
Cisstons
node2vec
12v-dcBBM
Subject category
Eoler
Cheeurty
Prpalis
Goctannary
Ryseerm
Mediche
sarte ag Mekito
Huriing
Dependence of node similarity on node attributes
E
Prediction based on embedding
Desendence score)
In-degroe
Year
Subject catopory
0.03
0.20
Fl sccorre
0.15
CAL
Rc 0.00
0.0
6.02
Embedding
(2v-dESaN
node2vec
Glove
GCN
126-config
GrachGAGE
Figure Embedding of the WOS journal citation graph. (A) Fach node represents a pair (j,t) of journal and year and each edge is weighted by citations. (B, C) A 2d projection of 128-dimensional embedding by the LDA. (D) I2v-dcSBM produces the embedding that is less dependent on degree and time. (E) By using the k-nearest neighbor algorithm, the embedding by r2v-dcSBM best predicts the impact factor and subject category.
Science (WoS) (Fig. 4A). Each node represents pair (i,t) of journal i and year t. Each undirected edge between (1,1) and (i, is weighted by the number of citations between journal in year l and journal j in year l' The graph consists of 242, 789 nodes and 254, 793, 567 undirected and weighted edges. Because the graph has high average degree (i.e., 1, 1,04,,, some algorithms are computationally demanding. For this reason, omit node2vec with g = 0.5 and 2, NetMF, and GAT due to memory shortage (ITb of RAM). Furthermore, for GCN, we set K 32, which still took more than 18 hours. We also perform the whole analysis for the directed graph to respect the directionality of citations. Although all hods perform worse in predicting impact factor and subject category, we find qualitatively the same results. See Supplementary Information for the results for the directed graph
Here, in addition to the degree bias, there are also temporal biases, e.g., there has been exponential growth in publications, older papers had more time to accumulate citations, and papers tend to cite those published in prior few years 50 To remove both biases, residual2vec with the dcSBM (denoted by r2v-dcSBM), where we group journals by year to randomize edges while preserving the number of citations within and between years. We generate K = 128 dimensional embeddings with T 10.
Figures B and C show the 2d projection by the Linear Discriminant. Analysis (LDA) with journals subject categories as the class labels. Glove and node2vec capture the temporal structure prominently, placing many old issues at the center of the embeddings. By contrast, r2v-dcSBM spreads out the old issues on the embedding. To quantify the effect of temporal bias, randomly sample 50, 000 node pairs (i.j) and then fitting linear regression model Viy = up + wi (æ, +,,)+ + Wz
æ, Wyn,K, that predicts cosine similarity Vij for node pair (i,j) with attributes 2; and æj, where is either the degree the year of node We perform 5-cross validations and compute Rº score (Fig. 4D). A smaller R² Re-sc indicates

---

that node similarity is less dependent on node attributes and thus less biased. LEM has the smallest Rc-sc for both degree and year. r2v-dcSBM has a smaller R than r2v-config for year, respectively, suggesting that r2v-dcSBM successfully negates the biases due to time.
Is debiasing useful to capture the more relevant structure of graphs? We use embedding vectors to predict journal's impact factor (IF) and subject category. By employing the k-nearest neighbor algorithm, we carry out 5-cross validations and measure the prediction performance by R'-score and the micro-F1 score. To ensure that the train and test sets do not have the same journals in the cross-validation, we split the set of journals into the train and test sets instead of splitting the of nodes (i,t). No single method best predicts both impact and subject categories. Yet, r2v-config and r2v-dcSBM consistently achieve the strongest or nearly the strongest. prediction power for all & we tested (Fig. - This result demonstrates that debiasing embedding can reveal the salient structure of graphs that overshadowed by other systematic biases.
5 Discussion
In this paper, starting from the insight that word2vec with SGNS has built-in debiasing feature that cancels out the bias due to the degree of nodes, we generalize this debiasing feature further, proposing a method that can selectively remove any structural biases that are modeled by a mull random graph. By exposing the bias and explicitly modeling it, we provide a new way to integrate prior knowledge about graphs into graph embedding, and a unifying framework to understand structural graph embedding methods. Under our residual2vec framework, other structural graph embedding methods that use random walks can be understood as special cases with different choices of null models. Through empirical evaluations, we demonstrate that debiasing improves link prediction and community detection performances, and better reveals the characteristics of nodes, as exemplified in the embedding of the WoS journal citation graph.
Our method is highly flexible because any random graph model can be used. Although we focus two biases arising from degree and group structure in graph, one remove other biases such as the degree-degree correlation, clustering, and bipartitivity by considering appropriate null graphs. Beyond these statistical biases, there have been growing concerns about social bias (c.g., gender stereotype) as well as surveillanco and privacy in Al applications, which prompted the study of gender and frequency biases in word embedding [1 54 The flexibility and power of our selective and explicit debiasing approach may also be useful to address such biases that do not originate from common graph structures.
There are several limitations in residual2vec. We assume that random walks have a stationary distribution, which may not be the case for directed graphs. One ensure the stationarity in random walks by randomly teleporting walkers 55.. Second, is not yet clear to what extent debiasing affects downstream tasks (c.g., by losing information about the original graph). Nevertheless, we believe that the ability to understand and control systematic biases is critical to model graphs through the prism of embedding.
Broader Impact
There has been an ever-increasing concern on inappropriate social stereotyping and the leak of sensitive information in word and graph embeddings 51 56 Although we have not studied social biases in this paper, given the wide usage of graph embedding methods to model social data, our approach may lead to methods and studies that expose and mitigate social biases that manifest as structural properties in graph datascts. Our general idea and approach may also be appliod to modeling natural language and may contribute to the study of biases in language models. At the same time, by improving the accuracy of graph embedding, our method may also have negative impacts such as privacy altacks and exploitation of personal data (surveillance capitalism) 56 57 Nevertheless, we believe that our approach contributes to the effort to create transparent and accountable machine learning methods, especially because our method enables us to explicitly model what is structurally expected.
10

---

Disclosure of Funding
The authors acknowledge support from the Air Force Office of Scientific Research under award number FA9550-19-1-0891.
References
[1] Feld, S. L.. Why your friends have more friends than you do. Am. Sociol. 96, 1464-147 (1991).
[2] Cai, H., Zheng, V. W. & Chang, K. C.-C. A comprehensive survey of graph embedding: Problems, techniques, and applications. IEEE Trunsactions Knowl. Data Eng. 30, 1616 1637 (2018).
[3] Perozzi, B., Al-Rfou, R. & Skiena, S. DeepWalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD KDD, 701-710 (New York, New York, USA, 2014).
[4] Grover, A. & Leskovec, J. node2vec: Scalable feature learning for networks. In Proceedings of the 22ndd ACM SIGKDD KDD, 855 864 (New York, NY, USA, 2016).
Dong, Y., Chawla, N. Swami, A. metapath2vec: Scalable representation learning for heterogeneous networks. In Proceedings of the 23rd ACM SIGKDD KDD, 135-144 (New York, NY, USA, 2017).
[6] Mikolov, T., Sutskever, L,, Chen, K., Corrado, S. & Dean, Distributed representations of words and phrases and their compositionality. Advances in Neural Information Processing Systems, vol. 26 (2013).
[7] Eriksson, A., Edler, D., Rojas, A., de Domenico, M. Rosvall, M. How choosing random-walk model and network representation matters for flow-hased community detection in hypergraphs. Comman. Phys. 4, 12 (2021).
Andersen, R., Chung, F. & Tang, K. Local graph partitioning using PageRank vectors. In 47th Annual IEEE Symposium on Foundations of Compuler Science, 475-488 75-4866/ (2006).
[9] Wu, J., He, J. & Xu, J. DEMO-Net: Degree-specific graph neural networks for node and graph classification. In Proceedings of the 25th ACM SIGKDD KDD, 406 415 (New York, NY, USA, 2019).
[10] Tang, X. et al. Investigating and mitigating degree-related biases in graph convoltuional networks. In Proceedings of the 29th ACM International Conference Information & Knowledge Management, 1435- 1444 (2020).
[11] Ahmed, N. et al. Role-based graph embeddings. IEEE Transactions on Knowl. Data Eng. 1-1 (2020).
[12] Ha, W., Fountonlakis, K. & Mahoney, M. Statistical guarantees for local graph clustering. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, vol. 108, 2687-2697 (2020).
[13] Fountoulakis, K., Rousta-Khorasani, F., Shun, J., Cheng, Mahoney, M. W. Variational perspective on local graph clustering. Math. Program. 174, 553 573 (2019).
[14] Palowitch, J. & Perozzi, B. Debiasing graph representations via meladatta-orthoggnaal training. In 2020 IEEE/ACM International Conference on Advances Social Networks Analysis and Mining (ASONAM), 435 435-442 (2020).
[15] Faerman, E., Borutta, F., Fountoulakis, K. & Mahoney, M. W. LASAGNE: Locality and structure aware graph node embedding. In CBRE/WIC/ACL International Conference Web Intelligence, 246-253 (2018).
[16] Rahman, T., Surma, B., Backes, M. & Zhang, Y. Fairwalk: Towards fair graph embedding. In Proceedings of the Twentty-iggtt International Joint Conference on Artificial Intelligence, 3289 3295 (2019).
[17] Kojaku, S., Yoon, J.. Constantino, I. & Ahn, Y.Y. Python package for the residnal2vee graph embedding, lhtpp::/ http://ttttbto//teeeee wwt..//oossoooaa/////ooaa beeoojaauureiiuuawwe residua/2ved (Accessed 10/08/2021).
[18] Zhang, X., Martin, T. & Newman, M. E. J. Identification of core-periphery structure in networks. Phys. Rev. E 91, 032803 (2015).
[19] Gutmann, M. & Hyvärinen, A. Noise-contrastive estimation: new estimation principle for unnormalized statistical models. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, vol. 9, 297-304 (Chia Laguna Resort, Sardinia, Italy, 2010).
11

---

[20] Dyer, C. Notes noise contrastive estimation and negalive sampling (2014). arXivv14100.255)
[21] Murray, D. et al. Unsupervised embedding of trajectories captures the latent structure of mobility (2020). larXiv:202..02755
[22] Fortunato, S. Community detection in graphs Phys. Reports 486, 75 1--1 (2010).
[23] Newman, M. E. J. Networks: An introduction (Oxford University Press, 2014).
[24] Masuda, N., Porter, M. A. & Lambiotte, R. Random walks and diffusion on networks. Phys.
Reports 716-717, 1-58 (2017). 1612.03281
[25] Erdös, P. & Rényi, A. On random graphs. Publ. Math. 6, 290-297 (1959).
[26] Karrer, B. & Newman, M. E. J. Random graph models for directed acyclic networks. Phys.
Rev. E' 80, 046110 (2009).
[27] Garlaschelli, D. & Loffredo, M. T. Generalized bose-fermi statistics and structural correlations
in weighted networks. Phys. Rev. Lett. 102, 038701 (2009).
[28] Karrer, B. & Newman, M. E. J. Stochastic blockmodels and community structure in networks.
Phys. Rev. E 83, 016107 (2011).
[29] Expert, P., Evans, S., Blondel, V. D. Lambiotte, R. Uncovering space-independent communities in spatial networks. Proc. Natl. Acad. Sei. 108, 1663-7666 (2011).
[30] Levy, O. & Goldberg, Y. Neural word embedding implicit matrix factorization. In Advances in Neural Information Processing Systems (2014).
[31] Fosdick, B., Larremore, D., Nishimura, J. & Ugander, J. Configuring random graph models with fixed degree sequences. SIAM Rev. 60, 315-355 (2018).
[32] Qiu, et al. Network embedding as matrix factorization: Unifying DeepWalk, LINE, PTE, and Node2vec. Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, 459 167 (New York, NY, USA, 2018).
[33] Opsahl, T. nary ties and sample selection.
Why Anchorage is not (that)
important: hww.re/ossaa.oo.o..oooooomo htt.h/l.c/////11////
Bi-
https: http://torppall.looooo
why-anchorage-Bi is- not--hattimmortean inttrrtaa---iiia----t-------- and- -and--ampl--seeettion 10/08/2021).
(Accessed on
[34] Stark, C. et al. BioGRID: a general repository for interaction datasets. Nuclesc Acids Res. 34, D535-D539 (2006).
[35] Leskovec, J., Huttenlocher, D. & Kleinberg, J. Governance in social media: A case study of the wikipedia promotion process. Proc. Int. AAAI Conf. on Web Soc. Media 4 (2010).
[36] Leskovec, J., Kleinberg, J. & Faloutsos, C. Graph evolution: Densification and shrinking diameters. ACM Trans. Knowl. Discov. Data 1, 2-es (2007).
[37] Ley, M. The DBLP computer science bibliography: Evolution, research issues, perspectives bt.
In String Processing and Information Retrieval, 9th International Symposium, 1-10 (Berlin, Heidelberg, 2002).
[38] Lancichinetti, A. & Fortunato, S. Community detection algorithms: A comparative analysis. Phys. Rev E 80, 056117 (2009).
[39] Newman, M. J. Finding community structure in networks using the eigenvectors of matrices. Phys. Rev. E 74, 036104 (2006).
[40] Abu-El-Haija, S., Perozzi, B. & Al-Rfou, R. Learning edge represenlations via low-rank asymmetric projections. In Proceedings of the 2017 ACM Conference on Information and Knowledge Management, 1787 1796 (2017).
[41] Pennington, J., Socher, R. & Manning, C. Glove: Global vectors for word representation. In Proceedings of the 2014 Conference Empirical Methods in Natural Language Processing, 5, 1532 1543 (Stroudsburg, PA, USA, 2014).
[42] Belkin, M. & Niyogi, Laplacian eigenmaps for dimensionality reduction and data representa- tion. Newral Comput. 15, 1373-1396 (2003).
[13] Kipf, T. N. & Welling, M. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (Palais des Congrès Neptune, Toulon, France, 2017).
[44] Veličkovié, P. et al. Graph attention networks. In International Conference on Learning Represcntations (Vancouver, Canada, 2018).
[45] Hamilton, W. L., Ying, R. & Leskovec, J. Inductive representation learning on large graphs. In Proceedings of the 91st International Conference on Neural Information Processing Systems, 1025-1035 (Long Beach, USA, 2017).
12

---

[46] CSIRO's Data61. Stellargraph machine learning library (2018).
[47] Luxburg, U. A tutorial on spectral clustering. Stat. Comput. 17, 395-416 (2007).
[18] Kunegis, J. & Lommatzsch, A. Learning spectral graph transformations for link prediction. In Proceedings of the 26th Annual International Conference on Machine Learning. 561-568 (New York, NY, USA, 2009).
[49] Zhang, 7. al. Arbetrary-order proximity preserved network embedding. In Proceedings of the 24th ACM SIGKDD KDD, 2778 2786 (ACM, 2018).
[50] Wang, D., Song, C. & Barabási, A. L. Quantifying long-term scientific impact. Science 342, 127-132 (2013).
[51] Bolukbasi, T., Chang, K.-W., Zou, J., Saligrama, V. & Kalai, A. Man is to computer programmer woman is to homemaker? debiasing word embeddings. In Proceedings of the 90th International Conference on Neural Information Processing Systems, 4356-4364 (Red Hook, NY, USA, 2016).
[52] Ethayarajh, K., Duvenaud, D. & Hirst, G. Towards understanding linear word analogies. In Proceedings of the 57th Annual Meeling of the Association for Compulational Lénguistics, 3253-3262 (Florence, Italy, 2019).
[53] Ethayarajh, K., Duvenaud, D. & Hirst, G. Understanding undesirable word embedding associations. Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, 1696-1705 (Florence, Italy, 2019).
[54] Zhou, K., Ethayarajh, K. & Jurafsky, D. Frequency-based distortions in contextualized word embeddings (2021). arXiv:2101.08663
[55] Lambiotte, R. & Rosvall, M. Ranking and clustering of nodes in networks with smart telepor- tation. Physicciaal Rev. 85, 56107 (2012).
[56] Edwards, H. & Storkey, A. Censoring representations with adversary. In 4th International Conference Learning Representations, 14 (San Juan, Puerto Rico, 2016).
[57] Bose, A. & Hamilton, W. Compositional fairness constraints for graph embeddings. Tn Proceedings of the 36th International Conference on Machine Learning, vol. 97, 715-724 (2019).
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] See Figures and 4.
(b) Did you describe the limitations of your work? [Yes] See the last paragraph of the Discussion section.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See the Broader Impact section.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of ussumptions of all theoretical results? [Yes] See Sections
2.2 and 3.1, 3.2, and 3.3.
(b) Did you include complete proofs of all theoretical results? [Yes] See Sections 2.2, 3.1, 3.2, 3.3 for the main derivation and Sections and 2 in Supplementary Information for the step-by-step derivation.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material URL)? [Yes] See
Section in Supplementary Information.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section
(c) Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [Yes] See Figures 3 and 4.
(d) Did you include the total amount of computing and the type resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Section 3 in Supplementary Information.
13

---

4. If you using existing ussels (u.g., code, data, models)) or surating/releasinng new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] See Table
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any assets either in the supplemental material
URL? [Yes]
The code to reproduce our results available at GitHub. See the reference list.
(d) Did you discuss whether and how consent
obtained from people whose data you're msint//craatng? [Ye=] All data except WoS data are publicly available. We discuss how we obtain the consent in Section 3 in Supplementary Information.
(e) Did you discuss whether the data you are using/curating curating contains personally identifiable information or offensive content? [Ye]] Our data did not contain privacy-sensitive information.
5. Tf you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [No] We neither crowdsoureing conducted research with human subjects.
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [No]
(c) Did you include the estimated hourly wage paid participants and the total amount
spent on participant compensation? [No]
14


Reviews:
[{"review_id": "y6JzsmA0OBo", "reviewer": "Reviewer_MjL3", "summary": "In this paper, the authors emphasize the limitations of node representation learning methods that are based on random walks and how these random walks are biased from the connectivity in the graph. Nodes with high degree are the minority in such graphs, however they end up appearing often in the random walks. The authors propose a method that can be used as a component in existing methods in order to debias the various structural biases in graphs. The proposed method is utilizing the degree-corrected stochastic block model (dcSBM), that is partitioning nodes into groups and randomizes edges while preserving the degree of each node and the number of inter/intra group edges. They conduct experiment to test the proposed method against six state of the art models and some variations in the link prediction and community detection tasks. The results show that the proposed model outperforms the other in most cases. They also analyse their findings in a case study where they study a journal citation graph.\n\n-- I acknowledge that I have read the authors' response and the other reviews.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well-written, well-structured and easy to follow. It is around a fair observation in the high degree of rare nodes in graphs that influence a lot the random walks that are widely used during node representation learning. The idea and the proposed solution are simple, but can be used in a lot of existing methods to improve their performance and decrease the bias. The authors justify their choices for the proposed solution by citing the corresponding works. The experimental setup looks very good and they conduct a number of experiments using different downstream tasks (link prediction, community detection) and various datasets to show the improvements in the performance of the compared methods. Figure 4 is also very compact and offers a lot of information for the analysis of the results.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discuss the limitations of this work in the paper, and there are no concerns risen for potential negative societal impact of this paper. They have also included a broad impact section, where they discuss the benefits of their proposed method and findings in node representation learning applications, to avoid biases when learning the embeddings.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns arise from reading this paper.\n", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "_YgAdAwfoMx", "reviewer": "Reviewer_q94Z", "summary": "This paper mainly investigates the impact of bias originating from random walk on graph embedding. To handle the bias, the authors propose a model named residual2vec, based on the paradigm of skip-gram, for structurally fair node representation learning on graph. Experiments on several datasets demonstrate the effectiveness of the proposed model.", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Fairness or bias learning is a hot topic in the machine learning community, which deserves wide and deep investigation. However, several concerns in this paper should be well-addressed by the authors.\n\n1. This paper investigates fair representation learning in a random walk based paradigm. However, the related work is not sufficiently introduced, and several recent studies [1,2,3,4] also consider this problem, which are not cited and compared by the authors. For example, role2vec [2] considers the node degree as (one of) the role(s) of each node for better node representations, and Fairwalk consider more fair random walk to boost the fairness of the learned node embeddings.\n\n2. In the Introduction, the motivation is not so clear: why the debiasing of random walk based models can improve their performance? What is the benefit of the debiasing to node embedding?\n\n3. In Sect-3.1, the illustration of null graph is not clear. More details are needed to depict the usage of null graph. Besides, it is the same case for dcSBM, which is not clearly illustrated, either.\n\n4. In experiments, the baselines are not sufficient, some recent approaches such as [1,2,3,4] should be imported for comparison. Besides, it is better to employ GAT [5] as a baseline, since it can usually achieve better performance than GCN.\nFor link prediction, the proposed residual2vec performs worse than Glove on 3/6 datasets, thus the performance of the proposed model seems not good enough. No analysis is given.\n\n\nOverall, this paper focuses on an old research problem, the skipgram-based node representation learning. Furthermore, I think the contribution of this paper is limited, and the proposed model is incremental to some extent, which cannot catch the standard of this conference.\n\n\n[1] DEMO-Net: Degree-specific Graph Neural Networks for Node and Graph Classification. KDD 2019.  \n[2] Role-based Graph Embeddings. TKDE 2020.  \n[3] Fairwalk: Towards Fair Graph Embedding. IJCAI 2019.  \n[4] Investigating and Mitigating Degree-Related Biases in Graph Convolutional Networks. CIKM 2020.  \n[5] Graph Attention Networks. ICLR 2018.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please see the Main Review.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}, {"review_id": "TKFblPbHaiL", "reviewer": "Reviewer_HWNH", "summary": "A lot of machine learning models use random walks to create \"context\" for the nodes in the graph. However, some random walk methods have biases towards high degree nodes. Thus, starting the random walk from some node, the random walk might be drawn quickly to high degree nodes. The authors propose a new model for de-biasing node embedding methods from the biases of random walks. They solve the issue by changing the definition of the conditional probabilities that are fit to the data. They draw a relation between Noise Contrastive Estimation and Negative Sampling, and they show that using the latter, one can clearly understand the role of the noise probability $p_0$ in the SGNS word2vec model. Then they define the $p_0$ using random graphs with the goal to de-bias the model.", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I like the idea. It is clean and simple and it also seems perpendicular to existing approaches for node embeddings. I also like the motivation from NCE to NS. I have currently voted for rejection for the following reasons.\n\nMajor comments\n\n1) The idea that traditional random walks are biased towards high degree nodes (depending on the structure of the given graph) is true. However, it is an archaic idea at the same time. The problem of high degree nodes has been solved by approximate personalized PageRank vectors that penalize diffusing mass to high degree nodes. The first attempt is from [1]. Later on in [2] and [3], it was shown that the method in [1] is equivalent to performing degree weighted l1-regularization. This basically means, that the higher the degree of the node the larger the penalty in the approximate personalized PageRank vector. So, in a sense, the problem of random walks that the authors claim has been solved. In addition, these methods have a regularization parameter that controls the size of the penalty of high degree nodes. Therefore, one can control the random walk/diffusion process to remain local without touching high degree nodes. There are even more advanced methods than PageRank-based methods that put a heavier penalty to high degree nodes by changing the norm that they operate with. For combinatorial diffusions see [5] and [8], for p-norm diffusions see [6-7]. \nIt's fine to not know about [5-8] since they are too new, but [1] is folklore, thus ignoring it is important. \n\n2) In [4], the authors have tried to tackle exactly the same problem using [1]. They even mention the same core-periphery example and they go pretty deep into understanding how [1] helps de-biasing traditional random walks used in node2vec and DeepWalk. The authors need to refer to [4] and also compare with it. \n\n3) I would also like to see experiments for multi-label classification as done in node2vec and [4]. Such experiments can be put in the appendix and helps the reviewers evaluate the performance of the proposed method compared to existing methods. \n\nMinor comments\n\n4) GCN and GraphSAGE are implemented in Pytorch-Geometric. Why are you using StellarGraph?\n\n5) For link-prediction and the dataset AstroPh, DeepWalk is shown to significantly outperform node2vec, with the AUC-ROC curve to be larger than 0.8 for DeepWalk and always smaller than 0.8 for node2vec. However, in [4] it is shown that node2vec and DeepWalk have similar performance and above 0.8 for 2 different operators for the edge embedding. For comparison, it would be helpful if the authors discuss in detail the setting of their experiments as discussed in [4]. Why is it that in your experiments node2vec performs so poorly? \n\n[1] R Andersen, Fan R. K. Chung, and Kevin J. Lang. Local graph partitioning using pagerank vectors. In FOCS, pages 475–486, 2006.\n\n[2] K Fountoulakis, F Roosta-Khorasani, J Shun, X Cheng, and M W Mahoney. Variational perspective on local graph clustering. Mathematical Programming, 174(1-2):553–573, 2019.\n\n[3] W Ha, K Fountoulakis, M W Mahoney. Statistical guarantees for local graph clustering, arXiv:1906.04863.\n\n[4] E Faerman, F Borutta, K Fountoulakis, MW Mahoney. Lasagne: Locality and structure aware graph node embedding. IEEE/WIC/ACM International Conference on Web Intelligence (WI), 246-253, 2018.\n\n[5] D Wang, K Fountoulakis, M Henzinger, MW Mahoney, S Rao. Capacity releasing diffusion for speed and locality. International Conference on Machine Learning, 3598-3607\n\n[6] K Fountoulakis, D Wang, S Yang. p-Norm Flow Diffusion for Local Graph Clustering. International Conference on Machine Learning, 3222-3232.\n\n[7] M Liu, D Gleich. Strongly local p-norm-cut algorithms for semi-supervised learning and local graph clustering. NeurIPS 2020.\n\n[8] R Ibrahim, D Gleich. Nonlinear Diffusion for Community Detection and Semi-Supervised Learning. WWW 19.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "9 hours"}, "extra_text": {}}, {"review_id": "TBc6JeiK6Ex", "reviewer": "Reviewer_2mkY", "summary": "The paper introduces a graph embedding method that claims to debias structural biases in graphs by using random graphs called residual2vec. The work investigates that the standard random walk-based embedding methods have implicit bias due to the friendship paradox I.e., it is more likely that the dense node (node with many neighbors) is visited more frequently in the random walk. The authors performed experiments on residual2vec model for link prediction and community detection tasks. The work shows that the biases from the random walk overshadow the important features of graphs and that debiasing models the structural properties in the embeddings and improves the performance in the tasks. Baselines from variants of graph embedding methods have been considered in the experiments. Six datasets are taken for link prediction and one benchmark dataset is taken for the community detection task. Additional experiments on the directed citation graph and the sensitivity to the dimension of node features are provided in the supplementary. ", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: \n\n1. The idea of considering random graphs to debias the learned embedding is interesting and intuitive as the random graphs can make the learning more robust. \n2. Paper is explained properly with clear notations. \n3. To the best of my knowledge, there hasn't been much work on debiasing graph embeddings. So, this can be a good contribution to the area. \n4. Empirical evaluation of two tasks with interesting experiments is performed in the main paper and supplementary. \n5. This seems to be a generalized method of debiasing the learning curve for any random walk-based graph embedding method. \n\nWeaknesses: \n\n1. The novelty of the paper is somewhat limited. Moreover, since the key contribution is using random graph models, authors should do an ablation study on how it compares to other choices of random graph models, under the same framework. \n2. Contributions are not clearly listed anywhere in the paper. \n3. I find the idea interesting. However, I do not see consistency in the improvement of results. Only in the case of the journal citation graph, I see notable improvements. In Figure 3, we can see that Glove is consistently performing better. Even embedding visualizations are not helping in making clear distinctions. \n4. What would be the complexity of truncated R as the matrix is large (NxN)? \n5. No overall complexity analysis is provided. If N is large, then, even the SVD is computationally expensive. \n6. What about the existing work on debiasing GNNs? None of the papers are cited. No mention of how this work is different from those and no comparison is made with those works. \n[1] DEBIASED GRAPH NEURAL NETWORKS WITH AGNOSTIC LABEL SELECTION BIAS \n[2] Say no to the Discrimination: Learning Fair Graph Neural Networks with Limited Sensitive Attribute Information \n[3] MONET: DEBIASING GRAPH EMBEDDINGS VIA THE METADATA-ORTHOGONAL TRAINING UNIT \n[4] Debiasing Graph Representations via Metadata-Orthogonal Training ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Based on issues with the novelty, the experimental setup (lacking comparison) and the experimental results (lack of clear superiority over comparison), the reviewer discussion converged on rejection of the manuscript in its present form. We hope that the reviews provide useful feedback that can help improve a future presentation of the work. 
Decision: Accept (Poster)