完全动态约束子模最大化google-research fully_dynamic_submodular_maximization 源码解析与实验复现指南【免费下载链接】google-researchGoogle Research项目地址: https://gitcode.com/gh_mirrors/go/google-research本篇技术指南围绕 Google Research 开源仓库中的fully_dynamic_submodular_maximization项目系统讲解论文Fully Dynamic Algorithm for Constrained Submodular Optimization的高效 C 实现包括算法抽象接口、子模函数 Oracle图覆盖 / 影响力最大化、动态算法与基线算法的内部结构以及如何修改参数、编译并复现论文实验。读完本文你将掌握该代码库的完整调用链能够自行更换数据集、调整基数约束 k、选择实验类型与算法组合并理解其只统计 Oracle 调用次数、不依赖运行环境的可复现实验设计。项目定位动态子模最大化问题的实验代码库README.md 明确指出这是论文Fully Dynamic Algorithm for Constrained Submodular Optimization中算法与基线的高效 C 实现对应的文件全部位于 fully_dynamic_submodular_maximization/ 目录。其研究场景是在元素持续插入insertion与删除deletion的流式环境下维护一个满足基数约束cardinality constraintk的集合使其子模目标函数值尽可能接近最优解。整个代码库由三个清晰的层次组成层次代表性文件职责算法抽象层algorithm.h定义动态最大化算法的统一接口子模函数抽象层submodular_function.h定义子模函数 Oracle 接口与调用计数具体实现层dynamic_submodular_algorithm.*、sieve_streaming_algorithm.*、greedy_algorithm.*、simple_greedy.*、random_subset_algorithm.*论文算法与各类基线的实现实验与工具层dynamic_submodular_main.cc、graph.*、graph_utility.*、utilities.h图数据加载、子模函数实例、实验编排、随机数工具由于抽象层把算法与子模函数彻底解耦读者既可以替换算法来评估不同动态策略也可以实现自己的子模函数 Oracle 来复用论文算法。核心抽象一Algorithm 接口 —— 统一的动态算法协议所有动态算法都继承自 algorithm.h 中的Algorithm抽象类。该接口完整刻画了在插入/删除流上做约束最大化这一任务的全部语义class Algorithm { public: // 初始化算法状态同时保存子模函数 f 与基数约束 k。 virtual void Init(const SubmodularFunction sub_func_f, int cardinality_k) 0; // 处理一个元素的插入。 virtual void Insert(int element) 0; // 处理一个元素的删除。 virtual void Erase(int element) 0; // 获取当前解的目标函数值。 virtual double GetSolutionValue() 0; // 获取当前解元素集合。 virtual std::vectorint GetSolutionVector() 0; // 获取算法名称用于实验输出。 virtual std::string GetAlgorithmName() const 0; };这套协议是理解全部实验代码的关键任何算法都只需实现初始化 / 插入 / 删除 / 查询解值 / 查询解集合五个动作实验框架即可在完全统一的方式下驱动它。仓库中实现该接口的算法如下dynamic_submodular_algorithm.h ——OurSimpleAlgorithm论文Section 3提出的简单算法是本项目的主角sieve_streaming_algorithm.h ——SieveStreamingBadanidiyuru 等人的 Sieve-Streaming 算法的忠实模拟元素一旦从解中被删除就重跑 sievegreedy_algorithm.h ——Greedy贪心算法的增强版始终维护一个完整解插入/删除时增量重算通过保留 k 份函数前缀副本换取速度内存更大输出与 SimpleGreedy 等价simple_greedy.h ——SimpleGreedy朴素贪心基线random_subset_algorithm.h —— 随机子集基线。核心抽象二SubmodularFunction 接口 —— 可插拔的子模 Oracle论文算法假设可以查询一个子模函数即所谓的Oracle 访问模型。submodular_function.h 中SubmodularFunction抽象类把这一假设形式化函数对象内部维护一个当前集合 S 作为状态派生类需要实现四个纯虚函数class SubmodularFunction { public: static int64_t oracle_calls_; // 全局 Oracle 调用计数器 virtual void Reset() 0; // 令 S 空集 virtual const std::vectorint GetUniverse() const 0; // 元素全集 virtual std::string GetName() const 0; virtual std::unique_ptrSubmodularFunction Clone() const 0; protected: virtual void Add(int element) 0; // 把 e 加入集合 S virtual double Delta(int element) const 0; // 计算 f(S ∪ {e}) − f(S) };在受保护的原语之上基类提供了三个自动计数的公共方法实现在 submodular_function.ccAddAndIncreaseOracleCall(int element)把元素加入 S 并令oracle_calls_自增DeltaAndIncreaseOracleCall(int element)返回加入元素的边际增益并计数AddAndIncreaseOracleCall(int element, double thre)仅当边际贡献 ≥ thre 时才加入元素并返回贡献增量否则返回 0。注意oracle_calls_是static int64_t全局静态变量这正是后面只统计 Oracle 调用次数而非 CPU 时间这一实验设计的基础每次对子模函数的基本查询都会被精确记账供实验框架统计每个算法在每个 k 值下的调用开销。此外基类还提供了GetOptEstimates(int cardinality_k)见 submodular_function.cc返回一组几何递增的 OPT 估计值先扫描全集取单元素边际增量的最小值作为 OPT 下界、最大值 × k 作为上界再按公比1 0.3在LogSpace中生成估计序列。Sieve-Streaming 与论文算法都会为每个 γ 估计各维护一个单阈值子算法。自定义子模函数继承 SubmodularFunctionREADME 特别指出要实现自己的子模函数只需继承SubmodularFunctionTo implement your own submodular function oracle, inherit from SubmodularFunction. Refer to comments in the code for more details.。即至少实现Reset、GetUniverse、GetName、Clone以及受保护的Add、Delta六个方法并让Delta返回加入元素 e 后对目标函数的边际贡献让Add真正更新内部集合状态。仓库中的 graph_utility.cc 就是这一过程的完整范本。已实现 Oracle图覆盖 / 影响力最大化的子模函数论文实验采用**图覆盖graph coverage/ 影响力最大化influence maximization**场景仓库为此提供了两层实现Graph图数据容器graph.h 中的Graph类负责存储一张图例如社交网络其头文件注释明确给出了输入格式普通图每行一条边每条边为两个空格分隔的整数DBLP每行一条边边之后附带一个年份字段对应publicationDates_成员从源码结构看 DBLP 带有发布时间的特殊支持。Graph通过静态工厂方法GetGraph(name)按名称缓存实例并提供三类关键数据GetCoverableVertices()可覆盖顶点即所有有入边的顶点对应被覆盖集合GetUniverseVertices()全集顶点即所有有出边的顶点对应子模函数的元素全集GetNeighbors(int vertex_i)顶点的邻居列表。GraphUtility覆盖函数 Oraclegraph_utility.h 中的GraphUtility : public SubmodularFunction把上述图封装成覆盖函数// 加入元素 e 带来的边际覆盖量e 的邻居中尚未被覆盖的顶点个数。 double GraphUtility::Delta(int element) const { int val 0; for (int x : graph_.GetNeighbors(element)) { if (!present_elements_[x]) val; // present_elements_ 记录当前已覆盖顶点 } return val; } // 把 e 的邻居全部标记为已覆盖。 void GraphUtility::Add(int element) { for (int x : graph_.GetNeighbors(element)) present_elements_[x] true; }代码见 graph_utility.cc。覆盖函数天然的单调子模性使其成为动态子模最大化论文的标准实验载体选哪些顶点作为种子能覆盖最多邻居正是影响力最大化的经典抽象。GraphUtility的构造函数还会做数据完整性检查若最大覆盖顶点编号超过5e8会调用Fail报错looks like vertices were not renumbered?提示顶点可能未被连续重编号。主角算法OurSimpleAlgorithm论文 Section 3 的简单动态算法dynamic_submodular_algorithm.h 与 dynamic_submodular_algorithm.cc 实现了论文的核心贡献。它采用多阈值并行 层级level重构的设计单阈值子算法OurSimpleAlgorithmSingleThreshold每个 γ 估计对应一个OurSimpleAlgorithmSingleThreshold实例其内部维护论文中的三组数据结构头文件注释明确标注了与论文符号的对应关系buffer_B_尚未被纳入层级结构的元素论文中的B数据结构levels_A_各层级的元素集合论文中的Asolutions_S_各层级的解元素集合论文中的Ssize_of_S_记录其并集大小。关键方法LevelConstruct(int l_begin)实现了论文的LevelConstruct算法从第l_begin层开始重建 A、B、S。重建时用RandomHandler::Shuffle随机打乱元素顺序自实现的跨平台可复现洗牌以gamma_ / (2 * cardinality_k_)为阈值过滤掉边际贡献过低的元素并在size_of_S_达到 k 时提前终止见 dynamic_submodular_algorithm.cc。插入与删除处理Insert先判断元素边际增量是否 ≥gamma_ / (2k)不满足直接丢弃否则把元素插入所有层级的 buffer_B_并检查是否有层级触发LevelConstruct条件buffer_B_[l].size() 2^(num_T − l)且解未满 kErase从 A、B 中移除该元素若元素在某个 S 集合中则将其移出、size_of_S_减一并重算目标值。若目标值跌破(1 − eps) × gamma_ / 2则从lowest_level_起执行LevelConstruct重构——这正是懒重构思想的体现只有解的质量下降超过 ε 阈值时才触发代价较高的重建GetSolutionValue按层级顺序取至多 k 个元素用共享的子模函数副本计算目标值并在自己的 Oracle 计数模型中只记一次调用oracle_calls_ - 2 * count - 1。多阈值并行与 ε 参数OurSimpleAlgorithm(double eps)在Init时为每个 OPT 估计各生成一个单阈值实例num_T ⌈log₂|U|⌉GetSolutionValue/GetSolutionVector在所有子算法中取最优。构造函数接收的eps是解价值下降触发重构的松弛阈值main 中分别以0.0和0.2实例化两个版本进行对照实验。基线算法SieveStreaming、Greedy 与随机子集为公平评估动态算法仓库实现了若干基线SieveStreamingsieve_streaming_algorithm.hBadanidiyuru et al. 的经典流式算法头文件注明它是忠实模拟——每当一个元素从解中被删除sieve 就重跑一遍。它同样用多个SingleThresholdSieve子算法并行猜测 OPT每个子算法持有一个gamma_与当前解solution_、前缀目标值obj_vals_。值得注意的是它用一个stream_向量 position_on_stream_哈希表忠实记录元素到达顺序保证模拟与真实流式语义一致Greedygreedy_algorithm.h贪心的增强版始终让解保持可用状态插入/删除时更快地增量重算代价是保留 k 份函数前缀副本partial_F_内存更大输出与 SimpleGreedy 等价SimpleGreedysimple_greedy.h与RandomSubsetrandom_subset_algorithm.h朴素贪心与随机子集基线。实验框架窗口实验与先按序插入、再从大到小删除实验实验代码集中在 dynamic_submodular_main.cc。README 提到type of experiment (sliding window, etc.)——源码中实际定义了两个实验函数windowExperiment滑窗实验double windowExperiment(SubmodularFunction sub_func_f, Algorithm alg, int windowSize) { // 按全集顺序逐个处理元素 // 始终维护一个大小不超过 windowSize 的窗口 // i |U| 时执行 alg.Insert(Universe[i]) // i windowSize 时执行 alg.Erase(Universe[i - windowSize]) // 每步记录 alg.GetSolutionValue()最终返回平均值。 }见 dynamic_submodular_main.cc。这是论文完全动态场景的直接体现窗口随时间滑动新元素进入、旧元素离开算法必须持续维护高质量解。insertInOrderThenDeleteLargeToSmall先插入后删除另一个实验先按全集顺序插入全部元素再按边际贡献从大到小依次删除先删最有价值的元素对动态算法最具挑战性全程记录解值并返回平均值见 dynamic_submodular_main.cc。runExperimentForAlgorithms统一编排模板函数runExperimentForAlgorithmsdynamic_submodular_main.cc负责把若干算法 × 若干 k 值组合起来批量跑实验对每个算法、每个 k先用RandomHandler::generator_.seed()重新播种随机数保证随机化算法的可复现性调用alg.Init(sub_func_f, cardinality_k)记录实验前后的oracle_calls_差值作为该配置下的 Oracle 调用数依次打印两种结果表k fk 与平均目标函数值、k OCk 与 Oracle 调用次数。复现论文结果三步走实战操作README 给出了完整的复现流程下面结合源码展开每一步第 1 步编辑 main() 选择实验参数打开 dynamic_submodular_main.cc 末尾的main()函数第 L177-L202 行按需修改数据集名称README 给出的示例是GraphUtility f_graph(enron)当前 main() 中实际实例化的是GraphUtility f_pokec(pokec)第 L185 行。也就是说只需替换构造参数即可切换数据集其他代码不变基数约束集合main() 预置了两组 k 值——from10to20010 到 200步长 10与from20to20020 到 200步长 20可自行增删实验类型当前 main() 只运行windowExperiment并分别以窗口大小2000000、1300000各跑一遍第 L195 行如需其他实验如insertInOrderThenDeleteLargeToSmall在 main() 中按同样模式调用runExperimentForAlgorithms即可重复次数runExperimentForAlgorithms内部已对每个 k 重新播种随机数随机化算法如OurSimpleAlgorithm的重复实验可通过增加/调整实验函数中的循环实现README 称之为 number of repeats算法组合main() 中已实例化SieveStreaming sieveStreaming;、SimpleGreedy simpleGreedy;、Greedy greedy;、OurSimpleAlgorithm ourSimpleAlgorithmEps00(0.0);与ourSimpleAlgorithmEps02(0.2)选择参与实验的算法只需在runExperimentForAlgorithms的算法列表参数中增删即可第 L198-L200 行展示了用 ε0.0、ε0.2 的两个论文算法版本与 SieveStreaming 对照。main()中各处的注释即为 README 所称See the comments in main() for how to adjust the parameters的详细指引。第 2 步编译在 fully_dynamic_submodular_maximization/ 目录下执行make预期生成可执行文件dynamic-submodular.exe。需要注意当前仓库目录下未附带 Makefile 文件因此若直接执行make失败可依据 dynamic_submodular_main.cc 头部注释compile this as C14 (or later)手动编译例如将全部.cc文件一并编译并链接如g -O2 -stdc14 *.cc -o dynamic-submodular.exe具体链接参数以实际编译器环境为准。第 3 步运行./dynamic-submodular.exe程序按runExperimentForAlgorithms的顺序逐算法打印结果先是k f表k 与平均目标函数值随后是k OC表k 与 Oracle 调用次数可据此直接绘制论文中目标值—k与调用次数—k的对比曲线。为什么运行环境不影响结果README 特别强调As we use cross-platform-deterministic randomness and count only oracle calls rather than CPU time, parameters of the system on which the experiments are run are irrelevant.我们使用跨平台确定性随机数并且只统计 Oracle 调用次数而非 CPU 时间因此实验运行所在系统的参数无关紧要。这一设计在源码中有三重支撑确定性随机源utilities.h 中的RandomHandler使用默认初始化的std::mt19937generator_无随机种子即每次运行产生相同序列并实现了自有的Shuffle洗牌函数不依赖标准库实现细节从而保证跨平台可复现随机源自检RandomHandler::CheckRandomNumberGenerator()验证默认构造的 std::mt19937 第 10000 次调用必须产生 4123659995这一 C 标准要求若不符会向cerr打印警告提示随机性可能与原始实现不一致main() 第一行即调用此检查见 dynamic_submodular_main.cc以 Oracle 调用为度量所有实验指标k OC表基于SubmodularFunction::oracle_calls_静态计数器与机器 CPU、内存等硬件参数完全解耦换机器跑结果一致。扩展指南接入自己的子模函数与算法若要在该框架上做自己的研究从源码结构看最自然的路径有两条新子模函数继承SubmodularFunction实现Reset/GetUniverse/GetName/Clone与Add/Delta参考 graph_utility.cc 的写法即可随后在 main() 中把GraphUtility f_graph(pokec)换成你的函数实例全部算法与实验框架无需改动即可复用新动态算法继承Algorithm实现Init/Insert/Erase/GetSolutionValue/GetSolutionVector/GetAlgorithmName参考 dynamic_submodular_algorithm.cc 的接口用法即可直接接入runExperimentForAlgorithms与现有基线公平对比。小结fully_dynamic_submodular_maximization是一份结构清晰、抽象良好的论文配套代码Algorithm接口定义了动态最大化的统一协议SubmodularFunction接口实现了可插拔的子模 OracleGraphUtility提供了图覆盖/影响力最大化的标准实验载体而OurSimpleAlgorithm则完整呈现了论文 Section 3 基于多阈值 层级懒重构的动态算法思想。配合跨平台确定性随机数与 Oracle 调用计数机制任何人都能低成本复现论文实验并在此框架上快速扩展新的函数或算法。【免费下载链接】google-researchGoogle Research项目地址: https://gitcode.com/gh_mirrors/go/google-research创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考