Graph neural networks (GNNs) have shown promise on combinatorial problems such as Max-Clique, yet it remains unclear what algorithmic principles they actually learn. This paper introduces a concept-driven framework for evaluating and interpreting GNNs on such tasks. We begin with a principled benchmark based on synthetic graphs with known difficulty levels—easy, medium, and hard—derived from theoretical thresholds for planted cliques. Using this setup, we show that GNNs reliably learn a simple yet powerful concept: degree-based ranking. This insight motivates a new decoder, Least-Probable Removal (LPR), which significantly outperforms the common top-k strategy, especially on harder and real-world instances. Our analysis pipeline connects latent representations to classical heuristics, improving both interpretability and performance. Finally, we demonstrate cross-domain generalization to sparse PCA, showing that the same GNN architecture and decoding strategy succeed in recovering sparse principal components, revealing a shared underlying principle across domains.

Explainable AI and model transparency methods primarily focus on classification tasks, identifying salient input features or abstract concepts that are directly tied to the data. In contrast, algorithmic problems such as SAT solving present a deeper challenge: here, meaningful concepts depend not only on the input but also on the model’s evolving internal state; hence, such settings remain underexplored. We study concept learning in an existing model named NeuroSAT , a Graph Neural Network (GNN) trained to predict satisfiability, and uncover internal algorithmic structures, most notably the notion of support , that align with classical SAT heuristics. We then construct a significantly simplified GNN trained via a teacher–student approach: instead of learning from SAT/UNSAT labels, the student is trained to mimic NeuroSAT ’s latent representations—i.e., the concepts themselves—and achieves comparable performance using 91 % fewer parameters. For this simplified architecture, we provide a rigorous theoretical analysis that demonstrates, under certain assumptions on the input distribution and network weights, the emergence of the concept of support and its governing role in the network’s dynamics. This work bridges explainability and algorithmic reasoning by showing that classical SAT-solving strategies emerge naturally in GNNs—and can be used to simplify, compress, and formally analyze their internal dynamics. • We propose a framework for discovering algorithmic concepts learned by GNNs and showcase it on the problem of satisfiability using NeuroSAT by Selsam et al. (2018). • Key abstractions, such as variable assignment confidence-level, emerge spontaneously when the GNN is trained to predict SAT/UNSAT using only single-bit supervision and standard cross-entropy loss. • The discovered concepts enable both theoretical analysis and compression via a compact student network trained on internal representations. • Our insights guide principled modifications to the classical WalkSAT algorithm, yielding new variants that converge faster.

Stance detection plays a pivotal role in enabling an extensive range of downstream applications, from discourse parsing to tracing the spread of fake news and the denial of scientific facts. While most stance classification models rely on the textual representation of the utterance in question, prior work has demonstrated the importance of the conversational context in stance detection. In this work, we introduce TASTE – a multimodal architecture for stance detection that harmoniously fuses Transformer-based content embedding with unsupervised structural embedding. Through the fine-tuning of a pre-trained transformer and the amalgamation with social embedding via a Gated Residual Network (GRN) layer, our model adeptly captures the complex interplay between content and conversational structure in determining stance. TASTE achieves state-of-the-art results on common benchmarks, significantly outperforming an array of strong baselines. Comparative evaluations underscore the benefits of social grounding – emphasizing the criticality of concurrently harnessing both content and structure for enhanced stance detection.

Abstract A Citizens’ assembly (CA) is a democratic innovation tool where a randomly selected group of citizens deliberate a topic over multiple rounds to generate, and then vote upon, policy recommendations. Despite growing popularity, little work exists on understanding how CA inputs, such as the expert selection process and the mixing method used for discussion groups, affect results. In this work, we model CA deliberation and opinion change as a multi-agent systems problem. We introduce and formalise a set of criteria for evaluating successful CAs using insight from previous CA trials and theoretical results. Although real-world trials meet these criteria, we show that finding a model that does so is non-trivial; through simulations and theoretical arguments, we show that established opinion change models fail at least one of these criteria. We therefore propose an augmented opinion change model with a latent ‘open-mindedness’ variable, which sufficiently captures people’s propensity to change opinion. We show that data from the CA of Scotland indicates a latent variable both exists and resembles the concept of open-mindedness in the literature. We calibrate parameters against real CA data, demonstrating our model’s ecological validity, before running simulations across a range of realistic global parameters, with each simulation satisfying our criteria. Specifically, simulations meet criteria regardless of expert selection, expert ordering, participant extremism, and sub-optimal participant grouping, which has ramifications for optimised algorithmic approaches in the computational CA space.

Stance detection is an important task, supporting many downstream tasks such as discourse parsing and modeling the propagation of fake news, rumors, and science denial. In this paper, we propose a novel framework for stance detection. Our framework is unsupervised and domain-independent. Given a claim and a multi-participant discussion -- we construct the interaction network from which we derive topological embedding for each speaker. These speaker embedding enjoy the following property: speakers with the same stance tend to be represented by similar vectors, while antipodal vectors represent speakers with opposing stances. These embedding are then used to divide the speakers into stance-partitions. We evaluate our method on three different datasets from different platforms. Our method outperforms or is comparable with supervised models while providing confidence levels for its output. Furthermore, we demonstrate how the structural embedding relate to the valence expressed by the speakers. Finally, we discuss some limitations inherent to the framework.

The taxing computational effort that is involved in solving some high-dimensional statistical problems, in particular problems involving non-convex optimization, has popularized the development and analysis of algorithms that run efficiently (polynomial-time) but with no general guarantee on statistical consistency. In light of the ever-increasing compute power and decreasing costs, a more useful characterization of algorithms is by their ability to calibrate the invested computational effort with various characteristics of the input at hand and with the available computational resources. We propose a new greedy algorithm for the $\ell_0$-sparse PCA problem which supports the calibration principle. We provide both a rigorous analysis of our algorithm in the spiked covariance model, as well as simulation results and comparison with other existing methods. Our findings show that our algorithm recovers the spike in SNR regimes where all polynomial-time algorithms fail while running in a reasonable parallel-time on a cluster.

In this work we ask to which extent are simple statistics useful to make sense of social media data. By simple statistics we mean counting and bookkeeping type features such as the number of likes given to a user's post, a user's number of friends, etc. We find that relying solely on simple statistics is not always a good approach. Specifically, we develop a statistical framework that we term semantic shattering which allows to detect semantic inconsistencies in the data that may occur due to relying solely on simple statistics. We apply our framework to simple-statistics data collected from six online social media platforms and arrive at a surprising counter-intuitive finding in three of them, Twitter, Instagram and YouTube. We find that overall, the activity of the user is not correlated with the feedback that the user receives on that activity. A hint to understand this phenomenon may be found in the fact that the activity-feedback shattering did not occur in LinkedIn, Steam and Flickr. A possible explanation for this separation is the amount of effort required to produce content. The lesser the effort the lesser the correlation between activity and feedback. The amount of effort may be a proxy to the level of commitment that the users feel towards each other in the network, and indeed sociologists claim that commitment explains consistent human behavior, or lack thereof. However, the amount of effort or the level of commitment are by no means a simple statistic.

Based on a non-rigorous formalism called the "cavity method", physicists have put forward intriguing predictions on phase transitions in discrete structures. One of the most remarkable ones is that in problems such as random k-SAT or random graph k-coloring, very shortly before the threshold for the existence of solutions there occurs another phase transition called condensation [Krzakala et al., PNAS 2007]. The existence of this phase transition appears to be intimately related to the difficulty of proving precise results on, e.g., the k-colorability threshold as well as to the performance of message passing algorithms. In random graph k-coloring, there is a precise conjecture as to the location of the condensation phase transition in terms of a distributional fixed point problem. In this paper we prove this conjecture for k exceeding a certain constant k0.

In this paper we establish a substantially improved lower bound on the k-color ability threshold of the random graph G(n, m) with n vertices and m edges. The new lower bound is ≈ 1.39 less than the 2k ln (k)-ln (k) first-moment upper bound (and approximately 0.39 less than the 2k ln (k) - ln(k) - 1 physics conjecture). By comparison, the best previous bounds left a gap of about 2+ln(k), unbounded in terms of the number of colors [Achlioptas, Naor: STOC 2004]. Furthermore, we prove that, in a precise sense, our lower bound marks the so-called condensation phase transition predicted on the basis of physics arguments [Krzkala et al.: PNAS 2007]. Our proof technique is a novel approach to the second moment method, inspired by physics conjectures on the geometry of the set of k-colorings of the random graph.

Traditional studies of multi-source, multi-terminal interference channels typically allow a vanishing probability of error in communication. Motivated by the study of network coding, this work addresses the task of quantifying the loss in rate when insisting on zero error communication in the context of interference channels.

It is known that random [Formula: see text]-CNF formulas have a so-called satisfiability threshold at a density (namely, clause-variable ratio) of roughly [Formula: see text]: at densities slightly below this threshold almost all [Formula: see text]-CNF formulas are satisfiable, whereas slightly above this threshold almost no [Formula: see text]-CNF formula is satisfiable. In the current work we consider satisfiable random formulas and inspect another parameter—the diameter of the solution space (that is, the maximal Hamming distance between a pair of satisfying assignments). It was previously shown that for all densities up to a density slightly below the satisfiability threshold the diameter is almost surely at least roughly [Formula: see text] (and [Formula: see text] at much lower densities). At densities very much higher than the satisfiability threshold, the diameter is almost surely zero (a very dense satisfiable formula is expected to have only one satisfying assignment). In this paper we show that for all densities above a density that is slightly above the satisfiability threshold (more precisely, at ratio [Formula: see text], [Formula: see text] tending to 0 as [Formula: see text] grows) the diameter is almost surely [Formula: see text]. This shows that a relatively small change in the density around the satisfiability threshold (a multiplicative [Formula: see text] factor) makes a dramatic change in the diameter. This drop in the diameter cannot be attributed to the fact that a larger fraction of the formulas are not satisfiable (and hence have diameter 0), because the nonsatisfiable formulas are excluded from consideration by our conditioning that the formula be satisfiable.

In this paper we study the model of ∊-smoothed k-CNF formulas. Starting from an arbitrary instance F with n variables and m = dn clauses, apply the ∊-smoothing operation of flipping the polarity of every literal in every clause independently at random with probability ∊. Keeping ∊ and k fixed, and letting the density d = m/n grow, it is rather easy to see that for d ≥ ∊−-kln 2, F becomes whp unsatisfiable after smoothing. We show that a lower density that behaves roughly like ∊−-k+1 suffices for this purpose. We also show that our bound on d is nearly best possible in the sense that there are k-CNF formulas F of slightly lower density that whp remain satisfiable after smoothing. One consequence of our proof is a new lower bound of Ω(2k/k2) on the density up to which Walksat solves random k-CNFs in polynomial time whp. We are not aware of any previous rigorous analysis showing that Walksat is successful at densities that are increasing as a function of k.