Convolutional Neural Network Architectures for Signals Supported on Graphs

Fernando Gama; Antonio G. Marques; Geert Leus; Alejandro Ribeiro

Source-linked AI summary

Convolutional Neural Network Architectures for Signals Supported on Graphs

Fernando Gama, Antonio G. Marques, Geert Leus, Alejandro Ribeiro

arXiv:1805.00165v2May 1, 2018eess.SPcs.AIcs.LGstat.ML

TL;DR

CNNs lack a straightforward pooling mechanism for irregular graph-supported signals because downsampling does not define a suitable coarsened topology. This paper introduces selection and aggregation GNNs that retain graph-aware convolution and pooling, including a multinode aggregation variant for large graphs. Across source localization, authorship attribution, and 20NEWS classification, multinode aggregation GNNs consistently achieve the best performance.

Problem
Graph pooling is difficult after downsampling because the topology connecting the remaining signal components is not readily defined, and suitable coarsening criteria remain unclear.
Method
The paper proposes selection GNNs using graph filters, node selection, and zero padding, plus aggregation GNNs that create temporal diffusion signals for regular CNN processing, with a multinode variant for large graphs.
Results
Multinode aggregation GNNs consistently outperform the other evaluated GNN architectures across source localization, authorship attribution, and 20NEWS classification.
Takeaways & Limitations
Selection and aggregation GNNs provide graph-aware extensions of CNNs that preserve graph topology or encode it in diffusion signals while retaining convolutional and pooling stages.

Abstract

from arXiv · show

Two architectures that generalize convolutional neural networks (CNNs) for the processing of signals supported on graphs are introduced. We start with the selection graph neural network (GNN), which replaces linear time invariant filters with linear shift invariant graph filters to generate convolutional features and reinterprets pooling as a possibly nonlinear subsampling stage where nearby nodes pool their information in a set of preselected sample nodes. A key component of the architecture is to remember the position of sampled nodes to permit computation of convolutional features at deeper layers. The second architecture, dubbed aggregation GNN, diffuses the signal through the graph and stores the sequence of diffused components observed by a designated node. This procedure effectively aggregates all components into a stream of information having temporal structure to which the convolution and pooling stages of regular CNNs can be applied. A multinode version of aggregation GNNs is further introduced for operation in large scale graphs. An important property of selection and aggregation GNNs is that they reduce to conventional CNNs when particularized to time signals reinterpreted as graph signals in a circulant graph. Comparative numerical analyses are performed in a source localization application over synthetic and real-world networks. Performance is also evaluated for an authorship attribution problem and text category classification. Multinode aggregation GNNs are consistently the best performing GNN architecture.

I. INTRODUCTION

The paper extends CNNs to graph-supported signals through selection and aggregation GNN architectures that preserve graph structure while retaining convolutional and pooling operations. The proposed architectures address graph pooling without requiring a coarsened graph, and multinode aggregation GNNs perform best across the reported evaluations.

Motivation: Graph-supported signals use edge-weighted graphs to encode expected similarity or proximity among signal components, with graph shifts enabling local operations.Graph filters can be represented as polynomials in a shift operator or through sequences generated by repeated shifts.
Motivation: CNN layers combine convolution, feature summation, local summaries, subsampling, and pointwise activation; GNNs generalize these operations to graph neighborhoods and graph filters.Pointwise summation and activation transfer directly, while adjacency and convolution are generalized using graph neighborhoods and linear shift-invariant filters.
Motivation: Graph pooling is challenging because downsampling does not directly define a topology for the remaining nodes, and several prior architectures omit pooling altogether.Hierarchical clustering can create smaller graphs, but suitable coarsening criteria remain unclear.
Selection GNNs: Selection GNNs use linear shift-invariant graph filters and graph selection sampling, retaining sampled-node locations and using zero padding to compute deeper convolutional features on the original graph.Pooling aggregates information over multihop neighborhoods determined by the original topology and sampling sparsity.
Aggregation GNNs: Aggregation GNNs collect successive graph-shift outputs at designated nodes, producing temporal signals that encode nested-neighborhood information for processing by regular CNNs.Multinode aggregation GNNs run CNNs at several designated nodes and subsequently diffuse their outputs through the graph.
Evaluation: The evaluations cover source localization on synthetic and real-world networks, authorship attribution, and 20NEWS article classification, with multinode aggregation consistently performing best.The architectures are also compared with a graph-coarsening GNN based on multiscale hierarchical clustering.
Conventional CNNs: CNN convolution uses linear time-invariant filters across features, reducing learnable parameters from Mℓ×Mℓ−1 to Kℓ×Fℓ×Fℓ−1 when filters and feature counts are smaller.This parameter reduction is described as simplifying training and reducing overfitting.

B. Pooling

CNN pooling summarizes neighboring feature values, downsamples the resulting representations, and applies a pointwise nonlinearity. The summary can be linear or nonlinear and acts as a low-pass operation.

Pooling: Pooling aggregates neighboring feature components into a scalar using a possibly nonlinear summarization function ρℓ, reducing feature length from Nℓ−1 to Nℓ.The neighborhood is represented by index sets such as [n−1; n; n+1].
Local summarization: The summarization function ρℓ acts as a low-pass operation, with maximum and averaging given as common choices.Averaging uses the mean of the selected feature components.
Downsampling: Downsampling applies a binary sampling matrix Cℓ to the summarized features, after which a pointwise activation produces the layer features.The sampling matrix selects rows of the identity matrix corresponding to retained components.
Downsampling: The compression factor Nℓ−1/Nℓ is often matched to the summarization neighborhood so that each summary covers the corresponding number of adjacent indexes.In practice, only summarized components selected by Cℓ need to be computed.
Layer structure: Equations (2)–(5) specify a CNN layer by applying convolutional channels, local summarization, downsampling, and pointwise activation to the input features.The final layer may instead be fully connected and produce arbitrary linear combinations of the preceding features.

C. Signals on Graphs

Graph neural networks extend CNN operations to irregular graph-supported signals by replacing time shifts and filters with graph shifts and graph filters, while selection-based pooling addresses the difficulty of defining deeper-layer convolutions after downsampling.

Graph signals: Graph signals assign feature components to graph nodes, with edge weights encoding pairwise relationships and graph shifts implementing local operations.On a cyclic graph, the graph shift becomes a circular time shift.
CNN generalization: GNNs generalize CNN layers by retaining pointwise summation and nonlinearities while adapting filtering, local summaries, and downsampling to graph topology.Graph filters replace linear time-invariant filters, and graph neighborhoods replace regular-domain locality.
Selection GNNs: Selection GNNs use polynomial graph filters and graph selection sampling, while retaining sampled-node locations so later convolutions can operate on the original graph.The architecture zero-pads sampled features to the original graph before filtering and resampling.
Graph filtering: A graph filter with K1 taps aggregates information from nodes within up to its (K1−1)-hop neighborhood through successive local shifts.For a cyclic graph, the graph convolution reduces to the conventional time-domain convolution.
Pooling challenge: Graph pooling is challenging because downsampled signals no longer naturally reside on a graph, and suitable coarsening criteria are unclear.Hierarchical clustering can construct smaller graphs, but its appropriateness for GNN architectures is not established in the passage.

A. Selection Sampling on Graph Convolutional Features

Selection GNN convolution operates on the original graph while representing sampled features through their active-node locations, enabling lower-dimensional computation without abandoning the original topology.

Padded representation: At each layer, sampled features are represented as N-dimensional zero-padded signals whose nonzero components lie on active graph nodes.A tall binary sampling matrix maps the unpadded feature vector into this padded representation.
Original-graph convolution: Keeping sampled-node locations allows graph filters to compute deeper-layer convolutional features on the original graph.The padded signal is filtered on the original support and the output is selected at the active nodes.
Reduced computation: Reduced-dimensionality shift matrices enable equivalent convolutional computation directly in the smaller sampled space.These matrices depend only on the graph shift and sampling matrices and can be precomputed.
Implementation: Selection GNN convolution repeatedly applies the graph shift to padded signals, making sparse original graphs useful for local implementation.The convolutional and reduced-dimensional formulations are equivalent apart from subsampling.
Feature aggregation: The resulting convolutional features are followed by graph-based aggregation using the same linear feature summation as conventional CNNs.Feature aggregation itself does not require adaptation to graph structure.

B. Selection Sampling and Pooling

Selection GNN pooling summarizes graph neighborhoods at selected nodes, tracks their original locations across layers, and recovers conventional CNN sampling and pooling on cyclic graphs without hierarchical graph coarsening.

Neighborhood summaries: Pooling defines αℓ-hop neighborhoods from powers of the graph shift and intersects them with active nodes at the current layer.The reduced-dimensionality shift matrices encode these sampled graph neighborhoods.
Location tracking: Nested sampling matrices preserve the locations of selected nodes in the original graph for subsequent zero-padding and filtering.This location tracking is the mechanism that maintains a common graph support across layers.
Pooling pipeline: Each layer aggregates filtered features, summarizes selected neighborhoods, downsamples to Nℓ nodes, and applies a pointwise nonlinearity.Sampling matrices select each retained component at most once, while nested matrices record cumulative selections.
CNN reduction: On a cyclic graph with equally spaced sampling, selection GNN convolutional features and pooling become equivalent to conventional CNN operations.This requires the cyclic adjacency shift, nested regular sampling, and αℓ = Nℓ−1/Nℓ.
Coarsening-free pooling: Selection pooling reduces dimensionality without recomputing edges or weights between retained nodes, avoiding multiscale hierarchical clustering.The operations continue on the original graph support.

C. Practical Considerations

Selection GNN implementation uses precomputed graph-dependent matrices and layerwise sampling, with sparse-graph filtering and dimensionality reduction shaping computational cost; deeper filters may require regularization.

Architecture and training: The architecture specifies graph shifts, layer counts, feature counts, filter degrees, summary functions, sampling methods, node counts, and nonlinearities.Training learns filter coefficients and a final fully connected layer from the training set.
Node selection: Sampling methods select nested node subsets across layers, ensuring Nℓ≤Nℓ−1 and retaining previously selected locations.The specific selection method is chosen from graph-signal-processing sampling methods.
Computational implementation: Sparse original graphs support local filtering, while centralized implementations can use matrix multiplication in the reduced Nℓ-dimensional spaces.Reduced-dimensionality shift matrices can be computed before training.
Frequency considerations: Zero-padding and downsampling can alter frequency content, although learned filter taps are trained to account for this aliasing effect.The issue is stated for normal graph shift operators and arbitrary eigenvectors and downsampling matrices.
Computational cost: The cost of convolution is O(|E|KℓFℓFℓ−1) using padded filtering or O(Nℓ−1^2KℓFℓFℓ−1) using reduced-dimensional filtering.Pooling and downsampling have negligible cost in the stated accounting.
Scalability: Dimensionality reduction is critical for scalability because reduced-space convolution can be dominated by Nℓ−1^2.Filter parameters remain O(KℓFℓFℓ−1), independent of Nℓ−1.

IV. AGGREGATION GRAPH NEURAL NETWORKS

Aggregation GNNs transform graph signals into temporal sequences by recording successive graph-shifted components at a designated node, then apply conventional CNN operations to those sequences. The architecture incorporates graph topology through diffusion and reduces to a conventional CNN on cyclic graphs.

Aggregation construction: A designated node records successive graph-shifted signal components, producing a temporal sequence whose entries aggregate information from increasingly distant graph neighborhoods.The sequence begins with the node’s input value, then incorporates one-hop, two-hop, and farther neighborhoods through repeated graph shifts.
CNN processing: The resulting time-structured signal is processed with regular convolution, pooling, and pointwise nonlinearities from conventional CNNs.Graph topology enters through construction of the aggregated sequence rather than through the subsequent regular convolution itself.
Feature interpretation: Regular convolution over consecutive aggregated values effectively relates neighboring graph resolutions and can produce graph-smooth or graph-sharp features.Low-pass filters aggregate across neighborhoods, whereas high-pass filters detect sharp transitions between nearby-node values.
Relation to conventional CNNs: The aggregation GNN architecture reduces to a conventional CNN when graph signals are defined on a cyclic graph.On a cyclic graph, the aggregated signal at every node becomes the original signal up to cyclic shifting, after which a regular CNN is applied.

A. Multinode Aggregation Graph Neural Networks

Multinode aggregation GNNs use several designated nodes to build local temporal signals, process them with regular CNNs, and repeatedly exchange regional features across progressively smaller node subsets.

A. Multinode Aggregation Graph Neural Networks: Several selected nodes perform local graph exchanges to construct regular time-structured signals describing their respective neighborhoods.The first outer stage uses P1 selected nodes and Q1 shifts to gather local information at each node.
A. Multinode Aggregation Graph Neural Networks: Each selected node independently applies regular CNN layers to its aggregated signal and produces FL1 descriptive features for its neighborhood.The architecture treats these regular CNNs as inner aggregation layers.
A. Multinode Aggregation Graph Neural Networks: The resulting node-supported features are collected, zero-padded to the original graph, and diffused toward a smaller subset of selected nodes.This prepares regional features for the next outer aggregation stage.
A. Multinode Aggregation Graph Neural Networks: At each subsequent outer layer, selected nodes again construct temporal signals and run regular CNNs to generate features describing increasingly broader regions.The procedure repeats through R exchange layers, with Lr inner CNN layers at outer layer r.

B. Practical Considerations

Practical design choices concern locality, filter and pooling behavior, node selection, numerical normalization, and distributed computation in multinode architectures.

Local architecture: Single-node aggregation is entirely local: one node gathers information through local exchanges and produces the final output without physical access to every network node.This contrasts with the multinode setting, where processing is distributed across selected nodes.
Numerical normalization: Large networks may require a normalized graph shift because powers of the shift operator and associated aggregated components can become too large and numerically unstable.The normalization is chosen so the shift operator has spectral radius one.
Node selection: The choice of aggregating nodes affects overall performance and can use degree, signal frequency content, or network centrality criteria.The experiments select nodes using leverage scores from two sampling schemes.
Filter design: Aggregation filters can be shorter and emphasize high-frequency features because initial graph diffusion already performs part of the multiresolution aggregation.The regular CNN design can leverage conventional CNN expertise because the constructed signal has regular temporal structure.
Pooling: Pooling should preserve top samples for finer resolutions together with selected bottom samples for coarser information in the aggregated sequence.The pooling expressions match classical CNNs, but the selection of samples differs because sequence positions represent resolution levels.
Distributed computation: Multinode computation can be distributed across the participating nodes, and node-dependent shift counts and feature counts can be accommodated.The architecture is described as a decentralized method for constructing regional features.

V. NUMERICAL EXPERIMENTS

The experiments evaluate selection, aggregation, and multinode GNNs across synthetic and real-world graph tasks, using graph coarsening as a comparison architecture. The reported results show that multinode aggregation GNNs consistently outperform the other architectures.

V. NUMERICAL EXPERIMENTS: The evaluation covers source localization on synthetic SBM and Facebook networks, authorship attribution, and 20NEWS text categorization.The experiments include both synthetic and real datasets.
V. NUMERICAL EXPERIMENTS: The proposed selection, aggregation, and multinode GNNs are compared with a graph-coarsening architecture based on multiscale hierarchical clustering.Node-selection strategies include degree, experimentally designed sampling leverage scores, and spectral proxies.
V. NUMERICAL EXPERIMENTS: For SBM experiments, classification accuracy is averaged across ten graph instances, with standard deviation reported across those instances.Each graph instance uses ten independently generated training, validation, and test datasets.

A. Source Localization

The source-localization experiments evaluate GNN architectures on synthetic stochastic block-model graphs, where the multinode model achieves the strongest reported performance without apparent overfitting.

Experimental setting: The experiment uses connected stochastic block-model graphs with 100 nodes and five communities of 20 nodes each.Within-community edges have probability 0.8, while between-community edges have probability 0.2.
Experimental setting: Source localization estimates which community originated a signal diffused for an unknown time over the graph.The diffused signal is defined as x = A^tδ_c, with t ≥ 0.
Experimental setting: The datasets contain 10,000 training signals, 200 test signals, and 2,000 validation signals, with diffusion times sampled below 25.Experiments use 10 graphs and 10 training/test realizations per graph.
Model setup: The graph shift operator is normalized as S = A/λmax for numerical reasons.
Model setup: The tested architectures use two layers, 32 output features per layer, and five-tap filters; selection GNNs sample 10 nodes per layer.Selection summarization neighborhoods have sizes 6 and 8, while aggregation nodes are chosen by degree, EDS leverage score, or spectral-proxy norm.
Results: Training and validation losses decrease together and remain essentially equal, indicating no observed overfitting.The validation and training curves are reported as essentially equal throughout training for all three architectures.
Results: Multinode GNN with spectral-proxy node selection achieves the best accuracy, while aggregation and multinode models outperform graph coarsening.Selection GNNs using EDS and spectral-proxy sampling also outperform graph coarsening.

B. Facebook network

A second source-localization experiment tests the architectures on a 234-user Facebook network with two communities. All models achieve high accuracy, with multinode GNN using spectral proxies reaching 99.0%.

Experimental setting: The real-world experiment uses the largest connected component of a 234-user Facebook network, which contains two communities of different sizes.The task is to identify which community originated a diffused signal.
Model setup: The selection GNN uses two layers with 10-node selection, 32 features per layer, and five-tap filters.Its pooling uses max summarization with neighborhood sizes 2 and 4.
Results: Table II reports classification accuracy averaged over 10 training and test realizations, with standard deviations in parentheses.
Results: 99.0% classification accuracy is achieved by multinode GNN using spectral proxies, the best result among the evaluated architectures.All architectures attain very high classification accuracy, and selection GNN tends to outperform aggregation GNN.

C. Authorship attribution

The authorship-attribution experiment represents writing style with functional-word adjacency graphs and graph signals, then compares proposed GNN architectures with graph coarsening. Multinode GNN performs best, reaching 80.5% accuracy with EDS-based node selection.

Authorship attribution: The experiment models each author’s writing style as a weighted word adjacency network whose nodes are functional words.Graph edges encode precedence relationships between words in excerpts.
Dataset construction: The Brontë corpus contains 682 excerpts, 211 functional-word nodes, 546 training excerpts, and 136 test excerpts.A balanced authorship-classification set uses 1,092 training excerpts and 272 test excerpts.
Architectures: The comparison includes selection, aggregation, multinode, and graph-coarsening GNN architectures.Selection GNNs use 100 sampled functional-word nodes, while the tested architectures use multiple graph-filter and pooling configurations.
Results: 80.5% average classification accuracy is achieved by the multinode GNN with EDS-based node selection.Accuracy is averaged over 10 realizations, with standard deviations reported in Table III.
Results: All proposed GNN architectures outperform the graph-coarsening GNN, while EDS favors aggregation and multinode GNNs and spectral proxies favor selection GNNs.The result compares architecture and node-selection choices within the authorship-attribution evaluation.