Source-linked AI summary
Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs
Martin Simonovsky, Nikos Komodakis
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.
Method
ECC performs spatial graph convolution with filter weights conditioned on edge labels and dynamically generated for each input sample.
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.
Takeaways & Limitations
ECC generalizes convolution to arbitrary graph structures and supports applications including point-cloud and graph classification.
Takeaways & Limitations
The authors identify higher GPU memory consumption for large graphs with continuous edge labels as a current limitation.
Abstract
from arXiv · showhide
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.
- Current graph convolutions do not exploit edge labels, producing an overly homogeneous view of local neighborhoods.
- The method attains state-of-the-art performance on the Sydney LiDAR point-cloud dataset while preserving sparsity and presumably fine details.
- The proposed convolution conditions filter weights on discrete or continuous edge labels and dynamically generates them for each input sample.
- The networks support graphs with arbitrary, varying structure throughout a dataset.
- The method reaches a competitive level on NCI1 and outperforms other deep-learning approaches for graph classification.
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.
- The paper formulates filtering in the spatial domain, providing localization by construction while confronting variable neighborhood size and ordering.
- Several spatial methods share identical weights across edges, depend on hop counts, or use center-surround weighting.
- The paper argues that these methods do not capture finer neighborhood structure and therefore do not generalize standard grid convolutions.
- Graph neural networks also exploit edge labels, but their propagation-to-convergence systems differ from multilayer feed-forward architectures.
- Earlier point-cloud deep-learning approaches voxelized inputs, whereas this work regards point clouds as graphs in Euclidean space.
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.
- Edge-Conditioned Convolution: 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.
- 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.
- Relationship to Existing Formulations: 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.
- 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.
- 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.
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.
- Sydney Urban Objects: 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.
- 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.
- 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.
- 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.
- MNIST: 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.
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.
- ECC sets a new state of the art on Sydney point-cloud classification and outperforms other deep learning approaches on NCI1.
- Future work includes treating meshes as graphs and reducing GPU memory consumption for large graphs with continuous edge labels.
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.
- Additional ECC extensions vary edge labeling, identity connections, degree labels, and the learned normalization factor.
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: 83.80%: ECC outperforms convolutional methods without edge labels and remains slightly below WL at 84.55% on NCI1.
- NCI109: 82.14%: ECC is on par with non-convolutional approaches and exceeds DCNN at 62.86% on NCI109.
- MUTAG: 89.44%: ECC outperforms all reported MUTAG approaches except PSCN at 92.63%, although leading methods are considered statistically comparable on this tiny dataset.
- ENZYMES: 53.50%: ECC matches Deep WL at 53.43% on ENZYMES but trails WL and structure2vec.
- ENZYMES: More than 4 percentage points: edge labels at coarser graph resolutions improve ENZYMES performance through Kron reduction.
- D&D: 74.10%: ECC trails PSCN, WL, and structure2vec on the large-graph D&D dataset.
C. Robustness to Noise
ECC is highly robust to point removal and can become robust to additive Gaussian noise through suitable training-data augmentation.
- ECC is highly robust to point removal in real-world point clouds.
- Proper training-data augmentation can make ECC robust to additive Gaussian noise.
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.
- Edge labels encode point offsets in Cartesian and spherical coordinates, including coordinates, distance, and angular terms.
- 60.7 with isotropic labels and 38.9 with no labels show poor performance on Sydney.
- Either Cartesian or spherical coordinate information is important for the model's performance.
- IRz labeling performs comparably or slightly better than the proposed labeling, but this result may be specific to the dataset.
- The experiments include robustness to point removal and Gaussian noise.
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.
- ECC-resnet augments ECC with identity skip-connections to encourage residual learning.
- The residual formulation uses an identity mapping when layer dimensions match and a linear mapping otherwise.
- Identity connections do not benefit ECC in the tested network configurations, except on NCI109 and ENZYMES.
- 76.9 to 79.5 mean F1 score is the improvement reported for ECC 1.5ρ on Sydney with identity connections.
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.
- The graph-classification setup uses one-hot edge labels when available and Kron-reduction scalars on coarsened graphs.
- Degree information is added to edge labels for directed edges using variants based on the degrees of the incident vertices.
- The added degree labels are used at all graph resolutions, with degree defined as the neighborhood size.
- Up to 5 percentage points for ENZYMES and up to 2.14 percentage points for D&D are reported improvements from degree information.
- No degree-label variant guarantees consistent improvement across all datasets.
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.
- ECC normally normalizes by neighborhood size, while ECC-Z learns an additional factor from each vertex's degree.
- The factor-generating network maps vertex degree deg(i) = |N(i)| to a vertex-specific normalization factor.
- The factor-generating networks use an FC(32)-FC(1) configuration with orthogonal initialization and intervening ReLUs.
- ECC-Z helps on NCI109, ENZYMES, and ModelNet10 but harms performance on the other tested datasets.
- Embedding vertex information in edge labels is reported to achieve higher performance than ECC-Z.