Diffusion models (DMs) have recently gained significant interest for their exceptional potential in recommendation tasks. This stems primarily from their prominent capability in distilling, modeling, and generating comprehensive user preferences. However, previous work fails to examine DMs in recommendation tasks through a rigorous lens. In this paper, we first experimentally investigate the completeness of recommender models from a thermodynamic view. We reveal that existing DM-based recommender models operate by maximizing the energy, while classic recommender models operate by reducing the entropy. Based on this finding, we propose a minimalistic diffusion framework that incorporates both factors via the maximization of Helmholtz free energy. Meanwhile, to foster the optimization, our reverse process is armed with a well-designed denoiser to maintain the inherent anisotropy, which measures the user-item cross-correlation in the context of bipartite graphs. Finally, we adopt an Acceptance-Rejection Gumbel Sampling Process (AR-GSP) to prioritize the far-outnumbered unobserved interactions for model robustness. AR-GSP integrates an acceptance-rejection sampling to ensure high-quality hard negative samples for general recommendation tasks, and a timestep-dependent Gumbel Softmax to handle an adaptive sampling strategy for diffusion models. Theoretical analyses and extensive experiments demonstrate that our proposed framework has distinct superiority over baselines in terms of accuracy and efficiency.

Despite their success in Collaborative Filtering (CF), Graph Convolutional Networks (GCNs) are often viewed as Low-pass Graph Filters (LGFs) with task-specific supervision, while the influence of the underlying graph's spectral properties on LGF performance remains underexplored. Our analysis reveals that the performance of LGFs is strongly affected by algebraic connectivity. When connectivity is strong, LGFs tend to perform well; when it is weak, their effectiveness diminishes noticeably. This spectral sensitivity highlights an important limitation of existing models. To address this limitation, we propose Graph Booster, a learnable module that adaptively improves graph connectivity by reweighting edges. Unlike heuristic preprocessing, Graph Booster identifies bottleneck edges via spectral embeddings and adjusts their weights with a monotonic network guided by a lightweight graph connectivity regularizer. Integrated into LightGCN framework, our model BoostGCN achieves improvements over state-of-the-art methods, underscoring the significance of algebraic connectivity for graph-based CF.

Temporal graph representation learning seeks to capture the intrinsic evolution of nodes in temporal graphs for various applications. While existing models primarily learn node representations by aggregating temporal information from historical interactions of nodes, they often overlook the critical structural impacts arising from these interactions. To address this issue, we propose a Structure-aware model for Temporal Graph representation learning (STG), a framework that explicitly incorporates the impacts of evolving structural roles to enhance the learned node representations. Specifically, STG encodes distinct structural roles of nodes by extracting both single-unit and multi-unit interaction patterns. These roles are then transformed into the Fourier domain for a deeper analysis of the complex structural dynamics. To capture the structural impacts on future node interactions, we design a dynamic filter to process these roles. The filter is equipped with a personalized weight coefficient generator to perform the interaction-specific analysis. Finally, we employ a mixer to collaboratively aggregate the temporal and structural information to obtain structure-aware temporal node representations. Extensive experiments conducted on several real-world temporal graph datasets demonstrate the superior performance of our model in dynamic link prediction tasks under both transductive and inductive settings.

The structural heterogeneity of user-item interaction graphs poses a fundamental challenge for graph-based recommender systems. While Graph Convolutional Networks (GCNs) have achieved remarkable success in collaborative filtering, their uniform low-pass filtering nature often fails to accommodate the varying spectral needs of nodes with different local structures, resulting in suboptimal performance. To address this issue, we propose a Structurally Sensitive Adaptive Graph Filter, dubbed as SSAGF, a novel framework that enables structure-aware filtering on user-item graphs. SSAGF first clusters nodes based on local structural properties, then learns customized filters per group by reinterpreting the convolutional depth in GCNs. This adaptive mechanism ensures that nodes with distinct structural roles are treated appropriately, enhancing both accuracy and fairness without significantly increasing model complexity. To further improve scalability, SSAGF avoids costly eigenvalue decompositions by approximating spectral filters through Maclaurin series expansion, transforming the convolution into a pooling-like operation over standard GCN outputs. Extensive experiments on four benchmark datasets demonstrate that SSAGF consistently outperforms competitive baselines, especially in scenarios with high structural heterogeneity, offering a principled and efficient solution for structure-aware recommendation.

In graph-based multimedia recommendation, accurately modeling item-item semantic similarity is crucial for constructing high-quality semantic structures. However, multimodal content often exhibits semantic inconsistencies across modalities, resulting in noisy or misleading similarity signals. We refer to this as modality mismatching, where unaligned representations, such as an image conveying semantics unrelated to its accompanying text, undermine the reliability of feature-based similarity estimation. Importantly, modality consistency is context sensitive, varying with the underlying semantic environment in which modalities are interpreted. This highlights the necessity of jointly modeling modality reliability and contextual semantics. To address this challenge, we propose RGSLMRec, a robust graph structure learning framework that models and exploits the semantic reliability of multimodal features under diverse contexts. At its core, RGSLMRec builds on the invariant learning paradigm and introduces two key innovations: (i) it simulates multiple perturbed semantic environments and employs environment-specific monotonic networks to estimate reliability; and (ii) it adopts a risk-invariant objective based on Variance Risk Extrapolation to enforce the learning of invariant reliability across environments. On top of this, (iii) RGSLMRec constructs reliability-guided item-item graphs and captures collaborative and semantic signals via a hybrid early-late fusion strategy. Extensive experiments on several real-world datasets and additional synthetically perturbed datasets demonstrate that RGSLMRec not only outperforms strong baselines but also exhibits superior robustness to modality mismatching.

Graph Neural Networks (GNNs) have shown promising performance in various tasks on graph-structured data. However, recent studies demonstrate that GNNs are vulnerable to adversarial attacks. In this paper, we study a realistic graph adversarial attack scenario: node injection attack (NIA). In the NIA setting, malicious nodes will be injected into the original graph instead of modifying the existing edge or node features. We present an analysis of the node fragility of GNNs under the NIA setting, based on which we propose GraphDC, which has two stages Detecting and Confusing. Specifically, GraphDC first detects the node fragility in the graph and proposes the neighbor-based and logits-based fragility measurement to select the original node connected to the injected node. Then, to confuse the decision boundary, GraphDC designs a contrastive adversarial loss to optimize the injected node features, it aims to mislead the model into classifying original nodes into closely related but incorrect classes, thereby enhancing the effectiveness of adversarial attacks. Extensive experiments conducted on four datasets demonstrate the effectiveness and better performance compared with state-of-the-art baselines.

With the widespread adoption of online education platforms, an increasing number of students are gaining new knowledge through Massive Open Online Courses (MOOCs). Exercise recommendation have made strides toward improving student learning outcomes. However, existing methods not only struggle with high dropout rates but also fail to match the diverse learning pace of students. They frequently face difficulties in adjusting to inactive students' learning patterns and in accommodating individualized learning paces, resulting in limited accuracy and diversity in recommendations. To tackle these challenges, we propose Neural Re-ranking for Diversified Exercise Recommendation (in short, NR4DER). NR4DER first leverages the mLSTM model to improve the effectiveness of the exercise filter module. It then employs a sequence enhancement method to enhance the representation of inactive students, accurately matches students with exercises of appropriate difficulty. Finally, it utilizes neural re-ranking to generate diverse recommendation lists based on individual students' learning histories. Extensive experimental results indicate that NR4DER significantly outperforms existing methods across multiple real-world datasets and effectively caters to the diverse learning pace of students.

Contemporary datasets sourced from the web often adopt a multiview format, collecting data from diverse sources, domains, or modules.Existing methodologies employed to analyze such datasets frequently overlook or inaccurately allocate the view-weights, pivotal metrics reflecting each view's significance.This work introduces EVA-MVC, a simple yet effective algorithm designed for Equitable View-weight Allocation (EVA) seamlessly integrated with arbitrary Multi-view Clustering (MVC) methods.Within the EVA module, we establish theoretical connections between view supplementarity and Multi-view Subspace Learning (MSL), leading to the partition of views into View Communities (VCs) based on these foundational principles.These VCs exhibit internal supplementarity similarities, facilitating Equitable View-weights Allocation through VCspecific MSL.The proposed EVA process precedes and operates independently of traditional or SOTA MVC approaches, requiring no additional processing or specialized design, making it an ideal preprocessing step for MVC applications.Through comprehensive evaluations across diverse multi-view datasets, our findings reveal that our EVA significantly enhances the effectiveness of mainstream MVC frameworks, resulting in a notable performance improvement.

In the domain of Multi-view Subspace Clustering (MSC) in Latent Embedding Space (LES), existing methods aim to capture and leverage critical multi-view information by mapping it into a low-dimensional LES. However, several aspects can be further improved: (i) Fusion Strategy: Existing methods adopt either early fusion or late fusion to integrate multi-view information, limiting the effectiveness of the fusion. (ii) Diversity: Current methods often overlook the inherent diversity in the multi-view data by focusing on a single LES. (iii) Efficiency: LES-based methods exhibit high computational complexity, with cubic time and quadratic space requirements based on the number of samples. To address these issues, we propose a novel framework called MSC-DOLES (Multi-view Subspace Clustering in Diverse Orthogonal Latent Embedding Spaces), a novel framework designed to tackle these challenges. MSC-DOLES incorporates a two-stage fusion approach that generates and learns from multiple LES to maximize cross-view diversity. Orthogonality constraints on individual LES ensure view-internal diversity, resulting in a set of Diverse Orthogonal Latent Embedding Spaces (DOLES). The DOLES are then fused into a consensus anchor graph using learnable anchors. The final clustering is induced by partitioning the obtained graph without pre-processing. We develop an eight-step optimization algorithm for MSC-DOLES, which exhibits nearly linear time and space complexities relative to the number of samples. Extensive experiments demonstrate the superiority of MSC-DOLES over state-of-the-art methods.

Social recommendation systems leverage the social relations among users to deal with the inherent cold-start problem in user-item interactions. However, previous models only treat the social graph as the static auxiliary to the user-item interaction graph, rather than dig out the hidden essentials and optimize them for better recommendations. Thus, the potential of social influence is still under-explored. In this paper, we will fill this gap by proposing a novel model for social influence learning to derive the essential influence patterns within the user relationships. Our model views the social influence from the perspectives of (1) the diversity of neighborhood's influence on the users, (2) the disentanglement of neighborhood's influence on the users, and (3) the exploration of underlying implicit social influence. To this end, we first employ a novel layerwise graph-enhanced variational autoencoder for the reconstruction of neighborhoods' representations, which aims to learn the pattern of social influence as well as simulate the social profile of each user for overcoming the sparsity issue in social relation data. Meanwhile, we introduce a layerwise graph attentive network for capturing the most influential scope of neighborhood. Finally, we adopt a dual sampling process to generate new social relations for enhancing the social recommendation. Extensive experiments have been conducted on three widely-used benchmark datasets, verifying the superiority of our proposed model compared with the representative approaches.

The rapid development of heterogeneous networks has proposed new challenges to the long-standing link prediction problem. Existing models trained on the verified edge samples from different types usually learn type-specific knowledge, and their type-specific predictions may be contradictory for unverified edge samples with uncertain types. This challenge is termed edge-type disturbance in link prediction in heterogeneous networks. To address this challenge, we develop a disturbance-resilient prediction method ( DRPM ) comprising a structural characterizer, a type differentiator, and a resilient predictor. The structural characterizer is responsible for learning edge representations for link prediction. Concurrently, the type differentiator distinguishes type-specific edge representations to generate diverse type experts while maximizing their link prediction performances on specific types. Furthermore, the resilient predictor evaluates the reliability weights of different type experts to develop a resilient prediction mechanism to aggregate discriminable predictions. Extensive experiments conducted on various real-world datasets demonstrate the importance of the explainable introduction of the edge-type disturbance and the superiority of DRPM over state-of-the-art methods.

In recent years, graph embedding techniques have exhibited great potential for various downstream tasks, which can leverage both topological structures and the temporal dependencies of nodes in their representations, leading to remarkable achievements. However, the multi-role nature of nodes during their temporally interacting is neglected. To tackle this problem, we propose a novel model, Temporal graph Multi-Aspect Embedding (TMAE), to capture the latent multi-aspect characteristics of nodes in temporal graphs, thereby enhancing the quality of graph embeddings. Specifically, we propose to learn the aspect embeddings of nodes and their weights at different timestamps separately for a better adaptation. In contrast to the conventional fixed aspect number assumption, a Hierarchical Dirichlet Process-based approach is employed to dynamically determine the weight of aspects for nodes at different times. Through this framework, we effectively learn the multi-aspect information through Time-reversed Temporal Walks (TTWs). Extensive experiments performed across eight publicly accessible datasets have demonstrated the significant improvements of the proposed TMAE model over state-of-the-art algorithms by taking advantage of the multi-aspect nature.

Graph Neural Networks (GNNs) have achieved remarkable success in graph-based tasks. However, learning unbiased node representations under class-imbalanced training data remains challenging. Existing solutions may face overfitting due to extensive reuse of those limited labeled data in minority classes. Furthermore, many works address the class-imbalanced issue based on the embeddings generated from the biased GNNs, which make models intrinsically biased towards majority classes. In this paper, we propose a novel data augmentation strategy GraphGLS for semi-supervised class-imbalanced node classification, which aims to select informative unlabeled nodes to augment minority classes with consideration of both global and local information. Specifically, we first design a Global Selection module to learn global information (pseudo-labels) for unlabeled nodes and then select potential ones from them for minority classes. The Local Selection module further conducts filtering over those potential nodes by comparing their neighbor distributions with minority classes. To achieve this, we further design a neighbor distribution auto-encoder to learn a robust node-level neighbor distribution for each node. Then, we define class-level neighbor distribution to capture the overall neighbor characteristics of nodes within the same class. We conduct extensive experiments on multiple datasets, and the results demonstrate the superiority of GraphGLS over state-of-the-art baselines.

Feature learning is a crucial phase machine learning [1] – [3] . How to obtain appropriate features distribution without any background is still a hard problem in machine learning. In this paper, we present a novel unsupervised feature learning architecture (see Fig. 1 ), which consists of a multi-clustering integration module and a variant of RBM termed multi-clustering integration RBM (MIRBM). In the multi-clustering integration module, we choose three clusterers to obtain three different global clustering partitions (CPs). Then, an unanimous voting strategy is used to generate the local clustering partition (LCP) of visible layer data. Hence, the LCP only has partial visible layer data. The novel MIRBM model is a core feature encoding part of the proposed unsupervised feature learning architecture. The novelty of it is that the LCP as an unsupervised guidance is integrated into the CD 1 learning to guide the distribution of the hidden layer features. For the instance in the same LCP cluster, the hidden and reconstructed hidden layer features of the MIRBM model in the proposed architecture tend to constrict together in the training process. Meanwhile, each LCP center tends to disperse from each other as much as possible in the hidden and reconstructed hidden layer during training. This work has three main contributions: 1) A novel unsupervised feature learning architecture is proposed, which consists of a multi-clustering integration module and an MIRBM model. 2) In the multi-clustering integration module of the proposed architecture, three unsupervised algorithms are employed to obtain three different global CPs without any background knowledge or label. 3) The MIRBM model in the proposed architecture uses the LCP as an unsupervised guidance to guide the distribution of the hidden layer features by integrating the LCP into the CD 1 learning.

THE popularity of location-aware devices such as smart phones makes users freely share their activities through various location-based social networks (LBSNs), such as Foursquare and Yelp. A large amount of user-contributed data enable to develop effective point-of-interest (POI) recommender systems. It not only guides users to explore more interesting attractions, but also helps the location service providers deliver targeted advertising. Now most of existing studies focus on recommending POIs in the same city or region, named as traditional POI recommender systems. However, they fail to deal with the increasingly popular case: users travel to new cities to explore more attractions. This raises the problem that how we shall recommend POIs in a target city to a new visitor based on her/his check-in records in source cities. We refer to this problem as crossing-city POI recommendations. Compared with traditional POI recommender systems, crossing-city POI recommender systems are more challenging due to the following aspects:

Abstract User-generated content is daily produced in social media, as such user interest summarization is critical to distill salient information from massive information for recommendation tasks. While the interested messages (e.g., tags or posts) from a single user are usually sparse becoming a bottleneck for existing methods, we propose a neural inference method (NIGraphNet) by mining user social interest for item recommendation. It can unearth user latent topics combined with user relation learning. Specifically, we exploit a neural variational inference approach to learn the distributions between user interests and hidden topics. (We denote it as interest-topic distributions in the following.) Then, we adopt a unified graph-based training loss that jointly learns the hidden topics and user relations for item recommendation. Experiments on two datasets collected from well-known social media platforms demonstrate the superior performance of our model in the tasks of user interest summarization and item recommendation. Further discussions also show that exploiting the latent topic representations and user relations is conducive to the user’s automatic language understanding.

Accurate traffic prediction is one of the most important techniques in building a smart city. Many works, especially deep learning models, have made great progress in traffic prediction based on rich historical data. However, many cities still suffer from the problem of data scarcity in many aspects. Some works use transfer learning to solve this kind of problem, but what and how to transfer is still an important problem. In this article, we propose a novel Cross-city Multi-Granular Adaptive Transfer Learning method named MGAT for traffic prediction with only a few data in the target city. We first use the meta-learning algorithm to train the model on multiple source cities to get a good initialization. And at the same time, the multi-granular regional characteristics of each source city will be obtained based on our model structure. Then we design an Adaptive Transfer module mainly composed of Spatial-Attention and Multi-head Attention mechanism to automatically select the most appropriate features from the multi-granular features trained from multiple source cities, to achieve the best transfer effect. We conduct extensive experiments on two kinds of real-world traffic datasets cross several cities. Experimental results with other state-of-the-art models demonstrate the effectiveness of the proposed model.

Despite the massive surge of evolving social network analysis in popularity, existing research usually represent the observed social interactions among individuals as completely credible edges. However, due to information inaccuracy, individual non-response and dropout, and sampling biases in observations, the evolving noisy social network that coexists true edges and spurious edges is pervasive in actual applications, where the ignoration of credibility otherness of observed edges could lead to the wrong estimates of social properties and misleading conclusions. To discover credible edge information to shape correct social interactions among individuals, we propose a universal and explainable multiple-neighbor evolutional filtering method (MEFM) to evaluate how credible of observed edges to ‘truly’ exist in the evolving noisy social network.MEFMconsists of an evolutional extractor and a filtering evaluator. To resist the noisy disturbance, the evolutional extractor exploits the evolutional states of edges from the perspective of evolution mechanisms within multiple-neighbor ranges, which applies different link prediction algorithms to fit the evolution mechanism in the formation of each edge. Further, the filtering evaluator reconstructs Kalman filter to predict and refine the evolutional states of edges based on their evolving local structures. As a result,MEFMcombines the evolutional extractor and the filtering evaluator to analyze the evolutional fluctuations of the observed edges to evaluate their credibility. Extensive experiments on real-world datasets demonstrate that our proposedMEFMcan effectively and reasonably evaluate edge credibility in evolving noisy social networks.

As travel efficiency matters to the work productivity of cities, shortening passengers' travel time for metros is therefore a pressing need. To this end, we study a strategy by dynamically scheduling dwell time for trains. Developing such a strategy is challenging because of three aspects: 1) Optimizing the average travel time of passengers needs to properly balance passengers' waiting time at platforms and journey time on trains, as well as considering long-term impacts; 2) Capturing dynamic spatio-temporal (ST) correlations of incoming passengers for metro stations is difficult; and 3) For each train, the dwell time scheduling is affected by other trains, which is hard to measure. To tackle these challenges, we propose a novel deep neural network, entitled AutoDwell. Specifically, AutoDwell optimizes the long-term rewards of dwell time settings in terms of passengers' waiting and journey time by a reinforcement learning framework. Next, AutoDwell employs gated recurrent units and graph attention networks to extract the ST correlations of the passenger flows among metro stations. Moreover, attention mechanisms are leveraged in AutoDwell for capturing the interactions between the trains. Extensive experiments on two real-world datasets demonstrate the superior performance of AutoDwell over several baselines, capable of saving passengers' travel time significantly.

Spectral Clustering (SC) is an effective clustering method for its excellent performance in partitioning non-linearly distributed data. On the other hand, Ensemble Clustering (EC), a different clustering technology, can promote cluster quality by ensembling the results of base clusterings. In this work, we concentrate on an EC framework that utilizes SC as the base method. Nevertheless, SC suffers from scalability due to its high computational complexity in constructing the Laplacian graph and computing the corresponding eigendecomposition. In the past decades, many efforts have been made to it. However, SC suffers from the scalability issue in processing extensive data, especially in web-scale scenarios. Additionally, EC requires multiple clustering results as the ensemble bases, which further aggravates resource consumption. To address this issue, LiteWSEC, a simple yet efficient Lightweight Framework for Web-scale Spectral Ensemble Clustering, is proposed to cluster web-scale data with limited resource requirements. It adopts the Web-scale Spectral Clustering (WSC) as the base method, which has minimal space overhead without computing overall embedding explicitly. LiteWSEC is highly flexible in the memory requirement, which is adaptive to the available resource. It can partition web-scale data (e.g.,$n $= 8,000 k) in an resource-limited host (e.g., memory is restricted to 1 GB). Experiments on real-world, large-scale, and web-scale datasets demonstrate both the efficiency and effectiveness of LiteWSEC over state-of-the-art SC and EC methods.

Graph embedding is regarded as one of the most advanced techniques for graph data analyses due to its significant performance. However, the majority of existing works only focus on static graphs while ignoring the ubiquitous dynamic graphs. In fact, the temporal evolution of edges in a dynamic graph sets a harsh challenge for the traditional embedding algorithms. To solve the problem, in this paper we propose a Dynamic Graph Multi-Aspect Embedding (DGMAE) to automatically learn the proper number of aspects and their distributions in each temporal duration based on a distance dependent Chinese Restaurant Process. The proposed method can encode the inherent property of varying interactions among nodes along the time and present different aspect-influences to nodes embedding. Our extensive experiments on several public datasets show the performance improvement over state-of-the-art works.

User representation learning plays an essential role in Internet applications, such as recommender systems. Though developing a universal embedding for users is demanding, only few previous works are conducted in an unsupervised learning manner. The unsupervised method is however important as most of the user data is collected without specific labels. In this paper, we harness the unsupervised advantages of Variational Autoencoders (VAEs), to learn user representation from large-scale, high-dimensional, and multi-field data. We extend the traditional VAE by developing Field-aware VAE (FVAE) to model each feature field with an independent multinomial distribution. To reduce the complexity in training, we employ dynamic hash tables, a batched softmax function, and a feature sampling strategy to improve the efficiency of our method. We conduct experiments on multiple datasets, showing that the proposed FVAE significantly outperforms baselines on several tasks of data reconstruction and tag prediction. Moreover, we deploy the proposed method in real-world applications and conduct online A/B tests in a look-alike system. Results demonstrate that our method can effectively improve the quality of recommendation. To the best of our knowledge, it is the first time that the VAE-based user representation learning model is applied to real-world recommender systems.

The abundant sequential documents such as online archival, social media, and news feeds are streamingly updated, where each chunk of documents is incorporated with smoothly evolving yet dependent topics. Such digital texts have attracted extensive research on dynamic topic modeling to infer hidden evolving topics and their temporal dependencies. However, most of the existing approaches focus on single-topic-thread evolution and ignore the fact that a current topic may be coupled with multiple relevant prior topics. In addition, these approaches also incur the intractable inference problem when inferring latent parameters, resulting in a high computational cost and performance degradation. In this work, we assume that a current topic evolves from all prior topics with corresponding coupling weights, forming the multi-topic-thread evolution . Our method models the dependencies between evolving topics and thoroughly encodes their complex multi-couplings across time steps. To conquer the intractable inference challenge, a new solution with a set of novel data augmentation techniques is proposed, which successfully discomposes the multi-couplings between evolving topics. A fully conjugate model is thus obtained to guarantee the effectiveness and efficiency of the inference technique. A novel Gibbs sampler with a backward–forward filter algorithm efficiently learns latent time-evolving parameters in a closed-form. In addition, the latent Indian Buffet Process compound distribution is exploited to automatically infer the overall topic number and customize the sparse topic proportions for each sequential document without bias. The proposed method is evaluated on both synthetic and real-world datasets against the competitive baselines, demonstrating its superiority over the baselines in terms of the low per-word perplexity, high coherent topics, and better document time prediction.

In this paper, we present a novel unsupervised feature learning architecture, which consists of a multi-clustering integration module and a variant of RBM termed multi-clustering integration RBM (MIRBM). In the multi-clustering integration module, we apply three clusterers (K-means, affinity propagation and spectral clustering algorithms) to obtain three different clustering partitions (CPs) without any background knowledge or label. Then, an unanimous voting strategy is used to generate a local clustering partition (LCP). The novel MIRBM model is a core feature encoding part of the proposed unsupervised feature learning architecture. The novelty of it is that the LCP as an unsupervised guidance is integrated into one step contrastive divergence (${\mathtt{{CD}}}_{1}$) learning to guide the distribution of the hidden layer features. For the instance in the same LCP cluster, the hidden and reconstructed hidden layer features of the MIRBM model in the proposed architecture tend to constrict together in the training process. Meanwhile, each LCP center tends to disperse from each other as much as possible in the hidden and reconstructed hidden layer during training. The experiments demonstrate that the proposed unsupervised feature learning architecture has more powerful feature representation and generalization capability than the state-of-the-art models for clustering tasks in the Microsoft Research Asia Multimedia (MSRA-MM)2.0 dataset.

With the popularity of location-aware devices (e.g., smart phones), large amounts of location-based social media data such as check-ins are generated. This stimulates plenty of studies for POI recommendations by applying machine learning techniques. However, most of the existing studies focus on POI recommendations in the same city or region, and fail to recommend POIs for users when they travel to a new city. In this paper, we propose a novel deep neural network, named as ST-TransRec, for crossing-city POI recommendations. It integrates the deep neural network, transfer learning technique, and density-based resampling method into a unified framework. In this model, the deep neural network is used to capture users’ preferences for POIs and learn the embeddings of POIs. Besides, the transfer learning technique is employed to bridge the gap between cities that results from the city-dependent features. As the distributions over POIs are imbalanced, we design a density-based spatial resampling model which enables POIs to be well matched across cities. We conduct extensive experiments on two real-world datasets. The experimental results show the advantages of ST-TransRec over the state-of-the-art methods for crossing-city POI recommendations.

Node classification is a central task in graph data analysis. Scarce or even no labeled data of emerging classes is a big challenge for existing methods. A natural question arises: can we classify the nodes from those classes that have never been seen?

The online event discovery in social media based documents is useful, such as for disaster recognition and intervention. However, the diverse events incrementally identified from social media streams remain accumulated, ad hoc, and unstructured. They cannot assist users in digesting the tremendous amount of information and finding their interested events. Further, most of the existing work is challenged by jointly identifying incremental events and dynamically organizing them in an adaptive hierarchy. To address these problems, this article proposes d ynamic and h ierarchical C ategorization M odeling (dhCM) for social media stream. Instead of manually dividing the timeframe, a multimodal event miner exploits a density estimation technique to continuously capture the temporal influence between documents and incrementally identify online events in textual, temporal, and spatial spaces. At the same time, an adaptive categorization hierarchy is formed to automatically organize the documents into proper categories at multiple levels of granularities. In a nonparametric manner, dhCM accommodates the increasing complexity of data streams with automatically growing the categorization hierarchy over adaptive growth. A sequential Monte Carlo algorithm is used for the online inference of the dhCM parameters. Extensive experiments show that dhCM outperforms the state-of-the-art models in terms of term coherence, category abstraction and specialization, hierarchical affinity, and event categorization and discovery accuracy.

While scientific collaboration is critical for a scholar, some collaborators can be more significant than others, e.g., lifetime collaborators. It has been shown that lifetime collaborators are more influential on a scholar’s academic performance. However, little research has been done on investigating predicting such special relationships in academic networks. To this end, we propose Scholar2vec, a novel neural network embedding for representing scholar profiles. First, our approach creates scholars’ research interest vector from textual information, such as demographics, research, and influence. After bridging research interests with a collaboration network, vector representations of scholars can be gained with graph learning. Meanwhile, since scholars are occupied with various attributes, we propose to incorporate four types of scholar attributes for learning scholar vectors. Finally, the early-stage similarity sequence based on Scholar2vec is used to predict lifetime collaborators with machine learning methods. Extensive experiments on two real-world datasets show that Scholar2vec outperforms state-of-the-art methods in lifetime collaborator prediction. Our work presents a new way to measure the similarity between two scholars by vector representation, which tackles the knowledge between network embedding and academic relationship mining.

Finding both efficient and effective quantitative representations for scholars in scientific digital libraries has been a focal point of research. The unprecedented amounts of scholarly datasets, combined with contemporary machine learning and big data techniques, have enabled intelligent and automatic profiling of scholars from this vast and ever-increasing pool of scholarly data. Meanwhile, recent advance in network embedding techniques enables us to mitigate the challenges of large scale and sparsity of academic collaboration networks. In real-world academic social networks, scholars are accompanied with various attributes or features, such as co-authorship and publication records, which result in attributed collaboration networks. It has been observed that both network topology and scholar attributes are important in academic relationship mining. However, previous studies mainly focus on network topology, whereas scholar attributes are overlooked. Moreover, the influence of different scholar attributes are unclear. To bridge this gap, in this work, we present a novel framework of Attributed Collaboration Network Embedding (ACNE) for academic relationship mining. ACNE extracts four types of scholar attributes based on the proposed scholar profiling model, including demographics, research, influence, and sociability. ACNE can learn a low-dimensional representation of scholars considering both scholar attributes and network topology simultaneously. We demonstrate the effectiveness and potentials of ACNE in academic relationship mining by performing collaborator recommendation on two real-world datasets and the contribution and importance of each scholar attribute on scientific collaborator recommendation is investigated. Our work may shed light on academic relationship mining by taking advantage of attributed collaboration network embedding.

Recently, dynamic social network research has attracted a great amount of attention, especially in the area of anomaly analysis that analyzes the anomalous change in the evolution of dynamic social networks. However, most of the current research focused on anomaly analysis of the macro representation of dynamic social networks and failed to analyze the nodes that have anomalous structural changes at a micro level. To identify and evaluate anomalous structural change-based nodes in generalized dynamic social networks that only have limited structural information, this research considers undirected and unweighted graphs and develops a multiple-neighbor superposition similarity method ( ), which mainly consists of a multiple-neighbor range algorithm ( ) and a superposition similarity fluctuation algorithm ( ). introduces observation nodes, characterizes the structural similarities of nodes within multiple-neighbor ranges, and proposes a new multiple-neighbor similarity index on the basis of extensional similarity indices. Subsequently, maximally reflects the structural change of each node, using a new superposition similarity fluctuation index from the perspective of diverse multiple-neighbor similarities. As a result, based on and , not only identifies anomalous structural change-based nodes by detecting the anomalous structural changes of nodes but also evaluates their anomalous degrees by quantifying these changes. Results obtained by comparing with state-of-the-art methods via extensive experiments show that can accurately identify anomalous structural change-based nodes and evaluate their anomalous degrees well.

Many achievements have been made by studying how to visualize large-scale and high-dimensional data in typically 2D or 3D space. Normally, such a process is performed through a non-parametric (unsupervised) approach which is limited in handling the unseen data. In this work, we study the parametric (supervised) model which is capable to learn a mapping between high-dimensional data space Rd and low-dimensional latent space Rs with similarity structure in Rd preserved where s l d. The GNNVis is proposed, a framework that applies the idea of Graph Neural Networks (GNNs) to the parametric learning process and the learned mapping serves as a Visualizer (Vis) to compute the low-dimensional embeddings of unseen data online. In our framework, the features of data nodes, as well as the (hidden) information of their neighbors are fused to conduct Dimension Reduction. To the best of our knowledge, none of the existing visualization works have studied how to combine such information into the learning representation. Moreover, the learning process of GNNVis is designed as an end-to-end manner and can easily be extended to arbitrary Dimension Reduction methods if the corresponding objective function is given. Based on GNNVis, several typical dimension reduction methods t-SNE, LargeVis, and UMAP are investigated. As a parametric framework, GNNVis is an inherently efficient Visualizer capable of computing the embeddings of large-scale unseen data. To guarantee its scalability in the Training Stage, a novel training strategy with Subgraph Negative Sampling (SNS) is conducted to reduce the corresponding cost. Experimental results in real datasets demonstrate the advantages of GNNVis. The visualization quality of GNNVis outperforms the state-of-the-art parametric models, and is comparable to that of the non-parametric models.

Ride-sharing (RS) has great values in saving energy and alleviating traffic pressure. In this paper, we propose a new ride-sharing model, where each driver requires that the shared route percentage (SRP, the ratio of the shared route's distance to the driver's total traveled distance) exceeds her expected rate (e.g., 0.8) when sharing with a rider. We consider two variants of this problem. The first considers multiple drivers and multiple riders, and aims to compute a set of driver-rider pairs to maximize the overall SRP. We model this problem as the maximum weighted bigraph matching problem. We propose an effective exact algorithm, and an efficient approximate solution with error-bound guarantee. The second considers multiple drivers and a single rider and aims to find the top-k drivers for the rider with the largest SRP. We devise pruning techniques and propose a best-first algorithm to progressively selects drivers with high probability to be in the top-k results.

Ride-sharing (RS) has great values in saving energy and alleviating traffic pressure. Existing studies can be improved for better efficiency. Therefore, we propose a new ride-sharing model, where each driver has a requirement that if the driver shares a ride with a rider, the shared route percentage (i.e., the ratio of the shared route's distance to the driver's total travel distance) exceeds an expectation rate of the driver, e.g., 0.8. We consider two variants of this problem. The first considers multiple drivers and multiple riders and aims to compute driver-rider pairs to maximize the overall shared route percentage (SRP). We model this problem as the maximum weighted bigraph matching problem, where the vertices are drivers and riders, edges are driver-rider pairs, and edge weights are driver-rider's SRP. However, it is rather expensive to compute the SRP values for large numbers of driver-rider pairs on road networks. To address this problem, we propose an efficient method to prune many unnecessary driver-rider pairs and avoid computing the SRP values for every pair. To improve the efficiency, we propose an approximate method with error bound guarantee. The basic idea is that we compute an upper bound and a lower bound for each driver-rider pair in constant time. Then, we estimate an upper bound and a lower bound of the graph matching. Next, we select some driver-rider pairs, compute their real shortest-route distance, and update the lower and upper bounds of the maximum graph matching. We repeat above steps until the ratio of the upper bound to the lower bound is not larger than a given approximate rate. The second considers multiple drivers and a single rider and aims to find the top-$k$drivers for the rider with the largest SRP. We first prune a large number of drivers that cannot meet the SRP requirements. Then, we propose a best-first algorithm that progressively selects the drivers with high probability to be in the top-$k$results and prunes the drivers that cannot be in the top-$k$results. Extensive experiments on real-world datasets demonstrate the superiority of our method.

Malicious phone call is a plague, in which unscrupulous salesmen or criminals make to acquire money illegally from the victims. As a result, there has been broad interest in deveploing systems to make the end-users vigilant when receiving such phone calls. Typically, these systems justify the phone numbers either by the crowd-generated blacklist or exploiting the features via machine learning techniques. However, the former is frail due to the rare and lazy crowd, while the later suffers from the scarcity of effective features. In this work, we propose a solution named DeMalC to address those problems by applying the machine learning algorithmm on a novel set of discriminative features. These features consist of properties and behaviors that are powerful enough to characterize phone numbers from different perspectives. We extensively evaluated our solution, i.e., DeMalC, using massive call detail records. The experimental result shows the effectiveness of our extracted features. Capable of achieving 91.86% overall accuracy and 79.34% F1-score on the detection of malicious phone numbers, the DeMalC has been deployed online and demonstrated to be a competitive solution for detecting malicious calls.

20th International Conference on Extending Database Technology, EDBT 2017, Venice, Italy, 21-24 March 2017

Crowdsourced query processing is an emerging processing technique that tackles computationally challenging problems by human intelligence. The basic idea is to decompose a computationally challenging problem into a set of human friendly microtasks (e.g., pairwise comparisons) that are distributed to and answered by the crowd. The solution of the problem is then computed (e.g., by aggregation) based on the crowdsourced answers to the microtasks. In this work, we attempt to revisit the crowdsourced processing of the top-k queries, aiming at (1) securing the quality of crowdsourced comparisons by a certain confidence level and (2) minimizing the total monetary cost. To secure the quality of each paired comparison, we employ two statistical tools, Student's t-distribution estimation and Stein's estimation, to estimate the confidence interval of the underlying mean value, which is then used to draw a conclusion to the comparison. Based on the pairwise comparison process, we attempt to minimize the monetary cost of the top-k processing within a Select-Partition-Rank framework. Our experiments, conducted on four real datasets, demonstrate that our stochastic method outperforms other existing top-k processing techniques by a visible difference.

Ranking techniques have been widely used in ubiquitous applications like recommendation, information retrieval, etc. For ranking computation hostile but human friendly items, crowdsourcing is considered as an emerging technique to process the ranking by human power. However, there is a lack of an easy-to-use toolkit for answering crowdsourced top- k query with minimal effort. In this work, we demonstrate an interactive programming toolkit that is a unified solution for answering the crowd-sourced top- k queries. The toolkit employs a new confidence-aware crowdsourced top- k algorithm, SPR. The whole progress of the algorithm is monitored and visualized to end users in a timely manner. Besides the visualized result and the statistics, the system also reports the estimation of the monetary cost and the breakdown of each phase. Based on the estimation, end users can strike a balance between the budget and the quality through the interface of this toolkit.

SimRank is a widely adopted similarity measure for objects modeled as nodes in a graph, based on the intuition that two objects are similar if they are referenced by similar objects. The recursive nature of SimRank definition makes it expensive to compute the similarity score even for a single pair of nodes. This defect limits the applications of SimRank. To speed up the computation, some existing works replace the original model with an approximate model to seek only rough solution of SimRank scores. In this work, we propose a novel solution for computing all-pair SimRank scores. In particular, we propose to convert SimRank to the problem of solving a linear system in matrix form, and further prove that the system is non-singular, diagonally dominate, and symmetric definite positive (for undirected graphs). Those features immediately lead to the adoption of Conjugate Gradient (CG) and Bi-Conjugate Gradient (BiCG) techniques for efficiently computing SimRank scores. As a result, a significant improvement on the convergence rate can be achieved; meanwhile, the sparsity of the adjacency matrix is not damaged all the time. Inspired by the existing common neighbor sharing strategy, we further reduce the computational complexity of the matrix multiplication and resolve the scalable issues. The experimental results show our proposed algorithms significantly outperform the state-of-the-art algorithms.

The availability of geographical and temporal tagged documents enables many location and time based mining tasks. Event discovery is one of such tasks, which is to identify interesting happenings in the geographical and temporal space. In recent years, several techniques have been proposed. However, no existing work has provided a nonparametric algorithm for detecting events in the joint space crossing geographical and temporal dimensions. Furthermore, though some prior works proposed to capture the periodicities of topics in their solutions, some restrictions on the temporal patterns are often placed and they usually ignore the spatial patterns of the topics. To break through such limitations, in this paper we propose a novel nonparametric model to identify events in the geographical and temporal space, where any recurrent patterns of events can be automatically captured. In our approach, parameters are automatically determined by exploiting a Dirichlet Process. To reduce the influence from noisy terms in the detection, we distinguish its event role from its background role using a Bernoulli model in the solution. Experimental results on three real world datasets show the proposed algorithm outperforms previous state-of-the-art approaches.

Mining the most influential k-location set finds k locations, traversed by the maximum number of unique trajectories, in a given spatial region. These influential locations are valuable for resource allocation applications, such as selecting charging stations for electric automobiles and suggesting locations for placing billboards. This problem is NP-hard and usually calls for an interactive mining processes, e.g., changing the spatial region and k, or removing some locations (from the results in the previous round) that are not eligible for an application according to the domain knowledge. Thus, efficiency is the major concern in addressing this problem. In this paper, we propose a system by using greedy heuristics to expedite the mining process. The greedy heuristic is efficient with performance guarantee. We evaluate the performance of our proposed system based on a taxi dataset of Tianjin, and provide a case study on selecting the locations for charging stations in Beijing.

With the rapid development of mobile Internet technology, Internet users are shifting from desktop to mobile devices. Modern mobile devices (e.g., smartphones and tablets) are equipped with GPS, which can help users to easily obtain their locations, and location-based services (LBS) have been widely deployed. LBS users are generating more and more spatio-textual data which contains both textual descriptions and geographical locations. In user-generated data, a spatiotextual entity may have different representations, possibly due to GPS deviations or typographical errors [6], [2], and it calls for effective methods to integrate the spatio-textual data from different data sources. A spatio-textual similarity join is an important operation in spatio-textual data integration, which, given two sets of spatio-textual objects, finds all similar pairs from the two sets, where the similarity can be quantified by combining spatial proximity and textual relevancy. There are many applications in spatio-textual similarity joins, e.g., user recommendation in location-based social networks, image duplication detection using spatio-textual tags, spatio-textual advertising, and location-based market analysis [6], [2]. For example, a house rental agency (e.g., rent.com) wants to perform a similarity join on the spatio-textual data of house requirements from renters and the data of house properties from owners. For another example, a startup company, e.g., Factual (factual.com), crawls spatio-textual records to generate points of interest (POIs). As the records are from multiple sources and may contain many duplicates, It needs to run similarity joins to remove the duplicates.

To the best of our knowledge, this is the first work that offers very low latency (0.1ms) per kNN query on 10-million-node networks on a commodity machine. This translates to a query throughput of 10,000 queries per second per commodity machine. Our experimental studies on large scale road networks show that our solutions are 1–3 orders of magnitudes faster than existing methods while our indexes are compact and can fit into main memory. In the future, we plan to further enhance the performance of kNN search with keywords.

With rapidly growing popularity, Location Based Services (LBS), e.g., Google Maps, Yahoo Local, WeChat, FourSquare, etc., started offering web-based search features that resemble a kNN query interface. Specifically, for a user-specified query location q, these websites extract from the objects in their backend database the top-k nearest neighbors to q and return these k objects to the user through the web interface. Here k is often a small value like 50 or 100. For example, McDonald [1] returns the top 25 nearest restaurants for a user-specified location through its locations search webpage.

With the development of location-based services (LBS), LBS users are generating more and more spatio-textual data, e.g., checkins and attraction reviews. Since a spatio-textual entity may have different representations, possibly due to GPS deviations or typographical errors, it calls for effective methods to integrate the spatio-textual data from different data sources. In this paper, we study the problem of top-$k$spatio-textual similarity join (Topk-STJoin), which identifies the$k$most similar pairs from two spatio-textual data sets. One big challenge inTopk-STJoinis to efficiently identify the top-$k$similar pairs by considering both textual relevancy and spatial proximity. Traditional join algorithms that consider only one dimension (textual or spatial) are inefficient because they cannot utilize the pruning ability on the other dimension. To address this challenge, we propose a signature-based top-$k$join framework. We first generate a spatio-textual signature set for each object such that if two objects are in the top-$k$similar pairs, their signature sets must overlap. With this property, we can prune large numbers of dissimilar pairs without common signatures. We find that the order of accessing the signatures has a significant effect on the performance. So, we compute an upper bound for each signature and propose a best-first accessing method that preferentially accesses signatures with large upper bounds while those pairs with small upper bounds can be pruned. We prove the optimality of our best-first accessing method. Next, we optimize the spatio-textual signatures and propose progressive signatures to further improve the pruning power. Experimental results on real-world datasets show that our algorithm achieves high performance and good scalability, and significantly outperforms baseline approaches.

Many websites offering Location Based Services (LBS) provide a$k$NN search interface that returns the top-$k$nearest-neighbor objects (e.g., nearest restaurants) for a given query location. This paper addresses the problem of crawling all objects efficiently from an LBS website, through the public$k$NN web search interface it provides. Specifically, we develop crawling algorithm for 2D and higher-dimensional spaces, respectively, and demonstrate through theoretical analysis that the overhead of our algorithms can be bounded by a function of the number of dimensions and the number of crawled objects, regardless of the underlying distributions of the objects. We also extend the algorithms to leverage scenarios where certain auxiliary information about the underlying data distribution, e.g., the population density of an area which is often positively correlated with the density of LBS objects, is available. Extensive experiments on real-world datasets demonstrate the superiority of our algorithms over the state-of-the-art competitors in the literature.

Many online social networks feature restrictive web interfaces that only allow the query of a user’s local neighborhood. To enable analytics over such an online social network through its web interface, many recent efforts use Markov Chain Monte Carlo (MCMC) methods such as random walks to sample users in the social network and thereby support analytics based on the samples. The problem with such an approach, however, is the large amount of queries often required for a random walk to converge to a desired (stationary) sampling distribution. In this article, we consider a novel problem of enabling a faster random walk over online social networks by “rewiring” the social network on-the-fly. Specifically, we develop a Modified TOpology Sampling (MTO-Sampling) scheme that, by using only information exposed by the restrictive web interface, constructs a “virtual” random-walk-friendly overlay topology of the social network while performing a random walk and ensures that the random walk follows the modified overlay topology rather than the original one. We describe in this article instantiations of MTO-Sampling for various types of random walks, such as Simple Random Walk (MTO-SRW), Metropolis-Hastings Random Walk (MTO-MHRW), and General Random Walk (MTO-GRW). We not only rigidly prove that MTO-Sampling improves the efficiency of sampling, but we also demonstrate the significance of such improvement through experiments on real-world online social networks such as Google Plus, Epinion, Facebook, etc.

Emergency medical service provides a variety of services for those in need of emergency care. One of the major challenges encountered by emergency service providers is selecting the appropriate locations for ambulance stations. Prior works measure spatial proximity under Euclidean space or static road network. In this paper, we focus on locating the ambulance stations by using the real traffic information so as to minimize the average travel-time to reach the emergency requests. To this end, we estimate the travel-time of road segments using real GPS trajectories and propose an efficient PAM-based refinement for the location problem. We conduct extensive experimental evaluations using real emergency requests collected from Tianjin, and the result shows that the proposed solution can reduce the travel-time to reach the emergency requests by 29.9% when compared to the original locations of ambulance stations.

Discovering motifs in sequence databases has been receiving abundant attentions from both database and data mining communities, where the motif is the most correlated pair of subsequences in a sequence object. Motif discovery is expensive for emerging applications which may have very long sequences (e.g., million observations per sequence) or the queries arrive rapidly (e.g., per 10 seconds). Prior works cannot offer fast correlation computations and prune subsequence pairs at the same time, as these two techniques require different orderings on examining subsequence pairs. In this work, we propose a novel framework named Quick-Motif which adopts a two-level approach to enable batch pruning at the outer level and enable fast correlation calculation at the inner level. We further propose two optimization techniques for the outer and the inner level. In our experimental study, our method is up to 3 orders of magnitude faster than the state-of-the-art methods.

Peer reviewing is a standard process for assessing the quality of submissions at academic conferences and journals. A very important task in this process is the assignment of reviewers to papers. However, achieving an appropriate assignment is not easy, because all reviewers should have similar load and the subjects of the assigned papers should be consistent with the reviewers' expertise. In this paper, we propose a generalized framework for fair reviewer assignment. We first extract the domain knowledge from the reviewers' published papers and model this knowledge as a set of topics. Then, we perform a group assignment of reviewers to papers, which is a generalization of the classic Reviewer Assignment Problem (RAP), considering the relevance of the papers to topics as weights. We study a special case of the problem, where reviewers are to be found for just one paper (Journal Assignment Problem) and propose an exact algorithm which is fast in practice, as opposed to brute-force solutions. For the general case of having to assign multiple papers, which is too hard to be solved exactly, we propose a greedy algorithm that achieves a 1/2-approximation ratio compared to the exact solution. This is a great improvement compared to the 1/3-approximation solution proposed in previous work for the simpler coverage-based reviewer assignment problem, where there are no weights on topics. We theoretically prove the approximation bound of our solution and experimentally show that it is superior to the current state-of-the-art.

Peer reviewing is a widely accepted mechanism for assessing the quality of submitted articles to scientific conferences or journals. Conference management systems (CMS) are used by conference organizers to invite appropriate reviewers and assign them to submitted papers. Typical CMS rely on paper bids entered by the reviewers and apply simple matching algorithms to compute the paper assignment. In this paper, we demonstrate our Reviewer Assignment System (RAS), which has advanced features compared to broadly used CMSs. First, RAS automatically extracts the profiles of reviewers and submissions in the form of topic vectors. These profiles can be used to automatically assign reviewers to papers without relying on a bidding process, which can be tedious and error-prone. Second, besides supporting classic assignment models (e.g., stable marriage and optimal assignment), RAS includes a recently published assignment model by our research group, which maximizes, for each paper, the coverage of its topics by the profiles of its reviewers. The features of the demonstration include (1) automatic extraction of paper and reviewer profiles, (2) assignment computation by different models, and (3) visualization of the results by different models, in order to assess their effectiveness.

The k nearest neighbor (kNN) search on road networks is an important function in web mapping services. These services are now dealing with rapidly arriving queries, that are issued by a massive amount of users. While overlay graph-based indices can answer shortest path queries efficiently, there have been no studies on utilizing such indices to answer kNN queries efficiently. In this paper, we fill this research gap and present two efficient kNN search solutions on overlay graph-based indices. Experimental results show that our solutions offer very low query latency (0.1 ms) and require only small index sizes, even for 10-million-node networks.

A large number of web data repositories are hidden behind restrictive web interfaces, making it an important challenge to enable data analytics over these hidden web databases. Most existing techniques assume a form-like web interface which consists solely of categorical attributes (or numeric ones that can be discretized). Nonetheless, many real-world web interfaces (of hidden databases) also feature checkbox interfaces-e.g., the specification of a set of desired features, such as A/C, navigation, etc., for a car-search website like Yahoo! Autos. We find that, for the purpose of data analytics, such checkbox-represented attributes differ fundamentally from the categorical/numerical ones that were traditionally studied. In this paper, we address the problem of data analytics over hidden databases with checkbox interfaces. Extensive experiments on both synthetic and real datasets demonstrate the accuracy and efficiency of our proposed algorithms.

Location-based services have been widely adopted in many systems. Existing works employ a pull model or user-initiated model, where a user issues a query to a server which replies with location-aware answers. To provide users with instant replies, a push model or server-initiated model is becoming an inevitable computing model in the next-generation location-based services. In the push model, subscribers register spatio-textual subscriptions to capture their interests, and publishers post spatio-textual messages. This calls for a high-performance location-aware publish/subscribe system to deliver publishers' messages to relevant subscribers. In this paper, we address the research challenges that arise in designing a location-aware publish/subscribe system. We propose an R-tree based index by integrating textual descriptions into R-tree nodes. We devise efficient filtering algorithms and effective pruning techniques to achieve high performance. Our method can support both conjunctive queries and ranking queries. We discuss how to support dynamic updates efficiently. Experimental results show our method achieves high performance which can filter 500 messages in a second for 10 million subscriptions on a commodity computer.

In the recent decades, we have witnessed the rapidly growing popularity of location-based systems. Three types of location-based queries on road networks, single-pair shortest path query, k nearest neighbor (kNN) query, and keyword-based kNN query, are widely used in location-based systems. Inspired by R-tree, we propose a height-balanced and scalable index, namely G-tree, to efficiently support these queries. The space complexity of G-tree is O(|V|log|V|) where |V| is the number of vertices in the road network. Unlike previous works that support these queries separately, G-tree supports all these queries within one framework. The basis for this framework is an assembly-based method to calculate the shortest-path distances between two vertices. Based on the assembly-based method, efficient search algorithms to answer kNN queries and keyword-based kNN queries are developed. Experiment results show G-tree's theoretical and practical superiority over existing methods.

Deducing trip-related information from web-scale datasets has received large amounts of attention recently. Identifying points of interest (POIs) in geo-tagged photos is one of these problems. The problem can be viewed as a standard clustering problem of partitioning two-dimensional objects. In this work, we study spectral clustering, which is the first attempt for the identification of POIs. However, there is no unified approach to assigning the subjective clustering parameters, and these parameters vary immensely in different metropolitans and locations. To address this issue, we study a self-tuning technique that can properly determine the parameters for the clustering needed. Besides geographical information, web photos inherently store other rich information. Such heterogenous information can be used to enhance the identification accuracy. Thereby, we study a novel refinement framework that is based on the tightness and cohesion degree of the additional information. We thoroughly demonstrate our findings by web-scale datasets collected from Flickr.

The online shortest path problem aims at computing the shortest path based on live traffic circumstances. This is very important in modern car navigation systems as it helps drivers to make sensible decisions. To our best knowledge, there is no efficient system/solution that can offer affordable costs at both client and server sides for online shortest path computation. Unfortunately, the conventional client-server architecture scales poorly with the number of clients. A promising approach is to let the server collect live traffic information and then broadcast them over radio or wireless network. This approach has excellent scalability with the number of clients. Thus, we develop a new framework called live traffic index (LTI)which enables drivers to quickly and effectively collect the live traffic information on the broadcasting channel. An impressive result is that the driver can compute/update their shortest path result by receiving only a small fraction of the index. Our experimental study shows that LTI is robust to various parameters and it offers relatively short tune-in cost (at client side), fast query response time (at client side), small broadcast size (at server side), and light maintenance time (at server side)for online shortest path problem.

Many online social networks feature restrictive web interfaces which only allow the query of a user's local neighborhood through the interface. To enable analytics over such an online social network through its restrictive web interface, many recent efforts reuse the existing Markov Chain Monte Carlo methods such as random walks to sample the social network and support analytics based on the samples. The problem with such an approach, however, is the large amount of queries often required (i.e., a long “mixing time”) for a random walk to reach a desired (stationary) sampling distribution. In this paper, we consider a novel problem of enabling a faster random walk over online social networks by “rewiring” the social network on-the-fly. Specifically, we develop Modified TOpology (MTO)-Sampler which, by using only information exposed by the restrictive web interface, constructs a “virtual” overlay topology of the social network while performing a random walk, and ensures that the random walk follows the modified overlay topology rather than the original one. We show that MTO-Sampler not only provably enhances the efficiency of sampling, but also achieves significant savings on query cost over real-world online social networks such as Google Plus, Epinion etc.

Most existing work on sequence databases use correlation (e.g., Euclidean distance and Pearson correlation) as a core function for various analytical tasks. Typically, it requires users to set a length for the similarity queries. However, there is no steady way to define the proper length on different application needs. In this work we focus on discovering longest-lasting highly correlated subsequences in sequence databases, which is particularly useful in helping those analyses without prior knowledge about the query length. Surprisingly, there has been limited work on this problem. A baseline solution is to calculate the correlations for every possible subsequence combination. Obviously, the brute force solution is not scalable for large datasets. In this work we study a space-constrained index that gives a tight correlation bound for subsequences of similar length and offset by intra-object grouping and inter-object grouping techniques. To the best of our knowledge, this is the first index to support normalized distance metric of arbitrary length subsequences. Extensive experimental evaluation on both real and synthetic sequence datasets verifies the efficiency and effectiveness of our proposed methods.

In general, users may influence each other by their activities in social networks. It is interesting to explore hidden relationships of users based on their social activities. In this paper, we define and study a novel community detection problem that is to discover the hidden community structure in large social networks based on their common interests. We observe that the users typically pay more attention to those users who share similar interests, which enable a way to partition the users into different communities according to their common interests. We propose two algorithms to detect influential communities using common interests in large social networks efficiently and effectively. We conduct our experimental evaluation using a dataset from Epinions, which demonstrates that our method achieves 4%-11.8% accuracy improvement over the state of the art method.

Deducing trip related information from web-scale datasets has received very large amounts of attention recently. Identifying points of interest (POIs) in geo-tagged photos is one of these problems. The problem can be viewed as a standard clustering problem of partitioning two dimensional objects. In this work, we study spectral clustering which is the first attempt for the POIs identification. However, there is no unified approach to assign the clustering parameters; especially the features of POIs are immensely varying in different metropolitans and locations. To address this, we are intent to study a self-tuning technique which can properly assign the parameters for the clustering needed. Besides geographical information, web photos inherently store rich information. These information are mutually influenced each others and should be taken into trip related mining tasks. To address this, we study reinforcement which constructs the relationship over multiple sources by iterative learning. At last, we thoroughly demonstrate our findings by web scale datasets collected from Flickr.