Out-of-Distribution Generalized Graph Anomaly Detection with Homophily-aware Environment Mixup
Authors: Sibo Tian
Xin Wang
Zeyang Zhang
Haibo Chen
Wenwu Zhu
Venue: NeurIPS 2025 poster ()
Keywords: Graph Anomaly Detection
Out-of-Distribution Generalization
Primary area: applications

Abstract: Graph anomaly detection (GAD) is widely prevalent in scenarios such as financial fraud detection, anti-money laundering, and social bot detection. However, structural distribution shifts are commonly observed in real-world GAD data due to selection bias, resulting in reduced homophily. Existing GAD methods tend to rely on homophilic shortcuts when trained on high-homophily structures, limiting their ability to generalize well to data with low homophily under structural distribution shifts. In this study, we propose to handle structural distribution shifts by generating novel environments characterized by diverse homophilic structures and utilizing invariant patterns, i.e., features and structures with the capability of stable prediction across structural distribution shifts, which face two challenges: (1) How to discover invariant patterns from entangled features and structures, as structures are sensitive to varying homophilic distributions. (2) How to systematically construct new environments with diverse homophilic structures. To address these challenges, we propose the Ego-Neighborhood Disentangled Encoder with Homophily-aware Environment Mixup (HEM), which effectively handles structural distribution shifts in GAD by discovering invariant patterns. Specifically, we first propose an ego-neighborhood disentangled encoder to decouple the learning of feature embeddings and structural embeddings, which facilitates subsequent improvements in the invariance of structural embeddings for prediction. Next, we introduce a homophily-aware environment mixup that dynamically adjusts edge weights through adversarial learning, effectively generating environments with diverse structural distributions. Finally, we iteratively train the classifier and environment mixup via adversarial training, simultaneously improving the diversity of constructed environments and discovering invariant patterns under structural distribution shifts. Extensive experiments on real-world datasets demonstrate that our method outperforms existing baselines and achieves state-of-the-art performance under structural distribution shift conditions.

Out-of-Distribution Generalized Graph Anomaly Detection with Homophily-aware Environment Mixup
Sibo Tian', Xin Wang'; Zeyang Zhang', Haibo Chen', Wenwu Zhu Tsinghua University
Abstract
Graph anomaly detection (GAD) is widely prevalent in scenarios such financial fraud detection, anti-money laundering and social bot detecion. However, structural distribution shifts are commonly observed in real-world GAD data due selection bias, resulting in reduced homophily, Existing GAD methods tend to rely on ho- mophilic shorteuts when trained on high-homophily structures, limiting their ability to generalize well to data with low homophily under structural distribution shifts. In this study, we propose to handle structural distribution shifts by generating novel environments characterized by diverse homophilic structures and utilizing invariant patterns, i..., features and structures with the capability of stable prediction across structural distribution shifts, which face two challenges: (1) How to discover invari- ant patterns from entangled features and structures, as structures are sensitive to varying homophilic distributions. (2) How to systematically construct new environ- ments with diverse homophilic structures. To address these challenges, we propose Ego-Neighborhood Disentangled Encoder with Homophily-awand awaree Environment Mixup (HEM), which effectively handles structural distribution shifts in GAD by discovering invariant patterns. Specifically, we first propose an egg-neighboroood disentangled encoder to decouple the learning of feature and structural embeddings, which facilitates subsequent improvements in the invariance of structural embed- environment mixup
dings for prediction. Next, we introduce a homophily-awan that dynamically adjusts edge weights through adversarial learning, effectively generating environments with diverse structural distributions. Finally, we iteratively train the classifier and environment mixup via adversarial training, simultaneously improving the diversity of constructed environments and discovering invariant patterns under structural distribution shifts. Extensive experiments on real-world datasets demonstrate that our method outperforms existing basclines and achieves ttate-of-the-an performance under structural distribution shift.
Introduction
Graph anomaly detection (GAD) represents classical task in graph machine learning, with extensive applications in financial fraud detection (2), anti-money laundering 33) and social bot detection 4 (.) Typically, GAD can be formulated as semi-supervised node classification problem 6), where the objective is to identify anomalous nodes in the input graph. Graph neu- ral networks (GNNs) have demonstrated superior predictive capabilities in GAD tasks due to their ability to handle complex topological relationships and model sophisticated node representations 7
However, structural distribution shifts SIIT are prevalent in real-world graph anomaly detection sce- narios due to factors such as selection bias [2] For example, in anti-money laundering contexts [3]. coordinated money laundering accounts are more likely to be identified and labeled compared to
"Corresponding authors. Sein_wang.wer wwzhu| @ @tsinghua.edu.cn
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

isolated ones, while large-scale coordinated bot comments on social platforms are more easily de- tected by automated systems. This results in a structural distribution shift between training and test data, as nodes with stronger homophily and more connections to similar nodes are more likely to be labeled. Existing GNNs for GAD methods trained on high-homophily structures tend rely on the homophilic shortcut, limiting their ability to generalize effectively to test data with low homophily under structural distribution shifts.
In this paper, we study the problem of handling structural distribution shifts in graph anomaly tasks by generating novel environments characterized by diverse homophilic structures and utilizing invariant patterns, ie.. features and structures with the capability of stable prediction across structural distribution shifts, which remains largely unexplored in the literature. However, this problem highly nontrivial with the following challenges:
How to discover invariant patterns from entangled features and structures, as structures are sensitive to varying homophilic distributions.
How to systematically construct new environments with diverse homophilic structures.
To address these challenges, we propose novel framework named Ego-Neighborhood Disentangled Encoder with Homophily-aware Environment Mixup (HEM) to discover invariant patterns with stable predictive abilities under structural distribution shifts. Specifically,
first propose ego- neighborhood disentangled encoder to separately model the feature and structure representations. By this design, can (I) disentangle feature information and structure information, enabling the following modules to strengthen the invariance of the prediction patterns. (2) model the interaction patterns between ego-node and neighhorhood better predict the anomaly probability. Then, propose a homophily-aware environment mixup, which dynamically adjusts edge weights within the graph implicitly modify the structure of ego graphs. This mechanism generates diverse training environments and facilitates the learning of invariant patterns in a memory-efficient manner. Finally, the two modules are trained iteratively in an adversarial manner, in order improve the diversity of the constructed environment and discover invariant patterns under structural distribution shifts. Extensive experiments on real- real-world datasets demonstrate that our proposed method achieves state-of-ther afrt performance in GAD under structural distribution shift scenarios.
The contributions of work can be summarized follows:
We propose Ego-Neighborhood Disentangled Encoder with Homophily aware Environment Mixup (HEM), which can handle structural distribution shift in graph anomaly detection, which is largely unexplored in literature.
We propose an ego-neighborhood disentangled encoder to disentangle feature and structure representations for learning invariant patterns, which is general framework that can be utilized to improve model performance for many GNNs. Besides, we propose a homophily-aware environment mixup efficiently generate training environments with diverse local structures to improve the model's generalization capability.
Experiments on real-world datasets demonstrate that our method achieves state-of-the-art perfor- mance compared to existing baselines.
2 Problem Formulation
In this section, we formulate the problem of graph anomaly detection under distribution shift.
Node-Attribute Graph A node-attribute graph G consists of a node set V. an edge set E, and node attributes X E xa where each row of X represents the feature vector of the corresponding node. The edges between nodes are represented by the adjacency matrix A E Ruxn, where is the number of nodes and d is the dimension of the input features. The node labels are defined as Y g Thus, node-attribute graph can be summarized as G = {A, X, Y }. In node-level graph anomaly detection, the labels are binary variables indicating whether a node is normal or anomalous.
Node-Lever Graph Anomaly Detection (GAD) Node-level graph anomaly detection is an im- balanced binary classification task. The goal of the proposed model to predict whether node is normal or anomalous. In this paper, we focus the transductive setting, while our proposed

---

homophily-awarr Environment Mixup
-oo-Neihhborood Disentangled Encoder
Notations
Anomaly Node
Normal Nade
Mwm
Feclure
MW
Disentangled Encodor
Structure
Attentian
edge
Structure
M00
Structure
Adjusted Fdge Weight
Feelure
Embedding
Embedding
V(-LAUC Lorv Lpgg)
R(L Laus)
Augmeentdd Structure
Finiwiiiing
Feature
Structure
Feature
Structure
Structure
Structure
Original Edge
Classification Loss
Augmentation Loss LiP(y) pp.
DIV PER Loss
E(Py Page Hazl,
Lon Lysu
Adj
Adversarial Training
Figure I: The overall framework of our proposed HEM. The framework transforms an original graph into augmented graph by dynamically adjusting edge weights with homophily-aware environment mixup. Both graphs are processed by the neoonnegghoooood disentangled encoder to extract feature and structural representations. The original loss L and augmented loss LAUG computed using cross-entropy with the disentangled representations, while the diversity loss LDIV measures the difference between original and augmented structural embeddings, and the PER loss LPER constrains the proportion of perturbed edges to avoid trivial solutions. These losses jointly optimize the encoder and environment mixup, enhancing generalization across varying structural distributions.
method can be simply applied in inductive scenarios. Following [4 this problem as predicting the probability to be an anomaly of a node given its induced ego-graph, ie., p... A k-order ego-graph G, induced from is subgraph containing node with all of its k-hop neighbors, k is an arbitrary integer. The optimization objective to learn an optimal predictor to model the node's 's anomaly probability
15
16
we formulate
min
((J
where fe is graph neural network parameterized by 0. Denote random variable of ego-graph and node label as Gy, ye, and respective instances as Gv, Yv.
Structural Distribution Shift Structural distribution shift in node-level tasks can be treated as covariate shift, which means the ego-graph distribution different across training and test data, i.e. Ptrain (Gv) * Prest G, leading to different local structures. Therefore, we formulate this problem as an -iitt--distiiuution (OOD) problem,
min max (y.. (ow. eEE
In GAD tasks, structural distribution shift is a common problem [2], due to factors like sampling bias. For example, in e-commerce networks, accounts that transact with anomalous accounts more likely to be anomalous themselves, potentially indicating participation money laundering transactions. This will cause structural distribution shift that ego-graphs in the training set show a higher homophily ratio, i.e. the proportion of neighbors sharing the same label as the central node is much higher than that in the test set. The homophily ratio is defined as Homo(u) ju E (Y))), = Y.l. The ego-graphs with a high homophily ratio in the training stage may lead GNNs to rely on the homophilic shortcut, a spurious pattern that predicts nodes' labels by majority label in their neighborhood, and finally to fail in the test stage ego-graphs with low homophily ratio.

---

3 Method
In this section, we propose the HEM, a novel framework for graph anomaly detection under structural distribution shift by introducing two key modules, ego-neighborhood disentangled encoder and homophily-aware environment mixup.
3.1 Ego-Neighborhood Disentangled Encoder
It's critical to utilize both knowledge from ego-node and neighborhood to extract invariant patterns in graph anomaly detection for two reasons. (1) The interaction between the ego node and neighborhood indicates the discrepancy, which is important for predicting anomalies. (2) Excessive reliance on structural information results in unstable predictions under structural distribution shifts. Encoding both feature and structure information with one encoder makes the variant and invariant patterns entangled, leading performance drop under distribution shift. Most existing works simply employ a single GNN as an encoder, leading to fail in test data with distribution shift. While CoLA(T5] models anomaly probability via local discrepancy, its method faces trade-off between sampling size and speed, resulting in suboptimal performance.
To overcome these limits, propose ggo-neighborhood disentangled encoder to efficiently and effectively extract feature and structural patterns from ego graphs decoupled manner.
Neighborhood Encoder We define the k-hop neighborhood as the ego-graph for given node. The neighborhood encoder can be implemented using any commonly used message-passing-eene GNN architecture. In our framework, we adopt the B BWGNN strong backbone in GAD tasks, as the neighborhood encoder.
Given the initial node features X and the adjacency matrix A. we first employ an Multi-Layer Perceptron (MLP) projector project it into the embedding space.
Ho = Proj(X)
(3)
we can generally compute the neighborhood embeddings as follows
Hn GNN A)
Specifically, with BWGNN applied, the neighborhood embeddings can be modeled as
Hne Σ A Ho
(5)
where Å is the normalized adjacency matrix, i.e. A= D - AD 2, D the diagonal matrix. wy is the k th coefficient from a Beta polynomial.
Ego-Node Encoder The relationship between ego-node's feature and label is stable under structural distribution shift since ego-nodes only contain information about single instance. We disentangle them from structural patterns so that we can model the anomaly probability by the interaction patterns. Specifically, employ an MLP to encode the ego-node's representation. To align the neighborhood embedding space and ego-node embedding space, we utilize the same projector as the neighborhood embedding projector
Hego = Ho = (X)
The sharing projector ensures that the embeddings generated by the two encoders are aligned within the same embedding space, facilitating effective interaction between the ego node and its neighborhood embeddings.
Contrastive Prediction To capture the discrepancy between the ego-node embedding and structural embedding, we employ a bilinear function to predict anomaly probability. This design is commonly employed by contrastive learning methods [15
pyy hego: Ame) (h W Whne),
where a denotes the sigmoid function, and W is learnable weight matrix that models the interaction between the ego node and structural embeddings.

---

The classification loss can be computed
= D(Py Hegu, Hoe), Y)
(8)
where C is cross-entropy loss.
3.2 Homophily-aware Environment Mixup
Existing out-of cut-of-distribution graph anomaly detection methods suffer from issues like reliance on labeled and diverse environments 21] high memory c4) or limited performance due to lack of supervision[22)
To overcome these limitations, we propose homophily-awarc environment mixup, which generates diverse environments exhibiting effective structural distribution shifts by dynamically re- re-weighting edges based on the homophily observed among neighboring nodes. This process is both computation- ally and memory efficient.
Homophily-awann environment mixup We propose homophily-awarl environment mixup, to generate environments with structural distribution shift and improve the generalization capability of the classifier across environments with different local structures. Our objective for this module is to generate new environments with diverse local structures which is challenging enough to the classifier. This can be formulated as
max LE (ag. yo)le]. 3EE
As mentioned above, homophily is an important metric describe local structure. An obvious shift between training and test environments is the significant drop in homophily ratio. Motivated by this, we propose an attention mechanism that dynamically adjusts edge weights according the features of the nodes connected by the edge. Specifically, following (23]. we employ node-wise attention mechanism to model the connection strength between the nodes connected by the same edge as follows
(w.).) sigmoi([LcakyRRLL (irocoonnatthhhgggeee Aegoju WW),
(10)
where W is a learnable attention weight matrix. W((,,) is the adjusted weight, normalized to [0. IJ. Then apply the disentangled encoder the generated graph with the adjusted edge weights in the message passing process, resulting in ego-node and neighborhood embeddings Hego and H The augmented loss defined as:
LAUG L(P(z) H Hego Y)
(11)
Our design offers three key advantages. First, in contrast to methods that directly add or drop edges, our approach enables continuous modulation of edge weights, allowing for grained perturbation of local structures. This continuous adjustment effectively mixes the discrete states of connected and disconnected edges, providing richer spectrum of graph augmentations. Second, by optimizing the environment generator rather than directly manipulating several fully connected adjacency matrices, our method achieves significant memory efficiency. This approach circumvents the substantial memory overhead associated with storing and processing dense adjacency representations [4) Third, our method leverages the features of both endpoints of an edge to perform homophily-awan edge weight adjustments, opposed to random or uninformed modifications, leading to generating environments with diverse local structures with respect to homophily.
fine-
Diversity Loss
To ensure the module generates diverse local structures, we introduce a diversity loss that maximizes the dissimilarity between the original neighborhood embedding and the generated neighborhood embedding:
LDIV
Cosine Similarity(HHne: Hrre),
(12)
where H. Hubgrapp and H' respectively.
subgraph represent the embeddings of the original and augmented subgraphs,
5

---

Preserved Edge Ratio(PER) Loss To prevent trivial solutions, such as adjusting all edge weights zero, we regularize the environment generator to perturb only a small subset of edges. This is achieved by minimizing the following PER loss:
EEER w(e)
LPER
(13)
E
where p is the target proportion of edges to preserve from perturbation.
3.3 Overall Adversarial Training
To jointly optimize the disentangled encoder and the environment mixup, we employ an iterative adversarial training framework. This framework consists of an outer loop for training the encoder and an inner loop for training the environment mixup, ensuring that both components are optimized in coordinated manner.
Outer Loop: Training the Disentangled Encoder In the outer loop, we train the encoder using composite loss function that mixes the standard classification loss L and the augmented loss LAUG- The augmented loss LAUG ensures that the model generalizes well to environments with structural distribution shifts. The overall loss function for the outer loop is defined as:
Louter = L + LAUG-
(14)
Training the Environment Mixup In the inner loop, optimize the environment mixup to generate diverse and challenging augmented environments. The corresponding loss function combines the augmented loss - LUGG, the diversity loss LDIV, and the PER loss LPER- Specifically:
Inner Loop:
Linner = LAUG + Lpiv + LPER-
(15)
Here, -L LUG encourages to generate more challenging environments, LDIV maximizes the dissimi- larity between original and generated environments to enhance diversity, and LPER ensures that only a small subset of edges is perturbed, avoiding trivial solutions.
Training Dynamics The training process alternates between the outer and inner loops, as shown in the Algorithm. In each iteration of the outer loop, the encoder is updated to minimize Louters while in the inner loop, the environment mixup is updated to minimize Limner- This adversarial training strategy encourages to generation of new distributions with diverse local structures and improve the generalization capability across different distributions.
Algorithm Training pipeline for HEM
Require: Training epochs L, edge preservation ratio for
- I,... L do
2: Obtain H Hego, Hne for each node as described in Section 3.1
3: Calculate classification loss as Eq. 8
4: Generate new environment and calculate classification loss in generated environment LAUG
as Eq. IT
5: Calculate diversity loss LDIV and PER loss LPER as Eq. 12 and Eq.
13
6: Calculate inner loss Tanner and outer loss Toouter as Eq. 15 and Eq. 14
7: Update the homophily-aware environment mixup by minimizing inner loss
8: Update the disentagled encoder by minimizing outer loss
9: end for
3.4 Theoretical Explanation
To theoretically justify the proposed HEM framework, we analyze how promotes prediction stability and invariant learning across varying homophily ratios through a simplified example.

---

Variable Definitions. Let h denote the homophily ratio and Y E {0, 1) denote the node label, where indicates an anomalous node and normal node. Let π P(Y 1) be the anomaly rate, and denote by To the proportion of anomalous neighbors for node o:
To
Σ Y.
(16)
de aEN(e)
where d, (v) is the node degree. We assume constant node degree d. Let μ1 E[X Y 1] and Ao = [ X Y = 0]. and denote Aμr = μl μo # O. For a one-layer message paassigg encoder followed by linear classifier, the node embedding can be expressed
Z = Tufl1 + (1 - r.)po = po + TeAu..
(17)
Lemma 1 (Predictor Dependence on Homophily). The optimal coefficient that minimizes the Mean Squared Error (MSE) between predictions and labels is
Cov(Y. a (h) Var(r) h(1-A) 7(1 (0((1-))22)) 72h 13
T( (2h
(18)
Hence, the learned predictor a* depends explicitly on the homophily ratio h; a model trained under homophily for will be suboptimal for a test distribution with different hee-
Lemma 2 (Bounded Deviation the Test Distribution). If there exists such that |hte-ber S with the proposed enviromment mixup and adversarial training, the gap between the expected test loss of the training-optimal parameters and the optimal test loss is bounded. Specifically,
L(hre 0 L(hre oie) S Vinax Lyce
(19)
where Ly denotes the Lipschitz constant of f(h) = a and Viax represents the maximum of Var(r) for h satisfying Ih hul e.
4 Experiments
In this section, we conduct various experiments to verify that our proposed method can handle structural distribution shifts in graph anomaly detection tasks by utilizing the invariant patterns in the disentangled subgraph representations.
4.1 Datasets
We choose 3 commonly used GAD datasets, including Amazon, Yelp, and T-finance. We provide the details of the datasets in Appendix
4.2 Baselines
To demonstrate the effectiveness of our proposed method in addressing structural distribution shifts in graph anomaly detection tasks through complete comparison, we have selected four types of base- lines for evaluation, including (I) General GNNs: GCN[24], GAT[23,, GraphSAGE (5)) (2)GNNs Specialized for Graph Anomaly Detection: BernNet[26), BWGNN GHRN27], PCGNN
BAT[29] (3) General
Methods: GroupDRO 21,, V-REx 20), (4)Graph Out-of-
Distribution Methods: SRGNN 22
EERM 14, GDN Details of these baseline models are
provided in Appendix B
4.3 Settings
We adopt the above three real-world datasets as node-level graph anomaly detection tasks. We transform Amazon and Yelp into homogeneous graphs by simply merging all types of edges into one type to make comparison between homogeneous GNNs and heterogeneous GNNs. We divide each dataset into 2 domains, with/without structural distribution shift. For brevity, we denote domains with/without distribution shift as 'w/ DS' and 'w/o DS* separately. Specifically, we sample nodes by their homophily ratio, which means nodes with low homophily more likely to be divided
7

---

Table 1: Results of different methods real-world graph anomaly detection datasets. The best
results are in bold and the second- best results are underlined. The results are reported in AUPRC.
Dataset Model
Amazon
Yelp
T-Finance
w/o DS
w/ DS
w/o DS
w/ DS
w/o DS
w/ DS
GCN
94,45 11.97...97
69.90.12.13
53.63
40.7911.77
93.66.10.00
60.33 10.41
GAT
92.84=0.00
+0.04
54.74+0.00
42.83++0.00
87.38+0000
53,93+0000
GraphSAGE
90.57
69.71
63.05-10.24
53.25
73.61
44.21
BernNet
92.83=0.02
7..24
52.99+00.0
48.53+00.2
89.25+0.71
65.21 +0.58
PCGNN
90,951000
12.02
54.0510.78
1..52
19.37
16.07
GHRN
92.01
69.39
59.27
54.6810.61
93.62.10.15
62.43 1.036
BWGNN
91.59=0.20
69.26+00.8
58.21
52.97=
93,44++0.10
62.74
BAT
94.03+2.04
1..26
62. 19.2.1
54.93+0049
92.77++0.7
16.35
V-REx
92.54=0.14
40.24
59.16+0.70
53.58
93.04-+0.12
60.66+00.7
GroupDRO
92.58:0.00
68.87
58.73:10.66
52.13
93.86:10.13
60.81 1:028
SRGNN
90.48=0.36
70.36++0.56
58.73+00.1
52.84
91.1 +::24
60,36+00.1
EERM
92.57
70.94
00M
OOM
OOM
0OM
GDN
91.97
68.93340.4
48.20+1.13
48.43+1092
92.51
59.84=0005
HEM(+GCN) 93.70=
70.59
55.09
52.05=+1.0
95.69-1000
64. 64.97:0.11
HEM(+BWGNN)
91.97=0.74
74.91 :0049
61.42.00.6
18.45
94.76++0.06
66.04
Table 2: Results of different methods on real-world graph anomaly detection datasets. The best
results are bold and the second- results are underlined. The results are reported Recall @ K.
Model Model
Amazon
Yelp
T-Finance
w/o DS
w/ DS
w/o DS
w/ DS
w/o DS
w/ DS
GCN 90.18+1001
65.37
51.95++0.24
89.57+0.22 44.04
57. $7.50+0.99
GAT
90.22
66.9910.83
16.42
48.1 10.000
82.59
31,8810.0
GraphSAGE
88.1810..6
65.20.10.61
58.92
51.01 1.049
65. 65.88
43.68
BernNet
89.74 1.65
1.66
65.53.11.88
52.33
47.89 1.0.25
86.59
62.31 10.18 10.18
PCGNN
89.55 1..64
66.67
50.8910.12
43.14.00.08
80.08
53.36
GHRN
89.55
62.93+0.00
54.96+0.54
51.13++0.77
87.53+0.69
60. 60.16+228
BWGNN
90.00
63.90.10.00
54.98
50.33.10.7
87.76.10.84
60.75
BAT
90.18
66.99.0.83
56.80
51.37:12.14
88.83
56.54.0072
V-REx
89.24
62.76:1092
54.94.10.25
51.37:10.54
86.82..019
59. 19.72.1028
GroupDRO
89.55
61.63+0061
55.63++0.54
51.09
88.63+0.29
60.53+031
SRGNN
90.00
63.41 1:0.40
54.31 -:0.58
50.79110.9
87.92-10.73
59. 19.20+1.10
GDN
89.39
64.88
49.34
48.21
85.73+0022
58.024091
HEM(+GCN)
90.45 :0.45:0.000
65.85
52.83:10.49
49.47:10.20
90.27:t044
62.23
HEM(+BWGNN)
90.15 15.221
67.80-10.50
56. 1040.6
52.63310.28
90.4311022
63. 1211.00
into test data(" w/ DS'). Furthermore, we divide the "w/o DS' domain into training, validation, and test(" w/o DS') data. Since graph anomaly detection datasets are usually with severe data imbalance, we use AUPRC (Area Under the Precision- Recall Curve) and Recall @ K (the recall among the top- highest-confidence predictions) as the evaluation metrics.
4.4 Results
Based on the results in Table I we can get the following observations:
Baselines all fail significantly under structural distribution shift: (1) Although baseline methods performs well on test data without distribution shift, they all experience a significant performance drop on test data with structural distribution shift. This phenomenon indicates that these methods may rely spurious patterns that can not be generalized to the test ( ('w/ DS') environment.
8

---

Table 3: Ablation studies on ego-neighborhood disentangled encoder and homophily-awann environ- ment mixup, where 'wo END' denotes removing the ego-neighborhood disentangled encoder, 'w/o DIV" denotes removing diversity loss and 'w/o PER' denotes removing PER loss. The best results are in bold and the second-best results are underlined. The results are reported in AUPRC.
Dataset Model
Amazon
Yelp
T-Finance
w/o DS
w/ DS
w/o DS
w/ DS
w/o DS
w/ DS
w/o END encoder
=0.41
58.33++1.09 1..5
56.53++0.00
94.52++0.3
50
w/o DIV
93.3410064
70.96:1164
61.0810. 10.89
57.52.11.18
94.0810.71
64.73
w/o PER
92.45=0004
72.06=0.16
60.07+0.88
56,00++0.55
94.88+10.15
65.50+051
HEM(+BWGNN)
91.97
74.91:10.49
61.42:10.56
58.45
94.76:10.06
66.041.0.99
For example, strong baseline GHRN, experiences performance drop of nearly 25%, 8%, 33%. (2) cut-of-distribution baselines all fail to achieve consistent improvement across all datasets. Compared with BWGNN, the backhone classifier used in these OOD methods, some of the OOD baselines can achieve improvement on specific datasets, like EERM in Amazon and V- REx in Yelp. However, none of them achieves consistent generalization improvement across all datasets, indicating these OOD methods rely on diverse training environments with ground- truth environment labels, e.g. V-REx, GroupDRO, SRGNN, EERM employs the REINFORCE algorithm to create diverse training environments by directly optimizing multiple edge masks, which costs too much memory resources.
Our proposed method achieves consistent performance improvement across all datasets. Com- pared with the best baselines, our method achieves relative improvements of 3.4%, 6.9%, and 1.3% on test ('w/ DS') data, and outperforms all general and This implies that our method can capture the invariant patterns consistently, and create new environments a memory-effiiiee manner.
OOD baselines.
4.5 Abaltion Study
In this section, we conduct ablation studies to verify the effectiveness of our proposed ego- neighborhood disentangled encoder and homophily-aware environment mixup.
Ego-neighborhood disentangled encoder We remove the disentangled encoder and simply apply GNN encoder. From 3 we can find that without ego-neighborhood disentangled encoder, the model's performance drops significantly in 'w/o DS' and 'w/ DS' test data across all datasets, which implies the disentanglement design important modeling feature and structural information in GAD tasks.
Hoomophily-awarr environment mixup We remove the diversity loss ('w/o DIV") and preserved edge ratio loss ('w/o PER') separately, and both of them show significant performance drops in Table 3 Specifically, removing diversity loss leads to consistent performance drop across all datasets, but removing PER loss increases the performance on T-Finance, implying that deleting large proportion of edges T-Finance can increase the generalization capability while preserving the performance in the training stage. This can be verified in the hyperparameter sensitivity analysis. Moreover, our proposed method reduced overfitting the training stage by adding the diversity loss and preserved edge ratio loss. For example, in the Amazon dataset, the models removing diversity loss or removing PER loss perform better the test("wd w/o DS') but worse in the test( w/ DS*).
4.6 Complexity Analysis
In this section, we analyze the computation complexity of HEM. Denote [ and |E| as the total number of nodes and edges in the graph, and denote d the dimension of hidden representation. The ego-neighborhood disentangled encoder has time complexity of O dd + |E d)). The homophily- aware environment mixup has a time complexity of O EI Eld EE = O Eld), including the edge reweighting and computation of diversity loss and PER loss. Therefore, the total computation complexity for HEM is ((V]d + |F]d). HEM has a linear computation complexity with respect to the number of nodes and edges, comparable to existing GNN baselines.

---

5
Related Work
In this section, we review the existing works about graph anomaly detection and -utto--distribution generalization.
Graph Anomaly Detection and heterophily[I]. and extensive works are proposed to solve these problems from spatial and spectral prospectives 34). For spatial methods, PCGNN proposes balanced sampler for the neighborhood aggregation process in GNNs to reduce data imbalance. BAT(29) further proposes a class-rebalancing--e data augmentation framework based on topological paradigm, which can mitigate the class-imbalance bias and achieve consistent performance boosting across general class imbalance node classification tasks. GAS[35] utilizes structural preprocessing to handle severe heterophily before applying the GNN model. CARE-GNN[36, PMP[37] GraphConsis propose to design new message passing and aggregation mechanisms to mitigate the influence of heterophily on prediction. Another type of method like H2-FDetector (39 decouples the information aggregation for homophilic and heterophilic patterns. Since traditional graph convolution is known low- frequency [40), extensive spectral GNN methods are proposed to handle high-frequency signals in heterophilic graphs[41] (2]. B BWGNN[18] propose polynomial spectral GNN with Beta kernel as prior, which is proved to fit the spectral energy distribution in GAD scenario and achieves obvious performance improvement compared with BernNet 26]. which has no prior and tries to learn a kernel from all possible polynomial functions. AMNet[43 tries to learn high-frequency and low-frequency signals separately and combines them for prediction. While these GAD-specific methods have achieved substantial progress, there is still room for further enhancement. They fail to adequately model the interaction patterns between the ego-node and its surrounding neighborhood, which could potentially reveal discrepancies that are crucial for more accurate anomaly identification.
The common challenges in graph anomaly detection are data imbalance
Out-of- Disttribution in Graph (OOD) The structural distribution shift is a prevalent issue in graph data. For example, variations in disciplines and time periods may result in different citation patterns in citation networks, and variations in geographic locations and relationship types result in different interaction types in social networks. Existing OOD methods can be divided into general methods and graph specialized methods[44455). General OOD approaches, such V-REx [20] and [201, commonly depend on diverse training environments characterized by explicit environment labels, a challenging requirement in graph anomaly detection where inherent homophily obscures environment distinctions. While graph-specifi OOD methods have emerged, limitations persist. For instance, [ERM[4] constructs novel training environments using learnable graph editors and trains with V-REx to learn invariant representations, yet incurs significant memory overhead due to maintaining multiple full adjacency matrices. SRGNN [22 utilizes the kernel mean matching method to regularize the discrepancy between embeddings of training and test data, while the lack of supervised information leads to its limited performance. G2 & is the first work to address structural distribution shift in graph anomaly detection. They handle the problem in an invariant learning way by identifying the critical anomaly features with gradients, while neglecting the importance of varying local structures in distribution shift. In conclusion, prevailing methodologies still have limitations prominently including memory inefficiency, insufficient availability of supervised information, neglect of inherent local structural patterns, and undue reliance specific training environment assumptions.
Conclusion
In this paper, we proposed the -gg-Neighboroood Disentangled Encoder with Homophily-awan Environment Mixup (HEM), for improving the OOD generalization performance for GAD problems. First, we proposed an ego-neighborhood disentangled encoder to disentangle feature and structural representations, in order to model discrepancy patterns and discover invariant patterns. Then, we proposed the homophily-aware environment mixup to generate training environments with diverse local structures to improve the generalization capability of the model. Our model achieves consistent improvement across all datasets.
10

---

Acknowledgments and Disclosure of Funding
This work was supported by the National Key Research and Development Program of China (No. 2022ZD01 15903, 2023YFF1205000
National Natural Science Foundation of China No. 62222209, Beijing National Research Center for Information Science and Technology under Grant No. BNR2023TD03006, and Beijing Key Lab of Networked Multimedia.
References
[1] X. Ma, J. Wu, S. Xue, J. Yang. C. Zhou, Q Z. Sheng, H. Xiong, and L. Akoglu, "A comprehen- sive survey on graph anomaly detection with deep learning," IEEE Transactions on Knowledge and Data Engineering, vol. 35, no. 12, pp. 12012-12 038, 2021.
[2] X. Huang, Y. Yang, Y. Wang, C. Wang. Z. Zhang, J. Xu, L. Chen, and M. Vazirgiannis, "Dgraph: large-scale financial dataset for graph anomaly detection," Advances in Neural Information Processing Systems, vol. 35, pp. 22 72576222277 777, 2022.
[3] M. Weber, G. Domeniconi, J. Chen, D. K. I. Weidele, C. Bellei, T. Robinson, and C. E. Leiserson, "Anti-money laundering in bitcoin: Experimenting with graph convolutional networks for financial forensies," arXiv preprint arXiv: 02591/, 2019.
[4] I.. Cheng, R. Guo, K. Shu, and H. Liu, "Causal understanding of fake news dissemination on social media," " Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, 2021, pp. 148-157.
[5] X. Yuan, N. Zhou, S. Yu, H. Huang, Z. Chen, and Xia, "Higher-order structure based anomaly detection on attributed networks," in 2021 IEEE International Conference Big Data (Big Data). IEEE, 2021, pp. 2691-2700.
[6] J. Tang, F. Hua, Z. Gao, P. Zhao, and J. Li, "Gadbench: Revisiting and benchmarking supervised graph anomaly detection," " Advances in Neural Information Processing Systems, vol. 36, pp. 29 628 29 653, 2023.
[7] J. Chen, G. Zhu, C. Yuan, and Y. Huang, "Boosting graph anomaly detection with adaptive message passing," in The Twelfth International Conference Learning Representations.
[8] Y. Gao, J. Li, X. Wang, X. He, H. Feng, and Y. Zhang, "Revisiting attack-caused structural distribution shift in graph anomaly detection," JEEE Transactions Knowledge and Data Engineering, vol. 36, no. 9, pp. 4849-4861, 2024.
[9] M. Wu, X. Zheng, Q. Zhang, X. Shen, X. Luo, X. Zhu, and Pan, "Graph learning under distribution shifts: A comprehensive survey on domain adaptation, out-of-distribution, and continual learning." arXiv preprint vrXiv22402.16374 2024.
[10) W. Bao, Z. Zeng, Z. Liu, H. Tong, and J. He, "Adarc: Mitigating graph structure shifts during test-time." " arXiv preprint arXiv:2410.06976. 2024.
[11] S. Liu, T. Li, Y. Feng, N. Tran, H. Zhao, Q. Qiu, and P. Li, "Structural re-ieighting improves graph domain adaptation," in International Conference on Machine Learning. PMLR, 2023, pp. 21 778-777 793.
[12] Y. Gao, X. Wang. X. He, Z. Liu, H. Feng, and Y. Zhang, "Alleviating structural distribution shift in graph anomaly detection," in Proceedings of the sixteenth ACM international conference on web search and data mining, 2023, pp. 357-365.
[13] E. Altman, J. Blanuša, I.. Von Niederhäusern, B. Egressy, A. Anghel, and K. Atasu, "Real- istic synthetic financial transactions for anti-money laundering models," Advances in Neural Information Processing Systems, vol. 36, 2024.
[14] Q WU, H. Zhang, J. Yan, and D. Wipf, "Handling distribution shifts on graphs: An invariance perspective," arXiv preprint ar arXiv: 2022.

---

[15] Y. Liu, Z. Li, S. Pan, C. Gong, C. Zhou, and G. Karypis. "Anomaly detection on attributed networks via contrastive self-supervised learning," IEEE transactions on neural networks and learning systems, vol. 33, no. 6, pp. 2378- 2392, 2021.
[16) Z. Zhang, X. Wang, Z. Zhang, H. Li, Qin, and W. Zhu, "Dynamic graph neural networks under spatio-temporal distribution shift," Advances in neural information processing systems, vol. 35, pp. 6074-6089, 2022.
[17] Z. Zhang. X. Wang, Z. Zhang. Z. Qin, W. Wen, H. Xue, H. Li, and W. Zhu, "Spectral invari- ant learning for dynamic graphs under distribution shifts," " Advances in Neural Information Processing Systems, vol. 36, 2024.
[18] J. Tang, J. Li. Z. Gao, and Li, "Rethinking graph neural networks for anomaly detection," " in International Conference Machine Learning. PMLR, 2022, pp. 21 076-21 089.
[19] A. v. d. Oord, Y. Li, and O. Vinyals, "Representation learning with contrastive predictive coding," arXiv preprint arXiv: 807.03748 2018.
[20] D. Krueger, E. Caballero, J.-H. Jacobsen, A. Zhang. J. Binas, D. Zhang, R. Le Priol, and A. Courville, "Out-of-disttriutioo generalization via risk extrapolation (rex)," in International conference on machine learning. PMLR, 2021, pp. 5815-5826.
[21] S. Sagawa, W. Koh, T. B. Hashimoto, and P. Liang, "Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case generalization," arXiv preprint 1XXiv:91110877
2019.
[22] Q. Zhu, N. Ponomareva, J. Han, and B. Perozzi, "Shift-robust gnns: Overcoming the limitations of localized graph training data," Advances in Neural Information Processing Systems, vol. 34, pp. 27 965 27 977, 2021.
[23] Velickovic, G. Cucurull, A. Casanova, A. Romero, P. Lio, Y. Bengio et al., "Graph attention networks," stat, vol. 1050, no. 20, pp. 10-48 550, 2017.
[24] T. N. Kipf and M. Welling, -upervsupe classification with graph convolutional networks," arXiv preprint arXiv: 1609:00999002900 2016.
[25] W. Hamilton, Z. Ying, and Leskovec, "Inductive representation learning on large graphs," Advances in neural information processing systems, vol. 30, 2017.
[26] M. He, Z. Wei, H. Xu et al., "Bernnet: Learning arbitrary graph spectral filters via bernstein approximation," Advances in Neural Information Processing Systems, vol. 34, pp. 14 1329 14251, 2021.
[27] Y. Gao, X. Wang, X. He, Z. Liu, H. Feng, and Y. Zhang. "Addressing heterophily in graph anomaly detection: A perspective of graph spectrum," in Proceedings of the ACM Web Confer- ence 2023, 2023, pp. 1528-1538.
[28] Y. Liu, X. Ao, Z. Qin, J. Chi, J. Feng, H. Yang, and Q. He, "Pick and choose: a gon-based imbalanced learning approach for fraud detection," in Proceedings of the web conference 2021, 2021, pp. 3168-3177.
[29] Z. Liu, R. Qiu. Z. Zeng, H. Yoo, D. Zhou, Z. Xu, Y. Zhu, K. Weldemariam, J. He, and H. Tong. Class-imbalanced graph learning without class rebalancing," 2024.
[30] Y. Lin, J. Tang, C. Zi, H. V. Zhao, Y. Yao, and J. Li, "Unigad: Unifying multi-leved graph anomaly detection," arXiv preprint arXiv:2411.066 2024.
[31] Q. Wang, G. Pang, M. Salehi, Xia, and C. Leckie, "Open-set graph anomaly detection via normal structure regularisation," arXiv preprint arXiv:231 12223311..080 I.06835, 2023.
[32] Zhang, S. Wang, and S. Chen, "Reconstruction enhanced multi-view contrastive learning for anomaly detection attributed networks," arXiv preprint arXiv:2205.04816, 2022.
12

---

[33] J. Duan, B. Xiao. S. Wang, H. Zhou, and X. Liu, "Arise: Graph anomaly detection on attributed networks via substructure awareness," IEEE transactions on neural networks and learning systems, 2023.
[34] R. Guo, M. Zou, S. Zhang, X. Zhang, Z. Yu, and Z. Feng, "Graph local homophily network for anomaly detection," " in Proceedings of the 33rd ACM International Conference on Information and Knowledge Management, 2024, pp. 706-716.
[35] A. Li, Z. Qin, R. Liu, Y. Yang, and D. Li, "Spam review detection with graph convolutional networks," Proceedings of the 28th ACM International Conference on Information and Knowledge Management, 2019. [Online]. Available: http::/aap..mmaatttssssaa..r..ro 201660501
[36] Y. Dou, Z. Liu, L. Sun, Y. Deng, H. Peng, and S. Yu, "Enhancing graph neural network-based fraud detectors against camouflaged fraudsters," " in Proceedings of the 29th ACM international conference on information & knowledge management, 2020, pp. 315-324.
[37] W. Zhuo, Z. Liu, B. Hooi, B. He, G. Tan, R. Fathony, and J. Chen, "Partitioning message passing for graph fraud detection," in The Twelfth International Conference on Learning Representations, 2024.
[38] 7. Liu, Y. Dou, P. S. Yu, Y. Deng, and H. Peng, "Alleviating the inconsistency problem of applying graph neural network to fraud detection," in Proceedings of the 43rd international ACM SIGIR conference research and development in information retrieval, 2020, pp. 1569-1572.
[39] F. Shi, Y. Cao, Y. Shang, Y. Zhou, C. Zhou, and Wu, "H2-fdetector: A gnn-based fraud detector with homophilic and heterophilic connections," " in Proceedings of the ACM web conference 2022, 2022, pp. 1486-1494.
[40] D. Bo, X. Wang, C. Shi, and H. Shen, "Beyond low- wwwffreueneyy information in graph convolu- tional networks," " in Proceedings of the AAAI conference on artificial intelligence, vol. 35, no. 5, 2021, pp. 3950-3957.
[41] E. Chien, Peng, P. Li, and O. Milenkovic, "Adaptive universal generalized pagerank graph neural network," " arXiv preprini arXiv:2006.07990 07988, 2020.
[42] Y. Gao, J. Fang, Y. Sui, Y. Li, X. Wang, H. Feng, and Y. Zhang, "Graph anomaly detection with bi-level optimization," " in Proceedings of the ACM Web Conference 2024, ser. WWW '24. New York, NY. USA: Association for Computing Machinery, 2024, p. 4383 4394. [Online]. Available: https://6o..org00.111////3/////3
[43] Z. Chai, S. You, Yang. S. Pu, J. Xu, H. Cai, and W. Jiang, "Can abnormality be detected by graph neural networks?" in IJCAI, 2022, pp. 1945-1951.
[44] X. Han, Z. Jiang, N. Liu, and X. Hu, "G-mixup: Graph data augmentation for graph classifica- tion," in International Conference on Machine Learning. PMLR, 2022, pp. 8230-8248.
[45] G. Liu, T. Zhao, J. Xu, T. Luo, and M. Jiang, "Graph rationalization with environment based augmentations," in Proceedings of the 28th ACM SIGKDD Conference Knowledge Discovery and Data Mining, 2022, pp. 1069-1078.
[46] K. Kong, G. Li, M. Ding, Z. Wu, C. Zhu, B. Ghanem, G. Taylor, and T. Goldstein, "Robust optimization as data augmentation for large-scale graphs," in Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, 2022, pp. 60-69.
[47] S. Fan, X. Wang, C. Shi, P. Cui, and B. Wang, "Generalizing graph neural networks on out- of-distribution graphs," IEEE Transactions on Pattern Analysis and Machine Intelligence. 2023.
[48] Y.-. WU, X. Wang, A. Zhang, X. He, and T.-S. Chua, "Discovering invariant rationales for graph neural networks," arXiv preprint (0w:220).118722 2022.
[49] Q Zhu, C. Zhang, C. Park, C. Yang, and Han, "Shift-robust node classification via graph adversarial clustering," arXiv preprint arX1v:2203.15802, 2022.
13

---

[50] J. Ma, J. Deng, and Q. Mei. "Subgroup generalization and fairness of graph neural networks," Advances Neural Information Processing Systems, vol. 34, pp. 1048-1061, 2021.
[51] Y. Qin, X. Wang, Zhang, Xie, and W. Zhu, "Graph neural architecture search under distribution shifts," in International Conference Machine Learning. 18 083008 095.
PMLR, 2022, pp.
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The main claims can be verified in the Experiments Section.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [NA]
Justification: This paper proposes a new GAD OOD method a structural distribution shift setting and shows no obvious limitations.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
15

---

Justification:
The assumptions and proofs can be found in the Appendix E
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The details can be found in the Experiments Section, especially the settings subsection.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
16

---

Answer: [NA]
Justification: The data used in this paper are all public datasets, and it requires some time to get the code fully prepared be released.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm ec/
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips. //nips.cc/ppl wwwppbblccgguiecuceccccccooooope hetggudddsse/eebbbinninn httSSSabmiiiiooooiiioiooooi for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: This can be found in the Experiments Section.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
This can be found Table
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
17

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The details can be found in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics http:p/p/..aarr.....oooooo/aaaaa
Answer: [Yes]
Justification:
This research is with the NeurIPS Code of Ethics in every respect.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper is focusing on improving the OOD algorithm in GAD problems, with little impact on society.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
18

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This paper has no such risks since it's an improved OOD method without releasing any data or models that have a high risk for misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: This can be found in the Experiments and Related Work Sections.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the batasets.papersstt paperswi thcode. cww/ datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
19

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not involve such experiments.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
20

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The method does not involve LLMs any important, original, non- standard components.
Guidelines:
The answer NA means that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
21

---

A Datasets
A.1 Dataset Details
Amazon. The task of the Amazon dataset is identify anomalous users who wrote fake reviews for products under the Musical Instrument category on the Amazon website. Uses are nodes in the graph and there are three types of edges: U-P-U (connects users reviewing least one same product), U-S-U (connects users giving at least one same star rating within one week), U-V-U (connects users with top 5% mutual review text similarities among all users). The node features are handcrafted features about user information.
Yelp. Yelp dataset includes hotel and restaurant reviews, and the task is to filter spam reviews. The reviews are nodes in the graph and there are three types of edges: R-U-R (connects reviews posted by the same person), R-S-R (connects reviews about the same product with the same rating). R-T-R (connects reviews about the same product while posted in the same month). The node features are handcrafted features from raw texts.
T-Finance. T-Finance dataset is about transaction network and the target is to find anomaly accounts. The nodes are accounts and the edges are transactions between accounts. The node features are user profile details like registration days.
A.2 Dataset Split Method
The dataset is divided by the homophily ratio of nodes, split into 50%%/00%%/0%/20% for training, validation, in-distribution test, and out-of-distribution (OOD) test sets, respectively.
The bottom 20% of nodes with the lowest homophily ratios selected to form the OOD test set.
B Baseline Models
General GNNs: GCN[24] utilizes convolution operation aggregate messages from the neigh- borhood and achieves excellent performance in semi-supervised graph tasks. GAT(23] adds an attention mechanism to the message passing process, assigning different weights to edges in order to aggregate information from important neighbors. GraphSAGE utilizes neighborhood sampling methods fit inductive learning.
GNNs Specialized for Graph Anomaly Detection: BernNet utilizes a K-order Bernstein polynomial approximation to estimate arbitrary graph spectral filers. BWGNN [8] uses Beta distribution prior for spectrum distribution of graph anomaly detection data. GHRN[271 drops inter-class edges delineate high-frequency components and increases the homophily of heterophilic dataset. PCGNN 28 designs a label-balanced sampler to sample nodes and edges within neighborhoods to increase Bemoophil.BBTT/II proposed plug-and -un--and-lay framework that dynamically augments the graph topology via uncertainty-brat based node risk estimation and virtual connections.
Methods: GroupDRO 21] puts weights worst-case across different training domains. V-REx enhances out-of-distributioo generalization by extrapolat- ing risks and minimizing the variance of losses across different environments.
General
Graph Out-of-Diie Distribution Methods: SRGNN uses kernel mean matching to regularize the difference in the distributions of training and test nodes' embeddings, in order to avoid learning spurious embedding distribution. [ERM[[] utilizes REINFORCE to create diverse environments at the training stage to enhance generalization capability. GDN[12] designs invariance losses and uses gradient descent on input features to filter invariant features.
Hyperparameter Sensitivity Analysis
C.1 Edge Preservation Ratio
We analyze the sensitivity of the hyperparameter P, the edge preservation ratio in PER loss from Equation 13 From 2 we can find proper p is neither too small nor too big. A small p means preserving only small proportion of edges, which may destroy the invariant patterns, and a big lead to structural distribution without much shift. A perfect choice of p is a balance of both aspects.
22

---

01 Aeees
We
Selwee
Figure Sensitivity of hyperparameter p. The shows the average AUPRC and standard deviations in the test(w// DS') data. The dashed line represents the average AUPRC of the best- performed baseline.
C.2 Advaserarial Training
AUPRC
etaaoon 35
arT4230 DS
0.7
0.73
0.70
100
300
500
Inner loop stepa
outer loop steps
Figure Sensitivity of inner/outer training steps in the adversarial training. The area shows the average AUPRC and standard deviations in the amazon test(" w/DS"). By default we choose inner loop steps = and outer loop steps 500.
We conducted an extensive analysis on the Amazon dataset to evaluate the sensitivity of HEM to the number of inner loop and outer loop steps. Our findings indicate that for the outer loop steps, the model demonstrates robust performance as long as the training steps are not excessively limited. Conversely, the model exhibits relatively higher sensitivity to the inner loop steps. Utilizing smaller number of inner loop training steps allows for the generation augmented graphs with an appropriate level of difficulty, thereby facilitating casier model convergence.
D Case Study
Homogeneous Ratio for yelp
original adjusted
0.4
0.0
anomaly
Figure 4: Case Study of Homophily Ratio in Yelp Dataset.
23

---

In the case study, we analyze the homophily ratio of anomaly and normal nodes in Yelp dataset. During the data preprocessing. we construct structural distribution shift by sampling nodes with high homophily ratio as training data, leading to a shortcut to predict the label of central node by its neighbors. From Figure the model has learnt to adjust edge weight to decrease the homophily ratio of the total graph and discovered patterns based on the augmented graph.
E
Theoretical Proofs
E.1
Lemma (Predictor Dependence on Homophily)
The optimal coefficient that minimizes the Mean Squared Error (MSE) between predictions and labels is
Cov(Y.r) Var(r)
T (2h
a (h)
(20)
h(1-h) T(1 (2h 1)²
d
Firstly, the value of some key statistical properties are:
Cov(Y, = π T) (2h - 1),
Var(Y) T(1 T),
Var(r Y-y) b((-A)
Var(r) h(1-h) + TI T) r2h - 1)2.
d
For a one-layer message-passing GNN followed by a linear classifier, the node embedding Zp is: Z. (AX) ru/l + (1 re)po po + r.
(21)
The final prediction Y, is then:
V, w/ no + (w Au) rg.
(22)
The optimal coefficient a that minimizes the Mean Squared Error (MSE) is given by linear regres- sion:
a' Cov(Y,r) m(1 - π (2h - 1) Var(r)
(23)
M(1-A) + x11 - xt) (2h 1)2
Lemma (Bounded Deviation on the Test Distribution). there exists an e such that |iee her S with the proposed environment mixup and adversarial training, the gap between the expected test loss of the training-optimal parameters and the optimal test loss is bounded. Specifically,
L(hee )fr)) L(he, Ofee) Vinax L,c²
(24)
where Ly denotes the Lipschitz constant of f(h) = añ, and Vmax represents the maximum of Var(r) for satisfying (h hul S
For simplicity, we define:
C(h) Cov(Y,r) T(1 T)) (2h 1),
(h) Var(r) M(1-)) d + +T(11 (2h - 1)2.
Then the MSE Loss is:
a();a) = E((Y - 8)3 h] V(h) 2xC(h) + (V))
(25)
Define the optimal a on h as a² = s(h)
C(h) v(ny. and the optimal loss as:
L' v C(h)²
(26)
V(h)
24

---

We assume HEM trains on H. [hier her + c] by applying environment mixup, which covers hig-
Define:
fuin inf f(h),
fmax Su f(h),
Vmax = suPhEH. ((h).
Then
a(k;a) (*(h) + ((h)(a- s(h))
(27)
therefore we can get the upper bound of the loss difference:
a( -
< sup (a - f(h))² S Viaxx
sup (a s(1))2)
kEH.
NEE
Since the goal of adversarial training in HEM is to minimize the loss in the worst case, we further assume HEM can minimize the upper bound, then:
min + fmax
(28)
2
Thus,
Fmax fmin 2 ))
a(:;a) (h) S Viaax
sup hEH.
(29)
If follows Lipschitz continuity, then
fmax Smin S La ((her + (Ntrr - -()) 2L.
(30)
Finally,
- S Vmax 1.7e².
(31)
Configurations
All experiments conducted with:
Operating System: Ubuntu 20.04.6 LTS
CPU: Intel(R) Xeon(R) Gold 6348 CPU @ 2.60GHz
GPU: NVIDIA GeForce RTX 4090 with 24 GB of memory
Software: Python 3. 12.4; CUDA 12.2; PyTorchh 2.4.1
25


Reviews:
[{"review_id": "Gnzdgity7l", "reviewer": "Reviewer_RDof", "summary": "This paper addresses the problem of graph anomaly detection (GAD) under structural distribution shifts, a scenario where models trained on graphs with high homophily perform poorly on test graphs with lower homophily due to selection bias in real-world data. The authors propose a novel framework, HEM (Ego-Neighborhood Disentangled Encoder with Homophily-aware Environment Mixup), to tackle this challenge. The framework consists of two key contributions:\n1.  An **Ego-Neighborhood Disentangled Encoder** that separates the learning of a node's own features from its neighborhood's structural information. This is designed to capture invariant patterns from node features while isolating them from the spurious correlations that arise from shifting structural patterns.\n2.  A **Homophily-aware Environment Mixup** module that adversarially generates diverse training environments by re-weighting graph edges. This forces the encoder to learn representations that are robust across different structural distributions in a memory-efficient manner.\n\nThrough an adversarial training process, the model learns to generalize better to out-of-distribution data. Extensive experiments on three real-world datasets demonstrate that HEM significantly outperforms a wide range of baselines, achieving state-of-the-art performance for GAD under structural distribution shift.", "questions": "1.  The core motivation is to learn \"invariant patterns\" by disentangling ego and neighborhood representations. Could you provide a more direct, qualitative analysis to support this? For instance, using an embedding visualization technique (like t-SNE) to show that the ego-embeddings ($H_{ego}$) for a given class (anomalous/normal) are clustered more tightly across the \"w/o DS\" and \"w/ DS\" domains compared to the neighborhood embeddings ($H_{ne}$)? This would provide strong evidence that the disentanglement is working as intended.\n2.  Your environment mixup module is positioned as a memory-efficient alternative to methods like EERM. While EERM resulted in an \"Out of Memory\" (OOM) error on most datasets, it did run on the Amazon dataset. Could you provide a quantitative comparison of the training time and peak memory usage of HEM versus EERM on the Amazon dataset to concretely substantiate this advantage?\n3.  You claim that the ego-neighborhood disentangled encoder is a general framework applicable to various GNNs. Have you performed any experiments by substituting the BWGNN neighborhood encoder with other GNN architectures (e.g., GCN, GAT, or GraphSAGE)? Showing that the HEM framework still provides a significant boost would greatly strengthen this claim of generality.\n4.  The adversarial training framework involves an inner and outer loop. Can you comment on the stability and convergence of this training process? How sensitive is the model's final performance to the number of training steps in the inner loop (for the environment mixup) versus the outer loop (for the encoder)?", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "**Strengths:**\n\n* The paper tackles a critical and practical problem in graph machine learning. Structural distribution shift is a common issue in real-world applications like financial fraud and bot detection, and the paper clearly motivates how homophily shortcuts can lead to poor generalization. This work represents a significant step towards creating more robust GAD systems.\n* The proposed HEM framework is novel and well-conceived. The combination of a disentangled encoder and an adversarial environment generator is an original approach to this problem. The environment mixup mechanism, which uses continuous edge re-weighting via an attention mechanism, is a particularly clever and efficient alternative to prior work like EERM that required manipulating multiple large adjacency matrices.\n* The paper demonstrates high quality in its methodology and evaluation. The proposed method is technically sound, and the components are well-integrated into a coherent adversarial learning framework. The experimental evaluation is comprehensive, comparing HEM against an extensive list of 13 baselines across four relevant categories (General GNNs, GAD-specific GNNs, General OOD, and Graph OOD methods)\n* The paper is well-written, clearly structured, and easy to follow. The problem is precisely formulated, and the proposed solution is motivated and explained in detail.\n\n**Weaknesses:**\n\n* While the paper's motivation hinges on discovering \"invariant patterns\", the analysis does not offer a qualitative look into what these patterns are. The case study in Figure 3 shows that the mixup module successfully alters the graph's homophily ratio, but a deeper analysis (e.g., embedding visualization) to show that the ego-embeddings are indeed more \"invariant\" than the neighborhood embeddings across different distributions would be highly insightful.", "was_revised": true, "final_justification": "It has addressed my concerns, and I will keep my score.", "rebuttal": "1. Our primary objective with environment mixup is to mitigate the spurious connection between the proportion of anomalous nodes in the neighborhood and the label, a connection often induced by high homophily. The overarching goal of the HEM framework is to achieve invariant ego and neighborhood distributions. Consequently, our methodology aims to simultaneously enhance the performance concerning both ego and neighborhood representations. The overall improvement in performance, while evident in the final results, is also directly substantiated by the ablation study, where the significant performance degradation observed when operating \"w/o END encoder\" clearly demonstrates the crucial role of disentanglement.\n\n2. | Model | Peak GPU Memory Usage | Training Time |\n| ----- | --------------------- | ------------- |\n| EERM  | 21.05 GB              | 489.19 s      |\n| HEM   | **0.92 GB**           | **45.67 s**   |\n\n3. We change the neighborhood encoder from BWGNN to GCN, HEM also improves the performance.\n\n|            | ('amazon', 'w/o DS') | ('amazon', 'w/ DS') | ('yelp', 'w/o DS') | ('yelp', 'w/ DS')  | ('tfinance', 'w/o DS') | ('tfinance', 'w/ DS') |\n| :--------- | :------------------- | :------------------ | :----------------- | :----------------- | :--------------------- | :-------------------- |\n| GCN        | **0.9445(0.0097)**   | 0.6990(0.0213)      | 0.5363(0.0094)     | 0.4079(0.0173)     | 0.9366(0.0010)         | 0.6033(0.0041)        |\n| HEM (+GCN) | 0.9370(0.0011)       | **0.7059(0.0009)**  | **0.5509(0.0047)** | **0.5205(0.0100)** | **0.9569(0.0008)**     | **0.6497(0.0011)**    |\n\n4. We conducted an extensive analysis on the Amazon dataset to evaluate the sensitivity of HEM to the number of inner loop and outer loop steps. Our findings indicate that for the outer loop steps, the model demonstrates robust performance as long as the training steps are not excessively limited. Conversely, the model exhibits relatively higher sensitivity to the inner loop steps. Utilizing a smaller number of inner loop training steps allows for the generation of augmented graphs with an appropriate level of difficulty, thereby facilitating easier model convergence.\n\n| Inner Loop     | ('amazon', 'w/o DS') | ('amazon', 'w/ DS') |\n| :------------- | :------------------- | :------------------ |\n| 1 (By Default) | 0.9197(0.0074)       | **0.7491(0.0049)**  |\n| 3              | **0.9203(0.0007)**   | 0.7193(0.0023)      |\n| 5              | 0.9193(0.0023)       | 0.7182(0.0101)      |\n\n| Outer Loop       | ('amazon', 'w/o DS') | ('amazon', 'w/ DS') |\n| :--------------- | :------------------- | :------------------ |\n| 500 (By Default) | 0.9197(0.0074)       | **0.7491(0.0049)**  |\n| 300              | **0.9208(0.0002)**   | 0.7411(0.0011)      |\n| 100              | 0.9137(0.0001)       | 0.702(0.0003)       |"}, {"review_id": "6EtRiztkUo", "reviewer": "Reviewer_YbZZ", "summary": "This paper tackles how Graph Anomaly Detection (GAD) models fail when there are structural distribution shifts between training and test data. It points out that models often learn homophilic shortcuts from biased training data, which hurts their performance on test data with different structures.To fix this, the paper introduces a new framework called HEM (Ego-Neighborhood Disentangled Encoder with Homophile-aware Environment Mixup). HEM's main ideas are:an Ego-Neighborhood Disentangled Encoder that processes a node's own features separately from its neighborhood's structure. A Homophily-aware Environment Mixup module that cleverly re-weights graph edges to create diverse training examples. The whole system is trained adversarially, pushing the encoder to learn stable patterns while the mixup module creates tough, new graph structures. The experiments show that HEM works much better than other methods, especially when the graph structure shifts.", "questions": "1 Your mixup module aims to create \"diverse\" environments, but the objective function focuses on making \"hard\" examples for the classifier. How do you ensure this creates a true diversity of structures, rather than just pushing all augmented graphs to be low-homophily, for example?\n\n2 You used BWGNN as the neighborhood encoder. How much do your results depend on this specific choice? It would strengthen your claims if you showed that the HEM framework also improves the performance of other backbones like GCN or GAT.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "## pros\nSignificance: The paper tackles a really important and often overlooked problem in GAD—how to make models generalize when the graph structure changes. This is a big deal for real-world uses like finding fraudsters or bots, where the data is always biased.\n\nOriginality: The Homophily-aware Environment Mixup idea is quite innovative. Instead of making multiple copies of the graph, which eats up memory, it just adjusts edge weights. This is a much more efficient and fine-grained way to create the diverse data needed for robust training.\n\nQuality: The technical work is solid. The method makes sense, and the experiments are thorough. You compared HEM against a wide variety of relevant models and showed it consistently comes out on top, particularly in the most challenging scenarios. The ablation studies also clearly prove that each part of your framework is necessary.\n\nClarity: The paper is well-written and easy to understand. You do a great job explaining the problem and your solution. Figure 1 is especially helpful for getting a quick overview of the whole system.\n\n## cons\nNo Limitations Section: The paper would be stronger if it discussed its own limitations. For example, the model's performance seems to depend quite a bit on the ρ hyperparameter, and it'd be good to acknowledge the challenge of tuning this in practice.\n\nHomophily-aware Link: The connection between the name \"homophily-aware\" and the mechanism could be clearer. Your mixup module makes the training examples \"harder,\" but it's not fully explained how this ensures a diversity of homophily levels, rather than just always making homophily lower.\n\nFramework Generalizability: You use a strong, specific GNN (BWGNN) as the backbone. It would be great to see if the HEM framework provides the same benefits when used with other common GNNs like GCN or GAT. This would show that the framework itself is what's providing the boost.", "was_revised": true, "final_justification": "This paper is well-written and highly inspiring. The few concerns were satisfactorily addressed in the rebuttal. I believe it fully meets the required standards. Therefore, I give an \"Accept.\"", "rebuttal": "1. While our motivation stemmed from the need to mitigate the homophily distribution shift between high- and low-homophily data, our method does not directly minimize the homogeneous ratio of augmented data during training. Rather, our adversarial training framework is designed to create an environment with harder samples, which implicitly fosters improved model generalization.\n\n2. We change the neighborhood encoder from BWGNN to GCN, HEM also improves the performance.\n\n|            | ('amazon', 'w/o DS') | ('amazon', 'w/ DS') | ('yelp', 'w/o DS') | ('yelp', 'w/ DS')  | ('tfinance', 'w/o DS') | ('tfinance', 'w/ DS') |\n| :--------- | :------------------- | :------------------ | :----------------- | :----------------- | :--------------------- | :-------------------- |\n| GCN        | **0.9445(0.0097)**   | 0.6990(0.0213)      | 0.5363(0.0094)     | 0.4079(0.0173)     | 0.9366(0.0010)         | 0.6033(0.0041)        |\n| HEM (+GCN) | 0.9370(0.0011)       | **0.7059(0.0009)**  | **0.5509(0.0047)** | **0.5205(0.0100)** | **0.9569(0.0008)**     | **0.6497(0.0011)**    |"}, {"review_id": "jYVuEQ9M6Z", "reviewer": "Reviewer_r6WM", "summary": "This paper addresses the problem of graph anomaly detection (GAD) under structural distribution shifts, where models trained on data with high homophily perform poorly on test data with low homophily. The authors argue that existing methods learn \"homophilic shortcuts\" that fail to generalize. To tackle this, they propose HEM (Ego-Neighborhood Disentangled Encoder with Homophily-aware Environment Mixup). Experiments on three real-world datasets show that HEM outperforms a range of baselines, especially in the presence of distribution shift.", "questions": "1.  The homophily-aware environment mixup learns to re-weight edges to create more challenging training scenarios. How does the framework ensure that the generated edge weights lead to meaningful and realistic low-homophily structures, rather than simply learning a trivial adversarial perturbation that inverts embeddings but does not reflect real-world structural shifts?\n2.  The core problem is framed as generalizing from high-homophily training data to low-homophily test data. How would HEM be expected to perform in the reverse scenario (training on low-homophily data and testing on high)? Furthermore, how does it compare to methods designed specifically for static heterophilic graphs, where low homophily is the default and not the result of a distribution shift?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "pros:\n1. the paper provides a well-motivated approach to address this Structural distribution shifts.\n2. The proposed HEM framework is novel in its approach to this problem. The combination of a disentangled encoder to separate ego and neighborhood information with a learnable, homophily-aware data augmentation module is a clever and well-integrated solution. \n3. The experimental setup is thorough. The authors compare HEM against a comprehensive set of baselines, including general GNNs, specialized GAD methods, and both general and graph-specific out-of-distribution (OOD) methods. The results consistently demonstrate the superiority of HEM on test sets with distribution shifts, validating the effectiveness of the proposed approach.\n\ncons:\n1. While generally well-written, the overall framework is quite complex, involving multiple modules and loss functions. The adversarial training dynamic could be explained more intuitively. The term \"environment\" is used to describe the result of re-weighting edges on a single graph, which might be slightly confusing for readers familiar with OOD literature where environments are often distinct datasets.\n2. The paper claims to disentangle feature and structural representations. However, this is achieved structurally by using separate encoders. The paper lacks a quantitative analysis to prove that the representations are truly disentangled (e.g., showing that the neighborhood embedding is more sensitive to structural changes while the ego embedding remains stable). The benefit is only demonstrated through downstream performance.", "was_revised": true, "final_justification": "I maintain my review.", "rebuttal": "1. Our method directly confronts this issue by creating augmented environments with diverse homophily distributions. The key insight is that these augmented samples do not need to perfectly mirror realistic data. Their strategic purpose is to create challenging scenarios that **break the spurious connection** between the proportion of anomaly nodes in neighborhood and node labels in high-homophily data.\nBy forcing the model to perform well across generated environments—from high to low homophily—we compel it to learn features that are robust and invariant to the graph's homophily level. This process prevents the model from learning a trivial adversarial perturbation (e.g., simply inverting embeddings), as such a simplistic strategy would perform poorly on the original, un-augmented training environments. Ultimately, this approach produces a model that generalizes more effectively to test sets with unknown or different structural properties.\n\n2. Although our primary motivation was to address the homophily distribution shift observed when moving from high-homophily to low-homophily data, our method does not explicitly minimize the homogeneous ratio of augmented data during the training phase. Instead, our adversarial training framework aims to generate more challenging samples, thereby enhancing the model's generalization ability."}, {"review_id": "Fq6u11aAoe", "reviewer": "Reviewer_i6um", "summary": "The paper addresses the challenge of graph anomaly detection under structural distribution shifts due to selection bias. It proposes a novel method called HEM (Ego-Neighborhood Disentangled Encoder with Homophily-aware Environment Mixup) to discover invariant patterns and dynamically adjust edge weights to handle varying homophilic structures. The approach involves disentangling feature and structure embeddings, and performing adversarial training to improve generalization capabilities.", "questions": "1. How does the disentangled encoder theoretically ensure prediction stability by separating features and structures?\n2. Is there a unified mathematical representation of \"stability\" across distributions for invariant patterns, and how is it proven?\n3. Could you elaborate on the specific criteria or methods used to distinguish and partition the datasets into these two domains? \n4. The method seems to primarily address a unidirectional distribution shift. How does it ensure the model’s stability in scenarios where homophily either intensifies or remains nearly constant?", "limitations": "1. The baselines are outdated, as they do not include recent OOD detection methods (like energy-based models, uncertainty-aware models) or some recent anomaly detection frameworks. Notably, there have already been frameworks that decouple attribute and structure, such as GOOD-D proposed in WSDM23. \n2. As a typical binary classification problem, using only AUPRC as the metric is insufficient to convince readers.\n3. The paper does not elaborate on how General GNNs (e.g., GCN, GAT) are adapted for anomaly detection tasks.", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strength:\n1. Innovative decoupling framework.\n2. Dynamic & continuous environment augmentation for distribution shifts.\nWeakness:\n1. Outdated baselines, missing recent frameworks.\n2. Lacks mathematical proofs for invariant pattern stability.\n3. Overly complex descriptions.", "was_revised": true, "final_justification": "I appreciate the thoughtful rebuttal addressing most of my concerns. I decided to maintain my original score.", "rebuttal": "## Q1&Q2\n\n**Annotations**\n\nLet $h$ denote the homogeneous ratio and $Y$ be the node label, where $Y=1$ for anomalous nodes and $Y=0$ for normal nodes. The proportion of anomalous nodes is $\\pi$, such that $P(Y=1) = \\pi$.\n\nThe proportion of anomalous neighbors for a node $u$, denoted as $r_u$, is defined as:\n$$r_u = \\frac{1}{\\text{deg}(u)}\\sum_{(u,v)\\in E} Y_v$$\nWe assume a constant node degree $d$, $\\mu_1=\\mathbb E[X\\mid Y{=}1]$ and $\\mu_0=\\mathbb E[X\\mid Y{=}0]$, with the assumption that $\\Delta\\mu=\\mu_1-\\mu_0\\neq 0$.\n\n**Theorem 1:** Under a homophily distribution shift, the optimal parameter $w^\\star$ learned on a training set with homophily $h_{tr}$ is no longer optimal for a test set with a different homophily $h_{te}$.\n\nKey statistical properties:\n\n* $\\operatorname{Cov}(Y,r)=\\pi(1-\\pi)(2h-1)$\n* $\\operatorname{Var}(Y)=\\pi(1-\\pi)$\n* $\\operatorname{Var}(r\\mid Y{=}y)=\\frac{h(1-h)}{d}$\n* $\\operatorname{Var}(r)=\\frac{h(1-h)}{d}+\\pi(1-\\pi)(2h-1)^2$\n\nFor a one-layer message-passing GNN followed by a linear classifier, the node embedding $Z_v$ is:\n$Z_v=(AX)_v=r_v\\mu_1+(1-r_v)\\mu_0=\\mu_0+r_v\\Delta\\mu$\n\nThe final prediction $\\hat{Y}_v$ is then: $\\hat{Y}_v$\n\n$=w^\\top\\mu_0+\\underbrace{(w^\\top\\Delta\\mu)}_{\\alpha}\\,r_v$\n\nThe optimal coefficient $\\alpha^{\\star}$ that minimizes the Mean Squared Error (MSE) is given by linear regression:$$\\alpha^{\\star}=\\frac{\\operatorname{Cov}(Y,r)}{\\operatorname{Var}(r)} =\\frac{\\pi(1-\\pi)(2h-1)}{\\frac{h(1-h)}{d}+\\pi(1-\\pi)(2h-1)^2}$$\nSince $\\alpha^{\\star}$ is a function of the homophily ratio $h$, the optimal weight vector $w^\\star$ also depends on $h$. Consequently, a parameter $w^\\star$ learned with $h_{tr}$ will be suboptimal for a test distribution with $h_{te} \\neq h_{tr}$, causing model **instability**.\n\n**Theorem 2**: If there exists an $\\epsilon$ such that $|h_{te}-h_{tr}|\\leq \\epsilon$, then the difference between the empirical loss and the optimal loss on the test set is bounded. Specifically, $L(h_{te};\\alpha) - L^\\star(h_{te}) \\leq V_{max}L_f\\epsilon^2$, where $L_f$ is the Lipschitz constant of $f$.\n\nDefine\n$C(h)=\\operatorname{Cov}(Y,r)=\\pi(1-\\pi)\\,(2h-1)$\n$V(h)=\\operatorname{Var}(r)=\\frac{h(1-h)}{d}+\\pi(1-\\pi)(2h-1)^2$\n\nThe MSE loss is\n$L(h;\\alpha)=E[(Y-\\hat{Y})^2|h]=V(h)-2\\alpha C(h)+\\alpha^2 V(h)$\n\nThe optimal $\\alpha$ for a given $h$ is defined as $\\alpha^{\\star}=f(h)=\\frac{C(h)}{V(h)}$, with corresponding optimal loss $L^\\star=V(h)-\\frac{C(h)^2}{V(h)} $.\n\nWe assume that HEM trains on the interval ${H}_\\epsilon =$ \n\n$[h_{tr}-\\epsilon, h_{tr}+\\epsilon]$, \n\nwhich encompasses $h_{te}$.\n\nDefine \n\n* $f_{min}=\\inf_{h\\in \\mathcal{H}_\\epsilon} f(h)$\n* $f_{max}=\\sup_{h\\in \\mathcal{H}_\\epsilon} f(h)$\n* $V_{max}=\\sup_{h\\in \\mathcal{H}_\\epsilon} V(h)$\n\n\n$L(h;\\alpha)=L^\\star(h) + V(h)(\\alpha-f(h))^2$\n\nTherefore, we can establish an upper bound for the empirical loss exceeding the optimal loss:\n\n$L(h;\\alpha) - L^\\star(h) \\leq \\sup_{h\\in \\mathcal{H}_\\epsilon} V(h)(\\alpha-f(h))^2$\n\n$\\leq V_{max}(\\sup_{h\\in \\mathcal{H}_\\epsilon}(\\alpha-f(h))^2)$\n\nSince the objective of the adversarial training process in HEM is to minimize the loss in the worst case, we further assume HEM minimizes this upper bound. This implies that $\\alpha$ is chosen as the midpoint of the range of $f(h)$:\n\n$\\alpha=\\frac{f_{min}+f_{max}}{2}$\n\n$L(h;\\alpha) - L^\\star(h) \\leq V_{max}(\\sup_{h\\in \\mathcal{H}_\\epsilon} (\\frac{fmax- fmin}{2})^2) )$\n\nIf $f$ adheres to Lipschitz continuity, \n\n$f_{max}-f_{min}\\leq L_f((h_{tr}+\\epsilon)-(h_{tr}-\\epsilon))=2L_f\\epsilon$\n\nFinally, \n$L(h;\\alpha) - L^\\star(h) \\leq V_{max}\\left(\\frac{2L_f\\epsilon}{2}\\right)^2 = V_{max}(L_f\\epsilon)^2 = V_{max}L_f^2\\epsilon^2$\n\nTheorem 2 shows that HEM ensures stability through adversarial training on disentangled embeddings, resulting in a bounded test loss, unlike traditional methods, which lack this condition and thus may suffer unbounded loss.\n\n## Q3\n\nThe dataset is divided by the *homogeneous ratio* of nodes,  split into 50%/10%/20%/20% for training, validation, in-distribution test, and out-of-distribution (OOD) test sets, respectively. The bottom 20% of nodes with the lowest homogeneous ratios are selected to form the OOD test set. \n\n## Q4\n\nTo ensure that the model remains stable under minimal distributional shift, we report its performance on the test sets without/with distribution shift (w/o DS and w/ DS). As shown, our model achieves state-of-the-art or near-SOTA performance even on the w/o DS test set.\n\n## L1\n(1) We add a new baseline [ICML 2024] BAT [1], an uncertainty-aware framework. \n- |      | ('amazon', 'w/o DS') | ('amazon', 'w/ DS') | ('yelp', 'w/o DS') | ('yelp', 'w/ DS')  | ('tfinance', 'w/o DS') | ('tfinance', 'w/ DS') |\n| :--- | :------------------- | :------------------ | :----------------- | :----------------- | :--------------------- | :-------------------- |\n| BAT  | **0.9403(0.0204)**   | 0.7226(0.0116)      | **0.6219(0.0261)** | 0.5493(0.0049)     | 0.9277(0.0067)         | 0.5635(0.0175)        |\n| HEM  | 0.9197(0.0074)       | **0.7491(0.0049)**  | 0.6142(0.0056)     | **0.5845(0.0101)** | **0.9476(0.0060)**     | **0.6604(0.0029)**    |\n\n(2) Key Differences between HEM and GOOD-D:\n1. Problem Setting:\n\n- **GOOD-D** focuses on **unsupervised graph-level out-of-distribution (OOD) detection**, where the goal is to distinguish whether an entire graph is from the in-distribution or OOD.\n- **HEM** is designed for **node-level graph anomaly detection** under **structural distribution shift**, specifically addressing the performance degradation caused by varying levels of homophily between training and test data.\n\n2. Disentanglement Strategy:\n\n- In **GOOD-D**, disentanglement is implemented through a **perturbation-free augmentation** strategy that generates a structure view using pre-computed structural encodings, contrasting it with a feature view.\n- In **HEM**, we propose an **ego-neighborhood disentangled encoder** that **explicitly separates the modeling of node features and neighborhood structures through MLP and GNN sharing the same encoder**, allowing more targeted learning of invariant patterns for node-level prediction.\n\n3. **Optimization Objectives and Mechanisms:**\n\n- **GOOD-D** uses a **hierarchical contrastive learning framework** to capture ID patterns and define OOD scores based on multi-level inconsistencies.\n- **HEM** introduces a **homophily-aware environment mixup** that **dynamically adjusts edge weights** to create structurally diverse environments, and optimizes the encoder in an **adversarial training** setup to improve robustness across distribution shifts.\n\n## L2 \nTo address this concern, we have supplemented our evaluation with Rec@K metric. Since GAD is a highly imbalanced classification problem, we believe AUPRC and Rec@K are more informative than AUROC and ACC.\n\n- **Rec@K (Recall at K)** measures the recall among the top-K highest-confidence predictions, where K equals the number of actual anomalies in the test set.\n\n|           | ('amazon', 'w/o DS') | ('amazon', 'w/ DS') | ('yelp', 'w/o DS') | ('yelp', 'w/ DS')  | ('tfinance', 'w/o DS') | ('tfinance', 'w/ DS') |\n| :-------- | :------------------- | :------------------ | :----------------- | :----------------- | :--------------------- | :-------------------- |\n| GCN       | 0.9018(0.0101)       | 0.6537(0.0069)      | 0.5195(0.0024)     | 0.4404(0.0027)     | 0.8957(0.0022)         | 0.575(0.0089)         |\n| GAT       | **0.9022(0.0218)**   | 0.6699(0.0083)      | 0.5642(0.0)        | 0.4811(0.0)        | 0.8259(0.0)            | 0.5188(0.0)           |\n| GraphSAGE | 0.8818(0.0064)       | 0.652(0.0061)       | **0.5892(0.0023)** | 0.5101(0.0049)     | 0.8867(0.0169)         | 0.5329(0.0258)        |\n| BernNet   | 0.8974(0.0165)       | 0.6553(0.0184)      | 0.5233(0.0021)     | 0.4789(0.0025)     | 0.8659(0.0077)         | 0.6231(0.0018)        |\n| PCGNN     | 0.8955(0.0064)       | 0.6667(0.0046)      | 0.5089(0.0012)     | 0.4314(0.0008)     | 0.8008(0.0144)         | 0.5336(0.0069)        |\n| GHRN      | 0.8955(0.0)          | 0.6293(0.0)         | 0.5496(0.0054)     | 0.5113(0.0057)     | 0.8753(0.0069)         | 0.6016(0.0028)        |\n| BWGNN     | 0.9(0.0)             | 0.639(0.0)          | 0.5498(0.0083)     | 0.5033(0.0037)     | 0.8776(0.0084)         | 0.6075(0.0072)        |\n| V-REx     | 0.8924(0.0021)       | 0.6276(0.0092)      | 0.5494(0.0025)     | 0.5137(0.0054)     | 0.8682(0.0019)         | 0.5972(0.0028)        |\n| GroupDRO  | 0.8955(0.0)          | 0.6163(0.0061)      | 0.5563(0.0054)     | 0.5109(0.004)      | 0.8863(0.0029)         | 0.6053(0.0031)        |\n| SRGNN     | 0.9(0.0037)          | 0.6341(0.004)       | 0.5431(0.0058)     | 0.5079(0.0059)     | 0.8792(0.0073)         | 0.592(0.011)          |\n| GDN       | 0.8939(0.0021)       | 0.6488(0.0105)      | 0.4934(0.0166)     | 0.4821(0.0164)     | 0.8573(0.0022)         | 0.5802(0.0091)        |\n| BAT       | 0.9018(0.0121)       | 0.6699(0.0083)      | 0.568(0.0264)      | 0.5137(0.0214)     | 0.8883(0.0154)         | 0.5654(0.0072)        |\n| HEM       | 0.9015(0.0021)       | **0.678(0.008)**    | 0.561(0.0068)      | **0.5263(0.0028)** | **0.9043(0.0022)**     | **0.6312(0.001)**     |\n\n## L3\n\nAlthough anomaly detection involves significant class imbalance, it can still be formulated as a classification task. Therefore, general GNNs like GCN and GAT can be directly applied.\nUnlike prior works that adopt naive implementations of these GNNs as weak baselines, we follow the insights from [2] by incorporating residual connections and Layer Normalization. These enhancements significantly improve the performance of classic GNNs in GAD tasks.\n\n[1] Liu Z, Qiu R, Zeng Z, et al. Class-imbalanced graph learning without class rebalancing[J]. arXiv preprint arXiv:2308.14181, 2023.\n\n[2] Luo Y, Shi L, Wu X M. Classic gnns are strong baselines: Reassessing gnns for node classification[J]. Advances in Neural Information Processing Systems, 2024, 37: 97650-97669."}]

Author rebuttal:

Meta-review: Summary of Reviews:

The paper introduces HEM (Ego-Neighborhood Disentangled Encoder with Homophily-aware Environment Mixup), a framework for tackling graph anomaly detection (GAD) under structural distribution shifts caused by selection bias. It addresses a critical problem in real-world GAD applications, such as fraud detection and bot identification. By disentangling node features from structural information and employing a homophily-aware mixup module to generate robust training environments, HEM improves generalization to out-of-distribution graphs. Experiments demonstrate its superiority over various baselines.

Strengths:
-- Novelty: Combines disentangled encoders with an adversarial mixup module, offering an efficient and innovative solution.
-- Comprehensive Evaluation: Outperforms 13 baselines across multiple datasets with strong ablation studies validating its components.
-- Efficiency: The mixup mechanism dynamically re-weights edges instead of creating multiple graph copies, saving memory.
-- Clarity: Well-written and structured, with clear problem formulation and solution explanation.

Weaknesses raised in concerns of reviewers:
-- Lack of Qualitative Analysis: No visualization or deeper analysis of the "invariant patterns" learned by the disentangled embeddings.
-- Complexity: The framework involves multiple modules and loss functions, which could be more intuitively explained.
-- Generalizability: The method relies on a specific GNN (BWGNN); its benefits with other GNNs (e.g., GCN, GAT) are not tested and explained.
-- Outdated Baselines: Some recent GAD and OOD detection frameworks are missing in comparisons (e.g., energy-based models).
-- Dependence on Hyperparameters: The performance depends heavily on the tuning of certain parameters (e.g., ρ).

Conclusion:
HEM presents an innovative and effective approach to GAD under structural distribution shifts, with strong experimental results and practical design. Concerns from reviewers include broader baseline comparisons, qualitative insights, and validation of its generalizability across different GNN architectures. After the rebuttal period, such concerns are well addressed and reviewers are mostly satisfied. Therefore, publication is recommended had the authors include all the discussions and revisions in the final version.
Decision: Accept (poster)