1、Anomaly Detection in Graphs,Yang YangZhejiang University,Including joint work with Yifei Sun,Ziwei Chai,Junru Chen,Xuan Yang ZJU;Jiarong Xu FDU;Chunping Wang and Lei Chen FinVolution;Yizhou Sun UCLA.,Yang Yang(杨洋),Associate Professor,Zhejiang UniversityDean of AI DepartmentPh.D.from Tsinghua Univers

2、ity 2016(advised by Jie Tang and Juanzi Li)Visit Cornell 2012(work with John Hopcroft)Visit KU Leuven 2013(work with Sien Moens)Research:artificial intelligence in networks and deep learning for large-scale dynamic time-series.,Anomaly Detection,Computational Social Science,Representation Learning,A

3、pplications,Research,Social and Information Network,Time Series Modeling via Graphs,Anomaly Detection in Real World,Telecom,E-commerce,Games,Finance,Society,Energy,500 million phone frauds at a cost of$16.4 billion in 2021,GDP in India was reported to drop 1.5%due to electricity theft,4.8 million pe

4、ople were identified theft and fraud,1.1 billion game bots banned over 6 months,Payment card fraud losses reached$27.85 billion in 2018,The value of potential fraud across online retailers faced a loss of$60 billion,Recovery Process after COVID Lockdowns,We use 76 million electricity consumption rec

5、ords of 10K organizations spanning two years to measure the recovery process of different sectors.,Xuan Yang,Yang Yang,Chenhao Tan,Yinghe Lin,Fei Wu,Yueting Zhuang.Unfolding and Modeling the Recovery Process after COVID Lockdowns.Preprint,2022.,Which Sectors Shall Government Support?,We learn a grap

6、h to represent influence relationships between organizations and explore the promotion policy-making.,Xuan Yang,Yang Yang,Chenhao Tan,Yinghe Lin,Fei Wu,Yueting Zhuang.Unfolding and Modeling the Recovery Process after COVID Lockdowns.Preprint,2022.,Risk management Identify default borrowers with 90+d

7、ays overdue repayments.Traditional work relies heavily on borrowers historical loan records1-3.,61%of defaults happen at the first application,1 A.Byanjankar,M.Heikkila,and J.Mezei,Predicting credit risking peer-to-peer lending:A neural network approach.Symposium Series on Computational Intelligence

8、,2015.2 A.Bahrammirzaee,A comparative survey of artificial intelligence applications in finance:artificial neural networks,expert system and hybrid intelligent systems,Neural Computing and Applications,2010.3 R.Malhotra and D.K.Malhotra,Evaluating consumer loans using neural networks,Omega,2003.,Exa

9、mple in Financial Field,Our running example,Normal,Abnormal,Goal:given a graph,identify abnormal nodes.,Anomaly Detection in Graphs,Yang Yang*,Yuhong Xu*,Chunping Wang,Yizhou Sun,Fei Wu,Yueting Zhuang and Ming Gu.Understanding Default Behavior in Online Lending.In CIKM,2019.(*:equal contribution)Yan

10、g Yang,Yuhong Xu,Yizhou Sun,Yuxiao Dong,Fei Wu,and Yueting Zhuang.Mining Fraudsters and Fraudulent Strategies in Large-Scale Mobile Social Networks.InTKDE,2019.,Connection Between Default Behavior and Network Structure,Users with higher importance are more likely to be default borrowers.,phenomenon

11、of“abnormal bridges”,Cheating agent:connect with fraudulent borrowers and benefit from providing false information,faking application documents,etc.We validate its existence by constructing a null model.,Dual-Task Factor Graph Model,Correlation between network features and default borrower identity

12、Y:,Correlation between network features and cheating agent identity Z:,Correlation between Y and Z:,Overall likelihood:,Experimental Results,Experimental setup:20,010 default borrowers,185,814 normal users(1:9.3),and 594 cheating agent.We performed 5-fold cross validation.,Detecting default borrower

13、s,Detecting cheating agent,Two tasks enhance each other,Machine Learning in Graphs,Paradigm of(supervised)machine learning in graphs,Raw Data,Structured Data,Learning Algorithm,Model,Anomaly detection task,Feature Engineering(costly),Automatically learn the features,(Abnormal)Feature Learning in Gra

14、phs,Goal:Efficiently and automatically learning features for machine learning in graphs!Representative solution:Graph Neural Networks(GNN).,Q1:Can abnormality in graphs be detected by graph neural networks?,(Spectral)Graph Neural Networks,Core idea:design graph filter()to perform convolution on grap

15、h signals in spectral domain.Most GNNs are limited to low-pass filters1.,=,3.Graph Fourier inverse trans.,1.Graph Fourier transform,2.Convlution in spectral domain,Eigen-decomposition of Laplacian matrix:=,1 Muhammet Balcilar et.al.,Analyzing the expressive power of graph neural networks in a spectr

16、al perspective.In ICLR21.,GAT,GCN,Why GCN Fail to Identify Anomalies?,Graphs with anomalies tend to mix both high-frequency and low-frequency signals.,Ziwei Chai*,Siqi You*,Yang Yang,Shiliang Pu,Jiarong Xu,Haoyang Cai,and Weihao Jiang.Can Abnormality be Detected by Graph Neural Networks?In IJCAI,202

17、2.(*:equal contribution),AMNet:Adaptive Multi-frequency GNN,Core idea:fusing both low and high-frequency signals adaptively for identifying anomalies.,Ziwei Chai*,Siqi You*,Yang Yang,Shiliang Pu,Jiarong Xu,Haoyang Cai,and Weihao Jiang.Can Abnormality be Detected by Graph Neural Networks?In IJCAI,202

18、2.(*:equal contribution),Group of multiple trainable graph filters run in parallel,Node-adaptively combine signals of different frequency bands,1,2,Combinable Graph Filter Parametrization,Goal:capture graph signals of different frequencies simultaneously.Challenges:Negative spectral response=complex

19、 combinationScale-invariant=filters with larger scale will be dominant,Ziwei Chai*,Siqi You*,Yang Yang,Shiliang Pu,Jiarong Xu,Haoyang Cai,and Weihao Jiang.Can Abnormality be Detected by Graph Neural Networks?In IJCAI,2022.(*:equal contribution),Choice of graph filter:,m-th Bernstein basis of order M

20、,Combing Signals via Node-level Attention,Experimental Results,Setup:identify anomalies in four different domains,AMNet can outperform both general Graph Neural Networks and GNN-based Graph Anomaly Detection Models,Experimental Results,How do learned graph filters behave?,AMNet can learn filters tha

21、t capture multiple frequency signals in an end-to-end manner,Experimental Results,How anomalous/normal nodes favor signals with different frequencies?,AMNet is able to adaptively adopt graph signals with suitable frequencies for different nodes,(Spatial)Graph Neural Networks,GCN:aggregating neighbor

22、 information,equivalent to converged Random Walk1,1 Keyulu Xu,Chengtao Li,Yonglong Tian,Tomohiro Sonobe,Ken-ichi Kawarabayashi,and Stefanie Jegelka.Representation learning on graphs with jumping knowledge networks.In ICML,2018.,Most GNNs Rely on Homophily Assumption,Homophily:connected nodes tend to

23、 be similar.,Homophily Vs.Heterophily,Indistinguishable!,GNN aggregation,What information we have lost?,GNN Beyond Homophily,Core idea:aggregate path information,Path aggregation,Yifei Sun,Haoran Deng,Yang Yang,Chunping Wang,Jiarong Xu,Renhong Huang,Linfeng Cao,Yang Wang,and Lei Chen.Beyond Homophil

24、y:Structure-aware Path Aggregation Graph Neural Network.In IJCAI,2022.,Yifei Sun,Haoran Deng,Yang Yang,Chunping Wang,Jiarong Xu,Renhong Huang,Linfeng Cao,Yang Wang,and Lei Chen.Beyond Homophily:Structure-aware Path Aggregation Graph Neural Network.In IJCAI,2022.,PathNet:Structure-Aware Path Aggregat

25、ion,Path Sampler,Path SamplerHow to acquire meaningful paths?Maximal entropy random walk,#paths grows exponentially!,Transition matrix:,is the Eigen value.,PathNet:Structure-Aware Path Aggregation,Aggregator shall be able to capture,Path Sampler,Structure-aware Recurrent Mechanism,Distance info.,Ord

26、er info.,Yifei Sun,Haoran Deng,Yang Yang,Chunping Wang,Jiarong Xu,Renhong Huang,Linfeng Cao,Yang Wang,and Lei Chen.Beyond Homophily:Structure-aware Path Aggregation Graph Neural Network.In IJCAI,2022.,PathNet:Structure-Aware Path Aggregation,Capture path preferences of different nodes.Heterophily ne

27、ighborhood prefers deeper paths.,Path Sampler,Structure-aware Recurrent Mechanism,Path Preference Modeler,Yifei Sun,Haoran Deng,Yang Yang,Chunping Wang,Jiarong Xu,Renhong Huang,Linfeng Cao,Yang Wang,and Lei Chen.Beyond Homophily:Structure-aware Path Aggregation Graph Neural Network.In IJCAI,2022.,Ex

28、perimental Results,Homophily Graphs,Heterophily Graphs,+10.08%,Competitive results,Superior performance,Yifei Sun,Haoran Deng,Yang Yang,Chunping Wang,Jiarong Xu,Renhong Huang,Linfeng Cao,Yang Wang,and Lei Chen.Beyond Homophily:Structure-aware Path Aggregation Graph Neural Network.In IJCAI,2022.,Anom

29、aly Detection in Graphs under Adversarial Attacks,Frauds will attack our model!,Normal,Abnormal,adversary,Frauds will attack our model!,Anomaly Detection in Graphs under Adversarial Attacks,Normal,Abnormal,Q2:How to learn robust graph models against adversarial attacks?,What Kind of Information is A

30、ccessible to the Attackers?,Existing works assume the attacker is either(partly)aware of the target model,or able to send queries to it.,1 Wu et al.Adversarial Examples for Graph Data:Deep Insights into Attack and Defense.In IJCAI,2019.2 Xu et al.Topology Attack and Defense for Graph Neural Networks

31、:An Optimization Perspective.In IJCAI,2019.3 Zgner et al.Adversarial Attacks on Neural Networks for Graph Data.In SIGKDD,2018.4 Zgner et al.Adversarial Attacks on Graph Neural Networks via Meta Learning.In ICLR,2019.5 Chang et al.A restricted black-box adversarial framework towards attacking graph e

32、mbedding models.In AAAI,2020.6 Dai et al.Adversarial Attack on Graph Structured Data.In ICML,2018.7 Yu et al.Unsupervised Euclidean Distance Attack on Network Embedding.In DSC,2020.,1,2,3,4,5,6,7,Ours,No knowledge of the target model,No query access to the model,Query-free Black-box Attack on Networ

33、ks,1,generic graph filter:1,Jiarong Xu,Yang Yang,Yizhou Sun,Xin Jiang,Yanhao Wang,Chunping Wang,and Jiangang Lu.Blindfolded Attackers Still Threatening:Strict Black-Box Adversarial Attacks on Graphs.In AAAI,2022.,Query-free Black-box Attack on Networks,No knowledge of the target model,No query acces

34、s to the model,1,2,generic graph filter:1,change in graph spectrum,Jiarong Xu,Yang Yang,Yizhou Sun,Xin Jiang,Yanhao Wang,Chunping Wang,and Jiangang Lu.Blindfolded Attackers Still Threatening:Strict Black-Box Adversarial Attacks on Graphs.In AAAI,2022.,No knowledge of the target model,No query access

35、 to the model,Query-free Black-box Attack on Networks,1,2,3,max,generic graph filter:1,Jiarong Xu,Yang Yang,Yizhou Sun,Xin Jiang,Yanhao Wang,Chunping Wang,and Jiangang Lu.Blindfolded Attackers Still Threatening:Strict Black-Box Adversarial Attacks on Graphs.In AAAI,2022.,eigenvalue perturbation theo

36、ry,Node-level attacks against three types of victim models.We report the decrease in Macro-F1 score(in percent)on the test set after the attack is performed;the higher the better.,Blindfolded Adversaries Still Threatening!,Even with no exposure to the target model,the Macro-F1 drops 6.4%in node clas

37、sication task.,Adversaries Can Hurt Various Downstream Tasks!,Jiarong Xu,Yang Yang,Junru Chen,Chunping Wang,Xin Jiang,Jiangang Lu,and Yizhou Sun.Unsupervised Adversarially-Robust Representation Learning on Graphs.In AAAI,2022.,Adversaries Can Hurt Various Downstream Tasks!,defense,Jiarong Xu,Yang Ya

38、ng,Junru Chen,Chunping Wang,Xin Jiang,Jiangang Lu,and Yizhou Sun.Unsupervised Adversarially-Robust Representation Learning on Graphs.In AAAI,2022.,Adversaries Can Hurt Various Downstream Tasks!,Jiarong Xu,Yang Yang,Junru Chen,Chunping Wang,Xin Jiang,Jiangang Lu,and Yizhou Sun.Unsupervised Adversaria

39、lly-Robust Representation Learning on Graphs.In AAAI,2022.,Label space,Node attributes,Representation space,Network structure,Quantifying Representation Robustness,Task-specific,Representation vulnerability on networksGraph Representation Vulnerability(defined on representation space)Mutual informat

40、ion based,Label space,Node attributes,Representation space,Network structure,Quantifying Representation Robustness,:encoder,Anyconnection?,Label space,Node attributes,Representation space,Network structure,Topology-aware:Attribute-aware:General case:,Representation vulnerability on networks,Robustif

41、ication principle-Theories,Summary of results using polluted data.,One robust graph encoder can significantly enhance the robustness in three downstream tasks,Experimental Results-Robustness,Q3:What are application scenarios of anomaly detection in graphs?,Honor of Kings,Join as Five,Battle as One,G

42、oal:identify abuse behavior of players,Modeling the Game,Data:95.6M games among 100.2M players.,Borrow Ideas from Sociology,How to build an effective team?Belbin Team Inventory:balance in team roles is associated with team performanceIt defines 9 team roles(e.g.,implementer,co-ordinator,resource inv

43、estigator,etc.)Challenges:Team roles are usually implicit in real life and it is difficult to identify.Difficult to understand the effectiveness of teams in multiple measures.,1 R Meredith Belbin.2012.Team roles at work.Routledge.2 R Meredith Belbin.1981.Management teams:Why they succeed or fail.Hum

44、an Resource Management International Digest 19,3(1981).,Team Roles in Gaming,We have 125 types of role combinations.Teams with diverse roles tend to win the game.,How Team Roles Influence Abuse Behavior,Diverse teams tend to abuse more when losing and abuse less when winning.,Ziqiang Cheng,Yang Yang

45、,Chenhao Tan,Denny Cheng,Alex Cheng,and Yueting Zhuang.What Makes a Good Team?A Large-scale Study on the Effect of Team Composition in Honor of Kings.In WWW,2019.,“Abusive”Assassin Phenomenon,Are assassins more abusive because abusive players tend to choose assassins,or players become more abusive w

46、hen choosing assassins?Players who prefer leading roles are more abusive.,Ziqiang Cheng,Yang Yang,Chenhao Tan,Denny Cheng,Alex Cheng,and Yueting Zhuang.What Makes a Good Team?A Large-scale Study on the Effect of Team Composition in Honor of Kings.In WWW,2019.,Applications,Before the game starts,we p

47、redict:Which team will win?Will anyone use abusive language?Will a team surrender?Only consider team roles without any user behavior,Electricity Theft,Electricity theft is a common illegal behavior in developing countries.In 2012,GDP in India was reported to drop 1.5%as a result of electricity theft

48、1;Uttar Pradesh lost 36%of its total electric power caused by electricity theft.,1 PR Newswire.96 Billion Is Lost Every Year To Electricity Theft:Utilities increasingly investing in solutions to combat theft and non-technical losses.2017.,Macro-level:,Meso-level:,Micro-level:,Electricity-Theft Detec

49、tion,Data：(2 years,from June 2017 to April 2019)310,786 electricity usage records of user,3,908 NTL records of transformer areas,11 weather records of prefecture-level cities.,Our work has been applied by State Grid of China to successfully catch 5785 electricity thieves and retroactive electric bil

50、l 6.24 million RMB.,Wenjie Hu,Yang Yang,Jianbo Wang,Xuanwen Huang,and Ziqiang Cheng.Understanding Electricity-Theft Behavior via Multi-Source Data.In WWW,2020.,HEBR:Hierarchical Electricity-theft Behavior Recognition,model the influence from macro/meso to micro info,uniform the influence from macro

51、and meso level,estimate the probability of electricity theft,HEBR contains three levels of feature extraction and hierarchical fusion,Wenjie Hu,Yang Yang,Jianbo Wang,Xuanwen Huang,and Ziqiang Cheng.Understanding Electricity-Theft Behavior via Multi-Source Data.In WWW,2020.,Real-World Application,Our

52、 work has been applied by State Grid of China to successfully catch electricity thieves in Hangzhou with a precision of 15%,when the thief was caught,e:electricity consumption of user l:non-technical loss c:climate(temperature):the attention scores of e and c(level 1):the attention scores of e and l

53、(level 1):the attention scores of ec and el(level 2),Real-World Application,Our work has been applied by State Grid of China to successfully catch electricity thieves in Hangzhou with a precision of 15%,when the thief was caught,epileptic,Human SEEG recording,BrainNet:First Study of Epileptic Wave D

54、etection via SEEG Records,BrainNet learns the epileptogenic network in both brain-region and channel levels.,Junru Chen*,Yang Yang*,Tao Yu,Yingying Fan,Xiaolong Mo,and Carl Yang.BrainNet:Epileptic Wave Detection from SEEG with Hierarchical Graph Diffusion Learning.In KDD,2022.(*:equal contribution),

55、Experimental Results,BrainNet improves the performance by 142%(F2)on the dataset with the epileptic wave ratio of 1:500.,Explainable Results,The diffusion process of brain waves reveals how BrainNet detects epileptic seizures.,Junru Chen*,Yang Yang*,Tao Yu,Yingying Fan,Xiaolong Mo,and Carl Yang.Brai

56、nNet:Epileptic Wave Detection from SEEG with Hierarchical Graph Diffusion Learning.In KDD,2022.(*:equal contribution),Weak connections,Strong connections,Seizure diffusion,Start of seizure,Some Thoughts,We have not found any silver bullets yet.Still requiring hard domain knowledge.Translate machine

57、language into humans-teach machine how human thinks,GNNs favor informative but unexplainable subgraphs,People favors more“reliable”neighbors,Human in the loop,:Graph Anomaly Detection Benchmark,DGraph provides a dynamic graph spanning over two years,representing a realistic user-to-user social netwo

58、rk with financial fraud labels.,Webpage:https:/https:/,Thanks&Take-Home Message,How to apply GNN on graph anomaly detection?Adaptively combine multiple frequency signals.Aggregate structure-aware path information.How to learn robust model against graph attacks?Query-free and black-box graph attacks.Graph pretraining based model defense.How to apply our research on real-world scenarios?Abusive player in gamingElectricity-theft predictionEpileptic-wave detection,Email：Homepage:http:/yangy.org,Homepage,Human-in-the-Loop GNNs,