Permuton-induced Chinese Restaurant Process
Authors: Masahiro Nakano
Yasuhiro Fujiwara
Akisato Kimura
Takeshi Yamada
Naonori Ueda
Venue: NeurIPS 2021 Poster (2021)
Keywords: Bayesian nonparametrics
Chinese restaurant process
Relational model

Abstract: This paper proposes the permuton-induced Chinese restaurant process (PCRP), a stochastic process on rectangular partitioning of a matrix. This distribution is suitable for use as a prior distribution in Bayesian nonparametric relational model to find hidden clusters in matrices and network data. Our main contribution is to introduce the notion of permutons into the well-known Chinese restaurant process (CRP) for sequence partitioning: a permuton is a probability measure on $[0,1]\times [0,1]$ and can be regarded as a geometric interpretation of the scaling limit of permutations. Specifically, we extend the model that the table order of CRPs has a random geometric arrangement on $[0,1]\times [0,1]$ drawn from the permuton. By analogy with the relationship between the stick-breaking process (SBP) and CRP for the infinite mixture model of a sequence, this model can be regarded as a multi-dimensional extension of CRP paired with the block-breaking process (BBP), which has been recently proposed as a multi-dimensional extension of SBP. While BBP always has an infinite number of redundant intermediate variables, PCRP can be composed of varying size intermediate variables in a data-driven manner depending on the size and quality of the observation data. Experiments show that PCRP can improve the prediction performance in relational data analysis by reducing the local optima and slow mixing problems compared with the conventional BNP models because the local transitions of PCRP in Markov chain Monte Carlo inference are more flexible than the previous models.

Permuton-induced Chinese Restaurant Process
Masahiro Nakano, Yasuhiro Fujiwara, Akisato Kimura, Takeshi Yamada, Naonori Ueda
NTT Communication Science Laboratories, NTT Corporation
(masahiro nakano pr, yasuhiro.. fujiaara. Saaar..ki kh, akisato. kimura. takeshi, yamada, be, naonori. ueda. fr @hco co.
Abstract
This paper proposes the permuton-induced Chinese restaurant process (PCRP), a stochastic process rectangular partitioning of matrix. This distribution is suitable for use a prior distribution Bayesian nonparametric relational model to find hidden clusters in matrices and network data. Our main contribution is introduce the notion of permutons into the well-known Chinese restaurant process (CRP) for sequence partitioning: a permuton is probability measure on [0, 1] [0, 1] and can be regarded as a geometric interpretation of the scaling limit of permutations. Specifically, a random geometric arrangement on [0, 1] x [0, 1] drawn from the permuton. By analogy with the relationship between the stick- bocc-breaking process (SBP) and CRP for the infinite mixture model sequence, this model can be regarded as a multi- dimensional extension of CRP paired with the block-breaking process (BBP), which has been recently proposed as a multi diimensionnll extension of SBP. While BBP always has infinite number of redundant intermediate variables, PCRP be composed of varying size intermediate variables a data-driven manner depending the size and quality of the observation data. Experiments show that PCRP improve the prediction performance in relational data analysis by reducing the local optima and slow mixing problems compared with the conventional BNP models because the local transitions of PCRP in Markov chain Monte Carlo inference are more flexible than the previous models.
extend the model that the table order of CRPs has
1 Introduction
The multi-diieenional extension of the Chinese restaurant process (CRP) 9 50 for infinitely exchangeable random arrays is one of the most significant unsolved issues in the field of Bayesian nonparametrics and its applications representing random clustering of sequence using the metaphor of customers sitting at tables. Typically, often used when we need to cluster a sequence where the number of clusters is unknown in advance. The magic of CRP is that it requires only finite number of parameters for finite data; nevertheless, the model itself has infinite representational power. Specifically, is known that a mixture model using CRP is theoretically equivalent the Dirichlet process mixture model (DPMM) represented by the stick- breckinn process (SBP) [ with an infinite number of parameters. The relationship between the two DPMM representations. CRP and SBP. can be explained by whether the intermediate random variables in de Finetti's 's representation theorem 28 37 are marginalized or not (Figure T. (a) and (b)). CRP has contributed greatly the development of the BNP machine learning field in the sense that it has made BNP not only theoretical but also practical. It enables models with infinite representational power be accurately simulated on a computer with finite number of parameters without any approximation (c.g., finite truncation). In fact, variety of extensions of CRP have been studied, including the nested CRP [6 I7 60] the Chinese restaurant franchise [61], the tree-structured CRP (6), the dependent CRP 14 15 31 However, in the development of CRP, the extension BNP relational models has remained historical conundrum.
machine learning. The standard CRP is the stochastic process
[1 27
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

AAAAMAAA
9
(x) Süick-brwnking process
(b) Chinese restaurant process
A
AAA
(e) Block-breokking process
(4) Permatoot-itduoed CRP
(e) Permenton
Figure 1: (a) SBP representation for sequence partitioning based on de Finetti's 's representation. (b) CRP representation for sequence partitioning. Each customer (triangle) sequentially choose table (dark circle). (c) BBP representation for rectangular partitioning based on AHK representation theorem. (d) Our proposed PCRP. We recall that certain class of rectangular partitioning has a bijection to a certain class of permutation. Therefore, if we could add to the order based on permutations for CRP tables, could convert the table assignments of data by CRP into rectangular partitioning. To achieve this, we introduce a random geometric location on [0, 1] x [0, 1] into the CRP table drawn from permuton. (e) Illustration of permuton. Top shows an array representation
of a permutation a = 5724163. The horizontally i-th circle has the height a (i). Bottom shows the corresponding permuton to a 5724163, i.e., the probability measure [0, 1] [0, 1].
As a special case of the BNP relational models, the infinite relational model (IRM) 38 consisting of the product of CRPs was proposed. The IRM express random rectangular partitioning of a matrix; however, its representational capability is restricted to a minimal subset of rectangular partitioning called regular grid (Figure [ left). Therefore, in order obtain model with higher representational capability, variety of BNP models for relational data have been rapidly developed
in recent years 38
55
54
20
[53
58
46
36
19
7
2X
26
43
25
24
56).
Recent
excellent surveys can be found in
12
49
In particular, the Mondrian process (MP) (55
54 and
48 have been proposed as new BNP models to expand the expressive classes of rectangular partitioning. However, both of them require an infinite number of parameters as intermediate random variables in the Aldous-Hoover Kaaleer-allenbergg (AHK) representation (an extension of de Finetti's ' theorem to multi-dimensionn the SBP representation for DPMM. As a result, Bayesian inference to those models always had to take care of an infinite number of parameters, which compromise the flexibility of local movements for the Markov chain Monte Carlo (MCMC) inference and make it highly affected by local optima and slow mixing problems. As natural question, we wonder if it is possible to marginalize out the infinite number of intermediate random variables of these models, as the CRP representation of DPMM. Unfortunately, an approach to achieve this has remained unsolved for long time.
the rectangular tiling process (RTP)
theorem g
34 37
arrays), similar to
This paper deals with the nulti-dimensional extension of CRP to represent wider classes of rectangular partitioning than regular grid partitioning. As an important stepping stone for this, the block- blck-breakinng process (BBP)
has been proposed very recently as a multi- multi-dimensional extension of SBP (Figure 1 (c)). The key insight for the BBP construction is that rectangular partitioning can be represented indirectly using permutations. Specifically, special class of permutations called Baxter permutation 133. which has one-to-one correspondence with particular class of rectangular partitioning, is used to extend the stick-breaking procedures of SBP for a sequence to the block-breaking procedures for a matrix (Figure 3). Although BBP can indeed be used as an infinitely exchangeable relational model, it requires an infinite number of redundant parameters, similar to SBP, making Bayesian inference highly affected by local optima and slow mixing problems. Therefore, CRP-like representation that avoids the infinite number of redundant parameters of BBP, analogous to the relationship between SBP and CRP for DPMM, has been desired. Our contributions are summarized as follows:
Construction of new stochastic process Section 3.1 proposes stochastic process such that each table of the CRP has random coordinates on [0. x 0]. Specifically, we suppose that the coordinates of each table is independent and identically distributed (i.i.d.) random variable drawn from a permuton 35 on [0, 1] x (0. 1]. Permuton is probabilistic measure on [0, 1] [0. 1] and can also be regarded as prior model for random permutations. By exploiting the correspondence between permutations and rectangular partitions [62 52), PCRP can be used as generative probabilistic

---

Figure 2: Several classes of rectangular partitions appear in this paper. The details of each class will also be described in the main body Section 2.1 Left: Regular grid partitioning. Each block is characterized by the product of the row and column clusters. Second from left: Hierarchical partitioning. Third from left: Hierarchical partitioning with one place deeper in each layer. Fourth from left: Diagonal rectangulation. Right: Generic rectangulation.
2314
25314
231
21
2
15
Figure 3: Illustration of BBP 477, which can be regarded as a multi-dimensional extension of SBP. First BBP uses Markov process Baxter permutations, and transforms the evolution of Baxter permutations to the evolution of floorplan partitioning (i.e., rectangular partitioning ignoring the size of each rectangle block) by using the one-to-one correspondence between Baxter permutations and floorplan partitioning 33 (Left). Next BBP uses the block- breck-nn procedures to sequentially assign the random size each rooms floorplan partitioning (Right).
model of rectangular partitioning of matrix. While BBP 47 (i.e., SBP) always has an infinite number of redundant intermediate variables, our PCRP can be composed of varying size (finite) intermediate variables in data-driven manner depending on the size and quality of the observation data. As a result, PCRP can lead to very flexible local movements in Bayesian inference, reducing the problems of local optima and slow mixing.
extension of
Unified framework for various classes of rectangular partitioning Conventionallly, the stochastic processes for each class of rectangular partitioning have been constructed individually. However, according to the design of the permuton, PCRP provides a unified framework for various classes of rectangular partitioning. Section 3.2 shows approach to tune the permuton of PCRP adapt it to various classes of rectangular partitioning.
New representation of BNP model As mentioned earlier, multi-dimensional extension of CRP is a historical conundrum, and thus PCRP does not provide a perfect solution to this issue. In Section 4 the theoretical imperfection of PCRP is clarified. Specifically, we intuitively explain that projectivity and exchangeability of PCRP change when viewed from two different perspectives: rectangular partitioning of matrix and table assignment of data. Thus, propose ENP model as a way to overcome this imperfection, that applies PCRP as bridging state to existing infinitely exchangeable relational models, inspired by the MCMC inference via bridging [2]
representation of the
Preliminaries
2.1 Permutation, permutation class and its relation to rectangular partitioning
Permutation and rectangulation A permutation of set S is defined bijection from S to itself. Specifically, this paper always focus on permutations of natural numbers = [n] := (1.2...., (n N). For convenience, For example, the permutation a = 312 means 0 = 3, d2 1, d3 2. A rectangulation (also called rectangular partitioning) is tiling of rectangle by finite number of disjoint rectangles such that no four of its rectangles share single corner. In recent years, it has become clear that there is close relationship between permutations and rectangulations. Here we focus in particular the fact that every permutation can be uniquely converted into a generic rectangulation (Figure 2 right), that is, the class of rectangulations without any constraints:
one-line notation for permutation
0102 ... Tn-
Proposition 2.1 (See Proposition 6.2 in 33 and Proposition 4.2 from permutations to generic rectangulations.
52 There a surjective map

---

Figure 4: Map from permutations (e.g., 34861725) to diagonal rectangulations [9] We first draw distinct diagonal points on the diagonal, with one of the points being the top-left corner and another being the bottom-right corner. We perform the following steps sequentially. Let R be the union of the rectangles drawn in the first - steps. To draw the ith rectangle, we consider the label i on the diagonal. If the diagonal point p on the diagonal immediately above left of the label i is not in R. then the upper left corner of the new rectangle is the rightmost point of R immediately to the left of p. If the diagonal point p immediately below or right of the label is not in R. then the lower right corner of the new rectangle is the highest point of I immediately below p. If is in Rt then the lower-right corner of the new rectangle the rightmost point of R. immediately to the right of p.
Edge
Wall
31861725
24851725
31128675
34128675
34861725 1725
Wall slides
34128675
Wall slides
Figure 5: Transformation from diagonal rectangulations to generic rectangulations (52). Left: Two notions, edge and wall. An edge of the rectangulation is a line segment contained in the side of some rectangles such that the endpoints of the line segment are vertices and the segment has no vertices in its interior. A wall of the rectangulation is a maximal union of edges forming a line segment. Middle and right: Two examples of mapping from permutations (c.g., o 34881723 and 34128675) to generic rectangulations. First, we convert the permutation to diagonal rectangulation. Then we assign the vertex on the walls the label of the block that contains that vertex as its own upper left or lower right corner. Finally. the order of the vertices on the wall will be rearranged according to the permutation. Specifically, vertices on the horizontal wall are aligned in permutation order from left to right, and vertices on the vertical wall are aligned in permutation order from bottom to top.
Fortunately, we can constructively obtain this map as the following two-stage transformation from permutation to general rectangulation by way of a diagonal rectangulation. A rectangulation is and
diagonal the interior of each rectangle has an area that intersects the diagonal. Figure and Figure 5 describe the details of the first and second steps, respectively. We use this transformation as an important component in our generative model of PCRP (in Section 3.1).
Permutation classes and rectangulation classes To investigate the properties of the permutation, focus on subsets of permutations as permutation classes. To identify permutation class, we introduce the notion of occurrences. We suppose that T and a are permutations of size k and n, respectively. The occurrences of pattern in a subsequence Ui.....,Ti, that is order- isomorphic to т, that is, for all indices s, E [k]. we have o,, < oi, > Ta < Tt. One way to characterize a permutation class is often to focus on what patterns (typically very short permutations) are not contained as occurrences in the permutations belonging to that class. Conventionally, various permutation classes have been studied in depth, however, here we would like to focus on several permutation classes that are particularly relevant to rectangular partitioning. The details of each class will be explained the supplementary material. It should be emphasized here that, surprisingly, permutations of particular class have a one-to-one correspondence with rectangulations of particular class. A brief list is given below. We will use this fact in Section 3.2 to show that PCRP can potentially serve a unified model for the various classes of rectangular partitioning.
2-clumped permutation: The 2-clumped permutations have bijection generic rectangulations (Figure right) [52. that no restrictions are required.
Baxter permutation: and twisted Baxter permutation: The Baxter permutations have bijection
to diagonal rectangulations (Figure 2 fourth from left) [62 5 32 which has a representative in which every rectangle's 's interior intersects the diagonal.
Separable permutation: Separable permutations have a bijection to hierarchical and diagonal rectangulations [59 5], subset of hierarchical partitioning (Figure second from left), which are

---

expressed as binary trees where nodes represent a vertical or horizontal separation of rectangle into two disjoint rectangles.
Separable skew-merged permutation: Separable skew-merged permutations have a bijection to a special subset of hierarchical partitioning, in partieular, those where only one rectangle is allowed to be further cut in each layer (Figure 2 third from left) [45]
2.2 Permuton
In this paper, introduce permuton 335 very useful tool for handling random permutations.
Before defining permuton, we begin with geometric interpretation a permutation (Figure (e) top). To a permutation a, we We first divide [0, 1] x [0, 1] into an n X grid of squares of size 1/n x 1/n. Then, we can define the density of %o on the square in the i-th row and j-th column to be the constant n if o, = j and O otherwise. Therefore,
associate probability measure % on [0, [0, 1] as follows.
can be regarded as a geometric representation of the permutation matrix of a. More generally, we define a permutonn to be probability measure y on [0. x [0, 1] with uniform
marginals (Figure (e) bottom): >((a, bj x [0. 1]] = a = >(00 1] (a, 6)) for all 0 < a <b< 1. We emphasize that, for any permutation σ, the corresponding probability measure %o
permuton. Specifically, the permutation a can be interpreted as the permuton given by the sum of Lebesgue area measures [35]: To (4) = n Ei= Leb([(i-1)) i/n] [[a(i) 1)/n, (i)/n) m]] n A), for all Borel measurable set of [0, 1] [0, 1J, where Leb(-) indicates the Lebesgue measure.
We will provide the intuition behind why permuton is useful in dealing with random permutations. We suppose that and are permutations of size & and n, respectively. We set oC := (nl/ (nl/k[(n - k)! # (occurrences
r in d}. Intuitively, occ(T, o) means the probability to find pattern in σ, when we take & elements uniformly at random in Similarly, if we replace permutation with permuton 7, we can consider the probability of occurrence of a pattern T: oCC(T,7) IP(u,,...: Ug form pattern r]. where 01,-..; ; ug i.i.d. points [0, 1] x [0, 1] drawn from the permuton 7, Now, a natural question is whether these two occ(T, o) and occ (T7)
are generally consistent. The following theorem gives us an answer to this question:
Theorem 2.2 (See, e.g., Theorem 2.5 (29] and Lemana 3.5 (35)) We consider a sequence of per- mutations 01, 02. ..., On.... of size tending to infinity n - c0. Then, we have "(a, - Y O for every т, occ T, on) + OCc(T, 7). Moreover, if T and a are permutations of size k and n, respec- rively, then (T)e(T, oce(T, Ta) S k(k 1)/2n.
As result, random permutations belonging to some class can be controlled by the limit of sequences of permutons. We use the permuton as a prior model for the PCRP table coordinates (in Section 3.1).
3 Permuton-induced Chinese restaurant process (PCRP)
This section proposes a new stochastic process, which is our main contribution this paper. First, we describe the stochastic process, PCRP, in terms of generative model and show how we can introduce the notion of the permuton into CRP to obtain model for rectangular partitioning. Next, we discuss how to design the permuton so that PCRP can represent some classes of rectangular partitioning.
3.1 Model description of PCRP from generative probabilistic point of view
PCRP is composed of input matrix, the concentration parameter v) > O, and the permuton 7, i.e., probability measure on [o. 1] x [o, 1]. The specific design of the permuton will be discussed in the next subsection, thus the reader may continue to read assuming, for example, 7()) = Leb ({-)) that is, the uniform distribution on [o, 1] x [o. 1]. The following four steps represent the overall picture of PCRP from the viewpoint of probabilistic generative model.
Step 1: Table assignment process of all row and column elements of the input matrix by single CRP (Figure 6 first and second from left) Each row (white triangle) and each column (black triangle) of the input matrix chooses either an existing table to sit at with probability S. +n) (L (1= 1, K) or new table with probability n/(S + 11), as in standard CRP D. where K is the total number of customers seated at the tables, S, is the number of
the number of tables, customers seated at the t-th table. If new table is chosen, we draw the coordinates of the table
5

---

Figure 6: Overview of permuton permuton-induced CRP, described in Section 3.1
on [0 x [0, 1] from the permuton y. Here, for simplicity, we show a model that delivers row and column elements to a single CRP. However, the model can be easily extended to use different CRPs for rows and columns as in the conventional IRM [88] (e.g., using the Chinese restaurant franchise [6]] where CRPs for rows and columns share common dishes).
Numbering the CRP tables and placement of customers the sides of rectangle (Figure 6, second and third from left) The CRP tables are numbered according to the vertical order of the coordinates, which leads perform this numbering each time we add a new table. Next, we consider a rectangle (referred to as the outer rectangle) and its main diagonal and divide it into K equal-sized line segments numbered 1.... K, from top left to bottom right. The customer corresponding to each row of the input matrix is moved to the left side position of the outer rectangle corresponding to the table number belongs to. Similarly, we move the customer corresponding to each column of the input matrix to the top side position of the outer rectangle corresponding to the table number it belongs to.
Step 2:
permutation a aI... ....K. Note that we recursively
Step 3: Transforming permutation to generic rectangulation (Figure [6] fourth and fifth from
left) We apply the map from permutations to rectangulations described in Proposition 2. (Figure 55d to the permutation derived from the PCRP table coordinates in Step 2. This transformation performed in two steps, first converting the PCRP table assignment (Step 1) to a diagonal rectangu- lation (Figure 6 fourth), and then converting it further to a generic rectangulation (Figure 6 right). As result, PCRP yields a random rectangular partition of the input matrix.
Intuitive interpretation of PCRP: We recall that PCRP consists of two components: (1) random table assignments all the row and column elements of the input matrix, and (2) random permutations represented by the table coordinates. The former table assignments serve to roughly group the rows and columns of the input data, and the latter random table coordinates serve transform those rough groupings into detailed rectangular partitioning. The practical advantage of PCRP is that when a new table of CRPs is added, it can be inserted into every possible place of the rectangular partition (with the consistency that the whole is rectangular partition). This allows us to eliminate the problem of the disadvantage of the conventional BBP, where the insertion of new rectangle is restricted to specific place in the lower right corner (Figure 3
3.2 Design of permuton to provide various representational capabilities to PCRP
In this subsection, we discuss how to specifically choose a permuton y restrict the rectangular partitions generated by PCRP to a specific class. We start with the simplest case of 7-) Leb f-)). called the uniform permuton 35 As well known, o a uniform random permutation of size n, then Yo,, converges in distribution to this uniform permuton. We recall here that every permutation can be transformed into some rectangular partition. Thus seems that PCRP with the uniform permuton can be used as probabilistic model for arbitrary rectangular partitioning. However, there is one crucial point to note: The mapping between permutations (a set of all permutations) and generic rectangulations is not one-to-one correspondence. This means that even if the random permutations are uniform, the corresponding random rectangular partitions they are transformed into are not uniform and have some bias. Namely, there are some biases in PCRP with the uniform permuton, such that some rectangular partitions are more likely to appear and some are less likely to appear. We could ignore this bias for practical use, but theoretically, it is essential to know how to eliminate it. We briefly introduce some permuton designs that are uniform for some class of rectangular partitioning. Here is brief list, and details are given in the supplementary material.
Hierarchical partitioning with one place deeper in each layer (Figure 2 form partitioning of this class can be obtained by restricting the random permutation of coordinates in
third from left) Uni-

---

the CRP tables to uniform separable skew-merged. If Tn is a uniform separable skew-merged permu- tation of size n, then Yo. converges in distribution a deterministic permutonn 7 (See, e.g., Theorem 3.3 and Section 3.2.1 12]). Intuitively, the permuton "y has an X-shaped density on [0, 1 x [0, 1).
Hierarchical and diagonal rectangulation (Figure 2 second and fourth from left) Uniform hierarchical and diagonal rectangulations can be expressed by uniform separable permutations. If on is uniform separable permutation of size n, then ,o, converges in distribution to the Brownian separable permuton
45).
Diagonal rectangulation (Figure 2 fourth from left) Uniform diagonal rectangulations can be expressed by uniform Baxter permutations. If on is a uniform Baxter permutation of size n, then Yo... converges in distribution to the Baxter permuton [8].
Generic rectangulation (Figure 2 right) - Too the best of our knowledge, there still no way to construct permuton that corresponds to 2-clumped permutations, which have a bijection to generic rectangulations. This means that it currently tricky to explicitly design a clever permuton that will always restrict its samples to 2-clumped permutations. One possible strategy is to relax the permuton itself to one that can generate a broad class permutations (e.g. 7-)) = Leb(t:))) and instead use rejection sampling to restrict the generated permutations so that they are actually 2-clumped. Details are given in the supplementary material.
4 Intermediate level representation between SBP and CRP
PCRP would be very useful in the practical use of relational data analysis due to the following two advantages. (1) The model itself adjusts the model complexity in data-driven manner according to the quality and size of the input data. (2) The design of permuton allows us to handle various classes of rectangular partitioning in unified manner. In this section, we explore the former point more deeply from the viewpoint of the theory of Bayesian nonparametrics. A precise explanation would require the notions of projective system, projectivity, and exchangeability, which are far from the scope of this paper. Therefore, we would like to focus on an intuitive explanation while providing a rigorous discussion in the supplementary material.
Motivation - As well as the standard CRP for sequence partitioning being an infinitely exchangeable model, PCRP also has projectivity and exchangeability in terms of the CRP table assignments of data. However, from the perspective of rectangular partitioning model in relational data analysis, the projectivity and exchangeability of PCRP, unfortunately, do not hold. The implications of this fact will be explained in terms of the practical intuition for relational data analysis. We consider a pair of matrices I C J C (1,22...., ) x {1, 2, ......... }. Namely, smaller matrix I is extraction of some rows and columns of a larger matrix J. As it turns out, the only theoretical imperfection of PCRP can be explained as follows: the random rectangular partitioning of the smaller matrix / that follows PCRP cannot be equivalent to the random rectangular partitioning of I when the random rectangular partitioning of the larger matrix J follows PCRP. In other words, PCRP does not have perfect self- self-similarrty according to the size of the data in terms of the rectangular partitioning model, but only in the imaginary object of the CRP table assignments. This implies that PCRP may have to tune its model complexity (c.g., the concentration parameter of CRP) according to the size of the data. Nevertheless, local optima and slow mixing problems in Bayesian inference have a more significant impact on the performance of the model. However, readers familiar with the theory of Bayesian nonparametrics may wish to have a BNP model that is strictly projective and exchangeable in terms of rectangular partitioning. For such readers, we also propose a new way to create an exact infinite exchangeable model while using PCRP. Specifically, we apply PCRP as bridging state to existing infinitely exchangeable relational models, inspired by the MCMC inference via bridging [4]
practical sense, we believe that this is not such a significant issue. Rather,
We are interested in a set of rectangular partitioning of a matrix I C (1.2...., } x (1, whose rows and columns are indexed by natural numbers. We consider probability measures 2 on (X,, 2 where X' is set of rectangular partitioning of a matrix (i.e., a constrained combinatorial space), and hope to find an exact BNP model (Figure 7 left). Needless to say, number of the various BNP models have actually been proposed as the exact BNP model μúξ_ including the IRM 38) the MP-based relational model (55) and the BBP-dased relational model [47]. However, conventionally, these exact BNP models have significantly struggled with local optima and slow mixing problems in Bayesian inference. For example, in the standard MCMC inference phase, we wish to sample
7

---

Pubbablll (3usity)
Px
Protabite (dmiity)
Prolahite (deestt))
apt (1 alp4
X1
3/1
29 00
Figure 7: Illustration of exact BNP model with bridging states. Left: Existing exact BNP model on rectangular partitioning X₁. Middle: PCRP on imaginary table assignments of data V/. Right: BNP model on extended space X2 Uy,. Sampling from u'X is equivalent to drawing samples (gray circles) from X₁ U U),, via the joint chain and discarding those (white circles) from 3/,
from the distribution x''x over a constrained combinatorial space X,. Typically, by using some local moves, we can derive a Markov chain with a transition matrix, which may have slow mixing or even be non-ergodic. To mitigate these issues, we propose to introduce auxiliary spaces to relax the local movements in combinatorial spaces and to connect different regions of the sample space where communication is difficult or impossible.
Exact BNP model with bridging states First, as the auxiliary space V/, we introduce the table assignments of by CRP and a set of coordinates on [0, 1] [0. 1] of the tables. The corresponding probability model ndy on (Y,, 2>)) should be PCRP described in the previous section (Figure 7 middle). Then, connecting the bridging state in the auxiliary space V/y with samples in X,, we consider the combined probability model over the union space XG U To address probabilistic models on the union space X, U ,/, we modify the previous probabilistic models μ'x and uy as follows: ( E 2 == ( (,)),) and j (: 2 == n (-n3)). For simplicity of notation, the modified probabilistic models ja'x and juy will be denoted original μax and byy in the following. Finally, we consider probabilistic model p4_ (Figure 7 right) in form of #4 cup'x + (1 a)jú where 0 S a S 1 is tunable real variable. Fortunately, we can treat this new model p!_ BNP model, that is, there uniquely exists projective limit of μd_ (I N N) (See the supplementary materials for details). In summary, the BNP model with bridging states has the following advantages: (1) The family (E can be treated in the same way as the usual BNP model, i.e., the model itself has self-similarity (self-consistency) regardless of the size of the observed inputs. (2) If we restrict the space of interest to X2 (i.e. forget about the auxiliary space V1). it becomes equivalent to the exact BNP model on rectangular partitions. More specifically, we have px(() = (1/a)u((-nn))
5
Application to relational data analysis
5.1 PCRP-based relational model and Bayesian inference
Relational model The PCRP-based relational model is applied to the input observation matrix Z z= =( (N M- We suppose that the input matrix Z consists of categorical elements, i.e., Z E (1.2...., D) (D E N). The generative model can be constructed as follows. First, a random table assignment is performed by a single CRP for all rows and columns of the input matrix (Step 1 described in Section 3.1.. We will denote by ri (E N) the index of the table to which the i-th row is assigned and by e [E N) the index of the table to which the j-th column is assigned. In the process of the table assignment by CRP, whenever new table is generated, random coordinates for that table on [0, 1] x [0, 1] will be drawn from permuton Y (Step 1). We will denote by Tue (E R22 the coordinates assigned the f-th table (t 2, ......... K), where K is the number of tables generated by CRP. With the PCRP table assignments T := (ri...., JNN, Ci...., CMr) and the PCRP table coordinates L == (LI,... Lx), they can be uniquely transformed into a rectangular partition of the input matrix Z (Step 2-3). For simplicity, we denote by R(T, L) the rectangular partition derived from T and L. Each block indexed by ie (E N) in the rectangular partition R(T, L) has latent Dirichlet random variable 02 ~ Dirichlet (Qw) (k: ........ K). where Qu = (Qu..... ... an) a D-dimensional non-negative hyper parameter. Each element Zi,, is drawn from the categorical distribution with the parameter (k(i,)) where k(i, j) indicates the block index to which the entry with the i-th row and the j-th column belongs. summary, it can be viewed as a problem of estimating PCRP table assignments T and PCRP table coordinates L, given the input matrix Z and the
8

---

01
Figure 8: Illustration of generating new table in Gibbs sampling. Left: Coordinates of existing K tables with customers already seated. Second from left: (K + 1) subsections that are candidates for the coordinates from which the new table will be generated. Third from left: Subsection (colored in gray) [e1, 12] x [h1, h2] chosen as the location where the new table will be generated. Right: Coordinates of the new table (colored in dark gray) drawn from permuton 7(11, d2] (h1, h2)).
hyper- peer-parameters: permuton 7, Dirichlet distribution parameters ag 0, and concentration parameter of PCRP1) 17 > 0.
Bayesian inference The PCRP relational model can lead to very simple inference algorithms based on the MCMC methods. Following the generative model described above, the joint probability density is expressed as follows:
K [
Pperm (Lr 1n)) Poba. (Z R(T, L), ao),
(Z,TT, T L 7,00, 11) PCRP (T) 1))
where the first term PCRP (T) 17) is the probability distribution for the standard CRP, the second term Pperm. (L1 7) is the probability density that L, is drawn from the permuton y, and the third term is
r(Dav) r(Dao + Ed Nk.d)
I(ao +Naaa) II d=1 I(an)
Pobs. (Z ([(T,,)) an)
II 1=1
where Na.d denotes the number of elements in both the k-th block and the d-th category of the categorical distribution. The overview of the MCMC inference algorithm to simulate the above joint probability by scquentially updating the table assignments T and the table coordinates L.
One simple question is whether PCRP can construct Gibbs sampling in updating table assignments like the usual CRP. Fortunately, PCRP can lead to Gibbs sampling. Updating table assignments for rows and columns involves assigning them to existing tables or generating a new table, similar to the standard CRP. Calculating the probability of the former is straightforward, whereas calculating the latter, i.e., the probability of generating a new table, requires little more care. Figure shows an illustration of the case where new table is generated in Gibbs sampling. We suppose that there are currently tables. The posterior probability of choosing new table depends on random coordinates of that table and the random rectangular partition derived from it, which has at most (K + 1)² cases of new rectangular partitions. Specifically, for each of the K tables on [0, 1] x [o, 1]. draw a horizontal and vertical crosshair line, respectively, divide [0, 1] x [0, 1] into (K + 1)a subsections (Figure g second). The probability of the new table's coordinates falling into each of those (K + 1)a subsections
be calculated using Equation (). Therefore, the sum of those probabilities can be regarded as the probability that the new table will be generated. This can be calculated exactly without any approximation. Therefore, the conditional posterior distributions for r; and C can be calculated explicitly, and Gibbs sampling can be easily performed. The whole MCMC algorithm will be discussed in the supplementary material. Our code will be available iiw.itoon-iiuuudcrprpp
https:/ wtt.gttb.../tttsllaaaaeeeeeeee
5.2 Experimental evaluation
We compare PCRP with the existing BNP models for rectangular partitioning. IRM 38 MP [55]
RTP 48
and BBP 47].
The detailed experimental setup described the supplementary material.
Datasets Four social network datasets [40] Wiki Facebook (2]. Twitter [3, and Epinions
All data is public and does not contain any personally identifiable information (See [4] for license). We selected the top 1000 active nodes based on their interactions with others; subsequently we randomly sampled 500 x 500 matrix to construct the relational data, as in 25 47). We held
out 20% cells of the input data for testing, and each model was trained by the MCMC using the

---

BBP
BBP
BEP
BBP RTP
1.80
RTP
RTP
+ RTP
MP
MP
+ MP
MP
1.34
IPM
PCRP
Perpeen
++MM PCRP
+ORO
+IRM
1.45
+FM FORP
1.3
14
10
10"
10'
10"
10
10"
10"
Logardirn wwd.clocc
wwwd-chldd Iirm
Logariton coul-clock
Lugaritte of cockkdock
Wiki data
Facebook data
Twitter data
Epinion data
Figure 9: Experimental results of perplexity comparison for four real world data, relationship between test perplexity (mean=tstd) evolution and logarithm of wall-clock time.
Wiki data
Facebook data
Twitter data
Epinion data
Figure 10: Four examples of analysis results for each data by BBP (Top) and PCRP (Bottom).
remaining 80% of the cells. We evaluated the models using perplexity criterion: perp (xo(-(log p( (2) E), where E is the number of non- non-missing cells in the partitioned matrix Z.
Experimental results We ran 10 trials of analysis for each method on each data set. Figure summarizes the test perplexity comparison results. We recall that IRM and MP are limited in the class of rectangular partitions they can represent, and only PCRP, BBP, and RTP can represent arbitrary rectangular partitioning. Indeed, it can be seen that these arbitrary rectangular partitioning models have good prediction accuracy when MCMC converges. Among them, PCRP in particular achieves the best prediction accuracy for all the data. As another perspective, BBP. RTP, and MP are SBP-type models, while PCRP and IRM are CRP-type models. can seen PCRP improves the perplexity from an early stage compared to SBP-like methods. In light of the above, can confirm that PCRP can reduce the problems local optima and slow mixing in Bayesian inference. As shown in Figure 10 BBP extracts very biased rectangular partition due to the fact that the addition of new blocks tends to occur in the lower right corner. In other words, BBP only has a high probability adding blocks the lower right, so if coarse cluster is created in the upper left, will be difficult modify the coarse cluster into fine one. On the other hand, PCRP has the flexibility to add new blocks to the entire area, so it can properly find coarse and fine clusters in the entire area.
6 Conclusion and Discussion
Summary This paper has proposed new stochastic process for relational data analysis. Our main contributions are as follows: (1) We introduce the notion of the permuton the CRP and obtain probabilistic model of rectangular partitioning of matrix. (2) We show a unified framework for PCRP various classes of rectangular partitioning based on the design of the permuton. (3) We discuss the theoretical imperfection of PCRP for projectivity and exchangeability in terms of rectangular partitioning and propose a new representation the BNP model as way to overcome this imperfection that applies PCRP bridging state to existing BNP relational models.
10

---

Funding disclosure
Funding in direct support of this work is NTT Corporation, without any third party funding.
References
[1]
[2] http://aagsssaartt.cccdo02141112
[5] Ackerman, E., Barequet, G., Pinter, Y.Y.: A bijection between permutations and floorplans, and its applications. Discrete Applied Mathematics 154(12), 1674-1684 (2006)
[6] Adams, R.P. Jordan, M.I. Ghahramani, 7.: Tree-structured stick breaking for hierarchical data. In: Lafferty, J., Williams, C., Shawe-Taylor, J., Zemel, R., Culotta, A. (eds.) Advances in Neural Information Processing Systems. vol. 23, Curran Associates, Inc. (2010)
Airoldi, E.M., Costa, T.B., Chan, S.H.: Stochastic blockmodel approximation graphon: Theory andconsistent estimation. In: Advances in Neural Information Processing Systems (2013)
[8] Aldous. DJJ.: Representations for partially exchangeable arrays of random variables. Journal Multivariate Analysis 11. 581-598 (1981)
[9] Aldous, DJJ.: Exchangeability and related topics. École d' d'Été St Flour, Lecture Notes in Mathematics 1117, 198 (1985)
[10] Bassino, F., Bouvel, M., Feray, V., Gerin, L., Maazoun, M., Pierrot, A.: Universal limits of substitution- closed permutation classes. Journal of the European Mathematical Society 22(11), 3565-3639 (2019)
[11] Bassino, F., Bouvel, M., Féray, V., Gerin, L., Pierrot, A.: The Brownian limit of separable permutations. The Annals of Probability 46(4), 2134-22189 (2018)
[12] Bassino, F., Bouvel, M., Féray, V., Gerin, L.., Maazoun, M., Pierrot, A.: Scaling limits of permutation classes with finite specification: dichotomy. arXiv:1903.000 1903.07222 (2019)
[13] Baxter, G.: On fixed points of the composite of commuting functions. Proceedings of American Mathemat- ical Society 15, 851 855 (1964)
[14] Blei. D., Frazier, P.: Distance dependent Chinese restaurant processes. In: International Conference Machine Learning (2010)
[15] Blei, D., Frazier, P:: Distance dependent Chinese restaurant processes. Journal of Machine Learning Reseach 12, 2461-2488 (2011)
[16] Blei, D.M., Jordan, M.I., Griffithss T.L., Tenenbaum, J.B.: Hierarchical topic models and the nested Chinese restaurant process. pp. 17-24 (2003)
[17] Blei, D.M., Griffiths, Jordan, M.I.: The nested Chinese restaurant process and Bayesian nonparametric inference of topic hierarchies. J. ACM 57(2) (2010)
[18] Borga, J., Maazoun, M.: Scaling and local limits of Baxter permutations and bipolar orientations through coalescent-walk processes. 2r0iv:2008. 09086 (2020)
[19] Caldas, J., Kaski, S.: Bayesian biclustering with the plaid model. In: 2008 IEEE Workshop on Machine Learning for Signal Processing, pp. 291-296 (2008)
[20] Choi, D.S., Wolfe, P.I.: Co-clustering separately exchangeable network data. Annals of Statistics 42, 29-63 (2014)
[21] Fan, X., Li, B., Sisson, S.A.: The binary space partitioning-tree process. In: International Conference on Artificial Intelligence and Statistics, pp. 1859-1867 (2018)
[22] Fan, X., Li, B., Luo, L.,, Sisson, S.A.: Bayesian nonparametric space partitions: A survey, arXiv:2002. 1394 (2020)

---

[23] Fan, X., Li, B., Sisson, S.: Rectangular bounding process. In: Advances in Neural Information Processing Systems. pp. 7631-7641 (2018)
[24] Fan, X., Li, B., Sisson, S.A.: Online hinary space partitioning forests, arXiv:2003.00669 (2020)
[25] Fan, X., Li, B.. Sisson, S.A.: Binary space partitioning forests. arXiv:1903.09244 (2019)
[26] Fan, X., Li, B., Wang, Y. Wang. Y., Chen, F: The Ostomachion Process. In: AAAI Conference on Artificial Intelligence, pp. 1547-1553 (2016)
[27] Ferguson, T.: Bayesian analysis of some nonparametric problems. Annals of Statistics 2(1). 209-230 (1973)
[28] de Finetti, B.: Funzione caratteristica di un fenomeno alcatorio. Memorie della R. Academia Nazionale dei Lincei 4(5), 251-299 (1930)
[29] Frédérique, B., B. Mathilde, F.V., Lucas, G., M. Mickaël, P.A.: Universal limits of substitution-closed permutation classes. Journal of European Mathematical Society 22, 3565-3639 (2020)
[30] Ge, S., Wang. Tch, Y.W., Wang, I.., Elliott, L.: Random tessellation forests. In: Advances in Neural Information Processing Systems 32. pp. 9575 9585 (2019)
[31] Ghosh, S., Ungureunu, A., Sudderth, E., Blei, D.: Spatial distance dependent Chinese restaurant processes for image segmentation. In: Advances in Neural Information Processing Systems (2011)
[32] He, B.D.: simple optimal binary representation of mosaic floorplans and Baxter permutations. Theoretical Computer Science 532(1), I), 40-50 (2014)
[33] Hong, X., Huang, G., Cai, Y., Gu, J., Dong, S., Cheng. C., Gu, J.: Corner block list: an effective and efficient topological representation of non-slicing floorplan. In: Proceedings of the IEEF/ACM International Conference Computer-Aiin Aided Design (2000)
[34] Hoover, D.N.: Relations on probability spaces and arrays of random variables. Tech. rep., Institute of Advanced Study, Prineeton (1979)
[35] Hoppen, C.,, Kohayakawa, Y., Moreira, C.G., Ráth, B., Sampaio, R.M.: Limits of permutation sequences. Journal of Combinatorial Theory, Series B 103(1), 93 -113 (2013)
[36] Ishiguro, K., Sato, I,, Nakano, M., Kimura, A., Ueda, N.: Infinite plaid models for infinite bi-clustering, pp. 1701-1708 (2016)
[37] Kallenberg. O.: Symmetries on random arrays and set-indexed processes. Journal of Theoretical Probability 5(4), 727-765 (1992)
[38] Kemp, C., Tenenbaum, J.B., Griffiths, T.L.,, Yamada, T., Ueda, N.: Leamingg systems of concepts with an
infinite relational model. In: AAAI Conference on Artificial Intelligence, pp. 381-388 (2006)
[39] Law, S., Reading, N.: The hopf algebra of diagonal rectangulations. Journal of Combinatorial Theory, Series A 119(3), 788-824 (2012)
[40] Leskovec, J., Huttenlocher, D., Kleinberg, Predicting positive and negative links in online social networks. In: Proceedings of the 19th International Conference on World Wide Web. pp. 641-650 (2010)
[41] Leskovee, J., Krevl, A.: SNAP Datasets: Stanford large network dataset collection. http://snap snap
stanford. www//ddutaaa. (Jun 2014)
[42] Lin, D., Fisher. J.: Efficient sampling from combinatorial space via bridging. In: International Conference on Artificial Intelligence and Statistics (2012)
[43] Lloyd, J., Orbanz, P., Ghahramani, Z., Roy, D.M.: Random function priors for exchangeable arrays with applications to graphs and relational data. In: Advances in Neural Information Processing Systems (2012)
[44] Lovász, L.: Very large graphs. Current Developments in Mathematics 11, 67-128 (2009)
[45] Maazoun, M.: On the brownian separable permuton. Combinatorics, Probability and Computing 29(2). 241-266 (2019)
[46] Miller, K. Jordan, M.I., Grifliths, T.L.: Nonparametric latent feature models for link prediction. pp. (2009)
12

---

[47] Nakano, M., Kimura, A., Yamada. T., Ueda, N.: Baxter permutation process. In: Advances in Neural Information Processing Systems (2020)
[48] Nakano, M. Ishiguro, K., Kimura, A., Yamada, T., Ueda, N.: Rectangular tiling process. In: Proceedings of the st International Conference Machine Learning. Proceedings of Machine Learning Research, vol. 32, pp. 361-369 (2014)
[49] Orbanz, P., Roy, D.M.: Bayesian models of graphs, arrays and other exchangcable random structures. IEEE Transactions Pattern Analysis and Machine Intelligence 37, 437-461 (2013)
[50] Pitman, J. Yor, M.: The two-twrooe woo-parameter poisson-dirichlet distribution derived from stable subordinator. IBM Journal of Research and Development 2(25), 855-900 (1997)
[51] Rasmussen, C.: The infinite gaussian mixture model. In: Advances in Nueral Information Processing Systems (2000)
[52] Reading, N.: Generic rectangulations. European Journal of Combinatorics 33(4), 610-623 (2012)
[53] Rodriguez, A., Ghosh, K.: Nested partition models. Tech. rep., JackBaskin School of Engineering (2009)
[54] Roy, D.M.: Computability, inference modeling in probabilistic programming. Ph.D, thesis, Mas- sachusetts Institute of Technology (2011)
[55] Roy, D.M., Tch, Y.W.: The Mondrian process. In: Advances Neural Information Processing Systems (2009)
[56] Saad, F.A., Mansinghka, V.K.: Hierarchical infinite relational model. In: Praceedings of the 37th Confer- ence on Uncertainty in Artificial Intelligence, AUAI Press, Arlington, VA, USA (2021)
[57] Sethuraman, J.: A constructive definition of Dirichlet priors. Statistica Sinica 4, 639-650 (1994)
[58] Shan, H., Banerjee, A.: Bayesian co-clustering. In: IEEE International Conference Data Mining, pp. 530-539 (2008)
[59] Shen, Z.C., Chu, C.C.N.: Bounds the number of slicing, mosaic, and general floorplans. IEEE Transactions Computer-Aided Design of Integrated Circuits and Systems 22(10). 3544-366 (2003)
[60] Tan, X., Rao, V., Neville, J.: Nested with wowkes-gaussian processes. In: Storkey, A., Perez- Cruz, F. (eds.) Proccedings of the Twenty-Fing First International Conference Artificial Intelligence and Statistics. Proceedings of Machine Learning Research, vol. 84, pp. 1289-1298 (2018)
[61] Tch, Y.W., Jordan, M.I., Beal, M., Blei, D.: Hicrarchical Dirichlet processes. Journal of the AmericanSta- tistical Association 101, 1566-1581 (2006)
[62] Yao, B., Chen, H., Cheng, C.K., Graham, R.I.: Floorplan representations: Complexity and connections.
ACM Transactions Design Automation of Electronic Systems 8(1). 55-80 (2003)
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes] See Section T We have clarified the main contributions of this paper under three headings.
(b) Did you describe the limitations of your work? [Yes] See Section 4 We have simul- tancously clarified the technical imperfection of our proposed PCRP and proposed a reasonable proposal to solve it.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See Ethical perspective in Supplementary material.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Section 4 is an intuitive sketch of the theoretical results. Details are given in the supplementary material.
13

---

(b) Did you include complete proofs of all theoretical results? [Yes] See Supplementary material.
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See experimental settings in Supplementary material
(c) Did you report error bars (e-g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, or cloud provider)? [Yes] See experimental settings in Supplementary material
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] See Relational models in Section 5
(b) Did you mention the license of the assets? [Yes] See Datasets Section
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [Yes] See Datasets in Section 5
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [Yes] See Datasets in Section
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "oQtU0owlgFk", "reviewer": "Reviewer_sbRq", "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. ", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nThe presentation is very clear and the figure visualisation helps a lot in understanding the related processes. \n\nI 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:\n1, 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?\n\n2, 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?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}, {"review_id": "k8JtmgD7hnG", "reviewer": "Reviewer_hdxZ", "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. \n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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$. \n\nI 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.\n\n- 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?\n- 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? \n- 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?\n\n\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7 hours"}, "extra_text": {}}, {"review_id": "jj4CEsso9H3", "reviewer": "Reviewer_rRnG", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I have a concern with the quality of the paper. \n\nOriginality. 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. \n\nQuality. (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. \n\nQuality (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. \n\nClarity. 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.\n\nSignificance. The PCRP has the potential to add to the Bayesian nonparametrics a model over rectangular partitions with more flexible sample paths.\t", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.25"}, "extra_text": {}}, {"review_id": "gTi0HBFafVE", "reviewer": "Reviewer_NeZe", "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.\nA Permuton is a probability measure on [0, 1]\u0002x [0, 1], which can be regarded as a geometric interpretation of the\nscaling 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.\nExperiments involve the application of PCRP to Bayesian nonparametric (BNP) relational data and there are some promising results showcased.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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\n\nQuality: The submission is technically sound justified by theoretical analysis and experimental results. This is a complete piece of work\n\nClarity: The submission is clearly written.\n\nSignificance: 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.\n\n** Comments\n* Can PCRP handle continuous distributions as opposed to a multinomial/Dirichlet distribution?\n* How would PCRP behave with an asymmetric Dirichlet prior? \n* What are the conditions under which PCRP partitions data to mostly the same partition?\n\n** Minor comments\n* Figure 9: It would be helpful if the details of the ‘hidden fine clusters’ can be highlighted. What does ‘hidden’ mean in this context?\n* 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. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, limitations have been discussed", "review_text": "", "extra_scores": {"ethical_concerns": "Ethical concerns have been discussed", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "9iL383dzGTY", "reviewer": "Reviewer_5pQM", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1 hour"}, "extra_text": {}}]

Author rebuttal:

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)