Dan Vilenchik

AAAI Conference 2026 Conference Paper

Learning to Rank: How GNNs Solve Max-Clique and Sparse PCA

• Elad Shoham
• Omri Haber
• Havana Rika
• Dan Vilenchik

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.

AAMAS Conference 2025 Conference Paper

Beyond the Echo Chamber: Modelling Open-Mindedness in Citizens' Assemblies

• Jake Barrett
• Kobi Gal
• Loizos Michael
• Dan Vilenchik

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, and therefore on how to systematically set such parameters to optimize the process. 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 nontrivial; through simulations and theoretical arguments, we show that established opinion change models fail at least one of these criteria. This is an extended abstract of a JAAMAS article [2].

JAAMAS Journal 2024 Journal Article

Beyond the echo chamber: modelling open-mindedness in citizens’ assemblies

• Jake Barrett
• Kobi Gal
• Dan Vilenchik

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.

AAAI Conference 2022 Conference Paper

STEM: Unsupervised STructural EMbedding for Stance Detection

• Ron Korenblum Pick
• Vladyslav Kozhukhov
• Dan Vilenchik
• Oren Tsur

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.

AAMAS Conference 2022 Conference Paper

Welfare vs. Representation in Participatory Budgeting

• Roy Fairstein
• Dan Vilenchik
• Reshef Meir
• Kobi Gal

Participatory budgeting (PB) is a democratic process for allocating funds to projects based on the votes of members of the community. Different rules have been used to aggregate participants’ votes. A recent paper by Lackner and Skowron [12] studied the tradeoff between notions of social welfare and representation in the multi-winner voting, which is a special case of participatory budgeting with identical project costs. But there is little understanding of this trade-off in the more general PB setting. This paper provides a theoretical and empirical study of the worst-case guarantees of several common rules to better understand the trade-off between social welfare and representation. We show that many of the guarantees from the multi-winner setting do not generalize to the PB setting, and that the introduction of costs leads to substantially worse guarantees, thereby exacerbating the welfare-representation trade-off. We further study how the requirement of proportionality over voting rules effects the guarantees on social welfare and representation. We study the latter point also empirically, both on real and synthetic datasets. We show that variants of the recently suggested voting rule Rule-X (which satisfies proportionality) do very well in practice both with respect to social welfare and representation.

FOCS Conference 2013 Conference Paper

Chasing the K-Colorability Threshold

• Amin Coja-Oghlan
• Dan Vilenchik

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.

SODA Conference 2009 Conference Paper

On smoothed k -CNF formulas and the Walksat algorithm

• Amin Coja-Oghlan
• Uriel Feige
• Alan M. Frieze
• Michael Krivelevich
• Dan Vilenchik

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 ≥ ∊ −- k ln 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 Ω(2 k / k 2 ) 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.

SODA Conference 2006 Conference Paper

Solving random satisfiable 3CNF formulas in expected polynomial time

• Michael Krivelevich
• Dan Vilenchik