Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: In this paper, the authors emphasize the limitations of node representation learning methods that are based on random walks and how these random walks are biased from the connectivity in the graph. Nodes with high degree are the minority in such graphs, however they end up appearing often in the random walks. The authors propose a method that can be used as a component in existing methods in order to debias the various structural biases in graphs. The proposed method is utilizing the degree-corrected stochastic block model (dcSBM), that is partitioning nodes into groups and randomizes edges while preserving the degree of each node and the number of inter/intra group edges. They conduct experiment to test the proposed method against six state of the art models and some variations in the link prediction and community detection tasks. The results show that the proposed model outperforms the other in most cases. They also analyse their findings in a case study where they study a journal citation graph.

-- I acknowledge that I have read the authors' response and the other reviews.
main_review: The paper is well-written, well-structured and easy to follow. It is around a fair observation in the high degree of rare nodes in graphs that influence a lot the random walks that are widely used during node representation learning. The idea and the proposed solution are simple, but can be used in a lot of existing methods to improve their performance and decrease the bias. The authors justify their choices for the proposed solution by citing the corresponding works. The experimental setup looks very good and they conduct a number of experiments using different downstream tasks (link prediction, community detection) and various datasets to show the improvements in the performance of the compared methods. Figure 4 is also very compact and offers a lot of information for the analysis of the results.
limitations_and_societal_impact: The authors discuss the limitations of this work in the paper, and there are no concerns risen for potential negative societal impact of this paper. They have also included a broad impact section, where they discuss the benefits of their proposed method and findings in node representation learning applications, to avoid biases when learning the embeddings.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This paper mainly investigates the impact of bias originating from random walk on graph embedding. To handle the bias, the authors propose a model named residual2vec, based on the paradigm of skip-gram, for structurally fair node representation learning on graph. Experiments on several datasets demonstrate the effectiveness of the proposed model.
main_review: Fairness or bias learning is a hot topic in the machine learning community, which deserves wide and deep investigation. However, several concerns in this paper should be well-addressed by the authors.

1. This paper investigates fair representation learning in a random walk based paradigm. However, the related work is not sufficiently introduced, and several recent studies [1,2,3,4] also consider this problem, which are not cited and compared by the authors. For example, role2vec [2] considers the node degree as (one of) the role(s) of each node for better node representations, and Fairwalk consider more fair random walk to boost the fairness of the learned node embeddings.

2. In the Introduction, the motivation is not so clear: why the debiasing of random walk based models can improve their performance? What is the benefit of the debiasing to node embedding?

3. In Sect-3.1, the illustration of null graph is not clear. More details are needed to depict the usage of null graph. Besides, it is the same case for dcSBM, which is not clearly illustrated, either.

4. In experiments, the baselines are not sufficient, some recent approaches such as [1,2,3,4] should be imported for comparison. Besides, it is better to employ GAT [5] as a baseline, since it can usually achieve better performance than GCN.
For link prediction, the proposed residual2vec performs worse than Glove on 3/6 datasets, thus the performance of the proposed model seems not good enough. No analysis is given.


Overall, this paper focuses on an old research problem, the skipgram-based node representation learning. Furthermore, I think the contribution of this paper is limited, and the proposed model is incremental to some extent, which cannot catch the standard of this conference.


[1] DEMO-Net: Degree-specific Graph Neural Networks for Node and Graph Classification. KDD 2019.  
[2] Role-based Graph Embeddings. TKDE 2020.  
[3] Fairwalk: Towards Fair Graph Embedding. IJCAI 2019.  
[4] Investigating and Mitigating Degree-Related Biases in Graph Convolutional Networks. CIKM 2020.  
[5] Graph Attention Networks. ICLR 2018.
limitations_and_societal_impact: Please see the Main Review.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper introduces a graph embedding method that claims to debias structural biases in graphs by using random graphs called residual2vec. The work investigates that the standard random walk-based embedding methods have implicit bias due to the friendship paradox I.e., it is more likely that the dense node (node with many neighbors) is visited more frequently in the random walk. The authors performed experiments on residual2vec model for link prediction and community detection tasks. The work shows that the biases from the random walk overshadow the important features of graphs and that debiasing models the structural properties in the embeddings and improves the performance in the tasks. Baselines from variants of graph embedding methods have been considered in the experiments. Six datasets are taken for link prediction and one benchmark dataset is taken for the community detection task. Additional experiments on the directed citation graph and the sensitivity to the dimension of node features are provided in the supplementary. 
main_review: Strengths: 

1. The idea of considering random graphs to debias the learned embedding is interesting and intuitive as the random graphs can make the learning more robust. 
2. Paper is explained properly with clear notations. 
3. To the best of my knowledge, there hasn't been much work on debiasing graph embeddings. So, this can be a good contribution to the area. 
4. Empirical evaluation of two tasks with interesting experiments is performed in the main paper and supplementary. 
5. This seems to be a generalized method of debiasing the learning curve for any random walk-based graph embedding method. 

Weaknesses: 

1. The novelty of the paper is somewhat limited. Moreover, since the key contribution is using random graph models, authors should do an ablation study on how it compares to other choices of random graph models, under the same framework. 
2. Contributions are not clearly listed anywhere in the paper. 
3. I find the idea interesting. However, I do not see consistency in the improvement of results. Only in the case of the journal citation graph, I see notable improvements. In Figure 3, we can see that Glove is consistently performing better. Even embedding visualizations are not helping in making clear distinctions. 
4. What would be the complexity of truncated R as the matrix is large (NxN)? 
5. No overall complexity analysis is provided. If N is large, then, even the SVD is computationally expensive. 
6. What about the existing work on debiasing GNNs? None of the papers are cited. No mention of how this work is different from those and no comparison is made with those works. 
[1] DEBIASED GRAPH NEURAL NETWORKS WITH AGNOSTIC LABEL SELECTION BIAS 
[2] Say no to the Discrimination: Learning Fair Graph Neural Networks with Limited Sensitive Attribute Information 
[3] MONET: DEBIASING GRAPH EMBEDDINGS VIA THE METADATA-ORTHOGONAL TRAINING UNIT 
[4] Debiasing Graph Representations via Metadata-Orthogonal Training 
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: A lot of machine learning models use random walks to create "context" for the nodes in the graph. However, some random walk methods have biases towards high degree nodes. Thus, starting the random walk from some node, the random walk might be drawn quickly to high degree nodes. The authors propose a new model for de-biasing node embedding methods from the biases of random walks. They solve the issue by changing the definition of the conditional probabilities that are fit to the data. They draw a relation between Noise Contrastive Estimation and Negative Sampling, and they show that using the latter, one can clearly understand the role of the noise probability $p_0$ in the SGNS word2vec model. Then they define the $p_0$ using random graphs with the goal to de-bias the model.
main_review: I like the idea. It is clean and simple and it also seems perpendicular to existing approaches for node embeddings. I also like the motivation from NCE to NS. I have currently voted for rejection for the following reasons.

Major comments

1) The idea that traditional random walks are biased towards high degree nodes (depending on the structure of the given graph) is true. However, it is an archaic idea at the same time. The problem of high degree nodes has been solved by approximate personalized PageRank vectors that penalize diffusing mass to high degree nodes. The first attempt is from [1]. Later on in [2] and [3], it was shown that the method in [1] is equivalent to performing degree weighted l1-regularization. This basically means, that the higher the degree of the node the larger the penalty in the approximate personalized PageRank vector. So, in a sense, the problem of random walks that the authors claim has been solved. In addition, these methods have a regularization parameter that controls the size of the penalty of high degree nodes. Therefore, one can control the random walk/diffusion process to remain local without touching high degree nodes. There are even more advanced methods than PageRank-based methods that put a heavier penalty to high degree nodes by changing the norm that they operate with. For combinatorial diffusions see [5] and [8], for p-norm diffusions see [6-7]. 
It's fine to not know about [5-8] since they are too new, but [1] is folklore, thus ignoring it is important. 

2) In [4], the authors have tried to tackle exactly the same problem using [1]. They even mention the same core-periphery example and they go pretty deep into understanding how [1] helps de-biasing traditional random walks used in node2vec and DeepWalk. The authors need to refer to [4] and also compare with it. 

3) I would also like to see experiments for multi-label classification as done in node2vec and [4]. Such experiments can be put in the appendix and helps the reviewers evaluate the performance of the proposed method compared to existing methods. 

Minor comments

4) GCN and GraphSAGE are implemented in Pytorch-Geometric. Why are you using StellarGraph?

5) For link-prediction and the dataset AstroPh, DeepWalk is shown to significantly outperform node2vec, with the AUC-ROC curve to be larger than 0.8 for DeepWalk and always smaller than 0.8 for node2vec. However, in [4] it is shown that node2vec and DeepWalk have similar performance and above 0.8 for 2 different operators for the edge embedding. For comparison, it would be helpful if the authors discuss in detail the setting of their experiments as discussed in [4]. Why is it that in your experiments node2vec performs so poorly? 

[1] R Andersen, Fan R. K. Chung, and Kevin J. Lang. Local graph partitioning using pagerank vectors. In FOCS, pages 475–486, 2006.

[2] K Fountoulakis, F Roosta-Khorasani, J Shun, X Cheng, and M W Mahoney. Variational perspective on local graph clustering. Mathematical Programming, 174(1-2):553–573, 2019.

[3] W Ha, K Fountoulakis, M W Mahoney. Statistical guarantees for local graph clustering, arXiv:1906.04863.

[4] E Faerman, F Borutta, K Fountoulakis, MW Mahoney. Lasagne: Locality and structure aware graph node embedding. IEEE/WIC/ACM International Conference on Web Intelligence (WI), 246-253, 2018.

[5] D Wang, K Fountoulakis, M Henzinger, MW Mahoney, S Rao. Capacity releasing diffusion for speed and locality. International Conference on Machine Learning, 3598-3607

[6] K Fountoulakis, D Wang, S Yang. p-Norm Flow Diffusion for Local Graph Clustering. International Conference on Machine Learning, 3222-3232.

[7] M Liu, D Gleich. Strongly local p-norm-cut algorithms for semi-supervised learning and local graph clustering. NeurIPS 2020.

[8] R Ibrahim, D Gleich. Nonlinear Diffusion for Community Detection and Semi-Supervised Learning. WWW 19.
limitations_and_societal_impact: The authors adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

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