Discovering Opinion Intervals from Conflicts in Signed Graphs
Authors: Peter Blohm
Florian Chen
Aristides Gionis
Stefan Neumann
Venue: NeurIPS 2025 oral ()
Keywords: Signed graphs
intervals graphs
social networks
correlation clustering
opinions
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: We present a novel problem that allows to infer a small and interpretable set of prevalent opinion ranges in signed graphs, that explain the users' interactions.

Abstract: Online social media provide a platform for people to discuss current events and exchange opinions with their peers. While interactions are predominantly positive, 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.  In this paper, we ask whether the conflicts in a network reveal a small and interpretable set of prevalent opinion ranges that explain the users' interactions.  More precisely, we consider signed graphs, where the edge signs indicate positive and negative interactions of node pairs, and our goal is to infer opinion intervals that are consistent with the edge signs.  We introduce an optimization problem that models this question, and we give strong hardness results and a polynomial-time approximation scheme by utilizing connections to interval graphs and the Correlation Clustering problem.  We further provide scalable heuristics and show that in experiments they yield more expressive solutions than Correlation Clustering baselines. We also present a case study on a novel real-world dataset from the German parliament, showing that our algorithms can recover the political leaning of German parties based on co-voting behavior.

Discovering Opinion Intervals from Conflicts in Signed Graphs
Peter Blohm'
Florian Chen" University of Oxford Oxford, UK florian. chenccs.cccco. ox. ww.ac.cc....ooo................. ac..c. uk
Aalto University
Espoo, Finland
peter. blohm@aalto.ff
Aristides Gionis
Stefan Neumann
KTH Royal Institute Technology
TU Wien
Digital Futures
Vienna, Austria
Stockholm, Sweden argioni@kh..se
stefan, www.anmmnnnnnuiinnnncmmmm ac at
Abstract
Online social media provide a platform for people discuss current events and exchange opinions with their peers. While interactions are predominantly positive, in recent years, there has been lot of research understand the conflicts in social networks and how they are based on different views and opinions. In this paper, ask whether the conflicts in network reveal a small and interpretable set of prevalent opinion ranges that explain the users' interactions. More precisely, we consider signed graphs, where the edge signs indicate positive and negative interac- tions of node pairs, and our goal is to infer opinion intervals that are consistent with the edge signs. We introduce an optimization problem that models this question, and we give strong hardness results and a polynomial-time approximation scheme by utilizing connections interval graphs and the CORRELATION CLUSTERING problem. We further provide scalable heuristics and show that in experiments they yield more expressive solutions than CORRELATION CLUSTERING baselines. We also present case study on a novel real-world dataset from the German parliament, showing that our algorithms can recover the political leaning German parties based on co-voting behavior.
Introduction
Online social networks are essential parts of modern societies and used by billions of people discuss current events. Even though a majority of the interactions on such networks are positive, there are a substantial number of conflicts, particularly due tensions among people with differing viewpoints [48, 47].
As result, gaining deeper understanding of these conflicts has become essential. This question is often studied using signed graphs [29, 48, 47], where each edge has a sign that is either positive (+) if two nodes interact amicably, negative (-) if the interaction is conflicting. A classic formulation used to analyze signed graphs and gain insights about the graph structure and potentially the opinions of nodes is the CORRELATION CLUSTERING problem [4]. In CORRELATION CLUSTERING, to partition the nodes of a given signed graph into clusters, so as to maximize the number of edges that are consistent with the clustering (or minimize the number of inconsistent edges).
ask
Equal contribution. This work was done while the authors TU Wien.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

3
6
8
LINKE (Left)
GRÜNE (Green)
(Social Democrat)
FDP (Liberal)
CDU/CSU (Conservative)
AFD (Far Right)
Figure I: Visualization of our results signed graph based on co-voting behavior in the German parliament. We computed solution to BEST INTERVAL. APPROXIMATION with 8 intervals, where consecutive intervals overlap (the intervals visualized at the bottom of the figure). Each point corresponds to a German politician and assignments are visualized by mapping them to their party (y-axis) and interval (x-axis); for example, interval 3 contains politicians from SPD, GRÜNE, and LINKE. In each interval, points are shifted left or right, based on the number of positive and negative edges the corresponding politician shares with adjacent intervals.
One drawback of the CORRELATION CLUSTERING formulation is that it makes hard decisions for the assignment of nodes into clusters and does not allow for a nuanced model in the presence of complex node interactions. For instance, in the landscape of European political parties, the opinions of representatives typically do not align perfectly with party lines; instead, members of adeologically-neigheee
parties may agree certain issues, while at the same time, members of the same party may disagree on other issues. Similar observations have been made for the US House of Representatives [2], however, when more parties are involved, modeling the interactions between representatives becomes increasingly complex.
In this paper, we introduce a novel problem to analyze signed graphs and discover structure that explains the nodes' interactions (confficts and agreements) more accurately. Instead of assigning nodes to disjoint clusters, we seek to assign nodes to a small number of thienialll-ovverlappin opinion intervals. The resulting structure can lead to meaningful insights and intuitive visualization (e.g., see Figure 1). We show that our problem is more expressive than CORRELATION CLUSTERING, thus resolving the drawback mentioned above, At the same time, our problem only requires the edge signs in the network as input, making it widely applicable.
Our results. First, we introduce the BEST INTERVAL APPROXIMATION problem: Given signed graph G (V,E* E U E ). assign an interval Lg C R to every vertex e E V such that we maximize the number of edges {u, v} Et with 4, n L, # 0 and {u, v} E' with Ly O La 0. In other words, if two nodes are connected by positive edge, then their corresponding intervals should overlap, whereas they are connected by a negative edge, then their intervals should be disjoint. Note that for node we can think of I as the range of opinions that are acceptable to and yield an amicable interaction; all opinions outside of I, are not acceptable and yield conflict. This problem is more expressive than the CORRELATION CLUSTERING problem of Bansal et al. [4], and related problem by Kermarree and Thraves [34] as we explain below.
Second, we show that BEST INTERVAL. APPROXIMATION is NP-hard even when the graph G+ (V, E) induced by the positive edges forms a cycle. In sense, this is the strongest possible hardness result one could hope for since removing a single edge from the cycle G+ (V, E*) produces path, for which intervals can always be assigned without any error. This implies that (unless P NP) for BEST INTERVAL APPROXIMATION there is no FPT algorithm that parameterizes by the number of required edge removals and that the disagreement version of BEST INTERVAL APPROXIMATION cannot be approximated within any multiplicative factor. It also provides novel insights into the hardness of finding forbidden induced subgraphs, which rules out several algorithm design approaches. Our reduction is based on a result of Cygan et al. [22], but making it work for cycles requires several new ideas and gets significantly more complicated. We provide an overview of the reduction in Section 2.

---

Third, we consider a constrained version of BEST INTERVAL APPROXIMATION, where we are given a complete signed graph and parameter E > O. Now, we are only allowed to use & distinct intervals and each node must be assigned to one of them. This provides highly interpretable insights since the number of intervals is small. For this problem, we provide a polynomial-time approximation scheme (PTAS); specifically, we present an algorithm that computes a (1 + --approximationn in time 20 log(k/(s6))/=") n. This generalizes an algorithm by Giotis and Guruswami [28] that was developed for CORRELATION CLUSTERING with fixed number of clusters. We provide an overview of the PTAS in Section 2.2.
Fourth, from a practical point of view, we introduce heuristics that we describe in Section 3. Our heuristics are inspired by the PTAS above and include several practical improvements. Our experi- ments find that BEST INTERVAL APPROXIMATION is substantially more expressive than CORRE- LATION CLUSTERING and that our heuristic algorithms succeed in exploiting this expressivity. On 8 real-world datasets, our methods find overlapping opinion interval assignments that represent the data with 38% fewer disagreements on average compared to CORRELATION CLUSTERING solutions found by state-of-the-art methods. This holds even when we use only 8 intervals, showing that already a small number of intervals yields expressive and interpretable representations.
we perform a case study on a novel dataset based on co-voting behavior in the German parliament, which we make publicly available. The output of our algorithm allows to reconstruct the leaning of the political parties, as we demonstrate in Figure 1. Besides accurately reflecting the German political spectrum, the figure also reveals the coalition governments throughout the past decade (see Section 4). We stress that, due to the overlapping spectrum from the left to the right, finding such structure would not be possible in existing problems like CORRELATION CLUSTERING.
Furthermore,
We conclude the paper with several interesting questions for further research in Section 5, and present proofs and additional experimental results in the supplementary material.
Related work. The BEST INTERVAL APPROXIMATION problem is closely related to the SITTING ARRANGEMENT problem by Kermarrec and Thraves [34]: Given a signed graph G = (V,E+UB can we assign a vector Tu E RR to each u E V such that for all positive edges {u. E E
and negative edges [u, E E- the inequality || - xulll2 < || - x=wl2 holds? Kermarrec and Thraves [34] presented several results for the case of L = 1, i.e. embedding G into the real line. Cygan al. [22] improved upon this and showed that for complete signed graph G such an assignment exists if and only if the subgraph induced by its positive edges G+ (V, Et) is unit interval graph [59]. Given this characterization, we note that our problem more expressive since we allow general (non-unit) intervals. Besides these theoretical insights, Pardo et al. [55, 56] provided heuristics for an optimization version that aims to minimize the number of violated constraints on the vectors Ty above. However, this objective is substantially different from ours and thus incomparable.
As mentioned before, CORRELATION CLUSTERING [4] is highly related our work and is stated as follows: Given a signed graph G = (V, E+ U E-), partition its vertices into disjoint clusters Ci,..., C V such that the number of positive edges within the clusters C2 and the number of negative edges between different clusters C, and Cj. i A j. is maximized. Here, the value of k can be picked by the algorithm. CORRELATION CLUSTERING has received a lot of attention in the past two decades in social network analysis and image segmentation, spanning approximation algorithms [13, 60, 28, 20, 18. 17], more expressive formulations [7], and results in dynamic, online, parallel, and streaming settings [16, 15, 19, 3, 41, 51, 43). There has also been continued interest in developing heuristics [50, 1, 61, 66, 42, 6, 9]. We refer to the book by Bonchi al. [8] for more references.
Another closely related problem is that of (Unit) Interval Editing. Specifically, in (Unit) Interval Editing, the task is transform an unsigned graph into a (unit) interval graph using a minimum number of edge deletions and insertions. This problem is known to be NP-hard already since the seminal work of Garey and Johnson [27] and it is karammarrmeter tractable (FPT) when parameterized by the number of edge insertions and deletions [11, 33, 64, 12]. We further discuss the relation of BEST INTERVAL APPROXIMATION to these problems in Section 2.
Opinion formation models, such as the DeGroot model [24], the Friedkin model [26], or the mounded-confidencee model [38, 23), are also related. These models have recently received significant amount of attention in computer science and machine learning [53, 65, 67, 62] and assign real-valued opinion to each node in graph, which allows more fine-graine understanding of con- flicts than CORRELATION CLUSTERING. However, estimating the parameters of such models is highly
3

---

challenging and requires more information than the edge signs of a signed graph [5, 45, 44]. Thus, our method is more easily applicable as requires substantially less (and particularly less sensitive) data.
In relation to our case study on the German parliament, the also predicts ideological positions of legislators based co-voting data. It models legislators and roll-call votes as signed bipartite graph and applies -idimum--ikelhhood estimation to infer each legislator's ideological location in Iow-dimensional Euclidean space, together with Gaussian utility function centered at that point. However, since -NOMINAE operates on a bipartite graph, it is not applicable in more general social network settings where the input is given as unipartite graph. This is in contrast to our methods, which only require a unipartite signed graph as input.
algorithm [57, 58, 52]
Several related works consider versions of the CORRELATION CLUSTERING objective for partitioning signed graphs to reveal community structures [21, 40, 14, 54, 63]. However, similar to CORREL LATIONN CLUSTERING, these methods do not allow finding overlapping communities. Thus, they cannot explicitly consider individual tolerance of other opinions a way comparable to opinion intervals.
Further, Dwork al. [25] employed opinion intervals to analyze content moderation in online communities. They use them to study the effectiveness of moderation strategies on online platforms.
Preliminaries. A signed graph G = (V, E+ E is given by its vertices V, positive edges E+, and negative edges F where E+ n F = 0. It is complete if E+ U F = (2) For u E V, we write N+ to denote its neighbors in E+ and N (u) to denote its neighbors in E-
graph G (V, E) is an interval graph if can assign an interval L, R to all vertices e E V such that for all u, E V, it holds that {u, e) E E if and only if Iu n I, + 0. Additionally, we say that G unit interval graph if all intervals have length 1.
2 Problem Definition and Theoretical Results
In this section, we define our novel problem and state our main theoretical results.
Problem 2.1 (BEST INTERVAL APPROXIMATION), Given a signed graph G = (V, (V, E UE)), find Iet = [ C R: VJ of non-empty, contiguous intervals that maximizes
agree(G,I)
Σ
I(T 0 +0
Σ {a,
11104=
{u.o)EE+
where 1EE) is indicator function, which takes value 1 if E is true and 0 otherwise.
Intuitively, the problem assigns an interval I, to each vertex and asks that two intervals overlap their corresponding vertices are connected with positive edge and do not overlap if their vertices are
connected with a negative edge. connect this problem to opinions, we may consider an interval I for node e as the range of opinions that are acceptable to The length [ol can further be seen measure of v's tolerance towards the opinion spectrum to the left and to the right.
We will refer to the formulation in Problem 2. as the agreement version of BEST INTERVAL APPROXIMATION, which asks to satisfy as many edges as possible. We will also talk about the disagreement version, which aims to minimize the number of edges violating the interval assignment. Their complexity the same for exact solutions, but they differ w.r.t. approximation guarantees.
Relationship to CORRELATION CLUSTERING. Next, we observe that BEST INTERVAL. APPROXIMATION is expressive than CORRE- LATION CLUSTERING: First, consider any CORRELATION CLUSTER- ING solution Ci..... Cs. and consider k non-overlapping intervals Ii...., 4. Now we assign each vertex in C₂ to the same interval 4, Thus, if u, v E C, then their intervals overlap, and, if u E C₁ and C₁ for # j, then their intervals do not overlap. This implies that the optimal solution of BEST INTERVAL APPROXIMATION will always yield an agreement at least as large as for CORRELATION CLUSTERING. Second, our interval representation strictly more expressive and, for instance, allows us to model non-transitive node relationships and this property is illustrated Figure This is neither possible in CORRELATION CLUSTERING nor in the structural balance
U22
+
11
U3
2
Figure 2: A triangle with one negative edge and its (exact) interval representation.

---

theory of Harary [29], in both of which no eycle with exactly one negative edge can be represented without error.
The case of complete graphs and relationship to Interval Editing. G is complete signed graph then it can be represented without error in BEST INTERVAL APPROXIMATION if and only if G+ = (V, E+) is an interval graph. That is because missing edges in G correspond to negative edges in G (since G is complete). Thus, making the minimum number of edge deletions/insertions an interval graph is equivalent to flipping the minimum number of edge signs in G such that we have agreement for all edges. Hence, for complete graphs, we can rely on the rich literature on Interval Editing which asks for the minimum number of edge changes to G+ such that it becomes an interval graph. The results of Cao [10] now imply that BEST INTERVAL APPROXIMATION is FPT for complete graphs when only allowing a fixed number of sign changes (in one direction). However, in social networks this number will be large for real-world instances and thus these algorithms are not applicable in practice. Furthermore, our hardness results show that such FPT results are not possible in incomplete graphs when parameterized by the number of required edge deletions (see Section 2.
turn G into
2.1
Computational hardness
Next, we show that BEST INTERVAL APPROXIMATION is NP-hard. We show this by using a reduction from the NP-complete problem ACYCLIC DIGRAPH PARTITION [22], where we are given a directed graph H = (V, E) and have to decide whether one can partition V into two sets V1 and V2, such that both [V]] and H[V]] are directed acyclic graphs.
Our hardness result is stated below. In the theorem, we say that an interval representation conflict- free if it achieves agreement for all edges, i.e., if Equation (1) equals the number of edges in the graph. Further, we will consider the minimum number edge deletions required to make the graph conflict-free, which is identical to the optimal objective function value for the disagreement version of BEST INTERVAL APPROXIMATION.
Theorem 2.2. There exists polynomial-time algorithm that, given instance H = (V, E) of ACYCLIC DIGRAPH PARTITION, outputs an instance G = (V", F.+ E
EE) of BEST INTERVAL APPROXIMATION with the following properties: (1) H is a YES-instance if and only if conflict-free interval representation of G exists. (2) If H is a NO-instance, then only a single edge deletion is required to obtain a conflict-free interval representation G. (3) O(VV), |EtuE- (. and G = (V', E+) is a cycle. Thus, BEST INTERVAL APPROXIMATION NP-hard.
The theorem has several implications for BEST INTERVAL APPROXIMATION in incomplete graphs: (1) The disagreement version is hard to approximate within any factor. (2) It is not FPT when parameterized by the number of required edge deletions (unless P = NP), separating it from the problem in complete graphs. (3) The result holds even when restricted to graphs G (V", U E where G = (V', ) is a chordless cycle. This is intriguing because many algorithmic results on interval graphs rely on detecting forbidden induced subgraphs like chordless cycles of four more vertices [10, 64, 37]. Our hardness result implies that detecting these forbidden structures Nh-hard for incomplete signed graphs.
We prove Theorem 2.2 in Appendix A, where we construct a new graph G from an ACYCLIC DIGRAPII PARTITION instance !f, and show that G can be represented conflict-free if and only if H a YES-instance. In G. we introduce two auxiliary vertices and It and we show that all vertices whose intervals overlap with the interval of L (R) must be in partition V/2 (V2) in the optimal solution of ACYCLIC DIGRAPH PARTITION. Thus, the overlap structure of the intervals encodes a partition of the vertices of H. Crucially, partitions and the induced subgraphs H [V1] and H [V2), and we introduce further auxiliary vertices to ensure that G forms a cycle.
negative edges to enforce topological ordering over these
2.2 A PTAS for fixed is in complete graphs
From an algorithmic perspective, we provide a PTAS when G is a complete graph and when each vertex must be assigned to one of & intervals, where i = (1). Formally, we study version of BEST
'This is the case since minimizing the number of edges violating the interval assignment is equivalent to deleting minimum number of edges such that for the remaining graph (after the edges were deleted) there exists conflict- free interval representation.
5

---

INTERVAL APPROXIMATION in which we must find k intervals ,I....,II Is C R and each vertex V E V must be assigned to one of these intervals. In practice, the small number of intervals makes the results highly interpretable. Additionally, it applies to scenarios such as analyzing political votes, where we would like to have one interval representing each party, and the number of parties small. Our result for this restricted version of the problem is as follows.
Theorem 2.3. Let G be a complete signed graph and let E > 0, 8 > 0 and k E N be parameters. There exists an algorithm that, with probability at least 1 ö, returns (1 + =)-appooximate solution for BEST INTERVAL APPROXIMATION when the algorithm can only use k different intervals and it runs in time 201k² log(k/(e)))/=") .n.
The complete description and analysis of the PTAS are provided in Appendix B. An overview to obtain this result is as follows. Since & is fixed, we enumerate all possible choices of l intervals with respect to their overlap structure. Now, given a fixed set of & intervals, the main observation generalized instance of CORRELATION CLUSTERING where
is that this corresponds given k fixed clusters that might overlap. Specifically, when two clusters V, and V, overlap, we want their vertices to be connected by positive edges (rather than negative edges in the classic version of CORRELATION CLUSTERING). Then, we show that we can generalize a PTAS from Giotis and Guruswami [28] as described below.
We solve the generalized version of CORRELATION CLUSTERING by partitioning V into m = O(1/s) equally- sized subsets Vi....., Vm. Then, for each = 1, . m, proceed follows. We sample set of vertices St C V \ Vi of size Ô (1/=²) Now, we enumerate all possible assignments of S; into , S, where Sie S S; are the vertices assigned to interval I5, and for each such assignment, we greedily assign the vertices E V; to the interval that maximizes the agreement of w's edges to the clustering of S; given by (S,, S...). This process gives clustering of V, and we show how the clusterings of the Vi can be merged to obtain global clustering of V.
Our analysis is similar to that of [28] and shows that the sets S, are small enough such that enumerating all assignments is not too expensive, and simultancously large enough that for most vertices they give us a good estimate for the agreement of their edges w.r.t. fixed clustering. This is the key to arguing that the greedy assignment will yield good result when we consider the correct clustering of the S; In contrast to [28], we have to take into account the overlap of intervals when computing the estimates. As for [28], the approach does not extend to incomplete graphs or large k, since then the sets S; become too large and enumeration would not be possible anymore.
3 Heuristic Algorithms
Next, we present our heuristic Greedy Agreement Interval Assignment (GAIA) for BEST INTERVAL APPROXIMATION, which is given intervals I1...., Ig as input to which all vertices must be assigned.
We use the following notation. For an interval Ie we let overlap(f) {l': : Ie O Ie * 0} denote the set of intervals 4r that overlap with 1,. Furthermore, we will consider disjoint vertex clusters .i....: Cs S V that correspond an assignment of the vertices to the intervals, i.e., C2 contains all vertices assigned to interval Tt. Now, for a vertex and C1,..., C as before, we write
agree(u, l, (CI,... Ct))= =
Σ (N+ n + Σ IN
E' ('Eoveraa(())
('goverla(())
for the number of agreeing edges when assigning vertex interval Ie for the clustering Ci...., Ck-
Now, we describe GAIA and state its pseudocode in Algorithm 1. GAIA is based on iterative refinement: After computing an initial greedy assignment of all vertices, the solution is improved by reassigning vertices in multiple epochs. This reassignment procedure is carried out in batches to avoid local minima. In each epoch, the vertex set is partitioned into random batches Vi,..., Vn. and the algorithm iterates over these batches one at a time. When processing a batch V,, all vertices in the batch are first unassigned and then reassigned using the greedy procedure described below. This can be viewed as a practical version of PTAS from Theorem 2.3, where, instead of crute-forcing solutions on out-of-batch vertices, the algorithm leverages the previously constructed greedy solution.
The core of GAIA is the greedy assignment of vertices in V; to intervals in Line 5-8 in Algorithm 1. Here, each vertex E V, is assigned to the interval 1ę (and its corresponding cluster Cş) that

---

Algorithm 1: Greedy Agreement Interval Assignment (GAIA)
Input:
Signed graph G (V,E+ U E
intervals 4......44
Output: Interval assignment (C1,.... C.) where Ct are the vertices assigned to interval 15
1
Compute an initial assignment of the vertices to the intervals; for each epoch do Randomly partition V into m sets Vi,..., . Vn of size " each;
3
for = I..... m do
Ce Ce V; for all 8 L..... k; for U E V₂ in order of maximum agreement do f argmax-=1... agree(v, (C1, (C.,...... Ck));
// Unassign all vertices in Vi
8
Ce + (b);
// Assign v to I
return (R),
maximizes agree(v, e, .Ci...., Ck)) (breaking ties at random). Crucially, we assign the vertices with the highest agreement values first, as these vertices are easier to assign and their assignment provides more information when assigning later vertices.
We also provide a version of GAIA called Variable ENergy Uphill Search (VENUS), which additionally uses simulated annealing [36] further increase the variability of its solutions. In VENUS, vertices are not necessarily assigned to the interval that maximizes agree(v, é, (Ci,... C&)), but instead, each vertex assigned to an interval selected probabilistically according to a temperature-scales softmax distribution over agreement values. To that end, Line 7 of Algorithm is replaced with É softmax agree(v.E[(C,....c
Here, is temperature parameter and controls the level of randomness during the assignment. A temperature t close to 0 corresponds to more greedy approach, while higher temperatures lead increasingly uniform random assignments. The annealing schedule follows exponential decay: the temperature is initialized at to and multiplied by a decay factor (0, 1) after every r epochs. This gradually reduces randomness and encourages convergence.
4 Experiments
Next, we experimentally evaluate our algorithms. Our code is available in GitHub repository." 2 We aim answer the following research questions:
(RQ1) Does BEST INTERVAL APPROXIMATION yield a substantial increase in expressiveness compared to CORRELATION CLUSTERING?
(RQ2) How computationally efficient and scalable are our proposed algorithms?
(RQ3) What is the trade-off between solution quality and the number of intervals?
(RQ4) Are the solutions produced by our method interpretable?
(RQ5) Are our algorithms able to recover ground-truth interval structures?
We evaluate our algorithms on real-world datasets from SNAP [46] and KONECT [39]. We further provide a novel dataset based on voting data from the German Bundestag (parliament) between the years of 2012 and 2025 and make it available in repository. In this dataset, each Bundestag member corresponds to a vertex in the graph, and two members are connected by positive edge if they vote the same way in least 75% of the sessions they both attended. Conversely, they are connected by a negative edge if their votes align in 25% of sessions or less.
In experiments, evaluate our base algorithm, GAIA, as well the VENUS variant that simulated annealing. For VENUS, we use an initial temperature of 100 and a decay factor of 2/3, applied every 5 epochs. Both are with 10 batches for vertex reassignment. For the interval structure that our algorithms receive as input, unless stated otherwise, we use a chain-like structure of 8 intervals, where each interval overlaps with the next, e.g., [0, 1), [1, 21, .... [7, 8). and we call this interval structure an 8-Chain. This structure was chosen to find a trade-off between increased
Patpss//github..om/Pecc http://htbb.oomtttteeeBnneisseii ooppooooooiiiiiooooiiiiooooooooo ipppiiooonnnntiiiniiall intervals
7

---

Table 1: Overview of the best solutions found by the algorithms. Reported is the percentage (%) of edges violated (lower is better). Our algorithms use the 8- 8-Chain interval structure while the CORRELATION CLUSTERING algorithms use unrestricted number of clusters.
Our algorithms
CORRELATION CLUSTERING baselines
Dataset
[V]
[B]
LET [2T
GATA
VENUS
GAEC
GABCKL.
SCHLEVo
RAMA
Improvement
BitcoinOTC
5.881
21 434
0.85
3.32
3.55
5.58
5.57
5.57
5.64
40.39%
Chess
73301
32650
0.58
19.82
19.63
28.64
28.10
27.33
39.98
28.17%
WikiElec
715
100.35
0.78
11.24
11.26
14.13
141.13
14.13
14:455
20.45%
Bundestag
0.25
3.06
91.53%
Slashdot
82 1410
498 532
0.76
9.05
8.94
13.75
13.66
13.52
17.17
33.88%
Epinions
131 580
708 507
0.83
1.47
4.42
6.83
6.68
6.67
6.96
33. 33.73%
WikiSigned
138-587 587
712
0.88
4.94
4.85
6.17
6.17
6.17
6.96
21.39%
WikiConflict
116888
20140533
0.38
3.44
3.43
5.87
5.82
5.82
6.02
41.06%
expressivity and intuitive interpretation (see also discussion of RQ3 below). Where applicable, experiments were repeated 50 times on different random seeds, and standard deviations are reported.
Numerous approaches have been proposed for solving CORRELATION CLUSTERING in social networks analysis [49, 9, 31, 30] and in computer vision [35, 66, 42, 1]. To provide a representative performance overview, we selected four state-of-the-art algorithms for comparison:
GAEC [35]: A method that incrementally merges clusters to minimize disagreement.
GAECKLj [35]: An extension of GAEC that additionally applies local search postprocessing.
SCMLEvo [30]: An algorithm combining multilevel local search with evolutionary techniques.
RAMA [1]: An algorithm using polyhedral relaxation and message passing to guide cluster merging.
For each of these algorithms, we run the authors' publicly available implementaiinns. In contrast to algorithms, which only use 8 intervals, the baselines may use an unrestricted number of clusters.
Throughout our experiments, we report the disagreement, i.c., the fraction of violated edges in solutions found across all real-world datasets (rather than the number of agrecing edges in Equation (I)), as this makes the algorithms' performance casier to compare. Further details on the experiment setup, well as additional results, are described in Appendix C.
Expressivity analysis (RQI). To compare the expressivity of BEST INTERVAL APPROXIMATION with CORRELATION CLUSTERING, we run our algorithms and the baselines on the real-world datasets. The results in Table show that our algorithms consistently find interval assignments that achieve 20% to 90% fewer disagreements than the best CORRELATION CLUSTERING solution. Across all datasets, our results have 38% less disagreement on average, even though our methods only use 8 intervals, whereas the CORRELATION CLUSTERING baselines of clusters. Hence, our heuristic algorithms manage to effectively use the increased expressivity of the overlapping interval structure. Additionally, find that VENUS tends to outperform GAIA slightly, particularly for larger graphs.
unrestricted number
Computational efficiency (RQ2). Next, we assess the runtime efficiency of our algorithms by tracking the progression of the objective value over time. Representative results for Slashdot are presented in Figure 3a. GAIA makes the most progress in the first 15 seconds, followed by slower, incremental gains. VENUS exhibits a similar pattern, though slightly delayed, likely due temperature which slows early convergence. However, this high initial temperature appeared to be necessary to achieve improvement over GAIA's 's results. In most instances, both hcuristics stopped after 50 epochs without improvement in the first five minutes of runtime, with GAIA often terminating after a few seconds. The algorithms' running time until convergence scales approximately linearly in the number of edges and on all datasets our methods terminate within 30 minutes; we also elaborate on this in the appendix.
initially high
Number of intervals (RQ3). To investigate the relationship between the number of intervals and solution quality, we ran our algorithms with 4, 8, 12, and 16 intervals. As for the 8- E-Chain, in each interval structure, every interval overlaps with its successor and predecessor. In Figure 3a, we illustrate the convergence behavior, and Figure 3b presents the solution quality after convergence, both on the Slashdot dataset. Our results show that using only intervals leads to poor solution quality

---

Disagrement
55k
Disagreement
55k
50k
50k-
45k
45k-
0s
25s
50s
75s
100s
125s
16
Runtime
Number of Intervals
Algorihhm Number of Intervals
GAIA
VENUS
Algorithm
GAIA
VENUS
12
(a) Objective value over time.
(b) Final objective for different interval structures.
Figure 3: Performance of our algorithms with different configurations on the Slashdot dataset.
compared to the higher numbers, suggesting that such limited structure may not adequately capture the complexity of the graph. While the solution quality improves with more intervals, 8 intervals seem sufficiently expressive for this graph, with only marginal improvements beyond that. This behavior is typical for other problem instances as well. Again, we see that VENUS tends to perform slightly better, and most notably, its results have much less variance compared to GAIA.
Interpretability (RQ4). To study the interpretability of our solutions, we perform a case study on the Bundestag dataset. We present representative solution found by VENUS in Figure 1. As the dataset models co-voting behavior of politicians, we expect our interval representation to resemble the German political spectrum, and, indeed, this the case. Our result assigns most members from the same party to the same or neighboring intervals. For each party, except the FDP, we can identify one interval consisting mainly of members of that party. We note that the slight splitting up of parties is natural due to government coalitions they formed throughout the years. Also, the behavior of the FDP can be traced back to different coalition governments they were part of (they formed governments with the conservative CDU/CSU, as well as with the left/center GRÜNE and SPD). We consider the ability of our algorithms extract such highly overlapping structure as a substantial improvement over CORRELATION CLUSTERIIGG and this is also emphasized by the objective function values reported in Table where our methods have 91% % fewer disagreeing edges on this dataset.
Reconstruction of ground-truth data (RQ5). Next, we evaluate our algorithms on synthetic data. We fix the 8- G-Chain and generate graph with n 800 vertices as follows. We assign a vertices each interval, and we introduce edges with signs corresponding to the interval structure for d(") random pairs of vertices, where d E [0, 1] is the desired density of the graph. Each edge obtains correct edge sign based on the interval structure with probability 1 and we flip the sign with probability In our experiments, we measure the relative change of the objective function achieved by our algorithms agreei G.ouddd aaatie--ggeeeGG... (AALG) 100, and we
compared to the ground-truth assignment in percent,
also report the accuracy with which vertices are assigned to their corresponding interval.
Figure 4 shows the result of our experiments. Without sign noise, the solutions always within 6.5% of the ground truth for VENUS, and within 12.5% the ground truth for GAIA. We also obtain a high accuracy in reconstructing the ground-truth assignment. With increasing sign noise, the true solution becomes increasingly suboptimal to the point where both GAIA and VENUS find alternative solutions, with better objective values than the ground truth (this is the case when we have negative y-axis values in the plot). This increased objective value, however, comes at the cost of less accuracy in the vertex assignment. The point which alternative solutions become viable depends heavily on the density of the graph, with denser graphs being more resilient to this phenomenon.
5 Conclusion
We introduced the BEST INTERVAL APPROXIMATION problem and showed that is more expressive than CORRELATION CLUSTERING, both theoretically and in experiments. We gave strong hardness results for incomplete graphs, as well PTAS for complete graphs and fixed k. We also provided efficient heuristics, which find interval assignments with significantly better objective values than CORRFLATION CLUSTTERING solutions found by state-of-the-art algorithms, and we showed that these interval assignments are highly interpretable.

---

10
0
Diference
-10-
-10-
-10-
-10-
-20-
-30-
330-
0.1
0.2 0.3 0.4 0.5
0
0.1
0.2 0.3 0.4 0.5
0.1
0.2 0.3 0.4 0.5
0
0.1
0.2
0.3 0.4 0.5
Sign Flip Probability Density: 0.01
Sign Probability Density: 0.03
Sign Flip Probability Density: 0.1
Sign Flip Probabiity
Density:
1.00
1.00-
1.00
1.00
Accuracy
0.75
0.75
0.75
0.75
0.50
0.50
0.50
0.50
0.25
0.25
0.25
0.25
0.00
0.00
0.00
0.1
0.2
0.3 0.4 0.5
0.1 0.2 0.3 0.4 0.5
0.1
0
0.1 0.2 0.5
Sign Flpp Probabiliy Density: 0.01
Sign Flip Probability Densily: 0.03
Sign Flip Probability Densily: 0.1
Sign Flip Probability Density: 1
GAIA
VENUS
Random Assignment
Figure 4: Results on synthetic data. For different edge density levels EE] ((2), we report the nor-
malized difference (grree(G,gromne truth) -ggeee)) averaged over 50 runs, and standard deviations. E
Negative numbers indicate an improvement over the ground truth. Further, we report the accuracies of the solution with the lowest disagreement. GAIA and VENUS reconstruct the ground truth under considerable levels of noise in dense graphs, and find alternative, better solutions sparse graphs.
We believe there several interesting directions for future work, which we describe next.
From a more theoretical point of view, several problems remain unresolved. First, we conjecture that in the agreement version of the problem (for k not fixed), the optimal solution can always satisfy a 1 3-fraction of the edges. This claim supported by sooltsoltions that we computed on small instances, and it is tight, for instance, when taking two cliques with negative edges and connecting each pair of their vertices with positive edge. Second, it is interesting to study whether a PTAS exists in this setting. Third, our hardness results do not allow us to rule out that for fixed k and complete graphs a PTAS exists for the disagreement version of our problem. While the techniques of Giotis and Guruswami [28] for CORRELATION CLUSTERING do not seem to extend to this setting, obtaining such a result would be interesting.
From a modeling perspective, several extensions are well-motivated. First, natural extension is to move beyond miedimmesional intervals. Interestingly, neither our PTAS nor our heuristic algorithms are inherently restricted to intervals on line. Rather, they only require knowledge of which clusters overlap and which do not. Hence, an empirical study using higher-dimensional intervals could allow more nuanced discovery of opinions along multiple axes. Second, it might be interesting to consider temporal or dynamic settings which opinion ranges expand or contract over time. Here, one could consider making the opinion intervals expand or contract depending on the nodes' centrality or the homophily their immediate neighborhood.
From a machine learning perspective, it is interesting to study whether methods like GNNs can outperform our algorithms. This might be particularly promising when additional information, such as node labels, are available, which can be exploited by the GNNs.
Acknowledgments and Disclosure of Funding
The authors thank the anonymous reviewers for their helpful comments, which have helped us to improve the presentation of the paper. We further thank Sebastian Lüderssen for useful discussions.
This research has been funded by the Vienna Science and Technology Fund (WWTF) [Grant ID: 10.47379/VRG233133 the ERC Advanced Grant REBOUND [834862]. the Swedish Research Council (VR) [2024-056033 the European Commission MSCA DN ARMADA [101 168951], and the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation.
10

---

References
[1] A. Abbas and Paul Swoboda. Rama: rapid multicut algorithm on gpu. CVPR, pages 8183-8192, 2021.
[2] Samin Aref and Zachary P. Neal. Identifying hidden coalitions in the us house of representatives by optimally partitioning signed networks based generalized balance. Scientific Reports, 11, 2021.
[3] Sepehr Assadi, Vihan Shah, and Chen Wang. Streaming algorithms and lower bounds for estimating correlation clustering cost. In NeurIPS, 2023.
[4] Nikhil Bansal, Avrim Blum, and Shuchi Chawla. Correlation clustering. Mach. Learn., 56(1-3): 89-113, 2004.
2004.
[5] Pablo Barberá. Birds of the same feather tweet together: Bayesian ideal point estimation using twitter data. Political analysis, 23(1):76-91, 2015.
[6] Thorsten Beier, Thorben Kröger, Jörg H. Kappes, U. Köthe, and Fred A. Hamprecht. Cut, glue, cut: fast, approximate solver for multicut partitioning. CVPR, pages 73-80, 2014.
[7] Francesco Bonchi, A. Gionis, and Antti Ukkonen. Overlapping correlation clustering. Knowl- edge and Information Systems, 35:1-32, 2011.
[8] Francesco Bonchi, David Garcfa-Soriano, and Francesco Gullo. Correlation Clustering. Syn- thesis Lectures on Data Mining and Knowledge Discovery. Springer, 2022.
[9] Michael J. Brusco and Patrick Dorcian. Partitioning signed networks using relocation heuristics, tabu search, and variable neighborhood search. Social Networks, 56:70-80, 2019.
[10] Yixin Cao. Linear recognition of almost interval graphs. In SODA, pages (096-1115,_) 2016. 2016.
[11] Yixin Cao. Unit interval editing is pard-pprameter tractable. Inf. Comput., 253:109-126,, 2017.
[12] Yixin Cao and Dániel Marx. Interval deletion is fixed fixedparameete tractable. ACM Truns. Algorithms, 11(3)21:1-21:35, 2015.
[13] Moses Charikar, Venkatesan Guruswami, and Anthony Wirth. Clustering with qualitative information. FOCS, pages 524-533, 2003.
[14] Kai-Yang Chiang, Joyce Jiyoung Whang, and Inderjit S. Dhillon. Scalable clustering of signed networks using balance normalized cut. In CIKM, pages 615-624, 2012.
[15) Vincent Cohen-Addad, Silvio Lattanzi, Slobodan Mitrovic, Ashkan Norouzi-Fard, Nikos Parot- sidis, and Jakub Tarnawski. Correlation clustering in constant many parallel rounds. In ICML, volume 139, pages 2069-2078, 2021.
[16] Vincent Cohen-Addad, Silvio Lattanzi, Andreas Maggiori, and Nikos Parotsidis. Online and consistent correlation clustering. In ICML, volume 162, pages 4157-4179, 2022.
[17] Vincent Cohen-Addad, Euiwoong Lee, and Alantha Newman. Correlation Clustering with Sherali-Adams. In FOCS, pages 651 651-661, 2022.
[18] Vincent Cohen-Addad, Euiwoong Lee, Shi Li, and Alantha Newman. Handling correlated rounding error via preclustering: A 1.73-approximation for correlation clustering. In FOCS, pages 1082-1104, 2023.
[19] Vincent Cohen-Addad, Silvio Lattanzi, Andreas Maggiori, and Nikos Parotsidis, Dynamic correlation clustering in sublinear update time. In ICMI., 2024.
[20] Vincent Cohen-Addad, David Rasmussen Lolck, Marcin Pilipezuk, Mikkel Thorup, Shuyi Yan, and Hanwen Zhang. Combinatorial correlation clustering. In STOC, pages 1617-1628. ACM, 2024.
11

---

[21] Mihai Cucuringu, Peter Davies, Aldo Glielmo, and Hemant Tyagi. SPONGE: A generalized cigenproblem for clustering signed networks. In AISTATS, volume 89, pages 1088-1098. PMLR, 2019.
[22] Marek Cygan, Marein Pilipezuk. Michal Pilipezuk, and Jakub Onufry Wojtaszczyk. Sitting closer to friends than enemies, revisited. Theory Comput. Syst., 36:394-405, 2015.
[23] Guillaume Deffuant, David Neau, Frederic Amblard, and Gérard Weisbuch, Mixing beliefs among interacting agents. Advances in Complex Systems, 3(01n04):87-98, 2000.
[24] Morris H DeGroot. Reaching a consensus. J Am Stat Assoc, 69(345):118 121, 1974.
[25] Cynthia Dwork, Chris Hays, Jon M. Kleinberg, and Manish Raghavan. Content moderation and the formation of online communities: A theoretical framework. In WWW, pages 1307-1317. ACM, 2024.
[26] Noah E Friedkin and Eugene C Johnsen. Social influence and opinions. Journal of Mathematical Sociology, 15(3-4):193-222 193-206, 1990.
[27] M. R. Garey and David S. Johnson. Computers and Intractabilityy A Guide to the Theory of NP-Com VPpCComlettness. W. H. Freeman, 1979. ISBN 0-7167-1044-7.
[28] Ioannis Giotis and Venkatesan Guruswami. Correlation clustering with a fixed number of clusters. Theory Comput., 2(13):249 266, 2006.
[29] Frank Harary. On the notion of balance of a signed graph. Michigan Mathematical Journal, 2 (2):143-146, 1953.
[30] Felix Hausberger, Marcelo Fonseca Faraj, and Christian Schulz. Scalable multilevel and memetic signed graph clustering. ALENEX, pages 81-94, 2025.
[31] Jia-Lin Hua, Jian Yu, and Minn-She Yang. Fast clustering for signed graphs based on random walk gap. Social Networks, 60:113-128, 2020.
[32] Kevin G. Jamieson and Amect Talwalkar. Non-stochastic best arm identification and hyperpa- rameter optimization. In AISTATS, pages 240-248, 2016.
[33] Haim Kaplan, Ron Shamir, and Robert Endre Tarjan. Tractability of parameterized completion problems on chordal, strongly chordal, and proper interval graphs. SIAM J. Comput., 28: 1906-1922, 1999.
[34] Anne-Marie Kermarrec and Christopher Thraves. Can everybody sit closer to their friends than their enemies? In MFCS, pages 388-399, 2011.
[35] Margret Keuper, Evgeny Levinkov, Nicolas Bonneel, Guillaume Lavoué, Thomas Brox, and Bjoern Andres. Efficient decomposition of image and mesh graphs by lifted multicuts. ICCV, pages 1751-1759, 2015.
[36] Kirkpatrick, C. D. Gelatt, and M. Vecchi. Optimization by simulated annealing. Science, 220(4598).671-680, 1983.
[37] Dieter Kratsch, Ross M. McConnell, Kurt Mehlhorn, and Jeremy P. Spinrad. Certifying algorithms for recognizing interval graphs and permutation graphs. SIAM J. Comput., 36(2): 326-353, 2006.
[38] UIrich Krause. A discrete nonlinear and non-autonomous model of consensus formation. Communications in Difference Equations, 2000, 07 2000. doi:
[39] Jérôme Kunegis. Konect: the koblenz network collection. www. 2013.
[40] Jérôme Kunegis, Stephan Schmidt, Andreas Lommatzsch, Jürgen Lerner, Ernesto William De Luca, and Sahin Albayrak. Spectral analysis of signed graphs for clustering, prediction and visualization. In SDM, pages 559-570. SIAM, 2010.
12

---

[41] Yuko Kuroki, Atsushi Miyauchi, Francesco Bonchi, and Wei Chen. Query-efficient correlation clustering with noisy oracle. In NeurlPS, 2024.
[42] Jan-Hendrik Lange, Andreas Karrenbauer, and Bjoemn Andres. Partial optimality and fast lower bounds for weighted correlation clustering. In ICML, volume 80, pages 289222900) 2018.
[43] Silvio Lattanzi, Benjamin Moseley, Sergei Vassilvitskii, Yuyan Wang, and Rudy Zhou. Robust online correlation clustering. In NeurIPS, pages 4688-4698, 2021.
[44] Jacopo Lenti, Corrado Monti, and Gianmarco De Francisci Morales. Likelihood based methods improve parameter estimation in opinion dynamics models. In WSDM, pages 350-359, 2024.
[45] Jacopo Lenti, Fabrizio Silvestri, and Gianmarco De Francisci Morales. Variational inference of parameters in opinion dynamics models. CoRR, abs/2403.05358. 2024.
[46] Jure Leskovee and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http://saap.saanfor..cm .dwu/data, June 2014.
[47] Jure Leskovec, Daniel P. Huttenlocher, and Jon M. Kleinberg. Predicting positive and negative links in online social networks. In WWW, pages 641-650, 2010.
[48] Jure Leskovec, Daniel Huttenlocher, and Jon M. Kleinberg. Signed networks in social media. In CHII, pages 1361-1370, 2010.
[49] Evgeny Levinkov, Alexander Kirillov, and Bjoern Andres, A comparative study of local search algorithms for correlation clustering. In German Conference on Pattern Recognition, 2017.
[50] Mário Levorato, Rosa Figueiredo, Yuri Frota, and Lúcia M. A. Drummond. Evaluating balancing on social networks through the efficient solution of correlation clustering problems. EURO Journal on Computational Optimization, 5:467-499. 2017.
[51] Konstantin Makarychev and Sayak Chakrabarty. Single-pass pivot algorithm for correlation clustering. keep it simple! In NeurlPS, 2023.
[52] Nolan McCarty, Keith T. Poole, and Howard Rosenthal. Income redistribution and the realign- ment of American politics. AEI Press, 1997.
[53] Cameron Musco, Christopher Musco, and Charalampos E. Tsourakakis. Minimizing polariza- tion and disagreement in social networks. In WWW, pages 369-378, 2018.
[54] Stefan Neumann and Pan Peng. bublinear-time clustering oracle for signed graphs. In ICML, volume 162, pages 16496-16528, 2022.
[55] Eduardo G. Pardo, Mauricio Soto, and Christopher Thraves. Embedding signed graphs in the line heuristics to solve minsa problem. J. Comb. Optim., 29:451-471, 2015.
[56] Eduardo G. Pardo, Antonio Garcfa- Sánchez, Mare Sevaux, and Abraham Duarte. Basic variable neighborhood search for the minimum sitting arrangement problem. J. Heuristics, 26:249 2688 2020.
[57] Keith T. Poole and Howard Rosenthal. Patterns of congressional voting. American Journal of Political Science, 35:228, 1991.
[58] Keith T. Poole and Howard Rosenthal. Congress: A Political-Ecoommic History of Roll Call Voting. Oxford University Press, 1997.
[59] Fred S. Roberts. Indifference graphs. Proof Techniques in Graph Theory, pages 139-146, 1969.
[60] Chaitanya Swamy. Correlation clustering: maximizing agreements via semidefinite program- ming. In SODA, 2004.
[61] Paul Swoboda and Bjoemn Andres. A message passing algorithm for the minimum cost multicut problem. CVPR, pages 4990-4999, 2016.
[62] Sijing Tu and Stefan Neumann. A viral marketing based model for opinion dynamics in online social networks. In WWW, pages 1570-1578, 2022.
13

---

[63] Ruo-Chun Tzeng, Bruno Ordozgoiti, and Aristides Gionis. Discovering conflicting groups in signed networks. In NeurIPS, 2020.
[64] Yngve Villanger, Pinar Heggernes, Christophe Paul, and Jan Arne Telle. Interval completion fixed parameter tractable. SIAM J. Comput., 38(5):0077-2020, 2009.
[65] Yanbang Wang and Jon M. Kleinberg. On the relationship between relevance and conflict in online social link recommendations. NewrIPS, 2023.
[66] Steffen Wolf, Constantin Pape, Alherto Bailoni, Nasim Rahaman, Anna Kreshuk, U. Köthe, and Fred A. Hamprecht. The mutex watershed: Efficient, parameter-free image partitioning. In ECCV, 2018.
[67] Liwang Zhu, Qi Bao, and Zhongzhi Zhang. Minimizing polarization and disagreement in social networks via link recommendation. NeurlPS, pages 2072-2084, 2021.
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The claimed theoretical results are formalized in Section with additional proof' in Appendices A and B. The heuristic algorithms are described in Section 3, and the claimed empirical results are supported in Section 4.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Our theorems clearly state the assumptions that are necessary for them to hold. Regarding the performance of our practical algorithms, have evaluated them the best of our knowledge and also provide further information on their scalability in the appendix.
3. Theory assumptions and proof'
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: For each theoretical result (Theorems 2.2 and 2.3) we clearly state assumptions and provide proof sketches in Section 2. Formal proofs provided in Appendices A and B and cross-referenced to T'eeorems 2.2 and 2.3, respectively.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: The heuristic algorithms described in Section 3, the dataset generation process and the parameters used to run the experiments are described Section and Ap- pendix C. Additionally, our code is available in GitHub repository.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Our code, including the experiment setup, is available GitHub repository, referenced in Footnote 2 in Section 4. All datasets used are either publicly available or included in the linked repository.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
The parameters used to run all experiments are described in Section 4 and Ap- pendix Additionally, the code to reproduce our experiments available in a GitHub repository.
Justification:
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
15

---

Justification: All experimental results in Section 4 and Appendix C include averages, standard deviations, and confidence intervals where applicable. In the box plots. the notches extend 1.58 TQR/ n, giving roughly 95% confidence interval for comparing medians.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: (Yss]
Justification:
The computer resources used the experiments are described in Appendix C.
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
The authors have ensured that the research conducted in the paper conforms, in every respect, with the NeurIPS Code of Ethics
Justification:
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
We believe that our work has no broader societal impact, given that focus is on foundational research. While we offer a new perspective on modeling opinion diversity using limited interaction data, similar insights are already frequently obtained in the real world by existing methods using richer user-level data.
Justification:
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We cite all original papers where code or datasets used in work. In particular, for the scraped Bundestag dataset, we provide copyright- and legal notice in the GitHub repository.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The generation process for the newly introduced dataset is described in Section 4. The dataset and the code used for its generation are available a GitHub repository.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and sereenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
16

---

Justification: No crowdsourcing experiments with human subjects were used in the paper.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country institution) were obtained?
Answer: [NA]
Justification: No crowdsourcing experiments with human subjects were used in the paper.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration not required.
Answer: [NA]
Justification: LLMs were not involved in the core method development.
17

---

A Hardness Result
In this section, we prove our hardness result from Theorem 2.2. In the proof, we use the notation I= r()), where ((T) denotes the infimum and r(7) denotes the supremum of the interval.
A.1 Construction
We describe reduction from instance H E) of ACYCLIC DIGRAPH PARTITION to instance G = (V", E+ U E-) of BEST INTERVAL APPROXIMATION, where (V", FF+) forms a cycle.
First, the set of vertices V consists of:
These vertices will be used to constrain the structure of the solution. With of negative edges, will force any conflict-rre representation to assign each vertex in to a sub-interval of either L or R. The names of the vertices stand for start, left, middle, right, target, help-start, and help-target, respectively.
Seven constant vertices V = H,,,
2. Four vertices for each vertex o V: V = {M.: Au, X,, B. where X, corresponds to the original vertex in H and the other vertices are used to structure the instance.
Next, we define the set of positive edges E+ to form a cycle over V'. For this, we use an arbitrary ordering of V ......., ) and construct E+ as the union of the following sets:
1. E = ([S, (1, M), (M, RJ, Th (s, Hs), TH
2. for all V: E = ([M,, A, (Aa, X,), {X,, B.}}
3. E+ = iils, Mr,H }} noce[i,n-1]00 -i M H U ((Br,, HT}}
Finally, construct F- as the union of the following sets:
1. Fg = (1S, :' EV" {I, Hs},. FT = (( VV' (R, Hr]} HR)
We connect negatively S and T each vertex in the graph besides their positive neighbors. This forces 1s and !r to be the outermost intervals in any conflict-free interval representation. as otherwise the interval of some negatively connected vertex intersects either of them. See Lemma A.1. To break symmetry, we assume without loss of generality that r r(Is) < E(Tr).
2. E- = ([LRR)
This edge ensures that It and In are disjoint, and in any conflict-free representation, r(lr) < {(IR), due to their respective positive edges to S and T.
3. Σ = -'vvv {M L}, {M,, R}}
These edges ensure that for all vertices E V the interval IM, lies in IM. See Lemma A.3.
4. E- ((X., M) U V}
These edges ensure that for all vertices v E V, the interval Ix, either lies in Jr. or in LR- See Lemma A.4.
5. EV [(Xu; u V. V, These edges ensure that for all vertices u, u E V with u + v the intervals Ix., and Ix, are disjoint.
6. EE = Ul. (( (X,, B.}}
These edges enforce topological orderings of the vertices. See Lemma A.5.
This concludes the construction. We refer to Figure 5 for an illustration. It is clear that V E+ and E have the sizes claimed in the theorem.
A.2 Structural lemmas
To prove the correctness of the reduction, we will make use few smaller results that describe the structure of any conflict-free interval representation of G. First, notice that (S, 7) E E-, so for any conflict-free interval representation, it must hold that 7s O Ty 0. For the rest of this analysis, assume without loss of generality r(ls) < ((IT).
18

---

M
R
T
U1
1/2
Hs
V1
V2
21 {
02
U4
U/
1/3
U4
HT
(a) Directed graph instance for ACYCLIC DI-
GRAPH PARTITION
(b) Interval representation
Figure 5: Reduction from ACYCLIC DIGRAPH PARTITION
Lemma A.1. For any conflict-free interval representation of G it must hold that for all u E V (S):
r(ss) < r(La) and for all V (T) E(Lw) < ((IT).
Proof. Towards contradiction assume there exists vertex V {(S} such that r(w) S r([s). As (V', E+) is cycle, there exists path from w to that does not include S. The union T, of the intervals corresponding to the vertices in this path must form interval itself. As r(Ta) S r(gg), but ((TT) > r(Ts), Is n I, + 9, and consequently there exists some vertex x E V (S), + along this path such that 1s La of O. Note that by the construction of this path, cannot be positive neighbor of S, as we explicitly choose one of the two paths from u to T that does not include S. Then, {S, E E leading to contradiction. Finally, for all V (T} ((h.) < ((IT) holds by symmetric argument.
Lemma A.2. For any conflict-free interval representation of G it must hold that (i) for all u V' V Hs) r(Is) < E(T.) and (ū) for all u E V' {T, Rt Hr} r((.) < E(IT).
Proof. Assume towards a contradiction that there exists a vertex a E V \ {S, L, Hz} such that ((Iw) I <r(ss. From Lemma A.1, we know r(Iw) r(Is). so it follows that Ia I # 0. However, since {S. u} E E- this leads to a contradiction with the assumption of a conflict-free interval representation. The proof for (ii) follows symmetrically.
Lemma A.3. For any conflict-free interval representation of G, it must hold that for all E V: IM. C Ias-
Proof. By construction, the open interval (r(Ts), (((Ts),((TT) C UT U From Lemma A.2, we
know that IM, It U IM U In. Finally, (Ma, L), (M,, R) E the claim holds.
L
Lemma A.4. For any conflict-free interval representation of it must hold that for all v V either Ix. C. 1L or Ix, C. IR but not both.
Proof. By construction, the open interval (r(T)),((TT) C Ir U U Jn. From Lemma A.2, we know that Tx_ C UT. U Tn. Furthermore, we know that Jr. n In 0. Finally, (X., M) E the claim holds.
Building on this statement, we can further characterize the relative location of the intervals Ix, inside Ir and LR-
Lemma A.5. For any conflict-free interval representation of G it must hold that for all edges vu, E Ix, C In and Ix, C TR. then r(Ix.) < {(Tx.), and, symmetrically, if Ix., Ir. and Ix. II, then r(xx.) E(Ix.)
Proof. As we assumed that r(Is) < ((Ir, it follows that {(IM) < ((IR) S r(Ix) < r(IR). Towards a contradiction, assume there exists an edge (u,v) E E such that Ix, C In and Ix, c TR. but ((xx.) < r(Tx,)) As in any conflict-free interval representation the intervals Ix, and Ix. are disjoint, this implies that r(xx.) < {(Tx.)) Now, consider the intervals TM. and LA,-
From Lemma A.3, we know that I IM. C. IMs hence r(lM.) < ((Ix.) < r(Ix.) < ((xx.). By
19

---

construction, LA, must overlap with IM. and xx.. hence P(TA.) I <r([,,)) and r(La.) 2 ((xx.) However, this implies that A.. nix, * 9. leading a violation of the {-x,, Au) constraint introduced in EE. By symmetry, this also proves the case where Lx, C 1t and 1x, C Lt.
A.3 Proof of Theorem 2.2
Equipped with Lemmas A.I I to A.5 we can now prove Theorem 2.2.
We first show that if H (V, E) is YES-instance of ACYCLIC DIGRAPH PARTITION, then the constructed signed graph instance G has conflict-free
in BEST INTERVAL APPROXIMATION. Assume [V]] and [V2] are the two acyclic induced subgraphs of H corre- sponding to the partition and let k = [Vil. Further, let [I(,,1)..... ((1,))) and (l(2.1),.... .. (1) be topological orderings of Vi and 1/2 respectively, Now, we define intervals for Vi as follows and depicted Figure 5:
Is = 0.2]. J = [0.2, 0.4], Is = [0.4,0.6), I = [0.6, Ir = [0.8, 11. Iss = [0.1, 0.5), IH, = [0.5, 0.9].
This satisfies the constraints set by E Then, for each a V, we assign M.. = [0.45,, 0.55). This satisfies all constraints imposed by Exr. Next, we define
2i +
2i
for all E {1....,k} Ixva.o :
0.4
00.4
and
16k
16k
2i
2i + 1
for all E {L...., k3 Ixvaa.
0.6 +
0.6
16(n k)
16(n k)
This ensures that for all vertices E V1, the interval Ix, lies in (0.2, 0.4). and symmetrically for all vertices v E V22 the interval Ix. lies in (0.6, 0.8), hence satisfying E,- Further, for all vertices u, V with u A e their intervals Tx,: Ix, are disjoint, thereby satisfying Ev. To conclude the construction of the interval representation, we set
for all o E V/2 LA, = IB. = [E([x,): 0.5], and for all v E V22 IA. IB. [0.5, r.xx)((
Now, all the constraints set in E+ Eg and ET are satisfied by construction. It is left to check whether the constraints set by Eg satisfied. Here, Ix., must not overlap IA., IB. if there exists directed edge (u, v) E E. This is trivially satisfied if u E V1 and v E V/2 or versa. If both u, v E 122 then in the constructed interval representation
must have that {(Tx.) > r(lA..) r(In.). r((xx.) ) As the intervals {/x, v E 1/2} were constructed according to a topological ordering of Vz, this is always satisfied. The argument works symmetrically for Vi, and hence the interval representation is conflict-free.
Conversely, suppose the constructed instance G admits conffict-free interval representation in BEST INTERVAL APPROXIMATION. We claim that this implies // a YES-instance of ACYCLIC DIGRAPH PARTITION. First, by Lemmas A. and A.2, any conflict-free interval representation places Is and I at the extreme left and extreme right, respectively. Consequently, in the open interval (r(Is), {(Ir)). the intervals Iz, IM, and In appear in that left-to-right order. Next, Lemma A.3 guarantees that every interval M.. for E V is contained in IM. Meanwhile, Lemma A,4 ensures that each Ix, is contained entirely in either Ir. or TR. This setup naturally suggests bipartition of the set V:
V1 = {VEV: 1x, CI and V32 = (uEV: Ix, CR).
We claim that V/]] and H[22] must each be acyclic. Indeed, in Lemma A.5 we show that for any directed edge (u. E E with u, E V1, the intervals Ix,, and Ix, in Iz must satisfy r(Ix.)) < {(Ix.)) Hence, the interval Ix, must lie to the left of Ix,- This implies topological ordering of vertices in VI, and thus prevents directed cycles in H[v). A symmetric argument shows that H[]]] acyelic. Thus, H admits partition of its vertex set into two DAGS H HV] and ([2)). Therefore, H is a YES-instance of ACYCLIC DIGRAPH PARTITION, completing the proof of Theorem 2.2.
20

---

B A PTAS for a Fixed Number of Intervals
We prove Theorem 2.3, which generalizes a result of Giotis and Guruswami [28] for the agreement version of CORRELATION CLUSTERING in complete signed graphs and also for a fixed number of clusters. Our analysis is similar to that of [28], but we have to adjust it such that we take into account the overlap of the given intervals.
Interestingly, Giotis and Guruswami [28] also presented a PTAS for the disagreement version of CORRELATION CLUSTERING. However, their result does not extend to BEST INTERVAL AP- PROXIMATION, since in our setting we may have overlapping intervals and this breaks their greedy assignment rule, well several of their technical arguments.
In the following, we consider a complete signed graph G = EV)++ We assume that we are given k intervals /,...,, 1& C IR as input. In the problem we consider, each vertex must be assigned to one of the intervals such that agreement is maximized.
The main work of this section will go into the proof of the following proposition from which the rest of our results follow.
Proposition B.1. Let and 8 O. With probability at least 1 8, Algorithm 2 computes an approximate solution with additive error at most en² /2 and has running time kO(1/e2 (og(k/(e)))) n.
The propositionn allows us to obtain Corollary B.2, which shows that we can obtain a multiplicative (1+))-approximil) guarantee for k fixed intervals. This then also implies the proof of Theorem 2.3.
Corollary B.2. Let 0 and 8 >> O. There exists an algorithm that computes (1 + -approxiimaee solution for BEST INTERVAL APPROXIMATION with ls given intervals in time /O(3/e" log(k/(e6))) with probability at least 1 - 5.
Proof. First, assume that all pairs of intervals overlap. Then it does not matter how assign the vertices because only the positive edges can be satisfied. In this case, any assignment will achieve the same objective function value as OPT. Second, assume that there is at least one pair of non- overlapping intervals. In that case, we know from CORRELATION CLUSTERING that the objective function agreement must be ?(n²) (see the proof of Theorem 3.1 in [28]). In that case, we can use the result from Proposition B.1 to obtain a multiplicative (1 + E) apprroxximtioonn by making the parameter in our additive approximation small enough. The running time claim follows from Proposition B.1.
Proof of Theorem 2.3. Note that only need to consider most 2(5) choices for picking k intervals (up to changing their coordinates): For any pair of intervals they either overlap or they do not. Thus, since there ()) interval pairs, there are at most 2(5) 20(A2) choices for the overlap.
Now we can just enumerate all possible overlap-patterns of intervals and run the algorithm from Corollary B.2 for it in time 20(A2+1/65* log(k) log(k/(s8))) n < 20 log(k/(ed)))/=)) n. Note that result is correct if the algorithm succeeds for the k intervals picked by OPT, and thus get the desired success probability (and in particular we do not have to apply a union bound that the algorithm succeeds for all possible choices of 20(k3) choices of intervals).
For the remainder of this section, we work the proof of Proposition B.1.
We present the pseudocode of our method with full details in Algorithm 2. On high level, our algorithm works by partitioning V into m O(1/e) equally-sized subsets V,, Vi,.... ...... Vm- Then, for each i = I,..., m, we proceed as follows. We sample a set of vertices S, S V Vú of size Ô (1/e?). Now, we enumerate all possible assignments of S, into U5......,,S.AA the vertices assigned to interval Ie, and for each such assignment, we greedily assign the vertices v E V, to the interval that maximizes the agreement of v edges to the clustering of S, given by (St. (S..,,.... S...). This process gives clustering of Vi and we build the final clustering by merging our solutions for the V. to obtain a global clustering of V.
where Si, S S;
For high-level description of the algorithm, see Section 2.2.
21

---

Algorithm 2: Maximizing agreement for fixed k
Input: A complete signed graph = (V, E* U
contiguous and non-empty intervals
,,...,, 4. C IR, > 0
Result: clustering (ALG)....,ALLS
maximizing the agreement
sets Vi,... Vn of size 2 Sample S; C V V uniformly at random with replacement of size s
Partition V into
each;
322 26
log (64mk
for all
1, m!;
Initialize some arbitrary clustering (ALG1,.... ALGE:: for all possible clusterings of all S; into (S....... S.,) do
for I..... m do
Let ALG,, i. ALG, be an empty clustering of Vi; for E Vú do
~ + argmax,- I..... agree (u, L, (S......... St,x)); Assign u to A
10
Set ALG; + - ALG for all / 1,..,; if agree G,
)LG agreo(G, (ALGI..., then Set (ALG),..., ALGa) t (ALG), ALG;);
11
12
13
return [AL
Recall from the main text that we write overlap(() to denote the set of all intervals Ty that overlap with interval It, i.c., overlap
{l': n Le * #0}. Furthermore, a clustering Ci...., Cs of V is an assignment of the vertices to intervals. In particular, C2 denotes all vertices which are assigned interval 4, Note that the C, are mutually disjoint. For a vertex u and a clustering CI...., C2 we write
agree(u, e, (CI,... Ck).
Σ (N) n
E
(2) nCel
e' ('Eoverlap(E)
('goverlap(?)
which is the number of agreeing edges vertex u for the clustering CI...., C2 when assigning u to interval Te. Similarly, we define
agree
(u, Tatettu,,,, (CI..., Ck)) Σ
(u)
(ovvrrlap)()
and
agree (C,,,(C =
Σ
(u)
2' (2)
For the analysis we consider an optimal clustering denoted by OPT = (OPT OPTR). Here, OPT, V consists of all vertices that get assigned to interval le in the optimal solution.
We set OPT,, V, n OPT,. Note that OPT (OPT,.,, OPT;,)) is the clustering of OPT when constrained on the vertices V,-
Next, we construct a set of hybrid clusterings that use a part of our solution from ALG and part of the solution from OPT. In particular, we
Hi, = (UALGHH) 1=1
(
m (UOPT
Note that Hi corresponds to hybrid between ALG, and OPT, where all vertices in Vi,..., V are clustered based on ALG, and all vertices in V..... Vm are clustered based on OPT₂.
Now, additionally we set H4. Hi. \ Ve, i.e., these are all vertices in H, which are not contained Vú and thus they will be clustered either before or after the i'th iteration of our algorithm. We set H, I........ H,,a) and note that H; is solution for all vertices (not just the vertices in Vg). In partieular, note that Hi OPT and Hm+1 = ALG. Additionally, we set Hi (Hi,1,...5 H..k) for the clustering given by H, after removing the vertices in V,,
22

---

For the rest of the analysis, for all = I....,m, we consider the clustering St...... Sr.k of S that agrees with the hybrid clustering, i.e., assume that S S; n H..e. Note that this clustering must be considered by the algorithm since we exhaustively enumerate all possible clusterings of all St.
Lemma B.3. Let [I,...,m), With probability at least 1 A over the randomness in St the sollowing event happens: For at least a (1 E/ //8)-fraction of the verlices u E V; it holds that for all E ,,...
im
VV V.
agree (u, E, (St,....., S(,k)) agree" (u, e, (Hi,,,.... Hi,))
E V S
(2)
32
Proof. Consider any u E Vi and let S; = fui...... v.J. For é I,..., and = 1 let X, be the indicator random variable which is vj N+(w)) and vy E S for some cluster with l' E overlap((), (), and 0 otherwise.
Note that Σド= X,,t f agree ' (u, (S,,,...,, S1,))) and that the X,, are iid. random variables =1) 1) agree* I.......H....... Now an additive Chernoff MA
with expectation E[X,,el = Pr(X, = bound gives that
agree
agree (u, (Hi.,, High)
Pr
[V Vil
E
Eō
exp
-2
32
32mk
Note that this gives the inequality from the lemma after multiplying with VV Vil on both sides.
Now let Y be the random variable denoting the number of vertices in V/2 which do not satisfy the inequality above. Observe that E E{] < 32mk Vil. By Markov's ' incquality, we get that the inequality
holds for all but [Vl vertices with probability at least 1
4mmk
Now the lemma follows by applying union bound.
We note that the lemma also holds for agree (u, f, (St,1,... S(,,)) with the same proof.
Lemma B.4, For = 0,...,m m it holds that agree(G, G, H;+1) 2 agree(G, OPT) - i. 1
Proof. Consider some iteration of the algorithm. Note that in this iteration only the vertices in V/2 are assigned clusters and thus H, and H,,1 only differ by the vertices contained in V. Therefore, proof will proceed by considering a vertex u E V/ that gets assigned to interval I, by the algorithm but interval Ie in the solution H,.
First, observe that since the algorithm assigned u to interval Iç we must have that
agree + (u. l, (S.. Sr,))) + agree (u, l, (S.. St,)) 2 agree* + (v, (Si,,, S.,)) + agree (u, E, (S.,,.... St,a)) (..
which implies that
agree (u, l',
+ agree (u, .S.......... agree + (u, E, (S.,,...., S,,)) agree (u, l, ... S,,x) $ 0.
23

---

Now set a; = VV and assume that u is vertex satisfying Equation (2). Observe that the number of agreements we might lose by this misplacement at most
agree(u, E", (H..,,..., Ha,a)) agree(u, E, (H..,,..., H.,)))
((.4,,,,.......))) agree (u, (', (Hol.... Hs,k.) agree* (u, (u,
agree + (u. 2, (Hi,1: Hr,x)) agree (u, (Hi,,, H(x))
agree (u, E,, (H.,,..... H(x)) + a,agree (u, (S.,,,..,, St,,)) agrgge (u, (St,, St,k))
+ agree (u, E (H,,,,....
(,,s)) + auagee (u, E', (S .... S(,)) o,
(u, E' (St.1, Sr,4))
agree
(u, l, (Hi,.......
Hi.k)) a.agree - (u, (St, ..... S(,z)) a,
(u, E, 1.,...... St,t))
agree
(u, E, (H,,,,...., H4,k)) agree (u, (S.,, ... St,n)) o,agree (u, E, S1,x))
x agree
(Haa)....... Hi,)) a,agre (u, ,', (S,,,,... l.... St,x))
+
agree
(Hu......, Hi,x)) (H.,,,
a.agree
(u, E, (St,1, Stx))]
+ agree
(u, f, (Ha...... Hr,k)) agagee (u, E, (S.,, St,i))
+ agree
(u, 4, (Hi,), Hi,)) a,agree (u, 2, (S,,,,... St.))
+ a. agree (u, E, (St,, St,k)) + oxagree (u, E , Si,)
a:agree + (u, E, (S,,,, S,,,) chagree (u, E, (Si, (S., St,4))
1 VV +0
32
n.
Thus we get that for all vertices in V/2 satisfying Equation (2) we get that their total difference is at most &n Vi
Furthermore, as there are most [V] vertices that do not satisfy Equation (2), they can contribute at most [Vinn en edges that are in disagreement. The number of disagreements within V; is at most [V,
22,2 16
In total, we get that we have introduced s'n 8 new disagreements due our approximations in the i' i'th iteration. The lemma now follows by induction.
Proof of Proposition B.I. The approximation ratio follows from the previous lemma. The running time follows from the fact that there are k* = k01/ log(t/(=4))) choices to assign the vertices in each S; to the intervals and we have to consider the combinations of these assignments for m = O(1/e) sets. Thus, the outer loop iterates over kms = RO(1/6" (0011e""oge log(k/((6))) assignments. Furthermore, each loop iteration can be implemented in time O(ns).
C Additional Experiment Details and Results
C.1 Experiment setup
Hardware. All our algorithms are implemented the Rust programming language. The experiments were run system with two AMD EPYC 9124 CPUs, 500 GB of RAM, and an NVIDIA RTX 4000 Ada Generation GPU.
Dataset preprocessing. As preprocessing step, we convert all networks into simple undirected graphs by removing loops and multiple edges. When removing multiple edges between two vertices, we replace them with a single undirected edge whose weight is the sum of the original edges. Finally, we apply thresholding function where positive edges are assigned weight 1, and negative edges are assigned weight -1 An overview of all our datasets is shown in Table 2.
C.2 Parameters and implementation details for VENUS and GAIA
The pseudocode of GAIA is shown in Algorithm 1. The algorithm uses greedy approach and employs randomness when partially destroying and reconstructing solutions to improve the overall objective.
24

---

Table 2: Summary of our datasets.
Dataset
[V]
[
E
E
BitcoinOTC
5 8881
21 434
18 281
3 153
Chess
7 7301
650
19 046
13.604
WikiElec
7115
355
78 440
21915
Bundestag
1 180
397 497
320 956
76541
Slashdot
82 140
498 532
380 933
117 599
Epinions
131 580
507
589 888
118619
WikiSigned
138
712
628 000
84337
WikiConflict
116 836
2014
762 999
1251054
Batch size. After one initial assignment performed over the full vertex set, V is partitioned into sets of size =. Sequentially, each of these m subsets is unassigned and reassigned greedily. In the presented results, we generally use m 10 for the sake of consistency. Depending on the specific dataset, higher or lower values might be advantageous. Lower numbers result in more aggressive reassignments and higher numbers in smaller, more incremental changes. For example, for BitcoinOTC, we observed that solutions with m = 100 on average achieve I % better objective than with m 10.
Breaking ties and randomization. An essential aspect of the implementation is randomised tie breaking for both the order of vertex assignment and the selection of the assigned cluster. Without the extensive use of randomization, the solution quality suffers greatly, and GAIA can get stuck in bad local optima early. The same can be said for the ordering of the reassignment: if vertices are reassigned in the same order in every iteration, the performance of the algorithms is substantially reduced. In our implementation, vertices are greedily assigned during the first epoch, and in each subsequent epoch, they are randomly partitioned into batches.
Vertex priority. In each batch of vertices, select the assignment order based on the maximal potential agreement of the vertex. In our preliminary experiments performed during the algorithm development, this strategy was more effective than using randomized order using different characteristics like the vertex degree for ordering. However, the performance does not differ greatly, so other methods of selecting vertex ordering might be considered in the future.
Timeout and early stopping. In the presented results, both GAIA and VENUS terminate either after 30 minutes by timeout, or until the best found solution could not be improved for 50 consecutive epochs. The condition for early stopping is intentionally chosen a very conservative manner, as often the algorithms will find very marginal improvements to their solutions late in the optimization process. To reduce runtime, using, e.g., a time limit minutes instead of 30 massively reduces solving time while only causing significant decrease in objective value for the Epinions and WikiConflicc dataset, with an average relative difference of 1 % and 10% respectively.
Simulated annealing for VENUS. With the implementation of CAIA, even with the added randomness, a high variance in the solution quality can be observed. This, paired with the fast convergence time, motivated second approach with simulated annealing: VENUS. For VENUS, every part of the algorithm remains unchanged, besides the assignment process in Line of Algorithm 1. We replace the deterministic argmax with temperature-scaled softmax over the agreement, where we define softmax over some function ff as
exp(S(())
softmax = Ee exp((e))) exp()(e))
(3)
For our setting, we use the agreement scaled by a temperature parameter to control the level of randomness, with higher levels of t yielding close to uniformly random distributions, and small values of resulting in increasingly greedy solutions. In all our experiments, we use an initial temperature of to 100, and use an exponential decay schedule where after every where a =
epochs we let t +- t a,
Interval structure. In all experimental results presented in the main text, we use 8-Chains as the interval structure for both GAIA and VENUS. As seen in Figures 3b and and Table 3, using larger and thus more expressive chain-like structures did not substantially improve the objective value. For some
25

---

Table 3:
Comparison of GAIA and VENUS for BEST INTERVAL APPROXIMATION across For each chain length, we report the best (lowest) and average disagreement.
Across all datasets, improvement above 8-Chains is minimal, with WikiConflict being the only dataset with more than 1% improvement.
Dataset
Algorithm
4-Chain
8-Chain
12-Chain
16-Chain
Best
Avg
Best
Avg
Best
Avg
Best
Avg
GAIA VENUS
768
824
711
767
721
766
725
769
BitcoinOTC
819
839
760
783
750
787
716
781
GAIA
7279
7361
6472
6 5733
6.699
6 6590
6 467
6 620
Chess
VENUS
7276
7334
6410
686
6.226
6,505
6 398
6516
GAIA
11937
12 159
11 275
11459
11 265
11 403
11 300
11 474
WikiElec
VENUS
11923
11 943
297
420
302
11 404
11 255
11 390
GAIA VENUS
3772
300
001
954
130
10256
10 2,584
Bundestag
3819
4.324
001
2078
002
10862
11 704
11 722
GAIA
51.367
53 042
45 120
46
44 860
46 180
44 827
95910
Slashdot
VENUS
51
51 813
44 563
884
447
767
44 462
44 707
GAIA
34213
32
31 687
729
31 959
125
31 805
727
Epinions
VENUS
34112
34
31 286
33.258
31 287
32
31 445
34438
GAIA
38513
39313
35 204
36270
35003
36225
35 008
36 269
WikiSigned
VENUS
38083
38343
34
34971
319
230
35 062
35.
GAIA
140004
142
69 344
69 847
68
094
68445
67 761
68 111
WikiConflict
VENUS
142450
143 269
69 014
69 264
67 645
67 953
67 472
67 717
datasets, like Bundestag Epinions, performance even starts decrease with more intervals. Hence, we report the results on an 8-Chain for consistency and to strike balance between interpretability, expressivity, and effectiveness of our heuristic.
C.3 Choosing interval structures
We always choose the interval structure for the algorithm statically. While we can adapt partial assignments to changed interval structures, preliminary experiments indicate that pruning unused intervals does not provide an effective heuristic. Rather, we would suggest using approaches from hyperparameter search to choose interval structures. With only very limited runtime, GAIA and VENUS can find good solutions. Methods like successive halving [32] can be used to exploit this efficiency and start with large population of candidate structures, which is quickly reduced to only invest compute into structures with good objective scores.
C.4 Impact simulated annealing on solution quality
Next, study how much the simulated annealing used in VENUS impacts its results compared to GAIA. Our detailed results on the real-world datasets are shown in Table 4. For almost all datasets, the average objective function of solutions found by VENUS is better than those found by GAIA. This demonstrates how simulated annealing can avoid local minima and continue the optimization process toward better solutions. Additionally, VENUS generally exhibits smaller standard deviations, indicating more consistency in the approach. A clear outlier this is the Epinions dataset, where the trend reverses and the purely greedy approach performs better; tried to understand the reason for this behavior, but could not find a clear indicator.
C.5 Benchmarking against CORRELATION CLUSTERING baselines
In addition to using GAIA and VENUS to find interval assignments with partially overlapping structures, we also evaluate their performance on structures where intervals are non-overlapping (pairwise disjoint). As described in Section 2, this setup corresponds to the CORRELATION CLUSTERING
26

---

Itcain
Bundestag
Chess
Einioon
12.0k-
7.5k-
1.0k-
9.0k
37.0k-
0.9k-
6.0k
6.9k
35.0k-
0.8k-
3.0k
6.6k-
33.0k-
Disagreenert
0.7k
31.0k-
12
12
16
16
16
Slashdot
WikiConflict
WikiElec
Wikis igned
56.0k
160 0k-
40.0k
12.5k
52.0k
120.0k Ok-
38.0k-
12.0k-
100 0k
48
36.0k-
80.0k
11.5k
44.0k
12
166
16
Number of Intervals GAIA
Algorithm
VENUS
Figure Final objective for different interval structures for all datasets.
Table 4: Comparison of GAIA and VENUS for solving BEST INTERVAL APPROXIMATION. We report the minimum disagreement (in absolute number of edges), as well as averages and standard deviations over 50 runs. The solutions computed for fixed 8-Chain interval structure and 10 reassignment batches.
Gaia
Venus
Dataset
Best
Std
Best
Atd
BitcoinOTCC
711
767+26
760
783
Chess
6472
5523+55
6410
64864:36
WikiElec
11 275
11 449+143
19
11 410
Bundestag
1001
9 455
1001
2078
Slashdot
120
462181880
445663
848844477
Epinions
687
32 1300
286
33 258 306
WikiSigned
354
36 270
34564
349711165
WikiConflict
69.344
69 147
69014
69 264+1411
problem with fixed number of clusters. Results for structure with 8 disjoint intervals are shown in Tables 5 and 6. Across all datasets, GAIA and VENUS achieve objective values within 0.5 percentage points of the best CORRELATION CLUSTERING baselines, despite being constrained to only 8 clusters. Moreover, the solutions produced by GAIA and VENUS show low variance, with a standard deviation of under 100 violations all but one dataset. This indicates that the algorithms consistently found strong solutions, particularly with less variance than when using overlapping interval structures (see Table 4).
We believe that this finding is highly interesting, since it shows that our methods find CORRELA- TION CLUSTERING solutions that are on par with state-of-the-an algorithms, while also being able to solve
general BEST INTERVAL APPROXIMATION problem.
Additionally, notable that we find competitive solutions even though we only use 8 clusters, whereas the baselines might use an unrestricted number. However, this finding is not completely new and echoes findings by Brusco and Doreian [9), who observed similar objective values using few clusters the WikiElec and Slashdot datasets.
27

---

Table 5: Comparison of algorithms and CORRELATION CLUSTERING baselines for solving CORRELATION CLUSTERING. Reported is the percentage of edges violated in the solution (lower is better). Our algorithms fixed structure of distinet clusters, while the CORRELATION CLUSTERING algorithms are not restricted in the number of clusters.
Our algorithms
CORRELATION CLUSTERING baselines
Dataset
GAIA
VENUS
GAEC
GAECKL]
SCMLEvo
RAMA
BitcoinOTC
5.57
5.57
5.58
5.57
5.57
5.64
Chess
27.67
27.75
28.64
28.10
27.33
39.98
WikiElec
14.13
14.13
14.13
14.13
14.13
14.45
Bundestag
2.95
2.95
3.06
2.95
2.95
3.72
Slashdot
13.70
13.59
13.75
13.66
13.52
17.17
Epinions
6.69
6.71
6.83
6.68
6.67
6.86
WikiSigned
6.30
6.21
6.17
6.17
6.17
6.96
WikiConflict 5.85
5.85
5.87
5.82
5.82
6.02
Table 6: Comparison of the results of GAIA and VENUS when solving CORRELATION CLUSTERING. We report the minimum disagreement (in absolute number of edges), as well as averages and standard deviations over 50 runs. The solutions computed for 8 distinct clusters (i.e., 8 non-overlapping intervals) and 10 reassignment batches.
Gaia
Venus
Dataset
Best
Avg
Best
Atd
BitcoinOTC
1 194
201 4-3
194
1 200---4
Chess
933
128:555
906
9 1322722
WikiElec
14 181
14 18512
14
14 18512
Bundestag
736
11 756127
11725
11 73641
Slashdot
68 276
3531+33
67759
68 334+88
Epinions
47 412
47 4994:66
47570
750-
WikiSigned
881
44992+148
44217
274
WikiConflict
117814
117 882-:22
117885
117 23
C.6 Scalability and runtime analysis
The time until convergence for GAIA and VENUS is shown in Table 7 and Figure 7. For both algorithms, the running time scales roughly linearly with the size of the graph and the memory usage is at most 260 megabytes for the largest datasets. Despite the artificial slowdown of convergence during early epochs, VENUS remarkably not notably slower to converge than GAIA. Further, we note that both the memory and runtime complexity of our algorithms depend linearly on the number of intervals, so running time can vary with the size of the interval structure.
C.7
Case study
The Bundestag dataset. Our novel Bundestag dataset was constructed by scraping all the roll-call voting data from the German parliament between October 18th, 2012, and March 18th, 2025,3 As official works, this voting data is not subject to copyright. From the voting data, we then generated signed graph by representing each member with a vertex and assigning a positive edge two members vote the same way at least 75% of sessions they both attended, and a negative edge their votes aligned in 25% of sessions or less. This left two politicians without any edges, which were thus excluded from the signed graph. Notably, the voting data includes several politicians who changed parties during their parliamentary careers. In such cases, we treat the politicians as members of the party they were first affiliated with for visualization purposes. This could also explain slight within-party differences, e.g., the LINKE party split between 2023 and 2024.
This data is publicly available at https://www.bbunesttge http:///wwwwww.ooooeeoee/eeeeeen
28

---

Table Time until convergence averaged over runs on different instances. We report the runtime in seconds until 50 full epochs without improvement (lower is better). Our algorithms use fixed Chain interval structure and 10 batches for vertex reassignment.
GAIA
VENUS
Dataset
Best
Std
Worst
Best
Avg
Worst
BitcoinOTC
1.2
2.5++0.9
5.7
1.8
3.2-+-.88
Chess
3.7
8.412.4
15.2
3,8
8.542.1
13.4
WikiElec
6.1
16.245.5
31.1
7.1
13.916.2
41.5
Bundestag
5.5
8.8+1.9
16.2
10.9
15.2+2.4
22.8
Slashdot
107.5
251.9
781.2
98.9
173.8145.3
348.5
Epinions
182.3
169.1=129.4
954.8
196.0
390.8=113.0
897.4
WikiSigned
169.6
353.5+94.3
602.9
214.6
357.5+90.6
585.3
WikiConflict
436.2
874.0=192.8
1470.0
372.9
695.1=183.7
1 1200.0
800s
Auntime
400s
500k
000k Number of Edges
500k
000k
GAIA
VENUS
Bitcoin
Chess
Epinions
WikCoonfiict
Bundestag
X Wkiille
Slashdot
WikSiigned
Figure 7: Time until convergence per instance, Table 7 for details.
Generation of Figure 1. With the preprocessed Bundestag instance, let VENUS compute solution and for each politician we visualize their party membership via coloring the corresponding point and the positioning it on the y-axis. The interval assignment produced by VENUS determines the x-position. We then slightly adjust the position inside the bins to indicate the affinity of each politician as follows: For the vertex v E C' corresponding the politician, we define its affinity to other clusters Cp
affinity(v, Cr-) = |N (v) nCel |N (e)
Then calculate the z-perturbation of denoted by Un.
affinity(u,Ce Ce.
tanh
Σ F'ge e ())
(5)
In words, the position of a vertex is shifted to the left or to the right according to the assignment of its neighbors, depending on their distance. Neighbors assigned closer intervals affect the position more, and neighbors assigned further away affect the position less. The direction of this influence depends on the edge sign.
This function simply serves the purpose of visualization, to show connectivity across intervals. is direct output of algorithm and does not have a fixed interpretation. Finally, we slightly adjust the position of the vertices in the plot with small amounts Gaussian noise to avoid over-plotting The figure also includes violin plot of each political party.
Results. The solution found by VENUS is highly interpretable and can used to generate insight about the co-voning behavior in the German parliament. This interpretation is discussed in Section 4,
29

---

Number Assigned Memberr
750
250
Interval Index
LINKE (Left)
GRÜNE (Green)
SPD (Social Democrat)
FDP (Liberal)
CDU/CSU (Conservative)
AID (Far Right)
Figure 8: An alternative visualization of VENUS's s results on the Bundestag dataset. Here, we present party affiliations of Bundestag members assigned to each interval.
with alternative visualisation in Figure 8, which shows interval-centric view instead of the party-centric view Figure 1. Figure shows that each interval dominated by members one political party. Further, discussed previously, the figure accurately reflects the political spectrum in Germany, with the exception of the FDP, which appears "split" between intervals 4-6. This can be justified by the different coalition structures in the last few legislative periods, discussed in the main text.
30


Reviews:
[{"review_id": "7cSZdxjyZ5", "reviewer": "Reviewer_HyVH", "summary": "This paper introduces a generalization of correlation clustering, which they call the “Opinion Interval Representation” problem. The idea is that we are given a set of nodes and a set of signed edges. In correlation clustering, the goal is to assign nodes to clusters in such a way that we minimize the total number of negative edges within a cluster plus the number of positive edges between two different clusters. This paper consider instead assigning each node to an interval on the real line. If two nodes have overlapping intervals, we recieve a penality if they have a negative edge between them. If nodes have non-overlapping intervals, they receive a penalty if connected by a positive edge. The idea is to choose intervals to minimize the number of penalties. \n\nThe justifcation for this problem is that we might have non-transitive edge forming behavior in social networks — the authors give the compelling example of politicians — a centrist candidate might often vote the same way as both a liberal candidate and a conservative candidate, but those candidates rarely vote in the same way. The authors also provide some nice experimental justification — they apply the clustering approach to a new data set based on German Parliment votes, and recover a natural picture of the political “spread” of different parties. They also show that, on all examples datasets they test, the problem leads to significanty better “explanations” than correlation clustering -- i.e., it is possible to produce an interval representations that gets many more edges correct than a regular clustering. This is despite the fact that these experiments actually solve a restricted version of the problem, where we have a fixed number of intervals k (they choose k = 8 for some reason) and assign every node to one of those intervals. \n\nThe theoretical work of the paper is mainly focused on algorithms, and read more like an algorithms conference paper than a machine learning paper. The authors first prove the problem as stated is NP-hard, which is not too surprising. They then describe a fixed-parameter tractible algorithm for their restricted version of the problem involving a fixed set of k intervals — the runtime is polynomial but exponential in k. This method is based on adapting an FPT algorithm for correlation clustering when the number of clusters is fixed (in general, correlation clustering allows any number of clusters — the idea is to find the least disagreements amoung all possible partitions). Basically, but brute forcing over all possible “overlaps” of the fixed set of intervals, they can reduce to a generalization of correlation clustering where disagreement between some clusters is not penalized.\n\nThe authors also describe some heuristic algorithms for the problem, which they test in an experiments section. The experiments section is complete in that it asks clear questions and tells a clear story: the authors justify they their new problem is interesting (it’s more expressive than correlation clusteirng for real dataset), that their heuristics find reasonable solutions in a reasonable amount of time, and that sovling the problem can product interesting visualizations/explanations (via their German parliment example). \n\nSmall comments:\n- It doesn’t seem necessary to write k = O(1) on Page 2 since you are being explicit about the dependence on k in the stated runtime.\n- 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 roughy what metric is being considered — how methods for two different problems compared in a head-tohead way?\n- A few times in the intro is was mentioned that something would be discussed later or “below” but I would have preferred a reference to exactly where. E.g.: Below, we will also argue that Interval Editing problems are closely related. Some of these points I also didn’t think were worth delaying — it is pretty obvious why the problem is more expressive than correlation clustering — could be explained in 2 sentences instead of defering until Section 2. \n- 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? \n- The text claims that OPINION INTERVAL REPRESENTATION “is not FPT when parameterized by the number of required edge deletions”, but the problem doesn’t even involve edge deletions at all. I think it would be better (if it is correct) to say when parameterized by OPT where OPT is the minimum cost solution of OPINION INTERVAL REPRESENTATION? Or at least to explain things more.\n- Why in the experiments did you restrict to exactly 8 intervals?\n- Should there be a last line of Theorem 2.2 that drives the point home, e.g. “Thus, the Opinion Interval Representation problem is NP-hard”.", "questions": "I listed maybe one small question with my summary, and a few other small suggestions, but honestly I don't have any major suggestions. I thought the paper was well written and an interesting read.", "limitations": "na", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "While I am not an expert on the topic, this feels like a very complete paper to me. The paper is well-written and easy to follow. The authors introduce a natural and easy to understand clustering objetive. Given its connection to correlation clustering, and how well interval graphs have been studied, the problem is not too far afield from prior work. At the same time, it appears significantly more expressive than correlation clustering, while still resulting in an easy to interpret visualization for structure that could possibly have lead to the observed signed graph (k 1-d intervals instead of k clusters). At least this is true of the restricted version of the problem. While none of the theoretical results in the paper are ground breaking, the authors take meaningful first steps towards understanding algorithms for their objective, and applying it to a case study. 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.", "was_revised": true, "final_justification": "No major negative points about the paper were raised by other reviewers, so my feelings on the paper remain positive for the reasons described in my review.", "rebuttal": "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.\n\n> Why in the experiments did you restrict to exactly 8 intervals?\n\nWe 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.\n\n| instance     | algorithm |  best_4 | best_8 | best_12 | best_16 |\n| :----------- | :-------- | ------: | -----: | ------: | ------: |\n| Bitcoin      | GAIA      |     768 |    711 |     721 |     725 |\n| Bundestag    | GAIA      |   3,772 |  1,001 |   1,030 |   2,584 |\n| Chess        | GAIA      |   7,279 |  6,472 |   6,469 |   6,467 |\n| Epinions     | GAIA      |  34,213 | 31,687 |  31,959 |  31,805 |\n| Slashdot     | GAIA      |  51,367 | 45,120 |  44,860 |  44,827 |\n| WikiConflict | GAIA      | 140,004 | 69,344 |  68,094 |  67,761 |\n| WikiElec     | GAIA      |  11,937 | 11,275 |  11,265 |  11,300 |\n| WikiSigned   | GAIA      |  38,513 | 35,204 |  35,003 |  35,008 |\n| Bitcoin      | VENUS     |     819 |    760 |     750 |     716 |\n| Bundestag    | VENUS     |   3,819 |  1,001 |   1,002 |  11,704 |\n| Chess        | VENUS     |   7,276 |  6,410 |   6,426 |   6,398 |\n| Epinions     | VENUS     |  34,112 | 31,286 |  31,287 |  31,445 |\n| Slashdot     | VENUS     |  51,117 | 44,563 |  44,447 |  44,462 |\n| WikiConflict | VENUS     | 142,450 | 69,014 |  67,645 |  67,472 |\n| WikiElec     | VENUS     |  11,923 | 11,297 |  11,302 |  11,255 |\n| WikiSigned   | VENUS     |  38,083 | 34,564 |  34,819 |  35,062 |\n\nThe 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. \n\nWe will add this table, as well as plots for selected datasets, in the final version of the paper. \n\nIf 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.\n\n> 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.\n\nWe 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.\n\nYuko Kuroki, Atsushi Miyauchi, Francesco Bonchi, Wei Chen: Query-Efficient Correlation Clustering with Noisy Oracle. NeurIPS 2024\n\nSepehr Assadi, Vihan Shah, Chen Wang: Streaming Algorithms and Lower Bounds for Estimating Correlation Clustering Cost. NeurIPS 2023\n\nKonstantin Makarychev, Sayak Chakrabarty: Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple! NeurIPS 2023\n\nSilvio Lattanzi, Benjamin Moseley, Sergei Vassilvitskii, Yuyan Wang, Rudy Zhou: Robust Online Correlation Clustering. NeurIPS 2021: 4688-4698\n\nRuo-Chun Tzeng, Bruno Ordozgoiti, Aristides Gionis: Discovering conflicting groups in signed networks. NeurIPS 2020\n\nYanbang Wang, Jon M. Kleinberg: On the Relationship Between Relevance and Conflict in Online Social Link Recommendations. NeurIPS 2023\n\nLiwang Zhu, Qi Bao, Zhongzhi Zhang: Minimizing Polarization and Disagreement in Social Networks via Link Recommendation. NeurIPS 2021: 2072-2084\n\n> 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?\n\nThank 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.\n\n> 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?\n\nWe 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."}, {"review_id": "O35j49hTgT", "reviewer": "Reviewer_SMfw", "summary": "The manuscript's main contribution is the opinion interval representation, a framework for analyzing signed graphs. The proposed method assigns intervals on the real line to nodes, maximizing overlap for positively connected pairs and disjointness for negatively connected pairs (see Section 2). This method differs from correlation clustering, which partitions nodes into disjoint clusters. Another contribution of the paper is establishing NP-hardness for general instances (see Section 2.1). It also provides a polynomial-time approximation scheme (PTAS) for a restricted complete-graph scenario with a fixed number of intervals (see Section 2.2). Finally, the manuscript presents two scalable heuristics, GAIA and VENUS (see Section 3), for inference in the interval representation. Experiment results are encouraging and outperform state-of-the-art correlation clustering approaches on both synthetic and real-world datasets.", "questions": "* 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?\n* 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.", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**:\n\n* Novelty and a principled approach to a solution. The proposed framework for opinion interval representation allows for higher expressivity when modelling real-world scenarios (as shown in Figure 1 in the German parliament case study). Moreover, the theoretical results in Section 2 establish clear boundaries for the application of this framework. For instance, Theorem 2.3 provides grounding for an approximate solution, given that Section 2.1 shows that the problem is NP-hard.\n* Experiment results are thorough and convincing. The manuscript compares the method with four SOTA baselines, including a novel dataset based on voting data from the German Parliament. Table 1, which compares the proposed heuristics with the baseline, achieves an improvement of 20% to 90%.\n\n**Weaknesses**:\n\n* The polynomial-time approximation in Theorem 2.3 could limit the method's application due to graph completeness and fixed interval numbers. It is unclear from the manuscript the impact and size of practical limitations on real-world cases.\n* The hyperparameter selection for GAIA and VENUS could be challenging for some applications. The manuscript does not offer a data-driven approach for selecting the number of intervals or the overlap configuration.", "was_revised": true, "final_justification": "After reviewing the responses from my peer reviewers and the authors, I believe this paper should be accepted. The other reviews are positive and highlight relevant strengths of the work. The authors have appropriately addressed my question, including my suggestion for multi-dimensional extension.", "rebuttal": "We thank the reviewer for the positive evaluation of our paper.\n\n> 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?\n\nIn 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:\n* 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.\n* Regarding how to pick the intervals and their overlap structure, we can exploit the fact that our algorithms are highly efficient.\nIn 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.\n\nAdditionally, 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.\n\nWe will add a discussion of this in the appendix of the final version of our paper.\n\nKevin G. Jamieson, Ameet Talwalkar: Non-stochastic Best Arm Identification and Hyperparameter Optimization. AISTATS 2016: 240-248\n\n> 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.\n\nThank 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:\n* The assignment-procedure from the heuristic GAIA (Algorithm 1) can be readily adapted, because it only uses the overlap-structure of the geometric objects.\n* 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.\nWe 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."}, {"review_id": "eEP2uuNkzn", "reviewer": "Reviewer_NU77", "summary": "The authors introduce the Opinion Interval Representation problem: given a signed graph, assign each node to an interval on the real line in a way that maximizes the number of positive edges between nodes whose intervals overlap and the number of negative edges between nodes whose intervals are disjoint. They show the problem is NP hard and relate it to Interval Editing and Correlation Clustering. The authors provide a PTAS for the case when only $k$ distinct intervals are allowed and two greedy and simulated annealing heuristics. In experiments on real-world signed graph datasets, the authors find that interval representations found by their heuristics are more expressive than Correlation Clustering solutions. In synthetic data, they find that their heuristics can recover true interval structure. Finally, in a dataset of German parliamentary votes, the authors show one-dimensional ideologies of politicians can be recovered using overlapping intervals.", "questions": "I don't have any major questions, but I do have the following suggestions/comments:\n\n1. 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).\n2. 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. \n\nMinor:\n\"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).", "limitations": "The authors are clear about the extent of their results, and I don't see any potential for negative societal impact.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n1. The new algorithmic problem is explored thoroughly, with hardness, approximation, and heuristics.\n2. The experiments do a good job of showcasing the problem and the heuristics\n\nWeaknesses:\n1. The experimental comparison to Correlation Clustering is presented in a misleading way in certain places\n\nQuality: Seems high throughout the paper.  Good grounding in existing work and a well-executed paper overall.\n\nClarity:\nThe paper is generally well-written, with only a few unclear points (see suggestions below.)\n\nSignificance: I think this paper would be of interest to the the community interested in signed networks, community detection, and ideology estimation. \n\nOriginality: This paper explores a novel problem (to my knowledge), but the techniques are standard. 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.", "was_revised": true, "final_justification": "The updates described by the authors address my concerns about presentation. I've updated my score accordingly.", "rebuttal": "We thank the reviewer for the positive evaluation of our paper.\n\n> 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.\n\nWe 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.*\"\n\nWe will also make sure that there are no such misunderstandings in the rest of the paper.\n\nAs 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.\n\n> 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).\n\nIndeed, 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.\n\n> 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).\n\nWe 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.\n\n> 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.\n\nThank 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."}]

Author rebuttal:

Meta-review: This work examines the problem of inferring opinion ranges of nodes in a signed network (where edges have positive or negative signs corresponding to agreement or conflict between the corresponding nodes). In this optimization problem, we seek to assign opinion intervals (i.e., acceptable range of opinions) to each node such that two nodes connected by a positive edge should have overlapping intervals and those connected by a negative edge should have disjoint intervals. This is in contrast to assigning nodes to clusters so as to maximize the number of edges consistent with the clustering. 

The reviewers praised several strengths of this work, including: 
* A compelling and clearly described problem, as well as easy-to-follow writing, ample examples for building intuition, and clear presentation of results
* An intuitive formulation of this problem (i.e., by considering opinion ranges), which creates a clean mathematical formulation and is also grounded in real world observations. 
* Reasonable theoretical results which add to the paper's comprehensiveness. Though many of these theoretical results are not very surprising and follow a similar flow to other related works, they can serve as a foundation for future work. There could be interesting follow up papers considering a dynamic setting where opinion ranges expand or contract over time. Similarly, dropping the independence assumptions where, e.g., nodes have "innate" opinion ranges that expand or contract depending on the nodes' centrality or the homophily of its immediate neighborhood. 
* An interesting dataset, which, to my knowledge, may be new to the networks community, and gives a compelling set of empirical insights. 

The reviewers provide detailed questions and local suggestions for improvement. We thank the authors for their engagement through the discussion process and for sharing the list of edits they plan to make in their final remark. Though space is tight, we encourage the authors to also add a short discussion and suggestions for future work, including some learning-based questions to encourage engagement and follow-up work.
Decision: Accept (oral)