OpenRaiser/Intern-Atlas huggingface dataset:
Solidago: A Modular Collaborative Scoring Pipeline
Venue: arXiv cs.SI 2024
Year: 2024

This paper presents Solidago, an end-to-end modular pipeline to allow any community of users to collaboratively score any number of entities. Solidago proposes a six-module decomposition. First, it uses pretrust and peer-to-peer vouches to assign trust scores to users. Second, based on participation, trust scores are turned into voting rights per user per entity. Third, for each user, a preference model is learned from the user's evaluation data. Fourth, users' models are put on a similar scale. Fifth, these models are securely aggregated. Sixth, models are post-processed to yield human-readable global scores. We also propose default implementations of the six modules, including a novel trust propagation algorithm, and adaptations of state-of-the-art scaling and aggregation solutions. Our pipeline has been successfully deployed on the open-source platform tournesol.app. We thereby lay an appealing foundation for the collaborative, effective, scalable, fair, interpretable and secure scoring of any set of entities.
SoK: A Stratified Approach to Blockchain Decentralization
Venue: arXiv cs.CR 2024
Year: 2024

Decentralization has been touted as the principal security advantage which propelled blockchain systems at the forefront of developments in the financial technology space. Its exact semantics nevertheless remain highly contested and ambiguous, with proponents and critics disagreeing widely on the level of decentralization offered by existing systems. To address this, we put forth a systematization of the current landscape with respect to decentralization and we derive a methodology that can help direct future research towards defining and measuring decentralization. Our approach dissects blockchain systems into multiple layers, or strata, each possibly encapsulating multiple categories, and it enables a unified method for measuring decentralization in each one. Our layers are (1) hardware, (2) software, (3) network, (4) consensus, (5) economics ("tokenomics"), (6) client API, (7) governance, and (8) geography. Armed with this stratification, we examine for each layer which pertinent properties of distributed ledgers (safety, liveness, privacy, stability) can be at risk due to centralization and in what way. We also introduce a practical test, the "Minimum Decentralization Test" which can provide quick insights about the decentralization state of a blockchain system. To demonstrate how our stratified methodology can be used in practice, we apply it fully (layer by layer) to Bitcoin, and we provide examples of systems which comprise one or more "problematic" layers that cause them to fail the MDT. Our work highlights the challenges in measuring and achieving decentralization, and suggests various potential directions where future research is needed.
DeepSec: Deciding Equivalence Properties for Security Protocols -- Improved theory and practice
Venue: arXiv cs.CR 2024
Year: 2024

Automated verification has become an essential part in the security evaluation of cryptographic protocols. In this context privacy-type properties are often modelled by indistinguishability statements, expressed as behavioural equivalences in a process calculus. In this paper we contribute both to the theory and practice of this verification problem. We establish new complexity results for static equivalence, trace equivalence and labelled bisimilarity and provide a decision procedure for these equivalences in the case of a bounded number of protocol sessions. Our procedure is the first to decide trace equivalence and labelled bisimilarity exactly for a large variety of cryptographic primitives -- those that can be represented by a subterm convergent destructor rewrite system. We also implemented the procedure in a new tool, DeepSec. We showed through extensive experiments that it is significantly more efficient than other similar tools, while at the same time raises the scope of the protocols that can be analysed.
A Penalty-Based Method for Communication-Efficient Decentralized Bilevel Programming
Venue: arXiv cs.LG 2024
Year: 2024

Bilevel programming has recently received attention in the literature due to its wide range of applications, including reinforcement learning and hyper-parameter optimization. However, it is widely assumed that the underlying bilevel optimization problem is solved either by a single machine or, in the case of multiple machines connected in a star-shaped network, i.e., in a federated learning setting. The latter approach suffers from a high communication cost on the central node (e.g., parameter server). Hence, there is an interest in developing methods that solve bilevel optimization problems in a communication-efficient, decentralized manner. To that end, this paper introduces a penalty function-based decentralized algorithm with theoretical guarantees for this class of optimization problems. Specifically, a distributed alternating gradient-type algorithm for solving consensus bilevel programming over a decentralized network is developed. A key feature of the proposed algorithm is the estimation of the hyper-gradient of the penalty function through decentralized computation of matrix-vector products and a few vector communications. The estimation is integrated into an alternating algorithm for solving the penalized reformulation of the bilevel optimization problem. Under appropriate step sizes and penalty parameters, our theoretical framework ensures non-asymptotic convergence to the optimal solution of the original problem under various convexity conditions. Our theoretical result highlights improvements in the iteration complexity of decentralized bilevel optimization, all while making efficient use of vector communication. Empirical results demonstrate that the proposed method performs well in real-world settings.
Consistent Query Answering for Primary Keys and Conjunctive Queries with Counting
Venue: arXiv cs.DB 2024
Year: 2024

The problem of consistent query answering for primary keys and self-join-free conjunctive queries has been intensively studied in recent years and is by now well understood. In this paper, we study an extension of this problem with counting. The queries we consider count how many times each value occurs in a designated (possibly composite) column of an answer to a full conjunctive query. In a setting of database repairs, we adopt the semantics of [Arenas et al., ICDT 2001] which computes tight lower and upper bounds on these counts, where the bounds are taken over all repairs. Ariel Fuxman defined in his PhD thesis a syntactic class of queries, called C_forest, for which this computation can be done by executing two first-order queries (one for lower bounds, and one for upper bounds) followed by simple counting steps. We use the term "parsimonious counting" for this computation. A natural question is whether C_forest contains all self-join-free conjunctive queries that admit parsimonious counting. We answer this question negatively. We define a new syntactic class of queries, called C_parsimony, and prove that it contains all (and only) self-join-free conjunctive queries that admit parsimonious counting.
Dynamic loss balancing and sequential enhancement for road-safety assessment and traffic scene classification
Venue: arXiv cs.CV 2024
Year: 2024

Road-safety inspection is an indispensable instrument for reducing road-accident fatalities contributed to road infrastructure. Recent work formalizes road-safety assessment in terms of carefully selected risk factors that are also known as road-safety attributes. In current practice, these attributes are manually annotated in geo-referenced monocular video for each road segment. We propose to reduce dependency on tedious human labor by automating recognition with a two-stage neural architecture. The first stage predicts more than forty road-safety attributes by observing a local spatio-temporal context. Our design leverages an efficient convolutional pipeline, which benefits from pre-training on semantic segmentation of street scenes. The second stage enhances predictions through sequential integration across a larger temporal window. Our design leverages per-attribute instances of a lightweight bidirectional LSTM architecture. Both stages alleviate extreme class imbalance by incorporating a multi-task variant of recall-based dynamic loss weighting. We perform experiments on the iRAP-BH dataset, which involves fully labeled geo-referenced video along 2,300 km of public roads in Bosnia and Herzegovina. We also validate our approach by comparing it with the related work on two road-scene classification datasets from the literature: Honda Scenes and FM3m. Experimental evaluation confirms the value of our contributions on all three datasets.
Motif-guided Time Series Counterfactual Explanations
Venue: arXiv cs.LG 2024
Year: 2024

With the rising need of interpretable machine learning methods, there is a necessity for a rise in human effort to provide diverse explanations of the influencing factors of the model decisions. To improve the trust and transparency of AI-based systems, the EXplainable Artificial Intelligence (XAI) field has emerged. The XAI paradigm is bifurcated into two main categories: feature attribution and counterfactual explanation methods. While feature attribution methods are based on explaining the reason behind a model decision, counterfactual explanation methods discover the smallest input changes that will result in a different decision. In this paper, we aim at building trust and transparency in time series models by using motifs to generate counterfactual explanations. We propose Motif-Guided Counterfactual Explanation (MG-CF), a novel model that generates intuitive post-hoc counterfactual explanations that make full use of important motifs to provide interpretive information in decision-making processes. To the best of our knowledge, this is the first effort that leverages motifs to guide the counterfactual explanation generation. We validated our model using five real-world time-series datasets from the UCR repository. Our experimental results show the superiority of MG-CF in balancing all the desirable counterfactual explanations properties in comparison with other competing state-of-the-art baselines.
When is Momentum Extragradient Optimal? A Polynomial-Based Analysis
Venue: arXiv cs.LG 2024
Year: 2024

The extragradient method has gained popularity due to its robust convergence properties for differentiable games. Unlike single-objective optimization, game dynamics involve complex interactions reflected by the eigenvalues of the game vector field's Jacobian scattered across the complex plane. This complexity can cause the simple gradient method to diverge, even for bilinear games, while the extragradient method achieves convergence. Building on the recently proven accelerated convergence of the momentum extragradient method for bilinear games \citep{azizian2020accelerating}, we use a polynomial-based analysis to identify three distinct scenarios where this method exhibits further accelerated convergence. These scenarios encompass situations where the eigenvalues reside on the (positive) real line, lie on the real line alongside complex conjugates, or exist solely as complex conjugates. Furthermore, we derive the hyperparameters for each scenario that achieve the fastest convergence rate.
Improving safety in mixed traffic: A learning-based model predictive control for autonomous and human-driven vehicle platooning
Venue: arXiv cs.RO 2024
Year: 2024

As autonomous vehicles (AVs) become more common on public roads, their interaction with human-driven vehicles (HVs) in mixed traffic is inevitable. This requires new control strategies for AVs to handle the unpredictable nature of HVs. This study focused on safe control in mixed-vehicle platoons consisting of both AVs and HVs, particularly during longitudinal car-following scenarios. We introduce a novel model that combines a conventional first-principles model with a Gaussian process (GP) machine learning-based model to better predict HV behavior. Our results showed a significant improvement in predicting HV speed, with a 35.64% reduction in the root mean square error compared with the use of the first-principles model alone. We developed a new control strategy called GP-MPC, which uses the proposed HV model for safer distance management between vehicles in the mixed platoon. The GP-MPC strategy effectively utilizes the capacity of the GP model to assess uncertainties, thereby significantly enhancing safety in challenging traffic scenarios, such as emergency braking scenarios. In simulations, the GP-MPC strategy outperformed the baseline MPC method, offering better safety and more efficient vehicle movement in mixed traffic.
RaLiBEV: Radar and LiDAR BEV Fusion Learning for Anchor Box Free Object Detection Systems
Venue: arXiv cs.CV 2024
Year: 2024

In autonomous driving, LiDAR and radar are crucial for environmental perception. LiDAR offers precise 3D spatial sensing information but struggles in adverse weather like fog. Conversely, radar signals can penetrate rain or mist due to their specific wavelength but are prone to noise disturbances. Recent state-of-the-art works reveal that the fusion of radar and LiDAR can lead to robust detection in adverse weather. The existing works adopt convolutional neural network architecture to extract features from each sensor data, then align and aggregate the two branch features to predict object detection results. However, these methods have low accuracy of predicted bounding boxes due to a simple design of label assignment and fusion strategies. In this paper, we propose a bird's-eye view fusion learning-based anchor box-free object detection system, which fuses the feature derived from the radar range-azimuth heatmap and the LiDAR point cloud to estimate possible objects. Different label assignment strategies have been designed to facilitate the consistency between the classification of foreground or background anchor points and the corresponding bounding box regressions. Furthermore, the performance of the proposed object detector is further enhanced by employing a novel interactive transformer module. The superior performance of the methods proposed in this paper has been demonstrated using the recently published Oxford Radar RobotCar dataset. Our system's average precision significantly outperforms the state-of-the-art method by 13.1% and 19.0% at Intersection of Union (IoU) of 0.8 under 'Clear+Foggy' training conditions for 'Clear' and 'Foggy' testing, respectively.
Spectral Triadic Decompositions of Real-World Networks
Venue: arXiv cs.SI 2024
Year: 2024

A fundamental problem in mathematics and network analysis is to find conditions under which a graph can be partitioned into smaller pieces. The most important tool for this partitioning is the Fiedler vector or discrete Cheeger inequality. These results relate the graph spectrum (eigenvalues of the normalized adjacency matrix) to the ability to break a graph into two pieces, with few edge deletions. An entire subfield of mathematics, called spectral graph theory, has emerged from these results. Yet these results do not say anything about the rich community structure exhibited by real-world networks, which typically have a significant fraction of edges contained in numerous densely clustered blocks. Inspired by the properties of real-world networks, we discover a new spectral condition that relates eigenvalue powers to a network decomposition into densely clustered blocks. We call this the \emph{spectral triadic decomposition}. Our relationship exactly predicts the existence of community structure, as commonly seen in real networked data. Our proof provides an efficient algorithm to produce the spectral triadic decomposition. We observe on numerous social, coauthorship, and citation network datasets that these decompositions have significant correlation with semantically meaningful communities.
Enhancing Resource Utilization of Non-terrestrial Networks Using Temporal Graph-based Deterministic Routing
Venue: arXiv cs.NI 2024
Year: 2024

Deterministic routing has emerged as a promising technology for future non-terrestrial networks (NTNs), offering the potential to enhance service performance and optimize resource utilization. However, the dynamic nature of network topology and resources poses challenges in establishing deterministic routing. These challenges encompass the intricacy of jointly scheduling transmission links and cycles, as well as the difficulty of maintaining stable end-to-end (E2E) routing paths. To tackle these challenges, our work introduces an efficient temporal graph-based deterministic routing strategy. Initially, we utilize a time-expanded graph (TEG) to represent the heterogeneous resources of an NTN in a time-slotted manner. With TEG, we meticulously define each necessary constraint and formulate the deterministic routing problem. Subsequently, we transform this nonlinear problem equivalently into solvable integer linear programming (ILP), providing a robust yet time-consuming performance upper bound. To address the considered problem with reduced complexity, we extend TEG by introducing virtual nodes and edges. This extension facilitates a uniform representation of heterogeneous network resources and traffic transmission requirements. Consequently, we propose a polynomial-time complexity algorithm, enabling the dynamic selection of optimal transmission links and cycles on a hop-by-hop basis. Simulation results validate that the proposed algorithm yields significant performance gains in traffic acceptance, justifying its additional complexity compared to existing routing strategies.
A generalization to networks of Young's characterization of the Borda rule
Venue: arXiv cs.GT 2024
Year: 2024

We prove that, for any given set of networks satisfying suitable conditions, the net-oudegree network solution, the net-indegree network solution, and the total network solution are the unique network solutions on that set satisfying neutrality, consistency and cancellation. The generality of the result obtained allows to get an analogous result for social choice correspondences: for any given set of preference profiles satisfying suitable conditions, the net-oudegree social choice correspondence, the net-indegree social choice correspondence and the total social choice correspondence are the unique social choice correspondences on that set satisfying neutrality, consistency and cancellation. Using the notable fact that several well-known voting rules coincide with the restriction of net-oudegree social choice correspondence to appropriate sets of preference profiles, we are able to deduce a variety of new and known characterization theorems for the Borda rule, the Partial Borda rule, the Averaged Borda rule, the Approval Voting, the Plurality rule and the anti-Plurality rule, among which Young's characterization of the Borda rule and Fishburn's characterization of the Approval Voting.
Deep Joint Source-Channel Coding Over Cooperative Relay Networks
Venue: arXiv cs.IT 2024
Year: 2024

This paper presents a novel deep joint source-channel coding (DeepJSCC) scheme for image transmission over a half-duplex cooperative relay channel. Specifically, we apply DeepJSCC to two basic modes of cooperative communications, namely amplify-and-forward (AF) and decode-and-forward (DF). In DeepJSCC-AF, the relay simply amplifies and forwards its received signal. In DeepJSCC-DF, on the other hand, the relay first reconstructs the transmitted image and then re-encodes it before forwarding. Considering the excessive computation overhead of DeepJSCC-DF for recovering the image at the relay, we propose an alternative scheme, called DeepJSCC-PF, in which the relay processes and forwards its received signal without necessarily recovering the image. Simulation results show that the proposed DeepJSCC-AF, DF, and PF schemes are superior to the digital baselines with BPG compression with polar codes and provides a graceful performance degradation with deteriorating channel quality. Further investigation shows that the PSNR gain of DeepJSCC-DF/PF over DeepJSCC-AF improves as the channel condition between the source and relay improves. Moreover, DeepJSCC-PF scheme achieves a similar performance to DeepJSCC-DF with lower computational complexity.
The $\ell_p$-Subspace Sketch Problem in Small Dimensions with Applications to Support Vector Machines
Venue: arXiv cs.DS 2024
Year: 2024

In the $\ell_p$-subspace sketch problem, we are given an $n\times d$ matrix $A$ with $n>d$, and asked to build a small memory data structure $Q(A,ε)$ so that, for any query vector $x\in\mathbb{R}^d$, we can output a number in $(1\pmε)\|Ax\|_p^p$ given only $Q(A,ε)$. This problem is known to require $\tildeΩ(dε^{-2})$ bits of memory for $d=Ω(\log(1/ε))$. However, for $d=o(\log(1/ε))$, no data structure lower bounds were known. We resolve the memory required to solve the $\ell_p$-subspace sketch problem for any constant $d$ and integer $p$, showing that it is $Ω(ε^{-2(d-1)/(d+2p)})$ bits and $\tilde{O} (ε^{-2(d-1)/(d+2p)})$ words. This shows that one can beat the $Ω(ε^{-2})$ lower bound, which holds for $d = Ω(\log(1/ε))$, for any constant $d$. We also show how to implement the upper bound in a single pass stream, with an additional multiplicative $\operatorname{poly}(\log \log n)$ factor and an additive $\operatorname{poly}(\log n)$ cost in the memory. Our bounds can be applied to point queries for SVMs with additive error, yielding an optimal bound of $\tildeΘ(ε^{-2d/(d+3)})$ for every constant $d$. This is a near-quadratic improvement over the $Ω(ε^{-(d+1)/(d+3)})$ lower bound of (Andoni et al. 2020). Our techniques rely on a novel connection to low dimensional techniques from geometric functional analysis.
Adaptive Federated Minimax Optimization with Lower Complexities
Venue: arXiv cs.LG 2024
Year: 2024

Federated learning is a popular distributed and privacy-preserving learning paradigm in machine learning. Recently, some federated learning algorithms have been proposed to solve the distributed minimax problems. However, these federated minimax algorithms still suffer from high gradient or communication complexity. Meanwhile, few algorithm focuses on using adaptive learning rate to accelerate these algorithms. To fill this gap, in the paper, we study a class of nonconvex minimax optimization, and propose an efficient adaptive federated minimax optimization algorithm (i.e., AdaFGDA) to solve these distributed minimax problems. Specifically, our AdaFGDA builds on the momentum-based variance reduced and local-SGD techniques, and it can flexibly incorporate various adaptive learning rates by using the unified adaptive matrices. Theoretically, we provide a solid convergence analysis framework for our AdaFGDA algorithm under non-i.i.d. setting. Moreover, we prove our AdaFGDA algorithm obtains a lower gradient (i.e., stochastic first-order oracle, SFO) complexity of $\tilde{O}(ε^{-3})$ with lower communication complexity of $\tilde{O}(ε^{-2})$ in finding $ε$-stationary point of the nonconvex minimax problems. Experimentally, we conduct some experiments on the deep AUC maximization and robust neural network training tasks to verify efficiency of our algorithms.