Many sentiment systems learn which words are positive or negative without human labels. They start from a handful of seed words such as "excellent" and "poor", measure how often other words co-occur with them in a large text collection, and spread polarity outward through a graph of word associations. This makes them cheap and domain-adaptable. It also gives them a weakness first studied in a different field. In network coding, where routers mix packets together instead of forwarding them, one corrupted packet does not stay put: it gets folded into every downstream mixture. Polarity propagation over a word graph is the same kind of linear mixing process. Someone who controls a small slice of the corpus, for example a few hundred planted reviews from one site, can shift co-occurrence counts around a few well-connected words. Propagation then spreads that shift across the lexicon, and the corrupted lexicon goes on to feed review classifiers or the word-masking choices of sentiment-aware pre-training.
The proposal has two parts. First, it quantifies this cascade. Second, it borrows the localization idea from network coding, where each network edge leaves a traceable algebraic fingerprint on what the receiver sees, and applies it to locate which data sources polluted a lexicon. Because the propagation map is known and close to linear, each source's effect on the final polarities can be computed cheaply and exactly to first order. The central bet is that defenses must judge sources by the damage they do after mixing, not by how unusual their raw counts look. Planted co-occurrences can look entirely ordinary one at a time. Their harm depends on where they enter the graph.
Core Claim
In seed-based polarity propagation, write the lexicon as $s = (I - \alpha P)^{-1} y$. Here $P$ is the normalized word-association matrix built from positive PMI (pointwise mutual information, how much more often two words co-occur than chance predicts), $y$ holds the seed polarities, and $\alpha \in (0,1)$ controls how far polarity spreads. A source $k$ that contributes a change $\delta P_k$ to the association matrix shifts the lexicon, to first order, by
$$\delta s_k \approx \alpha (I - \alpha P)^{-1}\, \delta P_k\, s .$$
This expression is the text analogue of an impulse response vector: the signature that one input leaves on the output after passing through the mixing operator.
The claim has three parts.
The amplification part says the number of words whose polarity flips per planted co-occurrence grows with the operator $(I-\alpha P)^{-1}$ evaluated around the injection point. An attacker who targets hub words therefore needs far less budget than one who targets the word they want flipped directly.
The detection part says that defenses which trim or cap raw counts will miss such attacks. The same attacks will be visible in $\delta s_k$ as unusually large and sign-coherent shifts relative to the source's size.
The defense part says that down-weighting sources by their propagated influence recovers clean-lexicon accuracy at a small fraction of the cost of rebuilding the lexicon once per held-out source.
Relation to Prior Work
Prior work plays three roles here: it motivates the threat, constrains the design, or supplies the method.
The pollution mechanism comes from network coding. Multiple-Access Network Information-Flow and Correction Codes shows how a single injected error vector, once mixed by honest nodes, corrupts every downstream combination. We use this as the model of the cascade.
The defenses from that literature mostly constrain rather than supply our design. Subspace signatures (Signing a Linear Subspace: Signature Schemes for Network Coding, Preventing Pollution Attacks in Multi-Source Network Coding) authenticate what an honest source sent. In corpus poisoning, the malicious source is itself the author, so authentication certifies exactly the content we need to reject. We therefore do not port signatures.
The localization line does supply the method. Passive Network Tomography for Erroneous Networks: A Network Coding Approach locates adversarial edges from end-to-end observations using per-edge algebraic fingerprints. It also shows that localization is intractable under random mixing unless the topology is known. In our setting the topology is known: we build the word graph ourselves and know which source contributed each count. That is exactly the condition under which tracing becomes cheap. We take the fingerprint idea and drop the finite-field coding machinery.
On the sentiment side, Thumbs Up or Thumbs Down? defines seed-difference polarity (SO-PMI). Measuring praise and criticism generalizes it to balanced seed sets. Graph and double-propagation methods (Expanding Domain Sentiment Lexicon through Double Propagation, Semantic Lexicon Construction via Spectral Analysis) spread labels across word graphs. All of these treat propagation as benign. On the Impact of Seed Words on Sentiment Polarity Lexicon Induction motivates the threat by showing that induced lexicons are sensitive to small changes at the seeds. Studying an adversary who exploits that sensitivity is the next step it does not take.
SKEP supplies the downstream stake. It mines sentiment words and aspect-sentiment pairs by PMI from 46 seeds and uses them to choose which words to mask during pre-training, so a poisoned mining step corrupts the pre-training signal itself.
The closest adversarial work is profile pollution of sequential recommenders (Precision Profile Pollution Attack via Influence Function, Potent but Stealthy). Those papers use influence functions to craft attacks on learned recommender models. We use the same kind of sensitivity reasoning in a setting where it is exact up to first order, because the propagation map is closed-form. We use it mainly for source localization and defense rather than for building attacks.
RAG-poisoning detectors such as Knowledge Database or Poison Base? inspect a model's internal activations on individual retrieved items. We instead attribute damage at the level of sources through a mixing operator.
Research Program
The work has three stages.
The first stage builds a testbed. Source-partitioned corpora are constructed from Amazon-2 by treating product categories and reviewer groups as sources. A propagation lexicon is induced from the SKEP seeds and, separately, from the Littman–Turney paradigm seeds.
The second stage builds an attack suite that controls a fraction $\rho$ of sources, from 0.1% to 5% of tokens. It contains three attackers. A naive attacker plants co-occurrences of target words with negative seeds. A hub attacker chooses injection words greedily to maximize $\|\delta s\|$ on a target set, using the first-order expression above. A stealth attacker adds the constraint that per-pair counts stay within the clean per-source count distribution, which is designed to defeat count-level trimming.
The third stage builds the defense, which we call propagated-influence screening. For each source it computes $\delta s_k$ with a single sparse linear solve. It scores the source by the size of $\delta s_k$ normalized by the source's token count, weighted by how consistently the shift points in one sign direction. It then re-induces the lexicon with flagged sources down-weighted. A cross-check uses exact leave-one-out on a subsample of sources to measure how accurate the first-order approximation is. We expect it to degrade when single sources are large, and we will report where it breaks.
Baselines
The naive reference is the undefended lexicon induced from the poisoned corpus. We report both its clean-corpus accuracy and its poisoned accuracy. The gap between them defines how much harm the attack does and therefore how much there is to recover.
The strongest cheap competitor is count-level robust statistics. This means capping each source's contribution to every word-pair count at a per-source quantile, together with trimmed-mean aggregation of per-source PMI. It is the obvious defense, and it costs essentially nothing. We tune its quantile threshold on the same held-out clean validation split, with the same number of configurations as our scoring threshold. Beating it means recovering at least half of the remaining accuracy gap under the stealth attacker at matched false-flag rates on clean sources. We also expect to roughly tie it under the naive attacker, and we will report that tie honestly.
The strongest expensive competitor is exact leave-one-source-out re-induction. Its scores are what our first-order method approximates. Matching its detection quality within a few points of area under the ROC curve, while using one linear solve per source instead of a full re-induction, counts as success.
A seed-ensemble baseline, which induces the lexicon from several disjoint seed subsets and takes the median polarity, tests whether robustness to seed sensitivity alone neutralizes the attack.
The key-ingredient ablation scores sources by the size of their raw $\delta P_k$ instead of the propagated $\delta s_k$. This isolates the core claim: if raw-perturbation scoring does as well, then post-mixing measurement adds nothing.
Why not just…?
Why not just trim or cap anomalous co-occurrence counts? This is the real threat, and the stealth attacker exists specifically to test it. If capping matches our screening against an attacker that stays inside the clean count distribution, the core claim is wrong. Our prediction rests on the cascade argument: harm is set by the operator $(I-\alpha P)^{-1}$ at the injection point, not by count magnitude. Turney's movie-domain failure, 65.83% versus 84% on automobiles (Thumbs Up or Thumbs Down?), also shows that legitimate domains produce unusual counts. Count trimming should therefore pay a false-flag cost on genuine domain variation.
Why not just fine-tune a supervised model and ignore the lexicon? That avoids the attack only for users who have labels. The unsupervised mining step exists because labels are missing, and SKEP shows the mined knowledge matters: SKEP-base reaches 81.32 accuracy on Sem-L, against 79.22 for RoBERTa-large (SKEP). Whether poisoned mining actually erodes that gain is an empirical question, which the downstream experiment tests.
Why not just sign sources cryptographically, as network coding does? Signatures prove who sent the data. Here the poisoner is a genuine author of authentic-looking reviews. Signatures also carry per-dimension overhead with proven lower bounds (Preventing Pollution Attacks in Multi-Source Network Coding). Provenance is useful only as the source labels our method consumes.
Why not just use influence functions as in recommender pollution work? In a learned recommender, an influence function is only an approximation of how training data affects the model. Here the propagation map is closed-form, so influence reduces to the linear solve above. The novelty lies in source-level localization and in measuring robustness after mixing, not in the sensitivity calculus itself.
Proposed Experiments
The first experiment measures amplification. For each attacker and budget $\rho$, we measure the fraction of lexicon words whose sign flips and the drop in agreement with the clean lexicon. The decisive check is whether the hub attacker flips a target word set with substantially smaller $\rho$ than the naive attacker. If it does not, the cascade framing adds little.
The second experiment measures detection. We report area under the ROC curve for identifying poisoned sources, comparing our screening, count capping, exact leave-one-out, and the raw-$\delta P$ ablation.
The third experiment measures downstream harm and recovery. We run SO-PMI-style review classification on the Epinions corpus, where Turney reports 74.39% average accuracy across 410 reviews. We also run lexicon-based sentence classification on SST, with the recursive neural tensor network's 85.4% binary accuracy from Recursive Deep Models for Semantic Compositionality Over a Sentiment Treebank as an upper reference rather than a competitor. Clean, poisoned, and defended lexicons are compared on both.
The fourth experiment is a small-scale SKEP-style continued pre-training run in which masks are chosen from clean, poisoned, or defended mined knowledge, evaluated on Sem-L. Full-scale SKEP pre-training is outside the budget. We report the reduced-scale clean number alongside SKEP's published 81.32 rather than claiming parity with it.
The proposal is falsified if count capping matches screening under the stealth attacker, or if poisoned mining does not measurably move downstream accuracy.
References
- Multiple-access Network Information-flow and Correction Codes
- Signing a Linear Subspace: Signature Schemes for Network Coding
- Preventing Pollution Attacks in Multi-source Network Coding
- Passive Network Tomography for Erroneous Networks: A Network Coding Approach
- Thumbs Up or Thumbs Down? Semantic Orientation Applied to Unsupervised Classification of Reviews
- Measuring praise and criticism: Inference of semantic orientation from association
- Expanding Domain Sentiment Lexicon through Double Propagation
- Semantic Lexicon Construction: Learning from Unlabeled Data via Spectral Analysis
- On the Impact of Seed Words on Sentiment Polarity Lexicon Induction
- SKEP: Sentiment Knowledge Enhanced Pre-training for Sentiment Analysis
- Precision Profile Pollution Attack on Sequential Recommenders via Influence Function
- Potent but Stealthy: Rethink Profile Pollution Against Sequential Recommendation via Bi-Level Constrained Reinforcement Paradigm
- Knowledge Database or Poison Base? Detecting RAG Poisoning Attack through LLM Activations
- Recursive Deep Models for Semantic Compositionality Over a Sentiment Treebank