Source-linked AI summary
Graph Convolutional Networks using Heat Kernel for Semi-supervised Learning
Bingbing Xu, Huawei Shen, Qi Cao, Keting Cen, Xueqi Cheng
TL;DR
Graph-based semi-supervised learning needs to capture smoothness across graph-connected nodes, but existing methods face difficulty selecting neighborhoods that reflect relevant structural information. GraphHeat applies heat-kernel filtering and heat diffusion to emphasize smooth signals and determine neighboring nodes flexibly, achieving state-of-the-art classification results across Cora, Citeseer, and Pubmed.
Problem
Graph-based semi-supervised learning must capture smoothness of labels or features over graph nodes, while existing methods face an open challenge in determining appropriate neighborhoods.
Method
GraphHeat uses heat kernels to discount high-frequency filters, emphasize low-frequency filters, and use heat diffusion to determine neighboring nodes from local graph structure.
Results
GraphHeat achieves state-of-the-art results for graph-based semi-supervised classification across the Cora, Citeseer, and Pubmed benchmark datasets.
Takeaways & Limitations
GraphHeat provides a graph convolution approach that captures graph smoothness while flexibly determining neighboring nodes without restricting their range solely by order.
Abstract
from arXiv · showhide
Graph convolutional networks gain remarkable success in semi-supervised learning on graph structured data. The key to graph-based semisupervised learning is capturing the smoothness of labels or features over nodes exerted by graph structure. Previous methods, spectral methods and spatial methods, devote to defining graph convolution as a weighted average over neighboring nodes, and then learn graph convolution kernels to leverage the smoothness to improve the performance of graph-based semi-supervised learning. One open challenge is how to determine appropriate neighborhood that reflects relevant information of smoothness manifested in graph structure. In this paper, we propose GraphHeat, leveraging heat kernel to enhance low-frequency filters and enforce smoothness in the signal variation on the graph. GraphHeat leverages the local structure of target node under heat diffusion to determine its neighboring nodes flexibly, without the constraint of order suffered by previous methods. GraphHeat achieves state-of-the-art results in the task of graph-based semi-supervised classification across three benchmark datasets: Cora, Citeseer and Pubmed.
1 Introduction
Graph convolutional networks extend CNNs to non-Euclidean graph data, but existing spatial and spectral approaches face challenges in selecting informative neighborhoods and capturing graph smoothness. GraphHeat addresses these challenges with heat-kernel filtering and heat-diffusion-based neighborhoods, achieving state-of-the-art semi-supervised classification results on three benchmarks.
- CNNs succeed on Euclidean data, motivating graph convolutional networks for naturally non-Euclidean graph-structured data.
- Spatial methods define convolution as a weighted average over neighboring nodes, but selecting an appropriate neighborhood remains an open challenge.
- Spectral methods define graph convolution through graph Fourier bases and emphasize eigenvectors with smaller eigenvalues because they represent smoother graph signals.
- GraphHeat uses heat kernels to emphasize low-frequency filters and discount high-frequency signal variation, improving its capture of graph smoothness.
- GraphHeat uses heat diffusion to determine neighboring nodes from the target node's local structure and achieves state-of-the-art semi-supervised classification across Cora, Citeseer, and Pubmed.
2 Preliminary
The preliminary framework represents graphs with adjacency and Laplacian matrices, whose eigenvectors provide graph-frequency bases for Fourier analysis. Graph convolution methods then parameterize spectral filters, with polynomial approximations improving localization and reducing computational or parameter costs.
- 2.1 Graph Definition: An undirected graph is represented by nodes, edges, and a symmetric adjacency matrix, while its Laplacian is formed from the degree and adjacency matrices.
- 2.1 Graph Definition: The normalized Laplacian has orthonormal eigenvectors with non-negative eigenvalues ordered by frequency, yielding the decomposition L = UΛU^⊤.
- 2.2 Graph Fourier Transform: Graph Fourier transform maps a graph signal x to spectral coefficients through ˆx = U^⊤x, with x = Uˆx as the inverse transform.
- 2.3 Graph Convolutional Networks: Spectral CNN represents graph convolution kernels with learnable coefficients associated with Fourier bases, but its non-parametric kernel is not spatially localized and can require O(n) parameters.
- 2.3 Graph Convolutional Networks: ChebyNet parameterizes the spectral kernel with a polynomial expansion whose order K and coefficients α_k control the filter.
- 2.3 Graph Convolutional Networks: GCN simplifies ChebyNet to a first-order polynomial approximation with K = 2, while combined filters accelerate computation and reduce parameter complexity.
3 GraphHeat for Semi-supervised Learning
GraphHeat targets graph smoothness by suppressing high-frequency signal variation and uses heat diffusion to define flexible, structure-sensitive neighborhoods for semi-supervised learning.
- 3.1 Motivation: Graph smoothness treats connected nodes as tending to share labels or similar features, motivating graph-based semi-supervised learning.The paper measures smoothness through similarity of signal values on connected nodes, normalized by node degree.
- 3.1 Motivation: Previous spectral and spatial approaches do not reliably suppress high-frequency signals, limiting their ability to capture graph smoothness.ChebyNet assigns increasing weights to high-frequency filters, while GCN uses a first-order approximation; the paper summarizes these methods as failing to capture smoothness well.
- 3.2 GraphHeat: Graph Convolutional using Heat Kernel: GraphHeat uses heat-kernel filters whose weights decrease with eigenvalue, thereby discounting high-frequency basic filters and producing a low-pass graph convolution.Its heat kernel is f(λ_i) = e^-sλ_i, and the convolution combines heat-diffusion terms with learnable coefficients.
- 3.3 GraphHeat: Defining Neighboring Nodes under Heat Diffusion: Heat diffusion defines neighboring nodes by similarity threshold rather than fixed shortest-path order, allowing high-order relevant nodes and excluding irrelevant low-order nodes.The scaling parameter s controls diffusion, and the neighborhood range can vary across target nodes without increasing parameter complexity with neighborhood order.
- 3.4 Architecture: The two-layer GraphHeat architecture applies heat-kernel graph convolution and trains its parameters with cross-entropy over labeled nodes.The first layer maps p input features to q output features, and the second maps them to c class predictions.
4 Experiments
Experiments evaluate GraphHeat on three citation-network benchmarks, compare it with traditional and graph-convolution baselines, and examine hyper-parameter effects, case behavior, and neighborhood-range flexibility. GraphHeat achieves state-of-the-art results across all three datasets while heat diffusion adapts which nodes contribute to each target.
- Datasets: Experiments use Cora, Citeseer, and Pubmed citation networks, where nodes are documents and edges are citation links.Label rate denotes the proportion of labeled nodes used for training.
- Baselines: GraphHeat is compared with traditional semi-supervised methods and spectral and spatial graph convolutional networks.The graph-convolution baselines include ChebyNet, GCN, MoNet, and GAT.
- Performance on Node Classification Task: GraphHeat achieves state-of-the-art node-classification results on Cora, Citeseer, and Pubmed, outperforming all baseline methods.The model uses heat-based smoothing by discounting high-frequency filters and modulates parameter s to suit diverse networks.
- Influence of Hyper-parameter s and ϵ: On Cora, accuracy initially increases with s but drops when diffusion includes irrelevant nodes; increasing ϵ substantially decreases accuracy by discarding relevant nodes.A small ϵ can speed computation and remove noise, whereas a large ϵ can overlook graph structure.
- Case Study: In a Cora case study, GraphHeat uses heat diffusion to include informative second-order neighbors, whereas GCN relies on first-order neighbors with conflicting labels.Some second-order neighbors can receive greater weights than first-order neighbors, helping GraphHeat assign label 3 correctly in the illustrated case.
- Case Study: GraphHeat flexibly varies neighborhood range across target nodes instead of fixing it solely by hop order.For a fixed s, some nodes include only part of their immediate neighborhood while others reach a larger range.
5 Conclusion
GraphHeat enforces graph smoothness by discounting high-frequency filters and uses heat diffusion to determine neighboring nodes without restricting them by order. It consistently outperforms previous methods across three benchmark datasets.
- GraphHeat applies heat kernels to discount high-frequency filters and assign greater importance to low-frequency filters.This enforces smoothness in graph signals because higher-eigenvalue eigenvectors are unsmooth.
- Heat diffusion determines neighboring nodes instead of restricting neighborhoods solely by graph order.This allows the method to use local structure and relevant smoothness information more flexibly.
- GraphHeat consistently outperforms previous methods on graph-based semi-supervised learning benchmarks.The reported benchmarks are Cora, Citeseer, and Pubmed.