PaperlayerView exact revision on arXiv

Source-linked AI summary

Geometric deep learning: going beyond Euclidean data

Michael M. Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, Pierre Vandergheynst

arXiv:1611.08097v2cs.CV

TL;DR

Deep learning has mainly targeted Euclidean data, leaving non-Euclidean domains such as graphs and manifolds without a common treatment. This paper surveys geometric deep learning models and applications, including a spectral CNN achieving 81.6% accuracy on CORA versus 75.7% previously.

  • Problem

    Deep learning remains primarily designed for Euclidean or grid-like data, while generalizing models across non-Euclidean domains remains challenging.

  • Method

    The paper provides an accessible overview of geometric deep learning problems, models, applications, difficulties, and future directions across graphs and manifolds.

  • Results

    81.6% accuracy was achieved on CORA with a spectral CNN, compared with 75.7% for the previous best result.

  • Takeaways & Limitations

    Geometric deep learning offers a common framework for extending structured deep models to non-Euclidean data.

  • Takeaways & Limitations

    Spectral filter constructions are limited to a single domain unless correspondence between domains is available for compatible basis construction.

Abstract

from arXiv · show

Many scientific fields study data with an underlying structure that is a non-Euclidean space. Some examples include social networks in computational social sciences, sensor networks in communications, functional networks in brain imaging, regulatory networks in genetics, and meshed surfaces in computer graphics. In many applications, such geometric data are large and complex (in the case of social networks, on the scale of billions), and are natural targets for machine learning techniques. In particular, we would like to use deep neural networks, which have recently proven to be powerful tools for a broad range of problems from computer vision, natural language processing, and audio analysis. However, these tools have been most successful on data with an underlying Euclidean or grid-like structure, and in cases where the invariances of these structures are built into networks used to model them. Geometric deep learning is an umbrella term for emerging techniques attempting to generalize (structured) deep neural models to non-Euclidean domains such as graphs and manifolds. The purpose of this paper is to overview different examples of geometric deep learning problems and present available solutions, key difficulties, applications, and future research directions in this nascent field.

I. INTRODUCTION

Deep learning has achieved major success on Euclidean, grid-like data by exploiting local statistical properties through deep neural networks. Geometric deep learning addresses the challenge of extending these methods to non-Euclidean domains, where familiar structures and operations such as convolution are not well defined.

  • I. INTRODUCTION: Deep learning builds complicated concepts hierarchically from simpler ones using multi-layer neural networks.Modern GPU computing and large training datasets have enabled networks with many layers and degrees of freedom.
  • I. INTRODUCTION: Deep neural networks succeed partly by leveraging statistical properties such as stationarity and compositionality through local statistics.These properties are present in natural images, video, and speech and have been formalized in convolutional neural networks.
  • I. INTRODUCTION: Non-Euclidean geometric data arise in applications including social networks and sensor networks, where characteristics can be modeled on graph vertices.The paper also identifies growing interest in applying learning to such data beyond speech, images, and video.
  • I. INTRODUCTION: Non-Euclidean domains lack global parameterization, common coordinates, vector-space structure, and shift-invariance, making convolution not well defined.These differences motivate translating key ingredients of successful deep learning methods to geometric domains.

II. GEOMETRIC LEARNING PROBLEMS

Geometric learning problems comprise characterizing non-Euclidean data structures and analyzing functions defined on such domains. The review focuses on learning functions on graphs and manifolds, especially generalizing CNNs beyond Euclidean settings.

  • Problem classes: Geometric learning problems divide into structure characterization and analysis of functions defined on a given non-Euclidean domain.The two classes are related because domain structure constrains functions, while function properties convey information about the domain.
  • Structure of the domain: Manifold learning recovers lower-dimensional structure embedded in high-dimensional Euclidean data as an unsupervised nonlinear dimensionality-reduction problem.Many methods first construct an affinity structure and then use it to recover the underlying geometry.
  • Data on a domain: Function-analysis problems distinguish fixed domains, such as social graphs carrying time-dependent signals, from multiple domains, such as shapes modeled as manifolds.Fixed-domain problems support graph signal-processing operations, whereas multiple-shape problems motivate convolution generalizations using local charting.
  • Review focus: The review’s geometric deep learning paradigms differ primarily in how convolution-like operations are formulated on graphs and manifolds.The paper contrasts spectral definitions based on the Convolution Theorem with spatial definitions based on template matching.
  • Scope and organization: The paper surveys geometric deep learning applications in network analysis, particle physics, recommender systems, computer vision, and graphics, then outlines challenges and future directions.It also introduces differential geometry and graph theory in a common, accessible overview for the signal-processing community.

III. DEEP LEARNING ON EUCLIDEAN DOMAINS

This section explains how CNNs exploit Euclidean-domain priors—translation invariance or equivariance, stability to local deformations, and multiscale structure—to build hierarchical representations while avoiding dimensionality-related learning complexity.

  • Geometric priors: CNNs encode translation invariance for classification and translation equivariance when outputs retain a translation action, matching the task’s required behavior.For invariant tasks, y(T_vf)=y(f); for equivariant tasks, y(T_vf)=T_vy(f).
  • Geometric priors: Stability to local deformations allows long-range image dependencies to be captured through downsampled, multiscale local interactions.Demodulated localized filter responses can be downsampled without losing approximation power, supporting hierarchical models with progressively reduced spatial resolution.
  • Convolutional neural networks: CNNs implement these priors using compact-support convolutions, point-wise nonlinearities, and optional permutation-invariant pooling over local neighborhoods.Pooling choices include average-, energy-, and max-pooling for p=1, 2, and ∞, respectively.
  • Convolutional neural networks: A CNN composes convolutional and pooling layers into a hierarchical representation whose outputs are invariant or covariant depending on whether pooling reduces spatial resolution.The network parameters are the filter coefficients across its layers.
  • Learning complexity: CNN geometric priors avoid the curse of dimensionality: each layer uses a constant number of linear-operator parameters, while depth grows as O(log n).The constant parameter count is independent of image size n, the number of pixels.

IV. THE GEOMETRY OF MANIFOLDS AND GRAPHS

The section introduces manifolds and graphs as non-Euclidean domains for geometric deep learning, emphasizing their shared structural characteristics. It explains manifold geometry and calculus through local tangent spaces, then discusses the challenges of discretizing sampled manifolds.

  • Manifolds: Manifolds are spaces that are locally Euclidean, and a Riemannian metric enables local measurements of angles, distances, and volumes.A manifold equipped with such a metric is called a Riemannian manifold.
  • Manifolds: Isometries preserve a manifold’s metric structure and intrinsic quantities, whereas properties depending on its Euclidean realization are extrinsic.This distinction separates geometry experienced within the surface from the viewpoint of an embedding space.
  • Calculus on manifolds: Because manifolds lack a vector-space structure, differential calculus must work locally in tangent spaces rather than use expressions such as f(x+dx).The differential acts on tangent vectors, which represent infinitesimal displacements around each point.
  • Calculus on manifolds: Intrinsic gradient, divergence, and Laplacian operators extend familiar calculus to manifolds and support geometric interpretations of change, flow, and smoothness.The Laplacian compares a function’s value at a point with its local average and is linked to Dirichlet energy.
  • Discrete manifolds: A graph-based discretization may fail to capture the continuous manifold geometry, since its graph Laplacian typically does not converge to the continuous Laplacian as sampling density increases.Geometrically consistent discretization requires additional face structure representing the manifold as a polyhedral surface.
  • Discrete manifolds: When only sampled points are available, reconstructing a manifold discretization is a difficult meshing problem, while manifold learning commonly uses graphs to capture local affinities.These settings require approximating the underlying manifold rather than directly operating on its full continuous representation.

V. SPECTRAL METHODS

Spectral methods generalize CNN convolutions on fixed graphs by using operators that commute with the graph Laplacian and therefore act in its eigenbasis. Their main limitation is that spectral filters are basis-dependent, restricting transfer across domains, although spectral truncation supports coarsening and pooling.

  • Spectral convolution: Spectral graph convolutions restrict linear operators to those commuting with the graph Laplacian, thereby operating on its eigenvector spectrum.The graph Laplacian eigenvectors define the frequency-domain representation used to generalize convolutional architectures.
  • Spectral convolution: A spectral layer maps graph signals through diagonal spectral multipliers, retains the first k eigenvectors, and applies a vertex-wise nonlinearity.The input and output signals are represented on graph vertices, while the spectral multipliers define the frequency-domain filter.
  • Spectral truncation: Typically, k ≪ n because the leading Laplacian eigenvectors capture the graph’s smooth structure and determine the practical cutoff frequency.The required cutoff depends on the graph’s intrinsic regularity and the sample size.
  • Limitations: Spectral filters cannot generally transfer between domains because their coefficients depend on the domain-specific Fourier or Laplacian basis.Applying a filter learned in basis Φk to another domain with basis Ψk can produce a very different result, even for nearly-isometric domains.
  • Pooling and efficiency: Dropping the last part of the Laplacian spectrum provides spatial subsampling and pooling, while combining spectral layers with graph coarsening can yield O(log n) total trainable parameters.The spectral construction also interprets deeper spatial filters as low frequency through interpolation.

VI. SPECTRUM-FREE METHODS

Spectrum-free methods represent graph filters as polynomials of the Laplacian, avoiding explicit spectral multipliers and eigenvectors while yielding localized r-hop operations. ChebNet and GCN are efficient spatial filtering methods, and broader GNNs learn nonlinear, task-specific diffusion operators from local graph interactions.

  • Polynomial filters: Polynomial Laplacian filters replace explicit spectral multipliers with an expansion whose coefficients determine the filter response on Laplacian eigenvalues.The filter matrices are diagonal functions of the eigenvalues, parameterized by an r-dimensional coefficient vector.
  • Polynomial filters: Linear combinations of Laplacian powers act as diffusion operators restricted to r-hop neighborhoods, making the resulting filters automatically localized.The jth Laplacian power reaches at most j hops because the Laplacian itself operates on 1-hop neighborhoods.
  • ChebNet and GCN: ChebNet computes order r−1 Chebyshev filters through a Laplacian recurrence in O(rn) operations without explicitly computing Laplacian eigenvectors.The Laplacian eigenvalues are rescaled from [0, λn] to [−1, 1] for the Chebyshev basis.
  • ChebNet and GCN: GCN simplifies ChebNet by setting r = 2 and λn ≈2, then constraining the filter coefficients to obtain a single-parameter filter.Repeated application can be numerically unstable because the relevant eigenvalues lie in [0, 2], motivating renormalization.
  • General GNN framework: GNNs generalize these constructions by learning local graph filters and nonlinear, task-specific diffusion operators that can be stacked with graph pooling.ChebNet and GCN can be viewed as particular GNN instances, while layerwise communication remains local to vertex neighborhoods.

VII. CHARTING-BASED METHODS

Charting-based methods define localized spatial convolutions on graphs and manifolds by constructing position-dependent patches in local intrinsic coordinates. Geodesic CNNs, Anisotropic CNNs, and MoNet differ in how they define weighting functions, with MoNet learning both filters and patch operators.

  • Pooling across domains: Multiple domains also lack an immediate common spatial pooling operation because point counts and ordering vary, motivating aggregation of point-wise features into a single vector.Mean or covariance statistics are examples of such aggregation.
  • Motivation: Non-Euclidean domains lack shift-invariance and meaningful global coordinates, so local patches must be position-dependent and represented in intrinsic coordinate systems.Weighting functions localized near each point specify the patch operator used for spatial convolution.
  • Geodesic CNN: Geodesic CNN constructs two-dimensional polar patches from intrinsic radial distance and angular coordinates defined by rays at equi-spaced angles.Gaussian products over radial and angular bins provide the localized weighting functions.
  • Anisotropic CNN: Anisotropic CNN uses direction-dependent heat kernels whose elongation, orientation, and scale are controlled by α, θ, and t.The anisotropic conductivity tensor generalizes isotropic diffusion, and the resulting elongated rotated blobs serve as patch weights.
  • Mixture model network (MoNet): MoNet applies learned Gaussian kernels to local pseudo-coordinates, learning both filter parameters and patch operators.Its learned covariance matrices and mean vectors provide additional degrees of freedom, and the approach generalizes Euclidean, Geodesic, and Anisotropic CNNs.

VIII. COMBINED SPATIAL/SPECTRAL METHODS

Combined spatial/spectral methods localize frequency analysis while retaining spatial information, addressing the spatial-localization limitation of classical Fourier analysis. On non-Euclidean domains, these methods include intrinsic windowed Fourier transforms, wavelet decompositions, and LSCNN patch operators.

  • Windowed Fourier transform: The Windowed Fourier Transform addresses classical Fourier analysis’s lack of spatial localization by analyzing frequency within a localized window g(x).WFT is also known as the short-time Fourier transform or spectrogram.
  • Windowed Fourier transform: WFT depends on spatial location x and modulation frequency ω, while the window g controls the tradeoff between spatial and frequency localization.Wider windows provide better frequency resolution, and WFT can be interpreted through translated and modulated window atoms.
  • Windowed Fourier transform: Generalizing WFT to non-Euclidean domains requires translation and modulation operators; modulation uses Laplacian eigenfunctions, while translation can be defined spectrally by convolution with a delta function.Translation is otherwise not well-defined because non-Euclidean domains lack shift-invariance.
  • Wavelets: Wavelet decompositions replace frequency with scale and seek stable linear decompositions whose atoms are localized in both space and frequency.Graph wavelet methods include Haar constructions, learned sparse-reconstruction decompositions, and deep wavelet scattering transforms.
  • Localized Spectral CNN (LSCNN): LSCNN uses WFT-based patch operators on manifolds and point clouds, applying learnable spectral multipliers to extract meaningful features.The WFT expresses a function around a point in the spectral domain as Dj(x)f = (Sf)(x, j).

IX. APPLICATIONS

Geometric deep learning is applied to network analysis, recommender systems, and 3D computer vision and graphics. Applications include citation-paper classification, spectral ranking and community detection, geometric matrix completion, and processing 3D geometric data.

  • Network analysis: Graph eigenvalue problems support network ranking and community detection, including graph partitioning via the Fiedler vector and page ranking via PageRank.The Fiedler vector corresponds to the smallest non-trivial Laplacian eigenvalue, while PageRank uses a modified Laplacian operator.
  • Network analysis: The CORA citation network contains 2708 paper vertices, 5429 citation edges, 1433-dimensional features, and seven classes; a spectral CNN achieved 81.6% classification accuracy.The network was treated as undirected for this application.
  • Recommender systems: Geometric matrix completion models recommender systems using user and item graphs to represent similarity and make matrix-value smoothness meaningful.This setting was shown beneficial for recommender-system performance.
  • Recommender systems: Monti et al. combine a Multi-Graph CNN and recurrent neural network, applying multi-graph convolution to score matrices over distinct user and item graphs.The multi-graph convolution generalizes standard two-dimensional image convolution to row and column domains with different graphs.
  • Computer vision and graphics: Computer vision increasingly targets 3D geometric data enabled by affordable range sensors, with image-based methods applied as range images or rasterized volumes.Examples of range-sensing technology include Microsoft Kinect and Intel RealSense.

FILTER

The section contrasts non-intrinsic Euclidean processing, which makes deformation invariance difficult, with intrinsic geometric models that build isometric-deformation invariance into convolutional filters. It also highlights that useful features depend on the task and that geometric methods extend to particle systems, molecules, and brain imaging.

  • 3D shape analysis: Geometric CNN filters operate intrinsically on surfaces and are deformation-invariant by construction.This contrasts with classical CNNs that treat a 3D shape as a Euclidean object.
  • 3D shape analysis: Euclidean representations vary with pose and deformation, making deformation invariance require complex models and huge training sets.The difficulty arises from the many degrees of freedom involved in describing non-rigid deformations.
  • 3D shape analysis: Feature requirements differ by task: correspondence favors invariance across a shape class, whereas retrieval requires shape-specific descriptors.Hand-crafting features for each application is described as challenging.
  • 3D shape analysis: Intrinsic deep neural networks automatically encode invariance to isometric deformations and learn residual deviations from the isometric model.This reduces the degrees of freedom needed to describe the invariance class.
  • Particle physics and Chemistry: Particle systems can be represented as graphs whose edge weights encode similarity-kernel priors, enabling graph neural networks for event classification, energy regression, and anomaly detection.This representation uses particle-specific information and phase-space locations.
  • Particle physics and Chemistry: Molecule-property prediction can model atoms as graph vertices and chemical bonds as edges, providing an alternative to hand-crafted molecular descriptors.The passage identifies this as a problem in material and drug design.

X. OPEN PROBLEMS AND FUTURE DIRECTIONS

Geometric deep learning is emerging as a new field, but key difficulties remain in generalization, changing and directed domains, synthesis, and computation. Future research targets methods that address these challenges across geometric data.

  • Field emergence: Geometric deep learning is emerging across communities and application domains, with exciting new approaches and results expected in the coming years.The review characterizes the field’s emergence cautiously while highlighting current difficulties and future research directions.
  • Generalization: Generalizing geometric deep learning requires both non-Euclidean building blocks and transfer across domains, such as applying models learned on training shapes to unseen 3D shapes.Spectral convolution is domain-dependent, while spatial methods generalize across domains but face challenges constructing low-dimensional local graph coordinates.
  • Generalization: Constructing anisotropic diffusion on general graphs is an open direction because low-dimensional local spatial coordinates on graphs are difficult to define.Spatial methods support cross-domain generalization, but their local coordinate construction remains challenging.
  • Time-varying domains: Time-varying domains require tracking how structural changes affect signals, enabling applications such as abnormal activity detection in social or financial networks and dynamic-shape analysis.The domain can change dynamically, so fixed-domain assumptions no longer apply.
  • Directed graphs: Directed graphs remain challenging because nonsymmetric Laplacians lack orthogonal eigendecompositions, while treating citation networks as undirected can lose citation-direction information.Directed-graph methods must address spectral constructions that are not readily interpretable under nonsymmetric Laplacians.
  • Synthesis problems: Extending generative models to geometric data is promising, but synthesis must also reconstruct the underlying geometric structure.The review identifies data synthesis as an important complement to analysis problems on non-Euclidean domains.
  • Computation: Geometric deep learning faces computational limitations because existing frameworks target regularly structured grids that efficiently use modern GPU hardware, unlike most geometric data.The lack of grid structure in geometric data undermines a major source of deep-learning computational efficiency.
Loading 1611.08097v2…