PaperlayerView exact revision on arXiv

Source-linked AI summary

Directed Acyclic Graph Neural Networks

Veronika Thost, Jie Chen

arXiv:2101.07965v3cs.LGcs.AI

TL;DR

GNN message passing uses local neighborhoods, while DAG partial order carries dependency information relevant to graph representations. DAGNN processes representations along that order, and the paper reports stronger performance than MPNNs and representative DAG architectures across evaluated tasks.

  • Problem

    DAGs encode a partial order, including computation dependencies in neural architectures, but conventional MPNN information is limited by a depth-bounded multi-hop neighborhood.

    Source: §1 · p. 2

  • Method

    DAGNN updates node representations sequentially according to the partial order, aggregating current-layer information from direct predecessors and reading out nodes without successors.

    Source: §1 · p. 2

  • Results

    DAGNN outperforms MPNNs on several representative datasets and tasks and outperforms D-VAE and other baselines on the reported DAG-scoring tasks.

    Source: §4.2 · pp. 7–8, §5 · p. 9

  • Takeaways & Limitations

    The analysis establishes maximal parallel concurrency for topological batching and permutation invariance and injectivity under mild assumptions.

    Source: §2.2 · p. 5, §5 · p. 9

    The ϵ needed to ensure injection is unknown and is either set to zero or treated as a tunable hyperparameter in practice.

    Source: §2.3 · pp. 5–6

Abstract

from arXiv · show

Graph-structured data ubiquitously appears in science and engineering. Graph neural networks (GNNs) are designed to exploit the relational inductive bias exhibited in graphs; they have been shown to outperform other forms of neural networks in scenarios where structure information supplements node features. The most common GNN architecture aggregates information from neighborhoods based on message passing. Its generality has made it broadly applicable. In this paper, we focus on a special, yet widely used, type of graphs -- DAGs -- and inject a stronger inductive bias -- partial ordering -- into the neural network design. We propose the \emph{directed acyclic graph neural network}, DAGNN, an architecture that processes information according to the flow defined by the partial order. DAGNN can be considered a framework that entails earlier works as special cases (e.g., models for trees and models updating node representations recurrently), but we identify several crucial components that prior architectures lack. We perform comprehensive experiments, including ablation studies, on representative DAG datasets (i.e., source code, neural architectures, and probabilistic graphical models) and demonstrate the superiority of DAGNN over simpler DAG architectures as well as general graph architectures.

1 INTRODUCTION

GNNs use neighborhood aggregation to exploit graph structure, while DAG edges encode a partial order that carries dependency information. DAGNN processes DAGs along that order; the paper also studies its theoretical properties, relation to prior architectures, and empirical performance.

1 INTRODUCTION

  • DAGNN updates node representations in partial order, using current-layer information from direct predecessors so nodes without successors can digest the entire graph.Unlike MPNNs, whose node information is limited by a multi-hop neighborhood and network depth L, DAGNN uses more recent information.Source: §1 · p. 2
  • Its architecture aggregates from direct predecessors, pools only nodes without successors, and combines attention, multiple layers, and topological batching.These choices exploit DAG structure; the paper describes this instantiation as state of the art.Source: §1 · p. 2
  • The theoretical analysis establishes maximal parallel concurrency for topological batching and shows permutation invariance and injectivity under mild assumptions.The authors state that injectivity reassures that DAGNN's graph representation is discriminative.Source: §1 · p. 2
  • The paper unifies representative DAG architectures, including D-VAE (Zhang et al., 2019), as special cases of the proposed framework.It compares DAGNN with those architectures and discusses differences associated with its superior performance.Source: §1 · p. 2
  • Evaluation on source-code, neural-architecture-search, and Bayesian-network-learning datasets shows DAGNN outperforming representative DAG architectures and MPNNs.The paper describes these as comprehensive empirical evaluations.Source: §1 · p. 2

2 THE DAGNN MODEL

DAGNN processes DAG nodes in partial-order sequence, using predecessor information to update representations and read out the graph from target nodes. Its framework also provides guarantees about batching efficiency and graph-representation properties under stated conditions.

2.1 MODEL

  • DAGNN updates each node from direct predecessors’ current-layer representations, combining their message with the node’s prior state through a GRU.The aggregation is instantiated with attention.Source: §2.1 · pp. 3–4
  • The readout pools representations across layers only at target nodes and, when bidirectional, combines results from both DAG directions.In the reverse DAG, target nodes correspond to the original graph’s sources; unidirectional processing drops that pooling term.Source: §2.1 · p. 4

2.2 TOPOLOGICAL BATCHING

  • Topological batching groups mutually incomparable nodes for parallel processing and uses the minimum number of sequential batches, equal to the longest path’s node count.The batching procedure satisfies the stated partition properties and permits each batch’s nodes to be processed in parallel.Source: §2.2 · p. 5

2.3 PROPERTIES

  • The graph representation is invariant to node indexing when the aggregation, combination, and readout functions are invariant to node indexing.The instantiated functions are stated to satisfy this invariance.Source: §2.3 · p. 5
  • DAGNN’s mapping is injective when its aggregation, combination, and readout are injective multiset functions, though the paper’s instantiations are not necessarily injective.An ε-trick can ensure injection, but the required ε is unknown and may be set to zero or tuned.Source: §2.3 · pp. 5–6

3 COMPARISON TO RELATED MODELS

The paper frames earlier DAG and tree architectures as restricted cases of its framework. It contrasts DAGNN with those models, highlighting limitations of tree-specific designs and differences from the D-VAE encoder.

3 COMPARISON TO RELATED MODELS

  • Earlier DAG and tree architectures can be viewed as restricted cases of DAGNN’s framework, with D-VAE’s encoder identified as the closest related architecture (Zhang et al., 2019).Source: §3 · p. 6
  • Some recursive tree models require fixed child counts and omit internal-node inputs (Socher et al., 2011; 2012; 2013; Ebrahimi & Dou, 2015).Tree-LSTM and DAG-RNN use recurrent combination but form messages from naive sums or element-wise products of child representations (Tai et al., 2015; Zhang et al., 2016; Kiperwasser & Goldberg, 2016; Shuai et al., 2016).Source: §3 · p. 6
  • Unlike D-VAE’s gated-sum aggregation, DAGNN uses attention and multiple layers, which the authors describe as more natural and powerful for general GNNs (Zhang et al., 2019).The authors report that their empirical results confirm the value of these differences.Source: §3 · p. 6

4 EVALUATION

The evaluation compares DAGNN with DAG and general graph architectures across source-code prediction, neural-architecture scoring, and Bayesian-network scoring, alongside timing, ablation, and layer-sensitivity studies.

4.1 DATASETS, TASKS, METRICS, AND BASELINES

  • The evaluation uses OGBG-CODE Python-function DAGs for TOK and longest-path tasks, plus NA and BN datasets for score prediction.OGBG-CODE contains 452,741 functions; NA contains 19,020 architectures and BN contains 200,000 networks.Source: §4.1 · pp. 6–7

4.2 RESULTS AND DISCUSSION

  • DAGNN performs best on both TOK and longest-path prediction across OGBG-CODE and its 15% subset.The TOK metric is F1, whose stated best achievable value is 90.99; the longest-path metric is accuracy.Source: Table 1 · p. 7, §4.2 · pp. 7–8
  • On neural-architecture and Bayesian-network scoring, DAGNN outperforms D-VAE, which outperforms the other four baselines.The comparison covers predictive performance of latent representations on NA and BN.Source: Table 2 · p. 7, §4.2 · p. 8
  • Removing attention generally causes the largest ablation degradation, while changes to layers, GRUs, readout, or edge attributes also incur losses.The LP-15 gated-sum exception is a tight-margin result relative to standard deviation.Source: Table 3 · p. 8, §4.2 · p. 8
  • DAGNN’s sequential topological processing costs more per epoch than concurrent MPNN processing, but its autoencoder overhead may be negligible in some comparisons.DAGNN reached its best performance around epoch 45, versus around 200 for D-VAE.Source: §4.2 · p. 8, Figure 3 · p. 8
  • DAGNN performs best with two or three layers; one layer is insufficient, and additional layers beyond three offer no advantage.On TOK-15, the largest improvement occurs beyond a single layer, while one layer has the highest variance under randomization.Source: Table 4 · p. 9, Figure 4 · p. 9, §4.2 · p. 9
  • Pooling over all nodes appears to correct target-node overemphasis for BN, where variables contribute equally to the BIC score.The DAG structure captures conditional independence, but does not make the variables unequal contributors to BIC.Source: §4.2 · p. 9
  • Bayesian optimization over DAGNN-encoded BN graphs found an Asia-network DAG with BIC −11107.29, higher than the ground truth’s −11109.74 and D-VAE’s −11125.75.The learned graph differs from the ground truth by omitting the edge from “visit to Asia?” to “Tuberculosis?”.Source: §4.2 · p. 9

5 CONCLUSIONS

DAGNN incorporates DAG partial order into graph representation learning and is reported to outperform MPNNs on representative datasets and tasks.

5 CONCLUSIONS

  • Figure 5 shows a Bayesian network identified by Bayesian optimization over DAGNN's latent space.Source: Figure 5 · p. 9
  • DAGNN incorporates DAG partial order as an inductive bias and outperforms MPNNs on several representative datasets and tasks.The paper also reports gains over other DAG-aware models, notably D-VAE.Source: §5 · p. 9
  • Ablations identify several DAGNN components as crucial contributors to performance gains over other models that incorporate DAG bias, notably D-VAE.Source: §5 · p. 9
  • The paper proves DAGNN is permutation invariant and injective, and that its topological batching achieves maximal parallel concurrency in processing DAGs.Source: §5 · p. 9

A PROOFS

The proofs establish maximal concurrency for topological batching and show permutation invariance and injectivity under the stated model assumptions.

A PROOFS

  • The proof equates the number of batches with the longest-path length, establishing the stated maximal-concurrency consequence of the batching properties.Source: A PROOFS · p. 13
  • Double induction over layers and batches establishes that node representations remain invariant to node indexing, yielding an index-invariant graph representation.Source: A PROOFS · p. 13
  • The proof attributes Gℓ's indexing invariance to a weighted sum with shared weights, and Fℓ's to its distinguished arguments.Source: A PROOFS · p. 13
  • Equal graph representations imply matching target sets and node representations; backward induction then recovers the same node and edge sets.Source: A PROOFS · p. 13
  • Injectivity of Fℓ lets the proof trace equal node representations back to the same input node features.Source: A PROOFS · p. 13

B DATASET DETAILS

The experiments cover code summarization and graph longest-path prediction on OGBG-CODE, plus latent-representation evaluation on neural-architecture and Bayesian-network DAGs.

B DATASET DETAILS

  • OGBG-CODE contains 452,741 Python method-definition DAGs, formed by augmenting abstract syntax trees with edges between source-code tokens.The graphs have 11/125/36,123 minimum/average/maximum nodes and include node type, attributes, AST depth, and pre-order index features.Source: B DATASET DETAILS · p. 13
  • OGBG-CODE evaluates method-name sub-token prediction and 275-class longest-path-length prediction, omitting AST depth for the latter task.Source: B DATASET DETAILS · p. 13
  • The OGBG-CODE project split keeps training projects unseen in validation and test, while OGBG-CODE-15 uses a random 15% of training data with validation and test unchanged.Source: B DATASET DETAILS · p. 14
  • For NA and BN, DAGNN's latent representations are evaluated for predictive performance against D-VAE and autoencoder baselines using the given 90/10 splits.Source: B DATASET DETAILS · p. 14
  • Neural architectures comprise 19,020 six-layer ENAS models, evaluated by weight-sharing CIFAR-10 accuracy; Bayesian networks comprise 200,000 random eight-node DAGs evaluated by BIC on the Asia dataset.Source: B DATASET DETAILS · p. 14

C BASELINE DETAILS

  • Code-task reference baselines include second-node token prediction, ground-truth tokens restricted to those in the graph, and validation-set majority-length prediction.Source: C BASELINE DETAILS · p. 14
  • The code-task comparisons include OGB GCN/GIN variants, GAT, GG-NN, hierarchical SAGPool and ASAP, and the D-VAE encoder; NA/BN baselines include S-VAE, GraphRNN, GCN, and DeepGMG.The NA/BN objective is to compare latent-representation performance.Source: C BASELINE DETAILS · p. 14

D.1 EXPERIMENT PROTOCOL AND HYPERPARAMETER TUNING

The protocol adapts established evaluation settings for the code benchmark and follows prior settings for neural architectures and Bayesian networks, with specified tuning and implementation adjustments.

D.1 EXPERIMENT PROTOCOL AND HYPERPARAMETER TUNING

  • For OGBG-CODE, they used 5-fold cross validation and swept eight learning rates, selecting each model’s best rate based on performance on OGBG-CODE-15.Training stopped when the validation metric did not improve for 20 epochs, except D-VAE and DAGNN, which used a patience of 10; those models also used gradient clipping at 0.25 and batch size 80.Source: §D.1 · p. 15
  • NA and BN follow Zhang et al.'s training settings, with DAGNN's scheduler starting at 1e-3 and maximum epochs reduced to 100 for NA and 50 for BN.A sparse Gaussian process evaluates latent representations, with results averaged over 10 folds.Source: §D.1 · p. 15
  • The Bayesian-network learning experiment follows Zhang et al.'s settings and runs ten rounds of Bayesian optimization.Source: §D.1 · p. 15

D.2 BASELINE MODELS

  • Baseline GNNs use PyTorch Geometric implementations and mostly OGB-suggested settings, while ASAP uses three layers instead of five because of memory constraints.Source: §D.2 · p. 15
  • The authors reimplement D-VAE in the DAGNN codebase because its implementation lacks topological batching support and has other restrictions, and report reproducing its published results.Source: §D.2 · p. 15

D.3 DAGNN IMPLEMENTATION

DAGNN’s implementation uses task-specific prediction heads and selects processing direction according to the experiment.

D.3 DAGNN IMPLEMENTATION

  • DAGNN uses independent linear classifiers for sub-token prediction at each sequence position and a linear classifier for longest-path-length prediction.The hidden dimension is 300.Source: §D.3 · p. 15
  • The NA and BN experiments use hidden dimension 501 and adapt the D-VAE decoder, while retaining Zhang et al. (2019)’s baselines and procedures.Bidirectional processing is used for BN and OGBG-CODE token prediction; unidirectional processing is used for NA and longest-path prediction because bidirectionality did not improve performance there and took too much time.Source: §D.3 · p. 15

E DETAILS ON THE LONGEST PATH EXPERIMENT

The longest-path experiment links MPNNs’ weaker results on the smaller subset to low sample efficiency, while DAG models perform similarly across dataset sizes. The D-VAE reimplementation closely reproduces the original results.

E DETAILS ON THE LONGEST PATH EXPERIMENT

  • MPNN longest-path results are much worse on the 15% subset, which has a similar path-length distribution; DAG architectures perform similarly on both dataset sizes.The authors conclude that MPNNs’ degradation on the smaller training set reflects low sample efficiency.Source: E DETAILS ON THE LONGEST PATH EXPERIMENT · p. 16, Figure 6 · p. 16

F REIMPLEMENTATION OF D-VAE

G ADDITIONAL ABLATION RESULTS

Bidirectional processing is optional, and its performance relative to unidirectional processing varies by task. DAGNN outperforms the reported baselines except for the LP-15 comparison with D-VAE.

G ADDITIONAL ABLATION RESULTS

  • DAGNN outperforms all reported baselines across the direction variants, except that on LP-15 D-VAE beats bidirectional DAGNN but not unidirectional DAGNN.Bidirectional processing performs better on TOK-15 and BN, while unidirectional processing performs better on LP-15 and NA.Source: G ADDITIONAL ABLATION RESULTS · p. 16, Table 6 · p. 16
  • Bidirectional processing does not necessarily improve over unidirectional processing.Table 6 compares the two processing directions.Source: Table 6 · p. 16

Related papers

Loading 2101.07965v3…