State of the Art and Potentialities of Graph-level Learning

GKs perform graph-level learning based on kernel values (i.e., pair-wise graph similarities). Given a graph dataset \(\mathbb {G}\), GKs decompose each graph \(\mathcal {G}\) into a bag-of-graphs \(S^{\mathcal {G}}=\lbrace g_1,\ldots ,g_I\rbrace\), where \(g_i\subseteq \mathcal {G}\) and \(g_i\) can be a node or a subgraph. Most GKs are based on the paradigm of an \(R\)-Convolution kernel [26] that obtains the kernel value \(K_{R-conv} \left(\mathcal {G},\mathcal {G}^{\prime }\right)\) of two graphs \(\mathcal {G}\) and \(\mathcal {G}^{\prime }\) by:where \(K_{parts}(g_i,g^{\prime }_j)\) is the kernel function that defines how to measure the similarity between \(g_i\) and \(g^{\prime }_j\), and \(I\) and \(J\) count the size of bag-of-graphs for decomposing \(\mathcal {G}\) and \(\mathcal {G}^{\prime }\), respectively. A kernel matrix that packages all kernel values is then fed into an off-the-shelf machine learning model, such as a support vector machine (SVM), to classify the graphs.

Subgraph mining is similar to SGKs, where the vector \(\textbf {x}_i = [x_i^1,\ldots ,x_i^M]^\top\) is taken as a graph-level representation of the graph \(\mathcal {G}_i\). Here, \(x_i^m\in \lbrace 0,1\rbrace\), \(x_i^m=1\) if \(g_m \subseteq \mathcal {G}_i\), otherwise, \(x_i^m=0\). The established graph-level representation is then directly input into an off-the-shelf machine learning model, such as SVM classifier, for downstream tasks. What is different about subgraph mining algorithms is that they place particular emphasis on how to extract the optimal subgraph set \(\mathcal {S}^* = \lbrace g_1,...g_T\rbrace\) from the subgraph set \(\lbrace g_1,...g_M\rbrace\), where \(g_1,\ldots ,g_M\) denote all possible subgraphs of \(\mathbb {G} =\lbrace \mathcal {G}_1,\ldots ,\mathcal {G}_N\rbrace\). Techniques for extracting subgraphs can be divided into two branches, depending on how the supervision information is used. Frequent subgraph mining is the unsupervised method, as illustrated in Figure 4(a), while discriminative subgraph mining is the supervised or semi-supervised method (see Figure 4(b)).

Graph embeddings are the compression of graphs into a set of lower-dimensional vectors. Some non-learnable graph embedding methods extract graph-level representations from the inherent properties of graphs, e.g., their topologies and eigenspectrums.

Local Degree Profile (LDP) [53] summarizes the degree information of each node and its 1-hop neighbors as node features. LDP constructs graph representations by building an empirical distribution or histogram of the hand-crafted node features. In addition to node degree, non-learnable graph embedding can also leverage anonymous random walk sequences to describe a graph’s topological information. Specifically, anonymous random walks record the status change of node labels. Two anonymous random walk sequences \(A \rightarrow B \rightarrow A\) and \(B \rightarrow A \rightarrow B\) can be both written as \(1 \rightarrow 2 \rightarrow 1\). Anonymous Walk Embeddings (AWE) [52] encode a graph via an \(n\)-dimensional vector in which each element represents the occurrence frequency of a specific anonymous random walk sequence.

In spectral graph theory [61], the spectrum of a graph is determined by its topology. Based on this theory, the Family of Graph Spectral Distances (FGSD) method [51] proposes that the distance between the spectrums of two graphs can be used to test whether the graphs are isomorphic. Thus, the histogram of the spectrum is used to construct a graph-level representation. Analogously, A-DOGE [56] depicts a graph by computing the spectral density across its eigenspectrum. However, these methods are limited to use with small graphs given the prohibitive costs of computing eigenspectrum decompositions with large-scale graphs. As a possible solution to this limitation, SlaQ [54] uses stochastic approximations as a way of quickly calculating the distance between two graphs’ spectral densities. More specifically, these works employ Von Neumann Graph Entropy (VNGE) [62, 63] as a way of approximately representing the spectral properties of the graphs. In turn, this approximation supports fast computation by tracing a Laplacian matrix of the graph. Another VNGE-based method [55] derives the error bound of the approximation estimation for VNGE.

Skip-gram [80] is a widely used unsupervised neural network model that predicts context words given a target word. Initially, the researchers built a skip-gram model based on the relationship between two adjacent subgraphs, namely, subgraph2vec [64]. Subgraph2vec first takes the (\(d\)-1)-, \(d\)-, (\(d\)+1)-hop neighborhoods of the \(v\)th selected node in the graph \(\mathcal {G}_i\) as three subgraphs \(g^i_{v-1}\), \(g^i_{v}\), \(g^i_{v+1}\), respectively, where \(d\ge 1\) is a predefined value. \(\lbrace \mathbf {w}^1_{1-1},\ldots ,\mathbf {w}^1_{V+1};...;\mathbf {w}^N_{1-1},\ldots ,\mathbf {w}^N_{V+1}\rbrace\) are the randomly initialized embeddings of all sampled subgraphs \(\lbrace g^1_{1-1},\ldots ,g^1_{V+1};...; g^N_{1-1},\ldots ,g^N_{V+1}\rbrace\), respectively, where \(N\) represents the total number of graphs, and \(V\) is the number of selected nodes in each graph. Then, the Skip-gram model is used to update the subgraph embeddings. The Skip-gram model takes \(\mathbf {w}^i_{v}\) as its input and predicts the context of \(\mathbf {w}^i_{v}\) (i.e., \(\mathbf {w}^i_{v-1}\) and \(\mathbf {w}^i_{v+1}\)). Then, the prediction results are back-propagated to update \(\mathbf {w}^i_{v}\). To summarize, subgraph2vec’s learning objective is to maximize the following probability \(\operatorname{Pr}\):

Another method, Graph2vec [65], was designed to tackle graph representation tasks. By establishing semantic associations between a graph and its sampled subgraphs, Graph2vec employs the idea of Skip-gram to learn graph embeddings. Following this work, Dang et al. [66] replaced the sampled subgraphs in Graph2vec with frequent subgraphs that have more discriminative features for graph classification tasks.

RNNs are particularly good at learning sequential data, such as text [81] and speech [82]. Two main types of algorithms apply RNNs to graph-level learning. One type transforms graphs into sequential-structured data. The other aggregates neighborhood information about the target node and relabels those aggregated features through an RNN. This is similar to Message Passing Kernels (MPKs, Section 4.1.1).

A natural way to capture the sequential information in graphs is to use a series of random walk paths to represent a graph. For example, GAM [68] employs a long short-term memory (LSTM) model to guide a random walk on graphs. Meanwhile, the LSTM model generates a representation for the walk sequence to describe the graph. In addition, Zhao et al. [69] proposed an RNN-based graph classification algorithm called SAN. Starting from a node, SAN employs an RNN model that adds nodes and edges to form an informative substructure whose representation is progressively generated by the RNN model. A graph-level representation that can be used for graph classification tasks is then generated by summing all the representations of the formed substructures. Given a graph generation task, NetGAN [7] uses an LSTM model as a generator to yield fake walk sequences, while a discriminator disambiguates the graph’s real walk sequences from the generated fake ones to reverse-train the generator. Another graph generation model, GraphRNN [8], creates various permutations of graphs, with various combinations of nodes and edges as sequential data for RNNs.

The second category of RNN-based GL-DNNs implements neural network versions of MPKs through RNN models. For instance, Scarselli et al. [83] recurrently updated node embeddings until reaching a stable situation, that is:where \(h_u^{0}\) is randomly initialized and \(f_{w}(\cdot)\) is a parametric function that maps vectors into a concentrated space to shorten their distance. To address the graph-level task, a super node connected with all the other nodes is used to output the representation of the whole graph. In addition, Li et al. [67] proposed the idea of using a gated recurrent unit (GRU) to relabel the aggregated information from the 1-hop neighborhoods of the center node. This approach reduces the recurrent process for updating node embeddings to a fixed number of steps and avoids control convergence parameters, formulated as:where \(\mathbf {h}_v^{(k)}\) represents the node representation of \(v\) at the \(k\)th iteration, \(\mathbf {h}_v^{(0)}\) is the node feature \(\mathbf {x}_v\), and here \(\text{AGG}\) is a weighted sum aggregation function. This algorithm continues the recurrent process until it hits the predefined \(K\) number of iterations needed to form the node representations. A graph-level representation is then produced via:where \(f_{t}\left(\cdot \right)\) is a softmax function guided by an attention mechanism, which preserves and aggregates valuable node representations for specific graph-level tasks. \(\tanh \left(\cdot \right)\) is an activation function, and \(\odot\) is element-wise multiplication.

Another significant deep learning technique that works in the Euclidean domain is CNN. Here, grid-structured data, such as images [84, 85], are studied. Similar to RNN-based GL-DNNs, there are two main branches of CNN-based graph-level learning. In Appendix ??, Figure ?? depicts the details of these two different branches.

The first branch sorts nodes and arranges the node features to form a concentration matrix, of grid-structured data, to train the CNNs. PATCHY-SAN [70] selects a fixed number of neighbors of a central node and sorts neighbors to concatenate their features as the grid-structured feature matrix. By choosing a series of central nodes, PATCHY-SAN constructs some matched feature matrices. Finally, a graph-level representation is produced by the CNN model from the concatenation matrix of all built feature matrices. In addition, Kernel Convolutional Neural Network (KCNN) [73] sorts all vertices in a graph to form grid-structured data. A neighborhood graph is built for each vertex, and a kernel matrix is constructed by implementing the kernel function (i.e., an SPK or an MPK) between all pairwise neighborhood graphs. In this work, the grid-structured data for feeding up CNN is the kernel matrix, where each row is a vector describing the similarities between the neighborhood graph of the matched index vertex and the other neighborhood graphs.

The second branch involves CNN-guided neural network versions of MPKs. These methods have two main steps: aggregating neighborhood information to the central node and using the convolution operation to relabel the aggregated features. NN4G [86] performs a convolution kernel upon 1-hop neighbors for updating the center node and outputs the graph-level representations based on the node embeddings produced by each convolution layer, which is defined as:where \(f(\cdot)\) is a linear or sigmoidal function and \(h_v^{(0)}=0\). Another related work, ECC [72], concatenates 1-hop neighbor embeddings \((\mathbf {h}_u^{(k-1)}: u\in \mathcal {N}(v))\) around the central node \(v\) to construct a feature matrix by the \(k\)th iteration. Subsequently, a convolution and average operation is executed on the aggregated neighbor feature matrix to obtain a representation for the central node. Then, a graph-level representation is produced via max-pooling the node embeddings.

Moreover, Diffusion CNN (DCNN) [71] expands the diffusion process on graphs to derive the probability transition matrix \(\mathbf {P} = [\mathbf {A}, \mathbf {A}^2,\ldots , \mathbf {A}^h] \in \mathbb {R}^{h \times n\times n}\), which presents the transition probability of information transfer from one node to other nodes during \(h\) diffusion steps. The representations of nodes within \(h\) steps is presented as \(\mathbf {P} \mathbf {X} \in \mathbb {R}^{h \times n\times f}\). For graph classification tasks, DCNN permutes the dimensions giving \(\mathbf {P} \mathbf {X} \in \mathbb {R}^{n \times h\times f}\), and all node representations are averaged as \(\mathbf {P}^{*} \in \mathbb {R}^{h\times f}\). Subsequently, a convolution operation is implemented on \(\mathbf {P}^{*}\) to produce a graph-level representation. The convolution operation can be defined as \(\mathbf {h}_{\mathcal {G}} = f\left(\mathbf {W} \odot \mathbf {P}^{*}\right),\) where \(f\left(\cdot \right)\) is a nonlinear activation function, and \(\mathbf {W}\) is a trainable weight matrix for convolution and summation. Although it is similar to MPKs that aggregate multi-hop neighborhoods, DCNN leverages diffusion process to directly aggregate features over multiple steps instead of layer-by-layer. This unique characteristic allows DCNN to capture global topology and direct control over the scale of information aggregation through diffusion steps.

CapsNets [87] were originally designed to capture more spatial relationships between the partitions of an entity than CNNs. CapsNets are available to assemble vectorized representations of different features (e.g., colors, textures) to a capsule dealt with by a specific network. Thus, applying a CapsNet to a graph preserves rich features and/or structure information at the graph level.

Graph Capsule Convolutional Neural Networks (GCAPS-CNN) [74] iteratively aggregates neighbor information under different statistical moments (e.g., mean, standard deviation) to form a capsule representation of the central node, formulated as:where \(\left(\mathbf {W}_1,\mathbf {W}_2,...\right)\) are the learnable weight matrices for mapping the aggregated features into a uniform hidden space with a dimensionality of \(h\). If the number of statistical moments is \(p\) and the final iteration number is \(K\), then each node will be represented as \(\mathbf {h}_v^{(K)} \in \mathbb {R}^{p \times h}\), and the matrix of all \(n\) node embeddings will be \(H^{(K)} \in \mathbb {R}^{n \times p \times h}\). This approach employs a covariance function as the permutation-invariant layer to output a graph-level representation, defined as:CapsGNN [75] iteratively aggregates node features to a center node, and, in turn, adds the aggregation results of each iteration to a capsule representation of the central node. An attention mechanism is then applied to all node capsules to generate a graph capsule that can be plugged into a capsule network for graph classification. Mallea et al. [76] employ the same approach as PATCHY-SAN [70] to find substructures in graphs, while the feature matrices of searched substructures are assembled in a capsule network for graph classification.

Recently, transformers [88] have achieved remarkable success in many fields, such as Natural Language Processing [88] and Computervision [89], attracting interest from the graph-level learning community. Transformers are initially designed for modeling relationships among all pair-wise entities (e.g., words, pixels); such relationships only consider semantic relationships while overlooking structure. Therefore, it still requires endeavors to generalize transformers on graph-level tasks. Dwivedi and Bresson [77] proposed an early Transformer-based GL-DNN, which limits transformers into the neighborhood range as the structure inductive bias, that is,where \(\mathbf {h}_v^{(k)} \in R^{1*d}\) represents the node representation of \(v\) at the \(k\)th layers, \(\mathbf {W}_Q \in R^{d*d_z}, \mathbf {W}_K \in R^{d*d_z}\), and \(\mathbf {W}_V \in R^{d*d_z}\) are the projection matrix to map the node representations as query, key, value vectors, and \(\mathcal {N}(v)\) means the set of nodes in the \(v\)’s neighborhood including itself. Graphormer [78] frees transformers for all node pairs on the graph while encoding structure information (i.e., degree centrality and shortest path) for modeling relationships. In addition, TokenGT [79] treats all nodes and edges in the graph as inputs and augments them with orthonormal identifiers that allow transformers to recognize and exploit the connectivity structure of the graph. The graph-level representation can be obtained by inserting an extra trainable graph entity into TokenGT.

As mentioned, researchers have developed RNN- and CNN-based versions of MPKs. However, as the influence of deep learning has expanded, researchers have also developed various feedforward versions of Message-passing Kernels (MPKs, refer to Section 4.1.1). Collectively, these are called MPNNs. MPNNs are similar to RNN-based MPKs in Equation (15), but MPNNs set different weights in separate layers rather than sharing weights in all layers. Gilmer et al. [25] summarize a collection of MPNNs [90, 91, 92] and further propose a unified framework for this branch of techniques, as shown in Figure 5(a) and denoted as:where \(\mathbf {h}_v^{(0)} = \mathbf {x}_v\), \(M^{(k)}\) is a function that outputs the passed message for the target node based on itself and its neighbors, and \(U^{(k)}\left(\cdot \right)\) updates the embedding of the target node. After multiple iterations, the node embeddings \(\mathbf {h}_v^{(k)}\) learn the local structure information and the graph-level topology has distributed in all nodes. A readout function reads all node embeddings and outputs a graph-level representation, that is:

MPNNs have become the mainstream of graph-level studies [25]. They are also representative of spatial-based GL-GNNs, since they are easy to use through matrix operations. Last, the time and memory complexity of MPNNs only grows linearly with the graph size, making this a very practical approach for large sparse graphs. In recent years, practitioners have developed numerous enhanced versions of MPNNs, including subgraph-enhanced MPNNs (see Section 6.2) and kernel-enhanced MPNNs (see Section 6.3).

The widespread of MPNNs attracts researchers’ interest in exploring their upper-bound capability for distinguishing structures. Recently, some studies [111, 118] have identified flaws in MPNNs, noting that they fail to perform in certain cases, such as regular graphs [94, 106, 119, 120]. The reason for these flaws is that MPNNs, relying on aggregating neighborhood information, are restricted by local topology. Thus, investigating GL-GNNs capable of capturing more topological information has been a crucial stream of study. As yet, practitioners have devised subgraph-based GL-GNNs, which leverage the rich structural information in subgraphs. These subgraph-based GL-GNNs can be divided into two branches. The first branch enhances an MPNN by injecting the subgraph information into the aggregation process, as outlined in Figure 5(b). The other branch borrows the graphlet idea and decomposes the graph into a few subgraphs, merging multiple subgraph embeddings to produce an embedding of the entire graph.

Like the revival of the subgraph idea in the deep learning field, graph kernels that incorporate deep learning techniques have also attracted attention. Similar to subgraph-based GL-GNNs, there are generally two branches of graph kernel-based GL-GNNs. As Figure 5(c) shows, one branch replaces the 1-hop neighbor aggregation and vertex update functions in MPNNs with a kernel function. This group is called the kernel-enhanced MPNNs. Another branch involves designing differentiable and parameterized kernels by plugging kernels into neural networks.

Spectral-based GL-GNNs were started earlier by Bruna et al. [124], which designed graph convolutions via the spectral graph theory [61]. Recently, Balcilar et al. [125] described spectral and spatial graph convolution in a unified way and performed spectral analysis on convolution kernels. The analysis results demonstrate that a vast majority of MPNNs are low-pass filters in which only smooth graph signals are retained. Graph signals with a low-frequency profile are useful for node-level tasks on assortative networks where nodes have similar features to their neighborhoods [126]. However, with graph-level tasks, graph signals beyond the low frequency may be critical, since they can highlight the differences between different graphs [127], and, although MPNNs have been widely used, they overlook the signal frequency of graph data.

In terms of a feature \(\mathbf {x}\in \mathbb {R}^n\) (a column vector of \(\mathbf {X}\in \mathbb {R}^{n\times f}\)) as a graph signal on a graph with \(n\) nodes, spectral graph convolution performs graph signal filtering after transforming the graph signals \(\mathbf {x}\) in spatial space into the frequency domain. According to spectral graph theory [61], the frequency domain generally takes the eigenvectors of the graph Laplacian \(\mathbf {L}=\mathbf {D}-\mathbf {A}\), where \(\mathbf {D}\) is the degree matrix (or the normalized version \(\mathbf {L} = \mathbf {I}- \mathbf {D}^{-\frac{1}{2}}\mathbf {A} \mathbf {D}^{-\frac{1}{2}}\)) of a set of space bases. Note, though, that other bases can also be used, such as graph wavelet bases [128, 129]. Specifically, \(\lbrace \lambda _1,\ldots , \lambda _n\rbrace\) where \(0 \le \lambda _1 \le ... \le \lambda _n \le 2\), and \(\mathbf {U}=(\mathbf {u}_1,\ldots , \mathbf {u}_n)\) are the \(n\) eigenvalues and \(n\) orthogonal eigenvectors of \(\mathbf {L}\), respectively. \(\lambda _i\) represents the smoothness degree of \(\mathbf {u}_i\) about \(\mathbf {L}\). Based on the graph Fourier transformation \(\hat{\mathbf {x}} =\mathbf {U}^\mathrm{T}\mathbf {x}\), the graph signal \(\mathbf {x}\) is mapped to the frequency domain. And \(\mathbf {x}=\mathbf {U}\hat{\mathbf {x}}\) is the graph Fourier inverse transformation that can restore the graph signal in spectral domain to the spatial domain. The polynomial filter is adopted by most of spectral graph convolution methods; for example, ChebNet [112] defines the spectral graph convolution as \(\mathbf {U} \text{diag}(\Phi (\mathbf {\Lambda }))\mathbf {U}^\mathrm{T}\mathbf {x}\), where \(\Lambda =\text{diag}(\lbrace \lambda _i\rbrace _{i=1}^{i=n})\), \(\Phi (\mathbf {\Lambda })=\sum _{k=0}^{K}\theta _k\mathbf {\Lambda }^{k}\) is the polynomial filtering function, \(K\) are the hyper-parameters that realize the localized spectral graph convolution, and \(\theta _k\) is the polynomial coefficient.

Spectral graph convolution can be task-agnostic when graph signals with any frequency profiles are filtered. Conversely, they can also be task-specific; for example, a band-pass filter can highlight graph signals that are strongly related to downstream tasks [125]. However, only a few practitioners have designed graph-level neural networks from the perspective of spectral graph convolution [114, 115]. The main problem with applying spectral convolution in graph-level tasks is the transferability of the spectral filter coefficients from the training graph set to the unseen graphs. The spectral filters depend on the graph Laplacian decomposition, but different graph structures have different graph Laplacian decomposition results. Most recently, Levie et al. [113] theoretically proved the transferability of spectral filters on multigraphs. Balcilar et al. [114] proposed a custom filter function that could output frequency components from low to high to better distinguish between graphs. Due to the limitation of polynomial filters in modeling sharp changes in the frequency response, Bianchi et al. [115] employed an auto-regressive moving average (ARMA) filter to perform graph-level tasks. The ARMA filter is more robust to the changes or perturbations on graph structures, as it does not depend on the eigen-decomposition of the graph Laplacian explicitly. Zheng et al. [116] proposed a graph convolution based on graph Framelet transforms instead of graph Fourier transform with a shrinkage activation to decompose graphs into both low-pass and high-pass frequencies. However, there is no theoretical proof of the transferability of framelet decomposition. In addition, Wang et al. [130] analyzed various spectral GL-GNNs to find that an orthogonal basis whose weight function is related to the density of graph signals can maximize the convergence speed. Thus, they designed a novel spectral graph convolution via the Jacobi basis, which is orthogonal and flexible to adapt to a wide range of weight functions.

Transformers [88] have attracted growing interest from the graph-level learning community. In addition to generalizing it directly on graph-level tasks (see Section 5.5), a more efficient way is to leverage transformer architecture for raising up GL-GNNs. The addition of transformers into GL-GNNs offers numerous advantages, such as capturing long-range interactions and relieving strict structural inductive bias. GTransformer [6] welds GL-GNNs and transformer as a hybrid layer, passing the node representations learned by GL-GNNs through a subsequent transformer. Thus, the final node representations contain both local and long-range topology information to capture precise graph embeddings. GraphGPS [117] constructs the framework that ensembles various GL-GNNs and transformers, achieving state-of-the-art results on multiple graph-level tasks. In addition, SAT [131] employs GL-GNNs and transformers to generate and update subgraph embeddings, respectively, and sums subgraph embeddings as the graph representation.

There are four different types of global graph pooling—numeric operation, attention-based, CNN-based, and global top-\(K\)—all of which aggregate all node embeddings at once to build a graph-level representation.

Global graph pooling ignores the hierarchical structures in graphs. The evolution of a graph is to collect nodes into hierarchical structures (e.g., communities), then to form the graph. Hence, researchers tend to capture hierarchical information through an aggregation process that has multiple parses, which coarsens the graph each time. We have divided hierarchical graph pooling techniques into three branches: clustering-based, hierarchical top-\(K\), and tree-based.

Table 4 summarizes a selection of benchmark graph-level datasets, including TUDataset [160], Open Graph Benchmark (OGB) [161], MOLECULENET [2], MALNET [162], and others [163]. TUDataset [160], consisting of molecules, proteins, images, social networks, synthetic graphs, and data from many other domains, has been widely used to evaluate graph-level learning approaches. However, despite its wide use, it has attracted criticism from some practitioners. For example, Ivanov et al. [164] contend that the sets suffer from isomorphism bias, i.e., they contain isomorphic graphs with different labels, which may hinder model training—a claim based on the analysis of 54 widely used graph datasets. They also note that some of the datasets are too small to train a data-hungry deep learning model. For example, Dwivedi et al. [163] presented that most GL-GNNs have a close performance to others in the small dataset. Further, some topology-agnostic baselines yield a performance that is competitive to GL-GNNs.

Developing practical and large-scale benchmark datasets has become an important issue for the graph-level learning community. To this end, Wu et al. [2] proposed a benchmark named MOLECULENET that contains a set of large-scale graph datasets of molecules for their property prediction. Dwivedi et al. [163] transformed images into graphs for classification, in which a group of pixels is clustered as a node. In addition, 3D point clouds are naturally represented as graph datasets. For instance, MODELNET40 [165] consists of 12,311 meshed models, and each model can be treated as a single graph by sampling 1,000 points as nodes and constructing edges between all neighbors [72]. Based on real-world cybersecurity scenarios, Freitas et al. [162] proposed a large-scale graph dataset of over 1.2 million graphs with imbalanced labels. Recently, OGB [161] published application-oriented large-scale graph datasets of molecules, proteins, and source code cooperation networks.

The development of graph-level learning has been impeded by unfair evaluations. For example, Ruffinelli et al. [185] argue that some graph-level learning models only produce state-of-the-art performance because of tricks with the model’s training, not because of the novel ideas proposed in the articles. However, there is no consensus on which evaluation to use with the most widely used graph datasets, such as TUDatasets, nor is there even a universally accepted data split [186]. Hence, to evaluate the graph-level learning models in a unified and fair way, some researchers have attempted to establish a standard model evaluation protocol. For example, Dwivedi et al. [163] built a benchmark framework based on PyTorch and DGL⁷ that evaluates models on graph classification and graph regression tasks with an unified model evaluation protocol. They do apply training tricks, such as batch normalization, residual connections, and graph size normalization, to GL-GNNs to measure their effects. But all models being evaluated with the protocol are subject to the same training regime. Similarly, in addition to the large-scale graph datasets, OGB [161] provides a standard model evaluation protocol that includes a unified way to load and split data, the model evaluation itself, plus the cross-validations. Recently, Zhu et al. [187] provided a benchmark framework for graph contrastive learning.

Challenges: Existing GL-GNNs often have a complex architecture, consisting of a number of different components, e.g., multiple graph convolutions and graph pooling layers. Developing effective NAS methods to free researchers from repeatedly searching for good architectures manually and, in turn, tuning the parameters is an urgent goal. However, the multitude of optional components with numerous parameters results in an exceedingly vast parameter search space for GL-GNNs. Additionally, diverse graphs could desire distinct optimal parameters, raising the demand for a globally searched architecture that fits all graphs.

Opportunities: Although NAS has attracted a bulk of interest from the deep learning community, there is limited exploration for NAS on GL-GNNs. To fill this gap, one strategy could be leveraging reinforcement learning or policy gradients to restrict the entire architecture space to an optimal subspace by maximizing expected results (e.g., accuracy). Another strategy could involve estimating optimal parameters based on intrinsic graph properties. This approach would enable the consideration of diverse graph properties, thereby providing a globally applicable architecture for entire graph datasets. For instance, Yang et al. [190] estimated the embedding dimensionality for each graph via their entropy and sought a few centers of all individual estimated dimensionalities as final embedding dimensions for encoding the graph dataset.

Challenges: In geometric graphs [191], each node is described by two vectors, i.e., a feature vector and a geometric vector. For example, in 3D molecule graphs, atoms are assigned geometric information such as speeds, coordinates, and spins that together comprise the geometric vector. A key challenge for GL-GNNs working on geometric graphs is the equivariant, i.e., when inputting a geometric graph with a specific rotation into a GL-GNN, the subsequent output should reflect the same rotation.

Opportunities: Geometrically Equivariant GL-GNNs have been a newly raised field in recent years; as yet, there is limited research [192, 193]. A straightforward direction could be to extend the current GL-GNN architecture on both node features and geometric vectors to construct the GL-GNNs on geometric graphs. For instance, Equivariant Graph Neural Networks (EGNN) [192] expand MPNNs aggregating both feature vectors and geometric vectors, and AMP [194] designs a novel message-passing scheme considering the directional effects from an external field or a set of particles unreachable in a graph. In addition, we argue that presenting geometric graphs as hypergraphs or multi-view graphs can also help us better learn complex geometric features.

Challenges: Providing global explanations for GL-GNNs’ prediction could offer high-level insight into model behavior and task mechanism. For example, we can learn why models diagnose brain networks as normal or disordered without case-by-case explanations. However, building global explainable GL-GNNs is non-trivial, since it requires an excellent abstraction ability to explain generic patterns of a set of graphs, rather than only recognizing the significant part in a single graph.

Opportunities: Most algorithms for explaining the predictions of GL-GNNs focus on instances (e.g., PGExplainer [195], GSAT [196]); globally explainable GL-GNNs is less studied. A promising direction in building globally interpretable GL-GNN could be summarizing rules from all instance-level explanations via statistical inference methods, e.g., logic combination [197], Bayes theorem, and so on. Furthermore, the graph generation techniques could also be a significant tool, generating generic graph patterns without reference to instance-level explanations [198].

Challenges: Existing graph pooling techniques leverage all nodes collectively or seek the most representative nodes for presenting graphs, but neither can ensure a low redundancy between the selected nodes. An informative graph pooling should select the set of nodes within the high representative and low redundancy. Yet, there are no existing criteria to evaluate the redundancy of a set of nodes, and optimizing the node set with two criteria could be a nonconvex problem.

Opportunities: As far as we know, informative graph pooling is first identified in this article. We highlight the informative node set selection for pooling with two criteria, high representative and low redundancy. On the one hand, the criteria of representative nodes could be a score function via neural networks [4, 136] or the policy gradient’s feedback. On the other hand, the redundancy of a set of nodes can be evaluated by the similarity of their features or even the graph kernel value between their neighborhoods. The nonconvex optimization problem could be alleviated by reinforcement learning or evolutionary algorithms.

Challenges: Most state-of-the-art graph-level learning models are data-hungry, especially GL-GNNs. In the industrial scenario, however, the size of the graph dataset sourced from a single institution is limited for training models. There is a practical demand to develop graph-level federated learning, that is, joint training graph-level learning models via diverse institutions. A major obstacle to graph-level federated learning is the divergence of graph structure and feature distribution across graph datasets from various institutions. This incongruity leads to complications in both training and convergence of federated models.

Opportunities: Federated learning has attracted a surge of attention in promoting graph learning, as both are valuable in real-world applications. Xie et al. [199] proposed a graph-level federated learning model, which clusters graph datasets from various institutions and trains an exclusive GNN for each cluster. This could be a promising strategy that divides the multi-sourced data into homogeneous clusters to smooth training. Another strategy could involve enhancing the generalizability of graph-level learning models, which enable models trained via common patterns between graphs sourced from distinct institutions.

Challenges: Graph-level tasks could face an imbalanced state of class labels, such as anomaly detection [200] and long-tail event detection [201], confronting challenges on model learning. Specifically, the model trained on the data with an imbalanced label distribution might be biased towards the majority classes, that is, with many samples and the minority classes consisting only of a small number of samples, the model may be under-fit.

Opportunities: Although imbalanced learning has been a long-standing issue in deep learning, graph-level imbalance learning, especially with deep models, is underexplored. Adopting some simple but effective solutions for imbalanced learning is an easy-implemented way, such as Wang et al. [202] over-sampled graphs in the minority class to relieve imbalance distributions between the majority and minority classes. However, this approach may be criticized for its shortcomings, such as over-fitting and changing the original distribution of the dataset. We argue that a more reasonable direction is leveraging graph generation techniques to expand the subspace of the minor classes [203, 204, 205]. Another possible direction could be to capture the special factors of minority graphs, e.g., key substructures existing in minority graphs but not appearing in the majority. Towards this, strengthening the structural awareness of the current graph-level learning tools is feasible.

Challenges: In this survey, almost all the investigated graph-level learning methods are assumed to work on fundamental graphs (i.e., unweighted and undirected graphs, and their nodes and edges are homogeneous). However, realistic graphs are usually complex graphs, such as heterogeneous graphs involving multiple types of nodes or edges, dynamic graphs whose structure or attributes evolve over time, and so on. Graph-level learning on complex graphs confronts the challenges of tuning graph-level models for the specific type of graph according to its structure and attributes.

Opportunities: Compared to highly developed graph-level learning on fundamental graphs, mining complex graphs still requires further development. For instance, most GL-GNNs for heterogeneous graphs rely on manually defined meta-paths (i.e., a sequence of relations between nodes or edges) that are based on domain knowledge. However, defining meta-paths is not only expensive but also loses partial semantic relationships [206, 207]. Thus, developing the automatic mechanism for exploring comprehensive meta-paths could be a feasible direction. Dynamic graphs could be conceptualized as a collection of static graphs sourcing from a series of temporal scales. One potential strategy for dealing with dynamic graphs is learning from distinct static graphs at each scale, culminating in the fusion of all outcomes [208]. In addition, building a cross-time graph linking all static graphs together represents a promising direction, e.g., tdGraphEmbed [209] adopts a temporal random walk across all time-scale static graphs.

Challenges: Almost all the literature on graph-level learning treats each graph in a dataset as an independent sample. However, considering the interactions between graphs should lead to challenging and highly novel research. For example, learning the interactions between graphs might be used to predict the chemical reactions when two compounds meet or to explore the effect of mixing multiple drugs. Graph-level interaction learning raises the requirement to explore the graph-graph relationships, which is tough, since there are no explicit metrics to compare two graphs regarding a tremendous number of irregular components (e.g., nodes, substructures).

Opportunities: Although this topic has strong practical implications for graph-level learning applications in biochemistry, it is still understudied. A few attempts [104, 210] revamp GL-GNNs for this task, but we argue that GL-GNNs are not the most suitable tool. Graph kernels and attention mechanisms could be the better candidate for this task, due to their advantages in measuring pair-wise similarities. In addition, capturing crucial substructures that lead to chemical reactions can be a powerful assistance, which requires the addition of interpretable learning.

Challenges: Anomaly detection aims to identify objects that significantly deviate from the majority of other objects. However, when it comes to the anomalous as entire graphs, the inducement could be node features or substructures in graphs. Generally anomaly detectors mostly only pay attention to outliers in the feature space, but the challenge of graph-level anomaly detectors is identifying outlier points in terms of both node feature and structure.

Opportunities: Graph-level anomaly detection that identifies anomalous graphs in a graph dataset is a research topic of great value application-wise but lacks exploration. Some pioneering studies [211, 212] combine state-of-the-art GL-GNNs with traditional anomaly-detection methods (e.g., one-class classification [213]) to detect anomalous graphs in a graph dataset. This is a feasible way but still needs to solve some derivative issues, e.g., performance flip, and hypersphere collapse [212]. Another possible direction could be designing specific graph convolution layers to highlight anomalous. This is because current graph convolution works like a low-pass filter [125] that smooths the anomalous information in a graph [214].

Challenges: Out-of-distribution (OOD) learning indicates the scenarios in which the test data own deviation distribution as the training data. Almost all the graph-level learning algorithms assume that the training and the test data will have the same distribution. However, this I.I.D. (independent, identically distributed) assumption may be violated in some scenarios. For example, molecules with the same function may contain some different scaffolds. When test data have a scaffold that never appears in training data, graph-level learning methods models will not perform nearly as well.

Opportunities: The graph-level learning community has recently noticed the OOD generalization issue and desired related research in response. Invariant learning could be a direction for this task, for instance, Wu et al. [215] identified the causal subgraphs that are invariant across different distributions to improve the OOD generalization ability of GL-GNNs. Similarly, Bevilacqua et al. [216] employed an inference model to capture approximately invariant causal graphs to improve the extrapolation abilities of GL-GNNs. In addition to invariant learning, many techniques such as meta-learning, data augmentation, and disentanglement learning are feasible for OOD learning. Combining these techniques with GL-GNNs is likely to be the future of achieving graph-level learning models with a strong OOD generalization capacity. For more details on this topic, we refer readers to the graph OOD learning benchmark [217].

Challenges: Brain networks, also known as connectomes, are maps of the brain where the nodes denote the brain regions of interest (ROIs) in the brain, and the edges denote the neural connections between these ROIs. Existing graph-level learning algorithms, especially GL-DNNs and GL-GNNs, tend to be over-parameterized for learning brain networks, which are usually sparse. Further, obtaining a brain network usually comes at a high cost, because it involves scanning an individual’s brain and converting the neuro-image into a brain network. In addition, existing GL-DNNs and GL-GNNs cannot handle the correspondence of nodes between different graphs. However, distinct brain networks have the same ROIs, and node identities and ROIs are one-to-one correspondence [218].

Opportunities: Brain network analytics pertains to a vast of valuable realistic applications, such as distinguishing brains with neurological disorders from normal individuals and identifying those regions of the brain that are the cause of brain disease. We argue that graph-level learning with brain networks requires lightweight models to prevent the model from overfitting on realistic small datasets. In addition, the model should add a module for identifying corresponding nodes between different graphs.

Challenges: Standard graph-level learning views each graph as an instance, which can be restrictive in practical applications. Considering a product that has multiple reviews on an online shopping page, each review can be represented as a graph of the textual semantics among the words. To predict any properties of that online product, one needs to learn from review-based multi-graphs—that is, multi-graph-level learning. Two significant challenges arise when multiple graphs are bagged as an object: how to glean insights from multi-graph level labels instead of individual instance-level labels and how to filter redundant information across multi-graphs.

Opportunities: To the best of our knowledge, the current multi-graph-level learning algorithms are all subgraph mining methods [219, 220]. However, these endeavors cannot leverage label information to guide the learning process. We argue that deep learning models will revolutionize this task; one possible direction is to build a new GL-GNN framework enabling multiple graph embeddings used to predict a single label. Another promising way could be informative graph pooling, which avails of selecting the node set that contains highly representative and low-redundancy information across multiple graphs.