TL;DR
This paper introduces the Deep Graph Attention Model (GAM), a novel recurrent neural network (RNN) that uses an attention mechanism to selectively focus on informative parts of a graph for classification. This approach tackles the computational and performance issues of traditional methods that process entire graphs, especially for large and noisy datasets.
What Problem Does This Paper Address?
Graph classification is a crucial task with applications ranging from drug discovery (predicting molecule properties) to social network analysis. Many existing methods, like graphlet-based approaches or graph kernels, require processing the entire graph to extract features. This becomes computationally expensive and can lead to performance degradation when the discriminative patterns are localized within small, noisy regions of a large graph. The paper aims to address this by developing a model that can intelligently focus on relevant parts of a graph, similar to how humans attend to specific details.
Methods
The core of the proposed method is a Graph Attention Model (GAM) built upon a Recurrent Neural Network (RNN), specifically a Long Short-Term Memory (LSTM) variant. The model operates by having an "agent" traverse the graph. At each step, a "step module" selects a neighboring node to visit, guided by a "rank vector" that prioritizes node types deemed more important. The attributes of the visited node and the current rank vector are used to generate a "step embedding," which is then fed into the LSTM's core network. The LSTM maintains a "history vector" that summarizes the information gathered so far.
This history vector is then used by two key components:
- Classification Network: Predicts the graph's label.
- Rank Network: Generates the rank vector for the next step, effectively steering the agent's exploration.
The agent's exploration is framed as a Partially Observable Markov Decision Process (POMDP), and the model is trained using a reinforcement learning approach (REINFORCE algorithm) to maximize the cumulative reward (correct classification). A variant, GAM-mem, is also introduced, which incorporates an external memory component to integrate information from multiple agents exploring different parts of the graph, enhancing its ability to capture global context.
Datasets
The paper evaluates its proposed methods on five molecular graph datasets for binary classification:
- HIV
- NCI-1
- NCI-33
- NCI-83
- NCI-123
These datasets represent molecules where nodes are atoms and edges are chemical bonds, and the labels indicate anti-cancer properties. The authors note that these datasets are imbalanced and they used balanced subsets of 500 randomly selected graphs for their experiments.
Key Insights and Ideas
- Attention for Graph Classification: The central idea is that not all parts of a graph are equally important for classification. By using an attention mechanism, the model can learn to focus on discriminative subgraphs, leading to more efficient and effective classification, especially in noisy or large graphs.
- Agent-Based Exploration: Framing graph traversal as a decision-making process for an agent provides a natural way to implement selective information gathering. The agent's "walk" through the graph is guided by learned policies.
- Reinforcement Learning for Graph Structure: Using RL to train the attention mechanism is a novel approach. The agent learns to explore the graph by maximizing a reward signal (correct classification), which implicitly teaches it to identify important structural patterns.
- External Memory for Global Context: The GAM-mem variant highlights the importance of integrating information from different parts of the graph. By using an external memory, the model can combine insights from multiple agents, mitigating the limitations of purely local exploration.
Key Results
- Competitive Performance: The GAM model consistently performs competitively with, and often outperforms, baseline methods that process the entire graph. GAM-mem, with its external memory, achieves the best performance on four out of the five tested datasets, often outperforming GAM itself.
- Efficiency Gains: The paper demonstrates that GAM can achieve strong results even when only observing a portion of the graph. When baselines are restricted to partial observations (mimicking GAM's setting), their performance significantly deteriorates, highlighting the effectiveness of GAM's attention mechanism. For example, Agg-WL's performance drops drastically, sometimes near random guessing.
- Space Complexity: The proposed GAM model has a favorable space complexity of O(△GD), where △ is the maximum node degree, G is the number of nodes, and D is the attribute dimension, making it suitable for large graphs.
Limitations and Future Work
- Partial Observability: The authors acknowledge that their model is at a disadvantage compared to baselines that observe the entire graph, as GAM only has partial observability.
- Node Typing: The paper mentions that more expressive node typing strategies could be explored.
- External Memory Refinements: Future work could involve more sophisticated external memory mechanisms, such as making the memory rewritable or conditioning the rank network's output on the memory.
- Flexible Architectures: The authors suggest exploring more flexible graph-native architectures like Tree-LSTMs.
- Random Attention Experiment: The paper uses random walks to restrict baselines to partial observations. While effective for demonstration, this is a simplified form of attention compared to GAM's learned mechanism.
Summary updated