PaperlayerView exact revision on arXiv

Source-linked AI summary

Transfer Learning of Graph Neural Networks with Ego-graph Information Maximization

Qi Zhu, Carl Yang, Yidan Xu, Haonan Wang, Chao Zhang, Jiawei Han

arXiv:2009.05204v2cs.LGstat.ML

TL;DR

Training dedicated GNNs is costly, and transferability lacks clear theoretical analysis and guarantees. This paper defines transferable graph information through ego-graphs and features, proposes EGI, and analyzes transferability under structural and feature conditions. Synthetic and real-world experiments support the analysis, with EGI outperforming state-of-the-art frameworks on YAGO; the analysis is bounded when target tasks rely on different structural signals.

  • Problem

    Dedicated GNN training is costly on large graphs, while it remains unclear when models will succeed or fail across different transfer tasks.

    Source: §1 · p. 1

  • Method

    The paper defines graph information through ego-graph structures and node features, uses EGI to capture it, and analyzes transferability against feature requirements and local graph Laplacian differences.

    Source: §1 · pp. 1–2

  • Results

    Controlled synthetic experiments validate the theoretical conclusions, Airport and Gene results support EGI’s design, and YAGO experiments report significant-margin gains over state-of-the-art frameworks.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The theoretically grounded framework is presented as practically useful for guiding GNN transfer-learning design and experiments.

    Source: §5 · p. 10

    The analysis may be less effective when target tasks depend on structural signals beyond local ego-graphs, such as connected-component counts or community structure.

    Source: §3.2 · p. 7

Abstract

from arXiv · show

Graph neural networks (GNNs) have achieved superior performance in various applications, but training dedicated GNNs can be costly for large-scale graphs. Some recent work started to study the pre-training of GNNs. However, none of them provide theoretical insights into the design of their frameworks, or clear requirements and guarantees towards their transferability. In this work, we establish a theoretically grounded and practically useful framework for the transfer learning of GNNs. Firstly, we propose a novel view towards the essential graph information and advocate the capturing of it as the goal of transferable GNN training, which motivates the design of EGI (Ego-Graph Information maximization) to analytically achieve this goal. Secondly, when node features are structure-relevant, we conduct an analysis of EGI transferability regarding the difference between the local graph Laplacians of the source and target graphs. We conduct controlled synthetic experiments to directly justify our theoretical conclusions. Comprehensive experiments on two real-world network datasets show consistent results in the analyzed setting of direct-transfering, while those on large-scale knowledge graphs show promising results in the more practical setting of transfering with fine-tuning.

1 Introduction

The introduction frames GNN transfer as a response to costly graph-specific training and uncertainty about when transfer succeeds. It proposes an ego-graph-and-feature view, develops EGI and a transferability analysis, and reports supporting synthetic and real-world results.

1 Introduction

  • Dedicated GNN training is costly on large graphs, and it remains unclear when models will excel or fail across different pre-training and fine-tuning tasks.Source: §1 · p. 1
  • The framework views a graph as samples from a joint distribution of k-hop ego-graph structures and node features, enabling definitions of graph information and similarity.Source: §1 · p. 1
  • EGI maximizes ego-graph information to capture the defined graph information, and its transferability analysis relates source-target local graph Laplacians to transferable-feature requirements.Source: §1 · p. 2
  • Controlled synthetic experiments validate the theoretical conclusions, while Airport and Gene results support EGI’s design and YAGO experiments show significant-margin gains over state-of-the-art frameworks.The YAGO evaluation uses task-specific fine-tuning.Source: §1 · p. 2

2 Related Work

Earlier graph representation methods either struggled to scale or learned embeddings tied to observed nodes. GNNs support inductive learning, but transfer across graphs with varying features and structures remained uncertain; prior theoretical work did not analyze transfer between distinct graph pairs.

2 Related Work

  • Spectral methods were theoretically grounded but struggled beyond graphs with a thousand nodes, while Skip-gram embeddings scaled to millions yet were transductive.Source: §2 · p. 2
  • GNNs can generalize to unseen nodes with meaningful features, but task-specific labels and fixed downstream tasks limit many models; unsupervised GNN transfer across varying graphs remains unclear.Source: §2 · p. 2
  • Prior GNN pre-training work lacked rigorous transferability analysis; existing theory studied graph permutations [33] [34] or discriminability-transferability tradeoffs [47], not distinct graph pairs.Source: §2 · p. 3

3 Transferable Graph Neural Networks

The framework treats transferable GNN utility as capturing the joint information in graph structures and node features, motivating EGI and a Laplacian-based analysis of its transferability. That analysis relies on structure-respecting node features and relates transferability to structural differences between source and target graphs.

3 Transferable Graph Neural Networks

  • The framework defines general GNN utility as capturing the joint distribution of graph topology structures and node features, rather than optimizing for an unknown downstream task.It quantifies transferability by the gap between a GNN’s ability to model source and target graphs.Source: §3 · p. 3

3.1 Transferable GNN via Ego-graph Information Maximization

  • EGI maximizes mutual information between each k-hop ego-graph and its node embedding, using a discriminator to predict whether edges belong to that ego-graph.The paper presents the objective as jointly reconstructing the ego-graph’s edges.Source: §3.1 · pp. 3–5
  • Synthetic experiments show EGI outperforms the compared methods on similar and dissimilar graph transfers when using node-degree features.Its gains over untrained GIN and two state-of-the-art unsupervised GNNs support its structure-preserving transferability.Source: §3.1 · p. 5

3.2 Transferability analysis based on local graph Laplacians

  • When fixed non-transferable node features are used, compared methods show almost no transferability, with trained GNN performance similar to or worse than untrained baselines.The paper contrasts these results with transferable-feature settings.Source: §3.2 · p. 6
  • EGI’s transferability analysis bounds the source–target performance difference using local graph Laplacian differences, assuming structure-relevant node features and reasonable local-spectrum conditions.The EGI gap measures structural difference and can bound the loss difference across graphs.Source: §3.2 · p. 6
  • The EGI gap can pre-judge a single source graph or help select the source with the smallest gap before GNN pre-training.The paper also describes estimating the gap for large graphs by sampling ego-graph pairs, with complexity O(ML^2).Source: §3.2 · p. 7
  • The gap may not predict transferability when target tasks depend on global graph properties such as connected-component counts or community structure.The stated limitation is that EGI accounts for structural differences captured by k-hop ego-graphs.Source: §3.2 · p. 7

4 Real Data Experiments

Real-data experiments assess direct transfer for role identification and fine-tuned few-shot relation prediction. EGI leads the reported comparisons, while the direct-transfer results also track the source–target structural differences examined by the paper.

4 Real Data Experiments

  • The real-data studies use Airport and Gene role labels, with GIN for direct transfer and GCN for fine-tuned transfer comparisons.The experiments use node degree one-hot features by default and examine structure-relevant role identification alongside few-shot relation prediction.Source: §4 · pp. 7–8, §4.1 · p. 8

4.1 Direct-transfering on role identification

  • In Airport direct transfer, EGI achieves the best performance on USA and Brazil, with scores of 64.55 and 73.15, respectively.The comparison uses structure-relevant node features; Table 2 reports results over 100 runs.Source: §4.1 · p. 9, Table 2 · p. 9
  • For Airport, Europe-to-USA and Europe-to-Brazil structural differences are 0.869 and 0.851, alongside EGI gains over untrained GIN of 4.8% and 4.4%, respectively.Source: §4.1 · p. 9
  • On seven better-balanced Gene cancer networks, larger EGI gaps correspond to lower micro-F1 improvement; positive transfer occurs below a gap of 1 and negative transfer above 1.The networks were selected because severe label imbalance otherwise removes performance gaps.Source: §4.1 · p. 9

4.2 Few-shot learning on relation prediction

  • On YAGO, EGI significantly outperforms all compared methods in both post-fine-tuning and joint-fine-tuning.Table 3 reports few-shot relation-prediction performance; scores marked ∗∗ pass a t-test against the second-best result.Source: §4.2 · p. 10, Table 3 · p. 10

5 Conclusion

The paper presents a theoretically grounded framework for analyzing GNN transferability and guiding model design; it identifies relaxed assumptions, broader settings, and data privacy as future concerns.

5 Conclusion

  • The authors present a theoretically grounded framework for analyzing GNN transferability and guiding practical transfer-learning design.They identify this as the first such research effort to their knowledge.Source: §5 · p. 10
  • Future work should strengthen the bound under relaxed assumptions and extend analysis to more complex node features, downstream tasks, scenarios, and datasets.The authors also identify protecting pre-training data privacy as important.Source: §5 · p. 10

A Theory Details

The theory details clarify the notation for edge-related representations and describe how a layered GNN can be analyzed through local ego-graphs.

A Theory Details

  • The objective evaluation samples uniformly, and each sample provides empirical distributions of three quantities.The passage does not identify those three quantities.Source: A Theory Details · p. 15
  • In Eq. 2, h_p denotes a d-dimensional source-node representation and x_q denotes destination-node features.The notation concerns the structure of the ego-graph and its associated source-node feature.Source: A Theory Details · p. 15
  • A GNN with k layers computes embeddings using only the center node’s k-hop ego-graph, rather than the entire graph.This locality is used when unfolding the center-node embedding.Source: A Theory Details · p. 15
  • The proof invokes eigenvalue interlacing and the shared nonzero singular values of A and A^T to relate matrix operator norms.The supplied passage states the setup but does not include the resulting equality.Source: A Theory Details · p. 15

A.1 Center-node view of GCN

The center-node view expresses GCN computation and edge-level discrimination through representations and propagation within k-hop ego-graphs.

A.1 Center-node view of GCN

  • Layer-wise propagation is written for the center-node encoder and discriminator, with the discriminator representing edge information at each layer.The account describes the GCN propagation form and defines the adjacency degree matrix and self-loop notation.Source: §A.1 · pp. 15–16
  • A k-layer GCN’s center-node embedding can be computed from its k-hop ego-graph without processing the entire graph.The p-hop subgraph corresponds to the model’s (k − p)th layer.Source: §A.1 · p. 15
  • The notation distinguishes out-degree and in-degree normalized ego-graph Laplacians by their respective leaf-to-center and center-to-leaf directions.Node-feature and embedding matrices are defined over the ego-graph’s nodes and hops.Source: §A.1 · p. 15
  • At layer ℓ, the GCN updates nodes from hop 0 through hop k − ℓ while leaving the more distant hops unchanged.The center-node representation is taken from hop 0 after the final update.Source: §A.1 · pp. 15–16

A.2 Proof for Theorem 4.1

This appendix states the conditions and proof approach for a transferability bound, details EGI’s encoder–discriminator procedure, and distinguishes direct transfer from fine-tuning settings.

A.2 Proof for Theorem 4.1

  • Theorem A.2 concerns empirical LEGI performance differences between two graphs when features are structure-respecting and the encoder is a k-layer GCN with a 1-hop polynomial filter.The theorem’s conditions specify features of the form x_i = f(L_gi).Source: §A.2 · p. 16
  • The proof assumes bounded neighborhood sizes and pads smaller neighborhoods with isolated, non-informative nodes so corresponding hop sizes match.The maximum neighborhood size at hop p is bounded by r^p.Source: §A.2 · p. 16
  • The proof unfolds layer-wise representation differences into a recurrence and derives bounds for center-node embeddings and discriminator terms.The appendix introduces a lemma bounding hidden-representation differences and treats encoder and discriminator contributions separately.Source: §A.2 · pp. 16–19

B Model Details

  • EGI’s encoder aggregates neighbors toward the center node, while its discriminator operates on a reversed ego-graph to make edge-level true-or-fake predictions.The encoder and discriminator can use existing GNN models; the discriminator’s reversed-graph computation builds source-node representations.Source: B Model Details · pp. 19–20
  • EGI uses mini-batches of ego-graphs and neighborhood sampling; its stated space and time complexity is O(BNK).The encoder and discriminator both propagate on k-hop ego-graphs, making the discriminator’s extra computation a constant multiplier over a common GNN module.Source: B Model Details · p. 20

B.1 Transfer Learning Settings

  • The study uses direct transfer without target fine-tuning to measure transferability, and also evaluates post-fine-tuning and joint-fine-tuning on large-scale YAGO graphs.Post-fine-tuning uses the supervised target-task objective; joint-fine-tuning combines it with the unsupervised pre-training objective.Source: §B.1 · pp. 20–21

C.1 Synthetic Experiments

The synthetic experiments test structural-equivalent node identification across graph families and feature settings. EGI’s transferability is stronger with limited transferable features and varies with source–target structural similarity.

C.1 Synthetic Experiments

  • The experiments generate 40 graphs of 100 nodes each from Barabasi–Albert and forest-fire models, then identify nodes sharing 2-hop ego-graphs using 2-hop WL labels.The degree encoding length is set to 3 for the main comparison; nodes with degree above 3 share an encoding.Source: §C.1 · p. 21, Figure 4 · p. 21
  • With limited initial node features, EGI’s advantage in learning and transferring graph structure is clear; at d=10, transfer gaps diminish across methods and graphs.At d=10, neighborhood aggregation can solve structural equivalence exactly.Source: §C.1 · p. 21, Table 4 · p. 22
  • Transferable degree features reflect the performance gap between similar and dissimilar graphs, while non-transferable node embeddings and random vectors do not.The comparisons include node embeddings and random feature vectors.Source: §C.1 · p. 22, Table 5 · p. 22
  • EGI pre-trained on Forest-fire graphs performed better on Forest-fire than Barabasi graphs by +0.094 with degree encoding (d=3) and +0.057 with DeepWalk embeddings.The reported transfer gap aligns with the graphs’ measured structural similarity.Source: §C.1 · p. 22, Table 4 · p. 22

C.2 Real-world Role Identification Experiments

The real-world role-identification experiments compare direct transfer across airport and gene graphs. EGI’s transferability tracks structural similarity and is supported when node features are transferable.

C.2 Real-world Role Identification Experiments

  • The gene dataset aggregates 52 networks, but experiments use relatively balanced brain-cancer gene graphs because some graphs have extremely imbalanced class distributions.75% of the matched genes are marked as transcription factors.Source: §C.2 · p. 22, Table 6 · p. 23
  • Structural differences for Europe–USA and Europe–Brazil are close (0.869 and 0.851), corresponding to close transferability from Europe to both target graphs.The three airport graphs vary in size and structure, so absolute accuracy varies across them.Source: §C.2 · p. 22, Figure 5 · p. 23
  • On the airport dataset, EGI yields good transferability with transferable features, while the Table 7 comparison uses non-transferable features.The source passage describes role-based labels as relevant to local graph structure and says neither dataset has organic node attributes.Source: §C.2 · pp. 22–23, Table 7 · p. 23
  • EGI’s direct-transfer results were close to directly trained results, and the authors report significant improvements by t-tests; they suggest fine-tuning may be skipped when graphs are sufficiently similar.The source text notes large variances, also observed in other work [45].Source: §C.2 · p. 23

C.3 Real-world large-scale Relation Prediction Experiments

The large-scale relation-prediction experiments pre-train on YAGO and fine-tune on a sampled subgraph with different node features. They report significant accuracy and characterize the time required by both stages.

C.3 Real-world large-scale Relation Prediction Experiments

  • Pre-training on the full YAGO graph uses 256-dimensional degree encodings, while fine-tuning uses 128-dimensional LINE positional embeddings on a uniformly sampled subgraph.The source graph treats relations as unknown; the target graph provides 24 relation types.Source: §C.3 · pp. 23–24
  • EGI’s classification accuracy on all three datasets passed a t-test (p<0.01) and was the second-best result in the table.The table caption reports average and standard deviation over 10 runs.Source: Table 8 · p. 24
  • A feature encoder before the GNN bridges differences in feature dimensions and in feature semantics and distributions between pre-training and fine-tuning.The supervised loss follows DistMult, using a relation-specific diagonal bilinear score function.Source: §C.3 · p. 24
  • EGI takes about 338 seconds per epoch on YAGO-source; pre-training and fine-tuning take about 40 and 10 epochs to converge, respectively.Fine-tuning also takes significant time, and the reported baseline running times are in the same scale.Source: §C.3 · p. 24, Table 9 · p. 24

C.4 Parameter study

The parameter study examines ego-graph size and the sampling frequency used to estimate the EGI gap. It selects k=2 for the main experiments and reports more accurate, robust estimates with more samples.

C.4 Parameter study

  • Larger k may improve encoder expressiveness and gap accuracy, but can also bring over-smoothing and more computational noise.The authors choose k=2 for the main paper’s experiments.Source: §C.4 · pp. 24–25
  • k=2 provides the best transferability to both USA and Brazil; k=1 and k=3 have lower source accuracy than k=2.At k=3, the estimated gap may reflect overly subtle or noisy ego-graph differences.Source: §C.4 · p. 25, Table 10 · p. 25
  • Higher sampling frequencies produce more accurate and robust estimates of the EGI gap; 100 Europe–USA ego-graph pairs, 2.1% of all pairwise enumerations, already give a close estimate.The authors identify theoretical convergence analysis as a possible future direction.Source: §C.4 · p. 25, Table 11 · p. 25
Loading 2009.05204v2…