A key challenge in graph out-of-distribution (OOD) detection lies in the absence of ground-truth OOD samples during training. Existing methods are typically optimized to capture features within the in-distribution (ID) data and calculate OOD scores, which often limits pre-trained models from representing distributional boundaries, leading to unreliable OOD detection. Moreover, the latent structure of graph data is often governed by multiple underlying factors, which remains less explored. To address these challenges, we propose a novel test-time graph OOD detection method, termed BaCa, that calibrates OOD scores using dual dynamically updated dictionaries without requiring fine-tuning the pre-trained model. Specifically, BaCa estimates graphons and applies a mix-up strategy solely with test samples to generate diverse boundary-aware discriminative topologies, eliminating the need for exposing auxiliary datasets as outliers. We construct dual dynamic dictionaries via priority queues and attention mechanisms to adaptively capture latent ID and OOD representations, which are then utilized for boundary-aware OOD score calibration. To the best of our knowledge, extensive experiments on real-world datasets show that BaCa significantly outperforms existing state-of-the-art methods in OOD detection.

While leveraging pseudo-labels has become a common paradigm in untargeted gray-box graph poisoning attacks, it suffers from two critical limitations: the use of brittle hard pseudo-labels that overlook uncertainty and can amplify surrogate model errors, and static guidance that progressively becomes stale as the graph is perturbed. To resolve these issues, we propose MetaDist, a novel framework that reframes the attack as an adversarial self-knowledge distillation process. Here, a "teacher" model provides continuously refined soft pseudo-labels to a "student" model, with the attack objective being to maximize the divergence between them. MetaDist makes two synergistic innovations. It employs the Reverse KL (RKL) divergence as a more strategic attack loss that efficiently converts uncertain nodes into robust, high-confidence errors. Concurrently, it introduces the Online Adaptive Teacher (OAT) mechanism, which adapts the teacher via student feedback to ensure the guidance signal remains relevant. Extensive experiments demonstrate that MetaDist consistently and significantly outperforms strong baselines across multiple datasets, proving its effectiveness and transferability even against advanced graph defenses.

Physical adversarial examples (PAEs) are regarded as “whistle-blowers” of real-world risks in deep-learning applications, thus worth further investigation. However, current PAE generation studies show limited adaptive attacking ability to diverse and varying scenes, revealing the urgent requirement of dynamic PAEs that are generated in real time and conditioned on the observation from the attacker. The key challenge in generating dynamic PAEs is learning the sparse relation between PAEs and the observation of attackers under the noisy feedback of attack training. To address the challenge, we present DynamicPAE, the first generative framework that enables scene-aware real-time physical attacks. Specifically, to address the noisy feedback problem that obfuscates the exploration of scene-related PAEs, we introduce the residual-guided adversarial pattern exploration technique. We first introduce the limited feedback information restriction to model the training degeneracy problem under noisy feedback. Then, residual-guided training, which relaxes the attack training with a reconstruction task, is proposed to enrich the feedback information, thereby achieving a more comprehensive exploration of PAEs. To address the alignment problem between the trained generator, which represents the learned relation, and the real-world scenario, we introduce the distribution-matched attack scenario alignment, consisting of the conditional-uncertainty-aligned data module and the skewness-aligned objective re-weighting module. The former aligns the training environment with the incomplete observation of the real-world attacker. The latter facilitates consistent stealth control across different attack targets by balancing the objectives with the skewness indicator. Extensive digital and physical evaluations demonstrate the superior attack performance of DynamicPAE, attaining a 2.07× boost ( 58.8% average AP drop under attack) on representative object detectors (e.g., DETR) over state-of-the-art static PAE generating methods. Overall, our work opens the door to end-to-end modeling of dynamic PAEs.

With the emerging of huge amount of unlabeled data, unsupervised out-of-distribution (OOD) detection is vital for ensuring the reliability of graph neural networks (GNNs) by identifying OOD samples from in-distribution (ID) ones during testing, where encountering novel or unknown data is inevitable. Existing methods often suffer from compromised performance due to redundant information in graph structures, which impairs their ability to effectively differentiate between ID and OOD data. To address this challenge, we propose SEGO, an unsupervised framework that integrates structural entropy into OOD detection regarding graph classification. Specifically, within the architecture of contrastive learning, SEGO introduces an anchor view in the form of coding tree by minimizing structural entropy. The obtained coding tree effectively removes redundant information from graphs while preserving essential structural information, enabling the capture of distinct graph patterns between ID and OOD samples. Furthermore, we present a multi-grained contrastive learning scheme at local, global, and tree levels using triplet views, where coding trees with essential information serve as the anchor view. Extensive experiments on real-world datasets validate the effectiveness of SEGO, demonstrating superior performance over state-of-the-art baselines in OOD detection. Specifically, our method achieves the best performance on 9 out of 10 dataset pairs, with an average improvement of 3.7% on OOD detection datasets, significantly surpassing the best competitor by 10.8% on the FreeSolv/ToxCast dataset pair.

Zekun Moore Wang, Shenzhi Wang, King Zhu, Jiaheng Liu, Ke Xu, Jie Fu, Wangchunshu Zhou, Wenhao Huang. Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2025.

Traditional methods for detecting rumors on social media primarily focus on analyzing textual content, often struggling to capture the complexity of online interactions. Recent research has shifted towards leveraging graph neural networks to model the hierarchical conversation structure that emerges during rumor propagation. However, these methods tend to overlook the temporal aspect of rumor propagation and may disregard potential noise within the propagation structure. In this paper, we propose a novel approach that incorporates temporal information by constructing a weighted propagation tree, where the weight of each edge represents the time interval between connected posts. Drawing upon the theory of structural entropy, we transform this tree into a coding tree. This transformation aims to preserve the essential structure of rumor propagation while reducing noise. Finally, we introduce a recursive neural network to learn from the coding tree for rumor veracity prediction. Experimental results on two common datasets demonstrate the superiority of our approach.

Zekun Moore Wang, King Zhu, Chunpu Xu, Wangchunshu Zhou, Jiaheng Liu, Yibo Zhang, Jessie Wang, Ning Shi, Siyu Li, Yizhi Li, Haoran Que, Zhaoxiang Zhang, Yuanxing Zhang, Ge Zhang, Ke Xu, Jie Fu, Wenhao Huang. Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing. 2025.

Human identification at a distance (HID) faces challenges due to the difficulty of acquiring traditional biometric modalities like face and fingerprints. Gait recognition offers a viable solution since it can be captured at a distance. To promote progress in gait recognition and provide a fair evaluation platform, the International Competition on Human Identification at a Distance (HID) has been organized annually since 2020. Since 2023, the competition has adopted the challenging SUSTech-Competition dataset, which includes significant variations in clothing, carried objects, and view angles. No training data is provided, requiring participants to train their models using external datasets. Each year, the competition applies a different random seed to generate distinct evaluation splits, reducing the risk of overfitting and ensuring fair evaluation of cross-domain generalization. Although the previous two competitions (HID 2023 and HID 2024) already utilized this dataset, HID 2025 aimed explicitly to explore whether algorithmic improvements could surpass the accuracy limits observed previously. Despite these heightened challenges, participants again demonstrated significant advancements, with the highest accuracy reaching 94.2%, setting a new benchmark for this dataset. We also analyze key technical trends and outline potential directions for future research on gait recognition.

This paper studies point cloud perception within outdoor environments. Existing methods face limitations in recognizing objects located at a distance or occluded, due to the sparse nature of outdoor point clouds. In this work, we observe a significant mitigation of this problem by accumulating multiple temporally consecutive LiDAR sweeps, resulting in a remarkable improvement in perception accuracy. However, the computation cost also increases, hindering previous approaches from utilizing a large number of LiDAR sweeps. To tackle this challenge, we find that a considerable portion of points in the accumulated point cloud is redundant, and discarding these points has minimal impact on perception accuracy. We introduce a simple yet effective Gumbel Spatial Pruning (GSP) layer that dynamically prunes points based on a learned end-toend sampling. The GSP layer is decoupled from other network components and thus can be seamlessly integrated into existing point cloud network architectures. Extensive experiments show that our pruning strategy improves several perception algorithms in multiple tasks.

Out-of-distribution (OOD) detection for graph-structured data remains a challenging problem, particularly when test-time OOD samples deviate significantly from the training outliers. Existing methods are typically optimized to capture the features within the in-distribution (ID) training data, but often fail to model the transitional region near the boundary between ID and OOD samples. Moreover, since data distributions are usually governed by multiple latent factors, pre-trained models constrained by the scope and diversity of training data struggle to represent the full spectrum of sample characteristics and distributional boundaries. To address this dilemma, we propose a novel test-time graph OOD detection method, termed D2GO, that constructs and dynamically updates ID and OOD graphon dictionaries for OOD score calibration, without requiring fine-tuning. Specifically, D2GO estimates graphons from test graphs and employs a mix-up strategy to generate boundary samples, eliminating the need for exposing auxiliary datasets or training graphs. Priority queues are utilized to expand the ID and OOD dictionaries by incorporating diverse graphons based on pseudo-labels at test-time, and the OOD scores are calibrated by computing the similarity between test samples and both graphon dictionaries. Extensive experiments on real-world datasets show that D2GO significantly outperforms existing state-of-the-art methods in OOD detection.

Distributional discrepancy between training and test data can lead models to make inaccurate predictions when encountering out-of-distribution (OOD) samples in real-world applications. Although existing graph OOD detection methods leverage data-centric techniques to extract effective representations, their performance remains compromised by structural redundancy that induces semantic shifts. To address this dilemma, we propose RedOUT, an unsupervised framework that integrates structural entropy into test-time OOD detection for graph classification. Concretely, we introduce the Redundancy-aware Graph Information Bottleneck (ReGIB) and decompose the objective into essential information and irrelevant redundancy. By minimizing structural entropy, the decoupled redundancy is reduced, and theoretically grounded upper and lower bounds are proposed for optimization. Extensive experiments on real-world datasets demonstrate the superior performance of RedOUT on OOD detection. Specifically, our method achieves an average improvement of 6.7\%, significantly surpassing the best competitor by 17.3\% on the ClinTox/LIPO dataset pair.

Recently, semantically constrained adversarial examples (SemanticAE), which are directly generated from natural language instructions, have become a promising avenue for future research due to their flexible attacking forms, but have not been thoroughly explored yet. To generate SemanticAEs, current methods fall short of satisfactory attacking ability as the key underlying factors of semantic uncertainty in human instructions, such as $\textit{referring diversity}$, $\textit{descriptive incompleteness}$, and $\textit{boundary ambiguity}$, have not been fully investigated. To tackle the issues, this paper develops a multi-dimensional $\textbf{ins}$truction $\textbf{u}$ncertainty $\textbf{r}$eduction ($\textbf{InSUR}$) framework to generate more satisfactory SemanticAE, $\textit{i.e.}$, transferable, adaptive, and effective. Specifically, in the dimension of the sampling method, we propose the residual-driven attacking direction stabilization to alleviate the unstable adversarial optimization caused by the diversity of language references. By coarsely predicting the language-guided sampling process, the optimization process will be stabilized by the designed ResAdv-DDIM sampler‌, therefore releasing the transferable and robust adversarial capability of multi-step diffusion models. In task modeling, we propose the context-encoded attacking scenario constraint to supplement the missing knowledge from incomplete human instructions. Guidance masking and renderer integration are proposed to regulate the constraints of 2D/3D SemanticAE, activating stronger scenario-adapted attacks. Moreover, in the dimension of generator evaluation, we propose the semantic-abstracted attacking evaluation enhancement by clarifying the evaluation boundary based on the label taxonomy, facilitating the development of more effective SemanticAE generators. Extensive experiments demonstrate the superiority of the transfer attack performance of InSUR. Besides, it is worth highlighting that we realize the reference-free generation of semantically constrained 3D adversarial examples by utilizing language-guided 3D generation models for the first time.

ABSTRACT Technical analysis, which includes technical indicators and charts derived from specific rules, has proven effective and widely used for stock movement prediction. However, technical chart evaluation is often limited by subjectivity, arising from sparse chart types and substantial information loss due to rigid rules. While pattern recognition algorithms have been developed to address this issue, they still rely on manual chart labelling and primarily focus on closing prices, leaving much of the chart's broader information untapped. To overcome these limitations, we propose a novel framework called ChartNet, designed to extract general information from technical charts and reduce subjectivity in chart analysis. ChartNet employs a unified representation for charts across financial series with varying simplification levels and leverages a chart triplet loss function for unsupervised training, eliminating the need for labelled data. Compared with several state‐of‐the‐art baselines, our framework has reached the best prediction accuracy on CSI‐300, SZ‐50 components and Dow Jones Index in 2022: 65.91%, 63.70% and 64.96% respectively. In backtesting using actual stock data, our framework achieves the highest average return of 1.12 and 1.15. Furthermore, we highlight the interpretability of ChartNet through two case studies, some important charts and failure cases, illustrating its capability to uncover meaningful insights from charts. This research contributes to advancing the objective evaluation of technical charts and promoting a more comprehensive understanding of chart‐based stock prediction performance.

In mobile crowdsensing, task interruptions can cause failures and reduce system stability. Despite the significance of this issue, few studies have addressed task allocation under interruptions. To bridge this gap, we propose IT-STA, an interruption-based stable task allocation algorithm that reallocates interrupted tasks to improve completion rates and maintain system stability. First, an efficient detection mechanism is designed to promptly identify interrupted tasks, ensuring timely intervention. Second, a distributed reallocation strategy is developed to assign interrupted tasks to suitable participants, leveraging a novel individual migration strategy that enables parallel coordination among nodes, ensuring efficient global matching and avoiding suboptimal solutions. Experimental results demonstrate IT-STA’s superiority over baselines in task allocation stability and performance.

Given the pivotal role of molecular property prediction in drug development and material science, graph self-supervised learning has been implemented in molecular representation learning to compensate for the shortage of labeled molecules. However, current proposed methods often focus on designing data augmentation schemes and leveraging domain knowledge to improve performance, which inevitably leads to molecular semantics loss and limited generalization capability. To the end, we propose IPM, an Information lossless Pretraining strategy for Molecular property prediction that leverages the information of both the original graph and line graph of molecules. Specifically, by contrasting the given graph with the corresponding line graph, the graph encoder can fully learn the generic molecular semantic representation without profound domain knowledge. We also design a new message-passing scheme that retains information consistency during message passing between two kinds of graphs. Additionally, we present two graph contrastive losses for performance fixing and over-smoothing prevention during the learning process. Experimental results on multiple regression tasks for molecular property prediction demonstrate the effectiveness of IPM against state-of-the-art (SOTA) methods.

Novel Class Discovery (NCD) involves identifying new categories within unlabeled data by utilizing knowledge acquired from previously established categories. However, existing NCD methods often struggle to maintain a balance between the performance of old and new categories. Discovering unlabeled new categories in a class-incremental way is more practical but also more challenging, as it is frequently hindered by either catastrophic forgetting of old categories or an inability to learn new ones. Furthermore, the implementation of NCD on continuously scalable graph-structured data remains an under-explored area. In response to these challenges, we introduce for the first time a more practical NCD scenario for node classification (i.e., NC-NCD), and propose a novel self-training framework with prototype replay and distillation called SWORD, adopted to our NC-NCD setting. Our approach enables the model to cluster unlabeled new category nodes after learning labeled nodes while preserving performance on old categories without reliance on old category nodes. SWORD achieves this by employing a self-training strategy to learn new categories and preventing the forgetting of old categories through the joint use of feature prototypes and knowledge distillation. Extensive experiments on four common benchmarks demonstrate the superiority of SWORD over other state-of-the-art methods.

Recently, many approaches directly operate on point clouds for different tasks. These approaches become more computation and storage demanding when point cloud size is large. To reduce the required computation and storage, one possible solution is to sample the point cloud. In this paper, we propose the first Learnable Task-Agnostic Point Cloud Sampling (LTA-PCS) framework. Existing task-agnostic point cloud sampling strategy (e.g., FPS) does not consider semantic information of point clouds, causing de-graded performance on downstream tasks. While learning-based point cloud sampling methods consider semantic in-formation, they are task-specific and require task-oriented ground-truth annotations. So they cannot generalize well on different downstream tasks. Our LTA-PCS achieves task-agnostic point cloud sampling without requiring task-oriented labels, in which both the geometric and semantic information of points is considered in sampling. Extensive experiments on multiple downstream tasks demonstrate the effectiveness of our LTA-PCS.

With the rapid advancement of IT operations, managing and analyzing large data volumes efficiently for practical applications has become increasingly critical. Natural Language Processing (NLP) techniques have demonstrated remarkable capabilities in various tasks, including named entity recognition, machine translation, and dialogue systems. Recently, Large Language Models (LLMs) have achieved significant improvements across various domain-specific areas. However, there is a noticeable gap in the development of specialized Large Language Models (LLMs) tailored for IT operations. In this paper, we introduce the OWL, a large language model trained on our constructed Owl-Instruct with a wide range of IT-related information. Specifically, limited by the maximum input length, we propose the \textbf{H}omogeneous \textbf{M}arkov \textbf{C}ontext \textbf{E}xtension method (HMCE). The mixture-of-adapter strategy is leveraged to improve the parameter-efficient tuning across different domains or tasks. Further, we evaluate the performance of OWL on the Owl-Bench established by us and open IT-related benchmarks. OWL demonstrates superior performance results on IT tasks, which outperforms existing models by significant margins. Moreover, we hope that the findings of our work will provide more insights to revolutionize the techniques of IT operations with specialized LLMs.

Path planning underpins various applications such as transportation, logistics, and robotics. Conventionally, path planning is formulated with explicit optimization objectives such as distance or time. However, real-world data reveals that user intentions are hard-to-model, suggesting a need for data-driven path planning that implicitly incorporates the complex user intentions. In this paper, we propose GDP, a diffusion-based model for end-to-end data-driven path planning. It effectively learns path patterns via a novel diffusion process that incorporates constraints from road networks, and plans paths as conditional path generation given the origin and destination as prior evidence. GDP is the first solution that bypasses the traditional search-based frameworks, a long-standing performance bottleneck in path planning. We validate the efficacy of GDP on two real-world datasets. Our GDP beats strong baselines by 14.2% ~ 43.5% and achieves state-of-the-art performances.

Public opinion plays a pivotal role in politics, influencing political leaders' decisions, shaping election outcomes, and impacting policy-making processes. In today's digital age, the abundance of political discourse available on social media platforms has become an invaluable resource for analyzing public opinion. This paper focuses on the task of detecting political stances in the context of the 2020 US presidential election. To facilitate this research, we curate a substantial dataset sourced from Twitter, annotated using hashtags as indicators of political polarity. In our approach, we construct a bipartite graph that explicitly models user-tweet interactions, which provides a comprehensive contextual understanding of the election. To effectively leverage the wealth of user behavioral information encoded in this graph, we adopt graph convolution and introduce a novel skip aggregation mechanism. This mechanism enables tweet nodes to aggregate information from their second-order neighbors, which are also tweet nodes due to the graph's bipartite nature. Our experimental results demonstrate that our proposed model outperforms a range of competitive baseline models. Furthermore, our in-depth analyses highlight the importance of user behavioral information and the effectiveness of skip aggregation.

Given the development and abundance of social media, studying the stance of social media users is a challenging and pressing issue. Social media users express their stance by posting tweets and retweeting. Therefore, the homogeneous relationship between users and the heterogeneous relationship between users and tweets are relevant for the stance detection task. Recently, graph neural networks (GNNs) have developed rapidly and have been applied to social media research. In this paper, we crawl a large-scale dataset of the 2020 US presidential election and automatically label all users by manually tagged hashtags. Subsequently, we propose a bipartite graph neural network model, DoubleH, which aims to better utilize homogeneous and heterogeneous information in user stance detection tasks. Specifically, we first construct a bipartite graph based on posting and retweeting relations for two kinds of nodes, including users and tweets. We then iteratively update the node's representation by extracting and separately processing heterogeneous and homogeneous information in the node's neighbors. Finally, the representations of user nodes are used for user stance classification. Experimental results show that DoubleH outperforms the state-of-the-art methods on popular benchmarks. Further analysis illustrates the model's utilization of information and demonstrates stability and efficiency at different numbers of layers.

Recently, indoor 3D object detection has shown impressive progress. However, these improvements have come at the cost of increased memory consumption and longer inference times, making it difficult to apply these methods in practical scenarios. To address this issue, knowledge distillation has emerged as a promising technique for model acceleration. In this paper, we propose the VRDistill framework, the first knowledge distillation framework designed for efficient indoor 3D object detection. Our VRDistill framework includes a refinement module and a soft foreground mask operation to enhance the quality of the distillation. The refinement module utilizes trainable layers to improve the quality of the teacher's votes, while the soft foreground mask operation focuses on foreground votes, further enhancing the distillation performance. Comprehensive experiments on the ScanNet and SUN-RGBD datasets demonstrate the effectiveness and generalization ability of our VRDistill framework.

He Zhu, Junran Wu, Ruomei Liu, Yue Hou, Ze Yuan, Shangzhe Li, Yicheng Pan, Ke Xu. Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers). 2024.

Believable agents can empower interactive applications ranging from immersive environments to rehearsal spaces for interpersonal communication. Recently, generative agents have been proposed to simulate believable human behavior by using Large Language Models. However, the existing method heavily relies on human-annotated agent profiles (e.g., name, age, personality, relationships with others, and so on) for the initialization of each agent, which cannot be scaled up easily. In this paper, we propose a scalable RoleAgent framework to generate high-quality role-playing agents from raw scripts, which includes building and interacting stages. Specifically, in the building stage, we use a hierarchical memory system to extract and summarize the structure and high-level information of each agent for the raw script. In the interacting stage, we propose a novel innovative mechanism with four steps to achieve a high-quality interaction between agents. Finally, we introduce a systematic and comprehensive evaluation benchmark called RoleAgentBench to evaluate the effectiveness of our RoleAgent, which includes 100 and 28 roles for 20 English and 5 Chinese scripts, respectively. Extensive experimental results on RoleAgentBench demonstrate the effectiveness of RoleAgent.

Spatiotemporal applications such as taxi order dispatching and warehouse task scheduling depend critically on the algorithms for operational efficiency. However, the inherent dynamic nature of these applications presents challenges in algorithm design. The growth of mobility services has facilitated the collection of extensive spatiotemporal data, which in turn prompted algorithm designers to use data-driven methods. Reinforcement learning (RL), recognized for its strong performance and suitability for spatiotemporal contexts, has garnered considerable research interest. Despite their potential, RL algorithms necessitate the use of a simulator for both training and validation purposes. However, no specific simulation system has been developed for spatiotemporal algorithm design. This vacancy hinders the progress of spatiotemporal algorithm designers. In this demo, we build a system called Data-driven Spatiotemporal Simulator (DSS), hoping to bring convenience for spatiotemporal algorithm designers. DSS is adept at handling problems related to taxi order dispatching and warehouse task scheduling and possesses the versatility to be expanded for other user-defined scenarios. The system includes visualization modules that offer insightful panels, alongside developer tools designed to streamline the development process. This enables designers to efficiently craft, evaluate, and refine their algorithms, potentially accelerating innovation in spatiotemporal application development.

Shared mobility leverages under-utilized vehicles to offer on-demand transport services by sharing vehicles among users. It strives to match supply with demand via a series of data-intensive operations such as supply prediction and task assignment. However, its full potential is often compromised in practice as most shared mobility platforms operate in isolation, leading to sub-optimal resource utilization. In this demonstration, we advocate a federated approach to shared mobility, which enhances its effectiveness by enabling optimizations across platforms while retaining their autonomy. We develop privacy-preserving operators and incentive mechanisms dedicated to supply prediction and task assignment in shared mobility and implement generic interfaces that support diverse prediction and assignment algorithms. We showcase the shared mobility system with real-world ride-hailing applications.

Forecasting financial data plays a crucial role in financial market. Relying solely on prices or price trends as prediction targets often leads to a vast of invalid transactions. As a result, researchers have increasingly turned their attention to turning points as the prediction target. Surprisingly, existing methods have largely overlooked the role of technical charts, despite turning points being closely related to the technical charts. Recently, several researchers have attempted to utilize chart information via converting price sequences into images for turning point forecasting, but robustness and convergence problems arise. To address these challenges and enhance the turning point predictions, this article introduces a new method known as MPCNet. Specifically, we first transform the price series into a graph structure using chart similarity to robustly extract valuable information from technical charts. Additionally, we introduce the multipersistence topology tool to accurately predict stock turning points and provide convergence guarantee. Experimental results demonstrate the significant superiority of our proposed model over existing methods. Furthermore, based on additional performance evaluations using real stock data, MPCNet consistently achieves the highest average return during the transaction backtesting period. Meanwhile, we provide empirical validation of robustness and theoretical analysis to confirm its convergence, establishing it as a superior tool for financial forecasting.

Hierarchical text classification (HTC) is a challenging subtask of multi-label classification as the labels form a complex hierarchical structure.Existing dual-encoder methods in HTC achieve weak performance gains with huge memory overheads and their structure encoders heavily rely on domain knowledge.Under such observation, we tend to investigate the feasibility of a memory-friendly model with strong generalization capability that could boost the performance of HTC without prior statistics or label semantics.In this paper, we propose Hierarchy-aware Tree Isomorphism Network (HiTIN) to enhance the text representations with only syntactic information of the label hierarchy.Specifically, we convert the label hierarchy into an unweighted tree structure, termed coding tree, with the guidance of structural entropy.Then we design a structure encoder to incorporate hierarchy-aware information in the coding tree into text representations.Besides the text encoder, HiTIN only contains a few multi-layer perceptions and linear transformations, which greatly saves memory.We conduct experiments on three commonly used datasets and the results demonstrate that HiTIN could achieve better test performance and less memory consumption than state-of-the-art (SOTA) methods. * Equal Contribution.† Correspondence to: Junran Wu.

Multi-robot systems are deployed in modern warehouses to reduce operational cost. The robots are tasked to deliver items stored on racks to pickers for fast distribution. A central algorithmic problem is collision-aware route planning, which aims to plan shortest routes for robots to deliver racks while avoiding collision with racks, pickers, and other robots. Prior solutions are inefficient in real-world warehouses, where route planning requests emerge online and at large scale. In this paper, we identify collision judgement in grid-based warehouse representation as the primary efficiency bottleneck, and propose a novel Strip-based Route Planning framework (SRP). Specifically, we exploit the regularity in warehouse layouts, and aggregate grids into strips. The strip-based representation also converts collisions of 3-dimensional (2-dimensional space and 1-dimensional time) routes into 2-dimensional (1-dimensional space and 1-dimensional time) segment intersections, which can be fast checked via computational geometry. We further accelerate the collision judgement via indexing on segments within strips. Theoretical analysis shows a reduction of time complexity from square to linear-logarithmic. Experimental results on datasets collected from real-world robotized warehouses show that our SRP is up to 227× faster than existing methods.

In contrastive learning, the choice of "view" controls the information that the representation captures and influences the performance of the model. However, leading graph contrastive learning methods generally produce views via random corruption or learning, which could lead to the loss of essential information and alteration of semantic information. An anchor view that maintains the essential information of input graphs for contrastive learning has been hardly investigated. In this paper, based on the theory of graph information bottleneck, we deduce the definition of this anchor view; put differently, the anchor view with essential information of input graph is supposed to have the minimal structural uncertainty. Furthermore, guided by structural entropy, we implement the anchor view, termed SEGA, for graph contrastive learning. We extensively validate the proposed anchor view on various benchmarks regarding graph classification under unsupervised, semi-supervised, and transfer learning and achieve significant performance boosts compared to the state-of-the-art methods.

Skyline is a primitive operation in multi-objective decision applications and there is a growing demand to support such operations over a data federation, where the entire dataset is separately held by multiple data providers (a.k.a., silos). Data federations notably increase the amount of data available for data-intensive applications such as commercial recommendation and location based services. Yet they also challenge the conventional implementation of skyline queries because the raw data cannot be shared within the federation and the secure computation cross silos can be two or three orders of magnitude slower than plaintext computation. These constraints render existing solutions inefficient on data federation. In this work, we propose a novel local dominance based framework for efficient skyline queries over a vertical data federation. We decompose the skyline query into plaintext local dominance computations and secure result aggregations, which can perform as many computations in plaintext as possible without compromising security. We further propose a dedicate private set intersection based algorithm to accelerate the query processing. Extensive evaluations on both synthetic and real-world datasets show that compared with general-purpose secure multi-party computation techniques, our solutions reduce the time cost by up to 35.4× and communication cost by two orders of magnitude respectively.

kNN is a fundamental query in various location based services such as POI recommendation and ride planning. There is an increasing demand to scale such services by querying over a data federation, where the entire dataset is distributedly held by multiple data providers (a.k.a., silos), and each silo keeps its data partition private. However, it is challenging to provide secure kNN queries over a large-scale data federation. Prior secure kNN queries can be are highly inefficient if performed cross silos because they involve excessive secure distance operations, which can be two or three orders of magnitude slower than the corresponding plaintext operations. In this work, we propose a novel threshold based framework for efficient kNN queries over a spatial data federation. The key idea is to rewrite excessive secure distance computations as light-weight secure operations. We further propose an adaptive threshold algorithm to reduce the secure communication rounds and accelerate the query processing. Extensive evaluations on both synthetic and real-world datasets show that compared with the state-of-the-art secure kNN querying methods, our solutions reduce the time cost by up to 104.1 times and communication cost by three orders of magnitude.

Text classification is a primary task in natural language processing (NLP). Recently, graph neural networks (GNNs) have developed rapidly and been applied to text classification tasks. As a special kind of graph data, the tree has a simpler data structure and can provide rich hierarchical information for text classification. Inspired by the structural entropy, we construct the coding tree of the graph by minimizing the structural entropy and propose HINT, which aims to make full use of the hierarchical information contained in the text for the task of text classification. Specifically, we first establish a dependency parsing graph for each text. Then we designed a structural entropy minimization algorithm to decode the key information in the graph and convert each graph to its corresponding coding tree. Based on the hierarchical structure of the coding tree, the representation of the entire graph is obtained by updating the representation of non-leaf nodes in the coding tree layer by layer. Finally, we present the effectiveness of hierarchical information in text classification. Experimental results show that HINT outperforms the state-of-the-art methods on popular benchmarks while having a simple structure and few parameters.

Robotized warehouses are deployed to automatically distribute millions of items brought by the massive logistic orders from e-commerce. A key to automated item distribution is to plan paths for robots, also known as task planning, where each task is to deliver racks with items to pickers for processing and then return the rack back. Prior solutions are unfit for large-scale robotized warehouses due to the inflexibility to time-varying item arrivals and the low efficiency for high throughput. In this paper, we propose a new task planning problem called TPRW, which aims to minimize the end-to-end makespan that incorporates the entire item distribution pipeline, known as a fulfilment cycle. Direct extensions from state-of-the-art path finding methods are ineffective to solve the TPRW problem because they fail to adapt to the bottleneck variations of fulfillment cycles. In response, we propose Efficient Adaptive Task Planning, a framework for large-scale robotized warehouses with time-varying item arrivals. It adaptively selects racks to fulfill at each timestamp via rein-forcement learning, accounting for the time-varying bottleneck of the fulfillment cycles. Then it finds paths for robots to transport the selected racks. The framework adopts a series of efficient optimizations on both time and memory to handle large-scale item throughput. Evaluations on both synthesized and real data show an improvement of 37.1% in effectiveness and 75.5% in efficiency over the state-of-the-arts.

Following the success of convolution on non-Euclidean space, the corresponding pooling approaches have also been validated on various tasks regarding graphs. However, because of the fixed compression ratio and stepwise pooling design, these hierarchical pooling methods still suffer from local structure damage and suboptimal problem. In this work, inspired by structural entropy, we propose a hierarchical pooling approach, SEP, to tackle the two issues. Specifically, without assigning the layer-specific compression ratio, a global optimization algorithm is designed to generate the cluster assignment matrices for pooling at once. Then, we present an illustration of the local structure damage from previous methods in reconstruction of ring and grid synthetic graphs. In addition to SEP, we further design two classification models, SEP-G and SEP-N for graph classification and node classification, respectively. The results show that SEP outperforms state-of-the-art graph pooling methods on graph classification benchmarks and obtains superior performance on node classifications.

Document-level relation extraction aims to extract relations between entities in a document. In contrast to sentence-level relation extraction, it deals with longer texts and more complex entity interactions, which requires reasoning over multiple sentences with rich reasoning skills. Most current researches construct a document-level graph first, and then focus on the overall graph structure or the paths between the target entity pair in the graph. In this paper, we propose a novel subgraph reasoning (SGR) framework for document-level relation extraction. SGR combines the advantages of both graph-based models and path-based models, integrating various paths between the target entity pair into a much simpler subgraph structure to perform relational reasoning. Moreover, the paths generated by our designed heuristic strategy explicitly model the requisite reasoning skills and roughly cover the supporting sentences for each relation instance. Experimental results on DocRED show that SGR outperforms existing models, and further analyses demonstrate that our method is both effective and explainable. Our code is available at https://github.com/Crysta1ovo/SGR.

In deep neural networks, better results can often be obtained by increasing the complexity of previously developed basic models. However, it is unclear whether there is a way to boost performance by decreasing the complexity of such models. Intuitively, given a problem, a simpler data structure comes with a simpler algorithm. Here, we investigate the feasibility of improving graph classification performance while simplifying the learning process. Inspired by structural entropy on graphs, we transform the data sample from graphs to coding trees, which is a simpler but essential structure for graph data. Furthermore, we propose a novel message passing scheme, termed hierarchical reporting, in which features are transferred from leaf nodes to root nodes by following the hierarchical structure of coding trees. We then present a tree kernel and a convolutional network to implement our scheme for graph classification. With the designed message passing scheme, the tree kernel and convolutional network have a lower runtime complexity of O(n) than Weisfeiler-Lehman subtree kernel and other graph neural networks of at least O(hm). We empirically validate our methods with several graph classification benchmarks and demonstrate that they achieve better performance and lower computational consumption than competing approaches.

The increasing concerns on data security limit the sharing of data distributedly stored at multiple data owners and impede the scale of spatial queries over big urban data. In response, data federation systems have emerged to perform secure queries across multiple data owners leveraging secure multi-party computation. However, existing systems are designed for relational data. They are highly inefficient on spatial queries and limited in usability. In this demonstration, we introduce Hu-Fu, the first data federation system for secure spatial queries with high efficiency and usability. Hu-Fu is designed from the perspectives of the query user and the data owner for high usability and decomposes a spatial query into as many plaintext operators and as few secure operators as possible for high efficiency. We demonstrate the deployment and usage of Hu-Fu via cross-company taxi-calling, a popular smart city application.

Data isolation has become an obstacle to scale up query processing over big data, since sharing raw data among data owners is often prohibitive due to security concerns. A promising solution is to perform secure queries over a federation of multiple data owners leveraging secure multi-party computation (SMC) techniques, as evidenced by recent federation work over relational data. However, existing solutions are highly inefficient on spatial queries due to excessive secure distance operations for query processing and their usage of general-purpose SMC libraries for secure operation implementation. In this paper, we propose Hu-Fu, the first system for efficient and secure spatial query processing on a data federation. The idea is to decompose the secure processing of a spatial query into as many plaintext operations and as few secure operations as possible, where fewer secure operators are involved and all secure operators are implemented dedicatedly. As a working system, Hu-Fu supports not only query input in native SQL, but also heterogeneous spatial databases ( e.g. , PostGIS, Simba, GeoMesa, and SpatialHadoop) at the backend. Extensive experiments show that Hu-Fu usually outperforms the state-of-the-arts in running time and communication cost while guaranteeing security.

Dynamic ridesharing refers to services that arrange one-time shared rides on short notice. It underpins various real-world intelligent transportation applications such as car-pooling, food delivery and last-mile logistics. A core operation in dynamic ridesharing is the “insertion operator”. Given a worker and a feasible route which contains a sequence of origin-destination pairs from previous requests, the insertion operator inserts a new origin-destination pair from a newly arrived request into the current route such that certain objective is optimized. Common optimization objectives include minimizing the maximum/sum flow time of all requests and minimizing the total travel time of the worker. Despite its frequent usage, the insertion operator has a time complexity of$O(n^3)$, where$n$is the number of all requests assigned to the worker. The cubic running time of insertion fundamentally limits the efficiency of urban-scale dynamic ridesharing based applications. In this paper, we propose a novel partition framework and a dynamic programming based insertion with a time complexity of$O(n^2)$. We further improve the time efficiency of the insertion operator to$O(n)$harnessing efficient index structures, such as fenwick tree. Evaluations on two real-world large-scale datasets show that our methods can accelerate insertion by 1.5 to 998.1 times.

The problem of session-aware recommendation aims to predict users’ next click based on their current session and historical sessions. Existing session-aware recommendation methods have defects in capturing complex item transition relationships. Other than that, most of them fail to explicitly distinguish the effects of different historical sessions on the current session. To this end, we propose a novel method, named Personalized Graph Neural Networks with Attention Mechanism (A-PGNN) for brevity. A-PGNN mainly consists of two components: one is Personalized Graph Neural Network (PGNN), which is used to extract the personalized structural information in each user behavior graph, compared with the traditional Graph Neural Network (GNN) model, which considers the role of the user when the node embedding is updated. The other is Dot-Product Attention mechanism, which draws on the Transformer net to explicitly model the effect of historical sessions on the current session. Extensive experiments conducted on two real-world data sets show that A-PGNN evidently outperforms the state-of-the-art personalized session-aware recommendation methods.

There has been a dramatic growth of shared mobility applications such as ride-sharing, food delivery, and crowdsourced parcel delivery. Shared mobility refers to transportation services that are shared among users, where a central issue is route planning . Given a set of workers and requests, route planning finds for each worker a route, i.e., a sequence of locations to pick up and drop off passengers/parcels that arrive from time to time, with different optimization objectives. Previous studies lack practicability due to their conflicted objectives and inefficiency in inserting a new request into a route, a basic operation called insertion . In addition, previous route planning solutions fail to exploit the appearance patterns of future requests hidden in historical data for optimization. In this paper, we present a unified formulation of route planning called URPSM. It has a well-defined parameterized objective function which eliminates the contradicted objectives in previous studies and enables flexible multi-objective route planning for shared mobility. We propose two insertion-based frameworks to solve the URPSM problem. The first is built upon the plain-insertion widely used in prior studies, which processes online requests only, whereas the second relies on a new insertion operator called prophet-insertion that handles both online and predicted requests. Novel dynamic programming algorithms are designed to accelerate both insertions to only linear time. Theoretical analysis shows that no online algorithm can have a constant competitive ratio for the URPSM problem under the competitive analysis model, yet our prophet-insertion-based framework can achieve a constant optimality ratio under the instance-optimality model. Extensive experimental results on real datasets show that our insertion-based solutions outperform the state-of-the-art algorithms in both effectiveness and efficiency by a large margin (e.g., up to 30 \( \times \) more effective in the objective and up to 20 \( \times \) faster).

The great success of Transformer-based models benefits from the powerful multi-head self-attention mechanism, which learns token dependencies and encodes contextual information from the input. Prior work strives to attribute model decisions to individual input features with different saliency measures, but they fail to explain how these input features interact with each other to reach predictions. In this paper, we propose a self-attention attribution method to interpret the information interactions inside Transformer. We take BERT as an example to conduct extensive studies. Firstly, we apply self-attention attribution to identify the important attention heads, while others can be pruned with marginal performance degradation. Furthermore, we extract the most salient dependencies in each layer to construct an attribution tree, which reveals the hierarchical interactions inside Transformer. Finally, we show that the attribution results can be used as adversarial patterns to implement non-targeted attacks towards BERT.

Junjie Huang, Duyu Tang, Linjun Shou, Ming Gong, Ke Xu, Daxin Jiang, Ming Zhou, Nan Duan. Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers). 2021.

Recent studies on compression of pretrained language models (e.g., BERT) usually use preserved accuracy as the metric for evaluation.In this paper, we propose two new metrics, label loyalty and probability loyalty that measure how closely a compressed model (i.e., student) mimics the original model (i.e., teacher).We also explore the effect of compression with regard to robustness under adversarial attacks.We benchmark quantization, pruning, knowledge distillation and progressive module replacing with loyalty and robustness.By combining multiple compression techniques, we provide a practical strategy to achieve better accuracy, loyalty and robustness. 1

In this paper, we propose Sequence Span Rewriting (SSR), a self-supervised task for sequence-to-sequence (Seq2Seq) pre-training.SSR learns to refine the machine-generated imperfect text spans into ground truth text.SSR provides more fine-grained and informative supervision in addition to the original textinfilling objective.Compared to the prevalent text infilling objectives for Seq2Seq pretraining, SSR is naturally more consistent with many downstream generation tasks that require sentence rewriting (e.g., text summarization, question generation, grammatical error correction, and paraphrase generation).We conduct extensive experiments by using SSR to improve the typical Seq2Seq pre-trained model T5 in a continual pre-training setting and show substantial improvements over T5 on various natural language generation tasks. 1

Traditional learning-to-rank (LTR) models are usually trained in a centralized approach based upon a large amount of data. However, with the increasing awareness of data privacy, it is harder to collect data from multiple owners as before, and the resultant data isolation problem makes the performance of learned LTR models severely compromised. Inspired by the recent progress in federated learning, we propose a novel framework named Cross-Silo Federated Learning-to-Rank (CS-F-LTR), where the efficiency issue becomes the major bottleneck. To deal with the challenge, we first devise a privacy-preserving cross-party term frequency querying scheme based on sketching algorithms and differential privacy. To further improve the overall efficiency, we propose a new structure named reverse top-K sketch (RTK-Sketch) which significantly accelerates the feature generation process while holding theoretical guarantees on accuracy loss. Extensive experiments conducted on public datasets verify the effectiveness and efficiency of the proposed approach.

Spatial crowdsourcing has stimulated various new applications such as taxi calling and food delivery. A key enabler for these spatial crowdsourcing based applications is to plan routes for crowd workers to execute tasks given diverse requirements of workers and the spatial crowdsourcing platform. Despite extensive studies on task planning in spatial crowdsourcing, few have accounted for the location privacy of tasks, which may be misused by an untrustworthy platform. In this paper, we explore efficient task planning for workers while protecting the locations of tasks. Specifically, we define the Privacy-Preserving Task Planning (PPTP) problem, which aims at both total revenue maximization of the platform and differential privacy of task locations. We first apply the Laplacian mechanism to protect location privacy, and analyze its impact on the total revenue. Then we propose an effective and efficient task planning algorithm for the PPTP problem. Extensive experiments on both synthetic and real datasets validate the advantages of our algorithm in terms of total revenue and time cost.

Canwen Xu, Wangchunshu Zhou, Tao Ge, Ke Xu, Julian McAuley, Furu Wei. Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. 2021.

Automated evaluation of open domain natural language generation (NLG) models remains a challenge and widely used metrics such as BLEU and Perplexity can be misleading in some cases. In our paper, we propose to evaluate natural language generation models by learning to compare a pair of generated sentences by fine-tuning BERT, which has been shown to have good natural language understanding ability. We also propose to evaluate the model-level quality of NLG models with sample-level comparison results with skill rating system. While able to be trained in a fully self-supervised fashion, our model can be further fine-tuned with a little amount of human preference annotation to better imitate human judgment. In addition to evaluating trained models, we propose to apply our model as a performance indicator during training for better hyperparameter tuning and early-stopping. We evaluate our approach on both story generation and chit-chat dialogue response generation. Experimental results show that our model correlates better with human preference compared with previous automated evaluation approaches. Training with the proposed metric yields better performance in human evaluation, which further demonstrates the effectiveness of the proposed model.

Question Answering (QA) has shown great success thanks to the availability of largescale datasets and the effectiveness of neural models.Recent research works have attempted to extend these successes to the settings with few or no labeled data available.In this work, we introduce two approaches to improve unsupervised QA.First, we harvest lexically and syntactically divergent questions from Wikipedia to automatically construct a corpus of question-answer pairs (named as REFQA).Second, we take advantage of the QA model to extract more appropriate answers, which iteratively refines data over RE-FQA.We conduct experiments 1 on SQuAD 1.1, and NewsQA by fine-tuning BERT without access to manually annotated data.Our approach outperforms previous unsupervised approaches by a large margin and is competitive with early supervised models.We also show the effectiveness of our approach in the fewshot learning setting.

With spatial crowdsourcing applications such as Uber and Waze deeply penetrated into everyday life, there is a growing concern to protect user privacy in spatial crowdsourcing. Particularly, locations of workers and tasks should be properly processed via certain privacy mechanism before reporting to the untrusted spatial crowdsourcing server for task assignment. Privacy mechanisms typically permute the location information, which tends to make task assignment ineffective. Prior studies only provide guarantees on privacy protection without assuring the effectiveness of task assignment. In this paper, we investigate privacy protection for online task assignment with the objective of minimizing the total distance, an important task assignment formulation in spatial crowdsourcing. We design a novel privacy mechanism based on Hierarchically Well-Separated Trees (HSTs). We prove that the mechanism is ε-Geo-Indistinguishable and show that there is a task assignment algorithm with a competitive ratio of O(ε1/4log N log2k), where ε is the privacy budget, N is the number of predefined points on the HST, and k is the matching size. Extensive experiments on synthetic and real datasets show that online task assignment under our privacy mechanism is notably more effective in terms of total distance than under prior differentially private mechanisms.

There is a growing trend to deploy deep neural networks at the edge for high-accuracy, real-time data mining and user interaction. Applications such as speech recognition and language understanding often apply a deep neural network to encode an input sequence and then use a decoder to generate the output sequence. A promising technique to accelerate these applications on resource-constrained devices is network pruning, which compresses the size of the deep neural network without severe drop in inference accuracy. However, we observe that although existing network pruning algorithms prove effective to speed up the prior deep neural network, they lead to dramatic slowdown of the subsequent decoding and may not always reduce the overall latency of the entire application. To rectify such drawbacks, we propose entropy-based pruning, a new regularizer that can be seamlessly integrated into existing network pruning algorithms. Our key theoretical insight is that reducing the information entropy of the deep neural network outputs decreases the upper bound of the subsequent decoding search space. We validate our solution with two state-of-the-art network pruning algorithms on two model architectures. Experimental results show that compared with existing network pruning algorithms, our entropy-based pruning method notably suppresses and even eliminates the increase of decoding time, and achieves shorter overall latency with only negligible extra accuracy loss in the applications.

In this paper, we propose Patience-based Early Exit, a straightforward yet effective inference method that can be used as a plug-and-play technique to simultaneously improve the efficiency and robustness of a pretrained language model (PLM). To achieve this, our approach couples an internal-classifier with each layer of a PLM and dynamically stops inference when the intermediate predictions of the internal classifiers do not change for a pre-defined number of steps. Our approach improves inference efficiency as it allows the model to make a prediction with fewer layers. Meanwhile, experimental results with an ALBERT model show that our method can improve the accuracy and robustness of the model by preventing it from overthinking and exploiting multiple classifiers for prediction, yielding a better accuracy-speed trade-off compared to existing early exit methods.

Previous studies on lexical substitution tend to obtain substitute candidates by finding the target word's synonyms from lexical resources (e.g., WordNet) and then rank the candidates based on its contexts.These approaches have two limitations: (1) They are likely to overlook good substitute candidates that are not the synonyms of the target words in the lexical resources;(2) They fail to take into account the substitution's influence on the global context of the sentence.To address these issues, we propose an end-toend BERT-based lexical substitution approach which can propose and validate substitute candidates without using any annotated data or manually curated resources.Our approach first applies dropout to the target word's embedding for partially masking the word, allowing BERT to take balanced consideration of the target word's semantics and contexts for proposing substitute candidates, and then validates the candidates based on their substitution's influence on the global contextualized representation of the sentence.Experiments show our approach performs well in both proposing and ranking substitute candidates, achieving the state-of-the-art results in both LS07 and LS14 benchmarks.

Yaru Hao, Li Dong, Furu Wei, Ke Xu. Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP). 2019.

Online bipartite graph matching is attracting growing research attention due to the development of dynamic task assignment in sharing economy applications, where tasks need be assigned dynamically to workers. Past studies lack practicability in terms of both problem formulation and solution framework. On the one hand, some problem settings in prior online bipartite graph matching research are impractical for real-world applications. On the other hand, existing solutions to online bipartite graph matching are inefficient due to the unnecessary real-time decision making. In this paper, we propose the dynamic bipartite graph matching (DBGM) problem to be better aligned with real-world applications and devise a novel adaptive batch-based solution framework with a constant competitive ratio. As an effective and efficient implementation of the solution framework, we design a reinforcement learning based algorithm, called Restricted Q-learning (RQL), which makes near-optimal decisions on batch splitting. Extensive experimental results on both real and synthetic datasets show that our methods outperform the state-of-the-arts in terms of both effectiveness and efficiency.

Dynamic ridesharing refers to services that arrange one-time shared rides on short notice. It underpins various real-world intelligent transportation applications such as car-pooling, food delivery and last-mile logistics. A core operation in dynamic ridesharing is the "insertion operator". Given a worker and a feasible route which contains a sequence of origin-destination pairs from previous requests, the insertion operator inserts a new origin-destination pair from a newly arrived request into the current route such that certain objective is optimized. Common optimization objectives include minimizing the maximum flow time of all requests and minimizing the total travel time of the worker. Despite its frequent usage, the insertion operator has a time complexity of O(n^3), where n is the number of all requests assigned to the worker. The cubic running time of insertion fundamentally limits the efficiency of urban-scale dynamic ridesharing based applications. In this paper, we propose a novel partition framework and a dynamic programming based insertion with a time complexity of O(n^2). We further improve the time efficiency of the insertion operator to O(n) harnessing efficient index structures, such as fenwick tree. Evaluations on two real-world large-scale datasets show that our methods can accelerate insertion by 1.5 to 998.1 times.

BACKGROUND: Biomedical named entity recognition (BioNER) is a fundamental and essential task for biomedical literature mining, which affects the performance of downstream tasks. Most BioNER models rely on domain-specific features or hand-crafted rules, but extracting features from massive data requires much time and human efforts. To solve this, neural network models are used to automatically learn features. Recently, multi-task learning has been applied successfully to neural network models of biomedical literature mining. For BioNER models, using multi-task learning makes use of features from multiple datasets and improves the performance of models. RESULTS: In experiments, we compared our proposed model with other multi-task models and found our model outperformed the others on datasets of gene, protein, disease categories. We also tested the performance of different dataset pairs to find out the best partners of datasets. Besides, we explored and analyzed the influence of different entity types by using sub-datasets. When dataset size was reduced, our model still produced positive results. CONCLUSION: We propose a novel multi-task model for BioNER with the cross-sharing structure to improve the performance of multi-task models. The cross-sharing structure in our model makes use of features from both datasets in the training procedure. Detailed analysis about best partners of datasets and influence between entity categories can provide guidance of choosing proper dataset pairs for multi-task training. Our implementation is available at https://github.com/JogleLew/bioner-cross-sharing .

The maximum clique problem (MaxClique for short) consists of searching for a maximum complete subgraph in a graph. A branch-and-bound (BnB) MaxClique algorithm computes an upper bound of the number of vertices of a maximum clique at every search tree node, to prune the subtree rooted at the node. Existing upper bounds are usually computed from scratch at every search tree node. In this paper, we define an incremental upper bound, called IncUB, which is derived efficiently from previous searches instead of from scratch. Then, we describe a new BnB MaxClique algorithm, called IncMC2, which uses graph coloring and MaxSAT reasoning to filter out the vertices that do not need to be branched on, and uses IncUB to prune the remaining branches. Our experimental results show that IncMC2 is significantly faster than algorithms such as BBMC and IncMaxCLQ. Finally, we carry out experiments to provide evidence that the performance of IncMC2 is due to IncUB. The online supplement is available at https://doi.org/10.1287/ijoc.2017.0770 .

There has been a dramatic growth of shared mobility applications such as ride-sharing, food delivery and crowdsourced parcel delivery. Shared mobility refers to transportation services that are shared among users, where a central issue is route planning . Given a set of workers and requests, route planning finds for each worker a route, i.e. , a sequence of locations to pick up and drop off passengers/parcels that arrive from time to time, with different optimization objectives. Previous studies lack practicability due to their conflicted objectives and inefficiency in inserting a new request into a route, a basic operation called insertion . In this paper, we present a unified formulation of route planning called URPSM. It has a well-defined parameterized objective function which eliminates the contradicted objectives in previous studies and enables flexible multi-objective route planning for shared mobility. We prove the problem is NP-hard and there is no polynomial-time algorithm with constant competitive ratio for the URPSM problem and its variants. In response, we devise an effective and efficient solution to address the URPSM problem approximately. We design a novel dynamic programming (DP) algorithm to accelerate the insertion operation from cubic or quadric time in previous work to only linear time. On basis of the DP algorithm, we propose a greedy based solution to the URPSM problem. Experimental results on real datasets show that our solution outperforms the state-of-the-arts by 1.2 to 12.8 times in effectiveness, and also runs 2.6 to 20.7 times faster.

Aspect-based opinion mining is finding elaborate opinions towards a subject such as a product or an event. With explosive growth of opinionated texts on the Web, mining aspect-level opinions has become a promising means for online public opinion analysis. In particular, the boom of various types of online media provides diverse yet complementary information, bringing unprecedented opportunities for cross media aspect-opinion mining. Along this line, we propose CAMEL, a novel topic model for complementary aspect-based opinion mining across asymmetric collections. CAMEL gains information complementarity by modeling both common and specific aspects across collections, while keeping all the corresponding opinions for contrastive study. An auto-labeling scheme called AME is also proposed to help discriminate between aspect and opinion words without elaborative human labeling, which is further enhanced by adding word embedding-based similarity as a new feature. Moreover, CAMEL-DP, a nonparametric alternative to CAMEL is also proposed based on coupled Dirichlet Processes. Extensive experiments on real-world multi-collection reviews data demonstrate the superiority of our methods to competitive baselines. This is particularly true when the information shared by different collections becomes seriously fragmented. Finally, a case study on the public event “2014 Shanghai Stampede” demonstrates the practical value of CAMEL for real-world applications.

Li Dong, Shaohan Huang, Furu Wei, Mirella Lapata, Ming Zhou, Ke Xu. Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 1, Long Papers. 2017.

The prevalence of mobile Internet techniques and Online-To-Offline (O2O) business models has led the emergence of various spatial crowdsourcing (SC) platforms in our daily life. A core issue of SC is to assign real-time tasks to suitable crowd workers. Existing approaches usually focus on the matching of two types of objects, tasks and workers, or assume the static offline scenarios, where the spatio-temporal information of all the tasks and workers is known in advance. Recently, some new emerging O2O applications incur new challenges: SC platforms need to assign three types of objects, tasks, workers and workplaces, and support dynamic real-time online scenarios, where the existing solutions cannot handle. In this paper, based on the aforementioned challenges, we formally define a novel dynamic online task assignment problem, called the trichromatic online matching in real-time spatial crowdsourcing (TOM) problem, which is proven to be NP-hard. Thus, we first devise an efficient greedy online algorithm. However, the greedy algorithm can be trapped into local optimal solutions easily. We then present a threshold-based randomized algorithm that not only guarantees a tighter competitive ratio but also includes an adaptive optimization technique, which can quickly learn the optimal threshold for the randomized algorithm. Finally, we verify the effectiveness and efficiency of the proposed methods through extensive experiments on real and synthetic datasets.

With the rapid development of mobile internet and online to offline marketing model, various spatial crowdsourcing platforms, such as Gigwalk and Gmission, are getting popular. Most existing studies assume that spatial crowdsourced tasks are simple and trivial. However, many real crowdsourced tasks are complex and need to be collaboratively finished by a team of crowd workers with different skills. Therefore, an important issue of spatial crowdsourcing platforms is to recommend some suitable teams of crowd workers to satisfy the requirements of skills in a task. In this paper, to address the issue, we first propose a more practical problem, called Top-k team recommendation in spatial crowdsourcing (Top k TR) problem. We prove that the Top k TR problem is NP-hard and designs a two-level-based framework, which includes an approximation algorithm with provable approximation ratio and an exact algorithm with pruning techniques to address it. In addition, we study a variant of the Top k TR problem, called Top k TRL, where a team leader is appointed among each recommended team of crowd workers in order to coordinate different crowd workers conveniently, and the aforementioned framework can be extended to address this variant. Finally, we verify the effectiveness and efficiency of the proposed methods through extensive experiments on real and synthetic datasets.

Recently, crowdsourcing platforms have attracted a number of citizens to perform a variety of location-specific tasks. However, most existing approaches consider the arrangement of a set of tasks for a set of crowd workers, while few consider crowd workers arriving in a dynamic manner. Therefore, how to arrange suitable location-specific tasks to a set of crowd workers such that the crowd workers obtain maximum satisfaction when arriving sequentially represents a challenge. To address the limitation of existing approaches, we first identify a more general and useful model that considers not only the arrangement of a set of tasks to a set of crowd workers, but also all the dynamic arrivals of all crowd workers. Then, we present an effective crowd-task model which is applied to offline and online settings, respectively. To solve the problem in an offline setting, we first observe the characteristics of task planning (CTP) and devise a CTP algorithm to solve the problem. We also propose an effective greedy method and integrated simulated annealing (ISA) techniques to improve the algorithm performance. To solve the problem in an online setting, we develop a greedy algorithm for task planning. Finally, we verify the effectiveness and efficiency of the proposed solutions through extensive experiments using real and synthetic datasets.

The popularity of Online To Offline (O2O) service platforms has spurred the need for online task assignment in real-time spatial data, where streams of spatially distributed tasks and workers are matched in real time such that the total number of assigned pairs is maximized. Existing online task assignment models assume that each worker is either assigned a task immediately or waits for a subsequent task at a fixed location once she/he appears on the platform. Yet in practice a worker may actively move around rather than passively wait in place if no task is assigned. In this paper, we define a new problem Flexible Two-sided Online task Assignment (FTOA). FTOA aims to guide idle workers based on the prediction of tasks and workers so as to increase the total number of assigned worker-task pairs. To address the FTOA problem, we face two challenges: (i) How to generate guidance for idle workers based on the prediction of the spatiotemporal distribution of tasks and workers? (ii) How to leverage the guidance of workers' movements to optimize the online task assignment? To this end, we propose a novel two-step framework, which integrates offline prediction and online task assignment. Specifically, we estimate the distributions of tasks and workers per time slot and per unit area, and design an online task assignment algorithm, Prediction-oriented Online task Assignment in Real-time spatial data (POLAR-OP). It yields a 0.47-competitive ratio, which is nearly twice better than that of the state-of-the-art. POLAR-OP also reduces the time complexity to process each newly-arrived task/worker to O(1). We validate the effectiveness and efficiency of our methods via extensive experiments on both synthetic datasets and real-world datasets from a large-scale taxi-calling platform.

Recent years have witnessed the unprecedented growth of online social media, which empower short texts as the prevalent format for information of Internet. Given the nature of sparsity, however, short text topic modeling remains a critical yet much-watched challenge in both academy and industry. Rich research efforts have been put on building different types of probabilistic topic models for short texts, among which the self aggregation methods without using auxiliary information become an emerging solution for providing informative cross-text word co-occurrences. However, models along this line are still rarely seen, and the representative one Self-Aggregation Topic Model (SATM) is prone to overfitting and computationally expensive. In light of this, in this paper, we propose a novel probabilistic model called Pseudo-document-based Topic Model (PTM) for short text topic modeling. PTM introduces the concept of pseudo document to implicitly aggregate short texts against data sparsity. By modeling the topic distributions of latent pseudo documents rather than short texts, PTM is expected to gain excellent performance in both accuracy and efficiency. A Sparsity-enhanced PTM (SPTM for short) is also proposed by applying Spike and Slab prior, with the purpose of eliminating undesired correlations between pseudo documents and latent topics. Extensive experiments on various real-world data sets with state-of-the-art baselines demonstrate the high quality of topics learned by PTM and its robustness with reduced training samples. It is also interesting to show that i) SPTM gains a clear edge over PTM when the number of pseudo documents is relatively small, and ii) the constraint that a short text belongs to only one pseudo document is critically important for the success of PTM. We finally take an in-depth semantic analysis to unveil directly the fabulous function of pseudo documents in finding cross-text word co-occurrences for topic modeling.

Recently, MaxSAT reasoning is shown very effective in computing a tight upper bound for a Maximum Clique (MC) of a (unweighted) graph. In this paper, we apply MaxSAT reasoning to compute a tight upper bound for a Maximum Weight Clique (MWC) of a wighted graph. We first study three usual encodings of MWC into weighted partial MaxSAT dealing with hard clauses, which must be satisfied in all solutions, and soft clauses, which are weighted and can be falsified. The drawbacks of these encodings motivate us to propose an encoding of MWC into a special weighted partial MaxSAT formalism, called LW (Literal-Weighted) encoding and dedicated for upper bounding an MWC, in which both soft clauses and literals in soft clauses are weighted. An optimal solution of the LW MaxSAT instance gives an upper bound for an MWC, instead of an optimal solution for MWC. We then introduce two notions called the Top-k literal failed clause and the Top-k empty clause to extend classical MaxSAT reasoning techniques, as well as two sound transformation rules to transform an LW MaxSAT instance. Successive transformations of an LW MaxSAT instance driven by MaxSAT reasoning give a tight upper bound for the encoded MWC. The approach is implemented in a branch-and-bound algorithm called MWCLQ. Experimental evaluations on the broadly used DIMACS benchmark, BHOSLIB benchmark, random graphs and the benchmark from the winner determination problem show that our approach allows MWCLQ to reduce the search space significantly and to solve MWC instances effectively. Consequently, MWCLQ outperforms state-of-the-art exact algorithms on the vast majority of instances. Moreover, it is surprisingly effective in solving hard and dense instances.

Recently, with the development of mobile Internet and smartphones, the online minimum bipartite matching in real time spatial data (OMBM) problem becomes popular. Specifically, given a set of service providers with specific locations and a set of users who dynamically appear one by one, the OMBM problem is to find a maximum-cardinality matching with minimum total distance following that once a user appears, s/he must be immediately matched to an unmatched service provider, which cannot be revoked, before subsequent users arrive. To address this problem, existing studies mainly focus on analyzing the worst-case competitive ratios of the proposed online algorithms, but study on the performance of the algorithms in practice is absent. In this paper, we present a comprehensive experimental comparison of the representative algorithms of the OMBM problem. Particularly, we observe a surprising result that the simple and efficient greedy algorithm, which has been considered as the worst due to its exponential worst-case competitive ratio, is significantly more effective than other algorithms. We investigate the results and further show that the competitive ratio of the worst case of the greedy algorithm is actually just a constant, 3.195, in the average-case analysis. We try to clarify a 25-year misunderstanding towards the greedy algorithm and justify that the greedy algorithm is not bad at all. Finally, we provide a uniform implementation for all the algorithms of the OMBM problem and clarify their strengths and weaknesses, which can guide practitioners to select appropriate algorithms for various scenarios.

Recursive neural network models have achieved promising results in many natural language processing tasks. The main difference among these models lies in the composition function, i.e., how to obtain the vector representation for a phrase or sentence using the representations of words it contains. This paper introduces a novel Adaptive Multi-Compositionality (AdaMC) layer to recursive neural network models. The basic idea is to use more than one composition function and adaptively select them depending on input vectors. We develop a general framework to model the semantic composition as a distribution of these composition functions. The composition functions and parameters used for adaptive selection are jointly learnt from the supervision of specific tasks. We integrate AdaMC into existing recursive neural network models and conduct extensive experiments on the Stanford Sentiment Treebank and semantic relation classification task. The experimental results demonstrate that AdaMC improves the performance of recursive neural network models and outperforms the baseline methods.

Li Dong, Furu Wei, Ming Zhou, Ke Xu. Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers). 2015.

Aspect-based opinion mining is to find elaborate opinions towards an underlying theme, perspective or viewpoint as to a subject such as a product or an event. Nowadays, with rapid growing of opinionated text on the Web, mining aspect-level opinions has become a promising means for online public opinion analysis. In particular, the booming of various types of online media provide diverse yet complementary information, bringing unprecedented opportunities for public opinion analysis across different populations. Along this line, in this paper, we propose CAMEL, a novel topic model for complementary aspect-based opinion mining across asymmetric collections. CAMEL gains complementarity by modeling both common and specific aspects across different collections, and keeping all the corresponding opinions for contrastive study. To further boost CAMEL, we propose AME, an automatic labeling scheme for maximum entropy model, to help discriminate aspect and opinion words without heavy human labeling. Extensive experiments on synthetic multicollection data sets demonstrate the superiority of CAMEL to baseline methods, in leveraging cross-collection complementarity to find higher-quality aspects and more coherent opinions as well as aspect-opinion relationships. This is particularly true when the collections get seriously imbalanced. Experimental results also show that the AME model indeed outperforms manual labeling in suggesting true opinion words. Finally, case study on two public events further demonstrates the practical value of CAMEL for real-world public opinion analysis.

We present a statistical parsing framework for sentence-level sentiment classification in this article. Unlike previous works that use syntactic parsing results for sentiment analysis, we develop a statistical parser to directly analyze the sentiment structure of a sentence. We show that complicated phenomena in sentiment analysis (e.g., negation, intensification, and contrast) can be handled the same way as simple and straightforward sentiment expressions in a unified and probabilistic way. We formulate the sentiment grammar upon Context-Free Grammars (CFGs), and provide a formal description of the sentiment parsing framework. We develop the parsing model to obtain possible sentiment parse trees for a sentence, from which the polarity model is proposed to derive the sentiment strength and polarity, and the ranking model is dedicated to selecting the best sentiment tree. We train the parser directly from examples of sentences annotated only with sentiment polarity labels but without any syntactic annotations or polarity annotations of constituents within sentences. Therefore we can obtain training data easily. In particular, we train a sentiment parser, s.parser, from a large amount of review sentences with users' ratings as rough sentiment polarity labels. Extensive experiments on existing benchmark data sets show significant improvements over baseline sentiment classification approaches.

Summary In delay tolerant networks, most of the existing message forwarding algorithms prefer to deliver messages to the nodes with a higher popularity or centrality in the hope of maximizing the delivery ratio or minimizing the end‐to‐end delay. This forwarding scheme is prone to cause unfair load distribution and further lead to network congestion, overlooked in the previous work. In this paper, we discuss the network congestion from a community perspective and take it into account the design of message forwarding algorithms. We first put forward a novel distributed community detection approach, which could track the evolution of communities. Based on the identified communities, we develop a congestion avoidance mechanism to divert the load away from the congested areas to the alternative custodians and further present a congestion‐aware message forwarding algorithm where messages can avoid being transmitted to the congested nodes. We finally evaluate the effectiveness of distributed community detection and congestion‐aware message forwarding through the extensive real‐trace driven simulations. Copyright © 2015 John Wiley & Sons, Ltd.

In Delay Tolerant Networks (DTNs), the connections between mobile nodes are always disrupted and constant end-to-end paths rarely exist. In order to cope with these communication challenges, most existing DTN routing algorithms favour the “multi-hop forwarding” fashion where a message can be forwarded by multiple relay nodes in the hope that one of the employed relay nodes can deliver the message to the destination node. Since aggressively employing relay nodes may incur the intolerable delivery cost in DTNs, it is meaningful to design a cost-efficient routing algorithm that can achieve a high delivery performance. In this paper, we first design a novel delivery metric to measure the forwarding capability of nodes. Then, we utilize small-world properties to design the principles of relay node selection, e.g., limiting the number of relays and finding the appropriate relay nodes, and further develop a cost-efficient social-aware forwarding algorithm called TBSF. Extensive simulations on real mobility traces are conducted to evaluate the performance of TBSF, and the results demonstrate its efficiency and usefulness.

In mobile social networks (MSN), with the aim of conserving limited resources, egotistic nodes might refuse to forward messages for other nodes. Different from previous work which mainly focuses on promoting cooperation between selfish nodes, we consider it from a more pragmatic perspective in this paper. Be specific, we regard selfishness as a native attribute of a system and allow nodes to exhibit selfish behavior in the process of message forwarding. Apparently, selfishness has a profound influence on routing efficiency, and thus novel mechanisms are necessary to improve routing performance when self-centered nodes are considered. We first put forward a stateless approach to measure encounter opportunities between nodes, and represent forwarding capabilities of nodes by combining the acquired encounter opportunities with node selfishness. We then quantify receiving capabilities of nodes based on their available buffer size and energy. Taking both forwarding and receiving capabilities into account, we finally present a forwarding set mechanism, which could be deduced to a multiple knapsack problem to maximize the forwarding profit. Consequently, we take all the above studies into the design of a context-aware message forwarding algorithm (CAMF). Extensive trace-driven simulations show that CAMF outperforms other existing algorithms greatly. In fact, it achieves a surprisingly high routing performance while consumes low transmission cost and resource in MSN.

Recursive neural models have achieved promising results in many natural language processing tasks. The main difference among these models lies in the composition function, i.e., how to obtain the vector representation for a phrase or sentence using the representations of words it contains. This paper introduces a novel Adaptive Multi-Compositionality (AdaMC) layer to recursive neural models. The basic idea is to use more than one composition functions and adaptively select them depending on the input vectors. We present a general framework to model each semantic composition as a distribution over these composition functions. The composition functions and parameters used for adaptive selection are learned jointly from data. We integrate AdaMC into existing recursive neural models and conduct extensive experiments on the Stanford Sentiment Treebank. The results illustrate that AdaMC significantly outperforms state-of-the-art sentiment classification methods. It helps push the best accuracy of sentence-level negative/positive classification from 85.4% up to 88.5%.

The tremendous development of online social media have changed people's life fundamentally in recent years. Weibo, a Twitter-like service in China, has attracted more than 500 million users in less than four years and produces more than 100 million Chinese tweets every day. In these massive tweets, different user interests and daily trends are reflected by different topics. While to our best knowledge, a systematic investigation of topic dynamics in Weibo is still missing. Aiming at filling this vital gap, we try to disclose the evolving patterns of topics from the perspective of time, geography, gender, emotion and interaction. First, an incremental learning framework is established to classify more than 200 million tweets into seven topics fast and accurately, whose F-measure arrives as high as 84%. Second, many interesting patterns in topic dynamics are revealed. For instance, happy Entertainment accounts for over half of the tweets and angry Finance possesses the most significant periodic pattern. Besides, the female and male users prefer different topics and Finance shows a surprisingly high correlation between connected users. Finally, our findings could provide insights for the topic-related applications in social media, like event detection or content recommendation.

Study of reciprocity helps to find influential factors for users building relationships, which greatly facilitates the social behavior understanding in trust networks. In the previous literature, the dynamics of both network structure and user generated content are rarely considered. Our investigation of the available timing information from a real-world network demonstrates that time delay has significant impact on reciprocity formation. In particular, we find structural factors possess greater effect on short-term reciprocity while factors based on user generated content become more important for long-term reciprocity. Based on the empirical analysis, we redefine the reciprocity prediction problem as a learning task specific to each pair of users with different reciprocal delays. Evaluations show that our time-aware framework eventually outperforms the conventional classifiers that ignore the temporal information. Meanwhile, we tackle the problem of concept drift through fitting the evolving trend of features for Naive Bayes and performing periodic retraining for Logistic Regression classifiers, respectively.

There is huge amount of biomedical and biological literature online or in digital libraries. Moreover, new research papers are published with an exponential growth in recent years. So it is pressing and challenging to mine meaningful topics from massive biomedical literature. The mined topics are helpful to researchers for literature exploration and topic discovery. However, latent topics inferred by traditional topic models are not always coherent and meaningful. In this work, we propose a new methodology to mine meaningful biomedical topics with a combination of several off-the-shelf text mining techniques such as part-of-speech tagging, base noun phrase chunking, K-means clustering and latent Dirichlet allocation, which endow our methodology with scalability and implementation simplicity. We conduct comprehensive experiments on a dataset collected from PubMed. The experimental results demonstrate that our method significantly outperforms a baseline method. We also perform a qualitative analysis and present meaningful biomedical topics and multi-word expressions.

Satisfiability (SAT) and maximum satisfiability (MaxSAT) techniques are proved to be powerful in solving combinatorial optimization problems. In this paper, we encode the maximum weight clique (MWC) problem into weighted partial MaxSAT and use MaxSAT techniques to solve it. Concretely, we propose a new algorithm based on MaxSAT reasoning called Top-k failed literal detection to improve the upper bound for MWC, and implement an exact branch-and-bound solver for the MWC problem called MaxWClq based on the Top-k failed literal detection algorithm. To our best knowledge, this is the first time that MaxSat techniques are integrated to solve the MWC problem. Experimental evaluations on the broadly used DIMACS benchmark, BHOSLIB benchmark and random graphs show that MaxWClq outperforms state-of-the-art exact algorithms on the vast majority of instances. In particular, our algorithm is surprisingly powerful for dense and hard graphs.

DTNs are prone to congestion due to limited resource on each node and unpredictable end-to-end delay. We aim to develop an effective congestion control mechanism in this paper. For this purpose, we first identify a list of major congestion factors by analyzing the causes of congestion. We then model the congestion control as a multiple attribute decision making problem (MADM), in which the weight of congestion factors is measured by an entropy method. To solve this problem, we present a MADM-based congestion control mechanism that determines a set of forwarding messages and its transmission order on each encounter event. Moreover, we design a buffer management scheme that deletes messages whose removal would incur the least impact to the network performance when the buffer overflows. Extensive real-trace driven simulation is conducted and the experimental results finally validate the efficiency of our proposed congestion control mechanism.

Social-based routing protocols have shown their promising capability to improve the message delivery efficiency in Delay Tolerant Networks (DTNs). The efficiency greatly relies on the quality of the aggregated social graph that is determined by the metrics used to measure the strength of social connections. In this paper, we propose an improved metrics that leads to high-quality social graph by taking both frequency and duration of contacts into consideration. Furthermore, to improve the performance of social-based message transmission, we systematically study the community evolution problem that has been little investigated in the literation. Distributed algorithms based on the obtained social graph are developed such that the overlapping communities and bridge nodes (i.e., connecting nodes between communities) can be dynamically detected in an evolutionary social network. Finally, we take all the results above into our social-based routing design. Extensive trace-driven simulation results show that our routing algorithm outperforms existing social-based forwarding strategies significantly.

This paper targets at automatically detecting and classifying user's suggestions from tweets. The short and informal nature of tweets, along with the imbalanced characteristics of suggestion tweets, makes the task extremely challenging. To this end, we develop a classification framework on Factorization Machines, which is effective and efficient especially in classification tasks with feature sparsity settings. Moreover, we tackle the imbalance problem by introducing cost-sensitive learning techniques in Factorization Machines. Extensively experimental studies on a manually annotated real-life data set show that the proposed approach significantly improves the baseline approach, and yields the precision of 71.06% and recall of 67.86%. We also investigate the reason why Factorization Machines perform better. Finally, we introduce the first manually annotated dataset for suggestion classification.

In Delay Tolerant Networks (DTNs), the connections between mobile nodes are intermittent and constant end-to-end paths rarely exist. In order to achieve high delivery ratio, most existing DTN routing algorithms favor the ``multi-hop forwarding'' fashion where a message can be forwarded by multiple relay nodes in the hope that one of the employed relay nodes can deliver the message to the destination node. Since aggressively employing relay nodes may incur intolerable delivery cost to resource-constrained mobile nodes in DTNs, it is significant to design a cost-efficient routing protocol that can achieves high delivery ratio. In this paper, we first utilize the small-world feature to limit the maximum forwarding hops in a reasonable way and then propose a greedy relay node selection strategy. A cost-efficient social-aware forwarding algorithm called TBSF (the-best-so-far) is then presented. Extensive simulations on real mobility traces are conducted to evaluate the performance of TBSF. Simulation results show that, in comparison with several well-known routing algorithms, TBSF can achieve high performance in terms of delivery ratio and delivery delay while with much lower delivery cost.

Recently, MaxSAT reasoning has been shown to be powerful in computing upper bounds for the cardinality of a maximum clique of a graph. However, existing upper bounds based on MaxSAT reasoning have two drawbacks: (1)at every node of the search tree, MaxSAT reasoning has to be performed from scratch to compute an upper bound and is time-consuming, (2) due to the NP-hardness of the MaxSAT problem, MaxSAT reasoning generally cannot be complete at anode of a search tree, and may not give an upper bound tight enough for pruning search space. In this paper, we propose an incremental upper bound and combine it with MaxSAT reasoning to remedy the two drawbacks. The new approach is used to develop an efficient branch-and-bound algorithm for MaxClique, called IncMaxCLQ. We conduct experiments to show the complementarity of the incremental upper bound and MaxSAT reasoning and to compare IncMaxCLQ with several state-of-the-art algorithms for MaxClique.

Popularity prediction is a key problem in networks to analyze the information diffusion, especially in social media communities. Recently, there have been some custom-build prediction models in Digg and YouTube. However, these models are hardly transplant to an incomplete social network site (e.g., Flickr) by their unique parameters. In addition, because of the large scale of the network in Flickr, it is difficult to get all of the photos and the whole network. Thus, we are seeking for a method which can be used in such incomplete network. Inspired by a collaborative filtering method-Network-based Inference (NBI), we devise a weighted bipartite graph with undetected users and items to represent the resource allocation process in an incomplete network. Instead of image analysis, we propose a modified interdisciplinary models, called Incomplete Network-based Inference (INI). Using the data from 30 months in Flickr, we show the proposed INI is able to increase prediction accuracy by over 58.1%, compared with traditional NBI. We apply our proposed INI approach to personalized advertising application and show that it is more attractive than traditional Flickr advertising.

Recent years have witnessed the explosive growth of online social media. Weibo, a Twitter-like online social network in China, has attracted more than 300 million users in less than three years, with more than 1000 tweets generated in every second. These tweets not only convey the factual information, but also reflect the emotional states of the authors, which are very important for understanding user behaviors. However, a tweet in Weibo is extremely short and the words it contains evolve extraordinarily fast. Moreover, the Chinese corpus of sentiments is still very small, which prevents the conventional keyword-based methods from being used. In light of this, we build a system called MoodLens, which to our best knowledge is the first system for sentiment analysis of Chinese tweets in Weibo. In MoodLens, 95 emoticons are mapped into four categories of sentiments, i.e. angry, disgusting, joyful, and sad, which serve as the class labels of tweets. We then collect over 3.5 million labeled tweets as the corpus and train a fast Naive Bayes classifier, with an empirical precision of 64.3%. MoodLens also implements an incremental learning method to tackle the problem of the sentiment shift and the generation of new words. Using MoodLens for real-time tweets obtained from Weibo, several interesting temporal and spatial patterns are observed. Also, sentiment variations are well captured by MoodLens to effectively detect abnormal events in China. Finally, by using the highly efficient Naive Bayes classifier, MoodLens is capable of online real-time sentiment monitoring. The demo of MoodLens can be found at http://goo.gl/8DQ65.

The study of phase transition phenomenon of NP complete problems plays an important role in understanding the nature of hard problems. In this paper, we follow this line of research by considering the problem of counting solutions of Constraint Satisfaction Problems (#CSP). We consider the random model, i.e. RB model. We prove that phase transition of #CSP does exist as the number of variables approaches infinity and the critical values where phase transitions occur are precisely located. Preliminary experimental results also show that the critical point coincides with the theoretical derivation. Moreover, we propose an approximate algorithm to estimate the expectation value of the solutions number of a given CSP instance of RB model.

PageRank has been broadly applied to get credible rank sequences of nodes in many networks such as the web, citation networks, or online social networks. However, in the real world, it is usually hard to ascertain a complete structure of a network, particularly a large-scale one. Some researchers have begun to explore how to get a relatively accurate rank more efficiently. They have proposed some local approximation methods, which are especially designed for quickly estimating the PageRank value of a new node, after it is just added to the network. Yet, these local approximation methods rely on the link server too much, and it is difficult to use them to estimate rank sequences of nodes in a group. So we propose a new method called DIGRank, which uses global Degree to facilitate Ranking in an Incomplete Graph and which takes into account the frequent need for applications to rank users in a community, retrieve pages in a particular area, or mine nodes in a fractional or limited network. Based on experiments in small-world and scale-free networks generated by models, the DIGRank method performs better than other local estimation methods on ranking nodes in a given subgraph. In the models, it tends to perform best in graphs that have low average shortest path length, high average degree, or weak community structure. Besides, compared with an local PageRank and an advanced local approximation method, it significantly reduces the computational cost and error rate.

The mapping of the Internet topological structure is indeed of great importance for a better understanding of the network's internal structure, network management, etc. Current explorations still mainly rely on the extensive use of the traceroute tool from a given set of sources to a given set of destinations. However, the deployment of dedicated measurement infrastructures on sources is often quite costly and too many sources may impose heavy burden on the network. And there is a diminishing-returns effect concerning sources. In addition, when using different sets of sources with the same size, the overall coverage of the sampled network may vary significantly. As a result, it is very important for a network topology discovery project to select a limited set of sources to detect more nodes and edges. In this paper, aiming to maximize the numbers of nodes and edges discovered when deploying a limited set of sources, we propose a novel delay-guiding method. This method for the first time uses the underlying physical link delay between the source and a small number of landmarks as the metric to make source selection decisions. It incurs little extra traffic to the network because only the delay from the sources to a small number of landmarks is needed, which makes it very practical in real network topology discovery. We also compare our method with other known methods on both real datasets and synthetic datasets. The results show that our method is significantly more effective than the existing methods.

Page Rank has been widely used in ranking retrieval results on the web, finding the top influential papers in citation networks or detecting valuable users in online social networks. However, in practice, it is usually hard to obtain a complete structure of any above networks to rank nodes. Thus, some researchers have begun to explore how to get estimated ranks efficiently without acquiring the whole network. They have proposed some approximating methods, however, it is difficult to determine which method is the best one or which is suitable to a certain application. In this case, we set experiments in small-world and scale-free generated networks to certify the feasibility and characteristics of four approximating methods. We also use eleven real networks to mention different optimal conditions for these methods. We find the DIG Rank method performs better than other local estimation methods in almost every given sub graph. Besides, Mean field approach method tends to perform well in networks that have low average shortest path length, small amount of nodes with the same low in degree, or weak community structure. Finally, we apply the most versatile method DIG Rank to Sina micro-blog website to precisely classify users in a group as elites, grassroots or mummy users.

Considerable effort has been spent on collecting all the information of routers by using traceroute-like probes in the router-level topology measurements. This method has been argued to introduce uncontrolled sampling biases on statistical properties of the sample graph and heavy load to the network being measured. In order to improve the quality of the maps induced by the method, researchers are starting to investigate the deployment of large-scale distributed systems. But the lack of sources, the additional load introduced to the network and the potential uncontrolled scale in the IPv6 network cast a shadow over this direction. In this paper, we study traceroute sampling to represent the topology. Instead of finding a general strategy that would match all the graph properties, we focus on testing the impact of the proportion of destinations and sources on a single or several properties of the graph. We argue that, in order to obtain a more accurate sample graph, the general method of taking a small set of sources to perform traceroute-like probes to a large set of destinations is very unreasonable. Our results obtained from simulated experiments show that as the proportion of destinations and sources increases, the resulting properties of the sample graph can differ sharply from the underlying graph. The results also show that there is no single perfect proportion answer to meet all the graph properties but the small often perform better than the large overall. When we do the same measurement on several real-world networks, we find strong evidence for sampling bias because of taking so many destinations.

Internet topology plays a vital role in studying network's internal structure and properties. Currently traceroute-based topology discovery is the main approach to map the network. However, the deployments of probing sources are usually quite costly and complex. Even if the total numbers of sources are the same, the overall coverage of the sampled network may vary significantly for different sources. As a result, it is of great importance for a topology discovery project to select a limited set of probing sources to detect more nodes and links. The aim of this paper is to investigate how to select a fixed set of probing sources to maximize the coverage of the sampled network. We propose a novel logic distance-based method to make source placement decisions. Also we evaluate our approach and compare it with other known methods on real network topology and generated topologies.

Since media data in streaming media system are high volume and latency sensitive, transmission security of them have been a challenge task. To solve the problem, partial encryption and other media encryption schemes have been proposed. However those schemes are tradeoffs between security and efficiency. In a multi-stream system, using one media encryption scheme to protect all the media streams will induce either unscalability or insecurity. In this paper, the idea of partial encryption is generalized from encrypting a subset of one stream to multi-streams. A mathematical model based dynamic optimal selective control mechanism for multi-datastream security is proposed. Since the simplified model is 0-1 knapsack problem, which is NP-hard, a greedy heuristic incremental approximate algorithm is designed. Theoretical and experimental analyses show the performance of the algorithm is effective enough to support real-time applications. A prototype has been implemented in our Admire system, and used in a confidential project.

This paper describes a kernel based Web Services (abbrevi-ated as service) matching mechanism for service discoveryand integration. The matching mechanism tries to exploitthe latent semantics by the structure of services. Using textual similarity and n-spectrum kernel values as features of low-level and mid-level, we build up a model to estimate thefunctional similarity between services, whose parameters arelearned by a Ranking-SVM. The experiment results showedthat several metrics for the retrieval of services have beenimproved by our approach.

Alarm correlation plays an important role in improving the service and reliability in modern telecommunication networks. Most previous research of alarm correlation did not consider the effects of noise data in the database. This paper focuses on the method of discovering alarm correlation rules from a database containing noise data. We firstly define two parameters, win-freq and win-add, as the measures of noise data and then present a robust search algorithm to solve the problem. At different size of win-freq and win-add, the experiments on the alarm database containing noise data show that the robust search algorithm can discover more rules with the bigger size of win-add. We also compare, by experiments, two different interestingness measures of confidence and correlation.

In this paper we propose a new type of random CSP model, called Model RB, which is a revision to the standard Model B. It is proved that phase transitions from a region where almost all problems are satisfiable to a region where almost all problems are unsatisfiable do exist for Model RB as the number of variables approaches infinity. Moreover, the critical values at which the phase transitions occur are also known exactly. By relating the hardness of Model RB to Model B, it is shown that there exist a lot of hard instances in Model RB.