OpenRaiser/Intern-Atlas huggingface dataset:
K-level Reasoning for Zero-Shot Coordination in Hanabi
Venue: arXiv cs.AI 2022
Year: 2022

The standard problem setting in cooperative multi-agent settings is self-play (SP), where the goal is to train a team of agents that works well together. However, optimal SP policies commonly contain arbitrary conventions ("handshakes") and are not compatible with other, independently trained agents or humans. This latter desiderata was recently formalized by Hu et al. 2020 as the zero-shot coordination (ZSC) setting and partially addressed with their Other-Play (OP) algorithm, which showed improved ZSC and human-AI performance in the card game Hanabi. OP assumes access to the symmetries of the environment and prevents agents from breaking these in a mutually incompatible way during training. However, as the authors point out, discovering symmetries for a given environment is a computationally hard problem. Instead, we show that through a simple adaption of k-level reasoning (KLR) Costa Gomes et al. 2006, synchronously training all levels, we can obtain competitive ZSC and ad-hoc teamplay performance in Hanabi, including when paired with a human-like proxy bot. We also introduce a new method, synchronous-k-level reasoning with a best response (SyKLRBR), which further improves performance on our synchronous KLR by co-training a best response.
Accelerated Probabilistic Marching Cubes by Deep Learning for Time-Varying Scalar Ensembles
Venue: arXiv cs.LG 2022
Year: 2022

Visualizing the uncertainty of ensemble simulations is challenging due to the large size and multivariate and temporal features of ensemble data sets. One popular approach to studying the uncertainty of ensembles is analyzing the positional uncertainty of the level sets. Probabilistic marching cubes is a technique that performs Monte Carlo sampling of multivariate Gaussian noise distributions for positional uncertainty visualization of level sets. However, the technique suffers from high computational time, making interactive visualization and analysis impossible to achieve. This paper introduces a deep-learning-based approach to learning the level-set uncertainty for two-dimensional ensemble data with a multivariate Gaussian noise assumption. We train the model using the first few time steps from time-varying ensemble data in our workflow. We demonstrate that our trained model accurately infers uncertainty in level sets for new time steps and is up to 170X faster than that of the original probabilistic model with serial computation and 10X faster than that of the original parallel computation.
Infinite families of cyclic and negacyclic codes supporting 3-designs
Venue: arXiv cs.IT 2022
Year: 2022

Interplay between coding theory and combinatorial $t$-designs has been a hot topic for many years for combinatorialists and coding theorists. Some infinite families of cyclic codes supporting infinite families of $3$-designs have been constructed in the past 50 years. However, no infinite family of negacyclic codes supporting an infinite family of $3$-designs has been reported in the literature. This is the main motivation of this paper. Let $q=p^m$, where $p$ is an odd prime and $m \geq 2$ is an integer. The objective of this paper is to present an infinite family of cyclic codes over $\gf(q)$ supporting an infinite family of $3$-designs and two infinite families of negacyclic codes over $\gf(q^2)$ supporting two infinite families of $3$-designs. The parameters and the weight distributions of these codes are determined. The subfield subcodes of these negacyclic codes over $\gf(q)$ are studied. Three infinite families of almost MDS codes are also presented. A constacyclic code over GF($4$) supporting a $4$-design and six open problems are also presented in this paper.
Lexicographic Ranking based on Minimal Winning Coalitions
Venue: arXiv cs.GT 2022
Year: 2022

In this paper, we consider the consistency of the desirability relation with the ranking of the players in a simple game provided by some well-known solutions, in particular the Public Good Index [14] and the criticality-based ranking [1]. We define a new ranking solution, the Lexicographic Ranking based on Minimal winning coalitions (LRM), strongly related to the Public Good Index being rooted in the minimal winning coalitions of the simple game, proving that it is monotonic with respect to the desirability relation [17], when it holds. A suitable characterization of the LRM solution is provided. Finally, we investigate the relation among the LRM solution and the criticality-based ranking, referring to the dual game.
A Comparison of Source Distribution and Result Overlap in Web Search Engines
Venue: arXiv cs.IR 2022
Year: 2022

When it comes to search engines, users generally prefer Google. Our study aims to find the differences between the results found in Google compared to other search engines. We compared the top 10 results from Google, Bing, DuckDuckGo, and Metager, using 3,537 queries generated from Google Trends from Germany and the US. Google displays more unique domains in the top results than its competitors. Wikipedia and news websites are the most popular sources overall. With some top sources dominating search results, the distribution of domains is also consistent across all search engines. The overlap between Google and Bing is always under 32%, while Metager has a higher overlap with Bing than DuckDuckGo, going up to 78%. This study shows that the use of another search engine, especially in addition to Google, provides a wider variety in sources and might lead the user to find new perspectives.
Modeling Multi-interest News Sequence for News Recommendation
Venue: arXiv cs.IR 2022
Year: 2022

A session-based news recommender system recommends the next news to a user by modeling the potential interests embedded in a sequence of news read/clicked by her/him in a session. Generally, a user's interests are diverse, namely there are multiple interests corresponding to different types of news, e.g., news of distinct topics, within a session. %Modeling such multiple interests is critical for precise news recommendation. However, most of existing methods typically overlook such important characteristic and thus fail to distinguish and model the potential multiple interests of a user, impeding accurate recommendation of the next piece of news. Therefore, this paper proposes multi-interest news sequence (MINS) model for news recommendation. In MINS, a news encoder based on self-attention is devised on learn an informative embedding for each piece of news, and then a novel parallel interest network is devised to extract the potential multiple interests embedded in the news sequence in preparation for the subsequent next-news recommendations. The experimental results on a real-world dataset demonstrate that our model can achieve better performance than the state-of-the-art compared models.
Feasibility of Inconspicuous GAN-generated Adversarial Patches against Object Detection
Venue: arXiv cs.CV 2022
Year: 2022

Standard approaches for adversarial patch generation lead to noisy conspicuous patterns, which are easily recognizable by humans. Recent research has proposed several approaches to generate naturalistic patches using generative adversarial networks (GANs), yet only a few of them were evaluated on the object detection use case. Moreover, the state of the art mostly focuses on suppressing a single large bounding box in input by overlapping it with the patch directly. Suppressing objects near the patch is a different, more complex task. In this work, we have evaluated the existing approaches to generate inconspicuous patches. We have adapted methods, originally developed for different computer vision tasks, to the object detection use case with YOLOv3 and the COCO dataset. We have evaluated two approaches to generate naturalistic patches: by incorporating patch generation into the GAN training process and by using the pretrained GAN. For both cases, we have assessed a trade-off between performance and naturalistic patch appearance. Our experiments have shown, that using a pre-trained GAN helps to gain realistic-looking patches while preserving the performance similar to conventional adversarial patches.
Diverse Human Motion Prediction via Gumbel-Softmax Sampling from an Auxiliary Space
Venue: arXiv cs.CV 2022
Year: 2022

Diverse human motion prediction aims at predicting multiple possible future pose sequences from a sequence of observed poses. Previous approaches usually employ deep generative networks to model the conditional distribution of data, and then randomly sample outcomes from the distribution. While different results can be obtained, they are usually the most likely ones which are not diverse enough. Recent work explicitly learns multiple modes of the conditional distribution via a deterministic network, which however can only cover a fixed number of modes within a limited range. In this paper, we propose a novel sampling strategy for sampling very diverse results from an imbalanced multimodal distribution learned by a deep generative model. Our method works by generating an auxiliary space and smartly making randomly sampling from the auxiliary space equivalent to the diverse sampling from the target distribution. We propose a simple yet effective network architecture that implements this novel sampling strategy, which incorporates a Gumbel-Softmax coefficient matrix sampling method and an aggressive diversity promoting hinge loss function. Extensive experiments demonstrate that our method significantly improves both the diversity and accuracy of the samplings compared with previous state-of-the-art sampling approaches. Code and pre-trained models are available at https://github.com/Droliven/diverse_sampling.
An Approach for Link Prediction in Directed Complex Networks based on Asymmetric Similarity-Popularity
Venue: arXiv cs.SI 2022
Year: 2022

Complex networks are graphs representing real-life systems that exhibit unique characteristics not found in purely regular or completely random graphs. The study of such systems is vital but challenging due to the complexity of the underlying processes. This task has nevertheless been made easier in recent decades thanks to the availability of large amounts of networked data. Link prediction in complex networks aims to estimate the likelihood that a link between two nodes is missing from the network. Links can be missing due to imperfections in data collection or simply because they are yet to appear. Discovering new relationships between entities in networked data has attracted researchers' attention in various domains such as sociology, computer science, physics, and biology. Most existing research focuses on link prediction in undirected complex networks. However, not all real-life systems can be faithfully represented as undirected networks. This simplifying assumption is often made when using link prediction algorithms but inevitably leads to loss of information about relations among nodes and degradation in prediction performance. This paper introduces a link prediction method designed explicitly for directed networks. It is based on the similarity-popularity paradigm, which has recently proven successful in undirected networks. The presented algorithms handle the asymmetry in node relationships by modeling it as asymmetry in similarity and popularity. Given the observed network topology, the algorithms approximate the hidden similarities as shortest path distances using edge weights that capture and factor out the links' asymmetry and nodes' popularity. The proposed approach is evaluated on real-life networks, and the experimental results demonstrate its effectiveness in predicting missing links across a broad spectrum of networked data types and sizes.
SATAn: Air-Gap Exfiltration Attack via Radio Signals From SATA Cables
Venue: arXiv cs.CR 2022
Year: 2022

This paper introduces a new type of attack on isolated, air-gapped workstations. Although air-gap computers have no wireless connectivity, we show that attackers can use the SATA cable as a wireless antenna to transfer radio signals at the 6 GHz frequency band. The Serial ATA (SATA) is a bus interface widely used in modern computers and connects the host bus to mass storage devices such as hard disk drives, optical drives, and solid-state drives. The prevalence of the SATA interface makes this attack highly available to attackers in a wide range of computer systems and IT environments. We discuss related work on this topic and provide technical background. We show the design of the transmitter and receiver and present the implementation of these components. We also demonstrate the attack on different computers and provide the evaluation. The results show that attackers can use the SATA cable to transfer a brief amount of sensitive information from highly secured, air-gap computers wirelessly to a nearby receiver. Furthermore, we show that the attack can operate from user mode, is effective even from inside a Virtual Machine (VM), and can successfully work with other running workloads in the background. Finally, we discuss defense and mitigation techniques for this new air-gap attack.
GopCaml: A Structural Editor for OCaml
Venue: arXiv cs.PL 2022
Year: 2022

This talk presents Gopcaml-mode, the first structural editing plugin for OCaml. We will give a tour of the main plugin features, discussing the plugin's internal design and its integration with existing OCaml and GNU Emacs toolchains.
A tight quasi-polynomial bound for Global Label Min-Cut
Venue: arXiv cs.DS 2022
Year: 2022

We study a generalization of the classic Global Min-Cut problem, called Global Label Min-Cut (or sometimes Global Hedge Min-Cut): the edges of the input (multi)graph are labeled (or partitioned into color classes or hedges), and removing all edges of the same label (color or from the same hedge) costs one. The problem asks to disconnect the graph at minimum cost. While the $st$-cut version of the problem is known to be NP-hard, the above global cut version is known to admit a quasi-polynomial randomized $n^{O(\log \mathrm{OPT})}$-time algorithm due to Ghaffari, Karger, and Panigrahi [SODA 2017]. They consider this as ``strong evidence that this problem is in P''. We show that this is actually not the case. We complete the study of the complexity of the Global Label Min-Cut problem by showing that the quasi-polynomial running time is probably optimal: We show that the existence of an algorithm with running time $(np)^{o(\log n/ (\log \log n)^2)}$ would contradict the Exponential Time Hypothesis, where $n$ is the number of vertices, and $p$ is the number of labels in the input. The key step for the lower bound is a proof that Global Label Min-Cut is W[1]-hard when parameterized by the number of uncut labels. In other words, the problem is difficult in the regime where almost all labels need to be cut to disconnect the graph. To turn this lower bound into a quasi-polynomial-time lower bound, we also needed to revisit the framework due to Marx [Theory Comput. 2010] of proving lower bounds assuming Exponential Time Hypothesis through the Subgraph Isomorphism problem parameterized by the number of edges of the pattern. Here, we provide an alternative simplified proof of the hardness of this problem that is more versatile with respect to the choice of the regimes of the parameters.
Fixed-Parameter Tractability of Maximum Colored Path and Beyond
Venue: arXiv cs.DS 2022
Year: 2022

We introduce a general method for obtaining fixed-parameter algorithms for problems about finding paths in undirected graphs, where the length of the path could be unbounded in the parameter. The first application of our method is as follows. We give a randomized algorithm, that given a colored $n$-vertex undirected graph, vertices $s$ and $t$, and an integer $k$, finds an $(s,t)$-path containing at least $k$ different colors in time $2^k n^{O(1)}$. This is the first FPT algorithm for this problem, and it generalizes the algorithm of Björklund, Husfeldt, and Taslaman [SODA 2012] on finding a path through $k$ specified vertices. It also implies the first $2^k n^{O(1)}$ time algorithm for finding an $(s,t)$-path of length at least $k$. Our method yields FPT algorithms for even more general problems. For example, we consider the problem where the input consists of an $n$-vertex undirected graph $G$, a matroid $M$ whose elements correspond to the vertices of $G$ and which is represented over a finite field of order $q$, a positive integer weight function on the vertices of $G$, two sets of vertices $S,T \subseteq V(G)$, and integers $p,k,w$, and the task is to find $p$ vertex-disjoint paths from $S$ to $T$ so that the union of the vertices of these paths contains an independent set of $M$ of cardinality $k$ and weight $w$, while minimizing the sum of the lengths of the paths. We give a $2^{p+O(k^2 \log (q+k))} n^{O(1)} w$ time randomized algorithm for this problem.
A Consensus Algorithm Based on Risk Assessment Model for Permissioned Blockchain
Venue: arXiv cs.DC 2022
Year: 2022

Blockchain technology enables stakeholders to conduct trusted data sharing and exchange without a trusted centralized institution. These features make blockchain applications attractive to enhance trustworthiness in very different contexts. Due to unique design concepts and outstanding performance, blockchain has become a popular research topic in industry and academia in recent years. Every participant is anonymous in a permissionless blockchain represented by cryptocurrency applications such as Bitcoin. In this situation, some special incentive mechanisms are applied to permissionless blockchain, such as mined native cryptocurrency to solve the trust issues of permissionless blockchain. In many use cases, permissionless blockchain has bottlenecks in transaction throughput performance, which restricts further application in the real world. A permissioned blockchain can reach a consensus among a group of entities that do not establish an entire trust relationship. Unlike permissionless blockchains, the participants must be identified in permissioned blockchains. By relying on the traditional crash fault-tolerant consensus protocols, permissioned blockchains can achieve high transaction throughput and low latency without sacrificing security. However, how to balance the security and consensus efficiency is still the issue that needs to be solved urgently in permissioned blockchains. As the core module of blockchain technology, the consensus algorithm plays a vital role in the performance of the blockchain system. Thus, this paper proposes a new consensus algorithm for permissioned blockchain, the Risk Assessment-based Consensus protocol (RAC), combined with the decentralized design concept and the risk-node assessment mechanism to address the unbalance issues of performance in speed, scalability, and security.
Matching Patterns with Variables Under Edit Distance
Venue: arXiv cs.DS 2022
Year: 2022

A pattern $α$ is a string of variables and terminal letters. We say that $α$ matches a word $w$, consisting only of terminal letters, if $w$ can be obtained by replacing the variables of $α$ by terminal words. The matching problem, i.e., deciding whether a given pattern matches a given word, was heavily investigated: it is NP-complete in general, but can be solved efficiently for classes of patterns with restricted structure. If we are interested in what is the minimum Hamming distance between $w$ and any word $u$ obtained by replacing the variables of $α$ by terminal words (so matching under Hamming distance), one can devise efficient algorithms and matching conditional lower bounds for the class of regular patterns (in which no variable occurs twice), as well as for classes of patterns where we allow unbounded repetitions of variables, but restrict the structure of the pattern, i.e., the way the occurrences of different variables can be interleaved. Moreover, under Hamming distance, if a variable occurs more than once and its occurrences can be interleaved arbitrarily with those of other variables, even if each of these occurs just once, the matching problem is intractable. In this paper, we consider the problem of matching patterns with variables under edit distance. We still obtain efficient algorithms and matching conditional lower bounds for the class of regular patterns, but show that the problem becomes, in this case, intractable already for unary patterns, consisting of repeated occurrences of a single variable interleaved with terminals.
The Mechanical Neural Network(MNN) -- A physical implementation of a multilayer perceptron for education and hands-on experimentation
Venue: arXiv cs.LG 2022
Year: 2022

In this paper the Mechanical Neural Network(MNN) is introduced, a physical implementation of a multilayer perceptron(MLP) with ReLU activation functions, two input neurons, four hidden neurons and two output neurons. This physical model of a MLP is used in education to give a hands on experience and allow students to experience the effect of changing the parameters of the network on the output. Neurons are small wooden levers which are connected by threads. Students can adapt the weights between the neurons by moving the clamps connecting a neuron via a thread to the next. The MNN can model real valued functions and logical operators including XOR.
Explainable Sparse Knowledge Graph Completion via High-order Graph Reasoning Network
Venue: arXiv cs.LG 2022
Year: 2022

Knowledge Graphs (KGs) are becoming increasingly essential infrastructures in many applications while suffering from incompleteness issues. The KG completion task (KGC) automatically predicts missing facts based on an incomplete KG. However, existing methods perform unsatisfactorily in real-world scenarios. On the one hand, their performance will dramatically degrade along with the increasing sparsity of KGs. On the other hand, the inference procedure for prediction is an untrustworthy black box. This paper proposes a novel explainable model for sparse KGC, compositing high-order reasoning into a graph convolutional network, namely HoGRN. It can not only improve the generalization ability to mitigate the information insufficiency issue but also provide interpretability while maintaining the model's effectiveness and efficiency. There are two main components that are seamlessly integrated for joint optimization. First, the high-order reasoning component learns high-quality relation representations by capturing endogenous correlation among relations. This can reflect logical rules to justify a broader of missing facts. Second, the entity updating component leverages a weight-free Graph Convolutional Network (GCN) to efficiently model KG structures with interpretability. Unlike conventional methods, we conduct entity aggregation and design composition-based attention in the relational space without additional parameters. The lightweight design makes HoGRN better suitable for sparse settings. For evaluation, we have conducted extensive experiments-the results of HoGRN on several sparse KGs present impressive improvements (9% MRR gain on average). Further ablation and case studies demonstrate the effectiveness of the main components. Our codes will be released upon acceptance.
Sparse Relational Reasoning with Object-Centric Representations
Venue: arXiv cs.LG 2022
Year: 2022

We investigate the composability of soft-rules learned by relational neural architectures when operating over object-centric (slot-based) representations, under a variety of sparsity-inducing constraints. We find that increasing sparsity, especially on features, improves the performance of some models and leads to simpler relations. Additionally, we observe that object-centric representations can be detrimental when not all objects are fully captured; a failure mode to which CNNs are less prone. These findings demonstrate the trade-offs between interpretability and performance, even for models designed to tackle relational tasks.