摘要翻译：
当在潜在的噪声图数据中搜索特征子模式时，具有多个观测结果比只有一个观测结果要好，这是不言而喻的。然而，当不同的图实例具有不同的边集时引入的不一致性是一个严重的挑战。在这项工作中，我们解决了寻找最大加权团的问题。引入了最持久软团的概念。这是顶点子集，1)几乎完全或至少密集连通，2)出现在所有或几乎所有图实例中，3)具有最大权重。我们给出了一个团性度量，它本质上是计算使一个顶点子集成为一个团所缺少的边的数目。利用这一测度，我们证明了寻找最持久软团问题既可以归结为最大最小二人博弈优化问题，也可以归结为最小最小软边界优化问题。当用部分拉格朗日方法求解最优化问题时，这两个公式都得到了相同的解。通过对合成数据和真实社会网络数据的实验，我们证明了该方法能够可靠地找到图数据中的软团，即使被随机噪声或不可靠的观测所扭曲。
---
英文标题：
《The Most Persistent Soft-Clique in a Set of Sampled Graphs》
---
作者：
Novi Quadrianto (University of Cambridge), Chao Chen (IST Austria),
  Christoph Lampert (IST Austria)
---
最新提交年份：
2012
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Machine Learning        机器学习
分类描述：Papers on all aspects of machine learning research (supervised, unsupervised, reinforcement learning, bandit problems, and so on) including also robustness, explanation, fairness, and methodology. cs.LG is also an appropriate primary category for applications of machine learning methods.
关于机器学习研究的所有方面的论文（有监督的，无监督的，强化学习，强盗问题，等等），包括健壮性，解释性，公平性和方法论。对于机器学习方法的应用，CS.LG也是一个合适的主要类别。
--
一级分类：Computer Science        计算机科学
二级分类：Artificial Intelligence        人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--

---
英文摘要：
  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.
---
PDF链接：
https://arxiv.org/pdf/1206.4652