PaperlayerView exact revision on arXiv

Source-linked AI summary

Towards Unsupervised Deep Graph Structure Learning

Yixin Liu, Yu Zheng, Daokun Zhang, Hongxu Chen, Hao Peng, Shirui Pan

arXiv:2201.06367v1cs.LG

TL;DR

GNNs and supervised GSL can be hindered by noisy or unavailable graph structures, label dependence, biased edge distributions, and task-specific topology. The paper introduces unsupervised GSL and SUBLIME, which use contrastive agreement with a bootstrapped anchor graph to optimize structures from data alone. Extensive experiments on eight benchmark datasets report SUBLIME’s effectiveness and the high quality of its optimized graphs.

  • Problem

    Noisy or unavailable graph structures and supervised GSL’s reliance on labels, biased edge distributions, and node-classification-specific topology motivate unsupervised graph structure learning.

  • Method

    SUBLIME uses self-supervised contrastive learning to maximize agreement between a learned graph and an anchor graph generated from original data, while bootstrapping the anchor during training.

  • Results

    Extensive experiments on eight benchmark datasets demonstrate SUBLIME’s effectiveness and the high quality of its optimized graphs.

  • Takeaways & Limitations

    Unsupervised GSL can use data itself to learn graph structures without external label guidance, supporting structures intended for varied downstream tasks.

  • Takeaways & Limitations

    The presented data-augmentation scheme is not the only possible choice; applying other advanced augmentation methods is left for future research.

Abstract

from arXiv · show

In recent years, graph neural networks (GNNs) have emerged as a successful tool in a variety of graph-related applications. However, the performance of GNNs can be deteriorated when noisy connections occur in the original graph structures; besides, the dependence on explicit structures prevents GNNs from being applied to general unstructured scenarios. To address these issues, recently emerged deep graph structure learning (GSL) methods propose to jointly optimize the graph structure along with GNN under the supervision of a node classification task. Nonetheless, these methods focus on a supervised learning scenario, which leads to several problems, i.e., the reliance on labels, the bias of edge distribution, and the limitation on application tasks. In this paper, we propose a more practical GSL paradigm, unsupervised graph structure learning, where the learned graph topology is optimized by data itself without any external guidance (i.e., labels). To solve the unsupervised GSL problem, we propose a novel StrUcture Bootstrapping contrastive LearnIng fraMEwork (SUBLIME for abbreviation) with the aid of self-supervised contrastive learning. Specifically, we generate a learning target from the original data as an "anchor graph", and use a contrastive loss to maximize the agreement between the anchor graph and the learned graph. To provide persistent guidance, we design a novel bootstrapping mechanism that upgrades the anchor graph with learned structures during model learning. We also design a series of graph learners and post-processing schemes to model the structures to learn. Extensive experiments on eight benchmark datasets demonstrate the significant effectiveness of our proposed SUBLIME and high quality of the optimized graphs.

1 INTRODUCTION

Existing GSL methods improve graph topology jointly with GNNs under node-classification supervision, but this supervised setup depends on labels and can bias structures toward limited, task-specific evidence. The paper proposes unsupervised GSL, using data-driven contrastive learning and bootstrapped anchor graphs to learn more broadly applicable structures.

  • GNNs can suffer when original graph connections are noisy, while explicit-structure dependence limits application to unstructured domains.Real-world graphs may contain uncertain, redundant, wrong, or missing connections; implicit relations could broaden use to vision and language.
  • Existing deep GSL jointly optimizes graph structure and GNN parameters under node-classification supervision.Adjacency matrices may be modeled probabilistically, parametrically, or through metric learning.
  • Supervised GSL relies on labels, biases edge distributions toward labeled nodes and neighbors, and may produce topology specialized for node classification.The paper identifies these as limitations affecting applicability and generalization to tasks such as link prediction and node clustering.
  • SUBLIME learns graph structures without external labels by maximizing agreement between a learned graph and an anchor graph constructed from the original data.Its contrastive loss maximizes mutual information between the two graph views.
  • SUBLIME uses bootstrapping to upgrade the anchor graph with learned structures during training, providing persistent guidance for structure optimization.The contributions also include graph learners and post-processing schemes, evaluated on eight benchmark datasets.

2 RELATED WORK

Related work covers GNN architectures, conventional and deep graph structure learning, and graph contrastive learning. The paper positions its contribution at the intersection of these areas, noting that contrastive learning had not yet been clearly used to improve GSL.

  • 2.1 Graph Neural Networks: GNNs learn low-dimensional node representations from graph-structured data through spectral convolution or spatial neighbor aggregation.Spatial methods use functions such as mean or max pooling, LSTM aggregation, self-attention, and summation.
  • 2.2 Graph Structure Learning: Conventional GSL methods in graph signal processing, spectral clustering, and network science are not designed for graph data with high-dimensional features.
  • 2.2 Graph Structure Learning: Deep GSL models learn adjacency parameters jointly with GNNs under downstream node-classification supervision.Approaches use different parameterizations because graph structures are discrete.
  • 2.3 Graph Contrastive Learning: Graph contrastive learning maximizes mutual information across node-level, graph-level, and cross-scale views and supports diverse applications.
  • 2.3 Graph Contrastive Learning: It remained unclear how to use contrastive learning to improve graph structure learning.

3 PROBLEM DEFINITION

The paper defines attributed graphs with node features and weighted adjacency matrices, then formulates unsupervised GSL as learning or refining topology without node-label supervision. It distinguishes structure inference from structure refinement according to whether an initial graph is available.

  • An attributed graph is represented as G = (V, E, X) = (A, X), with node features X and weighted adjacency matrix A.The feature matrix contains one feature vector per node, while adjacency entries represent edge weights.
  • Unsupervised GSL includes structure inference for datasets without predefined graphs and structure refinement for noisy existing topologies.Node labels are unavailable for optimization in both tasks.
  • Structure inference: Structure inference learns S ∈ [0, 1]^n×n from X to reflect underlying correlations among data samples.Each S_ij indicates whether an edge exists between samples x_i and x_j.
  • Structure refinement: Structure refinement transforms a noisy adjacency matrix A into an optimized matrix S that better captures dependencies between nodes.
  • The formulation hypothesizes that downstream-task performance can improve when the learned or refined graph G_l = (S, X) is used as input.

4 METHODOLOGY

SUBLIME combines graph learners, post-processing, and contrastive structure bootstrapping to learn graph topologies without label-based supervision. It refines sketched structures, constructs augmented learner and anchor views, and progressively updates the anchor using learned structures.

  • SUBLIME consists of graph structure learning and structure bootstrapping contrastive learning modules that jointly optimize the learned topology.The graph learner produces a sketched adjacency matrix, the post-processor converts it into the learned structure, and contrastive learning optimizes agreement between learner and anchor views.
  • Graph Learner: Four graph learners—full graph parameterization, Attentive, MLP, and GNN—model sketched adjacency matrices using independent parameters or pairwise embedding similarities.The GNN learner incorporates original topology and is therefore used only for structure refinement.
  • Post-processor: The post-processor transforms sketched adjacency matrices into sparse, non-negative, symmetric, and normalized learned structures through sequential sparsification, activation, symmetrization, and normalization.Sparsification retains each row’s top-k values, while large-scale graphs can use locality-sensitive approximate kNN sparsification.
  • Graph View Establishment: Learner views combine the learned adjacency matrix S with node features X, while anchor views use the original adjacency matrix A or identity matrix I depending on the task.The anchor is kept stable by avoiding gradient-descent updates, whereas learner structures are directly updated during training.
  • Data Augmentation: SUBLIME applies feature masking and edge dropping to both learner and anchor views before maximizing agreement between the augmented views.These augmentations corrupt graph features and structures to support contrastive learning.
  • Structure Bootstrapping Mechanism: The bootstrapping mechanism slowly updates the anchor structure with the learned structure, reducing noise influence, incorporating effective information, and mitigating over-fitting to a fixed anchor.A slow-moving average with τ > 0.99 is used to stabilize training.

5 EXPERIMENTS

Experiments evaluate SUBLIME across structure inference, structure refinement, clustering, hyper-parameter sensitivity, adversarial robustness, and learned-structure visualization. SUBLIME performs competitively without labels, benefits from bootstrapping, and learns robust, semantically aligned topologies.

  • Node classification in structure inference scenario: SUBLIME outperforms all baselines on 3 of 8 benchmarks and achieves runner-up results on the remaining datasets without label guidance.The authors also report scalability on ogbn-arxiv.
  • Node classification in structure refinement scenario: SUBLIME shows promising node-classification results against self-supervised and supervised methods in structure refinement.The evaluation uses classification accuracy for structure refinement.
  • Node clustering in structure refinement scenario: SUBLIME improves node-clustering performance over baselines, supporting graph-structure optimization for clustering and application of the learned topology beyond node classification.Clustering is evaluated with C-ACC, NMI, F1, and adjusted Rand index.
  • Ablation study: 1.5% average classification-accuracy decrease without structure bootstrapping shows that updating the anchor graph improves learned-graph quality.With τ = 1, the anchor graph remains constant; smaller τ values can instead cause instability and performance declines.
  • Sensitivity analysis: The best k differs by dataset—30 for Cora, 20 for Citeseer, and 15 for Pubmed—while overly small or large neighborhoods perform poorly.The authors associate small k with too few beneficial neighbors and large k with noisy connections.
  • Robustness analysis: On corrupted Cora graphs, SUBLIME consistently performs better or comparably, with larger gains as edge-deletion rates increase toward 0.9.Robustness is tested under random edge deletion and addition across modification ratios from 0 to 0.9.

6 CONCLUSION

The paper investigates unsupervised graph structure learning and introduces SUBLIME, which uses contrastive learning to align learned topology with a self-enhanced target. Experiments demonstrate SUBLIME’s superiority and the rationality of its learned structures.

  • SUBLIME investigates unsupervised graph structure learning by using data itself to generate graph structures.
  • Contrastive learning maximizes agreement between the learned topology and a self-enhanced learning target.
  • Extensive experiments demonstrate SUBLIME’s superiority and the rationality of its learned structures.

B ANALYSIS OF GRAPH LEARNERS

The analysis compares graph learners by flexibility, complexity, and suitability for different feature and graph settings. It also summarizes SUBLIME’s inputs, optional adjacency, post-processing, and contrastive-loss computation.

  • Graph learner properties: FGP models each edge independently with flexible connections and low time complexity, but its O(n^2) space complexity limits large-scale graph applications.
  • Graph learner properties: The attentive learner has the lowest parameter and time complexity with respect to feature dimension d among metric learning-based learners.
  • Algorithm inputs: SUBLIME takes feature matrix X, optional adjacency matrix A, neighbor count k, bootstrapping settings, masking and edge-dropping probabilities, temperature, and epochs.
  • Algorithm procedure: When adjacency is provided, the algorithm computes a learned structure with post-processing and then calculates the contrastive loss.
  • Learner selection: Attentive learners suit high-dimensional features, MLP learners suit low-dimensional large-scale datasets, and GNN learners can exploit available original topology.

C COMPLEXITY ANALYSIS

The complexity analysis decomposes SUBLIME into graph learning, sparsification, augmentation, encoding, projection, and contrastive-loss components. Contrastive loss can be computed with full-graph or mini-batch complexity.

  • Post-processing sparsification costs O(ndb1) with effective kNN and O(n^2d) with conventional kNN.
  • Feature masking and edge dropping require O(d) and O(m) complexity, respectively.
  • The encoder and projector have total complexity O(md1L1 + nd2^2L2).
  • Contrastive-loss computation costs O(n^2) for the full-graph version and O(nb2) for the mini-batch version.
  • The training algorithm of SUBLIME is summarized in Algorithm 1.

E DATASETS

The experiments use benchmark datasets whose statistics and splitting follow prior work, with dataset descriptions covering citation-network examples. Implementation details specify the software and hardware environment.

  • Dataset splitting follows previous works, and Table 7 summarizes benchmark dataset statistics.
  • Cora, Citeseer, and Pubmed are citation networks in which nodes represent papers and edges represent citations.
  • Experiments use PyTorch 1.7.1 and DGL 0.7.1 on a Linux server with an Intel Xeon 4214R CPU and four Quadro RTX 6000 GPUs.

F.2 Evaluation Details

The learned structures are evaluated through node classification and node clustering, using retrained classifiers and clustered learned representations.

  • Node classification: Node classification retrains a GCN-based classifier using each learned adjacency matrix as a constant input.Testing performance is recorded at the highest validation accuracy, averaged over five runs.
  • Node clustering: Node clustering evaluates learned representations from the contrastive encoder by applying K-means clustering for 10 runs.The encoder takes the learned graph as input without augmentation.

F.3 Hyper-parameter Specifications

Hyper-parameters are selected through grid search across representation, graph augmentation, bootstrapping, and optimization settings, with standardized baseline evaluation seeds.

  • Hyper-parameter search: Grid search tunes representation and projection dimensions, kNN size, feature masking, edge dropping, bootstrapping decay, and Adam learning rate.The searched representation dimensions are {16, 32, 64, 128, 256, 512}, while kNN values range from 5 to 40.
  • Baseline settings: Classification baselines use seeds {0, 1, 2, 3, 4}, whereas clustering methods use a fixed seed of 0.Baseline experiments use official code or reported paper results, with hyper-parameters carefully tuned for fair comparison.

G PARAMETER SENSITIVITY OF 𝑝(𝑎)

SUBLIME is most effective at moderate edge dropping rates, while excessive dropping sharply degrades performance by deteriorating both graph views.

  • Sensitivity to p(a): When edge dropping p(a) is between 0.2 and 0.65, SUBLIME achieves better performance on Cora, Citeseer, and Pubmed.The dropping rate is varied from 0 to 0.95, with results reported in Fig. 7.
  • Sensitivity to p(a): Edge dropping above the effective range causes a sharp performance drop because structures on both views are deteriorated.
Loading 2201.06367v1…