How to exploit network properties to improve learning in relational domains Jennifer Neville Departments of Computer Science and Statistics Purdue University ! ! ! ! (joint work with Brian Gallagher, Timothy La Fond, Sebastian Moreno, Joseph Pfeiﬀer and Rongjing Xiang) Relational network classification examples Predict organizational roles from communication patterns Email networks! Predict protein function from interaction patterns Gene/protein networks! Predict paper topics from properties of cited papers Scientific networks! Predict content changes from properties of hyperlinked pages World wide web! Predict personal preferences from characteristics of friends Social networks! Predict group eﬀectiveness from communication patterns Organizational networks! Network data is: heterogeneous and interdependent, partially observed/labeled, dynamic and/or non-stationary, and often drawn from a single network ...thus many traditional ML methods developed for i.i.d. data do not apply Machine learning 101 choose 1 Data representation 2 Linear equation Generic form is: Knowledge representation y = "1 x1 + " 2 x 2 ...+ " 0 An example for the Alzheimer’s data would choose defines !CDR = 0.12MM1+ 0.34SBScore..." 0 Machine learning 101 Model space defines combine a would be: 3 re..." 0.34 Objective |D| X 1 Lsq (D) = (f (xi ) N i=1 function choose yi ) 2 Machine learning 101 (eg . op Search timiz ati algorithm o 4 combine n) Learning identifies model with max objective function on training data Model is applied for prediction on new data from same distribution Relational learning Machine learning 101 1 2 Data representation Knowledge representation Email networks! 3 Objective function relational data Social networks! Scientific networks! relational models Bn Bn Firm Broker (Bk) Disclosure Branch (Bn) Bn Size 4 Search algorithm Gene/protein networks! Problem In Past Has Business Is Problem On Watchlist Year Bk Region Type Bk Area Bk Layoffs Bn On Watchlist World wide web! Organizational networks! Bn Bk There has been a great deal of work on templated graphical model representations for relational data RBNs RMNs MLNs GMNs d e e n e w l a icRDNs h p a r g IHRMs o s l a s i n o i ks t r a t o n w e t s e e n r l p e d re o l DAPER e m d o m o m r PRMs f e c s rk Sin o w t e n a t a d h s i u g n i t s i to d Data network Gender? Married? Politics? Religion? Data network 1 Data representation F Y D !C M Y C C Relational learning task: E.g., predict political views based on user’s intrinsic attributes and political views of friends F N D !C M Y D C F N D !C M N C C F N C !C F Y D C (Y|{X}n , G) Estimate joint distribution: PAttributed network or conditional distribution: P (Yi |Xi , XR , YR ) a y l n o e v a nh e t f o e g w n i e n t r a No e l r fo k r o w t e n e singl Define structure of graphical model Politicsi Politics j Politicsi Gender i Politicsi Married i Politics Religion i i Relational template Yi Yj Relational template 1 Yi Xi Yi Xi Yi Xi 2 3 Model template Yi Yj Yi Xi Yi Xi Yi Xi 1 + 2 3 Model template Data network 2 Knowledge representation 2 2 X2 X8 X12 X21 1 1 X32 X24 Y2 3 1 X 1 X X14 Y1 1 3 3 3 X X Y3 X34 X15 2 6 X 1 6 X35 Y5 3 6 X X Y6 X8 Y8 X25 Y4 X23 3 X8 X27 X17 X37 Y7 Model network (graphical model) 3 Objective function Search: eg. convex optimization 4 2 2 X2 X8 X12 X21 1 1 X32 X24 Y2 3 1 X 1 X X14 Y1 1 3 3 3 X X34 X15 X Y3 2 6 X 1 6 X35 Y5 3 6 X X Y6 X8 Y8 X25 Y4 X23 3 X8 X27 X17 X37 Y7 Learn model parameters from fully labeled network P (yG |xG ) = 1 Z( , xG ) T (xC , yC ; T ) T T C C(T (G)) Apply model to make predictions in another network drawn from the same distribution X21 Yi Y j X11 1 Yi Xi Yi Xi Yi X12 3 1 X Y1 + Y2 X13 X33 Y3 X25 X15 X34 Y4 X23 3 X8 Y8 X24 X14 Xi Model template 1 X8 X32 2 3 X28 X22 Y5 X26 X16 X36 Y6 X35 X27 X17 X37 Y7 Test network Collective classification uses full joint, rolled out model for inference… but labeled nodes impact the final model structure 2 1 X X11 2 1 X X X Y2 Y1 2 81 2 2 X X 1 3 2 1 3 1 X1 X1 Y1 2 2 1 2 X32 1 X8 X32 Y2 2 X X3 X23 X13 X3 X33Y4 3 Y3 Y8 X24 X14 Y4 1 3 X X8 X X28 X38 3 X8 Y8 X25 X15 X34 Y4 Y4 X26 1 6 Y4 X Y3 Labeled node X16 Y6 X15 Y5 2 36 X X6 Y6 X3 25 X5 X35 2 Y5 X7 X2 1 37 X X 7 7 X17 X37 X36 Y7 Y7 Collective classification uses full joint, rolled out model for inference… but labeled nodes impact the final model structure The structure of “rolled-out” relational X X X X X X graphical models are determined by the Y Y Y Y X X structure of the underlying data network, X X X X including location + availability of labels Y Y X X X X X X X X X …this can impact performance of LabeledlearningY and inference Y Y methods , n o i t a node present X21 1 1 11 22 3 1 11 2 X828 X2222 11 88 33 22 22 44 22 11 44 22 33 11 33 22 55 88 11 55 33 44 33 55 22 66 44 33 33 33 33 88 11 66 33 66 66 22 77 55 11 77 33 77 77 , n via re o i t c n u f e v i t c e hm t i obj r o g l a h c r a e s and Networks are much, much larger in practice… Finding 1: Representation Implicit assumption is that nodes of the same type should be identically distributed—but many relational representations cannot ensure this holds for varying graph structures I.I.D. assumption revisited • Current relational models do not impose the same marginal invariance condition that is assumed for IID models, which can impair generalization p(yA |xA ) A B E C D F p(yE |xE ) p(yA |xA ) 6= p(yE |xE ) due to varying graph structure • Markov relational network representation does not allow us to explicitly specify the form of the marginal probability distributions, thus it is diﬃcult to impose any equality constraints on the marginals Is there an alternative approach? • Goal: Combine the marginal invariance advantages of IID models with the ability to model relational dependence • Incorporate node attributes in a general way (similar to IID classifiers) • Idea: Apply copulas to combine marginal models with dependence structure t1 t2 t3 ... tn t jointly ~ Copula theory: can construct n-dimensional vector( of 1) arbitrary zi = F i ( i (ti )) marginals while preserving the desired dependence structure F z1 z2 z3 ... zn zi marginally ~ Fi Let’s start with a reformulation of IID classifiers... • General form of probabilistic binary classification: p(yi = 1) = F (⌘(xi )) • e.g., Logistic regression • Now view F as the CDF of a distribution symmetric around 0 to obtain a latent variable formulation: zi ⇠ p(zi = z|xi = x) = f (z ⌘(xi )) ! yi = sign(zi ) • z is a continuous variable, capturing random eﬀects that are not present in x • p is the corresponding PDF of F • In IID models, the random eﬀect for each instance is independent, thus can be integrated out • When links among instances are observed, the correlations among their class labels can be modeled through dependence among the z’s • Key question: How to model the dependence among z’s while preserving the marginals? ? Zj Copula Latent Markov Network (CLMN) IID classifiers CLMN The CLMN model • Sample t from the desired joint dependency: (t1 , t2 , . . . , tn ) ⇠ to obtain • Apply marginal transformation ( 1) the latent variable z: zi = Fi • Classification: yi = sign(zi ) ( i (ti )) Marginal Φi transforms ti to uniform [0,1] r.v. ui Quasi-inverse of CDF Fi is used to obtain zi from ui, Attributes moderate corresponding pdf fi Copula Latent Markov Network (Xiang and N. WSDM‘13) CLMN implementation Estimation: • First, learn marginal model as if instances were IID Gaussian Markov network Logistic regression • Next, learn the dependence model conditioned on the marginal model... but GMN has no parameters to learn Inference: • Conditional inference in copulas have not previously been considered for largescale networks • For eﬃcient inference, we developed a message passing algorithm based on EP Experimental Results CLMN SocDim RMN Key idea: Ensuring that nodes with varying graph Facebook GMN LR structure have identical marginals improves learning IMDB Gene IMDB Finding 2: Search Graph+attribute space is too large to sample thoroughly, but efficient generative graph models can be exploited to search more eﬀectively How to efficiently generate attributed graph samples from the underlying joint distribution P (X, Y, G) ? V 2 +V ·p Space is O(2 ) so effective sampling from joint is difficult Naive sampling approach: Assume independence between graph/attributes PE (X, E|⇥E , ⇥X ) = PE (E|⇥E )P (X|⇥X ) Attributes Graph Model Attribute Model Problem with naive approach by d e r u t p ca e b n a te c u b e i r r t u t t a c u h it tr s w h g p n i a r r i g a p Sampled n e v o i i t a a n l , e Although hOriginal s r l or de c o l m a n o p i a t gr la e e r v i t e r a r u e t p a gen c t o n es o d s e l p sam 0-0 1-1 0-1 Attribute value combinations Solution: Use graph model to propose edges, but sample conditional on node attribute values PE (X, E|⇥E , ⇥X ) = PE (E|X, ⇥E , ⇥X )P (X|⇥E , ⇥X ) Attributes Graph Model t c e j e t-R p e c c A e l use p m a s o t s s e c s r t t pro a n o d e n o i t i cond Attribute Model Exploit efficient generative graph model as proposal distribution to search effectively • What to use as acceptance probabilities? Ratio of observed probabilities in original data to sampled probabilities resulting from naive approach ! ! ! ! ! Original Sampled Original 0-0 1-1 0-1 Attribute value combinations 0-0 1-1 0-1 Attribute value combinations • This corresponds to rejection sampling • Proposing distribution: PE (Eij = 1|⇥E ) • True distribution: Po (Eij = 1|f (xi , xj ), ⇥E , ⇥X ) 33 Attributed graph models (Pfeiffer, La Fond, Moreno, N & Gallagher WWW’14) # # # # ! Learn attribute and graph model Generate graph with naive approach Compute acceptance ratios Sample attributes while not enough edges: draw (vi,vj) from Q’ (the model) U ~ Uniform(0,1) if U < A(xi, xj) put (vi, vj) into the edges return edges 0-0 1-1 Attribute value combinations a e Possible Edges b b d f g h 0-1 c f g i h Theorem 1: AGM samples from the joint distribution of edges and attributes P (Eij = 1|f (xi , xj ), ⇥E , ⇥F )P (xi , xj |⇥X ) Corollary 2: Expected AGM degree equals expected degree of structural graph model Empirical results on Facebook data Correlation Political views 0.4 AGM preserves 0.3 characteristics Key idea: Statistical models of graphs of graph model can be exploited to improve sampling from full jointPE (E, X|⇥ E , ⇥ X ) 0.2 AGM captures attribute correlation 0.1 AGM No AGM 0.0 Facebook AGM-KPGM (2x2) TCL AGM-FCL AGM-KPGM (3x3) KPGM (2x2) AGM-TCL FCL KPGM (3x3) Relational learning 1 Data representation 2 Knowledge representation Representations affect our ability to enforce invariance assumptions Objective function Conventional obj. functions do not behave as expected in partially labeled networks Search algorithm Simpler (graph) models can be used to statistically “prune” search space 3 4 (not in this talk) Conclusion • Relational models have been shown to significantly improve predictions through the use of joint modeling and collective inference • But since the (rolled-out) model structure depends on the structure of the underlying data network… • …we need to understand how the data graph aﬀects model/algorithm characteristics in order to better exploit relational information for learning/prediction • A careful consideration of interactions between: data representation, knowledge representation, objective function, and search algorithm will improve our understanding of mechanisms that impact performance and this will form the foundation for improved algorithms & methodology Thanks to: Alum ni Hoda Eldardiry Rongjing Xiang Chris Mayfield Karthik Nagaraj Umang Sharan Sebastian Moreno Nesreen Ahmed Hyokun Yun Suvidha Kancharla Tao Wang Timothy La Fond Joel Pfeiﬀer Ellen Lai Pablo Granda Hogun Park Questions? ! [email protected] www.cs.purdue.edu/~neville

© Copyright 2018