子 图 匹 配 任 务 就 是 在 一 张 大 图 G 中 找 出 与 给 定 的 查 询 图 q 同 构 的 所 有 子 图, 并 输 出 这 些 同 构 子 图 图 G 规 模 一 般 较 大, 在 子 图 匹 配 任 务 中 称 为 数 据 图 需 4 c 1 a b 2 d 3 3 d 1

技 能 赛 命 题 2 基 于 Spark 的 同 构 子 图 查 询 1 题 目 描 述 现 实 生 活 中 的 很 多 关 系, 例 如 社 交 网 络 互 联 网 网 页 超 链 关 系 语 义 网 生 物 作 用 网 络 等, 都 可 以 用 离 散 数 学 中 的 图 加 以 描 述 并 进 行 分 析 随 着 计 算 技 术 的 发 展, 现 实 世 界 产 生 的 图 数 据 规 模 越 来 越 大 Facebook 的 社 交 网 络 目 前 已 经 包 括 至 少 9 亿 日 常 活 跃 用 户, 每 个 用 户 平 均 有 130 个 朋 友 而 根 据 估 计, 目 前 互 联 网 网 页 的 数 目 已 经 超 过 48 亿 个 面 对 大 规 模 的 图 分 析 任 务, 单 机 处 理 已 经 力 不 从 心, 需 要 人 们 利 用 分 布 式 计 算 系 统 进 行 并 行 处 理 子 图 匹 配 是 图 分 析 中 的 一 个 基 础 操 作, 被 广 泛 应 用 于 蛋 白 相 互 作 用 网 络 分 析 知 识 库 程 序 分 析 等 应 用 中 本 题 目 希 望 选 手 利 用 Spark 平 台 并 行 化 子 图 匹 配 算 法, 使 子 图 匹 配 操 作 能 高 效 地 在 大 规 模 图 数 据 集 上 完 成 1.1 子 图 匹 配 问 题 定 义 在 本 题 目 中, 主 要 考 虑 带 标 签 (label) 的 子 图 匹 配 任 务 假 设 有 向 图 G 定 义 为 : G = (V, E, T, l G ) 其 中 V 是 顶 点 集,E 是 边 集,T 是 标 签 集,l G : V T 是 标 签 函 数,l G 为 每 一 个 顶 点 赋 予 标 签 集 合 T 中 的 一 个 标 签 1 1 图 中 的 标 签 主 要 用 来 对 图 的 顶 点 进 行 分 类 以 社 交 网 络 为 例, 社 交 网 络 图 中 的 顶 点 代 表 了 现 实 世 界 中 的 人, 我 们 可 以 用 人 的 性 别 属 性 给 顶 点 贴 上 标 签 ; 假 设 标 签 集 T={1,2} 分 别 代 表 男 性 和 女 性, 则 图 G 的 标 签 函 数 l G 就 标 明 了 每 个 顶 点 对 应 的 人 的 性 别 一 般 来 说, 图 的 标 签 集 规 模 很 小, 远 小 于 图 顶 点 的 数 量 当 图 的 标 签 集 中 只 有 一 个 标 签 时 ( 即 标 签 集 大 小 为 1), 表 示 图 中 所 有 的 顶 点 都 具 有 相 同 的 标 签, 此 时 该 图 就 退 化 成 了 一 个 无 标 签 图 ( 标 签 没 有 区 分 性, 等 价 于 所 有 顶 点 都 没 有 标 签 ) 1

子 图 匹 配 任 务 就 是 在 一 张 大 图 G 中 找 出 与 给 定 的 查 询 图 q 同 构 的 所 有 子 图, 并 输 出 这 些 同 构 子 图 图 G 规 模 一 般 较 大, 在 子 图 匹 配 任 务 中 称 为 数 据 图 需 4 c 1 a b 2 d 3 3 d 1 2 a a b c 4 5 b 6 (a) 查 询 图 q (b) 数 据 图 G 图 1 子 图 匹 配 操 作 示 例 蓝 色 边 标 识 出 了 其 中 一 个 匹 配 的 子 图 要 被 查 询 的 图 q 规 模 通 常 较 小, 在 子 图 匹 配 任 务 中 称 为 查 询 图 图 1 展 示 了 一 个 子 图 匹 配 的 例 子 图 1 (a) 中 是 需 要 被 查 询 的 查 询 图 q, 图 1 (b) 中 是 数 据 图 G 数 据 图 G 中 一 个 匹 配 q 的 子 图 已 经 用 蓝 色 边 标 识 出 来 了 下 面 给 出 子 图 匹 配 任 务 的 形 式 化 定 义 数 据 图 G 的 定 义 见 上 文 查 询 图 的 定 义, 和 子 图 匹 配 任 务 的 定 义 见 后 文 查 询 图 定 义 查 询 图 q = (V q, E q, T q, l q ) 其 中 V q 是 查 询 图 的 顶 点 集,E q 是 查 询 图 的 边 集,T q 是 标 签 集 l q : V q T q 是 标 签 函 数, 将 查 询 图 中 的 顶 点 映 射 到 标 签 集 T q 上 查 询 图 的 标 签 集 T q 可 以 确 保 是 数 据 图 标 签 集 T 的 子 集 子 图 匹 配 问 题 对 于 一 张 有 向 数 据 图 G = (V, E, T, l G ) 和 一 个 查 询 图 q = (V q, E q, T q, l q ), 子 图 匹 配 的 目 标 是 在 数 据 图 G 中, 找 出 所 有 满 足 如 下 三 个 条 件 的 子 图 g = (V g, E g ): 1. 子 图 条 件 V g V, E g E; 2. 规 模 匹 配 条 件 匹 配 到 的 子 图 的 点 集 边 集 大 小 必 须 与 查 询 图 点 集 边 集 大 小 相 同, 即 V q = V g 且 E q = E g, 其 中 V q 表 示 集 合 V q 的 元 素 个 数 ; 3. 同 构 匹 配 条 件 存 在 从 查 询 图 q 的 点 集 到 同 构 子 图 g 的 点 集 的 一 个 双 射 f: V q V g, 该 2

双 射 f 同 时 满 足 : a) 标 签 匹 配 对 应 顶 点 的 标 签 相 同, 即 v V q, l q (v) = l G (f(v)); b) 拓 扑 结 构 匹 配 e = (u, v) E q, (f(u), f(v)) E g 同 构 匹 配 条 件 中 的 映 射 f 指 定 了 查 询 图 q 的 顶 点 如 何 同 构 地 映 射 到 子 图 g 的 顶 点 上 不 同 的 f 对 应 着 不 同 的 子 图 映 射 图 1 展 示 了 一 个 子 图 匹 配 的 示 例 图 中 顶 点 圆 圈 内 的 英 文 字 母 表 示 顶 点 的 标 签, 顶 点 旁 的 数 字 表 示 顶 点 编 号 在 图 1 (b) 所 示 的 数 据 图 G 中 查 询 图 1 (a) 所 示 的 子 图 q, 将 得 到 两 个 匹 配 的 子 图 图 1 (b) 中 的 蓝 色 线 条 标 识 出 了 其 中 的 一 个 匹 配 子 图 (1,4,3,5) (1,4,3,5) 的 意 思 是 数 据 图 G 中 的 1 4 3 5 号 顶 点 构 成 了 一 个 查 询 图 q 的 同 构 子 图, 数 据 图 G 中 的 1 4 3 5 号 顶 点 依 次 映 射 为 查 询 图 q 中 的 1 2 3 4 号 顶 点 可 以 验 证 该 子 图 满 足 子 图 匹 配 的 三 个 条 件, 是 查 询 图 q 的 匹 配 子 图 除 了 (1,4,3,5) 构 成 的 子 图, 在 图 1 中 还 存 在 另 一 个 匹 配 子 图, 它 的 映 射 关 系 序 列 是 (2,4,3,5), 选 手 可 自 行 验 证 1.2 本 题 任 务 题 目 将 给 出 一 个 数 据 图 G 和 一 个 查 询 图 q 请 编 写 Spark 程 序, 在 数 据 图 G 中 完 成 子 图 匹 配 任 务, 输 出 与 查 询 图 q 同 构 的 所 有 子 图 1.3 输 入 数 据 集 本 题 目 将 提 供 三 个 不 同 规 模 的 输 入 数 据 集 供 选 手 调 试 程 序 和 评 测 性 能 三 个 数 据 集 的 数 据 图 G 的 规 模 如 表 格 1 所 示 在 每 个 输 入 数 据 集 中, 同 时 配 套 有 一 个 示 例 性 的 查 询 图 q 选 手 可 以 通 过 该 文 件 了 解 输 入 文 件 格 式 调 试 自 己 的 程 序 在 评 测 阶 段, 比 赛 组 委 会 将 根 据 所 有 选 手 的 答 题 情 况, 另 外 选 择 新 的 查 询 图 进 行 测 评 3

表 格 1 数 据 集 规 模 数 据 集 名 称 数 据 图 顶 点 数 数 据 图 边 数 标 签 集 规 模 Gnutella08 2 6,301 20,777 1 WordNet 3 76,853 132,537 5 US Patents 4 3,774,768 16,518,947 416 2 提 交 材 料 请 选 手 提 交 如 下 材 料 1. 程 序 源 代 码, 要 求 提 供 包 含 完 整 目 录 结 构 的 src 代 码 包, 并 且 提 供 编 译 方 法 说 明 如 用 Scala+sbt 实 现 时, 提 交 目 录 结 构 如 下 的 程 序 文 件 和 sbt 文 件./src main scala Main.scala 因 为 在 必 要 时, 会 重 新 编 译 选 手 程 序 进 行 评 测, 请 在 提 交 代 码 时 附 带 编 译 方 法 说 明 2. 程 序 可 执 行 jar 包,jar 包 将 会 以 前 述 命 令 运 行 评 测 3. 程 序 设 计 报 告 报 告 内 容 包 括 但 不 局 限 于 程 序 采 用 的 算 法 进 行 的 优 化 工 作 优 化 取 得 的 效 果 等 2 数 据 集 来 源 :https://snap.stanford.edu/data/p2p-gnutella08.html 3 数 据 集 来 源 :http://vlado.fmf.uni-lj.si/pub/networks/data/dic/wordnet/wordnet.htm 4 数 据 集 来 源 :http://vlado.fmf.uni-lj.si/pub/networks/data/patents/patents.htm 4

3 附 录 A 程 序 设 计 约 束 3.1 输 入 文 件 格 式 一 个 输 入 数 据 集 由 一 张 数 据 图 G 和 一 张 查 询 图 q 组 成 数 据 图 G 和 查 询 图 q 使 用 相 同 的 文 件 格 式 进 行 描 述 而 每 一 张 图 使 用 点 集 文 件 和 边 集 文 件 两 个 输 入 文 件 进 行 描 述 3.1.1 点 集 文 件 格 式 点 集 文 件 是 一 个 文 本 文 件, 由 若 干 行 组 成 每 一 行 均 由 两 个 以 英 文 空 格 分 隔 的 正 整 数 组 成 : Vid LabelID 第 一 个 整 数 Vid 是 顶 点 编 号 第 二 个 整 数 LabelID 是 顶 点 对 应 的 标 签 假 设 图 1 中 的 四 个 标 签 a,b,c,d 分 别 用 整 数 1,2,3,4 表 示, 那 么 图 1 中 数 据 图 G 的 点 集 文 件 为 : 1 1 2 1 3 4 4 2 5 3 6 2 图 1 中 查 询 图 q 的 点 集 文 件 为 : 1 1 2 2 3 4 4 3 3.1.2 边 集 文 件 格 式 边 集 文 件 也 是 一 个 文 本 文 件, 由 若 干 行 组 成 每 一 行 均 由 两 个 以 英 文 空 格 分 隔 的 正 整 数 组 成 : Vid1 Vid2 第 一 个 整 数 Vid1 是 有 向 边 起 始 顶 点 编 号 第 二 个 整 数 Vid2 是 有 向 边 终 点 顶 5

点 的 编 号 图 1 (b) 中 数 据 图 G 的 边 集 文 件 的 部 分 内 容 为 : 1 3 3 1 1 4 4 1 1 5 5 1 2 4 2 5 图 1 (b) 中 查 询 图 q 的 边 集 文 件 的 内 容 为 : 1 4 1 2 2 3 4 2 3.2 输 出 文 件 格 式 请 输 出 与 查 询 图 q 同 构 的 所 有 子 图 到 一 个 或 多 个 文 本 文 件 中 输 出 时, 每 个 同 构 的 子 图 在 输 出 文 件 中 占 据 一 行 该 行 内 容 用 以 说 明 匹 配 时 的 映 射 函 数 f 每 一 行 由 若 干 以 英 文 逗 号 分 隔 的 顶 点 编 号 组 成, 格 式 如 下 所 示 : Vid1,Vid2,Vid3,Vid4,,VidK 这 表 示 数 据 图 G 的 Vid1 号 顶 点 对 应 查 询 图 q 的 1 号 顶 点, 数 据 图 的 Vid2 号 顶 点 对 应 查 询 图 q 中 的 2 号 顶 点, 数 据 图 中 Vid3 号 顶 点 对 应 q 中 的 3 号 顶 点, 依 次 类 推 例 如 在 图 1 (b) 中 的 数 据 图 G 上, 对 图 1 (a) 所 示 的 查 询 图 q 进 行 子 图 匹 配 操 作, 一 共 可 以 找 到 2 个 同 构 的 子 图, 对 应 的 输 出 文 件 的 内 容 如 下 : 1,4,3,5 2,4,3,5 只 要 子 图 的 匹 配 映 射 函 数 f 不 同, 即 算 作 不 同 的 匹 配 子 图 例 如 在 图 2 所 示 的 示 例 中, 利 用 查 询 图 q 去 匹 配 数 据 图 G 时, 一 共 可 以 产 生 6 种 不 同 的 匹 配 方 6

案 映 射 序 列 (4,1,2) 和 (4,2,1) 对 应 的 匹 配 子 图 虽 然 有 相 同 的 点 集 和 边 集, 在 输 出 时, 请 当 作 不 同 的 映 射 序 列 处 理 b 1 1 a 3 a a (a) 查 询 图 q 2 图 2 对 称 匹 配 示 例 2 3 a b a 4 (b) 数 据 图 G 3.3 程 序 运 行 方 式 每 个 参 赛 组 提 交 的 程 序 jar 包 将 会 以 如 下 格 式 的 命 令 运 行 进 行 评 测 ( 请 严 格 按 照 题 目 要 求 的 环 境 来 编 写 和 测 试 程 序, 另 外 不 要 将 数 据 集 大 小,Spark 集 群 的 Master URI, 输 入 输 出 路 径,jar 包 路 径 等 参 数 写 死 在 程 序 里!): ${SPARK_HOME/bin}/spark-submit \ --master <test spark cluster master uri> \ --class subgraph.main \ --executor.memory 20G \ --driver.memory 20G \ <your jar file path> \ hdfs://< 数 据 图 点 集 文 件 路 径 > \ hdfs://< 数 据 图 边 集 文 件 路 径 > \ hdfs://< 查 询 图 点 集 文 件 路 径 > \ hdfs://< 查 询 图 边 集 文 件 路 径 > \ hdfs://< 匹 配 结 果 输 出 文 件 路 径 > \ hdfs://< 临 时 工 作 目 录 路 径 > 7

请 选 手 按 照 上 述 运 行 方 式 要 求 进 行 程 序 设 计 其 中 主 类 名 已 设 置 好, 如 选 手 想 选 用 其 他 名 称, 务 必 另 外 添 加 文 件 说 明 需 要 运 行 的 主 类 名 选 手 的 程 序 请 正 确 处 理 6 个 命 令 行 参 数, 输 入 输 出 文 件 的 存 储 位 置 将 由 这 些 命 令 行 参 数 指 定 请 选 手 注 意, 所 有 参 数 中 出 现 的 文 件 路 径 均 是 以 hdfs://xxxx/yyyy/zzzz 的 形 式 表 示 的 HDFS 路 径 所 有 输 入 输 出 文 件 都 要 保 存 在 HDFS 上 选 手 在 输 出 匹 配 结 果 时, 既 可 以 将 匹 配 结 果 写 入 单 个 文 本 文 件, 也 可 以 将 匹 配 结 果 写 到 一 个 文 件 夹 内, 文 件 夹 中 存 放 若 干 以 part-xxx 格 式 命 名 的 文 本 文 件, 在 评 测 时 评 测 系 统 会 自 动 将 part-xxx 格 式 命 名 的 文 件 合 并 成 一 个 单 一 的 文 件 进 行 评 测 输 出 文 件 / 文 件 夹 路 径 由 hdfs://< 匹 配 结 果 输 出 文 件 路 径 > 命 令 行 参 数 指 定 程 序 运 行 开 始 之 前, 这 个 路 径 并 不 存 在, 请 选 手 自 行 创 建 在 评 测 时, 评 测 系 统 会 为 选 手 提 供 一 个 临 时 的 HDFS 工 作 目 录, 该 目 录 路 径 由 命 令 行 参 数 hdfs://< 临 时 工 作 目 录 路 径 > 给 出 选 手 的 程 序 可 以 假 设 该 文 件 夹 路 径 已 经 存 在, 而 且 在 最 开 始 时 是 一 个 空 文 件 夹 选 手 的 程 序 可 以 在 该 文 件 夹 内 读 写 任 意 的 文 件 该 文 件 夹 主 要 供 选 手 保 存 处 理 中 间 结 果 禁 止 对 输 入 数 据 集 文 件 所 在 的 文 件 夹 进 行 写 入 操 作 禁 止 读 取 写 入 命 令 行 参 数 指 定 的 HDFS 路 径 之 外 的 其 他 HDFS 文 件 如 果 读 写 命 令 行 参 数 中 未 出 现 的 文 件 路 径 写 入 输 入 数 据 集 所 在 的 文 件 夹 自 行 读 写 本 地 文 件 系 统 的 文 件, 将 可 能 导 致 程 序 异 常 退 出, 异 常 退 出 的 程 序 将 没 有 分 数 4 附 录 B 程 序 评 测 4.1 评 测 标 准 评 测 时 将 综 合 考 虑 程 序 的 正 确 性 能 够 处 理 的 数 据 集 规 模 和 程 序 的 运 行 速 度 正 确 性 部 分 将 结 合 选 手 答 案 的 召 回 率 和 准 确 率 综 合 给 分 8

4.2 评 测 软 件 环 境 本 题 目 测 评 时 将 会 运 行 在 Apache Spark-1.4.0,Hadoop-2.4.1,JDK-1.7, Scala-2.10.4 环 境 下, 请 选 手 使 用 Java 或 者 Scala 进 行 编 程 开 发 评 测 用 集 群 硬 件 配 置 : Workers 16 Cores 384 Memory per node 20GB CPU per node Intel(R) Xeon(R) E5-2620 v2 @ 2.10GHz 2 4.3 友 情 提 醒 1. 评 测 用 的 环 境 如 前 所 述, 请 注 意 Spark JDK 和 Scala 的 版 本 如 果 选 手 使 用 高 版 本 的 JDK, 请 在 编 译 程 序 时, 编 译 为 JDK-1.7 兼 容 的 格 式 评 测 将 使 用 Spark-1.4.0 版 本, 更 高 级 版 本 的 Spark API 将 不 会 被 支 持 2. 评 测 将 使 用 程 序 自 动 化 地 运 行 选 手 程 序 判 断 结 果, 因 此 请 务 必 遵 守 前 文 所 述 的 各 种 运 行 要 求 和 文 件 格 式 不 符 合 格 式 要 求 的 输 出 文 件, 可 能 导 致 评 测 失 败 3. 请 附 带 源 代 码 的 编 译 说 明 在 jar 包 无 法 运 行 的 情 况 下, 评 测 人 员 会 尝 试 从 源 代 码 重 新 编 译 运 行 4. 选 手 可 先 使 用 小 数 据 集 来 调 试 程 序 的 正 确 性, 再 用 大 数 据 集 进 行 性 能 调 优 评 测 时 会 综 合 考 虑 选 手 程 序 的 正 确 性 和 性 能 9