随着信息技术的不断发展，越来越多的研究者将包含多种对象类型且具有不同互连关系的网络数据建模为异质信息网络(heterogeneous information networks, HINs)^[1]，如互联网电影资料库(internet movie database, IMDB)^[2]. 相较于仅包含一种类型的对象和连接的同质信息网络，HINs蕴含了更加丰富的语义信息，能实现对现实世界更完整的抽象.

不同于通过社区发现^[3]获取网络中的所有社区，社区搜索^[4]的目标是在大型网络中针对用户给定的查询请求返回满足条件的社区，为用户提供个性化的服务. 目前，在HINs中，已经提出了使用(k, ${\mathcal{P}}$)-core^[5]、(k, ${\mathcal{P}}$)-truss^[6]之类的社区结构以及通过节点的关键字信息^[7-8]来查询社区的方法. 这些方法在应用于现实社会网络时存在局限性：一方面由于HINs中节点和边的异质性，现有的搜索方法难以处理用户复杂多样的搜索需求^[9]，如在IMDB网络中要求社区中的演员有合作关系且每个演员至少有k个电影类型的邻居^[10]. 另一方面，许多搜索方法只利用网络中的结构信息来度量节点间的相关性，忽略了HINs中语义信息和节点属性信息的影响，难以搜索出结构关系相对稀疏，但节点属性信息相似^[11]的社区. HINs信息的丰富性要求社区搜索方法不仅考虑结构信息，还要全面地抽取和利用网络的语义信息和属性特征来度量节点间的相关性.

针对HINs节点和边类型的多样性以及信息的丰富性特点，HINs中的社区搜索涉及几个问题：1）如何处理用户复杂多样的搜索要求；2）如何全面地提取HINs中的结构、语义和属性信息以有效地计算节点间的相关性.

元路径^[1]抽取了HINs的子结构，表达了多种对象间特定的语义关系，因此，针对问题1），本研究把每个搜索要求表示为一条元路径，并将其定义为查询约束，用于处理用户复杂多样的搜索要求.针对问题2），本研究利用互信息作为节点间融合网络结构和节点属性信息的相关性指标. 互信息(mutual information, MI)是衡量随机变量之间多维关系的综合度量，能够捕捉到变量间的非线性统计相关性^[10-13]，在社会网络分析中得到了应用，比如， CommDGI^[14](deep community graph infomax)模型在社区检测中利用互信息最大化范式度量社区互信息；异质深度图互信息最大化^[2] (heterogeneous deep graph infomax, HDGI)模型利用互信息融合网络结构和节点属性信息度量异质图局部与全局间的相关性. 基于CommDGI和HDGI的思想，本研究设计了应用于HINs的带查询约束的深度图互信息最大化(query constraint deep graph infomax, QC-DGI)模型，通过全面地提取HINs中的结构、语义和属性信息获得节点嵌入来计算节点间的互信息，同时使获得的节点嵌入包含查询约束的特征，有助于更精准地搜索出满足用户需求的社区.

互信息越大的节点间的相关性越高，同一社区中的节点间应具有较高的互信息. 因此，本研究提出异质信息网络的互信息最大化社区搜索问题，给出互信息最大化的社区定义，设计相应的社区搜索方法，互信息最大化社区搜索(community search with mutual information maximization, CSMIM)，根据给定的查询信息，利用QC-DGI模型和社区互信息最大化准则定位目标社区. 此外，社区搜索是一个过程化问题，在搜索社区过程中，用户可以根据每次搜索的结果进行调整，使搜索结果更加满足用户需求. 根据用户对社区的反馈，提出基于用户反馈训练局部互信息的交互式社区搜索优化策略，能更加精准地度量节点间的互信息，提高搜索结果的准确率.

定义1　 异质信息网络HINs^[1]. HINs定义为一个具有对象类型映射函数 $\varphi :V \to T$、关系类型映射函数 $\phi :E \to R$的图 $ G = (V,E,{\boldsymbol{X}}) $. 其中每一个对象 $v \in V$属于节点类型集合 $T:\varphi (v) \in T$中的一种特定对象类型，每一条链接 $e \in E$属于关系类型集合 $R:\phi (e) \in R$中的一种特定关系类型， ${\boldsymbol{X}}$为 $G$中的节点特征矩阵. HINs中对象类型和关系类型满足 $\left| T \right|+\left| R \right| > 2$，其中|T|、|R|分别为节点类型、边类型的数量. 如图1(a)所示为一个HINs实例.

定义2　网络模式^[5]. 网络模式是定义在节点类型集合 $T$和边类型集合 $R$上的一个有向图，记为 ${S_G} = ( T,R) $. 它是HINs的元描述，用于限定对象集合以及对象间关系的类型约束，这些约束使得HINs具有半结构化特点，引导网络语义的探究. 如图1(b)所示为图1(a)所示网络的网络模式.

定义3 　元路径^[1]. 元路径定义为在网络模式 ${S_G} = ( T,R) $上通过边类型序列 ${R_1},{R_2}, \cdots, {R_l}$连接的节点类型序列 ${T_1},{T_2}, \cdots, {T_{l+1}}$，表示为 $ {T_1}\mathop \to \limits^{{R_1}} {T_2}\mathop \to \limits^{{R_2}} \cdots \mathop \to \limits^{{R_l}} $ $ {T_{l+1}} $，其中， $l$为元路径长度. 在如图1所示的网络模式中，表示演员之间合作关系的元路径 $ A(演 $ $ 员)\to M(电影)\to A(演员) $，也可以表示为AMA，其中路径 ${a_0}$- ${m_0}$- ${a_1}$为元路径AMA的一条路径实例.

定义4 　 互信息^[12]. 给定2个随机变量 $X$和 $Y$，它们之间的互信息定义为

(1) $ { I}(X;Y) = H(X)+H(Y) - H(X,Y) = H(X) - H(X|Y). $

式中： $H(X)$和 $H(X|Y)$分别表示熵和条件熵， $H(X,Y)$表示 $X$和 $Y$联合分布的熵.

为了说明社区搜索问题的局限性和定义的合理性，以图1中的IMDB网络为例进行论述.

例1. 假设导演兼演员 ${a_4}$想要招募演员成立一个拍摄动作题材电影的团队，要求成员：1)至少演过2部电影；2)有合作参演其他电影的经历.

基于社区结构(k, ${\mathcal{P}}$)-core^[5]的方法无法同时处理上述2个需求. 现只考虑要求2），使用(k, ${\mathcal{P}}$)-core^[5]，其中k=2、元路径 ${\mathcal{P}}$为AMA的方法可以从图1中找到包含虚线框中节点的演员社区{ ${a_1},{a_2}, {a_3},{a_4}$}，演员间有紧密的结构关系. 但演员 ${a_1}$是一个喜剧型演员，与其他节点间的属性相似度并不高. 演员 ${a_5}$虽然与 ${a_2}、{a_3}$结构关系稀疏而不在社区中，但他与 ${a_4}$合作了2部相关性高的电影，并且 ${a_5}$与 ${a_4}$都是动作剧演员. 显然，相较于 ${a_1}$， ${a_4}$更希望 ${a_5}$加入团队，所以最终得到的结果社区应包含实线框中的节点. 对于此类结构凝聚性弱、节点属性相似性高的社区搜索，通过现有的异质网络社区搜索方法难以获得满意的解.

给定异质信息网络 $ G = (V,E,{\boldsymbol{X}}) $，查询节点 $q \in V$和用户的搜索要求，互信息最大化社区搜索旨在从 $G$中寻找包含查询节点且满足要求的社区 $C \subset V$，使得社区中的节点在网络结构和节点属性上紧密相关，即社区中节点间的互信息最大，并且社区中所有节点与查询节点 $q$的类型相同.

在HINs中，2个相邻节点可以通过不同类型的元路径连接. 元路径本质上抽取了HINs的子结构，体现了路径所包含的语义信息，因而成为HINs分析中的基本语义捕捉方法^[1]. 本研究将用户的搜索要求基于元路径概念定义为查询约束.

定义5　 查询约束. 查询约束是在网络模式上定义的基于特定约束的扩展元路径，可以表示为 $ {T_1}\mathop \to \limits^{{\delta _1}({R_1})} {T_2}\mathop \to \limits^{{\delta _2}({R_2})} \cdots \mathop \to \limits^{{\delta _L}({R_l})} {T_{l+1}} $. 如果关系 $R$在链接上具有约束值，则约束函数的函数值 $\delta (R)$是关系 $R$约束值范围内的一个取值集合；否则， $\delta (R)$为空集.

本研究将查询约束表示为 $\{ {\psi _1},{\psi _2}, \cdots ,{\psi _n}\} $，其中， ${\psi _i}$表示第i个查询约束. 例如，查询约束 $ A\mathop \to \limits^2 M $表示演员至少参演过2部电影. 此外，在基于查询约束考虑社区间节点邻近关系时，相邻节点间关系的连接紧密程度也不容忽视，即当通过元路径连接的节点u和v间有多条路径可达时，须考虑连接间的权重. 如例1中演员 ${a_4}$与 ${a_5}$合作了2部电影，即他们之间有 ${a_4}$- ${m_4}$- ${a_5}$和 ${a_4}$- ${m_5}$- ${a_5}$这2条元路径可达，则他们的关系紧密程度为2.

定义6　 基于查询约束的带权邻接矩阵. 若节点 ${v_i} \in {V_{\rm{t}}}$和 ${v_j} \in {V_{\rm{t}}}$之间存在查询约束 ${\psi _i}$，其中 ${V_{\rm{t}}}$为目标类型的节点集，则称 ${v_i}$和 ${v_j}$是基于 ${\psi _i}$的连通邻居. 此邻近关系信息可以表示为基于查询约束的带权邻接矩阵 $ {\boldsymbol{A}}_{\rm{w}}^{{\psi _i}} \in {{{\bf{R}}}^{\left| {{V_{\rm{t}}}} \right| \times \left| {{V_{\rm{t}}}} \right|}} $. 若节点 ${v_i}$和 ${v_j}$之间可以通过 ${\psi _i}$有n条路径可达，则 ${\boldsymbol{A}}_{\rm{w}}^{{\psi _i}}$的第 $(i,j)$和 $(j,i)$元素 $ A_{\rm{w}}^{{\psi _i}}(i,j) $和 $ A_{\rm{w}}^{{\psi _i}}(j,i) $均设置为 $n$，即 $ A_{\rm{w}}^{{\psi _i}}(i,j) = $ $ A_{\rm{w}}^{{\psi _i}}(j,i) = {n_{}}(n \geqslant 1) $，否则 $ A_{\rm{w}}^{{\psi _i}}(i,j) = A_{\rm{w}}^{{\psi _i}} (j,i) = 0$.

定义7　 $\Theta $-连通图. 根据查询约束集 $\{ {\psi _1},$ ${\psi _2}, \cdots ,{\psi _n}\} $，从异质信息网络 $ G= (V,E,{\boldsymbol{X}})$中抽取子图 ${G'}$，若 ${G'}$中所有节点均是基于某个查询约束的连通邻居，则称子图 ${G'}$为 $\Theta $-连通图. 如图2(a)、(b)所示均为 $\Theta $-连通图，其中(a)为满足查询约束AMA的 $\Theta $-连通图，(b)为期望得到的结果社区的生成子图，也是 $\Theta $-连通图，它满足查询约束AMA和 $A\mathop \to \limits^2 M$.

社区搜索是一个过程化问题，可以通过逐步加入节点定位结果社区^[11]. 比如，在例1中，若当前已经搜索出社区{ ${a_2},{a_3},{a_4}$}，可以通过从{ ${a_1},{a_5}$}中选出属于社区的节点加入当前社区来定位结果社区. 若每次都要与社区中每个节点计算互信息，将产生大量的计算，造成资源的浪费. 因此本研究把互信息的度量从节点与节点之间转换为节点与社区之间，即在社区搜索过程中，将度量待加入节点与当前社区中所有节点间的互信息，转换为度量待加入节点与当前社区之间的互信息，来获取结果社区，使得社区成员间的相关性最大. 一组数据的平均值能够反映这组数据的平均水平，平均值越大表明整体总和越大，因此本研究将社区成员与社区之间互信息的均值作为社区的互信息，引入社区互信息的概念来反映社区内节点的相关性，即社区互信息越大表明社区成员间的互信息总和越大、相关性越高. 此外，借鉴多维空间中几何中心的思想^[15]，采用社区内节点的向量均值作为社区的概要向量表示^[2]，以此反映整个社区的全局信息.

定义8　 社区互信息. 给定一个社区 $C$，社区的互信息定义为

(2) $ {{I} _{{{\rm{com}}}}}(C) = \frac{1}{{\left| C \right|}}\sum\nolimits_{u \in C} {{I} ({{\boldsymbol{h}}_u},{{\boldsymbol{s}}_C})} . $

式中： ${{\boldsymbol{h}}_u}$为社区成员 $u \in C$的低维向量表示， ${{\boldsymbol{s}}_C} = \sigma \left(\dfrac{1}{{\left| C \right|}}\displaystyle\sum\nolimits_{i = 1}^{\left| C \right|} {{{\boldsymbol{h}}_i}} \right)$为社区的概要向量表示^[2]，|C|为社区节点数.

定义9　 互信息最大化社区. 对于网络 $G = (V,E,{\boldsymbol{X}})$和社区互信息函数 ${{ I}_{{{\rm{com}}}}}$，给定查询节点 $q \in V$和社区大小约束 $n$，搜索集合 $C \subset V$使得：1) $q \in C$，并且子图 $G[C]$是一个 $\Theta $-连通图；2) $C = \mathop {\arg \max }\limits_{C \subset V}\; {{ I}_{{{\rm{com}}}}}(C)$，且 $\left| C \right| \geqslant n$.

条件1)要求查询顶点位于目标社区中，并且与基于(k, ${\mathcal{P}}$)-core算法对社区结构过于严格的约束不同，定义只要求社区 $G[C]$是 $\Theta $-连通图. 条件2)致力于找到一个互信息最大的社区，并对社区的规模进行限制，要求社区节点数不少于 $n$，用户可以根据搜索社区的质量调整 $n$. 这是因为搜索出的社区规模并不总能满足需求甚至会造成不必要的开销和资源浪费，此外有些应用程序或场合需要限制社区规模，例如组建一个至少有 $n$个人的团队.

CSMIM的基本框架如图3所示. CSMIM方法分为2个阶段. 在第1阶段完成HINs的表示学习，通过带查询约束的无监督节点嵌入模型QC-DGI来学习节点的低维向量表示. 在第2阶段，CSMIM首先基于学习到的节点低维向量表示计算互信息，然后使用社区互信息最大化搜索算法来定位包含查询节点的目标社区.

节点嵌入模型QC-DGI是一种通过最大化全局图和节点之间的互信息^[16]学习网络中节点低维向量表示^[17]的方法. 如图4所示为QC-DGI的整体框架，QC-DGI基于查询约束来分析HINs中涉及的结构和语义连接，利用图卷积模块和语义级注意机制来捕获融合多维度信息的节点表示.

在QC-DGI模型中，将异质信息网络 $G = (V,E,{\boldsymbol{X}})$的邻接矩阵 ${\boldsymbol{A}} \in {\{ 0,1\} ^{\left| V \right| \times \left| V \right|}}$(对于任意一对节点 ${v_i},{v_j} \in V$，若存在边 $({v_i},{v_j}) \in E$，则 $A(i,j) = 1$；否则 $A(i,j) = 0$)，和查询约束集 $ \{ {\psi _j}\} _{j = 1}^P $作为输入. 得到基于查询约束的带权邻接矩阵 ${\boldsymbol{A}}_{\rm{w}}^\psi $和节点特征矩阵 ${{\boldsymbol{X}}^\psi } = \{ {{\boldsymbol{x}}_1},{{\boldsymbol{x}}_2}, \cdots ,$ ${{\boldsymbol{x}}_N}\} $， $ {{\boldsymbol{x}}_i} \in {{{\bf{R}}}^{\left| {\boldsymbol{X}} \right|}},N = \left| {{V_{\rm{t}}}} \right| $. 并将这些节点看作正样本，将正样本腐蚀变换后的样本看作负样本，作为模型对比学习的参照样本. 基于查询约束的编码器根据每个带权邻接矩阵学习节点表示，然后通过语义注意机制融合，最大化正样本节点和图概要向量之间的互信息输出节点表示 ${\boldsymbol{H}}$.

为了捕获节点信息，基于查询约束的节点编码器具有2级结构. 首先，根据每个基于查询约束的带权邻接矩阵 ${\boldsymbol{A}}_{\rm{w}}^{{\psi _i}}(i = 1, \cdots ,P)$学习节点表示. 之后，所有基于 $\{ {\boldsymbol{A}}_{\rm{w}}^{{\psi _i}}\} _{i = 1}^P$的节点表示通过注意机制聚合.

在QC-DGI中，使用图卷积网络(graph convolutional network, GCN)^[18]作为获取节点嵌入的编码器组件 $\varepsilon $. 基于GCN学习到的节点表示为

(3) $ {{\boldsymbol{H}}^{{\psi _i}}} = \varepsilon ({{\boldsymbol{X}}^{{\psi _i}}},{\boldsymbol{A}}_{\rm{w}}^{{\psi _i}}) = ({{\hat{\boldsymbol B}}^{ - {1}/{2}}}{\hat{\boldsymbol A}}{{\hat{\boldsymbol B}}^{ - {1}/{2}}}){{\boldsymbol{X}}^{^{{\psi _i}}}}{{\boldsymbol{W}}_{\rm{f}}}. $

式中： ${\hat{\boldsymbol { A}}} = {\boldsymbol{ A}}_{\rm{w}}^{{\psi _i}}+{{\boldsymbol{I}}}$，I为单位矩阵，I∈R^N×N； ${\hat{\boldsymbol B}}$为对角矩阵；矩阵 ${{\boldsymbol{W}}_{\rm{f}}} \in {{\bf R}^{N \times \left| {\boldsymbol{X}} \right|}}$为滤波器参数矩阵.

通过学习可以获得基于查询约束的节点表示集 $\{ {{\boldsymbol{H}}^{{\psi _1}}},{{\boldsymbol{H}}^{{\psi _2}}}, \cdots ,{{\boldsymbol{H}}^{{\psi _P}}}\} $. 但基于查询约束学习的表示只包含特定的语义信息，为了聚合节点的更概括性的嵌入，须将这些嵌入结合起来. 实现这种结合的关键是探索每个查询约束对最终嵌入的贡献. 受异质图注意力网络(heterogeneous graph attention network, HAN^[19])的启发，本研究在模型中加入语义注意层 ${L_{{\text{att}}}}$，以了解每个查询约束应分配的权重：

(4) $ ( {Z^{{\psi _1}}},{Z^{{\psi _2}}}, \cdots ,{Z^{{\psi _P}}}) = {L_{{\text{att}}}}({{\boldsymbol{H}}^{{\psi _1}}},{{\boldsymbol{H}}^{{\psi _2}}}, \cdots ,{{\boldsymbol{H}}^{{\psi _P}}}). $

基于不同查询约束的表征的重要性将通过共享注意向量 ${\boldsymbol{a}} \in {{\bf R}^{\left| {\boldsymbol{X}} \right|}}$衡量. 查询约束 ${\psi _i}$的重要性为

(5) $ {e^{{\psi _i}}} = \frac{1}{N}\sum\limits_{j = 1}^N {\tanh \;\;({{\boldsymbol{a}}^{\rm{T}}} \cdot ({{\boldsymbol{W}}_{{{\rm{sem}}} }} {\boldsymbol{h}}_j^{{\psi _i}}+{\boldsymbol{b}}))} . $

式中： ${{\boldsymbol{W}}_{{\rm{sem}}}} \in {{\bf R}^{\left| {{{\boldsymbol{X}}{''}}} \right| \times \left| {{{\boldsymbol{X}}'}} \right|}}$为权重矩阵，a为共享注意向量， ${\boldsymbol{h}}_j^{\psi_i} $为 ${\boldsymbol{H}}^{\psi_i} $的第j行向量， ${\boldsymbol{b}}$为偏差向量. 使用softmax函数对查询约束的重要性规范化：

(6) $ {Z^{{\psi _i}}} = {{\rm{softmax}}} \;({e^{{\psi _i}}}) = \frac{{\exp\; ({e^{{\psi _i}}})}}{{\displaystyle\sum\nolimits_{j = 1}^P {\exp \;({e^{{\psi _j}}})} }}. $

使用不同查询约束的权重作为嵌入聚合的线性组合系数，以得到最终的局部特征：

(7) $ {\boldsymbol{H}} = \sum\limits_{i = 1}^P {{Z^{{\psi _i}}} {{\boldsymbol{H}}^{{\psi _i}}}} . $

QC-DGI的学习目标是最大化局部表示和全局表示之间的互信息^[16]. ${\boldsymbol{H}}$为节点的局部表示，需要读出函数 ${{\rm{Readout}}}$将节点表示汇总为概要向量来表示整个图的全局信息. 利用平均算子作为编码器函数，取节点表示的平均值，即可输出图级概要向量：

(8) $ {{\boldsymbol{s}}_G} = {{\rm{Readout}}}\; ({\boldsymbol{H}}) = \sigma \left(\frac{1}{N}\sum\limits_{i = 1}^N {{{\boldsymbol{h}}_i}} \right). $

负样本的生成会影响模型捕获的结构信息，因此需要高质量的负样本精确地保留结构信息，敦促学习的节点表示更好地捕捉图中不同节点的结构相似性. 负样本 $ {\boldsymbol{\tilde X}} $可以根据腐蚀函数 $ \mathcal{C} $对正样本 ${\boldsymbol{X}}$变换得到，即

(9) $ ({\boldsymbol{\tilde X}},\{ {\boldsymbol{A}}_{\rm{w}}^{{\psi _1}},{\boldsymbol{A}}_{\rm{w}}^{{\psi _2}}, \cdots ,{\boldsymbol{A}}_{\rm{w}}^{{\psi _P}}\} ) = {\mathcal{C}}({\boldsymbol{X}},\{ {\boldsymbol{A}}_{\rm{w}}^{{\psi _1}},{\boldsymbol{A}}_{\rm{w}}^{{\psi _2}}, \cdots ,{\boldsymbol{A}}_{\rm{w}}^{{\psi _P}}\} ). $

在变换过程中，保持负样本邻接矩阵 ${\boldsymbol{A}}_{\rm{w}}^\psi $与原始邻接矩阵相同，可以使 $G$的整体结构稳定，而负采样特征矩阵 ${\boldsymbol{\tilde X}}$通过原始特征矩阵 ${\boldsymbol{X}}$随机混洗获得. 根据互信息神经估计^[12]中的证明，互信息可以通过神经网络的梯度下降法来估计. 本研究通过训练鉴别器 $ {D} $估计互信息来区分 $({{\boldsymbol{h}}_i},{{\boldsymbol{s}}_G})$和 $({{\boldsymbol{\tilde h}}_j},{{\boldsymbol{s}}_G})$. 鉴别器 $ {D} $为二元分类器，表达式如下：

(10) $ {D} ({{\boldsymbol{h}}_i},{{\boldsymbol{s}}_G}) = \sigma ({{\boldsymbol{h}}_i}^{\rm{T}}{{\boldsymbol{W}}_G}{{\boldsymbol{s}}_G}). $

式中：W_G为图级互信息最大化的参数矩阵.

根据Jensen-Shannon散度和互信息之间的关系^[16]，可以利用鉴别器的二进制交叉熵损失最大化互信息：

(11) $ \begin{split} {L} =\;& \frac{1}{{2N}}\left( {\sum\limits_{i = 1}^N {{E}[\ln\; {D} ({{\boldsymbol{h}}_i},{{\boldsymbol{s}}_G})]} }+ \right.\\ &\left. {\sum\limits_{i = 1}^N {{E}[\ln\; (1 - {D} ({{{\boldsymbol{\tilde h}}}_i},{{\boldsymbol{s}}_G}))]} } \right). \end{split} $

基于QC-DGI学习到的节点嵌入，计算候选节点与当前社区之间的互信息，并提出一个基于互信息最大化的社区搜索算法(mutual information maximum, MI-MAX).

利用互信息神经估计^[12]能够有效地计算深度神经网络的高维输入/输出对之间的互信息. 这种估计依赖于将统计网络训练为来自2个随机变量及其边缘乘积的联合分布的样本分类器，即高维连续随机变量之间相互信息的估计可以通过神经网络的梯度下降法实现. 因此，在将节点映射到低维向量空间后，可以通过节点间的互信息来测量节点间的相关性. 受HDGI模型基于鉴别器估计互信息的启发，本研究使用互信息估计器-鉴别器^[15]来计算互信息. 因此，式（2）中节点 $u$与当前社区 $C$的互信息计算方式可以等价为

(12) $ {I} ({{\boldsymbol{h}}_u},{{\boldsymbol{s}}_C}) = {{\boldsymbol{h}}_u}^{\rm{T}}{{\boldsymbol{W}}_G}{{\boldsymbol{s}}_C}, $

则 ${{I} _{{{\rm{com}}} }}(C) = \dfrac{1}{{\left| C \right|}}\displaystyle\sum\nolimits_{u \in C} {{I} ({{\boldsymbol{h}}_u},{{\boldsymbol{s}}_C})} = \dfrac{1}{{\left| C \right|}}\displaystyle\sum\nolimits_{u \in C} {{{\boldsymbol{h}}_u}^{\rm{T}}{{\boldsymbol{W}}_G}{{\boldsymbol{s}}_C}}$.

利用互信息指标衡量节点是否属于社区，融合节点属性、网络结构和语义信息推断社区中成员的相关性，如果节点属于社区，节点特征与社区特征应尽可能相似，即该节点与社区中节点的互信息应尽可能高. 在社区搜索中，首先根据查询约束集生成满足需求的 $\Theta $-连通图. 基于 $\Theta $-连通图，通过优先选择外壳节点集 $N = \{ u|v \in D,u \notin D$， $A_{\rm{w}}^\psi (u,v) \geqslant 1\} $（也称候选节点集，即下一步最有可能进入社区的节点集合，要求该节点集中每个节点至少有一个邻居节点在当前社区中）中与当前社区互信息最大的节点加入社区来获得目标社区. 算法详细描述如下.

算法1　MI-MAX

输入:异质信息网络 $G = (V,E,{\boldsymbol{X}})$的 $\Theta $-连通图和节点嵌入 ${\boldsymbol{H}}$，查询节点 $q$，社区大小约束 $n$

输出：包含节点 $q$的最大互信息社区 $C$

1. 　初始化 $C = \{ q\} ,N = \{ u|u \notin C,A_{\rm{w}}^\psi (q,u) \geqslant 1\} $；

2. 　while $N$ is not NULL do

3. 　　 ${{\boldsymbol{s}}_C} = {{\rm{Readout}}} (C)$; //计算社区的概要向量

4. 　　for each $u \in N$

5. 　　　 ${\rm{MI}}[u] = {I}\left( {{{\boldsymbol{h}}_u},{{\boldsymbol{s}}_C}} \right)$; //计算 $u$与当前社区 $C$的互信息

6. 　　end for

7. 　　find $v$ such that $ {\rm{MI}}[v] $ is maximum;

8. 　　if $\left| C \right| < = n$ or ${{ I}_{{\rm{com}}}}(C \cup v) > = {{ I}_{{\rm{com}}}}\left( C \right)$ then

9. 　　　add $v$ to $C$ and update $N$;

10. 　　else

11. 　　　break;

12. 　　end if

13. 　end while

14. 　return $C$.

在算法1中，首先初始化目标社区 $C = \{ q\} $，外壳节点集 $N = \{ u|u \notin C,A_{\rm{w}}^\psi (q,u) \geqslant 1\} $(第1行)，通过迭代添加外壳节点集合中与当前社区 $C$的互信息最大的节点 $v \in N$来扩展社区 $C$，直到其节点数达到 $k$或社区互信息不再增大（第2~13行），最后返回社区 $C$（第14行）. 算法的时间复杂度为 $O({\left| V \right|^2} \times \log_2\; (\left| V \right|)+{\left| V \right|^2})$，其中 $\left| V \right|$为节点数. 具体来说，首先最外层while循环从外壳节点中找出加入社区的节点需要 $O(\left| V \right|)$，然后计算外壳节点中每个节点与当前社区的互信息(第5~6行)需要 $O(\left| V \right|)$，找互信息最大的节点(第8行)需要 $O(\left| V \right| \cdot \log_2\; (\left| V \right|))$.

通常，社区搜索是一个逐步优化的过程，用户可以根据每次定位的结果进行调整. 为了使搜索结果更加精准，本研究设计了异质信息网络的用户交互式互信息最大化社区搜索方法(interactive community search with mutual information maximization, ICSMIM)，其基本框架如图5所示. ICSMIM搜索通过多轮迭代完成. 第1轮依据CSMIM方法定位社区，用户可以依据定位的社区标记出希望在社区中或不在社区中的节点，生成标记节点集，基于标记节点集指导下一轮的训练和搜索；接下来的每一轮，根据用户反馈，ICSMIM都会通过训练一个有监督的鉴别器 ${{D} _{{\rm M}{\rm I}}}$估计社区互信息，直至定位出用户满意的社区.

在CSMIM中，通过使用模型QC-DGI训练的鉴别器 $ {D} $和节点表示来计算互信息，但训练出的鉴别器 $ {D} $是估计节点与图之间的互信息，此时 $ {D} $中的 ${{\boldsymbol{W}}_G}$是图级互信息最大化的参数矩阵，并没有充分考虑到社区内部的关系. 本研究加入基于用户指导的有监督鉴别器 ${{D} _{{\rm M}{\rm I}}}$，根据标记节点集指导鉴别器训练，来更加精准地度量节点间的互信息. 鉴别器 $ {{D} _{{\rm M}{\rm I}}} $是二元分类器，表达式如下：

(13) $ {{D} _{{\rm M}{\rm I}}}({{\boldsymbol{h}}_i},{{\boldsymbol{h}}_q}) = \sigma ({{\boldsymbol{h}}_i}^{\rm{T}}{{\boldsymbol{W}}_C}{{\boldsymbol{h}}_q}). $

式中：W_C为社区级互信息最大化的参数矩阵.

利用鉴别器的二进制交叉熵设计损失函数，最大化标签节点集中希望在社区中的节点与查询节点q之间的局部互信息，使得网络中与希望在社区中节点相似的节点和查询节点q之间的互信息尽量大，而与不希望在社区中节点相似的节点和q之间的互信息尽量小.

(14) $ \begin{split} {{L} _{{\rm{com}}}} =\;& \sum\limits_{u \in L} {y_u \times \ln \;({{D} _{{\rm M}{\rm I}}}({{\boldsymbol{h}}_u},{{\boldsymbol{h}}_q}))}+ \\ & {(1 - y_u) \times \ln\; (1 - {{D} _{{\rm M}{\rm I}}}({{\boldsymbol{h}}_u},{{\boldsymbol{h}}_q}))} . \end{split} $

式中： $L$为用户反馈的标签节点集， $y_u$为标签集中节点 $u$的标签.

基于鉴别器 ${{D} _{{{\rm{MI}}} }}$，社区互信息的计算方式可以等价为

(15) $ {{ I}_{{\rm{com}}}}(C) = \frac{1}{{\left| C \right|}}\sum\nolimits_{u \in C} {{{\boldsymbol{h}}_u}^{\rm{T}}{{\boldsymbol{W}}_C}{{\boldsymbol{s}}_C}} . $

在ICSMIM中，互信息的度量从全局细化到了局部，通过训练最大化用户标记的节点与初始查询节点 $q$之间的互信息，使得与 $q$在同一真实社区中的节点或用户希望出现在社区中的节点和 $q$相关性更高. 根据改进的互信息计算方法，利用算法1即可重新定位出更加满足实际需求的社区.

1）数据集. 在3个真实HINs中进行实验. 数据集详细描述如表1所示. 表中，N_n、N_e、N_f分别为节点数、边数、特征数. ACM数据集^[19]包含了在KDD、SIGMOD、SIGCOMM和VLDB上发表的论文记录，节点类型包括论文、作者和主题；IMDB数据集^[2]是一个关于电影的知识图表，节点类型包括演员、导演、电影和关键字；DBLP数据集^[5]包括计算机科学领域的出版记录，节点类型包括作者、论文、地点和主题.

2）对比方法. 与2种社区搜索方法进行比较，包括基于图神经网络训练得分的交互式社区搜索方法(interactive community search via graph neural network, ICS-GNN^[11])和基于社区结构(k, ${\mathcal{P}}$)-core的社区搜索方法FastBCore^[5].

ICS-GNN^[11]是一个基于图神经网络的交互式社区搜索方法. 此方法用子图上训练的图神经网络推断节点分数，然后以用户交互的方式发现目标社区. 由于ICSMIM是一个交互式的互信息最大化社区搜索方法，本研究通过与ICS-GNN对比，以验证在交互式社区搜索中，以互信息作为度量节点间融合网络结构和节点属性的相关性指标的有效性. 但ICS-GNN是应用于同质信息网络的方法，为了能与其对比，在实验中根据查询约束生成的邻接矩阵来构造同质图，基于此同质图来搜索社区.

FastBCore^[5]是一个基于社区结构(k, ${\mathcal{P}}$)-core的社区搜索方法. 该方法基于元路径，通过寻找满足节点度大于k且结构连接紧密的节点来获取社区. 通过与FastBCore比较，以验证社区搜索中综合度量网络结构和节点属性的有效性.

3）评价指标. 为了测量通过不同方法发现的社区质量，采用了4种测量方法.

(a)局部模块度^[20]（modularity）. 用于量化社区紧密性，即社区结构的内聚度，社区的局部模块度越高表明社区结构越内聚.

(b)社区相似度^[5]（PathSim）. 采用PathSim度量社区成员间的结构相似度，社区的PathSim越大表明社区的结构相似度越高.

(c)精确度^[5]（precision）. 用于度量搜索出的社区的准确率，衡量结果社区与真实社区之间的差异性，精确度越高表明结果社区与真实社区越接近.

(d)社区互信息（MI）. 用于度量社区成员间融合网络结构、语义信息和节点属性信息的相关性.

4）实现细节. 模型QC-DGI中将节点表示的维度设置为512， ${\boldsymbol{a}}$的维度设置为8，迭代次数设置为10000，学习率为0.001；在社区搜索算法中，社区大小约束设置为30，并且为了保证对比结果的稳定性和客观性，不同的方法通过同一组查询节点搜索社区，取这组社区中各指标的均值作为最终结果. 此外，为了更加客观地验证性能，在与FastBCore的对比实验中，在2~10逐一尝试k值，寻找各数据集中效果最好的k作为FastBCore算法(k, ${\mathcal{P}}$)-core的k. 本研究实验所用机器的CPU是Inter Xeon E5-2660 v2 @ 2.20 GHz，内存32 GB，2400 GHz DDR，硬盘容量1 TB，显卡1050 ti 4 GB，并用Python-3.8.12实现各个算法.

通过一个案例分析来验证CSMIM方法能够较好地应对用户复杂多样的社区搜索要求，根据在不同查询约束下得到的搜索结果验证方法的有效性，对比方法为FastBCore^[5].

社区搜索结果如表2所示，每一行的内容表示在不同的查询约束条件下的搜索结果，其中涉及3个查询约束集（AMA；AMA和 $A\mathop \to \limits^2 M$；AMA、AMDMA、AMKMA和 $A\mathop \to \limits^2 M$），在不同的查询约束条件下查询节点 $q$和社区大小相同，即 $q = $“演员Fionnula F”，社区大小约束为30，搜索数据集为IMDB，设置FastBCore算法的 $k = 6$. 从搜索结果可以看出，CSMIM方法在不同的查询约束下都能找到演员类型的节点社区，而FastBCore算法只支持搜索条件为对称元路径，所以当查询约束涉及多个或不对称时，FastBCore对应的结果社区为空.

当查询约束为AMA时，FastBCore算法对应的搜索结果几乎包含CSMIM的搜索结果，表明在同等条件下，CSMIM可以找出与FastBCore算法相似甚至更加精确的结果，该结果验证了CSMIM方法的有效性. 针对例1，成立一个演员小组，查询约束为AMA， $A\mathop \to \limits^2 M$，CSMIM的搜索结果淘汰了不满足 $A\mathop \to \limits^2 M$的演员，如James E，表明CSMIM可以应对多个和不对称的查询约束. 为了使得搜索结果更加准确，在成立演员小组的过程中，在考虑合作关系的同时考虑演员参演的电影类型和导演，设置查询约束为AMA、AMDMA、AMKMA、 $A\mathop \to \limits^2 M$. 由于查询节点Fionnula F参演了4部电影，且电影类型为动作、悬疑、谋杀和喜剧，在结果社区中淘汰了诸如A.J. Buckley、Frances F 和Kim D等虽然与查询节点有合作关系，但参演电影类型不同于查询节点的演员. 加入了演员Dennis Q、Xzibit 和Toby J等，他们参演过多部电影，且这些电影的导演拍摄过多部与查询节点相同类型的电影. 可以看到此查询约束条件下的搜索结果相较于只考虑合作关系的结果更为合理.

为了评估ICSMIM的效率，测试不同方法之间的查询效率. 如图6所示为所有数据集上的搜索时间t. 可以看出，在社区搜索问题中，ICSMIM的平均查询时间远低于其他方法的.

为了解决异质信息网络的互信息最大化搜索问题，提出社区搜索方法CSMIM以及改进方法ICSMIM. 如图7所示为改进前、后的方法在社区搜索任务上的性能. 图中，Mod为结果社区的局部模块度，Pre为准确率，PS为结构相似度，MI为互信息，ACM、DBLP、IMDB为数据集，且各指标的数值是对2种算法进行30轮社区搜索后取得的均值. 可以发现，与只考虑全局网络互信息的方法CSMIM不同，在加入了用户的反馈和社区互信息的训练后，ICSMIM的社区搜索性能得到了很大的改进，搜索出的结果社区的各个指标都有所提升.

如表3所示为在3个数据集上利用不同方法搜索出的结果社区在局部模块度、准确率、结构相似度和互信息指标上的比较结果. 与其他方法相比，ICSMIM在所有数据集上都表现出色. 与ICS-GNN相比每个指标都有显著提高，这是因为当互信息在重建表示中起到重要作用时，嵌入模型可以捕获更多的全局结构信息和节点属性特征，而基于监督损失的GNN过分强调直接近邻^[18]；另一方面，这也表明基于同质信息网络的方法直接应用到异质信息网络中的局限性，尽管实验中ICS-GNN是基于异质信息网络生成的同质网络搜索社区，但仍会忽略网络的异质性信息. 与FastBCore相比，虽然FastBCore搜索出的社区模块度和结构相似度更高，但FastBCore简化了异质性社区搜索问题，只考虑了顶点的度和结构凝聚性，完全忽略了图形中的语义信息和节点的属性相似度，因此在社区精确度上远低于ICSMIM.

如图8(a)~(d)所示为3个数据集上不同社区大小S_com的各指标结果. 可以看出，随着社区大小不断增加，各指标的值呈现出降低的趋势，社区越大，准确率之类的指标越可能减低，因此对于不同的应用背景应该按照需求合理定义社区大小.

为了验证QC-DGI模型的性能，在ICSMIM方法中用以下模型替换QC-DGI，根据搜索出的社区的精确度、模块度、相似度和互信息来分析模型.

1）DGI^[15]. 深度图互信息最大化(deep graph infomax)为面向同质信息网络的无监督学习模型，为了能与其对比，在实验中，从查询约束生成的邻接矩阵来构造同质图，基于此图来学习节点表示.

2）HDGI^[2]. 面向HINs的无监督学习模型，HDGI是利用图卷积网络捕捉局部表示的方法.

3）HGAT^[2]. 面向HINs的基于互信息的无监督学习模型，是HDGI的变体，与HDGI不同的是，HGAT利用注意力机制学习局部表征.

4）HAN^[19]. 面向HINs的有监督学习模型，用语义注意力机制从元路径中捕获节点信息.

如图9(a)~(d)所示为3个数据集上用不同模型搜索出的社区的各指标结果. 可以观察到QC-DGI优于其他模型. 首先，QC-DGI优于只考虑元路径的HDGI，表明在社区搜索任务中，考虑内容特征和约束信息更有利于互信息的度量和搜索出满足要求的社区. 与方法DGI相比，QC-DGI的性能也更好，这证明了HINs中的语义信息非常重要，不能直接忽略. QC-DGI还优于针对异质信息网络设计的监督模型HAN，原因是HAN在学习表征的过程中没有训练互信息最大化的过程，表明互信息能够很好地度量异质信息网络节点间的相关性. 从QC-DGI和HGAT之间的比较来看，QC-DGI有更好的性能，这是因为图注意力机制严格限于节点的直接邻域，考虑层次依赖性的图卷积比图注意力机制能看得更远.

为了验证搜索算法MI-MAX的有效性，在ICSMIM方法中，用以下搜索算法定位社区，并从社区的精确度之类的各个指标来分析搜索算法.

1）BFS-only. 只考虑结构信息，利用广度优先搜索(breadth first search，BFS)算法搜索社区.

2）MI-MAX. 本研究所提算法1.

3）BFS-MI(breadth first search-mutual inform- ation). 先利用广度优先策略搜索社区，然后从候选节点集中选择与社区的互信息较大的节点交换出社区内与社区的互信息较小的节点，逐步提高社区互信息，同时保持社区的连通性的改进算法.

如图10(a)~(d)所示为3个数据集上用不同搜索算法搜索出的社区的各指标结果. 可以看出，MI-MAX在社区精确度上取得了最佳性能. BFS-only搜索出的社区结构内聚，但社区精确低，表明只考虑结构特征是不够的. BFS-MI搜索出的社区各指标都取了折中，在对精确度影响较小的情况下，有效地缓解了算法MAX-MI结构相关性弱的问题.

本研究提出互信息最大化社区搜索方法来支持异质信息网络中的社区搜索. 从定义合理的社区出发，通过QC-DGI模型融合HINs的网络结构、语义信息和节点属性学习节点表示来计算互信息，并设计能高效、精确地搜索目标社区的算法. 其次，引入了交互式框架来优化社区搜索，能根据用户的反馈，更加精准地度量节点间的互信息，使得结构社区适应不同的用户需求，提高社区搜索结果的准确度. 在3个真实数据集上进行大量的实验，实验结果表明，基于互信息最大化原理的社区搜索方法在时间开销和社区结果上具有优势. 作为利用互信息最大化原理搜索社区的方法，CSMIM为社区搜索提供了一种很有前途的解决方案.

目前，异质信息网络的社区搜索问题还处在一个探索的阶段，如何利用互信息原理，解决搜索节点类型与目标社区节点类型不一致的问题是下一步须研究的方向，如例1中根据导演或关键性类型节点搜索出一个演员类型社区. 另外，目前大多数的异质信息网络社区方法只能搜索出节点类型相同的同质社区，在异质信息网络研究工作中，社区的异质性也不能忽视，搜索出包含多种节点类型的异质社区同样是一个值得研究的问题.