Capturing Graphs with Hypo-Elliptic Diffusions

• URL: http://arxiv.org/abs/2205.14092v1
• Date: Fri, 27 May 2022 16:47:34 GMT
• Title: Capturing Graphs with Hypo-Elliptic Diffusions
• Authors: Csaba Toth, Darrick Lee, Celia Hacker, Harald Oberhauser
• Abstract summary: We show that the distribution of random walks evolves according to a diffusion equation defined using the graph Laplacian. This results in a novel tensor-valued graph operator, which we call the hypo-elliptic graph Laplacian. We show that this method competes with graph transformers on datasets requiring long-range reasoning but scales only linearly in the number of edges.
• Score: 7.704064306361941
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Convolutional layers within graph neural networks operate by aggregating information about local neighbourhood structures; one common way to encode such substructures is through random walks. The distribution of these random walks evolves according to a diffusion equation defined using the graph Laplacian. We extend this approach by leveraging classic mathematical results about hypo-elliptic diffusions. This results in a novel tensor-valued graph operator, which we call the hypo-elliptic graph Laplacian. We provide theoretical guarantees and efficient low-rank approximation algorithms. In particular, this gives a structured approach to capture long-range dependencies on graphs that is robust to pooling. Besides the attractive theoretical properties, our experiments show that this method competes with graph transformers on datasets requiring long-range reasoning but scales only linearly in the number of edges as opposed to quadratically in nodes.

Related papers

• Graph Generation via Spectral Diffusion [51.60814773299899]
  We present GRASP, a novel graph generative model based on 1) the spectral decomposition of the graph Laplacian matrix and 2) a diffusion process. Specifically, we propose to use a denoising model to sample eigenvectors and eigenvalues from which we can reconstruct the graph Laplacian and adjacency matrix. Our permutation invariant model can also handle node features by concatenating them to the eigenvectors of each node.
  arXiv  Detail & Related papers  (2024-02-29T09:26:46Z)
• Learning to Approximate Adaptive Kernel Convolution on Graphs [4.434835769977399]
  We propose a diffusion learning framework, where the range of feature aggregation is controlled by the scale of a diffusion kernel. Our model is tested on various standard for node-wise classification for the state-of-the-art datasets performance. It is also validated on a real-world brain network data for graph classifications to demonstrate its practicality for Alzheimer classification.
  arXiv  Detail & Related papers  (2024-01-22T10:57:11Z)
• Advective Diffusion Transformers for Topological Generalization in Graph Learning [69.2894350228753]
  We show how graph diffusion equations extrapolate and generalize in the presence of varying graph topologies. We propose a novel graph encoder backbone, Advective Diffusion Transformer (ADiT), inspired by advective graph diffusion equations.
  arXiv  Detail & Related papers  (2023-10-10T08:40:47Z)
• A Fractional Graph Laplacian Approach to Oversmoothing [15.795926248847026]
  We generalize the concept of oversmoothing from undirected to directed graphs. We propose fractional graph Laplacian neural ODEs, which describe non-local dynamics. Our method is more flexible with respect to the convergence of the graph's Dirichlet energy, thereby mitigating oversmoothing.
  arXiv  Detail & Related papers  (2023-05-22T14:52:33Z)
• Graphon Pooling for Reducing Dimensionality of Signals and Convolutional Operators on Graphs [131.53471236405628]
  We present three methods that exploit the induced graphon representation of graphs and graph signals on partitions of [0, 1]2 in the graphon space. We prove that those low dimensional representations constitute a convergent sequence of graphs and graph signals. We observe that graphon pooling performs significantly better than other approaches proposed in the literature when dimensionality reduction ratios between layers are large.
  arXiv  Detail & Related papers  (2022-12-15T22:11:34Z)
• DiGress: Discrete Denoising diffusion for graph generation [79.13904438217592]
  DiGress is a discrete denoising diffusion model for generating graphs with categorical node and edge attributes. It achieves state-of-the-art performance on molecular and non-molecular datasets, with up to 3x validity improvement. It is also the first model to scale to the large GuacaMol dataset containing 1.3M drug-like molecules.
  arXiv  Detail & Related papers  (2022-09-29T12:55:03Z)
• Neural Sheaf Diffusion: A Topological Perspective on Heterophily and Oversmoothing in GNNs [16.88394293874848]
  We use cellular sheaf theory to show that the underlying geometry of the graph is deeply linked with the performance of GNNs. By considering a hierarchy of increasingly general sheaves, we study how the ability of the sheaf diffusion process to achieve linear separation of the classes in the infinite time limit expands. We prove that when the sheaf is non-trivial, discretised parametric diffusion processes have greater control than GNNs over their behaviour.
  arXiv  Detail & Related papers  (2022-02-09T17:25:02Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)
• Understanding Graph Neural Networks with Generalized Geometric Scattering Transforms [67.88675386638043]
  The scattering transform is a multilayered wavelet-based deep learning architecture that acts as a model of convolutional neural networks. We introduce windowed and non-windowed geometric scattering transforms for graphs based upon a very general class of asymmetric wavelets. We show that these asymmetric graph scattering transforms have many of the same theoretical guarantees as their symmetric counterparts.
  arXiv  Detail & Related papers  (2019-11-14T17:23:06Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.