Source-linked AI summary
Attention Models in Graphs: A Survey
John Boaz Lee, Ryan A. Rossi, Sungchul Kim, Nesreen K. Ahmed, Eunyee Koh
TL;DR
Graph mining must handle graphs that are large, complex, and noisy. This paper surveys graph attention models using three taxonomies covering problem setting, attention mechanism, and task. It also highlights challenges and directions for future work, while noting limitations in heterogeneous-graph handling and scalability.
Problem
Large, complex, and noisy real-world graphs create significant performance challenges for graph mining.
Method
The paper conducts a focused literature survey organized by problem setting, attention mechanism, and task, using examples to compare existing approaches.
Results
The survey provides three taxonomies for organizing graph attention models and uses them to examine competing approaches from distinct perspectives.
Takeaways & Limitations
The taxonomies provide a structured way to understand graph attention methods across graph types, attention strategies, and application tasks.
Takeaways & Limitations
Existing heterogeneous-graph methods do not generally distinguish both multiple link types and multiple node types, while scalability questions remain for large graphs and complex structures.
Abstract
from arXiv · showhide
Graph-structured data arise naturally in many different application domains. By representing data as graphs, we can capture entities (i.e., nodes) as well as their relationships (i.e., edges) with each other. Many useful insights can be derived from graph-structured data as demonstrated by an ever-growing body of work focused on graph mining. However, in the real-world, graphs can be both large - with many complex patterns - and noisy which can pose a problem for effective graph mining. An effective way to deal with this issue is to incorporate "attention" into graph mining solutions. An attention mechanism allows a method to focus on task-relevant parts of the graph, helping it to make better decisions. In this work, we conduct a comprehensive and focused survey of the literature on the emerging field of graph attention models. We introduce three intuitive taxonomies to group existing work. These are based on problem setting (type of input and output), the type of attention mechanism used, and the task (e.g., graph classification, link prediction, etc.). We motivate our taxonomies through detailed examples and use each to survey competing approaches from a unique standpoint. Finally, we highlight several challenges in the area and discuss promising directions for future work.
1 INTRODUCTION
Graph attention models address the difficulty of mining large, complex, and noisy graphs by focusing computation on task-relevant structure. This survey organizes the field through three taxonomies and identifies challenges and future directions.
- Motivation: Real-world graphs are structurally large, complex, and noisy, creating significant performance challenges for graph mining.Existing responses include multiple graph views, auxiliary non-graph data, and discriminative subgraph identification.
- Motivation: Attention helps graph models focus on relevant input parts, ignore noisy structure, assign relevance scores, and improve interpretability.Attention weights can highlight task-relevant neighbors or other graph components, including factors associated with medical conditions.
- Survey framework: The survey introduces taxonomies based on problem setting, attention mechanism, and task, including input and output types and applications such as node or graph classification.The taxonomies are motivated with examples and used to survey competing approaches from distinct perspectives.
- Survey framework: The problem-setting taxonomy covers graph types, properties, and embedding outputs, while the task taxonomy groups methods by application area.The survey considers node, edge, graph, and hybrid embeddings and organizes methods by supported graph types.
- Challenges and scope: The article highlights unresolved challenges in graph attention and discusses promising directions for future research.Its scope centers on methods that explicitly apply attention to graphs, rather than the broader field of graph-based methods without attention.
2 PROBLEM FORMULATION
This section establishes graph notation and defines graph attention as relevance scoring over a target object's task-specific neighborhood. It also distinguishes graph classes by node and edge types, attributes, direction, weights, and cycles.
- A graph is represented by nodes and edges, with adjacency matrices encoding connectivity and optionally edge weights or direction.
- Heterogeneous graphs assign types to nodes and edges, while homogeneous graphs are the special case with one node type and one edge type.
- Attributed graphs augment nodes or edges with input-attribute matrices, whose values may be real-valued or non-real-valued.
- The survey also distinguishes directed acyclic graphs and paths, with paths defined as sequences of unique adjacent nodes and length equal to their number of edges.
- Graph attention maps each object in a target's task-specific neighborhood to a relevance score indicating how much attention it receives.
3 ATTENTION-BASED NODE/EDGE EMBEDDING
This section surveys attention-based node and edge embeddings across graph types and embedding strategies. The methods use attention to weight neighborhood, path, or relation information, while coverage remains limited for some specialized heterogeneous settings.
- Node and edge embedding: Node embedding maps each graph node to a lower-dimensional vector that can support link prediction, classification, community detection, and role discovery.
- Node and edge embedding: Attention-based node embedding additionally learns neighbor weights so more similar or important neighbors receive greater relative influence.
- Homogeneous graph: AttentionWalks uses learnable weights over random-walk context lengths to broaden or narrow the neighborhood without grid-searching the context-window size.
- Homogeneous graph: GCN extensions such as GAT and AGNN replace degree-normalized neighbor aggregation with explicit attention weights, while multi-attention uses multiple heads between graph objects.
- Homogeneous graph: PRML uses attention first to identify important nodes along paths and then to prioritize paths indicative of link formation.
- Heterogeneous graph: EAGCN applies relation-specific multi-attention in heterogeneous graphs, but the surveyed heterogeneous-network methods assume only one node type.
- Other special cases: The survey reports no attention-guided node-embedding work for certain specialized graph types, although general-graph methods should be applicable to them.
4 ATTENTION-BASED GRAPH EMBEDDING
Attention-based graph embedding methods learn graph representations while prioritizing relevant subgraphs, nodes, or sequence positions. The surveyed approaches span homogeneous graphs, recurrent walks, and sequence-like graph inputs.
- Graph embedding maps each input graph to a low-dimensional vector that groups similar graphs together.
- Attention-based graph embedding adds a second function that assigns weights to subgraphs so important regions receive priority during embedding.
- Homogeneous graph: Ryu et al. adapt GAT attention for molecular graph regression, while graph2seq builds embeddings from attributed directed graphs for sequence generation.
- Homogeneous graph: GAM uses attention-guided walks and a second attention mechanism to combine multiple sampled subgraph embeddings into one graph embedding.
- Other special cases: For long paths, Luong et al. use a local attention window around a selected position rather than attending uniformly over every hidden embedding.
5 ATTENTION-BASED HYBRID EMBEDDING
Hybrid graph-attention methods combine graph information with other modalities or structured medical knowledge. They apply attention to subgraphs, triplets, text-linked graph components, or ontology ancestors for prediction and generation.
- Hybrid embeddings combine graph data with other modalities, such as text, rather than using graph input alone.
- CCM learns component embeddings from knowledge-graph triplets and attends to selected subgraphs and triplets during sequence decoding.
- JointD/E + SATT learns a joint embedding from a knowledge graph and text corpus for knowledge-graph link prediction.
- Brain-network settings can involve datasets that are small and noisy, motivating side information for highlighting discriminative graph patterns.
- Existing knowledge-graph attention models do not explicitly distinguish different node and link types, leaving more general heterogeneous graphs insufficiently addressed.
- GRAM applies attention over a medical-concept DAG so leaf-code embeddings can use more informative ancestors for diagnosis.
6 TYPES OF GRAPH ATTENTION MECHANISM
The survey groups graph attention into three mechanisms: relevance-based attention, similarity-based attention, and attention that ranks information gathered during graph walks. These mechanisms differ in how relevance is computed and used.
- Graph attention assigns relevance scores to neighborhood objects relative to a target graph object.
- Relevance-based attention: Relevance-based attention learns neighbor weights from target and neighbor attributes, commonly using a trainable function and softmax.
- Similarity-based attention: Similarity-based attention gives greater weight to objects with similar hidden representations or features, often using alignment or cosine similarity.
- Walk-based attention: GAM uses a walk RNN hidden state to rank candidate next nodes, steering subsequent steps toward relevant graph regions.
7 GRAPH ATTENTION TASKS
Graph-attention methods are organized by task level and output type. They support node-level prediction, graph-level classification or regression, sequence generation, and medical-code classification.
- Node-level tasks: Node-level methods learn attention-guided node or edge embeddings for tasks such as node classification and link prediction.
- Graph-level tasks: Graph-level methods construct attention-guided graph embeddings for graph classification, regression, and related similarity search.
- Sequence generation: Other methods generate sequences from graph data, including graph2seq, which outputs a sequence from an input graph.
- Medical applications: GRAM applies attention to a medical ontology graph to learn embeddings for medical codes used in patient-record classification.
8 DISCUSSION AND CHALLENGES
The discussion identifies unresolved challenges for graph attention models involving heterogeneous graphs, scalability, inductive learning, and walk-based representations. It also outlines directions for broader graph settings, larger datasets, and more generalizable patterns.
- 8.1 Attention-based methods for heterogeneous graphs: Existing attention methods for heterogeneous graphs often do not distinguish among different node and link types.Some methods handle multiple link types, while others prioritize nodes by type without covering the general heterogeneous case.
- 8.1 Attention-based methods for heterogeneous graphs: Future methods should address general heterogeneous networks and account for how different meta-paths affect learned embeddings.The survey notes that heterogeneous-graph methods can outperform approaches assuming a single edge type.
- 8.2 Scalability of graph attention models: Many attention-based graph-embedding methods target relatively small graphs and may not scale effectively to larger graphs.Methods designed for larger graphs still raise questions about walk length, recurrent processing, and whether walks capture complex relevant structures.
- 8.2 Scalability of graph attention models: Attention applied to graph convolutional architectures offers an attention-based, end-to-end differentiable version of the Weisfeiler-Lehman algorithm, but requires evaluation on large real-world graphs.The survey presents this as a promising direction while emphasizing the need for broader testing.
- 8.3 Inductive learning: Attention-based inductive learning could identify graph patterns that generalize across datasets and support cross-domain or heterogeneous transfer learning.More focused experiments are needed across larger sets of datasets and settings.
- 8.4 Attributed walks: Attention-based random-walk methods may benefit from attributed walks, which represent node-type sequences rather than node identities.Traditional random-walk models are recovered as a special case when the number of unique types approaches the number of nodes.
9 CONCLUSION
The survey organizes graph attention research through three taxonomies covering problem setting, attention mechanism, and task. It also identifies challenges and discusses possible directions for future work.
- 9 CONCLUSION: The paper presents a comprehensive and focused survey of graph attention models.The authors describe it as the first work of this kind.
- 9 CONCLUSION: Three taxonomies group existing work by problem setting, attention mechanism, and task, with detailed examples motivating each perspective.Each taxonomy is used to survey competing approaches from its own standpoint.
- 9 CONCLUSION: The survey highlights several challenges in graph attention and discusses possible directions for future work.