Summary
The authors introduce an attributed-graph clustering scenario where it is of interest to cluster the attributes of the graph rather than the nodes. They propose a pipeline that involves a graph-based attribute distance metric, a graph auto-encoder, dimensionality reduction via TSNE, and a final clustering step. They devise a synthetic benchmark framework to stress-test their approach vs baselines and ablations. They also evaluate the pipeline & alternatives on three real-world datasets from a variety of domains.
Strengths
(1) The paper's main strength is the novelty of the problem setting. I am not aware of any other approach to clustering that attempts to use an explicit graph over the dimensions. This is an interesting setting and worth exploring.
(2) The paper's simulation study and real data studies are (each) thorough, well-described, and appropriate for evaluation.
Weaknesses
I will elaborate on these high-level weaknesses (with evidence) in my questions to the authors.
(1) The paper lacks a clear understanding of how each of the individual modules are used. In some places, there is reason to question the soundness of the modules that are proposed.
(2) The proposed pipeline has unclear efficacy on the real-world datasets. It is not clear to practitioners whether the proposed approach should be used in general, or whether the baselines would suffice.
(3) The authors discuss a scalable estimation of the inverse Laplacian, but they do not check the performance of the approximation in their results.
Questions
It is very unclear how the graph auto-encoder (GAE) is applied in the pipeline. A graph autoencoder for attributed graphs performs node feature convolutions over the graph to arrive at a $n \times d_a$ representation of the graph, where $n$ is the number of nodes and $d_a$ is the size of the inner hidden dimension. It is possible to reconstruct an $n\times n$ low-rank estimated graph from this latent representation. We must consider this in light of the authors' statements:
* Q1: The authors describe the GAE baseline as follows: "GAE: clusters $O$, after passing it through our graph autoencoder, described in Section 2.4". It is not at all clear how one can "cluster $O$" from the output of the GAE. To cluster $O$, you need to cluster the columns of some matrix with column dimension $d(O)$. Since the output of a GAE is either $n\times d_a$ or $n\times n$, it is not at all clear how one can "cluster $O$" after "passing it through" a GAE. Can the authors elaborate?
* Q2: In S2.4.2, the authors write "We could apply tSNE directly to the GAE output." As above, this lacks a formal description, and it is ambiguous how this could actually be achieved. Again, we would need to apply tSNE to some $k \times d(O)$ matrix, which would result in a tSNE-estimated $2 \times d(O)$ matrix. How does the GAE output allow for this?
* Q3: Figure 2 implies that somehow the GAE output is used in the distance metric computation. However, this is never described (even vaguely). The formula for the distance metric (given in Section 2.3) includes only the original attribute data $O$ and the inverse laplacian $L^{+}$, which is derived from the original graph $G$. How does the GAE output feed into this?
* Q4: The authors write "We could apply tSNE directly to the GAE output. However that would mean that tSNE is seeking for the best representation of the data in an Euclidean space, which is not appropriate because we know the dimensions of our observations are related to each other in $G$". The plausibility of this reasoning is hard to evaluate because we don't know how the GAE is being applied. It is quite possible that (depending on how the GAE fed into the tSNE module), tSNE is actually *not* being applied in a "Euclidean" space, because the output of the GAE directly convolves the node features with the graph structure. Can the authors please clarify this statement, as well as the application of GAE itself?
Q5: The only justification the authors give for their distance metric, which is arguably a core part (if not *the* core part) of the contribution, is very weak:
"Previous work shows that this formula gives a good notion of distance between $o_1$ and $o_2$ on a network Coscia (2020). For instance, it can recover the infection and healing parameters in a Susceptible-Infected-Recovered (SIR) model by comparing two temporal snapshots of an epidemic."
To the best of my understanding, there is no immediate connection between a metric's ability to estimate SIR parameters and a metric's ability to cluster data well. Can the authors please elaborate their justification for this choice?
Q6: While the approximation to $L^{+}$ seems efficient (see Section 3.4), the authors did not explore how the approximation affects the performance of the algorithm. Could the authors please replicate the simulations and real data analyses using the approximation to $L^{+}$ rather than the exact solution? This would be a welcome addition to the appendix.
Q7: From a methodological perspective, the conclusions that a practioner can draw from the empirical study is very limited. This is because the baselines of the proposed pipeline do almost as well as the pipeline on the real-world data. In particular, for each dataset, two out of the top-3 scoring approaches do not use the proposed graph distance at all. Again on each dataset, ablations that *do* use the graph distance have at-most middle-ranks, and one of the scores for the full pipeline (GAE+GE+tSNE) is near-random performance (see Fig 4(a)). Can the authors further justify the use of their pipeline in light of these results?
If the authors can answer these questions satisfactorily and provide a substantial revision, I might be able to raise my score.
Rating
5: marginally below the acceptance threshold
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.