Analysis and Optimization of Graph Decompositions by Lifted Multicuts
Research output: Contribution to book/conference proceedings/anthology/report › Conference contribution › Contributed › peer-review
Contributors
Abstract
We study the set of all decompositions (clusterings) of a graph through its characterization as a set of lifted multicuts. This leads us to practically relevant insights related to the definition of classes of decompositions by must-join and must-cut constraints and related to the comparison of clusterings by metrics. To find optimal decompositions defined by minimum cost lifted multicuts, we establish some properties of some facets of lifted multicut polytopes, define efficient separation procedures and apply these in a branch-and-cut algorithm.
Details
Original language | English |
---|---|
Title of host publication | Proceedings of the 34th International Conference on Machine Learning |
Editors | Doina Precup, Yee Whye Teh |
Pages | 1539-1548 |
Volume | abs/1503.03791 |
Publication status | Published - 2017 |
Peer-reviewed | Yes |
Externally published | Yes |
Publication series
Series | Proceedings of Machine Learning Research |
---|---|
Volume | 70 |
External IDs
dblp | journals/corr/Andres15 |
---|---|
ORCID | /0000-0001-5036-9162/work/162346198 |