PaperlayerView exact revision on arXiv

Source-linked AI summary

Geometric Flow enhanced Graph Coarsening

Chaoqun Fei, Guoxuan Li, Tinglve Zhou, Chuanqing Wang, Yangyang Li

arXiv:2609.14962v1cs.AI

TL;DR

Graph pooling methods often cluster nodes using coarse topology or node attributes, leaving local connection structure insufficiently represented. RicciPool reweights edges through Ollivier-Ricci flow before spectral clustering, and experiments report strong comparisons on several benchmark datasets, with a stated boundary for fully connected graphs.

  • Problem

    Graph pooling methods commonly use node attributes or coarse topology and can overlook local similarities and higher-order connections among neighboring nodes.

    Source: §I · p. 1

  • Method

    RicciPool uses Ollivier-Ricci curvature to iteratively reweight graph edges, then applies spectral clustering to learn a node assignment matrix for pooling.

    Source: §I · p. 2

  • Results

    RicciPool achieves the best performance among compared methods on D&D, PROTEINS, IMDB-B, and IMDB-M, and outperforms geometry-aware methods on most datasets except ENZYMES.

    Source: B. Classification Results · p. 8

  • Takeaways & Limitations

    Experiments indicate that curvature flow provides useful structural information for graph pooling compared with MinCutPool and StructPool across seven datasets.

    Source: B. Classification Results · p. 8

    In fully connected graphs with uniform edge weights and curvature, RicciPool cannot uncover a more compact latent structure, limiting its ability to enhance graph representations for high-level tasks.

    Source: §VI · p. 15

Abstract

from arXiv · show

Recently, researchers have proposed a graph pooling operation, akin to the pooling process in conventional convolutional neural networks (CNN), aimed at reducing the computation cost of Graph convolutional neural networks (GCNNs). While most GCNN-based methods treat graph pooling as a node clustering problem and propose learning a cluster assignment matrix, existing clustering-based pooling methods tend to focus solely on the rough topology information of graphs, neglecting the exploitation of higher-order mutual connections among neighbors. In terms of message passing on graph, the ease of information passing on edges reflects the closeness between neighboring nodes, which significantly relies on the interconnectivity among neighbors. In this study, we address this gap by considering such local connection information and introducing a novel graph pooling method named RicciPool. We introduce discrete graph curvature, particularly Ollivier-Ricci curvature, as a measure of higher-order connectivity around an edge. Subsequently, we construct an Ollivier-Ricci flow formula to reweigh edge weights, leveraging the crucial information provided by Ricci curvature, particularly vital for extracting clusters in graphs. Building upon this foundation, we utilize the spectral clustering technique to learn a new cluster assignment matrix. Experimental results on multiple bioinformatics protein datasets and social networks underscore the effectiveness of our proposed method.

I. Introduction

Graph pooling seeks to reduce graph size and computation, but common clustering approaches rely on coarse topology or node attributes and overlook local connection structure. RicciPool uses Ollivier-Ricci curvature to reweight edges before spectral clustering assigns nodes to clusters.

I. Introduction

  • Existing GCNN pooling methods often rely on node attributes or coarse topology, which can miss local similarities and distinctions among neighboring structures.Well-connected communities have overlapping neighborhoods and shortcuts, unlike hierarchically structured communities.Source: §I · p. 1

B. Discrete Graph Curvature

  • Ollivier-Ricci curvature measures local graph structure: positive values indicate dense, clique-like graphs, while negative values indicate sparse, tree-like graphs.The paper chooses it to investigate local geometry and the difficulty of message passing on edges.Source: §I · p. 2

I. Introduction

  • RicciPool iteratively adjusts edge weights using Ollivier-Ricci curvature, then applies spectral clustering to learn a structure-aware assignment matrix for pooling.The method focuses on high-positive-curvature connections and is proposed to preserve structural bottlenecks and global topology.Source: §I · p. 2

A. Graph Pooling in GNNs

  • Graph coarsening treats pooling as node clustering based on graph topology, but few methods explicitly distinguish different pairwise connection structures.Prior approaches include DiffPool, StructPool, and MinCutPool.Source: A. Graph Pooling in GNNs · p. 2

III. Preliminaries

  • A graph is represented by its node set, edge set, unweighted adjacency matrix, and node feature matrix.The preliminaries introduce these elements as the framework for the approach.Source: §III · p. 3

A. Graph Convolutional Neural Networks

  • GCNNs learn node or graph embeddings from adjacency and feature matrices using spectral or spatial methods; spatial methods aggregate neighbor representations.The paper uses the spatial version for its basic convolution operation.Source: A. Graph Convolutional Neural Networks · p. 3

B. Graph Pooling

Graph pooling learns a node assignment that produces a smaller graph while seeking to preserve its topology. This paper adapts Ricci flow to graph edge weights and uses the updated weights for clustering and pooling.

B. Graph Pooling

  • A graph pooling operator learns an assignment matrix P to produce pooled node features and adjacency, with the new adjacency intended to preserve the original graph's global topology.The pooled graph has K nodes for an original graph with N nodes, typically with N ≥ K.Source: B. Graph Pooling · p. 3

C. Ricci Flow

  • The proposed Ollivier-Ricci flow treats edge weights as graph distances, diminishing weights on positive-curvature dense structures and enlarging them on negative-curvature sparse structures.This adapts the geometric evolution of Ricci flow to identify clique-like and tree-like subgraphs.Source: C. Ricci Flow · p. 3

IV. Proposed Method

  • RicciPool iteratively updates edge weights from curvature, partitions nodes into K clusters, then uses GCNN features and a learned assignment matrix to condense the graph.The resulting pooling layer produces a more compact graph.Source: §IV · p. 3

A. Ollivier-Ricci Curvature

  • Ollivier-Ricci curvature is defined on an edge using the optimal transportation cost between probability distributions over the neighbors of its endpoint nodes.The curvature uses the Wasserstein distance and the shortest-path distance between the endpoints.Source: A. Ollivier-Ricci Curvature · p. 4

B. Ollivier-Ricci Flow

Ollivier-Ricci flow evolves graph edge weights using curvature and shortest-path distances. The process expands negative-curvature edges, contracts positive-curvature edges, and stops when edge curvatures stabilize.

B. Ollivier-Ricci Flow

  • The distance d is the minimum total edge weight over paths connecting two vertices, inducing a shortest-path metric.It satisfies the triangle inequality.Source: B. Ollivier-Ricci Flow · p. 4
  • The flow starts from the unweighted adjacency matrix, with neighboring-node distances equal to their edge weights, and updates weights and curvature together.The update is restricted to curvature between neighboring nodes.Source: B. Ollivier-Ricci Flow · p. 4
  • The graph flow updates edge weights using Ollivier-Ricci curvature and shortest-path distance, expanding negative-curvature edges and shrinking positive-curvature edges.This evolution condenses clique-like connections and stretches tree-like connections, helping separate closely connected subgraphs.Source: B. Ollivier-Ricci Flow · p. 4
  • Flow iterations stop when each edge's curvature ceases to change or changes by less than threshold δ between consecutive iterations.The algorithm outputs the updated edge-weight matrix wR.Source: B. Ollivier-Ricci Flow · p. 4

C. Nodes Clustering

RicciPool learns graph clusters using spectral techniques and curvature-updated edge weights. Its assignment objective balances weighted and unweighted connections within and between clusters.

C. Nodes Clustering

  • The assignment objective minimizes intra-cluster edge weights while maximizing intra-cluster edge counts, and minimizes inter-cluster edge counts while maximizing inter-cluster edge weights.The authors formulate the assignment using spectral techniques based on the minCUT problem.Source: C. Nodes Clustering · pp. 4–5
  • Each node is constrained to exactly one cluster; a reciprocal constraint regularizes degree and edge-weight distributions to prevent extreme cases.The reformulation addresses a degenerate case in which a single-node cluster makes the minimum intra-cluster weight zero and the objective ill-posed.Source: C. Nodes Clustering · p. 6
  • A GCNN with a relaxed loss and softmax learns a probabilistic, near-optimal cluster assignment matrix for the normalized-cut problem.The normalized-cut clustering problem is NP-hard; the learned real-valued assignments can support deeper graph networks and downstream tasks.Source: C. Nodes Clustering · p. 6
  • RicciPool uses Ollivier-Ricci curvature to measure connectivity around edges and incorporates geometric information through an evolved edge-weight matrix.The matrix is obtained by iteratively updating the initial weight matrix.Source: C. Nodes Clustering · pp. 5–6

D. Graph Pooling via Node Clustering

RicciPool turns clusters into supernodes, producing pooled adjacency and feature matrices. Curvature flow reweights edges before spectral-style clustering, while the pooled graph retains topology and cluster features retain attribute information.

D. Graph Pooling via Node Clustering

  • Pooling aggregates the nodes in each of K clusters into K supernodes and produces a coarsened adjacency matrix and feature matrix.The pooled adjacency matrix is symmetric; its entries sum edge weights within or between clusters, while pooled features are assignment-weighted sums.Source: D. Graph Pooling via Node Clustering · p. 6
  • The pipeline iteratively applies Ollivier-Ricci flow to the initial adjacency matrix, learns assignments with a GCNN, then computes pooled adjacency and features.The assignments use the unsupervised loss, and pooling produces the next convolutional layer's inputs.Source: D. Graph Pooling via Node Clustering · pp. 6–7
  • The coarsened adjacency preserves global graph topology, while cluster embeddings retain geometric structure from the previous layer's attributes.Source: D. Graph Pooling via Node Clustering · p. 6
  • Ollivier-Ricci flow differentiates clique-like from tree-like subgraphs, whose structures may encode semantic information such as positive or negative node pairs.The authors state this information can provide additional unsupervised information for downstream tasks and enhance performance.Source: D. Graph Pooling via Node Clustering · p. 6

E. Computational Complexity Analysis

RicciPool's computational cost combines Ollivier-Ricci flow, GCNN training, and pooled-matrix computation. Curvature reweighting is offline preprocessing and may be expensive on highly dense graphs.

E. Computational Complexity Analysis

  • O(lN^4 log^2 N) is the stated total cost of l Ollivier-Ricci flow iterations.The passage gives O(N^4 log^2 N) for curvature computation in each iteration.Source: E. Computational Complexity Analysis · p. 7
  • O((lN log^2 N + m)N^3) is the stated total computational complexity of GCNN-based RicciPool.The estimate combines flow, m GCNN training iterations, and pooled adjacency and feature computation.Source: E. Computational Complexity Analysis · p. 7
  • Curvature computation is offline preprocessing that leaves GCNN architecture, training, and inference unchanged, but may become expensive on highly dense graphs.The authors describe the cost as more manageable on sparse or moderately connected graphs.Source: E. Computational Complexity Analysis · p. 7

B. Classification Results

RicciPool performs best among the compared methods on four datasets and consistently improves over MinCutPool and StructPool across all seven. Its gains are narrower on ENZYMES, COLLAB, and REDDIT-M-5K, with the latter two illustrating limits at extreme graph densities.

B. Classification Results

  • The evaluation compares 13 pooling methods on seven standard datasets using 10-fold cross-validation, with average accuracy and standard deviation reported.SPREADPOOL and MAGPOOL results are unavailable on REDDIT-M-5K because their computations could not be completed within a feasible timeframe on the shared platform.Source: B. Classification Results · p. 7
  • RicciPool performs best among compared methods on D&D, PROTEINS, IMDB-B, and IMDB-M, and improves over MinCutPool and StructPool on all seven datasets.The comparison uses the same framework, K = 32 clusters, and l = 5 flow iterations for RicciPool; results are ten-run averages.Source: Table II · p. 8, B. Classification Results · p. 8
  • RicciPool outperforms existing geometry-aware methods on most datasets except ENZYMES, where it still beats MinCutPool and StructPool.Its additional gain on ENZYMES is not sufficient to surpass the strongest geometry-based methods.Source: B. Classification Results · p. 8
  • Overly dense and overly sparse graphs may weaken RicciPool; it is more suitable for moderate connectivity and distinct cluster structures.COLLAB has average density ≈0.91 and mostly positive edge curvature, while REDDIT-M-5K has average density ≈0.0046 and many negatively curved edges; in both, consistent weight adjustments limit discrimination.Source: B. Classification Results · p. 8

C. Ablation Study and Analysis

RicciPool performs strongly across pooling rates and datasets, while its results depend on flow iterations and curvature-related settings. The analyses show that moderate, dataset-sensitive curvature refinement can matter for both classification and cluster formation.

Effects of graph pooling layer

Effects of Ricci flow iterations l

Curvature convergence and optimal performance

  • PROTEINS needs about 10 iterations to reach curvature convergence, compared with about 6 for IMDB-B; classification peaks earlier than full convergence.The authors define convergence as a maximum-to-minimum edge-curvature difference below 10^-3 and report that larger graphs usually need more iterations.Source: C. Ablation Study and Analysis · p. 9

Effects of graph pooling rate r

  • Across pooling rates, RicciPool maintains the highest average classification accuracy, with less degradation than ORC at higher compression.Its performance varies more widely than MinCut's, while MinCut is more stable but has lower average performance.Source: Figure 4 · p. 10, C. Ablation Study and Analysis · p. 10

Effects of curvature intervention and neighbor information

  • IMDB-B performs best at η = 0.7 or 0.6, while PROTEINS performs best at η = 0.9 or 1.0, depending on α.The authors report that IMDB-B is denser and suggest dataset connectivity may influence the optimal curvature intervention.Source: C. Ablation Study and Analysis · p. 10
  • IMDB-B performs best at α = 0.2, while PROTEINS performs best at α = 0.3 or 0.4, depending on η.α controls the relative weighting of source- and target-node neighborhood distributions in the Wasserstein-distance calculation.Source: C. Ablation Study and Analysis · p. 10

A trick for hyperparameter tuning

  • The reported tuning ranges are α ∈ [0.1, 0.5], η ∈ [0.5, 1.0], and flow iterations generally no greater than 5.These ranges are presented as a tuning guide based on the experiments.Source: C. Ablation Study and Analysis · p. 10

D. Analysis of Cluster Assignment in RicciPool

The visual analysis links curvature flow to changes in subgraph density and distinct node clusters. Cluster assignments also depend on the number of clusters, with potential topology loss at either extreme.

Visualization of graphs in RicciPool

Subgraph structures

  • The flow tightens dense subgraphs and extends edge lengths in sparse ones, distinguishing tree-like, intermediate, and nearly fully connected examples.Figure 6 shows three example graphs across flow iterations; edge lengths indicate weights, and background colors mark communities.Source: Figure 6 · p. 11, D. Analysis of Cluster Assignment in… · p. 12

Sensitivity of the Number of Clusters

  • For PROTEINS, too-large K can fragment dense subgraphs, while too-small K may fail to preserve global topology; for nearly fully connected IMDB-M graphs, K > 1 can disrupt connectivity.The authors report poorer IMDB-M classification under pooling when K > 1 than on the other four datasets discussed in Table II.Source: D. Analysis of Cluster Assignment in… · p. 12

E. Scalability and Efficiency of RicciPool on Large-Scale Graph Datasets

RicciPool separates offline curvature precomputation from graph pooling and GCNN training; its extra cost is generally manageable but sensitive to graph density.

E. Scalability and Efficiency of RicciPool on Large-Scale Graph Datasets

  • Curvature precomputation is shorter than training on larger, sparser REDDIT-M-5K graphs but exceeds training time on denser COLLAB graphs.The comparison indicates that graph size and density affect precomputation and training differently.Source: E. Scalability and Efficiency of… · p. 12
  • As graph density rises, curvature precomputation grows approximately polynomially while training time grows linearly, and precomputation can overtake training.The reported crossover occurs for a 120-node graph when node degree exceeds 60 (density ≈0.5).Source: E. Scalability and Efficiency of… · p. 12, Figure 7 · p. 12, Figure 8 · p. 12
  • Dense graphs may make curvature precomputation a scalability bottleneck, while its cost is usually more manageable for graphs with moderate connectivity.The authors attribute the density sensitivity to the additional local neighborhood interactions considered during Ollivier-Ricci flow.Source: E. Scalability and Efficiency of… · p. 13

F. Computational Efficiency Analysis

  • RicciPool decouples curvature computation from neural-network training: it precomputes curvature features offline and uses them for hierarchical pooling.The pooling phase has computational cost comparable to standard graph convolutional layers and lower than online curvature optimization approaches.Source: F. Computational Efficiency Analysis · p. 13
  • On PROTEINS, curvature precomputation takes 91.0 seconds, or 6.25% of the total training time of 1455.8 seconds.Across the four compared datasets, precomputation time is lower than GCNN training time; precomputation also uses less memory than training on all datasets, independent of Ricci flow iteration count.Source: F. Computational Efficiency Analysis · p. 13
  • The extra computational cost is concentrated in offline curvature precomputation; GCNN training and inference remain unchanged.COLLAB is an exception to the usual pattern of training taking longer, mainly because its high density makes curvature computation more expensive.Source: F. Computational Efficiency Analysis · p. 13

G. Geometric Interpretability of RicciPool

The section relates curvature patterns to clustering and reports stability across tested flow and stopping-threshold settings. It also identifies a fully connected graph limitation and poses open questions for future work.

G. Geometric Interpretability of RicciPool

  • As SBM clustering progresses, intra-cluster edges converge to 100% positive curvature, while inter-cluster edges converge to 100% negative curvature as clusters separate.The inter-cluster proportions shift over the process: positive curvature first increases then decreases, while negative curvature first decreases then increases.Source: Figure 10 · p. 13, G. Geometric Interpretability of… · p. 14
  • In case studies, curvature flow shortens positive-curvature intra-cluster edges and lengthens negative-curvature inter-cluster edges.ENZYMES edge ⟨6, 7⟩ has distances 0.5 and 0.21 after iterations 1 and 2; PROTEINS edge ⟨1, 2⟩ has distances 1.33 and 1.85.Source: G. Geometric Interpretability of… · p. 14

H. Algorithm Stability and Sensitivity Analysis

VI. Conclusion

  • RicciPool uses discrete graph Ricci flow and spectral clustering to learn an assignment matrix intended to preserve the pooled graph’s global topology.The method uses Ollivier-Ricci curvature to distinguish well-connected subgraphs from tree-like structures.Source: §VI · p. 15
  • In fully connected graphs with uniform edge weights and Ollivier-Ricci curvatures, RicciPool cannot uncover a more compact latent structure, limiting its ability to enhance graph representations.The authors also identify determining the optimal number of clusters and relating flow evolution to GNN over-smoothing and over-squashing as future questions.Source: §VI · p. 15

Appendix

IMDB-B shows greater stability than ENZYMES across tested flow iterations and marked insensitivity to stopping-threshold variations.

A. Stability and Sensitivity for IMDB-B

Related papers

Loading 2609.14962v1…