OpenRaiser/Intern-Atlas huggingface dataset:
Adversarial Attacks on Graph Neural Networks via Meta Learning
Venue: arXiv cs.LG 2024
Year: 2024

Deep learning models for graphs have advanced the state of the art on many tasks. Despite their recent success, little is known about their robustness. We investigate training time attacks on graph neural networks for node classification that perturb the discrete graph structure. Our core principle is to use meta-gradients to solve the bilevel problem underlying training-time attacks, essentially treating the graph as a hyperparameter to optimize. Our experiments show that small graph perturbations consistently lead to a strong decrease in performance for graph convolutional networks, and even transfer to unsupervised embeddings. Remarkably, the perturbations created by our algorithm can misguide the graph neural networks such that they perform worse than a simple baseline that ignores all relational information. Our attacks do not assume any knowledge about or access to the target classifiers.
Model-less Active Compliance for Continuum Robots using Recurrent Neural Networks
Venue: arXiv cs.RO 2024
Year: 2024

Endowing continuum robots with compliance while it is interacting with the internal environment of the human body is essential to prevent damage to the robot and the surrounding tissues. Compared with passive compliance, active compliance has the advantages in terms of increasing the force transmission ability and improving safety with monitored force output. Previous studies have demonstrated that active compliance can be achieved based on a complex model of the mechanics combined with a traditional machine learning technique such as a support vector machine. This paper proposes a recurrent neural network based approach that avoids the complexity of modeling while capturing nonlinear factors such as hysteresis, friction and delay of the electronics that are not easy to model. The approach is tested on a 3-tendon single-segment continuum robot with force sensors on each cable. Experiments are conducted to demonstrate that the continuum robot with an RNN based feed-forward controller is capable of responding to external forces quickly and entering an unknown environment compliantly.
Ordinary and Prophet Planning under Uncertainty in Bernoulli Congestion Games
Venue: arXiv cs.GT 2024
Year: 2024

We consider an atomic congestion game in which each player $i$ participates in the game with an exogenous and known probability $p_{i}\in(0,1]$, independently of everybody else, or stays out and incurs no cost. We compute the parameterized Price of Anarchy (PoA) to characterize the impact of demand uncertainty on the efficiency of selfish behavior, considering two different notions of a social planner. A prophet planner knows the realization of the random participation in the game; the ordinary planner does not. As a consequence, a prophet planner can compute an adaptive social optimum that selects different solutions depending on the players that turn out to be active, whereas an ordinary planner faces the same uncertainty as the players and can only minimize the expected social cost according to the player participation distribution. For both type of planners we obtain tight bounds for the PoA, by solving suitable optimization problems parameterized by the maximum participation probability $q=\max_{i} p_{i}$. In the case of affine costs, we find an analytic expression for the corresponding bounds.
The Android Platform Security Model (2023)
Venue: arXiv cs.CR 2024
Year: 2024

Android is the most widely deployed end-user focused operating system. With its growing set of use cases encompassing communication, navigation, media consumption, entertainment, finance, health, and access to sensors, actuators, cameras, or microphones, its underlying security model needs to address a host of practical threats in a wide variety of scenarios while being useful to non-security experts. To support this flexibility, Android's security model must strike a difficult balance between security, privacy, and usability for end users; provide assurances for app developers; and maintain system performance under tight hardware constraints. This paper aims to both document the assumed threat model and discuss its implications, with a focus on the ecosystem context in which Android exists. We analyze how different security measures in past and current Android implementations work together to mitigate these threats, and, where there are special cases in applying the security model in practice; we discuss these deliberate deviations and examine their impact.
MiniMax Entropy Network: Learning Category-Invariant Features for Domain Adaptation
Venue: arXiv cs.CV 2024
Year: 2024

How to effectively learn from unlabeled data from the target domain is crucial for domain adaptation, as it helps reduce the large performance gap due to domain shift or distribution change. In this paper, we propose an easy-to-implement method dubbed MiniMax Entropy Networks (MMEN) based on adversarial learning. Unlike most existing approaches which employ a generator to deal with domain difference, MMEN focuses on learning the categorical information from unlabeled target samples with the help of labeled source samples. Specifically, we set an unfair multi-class classifier named categorical discriminator, which classifies source samples accurately but be confused about the categories of target samples. The generator learns a common subspace that aligns the unlabeled samples based on the target pseudo-labels. For MMEN, we also provide theoretical explanations to show that the learning of feature alignment reduces domain mismatch at the category level. Experimental results on various benchmark datasets demonstrate the effectiveness of our method over existing state-of-the-art baselines.
Autonomous Locomotion Mode Transition in Quadruped Track-Legged Robots: A Simulation-Based Analysis for Step Negotiation
Venue: arXiv cs.RO 2024
Year: 2024

Hybrid track/wheel-legged robots combine the advantages of wheel-based and leg-based locomotion, granting adaptability across varied terrains through efficient transitions between rolling and walking modes. However, automating these transitions remains a significant challenge. In this paper, we introduce a method designed for autonomous mode transition in a quadruped hybrid robot with a track/wheel-legged configuration, especially during step negotiation. Our approach hinges on a decision-making mechanism that evaluates the energy efficiency of both locomotion modes using a proposed energy-based criterion. To guarantee a smooth negotiation of steps, we incorporate two climbing gaits designated for the assessment of energy usage in walking locomotion. Simulation results validate the method's effectiveness, showing successful autonomous transitions across steps of diverse heights. Our suggested approach has universal applicability and can be modified to suit other hybrid robots of similar mechanical configuration, provided their locomotion energy performance is studied beforehand.
Stay or Switch: Competitive Online Algorithms for Energy Plan Selection in Energy Markets with Retail Choice
Venue: arXiv cs.DS 2024
Year: 2024

Energy markets with retail choice enable customers to switch energy plans among competitive retail suppliers. Despite the promising benefits of more affordable prices and better savings to customers, there appears subsided participation in energy retail markets from residential customers. One major reason is the complex online decision-making process for selecting the best energy plan from a multitude of options that hinders average consumers. In this paper, we shed light on the online energy plan selection problem by providing effective competitive online algorithms. We first formulate the online energy plan selection problem as a metrical task system problem with temporally dependent switching costs. For the case of constant cancellation fee, we present a 3-competitive deterministic online algorithm and a 2-competitive randomized online algorithm for solving the energy plan selection problem. We show that the two competitive ratios are the best possible among deterministic and randomized online algorithms, respectively. We further extend our online algorithms to the case where the cancellation fee is linearly proportional to the residual contract duration. Through empirical evaluations using real-world household and energy plan data, we show that our deterministic online algorithm can produce on average 14.6% cost saving, as compared to 16.2% by the offline optimal algorithm, while our randomized online algorithm can further improve cost saving by up to 0.5%.
Topological Characterization of Consensus in Distributed Systems
Venue: arXiv cs.DC 2024
Year: 2024

We provide a complete characterization of both uniform and non-uniform deterministic consensus solvability in distributed systems with benign process and communication faults using point-set topology. More specifically, we non-trivially extend the approach introduced by Alpern and Schneider in 1985, by introducing novel fault-aware topologies on the space of infinite executions: the process-view topology, induced by a distance function that relies on the local view of a given process in an execution, and the minimum topology, which is induced by a distance function that focuses on the local view of the process that is the last to distinguish two executions. Consensus is solvable in a given model if and only if the sets of admissible executions leading to different decision values is disconnected in these topologies. By applying our approach to a wide range of different applications, we provide a topological explanation of a number of existing algorithms and impossibility results and develop several new ones, including a general equivalence of the strong and weak validity conditions.
On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems
Venue: arXiv cs.LG 2024
Year: 2024

We consider nonconvex-concave minimax problems, $\min_{\mathbf{x}} \max_{\mathbf{y} \in \mathcal{Y}} f(\mathbf{x}, \mathbf{y})$, where $f$ is nonconvex in $\mathbf{x}$ but concave in $\mathbf{y}$ and $\mathcal{Y}$ is a convex and bounded set. One of the most popular algorithms for solving this problem is the celebrated gradient descent ascent (GDA) algorithm, which has been widely used in machine learning, control theory and economics. Despite the extensive convergence results for the convex-concave setting, GDA with equal stepsize can converge to limit cycles or even diverge in a general setting. In this paper, we present the complexity results on two-time-scale GDA for solving nonconvex-concave minimax problems, showing that the algorithm can find a stationary point of the function $Φ(\cdot) := \max_{\mathbf{y} \in \mathcal{Y}} f(\cdot, \mathbf{y})$ efficiently. To the best our knowledge, this is the first nonasymptotic analysis for two-time-scale GDA in this setting, shedding light on its superior practical performance in training generative adversarial networks (GANs) and other real applications.
A Survey of Behavior Learning Applications in Robotics -- State of the Art and Perspectives
Venue: arXiv cs.RO 2024
Year: 2024

Recent success of machine learning in many domains has been overwhelming, which often leads to false expectations regarding the capabilities of behavior learning in robotics. In this survey, we analyze the current state of machine learning for robotic behaviors. We will give a broad overview of behaviors that have been learned and used on real robots. Our focus is on kinematically or sensorially complex robots. That includes humanoid robots or parts of humanoid robots, for example, legged robots or robotic arms. We will classify presented behaviors according to various categories and we will draw conclusions about what can be learned and what should be learned. Furthermore, we will give an outlook on problems that are challenging today but might be solved by machine learning in the future and argue that classical robotics and other approaches from artificial intelligence should be integrated more with machine learning to form complete, autonomous systems.
Discrete calculus with cubic cells on discrete manifolds
Venue: arXiv cs.DM 2024
Year: 2024

This work is thought as an operative guide to discrete exterior calculus (DEC), but at the same time with a rigorous exposition. We present a version of (DEC) on cubic cell, defining it for discrete manifolds. An example of how it works, it is done on the discrete torus, where usual Gauss and Stokes theorems are recovered.
Bayesian Modelling in Practice: Using Uncertainty to Improve Trustworthiness in Medical Applications
Venue: arXiv cs.LG 2024
Year: 2024

The Intensive Care Unit (ICU) is a hospital department where machine learning has the potential to provide valuable assistance in clinical decision making. Classical machine learning models usually only provide point-estimates and no uncertainty of predictions. In practice, uncertain predictions should be presented to doctors with extra care in order to prevent potentially catastrophic treatment decisions. In this work we show how Bayesian modelling and the predictive uncertainty that it provides can be used to mitigate risk of misguided prediction and to detect out-of-domain examples in a medical setting. We derive analytically a bound on the prediction loss with respect to predictive uncertainty. The bound shows that uncertainty can mitigate loss. Furthermore, we apply a Bayesian Neural Network to the MIMIC-III dataset, predicting risk of mortality of ICU patients. Our empirical results show that uncertainty can indeed prevent potential errors and reliably identifies out-of-domain patients. These results suggest that Bayesian predictive uncertainty can greatly improve trustworthiness of machine learning models in high-risk settings such as the ICU.
Derivation of the Variational Bayes Equations
Venue: arXiv cs.NE 2024
Year: 2024

The derivation of key equations for the variational Bayes approach is well-known in certain circles. However, translating the fundamental derivations (e.g., as found in Beal's work) to Friston's notation is somewhat delicate. Further, the notion of using variational Bayes in the context of a system with a Markov blanket requires special attention. This Technical Report presents the derivation in detail. It further illustrates how the variational Bayes method provides a framework for a new computational engine, incorporating the 2-D cluster variation method (CVM), which provides a necessary free energy equation that can be minimized across both the external and representational systems' states, respectively.
Finding irrelevant vertices in linear time on bounded-genus graphs
Venue: arXiv cs.DS 2024
Year: 2024

The irrelevant vertex technique provides a powerful tool for the design of parameterized algorithms for a wide variety of problems on graphs. A common characteristic of these problems, permitting the application of this technique on surface-embedded graphs, is the fact that every graph of large enough treewidth contains a vertex that is irrelevant, in the sense that its removal yields an equivalent instance of the problem. The straightforward application of this technique yields algorithms with running time that is quadratic in the size of the input graph. This running time is due to the fact that it takes linear time to detect one irrelevant vertex and the total number of irrelevant vertices to be detected is linear as well. Using advanced techniques, sub-quadratic algorithms have been designed for particular problems, even in general graphs. However, designing a general framework for linear-time algorithms has been open, even for the bounded-genus case. In this paper we introduce a general framework that enables finding in linear time an entire set of irrelevant vertices whose removal yields a bounded-treewidth graph, provided that the input graph has bounded genus. Our technique consists of decomposing any surface-embedded graph into a tree-structured collection of bounded-treewidth subgraphs where detecting globally irrelevant vertices can be done locally and independently. Our method is applicable to a wide variety of known graph containment or graph modification problems where the irrelevant vertex technique applies. Examples include the (Induced) Minor Folio problem, the (Induced) Disjoint Paths problem, and the $\mathcal{F}$-Minor-Deletion problem.
Sparsely Activated Networks
Venue: arXiv cs.LG 2024
Year: 2024

Previous literature on unsupervised learning focused on designing structural priors with the aim of learning meaningful features. However, this was done without considering the description length of the learned representations which is a direct and unbiased measure of the model complexity. In this paper, first we introduce the $φ$ metric that evaluates unsupervised models based on their reconstruction accuracy and the degree of compression of their internal representations. We then present and define two activation functions (Identity, ReLU) as base of reference and three sparse activation functions (top-k absolutes, Extrema-Pool indices, Extrema) as candidate structures that minimize the previously defined $φ$. We lastly present Sparsely Activated Networks (SANs) that consist of kernels with shared weights that, during encoding, are convolved with the input and then passed through a sparse activation function. During decoding, the same weights are convolved with the sparse activation map and subsequently the partial reconstructions from each weight are summed to reconstruct the input. We compare SANs using the five previously defined activation functions on a variety of datasets (Physionet, UCI-epilepsy, MNIST, FMNIST) and show that models that are selected using $φ$ have small description representation length and consist of interpretable kernels.
Maximum rectilinear convex subsets
Venue: arXiv cs.CG 2024
Year: 2024

Let $P$ be a set of $n$ points in the plane. We consider a variation of the classical Erdős-Szekeres problem, presenting efficient algorithms with $O(n^3)$ running time and $O(n^2)$ space complexity that compute: (1) A subset $S$ of $P$ such that the boundary of the rectilinear convex hull of $S$ has the maximum number of points from $P$, (2) a subset $S$ of $P$ such that the boundary of the rectilinear convex hull of $S$ has the maximum number of points from $P$ and its interior contains no element of $P$, (3) a subset $S$ of $P$ such that the rectilinear convex hull of $S$ has maximum area and its interior contains no element of $P$, and (4) when each point of $P$ is assigned a weight, positive or negative, a subset $S$ of $P$ that maximizes the total weight of the points in the rectilinear convex hull of $S$. We also revisit the problems of computing a maximum-area orthoconvex polygon and computing a maximum-area staircase polygon, amidst a point set in a rectangular domain. We obtain new and simpler algorithms to solve both problems with the same complexity as in the state of the art.
DECO: Liberating Web Data Using Decentralized Oracles for TLS
Venue: arXiv cs.CR 2024
Year: 2024

Thanks to the widespread deployment of TLS, users can access private data over channels with end-to-end confidentiality and integrity. What they cannot do, however, is prove to third parties the {\em provenance} of such data, i.e., that it genuinely came from a particular website. Existing approaches either introduce undesirable trust assumptions or require server-side modifications. As a result, the value of users' private data is locked up in its point of origin. Users cannot export their data with preserved integrity to other applications without help and permission from the current data holder. We propose DECO (short for \underline{dec}entralized \underline{o}racle) to address the above problems. DECO allows users to prove that a piece of data accessed via TLS came from a particular website and optionally prove statements about such data in zero-knowledge, keeping the data itself secret. DECO is the first such system that works without trusted hardware or server-side modifications. DECO can liberate data from centralized web-service silos, making it accessible to a rich spectrum of applications. To demonstrate the power of DECO, we implement three applications that are hard to achieve without it: a private financial instrument using smart contracts, converting legacy credentials to anonymous credentials, and verifiable claims against price discrimination.
Learning Hierarchically Structured Concepts
Venue: arXiv cs.AI 2024
Year: 2024

We study the question of how concepts that have structure get represented in the brain. Specifically, we introduce a model for hierarchically structured concepts and we show how a biologically plausible neural network can recognize these concepts, and how it can learn them in the first place. Our main goal is to introduce a general framework for these tasks and prove formally how both (recognition and learning) can be achieved. We show that both tasks can be accomplished even in presence of noise. For learning, we analyze Oja's rule formally, a well-known biologically-plausible rule for adjusting the weights of synapses. We complement the learning results with lower bounds asserting that, in order to recognize concepts of a certain hierarchical depth, neural networks must have a corresponding number of layers.
Deep Semantic Segmentation of Natural and Medical Images: A Review
Venue: arXiv cs.CV 2024
Year: 2024

The semantic image segmentation task consists of classifying each pixel of an image into an instance, where each instance corresponds to a class. This task is a part of the concept of scene understanding or better explaining the global context of an image. In the medical image analysis domain, image segmentation can be used for image-guided interventions, radiotherapy, or improved radiological diagnostics. In this review, we categorize the leading deep learning-based medical and non-medical image segmentation solutions into six main groups of deep architectural, data synthesis-based, loss function-based, sequenced models, weakly supervised, and multi-task methods and provide a comprehensive review of the contributions in each of these groups. Further, for each group, we analyze each variant of these groups and discuss the limitations of the current approaches and present potential future research directions for semantic image segmentation.
Termination of Triangular Polynomial Loops
Venue: arXiv cs.LO 2024
Year: 2024

We consider the problem of proving termination for triangular weakly non-linear loops (twn-loops) over some ring $\mathcal{S}$ like $\mathbb{Z}$, $\mathbb{Q}$, or $\mathbb{R}$. The guard of such a loop is an arbitrary quantifier-free Boolean formula over (possibly non-linear) polynomial inequations, and the body is a single assignment of the form $(x_1, \ldots, x_d) \longleftarrow (c_1 \cdot x_1 + p_1, \ldots, c_d \cdot x_d + p_d)$ where each $x_i$ is a variable, $c_i \in \mathcal{S}$, and each $p_i$ is a (possibly non-linear) polynomial over $\mathcal{S}$ and the variables $x_{i+1},\ldots,x_{d}$. We show that the question of termination can be reduced to the existential fragment of the first-order theory of $\mathcal{S}$. For loops over $\mathbb{R}$, our reduction implies decidability of termination. For loops over $\mathbb{Z}$ and $\mathbb{Q}$, it proves semi-decidability of non-termination. Furthermore, we present a transformation to convert certain non-twn-loops into twn-form. Then the original loop terminates iff the transformed loop terminates over a specific subset of $\mathbb{R}$, which can also be checked via our reduction. Moreover, we formalize a technique to linearize (the updates of) twn-loops in our setting and analyze its complexity. Based on these results, we prove complexity bounds for the termination problem of twn-loops as well as tight bounds for two important classes of loops which can always be transformed into twn-loops. Finally, we show that there is an important class of linear loops where our decision procedure results in an efficient procedure for termination analysis, i.e., where the parameterized complexity of deciding termination is polynomial.