Interactive Correlation Clustering with Existential Cluster Constraints
Authors: Rico Angell, Nicholas Monath, Nishant Yadav, Andrew Mccallum
ICML 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We evaluate the efficiency of existential cluster constraints in terms of human feedback inputs and the efficacy of our inference algorithm on publicly available author coreference datasets. Author coreference is a real world clustering task where the predictions are viewed by human users on websites such as Google Scholar1, Semantic Scholar2, and Open Review3. We simulate the process of human feedback in a series of rounds in which an oracle generates one or more constraints to correct the previous round s predictions and run our inference algorithm on the running set of constraints. We compare existential cluster constraint directly against must-link and cannot-link constraints. On every dataset, we find existential cluster constraints require nearly half as many user feedback inputs than must-link and cannot-link constraints to reach the ground truth clustering. |
| Researcher Affiliation | Collaboration | 1Manning College of Information and Computer Sciences, University of Massachusetts Amherst 2Google Research. |
| Pseudocode | Yes | Algorithm 1 TRELLISCUT(G, Φ, Ξ, T ) |
| Open Source Code | No | The paper mentions using and citing third-party open-source tools like S2AND, SCS, and Higra, but it does not provide a link or statement about releasing the source code for its own described methodology. |
| Open Datasets | Yes | We use three publicly available datasets from S2AND (Subramanian et al., 2021), a state-of-the-art author coreference system4. |
| Dataset Splits | Yes | We use the default and recommended 80/10/10 train/val/test split for each dataset, tuning all of the hyperparameters on the validation set. |
| Hardware Specification | No | The paper does not provide specific details about the hardware used for running the experiments (e.g., specific GPU or CPU models, memory, or cloud instance types). |
| Software Dependencies | Yes | We use SCS (O Donoghue et al., 2021), a modern convex optimization solver, to solve the SDP relaxation shown in Objective (4). For must-link and cannot link constraints, we use the total sum of the edge weights on the graph to act as a proxy for , since SCS cannot handle infinite edge weights. We use the default hyperparameters and set the maximum number of iterators to 50k. Given the output of the SDP solver, we use Higra (Perret et al., 2019) to construct the trellis by constructing greedy binary hierarchical clusterings of the vertices and the -constraints using five different linkage functions: average, complete, single, exp(α = 1), and exp(α = 1) (Yadav et al., 2019). We substitute a large negative number into all entries in X that represent two incompatible elements to safely avoid them from being merged by the hierarchical clustering algorithm. We construct the trellis by taking taking the union of all partial clusterings represented in the five binary hierarchical clustering trees. |
| Experiment Setup | Yes | To produce the edge weights on the graph for each block, we train the pairwise S2AND Light GBM (Ke et al., 2017) classifier model using the pairwise features detailed in Subramanian et al. (2021). We use the default and recommended 80/10/10 train/val/test split for each dataset, tuning all of the hyperparameters on the validation set. For each test set, we construct the complete graph for each block and for each edge assign edge weights based on the trained pairwise classifier output logits shifted by a threshold tuned on the validation set. If the classifier score is above (below) the threshold, the edge weight will be positive (negative). The resulting graph will be taken as input into the simulation of clustering with human feedback. Test set statistics for each dataset can be seen in Table 1. |