Jul, 2020

基于优先级的平衡图分区再流算法

PDF
TL;DR介绍了一种新型的基于 restreaming 的算法，使用带有乘性权重的约束管理策略来优化流式过程的排序，同时借鉴了平衡标签传播的优先级概念来进行分区优化，得到了与现有算法相比在真实世界图上具有更好性能的结果。
graph partitioningiterative partitionersrestreamingbalanced label propagationmultiplicative weights
发现论文，激发创造
  • 多维均衡图分割的投影梯度下降算法

    我们研究了多维平衡图分区问题，提出一种基于随机投影梯度下降的可扩展技术来解决该问题，并在实验中表明该方法在大规模图处理时具有卓越的性能表现。

    Feb, 2019

  • 流式图挑战：随机块划分

    实现大规模图表分析的基础是合理的分区算法，本文提出了一种基于贝叶斯推断方法的分区算法，并介绍了数据集、并行计算、评估指标等多个方面，最终展示了其高效性。

    Aug, 2017

  • 有效局部搜索增强平衡图边划分

    本文研究了图分区中的边划分问题，提出了可调节的边和块的两个新概念，基于此发展了一种贪心启发式和一个利用最大流模型的改进搜索算法，可以大幅度提高图分区的质量和近似比。

    Dec, 2020

  • 双节点和边公平感知的图分区

    提出了一种使用边平衡来实现社交网络公平图分区的方法，并通过使用线性图转换和协同嵌入框架来学习图分区的双节点和边公平感知表征，并提出了一种公平分区可用作伪标签以促进图神经网络在节点分类和链接预测任务中表现公平。

    Jun, 2023

  • 快速平衡划分尽管在网格和树上也很困难

    本文探讨了 k-Balanced Partitioning 问题的两类近似算法：快速但准确度不高和保证高质量准确度但速度较慢的算法。研究表明，这种运行时间和解决方案质量之间的权衡是必要的。我们还提出了一种基于图形类别的规约框架，以证明了该问题的困难性。本文是该问题的第一次双层次不可近似结果。

    Nov, 2011

  • 图分割的最新进展

    论文探讨了平衡图分割领域中最近趋势的算法，应用和未来的研究方向。

    Nov, 2013

  • 利用流和重新加权特征值进行有向图划分的快速算法

    提供了一种基于对称正定半定规划的指向图划分算法，同时证明了此算法具备较好的扩展性。

    Jun, 2023

  • 基于深度强化学习的流处理通用资源分配

    本文介绍了一种图嵌入式的编码器 - 解码器框架，以实现在流处理中分配资源任务，同时确保工作负载平衡和通信最小化。采用深度强化学习方法，有效地学习和求解未知图的最优解，并在测试中表现优于 METIS 算法和基于 LSTM 的编码器 - 解码器模型约 70％。

    Nov, 2019

  • 基于划分储备抽样的不平衡连续学习

    本文研究了从多标签流数据中进行不断学习的挑战，探讨了在长尾标签分布下灾难性遗忘和少数概念上的破坏性遗忘，提出了一种名为 Partitioning Reservoir Sampling (PRS) 的新抽样策略来防止这种遗忘，并开放了数据集和代码。

    Sep, 2020

  • 图分割的高级粗化方案

    本研究探讨了图划分问题中的粗化阶段，通过比较不同的匹配和 AMG（代数多重网格）粗化方案，并通过在不同类型的图上进行实验来展示不同粗化方案的运行时间和质量优势。

    Jan, 2012