Bias Fills the Evidence Gap in Linearized Graph Reasoning

Language models are increasingly used to make predictions about networks by reading them as text. Take a friend-recommendation or citation-recommendation question: will user A connect to user B? One common approach is to write out A's and B's profiles along with a handful of their neighbors as a prompt, then ask a large language model (LLM) to answer. Turning a graph into a token sequence like this is called graph linearization, and it inevitably throws information away. Two nodes that are neighbors in the graph can end up hundreds of tokens apart, and the pipeline must pick which few neighbors fit in the prompt. This note argues that those two choices, which neighbors to show and where to place them, are a major and unmeasured source of demographic bias. The mechanism is simple. When the prompt contains little real structural evidence about whether A and B are connected, the model fills the gap with what it does have: demographic cues in the profile text. Those cues correlate with links because real networks are segregated.

The proposal is to measure this effect directly and to test a specific fix. The fix is to fill the prompt with the pair's shared structure, meaning common neighbors and short connecting paths placed next to the query, instead of neighbors chosen for semantic similarity. The prediction is that this reduces how much the model amplifies segregation without the utility loss that weight-level debiasing usually causes. If the fix works, fairness in this setting can be improved by changing what the model is shown rather than what the model is.

Core Claim

The claim is that dyadic bias in LLM link prediction over linearized graphs rises as query-relevant structural evidence in the prompt falls. Dyadic bias here means the tendency to predict links more readily between same-group pairs than cross-group pairs.

Two findings from different literatures motivate this. First, Uncovering Stereotypes in Large Language Models: A Task Complexity-based Approach found that as prompts demand more relational reasoning, models refuse less often and fall back on ingrained stereotypes; ChatGPT's refusal rate fell from 32.8% to 29.4% across its complexity levels. Second, Fair Text-Attributed Graph Representation Learning (FairTAG) showed that language-model encoders on text-rich graphs overfit to "easy" same-group edges, and that downstream graph layers amplify this further.

The standard linearization recipe makes both problems worse. Better Together picks the neighbors to verbalize by semantic similarity to the query, which plausibly acts as a homophily filter. The topological distortions catalogued under graph linearization bury whatever connecting structure survives: spurious adjacency and broken distances (Canonical Tree Cover Neural Networks), and misleading traversal jumps (Random Search Neural Networks).

To separate amplifying bias from merely mirroring true network segregation, the analysis uses an amplification ratio:

$$A = \frac{\mathbb{E}[\hat{y} \mid \text{same group}] - \mathbb{E}[\hat{y} \mid \text{cross group}]}{\Pr[y=1 \mid \text{same group}] - \Pr[y=1 \mid \text{cross group}]}$$

In this ratio, $\hat{y}$ is the model's predicted link probability, $y$ is the true link label, and group membership refers to the sensitive attribute of the two endpoints. $A>1$ means the model exaggerates the segregation present in the data. The analysis also reports the usual dyadic demographic parity gap (the numerator alone), because that is the metric the prior work reports. The central hypothesis is that $A$ falls as the prompt contains more of the pair's shared structure, and that it falls more for evidence-first prompts than for semantically sorted prompts at equal token budget.

Research Program

The first component is a controlled "evidence dial." For each query pair, prompts are built under a fixed token budget. A small open model (LLaMA2-7B, matching GNN-RAG) is evaluated both zero-shot and after light fine-tuning. Four things vary independently:

  • Evidence amount: how much of the pair's shared structure is included, from zero common neighbors or paths up to all of them within budget.
  • Selection rule: random, semantic similarity as in Better Together, group-stratified, or evidence-first.
  • Placement: whether connecting paths sit next to the query or are scattered through the prompt, which probes distance distortion directly.
  • Demographic cues: whether profile text is left intact or counterfactually swapped, so that A's region or gender field is changed and everything else is held fixed.

The swap separates how much of the prediction rides on demographic text from how much rides on structure. A counterfactual flip rate, the fraction of predictions that change under the swap, is reported as a per-condition estimate of stereotype reliance.

The second component is the method itself: evidence-first linearization. Candidate context is ranked by topological relevance to the pair rather than by text similarity to the query. The first candidates are shortest connecting paths, verbalized as A -> friend_of -> C -> friend_of -> B in the style GNN-RAG uses for question answering. Next come common neighbors, then each endpoint's highest-degree neighbors. The selected structure is placed in a compact block adjacent to the query, following the hierarchical formatting idea of Link Prediction on Textual Edge Graphs so that path identity survives flattening.

This method involves no fairness loss and no weight edit. That is deliberate: the test is whether giving the model real evidence is enough to stop it from reaching for the demographic shortcut. A second variant adds light fine-tuning on these prompts to check whether the effect persists once the model is trained to use structure.

The third component is an honesty check against evasive fairness. Rethinking Prompt-based Debiasing showed that fairness prompts can produce "false prosperity," where the model answers "unknown" instead of reasoning. In link prediction, the equivalent failure is predicting "no link" or low confidence on every cross-group pair. So the note reports cross-group recall and the rate of near-0.5 predictions per group alongside every parity number. A method is not credited with reducing bias if the reduction comes from abstaining on minority pairs.

Baselines

The naive reference point is semantic-similarity linearization as in Better Together: 1-hop neighbors ranked by embedding similarity to the query, concatenated with separators. That paper reports Wikidata5M Hits@1 rising from 0.240 to 0.327 with this context on T5-small. This establishes that the recipe helps utility, but the paper measured no fairness quantity. It is the default any practitioner would reach for, so it defines the amplification this work expects to see. A bare "no context, profiles only" prompt is also included as the do-nothing floor.

The strongest existing fairness method is FairTAG. It fine-tunes the language-model encoder with fairness-score-based edge dropping and DPO on boundary "anchor" nodes, where DPO (direct preference optimization) trains the model to prefer one output over another from paired examples. FairTAG reports an 18.4% lead in mixed-dyadic demographic parity over the nearest competitor on Pokec-n while maintaining link-prediction AUC. The file gives no exact AUC value; it is only plotted in the paper's figures. FairTAG uses the encoder-plus-graph-network paradigm rather than LLM-as-predictor, so it will be reproduced on identical train/test edge splits of Pokec-n, Pokec-z, Cora, CiteSeer, and PubMed. It will be matched in GPU-hours to the fine-tuned evidence-first variant and given the same hyperparameter search budget of 20 trials. Evidence-first linearization beats FairTAG if it reaches equal or lower mixed-dyadic parity gap at AUC no more than one point lower, or if it gives a strictly better parity–AUC Pareto front across operating thresholds, with no increase in cross-group abstention.

The topology-only fairness reference is FairAdj. It learns a reweighted adjacency inside a variational graph autoencoder, and on UNC28 it keeps AUC within about 0.6% of the biased baseline while reducing the parity gap. It will be run on frozen text embeddings, which is the "shallow cascade" a reviewer would propose. No reported result was found on Lacuna for FairAdj on Pokec with text attributes, so it will be run here.

The key ablation is group-stratified selection at the same token budget: neighbors are sampled so each group is represented in proportion to the full neighborhood, with no preference for connecting structure. This isolates whether the gain comes from evidence or from balanced composition.

Why not just…?

Why not just balance the neighbors shown in the prompt by group? This is the real threat. If stratified sampling lowers amplification as much as evidence-first selection does, the "evidence gap" story is wrong and the lesson is simply "rebalance context." Mind the Graph When Balancing Data for Fairness or Robustness gives a reason to expect balancing to cost utility when features cause the label: in their Amazon Reviews experiment, balancing dropped accuracy from 66% to 57%. Neighbor text plausibly causes link formation in this sense. The stratified ablation, crossed with the evidence dial, settles it. If amplification tracks composition rather than evidence amount, the claim is changed accordingly.

Why not just scrub demographic words from profiles? Graph structure leaks group membership: FairAdj shows message passing reconstructs demographic clusters from topology alone. Semantically sorted neighbors also carry correlated cues such as schools or hobbies. The counterfactual-swap experiment measures directly how much prediction depends on explicit attribute fields versus these proxies. If scrubbing alone reduces the amplification ratio to near 1 without hurting AUC, that result would be reported as a cheaper answer.

Why not just tell the model to ignore protected attributes, or use chain-of-thought? BiasFreeBench finds that prompting methods score 10–20% higher on its bias-free score than training methods. However, Rethinking Prompt-based Debiasing shows such gains often come from evasion. A fairness-instruction prompt is therefore included as a baseline and judged by cross-group recall and abstention rate, not by parity alone.

Why not just debias the encoder, as FairTAG does? FairTAG is a reasonable choice when you can train an encoder. But it modifies weights, it was never tested with LLMs acting as predictors over prompts, and weight-level debiasing is known to tax general ability: task-vector debiasing degraded BoolQ and COPA in BiasFreeBench. The comparison above is designed so that FairTAG can win. If it does, the contribution narrows to the diagnostic finding.

Proposed Experiments

The main experiment computes the amplification ratio, the dyadic parity gap, AUC, and the counterfactual flip rate on Pokec-n and Pokec-z, where region or gender is the sensitive attribute. It then repeats the analysis on Cora, CiteSeer, and PubMed, with research subfield as the sensitive attribute following FairAdj, to test whether the effect holds beyond social networks. Each is evaluated across the grid of evidence amount, selection rule, and placement, at three token budgets.

Three outcomes would decide the question. The first is whether amplification, measured with semantic selection, falls monotonically as the number of connecting paths revealed increases; this is the core claim, and a flat curve refutes it. The second is whether evidence-first selection beats group-stratified selection on amplification at matched budget and matched AUC; this separates evidence from composition. The third is whether placing the same paths far from the query, rather than adjacent to it, restores the amplification; if so, linearization distortion is a bias mechanism and not only a utility one. Across all three, any parity improvement that coincides with rising cross-group abstention counts as a failure.

A secondary check applies the same prompts to the knowledge-graph setting. On Wikidata5M, the test is whether semantic neighbor sorting skews predictions for person entities by nationality or institution, the halo effects documented in Investigating Subtler Biases in LLMs. It also verifies that evidence-first prompts do not fall below Better Together's reported 0.327 Hits@1.