Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors created a semi-supervised approach for the crucial and challenging subject of community detection. 
To solve the problem, they are facing the following challenges: (1) Non-assortative communities exist in real networks; (2) Degree heterogeneity exists in the network; (3) Optimization-based techniques may obtain local minima; and (4) No existing solution offers theoretical assurances. 
Their method can give the predicted labels of unlabeled nodes in a graph based on the structural similarity metric between the new node and the observed labeled communities. In this work, their contributions include (1)Their new semi-supervised method models degree heterogeneity; (2) The authors' method allows for both assortative and non-assortative communities; (3) The authors designed a structural similar metric to measure the similarity between a new node and the other observed communities. (4) They first showed the theoretical guarantees of their method.
Their efforts do aid in the advancement of community label prediction.
strength_and_weaknesses: Strength:
(1) They propose a fast method.
(2) Their method is more generalized because their semi-supervised method models degree heterogeneity and can handle both assortative and non-assortative communities.
(3) The authors first offer theoretical guarantees on the community detection problems.

Weaknesses:
(1) In the Introduction part, The authors suppose that "the nodes partition into K non-overlapping communities". It could be clearer if they can explain how to process the unlabeled nodes. It means it is not clear how to decide the unlabeled nodes to which community C_i. I believe the way, how to initiate the unlabeled nodes, may influence their equation (4) which needs to consider the labeled and unlabeled nodes in each community.
(2) On page 3, if we look at equation (3), it would be clearer if the authors can add a notation on "𝛳/i" and "𝛳/j".
(3) The authors claimed that their method is fast. However, they didn't give an analysis of time complexity or a comparison of running time. I think it would be better if the authors can give a comparison of running time.
(4)It would be clearer if the authors can offer a pseudo code or a figure of their algorithm.

clarity,_quality,_novelty_and_reproducibility: The author proposed a semi-supervised community detection method that can predict the labels for the unlabeled nodes in networks. The authors clearly described their works. The novelties of their work include a new structural similar metric and theoretical guarantees. Their efforts, in my opinion, do contribute to the development of community label prediction.
summary_of_the_review: Based on the innovations in their work as well as their strengths and weaknesses. Their work is, in my opinion, above the standard for acceptance. But it falls short of becoming strongly accepted.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a semi-supervised community detection method based on the idea that "a community is a group of structurally equivalent nodes". To this end, the authors propose structural similarity metrics, which enable the model to handle non-assortative networks and degree heterogeneity. Theoretical guarantees are also provided to support the proposed approach.
strength_and_weaknesses: Strengths:
+ the proposed approach is well motivated
+ solid theoretical analysis

Weaknesses:
- major issues in the empirical experiments on real-world networks
- minor issues such as citation format and ethics statement
clarity,_quality,_novelty_and_reproducibility: - It is my understanding that when references are not included as part of the sentence, it should be (Ji et al. (2022)) rather than Ji et al. (2022). However, the citation format seems to be mixed throughout the paper, such as in the first paragraph of the introduction. I encourage the authors to fix the misused reference formats.

- In the third paragraph of the introduction, two real-world examples are given to motivate the research question. Maybe add some references to support the first example just like Ji et al. (2022) supports the second example.

- I have major reservations about the experiments on real-world networks.

1) Is it a fair comparison between this model and GCN, when your setting excludes node attributes while GCN specifically focuses on propagating messages based on node attributes? Although three measures are adopted to add synthetic node attributes to do GCN (i: all 1 vectors, ii: random attributes, iii: adjacency vectors), I am not sure whether these are standard practices to use GNNs on networks with no node attributes. Propagating messages with all-1 vectors seems to be resulting in over-smoothing. Using adjacency vectors as node features means that the feature transformation linear layers' size changes with respect to the number of nodes in a network, which is not an inductive setting and could heavily overfit due to too my parameters. If these statements are true, then the consistently low performance of GCNs in Table 1 could be a result of the undesirable experiment setting, not necessarily indicating the proposed approach's superiority over GCN. Setting aside whether it's fair to compare non-attribute approaches with GCN, I would encourage the author to check out standard practices to add synthetic node attributes in GNN research.

2) Since (a) the authors acknowledged that the proposed approach could be extended to handle attributed graphs (remark 4 in Section 2.2), (b) GCNs rely on meaningful node attributes, and (c) an increasing amount of real-world networks have nodes with clear attributes or semantic information, I wonder if it might be better and fairer to evaluate on the datasets used in [1] and/or other large-scale real-world networks [2,3].

3) Let's assume that the current setup, adding synthetic features to GCN as a baseline, is fair. In that way, there seem to be more advanced semi-supervised community detection approaches based on better GNNs and node attributes [1,4,5,6]. The authors are encouraged to compare with them, or at least discuss them in the related work.

- The authors stated that "we do not think that our work has any potential negative influence" and I would like to propose one. In the third paragraph of the introduction, the authors gave an application case of how to determine the community belongings of social media users with the help of a small fraction of nodes with known community labels. Similarly, the proposed approach could be manipulated by malicious and authoritarian actors to identify dissenters on social media with "dissenter" as a community. If the authors agree, I would suggest expanding the discussion in the ethics statement.

[1] Jin, Di, et al. "Graph convolutional networks meet markov random fields: Semi-supervised community detection in attribute networks." Proceedings of the AAAI conference on artificial intelligence. Vol. 33. No. 01. 2019.

[2] Tang, Jie, et al. "Arnetminer: extraction and mining of academic social networks." Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining. 2008.

[3] Feng, Shangbin, et al. "TwiBot-22: Towards Graph-Based Twitter Bot Detection." arXiv preprint arXiv:2206.04564 (2022).

[4] Wu, Xixi, et al. "CLARE: A Semi-supervised Community Detection Algorithm." Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2022.

[5] Bakshi, Arjun, Srinivasan Parthasarathy, and Kannan Srinivasan. "Semi-supervised community detection using structure and size." 2018 IEEE International Conference on Data Mining (ICDM). IEEE, 2018.

[6] Li, Pan, I. Chien, and Olgica Milenkovic. "Optimizing generalized pagerank methods for seed-expansion community detection." Advances in Neural Information Processing Systems 32 (2019).
summary_of_the_review: This paper proposes a well-grounded solution to an interesting problem with theoretical guarantees. Though I appreciate this work, I have some reservations about the empirical experiments. I look forward to discussing with the authors to revisit my review and/or score. :)
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the a semi-supervised community detection problem on a degree-corrected stochastic block model. Given some known labels of the nodes in the network, the authors propose a method to classified the new node based on cosine similarity with the in-sample data. 
strength_and_weaknesses: Strength

This paper is easy to read. I can understand the algorithm and theorems without any trouble. 

Weaknesses

1. The problem can be easily solved by existing algorithms with slight modification. For example, we can run the community detection algorithm again on the whole network. If we are only allowed to apply local refinement on the network to reduce computational complexity, the following steps will also work. 

(i) Apply prototypical refinement, e.g., Algorithm 2 of Gao et al. (2018), with known labels, then we can assign labels to nodes in $\mathcal U$.

(ii) Now we have labels for all nodes. we update the labels for every node by applying the same refinement procedure with initial labels for all node. 

Note that the reason we update the labels in step (ii) is to use the information in $A_{\mathcal U\mathcal U}$. The method in Gao et al. (2018) may not be applied to non-assortative block models, but it is not hard to replace their procedure by a local likelihood ratio classifier. 

2. The authors propose a method based on the cosine distance. This classifier may be equivalent to likelihood ratio classifier. If this is the case, it should achieve the information theoretical lower bound, but the authors fail to show this in Lemma 2. It is claimed in the paper that "we bound the total variation distance by the Hellinger distance (the total variation distance is hard to analyze directly)". It can be shown that the exponent of total variation distance and Hellinger distance are the same up to a $1+o(1)$ factor. See [1] for details. If the connectivity matrix is more general, you can use Chernoff information to bound the total variation distance. See Section 11 of [2] for more details. 

[1] Zhang, Anderson Y., and Harrison H. Zhou. "Minimax rates of community detection in stochastic block models." The Annals of Statistics 44.5 (2016): 2252-2280.

[2] Thomas, M. T. C. A. J., and A. Thomas Joy. Elements of information theory. Wiley-Interscience, 2006.
clarity,_quality,_novelty_and_reproducibility: This paper is reader friendly. I believe the empirical result is easy to reproduce. 
summary_of_the_review: This paper is well written. However, the proposed method is too simple and the theoretical result cannot support the output of the algorithm can achieve the optimal error rate.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper considers the semi-supervised community detection problem. In particular, they consider the degree-corrected block model (DCBM) where each node belongs to one of K communities and has a degree parameter. Then, the edges are generated between nodes according to the degree parameter of the two nodes and community connection probability.  The problem is given the label of a subset of nodes, to find the label of the remaining nodes. They propose two new algorithms Anglemin and Anglemin+ for this problem. They provide a misclassification error bound for their algorithm and show their algorithm is nearly optimal by comparing it with the information-theoretical lower bound. Finally, their experimental results show their algorithms achieve smaller classification errors than the unsupervised method.
strength_and_weaknesses: Strengths:
1. This paper considers a new semi-supervised community detection problem, which can be used in many applications with partially observed labeled data. 
2. This paper provides an explicit misclassification error bound for the proposed algorithm. 

Weaknesses:
(Minors): The label for equations (8),(9), and (10) seems unmatched with the lemmas and theorems below. 
clarity,_quality,_novelty_and_reproducibility: This paper is well-written and easy to follow. It provides solid theoretical results and convincing experimental results. I think all results are original and reproducible.
summary_of_the_review: This paper provides a solid contribution to a semi-supervised community detection problem, They provide theoretical guarantees and convincing experimental results. Thus, I tend to accept this paper.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The authors propose new algorithms to recover community in the degree-corrected stochastic block model in the semi-supervised setting. In this setting, few labels are revealed to the algorithm and the goal is to use such labels to recover the full community structure. The authors present algorithms for this task and they study their performances both in theory and in practice showing that their method is very effective.

Overall, the result is a nice and novel contribution on a well-studied problem and it would be nice to include it in the ICLR program.
justification_for_why_not_higher_score: Experimental results are interesting but they are not too strong. It is also not clear if the method could be directly applied in practice.
justification_for_why_not_lower_score: Nice theoretical analysis of natural model, interesting experimental results
Decision: Accept: poster