PaperlayerView exact revision on arXiv

Source-linked AI summary

Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs

Martin Simonovsky, Nikos Komodakis

arXiv:1704.02901v3cs.CVcs.LGcs.NE

TL;DR

Graph prediction needs convolution operators that handle irregular domains and varying graph structures without relying on spectral representations. The paper introduces spatial edge-conditioned convolution with dynamically generated, edge-label-dependent filters, achieving state-of-the-art performance on Sydney point-cloud classification and outperforming other deep-learning approaches on NCI1. The authors identify higher GPU memory consumption for large graphs with continuous edge labels as a current limitation.

  • Problem

    Graph prediction needs convolution operators that handle irregular domains and graphs with varying structure without relying on spectral representations.

    Source: §1 · p. 1

  • Method

    ECC performs spatial graph convolution with filter weights conditioned on edge labels and dynamically generated for each input sample.

    Source: §1 · p. 1, §3.1 · p. 3

  • Results

    The method sets a new state of the art on Sydney point-cloud classification and outperforms other deep-learning approaches on NCI1 graph classification.

    Source: §1 · p. 1, §5 · p. 8

  • Takeaways & Limitations

    ECC generalizes convolution to arbitrary graph structures and supports applications including point-cloud and graph classification.

    Source: §1 · p. 1, §5 · p. 8

    The authors identify higher GPU memory consumption for large graphs with continuous edge labels as a current limitation.

    Source: §5 · p. 8

Abstract

from arXiv · show

A number of problems can be formulated as prediction on graph-structured data. In this work, we generalize the convolution operator from regular grids to arbitrary graphs while avoiding the spectral domain, which allows us to handle graphs of varying size and connectivity. To move beyond a simple diffusion, filter weights are conditioned on the specific edge labels in the neighborhood of a vertex. Together with the proper choice of graph coarsening, we explore constructing deep neural networks for graph classification. In particular, we demonstrate the generality of our formulation in point cloud classification, where we set the new state of the art, and on a graph classification dataset, where we outperform other deep learning approaches. The source code is available at https://github.com/mys007/ecc

1. Introduction

The paper targets graph-structured data by introducing a graph convolution that uses edge labels to distinguish local neighborhoods. It applies this formulation to graph and point-cloud classification, reporting competitive or state-of-the-art performance.

  • Graph-structured problems arise in domains including 3D modeling, computational chemistry, biology, geospatial analysis, and social networks.Source: §1 · p. 1
  • Current graph convolutions do not exploit edge labels, producing an overly homogeneous view of local neighborhoods.Source: §1 · p. 1
  • The method attains state-of-the-art performance on the Sydney LiDAR point-cloud dataset while preserving sparsity and presumably fine details.Source: §1 · p. 1
  • The proposed convolution conditions filter weights on discrete or continuous edge labels and dynamically generates them for each input sample.Source: §1 · p. 1
  • The networks support graphs with arbitrary, varying structure throughout a dataset.Source: §1 · p. 1
  • The method reaches a competitive level on NCI1 and outperforms other deep-learning approaches for graph classification.Source: §1 · p. 1

2. Related Work

Prior graph-convolution methods address locality and weight sharing through spectral or spatial constructions, but often impose restrictive structure or homogeneous neighborhood weighting. ECC instead performs localized spatial filtering using edge-conditioned weights.

  • Spectral graph convolutions use graph Fourier transforms, but eigenvector-matrix multiplications are computationally expensive.Source: §2 · p. 2
  • The paper formulates filtering in the spatial domain, providing localization by construction while confronting variable neighborhood size and ordering.Source: §2 · p. 2
  • Several spatial methods share identical weights across edges, depend on hop counts, or use center-surround weighting.Source: §2 · p. 2
  • The paper argues that these methods do not capture finer neighborhood structure and therefore do not generalize standard grid convolutions.Source: §2 · p. 2
  • Graph neural networks also exploit edge labels, but their propagation-to-convergence systems differ from multilayer feed-forward architectures.Source: §2 · p. 2
  • Earlier point-cloud deep-learning approaches voxelized inputs, whereas this work regards point clouds as graphs in Euclidean space.Source: §2 · pp. 2–3

3. Method

The method defines Edge-Conditioned Convolution (ECC), a spatial graph convolution whose weights depend on edge labels, and builds hierarchical networks for variable-structure graphs. ECC preserves locality and weight sharing, recovers regular grid convolution as a special case, and supports graph and point-cloud classification.

Edge-Conditioned Convolution

  • ECC computes each vertex’s output by aggregating neighboring signals with edge-label-conditioned, dynamically generated weight matrices.The filter-generating network maps each edge label to an edge-specific matrix; biases and generating-network parameters are learnable.Source: §3.1 · p. 3
  • The spatial formulation handles varying neighborhood sizes and undefined vertex orderings while retaining locality and weight sharing.Aggregation is commutative, and weights are tied by edge label rather than hop distance, vertex position, or indiscriminately.Source: §3.1 · p. 3, §3.2 · p. 3

Relationship to Existing Formulations

  • Standard discrete convolution on grids is a special case of ECC when one-hot edge labels encode spatial offsets.For a 1D chain, a single-layer filter generator produces the corresponding reshaped kernel parameters.Source: §3.2 · p. 3
  • ECC retains the regular convolution’s parameter count and computational complexity on grids, apart from boundary normalization.The equivalence is demonstrated for centered filters and is unavailable to the cited alternative weight-tying schemes.Source: §3.2 · p. 3

Deep Networks with ECC

  • Deep graph-classification networks interleave ECC layers with pooling, using coarsened graphs and global pooling to process variable-size inputs.Pooling constructs coarser graphs through vertex merging, edge reduction and labeling, and a vertex mapping; batch normalization was needed for convergence.Source: §3.3 · pp. 3–4

Application in Point Clouds

  • For point clouds, the method creates vertices from points, assigns point features as signals, and connects spatially neighboring points with directed edges.The approach is presented as an alternative to voxelization, which can be memory-intensive and introduce discretization artifacts or loss of detail.Source: §3.4 · p. 4

4. Experiments

The experiments evaluate ECC on real and synthetic point-cloud classification, graph classification, and MNIST, using graph-based architectures with task-specific coarsening. ECC achieves state-of-the-art performance on Sydney, remains competitive on ModelNet, performs strongly on edge-labeled graph datasets, and matches standard quality on MNIST.

Sydney Urban Objects

  • ECC achieves a mean F1 score of 78.4 on Sydney, exceeding VoxNet at 73.0 and ORION at 77.8.The score is weighted by class frequency and aggregated over four standard training/testing splits.Source: §4.1 · pp. 5–6
  • Increasing convolution radii by 1.5× or 2× lowers performance, while identity skip-connections produce mean F1 scores of 77.0, 79.5, and 77.4 for ECC, ECC 1.5ρ, and ECC 2ρ.The 79.5 result is reported as a new state of the art, suggesting that larger context can help when integrated through a stronger identity connection.Source: §4.1 · p. 6

ModelNet

  • On ModelNet10 and ModelNet40, ECC remains competitive with 90.8% and 87.4% mean instance accuracy, respectively, but does not fully reach state of the art.Evaluation expands test sets to 12 orientations and also considers voting over orientations.Source: §4.2 · p. 6

Graph Classification

  • On five graph-classification datasets, ECC performs at state-of-the-art level on edge-labeled NCI1, NCI109, and MUTAG, while results on ENZYMES and D&D are somewhat below state of the art.The authors report that exploiting edge labels is important because ECC without edge labels and DCNN perform distinctly worse on the edge-labeled datasets.Source: §4.3 · p. 7

MNIST

  • ECC reaches 99.14 accuracy on MNIST, matching Defferrard et al. and exceeding other cited spectral approaches.The same 99.14 accuracy is obtained after discarding 80.9% of black points, indicating stability to changing graph structure across samples.Source: §4.4 · p. 8
  • The one-hot filter configuration reaches 99.37 accuracy, 0.23 higher than ECC, while learned filter-generating networks still learn effective edge-label partitions.The filters also exhibit structured patterns resembling those found in first CNN layers.Source: §4.4 · p. 8

5. Conclusion

The paper introduces ECC for spatial graph convolutions with dynamically generated, edge-conditioned filters. It reports state-of-the-art point-cloud classification and strong graph-classification performance, while identifying memory use on large graphs with continuous labels as future work.

  • ECC dynamically generates spatial convolution filters conditioned on edge labels for each input graph.Source: §5 · p. 8
  • ECC sets a new state of the art on Sydney point-cloud classification and outperforms other deep learning approaches on NCI1.Source: §5 · p. 8
  • Future work includes treating meshes as graphs and reducing GPU memory consumption for large graphs with continuous edge labels.Source: §5 · p. 8

Appendix

The appendix extends the paper with additional analyses and several ECC formulation variants. These cover benchmark results, noise robustness, edge labeling, identity connections, degree labels, and learned normalization.

  • The appendix provides further discussion of graph-classification results and investigates point-cloud robustness to noise.Source: A. Overview · p. 10
  • Additional ECC extensions vary edge labeling, identity connections, degree labels, and the learned normalization factor.Source: A. Overview · p. 10

B. Details on Graph Classification Benchmark

ECC performs strongly on edge-labeled graph benchmarks, matching or exceeding leading methods on NCI1, NCI109, and MUTAG. On edge-unlabeled ENZYMES and D&D, performance is mixed, though edge labels at coarser resolutions substantially help ENZYMES.

NCI1

NCI109

MUTAG

ENZYMES

D&D

C. Robustness to Noise

ECC is highly robust to point removal and can become robust to additive Gaussian noise through suitable training-data augmentation.

D. Edge Labels for Point Clouds

The study evaluates how edge-label choices affect ECC on point clouds, including rotation-invariant alternatives and robustness to point removal and Gaussian noise. Coordinate-based labels are important, while the reported rotation-invariant variant performs comparably or slightly better on this dataset.

E. Identity Connections

ECC-resnet adds identity skip-connections to the graph convolution formulation, motivated by residual networks. These connections usually do not improve the tested configurations, though one Sydney configuration shows a notable gain.

F. Vertex Degrees in Edge Labels

The paper extends edge labels with vertex-degree information to make neighborhood structure more informative. Degree features can substantially improve some graph-classification results, but no variant improves every dataset.

G. Vertex Degrees in Normalization

The paper tests a learned normalization factor conditioned on vertex degree as an alternative to fixed neighborhood-size normalization. ECC-Z helps some datasets but harms others, while embedding vertex information in labels performs better in the cited comparison.

Related papers

Loading 1704.02901v3…