As an emerging weakly supervised learning framework, partial label learning aims to induce a multi-class classifier from ambiguous supervision information where each training example is associated with a set of candidate labels, among which only one is the true label. Traditional feature selection methods, either for single label and multiple label problems, are not applicable to partial label learning as the ambiguous information contained in the label space obfuscates the importance of features and misleads the selection process. This makes the selection of a proper feature subset from partial label examples particularly challenging, and therefore has rarely been investigated. In this paper, we propose a novel feature selection algorithm for partial label learning, named PLFS, which considers not only the relationships between features and labels, but also exploits the relationships between instances to select the most informative and important features to enhance the performance of partial label learning. PLFS constructs an adaptive weighted graph to exploit the similarity information among instances, differentiate the label space and weight the feature space, which leads to the selection of a proper feature subset. Extensive experiments over a broad range of benchmark data sets clearly validate the effectiveness of our proposed feature selection approach.

With the personal partial rankings from agents over a subset of alternatives, the goal of preference completion is to infer the agent’s personalized preference over all alternatives including those the agent has not yet handled from uncertain preference of third parties. By combining the partial rankings of the target agent and the partial rankings from third parties to settle some disagreement with three-way preference completion, which includes a general strategy, an optimal strategy, and a pessimistic strategy, it forms the weighted preference graph. Technically, to settle the disagreement and obtain the completed preference of the target agent in the weighted preference graph, maximum likelihood estimation (MLE) under Mallows is proposed and validated theoretically by removing edges with the minimum weight in the weighted preference graph. However, it is not easy to locate the edges with the minimum weight efficiently in a big graph. Hence, an optimal MLE algorithm and three greedy MLE algorithms are proposed to process the MLE. Furthermore, these proposed algorithms are experimentally validated and compared with each other by both the synthetic dataset and the Flixter dataset.

Graph pattern matching (GPM) is widely used in social network analysis, such as expert finding, social group query, and social position detection. Technically, GPM is to find matched subgraphs that meet the requirements of pattern graphs in big social networks. In the application of expert community location, the nodes in the pattern graph and data graph represent expert entities, and the edges represent previous cooperations between them. However, the existing GPM methods focus on shortening the matching time and without considering the preference of the decision maker (DM), which makes it difficult for the DM to find ideal teams from numerous matches to complete the assigned task. In this article, as for the process of graph pattern matching and rematching, with a preferred expert set, i.e., the DM hopes that one or more experts in this set will appear in matched subgraphs, we propose a Dual Simulation-based Edge Sequencing-oriented Semi-Supervised GPM method (DsEs-ssGPM). In addition, considering a preferred expert set and a dispreferred expert set together, the DM hopes that experts in the dispreferred expert set will not appear in final matches, so we have the DsEs-ssGPM+ method. Technically, these DsEs-ssGPM methods conduct the matching process from the preferred expert set during dual simulation-based edge sequencing, and based on the edge sequence, these edges are searched recursively. Especially, as for the rematching process, when the preferred and/or the dispreferred expert sets change continuously, to process the GPM again is unnecessary and it is possible to revise the previous matched results partially with DsEs-ssGPM methods. Experiments on four large datasets demonstrate the effectiveness, efficiency and stability of our proposed DsEs-ssGPM methods, and the necessity of introducing an edge sequencing mechanism.

Truth inference can help solve some difficult problems of data integration in crowdsourcing. Crowdsourced workers are not experts and their labeling ability varies greatly; therefore, in practical applications, it is difficult to determine whether the labels collected from a crowdsourcing platform are correct. This article proposes a novel algorithm called truth inference based on label confidence clustering (TILCC) to improve the quality of integrated labels for the single-choice classification problem in crowdsourcing labeling tasks. We obtain the label confidence via worker reliability, which is calculated from multiple noise labels using a truth discovery method, and then we generate the clustering features and use the K-means algorithm to cluster all the tasks into K different clusters. Each cluster corresponds to a specific class, and the tasks in the cluster are assigned a label. Compared with the performances of six state-of-the-art methods, MV, ZenCrowd, PM, CATD, GLAD, and GTIC, on 12 randomly selected real-world datasets, the performance of our algorithm showed many advantages: no need to set complex parameters, faster running speed, and significantly higher accuracy.

Traditional social group analysis mostly uses interaction models, event models, or other social network analysis methods to identify and distinguish groups. This type of method can divide social participants into different groups based on their geographic location, social relationships, and/or related events. However, in some applications, it is necessary to make more specific restrictions on the members and the interactions between members of the group. Generally, Graph Pattern Matching (GPM) technique is used to solve this problem. However, the existing GPM methods rarely consider the rich contextual information of nodes and edges to measure the credibility between members. In this article, first, a social group query problem that needs to consider the trust between members of the group is proposed. Then, to solve this problem, a multi-fuzzy-constrained strong simulation matching model is proposed based on multi-constrained simulation, and a Strong Simulation GPM algorithm (NTSS) based on the exploration of pattern Node Topological ordered sequence is proposed. Aiming at the inefficiency of the NTSS algorithm when pattern graph with multiple nodes with zero in-degree and the problem of repeated calculation of matching edges shared by multiple matching subgraphs, two optimization strategies are proposed. Finally, we conduct verification experiments on the effectiveness and efficiency of the NTSS algorithm and the algorithms with the optimization strategies on four social network datasets in real applications. Experimental results show that the NTSS algorithm is significantly better than the existing multi-constrained GPM algorithm, and the NTSS_Inv_EdgC algorithm, which combines two optimization strategies, greatly improves the efficiency of the NTSS algorithm.

Graph edge partitioning, which is essential for the efficiency of distributed graph computation systems, divides a graph into several balanced partitions within a given size to minimize the number of vertices to be cut. Existing graph partitioning models can be classified into two categories: offline and streaming graph partitioning models. The former requires global graph information during the partitioning, which is expensive in terms of time and memory for large-scale graphs. The latter creates partitions based solely on the received graph information. However, the streaming model may result in a lower partitioning quality compared with the offline model. Therefore, this study introduces a Local Graph Edge Partitioning model, which considers only the local information (i.e., a portion of a graph instead of the entire graph) during the partitioning. Considering only the local graph information is meaningful because acquiring complete information for large-scale graphs is expensive. Based on the Local Graph Edge Partitioning model, two local graph edge partitioning algorithms—Two-stage Local Partitioning and Adaptive Local Partitioning—are given. Experimental results obtained on 14 real-world graphs demonstrate that the proposed algorithms outperform rival algorithms in most tested cases. Furthermore, the proposed algorithms are proven to significantly improve the efficiency of the real graph computation system GraphX.

Deep learning seeks to achieve excellent performance for representation learning in image datasets. However, supervised deep learning models such as convolutional neural networks require a large number of labeled image data, which is intractable in applications, while unsupervised deep learning models like stacked denoising auto-encoder cannot employ label information. Meanwhile, the redundancy of image data incurs performance degradation on representation learning for aforementioned models. To address these problems, we propose a semi-supervised deep learning framework called stacked convolutional sparse auto-encoder, which can learn robust and sparse representations from image data with fewer labeled data records. More specifically, the framework is constructed by stacking layers. In each layer, higher layer feature representations are generated by features of lower layers in a convolutional way with kernels learned by a sparse auto-encoder. Meanwhile, to solve the data redundance problem, the algorithm of Reconstruction Independent Component Analysis is designed to train on patches for sphering the input data. The label information is encoded using a Softmax Regression model for semi-supervised learning. With this framework, higher level representations are learned by layers mapping from image data. It can boost the performance of the base subsequent classifiers such as support vector machines. Extensive experiments demonstrate the superior classification performance of our framework compared to several state-of-the-art representation learning methods.

We propose a generalized optimization framework for detecting anomalous patterns (subgraphs that are interesting or unexpected) in interdependent networks, such as multi-layer networks, temporal networks, networks of networks, and many others. We frame the problem as a non-convex optimization that has a general nonlinear score function and a set of block-structured and non-convex constraints. We develop an effective, efficient, and parallelizable projection-based algorithm, namely Graph Block-structured Gradient Projection (GBGP), to solve the problem. It is proved that our algorithm 1) runs in nearly-linear time on the network size, and 2) enjoys a theoretical approximation guarantee. Moreover, we demonstrate how our framework can be applied to two very practical applications, and we conduct comprehensive experiments to show the effectiveness and efficiency of our proposed algorithm.

Along with the fast development of network applications, network research has attracted more and more attention, where one of the most important research directions is networked multi-label classification. Based on it, unknown labels of nodes can be inferred by known labels of nodes in the neighborhood. As both the scale and complexity of networks are increasing, the problems of previously neglected system overhead are turning more and more seriously. In this article, a novel multi-objective optimization-based networked multi-label seed node selection algorithm (named as MOSS) is proposed to improve both the prediction accuracy for unknown labels of nodes from labels of seed nodes during classification and the system overhead for mining the labels of seed nodes with third parties before classification. Compared with other algorithms on several real networked data sets, MOSS algorithm not only greatly reduces the system overhead before classification but also improves the prediction accuracy during classification.

Big graph data is different from traditional data and they usually contain complex relationships and multiple attributes. With the help of graph pattern matching, a pattern graph can be designed, satisfying special personal requirements and locate the subgraphs which match the required pattern. Then, how to locate a graph pattern with better attribute values in the big graph effectively and efficiently becomes a key problem to analyze and deal with big graph data, especially for a specific domain. This article introduces fuzziness into graph pattern matching. Then, a genetic algorithm, specifically an NSGA-II algorithm, and a particle swarm optimization algorithm are adopted for multi-fuzzy-objective optimization. Experimental results show that the proposed approaches outperform the existing approaches effectively.

The contents generated from different data sources are usually non-uniform, such as long texts produced by news websites and short texts produced by social media. Uncovering topics over large-scale non-uniform texts becomes an important task for analyzing network data. However, the existing methods may fail to recognize the difference between long texts and short texts. To address this problem, we propose a novel topic modeling method for non-uniform text topic modeling referred to as self-adaptive sliding window based topic model (SSWTM). Specifically, in all kinds of texts, relevant words have a closer distance to each other than irrelevant words. Based on this assumption, SSWTM extracts relevant words by using a selfadaptive sliding window and models on the whole corpus. The self-adaptive sliding window can filter noisy information and change the size of a window according to different text contents. Experimental results on short texts from Twitter and long texts from Chinese news articles demonstrate that our method can discover more coherent topics for non-uniform texts compared with state-of-the-art methods.

Short text stream classification is a challengingand significant task due to the characteristics of short length, weak signal, high velocity and especially topic drifting in short text stream. However, this challenge has received little attention from the research community. Motivated by this, we propose a new feature extension approach for short text stream classification using a large scale, general purpose semantic network obtained from a web corpus. Our approach is built on an incremental ensemble classification model. First, in terms of the open semantic network, we introduce more semantic contexts in short texts to make up of the data sparsity. Meanwhile, we disambiguate terms by their semantics to reduce the noise impact. Second, to effectively track hidden topic drifts, we propose a concept cluster based topic drifting detection method. Finally, extensive experiments demonstratethat our approach can detect topic drifts effectively compared to several well-known concept drifting detection methods in data streams. Meanwhile, our approach can perform best in the classification of text data streams compared to several stateof-the-art short text classification approaches.

The research on community structure is a key to analyze the network functionality and topology, and thus it is significant to detect and analysis the community structure. During the abstract process from an actual system to a network, especially for a large-scale network, it is inevitable to have mistaken connections between nodes or have connection missing. In addition, in real applications, from time to time we can obtain prior information in the form of pairwise constraints between nodes besides topology information, although they may be inaccurate or conflicted. These noises in the network-related information will dramatically reduce the accuracy of community detection. Hence, in this paper, we introduce a dissimilarity index to determine the trustworthiness of pairwise constraints and settle the conflict of pairwise constraints. Then, focusing on the community detection with false connections or conflicted connections, we propose a pairwise constrained structure-enhanced extremal optimization-based semi-supervised algorithm (PCSEO-SS algorithm). Compared with existing semi-supervised community detection approaches, the experimental results executed on real networks and synthetic networks, show that PCSEO-SS can solve the problem of false connections or conflicted connections to some extent and detect the community structure more precisely.