OpenRaiser/Intern-Atlas huggingface dataset:
Training Neural Networks is NP-Hard in Fixed Dimension
Venue: arXiv cs.CC 2024
Year: 2024

We study the parameterized complexity of training two-layer neural networks with respect to the dimension of the input data and the number of hidden neurons, considering ReLU and linear threshold activation functions. Albeit the computational complexity of these problems has been studied numerous times in recent years, several questions are still open. We answer questions by Arora et al. [ICLR '18] and Khalife and Basu [IPCO '22] showing that both problems are NP-hard for two dimensions, which excludes any polynomial-time algorithm for constant dimension. We also answer a question by Froese et al. [JAIR '22] proving W[1]-hardness for four ReLUs (or two linear threshold neurons) with zero training error. Finally, in the ReLU case, we show fixed-parameter tractability for the combined parameter number of dimensions and number of ReLUs if the network is assumed to compute a convex map. Our results settle the complexity status regarding these parameters almost completely.
CoSMo: a Framework to Instantiate Conditioned Process Simulation Models
Venue: arXiv cs.AI 2024
Year: 2024

Process simulation is gaining attention for its ability to assess potential performance improvements and risks associated with business process changes. The existing literature presents various techniques, generally grounded in process models discovered from event log data or built upon deep learning algorithms. These techniques have specific strengths and limitations. Traditional data-driven approaches offer increased interpretability, while deep learning-based excel at generalizing changes across large event logs. However, the practical application of deep learning faces challenges related to managing stochasticity and integrating information for what-if analysis. This paper introduces a novel recurrent neural architecture tailored to discover COnditioned process Simulation MOdels (CoSMo) based on user-based constraints or any other nature of a-priori knowledge. This architecture facilitates the simulation of event logs that adhere to specific constraints by incorporating declarative-based rules into the learning phase as an attempt to fill the gap of incorporating information into deep learning models to perform what-if analysis. Experimental validation illustrates CoSMo's efficacy in simulating event logs while adhering to predefined declarative conditions, emphasizing both control-flow and data-flow perspectives.
Applications of No-Collision Transportation Maps in Manifold Learning
Venue: arXiv cs.LG 2024
Year: 2024

In this work, we investigate applications of no-collision transportation maps introduced in [Nurbekyan et. al., 2020] in manifold learning for image data. Recently, there has been a surge in applying transportation-based distances and features for data representing motion-like or deformation-like phenomena. Indeed, comparing intensities at fixed locations often does not reveal the data structure. No-collision maps and distances developed in [Nurbekyan et. al., 2020] are sensitive to geometric features similar to optimal transportation (OT) maps but much cheaper to compute due to the absence of optimization. In this work, we prove that no-collision distances provide an isometry between translations (respectively dilations) of a single probability measure and the translation (respectively dilation) vectors equipped with a Euclidean distance. Furthermore, we prove that no-collision transportation maps, as well as OT and linearized OT maps, do not in general provide an isometry for rotations. The numerical experiments confirm our theoretical findings and show that no-collision distances achieve similar or better performance on several manifold learning tasks compared to other OT and Euclidean-based methods at a fraction of a computational cost.
Finding Pareto Efficient Redistricting Plans with Short Bursts
Venue: arXiv cs.CY 2024
Year: 2024

Redistricting practitioners must balance many competing constraints and criteria when drawing district boundaries. To aid in this process, researchers have developed many methods for optimizing districting plans according to one or more criteria. This research note extends a recently-proposed single-criterion optimization method, short bursts (Cannon et al., 2023), to handle the multi-criterion case, and in doing so approximate the Pareto frontier for any set of constraints. We study the empirical performance of the method in a realistic setting and find it behaves as expected and is not very sensitive to algorithmic parameters. The proposed approach, which is implemented in open-source software, should allow researchers and practitioners to better understand the tradeoffs inherent to the redistricting process.
SPAN: Learning Similarity between Scene Graphs and Images with Transformers
Venue: arXiv cs.CV 2024
Year: 2024

Learning similarity between scene graphs and images aims to estimate a similarity score given a scene graph and an image. There is currently no research dedicated to this task, although it is critical for scene graph generation and downstream applications. Scene graph generation is conventionally evaluated by Recall$@K$ and mean Recall$@K$, which measure the ratio of predicted triplets that appear in the human-labeled triplet set. However, such triplet-oriented metrics fail to demonstrate the overall semantic difference between a scene graph and an image and are sensitive to annotation bias and noise. Using generated scene graphs in the downstream applications is therefore limited. To address this issue, for the first time, we propose a Scene graPh-imAge coNtrastive learning framework, SPAN, that can measure the similarity between scene graphs and images. Our novel framework consists of a graph Transformer and an image Transformer to align scene graphs and their corresponding images in the shared latent space. We introduce a novel graph serialization technique that transforms a scene graph into a sequence with structural encodings. Based on our framework, we propose R-Precision measuring image retrieval accuracy as a new evaluation metric for scene graph generation. We establish new benchmarks on the Visual Genome and Open Images datasets. Extensive experiments are conducted to verify the effectiveness of SPAN, which shows great potential as a scene graph encoder.
A greedy approach for increased vehicle utilization in ridesharing networks
Venue: arXiv cs.DS 2024
Year: 2024

In recent years, ridesharing platforms have become a prominent mode of transportation for the residents of urban areas. As a fundamental problem, route recommendation for these platforms is vital for their sustenance. The works done in this direction have recommended routes with higher passenger demand. Despite the existing works, statistics have suggested that these services cause increased greenhouse emissions compared to private vehicles as they roam around in search of riders. This analysis provides finer details regarding the functionality of ridesharing systems and it reveals that in the face of their boom, they have not utilized the vehicle capacity efficiently. We propose to overcome the above limitations and recommend routes that will fetch multiple passengers simultaneously which will result in increased vehicle utilization and thereby decrease the effect of these systems on the environment. As route recommendation is NP-hard, we propose a k-hop-based sliding window approximation algorithm that reduces the search space from entire road network to a window. We further demonstrate that maximizing expected demand is submodular and greedy algorithms can be used to optimize our objective function within a window. We evaluate our proposed model on real-world datasets and experimental results demonstrate superior performance by our proposed model.
How Graph Structure and Label Dependencies Contribute to Node Classification in a Large Network of Documents
Venue: arXiv cs.LG 2024
Year: 2024

We introduce a new dataset named WikiVitals which contains a large graph of 48k mutually referred Wikipedia articles classified into 32 categories and connected by 2.3M edges. Our aim is to rigorously evaluate the contributions of three distinct sources of information to the label prediction in a semi-supervised node classification setting, namely the content of the articles, their connections with each other and the correlations among their labels. We perform this evaluation using a Graph Markov Neural Network which provides a theoretically principled model for this task and we conduct a detailed evaluation of the contributions of each sources of information using a clear separation of model selection and model assessment. One interesting observation is that including the effect of label dependencies is more relevant for sparse train sets than it is for dense train sets.
Mapping Degeneration Meets Label Evolution: Learning Infrared Small Target Detection with Single Point Supervision
Venue: arXiv cs.CV 2024
Year: 2024

Training a convolutional neural network (CNN) to detect infrared small targets in a fully supervised manner has gained remarkable research interests in recent years, but is highly labor expensive since a large number of per-pixel annotations are required. To handle this problem, in this paper, we make the first attempt to achieve infrared small target detection with point-level supervision. Interestingly, during the training phase supervised by point labels, we discover that CNNs first learn to segment a cluster of pixels near the targets, and then gradually converge to predict groundtruth point labels. Motivated by this "mapping degeneration" phenomenon, we propose a label evolution framework named label evolution with single point supervision (LESPS) to progressively expand the point label by leveraging the intermediate predictions of CNNs. In this way, the network predictions can finally approximate the updated pseudo labels, and a pixel-level target mask can be obtained to train CNNs in an end-to-end manner. We conduct extensive experiments with insightful visualizations to validate the effectiveness of our method. Experimental results show that CNNs equipped with LESPS can well recover the target masks from corresponding point labels, {and can achieve over 70% and 95% of their fully supervised performance in terms of pixel-level intersection over union (IoU) and object-level probability of detection (Pd), respectively. Code is available at https://github.com/XinyiYing/LESPS.
Untargeted Near-collision Attacks on Biometrics: Real-world Bounds and Theoretical Limits
Venue: arXiv cs.CR 2024
Year: 2024

A biometric recognition system can operate in two distinct modes: identification or verification. In the first mode, the system recognizes an individual by searching the enrolled templates of all the users for a match. In the second mode, the system validates a user's identity claim by comparing the fresh provided template with the enrolled template. The biometric transformation schemes usually produce binary templates that are better handled by cryptographic schemes, and the comparison is based on a distance that leaks information about the similarities between two biometric templates. Both the experimentally determined false match rate and false non-match rate through recognition threshold adjustment define the recognition accuracy, and hence the security of the system. To our knowledge, few works provide a formal treatment of security in case of minimal information leakage, i.e., the binary outcome of a comparison with a threshold. In this paper, we focus on untargeted attacks that can be carried out both online and offline, and in both identification and verification modes. On the first hand, we focus our analysis on the accuracy metrics of biometric systems. We provide the complexity of untargeted attacks using the False Match Rate (FMR) and the False Positive Identification Rate (FPIR) to address the security of these systems. Studying near-collisions with these metrics allows us to estimate the maximum number of users in a database, given a chosen FMR, to preserve the security and the accuracy. These results are evaluated on systems from the literature. On the other hand, we rely on probabilistic modelling to assess the theoretical security limits of biometric systems. The study of this metric space, and system parameters (template size, threshold and database size), gives us the complexity of untargeted attacks and the probability of a near-collision.
Incorporating Unlabelled Data into Bayesian Neural Networks
Venue: arXiv cs.LG 2024
Year: 2024

Conventional Bayesian Neural Networks (BNNs) are unable to leverage unlabelled data to improve their predictions. To overcome this limitation, we introduce Self-Supervised Bayesian Neural Networks, which use unlabelled data to learn models with suitable prior predictive distributions. This is achieved by leveraging contrastive pretraining techniques and optimising a variational lower bound. We then show that the prior predictive distributions of self-supervised BNNs capture problem semantics better than conventional BNN priors. In turn, our approach offers improved predictive performance over conventional BNNs, especially in low-budget regimes.
BugNIST -- a Large Volumetric Dataset for Object Detection under Domain Shift
Venue: arXiv cs.CV 2024
Year: 2024

Domain shift significantly influences the performance of deep learning algorithms, particularly for object detection within volumetric 3D images. Annotated training data is essential for deep learning-based object detection. However, annotating densely packed objects is time-consuming and costly. Instead, we suggest training models on individually scanned objects, causing a domain shift between training and detection data. To address this challenge, we introduce the BugNIST dataset, comprising 9154 micro-CT volumes of 12 bug types and 388 volumes of tightly packed bug mixtures. This dataset is characterized by having objects with the same appearance in the source and target domains, which is uncommon for other benchmark datasets for domain shift. During training, individual bug volumes labeled by class are utilized, while testing employs mixtures with center point annotations and bug type labels. Together with the dataset, we provide a baseline detection analysis, with the aim of advancing the field of 3D object detection methods.
Chasing Positive Bodies
Venue: arXiv cs.DS 2024
Year: 2024

We study the problem of chasing positive bodies in $\ell_1$: given a sequence of bodies $K_{t}=\{x^{t}\in\mathbb{R}_{+}^{n}\mid C^{t}x^{t}\geq 1,P^{t}x^{t}\leq 1\}$ revealed online, where $C^{t}$ and $P^{t}$ are nonnegative matrices, the goal is to (approximately) maintain a point $x_t \in K_t$ such that $\sum_t \|x_t - x_{t-1}\|_1$ is minimized. This captures the fully-dynamic low-recourse variant of any problem that can be expressed as a mixed packing-covering linear program and thus also the fractional version of many central problems in dynamic algorithms such as set cover, load balancing, hyperedge orientation, minimum spanning tree, and matching. We give an $O(\log d)$-competitive algorithm for this problem, where $d$ is the maximum row sparsity of any matrix $C^t$. This bypasses and improves exponentially over the lower bound of $\sqrt{n}$ known for general convex bodies. Our algorithm is based on iterated information projections, and, in contrast to general convex body chasing algorithms, is entirely memoryless. We also show how to round our solution dynamically to obtain the first fully dynamic algorithms with competitive recourse for all the stated problems above; i.e. their recourse is less than the recourse of every other algorithm on every update sequence, up to polylogarithmic factors. This is a significantly stronger notion than the notion of absolute recourse in the dynamic algorithms literature.
ERM++: An Improved Baseline for Domain Generalization
Venue: arXiv cs.LG 2024
Year: 2024

Domain Generalization (DG) aims to develop classifiers that can generalize to new, unseen data distributions, a critical capability when collecting new domain-specific data is impractical. A common DG baseline minimizes the empirical risk on the source domains. Recent studies have shown that this approach, known as Empirical Risk Minimization (ERM), can outperform most more complex DG methods when properly tuned. However, these studies have primarily focused on a narrow set of hyperparameters, neglecting other factors that can enhance robustness and prevent overfitting and catastrophic forgetting, properties which are critical for strong DG performance. In our investigation of training data utilization (i.e., duration and setting validation splits), initialization, and additional regularizers, we find that tuning these previously overlooked factors significantly improves model generalization across diverse datasets without adding much complexity. We call this improved, yet simple baseline ERM++. Despite its ease of implementation, ERM++ improves DG performance by over 5\% compared to prior ERM baselines on a standard benchmark of 5 datasets with a ResNet-50 and over 15\% with a ViT-B/16. It also outperforms all state-of-the-art methods on DomainBed datasets with both architectures. Importantly, ERM++ is easy to integrate into existing frameworks like DomainBed, making it a practical and powerful tool for researchers and practitioners. Overall, ERM++ challenges the need for more complex DG methods by providing a stronger, more reliable baseline that maintains simplicity and ease of use. Code is available at \url{https://github.com/piotr-teterwak/erm_plusplus}
Uncertainty estimation in Deep Learning for Panoptic segmentation
Venue: arXiv cs.CV 2024
Year: 2024

As deep learning-based computer vision algorithms continue to advance the state of the art, their robustness to real-world data continues to be an issue, making it difficult to bring an algorithm from the lab to the real world. Ensemble-based uncertainty estimation approaches such as Monte Carlo Dropout have been successfully used in many applications in an attempt to address this robustness issue. Unfortunately, it is not always clear if such ensemble-based approaches can be applied to a new problem domain. This is the case with panoptic segmentation, where the structure of the problem and architectures designed to solve it means that unlike image classification or even semantic segmentation, the typical solution of using a mean across samples cannot be directly applied. In this paper, we demonstrate how ensemble-based uncertainty estimation approaches such as Monte Carlo Dropout can be used in the panoptic segmentation domain with no changes to an existing network, providing both improved performance and more importantly a better measure of uncertainty for predictions made by the network. Results are demonstrated quantitatively and qualitatively on the COCO, KITTI-STEP and VIPER datasets.
Folklore Sampling is Optimal for Exact Hopsets: Confirming the $\sqrt{n}$ Barrier
Venue: arXiv cs.DS 2024
Year: 2024

For a graph $G$, a $D$-diameter-reducing exact hopset is a small set of additional edges $H$ that, when added to $G$, maintains its graph metric but guarantees that all node pairs have a shortest path in $G \cup H$ using at most $D$ edges. A shortcut set is the analogous concept for reachability. These objects have been studied since the early '90s due to applications in parallel, distributed, dynamic, and streaming graph algorithms. For most of their history, the state-of-the-art construction for either object was a simple folklore algorithm, based on randomly sampling nodes to hit long paths in the graph. However, recent breakthroughs of Kogan and Parter [SODA '22] and Bernstein and Wein [SODA '23] have finally improved over the folklore diameter bound of $\widetilde{O}(n^{1/2})$ for shortcut sets and for $(1+ε)$-approximate hopsets. For both objects it is now known that one can use $O(n)$ hop-edges to reduce diameter to $\widetilde{O}(n^{1/3})$. The only setting where folklore sampling remains unimproved is for exact hopsets. Can these improvements be continued? We settle this question negatively by constructing graphs on which any exact hopset of $O(n)$ edges has diameter $\widetildeΩ(n^{1/2})$. This improves on the previous lower bound of $\widetildeΩ(n^{1/3})$ by Kogan and Parter [FOCS '22]. Using similar ideas, we also polynomially improve the current lower bounds for shortcut sets, constructing graphs on which any shortcut set of $O(n)$ edges reduces diameter to $\widetildeΩ(n^{1/4})$. This improves on the previous lower bound of $Ω(n^{1/6})$ by Huang and Pettie [SIAM J. Disc. Math. '18]. We also extend our constructions to provide lower bounds against $O(p)$-size exact hopsets and shortcut sets for other values of $p$; in particular, we show that folklore sampling is near-optimal for exact hopsets in the entire range of $p \in [1, n^2]$.
Fair Ordering in Replicated Systems via Streaming Social Choice
Venue: arXiv cs.CR 2024
Year: 2024

Prior work studies the question of ``fairly'' ordering transactions in a replicated state machine. Each of $n$ replicas receives transactions in a possibly different order, and the system must aggregate the observed orderings into a single order. We argue that this problem is best viewed through the lens of social choice theory, in which (in the preference aggregation problem) rankings on candidates are aggregated into an election result. Two features make this problem novel. First, the number of transactions is unbounded, and an ordering must be defined over a countably infinite set. And second, decisions must be made quickly, with only partial information. Additionally, some faulty replicas might alter their reported observations; their influence on the output should be bounded and well understood. Prior work studies a ``$γ$-batch-order-fairness'' property, which divides an ordering into contiguous batches. If a $γ$ fraction of replicas receive $τ$ before $τ^\prime$, then $τ^\prime$ cannot be in an earlier batch than $τ$. We strengthen this definition to require that batches have minimal size ($γ$-batch-order-fairness can be vacuously satisfied by large batches) while accounting for the possibility of faulty replicas. This social choice lens enables an ordering protocol with strictly stronger fairness and liveness properties than prior work. We study the Ranked Pairs method. Analysis of how missing information moves through the algorithm allows our streaming version to know when it can output a transaction. Deliberate construction of a tiebreaking rule ensures our algorithm outputs a transaction after a bounded time (in a synchronous network). Prior work relies on a fixed choice of $γ$ and bound on the number of faulty replicas $f$, but our algorithm satisfies our definition for every $\frac{1}{2}<γ\leq 1$ simultaneously and for any $f$.
Analysis of Dynamic Voronoi Diagrams in the Hilbert Metric
Venue: arXiv cs.CG 2024
Year: 2024

The Hilbert metric is a projective metric defined on a convex body which generalizes the Cayley-Klein model of hyperbolic geometry to any convex set. In this paper we analyze Hilbert Voronoi diagrams in the Dynamic setting. In addition we introduce dynamic visualization software for Voronoi diagrams in the Hilbert metric on user specified convex polygons.