Source-linked AI summary
GeniePath: Graph Neural Networks with Adaptive Receptive Paths
Ziqi Liu, Chaochao Chen, Longfei Li, Jun Zhou, Xiaolong Li, Le Song, Yuan Qi
TL;DR
Graph neural networks need meaningful receptive fields on irregular graphs, where fixed or predefined neighborhoods can be limited by noise, node roles, and propagation depth. GeniePath introduces adaptive breadth and depth functions to learn receptive paths, and experiments report competitive or state-of-the-art performance, with reduced sensitivity to propagation depth. The approach is evaluated in both transductive and inductive settings.
Problem
Graph neural networks need to identify meaningful receptive paths because graphs can be noisy, nodes can play different roles, and existing methods may rely on predefined or hand-designed neighborhoods.
Method
GeniePath uses an adaptive path layer with complementary breadth and depth functions to select important neighbors and filter useful signals across multiple hops.
Results
Experiments on several datasets report competitive and state-of-the-art results on large graphs, while GeniePath remains less sensitive to the depth of propagation layers.
Takeaways & Limitations
Selecting appropriate receptive paths for different nodes is important for graph neural networks.
Takeaways & Limitations
On Pubmed, the small dataset and only 60 training labels limit the capacity of the methods, and GCN performs best with exactly two hidden convolutional layers.
Abstract
from arXiv · showhide
We present, GeniePath, a scalable approach for learning adaptive receptive fields of neural networks defined on permutation invariant graph data. In GeniePath, we propose an adaptive path layer consists of two complementary functions designed for breadth and depth exploration respectively, where the former learns the importance of different sized neighborhoods, while the latter extracts and filters signals aggregated from neighbors of different hops away. Our method works in both transductive and inductive settings, and extensive experiments compared with competitive methods show that our approaches yield state-of-the-art results on large graphs.
Introduction
Graph neural networks must learn on irregular, permutation-invariant graph domains where each node has a different receptive field. GeniePath addresses this by adaptively exploring breadth and depth through receptive paths.
- Graph data are irregular, so different nodes can have different receptive fields, unlike data in regular image and sequence domains.
- Deeper graph convolution can expose wider receptive fields, but GCN performance may deteriorate severely when more layers are stacked.
- Existing graph methods either predefine neighbor importance through the graph Laplacian or hand-design spatial receptive fields.
- The proposed adaptive path layer combines breadth selection of significant one-hop neighbors with depth filtering of signals from longer-hop neighborhoods.
- GeniePath describes these adaptively learned receptive fields as receptive paths that guide breadth and depth exploration.
Graph Convolutional Networks
Graph convolutional networks encode node representations from graph neighborhoods, but existing approaches largely predefine propagation structure or aggregate fixed-order neighborhoods. GeniePath motivates learning meaningful receptive paths that adapt both which neighbors matter and how far signals should propagate.
- Graph convolutions encode nodes using signals from their receptive fields for supervised or unsupervised learning.
- Spectral methods: Spectral approaches define neighborhood importance through the graph Laplacian and its Fourier basis, making receptive fields depend on the kernel U.
- GCN: GCN uses a localized first-order spectral convolution with self-looped, symmetrically normalized adjacency, node features, layer parameters, and activation functions.
- Inductive settings: GCN requires precomputed Laplacian normalization, limiting its use in inductive settings; GCN-mean instead averages neighborhoods.
- GraphSAGE: GraphSAGE supports inductive representation learning with aggregators, but its LSTM aggregator uses randomly permuted neighbors and is not permutation invariant.
- Adaptive receptive paths: Existing methods mainly propagate through T-th order neighborhoods, while GeniePath targets meaningful paths that account for graph noise, node roles, features, and hop distance.Its adaptive breadth exploration selects important neighbors, while depth exploration filters useful and noisy signals across hops.
Proposed Approaches
GeniePath learns permutation-invariant receptive paths by separately adapting breadth across one-hop neighbors and depth across increasingly distant neighborhoods. Its layered gated architecture filters signals as receptive fields expand, while sparse computation preserves linear graph-size complexity.
- Permutation Invariance: The method requires neighborhood aggregation to remain unchanged under arbitrary neighbor permutations.Theorem 1 characterizes valid functions through a permutation-invariant decomposition, and this property supports cascading layers.
- Adaptive Receptive Paths: GeniePath treats receptive-path learning as selecting a node-specific subgraph through breadth and depth expansions.Breadth determines which one-hop neighbors matter, while depth determines the importance of neighbors at successive hops.
- Adaptive Path Layer: The adaptive breadth function assigns different importances to one-hop neighbor embeddings, and the adaptive depth function extracts and filters aggregated signals across depths.The depth mechanism uses gated units to add newly useful signals, filter old memory, and produce the next node embedding.
- Adaptive Path Layer: GeniePath maintains a per-node memory that is updated while neighborhoods of increasing shortest-path distance are explored.The memory starts at zero and is updated across layers t = 0, 1, ..., T.
- GeniePath-lazy: GeniePath-lazy postpones adaptive depth evaluation until after stacking adaptive breadth functions to propagate signals to T-th order distance.The variant then applies the depth function to extract and filter signals at different depths.
- Efficient Numerical Computation: Sparse auxiliary matrices reduce generalized attention computation and storage to O(|E|), matching the scale of the graph adjacency matrix.The construction computes attention transformations only for graph edges rather than all node pairs.
Experiments
Experiments evaluate GeniePath across transductive and inductive graph settings, using multiple datasets and strong baselines. Results indicate competitive performance on large graphs, adaptive receptive paths that remain consistent with increasing depth, and sparse neighbor selection.
- Experimental Setup: Experiments cover citation, social, account-device, and protein-interaction graphs under transductive and inductive settings.The evaluation includes Pubmed, BlogCatalog1/2, Alipay, and PPI, with PPI evaluated inductively.
- Baselines: The study compares GeniePath with MLP, node2vec, Chebyshev, GCN variants, GraphSAGE, and GAT.The baselines include methods using node features alone, graph structures, spectral convolutions, neighborhood aggregation, and attention.
- Transductive Results: GCN performs best on Pubmed with exactly two hidden convolutional layers, while adding two more layers severely deteriorates performance.The authors attribute the limited capacity of their methods on this dataset to its small size.
- Transductive Results: GAT and GeniePath* perform best on BlogCatalog1 and BlogCatalog2, and GeniePath* is promising on the large, relatively sparse Alipay graph.Node2vec is not applicable to Alipay because it contains tens of thousands of subgraphs.
- Inductive Results: On inductive PPI, GeniePath* performs extremely promisingly, with adaptive depth more important than GAT’s adaptive breadth alone.The PPI experiments compare against GCN-mean because standard GCN is transductive.
- Depth and Qualitative Analysis: As propagation depth increases on PPI and Alipay, GeniePath maintains consistent classification results while GCN, GAT, and residual GraphSAGE do not.The adaptive path layer learns receptive paths, and neighbor selection produces sparser paths by propagating selected important paths while ignoring others.
Conclusion
GeniePath addresses meaningful receptive-path identification in graph convolutional networks through adaptive breadth and depth functions. Experiments on large benchmarks show improved performance and reduced sensitivity to manually chosen layer depths or neighborhood extents.
- GeniePath identifies meaningful receptive paths using adaptive breadth and depth functions.These functions guide receptive paths for different nodes.
- GeniePath significantly outperforms state-of-the-art approaches on large benchmark data.
- GeniePath is less sensitive to the depths of stacked layers and manually specified neighborhood extents.