OpenRaiser/Intern-Atlas huggingface dataset:
Evaluating Google's Protected Audience Protocol
Venue: arXiv cs.CR 2024
Year: 2024

While third-party cookies have been a key component of the digital marketing ecosystem for years, they allow users to be tracked across web sites in ways that raise serious privacy concerns. Google has proposed the Privacy Sandbox initiative to enable ad targeting without third-party cookies. While there have been several studies focused on other aspects of this initiative, there has been little analysis to date as to how well the system achieves the intended goal of preventing request linking. This work focuses on analyzing linkage privacy risks for the reporting mechanisms proposed in the Protected Audience (PrAu) proposal (previously known as FLEDGE), which is intended to enable online remarketing without using third-party cookies. We summarize the overall workflow of PrAu and highlight potential privacy risks associated with its proposed design, focusing on scenarios in which adversaries attempt to link requests to different sites to the same user. We show how a realistic adversary would be still able to use the privacy-protected reporting mechanisms to link user requests and conduct mass surveillance, even with correct implementations of all the currently proposed privacy mechanisms.
Discursive objection strategies in online comments: Developing a classification schema and validating its training
Venue: arXiv cs.CL 2024
Year: 2024

Most Americans agree that misinformation, hate speech and harassment are harmful and inadequately curbed on social media through current moderation practices. In this paper, we aim to understand the discursive strategies employed by people in response to harmful speech in news comments. We conducted a content analysis of more than 6500 comment replies to trending news videos on YouTube and Twitter and identified seven distinct discursive objection strategies (Study 1). We examined the frequency of each strategy's occurrence from the 6500 comment replies, as well as from a second sample of 2004 replies (Study 2). Together, these studies show that people deploy a diversity of discursive strategies when objecting to speech, and reputational attacks are the most common. The resulting classification scheme accounts for different theoretical approaches for expressing objections and offers a comprehensive perspective on grassroots efforts aimed at stopping offensive or problematic speech on campus.
cVIL: Class-Centric Visual Interactive Labeling
Venue: arXiv cs.HC 2024
Year: 2024

We present cVIL, a class-centric approach to visual interactive labeling, which facilitates human annotation of large and complex image data sets. cVIL uses different property measures to support instance labeling for labeling difficult instances and batch labeling to quickly label easy instances. Simulated experiments reveal that cVIL with batch labeling can outperform traditional labeling approaches based on active learning. In a user study, cVIL led to better accuracy and higher user preference compared to a traditional instance-based visual interactive labeling approach based on 2D scatterplots.
Beyond Theorems: A Counterexample to Potential Markov Game Criteria
Venue: arXiv cs.GT 2024
Year: 2024

There are only limited classes of multi-player stochastic games in which independent learning is guaranteed to converge to a Nash equilibrium. Markov potential games are a key example of such classes. Prior work has outlined sets of sufficient conditions for a stochastic game to qualify as a Markov potential game. However, these conditions often impose strict limitations on the game's structure and tend to be challenging to verify. To address these limitations, Mguni et al. [12] introduce a relaxed notion of Markov potential games and offer an alternative set of necessary conditions for categorizing stochastic games as potential games. Under these conditions, the authors claim that a deterministic Nash equilibrium can be computed efficiently by solving a dual Markov decision process. In this paper, we offer evidence refuting this claim by presenting a counterexample.
Multi-Agent Combinatorial Contracts
Venue: arXiv cs.GT 2024
Year: 2024

Combinatorial contracts are emerging as a key paradigm in algorithmic contract design, paralleling the role of combinatorial auctions in algorithmic mechanism design. In this paper we study natural combinatorial contract settings involving teams of agents, each capable of performing multiple actions. This scenario extends two fundamental special cases previously examined in the literature, namely the single-agent combinatorial action model of [Duetting et al., 2021] and the multi-agent binary-action model of [Babaioff et al., 2012, Duetting et al., 2023]. We study the algorithmic and computational aspects of these settings, highlighting the unique challenges posed by the absence of certain monotonicity properties essential for analyzing the previous special cases. To navigate these complexities, we introduce a broad set of novel tools that deepen our understanding of combinatorial contracts environments and yield good approximation guarantees. Our main result is a constant-factor approximation for submodular multi-agent multi-action problems with value and demand oracles access. This result is tight: we show that this problem admits no PTAS (even under binary actions). As a side product of our main result, we devise an FPTAS, with value and demand oracles, for single-agent combinatorial action scenarios with general reward functions, which is of independent interest. We also provide bounds on the gap between the optimal welfare and the principal's utility. We show that, for subadditive rewards, perhaps surprisingly, this gap scales only logarithmically (rather than linearly) in the size of the action space.
Facilitating Feature and Topology Lightweighting: An Ethereum Transaction Graph Compression Method for Malicious Account Detection
Venue: arXiv cs.CR 2024
Year: 2024

Ethereum has become one of the primary global platforms for cryptocurrency, playing an important role in promoting the diversification of the financial ecosystem. However, the relative lag in regulation has led to a proliferation of malicious activities in Ethereum, posing a serious threat to fund security. Existing regulatory methods usually detect malicious accounts through feature engineering or large-scale transaction graph mining. However, due to the immense scale of transaction data and malicious attacks, these methods suffer from inefficiency and low robustness during data processing and anomaly detection. In this regard, we propose an Ethereum Transaction Graph Compression method named TGC4Eth, which assists malicious account detection by lightweighting both features and topology of the transaction graph. At the feature level, we select transaction features based on their low importance to improve the robustness of the subsequent detection models against feature evasion attacks; at the topology level, we employ focusing and coarsening processes to compress the structure of the transaction graph, thereby improving both data processing and inference efficiency of detection models. Extensive experiments demonstrate that TGC4Eth significantly improves the computational efficiency of existing detection models while preserving the connectivity of the transaction graph. Furthermore, TGC4Eth enables existing detection models to maintain stable performance and exhibit high robustness against feature evasion attacks.
Cross-Category Functional Grasp Transfer
Venue: arXiv cs.RO 2024
Year: 2024

Generating grasps for a dexterous hand often requires numerous grasping annotations. However, annotating high DoF dexterous hand poses is quite challenging. Especially for functional grasps, requiring the hand to grasp the object in a specific pose to facilitate subsequent manipulations. This prompts us to explore how people achieve manipulations on new objects based on past grasp experiences. We find that when grasping new items, people are adept at discovering and leveraging various similarities between objects, including shape, layout, and grasp type. Considering this, we analyze and collect grasp-related similarity relationships among 51 common tool-like object categories and annotate semantic grasp representation for 1768 objects. These objects are connected through similarities to form a knowledge graph, which helps infer our proposed cross-category functional grasp synthesis. Through extensive experiments, we demonstrate that the grasp-related knowledge indeed contributed to achieving functional grasp transfer across unknown or entirely new categories of objects.
A Decoupling and Aggregating Framework for Joint Extraction of Entities and Relations
Venue: arXiv cs.CL 2024
Year: 2024

Named Entity Recognition and Relation Extraction are two crucial and challenging subtasks in the field of Information Extraction. Despite the successes achieved by the traditional approaches, fundamental research questions remain open. First, most recent studies use parameter sharing for a single subtask or shared features for both two subtasks, ignoring their semantic differences. Second, information interaction mainly focuses on the two subtasks, leaving the fine-grained informtion interaction among the subtask-specific features of encoding subjects, relations, and objects unexplored. Motivated by the aforementioned limitations, we propose a novel model to jointly extract entities and relations. The main novelties are as follows: (1) We propose to decouple the feature encoding process into three parts, namely encoding subjects, encoding objects, and encoding relations. Thanks to this, we are able to use fine-grained subtask-specific features. (2) We propose novel inter-aggregation and intra-aggregation strategies to enhance the information interaction and construct individual fine-grained subtask-specific features, respectively. The experimental results demonstrate that our model outperforms several previous state-of-the-art models. Extensive additional experiments further confirm the effectiveness of our model.
Establishing Heuristics for Improving the Usability of GUI Machine Learning Tools for Novice Users
Venue: arXiv cs.HC 2024
Year: 2024

Machine learning (ML) tools with graphical user interfaces (GUI) are facing demand from novice users who do not have the background of their underlying concepts. These tools are frequently complex and pose unique challenges in terms of interaction and comprehension by novice users. There is yet to be an established set of usability heuristics to guide and assess GUI ML tool design. To address this gap, in this paper, we extend Nielsen's heuristics for evaluating GUI ML Tools through a set of empirical evaluations. To validate the proposed heuristics, user testing was conducted by novice users on a prototype that reflects those heuristics. Based on the results of the evaluations, our new heuristics set improves upon existing heuristics in the context of ML tools. It can serve as a resource for practitioners designing and evaluating these tools.
No-Regret Learning of Nash Equilibrium for Black-Box Games via Gaussian Processes
Venue: arXiv cs.LG 2024
Year: 2024

This paper investigates the challenge of learning in black-box games, where the underlying utility function is unknown to any of the agents. While there is an extensive body of literature on the theoretical analysis of algorithms for computing the Nash equilibrium with complete information about the game, studies on Nash equilibrium in black-box games are less common. In this paper, we focus on learning the Nash equilibrium when the only available information about an agent's payoff comes in the form of empirical queries. We provide a no-regret learning algorithm that utilizes Gaussian processes to identify the equilibrium in such games. Our approach not only ensures a theoretical convergence rate but also demonstrates effectiveness across a variety collection of games through experimental validation.
Foundational Verification of Smart Contracts through Verified Compilation
Venue: arXiv cs.PL 2024
Year: 2024

Programs executed on a blockchain - smart contracts - have high financial stakes; their correctness is crucial. We argue, that this correctness needs to be foundational: correctness needs to be based on the operational semantics of their execution environment. In this work we present a foundational system - the DeepSEA system - targeting the Ethereum blockchain as the largest smart contract platform. The DeepSEA system has a small but sufficiently rich programming language amenable for verification, the DeepSEA language, and a verified DeepSEA compiler. Together they enable true end-to-end verification for smart contracts. We demonstrate usability through two case studies: a realistic contract for Decentralized Finance and contract for crowdfunding.
Reasoning about Interior Mutability in Rust using Library-Defined Capabilities
Venue: arXiv cs.PL 2024
Year: 2024

Existing automated verification techniques for safe Rust code rely on the strong type-system properties to reason about programs, especially to deduce which memory locations do not change (i.e., are framed) across function calls. However, these type guarantees do not hold in the presence of interior mutability (e.g., when interacting with any concurrent data structure). As a consequence, existing verification techniques for safe code such as Prusti and Creusot are either unsound or fundamentally incomplete if applied to this setting. In this work, we present the first technique capable of automatically verifying safe clients of existing interiorly mutable types. At the core of our approach, we identify a novel notion of implicit capabilities: library-defined properties that cannot be expressed using Rust's types. We propose new annotations to specify these capabilities and a first-order logic encoding suitable for program verification. We have implemented our technique in a verifier called Mendel and used it to prove absence of panics in Rust programs that make use of popular standard-library types with interior mutability, including Rc, Arc, Cell, RefCell, AtomicI32, Mutex and RwLock. Our evaluation shows that these library annotations are useful for verifying usages of real-world libraries, and powerful enough to require zero client-side annotations in many of the verified programs.
CIER: A Novel Experience Replay Approach with Causal Inference in Deep Reinforcement Learning
Venue: arXiv cs.LG 2024
Year: 2024

In the training process of Deep Reinforcement Learning (DRL), agents require repetitive interactions with the environment. With an increase in training volume and model complexity, it is still a challenging problem to enhance data utilization and explainability of DRL training. This paper addresses these challenges by focusing on the temporal correlations within the time dimension of time series. We propose a novel approach to segment multivariate time series into meaningful subsequences and represent the time series based on these subsequences. Furthermore, the subsequences are employed for causal inference to identify fundamental causal factors that significantly impact training outcomes. We design a module to provide feedback on the causality during DRL training. Several experiments demonstrate the feasibility of our approach in common environments, confirming its ability to enhance the effectiveness of DRL training and impart a certain level of explainability to the training process. Additionally, we extended our approach with priority experience replay algorithm, and experimental results demonstrate the continued effectiveness of our approach.
Coupled-Band ESSFM for Low-Complexity DBP
Venue: arXiv cs.IT 2024
Year: 2024

We propose a novel digital backpropagation (DBP) technique that combines perturbation theory, subband processing, and splitting ratio optimization. We obtain 0.23 dB, 0.47 dB, or 0.91 dB gains w.r.t. dispersion compensation with only 74, 161, or 681 real multiplications/2D-symbol, improving significantly on existing DBP techniques.
Towards a Hybrid Digital Twin: Physics-Informed Neural Networks as Surrogate Model of a Reinforced Concrete Beam
Venue: arXiv cs.CE 2024
Year: 2024

In this study, we investigate the potential of fast-to-evaluate surrogate modeling techniques for developing a hybrid digital twin of a steel-reinforced concrete beam, serving as a representative example of a civil engineering structure. As surrogates, two distinct models are developed utilizing physics-informed neural networks, which integrate experimental data with given governing laws of physics. The experimental data (sensor data) is obtained from a previously conducted four-point bending test. The first surrogate model predicts strains at fixed locations along the center line of the beam for various time instances. This time-dependent surrogate model is inspired by the motion of a harmonic oscillator. For this study, we further compare the physics-based approach with a purely data-driven method, revealing the significance of physical laws for the extrapolation capabilities of models in scenarios with limited access to experimental data. Furthermore, we identify the natural frequency of the system by utilizing the physics-based model as an inverse solver. For the second surrogate model, we then focus on a fixed instance in time and combine the sensor data with the equations of linear elasticity to predict the strain distribution within the beam. This example reveals the importance of balancing different loss components through the selection of suitable loss weights.
TEDNet: Twin Encoder Decoder Neural Network for 2D Camera and LiDAR Road Detection
Venue: arXiv cs.CV 2024
Year: 2024

Robust road surface estimation is required for autonomous ground vehicles to navigate safely. Despite it becoming one of the main targets for autonomous mobility researchers in recent years, it is still an open problem in which cameras and LiDAR sensors have demonstrated to be adequate to predict the position, size and shape of the road a vehicle is driving on in different environments. In this work, a novel Convolutional Neural Network model is proposed for the accurate estimation of the roadway surface. Furthermore, an ablation study has been conducted to investigate how different encoding strategies affect model performance, testing 6 slightly different neural network architectures. Our model is based on the use of a Twin Encoder-Decoder Neural Network (TEDNet) for independent camera and LiDAR feature extraction, and has been trained and evaluated on the Kitti-Road dataset. Bird's Eye View projections of the camera and LiDAR data are used in this model to perform semantic segmentation on whether each pixel belongs to the road surface. The proposed method performs among other state-of-the-art methods and operates at the same frame-rate as the LiDAR and cameras, so it is adequate for its use in real-time applications.
How to Surprisingly Consider Recommendations? A Knowledge-Graph-based Approach Relying on Complex Network Metrics
Venue: arXiv cs.IR 2024
Year: 2024

Traditional recommendation proposals, including content-based and collaborative filtering, usually focus on similarity between items or users. Existing approaches lack ways of introducing unexpectedness into recommendations, prioritizing globally popular items over exposing users to unforeseen items. This investigation aims to design and evaluate a novel layer on top of recommender systems suited to incorporate relational information and suggest items with a user-defined degree of surprise. We propose a Knowledge Graph (KG) based recommender system by encoding user interactions on item catalogs. Our study explores whether network-level metrics on KGs can influence the degree of surprise in recommendations. We hypothesize that surprisingness correlates with certain network metrics, treating user profiles as subgraphs within a larger catalog KG. The achieved solution reranks recommendations based on their impact on structural graph metrics. Our research contributes to optimizing recommendations to reflect the metrics. We experimentally evaluate our approach on two datasets of LastFM listening histories and synthetic Netflix viewing profiles. We find that reranking items based on complex network metrics leads to a more unexpected and surprising composition of recommendation lists.
Sparse MTTKRP Acceleration for Tensor Decomposition on GPU
Venue: arXiv cs.DC 2024
Year: 2024

Sparse Matricized Tensor Times Khatri-Rao Product (spMTTKRP) is the bottleneck kernel of sparse tensor decomposition. In this work, we propose a GPU-based algorithm design to address the key challenges in accelerating spMTTKRP computation, including (1) eliminating global atomic operations across GPU thread blocks, (2) avoiding the intermediate values being communicated between GPU thread blocks and GPU global memory, and (3) ensuring a balanced distribution of workloads across GPU thread blocks. Our approach also supports dynamic tensor remapping, enabling the above optimizations in all the modes of the input tensor. Our approach achieves a geometric mean speedup of 1.5x, 2.0x, and 21.7x in total execution time across widely used datasets compared with the state-of-the-art GPU implementations. Our work is the only GPU implementation that can support tensors with modes greater than 4 since the state-of-the-art works have implementation constraints for tensors with a large number of modes.
Rethinking Scanning Strategies with Vision Mamba in Semantic Segmentation of Remote Sensing Imagery: An Experimental Study
Venue: arXiv cs.CV 2024
Year: 2024

Deep learning methods, especially Convolutional Neural Networks (CNN) and Vision Transformer (ViT), are frequently employed to perform semantic segmentation of high-resolution remotely sensed images. However, CNNs are constrained by their restricted receptive fields, while ViTs face challenges due to their quadratic complexity. Recently, the Mamba model, featuring linear complexity and a global receptive field, has gained extensive attention for vision tasks. In such tasks, images need to be serialized to form sequences compatible with the Mamba model. Numerous research efforts have explored scanning strategies to serialize images, aiming to enhance the Mamba model's understanding of images. However, the effectiveness of these scanning strategies remains uncertain. In this research, we conduct a comprehensive experimental investigation on the impact of mainstream scanning directions and their combinations on semantic segmentation of remotely sensed images. Through extensive experiments on the LoveDA, ISPRS Potsdam, and ISPRS Vaihingen datasets, we demonstrate that no single scanning strategy outperforms others, regardless of their complexity or the number of scanning directions involved. A simple, single scanning direction is deemed sufficient for semantic segmentation of high-resolution remotely sensed images. Relevant directions for future research are also recommended.