PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph Information Bottleneck

Tailin Wu, Hongyu Ren, Pan Li, Jure Leskovec

arXiv:2010.12811v1cs.LGstat.ML

TL;DR

Graph neural networks fuse graph structure and node features but remain vulnerable to noise and adversarial attacks. Graph Information Bottleneck learns minimal, sufficient representations by regularizing both information sources, and its GIB-Cat and GIB-Bern models improve adversarial classification accuracy by up to 31.3% and 34.0%, respectively.

  • Problem

    Graph neural networks must integrate informative node features and graph structure while addressing vulnerability to noise and adversarial attacks.

  • Method

    Graph Information Bottleneck constrains information from node features and graph structure while maximizing information useful for prediction, using variational bounds and two sampling-based models.

  • Results

    GIB-Cat and GIB-Bern improve classification accuracy by up to 31.3% and 34.0% under adversarial perturbation, respectively.

  • Takeaways & Limitations

    The proposed GIB models consistently improve robustness over standard baselines and outperform other state-of-the-art defense models.

  • Takeaways & Limitations

    The tractable GIB formulation relies on a local-dependence assumption for graph-structured data.

Abstract

from arXiv · show

Representation learning of graph-structured data is challenging because both graph structure and node features carry important information. Graph Neural Networks (GNNs) provide an expressive way to fuse information from network structure and node features. However, GNNs are prone to adversarial attacks. Here we introduce Graph Information Bottleneck (GIB), an information-theoretic principle that optimally balances expressiveness and robustness of the learned representation of graph-structured data. Inheriting from the general Information Bottleneck (IB), GIB aims to learn the minimal sufficient representation for a given task by maximizing the mutual information between the representation and the target, and simultaneously constraining the mutual information between the representation and the input data. Different from the general IB, GIB regularizes the structural as well as the feature information. We design two sampling algorithms for structural regularization and instantiate the GIB principle with two new models: GIB-Cat and GIB-Bern, and demonstrate the benefits by evaluating the resilience to adversarial attacks. We show that our proposed models are more robust than state-of-the-art graph defense models. GIB-based models empirically achieve up to 31% improvement with adversarial perturbation of the graph structure as well as node features.

1 Introduction

The introduction motivates Graph Information Bottleneck (GIB) as an adaptation of Information Bottleneck for learning minimal, sufficient graph representations that are more robust to noise and adversarial attacks. It addresses graph-specific non-i.i.d. and discrete-structure challenges through variational bounds, structure sampling, and two GNN models.

  • Motivation and principle: GNNs fuse node features with graph structure effectively, but neighborhood noise and edge-based message passing make them vulnerable to irrelevant information and adversarial attacks.Graph representation learning is challenging because both feature and structural information matter, while neighborhood features can harm predictions.
  • Method: GIB addresses graph-specific IB challenges by using local dependence assumptions and variational bounds that regularize feature and structural information while maximizing target-predictive information.The bounds include a variational upper bound for information constraints and a variational lower bound for target prediction.
  • Motivation and principle: GIB adapts Information Bottleneck to graph representation learning by retaining task-sufficient information from graph structure and node features while removing irrelevant information.This minimal-sufficient objective is intended to reduce overfitting and improve robustness to adversarial attacks.
  • Method: Applying GIB to Graph Attention Networks, the authors sample discrete graph structure using attention weights and introduce categorical and Bernoulli sampling algorithms.These mechanisms alleviate the difficulty of optimizing and modeling discrete graph structure.
  • Results: The resulting GIB-Cat and GIB-Bern models consistently improve robustness relative to standard baseline models.The models instantiate the proposed GIB principle within GAT-based graph representation learning.

2 Preliminaries and Notation

This section defines attributed graphs, node-level prediction representations, and the notation used for probability distributions and latent variables. It also introduces the local-dependence assumption underlying the GIB search space.

  • Graph Representation Learning: An attributed graph is represented as G = (V, E, X), with adjacency matrix A and node attributes X; the input is D = (A, X).The graph has n nodes, and d(u, v) denotes shortest-path distance over A.
  • Graph Representation Learning: The work targets node-level tasks, extracting representations Z_X from D that can be used to predict node labels Y.For node v, its representation and label are denoted Z_X,v and Y_v, respectively.
  • Graph Representation Learning: GIB uses a Markov-chain search space in which each step applies local dependence to extract information from graph structure and node features.The representation correlations are established hierarchically across graph neighborhoods; for example, dependence within 2 hops can propagate across successive layers.
  • Notation: The notation distinguishes induced model distributions P(H) from variational distributions Q(H) and Q_i(H), while defining categorical, Bernoulli, and Gaussian variables.Categorical probabilities sum to one, Bernoulli components lie between zero and one, and Gaussian parameters may be vectors with covariance matrix Σ.

3 Graph Information Bottleneck

The GIB principle seeks node representations that compress graph-structured data while retaining information predictive of targets. A local-dependence assumption makes this objective tractable by restricting representations and controlling information flow through locally refined graph structures.

  • 3 Graph Information Bottleneck: GIB minimizes information between node representations and graph data while maximizing information between representations and targets.This inherits the general information bottleneck principle, balancing compression and prediction.
  • 3 Graph Information Bottleneck: Because graph data points are correlated, optimizing the general GIB principle is challenging under standard variational-bound derivations.The usual i.i.d. assumption does not directly fit graph-structured data.
  • 3 Graph Information Bottleneck: A local-dependence assumption restricts the space of optimal representations, making GIB more tractable by using only data from neighbors within a fixed hop range.Data elsewhere in the graph is treated as independent of a node once its local neighborhood is given.
  • 3 Graph Information Bottleneck: At each iteration, node representations incorporate neighbors while the graph structure is locally adjusted to control information flow, and predictions use the final representation.The formulation optimizes locally dependent distributions over intermediate representations and structures.

X ) and I(D; Z(L)

GIB derives variational bounds for its structural and feature information terms while accounting for correlated graph data, then instantiates the principle in GIB-Cat and GIB-Bern with categorical and Bernoulli neighbor sampling. These models loosely depend on graph structure, supporting robustness to structural and feature perturbations, and the framework can extend to other GNN architectures.

  • Variational bounds: The variational formulation provides a lower bound for I(Y ; Z(L)X) and an upper bound for I(D; Z(L)X), with bounds derived carefully because graph data points are correlated.The upper-bound construction requires index sets SX and SA that ensure conditional independence between D and Z(L)X.
  • GIB-Cat and GIB-Bern: GIB-Cat and GIB-Bern apply the GIB principle to GAT using categorical or Bernoulli neighbor sampling to refine graph structure before updating node representations.Both models sample structural information from attention-based neighbor distributions and then refine node representations layer by layer.
  • Properties: GIB-Cat and GIB-Bern depend loosely on graph structure because the adjacency matrix only determines potential neighbors, while message passing uses the sampled structural representation.This design is intended to improve robustness to structural attacks while retaining robustness to feature perturbations associated with information-bottleneck models.
  • Objective for training: Training estimates structural information with non-informative categorical or Bernoulli distributions and feature information with a learnable Gaussian-mixture variational distribution.The categorical version uses a uniform distribution, whereas the Bernoulli version adds the hyperparameter α as an additional degree of freedom.
  • Other Formalizations of the GIB Principle: The GIB principle can also be applied to other architectures and node-pair representations, including edge messages in MPNNs, although this is left for future investigation.The framework is presented as architecture-general beyond the GAT-based instantiations.

4 Related Work

Prior work develops GNN representations through message passing, attention, contrastive or mutual-information objectives, and IB-based methods, but this work specifically models feature and structural compression together with prediction for graph data.

  • GNN Representation Learning: GNNs learn node representations by aggregating neighbor information, but their representations can be attacked through malicious feature or structural perturbations [31] [32] [16].Attention mechanisms adaptively learn correlations between nodes and neighbors, while subsequent defenses target the resulting vulnerability.
  • Contrastive and Mutual-Information Methods: Contrastive GNN methods regularize representations by increasing similarity for positive samples and decreasing it for negative samples [28].These objectives can be formulated as mutual-information maximization between node representations and neighbor patches, sub-structures and hidden features, or graphs and sub-structures [37–39].
  • Contrastive and Mutual-Information Methods: Unlike prior contrastive and mutual-information approaches, this model compresses node features and graph structure while improving prediction.The paper characterizes this objective as orthogonal to those previous works [37–39].
  • Information Bottleneck Methods: IB-based work applies information bottleneck principles to deep networks and other domains, whereas this work develops information-theoretic modeling of graph features, structure, and their fusion [21] [40].Several GNN studies also leverage information maximization for unsupervised learning [37] [39].

5 Experiments

Experiments evaluate whether GIB-Cat and GIB-Bern improve GNN robustness to structural and feature attacks, comparing them with standard and defense-oriented baselines. Across citation benchmarks and attack settings, GIB generally improves robustness, while ablations examine the separate roles of structural and feature information bottlenecks.

  • Experimental setup: The evaluation uses Nettack targeted attacks in both evasive and poisoning settings across Cora, Pubmed, and Citeseer, with standard transductive node classification and five random initializations.Models are compared with GCN, GAT, GCNJaccard, and RGCN.
  • Robustness to adversarial attacks: GIB-Cat and GIB-Bern improve targeted-attack accuracy over GAT by averages of 8.9% and 8.4% on Cora and 14.4% and 14.6% on Pubmed, respectively.Table 1 reports average accuracy for 40 targeted nodes across five random initializations under direct attack.
  • Ablation study: Ablations on Cora separately evaluate structural-only AIB-Cat/AIB-Bern and feature-only XIB variants to assess how each GIB component contributes to robustness.AIB models sample structures, whereas XIB samples node representations.
  • Robustness to adversarial attacks: Against GCNJaccard and RGCN, GIB-Cat and GIB-Bern achieve higher average gains on Cora and Pubmed, but under Citeseer poisoning attacks both perform worse than GCNJaccard.The Citeseer limitation is attributed to many low-degree nodes having fewer neighbors than the specified number of perturbations.
  • Robustness to feature perturbations: GIB-Cat and GIB-Bern consistently outperform models without feature information bottlenecks under increasing Gaussian feature noise, especially at λ = 1.5.Structure-only AIB models perform slightly worse than or equivalently to the full GIB models, indicating benefits when feature perturbations dominate.

6 Conclusion and Discussion

The paper introduces Graph Information Bottleneck (GIB) for learning minimal sufficient representations of graph-structured data and demonstrates its efficacy through adversarial-robustness evaluation of GAT trained under GIB.

  • 6 Conclusion and Discussion: GIB learns minimal sufficient information from graph-structured data, and its efficacy is demonstrated by evaluating GIB-trained GAT robustness against adversarial attacks.The framework also leaves open questions about better GIB instantiations for future investigation.

Broader Impact · Appendix · A Preliminaries for Information Bottleneck

The paper highlights applications of graph learning across domains and reports no identified disadvantages, failure consequences, or undesirable bias concerns. Its Information Bottleneck preliminaries define learning representations that preserve target information while limiting input complexity.

  • Broader Impact: Graphs benefit social science, biology, geographical mapping, finance, and recommender systems by jointly representing relationships and data content.GNNs entangle structural and feature information in expressive representations.
  • Broader Impact: The authors identify no groups disadvantaged by the research and no consequences of system failure.Both broader-impact questions are explicitly marked not applicable.
  • Broader Impact: The proposed GIB principle and GIB-GAT leverage node features and structural information, which the authors generally do not consider undesirable biases.Their evaluation datasets are also described as widely used benchmarks generally not believed to contain undesirable biases.
  • A Preliminaries for Information Bottleneck: Information Bottleneck models an encoding Z of input data D for target Y under the Markov chain Z−D−Y.The encoding is stochastic and specified by P(Z|D).
  • A Preliminaries for Information Bottleneck: The IB objective minimizes −I(Y; Z) + βI(D; Z), balancing target information against representation complexity.Increasing β sweeps the Pareto frontier between I(Y; Z) and I(X; Z).
  • A Preliminaries for Information Bottleneck: IB seeks representations that retain shared information I(D; Y) while discarding irrelevant information in H(D|Y).The optimal representation is the minimal sufficient representation covering only I(D; Y) [49].

B Proof for Proposition 3.1 … E Permutation Invariance of GIB-Cat and GIB-Bern

The appendix proves the key information-theoretic propositions using variational bounds, data-processing arguments, and ordered mutual-information decompositions, derives a contrastive-loss alternative, and establishes permutation invariance for GIB-Cat and GIB-Bern. The invariance proof uses induction through the model and neighbor-sampling steps.

  • B Proof for Proposition 3.1: Proposition 3.1 is proved by applying the Nguyen–Wainwright–Jordan bound to the relevant mutual-information expression.The proof explicitly invokes Lemma B.1 and substitutes the graph representation variables into the bound.
  • C Proof for Proposition 3.2: Proposition 3.2 derives its first inequality from the data-processing inequality and the Markov property, then bounds the second through an ordering and decomposition of representation variables.The proof defines an order over variables, decomposes mutual information into terms, and bounds those terms using mutual-information properties and the definitions of AIB(l) and XIB(l).
  • D The Contrastive Loss Derived from the Variational Bound Eq. (2): The variational bound can alternatively be characterized with a contrastive loss [28] that may empirically improve model robustness.The construction retains Q1, estimates Q2 using representations from a randomly sampled graph, and discards the final term and constants because the term is empirically close to 1.
  • D The Contrastive Loss Derived from the Variational Bound Eq. (2): For the contrastive construction, the perturbed adjacency A′ is uniformly sampled subject to having the same number of edges as A.The sampled structure replaces A when obtaining the last-layer node representation used for the Q2 estimate.
  • E Permutation Invariance of GIB-Cat and GIB-Bern: GIB-Cat and GIB-Bern are permutation invariant: permuting input nodes as Π(D)=(ΠX,ΠAΠ^T) permutes the output node representations correspondingly.The statement is formulated for any permutation matrix Π and relates representations produced from the permuted and original graph-structured data.
  • E Permutation Invariance of GIB-Cat and GIB-Bern: The permutation-invariance result is proved by induction over layers and by checking the model and neighbor-sampling steps sequentially.The proof follows Algorithm 1 and uses the categorical and Bernoulli NeighborSample procedures before concluding the correspondence of representations.

F Summary of the Datasets … G.3 Implementation Details for RGCN and GCNJaccard

The experiments use Cora, Pubmed, and Citeseer with standard train-validation-test splits, and evaluate models under consistent training, selection, and reproducibility protocols. GIB-Cat and GIB-Bern follow GAT-based architectures, while compared baselines use established implementations and tuned hyperparameters.

  • F Summary of the Datasets: Experiments use Cora, Pubmed, and Citeseer with standard train-validation-test splits summarized in Table 4.Table 4 reports the dataset statistics and experimental splits.
  • G Implementation Details for the GIB-Cat, GIB-Bern and Other Compared Models: All models are selected by validation accuracy, trained for 2000 epochs, and averaged over five random seeds with standard deviations reported.The runs use seeds 0, 1, 2, 3, and 4 on NVIDIA GeForce RTX 2080 GPUs with Intel Xeon Gold 6148 CPUs, using PyTorch and PyTorch Geometric.
  • G.1 Implementation Details for the GIB-Cat and GIB-Bern: GIB-Cat and GIB-Bern follow the GAT default architecture with eight attention heads, LeakyReLU activation, 0.6 feature dropout, and dataset-specific learning rates.The learning rate is 0.01 for Cora and Citeseer and 5×10−3 for Pubmed; their objectives substitute the GIB variational terms into Eq. (1).
  • G.1 Implementation Details for the GIB-Cat and GIB-Bern: GIB-Bern’s variational marginal Q(ZX) uses a 100-component learnable diagonal-Gaussian mixture to flexibly approximate P(ZX).The implementation sets SA = [L] and SX = {L −1}, satisfying Proposition 3.2.
  • G.2 Implementation Details for GCN and GAT: GCN and GAT use their default implementations, while GIB-Cat and GIB-Bern retain matching architecture choices for fair comparison.Dropout on GAT attention weights is preserved from the original implementation.
  • G.3 Implementation Details for RGCN and GCNJaccard: RGCN and GCNJaccard use the DeepRobust implementation and are tuned over latent dimension, learning rate, and weight decay for adversarial experiments.GCNJaccard additionally tunes its connection threshold, while RGCN tunes β1 and γ; the best settings are reported in Tables 9–11.

G.4 Additional Details for Adversarial Attack Experiment … I Additional experiments for Deep Graph Infomax (DGI)

Additional experiments detail controlled Nettack and feature-noise evaluations, report comparable training costs for GIB models, and show that GIB-Cat and GIB-Bern outperform DGI on Cora under targeted attacks.

  • G.4 Additional Details for Adversarial Attack Experiment: Nettack evaluates 40 test nodes per dataset: 10 with highest classification margins, 10 with lowest correct margins, and 20 randomly selected nodes.A different model is independently trained for each target node and evaluated in both evasive and poisoning settings.
  • I Additional experiments for Deep Graph Infomax (DGI): Table 12 measures targeted-node classification accuracy on Cora by averaging results over 40 targets and five random experiment initializations.Bold font identifies the two highest-performing models.
  • G.4 Additional Details for Adversarial Attack Experiment: For each seed, all models are evaluated on the same 40 target nodes to eliminate differences caused by random target sampling.Models are trained and then fixed before evaluation.
  • G.5 Additional Details for Feature Attack Experiment: Feature attacks average 25 instances per setting: five model seeds and five random node-feature attacks for each seed.Noise added to each feature dimension is λ · r · ϵ, with r the mean maximum feature value per node and ϵ ∼N(0, 1).
  • H Training time for GIB-Cat and GIB-Bern: GIB-Cat and GIB-Bern have training times on the same order as GAT because they use similar parameter counts and computational complexity.With two layers, GIB-Cat takes 98s and GIB-Bern 84s for 2000 epochs, versus 51s for GAT on the same GPU.
  • I Additional experiments for Deep Graph Infomax (DGI): GIB-Cat and GIB-Bern outperform DGI by a large margin on Cora under direct Nettack attacks.Table 12 reports average accuracy across 40 targeted nodes and five random initializations; bold denotes the top two models.

J More Detailed Analysis of Adversarial Attack in Section 5.1

The analysis attributes Citeseer’s poorer model performance to its low-degree target nodes, which are especially vulnerable to added-edge structural attacks. Most Nettack perturbations are structural, typically add cross-class edges, and this pattern aligns with GCNJaccard’s edge-filtering assumption [34].

  • Adversarial perturbation statistics: Citeseer has more target nodes with degrees below 1, 2, 3, and 4 than Cora or Pubmed, helping explain the five models’ worse performance there.
  • Adversarial perturbation statistics: At least 99.1% of Nettack attacks are structural, and at least 83.4% of structural attacks add edges, with Citeseer having the largest fraction.
  • Adversarial perturbation statistics: At least 98.5% of added edges connect nodes from different classes.
  • Interpretation: Citeseer’s low-degree target nodes are particularly prone to added-edge attacks, matching GCNJaccard’s assumption that low-feature-similarity edges should be deleted during poisoning.The passage states this is probably why GCNJaccard performs better in Citeseer under Nettack poisoning, but the supplied text is truncated before completing that claim.
Loading 2010.12811v1…