PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph Meta Learning via Local Subgraphs

Kexin Huang, Marinka Zitnik

arXiv:2006.07889v4cs.LGstat.ML

TL;DR

Graph learning methods typically need abundant labels and edges, while new graph tasks may provide only a few examples. G-META addresses this gap with local-subgraph meta-learning, outperforming prior baselines and scaling across difficult graph and label-generalization settings.

  • Problem

    Prevailing GNN methods rely on extensively labeled datasets, leaving rapid learning from a few labeled nodes or edges underexplored on graphs.

  • Method

    G-META represents targets with local subgraphs, encodes them with a GNN, and combines prototypical loss with MAML for transfer across graphs and labels.

  • Results

    G-META outperforms nine baselines across seven datasets by up to 16.3% and scales to the 1,840-graph Tree-of-Life dataset.

  • Takeaways & Limitations

    G-META handles node classification and link prediction across new graphs and previously unseen or disjoint label sets in few-shot settings.

  • Takeaways & Limitations

    The authors caution that G-META targets few-shot settings and may provide limited benefit when labels are abundant; meta-learning can also suffer negative transfer.

Abstract

from arXiv · show

Prevailing methods for graphs require abundant label and edge information for learning. When data for a new task are scarce, meta-learning can learn from prior experiences and form much-needed inductive biases for fast adaption to new tasks. Here, we introduce G-Meta, a novel meta-learning algorithm for graphs. G-Meta uses local subgraphs to transfer subgraph-specific information and learn transferable knowledge faster via meta gradients. G-Meta learns how to quickly adapt to a new task using only a handful of nodes or edges in the new task and does so by learning from data points in other graphs or related, albeit disjoint label sets. G-Meta is theoretically justified as we show that the evidence for a prediction can be found in the local subgraph surrounding the target node or edge. Experiments on seven datasets and nine baseline methods show that G-Meta outperforms existing methods by up to 16.3%. Unlike previous methods, G-Meta successfully learns in challenging, few-shot learning settings that require generalization to completely new graphs and never-before-seen labels. Finally, G-Meta scales to large graphs, which we demonstrate on a new Tree-of-Life dataset comprising of 1,840 graphs, a two-orders of magnitude increase in the number of graphs used in prior work.

1 Introduction

Graph meta-learning addresses rapid learning from only a few labeled nodes or edges, where prevailing GNN methods and earlier graph meta-learning strategies face important limitations. G-META uses local subgraphs to support broad task generalization, accurate prediction, and scalability.

  • Few-shot graph learning targets rapid adaptation from only a few labeled nodes or edges, unlike standard evaluation with abundant labels.
  • G-META addresses single-graph disjoint-label, multiple-graph shared-label, and multiple-graph disjoint-label problems, and also supports link prediction.
  • Earlier graph meta-learning methods do not scale well or extend to the range of problems represented in Figure 1.
  • G-META represents each node with a local subgraph, using subgraph-specific information for meta-learning and transfer across tasks.The approach is theoretically motivated by evidence surrounding the target node or edge.
  • G-META outperforms nine baselines by up to 16.3% across seven datasets.
  • G-META scales to large graph collections through subgraph processing, including the 1,840-graph Tree-of-Life dataset.This represents a two-orders-of-magnitude increase over the number of graphs used in prior work.

2 Related Work

Related work places G-META among few-shot meta-learning and graph methods that model local subgraph structure. Its subgraph-based formulation differs from approaches that operate on entire graphs or node-embedding batches.

  • Few-shot meta learning: Few-shot meta-learning transfers prior experience to new tasks using only a few labeled examples.
  • Subgraphs and GNNs: Earlier graph meta-learning methods operate on entire graphs, whereas G-META extracts relevant local subgraphs and trains a GNN on each subgraph.
  • Subgraphs and GNNs: In Meta-GNN, a task is a batch of node embeddings; in G-META, a task is a batch of subgraphs.The passage associates this difference with rapid adaptation, scalability, and broader applicability.

3 Background and Problem Formulation

The paper formulates graph meta-learning over local subgraphs and three combinations of graph and label sharing. GNN propagation produces node representations, while meta-learning adapts from support examples to query examples.

  • 3 Background and Problem Formulation: A graph G=(V,E,X) contains nodes V, edges E, and node attribute vectors X={x1,...,xn}, with xu∈R^d.
  • 3 Background and Problem Formulation: G-META represents nodes with local subgraphs and maps each subgraph Su to labels using a GNN given only a handful of labeled nodes.
  • 3.1 G-META: Problem Formulation: G-META transfers knowledge across tasks, graphs, and label sets, adapting to a new task after observing related tasks.
  • 3 Background and Problem Formulation: GNNs generate representations through message passing, neighborhood aggregation, and nonlinear embedding updates.
  • 3 Background and Problem Formulation: Meta-learning separates tasks into support data for learning and query data for evaluation within a meta-set containing training, validation, and test tasks.
  • 3 Background and Problem Formulation: MAML seeks an initialization θ* that adapts quickly to unseen tasks using gradients learned during meta-training.
  • 3.1 G-META: Problem Formulation: The shared-label setting uses one label set across tasks, whereas disjoint-label settings require Yi∩Yj=∅ for distinct task label sets.
  • 3.1 G-META: Problem Formulation: The three problems are single graph with disjoint labels, multiple graphs with shared labels, and multiple graphs with disjoint labels.

4 Local Subgraphs and Theoretical Motivation for G-META

G-META uses local subgraphs to retain prediction-relevant information while reducing graph-wide computation. Theoretical results justify this choice by showing that node influence decreases with distance and local-subgraph approximation error is bounded.

  • Implications for meta-learning: G-META uses local subgraphs to capture graph structure, node features, and labels for graph meta-learning.The method is motivated by the claim that prediction evidence can be preserved around the target node or edge.
  • Local subgraph construction: Local subgraphs are induced by nodes within h hops of a target node and are encoded with GNNs.The neighborhood size h determines which nodes and edges are included around the target.
  • Theoretical motivation: Node influence decreases exponentially with distance, while accumulated node degrees along paths further dampen influence.Low-degree paths transmit influence more directly; highly connected paths introduce more complicated messages.
  • Theoretical motivation: The local-subgraph preservation property bounds graph influence loss by an exponentially decaying term as neighborhood size h increases.Thus, local subgraphs provide an h-th order approximation to applying a GNN over the entire graph.
  • Meta-learning procedure: During training, support subgraphs produce centroid embeddings and prototypes, support loss updates the GNN, and query loss drives the final meta-update.These task-level updates repeat across sampled tasks before meta-testing with the learned parameter θ∗.

5 G-META: Meta Learning via Local Subgraphs

G-META represents nodes with local subgraphs, encodes them with a GNN, and combines prototypical loss with MAML for transfer across graphs and labels. Its subgraph-based design supports few-shot adaptation with lower computational and memory demands.

  • Subgraph encoding: G-META first constructs a local subgraph for each node and uses a GNN to generate node embeddings within it.The centroid node embedding represents the local subgraph in the described implementation.
  • Prototypical loss: Prototypical loss computes one prototype per label from support embeddings and classifies support or query subgraphs by distances to those prototypes.The resulting class distributions are optimized with cross-entropy loss.
  • Optimization-based meta-learning: MAML transfers structural knowledge across graphs and labels by adapting the GNN on support subgraphs and evaluating updated parameters on query sets.Query losses are recorded across repeated task-level update steps and used for meta-learning.
  • Optimization-based meta-learning: The meta-learned parameter θ∗ is obtained from knowledge across meta-training tasks and is used to adapt quickly to unseen tasks.Meta-testing repeats the support-query procedure with the final meta-learned parameter.
  • Scalability: G-META operates on mini-batches of small local subgraphs and few-shot batches, reducing computation and memory requirements.Its smaller aggregation field is presented as the basis for scalability relative to prior approaches.

6 Experiments

Experiments evaluate G-META on synthetic and real-world graph meta-learning tasks, showing strong accuracy, local-structure capture, broad applicability, and scalability. Ablations indicate that both optimization-based meta-learning and prototypical loss contribute to performance, while subgraph size affects stability.

  • Datasets and setup: Experiments use synthetic datasets with labels tied to structural roles, real-world node and link prediction datasets, and newly constructed Fold-PPI data.The study also reports dataset statistics and evaluates few-shot settings using fixed meta-tasks rather than all available labels.
  • Overall results: G-META achieves the best accuracy in almost all tested graph meta-learning problems across node classification and link prediction.Results are reported for synthetic and real-world datasets using multi-class classification accuracy, with five-fold averages in the tabulated evaluations.
  • Overall results: 15.1% and 16.3% relative increases occur in the single-graph disjoint and multiple-graph disjoint-label settings, respectively, over the best-performing baseline.The gains are reported alongside adaptation using only a few gradient updates and examples on target tasks.
  • Local structure: Subgraph-based methods outperform entire-graph methods on synthetic datasets, indicating that subgraph embeddings capture local structural roles more effectively.In the single-graph disjoint-label setting, KNN achieves the best result, suggesting that the learned subgraph representation captures structural roles.
  • Generalization across problems: G-META is consistently better and more stable than MAML and ProtoNet across meta-learning models and works across problems where Meta-GNN and Meta-Graph are restricted.The study also observes that No-Finetune can outperform Finetune on ogbn-arxiv and Fold-PPI, indicating bias from meta-training datasets in meta-testing.
  • Scalability: Local subgraphs support scalability to a 160-thousand-node, 1-million-edge ogbn-arxiv graph and the 1,840-graph Tree-of-Life link-prediction dataset.The method examines small graph neighborhoods rather than operating over entire graphs.
  • Ablation and parameters: Both optimization-based meta-learning and prototypical loss improve predictive performance, while h = 2 provides the most stable subgraph-size performance.Increasing the number of shots produces a linear trend in predictive performance; h = 3 can add information or introduce noise depending on the dataset.

7 Conclusion

The paper presents G-META as a scalable, inductive graph meta-learning method based on local subgraphs. It is designed for difficult few-shot settings and multiple graph meta-learning problems, with evaluations across seven datasets including a new 1,840-graph dataset.

  • Conclusion: G-META uses local subgraphs to identify and transfer useful information across tasks instead of relying on entire-graph representations.The approach is theoretically motivated by evidence for predictions being found around target entities.
  • Conclusion: G-META addresses difficult few-shot learning tasks and a variety of graph meta-learning problems while outperforming nine baselines across seven datasets.The evaluation includes the newly introduced Tree-of-Life dataset containing 1,840 graphs.

Broader Impact

Graph meta-learning addresses scarce-label graph applications by transferring knowledge across related graphs or label sets. G-META is presented as a scalable approach, with potential applications and risks spanning scientific discovery, business, equality, negative transfer, misuse, and adversarial attacks.

  • Motivation: Meta learning supports rapid adaptation to graph tasks using few labeled nodes or edges, complementing graphs’ broad application potential.The paper positions graph meta-learning at the intersection of graph machine learning and few-shot learning.
  • Potential benefits: G-META is intended to leverage related graphs or label sets when graph labels are scarce or links are missing.The stated target tasks include node classification and link prediction under low-resource constraints.
  • Applications: The paper identifies scientific discovery, economic value, and equality as application areas for graph meta-learning.Examples include expensive molecular labels, recommendations for new product sets, and infrastructure planning in rural regions.
  • Risks: Potential risks include negative transfer, limited benefit when labels are abundant, and vulnerability to adversarial attacks in few-shot settings.The paper notes that each labeled example may be vital for prediction when labels are scarce.
  • Applicability: G-META’s broader applicability is contrasted with existing methods that cannot tackle all listed graph meta-learning problems.Table 5 compares methods across different graph meta-learning problems.

C.3 Theorem and Proof

The theorem and proof analyze how node influence propagates through a GCN. They show that influence is bounded through paths and decreases with path length and the geometric mean of node degrees.

  • Theorem 1: Theorem 1 establishes a decaying property for node influence between nodes connected by a path.The bound uses a constant, path length, and the geometric mean of node degrees along the path.
  • Proof: Under the stated GCN assumptions, the node output is expanded through neighboring nodes and then through longer paths.The proof uses the propagation rule, edge weights, and repeated neighborhood expansion.
  • Proof: The influence calculation decomposes into contributions from paths between the target nodes, with non-path nodes contributing zero to the relevant derivative.The proof then isolates the maximum path contribution.
  • Interpretation: When node degrees along paths are treated as random, the path with the smallest geometric mean of node degrees is the shortest path.This is stated as an additional assumption-based interpretation of the maximizing path.

Appendix D Theorem 2 and its Proof

Theorem 2 formalizes local subgraph preservation for G-META. Its proof connects graph influence loss to the most influential node outside a target node’s h-hop neighborhood, while the algorithm applies subgraph-based inner and outer updates.

  • Theorem 2: Theorem 2 defines local subgraph preservation for a node using a neighborhood of size h and the most influential node outside that neighborhood.The theorem introduces a path and geometric-mean degree quantity for the external node.
  • Proof: The proof begins from graph influence loss and bounds omitted influence using the node outside the local neighborhood with the highest influence.Nodes outside the neighborhood are more than h hops from the target node.
  • Algorithm: G-META constructs local subgraphs, samples meta-tasks, processes support and query subgraphs, and performs inner-loop and outer-loop updates.The algorithm’s steps include support prototypes, support loss, query loss, and meta-gradient updates.
  • Implementation: The implementation and datasets, including data loaders, are made available through the project repository.The paper states that the G-META implementation and relevant resources are available online.

F.1 Synthetic Datasets

The synthetic datasets evaluate whether G-META captures labels tied to local network structure. They use planted shapes, structural roles, and noise across single-graph and multiple-graph settings, alongside real-world datasets and baseline comparisons.

  • Synthetic dataset design: The synthetic datasets assign labels according to local structural roles and are designed to test G-META’s ability to capture local network structures.One construction uses cycle-basis networks with planted House, Star, Diamond, and Fan shapes plus random-edge noise.
  • Synthetic dataset design: The single-graph and disjoint-label setting uses 500 cycle-basis nodes, 100 shapes of each type, 1,000 random edges, and 17 labels in the multiple-graph setup.The passage reports these construction parameters across the described synthetic settings.
  • Evaluation datasets: The study also evaluates three real-world node-classification datasets and two real-world link-prediction datasets.The listed examples include arXiv and Tissue-PPI.
  • Baselines: Nine baselines are used for comparison, including Meta-Graph and Meta-GNN.Meta-Graph uses VGAE, a graph signature function, and MAML for few-shot multi-graph link prediction.

Appendix I Further Details on Performance Evaluation

The evaluation uses specified hardware, few-shot configurations, and parameter studies on Fold-PPI and FirstMM-DB. Performance generally increases with more labeled examples, while h = 2 offers stable neighborhood coverage across datasets.

  • Experiments ran on an Intel Xeon 2.50GHz CPU with an NVIDIA K80 GPU.
  • Synthetic experiments use 2-way disjoint-label tasks, while real-world node classification and link prediction use 3-shot and 16-shot settings.Meta-training and meta-testing use different numbers of gradient update steps across these settings.
  • Performance increased with k from 0.403 to 0.561 to 0.663 on Fold-PPI and from 0.758 to 0.784 to 0.795 on FirstMM-DB.The tested k values were 1, 3, 10 for Fold-PPI and 16, 32, 64 for FirstMM-DB.
  • The h = 2 neighborhood produced stable performance, outperforming h = 1 and remaining comparable to or better than h = 3 depending on the dataset.The reported performances were 0.399, 0.561, 0.427 for Fold-PPI and 0.616, 0.784, 0.837 for FirstMM-DB at h = 1, 2, 3.

Appendix K Further Results on Synthetic Datasets

Synthetic-dataset results use five-fold average multi-class accuracy for 1-shot node classification across graph meta-learning settings. Performance variability is larger when testing uses only two labels, especially when their structural roles lack transferable counterparts in training.

  • Large standard deviation arises because synthetic meta-testing samples only two labels in one data fold.For real-world datasets, more labels are sampled for meta-testing, producing smaller standard deviations.
  • Performance can be poor when meta-testing label structures are distinct from all meta-training label structures, because the meta-learner has no transferable pattern to learn.
  • Mean accuracy reflects predictive performance in both synthetic and real-world settings.
  • Table 6 reports five-fold average multi-class classification accuracy for 1-shot node classification across synthetic graph meta-learning settings.The disjoint-label setting uses 2-way tasks, while shared-label cycle and BA graphs contain 17 and 10 labels, respectively.
Loading 2006.07889v4…