Hierarchical Graph Convolutional Networks for Semi-supervised Node Classification

Fenyu Hu, Yanqiao Zhu, Shu Wu, Liang Wang, Tieniu TanIJCAI 2019 · OpenReview

TL;DR

This paper introduces Hierarchical Graph Convolutional Networks (H-GCN), a novel deep learning architecture for semi-supervised node classification. By incorporating hierarchical graph coarsening and refining mechanisms, H-GCN effectively expands the receptive field of traditional Graph Convolutional Networks (GCNs), enabling better capture of global graph information and leading to significant performance improvements, especially in low-label scenarios.

What Problem Does This Paper Address?

Node classification on graph-structured data is a crucial task in many domains, but it's often challenging due to the scarcity of labeled data. Existing Graph Convolutional Networks (GCNs) typically have shallow architectures and rely on aggregating information from only a few hops away (e.g., 2-hop neighborhoods). This limited receptive field hinders their ability to capture broader, global graph structures and makes them struggle when labeled data is scarce, as they cannot effectively propagate limited supervision signals across the entire graph. While deeper GCNs can theoretically increase the receptive field, they often suffer from over-smoothing and are difficult to train.

Methods

The core innovation of H-GCN is its hierarchical structure, which mimics pooling mechanisms used in image processing. It consists of two main components:

  • Graph Coarsening Layers: These layers progressively reduce the graph's complexity. First, a standard GCN operation is applied to learn node representations. Then, a novel two-step grouping strategy is employed:
  • Structural Equivalence Grouping (SEG): Nodes with identical neighbors are grouped into hyper-nodes.
  • Structural Similarity Grouping (SSG): Remaining unmarked nodes are grouped based on their normalized connection strength, prioritizing pairs with higher similarity. This process aggregates structurally similar nodes into hyper-nodes, creating a coarser graph representation.

  • Graph Refining Layers: These layers symmetrically mirror the coarsening process. They use the learned grouping information to restore the finer graph structure and node representations, effectively refining the information captured during coarsening.

H-GCN also incorporates:

  • Node Weight Embedding: To account for the varying number of original nodes represented by each hyper-node, their "weights" are embedded into vectors and concatenated with node features.
  • Multi-channel GCNs: Different GCNs are used in parallel to explore various feature subspaces, with their outputs combined via a weighted average.
  • Shortcut Connections: Similar to ResNets, shortcut connections are used across coarsening and refining layers to facilitate gradient flow in the deeper network.

Datasets

The paper evaluates H-GCN on four widely-used public datasets for semi-supervised node classification:

  • Cora: A citation network.
  • Citeseer: A citation network.
  • Pubmed: A citation network.
  • NELL: A knowledge graph.

The statistics of these datasets (number of vertices, edges, classes, features, and labeling rate) are provided in Table 1. The experiments are conducted in a transductive setting, with a fixed number of labeled samples per class (20 for citation networks, 1 for NELL) and a random split for validation.

Key Insights and Ideas

  • Hierarchical Structure for Global Information: The paper convincingly argues that a hierarchical approach, combining coarsening and refining, is essential for capturing global graph information, which is a significant limitation of shallow GCNs.
  • Effective Node Grouping: The novel SEG and SSG strategies for creating hyper-nodes are crucial for the coarsening process, ensuring that structurally similar nodes are effectively merged.
  • Addressing Scarcity of Labeled Data: H-GCN's ability to achieve substantial gains when labeled data is extremely scarce is a key takeaway. The expanded receptive field allows limited supervision signals to propagate more effectively across the graph.
  • Balancing Depth and Over-smoothing: By using coarsening and refining, H-GCN manages to create a deeper architecture without succumbing to the over-smoothing problem that plagues standard deep GCNs.

Key Results

  • State-of-the-Art Performance: H-GCN consistently outperforms existing state-of-the-art methods (DeepWalk, Planetoid, GCN, GAT, DGCN) across all four benchmark datasets.
  • Significant Accuracy Gains: The paper reports accuracy improvements of up to 5.9% over DGCN and 7.1% over GCN on the NELL dataset.
  • Superior Performance in Low-Label Scenarios: When the number of labeled nodes per class is reduced (e.g., to 5), H-GCN's performance advantage becomes even more pronounced, demonstrating its robustness to limited supervision. For instance, on Pubmed with 5 labeled nodes per class, H-GCN achieves 78.6% accuracy, significantly outperforming GCN (72.2%), GAT (75.4%), and DGCN (76.7%).
  • Ablation Study Validation: Ablation studies confirm that both the coarsening/refining layers and node weight embeddings are critical components contributing to H-GCN's performance.

Limitations and Future Work

  • Hyperparameter Sensitivity: The paper notes that the performance of H-GCN is sensitive to the number of coarsening layers and channels. While they identify optimal ranges (e.g., 4-5 coarsening layers), finding these optimal values might require tuning.
  • Computational Cost: While H-GCN is asymptotically efficient, the hierarchical structure and multiple channels might introduce higher computational overhead compared to simpler GCN models, especially for very large graphs.
  • Future Work: The authors suggest that their hierarchical approach can be extended to other graph-based tasks beyond node classification, such as graph classification or link prediction. Further exploration into more sophisticated grouping strategies or adaptive channel weighting could also be avenues for future research.

Summary updated

BibTeX
@inproceedings{hu2019hierarchical,
  author = {Fenyu Hu and Yanqiao Zhu and Shu Wu and Liang Wang and Tieniu Tan},
  title = {{Hierarchical Graph Convolutional Networks for Semi-supervised Node Classification}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  url = {https://openreview.net/forum?id=y4YwpZfVTst},
}
Figure