Wings: Efficient Online Multiple Graph Pattern Matching

实现了一个分布式系统，用于在线多图模式匹配。

采用有向无环图（DAG）来解决查询优化问题（许多查询图可能都有相同的查询子图，导致出现重复计算），从DAG中生成最优的查询计划。DAG中的节点是多个查询的子图模式。

采用渐进策略来进一步修剪DAG，用以评估查询路径的成本。

采用小批量的深度优先查询执行策略，来解决仍可能在匹配阶段才出现的重复匹配，导致产生大量中间结果，导致内存占用高。

这篇论文介绍了一个名为Wings的分布式系统，旨在解决在线多图模式匹配（online multi-GPM）问题。这个问题在需要对动态变化的图数据进行实时分析的应用程序中非常重要，例如在电子商务网站、社交网络公司和投资银行等领域。在线多GPM的挑战在于它需要快速响应以便于及时的业务决策。

提出的问题： 现有的图模式匹配（GPM）方法主要集中在两个方面：一是寻找单个查询模式，二是在静态图上寻找模式。然而，许多现代应用需要匹配多个查询模式，并且这些模式是在不断变化的图上进行匹配的。这就需要一个系统能够快速响应，以便及时做出业务决策。

解决方案： Wings系统通过一个查询规划器来优化查询计划，该规划器通过最大化多个查询之间的计算共享，并最小化中间匹配结果来实现高效的多GPM。此外，论文还设计了一个高效的查询执行器，具有内存占用控制和运行时冗余处理消除功能。

实现方法：

  • 查询规划器： 通过构建一个有向无环图（DAG），其中节点代表多个查询的子图模式，然后生成一个集成的最优查询计划，以实现查询间的计算共享并避免重复匹配。
  • 查询执行器： 采用minibatch深度优先查询执行策略，以限制内存占用，并动态识别和消除查询执行过程中的冗余处理。

具体实现：

  • DAG构建： 通过算法构建DAG，包括最大子图（MS）节点和最大公共子图（MCS）节点，以考虑不同的匹配顺序和计算共享。
  • 成本估计和DAG剪枝： 使用一种渐进策略，通过快速剪枝DAG来减少成本估计和计划优化的时间。
  • 最优计划近似： 使用近似算法来解决DAG上的定向斯坦纳树问题（DST），以找到最优查询计划。

实验部分： 实验部分通过与现有的系统（如TigerGraph和Timely Dataflow）进行比较，验证了Wings设计的有效性。实验在10台机器的集群上进行，使用了四个流行的数据图，包括LSBench、LiveJournal、Twitter和WebUK。实验评估了Wings的查询计划优化方法的有效性、查询执行的效率，并与其他基线进行了比较。

对比： Wings与现有的单查询GPM优化算法（如SymBi）和多查询处理方法（如TRIC）进行了比较。实验结果表明，Wings在查询计划优化和查询执行方面都优于现有方法。

Time-Constrained Continuous Subgraph Matching Using Temporal Information for Filtering and Backtracking

提出了一种过滤技术和修剪技术，用于时间约束下的连续子图匹配。（即在时间数据图上找到与时间查询图同构且满足时间查询图顺序的所有匹配）。

这篇论文提出了一种新的算法，用于解决时间约束的连续子图匹配（time-constrained continuous subgraph matching）问题。这个问题在实时分析包含时序信息的图数据中非常重要，例如社交媒体流、问答网络和网络数据源等。算法的目标是在时间变化的数据图中，实时检测具有严格部分顺序模式的子图。

问题背景：

  • 现实世界中的图数据（如社交网络、金融交易网络）包含时序信息，称为时序图。
  • 时间约束的连续子图匹配问题旨在实时检测与查询图在拓扑结构和时间顺序上都同构的子图。

提出的方法：

  1. 时间约束可匹配边（TC-matchable edge）：这是一种过滤技术，利用时序信息在多项式空间内进行过滤。
  2. 时间约束剪枝（time-constrained pruning）：在回溯过程中，通过利用时序信息减少搜索空间，剪枝一些平行边。

具体实现：

  • 论文提出了一个基于上述两种技术的算法，称为TCM（Time-Constrained Continuous Subgraph Matching）。
  • 为了提高过滤效率，论文引入了一种名为max-min时间戳的数据结构，可以高效地确定边是否被时间约束可匹配边过滤，并能随着图的更新而更新。
  • 论文还开发了一套时间约束剪枝技术，通过考虑平行边之间的时间关系来减少回溯过程中的搜索空间。

实验部分：

  • 作者在真实和合成数据集上进行了广泛的实验，包括Netflow、Wiki-talk、Superuser、StackOverflow、Yahoo和LSBench。
  • 实验结果表明，TCM算法在查询处理时间上比现有最先进的算法快两个数量级。
  • 论文还比较了算法在不同查询大小、时间顺序密度和时间窗口大小下的性能。

对比分析：

  • 论文将TCM算法与现有的算法（如Timing和Hasse）进行了比较。
  • 通过实验数据，展示了TCM在不同场景下的性能优势，包括处理时间和内存使用。

未来研究方向：

  • 论文提出，未来的工作可以探索算法的并行化，以进一步提高处理大规模图数据的效率。

总的来说，这篇论文针对实时图数据分析中的时间约束子图匹配问题，提出了一种新的高效算法，并通过实验验证了其优越的性能。论文还指出了未来可能的研究方向，包括算法的并行化。

Search to Fine-tune Pre-trained Graph Neural Networks for Graph-level Tasks

提出内容： 这篇论文提出了S2PGNN框架，旨在自动化搜索适合给定预训练图神经网络（GNNs）和下游图数据集的微调策略。

解决的问题： S2PGNN旨在解决预训练GNNs在下游任务中微调策略设计不足的问题，尤其是现有方法要么假设过强，要么忽视了不同下游数据集的数据感知需求。

采用的方法： S2PGNN通过定义一个新颖的微调策略搜索空间，并集成了一个高效的搜索算法来探索最佳微调策略。该算法结合了参数共享和连续松弛技术，并通过可微分优化解决问题。

具体实现： 具体实现涉及构建一个双级优化问题，外层优化寻找最佳微调策略，内层优化在给定策略下训练模型参数。搜索空间包括多个设计维度，如背骨卷积、身份增强、多尺度融合和图级读出。通过梯度下降方法优化一个参数化的控制器来指导搜索过程。

实验设计： 实验在多个图分类和图回归数据集上进行，验证了S2PGNN在不同预训练GNNs上的有效性。实验结果表明，S2PGNN能够一致性地提高预训练GNNs的性能。

对比方法： S2PGNN与传统的微调方法（如Vanilla Fine-Tuning）以及其他领域的先进微调策略（如Feature Extractor、Last-k Tuning和Adapter-Tuning）进行了对比，证明了其在图级任务上的优越性。

未来研究方向： 论文建议未来的研究可以探索如何开发更稳健和可迁移的预训练GNNs，以便更容易地适应各种下游图场景。此外，结合其他先进的正则化方法来进一步提升S2PGNN的性能也是一个潜在的研究方向。

Reducing Resource Usage for Continuous Model Updating and Predictive Query Answering in Graph Streams

问题背景： 图流数据（Graph Streams）是一类动态变化的图数据，它们在许多领域如医疗、社交网络、金融等领域有广泛应用。动态图神经网络（DGNN）是处理这类数据的强大工具，但它们在连续预测查询和模型更新时面临着显著的训练时间和内存成本。

研究目标： 论文的主要目标是减少在图流数据上进行连续模型更新所需的计算资源，同时保持预测查询的准确性。

方法论：

  1. 在线学习算法： 作者提出了一种随机在线算法，该算法同时学习节点的权重分布，并基于这个分布进行加权在线训练。这种方法可以根据数据和工作负载自适应地选择哪些节点更有利于训练。
  2. 图核密度估计（Graph KDE）： 为了平滑权重分布并提高学习质量，作者设计了一种新颖的图KDE技术。这种技术基于随机游走核，考虑了网络拓扑结构，并且是针对离散分布的。

具体实现：

  • 节点级别的训练划分： 论文提出了一种节点级别的增量训练工作划分方案，每个节点都有自己的训练分区。
  • 随机算法： 通过采样节点并执行这些节点的训练分区来学习节点权重分布。算法使用马尔可夫链理论来证明其收敛性。
  • 图KDE采样： 通过随机游走和种子节点集来实现从平滑的节点权重分布中采样。

实验设计： 作者使用三个真实世界的图流数据集（MIMIC-III医疗数据、Bitcoin交易网络和Reddit社区网络）进行实验。实验对比了标准DGNN模型和提出的在线学习算法（带和不带图KDE增强）的性能。实验评估了训练时间、内存消耗和预测准确性。

对比结果： 实验结果表明，与标准DGNN模型相比，提出的在线学习算法在保持相同准确性的同时，训练时间缩短了几个数量级，内存消耗也减少了数倍到20倍。图KDE增强的版本进一步提高了效率。

NewSP: A New Search Process for Continuous Subgraph Matching over Dynamic Graphs

这篇论文提出了一个名为 NewSP 的新型搜索过程，旨在解决动态图中连续子图匹配（Continuous Subgraph Matching, CSM）问题中的不必要计算问题。这些问题主要是由于在搜索空间的过早扩展所导致的。NewSP 通过在操作级别推迟不必要的扩展，避免了过早扩展，同时保持了匹配顺序的初始剪枝能力。

问题背景： 在动态图中进行连续子图匹配时，传统的 CSM 框架会过早地扩展搜索空间，导致不必要的计算。这主要是因为这些框架在匹配顺序上严格对齐，导致在没有邻居的查询顶点上进行了不必要的扩展。

NewSP 方法： NewSP 通过以下方式实现：

  1. 操作级别的延迟扩展：NewSP 保持所有兼容集计算（CPTs）在原始位置上，并将每个过早的扩展（EXPs）推迟到其必要性出现之前。这避免了过早扩展，同时保留了匹配顺序的剪枝能力。
  2. 多重扩展策略：NewSP 允许连续的扩展，这在对应的查询顶点形成独立集时特别有用。这种策略可以显著减少可能出现的指数级增长的冗余计算。
  3. 兼容集重用：由于兼容集可能不会立即扩展，这提供了重用缓存兼容集的机会，从而节省了计算资源。
  4. 自适应索引过滤策略：该策略与具体的索引设计无关，可以与多重扩展和兼容集重用相结合，进一步提高性能。

实验部分： 作者在多个真实世界的数据集上进行了广泛的实验，包括 Amazon、LiveJournal、LSBench 和 NetFlow。实验结果表明，NewSP 方法比传统算法提高了两到三个数量级。此外，作者还进行了案例研究，将 NewSP 集成到现有的动态和静态图匹配方法中，证明了其优越性。

对比方法： NewSP 与现有的多种状态最先进的方法进行了比较，包括 CaLiG、RapidFlow、GraphFlow、TurboFlux 和 Symbi。在插入和删除效率、空间效率以及索引构建时间等方面，NewSP 都展现出了优越的性能。

LearnSC: An Efficient and Unified Learning-based Framework for Subgraph Counting Problem

这篇论文提出了一个名为LearnSC的高效且统一的基于深度学习的框架，用于解决子图计数问题。子图计数问题在许多应用中都非常重要，如社交网络分析、化学反应模拟等，但它是一个众所周知的难题，因为其核心子程序——子图匹配——是NP完全的。

问题背景： 子图计数问题涉及在数据图中为给定的查询图查找匹配的子图数量。这个问题在数据库系统中是一个基础组件，用于估计复杂连接的成本效益查询计划，同时也有助于通过不同大小和标签的查询图集来理解数据图。

提出方法——LearnSC： LearnSC框架通过五个阶段来解决子图计数问题：分解、表示、交互、估计和聚合。这个框架的关键优势在于它是一个通用解决方案，与现有的基于学习的方法正交，并且它配备了一系列优化措施来显著提高估计结果的准确性。

具体实现：

  1. 分解阶段：LearnSC从数据图中提取子结构，并将查询分解为子图。
  2. 表示阶段：将数据子结构和查询子图中的节点嵌入到特征向量中。
  3. 交互阶段：通过考虑匹配信息，使查询图和数据图之间的节点表示对齐。
  4. 估计阶段：将对齐的节点表示输入到深度学习模型中，以估计子图的数量。
  5. 聚合阶段：将子查询和子结构的估计结果聚合，得出原始查询图的最终计数。

实验部分： 实验在7个真实世界的数据集上进行，包括社交网络、化学反应和知识图谱等。实验结果表明，LearnSC在准确性、鲁棒性和可扩展性方面都优于现有的基于统计和基于学习的竞争方法。

对比方法： LearnSC与四种基于学习的方法和五种基于统计的方法进行了比较。这些方法包括NSIC、LSS、NeurSC、DMPNN以及Alley、Wander Join、Correlated Sampling、Join Sampling with Upper Bounds和Characteristic Sets等。

未来研究方向： 论文最后提出，未来的研究可以开发新的技术来进一步提高LearnSC每个阶段的估计质量，例如在交互阶段区分节点标签和节点拓扑的影响。这表明LearnSC框架是通用的，可以容纳新的技术来进一步提升性能。

Large Subgraph Matching: A Comprehensive and Efficient Approach for Heterogeneous Graphs

这篇论文提出了一种名为CSCE（Clustered Compressed Sparse Rows和Sequential Candidate Equivalence）的综合且高效的方法，用于在异构图上进行大子图匹配。子图匹配问题是图分析中的一个重要任务，涉及在图G中识别给定模式P的所有实例。现有的方法在处理大规模、多样化的图类型和子图匹配任务时往往效率不高。为了解决这个问题，CSCE方法能够为不同的问题设置生成高效的计划。

提出的问题：

  • 如何在异构图中有效地匹配大型模式，尤其是在处理大规模和多样化的图类型时。

采用的方法：

  • **Clustered Compressed Sparse Rows (CCSR)**：这是一种新颖的数据结构，用于存储和索引异构图中的边。通过将数据图中的边进行聚类，并存储为CCSR，可以有效地检索候选匹配。
  • **Sequential Candidate Equivalence (SCE)**：这是一个用于减少冗余计算的概念，通过识别模式顶点之间的条件独立性，来重用候选集，避免重复匹配。

具体实现：

  • CSCE首先对数据图G进行聚类，将同构的边分组到同一个簇中，并构建CCSR索引。
  • 对于给定的子图匹配任务，CSCE选择性地检索聚类并优化匹配计划，通过Greatest-Constraint-First (GCF)启发式算法快速剪枝候选集，并利用SCE来识别和重用候选集。
  • CSCE还提出了LargestDescendant-Size-First (LDSF)启发式算法来进一步优化匹配计划，以最大化候选集的重用。

实验部分：

  • 作者在多个真实世界的大型数据图上进行了广泛的实验，包括蛋白质相互作用网络、引文网络、社交网络等。
  • 实验结果表明，CSCE在处理大规模图时比现有技术快两个数量级。
  • 论文还对比了CSCE与现有方法在不同子图匹配变体（边诱导、顶点诱导和同构）上的性能。

对比方法：

  • 作者选择了支持不同子图匹配变体和图类型的最新算法作为基线进行比较，包括GraphPi、GraphFlow、GuP、RapidMatch、VEQ和VF3等。
  • 通过测量总时间成本和峰值内存消耗来评估性能，并设置了时间限制和内存限制来确保实验的可比性。

未来研究方向：

  • 论文提出了未来可能的研究方向，包括减少CCSR的开销，以及将CSCE应用于使用不同启发式算法改进匹配顺序的方法。

IVE: Accelerating Enumeration-based Subgraph Matching via Exploring Isolated Vertices

这篇论文提出了一种名为IVE（Isolated Vertices Exploration）的新型子图匹配算法，旨在加速基于枚举的子图匹配过程。子图匹配是图数据库中的一项基本任务，它在多个领域如化学信息学、社交网络分析等有着广泛的应用。然而，传统的基于枚举的子图匹配方法在查询图的顶点数量增加时，其性能会呈指数级下降，这是因为其时间复杂度与查询图中的顶点数成指数关系。

问题： IVE算法旨在解决的问题是提高基于枚举的子图匹配算法的性能，尤其是在处理大型查询图时的性能问题。

方法： IVE算法通过在重排序和枚举阶段利用孤立顶点来加速子图匹配过程。孤立顶点是指在查询图中不与其他顶点相连的顶点。算法的核心思想是在重排序阶段通过最大化孤立顶点的数量来减少需要枚举的非孤立顶点的数量，从而降低匹配过程的时间复杂度。

实现： IVE算法包括两个主要阶段：

  1. 重排序阶段：开发了一种名为MDE（Maximum Deleted Edges）的重排序算法，目标是最小化非孤立顶点的数量。MDE算法通过迭代选择具有最多边的查询顶点来实现这一点。
  2. 枚举阶段：在这个阶段，IVE算法排除了孤立顶点，只枚举非孤立顶点。通过构建一个二分图，IVE算法可以使用二分图匹配算法在多项式时间内计算孤立顶点的匹配。

实验： 实验部分，作者在多个真实世界的数据集上评估了IVE算法的性能，包括不同规模、稀疏性和领域的图。实验结果表明，IVE算法在各种场景下都优于现有的最先进算法，如Sun’s算法、RapidMatch和BICE等。实验使用了两个指标来评估性能：未解决的查询实例数量和总执行时间。

对比： IVE算法与现有算法的对比主要体现在处理复杂查询图的能力上。实验结果表明，IVE算法在所有数据集上的未解决查询实例数量最少，且总执行时间最短。此外，IVE算法在处理不同密度和大小的查询图时都表现出色。

Graph Condensation for Inductive Node Representation Learning

这篇论文提出了一种名为映射感知图凝缩（Mapping-aware Graph Condensation，简称 MCond）的方法，旨在解决图神经网络（Graph Neural Networks，简称 GNNs）在处理大规模图数据时面临的显著计算挑战。这些挑战严重限制了 GNNs 在多种应用中的有效性。为了克服这一问题，作者提出了 MCond，它通过显式学习从原始节点到合成节点的一对多节点映射，将新节点无缝集成到合成图中，以实现归纳表示学习。这使得直接在合成图上进行信息传播，比在原始大型图上更高效。

问题背景： GNNs 在处理大规模图时面临计算瓶颈，因为它们通常需要对整个图进行卷积操作，这导致时间和空间消耗与节点数量成二次方和线性关系。现有的图凝缩（Graph Condensation，简称 GC）方法主要集中在训练阶段的效率，而对推理/部署阶段，特别是在存在归纳节点时的关注不足。

方法介绍： MCond 通过交替优化方案和从传导和归纳角度创新的损失项，促进了图凝缩和节点映射学习的相互促进。具体来说，MCond 学习一个稀疏的映射矩阵，将每个原始节点视为一些合成节点的加权集合，并通过查找其在完整图中的邻居及其映射到合成节点的对应关系，为归纳节点与合成图之间建立加权边。

实现细节：

  • 标签基于梯度匹配（Learning S）：通过梯度对齐来学习合成图 S，使得在原始图和合成图上训练的 GNN 表现出相似的学习轨迹。
  • 拓扑保持图凝缩（Learning S）：提出了一种新的基于结构的优化目标，以保留原始图中的信息，并将其作为监督信号引入合成图。
  • 传导映射约束（Learning M）：通过传导约束来学习映射矩阵 M，使得每个原始节点可以通过对应的合成节点来表示。
  • 归纳映射约束（Learning M）：通过归纳约束来准备 M，使其能够合理地连接归纳节点和合成图，以便直接从合成图 S 进行信息传播。

实验设计： 作者在三个真实世界的数据集上评估了 MCond，包括一个引用网络（Pubmed）、一个图像网络（Flickr）和一个社交网络（Reddit）。实验设计了两种场景：节点批量（node batch）和图批量（graph batch），以评估 MCond 在不同设置下的性能。此外，还考虑了四种评估设置，包括在原始图和合成图上训练和推理。

对比分析： MCond 与其他图简化方法（如随机选择、度选择、Herding、K-Center 和虚拟节点图）进行了比较。实验结果表明，MCond 在保持高精度的同时，显著提高了推理速度和减少了存储需求。

未来研究方向： 尽管 MCond 能够与图凝缩方法集成，但其性能受到图凝缩结果质量的显著影响。因此，未来的工作方向可以探索增强图凝缩对大规模数据集变化的鲁棒性的策略。

Fast Query Answering by Labeling Index on Uncertain Graphs

这篇论文提出了一种基于索引的方法，用于在不确定图（Uncertain Graphs, UGs）上快速回答查询。不确定图是一种图模型，其中每条边的存在都与特定的概率相关联。这种图在社交网络分析、生物信息学等领域有广泛应用。在这些应用中，查询处理是一个基础且关键的任务，但现有的方法（如蒙特卡洛采样和启发式方法）在效率和准确性之间存在显著的权衡，或者缺乏对不同图和查询的泛化能力。

提出的问题：

  • 如何在不确定图上高效且准确地回答查询，包括可靠性查询（两个节点是否连接）、期望可靠距离查询（所有连接路径的加权平均长度）和距离约束的可靠性查询（两个节点在d跳内连接的概率）。

采用的方法：

  • 论文提出了一种新颖的基于索引的方法，称为UR-index，通过预计算和存储操作符来构建标签索引框架，从而加速查询回答过程。

具体实现：

  • 通过构建一个标签索引框架，将耗时的采样过程转化为离线索引操作计算，使得查询回答只需要遍历有限数量的操作符，从而显著加快响应时间。
  • 利用顶点覆盖及其h-hop扩展来剪枝索引结构，减少空间复杂度。
  • 论文还提出了VecUR-index和HoVecUR-index，基于顶点覆盖和h-hop顶点覆盖的索引结构，以进一步优化效率和准确性之间的权衡。

实验部分：

  • 论文在五个真实世界的数据集上进行了实验，包括LastFM、NetHEPT、Epinions、Notre Dame和Google。
  • 实验结果表明，所提出的索引框架在效率上优于现有的不确定图查询方法，并且随着图规模的增长，改进效果更加明显。

对比方法：

  • 论文将提出的索引方法与现有的三种基于启发式采样的方法进行了对比，包括Lazy Propagation Sampling (LPS)、Basic Stratified Sampling (BSS)和Recursive Stratified Sampling (RSS)。
  • 通过比较平均查询时间、相对误差、绝对误差和均方误差等指标，展示了索引方法在查询效率和准确性上的优势。

未来研究方向：

  • 尽管索引方法提供了高效率的查询，但构建索引的计算成本仍然很高，因此需要设计更有效的剪枝技术。
  • 考虑到大型动态不确定图，即图拓扑变化时，索引应如何调整，是另一个有趣的研究方向。
  • 论文还提到了在资源充足的情况下，可以通过增加索引构建时的样本大小来提高准确性。

Fair Top-k Query on Alpha-Fairness

这篇论文提出了一种名为α-fairness的公平性模型，旨在解决传统top-k查询中可能存在的歧视问题，尤其是在涉及少数群体（如女性和少数族裔）的决策场景中。论文的主要贡献和内容可以总结如下：

提出了什么：

  • α-fairness模型：一个量化top-k结果集公平性的新模型。
  • FairTQ-Exact算法：一个精确的框架，用于找到具有最小修改惩罚的公平效用函数。
  • FairTQ-Exact-BnB算法：一个基于分支定界法的快速算法，用于提高FairTQ-Exact的效率。

为了解决什么问题：

  • 传统的top-k查询可能因为设计不当的效用函数而导致对某些群体的歧视。α-fairness模型旨在量化效用函数的公平性，并找到既公平又接近用户原始偏好的效用函数。

采用了什么方法来实现：

  • 设计了α-fairness模型来量化效用函数的公平性。
  • 提出了FairTQ-Exact算法，通过枚举所有可能的top-k集合并计算它们的α-fairness，找到具有最大α-fairness的效用函数。
  • 提出了FairTQ-Exact-BnB算法，利用α-fairness的上界来剪枝搜索空间，减少需要处理的top-k集合数量。

具体怎么实现的：

  • FairTQ-Exact算法通过超平面方法枚举所有可行的top-k集合，计算它们的α-fairness，并使用二次规划找到具有最小修改惩罚的效用函数。
  • FairTQ-Exact-BnB算法在FairTQ-Exact的基础上，通过计算less-than和greater-than区域的α-fairness上界，使用分支定界法来减少需要枚举的区域。

实验怎么做的：

  • 在合成数据集和真实数据集上进行了广泛的实验，包括XING、COMPAS、DOT等。
  • 评估了算法的有效性（α-fairness）和效率（响应时间）。
  • 分析了不同参数（如α、p、k、数据集大小）对算法性能的影响。

怎么对比的：

  • 与现有的公平性排名算法（如SR-Adapt、Greedy、Prop、FA*IR）进行了比较。
  • 展示了在不同数据集规模和维度下，提出的算法与其他基线算法在响应时间和公平性上的性能差异。

未来的研究方向：

  • 将公平性问题扩展到其他场景，例如考虑元组之间的相对排名。
  • 探索其他公平性度量方法，如KL散度的变体，以处理未知的受保护群体。

论文还提到了实验结果证明了所提出算法的有效性和效率，并在真实和合成数据集上展示了这些算法的性能。

Efficient Set-based Order Dependency Discovery with a Level-wise Hybrid Strategy

这篇论文提出了一种高效的基于集合的顺序依赖（Order Dependencies, ODs）发现方法，称为HyOD，以及其多线程并行版本HyOD+。这些方法旨在解决数据库查询优化中的排序操作问题，通过自动从数据中发现隐藏的顺序依赖关系。顺序依赖关系描述了属性之间的排序规范，对于优化数据库查询中的排序操作非常有效。

问题背景： 在数据库查询中，经常需要根据某些属性的顺序来排序数据。这些顺序依赖关系（ODs）可以用于查询优化，以减少查询执行所需的时间和资源。然而，手动设计这些依赖关系既昂贵又不可行，因此需要自动化的方法来发现这些依赖关系。

方法介绍： HyOD方法采用了一种新颖的层次混合策略，结合了样本数据上的依赖发现和整个实例上的依赖验证。这个过程是逐层进行的，直到在样本上的发现结果收敛到整个实例上的结果。HyOD方法还引入了动态样本大小的概念，可以在不影响发现结果的正确性和完整性的情况下，根据需要增量地细化样本。此外，HyOD方法还通过多线程并行处理来提高效率。

具体实现： HyOD方法的核心是层次混合策略，它在不同层次上交替进行样本数据上的OD发现和整个数据集上的OD验证。这种方法可以确保在样本上发现的ODs在整体数据集上也是有效的。HyOD方法还包括了一些优化技术，例如在验证过程中选择违反OD的元组对来细化样本，以及多线程并行处理来加速OD验证过程。

实验设计： 作者使用了一系列真实和合成的数据集来评估HyOD方法。实验结果与现有的最先进方法FastOD进行了比较，包括运行时间、可扩展性和内存效率。实验还研究了不同的参数设置，如初始样本大小和用于细化样本的违反元组对的数量。

对比结果： 实验结果表明，HyOD方法在所有测试的数据集上都显著优于FastOD，运行时间快达两个数量级。HyOD+通过多线程并行处理进一步提高了效率，平均加速比为2.7倍，最高可达4.5倍。此外，HyOD方法在内存使用上也更为高效，FastOD在某些数据集上因内存不足而失败。

未来研究方向： 论文最后提出了未来的研究方向，包括将HyOD方法与用户交互结合起来，以满足不同用户应用的需求。例如，可以开发工具来帮助用户从发现的ODs中选择有意义或相关的依赖关系，以用于查询优化、数据清洗或完整性维护等任务。此外，作者还计划探索HyOD方法在其他类型的数据依赖发现任务中的应用

Efficient Multi-query Oriented Continuous Subgraph Matching

论文主要关注于动态图中的多查询连续子图匹配（MQCSM）问题，这是一个在诸如信用卡欺诈检测、网络攻击追踪和谣言检测等领域具有广泛应用的重要任务。现有的连续子图匹配（CSM）算法主要针对单一查询进行设计，但在实际应用中，往往需要同时处理多个查询，这就要求算法能够高效地处理多查询的情况。

提出的问题：

论文指出，尽管已有一些MQCSM的解决方案，但它们由于性能不佳而变得过时。因此，作者提出了一个新的问题：如何在动态图中高效地处理面向多个查询的连续子图匹配问题。

采用的方法：

为了解决这个问题，作者提出了一个名为MQ-Match的新方法。MQ-Match包括两个主要部分：

  1. 候选分类图（CCG）：这是一个紧凑而有效的索引结构，用于维护数据图中顶点的局部匹配结果。
  2. 增量匹配算法：该算法基于查询图的深度优先搜索树构建一组匹配树，并通过利用CCG来收集查询图的增量匹配，确保查询图中的公共结构只被匹配一次。

具体实现：

  • CCG的构建：CCG是一个有向图，其顶点与数据图相同，有向边表示一个顶点至少出现在一个查询图的部分匹配中。CCG的构建包括确定数据图中顶点的状态，这涉及到构建邻域匹配图（NMG）和设置顶点状态。
  • 匹配树的构建：匹配树是基于查询图的深度优先搜索树构建的，每个匹配树对应于查询图中的一个唯一匹配边。匹配树的构建采用了一种贪婪算法，选择未访问顶点中具有最多匹配顶点的标签来扩展匹配树。
  • 基于CCG的匹配树搜索：当数据图发生更新时，算法会找到与更新边对应的匹配树，并在这个匹配树上执行回溯搜索，以收集所有增量匹配。

实验部分：

作者在六个真实数据集上进行了广泛的实验，包括Facebook、Slashdot、Wikipedia、Netflow、Youtube和Twitch。实验评估了MQ-Match在离线阶段（索引构建时间和内存使用）和在线阶段（查询时间，包括索引更新和增量匹配搜索时间）的性能。实验结果表明，MQ-Match在大多数设置下比现有解决方案更快，消耗的内存更少。

对比部分：

MQ-Match与多个现有算法进行了对比，包括IncMQO、TRIC+、CaLiG、RapidFlow、Symbi和Graphflow。对比结果显示，MQ-Match在索引构建时间和在线查询处理方面都优于这些算法。

Efficient Learning-based Top-k Representative Similar Subtrajectory Query

论文主要研究了在大量轨迹数据集中，如何高效地查询与给定查询轨迹最相似的前k个代表性子轨迹（subtrajectories）的问题。

提出的问题： 随着位置技术的发展和轨迹数据的增加，轨迹数据挖掘成为时空数据分析领域的焦点。与以往研究集中在整个轨迹的相似性不同，本文关注在大量轨迹集合中的子轨迹相似性，并提出了一个名为Top-k Representative Similar Subtrajectory Query（TRSSQ）的问题。目的是在大型轨迹数据集中识别与查询轨迹最相似的前k个子轨迹。

解决的问题： 在大规模轨迹数据库中，直接检索相似子轨迹可能会引入冗余，且计算成本高。本文旨在解决如何在保证结果多样性的同时，高效地检索出最具代表性的相似子轨迹。

采用的方法： 为了解决这一挑战，作者提出了一个基于学习的框架，并利用了一个深度学习模型，称为Representative Similarity Score Estimation（RSSE），来高效地近似子轨迹相似度得分，并显著减少候选集。

具体实现：

  • RSSE模型：该模型能够估计数据轨迹与查询轨迹之间所有可能子轨迹的最高相似度得分，而无需计算数据轨迹中每个单独子轨迹的相似度得分。
  • 过滤和验证范式：使用RSSE预测查询轨迹与数据库中所有轨迹之间的代表性相似度得分。在验证阶段，通过计算候选轨迹中代表性相似子轨迹的相似度得分来得出最终的前k个结果。

实验部分： 作者在多个真实世界的数据集上进行了实验评估，包括西安、成都和波尔图的出租车轨迹数据集。实验从两个方面进行评估：1) RSSE和其他基于学习的模型在准确预测前k个代表性相似度得分方面的性能；2) 通过学习基础过滤器和其他过滤方法获得的前k个代表性相似子轨迹的质量。

对比部分： 实验中，作者将RSSE模型与其他几种基线方法进行了比较，包括SRN、T3S和TMN等。此外，还比较了不同的过滤方法，如OSF、Grid Filter和LBF（Learning-Based Filter）。通过一系列的实验，作者证明了RSSE在预测代表性相似度得分方面的有效性和效率，并展示了所提出方法在大规模数据环境中的潜在应用性。

这篇论文研究了交互式图搜索（Interactive Graph Search, IGS）问题。在这个问题中，给定一个查询实体φ，目标是在有向无环图（DAG）概念层次结构H中找到最能描述φ的目标概念，通过与一个oracle（即知识源）的交互来实现。每次交互都是以“φ是否属于概念u？”的形式提问，oracle的回答只能是YES或NO。IGS算法的效率是通过识别目标概念所需提问的数量，即查询成本来衡量的。

提出的问题：

  • 如何在DAG概念层次结构中高效地识别查询实体的目标概念。

采用的方法：

  • 论文提出了两种算法：Target-Sensitive IGS (TS-IGS) 和 Example-Guided IGS (EG-IGS)。

具体实现：

  1. TS-IGS算法：这是一个理论上的改进算法，它在DFS heavy-path tree上运行，通过结果敏感的二分搜索（result-sensitive binary search）来找到最深的YES-concept，从而提高了搜索效率。TS-IGS的查询成本复杂度为O(log n · log L / log n + d · logd n)，其中L是从树根到目标概念的路径长度。
  2. EG-IGS算法：这是一个实际应用中的算法，它利用了实体的知识，通过类似φ的示例引导提问。EG-IGS算法的工作流程包括：
    • 收集与φ类似的示例集E。
    • 从E中导出有希望的问题（或概念）集Q。
    • 识别Q中最深的YES-concept t。
    • 在t根的子树上调用TS-IGS算法来识别目标概念。

实验：

  • 论文在六个真实世界的数据集上进行了广泛的实验，包括图像、文本和基因序列。
  • 实验结果显示EG-IGS在查询成本上优于所有现有竞争对手，最多提高了两个数量级。
  • 为了进一步展示EG-IGS技术的真正可行性，作者还开发了一个全自动的亚马逊产品分类演示系统，使用GPT-3.5作为oracle。

对比：

  • 论文将提出的算法与现有的几种算法进行了比较，包括IGS、BinG、STBIS和MIGS。
  • 通过对比平均查询成本，展示了EG-IGS在不同数据集上的性能优势。

未来研究方向：

  • 论文提出了几个未来研究方向，包括处理多目标问题、探索更强大的oracle定义以及研究独立噪声oracle设置，其中oracle对每个问题的答复正确的概率为某个大于1/2的常数p。

总的来说，这篇论文在理论和实践上都对IGS问题进行了深入研究，并提出了一种新的高效算法EG-IGS，通过实验验证了其在不同数据集上的有效性。同时，论文还探讨了如何将这种技术应用于实际的自动化分类系统，并指出了未来研究的可能方向。

CSM-TopK: Continuous Subgraph Matching with TopK Density Constraints

这篇论文提出了一个名为CSM-TopK的新型问题，即在动态加权图中持续计算给定查询图的k个最高密度的子图匹配。这个问题是为了解决在动态图中进行子图匹配时，现有方法返回的匹配结果数量可能非常庞大，给分析人员带来压力，并且没有考虑到加权图的情况。在许多现实世界的应用中，如支付网络，图中的边权重代表了交易金额，因此匹配的子图可能具有不同的分析优先级。

为了解决的问题：

  • 现有连续子图匹配（CSM）方法返回的匹配结果数量可能过多，难以处理。
  • 现有方法没有考虑加权图，忽略了图中边的权重信息。
  • 在加权图上，需要一种机制来帮助分析人员快速识别高优先级的匹配子图。

采用的方法：

  • 论文提出了一种新的CSM-TopK问题，通过定义星形子查询（star-structured subquery），设计了两种轻量级索引：全局MWstar和局部MWstar。
  • 引入了基于查询的图压缩技术，以提高时间和空间性能。

具体实现方式：

  • 定义了星形子查询和基于此的全局MWstar索引，维护每个特定星形子查询的所有部分匹配的最大权重。
  • 设计了局部MWstar索引，基于对应数据顶点的最大权重分布。
  • 提出了一种基于查询的图压缩技术，以减少搜索起点的数量，特别是在发生删除操作时。

实验部分：

  • 在真实世界的数据集上进行了广泛的实验，包括Amazon、LiveJournal、Human和YouTube数据集。
  • 实验评估了插入和删除操作的效率，以及不同k值和查询大小对性能的影响。
  • 比较了不同方法在空间效率和索引构建时间上的表现。

对比方法：

  • 与现有的静态子图匹配方法（KiSD和PBSM）以及连续子图匹配方法（GraphFlow、RapidFlow和CaLiG）进行了比较。
  • 实验结果显示，论文提出的方法在更新时间和空间效率上都优于比较的方法。

未来研究方向：

  • 论文提到CSM-TopK可能会返回重叠的匹配结果，因此未来的工作可能会集中在如何在CSM-TopK的框架下返回多样化的匹配结果。
  • 可能会探索更高效的索引结构和搜索策略，以进一步优化CSM-TopK的计算性能。

A Critical Re-evaluation of Benchmark Datasets for (Deep) Learning-Based Matching Algorithms

论文主要关注实体解析（Entity Resolution, ER）领域中的基准数据集的质量，特别是这些数据集在评估基于（深度）学习的匹配算法时的适用性。

提出的问题： 实体解析是识别一个或多个数据库中指向同一实体的记录的过程。尽管已有多种技术被开发出来解决ER挑战，但现有文献中尚未对用于基于学习匹配算法实验评估的基准数据集的质量进行检验。论文指出，大多数流行的基准数据集过于简单，不适合评估基于学习匹配算法的性能。

采用的方法： 为了填补这一空白，作者提出了四种不同的方法来评估13个已建立的数据集的难度和适用性：

  1. 理论上的方法，包括新的线性度量和现有的复杂度度量。
  2. 实践上的方法，包括最佳非线性匹配器与线性匹配器之间的差异，以及最佳基于学习匹配器与完美预言者之间的差异。

具体实现：

  • 提出了新的理论度量方法，如线性度量，以及将现有的复杂度度量首次应用于ER基准。
  • 实现了一种新的方法，通过创建四个新的匹配任务来生成基准数据集，并验证这些新基准更具挑战性，因此更适合该领域的进一步发展。
  • 通过开源的非线性机器学习（ML）和深度学习（DL）匹配算法来评估这些度量，并与新提出的线性分类器进行比较，以估计非线性基于学习匹配算法的优势。

实验方法：

  • 对13个流行的ER基准数据集进行了系统评估，实验表明这些数据集大多过于简单，无法适当评估复杂匹配器（如基于DL的匹配器）的预期改进。
  • 提出了一种新的创建ER基准数据集的方法，并通过实验证明了这些新基准数据集更适合评估基于DL匹配器的优势。

对比方法：

  • 通过比较新旧基准数据集的难度和适用性，展示了新方法的有效性。
  • 使用了多种度量方法，包括理论上的线性度量和复杂度度量，以及实践上的非线性提升（NLB）和基于学习的差距（LBM）。

未来研究方向：

  • 论文提出，未来的研究可以探索不同的DeepBlocker配置或不同的阻断方法，以从简单的数据集中提取出具有挑战性的基准数据集。
  • 作者计划创建一系列涵盖整个基准难度范围的数据集，以促进ER领域的进一步发展。

总的来说，这篇论文对现有的ER基准数据集进行了批判性重新评估，并提出了一种新的方法来生成更适合评估基于深度学习的匹配算法的基准数据集。通过理论和实践的结合，作者为ER领域的研究提供了新的视角和工具。

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

分享文章

快来参与讨论吧~