TGNN: A Joint Semi-supervised Framework for Graph-level Classification

1 Introduction

A fundamental problem in data mining is graph classification, which seeks to capture the property of the entire graph. The problem has been extensively studied lately with a range of downstream applications, such as predicting the quantum mechanical properties [Lu et al., 2019; Hao et al., 2020] and assessing the functionality of chemical compounds [Kojima et al., 2020]. Among various graph classification algorithms [Ying et al., 2018; Xu et al., 2019], message-passing neural networks (MPNNs), as the majority of graph neural networks (GNNs) [Kipf and Welling, 2017; Veliˇckovi´c et al., 2017], have achieved tremendous success. The main idea behind MPNNs is to propagate and aggregate messages on a graph [Gilmer et al., 2017], where each node receives messages from all its neighbors, and then iteratively performs neighborhood aggregation and node updates. Finally, all node representations can be combined into a graphlevel representation. In this way, the semantic knowledge of local structures represented by different nodes can be implicitly integrated into the graph-level representation.

∗Equal contribution with an alphabetical order.

†Corresponding authors.

Although GNNs have achieved impressive performance, they do have one drawback that optimizing effective GNNs is data-hungry and frequently relies on a large number of labeled graphs, as the settings of current graph classification tasks show [Xu et al., 2019]. Nevertheless, it is often expensive and time-consuming to annotate labels such as in biochemistry and chemistry [Hao et al., 2020]. Although the labeled samples could be limited, massive unlabeled samples are simple to obtain, whose structures can often regularize the graph encoder to learn more discriminative representations for classification. This thus naturally inspires us to leverage both labeled and unlabeled data in semi-supervised scenarios to address the limitations of existing methods.

Recent efforts of combining MPNNs with semi-supervised learning techniques for graph classification [Li et al., 2019; Sun et al., 2020; Hao et al., 2020; Luo et al., 2022] are usually divided into two categories: self-training [Lee and others, 2013] or knowledge distillation [Hinton et al., 2014]. However, topology information is only implicitly incorporated when node features are messaging along edges, which fails to effectively explore graph topology. Moreover, as the number of labeled graphs is limited in semi-supervised graph classification, an approach that can better model graph topology and explore the unlabeled data for classification is anticipated in real-world applications.

To address the above issues, we propose a new framework named TGNN, which is capable of better exploring graph structures for semi-supervised graph-level classification. In contrast to existing MPNNs which utilize graph structures in an implicit way via message passing, our approach aims to capture graph topology in both implicit and explicit manners. On the one hand, we follow MPNNs and learn structured node representations through neighbor aggregation, and the summarized graph representation implicitly captures graph topology. On the other hand, we employ a graph kernel module, which compares each graph with parameterized hidden graphs via the random walk kernel. By this means, we get another graph representation, which leverages graph topology more explicitly. In order to couple the explicit and implicit information of graph topology, we propose a unified semi-supervised optimization framework with a novel selfsupervised consistency loss, where two modules are encouraged to yield consistent similarity scores when applied to each unlabeled graph. Extensive experiments on a wide range of well-known graph classification datasets demonstrate significant improvements over competing baselines. The contributions of this work can be summarized as follows:

• We provide a new semi-supervised graph classification approach called TGNN, which comprises a message passing module and a graph kernel module to explore structural information in both implicit and explicit ways.
• To integrate the topology information from complementary views, we propose an optimization framework including a self-supervised consistency loss to encourage exchanging similarity knowledge between two modules.
• Experimental results show our TGNN significantly outperforms the compared baselines by a large margin on a variety of benchmark datasets.

2 RelatedWork

Graph Neural Networks. GNNs have been extensively investigated due to their simplification from spectral methods [Spielman, 2007] to localized models [Kipf and Welling, 2017], which connects GNNs to message passing framework [Gilmer et al., 2017] and significantly promotes its efficiency. Most existing GNN methods for graph classification task [Hao et al., 2020; Ju et al., 2022] inherently use message passing neural networks (MPNNs) [Gilmer et al., 2017] to learn graph-level representation. However, MPNNs bear the drawback that they ignore structural properties explicitly emanating from graph topology. Furthermore, recent studies have shown the inability of MPNNs to model high-order substructures such as paths [Chen et al., 2020; Long et al., 2021]. With our TGNN, besides implicitly learning effective graph structural information from MPNNs, we also benefit from the graph kernel module to explicitly incorporate graph topology in a semi-supervised framework.

Semi-supervised Graph Classification. Semi-supervised learning has attracted increasing attention in the field of machine learning and data mining [Grandvalet and Bengio, 2005; Laine and Aila, 2017; Tarvainen and Valpola, 2017], whose basic idea is effectively leveraging a small number of labeled data and massive available unlabeled data to enhance the model performance. Recently much work has been done for semi-supervised graph classification [Li et al., 2019; Sun et al., 2020; Hao et al., 2020; Luo et al., 2022]. SEALAI [Li et al., 2019] and ASGN [Hao et al., 2020] use active learning techniques to select the most representative samples from unlabeled data, while InfoGraph [Sun et al., 2020] and DualGraph [Luo et al., 2022] fully explore the semantic information of unlabeled data via contrastive learning. Different from existing methods which only model graph topology in an implicit way, we also consider structural information in an explicit manner via graph kernels.

3 Methodology

This paper provides a novel framework TGNN for semisupervised graph classification as shown in Figure 1. At a high level, TGNN aims to capture graph topology in both implicit and explicit manners with twin GNN modules. On the one hand, we follow MPNNs to learn structured node representations via message passing, and thus the summarized graph representation reflects graph topology implicitly. On the other hand, we introduce a graph kernel module, which compares each unlabeled graph with hidden graphs via a random walk kernel to explicitly explore graph topology. To couple different topology information from twin GNNs, we present a novel semi-supervised optimization approach, in which twin modules are enforced to yield consistent similarity scores when applied to each unlabeled graph.

Problem Definition. Let G = (V, E) denote a graph, where V and E represent the node set and the edge set, respectively. In the task of semi-supervised graph classification, we are given a whole graph set G = {G L, G U }, which contains labeled graphs G L = {G1, · · · ,G|GL |} with their labels Y L = {y1, · · · , y|GL |} and unlabeled graphs G U = {G|GL |+1, · · · ,G|GL |+|GU |}. We aim to learn a label distribution p(Y U |G, Y L), which is able to predict the categories for unlabeled graphs G U .

3.1 Message PassingModule

Message passing neural networks (MPNNs) [Kipf and Welling, 2017; Gilmer et al., 2017; Veliˇckovi´c et al., 2017] have recently emerged as promising approaches to model graph-structured data, which implicitly encode graph structure into learned node representations h(k) v for each node v at the k-th layer. MPNNs typically use neighborhood aggregation to iteratively update the representation of a node by incorporating representations of its neighboring nodes in the previous layer. After k iterations, a node representation h(k) v is able to capture the structural information within its k-hop neighborhoods. Formally, the k-th layer of a node representation h(k) v obtained from the MPNN is formulated as:

Here N(v) represents the set neighbors of node v, COM(k) θ is a non-linear combination operations at layer k. Eventually, by using an attention mechanism, the graph-level representation will be generated by integrating all node representations at layer K as follows:

where t is a learnable vector, fθ (G) is the graph-level representation, and θ denotes the parameters of the message passing module. I(·) is an indicator equaling 1 when the condition is met, and its introduction is to adaptively prune some unimportant nodes for discriminative graph-level representations.

3.2 Graph Kernel Module

However, recent MPNNs simply capture structural information implicitly via message-passing along edges. It is usually difficult to explore rich high-order substructures (e.g., paths [Chen et al., 2020; Long et al., 2021]) in various MPNN models. It is therefore desirable to have a principled way of incorporating structural information explicitly.

To this end, we propose to use a random walk graph kernel to explicitly explore graph topology. Our graph kernel module introduces some hidden graphs which are parameterized using trainable adjacency matrices. Formally, our module contains N hidden graphs G′1 ,G′2 , · · · ,G′N with different sizes. We parametrize each hidden graph G′i as an undirected graph for fewer parameters. These hidden graphs are expected to learn structures that help distinguish between available classes. Inspired by the fact that the randomwalk kernels quantify the similarity of two graphs based on the number of common walks in the two graphs [Kashima et al., 2003; Nikolentzos and Vazirgiannis, 2020], we compare each graph sample against hidden graphs with a differentiable function from the random walk kernel.

Specifically, given two graphs G = (V,E) and G′ = (V ′ ,E′ ), their graph direct product G× = (V×,E×) is a graph where V× = {(v, v′ ) : v ∈ V ∧ v′ ∈ V ′ } and E× = {{(v, v′ ) , (u, u′ )} : {v, u} ∈ E ∧ {v′ , u′ } ∈ E′ }. It could be observed that a random walk on G× can be interpreted as a simultaneous walk on graphs G and G′ [Vishwanathan et al., 2010]. Considering traditional random walk kernels count all pairs of matching walks on G and G′ , the number of matching walks is equivalent to the adjacency matrix A× of G× if traversing over nodes of G and G′ at random. The P-step (P ∈ N) random walk kernel between G and G′ that counts all simultaneous randomwalks is thus defined as:

where e is an all-one vector, and ω0, . . . , ωP are positive weights. To simplify the calculation, we only compute the number of common walks of length exactly p over two compared graphs:

Then, given P = {0, . . . , P} and hidden graph set Gh = {G′1 , . . . , G′N }, we can build a matrix H ∈ RN×(P+1) where Hij = k(j-1) (G,G′i ) for each input graph G. Finally, the matrix H is flattened and fed into a fully-connected layer to produce the graph-level representation denoted as gφ(G).

3.3 Semi-supervised Optimization Framework

In this subsection, we discuss how to integrate the twin modules to explore graph structural information from complementary views in semi-supervised scenarios.

To produce generalized and robust representations for two modules, we first involve four fundamental data augmentation strategies to create positive views of graphs that preserve intrinsic structural and attribute information: (1) Edge dropping (2) Node dropping (3) Attribute masking (4) Subgraph. For more details of these strategies, refer to [You et al., 2020]. We generate augmented graphs by randomly selecting one of the defined augmentation strategies. Specifically, given an instance Gj , for two modules, two stochastic augmentations T 1 and T 2 sampled from their corresponding augmentation families are applied to Gj, resulting in two correlated samples denoted as G1j = T 1 (Gj) and G2j = T 2 (Gj). Afterward, G1j and G2j are fed into two modules respectively to obtain the embedding pair (zj = fθ(G1j ), wj = gφ(G2j )).

Since two modules mine semantic information from GNNs and graph kernels respectively, the semantic representations derived from their respective representation spaces might exist a discrepancy. Moreover, since the label annotations are usually limited in a semi-supervised case, predicted pseudo labels are usually unreliable and biased. As such, simply aligning the graph-level representations or pseudo labels of the same instance may be sub-optimal, especially for unlabeled samples. To alleviate the issue, we propose to enhance each instance by exchanging instance knowledge via comparing its similarities to other labeled samples in embedding spaces of two modules.

Specifically, we first randomly select a set of the labeled data {Ga1 , . . . ,GaM } as anchor samples that are stored in a memory bank and then embed them using both message passing module and graph kernel module to get their representations {zam }Mm=1 and {wam }Mm=1 . Note that we need a large set of anchor samples so that they have large variations to cover the neighborhood of any unlabeled sample. However, it is computationally expensive to process many samples in a single iteration due to limited computation and memory. To tackle this issue, we maintain a memory bank as a queue defined on the fly by a set of anchor samples from several most recent iterations for our twin GNNmodules.

In detail, given an unlabeled graph Gj, we get its embeddings zj = fθ(T 1 (Gj)) via the message passing module, and then we calculate the pairwise similarity between zj and all anchor embeddings {zam }Mm=1 . Similarly, the pairwise similarity for the graph kernel module can be obtained through comparison between wj = gφ(T 2 (Gj)) and {wam }Mm=1 . In our implementation, we use exponential temperature-scaled cosine similarity to measure the relationship in both embedding spaces. Formally, the similarity distribution between the unlabeled sample and anchor samples in the message passing module's embedding space is:

where τ is the temperature parameter set to 0.5 following [You et al., 2020] and cos(a, b) = a·b ‖a‖2 ‖b‖2 is the cosine similarity. In the same way, the similarity in the embedding space of the graph kernel module is written as:

For each unlabeled graph Gj, we encourage the consistency between probability distributions pj = [pj1 , . . . , pjM ] and qj = [qj1 , . . . , qjM ] by using Kullback-Leibler (KL) Divergence as the measure of disagreement. In formulation, we present a consistency loss defined as follows:

Algorithm 1 TGNN's main learning algorithm

Input: Labeled data G L, unlabeled data G U

Parameter: Message passing module parameter θ, graph kernel module parameter φ, classifier parameter η

Output: classifier Φ(y|G)

• 1: Sample M examples from G L to construct anchor set as the memory bank.
• 2: Initialize parameters {θ, φ, η}.
• 3: while not convergence do
• 4: Sample minibatch BL and BU .
• 5: Forward propagation BL and BU via twin modules.
• 6: Compute objective function using Eq. (10).
• 7: Update the parameters by back propagation.
• 8: Update the memory bank with BL for two modules following a first-in, first-out manner.
• 9: end while

In order to output label distribution for classification, we use the graph-level representation from the message passing module to predict the label through a multi-layer perception (MLP) classifier Hη(·) (i.e., Φ(y | G) = Hη(fθ(G)). We choose the message passing module since a single MPNN outperforms a single graph kernel network empirically by validation study. Therefore, we use the cross-entropy function to characterize the supervised classification loss:

Finally, we combine the supervised classification loss Lsup with unsupervised consistency loss Lcon in the overall loss:

The overall framework is illustrated in Algorithm 1.

4 Experiments

4.1 Experimental Setups

Benchmark Datasets. We evaluate our proposed TGNN using seven publicly accessible datasets (i.e., PROTEINS, DD, IMDB-B, IMDB-M, REDDIT-B, REDDIT-M-5k and COLLAB [Yanardag and Vishwanathan, 2015]) and two largescale OGB datasets (i.e., OGB-HIV, OGB-MUV). Following DualGraph [Luo et al., 2022], we adopt the same data split, in which the ratio of labeled training set, unlabeled training set, validation set and test set is 2:5:1:2.

Competing Models. We carry out comprehensive comparisons with methods from three categories: classical graph approaches (i.e., WL [Shervashidze et al., 2011], Sub2Vec [Adhikari et al., 2018] and Graph2Vec [Narayanan et al., 2017]), classical semi-supervised learning approaches (i.e., EntMin [Grandvalet and Bengio, 2005], Mean-Teacher [Tarvainen and Valpola, 2017] and VAT [Miyato et al., 2018]) and graph-specific semi-supervised learning approaches (i.e., InfoGraph [Sun et al., 2020], ASGN [Hao et al., 2020], GraphCL [You et al., 2020], JOAO [You et al., 2021]), and DualGraph [Luo et al., 2022].

Implementation Details. All methods are implemented in PyTorch, and the experiments are presented with the average prediction accuracy (in %) and standard deviation of five times. For the proposed TGNN, we empirically set the embedding dimension to 64, the number of epochs to 300, and batch size to 64. We modify GIN [Xu et al., 2019] to parameterize the message passing module fθ, consisting of three convolution layers and one pooling layer with an attention mechanism. For our graph kernel module gφ, we empirically set the number of hidden graphs to 16 and their size equal to 5 nodes. The maximum length of random walk P is set to 3. Finally, we use Adam to optimize all the models.

4.2 Results and Analysis

Table 1 shows the results of semi-supervised graph classification using half of the labeled data. We can get the following observations: (1) The majority of the classical graph approaches achieve worse performance than others, indicating that GNNs have a high representation capability to extract effective information from graph data. (2) The approaches with classical semi-supervised learning techniques show worse performance compared with the graphspecific semi-supervised learning approaches, demonstrating that models specifically designed for graphs can better learn the characteristics of graphs in semi-supervised scenarios. (3) Our framework TGNN outperforms all other baselines on six of seven datasets, soundly justifying the superiority of our framework. Moreover, we assess our model on large-scale OGB datasets and the results on Table 2 further validate the effectiveness of TGNN.

Influence of Labeling Ratio. We vary the labeling ratio of training data on PROTEINS and DD in Figure 2. From the results, we can clearly see that the performance of all models generally improves as the number of available labeled data increases, demonstrating that adding more labeled data is an efficient way to boost the performance. Among these methods, TGNN achieves the best results, showing that sufficiently integrating graph topology information from complementary views can indeed benefit the performance.

4.3 Ablation Study

We investigate a few variants to demonstrate the effect of every part of our model: (1) MP-Sup trains an MPNN (i.e., fθ) solely on labeled in a supervised manner. (2) GK-Sup trains a graph kernel neural network (i.e., gφ) solely on labeled data. (3) MP-Ensemble replaces the graph kernel module with another message passing module with different initialization. (4) GK-Ensemble replaces the message passing module with another graph kernel module with different initialization. (5) TGNN w/o Aug. removes the graph augmentation strategy before feeding graphs into the twin modules.

We present the results of different model variants in Table 3. First, we can clearly observe that on most datasets, PROTEINS IMDB-B REDDIT-B

63.3±1.4 63.4±2.1 69.8±1.1

62.6±0.8 55.4±1.7 65.3±0.6

MP-Ensemble 68.1±1.5 69.8±1.2 73.7±1.1

GK-Ensemble 66.9±1.7 60.5±1.8 70.8±0.8

TGNNw/o Aug 69.3±0.8 71.7±1.3 75.8±0.7

TGNN (Ours) 71.0 ± 0.7 72.8 ± 1.7 76.3 ± 1.3

COLLAB

PROTEINS

2

3

4

5

6

Maximum Length of Random Walk

Figure 3: Hyper-parameter sensitivity study of TGNN.

MP-Sup outperforms GK-Sup. Maybe the reason is that the message passing module can utilize node attributes while the graph kernel module fails. Second, MP-Ensemble (GK-Ensemble) outperforms MP-Sup (GK-Sup), indicating our consistency learning framework can improve the model through ensemble learning. Third, our full model beats both two ensemble models, indicating the superiority of exploring similarity from complementary views. Finally, with the graph augmentation, our full model achieves better performance, showing that graph augmentation can produce generalized graph representations beneficial to graph classification.

4.4 Hyper-parameter Study

We further examine the hyper-parameter sensitivity of our TGNN w.r.t. different embedding dimensions of hidden layers d and the maximum length of random walk P as shown

in Figure 3. We first vary d in {8, 16, 32, 64, 128} with all other hyper-parameters fixed. It is clear that the performance saturates as the embedding dimensions reach around 64. This is because a larger dimensionality brings a stronger representation ability at the early stage, but might lead to overfitting as the continuously increasing of d. We further vary P in {1, 2, 3, 4, 5, 6} while fixing all other hyper-parameters. We observe that the performance tends to first increase and then decrease. A too-small P would lead to limited topological exploration space while a large P may introduce instability and fail to distinguish graph similarity.

4.5 Case Study

We investigate the power of our graph kernel module to show the superiority of explicitly exploring topology information. First, we show two cases on REDDIT-M-5k in Figure 4, where two unlabeled examples are annotated with both the message passing module and graph kernel module. We can find that both samples are classified into wrong categories by fθ, while gφ revises the wrong prediction successfully, which

0.579

0.069

0.001

0.013

0.001 0.001

0.025

Figure 4: Visualize the power of graph kernel on REDDIT-M-5k.

demonstrates that our graph kernel module is an important supplement for graph classification. The potential reason is that the graph kernel module is able to capture clearer topology information embedded in graph substructures. Furthermore, we visualize several hidden graphs derived from the graph kernel module on PROTEINS. From Figure 5, we can clearly see that our module is able to generate various kinds of graph substructures, so as to effectively capture the rich topological information in the dataset.

5 Conclusion

This paper presents a Twin Graph Neural Network (TGNN), a joint optimization framework that combines the advantages of graph neural networks and graph kernels. TGNN consists of twin modules named message passing module and graph kernel module, which explore graph topology information from complementary views. Furthermore, a semi-supervised framework is proposed to encourage the consistency between two similarity distributions in different embedding spaces. Extensive empirical studies show that our approach outperforms competitive baselines by a large margin.

Acknowledgments

This paper is partially supported by National Key Research and Development Program of China with Grant No. 2018AAA0101902 as well as the National Natural Science Foundation of China (NSFC Grant No. 62106008 and No. 62006004).

0.338

0.677

0.296