OpenRaiser/Intern-Atlas huggingface dataset:
Structural Measures of Resilience for Supply Chains
Venue: arXiv cs.SI 2024
Year: 2024

We investigate the structural factors that drive cascading failures in production networks, focusing on quantifying these risks with a topological resilience metric corresponding to the largest exogenous systemic shock that the production network can withstand, such that almost all of the network survives with high probability. We model failures using a node percolation process where systemic shocks cause suppliers to fail, leading to further breakdowns. We classify networks into two categories -- resilient and fragile -- based on their ability to handle shocks as the network grows large, and give bounds on their resilience. We show that the main factors affecting resilience are the number of raw products (primary sector), the number of final goods (final sector), and the source and supply dependencies. Further, we give methods to lower bound resilience based on bounding the cascade size with a linear program that can be efficiently calculated. We establish connections between our model, the independent cascade model, the Risk Exposure Index, and the Eisenberg-Noe contagion model. We give an almost linear-time deterministic algorithm to approximate the cascade size, which matches known lower bounds up to logarithmic factors. Finally, we design intervention algorithms and show that under reasonable assumptions, targeting nodes based on Katz centrality in the edge-reversed network is optimal. Finally, we account for network heterogeneities and validate our findings with real-world data.
LFM-3D: Learnable Feature Matching Across Wide Baselines Using 3D Signals
Venue: arXiv cs.CV 2024
Year: 2024

Finding localized correspondences across different images of the same object is crucial to understand its geometry. In recent years, this problem has seen remarkable progress with the advent of deep learning-based local image features and learnable matchers. Still, learnable matchers often underperform when there exists only small regions of co-visibility between image pairs (i.e. wide camera baselines). To address this problem, we leverage recent progress in coarse single-view geometry estimation methods. We propose LFM-3D, a Learnable Feature Matching framework that uses models based on graph neural networks and enhances their capabilities by integrating noisy, estimated 3D signals to boost correspondence estimation. When integrating 3D signals into the matcher model, we show that a suitable positional encoding is critical to effectively make use of the low-dimensional 3D information. We experiment with two different 3D signals - normalized object coordinates and monocular depth estimates - and evaluate our method on large-scale (synthetic and real) datasets containing object-centric image pairs across wide baselines. We observe strong feature matching improvements compared to 2D-only methods, with up to +6% total recall and +28% precision at fixed recall. Additionally, we demonstrate that the resulting improved correspondences lead to much higher relative posing accuracy for in-the-wild image pairs - up to 8.6% compared to the 2D-only approach.
Polyhedral Aspects of Feedback Vertex Set and Pseudoforest Deletion Set
Venue: arXiv cs.DS 2024
Year: 2024

We consider the feedback vertex set problem in undirected graphs (FVS). The input to FVS is an undirected graph $G=(V,E)$ with non-negative vertex costs. The goal is to find a minimum cost subset of vertices $S \subseteq V$ such that $G-S$ is acyclic. FVS is a well-known NP-hard problem and does not admit a $(2-ε)$-approximation for any fixed $ε> 0$ assuming the Unique Games Conjecture. There are combinatorial $2$-approximation algorithms and also primal-dual based $2$-approximations. Despite the existence of these algorithms for several decades, there is no known polynomial-time solvable LP relaxation for FVS with a provable integrality gap of at most $2$. More recent work (Chekuri and Madan, SODA '16) developed a polynomial-sized LP relaxation for a more general problem, namely Subset FVS, and showed that its integrality gap is at most $13$ for Subset FVS, and hence also for FVS. Motivated by this gap in our knowledge, we undertake a polyhedral study of FVS and related problems. In this work, we formulate new integer linear programs (ILPs) for FVS whose LP-relaxation can be solved in polynomial time, and whose integrality gap is at most $2$. The new insights in this process also enable us to prove that the formulation in (Chekuri and Madan, SODA '16) has an integrality gap of at most $2$ for FVS. Our results for FVS are inspired by new formulations and polyhedral results for the closely-related pseudoforest deletion set problem (PFDS). Our formulations for PFDS are in turn inspired by a connection to the densest subgraph problem. We also conjecture an extreme point property for a LP-relaxation for FVS, and give evidence for the conjecture via a corresponding result for PFDS.
The Innovation Paradox: Concept Space Expansion with Diminishing Originality and the Promise of Creative AI
Venue: arXiv cs.SI 2024
Year: 2024

Innovation, typically spurred by reusing, recombining, and synthesizing existing concepts, is expected to result in an exponential growth of the concept space over time. However, our statistical analysis of TechNet, which is a comprehensive technology semantic network encompassing over four million concepts derived from patent texts, reveals a linear rather than exponential expansion of the overall technological concept space. Moreover, there is a notable decline in the originality of newly created concepts. These trends can be attributed to the constraints of human cognitive abilities to innovate beyond an ever-growing space of prior art, among other factors. Integrating creative artificial intelligence (CAI) into the innovation process holds the potential to overcome these limitations and alter the observed trends in the future.
Medical diffusion on a budget: Textual Inversion for medical image generation
Venue: arXiv cs.CV 2024
Year: 2024

Diffusion models for text-to-image generation, known for their efficiency, accessibility, and quality, have gained popularity. While inference with these systems on consumer-grade GPUs is increasingly feasible, training from scratch requires large captioned datasets and significant computational resources. In medical image generation, the limited availability of large, publicly accessible datasets with text reports poses challenges due to legal and ethical concerns. This work shows that adapting pre-trained Stable Diffusion models to medical imaging modalities is achievable by training text embeddings using Textual Inversion. In this study, we experimented with small medical datasets (100 samples each from three modalities) and trained within hours to generate diagnostically accurate images, as judged by an expert radiologist. Experiments with Textual Inversion training and inference parameters reveal the necessity of larger embeddings and more examples in the medical domain. Classification experiments show an increase in diagnostic accuracy (AUC) for detecting prostate cancer on MRI, from 0.78 to 0.80. Further experiments demonstrate embedding flexibility through disease interpolation, combining pathologies, and inpainting for precise disease appearance control. The trained embeddings are compact (less than 1 MB), enabling easy data sharing with reduced privacy concerns.
Mining Clinical Notes for Physical Rehabilitation Exercise Information: Natural Language Processing Algorithm Development and Validation Study
Venue: arXiv cs.CL 2024
Year: 2024

Post-stroke patient rehabilitation requires precise, personalized treatment plans. Natural Language Processing (NLP) offers potential to extract valuable exercise information from clinical notes, aiding in the development of more effective rehabilitation strategies. Objective: This study aims to develop and evaluate a variety of NLP algorithms to extract and categorize physical rehabilitation exercise information from the clinical notes of post-stroke patients treated at the University of Pittsburgh Medical Center. A cohort of 13,605 patients diagnosed with stroke was identified, and their clinical notes containing rehabilitation therapy notes were retrieved. A comprehensive clinical ontology was created to represent various aspects of physical rehabilitation exercises. State-of-the-art NLP algorithms were then developed and compared, including rule-based, machine learning-based algorithms, and large language model (LLM)-based algorithms (ChatGPT). Analysis was conducted on a dataset comprising 23,724 notes with detailed demographic and clinical characteristics. The rule-based NLP algorithm demonstrated superior performance in most areas, particularly in detecting the 'Right Side' location with an F1 score of 0.975, outperforming Gradient Boosting by 0.063. Gradient Boosting excelled in 'Lower Extremity' location detection (F1 score: 0.978), surpassing rule-based NLP by 0.023. It also showed notable performance in 'Passive Range of Motion' with an F1 score of 0.970, a 0.032 improvement over rule-based NLP. The rule-based algorithm efficiently handled 'Duration', 'Sets', and 'Reps' with F1 scores up to 0.65. LLM-based NLP, particularly ChatGPT with few-shot prompts, achieved high recall but generally lower precision and F1 scores. However, it notably excelled in 'Backward Plane' motion detection, achieving an F1 score of 0.846, surpassing the rule-based algorithm's 0.720.
Promptable Game Models: Text-Guided Game Simulation via Masked Diffusion Models
Venue: arXiv cs.CV 2024
Year: 2024

Neural video game simulators emerged as powerful tools to generate and edit videos. Their idea is to represent games as the evolution of an environment's state driven by the actions of its agents. While such a paradigm enables users to play a game action-by-action, its rigidity precludes more semantic forms of control. To overcome this limitation, we augment game models with prompts specified as a set of natural language actions and desired states. The result-a Promptable Game Model (PGM)-makes it possible for a user to play the game by prompting it with high- and low-level action sequences. Most captivatingly, our PGM unlocks the director's mode, where the game is played by specifying goals for the agents in the form of a prompt. This requires learning "game AI", encapsulated by our animation model, to navigate the scene using high-level constraints, play against an adversary, and devise a strategy to win a point. To render the resulting state, we use a compositional NeRF representation encapsulated in our synthesis model. To foster future research, we present newly collected, annotated and calibrated Tennis and Minecraft datasets. Our method significantly outperforms existing neural video game simulators in terms of rendering quality and unlocks applications beyond the capabilities of the current state of the art. Our framework, data, and models are available at https://snap-research.github.io/promptable-game-models/.
Multi-Antenna Dual-Blind Deconvolution for Joint Radar-Communications via SoMAN Minimization
Venue: arXiv cs.IT 2024
Year: 2024

In joint radar-communications (JRC) applications such as secure military receivers, often the radar and communications signals are overlaid in the received signal. In these passive listening outposts, the signals and channels of both radar and communications are unknown to the receiver. The ill-posed problem of recovering all signal and channel parameters from the overlaid signal is termed as \textit{dual-blind deconvolution} (DBD). In this work, we investigate DBD for a multi-antenna receiver. We model the radar and communications channels with a few (sparse) \textit{continuous-valued} parameters such as time delays, Doppler velocities, and directions-of-arrival (DoAs). To solve this highly ill-posed DBD, we propose to minimize the sum of multivariate atomic norms (SoMAN) that depend on unknown parameters. To this end, we devise an exact semidefinite program using theories of positive hyperoctant trigonometric polynomials (PhTP). Our theoretical analyses show that the minimum number of samples and antennas required for perfect recovery is logarithmically dependent on the maximum of the number of radar targets and communications paths rather than their sum. We show that our approach is easily generalized to include several practical issues such as gain/phase errors and additive noise. Numerical experiments show the exact parameter recovery for different JRC scenarios.
An Optimization Model for Offline Scheduling Policy of Low-density Parity-check Codes
Venue: arXiv cs.IT 2024
Year: 2024

In this study, an optimization model for offline scheduling policy of low-density parity-check (LDPC) codes is proposed to improve the decoding efficiency of the belief propagation (BP). The optimization model uses the number of messages passed (NMP) as a metric to evaluate complexity, and two metrics, average entropy (AE), and gap to maximum a posteriori (GAP), to evaluate BP decoding performance. Based on this model, an algorithm is proposed to optimize the scheduling sequence for reduced decoding complexity and superior performance compared to layered BP. We validated the proposed algorithm on LDPC codes constructed following 5G New Radio, which resulted in a reduction of decoding complexity of more than 20$\%$ compared to LBP.
Edge-free but Structure-aware: Prototype-Guided Knowledge Distillation from GNNs to MLPs
Venue: arXiv cs.LG 2024
Year: 2024

Distilling high-accuracy Graph Neural Networks (GNNs) to low-latency multilayer perceptions (MLPs) on graph tasks has become a hot research topic. However, conventional MLP learning relies almost exclusively on graph nodes and fails to effectively capture the graph structural information. Previous methods address this issue by processing graph edges into extra inputs for MLPs, but such graph structures may be unavailable for various scenarios. To this end, we propose Prototype-Guided Knowledge Distillation (PGKD), which does not require graph edges (edge-free setting) yet learns structure-aware MLPs. Our insight is to distill graph structural information from GNNs. Specifically, we first employ the class prototypes to analyze the impact of graph structures on GNN teachers, and then design two losses to distill such information from GNNs to MLPs. Experimental results on popular graph benchmarks demonstrate the effectiveness and robustness of the proposed PGKD.
CompoNeRF: Text-guided Multi-object Compositional NeRF with Editable 3D Scene Layout
Venue: arXiv cs.CV 2024
Year: 2024

Text-to-3D form plays a crucial role in creating editable 3D scenes for AR/VR. Recent advances have shown promise in merging neural radiance fields (NeRFs) with pre-trained diffusion models for text-to-3D object generation. However, one enduring challenge is their inadequate capability to accurately parse and regenerate consistent multi-object environments. Specifically, these models encounter difficulties in accurately representing quantity and style prompted by multi-object texts, often resulting in a collapse of the rendering fidelity that fails to match the semantic intricacies. Moreover, amalgamating these elements into a coherent 3D scene is a substantial challenge, stemming from generic distribution inherent in diffusion models. To tackle the issue of 'guidance collapse' and further enhance scene consistency, we propose a novel framework, dubbed CompoNeRF, by integrating an editable 3D scene layout with object-specific and scene-wide guidance mechanisms. It initiates by interpreting a complex text into the layout populated with multiple NeRFs, each paired with a corresponding subtext prompt for precise object depiction. Next, a tailored composition module seamlessly blends these NeRFs, promoting consistency, while the dual-level text guidance reduces ambiguity and boosts accuracy. Noticeably, our composition design permits decomposition. This enables flexible scene editing and recomposition into new scenes based on the edited layout or text prompts. Utilizing the open-source Stable Diffusion model, CompoNeRF generates multi-object scenes with high fidelity. Remarkably, our framework achieves up to a \textbf{54\%} improvement by the multi-view CLIP score metric. Our user study indicates that our method has significantly improved semantic accuracy, multi-view consistency, and individual recognizability for multi-object scene generation.
'Team-in-the-loop': Ostrom's IAD framework 'rules in use' to map and measure contextual impacts of AI
Venue: arXiv cs.CY 2024
Year: 2024

This article explores how the 'rules in use' from Ostrom's Institutional Analysis and Development Framework (IAD) can be developed as a context analysis approach for AI. AI risk assessment frameworks increasingly highlight the need to understand existing contexts. However, these approaches do not frequently connect with established institutional analysis scholarship. We outline a novel direction illustrated through a high-level example to understand how clinical oversight is potentially impacted by AI. Much current thinking regarding oversight for AI revolves around the idea of decision makers being in-the-loop and, thus, having capacity to intervene to prevent harm. However, our analysis finds that oversight is complex, frequently made by teams of professionals and relies upon explanation to elicit information. Professional bodies and liability also function as institutions of polycentric oversight. These are all impacted by the challenge of oversight of AI systems. The approach outlined has potential utility as a policy tool of context analysis aligned with the 'Govern and Map' functions of the National Institute of Standards and Technology (NIST) AI Risk Management Framework; however, further empirical research is needed. Our analysis illustrates the benefit of existing institutional analysis approaches in foregrounding team structures within oversight and, thus, in conceptions of 'human in the loop'.
Spatially-aware station based car-sharing demand prediction
Venue: arXiv cs.LG 2024
Year: 2024

In recent years, car-sharing services have emerged as viable alternatives to private individual mobility, promising more sustainable and resource-efficient, but still comfortable transportation. Research on short-term prediction and optimization methods has improved operations and fleet control of car-sharing services; however, long-term projections and spatial analysis are sparse in the literature. We propose to analyze the average monthly demand in a station-based car-sharing service with spatially-aware learning algorithms that offer high predictive performance as well as interpretability. Our study utilizes a rich set of socio-demographic, location-based (e.g., POIs), and car-sharing-specific features as input, extracted from a large proprietary car-sharing dataset and publicly available datasets. We first compare the performance of different modeling approaches and find that a global Random Forest with geo-coordinates as part of input features achieves the highest predictive performance with an R-squared score of 0.87 on test data. While a local linear model, Geographically Weighted Regression, performs almost on par in terms of out-of-sample prediction accuracy. We further leverage the models to identify spatial and socio-demographic drivers of car-sharing demand. An analysis of the Random Forest via SHAP values, as well as the coefficients of GWR and MGWR models, reveals that besides population density and the car-sharing supply, other spatial features such as surrounding POIs play a major role. In addition, MGWR yields exciting insights into the multiscale heterogeneous spatial distributions of factors influencing car-sharing behaviour. Together, our study offers insights for selecting effective and interpretable methods for diagnosing and planning the placement of car-sharing stations.
A Survey on the Densest Subgraph Problem and Its Variants
Venue: arXiv cs.DS 2024
Year: 2024

The Densest Subgraph Problem requires to find, in a given graph, a subset of vertices whose induced subgraph maximizes a measure of density. The problem has received a great deal of attention in the algorithmic literature since the early 1970s, with many variants proposed and many applications built on top of this basic definition. Recent years have witnessed a revival of research interest in this problem with several important contributions, including some groundbreaking results, published in 2022 and 2023. This survey provides a deep overview of the fundamental results and an exhaustive coverage of the many variants proposed in the literature, with a special attention to the most recent results. The survey also presents a comprehensive overview of applications and discusses some interesting open problems for this evergreen research topic.
A Spatial-Constraint Model for Manipulating Static Visualizations
Venue: arXiv cs.HC 2024
Year: 2024

We propose a spatial-constraint approach for modeling spatial-based interactions and enabling interactive visualizations, which involves the manipulation of visualizations through selection, filtering, navigation, arrangement, and aggregation. We proposes a system that activates static visualizations by adding intelligent interactions, which is achieved by associating static visual objects with forces. Our force-directed technique facilitates smooth animated transitions of the visualizations between different interaction states. We showcase the effectiveness of our technique through usage scenarios that involve activating visualizations in real-world settings.
Saihu: A Common Interface of Worst-Case Delay Analysis Tools for Time-Sensitive Networks
Venue: arXiv cs.NI 2024
Year: 2024

Time-sensitive networks, as in the context of IEEE-TSN and IETF-Detnet, require bounds on worst-case delays. Various network analysis tools compute such bounds; these tools are based on different methods and provide delay bounds that are all valid but may differ; furthermore, it is generally not known which tool will provide the best bound. To obtain the best possible bound, users need to implement multiple pieces of code with a different syntax for every tool, which is impractical and error-prone. To address this issue, we present Saihu, a Python interface that integrates the three most frequently used worst-case network analysis tools: xTFA, DiscoDNC, and Panco. They altogether implement six analysis methods. Saihu provides a general interface that enables defining a network in a single file and executing all tools simultaneously without any modification. Saihu further exports analysis results as formatted reports automatically and allows quick generation of certain types of networks. With its simplified steps of execution, Saihu reduces the burden on users and makes it accessible for anyone working with time-sensitive networks.
Design and Control of a Small Humanoid Equipped with Flight Unit and Wheels for Multimodal Locomotion
Venue: arXiv cs.RO 2024
Year: 2024

Humanoids are versatile robotic platforms owing to their limbs with multiple degrees of freedom. Although humanoids can walk like humans, they are relatively slow, and cannot run over large barriers. To address these limitations, we aim to achieve rapid terrestrial locomotion ability and simultaneously expand the locomotion domain to the air by utilizing thrust for propulsion. In this paper, we first describe an optimized construction method for a humanoid robot equipped with wheels and a flight unit to achieve these abilities. Then, we describe the integrated control framework of the proposed flying humanoid for each locomotion mode: aerial, legged, and wheeled locomotion. Finally, we achieved multimodal locomotion and aerial manipulation experiments using the proposed robot platform. To the best of our knowledge, this is the first time that a single humanoid has simultaneously achieved three different types of locomotion, including flight.