上海后花园论坛(爱上海419论坛/阿拉爱上海同城)

上海品茶

1-4 曲率视角下的图网络建模与分析.pdf

上传人：云闲

编号：102286

2021-01-01

PDF 51页 4.85MB

《1-4 曲率视角下的图网络建模与分析.pdf》由会员分享，可在线阅读，更多相关《1-4 曲率视角下的图网络建模与分析.pdf（51页珍藏版）》请在三个皮匠报告上搜索。

1、曲率视角下的图数据分析与学习周敏华为诺亚方舟实验室主任工程师|自我介绍|本科毕业于中科大，博士毕业于新加坡国立大学 2017年入职华为诺亚方舟实验室研究方向:图数据、序列数据模式挖掘和学习产产业业会会战战行行业业军军团团01Curvatures02Curvature on Network03Curvature on Surface04Conclusion目录目录 CONTENT|Curvatures01|Networks|Source:Internet(left):https:/ available in the form of networks are ubiquitous(socia

2、l networks,telecom network,drug interaction etc.)Network(Graph）Analysis&Learning|Graph structureDegree distributionGraph diameterShortest path lengthSparsenessGraph GeometryCurvatureRepresentation Learning Graph embeddingGraph Neural NetworkCurvature?|A geometric property:Flatness of an objectGeomet

3、ric intuition:Measure for growth rate of volume of distance ball“geodesic dispersion”Eidi M,Jost J.Ollivier ricci curvature of directed hypergraphsJ.Scientific Reports,2020,10(1):1-14.Curvature in Geometry|How do we know that the earth is not flat?Figure from internetSectional curvature&Ricci Curvat

4、ure|Consider a tangent vector =and another tangent vector at.Transport along to be a tangent vector at y.Ricci Curvature:averaging over all directions Curvature on Surfaces vs.on Network|Networks as Geometric Objects|Understanding the corresponding complex networks via the lens of curvatureIntrinsic

5、Discrete Ricci Curvature-Ollivier-Ricci Curvature-Forman Ricci Curvature-Other NotionsExtrinsicLearning Space-Euclidean Space-Hyperbolic Space-Mixed-Curvature SpaceCurvature on Network02|Discrete Ricci Curvature|Ollivier-Ricci curvatureForman-Ricci curvature Basic idea：Optimal transport Emphasizes c

6、lustering Basic idea：Dispersion Emphasize network dynamicSource：Comparative analysis of two discretizations of Ricci curvature for complex networksFroman-Ricci Curvature|Quantifies the degree of spread of the vertices Consider trianglesas faces，and uvis the number of triangles that contain u,v.All e

7、dges have weight 1.Ollivier-Ricci Curvature|For an edge xy,consider the distance from xs neighbors to ys neighbors and compare it with the length of xyHow to compute the distance of xs neighbors to ys neighbors?Optimal transport distance Source:Graph Ricci Flow and Applications in Network Analysis a

8、nd Learning by Prof.Jie GaoCurvature on Network|Zero Curvature:2D gridCurvature on Network|Negative curvature:,=1+1 1,is degree of x.Curvature on Network|Positive Curvature:Complete graph Curvature Distribution on Network|Positive curvature within community Negatively curved edges are the“backbones”

9、,connecting the clusters Ni,Chien-Chun,et al.Ricci curvature of the internet topology.2015 IEEE conference on computer communications(INFOCOM).IEEE,2015.Network Curvature for market fragility analysisSia J,Jonckheere E,Bogdan P.Ollivier-ricci curvature-based method to community detection in complex

10、networksJ.Scientific reports,2019,9(1):1-12.Ollivier-riccicurvature as a crash hallmark to model asset returns.Network Curvature for Community DetectionSia J,Jonckheere E,Bogdan P.Ollivier-ricci curvature-based method to community detection in complex networksJ.Scientific reports,2019,9(1):1-12.Olli

11、vier-ricci curvature as a natural metric to discover hierarchies in graphs.Network Curvature for brain structural analysisFarooq H,Chen Y,Georgiou T T,et al.Network curvature as a hallmark of brain structural connectivityJ.Nature communications,2019,10(1):1-11.Network Curvature for guiding message p

12、assingYe Z,Liu K S,Ma T,et al.Curvature Graph NetworkC/International Conference on Learning Representations.2019.Network Curvature for alleviating over-squashingTopping J,Di Giovanni F,Chamberlain B P,et al.Understanding over-squashing and bottlenecks on graphs via curvatureC/International Conferenc

13、e on Learning Representations.2021.Curvature on Surface03|Representation Learning|Embedding data into a continuum space is at the heart of representation learningFigure source:InternetRepresentation Learning|The quality embeddings crucially depends on whether the geometry of the space matches the da

14、tasetSource:Curvature and Representation Learning:Identifying Embedding Spaces for Relational DataRepresentation Learning|Euclidean geometry not suitable for many graphs(cycles,trees.)Graph distance(,)=“shortest path from i to j”Figure source:https:/people.csail.mit.edu/oct/ctgnn_slides.pdfWhy hyper

15、bolic space？|Many Network are with tree-like structures or power-law distributed.|Embedding TreesNodes grow exponentiallyHyperbolic modelsLorentz model and Poincare ball modelHyperbolic Graph Convolutional Neural Networks(right););https:/ radius(1)Acts as a geometric prior for hierarchical structure

16、s/tree graphs/heavy tailed distributions(e.g.scale-free,power-law).*(2)Larger embedding space-smaller embedding dimension and fewer parameter Hyperbolic EmbeddingsNickel M,Kiela D.Poincarembeddings for learning hierarchical representationsJ.Advances in neural information processing systems,2017,30.(

17、Hyperbolic)Graph Neural Networks(a)Input graph(b)Neighborhood aggregationTarget NodeGraph Neural Network,=Msg,(1/3)Message,=AGG1,(2/3)Aggregation ,=Update1,(3/3)UpdateChami,Ines,et al.Hyperbolic graph convolutional neural networks.Advances in neural information processing systems 32(2019).Hyperbolic

18、 Graph Neural NetworksHGNN arranges nodes in a more hierarchically way.Hyperbolic Space for word representations Chen B,Fu Y,Xu G,et al.Probing BERT in Hyperbolic SpacesC/International Conference on Learning Representations.2020.Hyperbolic Space for knowledge graph embeddingBai Y,Ying Z,Ren H,et al.

19、Modeling heterogeneous hierarchies with relation-specific hyperbolic conesJ.Advances in Neural Information Processing Systems,2021,34:12316-12327.Hyperbolic Space for Drug GenerationYu,Ke,Shyam Visweswaran,and Kayhan Batmanghelich.Semi-supervised hierarchical drug embedding in hyperbolic space.Journ

20、al of chemical information and modeling 60.12(2020):5647-5657.Hyperbolic spaces help inject hierarchies knowledge for drug generation.Hyperbolic Space for Cell AnalyzingKlimovskaia,Anna,et al.Poincarmaps for analyzing complex hierarchies in single-cell data.Nature communications 11.1(2020):1-9.Hyper

21、bolic maps discover hierarchies and branching processes.Hyperbolic Space for Image RetrievalYan J,Luo L,Deng C,et al.Unsupervised hyperbolic metric learningC/Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition.2021:12465-12474.Hyperbolic Space for Recommender SystemYang

22、 M,Zhou M,Liu J,et al.HRCF:Enhancing collaborative filtering via hyperbolic geometric regularizationC/Proceedingsof the ACM Web Conference 2022.2022:2462-2471.User-item networkEuclideanspaceHyperbolic spaceUnpopular items(low-level)Popular items(High-level)Lightweightnessw.r.t.the Embedding SizeRobu

23、stness w.r.t Aggregation Order-Convergent Speed w.r.t Training EpochsHyperbolic Space for dynamic link predictionYang M,Zhou M,Kalander M,et al.Discrete-time temporal network embedding via implicit hierarchical learning in hyperbolic spaceC/Proceedings of the 27th ACM SIGKDD Conference on Knowledge

24、Discovery&Data Mining.2021:1975-1985.Challenges&OpportunitiesDomain Applications Complex StructuresEvolving InteractionsGeometry-aware LearningTrustworthy and ScalabilityYang M,Zhou M,Li Z,et al.Hyperbolic Graph Neural Networks:A Review of Methods and ApplicationsJ.arXiv preprint arXiv:2202.13852,20

25、22.Take-home messagesCurvature is an promising tool to understand and analyze networksIntrinsic:topology measure Extrinsic:Learning space IntrinsicDiscrete Ricci Curvature-Ollivier-Ricci Curvature-Forman Ricci Curvature-Other NotionsExtrinsicLearning Space-Euclidean Space-Hyperbolic Space-Mixed-Curvature Space非常感谢您的观看|Resource|SurveyHyperbolic Graph Neural Networks:A Review of Methods and ApplicationHyperbolic Deep Neural Networks:A SurveyToolsGeoopt:https:/ Tutorialhttps:/