PaperlayerView exact revision on arXiv

Source-linked AI summary

Node Feature Extraction by Self-Supervised Multi-scale Neighborhood Prediction

Eli Chien, Wei-Cheng Chang, Cho-Jui Hsieh, Hsiang-Fu Yu, Jiong Zhang, Olgica Milenkovic, Inderjit S Dhillon

arXiv:2111.00064v3cs.LG

TL;DR

Standard GNN pipelines extract numerical node features from raw data without graph information, leaving a feature-extraction gap. GIANT uses graph-structured self-supervision and XMC-based neighborhood prediction to fine-tune an encoder, improving downstream node-classification performance on large OGB graphs.

  • Problem

    Standard GNN pipelines use graph-agnostic methods to extract numerical node features from raw data, despite correlations between node attributes and graph topology.

  • Method

    GIANT fine-tunes a language-model encoder by predicting graph neighborhoods represented as multi-labels, using XR-Transformers to solve the resulting XMC task.

  • Results

    GIANT significantly improves OGB node-classification accuracy, with absolute gains of roughly 1.5% for first-ranked methods, 3% for standard GNNs, and 14% for MLPs.

  • Takeaways & Limitations

    The fine-tuned encoder produces informative numerical node features that consistently boost downstream GNN performance and can be combined with other learning methods.

  • Takeaways & Limitations

    The study focuses on raw text, while applying the framework to images and audio is deferred to future work.

Abstract

from arXiv · show

Learning on graphs has attracted significant attention in the learning community due to numerous real-world applications. In particular, graph neural networks (GNNs), which take numerical node features and graph structure as inputs, have been shown to achieve state-of-the-art performance on various graph-related learning tasks. Recent works exploring the correlation between numerical node features and graph structure via self-supervised learning have paved the way for further performance improvements of GNNs. However, methods used for extracting numerical node features from raw data are still graph-agnostic within standard GNN pipelines. This practice is sub-optimal as it prevents one from fully utilizing potential correlations between graph topology and node attributes. To mitigate this issue, we propose a new self-supervised learning framework, Graph Information Aided Node feature exTraction (GIANT). GIANT makes use of the eXtreme Multi-label Classification (XMC) formalism, which is crucial for fine-tuning the language model based on graph information, and scales to large datasets. We also provide a theoretical analysis that justifies the use of XMC over link prediction and motivates integrating XR-Transformers, a powerful method for solving XMC problems, into the GIANT framework. We demonstrate the superior performance of GIANT over the standard GNN pipeline on Open Graph Benchmark datasets: For example, we improve the accuracy of the top-ranked method GAMLP from $68.25\%$ to $69.67\%$, SGC from $63.29\%$ to $66.10\%$ and MLP from $47.24\%$ to $61.10\%$ on the ogbn-papers100M dataset by leveraging GIANT.

1 INTRODUCTION

GIANT addresses graph-agnostic feature extraction by using graph-structured self-supervision to fine-tune language models, formulate neighborhood prediction as XMC, and improve downstream GNN performance.

  • Motivation: Graph-agnostic feature extraction is a neglected issue because standard methods obtain numerical node features from raw data without using graph topology.The issue applies to raw text, images, and audio, although this work focuses on text.
  • GIANT framework: GIANT generates numerical node features from raw node attributes using graph-structured self-supervision.The framework is designed to resolve graph-agnostic feature extraction in the standard GNN pipeline.
  • GIANT framework: Neighborhood prediction fine-tunes a language model by predicting each node’s neighborhood, supporting both homophilous and heterophilous graphs.Unlike link prediction, the task is described as addressing problems associated with heterophilic graphs.
  • XMC formulation: Neighborhoods can be encoded as binary multi-labels, enabling GIANT to use XR-Transformers for scalable neighborhood prediction.This connects graph-guided self-supervision to the extreme multi-label classification formalism.
  • Results: GIANT improves accuracy on ogbn-papers100M from 68.25% to 69.67% for GAMLP, from 63.29% to 66.10% for SGC, and from 47.24% to 61.10% for MLP.The paper also reports new state-of-the-art results on the OGB leaderboard.
  • Theory: The paper provides theoretical analysis supporting key XR-Transformer components and improving understanding of XR-Transformers and XMC.Proofs are deferred to the Appendix because of space limitations.

2 BACKGROUND AND RELATED WORK

The background reviews self-supervised GNN methods, extreme multi-label classification, and scalable alternatives to jointly training language models with GNNs.

  • SSL in GNNs: Existing self-supervised GNN methods exploit correlations between node features and graph structure but do not solve graph-agnostic feature extraction.The paper notes that these methods can serve as SSL modules within GNNs and may be integrated into GIANT.
  • XMC and XR-Transformer: XMC maps text instances to relevant labels from an extremely large label collection, with hierarchical clustering helping manage the label space.PECOS uses this organization to handle potentially enormous numbers of labels.
  • XMC and XR-Transformer: In GIANT, node neighborhoods are treated as multi-labels that must be predicted from textual information to match the graph topology.XR-Transformer first clusters output labels and then learns instance-to-cluster matchers.
  • GNNs with raw text: Joint end-to-end training of BERT and GNNs is practically prohibitive because of BERT’s model complexity, GPU memory requirements, and mini-batch constraints.XR-Transformer instead naturally supports mini-batch training and scales well.

3 METHODS

GIANT addresses graph-agnostic feature extraction by predicting node neighborhoods from raw text and using XMC with XR-Transformers to produce numerical node features.

  • Neighborhood prediction: GIANT treats each node’s neighborhood vector as a multi-label target for predicting graph structure from raw text.A language-model encoder maps raw text T_i to numerical features X_i, while neighborhood prediction determines A_i from T_i.
  • Neighborhood prediction: Neighborhood prediction is framed as XMC because each node’s neighborhood can be encoded as a binary multi-label vector.This formulation connects graph-guided feature extraction with XR-Transformers, which are designed for large-scale XMC.
  • Feature extraction: The resulting fine-tuned Transformer serves as an encoder that generates numerical node features from raw text.The encoder can be replaced to process other raw-data formats, including images or audio signals.
  • XR-Transformers: XR-Transformers solve neighborhood prediction at scale by hierarchically clustering neighborhood labels and learning multi-resolution XMC matchers.Higher-level results guide lower-level Transformers, producing coarse-to-fine neighborhood views.

4 THEORETICAL ANALYSIS

The analysis argues that neighborhood prediction is better suited than standard link prediction for both homophilic and heterophilic graphs, and that PIFA-based clustering improves feature separation under a cSBM.

  • Link versus neighborhood prediction: Standard link prediction implicitly assumes that similar node representations are more likely to be connected, making it biased toward homophilic graphs.The paper notes that real-world graphs can violate this assumption and that some GNN architectures fail on such datasets.
  • Link versus neighborhood prediction: In the Figure 3 counter-example, same-color nodes have the most similar features but no edges between them, so homophily-based link prediction fails.The paper instead assumes similar node features correspond to similar structural roles, defined here by 1-hop neighborhoods.
  • Link versus neighborhood prediction: Neighborhood prediction is presented as more suitable because it works for both homophilic and heterophilic graphs.This universality is identified as important for robust graph learning methods.
  • cSBM analysis: For the cSBM, node features are independent Gaussian vectors and edges are independent Bernoulli variables whose probabilities depend on class membership.The analysis uses a balanced two-class setting and does not require p − q > 0, allowing homophilic or heterophilic structures.
  • Theoretical results: PIFA embeddings have asymptotically larger class-centroid effect size than the original node features under the stated cSBM assumptions.The result provides evidence that PIFA in XR-Transformers can improve clustering and feature quality.
  • Theoretical results: Neighborhood vectors of same-class nodes can have Hamming distance ω(√n log n), so directly using them for self-supervision is not advisable.Clustering can average neighborhood vectors within groups and reduce variance, supporting clustering in XR-Transformers.

5 EXPERIMENTS

Experiments evaluate GIANT-XRT on three large-scale OGB node-classification datasets using multiple downstream models, finding consistent accuracy gains and support for its design choices.

  • Evaluation Protocol: GIANT-XRT is evaluated on ogbn-arxiv, ogbn-products, and ogbn-papers100M with MLP and dataset-appropriate GNN models.The protocol uses GraphSAGE on ogbn-arxiv, GraphSAINT on ogbn-products, SGC on ogbn-papers100M, and each dataset’s state-of-the-art GNN.
  • Main Results: GIANT-XRT achieves the best results across both ogbn-arxiv and ogbn-products datasets and all tested downstream models.It improves top-ranked OGB leaderboard accuracy by 1.86% on ogbn-arxiv and 1.19% on ogbn-products.
  • Main Results: 17.58% for MLP and 3.1% for GraphSAGE are the improvements on ogbn-arxiv, while 18.76% for MLP and 5.32% for GraphSAINT are achieved on ogbn-products.These comparisons are against the standard GNN pipeline.
  • Main Results: 1.42% is GIANT-XRT’s accuracy improvement over the top-ranked GAMLP-RLU model on ogbn-papers100M.GIANT-XRT also consistently improves all tested downstream methods on this dataset.
  • Ablation Study: GIANT-XRT’s ablation results favor neighborhood prediction over link prediction and combining both TFIDF and PIFA information for clustering.BERT+LP is not robust across datasets; combined TFIDF and PIFA gives the best results, while omitting both performs worst.

6 ETHICS STATEMENT

The paper reports no potential ethical issues and concludes that GIANT consistently improves state-of-the-art GNN models.

  • ETHICS STATEMENT: The authors report no potential ethical issues regarding their work.
  • ETHICS STATEMENT: GIANT consistently improves state-of-the-art GNN models in extensive numerical experiments.The conclusion also describes graph-guided feature extraction and neighborhood prediction as central components of the framework.

B PROOF OF THEOREM 4.4

The proof analyzes PIFA embeddings by concentrating neighborhood counts and Gaussian feature sums, then shows that nodes cluster around class-specific centroids with vanishing deviation.

  • Concentration analysis: Hoeffding and Gaussian concentration bounds control neighborhood counts, feature-vector norms, and their deviations with high probability.The proof applies concentration inequalities and union bounds over node- and coordinate-level error events.
  • Centroid analysis: PIFA centroid means are characterized by combining class-conditional neighborhood counts with the node-feature means.For class 0, the resulting centroid is expressed through (µp + νq)(1 + o(1)); the class-1 expression swaps p and q.
  • Deviation analysis: The normalized PIFA embedding has class-dependent centroids whose within-class deviation is o(1).The deviation follows from the ratio of an O(σ√n log n) norm bound to the centroid scale n/2·r|p − q|(1 + o(1)).
  • Conclusion: The PIFA embedding has effect size ω(1) with probability at least 1 − O(1/n^c2), implying a better-clustered node representation.The argument assumes r and σ are constants, as specified in the proof.

C PROOF OF PROPOSITION 4.5

The proposition establishes concentration of same-class neighborhood differences under the cSBM setting by representing Hamming distances as sums of independent Bernoulli variables.

  • Bernoulli representation: For same-label nodes, adjacency-coordinate differences are independent Bernoulli variables with parameters 2p(1 − p) or 2q(1 − q), depending on the other node’s label.The proof separates coordinates whose labels match the reference label from those whose labels differ.
  • Distance concentration: The Hamming distance between adjacency vectors is therefore represented using a Binomial random variable.This converts the graph comparison into a concentration problem for a sum of Bernoulli trials.
  • Distance concentration: The resulting Hamming distance is of order ω(√n log n) with probability at least 1 − O(1/n^c).The bound follows by applying the stated concentration inequality under the assumption nq(1 − q) = ω(√n log n).

D PROOF OF LEMMA B.2

The lemma’s proof derives a Gaussian concentration bound using independence, the moment generating function, optimization of the exponential bound, and a union bound.

  • MGF bound: Independence reduces the analyzed sum to a product of Gaussian moment generating functions.The proof uses the i.i.d. assumption together with the MGF of a zero-mean Gaussian of standard deviation σ.
  • Optimization: Choosing t = a/(nσ^2) minimizes the exponential upper bound for the Gaussian sum.The optimized parameter is substituted into the concentration inequality before selecting the deviation scale.
  • Conclusion: Setting a = cσ√(n log n) and applying the bound to both tails with a union bound completes the proof.The resulting statement is the high-probability concentration claim used later in the analysis.

E.1 DATASETS

The experiments use three large-scale OGB datasets with raw text and evaluate downstream node classification with GIANT-XRT and related baselines.

  • Datasets: Node classification is evaluated on ogbn-arxiv, ogbn-products, and ogbn-papers100M, the OGB datasets with available raw text.The citation-network texts consist of paper titles and abstracts, with primary paper categories as labels.
  • Evaluation setup: The downstream experiments average standard GNN results over three independent runs, while OGB-feat results are taken directly from the OGB leaderboard.GPU memory constraints lead to GraphSAINT usage for VGAE and DGI on ogbn-products, and TFN-only consideration on ogbn-papers100M.
  • GIANT-XRT pre-training: GIANT-XRT uses graph adjacency as the XMC instance-to-label matrix for ogbn-arxiv and ogbn-products.The matrix has one row and column per graph node in these datasets.
  • GIANT-XRT pre-training: For ogbn-papers100M, GIANT-XRT subsamples 50M of 111M nodes using PageRank scores, producing an XMC matrix with 50.0M rows, 49.9M columns, and 2.5B edges.The PIFA embedding for hierarchical clustering is constructed by aggregating neighboring nodes’ TF-IDF features.
  • Comparison baseline: BERT+LP pre-training uses a Siamese BERT encoder with a triplet loss, sampling one positive and one negative pair per node.This baseline is used to compare alternative link-prediction pre-training with neighborhood prediction.

E.4 HYPER-PARAMETERS OF DOWNSTREAM METHODS

The downstream experiments tune selected hyperparameters across models and pre-trained node features, run on a specified AWS instance, and compare GIANT-XRT with leading OGB models.

  • Hyperparameter tuning: Learning rates are optimized over {0.01, 0.001} for all downstream models.MLP, GraphSAGE, and SAGN also tune the number of layers over {1, 3}.
  • Hyperparameter tuning: Hyperparameter tuning applies consistently to Xplain, XSSLGNN, and XGIANT pre-trained node features.GAMLP uses the official implementation setting, while RevGAT retains its default hyperparameters.
  • Experimental infrastructure: All experiments use an AWS p3dn.24xlarge instance with 96 CPUs, 768 GB of RAM, and 8 Nvidia V100 GPUs.Each GPU has 32 GB of memory.
  • Leaderboard comparison: Figure 5 compares the performance of the top 8 models on the OGB leaderboard as of Nov. 11th, 2021.The figure notes that ogbn-products results exceed Table 2 because the latest SAGN GitHub hyperparameters were used.
Loading 2111.00064v3…