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

Learning latent representations in graphs is finding a mapping that embeds nodes or edges as data points in a lowdimensional vector space. This paper introduces a flexible framework to enhance existing methodologies that have difficulty capturing local proximity and global relationships at the same time. Our approach generates a virtual edge between non-adjacent nodes based on the Forman-Ricci curvature in network. By analyzing the network using topological information, global relationships structurally similar can easily be detected and successfully integrated with previous works.


Introduction
Various approaches have been proposed to find latent representations in graphs. The traditional approach is based on matrix-factorization algorithms related to dimension reduction techniques. Encoding the graph structure heavily depends on which proximity measure is chosen. From a random walk based perspective, learning the node embeddings can be formulated by optimizing the conditional probabilities; the nodes have similar attributes if they co-occur on a short random walk. For instance, struc2vec enables more effective random walk approaches when accounting for the structural identity independent of the node or edges attributes (Ribeiro et al., 2017).
However, a new approach using deep neural network has achieved a breakthrough in network embedding. The advantage of this approach is that it compresses local information so that learning representations not only leverage the substructure of the graph but also the node attributes. For example, it attempts to learn the adaptive structure-aware representations by using jumping knowledge networks (Xu et al., 2018).
When considering the above approaches together, it is difficult to preserve the local proximity and global relationships at the same time.
• Random walk based approaches, such as node2vec and DeepWalk, tend to generate context vertices by exploring local nodes randomly. • Neighborhood aggregation and convolutional methods directly encode the graph structure using a deep neural network. To represent the context vertices, they incorporate the information from the arbitrary depth of the neighborhood nodes (Hamilton et al., 2017).
However, these approaches are easily perturbed on how to construct the context vertices. In particular, the farther apart two nodes are, the less likely the existing methodologies are to capture the structural characteristics between the subgraphs that each node forms. To overcome this weakness, a novel framework is proposed that reformulates the graph by extending the neighborhood of the set based on the topological information. When analyzing the structural similarity of the subgraph, the discrete notion of the curvature is introduced.

Forman-Ricci Curvature
To generalize the curvature in graphs, the definition of Forman-Ricci curvature is reformulated (Weber et al., 2017). Specifically, the discrete notion of the curvature is defined as the geometric properties of two neighboring nodes deviating from the state of a grid graph. To calculate the curvature, we impose a weighting scheme on the nodes and edges so that it reflects the geometric property of the subgraph.

Definition 1 Given a graph
(a) Equivalent subgraphs. (b) Similar subgraphs. Figure 1: Measuring the structural similarity between subgraphs that each of two non-adjacent nodes forms.
The weighting scheme indicates that the subgraph has a 2-hop neighborhood as in Figure 1. With the weighting scheme, the curvature can be represented as the topological information of the graph's sub-structure.
Definition 2 Given a graph G = (V, E) without isolated nodes, the Forman-Ricci curvature for an edge e = (v, u) is defined as where w and γ are weights defined on V and E, respectively, and n e (v) is a set of edges from v excluding e

Generating Virtual Edges in Graphs
By estimating Forman-Ricci curvature information in graph, it can be surmised whether two randomly sampled nodes have structural similarity regardless of their distance. Because the curvature is calculated bidirectionally, the absolute difference of curvature can be interpreted as the structural differences. In detail, the two nodes have the isomorphic structure of the subgraph if is zero and the structural equivalence if is converged. Therefore, it is natural to evolve the network by augmenting the virtual edges by choosing a set of candidate node pairs.
Algorithm 1 Candidate Node Pairs from Curvature Input: An undirected graph G = (V, E), parameters k and Output: A set of candidate node pairs C 1: E ← set of edges not appeared in E; 2: C ← empty set of candidate node pairs;

Experiments
This section shows the effectiveness of the framework in an experiment that used two different datasets. Specifically, we concentrate on identifying the non-adjacent node set that is (a) Karate graph.
(b) Barbell graph. Figure 2: Candidate virtual edges for two networks.
assumed to have the structural equivalence. In this experiment, the value of k was set up to 3 and = 0.1 to select the virtual edges. As shown in Figure 2, two non-adjacent nodes were detected that are regarded as the core of the star structure in the network. Moreover, the two entry points that construct the complete graph were discovered by analyzing the barbell graph using the curvature information. Consequently, we can conclude that curvature-based analysis of the network captures not only the local proximity but also the global relationships between the nodes.

Future Work
The aim of the proposed framework is to reinforce the performance of existing embedding methods. This work showed that the expansion of the neighborhood is reasonable by curvature-based analysis. Additionally, we will demonstrate in the future that combining the meta graph with previous methods can efficiently solve the machine learning tasks such as link prediction and graph classification.
To refine the definition of the curvature, it is worthy that we make an attempt to apply another discretization of curvature to network analysis. Furthermore, we anticipate that it would be practical if the curvature information can be formulated in vector form to exploit both the direction and size.