Hyperbolic Graph Neural Networks at Scale: A Meta Learning Approach
Authors: Nurendra Choudhary
Nikhil Rao
Chandan K. Reddy
Venue: NeurIPS 2023 poster (2023)
Keywords: meta learning
hyperbolic networks
scalability
graph neural networks
TL;DR: The paper proposes H-GRAM, a novel method for learning meta information from support subgraphs in HNNs to enable faster learning over new disjoint subgraphs. H-GRAM solves the scalability limitation in HNNs and outperforms SOTA baselines.

Abstract: The progress in hyperbolic neural networks (HNNs) research is hindered by their absence of inductive bias mechanisms, which are essential for generalizing to new tasks and facilitating scalable learning over large datasets. In this paper, we aim to alleviate these issues by learning generalizable inductive biases from the nodes’ local subgraph and transfer them for faster learning over new subgraphs with a disjoint set of nodes, edges, and labels in a few-shot setting. We introduce a novel method, Hyperbolic GRAph Meta Learner (H-GRAM), that, for the tasks of node classification and link prediction, learns transferable information from a set of support local subgraphs in the form of hyperbolic meta gradients and label hyperbolic protonets to enable faster learning over a query set of new tasks dealing with disjoint subgraphs. Furthermore, we show that an extension of our meta-learning framework also mitigates the scalability challenges seen in HNNs faced by existing approaches. Our comparative analysis shows that H-GRAM effectively learns and transfers information in multiple challenging few-shot settings compared to other state-of-the-art baselines. Additionally, we demonstrate that, unlike standard HNNs, our approach is able to scale over large graph datasets and improve performance over its Euclidean counterparts.

Hyperbolic Graph Neural Networks at Scale: A Meta Learning Approach
Nurendra Choudhary Virginia Tech Arlington, VA, USA nurendra@vt.edu
Nikhil Rao Microsoft Sunnyvale, CA, USA
Chandan K. Reddy Virginia Tech Arlington, VA, USA reddy0cs .tt edu
midhhlraommicrooofee com
Abstract
The progress in hyperbolic neural networks (HNNs) research is hindered by their absence of inductive bias mechanisms, which are essential for generalizing new tasks and facilitating scalable learning over large datasets. this paper, we aim to alleviate these issues by learning generalizable inductive biases from the nodes' local subgraph and transfer them for faster learning over new subgraphs with a disjoint set of nodes, edges, and labels in few-shot setting. We introduce novel method, Hyperbolic GRAph Meta Learner (H-GRAM), that, for the tasks node classification and link prediction, learns transferable information from set of support local subgraphs the form of hyperbolic meta gradients and label hyper- bolic protonets to enable faster learning over query set of new tasks dealing with disjoint subgraphs. Furthermore, we show that an extension of our meta-learning framework also mitigates the scalability challenges seen in HNNs faced by exist- ing approaches. Our comparative analysis shows that H-GRAM effectively learns and transfers information multiple challenging few-shot settings compared other state-of-the-ar baselines. Additionally, we demonstrate that, unlike stan- dard HNNs, our approach is able scale over large graph datasets and improve performance over its Euclidean counterparts.
Introduction
Graphs are extensively used in various applications, including image processing, natural language processing, chemistry, and bioinformatics. With modern graph datasets ranging from hundreds of thousands to billions of nodes, research in the graph domain has shifted towards larger and more complex graphs, e.g., the nodes and edges in the traditional Cora dataset 103, whereas, the more recent OGBN datasets [I7] are in the order of 105. However, despite their potential, Hyperbolic Neural Networks (HNNs), which capture the hierarchy of graphs in hyperbolic space, have struggled to scale up with the increasing size and complexity of modern datasets.
[29] are the order of
HNNs have outperformed their Fuclidean counterparts by taking advantage the inherent hierarchy present in many modern datasets 4 10 13 Unlike standard Graph Neural Network (GNN), HNN learns node representations based on an "anchor" or a "root" node for the entire graph, and the operations needed to learn these embeddings are function of this root node. Specifically, HNN for- mulations
[K] depend on the global origin (root node) for several transformation operations (such Möbius addition. Möbius multiplication, and others), and hence focusing subgraph structures to learn representations becomes meaningless when their relationship to the root node is not con- sidered. Thus, state-of-the-ar HNNs such HGCN [4], HAT (15), and HypE g require access to the entire dataset to learn representations, and hence only scale to experimental datasets (with es 100 nodes). Despite this major drawback, HNNs have shown impressive performance eral research domains including recommendation systems (32) e-commerce (9). natural language processing [1I, and knowledge graphs 5 M It is thus imperative that develops methods to scale HNNs to larger datasets, so as to realize their full potential. To this end, we introduce a novel method, Hyperbolic GRAph Meta Learner (HI-GRMM,, that utilizes meta-learning to learn infor-
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Generic graph with labeled samples (red and blue) and unlabeled samples (silver).
Meta learning structure priors on the labeled local partitions the graph.
Utilize the meta information for faster learning new nodes, edges labels (yellow in this case).
Meta. Trainini
Meta- Testing
Single Graph, Shared Labels
Single Graph, Disjoint Labels
Multiple Graph, Shared Labels
Multiple Graph, Disjoint Labels
Figure I: Meta-learning on hyperbolic neural networks. The procedure consists of two phases (i) meta-training to update the parameters of the HNNs and learn inductive biases (meta gradients and label protonets), and (ii) meta-testing that initializes the HNNs with the inductive biases for faster learning over new graphs with a disjoint set of nodes, edges, or labels.
mation from local subgraphs for HNNs and transfer it for faster learning disjoint set of nodes, edges, and labels contained in the larger graph. As consequence of meta-learning, H-GRAM also achieves several desirable benefits that extend HNNs' applicability including the ability transfer information on new graphs (inductive learning), elimination of over-smoothing, and few-shot learn- ing. We experimentally show that H-GRAM can scale graphs of size O(10)), which O(10)) times larger than previous state-of-the-art HNNs. To the best of our knowledge, there are no other methods that can scale HNNs datasets of this size.
Recent research has shown that both node-level and edge-level tasks only depend on the local neigh- borhood for evidence of prediction | 19 E2) Inspired by the insights from such rescarch, model handles large graph datasets using their node-centric subgraph partitions, where each sub- graph consists of root node and the h-hhpp neighborhood around it. In H-GRAM, the HNN formu- lations establish the root node as the local origin to encode the subgraph. We theoretically show that, due the locality of tangent space transformations in HNNs (more details in Section 3p. the evi- dence for a node's prediction can predominantly be found in the immediate neighborhood. Thus, the subgraph encodings do not lose significant amount of feature information despite not having cess to a "global" root node. However, due to the node-centric graph partitioning, the subgraphs are non-exhaustive, i.c., they do not contain all the nodes, edges, and labels, previously assumed by HNNs. Thus, to overcome the issue of non-exhaustive subgraphs, we formulate four meta-lcarning problems (illustrated in Figure Mp that learn inductive biases on support set and transfer it for faster learning a query set with disjoint nodes, edges, labels. Our model learns inductive biases in the meta-training phase, which contains two steps HNN update and meta update. HNN updates are regular stochastic gradient descent steps based on the loss function for each support task. The updated HNN parameters are used calculate lated into meta-gradies for the meta update. In the meta-testing phase, the models are evaluated on query tasks with parameters post the meta updates, as this snapshot of the model is the most adaptable for faster learning in few-shot setting. Our main contributions are as follows:
loss on query tasks and gradients are accumu-

---

1. We theoretically prove that HNNS rely on the nodes' local neighborhood for evidence in predic- tion, as well as, formulate HNNSs encode node-centric local subgraphs with root nodes as the local origin using the locality of tangent space transformations.
We develop Hyperbolic GRAph Meta Learner (H-GRAM), a novel method that learns meta in- formation (as meta gradients and label protonets) from local subgraphs and generalize it to new graphs with a disjoint set of nodes, edges, and labels. Our experiments show that H-GRAM can be used to generalize information from subgraph partitions, thus, enabling scalability.
3. Our analysis on a diverse set of datasets demonstrates that our meta-learning setup also solves several challenges in HNNs including inductive learning, elimination of over-smoothing, and few-shot learning in several challenging scenarios.
2 Related Work
This section reviews the relevant work in the areas of hyperbolic neural networks and meta learning.
Hyperbolic Neural Networks: Due to their ability to efficiently encode tree-like structures, hy- perbolic space has been significant development in the modeling of hierarchical datasets 43 44]
Among its different isometric interpretations, the Poincaré ball model is the most popular one and has been applied in several HNN formulations of Euclidean networks including the recurrent (HGRU
13) ), convolution (HGCN 4. and attention layers (HAT (51). As a result of their performance gains hierarchical graphs. the formulations have also been extended to applications in knowledge
graphs for efficiently encoding the hierarchical relations in different tasks such as representation learning (MuRP M. AttH (55) and logical reasoning (HypE ()). However, the above approaches have been designed for experimental datasets with a relatively small number of nodes (in the order of 109), and do not scale real-world datasets. Hence, we have designed H-GRAM a meta-learning algorithm to translate the performance gains of HNNs to large datasets in a scalable manner.
Few-shot meta-learning transfers knowledge from prior tasks for faster learning over new tasks with few labels. Due to their wide applicability, they have been adopted in several domains including computer vision [4 E4 natural language processing 22 and, more cently, graphs 18 39 One early approach in graph meta-learning is Gated Propagation Networks
Graph Meta-learning:
23 which learns to propagate information between label prototypes to improve the information available while learning new related labels. Subsequent developments such as MetaR 77, Meta-NA
41 and G-Matching (39) relied on metric-based meta learning algorithms for relational graphs, net- work alignment and generic graphs, respectively. These approaches show impressive performance on few-shot learning, but are only defined for single graphs. G-Meta [TS] extends the metric-based techniques to handle multiple graphs with disjoint labels. However, the method processes informa- tion from local subgraphs in a Euclidean GNN, and thus, is not as capable as hyperbolic networks in encoding tree-like structures. Thus, we model H-GRAM to encode hierarchical information from local subgraphs and transfer to new subgraphs with disjoint nodes, edges, and labels.
3 The Proposed H-GRAM Model
In this section, we define the problem setup for different meta-learning scenarios and describe our proposed model, H-GRAM, illustrated in Figure n For better clarity, we explain the problem setup for node classification and use HGCN as the exemplar HNN model. However, the provided setup can be extended to link prediction or to other HNN models, which we have evaluated in our experiments. The preliminaries of hyperbolic operations and meta-learning are provided in Appendix A
3.1 Problem Setup
Our problem consists of a group of tasks T, T which are divided into support set T and query set T", where T = Φ Furthermore, each task T, is batch of node-centric subgraphs S,, with corresponding label Y. (class of root node in node classification or root link in link prediction). The subgraphs Sy could be the partitions derived from single graph or multiple graphs, both denoted by G" G" U G4. We also define Y, = (Y, E Th} and Y, = (Y,, E T } as the set of labels in the support and query set respectively. The primary goal of meta-learning is to learn a predictor using the support set, Pa_ (YsIT*) such that the model can quickly learn a predictor (Y on the query set. Following literature in this area [8 the problem categories are defined follows:
3

---

Mota- Teaining Phase
HNN Update
Subgraph Encoding
T E Dieaon
HNN
train
Po.
Label ProtoNets
77 Diraio
Subgraph Encoding
train
Meta Update
0.
Testing Phase
Update
Node-centric Subbraaph
Subgraph Encoding
Partitions
HNN Model
Fest
T
Po
Label ProtoNets
Subgraph Encoding
test
An overview of the proposed H-GRAM meta-learning framework. Here, the imput graphs go are first partitioned into node-centric subgraph partitions. We theoretically show that encoding these subgraph neighborhoods is equivalent to encoding the entire graph in the context of node classification and link prediction tasks. H-GRAM then uses an HGCN encoder to produce subgraph encodings, which are further utilized to get label prototypes. Using the HGCN gradient updates and label prototypes, the HNN model's parameters Po- is updated through a series of weight updates and meta updates for 1 meta-training steps. The parameters are then transferred to the meta-testing stage Pa- and further trained on Diest and evaluated on D
Figure 2:
Single graph, shared labels (SG, SL) The objective is to learn the meta-learning model Pe.-1o, where Y, = Y, and n
G 1. It should be noted that the tasks are based on subgraphs, so | - + T = [ = Also, this problem setup is identical to the standard node classification task considering T." E Drest be the test set.
Single graph, disjoint labels (SG, DL): This problem operates on the same graph in the support and query set, however unlike the previous one, the label sets disjoint. The goal is to learn the model Po.- where | g" = 1 and Y, ny, = á.
3. Multiple graphs, shared labels (MG, SLY: This problem setup varies in terms of the dataset handles, i.e., the dataset can contain multiple graphs instead of a single one. However, our method focuses tasks which contain node-centric subgraphs, and hence, the model's aim is the same as problem 1. The aim to learn the predictor model Po.- where Y, = Y, and ( 199 1.
4. Multiple graphs, disjoint labels (MG, DL): In this problem, the setup is similar to the previ- ous one, but only with disjoint labels instead of shared ones, i.e., learn a predictor model P9. where Y, n Y and g | > 1.
From the problem setups, observe that, while they handle different dataset variants, the base HNN model operates on the (Su, Yu) pair. So, we utilize hyperbolic subgraph encoder and prototypical labels to encode S,, and get continuous version of Y,, for our meta-leariin algorithm, respectively.
3.2 Hyperbolic Subgraph Encoder
In previous methods 16 58) authors have shown that nodes' local neighborhood provides some informative signals for the prediction task. While the theory is not trivially extensible, use the local tangent space Poincaré ball model to prove that the local neighborhood policy holds better for HNN models. The reason being that, while message propagation is linear in Euclidean GNNs it is exponential in HNNs. Hence, a node's 's influence, as given by Definition D neighborhood decreases exponentially.
outside its
Definition 1. The influence of hyperbolic node vector xhe on node H is defined by the influence
(
logi (
score Ine = expp
3 Togg (c:)

---

The inftuence of a graph G with set of vertices V on a node u E V is defined as Iz(u)= expń (Ceey loge (Iuo)). Theorem 1. For a set of paths Puo between nodes u and v, let us define De as the geometric mean of nodes' degree in a path ps Puv. Puv the shortest path, and Iuo the influence node u. Also, let us say n min { gu Vp, E Puv }. then the relation Iwo S expp /K/ (Digin) I (where K is a constant) holds for message propagation in HGCN models.
Definition 2.
Theorem shows that the influence of a node decreases exponent-on with increasing distance |l Thus, we conclude that encoding the local neighborhood of node sufficient to encode its features for label prediction.
peponent-of-exponeee of-exoonentially (exp, O(c"))
Definition 3.
The information loss between encoding an entire graph 9 and a subgraph Su with root node is defined as 6g = expp (loge (Ig - logg (Is, (u))).
Theorem 2. For subgraph S, of graph centered at node u, let us define a node v E 9 with maximum inffuence on u, i.e., V = arg max, ( ((Iut,t t NN(u) ut)) For a set of paths Pwo between nodes u and v, let us define Dig as the geometric mean of degree of nodes in a path pi E Pan. lI is the shortest path length, and Dmnin = =min { (Dai gi Vp, E Puo Then, the information loss is bounded by (g Sw) S exppi (K/ (Dmin) (1pwol++) (where K is a constant).
Theorem shows that encoding the local subgraph is ellp order approximation of encoding the entire graph, and thus, with high enough ||Paoll ll. the encodings are equivalent. Note that ||pwe is equivalent to the subgraph's 's neighborhood size (A in k-hop). This shows that encoding a node's ' local neighborhood is sufficient to encode its features. Theorem proofs are provided in Appendix [ The above theorems provide us with the theoretical justification for encoding local subgraphs into our meta-learning framework. Hence, we partition the input GD into subgraphs S. = V x E centered at root node u, with [V] nodes, |E' edges, a neighborhood size k. and the corresponding label Yu- The subgraphs are processed through an k-layer HGCN network and the Einstein midpoint [3]] of all the node encodings are taken as the overall encoding of the subgraph S.. For a given subgraph
S, = (A, X), where A E [||V|| I is the local adjacency matrix and X E [IllI are the node feature vectors of m dimension, the encoding procedure given can be formalized as:
hu HGCNN (A, where h. E [l]lV||
(1)
I|1 Yeaheu E!M
Cu II1 Yiu
where Yiu VT- 1
(2)
where (ACN(A, e H is the output of k-layer HGCN with output units and e, E Hd is the final subgraph encoding of S.- You is the Lorentz factor of the hyperbolic vector hiu that indicates its weightage towards the Einstein midpoint.
3.3 Label Prototypes
Label information is generally categorical in node classification tasks. However, this does not allow us pass inductive biases from the support set the query set. Hence, to circumvent this issue, we use prototypical networks [3I] as our label encoding. Our approach constructs continuous label pro- totypes by using the mean of meta-training nodes' features that belong to the label. These prototypes are then employed to classify meta-testing samples based on their similarity to the corresponding meta-training label prototypes. This enables our model handle new, non-exhaustive labels in an inductive manner, without the need for additional training data. The primary idea is to form contin- uous label prototypes using the mean of nodes that belong to the label. To this end, the continuous Σy.=u Yie,
label prototype of a label ys is defined as C Lve-vy Yi where Y; Vi-Ilea| and e E Hd is
encoding of subgraphs Su with labels Y, = yk- For each S, with class yk, we compute the class ( ((-dg(en (e(.eee))))) distribution vector as Pı el (emiee)) where de(ee,, cu) Ve tanh- (vol - e, t cxl) and
the loss for HNN updates C(p, 9) = E, yr logp;, where y; is the one-hot encoding of the ground truth. The class distribution vector Ps is softmax over the hyperbolic distance of subgraph encod- ing to the label prototypes, which indicates the probability that the subgraph belongs to the class yk- The loss function L(p. y) is the cross-entropy loss between ground truth labels y and the class distribution vector p.
5

---

3.4 Meta-Learning
In the previous section, we learned a continuous label encoding that is able to capture inductive biases from the subgraph. In this section, we utilize the optimization-based MAMI. algorithm [22 to transfer the inductive biases from the support set to the query set. To this end, we sample a batch of tasks, where each task T. {s,, Y |17al In the meta-training phase, we first optimize the HNN parameters using the Riemannian stochastic gradient descent (RSGD) [ on support loss, Le., for each 7, E Tirain 0f +- expa; (-vVL.) where is the learning rate of RSGD. Using the updated parameters oj we record the evaluation results on the query set, i.e., loss on task 7," Tyy Again is CT The above procedure is repeated 1y times post which L over the batch of tasks T," Train is accumulated for the meta update 6* < expp. (-3V C.). The above steps are repeated with the updated #* and new batch of tasks till convergence. The final updated parameter set 8" + transferred to the meta-testing phase. In meta-testing, the tasks T E Ticst are used for RSGD parameter updates, i.., 7 Trest 0g < exp, (-aVL*) until convergence. The updated parameters are used for the final evaluation on T," E Tees Our meta-learning procedure is further detailed in Appendix C and the implementation code with our experiments is available at hattps://githii com Awwrato/ /kt/rat///tttaAMM Details on implementation and broader impacts are provided in Appendices 3.5 and respectively.
3.5 Implementation Details
with geoopt 21 and GraphZ.oo 656 as support libraries for hyperbolic formulations. Our experiments are conducted on a Nvidia V100 GPU with 16 GB of VRAM. For gradient descent, we employ Riemannian Adam (28] with an initial learning rate of 0.01 and standard 8 values of 0.9 and 0.999. The other hyper-parameteen were selected based on the best performance on the validation set (Dvat) under the given computational constraints. In our experiments, we empirically set k = search space and tune our cypeer-arammters. for best performance. The number of tasks in each batch are varied among 4, 8, 16, 32, and 64. The learning rate explored for both HNN updates and meta updates are 10-2.5 5 x 10-3, 10-3 and 5 x 10-1 The size of hidden dimensions are selected from among 64, 128, and 256. The final best-performing syper-parameter setup for real- world datasets
H-GRAM is primarily implemented Pytorch 26
32, h 4, and 1) = 10. We explore the following
presented in Table 5
4 Experimental Setup
Our experiments aim to evaluate the performance of the proposed H-GRAM model and investigate the following research questions:
RQ1:
Does our hyperbolic meta-learning algorithm outperform the Euclidean baselines on vari- ous meta-learning problems?
RQ2: How does our model perform and scale in comparison to other HNN formulations in stan-
dard graph problems?
RQ3: How does H- H-GRAM model's performance vary with different few-shot settings, i.e., dif- ferent values of & and N?
RQ4: What is the importance of different meta information components?
We use a set of standard benchmark datasets and baseline methods to compare the performance of H-GRAM on meta-learning and graph analysis tasks. The HNN models do not scale to the large datasets used in the meta-learning task, and hence, we limit our tests to Euclidean basclines. To compare against HNN models, we rely on standard node classification and link prediction on small datasets. Also, we do not consider other learning paradigms, such as self-supervised learning be- cause they require an exhaustive set of nodes and labels and do not handle disjoint problem settings.
4.1 Datasets
For the task of meta-learning we utilize the experimental setup from earlier approaches [8 two synthetic datasets to understand if H-GRAM is able to capture local graph information and five real-world datasets to evaluate model's performance in shot setting.

---

Synthetic Cycle 18 contains multiple graphs with cycle as the basis with different topologies (House, Star, Diamond, and Fan) attached to the nodes on the cycle. The classes of the node are defined by their topology.
Synthetic BA 18 uses larer (BA) graph as the basis with different topologies planted within it. The nodes are labeled using spectral clustering over the Graphlet Distribution Vector
27 of each node.
ogbn-arxiv 11 is a large citation graph of papers, where titles are the node features and subject
areas are the labels.
Tissue-PPI [16
+ contains multiple pootein-protein interaction (PPI) networks collected from
different tissues, gene signatures and ontology functions as features and labels, respectively.
FirstMM-DB
25
standard 3D point cloud link prediction dataset.
Fold-PPI is set of tissue PPI networks, where the node features and labels are the conjoint
4
triad protein descriptor
30 and protein structures, respectively.
Tree-of-Liife 44 is large collection of PPI networks, originating from different species.
4.2 Baseline Methods
For comparison with HNNs, we utilize the standard benchmark citation graphs of Cora 22 Pubmed [24]. and Citeseer (29]. For the baselines, we select the following methods to understand H-GRAM's performance compared state-of-the-art models in the tasks of meta-learning and standard graph processing.
Meta-Graph 3 developed for few-shot link prediction over multiple graphs, utilizes VGAE
model with additional graph encoding signals.
Meta-GNN
40 a MAML developed over simple graph convolution (SGC) network 36].
FS-GIN 37
runs Graph Isomorphism Network (GIN) on the entire graph and then uses the few- shot labelled nodes to propagate loss and learn.
FS-SGC 36
is the same as FS-GIN but uses SGC instead of GIN as the GNN network.
learn a metric space over label prototypes to generalize over unseen classes. is Model-Agnostie Meta Learning (MAML) method that learns multiple tasks to adapt the gradients faster on unseen tasks.
ProtoNet
31
MAML 12]
HMLP [ HGCN 4 and HAT [1]] are the hyperbolic variants of Euclidean multi-layer perceptron (MLP), Graph Convolution Network (GCN), and Attention (AT) networks that use hyperbolic gyrovector operations instead of the vector space model.
should be noted that not all the baselines can applied to both node classification and link prediction. Hence, we compare our model against the baselines only on the applicable scenarios.
5 Experimental Results
We adopt the following standard problem setting which is widely studied in the literature 18 The details of the datasets used in our experiments provided in Table L In the case of synthetic datasets, we use 2-way setup for disjoint label problems, and for the shared lahel problems the cycle graph and Barabási-Albert (BA) graph have 17 and 10 labels, respectively. The evaluation of our model uses 5 and 10 gradient update steps in meta-training and meta-testing, respectively. In the case of real-world datasets, we use 3-shot and 16-shot setup for node classification and link prediction, respectively. For real-world disjoint labels problem, we use the 3-way classification setting. The evaluation of our model uses 20 and 10 gradient update steps in metaa-raining and meta- testing, respectively. In the case of Tissue-PPI dataset, we perform each 2-way protein function task three times and average it over 10 iterations for the final result. In the case of link prediction task, we need to ensure the distinct nature of support and query set in all meta-training tasks. For this, we hold out fixed set comprised of 30% and 70% of the edges as preprocessing step for every graph for the support and query set, respectively.
5.1 RQ1: Performance of Meta-Learnnig
To analyze the meta-learning capability of H-GRAM, we compare it against previous approaches in this area on standard evaluation setup. We consider two experimental setups inline with previ- ous evaluation in the literature [[]] (i) with synthetic datasets to analyze performance on different problem setups without altering the graph topology, and (ii) with real-world datasets to analyze per-
7

---

Basic statistics of the datasets used our experiments. The columns present the dataset task (node classification or link prediction), number of graphs | nodes [V edges |E], node
Table 1:
features | and labels YY) Node, Link, and N/L. indicates whether the datasets are used for node classification, link prediction, and both, respectively.
Dataset
Task
V
E
X
Y
Synth. Cycle
Node
10
11,476
19,687
17
Synth. BA
Node
10
2,000
7,647
10
ogbn-arxiv
Node
169,343
1,166.243
Tissue-PPI
Node
24
51,194
1,350,412
50
10
FirstMMM-D
Link
41
56,468
126,024
5
2
Fold-PPI
Node
144
274,606
3,666.563
512
29
Tree-of-Lite
Link
1,840
1,5006633
8,762.166
Cora
N/L.
2,708
5,429
1,433
Pubmed N/L.
19,717
44,338
500
Citeseer
N/I.
1
3,312
4,732
3,703
6
Table 2: Performance of H-GRAM and the baselines on synthetic and real-world datasets. The top three rows define the task, problem setup (Single Graph (SG), Multiple Graphs (MG), Shared Labels (SL) Disjoint Labels (DL)) and dataset. The problems with disjoint labels use 2-way meta-learning setup, and in the case of shared labels, the cycle (S. Cy) and BA (S. BA) graph have 17 and 10 labels, respectively. In our evaluation, we use 5 and 10 gradient update steps meta- training and meta-testing, respectively. The columns present the average multi-class classification accuracy and 95% confidence interval over five-folds. Note that the baselines are only defined for certain tasks, "_" implies that the baseline is not defined for the task and setup. Meta-Graph is only defined for link prediction. The confidence intervals for the results are provided in Appendix D
Synthetic Datasets
Real-world (Node Classifiatiion
Real-workd (Link Prediction)
Task Setup
(SG. DL) (MG, SL) (MG, DE) (SG, DL) (MG, SL) (MG, DL) ogbm-arxiv
(MG, SL) (MG, SL)
Dalasel
Cy S.BA S. S. BA S.Cy S.BA
Tosme-PPI
Fold-PPI
Tree-of-Läfe
Meta-Graph
.19
.703
.644
FS-GIN
.684
.749
336
FS-SGC
.574
.715
.37
ProtoNet
.21
.888
282
.57
.749
866
.372
.546
.382
.779
.697
MAMI.
842
848
511
726
.633
844
389
.745
.422
.758
.719
G-META
867
542
734
767
867
451
.768
561
.784
.722
H-GRAM
883
.873
.55
.76
.779
888
.472
.786
.584
.804
.742
formance for practical application. Based the problem setup, the datasets are partitioned into node-centric subgraphs with corresonding root node's label as the subgraph's 's ground truth label. The subgraphs are subsequently batched into tasks which are further divided into support set and query set for meta-lcarning. The evaluation metric for both the tasks of node classification and link prediction accuracy A = YY Yl/[Y|. For robust comparison, the metrics are computed over five folds of validation splits in 2-shot setting for node classification and 32-shot setting for link prediction. Table presents the five-fold average and 95% confidence interval of our experiments on synthetic and real-world datasets, respectively. From the results, we observe that H-GRAM con- sistently outperforms the baseline methods on a diverse set of datasets and meta-learnin problem setups. For the disjoint labels setting. H-GRAM outperforms the best baseline in both the cases of single and multiple graphs. In the case of synthetic graphs, we observe that subgraph methods of H-GRAM and G-Meta outperform the entire graph encoding based approaches showing that sub- graph methods are able to limit the over-smoothing problem [c] and improve performance. Also, we observe that meta-learning methods (ProtoNet and MAML) are unreliable their results producing good results for some tasks and worse for others, whereas H-GRAM is consistently better across the board. Hence, we conclude that using label prototypes to learn inductive biases and transfer- ring them using MAML meta updates is a more robust technique. We note that H-GRAM, unlike previous HNN models, is able handle graphs with edges and nodes the order of millions, as evident by the performance on large real-world datasets including ogbn-arxiv, Tissue-PPI, Fold-PPI, and Tree-of-Life. Our experiments clearly demonstrate the significant performance of H-GRAM in wide-range of applications and prove the effectiveness of meta- meta-learning in HNN models.

---

Table 3: Comparison with HNN models on standard benchmarks. We compare the Single Graph, Shared Labels (SG,SL) setup of the H-GRAM model to the baselines. The columns report the average multi-class classification accuracy and 95% confidence interval over five-folds on the tasks of node classification (Node) and link prediction (Link) in the standard citation graphs.
Dataset
Cora
Pubmed
Citeseer
Task
Node
Link
Node
Link
Node
Link
HMLP
.754.1.029
.665.10477
.657.1.045
.8481.03 0.08
.8791.078
.8771.090
HAT
.796.1.036
.792.1.038
.6811.003
.9081.008
.9391.034
.92211036
HGCN
.779:.026
.789:1.300
696990029
.914.0011
.950-.032
.92+#.030
H--GAM
827-1.037
.790.1.026
.716.1.029
889.1.025
.9241.033
.936.1.030
5.2 RQ2: Comparison with HNN models
The current HNN formulations of HMLP, HAT, and HGCN do not scale to large datasets, and hence, we were not able to compare them against H-GRAM on large- scale datasets. However, it is necessary to compare the standard HNN formulations with H-GRAM to understand the importance of subgraph encoders and meta-learning. Thus, we utilize the single graph and shared labels setup of H-GRAM to evaluate its performance on citation net- works of Cora, Pubmed, and Citeseer for both tasks of node classification and link prediction. We also compare the time taken by our model and other HNNs on vary- ing number of nodes ((V) {10') 1100)_=))) in the Synthetic BA graph. For this experiment, we also consider a multi- GPU version of H-GRAM that parallelizes the HNN up- date computations and accumulates them for meta up- date. From results, presented in Table El ob- serve that H-GRAM is, on average, able to outperform the best baseline. This shows that our formulation of HNN models using meta-learning over node-centric sub- graphs is more effective than the traditional models, while also being scalable over large datasets. The scalability allows for multi-GPU training and translates the perfor- mance gains of HNNs to larger datasets. In the results provided in Figure 3 we observe that the time taken by the models is inline with their parameter complexity However, the tradi- tional HNNs are not able to scale beyond |V] 10 whereas, H-GRAM able to accommodate large graphs. Another point to note is that H- GRAM(multi) is able to parallelize well over multiple GPUs with its time taken showing stability after 10t nodes (which is the size of nodes that a single GPU can accommodate).
100
00
70
60
50
40
Time
30
20
10
Log of Number of Vertices D1et
HMUP -a-
HSCN
-M- HAT
H-DRAM
Figure 3: Time taken (per epoch) by
H-GRAM compared other HNNs
with varying number of nodes [V] [109H_] Syn. BA graph. H-
GR GRAM(multi) is the multi-GPU version of H-GRAM.
5.3 RQ3: Challenging Few-shot Settings
To understand the effect of different few-shot learning scenarios, vary the number of few-shots M and hops in the neighborhood. For the experiment on few-shot classification, we consider the problems of node classification Fold-PPI dataset and link prediction We vary M = 2,2,3 3 and M = 16, 32, 64 for node classification and link prediction, respectively, and calculate the corresponding accuracy and 95% confidence interval of H-GRAM. The results for this experiment are presented in Figures 4 and 4b for node classification and link prediction, respectively. To determine the effect of hops the neignborhood, we vary K 1, 3 for the same problem setting and compute the corresponding performance of our model. The results for varying neighborhood sizes are reported in Figure 4c the results on varying the number of few-shots, we observe a linear trend in both the tasks of node classification and link prediction, i.e., linear increase H-GRAM's accuracy with an increase in the number of shots in meta-testing. Thus, we conclude that H-GRAM, like other generic learning models, performs better with an increasing number of training samples. In the experiment on increasing neighborhood size, we observe that in the task of node classification, K = 3 shows the best performance, but in link prediction K
FirstMM-DB dataset.

---

has the best performance, with a significant drop in K = 3. Thus, for stability, we choose K = our experiments. The trend link prediction also shows that larger neighborhoods can lead an increase in noise, which can negatively affect performance.
Accunsty on Nodo Clasiitcation
0.70
Accurtty on Link Prediction
0.82
0.00
0.80
0.55
0.79
0.45
0.40
0.77
10
16
32
of horheohooddddddo
Number shots in Meta-testing
Number of shots Meta-testing
-o--Wade jellovng
(a) Number of Shots (vs) Accuracy (h) Number of Shots (vs) Accuracy (c) Number of hops (vs) Accuracy for node classification Fold-PPI for link prediction FistMMM-DB the task of node classification and dataset.
dataset.
link prediction.
Figure 4: Performance of H-GRAM on challenging few-shot settings. The reported accuracies multi-class classification accuracy averaged over five-fold runs our model.
5.4 RQ4: Ablation Study
In this section, we aim to understand the contribution of the different components in our model. To this end, we compare variants of our model by (i) varying the base HNN model (HMLP, HAT, and HGCN), and (ii) deleting individual meta-learning components H-ProtoNet implies H-GRAM without meta updates and H-MAML implies H-GRAM without prototypes. The model variants are compared on the real-world datasets and the results are presented in Table The ablation study indicates that meta gradient updates and label prototypes contribute 16% and #66 improvement in H-GRAM's performance, respectively. This clearly demonstrates the ability of label prototypes in encoding inductive biases and that of meta gradients transferring the knowledge from meta- training to the meta-testing phase. Additionally. from our study on different HNN bases for H- GRAM, we note that the HGCN base outperforms the other bases HMLP and HAT by 119% and 22%, respectively. Thus, we choose HGCN the base in our final model.
Table 4: Ablation study results H-ProtoNet and H-MAML can be considered H-GRAM's model variants without meta updates and label prototypes, respectively. H-GRAM(HMLP)) and H- GRAM(HAT) represents the variant of H-GRAM with HMLP and HAT as base, respectively. Our final model, presented the last row, uses HGCN as the base model. The columns report the av- erage multi-class classification accuracy and 95% confidence interval over five-folds on different tasks.
Task
Node Classification (MG, SL)
Link Prediction
Setup
(SG, DL> ogbn-arxiv
(MG, DL)
(MG, SL)
(MG, SL)
Dataset
Tissue-PPI
Fold-PPI
FirstMM-DB
Tree-of-Life
H- ProtoNet
.389-E0119
559+.027
.93+.023
.799t.015
.716#.004
H-MAML
.407.0023
.722+.056
5022:.04
.7772.018
.739+.005
H-GRAM(HMLP)
.370#.036
.537:.044
.372+.036
.772+.028
.688#.019
H-GRAM(HAT)
.62.1.032
.7774.028
.5734.048
.7944.023
.7324.021
H-GRAM(ours)
4721.035
.7864.031
.884.004
.844.001
.742:.013
Conclusion
In this paper, we introduce H-GRAM, scalable hyperbolic meta- meta-learning model that is able to learn inductive biases from support set and adapt to a query set with disjoint nodes, edges, and labels by transferring the knowledge. We have theoretically proven the effectiveness of node-centric subgraph information HNN models, and used that to formulate meta-learning model that can scale over large datasets. Our model is able to handle challenging few-shot learning scenarios and also outperform the previous Fuclidean baselines in the area of meta-learning. Additionally, unlike previous HNN models, H-GRAM is also able to scale to large graph datasets.
10

---

References
[1] Ivana Balažević, Carl Allen, and Timothy Hospedales. Multi-rclational poincaré graph embed- dings. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, Red Hook, NY, USA, 2019. Curran Associates Inc.
[2] Silvère Bonnabel. Stochastic gradient descent on riemannian manifolds. JEEE Transactions on Automatic Control, 58(9))2217-22299 2013. doi: 10. 10.1109/TAC.2013.22555
[3] Avishek Joey Bose, Ankit Jain, Piero Molino, and William L. Hamilton. Meta-graph: Few shot link prediction via meta learning, 2020. URL BJepcaEtwB
[4] Ines Chami, Zhitao Ying, Christopher Ré, and Jure Leskovec. Hyperbolic graph convolutional neural networks. Advances in neural information processing systems, 32, 2019.
[5] Ines Chami, Adva Wolf, Da-Cheng Juan, Frederic Sala, Sujith Ravi, and Christopher Ré. Low-dimensional hyperbolic knowledge graph embeddings. In Proceedings of the 58th An- nual Meeting of the Association for Computational Linguistics, pages 6901-6914 Online, July 2020. Association for Computational Linguistics. doi: 10. a URL https://aclaatthology org/ 2020 acl-
[6] Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Measuring and relieving the over-smoothing problem for graph neural networks from the topological view. Proceedings of the AAAI Conference on Artificial Intelligence, 34(04):3438 3445, Apr. 2020. doi: 10. 1609/aaai 1310044.....144447..... URLhttps: //ottss//ojj... aaai org index. php/ phtp/AAATaattcleee...p htt/aarrrcccleiieeo//eeoo
5747
[7] Mingyang Chen, Wen Zhang, Wei Zhang, Qiang Chen, and Huajun Chen. Meta relational learning for few-shot link prediction in knowledge graphs. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th Interna- tional Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pages 4208- 4217, Hong Kong, China, November 2019, Association for Computational Linguisties. URL https:// http://wwwwwwlwwbbb/pp acwweb..wb......... org./antholog//D1--1555 1431
[8] Nurendra Choudhary, Nikhil Rao, Sumeet Katariya, Karthik Subbian, and Chandan K. Reddy. supervieed hyperboloid representations from logical queries over knowledge graphs. In Proceedings of the Web Conference 2021, WWW '21, page 1373-1384, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 978 4503831 doi: 10. 10.1145/3442381.
3449974. URL
org/ htte//.0..155/34440 1145/3442381 43444994442213444997444 3449974
[9] Nurendra Choudhary, Nikhil Rao, Sumeet Katariya, Karthik Subbian, and Chandan K. Reddy. Anthem: Attentive hyperbolic entity model for product search. In Proceedings of the Fifteenth
ACM International Conference on Web Search and Data Mining, WSDM '22, page 161-171, New York, NY, USA, 2022. Association for Computing Machinery. ISBN 978 145039 320. 01411114413850 3498456
doi: 00.114/3448360.3498/8.8 URL httptttss////i..oot
[10] Nurendra Choudhary, Nikhil Rao, Karthik Subbian, Srinivasan H. Sengamedu, and Chandan K. Reddy. Hyperbolic neural networks: Theory, architectures and applications. In Proceed- ings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD) *22, page 4778-4779, New York, NY, USA, 2022. Association for Computing Machinery. htRpshtts::///al oroeiiorr/111.1 1145/
ISBN 4781450393850.. doi: 10. 10.1145/3534688.5544
3584678.3542613
[11] Bhuwan Dhingra, Christopher Shallue, Mohammad Norouzi, Andrew Dai, and George Dahl. Embedding text in hyperbolic spaces. In Proceedings of the Twelfth Workshop on Graph- Based Methods for Natural Language Processing (TextGraphs-12), pages 59-69, New Or- leans, Louisiana, USA, June 2018. Association for Computational Linguistics. doi: 10.18653/ v1/W18- 17088-178.. URL
1708
[12] Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adap- tation of deep networks. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, ICML' 17, page 1126-113 1135. JMLR.org, 2017.
11

---

[13] Octavian Ganea, Gary Bécigneul, and Thomas Hofmann. Hyperbolic neural networks. Ad- vances in neural information processing systems, 31, 2018.
[14] Ning Gao, Hanna Ziesche, Ngo Anh Vien, Michael Volpp, and Gerhard Neumann. What mat- ters for meta-learning vision regression tasks? In 2022 IEEE/CVF Conference on Computer Vi- sion and Pattern Recognition (CVPR), pages 14766, 2022. doi: 10. 109/ 2022.01436.
[15] Caglar Gulcehre, Misha Denil, Mateusz Malinowski, Ali Razavi, Razvan Pascanu, Karl Moritz Hermann, Peter Battaglia, Victor Bapst, David Raposo, Adam Santoro, and Nando de Fre- itas. Hyperbolic attention networks. In International Conference on Learning Representations, 2019. URL URL httptt:t//ppeereeeeeeee
[16] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Guyon, U. Von Luxburg, S. Bengio, H. Wallach, Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems. volume 30. Cur- ran Associates, Inc., 2017. URL wttptttss///p/oeeddaaae wtt.://s.....p.pp////1/...... pdff
[17] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.0066: 2020.
[18] Kexin Huang and Marinka Zitnik. Graph meta learning via local subgraphs. Advances in Neural Information Processing Systems, 33:5862-5874, 2020.
[19] Mehrdad Khatir, Nurendra Choudhary, Sutanay Choudbury, Khushbu Agarwal, and Chan- dan K. Reddy. A unification framework for euclidean and hyperbolic graph neural networks. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI 2023, 19th-25th August 2023, Macao, SAR, China, pages 3875-3883. ijcai.org, 2023. 14963//jcca1 2023/431
doi: 01.24963/jcai.2222332/
URL
[20] Thomas N Kipf and Max Welling. Variational graph auto-encoders. NIPS Workshop
Bayesian Deep Learning, 2016.
[21] Max Kochurov, Rasul Karimov, and Serge Kozlukov. Geoopt: Riemannian optimization in pytorch. arXiv preprint arXiv:2005.02819 2020.
[22] Hung-yi Lee, Shang-Wen Li, and Thang Vu. Meta learning for natural language processing: A survey. In Proceedings of the 2022 Conference of the North American Chapter of the Associ- ation for Computational Linguistics: Human Language Technologies, pages 666-684, Seattle, United States, July 2022. Association for Computational Linguistics. doi: 10.18653/v1/2000 mhacl-main44 URL
org.ogg////// 2022 naaca-aaalmannaaa 49
[23] Lu Liu, Tianyi Zhou, Guodong Long, Jing Jiang, and Chengqi Zhang. Learning to Propagate for Graph Meta-Learning. Curran Associates Inc., Red Hook, NY, USA, 2019.
[24] Galileo Mark Namata, Ben London, Lise Getoor, and Bert Huang, Query-driven active sur- veying for collective classification. In International Workshop on Mining and Learning with Graphs, Edinburgh, Scotland, 2012.
[25] Marion Neumann, Plinio Moreno, Laura Antanas, Roman Garnett, and Kristian Kersting- Graph kernels for object category prediction in task-dependent robot grasping. In Online pro- ceedings of the eleventh workshop on mining and learning with graphs, pages 0-6, 2013.
[26] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Des- maison, Andreas Kopf. Edward Yang, Zachary DeVito, Martin Raison, Alykhan Te- jani, Sasank Chilamkurthy. Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chin- tala. Pytorch: An imperative style, high-performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Bue, E. Fox, and R. Gar- netr, editors, Advances Neural Information Processing Systems 32, pages 8024- 8035. Curran Associates, Inc.. 2019. URL http:://apen newrips. neurips.cc/paper.
12

---

9015 pytorch-an an- pdf
library
[27] Nataša Pržulj. Biological network comparison using graphlet degree distribution. Bioinfor- matics, 23())e17--e183, 2007.
[28] Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In International Conference on Learning Representations, 2018. URL httpp:://oppereeiiiee
het//forurPid-ry(uff--3
[29] Ryan A. Rossi and Nesreen K. Ahmed. The network data repository with interactive graph analytics and visualization. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, 15, page 4292-4293, AAAI Press, 2015. ISBN 0262511290.
[30] Juwen Shen, Jian Zhang, Xiaomin Luo, Weiliang Zhu, Kunqian Yu, Kaixian Chen, Yixue Li, and Hualiang Jiang. Predicting protein-protein interactions based only on sequences informa- tion. Proceedings of the National Academy of Sciences, 104(11): (04(11):43774444) 2007.
[31] Jake Snell, Kevin Swersky, and Richard Zemel. Prototypical networks for few-shot leamn ing. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30, Cur- ran Associates, Inc., 2017. httpp.tttt:s///o/ottttt 7ataa677776661111222222222666622
www.:ne.iiipccmmm httparpppp.ccppppp////////// pdf
[32] Jianing Sun, Zhaoyue Cheng, Saba Zuberi, Felipe Perez, and Maksims Volkovs. Hgef: Hyperbolic graph convolution networks for collaborative filtering. In Proceedings of the Web Conference 2021, WWW '21, page 593-601, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781450383127.
doi: 10.1145/3442381 14144///42381.4450100 33500101. URL
http::/ddoo..rgg1// 1141/ 3450101
[33] Abraham A Ungar. Analytic hyperbolic geometry: Mathematical foundations and applica- tions. World Scientific, 2005.
[34] Ricardo Vilalta and Youssef Drissi. A perspective view and survey of meta-learning. Artificial intelligence review, 18(2):77-99) 2002.
[35] Anoushka Vyas, Nurendra Choudhary, Mehrdad Khatir, and Chandan K. Reddy. Graphzoo: A development toolkit for graph neural networks with hyperbolic geometries. In Companion Proceedings of the Web Conference 2022, WWW '22, page 184-188, New York, NY, USA, 2022. Association for Computing Machinery. ISBN 978 07774445331100 doi: 10.1 10.1145/3487553. 3524241. URL https::/doi. org/ 10. 1145/3487553 3524241
[36] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In Proceedings of the 36th International Confer- ence on Machine Learning, pages 6861-6871, PMLR, 2019.
[37] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019. URL https:
[38] Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. GraphSAINT: Graph sampling based inductive learning method. In International Confer- ence on Learning Representations, 2020. URL https://openreviee.. wtw.:/wwwwwetffooumiimmcm
BJe8pkHFwS
[39] Chuxu Zhang, Huaxiu Yao, Chao Huang, Meng Jiang, Zhenhui Li, and Nitesh V Chawla. Few-shot knowledge graph completion. In Proceedingy of the AAAI Conference on Artificial Intelligence, volume 34, pages 3041-3048, 2020.
[40] Fan Zhou, Chengtai Cao, Kunpeng Zhang. Goce Trajcevski, Ting Zhong, and Ji Geng- Meta-gnny gita: On few-shot node classification in graph meta-learning. In Proceedings of the 28th ACM International Conference on Information and Knowledge Management, CIKM New York, NY, USA, 2019. Association for Computing Machinery. doi: 10.1 DD.114553357384.35555 06. URL htttttsss//ii.rg/////// 1145/
'19 page 2357-23667
ISBN 97814603
3857384
335733843358106 3358106
13

---

[41] Fan Zhou, Chengtai Cao, Goce Trajcevski, Kunpeng Zhang, Ting Zhong, and Ji Geng. Fast network alignment via graph meta-learning. In IEEE INFOCOM 2020 IEEE Conference on Computer Communications, pages 686-695, 2020. 9155456.
doi: 10.1 10.1099INFOCMM4144:20000
[42] Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li. and Maosong Sun. Graph neural networks: A review of methods and applications. Al Open, 1:57-81, 2020. ISSN 2666-6510. doi: http:///di.org/10..0011 Laiopen.2021.01.000 http:://///ww $2666651021000012
BtRpsttp::
[43] Marinka Zitnik and Jure Leskovec. Predicting multicellular function through multi-layer tissue networks. Bioinformatics, 33(11)::190-i198, 2017.
[44] Marinka Zitnik, Rok Sosiè, Marcus W. Feldman, and Jure Leskovec. Evolution of resilience in protein interactomes across the tree of life. Proceedings of the National Academy of Sciences, 116(10):426 44333, 2019. doi: 10. 107330//ps 1818013116, URL https: : //www//www.. pnas .
doi/abs/ 1073//0a3.pp./ pnas. 1818013116
14


Reviews:
[{"review_id": "vQtHfWxd7a", "reviewer": "Reviewer_4N27", "summary": "This paper introduces H-GRAM, a novel meta-learning model for scalable Hyperbolic Graph Neural Networks. H-GRAM leverages meta-learning techniques to learn from from local subgraphs and adapt quickly to new tasks. The authors theoretically establish that HNNs are dependent on the local neighborhood of nodes for prediction and formulate HNNs to encode node-centric local subgraphs using the locality of tangent space transformations. Experiments conducted on various benchmark datasets to illustrate that H-GRAM addresses several HNNs tasks such as inductive learning, over-smoothing elimination, and few-shot learning in various demanding situations.", "questions": "I don't have further questions.", "limitations": "The authors adequately addressed the limitations.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The paper presents a novel approach that combines hyperbolic geometry and meta-learning techniques, which is innovative and interesting.\n- The proposed H-GRAM is scalable and efficient compared to previous HNN techniques.\n- Extensive and carefully designed experiments have been conducted to demonstrate the effectiveness of H-GRAM\n", "weaknesses": "For results listed in table 2, why did H-GRAM never achieve the best performances for both of node classification and link prediction at the same time among all datasets? Could you explain the reason behind this discrepancy between tasks?\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to express our gratitude for your thorough review of our paper. We value the time and effort you have dedicated to evaluating our work and providing valuable feedback. We acknowledge your positive remarks on the novelty and innovation of our approach, which combines hyperbolic geometry and meta-learning techniques to create the Hyperbolic GRAph Meta Learner (H-GRAM). We are pleased that you find our work scalable and efficient compared to previous Hyperbolic Neural Network (HNN) techniques. Additionally, your recognition of the extensive experiments we conducted to demonstrate H-GRAM's effectiveness in addressing various HNN tasks, such as inductive learning, over-smoothing elimination, and few-shot learning, is greatly appreciated.\n\nW1. Regarding the discrepancy between node classification and link prediction performances in Table 2, we recognize that our model may not always achieve the best results for both tasks simultaneously across all datasets. This behavior is attributed to the inherent trade-offs in hyperbolic geometry and our meta-learning approach when dealing with different tasks. H-GRAM's focus on fast adaptation and few-shot learning prioritizes aggregating messages from local subgraphs, which is required for node classification, whereas, link prediction requires good message passing ability across subgraphs which is limited when we partition the graph to enable scalability. However, we want to reiterate that our primary contribution lies in addressing the limitations of HNNs (it is impossible to train basic HNNs on large graphs) and achieving better scalability using meta-learning techniques in the hyperbolic space. In this context, H-GRAM consistently outperforms other state-of-the-art baselines in various challenging few-shot settings, which aligns with the core focus of our work.\n\nIn conclusion, we believe that the combination of hyperbolic geometry and meta-learning techniques presented in H-GRAM holds significant potential in the domain of graph representation learning. We hope that our additional clarifications on the discrepancy in task performance and the overall contributions of our work will lead to a more positive evaluation. Once again, we sincerely appreciate your feedback and consideration of our paper for NeurIPS. Your review has been invaluable in helping us improve the clarity and impact of our work."}, {"review_id": "d8aw4FrxZm", "reviewer": "Reviewer_UWvg", "summary": "The authors propose applying the MAML methodology to hyperbolic GNNs in a novel local manner, along with continuous label prototypes, that enables them to scale the HNN approach from a few thousand nodes to a few million nodes.\nThe authors provide theoretical justification for this local H-GRAM approach via theorems 1 and 2 and demonstrate its efficacy via a large set of experimental comparisons in Sec. 4 and 5.\n", "questions": "Please note the questions inherent in weakness 2, 3 and 4.", "limitations": "It is not clear if weakness 2 above constitutes a limitation or whether it is simply a case where no theoretical justification can be provided for an ulterhyperbolic-GRAM variant, for example.\n", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The four research questions from Sec. 4 regarding the novel HGRAM approach are comprehensively answered via comparison on multiple different datasets with competing Euclidean MAML approaches, standard hyperbolic baselines, other graph MAML approaches such as G-Meta [17], Meta-GNN [38], protoNET[29] and ablation studies. H-GRAM clearly outperforms competing meta-learning / protoNET approaches on large graphs in Table 1 and is comparable with competing hyperbolic approaches on small graphs in Table 2.\n\n2. The authors provide theoretical justification for their local H-GRAM approach via theorems 1 and 2.\n", "weaknesses": "1.\nSome of the mathematical presentation could be shortened, e.g., the same symbol $D_{g\\mu}^{p_i}$ is defined in both theorems 1 and 2. \n\n2.\nThe authors limit their meta-learning enhancements to hyperbolic neural networks, but it is not clear if their enhancements can be applied to superior pseudo-Riemannian approaches, e.g., Pseudo-Riemannian Graph Convolutional Networks, NeurIPS 2022, and Ultrahyperbolic Neural Networks, NeurIPS 2021.\n\n3.\nThe authors' approach seems quite similar to G-Meta [17], although their experimental results seem to be slightly better in Table 1. Presumably it is the hyperbolic modeling (and RSGD) or the continuous label prototypes that allows H-GRAM to outperform G-Meta, but such explanations or other explanations are not discussed.\n\n4.\nIn Sec. 5.4, it is not discussed why HGCN outperforms HMLP and HAT. In other studies, attention-based GNNs sometimes outperform GCNs, so some explanation appears to be necessary. The SG, SL setting on the Cora dataset from Table 2 could be considered in the ablation study in Table 3 to help answer this question.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to express our sincere appreciation for your positive feedback and constructive criticism of our paper. Your insights have been invaluable in helping us improve the clarity and impact of our work. \n\nW1. We understand your concern about the mathematical presentation and agree that some parts could be shortened for better readability. We will revise the paper accordingly to ensure that the notation is clear and concise while maintaining the rigor of our approach.\n\nW2. Regarding the limitation you pointed out about the application of our enhancements to pseudo-Riemannian approaches such as Pseudo-Riemannian Graph Convolutional Networks and Ultrahyperbolic Neural Networks, we acknowledge that our focus was on hyperbolic neural networks. However, we believe that the core ideas from our approach, such as the local H-GRAM methodology and continuous label prototypes, have the potential for generalization to pseudo-Riemannian settings. We will include a discussion in the revised paper to address this possibility and explore potential avenues for future research in this direction. This will be a future work and will be considered to be an orthogonal research direction.\n\nW3. Regarding the similarities between our approach and G-Meta [17], we agree that both methods leverage meta-learning techniques. However, there are significant differences in the underlying modeling. The advantage of H-GRAM lies in its ability of scaling hyperbolic modeling, which allows it to outperform G-Meta on large graphs (as shown in Table 1). To understand the exact strengths of the individual components in H-GRAM, we refer the reviewer to Section 5.4 that details the ablation study which highlights the strengths of different modules used in H-GRAM.\n\nW4. In Section 5.4, where HGCN outperforms HMLP and HAT, we acknowledge the need for further explanation. However, due to the limited number of pages we opted for brevity on performance not directly relevant to the main focus of our paper. Essentially, while attention networks are generally more performant than convolution networks, hyperbolic formulation needs certain approximations on the linear layers which leads to a minor information loss. Due to the comparatively more complex formulation of attention networks, the information loss has higher propagation in HAT. This approximation loss leads to lower performance of HAT than HGCN in certain cases.  We will include these findings in the revised paper and provide a comprehensive discussion of the results to address this question effectively.\n\nIn conclusion, we are grateful for your insightful feedback, and we are committed to addressing all the points you raised to enhance the quality and contribution of our work. We believe that the revisions will lead to a more comprehensive understanding of our approach's capabilities and potential. Once again, thank you for your thoughtful review and consideration of our paper for NeurIPS.\n"}, {"review_id": "khpImaA9qs", "reviewer": "Reviewer_qW7m", "summary": "The paper introduces a method, Hyperbolic GRAph Meta Learner (H-GRAM), to improve the scalability and generalization of Hyperbolic Neural Networks (HNNs). H-GRAM learns from local subgraphs and transfers this learning to new, disjoint subgraphs in a few-shot setting. The authors demonstrate that H-GRAM outperforms existing methods in various few-shot settings and scales effectively over large graph datasets.", "questions": "see weaknesses \n\nAdditionally, a lot of HNN or HGNNs are formulated within the manifold. \n\nCould you deduce the node influence and establish the information loss without utilizing a logarithmic map (i.e., relying on tangent space)? \n\nIf you use a logarithmic map, could you derive the conclusion using a local reference point other than the origin point since you say that \"we use the local tangent space of Poincare ball model to prove that the local neighborhood policy holds better for HNN models?\"", "limitations": "not mentioned.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper presents a new approach, H-GRAM, that combines meta-learning with hyperbolic neural networks (HNNs) to address their scalability and generalization issues. The quality of the work is evident in the detailed explanation of H-GRAM and its demonstrated effectiveness in comparison with baselines. ", "weaknesses": "* There are a few areas where it could potentially be improved:\n\n  * Comparison with Other Meta-Learning Approaches: The paper could include a comparison of H-GRAM with other meta-learning approaches in table 2 and 3, not just with other HNNs. This would provide a broader context for understanding the performance and advantages of H-GRAM.\n\n* Limited contribution\n\n  * This work seems just extend paper[1]'s work to hyperbolic and present some trivial definitions and theorem.\n  * Lack of important references [2-4] to make comparisons.\n[1]Huang, Kexin, and Marinka Zitnik. \"Graph meta-learning via local subgraphs.\" Advances in neural information processing systems 33 (2020): 5862-5874. The proposed method is close to this paper. Please make a detailed comparison with the method.\n\n[2] Yu, Tao, and Christopher De Sa. \"Random Laplacian Features for Learning with Hyperbolic Space.\" arXiv preprint arXiv:2202.06854 (2022). They also said that their method is scalable. Please compare with their method.\n\n[3] Zhang, Yiding, et al. \"Lorentzian graph convolutional networks.\" Proceedings of the Web Conference 2021. 2021. They developed a new HGNN with the aggregation in the manifold, could you provide your definition and theorem in such a case?\n\n[4] Yang, Menglin, et al.  HGCN: Tree-likeness Modeling via Continuous and Discrete Curvature Learning. KDD 2023. They also derive the node influence in the case of tangent space.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our paper. We appreciate your time and thoughtful evaluation of our work. We are pleased that you found the approach of H-GRAM intriguing and recognized its potential in improving the scalability and generalization of Hyperbolic Neural Networks (HNNs).\n\nW1. Regarding the weakness raised about the limited comparison with other meta-learning approaches, we focussed on foundational approaches that were directly relevant to the HNN and meta-learning aspects of our work’s advancement of the field. Additionally, due to the generalizable nature of our work, other comparisons can be drawn through relative study of the given references.\n\nW2. Regarding the point about emphasizing our contribution, we want to clarify that our work represents a significant breakthrough in the field of HNNs. Specifically, it enables the scaling of these networks to large graphs (with nodes and edges in the order of millions), which was previously a challenging task. To the best of our knowledge, there is currently no other existing research that successfully harnesses the inductive biases (with theoretical rigor) of HNNs for achieving scalability in the same way we have accomplished. This breakthrough opens up an entirely new avenue for achieving performance gains by leveraging the inherent hierarchical structure of graphs. The implications of this advancement are promising and hold the potential to pave the way for further advancements in the domain of large-scale graph processing.\n\n\nRegarding the questions raised:\n\nQ1. Deduction of Node Influence without Logarithmic Map: While we understand the interest in exploring alternative approaches, the use of the logarithmic map is essential in our methodology for modeling node influence effectively. It allows us to establish the local neighborhood policy for HNN models in a robust manner with theoretical justification. We will, however, discuss the possibility of providing additional insights using different techniques without compromising the integrity of our approach.\n\nQ2. Derivation Using a Local Reference Point: We appreciate your suggestion. However, the use of the local tangent space of the Poincare ball model is a fundamental choice grounded in our theoretical analysis, and it has proven to be effective in establishing the local neighborhood policy for HNN models. Choosing points other than the origin could lead to instability in the formulation as different graph partitions would have different definitions of hierarchy. This would necessitate the use of another model to track the relative positioning of the different roots, adding additional scope of errors. \n\nIn conclusion, we are grateful for your feedback, and we are committed to improving our paper based on your valuable comments. We believe that the suggested enhancements will strengthen the quality and impact of our work. Thank you again for your thoughtful review and consideration of our paper for NeurIPS.\n"}, {"review_id": "vk7zfbGHvy", "reviewer": "Reviewer_Urvd", "summary": "This submitted work identifies an important research problem of existing works, scalability of hyperbolic neural network to large graphs and previously unseen graphs. To achieve these two goals, this work first proves that node classification and link prediction can be done with a node's local neighborhood only. Based on this insight, this work designs a meta-learning mechanism for hyperbolic graph neural networks to scale on large graphs. Experiments on both small and large graphs show the effectiveness of the proposed model.", "questions": "1. Why is standard deviation at Table 1 absent?\n\n2. This paper uses Poincare ball as the hyperbolic model for illustration. I am wondering if the proposed model is also applicable when Hyperboloid model is used.", "limitations": "I can't see any potential negative societal impact of their work.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. This paper proposes an interesting and important research problem, scalability of hyperbolic graph neural networks on large datasets. With a theoretical analysis and a meta-learning based model achitecture, this paper shows promising performance over baseline models.\n\n2. This paper is self-contained, with enough introduction to background knowledge, such as meta-learning and operations in hyperbolic space, in Appendix.\n\n3. Experiments are comprehensive with both small and large graphs, with baselines from different categories, and with both node classification and link prediction tasks.", "weaknesses": "1. Introduction section contains too much redundant content. Introduction section should provide a general and overall picture of the paper, while this submitted work introduces too much model architecture and details in the Intro section. I suggest authors to remove some content and better emphasize the key innovation proposed in the paper. Paper writing can be imporved.\n\n2. I can see standard deviation of experiment results in most of the tables, but Table 1 doesn't have std. dev. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your thorough review of our paper and are pleased that you recognize the importance of the research problem we address, the scalability of hyperbolic neural networks on large datasets and previously unseen graphs, and the promising performance of our proposed model. Regarding the strengths of our paper, we are glad that you find our research problem interesting and important. We agree that the theoretical analysis and meta-learning-based model architecture contribute to the promising results compared to baseline models.\n\nW1. We acknowledge your feedback regarding the Introduction section. We sincerely apologize for the redundancy in our communication. While our primary aim was to emphasize the novelty of the content, we inadvertently allowed repetition to creep into the text. In the revised version, we will streamline the content to provide a clearer and more concise overview of the paper.\n\nW2 & Q1. Regarding the absence of standard deviation in Table 1, it was only a choice due to limited space. We have included the standard deviation values of Table 1 in Appendix Table 6 to provide a comprehensive view of the variability of our results. We shall also include them in our codebase.\n\nQ2. To address your question about the applicability of our proposed model when using the Hyperboloid model, we believe that the core ideas and methodologies of H-GRAM are trivially adaptable to other hyperbolic models, including the Hyperboloid model, which is isometric to the currently tackled Poincaré model. One possible approach could be to use the current Poincaré model formulations and use the isometric mappings for the hyperboloid model.\n\nIn conclusion, we sincerely appreciate your feedback, and we are committed to improving our paper based on your valuable comments. We believe that addressing the mentioned points will lead to a higher rating for our paper and enhance its contribution to the field of hyperbolic graph neural networks. Thank you again for your thoughtful review and consideration of our paper for NeurIPS.\n"}, {"review_id": "k3kqdSWLAi", "reviewer": "Reviewer_Ft7q", "summary": "This paper introduces the model, Hyperbolic GRAph Meta Learner (H-GRAM), that learns transferable information from a set of support local subgraphs using hyperbolic meta gradients and label hyperbolic protonets to enable faster learning over a query set of new tasks disjoint subgraphs. The model is evaluated on downstream tasks of both node classification and link prediction. The experiments and ablation studies show that H-GRAM effectively learns and transfers information in few-shot settings and outperforms its Euclidean counterparts.", "questions": "Please see weaknesses section above.", "limitations": "Authors have sufficiently identified limitations of the prior work and addressed it in their proposed model. It would also be helpful if the authors provide future directions for their work. ", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "In general, the paper is well written and the model introduces some novel contributions. Further, regarding experiment results, the model seems outperform all the baselines consistently on tasks of link prediction and node classification. The ablation studies from varying the base HNN model and deleting individual meta-learning components are informative to better understand the influence of the various components in the model and the final proposed architecture. ", "weaknesses": "- In the Related Work section on Hyperbolic Neural Networks, the following important reference is missing regarding HNNs for large scale datasets (from the knowledge graph domain) from recent work:\n\n[KDD 2022] Dual-Geometric Space Embedding Model for Two-View Knowledge Graphs. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD '22). Association for Computing Machinery, New York, NY, USA, 676–686. https://doi.org/10.1145/3534678.3539350\n\n- In the problem setup section, can the authors more clearly explain the properties of the graph (e.g., directed/undirected, what do the nodes/edges represent etc.)?\n\n- Regarding experiments, it would be useful to see the model performance on both inductive as well as transductive tasks. Furthermore, can the authors provide more details on the dataset statistics such as number of vertices and edges and the domain of the dataset to get a better indication of the data size?\n\n- I also have a concern about the scalability of the model especially since non-Euclidean space embedding models tend to converge very slowly and Mobius computations are more computationally expensive compared to the Euclidean space. Can the authors provide some model complexity analysis (e.g., runtime/memory complexity)? \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your insightful review of our paper. Your feedback has been invaluable in identifying areas for improvement, and we are committed to addressing your comments to enhance the quality and impact of our work. We are delighted that you find our paper well-written and recognize the novel contributions of our model, H-GRAM. We agree that the experiment results demonstrate consistent outperformance of H-GRAM over baselines on both link prediction and node classification tasks. We are glad that the ablation studies were informative in understanding the influence of various components in the proposed architecture.\n\nW1. Regarding the [KDD 2022] reference, we believe that it is orthogonal to our work because it addresses a different research topic than the abstract's main focus, which is HNNs and their inductive bias mechanisms for generalization and scalable learning. Our paper primarily addresses the limitations of current hyperbolic neural networks due to their lack of inductive bias mechanisms and proposes a novel method to alleviate these issues. On the other hand, the referenced paper focuses on embedding KGs in a dual-geometric space for the purpose of knowledge graph analysis or other related tasks. It does not address the inductive bias mechanisms or the few-shot learning setting that the abstract's H-GRAM method deals with.\n\nW2. In the problem setup section, we have relied on standard experimental setups in this problem for fair comparison. Due to the limited space and availability of this information in previous work, we placed the section on dataset details in Appendix F.\n\nW3. Regarding the experiments, we acknowledge the importance of evaluating both inductive and transductive tasks. Due to the nature of problem setup, all the meta-learning methods and comparisons provided in Table 1 and 3 operate in an inductive setting, whereas in Table 2 which details of comparison of hyperbolic approaches are evaluated on a transductive setting. The problem setting does not rely on the potential of H-GRAM rather it is dependent on the standards of traditional evaluation procedure of the baseline methods for fair comparison.\n\nW4. Furthermore, we understand the concern about the scalability of non-Euclidean space embedding models and the computational expense of Mobius computations. However, due to operating on small graph partitions, the additional computation required for Mobius operations is negligible when compared to Euclidean methods (single GCN and HGCN layer of 128 input dimensions take 0.195s vs 0.267s in our experiments, respectively). Furthermore, the primary contribution of the paper, approaches previous to H-GRAM, could not even train on such large graphs, so the performance improvement of hyperbolic networks was inaccessible due to the lack of scalability over large graphs.\n\nThank you for your encouraging confidence in our paper. We are committed to addressing all your feedback and ensuring that the revised version of our paper meets the highest standards. Your valuable insights have been instrumental in guiding our revisions. Once again, we sincerely appreciate your thoughtful review and consideration of our paper.\n"}]

Author rebuttal:
Based on the valuable feedback from the reviewers, the key contributions of our paper lie in the introduction of H-GRAM, a novel meta-learning model for scalable Hyperbolic Graph Neural Networks. H-GRAM effectively leverages meta-learning techniques to learn from local subgraphs and adapt quickly to new tasks. We have demonstrated the model's superiority in addressing various HNN tasks, including inductive learning, over-smoothing elimination, and few-shot learning in demanding situations.

The global theme of our response revolves around addressing the reviewers' feedback to enhance the clarity, significance, and impact of our work. We will provide a clearer presentation of the introduction, emphasize the core contributions, and discuss potential future research directions. We are committed to revising our paper to meet the highest standards and sincerely thank the reviewers for their valuable insights.

Meta-review: This paper proposes a meta-learning method for hyperbolic graph neural networks. The proposed method uses hyperbolic meta gradients and label hyperbolic prototypes for effective meta-learning. The proposed approach is a novel combination of hyperbolic geometry and meta-learning techniques. The proposed method is scalable. The theoretical justification of the proposed method is also provided. The extensive experiments demonstrate the effectiveness of the proposed method. It would be good to add more explanation to clarify the contribution of the proposed method compared with existing work. Please improve the paper further according to the reviewers’ comments as responded in the author response.
Decision: Accept (poster)