At its core, the self-attention mechanism computes a pairwise affinity matrix $A \in \mathbb{R}^{N \times N}$ for a sequence of $N$ tokens. In standard explanations, this matrix is viewed as a set of dynamic weights used to compute a linear combination of value vectors. However, there is an alternative, deeply intuitive perspective: the attention matrix is a weighted adjacency matrix of a fully connected, directed graph where tokens act as nodes.
By treating attention maps as graphs, we can move past treating Transformers as black-box vector processors. Instead, we can apply decades of graph theory, network flow algorithms, and spectral analysis to understand how information propagates, identify key tokens, and diagnose model behaviors.
Token Importance via Graph Centrality
In a single attention layer, a token might receive high attention weights from its immediate neighbors. But does that make it globally important to the sequence?
If we view the attention matrix as a directed graph, we can use centrality metrics to measure global token salience. For instance, Xu et al. demonstrate that indegree centrality—simply summing how much all other tokens attend to a specific word—acts as an effective, unsupervised proxy for semantic importance, which they use to guide abstractive summarization copy mechanisms.
To capture more complex, multi-hop dependencies, we can treat the attention graph as a Markov chain and run ranking algorithms like PageRank. In this view, a token is important if it is attended to by other important tokens. Pang et al. leverage this via their Match-Ignition framework to filter out noisy sentences in long-form text matching.
Similarly, Wang et al. utilize a weighted PageRank algorithm on Vision Transformer attention graphs to identify and prune redundant tokens without any fine-tuning. This same graph-based ranking intuition is extended to diffusion models by the authors of Attention-Driven Training-Free Efficiency Enhancement of Diffusion Models, where low-centrality tokens are pruned to accelerate inference.
Information Flow and Random Walks
When a Transformer has multiple layers, tracking information becomes harder. Raw attention weights in layer $L$ only tell us how embeddings at layer $L-1$ are mixed, but those embeddings already contain mixed information from earlier layers.
To solve this, we can construct a Directed Acyclic Graph (DAG) where nodes represent tokens at specific layers, and edges represent attention weights between layers. Abnar et al. formalized this with Attention Rollout and Attention Flow, treating the Transformer as a flow network to trace how information actually propagates from input tokens to final representations. This network flow framing is generalized across decoders and encoder-decoders by the authors of Attention Flows for General Transformers to compute exact token influences, and applied by Brandl et al. to analyze how language models resolve gender-neutral pronouns.
This multi-layer propagation has a beautiful mathematical equivalent: random walks. Wang proves that information transfer through multiple layers of self-attention is mathematically equivalent to a reversed random walk on the underlying attention graph. This equivalence allows researchers to use structural graph properties like diameter and degree to analyze and bound the representational capacity of sparse attention architectures, such as the Hypercube Transformer. For security and alignment, Dong et al. exploit this token-layer graph routing to detect jailbreak attacks by identifying anomalous information routing signatures across the model's depth.
The Equivalence to Graph Convolutional Networks
The connection between attention and graphs is not just an analogy; it is a formal mathematical equivalence. A standard Transformer layer computes:
$$\text{Attention}(Q, K, V) = \text{Softmax}\left(\frac{QK^T}{\sqrt{d_k}}\right)V$$
If we define $A = \text{Softmax}(QK^T / \sqrt{d_k})$, then the layer simply computes $AV$, which is exactly the message-passing step of a Graph Convolutional Network (GCN) operating on a fully connected graph with a dynamic adjacency matrix $A$.
Zhang et al. explicitly unveil this graph convolutional nature in their Fighter architecture, showing that treating the attention matrix as a dynamic adjacency matrix allows for multi-hop graph aggregation that dramatically reduces forecasting errors in time series. Viewing attention as a graph convolution also opens up new optimization paradigms: Miao et al. introduce Coeff-Tuning, which treats multi-head attention as a subspace of graph filters, allowing efficient fine-tuning by mixing heads as signal processing operations. Conversely, Jiang et al. use custom attention masks to force the Transformer to emulate a graph neural network directly, processing structural data without external graph encoders.
Furthermore, this GCN perspective helps diagnose structural failures. Shi et al. analyze the "over-smoothing" problem in deep BERT models—where token representations converge and become identical—by modeling the self-attention mechanism as a normalized adjacency matrix and applying graph signal processing theory to design hierarchical fusion strategies. To combat these limitations and capture higher-order statistics, Zhou et al. propose Jump Self-attention (JAT), which applies a spectral convolutional operator directly to the attention adjacency matrix to redistribute attention weights and strengthen indirect, multi-hop token connections.
Macroscopic Topology and Spectral Signatures
Instead of looking at individual nodes or paths, we can analyze the global geometric and algebraic properties of the attention graph to evaluate high-level text characteristics.
One powerful tool for this is Topological Data Analysis (TDA), which studies the "shape" of data across different connectivity thresholds. Kushnareva et al. model attention maps as weighted bipartite graphs and use TDA to extract structural fingerprints that accurately distinguish human text from AI-generated text. This topological approach is extended by Cherniavskii et al. to evaluate grammatical acceptability judgments, and by Jain et al. to quantify document coherence based on the topological signatures of attention graphs.
Alternatively, we can look at the graph's spectrum (the eigenvalues of its adjacency or Laplacian matrix). NOËL demonstrates that valid mathematical reasoning leaves a distinct spectral signature within the self-attention matrix, allowing the model to separate genuine logical coherence from superficial pattern matching.
Finally, graph-theoretic structures can expose latent semantic subgraphs. Choudhury uses community detection algorithms on attention bipartite graphs to perform unsupervised text span extraction, grouping interacting tokens into coherent units. For complex downstream tasks, Huber et al. treat self-attention matrices directly as adjacency matrices to parse document-level discourse trees, while Frasca et al. build fully attributed attention graphs (combining residual stream activations and multi-layer attention weights) and train Graph Neural Networks on top of them to detect model hallucinations.
Key Foundational Work
Self-Attention Guided Copy Mechanism for Abstractive Summarization (2020) — contributed 3 concept elements to this direction.
Artificial Text Detection via Examining the Topology of Attention Maps (2021) — contributed 1 concept elements to this direction.
Quantifying Attention Flow in Transformers (2020) — contributed 1 concept elements to this direction.