Effectively and efficiently mining valuable clustering patterns is a challenging problem when handling large-scale data from diverse sources. Existing approaches adopt anchor graph learning or binary representation embedding to reduce computational complexity. Normally, anchor graph learning can not directly obtain the clustering assignment except adopt the post-processing stage, such as graph cut or k-means clustering. The binary representation embedding neglects the structure information in Hamming space. In order to overcome these limitations, this paper proposes a novel, effective, and efficient angular reconstructive discrete embedding method with fusion similarity for a multi-view clustering (AFMC) that can jointly learn the global and local structure preserving binary representation and clustering assignment. Specifically, we propose to use angular reconstructive error minimization to maintain the global similarity correlation of binary representations of heterogeneous features in a common Hamming space. Moreover, we design a multi-view discrete ridge regression with fusion similarity term to handle the out-of-sample problem and preserve the local manifold structure. In addition, we propose an efficient optimization algorithm with linear computational complexity to solve the non-convex and non-smooth objective function. The experimental results demonstrate that AFMC outperforms several state-of-the-art large-scale multi-view clustering methods.

Most existing large-scale multiview clustering algorithms attempt to capture data distribution in multiple views by selecting view-wise anchor representations beforehand with$k$-means, or by direct matrix factorization on the original observations. Despite impressive performance, few of them have paid attention to the semantic correlations between anchor bases and cluster centroids, or even the underlying relations between clusters and data samples. In view of this, we propose aConceptFactorization basedMultiviewClustering for Large-scale Data (CFMC) method with nearly linear complexity. The anchor bases learning, coefficient expression with clear semantic cues and partitioning are integrated together in this unified model. Meanwhile, explicit connections among multiview data, anchor bases and clusters are modeled via coefficient representations with semantic meanings. A four-step alternate minimizing algorithm is designed to handle the optimization problem, which is proved to have linear time complexityw.r.t.the sample size. Extensive experiments conducted on several challenging large-scale datasets confirm the superiority of the method compared with the state-of-the-art methods.

Graph contrastive learning (GCL) has become the de-facto approach to conducting self-supervised learning on graphs for its superior performance. However, non-semantic graph augmentation methods prevent it from achieving better performance, and it suffers from vulnerability to graph attacks. To deal with these problems, we propose AEGCL to leverage graph AutoEncoder in Graph Contrastive Learning which directly targets graph property reconstruction to boost GCL effectiveness and robustness. Specifically, AEGCL has two distinctive characteristics, (1) a novel adaptive augmentation strategy based onmotifcentrality is proposed, which leverages semantic significant higher-order graph property; (2) the original attributed graph is decoupled into feature graph and topology graph to extract their dedicated information, and a simpleAttnFuseis proposed to combine the two augmented graphs and the two decoupled graphs. Graph autoencoder can thus be applied to the topology domain and raw attribute domain. Empirically, extensive experiments on benchmark graph datasets show that AEGCL outperforms existing baseline methods in terms of classification accuracy and robustness.

Next-basket recommendation methods focus on the inference of the next basket by considering the corresponding basket sequence. Although many methods have been developed for the task, they usually suffer from data sparsity. The number of interactions between entities is relatively small compared to their huge bases, so it is crucial to mine as much hidden information as possible from the limited historical interactions for prediction. However, the existing methods mainly just treat the next-basket recommendation task as a single-view sequential prediction problem, which leads to the inadequate mining of the information hidden in multiple views, and the mining of other patterns in the historical interactions is neglected, thus making it difficult to learn high-quality representations and limiting the recommendation effect. To alleviate the above issues, we propose a novel method named HapCL for next-basket recommendation, which mines information from multiple views and patterns with the help of polar contrastive learning. A hierarchical module is designed to mine multiple patterns of historical interactions from different views at two levels. In order to mine self-supervised signals, we design a polar contrastive learning module with a novel graph-based augmentation approach. Experiments on three real-world datasets validate the effectiveness of HapCL.

With the rapid growth of online platforms and the abundance of available information, personalized recommender systems have become essential for assisting users in discovering relevant and interesting content. Among the various methods, knowledge-aware recommendation model has achieved notable success by leveraging the rich semantic information encoded in knowledge graphs. However, it overlooks the fact that users’ historical click sequences can better reflect their preferences within a period of time, thus imposing certain limitations on the recommendation performance. On the other hand, the application of pre-trained language models in recommender systems has demonstrated increasingly significant potential, as they can capture sequential patterns and dependencies within users’ historical click sequences and effectively capture contextual information in user-item interactions. To this end, we propose a hybrid recommendation model that leverages Pre-training in the collaborative Knowledge graph Attention neTwork (PKAT), to extract both the high-order connectivity information in collaborative knowledge graphs and the contextual information in users’ historical click sequences captured by Bidirectional Encoder Representations from Transformers (BERT). The collaborative knowledge graph attention network enables the model to effectively capture the intricate relationships between users, items, and knowledge entities, thus enhancing the representation learning process. Furthermore, what sets PKAT apart from other state-of-the-art knowledge-aware recommendation methods is the incorporation of the BERT language model. This integration allows PKAT to capture the contextual sequence information of user behavior, enabling it to generate more accurate and personalized recommendations. Extensive experiments are conducted on multiple benchmark datasets. And the results demonstrate that our PKAT model outperforms several state-of-the-art baselines.

Class imbalance is the phenomenon that some classes have much fewer instances than others, which is ubiquitous in real-world graph-structured scenarios. Recent studies find that off-the-shelf Graph Neural Networks (GNNs) would under-represent minor class samples. We investigate this phenomenon and discover that the subspaces of minor classes being squeezed by those of the major ones in the latent space is the main cause of this failure. We are naturally inspired to enlarge the decision boundaries of minor classes and propose a general framework GraphSHA by Synthesizing HArder minor samples. Furthermore, to avoid the enlarged minor boundary violating the subspaces of neighbor classes, we also propose a module called SemiMixup to transmit enlarged boundary information to the interior of the minor classes while blocking information propagation from minor classes to neighbor classes. Empirically, GraphSHA shows its effectiveness in enlarging the decision boundaries of minor classes, as it outperforms various baseline methods in class-imbalanced node classification with different GNN backbone encoders over seven public benchmark datasets. Code is avilable at https://github.com/wenzhilics/GraphSHA.

Contrastive learning (CL) has become the de-facto learning paradigm in self-supervised learning on graphs, which generally follows the "augmenting-contrasting'' learning scheme. However, we observe that unlike CL in computer vision domain, CL in graph domain performs decently even without augmentation. We conduct a systematic analysis of this phenomenon and argue that homophily, i.e., the principle that "like attracts like'', plays a key role in the success of graph CL. Inspired to leverage this property explicitly, we propose HomoGCL, a model-agnostic framework to expand the positive set using neighbor nodes with neighbor-specific significances. Theoretically, HomoGCL introduces a stricter lower bound of the mutual information between raw node features and node embeddings in augmented views. Furthermore, HomoGCL can be combined with existing graph CL models in a plug-and-play way with light extra computational overhead. Extensive experiments demonstrate that HomoGCL yields multiple state-of-the-art results across six public datasets and consistently brings notable performance improvements when applied to various graph CL methods. Code is avilable at https://github.com/wenzhilics/HomoGCL.

Nowadays, it is more and more convenient for people to participate in group activities. Therefore, providing some recommendations to groups of individuals is indispensable. Group recommendation is the task of suggesting items or events for a group of users in social networks or online communities. In this work, we study group recommendation in a particular scenario, namely occasional group recommendation, which has few or no historical directly interacted items. Existing group recommendation methods mostly adopt attention-based preference aggregation strategies to capture group preferences. However, these models either ignore the complex high-order interactions between groups, users and items or greatly reduce the efficiency by introducing complex data structures. Moreover, occasional group recommendation suffers from the problem of data sparsity due to the lack of historical group-item interactions. In this work, we focus on addressing the aforementioned challenges and propose a novel group recommendation model called Self-Supervised Group Graph Collaborative Filtering (SGGCF). The goal of the model is capturing the high-order interactions between users, items and groups and alleviating the data sparsity issue in an efficient way. First, we explicitly model the complex relationships as a unified user-centered heterogeneous graph and devise a base group recommendation model. Second, we explore self-supervised learning on the graph with two kinds of contrastive learning module to capture the implicit relations between groups and items. At last, we treat the proposed contrastive learning loss as supplementary and apply a multi-task strategy to jointly train the BPR loss and the proposed contrastive learning loss. We conduct extensive experiments on three real-world datasets, and the experimental results demonstrate the superiority of our proposed model in comparison to the state-of-the-art baselines.

Graph-oriented multi-view clustering methods have achieved impressive performances by employing relationships and complex structures hidden in multi-view data. However, most of them still suffer from the following two common problems. (1) They target at studying a common representation or pairwise correlations between views, neglecting the comprehensiveness and deeper higher-order correlations among multiple views. (2) The prior knowledge of view-specific representation can not be taken into account to obtain the consensus indicator graph in a unified graph construction and clustering framework. To deal with these problems, we propose a novel Low-rank Tensor Based Proximity Learning (LTBPL) approach for multi-view clustering, where multiple low-rank probability affinity matrices and consensus indicator graph reflecting the final performances are jointly studied in a unified framework. Specifically, multiple affinity representations are stacked in a low-rank constrained tensor to recover their comprehensiveness and higher-order correlations. Meanwhile, view-specific representation carrying different adaptive confidences is jointly linked with the consensus indicator graph. Extensive experiments on nine real-world datasets indicate the superiority of LTBPL compared with the state-of-the-art methods.

Despite significant progress, there remain three limitations to the previous multi-view clustering algorithms. First, they often suffer from high computational complexity, restricting their feasibility for large-scale datasets. Second, they typically fuse multi-view information via one-stage fusion, neglecting the possibilities in multi-stage fusions. Third, dataset-specific hyperparameter-tuning is frequently required, further undermining their practicability. In light of this, we propose afastmulti-viewclustering viaensembles (FastMICE) approach. Particularly, the concept of random view groups is presented to capture the versatile view-wise relationships, through which the hybrid early-late fusion strategy is designed to enable efficient multi-stage fusions. Withmultipleviews extended tomanyview groups, three levels of diversity (w.r.t. features, anchors, and neighbors, respectively) are jointly leveraged for constructing the view-sharing bipartite graphs in the early-stage fusion. Then, a set of diversified base clusterings for different view groups are obtained via fast graph partitioning, which are further formulated into a unified bipartite graph for final clustering in the late-stage fusion. Notably, FastMICE has almost linear time and space complexity, and is free of dataset-specific tuning. Experiments on 22 multi-view datasets demonstrate its advantages in scalability (for extremely large datasets), superiority (in clustering performance), and simplicity (to be applied) over the state-of-the-art. Code available:https://github.com/huangdonghere/FastMICE.

Multi-view subspace clustering targets at clustering data lying in a union of low-dimensional subspaces. Generally, an n X n affinity graph is constructed, on which spectral clustering is then performed to achieve the final clustering. Both graph construction and graph partitioning of spectral clustering suffer from quadratic or even cubic time and space complexity, leading to difficulty in clustering large-scale datasets. Some efforts have recently been made to capture data distribution in multiple views by selecting key anchor bases beforehand with k-means or uniform sampling strategy. Nevertheless, few of them pay attention to the algebraic property of the anchors. How to learn a set of high-quality orthogonal bases in a unified framework, while maintaining its scalability for very large datasets, remains a big challenge. In view of this, we propose an Efficient Orthogonal Multi-view Subspace Clustering (OMSC) model with almost linear complexity. Specifically, the anchor learning, graph construction and partition are jointly modeled in a unified framework. With the mutual enhancement of each other, a more discriminative and flexible anchor representation and cluster indicator can be jointly obtained. An alternate minimizing strategy is developed to deal with the optimization problem, which is proved to have linear time complexity w.r.t. the sample number. Extensive experiments have been conducted to confirm the superiority of the proposed OMSC method. The source codes and data are available at https://github.com/ManshengChen/Code-for-OMSC-master.

Abstract Multi-view clustering (MVC) has attracted more and more attention in the recent few years by making full use of complementary and consensus information between multiple views to cluster objects into different partitions. Although there have been two existing works for MVC survey, neither of them jointly takes the recent popular deep learning-based methods into consideration. Therefore, in this paper, we conduct a comprehensive survey of MVC from the perspective of representation learning. It covers a quantity of multi-view clustering methods including the deep learning-based models, providing a novel taxonomy of the MVC algorithms. Furthermore, the representation learning-based MVC methods can be mainly divided into two categories, i.e., shallow representation learning-based MVC and deep representation learning-based MVC, where the deep learning-based models are capable of handling more complex data structure as well as showing better expression. In the shallow category, according to the means of representation learning, we further split it into two groups, i.e., multi-view graph clustering and multi-view subspace clustering. To be more comprehensive, basic research materials of MVC are provided for readers, containing introductions of the commonly used multi-view datasets with the download link and the open source code library. In the end, some open problems are pointed out for further investigation and development.

Most proximity-based multi-view clustering methods are sensitive to the initial proximity matrix, where the clustering performance is quite unstable when using different initial proximity matrixes. This problem is defined as the initial value sensitivity problem. Since clustering is an unsupervised learning task, it is unrealistic to tune the initial proximity matrix. Thus, how to overcome the initial value sensitivity problem is a significant but unsolved issue in the proximity-based multi-view clustering. To this end, this paper proposes a novel multi-view proximity learning method, named multi-view consensus proximity learning (MCPL). On the one hand, by integrating the information of all views in a self-weighted manner and giving a rank constraint on the Laplacian matrix, the MCPL method learns the consensus proximity matrix to directly reflect the clustering result. On the other hand, different from most multi-view proximity learning methods, in the proposed MCPL method, the data representatives rather than the original data objects are adopted to learn the consensus proximity matrix. The data representatives will be updated in the process of the proximity learning so as to weaken the impact of the initial value on the clustering performance. Extensive experiments are conducted to demonstrate the effectiveness of the proposed method.

Recently, some attempts have been made in introducing deep neural networks (DNNs) to recommender systems for generating more accurate prediction due to the nonlinear representation learning capability of DNNs. However, they inevitably result in high computational and storage costs. Worse still, due to the relatively small number of ratings that can be fed into DNNs, they may easily suffer from the overfitting issue. To tackle these issues, we propose a novel recommendation framework based on Back Propagation (BP) neural network with attention mechanism, namely BPAM++. In particular, the BP neural network is utilized to learn the complex relationship between the target user and his/her neighbors and the complex relationship between the target item and its neighbors. Compared with DNNs, the shallow neural network, i.e., BP neural network, can not only reduce the computational and storage costs, but also alleviate the overfitting issues in DNNs caused by a relatively small number of ratings. In addition, an attention mechanism is designed to capture the global impact of the nearest users of the target user on their nearest target user sets. Extensive experiments conducted on eight benchmark datasets confirm the effectiveness of the proposed model.

Recently, network embedding has received a large amount of attention in network analysis. Although some network embedding methods have been developed from different perspectives, on one hand, most of the existing methods only focus on leveraging the plain network structure, ignoring the abundant attribute information of nodes. On the other hand, for some methods integrating the attribute information, only the lower-order proximities (e.g., microscopic proximity structure) are taken into account, which may suffer if there exists the sparsity issue and the attribute information is noisy. To overcome this problem, the attribute information and mesoscopic community structure are utilized. In this article, we propose a novel network embedding method termed Attributed Network Embedding with Micro-Meso structure, which is capable of preserving both the attribute information and the structural information including the microscopic proximity structure and mesoscopic community structure. In particular, both the microscopic proximity structure and node attributes are factorized by Nonnegative Matrix Factorization (NMF), from which the low-dimensional node representations can be obtained. For the mesoscopic community structure, a community membership strength matrix is inferred by a generative model (i.e., BigCLAM) or modularity from the linkage structure, which is then factorized by NMF to obtain the low-dimensional node representations. The three components are jointly correlated by the low-dimensional node representations, from which two objective functions (i.e., ANEM_B and ANEM_M) can be defined. Two efficient alternating optimization schemes are proposed to solve the optimization problems. Extensive experiments have been conducted to confirm the superior performance of the proposed models over the state-of-the-art network embedding methods.

Community detection (or graph clustering) is crucial for unraveling the structural properties of complex networks. As an important technique in community detection, label propagation has shown the advantage of finding a good community structure with nearly linear time complexity. However, despite the progress that has been made, there are still several important issues that have not been properly addressed. First, the label propagation typically proceeds over the lower order structure of the network and only the direct one-hop connections between nodes are taken into consideration. Unfortunately, the higher order structure that may encode design principle of the network and be crucial for community detection is neglected under this regime. Second, the stability of the identified community structure may also be seriously affected by the inherent randomness in the label propagation process. To tackle the above issues, this article proposes a Motif-Aware Weighted Label Propagation method for community detection. We focus on triangles within the network, but our technique extends to other kinds of motifs as well. Specifically, the motif-based higher order structure mining is conducted to capture structural characteristics of the network. First, the motif of interest (locally meaningful pattern) is identified, and then, the motif-based hypergraph can be constructed to encode the higher order connections. To further utilize the structural information of the network, a re-weighted network is designed, which unifies both the higher order structure and the original lower order structure. Accordingly, a novel voting strategy termed NaS (considering both Number and Strength of connections) is proposed to update node labels during the label propagation process. In this way, the random label selection can be effectively eliminated, yielding more stable community structures. Experimental results on multiple real-world datasets have shown the superiority of the proposed method.

This paper focuses on scalability and robustness of spectral clustering for extremely large-scale datasets with limited resources. Two novel algorithms are proposed, namely, ultra-scalable spectral clustering (U-SPEC) and ultra-scalable ensemble clustering (U-SENC). In U-SPEC, a hybrid representative selection strategy and a fast approximation method for K-nearest representatives are proposed for the construction of a sparse affinity sub-matrix. By interpreting the sparse sub-matrix as a bipartite graph, the transfer cut is then utilized to efficiently partition the graph and obtain the clustering result. In U-SENC, multiple U-SPEC clusterers are further integrated into an ensemble clustering framework to enhance the robustness of U-SPEC while maintaining high efficiency. Based on the ensemble generation via multiple U-SEPC's, a new bipartite graph is constructed between objects and base clusters and then efficiently partitioned to achieve the consensus clustering result. It is noteworthy that both U-SPEC and U-SENC have nearly linear time and space complexity, and are capable of robustly and efficiently partitioning 10-million-level nonlinearly-separable datasets on a PC with 64 GB memory. Experiments on various large-scale datasets have demonstrated the scalability and robustness of our algorithms. The MATLAB code and experimental data are available at https://www.researchgate.net/publication/330760669.

Recommender system is widely used in e-commercial platforms to recommend users suitable items according to users's preferences. In recent years, an increasing amount of attention has been paid to the application of recommender system in education. There are many online learning systems that can recommend students suitable courses according to students' learning performances. However, there are few universities using recommender system to recommend students suitable elective courses. It is generally known that students in higher grade take the courses earlier than those in lower grade. Therefore, the elective course scores of sophomores can be predicted by using the course score information from students of higher grades. However, the unbalanced distribution of course-enrollment data makes it hard to predict the scores of the courses that are in a low selection rate. Therefore, we propose a Constrained Matrix Factorization (ConMF) algorithm to predict sophomores' elective course scores, which integrates the course average score into the objective function so as to make up the prediction deviation caused by the unbalanced course selection rate and make more accurate prediction than the traditional Matrix Factorization (MF) approach. The experimental results show that our proposed model outperforms the state-of-the-art methods in the task of university students' course score prediction.

Network community detection is a hot research topic in network analysis. Although many methods have been proposed for community detection, most of them only take into consideration the lower-order structure of the network at the level of individual nodes and edges. Thus, they fail to capture the higher-order characteristics at the level of small dense subgraph patterns, e.g., motifs. Recently, some higher-order methods have been developed but they typically focus on the motif-based hypergraph which is assumed to be a connected graph. However, such assumption cannot be ensured in some real-world networks. In particular, the hypergraph may become fragmented. That is, it may consist of a large number of connected components and isolated nodes, despite the fact that the original network is a connected graph. Therefore, the existing higher-order methods would suffer seriously from the above fragmentation issue, since in these approaches, nodes without connection in hypergraph can't be grouped together even if they belong to the same community. To address the above fragmentation issue, we propose an Edge enhancement approach for Motif-aware community detection (EdMot ). The main idea is as follows. Firstly, a motif-based hypergraph is constructed and the top K largest connected components in the hypergraph are partitioned into modules. Afterwards, the connectivity structure within each module is strengthened by constructing an edge set to derive a clique from each module. Based on the new edge set, the original connectivity structure of the input network is enhanced to generate a rewired network, whereby the motif-based higher-order structure is leveraged and the hypergraph fragmentation issue is well addressed. Finally, the rewired network is partitioned to obtain the higher-order community structure. Extensive experiments have been conducted on eight real-world datasets and the results show the effectiveness of the proposed method in improving the community detection performance of state-of-the-art methods.

Missing value is common in many machine learning problems and much effort has been made to handle missing data to improve the performance of the learned model. Sometimes, our task is not to train a model using those unlabeled/labeled data with missing value but process examples according to the values of some specified features. So, there is an urgent need of developing a method to predict those missing values. In this paper, we focus on learning from the known values to learn missing value as close as possible to the true one. It's difficult for us to predict missing value because we do not know the structure of the data matrix and some missing values may relate to some other missing values. We solve the problem by recovering the complete data matrix under the three reasonable constraints: feature relationship, upper recovery error bound and class relationship. The proposed algorithm can deal with both unlabeled and labeled data and generative adversarial idea will be used in labeled data to transfer knowledge. Extensive experiments have been conducted to show the effectiveness of the proposed algorithms.

Expert finding is an important technique to obtain the user authority ranking in community question answering (CQA) websites. ZhihuRank is a topic-sensitive expert finding algorithm, which is based on both LDA and PageRank. Currently, with the amount of participants and documents increasing rapidly in CQA websites, how to parallel expert finding algorithms for big data analysis has received significant attention. In this paper, we find that the Spark framework is more suitable for paralleling expert finding algorithms than the MapReduce framework, which is a memory-based parallel computing model to support complicated iterative algorithms. As an example, we parallel ZhihuRank using MLlib's LDA and GraphX's PageRank in Spark. Experiments have been conducted on large-scale real data from Zhihu1(the most popular CQA website in China). And the experimental results confirmed the effectiveness and scalability of our proposed approach.

Although many successful ensemble clustering approaches have been developed in recent years, there are still two limitations to most of the existing approaches. First, they mostly overlook the issue of uncertain links, which may mislead the overall consensus process. Second, they generally lack the ability to incorporate global information to refine the local links. To address these two limitations, in this paper, we propose a novel ensemble clustering approach based on sparse graph representation and probability trajectory analysis. In particular, we present the elite neighbor selection strategy to identify the uncertain links by locally adaptive thresholds and build a sparse graph with a small number of probably reliable links. We argue that a small number of probably reliable links can lead to significantly better consensus results than using all graph links regardless of their reliability. The random walk process driven by a new transition probability matrix is utilized to explore the global information in the graph. We derive a novel and dense similarity measure from the sparse graph by analyzing the probability trajectories of the random walkers, based on which two consensus functions are further proposed. Experimental results on multiple real-world datasets demonstrate the effectiveness and efficiency of our approach.

The availability of many heterogeneous but related views of data has arisen in numerous clustering problems. Different views encode distinct representations of the same data, which often admit the same underlying cluster structure. The goal of multi-view clustering is to properly combine information from multiple views so as to generate high quality clustering results that are consistent across different views. Based on max-product belief propagation, we propose a novel multi-view clustering algorithm termed multi-view affinity propagation (MVAP). The basic idea is to establish a multi-view clustering model consisting of two components, which measure the within-view clustering quality and the explicit clustering consistency across different views, respectively. Solving this model is NP-hard, and a multi-view affinity propagation is proposed, which works by passing messages both within individual views and across different views. However, the exemplar consistency constraint makes the optimization almost impossible. To this end, by using some previously designed mathematical techniques, the messages as well as the cluster assignment vector computations are simplified to get simple yet functionally equivalent computations. Experimental results on several real-world multi-view datasets show that MVAP outperforms existing multi-view clustering algorithms. It is especially suitable for clustering more than two views.

Recently, discovering dynamic communities has become an increasingly important task. Many algorithms have been proposed, most of which only use linkage structure. However, rich information is encoded in the content of social networks such as node content and edge content, which is essential to discover topically meaningful communities. Therefore, to detect both structurally and topically meaningful communities, linkage structure, node content and edge content should be integrated. The main challenge lies in how to integrate them dynamically in a seamless way. This paper proposes a novel transformation of content-based network into a Node-Edge Interaction (NEI) network where linkage structure, node content and edge content are embedded seamlessly. A differential activity based approach is proposed to incrementally maintain the NEI network as the content-based network evolves. To capture the semantic effect of different edge types, a transition probability matrix is devised for the NEI network. Based on this, heterogeneous random walk is applied to discover dynamic communities, leading to a new dynamic community detection method termed NEIWalk (NEI network based random Walk). Theoretical analysis shows that the proposed NEIWalk method gets a bounded accuracy loss due to the random walk sampling. Experimental results demonstrate the effectiveness and efficiency of NEIWalk.

In this paper, we aim to tackle the problem of discovering dynamic communities in weighted graph streams, especially when the underlying social behavior of individuals varies considerably over different graph regions. To tackle this problem, a novel structure termed Local Weighted-Edge-based Pattern (LWEP) Summary is proposed to describe a local homogeneous region. To efficiently compute LWEPs, some statistics need to be maintained according to the principle of preserving maximum weighted neighbor information with limited memory storage. To this end, the proposed approach is divided into online and offline components. During the online phase, we introduce some statistics, termed top-k neighbor lists and top-k candidate lists, to track. The key is to maintain only the top-k neighbors with the largest link weights for each node. To allow for less active neighbors to transition into top-k neighbors, an auxiliary data structure termed top-k candidate list is used to identify emerging active neighbors. The statistics can be efficiently maintained in the online component. In the offline component, these statistics are used at each snapshot to efficiently compute LWEPs. Clustering is then performed to consolidate LWEPs into high level clusters. Finally, mapping is made between clusters of consecutive snapshots to generate temporally smooth communities. Experimental results are presented to illustrate the effectiveness and efficiency of the proposed approach.

In this paper, we propose a novel data stream clustering algorithm, termed SVStream, which is based on support vector domain description and support vector clustering. In the proposed algorithm, the data elements of a stream are mapped into a kernel space, and the support vectors are used as the summary information of the historical elements to construct cluster boundaries of arbitrary shape. To adapt to both dramatic and gradual changes, multiple spheres are dynamically maintained, each describing the corresponding data domain presented in the data stream. By allowing for bounded support vectors (BSVs), the proposed SVStream algorithm is capable of identifying overlapping clusters. A BSV decaying mechanism is designed to automatically detect and remove outliers (noise). We perform experiments over synthetic and real data streams, with the overlapping, evolving, and noise situations taken into consideration. Comparison results with state-of-the-art data stream clustering methods demonstrate the effectiveness and efficiency of the proposed method.

Kernel-based clustering is one of the most popular methods for partitioning nonlinearly separable dataset. However, exhaustive search for the global optimum is NP-hard. Iterative procedure such as k-means can be used to seek one of the local minima. Unfortunately, it is easily trapped into degenerate local minima when the prototypes of clusters are ill-initialized. In this paper, we restate the optimization problem of kernel-based clustering in an on-line learning framework, whereby a conscience mechanism is easily integrated to tackle the ill-initialization problem and faster convergence rate is achieved. Thus, we propose a novel approach termed conscience on-line learning (COLL). For each randomly taken data point, our method selects the winning prototype based on the conscience mechanism to bias the ill-initialized prototype to avoid degenerate local minima, and efficiently updates the winner by the on-line learning rule. Therefore, it can more efficiently obtain smaller distortion error than k-means with the same initialization. Experimental results on synthetic and large-scale real-world datasets, as well as that in the application of video clustering, have demonstrated the significant improvement over existing kernel clustering methods.