PieClam: A Universal Graph Autoencoder Based on Overlapping Inclusive and Exclusive Communities

We thank that reviewer for the positive and in depth evaluation of our paper.

Claims And Evidence:

...further clarity on the implications of using the log cut distance in sparse graphs would enhance the overall argument.

Response. Thank you for this suggestion. We already shortly discussed this shortcoming in the Conclusion (Page 8):

"Another limitation of our analysis is that the log cut distance is mainly appropriate for dense graphs. Future work will extend this metric to sparse graphs..."

but we agree that this discussion may be too short. If accepted, we will extend the discussion about sparsity, stating that the analysis is mostly appropriate for dense graphs, but the method is empirically appropriate also for sparse graphs.

Regarding applicability of the method to real-world sparse graphs, the method was tested against sparse graphs in anomaly detection and link prediction benchmark, where we got competitive performance, demonstrating that the method performs well empirically also for sparse graphs.

Theoretical Claims:

However, further discussion surrounding any assumptions made during the proof processes would strengthen the rigor of this section...

Response. As a principle in mathematical writing, all assumptions are clearly and explicitly stated in the body of the theorem. No additional assumptions are allowed to be taken during the proof, as this would undermine the correctness of the theorem. We believe to have complied with this basic principle. However, if the reviewer found a hidden assumption in the body of the proof, please let us know where specifically this is made so we can fix it.

Essential References Not Discussed:

The manuscript could benefit from including related works that ... explored universal properties of graph representations. .. Works exploring the strengths and weaknesses of using similar graph distance measures in sparse networks should also be cited.

Response. We will add paragraphs to the Extended Related Work appendix about this. We will cite papers about universality of GNNs as functions from graphs to vectors (graph classification or regression). For example:

S. Chen, S. Lim, F. Memoli, Z. Wan, and Y. Wang. Weisfeiler-Lehman meets Gromov-Wasserstein. ICML. 2022.

S. Chen, S. Lim, F. Memoli, Z. Wan, and Y. Wang. The Weisfeiler- Lehman distance: Reinterpretation and connection with GNNs. Proceedings of 2nd Annual Workshop on Topology, Algebra, and Geometry in Machine Learning (TAG ML). 2023.

J. B¨oker, R. Levie, N. Huang, S. Villar, and C. Morris. Fine-grained expressivity of graph neural networks. NeurIPS. 2023.

L. Rauchwerger, S. Jegelka, R. Levie. Generalization, Expressivity, and Universality of Graph Neural Networks on Attributed Graphs. 2025.

We will also add a short discussion about sparse graph similarity measures that can potentially be used to define a version of log-cut distance appropriate for sparse graphs. For example:

Stretched Graphons: C. Borgs, J. T. Chayes, H. Cohn, and N. Holden. Sparse exchangeable graphs and their limits via graphon processes. Journal of Machine Learning Research. 2018.

$L^p$ graphons: C. Borgs, J. Chayes, H. Cohn, and Y. Zhao. A theory of sparse graph convergence i: Limits, sparse random graph models, and power law distributions. Transactions of the American Mathematical Society. 2019.

Graphings: L. Lovász. Large networks and graph limits, volume 60. American Mathematical Soc., 2012.

Graphops: Backhausz and B. Szegedy. Action convergence of operators and graphs. Canadian Journal of Mathematics, 74(1):72–121, 2022.

Weaknesses:

The potential narrow focus on node affiliations without sufficiently addressing node features in edge conditions, which may limit applicability across diverse graph types...

Response. First, we already addressed this issue in the Conclusion:

"One limitation of PieClam is that, for attributed graphs, it only models the node features through the prior in the community affiliation space, but not via the conditional probabilities of the edges (given the community affiliations). Future work will deal with extending PieClam to also include the node (or edge) features in the edge conditional probabilities."

Still, we often observe in experiments that not using the features can still lead to competitive performance with methods that do use the features. We wrote in section D3 of the appendix on page 25:

"Note that, since the prior is not used in classification, there is no added benefit from utilizing node features when training the prior, as proposed in 2.4. Therefore, the link prediction algorithm relies solely on the graph’s topological structure and the prior functions only as regularization."

Nevertheless, we will extend this discussion in the camera-ready version of the paper if accepted.

We thank the reviewer for the positive and in depth evaluation of our paper.

Weaknesses:

1. A key concern lies in the equivariance of the encoder architecture...

Response. Thank you for this comment. PieClam (and all other Clam models) are in fact equivariant to node re-indexing. This is due to the fact that maximizing the log likelihood via gradient descent in Clam models can be formulated as a message passing algorithm. We wrote this on Page 3, Column 1, Line 158 (about BigClam):

"We observe that the optimization process is a message passing scheme"

But we indeed did not link this to equivariance, and did not repeat this claim about all other Clam models. If accepted, we will add an explanation about the equivariance of Clam methods to node re-indexing.

2. The experimental evaluation would benefit from additional benchmarks...

Response. We ran additional experiments on link prediction on the OGB-ddi dataset. We will add more experiments in the final version.

3. The computational complexity of the proposed approach remains unspecified, leaving questions about its scalability and feasibility for large datasets.

Response. We wrote about the computational complexity of BigClam on Page 3, Column 1, Line 144:

"In order to implement the above iteration with $O(|E|)$ operations at each step, instead of $O(N^2)$, the loss can be rearranged as..."

As written above, basically, Clam models are trained with message passing algorithms, so they have efficient computational complexity: linear in the number of edges.

BigClam. On Page 4, Column 1, Line 208, wewrote:

"This loss can be efficiently implemented on sparse graph by the formulation..."

We agree that we have not clarified enough that all other Clam models, including PieClam, share their computational and memory complexity with

We will clarify in the camera ready version (if accepted) that all Clam models have linear complexity with respect to the number of edges

4. The paper does not fully explain how the model generalizes to unseen data.

Response. Studying how and why models generalize to unseen data is one of the key and most fundamental (mostly open) questions in learning theory, and specifically statistical learning. In this paper we do not provide generalization analysis, e.g., in a PAC learnability setting, VC dimension, Rademacher complexity, etc. We leave such analysis to future works, and note that most papers that first proposes a deep learning architecture do not provide a generalization analysis.

If your question is meant to be more practical, i.e., how the training and test data are defined, and how testing is defined, this depends on the problem.

1. In anomaly detection, the setting is explained in Section 4.3:

"In unsupervised node anomaly detection, one is given a graph with node features, where some of the nodes are unknown anomalies. The goal is to detect these anomalous nodes, without supervising on any example of normal or anomalous nodes, using only the structure of the graph and the node features"

Namely, here generalization is better interpreted as a form of "transfer learning". One fits the Clam model to the whole graph data (solving the task of reconstruction/autoencoder), and then uses the trained community affiliation features to solve a different task: evaluating the likelihood of nodes according to the learned probabilistic graph model.

2. In link prediction, as explained in Section 4.4:

"In supervised link prediction, one is given a graph where for some of the dyads it is unknown if they are edges or not. The goal is to predict the connectivity of the omitted dyads."

So, here the training set for he Clam model are the known dyads (the given known edges and non-edges) and the test set are the unknown dyads, where the task is to decide if each unknown dyad is an edge or a non-edge.

We thank the reviewer for the positive and in depth evaluation of our paper.

Claims And Evidences:

...the evidence on sparse graphs is a bit less comprehensive. Further empirical validation in more diverse settings would improve the support for universality claims.

Response. The experiments in the current version of the paper (anomaly detection and link prediction) are already on sparse graphs. For example, the Texas graph has 183 nodes and 279 edges.

We ran additional experiments on link prediction on the OGB-ddi dataset. We will add more experiments in the final version.

Methods And Evaluation Criteria:

...additional discussion on scalability (especially for large or sparse graphs) and hyperparameter sensitivity would be valuable.

Response. Regarding scalability, we will add to the camera ready version of the paper a discussion that shows that both the memory and time complexity of all Clam models are linear in the number of edges.

We already wrote about the computational complexity of BigClam on Page 3, Column 1, Line 144:

"In order to implement the above iteration with $O(|E|)$ operations at each step, instead of $O(N^2)$, the loss can be rearranged as..."

Moreover we wrote about BigClam, Page 3, Column 1, Line 158:

"We observe that the optimization process is a message passing scheme"

We agree that we have not sufficiently clarified that all other Clam models are trained with a message passing scheme, and share their complexity with BigClam: linear in the number of edges. We only wrote on Page 4, Column1, Line 208:

"This loss can be efficiently implemented on sparse graph by the formulation..."

We will clarify in the camera ready version that all Clam models have linear complexity with respect to the number of edges.

Regarding hyperparameter sensitivity, in Appendix D6 we do an ablation study where we show the impact of certain parameters on the performance of the model. We can extend this appendix to study sensitivity to more hyperparameters.

Theoretical Claims:

...some assumptions (e.g., regarding graph density) might limit their direct applicability to real-world sparse graphs.

Response. We already shortly discussed this in the Conclusion (Page 8):

"Another limitation of our analysis is that the log cut distance is mainly appropriate for dense graphs. Future work will extend this metric to sparse graphs..."

but we agree that this discussion may be too short. If accepted, we can extend the discussion about sparsity, mainly stating that the analysis is mostly appropriate for dense graphs (but the method is appropriate also for sparse graphs).

Regarding applicability of the method to real-world graphs, the method was tested against sparse graphs in anomaly detection and link prediction benchmark, where we got competitive performance, demonstrating that the method performs well empirically also for sparse graphs.

Experimental Designs Or Analyses:

Nonetheless, it would be useful to see more detailed analyses on the model’s performance with respect to computational efficiency... especially since the training involves simultaneous optimization of node embeddings and a prior.

Response. Note that the prior is a node-wise computation, so it is dominated by the rest of the log likelihood terms in optimization.

We wrote on Page 4, Column 2, Like 216:

"Observe that the PieClam loss is similar to the IeClam loss, only with the addition of the prior acting as a per node regularization term"

We will extend the text in the camera-ready version and write that, as a reuslt, adding the prior does not asymptotically increase the complexity of the model.

Essential References Not Discussed:

We will properly refer to the suggested papers in the camera-ready version of the paper if accepted.

Weaknesses:

Response. See our responses above.