OpenRaiser/Intern-Atlas huggingface dataset:
Codimensional Incremental Potential Contact
Venue: arXiv cs.GR 2021
Year: 2021

We extend the incremental potential contact (IPC) model for contacting elastodynamics to resolve systems composed of codimensional DOFs in arbitrary combination. This enables a unified, interpenetration-free, robust, and stable simulation framework that couples codimension-0,1,2, and 3 geometries seamlessly with frictional contact. Extending IPC to thin structures poses new challenges in computing strain, modeling thickness and determining collisions. To address these challenges we propose three corresponding contributions. First, we introduce a C2 constitutive barrier model that directly enforces strain limiting as an energy potential while preserving rest state. This provides energetically-consistent strain limiting models (both isotropic and anisotropic) for cloth that enable strict satisfaction of strain-limit inequalities with direct coupling to both elastodynamics and contact via minimization of the incremental potential. Second, to capture the geometric thickness of codimensional domains we extend the IPC model to directly enforce distance offsets. Our treatment imposes a strict guarantee that mid-surfaces (resp. mid-lines) of shells (resp. rods) will not move closer than applied thickness values. This enables us to account for thickness in the contact behavior of codimensional structures and so robustly capture challenging contacting geometries; a number of which, to our knowledge, have not been simulated before. Third, codimensional models, especially with modeled thickness, mandate strict accuracy requirements that pose a severe challenge to all existing continuous collision detection (CCD) methods. To address these limitations we develop a new, efficient, simple-to-implement additive CCD (ACCD) method that applies conservative advancement to iteratively refine a lower bound for deforming primitives, converging to time of impact.
A Novel Transformation Approach of Shared-link Coded Caching Schemes for Multiaccess Networks
Venue: arXiv cs.IT 2021
Year: 2021

This paper considers the multiaccess coded caching systems formulated by Hachem et al., including a central server containing $N$ files connected to $K$ cache-less users through an error-free shared link, and $K$ cache-nodes, each equipped with a cache memory size of $M$ files. Each user has access to $L$ neighbouring cache-nodes with a cyclic wrap-around topology. The coded caching scheme proposed by Hachem et al. suffers from the case that $L$ does not divide $K$, where the needed number of transmissions (a.k.a. load) is at most four times the load expression for the case where $L$ divides $K$. Our main contribution is to propose a novel {\it transformation} approach to smartly extend the schemes satisfying some conditions for the well known shared-link caching systems to the multiaccess caching systems. Then we can get many coded caching schemes with different subpacketizations for multiaccess coded caching system. These resulting schemes have the maximum local caching gain (i.e., the cached contents stored at any $L$ neighbouring cache-nodes are different such that the number of retrieval packets by each user from the connected cache-nodes is maximal) and the same coded caching gain as the original schemes. Applying the transformation approach to the well-known shared-link coded caching scheme proposed by Maddah-Ali and Niesen, we obtain a new multiaccess coded caching scheme that achieves the same load as the scheme of Hachem et al. but for any system parameters. Under the constraint of the cache placement used in this new multiaccess coded caching scheme, our delivery strategy is approximately optimal when $K$ is sufficiently large. Finally, we also show that the transmission load of the proposed scheme can be further reduced by compressing the multicast message.
A guide to choosing and implementing reference models for social network analysis
Venue: arXiv cs.SI 2021
Year: 2021

Analyzing social networks is challenging. Key features of relational data require the use of non-standard statistical methods such as developing system-specific null, or reference, models that randomize one or more components of the observed data. Here we review a variety of randomization procedures that generate reference models for social network analysis. Reference models provide an expectation for hypothesis-testing when analyzing network data. We outline the key stages in producing an effective reference model and detail four approaches for generating reference distributions: permutation, resampling, sampling from a distribution, and generative models. We highlight when each type of approach would be appropriate and note potential pitfalls for researchers to avoid. Throughout, we illustrate our points with examples from a simulated social system. Our aim is to provide social network researchers with a deeper understanding of analytical approaches to enhance their confidence when tailoring reference models to specific research questions.
Improving the Fairness of Deep Generative Models without Retraining
Venue: arXiv cs.CV 2021
Year: 2021

Generative Adversarial Networks (GANs) advance face synthesis through learning the underlying distribution of observed data. Despite the high-quality generated faces, some minority groups can be rarely generated from the trained models due to a biased image generation process. To study the issue, we first conduct an empirical study on a pre-trained face synthesis model. We observe that after training the GAN model not only carries the biases in the training data but also amplifies them to some degree in the image generation process. To further improve the fairness of image generation, we propose an interpretable baseline method to balance the output facial attributes without retraining. The proposed method shifts the interpretable semantic distribution in the latent space for a more balanced image generation while preserving the sample diversity. Besides producing more balanced data regarding a particular attribute (e.g., race, gender, etc.), our method is generalizable to handle more than one attribute at a time and synthesize samples of fine-grained subgroups. We further show the positive applicability of the balanced data sampled from GANs to quantify the biases in other face recognition systems, like commercial face attribute classifiers and face super-resolution algorithms.
On Distributed Algorithms for Minimum Dominating Set problem, from theory to application
Venue: arXiv cs.DC 2021
Year: 2021

In this paper, we propose a distributed algorithm for the minimum dominating set problem. For some especial networks, we prove theoretically that the achieved answer by our proposed algorithm is a constant approximation factor of the exact answer. This problem arises naturally in social networks, for example in news spreading, avoiding rumor spreading and recommendation spreading. So we implement our algorithm on massive social networks and compare our results with the state of the art algorithms. Also, we extend our algorithm to solve the $k$-distance dominating set problem and experimentally study the efficiency of the proposed algorithm. Our proposed algorithm is fast and easy to implement and can be used in dynamic networks where the edges and vertices are added or deleted constantly. More importantly, based on the experimental results the proposed algorithm has reasonable solutions and running time which enables us to use it in distributed model practically.
Operator as a Service: Stateful Serverless Complex Event Processing
Venue: arXiv cs.NI 2021
Year: 2021

Complex Event Processing (CEP) is a powerful paradigm for scalable data management that is employed in many real-world scenarios such as detecting credit card fraud in banks. The so-called complex events are expressed using a specification language that is typically implemented and executed on a specific runtime system. While the tight coupling of these two components has been regarded as the key for supporting CEP at high performance, such dependencies pose several inherent challenges as follows. (1) Application development atop a CEP system requires extensive knowledge of how the runtime system operates, which is typically highly complex in nature. (2) The specification language dependence requires the need of domain experts and further restricts and steepens the learning curve for application developers. In this paper, we propose CEPLESS, a scalable data management system that decouples the specification from the runtime system by building on the principles of serverless computing. CEPLESS provides operator as a service and offers flexibility by enabling the development of CEP application in any specification language while abstracting away the complexity of the CEP runtime system. As part of CEPLESS, we designed and evaluated novel mechanisms for in-memory processing and batching that enables the stateful processing of CEP operators even under high rates of ingested events. Our evaluation demonstrates that CEPLESS can be easily integrated into existing CEP systems like Apache Flink while attaining similar throughput under a high scale of events (up to 100K events per second) and dynamic operator update in up to 238 ms.
Page Tables: Keeping them Flat and Hot (Cached)
Venue: arXiv cs.AR 2021
Year: 2021

As memory capacity has outstripped TLB coverage, large data applications suffer from frequent page table walks. We investigate two complementary techniques for addressing this cost: reducing the number of accesses required and reducing the latency of each access. The first approach is accomplished by opportunistically "flattening" the page table: merging two levels of traditional 4KB page table nodes into a single 2MB node, thereby reducing the table's depth and the number of indirections required to search it. The second is accomplished by biasing the cache replacement algorithm to keep page table entries during periods of high TLB miss rates, as these periods also see high data miss rates and are therefore more likely to benefit from having the smaller page table in the cache than to suffer from increased data cache misses. We evaluate these approaches for both native and virtualized systems and across a range of realistic memory fragmentation scenarios, describe the limited changes needed in our kernel implementation and hardware design, identify and address challenges related to self-referencing page tables and kernel memory allocation, and compare results across server and mobile systems using both academic and industrial simulators for robustness. We find that flattening does reduce the number of accesses required on a page walk (to 1.0), but its performance impact (+2.3%) is small due to Page Walker Caches (already 1.5 accesses). Prioritizing caching has a larger effect (+6.8%), and the combination improves performance by +9.2%. Flattening is more effective on virtualized systems (4.4 to 2.8 accesses, +7.1% performance), due to 2D page walks. By combining the two techniques we demonstrate a state-of-the-art +14.0% performance gain and -8.7% dynamic cache energy and -4.7% dynamic DRAM energy for virtualized execution with very simple hardware and software changes.
Extracting the signed backbone of intrinsically dense weighted networks
Venue: arXiv cs.SI 2021
Year: 2021

Networks provide useful tools for analyzing diverse complex systems from natural, social, and technological domains. Growing size and variety of data such as more nodes and links and associated weights, directions, and signs can provide accessory information. Link and weight abundance, on the other hand, results in denser networks with noisy, insignificant, or otherwise redundant data. Moreover, typical network analysis and visualization techniques presuppose sparsity and are not appropriate or scalable for dense and weighted networks. As a remedy, network backbone extraction methods aim to retain only the important links while preserving the useful and elucidative structure of the original networks for further analyses. Here, we provide the first methods for extracting signed network backbones from intrinsically dense unsigned unipartite weighted networks. Utilizing a null model based on statistical techniques, the proposed significance filter and vigor filter allow inferring edge signs. Empirical analysis on migration, voting, temporal interaction, and species similarity networks reveals that the proposed filters extract meaningful and sparse signed backbones while preserving the multiscale nature of the network. The resulting backbones exhibit characteristics typically associated with signed networks such as reciprocity, structural balance, and community structure. The developed tool is provided as a free, open-source software package.
GAN "Steerability" without optimization
Venue: arXiv cs.CV 2021
Year: 2021

Recent research has shown remarkable success in revealing "steering" directions in the latent spaces of pre-trained GANs. These directions correspond to semantically meaningful image transformations e.g., shift, zoom, color manipulations), and have similar interpretable effects across all categories that the GAN can generate. Some methods focus on user-specified transformations, while others discover transformations in an unsupervised manner. However, all existing techniques rely on an optimization procedure to expose those directions, and offer no control over the degree of allowed interaction between different transformations. In this paper, we show that "steering" trajectories can be computed in closed form directly from the generator's weights without any form of training or optimization. This applies to user-prescribed geometric transformations, as well as to unsupervised discovery of more complex effects. Our approach allows determining both linear and nonlinear trajectories, and has many advantages over previous methods. In particular, we can control whether one transformation is allowed to come on the expense of another (e.g. zoom-in with or without allowing translation to keep the object centered). Moreover, we can determine the natural end-point of the trajectory, which corresponds to the largest extent to which a transformation can be applied without incurring degradation. Finally, we show how transferring attributes between images can be achieved without optimization, even across different categories.
Know Your Limits: Uncertainty Estimation with ReLU Classifiers Fails at Reliable OOD Detection
Venue: arXiv cs.LG 2021
Year: 2021

A crucial requirement for reliable deployment of deep learning models for safety-critical applications is the ability to identify out-of-distribution (OOD) data points, samples which differ from the training data and on which a model might underperform. Previous work has attempted to tackle this problem using uncertainty estimation techniques. However, there is empirical evidence that a large family of these techniques do not detect OOD reliably in classification tasks. This paper gives a theoretical explanation for said experimental findings and illustrates it on synthetic data. We prove that such techniques are not able to reliably identify OOD samples in a classification setting, since their level of confidence is generalized to unseen areas of the feature space. This result stems from the interplay between the representation of ReLU networks as piece-wise affine transformations, the saturating nature of activation functions like softmax, and the most widely-used uncertainty metrics.
Recurrence of Optimum for Training Weight and Activation Quantized Networks
Venue: arXiv cs.LG 2021
Year: 2021

Deep neural networks (DNNs) are quantized for efficient inference on resource-constrained platforms. However, training deep learning models with low-precision weights and activations involves a demanding optimization task, which calls for minimizing a stage-wise loss function subject to a discrete set-constraint. While numerous training methods have been proposed, existing studies for full quantization of DNNs are mostly empirical. From a theoretical point of view, we study practical techniques for overcoming the combinatorial nature of network quantization. Specifically, we investigate a simple yet powerful projected gradient-like algorithm for quantizing two-linear-layer networks, which proceeds by repeatedly moving one step at float weights in the negation of a heuristic \emph{fake} gradient of the loss function (so-called coarse gradient) evaluated at quantized weights. For the first time, we prove that under mild conditions, the sequence of quantized weights recurrently visits the global optimum of the discrete minimization problem for training fully quantized network. We also show numerical evidence of the recurrence phenomenon of weight evolution in training quantized deep networks.
Analysis and Optimal Edge Assignment For Hierarchical Federated Learning on Non-IID Data
Venue: arXiv cs.LG 2021
Year: 2021

Distributed learning algorithms aim to leverage distributed and diverse data stored at users' devices to learn a global phenomena by performing training amongst participating devices and periodically aggregating their local models' parameters into a global model. Federated learning is a promising paradigm that allows for extending local training among the participant devices before aggregating the parameters, offering better communication efficiency. However, in the cases where the participants' data are strongly skewed (i.e., non-IID), the local models can overfit local data, leading to low performing global model. In this paper, we first show that a major cause of the performance drop is the weighted distance between the distribution over classes on users' devices and the global distribution. Then, to face this challenge, we leverage the edge computing paradigm to design a hierarchical learning system that performs Federated Gradient Descent on the user-edge layer and Federated Averaging on the edge-cloud layer. In this hierarchical architecture, we formalize and optimize this user-edge assignment problem such that edge-level data distributions turn to be similar (i.e., close to IID), which enhances the Federated Averaging performance. Our experiments on multiple real-world datasets show that the proposed optimized assignment is tractable and leads to faster convergence of models towards a better accuracy value.
Longitudinal Citation Prediction using Temporal Graph Neural Networks
Venue: arXiv cs.CL 2021
Year: 2021

Citation count prediction is the task of predicting the number of citations a paper has gained after a period of time. Prior work viewed this as a static prediction task. As papers and their citations evolve over time, considering the dynamics of the number of citations a paper will receive would seem logical. Here, we introduce the task of sequence citation prediction. The goal is to accurately predict the trajectory of the number of citations a scholarly work receives over time. We propose to view papers as a structured network of citations, allowing us to use topological information as a learning signal. Additionally, we learn how this dynamic citation network changes over time and the impact of paper meta-data such as authors, venues and abstracts. To approach the new task, we derive a dynamic citation network from Semantic Scholar spanning over 42 years. We present a model which exploits topological and temporal information using graph convolution networks paired with sequence prediction, and compare it against multiple baselines, testing the importance of topological and temporal information and analyzing model performance. Our experiments show that leveraging both the temporal and topological information greatly increases the performance of predicting citation counts over time.
Deep-CR MTLR: a Multi-Modal Approach for Cancer Survival Prediction with Competing Risks
Venue: arXiv cs.LG 2021
Year: 2021

Accurate survival prediction is crucial for development of precision cancer medicine, creating the need for new sources of prognostic information. Recently, there has been significant interest in exploiting routinely collected clinical and medical imaging data to discover new prognostic markers in multiple cancer types. However, most of the previous studies focus on individual data modalities alone and do not make use of recent advances in machine learning for survival prediction. We present Deep-CR MTLR -- a novel machine learning approach for accurate cancer survival prediction from multi-modal clinical and imaging data in the presence of competing risks based on neural networks and an extension of the multi-task logistic regression framework. We demonstrate improved prognostic performance of the multi-modal approach over single modality predictors in a cohort of 2552 head and neck cancer patients, particularly for cancer specific survival, where our approach achieves 2-year AUROC of 0.774 and $C$-index of 0.788.
A Probabilistic Graphical Model Foundation for Enabling Predictive Digital Twins at Scale
Venue: arXiv cs.CE 2021
Year: 2021

A unifying mathematical formulation is needed to move from one-off digital twins built through custom implementations to robust digital twin implementations at scale. This work proposes a probabilistic graphical model as a formal mathematical representation of a digital twin and its associated physical asset. We create an abstraction of the asset-twin system as a set of coupled dynamical systems, evolving over time through their respective state-spaces and interacting via observed data and control inputs. The formal definition of this coupled system as a probabilistic graphical model enables us to draw upon well-established theory and methods from Bayesian statistics, dynamical systems, and control theory. The declarative and general nature of the proposed digital twin model make it rigorous yet flexible, enabling its application at scale in a diverse range of application areas. We demonstrate how the model is instantiated to enable a structural digital twin of an unmanned aerial vehicle (UAV). The digital twin is calibrated using experimental data from a physical UAV asset. Its use in dynamic decision making is then illustrated in a synthetic example where the UAV undergoes an in-flight damage event and the digital twin is dynamically updated using sensor data. The graphical model foundation ensures that the digital twin calibration and updating process is principled, unified, and able to scale to an entire fleet of digital twins.
Blending MPC & Value Function Approximation for Efficient Reinforcement Learning
Venue: arXiv cs.LG 2021
Year: 2021

Model-Predictive Control (MPC) is a powerful tool for controlling complex, real-world systems that uses a model to make predictions about future behavior. For each state encountered, MPC solves an online optimization problem to choose a control action that will minimize future cost. This is a surprisingly effective strategy, but real-time performance requirements warrant the use of simple models. If the model is not sufficiently accurate, then the resulting controller can be biased, limiting performance. We present a framework for improving on MPC with model-free reinforcement learning (RL). The key insight is to view MPC as constructing a series of local Q-function approximations. We show that by using a parameter $λ$, similar to the trace decay parameter in TD($λ$), we can systematically trade-off learned value estimates against the local Q-function approximations. We present a theoretical analysis that shows how error from inaccurate models in MPC and value function estimation in RL can be balanced. We further propose an algorithm that changes $λ$ over time to reduce the dependence on MPC as our estimates of the value function improve, and test the efficacy our approach on challenging high-dimensional manipulation tasks with biased models in simulation. We demonstrate that our approach can obtain performance comparable with MPC with access to true dynamics even under severe model bias and is more sample efficient as compared to model-free RL.