PACE: A Parallelizable Computation Encoder for Directed Acyclic Graphs

• URL: http://arxiv.org/abs/2203.10304v1
• Date: Sat, 19 Mar 2022 11:56:51 GMT
• Title: PACE: A Parallelizable Computation Encoder for Directed Acyclic Graphs
• Authors: Zehao Dong, Muhan Zhang, Fuhai Li, Yixin Chen
• Abstract summary: We propose a Parallelizable Attention-based structure (PACE) that processes nodes simultaneously and encodes DAGs in parallel. PACE not only improves the effectiveness over previous sequential DAG encoders with a significantly boosted training and inference speed, but also generates smooth latent (DAG encoding) spaces.
• Score: 30.294095901315746
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Optimization of directed acyclic graph (DAG) structures has many applications, such as neural architecture search (NAS) and probabilistic graphical model learning. Encoding DAGs into real vectors is a dominant component in most neural-network-based DAG optimization frameworks. Currently, most DAG encoders use an asynchronous message passing scheme which sequentially processes nodes according to the dependency between nodes in a DAG. That is, a node must not be processed until all its predecessors are processed. As a result, they are inherently not parallelizable. In this work, we propose a Parallelizable Attention-based Computation structure Encoder (PACE) that processes nodes simultaneously and encodes DAGs in parallel. We demonstrate the superiority of PACE through encoder-dependent optimization subroutines that search the optimal DAG structure based on the learned DAG embeddings. Experiments show that PACE not only improves the effectiveness over previous sequential DAG encoders with a significantly boosted training and inference speed, but also generates smooth latent (DAG encoding) spaces that are beneficial to downstream optimization subroutines. Our source code is available at \url{https://github.com/zehaodong/PACE}

Related papers

• Directed Acyclic Graph Convolutional Networks [10.282099295800322]
  Directed acyclic graphs (DAGs) are central to science and engineering applications including causal inference, scheduling, and neural architecture search.<n>We introduce the DAG Convolutional Network (DCN), a novel graph neural network (GNN) architecture designed specifically for convolutional learning from signals supported on DAGs.
  arXiv  Detail & Related papers  (2025-06-13T20:40:50Z)
• Directed Graph Grammars for Sequence-based Learning [20.579076532082684]
  directed acyclic graphs (DAGs) are a class of graphs commonly used in practice.<n>We propose a grammar-based approach to constructing a principled, compact and equivalent sequential representation of a DAG.
  arXiv  Detail & Related papers  (2025-05-29T00:05:07Z)
• Nesterov Method for Asynchronous Pipeline Parallel Optimization [59.79227116582264]
  We introduce a variant of Nesterov Accelerated Gradient (NAG) for asynchronous optimization in Pipeline Parallelism.<n>Specifically, we modify the look-ahead step in NAG to effectively address the staleness in gradients.<n>We theoretically prove that our approach converges at a sublinear rate in the presence of fixed delay in gradients.
  arXiv  Detail & Related papers  (2025-05-02T08:23:29Z)
• LASE: Learned Adjacency Spectral Embeddings [7.612218105739107]
  We learn nodal Adjacency Spectral Embeddings (ASE) from graph inputs. LASE is interpretable, parameter efficient, robust to inputs with unobserved edges. LASE layers combine Graph Convolutional Network (GCN) and fully-connected Graph Attention Network (GAT) modules.
  arXiv  Detail & Related papers  (2024-12-23T17:35:19Z)
• Scalable Graph Compressed Convolutions [68.85227170390864]
  We propose a differentiable method that applies permutations to calibrate input graphs for Euclidean convolution. Based on the graph calibration, we propose the Compressed Convolution Network (CoCN) for hierarchical graph representation learning.
  arXiv  Detail & Related papers  (2024-07-26T03:14:13Z)
• Amplify Graph Learning for Recommendation via Sparsity Completion [16.32861024767423]
  Graph learning models have been widely deployed in collaborative filtering (CF) based recommendation systems. Due to the issue of data sparsity, the graph structure of the original input lacks potential positive preference edges. We propose an Amplify Graph Learning framework based on Sparsity Completion (called AGL-SC)
  arXiv  Detail & Related papers  (2024-06-27T08:26:20Z)
• Efficient Graph Similarity Computation with Alignment Regularization [7.143879014059894]
  Graph similarity computation (GSC) is a learning-based prediction task using Graph Neural Networks (GNNs) We show that high-quality learning can be attained with a simple yet powerful regularization technique, which we call the Alignment Regularization (AReg) In the inference stage, the graph-level representations learned by the GNN encoder are directly used to compute the similarity score without using AReg again to speed up inference.
  arXiv  Detail & Related papers  (2024-06-21T07:37:28Z)
• T-GAE: Transferable Graph Autoencoder for Network Alignment [79.89704126746204]
  T-GAE is a graph autoencoder framework that leverages transferability and stability of GNNs to achieve efficient network alignment without retraining. Our experiments demonstrate that T-GAE outperforms the state-of-the-art optimization method and the best GNN approach by up to 38.7% and 50.8%, respectively.
  arXiv  Detail & Related papers  (2023-10-05T02:58:29Z)
• Structural Re-weighting Improves Graph Domain Adaptation [13.019371337183202]
  This work examines different impacts of distribution shifts caused by either graph structure or node attributes. A novel approach, called structural reweighting (StruRW), is proposed to address this issue and is tested on synthetic graphs, four benchmark datasets, and a new application in high energy physics.
  arXiv  Detail & Related papers  (2023-06-05T20:11:30Z)
• Performance Embeddings: A Similarity-based Approach to Automatic Performance Optimization [71.69092462147292]
  Performance embeddings enable knowledge transfer of performance tuning between applications. We demonstrate this transfer tuning approach on case studies in deep neural networks, dense and sparse linear algebra compositions, and numerical weather prediction stencils.
  arXiv  Detail & Related papers  (2023-03-14T15:51:35Z)
• NVDiff: Graph Generation through the Diffusion of Node Vectors [20.424372965054832]
  We propose NVDiff, which takes the VGAE structure and uses a score-based generative model (SGM) as a flexible prior to sample node vectors. Built on the NVDiff framework, we introduce an attention-based score network capable of capturing both local and global contexts of graphs.
  arXiv  Detail & Related papers  (2022-11-19T20:43:39Z)
• Neural Topological Ordering for Computation Graphs [23.225391263047364]
  We propose an end-to-end machine learning based approach for topological ordering using an encoder-decoder framework. We show that our model outperforms, or is on-par, with several topological ordering baselines while being significantly faster on synthetic graphs with up to 2k nodes.
  arXiv  Detail & Related papers  (2022-07-13T00:12:02Z)
• Distributed stochastic optimization with large delays [59.95552973784946]
  One of the most widely used methods for solving large-scale optimization problems is distributed asynchronous gradient descent (DASGD) We show that DASGD converges to a global optimal implementation model under same delay assumptions.
  arXiv  Detail & Related papers  (2021-07-06T21:59:49Z)
• DAGs with No Curl: An Efficient DAG Structure Learning Approach [62.885572432958504]
  Recently directed acyclic graph (DAG) structure learning is formulated as a constrained continuous optimization problem with continuous acyclicity constraints. We propose a novel learning framework to model and learn the weighted adjacency matrices in the DAG space directly. We show that our method provides comparable accuracy but better efficiency than baseline DAG structure learning methods on both linear and generalized structural equation models.
  arXiv  Detail & Related papers  (2021-06-14T07:11:36Z)
• Embedding Graph Auto-Encoder for Graph Clustering [90.8576971748142]
  Graph auto-encoder (GAE) models are based on semi-supervised graph convolution networks (GCN) We design a specific GAE-based model for graph clustering to be consistent with the theory, namely Embedding Graph Auto-Encoder (EGAE) EGAE consists of one encoder and dual decoders.
  arXiv  Detail & Related papers  (2020-02-20T09:53:28Z)

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.