In this paper, given a user's query set and budget, we aim to use the limited budget to help users assemble a set of datasets that can enrich a base dataset by introducing the maximum number of distinct tuples (i.e., maximizing distinctiveness). We prove this problem to be NP-hard. A greedy algorithm using exact distinctiveness computation attains an approximation ratio of (1-e-1 )/2, but it lacks efficiency and scalability due to its frequent computation of the exact distinctiveness marginal gain of any candidate dataset for selection. This requires scanning through every tuple in candidate datasets and thus is unaffordable in practice. To overcome this limitation, we propose an efficient machine learning (ML)-based method for estimating the distinctiveness marginal gain of any candidate dataset. This effectively eliminates the need to test each tuple individually. Estimating the distinctiveness marginal gain of a dataset involves estimating the number of distinct tuples in the tuple sets returned by each query in a query set across multiple datasets. This can be viewed as the cardinality estimation for a query set on a set of datasets, and the proposed method is the first to tackle this cardinality estimation problem. This is a significant advancement over prior methods that were limited to single-query cardinality estimation on a single dataset and struggled with identifying overlaps among tuple sets returned by each query in a query set across multiple datasets. Extensive experiments using five real-world data pools demonstrate that our algorithm, which utilizes ML-based distinctiveness estimation, outperforms all relevant baselines in effectiveness, efficiency, and scalability. A case study on two downstream ML tasks also highlights its potential to find datasets with more useful tuples to enhance the performance of ML tasks.
论文检索
输入标题、作者或关键词，从 447 篇学术成果中精准定位
Constitutional AI (CAI) guides LLM behavior using constitutions, but identifying which principles are most effective for model alignment remains an open challenge. We introduce the C3AI framework (Crafting Constitutions for CAI models), which serves two key functions: (1) selecting and structuring principles to form effective constitutions before fine-tuning; and (2) evaluating whether fine-tuned CAI models follow these principles in practice. By analyzing principles from AI and psychology, we found that positively framed, behavior-based principles align more closely with human preferences than negatively framed or trait-based principles. In a safety alignment use case, we applied a graph-based principle selection method to refine an existing CAI constitution, improving safety measures while maintaining strong general reasoning capabilities. Interestingly, fine-tuned CAI models performed well on negatively framed principles but struggled with positively framed ones, in contrast to our human alignment results. This highlights a potential gap between principle design and model adherence. Overall, C3AI provides a structured and scalable approach to both crafting and evaluating CAI constitutions.
Content feeds provided by platforms such as X (formerly Twitter) and TikTok are consumed by users on a daily basis. In this paper, we revisit the native advertising problem in content feeds, initiated by Ieong et al. Given a sequence of organic items (e.g., videos or posts) relevant to a user's interests or to an information search, the goal is to place ads within the organic content so as to maximize a reward function (e.g., number of clicks), while accounting for two considerations: (1) an ad can only be inserted after a relevant content item; (2) the users' attention decays after consuming content or ads. These considerations provide a natural model for capturing both the advertisement effectiveness and the user experience. In this paper, we design fast and practical 2-approximation greedy algorithms for the associated optimization problem, improving over the best-known practical algorithm that only achieves an approximation factor of 4. Our algorithms exploit a counter-intuitive observation, namely, while top items are seemingly more important due to the decaying attention of the user, taking good care of the bottom items is key for obtaining improved approximation guarantees. We then provide the first comprehensive empirical evaluation on the problem, showing the strong empirical performance of our~methods.
Cross-Domain Sequential Recommendation (CDSR) has recently gained attention for countering data sparsity by transferring knowledge across domains. A common approach merges domain-specific sequences into cross-domain sequences, serving as bridges to connect domains. One key challenge is to correctly extract the shared knowledge among these sequences and appropriately transfer it. Most existing works directly transfer unfiltered cross-domain knowledge rather than extracting domain-invariant components and adaptively integrating them into domain-specific modelings. Another challenge lies in aligning the domain-specific and cross-domain sequences. Existing methods align these sequences based on timestamps, but this approach can cause prediction mismatches when the current tokens and their targets belong to different domains. In such cases, the domain-specific knowledge carried by the current tokens may degrade performance. To address these challenges, we propose the A-B-Cross-to-Invariant Learning Recommender (ABXI). Specifically, leveraging LoRA's effectiveness for efficient adaptation, ABXI incorporates two types of LoRAs to facilitate knowledge adaptation. First, all sequences are processed through a shared encoder that employs a domain LoRA for each sequence, thereby preserving unique domain characteristics. Next, we introduce an invariant projector that extracts domain-invariant interests from cross-domain representations, utilizing an invariant LoRA to adapt these interests into modeling each specific domain. Besides, to avoid prediction mismatches, all domain-specific sequences are aligned to match the domains of the cross-domain ground truths. Experimental results on three datasets demonstrate that our approach outperforms other CDSR counterparts by a large margin. The codes are available in https://github.com/DiMarzioBian/ABXI.
Beast in the Cage: A Fine-grained and Object-oriented Permission System to Confine JavaScript Operations on the Web
PDF ↗JavaScript plays a crucial role on web. However, the inclusion of unknown, vulnerable, and malicious scripts on websites and in browser extensions and the use of browsers' developer tools often lead to undesired web content manipulations and data acquisitions. To restrict JavaScript operations on web content and data, we introduce a fine-grained, mandatory access control-based, and object-oriented permission system to browsers. With our system, web developers can define policies for sensitive web elements on their web pages to allow or deny scripts' operations on web content and data within browsers. The system substantially thwarts many web threats and attacks, and offers benefits to personal data governance. We developed a tool for automatic policy generation and demonstrated the usability and compatibility of the system in a three-month study. Our system is a reasonable and practical solution, bolstering the security and trustworthiness on the internet.
Graph Neural Networks (GNNs) have achieved great success in dealing with non-Euclidean graph-structured data and have been widely deployed in many real-world applications. However, their effectiveness is often jeopardized under class-imbalanced training sets. Most existing studies have analyzed class-imbalanced node classification from a supervised learning perspective, they do not fully utilize the large number of unlabeled nodes in semi-supervised scenarios. We claim that the supervised signal is just the tip of the iceberg and a large number of unlabeled nodes have not yet been effectively utilized. In this work, we propose IceBerg, a debiased self-training framework to address the class-imbalanced and few-shot challenges for GNNs at the same time. Specifically, to figure out the Matthew effect and label distribution shift in self-training, we propose Double Balancing, which can largely improve the performance of existing baselines with just a few lines of code as a simple plug-and-play module. Secondly, to enhance the long-range propagation capability of GNNs, we disentangle the propagation and transformation operations of GNNs. Therefore, the weak supervision signals can propagate more effectively to address the few-shot issue. In summary, we find that leveraging unlabeled nodes can significantly enhance the performance of GNNs in class-imbalanced and few-shot scenarios, and even small, surgical modifications can lead to substantial performance improvements. Systematic experiments on benchmark datasets show that our method can deliver considerable performance gain over existing class-imbalanced node classification baselines. Additionally, due to IceBerg's outstanding ability to leverage unsupervised signals, it also achieves state-of-the-art results in few-shot node classification scenarios. The code of IceBerg is available at: https://github.com/ZhixunLEE/IceBerg.
AdvTG: An Adversarial Traffic Generation Framework to Deceive DL-Based Malicious Traffic Detection Models
PDF ↗Deep learning-based (DL-based) malicious traffic detection models are effective but vulnerable to adversarial attacks. Existing adversarial attacks have shown promising results when targeting traffic detection models based on statistics and sequence features. However, these attacks are less effective against models that rely on payload analysis. The main reason is the difficulty in generating semantic, compliant, and functional payloads, which limits their practical application. In this paper, we propose AdvTG, an adversarial traffic generation framework to deceive DL-based malicious traffic based on the large language model (LLM) and reinforcement learning (RL). Specifically, AdvTG is designed to attack various DL-based detection models across diverse payload features and architectures, thereby enhancing the generalization capabilities of the generated adversarial traffic. Moreover, we design a specialized prompt for traffic generation tasks, where functional fields and target types are supplied as input, while non-functional fields are generated to produce the mutated traffic. This fine-tuning endows the LLM with task comprehension and traffic pattern reasoning abilities, allowing it to generate traffic that remains compliant and functional. Furthermore, leveraging RL, AdvTG automatically selects traffic fields that exhibit more robust adversarial properties. Experimental results show that AdvTG achieves over 40% attack success rate (ASR) across six detection models on four base datasets and two extended datasets, significantly outperforming other adversarial attack methods.
Machine learning (ML) models are widely deployed on edge nodes, such as mobile phones and edge servers, to power a wide range of AI applications over the web. Ensuring the integrity of these edge models is paramount, as they are subject to corruption caused by software/hardware exceptions and malicious tampering, which may undermine model performance, incur economic losses, and pose health risks. Existing data integrity mechanisms designed for files stored on disks cannot properly verify the integrity of models running in GPUs or mitigate the new integrity threats against edge models. This paper proposes EdgeThemis, a novel mechanism for verifying the integrity of edge models through sentinel verification. To enable verifiability for a model M, EdgeThemis embeds a sentinel backdoor and a verification module into M. Then, a challenger can send verification requests to the edge node hosting M to verify its integrity. Next, the sentinel activates the verification module to generate a unique integrity proof tied to the identity of the edge node for verification. Finally, the challenger can verify the integrity proof to detect model corruption. Theoretical analysis proves that EdgeThemis can properly mitigate potential integrity threats against edge models. Experiments demonstrate that EdgeThemis achieves a verification accuracy of 100.00% across various models and different types of model corruption with robustness against replay attacks, theft attacks, and replacement attacks.
Graphs are widely used to model complex systems across various domains, including social networks and biological systems. A key task in graph analysis is identifying recurring structural patterns, known as graphlets, which capture connectivity among a fixed-size subset of nodes. While graphlets have been extensively applied in tasks such as measuring graph similarity and identifying communities, conventional graphlets focus only on direct connections between nodes. This limitation overlooks potential insights from more distant relationships within the graph structure. In this paper, we introduce (d,s)-graphlets, a generalization of size-s graphlets that incorporates indirect connections between nodes up to distance d. This new formulation provides a more fine-grained and comprehensive understanding of local graph structures. To efficiently count (d,s)-graphlets in a graph, we present EDGE, an exact counting algorithm that employs optimized combinatorial techniques to significantly reduce computational complexity compared to naive enumeration. Our empirical analysis across diverse real-world datasets demonstrates that (d,s)-graphlets provide superior graph characterization, outperforming conventional graphlets in a graph clustering task. Moreover, our case studies show that (d,s)-graphlets uncover non-trivial insights that would remain undiscovered when using conventional graphlets.
Semi-supervised Node Importance Estimation with Informative Distribution Modeling for Uncertainty Regularization
PDF ↗Node importance estimation, a classical problem in network analysis, underpins various web applications. Previous methods either exploit intrinsic topological characteristics, e.g., graph centrality, or leverage additional information, e.g., data heterogeneity, for node feature enhancement. However, these methods follow the supervised learning setting, overlooking the fact that ground-truth node-importance data are usually partially labeled in practice. In this work, we propose the first semi-supervised node importance estimation framework, i.e., EASING, to improve learning quality for unlabeled data in heterogeneous graphs. Different from previous approaches, EASING explicitly captures uncertainty to reflect the confidence of model predictions. To jointly estimate the importance values and uncertainties, EASING incorporates DJE, a deep encoder-decoder neural architecture. DJE introduces distribution modeling for graph nodes, where the distribution representations derive both importance and uncertainty estimates. Additionally, DJE facilitates effective pseudo-label generation for the unlabeled data to enrich the training samples. Based on labeled and pseudo-labeled data, EASING develops effective semi-supervised heteroscedastic learning with the varying node uncertainty regularization. Extensive experiments on three real-world datasets highlight the superior performance of EASING compared to competing methods. Codes are available via https://github.com/yankai-chen/EASING.
We consider the problem of bidding in online advertising, where an advertiser aims to maximize value while adhering to budget and Return-on-Spend (RoS) constraints. Unlike prior work that assumes knowledge of the value generated by winning each impression (e.g., conversions), we address the more realistic setting where the advertiser must simultaneously learn the optimal bidding strategy and the value of each impression opportunity. This introduces a challenging exploration-exploitation dilemma: the advertiser must balance exploring different bids to estimate impression values with exploiting current knowledge to bid effectively. To address this, we propose a novel Upper Confidence Bound (UCB)-style algorithm that carefully manages this trade-off. Via a rigorous theoretical analysis, we prove that our algorithm achieves Õ(₲T log(|B|T) ) regret and constraint violation, where T is the number of bidding rounds and B is the domain of possible bids. This establishes the first optimal regret and constraint violation bounds for bidding in the online setting with unknown impression values. Moreover, our algorithm is computationally efficient and simple to implement. We validate our theoretical findings through experiments on synthetic data, demonstrating that our algorithm exhibits strong empirical performance compared to existing approaches.
Standard multimodal self-supervised learning (SSL) algorithms regard cross-modal synchronization as implicit supervisory labels during pretraining, thus posing high requirements on the scale and quality of multimodal samples. These constraints significantly limit the performance of sensing intelligence in IoT applications, as the heterogeneity and the non-interpretability of time-series signals result in abundant unimodal data but scarce high-quality multimodal pairs. This paper proposes InfoMAE, a cross-modal alignment framework that tackles the challenge of multimodal pair efficiency under the SSL setting by facilitating efficient cross-modal alignment of pretrained unimodal representations. InfoMAE achieves efficient cross-modal alignment with limited data pairs through a novel information theory-inspired formulation that simultaneously addresses distribution-level and instance-level alignment. Extensive experiments on two real-world IoT applications are performed to evaluate InfoMAE's pairing efficiency to bridge pretrained unimodal models into a cohesive joint multimodal model. InfoMAE enhances downstream multimodal tasks by over 60% with significantly improved multimodal pairing efficiency. It also improves unimodal task accuracy by an average of 22%.
Graph neural networks (GNNs) exhibit powerful performance in handling graph data, with Euclidean and hyperbolic variants excelling in processing grid-based and hierarchical structures, respectively. However, existing methods focus on learning specific structures linked to the inherent properties of the underlying space, failing to fully exploit their complementary properties in distinct geometric spaces, thus limiting their ability to efficiently model complex graph structures. In this paper, we propose a Hyperbolic-Euclidean Deep Mutual Learning (H-EDML) framework, which leverages the unique properties of hyperbolic space to effectively capture the hierarchical relationships present in graph data, while also utilizes the familiar Euclidean space to handle local interactions. Specifically, We design a topology mutual learning module to bolster the capacity of each single model to perceive the holistic topological structure of the graph. Then, we integrate a decision mutual learning module to further advance the models' comprehensive judgment capabilities towards graph data, thereby strengthening the robustness and generalization. Furthermore, we employ an attention-based probabilistic integration strategy for the final prediction to alleviate potential disparities in decision-making among different models. Extensive experiments on node classification are conducted on five real-world graph datasets and the results show that our proposed H-EDML achieves competitive performances compared to the state-of-the-art methods. The source code will be available at: https://github.com/caohaifang123/H-EDML.
With the increasing prevalence of Web-based platforms handling vast amounts of user data, machine unlearning has emerged as a crucial mechanism to uphold users' right to be forgotten, enabling individuals to request the removal of their specified data from trained models. However, the auditing of machine unlearning processes remains significantly underexplored. Although some existing methods offer unlearning auditing by leveraging backdoors, these backdoor-based approaches are inefficient and impractical, as they necessitate involvement in the initial model training process to embed the backdoors. In this paper, we propose a TAilored Posterior diffErence (TAPE) method to provide unlearning auditing independently of original model training. We observe that the process of machine unlearning inherently introduces changes in the model, which contains information related to the erased data. TAPE leverages unlearning model differences to assess how much information has been removed through the unlearning operation. Firstly, TAPE mimics the unlearned posterior differences by quickly building unlearned shadow models based on first-order influence estimation. Secondly, we train a Reconstructor model to extract and evaluate the private information of the unlearned posterior differences to audit unlearning. Existing privacy reconstructing methods based on posterior differences are only feasible for model updates of a single sample. To enable the reconstruction effective for multi-sample unlearning requests, we propose two strategies, unlearned data perturbation and unlearned influence-based division, to augment the posterior difference. Extensive experimental results indicate the significant superiority of TAPE over the state-of-the-art unlearning verification methods, at least 4.5x efficiency speedup and supporting the auditing for broader unlearning scenarios.
Recommender systems relying on contextual multi-armed bandits continuously improve relevant item recommendations by taking into account the contextual information. The objective of bandit algorithms is to learn the best arm (e.g., best item to recommend) for each user and thus maximize the cumulative rewards from user engagement with the recommendations. The context that these algorithms typically consider are the user and item attributes. However, in the context of social networks where the action of one user can influence the actions and rewards of other users, neighbors' actions are also a very important context, as they can have not only predictive power but also can impact future rewards through spillover. Moreover, influence susceptibility can vary for different people based on their preferences and the closeness of ties to other users which leads to heterogeneity in the spillover effects. Here, we present a framework that allows contextual multi-armed bandits to account for such heterogeneous spillovers when choosing the best arm for each user. Our experiments on several semi-synthetic and real-world datasets show that our framework leads to significantly higher rewards than existing state-of-the-art solutions that ignore the network information and potential spillover.
Recommender Systems (RS) aim to generate personalized ranked lists for each user and are evaluated using ranking metrics. Although personalized ranking is a fundamental aspect of RS, this critical property is often overlooked in the design of model architectures. To address this issue, we propose Rankformer, a ranking-inspired recommendation model. The architecture of Rankformer is inspired by the gradient of the ranking objective, embodying a unique (graph) transformer architecture --- it leverages global information from all users and items to produce more informative representations and employs specific attention weights to guide the evolution of embeddings towards improved ranking performance. We further develop an acceleration algorithm for Rankformer, reducing its complexity to a linear level with respect to the number of positive instances. Extensive experimental results demonstrate that Rankformer outperforms state-of-the-art methods. The code is available at https://github.com/StupidThree/Rankformer.
An important problem on social information sites is the recovery of ground truth from individual reports when the experts are in the minority. The wisdom of the crowd, i.e. the collective opinion of a group of individuals fails in such a scenario. However, the surprisingly popular (SP) algorithm[15] can recover the ground truth even when the experts are in the minority, by asking the individuals to report additional prediction reports--their beliefs about the reports of others. Several recent works have extended the surprisingly popular algorithm to an equivalent voting rule (SP-voting) to recover the ground truth ranking over a set of m alternatives. However, we are yet to fully understand when SP-voting can recover the ground truth ranking, and if so, how many samples (votes and predictions) it needs. We answer this question by proposing two rank-order models and analyzing the sample complexity of SP-voting under these models. In particular, we propose concentric mixtures of Mallows and Plackett-Luce models with G (≥ 2) groups. Our models generalize previously proposed concentric mixtures of Mallows models with 2 groups, and we highlight the importance of G > 2 groups by identifying three distinct groups (expert, intermediate, and non-expert) from existing datasets. Next, we provide conditions on the parameters of the underlying models so that SP-voting can recover ground-truth rankings with high probability, and also derive sample complexities under the same. We complement the theoretical results by evaluating SP-voting on simulated and real datasets.
SAHSD: Enhancing Hate Speech Detection in LLM-Powered Web Applications via Sentiment Analysis and Few-Shot Learning
PDF ↗As large language models (LLMs) increasingly power web applications, including social networks, the challenge of moderating hate speech has become a critical concern for the Web. These LLM-powered applications, while offering near-human interaction capabilities, are vulnerable to harmful or biased content due to imperfect training data scraped from the Web. Current hate speech detection methods often struggle with limited annotated data, especially for real-time moderation on these platforms. This paper introduces Sentiment-Aided Hate Speech Detection (SAHSD), a novel approach designed to enhance hate speech detection specifically in LLM-powered web applications. By treating hate speech detection as a few-shot learning task, SAHSD utilizes sentiment analysis to refine pre-trained language models (LM) for improved accuracy in recognizing harmful content. SAHSD first employs publicly available sentiment datasets to train a sentiment analysis model, which is then fine-tuned by merging sentiment prompts with hate speech prompts, enabling efficient and accurate detection even with limited training samples. The effectiveness of SAHSD is demonstrated through experiments on widely used web-sourced datasets like SBIC and HateXplain. SAHSD achieves an exceptional F1-score of 0.99 with only 64 training samples and outperforms advanced techniques such as ToKen, MRP, and HARE, with significant improvements of 33% on SBIC and 95% on HateXplain. SAHSD surpasses GPT-4 in generalization performance across multiple datasets, showing an 8% improvement when trained on equal-sized samples. These results underscore SAHSD's potential to enhance content moderation in LLM-driven web platforms, contributing to a safer, more inclusive and accountable Web ecosystem.
Beyond Visual Confusion: Understanding How Inconsistencies in ENS Normalization Facilitate Homoglyph Attacks
PDF ↗In recent years, the Ethereum Name Service (ENS) has garnered significant attention within the community for enabling the use of Unicode in domain names, thereby facilitating the inclusion of a wide array of character sets such as Greek, Cyrillic, Arabic, and Chinese. While this feature enhances the versatility and global accessibility of domain names, it concurrently introduces a substantial security vulnerability due to the presence of homoglyphs-characters that are visually similar to others across Unicode and ASCII sets. These similarities can be exploited in homoglyph attacks, posing a distinct threat to domain name integrity. Despite community efforts to counteract this issue through a normalization process prior to domain resolution, our analysis uncovers significant discrepancies in how the normalization processes are applied across various applications. This inconsistency could result in the same domain name being resolved to different addresses in different applications, underscoring a critical vulnerability. We also discovered the new attack scenario in ENS which may cause legitimate domains resolved into malicious addresses even when they are verified by authorities. To systematically evaluate this inconsistency, we designed a tool for detecting application-level discrepancies in domain normalization process without requiring access to the application's source code. Our evaluation on hundreds of real-world Web3 applications identifies widespread deviations from established homoglyph mitigation practices, with more than 60% digital wallets and 80% dApps (decentralized applications) not able to produce consistent ENS resolving results, potentially impacting millions of users. This analysis underscores the urgent need for a standardized implementation of normalization processes to safeguard the integrity and security of ENS domains.
Contemporary datasets sourced from the web often adopt a multi-view format, collecting data from diverse sources, domains, or modules. Existing methodologies employed to analyze such datasets frequently overlook or inaccurately allocate the view-weights, pivotal metrics reflecting each view's significance. This work introduces EVA-MVC, a simple yet effective algorithm designed for Equitable View-weight Allocation (EVA) seamlessly integrated with arbitrary Multi-view Clustering (MVC) methods. Within the EVA module, we establish theoretical connections between view supplementarity and Multi-view Subspace Learning (MSL), leading to the partition of views into View Communities (VCs) based on these foundational principles. These VCs exhibit internal supplementarity similarities, facilitating Equitable View-weights Allocation through VC-specific MSL. The proposed EVA process precedes and operates independently of traditional or SOTA MVC approaches, requiring no additional processing or specialized design, making it an ideal preprocessing step for MVC applications. Through comprehensive evaluations across diverse multi-view datasets, our findings reveal that our EVA significantly enhances the effectiveness of mainstream MVC frameworks, resulting in a notable performance improvement.