WSDM'17 参会总结

最近断更了很久,因为刚好过年,过年期间忙着走亲戚,很累也没有时间来学习,过完年之后去了趟英国参加 WSDM’17,刚好写了一些总结。

WSDM 的全称是 ACM International Conference on Web Search and Data Mining,17年刚好是第十届,这次的会议地点在英国剑桥,美丽的康河边。

总结的主要是社交网络和图算法部分,我们是一个团队代表公司参会,所以每个人会负责其中一个方面,而我自己擅长的推荐系统被分给了别人,就挑了一个感兴趣的 topic。因为对这个 topic 并不擅长,所以更多还是以提供信息为主,评论较少。

Tutorial:Social Media Anomaly Detection: Challenges and Solutions

之所以会对这个Tutorial感兴趣,主要是因为网络关系中的欺诈跟电商业务很相关,据我了解,无论是淘宝还是天猫,虚假交易、恶意评价等都是一直存在的问题。这个Tutorial是University of Southern California的Yan Liu和University of Sydney 的 Chawla 一起完成的,在Tutorial中,Liu 提到了Twitter、Yelp 等公司有意思的实际案例,还包括最近比较火总统大选中假新闻问题,十分有意思。

目前社交网络异常检测的应用场景主要是以下几种:

  1. Bot detection。Twitter中的僵尸粉识别。
  2. Compromised account detection。黑客盗取Twitter大V账号。
  3. Group Review Spamming。Yelp 中,某家店雇佣水军来刷虚假评价提高排名。
  4. Organized Viral Campaign。ISIS 利用 Twitter散播恐怖言论,招募恐怖分子。
  5. Bullying on Social Media。流言、恐吓等网络暴力。

Liu 首先通过举例介绍了社交网络异常识别的挑战,一方面会存在很高的误报率,另一方面,这些异常的情况又很难通过统计的方式来识别出来。后面就主要介绍各种方法了,比较偏综述,每一种方法都是粗略介绍了下核心技术,感兴趣的同学可以按图索骥拿 paper 来看

网络当中的异常识别

这里主要是一些过去人的工作

  • Static Plain Graph
    • Feature Based Anomaly
    • Community Based Anomaly
  • Static Attributed Graph
    • Substructure and subgraphs
    • Community outliers
  • Dynamic Graph
    • Distance based
    • Structure based

Overview of Graph Anomaly Detection

动态数据当中的异常识别

这一部分在过去也有相当多的论文可以查阅

  • Point anomaly detection
    • Markov process
      • Bayes one-step Markov [Schonlau et al. (2001)] Hybrid multi-step Markov [Ju and Vardi (2001)]
      • Poisson process [Ihler et al. (2006)]
    • Compression [Schonlau et al. (2001)]
    • Probabilistic suffix tree (PST) [Sun et al. (2006)]
    • Temporal dependence [Qiu et al. (2012)]
  • Group anomaly detection
    • Scan statistics [Das et al. (2009); Friedland and Jensen (2007)]
    • Density estimation
      • Multinomial genre model (MGM) [Xiong et al. (2011a)]
      • Flexible genre model (FGM) [Xiong et al. (2011b)]
      • Group Latent Anomaly Detection model(GLAD) [Rose et al. (2014)]
      • One class support measure machine (OCSMM) [Muandet and Sch ̈olkopf (2013)]

异常点识别

  • Activity-based Point Anomaly

    • Statistical hypothesis testing framework: (将每个点都放到时间序列里来看,很容易复杂度过高
      • Markov process
        • Bayes one-step Markov [Schonlau et al. (2001)]
        • Hybrid multi-step Markov [Ju and Vardi (2001)]
      • Poisson process [Ihler et al. (2006)]
      • Compression [Schonlau et al. (2001)]
      • Probabilistic suffix tree (PST) [Sun et al. (2006)]
      • Temporal dependence [Qiu et al. (2012)]
  • Graph-based Point Anomaly

    • Static graph(不仅考虑自己这个点的情况,还考虑对点跟点之间的影响
      • Power law [Akoglu and McGlohon (2009); Akoglu et al. (2010)]
      • Random walk [Moonesinghe and Tan (2008); Sun et al. (2005)]
      • Hyper-graph [Silva and Willett (2008b,a)]
      • Spatial auto-correlation [Sun and Chawla (2004); Chawla and Sun (2006)]
    • Dynamic graph
      • Time series analysis of graph data
        • ARIMA process (Pincombe, 2005)
        • graph eigenvectors (Id ́e and Kashima, 2004)
      • GraphScope: Minimum description length (MDL) (Sun et al., 2007)
      • Window based approaches: scan statistics (Park et al., 2008)

异常群体识别

这一部分我觉得跟淘宝的刷单炒信识别很像,协同作案,单独看某一单可能是没问题的,但放到一起就让人觉得很可疑。

  • Scan statistics [Das et al. (2009)]
  • Density estimation
    • Multinomial genre model (MGM) [Xiong et al. (2011a)]
    • Flexible genre model (FGM) [Xiong et al. (2011b)]
    • Group Latent Anomaly Detection model(GLAD) Rose et al. (2014)
    • One class support measure machine (OCSMM) [Muandet and Sch ̈olkopf (2013)]

最后是几个应用实例

应用实例:假新闻甄别

虚假新闻

  • Text-based 通过抽取文本训练分类器
  • Graph-based 通过用户对新闻的点击数据来筛选出行为异常的部分
  • Activity-based 通过用户在时间序列上的行为来识别
  • Mixture 混合以上三种方式

这里有一个识别虚假新闻的比赛:http://www.fakenewschallenge.org

应用实例:Twitter 中的僵尸粉识别系统

基于 Twitter 的数据集做的,作者介绍了他们团队在实际操作的过程中发现的几种有效的改进。

Temporal features/statistics

  • Inter-tweet time distribution for users
  • Entropy based methods
  • Reaction time for retweets/mentions
  • Temporal anomalies in retweeting behavior
  • Transfer entropy methods with tweet times

Follower/mention/retweet graph

  • Calculate node centrality (Pagerank, etc)
  • Analyze reciprocity relationships between friends/followers
  • Analyze correlation between node centrality and activity measures

Combined text/network analysis

  • Decompose #hashtag/user matrix to find topics/user groups
  • LDA and other topic models
  • Content Transfer

Sentiment analysis

  • Classify tweet sentiment as pro vs. anti-vaccination
  • Use unsupervised methods based on dictionaries
  • supervised by manually labeling some of the tweets
  • Classify user sentiment as pro vs. anti-vaccination

最后附上 Summary

Session:Social Networks and Graphs

这里一共有4个Long Talks分享。

Online Actions with Offline Impact: How Online So- cial Networks Influence Online and Offline User Be- havior

作者研究了社交网络是如何影响用户在线下的活动的。分析发现,当你在社交网络上认识了新朋友,你在 APP 内的行为会增加30%,在 APP 内的停留时间会增加17%,另外你的线下活动也会增加7%。

附:原文

Social Incentive Optimization in Online Social Net- works

研究表明,社交网络中存在一种自我激励机制,用户分享一条动态,当这条动态得到别人的响应(点赞、评论、转发),用户就会变得更活跃更乐意发动态。作者将这一原理应用在了 LinkedIn 的信息流推荐当中。

附:原文

Counting Graphlets: Space vs Time

作者通过对 Color Coding 方法的改进,显著增加输入图的上限,得到一个比 Markov Chain Monte Carlo 更优的结果。

附:原文

Representation Learning with Pair-wise Constraints for Collaborative Ranking

作者主要针对在推荐系统中常用的协同过滤,利用深度学习的方法做了改进。先把user跟item的评分数据构造成pairwise的形式,然后通过深度学习实现 Encoding 和 Decoding 的过程,来得到 user 对 item 的偏好。这篇文章的作者来自中科院。

附:原文

感受

最后谈一下这次参会的见闻感受:

  1. 在 DataMining 和 MachineLearning 这个圈子里,华人做出的贡献越来越突出,据 Huawei 的李航老师说,这次会议的论文中有华人名字的大概能占1/3;
  2. 学界里追逐流行的趋势很明显,感觉听到最多的字眼就是Embedding和GAN;
  3. WSDM 是个很偏应用的会,可以大量的文章来自工业界,不过主要还是集中在美国公司,Microsoft、Google、Yahoo!、LinkedIn、Amazon等都有独立或者合作发表文章;
  4. 欧洲整体福利水平高,几个科技型大公司也都有欧洲分部(DeepMind 就在伦敦),适合搞研究,跟几个参会的华人留学生聊他们都倾向于毕业继续留在欧洲;