OpenRaiser/Intern-Atlas huggingface dataset:
FireCommander: An Interactive, Probabilistic Multi-agent Environment for Heterogeneous Robot Teams
Venue: arXiv cs.RO 2021
Year: 2021

The purpose of this tutorial is to help individuals use the \underline{FireCommander} game environment for research applications. The FireCommander is an interactive, probabilistic joint perception-action reconnaissance environment in which a composite team of agents (e.g., robots) cooperate to fight dynamic, propagating firespots (e.g., targets). In FireCommander game, a team of agents must be tasked to optimally deal with a wildfire situation in an environment with propagating fire areas and some facilities such as houses, hospitals, power stations, etc. The team of agents can accomplish their mission by first sensing (e.g., estimating fire states), communicating the sensed fire-information among each other and then taking action to put the firespots out based on the sensed information (e.g., dropping water on estimated fire locations). The FireCommander environment can be useful for research topics spanning a wide range of applications from Reinforcement Learning (RL) and Learning from Demonstration (LfD), to Coordination, Psychology, Human-Robot Interaction (HRI) and Teaming. There are four important facets of the FireCommander environment that overall, create a non-trivial game: (1) Complex Objectives: Multi-objective Stochastic Environment, (2)Probabilistic Environment: Agents' actions result in probabilistic performance, (3) Hidden Targets: Partially Observable Environment and, (4) Uni-task Robots: Perception-only and Action-only agents. The FireCommander environment is first-of-its-kind in terms of including Perception-only and Action-only agents for coordination. It is a general multi-purpose game that can be useful in a variety of combinatorial optimization problems and stochastic games, such as applications of Reinforcement Learning (RL), Learning from Demonstration (LfD) and Inverse RL (iRL).
Domain-specific Knowledge Graphs: A survey
Venue: arXiv cs.DB 2021
Year: 2021

Knowledge Graphs (KGs) have made a qualitative leap and effected a real revolution in knowledge representation. This is leveraged by the underlying structure of the KG which underpins a better comprehension, reasoning and interpretation of knowledge for both human and machine. Therefore, KGs continue to be used as the main means of tackling a plethora of real-life problems in various domains. However, there is no consensus in regard to a plausible and inclusive definition of a domain-specific KG. Further, in conjunction with several limitations and deficiencies, various domain-specific KG construction approaches are far from perfect. This survey is the first to offer a comprehensive definition of a domain-specific KG. Also, the paper presents a thorough review of the state-of-the-art approaches drawn from academic works relevant to seven domains of knowledge. An examination of current approaches reveals a range of limitations and deficiencies. At the same time, uncharted territories on the research map are highlighted to tackle extant issues in the literature and point to directions for future research.
A Dilated Residual Hierarchically Fashioned Segmentation Framework for Extracting Gleason Tissues and Grading Prostate Cancer from Whole Slide Images
Venue: arXiv cs.CV 2021
Year: 2021

Prostate cancer (PCa) is the second deadliest form of cancer in males, and it can be clinically graded by examining the structural representations of Gleason tissues. This paper proposes \RV{a new method} for segmenting the Gleason tissues \RV{(patch-wise) in order to grade PCa from the whole slide images (WSI).} Also, the proposed approach encompasses two main contributions: 1) A synergy of hybrid dilation factors and hierarchical decomposition of latent space representation for effective Gleason tissues extraction, and 2) A three-tiered loss function which can penalize different semantic segmentation models for accurately extracting the highly correlated patterns. In addition to this, the proposed framework has been extensively evaluated on a large-scale PCa dataset containing 10,516 whole slide scans (with around 71.7M patches), where it outperforms state-of-the-art schemes by 3.22% (in terms of mean intersection-over-union) for extracting the Gleason tissues and 6.91% (in terms of F1 score) for grading the progression of PCa.
ASAD: A Twitter-based Benchmark Arabic Sentiment Analysis Dataset
Venue: arXiv cs.CL 2021
Year: 2021

This paper provides a detailed description of a new Twitter-based benchmark dataset for Arabic Sentiment Analysis (ASAD), which is launched in a competition3, sponsored by KAUST for awarding 10000 USD, 5000 USD and 2000 USD to the first, second and third place winners, respectively. Compared to other publicly released Arabic datasets, ASAD is a large, high-quality annotated dataset(including 95K tweets), with three-class sentiment labels (positive, negative and neutral). We presents the details of the data collection process and annotation process. In addition, we implement several baseline models for the competition task and report the results as a reference for the participants to the competition.
Ant Colony Inspired Machine Learning Algorithm for Identifying and Emulating Virtual Sensors
Venue: arXiv cs.LG 2021
Year: 2021

The scale of systems employed in industrial environments demands a large number of sensors to facilitate meticulous monitoring and functioning. These requirements could potentially lead to inefficient system designs. The data coming from various sensors are often correlated due to the underlying relations in the system parameters that the sensors monitor. In theory, it should be possible to emulate the output of certain sensors based on other sensors. Tapping into such possibilities holds tremendous advantages in terms of reducing system design complexity. In order to identify the subset of sensors whose readings can be emulated, the sensors must be grouped into clusters. Complex systems generally have a large quantity of sensors that collect and store data over prolonged periods of time. This leads to the accumulation of massive amounts of data. In this paper we propose an end-to-end algorithmic solution, to realise virtual sensors in such systems. This algorithm splits the dataset into blocks and clusters each of them individually. It then fuses these clustering solutions to obtain a global solution using an Ant Colony inspired technique, FAC2T. Having grouped the sensors into clusters, we select representative sensors from each cluster. These sensors are retained in the system while the other sensors readings are emulated by applying supervised learning algorithms.
Constant-Time Dynamic Weight Approximation for Minimum Spanning Forest
Venue: arXiv cs.DS 2021
Year: 2021

We give two fully dynamic algorithms that maintain a $(1+\varepsilon)$-approximation of the weight $M$ of a minimum spanning forest (MSF) of an $n$-node graph $G$ with edges weights in $[1,W]$, for any $\varepsilon>0$. (1) Our deterministic algorithm takes $O({W^2 \log W}/{\varepsilon^3})$ worst-case update time, which is $O(1)$ if both $W$ and $\varepsilon$ are constants. Note that there is a lower bound by Patrascu and Demaine (SIAM J. Comput. 2006) which shows that it takes $Ω(\log n)$ time per operation to maintain the exact weight of an MSF that holds even in the unweighted case, i.e. for $W=1$. We further show that any deterministic data structure that dynamically maintains the $(1+\varepsilon)$-approximate weight of an MSF requires super constant time per operation, if $W\geq (\log n)^{ω_n(1)}$. (2) Our randomized (Monte-Carlo style) algorithm works with high probability and runs in worst-case $O(\log W/ \varepsilon^{4})$ update time if $W= O({(m^*)^{1/6}}/{\log^{2/3} n})$, where $m^*$ is the minimum number of edges in the graph throughout all the updates. It works even against an adaptive adversary. This implies a randomized algorithm with worst-case $o(\log n)$ update time, whenever $W=\min\{O((m^*)^{1/6}/\log^{2/3} n), 2^{o({\log n})}\}$ and $\varepsilon$ is constant. We complement this result by showing that for any constant $\varepsilon,α>0$ and $W=n^α$, any (randomized) data structure that dynamically maintains the weight of an MSF of a graph $G$ with edge weights in $[1,W]$ and $W = Ω(\varepsilon m^*)$ within a multiplicative factor of $(1+\varepsilon)$ takes $Ω(\log n)$ time per operation.
Risk-Aware Submodular Optimization for Multi-objective Travelling Salesperson Problem
Venue: arXiv cs.RO 2021
Year: 2021

We introduce a risk-aware multi-objective Traveling Salesperson Problem (TSP) variant, where the robot tour cost and tour reward have to be optimized simultaneously. The robot obtains reward along the edges in the graph. We study the case where the rewards and the costs exhibit diminishing marginal gains, i.e., are submodular. Unlike prior work, we focus on the scenario where the costs and the rewards are uncertain and seek to maximize the Conditional-Value-at-Risk (CVaR) metric of the submodular function. We propose a risk-aware greedy algorithm (RAGA) to find a bounded-approximation algorithm. The approximation algorithm runs in polynomial time and is within a constant factor of the optimal and an additive term that depends on the optimal solution. We use the submodular function's curvature to improve approximation results further and verify the algorithm's performance through simulations.
Site-to-Site Internet Traffic Control
Venue: arXiv cs.NI 2021
Year: 2021

Queues allow network operators to control traffic: where queues build, they can enforce scheduling and shaping policies. In the Internet today, however, there is a mismatch between where queues build and where control is most effectively enforced; queues build at bottleneck links that are often not under the control of the data sender. To resolve this mismatch, we propose a new kind of middlebox, called Bundler. Bundler uses a novel inner control loop between a sendbox (in the sender's site) and a receivebox (in the receiver's site) to determine the aggregate rate for the bundle, leaving the end-to-end connections and their control loops intact. Enforcing this sending rate ensures that bottleneck queues that would have built up from the bundle's packets now shift from the bottleneck to the sendbox. The sendbox then exercises control over its traffic by scheduling packets to achieve higher-level objectives. We have implemented Bundler in Linux and evaluated it with real-world and emulation experiments. We find that Bundler allows the sender-chosen policy to be effective: when configured to implement Stochastic Fairness Queueing (SFQ), it improves median flow completion time (FCT) by between 28% and 97% across various scenarios.
Pairwise Relations Discriminator for Unsupervised Raven's Progressive Matrices
Venue: arXiv cs.AI 2021
Year: 2021

The ability to hypothesise, develop abstract concepts based on concrete observations and apply these hypotheses to justify future actions has been paramount in human development. An existing line of research in outfitting intelligent machines with abstract reasoning capabilities revolves around the Raven's Progressive Matrices (RPM). There have been many breakthroughs in supervised approaches to solving RPM in recent years. However, this process requires external assistance, and thus it cannot be claimed that machines have achieved reasoning ability comparable to humans. Namely, humans can solve RPM problems without supervision or prior experience once the RPM rule that relations can only exist row/column-wise is properly introduced. In this paper, we introduce a pairwise relations discriminator (PRD), a technique to develop unsupervised models with sufficient reasoning abilities to tackle an RPM problem. PRD reframes the RPM problem into a relation comparison task, which we can solve without requiring the labelling of the RPM problem. We can identify the optimal candidate by adapting the application of PRD to the RPM problem. Our approach, the PRD, establishes a new state-of-the-art unsupervised learning benchmark with an accuracy of 55.9% on the I-RAVEN, presenting a significant improvement and a step forward in equipping machines with abstract reasoning.
Recent Advances on the Graph Isomorphism Problem
Venue: arXiv cs.DS 2021
Year: 2021

We give an overview of recent advances on the graph isomorphism problem. Our main focus will be on Babai's quasi-polynomial time isomorphism test and subsequent developments that led to the design of isomorphism algorithms with a quasi-polynomial parameterized running time of the from $n^{\text{polylog}(k)}$, where $k$ is a graph parameter such as the maximum degree. A second focus will be the combinatorial Weisfeiler-Leman algorithm.
On Computing Stable Extensions of Abstract Argumentation Frameworks
Venue: arXiv cs.DS 2021
Year: 2021

An \textit{abstract argumentation framework} ({\sc af} for short) is a directed graph $(A,R)$ where $A$ is a set of \textit{abstract arguments} and $R\subseteq A \times A$ is the \textit{attack} relation. Let $H=(A,R)$ be an {\sc af}, $S \subseteq A$ be a set of arguments and $S^+ = \{y \mid \exists x\in S \text{ with }(x,y)\in R\}$. Then, $S$ is a \textit{stable extension} in $H$ if and only if $S^+ = A\setminus S$. In this paper, we present a thorough, formal validation of a known backtracking algorithm for listing all stable extensions in a given {\sc af}.
Transforming Gaussian Processes With Normalizing Flows
Venue: arXiv cs.LG 2021
Year: 2021

Gaussian Processes (GPs) can be used as flexible, non-parametric function priors. Inspired by the growing body of work on Normalizing Flows, we enlarge this class of priors through a parametric invertible transformation that can be made input-dependent. Doing so also allows us to encode interpretable prior knowledge (e.g., boundedness constraints). We derive a variational approximation to the resulting Bayesian inference problem, which is as fast as stochastic variational GP regression (Hensman et al., 2013; Dezfouli and Bonilla,2015). This makes the model a computationally efficient alternative to other hierarchical extensions of GP priors (Lazaro-Gredilla,2012; Damianou and Lawrence, 2013). The resulting algorithm's computational and inferential performance is excellent, and we demonstrate this on a range of data sets. For example, even with only 5 inducing points and an input-dependent flow, our method is consistently competitive with a standard sparse GP fitted using 100 inducing points.
Near-Optimal Entrywise Sampling of Numerically Sparse Matrices
Venue: arXiv cs.DS 2021
Year: 2021

Many real-world data sets are sparse or almost sparse. One method to measure this for a matrix $A\in \mathbb{R}^{n\times n}$ is the \emph{numerical sparsity}, denoted $\mathsf{ns}(A)$, defined as the minimum $k\geq 1$ such that $\|a\|_1/\|a\|_2 \leq \sqrt{k}$ for every row and every column $a$ of $A$. This measure of $a$ is smooth and is clearly only smaller than the number of non-zeros in the row/column $a$. The seminal work of Achlioptas and McSherry [2007] has put forward the question of approximating an input matrix $A$ by entrywise sampling. More precisely, the goal is to quickly compute a sparse matrix $\tilde{A}$ satisfying $\|A - \tilde{A}\|_2 \leq ε\|A\|_2$ (i.e., additive spectral approximation) given an error parameter $ε>0$. The known schemes sample and rescale a small fraction of entries from $A$. We propose a scheme that sparsifies an almost-sparse matrix $A$ -- it produces a matrix $\tilde{A}$ with $O(ε^{-2}\mathsf{ns}(A) \cdot n\ln n)$ non-zero entries with high probability. We also prove that this upper bound on $\mathsf{nnz}(\tilde{A})$ is \emph{tight} up to logarithmic factors. Moreover, our upper bound improves when the spectrum of $A$ decays quickly (roughly replacing $n$ with the stable rank of $A$). Our scheme can be implemented in time $O(\mathsf{nnz}(A))$ when $\|A\|_2$ is given. Previously, a similar upper bound was obtained by Achlioptas et. al [2013] but only for a restricted class of inputs that does not even include symmetric or covariance matrices. Finally, we demonstrate two applications of these sampling techniques, to faster approximate matrix multiplication, and to ridge regression by using sparse preconditioners.
Learning unbiased group-wise registration (LUGR) and joint segmentation: evaluation on longitudinal diffusion MRI
Venue: arXiv cs.CV 2021
Year: 2021

Analysis of longitudinal changes in imaging studies often involves both segmentation of structures of interest and registration of multiple timeframes. The accuracy of such analysis could benefit from a tailored framework that jointly optimizes both tasks to fully exploit the information available in the longitudinal data. Most learning-based registration algorithms, including joint optimization approaches, currently suffer from bias due to selection of a fixed reference frame and only support pairwise transformations. We here propose an analytical framework based on an unbiased learning strategy for group-wise registration that simultaneously registers images to the mean space of a group to obtain consistent segmentations. We evaluate the proposed method on longitudinal analysis of a white matter tract in a brain MRI dataset with 2-3 time-points for 3249 individuals, i.e., 8045 images in total. The reproducibility of the method is evaluated on test-retest data from 97 individuals. The results confirm that the implicit reference image is an average of the input image. In addition, the proposed framework leads to consistent segmentations and significantly lower processing bias than that of a pair-wise fixed-reference approach. This processing bias is even smaller than those obtained when translating segmentations by only one voxel, which can be attributed to subtle numerical instabilities and interpolation. Therefore, we postulate that the proposed mean-space learning strategy could be widely applied to learning-based registration tasks. In addition, this group-wise framework introduces a novel way for learning-based longitudinal studies by direct construction of an unbiased within-subject template and allowing reliable and efficient analysis of spatio-temporal imaging biomarkers.
A Survey on Contact Tracing: the Latest Advancements and Challenges
Venue: arXiv cs.SI 2021
Year: 2021

Infectious diseases are caused by pathogenic microorganisms, such as bacteria, viruses, parasites or fungi, which can be spread, directly or indirectly, from one person to another. Infectious diseases pose a serious threat to human health, especially COVID-19 that has became a serious worldwide health concern since the end of 2019. Contact tracing is the process of identifying, assessing, and managing people who have been exposed to a disease to prevent its onward transmission. Contact tracing can help us better understand the transmission link of the virus, whereby better interrupting its transmission. Given the worldwide pandemic of COVID-19, contact tracing has become one of the most critical measures to effectively curb the spread of the virus. This paper presents a comprehensive survey on contact tracing, with a detailed coverage of the recent advancements the models, digital technologies, protocols and issues involved in contact tracing. The current challenges as well as future directions of contact tracing technologies are also presented.
BaFFLe: Backdoor detection via Feedback-based Federated Learning
Venue: arXiv cs.CR 2021
Year: 2021

Recent studies have shown that federated learning (FL) is vulnerable to poisoning attacks that inject a backdoor into the global model. These attacks are effective even when performed by a single client, and undetectable by most existing defensive techniques. In this paper, we propose Backdoor detection via Feedback-based Federated Learning (BAFFLE), a novel defense to secure FL against backdoor attacks. The core idea behind BAFFLE is to leverage data of multiple clients not only for training but also for uncovering model poisoning. We exploit the availability of diverse datasets at the various clients by incorporating a feedback loop into the FL process, to integrate the views of those clients when deciding whether a given model update is genuine or not. We show that this powerful construct can achieve very high detection rates against state-of-the-art backdoor attacks, even when relying on straightforward methods to validate the model. Through empirical evaluation using the CIFAR-10 and FEMNIST datasets, we show that by combining the feedback loop with a method that suspects poisoning attempts by assessing the per-class classification performance of the updated model, BAFFLE reliably detects state-of-the-art backdoor attacks with a detection accuracy of 100% and a false-positive rate below 5%. Moreover, we show that our solution can detect adaptive attacks aimed at bypassing the defense.
Two-timescale Beamforming Optimization for Intelligent Reflecting Surface Aided Multiuser Communication with QoS Constraints
Venue: arXiv cs.IT 2021
Year: 2021

Intelligent reflecting surface (IRS) is an emerging technology that is able to reconfigure the wireless channel via tunable passive signal reflection and thereby enhance the spectral and energy efficiency of wireless networks cost-effectively. In this paper, we study an IRS-aided multiuser multiple-input single-output (MISO) wireless system and adopt the two-timescale (TTS) transmission to reduce the signal processing complexity and channel training overhead as compared to the existing schemes based on the instantaneous channel state information (I-CSI), and at the same time, exploit the multiuser channel diversity in transmission scheduling. Specifically, the long-term passive beamforming is designed based on the statistical CSI (S-CSI) of all links, while the short-term active beamforming is designed to cater to the I-CSI of all users' reconfigured channels with optimized IRS phase shifts. We aim to minimize the average transmit power at the access point (AP), subject to the users' individual quality of service (QoS) constraints. The formulated stochastic optimization problem is non-convex and difficult to solve since the long-term and short-term design variables are complicatedly coupled in the QoS constraints. To tackle this problem, we propose an efficient algorithm, called the primal-dual decomposition based TTS joint active and passive beamforming (PDD-TJAPB), where the original problem is decomposed into a long-term problem and a family of short-term problems, and the deep unfolding technique is employed to extract gradient information from the short-term problems to construct a convex surrogate problem for the long-term problem. The proposed algorithm is proved to converge to a stationary solution of the original problem almost surely. Simulation results are presented which demonstrate the advantages and effectiveness of the proposed algorithm as compared to benchmark schemes.
Physical ZKP for Connected Spanning Subgraph: Applications to Bridges Puzzle and Other Problems
Venue: arXiv cs.CR 2021
Year: 2021

An undirected graph $G$ is known to both the prover $P$ and the verifier $V$, but only $P$ knows a subgraph $H$ of $G$. Without revealing any information about $H$, $P$ wants to convince $V$ that $H$ is a connected spanning subgraph of $G$, i.e. $H$ is connected and contains all vertices of $G$. In this paper, we propose an unconventional zero-knowledge proof protocol using a physical deck of cards, which enables $P$ to physically show that $H$ satisfies the condition without revealing it. We also show applications of this protocol to verify solutions of three well-known NP-complete problems: the Hamiltonian cycle problem, the maximum leaf spanning tree problem, and a popular logic puzzle called Bridges.
Consequences of APSP, triangle detection, and 3SUM hardness for separation between determinism and non-determinism
Venue: arXiv cs.CC 2021
Year: 2021

We present implications from the known conjectures like APSP, 3SUM and ETH in a form of a negated containment of a linear-time with a non-deterministic logarithmic-bit oracle in a respective deterministic bounded-time class They are different for different conjectures and they exhibit in particular the dependency on the input range parameters.