PaperlayerView exact revision on arXiv

Source-linked AI summary

Towards Deeper Graph Neural Networks with Differentiable Group Normalization

Kaixiong Zhou, Xiao Huang, Yuening Li, Daochen Zha, Rui Chen, Xia Hu

arXiv:2006.06972v1cs.LGstat.ML

TL;DR

Increasing GNN depth can make node representations indistinguishable, while pair-based approaches overlook community structure and may be sub-optimal. The paper introduces two over-smoothing metrics and differentiable group normalization, which independently normalizes softly clustered groups. Experiments report that DGN slows performance degradation and enables deeper GNNs with higher node-classification performance.

  • Problem

    Deeper GNNs suffer over-smoothing, and existing pair-based approaches overlook community structure needed to organize same-class and different-class representations.

  • Method

    The paper introduces group distance ratio, instance information gain, and differentiable group normalization, which softly clusters nodes and normalizes groups independently.

  • Results

    DGN significantly outperforms other normalization methods across reported cases, with average improvements of 37.8% over NN, 7.1% over BN, and 12.8% over PN.

  • Takeaways & Limitations

    DGN slows performance degradation from over-smoothing and enables deeper GNNs with higher performance on attributed networks and missing-feature scenarios.

Abstract

from arXiv · show

Graph neural networks (GNNs), which learn the representation of a node by aggregating its neighbors, have become an effective computational tool in downstream applications. Over-smoothing is one of the key issues which limit the performance of GNNs as the number of layers increases. It is because the stacked aggregators would make node representations converge to indistinguishable vectors. Several attempts have been made to tackle the issue by bringing linked node pairs close and unlinked pairs distinct. However, they often ignore the intrinsic community structures and would result in sub-optimal performance. The representations of nodes within the same community/class need be similar to facilitate the classification, while different classes are expected to be separated in embedding space. To bridge the gap, we introduce two over-smoothing metrics and a novel technique, i.e., differentiable group normalization (DGN). It normalizes nodes within the same group independently to increase their smoothness, and separates node distributions among different groups to significantly alleviate the over-smoothing issue. Experiments on real-world datasets demonstrate that DGN makes GNN models more robust to over-smoothing and achieves better performance with deeper GNNs.

1 Introduction

GNN neighborhood aggregation can cause over-smoothing as depth increases, while pair-based remedies overlook community structure. The paper introduces group-aware metrics and differentiable group normalization to support deeper, more accurate GNNs.

  • Motivation: Neighborhood aggregation smooths node representations, but deeper GNNs can make them indistinguishable and degrade downstream performance.This over-smoothing issue limits how deep GNN models can become.
  • Motivation: Pair-distance methods separate linked and unlinked nodes but ignore communities, although same-class unconnected nodes may need similar representations.In Pubmed, 36% of unconnected node pairs belong to the same class.
  • Challenges: Over-smoothing is difficult to quantify because it reflects local relations and global structures, while group information is often unavailable during dynamic learning.Suitable clustering must align with embeddings and labels as they change.
  • Contributions: The paper proposes group distance ratio and instance information gain to measure over-smoothing from group-level and instance-level perspectives.The first measures inter-group versus intra-group representation distance; the second measures input information loss during smoothing.
  • Contributions: Differentiable group normalization softly clusters nodes and normalizes each group independently, separating distinct groups to alleviate over-smoothing.The method is designed to preserve within-group similarity while distinguishing different groups.
  • Results: Deeper GNNs equipped with differentiable group normalization yield better node classification accuracy.The paper reports this result empirically.

2 Quantitative Analysis of Over-smoothing Issue

The analysis frames GNN aggregation as graph-wide smoothing that can erase useful distinctions with depth. It evaluates group- and instance-aware metrics, including their behavior in an SGC study on Cora.

  • 2.1 Preliminaries: GNNs update nodes by aggregating themselves and their neighbors, smoothing representations and causing convergence toward similar vectors as depth increases.The final representation captures neighborhood information within K hops, but performance deteriorates as K increases.
  • 2.2 Measuring Over-smoothing with Group Structures: Existing pair-distance measurements can miss over-smoothing because unlinked nodes in the same class or community may appropriately require close representations.The proposed analysis therefore considers global communities alongside individual nodes.
  • 2.2 Measuring Over-smoothing with Group Structures: Group distance ratio measures inter-group representation distance relative to intra-group distance, favoring separated groups and similar members within each group.A small ratio indicates mixed groups and over-smoothing.
  • 2.2 Measuring Over-smoothing with Group Structures: Instance information gain measures the dependency between a node’s input feature and final representation through mutual information.As smoothing intensifies and self-features are lost, instance information gain becomes small.
  • 2.3 Illustration of Proposed Over-smoothing Metrics: On Cora with SGC, graph convolutions improve test accuracy through K = 5 before over-smoothing worsens performance.Figure 1 compares test accuracy, instance information gain, and group distance ratio across normalization methods.

3 Differentiable Group Normalization

DGN addresses over-smoothing by softly clustering nodes and normalizing each group independently, while preserving input information and separating group distributions. Experiments show that it stabilizes deeper GNNs and improves performance, including in missing-feature settings.

  • Objective and Design: DGN preserves the input embedding while applying group normalization, improving instance information gain and group distance ratio without directly optimizing the non-differentiable regularized objective.The input-preserving combination is distinct from a conventional GNN skip connection, which links outputs from successive layers.
  • Proposed Technique: DGN softly clusters nodes and normalizes their embeddings independently within groups, making same-group representations similar while separating distributions across groups.The assignment is learned during dynamic training and is intended to align with embeddings and labels.
  • Differentiable Clustering: DGN learns group assignments from node embeddings using a trainable linear model followed by row-wise softmax over groups.Nodes with close embeddings receive high probability of sharing a group.
  • Complexity: DGN-layer time complexity is O(nd(k)G + GT), increasing linearly with the number of groups G.Here T is treated as a constant depending on embedding dimension and node number.
  • Experiments: 79.7% accuracy is achieved with DGN at K = 20, while missing-feature experiments find best performance at 50, 20, and 8 layers for SGC, GCN, and GAT, respectively.The missing-feature results use Cora with validation and test features replaced by zeros; these depths exceed the two- or three-layer shallow models commonly used.

4 Experiments

Experiments evaluate DGN on real-world node-classification benchmarks, comparing normalization methods across depths and missing-feature settings. DGN alleviates over-smoothing, supports deeper GNNs, and remains effective across hyperparameter choices.

  • Experiment Setup: Experiments compare DGN with none, batch, and pair normalization across GCN, GAT, and SGC models on four datasets.Models are evaluated over varying layer depths, including settings with missing node features.
  • Studies on alleviating the over-smoothing problem: DGN almost always outperforms other normalization methods at matched depths and greatly slows performance degradation.Self-preserved input features and independent group normalization retain node information while separating group representations.
  • Studies on enabling deeper and better GNNs: DGN significantly outperforms competing normalization methods in missing-feature settings, with average improvements of 37.8% over NN, 7.1% over BN, and 12.8% over PN.The best-performing normalized models generally use larger optimal layer counts than vanilla GNNs.
  • Hyperparameter studies: With 20-layer GCNs on Cora with missing features, performance is studied across group number G and balancing factor λ.Figure 3 also visualizes representations without normalization and with DGN; colors indicate classes and black triangles indicate group running means.
  • Hyperparameter studies: Performance drops greatly when λ is near zero, while accuracy is relatively insensitive to G and can improve with suitable λ values.DGN reaches 74.7% with G = 1, λ = 0.1, and 76.3% with G = 10, λ = 0.01.
  • Node representation visualization: Independent group normalization separates running means and disentangles node representations, although a group may contain nodes from multiple classes.In the illustrated setting, only 6 of 10 groups are adopted.

5 Conclusion

The paper proposes graph-structure-based metrics and DGN to address over-smoothing. Experiments show slower performance degradation, deeper usable GNNs, and higher performance on attributed-network classification with missing features.

  • 5 Conclusion: The paper introduces group distance ratio, instance information gain, and DGN to improve GNN performance against over-smoothing.DGN independently normalizes groups of similar nodes to separate representations across classes.
  • 5 Conclusion: Experiments on real-world classification tasks show that DGN greatly slows performance degradation and enables deeper GNNs.The reported scope includes attributed networks and settings with missing features.

Broader Impact

The paper’s broader impact is framed around quantitative over-smoothing analysis and deeper graph neural network modeling. The proposed metrics and DGN are intended to support graph applications involving complex networked data.

  • Broader Impact: The proposed metrics are intended to indicate over-smoothing during the development of deeper GNN models.The stated metrics are instance information gain and group distance ratio.
  • Broader Impact: Differentiable group normalization is presented as a tool for tackling over-smoothing and modeling deeper GNN variants.The paper connects this capability to processing networked and complex graph-structured data.

A Dataset Statistics

The experiments use four benchmark datasets—Cora, Citeseer, Pubmed, and CoauthorCS—for node classification. Additional missing-feature scenarios are created by removing node features from validation and test sets.

  • A Dataset Statistics: The benchmark suite comprises Cora, Citeseer, Pubmed, and CoauthorCS.These datasets are used for node classification and are accompanied by dataset statistics in Table 3.
  • A Dataset Statistics: Missing-feature scenarios are created by removing node features in validation and test sets.The altered scenarios are used to study whether normalization enables deeper GNNs to achieve better performance.

B Running Environment

The experiments use PyTorch implementations on a specified CPU, GPU, and memory configuration. DGN is parallelized so its practical time cost is comparable to traditional batch normalization.

  • The GNN models and normalization approaches are implemented in PyTorch and evaluated on a machine with Xeon CPUs, a GTX-1080 Ti GPU, and 128GB memory.
  • Parallel implementation makes DGN’s practical time cost comparable to traditional batch normalization.

C GNN Models

The study evaluates GCN, GAT, and SGC models, whose neighborhood aggregation mechanisms differ in weighting and trainability. Batch, pair, and DGN normalization modules are used to examine deeper GNN behavior.

  • C GNN Models: The experiments cover graph convolutional networks, graph attention networks, and simple graph convolution networks.
  • C GNN Models: GCN combines a node with its neighbors using weights determined by vertex degrees, while GAT learns trainable link weights through attention.
  • C GNN Models: SGC removes trainable layer parameters and intermediate nonlinear activations from GCN, with reported benefits for over-fitting and vanishing gradients in deeper models.
  • D Normalization Baselines: Batch normalization rescales layer embeddings using running means and variances, whereas pair normalization removes trainable scale and shift parameters to maintain average node-pair distance.
  • D Normalization Baselines: The balancing factor λ is tuned on validation data from a specified candidate set as the number of GNN layers increases.

F Instance Information Gain

Instance information gain measures information retained between input features and node representations. The paper estimates it with KDE under Gaussian and empirical-distribution assumptions, then observes that DGN preserves more information as depth increases.

  • F Instance Information Gain: Instance information gain is estimated as mutual information between input features and representation vectors using kernel-density estimators.
  • F Instance Information Gain: The KDE treatment assumes input features or representations follow a mixture of Gaussians because deterministic neural-network mappings otherwise yield infinite mutual information.
  • F Instance Information Gain: Input features are modeled as true values plus Gaussian noise, with noise distributed as N(0, σ2I).
  • F Instance Information Gain: The empirical input distribution assigns each node feature probability 1/|V| across the dataset.
  • F Instance Information Gain: Representation vectors are binned by the index of their largest element, producing C discrete representation classes for probability estimation.
  • F Instance Information Gain: GIns decreases with depth and approaches zero at K = 30 or 120 without normalization, while DGN retains the largest GIns among the compared normalization approaches.

G Performance Comparison on Attributed Graphs

Across attributed graph datasets, the experiments compare DGN with no, batch, and pair normalization using test accuracy, instance information gain, and group distance ratio. DGN generally slows accuracy degradation as GNN depth increases and maintains competitive shallow performance.

  • G Performance Comparison on Attributed Graphs: The performance comparison reports test accuracy, instance information gain, and group distance ratio across the concerned attributed graph datasets.
  • G Performance Comparison on Attributed Graphs: DGN generally slows the decline in test accuracy as layer number increases compared with other normalization techniques.
  • G Performance Comparison on Attributed Graphs: For models with at most five layers, DGN achieves competitive performance compared with no normalization and does not damage model performance.
  • G Performance Comparison on Attributed Graphs: The figures compare differentiable group normalization with none, batch, and pair normalization on attributed Cora, Citeseer, Pubmed, and CoauthorCS.

H Performance Comparison in Scenarios with Missing Features

With missing features, the evaluation compares DGN against none, batch, and pair normalization using test accuracy, group distance ratio, and intra-group distance. DGN supports deeper GNNs and achieves the largest test accuracy in these scenarios.

  • Figures 8–11 evaluate test accuracy, group distance ratio, and intra-group distance on Cora, Citeseer, Pubmed, and CoauthorCS.The comparisons include differentiable group normalization, no normalization, batch normalization, and pair normalization.
  • Intra-group distance is the average node-pair distance among nodes within the same group.Its mathematical expression corresponds to the denominator of Equation (3) in the main manuscript.
  • DGN achieves the largest test accuracy when using deeper neural architectures with more graph convolutional layers.The reported scenarios involve missing features and compare DGN with none, batch, and pair normalizations.
  • With missing features, DGN enables deeper GNNs to exploit neighborhood structure across multiple hops while relieving over-smoothing.
Loading 2006.06972v1…