OpenRaiser/Intern-Atlas huggingface dataset:
Succinct Permutation Graphs
Venue: arXiv cs.DS 2022
Year: 2022

We present a succinct data structure for permutation graphs, and their superclass of circular permutation graphs, i.e., data structures using optimal space up to lower order terms. Unlike concurrent work on circle graphs (Acan et al. 2022), our data structure also supports distance and shortest-path queries, as well as adjacency and neighborhood queries, all in optimal time. We present in particular the first succinct exact distance oracle for (circular) permutation graphs. A second succinct data structure also supports degree queries in time independent of the neighborhood's size at the expense of an $O(\log n/\log \log n)$-factor overhead in all running times. Furthermore, we develop a succinct data structure for the class of bipartite permutation graphs. We demonstrate how to run algorithms directly over our succinct representations for several problems on permutation graphs: Clique, Coloring, Independent Set, Hamiltonian Cycle, All-Pair Shortest Paths, and others. Finally, we initiate the study of semi-distributed graph representations; a concept that smoothly interpolates between distributed (labeling schemes) and centralized (standard data structures). We show how to turn some of our data structures into semi-distributed representations by storing only $O(n)$ bits of additional global information, circumventing the lower bound on distance labeling schemes for permutation graphs.
Constant-time connectivity tests
Venue: arXiv cs.DS 2022
Year: 2022

We present implementations of constant-time algorithms for connectivity tests and related problems. Some are implementations of slightly improved variants of previously known algorithms; for other problems we present new algorithms that have substantially better runtime than previously known algorithms (estimates of the distance to and tolerant testers for connectivity, 2-edge-connectivity, 3-edge-connectivity, eulerianity).
Instance Weighted Incremental Evolution Strategies for Reinforcement Learning in Dynamic Environments
Venue: arXiv cs.LG 2022
Year: 2022

Evolution strategies (ES), as a family of black-box optimization algorithms, recently emerge as a scalable alternative to reinforcement learning (RL) approaches such as Q-learning or policy gradient, and are much faster when many central processing units (CPUs) are available due to better parallelization. In this paper, we propose a systematic incremental learning method for ES in dynamic environments. The goal is to adjust previously learned policy to a new one incrementally whenever the environment changes. We incorporate an instance weighting mechanism with ES to facilitate its learning adaptation, while retaining scalability of ES. During parameter updating, higher weights are assigned to instances that contain more new knowledge, thus encouraging the search distribution to move towards new promising areas of parameter space. We propose two easy-to-implement metrics to calculate the weights: instance novelty and instance quality. Instance novelty measures an instance's difference from the previous optimum in the original environment, while instance quality corresponds to how well an instance performs in the new environment. The resulting algorithm, Instance Weighted Incremental Evolution Strategies (IW-IES), is verified to achieve significantly improved performance on challenging RL tasks ranging from robot navigation to locomotion. This paper thus introduces a family of scalable ES algorithms for RL domains that enables rapid learning adaptation to dynamic environments.
Interval Query Problem on Cube-free Median Graphs
Venue: arXiv cs.DS 2022
Year: 2022

In this paper, we introduce the \emph{interval query problem} on cube-free median graphs. Let $G$ be a cube-free median graph and $\mathcal{S}$ be a commutative semigroup. For each vertex $v$ in $G$, we are given an element $p(v)$ in $\mathcal{S}$. For each query, we are given two vertices $u,v$ in $G$ and asked to calculate the sum of $p(z)$ over all vertices $z$ belonging to a $u-v$ shortest path. This is a common generalization of range query problems on trees and grids. In this paper, we provide an algorithm to answer each interval query in $O(\log^2 n)$ time. The required data structure is constructed in $O(n\log^3 n)$ time and $O(n\log^2 n)$ space. To obtain our algorithm, we introduce a new technique, named the \emph{stairs decomposition}, to decompose an interval of cube-free median graphs into simpler substructures.
A Self-supervised Representation Learning of Sentence Structure for Authorship Attribution
Venue: arXiv cs.CL 2022
Year: 2022

Syntactic structure of sentences in a document substantially informs about its authorial writing style. Sentence representation learning has been widely explored in recent years and it has been shown that it improves the generalization of different downstream tasks across many domains. Even though utilizing probing methods in several studies suggests that these learned contextual representations implicitly encode some amount of syntax, explicit syntactic information further improves the performance of deep neural models in the domain of authorship attribution. These observations have motivated us to investigate the explicit representation learning of syntactic structure of sentences. In this paper, we propose a self-supervised framework for learning structural representations of sentences. The self-supervised network contains two components; a lexical sub-network and a syntactic sub-network which take the sequence of words and their corresponding structural labels as the input, respectively. Due to the n-to-1 mapping of words to their structural labels, each word will be embedded into a vector representation which mainly carries structural information. We evaluate the learned structural representations of sentences using different probing tasks, and subsequently utilize them in the authorship attribution task. Our experimental results indicate that the structural embeddings significantly improve the classification tasks when concatenated with the existing pre-trained word embeddings.
Crowdsourcing Bridge Vital Signs with Smartphone Vehicle Trips
Venue: arXiv cs.CY 2022
Year: 2022

A key challenge in monitoring and managing the structural health of bridges is the high-cost associated with specialized sensor networks. In the past decade, researchers predicted that cheap, ubiquitous mobile sensors would revolutionize infrastructure maintenance; yet many of the challenges in extracting useful information in the field with sufficient precision remain unsolved. Herein it is shown that critical physical properties, e.g., modal frequencies, of real bridges can be determined accurately from everyday vehicle trip data. The primary study collects smartphone data from controlled field experiments and "uncontrolled" UBER rides on a long-span suspension bridge in the USA and develops an analytical method to accurately recover modal properties. The method is successfully applied to "partially-controlled" crowdsourced data collected on a short-span highway bridge in Italy. This study verifies that pre-existing mobile sensor data sets, originally captured for other purposes, e.g., commercial use, public works, etc., can contain important structural information and therefore can be repurposed for large-scale infrastructure monitoring. A supplementary analysis projects that the inclusion of crowdsourced data in a maintenance plan for a new bridge can add over fourteen years of service (30% increase) without additional costs. These results suggest that massive and inexpensive datasets collected by smartphones could play an important role in monitoring the health of existing transportation infrastructure.
On Fair Division under Heterogeneous Matroid Constraints
Venue: arXiv cs.GT 2022
Year: 2022

We study fair allocation of indivisible goods among additive agents with feasibility constraints. In these settings, every agent is restricted to get a bundle among a specified set of feasible bundles. Such scenarios have been of great interest to the AI community due to their applicability to real-world problems. Following some impossibility results, we restrict attention to matroid feasibility constraints that capture natural scenarios, such as the allocation of shifts to medical doctors, and the allocation of conference papers to referees. We focus on the common fairness notion of envy-freeness up to one good (EF1). Previous algorithms for finding EF1 allocations are either restricted to agents with identical feasibility constraints, or allow free disposal of items. An open problem is the existence of EF1 complete allocations among heterogeneous agents, where the heterogeneity is both in the agents' feasibility constraints and in their valuations. In this work, we make progress on this problem by providing positive and negative results for different matroid and valuation types. Among other results, we devise polynomial-time algorithms for finding EF1 allocations in the following settings: (i) $n$ agents with heterogeneous partition matroids and heterogeneous binary valuations, (ii) 2 agents with heterogeneous partition matroids and heterogeneous additive valuations, and (iii) at most 3 agents with heterogeneous binary valuations and identical base-orderable matroid constraints.
THIN: THrowable Information Networks and Application for Facial Expression Recognition In The Wild
Venue: arXiv cs.CV 2022
Year: 2022

For a number of machine learning problems, an exogenous variable can be identified such that it heavily influences the appearance of the different classes, and an ideal classifier should be invariant to this variable. An example of such exogenous variable is identity if facial expression recognition (FER) is considered. In this paper, we propose a dual exogenous/endogenous representation. The former captures the exogenous variable whereas the second one models the task at hand (e.g. facial expression). We design a prediction layer that uses a tree-gated deep ensemble conditioned by the exogenous representation. We also propose an exogenous dispelling loss to remove the exogenous information from the endogenous representation. Thus, the exogenous information is used two times in a throwable fashion, first as a conditioning variable for the target task, and second to create invariance within the endogenous representation. We call this method THIN, standing for THrowable Information Networks. We experimentally validate THIN in several contexts where an exogenous information can be identified, such as digit recognition under large rotations and shape recognition at multiple scales. We also apply it to FER with identity as the exogenous variable. We demonstrate that THIN significantly outperforms state-of-the-art approaches on several challenging datasets.
Altruist: Argumentative Explanations through Local Interpretations of Predictive Models
Venue: arXiv cs.LG 2022
Year: 2022

Explainable AI is an emerging field providing solutions for acquiring insights into automated systems' rationale. It has been put on the AI map by suggesting ways to tackle key ethical and societal issues. Existing explanation techniques are often not comprehensible to the end user. Lack of evaluation and selection criteria also makes it difficult for the end user to choose the most suitable technique. In this study, we combine logic-based argumentation with Interpretable Machine Learning, introducing a preliminary meta-explanation methodology that identifies the truthful parts of feature importance oriented interpretations. This approach, in addition to being used as a meta-explanation technique, can be used as an evaluation or selection tool for multiple feature importance techniques. Experimentation strongly indicates that an ensemble of multiple interpretation techniques yields considerably more truthful explanations.
Relating Functional and Imperative Session Types
Venue: arXiv cs.PL 2022
Year: 2022

Imperative session types provide an imperative interface to session-typed communication. In such an interface, channel references are first-class objects with operations that change the typestate of the channel. Compared to functional session type APIs, the program structure is simpler at the surface, but typestate is required to model the current state of communication throughout. Following an early work that explored the imperative approach, a significant body of work on session types has neglected the imperative approach and opts for a functional approach that uses linear types to manage channel references soundly. We demonstrate that the functional approach subsumes the early work on imperative session types by exhibiting a typing and semantics preserving translation into a system of linear functional session types. We further show that the untyped backwards translation from the functional to the imperative calculus is semantics preserving. We restrict the type system of the functional calculus such that the backwards translation becomes type preserving. Thus, we precisely capture the difference in expressiveness of the two calculi and conclude that the lack of expressiveness in the imperative calculus is largely due to restrictions imposed by its type system.
Arboricity games: the core and the nucleolus
Venue: arXiv cs.GT 2022
Year: 2022

The arboricity of a graph is the minimum number of forests required to cover all its edges. In this paper, we examine arboricity from a game-theoretic perspective and investigate cost-sharing in the minimum forest cover problem. We introduce the arboricity game as a cooperative cost game defined on a graph. The players are edges, and the cost of each coalition is the arboricity of the subgraph induced by the coalition. We study properties of the core and propose an efficient algorithm for computing the nucleolus when the core is not empty. In order to compute the nucleolus in the core, we introduce the prime partition which is built on the densest subgraph lattice. The prime partition decomposes the edge set of a graph into a partially ordered set defined from minimal densest minors and their invariant precedence relation. Moreover, edges from the same partition always have the same value in a core allocation. Consequently, when the core is not empty, the prime partition significantly reduces the number of variables and constraints required in the linear programs of Maschler's scheme and allows us to compute the nucleolus in polynomial time. Besides, the prime partition provides a graph decomposition analogous to the celebrated core decomposition and the density-friendly decomposition, which may be of independent interest.
Poincare: Recommending Publication Venues via Treatment Effect Estimation
Venue: arXiv cs.DL 2022
Year: 2022

Choosing a publication venue for an academic paper is a crucial step in the research process. However, in many cases, decisions are based solely on the experience of researchers, which often leads to suboptimal results. Although there exist venue recommender systems for academic papers, they recommend venues where the paper is expected to be published. In this study, we aim to recommend publication venues from a different perspective. We estimate the number of citations a paper will receive if the paper is published in each venue and recommend the venue where the paper has the most potential impact. However, there are two challenges to this task. First, a paper is published in only one venue, and thus, we cannot observe the number of citations the paper would receive if the paper were published in another venue. Secondly, the contents of a paper and the publication venue are not statistically independent; that is, there exist selection biases in choosing publication venues. In this paper, we formulate the venue recommendation problem as a treatment effect estimation problem. We use a bias correction method to estimate the potential impact of choosing a publication venue effectively and to recommend venues based on the potential impact of papers in each venue. We highlight the effectiveness of our method using paper data from computer science conferences.
Towards an Ethical Framework in the Complex Digital Era
Venue: arXiv cs.CY 2022
Year: 2022

The digital revolution has brought ethical crossroads of technology, behavior and truth. However, the need of a comprehensive and constructive ethical framework is emerging as digital platforms have been used to build a global chaotic and truth-agnostic system. The unequal structure of the global system leads to dynamic changes and systemic problems, which have a more significant impact on those that are most vulnerable. Ethical frameworks based only on the individual level are no longer sufficient as they lack the necessary articulation to provide solutions to the new challenges. A new ethical vision must comprise the understanding of the scales and complex interconnections, as well as the causal chains of modern social systems. Many of these systems are internally fragile and very sensitive to external factors and threats, which lead to unethical situations that require systemic solutions still centered on individuals. Furthermore, the multi-layered net-like social tissue generates clusters of power that prevent certain communities from proper development. Digital technology has also impacted at the individual level posing the risk of a more homogeneous, predictable and ultimately controllable humankind. To preserve the core of humanity and the aspiration of common truth, a new ethical framework must empower individuals and uniqueness, as well as cultural heterogeneity, tackling the negative outcomes of digitalization. Only combining human-centered and collectiveness-oriented digital development will it be possible to construct new social models and interactions that are ethical. This vision requires science to enhance ethical frameworks and principles using computational tools to support truth-grounded actions, so as to transform and configure properties of the social systems.
SeqTrans: Automatic Vulnerability Fix via Sequence to Sequence Learning
Venue: arXiv cs.CR 2022
Year: 2022

Software vulnerabilities are now reported at an unprecedented speed due to the recent development of automated vulnerability hunting tools. However, fixing vulnerabilities still mainly depends on programmers' manual efforts. Developers need to deeply understand the vulnerability and try to affect the system's functions as little as possible. In this paper, with the advancement of Neural Machine Translation (NMT) techniques, we provide a novel approach called SeqTrans to exploit historical vulnerability fixes to provide suggestions and automatically fix the source code. To capture the contextual information around the vulnerable code, we propose to leverage data flow dependencies to construct code sequences and fed them into the state-of-the-art transformer model. The fine-tuning strategy has been introduced to overcome the small sample size problem. We evaluate SeqTrans on a dataset containing 1,282 commits that fix 624 vulnerabilities in 205 Java projects. Results show that the accuracy of SeqTrans outperforms the latest techniques and achieves 23.3% in statement-level fix and 25.3% in CVE-level fix. In the meantime, we look deep inside the result and observe that NMT model performs very well in certain kinds of vulnerabilities like CWE-287 (Improper Authentication) and CWE-863 (Incorrect Authorization).
Fast and Incremental Loop Closure Detection with Deep Features and Proximity Graphs
Venue: arXiv cs.CV 2022
Year: 2022

In recent years, the robotics community has extensively examined methods concerning the place recognition task within the scope of simultaneous localization and mapping applications.This article proposes an appearance-based loop closure detection pipeline named ``FILD++" (Fast and Incremental Loop closure Detection).First, the system is fed by consecutive images and, via passing them twice through a single convolutional neural network, global and local deep features are extracted.Subsequently, a hierarchical navigable small-world graph incrementally constructs a visual database representing the robot's traversed path based on the computed global features.Finally, a query image, grabbed each time step, is set to retrieve similar locations on the traversed route.An image-to-image pairing follows, which exploits local features to evaluate the spatial information. Thus, in the proposed article, we propose a single network for global and local feature extraction in contrast to our previous work (FILD), while an exhaustive search for the verification process is adopted over the generated deep local features avoiding the utilization of hash codes. Exhaustive experiments on eleven publicly available datasets exhibit the system's high performance (achieving the highest recall score on eight of them) and low execution times (22.05 ms on average in New College, which is the largest one containing 52480 images) compared to other state-of-the-art approaches.
Rethinking the competition between detection and ReID in Multi-Object Tracking
Venue: arXiv cs.CV 2022
Year: 2022

Due to balanced accuracy and speed, one-shot models which jointly learn detection and identification embeddings, have drawn great attention in multi-object tracking (MOT). However, the inherent differences and relations between detection and re-identification (ReID) are unconsciously overlooked because of treating them as two isolated tasks in the one-shot tracking paradigm. This leads to inferior performance compared with existing two-stage methods. In this paper, we first dissect the reasoning process for these two tasks, which reveals that the competition between them inevitably would destroy task-dependent representations learning. To tackle this problem, we propose a novel reciprocal network (REN) with a self-relation and cross-relation design so that to impel each branch to better learn task-dependent representations. The proposed model aims to alleviate the deleterious tasks competition, meanwhile improve the cooperation between detection and ReID. Furthermore, we introduce a scale-aware attention network (SAAN) that prevents semantic level misalignment to improve the association capability of ID embeddings. By integrating the two delicately designed networks into a one-shot online MOT system, we construct a strong MOT tracker, namely CSTrack. Our tracker achieves the state-of-the-art performance on MOT16, MOT17 and MOT20 datasets, without other bells and whistles. Moreover, CSTrack is efficient and runs at 16.4 FPS on a single modern GPU, and its lightweight version even runs at 34.6 FPS. The complete code has been released at https://github.com/JudasDie/SOTS.
An analysis of the SIGMOD 2014 Programming Contest: Complex queries on the LDBC social network graph
Venue: arXiv cs.DB 2022
Year: 2022

This report contains an analysis of the queries defined in the SIGMOD 2014 Programming Contest. We first describe the data set, then present the queries, providing graphical illustrations for them and pointing out their caveats. Our intention is to document our lessons learnt and simplify the work of those who will attempt to create a solution to this contest. We also demonstrate the influence of this contest by listing followup works which used these queries as inspiration to design better algorithms or to define interesting graph queries.