International audience

Data clustering and representation learning play an indispensable role in data science. They are very useful to explore massive data in many fields, including information retrieval, natural language processing, bioinformatics, recommender systems, and computer vision. Despite their success, most existing clustering methods are severely challenged by the data generated by modern applications, which are typically high dimensional, noisy, heterogeneous, and sparse or even collected from multiple sources or represented by multiple views where each describes a perspective of the data. This has driven many researchers to investigate new effective clustering models to overcome these difficulties. One promising category of such models relies on representation learning. Indeed, learning a good data representation is crucial for clustering algorithms, and combining the two tasks is a common way of exploring this type of data. The idea is to embed the original data into a low dimensional latent space and then perform clustering on this new space. However, both tasks can be carried out sequentially or jointly. Many clustering algorithms, including deep learning versions, are based on these two modes of combining the two tasks.

Subspace clustering seeks to cluster high-dimensional data lying in a union of low-dimensional subspaces. It has achieved state-of-the-art results in image clustering, but text clustering of document-term matrices, has proved more impervious to advances with this approach, even though text data satisfies the assumptions of subspace clustering. We hypothesize that this is because such matrices are generally sparser and higher-dimensional than images. This, combined with the complexity of subspace clustering, which is generally cubic in the number of inputs, makes its use impractical in the context of text. Here we address these issues with a view to leveraging subspace clustering for networked (or not) text data. We first extend the concept of subspace clustering to co-clustering, which is suitable to deal with document-term matrices because of the interplay engendered between the document and word representations. We then address the sparsity problem through bilateral graph convolution, which promotes the grouping effect that has been credited for the effectiveness of some subspace clustering models. The proposed formulation results in an algorithm that is computationally/spatially efficient. Experiments using real-world datasets demonstrate the superior performance, in terms of document clustering, word clustering, and computational efficiency, of our proposed approach over the baselines and comparable methods.

Over the last few years, various multi-view graph clustering methods have shown promising performances. However, we argue that these methods can have limitations. In particular, they are often unnecessarily complex, leading to scalability problems that make them prohibitive for most real-world graph applications. Furthermore, many of them can handle only specific types of multi-view graphs. Another limitation is that the process of learning graph representations is separated from the clustering process, and in some cases these methods do not even learn a graph representation, which severely restricts their flexibility and usefulness. In this paper we propose a simple yet effective linear model that addresses the dual tasks of multi-view attributed graph representation learning and clustering in a unified framework. The model starts by performing a first-order neighborhood smoothing step for the different individual views, then gives each one a weight corresponding to its importance. Finally, an iterative process of simultaneous clustering and representation learning is performed w.r.t. the importance of each view, yielding a consensus embedding and partition of the graph. Our model is generic and can deal with any type of multi-view graph. Finally, we show through extensive experimentation that this simple model consistently achieves competitive performances w.r.t. state-of-the-art multi-view attributed graph clustering models, while at the same time having training times that are shorter, in some cases by orders of magnitude.

Subspace clustering aims to cluster high dimensional data lying in a union of low-dimensional subspaces. It has shown good results on the task of image clustering but text clustering, using document-term matrices, proved more impervious to advances based on this approach. We hypothesize that this is because, compared to image data, text data is generally higher dimensional and sparser. This renders subspace clustering impractical in such a context. Here, we leverage subspace clustering for text by addressing these issues. We first extend the concept of subspace clustering to co-clustering, which has been extensively used on document-term matrices due to the resulting interplay between the document and term representations. We then address the sparsity problem through a two-way graph convolution, which promotes the grouping effect that has been credited for the effectiveness of some subspace clustering models. The proposed formulation results in an algorithm that is efficient both in terms of computational and spatial complexity. We show the competitiveness of our model w.r.t the state-of-the-art on document-term attributed graph datasets in terms of performance and efficiency.

Attributed graphs are used to model a wide variety of real-world networks. Recent graph convolutional network-based representation learning methods have set state-of-the-art results on the clustering of attributed graphs. However, these approaches deal with clustering as a downstream task while better performances can be attained by incorporating the clustering objective into the representation learning process. In this paper, we propose, in a unified framework, an objective function taking into account both tasks simultaneously. Based on a variant of the simple graph convolutional network, our model does clustering by minimizing the difference between the convolved node representations and their reconstructed cluster representatives. We showcase the efficiency of the derived algorithm against state-of-the-art methods both in terms of clustering performance and computational cost on thede facto benchmark graph clustering datasets. We further demonstrate the usefulness of the proposed approach for graph visualization through generating embeddings that exhibit a clustering structure.

Co-clustering of document-term matrices has proved to be more effective than one-sided clustering. By their nature, text data are also generally unbalanced and directional. Recently, the von Mises-Fisher (vMF) mixture model was proposed to handle unbalanced data while harnessing the directional nature of text. In this paper we propose a novel co-clustering approach based on a matrix formulation of vMF model-based co-clustering. This formulation leads to a flexible method for text co-clustering that can easily incorporate both word-word semantic relationships and document-document similarities. By contrast with existing methods, which generally use an additive incorporation of similarities, we propose a dual multiplicative regularization that better encapsulates the underlying text data structure. Extensive evaluations on various real-world text datasets demonstrate the superior performance of our proposed approach over baseline and competitive methods, both in terms of clustering results and co-cluster topic coherence.

Abstract Dealing with relational learning generally relies on tools modeling relational data. An undirected graph can represent these data with vertices depicting entities and edges describing the relationships between the entities. These relationships can be well represented by multiple undirected graphs over the same set of vertices with edges arising from different graphs catching heterogeneous relations. The vertices of those networks are often structured in unknown clusters with varying properties of connectivity. These multiple graphs can be structured as a three-way tensor, where each slice of tensor depicts a graph which is represented by a count data matrix. To extract relevant clusters, we propose an appropriate model-based co-clustering capable of dealing with multiple graphs. The proposed model can be seen as a suitable tensor extension of mixture models of graphs, while the obtained co-clustering can be treated as a consensus clustering of nodes from multiple graphs. Applications on real datasets and comparisons with multi-view clustering and tensor decomposition methods show the interest of our contribution.

In this paper, we propose a unified framework for Ensemble Block Co-clustering (EBCO), which aims to fuse multiple basic co-clusterings into a consensus structured affinity matrix. Each co-clustering to be fused is obtained by applying a co-clustering method on the same document-term dataset. This fusion process reinforces the individual quality of the multiple basic data co-clusterings within a single consensus matrix. Besides, the proposed framework enables a completely unsupervised co-clustering where the number of co-clusters is automatically inferred based on the non trivial generalized modularity. We first define an explicit objective function which allows the joint learning of the basic co-clusterings aggregation and the consensus block co-clustering. Then, we show that EBCO generalizes the one side ensemble clustering to an ensemble block co-clustering context. We also establish theoretical equivalence to spectral co-clustering and weighted double spherical k-means clustering for textual data. Experimental results on various real-world document-term datasets demonstrate that EBCO is an efficient competitor to some state-of-the-art ensemble and co-clustering methods.

To deal with document clustering, we usually rely on document-term matrices. However, from additional available information like keywords, co-authors, citations we might rather exploit a reorganization of the data in the form of a tensor. In this paper, we extend the use of the Sparse Poisson Latent Block Model to deal with sparse tensor data using jointly all information arising from documents. The proposed model is parsimonious and tailored for this kind of data. To estimate the parameters, we derive a suitable tensor co-clustering algorithm. Empirical results on several real-world text datasets highlight the advantages of our proposal which improves the clustering results of documents.

In this work, we propose a novel way to consider the clustering and the reduction of the dimension simultaneously. Indeed, our approach takes advantage of the mutual reinforcement between data reduction and clustering tasks. The use of a low-dimensional representation can be of help in providing simpler and more interpretable solutions. We show that by doing so, our model is able to better approximate the relaxed continuous dimension reduction solution by the true discrete clustering solution. Experiment results show that our method gives better results in terms of clustering than the state-of-the-art algorithms devoted to similar tasks for data sets with different proprieties.

Several studies have demonstrated the importance of co-clustering which aims to cluster simultaneously the sets of objects and features. The co-clustering is often more effective than one-side clustering, especially when considering sparse high dimensional data. In this paper, we propose a novel way to consider the co-clustering and the reduction of the dimension simultaneously. Our approach takes advantage of the mutual reinforcement between Principal Component Analysis (PCA) which provides a low-dimensional representation of data and Semi-Nonnegative Matrix Factorization (SemiNMF) that learns this low-dimensional representation and lends itself to a co-clustering interpretation. In other words, the proposed framework aims to find an optimal subspace of multi-dimensional variables for effectively identifying a partition of the set of objects. We show that by doing so, our model is able to learn low-dimensional representations that are better suited for co-clustering, outperforming not only spectral methods, but also co-clustering graph-regularized-based methods.

Spectral clustering methods use the Laplacian eigenvalues and eigenvectors to obtain a low-dimensional embedding that can be trivially clustered. For that purpose, spectral clustering is often based on a tandem approach where the two steps: affinity matrix eigendecomposition and k-means clustering, are performed separately. The potential flaw of such common practice is that the obtained relaxed continuous spectral solution can severely deviate from the true discrete clustering solution. Given the high computational cost of such spectral clustering methods, this paper provides the so-called PSDEC framework. PSDEC performs simultaneously the eigendecomposition of the affinity matrix and clustering tasks, and uses the Power method to speed up the unified process convergence. In PSDEC, the selected top eigenvectors of the Laplacian matrix can be of help in detecting a cluster structure of objects and providing simpler and more interpretable solutions. We show that by doing so, our method can learn low-dimensional representations that are better suited to clustering, outperforming not only spectral clustering algorithms but also some NMF variants.

Cluster analysis is often carried out in combination with dimension reduction. The Semi-Non-negative Matrix Factorization (Semi-NMF) that learns a low-dimensional representation of a data set lends itself to a clustering interpretation. In this work we propose a novel approach to finding an optimal subspace of multi-dimensional variables for identifying a partition of the set of objects. The use of a low-dimensional representation can be of help in providing simpler and more interpretable solutions. We show that by doing so, our model is able to learn low-dimensional representations that are better suited for clustering, outperforming not only Semi-NMF, but also other NMF variants.

To tackle the co-clustering problem for binary and categorical data, we propose a generalized modularity measure and a spectral approximation of the modularity matrix. A spectral algorithm maximizing the modularity measure is then presented. Experimental results are performed on a variety of simulated and real-world data sets confirming the interest of the use of the modularity in co-clustering and assessing the number of clusters contexts.