Search

We propose a novel discriminative feature learning method via Max-Min Ratio Analysis (MMRA) for exclusively dealing with the long-standing “worst-case class separation” problem. Existing technologies simply consider maximizing the minimal pairwise distance on all class pairs in the low-dimensional subspace, which is unable to separate overlapped classes entirely especially when the distribution of samples within same class is diverging. We propose a new criterion, i.e., Max-Min Ratio Analysis (MMRA) that focuses on maximizing the minimal ratio value of between-class and within-class scatter to extremely enlarge the separability on the overlapped pairwise classes. Furthermore, we develop two novel discriminative feature learning models for dimensionality reduction and metric learning based on our MMRA criterion. However, solving such a non-smooth non-convex max-min ratio problem is challenging. As an important theoretical contribution in this paper, we systematically derive an alternative iterative algorithm based on a general max-min ratio optimization framework to solve a general max-min ratio problem with rigorous proofs of convergence. More importantly, we also present another solver based on bisection search strategy to solve the SDP problem efficiently. To evaluate the effectiveness of proposed methods, we conduct extensive pattern classification and image retrieval experiments on several artificial datasets and real-world ScRNA-seq datasets, and experimental results demonstrate the effectiveness of proposed methods.

Normalized-Cut (N-Cut) is a famous model of spectral clustering. The traditional N-Cut solvers are two-stage: 1) calculating the continuous spectral embedding of normalized Laplacian matrix; 2) discretization via $K$K-means or spectral rotation. However, this paradigm brings two vital problems: 1) two-stage methods solve a relaxed version of the original problem, so they cannot obtain good solutions for the original N-Cut problem; 2) solving the relaxed problem requires eigenvalue decomposition, which has ${\mathcal {O}}(n^{3})$error(n3) time complexity ($n$n is the number of nodes). To address the problems, we propose a novel N-Cut solver designed based on the famous coordinate descent method. Since the vanilla coordinate descent method also has ${\mathcal {O}}(n^{3})$error(n3) time complexity, we design various accelerating strategies to reduce the time complexity to ${\mathcal {O}}(|E|)$error(|E|) ($|E|$|E| is the number of edges). To avoid reliance on random initialization which brings uncertainties to clustering, we propose an efficient initialization method that gives deterministic outputs. Extensive experiments on several benchmark datasets demonstrate that the proposed solver can obtain larger objective values of N-Cut, meanwhile achieving better clustering performance compared to traditional solvers.

Satellites are capable of capturing high-resolution videos. It makes vehicle perception from satellite become possible. Compared to street surveillance, drive recorder or other equipments, satellite videos provide a much broader city-scale view, so that the global dynamic scene of the traffic are captured and displayed. Traffic monitoring from satellite is a new task with great potential applications, including traffic jams prediction, path planning, vehicle dispatching, etc. Practically, limited by the resolution and view, the captured vehicles are very tiny (a few pixels) and move slowly. Worse still, these satellites are in Low Earth Orbit (LEO) to capture such high-resolution videos, so the background is also moving. Under this circumstance, traffic monitoring from the satellite view is an extremely challenging task. To attract more researchers into this field, we build a large-scale benchmark for traffic monitoring from satellite. It supports several tasks, including tiny object detection, counting and density estimation. The dataset is constructed based on 12 satellite videos and 14 synthetic videos recorded from GTA-V. They are separated into 408 video clips, which contain 7,336 real satellite images and 1,960 synthetic images. 128,801 vehicles are annotated totally, and the number of vehicles in each image varies from 0 to 101. Several classic and state-of-the-art approaches in traditional computer vision are evaluated on the datasets, so as to compare the performance of different approaches, analyze the challenges in this task, and discuss the future prospects.

Spectral Clustering (SC) has been the main subject of intensive research due to its remarkable clustering performance. Despite its successes, most existing SC methods suffer from several critical issues. First, they typically involve two independent stages, i.e., learning the continuous relaxation matrix followed by the discretization of the cluster indicator matrix. This two-stage approach can result in suboptimal solutions that negatively impact the clustering performance. Second, these methods are hard to maintain the balance property of clusters inherent in many real-world data, which restricts their practical applicability. Finally, these methods are computationally expensive and hence unable to handle large-scale datasets. In light of these limitations, we present a novel Discrete and Balanced Spectral Clustering with Scalability (DBSC) model that integrates the learning the continuous relaxation matrix and the discrete cluster indicator matrix into a single step. Moreover, the proposed model also maintains the size of each cluster approximately equal, thereby achieving soft-balanced clustering. What's more, the DBSC model incorporates an anchor-based strategy to improve its scalability to large-scale datasets. The experimental results demonstrate that our proposed model outperforms existing methods in terms of both clustering performance and balance performance. Specifically, the clustering accuracy of DBSC on CMUPIE data achieved a 17.93% improvement compared with that of the SOTA methods (LABIN, EBSC, etc.).

Deep neural network (DNN) generally takes thousands of iterations to optimize via gradient descent and thus has a slow convergence. In addition, softmax, as a decision layer, may ignore the distribution information of the data during classification. Aiming to tackle the referred problems, we propose a novel manifold neural network based on non-gradient optimization, i.e., the analytical-form solutions. Considering that the activation function is generally invertible, we reconstruct the network via forward ridge regression and low-rank backward approximation, which achieve rapid convergence. Moreover, by unifying the flexible Stiefel manifold and adaptive support vector machine, we devise the novel decision layer which efficiently fits the manifold structure of the data and label information. Consequently, a jointly non-gradient optimization method is designed to generate the network with analytical-form results. Furthermore, an acceleration strategy is utilize to reduce the time complexity for handling high dimensional datasets. Eventually, extensive experiments validate the superior performance of the model.

Generating photo-realistic images from labels (e.g., semantic labels or sketch labels) is much more challenging than the general image-to-image translation task, mainly due to the large differences between extremely sparse labels and detail rich images. We propose a general framework Lab2Pix to tackle this issue from two aspects: 1) how to extract useful information from the input; and 2) how to efficiently bridge the gap between the labels and images. Specifically, we propose a Double-Guided Normalization (DG-Norm) to use the input label for semantically guiding activations in normalization layers, and use global features with large receptive fields for differentiating the activations within the same semantic region. To efficiently generate the images, we further propose Label Guided Spatial Co-Attention (LSCA) to encourage the learning of incremental visual information using limited model parameters while storing the well-synthesized part in lower-level features. Accordingly, Hierarchical Perceptual Discriminators with Foreground Enhancement Masks are proposed to toughly work against the generator thus encouraging realistic image generation and a sharp enhancement loss is further introduced for high-quality sharp image generation. We instantiate our Lab2Pix for the task of label-to-image in both unpaired (Lab2Pix-V1) and paired settings (Lab2Pix-V2). Extensive experiments conducted on various datasets demonstrate that our method significantly outperforms state-of-the-art methods quantitatively and qualitatively in both settings.

In the field of data mining, how to deal with high-dimensional data is an inevitable topic. Since it does not rely on labels, unsupervised feature selection has attracted a lot of attention. The performance of spectral-based unsupervised methods depends on the quality of the constructed similarity matrix, which is used to depict the intrinsic structure of data. However, real-world data often contain plenty of noise features, making the similarity matrix constructed by original data cannot be completely reliable. Worse still, the size of a similarity matrix expands rapidly as the number of samples rises, making the computational cost increase significantly. To solve this problem, a simple and efficient unsupervised model is proposed to perform feature selection. We formulate PCA as a reconstruction error minimization problem, and incorporate a $\ell _{2,p}$ℓ2,p-norm regularization term to make the projection matrix sparse. The learned row-sparse and orthogonal projection matrix is used to select discriminative features. Then, we present an efficient optimization algorithm to solve the proposed unsupervised model, and analyse the convergence and computational complexity of the algorithm theoretically. Finally, experiments on both synthetic and real-world data sets demonstrate the effectiveness of our proposed method.

The principal subspace estimation is directly connected to dimension reduction and is important when there is more than one principal component of interest. In this article, we introduce two new algorithms to solve the feature-sparsity constrained PCA problem (FSPCA) for the principal subspace estimation task, which performs feature selection and PCA simultaneously. Existing optimization methods for FSPCA require data distribution assumptions and are lack of global convergence guarantee. Though the general FSPCA problem is NP-hard, we show that, for a low-rank covariance, FSPCA can be solved globally (Algorithm 1). Then, we propose another strategy (Algorithm 2) to solve FSPCA for the general covariance by iteratively building a carefully designed proxy. We prove (data-dependent) approximation bound and regular stationary convergence guarantees for the new algorithms. For the spectrum of covariance with exponential/Zipf's distribution, we provide exponential/posynomial approximation bounds. Constructive examples and numerical results are provided to demonstrate the tightness of our results. Experimental results show the promising performance and efficiency of the new algorithms compared with the state-of-the-arts on both synthetic and real-world datasets.

Graph autoencoders (GAEs) are powerful tools in representation learning for graph embedding. However, the performance of GAEs is very dependent on the quality of the graph structure, i.e., of the adjacency matrix. In other words, GAEs would perform poorly when the adjacency matrix is incomplete or be disturbed. In this paper, two novel unsupervised graph embedding methods, unsupervised graph embedding via adaptive graph learning (BAGE) and unsupervised graph embedding via variational adaptive graph learning (VBAGE) are proposed. The proposed methods expand the application range of GAEs on graph embedding, i.e, on the general datasets without graph structure. Meanwhile, the adaptive learning mechanism can initialize the adjacency matrix without being affected by the parameter. Besides that, the latent representations are embedded with the Laplacian graph structure to preserve the topology structure of the graph in the vector space. Moreover, the adjacency matrix can be self-learned for better embedding performance when the original graph structure is incomplete. With adaptive learning, the proposed method is much more robust to the graph structure. Experimental studies on several datasets validate our design and demonstrate that our methods outperform baselines by a wide margin in node clustering, node classification, link prediction, and graph visualization tasks.

Hamiltonian learning, as an important quantum machine learning technique, provides a significant approach for determining an accurate quantum system. This paper establishes parameterized Hamiltonian learning (PHL) and explores its application and implementation on quantum computers. A parameterized quantum circuit for Hamiltonian learning is first created by decomposing unitary operators to excite the system evolution. Then, a PHL algorithm is developed to prepare a specific Hamiltonian system by iteratively updating the gradient of the loss function about circuit parameters. Finally, the experiments are conducted on Origin Pilot, and it demonstrates that the PHL algorithm can deal with the image segmentation problem and provide a segmentation solution accurately. Compared with the classical Grabcut algorithm, the PHL algorithm eliminates the requirement of early manual intervention. It provides a new possibility for solving practical application problems with quantum devices, which also assists in solving increasingly complicated problems and supports a much wider range of application possibilities in the future.

Multi-view clustering aims to discover common patterns from multi-source data, whose generality is remarkable. Compared with traditional methods, deep learning methods are data-driven and have a larger search space for solutions, which may find a better solution to the problem. In addition, more considerations can be introduced by loss functions, so deep models are highly reusable. However, compared with deep learning methods, traditional methods have better interpretability, whose optimization is relatively stable. In this paper, we propose a multi-view spectral clustering model, combining the advantages of traditional methods and deep learning methods. Specifically, we start with the objective function of traditional spectral clustering, perform multi-view extension, and then obtain the traditional optimization process. By partially parameterizing this process, we further design corresponding differentiable modules, and finally construct a complete network structure. The model is interpretable and extensible to a certain extent. Experiments show that the model performs better than other multi-view clustering algorithms, and its semi-supervised classification extension also has excellent performance compared to other algorithms. Further experiments also show the stability and fewer iterations of the model training.

Since the representative capacity of graph-based clustering methods is usually limited by the graph constructed on the original features, it is attractive to find whether graph neural networks (GNNs), a strong extension of neural networks to graphs, can be applied to augment the capacity of graph-based clustering methods. The core problems mainly come from two aspects. On the one hand, the graph is unavailable in the most general clustering scenes so that how to construct graph on the non-graph data and the quality of graph is usually the most important part. On the other hand, given $n$n samples, the graph-based clustering methods usually consume at least $\mathcal {O}(n^{2})$O(n2) time to build graphs and the graph convolution requires nearly $\mathcal {O}(n^{2})$O(n2) for a dense graph and $\mathcal {O}(|\mathcal {E}|)$O(|E|) for a sparse one with $|\mathcal {E}|$|E| edges. Accordingly, both graph-based clustering and GNNs suffer from the severe inefficiency problem. To tackle these problems, we propose a novel clustering method, AnchorGAE, with the self-supervised estimation of graph and efficient graph convolution. We first show how to convert a non-graph dataset into a graph dataset, by introducing the generative graph model and anchors. A bipartite graph is built via generating anchors and estimating the connectivity distributions of original points and anchors. We then show that the constructed bipartite graph can reduce the computational complexity of graph convolution from $\mathcal {O}(n^{2})$O(n2) and $\mathcal {O}(|\mathcal {E}|)$O(|E|) to $\mathcal {O}(n)$O(n). The succeeding steps for clustering can be easily designed as $\mathcal {O}(n)$O(n) operations. Interestingly, the anchors naturally lead to siamese architecture with the help of the Markov process. Furthermore, the estimated bipartite graph is updated dynamically according to the features extracted by GNN modules, to promote the quality of the graph by exploiting the high-level information by GNNs. However, we theoretically prove that the self-supervised paradigm frequently results in a collapse that often occurs after 2-3 update iterations in experiments, especially when the model is well-trained. A specific strategy is accordingly designed to prevent the collapse. The experiments support the theoretical analysis and show the superiority of AnchorGAE.