基于圖的人工智能基準(zhǔn)測試框架 A Framework for Benchmarking Graph-Based Artificial Intelligence

ABSTRACT

TitleofThesis:AFRAMEWORKFORBENCHMARKING

GRAPH-BASEDARTIFICIALINTELLIGENCE

KentDanielO’SullivanMasterofScience,2024

ThesisDirectedby:ProfessorWilliamRegli

DepartmentofComputerScience

Graph-basedArtificialIntelligence(GraphAI)encompassesAIproblemsformulatedusinggraphs,operatingongraphs,orrelyingongraphstructuresforlearning.ContemporaryArtificialIntelligence(AI)researchexploreshowstructuredknowledgefromgraphscanenhanceexistingapproachestomeettherealworld’sdemandsfortransparency,explainability,andperformance.

CharacterizingGraphAIperformanceischallengingbecausedifferentcombinationsofgraphabstractions,representations,algorithms,andhardwareaccelerationtechniquescantriggerun-predictablechangesinefficiency.AlthoughbenchmarksenabletestingdifferentGraphAIim-plementations,mostcannotcurrentlycapturethecomplexinteractionbetweeneffectivenessandefficiency,especiallyacrossdynamicandstructuredknowledgegraphs.

Thisworkproposesanempirical‘grey-box’approachtoGraphAIbenchmarking,providingamethodthatenablesexperimentallytradingbetweeneffectivenessandefficiencyacrossdiffer-entcombinationsofgraphabstractions,representations,algorithms,andhardwareaccelerators.AsystematicliteraturereviewyieldsataxonomyofGraphAItasksandacollectionofintelligence

andsecurityproblemsthatinteractwithGraphAI.Thetaxonomyandproblemsurveyguidethedevelopmentofaframeworkthatfusesempiricalcomputersciencewithconstrainttheoryinanapproachtobenchmarkingthatdoesnotrequireinvasiveworkloadanalysesorcodeinstrumen-tation.

Weformalizeamethodologyfordevelopingproblem-centricGraphAIbenchmarksand

developatooltocreategraphsfromOpenStreetMapsdatatofillagapinreal-worldmesh

graphdatasetsrequiredforbenchmarkinputs.Finally,thisworkprovidesacompletedbench-

markforthePopulationSegmentationIntelligenceandSecurityproblemdevelopedusingthe

GraphAIbenchmarkproblemdevelopmentmethodology.Itprovidesexperimentalresultsthat

validatetheutilityoftheGraphAIbenchmarkframeworkforevaluatingif,how,andwhenGraphAIac-celerationshouldbeappliedtothepopulationsegmentationproblem.

AFRAMEWORKFORBENCHMARKINGGRAPH-BASEDARTIFICIALINTELLIGENCE

by

KentDanielO’Sullivan

ThesissubmittedtotheFacultyoftheGraduateSchoolofthe

UniversityofMaryland,CollegeParkinpartialfulfillment

oftherequirementsforthedegreeof

MasterofScience2024

AdvisoryCommittee:

WilliamRegli,Chair/AdvisorMohammadHajiaghayi

BrianPierce

LaxmanDhulipala

?Copyrightby

KentO’Sullivan

2024

ii

Acknowledgments

Dr.BillRegli,forhisguidanceasmyadvisorandsupportthroughoutmytimeattheUniversityofMaryland.

MyThesisCommittee:Dr.MohammadHajiaghayi,Dr.BrianPierce,andDr.LaxmanDhulipalafortheirtimeandconstructivefeedback.

Nicole,forherextensiveeditingsupport,unwaveringwillingnesstocollaborateonresearch,andinsistenceonpushingmetopublishmyworkoverthelasttwoyears.

Nate,Sam,andTaylor,forthemoraleourstudygroupprovided,andNandiniforourchatsaboutGraphNeuralNetworks.

TheAustralian-AmericanFulbrightCommission,theKinghornFoundation,andtheUniversityofMarylandfortheirscholarshipswhichgavemethemeanstoundertakethiscourseofstudy.

TheAustralianArmy,forsupportingmydesiretostudycomputersciencefortwoyears.

TheAppliedResearchLaboratoryforIntelligenceandSecurityforsupportingmyresearch.

Mostimportantly,tomypartnerMaryforsupportingmeinmovingtotheothersideoftheworldtostudy,pausinghergoalswhileIpursuedmine,andmakingsurethatIsawmoreoftheUnitedStatesthanjusttheinsideoftheComputerScienceDepartment.

iii

TableofContents

Acknowledgements

ii

TableofContents

iii

ListofTables

vi

ListofFigures

vii

ListofAbbreviations

ix

Chapter1:Introduction

1

1.1Motivation

1

1.2ProblemandBackground

2

1.3DevelopingtheGraphAIBenchmarkFrameworkandGraphAIBenchmarkMethod-

ology

5

1.4ApplyingOurGraphAIBenchmarkFramework

8

1.5ApplicationsandImpactoftheGraphAIBenchmarkingFramework

9

1.6ThesisOutline

10

Chapter2:Preliminaries

12

2.1Graph-BasedArtificialIntelligence

12

2.1.1ATaxonomyofGraphAI

13

2.1.2Real-WorldUsesofGraphAI

15

2.2GraphDefinitions

15

2.2.1GraphComponents

16

2.2.2GraphCharacteristics

17

2.2.3GraphTypes

19

2.3GraphTopology

20

2.3.1Real-WorldGraphs

20

2.3.2SyntheticGraphs

21

2.3.3Summary

22

2.4GraphRepresentations

23

2.4.1GraphStorage

23

2.4.2GraphAbstractions

27

2.5GraphPrimitiveOperations

29

2.6ArchitecturalConstraintsforGraphProcessing:Locality

30

iv

2.6.1Locality

31

2.7Summary:OptimizingandEvaluatingGraphAIisaHardProblem

34

Chapter3:LiteratureReview

35

3.1Benchmarking

35

3.1.1Competitive‘Black-Box’Benchmarks

36

3.1.2‘White-Box’Benchmarks

37

3.1.3ConstrainedBenchmarks

38

3.1.4Summary

38

3.2BenchmarkingGraphAI

40

3.2.1TaskCoverage

42

3.2.2DatasetCoverage

46

3.2.3MetricCoverage

49

3.3GraphAIBottlenecks

51

3.3.1MemoryBottlenecks

51

3.3.2ComputationBottlenecks

52

3.3.3CommunicationBottlenecks

53

3.4Summary:GraphAIbenchmarkingrequiresa‘grey-box’approach

53

Chapter4:TheGraphArtificialIntelligenceBenchmarkingFramework

55

4.1Motivation

55

4.2BenchmarkMechanics

56

4.2.1BenchmarkSpecification

57

4.2.2SystemUnderTest

58

4.2.3Grey-BoxEvaluation

59

4.3GraphAIBenchmarkDesign

60

4.3.1EmpiricalBenchmarkDesign

60

4.3.2DesignusingtheTheoryofConstraints

63

4.4OurGraphAIBenchmarkFramework

63

4.5Summary:A‘Grey-Box’GraphAIBenchmarkFramework

68

Chapter5:ThePopulationSegmentationProblem

69

5.1IdentifyandCharacterizethePopulationSegmentationProblem

69

5.1.1Definition

69

5.1.2Tasks

70

5.1.3Datasets

71

5.1.4Outputs

72

5.2IdentifyandCharacterizePhenomenaofInterest

73

5.2.1Efficiency

73

5.2.2Effectiveness

73

5.2.3Cost

74

5.2.4Outputs

75

5.3ConductExploratoryExperimentation

75

5.3.1DatasetsObservations

77

5.3.2ImplementationObservations

77

v

5.3.3Outputs

79

5.4DevelopHypotheses

80

5.4.1StimulatingHardware

81

5.4.2StimulatingRepresentations

82

5.4.3StimulatingCommunityDetection(CD)Implementations

83

5.4.4SelectingHypotheses

84

5.5ConstructtheInvestigationApparatus

85

5.5.1ObservationApparatus

86

5.5.2Datasets

86

5.5.3Tasks

91

5.5.4Metrics

92

5.5.5Limitations

92

5.5.6Outputs

93

5.6AnalyzeResults,DevelopTheoreticExplanationandIterate

94

5.6.1ExperimentSetup

94

5.6.2ExperimentResults

96

5.7Discussion

101

Chapter6:Conclusion

104

6.1FutureWork

104

6.2Conclusion

106

Bibliography

109

vi

ListofTables

2.1TheGraphAItaxonomygroupsGraphAItasksintoGraphAIproblemsandbroader

GraphAIproblemareas

14

2.2AsurveyofGraphAIproblemsintheIntelligenceandSecurity(I&S)domain

16

3.1CoverageofGraphAItasksbyexistingbenchmarksuitesandworkloadanalyses

41

3.2CoverageofGraphAIdatasetsbyexistingbenchmarksuitesandworkloadanalyses.

45

3.3CoverageofGraphAImetricsbyexistingbenchmarksuitesandworkloadanalyses.

48

4.1Summaryofdependenciesbetweenbenchmarkcomponentsandevaluationmetrics.

60

4.2Summaryofexpectedmetricbehaviorswhenabenchmarkcomponentiscon-

strained

66

5.1Exampleproblem-centrictasksforthepopulationsegmentationbenchmark

71

5.2Surveyofcomputationalapproachestopopulationsegmentation,showingeffi-

ciencyandeffectivenessbottlenecks

76

5.3Summaryofdatasetsforthepopulationsegmentationproblemshowingsize,

summarystatisticsanddomain

90

5.4Summaryofexperimentsforthepopulationsegmentationbenchmark.EachSUT

completesthesametasksonthesamedata

96

vii

ListofFigures

1.1TheGraphAItaxonomyconsistsofsixGraphAIproblemareas.Indicativetasks

foreachproblemareaareingrey

2

1.2GraphAIchallengesareahierarchyofdependenciesfoundationallylimitedby

graphprocessing

5

1.3TheGraphAIbenchmarkframeworktakesagrey-boxapproachtobenchmarking,

designinginputstostimulateobservablechangestooutputstoinfersystemand

implementationdetail

6

1.4TheGraphAIbenchmarkdesignmethodologyforcreatingproblem-centricbench-

marks,showinghowmethodologyoutputsmaptobenchmarkcomponents

6

1.5Thehigh-levelviewoftheGraphAIbenchmarkingframework.SUTsinteract

withthebenchmarkthroughanobservationapparatusAPI

9

2.1Examplegraphwithfivenodesandfiveedges

23

2.2AdjacencyListforgraphinFigure2.1.Eachlinerepresentsavertex,withthe

firstinthelistbeingthesourceandeachsubsequentvertexadestinationofanedge.

24

2.3AdjacencyMatrixforgraphinFigure2.1isa|V|×|V|matrixwhereavalueof

1indicatesanedgeand0isnoedge

25

2.4IncidenceMatrixforthegraphinFigure2.1isa|E|×|V|matrixwherea-1is

thesourcenodeand1isthedestinationofagivenedge

26

2.5TheCompressedSparseRow(CSR)formatusesthreeliststorepresentthegraph

inFigure2.1

27

2.6Asimplifiedrepresentationofadirectedgraphinvertexorderwhereeachvertex

isaddedtomemorycreationorder(here,alphabetically).Edgesarenotshown

32

2.7Asimplifiedrepresentationofadirectedgraphinvertexorderwhereeachvertex

isaddedtomemorycreationorderwithattributesstoredseparately.Pointersfrom

topologytoattributesarenotshownforclaritybutcorrespondtothefirstletterof

theattribute

33

3.1Thebasiccomponentsofagenericbenchmarksystem

39

4.1ThecomponentsoftheGraphAIbenchmarkingframework

57

4.2Hooker’smethodologyforanempiricalscienceofalgorithms[1,2]

62

4.3ThecomponentsoftheGraphAIbenchmarkingframework

67

5.1ThecoverageofstaticCDdatasetsshowingtheexpecteddifficultyofeffective-

nessversusefficiency.Redcolorsaremore‘difficult’interactions

91

5.2Theobservationapparatusforthepopulationsegmentationbenchmark

93

viii

5.3TheexperimentscomparethreeSUT,eachwithastaticanditerativeimplemen-

tationoftheLouvainAlgorithm[3]

95

5.4TheGPUimplementationisdrasticallyfasterthantheBaselineandXeonSUT

forthesametasks

97

5.5TheGPUSUTexperiencesadipinNMIforScale-Freedatasetswhileeffective-

nessremainsconstantacrossbothCPU-basedSUTs

97

5.6PorportionofatotalexperimentshowsGPUspendmoretimeonETLrelativeto

totalExecutionTime(ExTime)

99

5.7Theunderlyinghardwareimpactstheperformanceofiterativealgorithms,with

onlytheXeonCPUSUTshowingmonotonicimprovementthatallowstrading

effectivenessforefficiency

100

ix

ListofAbbreviations

A*

A-StarSearch

AI

ArtificialIntelligence

API

ApplicationProgrammingInterface

ARLIS

AppliedResearchLaboratoryforIntelligenceandSecurity

ASIC

ApplicationSpecificIntegratedCircuit

BFS

BreadthFirstSearch

BL

BatchLatency

BR

BatchRate

BS

BenchmarkServer

CD

CommunityDetection

CIMIC

Civil-MilitaryCoorperation

COCO

CommonObjectsinCOntext

CombBLAS

CombinatorialBasicLinearAlgebraSubprograms

CPU

CentralProcessingUnit

CRUD

CreateReadUpdateDelete

CSC

CompressedSparseColumn

CSR

CompressedSparseRow

CUDA

ComputeUniformDeviceArchitecture

CV

ComputerVision

DFS

DepthFirstSearch

ETL

ExtractTransformLoad

ETLTime

ExtractTransform&LoadTime

ExTime

ExecutionTime

GA

GraphAbstraction

GAP

GraphAlgorithmPlatform

GAS

GatherApplyScatter

GBBS

Graph-BasedBenchmarkSuite

GCC

GlobalClusteringCoefficient

GDB

GraphDatabase

GHA

GraphHardwareAccelerator

GM

GraphMining

GNN

GraphNeuralNetwork

GC

GraphClustering

GP

GraphPrediction

GPU

GraphicsProcessingUnit

GPS

GraphProblemSolving

x

GRGraphReasoning

GraphBLASGraphBasicLinearAlgebraSubprogramsGTGraphTransparency

HPCHighPerformanceComputingI&SIntelligenceandSecurity

IOInformationOperations

IPBIntelligencePreperationoftheBattlespace

LCCLocalClusteringCoefficient

LFRLancichinetti,Fortunato,RadicciLLMLargeLanguageModel

MLMachineLearning

NDRNetworkDataRepository

NMINormalizedMutualInformationNLPNaturalLanguageProcessing

MSTMinimumSpanningTreeOSMOpenStreetMaps

RAMRandomAccessMemory

RAGRetrievalAugmentedGenerationRMATRandomMatrix

SCCStronglyConnectedComponentsSLRSystematicLiteratureReview

SLNDCStanfordLargeNetworkDatasetCollectionSNAPStanfordNetworkAnalysisProject

SOTAStateOfTheArt

SSSPSingleSourceShortestPath

SUTSystemUnderTest

SWaPSizeWeightandPowerTCTriangleCounting

TEPSTraversedEdgesperSecondTxTimeTransferTime

UCSUniformCostSearch

VQAVisualQuestionAnswering

WCCWeaklyConnectedComponents

1

Chapter1

Introduction

1.1Motivation

Graphsareexpressivedatastructuresthatencodeevidenceasverticesandcontextualre-lationshipsbetweenevidenceasedges.Aspowerfulabstractionsoftherealworld,graphslendthemselveswelltolearningandreasoningtasks,whichencompassanemergingareaofworkwetermGraph-BasedArtificialIntelligence(GraphAI).WetaxonomizeGraphAIwithintheex-istingAIlandscape,coveringthewell-knownareasofGraphPrediction(GP)[

4

–

6

]andGraphMining(GM)[

7

]andextendingthosetoincludeGraphProblemSolving(GPS),GraphRea-soning(GR),GraphAbstraction(GA),andGraphTransparency(GT),whicharedetailedinFigure

1.1.

Acrosstheseareas,GraphAIincludestaskslikestructuralanalysis,inferenceovergraphs,andapplicationsofgraphstoAIproblemslikemodeltransparency,explainability,andinterpretability.

AlthoughgraphsareexpressiveandbroadlyapplicabletovariousAIproblems,theyimposeasignificantcomputationalburdenonsystemsthatoperateGraphAI.Intelligentalgorithmsthatoperateongraphsfrequentlyhavequadraticorworsecomplexity,whichlimitstheirusabilityonreal-worldgraphscontainingbillionsortrillionsofvertices.Moderngeneral-purposeprocessorsusecachingandprefetchingtospeedupcomputationoverlargenon-graphinputs.ThechallengewithgraphsisthatmostGraphAIalgorithmsexploitthegraph’sstructureinprocessing,whichrequiresaccesstothedataintopologicalorder.Thatrequirementconflictswithgraphstorage,whichistypicallychronologicalintheorderthatverticesarecreated,meaningtopologicallyclose

2

GraphMining

Q

Graphproblemsolving

Graph

Abstraction

Graph

prediction

Graph

Transparency

Graphsearch

common-sense

Graph

Embedding

GraphNeuralNetworks

Neuro-symbolicAl

Alplanning

communityDetection

ontologicaInference

KGcompletion

RepresentationLearning

KGInference

Graphprediction

post-HOC

Explanation

criticalpath

Graph

Generation

GraphA

Graph

Reasoning

GraphMatching

RAG

InfluenceMapping

Figure1.1:TheGraphAItaxonomyconsistsofsixGraphAIproblemareas.Indicativetasksfor

eachproblemareaareingrey.

verticesarenotnecessarilyproximalinmemory.Withoutcachingbenefits,GraphAIalgorithmsrelyondataretrievedfrommainmemory,whichcausesmemorylatencyandbandwidthbottle-necksthatlimitscalabilityandpreventGraphAIfrombeingdeployedonreal-worldproblemsthatmightotherwisebenefitfromit.

1.2ProblemandBackground

CommonapproachestospeedingupGraphAIprocessingtypicallyusehardware,likespe-cializedacceleratorsordistributedprocessing;representation,likecustomdatastructuresorab-stractionmodels;oralgorithms,likeparallelorapproximatemethods.Theseapproachesarein-terdependent,meaningdecisionsaboutoptimizinghardwarecanlimitchoicesaboutparallelismorprogrammingmodels,whichmakesitdifficulttodeterminetheoptimalconfigurationfora

3

givencollectionofproblems.

Thisthesisaimstodetermineif,how,andwhentospeedupproblem-solvingonGraphAIgivenasetofoperatingconstraints.Specifically,weconsiderhowtoeffectivelycombinerepresenta-tions,hardwareaccelerators,andalgorithmstospeedupGraphAIandunderwhatconditionsaspecificcombinationisappropriateforausecasegivensomeconstraintsonasolution’seffi-ciency,effectiveness,andcost.Priorapproachestoidentifyingif,how,andwhentoaccelerateaGraphAIsystemrelyongenericcompetitivebenchmarksorinvasiveworkloadanalysis,bothofwhichprovideincompleteviewsofGraphAIperformanceacrossmultiplepossiblesystemcon-figurations.

Benchmarkingisaprocessbywhichsystemsorcomponentsarecomparedaccordingtosomecriteria,whichisusedtodeterminetheirrelativeperformance[

8

].MostbenchmarksforGraphAItakea‘black-box’approachtocompetingsystemsbasedonefficiencyoreffectivenessmetricsbutrarelyboth,andnevertheirinteractions.Benchmarkstypicallyfocusonevaluatingisolatedkernel-leveltasksratherthanmorecomplicatedreal-worldproblemsandtypicallyuseasmallselectionofdatasetsthatdonotcoverthebreadthofexpectedinputsizesandshapes.Ex-istingbenchmarksalsolacksupportfordynamicgraphprocessingapproaches,especiallycom-paringdynamicandstaticapproachesunderthesameevaluationframework.

Alternatively,workloadanalysesare‘white-box’approachesthatanalyzetheinternalstateofasystemwhilecompletingaworkloadtoidentifybottlenecks.AlthoughworkloadanalysesyielddetailedinformationabouthowtoacceleratetheSystemUnderTest(SUT),theyrequireaccesstothesystemforprofilingandaccesstothecodeforinstrumentation.Theinvasiveconfig-urationrequirementsmeanworkloadanalysescannotbescaledforgeneral-purposecomparisons,makingthemunsuitableforbroadapplicationtoGraphAI.

4

Inadditiontothechoiceintheanalyticmethod,ahierarchyofotherchallengesunderlaythebroaderproblemofdecidingif,how,andwhentoimproveGraphAIundersomeconstraints,whichweoutlineinFigure

1.2.

Takingauser’stop-downperspectiveofthechallengehierarchy,theusermustfirstdecidethedegreetowhicheffectivenessshouldbetradedforefficiencyorcost.Theneedtomakethistrade-offstemsfromthereal-worldconstraintsimposedonGraphAIsys-tems,suchasarequirementtogeneratearecurringsolutionatapacemorefrequentthantheal-gorithm’sruntimeallows.Further,mostgraphhardwareacceleratorsarespecializedApplicationSpecificIntegratedCircuit(ASIC)andareoptimizedtospeedupaspecificalgorithm,representa-tion,abstraction,andprogrammingmodel.TheproblemwithASICsisthatagivenGraphAIsys-temmayneedtosupportmanygraphtasks,soanacceleratorthatoptimizestheperformanceofasingleGraphAItaskmaynotgarnerabroadenoughimprovementinallGraphAItaskstojustifyitscost.Thesereal-worldchallengesandtrade-offsareparticularlypronouncedforGraphAIbe-causeoftheinherentnatureofgraphprocessingthatunderliesGraphAIproblems.Graphsofdifferentshapesandsizesunpredictablyinfluencealgorithmiccomplexity,includingexacerbat-ingirregularmemoryaccessesandcomputationpatternsthatunderminespatialandtemporallocality.Whencombinedwiththedatadependence,thelackofstandardgraphrepresentationmethods,abstractionmodels,orasetofprimitiveoperationsfurtherpreventsaunityofefforttowardacceleratinggraphprocessingacrossallgraphtasks.

5

Evaluation:

'Racing'systemsorinvasive

analysis?

user:

Realworld:

GraphAl

Graph:

If,HOW,when&constraints?

EffectivenessorEfficiency?

Figure1.2:GraphAIchallengesareahierarchyofdependenciesfoundationallylimitedbygraphprocessing.

1.3DevelopingtheGraphAIBenchmarkFrameworkandGraphAIBenchmarkMethod-

ology.

WeaddresstheseGraphAIissuesbycontributingourGraphAIbenchmarkframework,showninFigure

1.5.

ThebenchmarkevaluatestheperformanceofaSUTusinganInput/OutputobservationapparatustoprovidetheSUTwithproblem-centrictasksanddata,recordthetimetosolution,andverifythecorrectnessofananswer.EachGraphAIbenchmarkintheframeworkisindependent,andwecontributeanempiricalmethodologyforconstructingaproblem-centric,accelerator-agnostic,‘grey-box’GraphAIbenchmarkthatcanevaluateboththeefficiencyandtheeffectivenessofdynamicandstaticGraphAIimplementationsandsystems.

By‘grey-box’,wemeananapproachtobenchmarkingbetweenthefullyopaqueblack-box

6

GREYBOX

-Inputsknown&designedtostimulatebottlenecks.

-systemdetailunknown.-Implementationunknown.

-outputsevaluatedand

analyzedtoinfersystemandimplementationdetail.

WHITEBOX-Inputsknown.

-systemdetailknownandinstrumented.

-Implementationknownandinstrumented.

-outputsrarelyevaluated.

Figure1.3:TheGraphAIbenchmarkframeworktakesagrey-boxapproachtobenchmarking,

designinginputstostimulateobservablechangestooutputstoinfersystemandimplementationdetail.

Datasets

Tasks

Metrics

observationApparatus

Hardware

softwarestack

Implementation

Figure1.4:TheGraphAIbenchmarkdesignmethodologyforcreatingproblem-centricbench-

marks,showinghowmethodologyoutputsmaptobenchmarkcomponents.

7

viewthatnaivelyracessystemsagainsteachotherandtheinvasivewhite-boxviewthatpainstak-inglymonitorstheinternalstateofasystem(Figure

1.3

).Inimplementingagrey-boxview,weuseourGraphAIbenchmarkdesignmethodologytoidentifyexpectedsystemandimplementa-tionbottlenecksanddesignadversarialinputsthatweexpecttostimulatethosebottlenecks.Byevaluatingtheoutputandanalyzingtheefficiencyandeffectivenessacrossdatasets,wecaninferwhichexpectedbottleneckwilllikelycauseanobservedoutputwithoutinvasiveinstrumentation.

Thisapproachofmanipulatinginputstotriggerbottlenecksobservableintheoutputsallowsustoturnoneofthemostsignificantproblemsingraphprocessing(datadependence)intoavaluableasset.

Weemployaformalmethod(Figure

1.4

)thatemphasizesthetransparency,verifiability,andreproducibilityofbenchmarkproblems.Atitscore,themethodconstructsadetailedmap-pingofthecharacteristicsoftheinputgraphstotheoutputsofaGraphAIsystemanddetailshowtointerpretthoseoutputsinthecontextofknownandsuspectedbottlenecksinhardware,representation,andimplementationdecisions.Themethodcomprisessixstepsthatgeneratethecomponentsofthebenchmarkspecificationandtheobservationapparatus.

Theprocessbeginsbyidentifyingausecasetogroundtheprobleminreal-worlddatasetsandcurrentapproaches.Amoredetailedanalysisoftheproblemyieldsinformationaboutthesizeandshapeofthedataandformallyspecifiestheeverydaytasksassociatedwiththatprob-leminnaturallanguage.Formalizingthestudy’sphenomenaincludesidentifyingwhatspecificinteractionsofdatasetandtaskar