Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper extends the traditional ONE-DIMENSIONAL Chinese Restaurant Process into the multi-dimensional case and introduce the permutation into the Bayesian nonparametric clustering perspective. As it can be seen as an component-wise integrated-out Block-Breaking Process, this work is very innovative and should produce long-term impact to the Bayesian nonparametric community. 
main_review: This paper presents a very innovative approach in extending the traditional one-dimensional CRP into the multi-dimensional case. Instead of independently and separately regarding the multi-dimensional clustering through multiple CRPs, this approach combines the multi-dimensional clustering into one single approach and is a very neat solution. I would very much recommend it to be accepted.

The presentation is very clear and the figure visualisation helps a lot in understanding the related processes. 

I do not have suggestions to further improve the paper (as the paper is already nearly perfect). It would be great if the authors can answer the below two small questions:
1, can the model extends to 3-dimensions or more. The current work seems to mainly focus on the 2-dimensional case. I believe this approach should be able to work on 3 dimensions or more in theory. However, will the related process change a lot and need a lot more considerations or more unseen difficulties?

2, recently, there is another paper of Hierarchical Infinite Relational Model (UAI-2021). That paper should be different from this approach. Can the authors comment on that paper?
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes Permuton-induced Chinese Restaurant Processes (PCRPs), a novel class of Bayesian nonparametric (BNP) models for rectangular partitioning. There have been several proposals for BNP priors for rectangular partitioning or more generally space partitioning problems. Many of them can be understood as a multi-dimensional extension of Dirichlet processes, but almost all of them only consider the infinite-dimensional representations (multi-dimensional stick-breaking like representations) which make posterior inference cumbersome. According to the authors, PCRP is probably the first try to introduce a CRP-like representation for rectangular partitioning, which comes with the benefit of handy posterior inference. The main idea is to use some tools developed in the literature dealing with the permutations; it can be shown that a permutation can be mapped to a specific class of rectangular partitioning, and a random permutation can be realized by the random measure called permuton (which is quite similar to graphon). In order to actually draw a rectangular partitioning, a partition is drawn from a plain CRP with table coordinates are sampled from the permuton. Then, the permutation induced from the table coordinates is turned into a rectangular partitioning. PCRP facilitates a convenient MCMC procedure which is demonstrated to converge faster than previous approaches in the experiments but is not projective like normal BNP models. The authors further propose a workaround to this and an MCMC inference for the workaround based on bridging. 

main_review: Overall, I find the paper hard to follow. There are many concepts introduced and the paper is too short to faithfully review all those concepts. Personally, I'm not familiar with the concepts related to permutations and patterns, so it took me a while to comprehend the definitions and notations for the permutations and patterns. It is also painful to follow the algorithm; how the permutations are represented as rectangular partitioning and how to convert between those two, and how the diagonal partitionings are extended to generic partitionings.   If possible, it would be better to provide more illustrative examples in the supplementary material for the readers like me. Some notations are used without being introduced; e.g., Av(B) or the symbol $\ngeq$. 

I must admit that I failed to understand all the proofs and arguments presented in this paper, so my judgment is for the generic story and implications of the presented work. The paper proposes a novel BNP model for rectangular partitioning based on the connection between permutations and rectangular partitioning. I like the model comes with a practical and possibly easier inference algorithm to implement than the previous ones. I also like to see that the permuton is introduced and led to derive a novel BNP model; this is quite reminiscent of how graphon (graphex) is related to BNP models for graphs and random arrays. The experimental results seem convincing, illustrating the fast convergence of the proposed algorithm as argued in the main paper.

- I wonder about the time complexity of each MCMC step of the proposed algorithm. It seems that whenever a new table is inserted, the permutation structures should be adapted accordingly. How expensive is this procedure, and is there any data structure to efficiently implement and manage this?
- For more generic space-partitioning processes, there have been several works that can partition a space into partitions whose components are not necessarily rectangles. For instance,  Ge et al., 2019 proposes a flexible class of space partitioning process called Random Tessellation Process (RTP, different from Rectangular tilting process) including Mondrian processes as special cases, and include generic non-axis-aligned cut partitions. RTP is also proved to be projective. Of course, the increased flexibility comes at a cost of a complicated inference procedure. I guess probably PCRP is less generic than RTP, but not sure whether the partitions can be generated from PCRP is a subset of partitions that can be generated from RTP. How would you compare PCRP to RTP? 
- The perplexity curves in Figure 8 seems not converged for the models other than IRM; If ran long for enough times, do the models converge to similar perplexity values?






limitations_and_societal_impact: The authors admit the theoretical imperfection of the proposed framework and further proposed a workaround for that. The ethical implication is also discussed in section 6.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper introduces  a multi-dimensional extension of the Chinese restaurant process (CRP) called permuton-induced CRP (PCRP). The paper discusses the permuton setting of the CRP to get a probabilistic model of rectangular partitioning of a matrix.
A Permuton is a probability measure on [0, 1]x [0, 1], which can be regarded as a geometric interpretation of the
scaling limit of permutations. The PCRP can be used as a unified stochastic process to represent different classes of rectangular partitioning.  The authors also propose a new representation of the BNP model to depict the PCRP as a bridging state to existing BNP relational models.
Experiments involve the application of PCRP to Bayesian nonparametric (BNP) relational data and there are some promising results showcased.
main_review: Originality: The work is a novel combination of well-known techniques. It is clear how this work differs from previous contributions. Related work is adequately cited

Quality: The submission is technically sound justified by theoretical analysis and experimental results. This is a complete piece of work

Clarity: The submission is clearly written.

Significance: The study and results are important. There is potential for others to use the ideas. The submission address a difficult task in a better way than previous work. The work provides a unique theoretical approach.

** Comments
* Can PCRP handle continuous distributions as opposed to a multinomial/Dirichlet distribution?
* How would PCRP behave with an asymmetric Dirichlet prior? 
* What are the conditions under which PCRP partitions data to mostly the same partition?

** Minor comments
* Figure 9: It would be helpful if the details of the ‘hidden fine clusters’ can be highlighted. What does ‘hidden’ mean in this context?
* Figure 4, 5 (for example) when mentioned in text: Consider a label for each subfigure (i, ii, or a, b) to increase readability as well as save some space. 


limitations_and_societal_impact: Yes, limitations have been discussed
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper introduces the permuton-induced Chinese restaurante process (PCRP), a prior over rectangular partitions of 2D space, and applies the prior to analyze relational data. The sample paths of the prior (Figure 2) exhibit different behavior depending on the permuton measure gamma, which is one of the design choices in the prior. In numerical experiments, probabilistic models using the proposed prior perform competitively with existing choices of prior in terms of held-out perplexity.
main_review: I have a concern with the quality of the paper. 

Originality. Even though the CRP is the most well-studied process in Bayesian nonparametrics (BNP), Section 3.1 has found a new use for it, in the context of generating random rectangular partitions. The construction is well-explained by text and illustration (Figure 4, 5, 6). The paper also discusses distinction between the new construction and existing ones where the opportunity arises (lines 166-168). The appearance of the permuton measure gamma creates a degree of flexibility in the prior sample paths (Figure 2) that is worth investigating further. 

Quality. (big concern). How is sampling done in the PCRP model? The abstract hints that we will use Markov chain Monte Carlo (MCMC) to draw inference from posteriors in PCRP-based models. For the CRP in clustering models, because of the exchangeability in the partition, we have Gibbs samplers that update the assignment of each observation conditioned on other observations’ assignments. What are the analogous results for PCRP?  I am not sure where the main paper/appendix discusses inference algorithms. While the “Exact BNP model with bridging states” is the closest paragraph, it does not discuss the update steps nor point to a location in the appendix with the equations. 

Quality (smaller concern). Is there intuition connecting the density of the permuton to the qualitative behavior in Figure 2? A key appeal of the PCRP approach based on Figure 2 is that different choices of gamma lead to qualitatively different types of rectangular partitioning. Can we understand the connection better? One starting point would be to plot the gamma densities (similar to what the paper currently does in Figure 1e). Currently, the paper points to outside references for information on gamma --- it would be great if it were self-contained. Relatedly, how do the sample paths from the permuton compare to those from say, the Mondrian process, another seemingly flexible prior over rectangular partitions? Finally, in Figure 9, I am not sure what “more detailed clusters” means. Is there some quantitative metric? The observations on the top and bottom rows are not the same as each other as well – for comparisons, it would be better if they were the same. 

Clarity. Lines 171-172: what does it mean that the CRP table ordering lead to permutation? What is “n” in this situation? My guess is that n is the number of tables after N customers. If so, I would recommend swapping out n for another notation since having lower case and upper case meaning different objects is confusing. It is not clear what the purpose of the antichain (lines 100) or dashed patterns (lines 103) play in the overall methodology. They are only mentioned in Section 2.1 and not again elsewhere in the paper. In Section 3.2, the intro could be renamed, and the caption of Figure 2 rewritten. The point of Section 3.2 appears to be “for different choices of the permuton gamma, the rectangular partition generated from PCRP takes on one of a few different qualitative behavior.” The starting sentence “how to design the permuton gamma in a specific way” is vague. In Figure 2, the stating sentence should be something like “Five classes of rectangular partitioning corresponding to different choices of permuton gamma.” The current phrasing makes it sound like these are the five classes overall (not just the ones we can generate with the permuton approach). My last comments are small suggestions if time permits. The abstract can be simplified. I think the structure of the abstract in https://www.jmlr.org/papers/volume12/griffiths11a/griffiths11a.pdf is also suitable for your paper. They first state that the sample paths of the IBP are binary matrices; they then mention the type of data analyses in which the IBP would be a good prior. The analogs in your abstract would be lines 6-8 and lines 1-2. In your abstract, the comparison with the BBP/the details on the permuton can be removed, as they introduce a lot of new concepts in the abstract and complicate the main message. The font / tick sizes in Figure 8 should be enlarged. The y-axis can also be standardized across datasets. The plots in Figure 8 are missing ticks on the x-axis. Finally, I would change the tone of “multi-dimensional extension of the CRP … is one of the most critical unsolved issues”, since the word “critical” is very strong and would require a lot of justification. In terms of applied work, the literature has come up with options to model relational data (like the Mondrian process, the IRM etc). In terms of theoretical work, the BBP is already one extension of the CRP in higher dimensions.

Significance. The PCRP has the potential to add to the Bayesian nonparametrics a model over rectangular partitions with more flexible sample paths.	
limitations_and_societal_impact: For future work, a careful synthetic example to highlight the benefits of PCRP over BBP would be useful. Based on Figure 1c), the types of partition in sample paths of the BBP is more restricted then the types of partitions in sample paths of the PCRP Figure 2. If the BBP is used to analyze data from a PCRP prior, can we show that it fails to capture important aspects?
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposed a model for relational data -- permuton-induced Chinese restaurant process, which can be regarded as a multidimensional Chinese restaurant process. The permuton is used to fill in the input matrix according to a Chinese restaurant scheme. The underlying model is well designed for rectangular partitioning, and various empirical results are also provided.
main_review: This paper proposed a new model to deal with relational data -- permuton-induced Chinese restaurant process. This model combines the idea of permuton with Chinese restaurant process for different hierarchies. In particular, the permuton-induced Chinese restaurant process is well designed for the problem of rectangular partitioning. A detailed description of the model, as well as how to choose the "hyperparameter"--permuton is explained in detail. The topic of the paper is important. The idea of the paper is novel, and of high quality. The paper is also well-written. I pretty like the idea and presentation of the paper, and would regard this as a good contribution to Neurips community.
limitations_and_societal_impact: The authors have adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

Meta-review: The reviewers all agreed that this paper should be accepted. Please read through the reviews and responses and make sure to include all suggested changes in the camera ready version. One area to pay special attention to when preparing the camera ready is clarity. For example, this paper contains quite technical definitions of permutations/partitions and their relationships. It would be very useful to the more general reader to provide many more illustrative examples (in the appendix, if space is limiting).

As a side note, the reviewers greatly appreciated the authors' enthusiastic engagement during the discussion period -- well done!
Decision: Accept (Poster)