Curvature Regularization to Prevent Distortion in Graph Embedding

• URL: http://arxiv.org/abs/2011.14211v1
• Date: Sat, 28 Nov 2020 20:16:24 GMT
• Title: Curvature Regularization to Prevent Distortion in Graph Embedding
• Authors: Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Chunxu Zhang, Bo Yang
• Abstract summary: We argue an important but neglected problem about proximity-preserving strategy. Graph topology patterns, while preserved well into an embedding manifold, may distort in the ambient embedding Euclidean space. We present a novel angle-based sectional curvature, termed ABS curvature, and accordingly three kinds of curvature regularization.
• Score: 15.383135890096462
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recent research on graph embedding has achieved success in various applications. Most graph embedding methods preserve the proximity in a graph into a manifold in an embedding space. We argue an important but neglected problem about this proximity-preserving strategy: Graph topology patterns, while preserved well into an embedding manifold by preserving proximity, may distort in the ambient embedding Euclidean space, and hence to detect them becomes difficult for machine learning models. To address the problem, we propose curvature regularization, to enforce flatness for embedding manifolds, thereby preventing the distortion. We present a novel angle-based sectional curvature, termed ABS curvature, and accordingly three kinds of curvature regularization to induce flat embedding manifolds during graph embedding. We integrate curvature regularization into five popular proximity-preserving embedding methods, and empirical results in two applications show significant improvements on a wide range of open graph datasets.

Related papers

• Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification [81.06278257153835]
  We propose a graph rewiring method that balances structural bottleneck reduction and graph property preservation.<n>Our method generates graphs with enhanced connectivity while maintaining sparsity and largely preserving the original graph spectrum.
  arXiv  Detail & Related papers  (2025-06-19T08:01:00Z)
• CurvGAD: Leveraging Curvature for Enhanced Graph Anomaly Detection [23.643189106137008]
  We propose CurvGAD - a mixed-curvature graph autoencoder that introduces the notion of curvature-based geometric anomalies.<n>CurvGAD introduces two parallel pipelines for enhanced anomaly interpretability.<n>Experiments over 10 real-world datasets demonstrate an improvement of up to 6.5% over state-of-the-art GAD methods.
  arXiv  Detail & Related papers  (2025-02-12T17:49:46Z)
• Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
  This paper proposes a novel Deep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE) for attributed graph data. The proposed method surpasses state-of-the-art baseline algorithms by a significant margin on different downstream tasks across popular datasets.
  arXiv  Detail & Related papers  (2024-01-12T17:57:07Z)
• Improving embedding of graphs with missing data by soft manifolds [51.425411400683565]
  The reliability of graph embeddings depends on how much the geometry of the continuous space matches the graph structure. We introduce a new class of manifold, named soft manifold, that can solve this situation. Using soft manifold for graph embedding, we can provide continuous spaces to pursue any task in data analysis over complex datasets.
  arXiv  Detail & Related papers  (2023-11-29T12:48:33Z)
• Mitigating Over-Smoothing and Over-Squashing using Augmentations of Forman-Ricci Curvature [1.1126342180866644]
  We propose a rewiring technique based on Augmented Forman-Ricci curvature (AFRC), a scalable curvature notation. We prove that AFRC effectively characterizes over-smoothing and over-squashing effects in message-passing GNNs.
  arXiv  Detail & Related papers  (2023-09-17T21:43:18Z)
• Curve Your Attention: Mixed-Curvature Transformers for Graph Representation Learning [77.1421343649344]
  We propose a generalization of Transformers towards operating entirely on the product of constant curvature spaces. We also provide a kernelized approach to non-Euclidean attention, which enables our model to run in time and memory cost linear to the number of nodes and edges.
  arXiv  Detail & Related papers  (2023-09-08T02:44:37Z)
• Contrastive Graph Clustering in Curvature Spaces [74.03252813800334]
  We present a novel end-to-end contrastive graph clustering model named CONGREGATE. To support geometric clustering, we construct a theoretically grounded Heterogeneous Curvature Space. We then train the graph clusters by an augmentation-free reweighted contrastive approach.
  arXiv  Detail & Related papers  (2023-05-05T14:04:52Z)
• Are Gradients on Graph Structure Reliable in Gray-box Attacks? [56.346504691615934]
  Previous gray-box attackers employ gradients from the surrogate model to locate the vulnerable edges to perturb the graph structure. In this paper, we discuss and analyze the errors caused by the unreliability of the structural gradients. We propose a novel attack model with methods to reduce the errors inside the structural gradients.
  arXiv  Detail & Related papers  (2022-08-07T06:43:32Z)
• 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)
• Multilayer Graph Clustering with Optimized Node Embedding [70.1053472751897]
  multilayer graph clustering aims at dividing the graph nodes into categories or communities. We propose a clustering-friendly embedding of the layers of a given multilayer graph. Experiments show that our method leads to a significant improvement.
  arXiv  Detail & Related papers  (2021-03-30T17:36:40Z)
• Learning Linear Non-Gaussian Graphical Models with Multidirected Edges [8.71151886950158]
  We propose a new method to learn the underlying acyclic mixed graph of a linear non-Gaussian structural equation model given observational data. We show that one can augment the hidden variable structure of the recovered model by learning em multidirected edges rather than only directed and bidirected ones.
  arXiv  Detail & Related papers  (2020-10-11T18:10:15Z)
• 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.