TRACE: Learning to Compute on Graphs

• URL: http://arxiv.org/abs/2509.21886v1
• Date: Fri, 26 Sep 2025 05:22:32 GMT
• Title: TRACE: Learning to Compute on Graphs
• Abstract summary: We introduce textbfTRACE, a new paradigm built on an architecturally sound backbone and a principled learning objective.<n>First, TRACE employs a Hierarchical Transformer that mirrors the step-by-step flow of computation.<n>Second, we introduce textbffunction shift learning, a novel objective that decouples the learning problem.
• Score: 15.34239150750753
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Learning to compute, the ability to model the functional behavior of a computational graph, is a fundamental challenge for graph representation learning. Yet, the dominant paradigm is architecturally mismatched for this task. This flawed assumption, central to mainstream message passing neural networks (MPNNs) and their conventional Transformer-based counterparts, prevents models from capturing the position-aware, hierarchical nature of computation. To resolve this, we introduce \textbf{TRACE}, a new paradigm built on an architecturally sound backbone and a principled learning objective. First, TRACE employs a Hierarchical Transformer that mirrors the step-by-step flow of computation, providing a faithful architectural backbone that replaces the flawed permutation-invariant aggregation. Second, we introduce \textbf{function shift learning}, a novel objective that decouples the learning problem. Instead of predicting the complex global function directly, our model is trained to predict only the \textit{function shift}, the discrepancy between the true global function and a simple local approximation that assumes input independence. We validate this paradigm on electronic circuits, one of the most complex and economically critical classes of computational graphs. Across a comprehensive suite of benchmarks, TRACE substantially outperforms all prior architectures. These results demonstrate that our architecturally-aligned backbone and decoupled learning objective form a more robust paradigm for the fundamental challenge of learning to compute on graphs.

Related papers

• Position: Graph Condensation Needs a Reset -- Move Beyond Full-dataset Training and Model-Dependence [26.234880574328823]
  We argue that graph condensation, in its current form, needs a reset.<n>We call for moving beyond full-dataset training and model-dependent design.<n>We aim to reorient the field toward approaches that deliver on the true promise of condensation.
  arXiv  Detail & Related papers  (2026-05-17T07:08:22Z)
• A General Neural Backbone for Mixed-Integer Linear Optimization via Dual Attention [33.27281529953169]
  Mixed-integer linear programming (MILP) is a widely used modeling framework for optimization.<n>Recent advances in deep learning address this challenge by representing MILP instances as variable-constraint bipartite graphs.<n>We present an attention-driven neural architecture that learns expressive representations beyond the pure graph view.
  arXiv  Detail & Related papers  (2026-01-08T02:23:47Z)
• 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)
• What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding [67.59552859593985]
  Graph Transformers, which incorporate self-attention and positional encoding, have emerged as a powerful architecture for various graph learning tasks. This paper introduces first theoretical investigation of a shallow Graph Transformer for semi-supervised classification.
  arXiv  Detail & Related papers  (2024-06-04T05:30:16Z)
• Homological Convolutional Neural Networks [4.615338063719135]
  We propose a novel deep learning architecture that exploits the data structural organization through topologically constrained network representations. We test our model on 18 benchmark datasets against 5 classic machine learning and 3 deep learning models.
  arXiv  Detail & Related papers  (2023-08-26T08:48:51Z)
• End-to-End Meta-Bayesian Optimisation with Transformer Neural Processes [52.818579746354665]
  This paper proposes the first end-to-end differentiable meta-BO framework that generalises neural processes to learn acquisition functions via transformer architectures. We enable this end-to-end framework with reinforcement learning (RL) to tackle the lack of labelled acquisition data.
  arXiv  Detail & Related papers  (2023-05-25T10:58:46Z)
• Counterfactual Intervention Feature Transfer for Visible-Infrared Person Re-identification [69.45543438974963]
  We find graph-based methods in the visible-infrared person re-identification task (VI-ReID) suffer from bad generalization because of two issues. The well-trained input features weaken the learning of graph topology, making it not generalized enough during the inference process. We propose a Counterfactual Intervention Feature Transfer (CIFT) method to tackle these problems.
  arXiv  Detail & Related papers  (2022-08-01T16:15:31Z)
• Stabilizing Q-learning with Linear Architectures for Provably Efficient Learning [53.17258888552998]
  This work proposes an exploration variant of the basic $Q$-learning protocol with linear function approximation. We show that the performance of the algorithm degrades very gracefully under a novel and more permissive notion of approximation error.
  arXiv  Detail & Related papers  (2022-06-01T23:26:51Z)
• Neural combinatorial optimization beyond the TSP: Existing architectures under-represent graph structure [9.673093148930876]
  We analyze how and whether recent neural architectures can be applied to graph problems of practical importance. We show that augmenting the structural representation of problems with Distance is a promising step towards the still-ambitious goal of learning multi-purpose autonomous solvers.
  arXiv  Detail & Related papers  (2022-01-03T14:14:28Z)
• Persformer: A Transformer Architecture for Topological Machine Learning [0.0]
  Persformer is the first Transformer neural network architecture that accepts persistence diagrams as input. In this article, we introduce Persformer, the first Transformer neural network architecture that accepts persistence diagrams as input.
  arXiv  Detail & Related papers  (2021-12-30T21:10:17Z)
• Rethinking Architecture Design for Tackling Data Heterogeneity in Federated Learning [53.73083199055093]
  We show that attention-based architectures (e.g., Transformers) are fairly robust to distribution shifts. Our experiments show that replacing convolutional networks with Transformers can greatly reduce catastrophic forgetting of previous devices.
  arXiv  Detail & Related papers  (2021-06-10T21:04:18Z)
• Joint learning of variational representations and solvers for inverse problems with partially-observed data [13.984814587222811]
  In this paper, we design an end-to-end framework allowing to learn actual variational frameworks for inverse problems in a supervised setting. The variational cost and the gradient-based solver are both stated as neural networks using automatic differentiation for the latter. This leads to a data-driven discovery of variational models.
  arXiv  Detail & Related papers  (2020-06-05T19:53:34Z)
• Self-Learning with Rectification Strategy for Human Parsing [73.06197841003048]
  We propose a trainable graph reasoning method to correct two typical errors in the pseudo-labels. The reconstructed features have a stronger ability to represent the topology structure of the human body. Our method outperforms other state-of-the-art methods in supervised human parsing tasks.
  arXiv  Detail & Related papers  (2020-04-17T03:51:30Z)

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.