OpenRaiser/Intern-Atlas huggingface dataset:
No Easy Way Out: the Effectiveness of Deplatforming an Extremist Forum to Suppress Hate and Harassment
Venue: arXiv cs.CR 2024
Year: 2024

Legislators and policymakers worldwide are debating options for suppressing illegal, harmful and undesirable material online. Drawing on several quantitative data sources, we show that deplatforming an active community to suppress online hate and harassment, even with a substantial concerted effort involving several tech firms, can be hard. Our case study is the disruption of the largest and longest-running harassment forum Kiwi Farms in late 2022, which is probably the most extensive industry effort to date. Despite the active participation of a number of tech companies over several consecutive months, this campaign failed to shut down the forum and remove its objectionable content. While briefly raising public awareness, it led to rapid platform displacement and traffic fragmentation. Part of the activity decamped to Telegram, while traffic shifted from the primary domain to previously abandoned alternatives. The forum experienced intermittent outages for several weeks, after which the community leading the campaign lost interest, traffic was directed back to the main domain, users quickly returned, and the forum was back online and became even more connected. The forum members themselves stopped discussing the incident shortly thereafter, and the net effect was that forum activity, active users, threads, posts and traffic were all cut by about half. Deplatforming a community without a court order raises philosophical issues about censorship versus free speech; ethical and legal issues about the role of industry in online content moderation; and practical issues on the efficacy of private-sector versus government action. Deplatforming a dispersed community using a series of court orders against individual service providers appears unlikely to be very effective if the censor cannot incapacitate the key maintainers, whether by arresting them, enjoining them or otherwise deterring them.
Completeness Theorems for Kleene algebra with tests and top
Venue: arXiv cs.FL 2024
Year: 2024

We prove two completeness results for Kleene algebra with tests and a top element, with respect to guarded string languages and binary relations. While the equational theories of those two classes of models coincide over the signature of Kleene algebra, this is no longer the case when we consider an additional constant ``top'' for the full element. Indeed, the full relation satisfies more laws than the full language, and we show that those additional laws can all be derived from a single additional axiom. We recover that the two equational theories coincide if we slightly generalise the notion of relational model, allowing sub-algebras of relations where top is a greatest element but not necessarily the full relation. We use models of closed languages and reductions in order to prove our completeness results, which are relative to any axiomatisation of the algebra of regular events. For one of our constructions, we extend the concept of finite monoid recognisability to guarded-string languages; this device makes it possible to obtain a PSpace algorithm for the equational theory of binary relations.
DINOv2: Learning Robust Visual Features without Supervision
Venue: arXiv cs.CV 2024
Year: 2024

The recent breakthroughs in natural language processing for model pretraining on large quantities of data have opened the way for similar foundation models in computer vision. These models could greatly simplify the use of images in any system by producing all-purpose visual features, i.e., features that work across image distributions and tasks without finetuning. This work shows that existing pretraining methods, especially self-supervised methods, can produce such features if trained on enough curated data from diverse sources. We revisit existing approaches and combine different techniques to scale our pretraining in terms of data and model size. Most of the technical contributions aim at accelerating and stabilizing the training at scale. In terms of data, we propose an automatic pipeline to build a dedicated, diverse, and curated image dataset instead of uncurated data, as typically done in the self-supervised literature. In terms of models, we train a ViT model (Dosovitskiy et al., 2020) with 1B parameters and distill it into a series of smaller models that surpass the best available all-purpose features, OpenCLIP (Ilharco et al., 2021) on most of the benchmarks at image and pixel levels.
Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learning
Venue: arXiv cs.LG 2024
Year: 2024

This paper studies reward-agnostic exploration in reinforcement learning (RL) -- a scenario where the learner is unware of the reward functions during the exploration stage -- and designs an algorithm that improves over the state of the art. More precisely, consider a finite-horizon inhomogeneous Markov decision process with $S$ states, $A$ actions, and horizon length $H$, and suppose that there are no more than a polynomial number of given reward functions of interest. By collecting an order of \begin{align*} \frac{SAH^3}{\varepsilon^2} \text{ sample episodes (up to log factor)} \end{align*} without guidance of the reward information, our algorithm is able to find $\varepsilon$-optimal policies for all these reward functions, provided that $\varepsilon$ is sufficiently small. This forms the first reward-agnostic exploration scheme in this context that achieves provable minimax optimality. Furthermore, once the sample size exceeds $\frac{S^2AH^3}{\varepsilon^2}$ episodes (up to log factor), our algorithm is able to yield $\varepsilon$ accuracy for arbitrarily many reward functions (even when they are adversarially designed), a task commonly dubbed as ``reward-free exploration.'' The novelty of our algorithm design draws on insights from offline RL: the exploration scheme attempts to maximize a critical reward-agnostic quantity that dictates the performance of offline RL, while the policy learning paradigm leverages ideas from sample-optimal offline RL paradigms.
STAS: Spatial-Temporal Return Decomposition for Multi-agent Reinforcement Learning
Venue: arXiv cs.AI 2024
Year: 2024

Centralized Training with Decentralized Execution (CTDE) has been proven to be an effective paradigm in cooperative multi-agent reinforcement learning (MARL). One of the major challenges is credit assignment, which aims to credit agents by their contributions. While prior studies have shown great success, their methods typically fail to work in episodic reinforcement learning scenarios where global rewards are revealed only at the end of the episode. They lack the functionality to model complicated relations of the delayed global reward in the temporal dimension and suffer from inefficiencies. To tackle this, we introduce Spatial-Temporal Attention with Shapley (STAS), a novel method that learns credit assignment in both temporal and spatial dimensions. It first decomposes the global return back to each time step, then utilizes the Shapley Value to redistribute the individual payoff from the decomposed global reward. To mitigate the computational complexity of the Shapley Value, we introduce an approximation of marginal contribution and utilize Monte Carlo sampling to estimate it. We evaluate our method on an Alice & Bob example and MPE environments across different scenarios. Our results demonstrate that our method effectively assigns spatial-temporal credit, outperforming all state-of-the-art baselines.
Interpretable Detection of Out-of-Context Misinformation with Neural-Symbolic-Enhanced Large Multimodal Model
Venue: arXiv cs.CL 2024
Year: 2024

Recent years have witnessed the sustained evolution of misinformation that aims at manipulating public opinions. Unlike traditional rumors or fake news editors who mainly rely on generated and/or counterfeited images, text and videos, current misinformation creators now more tend to use out-of-context multimedia contents (e.g. mismatched images and captions) to deceive the public and fake news detection systems. This new type of misinformation increases the difficulty of not only detection but also clarification, because every individual modality is close enough to true information. To address this challenge, in this paper we explore how to achieve interpretable cross-modal de-contextualization detection that simultaneously identifies the mismatched pairs and the cross-modal contradictions, which is helpful for fact-check websites to document clarifications. The proposed model first symbolically disassembles the text-modality information to a set of fact queries based on the Abstract Meaning Representation of the caption and then forwards the query-image pairs into a pre-trained large vision-language model select the ``evidences" that are helpful for us to detect misinformation. Extensive experiments indicate that the proposed methodology can provide us with much more interpretable predictions while maintaining the accuracy same as the state-of-the-art model on this task.
A multistep strategy for polynomial system solving over finite fields and a new algebraic attack on the stream cipher Trivium
Venue: arXiv cs.SC 2024
Year: 2024

In this paper we introduce a multistep generalization of the guess-and-determine or hybrid strategy for solving a system of multivariate polynomial equations over a finite field. In particular, we propose performing the exhaustive evaluation of a subset of variables stepwise, that is, by incrementing the size of such subset each time that an evaluation leads to a polynomial system which is possibly unfeasible to solve. The decision about which evaluation to extend is based on a preprocessing consisting in computing an incomplete Grobner basis after the current evaluation, which possibly generates linear polynomials that are used to eliminate further variables. If the number of remaining variables in the system is deemed still too high, the evaluation is extended and the preprocessing is iterated. Otherwise, we solve the system by a complete Grobner basis computation. Having in mind cryptanalytic applications, we present an implementation of this strategy in an algorithm called MultiSolve which is designed for polynomial systems having at most one solution. We prove explicit formulas for its complexity which are based on probability distributions that can be easily estimated by performing the proposed preprocessing on a testset of evaluations for different subsets of variables. We prove that an optimal complexity of MultiSolve is achieved by using a full multistep strategy with a maximum number of steps and in turn the standard guess-and-determine strategy, which essentially is a strategy consisting of a single step, is the worst choice. Finally, we extensively study the behaviour of MultiSolve when performing an algebraic attack on the well-known stream cipher Trivium.
An Interpretable Approach to Load Profile Forecasting in Power Grids using Galerkin-Approximated Koopman Pseudospectra
Venue: arXiv cs.LG 2024
Year: 2024

This paper presents an interpretable machine learning approach that characterizes load dynamics within an operator-theoretic framework for electricity load forecasting in power grids. We represent the dynamics of load data using the Koopman operator, which provides a linear, infinite-dimensional representation of the nonlinear dynamics, and approximate a finite version that remains robust against spectral pollutions due to truncation. By computing $ε$-approximate Koopman eigenfunctions using dynamics-adapted kernels in delay coordinates, we decompose the load dynamics into coherent spatiotemporal patterns that evolve quasi-independently. Our approach captures temporal coherent patterns due to seasonal changes and finer time scales, such as time of day and day of the week. This method allows for a more nuanced understanding of the complex interactions within power grids and their response to various exogenous factors. We assess our method using a large-scale dataset from a renewable power system in the continental European electricity system. The results indicate that our Koopman-based method surpasses a separately optimized deep learning (LSTM) architecture in both accuracy and computational efficiency, while providing deeper insights into the underlying dynamics of the power grid\footnote{The code is available at \href{https://github.com/Shakeri-Lab/Power-Grids}{github.com/Shakeri-Lab/Power-Grids}.
Implementing Responsible AI: Tensions and Trade-Offs Between Ethics Aspects
Venue: arXiv cs.CY 2024
Year: 2024

Many sets of ethics principles for responsible AI have been proposed to allay concerns about misuse and abuse of AI/ML systems. The underlying aspects of such sets of principles include privacy, accuracy, fairness, robustness, explainability, and transparency. However, there are potential tensions between these aspects that pose difficulties for AI/ML developers seeking to follow these principles. For example, increasing the accuracy of an AI/ML system may reduce its explainability. As part of the ongoing effort to operationalise the principles into practice, in this work we compile and discuss a catalogue of 10 notable tensions, trade-offs and other interactions between the underlying aspects. We primarily focus on two-sided interactions, drawing on support spread across a diverse literature. This catalogue can be helpful in raising awareness of the possible interactions between aspects of ethics principles, as well as facilitating well-supported judgements by the designers and developers of AI/ML systems.
Towards Computational Performance Engineering for Unsupervised Concept Drift Detection -- Complexities, Benchmarking, Performance Analysis
Venue: arXiv cs.LG 2024
Year: 2024

Concept drift detection is crucial for many AI systems to ensure the system's reliability. These systems often have to deal with large amounts of data or react in real-time. Thus, drift detectors must meet computational requirements or constraints with a comprehensive performance evaluation. However, so far, the focus of developing drift detectors is on inference quality, e.g. accuracy, but not on computational performance, such as runtime. Many of the previous works consider computational performance only as a secondary objective and do not have a benchmark for such evaluation. Hence, we propose and explain performance engineering for unsupervised concept drift detection that reflects on computational complexities, benchmarking, and performance analysis. We provide the computational complexities of existing unsupervised drift detectors and discuss why further computational performance investigations are required. Hence, we state and substantiate the aspects of a benchmark for unsupervised drift detection reflecting on inference quality and computational performance. Furthermore, we demonstrate performance analysis practices that have proven their effectiveness in High-Performance Computing, by tracing two drift detectors and displaying their performance data.
MANTRA: Temporal Betweenness Centrality Approximation through Sampling
Venue: arXiv cs.DS 2024
Year: 2024

We present MANTRA, a framework for approximating the temporal betweenness centrality of all nodes in a temporal graph. Our method can compute probabilistically guaranteed high-quality temporal betweenness estimates (of nodes and temporal edges) under all the feasible temporal path optimalities, presented in the work of Buß et al. (KDD, 2020). We provide a sample-complexity analysis of our method and speed up the temporal betweenness computation using a state-of-the-art progressive sampling approach based on Monte Carlo Empirical Rademacher Averages. Additionally, we provide an efficient sampling algorithm to approximate the temporal diameter, average path length, and other fundamental temporal graph characteristic quantities within a small error $\varepsilon$ with high probability. The running time of such approximation algorithm is $\tilde{\mathcal{O}}(\frac{\log n}{\varepsilon^2}\cdot |\mathcal{E}|)$, where $n$ is the number of nodes and $|\mathcal{E}|$ is the number of temporal edges in the temporal graph. We support our theoretical results with an extensive experimental analysis on several real-world networks and provide empirical evidence that the MANTRA framework improves the current state of the art in speed, sample size, and required space while maintaining high accuracy of the temporal betweenness estimates.
A Personality-Guided Preference Aggregator for Ephemeral Group Recommendation
Venue: arXiv cs.IR 2024
Year: 2024

Ephemeral group recommendation (EGR) aims to suggest items for a group of users who come together for the first time. Existing work typically consider individual preferences as the sole factor in aggregating group preferences. However, they neglect to take into account the importance of the individual inherent factors, such as personality, and thus fail to accurately simulate the group decision-making process. Additionally, these methods often struggle due to insufficient interactive records. To tackle these issues, a Personality-Guided Preference Aggregator (PEGA) is proposed, which guides the preference aggregation of group members based on their personalities, rather than relying solely on their preferences. Specifically, implicit personalities are first extracted from user reviews. Hyper-rectangles are then used to aggregate individual personalities to obtain the "Group Personality", which allows for the learning of personality distributions within the group. Subsequently, a personality attention mechanism is employed to aggregate group preferences, and a preference-based fine-tuning module is used to balance the weights of personality and preferences. The role of personality in this approach is twofold: (1) To estimate the importance of individual users in a group and provide explainability; (2) To alleviate the data sparsity issue encountered in ephemeral groups. Experimental results demonstrate that, on four real-world datasets, the PEGA model significantly outperforms related baseline models in terms of classification accuracy and interpretability. Moreover, empirical evidence supports the idea that personality plays a pivotal role in enhancing the performance of EGR tasks.
A note on Stone-Čech compactification in ZFA
Venue: arXiv cs.LO 2024
Year: 2024

Working in Zermelo-Fraenkel Set Theory with Atoms over an $ω$-categorical $ω$-stable structure, we show how \emph{infinite} constructions over definable sets can be encoded as \emph{finite} constructions over the Stone-Čech compactification of the sets. In particular, we show that for a definable set $X$ with its Stone-Čech compactification $\overline{X}$ the following holds: a) the powerset $\mathcal{P}(X)$ of $X$ is isomorphic to the finite-powerset $\mathcal{P}_{\textit{fin}}(\overline{X})$ of $\overline{X}$, b) the vector space $\mathcal{K}^X$ over a field $\mathcal{K}$ is the free vector space $F_{\mathcal{K}}(\overline{X})$ on $\overline{X}$ over $\mathcal{K}$, c) every measure on $X$ is tantamount to a \emph{discrete} measure on $\overline{X}$. Moreover, we prove that the Stone-Čech compactification of a definable set is still definable, which allows us to obtain some results about equivalence of certain formalizations of register machines.
Open-World Continual Learning: Unifying Novelty Detection and Continual Learning
Venue: arXiv cs.LG 2024
Year: 2024

As AI agents are increasingly used in the real open world with unknowns or novelties, they need the ability to (1) recognize objects that (a) they have learned before and (b) detect items that they have never seen or learned, and (2) learn the new items incrementally to become more and more knowledgeable and powerful. (1) is called novelty detection or out-of-distribution (OOD) detection and (2) is called class incremental learning (CIL), which is a setting of continual learning (CL). In existing research, OOD detection and CIL are regarded as two completely different problems. This paper first provides a theoretical proof that good OOD detection for each task within the set of learned tasks (called closed-world OOD detection) is necessary for successful CIL. We show this by decomposing CIL into two sub-problems: within-task prediction (WP) and task-id prediction (TP), and proving that TP is correlated with closed-world OOD detection. The key theoretical result is that regardless of whether WP and OOD detection (or TP) are defined explicitly or implicitly by a CIL algorithm, good WP and good closed-world OOD detection are necessary and sufficient conditions for good CIL, which unifies novelty or OOD detection and continual learning (CIL, in particular). We call this traditional CIL the closed-world CIL as it does not detect future OOD data in the open world. The paper then proves that the theory can be generalized or extended to open-world CIL, which is the proposed open-world continual learning, that can perform CIL in the open world and detect future or open-world OOD data. Based on the theoretical results, new CIL methods are also designed, which outperform strong baselines in CIL accuracy and in continual OOD detection by a large margin.
ID-MixGCL: Identity Mixup for Graph Contrastive Learning
Venue: arXiv cs.LG 2024
Year: 2024

Graph contrastive learning (GCL) has recently achieved substantial advancements. Existing GCL approaches compare two different ``views'' of the same graph in order to learn node/graph representations. The underlying assumption of these studies is that the graph augmentation strategy is capable of generating several different graph views such that the graph views are structurally different but semantically similar to the original graphs, and thus the ground-truth labels of the original and augmented graph/nodes can be regarded identical in contrastive learning. However, we observe that this assumption does not always hold. For instance, the deletion of a super-node within a social network can exert a substantial influence on the partitioning of communities for other nodes. Similarly, any perturbation to nodes or edges in a molecular graph will change the labels of the graph. Therefore, we believe that augmenting the graph, accompanied by an adaptation of the labels used for the contrastive loss, will facilitate the encoder to learn a better representation. Based on this idea, we propose ID-MixGCL, which allows the simultaneous interpolation of input nodes and corresponding identity labels to obtain soft-confidence samples, with a controllable degree of change, leading to the capture of fine-grained representations from self-supervised training on unlabeled graphs. Experimental results demonstrate that ID-MixGCL improves performance on graph classification and node classification tasks, as demonstrated by significant improvements on the Cora, IMDB-B, IMDB-M, and PROTEINS datasets compared to state-of-the-art techniques, by 3-29% absolute points.