Tailoring Self-Attention for Graph via Rooted Subtrees

• URL: http://arxiv.org/abs/2310.05296v1
• Date: Sun, 8 Oct 2023 21:47:18 GMT
• Title: Tailoring Self-Attention for Graph via Rooted Subtrees
• Authors: Siyuan Huang, Yunchong Song, Jiayue Zhou, Zhouhan Lin
• Abstract summary: We propose a novel multi-hop graph attention mechanism, named Subtree Attention (STA) to address the aforementioned issues. By allowing direct computation of attention weights among multi-hop neighbors, STA mitigates the inherent problems in existing graph attention mechanisms. Our resulting GNN architecture, the STAGNN, presents a simple yet performant STA-based graph neural network.
• Score: 29.822899665579673
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Attention mechanisms have made significant strides in graph learning, yet they still exhibit notable limitations: local attention faces challenges in capturing long-range information due to the inherent problems of the message-passing scheme, while global attention cannot reflect the hierarchical neighborhood structure and fails to capture fine-grained local information. In this paper, we propose a novel multi-hop graph attention mechanism, named Subtree Attention (STA), to address the aforementioned issues. STA seamlessly bridges the fully-attentional structure and the rooted subtree, with theoretical proof that STA approximates the global attention under extreme settings. By allowing direct computation of attention weights among multi-hop neighbors, STA mitigates the inherent problems in existing graph attention mechanisms. Further we devise an efficient form for STA by employing kernelized softmax, which yields a linear time complexity. Our resulting GNN architecture, the STAGNN, presents a simple yet performant STA-based graph neural network leveraging a hop-aware attention strategy. Comprehensive evaluations on ten node classification datasets demonstrate that STA-based models outperform existing graph transformers and mainstream GNNs. The code is available at https://github.com/LUMIA-Group/SubTree-Attention.

Related papers

• Neural Graph Pattern Machine [50.78679002846741]
  We propose the Neural Graph Pattern Machine (GPM), a framework designed to learn directly from graph patterns. GPM efficiently extracts and encodes substructures while identifying the most relevant ones for downstream tasks.
  arXiv  Detail & Related papers  (2025-01-30T20:37:47Z)
• DeltaGNN: Graph Neural Network with Information Flow Control [5.563171090433323]
  Graph Neural Networks (GNNs) are designed to process graph-structured data through neighborhood aggregations in the message passing process. Message-passing enables GNNs to understand short-range spatial interactions, but also causes them to suffer from over-smoothing and over-squashing. We propose a mechanism called emph information flow control to address over-smoothing and over-squashing with linear computational overhead. We benchmark our model across 10 real-world datasets, including graphs with varying sizes, topologies, densities, and homophilic ratios, showing superior performance
  arXiv  Detail & Related papers  (2025-01-10T14:34:20Z)
• Understanding When and Why Graph Attention Mechanisms Work via Node Classification [8.098074314691125]
  We show that graph attention mechanisms can enhance classification performance when structure noise exceeds feature noise. We propose a novel multi-layer Graph Attention Network (GAT) architecture that significantly outperforms single-layer GATs in achieving emphperfect node classification.
  arXiv  Detail & Related papers  (2024-12-20T02:22:38Z)
• Learning to Model Graph Structural Information on MLPs via Graph Structure Self-Contrasting [50.181824673039436]
  We propose a Graph Structure Self-Contrasting (GSSC) framework that learns graph structural information without message passing. The proposed framework is based purely on Multi-Layer Perceptrons (MLPs), where the structural information is only implicitly incorporated as prior knowledge. It first applies structural sparsification to remove potentially uninformative or noisy edges in the neighborhood, and then performs structural self-contrasting in the sparsified neighborhood to learn robust node representations.
  arXiv  Detail & Related papers  (2024-09-09T12:56:02Z)
• Representation Learning on Heterophilic Graph with Directional Neighborhood Attention [8.493802098034255]
  Graph Attention Network (GAT) is one of the most popular Graph Neural Network (GNN) architecture. GAT lacks the ability to capture long-range and global graph information, leading to unsatisfactory performance on some datasets. We propose Directional Graph Attention Network (DGAT) to combine the feature-based attention with the global directional information extracted from the graph topology.
  arXiv  Detail & Related papers  (2024-03-03T10:59:16Z)
• Graph Transformers for Large Graphs [57.19338459218758]
  This work advances representation learning on single large-scale graphs with a focus on identifying model characteristics and critical design constraints. A key innovation of this work lies in the creation of a fast neighborhood sampling technique coupled with a local attention mechanism. We report a 3x speedup and 16.8% performance gain on ogbn-products and snap-patents, while we also scale LargeGT on ogbn-100M with a 5.9% performance improvement.
  arXiv  Detail & Related papers  (2023-12-18T11:19:23Z)
• Redundancy-Free Self-Supervised Relational Learning for Graph Clustering [13.176413653235311]
  We propose a novel self-supervised deep graph clustering method named Redundancy-Free Graph Clustering (R$2$FGC) It extracts the attribute- and structure-level relational information from both global and local views based on an autoencoder and a graph autoencoder. Our experiments are performed on widely used benchmark datasets to validate the superiority of our R$2$FGC over state-of-the-art baselines.
  arXiv  Detail & Related papers  (2023-09-09T06:18:50Z)
• Simple and Efficient Heterogeneous Graph Neural Network [55.56564522532328]
  Heterogeneous graph neural networks (HGNNs) have powerful capability to embed rich structural and semantic information of a heterogeneous graph into node representations. Existing HGNNs inherit many mechanisms from graph neural networks (GNNs) over homogeneous graphs, especially the attention mechanism and the multi-layer structure. This paper conducts an in-depth and detailed study of these mechanisms and proposes Simple and Efficient Heterogeneous Graph Neural Network (SeHGNN)
  arXiv  Detail & Related papers  (2022-07-06T10:01:46Z)
• Towards Unsupervised Deep Graph Structure Learning [67.58720734177325]
  We propose an unsupervised graph structure learning paradigm, where the learned graph topology is optimized by data itself without any external guidance. Specifically, we generate a learning target from the original data as an "anchor graph", and use a contrastive loss to maximize the agreement between the anchor graph and the learned graph.
  arXiv  Detail & Related papers  (2022-01-17T11:57:29Z)
• Hierarchical Message-Passing Graph Neural Networks [12.207978823927386]
  We propose a novel Hierarchical Message-passing Graph Neural Networks framework. Key idea is generating a hierarchical structure that re-organises all nodes in a flat graph into multi-level super graphs. We present the first model to implement this framework, termed Hierarchical Community-aware Graph Neural Network (HC-GNN)
  arXiv  Detail & Related papers  (2020-09-08T13:11:07Z)
• Structural Temporal Graph Neural Networks for Anomaly Detection in Dynamic Graphs [54.13919050090926]
  We propose an end-to-end structural temporal Graph Neural Network model for detecting anomalous edges in dynamic graphs. In particular, we first extract the $h$-hop enclosing subgraph centered on the target edge and propose the node labeling function to identify the role of each node in the subgraph. Based on the extracted features, we utilize Gated recurrent units (GRUs) to capture the temporal information for anomaly detection.
  arXiv  Detail & Related papers  (2020-05-15T09:17:08Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.