Graph Block-structured Optimization And Its Applications

Graphs or networks can model ubiquitous entities,relationships and attributes in the real world,which constitute attributed networks.With the development of information technology,various websites,softwares,mobile apps and sensors have generated a large amount of attributed network data,e.g.,well-known data from social networks,the internet of things and others,which provide rich data resources for related studies.Pattern discovery in attributed networks can be used for disease outbreak prediction,congestion detection in road networks,intrusion detection in cyberspace,and many other applications.Most existing studies focus on a single network or structural properties of networks,while this dissertation concentrates on attributed interdependent networks,which consist of multiple attributed networks with connections.The problem of pattern discovery in attributed interdependent networks usually involves a huge search space and great computational complexity that is exponential.And the problem often requires some structural constraints that are hard to solve,some of which have been proven NP-hard.The core difficulty in solving the problem is how to optimize it with structural constraints when it has been modeled effectively.Some of the existing methods are heuristic and can not guarantee the quality of results and others have a problem with scalability.There are also some methods that simplify the way of modeling the problem and constraints to facilitate the solution.All of these compromises impede the progress in applications.This dissertation innovatively formulates pattern discovery in attributed interdependent networks as a graph block-structured optimization problem based on structured sparse optimization.The optimization methods for dynamic attributed networks,a network of networks and dual attributed networks are presented respectively,which can deal with the abovementioned challenges.The main contributions of this dissertation are as follows:1.For dynamic attributed networks,a method named Graph Block-structured Iterative Hard Thresholding(GB-IHT)is proposed.Dynamic attributed networks refer to those networks whose structures are static while their attributes evolve.The method GB-IHT leverages the projected gradient descent and formulates pattern discovery in dynamic attributed networks as a continuous optimization problem subject to structural constraints at each time slot,in which the structural constrained problem is solved by efficient approximate projections.The objective value can be gradually optimized in the alternation of iterative gradient updates and approximate projections.It is proven that the method has a theoretical guarantee on the convergence and its time complexity is nearly linear,which is dramatically reduced compared with the original exponential search space.The experiments on synthetic and real-world datasets demonstrate that the proposed method performs superior over baselines,which validates its effectiveness.2.For a network of networks,a method named Graph Block-structured Optimization(GB-Opt)is proposed.The method is an extension of GB-IHT for dynamic attributed networks,which can handle attributed interdependent networks composed of multiple networks with different structures and attributes,i.e.,a network of networks.The algorithm leverages structured sparse optimization,in which the original problem is decomposed into two sub-problems that are easier to solve,including the projection problem of structural constraints and the optimization problem independent of structural constraints.It is proven theoretically that the GB-Opt algorithm has a guarantee on the convergence and a nearly linear time complexity.In order to accelerate the solving of the problem and improve the scalability,a parallel accelerated implementation based on block coordinate optimization for the method is also devised.Because of the algorithm's universality,it is applied to anomalous connected subgraph detection in dynamic attributed networks and a network of networks.The experimental results show that the proposed method outperforms baselines and can solve related problems efficiently.3.For dual attributed networks,a method named Dual-Opt for block-structured optimization is proposed.Dual attributed networks are those networks that have two attributed networks with the same nodes but different edges.The optimization problem in dual attributed networks usually requires different structural constraints on those two networks,which is one of the difficulties in this problem.This dissertation aims at detecting connected dense subgraphs in dual attributed networks.A specific algorithm for density projection is devised to satisfy graph density constraints and then an optimization method for dual attributed networks is proposed,which can satisfy connectivity and density constraints.The method can model attributes on nodes and satisfy different types of structural constraints,which can detect significant nodes that are connected in one network and dense in another network.The experiments on synthetic and real-world datasets demonstrate that the proposed method can discover more meaningful patterns than baselines,which proves its effectiveness.