Out-of-Distribution Generalized Graph Anomaly Detection with Homophily-aware Environment Mixup

Q1&Q2

Annotations

Let $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$.

The proportion of anomalous neighbors for a node $u$, denoted as $r_u$, is defined as: $r_u = \frac{1}{\text{deg}(u)}\sum_{(u,v)\in E} Y_v$ We 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$.

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}$.

Key statistical properties:

• $\operatorname{Cov}(Y,r)=\pi(1-\pi)(2h-1)$
• $\operatorname{Var}(Y)=\pi(1-\pi)$
• $\operatorname{Var}(r\mid Y{=}y)=\frac{h(1-h)}{d}$
• $\operatorname{Var}(r)=\frac{h(1-h)}{d}+\pi(1-\pi)(2h-1)^2$

For a one-layer message-passing GNN followed by a linear classifier, the node embedding $Z_v$ is: $Z_v=(AX)_v=r_v\mu_1+(1-r_v)\mu_0=\mu_0+r_v\Delta\mu$

The final prediction $\hat{Y}_v$ is then: $\hat{Y}_v$

$=w^\top\mu_0+\underbrace{(w^\top\Delta\mu)}_{\alpha}\,r_v$

The 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}$ Since $\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.

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$.

Define $C(h)=\operatorname{Cov}(Y,r)=\pi(1-\pi)\,(2h-1)$ $V(h)=\operatorname{Var}(r)=\frac{h(1-h)}{d}+\pi(1-\pi)(2h-1)^2$

The MSE loss is $L(h;\alpha)=E[(Y-\hat{Y})^2|h]=V(h)-2\alpha C(h)+\alpha^2 V(h)$

The 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)}$.

We assume that HEM trains on the interval ${H}_\epsilon =$

$[h_{tr}-\epsilon, h_{tr}+\epsilon]$,

which encompasses $h_{te}$.

Define

• $f_{min}=\inf_{h\in \mathcal{H}_\epsilon} f(h)$
• $f_{max}=\sup_{h\in \mathcal{H}_\epsilon} f(h)$
• $V_{max}=\sup_{h\in \mathcal{H}_\epsilon} V(h)$

$L(h;\alpha)=L^\star(h) + V(h)(\alpha-f(h))^2$

Therefore, we can establish an upper bound for the empirical loss exceeding the optimal loss:

$L(h;\alpha) - L^\star(h) \leq \sup_{h\in \mathcal{H}_\epsilon} V(h)(\alpha-f(h))^2$

$\leq V_{max}(\sup_{h\in \mathcal{H}_\epsilon}(\alpha-f(h))^2)$

Since 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)$:

$\alpha=\frac{f_{min}+f_{max}}{2}$

$L(h;\alpha) - L^\star(h) \leq V_{max}(\sup_{h\in \mathcal{H}_\epsilon} (\frac{fmax- fmin}{2})^2) )$

If $f$ adheres to Lipschitz continuity,

$f_{max}-f_{min}\leq L_f((h_{tr}+\epsilon)-(h_{tr}-\epsilon))=2L_f\epsilon$

Finally, $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$

Theorem 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.

Q3

The 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.

Q4

To 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.

L1

(1) We add a new baseline [ICML 2024] BAT [1], an uncertainty-aware framework.

• | | ('amazon', 'w/o DS') | ('amazon', 'w/ DS') | ('yelp', 'w/o DS') | ('yelp', 'w/ DS') | ('tfinance', 'w/o DS') | ('tfinance', 'w/ DS') | | :--- | :------------------- | :------------------ | :----------------- | :----------------- | :--------------------- | :-------------------- | | 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) | | 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) |

(2) Key Differences between HEM and GOOD-D:

1. Problem Setting:

• 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.
• 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.

2. Disentanglement Strategy:

• 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.
• 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.

3. Optimization Objectives and Mechanisms:

• GOOD-D uses a hierarchical contrastive learning framework to capture ID patterns and define OOD scores based on multi-level inconsistencies.
• 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.

L2

To 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.

• 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.

L3

Although 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. Unlike 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.

[1] Liu Z, Qiu R, Zeng Z, et al. Class-imbalanced graph learning without class rebalancing[J]. arXiv preprint arXiv:2308.14181, 2023.

[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.

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. By 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.

2. 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.

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.

2. We change the neighborhood encoder from BWGNN to GCN, HEM also improves the performance.

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.

2. | Model | Peak GPU Memory Usage | Training Time | | ----- | --------------------- | ------------- | | EERM | 21.05 GB | 489.19 s | | HEM | 0.92 GB | 45.67 s |

3. We change the neighborhood encoder from BWGNN to GCN, HEM also improves the performance.

4. 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.