Discovering Opinion Intervals from Conflicts in Signed Graphs

We thank the reviewer for the positive evaluation of our paper.

I think it's important to make clear that GAIA and VENUS are not finding better Correlation Clustering solutions in Table 1: the 8-chain structure is intrinsically more forgiving than clustering, since edges between nodes assigned to an interval and those on either side are not penalized. (i.e., the authors are assigning 2-3 cluster labels to each node and counting agreement if any labels match between nodes connected by a positive edge). In particular, "our novel methods outperform state-of-the-art heuristics for CORRELATION CLUSTERING. On 8 real-world datasets, the results are at least 20% better and over 38% on average" is misleading--they're being compared on two different tasks.

We will rephrase this to ensure that there are no misunderstandings. In particular, we will reword the cited part to: "In our experiments, we compare our novel methods against state-of-the-art heuristics for CORRELATION CLUSTERING, which is a special case of our problem. On 8 real-world datasets, our methods using overlapping opinion intervals achieve an error at least 20% better and over 38% on average, compared to the methods solving (the less expressive) CORRELATION CLUSTERING problem."

We will also make sure that there are no such misunderstandings in the rest of the paper.

As a side note, we remark that our algorithms also perform surprisingly well when applied directly to correlation clustering. In the supplementary material in Table 4, we evaluated GAIA and VENUS on solving correlation clustering instances (i.e., they are given 8 non-overlapping intervals as input which corresponds to solving correlation clustering with 8 clusters). Several times they match the performance of the best correlation clustering heuristics we compare against, and their error is never more than 2% higher than the best dedicated method for correlation clustering.

I don't understand Figure 3... It introduces many symbols not mentioned in the text ($S$, $M$, $T$, $H_S$, ...) and it's not at all clear how this relates to a signed graph. The text/caption needs to provide enough detail for the reader to gain something from the figure (if there isn't enough space, it should be in the appendix).

Indeed, in the main text we only mention the vertices $L$ and $R$ from the reduction, but not the auxiliary vertices $S$, $M$, $T$, $H_S$ and $H_T$, which are necessary for our reduction (see Section A.1). We will move the figure to the appendix for the final version of the paper.

Minor: "in recent years we are increasingly witnessing conflicts based on different views and opinions." is this really a recent phenomenon? Seems like people have been disagreeing since Plato and Aristotle (and earlier...). I don't think the motivation needs to rely on an unbacked claim that conflict is increasing (I would add sources or cut the claim).

We will rephrase this to state that: "in recent years there has been a lot of research to understand the conflicts in social networks and how they are based on different views and opinions." We will do this in the abstract, as well as at the start of the introduction, where we will also add some citations for this claim.

Another piece of related work in the line of recovering ideological positions of legislators from co-voting data is the (DW-)NOMINATE algorithm of Poole and Rosenthal. That method has the advantage of providing continuous estimates for each politician rather than an interval representation.

Thank you for pointing out this work. We will cite it and discuss it in the final version of our paper. However, we stress that this work is only applicable for co-voting behavior in the case study that we constructed for the German Bundestag, where the available data consisted of politicians and how they voted on parliamentary bills. In other words, the DW-NOMINATE method requires a signed bipartite graph, with the two sides given by politicians and parliamentary bills. In contrast, our algorithm takes as input a unipartite graph only consisting of the politicians and whether they frequently co-voted or not. Thus, in such settings the DW-NOMINATE algorithm is not applicable to the best of our knowledge.

We thank the reviewer for the positive evaluation of our paper.

How should practitioners select the amount and overlap configuration for the intervals in GAIA and VENUS? Let us assume no domain expertise with the new datasets (so no reasonable guess can be made for these values). Are there any principled or data-driven approaches for this task?

In such cases, we recommend running the algorithms with multiple interval structures, varying both the number of intervals and their overlap. Then, one can pick the one with the lowest objective function value. Here, two important remarks are in order:

• More intervals will generally be more expressive (leading to better objective values) but less interpretable. To find a good tradeoff, one can adopt methods such as the elbow method from the clustering literature.
• Regarding how to pick the intervals and their overlap structure, we can exploit the fact that our algorithms are highly efficient. In particular, due to this efficiency we can enumerate or randomly sample a large number of interval structures and then one can pick the one with the best objective function value. Further, the results that we reported for Reviewer HyVH with varying number of intervals suggest that typically a small number of intervals is sufficient (in this particular case, we observed that for $k$-chains, the objective function values only improve slightly for $k>8$; this is also in line with results from the correlation clustering literature), limiting the search space further.

Additionally, given that our algorithms are iteration-based and converge quickly, one could speed up the procedure above using methods from the hyperparameter search literature. Specifically, low-budget Bayesian optimization methods like successive halving by Jamieson and Talwalkar (citation below) should be well-suited to select promising configuration candidates quickly. Here, a configuration consists of an interval structure and the hyperparameters of the algorithms. Now, we run our algorithms for a small number of iterations for many different configurations. Then, the successive halving procedure will be able to pick the most promising candidates automatically to use more iterations on them. This is done multiple times until, at the end, we find one most promising solution.

We will add a discussion of this in the appendix of the final version of our paper.

Kevin G. Jamieson, Ameet Talwalkar: Non-stochastic Best Arm Identification and Hyperparameter Optimization. AISTATS 2016: 240-248

Could the authors discuss potential extensions of this method to multi-dimensional interval representations? Although outside the scope of this work, a discussion on the challenges of higher-dimensional interactions, including their real-world applicability, would enhance the significance of this framework.

Thank you for raising this interesting point. Surprisingly, after discussing the reviewer's suggestion, we realized that all of our algorithms (both the heuristics, as well as the FPT algorithm) also extend to higher-dimensional settings without any significant changes:

• The assignment-procedure from the heuristic GAIA (Algorithm 1) can be readily adapted, because it only uses the overlap-structure of the geometric objects.
• Similarly, this is also the case for the analysis of the FPT algorithm, which works with overlapping clusters and this analysis thus also extends when we have higher-dimensional objects. We will mention this in the final version of the paper, and we will also mention that studying this empirically appears to be an interesting question for future work.

We thank the reviewer for the positive evaluation of our paper. We will address all of the small comments in the final version and comment on some of them below.

Why in the experiments did you restrict to exactly 8 intervals?

We decided to use $k=8$ intervals because in our experiments this provided the best tradeoff between interpretability and good objective function values. To illustrate this, we provide a table below showing the number of violated edges by GAIA and VENUS for different values of $k=4,8,12,16$. We report the best result achieved by the algorithm across 50 runs.

The results show that up to $k=8$ intervals, the objective function values still decrease substantially, and afterwards they only decrease slightly. We note that for the Bundestag dataset, the results for $k=16$ are worse because for this dataset the variance of the algorithms' solutions is larger; with more runs we could also obtain better results here and we stress that this is not the case for any other datasets.

We will add this table, as well as plots for selected datasets, in the final version of the paper.

If the reviewer wishes, we can also provide the results for averages of the objective function values (rather than report the best results) for all datasets.

Perhaps the only “negative” I can see for this paper is that it’s not an amazing fit for a machine learning conference, although correlation clustering seems to have been studied quite a bit in the ML community.

We submitted the paper to NeurIPS because we believe its community brings together researchers with interest in correlation clustering, opinion formation, as well as signed graphs. Therefore, we think the paper is a good fit. To make this more explicit, we will cite the papers listed below in the final version of our paper, which highlight the community's interest in these topics.

Yuko Kuroki, Atsushi Miyauchi, Francesco Bonchi, Wei Chen: Query-Efficient Correlation Clustering with Noisy Oracle. NeurIPS 2024

Sepehr Assadi, Vihan Shah, Chen Wang: Streaming Algorithms and Lower Bounds for Estimating Correlation Clustering Cost. NeurIPS 2023

Konstantin Makarychev, Sayak Chakrabarty: Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple! NeurIPS 2023

Silvio Lattanzi, Benjamin Moseley, Sergei Vassilvitskii, Yuyan Wang, Rudy Zhou: Robust Online Correlation Clustering. NeurIPS 2021: 4688-4698

Ruo-Chun Tzeng, Bruno Ordozgoiti, Aristides Gionis: Discovering conflicting groups in signed networks. NeurIPS 2020

Yanbang Wang, Jon M. Kleinberg: On the Relationship Between Relevance and Conflict in Online Social Link Recommendations. NeurIPS 2023

Liwang Zhu, Qi Bao, Zhongzhi Zhang: Minimizing Polarization and Disagreement in Social Networks via Link Recommendation. NeurIPS 2021: 2072-2084

The name "OPINION INTERVAL REPRESENTATION” makes me think of the problem of finding an exact representation if one exists, but Problem 2.1 is more general — maybe a better name would be something like “best interval approximation” or something?

Thank you for raising this point, indeed the current name could suggest that we are looking for an exact representation. As suggested by the reviewer, we will rename the problem to best interval approximation in the final version of our paper.

In the introduction it is mentioned that the paper approach leads to results that are “20% better than correlation clustering”. It would be helpful to describe here roughly what metric is being considered — how methods for two different problems compared in a head-tohead way?

We will clarify this in the final version of our paper, stating that we evaluate the algorithms on our objective function and that correlation clustering algorithms are more restricted when searching for solutions, since correlation clustering is less expressive than our problem. We will also implement all of the related changes that we discuss below for Reviewer NU77.