Visual storytelling systems turn a photo sequence into a short story. The more coherent ones first build a plan: they link what is in the pictures to a commonsense knowledge graph, a large network of facts such as "someone at a party wants to relax," and then pick a chain of linked facts for the story to follow. The difficulty is that such graphs contain many kinds of links, so the number of possible chains grows exponentially with chain length. Current systems cope in one of two ways. They stop after one or two hops, or they build a tiny graph that can be searched exhaustively. Either way, the planner cannot reach the deeper causal and social connections that hold a story together across images, and it has no principled way to tell which distant facts are still supported by the pictures.
We propose to make the images control the search itself. At each hop, a small cross-attention module reads the image features together with the current partial plan and decides which types of relation are worth expanding, for example "what the person wants next" versus "where this object is found." Only those relation types are expanded. The expensive step, enumerating every chain, is replaced by a learned, picture-conditioned choice over the graph's schema. The result is a plan that can go three or four hops deep at roughly constant cost per hop. Our central bet is that this beats the obvious cheap alternative, which is to enumerate candidates and filter them by image-text similarity. That filter tends to discard exactly the abstract social inferences, such as wants, needs, and intentions, that cannot be seen in a photo but that make stories coherent.
Core Claim
Gating relation types with cross-modal attention, applied before expansion and trained from story-level supervision, lets a visual story planner search commonsense paths of depth 3 to 4. It keeps more useful abstract inferences than similarity-based pruning and hallucinates fewer unsupported facts than fixed-depth enumeration. Concretely, at hop $t$ and for each relation type $r$ in the graph schema, the planner computes
$$g_{t,r} = \sigma\!\left(w_r^\top\, \mathrm{CrossAttn}(q = h_t,\; K, V = X)\right),$$
where $h_t$ is the encoded partial plan, $X$ are image patch features for the frames, $w_r$ is a learned vector per relation type, and $\sigma$ is the logistic function. Only the top-$k$ relation types by $g_{t,r}$ are expanded, and a beam of width $B$ is kept over the resulting chains. Search cost then falls from the $O(b^L)$ growth documented for schema-rich graphs (Xiong et al., Ma et al.), with $b$ the branching factor and $L$ the depth, to $O(L\,B\,k\,d)$. Here $d$ is the mean fan-out per relation type. The bound follows because each hop expands at most $B$ beams times $k$ relation types.
How This Differs From What Exists
Two visual storytelling systems motivate the proposal by showing that graph plans help and that they are depth-limited. SCO-VIST builds a story graph from image captions and ATOMIC social inferences, refines edge weights with a temporal graph network, and extracts a story spine with Floyd-Warshall shortest paths. It reports a UNION coherence score of 87.0. Its graph is kept small enough for cubic-time search, and its captioning stage is a hard cascade, so the images never influence which knowledge is retrieved. KG-Story reduces images to words, enumerates 1- or 2-hop paths from external graphs, and scores them with a language model. Its authors report that deeper paths hallucinate content that diverges from the pictures. We keep these systems' plan-then-write structure. What we change is where the visual evidence enters: inside the expansion step, rather than before the search (SCO-VIST) or after it (KG-Story).
Three lines of graph-learning work supply the method and its constraints. CP-GNN learns over automatically discovered paths of length at most 4, with attention over relation types and path lengths, on graphs with 104 edge types. Our gate is close to its relation-wise attention. The difference is that ours is conditioned on images and used to prune at inference time, not to weight an already-enumerated set. HetaFlow avoids path enumeration by processing each edge type as a parallel stream. We borrow that per-relation-type organization so that relation-type gating maps cleanly onto the computation. GraphHAM embeds branching structure in hyperbolic space. We deliberately leave geometry out: the question here is pruning by evidence, and adding hyperbolic embeddings would blur which ingredient matters. All three were evaluated only on node classification or clustering, never on generation.
The cross-modal attention literature constrains the gate's design. Gated cross-attention for drug-target interaction shows that unconstrained cross-attention lets the denser input wash out the sparser one, and that a learned mixing gate fixes this, reducing Davis MSE from 0.438 to 0.393. In our setting, dense image patches play the "large" role and the sparse plan state plays the "small" one. We therefore use the same residual gate so that the plan representation is not overwritten. The dual-stream graph–vision fusion study supports fusing a graph stream with a pixel stream rather than cascading them.
Research Program
The graph is the union of ATOMIC-style social inferences, as used by SCO-VIST, and ConceptNet-style physical relations, as used by KG-Story. It is anchored to each frame through detected objects and captions. The planner is trained with silver supervision. For each VIST training story, we align sentences to graph nodes using string match plus an entailment filter, and we treat chains connecting aligned nodes across consecutive frames as target paths. The gate is trained to keep the relation types that appear on target paths. A second stage fine-tunes the gate through a coherence reward on the realized story, using UNION as a training-time proxy that is held out from final reporting in favor of human judgments.
The surface realizer is the same BART-size decoder for every system, conditioned on the linearized plan, so that only the planner varies. We will also analyze which relation types the gate opens for which visual contexts. That analysis tests whether the model has learned something interpretable, such as opening "wants" edges for people-centric frames, or is only exploiting a dataset prior.
Baselines
The naive reference point is a plain vision-language decoder that writes the story directly from frame features with no plan. It is the AREL/GLACNet family as reported through SCO-VIST, where GLACNet scores 75.9 UNION. We will rerun it with our decoder for parity.
The strongest existing method is SCO-VIST. It reports UNION 87.0, ahead of GLACNet at 75.9 and KG-Story at 65.8, and humans preferred it over AREL 93.4% of the time. We will reproduce its pipeline on our merged graph with our decoder. Beating it means a higher UNION score and a significant human pairwise preference on coherence, with grounding precision at least equal.
KG-Story is the depth-limited enumeration baseline. It reports CIDEr 0.096 and a human rank of 2.975. We run it at 2 hops, as published, and at 3 hops wherever enumeration fits in memory, with the same LM scorer budget as our planner.
The baseline we consider most dangerous is per-hop CLIP beam search. It uses exactly our beam and expansion procedure, but replaces the learned gate with the image-text similarity between each candidate node and the frames. This baseline isolates the key ingredient, a learned relation-type gate versus a hand-free similarity score. It gets the same $B$, $k$, and node budget and needs no training.
Two ablations complete the set. One removes the residual mixing term from the gate, which tests modality dominance. The other gates individual nodes instead of relation types, which tests whether schema-level decisions are what make pruning cheap and robust.
Visual Storytelling with Question-Answer Plans is the graph-free planning competitor. It has no reported result on Lacuna for VIST, so we will run it with the same backbone budget.
All systems share data splits, decoder, and a matched hyperparameter search of equal trial count, and they are compared at equal nodes expanded per story.
Why not just…?
Why not just prompt a large vision-language model to write an outline and then the story? This is a real threat on 5-image VIST, where context length is not binding. Evidence from long-form text, namely Re3's 14% gain from structured plans over rolling-context generation and Captain Cinema's report that baselines degrade after 16 interleaved pairs, suggests unstructured planning drifts as sequences lengthen. We will include a prompted outline-then-write baseline on the same backbone. We will report results on standard VIST and on longer 10–20-frame sequences built from VIST albums. If the prompted baseline matches us on both, the graph is not earning its cost, and we will say so.
Why not just enumerate 2-hop paths and rerank, as KG-Story does? At 2 hops, enumeration is cheap. Our claim is limited to the regime where the useful link between two frames needs three or more hops. The decisive measurement is how plan quality and grounding change as depth goes from 2 to 4 under a fixed compute budget. If depth beyond 2 adds nothing to human coherence ratings, the premise fails.
Why not just filter candidate nodes by CLIP similarity at each hop? This is the cheapest version of our idea, and it may simply work. Our reason to expect it to fall short is specific: abstract inferences like "wants to relax" have weak visual similarity to any photo, yet they are what SCO-VIST's social graph contributes. We will measure the fraction of social-inference nodes retained in plans under each method, alongside coherence. If CLIP-beam keeps them equally well and scores equally, the learned gate is unnecessary.
Proposed Experiments
The main evaluation is VIST (Visual Storytelling), using METEOR, which that paper found correlates best with human judgment (r ≈ 0.22), along with CIDEr, UNION, and pairwise human ratings of coherence and grounding. Grounding precision is the fraction of plan facts that annotators mark as supported by the images.
The scaling experiment uses longer album sequences of 10 and 20 frames. No reported result was found on Lacuna for any system at these lengths, so all systems are run by us.
The first decisive check measures search recall on small graphs, where exhaustive enumeration at depth 3 is still feasible: how often does the gated search recover the best-scoring exhaustive path, compared with CLIP-beam at equal nodes expanded?
The second decisive check is the cost curve. We plot memory and wall-clock per story against depth 2 to 4 for exhaustive search, KG-Story enumeration, and our planner. If the proposal is right, these should show near-linear growth for ours and exponential growth for enumeration.
The third decisive check is the social-inference retention comparison against CLIP-beam described above. It is the experiment most likely to falsify the specific contribution.
References
- Heterogeneous network embedding enabling accurate disease association predictions
- Predicting Drug Repurposing Candidates and Their Mechanisms from A Biomedical Knowledge Graph
- SCO-VIST: Social Interaction Commonsense Knowledge-based Visual Storytelling
- Knowledge-Enriched Visual Storytelling
- Detecting Communities from Heterogeneous Graphs: A Context Path-based Graph Neural Network Model
- Heterogeneous graph adaptive flow network
- An Efficient Automatic Meta-Path Selection for Social Event Detection via Hyperbolic Space
- An Interpretable Framework for Drug-Target Interaction with Gated Cross Attention
- How GNNs Facilitate CNNs in Mining Geometric Information from Large-Scale Medical Images
- Visual Storytelling with Question-Answer Plans
- Re3: Generating Longer Stories With Recursive Reprompting and Revision
- Captain Cinema: Towards Short Movie Generation
- Visual Storytelling