Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: TLDR: split node embeddings into medatadata and graph structure, force them to be orthogonal.

The paper proposes to split node embeddings in a graph into two parts:
1. graph structure embeddings: Es
2. known node metadata embeddings: Em
To 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.

The 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.

This is an important caveat that should be highlighted in the papers' abstract, not burried deep on p4, under Theorem 2. 

In 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. 

Thus 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.

Action items ot correct the paper:
- be more honest about the true result. Decorrelation does not imply independence.
- 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

Finally, 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.

[1] https://arxiv.org/abs/1505.07818
[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


review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: The paper presents an approach to debiasing graph embeddings from known, given node attributes/metadata.
Specifically, 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.


Strength:
-	The paper addresses an interesting and relevant problem on debiasing graph embeddings.
-	The 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)
-	The 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)

Weaknesses:
1.	Experimental evaluation:
1.1.	The 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?
I would suggest splitting the dataset in two part: One part to train the debiased embedding and one to train and test the Linear SVM.
1.2.	It 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).
1.3.	While 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.
1.4.	Figure 3(c) visualizes that 
2.	Related work:
2.1.	The 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].
2.2.	The 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.


While 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.


References:
[A] Tzeng et al, Adversarial Discriminative Domain Adaptation, CVPR 2017


=== Post author response
I thank the authors for their response and additions as well as clarifications.

I 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. 

Table 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. 

It is also a bit unfortunate that all this additions are in supplement and not merged in the main paper.

Overall I still lean more towards accept.
review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: 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.

Decision: Accept

Reasons 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.

Additional Feedback:

1) 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”.

2) 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.

review_title: Official Blind Review #1

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