Graph Perceiver IO: A General Architecture for Graph Structured Data

Multimodal machine learning addresses fundamental goals for artificial intelligence by integrating and modeling multiple modalities, including visual, linguistic, and acoustic signals. Here, we introduce two branches of multimodal research: representation learning and general architecture.

Graph Neural Networks (GNN) is an efficient and well-designed framework for geometric data. The use of GNNs has expanded the range of applications for frameworks based on neural networks.

Jaegle et al. [6] proposes the Perceiver, a general perception module with iterative attention for handling the diverse and high-dimensional multimodal inputs. The Perceiver has two components of arrays, input arrays $x$, and latent arrays $z$. For given data instances, the Perceiver transforms the given data instances as the inputs array $x\in\mathbb{R}^{M\times C}$ where $M$ and $C$ denote the dataset properties such as the image size and the number of channels. The latent arrays $z\in\mathbb{R}^{N\times D}$ are learnable latent representations, where $N$ and $D$ are the number of latent and the latent dimension, respectively. The Perceiver adopts the two types of attention, cross-attention and self-attention, and both attentions are query-key-value attention, similar to the Transformer [1]. First, the cross-attention computes the attention between the latent arrays and the input arrays. The latent arrays are queries, and they attend to the important information from the key, the input arrays. The relevant input features for the given tasks are incorporated into the latent array with cross-attention. Second, the Perceiver adopts the self-attention for the latent arrays. Attention between latent arrays and input arrays reduces the time and space complexity compared to the self-attention for the input arrays only. The attention complexity of the Perceiver is $O(NM)$ while the complexity of the self-attention for input-image is $O(N^{2})$. In summary, the Perceiver is composed of the multiple blocks of cross-attention and the latent Transformer that adopts the self-attention for the latent arrays. The input arrays are fed into the Transformer iteratively across the layers. After the multiple blocks, the Perceiver adopts the average pooling over the index dimension and utilizes it to predict the target label.

The Perceiver is a general model that handles diverse datasets with flexible input structures. However, the output structure of the Perceiver is not flexible, and the Perceiver is limited to the classification tasks. To extend the Perceiver into diverse tasks such as language modeling and autoencoding, flexible output structures are necessary. Perceiver IO proposes an additional output query array components $y\in\mathbb{R}^{M\times E}$ for the flexible outputs structure. For the image classification task, the $M$ and $E$ denote the number of images and the number of classes, respectively. Perceiver IO adds the additional query-key-value attention block on the top of the Perceiver. The additional attention block computes the attention between the output query array and the latent arrays extracted by the Perceiver. The shape of the output query array is a controllable hyper-parameter, and it induces flexible output structures that produce any size of outputs.

The Perceiver and Perceiver IO attend to the relationship between the latent arrays and input arrays. They adopt query-key-value attention that is similar to the Transformer. Different from the convolutional neural nets (CNN) [37, 38] or the vision Transformer (ViT) [39, 40], the Perceiver operates on the individual pixels independently without patches or convolution operations. However, attention computation is permutation invariant, and the attention-only mechanism is hard to treat the sequence order. To incorporate the order information for sequence and spatial information for images, the Perceiver and the Perceiver IO introduce the learned positional encoding or Fourier-based positional encoding with sinusoid functions.

The Perceiver is a general architecture, and it has high flexibility for input and output structure. From its flexibility and generality, The Perceiver and its variants

handle the diverse tasks for image, text, speech, and 3D point clouds. They extend their works to incorporate the heterogeneous multimodal dataset such as audiovisual sequences, and the Perceiver shows competitive results. However, the application of Perceiver is limited to the non-graph structured dataset, and they do not handle the graph structured dataset that has topological information.

Extending the Perceiver to handle the graph structured dataset is non-trivial. First, the Perceiver is a general architecture, and it already shows the competitive results for diverse tasks. Therefore, simple extensions that do not modify the overall model structures are required. Second, the Perceiver receives the flattened inputs, and incorporating the topological information represented by the adjacency matrix into the Perceiver is challenging.

Graph data usually consists of $X\in\mathbb{R}^{M\times C}$ matrix, a set of nodes features, and adjacency matrix $A\in\mathbb{R}^{M\times M}$, which represents a set of relational information between nodes. In order to train graphs using Perceiver IO, the input array and the output query array should be constructed by using $X$ and $A$ properly. To handle the graph-structured data, topological information is essential. We can divide the topological information on the graph as relational information and canonical positional information. Both two information is essential for the graph-related tasks such as node classification and graph classification. To incorporate the topological information, we propose the following two methods 1) output query smoothing, and 2) positional embedding as shown in the Figure 1. The shape of the output query array depends on the given task, and we will discuss it in Section Output Query Array. The overall structure of our proposed model is in Figure 2.

One of the major problems of the Graph Perceiver IO is to incorporate the adjacency matrix. The adjacency matrix that is widely utilized in GNNs is not adaptable for the Graph Perceiver IO. Also, the Graph Perceiver IO requires a flexible output structure to handle the diverse graph-related tasks such as node classification, graph classification, and link prediction. For the flexible output array structure, we adopt the output query array by following the Perceiver IO. The output query shape can be determined by the task specifically. It is noted that the output query can be used as a pretrained embedding, or it can be learnable parameters. For graph classification task that requires a single label per graph, we set the output query size as $1\times D_{q}$, where $D_{q}$ denotes the output query array dimension. For node-specific tasks such as node classification and link prediction, we set the output array shape as $M\times D_{q}$ where $M$ is the number of nodes. The simple choice of the output array is raw nodes features $X\in\mathbb{R}^{M\times C}$ that is the same as the input array. However, we find that the output query array based on the raw node features tends to show poor performance. Furthermore, raw node features do not contain any relational information of adjacency matrix. Instead of raw node features, we propose a smoothing based output query array that is smoothed features of raw node features $L$ times [41]. The following Eq. 1 denotes the $L$ times smoothed node features, the output query array of the Graph Perceiver IO,

where $\widetilde{A}=A+I$ denotes a adjacency matrix with self-loop and $\widetilde{D}_{ii}=\sum_{j=0}\widetilde{A}_{ij}$ denotes node degree matrix of $\widetilde{A}$. SGC [41] removes nonlinear function between GCN layers and collapse repeated multiplication of matrix into $L$-th power of matrix like Eq. 1 which extracts smoothed features of $X$. As a result, extracted features $\widehat{X}$ tends to have similar representation to nearby nodes and help to make similar predictions. That is, the SGC incorporates adjacency matrix into its input to get $L$-hops neighbor information. In a similar way, we utilize adjacency matrix to obtain $\widehat{X}$ as an output query array which contain relational information.

Besides, we adopt the APPNP smoothing [42] as an output query array as shown in Eq. 4.2.

APPNP adopts personalized propagation, and it provides more data specific smoothing methods. We empirically find that the output query with a smoothing method is one of the key factors for the Graph Perceiver IO.

The Graph Perceiver IO requires the same input structure as the Perceiver or Perceiver IO. For image and text dataset, jaegle et al. propose Fourier embedding to consider the spatial or sequential information, but it shows poor performance for graph classification [7]. Appendix C. presents a detailed result. To reflect the topological information, specifically canonical positional information, with the original Perceiver input array structure, we adopt the random walk positional embedding ($RWPE$) [43]. Random walk operators are defined as $R=AD^{-1}$ where $A\in\mathbb{R}^{M\times M}$ is the adjacency matrix, and $D$ is the degree matrix. $RWPE$ of node $i$ is defined as

where $R_{ii}^{t}$ is the probability of starting from the $i$ node, walking $t$ times, and returning to the $i$ node. dwivedi et al. adopt $RWPE$ as positional encoding initialization for distinguishing several cases of non-isomorphic graphs and structurally different nodes which messeage-passing GNNs and 1-WL fail to distinguish. The choice of sufficiently large $t$ gives a unique node representation to distinguish each node and graph. Besides the node features, we concatenate the $RWPE$ to obtain nodes representation distinguishing non-isomorphic graphs and structurally different nodes. There is no restriction on the attention coverage, and it makes the Graph Perceiver IO handles the global structure information efficiently. It is noted that the injection of $RWPE$ into the Graph Perceiver can be interpreted as an inductive bias to consider the local information as well as the global information. Compared to typical GNNs, the Perceiver has lower space complexity in terms of the input array. GNNs requires $O(M\times C+M\times M)$ on dense graph, while the Perceiver Graph IO needs $O(M(C+t))$, where $t$ is the controllable hyper-parameters.

The Graph Perceiver IO has the capability to perform diverse graph-related tasks such as classification and prediction. In node classification tasks, the output array obtained after going through the logits layer contains each node’s predicted score. We use the cross-entropy loss to learn node embedding. For graph classification tasks, we set a size of output query array to 1-dimension vector. Then we pass the array to the logits layer (e.g., a single linear layer) instead of the read-out layer usually used for global pooling in graph-level tasks. We evaluate the cross-entropy loss with target label.

For link prediction tasks, we conduct the inner product between each pair of node features which is the output of the last cross attention layer. In the same manner, as GAE [30], We use the reconstruction loss for training our model. Table 1 provides configuration of each array and whether or not the logits layer is used for each task.

The Graph Perceiver IO requires a single adjacency matrix-related operation to make the smoothed output query before the model training. The smoothing operation is only once conducted, and it never appears during the model training. The mechanism is similar to the Simplifying Graph Convolutional (SGC) [41] that only performs single adjacency matrix-related operation. Therefore, the Graph Perceiver IO has an efficient computation time compared to the other graph neural networks. Besides, there is no attention between inputs, but there is attention between the latent array and the input array, or the output query array and the input array. The complexity of attention between latent arrays does not depend on the number of nodes, and the complexity of attention between latent and input arrays depends on the number of nodes linearly. However, the current Transformer variants, such as Graph Transformer architecture [34] adopt the input-wise attention, and the computation time is proportional to the square of a number of nodes. Therefore, Graph Perceiver IO has advantages in the time complexity as well as its simplicity and multi-modal learning.

We provide comprehensive experimental resists for diverse datasets and tasks. Table 2 describes the dataset statistics for graph-related tasks. For the preprocessing and train/test splits, we follow the benchmark experimental settings for each task and dataset. We follow the same settings with the [44] for node classification, graph classification and link prediction, respectively. We provide the dataset as well as the source code as supplementary files. It is noted that the graph-related dataset will be downloaded automatically upon running the source code.

For node classification experiments, we adopt the three benchmark data, Cora [45], CiteSeer [46], and PubMed [47]. We follow all experimental settings from [44], and we repeat the experiment 100 times. Table 3 denotes the accuracy of node classification task. The Graph Perceiver IO shows relatively lower results compared to the advanced graph neural networks, but our model shows the competitive results on the PubMed dataset.

To analyze the attention properties of the Graph Perceiver IO, we visualize the attention weights of cross-attention and the attention between the latent arrays and the input arrays as shown in Figure 3. Each latent index in the Graph Perceiver IO captures the different nodes with high diversity. Additionally, each latent focuses on the specific class group of nodes relatively. Besides, we analyze the learned embedding from the Graph Perceiver IO as shown in Figure 4. From the embedding visualization, we validate the Graph Perceiver IO has a relatively high uniformity embedding space.

Besides the classification task, we validate our models on the link prediction task. Table 4 denotes the results of the link prediction task. We utilize the features extracted by the cross attention between the output query array and latent array for the link prediction task. The Graph Perceiver IO shows the competitive results with the VGAE [30], but our model shows competitive performance compared to the state-of-the-art, VGNAE [33], that utilizes the additional normalization steps with the VGAE. It denotes that incorporating the further graph-specific regularization term into Graph Perceiver IO would be necessary. In Figure 5, we plot t-SNE to compare the performance of the three models in link prediction task.

We validate our models on the graph classification task. Graph classification tasks require the understanding of both the local and global graph structures. We repeat the experiments ten times, and we follow the same experimental protocols with the [44]. Table 5 denotes the accuracy of the graph classification on diverse benchmark dataset. For MUTAG [57] and PROTEINS [57], Graph Perceiver IO shows superior performance compared to the recent GNNs. In short, Graph Perceiver IO has a high capacity to incorporate both the node features and link information simultaneously. It is noted that MUTAG and PROTEINS have node features while IMDB, REDDIT, and COLLAB [58] have no node features. Even though there are no node features, the Graph Perceiver IO has competitive results with the recent GNNs. It denotes that the Graph Perceiver IO handles the topological information of graph structured data with the positional embeddings.