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

GSPBOX:AtoolboxforsignalprocessingongraphsNathanaelPerraudin,JohanParatte,DavidShuman,LionelMartinVassilisKalofolias,PierreVandergheynstandDavidK.HammondMarch16,2016AbstractThisdocumentintroducestheGraphSignalProcessingToolbox(GSPBox)aframeworkthatcanbeusedtotacklegraphrelatedproblemswithasignalprocessingapproach.Itexplainsthestructureandtheorganizationofthissoftware.Italsocontainsageneraldescriptionoftheimportantmodules.1ToolboxorganizationInthisdocument,webrieflydescribethedifferentmodulesavailableinthetoolbox.Foreachofthem,themainfunctionsarebrieflydescribed.Thischaptershouldhelpmakingtheconnectionbetweenthetheoreticalconceptsintroducedin[7,9,6]andthetechnicaldocumentationprovidedwiththetoolbox.Wehighlyrecommendtoreadthisdocumentandthetutorialbeforeusingthetoolbox.Thedocumentation,thetutorialsandotherresourcesareavailableon-line1.ThetoolboxhasfirstbeenimplementedinMATLABbutaporttoPython,calledthePyGSP,hasbeenmaderecently.Asofthetimeofwritingofthisdocument,notallthefunctionalitieshavebeenportedtoPython,butthemainmodulesarealreadyavailable.Inthefollowing,functionsprefixedby[M]:refertotheMATLABimplementationandtheonesprefixedwith[P]:refertothePythonimplementation.1.1Generalstructureofthetoolbox(MATLAB)ThegeneraldesignoftheGSPBoxfocusesaroundthegraphobject[7],aMATLABstructurecontainingthenecessaryinfor-mationstousemostofthealgorithms.Bydefault,onlyafewattributesareavailable(seesection2),allowingonlytheuseofasubsetoffunctions.Inordertoenabletheuseofmorealgorithms,additionalfieldscanbeaddedtothegraphstructure.Forexample,thefollowinglinewillcomputethegraphFourierbasisenablingexactfilteringoperations.1G=gsp_compute_fourier_basis(G);Ideally,thisoperationshouldbedoneontheflywhenexactfilteringisrequired.Unfortunately,thelackofwelldefinedclassparadigminMATLABmakesittoocomplicatedtobeimplemented.Luckily,theaboveformulationpreventsanyunnecessarydatacopyofthedatacontainedinthestructureG.Inordertoavoidnameconflicts,allfunctionsintheGSPBoxstartwith[M]:gsp_.Asecondimportantconventionisthatallfunctionsapplyingagraphalgorithmonagraphsignaltakesthegraphasfirstargument.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).Thetoolboxcontainstwoadditionalimportantmodules.Theoptimizationmodulecontainsproximaloperators,projectionsandsolverscompatiblewiththeUNLocBoX[5](seesection6).Thesefunctionsfacilitatethedefinitionofconvexoptimizationproblemsusinggraphs.Finally,section??iscomposedofwellknowngraphmachinelearningalgorithms.1.2Generalstructureofthetoolbox(Python)ThestructureofthePythontoolboxfollowscloselytheMATLABone.ThemajordifferencecomesfromthefactthatthePythonimplementationisobject-orientedandthusallowsforanaturaluseofinstancesofthegraphobject.ForexampletheequivalentoftheMATLABcall:1G=gsp_estimate_lmax(G);canbeachievedusingasimplemethodcallonthegraphobject:1G.estimate_lmax()Moreover,theuseofclassforthegraphobjectallowstocomputeadditionalgraphattributesonthefly,makingthecodeclearerasitsMATLABequivalent.Notethoughthatfunctionalitiesaregroupedintodifferentmodules(onepersectionbelow)andthatseveralfunctionsthatworkongraphshavetobecalleddirectlyfromthemodules.Forexample,oneshouldwrite:1layers=pygsp.operators.kron_pyramid(G,levels)Thisisthecaseassoonasthegraphisthestructureonwhichtheactionhastobeperformedandnotourprincipalfocus.InasimilarwaytotheMATLABimplementationusingtheUNLocBoXfortheconvexoptimizationroutines,thePythonimplementationusesthePyUNLocBoX,whichisthePythonportoftheUNLocBoX.2GraphsTheGSPBoxisconstructedaroundonemainobject:thegraph.ItisimplementedasastructureinMatlabandasaclassinPython.Itstoresthenodes,theedgesandotherattributesrelatedtothegraph.Intheimplementation,agraphisfullydefinedbytheweightmatrixW,whichisthemainandonlyrequiredattribute.Sincemostgraphstructuresarefarfromfullyconnected,Wisimplementedasasparsematrix.FromtheweightmatrixaLaplacianmatrixiscomputedandstoredasanattributeofthegraphobject.Differentotherattributesareavailablesuchasplottingattributes,vertexcoordinates,thedegreematrix,thenumberofverticesandedges.Thelistofallattributesisgivenintable1.2AttributeFormatDatatypeDescriptionMandatoryfieldsWNxNsparsematrixdoubleWeightmatrixWLNxNsparsematrixdoubleLaplacianmatrixdNx1vectordoubleThediagonalofthedegreematrixNscalarintegerNumberofverticesNescalarintegerNumberofedgesplotting[M]:structure[P]:dictnonePlottingparameterstypetextstringName,typeorshortdescriptiondirectedscalar[M]:logical[P]:booleanStateifthegraphisdirectedornotlap_typetextstringLaplaciantypeOptionalfieldsANxNsparsematrix[M]:logical[P]:booleanAdjacencymatrixcoordsNx2orNx3matrixdoubleVectorsofcoordinatesin2Dor3D.lmaxscalardoubleExactorestimatedmaximume