Motivated by the increasing risks of data misuse and fabrication, we investigate the problem of identifying synthetic time series generated by Time-Series Large Models (TSLMs) in this work. While there are extensive researches on detecting model generated text, we find that these existing methods are not applicable to time series data due to the fundamental modality difference, as time series usually have lower information density and smoother probability distributions than text data, which limit the discriminative power of token-based detectors. To address this issue, we examine the subtle distributional differences between real and model-generated time series and propose the contraction hypothesis, which states that model-generated time series, unlike real ones, exhibit progressively decreasing uncertainty under recursive forecasting. We formally prove this hypothesis under theoretical assumptions on model behavior and time series structure. Model-generated time series exhibit progressively concentrated distributions under recursive forecasting, leading to uncertainty contraction. We provide empirical validation of the hypothesis across diverse datasets. Building on this insight, we introduce the Uncertainty Contraction Estimator (UCE), a white-box detector that aggregates uncertainty metrics over successive prefixes to identify TSLM‑generated time series. Extensive experiments on 32 datasets show that UCE consistently outperforms state-of-the-art baselines, offering a reliable and generalizable solution for detecting model-generated time series.

Shared-nothing geo-distributed SQL databases, such as CockroachDB, are increasingly vital for enterprise applications requiring data resilience and locality. However, we encountered significant performance degradation at the customer side, especially when their deployments span multiple data centers over a Wide Area Network (WAN). Our investigation identifies the bottleneck in the performance of the Distributed Hash Join (Dist-HJ) algorithm, which is contingent upon a crucial balance between communication overhead and computational load. This balance is severely disrupted when processing skewed data from real-world customer workloads, leading to the observed performance decline. To tackle this challenge, we introduce Bala-Join, an adaptive solution to balance the computation and network load in Dist-HJ execution. Our approach consists of the Balanced Partition and Partial Replication (BPPR) algorithm and a distributed online skewed join key detector. The former achieves balanced redistribution of skewed data through a multicast mechanism to improve computational performance and reduce network overhead. The latter provides real-time skewed join key information tailored to BPPR. Furthermore, an Active-Signaling and Asynchronous-Pulling (ASAP) mechanism is incorporated to enable efficient, real-time synchronization between the detector and the redistribution process with minimal overhead. Empirical study shows that Bala-Join outperforms the popular Dist-HJ solutions, increasing throughput by 25%-61%.

Graph alignment, the task of identifying corresponding nodes across different graphs, is crucial for applications ranging from social network analysis to bioinformatics. Although most existing methods leverage graph neural networks (GNNs) to learn node embeddings for attributed graphs and match them based on node similarity, they often rely on objectives designed for node classification or link prediction. These approaches preserve node proximity within individual graphs but fail to capture cross-graph correspondence knowledge, leading to suboptimal alignment performance.

With the widespread use of social media platforms and people’s increasing dependence on them, social media has emerged as one of the most important channels for advertorials. However, there is currently a lack of research on detecting advertorials on social media platforms. This research focuses on detecting advertorials, a type of advertisement that frequently conceals itself within normal articles, blurring the nature of advertising and deceiving users. To effectively carry out research on advertorial detection, we have constructed a multi-topic advertorial dataset in Chinese with rich social information. This dataset is obtained from the Chinese question-answering platform ZHIHU, and it is publicly available to facilitate further research. 1 Furthermore, we propose AdDetector, a novel dual-tower model that detects advertorials by jointly leveraging the article’s textual and social information. In addition, we use fine-grained sentence-level classification labels to improve the model’s generalization capability on previously unseen topic articles. Experiment results show that our model significantly improves the \(F_1\) score by 1.29% in the intra-domain advertorial detection setting and 1.52% in the transfer setting in comparison with several strong baselines. The extensive ablation studies and thorough performance analyses also validate the complementary and beneficial values of the novel components of AdDetector. We also make our source code publicly available to facilitate future studies. 2 This research provides crucial support for user protection and advertising management.

Knowledge Graph Question Answering (KGQA) plays an important role in modern information service systems. However, due to the challenges in constructing Knowledge Graphs (KGs) and their rapid update pace, KGs often remain incomplete. Previous works on multi-hop KGQA on incomplete KGs tend to explore potential relations between topic entities and answers, so they are constrained by the limited set of entities in KGs. To address the issue, we propose a method that executes multi-hop KGQA over private-public KGs to expand the size of the available entity set while being privacy-preserving to the private KGs and the user query. To be specific, by embedding entities and relations in both private and public KGs and using the triple scoring function as a distance metric, we reduce multi-hop KGQA into the iterative information retrieval task and formulate the iterative inference module for this task. Extensive experiments demonstrate that our method achieves the absolute average accuracy increase of 15.4% on WebQuestionsSP and 24.4% on SimpleQuestions over state-of-the-art methods under various private-public settings while achieving no privacy leakage of user queries.

Recommender systems (RSs) are widely adopted due to their effectiveness in modeling user preferences and generating personalized recommendations. However, data poisoning attacks (PAs) manipulate recommendation results by injecting fake user profiles, thereby affecting the quality and accuracy of RSs. Moreover, emerging high-concealed PAs (HCPAs) achieve greater evasion of detection by controlling the cost of the attack, simulating the behavior patterns of benign users, and carrying out the attack with less prior knowledge. The HCPAs bring challenges: (1) the very low cost of attacks not only leads to an imbalance in data distribution but also introduces a large amount of accidental co-occurrence noise; (2) the behavioral patterns similar to benign users make it difficult to describe the characteristics of HCPAs; and (3) the prior knowledge for detecting HCPAs in real scenarios is very limited. To address these challenges, we propose STOP, an orthogonal projection bi-hypersphere detection method built on multi-view relational disentanglement and information-consistent fusion. First, we model the distributional preferences of user ratings to eliminate rating and popularity bias, and construct a co-occurrence association graph to suppress accidental overlaps. To address data imbalance caused by HCPAs, second, we introduce a distributional-consensus importance screening method that filters out benign users weakly associated with potential attackers. To address the issues of noise and the difficulty in feature characterization, third, we propose a multi-view relational disentanglement and information-consistent fusion method, which can eliminate redundant relationships, separate key relations into sequence-varying and sequence-stable components over rating sequences, and retain task-related relationships. Finally, inspired by the “convergence theorem”, we design an orthogonal projection bi-hypersphere boundary learning detection method to reduce the high false alarm rate (FAR). We extensively evaluate STOP under various HCPA scenarios, demonstrating its superiority over existing methods with an average 12.34% improvement in detection rate and an average 2.75% reduction in FAR. Furthermore, forensic analysis on real-world unlabeled data reveals distinct attacker “fingerprints”, such as extreme ratings, contradictory review styles, and analysis of target items, validating STOP's reliability in practical applications.

Computing the number of distinct elements (i.e., cardinality) in the intersection of two sets is a fundamental task in various distributed systems, including measuring origin-destination flows in wide-area networks and data synchronization in distributed databases. Due to the enormous data scale, lightweight probabilistic methods, such as FM sketch and HyperLogLog sketch, are extensively used in these systems to estimate the set intersection cardinality, with memory efficiency, high accuracy, and low communication costs. However, if a set's sketch and the hash functions used to construct the sketch are disclosed to an untrusted third party, the privacy of the set's sensitive elements may be compromised. Applying the differential privacy mechanism directly to safeguard the sketch's privacy may incur significant estimation errors. To address this challenge, we propose a novel private sketch,SetXor, for securely estimating intersection cardinality for static sets. Specifically, we incorporate the randomized response noise into the constructed sketch to achieve local differential privacy while ensuring ourSetXorsketch is mergeable. We establish a concrete probabilistic model to mitigate the estimation error caused by the noise and theoretically analyze the variance. We further propose a novel sketchSetXorDynenabling intersection cardinality estimation for streaming sets where elements appear sequentially and contain duplicates. We employ a sampling-like method to eliminate the impact of different parities of element occurrences, allowing us to handle all elements without bias. We conduct extensive experiments on synthetic and four real-world datasets. The results demonstrate that our methods reduce the Average Absolute Relative Error (AARE) of state-of-the-art baselines by up to$110\times$on synthetic datasets and$80\times$on real-world datasets, while achieving up to$18.7\times$speedup under the same settings.

Network intrusion detection systems (NIDS) are crucial for network management and security. However, in real-world scenarios, NIDS faces two core challenges: (i) label noise, where mislabeled samples in the training data distort the model's decision boundaries; (ii) unknown attack detection, where existing methods struggle to identify novel attack patterns in dynamic attack environments. More critically, these two challenges are interlinked, forming a vicious cycle that continuously degrades the overall reliability of NIDS. Existing research often addresses these issues in isolation, and no method has yet been proposed to coordinate their antagonistic effects systematically. To tackle this open problem, we propose AEGIS-Net for the first time—a dual anti-noise framework based on multi-prototype correction and model-agnostic detection. AEGIS-Net introduces a density-difference-driven multi-prototype competition mechanism, which achieves fine-grained noise label correction through feature space sub-cluster analysis. We also design a distribution-independent k-nearest neighbors detection paradigm, using the corrected compact feature space to determine unknown attacks in open environments. The two modules are collaboratively optimized through a shared encoder, forming a positive cycle of noise suppression and detection enhancement. Extensive experiments on real-world datasets validate the effectiveness of AEGIS-Net in addressing these dual challenges. Notably, under 50% asymmetric noise conditions, AEGIS-Net achieves classification accuracy of 89.02% for known attacks and 98.76% for unknown attack detection on the MAL_TLS2023 dataset. Theoretical proofs and visualization analysis reveal the anti-noise properties of AEGIS-Net under feature space stability constraints. Our code is available athttps://github.com/niebikong/AEGIS-Net.

An advertiser typically conducts a campaign across several publishers. Different publishers often reach different sets of persons, and some people may be exposed to the campaign via multiple publishers. Due to privacy restrictions, it is prohibited to collect all audience activities from multiple publishers in a centralized manner, therefore, we desire secure protocols for mining audience activities. In this paper, we propose a secure protocol for efficiently estimating the frequency histogram, i.e. the fraction of persons (or users) appearing a given number of times across all publishers. Our protocolMPC-FHis designed based on a novel sketch methodMPSthat uniformly samples a fraction of users across multiple parties and can be efficiently implemented on SPDZ, which is a popular secure multiparty computation (MPC) scheme. Our protocol provides more strict security guarantees than the state-of-the-art. In addition, our experimental results on a variety of large datasets demonstrate that our protocol can also accelerate the computation speed of existing protocols by orders of magnitudes.

Counting distinct elements (cardinality) across multiple data holders (DHs) privately is fundamental with broad applications, ranging from crowd counting to network monitoring. It is referred to as private distributed cardinality estimation (PDCE). Similarly, determining the intersection cardinality between the unions of two DH groups holds practical significance, a problem we call private distributed intersection cardinality estimation (PDICE). While many efficient methods (e.g., FM and LL sketches) exist, their differential privacy relies on secret hash functions. In PDCE, DHs must share the functions to enable sketch merging, which breaks this assumption and invalidates such guarantees. Although a recent protocol implements the FM sketch on a secret-sharing-based multiparty computation (MPC) framework for PDCE, we observe that it lacks differential privacy guarantees and is computationally expensive. To address these limitations, we propose DP-DICE-Bino, a novel protocol that is computationally efficient and differentially private for PDCE. DP-DICE-Bino is flexible in that it can compute the cardinality of any group of DHs without repeatedly interacting with the DHs. Furthermore, DP-DICE-Bino can also handle PDICE. Experiments show that DP-DICE-Bino achieves orders-of-magnitude speedups and reduces the estimation error by several times compared with the state of the art under the same security requirements.

Large Language Models (LLMs) have been widely adopted to enhance Task-Oriented Dialogue Systems (TODS) by modeling complex language patterns and delivering contextually appropriate responses. However, this integration introduces significant privacy risks, as LLMs, functioning as soft knowledge bases that compress extensive training data into rich knowledge representations, can inadvertently memorize training dialogue data containing not only identifiable information such as phone numbers but also entire dialogue-level events like complete travel schedules. Despite the critical nature of this privacy concern, how LLM memorization is inherited in developing task bots remains unexplored. In this work, we address this gap through a systematic quantitative study that involves evaluating existing training data extraction attacks, analyzing key characteristics of task-oriented dialogue modeling that render existing methods ineffective, and proposing novel attack techniques tailored for LLM-based TODS that enhance both response sampling and membership inference. Experimental results demonstrate the effectiveness of our proposed data extraction attack. Our method can extract thousands of training labels of dialogue states with best-case precision exceeding 70%. Furthermore, we provide an in-depth analysis of training data memorization in LLM-based TODS by identifying and quantifying key influencing factors and discussing targeted mitigation strategies.

Recommender systems are effective tools to alleviate the challenges posed by information overload, but data sparsity has greatly affected their performance. Knowledge Graphs (KGs) and self-supervised learning are used to alleviate the data sparsity problem. However, existing KG-enhanced self-supervised learning recommendation methods have the following limitations: (1) Generality : existing CL-based recommendation methods strongly rely on manually designed data augmentation strategies, leading to poor generality of the CL-based models. (2) Robustness : KG usually contains lots of task-irrelevant entities, and the user–item interactions constructed from implicit feedback are usually noisy. The noisy data will generate intrusive supervised and self-supervised signals and will degrade recommendation performance. To address these limitations, we propose a novel KG-enhanced self-supervised learning recommendation method, named Knowledge-Variational Contrastive Learning for Recommendation (KVCL) . Specifically, we first design an adaptively denoising mechanism to identify and prune the noisy data in the KG and user–item interaction bipartite graph. Then, we learn a normal distribution for each node by the variational auto-encoder, and sample multiple times from the learned distribution to obtain different contrastive views. Extensive experiments based on three public datasets show that KVCL achieves improved performance over state-of-the-art methods, notably with 3.13% performance gain over state-of-the-art methods on Recall@20 and NDCG@20. Furthermore, evaluations including ablation studies and detailed analyses of multi-scenarios, computational efficiency, complexity, and denoising interpretability further underscore its scalability and practical applicability.

Recommender systems (RSs), as crucial components of online services, can help users efficiently obtain information they may like. In reality, RSs face long-term threats. Attackers manipulate recommendation results by injecting malicious data in order to obtain benefits. At present, research on the security of RSs lacks a comprehensive understanding of attack capabilities. Moreover, existing defense strategies have not yet been systematically associated with attack characteristics. More importantly, existing defense methods rarely focus on real unlabeled data in practical application scenarios for anomaly detection and forensics. Therefore, this survey systematically analyzes the security of RSs and provides new insights. Specifically, we first categorize attack models from an attack perspective into: attack strategies based on targets, attack strategies against security and privacy, attack strategies based on prior knowledge, and attack strategies against other RSs. From a perspective of defense, existing detection models, second, can be divided into: behavioral representation based on statistics, detection based on hidden features, detection against privacy attacks, anomaly discovery based on association mining, and abnormality forensics for real-world data. Finally, we propose several potential research directions aimed at providing guidance for the security research of RSs. Additionally, to facilitate experimental reproducibility and comparative research, this survey also provides a repository of resources for attacks and defenses (https://github.com/xiaofengbbb/RS-Papers).

Large Language Models (LLMs) have impressive capabilities in text understanding and zero-shot reasoning. However, delays in knowledge updates may cause them to reason incorrectly or produce harmful results. Knowledge Graphs (KGs) provide rich and reliable contextual information for the reasoning process of LLMs by structurally organizing and connecting a wide range of entities and relations. Existing KG-based LLM reasoning methods only inject KGs' knowledge into prompts in a textual form, ignoring its structural information. Moreover, they mostly rely on close-source models or open-source models with large parameters, which poses challenges to high resource consumption. To address this, we propose a novel Lightweight and efficient Prompt learning-ReasOning Framework for KGQA (LightPROF), which leverages the full potential of LLMs to tackle complex reasoning tasks in a parameter-efficient manner. Specifically, LightPROF follows a “Retrieve-Embed-Reason” process, first accurately, and stably retrieving the corresponding reasoning graph from the KG through retrieval module. Next, through a Transformer-based Knowledge Adapter, it finely extracts and integrates factual and structural information from the KG, then maps this information to the LLM’s token embedding space, creating an LLM-friendly prompt to be used by the LLM for the final reasoning. Additionally, LightPROF only requires training Knowledge Adapter and can be compatible with any open-source LLM. Extensive experiments on two public KGQA benchmarks demonstrate that LightPROF achieves superior performance with small-scale LLMs. Furthermore, LightPROF shows significant advantages in terms of input token count and reasoning time.

Recent years have witnessed rapid advancements in the safety alignments of large language models (LLMs). Methods such as supervised instruction fine-tuning (SFT) and reinforcement learning with human feedback (RLHF) have thus emerged as vital components in constructing LLMs. While these methods achieve robust and fine-grained alignment to human values, their practical application is still hindered by high annotation costs and incomplete human alignments. Besides, the intrinsic human values within training corpora have not been fully exploited. To address these issues, we propose ISAAC (Intrinsically Supervised Alignments by Assessing Corpus), a primary and coarse-grained safety alignment strategy for LLMs. ISAAC only relies on a prior assumption about the text corpus, and does not require preferences in RLHF or human responses selection in SFT. Specifically, it assumes a long-tail distribution of text corpus and employs a specialized sampling strategy to automatically sample high-quality responses. Theoretically, we prove that this strategy can improve the safety of LLMs under our assumptions. Empirically, our evaluations on mainstream LLMs show that ISAAC achieves a safety score comparable to current SFT solutions. Moreover, we conduct experiments on ISAAC for some RLHF-based LLMs, where we find that ISAAC can even improve the safety of these models under specific safety domains. These findings demonstrate that ISAAC can provide preliminary alignment to LLMs, thereby reducing the construction costs of existing human-feedback-based methods.

Large Language Models (LLMs) may suffer from hallucinations in real-world applications due to the lack of relevant knowledge. In contrast, knowledge graphs encompass extensive, multi-relational structures that store a vast array of symbolic facts. Consequently, integrating LLMs with knowledge graphs has been extensively explored, with Knowledge Graph Question Answering (KGQA) serving as a critical touchstone for the integration. This task requires LLMs to answer natural language questions by retrieving relevant triples from knowledge graphs. However, existing methods face two significant challenges: *excessively long reasoning paths distracting from the answer generation*, and *false-positive relations hindering the path refinement*. In this paper, we propose an iterative interactive KGQA framework that leverages the interactive learning capabilities of LLMs to perform reasoning and Debating over Graphs (DoG). Specifically, DoG employs a subgraph-focusing mechanism, allowing LLMs to perform answer trying after each reasoning step, thereby mitigating the impact of lengthy reasoning paths. On the other hand, DoG utilizes a multi-role debate team to gradually simplify complex questions, reducing the influence of false-positive relations. This debate mechanism ensures the reliability of the reasoning process. Experimental results on five public datasets demonstrate the effectiveness and superiority of our architecture. Notably, DoG outperforms the state-of-the-art method ToG by 23.7% and 9.1% in accuracy on WebQuestions and GrailQA, respectively. Furthermore, the integration experiments with various LLMs on the mentioned datasets highlight the flexibility of DoG.

The advancement of 3D understanding and representation is a crucial step for the next phase of autonomous driving, robotics, augmented and virtual reality, 3D gaming and 3D e-commerce products. However, existing 3D semantic representation research has primarily focused on point clouds to perceive 3D objects and scenes, overlooking the rich visual details offered by multi-view images, thereby limiting the potential of 3D semantic representation. This paper introduces OpenView, a novel representation method that integrates both point clouds and multi-view images to form a unified 3D representation. OpenView comprises a unique fusion framework, sequence-independent modeling, a cross-modal fusion encoder, and a progressive hard learning strategy. Our experiments demonstrate that OpenView outperforms the state-of-the-art by 11.5% and 5.5% on the R@1 metric for cross-modal retrieval and the Top-1 metric for zero-shot classification tasks, respectively. Furthermore, we showcase some applications of OpenView: 3D retrieval, 3D captioning and hierarchical data clustering, highlighting its generality in the field of 3D representation learning.

Querying desired data from the key-value store on a cloud server is a prevalent scenario. Client queries might include sensitive information that the client prefers to keep confidential from the server. This occasion resembles the Keyword Private Information Retrieval (KPIR). Prior works on keyword PIR consider that there are no duplicated key-value pairs in the store, i.e., each key only occurs once with only a single value attached. This is one of the cases in practical applications. However, there is also a typical case where a key may occur multiple times with different values. Straightly applying the existing keyword PIR to this case doesn't work and may finally obtain a false query result. We are the first to extend the setting that keys in the store may appear with different values multiple times. To solve this problem, we propose FEDPIR, a fast single-server keyword PIR protocol that supports querying a large-scale key-value store with multiple values per key. FEDPIR uses a novel encoding and decoding strategy combined with a high-throughput linear homomorphic encryption to improve performance significantly. Our extensive experiments on different store configurations show that our FEDPIR achieves 1.2-65.6x lower query latency and 1.5-37.9x lower cost monetarily compared with the baseline methods.

Graph-level Contrastive Learning (GCL) has evolved as a powerful technique to derive representations from contrastive view pairs. Without access to labeled data, GCL typically takes two views augmented from the same graph as a positive pair and embeds them in nearby locations, while treating views from different graphs as negative pairs and pushing away their representations. Since the construction of contrastive pairs plays an important role in GCL, considerable attention has been paid to informative pairs mining. However, existing informative pairs mining methods suffer from the following two challenges: 1) Previous studies merely pay attention to the informative negative pairs while neglecting the informative positive pairs. Nevertheless, most augmentation methods require random perturbations, which may destroy the critical semantics of a graph, leading to false positive pairs (uninformative positives). 2) For informative negatives mining, most existing studies either overly emphasize hard negatives despite their potential unreliability, or rely on precise clustering pseudo-labels, which are error-prone especially in the early training stage. To solve the above challenges, we propose an informative sample-aware progressive graph contrastive learning framework, which filters both uninformative positives and negatives. In particular, we first present a progressive views sampler to evaluate the learning hardness of each view via clustering. Then, we feed model views with appropriate hardness, meaning those that aren't too challenging for the current model to assign pseudo labels confidently. Furthermore, we propose two samplers to filter out uninformative positives and negatives, respectively. Empirical results demonstrate the efficacy of our method IsGCL, which outperforms baselines by a margin of 2.5% on both MUTAG and PTC-MR in unsupervised learning settings. Furthermore, IsGCL maintains competitive training efficiency11Code available at https://github.com/jxzeng-git/IsGCL.

Pseudo-labeling is a widely used strategy in semi-supervised learning. Existing methods typically select predicted labels with high confidence scores and high training stationarity, as pseudo-labels to augment training sets. In contrast, this paper explores the pseudo-labeling potential of predicted labels that **do not** exhibit these characteristics. We discover a new type of predicted labels suitable for pseudo-labeling, termed *two-phase labels*, which exhibit a two-phase pattern during training: *they are initially predicted as one category in early training stages and switch to another category in subsequent epochs.* Case studies show the two-phase labels are informative for decision boundaries. To effectively identify the two-phase labels, we design a 2-*phasic* metric that mathematically characterizes their spatial and temporal patterns. Furthermore, we propose a loss function tailored for two-phase pseudo-labeling learning, allowing models not only to learn correct correlations but also to eliminate false ones. Extensive experiments on eight datasets show that **our proposed 2-*phasic* metric acts as a powerful booster** for existing pseudo-labeling methods by additionally incorporating the two-phase labels, achieving an average classification accuracy gain of 1.73% on image datasets and 1.92% on graph datasets.

Telecommunication fraud refers to deceptive activities in the field of communication services. This research focuses on a category of fraud identified as ''mutation telecommunication fraud". There is currently a lack of research on mutation telecommunication fraud detection, allowing this type of fraud to persist uncaught. We identify that detecting mutation fraud requires capturing multi-source patterns, including user communication graphs and temporal-spatial Voice of Call (VOC) features. Specifically, we introduce MutationGuard, which leverages Graph Neural Networks (GNN) to capture changes in user communication graphs. For VOC records, we map call start times onto a 3D cylindrical surface, thereby representing each VOC record in spatial coordinates and utilizing proposed LFFE and TCFE modules to capture local fraud behaviors and temporal behavior changes. The proposed neural modeling approach that facilitates multi-source information fusion constitutes a significant advancement in detecting mutation fraud. Experiment results reveal a significant improvement in the AUC score by 1.52% and the F1 score by 1.36% on the proposed telecommunication fraud dataset. Particularly, our method shows a significant improvement of 13.93% in accuracy on mutation fraud data. We also validate the effectiveness of our method on the publicly available Sichuan Telecommunication Fraud dataset.

Debiased recommendation focuses on alleviating the negative impact of various biases on recommendation quality to achieve fairer personalized recommendations. Current research mainly relies on propensity score estimation or causal inference methods to alleviate selection bias; at the same time, research on prevalence bias has proposed a variety of methods based on causal graphs and contrastive learning. However, these methods have shortcomings in dealing with unstable propensity score estimates, bias interactions, and decoupling of interest and bias signals, which limits the performance improvement of recommender systems. To this end, this paper proposes APWCF, a collaborative filtering debiased method that combines dynamic propensity modeling and adversarial learning. APWCF solves the problem of high variance in propensity scores through the dynamic propensity factor, and decouples user interests and bias signals through the adversarial learning to effectively remove multiple biases. Experiments show that APWCF significantly outperforms existing methods across various benchmark datasets from different domains. Compared with the current optimal baseline PDA, Recall@10 and NDCG@10 improve by 0.10%-5.42% and 1.01%-8.60% respectively.

Graph Few-Shot Node Classification (GFSNC) has emerged as a promising approach to address the challenge of learning with limited labeled data in graph-structured networks.Despite the success of Graph Neural Networks (GNNs) in node classification tasks, their performance heavily depends on the availability of abundant labeled data, which is often impractical in real-world scenarios.To tackle this issue, GFSNC adopts the episodic meta-learning paradigm, where models are trained on a series of meta-tasks.However, existing methods face two critical limitations: (i) they focus on local distributions within individual meta-tasks, neglecting the global data distribution, and (ii) they optimize models to minimize intra-class distances without adequately addressing inter-class separability, leading to suboptimal performance.This paper presents TaskNS, a novel GFSNC framework that introduces task-negative samples into meta-training tasks to address these limitations.By incorporating samples from classes outside the current meta-task, our framework enables the model to gradually learn the global distribution of the graph data.Additionally, we design a novel loss function that enhances the model's ability to distinguish between different classes of query samples.This loss function not only ensures high intra-class compactness but also maximizes the inter-class separation by leveraging task-negative samples.To further enhance the quality of task-negative samples, we propose an ℎ-hop-neighbors-based sampling method that leverages the topological structure of a graph.It selects task-negative samples that are structurally close to query samples, ensuring that they are informative and challenging for the model to classify.Extensive experiments on four benchmark datasets demonstrate the effectiveness of TaskNS, achieving average improvements of 4.6% in accuracy (ACC) and 4.9% in F1-score over state-of-the-art methods.

Federated learning (FL) is a popular collaborative training paradigm in which data owners offer gradients instead of private data to model owners for model training to protect data privacy. However, it faces security threats from two sides: dishonest model owners may extract sensitive information about private data from gradients; meanwhile, adversaries may pretend to be data owners and poison the model by sending malicious gradients. We propose a novel FL protocol, PARSIFAL, to address privacy leakage and model poisoning threats. A poisoning detection module is designed based on a novel sketch structure. This module efficiently detects potential malicious gradients that are dissimilar to the majority of benign gradients. PARSIFAL also contains a robust aggregation module based on sign gradients to mitigate the influence of poisoning gradients on aggregation results. Meanwhile, all processes of our PARSIFAL are protected by privacy protocols, mainly based on secret sharing, to guarantee that malicious detection and aggregation processes will not leak sensitive information. Experimental results show that PARSIFAL improves poisoning defense performance by up to 28% compared with recent baselines.

Knowledge graph-based retrieval-augmented generation seeks to mitigate hallucinations in Large Language Models (LLMs) caused by insufficient or outdated knowledge. However, existing methods often fail to fully exploit the prior knowledge embedded in knowledge graphs (KGs), particularly their structural information and explicit or implicit constraints. The former can enhance the faithfulness of LLMs' reasoning, while the latter can improve the reliability of response generations. Motivated by these, we propose a trustworthy reasoning framework, termed Deliberation over Priors (\texttt{DP}), which sufficiently utilizes the priors contained in KGs. Specifically, \texttt{DP} adopts a progressive knowledge distillation strategy that integrates structural priors into LLMs through a combination of supervised fine-tuning and Kahneman-Tversky Optimization, thereby improving the faithfulness of relation path generation. Furthermore, our framework employs a reasoning-introspection strategy, which guides LLMs to perform refined reasoning verification based on extracted constraint priors, ensuring the reliability of response generation. Extensive experiments on three benchmark datasets demonstrate that \texttt{DP} achieves new state-of-the-art performance, especially a H@1 improvement of 13% on the ComplexWebQuestions dataset, and generates highly trustworthy responses. We also conduct various analyses to verify its flexibility and practicality. Code is available at [https://github.com/mira-ai-lab/Deliberation-on-Priors](https://github.com/mira-ai-lab/Deliberation-on-Priors).

Graph Contrastive Learning (GCL) has shown excellent performance in Collaborative Filtering (CF), one of the most widely used techniques in efficient recommender systems . However, existing GCL-based CF methods suffer from node degree disparity, feature oversmoothing, difficulty in distinguishing hard negative samples, and semantic loss. To address these problems, this paper proposes a novel graph contrastive learning method for robust CF, named D egree- A ware P ropagation and E ntropy- W eighted contrastive loss (DAPEW). DAPEW introduces a degree-aware propagation mechanism to dynamically adjust the influence of initial embeddings, adjacency matrix products, and degree matrix products on the final embeddings, which can effectively handle node degree disparity and alleviate feature oversmoothing. DAPEW also designs an entropy-weighted contrastive loss, which introduces entropy weights to better distinguish hard negative samples and enhance the model’s discriminative ability and robustness. Experimental results show that DAPEW outperforms the existing GCL-based CF methods on several real-world datasets. Compared with existing GCL-based methods, DAPEW improves Recall@40 and NDCG@40 by 0.24% ∼ 25.88% and 0.14% ∼ 26.18% across four different datasets, respectively.

Counting the number of distinct values (NDV) is a fundamental problem in web applications and databases, particularly under memory constraints. Sketch-based methods, such as the Flajolet-Martin sketch, construct compact data summaries to estimate NDV but primarily focus on insertion-only scenarios. However, supporting delete operations is crucial for maintaining accurate and up-to-date cardinality estimates in many real-world applications, such as databases. Existing methods for fully dynamic scenarios, involving both insertions and deletions, often incur considerable computational and memory overhead. Furthermore, collaborative computation often requires sharing sketches with external or untrusted parties, which introduces significant privacy risks. To address these challenges, we propose a novel sketch method, GMod, specifically designed for fully dynamic scenarios and compatible with local differential privacy (LDP) for both NDV estimation and privacy preservation. Our method supports efficient deletions with minimal additional overhead by utilizing a single discrete uniformly distributed random variable. Additionally, we introduce a lightweight probabilistic estimation model to compute NDV, achieving 3× faster performance compared to the state-of-the-art. By incorporating carefully designed sketch perturbation mechanisms, our model mitigates the impact of LDP noise. Experimental results demonstrate that our method uses 1/3 of the memory to achieve comparable estimation accuracy in local settings and provides 8× higher accuracy under LDP scenarios compared to state-of-the-art methods.

Accurately estimating the number of unique elements that appear in data streams in real time is a fundamental problem with applications including network traffic monitoring and real-time social media analytics. Traditional sketch-based algorithms such as FM Sketch and HyperLogLog offer memory-friendly solutions for cardinality estimation but fall short in scenarios where the stream elements are privacy-sensitive and require differential privacy. Although recent approaches have incorporated differential privacy into the above cardinality estimators, they are limited to single-query settings, restricting their applicability. Previous methods for private cardinality continual release settings-i.e., releasing the cardinality after each new element in the stream-demand large memory resources and are thus difficult to apply in practice. In this paper, we present a novel cardinality estimation framework, FC, which ensures differential privacy under continual releases while simultaneously achieving low memory usage, high accuracy, and efficient computation. Our approach innovatively leverages an efficient cardinality estimator and privacy-preserving mechanisms to overcome the limitations of existing methods. Comprehensive experiments demonstrate that our method reduces memory usage by up to 504 times compared to the best previous method while maintaining nearly the same accuracy. Additionally, under identical memory constraints, our method improves the estimation accuracy by orders of magnitude.

Graph contrastive learning (GCL) has shown excellent performance in recommender systems. However, GCL-based methods have two major problems. First, many methods use graph perturbations to create the contrastive view, this operation may compromise the structure of the original graph. Second, some algorithms pursue the uniformity of features, but neglect the alignment, which may lead to the features of similar samples in the feature space distancing from each other, thereby reducing the model’s ability to distinguish similar samples. To address these problems, we propose the SiamGCL framework, which consists of two modules: multilevel alignment (MLA) and enhanced uniformity (EU). MLA uses the siamese network structure to process user and item data in parallel and achieves model-level alignment through shared structure and parameters. In addition, we introduce alignment loss in the optimization process to further refine the alignment of user and item embeddings. EU employs noise modulated augmentation and batch normalization regulator as alternatives to traditional graph perturbation methods. This embedding perturbation strategy effectively prevents over-aggregation in the feature space, which can also enhance the uniformity of the embedding distribution. Experiments on five large-scale benchmark datasets show that SiamGCL improves Recall@20 and NDCG@20 by 0.97%–5.51% and 1.31%–2.73%, respectively, compared with the current state-of-the-art method.

Approximate membership query (AMQ) structures represented by the Bloom Filter and its variants have been popularly researched in recent years. Researchers have recently combined machine learning with this type of structure to reduce space consumption and computation overhead further and make remarkable progress. However, with the booming performance in space or other metrics, researchers tend to ignore the security of the trained model. The machine learning model is vulnerable to poisoning attacks, and naturally, we infer that the learning-based filters also have the same deficiencies. Hence, in this article, to confirm the inference mentioned above, experiments on the real-world datasets of URLs are conducted and prove that it is necessary to consider the security issue when using learning-based filters. We show that by data poisoning, the attacker can deflect learned Bloom Filters to make a false identification, which can lead to a significant loss in some cases. Aiming to solve this issue, we put forward a method named Defensive Learned Bloom Filter (DLBF) to diminish the influence of data poisoning and achieve a better performance compared to types of learned Bloom Filters.

Legal case retrieval aims to automatically scour comparable legal cases based on a given query, which is crucial for offering relevant precedents to support the judgment in intelligent legal systems. Due to similar goals, it is often associated with a similar case matching task. To address them, a daunting challenge is assessing the uniquely defined legal-rational similarity within the judicial domain, which distinctly deviates from the semantic similarities in general text retrieval. Past works either tagged domain-specific factors or incorporated reference laws to capture legal-rational information. However, their heavy reliance on expert or unrealistic assumptions restricts their practical applicability in real-world scenarios. In this article, we propose an end-to-end model named LCM-LAI to solve the above challenges. Through meticulous theoretical analysis, LCM-LAI employs a dependent multi-task learning framework to capture legal-rational information within legal cases by a law article prediction sub-task, without any additional assumptions in inference. In addition, LCM-LAI proposes an article-aware attention mechanism to evaluate the legal-rational similarity between across-case sentences based on the law distribution, which is more effective than semantic similarity. We perform a series of exhaustive experiments that include two different tasks that involving four real-world datasets. The results demonstrate that LCM-LAI achieves state-of-the-art performance.

Legal Judgment Prediction (LJP) aims to automatically predict a law case’s judgment results based on the text description of its facts. In practice, the confusing law articles (or charges) problem frequently occurs, reflecting that the law cases applicable to similar articles (or charges) tend to be misjudged. Although some recent works based on prior knowledge solve this issue well, they ignore that confusion also occurs between law articles with a high posterior semantic similarity due to the data imbalance problem instead of only between the prior highly similar ones, which is this work’s further finding. This article proposes an end-to-end model named D-LADAN to solve the above challenges. On the one hand, D-LADAN constructs a graph among law articles based on their text definition and proposes a graph distillation operator (GDO) to distinguish the ones with a high prior semantic similarity. On the other hand, D-LADAN presents a novel momentum-updated memory mechanism to dynamically sense the posterior similarity between law articles (or charges) and a weighted GDO to adaptively capture the distinctions for revising the inductive bias caused by the data imbalance problem. We perform extensive experiments to demonstrate that D-LADAN significantly outperforms state-of-the-art methods in accuracy and robustness.

By integrating machine learning with edge devices, we can augment the capabilities of edge devices, such as IoT devices, household appliances, and wearable technologies. These edge devices generally operate on microcontrollers with inherently limited resources, such as constrained RAM capacity and limited computational power. Nonetheless, they often process data in a high-velocity stream fashion, exemplified by sequences of activities and statuses monitored by advanced industrial sensors. In practical scenarios, models must be interpretable to facilitate troubleshooting and behavior understanding. Implementing machine learning models on edge devices is valuable and challenging, striking a balance between model efficacy and resource constraint. To address this challenge, we introduce our novel Onfesk, which combines online learning algorithms with an innovative interpretable kernel. Specifically, our Onfesk trains an online classifier over the kernel's feature sketches. Benefiting from our specially designed modules, the kernel's feature sketches can be efficiently produced, and the memory requirements of the classifier can be significantly reduced. As a result, Onfesk delivers effective and efficient performance in environments with limited resources without compromising on model interpretability. Extensive experiments with diverse real-world datasets have shown that Onfesk outperforms state-of-the-art methods, achieving up to a 7.4% improvement in accuracy within identical memory constraints.

The drastic increase in language models' parameters has led to a new trend of deploying models in cloud servers, raising growing concerns about private inference for Transformer-based models. Existing two-party privacy-preserving techniques, however, only take into account natural language understanding (NLU) scenarios. Private inference in natural language generation (NLG), crucial for applications like translation and code completion, remains underexplored. In addition, previous privacy-preserving techniques suffer from convergence issues during model training and exhibit poor inference speed when used with NLG models due to the neglect of time-consuming operations in auto-regressive generations. To address these issues, we propose a fast private text generation framework for Transformer-based language models, namely MERGE. MERGE reuses the output hidden state as the word embedding to bypass the embedding computation and reorganize the linear operations in the Transformer module to accelerate the forward procedure. Extensive experiments show that MERGE achieves a 26.5x speedup to the vanilla encrypted model under the sequence length 512, and reduces 80% communication cost, with an up to 10x speedup to state-of-the-art approximated models.

Molecular representation learning has emerged as a game-changer at the intersection of AI and chemistry, with great potential in applications such as drug design and materials discovery. A substantial obstacle in successfully applying molecular representation learning is the difficulty of effectively and completely characterizing and learning molecular geometry, which has not been well addressed to date. To overcome this challenge, we propose a novel framework that features a novel geometric graph, termed HAGO-Graph, and a specifically designed geometric graph learning model, HAGO-Net. In the framework, the foundation is HAGO-Graph, which enables a complete characterization of molecular geometry in a hierarchical manner. Specifically, we leverage the concept of n-body in physics to characterize geometric patterns at multiple spatial scales. We then specifically design a message passing scheme, HAGO-MPS, and implement the scheme as a geometric graph neural network, HAGO-Net, to effectively learn the representation of HAGO-Graph by horizontal and vertical aggregation. We further prove DHAGO-Net, the derivative function of HAGO-Net, is an equivariant model. The proposed models are validated by extensive comparisons on four challenging benchmarks. Notably, the models exhibited state-of-the-art performance in molecular chirality identification and property prediction, achieving state-of-the-art performance on five properties of QM9 dataset. The models also achieved competitive results on molecular dynamics prediction task.

Computing set difference cardinalities is a critical task in database optimization, network management, and anomaly detection. Due to the limited computational and mem-ory resources, exactly calculating set difference cardinalities becomes impractical in real-world applications. To solve this issue, sketch methods such as Odd sketch, Tug-of-War sketch, and HyperLogLog sketch can be extended to provide approximate estimations of set difference cardinalities. They use a family of hash functions to compress all elements in a set into a compact data structure. Unfortunately, Odd sketch suffers from limited estimation range, while Tug-of-War sketch and HyperLogLog sketch unavoidably face the problems of large estimation errors and high computational costs. In this paper, we design a novel data structure of bit array GXBits to fast and accurately estimate set difference cardinalities in a large range. In GXBits, the prob-ability of each bit recording its corresponding elements follows a variant of geometric distributions and varies across different bits. We conduct extensive experiments on synthetic datasets and real-world datasets. Experimental results demonstrate that our method GXBits is more computationally and memory efficient, and significantly increases the estimation accuracy of existing methods by up to 221.3 times.

Key-value sequence data has become ubiquitous and naturally appears in a variety of real-world applications, ranging from the user-product purchasing sequences in e-commerce, to network packet sequences forwarded by routers in networking. Classifying these key-value sequences is important in many scenarios such as user profiling and malicious applications identification. In many time-sensitive scenarios, besides the requirement of classifying a key-value sequence accurately, it is also desired to classify a key-value sequence early, in order to respond fast. However, these two goals are conflicting in nature, and it is challenging to achieve them simultaneously. In this work, we formulate a novel tangled key-value sequence early classification problem, where a tangled key-value sequence is a mixture of several concurrent key-value sequences with different keys. The goal is to classify each individual key-value sequence sharing a same key both accurately and early. To address this problem, we propose a novel method, i.e., Key-Value sequence Early Co-classification (KVEC), which leverages both inner- and inter-correlations of items in a tangled key-value sequence through key correlation and value correlation to learn a better sequence representation. Meanwhile, a time-aware halting policy decides when to stop the ongoing key-value sequence and classify it based on current sequence representation. Experiments on both real-world and synthetic datasets demonstrate that our method outperforms the state-of-the-art baselines significantly. KVEC improves the prediction accuracy by up to 4.7 -17.5% under the same prediction earliness condition, and improves the harmonic mean of accuracy and earliness by up to 3.7 -14.0%.

With the widespread deployment of location-aware mobile devices, a mass of trajectory data is being generated and collected. Mining co-movement patterns of people and vehicles from streaming and massive trajectory data has attracted much attention due to its wide applications in various fields. As a typical co-movement pattern, convoys describe objects moving together in consecutive timestamps. There are two challenges for efficient distributed convoy mining: object clustering and workload balancing. Clustering objects in each time snapshot is a time-consuming operation. In addition, on the basis of practical application scenarios, load balancing is an important consideration for distributed algorithms. To tackle the above challenges, we propose a novel method for distributed convoy mining via sliding window-based indexing and sub-track partitioning, abbreviated SWISP. We offer three major advancements. First, we develop a grid-based DBSCAN clustering algorithm named Grid-DBSCAN for distributed scenarios. It avoids the exhaustive calculation of pairwise distances for neighborhood search and thus improves computational efficiency in the clustering stage. Second, we propose a sliding window-based indexing scheme to filter out sub-tracks with less than$k$consecutive time snapshots, significantly reducing the number of candidate sub-tracks for convoy mining. Third, we develop a distributed convoy mining algorithm based on sub-track partitioning. It exploits both temporal and spatial information of sub-tracks for data partitioning and solves the data skewness problem caused by uneven data distributions. We conduct extensive experiments on four real-world datasets. The experimental results show that our distributed algorithm can handle large-scale trajectory data and is more efficient than state-of-the-art approaches.

Graph data are ubiquitous in real-world systems such as social networks and protein-protein interaction networks. In many applications, nodes usually are associated with real-value attributes, e.g., age, income, and wealth. Recently, industry and research communities have attracted attention to mining and learning attribute graphs. In this paper, we study the problem of calculating the general neighborhood cardinality of each node$v$in the graph, i.e., the sum of non-negative attribute values of the nodes in the$k$-hop neighborhood of a node$v$. The naive solution is to run a$k$-step breadth-first-search (BFS) algorithm starting from each node and storing all visited nodes' attributes. Clearly, the time complexity of this solution is$O\left(\vert V\vert d_{\max }^k\right)$, where$\vert V\vert$is the number of nodes and$d_{\max}$is the maximum node degree in the graph. In real-world networks such as Twitter,$d_{\max}$is over$3\times{1}0^{6}$. Therefore, it is infeasible to compute the neighborhood cardinality of nodes exactly in such massive networks even if we set$k=2$. To solve this problem, we propose efficient methods to compute the neighborhood cardinality of graphs with non-negative node attributes and binary node attributes, respectively. Extensive experiments on large real-world networks show the efficiency and effectiveness of our methods.

The advancement toward deeper graph neural networks is currently obscured by two inherent issues in message passing, oversmoothing and oversquashing. We identify the root cause of these issues as information loss due to heterophily mixing in aggregation, where messages of diverse category semantics are mixed. We propose a novel multi-track graph convolutional network to address oversmoothing and oversquashing effectively. Our basic idea is intuitive: if messages are separated and independently propagated according to their category semantics, heterophilic mixing can be prevented. Consequently, we present a novel multi-track message passing scheme capable of preventing heterophilic mixing, enhancing long-distance information flow, and improving separation condition. Empirical validations show that our model achieved state-of-the-art performance on several graph datasets and effectively tackled oversmoothing and oversquashing, setting a new benchmark of $86.4$% accuracy on Cora.

Estimating cardinality, i.e., the number of distinct elements, of a data stream is a fundamental problem in areas like databases, computer networks, and information retrieval. This study delves into a broader scenario where each element carries a positive weight. Unlike traditional cardinality estimation, limited research exists on weighted cardinality, with current methods requiring substantial memory and computational resources, challenging for devices with limited capabilities and real-time applications like anomaly detection. To address these issues, we propose QSketch, a memory-efficient sketch method for estimating weighted cardinality in streams. QSketch uses a quantization technique to condense continuous variables into a compact set of integer variables, with each variable requiring only 8 bits, making it 8 times smaller than previous methods. Furthermore, we leverage dynamic properties during QSketch generation to significantly enhance estimation accuracy and achieve a lower time complexity of O(1) for updating estimations upon encountering a new element. Experimental results on synthetic and real-world datasets show that QSketch is approximately 30% more accurate and two orders of magnitude faster than the state-of-the-art, using only 1/8 of the memory.

Deep neural networks are widely used in retrieval systems. However, they are notoriously vulnerable to attack. Among the various forms of adversarial attacks, the patch attack is one of the most threatening forms. This type of attack can introduce cognitive biases into the retrieval system by inserting deceptive patches into images. Despite the seriousness of this threat, there are still no well-established solutions in image retrieval systems. In this paper, we propose the Pre-denosing Augmented Image Retrieval (PAIR) model, a new approach designed to protect image retrieval systems against adversarial patch attacks. The core strategy of PAIR is to dynamically and randomly reconstruct entire images based on their semantic content. This purifies well-designed patch attacks while preserving the semantic integrity of the images. Furthermore, we present a novel training strategy that incorporates a semantic discriminator. This discriminator significantly improves PAIR's ability to capture real semantics and reconstruct images. Experiments show that PAIR significantly outperforms existing defense methods. It effectively reduces the success rate of two state-of-the-art patch attack methods to below 5%, achieving a 14% improvement over current leading methods. Moreover, in defending against global perturbation attacks, PAIR also achieves competitive results.

Audio-Visual Question Answering (AVQA) is a complex multi-modal reasoning task, demanding intelligent systems to accurately respond to natural language queries based on audio-video input pairs. Nevertheless, prevalent AVQA approaches are prone to overlearning dataset biases, resulting in poor robustness. Furthermore, current datasets may not provide a precise diagnostic for these methods. To tackle these challenges, firstly, we propose a novel dataset, *MUSIC-AVQA-R*, crafted in two steps: rephrasing questions within the test split of a public dataset (*MUSIC-AVQA*) and subsequently introducing distribution shifts to split questions. The former leads to a large, diverse test space, while the latter results in a comprehensive robustness evaluation on rare, frequent, and overall questions. Secondly, we propose a robust architecture that utilizes a multifaceted cycle collaborative debiasing strategy to overcome bias learning. Experimental results show that this architecture achieves state-of-the-art performance on MUSIC-AVQA-R, notably obtaining a significant improvement of 9.32\%. Extensive ablation experiments are conducted on the two datasets mentioned to analyze the component effectiveness within the debiasing strategy. Additionally, we highlight the limited robustness of existing multi-modal QA methods through the evaluation on our dataset. We also conduct experiments combining various baselines with our proposed strategy on two datasets to verify its plug-and-play capability. Our dataset and code are available at <https://github.com/reml-group/MUSIC-AVQA-R>.

Graph retrieval aims to find the most similar graphs in a graph database given a query graph, which is a fundamental problem with many real-world applications in chemical engineering, code analysis, etc. To date, existing neural graph retrieval methods generally fall into two categories: Embedding Based Paradigm (Ebp) and Matching Based Paradigm (Mbp). The Ebp models learn an individual vectorial representation for each graph and the retrieval process can be accelerated by pre-computing these representations. The Mbp models learn a neural matching function to compare graphs on a pair-by-pair basis, in which the fine-grained pairwise comparison leads to higher retrieval accuracy but severely degrades retrieval efficiency. In this paper, to combine the advantage of Ebp in retrieval efficiency with that of Mbp in retrieval accuracy, we propose a novel Graph RetrievAl framework via KNowledge Distillation, namely GRAND. The key point is to leverage the idea of knowledge distillation to transfer the fine-grained graph comparison knowledge from an Mbp model to an Ebp model, such that the Ebp model can generate better graph representations and thus yield higher retrieval accuracy. At the same time, we can still pre-compute and index the improved graph representations to retain the retrieval speed of Ebp. Towards this end, we propose to perform knowledge distillation from three perspectives: score, node, and subgraph levels. In addition, we propose to perform mutual two-way knowledge transfer between Mbp and Ebp, such that Mbp and Ebp complement and benefit each other. Extensive experiments on three real-world datasets show that GRAND improves the performance of Ebp by a large margin and the improvement is consistent for different combinations of Ebp and Mbp models. For example, GRAND achieves performance gains of mostly more than 10% and up to 16.88% in terms of Recall@K on different datasets.

Graph few-shot learning (GFSL) has achieved great success in node classification tasks with rare labels. However, graph few-shot classification (GFSC) models often encounter the problem of classifying test samples with unobserved (or unknown) classes due to the rareness of labels. We formulate this problem as out-of-distribution (OOD) sample detection in inductive graph few-shot learning. This paper presents SMUG, a novel GFSL framework that can detect unobserved classes. Since we have no ground-truth OOD samples in a practical training dataset, it is challenging for the GFSC model to retrieve knowledge about unknown classes from labeled samples. To address this difficulty, we propose a sand mixing scheme to introduce observed classes as artificial OOD samples into meta-tasks. We also develop two unsupervised OOD discriminators to identify OOD samples. Thus, we can assess the performance of OOD discriminators since we know the true classes of these artificial OOD samples. Subsequently, we design a novel training procedure to optimize the encoder based on the performance of the OOD discriminators and the GFSC model. It not only enables the GFSL model to distinguish OOD samples but also promotes the classification accuracy of normal samples. We conduct extensive experiments to evaluate the effectiveness of SMUG based on four benchmark datasets. Experimental results demonstrate that SMUG achieves superior performance over state-of-the-art approaches in OOD detection and node classification. The source code of this paper is available at https://github.com/Memepp/SMUG.

Given two sets of elements held by two different parties separately, computing the cardinality (i.e., the number of distinct elements) of their intersection set is a fundamental task in applications such as network monitoring and database systems. To handle large sets with limited space, computation, and communication costs, lightweight probabilistic methods (i.e., sketch methods) such as the Flajolet-Martin (FM) sketch and the HyperLogLog (HLL) sketch are extensively used. However, when a set's probabilistic data summary and the hash functions used to construct the sketch are disclosed to an untrusted third party, the set's privacy is compromised. Directly applyingLocal Differential Privacy (LDP) techniques to safeguard the sketch collection results in extremely large estimation errors of set intersection cardinalities. To address this issue, we propose a novel sketch method that makes it easier to incorporate noise into the constructed sketch to achieve differential privacy. More importantly, our sketch method is compatible with the LDP noise. In other words, the probabilistic model underlying our LDP-based data summary is quite basic, allowing us to eliminate the estimation error generated by the noise. We perform extensive experiments on various synthetic and real-world datasets and the experimental results demonstrate that our method is orders of magnitude more accurate and several times faster than state-of-the-art methods.

Visual question answering requires a system to provide an accurate natural language answer given an image and a natural language question. However, it is widely recognized that previous generic VQA methods often tend to memorize biases present in the training data rather than learning proper behaviors, such as grounding images before predicting answers. Therefore, these methods usually achieve high in-distribution but poor out-of-distribution performance. In recent years, various datasets and debiasing methods have been proposed to evaluate and enhance the VQA robustness, respectively. This paper provides the first comprehensive survey focused on this emerging fashion. Specifically, we first provide an overview of the development process of datasets from in-distribution and out-of-distribution perspectives. Then, we examine the evaluation metrics employed by these datasets. Third, we propose a typology that presents the development process, similarities and differences, robustness comparison, and technical features of existing debiasing methods. Furthermore, we analyze and discuss the robustness of representative vision-and-language pre-training models on VQA. Finally, through a thorough review of the available literature and experimental analysis, we discuss the key areas for future research from various viewpoints.

Kernel density estimation is a useful method for estimating the probability distribution of data. It is a challenge to achieve efficient kernel density estimation, especially for large-scale and high-dimension stream data. We proposerotation kernel, a novel kernel function for density estimation. The rotation kernel density can be fast estimated by a data structure namedRotation Kernel Density Sketch(RKDS). RKDS is a time- and memory-efficient method for kernel density estimation, even over data streams and distributed systems. RKDS is applicable for estimating density at specific points and also for representing data distribution. We provide theoretical analysis for rotation kernel and RKDS. Furthermore, we apply RKDS to outlier detection, concept drift detection, and personalized federated learning. Experiments show that our method improves time efficiency by up to$3\times 10^{3}$times compared with baselines. RKDS also provides comparable detecting precision and better delay on outlier detection and concept drift detection tasks.

Graph alignment aims to find correspondent nodes between two graphs. Most existing algorithms assume that correspondent nodes in different graphs have similar local structures. However, this principle may not apply to some real-world application scenarios when two graphs have different densities. Some correspondent node pairs may have very different local structures in these cases. Nevertheless, correspondent nodes are expected to have similar importance, inspiring us to exploit global topology consistency for graph alignment. This paper presents GTCAlign, an unsupervised graph alignment framework based on global topology consistency. An indicating matrix is calculated to show node pairs with consistent global topology based on a comprehensive centrality metric. A graph convolutional network (GCN) encodes local structural and attributive information into low-dimensional node embeddings. Then, node similarities are computed based on the obtained node embeddings under the guidance of the indicating matrix. Moreover, a pair of nodes are more likely to be aligned if most of their neighbors are aligned, motivating us to develop an iterative algorithm to refine the alignment results recursively. We conduct extensive experiments on real-world and synthetic datasets to evaluate the effectiveness of GTCAlign. The experimental results show that GTCAlign outperforms state-of-the-art graph alignment approaches.

Calculating the number of distinct values (i.e., NDV) in a column of a big table is costly yet fundamental to a variety of database applications such as data compression and profiling. To reduce the high time and space cost, a number of sketch methods (e.g., HyperLogLog) have been proposed, which estimate the NDV from a constructed compact data summary of distinct values. However, these methods fail or are costly to manage fully-dynamic scenarios where data is often inserted into and deleted from the table. To solve this issue, we propose a novel sketch method,Half-Xor. Our Half-Xor sketch consists of a compact bit matrix and a small counter array, and it needs to set a few bits and update a counter when handling a data insertion/deletion. Compared with the state-of-the-art mergeable method, our experimental results demonstrate that our method Half-Xor is up to 6.6 times more accurate under the same memory usage and reduces the memory usage by up to 16 times to achieve the same estimation accuracy.

Textbook question answering (TQA) is the task of correctly answering diagram or nondiagram (ND) questions given large multimodal contexts consisting of abundant essays and diagrams. In real-world scenarios, an explainable TQA system plays a key role in deepening humans' understanding of learned knowledge. However, there is no work to investigate how to provide explanations currently. To address this issue, we devise a novel architecture toward span-level eXplanations for TQA (XTQA). In this article, spans are the combinations of sentences within a paragraph. The key idea is to consider the entire textual context of a lesson as candidate evidence and then use our proposed coarse-to-fine grained explanation extracting (EE) algorithm to narrow down the evidence scope and extract the span-level explanations with varying lengths for answering different questions. The EE algorithm can also be integrated into other TQA methods to make them explainable and improve the TQA performance. Experimental results show that XTQA obtains the best overall explanation result [mean intersection over union (mIoU)] of 52.38% on the first 300 questions of CK12-QA test splits, demonstrating the explainability of our method (ND: 150 and diagram: 150). The results also show that XTQA achieves the best TQA performance of 36.46% and 36.95% on the aforementioned splits. We have released our code in https://github.com/dr-majie/opentqa.

Influence maximization (IM) is the fundamental problem in many real world applications such as viral marketing, political campaign, and network monitoring. Although extensively studied, most studies on IM assume that social influence is static and they cannot handle the dynamic influence challenge in reality, i.e., a user’s influence is varying over time. To address this challenge, we formulate a novel influencer tracking problem over a social activity stream. In order to keep the solutions up-to-date and forget outdated data in the stream smoothly, we propose a probabilistic-decaying social activity stream (PDSAS) model that enforces each social activity in the stream participating in the analysis with a probability decaying over time. Built on the PDSAS model, we propose a family of streaming optimization algorithms to solve the influencer tracking problem. SIEVE PAIT can identify influencers from a special kind of probabilistic addition-only social activity streams with high efficiency, and guarantees an$(1/2-\epsilon)$approximation ratio. BASIC IT leverages SIEVE PAIT as a building block to identify influencers from general PDSASs, and also guarantees an$(1/2-\epsilon)$approximation ratio. HIST IT improves the efficiency of BASIC IT, and still guarantees an$(1/4-\epsilon)$approximation ratio. Experiments on real data show that our methods can find high quality solutions with much less computational costs than baselines.

Topic segmentation aims to reveal the latent structure of a document and divide it into multiple parts. However, current neural solutions are limited in the context modeling of sentences and feature representation of candidate boundaries. This causes the model to suffer from inefficient sentence context encoding and noise information interference. In this paper, we design a new text segmentation model SegFormer with unidirectional attention blocks to better model sentence representations. To alleviate the problem of noise information interference, SegFormer uses a novel additional context aggregator and a topic classification loss to guide the model to aggregate the information within the appropriate range. In addition, SegFormer applies an iterative prediction algorithm to search for optimal boundaries progressively. We evaluate SegFormer's generalization ability, multilingual ability, and application ability on multiple challenging real-world datasets. Experiments show that our model significantly improves the performance by 7.5% on the benchmark WIKI-SECTION compared to several strong baselines. The application of SegFormer to a real-world dataset to separate normal and advertisement segments in product marketing essays also achieves superior performance in the evaluation with other cutting-edge models.

Multi-action dialog policy (MADP), which generates multiple atomic dialog actions per turn, has been widely applied in task-oriented dialog systems to provide expressive and efficient system responses. Existing MADP models usually imitate action combinations from the labeled multi-action dialog samples. Due to data limitations, they generalize poorly toward unseen dialog flows. While reinforcement learning-based methods are proposed to incorporate the service ratings from real users and user simulators as external supervision signals, they suffer from sparse and less credible dialog-level rewards. To cope with this problem, we explore to improve MADPL with explicit and implicit turn-level user feedback received for historical predictions (i.e., logged user feedback) that are cost-efficient to collect and faithful to real-world scenarios. The task is challenging since the logged user feedback provides only partial label feedback limited to the particular historical dialog actions predicted by the agent. To fully exploit such feedback information, we propose BanditMatch, which addresses the task from a feedback-enhanced semi-supervised learning perspective with a hybrid learning objective of SSL and bandit learning. BanditMatch integrates pseudo-labeling methods to better explore the action space through constructing full label feedback. Extensive experiments show that our BanditMatch improves MADPL over the state-of-the-art methods by generating more concise and informative responses. The source code and the appendix of this paper can be obtained from https://github.com/ShuoZhangXJTU/BanditMatch.

Network embedding algorithms learn a mapping from the discrete representation of nodes to continuous vector spaces that preserve node proximity. Despite recent efforts to design novel models, little attention has been given to understanding the instability of network embedding. In this paper, we define the stability of node embeddings as the invariance of the nearest neighbors of nodes in different instantiations. We find that existing embedding approaches have significant amounts of instability. In addition, network structures and algorithm models influence the stability of node embeddings significantly. We also examine the implications of embedding instability for downstream tasks and find remarkable impacts on performance.

Log messages provide a valuable source of runtime information for ensuring the safety and consistency of systems. Recently, many machine learning and deep learning methods have been proposed to automatically detect anomalous log messages, obviating the need for manual detection by experts. However, we find that in practice, the effectiveness of existing learning-based methods is severely affected by incomplete information and distribution shift. Specifically, each log message can actually be parsed into a fixed number of key information fields, while existing methods analyze log messages using only the log event information and ignore other useful information fields that can be critical to anomaly detection. Further, the distribution of real-world log messages changes continuously due to the dynamic nature of the runtime environment and thus, a detection model conventionally trained based on the unrealistic i.i.d. assumption may not provide the expected and consistent performance. In this paper, we present a robust and transferable anomaly detection framework RT-Log to address the above problems. To perform a comprehensive analysis of log messages, we introduce an adaptive relation modeling technique, which captures feature interactions among log information fields selectively and dynamically for effective and interpretable log representations. To establish its robustness and transferability, we propose a general environment generalization technique for learning the environment invariant representations that can generalize across different runtime environments. We evaluate the anomaly detection performance of RT-Log on large real-world datasets. Extensive experimental results demonstrate that RT-Log consistently outperforms state-of-the-art methods by a significant margin under different settings.

Counting the number of distinct elements distributed over multiple data holders is a fundamental problem with many real-world applications ranging from crowd counting to network monitoring. Although a number of space and computationally efficient sketch methods (e.g., the Flajolet-Martin sketch and the HyperLogLog sketch) for cardinality estimation have been proposed to solve the above problem, these sketch methods are insecure when considering privacy concerns related to the use of each data holder's personal dataset. Despite a recently proposed protocol that successfully implements the well-known Flajolet-Martin (FM) sketch on a secret-sharing based multiparty computation (MPC) framework for solving the problem of private distributed cardinality estimation (PDCE), we observe that this MPC-FM protocol is not differentially private. In addition, the MPC-FM protocol is computationally expensive, which limits its applications to data holders with limited computation resources. To address the above issues, in this paper we propose a novel protocol DP-DICE, which is computationally efficient and differentially private for solving the problem of PDCE. Experimental results show that our DP-DICE achieves orders of magnitude speedup and reduces the estimation error by several times in comparison with state-of-the-arts under the same security requirements.

The well-known Gumbel-Max Trick for sampling elements from a categorical distribution (or more generally a non-negative vector) and its variants have been widely used in areas such as machine learning and information retrieval. To sample a random element$i$in proportion to its positive weight$v_{i}$, the Gumbel-Max Trick first computes a Gumbel random variable$g_{i}$for each positive weight element$i$, and then samples the element$i$with the largest value of$g_{i}+\ln v_{i}$. Recently, applications including similarity estimation and weighted cardinality estimation require to generate$k$independent Gumbel-Max variables from high dimensional vectors. However, it is computationally expensive for a large$k$(e.g., hundreds or even thousands) when using the traditional Gumbel-Max Trick. To solve this problem, we propose a novel algorithm,FastGM, which reduces the time complexity from$O(kn^+)$to$O(k \ln k + n^+)$, where$n^+$is the number of positive elements in the vector of interest. FastGM stops the procedure of Gumbel random variables computing for many elements, especially for those with small weights. We perform experiments on a variety of real-world datasets and the experimental results demonstrate that FastGM is orders of magnitude faster than state-of-the-art methods without sacrificing accuracy or incurring additional expenses.

Unmanned aerial vehicles (UAVs) have the potential to establish flexible and reliable emergency networks in disaster sites when terrestrial communication infrastructures go down. Nevertheless, potential security threats may occur on UAVs during data transmissions due to the untrusted environment and open-access UAV networks. Moreover, UAVs typically have limited battery and computation capacity, making them unaffordable for heavy security provisioning operations when performing complicated rescue tasks. In this paper, we develop RescueChain, a secure and efficient information sharing scheme for UAV-assisted disaster rescue. Specifically, we first implement a lightweight blockchain-based framework to safeguard data sharing under disasters and immutably trace misbehaving entities. A reputation-based consensus protocol is devised to adapt the weakly connected environment with improved consensus efficiency and promoted UAVs’ honest behaviors. Furthermore, we introduce a novel vehicular fog computing (VFC)-based off-chain mechanism by leveraging ground vehicles as moving fog nodes to offload UAVs’ heavy data processing and storage tasks. To offload computational tasks from the UAVs to ground vehicles with idle computing resources, an optimal allocation strategy is developed by choosing payoffs that achieve equilibrium in a Stackelberg game formulation of the allocation problem. For lack of sufficient knowledge on network model parameters and users’ private cost parameters in practical environment, we also design a two-tier deep reinforcement learning-based algorithm to seek the optimal payment and resource strategies of UAVs and vehicles with improved learning efficiency. Simulation results show that RescueChain can effectively accelerate consensus process, improve offloading efficiency, reduce energy consumption, and enhance user payoffs.

Graphs are widely used to represent the relations among entities. When one owns the complete data, an entire graph can be easily built, therefore performing analysis on the graph is straightforward. However, in many scenarios, it is impractical to centralize the data due to data privacy concerns. An organization or party only keeps a part of the whole graph data, i.e., graph data is isolated from different parties. Recently, Federated Learning (FL) has been proposed to solve the data isolation issue, mainly for Euclidean data. It is still a challenge to apply FL on graph data because graphs contain topological information which is notorious for its non-IID nature and is hard to partition. In this work, we propose a novel FL framework for graph data, FedCog, to efficiently handle coupled graphs that are a kind of distributed graph data, but widely exist in a variety of real-world applications such as mobile carriers’ communication networks and banks’ transaction networks. We theoretically prove the correctness and security of FedCog. Experimental results demonstrate that our method FedCog significantly outperforms traditional FL methods on graphs. Remarkably, our FedCog improves the accuracy of node classification tasks by up to 14.7%.

Graph Neural Networks (GNNs) have been success-fully applied to a variety of graph analysis tasks. Some recent studies have demonstrated that decoupling neighbor aggregation and feature transformation helps to scale GNNs to large graphs. However, very large graphs, with billions of nodes and millions of features, are still beyond the capacity of most existing GNNs. In addition, when we are only interested in a small number of nodes (called target nodes) in a large graph, it is inefficient to use the existing GNNs to infer the labels of these few target nodes. The reason is that they need to propagate and aggregate either node features or predicted labels over the whole graph, which incurs high additional costs relative to the few target nodes. To solve the above challenges, in this paper we propose a novel scalable and effective GNN framework COSAL. In COSAL, we substitute the expensive aggregation with an efficient proximate node selection mechanism, which picks out the most important$K$nodes for each target node according to the graph topology. We further propose a fine-grained neighbor importance quantification strategy to enhance the expressive power of COSAL. Empirical results demonstrate that our COSAL achieves superior performance in accuracy, training speed, and partial inference efficiency. Remarkably, in terms of node classification accuracy, our model COSAL outperforms baselines by significant margins of 2.22%, 2.23%, and 3.95% on large graph datasets Amazon2M, MAG-Scholar-C, and ogbn-papers100M, respectively.11Code available at https://github.com/joyce-x/COSAL.

Multi-action dialog policy (MADP), which generates multiple atomic dialog actions per turn, has been widely applied in task-oriented dialog systems to provide expressive and efficient system responses. Existing MADP models usually imitate action combinations from the labeled multi-action dialog samples. Due to data limitations, they generalize poorly toward unseen dialog flows. While interactive learning and reinforcement learning algorithms can be applied to incorporate external data sources of real users and user simulators, they take significant manual effort to build and suffer from instability. To address these issues, we propose Planning Enhanced Dialog Policy (PEDP), a novel multi-task learning framework that learns single-action dialog dynamics to enhance multi-action prediction. Our PEDP method employs model-based planning for conceiving what to express before deciding the current response through simulating single-action dialogs. Experimental results on the MultiWOZ dataset demonstrate that our fully supervised learning-based method achieves a solid task success rate of 90.6%, improving 3% compared to the state-of-the-art methods. The source code and the appendix of this paper can be obtained from https://github.com/ShuoZhangXJTU/PEDP.

Many real-world datasets are given in the stream of entity-identifier pairs, and measuring data distribution on these datasets is fundamental for applications such as privacy protection. In this paper, we study the problem of computing the cumulative distribution for different cardinalities (i.e., the number of distinct entities owning the same identifier). However, previous sketch-based methods cost large memory space especially when there are a large number of identifiers, and sampling-based methods require much time for cardinality estimation. A recent work KHyperLogLog combines both sketch and sampling methods but it is wasteful to separately build a HyperLogLog sketch of large size for identifiers with small cardinalities. To address these challenges, we propose a memory-efficient method EV-HLL, which designs a shared structure to store all sampled identifiers and their entities and utilizes additional sketches to track value updates during the sampling procedure. Meanwhile, EV-HLL provides real-time unbiased estimations according to value changes whenever a new entity-identifier pair arrives. We evaluate the performance of EV-HLL and other state-of-the-arts on real-world available datasets. Experimental results demonstrate that comparing to other methods, EV-HLL effectively reduces their memory usage with the same estimation accuracy and has higher accuracy with the same memory usage.

Online monitoring user cardinalities in graph streams is fundamental for many applications such as anomaly detection. These graph streams may contain edge duplicates and have a large number of user-item pairs, which makes it infeasible to exactly compute user cardinalities due to limited computational and memory resources. Existing methods are designed to approximately estimate user cardinalities, but their accuracy highly depends on complex parameters and they cannot provide anytime-available estimation. To address these problems, we develop novel bit/register sharing algorithms, which use a bit/register array to build a compact sketch of all users’ connected items. Our algorithms exploit the dynamic properties of the bit/register arrays (e.g., the fraction of zero bits in the bit array) to significantly improve the estimation accuracy, and have low time complexity$O(1)$to update the estimations for a new user-item pair. In addition, our algorithms are simple and easy to use, without requirements to tune any parameter. Furthermore, we extend our methods to detect super spreaders with large cardinalities in real-time. We evaluate the performance of our methods on real-world datasets. The experimental results demonstrate that our methods are several times more accurate and faster than state-of-the-art methods using the same amount of memory.

Bipartite graphs widely exist in real-world scenarios and model binary relations like host-website, author-paper, and user-product. In bipartite graphs, a butterfly (i.e.,$2\times 2$bi-clique) is the smallest non-trivial cohesive structure and plays an important role in applications such as anomaly detection. Considerable efforts focus on counting butterflies in static bipartite graphs. However, they suffer from high time and space complexity when the bipartite graph of interest is given as a stream of edges. Although there are methods for approximately counting butterflies from bipartite graph streams, they suffer from either low accuracy or high time complexity. Therefore, it is still a challenge to accurately estimate butterfly counts from bipartite graph streams in a short time. To address this issue, we develop novel algorithms by exploiting the bipartite nature, which subtly integrates sampling and sketching techniques. We provide accurate estimators for butterfly counts and derive simple yet exact formulas for bounding their errors. We also conduct extensive experiments on a variety of real-world large bipartite graphs. Experimental results demonstrate that our algorithms are up to 20.0 times more accurate and up to 286.3 times faster than state-of-the-art methods under the same memory usage.

With numerous nodes on online heterogeneous networks, how to reach and extract target nodes of our specific interests is a pressing problem. In this paper, we propose a novel heterogeneous network crawler,MCrawl. It addresses the problem via iterative online heterogeneous network crawling by navigating its available APIs, starting from a set of target nodes, i.e., seed nodes. We are facing two challenges towards addressing the problem. First, to navigate within a vast network, how do we start from a small set of target nodes? In other words, which nodes in the “current frontier” and which direction shall we expand, to reach promising target nodes quickly? We propose motif-based crawling to exploit the complex structures and rich semantics of heterogeneous networks. Second, in many scenarios, we do not have a classifier to assess the quality of the harvested nodes and thus the motifs to expand. We develop a probabilistic inference framework to estimate the yield and harvest rates of motifs, achieving principled bootstrapping for crawling. Our experiment on real networks of MCrawl achieves significant margins over baselines.

Network embedding algorithms learn a mapping from the discrete representation of nodes to continuous vector spaces that preserve the proximities of nodes. The techniques have a wide range of applications in various downstream tasks such as node classification, link prediction, and network alignment. Despite recent efforts to the design of novel models, little attention has been paid to understanding the instability of network embedding. In this paper, we fill this gap by investigating several state-of-the-art network embedding methods. Node embeddings form a geometric shape in the latent space. Characterizing the geometry is critical to figure out the variance of network embedding. Hence, we define two metrics to characterize the geometric properties and find that node embeddings tremble in different instantiations of an embedding space. Then, we formally define the stability of node embeddings as the invariance of the nearest neighbors of nodes. Experimental results show that existing embedding approaches have significant amounts of instability. We explore the influence factors that affect the stability of different methods and find that both network structure and algorithm models affect the stability of node embeddings significantly. Finally, we examine the implications of embedding instability for downstream tasks and find remarkable impacts on the performance.

Understanding mobile data traffic and forecasting future traffic trend is beneficial to wireless carriers and service providers who need to perform resource allocation and energy saving management. However, predicting wireless traffic accurately at large-scale and fine-granularity is particularly challenging due to the following two factors: the spatial correlations between the network units (i.e., a cell tower or an access point) introduced by user arbitrary movements, and the time-evolving nature of user movements which frequently changes with time. In this paper, we use a time-evolving graph to formulate the time-evolving nature of user movements, and propose a model Graph-based Temporal Convolutional Network (GTCN) to predict the future traffic of each network unit in a wireless network. GTCN can bring significant benefits to two aspects. (1) GTCN can effectively learn intra- and inter-time spatial correlations between network units in a time-evolving graph through a node aggregation method. (2) GTCN can efficiently model the temporal dynamics of the mobile traffic trend from different network units through a temporal convolutional layer. Experimental results on two real-world datasets demonstrate the efficiency and efficacy of our method. Compared with state-of-the-art methods, the improvement of the prediction performance of our GTCN is 3.2 to 10.2 percent for different prediction horizons. GTCN also achieves 8.4× faster on prediction time.

Contract consistency is important in ensuring the legal validity of the contract. In many scenarios, a contract is written by filling the blanks in a precompiled form. Due to carelessness, two blanks that should be filled with the same (or different) content may be incorrectly filled with different (or same) content. This will result in the issue of contract inconsistencies, which may severely impair the legal validity of the contract. Traditional methods to address this issue mainly rely on manual contract review, which is labor-intensive and costly. In this work, we formulate a novel Contract Inconsistency Checking (CIC) problem, and design an end-to-end framework, called Pair-wise Blank Resolution (PBR), to solve the CIC problem with high accuracy. Our PBR model contains a novel BlankCoder to address the challenge of modeling meaningless blanks. BlankCoder adopts a two-stage attention mechanism that adequately associates a meaningless blank with its relevant descriptions while avoiding the incorporation of irrelevant context words. Experiments conducted on real-world datasets show the promising performance of our method with a balanced accuracy of 94.05% and an F1 score of 90.90% in the CIC problem.

Many real-world datasets are given in the format of data streams, and processing these data streams is fundamental for many applications such as anomaly detection. In this paper, we study the problem of computing item frequencies, finding topk hot items, and detecting heavy changes. However, the widelyused sketches cost large memory usage and their performance is easily affected by the unbalanced distribution of data streams. To solve this issue, a novel method Cold Filter (CF) is proposed to split cold items and hot items, and use a separate structure to record the frequencies of hot items. Typically, CF has a small filter range and is only effective for filtering cold items with small frequencies. For some real-world applications, however, the cold items' frequencies may also be greater than hundreds or even tens of thousands. To solve the above challenges, we exploit the “LogLog” structure and develop a memory-efficient method LogLog Filter (LLF) to accurately estimate the above three metrics. LLF builds a register array where each register approximately counts the sum of item frequencies hashed into it. Our method remarkably enlarges the filter range of CF with fewer bits and only requires 4 bits to filter cold items with frequencies up to 224. We conduct extensive experiments on real-world and synthetic datasets, and the experimental results demonstrate the efficiency and effectiveness of our method.

Kernel density estimation method is a powerful tool and is widely used in many important real-world applications such as anomaly detection and statistical learning. Unfortunately, current kernel methods suffer from high computational or space costs when dealing with large-scale, high-dimensional datasets, especially when the datasets of interest are given in a stream fashion. Although there are sketch methods designed for kernel density estimation over data streams, they still suffer from high computational costs. To address this problem, in this paper, we propose a novel Rotation Kernel. The Rotation Kernel is based on a Rotation Hash method and is much faster to compute. To achieve memory-efficient kernel density estimation over data streams, we design a method, RKD-Sketch, which compresses high dimensional data streams into a small array of integer counters. We conduct extensive experiments on both synthetic and real-world datasets, and experimental results demonstrate that our RKD-Sketch saves up to 216 times computational resources and up to 104 times space resources than state-of-the-arts. Furthermore, we apply our Rotation Kernel in active learning. Results show that our method achieves up to 256 times speedup and saves up to 13 times space to achieve the same accuracy as the baseline methods.

Submodular optimization lies at the core of many data mining and machine learning applications such as data summarization and subset selection. For data streams where elements arrive one at a time, streaming submodular optimization (SSO) algorithms are desired. Existing SSO solutions are mainly designed for insertion-only streams where elements in the stream all participate in the analysis, or sliding-window streams where only the most recent data participates in the analysis. SSO for insertion-only streams does not sufficiently emphasize recent data. SSO for sliding-window streams abruptly forgets all past data. In this work, we propose a new SSO problem, i.e., temporal biased streaming submodular optimization (TBSSO), which embraces the special settings of all previous studies. TBSSO leverages a temporal bias function to force each element in the stream to participate in the analysis with a probability decreasing over time and hence elements in the stream are forgotten gradually. We design novel streaming algorithms to solve the TBSSO problem with provable approximation guarantees. Experiments show that our algorithm can find high quality solutions and improve the efficiency to about one order of magnitude faster than the baseline method.

As an efficient tool for approximate similarity computation and search, Locality Sensitive Hashing (LSH) has been widely used in many research areas including databases, data mining, information retrieval, and machine learning. Classical LSH methods typically require to perform hundreds or even thousands of hashing operations when computing the LSH sketch for each input item (e.g., a set or a vector); however, this complexity is still too expensive and even impractical for applications requiring processing data in real-time. To address this issue, several fast methods such as OPH and BCWS have been proposed to efficiently compute the LSH sketches; however, these methods may generate many sketches with empty bins, which may introduce large errors for similarity estimation and also limit their usage for fast similarity search. To solve this issue, we propose a novel densification method, i.e., BiDens. Compared with existing densification methods, our BiDens is more efficient to fill a sketch's empty bins with values of its non-empty bins in either the forward or backward directions. Furthermore, it also densifies empty bins to satisfy the densification principle (i.e., the LSH property). Theoretical analysis and experimental results on similarity estimation, fast similarity search, and kernel linearization using real-world datasets demonstrate that our BiDens is up to 106 times faster than state-of-the-art methods while achieving the same or even better accuracy.

Given a set S, Membership Querying (MQ) answers whether a query element $q\in S$. It is a fundamental task in areas like database systems and computer networks. In this paper, we consider a more general problem, Multi-Set Multi-Membership Querying (MS-MMQ). Given n sets $S_0,łdots,S_n-1 $, MS-MMQ answers which sets contain element q. A direct way to address MS-MMQ is to build an MQ structure (e.g., Bloom Filter) for each set. However, the query and space complexities grow linearly with n and become prohibitive for a large n. To address this challenge, we propose a novel Circular Shift and Coalesce (CSC) framework to efficiently achieve approximate MS-MMQ. Instead of building an MQ data structure for each set, the CSC index encodes all n sets into a compact sketch and retrieves only a few bytes in the sketch for a query, which achieves high memory-efficiency and boosts the query speed by several times. CSC is compatible with mainstream data structures for Approximate MQ. We conduct experiments on real-world datasets and results demonstrate that our framework is up to 91.2 times faster and up to 48.9 times more accurate than state-of-the-art methods.

Modern cloud-scale data centers necessitate self-healing (i.e., the automation of detecting and repairing component failures) to support reliable and scalable cloud services in the face of prevalent failures. Traditional policy-based self-healing solutions rely on expert knowledge to define the proper policies for choosing repair actions, and hence are error-prone and non-scalable in practical deployment. We propose AIHS, an automated intelligent healing system that applies machine learning to achieve scalable self-healing in cloud-scale data centers. AIHS is designed as a full-fledged, general pipeline that supports various machine learning models for predicting accurate repair actions based on raw monitoring logs. We conduct extensive trace-driven and production experiments, and show that AIHS achieves higher prediction accuracy than current self-healing solutions and successfully fixes 92.4% of the total of 33.7 million production failures over seven months. AIHS also reduces 51% of unavailable time of each failed server on average compared to policy-based self-healing. AIHS is now deployed in production cloud-scale data centers at Alibaba with a total of 600 K servers. We open-source a Python prototype that reproduces the self-healing pipeline of AIHS for public validation.

With the development of Internet technology, service providers can provide users with personalized services to enrich user experience, however, this often requires a large number of users’ private data. Meanwhile, the protection of their private data and the evaluation of the risk of leaked datasets become a matter of great concern to many people. To resolve these issues, in this paper, we develop a machine learning-based approach in online social networks (OSNs) to efficiently correlate the leaked datasets and accurately learn millions of users’ confidential information. Moreover, a trust evaluation model is developed in OSNs to identify malicious service providers and secure users’ social activities via direct trust computing and indirect trust computing. Extensive experiments are conducted by using real-world leaked datasets, and the results show that the efficiency and effectiveness of the proposed approach in terms of user privacy protection and accuracy of privacy leakage evaluation.

Estimating set similarity and detecting highly similar sets are fundamental problems in areas such as databases and machine learning. MinHash is a well-known technique for approximating Jaccard similarity of sets and has been successfully used for many applications. Its two compressed versions, b-bit MinHash and Odd Sketch, can significantly reduce the memory usage of the MinHash, especially for estimating high similarities (i.e., similarities around 1). Although MinHash can be applied to static sets as well as streaming sets, of which elements are given in a streaming fashion, unfortunately, b-bit MinHash and Odd Sketch fail to deal with streaming data. To solve this problem, we previously designed a memory-efficient sketch method, MaxLogHash, to accurately estimate Jaccard similarities in streaming sets. Compared with MinHash, our method uses smaller sized registers (each register consists of less than 7 bits) to build a compact sketch for each set. In this paper, we further develop a faster method, MaxLogOPH++. Compared with MaxLogHash, MaxLogOPH++ reduces the time complexity for updating each coming element from O(k) with a small additional memory. We conduct experiments on a variety of datasets, and experimental results demonstrate the efficiency and effectiveness of our methods.

Legal Judgment Prediction (LJP) is the task of automatically predicting a law case's judgment results given a text describing its facts, which has excellent prospects in judicial assistance systems and convenient services for the public.In practice, confusing charges are frequent, because law cases applicable to similar law articles are easily misjudged.For addressing this issue, the existing method relies heavily on domain experts, which hinders its application in different law systems.In this paper, we present an end-to-end model, LADAN, to solve the task of LJP.To distinguish confusing charges, we propose a novel graph neural network to automatically learn subtle differences between confusing law articles and design a novel attention mechanism that fully exploits the learned differences to extract compelling discriminative features from fact descriptions attentively.Experiments conducted on realworld datasets demonstrate the superiority of our LADAN.

The sheer scale of big data causes the information overload issue and there is an urgent need for tools that can draw valuable insights from massive data. This paper investigates the core items tracking (CIT) problem where the goal is to continuously track representative items, called core items, in a data stream so to best represent/summarize the stream. In order to simultaneously satisfy the recency and continuity requirements, we consider CIT over probabilistic-decaying streams where items in the stream are forgotten gradually in a probabilistic manner. We first introduce an algorithm, called PNDCIT, to find core items in a special kind of probabilistic non-decaying streams. Furthermore, using PNDCIT as a building block, we design two novel algorithms, namely PDCIT and PDCIT+, to maintain core items over probabilistic-decaying streams with constant approximation ratios. Finally, extensive experiments on real data demonstrate that PDCIT+ achieves a speedup of up to one order of magnitude over a batch algorithm while providing solutions with comparable quality.

We study the problem of node classification on graphs with few-shot novel labels, which has two distinctive properties: (1) There are novel labels to emerge in the graph; (2) The novel labels have only a few representative nodes for training a classifier. The study of this problem is instructive and corresponds to many applications such as recommendations for newly formed groups with only a few users in online social networks. To cope with this problem, we propose a novel Meta Transformed Network Embedding framework (MetaTNE), which consists of three modules: (1) A \emph{structural module} provides each node a latent representation according to the graph structure. (2) A \emph{meta-learning module} captures the relationships between the graph structure and the node labels as prior knowledge in a meta-learning manner. Additionally, we introduce an \emph{embedding transformation function} that remedies the deficiency of the straightforward use of meta-learning. Inherently, the meta-learned prior knowledge can be used to facilitate the learning of few-shot novel labels. (3) An \emph{optimization module} employs a simple yet effective scheduling strategy to train the above two modules with a balance between graph structure learning and meta-learning. Experiments on four real-world datasets show that MetaTNE brings a huge improvement over the state-of-the-art methods.

The well-known Gumbel-Max Trick for sampling elements from a categorical distribution (or more generally a nonnegative vector) and its variants have been widely used in areas such as machine learning and information retrieval. To sample a random element i (or a Gumbel-Max variable i) in proportion to its positive weight vi, the Gumbel-Max Trick first computes a Gumbel random variable gi for each positive weight element i, and then samples the element i with the largest value of gi + ln vi. Recently, applications including similarity estimation and graph embedding require to generate k independent Gumbel-Max variables from high dimensional vectors. However, it is computationally expensive for a large k (e.g., hundreds or even thousands) when using the traditional Gumbel-Max Trick. To solve this problem, we propose a novel algorithm, FastGM, that reduces the time complexity from O(kn+) to O(kln k + n+), where n+ is the number of positive elements in the vector of interest. Instead of computing k independent Gumbel random variables directly, we find that there exists a technique to generate these variables in descending order. Using this technique, our method FastGM computes variables gi + ln vi for all positive elements i in descending order. As a result, FastGM significantly reduces the computation time because we can stop the procedure of Gumbel random variables computing for many elements especially for those with small weights. Experiments on a variety of real-world datasets show that FastGM is orders of magnitude faster than state-of-the-art methods without sacrificing accuracy and incurring additional expenses.

Anomaly detection is an important technique used to identify patterns of unusual network behavior and keep the network under control. Today, network attacks are increasing in terms of both their number and sophistication. To avoid causing significant traffic patterns and being detected by existing techniques, many new attacks tend to involve gradual adjustment of behaviors, which always generate incomplete sessions due to their running mechanisms. Accordingly, in this work, we employ the behavior symmetry degree to profile the anomalies and further identify unusual behaviors. We first proposed a symmetry degree to identify the incomplete sessions generated by unusual behaviors; we then employ a sketch to calculate the symmetry degree of internal hosts to improve the identification efficiency for online applications. To reduce the memory cost and probability of collision, we divide the IP addresses into four segments that can be used as keys of the hash functions in the sketch. Moreover, to further improve detection accuracy, a threshold selection method is proposed for dynamic traffic pattern analysis. The hash functions in the sketch are then designed using Chinese remainder theory, which can analytically trace the IP addresses associated with the anomalies. We tested the proposed techniques based on traffic data collected from the northwest center of CERNET (China Education and Research Network); the results show that the proposed methods can effectively detect anomalies in large-scale networks.

Cardinality constrained submodular function maximization, which aims to select a subset of size at most k to maximize a monotone submodular utility function, is the key in many data mining and machine learning applications such as data summarization and maximum coverage problems. When data is given as a stream, streaming submodular optimization (SSO) techniques are desired. Existing SSO techniques can only apply to insertion-only streams where each element has an infinite lifespan, and sliding-window streams where each element has a same lifespan (i.e., window size). However, elements in some data streams may have arbitrary different lifespans, and this requires addressing SSO over streams with inhomogeneous-decays (SSO-ID). This work formulates the SSO-ID problem and presents three algorithms: BASIC-STREAMING is a basic streaming algorithm that achieves an (1/2 − ɛ) approximation factor; HISTAPPROX improves the efficiency significantly and achieves an (1/3 − ɛ) approximation factor; HISTSTREAMING is a streaming version of HISTAPPROX and uses heuristics to further improve the efficiency. Experiments conducted on real data demonstrate that HISTSTREAMING can find high quality solutions and is up to two orders of magnitude faster than the naive GREEDY algorithm.

Many real-world networks such as Twitter and YouTube are given as fully dynamic graph streams represented as sequences of edge insertions and deletions. (e.g., users can subscribe and unsubscribe to channels on YouTube). Existing similarity estimation methods such as MinHash and OPH are customized to static graphs. We observe that they are indeed sampling methods and exhibit a sampling bias when applied to fully dynamic graph streams, which results in large estimation errors. To solve this challenge, we develop a fast and accurate sketch method VOS. VOS processes each edge in the graph stream of interest with small time complexity O(1) and uses small memory space to build a compact sketch of the dynamic graph stream over time. Based on the sketch built on-the-fly, we develop a method to estimate user similarities over time. We conduct extensive experiments and the experimental results demonstrate the efficiency and efficacy of our method.

Recently, considerable efforts have been devoted to approximately computing the global and local (i.e., incident to each node) triangle counts of a large graph stream represented as a sequence of edges. Existing approximate triangle counting algorithms rely on sampling techniques to reduce the computational cost. However, their estimation errors are significantly determined by the covariance between sampled triangles. Moreover, little attention has been paid to developing parallel one-pass streaming algorithms that can be used to fast and approximately count triangles on a multi-core machine or a cluster of machines. To solve these problems, we develop a novel parallel method REPT to significantly reduce the covariance (even completely eliminate the covariance for some cases) between sampled triangles. We theoretically prove that REPT is more accurate than parallelizing existing triangle count estimation algorithms in a direct manner. In addition, we also conduct extensive experiments on a variety of real-world graphs, and the results demonstrate that our method REPT is several times more accurate than state-of-the-art methods.

Online monitoring user cardinalities (or degrees) in graph streams is fundamental for many applications. For example in a bipartite graph representing user-website visiting activities, user cardinalities (the number of distinct visited websites) are monitored to report network anomalies. These real-world graph streams may contain user-item duplicates and have a huge number of distinct user-item pairs, therefore, it is infeasible to exactly compute user cardinalities when memory and computation resources are limited. Existing methods are designed to approximately estimate user cardinalities, whose accuracy highly depends on parameters that are not easy to set. Moreover, these methods cannot provide anytime-available estimation, as the user cardinalities are computed at the end of the data stream. Realtime applications such as anomaly detection require that user cardinalities are estimated on the fly. To address these problems, we develop novel bit and register sharing algorithms, which use a bit array and a register array to build a compact sketch of all users' connected items respectively. Compared with previous bit and register sharing methods, our algorithms exploit the dynamic properties of the bit and register arrays (e.g., the fraction of zero bits in the bit array at each time) to significantly improve the estimation accuracy, and have low time complexity (O(1)) to update the estimations each time they observe a new useritem pair. In addition, our algorithms are simple and easy to use, without requirements to tune any parameter. We evaluate the performance of our methods on real-world datasets. The experimental results demonstrate that our methods are several times more accurate and faster than state-of-the-art methods using the same amount of memory.

Identifying influential nodes that can jointly trigger the maximum influence spread in networks is a fundamental problem in many applications such as viral marketing, online advertising, and disease control. Most existing studies assume that social influence is static and they fail to capture the dynamics of influence in reality. In this work, we address the dynamic influence challenge by designing efficient streaming methods that can identify influential nodes from highly dynamic node interaction streams. We first propose a general time-decaying dynamic interaction network (TDN) model to model node interaction streams with the ability to smoothly discard outdated data. Based on the TDN model, we design three algorithms, i.e., SieveADN, BasicReduction and HistApprox. SieveADN identifies influential nodes from a special kind of TDNs with efficiency. BasicReduction uses SieveADN as a basic building block to identify influential nodes from general TDNs. HistApprox significantly improves the efficiency of BasicReduction. More importantly, we theoretically show that all three algorithms enjoy constant factor approximation guarantees. Experiments conducted on various real interaction datasets demonstrate that our approach finds near-optimal solutions with speed at least 5 to 15 times faster than baseline methods.

Despite significant progress, deep reinforcement learning (RL) suffers from data-inefficiency and limited generalization. Recent efforts apply meta-learning to learn a meta-learner from a set of RL tasks such that a novel but related task could be solved quickly. Though specific in some ways, different tasks in meta-RL are generally similar at a high level. However, most meta-RL methods do not explicitly and adequately model the specific and shared information among different tasks, which limits their ability to learn training tasks and to generalize to novel tasks. In this paper, we propose to capture the shared information on the one hand and meta-learn how to quickly abstract the specific information about a task on the other hand. Methodologically, we train an SGD meta-learner to quickly optimize a task encoder for each task, which generates a task embedding based on past experience. Meanwhile, we learn a policy which is shared across all tasks and conditioned on task embeddings. Empirical results on four simulated tasks demonstrate that our method has better learning capacity on both training and novel tasks and attains up to 3 to 4 times higher returns compared to baselines.

Predicting interactions between structured entities lies at the core of numerous tasks such as drug regimen and new material design. In recent years, graph neural networks have become attractive. They represent structured entities as graphs, and then extract features from each individual graph using graph convolution operations. However, these methods have some limitations: i) their networks only extract features from a fix-sized subgraph structure (i.e., a fix-sized receptive field) of each node, and ignore features in substructures of different sizes, and ii) features are extracted by considering each entity independently, which may not effectively reflect the interaction between two entities. To resolve these problems, we present {\em MR-GNN}, an end-to-end graph neural network with the following features: i) it uses a multi-resolution based architecture to extract node features from different neighborhoods of each node, and, ii) it uses dual graph-state long short-term memory networks (LSTMs) to summarize local features of each graph and extracts the interaction features between pairwise graphs. Experiments conducted on real-world datasets show that MR-GNN improves the prediction of state-of-the-art methods.

Estimating set similarity and detecting highly similar sets are fundamental problems in areas such as databases, machine learning, and information retrieval. MinHash is a well-known technique for approximating Jaccard similarity of sets and has been successfully used for many applications such as similarity search and large scale learning. Its two compressed versions, b-bit MinHash and Odd Sketch, can significantly reduce the memory usage of the original MinHash method, especially for estimating high similarities (i.e., similarities around 1). Although MinHash can be applied to static sets as well as streaming sets, of which elements are given in a streaming fashion and cardinality is unknown or even infinite, unfortunately, b-bit MinHash and Odd Sketch fail to deal with streaming data. To solve this problem, we design a memory efficient sketch method, MaxLogHash, to accurately estimate Jaccard similarities in streaming sets. Compared to MinHash, our method uses smaller sized registers (each register consists of less than 7 bits) to build a compact sketch for each set. We also provide a simple yet accurate estimator for inferring Jaccard similarity from MaxLogHash sketches. In addition, we derive formulas for bounding the estimation error and determine the smallest necessary memory usage (i.e., the number of registers used for a MaxLogHash sketch) for the desired accuracy. We conduct experiments on a variety of datasets, and experimental results show that our method MaxLogHash is about 5 times more memory efficient than MinHash with the same accuracy and computational cost for estimating high similarities.

Estimating distributions of node characteristics (labels) such as number of connections or citizenship of users in a social network via edge and node sampling is a vital part of the study of complex networks. Due to its low cost, sampling via a random walk (RW) has been proposed as an attractive solution to this task. Most RW methods assume either that the network is undirected or that walkers can traverse edges regardless of their direction. Some RW methods have been designed for directed networks where edges coming into a node are not directly observable. In this work, we propose Directed Unbiased Frontier Sampling (DUFS), a sampling method based on a large number of coordinated walkers, each starting from a node chosen uniformly at random. It applies to directed networks with invisible incoming edges because it constructs, in real time, an undirected graph consistent with the walkers trajectories, and its use of random jumps to prevent walkers from being trapped. DUFS generalizes previous RW methods and is suited for undirected networks and to directed networks regardless of in-edge visibility. We also propose an improved estimator of node label distribution that combines information from initial walker locations with subsequent RW observations. We evaluate DUFS, compare it to other RW methods, investigate the impact of its parameters on estimation accuracy and provide practical guidelines for choosing them. In estimating out-degree distributions, DUFS yields significantly better estimates of the head of the distribution than other methods, while matching or exceeding estimation accuracy of the tail. Last, we show that DUFS outperforms uniform sampling when estimating distributions of node labels of the top 10% largest degree nodes, even when sampling a node uniformly has the same cost as RW steps.

Monitoring user behaviors over high speed links is important for applications such as network anomaly detection. Previous work focuses on monitoring anomalies such as extremely frequent users occurring in a short timeslot such as 1 minute. Little attention has been paid to detect users with stealthy behaviors (e.g., persistent, co-occurrence, anti-co-occurrence, and periodic behaviors) over a long period of time at the timeslot granularity. Due to limited computation and storage resources on routers, it is prohibitive to collect massive network traffic in a long period of time. We develop an end-to-end method for solving challenges in both long-term online traffic collection and offline user behavior analysis. We conduct extensive experiments on a variety of real-world traffic to evaluate the performance of detecting persistent, co-occurrence, anti-co-occurrence, and periodic behaviors, and the results demonstrate that our method significantly outperforms state-of-the-art methods.

Recently exploring locally connected subgraphs (also known as motifs or graphlets) of complex networks attracts a lot of attention. Previous work made the strong assumption that the graph topology of interest is known in advance. In practice, sometimes researchers have to deal with the situation where the graph topology is unknown because it is expensive to collect and store all topological information. Hence, typically what is available to researchers is only a snapshot of the graph, i.e., a subgraph of the graph. Crawling methods such as breadth first sampling can be used to generate the snapshot. However, these methods fail to sample a streaming graph represented as a high speed stream of edges. Therefore, graph mining applications such as network traffic monitoring usually use random edge sampling (i.e., sample each edge with a fixed probability) to collect edges and generate a sampled graph, which we call a “ RESampled graph”. Clearly, a RESampled graph's motif statistics may be quite different from those of the original graph. To resolve this, we propose a framework Minfer, which takes the given RESampled graph and accurately infers the underlying graph's motif statistics. Experiments using large scale datasets show the accuracy and efficiency of our method.

Distinct sampling is fundamental for computing statistics (e.g., the age and gender distribution of distinct users accessing a particular website) depending on the set of distinct keys (e.g., user IDs) in a large and high speed data stream such as a sequence of key-update pairs. However, the major shortcoming of existing methods is their high computational cost incurred by determining whether each incoming key in the data stream is currently in the set of sampled keys and keeping track of sampled keys’ update aggregations. To solve this challenge, we develop a new methodrandom projection and eviction(RPE) that uses a list of buckets to continuously sample distinct keys and their update aggregations. RPE processes each key-update pair with small and nearly constant time complexity$O(1)$. Besides centralized data streams, we also develop a novel method DRPE to deal with distributed data streams consisting of key-update pairs observed at multiple distributed sites. We conduct extensive experiments on real-world datasets, and the results demonstrate that RPE and DRPE reduce the memory, computational, and message costs of state-of-the-art methods by several times.

Despite recent efforts in counting 3-node and 4-node graphlets, little attention has been paid to characterizing 5-node graphlets. In this paper, we develop a computationally efficient sampling method to estimate 5-node graphlet counts. We not only provide a fast sampling method and unbiased estimators of graphlet counts, but also derive simple yet exact formulas for the variances of the estimators which are of great value in practice-the variances can be used to bound the estimates' errors and determine the smallest necessary sampling budget for a desired accuracy. We conduct experiments on a variety of real-world datasets, and the results show that our method is several orders of magnitude faster than the state-of-the-art methods with the same accuracy.

Mining user behaviors over high speed links is important for applications such as network anomaly detection. Previous work focuses on monitoring anomalies such as extremely frequent users occurring in a short timeslot such as 1 minute. Little attention has been paid to detect users with stealthy behaviors such as persistent frequent and co-occurrence behaviors over a long period of time at the timeslot granularity (e.g., 1 minute granularity level). Unlike frequent users, persistent users do not necessarily occur more frequently than other users in a single timeslot, but persist and occur in a larger number of timeslots. Due to limited computation and storage resources on routers, it is prohibitive to collect massive network traffic in a long period of time. We develop an end-to-end method for solving challenges in both long-term online traffic collection and offline user behavior analysis. To achieve this goal, we design a user embedding (UE) method to fast build compact sketches of user-occurrence events over time. To reduce the estimation error introduced by Bloom Filter, we model UE as a sampling method and propose methods to accurately mine a variety of user behaviors from user-occurrence events rebuilt from UE sketches. In addition, we introduce another new embedding method reversible UE (RUE) to detect persistent frequent behaviors when monitored users' IDs are not given in advance for offline analysis. We conduct extensive experiments on real-world traffic, and the results demonstrate that our methods significantly outperform state-of-the-art methods.

Counting 3-, 4-, and 5-node graphlets in graphs is important for graph mining applications such as discovering abnormal/ evolution patterns in social and biology networks. In addition, it is recently widely used for computing similarities between graphs and graph classification applications such as protein function prediction and malware detection. However, it is challenging to compute these graphlet counts for a large graph or a large set of graphs due to the combinatorial nature of the problem. Despite recent efforts in counting 3-node and 4-node graphlets, little attention has been paid to characterizing 5-node graphlets. In this paper, we develop a computationally efficient sampling method to estimate 5-node graphlet counts. We not only provide a fast sampling method and unbiased estimators of graphlet counts, but also derive simple yet exact formulas for the variances of the estimators which are of great value in practice-the variances can be used to bound the estimates' errors and determine the smallest necessary sampling budget for a desired accuracy. We conduct experiments on a variety of real-world datasets, and the results show that our method is several orders of magnitude faster than the state-of-the-art methods with the same accuracy.

Counting triangles in a large graph is important for detecting network anomalies such as spam web pages and suspicious accounts (e.g., fraudsters and advertisers) on online social networks. However, it is challenging to compute the number of triangles in a large graph represented as a stream of edges with a low computational cost when given a limited memory. Recently, several effective sampling-based approximation methods have been developed to solve this problem. However, they assume the graph stream of interest contains no duplicate edges, which does not hold in many real-world graph streams (e.g., phone calling networks). In this paper, we observe that these methods exhibit a large estimation error or computational cost even when modified to deal with duplicate edges using deduplication techniques such as Bloom filter and hash-based sampling. To solve this challenge, we design a one-pass streaming algorithm for uniformly sampling distinct edges at a high speed. Compared to state-of-the-art algorithms, our algorithm reduces the sampling cost per edge from O (log k ) ( k is the maximum number of sampled edges determined by the available memory space) to O (1) without using any additional memory space. Based on sampled edges, we develop a simple yet accurate method to infer the number of triangles in the original graph stream. We conduct extensive experiments on a variety of real-world large graphs, and the results demonstrate that our method is several times more accurate and faster than state-of-the-art methods with the same memory usage.

Characterizing motif (i.e., locally connected sub-graph patterns) statistics is important for understanding complex networks such as online social networks and communication networks. Previous work made the strong assumption that the graph topology of interest is known in advance. In practice, sometimes researchers have to deal with the situation where the graph topology is unknown because it is expensive to collect and store all topological and meta information. Hence, typically what is available to researchers is only a snapshot of the graph, i.e., a subgraph of the graph. Crawling methods such as breadth first sampling can be used to generate the snapshot. However, these methods fail to sample a streaming graph represented as a high speed stream of edges. Therefore, graph mining applications such as network traffic monitoring use random edge sampling (i.e., sample each edge with a fixed probability) to collect edges and generate a sampled graph, which we called a “RESampled graph”. Clearly, a RESampled graph's motif statistics may be quite different from those of the underlying original graph. To resolve this, we propose a framework and implement a system called Minfer, which takes the given RESampled graph and accurately infers the underlying graph's motif statistics. We also apply Fisher information to bound the errors of our estimates. Experiments using large scale datasets show the accuracy and efficiency of our method.

Graphlets are induced subgraph patterns and have been frequently applied to characterize the local topology structures of graphs across various domains, e.g., online social networks (OSNs) and biological networks. Discovering and computing graphlet statistics are highly challenging. First, the massive size of real-world graphs makes the exact computation of graphlets extremely expensive. Secondly, the graph topology may not be readily available so one has to resort to web crawling using the available application programming interfaces (APIs). In this work, we propose a general and novel framework to estimate graphlet statistics of " any size. " Our framework is based on collecting samples through consecutive steps of random walks. We derive an analytical bound on the sample size (via the Chernoff-Hoeffding technique) to guarantee the convergence of our unbiased estimator. To further improve the accuracy, we introduce two novel optimization techniques to reduce the lower bound on the sample size. Experimental evaluations demonstrate that our methods outperform the state-of-the-art method up to an order of magnitude both in terms of accuracy and time cost.

Recently, map services (e.g., Google maps) and location-based online social networks (e.g., Foursquare) attract a lot of attention and businesses. With the increasing popularity of these location-based services, exploring and characterizing points of interests (PoIs) such as restaurants and hotels on maps provides valuable information for applications such as start-up marketing research. Due to the lack of a direct fully access to PoI databases, it is infeasible to exhaustively search and collect all PoIs within a large area using public APIs, which usually impose a limit on the maximum query rate. In this paper, we propose sampling methods to accurately estimate PoI statistics such as sum and average aggregates from as few queries as possible. Experimental results based on real datasets show that our methods are efficient, and require six times less queries than state-of-the-art methods to achieve the same accuracy.

Random walk-based graph sampling methods have become increasingly popular and important for characterizing large-scale complex networks. While powerful, they are known to exhibit problems when the graph is loosely connected, which slows down the convergence of a random walk and can result in poor estimation accuracy. In this work, we observe that many graphs under study, called target graphs, usually do not exist in isolation. In many situations, a target graph is often related to an auxiliary graph and an affiliation graph, and the target graph becomes better connected when viewed from these three graphs as a whole, or what we called a hybrid social-affiliation network. This viewpoint brings extra benefits to the graph sampling framework, e.g., when directly sampling a target graph is difficult or inefficient, we can efficiently sample it with the assistance of auxiliary and affiliation graphs. We propose three sampling methods on such a hybrid social-affiliation network to estimate target graph characteristics, and conduct extensive experiments on both synthetic and real datasets, to demonstrate the effectiveness of these new sampling methods.

Characterizing user pair relationships is important for applications such as friend recommendation and interest targeting in online social networks (OSNs). Due to the large-scale nature of such networks, it is infeasible to enumerate all user pairs and thus sampling is used. In this article, we show that it is a great challenge for OSN service providers to characterize user pair relationships, even when they possess the complete graph topology. The reason is that when sampling techniques (i.e., uniform vertex sampling (UVS) and random walk (RW)) are naively applied, they can introduce large biases, particularly for estimating similarity distribution of user pairs with constraints like existence of mutual neighbors, which is important for applications such as identifying network homophily. Estimating statistics of user pairs is more challenging in the absence of the complete topology information, as an unbiased sampling technique like UVS is usually not allowed and exploring the OSN graph topology is expensive. To address these challenges, we present unbiased sampling methods to characterize user pair properties based on UVS and RW techniques. We carry out an evaluation of our methods to show their accuracy and efficiency. Finally, we apply our methods to three OSNs—Foursquare, Douban, and Xiami—and discover that significant homophily is present in these networks.

Recently map services (e.g., Google maps) and location-based online social networks (e.g., Foursquare) attract a lot of attention and businesses. With the increasing popularity of these location-based services, exploring and characterizing points of interests (PoIs) such as restaurants and hotels on maps provides valuable information for applications such as start-up marketing research. Due to the lack of a direct fully access to PoI databases, it is infeasible to exhaustively search and collect all PoIs within a large area using public APIs, which usually impose a limit on the maximum query rate. In this paper, we propose an effective and efficient method to sample PoIs on maps, and give unbiased estimators to calculate PoI statistics such as sum and average aggregates. Experimental results based on real datasets show that our method is efficient, and requires six times less queries than state-of-the-art methods to achieve the same accuracy.

The host connection degree distribution (HCDD) is an important metric for network security monitoring. However, it is difficult to accurately obtain the HCDD in real time for high-speed links with a massive amount of traffic data. In this paper, we propose a new sketch method to build a probabilistic traffic summary of a host's flows using a uniform Flajolet-Martin sketch combined with a small bitmap. To study its performance in comparison with previous sampling and sketch methods, we present a general model that encompasses all these methods. With this model, we compute the Cramér-Rao lower bounds and the variances of HCDD estimations. The theoretic analysis and numerical experimental results show that our sketch method is six times more accurate than state-of-the-art methods with the same memory usage.

Exploring statistics of locally connected subgraph patterns (also known as network motifs) has helped researchers better understand the structure and function of biological and Online Social Networks (OSNs). Nowadays, the massive size of some critical networks—often stored in already overloaded relational databases—effectively limits the rate at which nodes and edges can be explored, making it a challenge to accurately discover subgraph statistics. In this work, we propose sampling methods to accurately estimate subgraph statistics from as few queried nodes as possible. We present sampling algorithms that efficiently and accurately estimate subgraph properties of massive networks. Our algorithms require no precomputation or complete network topology information. At the same time, we provide theoretical guarantees of convergence. We perform experiments using widely known datasets and show that, for the same accuracy, our algorithms require an order of magnitude less queries (samples) than the current state-of-the-art algorithms.

Characterizing user pair relationships is important for applications such as friend recommendation and interest targeting in online social networks (OSNs). Due to the large scale nature of such networks, it is infeasible to enumerate all user pairs and so sampling is used. In this paper, we show that it is a great challenge even for OSN service providers to characterize user pair relationships even when they possess the complete graph topology. The reason is that when sampling techniques (i.e., uniform vertex sampling (UVS) and random walk (RW)) are naively applied, they can introduce large biases, in particular, for estimating similarity distribution of user pairs with constraints such as existence of mutual neighbors, which is important for applications such as identifying network homophily. Estimating statistics of user pairs is more challenging in the absence of the complete topology information, since an unbiased sampling technique such as UVS is usually not allowed, and exploring the OSN graph topology is expensive. To address these challenges, we present asymptotically unbiased sampling methods to characterize user pair properties based on UVS and RW techniques respectively. We carry out an evaluation of our methods to show their accuracy and efficiency. Finally, we apply our methods to two Chinese OSNs, Doudan and Xiami, and discover significant homophily is present in these two networks.

In this work we study the set size distribution estimation problem, where elements are randomly sampled from a collection of non-overlapping sets and we seek to recover the original set size distribution from the samples. This problem has applications to capacity planning and network theory. Examples of real-world applications include characterizing in-degree distributions in large graphs and uncovering TCP/IP flow size distributions on the Internet. We demonstrate that it is difficult to estimate the original set size distribution. The recoverability of original set size distributions presents a sharp threshold with respect to the fraction of elements that remain in the sets. If this fraction lies below the threshold, typically half of the elements in power-law and heavier-than-exponential-tailed distributions, then the original set size distribution is unrecoverable. We also discuss practical implications of our findings.

Despite recent efforts to characterize complex networks such as citation graphs or online social networks (OSNs), little attention has been given to developing tools that can be used to characterize directed graphs in the wild, where no pre-processed data is available. The presence of hidden incoming edges but observable outgoing edges poses a challenge to characterize large directed graphs through crawling, as existing sampling methods cannot cope with hidden incoming links. The driving principle behind our random walk (RW) sampling method is to construct, in real-time, an undirected graph from the directed graph such that the random walk on the directed graph is consistent with one on the undirected graph. We then use the RW on the undirected graph to estimate the outdegree distribution. Our algorithm accurately estimates outdegree distributions of a variety of real world graphs. We also study the hardness of indegree distribution estimation when indegrees are latent (i.e., incoming links are only observed as outgoing edges). We observe that, in the same scenarios, indegree distribution estimates are highly innacurate unless the directed graph is highly symmetrical.

We present a new virtual indexing method for estimating host connection degrees for high speed links. It is based on the virtual connection degree sketch where a compact sketch of network traffic is built by generating the associated virtual bitmaps for each host. Each virtual bitmap consists of a fixed number of bits selected randomly from a shared bit array by a new method for recording the traffic flows of the corresponding host. The shared bit array is efficiently utilized by all hosts since its every bit is shared by the virtual bitmaps of multiple hosts. To reduce the “noise” contaminated in a host's virtual bitmaps due to sharing, we propose a new method to generate the “filtered” bitmap used to estimate host connection degree. Furthermore, it can be easily implemented in parallel and distributed processing environments. The experimental and testing results based on the actual network traffic show that the new method is accurate and efficient.

Due to the massive amount of data in high-speed network traffic and the limit on processing capability, it is a great challenge to accurately measure and monitor network traffic over high-speed links online. A new data structure is presented in this paper for locating the hosts associated with large connection degrees or significant changes in connection degrees based on the reversible connection degree sketch to monitor anomalous network traffic. The reversible connection degree sketch builds a compact summary of host connection degrees efficiently and accurately. For each packet coming, it only needs to set several bits selected in a bit array by a group of hash functions. These hash functions are designed based on the Chinese Remainder Theorem so that the in-degree or out-degree associated with a given host can be accurately estimated. With this new data structure, we develop a new reverse sketch method for locating abnormal hosts. Although the reversible connection degree sketch does not preserve any host address information, we can analytically reconstruct the host addresses associated with large connection degrees or significant changes in connection degrees by a simple calculation purely based on the characteristics of the hash functions. Furthermore, a reinforced reversible connection degree sketch, the double connection degree sketch, is developed to reduce false positives which are commonly encountered in the sketch-based methods. A traffic monitoring system based on this double connection degree is developed to detect and classify the abnormal hosts associated with large connection degrees or significant changes in connection degrees. The experiments are conducted based on the actual network traffic and the testing results show that our method is accurate and efficient.

Measuring and monitoring the changes of network traffic patterns in large-scale networks are crucial for effective network management. In this paper, we present a framework and method for detecting and measuring the dynamic changes of the pivotal traffic patterns. A bidirectional regional flow model is established to aggregate traffic packets and extract the traffic metrics and profiles. The characteristics of the regional flows are analyzed and interesting findings are obtained. A directed graph model is applied to describe the flow metrics and six flow features are extracted to capture the dynamic changes of the flow patterns. The measurements based on Renyi entropy are developed to quantitatively monitor these changes. The experimental results based on the actual network traffic data traces show that the method presented in this paper can capture the dynamic changes of pivotal traffic patterns effectively.

Locating hosts with large connection degree is very important for monitoring anomalous network traffics. The in-degree (out-degree), defined as the number of distinct sources (destinations) that a network host is connected with (connects) during a given time interval. Due to massive amount of data in high speed network traffics and limit on processing capability, it is difficult to accurately locate hosts with large connection degree over high speed links on line. In this paper we present a new data streaming method for locating hosts with large connection degree based on the reversible connection degree sketch to monitor anomalous network traffics. The required memory space is small and constant, and more importantly the update/query complexity would not depend on the amount of data. The hash functions for data sketch are designed based on the remainder characteristics of the number theory so that in-degree/out-degree associated with a given host can be accurately estimated. Although the connection degree sketch does not preserve any host address information, we can analytically reconstruct the host addresses associated with large in-degree/out-degree by a simply equation purely based on the characteristics of the hash functions without using any host address information. This procedure is highly efficient since the computational time is constant and ignorable. Furthermore, this reversible connection degree sketch based method can be easily implemented in distributed systems. The experimental and testing results based on the actual network traffics show that the new method is truly accurate and efficient.

The randomness of the network behaviors poses serious challenges for discovering the abnormal patterns in network traffic flows. This paper presents a method based on blind source separation approach for detecting abnormal traffic flows. It decomposes the network traffic into two components: the routine pattern and the abnormal pattern. The scale-space filter with adaptive scale is applied to filter the noise without affecting the main behavior patterns which can be used to form the abnormal traffic metrics and profiles. The zero-crossing method is applied to extract the stochastic behavior pulse widths and the largest width is selected as the scale space factor. In this way, the influence of the inherent randomness could be removed or greatly reduced. The extracted patterns of the routine behaviors imply the user's habit and the abnormal patterns are useful for discovering anomalous behaviors such as scanning, flooding and content distribution attacks. A salient feature of the method is that no supervised learning process is needed. This is a very important advantage since obtaining labeled samples in traffic monitoring is extremely difficult. Experimental results based on the datasets of an actual network show that this method is effective for monitoring anomaly traffic flows in the gigabytes traffic environment and the identification accuracy is above 95%.