Factorizable Graph Convolutional Networks

Introduction

Disentangling aims to factorize an entity, like a feature vector, into several interpretable components, so that the behavior of a learning model can be better understood. In recent years, many approaches have been proposed towards tackling disentangling in deep neural networks and have achieved promising results. Most prior efforts, however, have been focused on the disentanglement of convolutional neural network (CNN) especially the auto-encoder architecture, where disentangling takes place during the stage of latent feature generation. For example, VAE (Kingma and Welling, 2014) restrains the distribution of the latent features to Gaussian and generates disentangled representation; $\beta$-VAE (Higgins et al., 2017) further improves the disentangling by introducing $\beta$ to balance the independence constraints and reconstruction accuracy.

Despite the many prior efforts in CNN disentangling, there are few endeavors toward disentangling in the irregular structural domain, where graph convolutional network (GCN) models are applied. Meanwhile, the inherent differences between grid-like data and structural data precludes applying CNN-based disentangling methods to GCN ones. The works of (Ma et al., 2019a; Liu et al., 2019), as pioneering attempts, focus on the node-level neighbour partition and ignore the latent multi-relations among nodes.

We introduce in this paper a novel GCN, that aims to explicitly conduct graph-level disentangling, based on which convolutional features are aggregated. Our approach, termed as factorizable graph convolutional network (FactorGCN), takes as input a simple graph, and decomposes it into several factor graphs, each of which corresponds to a disentangled and interpretable relation space, as shown in Fig. 1. Each such graph then undergoes a GCN, tailored to aggregate features only from one disentangled latent space, followed by a merging operation that concatenates all derived features from disentangled spaces, so as to produce the final block-wise interpretable features. These steps constitute one layer of the proposed FactorGCN. As the output graph with updated features share the identical topology as input, nothing prevents us from stacking a number of layers to disentangle the input data at different levels, yielding a hierarchical disentanglement with various numbers of factor graph at different levels.

FactorGCN, therefore, potentially finds application in a wide spectrum of scenarios. In many real-world graphs, multiple heterogeneous relations between nodes are mixed and collapsed to one single edge. In the case of social networks, two people may be friends, colleagues, and living in the same city simultaneously, but linked via one single edge that omits such interconnections; in the co-purchasing scenario (McAuley et al., 2015), products are bought together for different reasons like promotion, and functional complementary, but are often ignored in the graph construction. FactorGCN would, in these cases, deliver a disentangled and interpretable solution towards explaining the underlying rationale, and provide discriminant learned features for the target task.

Specifically, the contributions of FactorGCN are summarized as follows.

Graph-level Disentangling. FactorGCN conducts disentangling and produces block-wise interpretable node features by analyzing the whole graph all at once, during which process the global-level topological semantics, such as the higher-order relations between edges and nodes, is explicitly accounted for. The disentangled factor graphs reveal latent-relation specific interconnections between the entities of interests, and yield interpretable features that benefit the downstream tasks. This scheme therefore contrasts to the prior approaches of (Ma et al., 2019a; Liu et al., 2019), where the disentanglement takes place only within a local neighborhood, without accounting for global contexts.

Multi-relation Disentangling. Unlike prior methods that decode only a single attribute for a neighboring node, FactorGCN enables multi-relation disentangling, meaning that the center node may aggregate information from a neighbour under multiple types of relations. This mechanism is crucial since real-world data may contain various relations among the same pair of entities. In the case of a social network graph, for example, FactorGCN would produce disentangled results allowing for two users to be both friends and living in the same city; such multi-relation disentangling is not supported by prior GCN methods.

Quantitative Evaluation Metric. Existing quantitative evaluation methods (Eastwood and Williams, 2018; Burgess et al., 2018) in the grid domain rely on generative models, like auto-encoder (Kim and Mnih, 2018) or GAN (Chen et al., 2016). Yet in the irregular domain, unfortunately, state-of-the-art graph generative models are only applicable for generating small graphs or larger ones without features. Moreover, these models comprise a sequential generation step, making it infeasible to be integrated into the graph disentangling frameworks. To this end, we propose a graph edit-distance based metric, which bypasses the generation step and estimates the similarity between the factor graphs and the ground truth.

We conducted experiments on five datasets in various domains, and demonstrate that the proposed FactorGCN yields state-of-the-art performances for both disentanglement and downstream tasks. This indicates that, even putting side its disentangling capability, FactorGCN may well serve as a general GCN framework. Specifically, on the ZINC dataset (Jin et al., 2018), FactorGCN outperforms other methods by a large margin, and, without the bond information of the edges, FactorGCN achieves a performance on par with the state-of-the-art method that explicitly utilizes edge-type information.

Related Work

Disentangled representation learning. Learning disentangled representations has recently emerged as a significant task towards interpretable AI (Yang et al., 2020a; Song et al., 2020). Unlike earlier attempts that rely on handcrafted disentangled representations or variables (Wang et al., 2014, 2016), most of the recent works in disentangled representation learning are based on the architecture of auto-encoder (Higgins et al., 2017; Feng et al., 2018; Bouchacourt et al., 2018; Burgess et al., 2018; Wang et al., 2017; Kim and Mnih, 2018) or generative model (Chen et al., 2016; Zhao et al., 2017; Siddharth et al., 2017). One mainstream auto-encoder approach is to constrain the latent feature generated from the encoder to make it independent in each dimension. For example, VAE (Kingma and Welling, 2014) constrains the distribution of the latent features to Gaussian; $\beta$-VAE(Higgins et al., 2017) enlarges the weight of the KL divergence term to balance the independence constraints and reconstruction accuracy; (Schmidhuber, 1992) disentangles the latent features by ensuring that each block of latent features cannot be predicted from the rest; DSD (Feng et al., 2018) swaps some of the latent features twice to achieve semi-supervised disentanglement. For the generative model, extra information is introduced during the generation. For example, InfoGAN (Chen et al., 2016) adds the class code to the model and maximizes the mutual information between the generated data and the class code.

Graph convolutional network. Graph convolutional network (GCN) has shown its potential in the non-grid domain (Xu et al., 2018; Qiu et al., 2020; Li et al., 2018; Yang et al., 2020b; Monti et al., 2017; Yang et al., 2019), achieving promising results on various type of structural data, like citation graph (Veličković et al., 2018), social graph (Kipf and Welling, 2017), and relational graph (Schlichtkrull et al., 2018). Besides designing GCN to better extract information from non-grid data, there are also a couple of works that explore the disentangled GCNs (Ma et al., 2019b; Liu et al., 2019). DisenGCN (Ma et al., 2019a) adopts neighbour routine to divide the neighbours of the node into several mutually exclusive parts. IPGDN (Liu et al., 2019) improves DisenGCN by making the different parts of the embedded feature independent. Despite results of the previous works, there remain still several problems: the disentanglement is in the node level, which does not consider the information of the whole graph, and there is no quantitative metrics to evaluate the performance of disentanglement.

Method

In this section, we will give a detailed description about the architecture of FactorGCN, whose basic component is the disentangle layer, as shown in Fig. 1.

The goal of this step is to factorize the input graph into several factor graphs. To this end, we treat the edges equally across the whole graph. The mechanism we adopt to generate these factorized coefficient is similar to that of graph attention network (Veličković et al., 2018). We denote the input of the disentangle layer as $\mathbf{h}=\{h_{0},h_{1},...,h_{n}\},h_{i}\in\mathcal{R}^{F}$ and $\mathbf{e}=\{e_{0},e_{1},...,e_{m}\},e_{k}=(h_{i},h_{j})$. $\mathbf{h}$ denotes the set of nodes with feature of $F$ dimension, and $\mathbf{e}$ denotes the set of edges.

The input nodes are transformed to a new space, done by multiplying the features of nodes with a linear transformation matrix $\mathbf{W}\in\mathcal{R}^{F^{\prime}\times F}$. This is a standard operation in most GCN models, which increases the capacity of the model. The transformed features are then used to generate the factor coefficients as follows

where $\Psi_{e}$ is the function that takes the features of node $i$ and node $j$ as input and computes the attention score of the edge for factor graph $e$, and takes the form of an one-layer MLP in our implementation; $E_{ije}$ then can be obtained by normalizing the attention score to $$, representing the coefficient of edge from node$i$to node$j$in the factor graph$e$;$h^{\prime}$is the transformed node feature, shared across all functions$\Psi_{*}$. Different from most previous forms of attention-based GCNs that normalize the attention coefficients among all the neighbours of nodes, our proposed model generates these coefficients directly as the factor graph.

Once all the coefficients are computed, a factor graph $e$ can be represented by its own $E_{e}$, which will be used for the next aggregation step. However, without any other constrain, some of the generated factor graphs may contain a similar structure, degrading the disentanglement performance and capacity of the model. We therefore introduce an additional head in the disentangle layer, aiming to avoid the degradation of the generated factor graphs.

The motivation of the additional head is that, a well disentangled factor graph should have enough information to be distinguished from the rest, only based on its structure. Obtaining the solution that all the disentangled factor graphs differ from each other to the maximal degree, unfortunately, is not trivial. We thus approximate the solution by giving unique labels to the factor graphs and optimizing the factor graphs as a graph classification problem. Our additional head will serve as a discriminator, shown in Eq. 2, to distinguish which label a given graph has:

The discriminator contains a three-layer graph auto-encoder $\mathcal{A}$, which takes the transformed feature $\mathbf{h^{\prime}}$ and the generated attention coefficients of factor graph $\mathbf{E}_{e}$ as inputs, and generates the new node features. These features are then readout to generate the representation of the whole factor graph. Next, the feature vectors will be sent to a classifier with one fully connected layer. Note that all the factor graphs share the same node features, making sure that the information discovered by the discriminator only comes from the difference among the structure of the factor graphs. More details about the discriminator architecture can be found in the supplementary materials.

The loss used to train the discriminator is taken as follows:

2 Aggregation Step

As the factor graphs derived from the disentangling step is optimized to be as diverse as possible, in the aggregation step, we will use the generated factor graphs to aggregate information in different structural spaces.

This step is similar as the most GCN models, where the new node feature is generated by taking the weighted sum of its neighbors. Our aggregation mechanism is based on the simplest one, which is used in GCN (Kipf and Welling, 2017). The only difference is that the aggregation will take place independently for each of the factor graphs.

where $h^{(l+1)_{e}}_{i}$ represents the new feature for node $i$ in $l+1$ layer aggregated from the factor graph $e$; $\mathcal{N}_{i}$ represents all the neighbours of node $i$ in the input graph; $E_{ije}$ is the coefficient of the edge from node $i$ to node $j$ in the factor graph $e$; $c_{ij}$ is the normalization term that is computed according to the degree of node $i$ and node $j$; $\mathbf{W}^{(l)}$ is a linear transformation matrix, which is the same as the matrix used in the disentangling step.

Note that although we use all the neighbours of a node in the input graph to aggregate information, some of them are making no contribution if the corresponding coefficient in the factor graph is zero.

3 Merging Step

Once the aggregation step is complete, different factor graphs will lead to different features of nodes. We merge these features generated from different factor graphs by applying

where $h^{(l+1)}_{i}$ is the output feature of node $i$; $N_{e}$ is the number of factor graphs; $||$ represents the concatenation operation.

4 Architecture

We discuss above the design of one disentangle layer, which contains three steps. The FactorGCN model we used in the experimental section contains several such disentangle layers, increasing the power of expression. Moreover, by setting different number of factor graphs in different layers, the proposed model can disentangle the input data in a hierarchical manner.

The total loss to train FactorGCN model is $\mathcal{L}=\mathcal{L}_{t}+\lambda*\mathcal{L}_{d}$. $\mathcal{L}_{t}$ is the loss of the original task, which is taken to be a binary cross entropy loss for multi-label classification task, cross entropy loss for multi-class classification task, or L1 loss for regression task. $\mathcal{L}_{d}$ is the loss of the discriminator we mentioned above. $\lambda$ is the weight to balance these two losses.

Experiments

In this section, we show the effectiveness of the proposed FactorGCN, and provide discussions on its various components as well as the sensitivity with respect to the key hyper-parameters. More results can be found in the supplementary materials.

Datasets. Here, we use six datasets to evaluate the effectiveness of the proposed method. The first one is a synthetic dataset that contains a fixed number of predefined graphs as factor graphs. The second one is the ZINC dataset (Dwivedi et al., 2020) built from molecular graphs. The third one is Pattern dataset (Dwivedi et al., 2020), which is a large scale dataset for node classification task. The other three are widely used graph classification datasets include social networks (COLLAB,IMDB-B) and bioinformatics graph (MUTAG) (Yanardag and Vishwanathan, 2015). To generate the synthetic dataset that contains $N_{e}$ factor graphs, we first generate $N_{e}$ predefined graphs, which are the well-known graphs like Turán graph, house-x graph, and balanced-tree graph. We then choose half of them and pad them with isolated nodes to make the number of nodes to be 15. The padded graphs will be merged together as a training sample. The label of the synthetic data is a binary vector, with the dimension $N_{e}$. Half of the labels will be set to one according to the types of graphs that the sample generated from, and the rest are set to zero. More information about the datasets can be found in the supplemental materials.

Baselines. We adopt several methods, including state-of-the-art ones, as the baselines. Among all, MLP is the simplest one, which contains multiple fully connected layers. Although this method is simple, it can in fact perform well when comparing with other methods that consider the structural information. We use MLP to check whether the other compared methods benefit from using the structural information as well. GCN aggregates the information in the graph according to the laplacian matrix of the graph, which can be seen as a fixed weighted sum on the neighbours of a node. GAT (Veličković et al., 2018) extends the idea of GCN by introducing the attention mechanism. The weights when doing the aggregation is computed dynamically according to all the neighbours. For the ZINC dataset, we also add MoNet (Monti et al., 2017) and GatedGCNE (Dwivedi et al., 2020) as baselines. The former one is the state-of-the-art method that does not use the type information of edges while the latter one is the state-of-the-art one that uses additional edge information. Random method is also added to provide the result of random guess for reference. For the other three graph datasets, we add non DL-based methods (WL subtree, PATCHYSAN, AWL) and DL-based methods (GCN, GraphSage (Hamilton et al., 2017), GIN) as baselines. DisenGCN (Ma et al., 2019a) and IPDGN (Liu et al., 2019) are also added.

Hyper-parameters. For the synthetic dataset, Adam optimizer is used with a learning rate of 0.005, the number of training epochs is set to 80, the weight decay is set to 5e-5. The row of the adjacent matrix of the generated synthetic graph is used as the feature of nodes. The negative slope of LeakyReLU for GAT model is set to 0.2, which is the same as the original setting. The number of hidden layers for all models is set to two. The dimension of the hidden feature is set to 32 when the number of factor graphs is no more than four and 64 otherwise. The weight for the loss of discriminator in FactorGCN is set to 0.5.

For the molecular dataset, the dimension of the hidden feature is set to 144 for all methods and the number of layers is set to four. Adam optimizer is used with a learning rate of 0.002. No weight decay is used. $\lambda$ of FactorGCN is set to 0.2. All the methods are trained for 500 epochs. The test results are obtained using the model with the best performance on validation set. For the other three datasets, three layers FactorGCN is used.

2 Qualitative Evaluation

We first provide the qualitative evaluations of disentanglement performance, including the visualization of the disentangled factor graphs and the correlation analysis of the latent features.

Visualization of disentangled factor graphs. To give an intuitive understanding of the disentanglement. We provide in Fig. 2 some examples of the generated factor graphs. We remove the isolated nodes and visualize the best-matched factor graphs with ground truths. More results and analyses can be found in the supplemental materials.

Correlation of disentangled features. Fig. 3 shows the correlation analysis of the latent features obtained from several pre-trained models on the synthetic dataset. It can be seen that also GCN and MLP models can achieve a high performance in the downstream task, and their latent features are hidden entangled. GAT gives more independent latent features but the performance is degraded in the original task. FactorGCN is able to extract the highly independent latent features and meanwhile achieve a better performance in the downstream task.

3 Quantitative Evaluation

The quantitative evaluation focuses on two parts, the performance of the downstream tasks and that of the disentanglement.

Evaluation protocol. For the downstream tasks, we adopt the corresponding metrics to evaluate, i.e., Micro-F1 for the multi-label classification task, mean absolute error (MAE) for the regression task. We design two new metrics to evaluate the disentanglement performance on the graph data. The first one is graph edit distance on edge (GEDE). This metric is inspired by the traditional graph edit distance (GED). Since the input graph already provides the information about the order of nodes, the disentanglement of the input data, in reality, only involves the changing of edges. Therefore, we restrict the GED by only allowing adding and removing the edges, and thus obtain a score of GEDE by Hungarian match between the generated factor graphs and the ground truth.

Specifically, for each pair of the generated factor graph and the ground truth graph, we first convert the continuous value in the factor graph to 1/0 value by setting the threshold to make the number of edges in these two graphs are the same. Then, GEDEs can be computed for every such combination. Finally, Hungarian match is adopted to obtain the best bipartite matching results as the GEDE score.

Besides the GEDE score, we also care about the consistency of the generated factor graph. In other words, the best-matched pairs between the generated factor graphs and the ground truths, optimally, should be identical across all samples. We therefore introduce the second metric named as consistency score (C-Score), related to GEDE. C-Score is computed as the average percentage of the most frequently matched factor graphs. The C-score will be one if the ground truth graphs are always matched to the fixed factor graphs. A more detailed description of evaluation protocol can be found in the supplemental materials.

Evaluation on the synthetic dataset. We first evaluate the disentanglement performance on a synthetic dataset. The results are shown in Tab. 1. Although MLP and GCN achieve good classification performances, they are not capable of disentanglement. GAT disentangles the input by using multi-head attention, but the performance of the original task is degraded. Our proposed method, on the other hand, achieves a much better performance in terms of both disentanglement and the original task. We also evaluate the compared methods on the synthetic dataset with various numbers of factor graphs, shown in Tab. 2. As the number of latent factor graphs increase, the performance gain of the FactorGCN becomes large. However, when the number of factor graphs becomes too large, the task will be more challenging, yielding lower performance gains.

Evaluation on the ZINC dataset. For this dataset, the type information of edges is hidden during the training process, and is serve as the ground truth to evaluate the performance of disentanglement. Tab. 3 shows the results. The proposed method achieves the best performance on both the disentanglement and the downstream task. We also show the state-of-the-art method GatedGCNE on this dataset on the right side of Tab. 3, which utilizes the type information of edges during the training process. Our proposed method, without any additional edge information, achieves truly promising results that are to that of GatedGCNE, which needs the bond information of edges during training.

Evaluation on more datasets. To provide a thorough understanding of the proposed method, We also carry out evaluations on three widely used graph classification datasets and one node classification dataset to see the performances of FactorGCN as a general GCN framework. The same 10-fold evaluation protocol as (Xu et al., 2018) is adopted. Since there are no ground truth factor graphs, we only report the accuracy, shown in Tab. 4 and Tab. 5. Our method achieves consistently the best performance, showing the potential of the FactorGCN as a general GCN framework, even putting aside its disentangling capability. More details about the evaluation protocol, the setup of our method, and the statistic information about these datasets can be found in the supplemental materials.

4 Ablation and sensitivity analysis

We show in Fig. 4 the ablation study and sensitivity analysis of the proposed method. When varying $\lambda$, the number of factors is set to be eight; when varying the number of factors , $\lambda$ is set to be 0.2. As can be seen from the left figure, the performance of both the disentanglement and the downstream task will degrade without the discriminator. The right figure shows the relations between the performance and the number of factor graphs we used in FactorGCN. Setting the number of factor graphs to be slightly larger than that of the ground truth, in practice, leads to a better performance.

Conclusion

We propose a novel GCN framework, termed as FactorGCN, which achieves graph convolution through graph-level disentangling. Given an input graph, FactorGCN decomposes it into several interpretable factor graphs, each of which denotes an underlying interconnections between entities, and then carries out topology-aware convolutions on each such factor graph to produce the final node features. The node features, derived under the explicit disentangling, are therefore block-wise explainable and beneficial to the downstream tasks. Specifically, FactorGCN enables multi-relation disentangling, allowing information propagation between two nodes to take places in disjoint spaces. We also introduce two new metrics to measure the graph disentanglement performance quantitatively. FactorGCN outperforms other methods on both the disentanglement and the downstream tasks, indicating the proposed method is ready to serve as a general GCN framework with the capability of graph-level disentanglement.

Acknowledgments

This work is supported by the startup funding of Stevens Institute of Technology.

Broader Impact

In this work we introduce a GCN framework, termed as FactorGCN, that explicitly accounts for disentanglement FactorGCN is applicable to various scenarios, both technical and social. For conventional graph-related tasks, like node classification of the social network and graph classification of the molecular graph, our proposed method can serve as a general GCN framework. For disentangling tasks, our method generates factor graphs that reveal the latent relations among entities, and facilitate the further decision making process like recommendation. Furthermore, given sufficient data, FactorGCN can be used as a tool to analyze social issues like discovering the reasons for the quick spread of the epidemic disease in some areas. Like all learning-based methods, FactorGCN is not free of errors. If the produced disentangled factor graphs are incorrect, for example, the subsequent inference and prediction results will be downgraded, possibly yielding undesirable bias.

References