Relating-Up: Advancing Graph Neural Networks through Inter-Graph Relationships

GNNs attempt to exploit the relational information in real-world, thereby enhancing various downstream fields, such as molecules[13], recommendation[14], and social networks[15, 16]. Pioneering architectures such as GCNs [1], GraphSAGE [17], GATs [18], GIN [8] have ingeniously introduced the convolution operation to graphs. The foundational philosophy behind these designs is the recursive aggregation of information from neighboring nodes [19, 8], epitomizing the classic GNN paradigm that emphasizes neighborhood aggregation to discern local intra-graph relationships. In the specific field of graph classification, pooling is usually used to obtain the representation of the entire graph [20, 3, 21]. These methods form efficient representation of the entire graph by shrinking graph into different scales. Although many variants of GNNs with different neighborhood aggregation and graph-level pooling schemes have been proposed, their main focus remains on intra-graph, mapping the representation of a graph by summarizing node information enhanced through intra-graph structure, inadvertently neglecting inter-graph relations.

Despite the exceptional prowess of GNNs in theoretical settings, their practical efficacy on real-world graphs often remains precarious [22]. To address the overreliance on labeled data and intrinsic oversomoothing issue, graph data augmentation has emerged as a pivotal technique to enhance the robustness and generalization of GNNs[23]. Graph data augmentation typically involves creating synthetic graphs [11] or modifying existing ones [24] to reflect potential relationships within a transformation neighborhood, encouraging the model to learn more generalizable patterns. While these approaches internally exploit the relationships among variants graphs within a transformation neighborhood [25], they do not explicitly facilitate learning inter-graph relationships, which is a critical aspect of comprehensively understanding graph data.

Graph contrastive learning is a burgeoning area in graph representation learning, focused on extracting meaningful patterns from graphs by emphasizing contrasts between predefined graph relationships. Graph contrastive learning aim to maximizing the similarity between representations of similar graphs while minimizing it for dissimilar ones [12, 26]. However, this approach encounters a critical limitation in its inability to adaptively handle inter-graph relationships. The effectiveness of graph contrastive learning is contingent upon predefined priors knowledge, which limits its scope of application. It often struggles to autonomously uncover hidden or implicit relationships across graphs, thereby overlooking insightful connections.

Recent advancements have utilized semi-supervised learning and class-aware refinements for graph classification, such as SEAL [15] and CARE [27]. Diverging from these methods, our proposed module introduces a dynamic mechanism that continuously evolves graph representations by leveraging inter-graph relationships, enhancing robustness and contextual awareness. Unlike SEAL, Relating-Up adaptively uncovers complex relationships across graphs. Furthermore, it extends the scope of graph representation by exploring the varied structural and feature-based relationships across graphs, beyond traditional class labels.

Overall, our proposed Relating-Up addresses these shortcomings by inherently leveraging inter-graph relationships. It adaptively and dynamically learns the complex relationships across graphs, offering a more comprehensive and insightful perspective of graph data.

In the context of graph representation learning tasks, we consider a graph denoted as $\mathcal{G}=(\mathcal{V},\mathcal{E})$, where $\mathcal{V}$ represents the set of nodes and $\mathcal{E}$ signifies the set of edges. Each node $v\in\mathcal{V}$ is characterized by a feature vector $\mathbf{x}_{v}\in\mathbb{R}^{d}$, and the total number of nodes is given by $|\mathcal{V}|=n$. The edges, $\mathcal{E}$, play a pivotal role as they define the intra-graph relationships between the nodes.

The primary objective in graph representation learning tasks is to learn a function $f_{\mathcal{G}}:\mathcal{G}\rightarrow\mathbf{E}_{\mathcal{G}}$. The $f_{\mathcal{G}}$ is responsible for encoding the graph $\mathcal{G}$ into an informative representation space $\mathbf{E}_{\mathcal{G}}\in\mathbb{R}^{d_{g}}$, which is instrumental for various downstream tasks. Specifically, for graph classification tasks, this involves combining a classification head $f_{\theta}:\mathbf{E}_{\mathcal{G}}\rightarrow y$ trained on a set of graphs $\mathbb{G}=\{(\mathcal{G},y)\}$ to facilitate accurate classification.

To effectively capture the intricate relationships among nodes, GNN architectures recursively updating node representations according to the intra-graph relationships among neighboring nodes using a message passing strategy, formalized as follows:

where $\mathbf{h}_{v}^{l+1}$ represents the node representation of node $v$ after the $l-\text{th}$ layer, with $\mathbf{h}_{v}^{0}$ initialized as $\mathbf{x}_{v}$. The message-passing strategy for each GNN layer simplifies to $\mathbf{h}_{v}^{l+1}=\text{GNN}^{l+1}(\mathbf{h}_{v}^{l},\mathcal{N}(v))$, where $\mathcal{N}(v)$ denotes the neighborhood of node $v$, representing intra-graph relationships. The functions $\text{Aggregate}(\cdot)$ and $\text{Combine}(\cdot)$ are parametric functions designed to aggregate neighborhood information and combine them to update node representation.

By stacking multiple message-passing layers, a set of node representations is produced. The overall graph representation, $\mathbf{E}_{\mathcal{G}}\in\mathbb{R}^{d_{g}}$, is then obtained through a $\text{Readout}(\cdot)$ function as defined by:

where $\text{Readout}(\cdot)$ is a permutation invariance function to capture the structural nuances of the graph.

For a given graph $\mathcal{G}\in\mathbb{G}$, the graph encoder $f_{\mathcal{G}}$ transform individual graph structures and proprieties into fixed-dimensional representations $\mathbf{E}_{\mathcal{G}}$. Subsequently, $\mathbf{E}_{\mathcal{G}}$ is fed into the classification head, denoted as $f_{\theta}$, to obtain class probabilities. The loss function is typically defined as the CrossEntropy of the predictions over the labels:

where $\hat{y}_{gc}=\text{softmax}(f_{\theta}(\mathbf{E}_{\mathcal{G}}))$ denotes the predicted probability for graph $\mathcal{G}$ belonging to class $c$, and $y_{gc}$ is the ground truth label.

In Relating-Up, we implement graph encoder $f_{\mathcal{G}}$ by stacking multiple GNN layers, which extracts a fixed-dimensional representation $\mathbf{E}_{g}$ for each graph $\mathcal{G}\in\mathbb{G}$. Notably, Relating-Up is designed for integrate seamlessly with various GNN backbones without altering their fundamental operations.

Upon deriving the graph representations, the relation encoder, denoted as $f_{\mathcal{R}}$, dynamically interprets the relationships between these graphs. Specifically, it processes a set of graph representations, symbolized as $\mathbf{E}\in\mathbb{R}^{|\mathbb{G}|\times d_{g}}$. Each layer of $f_{\mathcal{R}}$ consists of a multi-head self-attention (MSA) mechanism and a feed-forward network (FFN) block, each followed by a layer normalization (LN). The MSA, pivotal to the encoder, dynamically computing inter-graph relationships as:

where $\mathbf{Q}\in\mathbb{R}^{|\mathbb{B}|\times d_{q}}$, $\mathbf{K}\in\mathbb{R}^{|\mathbb{B}|\times d_{k}}$, $\mathbf{V}\in\mathbb{R}^{|\mathbb{B}|\times d_{v}}$ represent queries, keys, and values, respectively, derived from the graph representations. $|\mathbb{B}|$ is the batch size during the training phase. Each head in the MSA captures unique relationship patterns, with their outputs concatenated and linearly transformed for comprehensive relationship encoding:

where the operations for $h$ parallel projections are parameter $\mathbf{W}^{Q}_{i}\in\mathbb{R}^{|\mathbb{B}|\times d_{k}}$, $\mathbf{W}^{K}_{i}\in\mathbb{R}^{|\mathbb{B}|\times d_{k}}$, and $\mathbf{W}^{V}_{i}\in\mathbb{R}^{|\mathbb{B}|\times d_{v}}$, where $h$ stands for the number of attention heads. The output projection matrix is $\mathbf{W}^{O}\in\mathbb{R}^{hd_{v}\times d_{g}}$. Then, the inter-graph relation-aware representation at $l$-th relation layer is formulated as:

where $\mathbf{R}_{\mathcal{G}}\in\mathbb{R}^{d_{g}}$ denotes the refined relation-aware representations, now enriched with inter-graph relationship information. This approach allows Relating-Up to dynamically and adaptively learns the nuanced relationships across graphs, which is crucial for tasks that require a comparative understanding of the inter-graphs relationships.

We introduce an innovative feedback training strategy as a pivotal component of the Relating-Up module. Algorithm 1 reports the pseudo-code of the feedback training strategy. This strategy is ingeniously designed to dynamically utilize the potential inter-graph relationships. Specifically, as shown in Figure 2 (b), we utilize a feedback loop mechanism to progressively refine graph representations. Mathematically, this strategy involves minimizing the discrepancy between the original graph representation space and relation-aware representation space,ensuring effective integration of insights from the relation-aware space into the original graph representation. To achieve this, we construct the feedback loop mechanism by two classifier $f^{\mathcal{G}}_{\theta}$ and $f^{\mathcal{R}}_{\theta}$ after graph encoder and relation encoder, respectively. The relation-aware insights from relation encoder are then distilled and conveyed to graph encoder to established a dynamic feedback loop:

where $\mathcal{L}_{class}(\mathcal{G})$ is the CrossEntropy loss for the labeled graph entities from the $f^{\mathcal{G}}_{\theta}$ and $f^{\mathcal{R}}_{\theta}$. The $\mathcal{L}_{distill}(\mathcal{G})$ is formulated as:

where $D_{kl}(\cdot,\cdot)$ is the Kullback-Leibler divergence, $D_{kl}(p,q)=\sum_{j}p_{j}log\frac{p_{j}}{q_{j}}$. $\psi=\text{softmax}(f^{\mathcal{G}}_{\theta}(\mathbf{E_{\mathcal{G}}})/T)$ and $\Psi=\text{softmax}(f^{\mathcal{R}}_{\theta}(\mathbf{R_{\mathcal{G}}})/T)$ are $f^{\mathcal{G}}_{\theta}$ and $f^{\mathcal{R}}_{\theta}$ predicted probability distribution, respectively. $T$ is the temperature of distillation with a larger $T$ makes the probability distribution softer. The relation hints is defined as the inexplicit knowledge in relation-aware representation to guide $f_{\mathcal{G}}$ to glimpse the global landscape of $f_{\mathcal{R}}$ during the training period. It works by decreasing the L2 distance between $\mathbf{E}_{\mathcal{G}}$ and $\mathbf{R}_{\mathcal{G}}$:

By embedding a feedback strategy that iteratively refines graph representations with the relation-aware insights, this strategy significantly enhances the capability of GNNs to understand and utilize the rich and complex tapestry of inter-graph relationships.

During training phase, the relation encoder and relation-aware classifier actively enhance the graph encoder with deep insights into inter-graph relationships. This process embeds a rich understanding of these relationships directly into the graph representations, ensuring that the encoder captures not only intra-graph features but also the nuanced dynamics between different graphs. As a result, during inference phase, the reliance shifts solely to this enriched graph encoder and original graph representation classifier for direct classification. This shift is underpinned by the premise that the relational insights, once integrated into the graph representations during training, remain inherently effective for classification tasks. The elimination of the relation encoder and relation-aware classifier during inference significantly streamlines the process, optimizing for speed and computational efficiency while maintaining the robustness and accuracy imparted during training.

GNN Backbones. In keeping with the focus of our research on enhancing GNN architectures to leverage inter-graph relationships, we primarily compare our module against widely used GNN backbones. Specifically, we assess the performance improvements achieved by integrating the Relating-Up module with various GNN backbones. The comparative results, as depicted in Table 1, illustrate both the original performance of the GNN backbones and the enhancements gained through Relating-Up integration. The most outstanding results within each group are highlighted in bold. Our experiments reveal that Relating-Up consistently boosts the performance of GNN backbones across diverse datasets. Additionally, we have also evaluated Relating-Up using the OGBG-MOLHIV dataset. As shown in Table 2, the results demonstrate significant improvements in ROC-AUC scores with the integration of Relating-Up. These improvements underscore the efficacy of the Relating-Up module in enhancing the predictive performance of GNN backbones on a challenging dataset."

Empirical Exploration. As shown in Figure 3 and 4, the embedding distribution learned by the Relating-Up is more compact in the same class and more separated in different classes. This enhancement results from the ability to link and integrate relationships across graphs, an aspect often neglect in standard GNN architectures. Overall, these results reinforce the effectiveness of Relating-Up module and highlight the versatility and robustness of Relating-Up as a valuable enhancement to graph representation learning.

Advanced Pooling Methods. Additionally, as presented in Table 3, Relating-Up demonstrates consistent improvements across various datasets with advanced pooling methods. In the bioinformatics domain, the average performance boost is 2.53±1.57% across all pooling methods, with individual improvements of 2.66±1.42% for DiffPool, 2.04±2.05% for GAPool, and 0.90±1.20% for SAGPool. This highlights its potential to significantly impact graph pooling scenarios, with a slightly more pronounced effect on pooling methods compared to the underlying GNN backbones. In social domain datasets, the average performance increase across pooling methods is 1.83±1.04%, with individual improvements of 2.2±0.68% for DiffPool, 1.69±1.58% for GAPool, and 1.59±1.05% for SAGPool.

Other Competitive Methods. The experimental results detailed in Table 5 demonstrate that Relating-Up exhibits competitive performance compared to other methods that claim to incorporate inter-graph relationships.

Hyperparameter Sensitivity. To balance the feedback training strategy, three hyper-parameters $\alpha$, $\beta$, and $T$ are introduced. Through the experiments detailed in Figure S1, we find out that these hyperparameters have impacts on the performance.

Batch Size. We examines the Relating-Up response to varying batch size in GNN architectures, as detailed in Table S3. The results indicate Relating-Up are not significantly hindered by the variations in batch size.

Time Efficiency. Our computational efficiency study detailed in Appendix D reveal that while our module introduces additional computational steps, the overall increase in processing time is marginal compared to the significant performance gains achieved.

To further evaluate the effectiveness of proposed Relating-Up, we compare it against other graph representation learning paradigms. The comparison includes GraphAug, Mixup for graph, GraphCL, and MVGRL. These methods represent a diverse set of strategies for enhancing graph representation learning. The experimental results are shown in the Table 4. It can been seen from the experiments results that Relating-Up consistently outperforms these methods that require an predefined relationships. We attributed this improvement to the dynamic understanding inter-graph relationships of Relating-Up.

The feedback training strategy entails dual-focused training: firstly on the original graph representations, and secondly on the relation-aware representations distilled from inter-graph relationships. Our experimental setup included three variations: (A1) a GNN module implementing Relating-Up without feedback training strategy; A GNN model with Relating-Up but (A2) remove $\mathcal{L}_{distill}$, and (A3) remove $\mathcal{L}_{hint}$. The experimental results, detailed in Table 6, showed an intriguing trend. The standalone implementation of relation-aware representation (A1) did not surpass baseline modules in performance, which emphasizes the importance of the feedback training strategy in the Relating-Up framework. The results demonstrate that effective integration and utilization of insights from inter-graph relationships hinge on a complete feedback training strategy.