PaperlayerView exact revision on arXiv

Source-linked AI summary

Sub-graph Contrast for Scalable Self-Supervised Graph Representation Learning

Yizhu Jiao, Yun Xiong, Jiawei Zhang, Yao Zhang, Tianqi Zhang, Yangyong Zhu

arXiv:2009.10273v3cs.LGstat.ML

TL;DR

Large-scale graph representation learning remains constrained by complete-graph computation and memory demands, costly labels, and self-supervised objectives focused on global or very local structure. SUBG-CON samples context subgraphs and contrasts central-node representations with them to learn regional structure, achieving competitive or superior benchmark performance with lower-cost, parallelizable training. The paper reports effectiveness and efficiency across multiple real-world graph datasets.

  • Problem

    Graph representation learning needs scalable, label-efficient methods that capture more than proximity while existing supervised and self-supervised approaches rely on costly labels or complete-graph processing.

  • Method

    SUBG-CON samples context subgraphs as graph data augmentation, encodes them, and optimizes central-node representations through contrast with corresponding subgraph representations.

  • Results

    Experiments across multiple benchmark datasets show competitive node-classification representations, often outperforming strong supervised and unsupervised baselines, with verified training-time and memory efficiency.

  • Takeaways & Limitations

    Sampled regional subgraphs provide a basis for scalable, weaker-supervision graph representation learning that is also easy to parallelize.

Abstract

from arXiv · show

Graph representation learning has attracted lots of attention recently. Existing graph neural networks fed with the complete graph data are not scalable due to limited computation and memory costs. Thus, it remains a great challenge to capture rich information in large-scale graph data. Besides, these methods mainly focus on supervised learning and highly depend on node label information, which is expensive to obtain in the real world. As to unsupervised network embedding approaches, they overemphasize node proximity instead, whose learned representations can hardly be used in downstream application tasks directly. In recent years, emerging self-supervised learning provides a potential solution to address the aforementioned problems. However, existing self-supervised works also operate on the complete graph data and are biased to fit either global or very local (1-hop neighborhood) graph structures in defining the mutual information based loss terms. In this paper, a novel self-supervised representation learning method via Subgraph Contrast, namely \textsc{Subg-Con}, is proposed by utilizing the strong correlation between central nodes and their sampled subgraphs to capture regional structure information. Instead of learning on the complete input graph data, with a novel data augmentation strategy, \textsc{Subg-Con} learns node representations through a contrastive loss defined based on subgraphs sampled from the original graph instead. Compared with existing graph representation learning approaches, \textsc{Subg-Con} has prominent performance advantages in weaker supervision requirements, model learning scalability, and parallelization. Extensive experiments verify both the effectiveness and the efficiency of our work compared with both classic and state-of-the-art graph representation learning approaches on multiple real-world large-scale benchmark datasets from different domains.

I. INTRODUCTION

SUBG-CON addresses scalability and supervision limits in graph representation learning by learning from sampled context subgraphs rather than complete graphs. It captures regional structure through central-node–subgraph correlation and supports efficient, parallel training.

  • Motivation: Complete-graph GNNs face computation, memory, and parallelization barriers on large graphs, while supervised methods require costly manual labels.
  • Motivation: Existing self-supervised graph methods use complete graphs and emphasize either global structure or directly adjacent 1-hop neighborhoods.
  • Results: Experiments across multiple real-world datasets found competitive node-classification representations, often outperforming supervised and unsupervised strong baselines while improving efficiency.
  • Method: SUBG-CON uses central nodes and sampled context subgraphs to capture regional graph structure for self-supervised representation learning.
  • Method: A graph data-augmentation strategy generates additional training samples through subgraph sampling from the existing graph.
  • Efficiency: Training on small, simple subgraphs lowers time and memory costs and enables parallel graph representation learning.

II. RELATED WORK

Related work spans supervised GNNs, proximity-based unsupervised embeddings, and emerging self-supervised graph representation learning. The paper frames subgraph-based learning as a response to limitations in supervision, scalability, and graph data augmentation.

  • Graph Neural Networks: GNNs commonly learn node representations by iteratively aggregating neighboring-node representations, but typically require label supervision.
  • Unsupervised Representation Learning: Traditional unsupervised methods use random-walk or graph-reconstruction objectives that place nearby nodes close in representation space.
  • Self-Supervised Learning: Self-supervised learning generates annotation-free pretext tasks and surrogate samples automatically, but graph-specific literature remains limited.
  • Paper Framework: The proposed framework presents subgraph sampling, subgraph encoding, self-supervised optimization, and parallel SUBG-CON as its main components.

A. Subgraph-Based Self-Supervised Representation Learning

SUBG-CON replaces complete-graph encoding with sampled context subgraphs that provide regional structure information for self-supervised node representation learning. Its sampler uses importance scores to select related neighbors, enabling minibatch training and improved scalability.

  • Subgraph-Based Self-Supervised Representation Learning: SUBG-CON encodes smaller context subgraphs instead of the complete graph, allowing node representations to be retrieved without global graph computation.The encoder operates on subgraphs whose sizes are much smaller than the original graph.
  • Subgraph-Based Self-Supervised Representation Learning: The sampler measures neighbor importance and selects closely related nodes to form context subgraphs containing regional structure information.Importance scores are computed with personalized PageRank before selecting neighbors.
  • Subgraph-Based Self-Supervised Representation Learning: The self-supervised pretext task uses central-node and context-subgraph correlation to embed regional information into node representations.The method focuses on context subgraph extraction, subgraph encoding, and self-supervised optimization.
  • Subgraph-Based Self-Supervised Representation Learning: The subgraph sampler acts as graph data augmentation by extracting regional neighborhoods as training instances.The paper formally defines graph data augmentation as producing variant graphs through transformations of features and relations, and adopts subgraph sampling.
  • Subgraph-Based Self-Supervised Representation Learning: Personalized PageRank importance scores can be precomputed, while node-wise computation reduces memory use for large-scale graphs.The sampler chooses the top-k important neighbors to constitute each context subgraph.
  • Subgraph-Based Self-Supervised Representation Learning: Sampled context subgraphs can be decomposed into minibatches and processed with parallel computing to improve efficiency.The procedure obtains each node’s context subgraph from the original graph and supports parallel computation for large inputs.

C. Encoding Subgraph For Representations

The encoder transforms each context subgraph into node-level latent representations, selects the central-node embedding, and pools node representations into a subgraph-level summary.

  • Encoding Subgraph For Representations: The encoder E maps a central node’s context subgraph into a latent representation matrix Hi.The encoder takes the subgraph’s feature and adjacency matrices as input.
  • Encoding Subgraph For Representations: A GNN encoder generates node representations by aggregating information from neighbors, after which the central-node embedding hi is selected from Hi.The operation C denotes selecting the central-node embedding.
  • Encoding Subgraph For Representations: A readout function R summarizes the encoded node representations into a context subgraph representation si.The resulting central-node and subgraph representations support positive and negative sample generation.
  • Encoding Subgraph For Representations: For each specified node, its context subgraph representation is treated as the positive sample in the contrastive architecture.Other randomly sampled subgraph representations serve as negative samples.

D. Contrastive Learning via Central Node and Context Subgraph

SUBG-CON defines an annotation-free contrastive task by matching each central node with its real context subgraph and contrasting it against corrupted alternatives. Because sampled subgraphs overlap, it uses a margin triplet loss rather than requiring absolute separation.

  • Contrastive Learning via Central Node and Context Subgraph: Self-supervised contrastive learning automatically generates positive and negative samples through an annotation-free pretext task.The encoder is trained by contrasting these examples.
  • Contrastive Learning via Central Node and Context Subgraph: SUBG-CON treats a central node’s real context-subgraph representation as positive and corrupted subgraph representations as negative samples.The corruption function P operates on a representation set to generate negatives.
  • Contrastive Learning via Central Node and Context Subgraph: The optimization procedure samples context subgraphs, encodes them, extracts central-node embeddings, pools subgraph representations, corrupts them, and updates E and R.Algorithm 1 repeats these steps until convergence.
  • Contrastive Learning via Central Node and Context Subgraph: Because context subgraphs overlap, SUBG-CON uses a margin triplet loss so positive and negative samples need only be discriminated to some extent.The authors motivate this choice as avoiding harm from absolute discrimination of overlapping examples.

E. Parallelizability

SUBG-CON supports parallel processing by extracting and encoding context subgraphs independently rather than requiring computation over the complete graph.

  • Parallelizability: Context-subgraph extraction can be parallelized across threads, processes, or machines exploring different graph regions.The method avoids global computation requiring the whole graph structure.
  • Parallelizability: Operating on context subgraphs enables multiple subgraphs to be encoded simultaneously, supporting scalable model learning.

IV. EXPERIMENT

Experiments evaluate SUBG-CON through fully unsupervised node classification on six real-world datasets, comparing effectiveness, architecture choices, objectives, and efficiency against established baselines.

  • Experimental setup: SUBG-CON learns representations fully unsupervised, then evaluates them with logistic regression on test nodes.
  • Experimental setup: The study compares supervised and unsupervised baselines, encoder architectures, contrastive objectives, training time, and memory usage.
  • Experimental setup: Six datasets span citation, social, and protein networks, with tasks covering topic, protein-role, image-description, and community classification.
  • Implementation: The method uses GCN encoders with skip connections for Cora, Citeseer, Pubmed, and PPI, and two-layer GCNs for Reddit and Flickr.
  • Implementation: Negative samples are generated by randomly shuffling context subgraph representations, treating another central node’s subgraph as the negative context.
  • Implementation: Subgraphs contain no more than 20 nodes, representations have dimension 1024, and the margin value ϵ is 0.75.

C. Node Classification

Comparative node-classification experiments report strong performance across six datasets, with SUBG-CON outperforming competing self-supervised methods and self-supervised approaches generally exceeding proximity-based baselines.

  • Comparative results: SUBG-CON outperforms all competing self-supervised approaches across the six evaluated datasets.
  • Comparative results: Self-supervised methods are more competitive than traditional unsupervised baselines based on proximity objectives.
  • Comparative results: DGI is competitive with three supervised graph neural networks and exceeds their reported performance on Cora, Citeseer, Pubmed, and Reddit.
  • Comparative results: On PPI, a large performance gap remains, which the authors attribute to sparse original node features, including over 40% all-zero-feature nodes.

D. Design of Architectures

Architecture experiments compare four GNN encoders and show that encoder suitability depends on the dataset and subgraph setting, while margin loss performs best among tested objectives.

  • Design of Encoder: Four encoders are compared: GCN, GCN with skip connections, GAT, and GIN.
  • Design of Encoder: GCN with skip connections performs best on Citeseer, Pubmed, and PPI, while two-layer GCN is best for Flickr and Reddit.
  • Design of Encoder: GAT can be competitive on Cora, but its higher training time and memory usage lead the authors to select GCN with skip connections.
  • Design of Encoder: More expressive GNNs such as GAT and GIN are considered less suitable for handling the sampled subgraphs.

2) Effectiveness of Objective Function:

SUBG-CON’s margin loss performs best among the compared objectives, while relatively few sampled subgraphs can provide sufficient encoder information and reduce efficiency costs. The method uses 500 subgraphs for smaller datasets and 50 for larger ones, outperforming complete-graph baselines in training time and memory usage.

  • Objective function: Margin loss achieves the best performance among the compared objective functions.The authors attribute this to similarities among context subgraphs, which make absolute separation of positive and negative examples unsuitable.
  • Sampled subgraphs: About 500 sampled subgraphs suffice for Cora, Citeseer, and Pubmed, whereas PPI, Flickr, and Reddit require as few as 50.These findings are reported from experiments varying the number of sampled subgraphs across six datasets.
  • Training time and memory cost: SUBG-CON trains much faster with much less computation memory than self-supervised complete-graph baselines on all six datasets.The efficiency advantage is reported as especially prominent on larger graphs, particularly Reddit.
  • Training time and memory cost: The efficiency evaluation uses 500 context subgraphs for three small-scale datasets and 50 for three large-scale datasets.Training time excludes validation, while memory includes model parameters and all hidden representations in a batch.

3) Parallel Computation:

SUBG-CON supports parallel computation over sampled subgraphs, accelerating processing as more GPUs are added without reducing predictive performance. Its regional-subgraph design also shows dataset-dependent sensitivity to context size, with larger contexts generally helping except where added structure introduces noise.

  • Parallel computation: SUBG-CON can be run efficiently in parallel when training with a small number of subgraphs is insufficient.The authors identify parallel execution as highly scalable for complex application scenarios.
  • Parallel computation: Increasing the number of GPUs accelerates processing on PPI, Flickr, and Reddit without reducing predictive performance relative to serial execution.The parallel experiments use 20,000 subgraphs and 400 training epochs.
  • Subgraph size analysis: Larger context subgraphs generally improve performance, so the default subgraph size is set to 20 under computation-memory constraints.The analysis varies context size from 2 to 20 nodes, including the central node.
  • Subgraph size analysis: Citeseer peaks at a context size of 10, after which larger subgraphs degrade performance because their added structural complexity introduces noise.The authors associate this exception with Citeseer’s sparsity and set its subgraph size to 10.
Loading 2009.10273v3…