OpenRaiser/Intern-Atlas huggingface dataset:
Learning Deformable 3D Graph Similarity to Track Plant Cells in Unregistered Time Lapse Images
Venue: arXiv cs.CV 2023
Year: 2023

Tracking of plant cells in images obtained by microscope is a challenging problem due to biological phenomena such as large number of cells, non-uniform growth of different layers of the tightly packed plant cells and cell division. Moreover, images in deeper layers of the tissue being noisy and unavoidable systemic errors inherent in the imaging process further complicates the problem. In this paper, we propose a novel learning-based method that exploits the tightly packed three-dimensional cell structure of plant cells to create a three-dimensional graph in order to perform accurate cell tracking. We further propose novel algorithms for cell division detection and effective three-dimensional registration, which improve upon the state-of-the-art algorithms. We demonstrate the efficacy of our algorithm in terms of tracking accuracy and inference-time on a benchmark dataset.
Beamforming Design for RIS-Aided THz Wideband Communication Systems
Venue: arXiv cs.IT 2023
Year: 2023

Benefiting from tens of GHz of bandwidth, terahertz (THz) communications has become a promising technology for future 6G networks. However, the conventional hybrid beamforming architecture based on frequency-independent phase-shifters is not able to cope with the beam split effect (BSE) in THz massive multiple-input multiple-output (MIMO) systems. Despite some work introducing the frequency-dependent phase shifts via the time delay network to mitigate the beam splitting in THz wideband communications, the corresponding issue in reconfigurable intelligent surface (RIS)-aided communications has not been well investigated. In this paper, the BSE in THz massive MIMO is quantified by analyzing the array gain loss. A new beamforming architecture has been proposed to mitigate this effect under RIS-aided communications scenarios. Simulations are performed to evaluate the effectiveness of the proposed system architecture in combating the array gain loss.
Relational Expressions for Data Transformation and Computation
Venue: arXiv cs.DB 2023
Year: 2023

Separate programming models for data transformation (declarative) and computation (procedural) impact programmer ergonomics, code reusability and database efficiency. To eliminate the necessity for two models or paradigms, we propose a small but high-leverage innovation: the introduction of complete relations into the relational database. Complete relations and the discipline of constraint programming, which concerns them, are founded on the same algebra as relational databases. We claim that by synthesising the relational database of Codd and Date, with the results of the constraint programming community, the relational model holistically offers programmers a single declarative paradigm for both data transformation and computation, reusable code with computations that are indifferent to what is input and what is output, and efficient applications with the query engine optimising and parallelising all levels of data transformation and computation.
When to Trust AI: Advances and Challenges for Certification of Neural Networks
Venue: arXiv cs.LG 2023
Year: 2023

Artificial intelligence (AI) has been advancing at a fast pace and it is now poised for deployment in a wide range of applications, such as autonomous systems, medical diagnosis and natural language processing. Early adoption of AI technology for real-world applications has not been without problems, particularly for neural networks, which may be unstable and susceptible to adversarial examples. In the longer term, appropriate safety assurance techniques need to be developed to reduce potential harm due to avoidable system failures and ensure trustworthiness. Focusing on certification and explainability, this paper provides an overview of techniques that have been developed to ensure safety of AI decisions and discusses future challenges.
Retrieve-Rewrite-Answer: A KG-to-Text Enhanced LLMs Framework for Knowledge Graph Question Answering
Venue: arXiv cs.CL 2023
Year: 2023

Despite their competitive performance on knowledge-intensive tasks, large language models (LLMs) still have limitations in memorizing all world knowledge especially long tail knowledge. In this paper, we study the KG-augmented language model approach for solving the knowledge graph question answering (KGQA) task that requires rich world knowledge. Existing work has shown that retrieving KG knowledge to enhance LLMs prompting can significantly improve LLMs performance in KGQA. However, their approaches lack a well-formed verbalization of KG knowledge, i.e., they ignore the gap between KG representations and textual representations. To this end, we propose an answer-sensitive KG-to-Text approach that can transform KG knowledge into well-textualized statements most informative for KGQA. Based on this approach, we propose a KG-to-Text enhanced LLMs framework for solving the KGQA task. Experiments on several KGQA benchmarks show that the proposed KG-to-Text augmented LLMs approach outperforms previous KG-augmented LLMs approaches regarding answer accuracy and usefulness of knowledge statements.
Towards a Prediction of Machine Learning Training Time to Support Continuous Learning Systems Development
Venue: arXiv cs.LG 2023
Year: 2023

The problem of predicting the training time of machine learning (ML) models has become extremely relevant in the scientific community. Being able to predict a priori the training time of an ML model would enable the automatic selection of the best model both in terms of energy efficiency and in terms of performance in the context of, for instance, MLOps architectures. In this paper, we present the work we are conducting towards this direction. In particular, we present an extensive empirical study of the Full Parameter Time Complexity (FPTC) approach by Zheng et al., which is, to the best of our knowledge, the only approach formalizing the training time of ML models as a function of both dataset's and model's parameters. We study the formulations proposed for the Logistic Regression and Random Forest classifiers, and we highlight the main strengths and weaknesses of the approach. Finally, we observe how, from the conducted study, the prediction of training time is strictly related to the context (i.e., the involved dataset) and how the FPTC approach is not generalizable.
Trace Monomial Boolean Functions with Large High-Order Nonlinearities
Venue: arXiv cs.CR 2023
Year: 2023

Exhibiting an explicit Boolean function with a large high-order nonlinearity is an important problem in cryptography, coding theory, and computational complexity. We prove lower bounds on the second-order, third-order, and higher-order nonlinearities of some trace monomial Boolean functions. We prove lower bounds on the second-order nonlinearities of functions $\mathrm{tr}_n(x^7)$ and $\mathrm{tr}_n(x^{2^r+3})$ where $n=2r$. Among all trace monomials, our bounds match the best second-order nonlinearity lower bounds by \cite{Car08} and \cite{YT20} for odd and even $n$ respectively. We prove a lower bound on the third-order nonlinearity for functions $\mathrm{tr}_n(x^{15})$, which is the best third-order nonlinearity lower bound. For any $r$, we prove that the $r$-th order nonlinearity of $\mathrm{tr}_n(x^{2^{r+1}-1})$ is at least $2^{n-1}-2^{(1-2^{-r})n+\frac{r}{2^{r-1}}-1}- O(2^{\frac{n}{2}})$. For $r \ll \log_2 n$, this is the best lower bound among all explicit functions.
Colour Passing Revisited: Lifted Model Construction with Commutative Factors
Venue: arXiv cs.AI 2023
Year: 2023

Lifted probabilistic inference exploits symmetries in a probabilistic model to allow for tractable probabilistic inference with respect to domain sizes. To apply lifted inference, a lifted representation has to be obtained, and to do so, the so-called colour passing algorithm is the state of the art. The colour passing algorithm, however, is bound to a specific inference algorithm and we found that it ignores commutativity of factors while constructing a lifted representation. We contribute a modified version of the colour passing algorithm that uses logical variables to construct a lifted representation independent of a specific inference algorithm while at the same time exploiting commutativity of factors during an offline-step. Our proposed algorithm efficiently detects more symmetries than the state of the art and thereby drastically increases compression, yielding significantly faster online query times for probabilistic inference when the resulting model is applied.
Integrating Visual Foundation Models for Enhanced Robot Manipulation and Motion Planning: A Layered Approach
Venue: arXiv cs.RO 2023
Year: 2023

This paper presents a novel layered framework that integrates visual foundation models to improve robot manipulation tasks and motion planning. The framework consists of five layers: Perception, Cognition, Planning, Execution, and Learning. Using visual foundation models, we enhance the robot's perception of its environment, enabling more efficient task understanding and accurate motion planning. This approach allows for real-time adjustments and continual learning, leading to significant improvements in task execution. Experimental results demonstrate the effectiveness of the proposed framework in various robot manipulation tasks and motion planning scenarios, highlighting its potential for practical deployment in dynamic environments.
A Game-theoretic Approach for Provably-Uniform Random Number Generation in Decentralized Networks
Venue: arXiv cs.CR 2023
Year: 2023

Many protocols in distributed computing rely on a source of randomness, usually called a random beacon, both for their applicability and security. This is especially true for proof-of-stake blockchain protocols in which the next miner or set of miners have to be chosen randomly and each party's likelihood to be selected is in proportion to their stake in the cryptocurrency. Current random beacons used in proof-of-stake protocols, such as Ouroboros and Algorand, have two fundamental limitations: Either (i)~they rely on pseudorandomness, e.g.~assuming that the output of a hash function is uniform, which is a widely-used but unproven assumption, or (ii)~they generate their randomness using a distributed protocol in which several participants are required to submit random numbers which are then used in the generation of a final random result. However, in this case, there is no guarantee that the numbers provided by the parties are uniformly random and there is no incentive for the parties to honestly generate uniform randomness. Most random beacons have both limitations. In this thesis, we provide a protocol for distributed generation of randomness. Our protocol does not rely on pseudorandomness at all. Similar to some of the previous approaches, it uses random inputs by different participants to generate a final random result. However, the crucial difference is that we provide a game-theoretic guarantee showing that it is in everyone's best interest to submit uniform random numbers. Hence, our approach is the first to incentivize honest behavior instead of just assuming it. Moreover, the approach is trustless and generates unbiased random numbers. It is also tamper-proof and no party can change the output or affect its distribution. Finally, it is designed with modularity in mind and can be easily plugged into existing distributed protocols such as proof-of-stake blockchains.
Data Exfiltration by Hotjar Revisited
Venue: arXiv cs.CY 2023
Year: 2023

Session replay scripts allow website owners to record the interaction of each web site visitor and aggregate the interaction to reveal the interests and problems of the visitors. However, previous research identified such techniques as privacy intrusive. This position paper updates the information on data collection by Hotjar. It revisits the previous findings to detect and describe the changes. The default policy to gather inputs changed; the recording script gathers only information from explicitly allowed input elements. Nevertheless, Hotjar does record content reflecting users' behaviour outside input HTML elements. Even though we propose changes that would prevent the leakage of the reflected content, we argue that such changes will most likely not appear in practice. The paper discusses improvements in handling TLS. Not only do web page operators interact with Hotjar through encrypted connections, but Hotjar scripts do not work on sites not protected by TLS. Hotjar respects the Do Not Track signal; however, users need to connect to Hotjar even in the presence of the Do Not Track setting. Worse, malicious web operators can trick Hotjar into recording sessions of users with the active Do Not Track setting. Finally, we propose and motivate the extension of GDPR Art. 25 obligations to processors.
Parameterized Algorithms for Scalable Interprocedural Data-flow Analysis
Venue: arXiv cs.PL 2023
Year: 2023

Data-flow analysis is a general technique used to compute information of interest at different points of a program and is considered to be a cornerstone of static analysis. In this thesis, we consider interprocedural data-flow analysis as formalized by the standard IFDS framework, which can express many widely-used static analyses such as reaching definitions, live variables, and null-pointer. We focus on the well-studied on-demand setting in which queries arrive one-by-one in a stream and each query should be answered as fast as possible. While the classical IFDS algorithm provides a polynomial-time solution to this problem, it is not scalable in practice. Specifically, it either requires a quadratic-time preprocessing phase or takes linear time per query, both of which are untenable for modern huge codebases with hundreds of thousands of lines. Previous works have already shown that parameterizing the problem by the treewidth of the program's control-flow graph is promising and can lead to significant gains in efficiency. Unfortunately, these results were only applicable to the limited special case of same-context queries. In this work, we obtain significant speedups for the general case of on-demand IFDS with queries that are not necessarily same-context. This is achieved by exploiting a new graph sparsity parameter, namely the treedepth of the program's call graph. Our approach is the first to exploit the sparsity of control-flow graphs and call graphs at the same time and parameterize by both treewidth and treedepth. We obtain an algorithm with a linear preprocessing phase that can answer each query in constant time with respect to the input size. Finally, we show experimental results demonstrating that our approach significantly outperforms the classical IFDS and its on-demand variant.
Generalizing Across Domains in Diabetic Retinopathy via Variational Autoencoders
Venue: arXiv cs.CV 2023
Year: 2023

Domain generalization for Diabetic Retinopathy (DR) classification allows a model to adeptly classify retinal images from previously unseen domains with various imaging conditions and patient demographics, thereby enhancing its applicability in a wide range of clinical environments. In this study, we explore the inherent capacity of variational autoencoders to disentangle the latent space of fundus images, with an aim to obtain a more robust and adaptable domain-invariant representation that effectively tackles the domain shift encountered in DR datasets. Despite the simplicity of our approach, we explore the efficacy of this classical method and demonstrate its ability to outperform contemporary state-of-the-art approaches for this task using publicly available datasets. Our findings challenge the prevailing assumption that highly sophisticated methods for DR classification are inherently superior for domain generalization. This highlights the importance of considering simple methods and adapting them to the challenging task of generalizing medical images, rather than solely relying on advanced techniques.
Memory-Anonymous Starvation-Free Mutual Exclusion: Possibility and Impossibility Results
Venue: arXiv cs.DC 2023
Year: 2023

In an anonymous shared memory system, all inter-process communications are via shared objects; however, unlike in standard systems, there is no a priori agreement between processes on the names of shared objects [14,15]. Furthermore, the algorithms are required to be symmetric; that is, the processes should execute precisely the same code, and the only way to distinguish processes is by comparing identifiers for equality. For such a system, read/write registers are called anonymous registers. It is known that symmetric deadlock-free mutual exclusion is solvable for any finite number of processes using anonymous registers [1]. The main question left open in [14,15] is the existence of starvation-free mutual exclusion algorithms for two or more processes. We resolve this open question for memoryless algorithms, in which a process that tries to enter its critical section does not use any information about its previous attempts. Almost all known mutual exclusion algorithms are memoryless. We show that (1) there is a symmetric memoryless starvation-free mutual exclusion algorithm for two processes using $m \geq 7$ anonymous registers if and only if $m$ is odd; and (2) there is no symmetric memoryless starvation-free mutual exclusion algorithm for $n\geq 3$ processes using (any number of) anonymous registers. Our impossibility result is the only example of a system with fault-free processes, where global progress (i.e., deadlock-freedom) can be ensured, while individual progress to each process (i.e., starvation-freedom) cannot. It complements a known result for systems with failure-prone processes, that there are objects with lock-free implementations but without wait-free implementations [2,5].
Better Sooner Rather Than Later
Venue: arXiv cs.DC 2023
Year: 2023

This article unifies and generalizes fundamental results related to $n$-process asynchronous crash-prone distributed computing. More precisely, it proves that for every $0\leq k \leq n$, assuming that process failures occur only before the number of participating processes bypasses a predefined threshold that equals $n-k$ (a participating process is a process that has executed at least one statement of its code), an asynchronous algorithm exists that solves consensus for $n$ processes in the presence of $f$ crash failures if and only if $f \leq k$. In a very simple and interesting way, the "extreme" case $k=0$ boils down to the celebrated FLP impossibility result (1985, 1987). Moreover, the second extreme case, namely $k=n$, captures the celebrated mutual exclusion result by E.W. Dijkstra (1965) that states that mutual exclusion can be solved for $n$ processes in an asynchronous read/write shared memory system where any number of processes may crash (but only) before starting to participate in the algorithm (that is, participation is not required, but once a process starts participating it may not fail). More generally, the possibility/impossibility stated above demonstrates that more failures can be tolerated when they occur earlier in the computation (hence the title).
Is Ethereum Proof of Stake Sustainable? $-$ Considering from the Perspective of Competition Among Smart Contract Platforms $-$
Venue: arXiv cs.CY 2023
Year: 2023

Since the Merge update upon which Ethereum transitioned to Proof of Stake, it has been touted that it resulted in lower power consumption and increased security. However, even if that is the case, can this state be sustained? In this paper, we focus on the potential impact of competition with other smart contract platforms on the price of Ethereum's native currency, Ether (ETH), thereby raising questions about the safety and sustainability purportedly brought about by the design of Proof of Stake.
Signature Activation: A Sparse Signal View for Holistic Saliency
Venue: arXiv cs.CV 2023
Year: 2023

The adoption of machine learning in healthcare calls for model transparency and explainability. In this work, we introduce Signature Activation, a saliency method that generates holistic and class-agnostic explanations for Convolutional Neural Network (CNN) outputs. Our method exploits the fact that certain kinds of medical images, such as angiograms, have clear foreground and background objects. We give theoretical explanation to justify our methods. We show the potential use of our method in clinical settings through evaluating its efficacy for aiding the detection of lesions in coronary angiograms.
Using deep learning to construct stochastic local search SAT solvers with performance bounds
Venue: arXiv cs.AI 2023
Year: 2023

The Boolean Satisfiability problem (SAT) is the most prototypical NP-complete problem and of great practical relevance. One important class of solvers for this problem are stochastic local search (SLS) algorithms that iteratively and randomly update a candidate assignment. Recent breakthrough results in theoretical computer science have established sufficient conditions under which SLS solvers are guaranteed to efficiently solve a SAT instance, provided they have access to suitable "oracles" that provide samples from an instance-specific distribution, exploiting an instance's local structure. Motivated by these results and the well established ability of neural networks to learn common structure in large datasets, in this work, we train oracles using Graph Neural Networks and evaluate them on two SLS solvers on random SAT instances of varying difficulty. We find that access to GNN-based oracles significantly boosts the performance of both solvers, allowing them, on average, to solve 17% more difficult instances (as measured by the ratio between clauses and variables), and to do so in 35% fewer steps, with improvements in the median number of steps of up to a factor of 8. As such, this work bridges formal results from theoretical computer science and practically motivated research on deep learning for constraint satisfaction problems and establishes the promise of purpose-trained SAT solvers with performance guarantees.
NeighViz: Towards Better Understanding of Neighborhood Effects on Social Groups with Spatial Data
Venue: arXiv cs.HC 2023
Year: 2023

Understanding how local environments influence individual behaviors, such as voting patterns or suicidal tendencies, is crucial in social science to reveal and reduce spatial disparities and promote social well-being. With the increasing availability of large-scale individual-level census data, new analytical opportunities arise for social scientists to explore human behaviors (e.g., political engagement) among social groups at a fine-grained level. However, traditional statistical methods mostly focus on global, aggregated spatial correlations, which are limited to understanding and comparing the impact of local environments (e.g., neighborhoods) on human behaviors among social groups. In this study, we introduce a new analytical framework for analyzing multi-variate neighborhood effects between social groups. We then propose NeighVi, an interactive visual analytics system that helps social scientists explore, understand, and verify the influence of neighborhood effects on human behaviors. Finally, we use a case study to illustrate the effectiveness and usability of our system.