---
_id: '3127'
abstract:
- lang: eng
  text: "When searching for characteristic subpatterns in potentially noisy graph
    data, it appears self-evident that having multiple observations would be better
    than having just one. However, it turns out that the inconsistencies introduced
    when different graph instances have different edge sets pose a serious challenge.
    In this work we address this challenge for the problem of finding maximum weighted
    cliques.\r\n    We introduce the concept of most persistent soft-clique. This
    is subset of vertices, that 1) is almost fully or at least densely connected,
    2) occurs in all or almost all graph instances, and 3) has the maximum weight.
    We present a measure of clique-ness, that essentially counts the number of edge
    missing to make a subset of vertices into a clique. With this measure, we show
    that the problem of finding the most persistent soft-clique problem can be cast
    either as: a) a max-min two person game optimization problem, or b) a min-min
    soft margin optimization problem. Both formulations lead to the same solution
    when using a partial Lagrangian method to solve the optimization problems. By
    experiments on synthetic data and on real social network data, we show that the
    proposed method is able to reliably find soft cliques in graph data, even if that
    is distorted by random noise or unreliable observations."
article_processing_charge: No
arxiv: 1
author:
- first_name: Novi
  full_name: Quadrianto, Novi
  last_name: Quadrianto
- first_name: Christoph
  full_name: Lampert, Christoph
  id: 40C20FD2-F248-11E8-B48F-1D18A9856A87
  last_name: Lampert
  orcid: 0000-0001-8622-7887
- first_name: Chao
  full_name: Chen, Chao
  id: 3E92416E-F248-11E8-B48F-1D18A9856A87
  last_name: Chen
citation:
  ama: 'Quadrianto N, Lampert C, Chen C. The most persistent soft-clique in a set
    of sampled graphs. In: <i>Proceedings of the 29th International Conference on
    Machine Learning</i>. ML Research Press; 2012:211-218.'
  apa: 'Quadrianto, N., Lampert, C., &#38; Chen, C. (2012). The most persistent soft-clique
    in a set of sampled graphs. In <i>Proceedings of the 29th International Conference
    on Machine Learning</i> (pp. 211–218). Edinburgh, United Kingdom: ML Research
    Press.'
  chicago: Quadrianto, Novi, Christoph Lampert, and Chao Chen. “The Most Persistent
    Soft-Clique in a Set of Sampled Graphs.” In <i>Proceedings of the 29th International
    Conference on Machine Learning</i>, 211–18. ML Research Press, 2012.
  ieee: N. Quadrianto, C. Lampert, and C. Chen, “The most persistent soft-clique in
    a set of sampled graphs,” in <i>Proceedings of the 29th International Conference
    on Machine Learning</i>, Edinburgh, United Kingdom, 2012, pp. 211–218.
  ista: 'Quadrianto N, Lampert C, Chen C. 2012. The most persistent soft-clique in
    a set of sampled graphs. Proceedings of the 29th International Conference on Machine
    Learning. ICML: International Conference on Machine Learning, 211–218.'
  mla: Quadrianto, Novi, et al. “The Most Persistent Soft-Clique in a Set of Sampled
    Graphs.” <i>Proceedings of the 29th International Conference on Machine Learning</i>,
    ML Research Press, 2012, pp. 211–18.
  short: N. Quadrianto, C. Lampert, C. Chen, in:, Proceedings of the 29th International
    Conference on Machine Learning, ML Research Press, 2012, pp. 211–218.
conference:
  end_date: 2012-07-01
  location: Edinburgh, United Kingdom
  name: 'ICML: International Conference on Machine Learning'
  start_date: 2012-06-26
date_created: 2018-12-11T12:01:33Z
date_published: 2012-06-01T00:00:00Z
date_updated: 2025-06-11T08:09:42Z
day: '01'
department:
- _id: ChLa
- _id: HeEd
external_id:
  arxiv:
  - '1206.4652'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: http://arxiv.org/abs/1206.4652
month: '06'
oa: 1
oa_version: Preprint
page: 211-218
publication: Proceedings of the 29th International Conference on Machine Learning
publication_status: published
publisher: ML Research Press
publist_id: '3572'
quality_controlled: '1'
scopus_import: '1'
status: public
title: The most persistent soft-clique in a set of sampled graphs
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2012'
...