KGNN: Harnessing Kernel-based Networks
for Semi-supervised Graph Classification

Our work is related to graph neural networks (GNNs), which are able to learn useful graph representations via supervised learning. Most existing methods (Xu et al., 2019; Ying et al., 2018; Lee et al., 2019; Khasahmadi et al., 2020) inherently use a message-passing neural network (Gilmer et al., 2017) to learn node representations, and then aggregate them as graph representations. Because of their effectiveness in learning graph representations, they achieve state-of-the-art results. However, graph representations derived from GNNs often fail to effectively leverage graph similarity for prediction. Besides, these methods rely on a large number of labeled data for training. With KGNN, besides learning effective graph representations derived from GNNs, we also benefit from graph kernels to explicitly incorporate graph similarity in a semi-supervised framework.

Kernels on graphs are originally introduced by (Gärtner et al., 2003; Kashima et al., 2003), and the basic idea is to decompose graphs into atomic substructures and use kernel functions to capture the graph similarity, which can be used in kernel methods for graph classification. Many early methods(Gärtner et al., 2003; Kashima et al., 2003) define feature vectors as counts of label paths using a random walk or shortest path. However, these methods cannot be scaled to large graphs and suffer from high computational complexity. To alleviate these weaknesses, many later graph kernels are designed based on limited-sized substructures  (Shervashidze et al., 2009) or neighborhood aggregation (Shervashidze et al., 2011). Some recent studies also try to combine graph kernels and graph neural networks (Du et al., 2019; Chen et al., 2020). GCKNs (Chen et al., 2020) connect two methods via multilayer graph kernels. GNTKs (Du et al., 2019) prove that their kernels are equivalent to infinitely wide GNNs trained by gradient descent. Similar to these methods, our proposed KGNN also combines the advantages of both worlds but from different views. To be specific, our approach not only imposes graph kernels as structured constraints to guide the training process of GNNs, but also uses unlabeled data to assist model training by maximizing the agreement of the two networks on unlabeled data, while their works can only leverage labeled data in a supervised way.

Another category of related work is semi-supervised learning. The self-training method is one of the earliest ideas along this line. It requires a trained classifier to periodically predict class labels of the unlabeled data and add high-quality classified samples to the training set. For example, the entropy minimization method (Grandvalet and Bengio, 2005) requires the classifier to output low-entropy predictions on unlabeled data. Another line of research focuses on perturbation-based approaches. The core idea is to encourage the mapping consistency between the input and output when noise is applied to the input, which is so-called consistency regularization. Among them, the temporal ensembling model (Laine and Aila, 2017) maintains an exponential moving average of label predictions while the mean teacher model (Tarvainen and Valpola, 2017) averages network parameters to obtain a stable target output.

Besides, there are also some recent studies (Li et al., 2019; Sun et al., 2020; Hao et al., 2020) proposed for semi-supervised graph classification. SEAL-AI (Li et al., 2019) approaches the problem in the perspective of the hierarchical graph related to self-training. InfoGraph (Sun et al., 2020) and ASGN (Hao et al., 2020) learn graph representations via contrastive learning and active learning respectively, which both can be boiled down to the teacher-student framework. Compared with existing works, our work focuses on combining the advantages of graph neural networks and graph kernels via posterior regularization, incorporating graph similarity from implicit and explicit perspectives respectively, while their works fail to enhance GNNs from the view of topological similarity.

Given two graphs $G_{i}$ and $G_{j}$, the graph kernel $K(G_{i},G_{j})$ measures the similarity between them and is defined as:

where the base kernel $k_{base}$, i.e., the inner product on Hilbert space, compares substructures centered at nodes $v_{i}$ and $v_{j}$, and $f_{G}(v)$ is the feature vector counting the number of appearances of each substructure (e.g., subtrees, paths, graphlets) in the graph $G$.

Afterward, the matrix of pairwise similarities among graphs defined by graph kernels can be passed to kernel-based methods such as the Support Vector Machine to perform graph classification.

Posterior regularization (PR) (Ganchev et al., 2010) is a principled framework to impose constraints from the desired distribution $q(\mathbf{y})$ on probabilistic models $p_{\theta}\left(\mathbf{y}|\mathbf{x}\right)$ as follows:

where $\mathcal{L}(\bm{\theta})$ is the log-likelihood of model $p_{\theta}\left(\mathbf{y}|\mathbf{x}\right)$, and $Q$ is a constraint set, with respect to the expectations of constraint features $\psi(\mathbf{x},\mathbf{y})$ that are bounded by $\mathbf{b}$:

To optimize the posterior regularized likelihood $\mathcal{L}(q;\bm{\theta})$, PR presents an iterative procedure akin to an EM-style algorithm:

For better interpretation, it can be viewed as performing coordinate ascent on $\mathcal{L}(q;\bm{\theta})$. Starting from an initial parameter estimate $\theta^{0}$, the algorithm iterates two block-coordinate ascent steps until a convergence criterion is reached.

In this paper, we introduce our approach for semi-supervised graph classification by incorporating both labeled and unlabeled data. Existing methods typically combine graph neural networks with semi-supervised learning techniques. However, these methods are not able to fully leverage graph similarity information for classification, which leads to insufficient expressiveness. Also, their performance is not yet satisfactory when the labeled data are limited.

We address the above limitations by proposing the Kernel-based Graph Neural Network (KGNN), which combines methods based on graph kernels and graph neural networks. The idea is to use graph kernels as structured constraints to guide the training of graph neural networks via posterior regularization, allowing the graph neural network to explicitly exploit graph similarity and receive additional supervision to boost performance. In particular, there are a kernel-based network and a GNN-based network in a KGNN, and we use an EM-style algorithm to jointly train both networks. In the E-step, the kernel-based network represented as a memory network is updated by projecting the GNN-based network to a subspace constrained by the graph similarity. In the M-step, the GNN-based network is improved by distilling the knowledge from the kernel-based network. In this way, both networks can effectively mutually enhance each other. An illustration of the framework is presented in Figure 2. Next, we first introduce the GNN-based network and the kernel-based network. Finally, the training algorithm is explained.

Due to the appealing representation learning ability, graph neural networks have been widely used in graph classification tasks. For example, InfoGraph (Sun et al., 2020) first learns node representations with GIN (Xu et al., 2019), and then summarizes the node representations into the graph-level representation, which serves as graph features for the classification task. Note that in InfoGraph (Sun et al., 2020), the label dependency between different graphs is ignored. We follow the same idea and factorize the joint label distribution as:

Furthermore, to learn graph-level representation for a graph $G=(V,E,\mathbf{X})$, GNN-based methods solely rely on the node attributes $\mathbf{X}$ and graph structure $E$. In other words, it is independent of other graphs, we therefore define the conditional probability of label $\mathbf{y}^{g}$ for graph $G$ as follows:

To predict the graph label $\mathbf{y}^{g}$, a graph neural network first learns node representations by aggregating and updating messages from its neighborhoods. Based on the node representations, a READOUT function summarizes them into the whole graph representation. This procedure can be formalized in the following way:

where $\mathbf{h}_{v}^{(l)}$ is the feature vector of node $v$ at the $l$-th layer. $\mathbf{h}_{v}^{(0)}$ is often initialized as node features (i.e., $\mathbf{X}_{v}$) and $\mathcal{N}(v)$ are neighborhoods to node $v$. The message-passing phase runs for $L$ steps and is defined in terms of aggregation functions $A_{\theta}^{(l)}(\cdot)$ and node updating functions $U_{\theta}^{(l)}(\cdot)$, which have a series of possible implementations (Kipf and Welling, 2017; Hamilton et al., 2017; Veličković et al., 2017). After a permutation invariant function $\text{READOUT}(\cdot)$ such as some pooling functions (Ying et al., 2018; Lee et al., 2019; Khasahmadi et al., 2020), the final graph-level representation $H(G)$ is fed into an $\text{MLP}_{\theta}$ (Multi-Layer Perceptron) classifier for classification. In this paper, we follow InfoGraph (Sun et al., 2020) and use GIN (Xu et al., 2019) to learn node representations for its high expressive power, and then use the sum operation to produce the graph-level representations (i.e., the READOUT function).

Graph neural networks can effectively utilize node attributes and graph local structures under the message-passing framework, however, they are insufficient in capturing more global graph topology and ignore the relations between different graphs. This motivates us to additionally incorporate graph kernels, which have been proven useful for encoding graph topology and similarity information (Kriege et al., 2020).

Traditional kernel-based methods perform graph classification tasks in a two-step approach that similarity features are separated from the training phase and are not optimized for downstream tasks, hence the performance is usually unsatisfactory. To address the above limitation, we propose a kernel-based network $q(\mathbf{y}^{U}|\mathcal{G},\mathbf{y}^{L})$ and implement it with a memory network, which shares a similar idea to classical kernel-based methods(Nowicki and Siegelmann, 2010), but haves larger model capacity and can be optimized in an end-to-end manner. Moreover, memory networks can be naturally and effectively coupled with kernel tricks (García and Moreno, 2004) and introduced to further compare graph-graph similarity via graph kernels for prediction.

In detail, with the assumption of label dependency in Eq. 6, we model the conditional probability $q(\mathbf{y}^{g}|\mathcal{G},\mathbf{y}^{L})$ as follows

where the memories of $\text{MemNN}_{\phi}$ consists of the labeled data set $\mathcal{G}^{L}$ represented as the feature vector set $\{z_{1},\cdots,z_{\left|\mathcal{G}^{L}\right|}\}$ derived from graph kernels (see. Sec. 3.2). Then each graph are converted into memory vectors by a set of trainable embedding matrix set $A_{\phi}=\{A_{\phi}^{1},\dots,A_{\phi}^{K+1}\}$, where each $A_{\phi}^{k}$ maps memory content into continuous space at each layer $k$. The query graph (one of the labeled data) is also encoded via another trainable embedding matrix $B_{\phi}$ to obtain a hidden representation $q^{k}$ as a reading head. Afterward, we measure the similarity between $q^{k}$ and each memory vector $A_{\phi}^{k}(z_{i})$ by inner product, corresponding to the graph kernel computed on Hilbert space $\mathcal{H}$ and then followed by a softmax function. The model loops over $K$ hops and it computes the attention weights at hop $k$ for each memory $G_{i}$ using:

where $\text{Softmax}(x_{i})=e^{x_{i}}/\Sigma_{j}{e^{x_{j}}}$. Here, $p^{k}$ is a soft memory selector that decides the memory relevance with respect to $q^{k}$. Then, the model reads out the memory $o^{k}$ by the weighted sum over $A_{\phi}^{k+1}$ ¹¹1Here is $A_{\phi}^{k+1}$ since we use adjacent weighted tying (Sukhbaatar et al., 2015).,

Then, the query vector is updated for the next hop by using $q^{k+1}=q^{k}+o^{k}$. The above step leads to the final graph representation $o^{K}$, which will be fed into an $\text{MLP}_{\phi}$ classifier for prediction as follows:

In this way, the representation of graphs can be combined with similarity features of multiple graphs from memories, and the multi-hop attention mechanism helps in learning correlations between memories. Thus, the derived kernel-based network enables high flexibility and is able to effectively exploit graph topology similarity. An illustration of the kernel-based network is presented in Figure 3.

Graph kernels offer effective prior knowledge to explicitly capture graph similarity. To inject this knowledge into graph neural networks efficiently, posterior regularization (PR) is utilized to provide a principled way to impose structured constraints on the posterior distribution of the probabilistic models. However, PR typically uses a fully-specified constraint (see Eq. (3)), which is often sub-optimal. To address this limitation, we represent the desired distribution $q(\mathbf{y})$ in (2) as the kernel-based network described in Section 4.3, where this manipulation leads to a more efficient and flexible training algorithm. For simplicity, the GNN-based network and the kernel-based network will be simply written $p_{\theta}(\mathbf{y}|\mathbf{x})$ and $q_{\phi}(\mathbf{y}|\mathbf{x})$ respectively with an abuse of notation in the rest of the paper.

Based on this, the kernel-based network enables learnable constraints and should be a good complement for the GNN-based network to incorporate the topology information. To this end, we formulate the training objective as:

Note that another benefit of modeling the kernel-based network as the memory network is the differentiability of our training objective Eq. (13). It is easy to use stochastic gradient descent algorithms to optimize model parameters. Next, we will give the specific training algorithm for updating parameters in Section 4.5.

In the training phase, our goal is to maximize the posterior regularized likelihood (13) that can be optimized by an iterative procedure akin to an EM-style algorithm, alternated by an E-step and an M-step. In the E-step, the goal is to optimize the kernel-based network by minimizing the KL divergence between the kernel-based network and the GNN-based network. In the M-step, we optimize the GNN-based network by the original likelihood of model $p_{\theta}\left(\mathbf{y}|\mathbf{x}\right)$ and additional guidance derived from the kernel-based network. Next, we introduce the details of the E-step and M-step.

Besides, we notice that $q_{\phi}$ is a standard discriminative classifier and can be also trained with labeled data. Therefore, we optimize $q_{\phi}$ by maximizing the following objective function:

We summarize the detailed optimization algorithm for KGNN in Algorithm. 1. The model alternates between optimizing the objective function with regard to $\phi$ and $\theta$, which is referred to as E-step and M-step. During each step, both labeled and unlabeled data are leveraged for training. In addition to training two networks with labeled data, we essentially select samples with high confidence from the unlabeled data for regularization to let both networks mutually enhance each other. Specifically, given the unlabeled data $\mathbf{x}$ and their predicted categories $\mathbf{y}$, we rank these data according to the probability of distribution $\mathbf{y}$ (i.e., $q_{\phi}(\mathbf{y}|\mathbf{x})$ and $p_{\theta}(\mathbf{y}|\mathbf{x})$) and then select top-$k$ data from the corresponding ranked list. This is similar to the way we do in self-training methods (Lee et al., 2013). Furthermore, to eliminate the influence of incorrect annotations in selected samples, we collect the intersection of the training samples predicted via both networks and regard them as the additional labeled set to enlarge the labeled data, experimental analysis in the next section shows that consistent prediction data are helpful for improving the final performance. The whole iterative procedure stops until convergence or the unlabeled data are exhausted.

We report the quantitative results of semi-supervised graph classification with half of the labeled data TRAIN-L in Table 2. From this table, we make the following observations. (1) We can observe that most of the traditional graph methods perform worse than other methods, which shows that graph neural networks possess the strong representation-learning ability to extract more useful information from graph-structured data. (2) The methods with traditional semi-supervised learning techniques (EntMin, $\Pi$-Model, Mean-Teacher and VAT) show worse performance compared with the graph-specific semi-supervised learning approaches, indicating that recent graph semi-supervised learning techniques are more suitable for the challenging graph classification task. (3) Among the previous state-of-the-art approaches, GraphCL achieves almost the best performance on most datasets. Specifically, other graph-specific semi-supervised learning approaches are not as effective as GraphCL, maybe the reason is that GraphCL takes advantage of the idea of instance discrimination for contrastive learning and specific graph augmentation strategies, and thus further improve the performance. (4) Our framework KGNN achieves the best performance on six of seven datasets, which demonstrates the effectiveness of our framework. From the results, we attribute the performance gain to two aspects: (i) Introduction of graph kernels. Graph kernels acting as structured constraints are able to guide the training process of graph neural networks. (ii) Introduction of posterior regularization framework. Instead of simply integrating the graph neural networks and graph kernels, we use a principled way to combine both worlds, which can mutually enhance each other.

In the KGNN model, either the GNN-based network or the kernel-based network is enhanced by incorporating extra “labels” selected from both networks. A more straightforward way could be empowering every single network with “labels” generated by itself, which is known as the self-training method. Next, we investigate a few variants that are trained under the self-training framework:

• •

  GNN-Sup. Our base model, which trains a GNN (i.e., $p_{\theta}$ network) solely on labeled data TRAIN-L in a fully supervised manner.

• •

  MemNN-Sup. It is another model, which optimizes a MemNN (i.e., $q_{\phi}$ network) solely on labeled data in a supervised way.

• •

  GNN-Self. It is a model variant where we optimize a GNN (i.e., $p_{\theta}$) using a self-training strategy.

• •

  Ensemble-Self. Besides using a single network, we first ensemble the GNN-based network $p_{\theta}$ and the kernel-based network $q_{\phi}$ by concatenating their graph representations before the final prediction layer, and train the ensembled model with self-training.

• •

  KGNN-Sep. KGNN-Sep differs from the original KGNN in that we directly feed the label annotations by one network into the other network without checking the prediction consistency.

Finally, we examine the KGNN’s performance varies w.r.t. different parameter settings. Specifically, we investigate the effect of embedding dimensions of hidden layers and the number of hops in the memory network on two datasets PROTEINS and COLLAB.

In this section, we study the power of the kernel-based network to validate the strength of our framework, showing the superiority from the view of topological similarity. Figure 7 illustrates some of the results we obtained on REDDIT-M-5k, where two unlabeled samples are annotated with both GNN-based network $p_{\theta}$ and kernel-based network $q_{\phi}$. We observe that both samples are classified into wrong categories by $p_{\theta}$ while $q_{\phi}$ corrects the wrong prediction successfully, which shows that our novel kernel-based network is a necessary supplement for the effective graph classification task. The reason may be that the kernel-based network is able to capture more relationships between different substructures and thus acts as structured constraints to guide the GNN-based network.