The Web Conference (WWW'21) Tutorial
Apr 2021 - Virtual

Graph Mining and Multi-Relational Learning: Tools and Applications


Given a large graph, like who-buys-what, which is the most important node? How can we find communities? If the nodes have attributes (say, gender, or, eco-friendly, or fraudster), and we know the values of interest for a few nodes, how can we guess the attributes of the rest of the nodes? Graphs naturally represent a host of processes including interactions between people on social or communication networks, links between webpages on the World Wide Web, interactions between customers and products, relations between products, companies, and brands, relations between malicious accounts, and many others. In such scenarios, graphs that model real-world networks are typically heterogeneous, multi-modal, and multi-relational. With the availability of more varieties of interconnected structured and semi-structured data, the importance of leveraging the heterogeneous and multi-relational nature of networks in being able to effectively mine and learn this kind of data is becoming more evident. In this tutorial, we present time-tested graph mining algorithms (PageRank, HITS, Belief Propagation, METIS), as well as their connection to Multi-relational Learning methods. We cover both traditional, plain graphs, as well as heterogeneous, attributed graphs. Our emphasis is on the intuition behind these tools, with only pointers to the theorems behind them. The tutorial will includes many examples are from settings of direct interest to the Web Conference community (e.g., social networks, recommender systems, and knowledge graphs).


  • Introduction and Motivation.
  • Part 1: Plain Graphs - Traditional tools
    • Node Importance, Node Proximity, Link Prediction: SVD, PageRank, HITS, SALSA
    • Community Detection METIS, Co-clustering, Cross-associations ‘No good cuts’
    • Fraud and Anomaly Detection OddBall, CopyCatch, EigenSpokes, Fraudar; Survey on anomaly detection applications
    • Belief Propagation (Basic, FastBP, zooBP); FastBP and extensions; Applications: NetProbe, Snare, Polonium
  • Part 2: Complex and Heterogeneous Graphs
    • Factorization Methods: Factorization Machines; PARAFAC, Survey on tensors, and applications
    • Heterogeneous Information Networks and Meta-path-based methods
    • Prediction and Recommender Systems, Entity Resolution and Knowledge Graph Identification
  • Conclusions


Shobeir Fakhraei

Shobeir Fakhraei

Machine Learning Scientist

Christos Faloutsos

Christos Faloutsos

Professor / Scholar
CMU / Amazon