Unsupervised graph anomaly detection is crucial for various practical
applications as it aims to identify anomalies in a graph that exhibit rare
patterns deviating significantly from the majority of nodes. Recent
advancements have utilized Graph Neural Networks (GNNs) to learn high-quality
node representations for anomaly detection by aggregating information from
neighborhoods. However, the presence of anomalies may render the observed
neighborhood unreliable and result in misleading information aggregation for
node representation learning. Selecting the proper neighborhood is critical for
graph anomaly detection but also challenging due to the absence of
anomaly-oriented guidance and the interdependence with representation learning.
To address these issues, we utilize the advantages of reinforcement learning in
adaptively learning in complex environments and propose a novel method that
incorporates Reinforcement neighborhood selection for unsupervised graph
ANomaly Detection (RAND). RAND begins by enriching the candidate neighbor pool
of the given central node with multiple types of indirect neighbors. Next, RAND
designs a tailored reinforcement anomaly evaluation module to assess the
reliability and reward of considering the given neighbor. Finally, RAND selects
the most reliable subset of neighbors based on these rewards and introduces an
anomaly-aware aggregator to amplify messages from reliable neighbors while
diminishing messages from unreliable ones. Extensive experiments on both three
synthetic and two real-world datasets demonstrate that RAND outperforms the
state-of-the-art methods.

提出了一种基于增强学习的无监督图异常检测方法（RAND），该方法利用图神经网络学习节点表示并选择可靠的邻居节点，通过增加增强学习模块和异常感知汇聚器来提高检测性能。实验证明，RAND 方法在合成和真实数据集上优于现有方法。

无监督图异常检测中的强化邻居选择

Reinforcement Neighborhood Selection for Unsupervised Graph Anomaly  Detection

Graph representation learning, aiming to learn low-dimensional
representations which capture the geometric dependencies between nodes in the
original graph, has gained increasing popularity in a variety of graph analysis
tasks, including node classification and link prediction. Existing
representation learning methods based on graph neural networks and their
variants rely on the aggregation of neighborhood information, which makes it
sensitive to noises in the graph. In this paper, we propose Graph Denoising
Policy Network (short for GDPNet) to learn robust representations from noisy
graph data through reinforcement learning. GDPNet first selects signal
neighborhoods for each node, and then aggregates the information from the
selected neighborhoods to learn node representations for the down-stream tasks.
Specifically, in the signal neighborhood selection phase, GDPNet optimizes the
neighborhood for each target node by formulating the process of removing noisy
neighborhoods as a Markov decision process and learning a policy with
task-specific rewards received from the representation learning phase. In the
representation learning phase, GDPNet aggregates features from signal neighbors
to generate node representations for down-stream tasks, and provides
task-specific rewards to the signal neighbor selection phase. These two phases
are jointly trained to select optimal sets of neighbors for target nodes with
maximum cumulative task-specific rewards, and to learn robust representations
for nodes. Experimental results on node classification task demonstrate the
effectiveness of GDNet, outperforming the state-of-the-art graph representation
learning methods on several well-studied datasets. Additionally, GDPNet is
mathematically equivalent to solving the submodular maximizing problem, which
theoretically guarantees the best approximation to the optimal solution with
GDPNet.

本文提出了 Graph Denoising Policy Network (GDPNet) 方法，使用增强学习从噪声图数据中学习鲁棒的低维表示，并在多个数据集上的节点分类任务中表现出优越性能。

利用图形去噪策略网络学习鲁棒表示

Learning Robust Representations with Graph Denoising Policy Network

The pattern of zero entries in the inverse covariance matrix of a
multivariate normal distribution corresponds to conditional independence
restrictions between variables. Covariance selection aims at estimating those
structural zeros from data. We show that neighborhood selection with the Lasso
is a computationally attractive alternative to standard covariance selection
for sparse high-dimensional graphs. Neighborhood selection estimates the
conditional independence restrictions separately for each node in the graph and
is hence equivalent to variable selection for Gaussian linear models. We show
that the proposed neighborhood selection scheme is consistent for sparse
high-dimensional graphs. Consistency hinges on the choice of the penalty
parameter. The oracle value for optimal prediction does not lead to a
consistent neighborhood estimate. Controlling instead the probability of
falsely joining some distinct connectivity components of the graph, consistent
estimation for sparse graphs is achieved (with exponential rates), even when
the number of variables grows as the number of observations raised to an
arbitrary power.

该文介绍了如何使用 lasso 算法来进行高维稀疏图的协方差无关估计，实现了变量选择，并控制了图中误连接不同的连通分量的概率，最终实现了稀疏图的一致性估计。