PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph Structure Learning with Variational Information Bottleneck

Qingyun Sun, Jianxin Li, Hao Peng, Jia Wu, Xingcheng Fu, Cheng Ji, Philip S. Yu

arXiv:2112.08903v1cs.LGcs.AI

TL;DR

GNNs commonly rely on observed graphs even when their structures are noisy, incomplete, or mismatched with downstream tasks. VIB-GSL learns a task-relevant bottleneck graph using Information Bottleneck principles and variational optimization, achieving reported effectiveness and robustness across graph classification and denoising.

  • Problem

    Observed graph structures can be noisy, incomplete, or task-independent, while existing structure-learning methods rely on assumptions or constraints that may not apply across datasets and tasks.

  • Method

    VIB-GSL jointly learns graph structure and representations by masking irrelevant features, generating an IB-Graph, and optimizing a tractable variational Information Bottleneck objective.

  • Results

    VIB-GSL demonstrates superior effectiveness and robustness over strong baselines in graph classification and graph denoising.

  • Takeaways & Limitations

    VIB-GSL provides a model-agnostic framework that distills task-relevant information while making graph structure learning easier and more stable to optimize.

  • Takeaways & Limitations

    The framework assumes no information loss when replacing mutual information involving GIB with corresponding quantities involving its graph representation ZIB.

Abstract

from arXiv · show

Graph Neural Networks (GNNs) have shown promising results on a broad spectrum of applications. Most empirical studies of GNNs directly take the observed graph as input, assuming the observed structure perfectly depicts the accurate and complete relations between nodes. However, graphs in the real world are inevitably noisy or incomplete, which could even exacerbate the quality of graph representations. In this work, we propose a novel Variational Information Bottleneck guided Graph Structure Learning framework, namely VIB-GSL, in the perspective of information theory. VIB-GSL advances the Information Bottleneck (IB) principle for graph structure learning, providing a more elegant and universal framework for mining underlying task-relevant relations. VIB-GSL learns an informative and compressive graph structure to distill the actionable information for specific downstream tasks. VIB-GSL deduces a variational approximation for irregular graph data to form a tractable IB objective function, which facilitates training stability. Extensive experimental results demonstrate that the superior effectiveness and robustness of VIB-GSL.

1 Introduction

Graph structure learning is needed because observed graphs can be noisy, incomplete, or task-independent, while existing methods often rely on dataset-specific assumptions. VIB-GSL applies the Information Bottleneck principle to learn task-relevant graph structures and provides a variational, model-agnostic framework.

  • Motivation: Observed graphs may be incomplete, noisy, or constructed independently of downstream tasks, creating a gap between raw and task-optimal structures.Some applications also lack graph structure and require additional graph construction.
  • Motivation: Graph properties can depend mainly on critical structures rather than the entire graph, making task-relevant structure learning fundamental.This challenge is especially important for real-world and risk-critical applications.
  • Research gap: Existing graph structure learning methods optimize adjacency with GNN parameters but may depend on assumptions such as community structure or sparsity, low-rank, and smoothness constraints.These assumptions and constraints may not generalize across datasets and tasks.
  • Approach: VIB-GSL advances the Information Bottleneck principle for graph structure learning to mine underlying task-relevant relations.The framework is designed to retain actionable information while compressing task-irrelevant information.
  • Approach: VIB-GSL generates an IB-Graph by masking irrelevant node features and learning a new structure, then uses a GNN and sampled representations for downstream tasks.The representation distribution is learned by the GNN module and sampled with a reparameterization trick.
  • Contributions: VIB-GSL is model-agnostic, uses a tractable variational optimization upper bound, and shows effectiveness and robustness in graph classification and denoising experiments.Existing GNNs can be plugged into the framework to enhance performance.

2 Background and Problem Formulation

This section formulates graph structure learning and introduces the Information Bottleneck framework used to balance predictive sufficiency against compression. It also situates graph-specific IB methods within related work.

  • 2.1 Graph Structure Learning: Graph structure learning jointly targets an optimized graph structure and corresponding representations to improve GNN robustness for graph-level tasks.The paper focuses specifically on graph-level applications.
  • 2.1 Graph Structure Learning: Given a graph or only a feature matrix, the problem is to produce an optimized graph G∗ = (X∗, A∗) and corresponding representations Z∗ = f(G∗) for downstream tasks.The formulation includes node features and adjacency when a graph is available.
  • 2.2 Information Bottleneck: The Information Bottleneck balances data fit and generalization using mutual information as both a cost function and regularizer.The framework uses entropy, cross entropy, mutual information, and Kullback-Leibler divergence as standard information-theoretic quantities.
  • 2.2 Information Bottleneck: The IB setup assumes a Markov chain Y → X → Z, where representation Z is derived from input data X for predicting target Y.This captures the dependency structure used in the formulation.
  • 2.2 Information Bottleneck: The Information Bottleneck principle seeks a minimal sufficient representation Z for input data X and label Y.Its objective is introduced as a formal definition in the background section.
  • 2.2 Information Bottleneck: The Lagrangian multiplier β trades off sufficiency and minimality in the Information Bottleneck objective.Changing β controls the balance between predictive information and compression.
  • 2.2 Information Bottleneck: Deep VIB makes the IB objective tractable by parameterizing distributions with a neural network and using variational approximations.The variational distributions approximate the target conditional and representation prior.
  • 2.2 Information Bottleneck: Graph-specific IB research includes GIB, which regularizes structure and feature information, and SIB, which extends the Information Bottleneck to graph learning.These methods represent prior efforts to apply IB principles to irregular graph data.

3 Variational Information Bottleneck Guided Graph Structure learning

VIB-GSL formulates graph structure learning as an Information Bottleneck problem, seeking an IB-Graph that preserves task-relevant information while compressing irrelevant graph information. Its variational implementation learns masked features, a task-specific structure, and a stochastic graph representation for classification.

  • 3.1 Graph Information Bottleneck: The IB-Graph GIB is an optimal graph representation compressed with minimum information loss about the properties of input graph G.
  • 3.1 Graph Information Bottleneck: The bottleneck objective preserves information about labels while dropping label-irrelevant information from the observed graph.The prediction term preserves essential graph-property information, whereas the compression term removes irrelevant information.
  • 3.1 Graph Information Bottleneck: Optimizing the IB objective encourages nuisance invariance, making GIB less related to task-irrelevant information in G.
  • 3.2 Instantiating the VIB-GSL Framework: Because mutual information is intractable for non-Euclidean graphs, VIB-GSL replaces both objective terms with tractable variational upper bounds.The bounds use variational approximations for the label posterior and the prior distribution over IB-Graphs.
  • 3.2 Instantiating the VIB-GSL Framework: VIB-GSL approximates graph-level mutual information using the IB-Graph representation ZIB and Monte Carlo sampling over training samples.This assumes no information loss when converting GIB into ZIB.
  • Step-1: Generate IB-Graph GIB.: The IB-Graph generator masks irrelevant node features and learns a new structure whose possible edges are independent Bernoulli variables parameterized by attention weights.Small edge probabilities indicate likely noise and can lead to small weights or edge removal.
  • Step-2 and Step-3: Learn and Sample IB-Graph Representation.: The GNN learns a distribution over ZIB from GIB, and reparameterization samples ZIB so an MLP can produce predicted labels.The sampled representation is used for classification while randomness is transferred to independent Gaussian noise for gradient estimation.
  • Step-1: Generate IB-Graph GIB.: Concrete relaxation makes Bernoulli edge samples differentiable, after which thresholding extracts a symmetric sparse adjacency matrix from the weighted fully connected graph.

10 end

VIB-GSL learns a new graph independently of the original structure, improving robustness to noisy information and structure perturbations. Compared with related IB-based methods, it explicitly learns task-relevant graphs and uses a tractable variational approximation for more stable training.

  • Property of VIB-GSL: VIB-GSL learns a new graph independently of the original graph structure, unlike traditional GNNs and methods such as IDGL and NeuralSparse.This design makes the method independent of potentially noisy or perturbed input structure.
  • Robustness: VIB-GSL’s robustness to noisy information and structure perturbations is verified experimentally.The method’s independence from the original graph structure is the stated basis for this robustness property.
  • Relation to GIB: VIB-GSL explicitly learns an optimal graph, whereas GIB denoises information in latent representations layer by layer.VIB-GSL targets graph-level tasks, while GIB focuses on node-level tasks.
  • Relation to SIB: VIB-GSL learns a new graph structure and can also be applied to data without an existing graph structure, unlike SIB’s critical-subgraph objective.SIB identifies a critical subgraph from an input graph, while VIB-GSL constructs a new graph.
  • Training stability: VIB-GSL uses a tractable variational approximation that provides more stable training than SIB’s MINE-based mutual-information estimation and bi-level optimization.The reported experiments demonstrate this training-stability difference.

4 Experiments

Experiments evaluate VIB-GSL on graph classification and graph denoising, examining effectiveness, robustness, information compression, and training stability. Results show improved classification, robustness to edge perturbations, dataset-dependent compression trade-offs, and stable optimization.

  • Experimental Setup: VIB-GSL is evaluated on graph classification and graph denoising using four social datasets and comparisons with NeuralSparse, SIB, and IDGL.Experiments also plug GCN, GAT, and GIN backbones into VIB-GSL.
  • Graph Classification: VIB-GSL consistently outperforms all baselines across the evaluated graph-classification datasets.The study reports average accuracy, standard deviation, and improvements using 10-fold cross-validation.
  • Graph Denoising: VIB-GSL maintains performance under edge perturbations, whereas GCN accuracy drops by 5% with 25% missing edges and 10% with 25% noisy edges.The perturbations are applied to REDDIT-B by randomly removing or adding 25%, 50%, or 75% of edges.
  • Parameter Sensitivity: Classification accuracy follows a hunchback-shaped trend with β: moderate compression improves performance, while excessive compression loses effective information.The best reported β values are 10^-3 on IMDB-B and 10^-5 on REDDIT-B.
  • Graph Visualization: At equal testing performance, larger β produces denser IB-Graphs because stronger compression requires more neighbors to retain enough information.The visualization also reports that learned edges tend to connect nodes with the same structural roles.
  • Training Stability: The tractable variational approximation makes VIB-GSL more stable to train than SIB, whose mutual-information estimation and bi-level optimization are difficult to converge.Training dynamics are analyzed on REDDIT-B with a learning rate of 0.001.

5 Conclusion

The conclusion presents VIB-GSL as an Information Bottleneck framework that jointly learns graph structures and graph representations. Experiments in graph classification and graph denoising support its effectiveness and robustness.

  • Conclusion: VIB-GSL jointly optimizes graph structure and graph representations through a tractable variational approximation to the Information Bottleneck objective.The approximation is described as facilitating training stability and efficiency.
  • Conclusion: Experiments in graph classification and graph denoising verify VIB-GSL’s superior effectiveness and robustness.

Proof of Lemma 1

The proof establishes an information-theoretic inequality for the learned IB-Graph using a Markov chain and the data processing inequality. It treats graph nuisance information as independent of the label.

  • Proof: The proof models (Y, Gn) → G → GIB as a Markov chain and applies the data processing inequality.GIB depends on Gn only through G.
  • Proof: Because Gn is independent of Y, H(Y | Gn) equals H(Y), while H(Y | Gn; GIB) is bounded by H(Y | GIB).
  • Proof: The resulting inequality is I(GIB; Gn) ≤ I(GIB; G) − I(GIB; Y).

Proof of Proposition 1

The proposition proof replaces an intractable posterior with a variational approximation and uses non-negativity of Kullback–Leibler divergence. The label entropy term can be omitted during optimization.

  • Proof: The proof expresses the mutual-information objective using the joint distribution p(Y, GIB) and conditional distribution p(Y | GIB).
  • Variational Approximation: Because p(Y | GIB) is intractable, the method introduces qθ(Y | GIB) as a variational approximation of the true posterior.
  • Variational Approximation: Non-negativity of Kullback–Leibler divergence provides the variational bound used to derive the tractable objective.The derivation substitutes the posterior relation into the preceding equation.
  • Optimization: The entropy H(Y) is constant with respect to optimization and can therefore be ignored.

Proof of Proposition 2

The proof starts from the definition of mutual information, introduces a variational approximation, and uses nonnegativity of KL divergence before substituting into the preceding equation.

  • The proof begins from the definition of mutual information.
  • Because p(GIB|G)p(G)dG is difficult to compute, the proof uses r(GIB) as a variational approximation to p(GIB).
  • The derivation invokes the nonnegativity of the Kullback–Leibler divergence, DKL(p(Z)||r(Z)) ≥ 0.
  • The resulting bound is obtained by plugging Eq. (23) into Eq. (24).

B. Training Efficiency

VIB-GSL has overall time complexity O(Kn^2) under d ≈ K and d ≪ n, and achieves comparable training efficiency to other methods at their best performance.

  • Under d ≈ K and d ≪ n, VIB-GSL has overall time complexity O(Kn^2).Learning an IB-Graph costs O(nd + n^2d), while graph representation costs O(n^2d + ndK).
  • VIB-GSL’s mean one-epoch training time is comparable to other methods when achieving the best performance.Training times are reported in seconds over 10 runs in Figure 6.
  • Figure 6 compares mean training time for one epoch across various datasets.
Loading 2112.08903v1…