图或者网络可以对现实世界普遍存在的实体、关系、属性进行建模,构成属性网络。随着信息技术的发展,各种网站、桌面软件、手机应用、传感器产生了大量属性网络数据,如人们熟知的社交网络数据,物联网数据等,为相关研究提供了丰富的数据资源。属性网络的模式发现被广泛用于传染病爆发预测、道路拥堵检测、网络入侵检测等领域。现有网络模式发现的研究多关注单一网络或网络结构方面,而本文将研究重点聚焦于属性依存网络,即多个存在相互联系的属性网络。属性依存网络上的模式发现问题一般搜索空间规模庞大,计算复杂度高,是指数量级的,而且该类问题通常带有结构约束,优化求解困难,其中有些问题已被证明是NPhard难题。如何在对问题进行有效建模的情况下,进行带结构约束的优化求解是解决此类问题的核心难点。现有方法或者是启发式的,求解结果质量无法保证,或者算法的可扩展性有待提高,或者为了方便求解,简化了问题的建模方式与约束条件,这些都限制了相关应用领域的发展。本文基于结构化稀疏优化理论,将属性依存网络的模式发现形式化为图的块结构优化问题,并分别针对动态属性网络、网络的网络以及对偶属性网络提出了相应的优化方法,可以较好地应对上述挑战。本文的主要研究工作如下:1.针对动态属性网络,本文提出了图的块结构迭代硬阈值法GB-IHT。动态属性网络是指网络结构不变,属性随时间演化的网络。该算法基于投影梯度下降的思想,将动态属性网络的模式发现问题形式化为在每一时刻网络上施加结构约束的连续优化问题,并利用高效的近似投影算法解决结构约束问题,在梯度更新与近似投影操作交替迭代过程中,实现目标函数的优化。本文从理论角度证明了该方法的收敛性,同时证明算法的时间复杂度是近线性的,较原始指数级的问题搜索规模大幅下降。在模拟与真实数据集上的异常连通子图发现实验表明,该方法的性能优于基准算法,证明了方法的有效性。2.针对网络的网络,本文提出了图的块结构优化算法GB-Opt。该方法扩展了动态属性网络的优化算法,可以处理多个结构与属性不同的网络组成的属性依存网络,即网络的网络。该方法基于结构化稀疏优化思想,在求解过程中将原始问题分解为较易解决的结构约束投影问题和结构约束无关的优化问题,降低了问题求解的难度。可以从理论上证明,GB-Opt算法具有收敛性保证与近线性的时间复杂度。为了加快问题的求解,提升方法的可扩展性,本文也设计了基于块坐标优化的算法并行加速实现方案。鉴于该算法的通用性,本文将其应用在动态属性网络与网络的网络的异常连通子图发现问题上。相关实验结果表明,该算法的性能优于基准算法,可以高效地求解相关问题。3.针对对偶属性网络,本文提出了相应的块结构优化方法Dual-Opt。对偶属性网络是指共享节点子集,而关系不同的两个属性网络。该类网络数据的优化问题一般要求对两个网络施加不同的结构约束,这是该类问题的难点之一。本文旨在发现对偶属性网络上的连通稠密子图。为满足图密度条件,文中设计了相关的图密度约束投影算法,进而构建可以满足连通性与图密度约束的对偶属性网络优化方法。本文算法考虑了节点属性与不同类型的结构约束,可以发现在一个网络上连通而在另一个网络上稠密且属性重要的节点子集。在模拟与真实数据集上的相关实验表明,本文方法可以发现较其他方法更有意义的模式,证明了其有效性。