You are an expert at summarizing long articles. Proceed to summarize the following text: 
spectral clustering is an important clustering technique that has been extensively studied in the image processing , data mining , and machine learning communities ( @xcite ) . it is considered superior to traditional clustering algorithms like @xmath0-means in terms of having deterministic polynomial - time solution , the ability to model arbitrary shaped clusters , and its equivalence to certain graph cut problems . for example , spectral clustering is able to capture the underlying moon - shaped clusters as shown in fig . [ fig : two_moon](b ) , whereas @xmath0-means would fail ( fig . [ fig : two_moon](a ) ) . the advantage of spectral clustering has also been validated by many real - world applications , such as image segmentation ( @xcite ) and mining social networks ( @xcite ) . +    spectral clustering was originally proposed to address an unsupervised learning problem : the data instances are unlabeled , and all available information is encoded in the graph laplacian . however , there are cases where unsupervised spectral clustering becomes insufficient . using the same toy data , as shown in ( fig . [ fig : two_moon](c ) ) , when the two moons are under - sampled , the clusters become so sparse that the separation of them becomes difficult . to help spectral clustering recover from an undesirable partition , we can introduce side information in various forms , in either small or large amounts . for example :    1 .   * pairwise constraints * : domain experts may explicitly assign constraints that state a pair of instances must be in the same cluster ( must - link , ml for short ) or that a pair of instances can not be in the same cluster ( cannot - link , cl for short ) . for instance , as shown in fig . [ fig : two_moon](d ) , we assigned several ml ( solid lines ) and cl ( dashed lines ) constraints , then applied our constrained spectral clustering algorithm , which we will describe later . as a result , the two moons were successfully recovered . * partial labeling * : there can be labels on some of the instances , which are neither complete nor exhaustive . we demonstrate in fig . [ fig : uci_ari ] that even small amounts of labeled information can greatly improve clustering results when compared against the ground truth partition , as inferred by the labels . * alternative weak distance metrics * : in some situations there may be more than one distance metrics available . for example , in table  [ table : reuters ] and accompanying paragraphs we describe clustering documents using distance functions based on different languages ( features ) . * transfer of knowledge * : in the context of transfer learning ( @xcite ) , if we treat the graph laplacian as the target domain , we could transfer knowledge from a different but related graph , which can be viewed as the source domain . we discuss this direction in section  [ sec : algorithm : transfer ] and [ sec : exp : transfer ] . all the aforementioned side information can be transformed into pairwise ml and cl constraints , which could either be hard ( binary ) or soft ( degree of belief ) . for example , if the side information comes from a source graph , we can construct pairwise constraints by assuming that the more similar two instance are in the source graph , the more likely they belong to the same cluster in the target graph . consequently the constraints should naturally be represented by a degree of belief , rather than a binary assertion .    how to make use of these side information to improve clustering falls into the area of constrained clustering ( @xcite ) . in general , constrained clustering is a category of techniques that try to incorporate ml and cl constraints into existing clustering schemes . it has been well studied on algorithms such as @xmath0-means clustering , mixture model , hierarchical clustering , and density - based clustering . previous studies showed that satisfying all constraints at once ( @xcite ) , incrementally ( @xcite ) , or even pruning constraints ( @xcite ) is intractable . furthermore , it was shown that algorithms that build set partitions incrementally ( such as @xmath0-means and em ) are prone to being over - constrained ( @xcite ) . in contrast , incorporating constraints into spectral clustering is a promising direction since , unlike existing algorithms , all data instances are assigned simultaneously to clusters , even if the given constraints are inconsistent . constrained spectral clustering is still a developing area . previous work on this topic can be divided into two categories , based on how they enforce the constraints . the first category ( @xcite ) directly manipulate the graph laplacian ( or equivalently , the affinity matrix ) according to the given constraints ; then unconstrained spectral clustering is applied on the modified graph laplacian . the second category use constraints to restrict the feasible solution space ( @xcite ) . existing methods in both categories share several limitations :    * they are designed to handle only binary constraints . however , as we have stated above , in many real - world applications , constraints are made available in the form of real - valued degree of belief , rather than a yes or no assertion . * they aim to satisfy as many constraints as possible , which could lead to inflexibility in practice . for example , the given set of constraints could be noisy , and satisfying some of the constraints could actually hurt the overall performance . also , it is reasonable to ignore a small portion of constraints in exchange for a clustering with much lower cost . * they do not offer any natural interpretation of either the way that constraints are encoded or the implication of enforcing them .      in this paper , we study how to incorporate * large * amounts of pairwise constraints into spectral clustering , in a flexible manner that addresses the limitations of previous work . then we show the practical benefits of our approach , including new applications previously not possible . we extend beyond binary ml / cl constraints and propose a more flexible framework to accommodate general - type side information . we allow the binary constraints to be relaxed to real - valued degree of belief that two data instances belong to the same cluster or two different clusters . moreover , instead of trying to satisfy each and every constraint that has been given , we use a user - specified threshold to lower bound how well the given constraints must be satisfied . therefore , * our method provides maximum flexibility in terms of both representing constraints and satisfying them*. this , in addition to handling large amounts of constraints , allows the encoding of new styles of information such as entire graphs and alternative distance metrics in their raw form without considering issues such as constraint inconsistencies and over - constraining . our contributions are :    * we propose a principled framework for constrained spectral clustering that can incorporate large amounts of both hard and soft constraints . * we show how to enforce constraints in a flexible way : a user - specified threshold is introduced so that a limited amount of constraints can be ignored in exchange for lower clustering cost . this allows incorporating side information in its raw form without considering issues such as inconsistency and over - constraining . * we extend the objective function of unconstrained spectral clustering by encoding constraints explicitly and creating a novel constrained optimization problem . thus our formulation naturally covers unconstrained spectral clustering as a special case . * we show that our objective function can be turned into a generalized eigenvalue problem , which can be solved deterministically in polynomial time . this is a major advantage over constrained @xmath0-means clustering , which produces non - deterministic solutions while being intractable even for @xmath1 ( @xcite ) . * we interpret our formulation from both the graph cut perspective and the laplacian embedding perspective . * we validate the effectiveness of our approach and its advantage over existing methods using standard benchmarks and new innovative applications such as transfer learning . this paper is an extension of our previous work ( @xcite ) with the following additions : 1 ) we extend our algorithm from 2-way partition to @xmath0-way partition ( section  [ sec : algorithm : k - way ] ) ; 2 ) we add a new geometric interpretation to our algorithm ( section  [ sec : interpret : geo ] ) ; 3 ) we show how to apply our algorithm to a novel application ( section  [ sec : algorithm : transfer ] ) , namely transfer learning , and test it with a real - world fmri dataset ( section  [ sec : exp : transfer ] ) ; 4 ) we present a much more comprehensive experiment section with more tasks conducted on more datasets ( section  [ sec : exp:2moon ] and [ sec : exp : reuters ] ) .    the rest of the paper is organized as follows : in section  [ sec : related ] we briefly survey previous work on constrained spectral clustering ; section  [ sec : background ] provides preliminaries for spectral clustering ; in section  [ sec : model ] we formally introduce our formulation for constrained spectral clustering and show how to solve it efficiently ; in section  [ sec : interpret ] we interpret our objective from two different perspectives ; in section  [ sec : algorithm ] we discuss the implementation of our algorithm and possible extensions ; we empirically evaluate our approach in section  [ sec : exp ] ; section  [ sec : conclusion ] concludes the paper . constrained clustering is a category of methods that extend clustering from unsupervised setting to semi - supervised setting , where side information is available in the form of , or can be converted into , pairwise constraints . a number of algorithms have been proposed on how to incorporate constraints into spectral clustering , which can be grouped into two categories . the first category manipulates the graph laplacian directly . @xcite proposed the spectral learning algorithm that sets the @xmath2-th entry of the affinity matrix to 1 if there is a ml between node @xmath3 and @xmath4 ; 0 for cl . a new graph laplacian is then computed based on the modified affinity matrix . in ( @xcite ) , the constraints are encoded in the same way , but a random walk matrix is used instead of the normalized laplacian . @xcite proposed to add both positive ( for ml ) and negative ( for cl ) penalties to the affinity matrix ( they then used kernel @xmath0-means , instead of spectral clustering , to find the partition based on the new kernel ) . @xcite proposed to propagate the constraints in the affinity matrix . in @xcite , the graph laplacian is modified by combining the constraint matrix as a regularizer . the limitation of these approaches is that there is no principled way to decide the weights of the constraints , and there is no guarantee that how well the give constraints will be satisfied . the second category manipulates the eigenspace directly . for example , the subspace trick introduced by @xcite alters the eigenspace which the cluster indicator vector is projected onto , based on the given constraints . this technique was later extended in @xcite to accommodate inconsistent constraints . @xcite encoded partial grouping information as a subspace projection . @xcite enforced constraints by regularizing the spectral embedding . this type of approaches usually strictly enforce given constraints . as a result , the results are often over - constrained , which makes the algorithms sensitive to noise and inconsistencies in the constraint set . moreover , it is non - trivial to extend these approaches to incorporate soft constraints . in addition , @xcite proposed a spectral kernel design that combines multiple clustering tasks . the learned kernel is constrained in such a way that the data distributions of any two tasks are as close as possible . their problem setting differs from ours because we aim to perform single - task clustering by using two ( disagreeing ) data sources . @xcite showed how to incorporate pairwise constraints into a penalized matrix factorization framework . their matrix approximation objective function , which is different from our normalized min - cut objective , is solved by an em - like algorithm . we would like to stress that the pros and cons of spectral clustering as compared to other clustering schemes , such as @xmath0-means clustering , hierarchical clustering , etc . , have been thoroughly studied and well established . we do not claim that constrained spectral clustering is universally superior to other constrained clustering schemes . the goal of this work is to provide a way to incorporate constraints into spectral clustering that is more flexible and principled as compared with existing constrained spectral clustering techniques . in this paper we follow the standard graph model that is commonly used in the spectral clustering literature . we reiterate some of the definitions and properties in this section , such as graph laplacian , normalized min - cut , eigendecomposition and so forth , to make this paper self - contained . readers who are familiar with the materials can skip to our formulation in section  [ sec : model ] . important notations used throughout the rest of the paper are listed in table  [ table : notation ] . .table of notations [ cols="^,<",options="header " , ]      finally we apply our algorithm to transfer learning on the resting - state fmri data . an fmri scan of a person consists of a sequence of 3d images over time . we can construct a graph from a given scan such that a node in the graph corresponds to a voxel in the image , and the edge weight between two nodes is ( the absolute value of ) the correlation between the two time sequences associated with the two voxels . previous work has shown that by applying spectral clustering to the resting - state fmri we can find the substructures in the brain that are periodically and simultaneously activated over time in the resting state , which may indicate a network associated with certain functions ( @xcite ) . one of the challenges of resting - state fmri analysis is instability . noise can be easily introduced into the scan result , e.g. the subject moved his / her head during the scan , the subject was not at resting state ( actively thinking about things during the scan ) , etc . consequently , the result of spectral clustering becomes instable . if we apply spectral clustering to two fmri scans of _ the same _ person on two different days , the normalized min - cuts on the two different scans are so different that they provide little insight into the brain activity of the subject ( fig . [ fig : fmri](a ) and ( b ) ) . to overcome this problem , we use our formulation to transfer knowledge from scan 1 to scan 2 and get a constrained cut , as shown in fig . [ fig : fmri](c ) . this cut represents what the two scans agree on . the pattern captured by fig . [ fig : fmri](c ) is actually the _ default mode network _ ( dmn ) , which is the network that is periodically activated at resting state ( fig . [ fig : fmri](d ) shows the idealized dmn as specified by domain experts ) .     +    to further illustrate the practicability of our approach , we transfer the idealized dmn in fig .  [ fig : fmri](d ) to a set of fmri scans of elderly subjects . the dataset was collected and processed within the research program of the university of california at davis alzheimer s disease center ( ucd adc ) . the subjects were categorized into two groups : those diagnosed with cognitive syndrome ( 20 individuals ) and those without cognitive syndrome ( 11 individuals ) . for each individual scan , we encode the idealized dmn into a constraint matrix ( using the rbf kernel ) , and enforce the constraints onto the original fmri scan . we then compute the cost of the constrained cut that is the most similar to the dmn . if the cost of the constrained cut is high , it means there is great disagreement between the original graph and the given constraints ( the idealized dmn ) , and vice versa . in other words , the cost of the constrained cut can be interpreted as the cost of transferring the dmn to the particular fmri scan .    in fig . [ fig : fmri : str ] , we plot the costs of transferring the dmn to both subject groups . we can clearly see that the costs of transferring the dmn to people without cognitive syndrome tend to be lower than to people with cognitive syndrome . this conforms well to the observation made in a recent study that the dmn is often disrupted for people with the alzheimer s disease ( @xcite ) . in this work we proposed a principled and flexible framework for constrained spectral clustering that can incorporate large amounts of both hard and soft constraints . the flexibility of our framework lends itself to the use of all types of side information : pairwise constraints , partial labeling , alternative metrics , and transfer learning . our formulation is a natural extension to unconstrained spectral clustering and can be solved efficiently using generalized eigendecomposition . we demonstrated the effectiveness of our approach on a variety of datasets : the synthetic two - moon dataset , image segmentation , the uci benchmarks , the multilingual reuters documents , and resting - state fmri scans . the comparison to existing techniques validated the advantage of our approach . we gratefully acknowledge support of this research via onr grants n00014 - 09 - 1 - 0712 automated discovery and explanation of event behavior , n00014 - 11 - 1 - 0108 guided learning in dynamic environments and nsf grant nsf iis-0801528 knowledge enhanced clustering . amini mr , usunier n , goutte c ( 2009 ) learning from multiple partially observed views - an application to multilingual text categorization . in : advances in neural information processing systems 22 ( nips 2009 ) , pp 2836                  davidson i , ravi ss , ester m ( 2007 ) efficient incremental constrained clustering . in : proceedings of the 13th acm sigkdd international conference on knowledge discovery and data mining ( kdd 2007 ) , pp 240249    de  bie t , suykens jak , de  moor b ( 2004 ) learning from general label constraints . in : structural , syntactic , and statistical pattern recognition , joint iapr international workshops ( sspr / spr 2004 ) , pp 671679              ji x , xu w ( 2006 ) document clustering with prior knowledge . in : proceedings of the 29th annual international acm sigir conference on research and development in information retrieval ( sigir 2006 ) , pp 405412                martin d , fowlkes c , tal d , malik j ( 2001 ) a database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics . in : proceedings of the 8th international conference on computer vision ( iccv 2001 ) , vol  2 , pp 416423            wang f , ding chq , li t ( 2009 ) integrated kl ( k - means - laplacian ) clustering : a new clustering approach by combining attribute data and pairwise relations . in : proceedings of the 9th siam international conference on data mining ( sdm 2009 ) , pp 3848        xu q , desjardins m , wagstaff k ( 2005 ) constrained spectral clustering under a local proximity structure assumption . in : proceedings of the 18th international florida artificial intelligence research society conference , pp 866867
constrained clustering has been well - studied for algorithms such as @xmath0-means and hierarchical clustering . 
 however , how to satisfy many constraints in these algorithmic settings has been shown to be intractable . 
 one alternative to encode many constraints is to use spectral clustering , which remains a developing area . in this paper 
 , we propose a flexible framework for constrained spectral clustering . 
 in contrast to some previous efforts that implicitly encode must - link and cannot - link constraints by modifying the graph laplacian or constraining the underlying eigenspace , we present a more natural and principled formulation , which explicitly encodes the constraints as part of a constrained optimization problem . 
 our method offers several practical advantages : it can encode the degree of belief in must - link and cannot - link constraints ; it guarantees to lower - bound how well the given constraints are satisfied using a user - specified threshold ; it can be solved deterministically in polynomial time through generalized eigendecomposition . 
 furthermore , by inheriting the objective function from spectral clustering and encoding the constraints explicitly , much of the existing analysis of unconstrained spectral clustering techniques remains valid for our formulation . 
 we validate the effectiveness of our approach by empirical results on both artificial and real datasets . 
 we also demonstrate an innovative use of encoding large number of constraints : transfer learning via constraints .