acceptodds
Under review as a conference paper at ICLR 2027

Recovering Consensus in Multi-Modal Graphs: Provable Multi-Modal Spectral Clustering

Abstract

This paper studies clustering algorithms for multi-modal graphs, in which each modality might have a different structure of clusters caused by the unique information of each modality, and the modality-consensus clusters are defined such that vertices belong to the same cluster if and only if they appear in the optimal cluster of every single modality. The paper presents a spectral algorithm to approximate these modality-consensus clusters, and provides a theoretical analysis of the algorithm’s output with respect to the optimal clusters. The paper further compares the performance of the proposed algorithm with the previous state-of-the-art on both synthetic and real-world datasets, with experimental results demonstrating its superiority.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
clustering, spectral methods, algorithms design

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_cFXkOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper studies aligned multi-modal graphs whose modality-specific optimal partitions may differ. Its target is their common refinement: each consensus cluster is a non-empty intersection of one cluster from every modality. Algorithm 1 computes the bottom k_i eigenvectors of each normalized Laplacian, concatenates the vertex embeddings, and applies k-means. The design aims to preserve complementary distinctions without forcing identical partitions. The paper claims an indicator-space approximation theorem and a clustering-error guarantee under strong clusterability and balance assumptions. It also proposes cost-threshold estimation of k and a practical signature-based merging heuristic. Validation comprises synthetic SBMs and three real-source datasets modified by zeroing features of selected classes, with an additional contrastive-representation variant. The empirical results are promising in these settings.

Critical strengths

1.A clear formulation for complementary modalities. Defining consensus clusters as the common refinement provides an explicit target when different modalities reveal distinct, meaningful aspects of the same samples.

2.A transparent method with encouraging reported results. Spectral-embedding concatenation followed by k-means is straightforward to implement and inspect. The experiments demonstrate potential benefits in the constructed settings, and Ours+CRL reports the highest ACC on all three modified real-source datasets.

Critical weaknesses

1.The specific contribution of the proposed clustering mechanism is not sufficiently isolated. The core algorithm combines modality-specific spectral embeddings through concatenation and k-means, but the experiments omit the directly relevant baseline of independently clustering each modality and intersecting the resulting partitions. This comparison is particularly important because the practical heuristic itself uses independent clustering assignments to merge clusters. Furthermore, the strongest results come from Ours+CRL, which adds an existing representation-learning component. Without comparing alternative clustering methods on the same learned features, the results do not establish how much improvement comes from the proposed clustering mechanism.

2.The experimental evidence is narrower than the intended application scope. The real-source datasets are modified by zeroing features of selected classes to create modality-specific cluster mergers, while the synthetic experiments cover a limited range of partition structures. These controlled settings do not sufficiently establish effectiveness under naturally occurring differences between modalities. More fundamentally, common refinement preserves every modality-specific distinction, including potentially irrelevant ones; the paper provides limited evidence that the resulting finer partition is a useful target in realistic applications. This limits the practical significance and generalizability of the reported gains.

Questions for authors

1.Can the authors compare against intersecting independently recovered modality partitions and ablate the signature-based merging heuristic? For Ours+CRL, can alternative clustering methods be evaluated on the same learned representations to isolate the contribution of the proposed method?

2.Can the authors provide evidence beyond class-dependent feature zeroing, including more general crossed partitions and a naturally complementary real-data setting? How should common refinement be interpreted when some modality-specific distinctions are irrelevant to the intended task?

Reviewer_1k3JOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies multi-modal graph clustering where different modalities may exhibit distinct optimal cluster structures. The authors define the target consensus clusters as the non-empty intersections of modality-specific optimal clusters. To recover these clusters, they propose a simple spectral clustering algorithm that concatenates the bottom eigenvectors of individual graph Laplacians and applies k-means. The paper further provides theoretical results concerning the relationship between spectral embeddings and consensus clusters, along with clustering error guarantees. Experiments on synthetic and real-world datasets are conducted to demonstrate the effectiveness of the proposed approach.

Critical strengths
  1. The paper addresses an interesting and relevant problem by allowing different modalities to have distinct optimal clustering structures, rather than assuming that all modalities share an identical partition.
  2. The proposed method is straightforward to implement and understand. Its simplicity, together with the attempt to establish theoretical recovery guarantees, is an appealing aspect of the work.
Critical weaknesses
  1. Several key theoretical claims appear to be incorrect, which undermines the reliability of the main theoretical contributions. In particular, the span equality used in the proof of Theorem 1 does not generally hold. Moreover, the lower bounds in Lemmas 5.3 and 5.5 appear to overlook important structural properties of consensus clusters. These issues may affect both the proof of Theorem 2 and the claimed guarantee for determining the number of clusters.
  2. The real-world experiments artificially create different modality-specific cluster structures by modifying features according to class labels, which may not adequately represent naturally occurring structural discrepancies. Furthermore, the paper lacks a direct comparison with the simple baseline of independently clustering each modality and intersecting the resulting partitions. The improvements of Ours+CRL are also difficult to attribute to the proposed clustering algorithm, since additional representation learning is introduced without fully controlled comparisons.
Questions for authors
  1. In Appendix B, the authors claim that the span of all modality-specific cluster indicator vectors equals the span of the consensus-cluster indicator vectors. However, consider two partitions of four vertices: {{1,2}, {3,4}} and {{1,3}, {2,4}}. Their common refinement contains four singleton clusters, but the modality-specific indicator vectors span only a three-dimensional space, whereas the consensus indicators span a four-dimensional space. This also yields a counterexample to the approximation bound in Theorem 1 when the graphs have sufficiently well-separated clusters. How do the authors justify this equality and the resulting theorem?
  2. Two different consensus clusters may belong to the same original cluster in several modalities. However, the proposed separation lower bound assigns a positive contribution to every modality when the clusterability parameters are sufficiently large. For example, with five modalities, four having the partition {{1,2}, {3,4}} and one having {{1,3}, {2,4}}, the squared embedding-center distance between singleton consensus clusters {1} and {2} approaches 1, whereas the claimed lower bound approaches 1.25. Could the authors clarify how modalities that do not distinguish a pair of consensus clusters are handled in the proof?
  3. Consider two identical modality graphs, each containing ten well-separated clusters of ten vertices. In the ideal spectral embedding, the optimal 9-means cost is 2, obtained by merging one pair of clusters, whereas the proposed lower bound approaches 12.5. This discrepancy persists for sufficiently small positive inter-cluster edge weights. Could the authors revisit the derivation of this lower bound and explain whether the cluster-number selection guarantee in Section 5.2 remains valid?
  4. Could the authors provide comparisons against a direct intersection-of-partitions baseline, evaluate naturally occurring modality-specific structural differences without label-guided feature modification, and compare methods using the same learned representations? These experiments would help isolate the contribution of the proposed clustering algorithm.
Reviewer_X1a1OpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper considers several graphs on a common vertex set whose optimal partitions may differ. It defines consensus clusters as the nonempty intersections of these partitions and proposes concatenating modality-specific spectral embeddings followed by kk-means. The claimed analysis includes a structure theorem, a misclassification bound, and a procedure for determining the number of consensus clusters; a faster merging heuristic is also proposed. Experiments use synthetic block-model graphs and three modified multi-view datasets, with a further variant using learned contrastive representations.

Critical strengths
  1. The target problem is meaningful. Recovering the common refinement of genuinely different modality partitions is a useful alternative to assuming that every modality shares one clustering. The motivating examples explain why this distinction matters.

  2. The proposed algorithm is simple and potentially useful empirically. Concatenating spectral embeddings provides an accessible baseline for this problem. The reported results make it worth investigating, even though they do not establish the proposed guarantees.

Critical weaknesses
  1. Several central theoretical claims seem to fail under the stated assumptions.

Theorem 1(1) relies on the span equality in Appendix B, line 682. Consider partitions {{1,2},{3,4}}\{\{1,2\},\{3,4\}\} and {{1,3},{2,4}}\{\{1,3\},\{2,4\}\}. Their indicators span only three dimensions, whereas the common refinement consists of four singleton clusters. In each modality, assign weight 1 to the within-cluster pairs and weight η\eta to the remaining pairs. Both graphs are connected and regular, and Υ=(1+η)/η\Upsilon=(1+\eta)/\eta. Their joint bottom-eigenvector span is generated by the constant vector and the two partition contrasts. A singleton indicator has squared projection error 1/41/4, while Theorem 1(1) bounds this by 4η/(1+η)4\eta/(1+\eta), which is smaller for sufficiently small η\eta. Thus the theorem is false even for arbitrarily well-clustered regular graphs. Intersections of clusters cannot generally be represented by linear combinations of the individual partition indicators.

Lemma 5.3 has a separate problem: if two consensus clusters share the same cluster in modality ii, their approximate centers in that modality are identical. The stated bound nevertheless sums a positive separation contribution over every modality. For example, four copies of the first modality above and one copy of the second, with η=0.001\eta=0.001, give squared separation 1 for the relevant pair, but the lemma asserts a lower bound of approximately 1.230. This undermines the separation argument used for Theorem 2.

Lemma 5.5 is also false even for one modality. Take five equal clusters, each consisting of a pair of vertices, with within-pair weight 1 and all other edges of weight η=10−4\eta=10^{-4}. The graph is regular and has Υ=2501\Upsilon=2501. Its bottom-five spectral embedding admits a four-means solution of cost 1 by merging two clusters. The lemma instead gives a lower bound 25/16−50/2501≈1.54325/16-50/2501\approx1.543. The proposed cluster-count rule therefore lacks its claimed justification.

Moreover, Lemma 4.1 applies a normalized-Laplacian result to unweighted indicators, whereas the cited result uses degree-weighted indicators. Balanced cluster sizes do not resolve this discrepancy. The counterexamples above are regular, so they do not depend on this additional issue.

  1. The empirical evidence does not resolve the theoretical concerns or fully isolate the proposed task. The real-data experiments induce differing modality partitions by zeroing features for selected labeled classes. This is a controlled transformation, but it provides limited evidence for naturally differing partitions. The evaluation also needs a direct baseline that clusters each modality separately and intersects the resulting labels, clear graph-construction and cluster-count settings, and variability across runs. Claims of consistently outperforming shallow methods should be qualified: Table 1 gives LMTC higher nuswide ACC. The learned-representation variant should also be distinguished from the setting actually covered by any corrected theorem.
Questions for authors
  1. How can Theorem 1(1) hold for the crossed-partition example above? What additional assumption or different representation is needed, and how would it change the intended problem scope?

  2. After correcting the degree normalization and counting only modalities that distinguish a pair of consensus clusters, what recovery guarantee remains? Can the authors provide a valid replacement for Lemma 5.5 and show whether the proposed kk-selection procedure still works?

  3. How were the graphs constructed and k,kik,k_i selected for Table 1? How many independent runs were used, and how does the method compare with intersecting independently estimated modality partitions?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.