PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph Neural Networks with convolutional ARMA filters

Filippo Maria Bianchi, Daniele Grattarola, Lorenzo Livi, Cesare Alippi

arXiv:1901.01343v7cs.LGstat.ML

TL;DR

Polynomial graph filters provide efficient localized convolutions but have limited frequency-response flexibility and require high degree to capture broader structure. This paper develops a recursive, distributed ARMA graph-convolution layer and evaluates it across four downstream tasks. The ARMA layer outperforms polynomial-filter GNNs across those tasks while remaining localized and transferable to graphs with unseen topologies.

  • Problem

    Polynomial graph filters are efficient and localized, but high-degree requirements limit frequency-response flexibility, increase cost, and reduce robustness to noise and topology changes.

  • Method

    The paper develops an ARMA-based graph-convolution layer using recursive distributed operations, producing node-space-localized filters independent of a specific graph structure.

  • Results

    ARMA-equipped GNNs outperform GNNs with polynomial filters in semi-supervised node classification, graph signal classification, graph classification, and graph regression.

  • Takeaways & Limitations

    ARMA layers provide more expressive filter responses and can account for larger neighborhoods than same-order polynomial GNN layers.

  • Takeaways & Limitations

    Polynomial filtering remains constrained by locality, high-degree computational cost, overfitting of known graph frequencies, and sensitivity to noise and topology changes.

Abstract

from arXiv · show

Popular graph neural networks implement convolution operations on graphs based on polynomial spectral filters. In this paper, we propose a novel graph convolutional layer inspired by the auto-regressive moving average (ARMA) filter that, compared to polynomial ones, provides a more flexible frequency response, is more robust to noise, and better captures the global graph structure. We propose a graph neural network implementation of the ARMA filter with a recursive and distributed formulation, obtaining a convolutional layer that is efficient to train, localized in the node space, and can be transferred to new graphs at test time. We perform a spectral analysis to study the filtering effect of the proposed ARMA layer and report experiments on four downstream tasks: semi-supervised node classification, graph signal classification, graph classification, and graph regression. Results show that the proposed ARMA layer brings significant improvements over graph neural networks based on polynomial filters.

1. Introduction

The paper introduces an ARMA-based graph convolutional layer to address limitations of polynomial filters, offering flexible frequency responses, global structure modeling, and inductive transferability. Experiments evaluate it across four graph-learning tasks and report consistent gains over polynomial-filter GNNs.

  • Motivation: Polynomial graph filters are efficient and localized, but their smooth frequency responses limit modeling capability and require high degree for broad graph structure.High-degree filters can also be computationally expensive and sensitive to noise and topology changes.
  • Contribution: The paper proposes an ARMA-based GNN convolutional layer that generalizes polynomial-filter layers through a more flexible frequency-response design.The layer is designed to capture global graph structures with fewer parameters.
  • Contribution: A recursive formulation makes the ARMA layer fast, distributed, localized in node space, and independent of the underlying graph structure.This enables handling graphs with unseen topologies during inductive inference.
  • Evaluation: The proposed layer is evaluated on semi-supervised node classification, graph signal classification, graph classification, and graph regression.The experiments cover both node-level and graph-level prediction settings.
  • Results: ARMA-equipped GNNs outperform GNNs with polynomial filters in every downstream task.The reported evaluation spans all four tasks listed above.

2. Background: graph spectral filtering

Graph spectral filtering modifies graph-signal components in the Laplacian eigenbasis, but direct spectral methods are costly and tied to a specific topology. Polynomial node-domain filters improve efficiency and transferability, yet remain limited in receptive field, frequency flexibility, and robustness.

  • Spectral filtering: A graph filter modifies graph-signal components in the Laplacian eigenbasis according to a frequency response applied to each eigenvalue.The filtered signal is subsequently mapped back to the node space.
  • Spectral filtering: Early spectral GNN filters can model whole-graph interactions, but eigendecomposition and repeated dense projections are computationally expensive.Their dependence on a specific Laplacian spectrum also prevents transfer to graphs with different structures.
  • Polynomial filters: Polynomial filters implement localized weighted moving averages whose output at each node depends only on nodes within its K-hop neighborhood.Their parameters are independent of the Laplacian spectrum, supporting node-domain implementations.
  • Polynomial filters: Chebyshev expansions provide fast localized polynomial GNN filters with trainable matrices mapping input node features to output features.The layer applies a nonlinear activation after combining polynomial orders.
  • Polynomial filters: Capturing larger graph structures with polynomial filters requires high degree, which increases computational cost and harms interpolation, extrapolation, and topology-noise robustness.High-degree polynomials also overfit known Laplacian eigenvalues.

3. Rational filters for graph signals

Rational ARMA filters extend polynomial graph filtering with more expressive frequency responses and longer graph dependencies. The paper replaces costly matrix inversion with recursive operations that can be implemented efficiently using sparse tensor multiplications.

  • Rational filters: ARMA filters use a rational design that can approximate a wider variety of desired frequency-response shapes than polynomial filters.Different numerator and denominator orders are obtained by setting selected coefficients to zero.
  • Rational filters: Setting all q_k coefficients to zero recovers the polynomial filter as the model’s moving-average term.The autoregressive term is the additional component distinguishing ARMA from polynomial filtering.
  • Rational filters: The autoregressive term makes the model robust to noise and allows longer graph dynamics because the output depends on multiple propagation steps.This supports capturing longer dependencies and more global structures than same-degree polynomial filters.
  • Implementation: Directly computing the ARMA matrix inverse is slow and produces a dense matrix, preventing sparse-multiplication implementations.The paper therefore approximates an ARMA1 filter through an iterative first-order recursion until convergence.
  • Implementation: The recursive filtering operation is connected to graph low-pass filtering, Label Propagation, and Personalized PageRank through repeated graph propagation.The frequency response follows from analyzing the recursion’s convergence.
  • Implementation: Summing K ARMA1 filters recovers the analytical ARMAK filtering operation.This provides the construction used to implement higher-order rational filters.

4. The ARMA neural network layer

The ARMA neural network layer implements trainable ARMA filtering through recursive, distributed GCS stacks, combining localized node-space operations with flexible graph-wide representations. Fixed-iteration variants improve training practicality while preserving transferability across graph topologies.

  • ARMA layer design: The ARMA layer replaces polynomial graph convolutions with a nonlinear, trainable filter whose frequency response has greater modeling flexibility.Its parameters are learned end-to-end from task-dependent losses rather than reproducing a designer-specified target response.
  • ARMA layer design: Each GCS layer performs localized neighbor exchanges and uses a skip connection to retain the initial node features.Its time and space complexity is linear in the number of edges through sparse multiplication with the modified Laplacian.
  • Recursive implementation: The ARMA1 implementation iterates a nonlinear recursive update until convergence, with convergence guaranteed under ||W||2 < 1 and a non-expansive activation.The update converges to a unique fixed point, making the initial state inconsequential in the convergent formulation.
  • Recursive implementation: The ARMAK layer combines the outputs of K parallel GCS stacks, allowing heterogeneous filtering operations through distinct trainable stacks.Dropout on skip connections encourages stacks to learn different responses, while shared parameters provide regularization.
  • Practical variant: Fixing the iteration count T removes the convergence requirement and yields a GNN that is easier to implement, faster to train and evaluate, and unaffected by stability issues.With finite iterations, the initial state influences the final representation; the paper initializes it using a linear transformation of the node features.
  • Properties: The resulting ARMA filters are localized in node space, independent of the underlying graph structure, and transferable to graphs with unseen topologies.The layer can also handle time-varying topology and graph signals by replacing the constant input with a time-dependent input.

5. Spectral analysis of the ARMA layer

The spectral analysis estimates how ARMA layers transform graph-frequency components and shows that stacking GCS units can approximate ARMA responses. Combining stacks produces filter shapes beyond the low-pass behavior of individual stacks and GCNs.

  • Empirical ARMA1 responses: The analysis measures filtering by comparing the Fourier components of the output signal with those of the input signal.UT ¯X shows how the original components UT X are changed by the GNN, and their ratio defines the empirical filter response.
  • Empirical ARMA1 responses: The empirical response of each GCS stack approaches the analytical ARMA1 response as the number of layers T increases.This supports using the empirical response to estimate the otherwise unknown filtering behavior of the nonlinear GNN.
  • Comparison with GCN: Stacked GCNs symmetrically amplify the lowest and highest frequencies, reflecting a less flexible response than heterogeneous GCS stacks.GCN response flexibility is mainly adjusted by manually tuning γ, while ARMA stacks vary through trainable parameters and their combination.
  • Filter responses: With K = 3, an ARMA layer can implement high-pass and band-pass responses, unlike an individual GCS stack.The reported high-pass example dampens low frequencies, whereas the band-pass example mostly allows medium frequencies.
  • Comparison with GCN: Different GCS stacks can selectively shrink or amplify Fourier components when combined in an ARMA layer.This heterogeneous combination is the stated source of the ARMA layer’s broader modeling capability.
  • Filter responses: A single GCS stack behaves as a low-pass filter that gradually dampens graph-Fourier components as frequency increases.High-pass and band-pass responses can nevertheless be formed by linearly combining low-pass stacks.

6. Experiments

The experiments evaluate ARMA convolutional layers across node, graph-signal, graph-classification, and graph-regression tasks against polynomial and rational-filter baselines. Across these settings, ARMA generally achieves stronger performance while retaining transferable and computationally efficient filtering.

  • Experimental setup: The evaluation compares ARMA with polynomial-filter GNNs and rational-filter CayleyNets across four downstream tasks using fixed architectures and training procedures.Additional baselines include GAT, GraphSAGE, and GIN.
  • Node classification: Node classification uses transductive citation-network benchmarks and inductive PPI graphs, with accuracy evaluated under single-label and multi-label settings.Citation networks use 20 labels per document class; PPI contains separate training, validation, and testing graphs.
  • Node classification: ARMA performs well across node-classification regimes because its flexible formulation can match task complexity; larger, better-labeled PPI graphs favor more complex models.On citation networks, strong regularization is important because only a few labels are available.
  • Node classification: ARMA significantly outperforms every other model on PPI, while its flexible filter responses support stronger modeling than local first-order neighborhood aggregation.GAT, GraphSAGE, and GIN require deeper stacks to reach higher-order neighborhoods and encounter the same over-smoothing issue as GCN.
  • Depth and graph structure: The optimal ARMA depth is low across datasets, consistent with short average shortest paths that allow most nodes to be reached in only a few propagation steps.This behavior is associated with the small-world structure of many real networks.
  • Efficiency: ARMA training uses sparse operations linear in the number of nodes and takes time comparable to a Chebyshev filter on PPI.CayleyNet is slower because its Jacobi-iteration formulation produces a high-order polynomial.
  • Graph signal classification: ARMA achieves slightly higher, almost perfect MNIST accuracy than Chebyshev and CayleyNet, and significantly outperforms all other models on 20news.The MNIST graph has larger optimal ARMA depth because its regular connectivity requires several propagation steps to mix node features.
  • Graph classification: On graph classification, ARMA achieves the highest mean accuracy among polynomial filters and higher mean accuracy with lower standard deviation than CayleyNets.These results indicate robustness and confirm transferability of the proposed layer.

7. Experimental details

The paper reports dataset characteristics, model hyperparameters, training procedures, and implementation settings for the node, signal, graph-classification, and regression experiments. These details include task-specific regularization, optimization, batch sizes, and dataset construction choices.

  • Node classification: Node-classification datasets are summarized by graph size, edge count, feature dimensionality, average shortest path, and number of node classes.The datasets include Cora, Citeseer, Pubmed, and PPI.
  • Node classification: Node-classification hyperparameters include regularization weight, learning rate, dropout, convolution depth, polynomial order, Jacobi iterations, and ARMA stack settings.Models are trained for 2000 epochs with early stopping and full-batch updates.
  • Graph regression: The QM9 regression dataset contains more than 130,000 molecular graphs whose nodes are heavy atoms and whose edges represent atomic bonds.The task predicts a chemical property from each molecule’s graph representation.
  • Graph regression: Graph regression uses Adam with learning rate 10^-3, batch size 64, no L2 regularization, and early stopping after 50 patience epochs.CayleyNets use only 3 Jacobi iterations because additional iterations caused numerical errors and rapid loss divergence.
  • Graph classification: Graph classification uses three GNN layers with 32 output units, ReLU activations, L2 regularization, Adam optimization, batch size 32, and patience of 50 epochs.Hyperparameters are summarized for ARMA, Chebyshev, and CayleyNets across datasets.
  • Graph signal classification: MNIST models are trained for 20 epochs with batch size 32, while 20news uses batch size 128 and 200-dimensional word embeddings.The datasets are generated using code from cnn_graph.
  • Graph signal classification: Graph-signal classification dataset summaries report graph size, average shortest path, class counts, and training, validation, and test-set signal counts.The corresponding model configurations are reported separately.

8. Conclusions

The paper introduces ARMA graph convolution as a rational filter with expressive frequency responses and demonstrates strong performance across diverse graph learning tasks.

  • ARMA layers model more expressive filter responses and account for larger neighborhoods than polynomial-filter GNN layers of the same order.
  • Parallel recurrent stacks approximate an arbitrary-order graph filter through efficient sparse tensor multiplications.
  • Spectral analysis shows that ARMA layers can implement a large variety of filter responses.
  • ARMA-equipped GNNs outperform existing architectures, including polynomial-filter and more complex models, across a large variety of graph machine learning tasks.
Loading 1901.01343v7…