DARTS-GT: Differentiable Architecture Search for Graph Transformers with Quantifiable Instance-Specific Interpretability Analysis

• URL: http://arxiv.org/abs/2510.14336v2
• Date: Thu, 30 Oct 2025 21:46:00 GMT
• Title: DARTS-GT: Differentiable Architecture Search for Graph Transformers with Quantifiable Instance-Specific Interpretability Analysis
• Abstract summary: Graph Transformers (GTs) have emerged as powerful architectures for graph-structured data, yet remain constrained by rigid designs and lack quantifiable interpretability.<n>We develop the first quantitative interpretability framework for GTs through causal ablation.<n>Experiments show DARTS-GT achieves state-of-the-art redesigns on four datasets while remaining competitive on others.<n>Our interpretability analysis reveals that visual attention salience and causal importance do not always correlate, indicating widely used visualization approaches may miss components that actually matter.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph Transformers (GTs) have emerged as powerful architectures for graph-structured data, yet remain constrained by rigid designs and lack quantifiable interpretability. Current state-of-the-art GTs commit to fixed GNN types across all layers, missing potential benefits of depth-specific component selection, while their complex architectures become opaque where performance gains cannot be distinguished between meaningful patterns and spurious correlations. We redesign GT attention through asymmetry, decoupling structural encoding from feature representation: queries derive from node features while keys and values come from GNN transformations. Within this framework, we use Differentiable ARchiTecture Search (DARTS) to select optimal GNN operators at each layer, enabling depth-wise heterogeneity inside transformer attention itself (DARTS-GT). To understand discovered architectures, we develop the first quantitative interpretability framework for GTs through causal ablation. Our metrics (Head-deviation, Specialization, and Focus), identify which heads and nodes drive predictions while enabling model comparison. Experiments across eight benchmarks show DARTS-GT achieves state-of-the-art on four datasets while remaining competitive on others, with discovered architectures revealing dataset-specific patterns. Our interpretability analysis reveals that visual attention salience and causal importance do not always correlate, indicating widely used visualization approaches may miss components that actually matter. Crucially, heterogeneous architectures found by DARTS-GT consistently produced more interpretable models than baselines, establishing that Graph Transformers need not choose between performance and interpretability.

Related papers

• Invariant-Based Diagnostics for Graph Benchmarks [16.239542747309727]
  We propose graph invariants as a diagnostic framework for graph benchmarks.<n>We show that (i) invariants are more expressive than standard GNNs, (ii) invariants characterize structural heterogeneity within and across benchmark datasets, (iii) invariants predict multi-task performance, and (iv) simple invariant-based models are competitive with, and sometimes exceed, transformer and message-passing baselines.
  arXiv  Detail & Related papers  (2026-05-07T15:51:43Z)
• Plain Transformers are Surprisingly Powerful Link Predictors [57.01966734467712]
  Link prediction is a core challenge in graph machine learning, demanding models that capture rich and complex topological dependencies.<n>While Graph Neural Networks (GNNs) are the standard solution, state-of-the-art pipelines often rely on explicit structurals or memory-intensive node embeddings.<n>We present PENCIL, an encoder-only plain Transformer that replaces hand-crafted priors with attention over sampled local subgraphs.
  arXiv  Detail & Related papers  (2026-02-02T02:45:52Z)
• Generalized Graph Transformer Variational Autoencoder [0.0]
  We propose the Generalized Graph Transformer Variational Autoencoder (GGT-VAE)<n>Our model integrates Generalized Graph Transformer Architecture with Variational Autoencoder framework for link prediction.<n> Experimental results on several benchmark datasets demonstrate that GGT-VAE consistently achieves above-baseline performance.
  arXiv  Detail & Related papers  (2025-11-29T19:53:44Z)
• Relational Graph Transformer [44.56132732108148]
  Graph Transformer (Relel) is the first graph transformer designed specifically for relational tables.<n>Relel employs a novel multi-element tokenization strategy that decomposes each node into five components.<n>Our architecture combines local attention over sampled subgraphs with global attention to learnable centroids.
  arXiv  Detail & Related papers  (2025-05-16T07:51:58Z)
• Graph Structure Refinement with Energy-based Contrastive Learning [56.957793274727514]
  We introduce an unsupervised method based on a joint of generative training and discriminative training to learn graph structure and representation.<n>We propose an Energy-based Contrastive Learning (ECL) guided Graph Structure Refinement (GSR) framework, denoted as ECL-GSR.<n>ECL-GSR achieves faster training with fewer samples and memories against the leading baseline, highlighting its simplicity and efficiency in downstream tasks.
  arXiv  Detail & Related papers  (2024-12-20T04:05:09Z)
• DA-MoE: Addressing Depth-Sensitivity in Graph-Level Analysis through Mixture of Experts [70.21017141742763]
  Graph neural networks (GNNs) are gaining popularity for processing graph-structured data. Existing methods generally use a fixed number of GNN layers to generate representations for all graphs. We propose the depth adaptive mixture of expert (DA-MoE) method, which incorporates two main improvements to GNN.
  arXiv  Detail & Related papers  (2024-11-05T11:46:27Z)
• 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)
• AnchorGT: Efficient and Flexible Attention Architecture for Scalable Graph Transformers [35.04198789195943]
  We propose AnchorGT, a novel attention architecture for Graph Transformers (GTs) with global receptive field and almost linear complexity. Inspired by anchor-based GNNs, we employ structurally important $k$-dominating node set as anchors and design an attention mechanism that focuses on the relationship between individual nodes and anchors. With its intuitive design, AnchorGT can easily replace the attention module in various GT models with different network architectures.
  arXiv  Detail & Related papers  (2024-05-06T13:53:09Z)
• Unsupervised Graph Neural Architecture Search with Disentangled Self-supervision [51.88848982611515]
  Unsupervised graph neural architecture search remains unexplored in the literature. We propose a novel Disentangled Self-supervised Graph Neural Architecture Search model. Our model is able to achieve state-of-the-art performance against several baseline methods in an unsupervised manner.
  arXiv  Detail & Related papers  (2024-03-08T05:23:55Z)
• Global Minima, Recoverability Thresholds, and Higher-Order Structure in GNNS [0.0]
  We analyze the performance of graph neural network (GNN) architectures from the perspective of random graph theory. We show how both specific higher-order structures in synthetic data and the mix of empirical structures in real data have dramatic effects on GNN performance.
  arXiv  Detail & Related papers  (2023-10-11T17:16:33Z)
• Transitivity-Preserving Graph Representation Learning for Bridging Local Connectivity and Role-based Similarity [2.5252594834159643]
  We propose Unified Graph Transformer Networks (UGT) that integrate local and global structural information into fixed-length vector representations. First, UGT learns local structure by identifying the local substructures and aggregating features of the $k$-hop neighborhoods of each node. Third, UGT learns unified representations through self-attention, encoding structural distance and $p$-step transition probability between node pairs.
  arXiv  Detail & Related papers  (2023-08-18T12:49:57Z)
• HINormer: Representation Learning On Heterogeneous Information Networks with Graph Transformer [29.217820912610602]
  Graph Transformers (GTs) have been proposed which work in the paradigm that allows message passing to a larger coverage even across the whole graph. The investigation of GTs on heterogeneous information networks (HINs) is still under-exploited. We propose a novel model named HINormer, which capitalizes on a larger-range aggregation mechanism for node representation learning.
  arXiv  Detail & Related papers  (2023-02-22T12:25:07Z)
• Edge-featured Graph Neural Architecture Search [131.4361207769865]
  We propose Edge-featured Graph Neural Architecture Search to find the optimal GNN architecture. Specifically, we design rich entity and edge updating operations to learn high-order representations. We show EGNAS can search better GNNs with higher performance than current state-of-the-art human-designed and searched-based GNNs.
  arXiv  Detail & Related papers  (2021-09-03T07:53:18Z)
• Heterogeneous Graph Transformer [49.675064816860505]
  Heterogeneous Graph Transformer (HGT) architecture for modeling Web-scale heterogeneous graphs. To handle dynamic heterogeneous graphs, we introduce the relative temporal encoding technique into HGT. To handle Web-scale graph data, we design the heterogeneous mini-batch graph sampling algorithm---HGSampling---for efficient and scalable training.
  arXiv  Detail & Related papers  (2020-03-03T04:49:21Z)

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.