OpenRaiser/Intern-Atlas huggingface dataset:
Federated Causal Discovery From Interventions
Venue: arXiv cs.LG 2024
Year: 2024

Causal discovery serves a pivotal role in mitigating model uncertainty through recovering the underlying causal mechanisms among variables. In many practical domains, such as healthcare, access to the data gathered by individual entities is limited, primarily for privacy and regulatory constraints. However, the majority of existing causal discovery methods require the data to be available in a centralized location. In response, researchers have introduced federated causal discovery. While previous federated methods consider distributed observational data, the integration of interventional data remains largely unexplored. We propose FedCDI, a federated framework for inferring causal structures from distributed data containing interventional samples. In line with the federated learning framework, FedCDI improves privacy by exchanging belief updates rather than raw samples. Additionally, it introduces a novel intervention-aware method for aggregating individual updates. We analyze scenarios with shared or disjoint intervened covariates, and mitigate the adverse effects of interventional data heterogeneity. The performance and scalability of FedCDI is rigorously tested across a variety of synthetic and real-world graphs.
Distribution Grid Monitoring Based on Widely Available Smart Plugs
Venue: arXiv cs.NI 2024
Year: 2024

The growing popularity of e-mobility, heat pumps, and renewable generation such as photovoltaics is leading to scenarios which the distribution grid was not originally designed for. Moreover, parts of the distribution grid are only sparsely instrumented, leaving the distribution system operator unaware of possible bottlenecks resulting from the introduction of such loads and renewable generation. To overcome this lack of information, we propose the use of widely available smart home devices, such as smart plugs, for grid monitoring. We detail the aggregation and storage of smart plug measurements for distribution grid monitoring and examine the accuracy of the measurements. A case study shows how the average monitoring error in a distribution grid area decreases the more measurement devices are installed. Hence, simple smart plugs can help with distribution grid monitoring and provide valuable information to the DSO.
Towards Measuring the Traceability of Cryptocurrencies
Venue: arXiv cs.CR 2024
Year: 2024

Cryptocurrencies aim to replicate physical cash in the digital realm while removing centralized and trusted intermediaries. Decentralization is achieved by the blockchain, a permanent public ledger that contains a record of every transaction. The public ledger ensures transparency, which enables public verifiability but harms untraceability, fungibility, and anonymity. In the last decade, cryptocurrencies attracted millions of users, with their total market cap reaching approximately three trillion USD at its peak. However, their anonymity guarantees are poorly understood and plagued by widespread misbeliefs. Indeed, previous notions of privacy, anonymity, and traceability for cryptocurrencies are either non-quantitative or inapplicable, e.g., computationally hard to measure. In this work, we put forward a formal framework to measure the (un)traceability and anonymity of cryptocurrencies, allowing us to quantitatively reason about the mixing characteristics of cryptocurrencies and the privacy-enhancing technologies built on top of them. Our methods apply absorbing Markov chains combined with Shannon entropy. To the best of our knowledge, our work provides the first practical, efficient, and probabilistic measure to assess the traceability of cryptocurrencies quantitatively, which also generalizes to entire cryptocurrency transaction graphs. We implement and extensively evaluate our proposed traceability measure on several cryptocurrency transaction graphs. Among other quantitative results, we find that in the studied one-week interval, the Bitcoin blockchain, on average, provided comparable but quantifiably more natural mixing than the Ethereum blockchain.
Review of coreference resolution in English and Persian
Venue: arXiv cs.CL 2024
Year: 2024

Coreference resolution (CR), identifying expressions referring to the same real-world entity, is a fundamental challenge in natural language processing (NLP). This paper explores the latest advancements in CR, spanning coreference and anaphora resolution. We critically analyze the diverse corpora that have fueled CR research, highlighting their strengths, limitations, and suitability for various tasks. We examine the spectrum of evaluation metrics used to assess CR systems, emphasizing their advantages, disadvantages, and the need for more nuanced, task-specific metrics. Tracing the evolution of CR algorithms, we provide a detailed overview of methodologies, from rule-based approaches to cutting-edge deep learning architectures. We delve into mention-pair, entity-based, cluster-ranking, sequence-to-sequence, and graph neural network models, elucidating their theoretical foundations and performance on benchmark datasets. Recognizing the unique challenges of Persian CR, we dedicate a focused analysis to this under-resourced language. We examine existing Persian CR systems and highlight the emergence of end-to-end neural models leveraging pre-trained language models like ParsBERT. This review is an essential resource for researchers and practitioners, offering a comprehensive overview of the current state-of-the-art in CR, identifying key challenges, and charting a course for future research in this rapidly evolving field.
On Instance-Optimal Algorithms for a Generalization of Nuts and Bolts and Generalized Sorting
Venue: arXiv cs.DS 2024
Year: 2024

We generalize the classical nuts and bolts problem to a setting where the input is a collection of $n$ nuts and $m$ bolts, and there is no promise of any matching pairs. It is not allowed to compare a nut directly with a nut or a bolt directly with a bolt, and the goal is to perform the fewest nut-bolt comparisons to discover the partial order between the nuts and bolts. We term this problem \emph{bipartite sorting}. We show that instances of bipartite sorting of the same size exhibit a wide range of complexity, and propose to perform a fine-grained analysis for this problem. We rule out straightforward notions of instance-optimality as being too stringent, and adopt a \emph{neighborhood-based} definition. Our definition may be of independent interest as a unifying lens for instance-optimal algorithms for other static problems existing in literature. This includes problems like sorting (Estivill-Castro and Woods, ACM Comput. Surv. 1992), convex hull (Afshani, Barbay and Chan, JACM 2017), adaptive joins (Demaine, López-Ortiz and Munro, SODA 2000), and the recent concept of universal optimality for graphs (Haeupler, Hladík, Rozhoň, Tarjan and Tětek, 2023). As our main result on bipartite sorting, we give a randomized algorithm that is within a factor of $O(\log ^3 (n+m))$ of being instance-optimal w.h.p., with respect to the neighborhood-based definition. As our second contribution, we generalize bipartite sorting to DAG sorting, when the underlying DAG is not necessarily bipartite. As an unexpected consequence of a simple algorithm for DAG sorting, we rule out a potential lower bound on the widely-studied problem of \emph{sorting with priced information}, posed by (Charikar, Fagin, Guruswami, Kleinberg, Raghavan and Sahai, STOC 2000).
Almost Tight Error Bounds on Differentially Private Continual Counting
Venue: arXiv cs.LG 2024
Year: 2024

The first large-scale deployment of private federated learning uses differentially private counting in the continual release model as a subroutine (Google AI blog titled "Federated Learning with Formal Differential Privacy Guarantees"). In this case, a concrete bound on the error is very relevant to reduce the privacy parameter. The standard mechanism for continual counting is the binary mechanism. We present a novel mechanism and show that its mean squared error is both asymptotically optimal and a factor 10 smaller than the error of the binary mechanism. We also show that the constants in our analysis are almost tight by giving non-asymptotic lower and upper bounds that differ only in the constants of lower-order terms. Our algorithm is a matrix mechanism for the counting matrix and takes constant time per release. We also use our explicit factorization of the counting matrix to give an upper bound on the excess risk of the private learning algorithm of Denisov et al. (NeurIPS 2022). Our lower bound for any continual counting mechanism is the first tight lower bound on continual counting under approximate differential privacy. It is achieved using a new lower bound on a certain factorization norm, denoted by $γ_F(\cdot)$, in terms of the singular values of the matrix. In particular, we show that for any complex matrix, $A \in \mathbb{C}^{m \times n}$, \[ γ_F(A) \geq \frac{1}{\sqrt{m}}\|A\|_1, \] where $\|\cdot \|$ denotes the Schatten-1 norm. We believe this technique will be useful in proving lower bounds for a larger class of linear queries. To illustrate the power of this technique, we show the first lower bound on the mean squared error for answering parity queries.
Stochastic Network Calculus with Localized Application of Martingales
Venue: arXiv cs.PF 2024
Year: 2024

Stochastic Network Calculus is a probabilistic method to compute performance bounds in networks, such as end-to-end delays. It relies on the analysis of stochastic processes using formalism of (Deterministic) Network Calculus. However, unlike the deterministic theory, the computed bounds are usually very loose compared to the simulation. This is mainly due to the intensive use of the Boole's inequality. On the other hand, analyses based on martingales can achieve tight bounds, but until now, they have not been applied to sequences of servers. In this paper, we improve the accuracy of Stochastic Network Calculus by combining this martingale analysis with a recent Stochastic Network Calculus results based on the Pay-Multiplexing-Only-Once property, well-known from the Deterministic Network calculus. We exhibit a non-trivial class of networks that can benefit from this analysis and compare our bounds with simulation.
pyRDDLGym: From RDDL to Gym Environments
Venue: arXiv cs.AI 2024
Year: 2024

We present pyRDDLGym, a Python framework for auto-generation of OpenAI Gym environments from RDDL declerative description. The discrete time step evolution of variables in RDDL is described by conditional probability functions, which fits naturally into the Gym step scheme. Furthermore, since RDDL is a lifted description, the modification and scaling up of environments to support multiple entities and different configurations becomes trivial rather than a tedious process prone to errors. We hope that pyRDDLGym will serve as a new wind in the reinforcement learning community by enabling easy and rapid development of benchmarks due to the unique expressive power of RDDL. By providing explicit access to the model in the RDDL description, pyRDDLGym can also facilitate research on hybrid approaches for learning from interaction while leveraging model knowledge. We present the design and built-in examples of pyRDDLGym, and the additions made to the RDDL language that were incorporated into the framework.
CCPrefix: Counterfactual Contrastive Prefix-Tuning for Many-Class Classification
Venue: arXiv cs.CL 2024
Year: 2024

Recently, prefix-tuning was proposed to efficiently adapt pre-trained language models to a broad spectrum of natural language classification tasks. It leverages soft prefix as task-specific indicators and language verbalizers as categorical-label mentions to narrow the formulation gap from pre-training language models. However, when the label space increases considerably (i.e., many-class classification), such a tuning technique suffers from a verbalizer ambiguity problem since the many-class labels are represented by semantic-similar verbalizers in short language phrases. To overcome this, inspired by the human-decision process that the most ambiguous classes would be mulled over for each instance, we propose a brand-new prefix-tuning method, Counterfactual Contrastive Prefix-tuning (CCPrefix), for many-class classification. Basically, an instance-dependent soft prefix, derived from fact-counterfactual pairs in the label space, is leveraged to complement the language verbalizers in many-class classification. We conduct experiments on many-class benchmark datasets in both the fully supervised setting and the few-shot setting, which indicates that our model outperforms former baselines.
Dynamic Curing and Network Design in SIS Epidemic Processes
Venue: arXiv cs.DS 2024
Year: 2024

This paper studies efficient algorithms for dynamic curing policies and the corresponding network design problems to guarantee the fast extinction of epidemic spread in a susceptible-infected-susceptible (SIS) model. We consider a Markov process-based SIS epidemic model. We provide a computationally efficient curing algorithm based on the curing policy proposed by Drakopoulos, Ozdaglar, and Tsitsiklis (2014). Since the corresponding optimization problem is NP-hard, finding optimal policies is intractable for large graphs. We provide approximation guarantees on the curing budget of the proposed dynamic curing algorithm. We also present a curing algorithm fair to demographic groups. When the total infection rate is high, the original curing policy includes a waiting period in which no measure is taken to mitigate the spread until the rate slows down. To avoid the waiting period, we study network design problems to reduce the total infection rate by deleting edges or reducing the weight of edges. Then the curing processes become continuous since the total infection rate is restricted by network design. We provide algorithms with provable guarantees for the considered network design problems. In summary, the proposed curing and network design algorithms together provide an effective and computationally efficient approach that mitigates SIS epidemic spread in networks.
An Adaptive and Stability-Promoting Layerwise Training Approach for Sparse Deep Neural Network Architecture
Venue: arXiv cs.LG 2024
Year: 2024

This work presents a two-stage adaptive framework for progressively developing deep neural network (DNN) architectures that generalize well for a given training data set. In the first stage, a layerwise training approach is adopted where a new layer is added each time and trained independently by freezing parameters in the previous layers. We impose desirable structures on the DNN by employing manifold regularization, sparsity regularization, and physics-informed terms. We introduce a epsilon-delta stability-promoting concept as a desirable property for a learning algorithm and show that employing manifold regularization yields a epsilon-delta stability-promoting algorithm. Further, we also derive the necessary conditions for the trainability of a newly added layer and investigate the training saturation problem. In the second stage of the algorithm (post-processing), a sequence of shallow networks is employed to extract information from the residual produced in the first stage, thereby improving the prediction accuracy. Numerical investigations on prototype regression and classification problems demonstrate that the proposed approach can outperform fully connected DNNs of the same size. Moreover, by equipping the physics-informed neural network (PINN) with the proposed adaptive architecture strategy to solve partial differential equations, we numerically show that adaptive PINNs not only are superior to standard PINNs but also produce interpretable hidden layers with provable stability. We also apply our architecture design strategy to solve inverse problems governed by elliptic partial differential equations.
Pilot-Aided Distributed Multi-Group Multicast Precoding Design for Cell-Free Massive MIMO
Venue: arXiv cs.IT 2024
Year: 2024

We propose fully distributed multi-group multicast precoding designs for cell-free massive multiple-input multiple-output (MIMO) systems with modest training overhead. We target the minimization of the sum of the maximum mean squared errors (MSEs) over the multicast groups, which is then approximated with a weighted sum MSE minimization to simplify the computation and signaling. To design the joint network-wide multi-group multicast precoders at the base stations (BSs) and the combiners at the user equipments (UEs) in a fully distributed fashion, we adopt an iterative bi-directional training scheme with UE-specific or group-specific precoded uplink pilots and group-specific precoded downlink pilots. To this end, we introduce a new group-specific uplink training resource that entirely eliminates the need for backhaul signaling for the channel state information (CSI) exchange. The precoders are optimized locally at each BS by means of either best-response or gradient-based updates, and the convergence of the two approaches is analyzed with respect to the centralized implementation with perfect CSI. Finally, numerical results show that the proposed distributed methods greatly outperform conventional cell-free massive MIMO precoding designs that rely solely on local CSI.
Assessing Uncertainty in Similarity Scoring: Performance & Fairness in Face Recognition
Venue: arXiv cs.CV 2024
Year: 2024

The ROC curve is the major tool for assessing not only the performance but also the fairness properties of a similarity scoring function. In order to draw reliable conclusions based on empirical ROC analysis, accurately evaluating the uncertainty level related to statistical versions of the ROC curves of interest is absolutely necessary, especially for applications with considerable societal impact such as Face Recognition. In this article, we prove asymptotic guarantees for empirical ROC curves of similarity functions as well as for by-product metrics useful to assess fairness. We also explain that, because the false acceptance/rejection rates are of the form of U-statistics in the case of similarity scoring, the naive bootstrap approach may jeopardize the assessment procedure. A dedicated recentering technique must be used instead. Beyond the theoretical analysis carried out, various experiments using real face image datasets provide strong empirical evidence of the practical relevance of the methods promoted here, when applied to several ROC-based measures such as popular fairness metrics.
Shellability is hard even for balls
Venue: arXiv cs.CG 2024
Year: 2024

The main goal of this paper is to show that shellability is NP-hard for triangulated d-balls (this also gives hardness for triangulated d-manifolds/d-pseudomanifolds with boundary) as soon as d is at least 3. This extends our earlier work with Goaoc, Patáková and Wagner on hardness of shellability of 2-complexes and answers some questions implicitly raised by Danaraj and Klee in 1978 and explicitly mentioned by Santamaría-Galvis and Woodroofe. Together with the main goal, we also prove that collapsibility is NP-hard for 3-complexes embeddable in the 3-space, extending an earlier work of the second author and answering an open question mentioned by Cohen, Fasy, Miller, Nayyeri, Peng and Walkington; and that shellability is NP-hard for 2-complexes embeddable in the 3-space, answering another question of Santamaría-Galvis and Woodroofe (in a slightly stronger form than what is given by the main result).
UniHPF : Universal Healthcare Predictive Framework with Zero Domain Knowledge
Venue: arXiv cs.LG 2024
Year: 2024

Despite the abundance of Electronic Healthcare Records (EHR), its heterogeneity restricts the utilization of medical data in building predictive models. To address this challenge, we propose Universal Healthcare Predictive Framework (UniHPF), which requires no medical domain knowledge and minimal pre-processing for multiple prediction tasks. Experimental results demonstrate that UniHPF is capable of building large-scale EHR models that can process any form of medical data from distinct EHR systems. We believe that our findings can provide helpful insights for further research on the multi-source learning of EHRs.
CorruptEncoder: Data Poisoning based Backdoor Attacks to Contrastive Learning
Venue: arXiv cs.CR 2024
Year: 2024

Contrastive learning (CL) pre-trains general-purpose encoders using an unlabeled pre-training dataset, which consists of images or image-text pairs. CL is vulnerable to data poisoning based backdoor attacks (DPBAs), in which an attacker injects poisoned inputs into the pre-training dataset so the encoder is backdoored. However, existing DPBAs achieve limited effectiveness. In this work, we take the first step to analyze the limitations of existing backdoor attacks and propose new DPBAs called CorruptEncoder to CL. CorruptEncoder introduces a new attack strategy to create poisoned inputs and uses a theory-guided method to maximize attack effectiveness. Our experiments show that CorruptEncoder substantially outperforms existing DPBAs. In particular, CorruptEncoder is the first DPBA that achieves more than 90% attack success rates with only a few (3) reference images and a small poisoning ratio 0.5%. Moreover, we also propose a defense, called localized cropping, to defend against DPBAs. Our results show that our defense can reduce the effectiveness of DPBAs, but it sacrifices the utility of the encoder, highlighting the need for new defenses.
Keeping it sparse: Computing Persistent Homology revisited
Venue: arXiv cs.CG 2024
Year: 2024

In this work, we study several variants of matrix reduction via Gaussian elimination that try to keep the reduced matrix sparse. The motivation comes from the growing field of topological data analysis where matrix reduction is the major subroutine to compute barcodes, the main invariant therein. We propose two novel variants of the standard algorithm, called swap and retrospective reductions. We test them on a large collection of data against other known variants to compare their efficiency, and we find that sometimes they provide a considerable speed-up. We also present novel output-sensitive bounds for the retrospective variant which better explain the discrepancy between the cubic worst-case complexity bound and the almost linear practical behavior of matrix reduction. Finally, we provide several constructions on which one of the variants performs strictly better than the others.
ArcAid: Analysis of Archaeological Artifacts using Drawings
Venue: arXiv cs.CV 2024
Year: 2024

Archaeology is an intriguing domain for computer vision. It suffers not only from shortage in (labeled) data, but also from highly-challenging data, which is often extremely abraded and damaged. This paper proposes a novel semi-supervised model for classification and retrieval of images of archaeological artifacts. This model utilizes unique data that exists in the domain -- manual drawings made by special artists. These are used during training to implicitly transfer the domain knowledge from the drawings to their corresponding images, improving their classification results. We show that while learning how to classify, our model also learns how to generate drawings of the artifacts, an important documentation task, which is currently performed manually. Last but not least, we collected a new dataset of stamp-seals of the Southern Levant. Our code and dataset are publicly available.
Completeness in static analysis by abstract interpretation, a personal point of view
Venue: arXiv cs.PL 2024
Year: 2024

Static analysis by abstract interpretation is generally designed to be "sound", that is, it should not claim to establish properties that do not hold-in other words, not provide "false negatives" about possible bugs. A rarer requirement is that it should be "complete", meaning that it should be able to infer certain properties if they hold. This paper describes a number of practical issues and questions related to completeness that I have come across over the years.