Measuring and Improving the Use of Graph Information in Graph Neural Networks

Yifan Hou, Jian Zhang, James Cheng, Kaili Ma, Richard T. B. Ma, Hongzhi Chen, Ming-Chang Yang

TL;DR

This paper introduces two novel metrics, "feature smoothness" ($\mathcal{A}_f$) and "label smoothness" ($\lambda_l$), to quantify how much useful information a graph's structure provides for Graph Neural Networks (GNNs). They then propose CS-GNN, a GNN model that leverages these metrics to selectively aggregate neighborhood information, leading to improved performance on various graph tasks.

What Problem Does This Paper Address?

Graph Neural Networks (GNNs) have shown great promise in learning from graph-structured data by aggregating information from neighboring nodes. However, there's a lack of understanding regarding how much performance gain GNNs actually achieve from this graph information and why they sometimes underperform. The authors identify that simply aggregating all neighbor information isn't always optimal, as some neighbors might provide noisy or even detrimental information for a specific task. This paper aims to bridge this gap by providing a quantitative way to measure the "usefulness" of graph information and developing a GNN that can better leverage this insight.

Methods

The core of the paper lies in two new metrics:

  • Feature Smoothness ($\mathcal{A}_f$): This metric quantifies the "frequency" of feature signals on a graph. A higher $\mathcal{A}_f$ indicates that connected nodes are more likely to have dissimilar features, suggesting that the graph's structure is rich and can potentially provide more information gain. It's calculated based on the variance of feature differences between connected nodes.
  • Label Smoothness ($\lambda_l$): This metric measures the "quality" of the neighborhood information with respect to a given task (e.g., node classification). It quantifies the proportion of connected nodes that have different labels. A higher $\lambda_l$ implies more "negative disturbance" from neighbors, meaning they are less likely to share the same class and thus provide less useful information for classification.

Based on these metrics, the authors propose CS-GNN (Context-Surrounding GNN). CS-GNN uses a context-surrounding framework where a node's representation is updated by combining its current context with aggregated information from its neighbors (the surrounding). Key aspects of CS-GNN include:

  • Multiplicative Attention: CS-GNN employs a multiplicative attention mechanism to compute neighbor aggregation coefficients. This mechanism is inspired by the difference between a node's context and its neighbor's representation, which is influenced by feature smoothness.
  • Selective Aggregation: CS-GNN uses the label smoothness metric ($\lambda_l$) to selectively drop neighbors that are likely to provide negative disturbance. If a neighbor's contribution is deemed unhelpful (based on attention coefficients and $\lambda_l$), its influence is zeroed out.
  • Dimension Adaptation: The dimensionality of the attention mechanism's query vector is dynamically set based on the feature smoothness ($\mathcal{A}_f$), aiming to balance expressive power and avoid overfitting.
  • Side Information Integration: CS-GNN is designed to be extensible and can incorporate side information like local topology features.

Datasets

The paper evaluates CS-GNN on five real-world datasets for node classification:

  • Citation Networks: Citeseer, Cora, PubMed
  • Co-purchasing Network: Amazon (computer)
  • Network Topology: Border Gateway Protocol (BGP) Network. For BGP, they created two versions: BGP (full) and BGP (small) (where unlabeled nodes and their edges were removed to create a more challenging scenario for label propagation).

Key Insights and Ideas

  • Not all graph information is equally useful: The paper convincingly demonstrates that the quantity ($\mathcal{A}_f$) and quality ($\lambda_l$) of information derived from a graph's structure significantly impact GNN performance.
  • Smoothness metrics as diagnostic tools: $\mathcal{A}_f$ and $\lambda_l$ provide valuable insights into why certain GNNs might struggle on specific graphs. For instance, low $\mathcal{A}_f$ (like in PubMed) means less information gain from neighbors, while high $\lambda_l$ (like in BGP) means more noisy or conflicting information.
  • Targeted aggregation is key: CS-GNN's success stems from its ability to intelligently select which neighbors to aggregate from, amplifying useful signals and suppressing noise, rather than blindly combining all neighborhood information.
  • GNNs aren't always superior to feature-based methods: For graphs with very low feature smoothness and high label smoothness, traditional feature-based methods (like MLP) can sometimes outperform GNNs because GNNs might struggle to extract meaningful information or might be overwhelmed by noise.

Key Results

  • CS-GNN consistently achieves competitive or superior performance across all tested datasets compared to baseline methods, including GCN, GraphSAGE, and GAT.
  • On datasets with high feature smoothness and low label smoothness (e.g., Amazon), CS-GNN shows significant improvements.
  • The paper demonstrates that CS-GNN's performance is robust and it achieves good results even on challenging graphs where other GNNs might falter due to over-smoothing or noisy neighborhood information.
  • The effectiveness of the smoothness metrics is validated by showing that CS-GNN's performance correlates with these metrics, and that incorporating local topology features (LTF) provides only marginal improvements, suggesting the core strength lies in the smoothness-aware aggregation.

Limitations and Future Work

  • Over-smoothing: The paper acknowledges that GNNs, including CS-GNN, can suffer from over-smoothing if too many aggregation rounds are used, leading to node representations becoming indistinguishable. This is a general limitation of many GNN architectures.
  • Parameter tuning: While CS-GNN aims to be more principled, the optimal dimension for the attention mechanism based on $\mathcal{A}_f$ is determined empirically.
  • Future work could explore:
    • Developing more sophisticated methods for incorporating side information.
  • Investigating the theoretical underpinnings of the relationship between smoothness metrics and GNN performance more deeply.
  • Extending CS-GNN to other graph-based tasks beyond node classification.

Summary updated

BibTeX
@inproceedings{hou2020measuring,
  author = {Yifan Hou and Jian Zhang and James Cheng and Kaili Ma and Richard T. B. Ma and Hongzhi Chen and Ming-Chang Yang},
  title = {{Measuring and Improving the Use of Graph Information in Graph Neural Networks}},
  booktitle = {International Conference on Learning Representations},
  year = {2020},
  url = {https://openreview.net/forum?id=2tpgyuG2jtP},
}
Figure