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, wown920mmil.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 word2vec.
Noise contrastive estimation NCE is a generic estimator for probability model Pn. of the form 19
0);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, (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, bascline 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 (0) 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, = = 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
P(i,)) R1j PMI (1.5) PMI.I, (i,5), where PM.,r(i,)) In 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-Prooteie
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 sosiggess-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)
Citer
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 parameters 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-deSBM 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.co////11////
Bi-
https: http://oorppall.looooo
why-anchorage-Bi is- not--hattimmortean inttrrta----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 /sinn//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": "oJKLnTkC-Gu", "reviewer": "Reviewer_eKFw", "summary": "This paper propose a prior probability for noise contrastive estimation (NCE) using degree-corrected stochastic block model (dcSBM), and propose a framework called residual2vec to learn the embedding of each node in the network, with a matrix factorization on the difference between random walk based empirical probabilities and the  dcSBM prior. The motivation arises from the implicit debiasing (of node degrees) property of negative sampling. Experiment results on link prediction and community detection are provided, as well as a case study on web of science citation network.", "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": "This work proposed a novel prior for NCE and matrix factorization solution of node embedding, based on the implicit debiasing (of node degrees) property of negative sampling from existing work, which is adequately cited. It is overall technically sound and clearly written, although some details and notations are not explicitly explained. The framework is potentially useful for practitioners to get better node embeddings with less dependency on node degrees, the web of science citation network can be a good dataset for other researchers to evaluate their algorithm if the authors can release them.\n\nMy comments and questions:\n\n1. line 117, $\\delta$ is not defined, it seems to be an indicator function. Please make sure to explain the notations as they appear.\n\n2. lines 116-120, I can see from the supplementary that you are fitting a dcSBM first, please explicitly mention it, otherwise it confuses me how you get the group $g_i$\n\n3. line 142, regarding $P_d(i)=P_0(i)$, it is not clear how you get it. Are you assuming what you learn from the dcSBM model is exactly the groundtruth, and even if so, how do you get it? Please provide a proof\n\n4. line 248, why do you fit that particular linear regression model? The form is not commonly used.\n\n5. For community detection experiment, why don't you use accuracy as the evaluation metrics? Also as you are using dcSBM as the null model in residual2vec, I would like to see how fitting a dcSBM itself performs in those experiments. If fitting dcSBM alone gives good community detection results, there is not much beneficial from the more complex residual2vec.\n\n6. Will the web of science citation network be released for public validation? If not, I would suggest the authors to use other publicly available networks like arxiv or us patents from SNAP (http://snap.stanford.edu/data/index.html#citnets) \n\n7. Figure 4D, it shows GCN has large dependence on degree but not year. Are you using negative sampling for GCN, if not, it does not seems to be a fair comparison to me.\n\nOverall I think this paper is on the borderline. I like the idea of using dcSBM as null model and the explanations in sec 3.2, so I recommend borderline accept.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, they discuss them in section 5. ", "review_text": "", "extra_scores": {"ethical_concerns": "No Ethical Concerns", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "iSH9eiNX3nT", "reviewer": "Reviewer_yRN6", "summary": "The paper proposes an unsupervised graph representation learning method, named residual2vec. The random walk-based approaches might be biased in sampling the center-context node pairs due to the network structure and many methods employ a noise distribution to sample the negative instances. The paper investigates the assumptions taken into the consideration during the sampling procedure. The authors formulate the sampling procedure under a general framework, and they show that the existing methodologies can be expressed as special cases of the proposed approach. The performance of the algorithm is evaluated on the link prediction and community detection tasks.", "questions": "", "limitations": "", "rating": 7, "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 organization of the paper is quite good, and it is well-written but some points could be enhanced. For instance, the definitions of the probability distributions can be more explicitly given in order to reduce the ambiguity. The difference between the notations $p_0()$ and $P_0()$ is not clear.\n \nThe authors clearly explain the proposed methodology with an illustrative figure. They consider a problem that has not been well studied before. The paper generalizes existing random walk-based approaches by reformulating the sampling procedures and proposes a novel framework. The paper could attract the interest of the community working in the graph representation learning field.\n \nHere, I would like to add some notes and ask questions to clarify some points about the paper.\n \n-  Could the authors elaborate more on what the offset values are, which are used in the link prediction task? And why the offset values for Node2Vec and DeepWalk are not set?\n- Why is the parameter B to 1,000? Does the parameter depend on the network size or structure?\n-  Why don’t the authors use the NetMF approach in the experimental evaluation? It is also cited in Table 1, and it is very relevant to the proposed approach. It learns the embeddings by factorizing the matrix based on the random walks.\n- In the experimental evaluation,  the authors might use more recent approaches in order to evaluate the performance of the proposed methodology.\n- The paper proposes a general framework, but it only concentrates on a special case of degree-corrected stochastic block model (dcSBM) with uniform random walk strategy. It might be because of the computational problems but it might be good to examine the influence and the relationship between the chosen random walk distribution and noise distribution. For instance, the authors of the SkipGram approach empirically observe that the model works well for \\gamma value equal to 0.75, and similarly, random walk-based approaches apply the same value for the parameter. Why do these models for this common choice show better performance in the downstream tasks?\n \nTypos:\n\nOn line 232, Furthremore -> Furthermore\nOn line 163, computaionally -> computationally\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discuss the limitations and possible social impact of the proposed methodology.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "WIBXte2y2q6", "reviewer": "Reviewer_yRQF", "summary": "There are two major contribution from this paper: 1) the authors provide the insight that the word2vec trained with SGNS is implicitly canceling out the bias due to the degree of the node; 2) the authors use this insight to introduce a framework that allows removing any structural bias in the graph, so that the true affinity between nodes can be revealed. Under this framework, the authors proposed to use the degree-corrected stochastic block model as the baseline probabilities, and learn the residual information on top of the baseline model. The authors also show that residual2vec can be understood as matrix factorization.\n\nThe authors use residual2vec empirically for link prediction and community detection, and find it works empirically the best against competing baselines. Moreover, in the case study, the authors show how residual2vec can be used to remove the bias introduced by publication years, and suggested how the model can be used to remove social bias in many real-world applications.", "questions": "", "limitations": "", "rating": 8, "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": "This paper brings a lot of insights to the existing methods such as node2vec and deepwalk, and explains why certain choice of p0 works well in different scenarios. The proposed residual2vec is efficient, gives good empirical performance, and is widely applicable to different scenarios. The writing is super clear and the experiments are very insightful. I haven't follow the node embedding literatures closely, so I will rely on other reviewers to judge the originality.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I find great positive societal impact of this paper. The method proposed in this paper can potentially be used to implicitly remove gender bias, racial bias, and age bias in social graphs.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "1eInjROVhL", "reviewer": "Reviewer_RJD5", "summary": "The paper presents residual2vec, a random-walk based node embedding method that explicitly factors out the structural bias of a specified null graph model. The authors claim that, by factoring out the structural biases of a null graph model, the learned embeddings better capture the salient features of the graph. The method learns node embeddings in an efficient way using singular value decomposition. It is then compared with other random-walk based node embedding methods, including node2vec and DeepWalk. The experiments examine how the different methods perform in terms of link prediction, community detection, and the prediction of underlying node features from embeddings. In most cases, residual2vec appears to do as well or better than these baselines. They also train a linear regression model, for each of the methods, to predict the node cosine similarity using the node degrees. Residual2vec (and several of the baselines) achieve a low r-squared in this linear regression, indicating that the embeddings are not biased by node degree.", "questions": "", "limitations": "", "rating": 6, "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": "See the References section of the main paper for any citations used in this review.\n\n## Originality:\n\nSome parts of the paper are novel. The embeddings on their own are learned to solve the same problem as node2vec. Both the authors of word2vec and residual2vec treat the noise distribution as a free parameter. The novel contribution of this paper are as follow:\n1.\tIt explicitly incorporates of the null graph transition probability in the conditional model (Equation 10). \n2.\tIt shows that the model can be fit perfectly if the dot product of embeddings is equal to the residual pointwise mutual information (explained in the paper).\n3.\tThe learning of the embeddings by singular value decomposition is an efficient solution. \n4.\tThe experiments and results are novel.\n\nI think the contribution of some other works should be stated more clearly. For instance, in section 2.2 Implicit debiasing by negative sampling, it should be made clear that equations 4, 5 and 6 come from [9].\n\nI think the authors should clearly state the differences between residual2vec, and the skip-gram with negative sampling (NEG) by Mikolov et al. [6], where they describe the noise distribution as a free parameter of both NCE and NEG.\n\n## Quality:\n\nThere are a few statements in the paper that I believe to be technically inaccurate (see detailed comments). I believe there is also an unstated assumption regarding the transition probability in the configuration model (also in the detailed comments).\n\nI would be interested to see how the offset ln $d_i$ + ln $d_j$ performs on its own in the link prediction task, as this is a monotonic transformation of preferential attachment, which is often a highly predictive metric.\n\nI am unconvinced that r2v-dcSBM achieves the best visual separation of classes in the 2d projection.\n\nThe prediction of journal impact factor and journal subject using KNN should ensure that test set nodes cannot have the same journal with a different year as one of its K nearest neighbours, and this should be made clear in the text.\n\n## Clarity:\n\nMost of the text is okay with regards to clarity, with the exception of section 2.2 Implicit debiasing by negative sampling. It took me a while to understand this section. I would like to see more of an introduction laying out the purpose of the derivation (to infer an unbiased model for $p(j|i)$), the logic of the derivation (showing that, for a certain choice of $f$, it has the same posterior probability as an estimator that we know to be unbiased), and the distinction between $Pm(x)$, $P(Yj=1|j)$ and $P(j|i)$.\n\nOne of the biggest issues with the paper is the figures displaying the results, particularly Figure 3. It is difficult to visually distinguish some of the series and their confidence intervals (due to overlap). A larger figure or a table might make the results clearer. Figure 3A-F also contain a series which is not in the legend (it is possible part of the legend has been cut off). Figure 3G-H has no explanation for the difference between G Degree homogeneous and H Degree heterogeneous in the main text nor the caption (I can guess, but clarification would be nice).\n\n## Significance:\n\nI think the novel elements of the paper are sufficiently significant for publication. I think it is possible that other researchers will use some of these ideas or build on them. Equation 9 in the paper helps to explain the widely used skip-gram negative sampling.\n\nI have added some more detailed comments relating to specific parts of the paper below.\n\n* Line 6-7: “Most notably, random walks are biased by the degree of each node, where, at each step, a node is sampled proportionally to its degree”\n   \n   Overall, a node is sampled proportionally to degree. At each step, I think neighbouring nodes are sampled uniformly (or in proportion to their share of edge weights of the present node).\n\n* Line 53: “… SGNS word2vec models conditional probability…”\n\n   Here, they define $P_{\\text{w2v}}$ (a sigmoid) as the way in which SGNS word2vec models the conditional probability of the context given the centre word. This is problematic because using the softmax here has nothing to do with negative sampling. They correctly carry on pointing out that learning the log probability of the softmax over a large corpus is not feasible. This was originally pointed out by the word2vec paper, where they also introduced and compared several strategies, including hierarchical softmax, NCE, negative sampling, and subsampling of frequent words. I would ask the authors to refrain to using SGNS word2vec here, and use skip-gram instead to avoid confusion.\n\n* Line 60: “Additionally, one samples k random context word…”\n\n   This is slightly misleading as context words are not being sampled. Words are being randomly sampled as candidate context words.\n\n* Line 70-71: “To see this, let us consider the unbiased variant of negative sampling, Noise Contrastive Estimation (NCE)”\n\n   Here, the authors introduce NCE as a “the unbiased variant of negative sampling”. This is incorrect, as NCE precedes NEG, and Mikolov et al. (authors of word2vec) describe NEG as a simplification of NCE. I ask the authors to rephrase this and not call NCE a variant of NEG, in favour of something else. The authors also present insufficient evidence that NCE is unbiased. I ask that the authors either provide more evidence of this, or reduce their claim to asymptomatically unbiased (in the number of negative samples, $k$ [9]). \n\n* Line 72: “where $f$ is a non-negative function of data $x$ in all data $\\mathcal{X}$”\n\n   Could the authors please clarify what they mean by ‘all data’ here?\n\n* Section 3  Residual2vec graph embedding, Line 91-92\n\n   The small paragraph at the start of this section mentions that the authors assume graphs are weighted, but it is not mentioned whether the graphs used in the evaluation are all weighted. The supplementary also mentions that the weights are Poisson distributed, which assumes that they only take discrete values, but this is not mentioned in the main text.\n\n* Section 3.1 … Random graph models\n\n   The dcSBM only preserves the expected degree of each node. Therefore, setting B=1 does not result in the configuration model, which exactly preserves the degree of each node.\nSimilarly, dcSBM only preserves the expected number of edges in the graph (according to the supplementary, the edge weights follow a Poisson distribution). Therefore, setting $B=1$ and $d_i =$ constant does not result in the Erdős-Rényi random graph that only preserves the number of edges.\n\n* Table 1\n\n   The baseline probability of $P_0(j|i)$ for the configuration model given in the table is an approximation for when the number of nodes is large, but this is never mentioned. It is not accurate for small graphs. Consider the configuration model defined by the degree sequence (a:1, b:1, c:2). For $T=1$, The nodes of degree 1 (a and b) cannot be linked within this model and thus $P_0(a|b) = 0$, and not $\\frac{1}{4}$ as the table suggests.\n\nIf the authors can adequately address my concerns, I would consider increasing my score.\n\nEdit: Based on the edits the authors have made in response to my review, I have edited my rating, increasing it from 4 to 6.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I think the authors adequately address the limitations and societal impact", "review_text": "", "extra_scores": {"ethical_concerns": "I have no ethical concerns about this paper", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents Residual2Vec, a technique for reducing structural biases for graph embedding. Existing methods use random walk-based sampling, which has a strong preference towards "hub" nodes. The paper draws an insightful analogy of how debasing effectively happens in negative sampling in word2vec, which inspired the authors to develop Residual2Vec to compensate structural biases in random walks. The reviewers are overall happy with the paper, with questions and concerns mostly regarding the presentation of the work. These questions are mostly clarified during the rebuttal, which the authors should include in the final version of the paper. The work makes a useful contribution for learning effective graph node embeddings with less dependency on node degrees. 
Decision: Accept (Poster)