OpenRaiser/Intern-Atlas huggingface dataset:
Private Graph Data Release: A Survey
Venue: arXiv cs.CR 2022
Year: 2022

The application of graph analytics to various domains has yielded tremendous societal and economical benefits in recent years. However, the increasingly widespread adoption of graph analytics comes with a commensurate increase in the need to protect private information in graph data, especially in light of the many privacy breaches in real-world graph data that was supposed to preserve sensitive information. This paper provides a comprehensive survey of private graph data release algorithms that seek to achieve the fine balance between privacy and utility, with a specific focus on provably private mechanisms. Many of these mechanisms are natural extensions of the Differential Privacy framework to graph data, but we also investigate more general privacy formulations like Pufferfish Privacy that address some of the limitations of Differential Privacy. We also provide a wide-ranging survey of the applications of private graph data release mechanisms to social networks, finance, supply chain, and health care. This survey paper and the taxonomy it provides should benefit practitioners and researchers alike in the increasingly important area of private analytics and data release.
BEAT: Blockchain-Enabled Accountable and Transparent Network Sharing in 6G
Venue: arXiv cs.NI 2022
Year: 2022

Infrastructure sharing is a widely discussed and implemented approach and is successfully adopted in telecommunications networks today. In practice, it is implemented through prior negotiated Service Level Agreements (SLAs) between the parties involved. However, it is recognised that these agreements are difficult to negotiate, monitor and enforce. For future 6G networks, resource and infrastructure sharing is expected to play an even greater role. It will be a crucial technique for reducing overall infrastructure costs and increasing operational efficiencies for operators. More efficient SLA mechanisms are thus crucial to the success of future networks. In this work, we present "BEAT", an automated, transparent and accountable end-to-end architecture for network sharing based on blockchain and smart contracts. This work focuses on a particular type of blockchain, Permissioned Distributed Ledger (PDL), due to its permissioned nature allowing for industry-compliant SLAs with stringent governance. Our architecture can be implemented with minimal hardware changes and with minimal overheads.
Rate-Splitting Multiple Access for Communications and Jamming in Multi-Antenna Multi-Carrier Cognitive Radio Systems
Venue: arXiv cs.IT 2022
Year: 2022

With the increasing number of wireless communication systems and the demand for bandwidth, the wireless medium has become a congested and contested environment. Operating under such an environment brings several challenges, especially for military communication systems, which need to guarantee reliable communication while avoiding interfering with other friendly or neutral systems and denying the enemy systems of service. In this work, we investigate a novel application of Rate-Splitting Multiple Access(RSMA) for joint communications and jamming with a Multi-Carrier(MC) waveform in a multiantenna Cognitive Radio(CR) system. RSMA is a robust multiple access scheme for downlink multi-antenna wireless networks. RSMA relies on multi-antenna Rate-Splitting (RS) at the transmitter and Successive Interference Cancellation (SIC) at the receivers. Our aim is to simultaneously communicate with Secondary Users(SUs) and jam Adversarial Users(AUs) to disrupt their communications while limiting the interference to Primary Users(PUs) in a setting where all users perform broadband communications by MC waveforms in their respective networks. We consider the practical setting of imperfect CSI at transmitter(CSIT) for the SUs and PUs, and statistical CSIT for AUs. We formulate a problem to obtain optimal precoders which maximize the mutual information under interference and jamming power constraints. We propose an Alternating Optimization-Alternating Direction Method of Multipliers(AOADMM) based algorithm for solving the resulting non-convex problem. We perform an analysis based on Karush-Kuhn-Tucker conditions to determine the optimal jamming and interference power thresholds that guarantee the feasibility of problem and propose a practical algorithm to calculate the interference power threshold. By simulations, we show that RSMA achieves a higher sum-rate than Space Division Multiple Access(SDMA).
Dihedral multi-reference alignment
Venue: arXiv cs.IT 2022
Year: 2022

We study the dihedral multi-reference alignment problem of estimating the orbit of a signal from multiple noisy observations of the signal, acted on by random elements of the dihedral group. We show that if the group elements are drawn from a generic distribution, the orbit of a generic signal is uniquely determined from the second moment of the observations. This implies that the optimal estimation rate in the high noise regime is proportional to the square of the variance of the noise. This is the first result of this type for multi-reference alignment over a non-abelian group with a non-uniform distribution of group elements. Based on tools from invariant theory and algebraic geometry, we also delineate conditions for unique orbit recovery for multi-reference alignment models over finite groups (namely, when the dihedral group is replaced by a general finite group) when the group elements are drawn from a generic distribution. Finally, we design and study numerically three computational frameworks for estimating the signal based on group synchronization, expectation-maximization, and the method of moments.
How to Approximate Ontology-Mediated Queries
Venue: arXiv cs.AI 2022
Year: 2022

We introduce and study several notions of approximation for ontology-mediated queries based on the description logics ALC and ALCI. Our approximations are of two kinds: we may (1) replace the ontology with one formulated in a tractable ontology language such as ELI or certain TGDs and (2) replace the database with one from a tractable class such as the class of databases whose treewidth is bounded by a constant. We determine the computational complexity and the relative completeness of the resulting approximations. (Almost) all of them reduce the data complexity from coNP-complete to PTime, in some cases even to fixed-parameter tractable and to linear time. While approximations of kind (1) also reduce the combined complexity, this tends to not be the case for approximations of kind (2). In some cases, the combined complexity even increases.
Disentangling Transfer and Interference in Multi-Domain Learning
Venue: arXiv cs.CV 2022
Year: 2022

Humans are incredibly good at transferring knowledge from one domain to another, enabling rapid learning of new tasks. Likewise, transfer learning has enabled enormous success in many computer vision problems using pretraining. However, the benefits of transfer in multi-domain learning, where a network learns multiple tasks defined by different datasets, has not been adequately studied. Learning multiple domains could be beneficial, or these domains could interfere with each other given limited network capacity. Understanding how deep neural networks of varied capacity facilitate transfer across inputs from different distributions is a critical step towards open world learning. In this work, we decipher the conditions where interference and knowledge transfer occur in multi-domain learning. We propose new metrics disentangling interference and transfer, set up experimental protocols, and examine the roles of network capacity, task grouping, and dynamic loss weighting in reducing interference and facilitating transfer.
Rate-Exponent Region for a Class of Distributed Hypothesis Testing Against Conditional Independence Problems
Venue: arXiv cs.IT 2022
Year: 2022

We study a class of $K$-encoder hypothesis testing against conditional independence problems. Under the criterion that stipulates minimization of the Type II error subject to a (constant) upper bound $ε$ on the Type I error, we characterize the set of encoding rates and exponent for both discrete memoryless and memoryless vector Gaussian settings. For the DM setting, we provide a converse proof and show that it is achieved using the Quantize-Bin-Test scheme of Rahman and Wagner. For the memoryless vector Gaussian setting, we develop a tight outer bound by means of a technique that relies on the de Bruijn identity and the properties of Fisher information. In particular, the result shows that for memoryless vector Gaussian sources the rate-exponent region is exhausted using the Quantize-Bin-Test scheme with \textit{Gaussian} test channels; and there is \textit{no} loss in performance caused by restricting the sensors' encoders not to employ time sharing. Furthermore, we also study a variant of the problem in which the source, not necessarily Gaussian, has finite differential entropy and the sensors' observations noises under the null hypothesis are Gaussian. For this model, our main result is an upper bound on the exponent-rate function. The bound is shown to mirror a corresponding explicit lower bound, except that the lower bound involves the source power (variance) whereas the upper bound has the source entropy power. Part of the utility of the established bound is for investigating asymptotic exponent/rates and losses incurred by distributed detection as function of the number of sensors.
DARM: Control-Flow Melding for SIMT Thread Divergence Reduction -- Extended Version
Venue: arXiv cs.PL 2022
Year: 2022

GPGPUs use the Single-Instruction-Multiple-Thread (SIMT) execution model where a group of threads-wavefront or warp-execute instructions in lockstep. When threads in a group encounter a branching instruction, not all threads in the group take the same path, a phenomenon known as control-flow divergence. The control-flow divergence causes performance degradation because both paths of the branch must be executed one after the other. Prior research has primarily addressed this issue through architectural modifications. We observe that certain GPGPU kernels with control-flow divergence have similar control-flow structures with similar instructions on both sides of a branch. This structure can be exploited to reduce control-flow divergence by melding the two sides of the branch allowing threads to reconverge early, reducing divergence. In this work, we present DARM, a compiler analysis and transformation framework that can meld divergent control-flow structures with similar instruction sequences. We show that DARM can reduce the performance degradation from control-flow divergence.
Least-Squares Linear Dilation-Erosion Regressor Trained using a Convex-Concave Procedure
Venue: arXiv cs.LG 2022
Year: 2022

This paper presents a hybrid morphological neural network for regression tasks called linear dilation-erosion regressor ($\ell$-DER). An $\ell$-DER is given by a convex combination of the composition of linear and morphological operators. They yield continuous piecewise linear functions and, thus, are universal approximators. Besides introducing the $\ell$-DER model, we formulate their training as a difference of convex (DC) programming problem. Precisely, an $\ell$-DER is trained by minimizing the least-squares using the convex-concave procedure (CCP). Computational experiments using several regression tasks confirm the efficacy of the proposed regressor, outperforming other hybrid morphological models and state-of-the-art approaches such as the multilayer perceptron network and the radial-basis support vector regressor.
Detect and Locate: Exposing Face Manipulation by Semantic- and Noise-level Telltales
Venue: arXiv cs.CV 2022
Year: 2022

The technological advancements of deep learning have enabled sophisticated face manipulation schemes, raising severe trust issues and security concerns in modern society. Generally speaking, detecting manipulated faces and locating the potentially altered regions are challenging tasks. Herein, we propose a conceptually simple but effective method to efficiently detect forged faces in an image while simultaneously locating the manipulated regions. The proposed scheme relies on a segmentation map that delivers meaningful high-level semantic information clues about the image. Furthermore, a noise map is estimated, playing a complementary role in capturing low-level clues and subsequently empowering decision-making. Finally, the features from these two modules are combined to distinguish fake faces. Extensive experiments show that the proposed model achieves state-of-the-art detection accuracy and remarkable localization performance.
Toward Safe Integration of Legacy SCADA Systems in the Smart Grid
Venue: arXiv cs.CR 2022
Year: 2022

A SCADA system is a distributed network of cyber-physical devices used for instrumentation and control of critical infrastructures such as an electric power grid. With the emergence of the smart grid, SCADA systems are increasingly required to be connected to more open systems and security becomes crucial. However, many of these SCADA systems have been deployed for decades and were initially not designed with security in mind. In particular, the field devices in these systems are vulnerable to false command injection from an intruding or compromised device. But implementing cryptographic defence on these old-generation devices is challenging due to their computation constraints. As a key requirement, solutions to protect legacy SCADA systems have to be an add-on. This paper discusses two add-on defence strategies for legacy SCADA systems -- the data diode and the detect-and-respond approach -- and compares their security guarantees and applicable scenarios. A generic architectural framework is also proposed to implement the detect-and-respond strategy, with an instantiation to demonstrate its practicality.
Security and Privacy of Wireless Beacon Systems
Venue: arXiv cs.CR 2022
Year: 2022

Bluetooth Low Energy (BLE) beacons have been increasingly used in smart city applications, such as location-based and proximity-based services, to enable Internet of Things to interact with people in vicinity or enhance context-awareness. Their widespread deployment in human-centric applications makes them an attractive target to adversaries for social or economic reasons. In fact, beacons are reportedly exposed to various security issues and privacy concerns. A characterization of attacks against beacon systems is given to help understand adversary motives, required adversarial capabilities, potential impact and possible defence mechanisms for different threats, with a view to facilitating security evaluation and protection formulation for beacon systems.
Model-free Reinforcement Learning for Robust Locomotion using Demonstrations from Trajectory Optimization
Venue: arXiv cs.RO 2022
Year: 2022

We present a general, two-stage reinforcement learning approach to create robust policies that can be deployed on real robots without any additional training using a single demonstration generated by trajectory optimization. The demonstration is used in the first stage as a starting point to facilitate initial exploration. In the second stage, the relevant task reward is optimized directly and a policy robust to environment uncertainties is computed. We demonstrate and examine in detail the performance and robustness of our approach on highly dynamic hopping and bounding tasks on a quadruped robot.
Reinforced Hybrid Genetic Algorithm for the Traveling Salesman Problem
Venue: arXiv cs.NE 2022
Year: 2022

In this paper, we propose a new method called the Reinforced Hybrid Genetic Algorithm (RHGA) for solving the famous NP-hard Traveling Salesman Problem (TSP). Specifically, we combine reinforcement learning with the well-known Edge Assembly Crossover genetic algorithm (EAX-GA) and the Lin-Kernighan-Helsgaun (LKH) local search heuristic. In the hybrid algorithm, LKH can help EAX-GA improve the population by its effective local search, and EAX-GA can help LKH escape from local optima by providing high-quality and diverse initial solutions. We restrict that there is only one special individual among the population in EAX-GA that can be improved by LKH. Such a mechanism can prevent the population diversity, efficiency, and algorithm performance from declining due to the redundant calling of LKH upon the population. As a result, our proposed hybrid mechanism can help EAX-GA and LKH boost each other's performance without reducing the convergence rate of the population. The reinforcement learning technique based on Q-learning further promotes the hybrid genetic algorithm. Experimental results on 138 well-known and widely used TSP benchmarks with the number of cities ranging from 1,000 to 85,900 demonstrate the excellent performance of RHGA.
Federated Self-Training for Semi-Supervised Audio Recognition
Venue: arXiv cs.LG 2022
Year: 2022

Federated Learning is a distributed machine learning paradigm dealing with decentralized and personal datasets. Since data reside on devices like smartphones and virtual assistants, labeling is entrusted to the clients, or labels are extracted in an automated way. Specifically, in the case of audio data, acquiring semantic annotations can be prohibitively expensive and time-consuming. As a result, an abundance of audio data remains unlabeled and unexploited on users' devices. Most existing federated learning approaches focus on supervised learning without harnessing the unlabeled data. In this work, we study the problem of semi-supervised learning of audio models via self-training in conjunction with federated learning. We propose FedSTAR to exploit large-scale on-device unlabeled data to improve the generalization of audio recognition models. We further demonstrate that self-supervised pre-trained models can accelerate the training of on-device models, significantly improving convergence to within fewer training rounds. We conduct experiments on diverse public audio classification datasets and investigate the performance of our models under varying percentages of labeled and unlabeled data. Notably, we show that with as little as 3% labeled data available, FedSTAR on average can improve the recognition rate by 13.28% compared to the fully supervised federated model.
WeightScale: Interpreting Weight Change in Neural Networks
Venue: arXiv cs.LG 2022
Year: 2022

Interpreting the learning dynamics of neural networks can provide useful insights into how networks learn and the development of better training and design approaches. We present an approach to interpret learning in neural networks by measuring relative weight change on a per layer basis and dynamically aggregating emerging trends through combination of dimensionality reduction and clustering which allows us to scale to very deep networks. We use this approach to investigate learning in the context of vision tasks across a variety of state-of-the-art networks and provide insights into the learning behavior of these networks, including how task complexity affects layer-wise learning in deeper layers of networks.
Compact and Optimal Deep Learning with Recurrent Parameter Generators
Venue: arXiv cs.CV 2022
Year: 2022

Deep learning has achieved tremendous success by training increasingly large models, which are then compressed for practical deployment. We propose a drastically different approach to compact and optimal deep learning: We decouple the Degrees of freedom (DoF) and the actual number of parameters of a model, optimize a small DoF with predefined random linear constraints for a large model of arbitrary architecture, in one-stage end-to-end learning. Specifically, we create a recurrent parameter generator (RPG), which repeatedly fetches parameters from a ring and unpacks them onto a large model with random permutation and sign flipping to promote parameter decorrelation. We show that gradient descent can automatically find the best model under constraints with faster convergence. Our extensive experimentation reveals a log-linear relationship between model DoF and accuracy. Our RPG demonstrates remarkable DoF reduction and can be further pruned and quantized for additional run-time performance gain. For example, in terms of top-1 accuracy on ImageNet, RPG achieves $96\%$ of ResNet18's performance with only $18\%$ DoF (the equivalent of one convolutional layer) and $52\%$ of ResNet34's performance with only $0.25\%$ DoF! Our work shows a significant potential of constrained neural optimization in compact and optimal deep learning.
What and When to Look?: Temporal Span Proposal Network for Video Relation Detection
Venue: arXiv cs.CV 2022
Year: 2022

Identifying relations between objects is central to understanding the scene. While several works have been proposed for relation modeling in the image domain, there have been many constraints in the video domain due to challenging dynamics of spatio-temporal interactions (e.g., between which objects are there an interaction? when do relations start and end?). To date, two representative methods have been proposed to tackle Video Visual Relation Detection (VidVRD): segment-based and window-based. We first point out limitations of these methods and propose a novel approach named Temporal Span Proposal Network (TSPN). TSPN tells what to look: it sparsifies relation search space by scoring relationness of object pair, i.e., measuring how probable a relation exist. TSPN tells when to look: it simultaneously predicts start-end timestamps (i.e., temporal spans) and categories of the all possible relations by utilizing full video context. These two designs enable a win-win scenario: it accelerates training by 2X or more than existing methods and achieves competitive performance on two VidVRD benchmarks (ImageNet-VidVDR and VidOR). Moreover, comprehensive ablative experiments demonstrate the effectiveness of our approach. Codes are available at https://github.com/sangminwoo/Temporal-Span-Proposal-Network-VidVRD.
Scene-adaptive Knowledge Distillation for Sequential Recommendation via Differentiable Architecture Search
Venue: arXiv cs.IR 2022
Year: 2022

Sequential recommender systems (SRS) have become a research hotspot due to its power in modeling user dynamic interests and sequential behavioral patterns. To maximize model expressive ability, a default choice is to apply a larger and deeper network architecture, which, however, often brings high network latency when generating online recommendations. Naturally, we argue that compressing the heavy recommendation models into middle- or light- weight neural networks is of great importance for practical production systems. To realize such a goal, we propose AdaRec, a knowledge distillation (KD) framework which compresses knowledge of a teacher model into a student model adaptively according to its recommendation scene by using differentiable Neural Architecture Search (NAS). Specifically, we introduce a target-oriented distillation loss to guide the structure search process for finding the student network architecture, and a cost-sensitive loss as constraints for model size, which achieves a superior trade-off between recommendation effectiveness and efficiency. In addition, we leverage Earth Mover's Distance (EMD) to realize many-to-many layer mapping during knowledge distillation, which enables each intermediate student layer to learn from other intermediate teacher layers adaptively. Extensive experiments on real-world recommendation datasets demonstrate that our model achieves competitive or better accuracy with notable inference speedup comparing to strong counterparts, while discovering diverse neural architectures for sequential recommender models under different recommendation scenes.