从因果角度的图分布外泛化

GraphOut-of-Distribution

GeneralizationFromaCausalPerspective

演讲人：隋勇铎(YongduoSui)

中国科学技术大学博士生

蚂蚁集团实习生

中国科学技术大学

UniversityofScienceandTechnologyofChina

蚂集团DataFun.

CONTENT

蚂蚁集团

ANTGROUP

01BackgroundandMotivation

02RelatedStudies

03CausalAttentionLearning

04AdversarialInvariantAugmentation

01

BackgroundandMotivation

oy

蚂集团DataFun.

蚂蚁集团

ANTGROUP

Fun.

1.1Background

口Graphdataareeverywhere

·Socialnetwork

·Chemicalmolecule

·Biologicalprotein

□Graphlearningtasks

·Nodeclassification

·Linkprediction/classification

·Graphclassification

Socialnetwork

CH₃

Molecule

Proteinstructure

蚂蚁集团

ANTGROUP

Fun.

1.2GraphOut-of-distributionIssue

□OODIssueinImageClassification

PACS

Camelyon

TestTraining

Covariateshift

Cow&CamelColoredMNIST

Correlationshift

[1]OoD-Bench:QuantifyingandUnderstandingTwoDimensionsofOut-of-DistributionGeneralization,CVPR2022

蚂蚁集团

ANTGROUP

1.2GraphOut-of-distributionIssue

□OODIssueinGraphClassification

Distributionshiftonnodefeatures

Distributionshiftongraphsizes

TrainTest(noise)Test(color)

TrainTest(large)

Frequency

90%

5%

TreeLadderWheel

BasesofHouseMotif

Distributionshiftongraphstructuresandnodefeatures

TrainTest(moleculesfromunseenscaffolds)

Scaffold1Scaffold44,930Scaffold44,931Scaffold90,124

y=activey=inactivey=activey=inactive

[2]DiscoveringInvariantRationalesforGraphNeuralNetworks,ICLR2022

[3]OOD-GNN:Out-of-DistributionGeneralizedGraphNeuralNetwork,TKDE2022

1.3AssumptionofGraphGeneration

□Stable(Causal)&EnvironmentalFeature

Stablefeature:functionalgroup,e.g.-OH,-COOH

Molecule:Molecule:

Cyclopropanol1,4-cyclohexanediol

Scaffold:Scaffold:

3-carbonring6-carbonring

Environmentalfeature:scaffold,e.g.carbonring,carbonchain

O

Molecule:aceticacid

Scaffold:smallsize

H

Molecule:citricacid

Scaffold:largesize

□Sufficiency&InvarianceAssumption

Assumption3.1.GivenG,thereexistsanoptimalinvariantsubgraphgenerator重*(G)satisfying:

a.Invarianceproperty:Ve,e′∈supp(E),Pe(Y|p*(G))=Pe(Y|p*(G)).

b.Sufficiencyproperty:Y=w*(g*(重*(G)))+6,∈⊥G,whereg*(·)denotesarepresentation

learningfunction,w*istheclassifier;Iindicatesstatisticalindependence,andeisrandomnoise.

[4]LearningInvariantGraphRepresentationsforOut-of-DistributionGeneralization,NeurlPS2022

[5]LearningSubstructureInvarianceforOut-of-DistributionMolecularRepresentations,NeurlPS2022

蚂蚁集团

ANTGROUP

1.4OurMotivations

□PossiblereasonsforpoorperformanceofGNNsonOODtestdata

Stablefeaturesaredifficulttocapture

·StablefeaturesarethekeytoimprovingtheOODgeneralization,whilethe"spuriouscorrelation"indatamakesthemodeltolearn"shortcuts".

Environmentalfeaturesarenotdiscrepantenough

·Thescarcityofthetrainingenvironmentsreducestheperformanceofthemodelinthefaceoftestdatainunknownenvironments.

RelatedStudies

oy

蚂集团DataFun.

蚂蚁集团

ANTGROUP

2.1GraphClassificationMethods

Pooling-orAttention-basedGNNs

Toselectdiscriminativesubgraphsor

featuresingraphdata,poolingor

attention-basedGNNsaregradually

emerging.Representativemodels

includeSAGPool,DiffPool,ASAP.

GraphKernel&GraphMatching

Calculatethesimilaritybetween

graphsbydecomposingthe

completegraphdataintosome

substructure,andthencomparing

thesubstructuresonthegraph.E.g.,

Graphletkernel(GK),Weisfeiler

LehmanKernel(WL).

GraphNeural

Networks(GNNs)

Graphneuralnetworksarebasedon

themessagepassingmechanism.

Thegraphfeatureextractionand

classificationareoptimizedend-to-

end.Representativemodelsinclude

GCN,GIN.

Hiddenlayer

Input

graph

Top-rank

Input

F1

F2

F3

Oupyut

F7

F8

F9

Masking

Attentionmask

Kernel-basedmethodGNNPoolbi

Attention-GNNs

蚂蚁集团

ANTGROUP

2.20ODGeneralization

DistributionallyRobustOptimization(DRO)

Itoptimizestheworstdistributionin

anuncertaindistributionsettoensure

thegeneralizationofthemodelunder

theworstdistribution.The

representativealgorithmisGroup-

DRO.

InvariantLearning

Itlearnsinvariantfeaturesby

minimizingtheempiricalriskin

variousenvironments.Intermsof

implementation,theregularization

constraintproblemisestablishedto

facilitatethesolution.The

representativealgorithmisIRM.

DataAugmentation

Itpointsoutthattherootcauseofthe

poorgeneralizationistheinsufficient

scaleanddiversityofthetrainingdata.

Hence,itaimstoincreasethescale

anddiversityofdata,thereby

improvingthegeneralization.The

representativealgorithmisMixup.

StableLearning

Toremovetheirrelevantfeatures

andspuriouscorrelations,it

simulatestheunbiaseddistribution

ofthedatabyre-weightingtheinput

samples.Therepresentative

algorithmisStableNet.

蚂蚁集团

ANTGROUP

2.3GraphOODGeneralization

MethodsLimitations

GeneralGeneralization

Algorithms

Zhang,etal,ICLR’18.

Sagawa,etal,ICLR'20.

Arjovsky,etal,Arxiv'19.

GraphDataAugmentation

Rong,etal,ICLR2020,Liu,etal,KDD'2022,Han,etal,ICML'2022

Duetotheirregularityofgraph

data,theyaredifficultto

achievesignificant

performanceimprovements.

Theyarepronetodestroythe

stablefeaturesinthedata,

resultingintheinsensitivityto

stablefeatures.

GraphInvariantLearning

Wu,etal,ICLR22(a),

Wu,etal,ICLR22(b),Li,etal,NeurlPS22.

Theyaredifficulttoimprovetheenvironmentaldiscrepancy.

03

CausalAttentionLearning

oy

蚂集团DataFun.

Learning(CAL)

P

3.1CausalAttention

ExistingIssue:Stablefeaturesaredifficulttocapture

OurIdea:AnalyzingtheGNNmodelingfromacausalview

E

G⑤-RY

□StructuralCausalModel(SCM)forgraphclassification

E

G=⑤=R

Y

G:Graphdata

S:Stablefeature

E:EnvironmentalfeatureR:Representation

口Backdoorpath

Y:Prediction/Label

S←G→E→R→Y

□Potentalproblem

·Themodelwilllearnthe“shortcuts”.

·These"shortcuts"maynotexistoutsidethetrainingdistribution,resultinginpoorOODgeneralization.

CausalAttentionforInterpretableandGeneralizableGraphClassification,KDD2022

AttentionLearning(CAL)

蚂蚁集团

ANTGROUP

Fun.

3.1Causal

TheoryandMethodDesign:CausalInterventions口BackdoorAdjustment

P(Y|do(S))=Pm(Y|S)

(BayesRule)

(Independency)

CausalAttentionforInterpretableandGeneralizableGraphClassification,KDD2022

CausalAttentionforInterpretableandGeneralizableGraphClassification,KDD2022

3.1CausalAttentionLearning(CAL)

□CausalAttentionLearning(CAL)

Estimatingattention

Disentanglement

Causalintervention

Graphs

GNNEncoder

EdgeAttentionNodeAttention

TrivialAttended-graphCausalAttended-graph

GraphConvGraphConv

ReadoutReadout

Classifier

RandomAddition

Label

Classifier

Class

One-hot

Classifier

Uniform

Lunif

Lsup

Label

Class

CausalAttentionforInterpretableandGeneralizableGraphClassification,KDD2022

3.1

ANTGROUP

CausalAttentionLearning(CAL)蚂蚁集团

□CausalAttentionLearning(CAL)

Estimatingattention

Disentanglement

Causalintenvention

Graphs

GNNEncoder

NodeAttention

EdgeAttention

TrivialAttended-graphCausalAttended-graph!

GraphConyGraphConv

R

do8

ReadoutReadout

Classifier

Luif

ClassifierLsup

RandomAddition

UniformLabel

One-hotLabel

Classifier

Class

Class

01

CausalAttentionforInterpretableandGeneralizableGraphClassification,KDD2022

3.

ANTGROUP

1CausalAttentionLearning(CAL)蚂蚁集团

□CausalAttention

Graphs

Learning(CAL)

GNNEncoder

Edge

TrivialAttended-graph

Attention

AttentionNode

CausalAttended-graph

Gc={AoMa,XoMx}

Gt={AOMa,XoMx}

Estimatingattention

GraphConvGraphConv

Disentanglement

Causalintervention

ReadoutReadout

Casifier-Lsup

Lunif←Classifier

RandomAddition

one-hotLabel

UniformLabel

Classifier

closs.

class

3.1CausalAttentionLearning(CAL)P

CausalAttentionforInterpretableandGeneralizableGraphClassification,KDD2022

Graphs

□CausalAttentionLearning(CAL)

GNNEncoder

EdgeAttentionNodeAttention

Gc={A◎Ma,XoMx}

Gt={AoMa,XoMx}

-20bmca)

Lmif=四∑KI(Yumi,2,)

Estimating_attention

Disentanglement

Causalintervention

TrivialAttended-graphCausalAttended-graph

GraphConvGraphConv

ReadoutReadout

Lunif←ClassifierClassifier→Lsup

RandomAddition

UniformLabelOne-hotLabel

Classifier

ClassClass

3.1CausalAttentionLearning(CAL)

CausalAttentionforInterpretableandGeneralizableGraphClassification,KDD2022

□Experimentsonsyntheticdatasets

Table1:TestAccuracy(%)ofgraphclassificationonsyntheticdatasetswithdiversebiases.Thenumberinbracketsrepresentstheperformancedegradationcomparedwiththeunbiaseddataset.Ourmethodsarehighlightedwithagraybackground.

Method

SYN-0.1

SYN-0.3

Unbiased

SYN-0.7

SYN-0.9

GATv2[4]

87.25(↓7.37%)

92.19(↓2.12%)

94.19

93.31(↓0.93%)

90.62(↓3.79%)

SuperGAT[16]

83.81(↓12.75%)

91.94(↓4.29%)

96.06

88.50(↓7.89%)

82.81(↓13.79%)

GlobalAtt[22]

87.19(↓10.40%)

93.75(↓3.66%)

97.31

94.62(↓2.76%)

91.50(↓5.97%)

AGNN[33]

84.56(↓11.69%)

93.06(↓2.81%)

95.75

94.81(↓0.98%)

88.12(↓7.97%)

DiffPool[45]

82.28(↓8.69%)

88.02(↓2.32%)

90.11

88.83(↓1.42%)

84.50(↓6.23%)

SortPool[49]

80.70(↓14.24%)

92.33(↓1.88%)

94.10

92.14(↓2.08%)

90.35(↓3.99%)

Top-kPool[10]

84.31(↓11.81%)

93.53(↓2.17%)

95.60

94.44(↓1.21%)

88.02(↓7.93%)

SAGPool[19]

88.08(↓7.82%)

90.86(↓4.91%)

95.55

92.22(↓3.49%)

83.99(↓12.10%)

GCN[17]

84.94(↓6.60%)

89.38(↓1.72%)

90.94

90.25(↓0.76%)

86.00(J5.43%)

GCN+CAL

89.38(↓6.03%)

93.50(↓1.70%)

95.12

95.06(10.06%)

93.31(↓1.90%)

GIN[41]

87.50(↓9.55%)

93.94(J2.89%)

96.74

94.88(↓1.92%)

89.62(↓7.36%)

GIN+CAL

93.19(↓3.87%)

96.31(↓0.65%)

96.94

96.56(↓0.39%)

95.25(↓1.74%)

GAT[35]

84.62(↓8.71%)

89.50(↓3.44%)

92.69

92.31(↓0.41%)

87.62(↓5.47%)

GAT+CAL

92.44(↓4.37%)

96.25(↓0.42%)

96.66

96.12(↓0.56%)

92.56(↓4.24%)

3.1CausalAttentionLearning(CAL)P

CausalAttentionforInterpretableandGeneralizableGraphClassification,KDD2022

□Furtheranalysis

Figure7:Visualizationsofcausalattended-graphs.(Left):

Syntheticgraphs,(Right):MNISTsuperpixelgraphs.

GCNGCN+CAL

GroundTruths

56.6%17.2%

90.9%9.1%27.4%

60.0%

33.3%16.7%50.0%

60.0%40.0%0.0%

1.1%

90.0%3.3%6.796

26.2%

0.0%

BA-DiamTreeHouse

0.0%40.0%

100%

11.8%71.8%16.5%

12.5%87.5%0.0%7.3%78.0%14.6%6

12.5%12.5%75.0%

50%

33.3%33.3%33.3%640.0%60.0%0.0%70.0%30.0%0.0%

68.4%0.0%31.6%

0%

75%

25%

PredictedlabelsPredictedlabels

Figure8:Themisclassificationdistribution.Redcirclehigh-lightstheconcentrationdegreeofmisclassification.

04

AdversarialInvariantAugmentation

oy

蚂蚁集团pDataFun.

DataFunSummit#2023

蚂蚁集团

ANTGROUP

4.1AdversarialInvariantAugmentation

□CorrelationShiftv.s.CovariateShift

Thejointdistributionoftrainingandtestdataasptr(G,Y)andpte(G,Y)

Distributionshiftmeansthatptr(G,Y)≠pte(G,Y)

ptr(G,Y)=ptr(Y|G)ptr(G)

pteG,Y=pte(Y|G)pte(G)

G

G

Correlationshift:ptr(G)=pte(G)butptr(Y|G)≠pte(Y|G)Ge

Covariateshift:pu(G≠pte(G)butptr(Y|G)=pte(Y|G)GraphDataGeneration

Ourscope:thesedistributionshiftsmainlycausedbytheenvironmentalfeatures.

[1]OoD-Bench:QuantifyingandUnderstandingTwoDimensionsofOut-of-DistributionGeneralization,CVPR2022

[6]GOOD:AGraphOut-of-DistributionBenchmark,NeurIPS2022

蚂蚁集团

ANTGROUP

4.1AdversarialInvariantAugmentation

un.

□CorrelationShiftv.s.CovariateShift

PACS

Camelyon

Cow&CamelColoredMNIST

TestTraining

Covariateshift

e.g.DomainGeneralization

Correlationshift

[1]OoD-Bench:QuantifyingandUnderstandingTwoDimensionsofOut-of-DistributionGeneralization,CVPR2022

4.1AdversarialInvariantAugmentation

□CorrelationShiftv.s.CovariateShift

Stablefeature

Y₂:Cycle

Environmentalfeature

e₁:Treee₂:Ladder

DataGenerationMechanism

ptr(G)=pte(G)

Trainingdata

pu(Y|G)=pte(Y|G)

UnleashingthePowerofGraphDataAugmentationonCovariateDistributionShift,NeurlPS2023

蚂蚁集团

ANTGROUP

4.1AdversarialInvariantAugmentation

ExistingIssue:Insufficientdiscrepancyofenvironmentalfeatures

□GraphCovariateShift

S={g∈G|Ptr(g)·Pte(g)=0}

Scaffold1

y=active

Train

Scaffold44,930

y=inactive

Test(moleculesfrom

Scaffold44,931

y=active

unseenscaffolds)

Scaffold90,124

y=inactive

□OurIdea

·Usingdataaugmentationtoincreasetheenvironmentaldiscrepancy

UnleashingthePowerofGraphDataAugmentationonCovariateDistributionShift,NeurlPS2023

UnleashingthePowerofGraphDataAugmentationonCovariateDistributionShift,NeurlPS2023

4.1AdversarialInvariantAugmentation

口TwoPrinciplesforGraphAugmentation

·Principle1(EnvironmentalFeatureDiscrepancy):Environmentalfeatures

shouldkeepdiscrepantduringaugmentation

Principle3.1(EnvironmentalFeatureDiscrepancy)Givenagraphset{g}withdistributionfunc-tionP,letT(·)denoteanaugmentationfunctionthataugmentsgraphs{T(g)}todistributionP.ThenT(·)shouldmeetGCS(P,P)→1.

·Principle2(StableFeatureConsistency):Stablefeaturesshouldkeepconsistencyduringaugmentation

Principle3.2(StableFeatureConsistency)Givenasetofgraphs{g}withacorrespondingstablefeatureset{9sta=(Asta,Xsta)}.LetT(·)denoteanaugmentationfunctionthataugmentsgraphs{T(g)}withacorrespondingstablefeatureset{9sta=(Ästa,Xsta)}.ThenT(·)shouldmeetE[I|Asta-Astal1².]→0andIE[|Xsta-Xstall².]→0,where||·leistheFrobeniusnorm.

蚂蚁集团

ANTGROUP

4.1AdversarialInvariantAugmentation

UnleashingthePowerofGraphDataAugmentationonCovariateDistributionShift,NeurlPS2023

□DistributionallyRobustOptimization

WassersteinDistance

TransportationCost

Lagrangianrelaxation

ANTGROUP

4.1AdversarialInvariantAugmentation蚂蚁集团

UnleashingthePowerofGraphDataAugmentationonCovariateDistributionShift,NeurlPS2023

□Robustsurrogateloss:φ(f(g),y)

φ(f(9),y):=supgeG{l(f(⑨),y)-γc(g,g)}

口AdversarialAugmentation

▽oφ(f(g),y)=▽el(f(g*),y),

whereg=argg∈Gmax{l(f(9),y)-γc(g,g)}.

ANTGROUP

4.1AdversarialInvariantAugmentation蚂蚁集团

UnleashingthePowerofGraphDataAugmentationonCovariateDistributionShift,NeurlPS2023

口AdversarialAugmenter&StableFeatureGenerator

To₂(g)

StableFeaturesAugmentedGraphs

GNN

Classifier

Trainingtime

EnvironmentalFeatures

AdversarialAugmenter

StableFeatureGenerator

InputGraph

Te₁(g)

4.1AdversarialInvariantAugmentation

UnleashingthePowerofGraphDataAugmentationonCovariateDistributionShift,NeurlPS2023

□Maximization

To₂(g)

StableFeatureGenerator

GNN

InputGraph

Trainingtime

EnvironmentalFeatures

AdversarialAugmenter

AugmentedGraphs

StableFeatures

Classifier

Te₁(g)

蚂蚁集团

ANTGROUP

4.1AdversarialInvariantAugmentation

UnleashingthePowerofGraphDataAugmentationonCovariateDistributionShift,NeurlPS2023

□Minimization

adv+Mcauadv+Mcau

min{Ccau=EP.[e(f(To₂(9),y)+e(f⑨),y)]}

Te₂(g)

StableFeatures

GNN

Classifier

Trainingtime

EnvironmentalFeatures

AdversarialAugmenter

StableFeatureGenerator

InputGraph

AugmentedGraphs

To₁(g)

UnleashingthePowerofGraphDataAugmentationonCovariateDistributionShift,NeurlPS2023

4.1AdversarialInvariantAugmentation

□MaskCombination

0.in{Ccau=IEp.[e(f(To₂(9)),y)+e(f(⑨),y)]}

To₂(g)

StableFeatureGenerator

InputGraph

Trainingtime

EnvironmentalFeatures

AdversarialAugmenter

To₁(g)

StableFeatures

蚂蚁集团

ANTGROUP

4.1AdversarialInvariantAugmentation

UnleashingthePowerofGraphDataAugmentationonCovariateDistributionShift,NeurlPS2023

□TheoreticaDiscussions

Proposition4.1ConsideraprobabilitydistributionPdefinedoverameasurablespace(Ω,F),whereSdenotesthesamplespaceandFisaσ-algebraonSΩ.WeconstructtwoWassersteinballswithPattheircenterandradiipiandp₂respectively.UtilizingEquationB,wegeneratetwodistinctdistributions,P₁andP₂,withinthespace(Ω,F).If(i)Pisanisotropicdistribution;(ii)3x₁,a₂∈ΩsuchthatP(x)=P₁(x-x₁)=P₂(x-x₂);(ii)p₁<P₂,thenwehaveGCS(P,P₁)≤GCS(P,P₂).

Conclusion:Ourobjectiveoptimizationcaneffectivelyamplifythe

covariateshiftbetweenthetrainingandgenerateddistributions.

UnleashingthePowerofGraphDataAugmentationonCovariateDistributionShift,NeurlPS2023

4.1AdversarialInvariantAugmentation

>RQ1:Comparedtoexistingefforts,howdoesAIAperformunderCovariateshift?

Table1:Performanceonsyntheticandreal-worlddatasets.Numbersinboldindicatethebestperformance,whiletheunderlinednumbersindicatethesecondbestperformance.

Type

Method

Motif

CMNIST

Molbbbp

Molhiv

base

size

color

scaffold

size

scaffoldsize

General

Generalization

ERM

IRM

GroupDRO

VREx

68.66+4.25

70.65±4.17

68.24±8.92

71.47±6.69

51.74+2.88

51.41+3.78

51.95+5.86

52.67+5.54

28.60+1.87

27.83+2.13

29.07+3.14

28.48+2.87

68.10±1.68

67.22±1.15

66.47+2.39

68.74±1,03

78.29+3.76

77.56+248

79.27+2.43

78.76+237

69.58+2.5159.94+2.37

67.97±1.8459.00±2.92

70.64+2.5758.98+2.16

70.77+2.8458.53+2.88

Graph

Generalization

DIR

CAL

GSAT

OOD-GNN

StableGNNCIGA

DisC

62.07±8.75

65.63+4.29

62.80±114161.10+7.87

57.07±14.10

66.43+11.31

51.08±3.08

52.27±4.56

51.18+5.60

53.20±8.35

52.61+4.67

46.93±8.8549.14±8.3450.39±1.15

33.20+6.17

27.99+3.24

28.17±1.26

26.49+2.94

28.38±3.49

32.22+267

24.99+1.78

66.86+2.25

68.06+2.60

66.78±1.45

66.72+1.23

66.74±1.30

64.92+2.09

67.12+2.11

76.40+4.43

79.50+4.81

75.63+3.83

79.48+4.19

77.47+4.69

65.98+3.31

56.59±10.09

68.07+2.2958.08+2.31

67.37+3.6157.95+2.24

68