Source-linked AI summary
Modeling Preference Dependencies with Directed Acyclic Graphs for Narrative-Driven Recommendation
Mingzhe Lu, Jian Qin, Ruize Qin, Jinhao Liu, Yunpeng Li, Hang Su
TL;DR
Narrative-driven recommendation must handle preferences that qualify and contextualize one another, a structure that existing approaches often leave implicit. PDG-F builds a directed acyclic preference graph to guide Web evidence retrieval and topological ranking. Across diverse domains, it improves recommendation performance and raises the attainable candidate-pool ceiling.
Problem
Existing narrative recommendation approaches often treat preferences as flat features or generate recommendations without explicitly representing how preferences qualify one another.
Source: §1 · p. 1Method
PDG-F uses PDG-A to build a directed acyclic graph of qualified preferences, then retrieves Web evidence along directed paths and ranks candidates through topological path scoring.
Source: §1 · p. 1, §3.2.2 · p. 3Results
PDG-F consistently improves recommendation performance across three domains, and dependency-guided retrieval raises pool recall from 0.2102 to 0.4858 on Movie, 0.2854 to 0.5481 on Book, and 0.1672 to 0.4734 on Anime.
Source: §5.1.1 · p. 7, §6 · p. 8Takeaways & Limitations
The broader candidate coverage raises the attainable performance ceiling, while the remaining ranking gap motivates more accurate evidence scoring.
Source: §6 · p. 8
Abstract
from arXiv · showhide
Narrative-driven recommendation allows users to express multifaceted needs through free-form text where stated preferences naturally qualify and condition one another. Existing methods typically treat narratives as flat keyword combinations or unconstrained generative queries, failing to capture how complex preferences hierarchically refine and contextualize each other. We propose the Preference Dependency Graph Framework (PDG-F), a narrative-driven recommendation framework centered on explicit preference dependencies. Specifically, PDG-A (PDG-Agent) first parses unstructured requests to organize user preferences and their mutual qualifications into a directed acyclic Preference Dependency Graph (PDG). Through this graph, candidate evidence from the open Web is acquired via directed path retrieval, and final recommendations are determined by topological path ranking. Comprehensive experiments across three diverse domains spanning English and Chinese contexts confirm that PDG-F consistently achieves superior recommendation performance over competitive baselines, open-domain retrieval agents, and frontier language models. Further diagnostic analyses show that our dependency-guided retrieval markedly raises the attainable candidate-pool ceiling, demonstrating the fundamental value of modeling preference dependencies in narrative-driven recommendation.
1 Introduction
Narrative requests contain preferences that qualify one another, but existing approaches often treat them as flat features or generate recommendations without explicitly modeling those dependencies. PDG-F represents those relationships in a graph that guides Web evidence retrieval and recommendation ranking.
Related approaches
- Preference dependencies remain insufficiently modeled in approaches ranging from feature extraction and semantic matching to LLM-based recommendation with external evidence.These methods can enrich narrative interpretation or candidate evidence without explicitly coordinating retrieval and evaluation around how preferences qualify one another.Source: §1 · p. 1
Motivating example
- A preference such as romance as a subplot is further qualified by how the relationship unfolds, so matching isolated keywords can select an unsuitable film.The passage contrasts humor tied to camaraderie in The Lord of the Rings with romance developed through interaction in Howl’s Moving Castle.Source: §1 · p. 1
Proposed framework
- PDG-F uses PDG-A to organize preferences and their qualifications into a dependency graph, then applies directed path retrieval and topological path ranking.The graph construction agent extracts preference elements, evaluates qualification relationships, and forms node preferences in topological order conditioned on ancestors.Source: §1 · pp. 1–2
Contributions
- Across movies, books, and anime in English and Chinese contexts, PDG-F is reported to outperform competitive baselines, retrieval engines, frontier models, and LLM agents.The paper also reports ablations and diagnostic analyses of dependency modeling.Source: §1 · p. 2
2 Related Work
Prior narrative-driven recommendation work spans explicit feature matching, representation learning, and LLM-based methods with evidence augmentation. Across these paradigms, the paper identifies a common gap: explicit modeling of preference qualifications and dependencies.
Explicit feature matching
- Feature-matching methods extract cues or narrative tropes, but do not explicitly represent modifier and qualification relationships among preferences.Examples include automated request-element extraction and trope tags for reranking.Source: §2 · p. 2
Representation learning
- Representation-learning approaches improve semantic relevance through embeddings, task adaptation, synthetic queries, and domain alignment, yet lack explicit characterization of qualification scope and dependencies.The surveyed work ranges from dual-encoder retrieval to general-purpose text embeddings.Source: §2 · p. 2
LLM-based methods
- LLM-based methods progress from direct generation to evidence-augmented recommendation, but still do not explicitly use preference dependencies to coordinate retrieval and candidate evaluation.External grounding includes collaborative retrieval, dynamic attribute templates, open-domain retrieval, and attribute completion.Source: §2 · p. 2
3.1 Problem Formulation
Narrative-driven recommendation takes a natural-language request and returns a ranked list of items that satisfy its needs. Because the candidate pool is not fixed, systems acquire candidates and evidence before scoring and ranking them.
Problem formulation
- The task is to return a ranked top-K list of items from the item space that satisfy a user’s natural-language narrative request.Requests may include target-item descriptions, reference items, and user evaluations.Source: §3.1 · p. 2
Candidate acquisition and ranking
- A system first acquires a request-specific candidate set and supporting evidence, then scores and ranks the candidates.Narrative-driven recommendation does not presuppose a fixed candidate pool; candidates can come from Web retrieval or LLM parametric knowledge.Source: §3.1 · p. 2
Scoring
- Candidate acquisition returns items and associated evidence, which the scoring function uses to evaluate how well each item satisfies the request.The formulation expresses the final output as the top-K candidates ordered by their scores.Source: §3.1 · p. 2
3.2 Preference Graph Construction
PDG-A turns narrative preferences into a directed dependency graph whose edges encode qualifications and whose node descriptions are refined using upstream context. It resolves cyclic judgments to produce an acyclic, topologically ordered graph for subsequent retrieval and evaluation.
3.2 Preference Graph Construction
- PDG-A constructs a preference dependency graph that supports downstream directed path retrieval and topological path ranking.The graph’s node preferences are generated in topological order conditioned on ancestral preferences.Source: §3.2 · pp. 2–3, Figure 1 · p. 3
3.2.1 Node: Preference Instantiation.
- Each preference node combines an atom, an interpretive perspective, and a concrete instantiation, with a feature field reserved for later contextual refinement.For example, a Harry Potter reference can yield an actor perspective and an Emma Watson instantiation.Source: §3.2.1 · p. 3
3.2.2 Edge: Qualification Dependencies.
- A directed edge from u to v means v qualifies the base preference expressed by u, capturing refinement rather than independent requirements.The agent considers the full narrative and the two node interpretations when deciding whether and in which direction to add a qualification dependency.Source: §3.2.2 · p. 3
3.2.3 Graph: Cycle Resolution.
- When local judgments create cycles, PDG-A removes the cycle edge least supported by the narrative, then uses transitive reduction to preserve reachability and establish a valid topological order.In the romance-conflict-reconciliation example, it removes the edge returning from reconciliation to romance, retaining the refinement path.Source: §3.2.3 · p. 4
- In topological order, PDG-A generates each node’s concrete preference using its initial representation, the narrative, and descriptions of its ancestors.When dependency paths converge, the path structure and original narrative are synthesized into a node description.Source: §3.2.3 · p. 4
3.3 Directed Path Retrieval
Directed path retrieval turns preference dependencies into targeted Web searches, then gathers candidate items with evidence tied to the preference nodes they address.
3.3.1 Rewriter.
- For each dependency edge, PDG-A rewrites the base preference under its target’s qualification as a targeted search query; predecessor-free nodes receive virtual-root entry queries.Queries use the narrative and initial node representations, translating qualification relationships into keywords and search operators.Source: §3.3.1 · p. 4
3.3.2 Query.
- Search results are filtered by resource type, and URLs from each dependency query are assigned to its target node for candidate recall.A node aggregates and deduplicates URLs from its incoming-edge queries; the same URL may serve multiple nodes.Source: §3.3.2 · p. 4
3.3.3 Recall.
- For each node, the system extracts identified items and preference-relevant descriptions from Web-page chunks, retaining both supporting and contradicting evidence.Candidates are consolidated within nodes after excluding items in the original request, while descriptions remain separate across nodes and retain source URLs.Source: §3.3.3 · pp. 4–5
3.4 Topological Path Ranking
Topological path ranking evaluates the same retrieved description against a node’s preference and its ancestors, then aggregates scores across the nodes where an item was recalled.
3.4.1 Initial Scoring.
- Each item description is compared with the current node’s preference and every ancestor preference, with relation judgments mapped to initial scores while respecting qualification scope and permitted alternatives.Missing details alone do not count as explicit contradiction, and a contradiction zeros only that pairwise comparison rather than removing the candidate.Source: §3.4.1 · p. 5
3.4.2 Topological Path Computation.
- In topological order, the system combines each node’s initial score with the discounted best predecessor path score, then aggregates an item’s path scores across its recalled nodes.The maximum selects among converging paths; gamma is 0.7 in the implementation, and evidence from multiple webpages mapped to one node contributes only once.Source: §3.4.2 · p. 5
4 Experiment
PDG-F (+Year) achieves the best performance across all three datasets and evaluation metrics. The experiments use movie, book, and anime recommendation benchmarks, with analysis highlighting temporal retrieval bias and differences in knowledge coverage.
4.1 Experimental Setup
- Evaluation covers Reddit MovieSuggestions plus 30 English Book queries and 30 Chinese Anime queries, using Precision@10, Recall@10, and NDCG@10.Results average three RankGPT reruns for baselines; PDG-F uses one deterministic ranking run.Source: §4.1 · pp. 5–6
- Table 1 reports the main comparison results, marking best values in bold and second-best values with underlining.For ties, only the last occurrence in each column is marked.Source: Table 1 · p. 6
4.2 Result Analysis
- PDG-F (+Year) leads all metrics on all three datasets; Movie gains over strongest baselines are 13.7% P@10, 14.1% R@10, and 19.6% NDCG@10.On Book, it improves P@10 by 92.4%; on Anime, it improves R@10 by 60.9% over the best competing methods.Source: §4.2 · p. 6
- The authors attribute some domain and model differences to temporal retrieval bias and knowledge coverage; (+Year) filtering helps on Movie, while retrieval is more valuable for newer or less-documented Book and Anime content.The rule-based year filter excludes candidates violating temporal constraints; gains on Anime are described as more limited.Source: §4.2 · p. 6
5 Ablation Study
The analysis compares PDG-F and OCG-Agent on candidate coverage, recall across recommendation lengths, and overlap among retrieved relevant items.
5.1.2 Recall across Recommendation Lengths.
- At Anime Recall@1, OCG-Agent scores 0.0492 versus 0.0359 for PDG-F with year, but PDG-F overtakes it as k reaches 10 and beyond.OCG-Agent plateaus around k=20 across datasets, while PDG-F with year continues surfacing relevant items through longer lists.Source: Figure 2 · p. 7, §5.1.2 · p. 7
5.1.1 Candidate Coverage.
- Pool recall rises from 0.2102 to 0.4858 on Movie, 0.2854 to 0.5481 on Book, and 0.1672 to 0.4734 on Anime.The reported increases establish a stronger candidate foundation for subsequent ranking.Source: Table 2 · p. 7, §5.1.1 · p. 7
5.1.3 Complementarity of Retrieved Items.
- PDG-F-only relevant items comprise 30.41%, 33.57%, and 38.85% on Movie, Book, and Anime, versus OCG-Agent-only shares of 2.86%, 7.29%, and 8.24%.Shares are computed per query and macro-averaged; OCG-Agent also retrieves some relevant items missed by PDG-F.Source: Figure 3 · p. 7, §5.1.3 · p. 7
5.2 Ranking Analysis
The ranking analysis examines node aggregation strategies, score discriminability, candidate-pool and ranking gaps, and dependency modeling.
5.2.1 Ranking Strategy Comparison.
- Full strategy scores are 0.4511 on Movie, 0.5101 on Book, and 0.3085 on Anime, with higher NDCG@10 than alternatives across all domains.The full additive strategy more than doubles performance on Book and Anime compared with the alternatives described.Source: Table 3 · p. 8, §5.2 · p. 8, §5.2.1 · p. 8
5.2.2 Graph Scores and Relevance.
- Top-decile relevance rates are 17.97% on Movie, 8.01% on Book, and 7.92% on Anime, versus 1.87%, 0.10%, and 0.18% in the respective bottom deciles.Relevant items concentrate in the top score decile across all three domains.Source: Figure 4 · p. 8, §5.2.2 · p. 8
5.2.3 Candidate Acquisition and Ranking Gaps.
- PDG-F achieves higher pool-oracle upper bounds than OCG-Agent across domains, but within-pool ranking remains the primary bottleneck.The decomposition is of the gap to ideal NDCG@10.Source: Figure 5 · p. 8, §5.2.3 · p. 8
5.2.4 Dependency Modeling Analysis.
- Without directed dependency edges, retrieval becomes uncoordinated across isolated preference nodes, and ranking reverts to prompting-based RankGPT reranking.Removing the graph also precludes topological path ranking.Source: §5.2.4 · p. 8
6 Conclusion
PDG-F models preference qualifications with directed acyclic graphs and carries them into candidate acquisition and evidence accumulation. Across three domains, it improves recommendation performance and relevant-item coverage, while oracle analysis identifies a remaining ranking gap.
6 Conclusion
- Across three domains, PDG-F improves recommendation performance over competitive baselines and broadens relevant-item coverage.Oracle analysis shows this broader coverage raises the attainable performance ceiling, while a remaining ranking gap points to the need for more accurate evidence scoring.Source: §6 · p. 8
- PDG-F represents how user preferences qualify one another with directed acyclic graphs.It carries these qualification relationships into candidate acquisition and topological evidence accumulation, connecting narrative understanding with evidence-based recommendation.Source: §6 · p. 8
- Oracle analysis finds a remaining ranking gap, motivating more accurate evidence scoring to realize the attainable performance ceiling.Source: §6 · p. 8