图论论文研究的内容

好。图论（GraphTheory）是研究边和点的连接结构的数学理论，该方向的内容面广，是很好写论文的，用户可以写的知识点多。

(该分享持续更新中...) 这篇论文主要有三个贡献点： 目前，物体检测、语义分割等技术都是集中在如何在图片上检测出物体，但是忽略了物体与物体之间的关系。一项最近的工作提出了用图（场景图）来代表一个场景。场景图是图像的可解释的结构化表示，可以支持更高级别的视觉智能任务，如captioning。 将每一对节点(对象)视为潜在的边(关系)的自然方法本质上是对全连通图的推理，这种方法在建模上下文关系时通常是有效的，但对对象数量的缩放效果很差(二次)，很快就变得不切实际。嘴朴素的修正方法是采用随机采样，虽然它是efficient，但不是effective，因为对象之间的相互作用的分布远远不是随机的。 作者的解决办法： 图1.给一张图片，模型从图片中抽取出objects(a), 所有节点考虑可能存在的边（b），通过一个医学系的方法‘relatedness’裁去不可能发关系，从而产生更稀疏的候选图结构（c）。最后，利用aGCN去集成全局信息并且更新物体节点和关系的标签（d） 在这项工作中，我们提出了一个新的框架，Graph R-CNN，它通过两种机制有效地利用对象关系规则来智能地稀疏化和推理候选场景图。我们的模型可以分解为三个逻辑阶段:1)对象节点提取，2)关系边缘剪枝，3)图上下文集成，如图1所示。 在对象节点提取阶段，我们使用了一个标准的对象检测的pipeline（faster rcnn）。这就产生了一组localized object regions，如图1b所示。我们将在剩下的pipeline中引入两个重要的新特性，以合并上面讨论的对象关系中的真实世界的规则性。首先，我们介绍了一个关系建议网络(RePN)，该网络能够有效地计算对象对之间的关联分数，这些分数被用来智能地修剪不太可能的场景图连接(与之前工作中的随机修剪不同)，剪枝后的稀疏图如图1c所示。其次，给出了稀疏连接的候选场景图，我们应用了一个注意图卷积网络(aGCN)来在整个图中传播higher-order上下文——更新每个对象及其基于其邻居的关系表示。与现有的工作相比，我们预测每个节点的边attention，使我们的方法能够学习调节不可靠或不太可能的边缘之间的信息流。我们在图1d中显示了细化的图形标签和边缘attention(与边缘宽度成比例)。 现有对于场景图生成的指标是基于召回⟨主题、谓词、对象⟩三元组或给定ground truth的object localizations的对象和谓词。为了揭示这些度量标准存在的问题，考虑一个方法，该方法将图1a中的boy误认为是man，但在其他方面识别出他是1)站在消防栓后面，2)靠近一辆汽车，3)穿着一件毛衣。在基于三元组的度量标准下，这个小错误(boy vs man)将被严重惩罚，尽管大多数boy的关系被正确识别。尽管提供ground-truth区域的度量方法通过严格关注关系预测来回避这个问题，但是它不能准确地反映整个场景图生成系统的测试时性能。 为了解决这种不匹配，我们引入了一种新的评估度量(SGGen+)，它更全面地评估场景图生成的性能，包括对象、属性(如果有的话)和关系。我们提出了度量SGGen +计算总的recall对于独立实体(对象和谓词),pair 实体⟨对象,属性⟩(如果有的话),和三元组实体⟨主题、谓词、对象⟩。我们在这个新的度量下报告现有方法的结果，发现我们的方法也显著地优于最先进的方法。更重要的是，这个新的度量为生成的场景图和真实场景图之间的相似性提供了一个更鲁棒、更全面的度量。 具体来说，本工作通过引入一种新的模型(graph R-CNN)来解决场景图生成问题，该模型可以利用对象关系的规律性，并提出了一种更全面的场景图生成评价指标(SGGen+)。我们将我们的模型与现有的标准度量方法进行基准测试，而这个新度量方法的性能优于现有方法。 利用上下文来提高场景理解的想法在计算机视觉中有着悠久的历史[16,27,28,30]。最近，Johnson等人受到图形界研究的表示方法的启发，提出了从图像中提取场景图的问题，这将对象检测的任务[6,7,22,31,32]概括为也检测对象的关系和属性。 已经提出了许多方法来检测对象及其关系。尽管这些工作中的大多数指出，对场景图中二次关系的推理是棘手的，但每个都采用了启发式方法，如随机抽样来解决这个问题。我们的工作是第一个引入一个可训练的关系建议网络(RePN)，它学会了在不牺牲efficacy的情况下从图中删除不可能的关系边缘。RePN提供了高质量的候选关系，我们发现它提高了场景图生成的整体性能。 大多数场景图生成方法还包括上下文传播和对候选场景图进行推理的机制，以细化最终的标记。在[40]中，Xu等人将问题分解为两个子图，一个用于对象，另一个用于关系，并执行消息传递。类似地，在[17]中，作者提出了两种消息传递策略(并行顺序)，用于在对象和关系之间传播信息。Dai等人将场景图生成过程建模为条件随机场(CRF)的推理。Newell等人提出直接从图像像素中生成场景图，而不需要使用基于关联图嵌入的对象检测器。在我们的工作中，我们开发了一种新的注意图卷积网络(aGCN)来更新节点和关系表示，通过在候选场景图的节点之间传播上下文来操作视觉和语义特征。虽然在功能上类似于上述基于消息传递的方法，但aGCN是高效的，可以学习将注意力放在可靠的边缘，并减弱不太可能的影响。 以往的许多方法都注意到在场景图生成过程中具有很强的规律性，从而激发了我们的方法。在[23]中，Lu等人整合了语言中的语义先验，以改进对对象之间有意义关系的检测。同样，Li等人[18]证明了region caption也可以为场景图生成提供有用的上下文。与我们的动机最相关的是，Zeller等人将motifs的概念(即经常出现的图结构)形式化。并在VG数据集[14]中检测它们的出现的概率。作者还提出了一个令人惊讶的强基线，它直接使用频率先验来明确地综合图结构中的规律来预测关系。 我们的关系建议网络(Relationship Proposal Network, RePN)受到了RPN的启发，与用于对象检测的faster R-CNN[32]的区域建议网络(region Proposal Network, RPN)紧密相关。我们的RePN在本质上也类似于最近提出的关系建议网络(Rel-PN)[45]。这些方法之间有许多细微的差别。Rel-PN模型独立地预测主题、对象和谓词的建议，然后重新对所有有效的三元组进行评分，而我们的RePN根据对象生成关系，允许它学习对象对关系的偏差。此外，他们的方法是类无关的，并没有用于场景图生成。 GCNs最初是在[13]的半监督学习环境中提出的。GCNs将图数据上的复杂计算分解为一系列局部化操作(通常只涉及相邻节点)，用于每个节点的每个时间步。在计算之前，结构和边缘强度通常是固定的。为了完整起见，我们注意到即将出版的出版物[36]同时独立地开发了一个类似的GCN注意机制(如aGCN)，并在其他(非计算机视觉)上下文中显示了它的有效性。 在这项工作中，我们将场景图建模为包含图像区域、关系及其标签的图。 代表image， 代表nodes集合(一个node对应一个localized object region)， 代表物体间的关系， 分别代表object和relationship的labels。因此，我们的目标是为 建模，在我们的工作中，我们把场景图的生成分解为三部分： 将图的构造(节点和边)与图的标注分离开来。这个因式分解背后的直觉很简单。首先，object region proposal 通常使用现成的对象检测系统(如faster rcnn[32])进行建模，以生成候选区域。值得注意的是，现有的方法通常将第二个关系建议项 建模为顶点 之间潜在边的均匀随机抽样。相反，我们提出了一个关系建议网络(RePN)来直接建模 ——使我们的方法成为第一个允许学习整个生成过程端到端。最后，图标记过程 通常被视为迭代求精过程。模型的pipeline如图2所示：每一个object proposal 都与一个空间区域 , 一个合并的特征向量 , 一个初始化估计标签分布 over 相关联。我们将对于所有n个proposals的向量集合表示为矩阵 以及 Relation Proposal Network 给定上一步提出的n个对象节点，它们之间可能有 个连接;然而，正如前面所讨论的，由于真实对象交互中的规则性，大多数对象对不太可能有关系。为了对这些规律进行建模，我们引入了一个关系建议网络(RePN)，该网络能够有效地估计对象对之间的关联性。通过对不太可能关系的边缘进行剪枝，可以有效地稀疏化候选场景图，保留可能的边缘，抑制不太可能的边缘带来的噪声。 在这篇论文中，我们利用估计的类别分布( )来推断关联性——本质上是学习软类别关系的先验。这种选择与我们的直觉一致，即与其他类相比，某些类相对不太可能交互。具体,给定初始对象分类分布 ,我们给所有的 有向对 评分, 计算 时的相关性，其中 是一个习得的相关性对函数。 的一个直接实现可以将连接[p^o_i, p^o_j]作为输入传递给一个多层感知器，该感知器输出分数。然而，考虑到对象对的平方数，这种方法将消耗大量的内存和计算。为了避免这种情况，我们考虑一个非对称的内核函数: 分别代表在关系中主语和宾语对映射函数。这个分解使得，仅使用 的两个投影过程，然后执行一次矩阵乘法就能获得分数矩阵 。对于 和 ，我们使用两个多层感知器(mlp)与相同的架构(但不同的参数)。我们还对分数矩阵S进行了sigmoid操作，使得每一个元素都为0～1之间。 在获得分数矩阵后，我们将其降序排序，然后选择前K对。然后，我们使用非最大抑制(NMS)来过滤出与其他对象有明显重叠的对象对。每个关系都有一对边界框，组合顺序很重要。我们计算两个对象对 and 之间对重叠： 计算两个box交集的区域， 计算并集区域。剩余的m个对象对被认为是具有意义关系E的候选对象。利用E，我们得到了一个图 ，它比原来的全连通图稀疏得多。随着图的边的提出，我们还通过从每个对象对的联合框中提取特征，得到所有m个关系的可视化表示 。 为了整合由图结构提供的上下文信息，我们提出了一个注意图卷积网络(aGCN)。在描述我们提出的aGCN之前，让我们简要回顾一下“普通的”GCN，其中每个节点 都有一个表示 如在[13]中提出的那样。简单,目标节点图中,相邻节点的表示 首先通过学习改变线性变换矩阵 .然后,这些转换表示与预先确定的权值α聚集,紧随其后的是一个非线性函数σ(ReLU [25])。这种分层传播可以写成: 或者我们可以把节点整合进一个矩阵中，就可以得到：与i不相邻的节点设定为0，并且设定αii为1。在传统的GCN中,图中的连接是已知并且系数向量αi是基于对称规范化邻接矩阵的特性预设的。 在这篇论文中，我们将传统的GCN拓展了attention版本，通过调节α。为了能够从节点features预测attention，我们通过一个拼接的节点feature学习了一个两层的MLP，并且对得到的分数进行一次softmax。对于节点i的attention是：and 是习得参数，[·, ·] 是拼接操作。通过定义，我们设定 and 。由于注意力机制是节点特征的函数，每次迭代都会导致注意力的改变，从而影响后续的迭代。 回想一下，在前面的小节中，我们有一组N个对象区域和m个关系。在此基础上，我们构造了一个图G，其中节点对应于对象和关系建议。我们在关系节点及其关联对象之间插入边。我们还在所有对象节点之间直接添加了跳转连接边。这些连接允许信息直接在对象节点之间流动。最近的研究表明，对目标相关性进行推理可以提高检测的性能。我们将aGCN应用于此图，基于全局上下文更新对象和关系表示。 注意到我们的图捕获到不同类型到连接（ ↔ relationship, relationship ↔ subject and object ↔ object）。此外，每个连接之间的信息流可能是不对称的(the 信息量 of subject on relationship might be quite different from relationship to subject)。我们学习了每种类型和顺序的不同转换——将节点类型a到节点类型b的线性转换表示为 ，其中s=subject、o=objects和r=relationships。Object node的representation的更新公式如下（object features为 , relationship features为 ）：with and similarly for relationship nodes as: 一个开放的选择是如何初始化object and relationship node represenstions ，它可能被设置为任何intermediate feature representations，甚至是对应类标签的pre-softmax输出。在实践中，我们同时运行可视化的和语义化的aGCN计算——一个具有可视化的特性，另一个使用pre-softmax输出。通过这种方式，我们既可以推断出较低层的视觉细节，也可以推断出较高级别的语义共现(即汽车轮子)。进一步地，我们把语义aGCN的注意力放在视觉aGCN上——基于视觉线索有效地调节语义信息流。这也加强了两个图中表示的真实对象和关系以相同的方式与其他对象交互。 Loss Function 在Graph R-CNN，我们把场景图生成过程分解成三个子过程： 。在训练阶段，这些子过程都是使用监督训练。对于 ，我们用RPN相同的损失（binary cross entropy loss on proposals，regression loss for anchors）。对于 ，我们使用另一个binary cross entropy loss on the relation proposals。对于最后的场景图生成 ，两个muti-class cross entropy losses是被用于object classification and predicate classification。 场景图生成是一个结构化的图上预测问题，如何正确、有效地对预测进行评价是当前场景图生成研究中尚未解决的问题。我们注意到图论[5]对基于最小图编辑距离的图相似度进行了深入的研究;然而，计算准确的解决方案是np完全和ap近似的APX-hard[20]。 以前的工作通过在[40]中引入一个简单的基于三元组回归的度量来评估场景图的生成，从而绕过了这些问题。根据这个指标,我们将称之为SGGen, the ground truth of 场景图表示为一组通过精确匹配计算。也就是说，在生成的场景图中，如果三个元素都被正确地标记，并且object和subject nodes都被正确地定位(例如，边界框IoU > )。虽然计算简单，但这种度量导致了一些不直观的相似度概念，如图3所示。 SGGen+的计算公式： 是一个计数操作， 是正确被定位和识别的物体节点数； 是正确谓词的数目。由于谓词的定位取决于subject和object的正确定位，所以只有在主语和宾语都正确定位并且正确识别谓词的情况下，我们才会将其算作一个。 是针对三元组的，和SGGen一样。N是ground真值图中的条目数(对象、谓词和关系的总数)。