OpenRaiser/Intern-Atlas huggingface dataset:
Counting and localizing defective nodes by Boolean network tomography
Venue: arXiv cs.NI 2021
Year: 2021

Identifying defective items in larger sets is a main problem with many applications in real life situations. We consider the problem of localizing defective nodes in networks through an approach based on boolean network tomography (BNT), which is grounded on inferring informations from the boolean outcomes of end-to-end measurements paths. {\em Identifiability} conditions on the set of paths which guarantee discovering or counting unambiguously the defective nodes are of course very relevant. We investigate old and introduce new identifiability conditions contributing this problem both from a theoretical and applied perspective. (1) What is the precise tradeoff between number of nodes and number of paths such that at most $k$ nodes can be identified unambiguously ? The answer is known only for $k=1$ and we answer the question for any $k$, setting a problem implicitly left open in previous works. (2) We study upper and lower bounds on the number of unambiguously identifiable nodes, introducing new identifiability conditions which strictly imply and are strictly implied by unambiguous identifiability; (3) We use these new conditions on one side to design algorithmic heuristics to count defective nodes in a fine-grained way, on the other side to prove the first complexity hardness results on the problem of identifying defective nodes in networks via BNT. (4) We introduce a random model where we study lower bounds on the number of unambiguously identifiable defective nodes and we use this model to estimate that number on real networks by a maximum likelihood estimate approach
Privacy Aspects of Provenance Queries
Venue: arXiv cs.DB 2021
Year: 2021

Given a query result of a big database, why-provenance can be used to calculate the necessary part of this database, consisting of so-called witnesses. If this database consists of personal data, privacy protection has to prevent the publication of these witnesses. This implies a natural conflict of interest between publishing original data (provenance) and protecting these data (privacy). In this paper, privacy goes beyond the concept of personal data protection. The paper gives an extended definition of privacy as intellectual property protection. If the provenance information is not sufficient to reconstruct a query result, additional data such as witnesses or provenance polynomials have to be published to guarantee traceability. Nevertheless, publishing this provenance information might be a problem if (significantly) more tuples than necessary can be derived from the original database. At this point, it is already possible to violate privacy policies, provided that quasi identifiers are included in this provenance information. With this poster, we point out fundamental problems and discuss first proposals for solutions.
Towards a Performance Model for Byzantine Fault Tolerant (Storage) Services
Venue: arXiv cs.DC 2021
Year: 2021

Byzantine fault-tolerant systems have been researched for more than four decades, and although shown possible early, the solutions were impractical for a long time. With PBFT the first practical solution was proposed in 1999 and spawned new research which culminated in novel applications using it today. Although the safety and liveness properties of PBFT-type protocols have been rigorously analyzed, when it comes to practical performance only empirical results - often in artificial settings - are known and imperfections on the communication channels are not specifically considered. In this work we present the first performance model for PBFT specifically considering the impact of unreliable channels and the use of different transport protocols over them. We also did extensive simulations to verify the model and to gain more insight on the impact of deployment parameters on the overall transaction time. We show that the usage of UDP can lead to significant speedup for PBFT protocols compared to TCP when tuned accordingly even over lossy channels. Finally, we compared the simulation to a real implementation and measure the benefits of a developed improvement directly. We found that the impact on the design of the network layer has been overlooked in the past but offers some additional room for improvement when it comes to practical performance. In this work we are focusing on the optimistic case with no node failures, as this is hopefully the most relevant situation.
Resolution-invariant Person ReID Based on Feature Transformation and Self-weighted Attention
Venue: arXiv cs.CV 2021
Year: 2021

Person Re-identification (ReID) is a critical computer vision task which aims to match the same person in images or video sequences. Most current works focus on settings where the resolution of images is kept the same. However, the resolution is a crucial factor in person ReID, especially when the cameras are at different distances from the person or the camera's models are different from each other. In this paper, we propose a novel two-stream network with a lightweight resolution association ReID feature transformation (RAFT) module and a self-weighted attention (SWA) ReID module to evaluate features under different resolutions. RAFT transforms the low resolution features to corresponding high resolution features. SWA evaluates both features to get weight factors for the person ReID. Both modules are jointly trained to get a resolution-invariant representation. Extensive experiments on five benchmark datasets show the effectiveness of our method. For instance, we achieve Rank-1 accuracy of 43.3% and 83.2% on CAVIAR and MLR-CUHK03, outperforming the state-of-the-art.
TopoKnit : A Process-Oriented Representation for Modeling the Topology of Yarns in Weft-Knitted Textiles
Venue: arXiv cs.GR 2021
Year: 2021

Machine knitted textiles are complex multi-scale material structures increasingly important in many industries, including consumer products, architecture, composites, medical, and military. Computational modeling, simulation, and design of industrial fabrics require efficient representations of the spatial, material, and physical properties of such structures. We propose a process-oriented representation, TopoKnit, that defines a foundational data structure for representing the topology of weft-knitted textiles at the yarn scale. Process space serves as an intermediary between the machine and fabric spaces, and supports a concise, computationally efficient evaluation approach based on on-demand, near constant-time queries. In this paper, we define the properties of the process space, and design a data structure to represent it and algorithms to evaluate it. We demonstrate the effectiveness of the representation scheme by providing results of evaluations of the data structure in support of common topological operations in the fabric space.
Predicting Relative Depth between Objects from Semantic Features
Venue: arXiv cs.CV 2021
Year: 2021

Vision and language tasks such as Visual Relation Detection and Visual Question Answering benefit from semantic features that afford proper grounding of language. The 3D depth of objects depicted in 2D images is one such feature. However it is very difficult to obtain accurate depth information without learning the appropriate features, which are scene dependent. The state of the art in this area are complex Neural Network models trained on stereo image data to predict depth per pixel. Fortunately, in some tasks, its only the relative depth between objects that is required. In this paper the extent to which semantic features can predict course relative depth is investigated. The problem is casted as a classification one and geometrical features based on object bounding boxes, object labels and scene attributes are computed and used as inputs to pattern recognition models to predict relative depth. i.e behind, in-front and neutral. The results are compared to those obtained from averaging the output of the monodepth neural network model, which represents the state-of-the art. An overall increase of 14% in relative depth accuracy over relative depth computed from the monodepth model derived results is achieved.
Hybrid matheuristics to solve the integrated lot sizing and scheduling problem on parallel machines with sequence-dependent and non-triangular setup
Venue: arXiv cs.DC 2021
Year: 2021

This paper approaches the integrated lot sizing and scheduling problem (ILSSP), in which non-identical machines work in parallel with non-triangular sequence-dependent setup costs and times, setup carry-over and capacity limitation. The aim of the studied ILSSP, here called ILSSP-NT on parallel machines, is to determine a production planning and tasks sequencing that meet period demands without delay and in such a way that the total costs of production, machine setup and inventory are minimized. The dearth of literature on the ILSSP-NT, despite the increasing amount of applications in the industrial sector, mainly in the food processing industry, motivated us to conduct this study. In this paper, we propose efficient methods to solve the ILSSP-NT on parallel machines. The methods virtually consist in the hybridization of the relax-and-fix and fix-and-optimize methods with the path-relinking and kernel search heuristics. To assess how well the heuristics solve the ILSSP-NT on parallel machines, we compared their results with those of the CPLEX solver with a fixed CPU time limit. The proposed matheuristics significantly outperformed CPLEX in most of the tested instances.
Declarative Demand-Driven Reverse Engineering
Venue: arXiv cs.PL 2021
Year: 2021

Binary reverse engineering is a challenging task because it often necessitates reasoning using both domain-specific knowledge (e.g., understanding entrypoint idioms common to an ABI) and logical inference (e.g., reconstructing interprocedural control flow). To help perform these tasks, reverse engineers often use toolkits (such as IDA Pro or Ghidra) that allow them to interactively explicate properties of binaries. We argue that deductive databases serve as a natural abstraction for interfacing between visualization-based binary analysis tools and high-performance logical inference engines that compute facts about binaries. In this paper, we present a vision for the future in which reverse engineers use a visualization-based tool to understand binaries while simultaneously querying a logical-inference engine to perform arbitrarily-complex deductive inference tasks. We call our vision declarative demand-driven reverse engineering (D^3RE for short), and sketch a formal semantics whose goal is to mediate interaction between a logical-inference engine (such Souffle) and a reverse engineering tool. We describe aprototype tool, d3re, which are using to explore the D^3RE vision. While still a prototype, we have used d3re to reimplement several common querying tasks on binaries. Our evaluation demonstrates that d3re enables both better performance and more succinct implementation of these common RE tasks.
Latent Alignment of Procedural Concepts in Multimodal Recipes
Venue: arXiv cs.CL 2021
Year: 2021

We propose a novel alignment mechanism to deal with procedural reasoning on a newly released multimodal QA dataset, named RecipeQA. Our model is solving the textual cloze task which is a reading comprehension on a recipe containing images and instructions. We exploit the power of attention networks, cross-modal representations, and a latent alignment space between instructions and candidate answers to solve the problem. We introduce constrained max-pooling which refines the max-pooling operation on the alignment matrix to impose disjoint constraints among the outputs of the model. Our evaluation result indicates a 19\% improvement over the baselines.
People, Places, and Ties: Landscape of social places and their social network structures
Venue: arXiv cs.SI 2021
Year: 2021

Due to their essential role as places for socialization, "third places" - social places where people casually visit and communicate with friends and neighbors - have been studied by a wide range of fields including network science, sociology, geography, urban planning, and regional studies. However, the lack of a large-scale census on third places kept researchers from systematic investigations. Here we provide a systematic nationwide investigation of third places and their social networks, by using Facebook pages. Our analysis reveals a large degree of geographic heterogeneity in the distribution of the types of third places, which is highly correlated with baseline demographics and county characteristics. Certain types of pages like "Places of Worship" demonstrate a large degree of clustering suggesting community preference or potential complementarities to concentration. We also found that the social networks of different types of social place differ in important ways: The social networks of 'Restaurants' and 'Indoor Recreation' pages are more likely to be tight-knit communities of pre-existing friendships whereas 'Places of Worship' and 'Community Amenities' page categories are more likely to bridge new friendship ties. We believe that this study can serve as an important milestone for future studies on the systematic comparative study of social spaces and their social relationships.
Linear Representation Meta-Reinforcement Learning for Instant Adaptation
Venue: arXiv cs.LG 2021
Year: 2021

This paper introduces Fast Linearized Adaptive Policy (FLAP), a new meta-reinforcement learning (meta-RL) method that is able to extrapolate well to out-of-distribution tasks without the need to reuse data from training, and adapt almost instantaneously with the need of only a few samples during testing. FLAP builds upon the idea of learning a shared linear representation of the policy so that when adapting to a new task, it suffices to predict a set of linear weights. A separate adapter network is trained simultaneously with the policy such that during adaptation, we can directly use the adapter network to predict these linear weights instead of updating a meta-policy via gradient descent, such as in prior meta-RL methods like MAML, to obtain the new policy. The application of the separate feed-forward network not only speeds up the adaptation run-time significantly, but also generalizes extremely well to very different tasks that prior Meta-RL methods fail to generalize to. Experiments on standard continuous-control meta-RL benchmarks show FLAP presenting significantly stronger performance on out-of-distribution tasks with up to double the average return and up to 8X faster adaptation run-time speeds when compared to prior methods.
A threshold search based memetic algorithm for the disjunctively constrained knapsack problem
Venue: arXiv cs.NE 2021
Year: 2021

The disjunctively constrained knapsack problem consists in packing a subset of pairwisely compatible items in a capacity-constrained knapsack such that the total profit of the selected items is maximized while satisfying the knapsack capacity. DCKP has numerous applications and is however computationally challenging (NP-hard). In this work, we present a threshold search based memetic algorithm for solving the DCKP that combines the memetic framework with threshold search to find high quality solutions. Extensive computational assessments on two sets of 6340 benchmark instances in the literature demonstrate that the proposed algorithm is highly competitive compared to the state-of-the-art methods. In particular, we report 24 and 354 improved best-known results (new lower bounds) for Set I (100 instances) and for Set II (6240 instances), respectively. We analyze the key algorithmic components and shed lights on their roles for the performance of the algorithm. The code of our algorithm will be made publicly available.
MP3net: coherent, minute-long music generation from raw audio with a simple convolutional GAN
Venue: arXiv cs.SD 2021
Year: 2021

We present a deep convolutional GAN which leverages techniques from MP3/Vorbis audio compression to produce long, high-quality audio samples with long-range coherence. The model uses a Modified Discrete Cosine Transform (MDCT) data representation, which includes all phase information. Phase generation is hence integral part of the model. We leverage the auditory masking and psychoacoustic perception limit of the human ear to widen the true distribution and stabilize the training process. The model architecture is a deep 2D convolutional network, where each subsequent generator model block increases the resolution along the time axis and adds a higher octave along the frequency axis. The deeper layers are connected with all parts of the output and have the context of the full track. This enables generation of samples which exhibit long-range coherence. We use MP3net to create 95s stereo tracks with a 22kHz sample rate after training for 250h on a single Cloud TPUv2. An additional benefit of the CNN-based model architecture is that generation of new songs is almost instantaneous.
Evaluation of quality scalability techniques for video transmission
Venue: arXiv cs.NI 2021
Year: 2021

The significant increase of the transmission of multimedia content over Internet are demanded new delivery strategies to assure a good quality of experience of the users. Transmission of video over packet networks is not an easy task due to multiple fluctuations of the network conditions. One possibility to improve the quality of some video streaming services is the combinate use of the scalable video coding and cross layer mechanisms that allow applications to adapt its traffic stream to the resources network that are available. In this paper, it is presented a performance evaluation of the three main scalability techniques: CGS (Coarse-Grained Scalability), FGS (Fine Grain scalability) and MGS (Medium Grain Scalability). In particular, we focus on determining what method is more appropriated for video transmission taking into account some video quality metrics like PSNR (Peak Signal-to-Noise Ratio) and decoded frame rate. The results reveal that the rate-adaptive strategy and the MGS technique help avoid or reduce the congestion in networks obtaining a better quality in the received videos.
Is NOMA Efficient in Multi-Antenna Networks? A Critical Look at Next Generation Multiple Access Techniques
Venue: arXiv cs.IT 2021
Year: 2021

In this paper, we take a critical and fresh look at the downlink multi-antenna NOMA literature. Instead of contrasting NOMA with OMA, we contrast NOMA with two other baselines. The first is conventional Multi-User Linear Precoding (MULP). The second is Rate-Splitting Multiple Access (RSMA) based on multi-antenna Rate-Splitting (RS) and SIC. We show that there is some confusion about the benefits of NOMA, and we dispel the associated misconceptions. First, we highlight why NOMA is inefficient in multi-antenna settings based on basic multiplexing gain analysis. We stress that the issue lies in how the NOMA literature has been hastily applied to multi-antenna setups, resulting in a misuse of spatial dimensions and therefore loss in multiplexing gains and rate. Second, we show that NOMA incurs a severe multiplexing gain loss despite an increased receiver complexity due to an inefficient use of SIC receivers. Third, we emphasize that much of the merits of NOMA are due to the constant comparison to OMA instead of comparing it to MULP and RS baselines. We then expose the pivotal design constraint that multi-antenna NOMA requires one user to fully decode the messages of the other users. This design constraint is responsible for the multiplexing gain erosion, rate loss, and inefficient use of SIC receivers in multi-antenna settings. Our results confirm that NOMA should not be applied blindly to multi-antenna settings, highlight the scenarios where MULP outperforms NOMA and vice versa, and demonstrate the inefficiency, performance loss and complexity disadvantages of NOMA compared to RS. The first takeaway message is that, while NOMA is not beneficial in most multi-antenna deployments. The second takeaway message is that other non-orthogonal transmission frameworks, such as RS, exist which fully exploit the multiplexing gain and the benefits of SIC to boost the rate in multi-antenna settings.
Wireless Power Transfer for Future Networks: Signal Processing, Machine Learning, Computing, and Sensing
Venue: arXiv cs.IT 2021
Year: 2021

Wireless power transfer (WPT) is an emerging paradigm that will enable using wireless to its full potential in future networks, not only to convey information but also to deliver energy. Such networks will enable trillions of future low-power devices to sense, compute, connect, and energize anywhere, anytime, and on the move. The design of such future networks brings new challenges and opportunities for signal processing, machine learning, sensing, and computing so as to make the best use of the RF radiations, spectrum, and network infrastructure in providing cost-effective and real-time power supplies to wireless devices and enable wireless-powered applications. In this paper, we first review recent signal processing techniques to make WPT and wireless information and power transfer as efficient as possible. Topics include power amplifier and energy harvester nonlinearities, active and passive beamforming, intelligent reflecting surfaces, receive combining with multi-antenna harvester, modulation, coding, waveform, massive MIMO, channel acquisition, transmit diversity, multi-user power region characterization, coordinated multipoint, and distributed antenna systems. Then, we overview two different design methodologies: the model and optimize approach relying on analytical system models, modern convex optimization, and communication theory, and the learning approach based on data-driven end-to-end learning and physics-based learning. We discuss the pros and cons of each approach, especially when accounting for various nonlinearities in wireless-powered networks, and identify interesting emerging opportunities for the approaches to complement each other. Finally, we identify new emerging wireless technologies where WPT may play a key role -- wireless-powered mobile edge computing and wireless-powered sensing -- arguing WPT, communication, computation, and sensing must be jointly designed.
Energy-Efficient Distributed Learning Algorithms for Coarsely Quantized Signals
Venue: arXiv cs.LG 2021
Year: 2021

In this work, we present an energy-efficient distributed learning framework using low-resolution ADCs and coarsely quantized signals for Internet of Things (IoT) networks. In particular, we develop a distributed quantization-aware least-mean square (DQA-LMS) algorithm that can learn parameters in an energy-efficient fashion using signals quantized with few bits while requiring a low computational cost. We also carry out a statistical analysis of the proposed DQA-LMS algorithm that includes a stability condition. Simulations assess the DQA-LMS algorithm against existing techniques for a distributed parameter estimation task where IoT devices operate in a peer-to-peer mode and demonstrate the effectiveness of the DQA-LMS algorithm.