Graph Laplacian Mixture Model | EPFL Graph Search

Graph learning methods have recently been receiving increasing interest as means to infer structure in datasets. Most of the recent approaches focus on different relationships between a graph and data sample distributions, mostly in settings where all available data relate to the same graph. This is, however, not always the case, as data is often available in mixed form, yielding the need for methods that are able to cope with mixture data and learn multiple graphs. We propose a novel generative model that represents a collection of distinct data which naturally live on different graphs. We assume the mapping of data to graphs is not known and investigate the problem of jointly clustering a set of data and learning a graph for each of the clusters. Experiments demonstrate promising performance in data clustering and multiple graph inference, and show desirable properties in terms of interpretability and coping with high dimensionality on weather and traffic data, as well as digit classification.

Representing graphs through data with learning and optimal transport

Hermina Petric Maretic

Graphs offer a simple yet meaningful representation of relationships between data. Thisrepresentation is often used in machine learning algorithms in order to incorporate structuralor geometric information about data. However, it can also be used in an inverted fashion:instead of modelling data through graphs, we model graphs through data distributions. In thisthesis, we explore several applications of this new modelling framework.Starting with the graph learning problem, we exploit the probabilistic model of data giventhrough graphs to propose a multi-graph learning method for structured data mixtures. Weexplore various relations that data can have with the underlying graphs through the notionof graph filters. We propose an algorithm to jointly cluster a set of data and learn a graph foreach of the clusters. Experiments demonstrate promising performance in data clusteringand multiple graph inference, and show desirable properties in terms of interpretability andproper handling of high dimensionality on synthetic and real data. The model has further beenapplied to fMRI data, where the method is used to successfully identify different functionalbrain networks and their activation times.This probabilistic model of data defined through graphs can be very meaningful evenwhen no data is available. Thus, in the second part of this thesis, we use such models torepresent each graph through the probabilistic distribution of data, which varies smoothly onthe graph. Optimal transport allows for a comparison of two such distributions, which in turngives a structurally meaningful measure for graph comparison. We follow by using this distance to formulate a new graph alignment problem based on theoptimal transport framework, and propose an efficient stochastic algorithm based onBayesian exploration to accommodate for the nonconvexity of the graph alignment problem.We demonstrate the performance of our novel framework on different tasks like graph alignment,graph classification and graph signal prediction, and we show that our method leads tosignificant improvement with respect to the state-of-art algorithms.Furthermore, we cast a new formulation for the one-to-many graph alignment problem,allowing for comparison of graphs of different sizes. The resulting alignment problem issolved with stochastic gradient descent, where a novel Dykstra operator ensures that thesolution is a one-to-many (soft) assignment matrix. Experiments on graph alignment and graph classification problems show that our method for one-to-many alignment leads to meaningful improvements with respect to the state-of-the-art algorithms for each of thesetasks.Finally, we explore a family of probabilistic distributions for data based on graph filters.Distances defined through a graph filter give a high level of flexibility in choosing whichgraph properties we want to emphasize. In addition, in order to make the above graphalignment problem more scalable, we formulate an approximation to our filter Wassersteingraph distance that allows for the exploitation of faster algorithms, without grossly sacrificingthe performance. We propose two algorithms, a simple one based on mirror gradient descentand another one built on its stochastic version, which offers a trade-off between speed andaccuracy. Our experiments show the performance benefits of our novel stochastic algorithm,as well as the strong value of flexibility offered by filter-based distances.

EPFL2021

Learning the structure of image collections with latent aspect models

Florent Monay Michaud

The approach to indexing an image collection depends on the type of data to organize. Satellite images are likely to be searched with latitude and longitude coordinates, medical images are often searched with an image example that serves as a visual query, and personal image collections are generally browsed by event. A more general retrieval scenario is based on the use of textual keywords to search for images containing a specific object, or representing a given scene type. This requires the manual annotation of each image in the collection to allow for the retrieval of relevant visual information based on a text query. This time-consuming and subjective process is the current price to pay for a reliable and convenient text-based image search. This dissertation investigates the use of probabilistic models to assist the automatic organization of image collections, attempting to link the visual content of digital images with a potential textual description. Relying on robust, patch-based image representations that have proven to capture a variety of visual content, our work proposes to model images as mixtures of latent aspects. These latent aspects are defined by multinomial distributions that capture patch co-occurrence information observed in the collection. An image is not represented by the direct count of its constituting elements, but as a mixture of latent aspects that can be estimated with principled, generative unsupervised learning methods. An aspect-based image representation therefore incorporates contextual information from the whole collection that can be exploited. This emerging concept is explored for several fundamental tasks related to image retrieval – namely classification, clustering, segmentation, and annotation – in what represents one of the first coherent and comprehensive study of the subject. We first investigate the possibility of classifying images based on their estimated aspect mixture weights, interpreting latent aspect modeling as an unsupervised feature extraction process. Several image categorization tasks are considered, where images are classified based on the present objects or according to their global scene type. We demonstrate that the concept of latent aspects allows to take advantage of non-labeled data to infer a robust image representation that achieves a higher classification performance than the original patch-based representation. Secondly, further exploring the concept, we show that aspects can correspond to an interesting soft clustering of an image collection that can serve as a browsing structure. Images can be ranked given an aspect, illustrating the corresponding co-occurrence context visually. In the third place, we derive a principled method that relies on latent aspects to classify image patches into different categories. This produces an image segmentation based on the resulting spatial class-densities. We finally propose to model images and their caption with a single aspect model, merging the co-occurrence contexts of the visual and the textual modalities in different ways. Once a model has been learned, the distribution of words given an unseen image is inferred based on its visual representation, and serves as textual indexing. Overall, we demonstrate with extensive experiments that the co-occurrence context captured by latent aspects is suitable for the above mentioned tasks, making it a promising approach for multimedia indexing.

EPFL2007

Fast high-dimensional Bayesian classification and clustering

Vahid Partovi Nia

We introduce a fast approach to classification and clustering applicable to high-dimensional continuous data, based on Bayesian mixture models for which explicit computations are available. This permits us to treat classification and clustering in a single framework, and allows calculation of unobserved class probability. The new classifier is robust to adding noise variables as a drawback of the built-in spike-and-slab structure of the proposed Bayesian model. The usefulness of classification using our method is shown on metabololomic example, and on the Iris data with and without noise variables. Agglomerative hierarchical clustering is used to construct a dendrogram based on the posterior probabilities of particular partitions, to provide a dendrogram with a probabilistic interpretation. An extension to variable selection is proposed which summarises the importance of variables for classification or clustering and has probabilistic interpretation. Having a simple model provides estimation of the model parameters using maximum likelihood and therefore yields a fully automatic algorithm. The new clustering method is applied to metabolomic, microarray, and image data and is studied using simulated data motivated by real datasets. The computational difficulties of the new approach are discussed, solutions for algorithm acceleration are proposed, and the written computer code is briefly analysed. Simulations shows that the quality of the estimated model parameters depends on the parametric distribution assumed for effects, but after fixing the model parameters to reasonable values, the distribution of the effects influences clustering very little. Simulations confirms that the clustering algorithm and the proposed variable selection method is reliable when the model assumptions are wrong. The new approach is compared with the popular Bayesian clustering alternative, MCLUST, fitted on the principal components using two loss functions in which our proposed approach is found to be more efficient in almost every situation.

EPFL2009