The problem of representative selection amounts to sampling few informative exemplars from large datasets. Existing approaches to data selection often fall short of simultaneously handling non-linear data structures, sampling concise and non-redundant subsets, rejecting outliers, and yielding interpretable outcomes. This paper presents a novel representative selection approach, dubbed MOSAIC, for drawing descriptive sketches of arbitrary manifold structures. Resting upon a novel quadratic formulation, MOSAIC advances a multi-criteria selection approach that maximizes the global representation power of the sampled subset, ensures novelty of the samples by minimizing redundancy, and rejects disruptive information by effectively detecting outliers. Theoretical analyses shed light on geometrical characterization of the obtained sketch and reveal that the sampled representatives maximize a well-defined notion of data coverage in a transformed space. In addition, we present a highly scalable randomized implementation of the proposed algorithm shown to bring about substantial speedups. MOSAIC’s superiority in achieving the desired characteristics of a representative subset all at once while exhibiting remarkable robustness to various outlier types is demonstrated via extensive experiments conducted on both real and synthetic data with comparisons to state-of-the-art algorithms.

This paper proposes a sketch-based approach to the community detection problem which clusters the full graph through the use of an informative and concise sketch. The reduced sketch is built through an effective sampling approach which selects few nodes that best represent the complete graph and operates on a pairwise node similarity measure based on the average commute time. After sampling, the proposed algorithm clusters the nodes in the sketch, and then infers the cluster membership of the remaining nodes in the full graph based on their aggregate similarity to nodes in the partitioned sketch. By sampling nodes with strong representation power, our approach can improve the success rates over full graph clustering. In challenging cases with large node degree variation, our approach not only maintains competitive accuracy with full graph clustering despite using a small sketch, but also outperforms existing sampling methods. The use of a small sketch allows considerable storage savings, and computational and timing improvements for further analysis such as clustering and visualization. We provide numerical results on synthetic data based on the homogeneous, heterogeneous and degree corrected versions of the stochastic block model, as well as experimental results on real-world data.

This letter presents an effective and simple method, termed Global Conformity Pursuit (GCP), for robust manifold learning. Data points lying on a union of low-dimensional nonlinear manifolds are expected to be highly conforming. On the other hand, outliers do not typically adhere to low-dimensional structures or otherwise do not exist in large numbers. Hence, they can be identified by their low overall resemblance to the rest of the data. Our kernel-based setting allows us to capture the underlying nonlinear structure of the manifold data, while avoiding the construction of local neighborhood regions which typically causes extreme sensitivity to noise and outliers. Aside from its significantly simple structure-involving only a matrix evaluation and multiplication-GCP is the first manifold learning approach that is simultaneously noniterative and capable of tolerating a large number of outliers, dependent outliers, and noise components. Theoretical analysis guarantees a large gap between conformity values of inliers and outliers. Experimental results showcase potential uses of the proposed framework on benchmark datasets.

In this paper, we introduce a novel hash learning framework for multi-label learning which employs structured prediction. A hash function is learned to embed samples in Hamming spaces, and for each label, a pair of codewords are simultaneously inferred from the available data. These codewords are then used to determine label predictions based on Hamming proximity. The key advantage of this framework is it's computational efficiency in tackling multi-label problems without making restrictive, simplifying assumptions about the structure of the output space, or developing problem-dependent heuristics. Our method not only enjoys considerably better scalability while capturing label inter-dependence, but also yields an exact training algorithm. Experimental results on a collection of benchmark multi-label datasets demonstrate that our model attains higher performance over alternative state-of-the-art multi-label approaches. It is also worth noting that our method can be extended to semi-supervised and missing labels scenarios.

Metric Multi-Dimensional Scaling is one of the most popular visualization techniques aiming to determine a point configuration of the data in a low-dimensional space, while preserving the original pairwise dissimilarities amongst the data points. In this paper we propose Sparse Inductive Multi- Dimensional Scaling approach, an exploratory data analysis and visualization tool. Its kernel-based nature provides an inductive method, and hence allows for embedding of previously unseen data even with non-numerical features. Furthermore, via the use of a sparsity-promoting regularizer, the technique is capable of identifying key training samples, whose contribution in defining the embedded manifold's specific structure is most influential. As we will show, the influence of these samples leads us to interesting interpretations in the context of the data at hand. We adequately train the consequent non-convex framework via an Iterative Majorization approach, for which a stable closed-form solution is obtained. Experimental results showcase the potential benefits of the proposed embedding method on both artificial and real-world data.