Redundancy-Aware Test-Time Graph Out-of-Distribution Detection
Authors: Yue Hou
He Zhu
Ruomei Liu
Yingke Su
Junran Wu
Ke Xu
Venue: NeurIPS 2025 poster ()
Keywords: out-of-distribution detection
structural entropy
Primary area: general_machine_learning

Abstract: Distributional discrepancy between training and test data can lead models to make inaccurate predictions when encountering out-of-distribution (OOD) samples in real-world applications. Although existing graph OOD detection methods leverage data-centric techniques to extract effective representations, their performance remains compromised by structural redundancy that induces semantic shifts. To address this dilemma, we propose RedOUT, an unsupervised framework that integrates structural entropy into test-time OOD detection for graph classification. Concretely, we introduce the Redundancy-aware Graph Information Bottleneck (ReGIB) and decompose the objective into essential information and irrelevant redundancy. By minimizing structural entropy, the decoupled redundancy is reduced, and theoretically grounded upper and lower bounds are proposed for optimization. Extensive experiments on real-world datasets demonstrate the superior performance of RedOUT on OOD detection. Specifically, our method achieves an average improvement of 6.7\%, significantly surpassing the best competitor by 17.3\% on the ClinTox/LIPO dataset pair.

Redundancy-Aware Test-Time Graph Out-of-Distribution Detection
Yue Hou He Zhu', Ruomei Liu', Yingke Su², Junran :u': Ke Xu',
State Key Laboratory of Complex & Critical Software Environment, Beihang University Shen Yuan Honors College, Beihang University (hou_yue, roy_zh, rmliu, suyingke, wu_junran, kexu) edu.
Abstract
Distributional discrepancy between training and test data lead models to make inaccurate predictions when encountering out-of-distributie (OOD) samples in real-world applications. Although existing graph OOD detection methods lever- age data-centric techniques to extract effective representations, their performance remains compromised by structural redundancy that induces semantic shifts. To address this dilemma, we propose RedOUT, an unsupervised framework that in- tegrates structural entropy into test-time OOD detection for graph classification. Concretely, we introduce the Redundancy-ave (ReGIB) and decompose the objective into essential information and irrelevant re- dundancy. By minimizing structural entropy, the decoupled redundancy is reduced, and theoretically grounded upper and lower bounds are proposed for optimization. Extensive experiments real-world datasets demonstrate the superior performance RedOUT on OOD detection. Specifically, our method achieves an average im- provement of 6.7%, significantly surpassing the best competitor by 17.3% the ClinTox/LIPO dataset pair.
Graph Information Bottleneck
Introduction
Deep learning models have achieved impressive success across wide range tasks, yet they can behave unpredictably when faced with out-of distribbbit (OOD) data that differ significantly from the training distribution, making high-confidence but incorrect predictions. OOD detection [3] (7)
seeks to identify such inputs and is critical for reliable deployment in open-world scenarios. This challenge becomes even more pronounced for graph-structured data due the oon-uuclidean nature and complex topological structures.
39 in graph OOD detection can be broadly divided into main categories, (1) End-to-end methods [20] aim to train OOD-specific graph neural networks
Recent advancements
20
(GNNs) 13 46 from scratch using only unlabeled ID data. These approaches typically lever-
age unsupervised objectives such as graph contrastive learning (GCL) to extract discriminative representations that can separate ID and OOD samples during inference (L> Figure
[ i)). (2)
Post-hoc methods [9] (39 employ rell-trained GNNs and fine-tune OOD detectors to refine the predictions or representations at inference time (D> Figure [i)). Specifically, GOODAT [39
stands out by directly optimizing learnable graph masker on test samples without altering the pre-trained model. This test-time setting with data-centric modification more practical for removing the dependency on labeled training data or model retraining.
Despite significant advancements the aforementioned data-centric paradigm, a less-explored challenge persists. While pre-trained models can effectively extract information from ID data, they
"Corresponding author
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

End-to-end methed training from scratch
Test graphs batches
OOD-speciiic
OOD Prediction
Training Graphs
GNN models
distinctive patterns
(ii) Post-hoc methods with data-centric modification
Learnable
(b) Distinctive patterns
Graph Masker
Well-trained GNN models
OOD Prediction
Before inimization
Test Graphs
Deasiry
0.25
OOD
(iii) Our method with SE minimization test-time
0.00
10
20
ReGiB
Allez minimization
(Coding Tree)
Well-trained GNN models
OOD
Denagy
0.25
ID
Test Graphs
Prediction
0.00
OOD
20
OOD
(a) Comparison between RedOUT and other methods
(c) Density distributions
Figure I: (a) A schema comparison. (b) A toy example of distinctive components within test graphs
(c) Scoring distributions before/after structural entropy (abbr. SE) minimization.
lack ground-truth information indicative of the underlying distribution when inferring on both ID and OOD test data, which is often embedded within the graph structure. As illustrated in the toy example in Figure [[b)] graphs in test batches comprise distinctive components (highlighted by dashed circles) and irrelevant structural elements. Effectively capturing these distinctive components can intuitively differentiate OOD samples from ID graphs. However, the pervasive presence of similar irrelevant structural elements hinders current methods from accurately capturing and distinguishing these essential structures between ID and OOD data. Although GOODAT [3] tries to address this concern by utilizing graph maskers to identify subgraphs in test data that are similar to those in ID graphs from training datasets, it fundamentally relies on learnable graph augmentations. These augmentations inadvertently alter the semantic information of substructures or lead to information loss, thereby compromising the reliability of OOD detection.
To capture the distinctive information while preserving structural semantics, we first decompose the information within graph into essentiality and redundancy, leveraged by the graph information bottleneck [45] Structural entropy, which provides hierarchical abstraction to measure structural complexity 15). further inspires us to utilize the technology to eliminate decoupled redundant information. We compute the scoring distributions of graph representations before and after structural entropy minimization on the AIDS/DHER dataset pair (with AIDS as ID dataset and DHFR as OOD dataset), shown in Figure [(c) From score density plots, observe that after structural entropy minimization, OOD scores exhibit smaller variance and a decrease in the overlap between OOD and ID samples. This intuitively demonstrates that by removing redundancy, the more distinctive parts of graphs are retained, enabling more effective differentiation of the distributions.
In this paper, we propose an innovative redundancy aware test-time graph OOD detection framework, termed RedOUT, aiming at endowing well-trained models with the ability to extract the essential structural information from test graphs effectively. Concretely, we introduce the Redundancy-and Graph Information Bottleneck (ReGIB) and decompose the objective into distinctive essential view and irrelevant redundancy. By minimizing structural entropy, coding tree is constructed to instantiate the essential view, effectively removing redundancy. To make the overall objectives tractable, we establish upper and lower bounds for optimizing essential and redundant information. A comparison between RedOUT and existing methods is illustrated in Figure ((a) It is important to note that structural entropy minimization serves preprocessing step, utilizing approximation algorithm that does not require additional learning. Leveraging hierarchical representation learning based on the coding tree, we calibrate OOD scores to get better predictions without modifying the parameters of pre-trained models. Extensive experiments on real-world datasets demonstrate the superiority of RedOUT against sfate-of-the-art (SOTA) baselines. The contributions of this work are follows:
We propose novel framework for test-time unsupervised graph OOD detection, termed RedOUT. To the best of our knowledge, this is the first trial to endow trained models with the ability to capture the essential structural information of graphs during test-time.

---

We introduce the ReGIB to decouple the essential and redundant information within graphs, where coding tree with minimized structural entropy instantiated as essential view. We further introduce the upper and lower bounds for optimizing the ReGIB objectives. Extensive experiments validate the effectiveness of RedOUT, demonstrating the superior perfor- mance over SOTA baselines in unsupervised OOD detection.
2 Notations and Preliminaries
Before formulating the research problem, we first provide some necessary notations. Let G = (V,E, X) represent graph, where V is the set of nodes and & is the set of edges. The node features are represented by the feature matrix X E guxd,, where = [V] is the number of nodes and dj the feature dimension. The structure information can also be described by an adjacency matrix A E IR"*", so graph can be alternatively represented by G = (A, X). Notation with its description can be found in Appendix A
Unsupervised Pre-training with Contrastive Loss. In the general graph contrastive learning paradigm for graph classification, two augmented graphs are generated using different graph aug- mentation operators. Subsequently, representations are generated using GNN encoder, and further mapped into an embedding space by shared projection head for contrastive learning. A typical graph contrastive loss, InfoNCE [S] 53], treats the same graph G; in different views G. and G as positive pairs and other nodes as negative pairs. The graph contrastive learning loss Loi can be formulated as:
eoim(Z; (Z; 1/T/r
Lei(G GO) = N 1=1
Σ log
(1)
6 cmm(2 22)//"
Lj=1.j41
where z and Z are graph-level representations on G and C. . denotes the batch size, is the temperature coefficient, and sim(--- stands for cosine similarity function.
In this study, inspired by GOOD- D22D- 20]. we employ 5 layers of GIN [46] as the backbone and adopt a perturbation free augmentation strategy to construct view G = (A, P). where P is formed
by concatenating P. (m])) Ip, 1p. Specifically, the random walk diffusion encoding P, (rw)
[RW.., RW? RWT, E R", where RW AD- is the random walk transition matrix, and D is AAD=
the diagonal degree matrix. The Laplacian positional encoding p; (lp) = - AD- 716- With the original graph G as the basic view, loss (ci(G, GT) is computed to optimize the pre-traine pre-trained model.
Test-time Graph-level OOD Detection. Following GOODAT 39
we consider an unlabeled ID) dataset Did = {Gid), JN where graphs are sampled from distribution pid and an OOD dataset Dood {Goodd } n' sampled from different distribution doood Given a graph G' from Did U Dood test-time graph OOD detection aims to detect whether G originates from pid or pood utilizing a GNN Did pre-trained on ID graphs Dirain C Did Specifically, the objective is to learn OOD detector D(...) that assigns an OOD detection score = D(S.G) with a higher indicating greater probability that G is from ioood (note that Did n Dirain = 0. Did C DDid, and Dood C Dood).
Structural Entropy. Structural entropy is initially proposed [15] to measure the uncertainty of graph structure, revealing the essential structure of graph. The structural entropy of given graph G = (V, 8, X} on its coding tree T is defined as:
(C) - Σ Jo- log vol(u;) V+ET vol (ot()))
where u, is node in T except for root node and also stands for a subset V, E V, ge. is the number of edges connecting nodes in and outside Vr, of is the immediate predecessor of v, and vol(u,), (ol() and vV) are the sum of degrees of nodes in er, ot and V, respectively.
3 Methodology
This section elaborates on RedOUT with its framework shown in Figure 2 We first derive the Redundancy-awand Graph Information Bottleneck (ReGIB) (D> Sec. [3I] by decomposing the objective into essential information and irrelevant redundancy, and introduce their upper and lower bounds. Additionally, we construct coding tree with minimized structural entropy as the essential view and instantiate the ReGIB with tractable bounds for efficient optimization (D> Sec. 3.2
3

---

Label
(a) ReGIR: (UCC))(C) K(C")CCP)) (C:
Diagram of G. G
(frozen)
Decocupose
max (((("):f(G)
min (G", G
NO
Essentallty
trannd GNN
Embesking
Redundancy
min (G)
Test Graphs
Constructing Coding Tree with Essential Information
Tree Embedding
GerlC:
MERGE
DROP
GearlG G')
leaves)
Coding
Objoccivoss
Constructing Coding
argrmin 20 (G)
(c) Aggreyating Based Coding Tree
Figure 2: Overview of the overall framework of RedOUT and proposed ReGIB. (a) the ReGIB principle and its bounds. (b) obtained by minimizing structural entropy of graph G, coding tree T serves as an instantiation of the essential view. (c) message passing and aggregating on graph are under the guidance of the coding tree.
3.1 The Principle of ReGIB
retaining optimal representation on a graph view should involve maximizing mutual information (MI) between the output and ground- truth labels (i.e., max (G); Y)) while reducing mutual information between input and output (i.e. min [(;; f(G)). This can be expressed as follows:
According to the graph information bottleneck (GIB) principle 45
min GIB - -I((G)) + BI(G; f(G)),
(3)
where 3 the Lagrangian parameter to balance the two terms, Y is the ground-trun truth labels, and ((::)) denotes the mutual information between inputs.
As mentioned, ID and OOD graphs can be distin- guished based distinctive structures. In this section, we introduce G with essential informa- tion of the original graph G' in test-time setting the first time, extending the GIB principle.
Optimal
Redundant
Fssential
Y
Compared to vanilla GIB, the proposed ReGIB accounts for the fact that the model pre-trained solely on ID graphs, struggles to generalize to unseen distribution, leading the representa- tions containing not only the optimal compo- nents but also irrelevant redundancy (D> Fig- ure bb). Moreover, for unsupervised tasks, the predicted label Y is used as a surrogate for the unknown label distribution, enabling training without access to ground-truth labels Y. Thus, by substituting G and Y into Eq. 3 we have:
(b) ReGIB Figure 3: Comparison between the basic GIB and proposed ReGIB. Note ReGIB balances signals D. 2 with optimal f(G*) to capture the essential information and discard redundancy.
(a) Vanilla GIB
min II(((")); BI(G";
Besides, due to semantic shifts in representations during test-time, the dual information sources (f")) and Y) may contain redundany. Therefore, it is crucial to further decouple the dependence among f(G*), f(G), and Y.
Proposition 1 (Lower Bound of ())
T(((T):;)) T(J(G")) -UCC))::1C0----UXX)))))))-------
(5)
I(((G)):(()) I(((")):
Eq. and
15
Eq. and 16
Proofs for Proposition
D is provided in Appendix
Definition 3.1 (Redundancy-awarr Graph Information Bottleneck). Given test graph G, and the pseudo-label Y predicted by pre-trained f. ReGIB aims to capture the distinctive structure G with essential information and further learn the optimal representation f(G") that satisfies: min ReGIB -I(((G)): (G)) + ([) BT(G" ((G)))
(6)

---

Remark. Intuitively, the first term f[f(");;((G) is the prediction term, which encourages that essential information to the graph property is preserved. The last two terms [(f(G)); ()) and f(*)) are used for compression, which encourage that irrelevant redundant information is dropped. Since the well-trained model f tends to make accurate predictions ID graphs, its predictions for OOD graphs, which are unseen during training, are more random. The model struggles to identify distinctive structural information and similar redundant structures. However, with the distinctive patterns of G ReGIB can provide ground-truth information to calibrate the model's s predictions test graphs. A further comparison of ReGIB and GIB argumentation view is conducted in Appendix C.9
The key to our objective is how to obtain the distinctive structure G and how to acquire the most optimal and essential information based on pseudo-labels while eliminating irrelevant redundancy in representations. Thus, we introduce the lower and upper bounds for Eq. 6
Proposition 2 (Lower Bound (:FG))
I(((G);f(G)) 2 -CciGG (G) + log(N). Proposition (Upper Bound of I(f(G*); f(G)) For any Q(f(G)) the variational upper bound of conditional mutual information T(f(G"): (GG))) is:
PUGGI PUGIMICNN
(((()
< Er log
(8)
Proofs for Proposition 2 and are provided in Appendix
C33 C.4
Essential Information. The key effectively distinguishing between ID and OOD graphs lies in maximizing the elimination of redundancy while preserving essential information. Suppose the optimal view G* can capture the essential information while eliminating redundancy of graph G. Here, we first provide the definition of essential view as follows.
Redundancy-climinn
Definition 3.2. The essential view with cedundancy--lliminae information is supposed be distinctive substructure of the given graph.
Based on the above analysis, the celtundancy-elmminnan view should retain the minimal amount of information while capturing the most distinctive structural patterns. The mutual information between G and G* can be formulated as:
IG G) = H(G") - H(G")G),
(9)
where H(G*) is the entropy of G and H(G G)) is the conditional entropy of G* conditioned on G. Theorem 3.3. The information in G is a subset of information in (i.c., H(G") S H(G)); thus, we have:
H(G (G) = O.
(10)
The detailed proof of Theorem 3.3 is shown in Appendix C.5
Here, the mutual information between
G and G can be rewritten as:
T(G"; H(G)).
(11)
Proposition (Upper Bound of I(G f(G))) ))), Given the tuple (G, G", f(G))) the learning proce-
dure follows the Markov Chain G - G* f(G") >. Accordingly, acquire the essential view with essential information, we need to optimize:
min
< min I(G min H(G").
(12)
To eliminate redundancy, we introduce structural entropy measure of the information content within the hicrarchy of the graph. Thus, we argue that the view obtained by minimizing structural entropy of given graph represents the redundancy-eliminatee information, serving essential view that retains the graph's 's distinctive substructure.
To extract optimal and essential representations on G*, we aim to maximize (ff(""; and minimize (G" ()) to obtain the optimal encoder, such that:
((G)))
f arg max I (f(G"); - ((("")
(13)
f
We also analytically provide theoretical guarantee for redundant and essential information follows.
5

---

Theorem 3,4. According to Proposition 2 optimizing loss LCi(G", G) is equivalent to maximizing the mutual information (f((")); f(G)) which could lead the maximization of ((( Y).
Remark. Theorem 3.4 (See proof in Appendix (C66 reveals that our essential view enables the encoder to preserve more information associated with the ground-trun -outh labels, which will boost the performance of downstream tasks.
Theorem 3.5 (Bounds of Redundant and Essential Information). Suppose the encoder f is imple- mented by a GNN as powerful as the 1-WL test. Suppose 9 is countable space and thus g' is a countable space, where = denotes equivalence (G1 _ G2 if G1. G2 cannot be distinguished by the 1-WL test). Define Pe'xy(G',, (o","""" Y") = Pgxy(G G) and ('(G") = EGAra (T (G) G'] for G" g. Then, the optimal f and G" to RedOUT satisfies:
T(G"; Y) (("())))((())))))))))))))))))")) (( miny (U) -((()));) where t" (G) = G*, "" (C")~~"""" (G,Y) ~ Pgxy and (G', Y) ~ Pgxxy-
Therefore, the encoder optimized by ReGIB enables encoding a representation that has limited redundant information and more essential information (See proof in Appendix C.7
3.2 ReGIB Principle Instantiation
To optimize ReGIB, we begin by constructing coding tree to instantiate essential information, and then specify the lower and upper bounds defined in Proposition 2 and
Coding Tree Construction (Instantiation for G*). For any given test graph, we construct an essential view of the graph with minimal structural entropy, defined by Eq. [2). Specifically, according to structural information theory [15. the structural entropy of a graph needs to be calcu- lated with the coding tree. Besides the optimal coding tree with minimum structural entropy (i.e., miner (H² (G))), a fixed-height coding tree is often preferred for its better representing the fixed natural hierarchy commonly found in real-world networks. Therefore, the k-dimensional structural entropy of G is defined on coding tree with fixed height k:
H H(0((G)
min HeTHeiggh(T)==k (H
(14)
The total process of generation of a coding tree with fixed height & can be divided into two steps: I) construction of the full-height binary coding tree, and 2) compression of the binary coding tree to height k. Given root node o, of the coding tree T', all original nodes in graph G (V, E) are treated
as leaf nodes. Correspondingly, based on SEP [42]. we design two efficient operators, MERGE and DROP, to construct coding tree T with minimum structural entropy. An overview of these operators is shown in Algorithm (in Appendix D)
Remark. The coding tree, a hierarchical abstraction of the original graph structure, can be considered a contrastive view T arg min H² (G), which serves as an instantiation of the essential information in graph G. By minimizing structural entropy, this essential view T effectively reduces redundant information from the graphs while preserving distinctive structural features, enabling the capture of distinct patterns between ID and OOD samples.
Representing Learning on Essential Information. Within the test-time OOD detection setting, the parameters of the pre-trained model are frozen. To maintain the optimal representation of the essential information, we update parameters the coding tree encoder based on the tree essential view T constructed during preprocessing. Specifically, the encoder is designed to iteratively transfer messages from the bottom to the top. Formally, the I-th layer of the encoder can be written as, X (1) (LP( (Enec(u)
x -)). where x(, the feature of in the i-th layer of coding tree T, x! is the input feature of leaf nodes, and C(v) refers the children of The aggregated node features from the (l - 1) 1t layer of coding tree are used as inputs for the 1-th layer, continuing the propagation towards the top of the tree. Once the features reach the root node, readout function is applied to obtain the tree embedding Zr-
Instantiation for I(f(G)) f()).. Based on the lower bound derived in Eq. the mutual information between the essential view G and basic view G is estimated by:
T(f(G)); f(G) -Cci(G",O
(15)

---

Table OOD detection results in terms of AUC (%, mean + std). The best and runner-up results are highlighted with bold and underline, respectively. A.A. is short for average AUC. A.R. implies the abbreviation of average rank. The results of baselines are derived from the published works, with unreported results denoted by" '-'.
PTC-MR
AIDS
IMDS-M
Tos21
FreeSalv TeaCas
A.A.
deor
Merkods
PK-LOF
42.2218.39
51.046004
50.1513.29
50.7222.7
48 4800::2533
51.33 L81
49 39.15.3.70
23.
S0.0:2.17
40.82:145
49.63
14.9
PK-0U3VM
12.5548..6
49.71:6.5
90.1763.30
504665778
48174241 41
51.339118 18
48 68 2M
5308-2 10
50
518961:31
49.53
14.8
PK-IF
$1,451162
$4.20=2.33
51.001143
S16722550 59
50.67:2-47
49,5720082
5225411.37
51.4721.33
50.1123.10
50.523351
51A4
12.9
WI-L
889916.20
8:
57A8-3-47 47
51-92--1 1.5
12-0--11 M1
1-40
512661131
51.6
WL-OCSVM
4915444.1
53.31=7.57
$1.36:2399
510811146
22.882200
50.7133.99
50.771165
13.0
50
62.6012..6
Dese Temsnio Marhods
Infotinph-a
651774974
51.43-518
95 35
N6 73:11 Ms. 56. 00-
56 56.92-1.00 AM
85-51
561644514
59.00
9.9
InftGnaeh MD
86.1416.77
50.7928.69
000221107
55.2553.51
$138:114
59.9722.06
58.543346
70.49:4461
48.1215.72
77.5721199
55.65
8,5
Gmphtll-fF
90001-31
54.8
92901121
1167-165
90.4
4133610.02
62.1244.01
50.5
10.2
GryOCTLM MD
136426000
73.00=233
937754213
52.8755.11
79099223
55,30:1.522
00.3165:24
75.72=1.54
51,5883.6
78.7361.40
70.70
Melhod
DOGIN
16051411
84 84
160116.99
6791-386
46:00-166 1.66
50 54601-476
61:11-111
4615-4415
56061530
6981
9.1
GLocdlDD
15.75
73.63:3.54
236672124
57.18:208
25245
66.28205
648223331
75.15=1.26
55.71
56334235
72.23
6.1
GOOD-D
930013:20
7643-266
(6911011
61.992551
19 79
65 1:22
70 ma.1-275
81 8155-199 199
91.991046
7866
14
GOOD D
S199432.5
21.21:2265
9907740.00
613411194
66,5011335
80.1543.33
$2.91-2558
09.8831.1
91.5230.70
80.21
24
55,1715044
62.38:236
00:1221955
49,945567
$1:55:900
61677:077
30.113305
64.022211
54.5442.38
7633133.5
10.0
A
76.75
66.20
5000
64.25
67.50
AAGOD,
76,00
65,89
62.70
57.59
$7.13
GOODAT
$2.1810.15
91.84:055
06.3310.25
16.2911.54
79
09000003
66.92:0001
688310000
77:00007
62.4610.54
859110227
76.80
3.9
RaiNUT
998610.54
1.66
71,871
929911084
92.00 0.21
863618766
900810.44
K7.46
1.3
Improwe
2.1000
A11261
A10%)
2-0.46
4.2275
1.12.
1.9.0
4.17335
A.3.48
Instantiation for (G)))) To specify the variational upper bound, we treat the similarity approximation of the
between Zr and Z given the predicted label Y arg max(ssff(xxxx(( e eiim .Zr), where Z
log-likelihood (f Y). and set Q(f(G))) = E
negative samples drawn from the conditional distribution P(J(G)))) Thus, I(f(G"): Y) can be approximately instantiated as (Proof in Appendix CCB
I(f(G";;(G)) = LCRi(G,
(16)
where Lens is conditional redundancy--llmmintee loss, i.e.,
(G, A E B..2,--)222 (Z Zr) logg - e si (2" _ZTr
(17)
Optimization. Regarding objectives in Eq. 15) and 16 the overall optimization objective is:
L= La + XCCRI,
(18)
where X is trade-off hyperparameter. When implementing OOD detection, we employ this overall loss as the OOD detection score.
4 Experiment
In this section, we empirically evaluate the effectiveness of the proposed RedOUT Detailed settings and additional results can be found in Appendix [
Datasets, For OOD detection, we employ 10 pairs of datasets from two mainstream graph data
benchmarks (i.e., TUDataset (24) and OGB (TT) following GOOD-D (20). We also conduct
experiments on anomaly detection settings, where the samples in minority class or real anomalous
class viewed anomalies. Further details are shown in Appendix E.
Baselines. We compare RedOUT with 18 competing baseline methods, including 6 graph kernel based methods (32 38 4 GCL
20 34, 49 based methods, 4 end-to-end training methods [11. I test-time training methods [12]. and 3 data-centric OOD detection methods
More details
about implementation are provided in Appendix B.2
Evaluation and Implementation. We evaluate RedOUT with a popular OOD detection metric, i.e. the area under receiver operating characteristic Curve (AUC). Higher AUC values indicate better performance. The reported results are the mean performance with standard deviation after 5 runs.
'hh code of RedOUT is available https://github. http://gtttuuub.mm//aaaaaee www/cameeooo/eeecceeeeeeeeoeee what/RedOUR
7

---

4.1 Performance on OOD Detection
In this section, we compare our proposed methods with 18 competing methods in OOD detection tasks. From the comparison results in Table we observe that RedOUT achieves superior performance improvements, which outperforms other baselines 9 out of 10 dataset pairs and ranks first on average among all baselines with an average rank (A.R.) of 1.3. Concretely, RedOUT achieves an average AUC of 87.46, outperforming all compared methods by 6.7% over the second-best approach GOOD-D 120] Moreover, RedOUT delivers nearly a 10% performance gain on 4 pairs of molecular datasets. Notably, on the Clin Tox/LPPO dataset pair, RedOUT surpasses the best competitor by 17.3%. These findings highlight the superiority of RedOUT in OOD detection tasks, demonstrating its strong capability to capture essential information in graph data.
We also observe that RedOUT does not achieve the absolute best results on the IMDB-B/MDD--M dataset pair. We consider this phenomenon be within our expectation, as for molecular graphs, semantic information is directly manifested in their structural composition (e.g., molecular functional groups), thereby enhancing effectivvness. In contrast, for social networks such as IMDB-B and IMDB-M, which originate from the same data source and differ only in labels, the inherent semantic information is similarly reflected structurally, making it challenging to distinguish based solely on structure. A further explanation is provided through a case study in Sec. 4.5
Time Complexity Analysis. Given graph G (V,E), the time complexity of coding tree construction is O | general, the coding tree T tends to be balanced in the process of structural entropy minimization, thus, h will be around log [V] Furthermore, a graph generally has more edges than nodes, i.e., |E| >
[ [V])), in which is the height of coding tree T after the first step. In
V
To evaluate the efficiency of RedOUT, plot the runtime and memory usage at peak time on Réngi graphs with [&] 2| shown in Figure The results illustrate that from smaller scales to the OGB datasets (e.g., ogbg-code2, with an average count of around 100 nodes), the runtime and memory usage scale up nearly linearly with [V]. which is consistent with the theoretical analysis above. RedOUT remains efficient even for graph sizes that exceed those of OGB datasets. We also compared the time consumption in Appendix E.6
Time and Memory Usage Frdös- Rényi Graphs
2.00
Meniory Usage (GB)
200
Time Usage
Time Usage
Memory Usage
1.75
100-
1.50
1.25
0
2000
4000
6000
8000
10000
#Node
Figure 4: Scalability of coding tree construction on Ménōs-Rényi graphs with |ε 2 V
Table 2: Anomaly detection results in terms of AUC (%, mean + std). The best and runner-up results are highlighted with bold and underline, respectively.
4.2 Performance on Anomaly Detection
To investigate if RedOUT can generalize to the anomaly detection setting (1], we con- duct experiments on 5 datasets following the
Datneet
ENZYMES
DHFR
IMDB-B
REDDIE
benchmark in GOOD-D 20). From the results shown in T significant performance improvements com- pared to other basclines, owing to the strong capability to capture essential patterns. More experiments on other 5 datasets for anomaly detection can be found in Appendix E.8
OCSVV
53.671266
51.901201
46.7213442
we find that RedOUT shows
WL-IF
W1-0CSVM
51.6013381
50.2911.77
52,4633.00
5408-5.19
50.20:0.400
48.261..32
GrahhLL
53. 33.6011-855
51.1011.35
00.2415.37
$6.50=450
71:8014.38
OCGIN
58,7515.99 98
49.2313.00 05
65.9111.47
60.19_350
75.931865
GLocalKD
61.3918881
56.1133.57
69.42.7.7
52.09-341
17.851262
GOOD-D...
61.2414.55
61.7113 58
94.48.491
65 65.49:1.00
878711 1.36
GOOD-0
63
N18/1311
75.16:5.155 15
6538-0075
66676112 1.24
GTam
05.02+6.24
61-15+2.87
$1.97+9.15
45.14-3.75
6971+-231
GOODAT
52.3324.74
61,521:2.86
64.7723.57
65.46::434
30.31:0025
RedOUT
77.6415.4
65.5114955
89.62-4.72
67.48 67.48-0.59
89.81-254 2.54
4.3 Ablation Study
In this section, we conduct ablation experiments on all OOD detection datasets to analyze the effectiveness of two variants by separately removing Lei and Len-- Results are presented in Table Ablating Lei prevents the pre-trained model from obtaining new optimal representation for calibrating the OOD score. In contrast, ablating LCRS impairs the removal of irrelevant redundant information. This further demonstrates the effectiveness of ReGIB in disentangling essential and redundant information. Concretely, we witness RedOUT surpassing both variants, which provides insights into the effectiveness of the proposed losses and demonstrates their importance in achieving better performance for capturing essential information.
8

---

Table 3: Ablation study results of RedOUT and its variants in terms of AUC (%, mean + std). The best and runner-up results are highlighted with bold and underline, respectively.
Aei
Gova
BZR
PIC-MR
AIDS
ENZYMES
IMDB-M
Tox21
FreeSolv
BHBP
Clinixx
COX2
MUTAG
DEIE
PROTEIN
IMDB-B
SIDER
ToxCast
BACE
LIPO
MUV
93.04:1183
86. 78.372272
28.79:20.2
08.7623.0
23.28:2.13
68.6611
87.652441
86,3811
76.152345
926142332
92.75+1.71
89.40+284
58.73+281
72.67+2.13
67.05+1
85,99+1
76,90+243
91.77
/ 95.06.10.54
94,451166
99.98100.16
66.7511.02
79,5410.73
71.67.0.99
92,97.0.84
92.00.0.23
86.56.10.66
95.010..44
4.4 Parameter Study
The Height is of Graph's Natural Hierarchy. Here, delve deeper into the effect of the height k on the graph's 's natural hicrarchy. The specific performance of RedOUT under each height k. ranging from 2 to 5, on OOD detection is shown in Figure 5 We can observe that the optimal height & with the highest accuracy varies among datasets. We also conducted experiments on the impact of coding tree height anomaly detection datasets, detailed in Appendix E.9
93
Ind3 1x42
Ind1
led4 Ie le
In 81 Ia-2 Io-81
220
AMT
AUC
928
AUC
000-
16 1043 1642 1041
1604 1640
30043 1042 10-91
Figure 6: The sensitivity of hyperparameter X. Sensitivity Analysis of x. To analyze the sensitivity of À for RedOUT, we alter the value from le-04 to 1. The AUC w.r. different selections of X is plotted in Figure O Results demonstrate the performance is sensitive to changes in À and contains reasonable range across different datasets.
Figure 5: The natural hierarchy of graph.
4.5 Visualization and Case Study
The embeddings learned by Red- OUT on AIDS/DHFR are visualized using SNE (37 in Figure [c)) The representa- tions from the pre-trained model tend to blend ID and OOD graphs. The limitation of GOO- DAT 39 lies in the relatively small representa- tion space, which results in over-compression of representations and consequently diminishes the discriminability between ID and OOD samples. In contrast, the representation gap in Zr is most prominent, highlighting its superior effective- ness in capturing essential structures.
Visualization.
ID Crigh
II Gregh OOD Greg
loggs odt Gugt
OOD Coiph
(a) w.r.t Z
(b) w.r.t Zr (c) w.r.t GOODAT
Figure 7: T-SNE visualization of embeddings, where is from the pre-trained model, and Zr is from the coding tree encoder.
Case Study. To further investigate the suboptimal performance of RedOUT social networks, visualize the essential structures extracted on IMDB-B and IMDB-M, as shown in Figure([j)-(b)) These datasets share similar structural characteristies (e.g., star-shaped and mesh-like patterns) but differ in the nature of classification task (binary versus multi-class). The similarity in structural semantics suggests that the intrinsic information captured by the coding tree may not sufficiently dis- tinguish these datasets from a structural standpoint, consistent with the results in Table [ In contrast, Figure g (d) illustrates the extracted essential structures PTC-MR and MUTAG, highlighting RedOUT's capability in molecular datasets where structural differences are more pronounced and crucial for OOD detection. Additional case studies and analyses are provided in Appendix E.
5 Related Work
Graph Out-of-distribution Detection. Graph OOD detection aims to distinguish OOD graphs from ID ones to address the excessive confidence predictions. Lots of cxisting methods (54 16 focus

---

IMDR-M
(b) IMDB-B
(c) PTC-MR
(d) MUTAG
Figure 8:
Visualization of the essential structure based on the coding tree preserved by RedOUT on IMDB-B/MMDB-M and PTC-MR/MUTAG dataset pairs.
on improving the generalization ability of GNNs for specific downstream tasks like node classification through supervised learning, rather than identifying OOD samples. Other advancements 20 39
focus on training OOD-specific GNN models or enable well-trained models in a post-hoc manner with training or samples. In this work, we provide novel perspective for identifying OOD graphs at test-time by focusing essential information based on structural entropy.
Structural Entropy. Structural entropy [15] extension of Shannon entropy B1], quantifies system uncertainty by measuring the complexity of graph structures through the coding tree. Structural entropy has been widely applied in various domains [50 42
40), such dynamic network analysis [19]. hierarchical community detection [43, and graph structure learning (55). In our work, apply structural entropy to capture the distinetive structure with essential information test graphs for test-time OOD detection.
Discussion and Comparison with Related Methods. Here, we elucidate the association between our proposed RedOUT and two prominent methods, namely GOODAT 33 and SEGO 10
GOODAT. GOODAT [39] first introduced the setting of test-time OOD detection, where plug- and-play graph masker is trained to decompose the test-time graph into two subgraphs. Although GOODAT is built upon the GIB principle, it does not consider the redundancy in graph structures and cannot guarantee that the subgraph decomposition preserves semantic information. In contrast, RedOUT is the first theoretically decouple GIB into redundant and essential components, and improves OOD detection for pre-trained models by explicitly removing redundancy at test-time.
SEGO. SEGO 10 stands as pioneering work specifically crafted for unsupervised OOD detection, achieving promising results through pre-hoc operation that minimizes structural en- tropy. is noteworthy that SEGO a fully end-to-end method trained from scratch, which differs from the setting considered in this paper. Although SEGO also follows structural information principles, it does not investigate what constitutes redundancy or how should be removed. In contrast, our approach is the first to isolate redundancy from the perspective of GIB and extract the essential structural information.
Further comparisons and analysi can be found in Appendix E.5 and E.6
6 Conclusion
In this paper, we present a redundancy-aware test-time OOD detection framework, termed RedOUT, aiming at endowing well-trained GNN models with the ability to extract essential information Graph Information Bottleneck
for the first time. Concretely, we propose the Redundancy-auts and decompose the objective into essential information and irrelevant redundancy. By minimizing structural entropy, coding tree constructed instantiate the essential view, and tractable bounds introduced for efficient optimization. Extensive experiments on real-world datasets demonstrate the superior performance of RedOUT over sfate-of-the-ar baselines in unsupervised OOD detection. One limitation is that mainly consider the graph-level tasks, and leave extending method to the nove-level fest-time OOD detection for future explorations.
Acknowledgements
This work has been supported by CCSE project (CCSE-2024ZX-09).
"Since SEGO adopts data- cnta-centric preprocessing strategy to assist OOD- training. it does not fall under the category of native end-to-ent methods. Therefore, compare separately with RedOUT in Table B
10

---

References
[1] Alexander A. Alemi, lan Fischer, Joshua V. Dillon, and Kevin Murphy. Deep variational information bottleneck. In ICLR, 2017.
[2] Philip Bachman, R. Devon Hjelm, William Buchwalter. Learning Representations by Maximizing Mutual Information Across Views. In Advances in Neural Information Processing Systems 32, pages 15509- 15519, 2019.
[3] Tianyi Bao, Qitian Wu, Zetian Jiang, Yiting Chen, Jiawei Sun, and Junchi Yan. Graph out-of-distribution detection goes neighborhood shaping. In Forty-first International Conference on Machine Learning, 2024.
[4] Markus M Breunig, Hans-Peter Kriegel, Raymond T Ng, and Jörg Sander. Lof: identifying density density-based local outliers. In SIGMOD, pages 93-104, 2000.
[5] Ting Chen, Simon Komblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In ICML, pages 1597-1607. PMER, 2020.
[6] Thomas M Cover. Elements of information theory. John Wiley & Sons, 1999.
[7] Eleanor J Gardiner, John D Holliday, Caroline DoDdd, and Peter Willett. Fffeetivvnnes of 2d fingerprints for scaffold hopping. Future Medicinal Chemistry, 3(4))405 2011.
[8] Kaitlyn M. Gayvert, Neel S Madhukar, and Olivier Elemento. A data-driven approach to predicting 2016.
successes and failures of clinical trials. Cell Chemical Biology,
[9] Yuxin Guo, Cheng Yang. Yuluo Chen, Jixi Liu, Chuan Shi, and Junping Du. A data-centric framework to endow graph neural networks with ofiit--diitiitttinn detection ability. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 388-688 2023.
[10] Yue Hou, He Zhu, Ruomei Liu, Yingke Su, Jinxiang Xia, Junran Wu, and Ke Xu. Structural entropy guided unsupervised graph out-of- of-distribution detection. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pages 17258 17266, 2025.
[11] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In NeurlPS, volume 33, pages 22 22118-22133, 2020.
[12] Wei Jin, Tong Zhao, Jiayuan Ding, Yozen Liu, Jiliang Tang, and Neil Shah. Empowering graph representa- tion learning with test-time graph transformation. ICLR, 2022.
[13] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
[14] Michael Kuhn, Ivica Letunic, Lars Juhl Jensen, and Peer Bork. The sider database of drugs and side effects. Nucleic Acids Research, 44(01): D1079, 2016.
[15] Angsheng Li and Yicheng Pan. Structural information and dynamical complexity of networks. IEEE Transactions Information Theory, 62:3290-3333 -3399, 2016.
[16] Haoyang Li, Xin Wang, Zeyang Zhang, Haibo Chen, Ziwei Zhang, and Wenwu Zhu. Disentangled graph self sulervupe learning for diitt--ddittitttio generalization. In Forty-first International Conference on Machine Learning, 2024.
[17] Xiner Li, Shurui Gui, Youzhi Luo, and Shuiwang Ji. Graph structure extrapolation for out-of-distribution generalization. In Forty-first International Conference on Machine Learning, 2024.
[18] Fei Tony Liu, Kai Ming Ting, and Zhi-Hua Zhou. Isolation forest. In ICDM, 2008.
[19] Yiwei I. Liu, Jiamou Liu, Zijian Zhang, Lichuang Zhu, and Angsheng L.. REM: from structural entropy to community structure deception. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 1291 12918-1292,, 2019.
[20] Yixin Liu, Kaize Ding, Huan Liu, and Shirui Pan. Good-d: On unsupervised graph out-of distribbbbttio detection. In Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining, pages 339- 347, 2023.

---

[21] Rongrong Ma, Guansong Pang, Ling Chen, and Anton van den Hengel. Deep graph-level anomaly detection by glocal knowledge distillation. In WSDM, 2022.
[22] Larry M Manevitz and Malik Yousef. Ole-class svms for document classification. JMLR, 13D 154, 2001.
[23] Ines Filipaa Martins, Ana L Teixeira, Luis Pinheiro, and Andre O Falcao. A bayesian approach to in silico blood- brain barrier penetration modeling. Journal of Chemical Information and Modeling, 52(6))1686- 1697, 2012.
[24] Christopher Morris, Nils M. Kriege, Franka Bause. Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. In ICML Workshop, 2020.
[25] Marion Neumann, Roman Garnett, Christian Bauckhage, and Kristian Kensting. Propagation kemels: efficient graph kernels from propagated information. Machine Learning, 102(2):209-22)) 245, 2016.
[26] Paul A Novick, Oscar F Ortiz, Jared Poclman, Amir Y Abdulhay, and Vijay S Pande. Sweetlead: an in silico database of approved drugs, regulated chemicals, and herbal isolates for computer-aide aided drug discovery. PloS One, 8(1 =(75)88, 2013.
[27] Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding, arXiv preprint arviv: /00::800... 007400378, 2018.
[28] Ben Poole, Sherjil Ozair, Aäron van den Oord, Alexander A. Alemi, and George Tucker. On Variational Bounds Mutual Information. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 5171-5180. PMLR, 2019.
[29] Ann M Richard, Richard S Judson, Keith A Houck, Christopher M Grulke, Patra Volarath, Inthirany Thillainadarajah, Chihae Yang. James Rathman, Matthew T Martin, John F Wambaugh, et al. Toxcast chemical landscape: paving the road to 21 century toxicology. Chemical Research in Toxicology. 29(8):1225 1251, 2016.
[30] Vikash Sehwag, Mung Chiang. and Prateek Mittal. Ssd: A unified framework for self- self-supervised outlier detection. In ICLR, 2021.
[31] Claude E. Shannon. A mathematical theory of communication. Bell Syst. Tech. J. 27(3):379 -233, 1948,
[32] Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weisfeiler- graph kemels. JMLR, 12(9), 2011.
[33] Govindan Subramanian, Bharath Ramsundar, Vijay Pande, and Rajiah Aldrin Denny. Computational modeling of 3-secretase 1 (bace- 1) inhibitors using ligand based approaches. Journal of Chemical Information and Modeling, 56( 1931009993619999 2016.
[34] Yun Sun, Jordon Hoffman, Vikas Verma, and Jian Tang. Infograph: Unsupervised and semi semi-supervised graph-level representation learning via mutual information maximization. In ICLR, 2020.
[35] Fan-Yun Sun, Jordon Hoffman, Vikas Verma, and Jian Tang. Infograph: Unsupervised and semi-supervised graph-level representtinn lcarning via mutual information maximization. ICLR, 2020.
[36] Michael Tschannen, Josip Djolonga, Paul K. Rubenstein, Sylvain Gelly, and Mario I Lucic. On Mutual Information Maximization for Representation Learning. In Proceedings of the 8th International Conference on Learning Representattons, 2020.
[37] Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. JMLR, 9(11), 2008
[38] S Vichy N Vishwanathan, Nicol N Schraudolph, Risi Kondor, and Karsten M Borgwardt. Graph kernels. JMLR, 11:1201-1242, 2010.
[39] Luzhi Wang, Dongxiao He, He Zhang, Yixin Liu, Wenjie Wang, Shirui Pan, Di Jin, and Tat-Seng Chua. Goodat: Towards test-time graph out-of-distribution detection. In Proceedings of the AAAI Conference on Artificial Intellignce, volume 38, pages 15537-15545, 2024.
[40] Yifei Wang, Yupan Wang, Zeyu Zhang, Song Yang, Kaiqi Zhao, and Jiamou Liu. USER: unsupervised structural entropy-based robust graph neural network. In Brian Williams, Yiling Chen, and Jennifer Neville, editors. Thirty-Seventhy AAAI Conference on Artificial Intelligence, AAAI 2023, Thirty-Fithh Conference on Innovative Applications of Artificial Intelligence, IAAI 2023, Thirteenth Symposium on Educational Advances in Artificial Intelligence, EAAI 2023, Washington, DC, USA, February 7-14, 2023. AAAI Press, 2023.
pages 10235- 10243, 10235-10243,
12

---

[41] Junran Wu, Xueyuan Chen, Bowen Shi, Shangzhe Li, and Ke Xu. Sega: Structural entropy guided anchor view for graph contrastive learning. In International Conference Machine Leurning. PMLR, 2023.
[42] Junran Wu, Xueyuan Chen, Ke Xu, and Shangzhe Li. Structural entropy guided graph hierarchical pooling. In International Conference Machine Learning, pages 24017-24030. PMLR, 2022.
[43] Junran Wu, Shangzhe Li, Jianhao Li, Yicheng Pan, and Ke Xu. A simple yet effective method for graph classification. In Lue De Raedt, editor, Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI 2022, Vienna, Austria, 23-29 July 2022, pages -3860-366..0 ijcai.org, 2022.
[44] Qitian Wu, Yiting Chen, Chenxiao Yang, and Junchi Yan. Energy-based duitt--iistiiuutionn detection for graph neural networks. The Eleventh International Conference on Learning Representations. 2024.
[45] Tailin Wu, Hongyu Ren, Pan Li, and Jure Leskovec. Graph information bottleneck. Advances Neural Information Processing Systems, 33:20437 20448, 2020.
[46] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? In ICLR, 2019.
[47] Shenzhi Yang, Bin Liang, An Liu, Lin Gui, Xingkai Yao, and Xiaofang Zhang. Bounded and uniform energy-based out-of-dittibbttio detection for graphs. In Forty-first International Conference on Machine Learning, 2024.
[48] Zhenyu Yang, Ge Zhang, Jia Wu, Jian Yang. Quan Sheng, Hao Peng, Angsheng Li, Shan Xue, and Jianlin Su. Minimum entropy principle guided graph neural networks. In Tat-Seng Chua, Hady W. Lauw, Luo Si, Evimaria Terzi, and Panayiotis Tsaparas, editors. Proceedings of the Sixieenth ACM International Conference on Web Search and Data Mining, WSDM 2023, Singapore, 27 February 2023 3 March 2023, pages 114-122. ACM, 2023.
[49] Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. In NewrlPS, volume 33, pages 5812 5823, 2020.
[50] Chong Zhang, He Zhu, Xingyu Peng, Junran Wu, and Ke Xu. Hierarchical information matters: Text classification via tree based graph neural network. In Nicoletta Calzolari. Chu-Ren Huang, Hansaem Kim, James Pustejovsky, Leo Wanner, Key-Sun Choi, Pum-Mo Ryu, Hsin-Hsi Chen, Lucia Donatelli, Heng Ji, Sadao Kurohashi, Patrizia Paggio, Nianwen Xue, Scokhwan Kim, Younggyun Hahm, Zhong Hc, Tony Kyungil Lee, Enrico Santus, Francis Bond, and Seung- Hoon Na, editors, Proceedings of the 29th International Conference on Computational Linguistics, COLING 2022, Gyeongju, Republic of Korea, October 12-17, 2022, pages 950-959. International Commiltee on Computational Linguisties, 2022.
[51] Lingxiao Zhao and Leman Akoglu. On using classification datasets to evaluate graph outlier detection: Peculiar observations and new insights. Big Data, 2021.
[52] Wenxuan Zhou, Fangyu Liu, and Muhao Chen. Contrastive out-of-distribution detection for pretrained transformers. EMNLP, pages 1100-1111 2021.
[53] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Graph contrastive learning with adaptive augmentation. In WWW, pages 2069-2080. 2021.
[54] Yun Zhu, Haizhou Shi, Zhenshuo Zhang, and Siliang Tang. Mario: Model agnostic recipe for improving ood generalization of graph contrastive learning. Proceedings of the ACM on Web Conference 2024, pages 300-311, 2024.
[55] Dongcheng Zou, Hao Peng, Xiang Huang, Renyu Yang. Jianxin Li, Jia Wu, Chunyang Liu, and Philip Yu. Se-gsl: A general and effective graph structure learning framework through structural entropy optimization. In Proceedings of the ACM Web Conference 2023, pages 499-510, 2023.
13

---

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:
Abstract and introduction accurately reflect the paper's contributions and
Scope.
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 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: [Yes]
The limitations regarding the future research direction of the work are discussed in the conclusion section.
Justification:
Guidelines:
The answer NA means that the paper has 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 in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiitiinn asymptotic approximations only holding locally). The authors should reflect on 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 on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails 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 faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
14

---

Answer:
[Yes]
Justification:
The full set of assumptions and proofs is provided in the paper.
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 in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or 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 the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: Our paper fully discloses all the information needed to reproduce the main experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a 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 a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a 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 submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is 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., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
15

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
The adopted datasets are public datasets. The code of RedOUT is available.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
//nips //ipss.cc/pill wttpcccpppppppppeeeeeeeeeeeeeeee httpa///giiieee/eeeSebiiisssssss /Cc////oddiiisssseeeeeee ssi.isoiccyyyyyciicc for more details.
The authors should provide instructions on 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. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
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 understand the results?
Question:
Answer: [Yes]
Justification: Our paper specifies all the training and testing details.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary 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: Our paper shows average results over 5 runs with different random seeds and reports the variance for our metrics.
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 error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
16

---

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).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It 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 figures symmetric error bars that would yield results that are out of range (c.g. negative emror 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 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: Our paper provides sufficient information on the computer resources.
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, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as 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 or failed experiments that didn't 't make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of httphhhp..p..............pp//ppt
Answer: [Yes]
Justification: Our research complies with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have 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 in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
The socictal impacts of the work are discussed Appendix F
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or 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.
17

---

The conference expects that many papers will be foundational research and not tied 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 intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risk.
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 not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: 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?
Answer: [Yes]
Justification: The adopted datasets and compared baselines properly credited.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or 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 (c.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 package should be provided. For popular datasets, paperswi thcode. com com/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.
18

---

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: Our 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: Our 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.
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:
Our 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
19

---

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 the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA
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.
20

---

Technical Appendices and Supplementary Material
Notation Table
21
Related Work
21
Theoretical Justification
22
Preliminaries for Mutual Information
22
Proof for Proposition C.3
23
Proof for Proposition
23
Proof for Proposition
24
Proof of Theorem C.9
26
C.6
Proof of Theorem C.12
27
Proof of Theorem C.15
28
C.8
Proof of Instantiation for [(f('')) f(G)
30
C
Further Comparison of ReGIB and GIB with Random Augmentation Views
31
Algorithms
32
Experiment
33
Dataset Description
33
Baseline Details
36
E,3
Conligurations
37
E,4
Additional Experiments Using Structural Entropy Distinct Metric
37
Comparison Results of RedOUT with Structural Entropy Guided End-to-end Training
38
E.6
Efficiency Analysis and Runtime Comparison
38
E.7
Additional Results of Parameter Study OOD Detection
39
Additional Results of Anomaly Detection Performance
40
E.9
Additional Results of Parameter Study on Anomaly Detection
40
E. 10 Additional Case Study on ID/OOD Dataset Pairs
41
Broader Impacts
Notation Table
As an expansion of the notations in our work, we summarize the frequently used notations in Table
B Related Work
Graph Out-of-distribation Detection. Graph OOD detection aims to distinguish OOD graphs from ID ones address the excessive confidence predictions. Lots of existing methods [54 17 focus on improving the generalization ability of GNNs for specific downstream tasks like node classification through supervised learning, rather than identifying OOD samples. Other advancements focus on training OOD-specific GNN models or enable well-trained models in a post-hoc manner with training or test samples. In this work, we provide novel perspective for identifying OOD graphs at test-time by focusing essential information based structural entropy.
20 39)
21

---

Table The most frequently used notations in this paper.
Notations
Descriptions
G (V,EX)
Graph with the node set V/ and edge set &
The of nodes in the graph
The set of edges in the graph The feature matrix
X
Ipid pood
The distribution where the graphs are sampled from The label of test graph
Y E {0,1)
The predicted label of test graph The adjacency matrix of the graph The original graph as the basic view Perturbation- frree augmentation on G The structural entropy
A
G XA
G PA.P)
H
T
Tree essential view of the graph The coding tree height
Z
Graph embedding from the well-trained GNN model
ZT
Tree embedding
Lov, LORI
Overall loss, contrastive loss and conditional redundancy-eliminaaed loss Hyperparameter for loss trade-off
Structural Entropy. Structural entropy [5] an extension of Shannon entropy 31 quantifies system uncertainty by measuring the complexity of graph structures through the coding tree. Structural entropy has been widely applied in various domains (50) 42, 48, 41 40], such as dynamic network analysis [9), hierarchical community detection [43), and graph structure learning (55). In work, we apply structural entropy to capture the distinctive structure with essential information on test graphs for test-time OOD detection.
Discussion and Comparison with Related Methods. Here, we elucidate the association between proposed RedOUT and two prominent methods, namely GOODAT 39 and SEGO [00
GOODAT. GOODAT (39] first introduced the setting of test-time OOD detection, where plug- and-play graph masker is trained to decompose the test-time graph into two subgraphs. Although GOODAT is built upon the GIB principle, it does not consider the redundancy in graph structures and cannot guarantec that the subgraph decomposition preserves semantic information. In contrast, RedOUT is the first theoretically decouple GIB into redundant and essential components, and improves OOD detection for pre-trained models by explicitly removing redundancy at test-time.
SEGO. SEGO 10) stands out as a pioneering work specifically crafted for unsupervised OOD) detection, achieving promising results through pre-hoc operation that minimizes structural en- tropy. is noteworthy that SEGO a fully end-to-end method trained from scratch, which differs from the setting considered in this paper. Although SEGO also follows structural information principles, it does not investigate what constitutes redundancy or how it should be removed. In contrast, our approach is the first isolate redundancy from the perspective of GIB and extract the essential structural information.
Further comparisons and analysis can found in Appendix E.5 and E.6
C Theoretical Justification
C.1 Preliminaries for Mutual Information
Definition C.1 (Informational Divergence). The informational divergence (also called relative entropy or Kullback-Leibler distance) between two probability distributions and finite space X (i.e.,
"Since SEGO adopts data-centric preprocessing strategy to assist OOD OOD-specitic training. it does not fall under the category of native end-to-end methods. Therefore, compare separately with RedOUT in Table B
22

---

common alphabet) is defined as
DKL(Plla) = Σ p(x) log p(a) g(x)
Ep log ((X). q ((x)
(19)
ZEN
measures the distance between p and q. However, D(-II-) is not true Remark C.1. (Kl q)
metric, and it does not satisfy the triangular inequality. DKL (p) (q) is non-negative and zero if and only if p q.
Definition C.2 (Mutual Information). Given two discrete random variables X and Y. the mutual information (MI) (X; Y) is the relative entropy between the joint distribution p(2; y) and the product of the marginal distributions p(x) namely,
[(X; Y) =Ku v) Ip(x)p(())
p(a, v) p(z)p(u)
E rEX,EEY
p(z,)) log
(20)
p(z())
Σ
vlz, v) log
p(x))
DEX,EEY
Remark C.2. I(X;Y) is symmetrical in X and Y. i... (XX;)) H(X) H(X|Y) H(Y)
X( = XX:
C.2 Proof for Proposition
C33
Proposition C.3 (Lower Bound of T((()));))
(21)
Proof.
=
(22)
Since mutual information is non-negative, i.e.,
((((G) O.
(23)
This implies that:
(24)
C.3 Proof for Proposition
C.4
To begin with, revisit the graph contrastive learning loss Lor, formally expressed as:
sim (2 1/T
Lei(G"
log
(25)
N
2 e sim 22 25)//
where N denotes the batch size, T the temperature coefficient, and sim(... stands for cosine similarity function.
Proposition C.4 (Lower Bound of I(f(G);
ff(G));;(GG) -Car(G",G) + log(N.
(26)
Proof. From 27 easily get a lower bound of mutual information between Z and z
sim 2?)
sim (Z. (Z. .Z,)
E(G
log
log
S IZZ Z,") log(N).
- sim (Z. 23)
==1jf1 sim ZZ (5)
(27)
23

---

According to Eq. 25 we get
e 2, 2
N
esmm(Z 2,
1
Lei(G", GD) Bia ,Ga)
log
log
ji a (2). 23))
N
Lj=
N
cetm) 2 229)
(28)
Thus, minimizing (Gr G is equivalent to maximize the lower bound of [Z, ZZ,)
Therefore, we have
- G ,G) s [(; z log(NN,
(29)
which is equivalent to:
(U(G));)())) 2 -Cr G) + log(N).
(30)
This indicates that minimizing the contrastive loss Loi(G", G) is equivalent to maximizing the lower bound of the mutual information (ff(G");
C.4 Proof for Proposition
C.7
We first apply the upper bound proposed in the Variational Information Bottleneck [.
Lemma C.5 (Variational Upper Bound of Mutual Information). Given any two variables X and Y.
we have the variational upper bound of [(;; (X;Y):
P(Y
P(YI))0()
I(X; Y) Bp(x,r)
log P(Y)
E log P(Y)(())
log X(Y DKL (P())IQ(()
Ep(x.))
Q(Y)
non-nogative
X(Y Q(Y)
$ Er(x,)
log
(31)
Lemma C.6 (Variational Upper Bound of Conditional Mutual Information). For any Q(U|Y).
P(VU, Y)
IU:VIY) < Ex(.Y
log Q(VIY)
(32)
Proof. According to Lemma C.5 we can derive a variational upper bound for the conditional mutual information I(U; V|Y). First, the conditional mutual information can be expressed as:
PUU. V(Y I(U: VIY) = EP(C.V.) log P(U]Y)((VI))
(33)
Using the properties of conditional probability, have
F(U, VIY) P(VIU, ()P(Y
(34)
Substituting this into the expression for mutual information, we obtain:
= ERU.VY log PV Y) P(VIY)
(U:V = Exw.Y log
(35)
P(U]Y))(VIY)
Next, introduce a variational distribution Q(V for V, and utilize the logarithmic identity:
PVVV,,Y log P(VIU, Y) log P(V]Y) Q(VYY)
log P(VVY) Q(VIY)
(36)

---

Therefore, the mutual information can be re-expressed as:
log P(VIU,Y) Y) Q(VI))
Bryy log P(VI)) Q(VI))
I(UV) = BP(UYY
P(V)U)))
(37)
log Q(VIY)
DIuLI((IIY)QQQVXX))
non-negative
Since the KL divergence non-negative, we have a variational upper bound for the conditional mutual information:
(UUVIY) EE(U.Y log P(VIU,Y)
(38)
Q(VIY)
Similarly, if we introduce a variational distribution Q(UIY) for U:
I(U: VIY) S EY(U.V.) log P(U|V,Y) Q(U
(39)
In summary, the conditional mutual information I(U; VIY) can be upper bounded as:
P(V Y) Q(VIY)
P(ULY Q(UTY)
V(UV < (e log
(U; Eew.yy
log
(40)
Proposition C.7 (Upper Bound of ((f(G";; [ (()) For any Q(J(G)) the variational upper bound of conditional mutual information
(()())) s Ep log F(FG))
(41)
P(f(G=))XXO(((GIMM))
Proof. Since I(U:VIY) < EuU.V log Q(VI)) in Lemma C.6 let U = f(G"), V f(G).
P(VIUYY)
we have
[[f(G)); s Ep log P(
(42)
Q(f())
where P(f(G))((G*) Y) is the true conditional distribution PP (( P). and Q(f(G) is a variational distribution used to approximate P(f(G) Based on the multiplication rule,
(43)
This implies that
F(
P(F()))(("')) = P(f(G*))Y)
(44)
Substituting this into the variational upper bound, we have
P(
I[f("); s Ep
log Q(f(G))))
(45)
F(GG))
Ep
log
25

---

)(()))
1 G)
K(G)
(g3
HU(G")
((((G%/(())
n00%
X(GG))
IIG
K(GG
S[GT)
K((())
3(G,0*)
2((G.G*)
X(G.G")
(a) MI between original graph and anchor view. Figure 9; Venn diagram of the mutual information between original graph and essential view.
(b) MI when anchor view G*
(c) MI when is the well-
substructure of graph G.
trained GNN encoder G.
C,5 Proof of Theorem
In this section, present the proof of the statement H(G*|G) 0. First, we repeat the property that the target essential view should own: Definition C.8. The essential view with redundancy-eliminatee information is supposed be distinctive substructure of the given graph.
Now, let G be the target essential view of graph G, the MI between G and G* (i.e., [(G*; can be formulated as:
(46) where H(G") is the structural entropy of G' and H(G'IG) is the conditional entropy of G* condi- tioned on Before the proof, as shown in Figure the Venn diagram on the left suggests the mutual information (MI) between the original graph and the essential view in general cases, while the Venn diagram on right reveals MI relationship when the essential view a substructure of the given original graph (i.e., complies with Definition C.8)
I(G"; H(G H(G'IG),
Theorem C.9. The information in G* is a subset of information in G (i.e. H(G") C HHGG); thus, have
H(G (G) = 0.
(47)
Proof. According to the definition of Shannon entropy
31 iee.
H(X) = Σ
P(x) log P(z),
(48)
#EX
we follow the formulation of graph MI in 335 that X a set of node representations drawn from an empirical probability distribution of graph G, have
H(G*IG) H(X*I).
(49)
So the conditional entropy be written as:
H(X*I))= = E P())H(X'(XX))
sEX
P(x) Σ log
xEX
''EX.
(50)
Σ Σ P(x", x)) log P(x* (z)
sEX EX
P(a", a)) log P(x
Considering that G complies with the Definition C.8 the illustration of the probability distribution of G* and G is shown Figure (b. Here, let us first discuss that when X and
X*, we have
P(x x) =
(51)
Therefore, transform Eq. 50 to:
26

---

H(X1x) = Σ P(ø 2) log p(x*
Σ
x x logP(<"(<=)
Σ
P(x x)) log P(x*(z)
2'24x'
x'EX' Pog""""))
E
E
E P(x))
Σ
log
2'EXx
XXEX
E P(x P(x')H(X*| =x)
E'EX"
=H(XIX*)
=0.
(52)
Therefore, given VI E X, have
H(G G) H(X*IX)
(53)
Accordingly, we have
I(G"; H(G))
(54)
L
C.6 Proof of Theorem C.12
With the essential view eliminating redundant information, we also theoretically prove that our RedOUT effectively captures the maximum mutual information between the representations obtained from the essential view and labels by minimizing the contrastive loss in Eq. [T] The InfoMax
principle has been widely applied in representation learning literature 2 28 36) MI quantifies the
amount of information obtained about one random variable by observing the other random variable.
We first introduce two lemmas.
Lemma C.10. Given that f is GNN encoder with learnable parameters and G* is the target essential view of graph G. If T(f(G"); f(G) reaches maximum, then T(f(G*); G) will also reach its maximum.
Proof. Because f(G) is a function of G, I(J(G)):)) -1(((C))(((0++++(((()))))1))
(55)
Thus,
= K(CC):1(0)--11000)))--1110000100
(56)
While maximizing I(f(G"): ): (G)), either [(f(G"); increases or [(f(G*); Glf(G)) decreases.
When (G) G (G)) reaches minimum value 0, ((((G")) G) will definitely increase. Hence, the process of maximizing (()(""); )); (G)) can lead to the maximization of (ff(""): G) well. L
Lemma C.11. Given the essential view G of graph G and an encoder f. we have
(57)
Proof.
II(C))))-(((((CC))))))+++1111 I(G; Y) = -1(CC))1-11000))0---00000----
(58)
Due to the non-negativity of mutual information,
+(G 2 G:
(the non-negativity of I)
(59)
= G)))
27

---

According to Eq.
58 and
59
we get
+ ((000000111010111001111111111011
(60)
Thus,
(61)
Theorem C.12. According to Proposition 2 to maximizing [[f(G"); fG)). which could lead to the maximization of (ff(G)):Y)
optimizing the contrastive loss Coi (G', G) is equivalent
Proof. Minimizing the contrastive loss Lcr(G", G) is equivalent maximizing lower bound of the mutual information between the latent representations of two views of the graph, and can be viewed as one way of mutual information maximization between the latent representations (i.e., max (ff(G);; f(G)). Consequently, the optimization of (ci(G", G') is equivalent to maximizing I(f(G);; f(G)).
According to Lemma T(f(G*); ie,
C.10 we know that maximizing [(f(G*); ((G)) is equivalent to maximizing
max (J(G)) - max IJ(G")
(62)
According to Lemma
we have
(63)
Since
(64)
follows that
(
(65)
By combining Eq. 63 and Eq. (65
we obtain:
I(f(G));)) & I((G))
(66)
+I((();;))
Thus,
I < ((((')))
(67)
Since the Eq. (54) in Theorem C.9 essential view of graph G obtained by minimizing structural entropy (i.e., min H(G')), it follows that
we have already proven that T(G": G) = H(G"), and G" the
min [(G; G*) min H(G").
(68)
Thus,
max G
S max I((())):))
(69)
Therefore, minimizing the contrastive loss LCr(G*, G) is equivalent maximizing [[ At this point, I(f(G*); ); G) reaches its maximum, and I G) reaches its minimum, thereby maximizing I(f(G");
C.7 Proof of Theorem C.15
Definition C.13 (Graph Quotient Space). Define the equivalence 2r between two graphs Gi S G2 if G1, G2 cannot be distinguished by the 1-WL test. Define the quotient space g' = G
So every element in the quotient space, i.e., G' E g', is representative graph from family of graphs that cannot be distinguished by the 1-WL test. Note that our definition also allows attributed graphs
Definition C.14 (Probability Measures in g'). Define P& over the space g' such that (G' = Fo z G') for any G' g'. Further define Pg (G" Y') Pexx GG = G². Y Y'). Given GDA T(-) defined over G, define a distribution on g', (G') = EG-r, G = G*] for G' E g
28

---

Theorem C.15 (Bounds of Redundant and Essential Information). Suppose the encoder f is imple- mented by a GNN as powerful as the 1-WL test. Suppose G is countable space and thus G' is countable space, where z denotes equivalence (G1 ž G2 if G1 G2 cannot be distinguished by the 1-WI. test). Define P Y* P G', Y) and ('G") = Rauro (Tx (G) G'] for G" g. Then, the optimal f and G" to RedOUT satisfies:
1. I(G))) - -
(()()));)),
2. [()* G|) S miny [tt -(((()))) where t" (G) - = G*, ((C) ~ (G') (G.Y) ~ Paxy and (G', Pgrxy-
Proof. Because G and G' are countable, Pg and Pg: defined over countable sets and thus discrete distribution. Later we may call a function z(-) can distinguish two graphs G1. G2 if (G1) * (G2)..
Moreover, for notational simplicity, we consider the following definition. Because f is as powerful as the 1-WL. test. Then, for any two graphs G1, G2 9, G1 = G2, (G,) ('))).. We may
define a mapping over G', also denoted by f which simply satisfies (G' : (G), where G = G², and G E G and G' G
We first prove the statement i.e., the lower bound. Given G G (G*) ) is an injective deterministic mapping because of the injective f*. Therefore, we have
[(f(G)::)) = I(G";Y).
(70)
Given e' (G)) ('( (G")(())) is an injective deterministic mapping. Therefore, for any random variable Q
Ilf" [F(("(()))))==1("(()))
where G' ~ t GG).
Of course, we may set Q = So.
where (G', Y) ~ Poxx,, (G') =
(71)
Because of the data processing inequality 66 and (G) = EaNR (T = G'), we further have
1 1F
(72)
where (G', Y) ~ the data processing inequality (6)
" (G). Further because of
1((()))))
(73)
Combining Eq.
72
73
we have
I[f" (UFTC33)))1(((TC000)0000001CC000
min min Itn':)
(74)
which concludes the proof of the lower bound.
We next prove the statement 2, i.e., the upper bound. Recall that T' = EGNR (G) G*]
and 1'x (G') (G).
1(t" (C
=1("()))))++1("))" @ "T""
(75)
29

---

where (a) is because t' (G") Lo Y. (6) is because the data processing inequality [6]. Moreover,
because f could be as powerful as the 1-WL test and thus could be injective G' a.c. with respect
to the measure Pg.. Since f (G) = 1" (G") and (G") , (T(G) G*}.
-I(");)))((((((())))) (CCC)C))-((((VVVO/////OOUUUUUOO)
(76)
where ('()) ( (G)))
I(t"(G");)) = arg min / (t")"") Since T = arg miny [G" where (*))) ~ (G) and Eq. (7).. we have
(77)
Again, because f could be as powerful the 1-WL test, its counterpart defined over G', i.e., f must be injective over G' n Supp(Ecr (G'))) a.c. with respect to the measure Pg to achieve such mutual information maximization. Here, Supp(μ) defines the set where j has non-zero measure.
Because of the definition of TT* R (T (G) [ G*],
G' Supp(Barwzgppppp (T') g n Pupp(EGR,,ITT(T
(78)
Therefore, f is a.e. injective over G' (S and thus
(79)
Moreover, f cannot cannot distinguish more graphs in G than G' the power of f is limited by 1-WL test, thus,
I(f
=
(80)
Plugging Eq. (7). into Eq. 75p. we achieve
()) G|Y) S arg songii/((((cee [
I arg min -
min
(81)
where r'(G") ('))) = EG-r, [TG G' and t" (G') T (G') EG (G)
G*], which gives us the statement 1, which is the upper bound.
Enhancing Essential Information: statement of Theorem C.15 highlights the effectiveness of
ReGIB in capturing essential information. It implies that the essential information G is guaranteed to have at least as much mutual information with the ground-truth labels Y as the augmented representation (''",, which suggests that G* is highly informative with respect to the downstream task.
ii) Limiting Redundant Information: statement 2 of Theorem C.I5 establishes an upper bound on the
redundant information embedded the representations. This aligns with the GIB principle (Eq. (3) when 3 1). ensuring that the encoder f* captures only the necessary information from input graph G that relevant to the downstream task. The statement suggests that ReGIB is capable of producing representations with limited redundant information, thereby enhancing the overall efficiency of the representation learning process.
C.8 Proof of Instantiation for I(f(G))
According to Proposition
C.7 we have:
HGG)I
((G)) < Ep log
(82)
To specify the variational upper bound, we provide the proof for the instantiation [(G) as follows.
30

---

Optimal
Redundant
Fssential
I
G
Y
I(G)
(a) Vanilla GIB
(b) GTB with view ((G) involved
(c) ReGIB
Figure 10: Venn diagram of comparison between the basic GIB, GIB with random augmentation view, and proposed ReGIB. Note ReGIB captures the essential information and discards redundancy, wherein (c)
T(f(G);)) 1 + [(](G)); (GG), I T(f(G*);Y)
Proof. Since
(sim(u,))
IUUVV\Y) < EPW.YY
log N Di=1 esim((u,))
(83)
sim (u, )
sim(u, v) - log
Here, we give the definition of the conditional redundancy-Climinatee loss CORT:
(G G*) A
sim Zr) -log Ez eimm Zr)
(84)
Now, for Eq. we treat the similarity between Zr and Z given the predicted predicted label Y = softmax Z as an approximation the log- ligllikel log (()()))((G)) Y), and set
Q(f(G)))) (P((O)) cii (Z Zrr
(85)
where Z- are negative samples drawn from the conditional distribution P(J(G)
Thus, I(f(G*): Y) can be approximately instantiated as:
(U((G); (G))(
(86)
C.9 Further Comparison ReGIB and GIB with Random Augmentation Views
In this section, we provide a comparative analysis of ReGIB and GIB with random augmentation views from an argumentation perspective. Compared the standard GIB with random augmentation views (D> Figure a)), ReGIBB addresses the limitations of models pretrained solely on ID data. Such models often lack the generalization capability required for OOD data, which results in representations that contain both relevant and irrelevant information (D> Figure c))... For unsupervised tasks, models pretrained on ID data can leverage pseudo-labels Y obtained from softmax outputs to reduce dependence on ground-trun -tuth labels
As discussed previously, ID and OOD graphs can be distinguished by their unique structural character- isties. Through the proof of Theorem C.9 show that essential structural information embedded within the original graph and can be extracted by minimizing structural entropy to obtain the essential view G". Methods such as GOODAT (3 however, which use graph maskers identify subgraphs in test data similar to those in ID graphs. fundamentally rely on learnable graph augmentations. These augmentations may inadvertently alter the semantic information of substructures or lead informa- tion loss, compromising the reliability of OOD detection. Specifically, as shown in Figure b)) random augmentations on graph G can introduce redundant information captured by the pretrained model, making more difficult to extract the optimal and essential information.
31

---

Iterations
The original graph G
MERGE v2)
MERGEOs,
MERGE entire graph G
All nodes as leaves
Root node
Root node v,
Root node V,
Root node
14
Initialization coding tree
Coding tree after MERGE
Figure 11: Overview of MERGE to construct full-height binary coding tree.
Root mode v,
Root node
Root node v,
Root node
Coding tree after MERGE
DROP(y, 1)
DROP(,, V.
Final voding tree of
Figure 12: Overview of DROP to squeeze the height of coding tree to k.
Since well-trained GNNs generally perform well on ID graphs but tend to produce more random and unreliable predictions for unseen OOD graphs in the test data, their predictions fail identify distinctive structural information or recognize similar modifying structures. For graph data with specific structures, the intrinsic semantic information is encoded in the structure itself. Unlike f(G) which introduces random irrelevant information, G is hierarchical abstraction derived from the original graph structure, obtained by minimizing the structural entropy of G. This process preserves the essential structure without altering the semantic information. Therefore, the distinctive pattern of G serves as form of ground- truth information correct predictions on test graphs.
The primary objective of ReGIB is to obtain the distinctive structure G and to extract as much optimal and essential information possible based pseudo-labels while eliminating irrelevant redundancies. Thus, ReGIB can be considered a special case of GIB with random augmentation views. By placing t(G) entirely within the space of G in vanilla GIB, we derive ReGIB. In summary, ReGIB eliminates irrelevant redundancies introduced by random modifications, effectively simplifying the representation of the graph's 's intrinsic structure and extracting optimal essential information without adding unnecessary redundancies. In unlabeled OOD detection tasks and test-time settings that rely solely on test samples, ReGIB proves be more effective.
D Algorithms
To start with, we initialize a coding tree T by treating all nodes V as children of root node v,. The construction of the coding tree involves initially building full-height binary tree with all nodes as leaves and then optimizing this binary tree into fixed-height coding tree. Specifically, during step I, an iterative MERGE(15 v²) is performed with the goal of minimizing structural entropy to obtain a binary coding tree without height limitation. this way, selected leaf nodes are combined to form new community divisions with minimal structural entropy. Then, to compress height to specific k, DROP (m)) is leveraged to merge small divisions into larger ones, and thus the height of the coding tree is reduced, which is still following the structural entropy minimization strategy. Eventually, the coding tree with fixed height & and minimal structural entropy is obtained.
Definition D.1. Assuming Ea and Eo as two child nodes of root node Uy. the function MERGE v%) is defined as adding new node üj the child of v, and the parent of v. and Uy:
ch.children {Va. vb). Vy children = {1,} chi.clddnnnn
(87)
32

---

Cut
Cur
Root node V,
Root node V,
Root node V,
V
V/
Figure 13: The process of adding nodes and cutting edges to the corresponding coding tree.
Since merging nodes in the original graph via the operator MERGE(1; U2, 26) operator reduces the structural entropy of graph G, the pair of child nodes to be merged should be the one that maximizes the reduction in structural entropy, formally written as:
(Vay Ub) = argmaa (H' (G) ah (G) Vb E vr.children).
(88)
An overview of the MERGE operator is shown in Figure II To provide more detailed explanation of the coding tree construction process, we first revisit the definition structural entropy as follows:
H² -- E
ge+ log V+ET (V) vol(
vol
(89)
where 4r is node except for root node and also stands for a subset V,- E V, go, is the number of edges connecting nodes in and outside V,, w is the immediate predecessor of e, and (v, vol(u:)) and vV)(V) are the sum of degrees of nodes Ur, of and V, respectively. When two nodes are merged into new node (e.g., merging the pair (Va, 0z) into vy), the structural information of the new node must satisfy the following equations:
gu, Iv. + 9v, 2Cuutuuu vb). vol (u,) vol( + vol(v));
(90)
where Cut(va Va. 0b) denotes the number of edges cut between nodes when merging (Va: v6). Figure 13 illustrates the process of merging nodes in graph and adding nodes to the corresponding coding tree through an example.
Definition D.2. Given node Um and its parent node u in T. the operator DROP(v..) is defined as adding the children of um and itself to the child set of u
t children = t children cm.children.
(91)
Similarly, since creating node um through the DROP( operator also changes the structural entropy of graph G, the selection of the new node e. should aim to minimize the change structural entropy, written
argmiin(H Tm (C) H. (G) E T, Um o
V}
(92)
An overview of the DROP operator is shown in Figure 12 The construction of coding tree with
fixed height & primarily involves iterations through the two operators to obtain the minimum structural entropy, which is shown in Algorithm T
E
Experiment
E.
Dataset Description
For OOD detection, we employ pairs of datasets from two mainstream graph data benchmarks (i.e., TUDataset [4] and OGB (T] following GOOD-D (20). Specifically, select 8 pairs of molecular
33

---

Algorithm 1: Coding tree construction with height & via structural entropy minimization. EV; Specific height 1.
Input: undirected graph
Coding tree T with height k. Initialize coding tree with root node v, and nodes in V as its children;
Output:
// Step 1: full-height binary coding tree construction while (vj-children) > do
Select child node pair (Va.0%) <- Eq. 88
MERGE 1b);
end
// Step 2: binary coding tree squeeze to height k while (T) > k do
Select node Um <-Eq. 992
10
DROP (Um)
end
12 return coding tree T
Algorithm 2: Overall optimization process of RedOUT.
Input:
Test graph sample G; Pre-trained GNN encoder which is frozen; Coding tree encoder fe: Number of test-time training epochs E; Hyperparameters X.
Output: Optimized tree encoder fe: Predicted OOD score S.
Initialize parameters randomly;
Instantiation for Redundancy--liminnen Essential Information
Construct redundancy-eliminatee G* via structural entropy minimization <- Eq.
14
for i = 1,2,...., EE do
Obtain representations for original graph and coding tree, as Z S(G), Zr (e Instantiation for Lower Bound of (G
Calculate contrastive loss, as Loi -Z, ZT) + Eq 15
Instantiation for Upper Bound of f[
Calculate conditional redundancy-eliminated loss, as LoRi = I(Z, ZT + Eq. 16
10
Calculate the overall loss, C < Eq. (18):
11
Update parameter C by minimizing L and back-propagation:
12 end
datasets, pair protein datasets, and I pair of social network datasets. 90% of ID samples are used for training, and 10% of ID samples and the same number of OOD samples are integrated together for testing. The partitioning of samples for training, along with the division of ID and OOD samples for testing, follows GOOD-D (20). Detailed statistics of OOD detection datasets are compiled in Table Further detailed information about these datasets is categorized and described as follows.
E.1.1
Molecular Datasets
BZR [24] a dataset focused benzodiazepine receptor ligands, containing molecular structures and associated binding affinities. It is crucial for drug design and discovery, specifically for studying receptor-ligand interactions.
PTC-MR 24 reports the careinogenicity of 344 chemical compounds in male and female rats and includes 19 discrete labels. It is utilized for predicting the carcinogenic potential of chemical substances.
AIDS (24 contains data anti-HIV compounds, including their molecular structures and biological activities, serving as a valuable resource for the development anti-HIV drugs.
ENZYMES 24 a dataset consisting protein structures classified into enzyme types based their functionality. It is used for protein function prediction and enzyme classification.
COX2 24 comprises data on cyclooxygenase-2 inhibitors, which are compounds with anti- inflammatory properties. This dataset essential for the research and development of anti- inflammatory drugs.
34

---

Table 5: Statistics of OOD detection datasets.
Dataset Pair
Domain
#ID train
#ID test
#OOD test
BZR / COX2
Molecules
364
41
PTC-MR MUTAG
Molecules
309
35
35
AIDS DHFR
Molecules
1800
200
200
Tox21 SIDER
Molecules
7047
784
784
FreeSolv ToxxCatt
Molecules
577
65
BBBP / BACE
Molecules
1835
204
204
ClinTox LIPO
Molecules
1329
148
148
Esol MUV
Molecules
1015
113
113
ENZYMES PROTEINS
Proteins
540
60
60
IMDB-M IMDB-B
Social Networks
1350
150
150
Table 6: Further statistics of graph datasets.
Dataset
#Feature
#Graphs
Avg. Nodes
Avg. Edges
Avg. Deg.
ENZYMES
600
32.63
62.13
1.90
PROTEIN
1113
39.06
72.82
1.86
IMDB-M
1
1500
18.00
65.93
5.07
IMDB-B
1
1000
19.77
96.53
4.88
Tox21
9
7831
18.57
19.29
1.04
SIDER
9
1427
33.64
35.66
1.05
FreeSolv
9
642
8.72
8.38
0.96
ToxCast
9
8576
18.78
19.26
1.03
BBBP
9
2039
24.06
25.95
1.08
BACE
9
1513
34.08
35.91
1.08
ClinTox
1477
26.15
27.88
LIPO
9
4200
27.04
29.11
1.09
Esol
9
1128
13.28
14.08
1.03
MUV
9
93087
24.23
26.27
1.08
BZR
405
35.75
38.14
1.07
COX2
467
41.22
44.52
1.05
PTC PTC_MR
344
14.28
15.04
1.03
MUTAG
188
17.93
19.79
1.10
MUTAG 24 has seven kinds of graphs derived from 188 mutagenic aromatic and heteroaromatic nitro compounds. It is used for studying the mutagenicity of chemical substances.
DHFR (24 includes dihydrofolate reductase inhibitors, important in the development of antibac- terial and anticancer drugs, aiding in drug discovery and medicinal chemistry research.
PROTEINS (4] contains data on protein structures and their functionalities. Nodes represent secondary structure elements (SSEs), and edges connect neighboring elements the amino acid sequence or 3D space. This dataset is used for protein structure prediction and functional analysis.
Tox21 [ is dataset containing toxicity data 12 biological targets, which has been used in the 2014 Tox21 Data Challenge and includes nuclear receptors and stress response pathways.
BBBP 1 2 includes records of whether compound has the permeability property of pene- trating the blood blood-brain barrier, essential for the design of central nervous system drugs.
contains clinical toxicity data on variety of drug compounds, classifying drugs approved by the FDA and those that have failed clinical trials for toxicity reasons.
Clin'Tox [1] 26 8]
ToxCast II 29 includes high-throughput screening data on the toxicity of chemical substances, with measurements based over 600 in vitro screenings. This dataset is used for large-scale toxicity assessment and environmental health research.
contains information drug side effects, grouped into 27 system organ classes, also known as the Side Effect Resource. utilized for predicting drug side effects and improving drug safety profiles.
SIDER || 14
35

---

Table 7: Statisties of anomaly detection datasets.
Dataset Pair
Domain
#ID train
#ID test
#OOD test
BZR
Molecules
69
17
64
AIDS
Molecules
1280
320
80
COX2
Molecules
81
21
73
NCII
Molecules
1646
411
411
DHFR
Molecules
368
59
ENZYMES
Protcins
400
100
20
PROTEINS
Proteins
360
90
133
DD
Proteins
139
IMDB-B
Social Networks
400
100
100
REDDIT-B
Social Networks
800
200
200
includes qualitative binding results for set of inhibitors of human 3-secretase 1, which are potential treatments for Alzheimer's 's disease. This dataset is used in Alzheimer's disease research and drug development.
BACE III 3
FreeSolv [T]] includes data the hydration free energy of small molecules, used for molecular
dynamics simulations and solubility studies.
Esol [11] contains data on the aqueous solubility of compounds, used for studying compound solubility and drug design.
LIPO includes data on the lipophilicity chemical compounds. used for studying the partitioning of compounds between water and oil phases, which is important in drug design.
MUV [1 includes data the activity of compounds from virtual screening, designed for validation of virtual screening techniques.
HIV contains experimentally measured abilities to inhibit HIV replication.
E.1.2
Protein Datasets
PROTEINS [24] contains data on protein structures and their functionalities. Nodes represent secondary structure elements (SSEs), and edges connect neighboring elements the amino acid sequence or 3D space. This dataset is used for protein structure prediction and functional analysis.
ENZYMES 24 is dataset consisting of protein structures classified into enzyme types based on their functionality. It is used for protein function prediction and enzyme classification.
E.1.3 Social Network Datasets
IMDB-BINARY 24 (abbreviated as IMDB-B) is derived from the collaboration of movie set. Each graph consists of actors actresses, with edges representing their cooperation in movie. The label corresponds to movie's genre. This dataset used for movie classification and recommendation system studies.
IMDE-MULTI 24
(abbreviated as IMDB-M) consists of graphs derived from movie collabora- tions which is similar to BIDDY,,NARY, but with multi-class labels. It is utilized in multi-class classification tasks in social network analysis.
also conduct experiments on anomaly detection (AD) settings, where 10 datasets from TU- Dataset [24] are used for evaluation. Following the setting in GlocalKD [21]. the samples in the minority class or real anomalous class are viewed as anomalies, while the rest are viewed as normal data. Similar to [21] 51], only normal data used for model training. Detailed statistics of anomaly detection datasets are compiled in Table
E.2
Baseline Details
We evaluate the performance of RedOUT by comparing it against 18 state-of-the-art baseline methods. A detailed discussion of these methods is provided below.
36

---

Non-deep Two-step Methods. These methods first extract representations using hand-crafted graph kernels and then apply classical OOD detectors. We adopt the Weisfeiler-Lehmee (WL) kernel [32] and the propagation kernel (PK) 25 to obtain graph-level representations. On top
of these, we apply local outlier factor (I.OF) one-class SVM (OCSVM) 22 and isolation
forest (iF) 18] for OOD detection.
Deep Two-step Methods. These approaches employ self-supervised graph learning techniques generate expressive embeddings, followed by separate OOD detector. We two represen- tative graph contrastive learning (GCL) methods, InfoGraph 34 and GraphCL 49] to learn
representations. For detection, adopt iF [18] and Mahalanobis distance (MD) which have demonstrated effectiveness prior work.
30 52 both of
End-to-end Training Methods. These methods jointly optimize the representation learning and OOD detection objective within a unified framework. We consider GOOD-D 20 as the primary SOTA method in our comparison, which is a GCL-based method that has shown strong performance in unsupervised OOD detection tasks. We also compare our approach with two graph anomaly detection methods that are trained in an end-to-end manner. OCGIN [51], which uses a GIN encoder trained with support vector data description (SVDD) loss, and GLocalKD [2]] which identifies graph anomalies using local-global knowledge distillation.
Test-time and Data-centric Methods. A typical test-time training method is GTrans 12 which adapts representations via test-time contrastive alignment. Since GTrans is not explicitly designed for graph OOD detection, its loss value is utilized as the OOD score. We conduct comparisons based on the experimental results from GOODAT (39. Data-centric methods leverage well-trained GNN models to fine-tune OOD detectors for identifying OOD samples. These methods mainly include the following approaches: AAGOD [9] employs a graph adaptive amplifier module, which is integrated into well-trained GNN to facilitate graph OOD detection. Specifically, AAGOD corresponding to distinct OOD evaluation methods. GOODAT [3] is the first directly partition test data into two subgraphs using data-centric techniques in a test-time setting, training a plug-and and-play graph masker.
exists in two versions: AAGOD GINg + and AAGOD-GIN,
E.3 Configurations
We conduct the experiments with:
Operating System: Ubuntu 20.04 LTS.
CPU: Intel(R) Xeon(R) Gold 6240 CPU @ 2.60GHz, 256GB RAM.
GPU: Tesla V100 PCIe 32GB GPU.
Software: Python 3.7, Pytorch 1.8, CUDA 11.0, and Petoecc-Geometrie 2.0.1.
E.4
Additional Experiments Using Structural Entropy as Distinct Metric
By minimizing structural entropy, the structural uncertainty of the graph is reduced, which aids in capturing essential information and identifying distinet patterns between ID and OOD samples. As shown in the score density plots in Figure [(e] by minimizing structural entropy, the overlap between the representations of ID and OOD graph samples is significantly reduced.
To clarify, we do not treat structural entropy solely as distinct values, but construct a coding tree that reduces redundancy and retains distinctive parts. To further illustrate the performance of using structural entropy directly as distinct values for the OOD detection task, we conduct additional experiments using the 95% range of structural entropy from ID training graphs for OOD detection on test samples. The AUC results shown in Table reveal that using structural entropy directly as a metric causes a significant performance drop. Thus, we can analyze that structural entropy only measures information but does not capture structural differences, and cannot be directly used as an indicator of substantial information. In contrast, our method instantiates substantial information through the encoding tree with minimized structural entropy, achieving good performance.
37

---

Table 8: Additional results using structural entropy the distinct metric, compared with RedOUT, for OOD detection in terms of AUC (%, mean + std).
ID data
BZR COX2
PTC-MR MUTAG
AIDS DHER
ENZYMES PROTEIN
IMDB-M
Tox21 SIDER
FreeSols ToxCast
BRBP BACE
ClinTix LIPO
0OD data
IMDB B
MUV
51.710060
50.1010.68
54.8310.77
1.10
51.360058
47.9711.36
08.9710.81
15,07.0.66
52.39.0.00
SEGO
96.66=0.91
05.0220.94
99,4840.111
64.4244955
0027=092
0666=0082
9095*1193
87,55++0.13
78.99#2811
34.59=0954
RedOUT
95.06.0.:44
91/6511.66
99,9810.16
66.75.12.2
79.54.10722
71.67.0.50
92.97.10.84
92,6010.23
86.56.10.76
95.00....54
E,5
Comparison Results of RedOUT with Structural Entropy Guided End-to-end Training
SEGO [10 is a recent approach that leverages structural entropy for unsupervised OOD detection. In this section, we conduct detailed comparison between our method and SEGO to highlight their methodological differences and performance characteristics.
Difference in Settings. Firstly, the key differences between our RedOUT and SEGO lie in their settings: RedOUT is designed to improve OOD detection at test-time without modifying rre-trained models or requiring training data, whereas SEGO is an end-to-end unsupervised method that trains from seratch. It is evident that the test-time setting is more practical for real-world applications.
Difference in Techniques. Regarding technical details, although both RedOUT and SEGO leverage structural entropy to construct coding trees, their implementations and focal points differ significantly. Specifically, SEGO merely discovers the phenomenon that minimizing structural entropy is beneficial for the OOD detection task. In contrast, our RedOUT's s main contribution is the first to extend GIB to redundancy-awan disentanglement by proposing ReGIB, which effectively eliminates redundancy and captures essential information through theoretically grounded upper and lower bound optimization.
Superior Performance of RedOUT. We further conduct a comparison experiment between RedOUT and SEGO, as shown in Table where our method outperforms SEGO on 8 out of 10 ID/OOD dataset pairs.
E.6 Efficiency Analysis and Runtime Comparison
Given graph G (V,&) the time complexity of coding tree construction is (h((E)) log [V] + +ID). in which h is the height of coding tree after the first step. In general, the coding tree tends to be balanced in the process of structural entropy minimization, thus, / will be around log | Furthermore, [V], thus the runtime almost scales linearly
a graph generally has more edges than nodes, i.e., [8] >>
in the number of edges.
Discussion on the Runtime Comparison. We compared RedOUT with GOODAT 39 in terms of inference time on test data and the time consumption for coding tree construction (abbreviated as Tree Constr.). .. For deep learning methods under other settings, we select the best-performin methods, GOOD-D and GraphCL-MD. Shown Table 9 the time overhead of RedOUT is comparable with the baseline while achieving enhanced performance. Note that coding tree construction is a one-time preprocessing step, it does not impact the efficiency of test-time inference.
The difference in speed is related to the graph density. Specifically, since GOODAT relies on training a graph masker on test samples to separate subgraphs, the iterative optimization of the masker and representation learn- ing of the two subgraphs become fre- quent and time-consuming when deal- ing with large amount of edges in
Table 9: Time consumption on pre-training, coding tree con- struction and test-time OOD detection.
ID dataset OOD dataset
B7R COX2
PTC-MR MUTAG
ENZYMES PROTEIN
IMDR-M M IMDB-B
FreeSolv ToxCast
Pre-training
53.21
40.99
30.18
8.12
70.84
Tree Constr. (8)
0.14
0.04
0.15
0.09
0.38
GraphCL-MD (8)
27.94
21.71
14.43
10.64
40.02
GOOD-D (s)
323.36
320.77
137.5
33.59
356.44
dense graphs. In contrast, RedOUT does not involve a masking design, and the preprocessing step of coding tree construction is non-trainable. For dense social network graphs such as IMDB-M/B, the higher the graph density, the more pronounced the efficiency advantage of RedOUT compared to GOODAT. Detailed dataset statistics can be found in Table
GOODAT (s)
6.86
3.55
5.24
0.87
4.81
RedOUT (8)
7.51
5.65
2.88
0.28
7.51
38

---

Discussion on the Efficiency of Trainable Parameters. We further analyze the number of pa- rameters required during training for both RedOUT and GOODAT on specific datasets. RedOUT only updates the parameters of tree encoder. Assuming the encoder has / layers, with each layer consisting of two-layer MI.P with hidden dimension hid, the total number of trainable parameters is approximately 2 x 1 x hid x hid. In contrast, GOODATJupdater both a feature masker and an edge masker, with a parameter size of approximately match_size. x (n X d + 2 x m). where n is the number of nodes, m is the number of edges, and d is the feature dimension. The edge count is doubled because reciprocal edges are automatically added for undirected graphs.
As shown in Table 6 dataset pairs such as IMDB-M/IMD 110-MM/MMBBBB -B and ENZYME//PROTEINS have higher average node and edge counts. Taking IMDB-M/IMDE B as an example, whose average number of nodes is about 19, and the average number of edges is about 81. With a batch size of 128, comparison, RedOUT uses up to a 5-layer encoder (note that the analysis in Section 5.5 shows that 5 layers are not strictly necessary for optimal performance) with hidden dimension 32, requiring 2 x 32 32 = 10, 240 trainable parameters. Thus, for dense graphs with more edges on average. RedOUT requires fewer parameters and less runtime. However, for sparser graphs such as PTC_ MTC_MR/MUTAG, GOODAT's parameter count is 128x (16 x x 17) 6, 400, which is smaller than that of RedOUT. Therefore, GOODAT is more efficient on sparse graphs.
GOODAT requires around 128 (19 x 1 + x 81) = 23, 168 parameters.
E.7
Additional Results of Parameter Study on OOD Detection
We illustrate additional results of hyperparameter sensitivity analysis on OOD detection datasets in We provide additional analysis here.
Figure [4] and Figure 15
AIDS:DHER
IMDB IMDB-M/MMDB-B
BBBPBBCC
Esa
101.0
AUC (%)
AUC (%)
80.0
92.0
AUIC (%)
95.0
AUC
90.0
99.0
75.0
90.0
Figure 14: Additional results of the natural hicrarchy of graph on OOD detection.
AIDSIDHIRR
McMMDB
BBBPBBAC
EsoUMUV
$0.0
93.0
100.0
75.0
AliC-(0) (h6)
92.0
94.0
91.0
76.0
93.0
92.0
14 1s:33
1e-02
1e
1s:04
1e:0
02
11
14:04
1s:33
1e42
1c
1c:4
1e:03
1z:02
1e-01
Figure 15: Additional results of the sensitivity of hyperparameter À on OOD detection.
Height k of Graph's Natural Hierarchy OOD Detection. We observe that the impact of coding tree height on OOD detection performance in Figure 14 varies slightly across different datasets. Specificallyy, height k can be interpreted as the number of hierarchical aggregations of essential information. Corresponding to the number of layers in GNNs, the range of l values we selected is from 2 to 5. The optimal value of &s differs due to the varying graph structures of different datasets, yet it fluctuates within a reasonable range. The current coding tree optimization algorithm relies on the fixed height applied to the whole dataset, without considering the diversity among samples. One potential direction for improving our method is to incorporate an adaptive coding tree height better extract essential structures in graphs, which we leave as our future work.
Sensitivity Analysis of X on OOD Detection. To analyze the sensitivity of X for RedOUT, we alter the value from le-04 to 1. Results in Figure demonstratte the performance is sensitive to changes in X and contains a reasonable range across different datasets.
SSouree code of GOODAT is available at httpppps//ggguuu..o//////////e/e
39

---

Table 10: Anomaly detection results in terms of AUC (,, mean = std). results are highlighted with bold and underline, respectively.
The best and runner-up
PROTEINS-GUl
ENZYMES
BZR
NC11
IMDB-B
REDENT-
PK-OCSVM
40.40:1.92
23.7::266
50:7014.30
47.91-3.76
46.811531
50.21:7911
68.9013.06
40:00-1.15 1.18
50.25:55 10
45.6812.34
49.66
10.6
Pi-4F
68. 20:2012.55
11:30:2.1
51.4412.87
52.11:90
55.3236.188
50.5-2.05
11:32:2.41
50.58:113 1.8
50.90:331 17
66.721-3.42
54.07
9.1
WL-OCSVM
51.35 21.35-24.25
55.24:206
50.12:345
50.38-3.13
47.9924099
50654:1. 12
56.08:55 19
09.3142.35
50.44
9.7
61.36-1254
52.46.3.30
50.27:10.34
70.3121000
30.411100
20:30:0.0
43.3610.32
24.89:2244
58.75
78.0613005
40.23:3.05
65.011147
53.55.5055
72.2721.83
71.98:1.11
60.19:8.0
75.3313.55
Gl Glacall0
17 17.3045515
V1:376-4.19
59. 59.17-12.07
M1.11.5.24
04. 18-88-2.3 3M
52.09-3
77.5547762
68/00
43
GOOD-Duug
74,74:2225
61.33:455
94.0921.75
62.71=3.38
74.482-91
00.462:2.44
19.5621.62 72.222132
65.4921 05
57.87241.35
71.29
388
GOOD-D
11 138
90.38 0.69
18.1615.15
62A5-1814
71.54-9119
62:12-2211
65 6588-0177 75
83.-711.7 7.4
12.26
2.2
GTass
0016655005
38.02:663 24
54.5721911
61.15-2.77
119778815
53 57
76.71422.5
41.4262.10 16
45.3423377 75
02. 09.714:2.31
58.25
85
GOODAT
77.222237
52.33.4.74
5055399
61.52=2.6 56
04.77833.77
9999999.6
77.6322.55
45.96622.22
65
90:31160.35
ReSOUT
76.0933.33
77.44:664
66.336061
45.51:4955
59.6234772
144955
746113345
21.3481:22
67.45:00.99
89 89.511:2.54
77.01
TROTTINS
ENZYMES
AIPS
R/R
80.0
10.0
ATCC/50
AtTC-00 (50
Attr
70.0
Aur
$0.0
400
850
OXX2
NET1
IMDI--I1
15.0
Afre.00
68.0
50.5
60.0
ADC
70.3
66.0
65.0
Figure 16: The natural hierarchy of graph on AD datasets.
ABDS
B2R
$1.2
70.0
200
52
+0.0
COX2
NCII
14D0-B
REDOrrO
70.8
75.3
60.3
210
65.2
1650
1e02
1+04
1e:1 1x-22
(e:8)
1x:0
1e42
1e03 1n40 Inf0
16:35 1e:0
10:2
Figure 17: The sensitivity of hyperparameter À on AD datasets.
E.8
Additional Results of Anomaly Detection Performance
To investigate if RedOUT generalize to the anomaly detection setting [51] 21). we conduct experiments on 10 datasets following the benchmark in GLocalKD and GOOD-D 21 20), where only normal data used for model training. The results are shown in Table 10 From the results, find that our method achieves the best performance on 5 out 10 datasets and runner-up performance on 3 datasets, with an average improvement of 4.75% over the SOTA. This demonstrates that RedOUT indeed has a strong capability to transfer to anomaly detection tasks. Thus, we can conclude that capturing common patterns in the anomaly detection setting crucial, which directly reflected in the performance.
E.9 Additional Results of Parameter Study on Anomaly Detection
We also illustrate additional results of hyperparameter sensitivity analysis on anomaly detection datasets in Figure 16 and Figure 17
We provide additional analysis here.
Height of Graph's Natural Hierarchy on Anomaly Detection. We also conducted experiments on the impact of the coding tree height & on 10 anomaly detection datasets, as shown in Figure 16 We observe that the impact of coding tree height on anomaly detection performance varies slightly across different datasets.
Sensitivity Analysis of on Anomaly Detection. To analyze the sensitivity of for RedOUT, alter the value from lc-04 to 1. The AUC w.t. different selections of À is plotted in Figure 17
40

---

Figure 18: Visualizing of the essential structure based on the coding tree preserved by RedOUT on BZR/COX2, where the first row is BZR and the second row is COX2.
Results demonstrate the performance is sensitive to changes in À and contains a reasonable range across different datasets.
E.10
Additional Case Study ID/OOD Dataset Pairs
In this additional case study, we further demonstrate the effectiveness our method in extracting the intrinsic structural features of graphs. We visualize the graph structures extracted by the encoding tree based on minimizing structural entropy on 10 pairs ID/OOD datasets, as shown from Figure [8 to Figure 27
In these visualizations, the colored nodes represent different communities based on the subtree structures of the coding tree. The edges marked with different colors are those involved in the merging process during the construction of the coding tree, with each color indicating a different subtree partition. We provide additional analysis as follows. RedOUT effectively extracts the distinct intrinsic structures of ID and OOD graph data in datasets related to molccules, proteins, and social networks, which is crucial for OOD detection. For graphs in social networks, which typically exhibit high connectivity and edge density, incorporating node and edge attributes implies huge potential to enhance the model's representational capacity, beyond the essential structural information currently extract. However, the current IMDB-M//MDB-B datasets do not incorporate node or edge attributes. This promising direction that inspires As illustrated in Figure 22 although the similarity in social network structures leads to suboptimal performance on the MDDBMM/MDDB-B datasets, still captures the differences intrinsic structures. Moreover, our method successfully extracts distinctive structures in the other datasets.
take deep exploration in our future work.
F Broader Impacts
Graph OOD detection contributes to improving the robustness of GNNs in safety-critical applications and scientific discovery tasks such as drug design and protein interaction analysis. It is important to ensure that such techniques are used to enhance reliability rather than to analyze user behavior without proper authorization.
41

---

Figure 19: Visualizing of the essential structure based on the coding tree preserved by RedOUT on PIC-MR/MUTAG, where the first row is PTC-MR and the second row is MUTAG.
Figure 20: Visualizing of the essential structure based the coding tree preserved by RedOUT on AIDS/DHFR, where the first row is AIDS and the second row is DHFR.
Figure 21: Visualizing of the essential structure based on the coding tree preserved by RedOUT on ENZYMES/POOTEIN, where the first row is ENZYMES and the second row is PROTEIN.
42

---

Figure 22: Visualizing of the essential structure based on the coding tree preserved by RedOUT on JIDB-M//MDB-B where the first row is IMDB-M and the second row is IMDB-B.
Figure 23: Visualizing of the essential structure based the coding tree preserved by RedOUT on Tox21/SIDER, where the first row is Tox21 and the second row is SIDER.
Figure 24: Visualizing of the essential structure based on the coding tree preserved by RedOUT on FreeSolv/Toxcast, where the first row is FreeSolv and the second row is Toxcast.
43

---

Figure 25: Visualizing of the essential structure based on the coding tree preserved by RedOUT on BBBP/BACE, where the first row is BBBP and the second row is BACE.
Figure 26: Visualizing of the essential structure based the coding tree preserved by RedOUT on ClinTox/LIPO, where the first row is ClinTox and the second row LIPO.
Figure 27: Visualizing of the essential structure based on the coding tree preserved by RedOUT on Esol/MUV, where the first row is Esol and the second row is MUV.
44


Reviews:
[{"review_id": "3XEcR2aSAe", "reviewer": "Reviewer_mdJJ", "summary": "This paper proposes RedOUT, a redundancy-aware framework for test-time graph OOD detection. The method introduces a Redundancy-aware Graph Information Bottleneck , which decomposes graph information into essential components and redundant noise. By minimizing structural entropy on a coding tree constructed from test graphs, RedOUT extracts distinctive substructures critical for OOD detection while preserving semantic consistency. The framework operates as a post-hoc, unsupervised test-time algorithm without retraining, achieving substantial improvements on several graph benchmarks. Experimental results demonstrate sota performance  on both OOD detection and anomaly detection tasks.", "questions": "1. How robust is RedOUT to incorrect pseudo-labels at test time, especially on highly uncertain OOD samples? Could this reliance on pseudo-labels amplify noise or bias in the essential view extraction?\n2. Since RedOUT mainly improves on molecular graph datasets, what specific characteristics of social network graphs limit its performance? Could incorporating node/edge attributes (besides structure) help mitigate this?\n3. Given the strong reliance on structural entropy minimization, how sensitive is the framework to the choice of coding tree height k in unseen datasets or new application scenarios? Could an adaptive or data-driven selection of k improve stability?", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. Novel formulation of redundancy-aware test-time OOD detection for graphs, filling a gap in current data-centric, post-hoc graph OOD detection literature.\n2. The introduction of ReGIB with theoretical bounds and entropy minimization provides a well-motivated, principled approach for isolating essential information.\n3. The ablation studies and parameter sensitivity analyses are thorough and help clarify the contribution of each component.\n4. The framework does not require model retraining, which makes it practical for real-world applications.\n\nWeaknesses:\n1. The performance improvement of RedOUT on the IMDB datasets appears to be relatively limited. Could the authors provide an explanation for this phenomenon?\n2. The reliance on pseudo-labels during test-time introduces potential error accumulation that is not deeply analyzed\n3. The time complexity of the coding tree construction is relatively high (O(h|E|log|V|)), which may affect scalability on large graphs.", "was_revised": true, "final_justification": "The authors have addressed most of my concerns, after reviewing the other reviewers' comments, I have decided to maintain my original score.", "rebuttal": "We sincerely appreciate your valuable comments and are happy to address your concerns as follows:\n\n**W1 & Q2:** An explanation for the relatively limited performance improvement on the IMDB dataset. Could incorporating node/edge attributes (besides structure) help?\n\nThank you for the insightful suggestion. In Section 4.5, through a case study, we investigate that the suboptimal performance mainly stems from the highly similar structural semantic information and the shared data source, which makes it challenging even for existing methods to effectively distinguish OOD samples. \n\nFor graphs in social networks, which typically exhibit high connectivity and edge density, incorporating node and edge attributes implies huge potential to enhance the model’s representational capacity, beyond the essential structural information we currently extract. \nHowever, the current IMDB-B/M datasets do not incorporate node or edge attributes. This is a promising direction that inspires us to take a deep exploration in our future work. We will include further analysis in the revision.\n\n\n---\n**W2 & Q1.1:** The impact of incorrect pseudo-labels at test time on RedOUT, especially for highly uncertain OOD samples\n\nThank you for the valuable question.\nWhile the pseudo-labels predicted by pre-trained model may contain errors when encountering highly uncertain OOD samples, such errors do not compromise the effectiveness of our redundancy removal mechanism. Specifically, we leverage ReGIB to disentangle the conditional redundant information associated with pseudo-labels in Eq. (6), and optimize the upper bound in Eq. (8) to minimize $I(f(G ^ *); f(G) \\mid \\tilde{Y})$.\n\nIn the general case, we decompose the learned representation as $f(G) \\rightarrow{R_1 + Y_G}$ and $f(G ^ *) \\rightarrow{R_2 + Y_G}$, where $R_{1/2}$ denotes label-irrelevant redundant information, and $Y_G$ denotes label-related information.\nMinimizing $I(f(G ^ *); f(G) \\mid \\tilde{Y})$ is equivalent to minimizing $I((R_1+Y_G);(R_2+Y_G) \\mid \\tilde{Y}) \\rightarrow \\min I(R_1; R_2)$.\n\nIf the pseudo-label $\\tilde{Y}$ predicted by the pre-trained model is incorrect, then $f(G) \\mid \\tilde{Y} \\rightarrow \\bar{R}_1 + \\bar{Y}_G$ and $f(G ^ *) \\mid \\tilde{Y} \\rightarrow \\bar{R}\\_2 + \\bar{Y}\\_G$, \nwhere $ \\bar{R}\\_{1/2}$ denotes the residual irrelevant information after removing the wrongly associated label part, and $\\bar{Y}\\_G$ similarly denotes the remaining label-related information. \nIn this case, minimizing $I(f(G ^ *); f(G) \\mid \\tilde{Y})$ becomes $\\min I(\\bar{R}_1 + \\bar{Y}_G ; \\bar{R}_2 + \\bar{Y}_G) \\rightarrow \\min I(\\bar{R}_1 ; \\bar{R}_2)$.\n\nHence, the optimization still targets the irrelevant redundancy and the direction of our objective remains unchanged. Therefore, the effectiveness of our method in removing irrelevant redundancy is not compromised.\n\n---\n**W3:** Scalability of coding tree construction on large graphs\n\nThanks for your suggestions. We provide a scalability efficiency analysis of our method in Appendix E7. As shown in Figure 13, the results illustrate that from smaller scales to the OGB datasets (e.g., ogbg-code2), the runtime and memory usage scale up nearly linearly with the number of nodes. Furthermore, as shown in Table 10, the time overhead introduced by coding tree construction is negligible compared to the cost of model pretraining and test-time detection.\n\n---\n**Q1.2:** Could the reliance on pseudo-labels amplify noise or bias in the essential view extraction?\n\n Thanks for the question. The extraction of essential information does not depend on pseudo-labels and thus is not subject to such bias. It is derived independently by minimizing the structure entropy in Eq. (12). We will include the additional explanation in the revision.\n\n---\n**Q3:** How sensitive is the framework to the choice of coding tree height $k$ in unseen datasets or new application scenarios? Could an adaptive or data-driven selection of k improve stability?\n\nThanks for the question. The impact of the coding tree height $k$ on performance is analyzed in Figure 4. We observe that across 5 out of 6 datasets, our method outperforms the baselines regardless of the specific choice of $k$. Notably, compared with GOODAT, which also operates in a test-time setting, our method achieves superior performance across all 6 datasets. This further confirms the effectiveness of our proposed ReGIB in extracting essential structures and removing redundancy, irrespective of the coding tree depth. \n\nAdditionally, in light of the variability of test-time samples, an adaptive or data-driven selection of $k$ shows great potential for improving stability. We leave this exploration for future work.\n\n\nWe once again thank you for your constructive feedback and valuable suggestions. We will carefully address all the raised points in the revised version."}, {"review_id": "ezPL56afB4", "reviewer": "Reviewer_HHWR", "summary": "The paper proposes RedOUT, a framework for test-time graph out-of-distribution (OOD) detection that addresses the challenge of structural redundancy in graph data. It introduces the Redundancy-aware Graph Information Bottleneck (ReGIB) to separate essential information from irrelevant redundancy by minimizing structural entropy, which helps in effectively distinguishing between in-distribution and out-of-distribution graph samples. The framework demonstrates superior performance over state-of-the-art baselines through extensive experiments on real-world datasets, highlighting its capability to capture essential structural information in graphs.", "questions": "1. It lacks clear introduction of the baseline to analyze the contribution of this work. \n2. The performance of RedOUT is sensitive to hyperparameters such as the coding tree height k and the trade-off parameter λ. While the paper provides a reasonable range for these parameters, it lacks detailed analysis on how to select optimal values for different datasets, which may affect the method's practical usability.\n3. The coding tree construction process involves structural entropy minimization, which may incur higher computational costs for large-scale graphs.", "limitations": "1. The coding tree construction process involves structural entropy minimization, which may incur higher computational costs for large-scale graphs.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strength:\n1. By minimizing structural entropy, it effectively extracts essential structural information from graphs while eliminating redundancy, offering a new perspective for test-time graph OOD detection.\n2. Extensive experiments on multiple real-world graph datasets demonstrate that RedOUT outperforms state-of-the-art baselines, achieving an average improvement of 6.7% in unsupervised OOD detection tasks. \n3. The paper provides theoretical analysis and proofs for ReGIB, such as deriving upper and lower bounds for essential and redundant information optimization.\n4. The Paper is well written and easy to follow. \n\nWeakness:\n1. It lacks clear introduction of the baseline to analyze the contribution of this work. \n2. The performance of RedOUT is sensitive to hyperparameters such as the coding tree height k and the trade-off parameter λ. While the paper provides a reasonable range for these parameters, it lacks detailed analysis on how to select optimal values for different datasets, which may affect the method's practical usability.\n3. The coding tree construction process involves structural entropy minimization, which may incur higher computational costs for large-scale graphs.", "was_revised": true, "final_justification": "The paper proposes RedOUT, a framework for test-time graph out-of-distribution (OOD) detection that addresses the challenge of structural redundancy in graph data. It introduces the Redundancy-aware Graph Information Bottleneck (ReGIB) to separate essential information from irrelevant redundancy by minimizing structural entropy, which helps in effectively distinguishing between in-distribution and out-of-distribution graph samples. The framework demonstrates superior performance over state-of-the-art baselines through extensive experiments on real-world datasets, highlighting its capability to capture essential structural information in graphs.\nBy minimizing structural entropy, it effectively extracts essential structural information from graphs while eliminating redundancy, offering a new perspective for test-time graph OOD detection.\nExtensive experiments on multiple real-world graph datasets demonstrate that RedOUT outperforms state-of-the-art baselines, achieving an average improvement of 6.7% in unsupervised OOD detection tasks. \nThe paper provides theoretical analysis and proofs for ReGIB, such as deriving upper and lower bounds for essential and redundant information optimization.\nThe Paper is well written and easy to follow.", "rebuttal": "We sincerely appreciate your thoughtful comments and address your comments and suggestions point by point below.\n\n**Q1:** Further analysis of baselines and the contribution of this work\n\nThank you for the suggestion.\nIn Appendix E2, we provide a detailed categorization and discussion of the 18 baseline methods considered in our comparison. These baselines are grouped into 4 categories: Non-deep Two-step Methods, Deep Two-step Methods, End-to-end Training Methods, and Test-time and Data-centric Methods. Additional discussion and comparison with related works are provided in Appendix B. We summarize the key differences and contributions below.\n\nNon-deep two-step methods, deep two-step methods, and end-to-end training methods all rely on training data to modify the parameters of GNN models. Data-centric methods such as AAGOD do not alter pre-trained GNN parameters but still require access to ID training data for post-hoc data augmentation.\nIn contrast, our method is designed for the test-time setting, aiming to improve OOD detection performance without modifying pre-trained models or requiring any access to training data. Although Gtrans and GOODAT are also test-time methods, they requires additional training of graph transformation functions or graph maskers. In our case, the extraction of essential structure is achieved via structure entropy minimization, which is a training-free optimization procedure.\nWe would like to further emphasize that the core contribution of this work lies in the first to extend GIB framework to redundancy-aware disentanglement. Specifically, we propose ReGIB, which effectively removes redundant information and extracts essential structure by jointly optimizing theoretical upper and lower bounds.\n\nThanks again and we will include further analysis in the revised version.\n\n---\n**Q2:** How to select optimal values for different datasets\n\nThank you for the insightful question.\nFor the hyperparameter $k$, while the performance may exhibit slight variations, we observe that RedOUT consistently achieves strong results, as illustrated in Figure 4. Specifically, on 5 out of 6 datasets, RedOUT outperforms all baselines regardless of the choice of $k$. Furthermore, compared with GOODAT (which also operates in test-time setting), our method achieves superior performance on all 6 datasets. These results demonstrate that ReGIB can effectively extract essential structural information and eliminate irrelevant redundancy, regardless of the depth of  coding tree.\nFor the hyperparameter $\\lambda$, we empirically find that values in the range from 1e-4 to 1e-2 lead to consistently effective performance.\nThis robustness reduces the need for extensive hyperparameter tuning, making our method well-suited for practical deployment in real-world scenarios.\n\n---\n**Q3:** Analysis of the computational overhead of coding tree construction on large-scale graphs\n\nThank you for the suggestion. We provide a detailed analysis of the scaling efficiency of our method in Appendix E7. As shown in Figure 13, the results indicate that from small-scale graphs to larger ones such as the OGB datasets (e.g., ogbg-code2), the runtime and memory consumption of coding tree construction increase nearly linearly with the number of nodes.\n\nWe once again thank you for your constructive feedback and valuable suggestions. We will carefully address all the raised points in the revised version."}, {"review_id": "wKVVfjjQ6t", "reviewer": "Reviewer_tiWp", "summary": "This paper proposes to construct a coding tree based on a well-trained GNN to reduce the redundancy in the graph structure and use the construction loss as a criterion for OOD detection.", "questions": "* Since the proposed method uses the optimized loss as an OOD detection score, how does the method identify a sample as an OOD sample? Is there a manually set threshold that separates IID and OOD samples?\n\n* While the paper provides time complexity analysis, could the comparison between the proposed method and other baseline methods be provided? Constructing and optimizing a coding tree can be a time-consuming process. It would be beneficial to have more details about optimizing the coding tree on a sample provided.\n\nI look forward to the authors' response and will adjust my rating based on the rebuttal.", "limitations": "The authors have discussed the limitation that the proposed method mainly focuses on graph-level detection. However, I encourage the authors to further discuss the limitations of the proposed method.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strength**:\n* The proposed method seems novel. This paper proposes to detect OOD samples by constructing a coding tree that minimizes the structural entropy.\n\n* The paper provides sufficient experimental results to verify the effectiveness and sensitivity to hyperparameter settings of the proposed method.\n\n**Weakness**:\n* Some parts of the paper are hard to follow. For example, Figure 2 contains \"?\", which makes it difficult to understand. Sec. 3 introduces the ReGIB and the objective for coding tree construction, but lacks a straightforward explanation on the choice of using the construction loss as the OOD detection score.\n\n* The details of how the OOD samples are detected are vague. While constructing the coding tree provides a loss that is used as an OOD detection score, the method for separating OOD samples from IID samples seems unclear. If the OOD samples are detected when the loss exceeds a certain threshold, the good performance of the proposed method may stem from a well-tuned threshold on the benchmark datasets. \n\n* The paper could benefit from more empirical details on the coding tree construction and a time consumption comparison between the proposed method and other baseline methods.", "was_revised": true, "final_justification": "This paper proposes a new OOD detection method using a coding tree. The proposed method seems novel. My initial concerns has been addressed in the rebuttal, therefore I am increasing my rating.", "rebuttal": "We sincerely appreciate your valuable comments and will reply to all these concerns individually.\n\n**W1.1:** Figure 2 contains \"?\", which makes it difficult to understand\n\nWe would like to clarify that Figure 2 in our paper does not contain \"?\" symbols. The issue you mentioned may result from incomplete image rendering in the browser. We recommend downloading the paper and viewing it locally using Adobe Reader to ensure correct visualization.\n\n---\n**W1.2 & W2.1:** Section 3 introduces ReGIB and the objective for coding tree construction, but lacks a straightforward explanation on the choice of using the construction loss as the OOD detection score\n\nThank you for the question. The construction of coding tree does not introduce any new loss function. Instead, we use structural entropy as the optimization metric for coding tree construction (see Eq. (12) and (14)). \nMoreover, we would like to clarify that we do not use structural entropy as the OOD score, and the OOD score is actually computed based on Eq. (18).\n\n---\n**W2.2:** If the OOD samples are detected when the loss exceeds a certain threshold, the good performance of the proposed method may stem from a well-tuned threshold on the benchmark datasets\n\nThank you for the comment. The strong performance of our method does not stem from a well-tuned threshold.\nWe follow the same evaluation protocol as GOOD-D and GOODAT, where the AUC metric is computed using `auc = sklearn.metrics.roc_auc_score(y, ood_score)`.\nSpecifically, `y` denotes the binary ground-truth labels, and `ood_score` represents the confidence score for predicting a sample as OOD. This score is a continuous value that can be ranked across samples. AUC is computed by ranking all samples according to their `ood_score`, and then calculating the corresponding true positive rate (TPR) and false positive rate (FPR) over the full range of score distributions to construct the ROC curve (with FPR on the x-axis and TPR on the y-axis). The AUC is the area under this ROC curve, with a larger value indicating stronger discrimination ability. The effectiveness of these methods, including ours, is thus evaluated independently of any manually selected threshold.\n\n---\n**W3 & Q2.2:** The paper could benefit from more empirical details on the coding tree construction and a time consumption comparison between the proposed method and other baseline methods\n\nThank you for pointing this out. We provide detailed illustrations and explanations of the coding tree construction process in Appendix D and Figures 10 to 12 of the paper.\nMoreover, coding tree construction, as well as the proposed RedOUT method, is not time-consuming. In Appendix E7, Table 10 compares the time consumption of pretraining, coding tree construction, and test-time OOD detection.\n\nWe additionally provide a comparison of time consumption with other baselines in the table below. For deep learning methods under other settings, we select the best-performing methods, GOODD and GraphCL-MD, for reference. \n\n|ID|BZR| PTC-MR|ENZYMES| IMDB-M|FreeSolv|\n|-|-|-|-|-|-|\n|OOD| COX2   | MUTAG  | PROTEIN | IMDB-B | ToxCast  |\n|Coding Tree Construction (s) | 0.14   | 0.04   | 0.15    | 0.09   | 0.38     |\n|GraphCL-MD (s)| 27.94  | 21.71  | 14.43   | 10.64  | 40.02|\n|GOODD (s)| 323.36 | 320.77 | 137.5   | 33.59  | 356.44|\n|GOODAT (s)| 6.86   | 3.55   | 5.24    | 0.87   | 4.81|\n|RedOUT (s)| 7.51   | 5.65   | 2.88    | 0.28   | 7.51|\n\nNote that the official implementation of AAGOD could not run successfully in our experimental environment. Several issues have also been reported by other users on its GitHub repository and remains unresolved.\n\n---\n**Q1:** Since the proposed method uses the optimized loss as an OOD detection score, how does the method identify a sample as an OOD sample? Is there a manually set threshold that separates IID and OOD samples?\n\nThank you for the insightful question. A global evaluation metric AUC is used to assess a model’s ability to distinguish between ID and OOD samples overall. In practical applications, we can estimate a decision threshold based on the ID distribution observed in the pretraining dataset. For example, a score threshold that corresponds to a 5% false positive rate (FPR) on ID samples can be chosen. This threshold can then be used at test time to decide whether a new input is OOD. Notably, the selection of threshold does not affect the evaluation of the model’s OOD detection performance, that is, the threshold selection does not affect the computation of AUC metric.\n\n---\n**Q2.1:** While the paper provides time complexity analysis, could the comparison between the proposed method and other baseline methods be provided?\n\nThank you for the valuable question. A detailed analysis and comparison of computational complexity between our proposed RedOUT and GOODAT is provided on page 31 in Appendix E7.\nIn addition, we provide a comparative analysis of time complexity for our proposed method and several other representative baselines as follows:\n\n- **RedOUT** only optimizes a tree encoder with $L$ layers, each being a two-layer MLP with hidden dimension $h$. The total time complexity is $O(L(mh + nh^2))$ per graph.\n- **GOOD-D** updates two GIN encoders with $L$ layers and hidden size $h$. The forward pass complexity is $O(L(mh + nh^2))$ per graph. An additional $O(nh)$ cost arises from the group-space clustering, resulting in $O(L(mh + nh^2)+nh)$ overall.\n- **GTrans** performs optimization over node features and edge structure based on a fixed backbone. The per-graph time complexity is $O(L(mh + nh^2)+md + nd^2 + B'\\log B')$, where $B'$ is the number of candidate edge flips.\n- **AAGOD** introduces an auxiliary augmentation scorer alongside the main GNN model with $L$ layers and hidden dimension $h$ that scoring $K$ augmentations per graph. The total time complexity is $O(L(mh + nh^2)+K(nd+m))$.\n- **GOODAT** introduces two masking modules (feature and edge maskers). The time complexity per graph is $O(L(mh + nh^2)+nd + m)$, as it applies learnable masks over node features and edge connections.\n\nOverall, the time complexity of our proposed RedOUT is comparable to that of other baselines.\n\n---\n**Limitation:** The authors have discussed the limitation that the proposed method mainly focuses on graph-level detection. However, I encourage the authors to further discuss the limitations of the proposed method.\n\nThank you for the suggestion. The current coding tree optimization algorithm relies on the fixed height applied to the whole dataset, without considering the diversity among samples. One potential direction for improving our method is to incorporate an adaptive coding tree height to better extract essential structures in graphs, which we leave as our future work. We will expand the discussion of limitations in the revised version.\n\nWe once again thank you for your constructive feedback and valuable suggestions. We will carefully address all the raised points in the revised version."}]

Author rebuttal:

Meta-review: The paper proposes RedOUT, a redundancy-aware framework for test-time graph Out-of-Distribution (OOD) detection. The core contribution is the introduction of the Redundancy-aware Graph Information Bottleneck (ReGIB), which decomposes graph information into essential components and redundant noise by minimizing structural entropy on a coding tree constructed from test graphs. This approach enables the extraction of distinctive substructures important for OOD detection while preserving semantic consistency. The framework operates as a post-hoc, unsupervised test-time algorithm without retraining and demonstrates substantial improvements over state-of-the-art baselines on several graph benchmarks.

**Strengths**

The strengths include its novel formulation of redundancy-aware test-time OOD detection for graphs, the introduction of ReGIB with theoretical bounds and entropy minimization, thorough ablation studies and parameter sensitivity analyses, and the framework's practicality due to not requiring model retraining. Additionally, the paper offers a new perspective on test-time graph OOD detection by addressing structural redundancy in graph data.

**Weaknesses**

The weaknesses include limited performance improvement on certain datasets (e.g., IMDB), potential error accumulation from relying on pseudo-labels during test-time, and high time complexity of coding tree construction (O(h|E|log|V|)), which may affect scalability on large graphs. Furthermore, some reviewers noted poor clarity in parts of the paper, lack of straightforward explanation for using construction loss as an OOD detection score, and vagueness in details of OOD sample detection.

**Summary**

During the rebuttal period, the authors addressed several concerns raised by reviewers, including explanations for limited performance improvement on certain datasets, impact of incorrect pseudo-labels at test time, and scalability of coding tree construction on large graphs. The authors also provided additional analyses, such as comparisons with baseline methods and discussions on selecting optimal values for different datasets. Reviewers appreciated the rebuttal, with one reviewer increasing their rating after finding that the authors had addressed most of their concerns. While some reviewers maintained their original scores, they acknowledged the authors' efforts to address concerns and recognized the paper's technical solidity despite some limitations.

Overall, while not working on an exciting new topic, the paper presents a decent contribution. Based on the reviews and rebuttal, I recommend accepting this paper. The authors have addressed most of the reviewers' concerns, providing additional explanations and analyses to clarify the methodology and results. The paper's strengths, including its novelty, thorough experiments, and good performance on benchmark datasets, outweigh its weaknesses. While some limitations remain, such as sensitivity to hyperparameters and potential computational costs, the authors have acknowledged these and plan to discuss them further in a revised version.
Decision: Accept (poster)