GSPBOX_-A-toolbox-for-signal-processing-on-graphs_

1、GSPBOX:AtoolboxforsignalprocessingongraphsNathanaelPerraudin,JohanParatte,DavidShuman,LionelMartinVassilisKalofolias,PierreVandergheynstandDavidK.HammondMarch16,2016AbstractThisdocumentintroducestheGraphSignalProcessingToolbox(GSPBox)aframeworkthatcanbeusedtotacklegraphrelatedproblemswithasignalprocessingapproach.Itexplainsthestructureandtheorganizationofthissoftware.Italsocontainsageneraldescriptionoftheimportantmodules.1ToolboxorganizationInthisdocument,webrieflydescribethedifferentmodulesavai。

2、lableinthetoolbox.Foreachofthem,themainfunctionsarebrieflydescribed.Thischaptershouldhelpmakingtheconnectionbetweenthetheoreticalconceptsintroducedin[7,9,6]andthetechnicaldocumentationprovidedwiththetoolbox.Wehighlyrecommendtoreadthisdocumentandthetutorialbeforeusingthetoolbox.Thedocumentation,thetutorialsandotherresourcesareavailableon-line1.ThetoolboxhasfirstbeenimplementedinMATLABbutaporttoPython,calledthePyGSP,hasbeenmaderecently.Asofthetimeofwritingofthisdocument,notallthefunctionalitieshaveb。

3、eenportedtoPython,butthemainmodulesarealreadyavailable.Inthefollowing,functionsprefixedby[M]:refertotheMATLABimplementationandtheonesprefixedwith[P]:refertothePythonimplementation.1.1Generalstructureofthetoolbox(MATLAB)ThegeneraldesignoftheGSPBoxfocusesaroundthegraphobject[7],aMATLABstructurecontainingthenecessaryinfor-mationstousemostofthealgorithms.Bydefault,onlyafewattributesareavailable(seesection2),allowingonlytheuseofasubsetoffunctions.Inordertoenabletheuseofmorealgorithms,additionalfieldscan。

4、beaddedtothegraphstructure.Forexample,thefollowinglinewillcomputethegraphFourierbasisenablingexactfilteringoperations.1G=gsp_compute_fourier_basis(G);Ideally,thisoperationshouldbedoneontheflywhenexactfilteringisrequired.Unfortunately,thelackofwelldefinedclassparadigminMATLABmakesittoocomplicatedtobeimplemented.Luckily,theaboveformulationpreventsanyunnecessarydatacopyofthedatacontainedinthestructureG.Inordertoavoidnameconflicts,allfunctionsintheGSPBoxstartwith[M]:gsp_.Asecondimportantconventionisthata。

5、llfunctionsapplyingagraphalgorithmonagraphsignaltakesthegraphasfirstargument.Forexample,thegraphFouriertransformofthevectorfiscomputedby1fhat=gsp_gft(G,f);1See://lts2.epfl.ch/pygspforPython.Thefulldocumentationisalsoavail-ableinasingledocument::1408.5781v2[cs.IT]15Mar2016Thegraphoperatorsaredescribedinsection4.Filteringasignalonagraphisalsoalinearoperation.However,sincethedesignofspecialfilters(kernels)isimportant,theyareregroupedinadedicatedmodule(seesection5).Thetoolboxcontainstwoadditionalimpor。

6、tantmodules.Theoptimizationmodulecontainsproximaloperators,projectionsandsolverscompatiblewiththeUNLocBoX[5](seesection6).Thesefunctionsfacilitatethedefinitionofconvexoptimizationproblemsusinggraphs.Finally,section??iscomposedofwellknowngraphmachinelearningalgorithms.1.2Generalstructureofthetoolbox(Python)ThestructureofthePythontoolboxfollowscloselytheMATLABone.ThemajordifferencecomesfromthefactthatthePythonimplementationisobject-orientedandthusallowsforanaturaluseofinstancesofthegraphobject.Fore。

7、xampletheequivalentoftheMATLABcall:1G=gsp_estimate_lmax(G);canbeachievedusingasimplemethodcallonthegraphobject:1G.estimate_lmax()Moreover,theuseofclassforthegraphobjectallowstocomputeadditionalgraphattributesonthefly,makingthecodeclearerasitsMATLABequivalent.Notethoughthatfunctionalitiesaregroupedintodifferentmodules(onepersectionbelow)andthatseveralfunctionsthatworkongraphshavetobecalleddirectlyfromthemodules.Forexample,oneshouldwrite:1layers=pygsp.operators.kron_pyramid(G,levels)Thisisthecaseas。

8、soonasthegraphisthestructureonwhichtheactionhastobeperformedandnotourprincipalfocus.InasimilarwaytotheMATLABimplementationusingtheUNLocBoXfortheconvexoptimizationroutines,thePythonimplementationusesthePyUNLocBoX,whichisthePythonportoftheUNLocBoX.2GraphsTheGSPBoxisconstructedaroundonemainobject:thegraph.ItisimplementedasastructureinMatlabandasaclassinPython.Itstoresthenodes,theedgesandotherattributesrelatedtothegraph.Intheimplementation,agraphisfullydefinedbytheweightmatrixW,whichisthemainandonlyr。

9、equiredattribute.Sincemostgraphstructuresarefarfromfullyconnected,Wisimplementedasasparsematrix.FromtheweightmatrixaLaplacianmatrixiscomputedandstoredasanattributeofthegraphobject.Differentotherattributesareavailablesuchasplottingattributes,vertexcoordinates,thedegreematrix,thenumberofverticesandedges.Thelistofallattributesisgivenintable1.2AttributeFormatDatatypeDescriptionMandatoryfieldsWNxNsparsematrixdoubleWeightmatrixWLNxNsparsematrixdoubleLaplacianmatrixdNx1vectordoubleThediagonalofthedegree。

10、matrixNscalarintegerNumberofverticesNescalarintegerNumberofedgesplotting[M]:structure[P]:dictnonePlottingparameterstypetextstringName,typeorshortdescriptiondirectedscalar[M]:logical[P]:booleanStateifthegraphisdirectedornotlap_typetextstringLaplaciantypeOptionalfieldsANxNsparsematrix[M]:logical[P]:booleanAdjacencymatrixcoordsNx2orNx3matrixdoubleVectorsofcoordinatesin2Dor3D.lmaxscalardoubleExactorestimatedmaximume。