Tangnn: A Concise, Scalable and Effective Graph Neural Networks with Top-M Attention Mechanism For Graph Representation Learning

E Jiawei, Yinglong Zhang, Xuewen Xia, Xing XuSSRN 2024 · DOI

TL;DR

This paper introduces TANGNN, a novel Graph Neural Network (GNN) architecture that combines a "Top-m attention mechanism" with traditional neighborhood aggregation. This approach aims to efficiently capture both local and long-range dependencies in graph data, addressing the scalability and computational challenges of existing Graph Transformer models. The authors also introduce ArXivNet, a new dataset for citation sentiment prediction, and demonstrate TANGNN's superior performance across various graph learning tasks.

What Problem Does This Paper Address?

Graph Neural Networks (GNNs) are powerful tools for analyzing structured data, but traditional GNNs struggle to effectively capture information from distant nodes, limiting their receptive field. Graph Transformers, on the other hand, excel at modeling long-range dependencies but suffer from high computational and storage costs, especially with large graphs. This paper tackles the challenge of creating a GNN that is both scalable and effective, capable of capturing both local and global graph information without the prohibitive overhead of Graph Transformers.

Methods

The core innovation of TANGNN lies in its dual-component aggregation strategy:

  • Top-m Attention Mechanism Aggregation: This component identifies the 'm' most relevant nodes to a central node based on cosine similarity with an auxiliary vector. This selective attention focuses on informative features, improving efficiency and performance. An auxiliary vector 'a' is introduced, which is orthogonal to node feature vectors, to indirectly estimate node similarity and reduce computational complexity from O(N²) to O(N).
  • Neighborhood Aggregation Component: This component performs traditional GNN aggregation, inspired by GraphSAGE, using random sampling of neighbors. This approach is efficient and helps maintain training speed.

These two components work in tandem at each layer, with their outputs concatenated and processed by a Multi-Layer Perceptron (MLP) to generate the node's representation for the next layer. This allows TANGNN to effectively integrate local and extended neighborhood information.

The paper also proposes several model variants and optimizations, including:

  • TANGNN-LC (Final Layer Concatenation): Concatenates outputs from all layers before the final MLP.
  • TANGNN-NAI (Neighborhood Aggregation As Input): Uses concatenated representations as input for the next layer's neighborhood aggregation.
  • TANGNN-TAI (Top-m Attention As Input): Uses concatenated representations as input for the next layer's Top-m attention aggregation.

Datasets

The authors evaluated TANGNN on several standard datasets for node classification, link prediction, and graph regression, including:

  • Cora
  • Citeseer
  • PubMed
  • Amazon
  • Reddit
  • ZINC
  • QM9

Additionally, they introduced ArXivNet, a new citation network dataset. ArXivNet was constructed by extracting papers from unarXive and building a citation network. This dataset is unique in that it not only includes document features but also annotates citation sentiments (positive, neutral, negative), making it suitable for citation sentiment prediction, a task previously unexplored in GNN research.

Key Insights and Ideas

  • Bridging the Gap: TANGNN successfully bridges the gap between traditional GNNs (limited receptive field) and Graph Transformers (high computational cost) by selectively attending to the most relevant nodes.
  • Auxiliary Vector for Efficiency: The introduction of an auxiliary vector 'a' for similarity calculation is a clever way to reduce the computational burden of finding top-m neighbors, making the model scalable to large graphs.
  • Citation Sentiment Prediction: Introducing citation sentiment prediction as a novel GNN task and creating the ArXivNet dataset opens up new avenues for research in understanding the nuances of academic discourse.
  • Layered Integration: The strategy of concatenating outputs from both aggregation components at each layer allows for a richer representation that captures information from different scales of the graph.

Key Results

  • Superior Performance: TANGNN-LC consistently outperformed baseline methods across various tasks, including vertex classification, link prediction, and sentiment prediction. For instance, on the Cora dataset, TANGNN-LC improved vertex classification accuracy by 12% compared to GraphSAGE.
  • Efficiency Gains: TANGNN demonstrated significantly faster convergence and lower training loss compared to GraphSAGE on the Cora dataset. It also showed competitive runtime performance on large graph datasets compared to other advanced models like TransGNN and NAGphormer.
  • Citation Sentiment Prediction: TANGNN-LC achieved superior performance on the ArXivNet dataset for citation sentiment prediction, outperforming other algorithms.
  • Parameter Sensitivity: The study found that TANGNN maintains stable performance across different values of 'm' (the number of top-m neighbors), suggesting robustness. A recommended value of m=30 was identified for balancing performance and computational cost.

Limitations and Future Work

  • Computational Burden of Top-m: While more efficient than full attention, the Top-m mechanism still involves similarity calculations. The paper suggests that further optimization of this process could be beneficial.
  • Dataset Specificity: The ArXivNet dataset, while novel, is specific to citation networks. Future work could explore its application to other domains or the creation of similar datasets for different graph types.
  • Oversmoothing: Although TANGNN aims to mitigate oversmoothing, it's a persistent challenge in GNNs. Further research into more robust solutions for oversmoothing in deep GNNs could be explored.
  • Model Variants: The paper introduces several variants (TANGNN-FLC, TANGNN-NAI, TANGNN-TAI) and notes their competitiveness. Further in-depth analysis and comparison of these variants could provide more insights.

Summary updated

BibTeX
@misc{jiawei2024tangnn,
  author = {E Jiawei and Yinglong Zhang and Xuewen Xia and Xing Xu},
  title = {{Tangnn: A Concise, Scalable and Effective Graph Neural Networks with Top-M Attention Mechanism For Graph Representation Learning}},
  year = {2024},
  doi = {10.2139/ssrn.4924674},
  howpublished = {SSRN},
}
Figure