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, standard GNNs 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 generalizable neural network architecture for performing training-time 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 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.
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.