企业官网建设流程全解析

完全动态约束子模最大化：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 constraint）k的集合，使其子模目标函数值尽可能接近最优解。

整个代码库由三个清晰的层次组成：

由于抽象层把"算法"与"子模函数"彻底解耦，读者既可以替换算法来评估不同动态策略，也可以实现自己的子模函数 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::vector<int> GetSolutionVector() = 0; // 获取算法名称（用于实验输出）。 virtual std::string GetAlgorithmName() const = 0; };

这套协议是理解全部实验代码的关键：任何算法都只需实现"初始化 / 插入 / 删除 / 查询解值 / 查询解集合"五个动作，实验框架即可在完全统一的方式下驱动它。仓库中实现该接口的算法如下：

• dynamic_submodular_algorithm.h ——OurSimpleAlgorithm：论文Section 3提出的"简单算法"，是本项目的主角；
• sieve_streaming_algorithm.h ——SieveStreaming：Badanidiyuru 等人的 Sieve-Streaming 算法的忠实模拟（元素一旦从解中被删除就重跑 sieve）；
• greedy_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::vector<int>& GetUniverse() const = 0; // 元素全集 virtual std::string GetName() const = 0; virtual std::unique_ptr<SubmodularFunction> 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.cc）：

• AddAndIncreaseOracleCall(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 与论文算法都会为每个 γ 估计各维护一个"单阈值"子算法。

自定义子模函数：继承 SubmodularFunction

README 特别指出：要实现自己的子模函数，只需继承SubmodularFunction（"To 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：覆盖函数 Oracle

graph_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_：各层级的元素集合（论文中的A）；
• solutions_S_：各层级的解元素集合（论文中的S，size_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)且解未满 k）；
• Erase：从 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 与随机子集

为公平评估动态算法，仓库实现了若干基线：

• SieveStreaming（sieve_streaming_algorithm.h）：Badanidiyuru et al. 的经典流式算法，头文件注明它是"忠实模拟"——每当一个元素从解中被删除，sieve 就重跑一遍。它同样用多个SingleThresholdSieve子算法并行猜测 OPT（每个子算法持有一个gamma_与当前解solution_、前缀目标值obj_vals_）。值得注意的是它用一个stream_向量 +position_on_stream_哈希表忠实记录元素到达顺序，保证模拟与真实流式语义一致；
• Greedy（greedy_algorithm.h）：贪心的"增强版"，始终让解保持可用状态，插入/删除时更快地增量重算，代价是保留 k 份函数前缀副本partial_F_（内存更大，输出与 SimpleGreedy 等价）；
• SimpleGreedy（simple_greedy.h）与RandomSubset（random_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：统一编排

模板函数runExperimentForAlgorithms（dynamic_submodular_main.cc）负责把"若干算法 × 若干 k 值"组合起来批量跑实验：

• 对每个算法、每个 k：先用RandomHandler::generator_.seed()重新播种随机数（保证随机化算法的可复现性），调用alg.Init(sub_func_f, cardinality_k)，记录实验前后的oracle_calls_差值作为该配置下的 Oracle 调用数；
• 依次打印两种结果表：k f（k 与平均目标函数值）、k OC（k 与 Oracle 调用次数）。

复现论文结果：三步走实战操作

README 给出了完整的复现流程，下面结合源码展开每一步：

第 1 步：编辑 main() 选择实验参数

打开 dynamic_submodular_main.cc 末尾的main()函数（第 L177-L202 行），按需修改：

• 数据集名称：README 给出的示例是GraphUtility f_graph("enron")；当前 main() 中实际实例化的是GraphUtility f_pokec("pokec")（第 L185 行）。也就是说，只需替换构造参数即可切换数据集，其他代码不变；
• 基数约束集合：main() 预置了两组 k 值——from10to200（10 到 200，步长 10）与from20to200（20 到 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 C++14 (or later)"）手动编译，例如将全部.cc文件一并编译并链接（如g++ -O2 -std=c++14 *.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 时间，因此实验运行所在系统的参数无关紧要。）这一设计在源码中有三重支撑：

1. 确定性随机源：utilities.h 中的RandomHandler使用默认初始化的std::mt19937（generator_无随机种子，即每次运行产生相同序列），并实现了自有的Shuffle洗牌函数（不依赖标准库实现细节），从而保证跨平台可复现；
2. 随机源自检：RandomHandler::CheckRandomNumberGenerator()验证"默认构造的 std::mt19937 第 10000 次调用必须产生 4123659995"这一 C++ 标准要求，若不符会向cerr打印警告，提示随机性可能与原始实现不一致（main() 第一行即调用此检查，见 dynamic_submodular_main.cc）；
3. 以 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接口实现了可插拔的子模 Oracle，GraphUtility提供了图覆盖/影响力最大化的标准实验载体，而OurSimpleAlgorithm则完整呈现了论文 Section 3 基于"多阈值 + 层级懒重构"的动态算法思想。配合跨平台确定性随机数与 Oracle 调用计数机制，任何人都能低成本复现论文实验，并在此框架上快速扩展新的函数或算法。

【免费下载链接】google-researchGoogle Research项目地址: https://gitcode.com/gh_mirrors/go/google-research