Exact Recovery and Bregman Hard Clustering of Node-Attributed Stochastic Block Model

Summary

This paper extends the analysis of exact recovery of the Stochastic Block model to node attributed graphs (CSBM). This opens up a new dimension as the desired clustering must not only be optimal in the sense of the SBM but also respect the node attributes (which are assumed to be distributed based on the block of the SBM). First, a binary setting is presented, where edges are either present or not. For this setting, the authors present a tight bound on the information theoretical (im-)possibility of recovering the blocks of the SBM using the Chernoff information of the model. Second, a setting is analysed where the graph structure is sampled from an SBM and node attributes and edge weights are sampled from a distribution from the exponential family. For this setting, the authors present the Chernoff information of the model given its parameters allowing for a concrete characterization of the phase transition between possibility and impossibility of recovery. An iterative likelihood maximization algorithm is then proposed and evaluated on synthetic data.

Strengths

- This paper provides a nice perspective on the relevance of information gained from the network structure and that gained from the node attributes. - The claims of the paper seem sound. - The sections themselves have clear statements.

Weaknesses

- The experiments are not convincing. - All experiments are carried out on synthetic graphs generated in a way that benefits this algorithm. - The presented algorithm is compared with 2 baseline algorithms that only optimize for one of the two dimensions and thus fail at the other. Instead, one could have compared with other approaches to node-attributed community detection, which should pose more of a challenge. [19,20] could have been used as a comparison. - The related work section is quite sparse and is used to distinguish the contribution rather than present related work. E.g. section 2.2 "Algorithms for clustering node-attributed networks" contains 2 citations. This should be augmented. - In the presentation of the results it should be made much clearer that the developments presented here, heavily depend on [3]; with the current writing the reader gets a wrong impression of the novelty of the here presented ideas. - The structure and the presentation of this paper are sometimes confusing. - The reader is often left guessing where we are headed next. E.g. section 4, which is framed as the main contribution (extending [19] by allowing for sparse networks) simply starts by introducing zero-inflated distributions from the exponential family. Or 4.2 gives the derivation for the negative log-likelihood without previously mentioning that this will be used in the iterative likelihood maximization algorithm. - The numbering in the appendix overwrites the numbering in the paper (e.g. Theorem 1 in the paper is not Theorem 1 in the appendix) which makes referencing the paper from the appendix or the appendix from the paper very hard.

Questions

- Can you find any guarantees for your algorithm such as recovery with high probability in a certain regime? - In the experiments, why don't you compare your approach to the other papers [19,20] that you mentioned in your related work? - In the experiments, how close is the performance of your algorithm to the theoretical bound you presented? - Why did you not compare the algorithms on real-world data?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

Limitations of the setting or the approach are not discussed -- this should be rectified.

Summary

This paper studies clustering of node-attributed Stochastic Block Model (SBM). The authors provide information-theoretic threshold for exact recovery under generic distributions for both edge weights and node attributes. In addition, the authors propose a clustering algorithm based on iterative likelihood maximization when edge weights and node attributes are drawn from exponential family distributions. The authors carry out experiment on synthetic data and show that the proposed algorithm outperforms existing state-of-the-art methods.

Strengths

- The theoretical setting (i.e. clustering of node attributed SBM) considered in this work is fairly general. The threshold for exact recovery is presented in a general setting without assuming any particular family of distributions for either edge weights or node attributes. The examples and implications of Theorem 1 provided on page 5 are nice. - The threshold which involves Equation (3.3) captures an intuitive additive signal from edge connections and node attributes. - The overall writing and presentation is very clear and generally easy to follow (although there are many typos here and there). In particular, the presentation of background and related works seem reasonably thorough. - The empirical results, though limited to synthetic data, are promising. - Overall, I think this paper studies a well-known problem in a more general setting than those have been considered in prior work. The new results and algorithm can be a nice addition.

Weaknesses

- Algorithm 1 requires knowing the functions $\psi^*$ and $\phi^*$. This requirement often does not hold in practice. The authors should discuss the practical implications for such requirement and what if these functions are unknown. - Though not necessary for a theory paper, it would be nice to have at least some elementary experiments on real data. - There are many typos throughout the paper. Here are some: - Line 95: standard deviation $\sigma^2$ -> standard deviation $\sigma$ - Line 124: while his work -> while this work - Line 129: is find the community -> is finding the community - Equation (4.2): subscripts for $\theta$ do not match, similarly, subscripts for $\eta$ do not match - Lemma 2: $p_{k\ell}$ in the Equation should be $p_{ab}$? - Line 284: in Nor(...) I think the placements for mean and variance should be reversed

Questions

- In practice, how should one use Algorithm 1 when $\psi^*$ and $\phi^*$ are unknown? - Does Example 2 imply that an oracle to the true community is almost useless unless the oracle gives almost full access to all labels?

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.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

I could not find where the authors discuss the limitations or potential negative societal impact of their work.

Summary

This paper studies community recovery in sparse, weighted networks, which is an important setting that is more general than the commonly-studied undirected, unweighted networks. The authors' first main contribution is to establish the information-theoretic conditions for exact community recovery in this setting, which is a form of the Chernoff information (and cleanly reduces to well-known info-theoretic thresholds in unweighted settings). Next, assuming that edge and node attributes belong to exponential families, an expression for the likelihood in terms of Bregman divergences is given, which then leads to a natural clustering procedure. Extensive numerical experiments are provided comparing the proposed procedure to other approaches.

Strengths

Deriving the information-theoretic threshold for exact recovery via the Chernoff information is perhaps not surprising, but it is a solid contribution as it encompasses a wide range of important examples. The clustering procedure derived, based on a connection between exponential families and Bregman divergences, is clean and intuitive. The simulations on synthetic data show that the clustering procedure has favorable performance in terms of the ARI, compared to other methods, which is a good validation of the theory.

Weaknesses

The paper could be improved if the authors filled in some gaps regarding a few central topics. - Please discuss in more detail how similar / different your approach is to [19], since both leverage the connection between exponential families and Bregman divergences to come up with clustering procedures. - The information-theoretic results are not too surprising. Does the proof require new techniques to handle the more general setting under consideration? If so, they should be discussed in the main text, as it would be of interest to theoreticians in this field. - Please provide additional discussion around the accuracy and sample complexity of the clustering algorithm. Is it efficient? Is it guaranteed to output the MLE or similar?

Questions

- You use the term "homogeneous" a lot: can you define precisely what you mean by this? - Section 2: You can also consider citing work on Censored Block Models, in which edges take on 3 values (present, absent, unknown) - Theorem 1: How crucial is the assumption on the convexity of CH_t (a^*, b^*) in t? - A clarification question: if the attribute distributions were not from an exponential family, would the likelihood be intractable to compute? - For clarity, I would suggest defining ARI. - In the simulations, is the ARI measured between the estimated and ground-truth communities? If so, please clarify in the main text.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

Yes

Summary

This paper studies community detection in node-attributed stochastic block models. Although these models have been studied before, this work has two main contributions: (i) the edge weights in the model are now not necessarily binary, but can also be weighted. The node attributes don’t have to be Gaussian, and can come from a more general exponential family. (ii) An iterative clustering algorithm which maximizes the likelihood by placing nodes in correct cluster based on attributes and edge weights. Experiments on synthetic datasets are also presented

Strengths

• The weakening of the assumptions in this work are more general than what previous work has considered. This is a significant strength of this work. The assumptions in this model (weighted edges, non Gaussian node attributes) are more realistic than what previous work has considered, and I consider this a nice contribution. • To the best of my knowledge the theoretical work is sound and contains some non-trivial insights. Some of the technical techniques presented might have impact on future work. • Experimental results on synthetic data suggest that the proposed algorithm 1 performs well compared to previous work.

Weaknesses

• Given that a motivation for this paper is to provide an algorithm for a more realistic setting, I would have expected to see experiments on real world datasets. In general, stochastic block models enjoy a very symmetric structure, which in some sense makes it nice to cluster. It would be interesting to see how the performance of this algorithm generalises to real-world graphs. • Experimental results on synthetic data is only performed when $k=2$. Higher values of $k$ should be considered ## Minor: Line 73: conditioned of --> conditioned on Line 129: is find --> is to find

Questions

None

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

none

Acknowledgement Response

I thank the authors for their additional experiments on larger $k$ which do improve the experimental results in this work. I do still think that real-world experiments (albeit in a slightly adjusted form) would significantly strengthen the paper. I do appreciate the theoretical analysis of this work which is non-trivial and important (hence my positive evaluation of the paper). However, a large part of the introduction is spent justifying the additional parameters (for continuous edge weights) in the CSBM because of real-world observations. One would therefore also expect some form of real-world experiments.

response

I thank the authors for the response and clarifications, which have improved my understanding of the paper. I thus increased my score to 6. I still disagree with the statement that the experiments are not favorably stacked for the algorithm considered. Indeed only 50% of the other baselines considered even consider attributes. Of those that consider attributes all assume Gaussian attributes, so it is not a surprise to see that such algorithms fail if the attributes are not Gaussian. In the case of Gaussian attributes one of the two attribute considering baselines is in fact not so much worse than what is considered here. Moreover, those baseline algorithms are designed for dense networks and not for sparse networks. Ultimately, I think it would be much more convincing if the authors could represent results on real-world networks.