Global graph curvature
Recently, non-Euclidean spaces became popular for embedding structured data. However, determining suitable geometry and, in particular, curvature for a given dataset is still an open problem. In this paper, we define a notion of global graph curvature, specifically catered to the problem of embedding graphs, and analyze the problem of estimating this curvature using only graph-based characteristics (without actual graph embedding). We show that optimal curvature essentially depends on dimensionality of the embedding space and loss function one aims to minimize via embedding. We review the existing notions of local curvature (e.g., Ollivier-Ricci curvature) and analyze their properties theoretically and empirically. In particular, we show that such curvatures are often unable to properly estimate the global one. Hence, we propose a new estimator of global graph curvature specifically designed for zero-one loss function.
Code (0)
등록된 구현이 없습니다.
Tasks
Graph EmbeddingSimilar Papers 제목 키워드 기반
Continuum Limits of Ollivier's Ricci Curvature on data clouds: pointwise consistency and global lower bounds
Let $M$ denote a low-dimensional manifold embedded in Euclidean space and let ${X}= \{ x_1, \dots, x_n \}$ be a collection of points uniformly sampled from it. We study the relationship between the curvature of a random …
Probing Graph Neural Network Activation Patterns Through Graph Topology
Curvature notions on graphs provide a theoretical description of graph topology, highlighting bottlenecks and denser connected regions. Artifacts of the message passing paradigm in Graph Neural Networks, such as oversmoo…
Graph Neural NetworkGraph LearningCurvature-Aware PCA with Geodesic Tangent Space Aggregation for Semi-Supervised Learning
Principal Component Analysis (PCA) is a fundamental tool for representation learning, but its global linear formulation fails to capture the structure of data supported on curved manifolds. In contrast, manifold learning…
Dimensionality ReductionRepresentation LearningA Geometric Approach for Real-time Monitoring of Dynamic Large Scale Graphs: AS-level graphs illustrated
The monitoring of large dynamic networks is a major chal- lenge for a wide range of application. The complexity stems from properties of the underlying graphs, in which slight local changes can lead to sizable variations…
Local-Curvature-Aware Knowledge Graph Embedding: An Extended Ricci Flow Approach
Knowledge graph embedding (KGE) relies on the geometry of the embedding space to encode semantic and structural relations. Existing methods place all entities on one homogeneous manifold, Euclidean, spherical, hyperbolic…
Knowledge Graph EmbeddingNode ClassificationLink Prediction