MONET: Debiasing Graph Embeddings via the Metadata-Orthogonal Training Unit
Authors: John Palowitch
Bryan Perozzi
Venue:  (2020)
Keywords: Graph Embeddings
Representation Learning

Abstract: Are Graph Neural Networks (GNNs) fair? In many real world graphs, the formation of edges is related to certain node attributes (e.g. gender, community, reputation). In this case, any GNN using these edges will be biased by this information, as it is encoded in the structure of the adjacency matrix itself.  In this paper, we show that when metadata is correlated with the formation of node neighborhoods, unsupervised node embedding dimensions learn this metadata. This bias implies an inability to control for important covariates in real-world applications, such as recommendation systems. 

To solve these issues, we introduce the Metadata-Orthogonal Node Embedding Training (MONET) unit, a general model for debiasing embeddings of nodes in a graph. MONET achieves this by ensuring that the node embeddings are trained on a hyperplane orthogonal to that of the node metadata. This effectively organizes unstructured embedding dimensions into an interpretable topology-only, metadata-only division with no linear interactions. We illustrate the effectiveness of MONET though our experiments on a variety of real world graphs, which shows that our method can learn and remove the effect of arbitrary covariates in tasks such as preventing the leakage of political party affiliation in a blog network, and thwarting the gaming of embedding-based recommendation systems.

Under review as a conference paper at ICLR 2020
MONET: DEBIASING GRAPH EMBEDDINGS VIA THE METAADTAA-ORTOOGONA TRAINING UNIT
Anonymous authors Paper under double-blind review
ABSTRACT
Are Graph Neural Networks (GNNs) fair? In many real world graphs, the formation edges is related to certain node attributes (e.g. gender, community, reputation). In this case, standard GNNs using these edges will be biased by this information, as is encoded in the structure the adjacency matrix itself. In this paper, we show that when metadata is correlated with the formation of node neighborhoods, unsupervised node embedding dimensions learn this metadata. This bias implies inability control for important covariates in real-world applications, such as recommendation systems.
To solve these issues, introduce the Detadata-Orthogone Node Embedding Training (MONET) unit, generalizable neural network architecture for perform- ing training-tine tiie linear debiasing of graph embeddings. MONET achieves this by ensuring that the node embeddings are trained on a hyperplane orthogonal to that of the node metadata. This effectively organizes unstructured embedding dimen- sions into an interpretable topology-oni, metadata-only division with no linear interactions. We illustrate the effectiveness of MONET though our experiments on a variety of real world graphs, which shows that our method can learn and remove the effect of arbitrary covariates in tasks such as preventing the leakage of political party affiliation in blog network, and thwarting the gaming of embedding babsed recommendation systems.
INTRODUCTION
Graph embeddings continuous, low-dimensional vector representations of nodes have been eminently useful in network visualization, node classification, link prediction, and many other graph learning tasks (10). While graph embeddings can be estimated directly by unsupervised algorithms using the graph's ' structure (e.g. 24 28 15] 25), there is often additional (non-relational) information available for each node in the graph. This information, frequently referred as node attributes or node metadata, can contain information that is useful for prediction tasks including demographic, geo-spatial, and/or textual features.
The interplay between a node's metadata and edges is a rich and active area of research. Interestingly. number of cases, this metadata can be measurably related to a graph's 's structure (2I), and in some instances there may be a causal relationship (the node's s attributes influence the formation of edges). As such, metadata can enhance graph learning models (31 20) and conversely, graphs can be used as regularizers in supervised and semi-supervised models of node features (32) IT). Furthermore, metadata are commonly used as evaluation data for graph embeddings ( For example, node embeddings trained on a Flickr user graph were shown to predict user-specified Flickr "interests" (24). This is presumably because users (as nodes) in the Flickr graph tend to follow users with similar interests, which illustrates potential causal connection between node topology and node metadata.
However, despite the usefulness and prevalence of metadata in graph learning, there are instances where it desirable to design system avoid the effects of particular kind of sensitive data. For instance, the designers of recommendation system may want to make recommendations independent of user's demographic information location.
At first glance, this may seem like an artificial dilemma surely one could just avoid the problem by not adding such sensitive attributes to the model. However, such approach (ignoring sensitive

---

Under review as a conference paper at ICLR 2020
attribute) does not control for any existing correlations that may exist between the sensitive metadata and the edges of node. In other words, if the edges of the graph are correlated with sensitive metadata, then any algorithm which does not explicitly model and remove this correlation will be biased as a result of it. Surprisingly, almost all of the existing work in the area (31 35 has ignored this important realization
In this work, we seek to refocus the discussion about graph learning with node metadata. To this end, we propose novel, general technique for extending graph representations with metadata embedding dimensions while debiasing the remaining (topology) dimensions. Specifically, our contributions are the following:
1. The Metadata-Orine Orthogonal Node Embedding Training (MONET) unit, novel GNN al- gorithm which jointly embeds graph topology and graph metadata while enforcing linear decorrelation between the two embedding spaces.
2. Analysis which proves that a naive approach (adding metadata embeddings without MONET) leaks metadata information into topology embeddings, and that the MONET unit does not.
3. Experimental results on real world graphs which show that MONET can successfully "debias" topology embeddings while relegating metadata information separate metadata embeddings.
PRELIMINARIES
Early graph embedding methods involved dimensionality reduction techniques like multidimensional scaling and singular value decomposition (8). In this paper
graph neural networks trained on random walks, similarly to DeepWalk (24). DeepWalk and many subsequent methods first generate a sequence of random walks from the graph, create a "corpus" of node "sentences" which are then modeled via word embedding techniques (e.g. word2vec (19) or GloVe (23) to learn low dimensional representations that preserve the observed co-occurrence similarity.
Let W be a d-dimensional graph embedding matrix, W E Raxd, which aims to preserve the low- dimensional structure of graph << n). Rows of W correspond to nodes, and node pairs i, with large dot- pot-produsts W ,W, should be structurally or topologically close in the graph. As a concrete example, in this paper we consider the debiasing of a recently proposed graph embedding using the GloVe model (6) Its training objective is:
GloVe(U, a, = Σ fa(Cs))a bb + V, - log(Ci,)))² S.j
(1)
where U, V E Raxd are the "center" and "context" embeddings, a, E Raxl are the biases, C' is
the
context co-occurrences, and fa is the loss smoothing function (23). We
use the GloVe model in the next section to illustrate topology/metadata embeddings and metadata- orthogonal training. However, the MONET unit we propose is broadly generalizable. To illustrate this, we also describe MONET unit for DeepWalk (24). popular graph embedding algorithm.
Notation. In this paper, given a matrix A Rxd and index I,..., n, A, denotes the d x 1 i-th row vector of A. Column indices will not be used. Onxd denotes the n x d zero matrix, and ||- || denotes the Frobenius norm.
METADATA EMBEDDINGS AND ORTHOGONAL TRAINING
In this section we present MONET, our proposed method for separating and controlling the effects of metadata on topology embeddings. First, we begin by outlining the straightforward extension of metadata to traditional embedding models Section 3.1 Next, in Section 3.2 we prove that such a simple model will leak information from the metadata to the topology (structural) embeddings. Then, we present MONET, our proposed approach for training embeddings of a graph's
in Section 3.3
While preparing this manuscript, we have become aware of recent independent result ( in this area for recommender graphs. In contrast that work, use substantially different methodology which offers guarantees about the debiasing pracess.
2

---

Under review as a conference paper at ICLR 2020
structure which not correlated with metadata. Finally, conclude with some analysis of MONET in Section 3.4
3.1 JOINTLY MODELING METADATA & TOPOLOGY
A natural first approach to modeling the effects of metadata on the graph is to explicitly include the node metadata as part of node embedding model. For instance, to extend Eq. ( in addition to U and V (the "topology embeddings"), we consider the node metadata M directly (M R= row vector M, is the metadata for node uz). We then can define metadata embeddings X = MT;, Y = MT2, where Tı, T2 trainable transformations, and propose the concatenations [U, X] and [V,y] as full-graph representations. The GloVe loss with metadata embeddings is:
Glote
(U, UU, T2, BIC, M) = 2
Σ fa(Cz)(a+tb x log(C (2) G
While in this paper we demonstrate metadata embeddings within the GloVe model, they can be incorporated in any dot-product-based graph neural network. For instance, the well-known DeepWalk (24) loss, which is based on word2vec (1)), would incorporate metadata embeddings as follows:
DeepWalk, Walk (U. TWW, = Σ log( Vog(U/V,+x())) - Σ Log(-U,"V Yv).
'jeW
KEK;
Above, W is the set of context pairs from random walks, and K; is set of negative samples associated with node i. For GloVe, DeepWalk, and many other GNNs, this approach augments the overall graph representation by concatenating metadata-learned dimensions.
However, this naive approach does not guarantee that the topology embeddings converge to be decor- related from the metadata embeddings. Suppose that the metadata (like demographic information) are indeed associated with the formation of links in the graph. In this case, any algorithm which does not explicitly model and remove the association will be biased as result of In the next section we formalize this concept, which we call metadata leakage.
3.2 METADATA LEAKAGE IN GRAPH NEURAL NETWORKS
Here, we formally define metadata leakage for general topology and metadata embeddings, and show how it can occur even in embedding models with separate metadata embeddings. All proofs appear in the Appendix.
Definition 1. The metadata leakage of metadata embeddings Z E Raxdd into topology embeddings W E Raxd is defined ML(2, W) == W/I.. We say that there is meladata leakage if and only if MLM(,, W)
Without a more nuanced approach, metadata leakage can occur even in embedding models that explicitly include the metadata, like Eqs. (2) and (3). To demonstrate this, we consider for simplicity a reduced metadata-awar GloVe loss with ;= = V e gaxd as the sole topology embedding and T := Ti T2 E mxy as the sole metadata transformation parameter. With 2 == MT, the reduced loss is:
1 Σ (a, aa WTW, + z - log log) 2 i.5
GloVe (W, (W.T.aCC,M)
(4)
We now show that under a random update of the VloVe meta model in Eq. (4), the expected metadata leakage is non-zero. Specifically, let (i,j) be a node pair from C, and define dw (i, j) as the incurred Stochastic Gradient Descent update W +- W + (i,j). Suppose there is a "ground-truth" metadata transformation B E Rmxdn, and define ground-truth metadata embeddings 7 := MB, which represent the "true" dimensions of the metadata effect on the co-occurrences C. Define Σg BB" and Ex TTT, With expectations taken with respect to the sampling of pair (i.j) for Stochastic Gradient Descent, define fw := E[W and Ew == E(W,W?] Define μMM EM similarly. Then our main Theorem is as follows:
3

---

Under review as a conference paper at ICLR 2020
Algorithm 1 MONET Unit Training Step
Given: topology embedding W, metadata embedding Z
1: procedure FORWARD PASS DEBIASING(W, Z)
2: Compute Z left-singular vectors Qz and projection Px + Iuxn Q2Q2
3: Compute orthogonal topology embedding W- - PzW
4:
return debiased graph representation [W -
5:
procedure BACK WARD PASS DEBIASING(ÓW)
6:
Compute orthogonal topology embedding update o Pzów
7:
Apply update W- + W- ow
8:
return debiased topology embedding W-
Theorem 1. Assume Ew = ow ow > O, jaw = Oax1, and μM = =0mx1 Suppose for some fixed 0 E R we have log(Cig) = + 7 Zj. Let (i,j) be randomly sampled co-occurrence pair and W' the incurred update. Then if W[ = B E IRd we have
B[MC(Z, 2 2 EM Ex) + (n ow Im
(5)
Importantly, Dr and ow are neural network hyperparameters, so we give useful Corollary: Corollary 1. Under the assumptions of Thhorem 1, ([MM(2,,W) 1 as co.
Note that under reasonable GNN initialization schemes, 7 and , are random perturbations. Thus, Corollary implies the surprising result that incorporating feed-forward metadata embeddings not sufficient to prevent metadata leakage in practical settings.
3.3 MONET: METADATA-ORTHOGONT NODE EMBEDDING TRAINING
Here, we introduce the Metadata Metadata-Orthogone Orthogonal Node Embedding Training (MONET) unit for training joint -opology-metudata
metadata graph representations [W, Z] without metadata leakage. MONET explicitly prevents the correlation between topology and metadata, by using the Singular Value Decomposition (SVD) of Z to orthogonalice updates to W during training.
MONET, The MONET unit a two-step algorithm applied to the training of topology embedding in a neural network, and is detailed in Algorithm [ The input to a MONET unit is metadata embedding E Raxdd and target topology embedding E xdd for debiasing. Then, let Qz be the left-singular vectors of Z, and define the projection Pz == Inxn QzQz. In the forward pass procedure, debiased topology weights are obtained by using the projection W11 Pz W. Similarly, W is used in place of in subsequent GNN layers. In the backward pass, MONET also debiases the backpropagation update to the topology embedding, dw, using di Pzow. Figure illustrates a geometric interpretation of the MONET algorithm.
Straightforward properties of the SVD show that MONET directly prevents metadata leakage:
Theorem 2. Using Algorithm i MC(Z, w 0 and MC 8+) 0.
We note that in this work we have only considered linear metadata leakage; debiasing nonlinear topology/metadata associations is an area of future work.
Implementation (MONET and MONETp). We demonstrate MONET our experiments by applying Algorithm 1 to Eq. (2 and Eq. (3). We denote these models respectively by MONET and MONET p. for MONET "GloVe" and "DeepWalk". For MONETG, we orthogonalize the input and output topology embeddings U, V with the summed metadata embeddings Z := X + Y. By linearity, this implies Z-orthogonal training of the summed topology representation W U + V. We note that working with the sums of center and context embeddings is the standard way to combine these matrices (23). Figure 2 shows an illustration of MONETG. MONET, is implemented similarly, and fully described in the Appendix Section A.3
4

---

Under review as a conference paper at ICLR 2020
endlesdings
Fondommation
P P.W.
W
Figure I: Geometric interpretation of MONET. Both prediction and training for W occur on hyperplane orthogonal Z. In the forward pass, W is projected onto the Z-orthogonal plane. When update dw is proposed, it too is pro- jected, resulting in the best metadata-orthogondd orthogonal update. This allows W explore the space of unknown latent structure without bias from Z.
Figure 2: Illustration of MONET
U and V are topology embeddings. The MONET unit adds feed-forward transforma- tion of the metadata, resulting in metadata em- beddings X and Y. Z X + Y gives the com- bined metadata representation, used to debias U and V via Pz. Dotted lines indicate stopped gradient flow during backpropagation.
3.4 ANALYSIS
Here we address some brief remarks about the algorithmic complexity of MONET, and the interpreta- tion of its parameters.
Algorithmic Complexity. The bottleneck of MONET occurs in the SVD computation and orthogo-
nalization. In our setting, the SVD is (nd)) (9).. The matrix Pz need not be computed to perform orthogonalization steps, PzW W Qz W) and the right-hand quantity is ((ndd.) to compute. Hence the general complexity of the MONET unit is O(nd, max(d, de H. In Table we compare the wall clock time of MONET and baselines, showing only about 10% overall time increase from standard GloVe.
Metadata Parameter Interpretation. The i,j terms in the sum of the loss for GloVe models with metadata Ve and MONETg) involve the dot product X?Y, = M,TT;T, My. That expan- sion suggests that the matrix Vn == TiT: contains all pairwise metadata dimension relationships. In other words, Er gives the direction and magnitude of the raw metadata effect on log co-occurrence, and is therefore a way to measure the extent to which the model has captured metadata information. We will refer to this interpretation in the experiments that follow. An important experiment will show that applying the MONET algorithm increases the magnitude of Σy entries.
Connection Adversarial Methods. There are now many methods for supervised learning that use adversarial networks to produce data representations that are invariant to given factors (e.g. 30 [3). Because we are introducing MONET in the unsupervised graph learning setting, none of these approaches (to knowledge) apply out-of-the-box to produce baseline. To give an idea for how an adversarial approach might work as an alternative to MONET, we craft a adversarial version of Glo Ve which attempts to predict the metadata from the topology embeddings. This method, which to our knowledge is novel, is fully described Section 4.1 and the Appendix.
4 METADATA DEBIASING EXPERIMENTS
Here we empirically demonstrate Theorems and by confirming the following hypotheses:
1. HI. The MONET unit can remove leakage of metadata information from topology embed- dings, so that the topology embeddings cannot predict the metadata.
2. H2. The MONET unit can make recommender systems more robust to abuse by removing malicious user directions from rating graphs.
5

---

Under review as a conference paper at ICLR 2020
For all embedding models, use the center-context embedding sum of topology embeddings W := U V as the graph representation for task evaluation. Note that some standard baselines (e.g. DeepWalk) do not incorporate metadata and therefore only train topology embeddings. All GloVe-based models are trained with TensorFlow ( using the AdaGrad optimizer (12) with initial learning rate 0.05. DeepWalk models were trained using the gensim software (26).
4.1 QUANTITATIVE EXPERIMENT: POLITICAL BLOGS NETWORK
To address HI, illustrating Theorem 1 and the effect of MONET debiasing, we embed the effect of political ideology on blogger network (3). The political blog network has has 1,107 nodes corresponding to blog websites, 19,034 hyperlink edges between the blogs (after converting the graph to be undirected), and two clearly defined, equally sized communities of liberal and conservative
bloggers.
Methods and Design. In this experiment all graph neural network models were trained on 5 iterations across 80 random walks per node of length 40 with context window size 10 (MONET, was trained on 20 iterations and used negative samples per positive). Topology embeddings had dimension 16, and metadata embeddings had dimension 2. As one baseline, we use a random embedding generated from a 16-dimensional multivariate Normal. As our adversarial baseline, we apply the ideas introduced in (14) by adding 2-layer MLP adversary to the GloVe model, referred to as Glo Viadoerrrryy. The adversary is trained to predict political party from the topology embeddings (more detail given in Appendix A.4).
We measure embedding bias by the Macro-Fl score a linear SVM predicting political party from the embeddings, using LIBLINEAR implementation (7). For each embedding set, we compute the mcan and standard deviation Macro-F1 over 10 independent classification repetitions, each trained using half of the node labels sampled at random. To assess metadata information leakage, also track the metadata dimension importance matrix Σr == T.TT. recalling its interpretation from Section 3.
Results. Table T shows that the baselines Deep and GloVe are highly effective at predicting political party, and therefore biased. This is unsurprising, these methods are trained without metadata information, and were originally intended to encode low-dimensional structure like that present this data set. The bias in DeepWalk and Glo embeddings is further seen their metadata leakage values, computed using political party one-hot vectors as metadata embeddings.
Considering the embedding models with metadata embeddings, we find that, interestingly, Ve 's topology embeddings are still able to predict political party with 88.3% Macro-F1. Also, as predicted by Corollary 1, Glo 's metadata leakage remains (n)) This shows that simply concatenating metadata embeddings is not sufficient to isolate the metadata effect. In contrast, MONET& and MONET, achieve random Macro-F1 and no metadata leakage (under machine preci- sion), demonstrating that on this data, the MONET unit is necessary to debias the blog embeddings from political party. Surprisingly, the MONET-enhanneee random embeddings, reflecting the fact that even random embeddings will not be perfectly linearly de-correlated from any given sensitive attribute.
models show significantly less bias than
The contrast between Glo anete
is seen in two other ways. First, there is a noticeable increase in Er magnitude when MONET is used, implying that GloVemett metadata embeddings not capturing all possible metadata information. Second, seen in Fig. the 2-dimensional PCA plots of the GloVe embeddings still show political party separation, whereas the MONET & PCA dimensions reveal strong mixing.
In addition to the metrics in Table T we show additional metrics from this experiment in Appendix Table 3 In particular, that table contains results from a non-linear SVM applied all embeddings. Accuracy from that classifier is high even on MONET embeddings, which emphasizes the fact that MONET only performs linear debiasing. We also report wall times for each method, and the embdding pairwise distance correlation to the GloVe model. These metrics (respectively) show that the SVD correction does not add substantial runtime, and that does not overly corrupt the GloVe embedding signal.
Available within the Graph-Too software
22

---

Under review as a conference paper at ICLR 2020
Model
Fl (mean + std)
ΣT TiT. (mean = std)
MC
Random
53.23% =0.73% 95.59% +-007%
N/A
N/A 2743.9 + 36.7
DeepWalk
N/A
GloVe
95.94% +0.07%
N/A
6598.0 200.1
Glo Vadversaryy
81.46% +4.96%
N/A
4459.0 + 430.4
0.108 =0.006
-0.106 = 0.004
Glo VloVe
88.33% +0.60%
1827.6 289.7
-0.108 0.009
0.106 + 0.006
0.144+0.005
-0.140 0.007
DONET
48.60 % +0.50%
0.001 + 0.001
-0.14 + 0.06
0.140 0.006
0.180=0.006
MONETG
49.30 % +0.60%
0.018 + 0.002
0.181 0.008
0.179 + 0.006
Table 1: Macro-F1 scores from political blog network classifications using graph topology em- beddings only. MONET is successful in removing all metadata information from the topology embeddings the links in the graph are no longer effective predictor of political party. Comparison of the metadata transformation product Er between GloVemett and MONET shows MONET allows for considerably more metadata information learning. Finally, only MONET removes metadata leakage to precision error (recall MC() a Frobenius norm).
Farty on GloVe PCA
Party on Glove meto PCA Topology Embeedsings.
Party on MONETIGIOVe meta) PCA Topology Embeddlings
(a)
(b)
(c)
Figure 3: PCA of political blog graph embeddings. (a): Party separation clearly visible stan-
(b): Party separation reduces when Glo GloVemeta captures some metadata information. (c): Party separation disappears with MONET orthogonalized training.
dard GloVe embeddings.
Model
Manipulated Items in Top-20
Embedding Distance
(mean dev)
Correlation w/GloVe
DeepWalk GloVe
9.9 + 0.40
0.385 + 0.005
9.8 + 0.76
1.000 + 0.000
GloVe
9.8 + 0.476
0.852 0.002
NLP Debiasing (27 4 (sum)
8.1
0.566 + 0.004
NLP Debiasing 27 (max)
4.9 3.4
0.990 + 0.003
MONET MONET
5.7 = 2.0
0.560 + 0.055
1.2 - 1.7
0.831 0.004
Table 2: Results from the shilling attack experiment. Attackers attempt to insert 10 items in the top-20 recommendations a target video. The results show that MONET can best mitigate the effect of an attack under incomplete information. We note that there is an implicit trade-off between debiasing and maintaining correlation with the original (biased) embeddings.
4.2 EXPERIMENT 2: THWARTING ATTACKS ON GRAPH-BASED RECOMMENDATION SYSTEMS
In this experiment we address H2, investigating the effectiveness of MONET to defend against a shilling attack (9) against graph-embedding based recommender systems (33). In shilling attack, number of users act together to artificially increase the likelihood that a particular influenced item will be recommended for particular target item.
7

---

Under review as a conference paper at ICLR 2020
Data. In single repetition of this experiment, we inject artificial shilling attack into the MovieLenn 100k datase The raw data is represented as a bipartite graph with 943 users, 1682 items, and a total of 100,000 ratings (edges). Each user has rated at least 20 items. At random, we sample 10 items into an influence set Sj, and a target item i, to be attacked. We take a random sample of 5% of the existing users to be the set of attackers, SA- We then create a new graph, Gattaked which in addition to all the existing ratings, contains new ratings from each attacker E SA to each item E SJ as well the target video. (Note that this corresponds several varieties of behavior including both incentivizing formerly good users, and account takeover.)
Design and Methods. For each embedding method, we perform random walks through the new bipartite graph Gatucked As we wish to study item recommendation, in the random walks, we simply remove user nodes each time they are visited (so the walks contain only pairwise co-occurrence information over items). With any given network emhedding, we measure its bias by the number of influence items Sy in top-20 models to know the per-movie attacker rating count for each attacked movie. However, to better demonstrate real-world performance, we only allow 50% (randomly sampled) attackers from the original 5% sample to be "'nnwnn" when constructing these metadata. As non-debiasing baselines, compare against DeepWalk and Glove. As debiasing baselines, we applied generalized correlation removal framework developed for removing word embedding bias (27 4 Specifically, approaches to "debias" the Glo embedding of the Moviel.nns graph - as the "gender" embedding direction, we tried both (a) the most attacked movie vector and (b) the sum of attacked movie vectors. All methods use 128 dimensional topology embeddings and are trained on 100 random walks per node, each walk of length 5.
list of i,. As metadata, we allow MONET
tried two
As seen in Table 2 the topology embeddings from MONET are the least biased by a large margin, letting on average only 1.2 influence items in the top-20 neighbors t,. Interestingly, we note that this behavior occurs even though the majority of observed co- co-occurrences for the algorithm had nothing to do with the attack in question, and only the known 50% of attackers were used to construct the metadata. MONET,, D had comparably less efficacy in this experiment. We speculate that this is due to harmful effect of negative sampling on the learning of the metadata direction from the continuous attacker metadata- which would affect MONET's s ability to debias the Deep Walk embeddings. Further research could investigate appropriate hyperparameter settings for MONET p in this case.
Results.
All other baselines (including those that explicitly model the attacker metadata) left at least around half of the attacked items in the top-20 list. To measure the extent to which debiased embeddings retain the original recommendation signal, we compute the pair-wise embedding distances of each method, and compute their Pearson correlation to the standard Glo Ve embeddings. We find that MONET embedding distances achieve high correlation (0.83) to the original distances, showing that with MONET it is possible nearly nullify a shilling attack while preserving most of the signal from the true, un-attacked ratings. We note that the www--attck-embeedee distance correlation, but this method let many more attacked items (on average) into higher ranks. This reveals trade-off between embedding debiasing and prediction efficacy which has also been observed in other contexts 33
baseline higher embedding
5 RELATED WORK
Though graph learning is an immense field, a minority of unsupervised graph embedding techniques involve graph metadata. To our knowledge, none of these techniques involve either metadata orthogo- nalization or the capacity to learn arbitrary metadata transformations. (36) is a matrix factorization approach which
shared node embedding matrix to factor both the graph adjacencies and the raw metadata in a joint loss, with a tunable parameter to control the influence of the metadata loss. Similarly. (T8) pre-computes a metadata similarity matrix and trains shared center-context embedding matrices on the metadata similarities and random walk similarities. In contrast, we learn the direction and effect of metadata as neural network parameters, and we separate those parameters into unique embedding dimensions. (31) and (35) are matrix factorization approaches which factor an approximation to the co-occurrence matrix into equally-size sized metadata and topology embeddings. and were built mainly for text metadata. Their approaches enforce metric space similarity and
Available: http://:hhhissssooprraar.r.rrrrr
100k/
8

---

Under review as a conference paper at ICLR 2020
dimensional homogeneity between metadata and topology representations, restrictions that we do
not rely on and are ill-suited to the setting with multiple types of urbitrarily-sized metadata. (16)
constructs random walks that traverse between the original graph and the metadata freely, approach which runs counter to our ability to separate out the effects of metadata on graph adjacencies. (20)
introduce version of the stochastic block model with metadata priors, and show that the estimated posteriors yield insight into the influence of metadata on the graph. However, this model estimates a community partition and in/out-community probabilities it does not yield embeddings either of the node topology or the node metadata. There has been work in Natural Language Processing on removing gender bias from word embeddings (e.g. 4 but these methods operate with pre-computed embeddings and rely on identification of gendered terminology.
Additionally; there has been a wealth of work studying semi-supervised learning with graphs (e.g. 32) and graph convolutional networks (e.g.2) [7 which use graph metadata as features. While most semi-supervised and supervised neural networks for graphs indirectly produce embeddings that in some cases can be identified with feature and topology dimensions, they are trained as part of prediction or label propagation tasks, Therefore, the topology embeddings are free to correlate with features to the extent that this serves the loss function there is no explicit separation of topology and metadata dimensions. In this paper, we have studied the benefits of metadata orthogonalization in the unsupervised setting, and we leave the exploration of our techniques in the semi-supervised and supervised settings to future work.
As described at the end of Section 3, there are many approaches to data representation learning that use adversarial networks to produce attribute-invariant embeddings. For instance, (30) and (33 use an adversary to allow feature embeddings to forget differences in data sources. Similar techniques have been applied to debias word embeddings from gender information (34) and recommender graph embeddings from demographic information (5). MONET differs from these approaches in few key and consequential ways. First, (to our knowledge) none apply out-of-the-boo to the unsupervised setting, which motivated our introduction of a baseline adversarial version of Glo Second, whereas MONET can accept any metadata in an appropriate design matrix M, different types metadata require different adversary losses, which can require cumbersome tuning. Third, adversarial approaches induce trade-off between accuracy the main task and debiasing. In contrast, our work aims to minimize training error subject to perfect (linear) debiasing.
6 CONCLUSION
In this work, we have shown that unsupervised training of graph embeddings induces bias from important graph metadata. We proposed a novel solution to address this problem the Metadata- Orthogonal Node Embedding Training (MONET) unit. The MONET unit is the first graph learning technique for training-time debiasing of embeddings, using orthogonalization. Our experimental results using real datasets showed that MONET is able to encode the effect of graph metadata in isolated embedding dimensions, and simultaneously remove the effect from other dimensions. This has immediate practical applications, which we illustrate by mitigating a simulated shilling attack on real dataset of movie ratings.
We note that, because MONET only performs linear debiasing, the method is simply a first step in this area, and does not completely solve the problem of exact metadata independence. That being said, we argue that this is not major limitation for many practical uses. As we show in the shilling attack experiment, MONET seems to greatly reduce bias when embeddings are used for simple nearest- neighbor nearest-neighhor lookups, which is common application in graph-based recommender systems. Furthermore, advanced non-linean classifiers are not always scalable to graphs commonly found in industrial applications.
This work was meant to introduce the basic principles underlying the need for the MONET technique, and show its utility in shallow graph neural network (G). While we used a shallow network for instructional purposes, we note that MONET is generalizable, and MONET units can be used to debias any set of embeddings from another set during training. Subsequent research can explore the use of MONET in deeper networks and potentially semi-supereised models or graph convolutional networks. As MONET's SVD calculation dimensions, future research could be in assessing the effect of SVD approximations, or training algorithms that utilize caching of previous metadata embedding SVDs to speed up training.
be expensive with large graphs and large embedding

---

Under review as a conference paper at ICLR 2020
REFERENCES
[1] M. Abadi, P. Barham, J. Chen, Z. Chen, A. Davis, J. Dean, M. Devin, S. Ghemawat, G. Irving, M. Isard, al. Tensorflow: system for large-scale machine learning. In 12th {USENIX) Symposium Operating Systems Design and Implementation ({OSDI) 16), pages 265-283, 2016.
[2] S. Abu-El-Haija, B. Perozzi, A. Kapoor, H. Harutyunyan, N. Alipourfard, K. Lerman, G. V. Steeg, and A. Galstyan. Mixhop: Higher-order graph convolution architectures via sparsified neighborhood mixing. arXiv preprint arXiv: 1905.00067, 2019.
[3] L. A. Adamic and N. Glance. The political blogosphere and the 2004 us election: divided they blog. In Proceedings the 3rd international workshop Link discovery, pages 36-43, ACM, 2005.
[4] T. Bolukbasi, K.-W. Chang, Y. Zou, V. Saligrama, and A. T. Kalai. Man is computer programmer as woman is to homemaker? debiasing word embeddings. In Advances in neural information processing systems, pages 3349-4357, 2016.
[5] A. J. Bose and W. L. Hamilton. Compositional fairness constraints for graph embeddings. Proceedings of the 36th International Conference on Machine Learning. 2019.
[6] R. Brochier, A. Guille, and J. Velcin. Global vectors for node representations. arXiv preprint 1rXiv:1902.11004 2019.
[7] C.-C. Chang and C.-J. Lin. Libsvm: A library for support vector machines. ACM transactions on intelligent systems and technology (TIST), 2(3):27, 2011.
[8] H. Chen, B. Perozzi, R. Al-Rfou, and S. Skiena. A tutorial network embeddings. arXiv preprint arXiv: 1808. 02590, 2018.
[9] P.-A. Chirita, W. Nejdl, and C. Zamfir. Preventing shilling attacks in online recommender systems. In Proceedings of the 7th Annual ACM International Workshop on Web Information and Data Management, WIDM '05, pages 67-74, New York, NY, USA, 2005, ACM. ISBN 1-59593- 194-5. doi: 10. 00.114//099704411007666 URL http: //tp::://oi..o acm. org/10. 1097047 1097061
[10] Cui, X. Wang, J. Pei, and W. Zhu, A survey on network embedding. IEEE Transactions on Knowledge and Data Engineering, 2018.
[11] M. Defferrard, X. Bresson, and P. Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in neural information processing systems, pages 3844-3852, 2016.
[12] Duchi, E. Hazan, and Y. Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 120u)):2121-2159, 2011.
[13] Y. Ganin, Ustinova, H. Ajakan, Germain, H. Larochelle, Laviolette, M. Marchand, and V. Lempitsky. Comain-adversane training of neural networks. The Journal of Machine Learning Research, 17(1):2096- 2030, 2016.
[14] I. Goodfellow, J. Pouget- Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Bengio. Generative adversarial nets. In Advances neural information processing systems, pages 2672-2680, 2014.
[15] A. Grover and Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference Knowledge discovery and data mining, pages 855-864, ACM, 2016.
[16] J. Guo, L. Xu, X. Huang, and E. Chen. Enhancing network embedding with auxiliary informa- tion: An explicit matrix factorization perspective. In International Conference on Database Systems for Advanced Applications, pages 3-19. Springer, 2018
10

---

Under review as a conference paper at ICLR 2020
[17] T.N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. International Conference on Learning Representations, 2017. URU/attass//opeeeeeieer
net/ htt.//ouummdd=sSSAay/2.
[18] C. S. Wang. D. Yang. Z. Li, Y. Yang, X. Zhang, and Zhou. Ppne: work embedding. In International Conference Database Systems for Advanced Applications, pages 163-179. Springer, 2017.
property preserving net-
[19] T. Mikolov, I. Sutskever, K. Chen, S. Corrado, and J. Dean. Distributed representations of words and phrases and their compositionality. In Advances in neural information processing systems, pages 3111 3111-3119, 2013.
[20] M. E. Newman and A. Clauset. Structure and inference in annotated networks. Nature commurications, 7:1 1863, 2016.
[21] L. Peel, D. B. Larremore, and A. Clauset. The ground truth about metadata and community detection in networks. Science advances, 3()):e1602548, 2017.
[22] T. P. Peixoto. The graph-tool python library. figshare, 2014. doi: 10.6084/m9 figsteii...hiiiiico 164194. URL.ttp::/ ht//ffgghhaa. com/ art ctapaaiiaoeeegaaapaooooo/o///
[23] J. Pennington, R. Socher, and C. Manning. Glove: Global vectors for word representation. In Proceedings of the 2014 conference empirical methods in natural language processing (EMNLP), pages 1532-1543, 2014.
[24] B. Perozzi, R. Al-Rfou, and S. Skiena. Deepwalk: Online learning of social representations, In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 701-710. ACM, 2014.
[25] Qiu, Y. Dong, H. Ma, J. Li, K. Wang, and Tang. Network embedding as matrix factorization: Unifying deepwalk, line, pte, and node2vec. In Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, pages 459-467. ACM, 2018
[26] R. Rehüřek and P. Sojka. Software Framework for Topic Modelling with Large Corpora. In Proceedings of the LREC 2010 Workshop on New Challenges for NLP Frameworks, pages 45-50, Valletta, Malta, May 2010. ELRA. http:// muni c2 wttp:///wwwpacnnnnnaaeeeeeeeeeee
[27] B. Schmidt. Rejecting the gender binary: vector-space operation. Ben's Bookworm Blog, 2015.
[28] J. Tang, M. Qu, M. Wang, M. Zhang, J. Yan, and Q. Mei. Line: Large-scale information network embedding. In Proceedings of the 24th international conference on world wide web, pages 1067-1077. International World Wide Web Conferences Steering Committee, 2015.
[29] L. N. Trefethen and D. Bau III. Numerical linear algebra, volume 50. Siam, 1997.
[30] E. Tzeng, J. Hoffman, K. Saenko, and T. Darrell. Adversarial discriminative domain adaptation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 7167-7176, 2017.
[31] C. Yang, Z. Liu, D. Zhao, M. Sun, and E. Chang. Network representation learning with rich text information. In Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015.
[32] Z. Yang. W. W. Cohen, and R. Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. In Proceedings of the 33rd International Conference International Conference on Machine Learning Volume 48, ICML' 16, pages 40-48. JMLR.org. 2016. URL http://dl acm. org/ citation...... cfm? 2ttmmmid=3004 1e11==33033998 3045396
[33] R. Ying, R. He, K. Chen, P. Eksombatchai, W. L. Hamilton, and J. Leskovec. Graph convolu- tional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 974-983. ACM, 2018
11

---

Under review as a conference paper at ICLR 2020
[34] B. H. Zhang, B. Lemoine, and M. Mitchell. Mitigating unwanted biases with adversarial learning. In Proceedings of the 2018 AAAI/ACM Conference on Al, Ethics, and Society, pages 335-340. ACM, 2018.
[35] D. Zhang. J. Yin, X. Zhu, and C. Zhang. Homophily, structure, and content augmented network representation learning. In 2016 IEEE 16th International Conference on Data Mining (ICDM), pages 609-618, IEEE, 2016.
[36] S. Zhu, K. Yu, Y. Chi, and Y. Gong, Combining content and link for classification using matrix factorization. In Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, pages 487-494. ACM, 2007.
A APPENDIX
Proposition Under the assumptions of Theorem I, we have
6w (f. = [EM - Er) + Im]3.
(6)
Proof. Derivatives of Glo GloVe mento yield that the i-th row of 5w (i, is d,y W where
di 1, w?? W; - a; - aj
= θ + Z- W W, 0: aj.
Similarly the j-th row is d,j WT, and all other rows are zero vectors. Hence
Biz" 6w (i. - -, 3,
We derive the second term on the right- side of Equation X the first term follows by symmetry. Note first that (Z
b by independence and centering assumptions. Second:
BiZW? W, w7] = T N"M
=T" Bow la = = T TToowll ImB
by independence. Third:
2| = TT TMT
= TT (E(MM)F) TT (B(GWTT) = T ErB
by independence, and similarly E| 2, W = T Enr Ep Combining these with Equation 7 we have
E [ = T [E Ex) o. Ta] B.
Applying symmetry to the second term in Equation 8 completes the proof.
A.1 PROOF THEOREM 1
Proof.
Proposition I gives E[ (i,j)
2T [2 ET) + -ow 8. Second, note that Recalling that W"
E[M,WT] = =B- = MTW = n. and thus zw = TTT NTW = nI
W + Sw (1. have
E
W' T
2 E - Er) + (n ow Im]] 18
Applying Jensen's Inequality completes the proof.
A.2 PROOF OF THEOREM 2
Proof. Consider metadata embeddings Z Roxdz and, in the MONET algorithm, define the
projection Pz = läz - QzQZ, where Qz are the left-singular vectors of Z. By properties of the SVD. 2T Q = Zr. and hence zT Pz = Onxdz- This means that ZTW = 2d 8 = = O x which completes the proof by definition of metadata leakage.
12

---

Under review as a conference paper at ICLR 2020
Model
Wall Time (sec)
SVM Accuracy
Embedding Distance Correlation w/GloVe
Random
N/A
0.527 = 0.000
0,004 0.001
DeepWalk
48.562 + 0.579
0.896 + 0.000
0.630 + 0.006
GloVe
48.48747.220
0.948 0.000
1,000 0.000
Glo GloVeadvessary
162.575 7.042
0.549 0.018
0.432 + 0.02
Glo Vemeto
102.387 7.595
0.906
0,862 0.020
DONET
595.477 = 29.66
0.796 + 0.032
0.035 + 0.005
MONETG
112.505 = 7.156
0.899 + 0.000
0.334 0.017
Table 3: Additional metrics from the political blogs experiment. Wall time is the user wait time during won-linear SVM with an RBF kernel. Embedding
training. SVM Accuracy is the accuracy Distance Correlation with Glo Ve is the Pearson correlation of the pairwise embedding distances between each of embeddings and GloVe embeddings.
A.3 DESCRIPTION OF DONET MONET IMPLEMENTED IN DEEPWALK
The implementation of MONET follows the general procedure laid out in Algorithm T MONET,, for DeepWalk the MONET unit adds feed-forward transformation of the metadata the graph representation, resulting in metadata embeddings X and Y (see Eq., 3}. Z X + Y gives the combined metadata representation, used to debias U and V via Pz (see Algorithm and surrounding description). MONET does not affect the negative sampling component of DeepWalk's
As with
Walk's ' loss (Eq. B). MONET debiases the topology embeddings as described, which are then used throughout the standard DeepWalk Walk model (along with the metadata embeddings).
A.4 ADVERSARIAL BASELINE
As our adversarial baseline, we implemented a 2-layer MI.P discriminator following the framework of (14). The MLP had ReLU activations and an 8 dimensional hidden layer. The MLP was trained to predict political party from the topology vectors each batch of input nodes, using cross-entrops loss (discriminator task). Then, the topology vectors were fed through the discriminators, but their negative logits were used for prediction (topology task). The discrimnator task and topology task evaluated and optimized after each optimization of the GloVe loss.
A.5 ADDITIONAL RESULTS FROM POLITICAL BLOGS EXPERIMENT
In Table 3
we give the following additional metrics computed from the political blogs experiment, averaged over thirty repetitions:
1. Wall Time (sec): user wait time in seconds from the beginning to end of each method. The significant increase seen from MONET D is due to DeepWalk's 's negative sampling loss.
2. SVM Accuracy: emphasize the fact that MONET only performs linear debiasing, trained a non-linear SVM with an RBF kernel using a randomly-chosen 50% of the nodes as training points.
3. Embedding Distance Correlation Ve: This metric was also used in the shilling experiment. In our experiments, GloVemeta and MONET were implemented into the GloVe model, we the correlation between the pairwise embedding distances between MONET models and GloVe to measure the amount that metadata embedding and SVD cor- rection has "corrupted" the embeddings. As the results show, among non-random methods, MONET; and MONET p are most corrupted. This is because most of the community signal in the political blogs network is due to the political affiliation attribute, and MONET models explicitly removes linear correlation with that attribute. That said, we see that MONET models still preserve a statistically significant amount of signal from the GloVe embeddings above the random baseline.
Additionally, we perform a variant of the political blogs experiment to test the inductive performance of MONET. Specifically,
aim to answer the question: if some nodes are not used to train the MONET model, can we still use the MONET model to debias other embeddings for those nodes? Given subset of nodes Na, train MONET model the induced subgraph G2 G(Na). We then attempt to debias the DeepWalk embeddings of held-out nodes N₂, := \ N₂, To do this, we apply the MONET metadata transformation Ti, T2, trained on Ga. the metadata of Ng. This yields
13

---

Under review as a conference paper at ICLR 2020
inductive metadata embeddings Z₁ for the nodes N6- We then apply the de- de-biasing projection given in Algorithm to the DeepWalk embeddings for Ng. and compute the linear SVM Macro/Micro-F) scores measure embddings bias.
Figure f shows the average Macro/Micro-FI over 5 repetitions per proportion of held-out nodes. For reference, also give the accuracy scores for the un-corrected DeepWalk embeddings for Ng. Note that the linear SVM was trained on a 50% training-test split across N₂ only. We find that the MONET transformation learned from the given nodes able properly generalize to and debias the new data
Na.
1.0
1.0
0.9
0.9
0.8
0.8
MacroF1
MicroF1
0.7
0.7
Embedding
Embedding
Biased (DeepWalk)
Biased (DeepWalk)
0.6
De bieseeedd (MONET G)
0.6
-e-ibideed (MONET. ())
0.5
0.5
0.4
04
Missing Data Proportion
Missing Data Proportion
Figure 4: Macro/Micro-Fil scores from linear SVM classifier, trained on "held-out" node embed-
dings from both DeepWalk and inductive MONET.
14


Reviews:
[{"review_id": "S1lWDbG0FH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper presents an approach to debiasing graph embeddings from known, given node attributes/metadata.\nSpecifically, the paper proposes to learn an embedding that is orthogonal to given node attributes, ensuring that there is no *linear* function which can extract the node attributes from the learned embedding.\n\n\nStrength:\n-\tThe paper addresses an interesting and relevant problem on debiasing graph embeddings.\n-\tThe paper presents a, to my knowledge, novel approach, to avoid the leakage of meta-data in the embedding, effectively debiasing it from this information (although some discussion of prior should be addressed, see below)\n-\tThe paper shows that the approach is effective compared to two baselines on two datasets (although some aspects of the experiments can be improved, see below)\n\nWeaknesses:\n1.\tExperimental evaluation:\n1.1.\tThe paper only evaluates on the training set. Specifically, in experiment 1, the paper learns an embedding and supervises it to be orthogonal to given labels; this is good, but it also somewhat expected that this could be learned when tested on the same dataset. An important question is, if the model actually learned a generalizable embedding or just overfit to the training set. If the learned embedding is applied to new data, is it still not possible to extract political affiliation from it?\nI would suggest splitting the dataset in two part: One part to train the debiased embedding and one to train and test the Linear SVM.\n1.2.\tIt would be great if the authors describe better and quantify how they ensure in experiment 1 that the learned embedding of the MONET model is measured, and how this compares to the three baselines (e.g. a random or constant embedding would also be perfectly debiased).\n1.3.\tWhile the paper clearly states that the approach is restricted to linear relationships, it would be interesting to look at non-linear classifiers and see how well this works in practice, also in comparison to the baselines.\n1.4.\tFigure 3(c) visualizes that \n2.\tRelated work:\n2.1.\tThe comparison to related work could be improved. Specifically, a discussion relating this work to adversarial training, e.g. as in domain confusion networks [A] or in [5].\n2.2.\tThe authors argue that [5] is independent/concurrent work. I agree with the authors that [5] is sufficiently different to this work, but it should be discussed thoroughly as it has been published at ICML 2019. Unfortunately, the authors also miss to include in the references that it has been published at ICML 2019.\n\n\nWhile the paper explores an interesting direction and approach, there are several concerns which speak against acceptance (see Weaknesses above); however, I believe they can be a addressed/clarified in a further revision.\n\n\nReferences:\n[A] Tzeng et al, Adversarial Discriminative Domain Adaptation, CVPR 2017\n\n\n=== Post author response\nI thank the authors for their response and additions as well as clarifications.\n\nI agree to other reviewers, that the limitation to linear de-biasing is a concern for the paper, but the authors have clarified it now in the abstract an other locations; the additional experiments with and RBF kernel have shown that  indeed the formulation only does mainly do linear decorrelation. \n\nTable 3 could be further clarified (what is the goal? 50% accuracy, i.e. chance level?) and made more similar to Table 1, or ideally merged with it. \n\nIt is also a bit unfortunate that all this additions are in supplement and not merged in the main paper.\n\nOverall I still lean more towards accept.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Bye6Jh_TFB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: The paper introduces a GNN model (MONET) for debiasing graph embeddings, by enforcing orthogonality between the embedding spaces of the graph topology & the graph metadata. They show that unsupervised learning induces bias from important graph metadata, when the metadata is correlated with the node edges. They show experimental results on real world graphs (political blogs network & graph-based recommendation systems), where MONET can debias  graph embeddings and prevent metadata leakage.\n\nDecision: Accept\n\nReasons for the decision: The paper is clearly written, well-motivated, and well-organized. The proposed algorithm and analysis seem insightful & novel, and the experimental results (showing that MONET can debias metadata from topology) are convincing.\n\nAdditional Feedback:\n\n1) It would be helpful to show results on at least one other graph embedding model other than GloVe, to empirically substantiate the claim that MONET is “broadly generalizable”.\n\n2) In Section 3.4 [Algorithmic Complexity], it would be helpful to compare the wall clock time of MONET vs. the baselines (DeepWalk, GloVe), to give a better sense of how expensive the SVD calculation is.\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "Bke4vIkIcr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "TLDR: split node embeddings into medatadata and graph structure, force them to be orthogonal.\n\nThe paper proposes to split node embeddings in a graph into two parts:\n1. graph structure embeddings: Es\n2. known node metadata embeddings: Em\nTo prevent Es from containing information about Em, the authors propose a scheme which puts Es into the Nullspace of Em through repeated SVD factorizations. This prevents linear classifiers that operate on Es to reliably predict information in Em.\n\nThe weakness of the paper stems from the proposed definition of debiasing. Just like two random variables can be dependent, but have a linear correlation coefficient of 0, in the proposed method the two embeddings may be linearly unrelated, but have a strong non-linear relationship.\n\nThis is an important caveat that should be highlighted in the papers' abstract, not burried deep on p4, under Theorem 2. \n\nIn fact, looking at Fig 3c information about party affiliation follows a XOR-like pattern in the PCA space. This means that a linear classifier will fail (indeed the linear SVM in Table 1 fails), but a non-linear one should work OK. Thus, contrary to the abstract, the proposed method doesn't remove the effect of arbitrary covariates, but removes a LINEAR dependence. \n\nThus the paper proposes to solve an important problem and proposes a partial solution, but overstates the results in the abstract and hides the true efficiency of the method.\n\nAction items ot correct the paper:\n- be more honest about the true result. Decorrelation does not imply independence.\n- redo Table 1 with strong non-linear classifiers such a Gaussian SVM or Random Forest to show how much is not filtered out by your linear decorrelation method\n\nFinally, contrast with the adversarial information removal [1] and  the information bottleneck [2], both of which also promise to remove non-linear dependencies. It may happen that the you method works better, even though it only guarantees no linear dependencies.\n\n[1] https://arxiv.org/abs/1505.07818\n[2] D. Moyer, S. Gao, R. Brekelmans, A. Galstyan, and G. Ver Steeg, “Invariant Representations without Adversarial Training,” in Advances in Neural Information Processing Systems 31, 2018\n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work presents a method for debiasing graph embeddings. The main concerns for the work were originally identified by Reviewer 3, who pointed out that the method is only capable of linear debiasing. Authors responded by updating the manuscript in several places to mention this limitation as well as adding Table 3 to the Appendix showing that SVM's with non-linear kernels are still able to identify bias in the embeddings. Reviewers agreed that this addition improved the manuscript, however some reviewers still had concerns about the revised manuscript. This AC has several recommendations for improving the paper. First additional revision is needed to better address the limitations of linear debiasing, for example Table 1 still reads "MONET is successful in removing all metadata information from the topology embeddings – the links in the graph are no longer an effective predictor of political party".  Statements like this are a bit misleading, as the embeddings will still be biased with respect to a non-linear classifiers (as evident by Table 3). Additionally, updating Table 1 and related experiments to measure embedding bias with respect to non-linear classifiers would help clarify the limitations for perspective readers. Second, the paper should be updated to address remaining concerns that the linear debiasing assumption limits the applicability of the method. One could either discuss or demonstrate additional applications of the method that work even with the linear assumption, extend MONET so it can improve model bias with respect to non-linear classifiers, or show that MONET still outperforms baselines when the non-linear assumption is violated.
Decision: Reject