Source-linked AI summary
Geom-GCN: Geometric Graph Convolutional Networks
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, Bo Yang
TL;DR
Existing MPNN aggregators can lose neighborhood structure and fail to capture long-range dependencies in disassortative graphs. The paper introduces a permutation-invariant geometric aggregation scheme based on a continuous latent space, instantiates it as Geom-GCN, and reports state-of-the-art performance across open graph datasets.
Problem
MPNN aggregators lose structural information in neighborhoods and lack the ability to capture long-range dependencies in disassortative graphs.
Method
The paper maps graphs to a continuous latent space, constructs geometric structural neighborhoods, and applies a permutation-invariant bi-level aggregator, implemented as Geom-GCN.
Results
Geom-GCN achieves state-of-the-art performance across a wide range of open graph datasets.
Takeaways & Limitations
Geometric aggregation can recover discriminative structures and long-range dependencies by operating across graph and latent spaces.
Abstract
from arXiv · showhide
Message-passing neural networks (MPNNs) have been successfully applied to representation learning on graphs in a variety of real-world applications. However, two fundamental weaknesses of MPNNs' aggregators limit their ability to represent graph-structured data: losing the structural information of nodes in neighborhoods and lacking the ability to capture long-range dependencies in disassortative graphs. Few studies have noticed the weaknesses from different perspectives. From the observations on classical neural network and network geometry, we propose a novel geometric aggregation scheme for graph neural networks to overcome the two weaknesses. The behind basic idea is the aggregation on a graph can benefit from a continuous space underlying the graph. The proposed aggregation scheme is permutation-invariant and consists of three modules, node embedding, structural neighborhood, and bi-level aggregation. We also present an implementation of the scheme in graph convolutional networks, termed Geom-GCN (Geometric Graph Convolutional Networks), to perform transductive learning on graphs. Experimental results show the proposed Geom-GCN achieved state-of-the-art performance on a wide range of open datasets of graphs. Code is available at https://github.com/graphdml-uiuc-jlu/geom-gcn.
1 INTRODUCTION
Existing MPNN aggregators can lose neighborhood structure and miss informative long-range dependencies in disassortative graphs. The paper proposes geometric aggregation, implemented as Geom-GCN, to address both weaknesses using a continuous latent space.
- Motivation: MPNN aggregators may lose structural information by treating neighborhood messages as an indistinguishable set.GCN, for example, sums normalized messages without distinguishing which node contributed each message.
- Motivation: MPNNs may fail to capture important features from distant but informative nodes in disassortative graphs.Their local neighborhoods can mix relevant distant information with many irrelevant proximal messages, washing out the useful signal.
- Approach: The geometric aggregation scheme maps graphs to a continuous latent space and uses geometric relationships to construct structural neighborhoods.The paper motivates this design through classical neural networks and network geometry, which connect graphs with an underlying latent continuous space.
- Approach: A bi-level aggregator updates node representations while preserving permutation invariance for graph-structured data.The scheme combines node embedding, structural neighborhoods, and bi-level aggregation.
- Implementation: Geom-GCN implements the scheme in graph convolutional networks for transductive node classification using Euclidean and hyperbolic embedding spaces.Different embedding methods are selected to preserve suitable topology patterns for different applications.
- Evaluation: The paper reports state-of-the-art results for Geom-GCN across a wide range of open graph datasets.Its contribution includes extensive comparisons with state-of-the-art methods on challenging benchmarks.
2 GEOMETRIC AGGREGATION SCHEME
The geometric aggregation scheme combines node embeddings, structural neighborhoods, and bi-level aggregation to preserve neighborhood structure while capturing long-range dependencies. It uses latent-space geometry to distinguish relationships among nodes and remains permutation-invariant.
- Overview: The scheme has three modules: node embedding, structural neighborhood, and bi-level aggregation.Node embedding maps graph nodes to a latent continuous space; the other modules construct and aggregate geometric neighborhoods.
- Structural neighborhood: Structural neighborhoods combine graph-adjacent nodes with latent-space neighbors within radius ρ.Latent-space neighbors may be distant in the graph but similar in the embedding, supporting long-range dependency capture.
- Structural neighborhood: The relational operator τ assigns each ordered node pair a single discrete geometric relationship in the latent space.The relationship set can be chosen according to the latent space and application, such as directional units in a 2-D grid.
- Bi-level aggregation: Low-level aggregation groups nodes sharing a neighborhood and geometric relationship, while high-level aggregation combines the resulting virtual nodes using their identities.The high-level function can use ordered inputs such as concatenation, explicitly distinguishing structural roles.
- Properties: The bi-level aggregation is permutation-invariant and explicitly models neighborhood structure through latent-space geometric relationships.The scheme is intended to distinguish structural roles that ordinary permutation-invariant message aggregation treats as an undifferentiated set.
- Case study: Structural neighborhoods can distinguish certain non-isomorphic graphs by assigning different geometric relationships and therefore different aggregation inputs to neighbors.In the case study, the center node receives different relationship-specific inputs in the two example graphs.
3 GEOM-GCN: AN IMPLEMENTATION OF THE SCHEME
Geom-GCN implements the geometric aggregation scheme with graph convolutional layers using graph embeddings, latent-space neighborhoods, relationship operators, and bi-level aggregation.
- Implementation: Geom-GCN is a graph-convolutional implementation of the geometric aggregation scheme for transductive graph learning.Its implementation specifies node embedding, structural neighborhood, and bi-level aggregation functions.
- Node embedding: The implementation uses Isomap, Poincare embedding, and struc2vec to construct latent spaces for aggregation.These embeddings preserve connection, distance, or structural patterns to varying degrees.
- Structural neighborhood: The latent-space radius ρ is increased until the average latent-neighborhood size matches the average graph-neighborhood size.The graph neighborhood contains adjacent nodes, while the latent neighborhood contains nodes within distance ρ.
- Relationship operator: In 2-D Euclidean or hyperbolic spaces, τ uses four relative-position relationships: upper left, upper right, lower left, and lower right.The operator uses rectangular coordinates in Euclidean space and angular coordinates in hyperbolic space.
- Bi-level aggregation: Geom-GCN uses normalized summation for low-level aggregation, concatenation for high-level aggregation except at the final layer, and ReLU activation.The final high-level aggregation uses mean instead of concatenation.
4 EXPERIMENTS
The experiments evaluate Geom-GCN against GCN and GAT on transductive node-label classification across diverse open graph datasets.
- Evaluation: Geom-GCN is compared with GCN and GAT on transductive node-label classification tasks across a wide variety of open graph datasets.The supplied experiment passage specifies the comparison and task scope but reports no numerical results.
4.1 DATASETS
The evaluation uses nine open graph datasets spanning citation, webpage, actor co-occurrence, and Wikipedia networks with node features and labels defined by each domain.
- Dataset collection: Nine open graph datasets are used to validate Geom-GCN.Their characteristics are summarized in the dataset statistics table.
- Citation networks: Citation-network datasets represent papers as nodes, citations as edges, bag-of-words vectors as features, and academic topics as labels.The citation benchmarks are Cora, Citeseer, and Pubmed.
- WebKB: WebKB datasets represent webpages and hyperlinks, using bag-of-words features and five webpage-category labels.The evaluated WebKB subsets are Cornell, Texas, and Wisconsin.
- Actor co-occurrence network: The actor co-occurrence dataset links actors appearing on the same Wikipedia page and labels them using words from their Wikipedia pages.Node features are keywords from the corresponding Wikipedia pages.
- Wikipedia networks: Chameleon and squirrel are Wikipedia page networks whose nodes are pages, edges are mutual links, and labels reflect average monthly traffic.Their node features consist of informative nouns from the pages.
4.2 EXPERIMENTAL SETUP
The experiments use three embedding spaces and standardized two-layer training settings, with model performance averaged over ten random train/validation/test splits.
- Geom-GCN variants use Isomap, Poincare, or struc2vec embeddings in two-dimensional spaces, with mean and concatenation for low- and high-level aggregation.
- All models receive equal hyperparameter-search budgets over hidden units, learning rate, weight decay, and dropout, using two layers and Adam.
- Geom-GCN uses eight times GCN’s hidden units because it has eight virtual nodes, while GAT uses eight attention heads in its first layer.
- Nodes are split 60%, 20%, and 20% by class for training, validation, and testing, and results average performance across ten random splits.
4.3 RESULTS AND ANALYSIS
Geom-GCN generally achieves state-of-the-art classification accuracy, while analyses show that latent-space neighborhoods particularly help disassortative graphs. The method incurs higher theoretical complexity than GCN, although its measured runtime is comparable to GAT.
- Geom-GCN generally achieves state-of-the-art mean classification accuracy, and selecting an embedding suited to disassortative or hierarchical graphs can yield significant improvement.
- Geom-GCN aggregates messages from graph and latent-space neighborhoods, while some single-neighborhood variants outperform two-neighborhood variants.
- Both graph-space and latent-space neighborhoods benefit aggregation in most cases, with latent-space neighborhoods contributing more on disassortative graphs with small β.
- Geom-GCN’s update complexity is O(n × m × 2|R|), which is 2|R| times GCN’s O(n × m) complexity because of virtual nodes.
- After 500 epochs, GCN is fastest, while GAT and Geom-GCN have similar running times.
- Geom-GCN-P representations on Cora show same-label spatial clustering and radial distribution associated with hierarchy learned through Poincare embedding.
4.4 CONCLUSION AND FUTURE WORK
The paper addresses lost discriminative structure and long-range dependencies in graph message passing by connecting discrete graphs to continuous geometric spaces. It proposes geometric aggregation and reports clear advantages over state-of-the-art methods.
- Geom-GCN addresses losses of discriminative structures and long-range dependencies in existing message-passing neural networks.
- The approach uses graph embedding to bridge a discrete graph to a continuous geometric space for spatial aggregation over meaningful neighborhoods.
- The paper proposes a general geometric aggregation scheme with several Geom-GCN implementations, whose experiments validate clear advantages over the state-of-the-art.