OpenRaiser/Intern-Atlas huggingface dataset:
Digging Into Normal Incorporated Stereo Matching
Venue: arXiv cs.CV 2024
Year: 2024

Despite the remarkable progress facilitated by learning-based stereo-matching algorithms, disparity estimation in low-texture, occluded, and bordered regions still remains a bottleneck that limits the performance. To tackle these challenges, geometric guidance like plane information is necessary as it provides intuitive guidance about disparity consistency and affinity similarity. In this paper, we propose a normal incorporated joint learning framework consisting of two specific modules named non-local disparity propagation(NDP) and affinity-aware residual learning(ARL). The estimated normal map is first utilized for calculating a non-local affinity matrix and a non-local offset to perform spatial propagation at the disparity level. To enhance geometric consistency, especially in low-texture regions, the estimated normal map is then leveraged to calculate a local affinity matrix, providing the residual learning with information about where the correction should refer and thus improving the residual learning efficiency. Extensive experiments on several public datasets including Scene Flow, KITTI 2015, and Middlebury 2014 validate the effectiveness of our proposed method. By the time we finished this work, our approach ranked 1st for stereo matching across foreground pixels on the KITTI 2015 dataset and 3rd on the Scene Flow dataset among all the published works.
Image2Flow: A hybrid image and graph convolutional neural network for rapid patient-specific pulmonary artery segmentation and CFD flow field calculation from 3D cardiac MRI data
Venue: arXiv cs.CV 2024
Year: 2024

Computational fluid dynamics (CFD) can be used for evaluation of hemodynamics. However, its routine use is limited by labor-intensive manual segmentation, CFD mesh creation, and time-consuming simulation. This study aims to train a deep learning model to both generate patient-specific volume-meshes of the pulmonary artery from 3D cardiac MRI data and directly estimate CFD flow fields. This study used 135 3D cardiac MRIs from both a public and private dataset. The pulmonary arteries in the MRIs were manually segmented and converted into volume-meshes. CFD simulations were performed on ground truth meshes and interpolated onto point-point correspondent meshes to create the ground truth dataset. The dataset was split 85/10/15 for training, validation and testing. Image2Flow, a hybrid image and graph convolutional neural network, was trained to transform a pulmonary artery template to patient-specific anatomy and CFD values. Image2Flow was evaluated in terms of segmentation and accuracy of CFD predicted was assessed using node-wise comparisons. Centerline comparisons of Image2Flow and CFD simulations performed using machine learning segmentation were also performed. Image2Flow achieved excellent segmentation accuracy with a median Dice score of 0.9 (IQR: 0.86-0.92). The median node-wise normalized absolute error for pressure and velocity magnitude was 11.98% (IQR: 9.44-17.90%) and 8.06% (IQR: 7.54-10.41), respectively. Centerline analysis showed no significant difference between the Image2Flow and conventional CFD simulated on machine learning-generated volume-meshes. This proof-of-concept study has shown it is possible to simultaneously perform patient specific volume-mesh based segmentation and pressure and flow field estimation. Image2Flow completes segmentation and CFD in ~205ms, which ~7000 times faster than manual methods, making it more feasible in a clinical environment.
Lower Bounds for Leaf Rank of Leaf Powers
Venue: arXiv cs.DM 2024
Year: 2024

Leaf powers and $k$-leaf powers have been studied for over 20 years, but there are still several aspects of this graph class that are poorly understood. One such aspect is the leaf rank of leaf powers, i.e. the smallest number $k$ such that a graph $G$ is a $k$-leaf power. Computing the leaf rank of leaf powers has proved a hard task, and furthermore, results about the asymptotic growth of the leaf rank as a function of the number of vertices in the graph have been few and far between. We present an infinite family of rooted directed path graphs that are leaf powers, and prove that they have leaf rank exponential in the number of vertices (utilizing a type of subtree model first presented by Rautenbach [Some remarks about leaf roots. Discrete mathematics, 2006]). This answers an open question by Brandstädt et al. [Rooted directed path graphs are leaf powers. Discrete mathematics, 2010].
Max-Cut with $ε$-Accurate Predictions
Venue: arXiv cs.DS 2024
Year: 2024

We study the approximability of the MaxCut problem in the presence of predictions. Specifically, we consider two models: in the noisy predictions model, for each vertex we are given its correct label in $\{-1,+1\}$ with some unknown probability $1/2 + ε$, and the other (incorrect) label otherwise. In the more-informative partial predictions model, for each vertex we are given its correct label with probability $ε$ and no label otherwise. We assume only pairwise independence between vertices in both models. We show how these predictions can be used to improve on the worst-case approximation ratios for this problem. Specifically, we give an algorithm that achieves an $α+ \widetildeΩ(ε^4)$-approximation for the noisy predictions model, where $α\approx 0.878$ is the MaxCut threshold. While this result also holds for the partial predictions model, we can also give a $β+ Ω(ε)$-approximation, where $β\approx 0.858$ is the approximation ratio for MaxBisection given by Raghavendra and Tan. This answers a question posed by Ola Svensson in his plenary session talk at SODA'23.
Output-Sensitive Enumeration of Potential Maximal Cliques in Polynomial Space
Venue: arXiv cs.DS 2024
Year: 2024

A set of vertices in a graph forms a potential maximal clique if there exists a minimal chordal completion in which it is a maximal clique. Potential maximal cliques were first introduced as a key tool to obtain an efficient, though exponential-time algorithm to compute the treewidth of a graph. As a byproduct, this allowed to compute the treewidth of various graph classes in polynomial time. In recent years, the concept of potential maximal cliques regained interest as it proved to be useful for a handful of graph algorithmic problems. In particular, it turned out to be a key tool to obtain a polynomial time algorithm for computing maximum weight independent sets in $P_5$-free and $P_6$-free graphs (Lokshtanov et al., SODA `14 and Grzeskik et al., SODA `19. In most of their applications, obtaining all the potential maximal cliques constitutes an algorithmic bottleneck, thus motivating the question of how to efficiently enumerate all the potential maximal cliques in a graph $G$. The state-of-the-art algorithm by Bouchitté \& Todinca can enumerate potential maximal cliques in output-polynomial time by using exponential space, a significant limitation for the size of feasible instances. In this paper, we revisit this algorithm and design an enumeration algorithm that preserves an output-polynomial time complexity while only requiring polynomial space.
Fractional Linear Matroid Matching is in quasi-NC
Venue: arXiv cs.CC 2024
Year: 2024

The matching and linear matroid intersection problems are solvable in quasi-NC, meaning that there exist deterministic algorithms that run in polylogarithmic time and use quasi-polynomially many parallel processors. However, such a parallel algorithm is unknown for linear matroid matching, which generalizes both of these problems. In this work, we propose a quasi-NC algorithm for fractional linear matroid matching, which is a relaxation of linear matroid matching and commonly generalizes fractional matching and linear matroid intersection. Our algorithm builds upon the connection of fractional matroid matching to non-commutative Edmonds' problem recently revealed by Oki and Soma~(2023). As a corollary, we also solve black-box non-commutative Edmonds' problem with rank-two skew-symmetric coefficients.
FSL-Rectifier: Rectify Outliers in Few-Shot Learning via Test-Time Augmentation
Venue: arXiv cs.CV 2024
Year: 2024

Few-shot learning (FSL) commonly requires a model to identify images (queries) that belong to classes unseen during training, based on a few labelled samples of the new classes (support set) as reference. So far, plenty of algorithms involve training data augmentation to improve the generalization capability of FSL models, but outlier queries or support images during inference can still pose great generalization challenges. In this work, to reduce the bias caused by the outlier samples, we generate additional test-class samples by combining original samples with suitable train-class samples via a generative image combiner. Then, we obtain averaged features via an augmentor, which leads to more typical representations through the averaging. We experimentally and theoretically demonstrate the effectiveness of our method, obtaining a test accuracy improvement proportion of around 10\% (e.g., from 46.86\% to 53.28\%) for trained FSL models. Importantly, given a pretrained image combiner, our method is training-free for off-the-shelf FSL models, whose performance can be improved without extra datasets nor further training of the models themselves. Codes are available at https://github.com/WendyBaiYunwei/FSL-Rectifier-Pub.
Quantification and Modeling of Broken Links Prevalence in Hyper Traffic Websites Homepages
Venue: arXiv cs.CR 2024
Year: 2024

Broken links in websites external resources pose a serious threat to cybersecurity and the credibility of websites. They can be hijacked to eavesdrop user traffic or to inject malicious software. In this paper, we present the first result of an ongoing research. We focus on the prevalence of broken links in external resources on home pages of the most visited websites in the world. The analysis was conducted on the top 88 000 homepages extracted from the Majestic Million rankings. 35,2% of them have at least one broken link. We also identify the common causes of these broken links and highlight improper implementation of testing phases to prevent such errors. We provide a formal model for the distribution of external links. At the next research step, we are exploring the potential impact on privacy of broken links by analyzing inherited traffic of purchasable expired domains.
Enhancing Roadway Safety: LiDAR-based Tree Clearance Analysis
Venue: arXiv cs.CV 2024
Year: 2024

In the efforts for safer roads, ensuring adequate vertical clearance above roadways is of great importance. Frequently, trees or other vegetation is growing above the roads, blocking the sight of traffic signs and lights and posing danger to traffic participants. Accurately estimating this space from simple images proves challenging due to a lack of depth information. This is where LiDAR technology comes into play, a laser scanning sensor that reveals a three-dimensional perspective. Thus far, LiDAR point clouds at the street level have mainly been used for applications in the field of autonomous driving. These scans, however, also open up possibilities in urban management. In this paper, we present a new point cloud algorithm that can automatically detect those parts of the trees that grow over the street and need to be trimmed. Our system uses semantic segmentation to filter relevant points and downstream processing steps to create the required volume to be kept clear above the road. Challenges include obscured stretches of road, the noisy unstructured nature of LiDAR point clouds, and the assessment of the road shape. The identified points of non-compliant trees can be projected from the point cloud onto images, providing municipalities with a visual aid for dealing with such occurrences. By automating this process, municipalities can address potential road space constraints, enhancing safety for all. They may also save valuable time by carrying out the inspections more systematically. Our open-source code gives communities inspiration on how to automate the process themselves.
Equivalent Environments and Covering Spaces for Robots
Venue: arXiv cs.RO 2024
Year: 2024

This paper formally defines a robot system, including its sensing and actuation components, as a general, topological dynamical system. The focus is on determining general conditions under which various environments in which the robot can be placed are indistinguishable. A key result is that, under very general conditions, covering maps witness such indistinguishability. This formalizes the intuition behind the well studied loop closure problem in robotics. An important special case is where the sensor mapping reports an invariant of the local topological (metric) structure of an environment because such structure is preserved by (metric) covering maps. Whereas coverings provide a sufficient condition for the equivalence of environments, we also give a necessary condition using bisimulation. The overall framework is applied to unify previously identified phenomena in robotics and related fields, in which moving agents with sensors must make inferences about their environments based on limited data. Many open problems are identified.
When Should Algorithms Resign? A Proposal for AI Governance
Venue: arXiv cs.CY 2024
Year: 2024

Algorithmic resignation is a strategic approach for managing the use of artificial intelligence (AI) by embedding governance directly into AI systems. It involves deliberate and informed disengagement from AI, such as restricting access AI outputs or displaying performance disclaimers, in specific scenarios to aid the appropriate and effective use of AI. By integrating algorithmic resignation as a governance mechanism, organizations can better control when and how AI is used, balancing the benefits of automation with the need for human oversight.
Robust Synthetic Data-Driven Detection of Living-Off-the-Land Reverse Shells
Venue: arXiv cs.CR 2024
Year: 2024

Living-off-the-land (LOTL) techniques pose a significant challenge to security operations, exploiting legitimate tools to execute malicious commands that evade traditional detection methods. To address this, we present a robust augmentation framework for cyber defense systems as Security Information and Event Management (SIEM) solutions, enabling the detection of LOTL attacks such as reverse shells through machine learning. Leveraging real-world threat intelligence and adversarial training, our framework synthesizes diverse malicious datasets while preserving the variability of legitimate activity, ensuring high accuracy and low false-positive rates. We validate our approach through extensive experiments on enterprise-scale datasets, achieving a 90\% improvement in detection rates over non-augmented baselines at an industry-grade False Positive Rate (FPR) of $10^{-5}$. We define black-box data-driven attacks that successfully evade unprotected models, and develop defenses to mitigate them, producing adversarially robust variants of ML models. Ethical considerations are central to this work; we discuss safeguards for synthetic data generation and the responsible release of pre-trained models across four best performing architectures, including both adversarially and regularly trained variants: https://huggingface.co/dtrizna/quasarnix. Furthermore, we provide a malicious LOTL dataset containing over 1 million augmented attack variants to enable reproducible research and community collaboration: https://huggingface.co/datasets/dtrizna/QuasarNix. This work offers a reproducible, scalable, and production-ready defense against evolving LOTL threats.
Detecting Anti-vaccine Content on Twitter using Multiple Message-Based Network Representations
Venue: arXiv cs.SI 2024
Year: 2024

Social media platforms such as Twitter have a fundamental role in facilitating the spread and discussion of ideas online through the concept of retweeting and replying. However, these features also contribute to the spread of mis/disinformation during the vaccine rollout of the COVID-19 pandemic. Using COVID-19 vaccines as a case study, we analyse multiple social network representation derived from three message-based interactions on Twitter (quote retweets, mentions and replies) based upon a set of known anti-vax hashtags and keywords. Each network represents a certain hashtag or keyword which were labelled as "controversial" and "non-controversial" according to a small group of participants. For each network, we extract a combination of global and local network-based metrics which are used as feature vectors for binary classification. Our results suggest that it is possible to detect controversial from non-controversial terms with high accuracy using simple network-based metrics. Furthermore, these results demonstrate the potential of network representations as language-agnostic models for detecting mis/disinformation at scale, irrespective of content and across multiple social media platforms.
The First Place Solution of WSDM Cup 2024: Leveraging Large Language Models for Conversational Multi-Doc QA
Venue: arXiv cs.CL 2024
Year: 2024

Conversational multi-doc question answering aims to answer specific questions based on the retrieved documents as well as the contextual conversations. In this paper, we introduce our winning approach for the "Conversational Multi-Doc QA" challenge in WSDM Cup 2024, which exploits the superior natural language understanding and generation capability of Large Language Models (LLMs). We first adapt LLMs to the task, then devise a hybrid training strategy to make the most of in-domain unlabeled data. Moreover, an advanced text embedding model is adopted to filter out potentially irrelevant documents and several approaches are designed and compared for the model ensemble. Equipped with all these techniques, our solution finally ranked 1st place in WSDM Cup 2024, surpassing its rivals to a large extent. The source codes have been released at https://github.com/zhangzhao219/WSDM-Cup-2024.
A Modular System for Enhanced Robustness of Multimedia Understanding Networks via Deep Parametric Estimation
Venue: arXiv cs.CV 2024
Year: 2024

In multimedia understanding tasks, corrupted samples pose a critical challenge, because when fed to machine learning models they lead to performance degradation. In the past, three groups of approaches have been proposed to handle noisy data: i) enhancer and denoiser modules to improve the quality of the noisy data, ii) data augmentation approaches, and iii) domain adaptation strategies. All the aforementioned approaches come with drawbacks that limit their applicability; the first has high computational costs and requires pairs of clean-corrupted data for training, while the others only allow deployment of the same task/network they were trained on (\ie, when upstream and downstream task/network are the same). In this paper, we propose SyMPIE to solve these shortcomings. To this end, we design a small, modular, and efficient (just 2GFLOPs to process a Full HD image) system to enhance input data for robust downstream multimedia understanding with minimal computational cost. Our SyMPIE is pre-trained on an upstream task/network that should not match the downstream ones and does not need paired clean-corrupted samples. Our key insight is that most input corruptions found in real-world tasks can be modeled through global operations on color channels of images or spatial filters with small kernels. We validate our approach on multiple datasets and tasks, such as image classification (on ImageNetC, ImageNetC-Bar, VizWiz, and a newly proposed mixed corruption benchmark named ImageNetC-mixed) and semantic segmentation (on Cityscapes, ACDC, and DarkZurich) with consistent improvements of about 5\% relative accuracy gain across the board. The code of our approach and the new ImageNetC-mixed benchmark will be made available upon publication.
Take It, Leave It, or Fix It: Measuring Productivity and Trust in Human-AI Collaboration
Venue: arXiv cs.HC 2024
Year: 2024

Although recent developments in generative AI have greatly enhanced the capabilities of conversational agents such as Google's Gemini (formerly Bard) or OpenAI's ChatGPT, it's unclear whether the usage of these agents aids users across various contexts. To better understand how access to conversational AI affects productivity and trust, we conducted a mixed-methods, task-based user study, observing 76 software engineers (N=76) as they completed a programming exam with and without access to Bard. Effects on performance, efficiency, satisfaction, and trust vary depending on user expertise, question type (open-ended "solve" vs. definitive "search" questions), and measurement type (demonstrated vs. self-reported). Our findings include evidence of automation complacency, increased reliance on the AI over the course of the task, and increased performance for novices on "solve"-type questions when using the AI. We discuss common behaviors, design recommendations, and impact considerations to improve collaborations with conversational AI.
RNNs are not Transformers (Yet): The Key Bottleneck on In-context Retrieval
Venue: arXiv cs.LG 2024
Year: 2024

This paper investigates the gap in representation powers of Recurrent Neural Networks (RNNs) and Transformers in the context of solving algorithmic problems. We focus on understanding whether RNNs, known for their memory efficiency in handling long sequences, can match the performance of Transformers, particularly when enhanced with Chain-of-Thought (CoT) prompting. Our theoretical analysis reveals that CoT improves RNNs but is insufficient to close the gap with Transformers. A key bottleneck lies in the inability of RNNs to perfectly retrieve information from the context, even with CoT: for several tasks that explicitly or implicitly require this capability, such as associative recall and determining if a graph is a tree, we prove that RNNs are not expressive enough to solve the tasks while Transformers can solve them with ease. Conversely, we prove that adopting techniques to enhance the in-context retrieval capability of RNNs, including Retrieval-Augmented Generation (RAG) and adding a single Transformer layer, can elevate RNNs to be capable of solving all polynomial-time solvable problems with CoT, hence closing the representation gap with Transformers.
Energy-Aware Heterogeneous Federated Learning via Approximate DNN Accelerators
Venue: arXiv cs.AR 2024
Year: 2024

In Federated Learning (FL), devices that participate in the training usually have heterogeneous resources, i.e., energy availability. In current deployments of FL, devices that do not fulfill certain hardware requirements are often dropped from the collaborative training. However, dropping devices in FL can degrade training accuracy and introduce bias or unfairness. Several works have tackled this problem on an algorithm level, e.g., by letting constrained devices train a subset of the server neural network (NN) model. However, it has been observed that these techniques are not effective w.r.t. accuracy. Importantly, they make simplistic assumptions about devices' resources via indirect metrics such as multiply accumulate (MAC) operations or peak memory requirements. We observe that memory access costs (that are currently not considered in simplistic metrics) have a significant impact on the energy consumption. In this work, for the first time, we consider on-device accelerator design for FL with heterogeneous devices. We utilize compressed arithmetic formats and approximate computing, targeting to satisfy limited energy budgets. Using a hardware-aware energy model, we observe that, contrary to the state of the art's moderate energy reduction, our technique allows for lowering the energy requirements (by 4x) while maintaining higher accuracy.