算法梳理（按结构分类）
2020-04-07 12:11:51 0 举报AI智能生成
对算法进行梳理，不断更新
作者其他创作
大纲/内容
图算法（按问题场景分类）
基础图算法
node2vec
是DeepWalk的一般化，工业界运用最广的网络嵌入算法
struc2vec
空间结构相似性的角度定义顶点相似度。
GNN
综述
论文
GCN（Graph Convolutional Network）
半监督图卷积神经网络GCN
numpy实现
论文解读
论文
GAT
图注意网络
GraphSAGE（Graph SAmple and aggreGatE）
设计
对图中每个顶点邻居顶点进行采样
根据聚合函数聚合邻居顶点蕴含的信息
得到图中各顶点的向量表示供下游任务使用
GCN落地应用
PinSage
基于GCN，工业级推荐系统
FastGCN
采用重要性采样选择邻居，为了解决GraphSage计算性能问题
Large-Scale Learnable GCN
将graph数据转化成 grid-like 结构数据，使用Sub-Graph Training做顶点抽样，解决图相关的深度学习模型内存和计算问题。
GeniePath
蚂蚁金服，可自动选择邻居的GCN
Fast-unfolding
基于模块度优化的社团发现，在工业界应用最为广泛
图嵌入(把图改造成规则化数据)
DeepWalk
LINE
SDNE
基于图的社区挖掘
CopyCatch（hive实现）
Facebook采用CopyCatch处理Lockstep欺诈行为
SynchroTrap
对恶意账户进行识别
CatchSync
捕获大规模有向图中同步行为，挖掘网络中的异常。
FRAUDAR
二部高密子图挖掘
M-Zoom
思想与fraudar非常类似，将数据扩充到更高维度，在高维 Tensor 中寻找 Dense Sub tensor
K-L（Kernighan-Lin）算法
谱二分算法
GN算法
Newman快速算法
派系过滤CPM方法
基于标签传播
基于标签传播的重叠社区发现算法COPRA
基于标签传播的非重叠社区发现算法LPA
基于节点相似性的社区划分
BotGraph（hive实现）
应用
反欺诈
主要逻辑
基于botuser的注册、登录、发送邮件等操作时共享的IP地址，建立botuser之间的关系。
设计
构建user-user图
权重定义：两个user之间共享ip数
连边条件阈值：边权重w >= 阈值T
层次聚类，自上而下
判断连通图成员数 > 阈值M，若大于，更新阈值T
阈值 T + 1
循环，直到 连通图成员数 <= 阈值M
剪枝 pruning
评价
每个团体中80%的成员日均发送邮件数 > 阈值Q，则为候选botuser团体
成团 grouping
工程实现
简单的数据并行化
map
根据 IP分区
每个分区维护一个HashTable
key：(Ui,Uj)
value: weight
reduce
以key作为 hash partition，聚合weight
过滤方法
map
根据user ID分区
生成每个分区p出现ip的list
过滤
将该ip list分发到其他各分区，若共用ip数小于w，则过滤掉
将剩下的(U,IP)传输到原分区p中
非负矩阵分解
基于模块度的社区划分
最小割
图传播算法
PageRank
指标
对图中的每个节点进行重要性排名
假设
数量假设——被更多网页链接到的网页更重要
权重假设——有更少外链的网页将会传递更高的权重
HITS
指标
Authority：可理解为权威页面，一般包含高质量内容。
hub：可理解为导航页面，指向很多Authority页面。
假设
被越多的hub页面所指向的页面，内容质量越高。
一个hub页面会尽可能地指向更高质量的内容页面。
Weisfeiler-Lehman
指标
节点独立性
attribute
structure
邻居
RVE2
标签传播算法LPA
设计
为所有节点指定一个唯一的标签
对于某一个节点，考察其所有邻居节点的标签，并进行统计，将出现个数最多的那个标签赋给当前节点。当个数最多的标签不唯一时，随机选一个。
逐轮刷新所有节点的标签，直到达到收敛要求为止
BP(信念传播算法)
基于GAN思想的标签传播
基于图的（半）监督学习
GEM
蚂蚁金服建立多个二部图应用gcn对恶意注册进行检测。
GraphRAD
通过黑种子账户进行局部社区发现，使用层次聚类的方法得到最终的欺诈社区。
GOTCHA
使用PPR进行欺诈风险传播，对偷税逃税这一类社会保证欺诈问题进行检测。
GCN算法
IBM使用GCN算法识别比特币反洗钱。
HinDroid
通过构建HIN抽关系特征，对安卓智能手机中的恶意应用进行识别。
有监督欺诈检测&评分卡
SocialWatch
手工提取基于图的特征做有监督的分类。
BLP框架
手工提取图的特征，结合其他维度构建评分卡。
基于行为序列的欺诈检测
通过用户行为转移关系构建MTF矩阵，通过CNN提取特征，结合LSTM的时序信息对在线借贷中的恶意用户进行识别。
京东基于用户行为序列进行反欺诈，通过抽取用户点击商品行为Session序列采用RNN网络识别恶意用户。
异常检测
OddBall
基于图的孤立点检测，通过研究Ego-net总结几种异常模型及度量方式
树算法
0 条评论
下一页
