Continuous Conditional Random Field Convolution for Point Cloud Segmentation

Point cloud segmentation is the foundation of 3D environmental perception for modern intelligent systems. To solve this problem and image segmentation, conditional random fields (CRFs) are usually formulated as discrete models in label space to encourage label consistency, which is actually a kind of postprocessing. In this paper, we reconsider the CRF in feature space for point cloud segmentation because it can capture the structure of features well to improve the representation ability of features rather than simply smoothing. Therefore, we first model the point cloud features with a continuous quadratic energy model and formulate its solution process as a message-passing graph convolution, by which it can be easily integrated into a deep network. We theoretically demonstrate that the message passing in the graph convolution is equivalent to the mean-field approximation of a continuous CRF model. Furthermore, we build an encoder-decoder network based on the proposed continuous CRF graph convolution (CRFConv), in which the CRFConv embedded in the decoding layers can restore the details of high-level features that were lost in the encoding stage to enhance the location ability of the network, thereby benefiting segmentation. Analogous to the CRFConv, we show that the classical discrete CRF can also work collaboratively with the proposed network via another graph convolution to further improve the segmentation results. Experiments on various point cloud benchmarks demonstrate the effectiveness and robustness of the proposed method. Compared with the state-of-the-art methods, the proposed method can also achieve competitive segmentation performance.

Introduction
A conditional random field (CRF) is a kind of probabilistic graphical model (PGM) that is widely employed for structure prediction problems in computer vision. In image segmentation, most previous studies have attempted to model the data affinity in label space with CRFs, where the CRF is formulated as a discrete model. Such a discrete model is usually NP-hard to solve. Nevertheless, some approximate methods have been proposed to solve discrete CRF models efficiently. The most widely used approximate methods in computer vision are α-expansion/αβ-swap [1] and mean-field approximation [2]. The former is a graph-cut-based method, and the latter belongs to the variational inference-based method. With the rapid development of deep learning techniques, mean-field approximation methods have attracted more attention in the community because the mean-field approximation can be easily embedded in a deep network to build an end-to-end architecture [3]. Despite these, discrete CRFs that encourage label consistency in the results can only smooth the object boundaries and remove some small noises. The misclassified object regions in the prediction stage are hard to correct by these kinds of postprocessing CRFs.
Convolutional neural networks (CNNs) have achieved significant success in image, speech, and natural language processing (NLP). However, with the explosion in 3D data such as point clouds, traditional CNNs that are designed for grid-like data can no longer meet all the needs. On the one hand, the point cloud data acquired by 3D sensors are usually large-scale, sparse, and unordered, which is difficult to process with traditional CNNs directly. On the other hand, point cloud segmentation is the foundation of 3D environmental perception in modern intelligent systems, such as intelligent robotics and autonomous driving cars. Therefore, segmenting point clouds with deep learning techniques is an urgent challenge in modern computer vision. Although many deep learning-based methods [4,5,6] have been proposed to segment point clouds, they focus on the design of the feature extractor to improve the representation ability of the point features. Segmentation consists of two parts: classifying (what it is) and locating (where it is). For classification tasks, we only need to encode the high-level features, and focus less on where the extracted features should be. The classification result can be inferred from only a single global vector. However, segmentation is a dense prediction task. We need to not only extract the high-level features (what it is) but also restore the correspondence between the encoded high-level features and each input point exactly (where it is). The restoration process can be understood as solving the problem of where it is. In other words, previous studies attempted to make the network understand what it is but failed to investigate the problem of where it is. Currently, the research on feature decoding is scarce in the literature. To fill this gap, we focus our study on feature decoding rather than feature encoding, considering that the feature encoding methods targeting a classification task are competent for a segmentation task.
To address the problems mentioned above, we reconsider the CRF in feature space to enhance the location ability of the network during feature decoding. Segmentation is a typical structure prediction problem. To address this problem, the CRF is usually formulated as a discrete model to encourage label consistency in the results, which can only smooth the object boundaries and remove some small noises. Inspired by the continuous CRF used for depth completion, we reconsider the CRF as a continuous model in feature space to restore the encoding features for point cloud segmentation. The CRF is enforced to participate in the feature extraction process of the point cloud and thus can fundamentally improve the representation ability of the features rather than just smoothing the labels by postprocessing. Specifically, previous methods usually adopt the kNN (k-nearest neighbors)-based interpolation method to decode high-level features. They roughly place the high-level features at their closest positions during upsampling but ignore the consistency of features in feature space. The details of the high-level features will be lost in such an upsampling process. There is an intuitive assumption that similar points in low-level feature space should also have similar high-level features. Therefore, we employ the CRF model to guide the feature upsampling procedure to restore the details of high-level input point features gradually. In our continuous CRF model, the low-level features in the encoding layers are used as guidance information to guide the high-level feature upsampling. This process has a similar effect to guided filtering, such as joint bilateral filters.
In this paper, we propose a continuous CRF graph convolution (CRFConv) to capture the feature structures during the feature extraction stage. More precisely, we propose using a continuous quadratic energy model to describe the point cloud in feature space, in that a continuous CRF model is mathematically equivalent to a quadric energy model that has a similar form to the diffusion model. Inspired by some diffusion-based graph convolution methods in the community, we formulate the solution process of this model as a message-passing graph convolution, by which the continuous CRF can be embedded in the network for feature extraction. From a CRF perspective, we also prove that the message passing of this graph convolution is equivalent to the mean-field approximation algorithm of a continuous Gaussian CRF model, which indicates that the proposed graph convolution is actually equivalent to a continuous CRF model. After that, we build an encoder-decoder network for point cloud segmentation, in which the decoding modules are carefully designed based on the proposed CRFConv. We use the proposed CRFConv to enhance the location ability (where it is) of the network as described above. To enlarge the receptive field, the extracted high-level features in the encoder lose details by successive pooling/downsampling operations. Previous methods only upsample the high-level features with simple linear interpolation in the decoding layers, while our method models the upsampling process with a structure model (i.e., the CRFConv), by which the details of the high-level point cloud features can be restored gradually. Furthermore, we show that our continuous CRF can also work collaboratively with the classical discrete CRF to further improve the segmentation results. The discrete CRF is formulated as another message-passing graph convolution by analogy to the CRFConv, by which the discrete CRF can be embedded in our segmentation network to implement an end-to-end dual CRF network. To the best of our knowledge, we are the first to consider CRF models both in feature and label space simultaneously in point cloud segmentation.
Experiments on various datasets, including object-level and scene-level segmentation tasks, demonstrate the ef-fectiveness of the proposed method. The contributions of this paper can be summarized as follows: 1 1. We propose a continuous CRF graph convolution (CRFConv) to model the data affinity in feature space instead of label space, which enforces the CRFConv to participate in the point cloud feature extraction process. The CRFConv can thus fundamentally improve the representation ability of the features rather than just smoothing the labels by postprocessing. 2. We design a point cloud segmentation network based on the proposed CRF convolution to enhance the location ability of the network. The CRFConv is embedded in the network decoder to model the upsampling process with a continuous CRF model, by which the details of the high-level point cloud features can be restored gradually during upsampling. 3. We further implement a dual CRF network by reformulating the classical discrete CRF as another graph convolution. The dual CRF network models the data affinity both in feature space and label space simultaneously to further improve the segmentation results. 4. We conduct experiments on various challenging point cloud segmentation benchmarks, including synthetic object data and large-scale indoor and outdoor scenes. The experimental results demonstrate the effectiveness and robustness of the proposed method.
The rest of this paper is organized as follows. In section 2, we review the literature and introduce some related basic knowledge about CRF. The continuous CRF graph convolution and theoretical analyses are presented in section 3. In section 4, we present the architecture of the segmentation network in detail and show how to combine the continuous CRF with the classical discrete CRF in our segmentation network. The experimental results, comparisons, and ablation analysis can be found in section 5. Section 6 concludes the work in this paper, in which the limitations and future works are also discussed.

Point cloud segmentation
With the popularity of 3D sensors, 3D data are exploding in human daily life owing to their easy acquisition.
One key application of 3D data is point cloud segmentation, which is the foundation of 3D environmental perception. Considering the success of CNNs in image processing, many researchers have attempted to employ deep learning techniques to segment point clouds [7]. In this section, we only review the point cloud segmentation methods based on deep learning. These methods can be divided into four categories: image-based, voxel-based, point-based, and graph-based methods.
Image-based methods convert the point cloud as an image-like representation and employ some image-based networks to process the point cloud. For example, Yang et al. [8] projected LiDAR (light detection and ranging) points to the image plane by the cross-calibration parameters. Instead of converting the LiDAR point cloud to the image plane, Wu et al. [9] projected the LiDAR point cloud to a sphere plane to form a dense and grid-based representation. An alternative solution for 3D point cloud representation is the multiview-based method [10]. In other words, the image-based methods convert the 3D point cloud to a 2D grid-like representation to cater to image-based networks. The structural information of the point cloud will inevitably be lost during such conversions.
Voxel-based methods borrow ideas from image-based CNNs. In these methods, the point cloud is first split into uniform voxels and then processed by deep 3D networks. Maturana et al. proposed VoxNet[11], an architecture to segment point clouds by integrating a volumetric occupancy grid representation with a supervised 3D CNN. However, the voxel-based presentation for a point cloud is usually time consuming and space wasting. To address this problem, Octree [12] and Kd-Tree [13]-based approaches have been proposed to save computations by skipping convolution in empty space. Nevertheless, voxel-based representation methods still cause information loss. In addition, it is difficult to balance computations and accuracy. How to determine the voxel resolution for the point cloud, which varies in density, remains a problem.
Point-based methods overcome the shortcomings of image-based and voxel-based methods. The unordered and sparse points can be directly processed by point-based methods without transformations. PointNet [4] was the first work to directly process the points in point clouds with deep learning techniques. Since Qi et al. pioneered this field, many point-based methods have emerged in the community. For example, Qi et al. further extended their PointNet to PointNet++ [14], which is a hierarchical version of PointNet. Li et al. [5] learned a χ-transformation to transform the point cloud to a latent and potential canonical order, by which the typical convolution operator can be applied on the χ-transformed features. [15,16] defined the convolution on point cloud domains using Monte Carlo. Thomas et al. [6] proposed the kernel point convolution (KPConv) inspired by the convolution operator on regular domains. Recently, the attention mechanism was also explored to extract the point features for point cloud segmentation in [17] and [18].
Graph-based methods have also been extended to process point clouds with the advent of graph neural networks (GNNs) in recent years. In these methods, they assume that a latent graph exists in the point cloud (e.g., kNN or radius graph). Landrieu et al. [19] first presegmented the point cloud to superpoints using an unsupervised cluster algorithm. Then they built a superpoint graph based on the superpoint features extracted by PointNet to segment the point cloud. Wang et al. [20] proposed EdgeConv, which is dynamically computed in each layer of the network, for high-level tasks on point clouds. DeepGCNs [21] extended graph convolutional networks (GCNs) to deep models by borrowing concepts from CNNs, specifically residual/dense connections and dilated convolutions. DeepGCNs have also shown their ability on large-scale 3D point cloud segmentation tasks.
Point-based and graph-based methods can both be categorized as geometric deep learning (GDL) [22] methods. GDL has shown its advances in processing point clouds. In this paper, the proposed method is also a kind of GDL method. However, previous methods focus on improving the classification ability of the network but ignore its location ability, which is crucial for segmentation. Our work focuses on the decoding rather than the encoding of the point features to enhance the location ability of the network, which is the most different point from existing methods.

Conditional random field
In this section, we first review some basic knowledge about CRF for the convenience of readers who are not familiar with this field. Then, we review the applications of CRFs in computer vision, including but not limited to point cloud processing. Basic knowledge. Let G(V, E) be an undirected graph, where V and E represent the node and edge sets of the graph, respectively. Denote x i as a random variable defined on node i ∈ V. e(i, j) ∈ E can be understood as the relationship between the random variables x i and x j . Thus, X = {x i |i ∈ V} can be viewed as a random field on G. If the random variables of X in G satisfy the Markov property, then we call X a Markov random field (MRF) on G. According to the Hammersley-Clifford theorem, the joint probability distribution of the MRF can be presented with a Gibbs distribution parameterized by the clique potentials defined on G, that is: where c and X c denote a maximum clique (complete subgraph) of G and its associated random variable, respectively. C G is the set of all cliques. φ c is the clique potential defined on c. Z is a partition function to ensure a distribution. Note that φ c is constrained to be nonnegative in the Gibbs distribution. In general, we can transform φ c (X c ) to its log space. Specifically, we let φ c (X c ) = exp(−ψ c (X c )), where ψ c (X c ) = − log φ c (X c ) denotes the energy function defined on c. Hence the Gibbs distribution can be simply rewritten as: where E(X) = c∈CG ψ c (X c ) is the Gibbs energy function defined by all cliques of G. Eq. (2) is a log linear model, which ensures a positive distribution. The MRF can also be used to describe a conditional distribution. Given another random variable Y, if the random variable X on G is conditional on Y, we say the MRF determined by X is a CRF determined by X and Y. The conditional distribution P(X|Y) of the CRF can also be represented with a Gibbs distribution, which has the same form as Eq. (2). Y and X can be viewed as the observed and latent variables in the CRF, respectively. In other words, the CRF of X and Y can be understood as the MRF of X with an additional input Y. For notational convenience, we omit the condition Y in the rest of the paper when we refer to CRF. Applications. CRFs/MRFs are widely applied to image segmentation for structure prediction as a kind of postprocessing. Krähenbühl et al. [23] proposed the fully connected CRF for image segmentation for the first time. The fully connected CRF also acts as a postprocessing step of a CNN in [24] to improve the localization accuracy. In addition, Zheng et al. [25] extended the fully connected CRF as a recurrent neural network (RNN) for object segmentation. Qiu et al [26] also integrated the CRF into a CNN to segment saliency objects. Although these methods allow us to jointly train the CNN and the CRF model end-to-end, the CRF still acts as postprocessing in the pipeline. In contrast to the existing approaches that use discrete CRF models, Vemulapalli et al. [27] proposed using a Gaussian CRF model for semantic segmentation instead, in which the CRF is still built in the label space to refine the labels. In addition to image segmentation, the application of CRFs/MRFs for point cloud segmentation is also explored. Wu et al. adopt a CRF model as in [24] to refine the output of their SqueezeNet [9]. Our continuous CRF model is different from discrete CRFs that usually act as postprocessing to refine the labels. We model the data affinity in feature space with a continuous CRF that essentially participates in the feature extraction process of the point cloud. Hence, our CRF can fundamentally improve the representation ability of the features rather than only smoothing the labels in postprocessing.

The continuous CRF graph convolution
In this section, we present the CRF graph convolution from a continuous quadratic energy model in the feature space of a point cloud. First, we present how to formulate its solution process as a message-passing algorithm in a graph defined on the point cloud. Then we define the continuous graph convolution based on this message-passing algorithm. Finally, we conduct a theoretical analysis of the proposed graph convolution from a CRF perspective.

The continuous quadratic energy model
is the position vector of point i in the 3D Euclidean space. z i ∈ R d and x i ∈ R d represent the observed and latent features of point i, respectively. Assume that the observed feature z i is independent of each other. We infer the latent feature x i from the observed feature z i by considering the affinity in the feature space. Thus, we consider the following quadratic energy function: where X = {x i |i < N} denotes the feature set of the latent features. w i j ∈ R d×d is the weight matrix between features x i and x j , which encodes the relationship between two points. It can be computed as: where s i j ≥ 0 is the scalar similarity between points i and j, which can be estimated from the observed feature z. 2 C ∈ R d×d 0 is a compatibility matrix to model the intrarelationship between feature channels and is assumed to be independent of the feature value. There is a similar concept of the compatibility matrix in the classic discrete CRF model. In that case, C describes the co-occurrence (or compatibility) of different object classes or labels. Since our model is built in feature space, C actually describes the channel/dimension compatibility of feature space here. In general, we can assume that the channels are independent of each other, and the messages pass in each channel individually in this case. Therefore, it is possible to directly define C as the identity matrix. Alternatively, it is also possible to automatically learn it from the data to further enhance the expression ability of the model. We cannot parameterize C directly because of its positive-define constraint. In this paper, we let C = c c + I to ensure positive definition, where c is a learnable parameter initialized as c = I. is a tiny positive value.
Eq. (3) consists of two terms: a fidelity term and a smoothness term. It can be understood that we want the new representation x i to be smoother but as close as possible to its original representation z i . Eq. (3) and its variants have been widely applied in the problems of denoising, recovery, and superresolution in computer vision. The latent feature X can be obtained by minimizing Eq. (3): Eq. (5) is a quadratic convex optimization problem with a closed-form solution. Denote Z = [z 1 , z 2 , ..., z N ] and X = [x 1 , x 2 , ..., x N ] as the concatenated feature vector of the point cloud, where Z, X ∈ R (N×d) . The compact form of Eq. (3) can be rewritten as: where W is a N × N block matrix consisting of w i j , which can be computed as is calculated with respect to X and ∂E(X)/∂X = 0. We can obtain the closed-form solution of E(X): where To solve the linear system, we need to calculate the inverse of such a large matrix, which is computationally expensive, especially when N and d are both large. Alternatively, we adopt an iterative strategy instead of using the closed-form solution. Recalling Eq. (3), we calculate the partial derivation of E(X) with respect to x i and let ∂E(X)/∂x i = 0. Then, we can obtain an iterative solution for x i under the coordinate descent framework: Since Eq. (3) is convex, the coordinate descent algorithm can guarantee the global minimum, which is validated in the experimental section. If we further assume that point i is only related to its neighbor points N(i) = j p i − p j 2 2 ≤ r in the point cloud and normalize the similarity toŝ i j = s i j / j∈N(i) s i j , Eq. (8) can be further simplified to: It is easy to find that Eq. (3) actually contains a graph structure implicitly. We denote the graph defined on a point cloud as G P (V P , E P ), where V P is the node set that contains all points (|V P | = N). E P represents the edge set that indicates whether two points are related to each other. Therefore, the update equation Eq. (9) can be described as a message-passing process in G P , as shown in Algorithm 1.

Algorithm 1 The message-passing process of Eq. (3)
Input: Point cloud graph G P (V P , E P ), observed feature Z = {z i |i ∈ V P }, maximum iteration steps T . 1: Initialize: x i ← z i for i ∈ V P 2: Compute the normalized similarity:ŝ i j for e(i, j) ∈ E P 3: for t = 1 : T do 4: for i ∈ V P do 5: Message passing: msg j→i = e(i, j)∈EPŝi j x j 6: Compatibility transformation: msg j→i = Cmsg j→i 7: Add unary: x i = z i + msg j→i 8: Normalize: end for 10: end for Output: Latent feature X = {x i |i ∈ V P }.

The message-passing graph convolution
Gilmer et al. proposed a universal GNN paradigm named message-passing neural networks (MPNNs) in [28]. The forward pass of MPNN has two phases: message passing and readout. In fact, most graph convolutional networks previously proposed [29,30,31] follow such a message-passing paradigm. Accordingly, we can also reformulate Algorithm 1 as a message-passing graph convolution.
Denote x l i as the feature vector of node i in the l th layer of the network. Our message-passing graph convolution can be defined as: Message-passing step: Readout step: where MLP(·) denotes the multilayer perceptron which is used for the pointwise feature transformation. m (l,t) i and h (l,t) i denote the message and the hidden state of node i in the l th layer after t message-passing steps, respectively. σ(·) acts as a nonlinear activation function in the read out step. The data flow of the message-passing step is illustrated in Figure 1. Unlike most one-step graph convolution methods, the message-passing phase of our graph convolution, which consists of a message function Eq. (11) and an update function Eq. (12), runs T times.

The CRF Perspective
Consider a Gibbs distribution in Eq. (2) with the energy function given in Eq. (3). According to the Hammersley-Clifford theorem, in this case, Eq. (2) actually determines a continuous Gaussian CRF model defined on G P (V P , E P ). Considering CRF, the maximization of P(X) is also equivalent to the minimization of the energy function E(X).
Proof. The goal of the mean-field approximation algorithm is to find a distribution Q(X) that can be factorized as Then, we can obtain Q(X) by minimizing the Kullback-Leibler divergence KL(Q||P) between Q(X) and P(X). We obtain {(µ * i , Σ * i )|i ∈ V P } by solving the following problem: where F[·] is an energy functional about the energy function E(X) and the approximation distribution Q(X). Since the forms of E(X) and Q(X) are determined in our case, F can be viewed as a function of {(µ i , Σ i )|i ∈ V P } directly.
Q i is supposed to be independent and identically distributed. Without losing generality, we consider each µ i and Σ i individually. By setting ∂F/∂µ i = 0 and ∂F/∂Σ i = 0, we can obtain the update equations of µ i and Σ i , respectively: Actually, we are only interested in the mean vector We find that the update equation of µ i in the mean-field algorithm is equivalent to the update equation of x i in the coordinate descent algorithm. In other words, the coordinate descent of Eq. (3) is equivalent to the mean-field approximation of a continuous CRF (Eq. (2)), by which Theorem 1 can be proved. Hence, we name the proposed message-passing graph convolution continuous CRF graph convolution (CRFConv). For clarity reasons, we only provide a brief proof here. The detailed proof of Theorem 1 can be found in the supplemental material.

The point cloud segmentation network
In this section, we show how to utilize the proposed CRFConv for point cloud segmentation. We design a point cloud segmentation network that includes two parts: an encoder and a decoder. An overview of the network architecture is shown in Figure 2. The CRFConv is embedded in the decoder to decode the high-level features. Specifically, we model the upsampling process with the CRF model rather than linear interpolation, by which the lost details of high-level features caused by the encoder can be restored gradually during feature decoding.

The encoder
Because point clouds are unordered, sparse, and continuous in 3D Euclidean space, the convolution on a point cloud is different from that on an image. Analogous to image convolution, we adopt the convolution defined on irregular domains to extract the point features in the encoder. The standard convolution operation is defined as: where f is the signal to be convolved, and g is the convolution kernel. In a regular domain (e.g., image), the offset (x − y) is fixed with respect to different kernel centers, which allows us to directly parameterize g with shared parameters. However, for an irregular domain (e.g. ,point cloud), the offset (x − y) and the neighborhood size |N(x)| may vary at different positions, which leads to the fact that we cannot parameterize g directly. In the literature, researchers have attempted different methods to define the convolution on irregular domains [5,6,32,15,16]. In this paper, we follow [32,15,16] and parameterize the convolution kernel g as: where Θ is the learnable weights of the MLP. Therefore, the point convolution (PointConv) used in this paper can be written as: in which normalization is necessary to make it robust to various neighbor sizes. d in and d out are denoted as the input and output feature dimensions, respectively. For each PointConv, the kernel g(·) is evaluated N × |N| × d in × d out times. This is computationally expensive in practice, especially when both the number of points and the feature dimension are large. Inspired by the depthwise separable convolution of image networks, we separate canonical PointConv into a depthwise point convolution and several 1 × 1 convolutions. Figure  3 illustrates our PointConv layer in detail. Specifically, we first use a 1 × 1 convolution to reduce the dimension of the input feature from d in to d in /r with a proportion of r. Then, we evaluate N × |N| × (d in /r) kernels for depthwise point convolution. Finally, another 1 × 1 convolution with (d in /r) × d out parameters is adopted to produce the output features. Moreover, batch normalization (BN) and residual connections are also adopted for PointConv. Dilated kNN neighbors are constructed for dilated PointConv to increase the receptive field of the encoder, which is proven to be helpful in image segmentation [24].

The decoder
In the literature, successive pooling operations or strided convolutions are adopted to increase the receptive field of the encoder. In the decoding stage, they simply adopt linear interpolation to upsample the high-level features, by which the details of these features are lost. Such linear interpolation only considers the positions of the features but ignores their continuity in feature space. The high-level features become increasingly coarser during decoding. Previous methods skip connections to relieve this situation. However, no previous study has fundamentally attempted to solve this problem. To address this problem, we propose using the CRFConv to restore the details of the high-level features during decoding. In our method, not only the point positions but also the distribution of the low-level features are considered for feature decoding. CRFConv is utilized to model the data affinity in feature space to generate high-resolution and detailed high-level features.
Denote x (l−1) and x l as the high-level feature to be upsampled (the input feature in the decoder) and the upsampled high-level feature (the output feature in the decoder), respectively. Let x (l) be the corresponding lower-level feature in the encoder that has the same resolution as x (l) . Figure 4(a) gives the architecture of our decoding layer. The high-level feature is initially upsampled by kNN interpolation. Then, a unary net is immediately adopted to extract the unary feature, which produces z (l) as described in Eq. (10). Then, we dynamically compute the similarity s i j . We adopt a pairwise net that takes the corresponding feature x (l) in the encoding layer to compute s i j . The CRFConv 9 takes these two inputs to generate the restored feature via the message-passing module, as shown in Figure 1. Once the message-passing completes, the restored feature is further concatenated with the corresponding lower-level feature x (l) in the encoding layer to feed the next decoding layer after activation.
Unary Net. We simply take an MLP as the unary net, which conducts a pointwise feature transformation for the point features. The unary net plays the roles of dimension reduction and feature fusion in the decoding layers.
Pairwise Net. The pairwise net is used to compute the similarity s i j of each point pair (i, j). For each high-level point feature pair (x i , x j ), we compute its similarity with the corresponding point feature pair (x i , x j ) in a lower-level feature space. We adopt the Mahalanobis distance in the low-level feature space to compute the similarity s i j . The vanilla Mahalanobis distance is computed as: where The Mahalanobis distance is actually the Euclidean distance on a projected space determined by the linear projection matrix P, which may fail to model nonlinear data effectively. In this paper, we reformulate P as a nonlinear projection to better model nonlinear data. We let the network learn a measure function automatically with an MLP. Thus, the improved Mahlanobis distance used in this paper can be computed as: Accordingly, the normalized similarityŝ i j is given as: which can be easily implemented with a softmax layer in the network.

Classical discrete CRF as graph convolution
Most previous studies utilize the discrete CRF model to refine the labels in segmentation tasks, while our CRF is a continuous model defined in feature space. Hence our continuous CRF can work collaboratively with the classical discrete CRF to further improve the segmentation performance. In image segmentation, the energy function of the discrete CRF is usually defined as a pairwise model [23]: where x i ∈ L presents the label of pixel (node) i. Here L is a discrete label set. ψ u (x i ) ≥ 0 is the unary potential, which gives a penalty when each pixel is assigned a label. In the postprocessing CRFs, the unary potential can be simply computed as ψ u (x i ) = − log p(x i ), where p(x i ) is the probability predicted by a discriminative classifier.
is the pairwise potential, which penalizes two connected pixels with different labels.
Here, µ(·, ·) measures the compatibility between different classes. K(·, ·) : R d × R d → R + is a positive function defined on a feature space of the pixels. The update equation of the approximate distribution Q i in the mean-field approximation of Eq. (23) is given in [23]: We show that Eq. (23) can also be used for point cloud segmentation. For each point i, let p i be the output probability vector of the segmentation network and q i be the vector version of Q i . Eq. (24) can be compactly rewritten as: where we denote w i j = K(f i , f j ). C ∈ R |L|×|L| is a matrix that encodes the compatibility of labels. Here, we have no constraint on C and learn it from the data. If we set C = I, it will degenerate to the Potts model, that is, µ(x i , x j ) = 0 if x i = x j otherwise 1, which is widely adopted in most previous image segmentation CRFs.
Algorithm 2 Message passing of the discrete CRF Input: Point cloud graph G P = (V P , E P ), initial distribution P = {p i |i ∈ V P }, maximum iteration step T . 1: Initialize: q i ← p i for i ∈ V P 2: Compute weights: w i j = K(f i , f j ) for e(i, j) ∈ E P 3: for t = 1 : T do 4: for i ∈ V P do 5: Message-passing: msg j→i = e(i, j)∈EP w i j q j 6: Compatibility transformation: msg j→i = Cmsg j→i 7: Add unary: q i = log(p i ) − msg j→i 8: end for 10: end for Output: Approximate distribution Q = {q i |i ∈ V P }.
Eq. (25) can be formulated as another message-passing algorithm on the point cloud graph G P (V P , E P ), as shown in Algorithm 2. Analogous to CRFConv, we can further reformulate Algorithm 2 as another message-passing graph convolution for point cloud segmentation: Initial step: Message-passing step: Update Readout step: Following [23], we set Instead of adopting artificially designed parameters such as [23], we learn ω m and Σ m of each Gaussian component from the data automatically. To ensure positive definition and avoid the inverse operation, we let Σ −1 m = PP , where P ∈ R d×d , which can be implemented with a linear layer having d outputs. Similarly, the weight sum operation can also be implemented with another linear layer having only one output. The data flow of the discrete CRF convolution layer is shown in Figure 4(b). It can be added at the end of our segmentation network as an additional graph convolution layer to form a dual CRF network. In addition, the whole network can be trained end-to-end.

Experiments
The experimental platform is a PC equipped with an Intel Core i7 9700K CPU, 16 GB RAM, and an Nvidia TITAN RTX GPU (24 GB). The algorithm is implemented with PyTorch [33] and PyTorch Geometric [34] on Ubuntu 16.04.

Datasets
The experiments are conducted on various 3D point cloud segmentation datasets, including ShapeNet [35] for object-level evaluation and S3DIS [36] and Semantic3D [37] for indoor and outdoor scene-level evaluation.
ShapeNet. ShapeNet is a 3D object model dataset that contains 16,880 object models from 16 categories. Each 3D object consists of approximately 2k points. ShapeNet Parts is the part segmentation benchmark for the ShapeNet models, in which each model annotates 2 to 6 parts with a part label (50 parts in total). S3DIS. S3DIS is a large-scale indoor 3D scene segmentation dataset that was collected on six large-scale indoor areas from 3 different buildings. The scene is annotated with 13 categories (including clutter). Following [4], we organize the dataset by rooms (271 rooms in total). In our experiments, we split the training and test sets according to area.
Semantic3D. Semantic3D is a large-scale outdoor point cloud segmentation online benchmark. This benchmark provides a large labeled 3D point cloud dataset of natural scenes with over 4 billion points in total, which covers a range of diverse urban scenes. We conduct our experiments on the reduced-8 benchmark, which contains 15 scenes for training and 4 reduced scenes for testing with 8 semantic categories.

Experimental Settings
The encoder of our segmentation network contains five convolution blocks, each of which consists of two successive PointConv layers. The cloud resolution is reduced by the farthest point sampling (fps) with a ratio of r after each convolution block; additionally, the feature dimension d is doubled. In our experiment, we set r = The dilated kNN is only available in the encoder. We set the dilation rate dil = [1, 2, 4, 4, 2] in the five PointConv blocks. Two fully connected layers follow the last decoding layer to obtain per-point labels. The discrete CRF is added after the last fully connected layer if necessary. To make fair comparisons with the previous methods, the discrete CRF convolution is not adopted in the comparison experiments. The performance of the discrete CRF convolution is evaluated in the ablation study. The detailed network architecture and more experimental details can be found in the supplementary material.

Object-Level Evaluation
We conduct a shape part segmentation experiment on the ShapeNet Parts benchmark. Instead of training each category individually, we train a model with all part labels (50 in total). The normalized x, y, z position and the normal vector n x , n y , n z of each point are taken as the input features. Because our network supports various input point cloud sizes, we do not sample the points as in previous methods [4,14,5]. The intersection over union (IoU) of the object parts is used as the metric to evaluate the performance. The instance part IoU (pIoU) and mean class pIoU (mpIoU) are given in Table 1. Compared with nearly twenty current popular methods, the performance of the proposed method exceeds most previous methods. From Table 1, we can find that KPConv [6] performs best overall, which may be due to the better feature encoding ability. Even compared with state-of-the-art methods, the proposed method can achieve competitive performance. Please see the supplementary material for some visualization results.

Scene-Level Evaluation 5.4.1. Data Preparation Conventional Implementation.
Scene-level point cloud data are more complex than object-level data. The former is spatially continuous and usually nonuniform in density and cannot be processed by the network directly. Following [4,14,5], we sample blocks from a scene point cloud in training and testing. For indoor scenes, the point cloud is first collected by rooms. Then, each block is randomly sampled from each room. For outdoor scenes, we directly sample blocks from each scene. To control the block size, we then uniformly sample N points in each block to feed the network. In training, the blocks are randomly sampled from the training set in each epoch. In the test, we sample multiple blocks in the test set until each point is evaluated at least once. After that, the final per-point labels can be obtained by voting. In this strategy, neighbor searching and cloud sampling are computed directly in the network. We adopt this strategy as a conventional implementation in scene-level evaluation experiments.
Advanced Implementation. In conventional implementations, the network will require considerable computation to organized the structure of the point cloud (i.e., neighbor searching and cloud sampling). Therefore, some methods [6,48] adopt a more computationally efficient method to organize the input point cloud blocks. In this strategy, the multiscale point cloud and the point neighbors at each scale are efficiently precomputed on the CPU. This strategy allows them to handle ten times the input size than the conventional implementation under the same time complexity, which is helpful for training the network on large-scale point clouds. To compare with them, we also employ this strategy as an advanced implementation for the proposed method and conduct experiments on scene-level benchmarks. The advanced implementation is denoted as CRFConv+ to be distinct from the conventional implementation, which is denoted as CRFConv.

Indoor Scene Segmentation
The proposed method is evaluated on the S3DIS dataset for scene-level segmentation tasks. We adopt the normalized coordinates in the block and the corresponding RGB color as the input feature. We set the input point size to 8,192 for the conventional implementation (CRFConv) and 40,960 for the advanced implementation (CRFConv+). We take the overall accuracy (OA), mean accuracy (mACC), mean IoU (mIoU), and per class IoU as metrics to evaluate the performance. Since previous methods usually give the results on Area 5, we also report the results on this area in Table 2. From the experimental results, our method can achieve state-of-the-art performance with the precomputed multiscale strategy. For conventional implementation, the proposed method can also outperform some previous methods that prepare data in a conventional style, such as PointNet and PointCNN.

Outdoor Scene Segmentation
We further evaluate the proposed method on the large-scale outdoor 3D point cloud segmentation benchmark Semantic3D. We first uniformly downsample the training set before sampling blocks to maintain a voxel resolution of 0.01m 3 , which is the as the reduced test set. The normalized position in the block and the corresponding RGB color are taken as the input features for the network. The input point cloud sizes are set to 8,192 and 65,536 for the conventional and advanced implementations, respectively. Because Semantic3D is an online benchmark, we submit the experimental results on the reduced-8 test set to the benchmark website. 3 The experimental results are also shown in Table 3. Note that only the published methods are listed in the table. From the table, the performance of RandLA-Net and SCF-Net is state-of-the-art overall. Next, the proposed method performs comparably with KPConv and BCM AFM, and outperforms the other methods.

Discussion
According to the experimental results for scene-level evaluation, the proposed method can perform well in both indoor and outdoor scenes, which demonstrates the robustness of our method. Overall, the proposed method performs better in indoor scenes because the outdoor scenes are usually more complex and biased than indoor scenes. In Table  3, we find that our method performs better on large or regular objects such as terrain and cars but worse on small or irregular objects such as vegetation and landscape. The reason can be explained by the fact that the former will benefit from the proposed CRF model, but the latter may be erroneously viewed as noise and smoothed by the CRF model in feature extraction, especially when the training samples involving the case are very limited. Actually, this phenomenon occurs not only in this dataset but will be magnified in a biased situation. We will try to address this problem in future works. In addition, we find that the advanced implementations with a precomputed multiscale strategy can largely improve the performance on both indoor and outdoor scenes compared with the conventional implementations. This is because the block sampling strategy damages the completeness of the continuous point cloud, especially when the block size is small, which may harm the overall performance in some way. In contrast, the precomputed multiscale strategy allow us to handle a larger input block size, which is helpful for network learning on scene-level point clouds. More visualization results on the scene-level datasets can be found in the supplementary material.

Ablation Study
To further evaluate the performance of the continuous/discrete CRF convolution, we conduct an ablation study on the S3DIS dataset for the proposed method. First, we compare the performance of the proposed method with/without the continuous/discrete CRF convolution. Table 4 shows the experimental results on Area 5. Note that the results in this section are conventionally implemented without merging labels. We adopt the same encoder for all models. In the baseline model, we remove the continuous CRF convolution in the decoder and only perform linear interpolation for point cloud upsampling. Baseline+discrete CRF denotes that we add the discrete CRF at the end of the baseline model. Baseline+continuous CRF employs continuous CRF convolution in the decoder, which is the general version of the proposed method. For baseline+dual CRF, we add the discrete CRF convolution at the end of the general version to form the dual CRF version of the proposed method. In Table 4, even the baseline model achieves promising performance, which can also prove the effectiveness of the encoder we designed. Compared with the baseline model, the model with continuous CRF has achieves a significant improvement. Although the discrete CRF also improves the performance in some way, the improvement effect is marginal. In traditional discrete CRF, the performance of the model depends largely on the unary term. In other words, the misclassified regions caused by the classifier are hard to correct by the discrete CRF. However, our continuous CRF model can fundamentally improve the presentation (location) ability of the point features, therefore avoiding such discrete CRF model limitations. Additionally, some visualization comparisons with/without the CRFConv are illustrated in Figure 5. We can see that the segmentation results of the CRFConv model look smoother and more complete than those of the baseline model in most cases, especially on some boundary areas (see office 2 and office 40). Some misclassified regions produced by the baseline model can also be corrected by the proposed CRFConv (see hallway 1).
The proposed CRFConv layer is flexible and scalable and can be used as a plug-and-play module for integrating Note that the "ceilings" category is removed manually for better visualization. The regions marked by green circles show some significant local differences.  into existing encoder-decoder networks to further improve their performance. In this section, we integrate CRFConv with RandLA-Net [48], which is one of the representative methods in the community, and conduct experiments on the S3DIS dataset. Specifically, we package the CRFConv as an upsampling layer and insert it into the decoding layers of the original RandLA-Net. All other settings follow the same schemes as the original paper. We report the results on Area5 in Table 5. In the table, our CRFConv can further improve its performance, which also proves the effectiveness of the proposed CRFConv. Through this experiment, we demonstrate that the proposed method has a certain generality that can improve the performance of the network independent of specific encoders.

Parameter Analysis
The mean-field step T of our CRFConv is a flexible parameter, which allows us to adopt different mean-field steps for the training and test phases. In training, we set the mean-field step as 1 for efficiency and to avoid vanishing/exploding gradients. Therefore, we evaluate the performance of various mean-field steps in the test phase. The performance of different mean-field steps on the validation set is illustrated in Figure 6. According to this figure, the continuous CRF performs best when the mean-field step is approximately 10. With the increase in the mean-field steps, the performance tends gradually become saturated. Owing to the fidelity ability of CRFConv, we do not observe obvious performance degradation caused by oversmoothness, which may occur in most current popular graph convolutions. However, we find that the model performs best when it is about to converge rather than converge. When the model converges, the feature may become smoother, which may be harmful to some small or irregular objects. This can explain why the performance decreases slightly when the CRF reaches convergence. This experimental result is also coincident with our analysis of the outdoor scenes. Figure 6: The test performance of the CRFConv on various mean-field steps.

Time complexity
In this section, we conduct a runtime analysis of the proposed method. First, the runtime of the proposed method with/without the precomputed multiscale strategy is given. Then, we additionally make a runtime comparison with some previous methods. Specifically, we choose the S3DIS benchmark for this experiment and run the previous methods on our experimental platform. The experimental setting follows the original paper. We give both the training and test runtime of each iteration including data preparation. To make a fair comparison, we make the input point cloud size of our method the same as previous methods. Note that, because KPConv adopts various input sizes, we report an approximate value here. The experimental results are shown in Table 6. From the table, we find that PointNet is the most efficient method because of its simple architecture. Although the overall runtime of the proposed method is higher than that of previous methods, the proposed CRFConv module only adds a small runtime cost to the backbone network in both training and testing. Moreover, due to the precomputed multiscale strategy, the efficiency of the network greatly improved. This strategy allows us to handle a larger batch size but with lower time complexity.

Conclusion
In this paper, we addressed the problem of point cloud segmentation. First, we proposed a continuous CRF graph convolution to capture the structure of the point features, by which the representation ability of the features improved.
Then, we designed an encoder-decoder point cloud segmentation network based on the proposed continuous CRF convolution. The continuous CRF convolution embedded in the decoder can restore the details of the high-level features produced by the encoder to enhance the localization ability of the network. Furthermore, we also showed how to formulate the discrete CRF as another message-passing graph convolution and combined it with the continuous CRF convolution, by which we modeled the data affinity not only in feature space but also in label space to further improve the segmentation results. Experiments on various datasets demonstrated the effectiveness of the proposed method.
However, compared with indoor scenes, we find that the proposed method performs worse in outdoor scenes that are usually more complex and biased than the former. In this case, the CRF model erroneously viewed some small or irregular objects as noise in feature extraction, especially when the number of training samples involving the case was very limited. This situation may be relieved by increasing the input point cloud size with the precomputed multiscale strategy. In the future, we will attempt to address this problem. In this work, we focused the decoding of the point cloud features and achieve promising results. However, the overall performance of the network depends on more than one aspect. For example, the feature encoder may play a decisive role. In future work, we will also attempt to investigate more feature encoding methods, such as convolution in the point cloud domain. Moreover, we will continue exploring the feasibility of integrating graph neural networks with probabilistic graphical models.

Abstract
This document provides some supplementary contents for the paper: Continuous Conditional Random Field Convolution for Point Cloud Segmentation. Section 1 of this document presents some details about the proof of Theorem 1. The model-level analysis of the relationship between the proposed CRFConv and previous diffusion-based methods is given in section 2. More experimental details and results can be found in section 3.

The proof of Theorem 1
Problem statement: Given a continuous CRF defined on graph G(V, E), its corresponding Gibbs distribution can be written as: where the X = {x i ∈ R d |i ∈ V} denotes the set of all latent features, Z is a partition function to ensure a distribution. The energy function E(X) is defined as a continuous quadratic energy model: where z i denotes the observed feature of node i. N(i) denotes the neighbor nodes set of node i in G. w i j ∈ R d×d 0 is the weight matrix of two connected nodes in G. Let Q(X) = i Q i (x i ) be the approximate distribution of P(x), where Q i ∼ N(µ i , Σ i ). Our object is to obtain {(µ * i , Σ * i )|i ∈ V} by solving the following problem: where is the KL-divergence between Q(X) and P(X 2 To minimize µ i and Σ i , we only need to concern about the terms which contains µ i and Σ i in Eq. (5), respectively. For µ i , we have For Σ i , we have Compute the gradients of Eq. (6) and Eq. (7) with respect to µ i and Σ i respectively and let the gradients to be zero, we can get the update equations of µ * i and Σ * i : To maximize Q(X), we only need to compute µ i for all Q i (x i ). It can be found that the update equation of µ i in the mean-field approximation is the same as that of x i in the coordinate descent algorithm, by which Theorem 1 can be proven.

The relationship with diffusion
Consider an anisotropic diffusion process on a heat field H defined on graph G H . Denote h t as the heat vector of H at time t on G H . And let L H = I − D −1 H W H be the normalized Laplacian matrix of G H , where D H and W H are the degree and adjacent matrix, respectively. The diffusion process on G H can be described as the following PDE with a discrete form: where c is a diffusion coefficient to control the diffusion speed.
In the diffusion process, the heat field is a scalar field. By unfolding Eq. (10), we can obtain the temperature h t i in the heat field H for any position i and time t: where w i j is the weight of two adjacent nodes. If we set the compatibility transform matrix C = I in our model, that is, each channel is independent of others, we can find that our CRFConv is equivalent to a diffusion model built on each channel individually at time t = 0. However, when t > 0, the difference between the diffusion process and our CRFConv is that the diffusion process adds the previous state at each iteration while our CRFConv always adds the initial state at each iteration. Furthermore, when the diffusion process reaches the stable state, we have L H h = 0, which is the solution of where h T L H h is the Dirichlet energy. It can be found that the Dirichlet energy only acts as the smoothness term of our CRF model. That is to say, the diffusion-based methods only ensure the smoothness but ignore the uniqueness of features, which could cause over smoothness, while the proposed method does. In other words, our CRFConv can overcome the over smoothness phenomenon usually occurred in current popular graph convolution methods. Moreover, the diffusion-based methods suppose that each channel is independent of the others, while our CRFConv models the relations between each channel by a compatibility transformation matrix C which can be learned from the data automatically to improve the representation ability of the model.

Implementation details
The details of the point cloud segmentation network can be found in Table 1. Note that the Batch Normalization with the momentum of 0.98 and the LeakyReLU with the negative slope of 0.1 are added after each convolution layer. For brevity, we did not show them in Table 1. We construct the point cloud graph based on kNN in both the encoder and the decoder. The dilated kNN is only available for the PointConv in the encoder. The momentum stochastic gradient descent (SGD) algorithm is used to minimize the cross entropy-loss, with a momentum of 0.95. We take an exponential decay strategy for the learning rate with initial rate of 0.01. The decay rate is set to ensure the learning rate is divided by 10 every 50 epochs. The network will reach convergence within 100 epochs. The batch sizes are set to 16 and 8 for the conventional and advanced (with precomputed multiscale strategy) implementations, respectively. Discrete CRF (optional) DiscreteCRFConv(in dims=L, out dims=L, kernel size=32) Figure 1: Visualization results compared with the groundtruth on the ShapeNet Part dataset. Three samples are shown for each object category, in which each part is visualized in a unique color. Figure 2: Visualization results compared with the groundtruth on Area 5 of the S3DIS dataset. Each class is visualized in a unique color. Note that the "ceiling" category is removed manually for better visualization. Figure 3: Visualization results compared with the groundtruth on the validation set of the Semantic3D dataset. Each class is visualized in a unique color. Note that the "unlabeled" category is removed manually for better visualization.


#HowYouTagTweets: Learning User Hashtagging Preferences via Personalized Topic Attention

Millions of hashtags are created on social media every day to cross-refer messages concerning similar topics. To help people find the topics they want to discuss, this paper characterizes a user’s hashtagging preferences via predicting how likely they will post with a hashtag. It is hypothesized that one’s interests in a hashtag are related with what they said before (user history) and the existing posts present the hashtag (hashtag contexts). These factors are married in the deep semantic space built with a pre-trained BERT and a neural topic model via multitask learning. In this way, user interests learned from the past can be customized to match future hashtags, which is beyond the capability of existing methods assuming unchanged hashtag semantics. Furthermore, we propose a novel personalized topic attention to capture salient contents to personalize hashtag contexts. Experiments on a large-scale Twitter dataset show that our model significantly outperforms the state-of-the-art recommendation approach without exploiting latent topics.

Introduction
Virtual communications are playing an increasingly crucial role in our daily activities. In this profound revolution in interpersonal communications, social media has become the key channel to connect an individual with human society. People are now turning to the online world to exchange viewpoints, voice opinions, and engage in topics they are interested in. Nonetheless, the deluge of the online contents streaming through social media every day has presented the concrete challenges for users to catch what they essentially need. To deal with this issue, many platforms encourage users to tag their messages with hashtags (e.g., "#COVID19" and "#NLPeople") -topic labels referring to similar posts and allowing easier microblog search. However, users may only want to explore the hashtags (and the linked messages) they are interested in, whereas platforms tend to display popular hashtags for all the users. In light of this concern, how to curate personalized hashtags to draw better user engagements?
This paper studies hashtag personalization which explores users' hashtagging preferences and predicts how likely a user will put a hashtag in their future posts (henceforth user-hashtag engagements). We hypothesize that one's hashtagging behavior is highly related to two factors: (1) the user's personal interests reflected by their past hashtagging history (user history) and (2) the contents appear with the hashtag in posts (hashtag contexts).
To illustrate this intuition, Figure 1 shows the sample tweets tagged with #book (H) and some history tweets of a user U . As can be seen, U was a big fan of mystery books, who later tweeted to share a book and tagged H for topic indication. Such future engagements can be signalled by the contexts of H from words like "thriller" and "mys-tery" which suggest U 's potential interests to H.
In previous research, most studies (Wu et al., 2017) ignore the possible semantic change of hashtags and hence insurmountable to tackle a ubiquitous issue in real life -new hashtags might appear after the model is trained and even the old ones may exhibit different meanings in the future (and are hence likely to engage different user groups).
Another similar-by-name concept is "hashtag recommendation", which attempts to fit a hashtag to a post and is thus post-oriented (Li et al., 2016;. Our task is oriented at users, whose past hashtagging behavior is explored to foresee their preferences to the future hashtags. If we consider a broader area of online content recommendation (e.g., tweets (Chen et al., 2012), conversations (Zeng et al., 2019)), many studies rely on user-content interaction history with pairwise labels for supervised learning. They are hence unable to adapt the user interests trained from history data to personalize future contents, due to the semantic gap between past and future data. This is however unignorable when studying social media contents which commonly exhibit evolving topics.
To leverage user hashtagging history (in the past) to hashtag contexts in the future, we first conduct unsupervised learning to encode hashtags, whose embeddings are later used for joint training to gain user interests from hashtagging history. For hashtag modeling, a pre-trained BERT (Devlin et al., 2019) and a neural topic model (NTM) (Miao et al., 2017) work together to couple the effects of local contexts on message level (handled by BERT) and global contexts observed from word statistics (handled by NTM).
Furthermore, we propose a novel mechanism of personalized topic attention over hashtag contexts to capture the keypoints therein, where the useful features might be sparse and the tremendous noise is likely to hinder the model's capability to learn anything helpful. For instance, in Figure 1, only the first tweet in H's contexts explicitly hint the connection of H with U 's interests, while the others are relatively useless. To address such issues, we leverage latent topics and user embeddings to attend salient contextual messages exhibiting the positive match with the user hashtagging history.
To the best of our knowledge, we are the first to personalize hashtags via joint training to adapt user interests gained in history to future hashtag semantics, where the joint effects of latent hash-tag topics and user hashtagging preferences are explored in a novel personalized topic attention.
For the experiments, we gather a large-scale Twitter dataset and use absolute time to separate the training and validation data (before the time) from the test (after the time). In this way, hashtags available for user preference modeling (in training) will exhibit a gap compared with the hashtags (in test). Moreover, we focus on hashtags that do not appear in the target user's history, considering that users may prefer new and unseen hashtags.
Main experimental results show that our model significantly outperforms the state-of-the-art recommendation model. For example, we present 0.311 MAP compared with 0.277 obtained by adapting Zeng et al. (2020). We then examine the effects of varying user history and hashtag contexts, where we observe consistently better results on varying users, while hashtag modeling might be benefited from richer contexts. Next, an analysis of our model indicates that all its components collaborate to effectively capture user hashtagging preferences and meaningful topics can be discovered to help attend salient contents for personalizing hashtags. At last, we compare the attended history tweets and the future tweets presenting successful engagements and shed light on our potential to not only answer "yes-or-no" to whether a user will be engaged with a hashtag but also how it happens.

Related Work
This paper is in line with prior studies for personalizing hashtags. They adopt shallow word statistics (e.g., latent topics (Zhao et al., 2016) and content factors (Wu et al., 2017)) or handcrafted features (Alkouz and Al Aghbari, 2020) to characterize user behavior. Different from them, we employ neural networks to explore users' hashtagging preferences in the deep semantic space, which enables natural inclusion of richer information and better language understanding ability.
Our work is also related to hashtag recommendation, which "recommends" a hashtag to a microblog post via hashtag ranking (Li et al., 2016;Huang et al., 2016) or generation (Ding et al., 2012; unaware of the personalized information. Others (Zhang et al., 2014;Gong et al., 2015) encode authors' writing styles for text consistency with the inserted hashtag. Bayesian graphical models are adopted for user modeling, which requires massive manual efforts to customize inference algorithms. In a broader line of online content recommendation, collaborative filtering (CF) is popular to explore user interaction history for recommendation, e.g., tweets (Chen et al., 2012), topics (Lu et al., 2015), conversations (Zeng et al., 2019). For other text-based recommenders, contents (to be recommended) are explored barely with supervised learning (based on user history) (Yu et al., 2016;Zeng et al., 2018). These approaches are therefore unable to cater for contents with evolving semantics. Our work employs a pre-trained BERT and neural topic model to gain the preliminary context understanding of future hashtags, which has never been studied before. Zeng et al. (2020) also capture the dynamic user interests to recommend conversations. Our task exhibits a new challenge to encode fragmented and noisy hashtag contexts and we propose a novel personalized topic attention to capture salient contents to predict user's future behavior.

Hashtag Personalization Framework
This section presents how to predict a user u's future engagement with a hashtag h via leveraging u's hashtagging history and h's contextual messages. Figure 2 shows our model architecture.
Input and Output. Before we start the story about how our model works, we formulate the task of hashtag personalization here. The inputs are a user u and a hashtag h, where h was not tagged by u in the history messages. To capture u's hashtagging preferences, we employ u's past chatting messages with other hashtags for user modeling. For the modeling of h, the messages sharing the hashtag h are adopted as the hashtag contexts. The output is how likely u will tag h in a future posth forms a user-hashtag engagement pair with u.

User History Encoding
As shown above, the user history of u is encoded from a sequence of u's messages m 1 , m 2 , ..., m |u| in chronologically order. |u| is the number of u's history messages. User embeddings are hence learned in the two-level hierarchy on message and user.

Message-level Modeling
For a message m in user history, we explore the semantics from its word sequence w m with a pre-trained BERT encoder and map m into a latent vector space. The learned message embedding is denoted as r m and will be further delivered to conduct user-level modeling with other history messages.
User-level Modeling Here, inspired by Zeng et al. (2020), temporal patterns of hashtagging history are explored to capture the possible user interest change over time. To that end, the embeddings of user history messages (r m ) are sequentially encoded by a Bidirectional LSTM network. For the i-th message, u's current preferences h u i are updated based on the previous interests h u i−1 and the current behavior r m i . The last hidden states of the two directions are then concatenated to represent u's overall hashtagging preferences r u .

Hashtag Context Encoding
Following the aforementioned description, the contexts of a hashtag h are formed with h set : a set of messages {m 1 , m 2 , ..., m |h| }, each hashtagged with h. |h| is the message number used to explore hashtag contexts, which are learned globally from inter-message word co-occurrence patterns and locally based on intra-message semantics.
Global Context Modeling The previous discussions concern the severe data sparsity in hashtag contexts attributed to their fragmented and noisy nature. To help our model capture essential features to characterize hashtags, we employ a neural topic model (NTM) to discover the latent topics (distributional word clusters) via exploring the intermessage word co-occurrences on hashtag level.
Here we adopt the NTM design based on variational auto-encoder (VAE) following Miao et al. (2017). Here h's hashtag contexts are represented by a bag-of-word (BoW) vector v h over the vocabulary V , which is first encoded into a latent topic vector z h (in K dimension and K for the topic number), followed by the decoding process re-generates v h conditioned on z h . For encoding, v h is mapped into the latent topic space via Gaussian sampling: where f * (·) denotes a ReLU-activated neural perceptron. In decoding, we first conduct a softmax transformation over the latent topic vector z h to yield the hashtag-topic distribution θ h for h. Then, The weights of f φ (·) (after softmax normalization) are adopted to represent the topic-word distributions and the latent topic vector z h is employed as the global context representation for h.
Local Context Modeling. Here, the focus is to explore the word semantics inside a message. Similar to the way we conduct message-level modeling for user history, pre-trained BERT is first employed to yield latent embeddings r m for a message m in hashtag contexts. Then, to enable the model to focus on essential messages for hashtag modeling, a personalized topic attention (in aware of the user embedding r u and latent hashtag topic z h ) is put over the message embeddings to generate the personalized hashtag embedding r u h (Section 3.3).

User-Hashtag Engagement Prediction with Personalized Topic Attention
To capture user hashtagging preferences, personalized topic attention is put over hashtag contexts to explore user u's potential interests to hashtag h and the attended context vector is further delivered to learn the prediction of user-hashtag engagement.
Personalized Topic Attention. This mechanism is designed to indicate messages in hashtag contexts whose topics exhibit better consistency with the target user's past hashtagging behavior. For all h's contextual messages, we first concatenate their embeddings with h's latent topic vector z h to present a topic-aware message embedding [r m ; z h ], which helps to provide the local message representation with the global view of hashtag-level topics. Then, u's user embedding r u is employed to query h's contextual messages to further inject personalized information to the learning of attention weights. Concretely, we capture the semantic relations between user embedding (r u ) and the message m in h's context using the formula below: where W att and b att are learnable parameters. Next, attention weights (in aware of topic and user representations) are computed as following to indicate the messages in h's context set h set which indicate better match with u's user interests: Afterwards, we conduct weighted sum to attend messages in h set and produce the context vector: r u h , employed to represent h, carries both topic information and the personal hashtagging interests of u (henceforth personalized hashtag embedding).
User-Hashtag Engagement Prediction. At output layer, we explore how similar the hashtag contexts (represented by r u h ) are to the historical user hashtagging behavior (encoded in r u ). Here MLP (He et al., 2017) is adopted to measure the potential engagements of user u and hashtag h: where γ(·) is the ReLU activation function. W M LP and b M LP are both learnable parameters. Finally, r u,h is used to predictŷ u,h which signals how likely u will hashtag h (positive engagement): W and b are learnable parameters for training.

Training Losses and Joint Training
The entire framework in joint training fashion is trained via minimizing multiple losses together.
Training Losses. We design two training objectives -an engagement loss for predicting userhashtag engagement and an NTM loss for exploring latent topics in hashtag contexts. The former (engagement loss) is designed based on the weighted binary cross-entropy following (Zeng et al., 2020). Given a training set τ of userhashtag pairs (u, h), we minimize the loss L eng via learning from their pairwise ground-truth label y u,c (1 for positive engagement and 0 for negative): The hyperparameter λ > 1 trades off the weights of positive and negative hashtag-user engagement pairs. Intuitively, more weights should be put on positive pairs, which is relatively more reliable, whereas negative pairs might be affected by many unpredictable things (e.g., users' busy schedule). For the same consideration, negative sampling is adopted to speed up the training (He et al., 2017).
For the NTM loss (L ntm ) in hashtag modeling, we follow Miao et al. (2017) to use variational inference (Blei et al., 2017) to approximate a posterior distribution over hashtag h's latent topic z h given the statistics of words observed in its contexts.
D KL (·) is the Kullback-Leibler divergence loss and E * [·] measures the VAE reconstruction. 2 Joint Training. To gain the preliminary understanding for hashtags with limited user engagement history for training (hashtag coldstart), we optimize NTM loss first for pre-training. Then, we joint train NTM and user-engagement prediction in an unified framework. The joint-training loss of the overall framework to learn hashtagging preferences is defined as following: where µ is the weight balancing the two effects.

Experimental Setup
Datasets and Setup. A large Twitter dataset was first gathered with the official streaming API in 2 Due to the space limitation, we leave out the details of the derivation and refer the readers to Miao et al. (2017).
Feb 2013, which contains 900M tweets. 3 We then filtered out tweets without hashtags and capped the user history at 50 tweets. Next, hashtag texts are hidden from both history and contexts to avoid the trivial features learned by the models, and the tweets presenting hashtags in the middle were ignored to enable better semantic learning (following Wang et al. (2019)). At last, we removed users who posted original hashtags only (never tagged by others) because these users cannot be taken for prediction. Here we distinguish hashtag first-use from reuse because the latter is dominant (taking 82% of hashtags) yet relatively valueless (users tend to see new hashtags), while prior settings tend to mix them together (Zhao et al., 2016;Wu et al., 2017).
For training and evaluation, we rank the tweets by time and take the earliest 80% for training, the latest 10% for test, and the remaining 10% for validation. In this way, the model is trained with past data and tested for the future, which reflects a more realistic scenario compared to random split (Wu et al., 2017). Based on our setup, users newly appearing in the test will not be taken away because they have no history to learn user embedding.  Data Analysis. Table 1 shows the data statistics. It exhibits more than half of "future hashtags" which do not appear in any user's history. This demonstrates the prominence of coldstart hashtags resulting from dynamic social media topics. We also observe the severe sparsity of hashtag contexts, exhibiting the variability of hashtags caused by the casual writings on social media. User history, on the other hand, seems to dense, providing rich contents to learn dynamic interests yet presenting another challenge of how to match hashtags (with sparse context) to users (with dense history).
To further probe into user and hashtag statistics, we plot the tweet number distribution in hashtag contexts in Figure 3a and user history in 3b. Most hashtags appear in only a few tweets (Fig. 3a), exhibiting a power-law distribution. User history has relatively richer contents (Fig. 3b), which implies users who hashtag once are likely to do it again.
Preprocessing and Model Settings. The tweet pre-processing was first conducted via open-source toolkit NLTK (Bird, 2006) for tokenization, stemming, and lemmatization. Then, meaningless tokens (e.g., links, punctuation, mentions) were removed. At last, a vocabulary of the most frequent 10K tokens was maintained for both word sequence input (to BERT) and BoW (to NTM).
In training, hashtag contexts were capped at 30 tweets via sampling. And to avoid problem degeneration, we only consider hashtags appear in ≥ 5 tweets for context modeling, though others may engage in user history modeling. The sampling ratio was set to 5 for negative sampling for training while all test hashtags will be ranked for evaluation.
For model setup, we took BERTweet (Nguyen et al., 2020) as the pre-trained BERT for message encoding. We adopted two layers of Bi-LSTM whose hidden states were set to 768 for each direction. The models were trained with Adam optimizer, initialized with a learning rate of 1e-3, and training batch size 128. The hyperparameters were set via grid search on the validation set, where the topic number K = 100, the positive and negative sample tradeoff λ = 100 (Eq. 6), and µ = 1e − 4 (Eq. 10) for balancing training losses.
For the joint training of our model, we first pretrained NTM for 20 epochs, warmed up other parameters for 20 epochs, and then updated all parameters simultaneously for 100 epochs.
Evaluation and Comparison. Our evaluation metrics follow the recommendation practice (Zeng et al., 2020) to measure the hashtag ranks predicted for each target user. Here we employ the popular information retrieval metrics precision@N (P@N ), mean average precision (MAP) over the top N predictions, and normalized Discounted Cumulative Gain at N (nDCG@N ). In the experimental results (Section 5), the scores reported are measured given N = 5 and similar trends hold for other N settings.
For baselines, we first consider a simple method which rank hashtags randomly (RANDOM), by their frequency in training set (POPULARITY), and the cosine similarity between user and hashtag embeddings (based on BERT) (henceforth BERT-SIM). Then, we examine features learned by LDA (Blei et al., 2001) and TF-IDF, where the popular learning-to-rank model GBDT (Friedman, 2001) is used for hashtag ranking. 4 Moreover, collaborative filtering (CF) is compared, which recommend hashtags based on user-hashtag interaction history (without content modeling).
For neural comparisons, we tailor-make Zeng et al. (2020), the state-of-the-art conversation recommendation model employing user history encoder based on LSTM with attention (henceforth LSTM-ATT), to personalize hashtags encoded by pre-trained BERT. Its two ablations -one without attention (LSTM) and the other simply adopting (MLP) to match BERT-generated user and hashtag embeddings are also considered.

Experimental Results
In this section, we first discuss the main results in Section 5.1 and quantify the effects of varying lengths of user history and hashtag contexts for measuring their engagement potential in Section 5.2. Then, Section 5.3 further interprets our superiority with an ablation study and a case study. At last, we analyze our ability to predict users' future hashtagging behavior in Section 5.4. Table 2 shows the main comparison results, where the following observations can be drawn.

Main Comparison Results
First, personalizing hashtags is not trivial. All baselines obtain poor results, though BERT-SIM performs relatively better thanks to its language understanding ability priorly gained by pre-trained BERT. Then, CF yields worse results than BERT-SIM, which showcase content features' better ability to indicate the future user-hashtag engagements than user interaction history. This is because future  hashtags will exhibit a different semantic space compared to the past, while CF is unable to leverage future hashtag contexts for prediction. Next, neural features are more useful than the non-neural counterparts. This suggests the ability of neural encoders to explore deep semantics for effectively characterizing user and hashtag factors, as opposed to LDA and TF-IDF which rely on shallow word statistics to handle a challenging task. In neural comparison models, LSTM and LSTM-ATT slightly perform better than MLP because user hashtagging behavior may change over time which can be captured by LSTM encoders; LSTM-ATT outperforms LSTM thanks to the ability of attention mechanism to explore salient user history message for personalization. At last, all results from our model are significantly better than others by a large margin. This implies personalized topic attention can indeed effectively encode noisy hashtag contexts and allow a better learning of user hashtagging preferences.

Engagement Prediction with Varying User History and Hashtag Contexts
Here we further examine how varying lengths of user history and hashtag contexts affect the prediction of their future relations.
Results with Varying User History. Figure 4 shows the P@5 yielded by our model and the LSTM-ATT comparison for the prediction on users with varying history tweet number. It is observed that both models exhibit a performance drop when handling very long user history, probably resulting from the small-scale training samples for user modeling (shown in Figure 3b). Nevertheless, our model performs consistently better for users with varying sparsity degrees of hashtagging history, especially for those having limited data to capture their past hashtagging preferences. This is probably because unsupervised topic modeling will enable our model to make use of the unlabeled data (future hashtag contexts), which enrich the limited features allowed to be captured from the sparse user interaction history.

Results with Varying Hashtag Contexts.
Here we discuss the effects of hashtag contexts on the prediction and display the P@5 scores of our model and LSTM-ATT in Figure 5. It is observed that LSTM-ATT performs slightly better for hashtags with sparse contexts, while our model exhibits large-margin performance gain for hashtags with rich context.
The reasons are two-fold. First, the latent topics are discovered in word co-occurrences in hashtag contexts, while more tweets will result in richer statistical patterns for topic modeling and better representation learning for hashtags. Second, in addition to richer contents, more contextual tweets are likely to bring in more noisy information. The noise may hinder LSTM-ATT to effectively explore the context because it relies on local contexts (captured by BERT) for hashtag modeling. On the contrary, our model is able to couple local contexts with the global ones (latent topics), which will enable the personalized topic attention to concentrate on what is essentially helpful for prediction.

Further Discussions to Our Model
Here we probe into our model output to examine how it works to characterize user hashtagging preferences and its current limitation. Ablation Study. To examine the relative contributions of personalized topic attention and joint training, Table 3 shows the ablation study results. We observe that simple concatenation of latent topics (⊕ TOPICS) can already exhibit the performance gain compared with LSTM-ATT (the SOTA without topics). This again demonstrates the usefulness of latent topics, which can signal topic words and enable the better modeling of hashtag factors.  Moreover, employing personalized topic attention can further boost the prediction results. This implies that latent topics can enable the user-aware attention to focus on keypoints in hashtag contexts that indicate the potential match with user interests.
In addition, joint training is crucial for the personalized topic attention to capture salient contents, which is seen from the much better results from FULL MODEL than W/O JOINT. It is probably because hashtag content change over time will result in different topics of the test hashtag contexts from those used for training user hashtagging preferences; joint modeling of latent topics and userhashtag engagements shows its benefits to mitigate such topic gap.
Case Study. To further interpret how our personalized topic attention learns to characterize a user's hashtagging preferences, we take the user U and hashtag H (#book) in Figure 1 as an example to interpret our learning results. Recall that U loves mystery books and engaged with H in a future tweets, though H did not appear in U 's history.
[M1]: love thriller and mystery check out [M2]: 85-5 star review [M3]: why not visit for sunday share [M4]: she be write the end for a long time Figure 6: The visualization of personalized topic attention learned for H (#book) and U in Figure 1 over the example hashtag context tweets M 1 -M 4 (on the left in purple) and the topic likelihood assigned to each word (on the right in red). Darker color, higher weights. Figure 6 shows the heatmap visualizing the attention weights over H's messages and the topic likelihood over their words. Personalized topic attention gives much higher weight to the first tweet M 1 compared others (M 2 to M 4 ) to indicate M 1 's strong effects to predict H's potential to draw U 's engagement. We also find that our NTM are able to highlight topic words with higher topic likelihood, e.g., "thriller", "mystery", and "write". This observation shows our capability to learn meaningful topic features to represent "#book".

Future Hashtagging Behavior Prediction
As discussed above, joint exploration of neural topics and user hashtagging preferences may enable better prediction of users' future hashtagging behavior. For an in-depth analysis, we first select the tweets in test, where the engagements of their hashtags and authors are correctly predicted by an attention-based model, and then measure their cosine similarity with the tweets in hashtag contexts assigned highest attention weights (queried by the user). Here we adopt our full model and the SOTA comparison LSTM-ATT, both employing user-aware attention, and show the test tweet frequency over similarity measures in Figure 7.
As can be seen, our model is able to predict more correct engagement attributed to its better ability to capture tweets in noisy hashtag contexts which exhibit more similar semantics to the future tweets presenting the successful user-hashtag engagements. This suggests our potential to not only personalize future hashtags but also predict their possible contexts by aligning the hashtagging behavior learned from the past to fit the future.  Figure 7: Y-axis shows frequency of test tweets whose user-hashtag engagements are correctly predicted by our full model (blue) and the LSTM-ATT (red). Xaxis indicates the cosine similarity of BERT embeddings of the test tweet and the one in its hashtag contexts given the highest attention weights.

Conclusion
This paper has studied the learning of user hashtagging preferences from history data to predict their future trajectory. Neural topic model is jointly trained with the prediction of user-hashtag engagements in a novel personalized topic attention. Experimental results demonstrate our effectiveness benefited from the ability to align user hashtagging interests gained from the history to customize their future behavior in the future.