Graph Neural Networks (GNNs)

• Graph Neural Networks (GNNs) are standard for machine learning on graphs.
• GNNs are used for node classification, graph classification, and link prediction.
• Graph convolution is a central operation in most GNNs.
• Graph convolution aggregates node features from neighbors for representation updates.
• Graph convolution can be defined in the spectral domain, but is computationally expensive for large graphs.
• Graph convolution can be defined in the vertex domain, which is more efficient but potentially less expressive.
• The heat kernel can define graph convolution efficiently and expressively.

Graph Neural Networks

• A GNN maps graph structured data $G=(V, E)$ with node features $X \in \mathbb{R}^{|V|\times d}$ to node embeddings $Z \in \mathbb{R}^{|V|\times d'}$.
• A single GNN layer equation is: $H^{(l+1)} = \sigma(AH^{(l)}W^{(l)})$,
• $H^{(l)}$ represents node embeddings at layer $l$.
• A is the graph's adjacency matrix.
• $W^{(l)}$ is a learnable weight matrix.
• $\sigma$ is a non-linear activation function.

Graph Convolutional Networks

• Graph Convolutional Networks (GCNs) use a spectral definition of convolution.
• A GCN layer equation is: $H^{(l+1)} = \sigma(\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}H^{(l)}W^{(l)})$.
• $\tilde{A} = A + I$ is the adjacency matrix with self-loops.
• $\tilde{D}$ is the degree matrix of $\tilde{A}$.

Graph Attention Networks

• Graph Attention Networks (GATs) use an attention mechanism to weight neighbors.
• Attention weights are learned based on node features.
• Allows the network to focus on the most relevant neighbors.

Heat Kernel Convolution

• Heat kernel $K_t$ solves the heat equation on the graph: $\frac{\partial K_t}{\partial t} = -\Delta K_t$.
• $\Delta = L = D - A$ is the graph Laplacian.
• $D$ is the degree matrix, $A$ is the adjacency matrix.
• Closed form solution: $K_t = e^{-t\Delta}$.

Heat Kernel Convolution Layer

• Heat kernel convolution equation: $H^{(l+1)} = \sigma(K_tH^{(l)}W^{(l)})$.
• $K_t$ is the heat kernel.
• $H^{(l)}$ represents node embeddings at layer $l$.
• $W^{(l)}$ is a learnable weight matrix.
• $\sigma$ is a non-linear activation function.

Parameterization

• The heat kernel $K_t$ is parameterized by the diffusion time $t$.

• $t$ can be a hyperparameter or learned.

• $t$ can be defined as $t = \sigma(\alpha)$, where $\alpha$ is a learnable parameter to bound $t$ between 0 and 1.

• The heat kernel convolution networks are evaluated on node classification and graph classification benchmarks.

• Compared against existing GNN models, including GCNs and GATs.

• GNNs based on heat kernel convolution are more effective than existing approaches.