Data summarization aims at utilizing a small-scale summary to represent massive datasets as a whole, which is useful for visualization and information sipped generation. However, most existing studies of hierarchical summarization only work onone single treeby selecting$k$representative nodes, which neglects an important problem of comparative summarization on two trees. In this paper, given two trees with the same topology structure and different node weights, we aim at finding$k$representative nodes, where$k_{1}$nodes summarize the common relationship between them and$k_{2}$nodes highlight significantly different subtrees meanwhile satisfying$k_{1}+k_{2}=k$. To optimize summarization results, we introduce a scaling coefficient for balancing the summary view between two subtrees in terms of similarity and difference. Additionally, we propose a novel definition based on the Hellinger distance to quantify the node distribution difference between two subtrees. We present a greedy algorithm SVDT to find high-quality results with approximation guaranteed in an efficient way. Furthermore, we explore an extension of our comparative summarization to handle two trees with different structures. Extensive experiments demonstrate the effectiveness and efficiency of our SVDT algorithm against existing summarization competitors.

Community detection aims at partitioning a network into several densely connected subgraphs. Recently, nonnegative matrix factorization (NMF) has been widely adopted in many successful community detection applications. However, most existing NMF-based community detection algorithms neglect the multihop network topology and the extreme sparsity of adjacency matrices. To resolve them, we propose a novel conception of adjacency tensor, which extends adjacency matrix to multihop cases. Then, we develop a novel tensor Tucker decomposition-based community detection method-autoencoder-like nonnegative tensor decomposition (ANTD), leveraging the constructed adjacency tensor. Distinct from simply applying tensor decomposition on the constructed adjacency tensor, which only works as a decoder, ANTD also introduces an encoder component to constitute an autoencoder-like architecture, which can further enhance the quality of the detected communities. We also develop an efficient alternative updating algorithm with convergence guarantee to optimize ANTD, and theoretically analyze the algorithm complexity. Moreover, we also study a graph regularized variant of ANTD. Extensive experiments on real-world benchmark networks by comparing 27 state-of-the-art methods, validate the effectiveness, efficiency, and robustness of our proposed methods.

Community detection aims at finding all densely connected communities in a network, which serves as a fundamental graph tool for many applications, such as identification of protein functional modules, image segmentation, social circle discovery, to name a few. Recently, nonnegative matrix factorization (NMF)-based community detection methods have attracted significant attention. However, most existing methods neglect the multihop connectivity patterns in a network, which turn out to be practically useful for community detection. In this article, we first propose a novel community detection method, namely multihop NMF (MHNMF for brevity), which takes into account the multihop connectivity patterns in a network. Subsequently, we derive an efficient algorithm to optimize MHNMF and theoretically analyze its computational complexity and convergence. Experimental results on 12 real-world benchmark networks demonstrate that MHNMF outperforms 12 state-of-the-art community detection methods.

Abstract The process of team composition in multiplayer sports such as football has been a main area of interest within the field of the science of teamwork, which is important for improving competition results and game experience. Recent algorithms for the football team composition problem take into account the skill proficiency of players but not the interactions between players that contribute to winning the championship. To automate the composition of a cohesive team, we consider the internal collaborations among football players. Specifically, we propose a Team Composition based on the Football Players’ Attributed Collaboration Network (TC-FPACN) model, aiming to identify a cohesive football team by maximizing football players’ capabilities and their collaborations via three network metrics, namely, network ability, network density and network heterogeneity&homogeneity. Solving the optimization problem is NP-hard; we develop an approximation method based on greedy algorithms and then improve the method through pruning strategies given a budget limit. We conduct experiments on two popular football simulation platforms. The experimental results show that our proposed approach can form effective teams that dominate others in the majority of simulated competitions.

Unsupervised feature selection has attracted remarkable attention recently. With the development of data acquisition technology, multi-dimensional tensor data has been appeared in enormous real-world applications. However, most existing unsupervised feature selection methods are non-tensor-based which results the vectorization of tensor data as a preprocessing step. This seemingly ordinary operation has led to an unnecessary loss of the multi-dimensional structural information and eventually restricted the quality of the selected features. To overcome the limitation, in this paper, we propose a novel unsupervised feature selection model: Nonnegative tensor CP (CANDECOMP/PARAFAC) decomposition based unsupervised feature selection, CPUFS for short. In specific, we devise new tensor-oriented linear classifier and feature selection matrix for CPUFS. In addition, CPUFS simultaneously conducts graph regularized nonnegative CP decomposition and newly-designed tensor-oriented pseudo label regression and feature selection to fully preserve the multi-dimensional data structure. To solve the CPUFS model, we propose an efficient iterative optimization algorithm with theoretically guaranteed convergence, whose computational complexity scales linearly in the number of features. A variation of the CPUFS model by incorporating nonnegativity into the linear classifier, namely CPUFSnn, is also proposed and studied. Experimental results on ten real-world benchmark datasets demonstrate the effectiveness of both CPUFS and CPUFSnn over the state-of-the-arts.

Feature extraction plays an indispensable role in image and video technology. However, it is difficult for traditional matrix based feature extraction methods to handle massive multi-dimensional data. This, alongside with the ubiquitous uncertainty (noise) in real-world data, resulted in many robust tensor based feature extraction models. All these existing models did not consider the worst-case model performance (i.e., the largest fitting error among all samples), which is critically important from a robust optimization perspective. In this paper, we propose a novel robust feature extraction model via$\ell _{\infty }$-norm based nonnegative Tucker decomposition. The model is to minimize the maximum sample fitting error so as to overcome the influence of data uncertainty. Although the new model is nonconvex and nonsmooth, we design an effective iterative optimization algorithm with theoretical guarantee on its convergence. The performance of the new model on five real-world benchmark object classification and face recognition datasets under various corruption scenarios are evaluated, and the experimental results show the excellence of the new model by comparing to many existing models.

Community detection is an important topic in network analysis, and recently many community detection methods have been developed on top of the Nonnegative Matrix Factorization (NMF) technique. Most NMF-based community detection methods only utilize the first-order proximity information in the adjacency matrix, which has some limitations. Besides, many NMF-based community detection methods involve sparse regularizations to promote clearer community memberships. However, in most of these regularizations, different nodes are treated equally, which seems unreasonable. To dismiss the above limitations, this article proposes a community detection method based on node centrality under the framework of NMF. Specifically, we design a new similarity measure which considers the proximity of higher-order neighbors to form a more informative graph regularization mechanism, so as to better refine the detected communities. Besides, we introduce the node centrality and Gini impurity to measure the importance of nodes and sparseness of the community memberships, respectively. Then, we propose a novel sparse regularization mechanism which forces nodes with higher node centrality to have smaller Gini impurity. Extensive experimental results on a variety of real-world networks show the superior performance of the proposed method over thirteen state-of-the-art methods.

Recommender system provides personalized suggestions based on users' interests and social connections. However, most existing social recommendation models utilize social relationships in a direct manner, i.e., they only consider the user-user connections, neglecting the clustering nature of social networks. As social information recursively spreads in the social network, the community structure, which contains richer information in contrast to pure user-user relationships, would emerge. To dismiss these limitations, in this paper, we propose a unified recommendation framework named Simultaneous Community detection and Singular Value Decomposition (SCSVD), which utilizes the underlying community structure to regularize user latent preferences. We propose a well-designed iterative optimization algorithm to tackle social recommendation efficiently. In addition, we theoretically analyze the proposed algorithm in terms of convergence, time complexity, and also the unified process of community detection and user embedding learning. Extensive experiments are conducted on three benchmark real-world datasets of product reviews, demonstrating the effectiveness, robustness, and flexibility of SCSVD in both rating prediction and top-N recommendation tasks, compared to fifteen state-of-the-art approaches.

Social recommendation aims at improving recommendation performance by incorporating social information. Most existing social recommender systems only utilize the one-hop interpersonal social information, neglecting the community structure emerged in social networks, which may contain additional conducive information. In this paper, we propose a unified Simultaneous Community detection and Singular Value Decomposition (SCSVD) framework for community-aware social recommendation. An efficient optimization algorithm is also derived to optimize SCSVD, with an analysis of convergence and computational complexity. Comprehensive experimental results on three real-world benchmark datasets demonstrate the effectiveness of SCSVD, over both traditional matrix factorization based recommendation models and advanced neural network based recommendation models.

Due to the "curse of dimensionality" issue, how to discard redundant features and select informative features in high-dimensional data has become a critical problem, hence there are many research studies dedicated to solving this problem. Unsupervised feature selection technique, which does not require any prior category information to conduct with, has gained a prominent place in preprocessing high-dimensional data among all feature selection techniques, and it has been applied to many neural networks and learning systems related applications, e.g., pattern classification. In this article, we propose an efficient method for unsupervised feature selection via orthogonal basis clustering and reliable local structure preserving, which is referred to as OCLSP briefly. Our OCLSP method consists of an orthogonal basis clustering together with an adaptive graph regularization, which realizes the functionality of simultaneously achieving excellent cluster separation and preserving the local information of data. Besides, we exploit an efficient alternative optimization algorithm to solve the challenging optimization problem of our proposed OCLSP method, and we perform a theoretical analysis of its computational complexity and convergence. Eventually, we conduct comprehensive experiments on nine real-world datasets to test the validity of our proposed OCLSP method, and the experimental results demonstrate that our proposed OCLSP method outperforms many state-of-the-art unsupervised feature selection methods in terms of clustering accuracy and normalized mutual information, which indicates that our proposed OCLSP method has a strong ability in identifying more important features.