结构保持式图约简框架

Structure⁃preserving graph reduction framework

摘要

以知识图谱、社交网络为代表的大规模图数据广泛存在，由于规模庞大，大图上的分析，如频繁模式挖掘等，面临严峻挑战.图约简技术可以在保留图中关键信息的同时大幅减小图的规模，因而成为大图分析的关键技术之一.然而，现有图约简技术致力于保留特定属性信息或最小化全局信息损失，忽略了对局部高阶结构的保护，导致其对频繁模式挖掘任务的支持不尽人意.为此，提出一种结构保持式图约简框架，在约简数据规模的同时，保留原图中更多的高质量频繁模式.首先，提出了一种从局部到全局的边重要性评估方法，通过对关键节点与核心边的精确识别，引导初始约简骨架的构建；其次，为弥补约简引发的结构损失，设计了一种基于邻域信息的骨架增强机制，提升约简图的结构多样性与完整性.在真实图上的广泛实验表明，该框架在多项指标上表现优异，且生成的约简图有效保留了原图的骨干结构，当约简率仅为0.1时，在Wiki数据集上\mathrm{t}\mathrm{o}\mathrm{p}\mathrm{⁃}k\left(k=\mathrm{800}\right)频繁模式的准确率可达96%.

Abstract

Large⁃scale graph data，such as knowledge graphs and social networks，are ubiquitous. The enormous size of these graphs poses significant challenges for analytical tasks like frequent pattern mining (FPM). Graph reduction techniques have emerged as a key enabler for large⁃scale graph analysis，as they can drastically reduce graph size while preserving critical information. However，existing graph reduction methods primarily focus on retaining specific attribute information or minimizing global information loss，often neglecting the preservation of local high⁃order structures. This limitation leads to suboptimal support for FPM tasks. To address this issue，we propose a Structure⁃Preserving Graph Reduction Framework (SPGRF) that retains a higher quantity of high⁃quality frequent patterns while reducing data scale. First，we introduce a local⁃to⁃global edge importance evaluation method that guides the construction of an initial reduction skeleton by precisely identifying key nodes and core edges. Second，to compensate for structural degradation caused by reduction，we design a neighborhood⁃based skeleton enhancement mechanism to improve the structural diversity and completeness of the reduced graph. Extensive experiments on real⁃world graphs demonstrate the superiority of our framework across multiple metrics. The generated reduced graphs effectively preserve the original "backbone" structure: when the graph is reduced to 10% of its original size \left(\mathrm{r}\mathrm{e}\mathrm{d}\mathrm{u}\mathrm{c}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{e}=\mathrm{0.1}\right),the accuracy of \mathrm{t}\mathrm{o}\mathrm{p}\mathrm{⁃}k\left(k=\mathrm{800}\right) frequent patterns on the Wiki dataset reaches 96%.

Graphical abstract

关键词

图约简 / 频繁模式挖掘 / 图卷积网络 / 约简骨架

Key words

graph reduction / frequent pattern mining / graph convolutional networks / reduced skeleton

当前，图数据已成为建模复杂系统（如社交网络、知识图谱等）的主要工具之一，通过频繁模式挖掘（Frequent Pattern Mining，FPM）在图数据上发现有价值的知识对于理解图数据的拓扑结构等至关重要.然而，单一大图上的FPM是一个极具挑战性的任务，其根本原因在于FPM是一个NP难问题^［1］，在大图上展开挖掘，算法往往面临着计算成本高昂、内存占用巨大的问题，甚至存在资源崩溃的风险.

近年来，图约简（Graph Reduction）技术成为应对大图分析的有效手段之一.图约简在保留图中关键信息的同时，能够大幅减小数据规模^［2］.然而，已有的约简方法主要侧重于保留图的特定属性（如谱性质^［3］、节点成对距离^［4］）或确保下游任务（如节点分类）在GNN （Graph Neural Network）等模型上的性能表现^［5］，没有充分考虑图本身丰富的结构信息.对于FPM这类对图拓扑结构高度敏感的任务，已有的约简方法往往会导致约简图中丢失大量重要模式，挖掘效果不及预期.鉴于此，本文提出了一种结构保持式图约简框架（Structure⁃Preserving Graph Reduction Framework，SPGRF），基于模式层次扩展原理，充分融合了图的属性信息与拓扑结构，极大程度上保留原图中的高频结构，为FPM任务提供有力支撑.

例1图1a是某社交网络图G，其中每个节点v代表一个用户，节点的颜色代表他们不同的职务，如数据库管理员（DBA）、程序员（PRG）、业务分析师（BA）、软件测试人员（ST）、项目经理（PM）；边e表示用户之间的联系.图中频繁出现与模式Q=\left\{\mathrm{D}\mathrm{B}\mathrm{A},\mathrm{P}\mathrm{R}\mathrm{G},\mathrm{B}\mathrm{A}\right\}同构的子图，如\left\{v_{\mathrm{2}},v_{\mathrm{3}},v_{\mathrm{4}}\right\}等，因此，在约简图中保留这些频繁出现的结构信息对于FPM至关重要.图1b~d分别展示了基于三种不同策略形成的约简图（灰色节点与边为约简结构）.图1b和图1c展示了仅基于拓扑结构^［6］和基于全局信息^［7］约简策略生成的约简图.这两种策略，前者对图的属性信息不敏感，只能尽可能地保留“枢纽”节点；后者只关注全局信息的损失最小，不能充分保留结构特征，导致频繁结构保留不足.相比之下，图1d展示的约简策略结合了G的结构和属性信息进行约简，所以约简图G_s有效保留了原图中重要的频繁模式.然而，生成G_s面临两个关键问题：（1）量化图中节点和边对于保留重要频繁模式的重要性，并据此生成约简图骨架；（2）对约简图骨架进行增强，弥补约简中导致的结构损失.

本文的具体贡献如下.

（1）提出一种结构保持式图约简框架（SPGRF），引入了一套从局部到全局的边重要性评估方法.首先，为边赋予基于局部信息的初始权重，再利用图卷积网络（Graph Convolutional Network，GCN）学习并推理出融合了高阶邻域信息的全局重要性评分.基于该评分，框架通过筛选重要节点并连接“高分值”边，构建出初始的约简骨架.整个约简过程在有效减小图数据规模的同时，保留了原图中更多的高质量频繁模式.

（2）设计了一种基于邻域信息的约简骨架增强机制，用于弥补约简导致的结构损失.该机制能准确鉴别直接连接（原图中已有的边）和间接连接（原图中没有的边），并在约简骨架中予以恢复，得到约简图.约简图有效提升了约简骨架的结构多样性和完整性，有助于保留原图中的重要频繁模式.

（3）在真实图数据集上进行的大量实验表明，在资源消耗可接受范围内，SPGRF在各项指标上表现优异.当约简率仅为0.1时，在Wiki数据集上\mathrm{t}\mathrm{o}\mathrm{p}\mathrm{⁃}k\left(k=\mathrm{800}\right)频繁模式挖掘结果的准确率可达96%.

1 相关工作

图约简作为图数据处理中一项关键技术，旨在在尽可能保留原图结构与语义信息的基础上，生成规模更小、计算更高效的近似图^［2］.当前主流方法大致分三类：图稀疏化、图粗化与图凝聚.

图稀疏化主要通过去除冗余边或节点，在保留原图结构性质的同时生成相似的小图.早期方法多以结构保真为目标，例如，Althöfer et al^［8］提出的Spanner算法采用一种贪心策略，在允许节点间距离被可控拉伸的前提下，以少量边保留原始图的近似距离结构，实现了有效的图稀疏化，奠定了稀疏图构建的理论基础.随后，研究焦点逐渐转向谱相似性保持，旨在在图拉普拉斯矩阵层面维持图的整体性质，代表性成果包括Feng^［9］提出的相似性感知构造框架，有效兼顾了理论保证与计算的可扩展性.近年来，GNN的快速发展推动了稀疏化从结构驱动向模型性能导向演化.Razin et al^［10］提出的WIS方法引入“步行指数”作为边重要性度量，移除对多步信息传播影响较小的边，提升GNN的效能.Zhao et al^［11］进一步将公平性纳入优化目标，实现模型准确性与群体公平性的协调.Zhang et al^［12］突破了统一稀疏率的约束，提出节点感知的个性化稀疏策略，更贴合异质图中个体差异的表示需求.随着图数据规模的增长，结构演化，动态图、高效计算以及可解释性成为最新研究热点.为了提升稀疏化的合理性，Akkas and Azad^［13］引入Shapley来评估边影响力，在保障GNN性能的同时，实现有效约简.针对动态演化场景，Shabani et al^［14］利用强化学习设计了STGS框架以保持关键时空模式.Yuan et al^［15］提出dyGRASS算法，借助GPU加速的局部随机游走实现了极高效的动态谱稀疏化.除了基于边评分的稀疏化方法，另一类通过子图采样获取代表性结构的策略也在大规模图处理中得到广泛应用.森林火灾采样（Forest Fire Sampling，FF）^［16］以模拟火势蔓延的方式递归选取邻接节点，适用于连通性强的图.钉球采样（Spikyball Sampling，SS）^［17］在广度优先搜索中仅激活少量邻居，可以缓解高密度区域的过采样问题.针对传统随机游走存在的收敛速度慢、探索效率低等问题，CNARW方法^［18］引入共同邻居信息对游走方向进行引导，以加速采样过程，提高探索多样性.此外，为了在采样中纳入更高阶结构，Wang et al^［19］在BMiner挖掘框架中提出基于Motif的节点采样策略，借助Motif模式重新定义节点重要性，融合结构特征与属性语义，在保持信息完整性的同时显著压缩图规模.

图粗化通过节点聚合与信息压缩，生成更简洁的图结构以提升表示与计算效率.传统粗化方法多以最小化结构重建误差为目标.Loukas and Vandergheynst^［20］提出的RSS框架首次为粗化过程提供了谱层面的形式化分析.Kumar et al^［7］进一步将节点特征纳入粗化过程，提出联合结构与属性优化的粗化策略，提升了特征一致性.针对传统粗化方法易产生稠密摘要图的局限，Lee et al^［21］提出的SSumM方法将节点合并与摘要图稀疏化两个过程相结合，在最小描述长度原则的指导下生成稀疏的摘要图.在GNN应用中，图粗化逐渐融入了模型训练流程.Huang et al^［22］提出的SCAL方法结合粗化与知识迁移策略，先在小图上进行训练再迁移至原图，显著提升了训练效率.Bacciu et al^［23］借鉴卷积神经网络设计，提出图下采样机制，解决了图数据缺乏规则结构的问题，拓展了GNN的层次化设计空间.

图凝聚技术进一步将约简提升至“可训练小图合成”层面，通过合成一个与原图结构无关的全新小图，强调在小图上尽可能重现原图的训练行为，其代价是牺牲了节点与边的直接可解释性.Jin et al^［24］提出的GCond框架率先引入知识蒸馏思想，以梯度匹配方式驱动小图训练过程与原图一致，开启了图凝聚研究序章.为了缓解其在大图场景下的效率瓶颈，Jin et al^［25］提出的DosCond，通过模型解耦与流程简化显著提升了可扩展性.Gao et al^［26］创新性地将凝聚图作为反馈机制，引导原图去噪与学习协同优化.考虑到单步蒸馏误差累积，Zheng et al^［27］进一步提出SFGC框架，引入“专家轨迹”引导小图模拟原图的长期训练动态，提升了模型的稳定性.Zhang et al^［28］与Liu et al^［29］分别从节点评分与结构可解释性的角度提出了新型蒸馏范式.为了规避高昂的双循环训练开销，Wang et al^［30］提出GC⁃SNTK框架，采用图正切核逼近原图行为来形成封闭解方案，大幅简化计算.后续如KiDD^［31］，OpenGC^［32］等方法，进一步扩展其在动态图与增量学习等复杂场景中的应用.

另一路线以分布匹配为核心，通过对齐特征分布来替代梯度监督.Xiao et al^［33］提出更简洁的对齐策略SimGC，Gao et al^［34］提出CGC，进一步摆脱了训练依赖，通过结构先验直接生成可用小图，极大地提升了图凝聚方法的效率与可落地性.

2 相关概念

定义1 图与子图^［19］ 一个图定义为三元组G=\left(V,E,L\right)，其中，V是节点集合；E是边集合；V中每个节点v携带L\left(v\right)，表示其标签或内容.图G^{\text{'}}=\left(V^{\text{'}},E^{\text{'}},L^{\text{'}}\right)是G=\left(V,E,L\right)的子图，其中，V^{\text{'}}\subseteq V，E^{\text{'}}\subseteq E，针对每个节点v\in V^{\text{'}}，都有L^{\text{'}}\left(v\right)=L\left(v\right).

定义2 模式和子模式^［35］ 一个模式Q定义为Q=\left(V_p,E_p,f_v\right)，其中，V_p是节点集合；E_p是边集合；对于每一个节点u\in V_p，f_v\left(u\right)被定义为“A=a”形式的原子公式的连接.A表示节点u的一个属性，a是属性A对应的值.

通过一次前向扩展（或后向扩展），得到模式Q^{\text{'}}=\left(V_p^{\text{'}},E_p^{\text{'}},f_v^{\text{'}}\right),其中，Q\subseteq Q^{\text{'}}.Q^{\text{'}}比Q多一条边和一个顶点（或只多一条边）.同时，模式Q称为父模式，模式Q^{\text{'}}是模式Q的一个子模式.

定义3 前向扩展和后向扩展^［35］ 给定模式Q，通过从其节点u对Q进行深度优先搜索来构建其DFS树T_q，称T_q中的边为前向边，Q中的其余边为后向边.因此，前向扩展通过引入一条从Q中的现有节点到新引入节点的新边来扩大Q，扩展出来的模式形如树状结构，被称为树模式.后向扩展从Q的两个现有节点引入新边，扩展出来的模式，其结构中包含回边，不再是树状结构，称为非树模式.

定义4 模式匹配^［19］ 给定图G=\left(V,E,L\right)和模式Q=\left(V_p,E_p,f_v\right).如果G中节点v满足Q中节点u的查询条件，即对每一个f_v\left(u\right)中的原子公式“A=a”，在L\left(v\right)中都有对应的属性A，使得v.A=a，则用“v~u”表示两者之间的匹配关系.

图G中模式Q的匹配是一个从Q到G的同构映射f，使得：（1）对于每个节点u\in V_p，u~f\left(u\right)；（2）对于模式中每条边\left(u,u^{\text{'}}\right)\in E_p，当且仅当\left(f\left(u\right),f\left(u^{\text{'}}\right)\right)\in E.当模式Q与G的子图G^{\text{'}}=\left(V^{\text{'}},E^{\text{'}},L^{\text{'}}\right)存在同构映射关系f时，G^{\text{'}}为Q在G中的一个匹配.

沿用上述“匹配”的语义，称v\in V^{\text{'}}是u\in V_p的匹配.通常模式Q在G中的匹配不止一个，本文使用M\left(Q,G\right)表示模式Q在图G中的所有匹配的集合，并用img\left(u\right)表示G中所有与节点u\in V_p匹配的节点.

定义5 支持度^［35］ 给定模式Q和图G，支持度表示模式Q在图G中对应匹配出现的频率，记为Sup\left(Q,G\right).基于图像的最小支持度MNI是一个广泛使用的度量标准^［36］，保证模式扩展的反单调性.MNI的定义如下所示：

Sup\left(Q,G\right)=\mathrm{m}\mathrm{i}\mathrm{n}\left\{\left|img\left(u\right)\right|,u\in V_p\right\}(1)

其中，img\left(u\right)表示模式中节点u在图G上的匹配去重后的节点集合.

定义6 图约简^［2］ 给定图G=\left(V,E,L\right)，图约简指构造一个规模更小的图G_s=\left(V_s,E_s,L_s\right)，使得G_s在结构与语义上仍然保留G的关键信息.本文采用节点约简率来量化图约简效果：

r=\frac{\left|V_s\right|}{\left|V\right|}(2)

其中，\left|V\right|是G的节点总数；\left|V_s\right|是G_s的节点总数.

给定节点v，称N_G\left(v\right)为v在图G中的邻居节点集合，deg\left(v\right)为v的度数，deg\_G\_avg为G中节点的平均度数.

表1列举了本文使用的符号及其含义.

3 结构保持式图约简

3.1　总体流程

SPGRF算法将图G约简为满足约简率的图G_s，使得G_s蕴含尽可能多原图中的频繁模式.详细流程如算法1所示.

算法1 SPGRF

输入：图G，约简率r，直接连边率d_r，相似度阈值\tau.

输出：约简图G_s.

1.initialize G_s；

2.G_w:=InitWeight\left(G\right)；

3.scores,Z:=EdgeImpModel\left(G_w\right)；

4.G_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}:=GetInitGraph\left(G_w,r,scores\right)；

5.G_s:=ConnectEdges\left(G,G_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}},scores,Z,d_r,\tau \right);

6.return G_s.

SPGRF接受图G、约简率r、直接连边率d_r和相似度阈值\tau作为输入.其中，直接连边率d_r决定每个节点在约简图中可保留多少原图中的直接邻居边，以调控约简图的稠密程度和结构信息保留程度.d_r越大，结构信息保留越多；d_r越小，可能导致丢失重要结构.相似度阈值\tau可衡量“替身”节点与其所代替的原节点之间相似性，以调控非直连边的数量.\tau越大，图结构更稀疏；\tau越小，可能提升结构多样性，但易引入噪声.

SPGRF算法包含四个阶段：权重初始化、边评分、骨架生成以及骨架增强.

（1）权重初始化（第1行和第2行）.SPGRF首先初始化一个空的约简图G_s.为了评价节点和边的重要性，SPGRF调用InitWeight函数（详见3.2）来完成权重初始化，即结合节点标签频率和单边模式支持度，为图G中的每个节点和每条边赋予一个先验权重，生成加权图G_w.然而，这一类权重仅依赖于局部信息，难以捕捉全局的、高阶的结构依赖，有必要引入一个更强大的、能够感知全局结构的模型来对这些初步权重进行学习和优化，生成更精确、更具上下文感知能力的重要性评分.

（2）边评分（第3行）.SPGRF利用EdgeImpModel函数进行边重要性评分.首先训练一个基于GCN的边评分模型（详见3.3），该模型以加权图G_w中的边权重作为监督信号进行学习，然后利用训练好的模型生成更具上下文感知能力的边重要性分数scores以及能够表征高阶邻域信息的节点向量Z.在获得对图中每条边的精确评估后，进一步构建图的高质量约简骨架.

（3）骨架生成（第4行）.结合约简率r，SPGRF调用GetInitGraph函数（详见3.4）来生成约简骨架G_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}.首先根据InitWeight计算出的节点权重并兼顾原图的标签分布，筛选出最重要的节点集合V_s.接着，利用EdgeImpModel生成的边重要性分数scores，为这些选定的节点连接上分数最高的边，形成一个稀疏但包含关键结构信息的约简骨架G_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}.约简骨架虽然保留了重要的连接，但为了构成蕴含尽可能多频繁模式的约简图，仍需恢复更多的邻域关系.

（4）骨架增强（第5行）.SPGRF调用ConnectEdges函数（详见3.5）来完成图骨架增强.首先，对于在原图中是邻居但在约简骨架中被断开的节点对，函数根据直接连边率d_r恢复部分重要的直连边.然后，对于骨架中的节点v，如果其在原图中的某个邻居u未被选入骨架，该函数利用EdgeImpModel得到的节点表示Z，在现有骨架中为u寻找一个最相似的“替身”节点u^{\text{'}}，若相似度高于阈值\tau，便在v和u^{\text{'}}之间建立连接.通过以上措施，极大地丰富了约简图的结构多样性.

3.2　权重初始化

InitWeight函数利用图G的结构和属性信息，为图中节点和边进行加权，获得加权图G_w.其伪代码如算法2所示.

算法2 InitWeight

输入：图G.

输出：加权图G_w.

1.initialize G_w as G，W_{\mathrm{l}\mathrm{a}\mathrm{b}\mathrm{e}\mathrm{l}\mathrm{s}}，W_{\mathrm{p}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{n}\mathrm{s}}，sEdges；

2.for each node v in G_w do

3. compute W_{\mathrm{n}\mathrm{o}\mathrm{d}\mathrm{e}\mathrm{s}}\left(v\right) using Eq.（5）；

4.end for

5.for each edge e=\left(u,v\right) in G_w do

6. W_{\mathrm{e}\mathrm{d}\mathrm{g}\mathrm{e}\mathrm{s}}\left(e\right):=W_{\mathrm{n}\mathrm{o}\mathrm{d}\mathrm{e}\mathrm{s}}\left(u\right)+W_{\mathrm{n}\mathrm{o}\mathrm{d}\mathrm{e}\mathrm{s}}\left(v\right)+W_{\mathrm{p}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{n}\mathrm{s}}\left(Q_e\right)；

7.end for

8.return G_w.

InitWeight首先初始化四个参数——加权图G_w、辅助结构W_{\mathrm{l}\mathrm{a}\mathrm{b}\mathrm{e}\mathrm{l}\mathrm{s}}和W_{\mathrm{p}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{n}\mathrm{s}}以及单边模式集合sEdges（第1行）.其中，G_w的边集、点集与G一致，但每个节点和每条边都引入了权重属性，初始化为0.W_{\mathrm{l}\mathrm{a}\mathrm{b}\mathrm{e}\mathrm{l}\mathrm{s}}和W_{\mathrm{p}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{n}\mathrm{s}}作为字典结构分别用于存储图G中每个节点标签和每个单边模式对应的权重.sEdges表示图G中所有的单边模式集合，这些单边模式成为G中频繁模式的基础元素.

W_{\mathrm{l}\mathrm{a}\mathrm{b}\mathrm{e}\mathrm{l}\mathrm{s}}\left(a\right)表示标签a出现的频率，定义如下：

W_{\mathrm{l}\mathrm{a}\mathrm{b}\mathrm{e}\mathrm{l}\mathrm{s}}\left(a\right)=\frac{count\left(a\right)}{{\sum }_{l\in G_{\mathrm{l}\mathrm{a}\mathrm{b}\mathrm{e}\mathrm{l}\mathrm{s}}}count\left(l\right)}(3)

其中，G_{\mathrm{l}\mathrm{a}\mathrm{b}\mathrm{e}\mathrm{l}\mathrm{s}}表示图G中标签的集合，count\left(\bullet \right)函数返回具有特定标签的节点数量.

权重W_{\mathrm{p}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{n}\mathrm{s}}\left(Q_e\right)综合了Q_e的语义重要性（通过端节点标签权重体现）和结构重要性（通过支持度体现），其定义如下：

\begin{array}{l}{W}_{\mathrm{p}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{n}\mathrm{s}}\left(Q_e\right)=\beta \bullet \frac{{\sum }_{v\in V_{Q_e}}{W}_{\mathrm{l}\mathrm{a}\mathrm{b}\mathrm{e}\mathrm{l}\mathrm{s}}\left(L\left(v\right)\right)}{\mathrm{2}}+\\ \left(\mathrm{1}-\beta \right)\bullet \frac{Sup\left(Q_e,G\right)}{{\sum }_{Q\in sEdges}Sup\left(Q,G\right)}\end{array}(4)

其中，L\left(v\right)表示节点v的标签，Sup\left(Q_e,G\right)表示Q_e在G中的支持度，引入参数\beta来平衡两部分的权重.考虑到语义重要性与结构重要性分别度量了模式Q_e不同维度的重要程度，为了避免引入先验偏好，设定\beta=0.5作为无偏先验来均衡两方面的重要性.\beta的变化会引起权重W_{\mathrm{p}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{n}\mathrm{s}}\left(Q_e\right)的变化，较大的\beta倾向于从语义角度对模式赋权，反之则偏好结构赋权.\beta的取值受应用影响，受篇幅限制，本文不做赘述.

按照式（3）和式（4）分别计算得到每个标签权重W_{\mathrm{l}\mathrm{a}\mathrm{b}\mathrm{e}\mathrm{l}\mathrm{s}}和每个单边模式权重W_{\mathrm{p}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{n}\mathrm{s}}后，函数开始为G_w中每个节点v进行加权（第2~4行）.其设计理念是一个节点的重要性不仅取决于自身属性，还取决于其局部邻域信息.基于此，v的权重定义如下：

W_{\mathrm{n}\mathrm{o}\mathrm{d}\mathrm{e}\mathrm{s}}\left(v\right)=W_{\mathrm{l}\mathrm{a}\mathrm{b}\mathrm{e}\mathrm{l}\mathrm{s}}\left(L\left(v\right)\right)\bullet \left(\mathrm{1}+\sum _{l\in U_{\mathrm{l}\mathrm{a}\mathrm{b}\mathrm{e}\mathrm{l}\mathrm{s}}}{W}_{\mathrm{l}\mathrm{a}\mathrm{b}\mathrm{e}\mathrm{l}\mathrm{s}}\left(l\right)\right)(5)

其中，U_{\mathrm{l}\mathrm{a}\mathrm{b}\mathrm{e}\mathrm{l}\mathrm{s}}是节点v的所有一阶邻居的标签集合，并排除了v自身的标签L\left(v\right).

加权后，节点的权重不仅考虑了自身标签属性，还聚合了近邻信息，即其一阶邻居标签信息，可以获得更全面的节点重要性衡量.

最后，函数为每条边e进行加权（第5~7行）.边e的权重W_{\mathrm{e}\mathrm{d}\mathrm{g}\mathrm{e}\mathrm{s}}\left(e\right)表示为组成e的两个节点的权重之和，加上e所形成的模式的权重（第6行）.最终，函数InitWeight返回一个加权图G_w（第8行）.

例2 以图1a中的社交网络图为例，展示详细的加权过程.首先，根据节点标签的出现频次，为每个标签赋予对应的权重.例如，DBA，PRG，BA，ST和PM的权重分别为0.37，0.21，0.21，0.11和0.11.随后，为单边模式计算权重.以Q_{\mathrm{1}}：PRG⁃BA为例，其标签部分权重为：

\frac{{\sum }_{v\in V_{Q_{\mathrm{1}}}}{W}_{\mathrm{l}\mathrm{a}\mathrm{b}\mathrm{e}\mathrm{l}\mathrm{s}}\left(L\left(v\right)\right)}{\mathrm{2}}=\frac{\mathrm{0.21}+\mathrm{0.21}}{\mathrm{2}}=\mathrm{0.21}

其支持度部分权重为：

\frac{Sup\left(Q_{\mathrm{1}},G\right)}{{\sum }_{Q\in sEdges}Sup\left(Q,G\right)}=\frac{\mathrm{4}}{\mathrm{20}}

假设\beta =\mathrm{0.5}，则：

W_{\mathrm{p}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{n}\mathrm{s}}\left(Q_{\mathrm{1}}\right)=\mathrm{0.5}\times \mathrm{0.21}+\mathrm{0.5}\times \mathrm{0.2}=\mathrm{0.205}

接着，为节点赋予权重.以节点v_{\mathrm{6}}为例，其邻居节点v_{\mathrm{5}}，v_{\mathrm{7}}，v_{\mathrm{8}}和v_{\mathrm{9}}组成的标签集合为U_{\mathrm{l}\mathrm{a}\mathrm{b}\mathrm{e}\mathrm{l}\mathrm{s}}=\left\{DBA,BA\right\}.因此，

\begin{array}{l}{W}_{\mathrm{n}\mathrm{o}\mathrm{d}\mathrm{e}\mathrm{s}}\left(v_{\mathrm{6}}\right)=W_{\mathrm{l}\mathrm{a}\mathrm{b}\mathrm{e}\mathrm{l}\mathrm{s}}\left(PRG\right)\times \\ \left(\mathrm{1}+W_{\mathrm{l}\mathrm{a}\mathrm{b}\mathrm{e}\mathrm{l}\mathrm{s}}\left(DBA\right)+W_{\mathrm{l}\mathrm{a}\mathrm{b}\mathrm{e}\mathrm{l}\mathrm{s}}\left(BA\right)\right)=\\ \mathrm{0.21}\times \left(\mathrm{1}+\mathrm{0.37}+\mathrm{0.21}\right)=\mathrm{0.3318}\end{array}

对于边的权重，以边\left(v_{\mathrm{6}},v_{\mathrm{8}}\right)为例，其边权重W_{\mathrm{e}\mathrm{d}\mathrm{g}\mathrm{e}\mathrm{s}}\left((v_{\mathrm{6}},v_{\mathrm{8}})\right)由W_{\mathrm{n}\mathrm{o}\mathrm{d}\mathrm{e}\mathrm{s}}\left(v_{\mathrm{6}}\right)，W_{\mathrm{n}\mathrm{o}\mathrm{d}\mathrm{e}\mathrm{s}}\left(v_{\mathrm{8}}\right)和W_{\mathrm{p}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{n}\mathrm{s}}\left(Q_{\mathrm{1}}\right)构成.

W_{\mathrm{e}\mathrm{d}\mathrm{g}\mathrm{e}\mathrm{s}}\left((v_{\mathrm{6}},v_{\mathrm{8}})\right)=0.3318+0.3318+0.205=0.8686

3.3　边评分

详细阐述算法1的核心函数Edge⁃ImpModel的实现机制.该函数接受加权图G_w作为输入，旨在通过学习来融合节点结构和特征的向量表示Z，计算出用于指导图约简的边重要性分数scores.

为此，设计并实现了一个基于GCN的边评分模型（Graph Convolutional Network based Edge Evaluation Model，GEEM）.GEEM通过学习图的拓扑结构和节点特征来完成边的评分，其网络结构（如图2所示）包含三个部分：（1）节点初始特征构建模块；（2）节点表示学习模块；（3）边重要性评估模块.

3.3.1　节点初始特征构建

首先，为图中的每个节点v构建初始特征向量h_v^{\left(\mathrm{0}\right)}.先利用词向量嵌入技术（如Word2Vec）将节点的离散标签（如类别）映射为一个稠密的语义向量e_v；随后，将此语义向量与该节点的权重信息W_{\mathrm{n}\mathrm{o}\mathrm{d}\mathrm{e}\mathrm{s}}\left(v\right)（通过函数InitWeight获得）进行拼接.如式（6）所示：

h_v^{\left(\mathrm{0}\right)}=\left[e_v‖W_{\mathrm{n}\mathrm{o}\mathrm{d}\mathrm{e}\mathrm{s}}\left(v\right)\right](6)

通过这种方式构建的初始特征向量h_v^{\left(\mathrm{0}\right)}既编码了节点的语义属性，也融入了其对于模式的重要程度.

3.3.2　节点表示学习

为了捕捉图的拓扑结构信息，采用一个两层的GCN对所有的初始节点特征向量H^{\left(\mathrm{0}\right)}=h_{\mathrm{1}}^{\left(\mathrm{0}\right)},h_{\mathrm{2}}^{\left(\mathrm{0}\right)},h_{\mathrm{3}}^{\left(\mathrm{0}\right)},\dots ,h_n^{\left(\mathrm{0}\right)}进行深度学习.GCN的核心机制在于通过迭代式的消息传播与聚合，使每个节点能够捕获其邻域内的信息，其更新过程遵循以下聚合与变换规则：

H^{\left(l+\mathrm{1}\right)}=\sigma \left({\tilde{D}}^{-\frac{\mathrm{1}}{\mathrm{2}}}\tilde{A}{\tilde{D}}^{-\frac{\mathrm{1}}{\mathrm{2}}}{H}^{\left(l\right)}{W}^{\left(l\right)}\right)(7)

其中，\tilde{A}为含自连接的邻接矩阵，\tilde{D}为度矩阵，W^{(l)}为可学习参数，\sigma为激活函数，H^{(l)}为节点特征矩阵.

如图2所示，深蓝色节点表示需要从周围邻居聚合信息的目标节点，红色和黄色线分别代表一阶邻居和二阶邻居的信息流.经过两层GCN的计算后，模型得到节点表示Z=H^{\left(\mathrm{2}\right)}，矩阵Z中的行向量z_v（即h_v^{\left(\mathrm{2}\right)}）是节点v融合了其二阶邻域内的结构和特征信息的深度表示.

3.3.3　边重要性评估

在获得能够表征节点局部拓扑环境的向量表示Z后，进而对边的重要性进行评估.对于图中的任意一条边\left(u,v\right)，通过拼接其端节点的最终向量表示z_u和z_v，来构造该边的特征向量h_{uv}：

h_{uv}=\left[z_u‖z_v\right](8)

随后，将h_{uv}输入一个两层全连接构成的MLP模块以预测其重要性分数s_{uv}.其计算过程如下：

s_{uv}=W_{\mathrm{2}}\sigma \left(W_{\mathrm{1}}{h}_{uv}+b_{\mathrm{1}}\right)+b_{\mathrm{2}}(9)

其中，W_{\mathrm{1}}，b_{\mathrm{1}}和W_{\mathrm{2}}，b_{\mathrm{2}}分别是MLP第一层和第二层的权重与偏置.第一层将输入映射至一个32维的隐藏空间并由ReLU激活，第二层将隐藏表示线性变换为一维的标量输出，即边的重要性分数s_{uv}，所有边的预测分数s_{uv}构成分数集合scores.

3.3.4　损失函数与模型优化

模型的训练过程在一个监督学习框架下进行.函数InitWeight获取的边权重W_{\mathrm{e}\mathrm{d}\mathrm{g}\mathrm{e}\mathrm{s}}是监督信号，均方误差（Mean Squared Error，MSE）是损失函数Loss，可度量模型预测分数s_{uv}与真实权重W_{\mathrm{e}\mathrm{d}\mathrm{g}\mathrm{e}\mathrm{s}}\left(u,v\right)之间的差异.损失函数的定义如下：

Loss=\frac{\mathrm{1}}{\left|E\right|}\sum _{\left(u,v\right)\in E}{\left(s_{uv}-W_{\mathrm{e}\mathrm{d}\mathrm{g}\mathrm{e}\mathrm{s}}\left(u,v\right)\right)}^{\mathrm{2}}(10)

其中，\left|E\right|为边集E的大小.通过反向传播算法来计算损失函数Loss对模型所有可学习参数（包括GCN的W^{\left(l\right)}和MLP的权重与偏置）的梯度，并借助梯度下降优化器Adam来迭代更新这些参数，以最小化损失函数，来不断优化模型的预测性能.

3.4　骨架生成

GetInitGraph函数接受加权图G_w、约简率r和边重要性分数scores作为输入，返回初始图骨架G_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}.详细流程如算法3所示.

算法3 GetInitGraph

输入：加权图G_w，约简率r，边重要性分数scores.

输出：初始图骨架G_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}.

1.initialize G_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}；

2.V_s:=SelectNodes\left(G_w,r\right)；

3.G_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}:=SelectEdges\left(scores,V_s,r\right)；

4.return G_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}；

5.function SelectNodes\left(G_w,r\right)

6. initializeV_s=\mathrm{\varnothing },B_{\mathrm{l}\mathrm{a}\mathrm{b}\mathrm{e}\mathrm{l}\mathrm{s}}；

7. for each label l in B_{\mathrm{l}\mathrm{a}\mathrm{b}\mathrm{e}\mathrm{l}\mathrm{s}} do

8. k_l:=\mathrm{m}\mathrm{a}\mathrm{x}\left(\mathrm{1},⌈r\bullet \left|B_{labels}\left(l\right)\right|⌉\right)；

9. select \mathrm{t}\mathrm{o}\mathrm{p}\_k_l nodes V_s^{\text{'}} from B_{\mathrm{l}\mathrm{a}\mathrm{b}\mathrm{e}\mathrm{l}\mathrm{s}}\left(l\right) with highest W_{\mathrm{n}\mathrm{o}\mathrm{d}\mathrm{e}\mathrm{s}}；

10. V_s:=V_s\bigcup V_s^{\text{'}}；

11. end for

12. return V_s；

13.function SelectEdges\left(scores,V_s,r\right)

14. initialize G_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}， sEdges；

15. for each pattern Q in sEdges do

16. targetSupport:=max(\mathrm{1},\mathrm{⎡}r\bullet Sup(Q,G)\mathrm{⎤})；

17. for each edge e in instance(Q,G) do

18. if e.u in V_s and e.v in V_s then

19. candEdges.adde；

20. end for

21. sort candEdges by the scores of each edge in descending order；

22. for each edge e in candEdges do

23. E_s:=E_s\bigcup \left\{e\right\}；

24. if Sup\left(Q,G_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}\right)\ge targetSupport then

25. break；

26. end for

27. end for

28.return G_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}；

该函数在初始化G_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}后（第1行），通过调用两个核心函数SelectNodes和SelectEdges来完成初始图骨架节点和边的构建.其中，SelectNodes函数首先初始化一个空的节点集合V_s以及一个用于存储各标签对应节点的字典B_{\mathrm{l}\mathrm{a}\mathrm{b}\mathrm{e}\mathrm{l}\mathrm{s}}（第6行）.为了有效保留原图的频繁结构信息，一个核心的设计原则是在约简过程中保持节点标签分布的高度一致性.随后，该函数结合原图信息和约简率为初始图骨架筛选其节点集V_s（第7~11行）.对于每个标签l，首先根据约简率和\left|B_{\mathrm{l}\mathrm{a}\mathrm{b}\mathrm{e}\mathrm{l}\mathrm{s}}\left(l\right)\right|计算出l应选出的节点数量k_l（第8行），然后根据节点权重W_{\mathrm{n}\mathrm{o}\mathrm{d}\mathrm{e}\mathrm{s}}，从B_{\mathrm{l}\mathrm{a}\mathrm{b}\mathrm{e}\mathrm{l}\mathrm{s}}\left(l\right)中选择前k_l个权重大的节点加入V_s（第9行和第10行）.

SelectEdges函数利用模型给出的边重要性分数scores构建初始图骨架G_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}.该函数首先基于已选定的节点集V_s初始化G_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}（第14行），其核心目标是使初始图骨架的单边模式支持度排序与原图对齐，以保留原图中重要的频繁模式结构.基于此目标，SelectEdges函数的选边流程如下（第15~27行）.对于每一个单边模式Q_e，其目标支持度为targetSupport，计算方式为原图支持度Sup\left(Q_e,G\right)与约简率r的乘积（第16行）.接着，从Q_e在原图中的实例instance\left(Q_e,G\right)中选出边中节点都在V_s中的边，将其加入候选边集合candEdges（第17~20行）.随后，该函数迭代处理按重要性分数降序排列的候选边，在每一轮迭代中，将边加入G_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}，直到Q_e在约简图中的支持度Sup\left(Q_e,G_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}\right)达到其targetSupport为止（第22~26行）.最终，该函数返回初始图骨架G_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}（第28行）.

例3 以约简率r=\mathrm{0.5}为例.首先，确定各标签下的节点数量.如图3a所示，标签PRG在原图中有四个节点（v_{\mathrm{2}}，v_{\mathrm{6}}，v_{\mathrm{7}}和v_{\mathrm{12}}），因此，在约简图中PRG的节点应有\mathrm{4}\times \mathrm{0.5}=\mathrm{2}个.再根据节点的权重，选择权重最大的v_{\mathrm{2}}和v_{\mathrm{12}}.对所有标签执行此操作后，便得到约简图的节点集V_s，如图3b中有颜色的节点所示.接着依据重要性分数scores选择边.以单边模式Q_{\mathrm{3}}：DBA⁃PRG为例，其支持度Sup\left(Q_{\mathrm{3}},G\right)=\mathrm{4}，因此，其目标支持度为\mathrm{4}\times \mathrm{0.5}=\mathrm{2}.假设Q_{\mathrm{3}}的实例按照scores降序排列为\left(v_{\mathrm{9}},v_{\mathrm{6}}\right)\left(v_{\mathrm{1}},v_{\mathrm{12}}\right)\left(v_{\mathrm{1}},v_{\mathrm{2}}\right)\left(v_{\mathrm{4}},v_{\mathrm{2}}\right)\left(v_{\mathrm{4}},v_{\mathrm{12}}\right)\left(v_{\mathrm{5}},v_{\mathrm{6}}\right)等，函数按顺序检查这些边.\left(v_{\mathrm{9}},v_{\mathrm{6}}\right)因v_{\mathrm{6}}不在V_s中而被跳过.\left(v_{\mathrm{1}},v_{\mathrm{12}}\right)和\left(v_{\mathrm{1}},v_{\mathrm{2}}\right)的节点均在V_s中，因此被加入E_s.此时，Sup\left(Q_{\mathrm{3}},G_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}\right)=\mathrm{2}，满足目标，因此该模式后续的候选边（如\left(v_{\mathrm{4}},v_{\mathrm{2}}\right)等）不再被考虑.对所有单边模式重复此过程，最终形成如图3b所示的初始图骨架G_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}.

3.5　骨架增强

如算法4所示，ConnectEdges函数以图G，初始图骨架G_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}、边重要性分数scores、节点表示Z、直接连边率d_r和相似度阈值\tau作为输入，返回最终的约简图G_s.

算法4 ConnectEdges

输入：图G，初始图骨架G_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}，边重要性分数scores，节点表示Z，直接连边率d_r，相似度阈值\tau.

输出：约简图G_s.

1.initialize groupNodes；

2.for each node v in V_s do

3. for each node u_{\mathrm{1}} in N_G\left(v\right)\bigcap V_s do

4. if \left(v,u_{\mathrm{1}}\right)\notin G_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}} then

5. missingEdges\left(v\right).add\left(v,u_{\mathrm{1}}\right)；

6. end for

7. k_e:=\mathrm{m}\mathrm{a}\mathrm{x}\left(\mathrm{1},⌈d_r\bullet \left|missingEdges\left(v\right)\right|⌉\right)；

8. select top\_k_e edges E_s^{\text{'}} from missingEdges(v) with highest scores；

9. E_s:=E_s\bigcup E_s^{\text{'}}；

10. for each node u_{\mathrm{2}} in N_G\left(v\right)\backslash V_s do

11. candNodes:=groupNodes\left(L\left(u_{\mathrm{2}}\right)\right)；

12. pick a node u_{\mathrm{2}}^{\text{'}} in candNodes with highest Similarity\left(Z\left(u_{\mathrm{2}}\right),Z\left(u_{\mathrm{2}}^{\text{'}}\right)\right)；

13. if Similarity\left(Z\left(u_{\mathrm{2}}\right),Z\left(u_{\mathrm{2}}^{\text{'}}\right)\right)\ge \tau then

14. E_s:=E_s\bigcup \left\{\left(v,u_{\mathrm{2}}^{\text{'}}\right)\right\}；

15. end for

16.end for

17. return G_s；

ConnectEdges函数分为两部分——直接邻居连边（第3~9行）和间接邻居连边（第10~15行）.首先该函数初始化一个字典辅助结构groupNodes，用于存储G中每个标签下对应的节点集合（第1行）.在直接邻居连边部分，对于G_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}节点集合V_s中的每一个节点v，如果其在G中的邻居节点u_{\mathrm{1}}也在V_s中且G_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}中不存在\left(v,u_{\mathrm{1}}\right)这条边（第4行），则将\left(v,u_{\mathrm{1}}\right)加入缺失边集合missingEdges\left(v\right)中（第5行）.为了避免过度连接导致约简图过于稠密，进而破坏模式支持度排序并影响下游任务效果，函数引入直接连边率d_r来控制直接连边数量k_e（第7行）.随后，从缺失边集合missingEdges\left(v\right)中选出分数最高的前k_e条边，加入约简图边集E_s（第8行和第9行）.对于那些不在V_s中的邻居节点u_{\mathrm{2}}，首先从groupNodes中选出u_{\mathrm{2}}对应的标签L\left(u_{\mathrm{2}}\right)下的候选节点candNodes（第11行）.由于节点表示Z已通过GCN聚合了邻域信息，因此节点表示间的相似度可反映其结构相似性.基于此，函数在与u_{\mathrm{2}}同标签的V_s节点中，寻找一个与u_{\mathrm{2}}节点表示（通过余弦相似度衡量）最相似的替代节点u_{\mathrm{2}}^{\text{'}}（第12行）.如果该相似度超过阈值\tau，则将新边\left(v,u_{\mathrm{2}}^{\text{'}}\right)加入E_s（第14行）.考虑到间接连边本质上属于对缺失结构的“推测性恢复”，为了有效抑制“伪连接”的引入，本文采取严格的“保真”策略，即将相似度阈值设定为\tau =\mathrm{1}.该设定使得仅在节点表示高度相似（即具有较高结构一致性）的情况下才允许建立连接，可以在一定程度上减少噪声边的引入，保证约简图的结构精确性.完成边连接操作后，函数返回最终的约简图G_s.

例4 在图3b的初始图骨架G_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}基础上执行ConnectEdges函数.以节点v_{\mathrm{3}}为例，其在原图的邻居v_{\mathrm{4}}也在约简图节点V_s中，因此根据直接连边规则添加边\left(v_{\mathrm{3}},v_{\mathrm{4}}\right)（如图3c中红线所示），v_{\mathrm{4}}同理.处理v_{\mathrm{5}}时其邻居v_{\mathrm{6}}不在V_s中，因此，执行间接连边，即函数在V_s中寻找与v_{\mathrm{6}}同类（标签为PRG）的节点，并从中选择最相似的节点作为替代节点（假设为v_{\mathrm{2}}），但因其相似度未超过阈值\tau，故不添加\left(v_{\mathrm{5}},v_{\mathrm{2}}\right).处理v_{\mathrm{8}}时其邻居v_{\mathrm{7}}（标签为PRG）不在V_s中，函数在v_{\mathrm{7}}的同类节点\left\{v_{\mathrm{2}},v_{\mathrm{12}}\right\}中发现v_{\mathrm{7}}与v_{\mathrm{12}}最相似，且相似度大于阈值\tau，因此添加\left(v_{\mathrm{8}},v_{\mathrm{12}}\right)（如图3c中绿线所示），v_{\mathrm{9}}同理.对V_s中所有节点执行完毕后，得到如图3c所示的最终约简图G_s.该图通过边的恢复与重连，维持了原图中更多的频繁模式（如阴影部分所示）.

3.6　复杂度分析

从最坏时间复杂度的角度展开分析.SPGRF算法的时间开销由三部分构成：（1）权重初始化InitWeight（算法2）；（2）骨架生成GetInitGraph（算法3）；（3）骨架增强Connect⁃Edges（算法4）.

算法2的时间开销主要包括四部分：（1）第1行初始化标签权重的计算，需要遍历所有节点的标签来统计频率，时间复杂度为O\left(\left|V\right|\right).（2）为每个单边模式计算权重，执行\left|sEdges\right|次，时间复杂度为O\left(\left|E\right|\right).（3）计算节点权重.第2行的for循环执行\left|V\right|次，循环内部需要找到每个节点v的一阶邻居，需要执行该节点的度数deg\left(v\right)次，总执行次数为所有节点度数之和，因此这部分的时间复杂度为O\left(\mathrm{2}\times \left|E\right|\right).（4）计算边权重.第5行的for循环需要为每条边赋予权重，即时间复杂度为O\left(\left|E\right|\right).因此，算法2的总时间复杂度为O\left(\left|V\right|+\left|E\right|\right).

算法3的时间开销主要由函数SelectNodes和SelectEdges决定.函数SelectNodes主要分两步.首先，初始化B_{\mathrm{l}\mathrm{a}\mathrm{b}\mathrm{e}\mathrm{l}\mathrm{s}}（第6行）要将原图所有节点按标签分组，需遍历全部节点，时间复杂度为O\left(\left|V\right|\right).其次，第7行的for循环对每个标签，从其节点集中选出权重最高的k_l个节点（第9行），涉及对每个标签下的节点进行排序.将所有标签的操作汇总，其总时间复杂度的上界为O\left(\left|V\right|\times \mathrm{l}\mathrm{g}\left|V\right|\right).SelectEdges函数首先通过两层嵌套循环（第15~20行）遍历所有模式的所有边实例，以筛选出两个端点都在V_s中的候选边.总执行次数为所有模式实例数之和，时间复杂度为O\left(\left|E\right|\right).随后，对于每个模式，函数对筛选出的候选边按重要性分数进行排序（第21行），这是此函数的主要时间开销.所有模式的排序总时间复杂度的上界为O\left(\left|E\right|\times \mathrm{l}\mathrm{g}\left|I_{max}|\right|\right)，其中，\left|I_{\mathrm{m}\mathrm{a}\mathrm{x}}\right|是单个模式包含的最大边实例数.因此，算法3的总时间复杂度为O\left(\left|V\right|\times \mathrm{l}\mathrm{g}\left|V\right|+\left|E\right|\times \mathrm{l}\mathrm{g}\left|I_{max}\right|\right))，最坏情况下的时间复杂度为O\left(\left|V\right|\times \mathrm{l}\mathrm{g}\left|V\right|+\right.

\left.\left|E\right|\times \mathrm{l}\mathrm{g}\left|E\right|\right).

算法4的核心是一个遍历约简图节点V_s的主循环（第2行），该循环执行\left|V_s\right|次，其时间复杂度主要由循环内部的两个部分构成.（1）处理直接邻居（第3~8行）.对于每个节点v，首先遍历其在图G中的所有邻居（第3行），该操作执行deg\left(v\right)次.随后，从缺失边集合中选出得分最高的k_e条边（第7行），这需要对最多deg\left(v\right)条缺少边进行排序，因此这部分最坏情况下的时间复杂度为O\left(deg\left(v\right)\times \mathrm{l}\mathrm{g}\left(deg\left(v\right)\right)\right).（2）处理间接邻居（第9~15行）.接着遍历节点v的邻居u_{\mathrm{2}}（第10行），执行deg(v)次.对于每个u_{\mathrm{2}}，需要从其同类别的候选节点candNodes中，通过计算向量相似度找到最匹配的节点（第11行）.若候选集大小为\left|C\right|，向量维度为d，则此操作的复杂度为O\left(\left|C\right|\times d\right).因此，算法4的总时间复杂度为：

O\left(\left|V_s\right|\times deg\_G\_avg\times \left(\mathrm{l}\mathrm{g}\left(deg\_G\_avg\right)+\left|C\right|\times d\right)\right)

进一步化简为：

O\left(\left|V\right|\times \left(\left|E\right|/\left|V\right|\right)\times \left(\mathrm{l}\mathrm{g}\left(\left|E\right|/\left|V\right|\right)+\left|V\right|\times d\right)\right)

即O\left(\left|V\right|\times \left|E\right|\right).综合以上分析，SPGRF的时间复杂度为：

\begin{array}{l}O\left(\left|V\right|+\left|E\right|+\left|V\right|\times \mathrm{l}\mathrm{g}\left|V\right|+\right.\\ \left.\left|E\right|\times \mathrm{l}\mathrm{g}\left|E\right|+\left|V\right|\times \left|E\right|\right)\end{array}

最终可约简为O\left(\left|V\right|\times \left|E\right|\right).

值得一提的是，骨架增强阶段替代节点的搜索与连接过程相互独立，具备良好的并行化计算潜力.此外，作为离线预处理步骤，该框架以一次性的计算换取下游挖掘任务的高效与高保真，在非实时的大规模图分析场景中具有较高的实用价值.

SPGRF的空间复杂度主要由两部分组成.（1）图结构的存储，空间复杂度为O\left(\left|V\right|+\left|E\right|\right).（2）节点表示的存储.为图中每一个节点存储维度为d的向量，空间复杂度为O\left(d\times \left|V\right|\right).因此，SPGRF总的空间复杂度为O\left(d\times \left|V\right|+\left|E\right|\right).

4 实验

在六个真实数据集上验证了SPGRF的效率和性能，证明SPGRF的约简效果优异.实验环境为一台3.70 GHz CPU和NVIDIA GeForce RTX 4060Ti GPU的Windows 11主机.实验代码均由Python 3.9编写.

4.1　实验设置

4.1.1　实验数据

共使用六个真实数据集：YouTube共享网络^［37］，论文出版网络图DBLP^［38］，蛋白质结构网络PDB^［39］，产品联合采购网络Amazon^［40］，Skitter网站互联网拓扑图^［19］，维基百科超链接的网络图Wiki^［41］.相关的统计信息如表2所示.

4.1.2　基线算法

（1）大规模图稀疏化摘要算法（Sparse Summarization of Massive Graphs，SSumM）^［21］.在最小描述长度原则指导下，交替执行节点合并与超边稀疏化，以比特数为约束生成稀疏图摘要.为了使输出能应用于频繁模式挖掘下游任务，从超边的两个超点中选取支持度最大边作为超边的替代.

（2）行走指数稀疏化算法（Walk Index Sparsification，WIS）^［10］.按边对划分边界游走数的贡献由小到大排序，依次删边，以最小结构改动保住GNN对节点交互的建模能力.

（3）共同邻居感知随机游走采样算法（Common Neighbor Aware Random Walk，CNARW）^［18］.改进了传统随机游走，引入共同邻居信息指导游走方向.每一步选择下一跳节点时，计算当前节点与候选节点的共同邻居数量.根据共同邻居数量对候选节点加权，优先选择共同邻居多的节点.

（4）森林火灾采样算法（Forest Fire Sampling，FF）^［16］.模拟森林火灾蔓延的随机遍历，从一个随机种子节点开始，以设定的“燃烧概率”决定是否“点燃”每个邻居.被点燃的节点继续以同样方式向外蔓延，直至达到预设规模.

（5）钉球采样算法（Spikyball Sampling，SS）^［17］.基于广度优先搜索对“雪球采样”的改进，从一个或多个种子节点开始，逐层扩展，每层选择当前节点的邻居并可进一步探索邻居的邻居.

（6）SPGRF_Init算法是没有进行骨架增强的SPGRF算法.

（7）top⁃k频繁模式挖掘算法（BMiner）^［19］.从图G中直接挖掘前k个高频子图模式，无需预设支持度阈值.

4.1.3　评价指标

采用以下三个指标从不同角度观察约简图和原图的差异.

（1）属性偏差（Attribute Deviation，AD）^［42］，是约简图G_s与原图G对应的属性相同的节点所占的比例.定义如下：

AD=\sum _{{\psi }^i\in G}\left|percentag{e}^i\left(G_s\right)-percentag{e}^i\left(G\right)\right|(11)

其中，{\psi }^i为具有相同属性i的节点集合，percentag{e}^i 为当前属性节点个数占完整图的节点个数的百分比.显然，AD越小，图的属性偏差越小.

（2）平均接近中心性（Average Closeness Centrality，AvgCC）^［43］，可以用来评估单个节点到图中其他节点的平均距离，反映了该节点在网络中的中心性和重要性.

C\left(i\right)=\frac{\mathrm{1}}{{\sum }_{u\ne v}d\left(u,v\right)}(12)

其中，d\left(u,v\right)表示节点u和节点v之间的最短路径距离.平均接近中心性可表示为：

AvgCC=\frac{\mathrm{1}}{n}\sum _{v\in V}C\left(v\right)(13)

（3）信息熵损失（Entropy Loss，EL）^［44］，可用于衡量约简后信息丢失的程度.图的信息熵能够反映图的结构信息与复杂性^［45］，定义如下：

I\left(G\right)=-\sum _{l\in labels\left(G\right)}p\left(l\right)\mathrm{l}\mathrm{g}\left(p\left(l\right)\right)(14)

其中，p\left(l\right)是标签l出现的频率，labels\left(G\right)是图G所有唯一节点标签的集合.

EL是原图G与约简图G_s的熵之间的归一化差异，其值越低，约简图的质量越好.

EL=\frac{\left|I\left(G\right)-I\left(G_s\right)\right|}{I\left(G\right)}(15)

4.2　实验结果

4.2.1　实验一：约简质量

约简率r从0.1开始，每次增加0.05，直到0.3，相似度阈值\tau和直接连边率d_r分别为1和对应的r.探究了六种约简方法的属性偏差、平均接近中心性和信息熵损失.图4展示了各算法在属性偏差上的表现.由图可见，SPGRF在YouTube，DBLP，PDB和Skitter四个数据集上表现最优，在Amazon和Wiki数据集上表现稍差，归因于其属性维度高且分布不均.图5展示了各算法在平均接近中心性上的表现.由图可见，随着r的增大，SPGRF的平均接近中心性逐渐趋近原图，并展现出良好的性能.在YouTube和Wiki数据集上的表现稍逊色于其他算法，这是因为SPGRF主要关注高频节点，而且，进行骨架增强后，改变了部分节点的全局最短路径分布，在宏观上导致平均接近中心性与原图产生了一定的偏移.图6展示了算法在信息熵损失方面的差异，刻画了约简图的信息损失程度.由图可见，SPGRF在大部分数据集上表现优异，而且，随着r的增大，损失总体呈下降趋势.在Amazon数据集上的表现在可接受程度上稍逊色于部分算法，这主要归因于Amazon数据集的特性与SPGRF的核心机制的相互作用.Amazon数据集标签的分布极不均衡，标签数量多且部分标签只在少量节点出现，而SPGRF更侧重于保留构成高频结构的节点.因此，算法在约简时更容易舍弃携带这些稀有标签的节点，而信息熵损失对这类少数类别的移除尤为敏感，导致了损失值相对偏高.

4.2.2　实验二：约简效率

固定约简率r为0.1，相似度阈值\tau为1，直接连边率d_r为0.1，在六个数据集上比较SPGRF，SPGRF_Init和其他五种基线算法的时间消耗（表3）和内存占用（表4），以探究不同方法的约简效率.从实验结果可以看出，时间消耗，SPGRF_Init与多数基线算法处于同一量级，但是完整的SPGRF耗时显著增加，表明主要的额外时间开销来源于ConnectEdges函数中计算成本较高的骨架增强过程.具体地，该过程需要为每个待处理节点在候选集合中遍历搜索最相似的替代节点，以进行精准的结构修复，其计算复杂度直接与图节点数量及候选集合规模正相关，带来不可避免的额外计算耗时.内存占用，SPGRF和SPGRF_Init的差距不大，但均高于部分基线算法，这符合预期，因为两者都需要保持图节点和边的权重信息以及每个节点的向量表示，这些信息增加了存储负担.骨架增强的计算开销并非冗余，它直接决定约简图中核心结构模式的恢复质量，弥补因直接断边导致的模式丢失，是保障下游任务极高准确率的必要代价.综合来看，SPGRF在时间和内存上的额外开销是为了实现高保真模式保留而进行的一种必要投资，这些额外存储的信息（权重和向量表示）和计算过程（骨架增强）正是SPGRF在下游频繁模式挖掘任务中性能远超其他方法的关键.因此，这种开销不仅是可接受的，更是一种以可控的计算资源换取下游任务性能显著提升的高效权衡（trade⁃off）.

4.2.3　实验三：top⁃k频繁模式准确率评估

本实验中，约简率r从0.1开始，每次增加0.05，直到0.3，相似度阈值\tau和直接连边率d_r分别为1和对应的r.对于数据集YouTube，DBLP，PDB，Amazon，Skitter和Wiki，k值分别设置为300，300，300，300，200和800，旨在探究不同约简算法产生的约简图对于频繁模式挖掘任务的有效性.首先，对于同一个图G，采用六种不同的约简算法生成对应的约简图.为了保证公平，所有基线算法生成的约简图规模与SPGRF保持一致.具体地，对于以节点数为约简目标的算法，设置相同的r；对于以边数为约简目标的算法，调整其参数，使其生成的约简图边数与SPGRF在对应r下生成的图边数大致相等.然后，分别在这些约简图和原图上执行BMiner频繁模式挖掘算法，获取top⁃k频繁模式.最后，通过比较约简图中和原图中获取的频繁模式来评估准确率.如图7所示，在大多数情况下，SPGRF在六个数据集上都表现出色，准确率均显著优于其他基线方法.随着r的逐步提升，SPGRF的准确率也基本呈上升趋势，表明更高的r能保留更多的频繁结构信息.一个值得注意的特例是，在Amazon数据集中，SPGRF的准确率在r=\mathrm{0.2}后开始出现轻微的下降，原因在于随着r的增大，骨架增强机制中修复的边连接数也增加，而过量的边连接可能引入了噪声，反而对部分原有的频繁模式造成了破坏.

4.2.4　实验四：骨架增强对算法的影响

本实验中，约简率r固定为0.2，相似度阈值\tau为1，直接连边率d_r从0.1开始，每次增加0.1，直到0.5.对于数据集YouTube，DBLP，PDB，Amazon，Skitter和Wiki，k的值分别设置为300，2000，80，300，2000和1200，探究有无图骨架增强机制以及d_r对算法的影响.

如图8所示，在YouTube，DBLP，PDB和Amazon等多个数据集中，SPGRF在top⁃k频繁模式挖掘任务中表现更好，显著优于SPGRF_Init，证明骨架增强机制对于频繁结构保留的有效性.同时也发现，随着d_r的增大，SPGRF的准确率会出现降低，甚至出现低于不进行骨架增强的SPGRF_Init情况，这是过度的连接引入“结构噪声”带来错误的信息，导致准确率的下降.特别是在Skitter数据集中，SPGRF_Init的性能几乎全面优于SPGRF，这是由于Skitter数据的结构相对稀疏，包含大量简单的局部模式.在这种情况下，骨架增强模块引入的额外边反而更容易形成“伪模式”，干扰了对原有简单模式的挖掘.基于上述实验结果，为了在有效恢复局部结构与抑制结构噪声之间取得最佳平衡，本文在主要实验中统一设定d_r=r，这一取值使直接连边的保留比例与全局图规模的缩减比例保持动态对齐，从而在微观层面维持了约简图与原图在局部连边密度上的相对一致性.

5 结论

针对大规模图上频繁模式计算成本高昂的挑战，本文提出一种结构保持式图约简框架SPGRF，有效克服了现有的图约简技术因为没有保留关键频繁结构，导致下游频繁模式挖掘任务准确率低的普遍挑战.SPGRF利用GCN感知边对于模式的重要性，并且，综合利用原图结构信息和GCN学习到的节点表示来恢复约简过程中可能丢失的潜在边，显著提升了约简图对原图高频模式的恢复能力.通过广泛的实验验证了SPGRF框架的有效性与优越性.在多个真实数据集上的实验结果表明，SPGRF生成的约简图能更好地保留原图的骨干结构.即使在约简率为0.1下，该框架依然能在Wiki数据集上的\mathrm{t}\mathrm{o}\mathrm{p}\mathrm{⁃}k\left(k=\mathrm{800}\right)频繁模式挖掘上达到最高96%的准确率，为解决大规模图数据上的频繁模式挖掘问题提供了一条行之有效的路径.然而，SPGRF在处理标签分布极度不均衡或原生结构极度稀疏的图数据时，存在引入结构噪声的局限.

未来将探索面向动态演化图的增量学习机制与自适应参数调节策略，以进一步优化骨架增强机制，并尝试将SPGRF应用于节点分类等通用图分析任务，提升其泛化能力.

参考文献

[1] 邹杰军，王欣，石俊豪，等. 面向大图的Top⁃Rank⁃K 频繁模式挖掘算法.南京大学学报(自然科学)，2024，60(1)：38-52.

[2] Hashemi M， Gong S B， Ni J T，et al. A comprehensive survey on graph reduction：Sparsification，coarsening，and condensation∥Proceedings of the 33rd International Joint Conference on Artificial Intelligence. Jeju，Korea (South)：IJCAI，2024：8058-8066.

[3] Liu Y L， Qiu R H， Huang Z. Cat：Balanced continual graph learning with graph condensation∥2023 IEEE International Conference on Data Mining. Shanghai，China：IEEE，2023：1157-1162.

[4] Wickman R， Zhang X F， Li W Z. A generic graph sparsification framework using deep reinforcement learning∥2022 IEEE International Conference on Data Mining. Orlando，FL，USA：IEEE，2022：1221-1226.

[5] Seo H， Yun J H， Yang E. TEDDY：Trimming edges with degree⁃based discrimination strategy∥The 12th International Conference on Learning Represen⁃tations. Vienna，Austira：ICLR，2023：1-12.

[6] Meng Y C， Li R H， Lin L L，et al. Topology⁃preserving graph coarsening：An elementary collapse⁃based approach. Proceedings of the VLDB Endowment，2024，17(13)：4760-4772.

[7] Kumar M， Sharma A， Saxena S，et al. Featured graph coarsening with similarity guarantees∥Proceedings of the 40th International Conference on Machine Learning. New York，NY，USA：PMLR，2023：17953-17975.

[8] Althöfer I， Das G， Dobkin D，et al. On sparse spanners of weighted graphs. Discrete & Compu⁃tational Geometry，1993，9(1)：81-100.

[9] Feng Z. GRASS：Graph spectral sparsification leveraging scalable spectral perturbation analysis. IEEE Transactions on Computer：Aided Design of Integrated Circuits and Systems，2020，39(12)：4944-4957.

[10] Razin N， Verbin T， Cohen N. On the ability of graph neural networks to model interactions between vertices. Advances in Neural Information Processing Systems，2023，36：26501-26545.

[11] Zhao J X， Huang T J， Liu S W，et al. FS⁃GNN：Improving fairness in graph neural networks via joint sparsification. Neurocomputing，2025，648：130641.

[12] Zhang G B， Sun X G， Yue Y W，et al. Graph sparsification via mixture of graphs∥The 13th International Conference on Learning Represen⁃tations. Singapore：ICLR，2025：92735-92763.

[13] Akkas S， Azad A. Explainable graph sparsification with Shapley values∥Proceedings of the ACM Web Conference 2026. New York，NY,USA：Association for Computing Machinery，2026：8557-8560.

[14] Shabani N， Beheshti A， Qi Y K，et al. STGS：Spatio⁃temporal graph sparsification using reinforcement learning∥Proceedings of the 34th ACM International Conference on Information and Knowledge Management. New York，NY，USA：Association for Computing Machinery，2025：2546-2555.

[15] Yuan Y H， Aghdaei A， Feng Z. dyGRASS：Dynamic spectral graph sparsification via localized random walks on GPUs∥2025 IEEE/ACM International Conference on Computer Aided Design.Munich，Germany：IEEE，2025：1-9.

[16] Zhang X， Ni Y， Li S Y，et al. A survey of large graph sampling techniques. Journal of Computer⁃Aided Design & Computer Graphics，2022，34(12)：1805-1814.

[17] Ricaud B， Aspert N， Miz V. Spikyball sampling：Exploring large networks via an inhomogeneous filtered diffusion. Algorithms，2020，13(11)：275.

[18] Li Y K， Wu Z Y， Lin S，et al. Walking with perception：efficient random walk sampling via common neighbor awareness∥2019 IEEE 35th International Conference on Data Engineering.Macao，China：IEEE，2019：962-973.

[19] Wang X， Shi J H， Zou J J，et al. Supports estimation via graph sampling. Expert Systems with Applica⁃tions，2024，240：122554.

[20] Loukas A， Vandergheynst P. Spectrally approxi⁃mating large graphs with smaller graphs∥Proceedings of the 35th International Conference on Machine Learning. New York，NY，USA：PMLR，2018：3237-3246.

[21] Lee K， Jo H， Ko J，et al. Ssumm：Sparse summarization of massive graphs∥Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. New York，NY，USA：Association for Computing Machinery，2020：144-154.

[22] Huang Z F， Zhang S Z， Xi C，et al. Scaling up graph neural networks via graph coarsening∥Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. New York，NY，USA：Association for Computing Machinery，2021：675-684.

[23] Bacciu D， Conte A， Landolfi F. Generalizing downsampling from regular data to graphs. Proceedings of the AAAI Conference on Artificial Intelligence，2023，37(6)：6718-6727.

[24] Jin W， Zhao L X， Zhang S C，et al. Graph condensation for graph neural networks∥The 10th International Conference on Learning Represen⁃tations. Online：ICLR，2022：1-19.

[25] Jin W， Tang X F， Jiang H M，et al. Condensing graphs via one⁃step gradient matching∥Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. New York，NY，USA：Association for Computing Machinery，2022：720-730.

[26] Gao X Y， Yin H Z， Chen T，et al. RobGC：Towards robust graph condensation. IEEE Transactions on Knowledge and Data Engineering，2025，37(8)：4791-4804.

[27] Zheng X， Zhang M， Chen C Y，et al. Structure⁃free graph condensation：From large⁃scale graphs to condensed graph⁃free data. Advances in Neural Information Processing Systems，2023，36：6026-6047.

[28] Zhang Y C， Zhang T L， Wang K，et al. Navigating complexity∥Proceedings of the 41st International Conference on Machine Learning. Vienna，Austria：JMLR.org，2024：60379-60395.

[29] Liu Z Y， Zeng C L， Zheng G J. Graph data condensation via self⁃expressive graph structure reconstruction∥Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. New York，NY，USA：Association for Computing Machinery，2024：1992-2002.

[30] Wang L， Fan W Q， Li J T，et al. Fast graph condensation with structure⁃based neural tangent kernel∥Proceedings of the ACM Web Conference 2024. New York，NY，USA：Association for Computing Machinery，2024：4439-4448.

[31] Xu Z， Chen Y Z， Pan M H，et al. Kernel ridge regression⁃based graph dataset distillation∥Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. New York，NY，USA：Association for Computing Machinery，2023：2850-2861.

[32] Gao X Y， Chen T， Zhang W T，et al. Graph condensation for open⁃world graph learning∥Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. New York，NY，USA：Association for Computing Machinery，2024：851-862.

[33] Xiao Z B， Wang Y， Liu S Y，et al. Simple graph condensation∥Machine Learning and Knowledge Discovery in Databases. Research Track. Cham，Switzerland：Springer，2024：53-71.

[34] Gao X Y， Ye G H， Chen T，et al. Rethinking and accelerating graph condensation：A training⁃free approach with class partition∥Proceedings of the ACM on Web Conference 2025. New York，NY，USA：Association for Computing Machinery，2025：4359-4373.

[35] Wang X， Lan Z， He Y A，et al. A cost⁃effective approach for mining near⁃optimal top⁃k patterns. Expert Systems with Applications，2022，202：117262.

[36] Bringmann B， Nijssen S. What is frequent in a single graph?∥Advances in Knowledge Discovery and Data Mining. Heidelberg,Germany：Springer，2008：858-863.

[37] Rossi R A， Ahmed N K. The network data repository with interactive graph analytics and visualization∥Proceedings of the 29th AAAI Conference on Artificial Intelligence. Menlo Park，CA，USA：AAAI Press，2015：4292-4293.

[38] Yang J， Leskovec J. Defining and evaluating network communities based on ground⁃truth∥Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics. Beijing，China：Association for Computing Machinery，2012：1-8

[39] Talukder N， Zaki M J. A distributed approach for graph mining in massive networks. Data Mining and Knowledge Discovery，2016，30(5)：1024-1052.

[40] Rozemberczki B， Allen C， Sarkar R，et al. Multi⁃scale attributed node embedding. Journal of Complex Networks，2021，9(1)：1-22.

[41] Yin H， Benson A R， Leskovec J，et al. Local higher⁃order graph clustering∥Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York，NY，USA：Association for Computing Machinery，2017，2017：555-564.

[42] Lin M K， Li W Z， Lu S L. Balanced influence maximization in attributed social network based on sampling∥Proceedings of the 13th International Conference on Web Search and Data Mining. New York，NY，USA：Association for Computing Machinery，2020：375-383.

[43] Zhou Z G， Shi C， Shen X L，et al. Context⁃aware sampling of large networks via graph representation learning. IEEE Transactions on Visualization and Computer Graphics，2021，27(2)：1709-1719.

[44] Kiouche A E， Baste J， Haddad M，et al. Neighborhood⁃preserving graph sparsification. Proceedings of the VLDB Endowment，2024，17(13)：4853-4866.

[45] Dehmer M， Mowshowitz A. A history of graph entropy measures. Information Sciences，2011，181(1)：57-78.

基金资助

国家自然科学基金(62172102)