PaperlayerView exact revision on arXiv

Source-linked AI summary

Automated Self-Supervised Learning for Graphs

Wei Jin, Xiaorui Liu, Xiangyu Zhao, Yao Ma, Neil Shah, Jiliang Tang

arXiv:2106.05470v3cs.LGcs.AI

TL;DR

Graph SSL tasks vary in effectiveness across datasets and downstream tasks, while searching their combinations is difficult without ground-truth labels. AutoSSL uses pseudo-homophily to search task combinations, and the paper reports improved node clustering and classification over individual tasks.

  • Problem

    Graph SSL tasks perform differently across datasets and downstream tasks, while evaluating task combinations and guiding their search without labels is challenging.

    Source: §1 · p. 2

  • Method

    AutoSSL uses pseudo-homophily, grounded in graph homophily, to evaluate embeddings and search combinations of graph SSL tasks.

    Source: §1 · p. 2

  • Results

    AUTOSSL significantly improves node clustering and node classification over individual tasks, with up to 10.0% relative improvement on node clustering.

    Source: §1 · pp. 2–3

  • Takeaways & Limitations

    For graphs with high homophily, maximizing pseudo-homophily can help maximize an upper bound on mutual information between pseudo-labels and downstream labels.

    Source: §1 · p. 2

Abstract

from arXiv · show

Graph self-supervised learning has gained increasing attention due to its capacity to learn expressive node representations. Many pretext tasks, or loss functions have been designed from distinct perspectives. However, we observe that different pretext tasks affect downstream tasks differently cross datasets, which suggests that searching pretext tasks is crucial for graph self-supervised learning. Different from existing works focusing on designing single pretext tasks, this work aims to investigate how to automatically leverage multiple pretext tasks effectively. Nevertheless, evaluating representations derived from multiple pretext tasks without direct access to ground truth labels makes this problem challenging. To address this obstacle, we make use of a key principle of many real-world graphs, i.e., homophily, or the principle that "like attracts like," as the guidance to effectively search various self-supervised pretext tasks. We provide theoretical understanding and empirical evidence to justify the flexibility of homophily in this search task. Then we propose the AutoSSL framework which can automatically search over combinations of various self-supervised tasks. By evaluating the framework on 7 real-world datasets, our experimental results show that AutoSSL can significantly boost the performance on downstream tasks including node clustering and node classification compared with training under individual tasks. Code is released at https://github.com/ChandlerBang/AutoSSL.

1 INTRODUCTION

Graph SSL tasks perform differently across datasets and downstream tasks, making task selection important; AutoSSL uses pseudo-homophily to search combinations without ground-truth labels. The paper reports improved node clustering and classification over individual tasks.

1 INTRODUCTION

  • Individual SSL tasks have distinct downstream performance across datasets, and a single task can ignore useful information from others.This motivates automatically composing tasks to learn better node representations.Source: §1 · p. 2
  • Task combinations are difficult to evaluate because their weights affect performance, the search space is large, and downstream labels are unavailable for guidance.The introduction identifies an unsupervised surrogate evaluation measure as necessary.Source: §1 · p. 2
  • For many real-world graphs, connected nodes tend to share labels; AUTOSSL uses this homophily prior to evaluate embeddings with pseudo-homophily.The paper assumes predicted labels from good node embeddings should adhere to homophily.Source: §1 · p. 2
  • The paper proposes pseudo-homophily and two task-search strategies: an evolution algorithm and differentiable search via meta-gradient descent.For graphs with high homophily, pseudo-homophily maximization can help maximize an upper bound on mutual information between pseudo-labels and downstream labels.Source: §1 · p. 2
  • Up to 10.0% relative improvement on node clustering; AUTOSSL also significantly improves node classification over individual tasks.The introduction reports improvement on both downstream tasks, with the stated maximum for clustering.Source: §1 · pp. 2–3

2 BACKGROUND AND RELATED WORK

This section introduces graph neural networks and graph self-supervised learning, then situates AutoSSL among multi-task learning and automated loss-search work.

2 BACKGROUND AND RELATED WORK

  • Graph neural networks map input graphs into low-dimensional representations, commonly using message passing to aggregate neighbors’ representations.The section describes GNNs as tools for extracting information from graph data.Source: §2 · p. 3
  • Graph SSL uses pretext tasks to assign pseudo-labels and train representations without task labels; JOAO selects augmentations for graph classification, while AUX-TS combines tasks at labeled fine-tuning.These works differ from AutoSSL’s unsupervised search over task weights.Source: §2 · p. 3
  • Prior multi-task SSL work commonly uses equal task weights and supervised training, whereas this work learns task weights without labels.Source: §2 · p. 3
  • Automated loss-search methods are generally supervised, while ELo targets image data; unsupervised loss search for graph data remains rarely explored.The paper positions AutoSSL as an automated framework for searching graph SSL losses without supervision.Source: §2 · p. 3

3 AUTOMATED SELF-SUPERVISED TASK SEARCH WITH AUTOSSL

AutoSSL searches combinations of self-supervised losses by weighting them to learn useful node embeddings, using homophily-based pseudo-homophily as an unsupervised search signal. It offers evolutionary and differentiable search strategies, with the latter using soft clustering and meta-gradients.

3 AUTOMATED SELF-SUPERVISED TASK SEARCH WITH AUTOSSL

  • AutoSSL seeks loss weights that produce meaningful node embeddings, but without downstream labels it needs an unsupervised measure of embedding quality.The framework combines n self-supervised losses with weights λ_i; downstream performance cannot serve as H when labels are unavailable.Source: §3 · p. 3

3.1 PSEUDO-HOMOPHILY

  • Pseudo-homophily estimates graph homophily from k-means cluster assignments of learned embeddings, guiding task search under a high-homophily assumption.The authors note that some real-world graphs are heterophilous, so the assumption does not cover every graph.Source: §3.1 · p. 4
  • For balanced pseudo-labels and ground-truth labels with hA < hB, increasing pseudo-label homophily raises the stated mutual-information upper bound, but does not guarantee optimal mutual information.The authors report that maximizing the bound empirically increased NMI across datasets.Source: §3.1 · p. 4

3.2.1 AUTOSSL-ES: EVOLUTIONARY STRATEGY

  • AUTOSSL-ES uses CMA-ES to sample and update task-weight combinations according to embedding quality, evaluating eight candidates per iteration with weights constrained to [0, 1].Candidate combinations can be evaluated independently and in parallel.Source: §3.2.1 · p. 5

3.2.2 AUTOSSL-DS: DIFFERENTIABLE SEARCH VIA META-GRADIENT DESCENT

  • AUTOSSL-DS makes clustering soft so pseudo-homophily is differentiable, then uses meta-gradients to update task weights through the encoder’s training process.Its online update uses one encoder gradient step per iteration to avoid storing the full training trajectory.Source: §3.2.2 · pp. 5–6

4 EXPERIMENTAL EVALUATION

The evaluation tests AUTOSSL against individual tasks and other representation-learning baselines, then examines how pseudo-homophily relates to performance and how task weights change. AUTOSSL generally improves on individual and unsupervised alternatives, while the analyses report dataset-dependent task weights and higher clustering performance with higher pseudo-homophily.

4.1 EXPERIMENTAL SETTING

  • The evaluation combines five SSL tasks across eight real-world datasets and tests node clustering and classification without using labels for task search.Results are averaged over five random seeds; clustering is measured with NMI and classification with test-node accuracy.Source: §4.1 · p. 6, §4 · p. 6

4.2 PERFORMANCE COMPARISON WITH INDIVIDUAL TASKS

  • AUTOSSL-ES improves NMI over the best individual task by 7.3% on WikiCS and 10.0% on Photo, and improves ACC by 1.3% on WikiCS.Combinations searched by AUTOSSL improve clustering and classification over the best individual task most of the time across datasets.Source: §4.2 · p. 7, Table 1 · p. 7

4.3 PERFORMANCE COMPARISON WITH SUPERVISED AND UNSUPERVISED BASELINES

  • AUTOSSL outperforms unsupervised baselines on every dataset except Citeseer, where it is comparable to MVGRL; AUTOSSL-DS outperforms GCN and GAT on 4 of 8 datasets.AUTOSSL-ES also outperforms GCN and GAT on 3/4 out of 8 datasets.Source: §4.3 · p. 8, Table 2 · p. 8
  • AUTOSSL-ES achieves 22.2% and 27.5% relative improvement over the second-best baseline in clustering on Physics and WikiCS, respectively.AUTOSSL-DS achieves 22.2% and 19.8% relative improvement on those datasets, respectively.Source: §4.3 · p. 8, Table 3 · p. 8

4.4 RELATION BETWEEN DOWNSTREAM PERFORMANCE AND PSEUDO-HOMOPHILY

  • Clustering performance has a clear relation with pseudo-homophily across datasets, while higher classification accuracy concentrates in high pseudo-homophily regions on 5 of 7 datasets.The sampled AUTOSSL-ES task weights on Computers and WikiCS show this relation between downstream performance and pseudo-homophily.Source: §4.4 · p. 8, Figure 2 · p. 9

4.5 EVOLUTION OF SSL TASK WEIGHTS, PSEUDO-HOMOPHILY AND PERFORMANCE

  • AUTOSSL-ES task weights vary by dataset: PAR and DGI weights are [0.198, 0.980] on Physics and [0.955, 0.066] on WikiCS; PAR generally benefits co-purchase networks, while DGI is crucial for citation and co-authorship networks.AUTOSSL-DS weights stabilize on CoraFull, and both search variants indicate that PAR and PAIRDIS are less important there.Source: §4.5 · p. 9, Figure 3 · p. 9
  • AUTOSSL-ES increases pseudo-homophily over iterations on CoraFull and Citeseer, with similar patterns reported for other datasets.The plotted quantity is the mean resulting pseudo-homophily in each iteration.Source: §4.5 · p. 9, Figure 4 · p. 9

5 CONCLUSION

The conclusion identifies the challenge of assessing combinations of self-supervised tasks without labels and proposes pseudo-homophily as a quality measure. It presents two AUTOSSL search frameworks and reports that experiments support combining tasks to produce more generalizable representations.

5 CONCLUSION

  • Different graph SSL tasks perform differently across datasets and downstream tasks, motivating combinations that encode multiple information sources.Source: §5 · p. 9
  • Pseudo-homophily measures the quality of task combinations, and the paper theoretically shows that maximizing it can help maximize an upper bound on mutual information between pseudo-labels and ground-truth labels.Source: §5 · p. 9
  • AUTOSSL-ES and AUTOSSL-DS search task weights efficiently, and experiments report that combining SSL tasks produces more generalizable representations.Source: §5 · p. 9

ACKNOLWEDGEMENT

The acknowledgements state that Wei Jin and Jiliang Tang received support from the NSF, ARO, Home Depot, Cisco Systems Inc., and SNAP Inc.

ACKNOLWEDGEMENT

  • Wei Jin and Jiliang Tang acknowledge support from the NSF, ARO, Home Depot, Cisco Systems Inc., and SNAP Inc.Source: ACKNOLWEDGEMENT · p. 10

ETHICS STATEMENT

The ethics statement reports that the authors know of no ethical issues with the paper.

ETHICS STATEMENT

A EXPERIMENTAL SETUP

Experiments use seven real-world datasets, with public splits for three datasets and 10%/10%/80% training/validation/test splits for the others.

A EXPERIMENTAL SETUP

  • Seven real-world datasets are evaluated; WikiCS, ogbn-arxiv, and Citeseer use public splits, while the others use 10%/10%/80% training/validation/test splits.The dataset-statistics table is identified, but its values are not supplied here.Source: A EXPERIMENTAL SETUP · p. 14
  • A one-layer GCN with 512 hidden dimensions is used; individual SSL methods and AUTOSSL-ES train with Adam at learning rate 0.001 for up to 1000 epochs with early stopping.AUTOSSL-DS trains for 1000 epochs and selects the checkpoint with highest pseudo-homophily; AUTOSSL-ES uses a population of 8 and 40 or 80 search rounds.Source: A EXPERIMENTAL SETUP · p. 14
  • Experiments run on NVIDIA Tesla K80 and V100 GPUs with eight Intel Xeon Platinum 8260 CPUs under CentOS Linux 7.Source: A EXPERIMENTAL SETUP · p. 14

B PROOF

The proof relates pseudo-homophily to an upper bound on mutual information, the algorithms search task combinations using that signal, and the discussion focuses on homophilous graphs.

B PROOF

  • For balanced pseudo-labels and ground-truth classes with h_A < h_B, the theorem bounds MI(A,B) and states U_A,B < U_A′,B when h_A < h_A′ < h_B.The proof further states that the upper bound decreases as h_A decreases under the stated conditions.Source: B PROOF · pp. 14, 16

C ALGORITHM

  • AUTOSSL-ES samples task-weight combinations, trains networks independently, scores pseudo-homophily, and updates its sampling distribution with CMA-ES.AUTOSSL-DS updates GNN parameters, clusters embeddings, computes homophily loss, and uses a meta-gradient to update task weights.Source: C ALGORITHM · p. 17

D DISCUSSIONS ON HOMOPHILY ASSUMPTION

  • The framework focuses on homophilous graphs; unsupervised learning on heterophilous graphs is left for future work, with graph transformation mentioned as a way to increase homophily.The discussion cites the homophily reliance of common GNNs as part of this scope choice.Source: D DISCUSSIONS ON HOMOPHILY ASSUMPTION · p. 17

E ADDITIONAL EXPERIMENTAL RESULTS

The additional results revisit the relationship between downstream performance and pseudo-homophily, and track pseudo-homophily and downstream metrics over AUTOSSL-DS iterations.

E.1 RELATIONSHIP BETWEEN DOWNSTREAM PERFORMANCE AND PSEUDO-HOMOPHILY

  • Figure 6 presents additional results on the relationship between downstream performance and pseudo-homophily, with observations referred back to Section 4.4.Source: §E.1 · p. 17, Figure 6 · p. 18

E.2 PSEUDO-HOMOPHILY OVER ITERATIONS

  • Pseudo-homophily first rises and stabilizes, while NMI and ACC later drop; stopping when pseudo-homophily peaks still yields high NMI and ACC.The authors attribute the later performance decline to overtraining and risk of overfitting combined SSL tasks; early low homophily loss reflects less-separable embeddings and close soft cluster assignments.Source: §E.2 · p. 18, Figure 7 · p. 18

E.3.1 TIME COMPLEXITY ANALYSIS

The appendix analyzes AUTOSSL’s search costs and compares runtime, task-weighting strategies, and search algorithms; it also cautions that benchmark gains do not establish fairness.

E.3.1 TIME COMPLEXITY ANALYSIS

  • AUTOSSL-ES has time complexity O(RTL|E|d + RTLNd2 + RKINd), while AUTOSSL-DS has O(TL|E|d + TLNd2 + TKINd); both scale linearly with N when E is proportional to N.For DS, second-order derivative computation adds O(|θ||{λi}|), reducible to O(|{λi}|) with approximated Hessian-vector products; the task-count factor is small.Source: §E.3.1 · pp. 18–19

E.3.2 EMPIRICAL COMPARISON

  • AUTOSSL-DS significantly reduces AUTOSSL-ES’s runtime; ES depends on the number of candidate solutions, and MVGRL can run long or encounter OOM on larger datasets.The reported comparison trains for 1000 epochs on one NVIDIA-K80 GPU; ES runtime is estimated using 500 candidate solutions.Source: Table 5 · p. 19, §E.3.2 · p. 19

F COMPARISON WITH DIFFERENT STRATEGY

G COMPARISON WITH RANDOM SEARCH

H BROADER IMPACT

  • Improved benchmark performance does not guarantee fair representations, so fairness checks remain necessary before industrial use.The authors associate possible inadvertent bias with the GNN and SSL foundations on which their approach builds.Source: H BROADER IMPACT · p. 20

Related papers

Loading 2106.05470v3…