Research On Coalition Detection Methods Based On K-clique Skeleton For Brain Networks

The human brain is a huge and widely connected complex system which composed of billions of neurons and trillions of synapses bearing neural interaction and information trans-mission.Uncovering the system through machine learning methods is an effective way for understanding brain mechanism.Brain functional networks are collections of regions of interest(ROIs)in widespread brain regions showing functional connectivity as revealed through neuroimaging of the living brain such as through using the functional magnetic resonance imaging(f MRI)blood oxygen level dependent(BOLD)signal.It is well known that cognitive function emerges through cooperation between specific ROIs.These ROIs are grouped into self-organized coalitions.Mining such functional connectivity patterns from brain functional networks is potentially very useful in uncovering the working mechanisms of the human brain and may provide new ideas that are complementary to the intelligence-based algorithms in AI research.However,determining these raises well-known problems:First,traditional community de-tection algorithms are not useful for brain functional networks.The obtained communities can not satisfy coalitions.It is mainly because some technical challenges such as imbalance,hard sample and noise that lead the algorithms fall into community disorder problems.However,the algorithms work on brain functional networks always suffer from high complexity problems.Especially for the k-clique-based algorithms,the implementation process is complex that can not be used to detect large-scale coalitions.In addition,manual labeling of ROIs is generally expensive.By determining k-clique skeleton as training data,semi-supervised learning models can detect whole-brain coalitions in a label-free way.But for k-clique training data,a low label rate in available training data always leads models to over-fitting that suffer from the limitations of incomplete attribute learning,insufficient structure capture,and the inability to distinguish between node attribute and graph structure.The models can not effectively learn node represen-tation that not to exactly predict function classification for the unlabeled ROIs.Focusing on the above difficulties,this thesis conducts a thorough study on the problem of coalition detection in brain functional networks.k-Clique is determined as the fundamental element to network reconstruction.Based on the kernel representation,intrinsic robustness and overlap decomposition features,a network analysis theorem by skeleton of k-clique pattern has been proposed in which the skeleton,as the stable support of coalition,is detected though the technologies of self-adaptive estimation and spanning tree cutting.A mixture learning frame-work is also introduced for whole-brain coalition detection.The main contents are as follows:Focusing on the imbalance,hard-sample and noise problems,we propose novel self-adaptive skeleton approaches to detect coalitions from brain functional networks.The nodes in the network are characterized in terms of robust k-order complete subgraphs(k-clique)as essential substructures.k-clique as a kind of substructure,possess some perfect local property,the k nodes in the k-clique have a strong connection with each other.There is a large possi-bility of forming k-clique within a coalition due to high connectivity among its nodes.On the other hand,outside of the coalition,there exists relatively lower connectivity and subsequently less probability of a k-clique arising.Outliers do not survive in a k-clique due to their weak connectivity,which suggests that k-cliques are robust to the outlier problem.All k-cliques of the given network are quickly enumerated in a parallel manner using the k-clique enumeration algorithm.This is a recursive backtracking method that recursively searches nodes to form a k-clique and backtracks to update the search strategy.Then the cliques with each order k,from max-clique down to min-clique,are hierarchically embedded into our probabilistic mixture mod-els.They are self-adapted to the corresponding structural density of coalitions through different order k.In the initial merging stage,the connected max-cliques first tie together to form origi-nal skeletons.Then our probabilistic mixture model evolves to a second merging stage and the k-cliques not connected to the previous skeletons form a new skeleton.All the k-cliques are merged and evolved into robust skeletons to stably sustain each unbalanced coalition,which is called the k-CLIque Merging Evolution(CLIME)algorithm.The outliers are eliminated out-side of the skeletons.Some k-cliques containing the overlap may belong to different coalitions,which means the overlaps are separated and absorbed into the corresponding coalitions.The experimental results illustrate that the proposed approaches are robust to density variation and coalition mixture and can enable the effective detection of coalitions from real brain functional networks.There exist potential cognitive functional relations between the regions of interest in the coalitions revealed by our methods which suggests the approach can be usefully applied in neuroscientific studies.To reduce the high complexity problems for k-clique pattern models,a novel method,named Cutting Double k-Clique Spanning Tree(COUSIN)method,for coalition detection from brain functional networks has been proposed.The local property for close-connected nodes is characterized by the k-clique.Firstly,the enumeration of all high-order cliques is executed by a truncation strategy in a fast and parallel method.Then max-clique layer turns into root of span-ning tree.Descendant cliques are merged to branches of spanning tree in a“Root2Leaf”mode.Two spanning trees join into double k-clique spanning tree forming a robust reconfiguration of the given network.Subsequently,a cutting strategy by maximizing modularity is used to quick-ly cut off skeletons from the double k-clique spanning tree in a“Leaf2Root”mode.Finally,the small-scale groups of nodes are collected into the existing huge coalition by the principle of degree priority.Experiments of robustness verification are executed on simulated networks.The experimental tests on real datasets exhibit prominent performance of community detection of the proposed method.The obtained coalitions from actual brain functional networks indicate the application value of the method in neuroscience.To solve the over-fitting problems for few-shot learning of graph neural networks,we pro-pose a novel method,called Graph Co-Neighbor Neural Network(GCo NN),for node classifi-cation.The framework is composed of two modules:GCo NN_Γand GCo NN?_Γ.Specifically,in the preparation stage,GCo NN_Γis pre-trained on labeled data to establish the fundamental pro-totype for attribute learning.Then the two models are interactively trained under a generalized expectation maximization framework through optimizing Evidence Lower Bound(ELBO)by amortised variational inference on entire data.It iterates using two steps:(1)Fixing GCo NN_Γ,derive GCo NN?_Γby optimizing the evidence lower bound.Since direct inference is intractable,we use the amortised variational inference approach to approximate the posterior distribution of neighbor representation.GCo NN?_Γincorporates the entire graph to capture sufficient structure information.(2)Maximize GCo NN_Γwith GCo NN?_Γfixed through maximizing the lower-bound pseudo-likelihood.Given the lack of labels for unlabeled data,instead of calculating the like-lihood function,we maximize the lower-bound pseudo-likelihood on unlabeled data.GCo NN_Γtraverses whole nodes to augment learning of complete attribute data.The iterative process allows GCo NN to learn the distinction between node attributes and graph structure through a cooperation opportunity.Training on transductive data enhances the expressive ability of the model,allowing GCo NN to learn a more generalized node representation.Empirical evidence demonstrates that the state-of-the-art performance of the proposed approach outperforms other methods.We also apply GCo NN to brain functional networks,the results of which reveal re-sponse features across the brain which are physiologically plausible with respect to language and visual functions.This thesis focusing on the key problems in coalition detection task,which proposes corre-sponding methods based on k-clique.The problems such as inefficiency clustering,high com-plexity and hard labeling are solved.The methods are also applied to real brain functional networks,which enable the effective detection of multi-scale coalitions.