PaperlayerView exact revision on arXiv

Source-linked AI summary

Gated Graph Recurrent Neural Networks

Luana Ruiz, Fernando Gama, Alejandro Ribeiro

arXiv:2002.01038v2eess.SPcs.LG

TL;DR

Graph processes require models that capture both temporal sequence structure and spatial graph structure. The paper introduces GRNNs, which combine recurrent hidden states with graph signal processing, and reports that gated variants address long-term temporal or spatial dependencies while GRNNs outperform conventional alternatives in the reported experiments.

  • Problem

    Graph processes have both temporal and spatial structure, whereas standard architectures are not designed to exploit both simultaneously.

  • Method

    The paper introduces GRNNs that combine recurrent hidden states with graph convolutions and extends them with time, node, and edge gating mechanisms.

  • Results

    GRNNs outperform GNNs and RNNs overall, while time gating improves long-term temporal dependencies and node and edge gates help encode long-range graph dependencies.

  • Takeaways & Limitations

    Jointly modeling sequence and graph structure is important for learning from graph processes, with gating offering targeted support for long-term dependencies.

Abstract

from arXiv · show

Graph processes exhibit a temporal structure determined by the sequence index and and a spatial structure determined by the graph support. To learn from graph processes, an information processing architecture must then be able to exploit both underlying structures. We introduce Graph Recurrent Neural Networks (GRNNs) as a general learning framework that achieves this goal by leveraging the notion of a recurrent hidden state together with graph signal processing (GSP). In the GRNN, the number of learnable parameters is independent of the length of the sequence and of the size of the graph, guaranteeing scalability. We prove that GRNNs are permutation equivariant and that they are stable to perturbations of the underlying graph support. To address the problem of vanishing gradients, we also put forward gated GRNNs with three different gating mechanisms: time, node and edge gates. In numerical experiments involving both synthetic and real datasets, time-gated GRNNs are shown to improve upon GRNNs in problems with long term dependencies, while node and edge gates help encode long range dependencies present in the graph. The numerical results also show that GRNNs outperform GNNs and RNNs, highlighting the importance of taking both the temporal and graph structures of a graph process into account.

I. INTRODUCTION

Graph processes combine temporal sequence structure with spatial graph structure, but conventional RNNs and GNNs each primarily address only one of these dimensions. The paper develops a unified GRNN framework to process both.

  • Motivation: GNNs process graph structure effectively but are limited when signals also change over time.
  • Motivation: RNNs model temporal dependencies through recurrence, motivating graph recurrent architectures for graph processes.
  • Contribution: The proposed GRNN framework replaces RNN linear transformations with graph filters, jointly exploiting temporal and graph structure.
  • Contribution: The paper establishes a unified GSP-based GRNN framework and analyzes its properties, including permutation equivariance and stability to graph perturbations.
  • Graph processes: Graph processes are time-varying graph signals whose values evolve over a fixed graph structure.

III. GRAPH RECURRENT NEURAL NETWORKS

GRNNs adapt recurrent state updates to graph signals by replacing linear transformations with graph convolutions. This yields local, parameter-efficient processing while retaining configurable hidden features and graph-aware outputs.

  • GRNN construction: GRNNs make the recurrent hidden state a graph signal and parameterize state updates using the graph shift operator.
  • GRNN construction: Graph convolutional parametrization uses K filter taps, enables local computation, and makes parameter count independent of graph size.
  • GRNN properties: Graph convolutions provide permutation equivariance and stability to graph perturbations, properties used in the GRNN analysis.
  • Outputs: A GNN can map hidden states to graph-signal outputs, with a one-layer graph filter and activation sufficient when outputs are graph signals.
  • Graph signal tensors: Graph signal tensors assign multiple features to each node, allowing the hidden-state descriptive power to be tuned through the feature dimension H.
  • Computation: Local hidden-state computation requires repeated exchanges with one-hop neighbors, while setting output filter order K = 1 avoids neighborhood exchanges at output computation.

IV. STABILITY OF GRNNS

GRNNs are permutation equivariant and Lipschitz stable to relative perturbations of the graph support under integral-Lipschitz and related assumptions. Their stability degrades polynomially with process length, with graph-dependent eigenvector misalignment also contributing.

  • GRNN outputs on permuted graphs are correspondingly permuted, making the architecture independent of node labeling.This equivariance also lets learned processing transfer across topologically symmetric graph regions.
  • The stability analysis measures general graph changes modulo node permutations through relative perturbation matrices and graph distance.A permutation of the original graph has zero distance under this measure.
  • Under the stated assumptions, GRNNs are Lipschitz stable to relative graph perturbations.The result applies to GRNNs built from integral Lipschitz filters with normalized filter height and normalized Lipschitz nonlinearities.
  • C(1 + Nδ)(T^2 + 3T) is the stability constant for a graph process of length T.C is the maximum filter constant, while δ measures eigenvector misalignment between the graph shift operator and perturbation matrix.
  • The T^2 term arises from recurrence, whereas the linear T term comes from sequential applications of the graph filters.Process length can be controlled by restricting or splitting graph processes.

V. GATED GRNN ARCHITECTURES

Gated GRNNs extend recurrent graph processing to address vanishing gradients in both time and space. Their gates control input and state retention through operators whose parameters are themselves generated by GRNNs, supporting time, node, and edge gating.

  • Time gating addresses temporal vanishing gradients, while node and edge gating target spatial imbalances in long-range graph exchanges.Spatial vanishing gradients can arise when some nodes or graph paths receive more importance than others.
  • Gated GRNNs use input and forget operators to control how much current input and past information contribute to each new state.The gates are updated at every sequence step, creating multiple dependency paths for short- and long-term dependencies.
  • The gate parameters are calculated as outputs of GRNNs, giving the gating operators recurrently generated parameters.Separate GRNN states are used for the input and forget gates.
  • The framework proposes three gating strategies: time, node, and edge gating.These strategies are intended to address distinct temporal and spatial dependency-imbalance scenarios.

A. Time gating

Time-gated GRNNs use scalar gates to regulate whole inputs and previous states across sequence steps. This targets temporal vanishing gradients while treating all nodes uniformly.

  • Time gating learns scalar input and forget gates between 0 and 1 to compensate for imbalanced temporal gradient paths.The gates multiply the input and state variables and can counter effects associated with overly small or large eigenvalues.
  • At each time instant, time gates can shut down the whole input or previous state without discriminating between nodes.This distinguishes time gating from spatially selective node and edge mechanisms.
  • A time-gated GRNN resembles an LSTM in using input and forget gates, but it does not include the LSTM output gate.The paper relates its gates to LSTM gates for regular data sequences.
  • Node-specific temporal interactions motivate node gating when graph-process dynamics vary across nodes or subgraphs.Node gates apply separate scalar input and forget gates to each node through diagonal matrices.
  • Composing node gating with graph convolution can be interpreted as a node-varying graph filter.Different nodes receive different weights rather than the scalar weights used by linear shift-invariant graph filters.

C. Edge gating

Edge-gated GRNNs control information transmission during local graph exchanges by assigning gates to edges. This implements edge-selective filtering and can suppress noisy or spurious graph connections.

  • Edge gates act within local exchanges, controlling how much information crosses each graph edge.Node gates instead operate after local exchanges to regulate longer-range graph dependencies.
  • Each edge’s input and forget gate scales its exchange by a value between 0 and 1, with zero completely shutting off that edge.This can help when graphs contain noisy or spurious edges, including graphs built from sample covariance matrices.
  • Edge gating can be interpreted as an edge-varying graph filter because it independently parametrizes edge weights in graph-shift multiplications.This contrasts with node-varying filtering, which assigns different weights by node.
  • Edge-gate parameters are matrices, whereas time-gate parameters are scalars and node-gate parameters are vectors.The corresponding parameter-generating models are attention mechanisms, fully connected layers, and GNNs, respectively.
  • Stability of gated GRNNs requires gate operators and their parameter-learning models to satisfy Lipschitz conditions with respect to parameters, states, and graph structure.The assumptions are denoted AS5 through AS7.
  • The gated-GRNN stability constant equals the non-gated constant plus a term with third- and fourth-order dependence on sequence length.The additional term reflects two extra recurrence relationships used to generate input and forget gate parameters and can be adjusted through gating parameters.

VI. NUMERICAL EXPERIMENTS

The experiments compare GRNNs with GNNs and RNNs on synthetic k-step prediction, then evaluate time, node, and edge gating under different dependency structures. GRNNs train efficiently and gating improves performance when temporal, spatial, or connectivity conditions make selective memory useful.

  • Experimental design: The experiments use synthetic k-step prediction with varying processes, graph structures, and gating mechanisms, alongside comparisons against architectures from prior work.The study includes 25 Monte Carlo simulations in the reported synthetic settings and also compares gated architectures such as DCRNN and GCRN in later experiments.
  • k-step prediction: GRNN vs. GNN vs. RNN: GRNNs outperform GNNs by almost 3 p.p. in average test rRMSE, while GRNNs and RNNs achieve roughly the same performance.The GRNN also trains faster and retains advantages when the training data is halved.
  • k-step prediction: AR(1) process and time gating: Time-gated GRNNs improve relative to GRNNs as α increases in AR(1) processes with stronger temporal correlation.The forget gate can partially shut off the recurrent state when the instantaneous input contains built-in memory.
  • k-step prediction: graph diffusion and node gating: Node-gated GRNNs achieve their largest relative improvements over GRNNs at intermediate spatial-correlation levels.At low α, input gates suppress less-informative inputs; at high α, forget gates suppress less-informative states.
  • k-step prediction: covariance graphs and edge gating: Edge-gated GRNNs outperform GRNNs on covariance graphs with n = 15 and n = 20 nearest neighbors.For small n, edge gating instead produces larger relative test RMSE on average.

E. Earthquake epicenter estimation

The earthquake experiment predicts one of 11 New Zealand regions from seismic readings collected across a 59-seismograph directed graph. GRNNs are compared with GNNs and RNNs under matched parameter budgets, with additional gated-architecture comparisons.

  • Data and task: The task predicts the geographic region of 2,289 New Zealand earthquakes from 10s, 20s, or 30s seismic readings.Inputs are sampled at 2 Hz immediately before each earthquake using a 3-nearest-neighbor directed network of 59 seismographs.
  • Models: The experiment compares GRNNs with RNNs and GNNs, then compares basic and gated GRNNs with gated DCRNNs.Hyperparameters were selected to ensure roughly equal inner-layer parameter counts, except for the gated GRNN variants.
  • Training and evaluation: The dataset is split into 1,648 training, 412 validation, and 229 testing earthquakes.Models are trained with class-weighted cross-entropy to account for class imbalance.

1) GRNN vs. GNN vs. RNN:

GRNNs combine recurrence with graph structure, retaining performance on longer seismic sequences where GNNs and RNNs degrade, while gating benefits depend on the task and graph process.

  • Earthquake region estimation: For 20s seismic waves, GRNN performance remains stable while GNN and RNN accuracy degrades as the input sequence length doubles.The RNN’s larger variance is attributed to exchanges that do not always match the seismograph network’s communication structure.
  • Earthquake region estimation: In 30s seismic waves, the edge-gated GRNN outperforms the GRNN by over 3 p.p. and classifies more than a third of test earthquakes correctly on the best split.Time and node gating do not improve average performance, although node gating reduces variance.
  • Traffic forecasting: On METR-LA traffic forecasting, all architectures perform roughly similarly except the time-gated GRNN, which performs worst by a large margin.Edge and node gating do not improve upon the GRNN, and the GSO choice has no bearing on architecture performance in this problem.
  • Epidemic tracking: On epidemic tracking, time- and node-gated GRNNs and GCRN achieve F1-scores approximately 2 p.p. higher than GRNN, whereas edge-gated GRNN and DCRNN perform worse.The authors relate node-gating gains to stopping information flow from recovered nodes, with the effect depending on the GSO.
  • Overall comparison: Across the evaluated synthetic and real-world problems, gating can improve GRNN performance for long-term temporal or long-range spatial dependencies.The paper compares GRNN architectures with GNNs, RNNs, DCRNN, and GCRN across seismic, traffic, and epidemic tasks.

APPENDIX A PROOF OF PROPOSITION 1

The proposition proof establishes permutation equivariance by propagating graph-signal permutations through graph convolutions and pointwise nonlinearities.

  • Permutation equivariance: Graph convolutions remain permutation equivariant under graph and signal permutation.The proof uses orthogonality of the permutation matrix and the corresponding transformed graph shift operator.
  • Permutation equivariance: Pointwise nonlinearities preserve the permutation relation, so the permuted hidden state produces the correspondingly permuted output.The argument applies the same reasoning to both σ and ρ.

APPENDIX B PROOF OF THEOREM 1

Theorem 1 bounds GRNN output changes caused by graph-support perturbations by combining filter perturbation bounds with recurrent-state error propagation.

  • Perturbation setup: The proof represents the perturbed graph shift as ˜S = S+ES+SET and applies graph-filter stability bounds to A, B, and C.The perturbation includes eigenvector misalignment through δ and assumes integral Lipschitz filters.
  • State-error propagation: The hidden-state discrepancy satisfies a recurrence relationship obtained by bounding input, state, and output terms with Lipschitz and norm inequalities.The recurrence is expanded over time to control the accumulated perturbation effect.
  • Final bound: The final stability bound follows by substituting bounds on state norms and filter differences, with the maximum filter Lipschitz constant controlling the result.Under the stated normalization and initialization conditions, the proof recovers the theorem’s bound.

APPENDIX C PROOF OF THEOREM 2

Theorem 2 extends the perturbation analysis to gated GRNNs by separately controlling gate, filter, and recurrent-state discrepancies before solving the resulting recurrence.

  • Perturbed gated architecture: The proof models perturbed gated operators and gate parameters, including input and forget gate transformations evaluated on the perturbed graph shift.The notation distinguishes perturbed filters, gates, and gate parameters.
  • Gate perturbation terms: Gate discrepancies are bounded using additivity, bounded gate-operator norms, Cauchy–Schwarz, and the assumptions on filters and inputs.These bounds are applied separately to input-gate and forget-gate terms.
  • State-error propagation: The state-error analysis combines gate and filter differences with the recurrent-state discrepancy to obtain a recurrence relationship.The proof bounds the intermediate gate states and the previous hidden state before assembling the full inequality.
  • Final bound: Adding gate operators does not affect the bound on state norms, allowing the gated proof to reuse the corresponding GRNN state-norm control.The resulting recurrence is solved and combined with filter perturbation bounds to obtain the theorem’s main result.
Loading 2002.01038v2…