OpenRaiser/Intern-Atlas huggingface dataset:
Efficient estimation of the modified Gromov-Hausdorff distance between unweighted graphs
Venue: arXiv cs.CG 2024
Year: 2024

Gromov-Hausdorff distances measure shape difference between the objects representable as compact metric spaces, e.g. point clouds, manifolds, or graphs. Computing any Gromov-Hausdorff distance is equivalent to solving an NP-Hard optimization problem, deeming the notion impractical for applications. In this paper we propose polynomial algorithm for estimating the so-called modified Gromov-Hausdorff (mGH) distance, whose topological equivalence with the standard Gromov-Hausdorff (GH) distance was established in Mémoli F, 2012. We implement the algorithm for the case of compact metric spaces induced by unweighted graphs as part of Python library $\verb|scikit-tda|$, and demonstrate its performance on real-world and synthetic networks. The algorithm finds the mGH distances exactly on most graphs with the scale-free property. We use the computed mGH distances to successfully detect outliers in real-world social and computer networks.
Question Classification with Deep Contextualized Transformer
Venue: arXiv cs.CL 2024
Year: 2024

The latest work for Question and Answer problems is to use the Stanford Parse Tree. We build on prior work and develop a new method to handle the Question and Answer problem with the Deep Contextualized Transformer to manage some aberrant expressions. We also conduct extensive evaluations of the SQuAD and SwDA dataset and show significant improvement over QA problem classification of industry needs. We also investigate the impact of different models for the accuracy and efficiency of the problem answers. It shows that our new method is more effective for solving QA problems with higher accuracy
Hierarchical Representation Learning in Graph Neural Networks with Node Decimation Pooling
Venue: arXiv cs.LG 2024
Year: 2024

In graph neural networks (GNNs), pooling operators compute local summaries of input graphs to capture their global properties, and they are fundamental for building deep GNNs that learn hierarchical representations. In this work, we propose the Node Decimation Pooling (NDP), a pooling operator for GNNs that generates coarser graphs while preserving the overall graph topology. During training, the GNN learns new node representations and fits them to a pyramid of coarsened graphs, which is computed offline in a pre-processing stage. NDP consists of three steps. First, a node decimation procedure selects the nodes belonging to one side of the partition identified by a spectral algorithm that approximates the \maxcut{} solution. Afterwards, the selected nodes are connected with Kron reduction to form the coarsened graph. Finally, since the resulting graph is very dense, we apply a sparsification procedure that prunes the adjacency matrix of the coarsened graph to reduce the computational cost in the GNN. Notably, we show that it is possible to remove many edges without significantly altering the graph structure. Experimental results show that NDP is more efficient compared to state-of-the-art graph pooling operators while reaching, at the same time, competitive performance on a significant variety of graph classification tasks.
Prediction, Communication, and Computing Duration Optimization for VR Video Streaming
Venue: arXiv cs.IT 2024
Year: 2024

Proactive tile-based video streaming can avoid motion-to-photon latency of wireless virtual reality (VR) by computing and delivering the predicted tiles to be requested before playback. All existing works either focus on designing predictors or allocating computing and communications resources. Yet to avoid the latency, the successively executed prediction, communication, and computing tasks should be accomplished within a predetermined time. Moreover, the quality of experience (QoE) of proactive VR streaming depends on the worst performance of the three tasks. In this paper, we jointly optimize the duration of the observation window for predicting tiles and the durations for computing and transmitting the predicted tiles, aimed at balancing the performance for three tasks to maximize the QoE given arbitrary predictor and configured resources. We obtain the closed-form optimal solution by decomposing the formulated problem equivalently into two subproblems. With the optimized durations, we find a resource-limited region where the QoE increases rapidly with configured resources, and a prediction-limited region where the QoE can be improved more efficiently with a better predictor. Simulation results using three existing predictors and a real dataset validate the analysis and demonstrate the gain from the joint optimization over non-optimized counterparts.
Simulation-based reinforcement learning for real-world autonomous driving
Venue: arXiv cs.LG 2024
Year: 2024

We use reinforcement learning in simulation to obtain a driving system controlling a full-size real-world vehicle. The driving policy takes RGB images from a single camera and their semantic segmentation as input. We use mostly synthetic data, with labelled real-world data appearing only in the training of the segmentation network. Using reinforcement learning in simulation and synthetic data is motivated by lowering costs and engineering effort. In real-world experiments we confirm that we achieved successful sim-to-real policy transfer. Based on the extensive evaluation, we analyze how design decisions about perception, control, and training impact the real-world performance.
Provably Efficient Exploration in Policy Optimization
Venue: arXiv cs.LG 2024
Year: 2024

While policy-based reinforcement learning (RL) achieves tremendous successes in practice, it is significantly less understood in theory, especially compared with value-based RL. In particular, it remains elusive how to design a provably efficient policy optimization algorithm that incorporates exploration. To bridge such a gap, this paper proposes an Optimistic variant of the Proximal Policy Optimization algorithm (OPPO), which follows an ``optimistic version'' of the policy gradient direction. This paper proves that, in the problem of episodic Markov decision process with linear function approximation, unknown transition, and adversarial reward with full-information feedback, OPPO achieves $\tilde{O}(\sqrt{d^2 H^3 T} )$ regret. Here $d$ is the feature dimension, $H$ is the episode horizon, and $T$ is the total number of steps. To the best of our knowledge, OPPO is the first provably efficient policy optimization algorithm that explores.
When Explanations Lie: Why Many Modified BP Attributions Fail
Venue: arXiv cs.LG 2024
Year: 2024

Attribution methods aim to explain a neural network's prediction by highlighting the most relevant image areas. A popular approach is to backpropagate (BP) a custom relevance score using modified rules, rather than the gradient. We analyze an extensive set of modified BP methods: Deep Taylor Decomposition, Layer-wise Relevance Propagation (LRP), Excitation BP, PatternAttribution, DeepLIFT, Deconv, RectGrad, and Guided BP. We find empirically that the explanations of all mentioned methods, except for DeepLIFT, are independent of the parameters of later layers. We provide theoretical insights for this surprising behavior and also analyze why DeepLIFT does not suffer from this limitation. Empirically, we measure how information of later layers is ignored by using our new metric, cosine similarity convergence (CSC). The paper provides a framework to assess the faithfulness of new and existing modified BP methods theoretically and empirically. For code see: https://github.com/berleon/when-explanations-lie
A Faithful Discretization of the Verbose Persistent Homology Transform
Venue: arXiv cs.CG 2024
Year: 2024

The persistent homology transform (PHT) represents a shape with a multiset of persistence diagrams parameterized by the sphere of directions in the ambient space. In this work, we describe a finite set of diagrams that discretize the PHT such that it faithfully represents the underlying shape. We provide a discretization that is exponential in the dimension of the shape. Moreover, we show that this discretization is stable with respect to various perturbations and we provide an algorithm for computing the discretization. Our approach relies only on knowing the heights and dimensions of topological events, which means that it can be adapted to provide discretizations of other dimension-returning topological transforms, including the Betti function transform. With mild alterations, we also adapt our methods to faithfully discretize the Euler characteristic function transform.
Properties of Winning Iterated Prisoner's Dilemma Strategies
Venue: arXiv cs.GT 2024
Year: 2024

Researchers have explored the performance of Iterated Prisoner's Dilemma strategies for decades, from the celebrated performance of Tit for Tat to the introduction of the zero-determinant strategies and the use of sophisticated learning structures such as neural networks. Many new strategies have been introduced and tested in a variety of tournaments and population dynamics. Typical results in the literature, however, rely on performance against a small number of somewhat arbitrarily selected strategies in a small number of tournaments, casting doubt on the generalizability of conclusions. In this work, we analyze a large collection of 195 strategies in thousands of computer tournaments, present the top performing strategies across multiple tournament types, and distill their salient features. The results show that there is not yet a single strategy that performs well in diverse Iterated Prisoner's Dilemma scenarios, nevertheless there are several properties that heavily influence the best performing strategies. This refines the properties described by Axelrod in light of recent and more diverse opponent populations to: be nice, be provocable and generous, be a little envious, be clever, and adapt to the environment. More precisely, we find that strategies perform best when their probability of cooperation matches the total tournament population's aggregate cooperation probabilities. The features of high performing strategies help cast some light on why strategies such as Tit For Tat performed historically well in tournaments and why zero-determinant strategies typically do not fare well in tournament settings. Furthermore, our findings have implications for the future training of autonomous agents, as understanding the crucial features for incorporation into these agents becomes essential.
United for Change: Deliberative Coalition Formation to Change the Status Quo
Venue: arXiv cs.MA 2024
Year: 2024

We study a setting in which a community wishes to identify a strongly supported proposal from a space of alternatives, in order to change the status quo. We describe a deliberation process in which agents dynamically form coalitions around proposals that they prefer over the status quo. We formulate conditions on the space of proposals and on the ways in which coalitions are formed that guarantee deliberation to succeed, that is, to terminate by identifying a proposal with the largest possible support. Our results provide theoretical foundations for the analysis of deliberative processes such as the ones that take place in online systems for democratic deliberation support.
Empirical Analysis of Fictitious Play for Nash Equilibrium Computation in Multiplayer Games
Venue: arXiv cs.GT 2024
Year: 2024

While fictitious play is guaranteed to converge to Nash equilibrium in certain game classes, such as two-player zero-sum games, it is not guaranteed to converge in non-zero-sum and multiplayer games. We show that fictitious play in fact leads to improved Nash equilibrium approximation over a variety of game classes and sizes than (counterfactual) regret minimization, which has recently produced superhuman play for multiplayer poker. We also show that when fictitious play is run several times using random initializations it is able to solve several known challenge problems in which the standard version is known to not converge, including Shapley's classic counterexample. These provide some of the first positive results for fictitious play in these settings, despite the fact that worst-case theoretical results are negative.
A Review of Blockchain-based Smart Grid: Applications,Opportunities, and Future Directions
Venue: arXiv cs.CY 2024
Year: 2024

The Smart Grid (SG) concept presented an unprecedented opportunity to move the energy sector to more availability, reliability, and efficiency to improve our economic and environmental conditions. Renewable energy sources (Solar & Wind) are such technologies that are used in the smart grid to figure out the environmental and economic issues and challenges. Smart grids provide energy in different crowded sectors with the efficient and timely transmission of electricity. But the traditional power grids follow a centralized approach for energy transactions with a large number of growing connections and become more challenging to handle power disturbance in the grid. Blockchain as a decentralized and distributed technology provides promising applications in the smart grid infrastructure with its excellent and salient features. In this paper, we provide a concise review of blockchain architecture, concepts, and applications in smart grids. Different potential opportunities for blockchain technology with smart grids are also discussed. Some future directions concluded the paper.
Symmetric Arithmetic Circuits
Venue: arXiv cs.CC 2024
Year: 2024

We introduce symmetric arithmetic circuits, i.e. arithmetic circuits with a natural symmetry restriction. In the context of circuits computing polynomials defined on a matrix of variables, such as the determinant or the permanent, the restriction amounts to requiring that the shape of the circuit is invariant under simultaneous row and column permutations of the matrix. We establish unconditional exponential lower bounds on the size of any symmetric circuit for computing the permanent. In contrast, we show that there are polynomial-size symmetric circuits for computing the determinant over fields of characteristic zero.
Formal Methods: From Academia to Industrial Practice. A Travel Guide
Venue: arXiv cs.SE 2024
Year: 2024

For many decades, formal methods are considered to be the way forward to help the software industry to make more reliable and trustworthy software. However, despite this strong belief and many individual success stories, no real change in industrial software development seems to be occurring. In fact, the software industry itself is moving forward rapidly, and the gap between what formal methods can achieve and the daily software-development practice does not appear to be getting smaller (and might even be growing). In the past, many recommendations have already been made on how to develop formal-methods research in order to close this gap. This paper investigates why the gap nevertheless still exists and provides its own recommendations on what can be done by the formal-methods-research community to bridge it. Our recommendations do not focus on open research questions. In fact, formal-methods tools and techniques are already of high quality and can address many non-trivial problems; we do give some technical recommendations on how tools and techniques can be made more accessible. To a greater extent, we focus on the human aspect: how to achieve impact, how to change the way of thinking of the various stakeholders about this issue, and in particular, as a research community, how to alter our behaviour, and instead of competing, collaborate to address this issue.
Comprehensive Taxonomies of Nature- and Bio-inspired Optimization: Inspiration versus Algorithmic Behavior, Critical Analysis and Recommendations (from 2020 to 2024)
Venue: arXiv cs.AI 2024
Year: 2024

In recent years, bio-inspired optimization methods, which mimic biological processes to solve complex problems, have gained popularity in recent literature. The proliferation of proposals prove the growing interest in this field. The increase in nature- and bio-inspired algorithms, applications, and guidelines highlights growing interest in this field. However, the exponential rise in the number of bio-inspired algorithms poses a challenge to the future trajectory of this research domain. Along the five versions of this document, the number of approaches grows incessantly, and where having a new biological description takes precedence over real problem-solving. This document presents two comprehensive taxonomies. One based on principles of biological similarity, and the other one based on operational aspects associated with the iteration of population models that initially have a biological inspiration. Therefore, these taxonomies enable researchers to categorize existing algorithmic developments into well-defined classes, considering two criteria: the source of inspiration, and the behavior exhibited by each algorithm. Using these taxonomies, we classify 518 algorithms based on nature-inspired and bio-inspired principles. Each algorithm within these categories is thoroughly examined, allowing for a critical synthesis of design trends and similarities, and identifying the most analogous classical algorithm for each proposal. From our analysis, we conclude that a poor relationship is often found between the natural inspiration of an algorithm and its behavior. Furthermore, similarities in terms of behavior between different algorithms are greater than what is claimed in their public disclosure: specifically, we show that more than one-fourth of the reviewed solvers are versions of classical algorithms. The conclusions from the analysis of the algorithms lead to several learned lessons.
The Topology of Local Computing in Networks
Venue: arXiv cs.DC 2024
Year: 2024

Modeling distributed computing in a way enabling the use of formal methods is a challenge that has been approached from different angles, among which two techniques emerged at the turn of the century: protocol complexes, and directed algebraic topology. In both cases, the considered computational model generally assumes communication via shared objects, typically a shared memory consisting of a collection of read-write registers. Our paper is concerned with network computing, where the processes are located at the nodes of a network, and communicate by exchanging messages along the edges of that network. Applying the topological approach for verification in network computing is a considerable challenge, mainly because the presence of identifiers assigned to the nodes yields protocol complexes whose size grows exponentially with the size of the underlying network. However, many of the problems studied in this context are of local nature, and their definitions do not depend on the identifiers or on the size of the network. We leverage this independence in order to meet the above challenge, and present $\textit{local}$ protocol complexes, whose sizes do not depend on the size of the network. As an application of the design of "compact" protocol complexes, we reformulate the celebrated lower bound of $Ω(\log^*n)$ rounds for 3-coloring the $n$-node ring, in the algebraic topology framework.
Adversarial Machine Learning: Bayesian Perspectives
Venue: arXiv cs.AI 2024
Year: 2024

Adversarial Machine Learning (AML) is emerging as a major field aimed at protecting machine learning (ML) systems against security threats: in certain scenarios there may be adversaries that actively manipulate input data to fool learning systems. This creates a new class of security vulnerabilities that ML systems may face, and a new desirable property called adversarial robustness essential to trust operations based on ML outputs. Most work in AML is built upon a game-theoretic modelling of the conflict between a learning system and an adversary, ready to manipulate input data. This assumes that each agent knows their opponent's interests and uncertainty judgments, facilitating inferences based on Nash equilibria. However, such common knowledge assumption is not realistic in the security scenarios typical of AML. After reviewing such game-theoretic approaches, we discuss the benefits that Bayesian perspectives provide when defending ML-based systems. We demonstrate how the Bayesian approach allows us to explicitly model our uncertainty about the opponent's beliefs and interests, relaxing unrealistic assumptions, and providing more robust inferences. We illustrate this approach in supervised learning settings, and identify relevant future research problems.
Scene Completeness-Aware Lidar Depth Completion for Driving Scenario
Venue: arXiv cs.CV 2024
Year: 2024

This paper introduces Scene Completeness-Aware Depth Completion (SCADC) to complete raw lidar scans into dense depth maps with fine and complete scene structures. Recent sparse depth completion for lidars only focuses on the lower scenes and produces irregular estimations on the upper because existing datasets, such as KITTI, do not provide groundtruth for upper areas. These areas are considered less important since they are usually sky or trees of less scene understanding interest. However, we argue that in several driving scenarios such as large trucks or cars with loads, objects could extend to the upper parts of scenes. Thus depth maps with structured upper scene estimation are important for RGBD algorithms. SCADC adopts stereo images that produce disparities with better scene completeness but are generally less precise than lidars, to help sparse lidar depth completion. To our knowledge, we are the first to focus on scene completeness of sparse depth completion. We validate our SCADC on both depth estimate precision and scene-completeness on KITTI. Moreover, we experiment on less-explored outdoor RGBD semantic segmentation with scene completeness-aware D-input to validate our method.
Semi-supervised Contrastive Learning Using Partial Label Information
Venue: arXiv cs.LG 2024
Year: 2024

In semi-supervised learning, information from unlabeled examples is used to improve the model learned from labeled examples. In some learning problems, partial label information can be inferred from otherwise unlabeled examples and used to further improve the model. In particular, partial label information exists when subsets of training examples are known to have the same label, even though the label itself is missing. By encouraging the model to give the same label to all such examples through contrastive learning objectives, we can potentially improve its performance. We call this encouragement Nullspace Tuning because the difference vector between any pair of examples with the same label should lie in the nullspace of a linear model. In this paper, we investigate the benefit of using partial label information using a careful comparison framework over well-characterized public datasets. We show that the additional information provided by partial labels reduces test error over good semi-supervised methods usually by a factor of 2, up to a factor of 5.5 in the best case. We also show that adding Nullspace Tuning to the newer and state-of-the-art MixMatch method decreases its test error by up to a factor of 1.8.