Graph-based fake news detectors link news articles that share readers and let a graph neural network pass information along those links. That network is a model that updates each node's representation from its neighbours. The links are noisy: a viral true story shares readers with many fake ones. The current best fix learns to down-weight suspicious links. Denoising of this kind has a side effect nobody measures. Cutting links can split the graph into pieces, or leave pieces hanging on a single link (a "bridge"). Articles in those pieces lose the neighbourhood evidence the detector relies on. A small, one-link-deep loss of data, such as users deleting their posts, can then silently change predictions.
We propose to treat the repair of this damage as a classic network-resilience problem. After a learned denoiser marks links for removal, we put back the cheapest set of removed links needed to keep every part of the graph "2-edge-connected." In such a graph, no single link deletion can cut off a group of articles. "Cheapest" means preferring the links the denoiser found least suspicious. This repair step is exactly a tree/forest augmentation problem from the approximation-algorithms literature, and it is small enough to solve with a linear program. Hyperparameter optimization plays the role of the fair referee. Every method gets the same tuning budget, and we measure how sensitive each one is to its pruning threshold. The point is to tell whether any gain is structural rather than a tuning artifact.
Core Claim
The claim is that connectivity-preserving repair makes a denoised fake news graph robust to losing engagement data, at small cost to clean accuracy. The repair is a minimum-cost 2-edge-connectivity augmentation over the links the denoiser removed. The robustness should show up at test time, when a fraction of user engagements disappear, either at random or by targeted deletion. There, we predict that repaired graphs keep their F1 score while plain thresholded denoising degrades. We also predict that a simpler "keep a spanning tree" backbone, which guarantees connectivity but not tolerance of a single failure, sits in between.
This is different from the closest existing work. DECOR scores each article–article link with a small network over two node degrees and a co-engagement count, and scales link weights accordingly. It motivates this proposal, because it shows that cross-veracity links are the dominant noise. It also supplies our denoiser. But DECOR makes each link decision locally and places no constraint on what the remaining graph looks like globally. We keep DECOR's scores and add a global structural guarantee on top of them.
The failure mode matters practically. FakeNewsNet notes that platform API restrictions make the social context decay and hard to redistribute. A detector whose evidence rests on bridges is fragile to exactly this decay.
Research Program
The pipeline has three stages. First, we build the article co-engagement graph as DECOR does and train its degree-correction scorer. This yields a mask value $m_e \in [0,1]$ for each link $e$. Links with $m_e \ge \tau$ are retained, where $\tau$ is a tunable threshold. The rest become repair candidates.
Second, we find the bridges of the retained graph in linear time. We then collapse each 2-edge-connected block to a single node. This turns the retained graph into a forest whose edges are exactly the bridges, plus any gaps where the original graph was connected but the retained one is not. The repair task is now a forest augmentation instance. Retained links are free, each candidate link covers the forest path between its endpoints, and every forest edge must be covered. This is the same structure analysed in Breaching the 2-approximation barrier for the forest augmentation problem, which gives a 1.9973-approximation through intricate credit arguments. We borrow the problem formulation, not that algorithm. We restrict the target to blocks that were 2-edge-connected in the original, unpruned graph, since repair cannot create redundancy that never existed.
Third, we solve the cut linear program for this instance:
$$\min \sum_{e \in C} c_e x_e \quad \text{s.t.} \quad \sum_{e \in C:\, e \text{ covers } b} x_e \ge 1 \;\; \text{for every forest edge } b, \qquad 0 \le x_e \le 1.$$
Here $C$ is the set of candidate (pruned) links. The cost $c_e = 1 - m_e + \epsilon$ makes the least suspicious links cheapest. The variable $x_e$ is the fractional decision to restore link $e$. Because each candidate covers a path, the program has one constraint per bridge. It is therefore small even for GossipCop-sized graphs.
We round the fractional solution in the spirit of A Simple LP-Based Approximation Algorithm for the Matching Augmentation Problem. That paper uses fractional values to order a search and then solves the resulting tree instance exactly. Our version is simpler: we take links in decreasing $x_e$ and then greedily cover any remaining bridges. That paper fixes its rounding constants for worst-case proofs. We instead treat the rounding threshold as a hyperparameter, alongside $\tau$. Restored links re-enter the graph at a floor weight rather than their original weight, so the detector can still discount them.
The analysis has three parts. We measure how much fragmentation denoising actually causes: the fraction of articles isolated or sitting behind a bridge, as a function of $\tau$. We measure how many cross-veracity links the repair reintroduces, which is the direct cost of the tension between denoising and connectivity. We also measure whether articles near repaired regions are the ones whose predictions change.
Baselines
The naive reference point is the graph neural network with no refinement at all: GCN, GIN and GraphConv on the raw co-engagement graph. It never fragments the graph, so it bounds how much fragmentation could possibly matter. We also run a text-only classifier on the same splits, to confirm that graph structure is contributing on these benchmarks.
For context, FakeNewsNet reports that its Social Article Fusion model reaches accuracy "around 69.1% on PolitiFact" and "71.7% on GossipCop." FACTOID shows that interaction topology alone gives a 61.6% F1 for spreader detection. Both results argue that structure carries signal worth protecting.
The strongest existing method is DECOR, run with its soft mask exactly as published. The file reports its gains only as relative improvements: "increasing the F1 score by 4.55% on PolitiFact" and "2.51% on GossipCop." It contains no absolute DECOR F1 values and no DECOR numbers on FANG or MC-Fake. We will therefore reproduce DECOR ourselves under our protocol and treat that reproduction as the reference. We also run a hard-threshold variant of DECOR, which is our method with the repair step switched off.
Two ablations isolate the key ingredient. The first is a maximum-weight spanning forest backbone. It keeps the highest-mask links needed to preserve the original connected components. It guarantees reachability but not tolerance of a single link failure, which separates "stay connected" from "survive one failure." The second is random repair: it restores the same number of pruned links as our method, chosen uniformly. This separates the value of choosing which links to restore from the mere effect of restoring more links.
Fairness is handled by one protocol for all methods. Every method gets the same splits and five seeds. Every method also gets the same hyperparameter budget: the same number of random-search trials over a shared search space covering learning rate, hidden size, dropout and depth, plus each method's own thresholds. This follows the lesson of Quantifying the Hyperparameter Sensitivity of Neural Networks for Character-level Sequence-to-Sequence Tasks, where a fully tuned LSTM matched a Transformer. MolRep found the same pattern at scale: once everything was tuned, no model dominated across tasks.
Beating the strongest competitor means two things. On clean test graphs, our F1 must be statistically indistinguishable from tuned DECOR. Under engagement deletion, our F1 must be significantly higher than tuned DECOR, hard-threshold DECOR and the spanning-forest backbone, across seeds.
Why not just…?
Why not just use DECOR's soft mask, which never literally deletes a link? A weight of 0.02 disconnects a region for practical purposes, even if the edge formally exists. We will check this directly. We compute effective fragmentation by thresholding soft weights at several small values, and we measure deletion robustness of soft DECOR itself. If soft DECOR proves as robust as our repaired graph, the repair step is unnecessary, and we will report that rather than argue around it.
Why not just keep a spanning tree of the most trusted links? This is the most serious threat, because it is simpler and guarantees connectivity. Its weakness is that every tree link is a bridge, so deleting any one engagement link cuts off a subtree. The spanning-forest ablation settles the question empirically. If it matches 2-edge-connected repair under targeted deletion, the extra redundancy is not worth its cost in reintroduced noise. We would then recommend the tree backbone as the finding.
Why not just tune the plain graph network properly and skip refinement altogether? DECOR's reported gains come from its own tuning. Wiemerslage et al. and MolRep show that such margins often shrink under equal-budget tuning. It is possible that a well-tuned unrefined GCN matches every refinement method. The equal-budget protocol answers this, and we will report the outcome whichever way it falls. We will also report sensitivity to $\tau$ with Wiemerslage et al.'s Percentage of Best-Equivalent Runs and Relative Performance at $k$. A method that works only in a narrow threshold band is a weaker contribution than its best run suggests.
Why not just use text and metadata and ignore the graph? The evidence in FakeNewsNet and FACTOID favours structure, and the text-only baseline checks that this holds in our setup. If text alone matches the graph methods on some dataset, deletion robustness is moot there, and we will say so.
Proposed Experiments
The benchmarks are the PolitiFact and GossipCop subsets of FakeNewsNet, using DECOR's graph construction. We add FANG and MC-Fake for the cross-topic setting DECOR also uses. Metrics are macro F1 and accuracy on clean test graphs. We also report F1 as a function of the fraction of user engagements deleted before the co-engagement graph is rebuilt, at 0, 10, 20 and 40 percent. Deletion is applied in two ways: uniformly, simulating data decay, and targeted at the retained graph's highest-traffic links, simulating an adversary or selective takedowns. Secondary measurements are the fraction of articles behind bridges, the number and homophily of restored links, repair runtime, and the sensitivity metrics above.
The first decisive check is diagnostic, and it can end the project early. We tune hard-threshold DECOR and inspect its best configuration. If that graph leaves almost no articles isolated or behind bridges, there is nothing to repair. We would then report that finding as a negative result about the value of connectivity constraints in these graphs.
The second check is the central one. Under targeted deletion at 20 percent, 2-edge-connected repair should beat both hard-threshold DECOR and the spanning-forest backbone by more than the seed-to-seed spread. Clean-graph F1 should stay within that spread of tuned DECOR. Random repair should fall below our method, showing that the linear-program choice of links matters and not just their count.
The third check asks whether DECOR's advantage over a tuned plain GCN survives equal-budget tuning at all. Whatever the answer, it frames every other number in the study.
References
- DECOR: Degree-Corrected Social Graph Refinement for Fake News Detection
- FakeNewsNet: A Data Repository with News Content, Social Context, and Spatiotemporal Information for Studying Fake News on Social Media
- Breaching the 2-approximation barrier for the forest augmentation problem
- A Simple LP-Based Approximation Algorithm for the Matching Augmentation Problem
- FACTOID: A New Dataset for Identifying Misinformation Spreaders and Political Bias
- Quantifying the Hyperparameter Sensitivity of Neural Networks for Character-level Sequence-to-Sequence Tasks
- MolRep: A Deep Representation Learning Library for Molecular Property Prediction