Modeling User Interfaces as Directed Graphs

34 concepts32 papers1 proposal

To an automated agent or testing script, a Graphical User Interface (GUI) can feel like a chaotic, non-linear maze. Unlike text or code, which flows sequentially, a GUI presents a visual canvas where actions—such as clicks, swipes, or text inputs—trigger state changes that completely alter the available options. If an autonomous system relies purely on step-by-step visual reasoning, it easily gets lost, hallucinates impossible actions, or fails to find deep, hidden screens.

The core insight uniting this body of research is that a user interface can be formally modeled as a directed graph. In this paradigm, each unique screen or interface state is represented as a node, and every valid user interaction is a directed edge connecting one state to another. By mapping a visual layout to a topological space, complex UI navigation, test automation, and bug verification are transformed into classic graph traversal and pathfinding problems.


Constructing the Map: Static and Dynamic Exploration

How do we build a graph of an application without manually mapping every screen? Researchers use two primary strategies: static analysis of the application's underlying code and dynamic exploration of the live interface.

Static Analysis

Static analysis looks under the hood to map out potential transitions before the app even runs. For instance, Wu et al. in Leaking the Privacy of Groups and More: Understanding Privacy Risks of Cross-App Content Sharing in Mobile Ecosystem construct activity transition graphs directly from application code to trace execution paths leading to specific UI components. Similarly, Hu et al. in Enhancing GUI Exploration Coverage of Android Apps with Deep Link-Integrated Monkey use static analysis of bytecode to build a topological roadmap, identifying deep-stack components that are hard to reach through normal usage.

Dynamic Analysis

Dynamic analysis, often called "GUI ripping" or crawling, maps the application by actively interacting with it. Tools systematically traverse the interface using heuristics like depth-first search (DFS) to record screenshots, component coordinates, and structural XML hierarchies, as demonstrated by Moran et al. in Auto-completing Bug Reports for Android Applications and Bernal-Cárdenas et al. in Guigle: A GUI Search Engine for Android Apps.

To prevent the graph from exploding with redundant nodes, Wu et al. in MobileVLM: A Vision-Language Model for Better Intra- and Inter-UI Understanding utilize a random walk algorithm paired with a uniqueness mechanism that filters out screens based on minor pixel or element differences.

[Screen A: Login] ----(Tap Login Button)----> [Screen B: Dashboard]
       |                                              |
(Tap Sign Up)                                  (Tap Settings)
       |                                              |
       v                                              v
[Screen C: Register]                         [Screen D: Settings Menu]

Why It Works: Topology Over Linear Sequences

Modern vision-language models (VLMs) and autonomous agents are powerful, but navigating a GUI purely through step-by-step visual processing is computationally expensive and error-prone. If an agent looks at a video sequence or a history of screenshots, it must infer the underlying rules of the application on the fly.

Modeling the UI as a directed graph changes the game in two fundamental ways:

  1. Reduced Computational Burden: Li et al. in GUI-Xplore: Empowering Generalizable GUI Agents with One Exploration show that a graph-based representation allows agents to perform complex reasoning over an app's topology without the heavy computational burden of processing linear video sequences.
  2. Eliminating Hallucinations: The graph acts as a physical constraint on behavior. Qin et al. in Executable Agentic Memory for GUI Agent represent the GUI as a formal state machine or knowledge graph. Because the agent can only choose actions that correspond to existing edges in the graph, it is structurally prevented from hallucinating or attempting impossible interactions.

Applications: Pathfinding, Verification, and Automation

Once an application is mapped as a graph, several complex software engineering challenges become straightforward pathfinding problems.

Validating Bug Reports

When a user submits a bug report, developers need the exact "Steps to Reproduce" (S2Rs). Often, users leave out critical steps. By treating the app as a directed graph, automated tools can act as a ground-truth validator.

Chaparro et al. in Assessing the Quality of the Steps to Reproduce in Bug Reports and Mahmud et al. in Combining Language and App UI Analysis for the Automated Assessment of Bug Reproduction Steps use these graph models to simulate and verify user-reported action sequences, identifying missing or ambiguous steps. Song et al. in Toward Interactive Bug Reporting for (Android App) End-Users even embed this graph into interactive chatbots to verify user descriptions in real-time.

Configuration-Independent Automation

Software layouts change across different devices, operating systems, or versions. Kushman in Enabling Configuration-Independent Automation by Non-Expert Users demonstrates that by representing UI structures as a global navigation graph, an automation system can dynamically calculate the shortest path to a target setting, adapting seamlessly to variations in menu layouts or organizational structures.

Systematic Testing over Stochastic Monkeys

Traditional automated testing relies on random event generation ("monkey testing"), which frequently gets trapped in circular navigation paths or tab-based layouts. Sun et al. in An Automatic UI Interaction Script Generator for Android Applications Using Activity Call Graph Analysis show that navigating via a structured graph of screen transitions ensures complete activity coverage in a fraction of the time by systematically targeting unvisited nodes.

Speculative Pre-rendering

The deterministic nature of a UI graph can even optimize network performance. Vankeirsbilck et al. in Round-trip time mitigation through speculative display updating for applications rendered in the cloud use directed graphs to accurately predict visual transitions based on user input. This allows cloud-rendered applications to pre-render the next likely interface state locally on the client side, effectively mitigating network latency.

Key Foundational Work

Toward automated exploration of interactive systems (2002) — contributed 2 concept elements to this direction.
Enabling Configuration-Independent Automation by Non-Expert Users (2010) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_graph_based_ui_navigation_ac40c2f2,
  title = {graph-based UI navigation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/graph-based-ui-navigation/rdr_ac40c2f205954d679e39a85a7118ae94},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_graph_based_ui_navigation_ac40c2f2_v1,
  title = {graph-based UI navigation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/graph-based-ui-navigation/rdr_ac40c2f205954d679e39a85a7118ae94/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake