The most persistent soft-clique in a set of sampled graphs

N. Quadrianto, C. Lampert, C. Chen, in:, Proceedings of the 29th International Conference on Machine Learning, Omnipress, 2012, pp. 211–218.

Conference Paper | Published | English
Abstract
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. 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.
Publishing Year
Date Published
2012-06-01
Proceedings Title
Proceedings of the 29th International Conference on Machine Learning
Page
211-218
Conference
ICML: International Conference on Machine Learning
Conference Location
Edinburgh, United Kingdom
Conference Date
2012-06-26 – 2012-07-01
IST-REx-ID

Cite this

Quadrianto N, Lampert C, Chen C. The most persistent soft-clique in a set of sampled graphs. In: Proceedings of the 29th International Conference on Machine Learning. Omnipress; 2012:211-218.
Quadrianto, N., Lampert, C., & Chen, C. (2012). The most persistent soft-clique in a set of sampled graphs. In Proceedings of the 29th International Conference on Machine Learning (pp. 211–218). Edinburgh, United Kingdom: Omnipress.
Quadrianto, Novi, Christoph Lampert, and Chao Chen. “The Most Persistent Soft-Clique in a Set of Sampled Graphs.” In Proceedings of the 29th International Conference on Machine Learning, 211–18. Omnipress, 2012.
N. Quadrianto, C. Lampert, and C. Chen, “The most persistent soft-clique in a set of sampled graphs,” in Proceedings of the 29th International Conference on Machine Learning, Edinburgh, United Kingdom, 2012, pp. 211–218.
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 Learningp. 211–218.
Quadrianto, Novi, et al. “The Most Persistent Soft-Clique in a Set of Sampled Graphs.” Proceedings of the 29th International Conference on Machine Learning, Omnipress, 2012, pp. 211–18.

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar