Disentangled Generative Graph Representation Learning

Q1: Computation Comleaxity

Grateful for your comments. We will expand the discussion on complexity and scalability in our revisions, focusing on the following three aspects:

1. Complexity Analysis: We discussed the network's complexity in Section 3.4 and will later compare the time and space complexity of additional models to demonstrate that DiGGR is comparable to previous work in terms of complexity.

2. Empirical Results: we compared DiGGR and SeeGera [1] on the Cora dataset. All experiments were conducted on an RTX 3090, with all the models adhering to their default settings, and perform a single run with the same random seed and the same Pytorch platform.

The experimental results indicate that our model has lower training time and resource consumption compared to SeeGera. Specifically, the training time of DiGGR is nearly four times less than that of SeeGera. These results collectively demonstrate that DiGGR maintains a manageable overall complexity while achieving excellent performance.

3. Lastly, we are actively working on extending DiGGR with a focus on scaling our algorithm to extremely large graphs. We conducted additional experiments on the larger dataset ogbn-arxiv. During the reconstruction of the adjacency matrix, we used the method from [5], sampling only a portion of the matrix for computation each time. The results are as follows:

DiGGR outperforms both on the ogbn-arxiv dataset, validating our approach's effectiveness and scalability. Previous works like GraphMAE initially focused on smaller datasets, but its subsequent work, GraphMAE2, used the PPR-Nibble technique to extend to large graph data. We believe that DiGGR also has the potential for scaling to large datasets and are actively working on advancing this capability.

Q2: Theoretical Analysis

Thank you for your valuable suggestion. We would like to provide a detailed theoretical analysis as follows:

DiGGR is built on an graph autoencoder (GAE)-based framework. Recent studies [6, 7] have demonstrated a direct connection between GAE and contrastive learning through a specific form of the objective function. The loss function can be rewritten as follows:

$$L^+ = \frac{1}{|\varepsilon^+|}\sum_{(u, v) \in V^+}{\log f_{dec}(h_u, h_v)}$$ $$L^- = \frac{1}{|\varepsilon^-|}\sum_{(u', v') \in V^-}{\log (1 - f_{dec}(h_{u'}, h_{v'}))}$$ $$L_{GAE} = -(L^+ + L^-)$$

where $h_u$ and $h_v$ are the node representations of node $u$ and node $v$ obtained from an encoder $f_{enc}$ respectively (eg., a GNN); $\varepsilon^+$ is a set of positive edges while $\varepsilon^-$ is a set of negative edges sampled from graph, and $f_{dec}$ is a decoder; Typically, $\varepsilon^+ = \varepsilon$.

Building on recent advances in information-theoretic approaches to contrastive learning [8, 9], a recent study [6] suggests that for SSL pretraining to succeed in downstream tasks, task-irrelevant information must be reasonably controlled. Therefore, the following proposition is put forward:

The task irrelevant information $I(U; V| T)$ of GAE can be lower bounded with:

$$I(U; V| T) \geq \frac{(E[N_{uv}^{k}])^2}{N_k} . \gamma^2$$

minimizing the aforementioned $L_{GAE}$ is in population equivalent to maximizing the mutual information between the k-hop subgraphs of adjacent nodes, and the redundancy of GAE scales almost linearly with the size of overlapping subgraphs.

The above proposition has been proved in detailed in [6], where $I(.;.)$ is the mutual information, $U$ and $V$ be random variables of the two contrasting views, and $T$ denote the target of the downstream task. $N_{uv}^{k}$ is the size of the overlapping subgraph of $G^k(u)$ and $G^k(v)$, and the expectation is taken with respect to the generating distribution of the graph and the randomness in choosing $u$ and $v$.

According to this lower bound, we need to reduce the task-irrelevant redundancy to design a better graph SSL methods. In DiGGR, we first factorize the input graph based on latent factor learning before feeding it into the masked autoencoder. Take Figure 1 from the PDF in global rebuttal as an example. Nodes $a$ and $b$ have overlapping 1-hop subgraphs. However, after graph factorization, the connection between $a$ and $b$ is severed, thereby reducing large-scale subgraph overlap and lowering the lower bound of task-irrelevant information. As shown in Table 3 of the paper, after factorization, the latent factor groups extracted by DiGGR exhibit lower normalized mutual information (NMI), indicating reduced overlap between the latent factor groups. This result aligns with our theoretical analysis and highlights the advantages of our proposed method.

[1] Seegera: Self-supervised semi-implicit graph variational auto-encoders with masking. WWW 2023.

[2] Graphmae: Self-supervised masked graph autoencoders. KDD 2022

[3] GraphMAE2: A Decoding-Enhanced Masked Self-Supervised Graph Learner. WWW 2023

[4] Local graph partitioning using pagerank vectors. (FOCS'06). IEEE, 2006

[5] Fastgae: Scalable graph autoencoders with stochastic subgraph decoding. Neural Networks 142 (2021): 1-19

[6] What’s Behind the Mask: Understanding Masked Graph Modeling for Graph Autoencoders. KDD 2023

[7] How Mask Matters: Towards Theoretical Understandings of Masked Autoencoders. NeurIPS 2022

[8] What Makes for Good Views for Contrastive Learning?. NeurIPS 2020

[9] Self-supervised Learning from a Multi-view Perspective. ICLR 2021

W1: Novelty

Thank you for the time and effort you have dedicated to our paper. It is true that DiGGR and [1-4] use some common techniques in disentangled learning. However, we sitll believe our approach offers novelties in the following aspects:

(i)The main goal of our paper is to use disentangled learning to enhance self-supervised feature learning, rather than focusing solely on disentanglement itself. To the best of our knowledge, most current work on graph masked autoencoders (GMAE) often overlooks the disentanglement of representations in the context of node classification and graph classification tasks: When performing mask modeling, these approaches treat the entire graph as a whole and often overlook its underlying structure. For example, a node $n$ might belong to both community $A$ and community $B$, playing different roles in each. Consequently, different learning strategies should be adopted for these roles. However, most GMAE methods ignore these latent relationships and uniformly sample nodes from the entire graph for masking, disregarding the heterogeneous factors present within nodes. Therefore, we introduced disentanglement into GMAE and used a tailored probabilistic approach to improve the learned representations.

(ii) our method differs significantly from those in [1-4]. Please refer to the global rebuttal. Briefly, the main differences are as follows: (a) Our approach models the latent factor $z$ as a probability distribution rather than a variable. This differs from most prototype-based factor learning methods [1, 2, 4]. By modeling $z$ as a distribution, our method introduces randomness during network training, leading to faster convergence and more distinctive latent factors. (b) We model the latent factor using a Gamma distribution, leveraging its non-negative property to transform the factorization problem into a non-negative matrix factorization problem. This contrasts with [3], where the distribution nature prevents such a conversion. According to [5], this approach results in representations that are more disentangled and expressive.

W2：Why not other framework

What we provide in this article is a general framework method. Within the DiGGR framework, any other GNN, such as GCN, GIN, and GAT, can be used for representation learning. Additionally:

1. In graph SSL, contrastive methods dominate node and graph classification but face challenges: (a) reliance on manually constructed negative samples, (b) need for high-quality data augmentation. Graph autoencoders (GAEs) avoid these issues by directly reconstructing the input graph. Therefore, our work is based on a GAE framework.

2. Due to an overemphasis on structural information, GAEs have lagged behind contrastive learning in node and graph classification tasks. Recently, [6] demonstrated that masked autoencoders achieve performance comparable to contrastive learning in graph SSL, with [7,8] confirming this. Thus, we incorporated mask modeling into our network.

However, Graph mask modeling is not our main focus. Our goal is to use disentangling to improve self-supervised representation learning, supported by a tailored probabilistic latent factor learning method.

Questions

Q1: 1. To clarify, "other modalities" refers to graph domain. Line 21 means While MAE techniques are well-established in language and image domains, they are now gaining attention in graph learning; 2. GMAE and GNN are analogous to MAE and Transformers. GMAE employs an encoder-decoder architecture to reconstruct input graphs, it can use GNNs as either encoders or decoders.

Q2: Disentangling node latent structures has proven effective in graph representation learning [1,2]. The node latent structure sets the aspects of node information. For example, In a social network, node $n$ might represent both a student and a club member, showing different traits in each context. Thus, the ideal approach is to learn distinct node properties for each group and aggregate these to represent the node’s overall information. Such an approach has been proven effective in GNNs. For example, [3] address the issue of latent factor entanglement and show that disentangled node representations, achieved through iterative neighborhood segmentation, are effective.

Q3: We will include the full name of EPM, which is Edge Partition Model in the revision.

Q4: We use mask strategies to boost the learning capability of the GAE framework. Please see our response in W2 for details.

Q5: We have thoroughly reviewed [1-4]. Please refer to our detailed response in the global rebuttal section.

Q6: Theoretical guarantees for identifying latent groups pose challenges for both our study and graph learning filed at large. Our algorithm encourages latent group discovery only if it improves the explanation of the defined loss terms. However, it does not guarantee identifying groups that may not be relevant to specific tasks. Thus, while it identifies meaningful groups, it may overlook less impactful ones. Our algorithm does not enforce permutation invariance for the discovered latent groups. Instead, it relies on the data to determine whether such invariance is necessary for the task. This approach allows for a data-driven determination of the relevance and utility of permutation invariance in the latent groups identified by our model.

[1] Disentangled graph collaborative filtering. SIGIR 2020

[2] Disentangled Graph Convolutional Networks. ICML 2019

[3] Deep Generative Model for Periodic Graphs. NeurIPS 2022

[4] Disentangled contrastive learning on graphs. NeurIPS 2021

[5] Learning the parts of objects by non-negative matrix factorization. Nature 1999.

[6] Graphmae: Self-supervised masked graph autoencoders. KDD 2022.

[7] Seegera: Self-supervised semi-implicit graph variational auto-encoders with masking. WWW 2023.

[8] Gigamae: Generalizable graph masked autoencoder via collaborative latent space reconstruction. CIKM 2023.

Q1: Computation Complexity

We genuinely appreciate the time and effort you dedicated to a thorough reading of our paper. Based on your suggestions, we conducted a training time comparison experiment. We found it to be very helpful for readers to understand the actual model complexity, and we will include this experiment in our paper in the later revision. We have provided the time required for training on IMDB-BINAR, IMDB-MULTI and Cora in the following tables. All experiments were conducted on an RTX 3090, with all the models adhering to their default settings, and perform a single run with the same random seed and the same Pytorch platform. In Section 3.4 of the paper, we analyze the time complexity of DiGGR and find it consistent with Seegera [1]. Therefore, we included it in the comparison. Since the public code of SeeGera only implement on Cora dataset, we also compared the training time of VEPM [2] on graph classification data for a comprehensive comparision.

From the table, it is evident that DiGGR's training time is significantly shorter than SeeGera's during actual training. On the Cora dataset, DiGGR's overall training time is almost 4 times less than SeeGera's, and the average number of epochs per second is 5.56 times higher than SeeGera. For graph classification, DiGGR's training speed is generally faster than VEPM, with shorter runtime per epoch. Overall, these experimental results revalidate the conclusion in Section 3.4 of the paper: the complexity of DiGGR is comparable to previous works.

[1] Li, Xiang, et al. "Seegera: Self-supervised semi-implicit graph variational auto-encoders with masking." Proceedings of the ACM web conference 2023.

[2] He, Yilin, et al. "A variational edge partition model for supervised graph representation learning." Advances in Neural Information Processing Systems 35 (2022): 12339-12351.

Q2: Optimal factor number K

Thank you for your valuable comments. As you pointed out, the hyperparameter $K$ is indeed a crucial factor in our model. We would like to share our view on this parameter from two aspects:

(1) Empirical Analysis: We initially analyzed the impact of different $K$ values on the datasets. We conducted ablation studies on $K$ across four different datasets (see Figure 5 in Appendix A) and documented the optimal hyperparameter $K$ used for each dataset (see Tables 5 and 6 in Appendix A). It was observed that the optimal $K$ for most datasets typically falls within the range of 2 to 4. Therefore, we believe the optimal number of latent factors depends on the dataset's complexity. In practical applications, we use NMI to measure the similarity between latent factors. If the NMI between a new latent factor and the existing ones is high, we opt to retain the original number of latent factors.

(2) Performance Stability: Although the optimal $K$ for achieving the best performance may vary across different datasets, the performance variation due to different $K$ values is not significant in practical applications. For instance, in the ablation study of $K$, the performance fluctuation remained relatively small as $K$ varied from 1 to 16. On the MUTAG dataset, the standard deviation of accuracy across different $K$ values was only 0.58, and on Cora, this value was just 0.25.

In summary, the optimal number of latent factors depends on the dataset's complexity. While the optimal $K$ may differ across datasets, the resulting performance variation is minimal.

We genuinely appreciate the time and effort you dedicated to thoroughly reading our paper. Our code is uploaded in the Supplementary Material, with optimal hyperparameters in the config file. Set "use_best_cfg = True" to reproduce our results. Specific training hyperparameters and dataset details are in Tables 5 and 6 in Appendix A. If you have any further questions about reproducing the results, please do not hesitate to contact us. We are more than happy to address any further concerns you may have.

W1： More discussion on Novelty

Thank you for your insightful questions. We first highlight a notable difference: DiGGR uses a different learning strategy compared to DGCL [1] and IDGCL [2]. They use a contrastive learning framework requiring negative samples and complex data augmentation methods ([1, 2] tested four different augmentation methods). In contrast, our model employs Graph Mask Autoencoder, with masking the input node as the only pretext task, eliminating the need for explicit negative samples.

Due to character limitations, we thoroughly discussed the differences between DiGGR and [1-2] in the global rebuttal section. Please refer to that section for details. In short, the differences primarily arise from three aspects: the general framework we use, the factor learning method we designed, and the probabilistic techniques specifically tailored for the generative model. We will also incorporate this comparison into future revisions of the paper.

W2: recent or related contrastive baselines

Grateful for you valuable suggestion. In the subsequent revision of our paper, we will include additional disentangled methods based on contrastive learning. For now, we have re-listed our tables below, showing only the results reported in the paper for [1-4].

1. Due to large variations across different validation folds, we agree for each individual dataset the improvement might not appear that significant (not only to us, this observation applies to almost all previous state-of-the-art methods, e.g., for node classification, SeeGera[5] achieves better accuracy than GraphMAE[6] 0.1% on the Cora dataset; for graph classification, IDGCL[2] outperforms DGCL[1] by 0.2% on the IMDB-B dataset.). However, we would like to highlight that our model employs a generative self-supervised learning framework. Compared to contrastive learning-based methods [1-4], it achieves comparable results across 11 datasets, with 7 of them reaching optimal performance. This is unlikely to occur by chance and thus can be used to verify its appealing performance.

2. We chose generative self-supervised learning method, specifically a Graph Masked Autoencoder (GMAE) as the foundational framework, and incorporated disentangled learning into GMAE to help bridge the gap between generative and contrastive methods in node classification and graph classification task. As demonstrated in Tables 1 and 2 in our paper, DiGGR outperformed most methods based on generative frameworks. We aim to further reduce the performance gap between generative SSL and contrastive methods in the graph domain, capitalizing on its advantage of not requiring complex, task-specific pretext tasks, and to extend its applications in graph-related fields.

W3: Larger Datasets

Following your advice, we tested our model on the ogbn-arxiv dataset. Since our model involves the reconstruction of the adjacency matrix, to further save computational costs on larger graphs, we adopted the scalable sampling method from [7], computing only a portion of the adjacency matrix at a time. Our experimental setup was as follows: Factor Number $K=4$, learning rate = 0.0005, training Epoch = 600. All other experimental settings and environments were kept consistent with those described in the main text. The results are shown below:

It can be seen that DiGGR outperforms GraphMAE and GraphMAE2 on the ogbn-arxiv dataset, further validating the effectiveness of our approach. In the future, we will consider extending our model to other larger benchmarks. For extremely large graphs, we plan to use techniques such as PPR-Nibble[8] to generate relatively smaller local subgraph clusters. We believe that DiGGR has the potential to handle large-scale data and we are continuously working on this.

[1] Disentangled contrastive learning on graphs. NeurIPS 2021

[2] Disentangled graph contrastive learning with independence promotion. TKDE 2022

[3] Augmentation-Free Graph Contrastive Learning of Invariant-Discriminative Representations. TNNLS 2023.

[4] MA-GCL: Model Augmentation Tricks for Graph Contrastive Learning. AAAI 2023.

[5] Seegera: Self-supervised semi-implicit graph variational auto-encoders with masking. WWW 2023

[6] Graphmae: Self-supervised masked graph autoencoders. KDD 2022

[7] Fastgae: Scalable graph autoencoders with stochastic subgraph decoding. Neural Networks 142 (2021): 1-19

[8] Local graph partitioning using pagerank vectors. (FOCS'06). IEEE, 2006