Tokenphormer: Structure-aware Multi-token Graph Transformer for Node Classification

• URL: http://arxiv.org/abs/2412.15302v1
• Date: Thu, 19 Dec 2024 10:44:18 GMT
• Title: Tokenphormer: Structure-aware Multi-token Graph Transformer for Node Classification
• Authors: Zijie Zhou, Zhaoqi Lu, Xuekai Wei, Rongqin Chen, Shenghui Zhang, Pak Lon Ip, Leong Hou U,
• Abstract summary: We propose the Structure-aware Multi-token Graph Transformer (Tokenphormer) It generates multiple tokens to capture local and structural information and explore global information at different levels of granularity. Experimental results demonstrate that the capability of the proposed Tokenphormer can achieve state-of-the-art performance on node classification tasks.
• Score: 9.967313792318606
• License:
• Abstract: Graph Neural Networks (GNNs) are widely used in graph data mining tasks. Traditional GNNs follow a message passing scheme that can effectively utilize local and structural information. However, the phenomena of over-smoothing and over-squashing limit the receptive field in message passing processes. Graph Transformers were introduced to address these issues, achieving a global receptive field but suffering from the noise of irrelevant nodes and loss of structural information. Therefore, drawing inspiration from fine-grained token-based representation learning in Natural Language Processing (NLP), we propose the Structure-aware Multi-token Graph Transformer (Tokenphormer), which generates multiple tokens to effectively capture local and structural information and explore global information at different levels of granularity. Specifically, we first introduce the walk-token generated by mixed walks consisting of four walk types to explore the graph and capture structure and contextual information flexibly. To ensure local and global information coverage, we also introduce the SGPM-token (obtained through the Self-supervised Graph Pre-train Model, SGPM) and the hop-token, extending the length and density limit of the walk-token, respectively. Finally, these expressive tokens are fed into the Transformer model to learn node representations collaboratively. Experimental results demonstrate that the capability of the proposed Tokenphormer can achieve state-of-the-art performance on node classification tasks.

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)
• 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)
• A Pure Transformer Pretraining Framework on Text-attributed Graphs [50.833130854272774]
  We introduce a feature-centric pretraining perspective by treating graph structure as a prior. Our framework, Graph Sequence Pretraining with Transformer (GSPT), samples node contexts through random walks. GSPT can be easily adapted to both node classification and link prediction, demonstrating promising empirical success on various datasets.
  arXiv  Detail & Related papers  (2024-06-19T22:30:08Z)
• VCR-Graphormer: A Mini-batch Graph Transformer via Virtual Connections [45.27160435758666]
  We show that mini-batch training of graph transformers is possible by loading each node's token list in batches. We further prove this PPR tokenization is viable as a graph convolution network with a fixed filter and jumping knowledge.
  arXiv  Detail & Related papers  (2024-03-24T06:10:56Z)
• GGNNs : Generalizing GNNs using Residual Connections and Weighted Message Passing [0.0]
  GNNs excel at capturing relationships and patterns within graphs, enabling effective learning and prediction tasks. It is commonly believed that the generalizing power of GNNs is attributed to the message-passing mechanism between layers. Our technique builds on these results, modifying the message-passing mechanism further: one by weighing the messages before accumulating at each node and another by adding Residual connections.
  arXiv  Detail & Related papers  (2023-11-26T22:22:38Z)
• SGFormer: Simplifying and Empowering Transformers for Large-Graph Representations [75.71298846760303]
  We show that a one-layer attention can bring up surprisingly competitive performance across node property prediction benchmarks. We frame the proposed scheme as Simplified Graph Transformers (SGFormer), which is empowered by a simple attention model. We believe the proposed methodology alone enlightens a new technical path of independent interest for building Transformers on large graphs.
  arXiv  Detail & Related papers  (2023-06-19T08:03:25Z)
• Tokenized Graph Transformer with Neighborhood Augmentation for Node Classification in Large Graphs [11.868008619702277]
  We propose a Neighborhood Aggregation Graph Transformer (NAGphormer) that treats each node as a sequence containing a series of tokens. Hop2Token aggregates the neighborhood features from different hops into different representations, producing a sequence of token vectors as one input. In addition, we propose a new data augmentation method called Neighborhood Augmentation (NrAug) based on the output of Hop2Token.
  arXiv  Detail & Related papers  (2023-05-22T03:29:42Z)
• Dynamic Graph Message Passing Networks for Visual Recognition [112.49513303433606]
  Modelling long-range dependencies is critical for scene understanding tasks in computer vision. A fully-connected graph is beneficial for such modelling, but its computational overhead is prohibitive. We propose a dynamic graph message passing network, that significantly reduces the computational complexity.
  arXiv  Detail & Related papers  (2022-09-20T14:41:37Z)
• Graph Ordering Attention Networks [22.468776559433614]
  Graph Neural Networks (GNNs) have been successfully used in many problems involving graph-structured data. We introduce the Graph Ordering Attention (GOAT) layer, a novel GNN component that captures interactions between nodes in a neighborhood. GOAT layer demonstrates its increased performance in modeling graph metrics that capture complex information.
  arXiv  Detail & Related papers  (2022-04-11T18:13:19Z)
• Local Augmentation for Graph Neural Networks [78.48812244668017]
  We introduce the local augmentation, which enhances node features by its local subgraph structures. Based on the local augmentation, we further design a novel framework: LA-GNN, which can apply to any GNN models in a plug-and-play manner.
  arXiv  Detail & Related papers  (2021-09-08T18:10:08Z)
• Locality Preserving Dense Graph Convolutional Networks with Graph Context-Aware Node Representations [19.623379678611744]
  Graph convolutional networks (GCNs) have been widely used for representation learning on graph data. In many graph classification applications, GCN-based approaches have outperformed traditional methods. We propose a locality-preserving dense GCN with graph context-aware node representations.
  arXiv  Detail & Related papers  (2020-10-12T02:12:27Z)

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.