CS Paper Radar

JECHO: Scalable Echo Chamber Detection via Jaccard-based Homophily and Seed Expansion

Ali Safarpoor Dehkordi, Atsushi Miyauchi, Francesco Bonchi, Ahad N. Zehmakan

cs.SI ·submitted 2026-08-22 13:52 UTC · v1
top venuetheory

Abstract

Detecting echo chambers is critical for understanding and limiting negative social phenomena, such as online polarization, misinformation, and conspiracy theory diffusion. However, the echo chamber detection (ECD) problem yet lacks a rigorous algorithmic foundation. We address this gap by formalizing a unified definition of echo chambers based on three principles: internal opinion homogeneity, opinion extremism, and structural isolation. Under such a definition, we establish the theoretical hardness of the ECD problem, proving it is NP-hard via a reduction from the conductance minimization problem. To circumvent this computational barrier, we derive a theoretical lower bound on the Jaccard-based homophily (JHO) of nodes that reside within valid echo chambers. This guarantee motivates JECHO, a novel algorithm that detects echo chambers via local seed expansion rather than global enumeration. JECHO first identifies seeds that exceed the JHO threshold and then applies a score-based expansion to optimize structural isolation. Extensive experiments on real-world and synthetic networks demonstrate that our theory-guided approach detects more structurally isolated echo chambers than state-of-the-art methods while reducing runtime by orders of magnitude.

Comment
Accepted to CIKM 2026

Closest papers

Nearest neighbours by meaning across the whole index.

Coherent belief and opinion propagation produces more echo chambers: corrected version

cs.AI cs.MA ·2026-11-19 ·Hiro Kataoka, J{é}r{ô}me Euzenat, Koji Hasebe
publishedhot direction similarity 0.63
Abstract · kataoka2026e

The occurrence of echo chambers is a well-known phenomenon in social networks. Echo chambers are groups of agents satisfying three properties: homogeneity, i.e., sharing the same opinion, segregation, i.e., listening primarily to agents of the same group, and reinforcement, i.e., increasing opinion similarity over time. Opinion dynamics models have been used to explain how echo chambers occur through agents updating their opinions. However, social network users also exchange beliefs supporting their opinions. Here, we aim at identifying the effect of propagating beliefs together with opinions on the formation of echo chambers. For that purpose, we complement an existing opinion dynamics model with classical belief merge operations. Beliefs and opinions are also maintained coherent guided by values that agents share. We introduce measures, applying to either beliefs and opinions, to identify echo chambers based on the three properties. This model is used to simulate opinion and belief propagation with varying initial conditions and agent tolerance for different opinions/beliefs. Results confirm the occurrence of echo chambers observed in previous opinion dynamics studies in a different setting and with a stricter measure. They also demonstrate the occurrence of echo chambers with belief propagation. Finally, they show that connecting opinions to beliefs and maintaining their coherence increases the number of belief echo chambers, but that they involve a reduced number of agents.

0.42

Revisiting the Objective of Echo Chamber Detection

cs.LG ·2026-09-16 ·Abylaikhan Bexeit, Kushani Perera, Shanika Karunasekera, Jean Honorio
position similarity 0.62
Abstract

In this paper, we study the detection of an echo chamber in a social network, i.e., the identification of a set of nodes that agree on a topic, while disagreeing with the rest of nodes. We argue that this problem is different from other social network analysis problems such as community detection, and from other graph problems such as maximum graph cut and maximum clique. To the best of our knowledge, we are the first to formalize the objective function of echo chamber detection, by using the theory of Fourier transforms of set functions (Stobbe and Krause, 2012). We propose scalable semidefinite relaxation, solved via an interior point method and sparse linear algebra. Experimentally, our algorithm recovers the ground truth echo chamber better than competing methods on small synthetic experiments. Our algorithm produces echo chambers with better network properties than competing methods on large real-world datasets. To independently validate our proposed objective function, we show that our algorithm finds echo chambers with more agreements with suspended users than competing methods on a small real-world dataset.

0.24

Not Just Oversmoothing: Detecting the Echo Chamber Effect in Graph Neural Networks

cs.LG ·2026-09-06 ·Asela Hevapathige, Ahad N. Zehmakan, Asiri Wijesinghe, Saman Halgamuge
similarity 0.55
Abstract

Oversmoothing is a well-known failure mode of Graph Neural Networks (GNNs). However, most existing diagnostics rely on global aggregation measures that fail to capture the heterogeneous dynamics of message passing. Real-world graphs exhibit pronounced community structure, and message passing operates on two timescales, with representations collapsing rapidly within communities and slowly across them. This creates a critical gap in which intra-community representations can become indistinguishable while inter community separation persists, a failure mode that we refer to as the Echo Chamber Effect. To quantify this effect, we introduce the Echo Chamber Index (ECI), which stratifies pairwise distances by community membership and reveals when global energy diminishes while inter-community separation persists. ECI further shows that feature retention mechanisms can preserve the echo chamber under the conditions of our theoretical analysis. The consequences depend on label structure: when communities align with classes, the echo chamber can sharpen node classification, whereas when they do not, the same collapse makes classification provably harder. Motivated by this analysis, we propose Community-Aware Split Propagation (CASP), a lightweight plugin that decouples intra- and inter-community aggregation and learns their balance from label structure. CASP improves diverse backbone GNNs across most evaluated homophilic and heterophilic settings.

0.10

Not Everyone Has a Voice, or an Ear, on Social Media: The Poster-Observer Model of Opinion Dynamics

cs.SI ·2026-10-30 ·Nikos Theologis, Aristides Gionis, Evaggelia Pitoura, Evimaria Terzi, Panayiotis Tsaparas
similarity 0.55
Abstract

Classic modeling of opinion dynamics via the Friedkin-Johnsen (FJ) model relies on the unrealistic assumption of synchronous communication among network users. Social media, however, exhibit extreme participation asymmetries: a vast majority of users silently observe, while a tiny minority creates and broadcasts most of the content. To capture this reality, we introduce the Poster-Observer FJ (PO-FJ) model, which decouples user communication into distinct posting and observing behaviors. This formulation fundamentally alters network dynamics by preventing convergence to a static equilibrium, driving opinions into perpetual oscillations. We establish closed-form expressions for these new dynamics and generalize classic metrics of public opinion, polarization, and disagreement under the PO-FJ model. By leveraging the novel Poster-Observer dynamics, we introduce a realistic and scalable intervention algorithm for conflict mitigation. Through experiments on synthetic and real-world networks, we demonstrate the efficacy and efficiency of our approach in reducing social-network conflict.

0.37

Recursive Neighbor Pruning: Decentralized Community Detection with Certified Behavior from Saturated Opinion Dynamics

eess.SY ·2026-10-25 ·Anthony Couthures, Irinel-Constantin Morarescu, Vineeth Satheeskumar Varma, Samson Lasaulce, Antoine Girard
similarity 0.54
Abstract

Detecting communities, i.e., groups of densely connected nodes, usually requires a central entity that knows the whole network. We study Recursive Neighbor Pruning (RNP), a fully decentralized alternative inspired by social learning. Each agent holds a private opinion but only shows its neighbors a coarse public action, namely its opinion amplified and clipped to a fixed range. Agents repeatedly move their opinion toward the actions of their neighbors and, once opinions settle, drop the links with neighbors whose action has the opposite sign. Repeating this procedure on the remaining network splits it into communities, without any agent knowing the network or the number of communities. We use tools from nonlinear control to characterize this behavior. We show that splitting requires the amplification to exceed a threshold set by how strongly the network is bottlenecked. We also show that a group in which every member has enough of its links inside the group can no longer be split once its members agree, and that a single run separates such groups exactly when started from suitable opinions. Finally, we bound the number of runs and messages. On two standard families of synthetic networks, RNP is as accurate as the best centralized method as long as each node has fewer than about forty percent of its links outside its community, and it fails close to the value predicted by our analysis. It is more accurate than two decentralized competitors below this level, but exchanges many more messages.

0.21

Robust Opinion Maximization

cs.SI ·2026-10-30 ·Nikos Theologis, Evaggelia Pitoura, Evimaria Terzi, Panayiotis Tsaparas
similarity 0.53
Abstract

Opinion-formation models are fundamental for analyzing social behavior and understanding social dynamics. The Friedkin-Johnsen (FJ) model is the most commonly used model in this line of research. In FJ, the expressed opinion of an individual evolves over time as the combination of the opinions of their peers and a fixed inner opinion, weighted by their stubbornness. A problem that has received considerable attention is the problem of Opinion Maximization, where the goal is to adjust the parameters of the FJ model, such as stubbornness, or inner opinions, to maximize the average expressed opinion, i.e., the public opinion. Most existing work assumes full knowledge of the parameters of the model, which is unrealistic. In this paper, we introduce the problem of Robust Opinion Maximization, where we assume uncertainty for the inner opinions of the nodes, and we maximize the public opinion under worst-case assumptions on this uncertainty. Using tools from Robust Optimization, we formulate our problem as a max-min problem, and we develop an optimal two-step solution that is both highly intuitive and efficient. Experiments on several real-world networks demonstrate that our approach can achieve robust solutions for million-node graphs in minutes, and reveal that our robust strategies can significantly mitigate the impact of noise compared to standard baselines.

0.13

Robust Action Clusters and Cascades in Opinion Dynamics with Heterogeneous Action Thresholds

eess.SY ·2026-11-16 ·Hassan Munif, Anthony Couthures, Vineeth Satheeskumar Varma, Samson Lasaulce, Irinel-Constantin Morarescu
similarity 0.52
Abstract

We study the preservation and propagation of public actions in networks whose agents hold continuous private opinions. Agents update their opinions from their neighbors' observed actions and express them through action rules whose thresholds differ across agents. We characterize groups of agents that preserve a given common action regardless of the outsiders' actions. We call such a group, paired with that action, a robust action cluster. We show that a group is a robust action cluster for that action if and only if each member places enough of its influence weight on the group, where the required influence depends on the member's own action rule. We further give a sufficient condition under which an agent outside the cluster permanently adopts the cluster's action, and we iterate it to obtain a cascade of agents that are guaranteed to adopt that action. Finally, numerical examples show that replacing heterogeneous thresholds by their mean can change both the propagation of an action and the presence of robust action clusters.

0.32

GraphWake: Group Polarization via Memory-Mediated Polarization Cascade in LLM-Agent Communities

cs.AI ·2026-08-18 ·Haoran Bu, Zejian Chen, Litian Zhang, Xi Zhang
similarity 0.52
Abstract

LLM-driven agents can autonomously exchange opinions on online platforms and form communities. Such agent-operated social platforms raise a new security concern: attackers may manipulate agents to induce group polarization. Existing methods manipulate agent prompts or construct echo chambers, both of which are difficult to realize in practice. We therefore formulate a new threat, Memory-Mediated Polarization Cascade, which uses agent memory as a persistence channel and public discussion as a propagation channel. This threat contains three stages. During exposure and memory retention, the attacker exposes a small set of target agents to arguments that reinforce their respective stated stances. The targets' memory systems then process and retain these arguments. During retrieval and reproduction, a shared stance-neutral discussion cues the targets to retrieve and reproduce their respective retained arguments. During iterative propagation, untreated agents influenced by the reproduced arguments restate and spread them. We instantiate this threat in GraphWake with three components: (i) stance-support argumentation knowledge graphs construct knowledge-based arguments; (ii) axiom-oriented triple selection distills them for reliable retention and reproduction; and (iii) stance-neutral memory cueing triggers concurrent retrieval and reproduction, initiating propagation. Experiments across multiple discussions and memory systems show that GraphWake substantially increases group polarization. These findings reveal a community-level polarization risk.

0.53