Recent studies have explored querying large language models (LLMs) to serve as predictors for graph mining tasks on text-attributed graphs (TAGs), establishing a promising paradigm that surpasses Graph Neural Networks (GNNs) in scalability and generalization. However, the high token costs of LLMs make this approach prohibitively expensive for large-scale node queries, and effective multi-query optimization solutions are currently lacking. By conducting information theory analysis at the single query level, we have gained insights that enabled the development of two multi-query optimization strategies: token pruning and query boosting. The token pruning strategy is designed to reduce token usage without compromising task performance by identifying saturated node queries and pruning tokens for these queries. Meanwhile, the query boosting strategy is designed to enhance task performance by enriching the context of unexecuted queries with pseudo-labels derived from previous queries through strategic scheduling, thereby maximizing the utility of these pseudo-labels. Extensive experiments applying these two strategies, either jointly or individually, to various existing methods demonstrate that the proposed approach serves our intentions well. Besides, this paper offers a fresh methodology for optimizing LLM processing of graph tasks, demonstrating great potential. For most natural graph data benchmarks in the field, it can save tokens by several orders of magnitude. For example, on the Ogbn-Products dataset, it could theoretically save up to$2\times 10^{9}$tokens.

With the rapid growth of multimodal and multi-view data, multi-view bipartite graph clustering (MVBGC) has emerged as a promising solution for large-scale tasks, which with linear complexity. However, most methods adhere to a unidirectional “encoding” design, where the bipartite graph is directly constructed from input data. Enlightened by the prevalent encoding-decoding in deep learning, this paper rethinks existing paradigms and proposes a novel “auto-encoding” MVBGC framework, named BGAE. Our model seamlessly integrates encoding, bipartite graph learning, and decoding modules within a self-supervised learning framework. The encoding module extracts a joint representation from input data, the bipartite graph learning module learns a discriminative bipartite graph in latent semantic space, and the decoding module reconstructs the input data by the structural information. Extensive experiments verify the superiority of our novel design, particularly highlighting the critical role of “decoding” learning. This work represents the first attempt to explore encoding-decoding design in MVBGC.

Bipartite graph clustering (BGC) has emerged as a fast-growing research in the clustering community. Despite BGC has achieved promising scalability, most variants still suffer from the following concerns: a) Susceptibility to noisy features. They construct bipartite graphs in the raw feature space, inducing poor robustness to noisy features. b) Inflexible anchor selection strategies. They usually select anchors through heuristic sampling or constrained learning methods, degrading flexibility. c) Partial structure mining. Existing methods are mainly built upon Linear Reconstruction Paradigm (LRP) from subspace clustering or Locally Linear Paradigm (LLP) from manifold learning, which partially exploit linear or locally linear structures, lacking a unified perspective to integrate global complementary structures. To this end, we propose a novel model, termedJoint Robust Embedding and Structural FusionBipartiteGraphClustering (JetBGC), which focuses on three aspects, namely robustness, flexibility, and complementarity. Concretely, we first introduce a robust embedding learning module to extract latent representation that can reduce the impact of noisy features. Then, we optimize anchors via a constraint-free strategy that can flexibly capture data distribution. Furthermore, we revisit the consistency and specificity of LRP and LLP, and design a new unified structural fusion strategy to integrate both linear and locally linear structures from a global perspective. Therefore, JetBGC unifies robust representation learning, flexible anchor optimization, and structural bipartite graph fusion in a framework. Extensive experiments on synthetic and real-world datasets validate our effectiveness against existing baselines.

Generative recommendation systems have recently seen a surge in interest, largely due to the promising advancements in generative AI. As a competitive solution for multi-behavior sequence recommendations, much of the recent research has concentrated on predicting the next item a user will likely interact with using a generative approach. However, these methods often 1). assign multiple residual quantization layers to obtain item codes, which leads to extra storage costs of more codebooks. And 2). explicitly utilize behavior sequences leading to longer sequences, potentially increasing the training time as well as inference time compared with original sequences. In response to these challenges, we introduce theImplicitMulti-BehaviorGenerative recommendation with a mixture of quantization (IMBGen) approach in this paper. Specifically, we have devised aMixtureofQuantization (MoQ) that combines the merits of both residual and parallel quantization for a more effective tokenization process. Additionally, we propose an Implicit Behavior Modeling (IBM) framework, allowing for more efficient integration of users' behaviors into the interacted items. Finally, we conducted extensive experiments on two widely used benchmark datasets and further confirmed our findings with an online A/B test. The results consistently demonstrate the advantages of our approach over other baseline methods.

Discovering user preferences across different domains is pivotal in cross-domain recommendation systems, particularly when platforms lack comprehensive user-item interactive data. The limited presence of shared users often hampers the effective modeling of common preferences. While leveraging shared items’ attributes, such as category and popularity, can enhance cross-domain recommendation performance, the scarcity of shared items between domains has limited research in this area. To address this, we propose a Coherence-guided Preference Disentanglement (CoPD) method aimed at improving cross-domain recommendation by (i) explicitly extracting shared item attributes to guide the learning of shared user preferences and (ii) disentangling these preferences to identify specific user interests transferred between domains. CoPD introduces coherence constraints on item embeddings of shared and specific domains, aiding in extracting shared attributes. Moreover, it utilizes these attributes to guide the disentanglement of user preferences into separate embeddings for interest and conformity through a popularity-weighted loss. Experiments conducted on real-world datasets demonstrate the superior performance of our proposed CoPD over existing competitive baselines, highlighting its effectiveness in enhancing cross-domain recommendation performance. The code is available at https://github.com/XiangZongyi/CoPD .

Graph Prompt Learning (GPL) bridges significant disparities between pretraining and downstream applications to alleviate the knowledge transfer bottleneck in real-world graph learning. While GPL offers superior effectiveness in graph knowledge transfer and computational efficiency, the security risks posed by backdoor poisoning effects embedded in pretrained models remain largely unexplored. Our study provides a comprehensive analysis of GPL's vulnerability to backdoor attacks. We introduce CrossBA, the first cross-context backdoor attack against GPL, which manipulates only the pretraining phase without requiring knowledge of downstream applications. Our investigation reveals both theoretically and empirically that tuning trigger graphs, combined with prompt transformations, can seamlessly transfer the backdoor threat from pretrained encoders to downstream applications.Through extensive experiments involving 3 representative GPL methods across 5 distinct cross-context scenarios and 5 benchmark datasets of node and graph classification tasks, we demonstrate that CrossBA consistently achieves high attack success rates while preserving the functionality of downstream applications over clean input. We also explore potential countermeasures against CrossBA and conclude that current defenses are insufficient to mitigate CrossBA. Our study highlights the persistent backdoor threats to GPL systems, raising trustworthiness concerns in the practices of GPL techniques.

Multivariate time-series (MTS) forecasting is a paramount and fundamental problem in many real-world applications. The core issue in MTS forecasting is how to effectively model complex spatial-temporal patterns. In this paper, we develop a adaptive, interpretable and scalable forecasting framework, which seeks to individually model each component of the spatial-temporal patterns. We name this framework SCNN, as an acronym ofStructuredComponent-basedNeuralNetwork. SCNN works with a pre-defined generative process of MTS, which arithmetically characterizes the latent structure of the spatial-temporal patterns. In line with its reverse process, SCNN decouples MTS data into structured and heterogeneous components and then respectively extrapolates the evolution of these components, the dynamics of which are more traceable and predictable than the original MTS. Extensive experiments are conducted to demonstrate that SCNN can achieve superior performance over state-of-the-art models on three real-world datasets. Additionally, we examine SCNN with different configurations and perform in-depth analyses of the properties of SCNN.

Unsupervised multi-view bipartite graph clustering (MVBGC) is a fast-growing research, due to promising scalability in large-scale tasks. Although many variants are proposed by various strategies, a common design is to construct the bipartite graph directly from the input data, i.e. only consider the unidirectional “encoding” process. However, “encoding-decoding” mechanism is a popular design for deep learning, the most representative one is auto-encoder (AE). Enlightened by this, this paper rethinks existing MVBGC paradigms and transfers the “encoding-decoding” design into graph machine learning, and proposes a novel framework termed auto-encoding multi-view bipartite graph clustering (BGAE), which integrates encoding, bipartite graph construction, and decoding modules in a self-supervised learning manner. The encoding module extracts a latent joint representation from the input data, the bipartite graph construction module learns a bipartite graph with connectivity constraint in latent semantic space, and the decoding module recreates the input data via the bipartite graph. Therefore, our novel BGAE combines representation learning, bipartite graph learning, reconstruction learning, and label inference into a unified framework. All the modules are seamlessly integrated and mutually reinforcing for clustering-friendly purposes. Extensive experiments verify the superiority of our novel design and the significance of “decoding” process. To the best of our knowledge, this is the first attempt to explore “encoding-decoding” design in traditional MVBGC. The code is provided athttps://github.com/liliangnudt/BGAE.

In this study, we present a transductive inference approach on that reward information propagation graph, which enables the effective estimation of rewards for unlabelled data in offline reinforcement learning. Reward inference is the key to learning effective policies in practical scenarios, while direct environmental interactions are either too costly or unethical and the reward functions are rarely accessible, such as in healthcare and robotics. Our research focuses on developing a reward inference method based on the contextual properties of information propagation on graphs that capitalizes on a constrained number of human reward annotations to infer rewards for unlabelled data. We leverage both the available data and limited reward annotations to construct a reward propagation graph, wherein the edge weights incorporate various influential factors pertaining to the rewards. Subsequently, we employ the constructed graph for transductive reward inference, thereby estimating rewards for unlabelled data. Furthermore, we establish the existence of a fixed point during several iterations of the transductive inference process and demonstrate its at least convergence to a local optimum. Empirical evaluations on locomotion and robotic manipulation tasks validate the effectiveness of our approach. The application of our inferred rewards improves the performance in offline reinforcement learning tasks.

Graph-based multi-view learning, which has hitherto been used to discover the intrinsic patterns of graph data giving the credit to its convenience of implementation and effectiveness. Note that even though these approaches have been increasingly adopted in multi-view clustering and have generated promising outcomes, they are still faced with the sub-optimal solution. For one thing, multi-view data can be corrupted in the raw feature space. For the other, most existing approaches normally utilize euclidean distance to obtain the similarity between two samples, which can not be the best option for all types of real-world data and leads to inferior results. Therefore, to overcome the aforementioned issues, we integrate multi-metric learning, graph filtering, and subspace learning into a collaborative learning framework for multi-view clustering. Particularly, we prefer to recover a smooth representation of data by graph filtering, which can reserve the geometric structure of the original multi-view data and discard the corruptions simultaneously. Furthermore, instead of using euclidean distance as a Swiss army knife, multiple metrics are utilized to fully exploit the correlation of data based on the smooth representation, hence finally facilitating the downstream clustering task. Extensive experiments on multi-view clustering tasks validate our theoretical findings of ours and prove the improvement of our method over the SOTA approaches.

Graph neural networks (GNNs) are designed to perform inference on data described by graph-structured node features and topology information. From the perspective of graph signal denoising, the typical message passing schemes of GNNs act as a globally uniform smoothing that minimizes disagreements between embeddings of connected nodes. However, the level of smoothing over different regions of the graph should be different, especially for those inter-class regions. This deviation limits the expressiveness of GNNs, and then renders them fragile to over-smoothing, long-range dependencies, and non-homophily settings. In this paper, we find that the node disagreements of initial graph features can present more trustworthy constraints on node embeddings, thereby enhancing the locally adaptive smoothing of GNNs. To spread the inherent disagreements of nodes, we propose the Laplacian node disagreement to jointly measure the initial features and output embeddings. With such a measurement, we then present a new graph signal denoising objective deriving a more effective message passing scheme and further incorporate it into the GNN architecture, named Laplacian node disagreement-based GNN (LND-GNN). Learning from its output node representations, we integrate an auxiliary disagreement constraint into the overall classification loss. Experiments demonstrate the expressive ability of LND-GNN in the downstream semi-supervised node classification task.

Multi-task learning (MTL) is a widely adopted machine learning paradigm in recommender systems. However, existing MTL models often suffer from performance degeneration with negative transfer and seesaw phenomena. Some works attempt to alleviate the negative transfer and seesaw issues by separating task-specific and shared experts to mitigate the harmful interference between task-specific and shared knowledge. Despite the success of these efforts, task-specific and shared knowledge have still not been thoroughly decoupled. There may still exist unnecessary mixture between the shared and task-specific knowledge, which may harm MLT models' performances. To tackle this problem, in this paper, we propose multi-task knowledge disentanglement network (MTKDN) to further reduce harmful interference between the shared and task-specific knowledge. Specifically, we propose a novel contrastive disentanglement mechanism to explicitly decouple the shared and task-specific knowledge in corresponding hidden spaces. In this way, the unnecessary mixture between shared and task-specific knowledge can be reduced. As for optimization objectives, we propose individual optimization objectives for shared and task-specific experts, by which we can encourage these two kinds of experts to focus more on extracting the shared and task-specific knowledge, respectively. Additionally, we propose a margin regularization to ensure that the fusion of shared and task-specific knowledge can outperform exploiting either of them alone. We conduct extensive experiments on open-source large-scale recommendation datasets. The experimental results demonstrate that MTKDN significantly outperforms state-of-the-art MTL models. In addition, the ablation experiments further verify the necessity of our proposed contrastive disentanglement mechanism and the novel loss settings.

Multi-variate time series (MTS) data is a ubiquitous class of data abstraction in the real world. Any instance of MTS is generated from a hybrid dynamical system and their specific dynamics are usually unknown. The hybrid nature of such a dynamical system is a result of complex external attributes, such as geographic location and time of day, each of which can be categorized into either spatial attributes or temporal attributes. Therefore, there are two fundamental views which can be used to analyze MTS data, namely the spatial view and the temporal view. Moreover, from each of these two views, we can partition the set of data samples of MTS into disjoint forecasting tasks in accordance with their associated attribute values. Then, samples of the same task will manifest similar forthcoming pattern, which is less sophisticated to be predicted in comparison with the original single-view setting. Considering this insight, we propose a novel multi-view multi-task (MVMT) learning framework for MTS forecasting. Instead of being explicitly presented in most scenarios, MVMT information is deeply concealed in the MTS data, which severely hinders the model from capturing it naturally. To this end, we develop two kinds of basic operations, namely task-wise affine transformation and task-wise normalization, respectively. Applying these two operations with prior knowledge on the spatial and temporal view allows the model to adaptively extract MVMT information while predicting. Extensive experiments on three datasets are conducted to illustrate that canonical architectures can be greatly enhanced by the MVMT learning framework in terms of both effectiveness and efficiency. In addition, we design rich case studies to reveal the properties of representations produced at different phases in the entire prediction procedure.

In multi-view subspace clustering, it is significant to find a common latent space in which the multi-view datasets are located. A number of multi-view subspace clustering methods have been proposed to explore the common latent subspace and achieved promising performance. However, previous multi-view subspace clustering algorithms seldom consider the multi-view consistency and multi-view diversity, let alone take them into consideration simultaneously. In this paper, we propose a novel multi-view subspace clustering by joint measuring the consistency and diversity, which is able to exploit these two complementary criteria seamlessly into a holistic design of clustering algorithms. The proposed model first searches a pure graph for each view by detecting the intrinsic consistent and diverse parts. A consensus graph is then obtained by fusing the multiple pure graphs. Moreover, the consensus graph is structurized to contain exactly$c$connected components where$c$is the number of clusters. In this way, the final clustering result can be obtained directly since each connected component precisely corresponds to an individual cluster. Extensive experimental studies on various datasets manifest that our model achieves comparable performance than the other state-of-the-art methods.

Multi-view clustering aims to reveal the correlation between different input modalities in an unsupervised way. Similarity between data samples can be described by a similarity graph, which governs the quality of multi-view clustering. However, existing multi-view graph learning methods mainly construct similarity graph based on raw features, which are unreliable as real-world datasets usually contain noises, outliers, or even redundant information. In this paper, we formulate a novel model to simultaneously learn a robust structured similarity graph and perform multi-view clustering. The similarity graph is adaptively learned based on a latent representation that is invulnerable to noises and outliers. Furthermore, the similarity graph is enforced to contain a clear structure, i.e., the number of connected components of the target graph is exactly equal to the ground-truth class number. Consequently, the label to each data sample can be directly assigned without any postprocessing. As a result, our model aims at accomplishing three subtasks: latent representation extraction, similarity graph learning, and cluster label allocation, in a unified framework. These three subtasks are seamlessly integrated and can be mutually boosted by each other towards the overall optimal solution. An efficient alternation algorithm is proposed to solve the optimization problem. Experimental results on several benchmark datasets illustrate the effectiveness of the proposed model.

Cold-start has become critical for recommendations, especially for sparse user-item interactions. Recent approaches based on meta-learning succeed in alleviating the issue, owing to the fact that these methods have strong generalization, so they can fast adapt to new tasks under cold-start settings. However, these meta-learning-based recommendation models learned with single and spase ratings are easily falling into the meta-overfitting, since the one and only rating$r_{ui}$to a specific item$i$cannot reflect a user's diverse interests under various circumstances(e.g., time, mood, age, etc), i.e. if$r_{ui}$equals to 1 in the historical dataset, but$r_{ui}$could be 0 in some circumstance. In meta-learning, tasks with these single ratings are called Non-Mutually-Exclusive(Non-ME) tasks, and tasks with diverse ratings are called Mutually-Exclusive(ME) tasks. Fortunately, a meta-augmentation technique is proposed to relief the meta-overfitting for meta-learning methods by transferring Non-ME tasks into ME tasks by adding noises to labels without changing inputs. Motivated by the meta-augmentation method, in this paper, we propose a cross-domain meta-augmentation technique for content-aware recommendation systems (MetaCAR) to construct ME tasks in the recommendation scenario. Our proposed method consists of two stages: meta-augmentation and meta-learning. In the meta-augmentation stage, we first conduct domain adaptation by a dual conditional variational autoencoder (CVAE) with a multi-view information bottleneck constraint, and then apply the learned CVAE to generate ratings for users in the target domain. In the meta-learning stage, we introduce both the true and generated ratings to construct ME tasks that enables the meta-learning recommendations to avoid meta-overfitting. Experiments evaluated in real-world datasets show the significant superiority of MetaCAR for coping with the cold-start user issue over competing baselines including cross-domain, content-aware, and meta-learning-based recommendations.

Cross domain recommendation (CDR) is one popular research topic in recommender systems. This article focuses on a popular scenario for CDR where different domains share the same set of users but no overlapping items. The majority of recent methods have explored the shared-user representation to transfer knowledge across domains. However, the idea of shared-user representation resorts to learning the overlapped features of user preferences and suppresses the domain-specific features. Other works try to capture the domain-specific features by an MLP mapping but require heuristic human knowledge of choosing samples to train the mapping. In this article, we attempt to learn both features of user preferences in a more principled way. We assume that each user’s preferences in one domain can be expressed by the other one, and these preferences can be mutually converted to each other with the so-called equivalent transformation. Based on this assumption, we propose an equivalent transformation learner (ETL), which models the joint distribution of user behaviors across domains. The equivalent transformation in ETL relaxes the idea of shared-user representation and allows the learned preferences in different domains to preserve the domain-specific features as well as the overlapped features. Extensive experiments on three public benchmarks demonstrate the effectiveness of ETL compared with recent state-of-the-art methods. Codes and data are available online: https://github.com/xuChenSJTU/ETL-master.

Cold-start issues have been more and more challenging for providing accurate recommendations with the fast increase of users and items. Most existing approaches attempt to solve the intractable problems via content-aware recommendations based on auxiliary information and/or cross-domain recommendations with transfer learning. Their performances are often constrained by the extremely sparse user-item interactions, unavailable side information, or very limited domain-shared users. Recently, meta-learners with meta-augmentation by adding noises to labels have been proven to be effective to avoid overfitting and shown good performance on new tasks. Motivated by the idea of meta-augmentation, in this paper, by treating a user's preference over items as a task, we propose a so-called Diverse Preference Augmentation framework with multiple source domains based on meta-learning (referred to as MetaDPA) to i) generate diverse ratings in a new domain of interest (known as target domain) to handle overfitting on the case of sparse interactions, and to ii) learn a preference model in the target domain via a meta-learning scheme to alleviate cold-start issues. Specifically, we first conduct multi-source domain adaptation by dual conditional variational autoencoders and impose a Multi-domain InfoMax (MDI) constraint on the latent representations to learn domain-shared and domain-specific preference properties. To avoid overfitting, we add a Mutually-Exclusive (ME) constraint on the output of decoders to generate diverse ratings given content data. Finally, these generated diverse ratings and the original ratings are introduced into the meta-training procedure to learn a preference meta-learner, which produces good generalization ability on cold-start recommendation tasks. Experiments on real-world datasets show our proposed MetaDPA clearly outperforms the current state-of-the-art baselines.

Network alignment is a critical task in a wide variety of fields. Many existing works leverage on representation learning to accomplish this task without eliminating domain representation bias induced by domain-dependent features, which yield inferior alignment performance. This paper proposes a unified deep architecture (DANA) to obtain a domain-invariant representation for network alignment via an adversarial domain classifier. Specifically, we employ the graph convolutional networks to perform network embedding under the domain adversarial principle, given a small set of observed anchors. Then, the semi-supervised learning framework is optimized by maximizing a posterior probability distribution of observed anchors and the loss of a domain classifier simultaneously. We also develop a few variants of our model, such as, direction-aware network alignment, weight-sharing for directed networks and simplification of parameter space. Experiments on three real-world social network datasets demonstrate that our proposed approaches achieve state-of-the-art alignment results.

Graph learning has emerged as a promising technique for multi-view clustering due to its efficiency of learning a unified graph from multiple views. Previous multi-view graph learning methods mainly try to exploit the multi-view consistency to boost learning performance. However, these methods ignore the prevalent multi-view diversity which may be induced by noise, corruptions, or even view-specific attributes. In this paper, we propose to simultaneously and explicitly leverage the multi-view consistency and the multi-view diversity in a unified framework. The consistent parts are further fused to our target graph with a clear clustering structure, on which the cluster label to each instance can be directly allocated without any postprocessing such as$k$-means in classical spectral clustering. In addition, our model can automatically assign suitable weight for each view based on its clustering capacity. By leveraging the subtasks of measuring the diversity of graphs, integrating the consistent parts with automatically learned weights, and allocating cluster label to each instance in a joint framework, each subtask can be alternately boosted by utilizing the results of the others towards an overall optimal solution. Extensive experimental results on several benchmark multi-view datasets demonstrate the effectiveness of our model in comparison to several state-of-the-art algorithms.

Recommendation efficiency and data sparsity problems have been regarded as two main challenges of real-world recommendation systems. Most existing works focus on improving recommendation accuracy instead of efficiency. In this paper, we propose a Deep Pairwise Hashing (DPH) to map users and items to binary vectors in the Hamming space, where a user's preference for an item can be efficiently calculated by the Hamming distance, which significantly improves the efficiency of online recommendation. To alleviate data sparsity and cold-start problems, the item content information exploited and integrated to learn effective representations of items. Specifically, we first pre-train robust item representation from item content data by a robust Denoising Auto-encoder instead of other deterministic deep learning frameworks. Then we fine-tune the entire recommender framework by adding a pairwise loss function with discrete constraints, which is more consistent with the ultimate goal of producing a ranked list of items. Finally, we adopt the alternating optimization method to optimize the proposed model with discrete constraints. Extensive experiments conducted on three different datasets show that DPH can significantly advance the state-of-the-art frameworks regarding data sparsity and cold-start item recommendation.

Multi-variate time series (MTS) data is a ubiquitous class of data abstraction in the real world. Any instance of MTS is generated from a hybrid dynamical system with their specific dynamics normally unknown. The hybrid nature of such a dynamical system is a result of complex external impacts, which can be summarized as high-frequency and low-frequency from the temporal view, or global and local if we take the spatial view. These impacts also determine the forthcoming development of MTS making them paramount to capture in a time series forecasting task. However, conventional methods face intrinsic difficulties in disentangling the components yielded by each kind of impact from the raw data. To this end, we propose two kinds of normalization modules -- temporal and spatial normalization -- which separately refine the high-frequency component and the local component underlying the raw data. Moreover, both modules can be readily integrated into canonical deep learning architectures such as Wavenet and Transformer. Extensive experiments on three datasets are conducted to illustrate that, with additional normalization modules, the performance of the canonical architectures can be enhanced by a large margin in the application of MTS and achieves state-of-the-art results compared with existing MTS models.

Transportation demand forecasting is a topic of large practical value. However, the model that fits the demand of one transportation by only considering the historical data of its own could be vulnerable since random fluctuations could easily impact the modeling. On the other hand, common factors like time and region attribute, drive the evolution demand of different transportation, leading to a co-evolving intrinsic property between different kinds of transportation. In this work, we focus on exploring the co-evolution between different modes of transport, e.g., taxi demand and shared-bike demand. Two significant challenges impede the discovery of the co-evolving pattern: (1) diversity of the co-evolving correlation, which varies from region to region and time to time. (2) Multi-modal data fusion. Taxi demand and shared-bike demand are time-series data, which have different representations with the external factors. Moreover, the distribution of taxi demand and bike demand are not identical. To overcome these challenges, we propose a novel method, known as co-evolving spatial temporal neural network (CEST). CEST learns a multi-view demand representation for each mode of transport, extracts the co-evolving pattern, then predicts the demand for the target transportation based on multi-scale representation, which includes fine-scale demand information and coarse-scale pattern information. We conduct extensive experiments to validate the superiority of our model over the state-of-art models.

It is challenging for stochastic optimization to handle large-scale sensitive data safely. Duchi et al. recently proposed a private sampling strategy to solve privacy leakage in stochastic optimization. However, this strategy leads to a degeneration in robustness, since this strategy is equal to noise injection on each gradient, which adversely affects updates of the primal variable. To address this challenge, we introduce a robust stochastic optimization under the framework of local privacy, which is called Privacy-pREserving StochasTIc Gradual lEarning (PRESTIGE). PRESTIGE bridges private updates of the primal variable (by private sampling) with gradual curriculum learning (CL). The noise injection leads to similar issue from label noise, but the robust learning process of CL can combat with label noise. Thus, PRESTIGE yields “private but robust” updates of the primal variable on the curriculum, that is, a reordered label sequence provided by CL. In theory, we reveal the convergence rate and maximum complexity of PRESTIGE. Empirical results on six datasets show that PRESTIGE achieves a good tradeoff between privacy preservation and robustness over baselines.

Approximate nearest neighbour search (ANNS) in high dimensional space is a fundamental problem in many applications, such as multimedia database, computer vision and information retrieval. Among many solutions, data-sensitive hashing-based methods are effective to this problem, yet few of them are designed for external storage scenarios and hence do not optimized for I/O efficiency during the query processing. In this paper, we introduce a novel data-sensitive indexing and query processing framework for ANNS with an emphasis on optimizing the I/O efficiency, especially, the sequential I/Os. The proposed index consists of several lists of point IDs, ordered by values that are obtained by learned hashing (i.e., mapping) functions on each corresponding data point. The functions are learned from the data and approximately preserve the order in the high-dimensional space. We consider two instantiations of the functions (linear and non-linear), both learned from the data with novel objective functions. We also develop an I/O efficient ANNS framework based on the index. Comprehensive experiments on six benchmark datasets show that our proposed methods with learned index structure perform much better than the state-of-the-art external memory-based ANNS methods in terms of I/O efficiency and accuracy.

In this paper, we propose a simple variant of the original SVRG, called variance reduced stochastic gradient descent (VR-SGD). Unlike the choices of snapshot and starting points in SVRG and its proximal variant, Prox-SVRG, the two vectors of VR-SGD are set to the average and last iterate of the previous epoch, respectively. The settings allow us to use much larger learning rates, and also make our convergence analysis more challenging. We also design two different update rules for smooth and nonsmooth objective functions, respectively, which means that VR-SGD can tackle non-smooth and/or non-strongly convex problems directly without any reduction techniques. Moreover, we analyze the convergence properties of VR-SGD for strongly convex problems, which show that VR-SGD attains linear convergence. Different from most algorithms that have no convergence guarantees for nonstrongly convex problems, we also provide the convergence guarantees of VR-SGD for this case, and empirically verify that VR-SGD with varying learning rates achieves similar performance to its momentum accelerated variant that has the optimal convergence rate O(1=T2). Finally, we apply VR-SGD to solve various machine learning problems, such as convex and non-convex empirical risk minimization, and leading eigenvalue computation. Experimental results show that VR-SGD converges significantly faster than SVRG and Prox-SVRG, and usually outperforms state-of-the-art accelerated methods, e.g., Katyusha.

Matrix factorization has been widely applied to various applications. With the fast development of storage and internet technologies, we have been witnessing a rapid increase of data. In this paper, we propose new algorithms for matrix factorization with the emphasis on efficiency. In addition, most existing methods of matrix factorization only consider a general smooth least square loss. Differently, many real-world applications have distinctive characteristics. As a result, different losses should be used accordingly. Therefore, it is beneficial to design new matrix factorization algorithms that are able to deal with both smooth and non-smooth losses. To this end, one needs to analyze the characteristics of target data and use the most appropriate loss based on the analysis. We particularly study two representative cases of low-rank matrix recovery, i.e., collaborative filtering for recommendation and high dynamic range imaging. To solve these two problems, we respectively propose a stage-wise matrix factorization algorithm by exploiting manifold optimization techniques. From our theoretical analysis, they are both are provably guaranteed to converge to a stationary point. Extensive experiments on recommender systems and high dynamic range imaging demonstrate the satisfactory performance and efficiency of our proposed method on large-scale real data.

Graph neural nets are emerging tools to represent network nodes for classification. However, existing approaches typically suffer from two limitations: (1) they only aggregate information from short distance (e.g., 1-hop neighbors) each round and fail to capturelong distance relationship in graphs; (2) they require users to label data from several classes to facilitate the learning of discriminative models; whereas in reality, users may only provide labels of a small number of nodes in a single class. To overcome these limitations, this paper presents a novel long-short distance aggregation networks (\textttLSDAN ) for positive unlabeled (PU) graph learning. Our theme is to generate multiple graphs at different distances based on the adjacency matrix, and further develop a long-short distance attention model for these graphs. The short-distance attention mechanism is used to capture the importance of neighbor nodes to a target node. The long-distance attention mechanism is used to capture the propagation of information within a localized area of each node and help model weights of different graphs for node representation learning. A non-negative risk estimator is further employed, to aggregate long- short-distance networks, for PU learning using back-propagated loss modeling. Experiments on real-world datasets validate the effectiveness of our approach.

Information network embedding is an effective way for efficient graph analytics. However, it still faces with computational challenges in problems such as link prediction and node recommendation, particularly with increasing scale of networks. Hashing is a promising approach for accelerating these problems by orders of magnitude. However, no prior studies have been focused on seeking binary codes for information networks to preserve high-order proximity. Since matrix factorization (MF) unifies and outperforms several well-known embedding methods with high-order proximity preserved, we propose a MF-based \underlineI nformation \underlineN etwork \underlineH ashing (INH-MF) algorithm, to learn binary codes which can preserve high-order proximity. We also suggest Hamming subspace learning, which only updates partial binary codes each time, to scale up INH-MF. We finally evaluate INH-MF on four real-world information network datasets with respect to the tasks of node classification and node recommendation. The results demonstrate that INH-MF can perform significantly better than competing learning to hash baselines in both tasks, and surprisingly outperforms network embedding methods, including DeepWalk, LINE and NetMF, in the task of node recommendation. The source code of INH-MF is available online\footnote\urlhttps://github.com/DefuLian/network .

The efficiency of top-k recommendation is vital to large-scale recommender systems. Hashing is not only an efficient alternative but also complementary to distributed computing, and also a practical and effective option in a computing environment with limited resources. Hashing techniques improve the efficiency of online recommendation by representing users and items by binary codes. However, objective functions of existing methods are not consistent with ultimate goals of recommender systems, and are often optimized via discrete coordinate descent, easily getting stuck in a local optimum. To this end, we propose a Discrete Ranking-based Matrix Factorization (DRMF) algorithm based on each user's pairwise preferences, and formulate it into binary quadratic programming problems to learn binary codes. Due to non-convexity and binary constraints, we further propose self-paced learning for improving the optimization, to include pairwise preferences gradually from easy to complex. We finally evaluate the proposed algorithm on three public real-world datasets, and show that the proposed algorithm outperforms the state-of-the-art hashing-based recommendation algorithms, and even achieves comparable performance to matrix factorization methods.

Approximate nearest neighbor (ANN) search has achieved great success in many tasks. However, existing popular methods for ANN search, such as hashing and quantization methods, are designed for static databases only. They cannot handle well the database with data distribution evolving dynamically, due to the high computational effort for retraining the model based on the new database. In this paper, we address the problem by developing an online product quantization (online PQ) model and incrementally updating the quantization codebook that accommodates to the incoming streaming data. Moreover, to further alleviate the issue of large scale computation for the online PQ update, we design two budget constraints for the model to update partial PQ codebook instead of all. We derive a loss bound which guarantees the performance of our online PQ model. Furthermore, we develop an online PQ model over a sliding window with both data insertion and deletion supported, to reflect the real-time behavior of the data. The experiments demonstrate that our online PQ model is both time-efficient and effective for ANN search in dynamic large scale databases compared with baseline methods and the idea of partial PQ codebook update further reduces the update cost.

The weakly supervised Multiple-Instance Learning (MIL) problem has been successfully applied in information retrieval tasks. Two related issues might affect the performance of MIL algorithms: how to cope with label ambiguities and how to deal with non-discriminative components, and we propose COmpact MultiPle-Instance LEarning (COMPILE) to consider them simultaneously. To treat label ambiguities, COMPILE seeks ground-truth positive instances in positive bags. By using weakly supervised information to learn data's short binary representations, COMPILE enhances discrimination via strengthening discriminative components and suppressing non-discriminative ones. We adapt block coordinate descent to optimize COMPILE efficiently. Experiments on text categorization empirically show: 1) COMPILE unifies disambiguation and data preprocessing successfully; 2) it generates short binary representations efficiently to enhance discrimination at significantly reduced storage cost.

Graph classification is an important tool for analyzing data with structure dependency, where subgraphs are often used as features for learning. In reality, the dimension of the subgraphs crucially depends on the threshold setting of the frequency support parameter, and the number may become extremely large. As a result, subgraphs may be incrementally discovered to form a feature stream and require the underlying graph classifier to effectively discover representative subgraph features from the subgraph feature stream. In this paper, we propose a primal-dual incremental subgraph feature selection algorithm (ISF) based on a max-margin graph classifier. The ISF algorithm constructs a sequence of solutions that are both primal and dual feasible. Each primal-dual pair shrinks the dual gap and renders a better solution for the optimal subgraph feature set. To avoid bias of ISF algorithm on short-pattern subgraph features, we present a new incremental subgraph join feature selection algorithm (ISJF) by forcing graph classifiers to join short-pattern subgraphs and generate long-pattern subgraph features. We evaluate the performance of the proposed models on both synthetic networks and real-world social network data sets. Experimental results demonstrate the effectiveness of the proposed methods.

Social recommendation explores social information to improve the quality of a recommender system. It can be further divided into explicit and implicit social network recommendation. The former assumes the existence of explicit social connections between users in addition to the rating data. The latter one assumes the availability of only the ratings but not the social connections between users since the explicit social information data may not necessarily be available and usually are binary decision values (e.g., whether two people are friends), while the strength of their relationships is missing. Most of the works in this field use only rating data to infer the latent social networks. They ignore the dynamic nature of users that the preferences of users drift over time distinctly. To this end, we propose a new Implicit Dynamic Social Recommendation (IDSR) model, which infers latent social network from cascade data. It can sufficiently mine the information contained in time by mining the cascade data and identify the dynamic changes in the users in time by using the latest updated social network to make recommendations. Experiments and comparisons on three real-world datasets show that the proposed model outperforms the state-of-the-art solutions in both explicit and implicit scenarios.

Graph classification is an important tool for analysing structured and semi-structured data, where subgraphs are commonly used as the feature representation. However, the number and size of subgraph features crucially depend on the threshold parameters of frequent subgraph mining algorithms. Any improper setting of the parameters will generate many trivial short-pattern subgraph fragments which dominate the feature space, distort graph classifiers and bury interesting long-pattern subgraphs. In this paper, we propose a new Subgraph Join Feature Selection (SJFS) algorithm. The SJFS algorithm, by forcing graph classifiers to join short-pattern subgraph fragments, can defrag trivial subgraph features and deliver long-pattern interesting subgraphs. Experimental results on both synthetic and real-world social network graph data demonstrate the performance of the proposed method.

Although graph embedding has been a powerful tool for modeling data intrinsic structures, simply employing all features for data structure discovery may result in noise amplification. This is particularly severe for high dimensional data with small samples. To meet this challenge, this paper proposes a novel efficient framework to perform feature selection for graph embedding, in which a category of graph embedding methods is cast as a least squares regression problem. In this framework, a binary feature selector is introduced to naturally handle the feature cardinality in the least squares formulation. The resultant integral programming problem is then relaxed into a convex Quadratically Constrained Quadratic Program (QCQP) learning problem, which can be efficiently solved via a sequence of accelerated proximal gradient (APG) methods. Since each APG optimization is w.r.t. only a subset of features, the proposed method is fast and memory efficient. The proposed framework is applied to several graph embedding learning problems, including supervised, unsupervised, and semi-supervised graph embedding. Experimental results on several high dimensional data demonstrated that the proposed method outperformed the considered state-of-the-art methods.

We propose a multi-view learning approach called co-labeling which is applicable for several machine learning problems where the labels of training samples are uncertain, including semi-supervised learning (SSL), multi-instance learning (MIL) and max-margin clustering (MMC). Particularly, we first unify those problems into a general ambiguous problem in which we simultaneously learn a robust classifier as well as find the optimal training labels from a finite label candidate set. To effectively utilize multiple views of data, we then develop our co-labeling approach for the general multi-view ambiguous problem. In our work, classifiers trained on different views can teach each other by iteratively passing the predictions of training samples from one classifier to the others. The predictions from one classifier are considered as label candidates for the other classifiers. To train a classifier with a label candidate set for each view, we adopt the Multiple Kernel Learning (MKL) technique by constructing the base kernel through associating the input kernel calculated from input features with one label candidate. Compared with the traditional co-training method which was specifically designed for SSL, the advantages of our co-labeling are two-fold: 1) it can be applied to other ambiguous problems such as MIL and MMC, 2) it is more robust by using the MKL method to integrate multiple labeling candidates obtained from different iterations and biases. Promising results on several real-world multi-view data sets clearly demonstrate the effectiveness of our proposed co-labeling for both MIL and SSL.

In the absence of the labeled samples in a domain referred to as target domain, Domain Adaptation (DA) techniques come in handy. Generally, DA techniques assume there are available source domains that share similar predictive function with the target domain. Two core challenges of DA typically arise, variance that exists between source and target domains, and the inherent source hypothesis bias. In this paper, we first propose a Stability Transfer criterion for selecting relevant source domains with low variance. With this criterion, we introduce a TARget learning Assisted by Source Classifier Adaptation (TARASCA) method to address the two core challenges that have impeded the performances of DA techniques. To verify the robustness of TARASCA, extensive experimental studies are carried out with comparison to several state-of-the-art DA methods on the real-world Sentiment and Newsgroups datasets, where various settings for the class ratios of the source and target domains are considered.

Data ambiguities exist in many data mining and machine learning applications such as text categorization and image retrieval. For instance, it is generally beneficial to utilize the ambiguous unlabeled documents to learn a more robust classifier for text categorization under the semi-supervised learning setting. To handle general data ambiguities, we present a unified kernel learning framework named Input-Output Kernel Learning (IOKL). Based on our framework, we further propose a novel soft margin group sparse Multiple Kernel Learning (MKL) formulation by introducing a group kernel slack variable to each group of base input-output kernels. Moreover, an efficient block-wise coordinate descent algorithm with an analytical solution for the kernel combination coefficients is developed to solve the proposed formulation. We conduct comprehensive experiments on benchmark datasets for both semi-supervised learning and multiple instance learning tasks, and also apply our IOKL framework to a computer vision application called text-based image retrieval on the NUS-WIDE dataset. Promising results demonstrate the effectiveness of our proposed IOKL framework.

Feature selection with specific multivariate performance measures is the key to the success of many applications, such as information retrieval and bioinformatics. The existing feature selection methods are usually designed for classification error. In this paper, we present a unified feature selection framework for general loss functions. In particular, we study the novel feature selection paradigm by optimizing multivariate performance measures. The resultant formulation is a challenging problem for high-dimensional data. Hence, a two-layer cutting plane algorithm is proposed to solve this problem, and the convergence is presented. Extensive experiments on large-scale and high-dimensional real world datasets show that the proposed method outperforms l1-SVM and SVM-RFE when choosing a small subset of features, and achieves significantly improved performances over SVMperfin terms of F1-score.

Domain Adaptation (DA) methods are usually carried out by means of simply reducing the marginal distribution differences between the source and target domains, and subsequently using the resultant trained classifier, namely source classifier, for use in the target domain. However, in many cases, the true predictive distributions of the source and target domains can be vastly different especially when their class distributions are skewed, causing the issues of sample selection bias in DA. Hence, DA methods which leverage the source labeled data may suffer from poor generalization in the target domain, resulting in negative transfer. In addition, we observed that many DA methods use either a source classifier or a linear combination of source classifiers with a fixed weighting for predicting the target unlabeled data. Essentially, the labels of the target unlabeled data are spanned by the prediction of these source classifiers. Motivated by these observations, in this paper, we propose to construct many source classifiers of diverse biases and learn the weight for each source classifier by directly minimizing the structural risk defined on the target unlabeled data so as to heal the possible sample selection bias. Since the weights are learned by maximizing the margin of separation between opposite classes on the target unlabeled data, the proposed method is established here as Maximal Margin Target Label Learning (MMTLL), which is in a form of Multiple Kernel Learning problem with many label kernels. Extensive experimental studies of MMTLL against several state-of-the-art methods on the Sentiment and Newsgroups datasets with various imbalanced class settings showed that MMTLL exhibited robust accuracies on all the settings considered and was resilient to negative transfer, in contrast to other counterpart methods which suffered significantly in prediction accuracy.

Dataset shift from the training data in a source domain to the data in a target domain poses a great challenge for many statistical learning methods. Most algorithms can be viewed as exploiting only the first-order statistics, namely, the empirical mean discrepancy to evaluate the distribution gap. Intuitively, considering only the empirical mean may not be statistically efficient. In this paper, we propose a non-parametric distance metric with a good property which jointly considers the empirical mean (Location) and sample covariance (Scatter) difference. More specifically, we propose an improved symmetric Stein's loss function which combines the mean and covariance discrepancy into a unified Bregman matrix divergence of which Jensen-Shannon divergence between normal distributions is a particular case. Our target is to find a good feature representation which can reduce the distribution gap between different domains, at the same time, ensure that the new derived representation can encode most discriminative components with respect to the label information. We have conducted extensive experiments on several document classification datasets to demonstrate the effectiveness of our proposed method.

One common predictive modeling challenge occurs in text mining problems is that the training data and the operational (testing) data are drawn from different underlying distributions. This poses a great difficulty for many statistical learning methods. However, when the distribution in the source domain and the target domain are not identical but related, there may exist a shared concept space to preserve the relation. Consequently a good feature representation can encode this concept space and minimize the distribution gap. To formalize this intuition, we propose a domain adaptation method that parameterizes this concept space by linear transformation under which we explicitly minimize the distribution difference between the source domain with sufficient labeled data and target domains with only unlabeled data, while at the same time minimizing the empirical loss on the labeled data in the source domain. Another characteristic of our method is its capability for considering multiple classes and their interactions simultaneously. We have conducted extensive experiments on two common text mining problems, namely, information extraction and document classification to demonstrate the effectiveness of our proposed method. Copyright 2009 ACM.

We propose a semi-supervised framework incorporating feature mapping with multiclass classification. By learning multiple classification tasks simultaneously, this framework can learn the latent feature space effectively for both labeled and unlabeled data. The knowledge in the transformed space can be transferred not only between the labeled and unlabeled data, but also across multiple classes, so as to improve the classification performance given a small amount of labeled data. We show that this problem is equivalent to a sequential convex optimization problem by applying constraint concave-convex procedure (CCCP). Efficient algorithm with theoretical guarantee is proposed and computational issue is investigated. Extensive experiments have been conducted to demonstrate the effectiveness of our proposed framework.

Maximum margin discriminant analysis (MMDA) was proposed that uses the margin idea for feature extraction. It often outperforms traditional methods like kernel principal component analysis (KPCA) and kernel Fisher discriminant analysis (KFD). However, as in other kernel methods, its time complexity is cubic in the number of training points m, and is thus computationally inefficient on massive data sets. In this paper, we propose an (1 + ε) 2-approximation algorithm for obtaining the MMDA features by extending the core vector machines. The resultant time complexity is only linear in m, while its space complexity is independent of m. Extensive comparisons with the original MMDA, KPCA, and KFD on a number of large data sets show that the proposed feature extractor can improve classification accuracy, and is also faster than these kernel-based methods by more than an order of magnitude.