Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper proposes a new method, called decoupled self-supervised learning (DSSL), for self-supervised learning of node representation on non-homophilous graphs. Experiments on reals datasets are used to verify the effectiveness of the proposed method. 
strengths_and_weaknesses: Strengths:
1. It is interesting to study the self-supervised learning problem about node representation learning on non-homophilous graphs, because most existing graph self-supervised learning methods assume homophily in graphs. 
2. The proposed method seems to be reasonable.
3. Theoretical analysis is provided.
4. Better accuracy is achieved by the proposed method, compared with existing methods.
5. The paper is well written with good organization.

Weaknesses:
1. Time complexity analysis is not provided. The datasets adopted for evaluation are relatively small. Is it due to high time complexity of the proposed method? As we know, most self-supervised learning methods are proposed for large-scale datasets.
2. On some datasets with non-homophilous structure, like Twitch, existing methods based on homopilous assumption also achieve comparable accuracy with the proposed method, which seems to contradict with the motivation of this paper. 


questions: 1. What is the time complexity of the proposed method? Is the proposed method slower than existing methods? Why not perform experiments on larger datasets? 
2. How to explain the phenomenon that existing methods based on homopilous assumption also achieve comparable accuracy with the proposed method?
3. Can we generate some synthetic datasets with only homophilous structure or non-homophilous structure to verify the property of the proposed method and existing methods?

limitations: The authors have adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper proposes a novel self-supervised learning approach for node representation learning on non-homophilous graphs. The proposed approach model the neighbors of a central node via a generative process. In addition to learning the patterns of local neighbors in the graph, the proposed approach also learns global semantic information in the node representations with parameterized prototypes. On top of that, the proposed method seeks to find different underlying semantics in different patterns of local neighbors in the graph.
strengths_and_weaknesses: Strengths 

1. This paper presents a framework for self-supervised learning on non-homophilous graphs, which is meaningful and well-motivated.
2. The paper shows a reasonable amount of experimental results on data of different homophily levels.
3. The paper performs thorough ablation studies on different components of the model. 

Weaknesses
1. Compared graph self-supervised learning methods are not comprehensive. For self-supervise graph learning methods, the performance of included baselines such as MVGRL and BGRL are not SOTA. It is better to include methods such as [1][2][3] which has much better performance. Also, the proposed method aims to learn the local structure and the global semantic information with self-supervised learning. Works with similar motivations have been proposed in the community. For example, [3] also proposes jointly considering structural and neighbor information for self-supervised learning. [4] also proposes a clustering objective. [5] also uses the idea of prototypes to capture the global semantic knowledge

2. For the experiments, the authors didn't use standard data split protocol (20-shot per class). Using 60% training data is somehow contradict with the goal of self-supervised learning and it is hard to fairly compare with the reported results in our papers. Meanwhile, considering that the proposed method consists of multiple components, ablation studies are vital to validate the power of semantic shift and personalized posterior. It would be great if the author can perform the ablation studies on multiple non-homophilous graph datasets and even on homophilous graph datasets.

3. Minor issues
Line 39 constructs -> construct

Line 96 have achieve -> have achieved

Line 182 equivalent to maximize -> equivalent to maximizing

Line 164 relation context -> relational context

Line 220 undated -> updated

Line 250 affect -> affects

Line 303 an relative improvement -> a relative improvement

[1] Jiao et al. "Sub-graph Contrast for Scalable Self-Supervised Graph Representation Learning", ICDM 2020

[2] Jin et al. "Multi-Scale Contrastive Siamese Networks for Self-Supervised Graph Representation Learning", IJCAI 2021

[3] Mo et al. "Simple unsupervised graph representation learning", AAAI, 2022

[4] Zhao, Han, et al. "Graph Debiased Contrastive Learning with Joint Representation Clustering" IJCAI 2021

[5] Ding et al. "Structural and Semantic Contrastive Learning for Unsupervised Node Representation Learning", arXiv 2022
questions: 1. Any reasons of using 60% 20% 20% data splits rather than standard splits as used in other papers? 
2. It would be great if the author could compare the proposed method against works with similar efforts, as stated in Weakness 1. 
3. Could the authors provide more details on the complexity analysis?


limitations: N/A
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper focuses on self-supervised learning for node representation learning on non-homophilous graphs. The authors propose a framework called DSSL. DSSL leverages a probabilistic formalization of the problem, and it introduces a latent variable for modeling the semantic structure of graphs. Experiments on a few graph benchmarks show promising results of DSSL.
strengths_and_weaknesses: ----- Strengths:

(1) The problem is important.
Node representation learning is a fundamental problem in the graph machine learning area for its wide downstream applications. Many recent works propose to use graph neural networks for node representation learning, but these methods require a large amount of labeled nodes for training. Different from these works, this paper focuses on self-supervised learning for node representation learning, which is an important problem.

(2) The proposed DSSL framework is principled.
A framework called DSSL is proposed. The framework uses a probabilistic formalization of the problem, and a mixture model is used to characterize graph structures, where a discrete latent variable is introduced. During training, gumbel-softmax is used to deal with the discrete latent variable. As discussed in the paper, DSSL can be theoretically viewed as to maximize the mutual information between node representations and global semantics. Overall, the DSSL framework is principled with good theoretical results, and I quite like this approach.

(3) The results are encouraging.
In the experiment, the authors use a few graph benchmarks for comparison, and DSSL outperforms many competitive baselines.

----- Weaknesses:

(1) Similar ideas of self-supervised learning have been explored in literature.
In terms of methodology, the major idea of DSSL is to maximize the conditional probability for each edge. Although this is an intuitive idea, the idea has been widely explored by existing studies. For example, classical graph embedding algorithms (e.g., DeepWalk, LINE, node2vec) also try to maximize the conditional probability for model training. Some more recent works (e.g., GraphSAGE) leverages similar ideas. The major difference between DSSL and these works is that DSSL uses a mixture-model formalization to define the conditional probability on each edge, which is able to approximate true conditional probabilities more precisely, but this idea has also been touched by existing works (e.g., vGraph: A Generative Model for Joint Community Detection and Node Representation Learning). Given all these works, the idea of DSSL is not very new. Also, vGraph is not discussed in the paper, making it hard to judge the contribution of DSSL over vGraph. Thus, it would be helpful if the authors could discuss the advantage of DSSL over vGraph in the revised draft.

(2) Whether non-homophilous graphs are worth studying?
The major focus of the paper is on non-homophilous graphs. However, I feel like non-homophilous graphs are not so popular in practice, and homophily exists in most real graphs. Besides, in terms of modeling, I feel like homophilous graphs and non-homophilous graphs are not so different. For example, if we look at the results in the experiment, we can see GraphCL and BGRL achieve competitive results on most homophilous graphs, although they are not specifically designed for non-homophilous graphs. Furthermore, from my understanding, DSSL can be applied to both non-homophilous and homophilous graphs, and I don't see special designs targeting at dealing with non-homophilous graphs. Therefore, I think what DSSL does is not so consistent with the major claim of the paper, and I wonder why the authors position DSSL as modeling non-homophilous graphs rather than general graphs (i.e., both non-homophilous and homophilous graphs)?

(3) The experiment can be further improved.
In the experiment, the authors compare DSSL against several competitive baseline methods. Overall, DSSL outperforms all the methods on non-homophilous graphs. However, the experiment mainly presents quantitative results, showing DSSL is a better model for non-homophilous graphs, but the underlying reason is not well explained and validated. Therefore, it might be more convincing if the authors could do some ablations studies or case studies to show the intuition why DSSL has better performance on non-homophilous graphs.

questions: See the weaknesses above.
limitations: N/A
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This work studies the new problem of self-supervised learning for node representations on non-homophilous graphs, with the novel latent variable modeling to capture local and global semantics of graphs by decoupling latent factors, which is supported by theoretical and empirical results. In particular,
* The authors first point out that self-supervised learning on non-homophilous graphs is undiscovered, yet it should be differently handled unlike in the existing self-supervised learning methods for homophilous graphs, due to a unique structure of non-homophilous graphs that connected nodes do not share similar properties. 
* To tackle this problem, the authors model the latent variable based on the motivation that nodes with similar neighborhood distributions should have similar representations, on which the model can capture the local semantics and global cluster structures by decoupling the neighborhood context. 
* The authors make the proposed latent variable model learnable in an end-to-end fashion with the famous amortized variational inference scheme.
* To alleviate the issue that all node representations are collapsed into one representation and are assigned to one cluster, the authors leverage two tricks: 1) use the asymmetric encoding scheme for node representations (i.e., updating central and neighboring nodes differently); 2) use the outputs of node representations with their mixture probabilities to obtain prototype vectors for node clustering. 
* The authors theoretically show that their proposed method maximizes the mutual information between the node representation and the joint distribution of suggested local and global latent variables, which is further analyzed in terms of the generalization bound to downstream tasks.
* The authors empirically verify that the proposed DSSL largely outperforms existing baselines, especially on non-homophilous graphs, and several analyses support their model designs as well as their claims.
strengths_and_weaknesses: ### Strengths
* This work discovers a new task of self-supervised learning for nodes on non-homophilous graphs, with enough explanations on its inherent challenges. 
* This work is technically and mathematically sound. Specifically, this work tackles the proposed task with the novel and interesting latent variable formulation that models distributions of node's neighbors with decoupled latent factors, which can capture local distributions with reconstruction loss but also global cluster semantics with cluster centroids. Also, the authors theoretically show the effectiveness of the proposed DSSL in the view of information maximization.
* The empirical results of the proposed DSSL are significant, compared against relevant baselines.
* The authors comprehensively conduct the ablation study and sensitivity analysis.
* This paper is extremely well written and easy to follow.

### Weaknesses
Note that the below points are not the major weaknesses of this paper, but it would improve the paper if the authors address them adequately.
* There is a relevant work that, in graph self-supervised learning, [1] considers both local and global semantic structures, where the global context is captured by class prototypes which could be considered similar to the authors' method in the motivational perspective.
* The authors claim in the introduction section that, one challenge of graph self-supervised learning is to capture the long-range semantic dependency described in Line 66. However, I cannot find empirical results that the proposed DSSL framework can alleviate this issue. The case study in Figure 5 only shows the local dependencies between nearby nodes, not the long-range dependencies.

---

[1] Xu et al. Self-supervised Graph-level Representation Learning with Local and Global Structure. ICML 2021.

questions: ### Major Questions and Suggestions
* Regarding the first weakness in the above, the authors can address it by discussing the relevant work [1].
* Regarding the second weakness in the above, the authors can address it by showing results of capturing long-range dependencies, perhaps in a similar manner in Figure 5 of the case study but based on nodes far away from each other.

### Minor Questions and Suggestions
* Does the color in Figure 1 denote the class of nodes? It seems more explanations are needed for the illustration of Figure 1.
* The meaning of encoding intra-cluster variation in Line 172 is unclear. How does the proposed formulation in equation (3) capture the intra-cluster variation?
* A lack of explanation on the projector g_\theta in Line 209. It is better to explain the projector, for readers who are not familiar with self-supervised learning.
* The contents on page 14 should be removed.

### Typos
* In Line 293, we. 
* In Line 346, case.
* In Line 361, (b) and (c) should be (c) and (d).

limitations: The authors provide the limitations and potential negative societal impact of their work in Section F of the supplementary file. I am satisfied with them.
review_title: null

Meta-review: metareview: This paper proposes a self-supervised learning method for graph-structured data, which can better explore global and local semantic dependencies. The method uses a probabilistic framework based on the mutual information maximization principle. Theoretical analysis is also developed to show a tighter upper bound on the downstream Bayes error can be obtained by the proposed method. After the rebuttal, all reviewers generally appreciate contributions made by this submission.

However, it is suggested to revise the following problem in the final version.
- As identified by the first three reviewers, this paper does not specifically target at non-homophilous graphs. Instead it seems to can better capture semantic information on graphs on a more non-local level as emphasized by the last reviewer. The connections between global semantic and non-homophilous graphs need to be clarified.
- The above problems make reviewers wonder the necessity of study non-homophilous graphs, whether sufficient methods are compared in homophilous graphs, and where enough ablation studies are performed.
- While authors also offer theoretical analysis, it is also not clear how obtained results are connected with non-homophilous graphs.
confidence: Certain
Decision: Accept