Efficient and Effective Edge-wise Graph Representation Learning and Applications
COM1 Level 3
MR1, COM1-03-19
Abstract:
Graph representation learning (GRL) is a powerful tool for graph analysis, which has gained massive attention from both academia and industry due to its superior performance in various real-world applications. However, the majority of existing works for GRL are dedicated to node-based tasks and thus focus on producing node representations. Despite such methods being used to derive edge representations by regarding edges as nodes, they suffer from sub-par result utility in practical edge-wise applications, such as financial fraud detection and review spam combating, due to neglecting the unique properties of edges and their inherent drawbacks. Moreover, there is a paucity of research devoted to edge representation learning. These methods either require high computational costs in sampling random walks or yield severely compromised representation quality because of falling short of capturing high-order information between edges.
In this thesis, we focus on addressing these challenges in edge representation learning and their applications, which are of great interest to both industry and academia. We present TER and AER, which generate high-quality edge representation vectors based on the graph structure surrounding edges and edge attributes, respectively. In particular, TER can accurately encode high-order proximities of edges into low-dimensional vectors in a practically efficient and theoretically sound way, while AER augments edge attributes through a carefully designed feature aggregation scheme.
To extend edge representation learning to bipartite graphs, we introduce EAGLE, a novel framework specifically designed for Edge-Attributed Bipartite Graphs (EABGs). EAGLE employs a Factorized Feature Propagation (FFP) mechanism to model long-range dependencies between edges and utilizes a dual-view representation learning approach to capture information within and across partitions. This design allows EAGLE to achieve scalable and effective edge representation learning on large bipartite graphs, which is demonstrated by significant improvements in edge classification and recommendation tasks compared to state-of-the-art methods.
Regarding the applications of edge representation learning, we focus on detecting anomalous edges, such as fraudulent financial transactions or product reviews. We first propose an effective solution, DoubleFA, which contains two novel schemes: proximal feature aggregation and anomaly feature aggregation. The former aggregates features from neighborhoods into edges based on top-k Personalized PageRank (PPR). In anomaly feature aggregation, we employ a predict-and-aggregate strategy to accurately preserve anomaly information, thereby alleviating the over-smoothing issue incurred by proximal feature aggregation. Next, we present EGNN-AD, a method for detecting anomalous edges from a node classification perspective in a transformed node-attributed graph, where each edge in the original graph is converted into an attributed node. EGNN-AD leverages two GNN models, EGNN and NGNN, to incorporate information from both edges and nodes for detecting edge anomalies. EGNN uses top-k Personalized PageRank (PPR) to establish different edge-to-edge relations in the new graph, while NGNN employs trainable node embeddings to enhance performance.
We conduct extensive experiments on real-world graphs to evaluate the effectiveness and efficiency of our proposed techniques. For edge representation learning, TER and AER achieve significantly superior performance in terms of edge classification on 8 real-life datasets, while being up to one order of magnitude faster than 16 baselines on large graphs. EAGLE further extends the applicability of edge representation learning to bipartite graphs, delivering up to 38% improvement in average precision on large-scale datasets. For anomalous edge detection, we apply DoubleFA on a financial transaction network dataset with 160 million users and 470 million transactions, achieving a significant improvement of at least 23% in F1 score compared to the best competitors. EGNN-AD, applied on smaller financial transaction and review network datasets, consistently outperforms several baselines in terms of anomaly detection accuracy.