OpenRaiser/Intern-Atlas huggingface dataset:
Ultrafast Distributed Coloring of High Degree Graphs
Venue: arXiv cs.DC 2021
Year: 2021

We give a new randomized distributed algorithm for the $Δ+1$-list coloring problem. The algorithm and its analysis dramatically simplify the previous best result known of Chang, Li, and Pettie [SICOMP 2020]. This allows for numerous refinements, and in particular, we can color all $n$-node graphs of maximum degree $Δ\ge \log^{2+Ω(1)} n$ in $O(\log^* n)$ rounds. The algorithm works in the CONGEST model, i.e., it uses only $O(\log n)$ bits per message for communication. On low-degree graphs, the algorithm shatters the graph into components of size $\operatorname{poly}(\log n)$ in $O(\log^* Δ)$ rounds, showing that the randomized complexity of $Δ+1$-list coloring in CONGEST depends inherently on the deterministic complexity of related coloring problems.
ppsim: A software package for efficiently simulating and visualizing population protocols
Venue: arXiv cs.DS 2021
Year: 2021

We introduce ppsim, a software package for efficiently simulating population protocols, a widely-studied subclass of chemical reaction networks (CRNs) in which all reactions have two reactants and two products. Each step in the dynamics involves picking a uniform random pair from a population of $n$ molecules to collide and have a (potentially null) reaction. In a recent breakthrough, Berenbrink, Hammer, Kaaser, Meyer, Penschuck, and Tran [ESA 2020] discovered a population protocol simulation algorithm quadratically faster than the naive algorithm, simulating $Θ(\sqrt{n})$ reactions in *constant* time (independently of $n$, though the time scales with the number of species), while preserving the *exact* stochastic dynamics. ppsim implements this algorithm, with a tightly optimized Cython implementation that can exactly simulate hundreds of billions of reactions in seconds. It dynamically switches to the CRN Gillespie algorithm for efficiency gains when the number of applicable reactions in a configuration becomes small. As a Python library, ppsim also includes many useful tools for data visualization in Jupyter notebooks, allowing robust visualization of time dynamics such as histogram plots at time snapshots and averaging repeated trials. Finally, we give a framework that takes any CRN with only bimolecular (2 reactant, 2 product) or unimolecular (1 reactant, 1 product) reactions, with arbitrary rate constants, and compiles it into a continuous-time population protocol. This lets ppsim exactly sample from the chemical master equation (unlike approximate heuristics such as tau-leaping or LNA), while achieving asymptotic gains in running time. In linked Jupyter notebooks, we demonstrate the efficacy of the tool on some protocols of interest in molecular programming, including the approximate majority CRN and CRN models of DNA strand displacement reactions.
Speech2Slot: An End-to-End Knowledge-based Slot Filling from Speech
Venue: arXiv cs.CL 2021
Year: 2021

In contrast to conventional pipeline Spoken Language Understanding (SLU) which consists of automatic speech recognition (ASR) and natural language understanding (NLU), end-to-end SLU infers the semantic meaning directly from speech and overcomes the error propagation caused by ASR. End-to-end slot filling (SF) from speech is an essential component of end-to-end SLU, and is usually regarded as a sequence-to-sequence generation problem, heavily relied on the performance of language model of ASR. However, it is hard to generate a correct slot when the slot is out-of-vovabulary (OOV) in training data, especially when a slot is an anti-linguistic entity without grammatical rule. Inspired by object detection in computer vision that is to detect the object from an image, we consider SF as the task of slot detection from speech. In this paper, we formulate the SF task as a matching task and propose an end-to-end knowledge-based SF model, named Speech-to-Slot (Speech2Slot), to leverage knowledge to detect the boundary of a slot from the speech. We also release a large-scale dataset of Chinese speech for slot filling, containing more than 830,000 samples. The experiments show that our approach is markedly superior to the conventional pipeline SLU approach, and outperforms the state-of-the-art end-to-end SF approach with 12.51% accuracy improvement.
Recurrent Neural Networks to automate Quality assessment of Software Requirements
Venue: arXiv cs.SE 2021
Year: 2021

Many problems related to the quality of requirements arise during elicitation and specification activities since they are written in natural language. The flexibility and inherent nature of language make requirements prone to inconsistencies, redundancies, and ambiguities, and consequently, this influences negatively the later phases of the software life cycle. To address this problem, this paper proposes an innovative approach that combines natural language processing techniques and recurrent neural networks to automatically assess the quality of software requirements. Initially, the analysis of singular, complete, correct, and appropriate quality properties defined in the IEEE 29148: 2018 standard is addressed. The proposed neural models are trained with a data set composed of 1000 software requirements. The proposal provides an average accuracy of 75%. These promising results were a motivation to explore its application in the evaluation of other quality properties
Unpacking the Expressed Consequences of AI Research in Broader Impact Statements
Venue: arXiv cs.CY 2021
Year: 2021

The computer science research community and the broader public have become increasingly aware of negative consequences of algorithmic systems. In response, the top-tier Neural Information Processing Systems (NeurIPS) conference for machine learning and artificial intelligence research required that authors include a statement of broader impact to reflect on potential positive and negative consequences of their work. We present the results of a qualitative thematic analysis of a sample of statements written for the 2020 conference. The themes we identify broadly fall into categories related to how consequences are expressed (e.g., valence, specificity, uncertainty), areas of impacts expressed (e.g., bias, the environment, labor, privacy), and researchers' recommendations for mitigating negative consequences in the future. In light of our results, we offer perspectives on how the broader impact statement can be implemented in future iterations to better align with potential goals.
Transfer-Meta Framework for Cross-domain Recommendation to Cold-Start Users
Venue: arXiv cs.IR 2021
Year: 2021

Cold-start problems are enormous challenges in practical recommender systems. One promising solution for this problem is cross-domain recommendation (CDR) which leverages rich information from an auxiliary (source) domain to improve the performance of recommender system in the target domain. In these CDR approaches, the family of Embedding and Mapping methods for CDR (EMCDR) is very effective, which explicitly learn a mapping function from source embeddings to target embeddings with overlapping users. However, these approaches suffer from one serious problem: the mapping function is only learned on limited overlapping users, and the function would be biased to the limited overlapping users, which leads to unsatisfying generalization ability and degrades the performance on cold-start users in the target domain. With the advantage of meta learning which has good generalization ability to novel tasks, we propose a transfer-meta framework for CDR (TMCDR) which has a transfer stage and a meta stage. In the transfer (pre-training) stage, a source model and a target model are trained on source and target domains, respectively. In the meta stage, a task-oriented meta network is learned to implicitly transform the user embedding in the source domain to the target feature space. In addition, the TMCDR is a general framework that can be applied upon various base models, e.g., MF, BPR, CML. By utilizing data from Amazon and Douban, we conduct extensive experiments on 6 cross-domain tasks to demonstrate the superior performance and compatibility of TMCDR.
Temporal graph-based approach for behavioural entity classification
Venue: arXiv cs.LG 2021
Year: 2021

Graph-based analyses have gained a lot of relevance in the past years due to their high potential in describing complex systems by detailing the actors involved, their relations and their behaviours. Nevertheless, in scenarios where these aspects are evolving over time, it is not easy to extract valuable information or to characterize correctly all the actors. In this study, a two phased approach for exploiting the potential of graph structures in the cybersecurity domain is presented. The main idea is to convert a network classification problem into a graph-based behavioural one. We extract these graph structures that can represent the evolution of both normal and attack entities and apply a temporal dissection approach in order to highlight their micro-dynamics. Further, three clustering techniques are applied to the normal entities in order to aggregate similar behaviours, mitigate the imbalance problem and reduce noisy data. Our approach suggests the implementation of two promising deep learning paradigms for entity classification based on Graph Convolutional Networks.
Testing Triangle Freeness in the General Model in Graphs with Arboricity $O(\sqrt{n})$
Venue: arXiv cs.DS 2021
Year: 2021

We study the problem of testing triangle freeness in the general graph model. This problem was first studied in the general graph model by Alon et al. (SIAM J. Discret. Math. 2008) who provided both lower bounds and upper bounds that depend on the number of vertices and the average degree of the graph. Their bounds are tight only when $d_{\rm max} = O(d)$ and $\bar{d} \leq \sqrt{n}$ or when $\bar{d} = Θ(1)$, where $d_{\rm max}$ denotes the maximum degree and $\bar{d}$ denotes the average degree of the graph. In this paper we provide bounds that depend on the arboricity of the graph and the average degree. As in Alon et al., the parameters of our tester is the number of vertices, $n$, the number of edges, $m$, and the proximity parameter $ε$ (the arboricity of the graph is not a parameter of the algorithm). The query complexity of our tester is $\tilde{O}(Γ/\bar{d} + Γ)\cdot poly(1/ε)$ on expectation, where $Γ$ denotes the arboricity of the input graph (we use $\tilde{O}(\cdot)$ to suppress $O(\log \log n)$ factors). We show that for graphs with arboricity $O(\sqrt{n})$ this upper bound is tight in the following sense. For any $Γ\in [s]$ where $s= Θ(\sqrt{n})$ there exists a family of graphs with arboricity $Γ$ and average degree $\bar{d}$ such that $Ω(Γ/\bar{d} + Γ)$ queries are required for testing triangle freeness on this family of graphs. Moreover, this lower bound holds for any such $Γ$ and for a large range of feasible average degrees.
Optimal Transmit Strategy for Multi-user MIMO WPT Systems With Non-linear Energy Harvesters
Venue: arXiv cs.IT 2021
Year: 2021

In this paper, we study multi-user multi-antenna wireless power transfer (WPT) systems, where each antenna at the energy harvesting (EH) nodes is connected to a dedicated non-linear rectifier. We propose an optimal transmit strategy which maximizes a weighted sum of the average harvested powers at the EH nodes under a constraint on the power budget of the transmitter. First, for multiple-input single-output (MISO) WPT systems, we show that it is optimal to transmit scalar symbols with an arbitrary phase and an amplitude, whose probability density function (pdf) has at most two mass points, using maximum ratio transmission (MRT) beamforming. Then, we prove that for single-input multiple-output (SIMO) WPT systems, the optimal transmit symbol amplitudes are discrete random variables, whose pdf also has no more than two mass points. For general multi-user MIMO WPT systems, we show that the optimal transmit strategy involves scalar unit-norm symbols with arbitrary phase and at most two beamforming vectors. In order to determine these vectors, we formulate a non-convex optimization problem and obtain an optimal solution based on monotonic optimization. Since the computational complexity of the optimal solution is high, we also propose a low-complexity iterative algorithm to obtain a suboptimal solution, which achieves nearly optimal performance. Our simulation results reveal that the proposed transmit strategy for multi-user MIMO WPT systems outperforms two baseline schemes, which are based on a linear EH model and a single beamforming vector, respectively. For a given transmit power budget, we show that the harvested power saturates when increasing the number of transmit antennas. Finally, we observe that the harvested power region spanned by multiple EH nodes is convex and the power harvested at one EH node can be traded for a higher harvested power at the other nodes.
What Will the Future of UAV Cellular Communications Be? A Flight from 5G to 6G
Venue: arXiv cs.IT 2021
Year: 2021

What will the future of UAV cellular communications be? In this tutorial article, we address such a compelling yet difficult question by embarking on a journey from 5G to 6G and sharing a large number of realistic case studies supported by original results. We start by overviewing the status quo on UAV communications from an industrial standpoint, providing fresh updates from the 3GPP and detailing new 5G NR features in support of aerial devices. We then show the potential and the limitations of such features. In particular, we demonstrate how sub-6 GHz massive MIMO can successfully tackle cell selection and interference challenges, we showcase encouraging mmWave coverage evaluations in both urban and suburban/rural settings, and we examine the peculiarities of direct device-to-device communications in the sky. Moving on, we sneak a peek at next-generation UAV communications, listing some of the use cases envisioned for the 2030s. We identify the most promising 6G enablers for UAV communication, those expected to take the performance and reliability to the next level. For each of these disruptive new paradigms (non-terrestrial networks, cell-free architectures, artificial intelligence, reconfigurable intelligent surfaces, and THz communications), we gauge the prospective benefits for UAVs and discuss the main technological hurdles that stand in the way. All along, we distil our numerous findings into essential takeaways, and we identify key open problems worthy of further study.
Video-based Analysis of Soccer Matches
Venue: arXiv cs.CV 2021
Year: 2021

With the increasingly detailed investigation of game play and tactics in invasive team sports such as soccer, it becomes ever more important to present causes, actions and findings in a meaningful manner. Visualizations, especially when augmenting relevant information directly inside a video recording of a match, can significantly improve and simplify soccer match preparation and tactic planning. However, while many visualization techniques for soccer have been developed in recent years, few have been directly applied to the video-based analysis of soccer matches. This paper provides a comprehensive overview and categorization of the methods developed for the video-based visual analysis of soccer matches. While identifying the advantages and disadvantages of the individual approaches, we identify and discuss open research questions, soon enabling analysts to develop winning strategies more efficiently, do rapid failure analysis or identify weaknesses in opposing teams.
Consistent Multiple Graph Embedding for Multi-View Clustering
Venue: arXiv cs.CV 2021
Year: 2021

Graph-based multi-view clustering aiming to obtain a partition of data across multiple views, has received considerable attention in recent years. Although great efforts have been made for graph-based multi-view clustering, it remains a challenge to fuse characteristics from various views to learn a common representation for clustering. In this paper, we propose a novel Consistent Multiple Graph Embedding Clustering framework(CMGEC). Specifically, a multiple graph auto-encoder(M-GAE) is designed to flexibly encode the complementary information of multi-view data using a multi-graph attention fusion encoder. To guide the learned common representation maintaining the similarity of the neighboring characteristics in each view, a Multi-view Mutual Information Maximization module(MMIM) is introduced. Furthermore, a graph fusion network(GFN) is devised to explore the relationship among graphs from different views and provide a common consensus graph needed in M-GAE. By jointly training these models, the common latent representation can be obtained which encodes more complementary information from multiple views and depicts data more comprehensively. Experiments on three types of multi-view datasets demonstrate CMGEC outperforms the state-of-the-art clustering methods.
Graph-based Neural Architecture Search with Operation Embeddings
Venue: arXiv cs.LG 2021
Year: 2021

Neural Architecture Search (NAS) has recently gained increased attention, as a class of approaches that automatically searches in an input space of network architectures. A crucial part of the NAS pipeline is the encoding of the architecture that consists of the applied computational blocks, namely the operations and the links between them. Most of the existing approaches either fail to capture the structural properties of the architectures or use hand-engineered vector to encode the operator information. In this paper, we propose the replacement of fixed operator encoding with learnable representations in the optimization process. This approach, which effectively captures the relations of different operations, leads to smoother and more accurate representations of the architectures and consequently to improved performance of the end task. Our extensive evaluation in ENAS benchmark demonstrates the effectiveness of the proposed operation embeddings to the generation of highly accurate models, achieving state-of-the-art performance. Finally, our method produces top-performing architectures that share similar operation and graph patterns, highlighting a strong correlation between the structural properties of the architecture and its performance.
Hierarchical RNNs-Based Transformers MADDPG for Mixed Cooperative-Competitive Environments
Venue: arXiv cs.LG 2021
Year: 2021

At present, attention mechanism has been widely applied to the fields of deep learning models. Structural models that based on attention mechanism can not only record the relationships between features position, but also can measure the importance of different features based on their weights. By establishing dynamically weighted parameters for choosing relevant and irrelevant features, the key information can be strengthened, and the irrelevant information can be weakened. Therefore, the efficiency of deep learning algorithms can be significantly elevated and improved. Although transformers have been performed very well in many fields including reinforcement learning, there are still many problems and applications can be solved and made with transformers within this area. MARL (known as Multi-Agent Reinforcement Learning) can be recognized as a set of independent agents trying to adapt and learn through their way to reach the goal. In order to emphasize the relationship between each MDP decision in a certain time period, we applied the hierarchical coding method and validated the effectiveness of this method. This paper proposed a hierarchical transformers MADDPG based on RNN which we call it Hierarchical RNNs-Based Transformers MADDPG(HRTMADDPG). It consists of a lower level encoder based on RNNs that encodes multiple step sizes in each time sequence, and it also consists of an upper sequence level encoder based on transformer for learning the correlations between multiple sequences so that we can capture the causal relationship between sub-time sequences and make HRTMADDPG more efficient.
Using Deep Neural Networks to Predict and Improve the Performance of Polar Codes
Venue: arXiv cs.LG 2021
Year: 2021

Polar codes can theoretically achieve very competitive Frame Error Rates. In practice, their performance may depend on the chosen decoding procedure, as well as other parameters of the communication system they are deployed upon. As a consequence, designing efficient polar codes for a specific context can quickly become challenging. In this paper, we introduce a methodology that consists in training deep neural networks to predict the frame error rate of polar codes based on their frozen bit construction sequence. We introduce an algorithm based on Projected Gradient Descent that leverages the gradient of the neural network function to generate promising frozen bit sequences. We showcase on generated datasets the ability of the proposed methodology to produce codes more efficient than those used to train the neural networks, even when the latter are selected among the most efficient ones.
You Are How (and Where) You Search? Comparative Analysis of Web Search Behaviour Using Web Tracking Data
Venue: arXiv cs.HC 2021
Year: 2021

We conduct a comparative analysis of desktop web search behaviour of users from Germany (n=558) and Switzerland (n=563) based on a combination of web tracking and survey data. We find that web search accounts for 13% of all desktop browsing, with the share being higher in Switzerland than in Germany. We find that in over 50% of cases users clicked on the first search result, with over 97% of all clicks being made on the first page of search outputs. Most users rely on Google when conducting searches, and users preferences for other engines are related to their demographics. We also test relationships between user demographics and daily number of searches, average share of search activities among tracked events by user as well as the tendency to click on higher- or lower-ranked results. We find differences in such relationships between the two countries that highlights the importance of comparative research in this domain. Further, we observe differences in the temporal patterns of web search use between women and men, marking the necessity of disaggregating data by gender in observational studies regarding online information behaviour.
Tensor-Train Recurrent Neural Networks for Interpretable Multi-Way Financial Forecasting
Venue: arXiv cs.LG 2021
Year: 2021

Recurrent Neural Networks (RNNs) represent the de facto standard machine learning tool for sequence modelling, owing to their expressive power and memory. However, when dealing with large dimensional data, the corresponding exponential increase in the number of parameters imposes a computational bottleneck. The necessity to equip RNNs with the ability to deal with the curse of dimensionality, such as through the parameter compression ability inherent to tensors, has led to the development of the Tensor-Train RNN (TT-RNN). Despite achieving promising results in many applications, the full potential of the TT-RNN is yet to be explored in the context of interpretable financial modelling, a notoriously challenging task characterized by multi-modal data with low signal-to-noise ratio. To address this issue, we investigate the potential of TT-RNN in the task of financial forecasting of currencies. We show, through the analysis of TT-factors, that the physical meaning underlying tensor decomposition, enables the TT-RNN model to aid the interpretability of results, thus mitigating the notorious "black-box" issue associated with neural networks. Furthermore, simulation results highlight the regularization power of TT decomposition, demonstrating the superior performance of TT-RNN over its uncompressed RNN counterpart and other tensor forecasting methods.