OpenRaiser/Intern-Atlas huggingface dataset:
Groupoidal Realizability for Intensional Type Theory
Venue: arXiv cs.LO 2024
Year: 2024

We develop realizability models of intensional type theory, based on groupoids, wherein realizers themselves carry non-trivial (non-discrete) homotopical structure. In the spirit of realizability, this is intended to formalize a homotopical BHK interpretation, whereby evidence for an identification is a path. Specifically, we study partitioned groupoidal assemblies. Categories of such are parameterised by "realizer categories" (instead of the usual partial combinatory algebras) that come equipped with an interval qua internal cogroupoid. The interval furnishes a notion of homotopy as well as a fundamental groupoid construction. Objects in a base groupoid are realized by points in the fundamental groupoid of some object from the realizer category; isomorphisms in the base groupoid are realized by paths in said fundamental groupoid. The main result is that, under mild conditions on the realizer category, the ensuing category of partitioned groupoidal assemblies models intensional (1-truncated) type theory without function extensionality. Moreover, when the underlying realizer category is "untyped", there exists an impredicative universe of 1-types (the modest fibrations). This is a groupoidal analogue of the traditional situation.
The Precise Complexity of Reasoning in $\mathcal{ALC}$ with $ω$-Admissible Concrete Domains (Extended Version)
Venue: arXiv cs.LO 2024
Year: 2024

Concrete domains have been introduced in the context of Description Logics to allow references to qualitative and quantitative values. In particular, the class of $ω$-admissible concrete domains, which includes Allen's interval algebra, the region connection calculus (RCC8), and the rational numbers with ordering and equality, has been shown to yield extensions of $\mathcal{ALC}$ for which concept satisfiability w.r.t. a general TBox is decidable. In this paper, we present an algorithm based on type elimination and use it to show that deciding the consistency of an $\mathcal{ALC}(\mathfrak{D})$ ontology is ExpTime-complete if the concrete domain $\mathfrak{D}$ is $ω$-admissible and its constraint satisfaction problem is decidable in exponential time. While this allows us to reason with concept and role assertions, we also investigate feature assertions $f(a,c)$ that can specify a constant $c$ as the value of a feature $f$ for an individual $a$. We show that, under conditions satisfied by all known $ω$-admissible domains, we can add feature assertions without affecting the complexity.
Federated Assemblies
Venue: arXiv cs.GT 2024
Year: 2024

A citizens' assembly is a group of people who are randomly selected to represent a larger population in a deliberation. While this approach has successfully strengthened democracy, it has certain limitations that suggest the need for assemblies to form and associate more organically. In response, we propose federated assemblies, where assemblies are interconnected, and each parent assembly is selected from members of its child assemblies. The main technical challenge is to develop random selection algorithms that meet new representation constraints inherent in this hierarchical structure. We design and analyze several algorithms that provide different representation guarantees under various assumptions on the structure of the underlying graph.
Learning Interpretable Scheduling Algorithms for Data Processing Clusters
Venue: arXiv cs.DC 2024
Year: 2024

Workloads in data processing clusters are often represented in the form of DAG (Directed Acyclic Graph) jobs. Scheduling DAG jobs is challenging. Simple heuristic scheduling algorithms are often adopted in practice in production data centres. There is much room for scheduling performance optimisation for cost saving. Recently, reinforcement learning approaches (like decima) have been attempted to optimise DAG job scheduling and demonstrate clear performance gain in comparison to traditional algorithms. However, reinforcement learning (RL) approaches face their own problems in real-world deployment. In particular, their black-box decision making processes and generalizability in unseen workloads may add a non-trivial burden to the cluster administrators. Moreover, adapting RL models on unseen workloads often requires significant amount of training data, which leaves edge cases run in a sub-optimal mode. To fill the gap, we propose a new method to distill a simple scheduling policy based on observations of the behaviours of a complex deep learning model. The simple model not only provides interpretability of scheduling decisions, but also adaptive to edge cases easily through tuning. We show that our method achieves high fidelity to the decisions made by deep learning models and outperforms these models when additional heuristics are taken into account.
Transformers as Neural Operators for Solutions of Differential Equations with Finite Regularity
Venue: arXiv cs.LG 2024
Year: 2024

Neural operator learning models have emerged as very effective surrogates in data-driven methods for partial differential equations (PDEs) across different applications from computational science and engineering. Such operator learning models not only predict particular instances of a physical or biological system in real-time but also forecast classes of solutions corresponding to a distribution of initial and boundary conditions or forcing terms. % DeepONet is the first neural operator model and has been tested extensively for a broad class of solutions, including Riemann problems. Transformers have not been used in that capacity, and specifically, they have not been tested for solutions of PDEs with low regularity. % In this work, we first establish the theoretical groundwork that transformers possess the universal approximation property as operator learning models. We then apply transformers to forecast solutions of diverse dynamical systems with solutions of finite regularity for a plurality of initial conditions and forcing terms. In particular, we consider three examples: the Izhikevich neuron model, the tempered fractional-order Leaky Integrate-and-Fire (LIF) model, and the one-dimensional Euler equation Riemann problem. For the latter problem, we also compare with variants of DeepONet, and we find that transformers outperform DeepONet in accuracy but they are computationally more expensive.
Algorithmic Transparency and Participation through the Handoff Lens: Lessons Learned from the U.S. Census Bureau's Adoption of Differential Privacy
Venue: arXiv cs.CY 2024
Year: 2024

Emerging discussions on the responsible government use of algorithmic technologies propose transparency and public participation as key mechanisms for preserving accountability and trust. But in practice, the adoption and use of any technology shifts the social, organizational, and political context in which it is embedded. Therefore translating transparency and participation efforts into meaningful, effective accountability must take into account these shifts. We adopt two theoretical frames, Mulligan and Nissenbaum's handoff model and Star and Griesemer's boundary objects, to reveal such shifts during the U.S. Census Bureau's adoption of differential privacy (DP) in its updated disclosure avoidance system (DAS) for the 2020 census. This update preserved (and arguably strengthened) the confidentiality protections that the Bureau is mandated to uphold, and the Bureau engaged in a range of activities to facilitate public understanding of and participation in the system design process. Using publicly available documents concerning the Census' implementation of DP, this case study seeks to expand our understanding of how technical shifts implicate values, how such shifts can afford (or fail to afford) greater transparency and participation in system design, and the importance of localized expertise throughout. We present three lessons from this case study toward grounding understandings of algorithmic transparency and participation: (1) efforts towards transparency and participation in algorithmic governance must center values and policy decisions, not just technical design decisions; (2) the handoff model is a useful tool for revealing how such values may be cloaked beneath technical decisions; and (3) boundary objects alone cannot bridge distant communities without trusted experts traveling alongside to broker their adoption.
Sparse High Dimensional Expanders via Local Lifts
Venue: arXiv cs.DM 2024
Year: 2024

High dimensional expanders (HDXs) are a hypergraph generalization of expander graphs. They are extensively studied in the math and TCS communities due to their many applications. Like expander graphs, HDXs are especially interesting for applications when they are bounded degree, namely, if the number of edges adjacent to every vertex is bounded. However, only a handful of constructions are known to have this property, all of which rely on algebraic techniques. In particular, no random or combinatorial construction of bounded degree HDXs is known. As a result, our understanding of these objects is limited. The degree of an $i$-face in an HDX is the number of $(i+1)$-faces containing it. In this work we construct HDXs whose higher dimensional faces have bounded degree. This is done by giving an elementary and deterministic algorithm that takes as input a regular $k$-dimensional HDX $X$ and outputs another $k$-dimensional HDX $\widehat{X}$ with twice as many vertices. While the degree of vertices in $\widehat{X}$ grows, the degree of the $(k-1)$-faces in $\widehat{X}$ stays the same. As a result, we obtain a new `algebra-free' construction of HDXs whose $(k-1)$-face degree is bounded. Our algorithm is based on a simple and natural generalization of the construction by Bilu and Linial (Combinatorica, 2006), which build expanders using lifts coming from edge signings. Our construction is based on local lifts of HDXs, where a local lift is a complex whose top-level links are lifts of links in the original complex. We demonstrate that a local lift of an HDX is an HDX in many cases. In addition, combining local lifts with existing bounded degree constructions creates new families of bounded degree HDXs with significantly different links than before. For every large enough $D$, we use this technique to construct families of bounded degree HDXs with links that have diameter $\geq D$.
LOGO: Video Text Spotting with Language Collaboration and Glyph Perception Model
Venue: arXiv cs.CV 2024
Year: 2024

Video text spotting (VTS) aims to simultaneously localize, recognize and track text instances in videos. To address the limited recognition capability of end-to-end methods, recent methods track the zero-shot results of state-of-the-art image text spotters directly, and achieve impressive performance. However, owing to the domain gap between different datasets, these methods usually obtain limited tracking trajectories on extreme dataset. Fine-tuning transformer-based text spotters on specific datasets could yield performance enhancements, albeit at the expense of considerable training resources. In this paper, we propose a Language Collaboration and Glyph Perception Model, termed LOGO, an innovative framework designed to enhance the performance of conventional text spotters. To achieve this goal, we design a language synergy classifier (LSC) to explicitly discern text instances from background noise in the recognition stage. Specially, the language synergy classifier can output text content or background code based on the legibility of text regions, thus computing language scores. Subsequently, fusion scores are computed by taking the average of detection scores and language scores, and are utilized to re-score the detection results before tracking. By the re-scoring mechanism, the proposed LSC facilitates the detection of low-resolution text instances while filtering out text-like regions. Moreover, the glyph supervision is introduced to enhance the recognition accuracy of noisy text regions. In addition, we propose the visual position mixture module, which can merge the position information and visual features efficiently, and acquire more discriminative tracking features. Extensive experiments on public benchmarks validate the effectiveness of the proposed method.
ConceptPrune: Concept Editing in Diffusion Models via Skilled Neuron Pruning
Venue: arXiv cs.CV 2024
Year: 2024

While large-scale text-to-image diffusion models have demonstrated impressive image-generation capabilities, there are significant concerns about their potential misuse for generating unsafe content, violating copyright, and perpetuating societal biases. Recently, the text-to-image generation community has begun addressing these concerns by editing or unlearning undesired concepts from pre-trained models. However, these methods often involve data-intensive and inefficient fine-tuning or utilize various forms of token remapping, rendering them susceptible to adversarial jailbreaks. In this paper, we present a simple and effective training-free approach, ConceptPrune, wherein we first identify critical regions within pre-trained models responsible for generating undesirable concepts, thereby facilitating straightforward concept unlearning via weight pruning. Experiments across a range of concepts including artistic styles, nudity, object erasure, and gender debiasing demonstrate that target concepts can be efficiently erased by pruning a tiny fraction, approximately 0.12% of total weights, enabling multi-concept erasure and robustness against various white-box and black-box adversarial attacks.
Hybrid-Parallel: Achieving High Performance and Energy Efficient Distributed Inference on Robots
Venue: arXiv cs.RO 2024
Year: 2024

The rapid advancements in machine learning techniques have led to significant achievements in various real-world robotic tasks. These tasks heavily rely on fast and energy-efficient inference of deep neural network (DNN) models when deployed on robots. To enhance inference performance, distributed inference has emerged as a promising approach, parallelizing inference across multiple powerful GPU devices in modern data centers using techniques such as data parallelism, tensor parallelism, and pipeline parallelism. However, when deployed on real-world robots, existing parallel methods fail to provide low inference latency and meet the energy requirements due to the limited bandwidth of robotic IoT. We present Hybrid-Parallel, a high-performance distributed inference system optimized for robotic IoT. Hybrid-Parallel employs a fine-grained approach to parallelize inference at the granularity of local operators within DNN layers (i.e., operators that can be computed independently with the partial input, such as the convolution kernel in the convolution layer). By doing so, Hybrid-Parallel enables different operators of different layers to be computed and transmitted concurrently, and overlap the computation and transmission phases within the same inference task. The evaluation demonstrate that Hybrid-Parallel reduces inference time by 14.9% ~41.1% and energy consumption per inference by up to 35.3% compared to the state-of-the-art baselines.
A Privacy-Preserving Graph Encryption Scheme Based on Oblivious RAM
Venue: arXiv cs.CR 2024
Year: 2024

Graph encryption schemes play a crucial role in facilitating secure queries on encrypted graphs hosted on untrusted servers. With applications spanning navigation systems, network topology, and social networks, the need to safeguard sensitive data becomes paramount. Existing graph encryption methods, however, exhibit vulnerabilities by inadvertently revealing aspects of the graph structure and query patterns, posing threats to security and privacy. In response, we propose a novel graph encryption scheme designed to mitigate access pattern and query pattern leakage through the integration of oblivious RAM and trusted execution environment techniques, exemplified by a Trusted Execution Environment (TEE). Our solution establishes two key security objectives: (1) ensuring that adversaries, when presented with an encrypted graph, remain oblivious to any information regarding the underlying graph, and (2) achieving query indistinguishability by concealing access patterns. Additionally, we conducted experimentation to evaluate the efficiency of the proposed schemes when dealing with real-world location navigation services.
Network Connectivity--Information Freshness Tradeoff in Information Dissemination Over Networks
Venue: arXiv cs.IT 2024
Year: 2024

We consider a gossip network consisting of a source generating updates and $n$ nodes connected according to a given graph structure. The source keeps updates of a process, that might be generated or observed, and shares them with the gossiping network. The nodes in the network communicate with their neighbors and disseminate these version updates using a push-style gossip strategy. We use the version age metric to quantify the timeliness of information at the nodes. We first find an upper bound for the average version age for a set of nodes in a general network. Using this, we find the average version age scaling of a node in several network graph structures, such as two-dimensional grids, generalized rings and hyper-cubes. Prior to our work, it was known that when $n$ nodes are connected on a ring the version age scales as $O(n^{\frac{1}{2}})$, and when they are connected on a fully-connected graph the version age scales as $O(\log n)$. Ours is the first work to show an age scaling result for a connectivity structure other than the ring and the fully-connected network, which constitute the two extremes of network connectivity. Our work helps fill the gap between these two extremes by analyzing a large variety of graphs with intermediate connectivity, thus providing insight into the relationship between the connectivity structure of the network and the version age, and uncovering a network connectivity--information freshness tradeoff.
LLMs Meet Multimodal Generation and Editing: A Survey
Venue: arXiv cs.AI 2024
Year: 2024

With the recent advancement in large language models (LLMs), there is a growing interest in combining LLMs with multimodal learning. Previous surveys of multimodal large language models (MLLMs) mainly focus on multimodal understanding. This survey elaborates on multimodal generation and editing across various domains, comprising image, video, 3D, and audio. Specifically, we summarize the notable advancements with milestone works in these fields and categorize these studies into LLM-based and CLIP/T5-based methods. Then, we summarize the various roles of LLMs in multimodal generation and exhaustively investigate the critical technical components behind these methods and the multimodal datasets utilized in these studies. Additionally, we dig into tool-augmented multimodal agents that can leverage existing generative models for human-computer interaction. Lastly, we discuss the advancements in the generative AI safety field, investigate emerging applications, and discuss future prospects. Our work provides a systematic and insightful overview of multimodal generation and processing, which is expected to advance the development of Artificial Intelligence for Generative Content (AIGC) and world models. A curated list of all related papers can be found at https://github.com/YingqingHe/Awesome-LLMs-meet-Multimodal-Generation
Information-theoretic language of proteinoid gels: Boolean gates and QR codes
Venue: arXiv cs.ET 2024
Year: 2024

With an aim to build analog computers out of soft matter fluidic systems in future, this work attempts to invent a new information-theoretic language, in the form of two-dimensional Quick Response (QR) codes. This language is, effectively, a digital representation of the analog signals shown by the proteinoids. We use two different experimental techniques: (i) a voltage-sensitive dye and (ii) a pair of differential electrodes, to record the analog signals. The analog signals are digitally approximatied (synthesised) by sampling the analog signals into a series of discrete values, which are then converted into binary representations. We have shown the AND-OR-NOT-XOR-NOR-NAND-XNOR gate representation of the digitally sampled signal of proteinoids. Additional encoding schemes are applied to convert the binary code identified above to a two-dimensional QR code. As a result, the QR code becomes a digital, unique marker of a given proteinoid network. We show that it is possible to retrieve the analog signal from the QR code by scanning the QR code using a mobile phone. Our work shows that soft matter fluidic systems, such as proteinoids, can have a fundamental informatiom-theoretic language, unique to their internal information transmission properties (electrical activity in this case) - such a language can be made universal and accessible to everyone using 2D QR codes, which can digitally encode their internal properties and give an option to recover the original signal when required. On a more fundamental note, this study identifies the techniques of approximating continuum properties of soft matter fluidic systems using a series representation of gates and QR codes, which are a piece-wise digital representation, and thus one step closer to programming the fluids using information-theoretic methods, as suggested almost a decade ago by Tao's fluid program.
PureEBM: Universal Poison Purification via Mid-Run Dynamics of Energy-Based Models
Venue: arXiv cs.LG 2024
Year: 2024

Data poisoning attacks pose a significant threat to the integrity of machine learning models by leading to misclassification of target distribution data by injecting adversarial examples during training. Existing state-of-the-art (SoTA) defense methods suffer from limitations, such as significantly reduced generalization performance and significant overhead during training, making them impractical or limited for real-world applications. In response to this challenge, we introduce a universal data purification method that defends naturally trained classifiers from malicious white-, gray-, and black-box image poisons by applying a universal stochastic preprocessing step $Ψ_{T}(x)$, realized by iterative Langevin sampling of a convergent Energy Based Model (EBM) initialized with an image $x.$ Mid-run dynamics of $Ψ_{T}(x)$ purify poison information with minimal impact on features important to the generalization of a classifier network. We show that EBMs remain universal purifiers, even in the presence of poisoned EBM training data, and achieve SoTA defense on leading triggered and triggerless poisons. This work is a subset of a larger framework introduced in \pgen with a more detailed focus on EBM purification and poison defense.