Search

Subgraph matching, as a challenging problem in the graph area, has a wide range of applications from social networks to computational biology. It refers to finding the occurrences of a query graph in a given large graph. Subgraph matching is considered an NP-complete problem in the literature. In order to reduce the computational complexity of subgraph matching, pruning the search space with heuristics, e.g., topological features, have been studied broadly. In this paper, we propose a novel pruning strategy in subgraph matching to reduce the size of search space, named Eigen Decomposition Pruning. EDP uses local spectral features to prune the search space instead of directly using topological features. Firstly, it generates a Local Laplacian Matrix (LLM) for each candidate solution. Then, it prunes the false positive candidates from the search space using the spectral features of these LLMs. An LLM is defined to capture the features in the localities of a graph and imposes a low computation overhead. Additionally, EDP recognizes more false positive candidates than previous methods due to more informative spectral features of LLM, which results in a noticeable decrease in the overall time of subgraph matching. To assess the performance of our algorithm, it is applied to both real and synthetic datasets and is compared against four well-known methods in this field. The theoretical analysis and experimental results confirm the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

• Paper proposes Deep and Wide Nonnegative Matrix Factorization with embedded regularization (DWNMF) as an end-to-end model. • It prevents overfitting via embedded regularization, and decreases vanishing gradient via training layers independently. • Model size can grow incrementally to achieve the performance. It saves memory since it only holds each layer's parameters. • Model size can grow incrementally to achieve the performance. It saves memory since it only holds each layer's parameters. • Experimental results showed that DWNMF performs better than end-to-end feature learning models in complexity and CPU time. End-to-end learning is an advanced framework in deep learning. It combines feature extraction, followed by pattern recognition (classification, clustering, etc.) in a unified learning structure. However, these deep networks face several challenges such as overfitting, vanishing gradient, computational complexity, information loss in layers, and weak robustness to noisy data/features. To address these challenges, this paper presents Deep and Wide Nonnegative Matrix Factorization (DWNMF) with embedded regularization for the feature extraction stage of the end-to-end models. DWNMF aims to identify more robust features while preventing overfitting via embedding regularization. For this purpose, DWNMF integrates input data with its noisy versions as diverse augmented channels. Then, the features in all channels are extracted in parallel using distinct network branches. The parameters of this model learn the intrinsic hierarchical features in the channels of complex data objects. Finally, the extracted features in different channels are aggregated in a single feature space to perform the classification task. To embed regularization in the DWNMF model, some NMF neurons in the layers are substituted by random neurons to increase the stability and robustness of the extracted features. Experimental results confirm that the DWNMF model extracts more robust features, prevents overfitting, and achieves better classification accuracy compared to state-of-the-art methods. [ABSTRACT FROM AUTHOR]

Ensemble learning is an effective technique in classifying high-dimensional data such as bioinformatics sequences since it combines some learning models to improve the overall prediction accuracy. The key point in success of an ensemble algorithm is to build a set of diverse classifiers. In this regard, a novel density-based lazy stacking algorithm, called DBLS, is proposed in this paper. It takes the advantages of both lazy learning, in finding local optimal solutions, and the stacking method, in achieving classifier diversity, to obtain better performance while keeping the complexity intact. DBLS uses a stacking framework with lazy local learners based on density for building an ensemble of classifiers to predict the structural classes of proteins. To evaluate the performance of DBLS, it is compared against four rival classification methods. For this purpose, some real-world UCI datasets beside to three benchmark protein datasets are used in the experiments. The experimental results confirmed that DBLS significantly (with 95% confidence) outperforms other methods in terms of classification accuracy; over 3% advantage in absolute accuracy. [ABSTRACT FROM AUTHOR]