OpenRaiser/Intern-Atlas huggingface dataset:
Projective Ranking-based GNN Evasion Attacks
Venue: arXiv cs.LG 2023
Year: 2023

Graph neural networks (GNNs) offer promising learning methods for graph-related tasks. However, GNNs are at risk of adversarial attacks. Two primary limitations of the current evasion attack methods are highlighted: (1) The current GradArgmax ignores the "long-term" benefit of the perturbation. It is faced with zero-gradient and invalid benefit estimates in certain situations. (2) In the reinforcement learning-based attack methods, the learned attack strategies might not be transferable when the attack budget changes. To this end, we first formulate the perturbation space and propose an evaluation framework and the projective ranking method. We aim to learn a powerful attack strategy then adapt it as little as possible to generate adversarial samples under dynamic budget settings. In our method, based on mutual information, we rank and assess the attack benefits of each perturbation for an effective attack strategy. By projecting the strategy, our method dramatically minimizes the cost of learning a new attack strategy when the attack budget changes. In the comparative assessment with GradArgmax and RL-S2V, the results show our method owns high attack performance and effective transferability. The visualization of our method also reveals various attack patterns in the generation of adversarial samples.
Automation of reversible steganographic coding with nonlinear discrete optimisation
Venue: arXiv cs.CV 2023
Year: 2023

Authentication mechanisms are at the forefront of defending the world from various types of cybercrime. Steganography can serve as an authentication solution through the use of a digital signature embedded in a carrier object to ensure the integrity of the object and simultaneously lighten the burden of metadata management. Nevertheless, despite being generally imperceptible to human sensory systems, any degree of steganographic distortion might be inadmissible in fidelity-sensitive situations such as forensic science, legal proceedings, medical diagnosis and military reconnaissance. This has led to the development of reversible steganography. A fundamental element of reversible steganography is predictive analytics, for which powerful neural network models have been effectively deployed. Another core element is reversible steganographic coding. Contemporary coding is based primarily on heuristics, which offers a shortcut towards sufficient, but not necessarily optimal, capacity--distortion performance. While attempts have been made to realise automatic coding with neural networks, perfect reversibility is unattainable via such learning machinery. Instead of relying on heuristics and machine learning, we aim to derive optimal coding by means of mathematical optimisation. In this study, we formulate reversible steganographic coding as a nonlinear discrete optimisation problem with a logarithmic capacity constraint and a quadratic distortion objective. Linearisation techniques are developed to enable iterative mixed-integer linear programming. Experimental results validate the near-optimality of the proposed optimisation algorithm when benchmarked against a brute-force method.
Adversarial robustness of sparse local Lipschitz predictors
Venue: arXiv cs.LG 2023
Year: 2023

This work studies the adversarial robustness of parametric functions composed of a linear predictor and a non-linear representation map. % that satisfies certain stability condition. Our analysis relies on \emph{sparse local Lipschitzness} (SLL), an extension of local Lipschitz continuity that better captures the stability and reduced effective dimensionality of predictors upon local perturbations. SLL functions preserve a certain degree of structure, given by the sparsity pattern in the representation map, and include several popular hypothesis classes, such as piece-wise linear models, Lasso and its variants, and deep feed-forward \relu networks. % are sparse local Lipschitz. We provide a tighter robustness certificate on the minimal energy of an adversarial example, as well as tighter data-dependent non-uniform bounds on the robust generalization error of these predictors. We instantiate these results for the case of deep neural networks and provide numerical evidence that supports our results, shedding new insights into natural regularization strategies to increase the robustness of these models.
New efficient algorithms for computing Gröbner bases of saturation ideals (F4SAT) and colon ideals (Sparse-FGLM-colon)
Venue: arXiv cs.SC 2023
Year: 2023

This paper is concerned with linear algebra based methods for solving exactly polynomial systems through so-called Gröbner bases, which allow one to compute modulo the polynomial ideal generated by the input equations. This is a topical issue in non-linear algebra and more broadly in computational mathematics because of its numerous applications in engineering and computing sciences. Such applications often require geometric computing features such as representing the closure of the set difference of two solution sets to given polynomial systems. Algebraically, this boils down to computing Gröbner bases of colon and/or saturation polynomial ideals. In this paper, we describe and analyze new Gröbner bases algorithms for this task and present implementations which are more efficient by several orders of magnitude than the state-of-the-art software.
Robust Multi-Agent Bandits Over Undirected Graphs
Venue: arXiv cs.LG 2023
Year: 2023

We consider a multi-agent multi-armed bandit setting in which $n$ honest agents collaborate over a network to minimize regret but $m$ malicious agents can disrupt learning arbitrarily. Assuming the network is the complete graph, existing algorithms incur $O( (m + K/n) \log (T) / Δ)$ regret in this setting, where $K$ is the number of arms and $Δ$ is the arm gap. For $m \ll K$, this improves over the single-agent baseline regret of $O(K\log(T)/Δ)$. In this work, we show the situation is murkier beyond the case of a complete graph. In particular, we prove that if the state-of-the-art algorithm is used on the undirected line graph, honest agents can suffer (nearly) linear regret until time is doubly exponential in $K$ and $n$. In light of this negative result, we propose a new algorithm for which the $i$-th agent has regret $O( ( d_{\text{mal}}(i) + K/n) \log(T)/Δ)$ on any connected and undirected graph, where $d_{\text{mal}}(i)$ is the number of $i$'s neighbors who are malicious. Thus, we generalize existing regret bounds beyond the complete graph (where $d_{\text{mal}}(i) = m$), and show the effect of malicious agents is entirely local (in the sense that only the $d_{\text{mal}}(i)$ malicious agents directly connected to $i$ affect its long-term regret).
Towards Effective Resource Procurement in MEC: a Resource Re-selling Framework
Venue: arXiv cs.NI 2023
Year: 2023

On-demand and resource reservation pricing models have been widely used in cloud computing, catering to different user requirements. Nevertheless, in Multi-Access Edge Computing (MEC), as the edge has limited resources compared to the cloud, on-demand users may not get their jobs served on time, or at all, if too many resources were reserved by reservation plan users. Concurrently, reservation plan users may possess excess un-utilized quota. To optimize this resource mismatch scenario, we propose a Sharing Quota Model (SQM) where reservation plan users can re-sell unused resource quota to on-demand users, with the mobile network operator (MNO) taking a commission. To analyze the user's aggregate behavior at equilibrium and investigate the MNO's incentive of allowing re-selling, we formulate a 3-stage non-cooperative Stackelberg Game. Solving this game, we characterize the optimal strategies of buyers and re-sellers. We show that on aggregate, users' optimal strategies give rise to 4 disjoint regions, dependent on the MNO's prices and supply levels. Based on this, we characterise the MNO's optimal prices for on-demand users. Numerical results show that having both the sharing and on-demand pool gives the MNO an optimal revenue when the on-demand pool's supply is low, and when the MNO's commission is low.
Continual SLAM: Beyond Lifelong Simultaneous Localization and Mapping Through Continual Learning
Venue: arXiv cs.RO 2023
Year: 2023

Robots operating in the open world encounter various different environments that can substantially differ from each other. This domain gap also poses a challenge for Simultaneous Localization and Mapping (SLAM) being one of the fundamental tasks for navigation. In particular, learning-based SLAM methods are known to generalize poorly to unseen environments hindering their general adoption. In this work, we introduce the novel task of continual SLAM extending the concept of lifelong SLAM from a single dynamically changing environment to sequential deployments in several drastically differing environments. To address this task, we propose CL-SLAM leveraging a dual-network architecture to both adapt to new environments and retain knowledge with respect to previously visited environments. We compare CL-SLAM to learning-based as well as classical SLAM methods and show the advantages of leveraging online data. We extensively evaluate CL-SLAM on three different datasets and demonstrate that it outperforms several baselines inspired by existing continual learning-based visual odometry methods. We make the code of our work publicly available at http://continual-slam.cs.uni-freiburg.de.
Pushdown Automata and Context-Free Grammars in Bisimulation Semantics
Venue: arXiv cs.LO 2023
Year: 2023

The Turing machine models an old-fashioned computer, that does not interact with the user or with other computers, and only does batch processing. Therefore, we came up with a Reactive Turing Machine that does not have these shortcomings. In the Reactive Turing Machine, transitions have labels to give a notion of interactivity. In the resulting process graph, we use bisimilarity instead of language equivalence. Subsequently, we considered other classical theorems and notions from automata theory and formal languages theory. In this paper, we consider the classical theorem of the correspondence between pushdown automata and context-free grammars. By changing the process operator of sequential composition to a sequencing operator with intermediate acceptance, we get a better correspondence in our setting. We find that the missing ingredient to recover the full correspondence is the addition of a notion of state awareness.
Query Processing on Tensor Computation Runtimes
Venue: arXiv cs.DB 2023
Year: 2023

The huge demand for computation in artificial intelligence (AI) is driving unparalleled investments in hardware and software systems for AI. This leads to an explosion in the number of specialized hardware devices, which are now offered by major cloud vendors. By hiding the low-level complexity through a tensor-based interface, tensor computation runtimes (TCRs) such as PyTorch allow data scientists to efficiently exploit the exciting capabilities offered by the new hardware. In this paper, we explore how database management systems can ride the wave of innovation happening in the AI space. We design, build, and evaluate Tensor Query Processor (TQP): TQP transforms SQL queries into tensor programs and executes them on TCRs. TQP is able to run the full TPC-H benchmark by implementing novel algorithms for relational operators on the tensor routines. At the same time, TQP can support various hardware while only requiring a fraction of the usual development effort. Experiments show that TQP can improve query execution time by up to 10$\times$ over specialized CPU- and GPU-only systems. Finally, TQP can accelerate queries mixing ML predictions and SQL end-to-end, and deliver up to 9$\times$ speedup over CPU baselines.
Off-Policy Evaluation in Embedded Spaces
Venue: arXiv cs.LG 2023
Year: 2023

Off-policy evaluation methods are important in recommendation systems and search engines, where data collected under an existing logging policy is used to estimate the performance of a new proposed policy. A common approach to this problem is weighting, where data is weighted by a density ratio between the probability of actions given contexts in the target and logged policies. In practice, two issues often arise. First, many problems have very large action spaces and we may not observe rewards for most actions, and so in finite samples we may encounter a positivity violation. Second, many recommendation systems are not probabilistic and so having access to logging and target policy densities may not be feasible. To address these issues, we introduce the featurized embedded permutation weighting estimator. The estimator computes the density ratio in an action embedding space, which reduces the possibility of positivity violations. The density ratio is computed leveraging recent advances in normalizing flows and density ratio estimation as a classification problem, in order to obtain estimates which are feasible in practice.
Learning Solution Manifolds for Control Problems via Energy Minimization
Venue: arXiv cs.RO 2023
Year: 2023

A variety of control tasks such as inverse kinematics (IK), trajectory optimization (TO), and model predictive control (MPC) are commonly formulated as energy minimization problems. Numerical solutions to such problems are well-established. However, these are often too slow to be used directly in real-time applications. The alternative is to learn solution manifolds for control problems in an offline stage. Although this distillation process can be trivially formulated as a behavioral cloning (BC) problem in an imitation learning setting, our experiments highlight a number of significant shortcomings arising due to incompatible local minima, interpolation artifacts, and insufficient coverage of the state space. In this paper, we propose an alternative to BC that is efficient and numerically robust. We formulate the learning of solution manifolds as a minimization of the energy terms of a control objective integrated over the space of problems of interest. We minimize this energy integral with a novel method that combines Monte Carlo-inspired adaptive sampling strategies with the derivatives used to solve individual instances of the control task. We evaluate the performance of our formulation on a series of robotic control problems of increasing complexity, and we highlight its benefits through comparisons against traditional methods such as behavioral cloning and Dataset aggregation (Dagger).
Cryptanalysis of some Nonabelian Group-Based Key Exchange Protocols
Venue: arXiv cs.CR 2023
Year: 2023

In the recently emerging field of nonabelian group-based cryptography, a prominently used one-way function is the Conjugacy Search Problem (CSP), and two important classes of platform groups are polycyclic and matrix groups. In this paper, we discuss the complexity of the conjugacy search problem (CSP) in these two classes of platform groups using the three protocols in [10], [26], and [29] as our starting point. We produce a polynomial time solution for the CSP in a finite polycyclic group with two generators, and show that a restricted CSP is reducible to a DLP. In matrix groups over finite fields, we usedthe Jordan decomposition of a matrix to produce a polynomial time reduction of an A-restricted CSP, where A is a cyclic subgroup of the general linear group, to a set of DLPs over an extension of Fq. We use these general methods and results to describe concrete cryptanalysis algorithms for these three systems. In particular, we show that in the group of invertible matrices over finite fields and in polycyclic groups with two generators, a CSP where conjugators are restricted to a cyclic subgroup is reducible to a set of O(n2) discrete logarithm problems. Using our general results, we demonstrate concrete cryptanalysis algorithms for each of these three schemes. We believe that our methods and findings are likely to allow for several other heuristic attacks in the general case.
Computing roadmaps in unbounded smooth real algebraic sets I: connectivity results
Venue: arXiv cs.SC 2023
Year: 2023

Answering connectivity queries in real algebraic sets is a fundamental problem in effective real algebraic geometry that finds many applications in e.g. robotics where motion planning issues are topical. This computational problem is tackled through the computation of so-called roadmaps which are real algebraic subsets of the set V under study, of dimension at most one, and which have a connected intersection with all semi-algebraically connected components of V. Algorithms for computing roadmaps rely on statements establishing connectivity properties of some well-chosen subsets of V , assuming that V is bounded. In this paper, we extend such connectivity statements by dropping the boundedness assumption on V. This exploits properties of so-called generalized polar varieties, which are critical loci of V for some well-chosen polynomial maps.
A Simple Multi-Modality Transfer Learning Baseline for Sign Language Translation
Venue: arXiv cs.CV 2023
Year: 2023

This paper proposes a simple transfer learning baseline for sign language translation. Existing sign language datasets (e.g. PHOENIX-2014T, CSL-Daily) contain only about 10K-20K pairs of sign videos, gloss annotations and texts, which are an order of magnitude smaller than typical parallel data for training spoken language translation models. Data is thus a bottleneck for training effective sign language translation models. To mitigate this problem, we propose to progressively pretrain the model from general-domain datasets that include a large amount of external supervision to within-domain datasets. Concretely, we pretrain the sign-to-gloss visual network on the general domain of human actions and the within-domain of a sign-to-gloss dataset, and pretrain the gloss-to-text translation network on the general domain of a multilingual corpus and the within-domain of a gloss-to-text corpus. The joint model is fine-tuned with an additional module named the visual-language mapper that connects the two networks. This simple baseline surpasses the previous state-of-the-art results on two sign language translation benchmarks, demonstrating the effectiveness of transfer learning. With its simplicity and strong performance, this approach can serve as a solid baseline for future research. Code and models are available at: https://github.com/FangyunWei/SLRT.
GPU-Initiated On-Demand High-Throughput Storage Access in the BaM System Architecture
Venue: arXiv cs.DC 2023
Year: 2023

Graphics Processing Units (GPUs) have traditionally relied on the host CPU to initiate access to the data storage. This approach is well-suited for GPU applications with known data access patterns that enable partitioning of their dataset to be processed in a pipelined fashion in the GPU. However, emerging applications such as graph and data analytics, recommender systems, or graph neural networks, require fine-grained, data-dependent access to storage. CPU initiation of storage access is unsuitable for these applications due to high CPU-GPU synchronization overheads, I/O traffic amplification, and long CPU processing latencies. GPU-initiated storage removes these overheads from the storage control path and, thus, can potentially support these applications at much higher speed. However, there is a lack of systems architecture and software stack that enable efficient GPU-initiated storage access. This work presents a novel system architecture, BaM, that fills this gap. BaM features a fine-grained software cache to coalesce data storage requests while minimizing I/O traffic amplification. This software cache communicates with the storage system via high-throughput queues that enable the massive number of concurrent threads in modern GPUs to make I/O requests at a high rate to fully utilize the storage devices and the system interconnect. Experimental results show that BaM delivers 1.0x and 1.49x end-to-end speed up for BFS and CC graph analytics benchmarks while reducing hardware costs by up to 21.7x over accessing the graph data from the host memory. Furthermore, BaM speeds up data-analytics workloads by 5.3x over CPU-initiated storage access on the same hardware.
Controlling Transaction Rate in Tangle Ledger: A Principal Agent Problem Approach
Venue: arXiv cs.NI 2023
Year: 2023

Tangle is a distributed ledger technology that stores data as a directed acyclic graph (DAG). Unlike blockchain, Tangle does not require dedicated miners for its operation; this makes Tangle suitable for Internet of Things (IoT) applications. Distributed ledgers have a built-in transaction rate control mechanism to prevent congestion and spamming; this is typically achieved by increasing or decreasing the proof of work (PoW) difficulty level based on the number of users. Unfortunately, this simplistic mechanism gives an unfair advantage to users with high computing power. This paper proposes a principal-agent problem (PAP) framework from microeconomics to control the transaction rate in Tangle. With users as agents and the transaction rate controller as the principal, we design a truth-telling mechanism to assign PoW difficulty levels to agents as a function of their computing power. The solution of the PAP is achieved by compensating a higher PoW difficulty level with a larger weight/reputation for the transaction. The mechanism has two benefits, (1) the security of Tangle is increased as agents are incentivized to perform difficult PoW, and (2) the rate of new transactions is moderated in Tangle. The solution of PAP is obtained by solving a mixed-integer optimization problem. We show that the optimal solution of the PAP increases with the computing power of agents. The structural results reduce the search space of the mixed-integer program and enable efficient computation of the optimal mechanism. Finally, via numerical examples, we illustrate the transaction rate control mechanism and study its impact on the dynamics of Tangle.
Differentiated Relevances Embedding for Group-based Referring Expression Comprehension
Venue: arXiv cs.CV 2023
Year: 2023

The key of referring expression comprehension lies in capturing the cross-modal visual-linguistic relevance. Existing works typically model the cross-modal relevance in each image, where the anchor object/expression and their positive expression/object have the same attribute as the negative expression/object, but with different attribute values. These objects/expressions are exclusively utilized to learn the implicit representation of the attribute by a pair of different values, which however impedes the accuracies of the attribute representations, expression/object representations, and their cross-modal relevances since each anchor object/expression usually has multiple attributes while each attribute usually has multiple potential values. To this end, we investigate a novel REC problem named Group-based REC, where each object/expression is simultaneously employed to construct the multiple triplets among the semantically similar images. To tackle the explosion of the negatives and the differentiation of the anchor-negative relevance scores, we propose the multi-group self-paced relevance learning schema to adaptively assign within-group object-expression pairs with different priorities based on their cross-modal relevances. Since the average cross-modal relevance varies a lot across different groups, we further design an across-group relevance constraint to balance the bias of the group priority. Experiments on three standard REC benchmarks demonstrate the effectiveness and superiority of our method.