A Causal Disentangled Multi-Granularity Graph Classification Method

To obtain continuous low-dimensional embedding, graph representation learning aims to map non-Euclidean data into a low-dimensional representation space. For graph classification, there are two categories of research methods. One category is similarity-based graph classification methods, including graph kernel methods and graph matching methods. However, these methods are often inflexible and computationally expensive. In these methods, the process of graph feature extraction and graph classification is independent, which limits optimization for specific tasks. The other category is based on GNNs. When applied to graph classification problems, GCN [11] and GAT [20] perform graph classification through convolution and pooling operations. Pooling is the process of graph coarsening, where the operation progressively aggregates fine-grained nodes. Subsequent research has also introduced changes to the pooling operation. For example, SAT [2] proposes a graph transformer method used in pooling.

The idea of disentangling initially originated from Bengio et al. [1] and is primarily focused on computer vision [9]. However, some researchers have extended this concept to graphs. DisenGCN model [15] introduces a neighborhood routing mechanism to disentangle the various latent factors behind interactions in the graph. The IPGDN model [12], based on DisenGCN, add the Hilbert Schmidt Independence Criterion (HSIC) to further enhance the independence between different modules. Based on the routing mechanism, the authors demonstrate the user-item relationship at the granularity of user intent and disentangle these intents in the representations of users and items [22]. However, this method mainly focuses on bipartite graphs and may not be suitable for more complex graph structures. It lacks scalability. In the context of knowledge graphs with richer types of relationships, some works consider leveraging relationship information in the process of disentangled representation learning. For example, they guide the disentangled representation of entity nodes based on the semantics of relationships [24]. However, these methods overlook the information from different types of relationship edges. These studies have successfully achieved disentangled. But, their primary emphasis is on manipulating the intermediate hidden layer states, which poses challenges in comprehending the structure of the graph. Consequently, their interpretability from a human perspective is limited.

Despite the excellent representation capability of GNN models, their learning process is often opaque and difficult for humans to understand. To address this issue, some researchers have proposed post-hoc methods for explaining. GNNExplainer model [23] learns masks for the adjacency matrix and node features to identify important substructures. The PGExplainer model [14] attempts to learn an MLP function to mask edges in the graph, incorporating sparsity and continuity constraints in the model to obtain the final explanations. The post-hoc methods for explaining can only understand the model, not adjust the model. Another category of GNN explanation methods involves constructing self-explainable GNNs. Compared with post-hoc methods, this kind of model not only provides predictions but also offers explanations for the reasons behind those predictions. It can guide the model to some extent. Some self-explainable models require prior knowledge. For example, KerGNNs [6] is a subgraph-based node aggregation algorithm that manually constructs graph kernel functions to compare the similarity between graph filters and input subgraphs. The trained graph filters are also visualized and used as the model’s explanation, which is then integrated into the GNN. In addition to explaining isomorphic GNN models, researchers have also explored self-explainable models for heterogeneous GNN models, such as Knowledge Router [3]. However, these self-explainable GNNs have not extensively considered the issue of the multi-granularity structure of graphs.

Let $G=\left(V,E\right)$ be a graph, where $V$ is the node set, and $E$ is the edge set. The $A\in\left\{0,1\right\}^{\left|N\right|\times\left|N\right|}$ is defined as the adjacency matrix of graph $G$. If there is an edge between node $i$ and node $j$, the $A_{ij}=1$; otherwise,$A_{ij}=0$. The $X$ is defined as the features matrix. $X\in R^{\left|V\right|\times F}$ represents the features of each node, where $F$ denotes the feature dimension for each node. The neighbour of node $i$ is $N_{i}$. The true label set is $Y$.

We analyze this problem using the Structural Causal Model (SCM). Figure 1 illustrates the five components. Z: input graph data, Y: labels, B: bias part in the graph, C: important substructures, and E: learned embedding by GNN model.

$C\to Z\leftarrow B$: Z is composed of B and C.

$C\to Z\to E\to Y$: The structure of C is learned through GNNs and represented as E. Then, establish a causal correlation between C and Y.

$B\to Z\to E\to Y$: Due to the confusion between B and C, it affects the representation E obtained from GNNs, which also impacts the prediction of Y. Consequently, a spurious correlation is formed, leading to misleading predictions.

Based on the multi-granularity characteristics of graph data, this paper first considers modeling the nodes at a fine-grained level to capture the closeness between nodes, forming a mask matrix.

Given a graph $G$, the attention values are calculated based on the feature similarity between node $i$ and node $j$ from a fine-grained perspective.

where $W_{feat}$ is the learnable parameters. Then the calculated attention values are normalized.

At the fine-grained level, we calculate the interaction between the structures of node $i$ and $j$ and use $Stru$ as the attention value of the topological structure to describe the relationship between nodes.

Here, We use restart random walks to describe the degree of structural similarity between the center node $i$ and other nodes $p$. Particles start from the center node $i$ and randomly walk to their neighbors $p$ and $p\in N_{i}$. At each step, there is a certain probability of returning to the center node $i$. After $t$ iterations, the probability vector of visiting the neighbors around node $i$ is obtained.

where $\tilde{A}=D^{-0.5}AD^{-0.5}$ and $D$ is the degree matrix. $q$ is the probability of restarting the random walk. $vec_{i}$ is a one-hot vector where the center node $i$ is assigned 1. Others are assigned 0.

The probability vector is proportional to the edge weights. The higher the probability, the larger the edge weight. This probability vector is used as the weight vector. When $t\to\infty$, the vector converges to the following equation:

In Equation (3), $\omega_{ip}$ represents the weight of node $p$ ($p\in N{i}$). After normalizing $Stru_{ij}$, we obtain the following expression:

We integrate $e_{ij}$ and $Stru_{ij}$ to obtain $M_{ij}$, resulting in the formation of matrix $M$:

At a fine-grained level, this paper describes the closeness between each node from its features and structure. And it fuses them to form a mask. The mask part is an important substructure, while others are the bias parts.

Firstly, at a fine-grained level, the features are subjected to a simple feature transformation using the $f_{\theta}$ function with the learnable parameters $\theta$.

where the $f_{\theta}$ is a multi-layer neural network with $\theta$.

Next, the transformed features, fine-grained closeness mask, and adjacency matrices of different orders are sent into slice layers. The modeling process starts with the important substructures.

In the important substructures, the $M$ matrix is constructed in each slice GNN layer following the approach described in the previous section. In the first layer, $M_{1}$ and $\tilde{A}$ are used, in the second layer, the $M_{2}$ and $\tilde{A}^{2}$ are used, and in the third layer, the $M_{3}$ and $\tilde{A}^{3}$ are used. These matrices are then inputted into their corresponding slice layers to obtain the hidden layer states $h_{1}$, $h_{2}$, and $h_{3}$, and $W_{1}$,$W_{2}$, and $W_{3}$ are learnable parameters.

The CDM-GNN model stacks the transformed feature results and obtained hidden layer states:

This model adaptive learns the weight $S$ for each slice layer:

For the graph $G_{k}$, this model performs pooling on the obtained embedding to obtain the representation of $Emb_{k}$:

For bias parts, the CDM-GNN obtains the status of hidden layer $\overline{h_{1}}$, $\overline{h_{2}}$, and $\overline{h_{3}}$. In this model, we share these learnable parameters $W_{1}$,$W_{2}$, and $W_{3}$.

Similarly, this model stacks the transformed feature results and obtained hidden layer states:

Then, the CDM-GNN model adaptive learns the weight $\overline{S}$ of each slice layer and gets the final embedding $\overline{Emb}_{k}$:

This paper aims to train $K$ graphs by the causal components of their representations to enable the CDM-GNN model to classify correctly. To achieve this, CDM-GNN employs the supervised classification cross-entropy loss as follows:

For the representation of bias parts, it should not affect the classification results. Therefore, the prediction results of the bias parts should be evenly distributed across all categories. Using uniform distribution to help learn the representation of bias parts as follows:

where $KL$ means the KL-Divergence, $Y_{unif}$ denotes the uniform distribution.

In order to reduce the interference of bias parts, the representation of bias parts is recombined with the causal parts to construct intervention terms. The CDM-GNN redefines the $\oplus$ function. It adds the bias representation of random disturbance back to the corresponding positions of the causal part representation to obtain the constructed intervention term $E_{k}^{int}$:

In this case, the CDM-GNN can get the correct classification results by the representation of the causal part. The loss function is as follows:

The overall loss function is as follows:

where $\alpha$, $\beta$, and $\gamma$ are hyper-parameters that determine the strength of disentanglement and causal influences.

The commonly-used datasets for graph classification are summarized in Table 1.

• $\bullet$

  MUTAG [4]: This dataset contains 188 compounds marked according to whether it has a mutagenic effect on a bacterium.

• $\bullet$

  PTC [19]: This dataset contains 344 organic molecules marked according to their carcinogenicity on male mice.

• $\bullet$

  IMDB-M [17]: This dataset is a movie collaboration dataset marked according to the genre an ego-network belongs to (romance, action, and science).

This paper compares the proposed CDM-GNN model with several state-of-the-art methods, which are summarized as follows:

• $\bullet$

  GCN [11]: It is a semi-supervised graph convolution network model for graph embedding.

• $\bullet$

  GAT [20]: It is a graph neural network model which employs an attention mechanism to obtain graph representations.

• $\bullet$

  Top-K [7]: It is a graph representation method that adaptively selects some critical nodes to form smaller subgraphs based on their importance vectors.

• $\bullet$

  ASAPool [16]: It is a graph neural network model that utilizes attention mechanisms to capture the importance of nodes and pools subgraphs into a coarse graph through learnable sparse soft clustering allocation for graph representation.

• $\bullet$

  SUGAR [18]: It is a graph representation method that first samples some subgraphs. And then it uses the DQN algorithm to select top-k key subgraphs as representative abstractions of the entire graph.

• $\bullet$

  SAT [2]: It is a graph transformer method that incorporates the structure explicitly. Before calculating attention, it fuses structural information into the original self-attention by extracting k-hop subgraphs or k-subtrees on each node.

In the graph classification task, this paper adopts accuracy as the evaluation metric to measure the performance of different models.

From Table 2, it can be observed that the proposed CDM-GNN model achieves the best graph classification results on the MUTAG, PTC, and IMDB-M datasets. Specifically, compared with the GCN and GAT, the CDM-GNN has an improvement of about 5$\%$ on the MUTAG dataset in terms of graph classification accuracy. Compared to Top-K and ASAPool, which are specifically designed for pooling operations, CDM-GNN demonstrates improvements ranging from 12$\%$ to 20$\%$. In comparison to methods focusing on substructure extraction, SUGAR and SAT, CDM-GNN shows improvements of 3$\%$ to 7$\%$. On the PTC dataset, the CDM-GNN also shows a notable improvement and achieves accurate graph classification. On the multi-class IMDB-M dataset, the proposed CDM-GNN achieves about 5.4$\%$ improvement over GCN and GAT. When compared to some pooling methods, CDM-GNN shows accuracy improvements ranging from 5.5$\%$ to 15$\%$. In the substructure research, CDM-GNN demonstrates accuracy improvements of 4$\%$ to 9$\%$. These results highlight the superior graph classification performance of the CDM-GNN model across different datasets. It surpasses other popular models and specialized approaches for pooling or subgraph analysis.

To demonstrate the interpretability of the CDM-GNN method, this paper conducts a qualitative analysis. According to the existing chemical knowledge, people know that the MUTAG dataset determines whether it has a mutagenic effect by judging whether the molecule contains the substructure of $NO_{2}$ or $NH_{2}$. Therefore, this paper visualizes the MUTAG dataset to observe the interpretability of the CDM-GNN model and perform qualitative analysis. If CDM-GNN model can recognize the important substructure $NO_{2}$ and disentangle this part with bias parts, then it indicates that the model has better interpretability. This model can obtain classification and interpretation results that are consistent with human cognition and prior knowledge.

In this study, the edges of the graph are colored based on the values of the mask, where darker colors indicate greater importance. In the visualized results, we can observe that the edges of important substructures $NO_{2}$ are colored darker, indicating their higher weights and greater significance in the classification of the MUTAG dataset. The edges connecting the important substructures $NO_{2}$ and the bias parts are colored lighter, indicating that the CDM-GNN model has successfully disentangled the important substructures from the bias parts. From Figure 3 (a)(b)(d)(e), it can be observed that regardless of whether the graph contains one or multiple $NO_{2}$ substructures, the CDM-GNN can recognize them and successfully disentangle them from the carbon rings. Even in cases where there are multiple carbon rings in the graph, like Figure 3 (c)(f), the CDM-GNN model can still identify the important $NO_{2}$ parts. This indicates the model has the ability to capture and distinguish the relevant features, enabling it to recognize and disentangle the important $NO_{2}$ parts from other structural components.

Here, this paper discusses the role of three losses in learning for the CDM-GNN model. From Figure 4, It can be observed that when this model only uses the $L_{KL}$, $L_{int}$, and $L_{pred}$, the $L_{pred}$ plays a more important role in this model training. The CDM-GNN model is designed by incorporating downstream graph classification tasks. The $L_{pred}$ plays a leading role in guiding this model to achieve better differentiation among different categories of graph data. This way, the CDM-GNN model focuses on the goal of graph classification and progressively improves its performance. The $L_{KL}$ is mainly aimed at reducing the interference caused by the bias component. Without this loss, the classification results are the most significant decrease in accuracy. The $L_{int}$ is to consider the decoupling of causality. If the CDM-GNN model is without $L_{int}$, it also leads to a decrease in accuracy. When three losses are used together, the model can achieve the best effect. It has better graph classification results and can separate the important substructure and the bias parts.