OpenRaiser/Intern-Atlas huggingface dataset:
Decremental Matching in General Graphs
Venue: arXiv cs.DS 2022
Year: 2022

We consider the problem of maintaining an approximate maximum integral matching in a dynamic graph $G$, while the adversary makes changes to the edges of the graph. The goal is to maintain a $(1+ε)$-approximate maximum matching for constant $ε>0$, while minimizing the update time. In the fully dynamic setting, where both edge insertion and deletions are allowed, Gupta and Peng (see \cite{GP13}) gave an algorithm for this problem with an update time of $O(\sqrt{m}/ε^2)$. Motivated by the fact that the $O_ε(\sqrt{m})$ barrier is hard to overcome (see Henzinger, Krinninger, Nanongkai, and Saranurak [HKNS15]); Kopelowitz, Pettie, and Porat [KPP16]), we study this problem in the \emph{decremental} model, where the adversary is only allowed to delete edges. Recently, Bernstein, Probst-Gutenberg, and Saranurak (see [BPT20]) gave an $O_ε(1)$ update time decremental algorithm for this problem in \emph{bipartite graphs}. However, beating $O(\sqrt{m})$ update time remained an open problem for \emph{general graphs}. In this paper, we bridge the gap between bipartite and general graphs, by giving an $O_ε(1)$ update time algorithm that maintains a $(1+ε)$-approximate maximum integral matching under adversarial deletions. Our algorithm is randomized, but works against an adaptive adversary. Together with the work of Grandoni, Leonardi, Sankowski, Schwiegelshohn, and Solomon [GLSSS19] who give an $O_ε(1)$ update time algorithm for general graphs in the \emph{incremental} (insertion-only) model, our result essentially completes the picture for partially dynamic matching.
An Empirical Survey on Long Document Summarization: Datasets, Models and Metrics
Venue: arXiv cs.CL 2022
Year: 2022

Long documents such as academic articles and business reports have been the standard format to detail out important issues and complicated subjects that require extra attention. An automatic summarization system that can effectively condense long documents into short and concise texts to encapsulate the most important information would thus be significant in aiding the reader's comprehension. Recently, with the advent of neural architectures, significant research efforts have been made to advance automatic text summarization systems, and numerous studies on the challenges of extending these systems to the long document domain have emerged. In this survey, we provide a comprehensive overview of the research on long document summarization and a systematic evaluation across the three principal components of its research setting: benchmark datasets, summarization models, and evaluation metrics. For each component, we organize the literature within the context of long document summarization and conduct an empirical analysis to broaden the perspective on current research progress. The empirical analysis includes a study on the intrinsic characteristics of benchmark datasets, a multi-dimensional analysis of summarization models, and a review of the summarization evaluation metrics. Based on the overall findings, we conclude by proposing possible directions for future exploration in this rapidly growing field.
NARRATE: A Normal Assisted Free-View Portrait Stylizer
Venue: arXiv cs.CV 2022
Year: 2022

In this work, we propose NARRATE, a novel pipeline that enables simultaneously editing portrait lighting and perspective in a photorealistic manner. As a hybrid neural-physical face model, NARRATE leverages complementary benefits of geometry-aware generative approaches and normal-assisted physical face models. In a nutshell, NARRATE first inverts the input portrait to a coarse geometry and employs neural rendering to generate images resembling the input, as well as producing convincing pose changes. However, inversion step introduces mismatch, bringing low-quality images with less facial details. As such, we further estimate portrait normal to enhance the coarse geometry, creating a high-fidelity physical face model. In particular, we fuse the neural and physical renderings to compensate for the imperfect inversion, resulting in both realistic and view-consistent novel perspective images. In relighting stage, previous works focus on single view portrait relighting but ignoring consistency between different perspectives as well, leading unstable and inconsistent lighting effects for view changes. We extend Total Relighting to fix this problem by unifying its multi-view input normal maps with the physical face model. NARRATE conducts relighting with consistent normal maps, imposing cross-view constraints and exhibiting stable and coherent illumination effects. We experimentally demonstrate that NARRATE achieves more photorealistic, reliable results over prior works. We further bridge NARRATE with animation and style transfer tools, supporting pose change, light change, facial animation, and style transfer, either separately or in combination, all at a photographic quality. We showcase vivid free-view facial animations as well as 3D-aware relightable stylization, which help facilitate various AR/VR applications like virtual cinematography, 3D video conferencing, and post-production.
One-off Events? An Empirical Study of Hackathon Code Creation and Reuse
Venue: arXiv cs.SE 2022
Year: 2022

Background: Hackathons have become popular events for teams to collaborate on projects and develop software prototypes. Most existing research focuses on activities during an event with limited attention to the evolution of the hackathon code. Aim: We aim to understand the evolution of code used in and created during hackathon events, with a particular focus on the code blobs, specifically, how frequently hackathon teams reuse pre-existing code, how much new code they develop, if that code gets reused afterward, and what factors affect reuse. Method: We collected information about 22,183 hackathon projects from DevPost and obtained related code blobs, authors, project characteristics, original author, code creation time, language, and size information from World of Code. We tracked the reuse of code blobs by identifying all commits containing blobs created during hackathons and identifying all projects that contain those commits. We also conducted a series of surveys in order to gain a deeper understanding of hackathon code evolution that we sent out to hackathon participants whose code was reused, whose code was not reused, and developers who reused some hackathon code. Result: 9.14% of the code blobs in hackathon repositories and 8% of the lines of code (LOC) are created during hackathons and around a third of the hackathon code gets reused in other projects by both blob count and LOC. The number of associated technologies and the number of participants in hackathons increase the reuse probability. Conclusion: The results of our study demonstrate hackathons are not always "one-off" events as common knowledge dictates and they can serve as a starting point for further studies in this area.
Algorithmic Meta-Theorems for Combinatorial Reconfiguration Revisited
Venue: arXiv cs.DS 2022
Year: 2022

Given a graph and two vertex sets satisfying a certain feasibility condition, a reconfiguration problem asks whether we can reach one vertex set from the other by repeating prescribed modification steps while maintaining feasibility. In this setting, Mouawad et al. [IPEC 2014] presented an algorithmic meta-theorem for reconfiguration problems that says if the feasibility can be expressed in monadic second-order logic (MSO), then the problem is fixed-parameter tractable parameterized by $\textrm{treewidth} + \ell$, where $\ell$ is the number of steps allowed to reach the target set. On the other hand, it is shown by Wrochna [J. Comput. Syst. Sci. 2018] that if $\ell$ is not part of the parameter, then the problem is PSPACE-complete even on graphs of bounded bandwidth. In this paper, we present the first algorithmic meta-theorems for the case where $\ell$ is not part of the parameter, using some structural graph parameters incomparable with bandwidth. We show that if the feasibility is defined in MSO, then the reconfiguration problem under the so-called token jumping rule is fixed-parameter tractable parameterized by neighborhood diversity. We also show that the problem is fixed-parameter tractable parameterized by $\textrm{treedepth} + k$, where $k$ is the size of sets being transformed. We finally complement the positive result for treedepth by showing that the problem is PSPACE-complete on forests of depth $3$.
Torque and velocity controllers to perform jumps with a humanoid robot: theory and implementation on the iCub robot
Venue: arXiv cs.RO 2022
Year: 2022

Jumping can be an effective way of locomotion to overcome small terrain gaps or obstacles. In this paper we propose two different approaches to perform jumps with a humanoid robot. Specifically, starting from a pre-defined CoM trajectory we develop the theory for a velocity controller and for a torque controller based on an optimization technique for the evaluation of the joints input. The controllers have been tested both in simulation and on the humanoid robot iCub. In simulation the robot was able to jump using both controllers, while the real system jumped with the velocity controller only. The results highlight the importance of controlling the centroidal angular momentum and they suggest that the joint performances, namely maximum power, of the legs and torso joints, and the low level control performances are fundamental to achieve acceptable results.
Guessing With Quadratic Differential Equations
Venue: arXiv cs.SC 2022
Year: 2022

By holonomic guessing, we denote the process of finding a linear differential equation with polynomial coefficients satisfied by the generating function of a sequence, for which only a few first terms are known. Holonomic guessing has been used in computer algebra for over three decades to demonstrate the value of the guess-and-prove paradigm in intuition processes preceding proofs, as propagated in The Art of Solving (Polya, 1978). Among the prominent packages used to perform guessing, one can cite the Maple Gfun package of Salvy and Zimmermann; the Mathematica GeneratingFunctions package of Mallinger; and the Sage ore_algebra package of Kauers, Jaroschek, and Johansson. We propose an approach that extends holonomic guessing by allowing the targeted differential equations to be of degree at most two. Consequently, it enables us to capture more generating functions than just holonomic functions. The corresponding recurrence equations are similar to known equations for the Bernoulli, Euler, and Bell numbers. As a result, our software finds the correct recurrence and differential equations for the generating functions of the up/down numbers (https://oeis.org/A000111), the evaluations of the zeta function at positive even integers, the Taylor coefficients of the Lambert W function, and many more. Our Maple implementation ($delta2guess$) is part of the FPS package which can be downloaded at http://www.mathematik.uni-kassel.de/~bteguia/FPS_webpage/FPS.htm
Collective Memory in the Digital Age
Venue: arXiv cs.CY 2022
Year: 2022

The digital transformation of our societies and in particular information and communication technologies have revolutionized how we generate, communicate, and acquire information. Collective memory as a core and unifying force in our societies has not been an exception among many societal concepts which have been revolutionized through digital transformation. In this chapter, we have distinguished between "the digitalized collective memory" and "collective memory in the digital age". In addition to discussing these two main concepts, we discuss how digital tools and trace data can open doorways into the study of collective memory that is formed inside and outside of the digital space.
An Empirical Study of Flaky Tests in JavaScript
Venue: arXiv cs.SE 2022
Year: 2022

Flaky tests (tests with non-deterministic outcomes) can be problematic for testing efficiency and software reliability. Flaky tests in test suites can also significantly delay software releases. There have been several studies that attempt to quantify the impact of test flakiness in different programming languages (e.g., Java and Python) and application domains (e.g., mobile and GUI-based). In this paper, we conduct an empirical study of the state of flaky tests in JavaScript. We investigate two aspects of flaky tests in JavaScript projects: the main causes of flaky tests in these projects and common fixing strategies. By analysing 452 commits from large, top-scoring JavaScript projects from GitHub, we found that flakiness caused by concurrency-related issues (e.g., async wait, race conditions or deadlocks) is the most dominant reason for test flakiness. The other top causes of flaky tests are operating system-specific (e.g., features that work on specific OS or OS versions) and network stability (e.g., internet availability or bad socket management). In terms of how flaky tests are dealt with, the majority of those flaky tests (>80%) are fixed to eliminate flaky behaviour and developers sometimes skip, quarantine or remove flaky tests.
A Formal Framework for Distributed Cyber-Physical Systems
Venue: arXiv cs.LO 2022
Year: 2022

Composition is an important feature of a specification language, as it enables the design of a complex system in terms of a product of its parts. Decomposition is equally important in order to reason about structural properties of a system. Usually, however, a system can be decomposed in more than one way, each optimizing for a different set of criteria. We extend an algebraic component-based model for cyber-physical systems to reason about decomposition. In this model, components compose using a family of algebraic products, and decompose, under some conditions, given a corresponding family of division operators. We use division to specify invariant of a system of components, and to model desirable updates. We apply our framework to design a cyber-physical system consisting of robots moving on a shared field, and identify desirable updates using our division operator.
Protea: Client Profiling within Federated Systems using Flower
Venue: arXiv cs.LG 2022
Year: 2022

Federated Learning (FL) has emerged as a prospective solution that facilitates the training of a high-performing centralised model without compromising the privacy of users. While successful, research is currently limited by the possibility of establishing a realistic large-scale FL system at the early stages of experimentation. Simulation can help accelerate this process. To facilitate efficient scalable FL simulation of heterogeneous clients, we design and implement Protea, a flexible and lightweight client profiling component within federated systems using the FL framework Flower. It allows automatically collecting system-level statistics and estimating the resources needed for each client, thus running the simulation in a resource-aware fashion. The results show that our design successfully increases parallelism for 1.66 $\times$ faster wall-clock time and 2.6$\times$ better GPU utilisation, which enables large-scale experiments on heterogeneous clients.
Identifying the Context Shift between Test Benchmarks and Production Data
Venue: arXiv cs.LG 2022
Year: 2022

Machine learning models are often brittle on production data despite achieving high accuracy on benchmark datasets. Benchmark datasets have traditionally served dual purposes: first, benchmarks offer a standard on which machine learning researchers can compare different methods, and second, benchmarks provide a model, albeit imperfect, of the real world. The incompleteness of test benchmarks (and the data upon which models are trained) hinder robustness in machine learning, enable shortcut learning, and leave models systematically prone to err on out-of-distribution and adversarially perturbed data. The mismatch between a single static benchmark dataset and a production dataset has traditionally been described as a dataset shift. In an effort to clarify how to address the mismatch between test benchmarks and production data, we introduce context shift to describe semantically meaningful changes in the underlying data generation process. Moreover, we identify three methods for addressing context shift that would otherwise lead to model prediction errors: first, we describe how human intuition and expert knowledge can identify semantically meaningful features upon which models systematically fail, second, we detail how dynamic benchmarking - with its focus on capturing the data generation process - can promote generalizability through corroboration, and third, we highlight that clarifying a model's limitations can reduce unexpected errors. Robust machine learning is focused on model performance beyond benchmarks, and as such, we consider three model organism domains - facial expression recognition, deepfake detection, and medical diagnosis - to highlight how implicit assumptions in benchmark tasks lead to errors in practice. By paying close attention to the role of context, researchers can design more comprehensive benchmarks, reduce context shift errors, and increase generalizability.
Enhancing Automated Software Traceability by Transfer Learning from Open-World Data
Venue: arXiv cs.SE 2022
Year: 2022

Software requirements traceability is a critical component of the software engineering process, enabling activities such as requirements validation, compliance verification, and safety assurance. However, the cost and effort of manually creating a complete set of trace links across natural language artifacts such as requirements, design, and test-cases can be prohibitively expensive. Researchers have therefore proposed automated link-generation solutions primarily based on information-retrieval (IR) techniques; however, these solutions have failed to deliver the accuracy needed for full adoption in industrial projects. Improvements can be achieved using deep-learning traceability models; however, their efficacy is impeded by the limited size and availability of project-level artifacts and links to serve as training data. In this paper, we address this problem by proposing and evaluating several deep-learning approaches for text-to-text traceability. Our method, named NLTrace, explores three transfer learning strategies that use datasets mined from open world platforms. Through pretraining Language Models (LMs) and leveraging adjacent tracing tasks, we demonstrate that NLTrace can significantly improve the performance of LM based trace models when training links are available. In such scenarios NLTrace outperforms the best performing classical IR method with an 188% improvement in F2 score and 94.01% in Mean Average Precision (MAP). It also outperforms the general LM based trace model by 7% and 23% for F2 and MAP respectively. In addition, NLTrace can adapt to low-resource tracing scenarios where other LM models can not. The knowledge learned from adjacent tasks enables NLTrace to outperform VSM models by 28% F2 on generation challenges when presented with a small number of training examples.
Representation Heterogeneity
Venue: arXiv cs.AI 2022
Year: 2022

Semantic Heterogeneity is conventionally understood as the existence of variance in the representation of a target reality when modelled, by independent parties, in different databases, schemas and/ or data. We argue that the mere encoding of variance, while being necessary, is not sufficient enough to deal with the problem of representational heterogeneity, given that it is also necessary to encode the unifying basis on which such variance is manifested. To that end, this paper introduces a notion of Representation Heterogeneity in terms of the co-occurrent notions of Representation Unity and Representation Diversity. We have representation unity when two heterogeneous representations model the same target reality, representation diversity otherwise. In turn, this paper also highlights how these two notions get instantiated across the two layers of any representation, i.e., Language and Knowledge.
Evaluating Error Bound for Physics-Informed Neural Networks on Linear Dynamical Systems
Venue: arXiv cs.NE 2022
Year: 2022

There have been extensive studies on solving differential equations using physics-informed neural networks. While this method has proven advantageous in many cases, a major criticism lies in its lack of analytical error bounds. Therefore, it is less credible than its traditional counterparts, such as the finite difference method. This paper shows that one can mathematically derive explicit error bounds for physics-informed neural networks trained on a class of linear systems of differential equations. More importantly, evaluating such error bounds only requires evaluating the differential equation residual infinity norm over the domain of interest. Our work shows a link between network residuals, which is known and used as loss function, and the absolute error of solution, which is generally unknown. Our approach is semi-phenomonological and independent of knowledge of the actual solution or the complexity or architecture of the network. Using the method of manufactured solution on linear ODEs and system of linear ODEs, we empirically verify the error evaluation algorithm and demonstrate that the actual error strictly lies within our derived bound.
Capacity Bounds for the Two-User IM/DD Interference Channel
Venue: arXiv cs.IT 2022
Year: 2022

This paper studies the capacity of the two-user intensity-modulation/direct-detection (IM/DD) interference channel (IC), which is relevant in the context of multi-user optical wireless communications. Despite some known single-letter capacity characterizations for general discrete-memoryless ICs, a computable capacity expression for the IM/DD IC is missing. In this paper, we provide tight and easily computable inner and outer bounds for a general two-user IM/DD IC under peak and average optical intensity constraints. The bounds enable characterizing the asymptotic sum-rate capacity in the strong and weak interference regimes, as well as the generalized degrees of freedom (GDoF) in the symmetric case. Using the obtained bounds, the GDoF of the IM/DD IC is shown to have a `W' shape similar to the Gaussian IC with power constraints. The obtained bounds are also evaluated numerically in different interference regimes to show their tightness, and used to study the performance of on-chip and indoor OWC systems.
Portuguese Man-of-War Image Classification with Convolutional Neural Networks
Venue: arXiv cs.CV 2022
Year: 2022

Portuguese man-of-war (PMW) is a gelatinous organism with long tentacles capable of causing severe burns, thus leading to negative impacts on human activities, such as tourism and fishing. There is a lack of information about the spatio-temporal dynamics of this species. Therefore, the use of alternative methods for collecting data can contribute to their monitoring. Given the widespread use of social networks and the eye-catching look of PMW, Instagram posts can be a promising data source for monitoring. The first task to follow this approach is to identify posts that refer to PMW. This paper reports on the use of convolutional neural networks for PMW images classification, in order to automate the recognition of Instagram posts. We created a suitable dataset, and trained three different neural networks: VGG-16, ResNet50, and InceptionV3, with and without a pre-trained step with the ImageNet dataset. We analyzed their results using accuracy, precision, recall, and F1 score metrics. The pre-trained ResNet50 network presented the best results, obtaining 94% of accuracy and 95% of precision, recall, and F1 score. These results show that convolutional neural networks can be very effective for recognizing PMW images from the Instagram social media.