Meta-Learning on Graph with Curvature-Based Analysis (Student Abstract)

Tae Hong Moon, Sungsu LimAAAI 2020 · DOI

Introduction

In the field of graph representation learning, the primary objective is to map nodes and edges into low-dimensional vector spaces (embeddings) that preserve the graph's essential properties. However, existing methodologies often struggle to bridge the gap between local neighborhood data and global structural patterns.

Most current approaches generally fall into two categories: Random Walk methods (e.g., node2vec), which explore the network by traversing adjacent nodes, and Neighborhood Aggregation methods (e.g., Graph Convolutional Networks), which pool information from immediate vicinities. While effective for capturing local proximity, these methods frequently fail to identify "structurally equivalent" nodes that are distant in the network. For instance, two nodes located on opposite ends of a large graph might both serve as the centers of identical star-shaped clusters. Despite their identical roles, standard algorithms often miss this similarity because the nodes are not topologically close. This paper proposes a novel framework utilizing Forman-Ricci curvature to detect these global structural identities and augment the graph accordingly.

Methodology: Curvature as a Structural Signature

The core innovation of this work is the application of differential geometry concepts—specifically Forman-Ricci curvature—to discrete graph structures. In geometry, curvature measures how a surface deviates from being flat; in this context, it serves as a signature for the topological "shape" of a node's local subgraph.

Figure 1: Illustration of equivalent subgraphs where the curvature difference between nodes u and v is zero, indicating structural isomorphism.

The proposed framework follows a multi-step pipeline:

  1. Weighting Scheme: Weights are assigned to nodes based on their degrees and to edges based on the properties of their connected nodes.
  2. Curvature Calculation: The Forman-Ricci curvature is calculated for edges, providing a mathematical description of the 2-hop neighborhood structure.
  3. Virtual Edge Generation: The algorithm performs a bidirectional analysis of non-adjacent node pairs. If the absolute difference between their curvatures is near zero, the nodes are deemed structurally isomorphic (as seen in the figure above).
  4. Graph Augmentation: The framework inserts "virtual edges" between these distant but structurally similar nodes. This process effectively "shortcuts" the graph, allowing standard embedding models to treat global structural similarity as local proximity.

Experimental Evaluation

To validate the framework as a proof-of-concept, the authors evaluated the curvature-based analysis on two classic benchmark graphs: the Karate Graph (Zachary’s Karate Club) and the Barbell Graph.

Figure 2: The two benchmark graphs used for qualitative analysis: (a) the Karate social network and (b) the synthetic Barbell graph.

Key Results

  • Karate Graph: The framework successfully identified non-adjacent nodes that functioned as the "cores" of star structures, recognizing their identical roles within the social network despite their lack of direct connection.
  • Barbell Graph: The analysis correctly pinpointed the "entry points" connecting dense cliques to the central bridge. These nodes share unique structural properties that the curvature analysis was able to isolate.

These qualitative results demonstrate that curvature-based analysis can detect global relationships that remain invisible to traditional methods relying solely on local adjacency. By treating curvature as a pre-processing step, the framework remains "plug-and-play," compatible with existing models like DeepWalk or GCNs without requiring fundamental changes to their architectures.

Conclusion and Future Work

While this student abstract provides a compelling geometric approach to graph learning, several areas for future research remain. The current study focuses on small-scale qualitative analysis; future work must address the computational scalability of calculating curvature for all node pairs in massive datasets. Additionally, the authors aim to provide quantitative benchmarking on standard machine learning tasks, such as link prediction and graph classification, to further prove the framework's utility in large-scale applications.

Summary updated

BibTeX
@inproceedings{moon2020meta,
  author = {Tae Hong Moon and Sungsu Lim},
  title = {{Meta-Learning on Graph with Curvature-Based Analysis (Student Abstract)}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i10.7210},
}
Figure