Spectral clustering requires the time-consuming decomposition of the Laplacian matrix of the similarity graph, thus limiting its applicability to large datasets. To improve the efficiency of spectral clustering, a top-down approach was recently proposed, which first divides the data into several micro-clusters (granular-balls), then splits these micro-clusters when they are not ``compact'', and finally uses these micro-clusters as nodes to construct a similarity graph for more efficient spectral clustering. However, this top-down approach is challenging to adapt to unevenly distributed or structurally complex data. This is because constructing micro-clusters as a rough ball struggles to capture the shape and structure of data in a local range, and the simplistic splitting rule that solely targets ``compactness'' is susceptible to noise and variations in data density and leads to micro-clusters with varying shapes, making it challenging to accurately measure the similarity between them. To resolve these issues and improve spectral clustering, this paper first proposes to start from local structures to obtain micro-clusters, such that the complex structural information inside local neighborhoods is well captured by them. Moreover, by noting that Euclidean distance is more suitable for convex sets, this paper further proposes a data splitting rule that couples local density and data manifold structures, so that the similarities of the obtained micro-clusters can be easily characterized. A novel similarity measure between micro-clusters is then proposed for the final spectral clustering. A series of experiments based on synthetic and real-world datasets demonstrate that the proposed method has better adaptability to structurally complex data than granular-ball based methods.

Density-based mode-seeking methods generate a density-ascending dependency from low-density points towards higher-density neighbors. Current mode-seeking methods identify modes by breaking some dependency connections, but relying heavily on local data characteristics, requiring case-by-case threshold settings or human intervention to be effective for different datasets. To address this issue, we introduce a novel concept called typicality, by exploring the locally defined dependency from a global perspective, to quantify how confident a point would be a mode. We devise an algorithm that effectively and efficiently identifies modes with the help of the global-view typicality. To implement and validate our idea, we design a clustering method called TANGO, which not only leverages typicality to detect modes, but also utilizes graph-cut with an improved path-based similarity to aggregate data into the final clusters. Moreover, this paper also provides some theoretical analysis on the proposed algorithm. Experimental results on several synthetic and extensive real-world datasets demonstrate the effectiveness and superiority of TANGO. The code is available at https://github.com/SWJTU-ML/TANGO_code.

Traditional logic-based belief revision research focuses on designing rules to constrain the behavior of revision operators. Frameworks have been proposed to characterize iterated revision rules, but they are often too loose, leading to multiple revision operators that all satisfy the rules under the same belief condition. In many practical applications, such as safety critical ones, it is important to specify a definite revision operator to enable agents to iteratively revise their beliefs in a deterministic way. In this paper, we propose a novel framework for iterated belief revision by characterizing belief information through preference relations. Semantically, both beliefs and new evidence are represented as belief algebras, which provide a rich and expressive foundation for belief revision. Building on traditional revision rules, we introduce additional postulates for revision with belief algebra, including an upper-bound constraint on the outcomes of revision. We prove that the revision result is uniquely determined given the current belief state and new evidence. Furthermore, to make the framework more useful in practice, we develop a particular algorithm for performing the proposed revision process. We argue that this approach may offer a more predictable and principled method for belief revision, making it suitable for real-world applications.

MOTIVATION: The rapid development of single-cell RNA sequencing (scRNA-seq) has significantly advanced biomedical research. Clustering analysis, crucial for scRNA-seq data, faces challenges including data sparsity, high dimensionality, and variable gene expressions. Better low-dimensional embeddings for these complex data should maintain intrinsic information while making similar data close and dissimilar data distant. However, existing methods utilizing neural networks typically focus on minimizing reconstruction loss and maintaining similarity in embeddings of directly related cells, but fail to consider dissimilarity, thus lacking separability and limiting the performance of clustering. RESULTS: We propose a novel clustering algorithm, called scHNTL (scRNA-seq data clustering augmented by high-order neighbors and triplet loss). It first constructs an auxiliary similarity graph and uses a Graph Attentional Autoencoder to learn initial embeddings of cells. Then it identifies similar and dissimilar cells by exploring high-order structures of the similarity graph and exploits a triplet loss of contrastive learning, to improve the embeddings in preserving structural information by separating dissimilar pairs. Finally, this improvement for embedding and the target of clustering are fused in a self-optimizing clustering framework to obtain the clusters. Experimental evaluations on 16 real-world datasets demonstrate the superiority of scHNTL in clustering over the state-of-the-arts single-cell clustering algorithms. AVAILABILITY AND IMPLEMENTATION: Python implementation of scHNTL is available at Figshare (https://doi.org/10.6084/m9.figshare.27001090) and Github (https://github.com/SWJTU-ML/scHNTL-code).

Neural networks, especially those update parameters by optimizing the difference between fit values and actual labels, often encounter challenges with real-world data containing mislabeled samples (called label noise). This label noise adversely affects the generalization performance of the network by disturbing local fit values. While existing network regularization methods such as data augmentation and label smoothing (LS) have shown usefulness in mitigating the devastation caused by label noise, they primarily focus on global constraints and overlook the local impacts of label noise. Furthermore, the detailed influence of label noise on network function remains underexplored. To fill this gap, our article presents an in-depth analysis of the local effects of label noise on neural networks from a topological perspective. A novel regularization method, network boundary topology regularization (NBTR), based on persistent homology, is introduced. This method is specifically designed for local fit values of the network, with the aim of simplifying the topology of each class boundary. By doing so, it effectively reduces the tendency of a network to memorize label noise. Extensive experiments have been conducted across a range of datasets, network structures, and noise types to validate the effectiveness of this method. Our findings demonstrate that this method not only surpasses strong baseline methods in network generalization accuracy, especially in asymmetric noise conditions (improving average generalization accuracy by 7.72%), but also enhances the anti-noise capabilities of traditional methods when integrated as a complementary method.

People often use qualitative relations to describe locations or directional information, especially in written communication, such as ‘the restaurant is located at the southeast corner of the square’. However, when a large number of spatial entities are involved, qualitative relations alone are not intuitive enough for people to understand a spatial configuration. In fact, many applications, e.g. pertaining to sharing travel experiences, use sketch maps, i.e. maps focusing on the main features of an area whilst abstracting exact scale measurements, to help demonstrate abstract qualitative relations with more intuitive geometric points. Current approaches for generating point sketch maps from qualitative spatial relations require a high level of expertise, face inherent difficulties with efficiently processing large-scale data in bulk, and are vulnerable to inaccurate or conflicting information contained in qualitative data. To address these limitations, by incorporating machine learning techniques, we propose to translate the problem into an optimization problem of data reconstruction, enabling a novel end-to-end approach for generating point sketch maps from qualitative directional relations in bulk. Experiments on real-world datasets show that the proposed approach has very high accuracy and is robust even with a large portion of inaccurate or incomplete information.

The instability is shown in the existing methods of representation learning based on Euclidean distance under a broad set of conditions. Furthermore, the scarcity and high cost of labels prompt us to explore more expressive representation learning methods which depends on as few labels as possible. To address above issues, the small-perturbation ideology is firstly introduced on the representation learning model based on the representation probability distribution. The positive small-perturbation information (SPI) which only depend on two labels of each cluster is used to stimulate the representation probability distribution and then two variant models are proposed to fine-tune the expected representation distribution of Restricted Boltzmann Machine (RBM), namely, Micro-supervised Disturbance Gaussian-binary RBM (Micro-DGRBM) and Micro-supervised Disturbance RBM (Micro-DRBM) models. The Kullback-Leibler (KL) divergence of SPI is minimized in the same cluster to promote the representation probability distributions to become more similar in Contrastive Divergence (CD) learning. In contrast, the KL divergence of SPI is maximized in the different clusters to enforce the representation probability distributions to become more dissimilar in CD learning. To explore the representation learning capability under the continuous stimulation of the SPI, we present a deep Micro-supervised Disturbance Learning (Micro-DL) framework based on the Micro-DGRBM and Micro-DRBM models and compare it with a similar deep structure which has no external stimulation. Experimental results demonstrate that the proposed deep Micro-DL architecture shows better performance in comparison to the baseline method, the most related shallow models and deep frameworks for clustering.

In this paper, we present an online (incremental) algorithm for checking the satisfiability of qualitative spatio-temporal data, with direct implications to other fundamental knowledge representation and reasoning problems for such data, like the problems of deductive closure and redundancy removal. In particular, qualitative data come in the form of human-like, symbolic, descriptions such as "region x contains or overlaps region y", which are abundant in the Web of Data. Our approach is also able to maintain, to some extent, any sparse graph structure that may be inherent in the data, i.e., it acts parsimoniously and only tries to infer new information when needed for soundness and completeness. To this end, we complement our practical algorithm with certain theoretical results to assert its correctness and efficiency. A subsequent evaluation with publicly available large-scale real-world and random datasets against the state of the art, shows the interest and promise of our method.

To effectively and efficiently deal with large-scale spatial data is critical for applications in the age of information technology. Compact representation of spatial knowledge is one of the emerging research techniques that contribute to this capability. In this article, we consider the problem of compactly representing qualitative directional relations between extended objects, modelled in the Cardinal Direction Calculus (CDC) of Goyal and Egenhofer. For a large dataset of regions, this approach first constructs a simplified geometry for each region, which preserves CDC relations between regions, and then represents each simplified geometry compactly, so that the storage size is small while retrieving CDC relations from the representation is still reasonably fast. More specifically, the method called necessary cut is used to construct simple geometries , and the two methods, viz. the polygon representation and the rectangle representation , are devised to compactly represent the constructed geometries in cubic time w.r.t. the size of the corresponding simple geometry. Theoretical analyses demonstrate that the two representations, especially the rectangle representation, are promising to have small storage size. Moreover, our empirical evaluations on real-world datasets show that, for each dataset the new approach can produce a rectangle representation that has dominant performance against the state of the art techniques in reducing the storage size of the relations, while the average efficiency of retrieving CDC relations based on the rectangle representation is about the same as the fastest method in the literature.

Restricted Boltzmann machines (RBMs) and their variants are usually trained by contrastive divergence (CD) learning, but the training procedure is an unsupervised learning approach, without any guidances of the background knowledge. To enhance the expression ability of traditional RBMs, in this paper, we propose pairwise constraints (PCs) RBM with Gaussian visible units (pcGRBM) model, in which the learning procedure is guided by PCs and the process of encoding is conducted under these guidances. The PCs are encoded in hidden layer features of pcGRBM. Then, some pairwise hidden features of pcGRBM flock together and another part of them are separated by the guidances. In order to deal with real-valued data, the binary visible units are replaced by linear units with Gaussian noise in the pcGRBM model. In the learning process of pcGRBM, the PCs are iterated transitions between visible and hidden units during CD learning procedure. Then, the proposed model is inferred by approximative gradient descent method and the corresponding learning algorithm is designed. In order to compare the availability of pcGRBM and traditional RBMs with Gaussian visible units, the features of the pcGRBM and RBMs hidden layer are used as input "data" for K -means, spectral clustering (SP) and affinity propagation (AP) algorithms, respectively. We also use tenfold cross-validation strategy to train and test pcGRBM model to obtain more meaningful results with PCs which are derived from incremental sampling procedures. A thorough experimental evaluation is performed with 12 image datasets of Microsoft Research Asia Multimedia. The experimental results show that the clustering performance of K -means, SP, and AP algorithms based on pcGRBM model are significantly better than traditional RBMs. In addition, the pcGRBM model for clustering tasks shows better performance than some semi-supervised clustering algorithms.

In this letter, a low-rank and sparse representation classifier with a spectral consistency constraint (LRSRC-SCC) is proposed. Different from the SRC that represents samples individually, LRSRC-SCC reconstructs samples jointly and is able to capture the local and global structures simultaneously. In this proposed classifier, an adaptive spectral constraint is imposed on both the low-rank and sparse terms so as to better reveal the data structure and enhance its discriminative power. In addition, the alternating direction method is introduced to solve the underlying minimization problem, in which, more importantly, the subobjective function associated with the low-rank term is optimized based on the rank equivalence between a matrix and its Gram matrix, resulting in a closed-form solution. Finally, LRSRC-SCC is extended to LRSRC-SCCE for fully exploiting the spatial information. Experimental results on two hyperspectral data sets demonstrate that the proposed LRSRC-SCC and LRSRC-SCCE methods outperform some state-of-the-art methods.

In order to properly regulate iterated belief revision, Darwiche and Pearl (1997) model belief revision as revising epistemic states by propositions. An epistemic state in their sense consists of a belief set and a set of conditional beliefs. Although the denotation of an epistemic state can be indirectly captured by a total preorder on the set of worlds, it is unclear how to directly capture the structure in terms of the beliefs and conditional beliefs it contains. In this paper, we first provide an axiomatic characterisation for epistemic states by using nine rules about beliefs and conditional beliefs, and then argue that the last two rules are too strong and should be eliminated for characterising the belief state of an agent. We call a structure which satisfies the first seven rules a general epistemic state (GEP). To provide a semantical characterisation of GEPs, we introduce a mathematical structure called belief algebra, which is in essence a certain binary relation defined on the power set of worlds.We then establish a 1-1 correspondence between GEPs and belief algebras, and show that total preorders on worlds are special cases of belief algebras. Furthermore, using the notion of belief algebras, we extend the classical iterated belief revision rules of Darwiche and Pearl to our setting of general epistemic states.

There are different models to characterize AGM belief revision framework. When the background language is finite propositional language, Katsuno and Mendelzon (KM) proposed in 1991 a representation model using total preorder on worlds. This ‘preorder’ model is very influential and has been extended to characterize epistemic state in iterated belief revision. KM showed an approach how to construct the preorder via a belief set and an AGM belif revision operator, however, this approach does not work well when the language is infinite. In this paper, we argue when the language is infinite propositional language, how to construct a preorder on world to model AGM belief revision framework, and then we generalize the representation theorem of KM over an infinite language.