Forman‐Ricci Curvature Coarse Geometry Lifting (Graph to Hypergraph)

Motivation This is a novel lifting that first identifies a network's structure-preserving, coarse geometry, i.e. its backbones, which lend themselves specifically to model information flows across wide areas of the network via hyperedges. To this end, we hope our approach may also contribute a topological remedy to the problem of information distortion in message passing across long-distances and graph bottlenecks, a phenomenom known as “over-squashing“ in graph learning [1]. To identify this coarse geometry we apply Forman-Ricci curvature to the original graph.

Background In general, curvature is a geometric property that describes the local shape of an object. In the graph, an edge with positive curvature represents an edge within a cluster, while a negative curvature edge tents to be a bridge within clusters. Forman-Ricci curvature defines an edge-based network characteristic that reveals properties of a graph's community structure [2]. In particular high absolute Forman-Ricci curvature exhibits a network's backbone, a coarse, structure preserving graph geometry that forms connections between major communities, most suitable to be represented as hyperedges to model information flows between clusters across large distances in the network. In addition, Forman-Ricci curvature was found to be especially useful for network analysis since its intuitive notion allows for efficient computation that scales to large networks sizes, in contrast to measures such as Ollivier-Ricci curvature [3].

Network representations of relational data $G = {V (G), E(G)}$ form regular, 1-dimensional cell complexes, in which case the following curvature function can be defined [2]:

${\rm Ric_F}(e) = \omega (e) \left( \frac{\omega (v_1)}{\omega (e)} + \frac{\omega (v_2)}{\omega (e)} - \sum_{\substack{e_{v_1}\ \sim\ e \ \ e_{v_2}\ \sim\ e}} \left[\frac{\omega (v_1)}{\sqrt{\omega (e) \omega (e_{v_1})}} + \frac{\omega (v_2)}{\sqrt{\omega (e) \omega (e_{v_2})}} \right] \right),.$

The function is defined on each edge $e = (v_1, v_2) \in E(G)$ of the network, connecting vertices $v_1, v_2 \in V (G)$; $\omega$ denotes the weights of edges and vertices. Our approach is applicable to both weighted and unweighted networks. In case of unweighted networks all weights in the above equation reduce to 1, i.e. $\omega (e) = \omega (v_1) = \omega (v_2) = 1$.

Method

Our approach works as follows: (1) calculate the Forman-Ricci curvature over the edges of a graph. (2) either define an absolute threshold on Forman-Ricci curvature or, from the given distribution of curvature weights, provide a quantile for automatic, network-dependent threshold estimation for backbone extraction. (3) prune the curvature graph using the provided or automatically estimated threshold. (4) identify and add remaining network backbone geometries as hyperedges to lift the original graph. (Note that while our exemplary figure only showcases a single backbone, in practise the number of backbones depends on the thresholds as well as graph geometry.)

Submission by Team PerelynAI Max Schattauer (@max-perelyn), Liliya Imasheva (@liliya-imasheva) , Dominik Filipiak (@DominikFilipiak), Michael Banf (@mbanf)

From https://github.com/pyt-team/challenge-icml-2024/pull/33