Ollivier-Ricci Curvature for Hypergraphs: A Unified Framework

• URL: http://arxiv.org/abs/2210.12048v3
• Date: Thu, 6 Apr 2023 16:54:48 GMT
• Title: Ollivier-Ricci Curvature for Hypergraphs: A Unified Framework
• Authors: Corinna Coupette and Sebastian Dalleiger and Bastian Rieck
• Abstract summary: We develop ORCHID, a flexible framework generalizing Ollivier-Ricci curvature to hypergraphs. We show that ORCHID curvatures are both scalable and useful to perform a variety of hypergraph tasks in practice.
• Score: 15.447966950703952
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Bridging geometry and topology, curvature is a powerful and expressive invariant. While the utility of curvature has been theoretically and empirically confirmed in the context of manifolds and graphs, its generalization to the emerging domain of hypergraphs has remained largely unexplored. On graphs, the Ollivier-Ricci curvature measures differences between random walks via Wasserstein distances, thus grounding a geometric concept in ideas from probability theory and optimal transport. We develop ORCHID, a flexible framework generalizing Ollivier-Ricci curvature to hypergraphs, and prove that the resulting curvatures have favorable theoretical properties. Through extensive experiments on synthetic and real-world hypergraphs from different domains, we demonstrate that ORCHID curvatures are both scalable and useful to perform a variety of hypergraph tasks in practice.

Related papers

• Hypergraphs as Weighted Directed Self-Looped Graphs: Spectral Properties, Clustering, Cheeger Inequality [40.215737469808026]
  Hypergraphs arise when studying group relations and have been widely used in the field of machine learning. There has not been a unified formulation of hypergraphs, yet the recently proposed edge-dependent Rayleigh weights (EDVW) modeling is one of the most generalized modeling methods of hypergraphs. We propose our definitions of hypergraph Quotient, NCut, boundary/cut, volume, and conductance, which are consistent with the corresponding definitions on graphs. Then, we prove that the normalized hypergraph Laplacian is associated with the NCut value, which inspires our HyperClus-G algorithm for spectral clustering
  arXiv  Detail & Related papers  (2024-10-23T05:16:48Z)
• Accelerated Evaluation of Ollivier-Ricci Curvature Lower Bounds: Bridging Theory and Computation [0.0]
  Curvature serves as a potent and descriptive invariant, with its efficacy validated both theoretically and practically within graph theory. We employ a definition of generalized Ricci curvature proposed by Ollivier, which Lin and Yau later adapted to graph theory, known as Ollivier-Ricci curvature (ORC) ORC measures curvature using the Wasserstein distance, thereby integrating geometric concepts with probability theory and optimal transport.
  arXiv  Detail & Related papers  (2024-05-22T02:44:46Z)
• Revealing Decurve Flows for Generalized Graph Propagation [108.80758541147418]
  This study addresses the limitations of the traditional analysis of message-passing, central to graph learning, by defining em textbfgeneralized propagation with directed and weighted graphs. We include a preliminary exploration of learned propagation patterns in datasets, a first in the field.
  arXiv  Detail & Related papers  (2024-02-13T14:13:17Z)
• DeepRicci: Self-supervised Graph Structure-Feature Co-Refinement for Alleviating Over-squashing [72.70197960100677]
  Graph Structure Learning (GSL) plays an important role in boosting Graph Neural Networks (GNNs) with a refined graph. GSL solutions usually focus on structure refinement with task-specific supervision (i.e., node classification) or overlook the inherent weakness of GNNs themselves. We propose to study self-supervised graph structure-feature co-refinement for effectively alleviating the issue of over-squashing in typical GNNs.
  arXiv  Detail & Related papers  (2024-01-23T14:06:08Z)
• Alignment and Outer Shell Isotropy for Hyperbolic Graph Contrastive Learning [69.6810940330906]
  We propose a novel contrastive learning framework to learn high-quality graph embedding. Specifically, we design the alignment metric that effectively captures the hierarchical data-invariant information. We show that in the hyperbolic space one has to address the leaf- and height-level uniformity which are related to properties of trees.
  arXiv  Detail & Related papers  (2023-10-27T15:31:42Z)
• Curvature-Independent Last-Iterate Convergence for Games on Riemannian Manifolds [77.4346324549323]
  We show that a step size agnostic to the curvature of the manifold achieves a curvature-independent and linear last-iterate convergence rate. To the best of our knowledge, the possibility of curvature-independent rates and/or last-iterate convergence has not been considered before.
  arXiv  Detail & Related papers  (2023-06-29T01:20:44Z)
• Revisiting Over-smoothing and Over-squashing Using Ollivier-Ricci Curvature [11.592567773739411]
  Our study reveals the key connection between the local graph geometry and the occurrence of over-smoothing and over-squashing. We propose the Batch Ollivier-Ricci Flow, a novel rewiring algorithm capable of simultaneously addressing both over-smoothing and over-squashing.
  arXiv  Detail & Related papers  (2022-11-28T21:21:31Z)
• Hypergraph Convolutional Networks via Equivalency between Hypergraphs and Undirected Graphs [59.71134113268709]
  We present General Hypergraph Spectral Convolution(GHSC), a general learning framework that can handle EDVW and EIVW hypergraphs. In this paper, we show that the proposed framework can achieve state-of-the-art performance. Experiments from various domains including social network analysis, visual objective classification, protein learning demonstrate that the proposed framework can achieve state-of-the-art performance.
  arXiv  Detail & Related papers  (2022-03-31T10:46:47Z)
• Invariance Principle Meets Out-of-Distribution Generalization on Graphs [66.04137805277632]
  Complex nature of graphs thwarts the adoption of the invariance principle for OOD generalization. domain or environment partitions, which are often required by OOD methods, can be expensive to obtain for graphs. We propose a novel framework to explicitly model this process using a contrastive strategy.
  arXiv  Detail & Related papers  (2022-02-11T04:38:39Z)
• Heterogeneous manifolds for curvature-aware graph embedding [6.3351090376024155]
  Graph embeddings are used in a broad range of Graph ML applications. The quality of such embeddings crucially depends on whether the geometry of the space matches that of the graph.
  arXiv  Detail & Related papers  (2022-02-02T18:18:35Z)
• Computationally Tractable Riemannian Manifolds for Graph Embeddings [10.420394952839242]
  We show how to learn and optimize graph embeddings in certain curved Riemannian spaces. Our results serve as new evidence for the benefits of non-Euclidean embeddings in machine learning pipelines.
  arXiv  Detail & Related papers  (2020-02-20T10:55:47Z)

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.