Transitivity Recovering Decompositions: Interpretable and Robust Fine-Grained Relationships
Authors: Abhra Chaudhuri
Massimiliano Mancini
Zeynep Akata
Anjan Dutta
Venue: NeurIPS 2023 poster (2023)
Keywords: Interpretability
Robustness
Fine-Grained Representation Learning
Graph Theory
Information Theory
TL;DR: We propose an approach for learning robust and interpretable equivalents of abstract multi-view relational representations by showing that such abstractions are nothing but a way of encoding the transitive relationships across views.

Abstract: Recent advances in fine-grained representation learning leverage local-to-global (emergent) relationships for achieving state-of-the-art results. The relational representations relied upon by such methods, however, are abstract. We aim to deconstruct this abstraction by expressing them as interpretable graphs over image views. We begin by theoretically showing that abstract relational representations are nothing but a way of recovering transitive relationships among local views. Based on this, we design Transitivity Recovering Decompositions (TRD), a graph-space search algorithm that identifies interpretable equivalents of abstract emergent relationships at both instance and class levels, and with no post-hoc computations. We additionally show that TRD is provably robust to noisy views, with empirical evidence also supporting this finding. The latter allows TRD to perform at par or even better than the state-of-the-art, while being fully interpretable. Implementation is available at https://github.com/abhrac/trd.

Transitivity Recovering Decompositions: Interpretable and Robust Fine-Grained Relationships
Abhra Chaudhuri!-6
Massimiliano Mancini²
Zeynep Akata Anjan Dutta
University of Exeter
2 University of Trento
University of Tübingen
4 MPI for Informatics
The Alan Turing Institute
University of Surrey
Abstract
Recent advances in fine-grained representation learning leverage local-to-global (emergent) relationships for achieving state-of-the-ard results. The relational rep- resentations relied upon by such methods, however, are abstract. We aim deconstruct this abstraction by expressing them as interpretable graphs over image views. We begin by theoretically showing that abstract relational representations are nothing but a way of recovering transitive relationships among local views. Based this, design Transitivity Recovering Decompositions (TRD), graph- space search algorithm that identifies interpretable equivalents abstract emergent relationships both instance and class levels, and with no post-hoc computations. We additionally show that TRD is provably robust to noisy views, with empirical evidence also supporting this finding. The latter allows TRD perform at par even better than the state-of-the-art. while being fully interpretable. Implementation is available sectps://githnn com/ com/abbrac/trr
Introduction
Identifying discriminative object parts (local views) has traditionally served as a powerful approach for learning fine-grained representations [95, 85 43]. Isolated local views, however, miss out on the
larger, general structure of the object, and hence, need be considered in conjunction with the global view for tasks like fine-grained visual categorization (FGVC) [94]. Additionally, the way in which local views combine form the global view (local-to-globes identified as being crucial for distinguishing between classes that share the same set of parts, but differ only in the way the parts relate to each other [32 97 10 [2). However, representations
emergent relationships
[59] has been
produced by state-of-the-an art approaches that leverage the emergent relationships are encoded in an abstract fashion for instance, through the summary embeddings of transformers
or via aggregations on outputs from a GNN 197, (7). This makes room for the following question that we aim to answer through this work: how can we make such abstract relational representations more human--undersandddbee Although there several existing works that generate explanations for localized, fine-grained visual features 11 78 36 63,, providing interpretations for abstract representations obtained for discriminative, emergent relationships still remains unaddressed.
Illustrated Figure [ we propose to make existing relational representations interpretable through bypassing their abstractions, and expressing all computations in terms of graph over image views, both at the level of the image as well as that of the class (termed class prexy, a generalized representa- tion of class). At the class level, this takes the form of what we call a Concept Graph: generalized relational representation of the salient concepts across all instances of that class. We use graphs, as they naturally interpretable model of relational interactions for variety of tasks [8 [ 46), allowing us to visualize entities (e.g., object parts, salient features), and their relationships.
Abhra Chaudhuri (ac l 151 (exeterr.c.uk) is the corresponding author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Bally
Head
Tril
Forti
Notey Subgraph
Informative Subgraph
Globol
Inttel Image Graph Dupul)
Gruph of Ginnne Cress View Beletionskips (Latent)
Class Proxy (Consep)) Graph (Output)
Figure I: Instead of learning representations of emergent relationships that are abstract aggregations of views, our method deconstructs the input, latent, and the class representation (proxy) spaces into graphs, thereby ensuring that all stages along the inference path are interpretable.
We theoretically answer the posed question by introducing the notion of transitivity (Definition 3 for identifying subsets of local views that strongly influence the global view. We then show that nothing but way of encoding transitivity, and design Transitivity Recovering Decompositions (TRD), an algorithm that decomposes both input images and output classes into graphs over views by recovering transitive cross- view relationships. Through the process of transitivity recovery (Section TRD identifies maximally informative subgraphs that co-occur in the instance and the concept (class) graphs. providing end-to-end relational transparency. In practice, we implement TRD by optimizing a GNN to match graph-based representation of the input image to the concept graph of corresponding class (through minimizing the Hausdorff Edit Distance between the two). The input image graph is obtained by decomposing the image into its constituent views 10 84 94], and connecting complementary sets of views. The concept graph is obtained by performing online clustering the node and edge embeddings of the training instances the corresponding class. The process is detailed in Section 3.3
the relational abstractions
We also show that TRD is provably robust to noisy views in the input image (local views that do not / negatively contribute the downstream task [T... We perform careful empirical validations under various noise injection models to confirm that this is indeed the case in practice. The robustness allows TRD always retain, and occasionally, even boost performance across small, medium, and large scale FGVC benchmarks, circumventing a known trade-off in the explainability literature [31 73 23 37
Finally, the TRD interpretations are ante-hoc- graphs encoding the learned relationships are produced as part of the inference process, requiring no post-hoc GNN explainers [8 92 34 68, 99)
In summary, with the purpose of bringing interpretability to abstract relational representations, make the following contributions - (1) show the existence of graphs that are equivalent to abstract local-to- -looal relational representations, and derive their information theoretic and topological properties; (2) design TRD, a provably robust algorithm that generates such graphs in an ante-hoc manner, incorporating transparency into the relationship computation pipeline at both instance and class levels; (3) extensive experiments demonstrating not only the achieved interpretability and robustness, but also state-of-the-arr performance on benchmark FGVC datasets.
2 Related Work
Fine-grained visual categorization: Learning localized image features 2 96 47 with extensions
exploiting the relationship between multiple images and between network layers (52) were shown be foundational for FGVC. Strong inductive biases like normalized object poses 6 87 and data-driven methods like deep metric learning [14] were used to tackle the high intra-class and low inter-class variations. Unsupervised bast- models leveraged CNN feature map activations or identified discriminative sequences of parts 4 Novel ways of training CNNs for FGVC included boosting [55), kernel pooling [15), and channel masking [19]. Vision transformers, with
35 94
their ability to learn localized features, had also shown great promise in FGVC 81 29 50
FGVC
interpretability has so far focused on the contribution of individual parts
20 However, the
usefulness of emergent relationships for learning fine- fine-graine grainrd visual features demonstrated by

---

83 97 9 [0]. Our method gets beyond the abstractions inherent in such approaches, and presents a fully transparent pipeline by expressing all computations terms of graphs representing relationships. at both the instance and the class-level.
Relation modeling in deep learning: Relationships between entities serve an important source of semantic information as has been demonstrated in graph representation learning [72 [8] deep
reinforcement learning [93], question answering [67]. object detection [33], knowledge distillation
[60] and few-shot learning 77. While the importance of learning relationships between different
views of an image was demonstrated in the self-supervised context [ IC] showed how relational representations themselves can be leveraged for tasks like FGVC. However, existing works that leverage relational information for representation learning typically (1) model all possible ways the local views can combine to form the global view through transformer. and distill out the information about the most optimal combination in the summary embedding [9 TQ], or (2) model the underlying relations through GNN, but performing an aggregation on its outputs 127 977. Both (1) and (2) produce rector-valued outputs, and such, cannot be decoded in a straightforward way to get understanding of what the underlying emergent relationships between views are. This lack of transparency is what we refer to as "abstract". The above set of methods exhibit this abstraction not only at the instance, but at the class-level as well, which also appear as vector-valued embeddings. On the contrary, an interpretable relationship encoder should be able to produce graphs encoding relationships in the input, intermediate, and output spaces, while also representing class as relationships among concepts, instead of single vectors that summarize information about emergence. This interpretability is precisely what we aim to achieve through this work.
Explainability for Graph Neural Networks: GNNExplainer [88] was the first framework that proposed explaining GNN predictions by identifying maximally informative subgraphs and subset of features that influence its predictions. This idea was extended in [92 through exploring subgraphs via
Monte-Carlo tree search and identifying the most informative ones based their Shapley values [69] However, all such methods inherently provided either local 88
M
68 or global explanations [90],
but not both. To address this issue, PGExplainer [51] presented parameterized approach to provide generalized, class-level explanations for GNNs, while [2] obtained multi ouult--raineed explanations based on the pre- pre-training (global) and fine-tuning (local) paradigm. [48] proposed GNN explanation approach from a causal perspective, which led to better generalization and faster inference. On the other hand, 3 improved explanation robustness by modeling decision regions induced by similar graphs, while ensuring counterfactuality. Although ViG (27) presents an algorithm for representing images graph of its views, it exhibits abstract computation pipeline lacking explainability. A further discussion on this is presented in Appendix IA Also, generating explanations for graph metric-spaces 99 45 remains unexplored, which we aim to address through this work.
3 Transitivity Recovering Decompositions
Our methodology is designed around three central theorems (i) Theorem [ shows the existence
of semantically equivalent graphs for every abstract representation of emergent relationships, (ii)
Theorem 2 establishes an information theoretic criterion for identifying such a graph, and (iii)
Theorem 3 shows how transitivity recovering functions can guide the search for candidate solutions that satisty the above criterion. Additionally, Theorem formalizes the robustness of transitivity recovering functions to noisy views. Due to space constraints, we defer all proofs to the Appendix A.9
X with categorical label y Y from FGVC task. Let g = (x) and Il = [1 12, .......,, 1+] = cx(x) be the global and set of local views of an image x respectively, jointly denoted as = {g] LL, where c2 and et are cropping functions applied on x to obtain such views. Let f be semantically consistent, relation-agnoste
Preliminaries:
Consider an image
encoder (Appendices A.4 3 and maps it to latent space representation z E R", where n is the
A.7 that takes as input representation dimensionality. Specifically, the representations of the global view g and local views IL obtained from ff are then denoted by Zy f(g) and Z {1( 1 L} = {Zı, Ziz ... Zi,) respectively, together denoted as Z, {zy Zi. Aiz.... Zie }. Let E be function that encodes the relationships r E R between the global (g) and the set of local (I.) views. DiNo [9] and Relational Proxies [10] can be considered as candidate implementations for Ç. Lett G be set of graphs [(W, [E,, Fuy FF ), (V, E2, FFg, (FFz)...) where the nodes in each graph constitute of the view set V. and the edge set E, P(V x V), where P denotes the power set. | [P(V x V)). meaning
3

---

that G is the set of all possible graph topologies with V as the set of nodes. The node features Fv, and the edge features Fr, R
3.1 Decomposing Relational Representations
Definition (Semantic Relevance Graph). A graph 9. of image views where each view-pair is connected by an edge with strength proportional to their joint relevance in forming the semantic label y of the image. Formally, the weight of an edge Es., connecting v, and V is proportional to y.
Intuitively, Es., is measure of how well the two views pair together as compatible puzzle pieces in depicting the central concept the image.
Theorem 1. For relational representation that minimizes the information gap I(x: y Zv),, there exists a metric space (M, d) that defines Semantic Relevance Graph such that:
d(zz: y) 8 A d(zz, 8
E: R
SCHR
r = E(p(Zi), ((Z;) d(r, 8
where M E RR, sem and denote semantically consistent transformations and distance metrics respectively, & Zy - M, and 5 is some finite, empirical bound on semantic distance.
Intuition: The theorem says that, even if z; and 2, individually cannot encode anymore semantic information, the metric space (M, d) encodes their relational semantics via its distance function d. Assuming the theorem to be false would mean that the outputs of the aggregation do not allow for distance computation that is semantically meaningful, and hence, there is no source from which r (the relational embedding) can be learned. This would imply that either (i) the information gap (Appendix (.2) does not exist, which is false, because f is a relation-agnostic encoder, or (ii) all available metric spaces are relation-aue aggiostic and hence, the information gap would always persist. The latter is again in contrary to what is shown in Appendix [A.6] which derives the necessary and sufficient conditions for a model to bridge the information gap. Thus, (M, d) defines G. with weights 1 l/d(p((v)) ip( (V))) x I (v,,,;y), y), where P V + M.
Corollary 1.1 (Proxy Concept Graph). Proxies also be represented by graphs.
Intuition: Since (M, d) is equipped with semantically relevant distance function, the hypersphere enclosing locality/cluster of local/global view node embeddings can be identified as a semantic relevance neighborhood. The centers of such hyperspheres can be considered for each such view, generalizing some salient concept of class. The centers of each such view cluster can then act as the nodes of a proxy/concept graph, connected by edges, that are also obtained similar manner by clustering the instance edge embeddings.
proxy representation
Theorem The graph G" underlying a member of G with maximal label information. Formally,
g arg max (G GEG
Intuition: The label information 7(x, y) can be factorized into relation-agnostic and relation-aware components (Appendix [A.2p. The node embeddings in G" already capture the relation component (being derived from f). From the implication in Theorem I we know that given the node embeddings, & is able to reduce further uncertainty about the label by joint observation of view pairs (or in other words, edges in G*), Hence must be relation-aware, as the relation-agnosti component already captured by f. Thus, G", which obtained as a composition of f and &, must be sufficient representation of x (Appendices and the amount of label information that a representation can encode (Appendix A.3). g" is the graph that satisfies the condition in the theorem. In the section below, show that the way to obtain G* from is by recovering transitive relationships among local views.
and A.3). Since sufficiency is the upper-bound on
3.2 Transitivity Recovery
Definition (Emergence). The degree to which a set of local views (V1, Vz) contributes towards forming the global view. It can be quantified as [ vkgg). g).

---

Align
Global View
Grop: Encoder
Leemalte Bilti Cost
Hundedf Drstanoe
Local Views
Enedwrant
Align
Cordiont
Complementarly Gogéls
Semanti Relevatre Grapht
Prasy I Concept Crophs
Figure 2: The TRD pipeline: We begin by computing Complementarity Graph (Ge) on the view embeddings obtained from f. The Graph Encoder derives the Semantic Relevance Graph (G.) through transitivity recovery on G.. We perform a class-level clustering the instance node and edge embeddings, producing a proxy graph, representing the salient concepts of a class and their interrelationship.. The sufficiency of 9, guaranteed by minimizing Hausdorff distance with its proxy graph.
Definition 3 (Transitivity). Local views V1. V2, and Vy are transitively related iff. when any two view pairs have high contribution towards emergence, the third pair also has a high contribution. Formally.
T(v.v;;)) > 7 ((vyva:)) > T(v.va: ?
where (i.j.h) E {1, and y is some threshold for emergence. A function (pv) is said to be transitivity recovering if the transitivity between V1, V2. and V3 can, some way, be inferred from the output space of This helps us quantify the transitivity of emergent relationships across partially overlapping sets of views.
Theorem 3. A function vp(z) that reduces the uncertainty gly2x): about the emergent relationships among the set of views can define G. by being transitivity recovering.
Reducing the uncertainty about transitivity among the of views equivalent reducing the uncertainty about the emergent relationships, and hence, bridging the information gap. If v1, V2. and V3 are transitively related, then would imply that, at most, only one of the three views (v,) is semantically relevant, and the other two (v,, V&) are not. This leads to a degenerate form of emergence. Thus, transitivity is the key property the graph space that filters out such degenerate subsets in IL, helping identify view triplets where all the elements contribute towards emergence. A further discussion can be found in Appendix IT Now, we know that relational information must be leveraged to learn sufficient representation. So, for sufficiency, a classifier operating in the graph space must leverage transitivity to match instances and proxies. transitivity in G is equivalent to the relational information r E R". Thus, the explanation graph G* a maximal MI member G obtained by applying a transitivity recovering transformation on the Complementarity Graph.
Intuition:
the proof, we hence show that
3.3 Generating Interpretable Relational Representations
Depicted in Figure 2 the core idea behind TRD is to ensure relational transparency by expressing all computations lcading to classification on graph of image views (Theorem all the way up to the class-proxy, by decomposing the latter into a concept graph (Corollary I.I We ensure the sufficiency (Theorem 2b of the instance and proxy graphs through transitivity recovery (Theorem by Hausdorff Edit Distance minimization.
We start by obtaining relational- aggossic representations Z, from the input image x by encoding each of its views v E V as f(v). We then obtain Complementarity Graph G. E G with node features Fv = Zv, and edge strengths inversely proportional to the value of the mutual information between the local view embeddings T(2,, 2,) that the edge connects. Specifically, instantiate the edge features F& as learnalee n-dimensional vectors, all with the same value of
Complementarity Graph:
5

---

1//z:- -zyl. This particular choice of calculating the edge weights is valid under the assumption that f is a semantically consistent function. Intuitively, local views with low mutual information (MI) are complementary to each other, while ones with high MI have lot of redundancy. The inductive bias behind the construction of such a graph is that, strengthening the connections among the complementary pairs suppresses the flow of redundant information during message passing, thereby reducing the search space in G for finding G The global view g, however, is connected to all the local-views with uniform edge weight of 1". This is because the local-to-global emergent information, i.e., / (I.lj...; :.g........) g), is what we want the model to discover through the learning process, and hence, should not incorporate it as inductive bias
Semantic Relevance Graph:
We compute the Semantic Relevance Graph G. by propagating Ge through Graph Attention Network (GAT) [77]. The node embeddings obtained from the GAT correspond the (z() in our theorems. We ensure that yp is transitivity recovering by minimizing the Learnable Hausdorff Edit Distance between the instance and the proxy graphs (Corollary [.T]. which known to take into account the degree of local-to-globe transitivity for dissimilarity computation [64] Below, we discuss this process in further detail.
We obtain the proxy / concept graph for each class via an online clustering of the Semantic Relevance node and edge embeddings (s (z), go. respectively) of the train-set instances of that class, using the Sinkhorn- SinkhornKKnopp algorithm [6 We set the number of node clusters to be equal to [V.. The number of edge clusters (connecting the node clusters) is equal to | 1)/2. Note that this the case because all the graphs throughout our pipeline are complete. Based on our theory of transitivity recovery, sets of semantically relevant nodes should form cliques in the semantic relevance and proxy graphs, and remain disconnected from the irrelevant ones by learning an edge weight of O We denote the set of class proxy graphs by P = (Gp,, GPa: 9p, where & is the number of classes.
Proxy / Concept Graph:
Inference and Learning objective: To recover end-to-end explainability, we need to avoid converting the instance and the proxy graphs to abstract vector-valued embeddings in R all times. For this purpose, we perform matching between Ge and Gp PP via a graph kernel 222. This kernel trick helps us bypass the computation of the abstract relationship & G - R and perform the distance computation directly in G, using only the graph-base decompositions, and thereby keeping the full pipeline end-to-end explainable.
We choose to the Graph Edit Distance (GED)
kernel [58] Although computing GED
has been proven to be NP-Complete (79), quadratic time Hausdorff Edit Distance (HED) [25] and learning- based approximations [65] have been shown to be of practical use. However, such approximations are rather coarse-grained, as they are either based on linearity assumptions [65] or consider only the substitution operations [25 Learnable (L)-HED 64 introduced two additional learnable costs for node insertions and deletions using a GNN, thereby making it a more accurate approximation. We observe that our o already performs the job of the encoder prefix in L-HED (Appendix 12).). Thus, we simply apply a fully connected MLP head e M + R with shared weights on the pzz) embeddings and the vertices of Gp E to compute the node insertion and deletion costs. Thus, in our case, L-HED takes the following form:
h(G., Gp) = Σ min v) VEG, LuEs.
Σ min c(u, v)
(1)
ueg, VES,
([)(,,) for deletions (u + 8),
c(u, v) =
[[)(,)]. for insertions (E - v),
- ||1/,, for substitutions,
where a 1/(2 and is the empty node 644. We use h(.--) as distance metric for the Proxy Anchor Loss 39, which forms our final learning objective, satisfying Theorem 2 Below we discuss how transitivity recovery additionally guarantees robustness to noisy views.
3.4 Robustness
Let DD be the data distribution over X x Y. Consider a sample x E X composed of views V = (V1, V2,..., v&} with label y Y. A view
V is said to be noisy if label(v) # y 13] The
Graph kernels, in general, help bypass mappings G + H. where H. is the Hilbert space p2

---

Comnee Tom
Sonty Albetros
Figure 3: Sample TRD explanations on CUB. Top: 8 nearest neighbors (columns) of the top-2 proxy nodes / concepts (rows) with highest emergence (Definition 2). Bottom: Instance (global view with green border) and proxy (global view with blue border) explanation graphs constructed using the top-6 nodes (nearest train set neighbor for the proxy nodes) with highest emergence. The edge-weights are Lg-norms of the edge embeddings (best visible on screen with zooming).
fraction of noisy views for given sample is denoted by n. Let f be classifier that minimizes the empirical risk of the mapping f(x) + in the ideal noise-free setting. Let / be the set of noisy views in with topology r". Let V V 8/7 be the set of noise free (and hence, transitively related Theorem 3 views with topology T". Recall that G is the optimal graph of V satisfying the sufficiency criterion in Theorem 2 and Gp E P is its proxy graph.
Theorem 4. In the representation space of y,, the uncertainty in estimating the topology T" of is exponentially greater in the error rate e, than the uncertainty in estimating the topology T of V*
Intuition: This theorem is based on the fact the number of topologies that a set of noisy views can assume, is exponentially more (in the desired error rate) to what can be assumed by set of transitive views. Since &p explicitly designed be transitivity recovering, making predictions using y based on noisy views would go directly against its optimization objective of reducing the output entropy (due to the exponentially larger family of topologies to choose from). So, to minimize the uncertainty in Equation ( ip would always make predictions based on transitive views, disregarding all noisy views in the process, satisfying the formal requirement of robustness (Definition 4). In other words, the following property of TRD allowed us to arrive at this result the structural priors that have on the transitive subgraphs make them the most optimal candidates for reducing the prediction uncertainty, relative to the isolated subgraphs of noisy views which do not exhibit such regularities.
4 Experiments
4.1 Experimental Settings & Datasets
Implementation Details: For obtaining the global view, we follow 84 94 by selecting the smallest bounding box containing the largest connected component of the thresholded final layer feature map obtained from an ImageNet- [17 pre-trained ResNet50 [00, which we also use as the relation-agnostic encoder f. The global view is resized to 224 224. We then obtain 64 local views by randomly cropping 28 28 regions within the global crop and resizing them to 224 224. We 8-layer Graph Attention Network (GAT) (177), with 4 attention heads in each hidden layer, and normalized via GraphNorm 77 to obtain the Semantic Relevance Graph. We train TRD for 1000 epochs using the Adam optimizer, an initial learning rate of 0.005 (decayed by a factor of 0.1 every 100 epochs), with a weight decay of 5 x 10 4, We generally followed [77] 10 for choosing the above settings. We implement TRD with single NVIDIA GeForce RTX 3090 GPU, 8-core Intel Xeon processor, and 32 GBs of RAM.
Datasets: To verify the generalizability and scalability of our method, we evaluate it on small, medium and large-scale FGVC benchmarks. We perform small-scale evaluation on the Soy and Cotton Cultivar datasets (89), while we choose FGVC Aircraft [53], Stanford Cars [2], CUB (80).

---

and NA Birds 75 for medium scale evaluation. For large-scale evaluation, we choose the iNaturalist dataset (6), which has over 675K train set and 182K test set images.
4.2 Interpretability & RRobusnesss
Figure shows sample explanations obtained using TRD on the CUB dataset. The top rows represent proxy nodes (concepts), and the columns represent the 8 nearest neighbors of the corresponding proxy nodes, which is highly consistent across concepts and classes. In the bottom are instance and proxy explanation graphs (top-6 nodes with highest emergence) from very limilar-looking but different classes. For the proxies, the nearest train set neighbors to the node embeddings are visualized. Even with similar appearance, the graphs have very different structures. This shows that TRD is able to recover the discriminative relational properties of an image, and encode them as graphs. We provide additional visualizations the supplementary.
Qualitative Results:
TRD
SubgraphX
PGExplainer
GNN UNNExplainer
Cotton Cultivar
FGVC Aircraft
Naturalist
0.8
0.7
0.6
0.5
Fidelity
0.6
Pidelicy
Fidliiy
0.4
0.5
0.4
0.3
0.4
0.2
0.2
0.1
0.5
0.6
0.7
0.3
0.4
0.5
0.6
0.7
0.3
0.4
0.5
0.6
0.7
Sparsity
Sparsity
Sparsity
Figure 4: Fidelity Sparsity curves of TRD and SOTA GNN interpretability methods.
Quantitative Evaluation: We quantitatively evaluate the explanations obtained using TRD based on the Fidelity (relevance of the explanations to the downstream task) vs Sparsity (precision of the explanations) plots for the generated explanations, which is a standard way to measure the efficacy of
We compare against SOTA, generic GNN explainers, namely SubgraphX [92], PGExplainer 51 and GNNExplainer [88], on candidate small (Cotton), medium (FGVC Aircraft), and large (iNaturalist) scale datasets, and report our findings in Figure 4 TRD consitently provides the highest levels of Fidelity not only in the dense, but also in the high sparsity regimes, outperforming generic GNN explainers by significant margins. Unlike the generic explainers, since TRD takes into account the edit distance with the proxy graph for computing the explanations, it is able to leverage the class-level topological information, thereby achieving higher precision. The supplementary contains results on the remaining datasets, details on the Fidelity and Sparsity metrics, and experiments on the functional equivalence of TRD with post-hoc explanations.
GNN explainability algorithms 192
62 91
Classilication Accuracy
95
Clussfication Accuracy
(Dws)
Relatioal Proxies
90
90
DiNo
85
85
80
75
75
TRD (Dus)
70
70
TaNo
20
40
60
80
20
40
60
Number Local Views
Controlled Noise Rate (in %))
Figure 5: Classification accuracies of relational learning based methods with different noise models on FGVC Aircraft. Left: Increasing number of local views sampled randomly across the entire image (instead of just the global view). Right: Increasing the proportion of noisy views in controlled manner by sampling from the region outside of the global view.
shows Sshows the performance of TRD on FGVC Aircraft under the following two noise injection models (1) The local views are sampled uniformly at random across
Robustness to Noisy-Views:
Views: Figure

---

the entire image, instead of just the global view. This model thus randomizes the amount of label information present in |L]. (2) A fraction 17 of the local views are sampled from outside the global view, and the remaining ones (1 '1) come from within the global view, where is the variable across experiments. This puts a fixed upper bound to the amount of label information in [L It can be seen that under model (1), TRD is significantly more stable to changing degrees of uncertainty in label information compared to other relational learning-base methods. Under model (2), TRD outperforms existing methods as the amount of label information is decreased by deterministically increasing the noise rate. As discussed in Section 3.4 and formally proved in Appendix [A.9.] transitivity acts semantic invariant between the instance and the proxy graph spaces, which is condition that subgraphs induced by the noisy views do not satisfy, leading to the observed robustness.
Here, we aim to understand the behaviour of our model under corruptions that affect the underlying causal factors of the data generating process. To this end, we train TRD by replacing subset of the local views for each instance with local views from other classes, both during training and inference. As the proxies are obtained via a clustering of the instance graphs, these local views consequently influence the proxy graphs. We report our quantitative and qualitative findings in Table [ and Figure 6 (Appendix [A.17) respectively. TRD significantly outperforms Relational Proxies all noise rates (percentage of local views replaced), and the gap between their performances widens as the percentage of corruption increases (Table Qualitatively (Figure 6), our model successfully disregards the views introduced from the negative class at both the instance and proxy level. Such views can be seen as being very weakly connected to the global view, well as the correct set of local views that actually belong to that class. Under this causal intervention, the TRD objective is thus equivalent to performing classification while having access to only the subgraph of clean views from the correct class.
Effect of Causal Interventions:
10
20
30
40
50
Relational Proxies
93.22
87.12
79.35
70.99
63.60
TRD (Ours)
94.90
91.54
82.80
76.35
70.55
Table 1: Quantitative performance comparison between Relational Proxies and TRD with increasing rates of corruption (ry: percentage local views from different classes).
4.3 FGVC Performance
Comparison with SOTA: Table 2 compares the performance of TRD with SOTA on benchmark FGVC datasets. Some of the most commonly used approaches involve some form of regularizer
21 41, bilinear features (98), or transformers [29] 8 However, methods that use multi-view
information 94 49], especially their relationships
for prediction have been the most promising, although their final image and class representations are abstract. TRD can be seen to provide the best performance across all benchmarks, while also being fully interpretable. We attribute this to the robustness of our method to noisy views, which is known to have a significant impact on metric learning algorithms [3]
97 5 7
Ablation Studies: Table TRD, namely Complementarity Graph: CG (Section 3.3
shows the contributions of the components of
Proxy Decompo- TR (Theorem
sition: PD (Corollary L.T. and Transitivity Recovery:
its downstream classification accuracy the FGVC Aircraft, Cotton, and Soy Cultivar datasets. Row 0 is the baseline with none of our novel components. Row I corresponds to the setting where the proxy representation is still abstract, ie., in R We concatenate the nodes in G. and propagate it through a 1-hidden layer MLP to summarize it in D.".. As we decompose the proxy into a graph (PD, Row 2) based on the instance node and edge clustering-basee ap- proach as discussed in Section 3or for class-level interpretability, can see that the performance
ID
CG
PD
TR
Aireraft
Cotton
Soy
0.
94.60
67.70
46.00
I.
/
95.10
69.60
47.70
2.
94.94
68.31
46.70
3.
95.15
69.70
50.32
4.
95.40
70.10
50.99
S.
95.60
70.90
52.15
Table 3: Ablations on the key components of TRD namely Complementarity Graph (CG), Proxy De- composition (PD), and TR (Transitivity Recovery).

---

Medium
Large
Catton
Soy
FGVC Aircraft
Stanford Cars
CUB
NA Birds
INaturalist
MaxEnt, NeurlPS'15 18
89.76
93.85
86.54
DBTNer, NeurIPS
88.
StochNorm. NeurIPS'20
45.41
38,50
81.79
$7.57
79.71
74.94
60.75
MMAL, MMM
65.00
47.00
94.70
95.00
89.60
87.10
69.85
BMVC'21
CAP. AAAT21
94.90
95,70
91.80
91.00
GaRD, CVPR
64,80
47.35
94. 30
95.10
89.601
88.00
69.90
ECCV'22
SR-GNN, TIP"22
95.40
96. 10
91.90
TransGG AAA122
45.84
38.67
80.59
94,801
91,70
90.80
71.70
Proxies, 22
95.25
PMRC, CVPR'22
94.80
95.40
91.80
TRD (Ours)
70.90 0.22
0.12
95.60 :: 0.08
96.35
0.03
92.10
0.04
91,45 = 0.12
72.27 0.05
Table 2: Comparison with SOTA on standard small, medium, and large scale FGVC benchmarks.
drops. This happens because lack of prior knowledge about the proxy-graph structure, which increases room for noisy views to be more influential, harming classification robustness. To alleviate this, we introduce
based on our findings from Theorem which effectively wards off the influence of noisy views. With PD, Rows 3 and 4 respectively show the individual contributions of CG, and enforcing the Transitivity invariant between instance and proxy graphs. Row 5 shows that TRD is at its best with all components included.
5 Conclusion & Discussion
We presented Transitivity Recovering Decompositions (TRD), an approach for learning interpretable relationships for FGVC. We theoretically showed the existence of semantically equivalent graphs for abstract relationships, and derived their key information theoretic and topological properties. TRD is a search algorithm in the space of graphs that looks for solutions that satisfy the above properties, providing concrete, human understandable representation of the learned relationships. Our experiments revealed that TRD not only provides end-to-end transparency, all the way up the class-proxy representation, but also achieves state-of of oitte-of-hhearr results on small, medium, and large scale benehmark FGVC datasets, a rare phenomenon the interpretability literature. We also showed that our method is robust to noisy input views, both theoretically and empirically, which we conjecture to be a crucial factor behind effectiveness.
Limitations: Although robust to noisy views, our method is not fully immune to spurious correlations (Figure 3] rightmost graph the wing and the sky are spuriously correlated; additional examples in the supplementary). Combined with recent advances in learning decorrelated representations [66], we believe that our method can overcome this limitation while remaining fully interpretable.
Societal Impacts: Our method makes a positive societal impact by adding interpretability to existing fine-grained relational representations, in provably robust manner. Although any specific negative societal impacts that our method might have, like most deep learning algorithms, method is susceptible the intrinsic biases of the training
not aware of
Acknowledgements
This work was supported by the MUR PNRR project FAIR Future AI Research (PE00000013) funded by the N.xIGenerationEU.
10

---

References
[1]
Aniket Agarwal, Ayush Mangal, and Vipul. Visual relationship detection using scene graphs: A survey, arXiv, 2020.
[2] Anelia Angelova and Shenghuo Zhu. Efficient object detection and segmentation for fine-grained recognition. In CVPR, 2013.
[3] Mohit Bajaj, Lingyang Chu, Zi Yu Xue, Jian Pei, Lanjun Wang. Peter Cho-Ho Lam, and Yong Zhang. Robust counterfactual explanations on graph neural networks. In NeurIPS, 2021. [4] Ardhendu Behera, Zachary Wharton, and Asish Bera. Context-aware Attentional Pooling (CAP) for Fine-graine Fine-grained Visual Classification. In AAAI, 2021.
[5] Asish Bera, Zachary Wharton, Yonghuai Liu, Nik Bessis, and Ardhendu Behera. Sr-gnn: Spatial relation-aware graph neural network for fine-grained image categorization. TIP, 2022.
[6] Steve Branson, Grant Van Horn, Serge Belongie, and Pietro Perona. Bird species categorization using pose normalized deep convolutional nets. In BMVC, 2014.
[7] Tianle Cai, Shengjie Luo, Keyulu Xu, Di He, Tie Liu, and Liwei Wang. Graphnorm: A principled approach to accelerating graph neural network training. In ICML, 2021.
[8] Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin. Unsupervised learning of visual features by contrasting cluster assignments. In NeurIPS, 2020. [9] Mathilde Caron, Hugo Touvron, Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski, and Armand Joulin. Emerging Properties in Self-Supervieed Vision Transformers. In NeurIPS, 2021.
[10] Abhra Chaudhuri, Massimiliano Mancini, Zeynep Akata, and Anjan Dutta. Relational proxies:
Emergent relationships as fine-grained discriminators. In NeurIPS, 2022.
[11] Chaofan Chen, Oscar Li, Chaofan Tao, Alina Jade Barnett, Jonathan Su, and Cynthia Rudin. This looks like that: Deep learning for interpretable image recognition. In NeurlPS, 2019.
[12] Subhabrata Choudhury, Iro Laina, Christian Rupprecht, and Andrea Vedaldi. Unsupervised Part Discovery from Contrastive Reconstruction. In NeurlPS, 2021.
[13] Ching- Yao Chuang. R Devon Hjelm, Xin Wang, Vibhav Vineet, Neel Joshi, Antonio Torralba, Stefanie Jegelka, and Yale Song. Robust contrastive learning against noisy views. CVPR, 2022.
[14] Yin Cui, Feng Zhou, Yuanqing Lin, and Serge Belongie. Fine-grained categorization and dataset bootstrapping using deep metric learning with humans in the loop. In CVPR, 2016.
[15] Yin Cui, Feng Zhou, Jiang Wang, Xiao Liu, Yuanqing Lin, and Serge Belongie. Kernel pooling for convolutional neural networks. In CVPR, 2017.
[16] Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. In NeurlPS, 2013.
[17] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, K. Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. CVPR, 2009.
[18] Alakh Desai, Tz- Ying Wu, Subarna Tripathi, and Nuno Vasconcelos. Single-stage visual relationship learning using conditional queries. NeurlPS, 2022.
[19] Yifeng Ding, Shuwei Dong, Yujun Tong, Zhanyu Ma, Bo Xiao, and Haibin Ling. Channel DropBlock: An Improved Regularization Method for Fine-Grained Visual Classification. In
BMVC, 2021.
[20] Jonathan Donnelly, Alina Jade Barnett, and Chaofan Chen. Deformable protopnet: An inter-
pretable image classifier using deformable prototypes. CVPR, 2021.
[21] Abhimanyu Dubey, Otkrist Gupta, Ramesh Raskar, and Nikhil Naik. Maximum-entropy fine
grained classification. In NeurlPS, 2018.
[22] Anjan Dutta and Hichem Sahbi. Stochastic graphlet embedding. IEEE TNNLS, 2019.
[23] Gintare Karolina Dziugaite, Shai Ben-David, and Daniel M. Roy. Enforcing interpretability and
its statistical impacts: Trade-offs between accuracy and interpretability. arXiv, 2020.
[24] Marco Federici, Anjan Dutta, Patrick Forré, Nate Kushman, and Zeynep Akata. Learning
Robust Representations via Multi-View Information Bottleneck. In ICIR, 2020.
[25] Andreas Fischer, Ching Y. Suen, Volkmar Frinken, Kaspar Riesen, and Horst Bunke. Approxi-
mation of graph edit distance based on hausdorff matching. PR, 2015.
[26] Aritra Ghosh, Naresh Manwani, and P.S. Sastry. Making risk minimization tolerant to label
noise. Neurocomputing, 2015.
[27] Kai Han, Yunhe Wang, Jianyuan Guo, Yehui Tang, and Enhua Wu, Vision GNN: An image worth graph of nodes. In NeurIPS, 2022.

---

[28] David Haussler. Quantifying inductive bias: Al learning algorithms and valiant's 's learning framework. AI, 1988.
[29] Ju He, Jie-Neng Chen, Shuai Liu, Adam Kortylewski, Cheng Yang. Yutong Bai, and Changhu Wang. TransFG: A Transformer Architecture for Fine-grained Recognition. In AAAI, 2022.
[30] Kaiming He, X. Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. CVPR, 2016.
[31] -aaktt--alenninn Herm, Kai Heinrich, Jonas Wanner, and Christian Janiesch. Stop ordering ma- chine learning algorithms by their explainability! a user-centered investigation of performance and explainability. IJM,, 2023.
[32] Geoffrey Hinton, Alex Krizhevsky, and Sida D. Wang. Transforming auto-encoders. In ICANN, 2011.
[33] Han Hu, Jiayuan Gu, Zheng Zhang, Jifeng Dai, and Yichen Wei. Relation Networks for Object Detection. In CVPR, 2018.
[34] Qiang Huang, Makoto Yamada, Yuan Tian, Dinesh Singh, and Yi Chang. Graphlime: Local interpretable model explanations for graph neural networks. IEEE TKDE, 2022.
[35] Shaoli Huang, Zhe Xu, Dacheng Tao, and Ya Zhang. Part-stacked enn for fine-grained visual categorization. In CVPR, 2016.
[36] Zixuan Huang and Yin Li. Interpretable and accurate fine-grained recognition via region grouping. In CVPR, 2020.
[37] Ulf Johansson, Cecilia Sönströd, Ulf Norinder, and Henrik Boström. Trade-off between accuracy and interpretability for predictive in silico modeling. FMC, 2011.
[38] Aditya Khosla, Nityananda Jayaeevaprakash, Bangpeng Yao, and Li Fei-Fei. Novel dataset for fine-grained image categorization. In CVPRW, 2011.
[39] Sungyeon Kim, Dongwon Kim, Minsu Cho, and Suha Kwak. Proxy anchor loss for deep metric learning. In CVPR, 2020.
[40] Daniel Kleitman and B. Rothschild. The number of finite topologies. Proceedings of The American Mathmattial Society- PROC AMER MATH SOC, 1970. [41] Zhi Kou, Kaichao You, Mingsheng Long, and Jianmin Wang. Stochastic normalization. In NeurIPS, 2020.
[42] Jonathan Krause, Michael Stark, Jia Deng, and Li Fei-Fei. 3D Object Representations for Fine-Grained Categorization. In 3DRR, 2013.
[43] Michael Lam, Behrooz Mahasseni, and Sinisa Todorovic. Fine-grained recognition as hsnet search for informative image parts. In CVPR, 2017.
[44] Fei-Fei Li, Andrej Karpathy, and Justin Johnson. Tiny image net.
com/c/tiny-imageeeee timiim//et 2017.
[45] Sihang Li, Xiang Wang, An Zhang, Yingxin Wu, Xiangnan He, and Tat-Seng Chua. Let invariant rationale discovery inspire graph contrastive learning. In ICML, 2022.
[46] Yanan Li, Jun Yu, Yibing Zhan, and Zhi Chen. Relationship graph learning network for visual relationship detection. In ICMA, 2021.
[47] Di Lin, Xiaoyong Shen, Cewu Lu, and Jiaya Jia. Deep lac: Deep localization, alignment and classification for fine- ane-grained recognition. In CVPR, 2015.
[48] Wanyu Lin, Hao Lan, and Baochun Li. Generative causal explanations for graph neural networks.
In ICML, 2021.
[49] Yang Liu, Lei Zhou, Pengcheng Zhang, Xiao Bai, Lin Gu, Xiaohan Yu, Jun Zhou, and Edwin Hancock. Where to focus: Investigating hierarchical attention relationship for fine-grad fnn-grained visual classification. In ECCV, 2022.
[50] Di Lu, Jinpeng Wang, Ziyun Zeng, Bin Chen, Shudeng Wu, and Shu-Tao Xia. SwinhGHash: Fine-grained Image Retrieval via Transformer-basee Hashing Network. In BMVC, 2021.
[51] Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. Parameterized explainer for graph neural network. In NeurlPS, 2020.
[52] Wei Luo, Xitong Yang, Xianjie Mo, Yuheng Lu, Larry Davis, Jun Li, Jian Yang, and Ser Nam Lim. Cross-x learning for fine-grained visual categorization. In ICCV, 2019.
[53] Subhransu Maji, Esa Rahtu, Juho Kannala, Matthew B. Blaschko, and Andrea Vedaldi. Fine-
Grained Visual Classification of Aircraft. arXiv, 2013.
[54] Antonio Martinón and Józef Banaš. Some properties of the hausdorff distance in metric spaces. Extracta mathematicae, 1990.
12

---

[55] Mohammad Moghimi, Mohammad Saberian, Jian Yang. Li Jia Li, Nuno Vasconcelos, and Serge
Belongie. Boosted convolutional neural networks. In BMVC, 2016.
[56] Yair Movshovitz-Attias, Alexander Toshev, Thomas K. Leung, Sergey Ioffe, and Saurabh Singh.
No Fuss Distance Metric Learning Using Proxies. In ICCV, 2017.
[57] Elaine D. Nelson. Separation axioms in topology. Graduate Student Theses, Dissertations, & Professional Papers. 17., 1966.
[58] Michel Neuhaus and Horst Bunke. Bridging the gap between graph edit distance and kernel
machines. In MPAI, 2007.
[59] Timothy O' Connor. Emergent Properties. Edward N. Zalta, editor, The Stanford Encyclopedia of Philosophy. Metaphysics Research Lab, Stanford University, Winter 2021 edition, 2021. [60] Wonpyo Park, Dongju Kim, Yan Lu, and Minsu Cho. Relational knowledge distillation. In
CVPR, 2019.
[61] Massimiliano Patacchiola and Amos Storkey. Self-supervised relational reasoning for represen- tation learning. In NeurlPS, 2020.
[62] Phillip E. Pope, Soheil Kolouri, Mohammad Rostami, Charles E. Martin, and Heiko Hoffmann. Explainability methods for graph convolutional neural networks. In CVPR, June 2019.
[63] Yongming Rao, Guangyi Chen, Jiwen Lu, and Jie Zhou. Counterfactual attention learning for fine-graine fine-grained visual categorization and re-identification. In ICCV, 2021.
[64] Pau Riba, Andreas Fischer, Josep Lladós, and Alicia Fornés. Learning graph edit distance by graph neural networks. PR, 2021.
[65]
Elena Rica, Susana Álvarez, and Francesc Serratosa. On-line learning the graph edit distance
costs. PRI., 2021.
[66]
Karsten Roth, Mark Ibrahim, Zeynep Akata, Pascal Vincent, and Diane Bouchacourt. Disentan-
glement of correlated factors via hausdorff factorized support. In ICLR, 2023.
[67] Adam Santoro, David Raposo, David G.T. Barrett, Mateusz Malinowski, Razvan Pascanu, Peter Battaglia, and Timothy Lillicrap. A simple neural network module for relational reasoning. In NeurlPS, 2017.
[68] Thomas Schnake, Oliver Eberle, Jonas Lederer, Shinichi Nakajima, Kristof T. Schütt, Klaus- Robert Müller, and Grégoire Montavon. Higher-order explanations of graph neural networks via relevant walks. IEEE TPAMI, 2022.
[69] I. S Shapley. Notes on the n-person game ii: The value of an n-person game. The RAND Corporation, 1951.
[70] Flood Sung. Yongxin Yang, Li Zhang, Tao Xiang, Philip H.S. Torr, and Timothy M. Hospedales.
Learning to Compare: Relation Network for Few-Shot Learning. In CVPR, 2018.
[71] Zhenchao Tang, Hualin Yang, and Calvin Yu-Chian Chen. Weakly supervised posture mining
for fine-grained classification. In CVPR, 2023.
[72] Komal Teru, Etienne Denis, and Will Hamilton. Inductive relation prediction by subgraph reasoning. In ICML, 2020.
[73] Matt Turek. Explainable artificial intelligence (xai). https://www.daree aaarpa.mil/prrgra... explainables ar arttiiiiiiat intelnielll ligence
[74] Pál Turán. On an extremal problem in graph theory. Matematikai és Fizikai Lapok (in Hungarian), 1941.
[75] Grant Van Horn, Steve Branson, Ryan Farrll, Scott Haber, Jessie Barry, Panos Ipeirotis, Pietro Perona, and Serge Belongie. Building a bird recognition app and large scale dataset with citizen scientists: The fine print in fine-grained dataset collection. In CVPR, 2015.
[76] Grant Van Horn, Oisin Mac Aodha, Yang Song, Yin Cui, Chen Sun, Alex Shepard, Hartwig Adam, Pietro Perona, and Serge Belongie. The iNauurllsst Species Classification and Detection Dataset. In CVPR, 2018.
[77] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
[78] Jörg Wagner, Jan Mathias Köhler, Tobias Gindele, Leon Hetzel, Jakob Thaddäus Wiedemer, and Sven Behnke. Interpretable and fine-grained visual explanations for convolutional neural networks. In CVPR, 2019.
[79] Robert A. Wagner and Michael J. Fischer. The ttring-to-string correction problem. ACM, 1974. [80] Catherine Wah, Steve Branson, Peter Welinder, Pietro Perona, and Serge J. Belongie. The caltech-uesd birds-200-205 dataset. In California Institute of Technology, CNS-TR-2010-001,
2011.
13

---

[81] Jun Wang, Xiaohan Yu, and Yongsheng Gao. Feature Fusion Vision Transformer for Fine-
Grained Visual Categorization. In BMVC, 2021.
[82] Xiang Wang, Yingxin Wu, An Zhang, Xiangnan He, and Tat-Seng Chua. Towards multi-grained explainability for graph neural networks. In NeurIPS, 2021.
[83] Zhuhui Wang, Shijie Wang, Haojie Li, Zhi Dou, and Jianjun Li. traph-propagation based correlation learning for weakly supervised fine-graine grained image classification. In AAAI, 2020.
[84] Xiu Shen Wei, Jian Hao Luo, Jianxin Wu, and Zhi Hua Zhou. Selective Convolutional Descriptor
Aggregation for GinenGr Image Retrieval. JEEE TIP, 2017.
[85] Xiu Shen Wei, Chen Wei Xie, Jianxin Wu, and Chunhua Shen. Mask-cnn: Localizing parts and
selecting descriptors for fine mee-griieed bird species categorization. PR, 2018.
[86] Guang Yang. Juan Cao,, Zhineng Chen, Junbo Guo, and Jintao Li. Graph-based neural networks for explainable image privacy inference. PR, 2020.
[87] Xuhui Yang. Yaowei Wang, Ke Chen, Yong Xu, and Yonghong Tian. Fine-grained object classification via self-supervised pose aligoment. In CVPR, 2022.
[88] Zhitao Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnnexplainer: Generating explanations for graph neural networks. In NeurlPS, 2019.
[89] Xiaohan Yu, Yang Zhao, Yongsheng Gao, Shengwu Xiong, and Xiaohui Yuan. Patchy image structure classification using multi-orientation region transform. In AAAI, 2020.
[90] Hao Yuan, Jiliang Tang, Xia Hu, and Shuiwang Ji. Xgnn: Towards model-level explanations of graph neural networks. In KDD, 2020.
[91] Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Ji. Explainability in graph neural networks:
A taxonomic survey. arXiv, 2020.
[92] Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji. On explainability of graph neural networks via subgraph explorations. ICML, 2021.
[93] Vinicius Zambaldi, David Raposo, Adam Santoro, Victor Bapst, Yujia Li, Igor Babuschkin, Karl Tuyls, David Reichert, Timothy Lillicrap. Edward Lockhart, Murray Shanahan, Victoria Langston, Razvan Pascanu, Matthew Botvinick, Oriol Vinyals. and Peter Battaglia. Deep reinforcement learning with relational inductive biases. In ICI.R, 2019.
[94] Fan Zhang, Meng Li, Guisheng Zhai, and Yizhao Liu. Multi-branch and Multi-scale Attention Learning for Fine-Grained Visual Categorization. In MMM, 2021.
[95] Han Zhang, Tao Xu, Mohamed Elhoseiny, Xiaolei Huang, Shaoting Zhang, Ahmed Elgammal, and Dimitris Metaxas. Spda-enn: Unifying semantic part detection and abstraction for fine- grained recognition. In CVPR, 2016.
[96] Ning Zhang. Jeff Donahue, Ross Girshick, and Trevor Darrell. Part-based r-cnns for fine-grained category detection. In ECCV, 2014.
[97] Yifan Zhao, Ke Yan, Feiyue Huang, and Jia Li. Graph-based high-order relation discovery for fine-graines recognition. In CVPR, 2021.
[98] Heliang Zheng. Jianlong Fu, Zheng-Jun Zha, and Jiebo Luo. Learning deep bilinear transforma- tion for fine-grained image representation. In NeurIPS, 2019.
[99] Yuehua Zhu, Muli Yang. Cheng Deng, and Wei Liu. Fewer is more: A deep graph metric learning perspective using fewer proxies. In NeurlPS, 2020.
14

---

A
Appendix
Below, we provide some theoretical results and quantification of empirical observations from the existing literature [24 10] that used in the main text.
A.1
Identities Mutual Information
Let three random variables x, y, and form the Markov Chain x - Then,
Positivity:
T(x:y) 2 0, yx)
Chain Rule:
yxx:) yx:: (x::
Data Processing Inequality:
(xx;) 2 ((xy)
A.2
Information Gap
The Information Gap [0] the uncertainty that remains about the label information given
relation-agnostic representation z. Quantitatively,
T(x; r|z) T(x:y) ((x:)))[(z;)))
An implication of the above is that the label information in can be factorized as follows:
[(x: y) / (x: r/z) (2;y)
A.3 Sufficiency
representation of sufficient [24] for predicting its label y if and only if, given z, there remains no uncertainty about the label of y of x. Formally,
7(x: 0 = I(x:y) = T(zyy)
A.4 Relation-Agnostic Representations Information Theoretic
An encoder f is said to produce relation-agnostic representations 100 if it independently encodes the global view g and local views v E L of without considering their relationship information Quantitatively,
((x:y (xx:)) [(v::g...V11s))))
A.5 Distributive property of
Since [(x;r) r) refers to local-to-global relationships (2.. the definition of relation ag- nosticity in Appendix A.4 implies that f(x) does not reduce any uncertainty about emergence, ie..
I(x;r) = I(vive )) -1fvv I(z1. Z2, ......2 Z.|
A.6 Sufficient Learner
Following are the necessary and sufficient conditions for a sufficient learner
It should have Claation-annstte encoder producing mappings +
There must be a separate encoder { that takes relation-agnostic representations z as input, and bridges the information gap I [xxr/zz)
15

---

A.7 Semantic Consistency
metric space (M,d) d) along with its embedding function yp X - M are called semantically consistent, if the following holds;
ylxxxx x d((p(x),))
In other words, MM encodes the semantics of x via its distance function d.
A.8 Semantic Emergence
Without loss of generality, let assume that g only contains semantic information. Semantic Emergence refers to the fact that for a particular view, its embedding &, encodes a large amount of semantic information, must also have large amount of information about the global-view (local- to to-global correspondence in DiNo (9). Intuitively, this the case because all views v E V, in some way, arise from g, and local-to-glon relationships encode semantic information. Quantitatively,
d(zv:y) x I(v:g)
A.9 Proofs of Theorems
Theorem 1 For relational representation that minimizes the information gap [(x: Zv), there exists a metric space (M, d) that defines a Semantic Relevance Graph such that:
d(z,, y) > A
5
g R"
sem
R
((p(2,). ((2)) d(r,) 8
where M R" som and d denote semantically consistent transformations and distance metrics respectively, ip: Zv sem
M. and is some finite, empirical bound on semantic distance.
Proof. By contradiction.
Let assume that there exists metric space (M, d) that induces Semantic Relevance Graph on Zy satisfying the given constraint. In other words, given Zy. we get an upper-boune of 5 on the amount of label information y that can be captured from x, and there is no function that can reduce the uncertainty about the label any further.
Since and d are semantically consistent (Appendix A.7) 1. in information theoretic terms, Zy is sufficient representation (Appendix AA.)). i.e., both sides of the following are true:
T(x, y) ((2v,y) x
Zvx Σ d(z,y) 6, zEZv
(2)
where 5 2 0 (Appendix A.I However, since ff is only a relation-agnosti encoder (as stated in the Preliminaries), it exhibits information gap (Appendix A.2 ie..
I(x,y) = ((x:
where ((x:r|Zz) 0. This leads to contradiction between Equation 2 and Equation 3
establishing the falsity the initial assumption and proving Theorem
Theorem 2: The graph 9" underlying the output relational representation is member of G for which the mutual information with the label is maximal. Formally,
g" = arg max ((g.y) GEG
Proof. By contradiction.
Let assume the existence of graph G' E G such that T(g', y) > T(g*, As shown in Theorem since G* encodes both relation-agmostic (nodes) and relation-aware (edges) information, it is sufficient representation (Appendix of x. Hence, for Zy,
1(g";y) [(x I(z,y) ((x:y)
16

---

Thus, for G' to exist,
I(g';y) I(x:y)
However, computing G" involves the following Markov Chain:
x Zv G'
Thus, from the Data Processing Inequality (Appendix A.I
1(x; 2v) 2 / (Zv;
Using the chain rule of mutual information (Appendix A.I):
((x:y) / (xx Zv) (Zzvi'))
1(x:y) - 1(x; Zv) [(''; y
Now, y(9::ylZv) 0, since Zv + G' (g' derived from Zv).
= I(x:y) [xx: Zv) 2 y( = [(x:y) 2 [g' + I(x: y (2v)
By the positivity property of mutual information 24 [(:: Zyy 2 0. Hence.
((x:y) yg
which is in contradiction Equation (4 Hence the initial assumption must be false.
Theorem 3; A function (z))) that reduces the uncertainty I(v.v (Z, )) about the emergent relationships among the set of views can define a Semantic Relevance Graph by being transitivity recovering.
Proof. Without loss of generality, consider three transitively related views V1, V2, and Va such that:
d y) < 8 (() > 8 A d(zz, > 8
In qualitative terms, V2 plays strong role in determining given Zy, while the other views do not. From the property of Semantic Emergence (Appendix(A.8) (A.
d(zz. y) < 8 = [(viv2:g) > I(v2vs:g) >
However, since V1, V2, and Vy transitively related,
T(ViVs:g) >
Now, f being a relation agnostic encoder, it has no way to minimize the uncertainty in the emergence T(v1v3::) g). Hence, using the distributive property of f (Appendix A.5.
I(vi 7 + [(, (2)23; zz) >
We know that ((x; = [[v, = 1 (2] g) (Appendix A.4).
Consider function (z() that maps elements in Zv to (M, d) such that d(s((z), p(zz)) x 1/1(z,2y:g) to is thus transitivity recovering. as it allows for the identification of transitivity among V1. V2 and va via the distance metric d. By allowing for such distance computation, ip minimizes [ 22, gl(((1)))(Zz)) meaning that the knowledge obtained from reduces the uncer- tainty about the emergent relationships. This in turn also minimizes 1(vi (((z)))(zz)) and consequently 7(x; (2)((11))))))))))))))) )((2)))
However, f(x;r) I ( 2z)) (Appendix A.4). Hence, also minimizes the information gap which implies that:
3 E(p(z)), (pza)) d(r,y) < 6,
thus defining Semantic Relevance Graph (Theorem
17

---

A.9.1 Robustness
Definition 4 (Robustness). A classifier f, is said to be robust (noise-tolerant) if it has the same classification accuracy that of f under the distribution D [26]. Formally,
Polf(=)) = (z,))
where PD defines the probability distribution over D, and vi is the noisy version of the input xc In other words, fn would base its prediction on the (1 - n)]/// noise-free views only.
Lemma Let Vn be the set of noisy views in V. Let V hence, transitively related Theorem 3) views. Then, the cut-set C (V*, wn) = Ø when mapped to the output space of -> G.
V be the set of noise free (and
Proof. to restricts G to the Hausdorff space (Theorem 3, Inference and Learning objective). In the general case, since the Hausdorff distance defines a pseudometric [54), satisfies the triangle inequality. In our specific case, it also defines complete metric. This is because yp also satisfies the requirement of geometric relation agnositicity in the fine-grained scenario under the minimization of the cross-entropy loss with categorical ground-truth [1O]:
vzi E Z : (z()z)) O (m,)),)) = の
The above implies that the representation space of satisfies the separation axioms 57 and hence:
h(r, v) > O, Va # y.
where h(.,,) .) is the Hausdorff edit distance [25 64] Therefore, for u(z), the Hausdorff distance defines a complete metric while satisfying the triangle inequality. Now, consider set of views {v., Vj, V where vi, E V*, and V, E V", Suppose these nodes define 3-clique (clique of size 3) the instance graph. The completeness of the Hausdorff distance in cp(z), as well as the satisfaction of the triangle inequality thus gives us:
d((((v,), ((vx)) < d((p(v)), (vv,)) + d((p(v)).
Hence, for the aforementioned clique formed by vi, y,, and Vk. the only edge that survives is (V:, V&). In other words, upon convergence, yp would never produce a path between two transitively related views that involves a noisy view, rendering V and 1 disconnected. This completes the proof of the lemma.
Corollary 4.1. There is path in G" connecting two views in 4/* that involves noisy view from V7, Thus, the elements of '* and V"1 respectively form homogeneous subgraphs of transitive and noisy views in G and Gp-
Definition 5 (Continents and Islands). A continent is complete subgraph (clique) in G" exclusively composed transitively related views. An island G* is a subgraph that exclusively contains noisy views.
Lemma 2. Let EE1 be the set of edges connecting continents C1 and Cz. The elements of E12 are mutually redundant, iee.,
H(egle:)= = 0, V(G,, ej) E E12
Proof. Consider a pair of vertices Ve, Uy E C1, such that both are connected C2 via edges e,, and ej respectively. However, since Ci is a clique, v; and fy (and all other nodes in C₁) are also connected. Thus, the complete set of information that v; has access to (and can potentially encode via e;) the transitivity of (local-to-global relationship emerging from) all the local views in C₁ given by:
((c,) I(V1, V2, Vic, :g)
Let y be a message passing function (like a GNN) that carries information across connected nodes. Thus, for 7, the following holds:
= 20 -e = C2) I(e;; = H(eyle:)= =
meaning that the knowledge of a single edge between C₁ and C2 is sufficient to determine the connectivity of the two continents. No other edge in [E12 can thus provide any additional information, thereby concluding the proof.
18

---

Theorem 4 In the representation space of y, the uncertainty in estimating the topology 7" of V is exponentially greater than the uncertainty in estimating the topology T" of V* in terms of the error rate 6.
Proof. It known that the total number of possible topologies 7 for a graph with n nodes is given by 40
-2(x²11)
In what follows, we show that it is possible to dramatically reduce this number to ((n) for continents, but not for islands.
According to Lemma D and Corollary 4.1 the groups of transitive and noisy view nodes can be separated into disjoint sets with edges between them. Let V' = {V1, V2, V&J be a set of transitively related views (a continent) with topology T. Let V = (Vx+1, Vk+2, .... Vn ] be a set of noisy views (an island) with topology Ty, Let .t" denote the probability mass of a topology in D (fraction of samples in with topology T).
Let 7 be the ground truth topology of a class, determined exclusively by the continents (since noisy views should not determine the label). Let be the best approximation of 7² that can be achieved by observing M unique samples, such that:
h - S,
where (T)) is the graph with topology т. In other words, is the upper-bound on the statistical error in the approximation of the ground truth topology that can be achieved with M unique samples.
Now, uniquely determining G(F*) involves determining all the k-cliques involving the global-view (Transitivity Recovery from Theorem 3). However, the Túran's 's theorem [74] puts an upper-bound on the number of edges [E] of graph with clique number and n nodes at:
n² E| = (1 k 2
which gives a direct upper-bound the sample complexity M for learning f.
there are |E| edges representing transitive relationships among n views, and the maximum clique size for class is k. the number of k-cliques to encode all possible clique memberships with this configuration would be given by:
log,
log2 e
1og2((1= 1
1og2((1 )m log, k
logg(1 ) logg 2++2 n = O(log n)
log, & loga
(6)
Since the maximum clique size is a constant for given class. The above number of samples would be required to gain the knowledge of all the cliques in the graph.
To analyze the connectivity across different continents in G*, we can apply Lemma 2 to reduce all the continents in G* into single nodes, connected by an edge if there is at least one node connecting the two continents in G Using this observation, and Lemma such a graph can be given by:
2 the number of topologies [ of
R = (OOo,, x)/4) = (n)
Thus with a clique number of k, G* could have maximum of Ologg n) continents (Equation ( connected with each other in O(n) possible ways (Equation (T). Since there is only 1 possibility for the topologies of each elique, the only variation would come from the cross-continent connectivity, which has (n) potential options. Using the Haussler's 's theorem (28), the number of samples M required to achieve maximum error rate of with probability (1 8) for continent given by:
M = log2 Onn) + log2 8 log, (()) + logz
log, ((n) loga
(8)
<(1/c)
where e is the number of classes, and in practice 1/c > Note that the above bound is tight since restrict our hypothesis class to only having transitivity recovering decompositions (Theorem 3).
19

---

Thus, one would need a number of samples that is linear in the number of transitive views (n)) as well as the the error rate (c), and the certainty (6), to determine for class. It can also be seen that M is completely independent of the noise rate 7).
However, for W since its constituent views noisy, prior assumptions be made about its structure. Thus, the number of possible topologies for V can be obtained by substituting n with in Equation (5) as follows:
|-"| = 2 /1) O(2))
Thus, based on the Haussler's 's theorem, the sample complexity for learning the topology of an island would be given by:
log2 ((2") + logz ETT
1 B log2 O(2)) + log2 1 3
log2 ((2") + logz
M
6
2
since the probability of finding an instance with specific noisy topology x² is very small, and hence can be approximated with the error-rate (c). Note that the small probability mass for a specific r" comes from the worst-case assumption that the dataset would have all possible forms of noise,
and hence, the probability for a specific kind would be very low. Also note that unlike Equation (8). the bound cannot be tightened as the premise of transitivity does not hold.
Thus, while the sample complexity for learning a transitive topology M is linear in the number of views and the error rate Equation (8) that for noisy topology M is exponential in the number of views and quadratic in the error rate Equation ( Hence, in the worst case, when n s [26). M > M This implies that is significantly more difficult for yp to learn the topology 7 of an island than it is to learn the topology f of a continent.
From Equation 9), the probability of yo making correct prediction based on noisy views would be given by:
loga O(2") log2
1
M, 2
loga
M
- logg O(2%)
62
5
1
loga 8
M 1)
1
1
My c² 6-1
loga
1
8
r7
loga σ
S nT
2 8
1
8, > 0
where the noise rate 7) is a constant for a particular dataset, and Mn/n e, since M, > 7, as M, (22)). From Equation (8), the probability of &o making correct prediction based on transitive views would be given by:
1 M. loga O(n) + loga A
loga
M.e loog ((n) M.e log2 n
log2 J
(0 logg T2)E 1og2 n
loga
log, n 0c
logg n
logz nt n
loga
-log, n 9
0c-1
2
= n
8, O),
where 0 == M. AM./log.1 n, which is a constant for particular class in a dataset, and so is the number of transitively related views |V* 2 for class, and I 0l. Thus the relative uncertainty
20

---

between 6n and 8. would be given by:
bq 0(2-2) 2 (2 (2-9)e²
(2-92-1=2- =2 =2- -2- =0 0
5, (
2-c
2-c
This completes the proof of the theorem.
A.10 Discussion on Graph-Based Image Representations and Proxy-Based Graph Metric Learning
Graph-based image representation using patches was recently proposed in ViG [27 Although the initial decomposition of image into a graph allowed for flexible viess-view relationship learning, the image graph is eventually abstracted into a single representation in R This prevents one from identifying the most informative subgraph responsible for prediction, both the instance level, and at the leass- Although interpreting ViGs may be possible via existing GNN explainablity algorithms [88] 51 82), they are typically post-hoc in nature, meaning that only the output predictions can be explained and not the entire classification pipeline. Incurred computational and time overheads that come with post-hoc approaches in general, are additional downsides. Our approach preserves the transparency of the entire classification pipeline by maintaining graph-based representation all the way from the input to the class- proxy, thereby allowing us to explain predictions at both instance and class levels in ante-hoc manner.
Although graph metric learning has been shown to effective for learning fine-grained discriminative features from graphs [45] rustance-based contrastive learning happens to be (1) computationally expensive and (2) unable to capture the large intra-class variations in FGVC problems [56] (39. Proxy- based graph metric learning
(99) has been shown to address both issues, while learning generalized
representations for each class. However, the metric space embeddings learned by the above methods
not fully explainable in terms of identifying the most influential subgraph towards the final prediction, which is an issue we aim to address in our work.
A.11 Role of Transitivity
The idea of transitivity allows us to narrow down sets of views whose relation- agnostic information have been exhaustively encoded in Z, and the only available sources of information comes only when all the views are observed collectively as the emergent relationship. On the other hand, dealing with a general local-to-global relationship recovery would additionally include fiew-pairs, only one of which might be contributing to the relational information (I(vI V2; g) and [(v2V3::) g)), thus not exhibiting emergence. Using only the former in our proof helps us to identify the set nodes responsible for bridging the information gap (via emergence) as the ones satisfying transitivity.
A.12 Learning the Graph Edit Costs
The GNN proposed in (64] would directly learn the mapping Ø Zv - R for computing the edit costs. In TRD, we instead split the GNN for edit cost computation into a prefix network Zv + M and cost head sb MM- + R. Note that this factorization is just a different view of á that allows to draw parallels of our implementation with the theory of TRD.
A.13 Further comparisons with Relational Proxies
Same number of local views: We evaluate both Relational Proxies and TRD with the same number of local views in the normal (no explicit addition of noise) setting on the FGVC Aircraft dataset, and report our findings in Table TRD marginally outperforms Relational Proxies for all values of the number of local views, and exhibits a trend of scaling in accuracy with increasing number of local views. Relational Proxies, on the other hand, does not seem to benefit from increasing the number of local views, possibly due to its lack of robustness to noisy views.
Compute cost: In Table 5 we provide the computational costs of Relational Proxies and TRD in terms of wall clock time evaluated on FGVC Aircraft (same experimental settings including the number of local views). We can see that TRD is significantly more efficient than Relational Proxies in terms of both single sample inference as well as training time until convergence. This is because of the following reasons:
21

---

# Local Views
8
16
32
64
Relational Proxies
95.25
95.30
95.29
95.31
TRD (Ours)
95.27
95.45
95.52
95.60
Table 4: Comparison of TRD with Relational Proxies under the same number of local views.
The Complementarity Graph in TRD constructed exactly once before training, and the semantic relevance graph, as well as the proxy graph are learned as part of the training process,
TRD does not involve updating the relation-agnostic encoder, which a ResNet50, as part of the training process. Relational Proxies requires it be updated, thereby exhibiting computationally heavier forward (as local view embeddings cannot be pre-computed) and backward passes.
Average Inference Time (ms)
Training Time (hrs)
Relational Proxies
130
22
TRD (Ours)
110
15
Table S: Compute cost of TRD relative to Relational Proxies.
A.14 Over-smoothing
To understand whether the process of modelling emergent relationships is vulnerable to the smoothing phenomenon in GNNs, we evaluated TRD using GATs of up to 64 layers on FGVC Aircraft, presenting our findings in Table We see that the performance does drop as the number of layers are increased beyond 8. To validate whether this is due to the oversmoothing phenomenon, we measure the degree of distinguishability among the nodes by taking the average of their pairwise 2 distances. The table shows that the distinguishability also decreases as we increase the number of layers, suggesting that the smo-hhhg phenomenon does occur. Under the light of the above experiments, the 8-layer GAT is an optimal choice for our problem.
GAT-Depth
4
16
32
64
Accuracy
95.05
95.60
95.32
94.78
94.20
Distinguishability
0.87
0.63
0.49
0.21
0.09
Table 6: Effect of over-smoothing in GAT on learning emergent relationships.
A.15
Results on ImageNet subsets
we evaluate the contribution of our novel Transitivity Recovery objective in the coarse-grained (multiple fine- ane-grained subcategories single class) and fine-grained subsets of ImageNet, namely Tiny ImageNet [44] and Dogs ImageNet (Stanford Dogs respectively, and report our findings in Table 7 Although our method can surpass existing SOTA in both the settings, larger gains (A) are achieved in the fine-grained setting, suggesting that TRD particularly well suited for that purpose.
Following existing FGVC literature
10 21
38
A.16
Dependence on input image size
We follow recent SOTA FGVC approaches that use relation-agnostie encoders to extract global and local views 100 94 84 In particular, our view extraction process exactly the same as Relational
Proxies 10 with the same input image resolution and backbone (relation-agnosttic) encoder. The
22

---

Tiny ImageNet
Dogs ImageNet
MaxEnt
21
82.29
75.66
Relational Proxies
10
88.91
92.75
w/o Transitivity Recovery
88.10
91.03
b with Transitivity Recovery
89.02
93.10
A a)
0.92
2.07
Table 7: Coarse-grained fine-grained classification results.
above approaches first extract the global view from the input image, and crop out local views from the global view. Since there are two scales at which the image is cropped, all the crops are resized to 224x224. In practice, this provides similar resolution resizing the full input image resolution at the start. To evaluate this hypothesis, we re-trained and re-evaluated our model with the input images resized to 448x448, keeping the remainder of the process of view extraction the same. We provide our results on multiple datasets in Table [8] which shows that the performance gains at the higher input resolution are minor, thus supporting our hypothesis.
higher
Soy
FGVC Aireraft
Stanford Cars
TRD: 224 x 224
52.15
95.60
96.35
TRD: 448 448
52.23
95.62
96.39
Table 8: Dependence of TRD input image size.
23

---

A.17 Results with Causal Interventions
R34
3
A22
Figure 6: Top-down: Qualitative results FGVCAireraft Stanford Cars, and NA Birds with causal intervention. The first two columns from the left are instance graphs, and the rightmost column contains the proxy graphs. The local views of the correct class are bordered in green, while the ones from a different class are bordered in red. A subset of the local views for each instance was corrupted with the introduction of local views from other classes, both during training and inference. These local views consequently also feature in the proxy graphs. The negative local views from different classes (red) can be seen have significantly weaker connection the global view (bordered in blue), and the correct set of local views (green).
24


Reviews:
[{"review_id": "vNc3voo1K2", "reviewer": "Reviewer_mGG3", "summary": "The paper presents a novel perspective on interpretable representation learning, introducing Transitivity Recovering Decompositions (TRD) as a method for identifying graphs that can learn local-to-global representations. The proposed approach achieves state-of-the-art (SOTA) performance on Fine-Grained Visual Classification (FGVC) datasets while maintaining interpretability. The TRD is well-defined, supported by theoretical and empirical analysis, and conducts thorough interpretability and robustness experiments.", "questions": "1.\tWhat if there are multiple high-level concepts along with low-level concepts present in a training distribution? A quick analysis of datasets such as CIFAR100, or (if possible) ImageNet can put some light on this. Like, multiple breeds of dogs, cats, and birds are in a single classification task. \n2.\tHow can the presence of a different local view (belonging to another class) affect the forming of cliques? (Any qualitative example or quantitative number can help understand the potential impact of TRD)\n3.\tWhat are the values of empirically defined hyper-parameters (such as delta and gamma) across the datasets? A plot/table showing the effect of such variables across the datasets is important to measure the stability of the TRD. \n", "limitations": "The authors have adequately discussed the limitations and potential positive societal impact of their work. No further discussion is necessary in this regard.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "1.\tThe authors provide a well-defined and theoretically supported Transitivity Recovering Decompositions (TRD) method, which is further validated through empirical analysis.\n2.\tThe experiments conducted on FGVC benchmarks demonstrate consistent SOTA performance across multiple datasets, although the improvements are marginal.\n3.\tThe paper includes comprehensive interpretability and robustness experiments, effectively showcasing the effectiveness of TRD to a certain extent.\n", "weaknesses": "1.\tThe introduction section requires improvement in terms of providing a high-level overview of the proposed TRD. A simple end-to-end pipeline overview in the introduction would greatly benefit readers' understanding.\n2.\tThe inference pipeline of the proposed system is not clearly described. Including the training and testing pseudo code would substantially enhance the clarity of the paper.\n3.\tThe robustness analysis is limited. To comprehensively evaluate the interpretability of TRD, it is crucial to observe the results under the influence of causal interventions. For instance, replacing a percentage of local views from another class and observing the results would provide valuable insights.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W1. Overview** We thank the reviewer for pointing this out. We will add the following to the final version:\n\"After decomposing an input image into its constituent views following related literature [9, 78, 88], we initialize the relational representation by forming a graph through connecting complementary sets of nodes. This allows information to flow across disjoint localities, while disregarding redundancy. We then propagate this initial image graph through a trainable GNN. We obtain the class proxy graph by an online clustering of the instance node and edge embeddings. We train the GNN to match the instance and the proxy graphs by recovering transitive relationships. Concretely, this is achieved by minimizing the edit cost between the two, approximated by a learnable form of the Hausdorff Edit Distance.\"\n\n**W2. Pseudocode** Below, we provide PyTorch style training and inference pseudocodes for TRD. We will release our full implementation upon acceptance.\\\n**Preprocess**\n```\ndef get_graphloader(X, Y, mode='train'):\n\tlabels_to_instances = {}\n\tgraphs = []\n\t# Complementarity graphs\n\tfor x, y in dataloader(X, Y):\n\t\tZ_l = [local_views(x)] + [global_view]\n\t\tZ_v = [f(z) for z in Z]\n\t\tG_c = {nodes: Z_v, edges: [(z_i, z_j, repeat(1 / dot(z_i, z_j), n)) for z_j in Z_l for z_i in Z_l]}\n\t\t# Adding global view and its edges\n\t\tG_c.nodes += z_g\n\t\tG_c.edges += [(z_g, z_l) ones(n) for z_l in Z_l]\n\t\tgraphs.append(G_c)\n\t\tif mode == 'train':\n\t\t\tlabels_to_instances[y] += G_c\n\tif mode == 'test':\n\t\treturn dataloader(graphs)\n\n\t# Initialize proxy graphs\n\tfor label in Y:\n\t\te = random.choice(labels_to_instances[label].all_edges())\n\t\tn = unique(e[0] + e[1])\n\t\t# Instance embeddings are only used as initializations. Proxies must be independent entities.\n\t\tY_proxies[label].nodes = deepcopy(n)\n\t\tY_proxies[label].edges = deepcopy(e)\n\t\tlabels_to_instances[label] = Y_proxies\n\n\treturn dataloader(labels_to_instances)\n```\n**Training**\n```\nfor G_c, P in get_graphloader(X, Y):\n\tG_s = phi(G_c)  # semantic relevance graph\n\n\t# Assignment of instances to proxies\n\tscores = pairwise_hausdorff(G_s, P)  # [59]\n\tpreds = sinkhorn(scores)  # [7]\n\tprobs = softmax(preds / temp)\n\n\tloss = proxy_anchor(probs, y)  # [36]\n\t\n\tupdate(phi.params)  # Update GNN\n\tupdate(P)  # Update proxy centroids\n```\n**Inference**\n```\n# X: Test images; P: Trained Class Proxies\n\nfor G_c in get_graphloader(X, None, mode='test'):\n\tG_s = phi(G_c)  # semantic relevance graph\n\t# Assignment of instances to proxies\n\tscores = pairwise_hausdorff(G_s, P)  # [59]\n\tpred = argmax(scores,  dim=1)\n```\n**W3 and Q2. Causality** We thank the reviewer for suggesting these insightful experiments on robustness. To this end, we train TRD by replacing a subset of the local views for each instance with local views from other classes, both during training and inference. As the proxies are obtained via a clustering of the instance graphs, these local views consequently influence the proxy graphs. We report our quantitative and qualitative findings in the **pdf attached as part of the global response.**\\\nTRD significantly outperforms Relational Proxies [9] at all noise rates, and the gap between their performances widens as the percentage of corruption increases (Tab 1, attached pdf).\nQualitatively (Fig 1, attached pdf), our model successfully disregards the views introduced from the negative class at both the instance and proxy level. Such views can be seen as being very weakly connected to the global view, as well as the correct set of local views that actually belong to that class.\n**Under this causal intervention, the TRD objective is thus equivalent to performing classification while having access to only the subgraph of clean views from the correct class.**\n\n**Q1. Coarse-grained** Following the reviewer’s suggestion, and existing FGVC literature [9, 19], we evaluate the contribution of our novel Transitivity Recovery objective in the coarse-grained (multiple fine-grained subcategories in a single class) and fine-grained subsets of ImageNet, namely Tiny ImageNet and Dogs ImageNet (Stanford Dogs) and report our findings below. Although our method can surpass existing SoTA in both the settings, larger gains ($\\Delta$) are achieved in the fine-grained setting, suggesting that TRD is particularly well suited for that purpose.\n\n|                            | Tiny ImageNet | Dogs ImageNet |\n|----------------------------|:-------------:|:-------------:|\n| MaxEnt [19]  |     82.29     |     75.66     |\n| Relational Proxies [9]  |     88.91     |     92.75     |\n| $a =$ w/o Transitivity Recovery  |     88.10     |     91.03     |\n| $b =$ with Transitivity Recovery |     89.02     |     93.10     |\n| $\\Delta = (b - a)$                      |      0.92     |    **2.07**   |\n\n**Q3. Bounds** Delta and gamma are not hyperparameters, but intrinsic properties of the dataset, and as such, cannot be controlled explicitly. Respectively, they denote implicit distance and mutual information bounds that the learning process aims to optimize for. We leverage them to prove the theoretical equivalence of existing abstract relational representation learning algorithms and our interpretable version. \nSpecifically, delta is an estimate of the best achievable error (Bayes error rate). Gamma is a way of quantifying the amount of emergence encoded by pairs of views, i.e., how important it is to jointly (rather than  individually) observe the two views in order to determine the global structure of the object.\\\nOne implicit way of controlling both delta and gamma at the level of the dataset is by altering the set of local views. We do this as part of addressing W3 and Q2, by introducing local views from other classes at both the instance and the proxy level, as well as our experiment on Robustness to Noisy Views in the main manuscript. The results show that TRD is able to efficiently optimize for both of these parameters by identifying the most relevant subgraph comprising local views of the target class.\n"}, {"review_id": "yfqJADIMS2", "reviewer": "Reviewer_7SVw", "summary": "The authors propose TRD, an algorithm that decomposes both input images and output classes into graphs over views by recovering transitive cross-view relationships for fine-grained visual categorization.", "questions": "What is the efficiency/time complexity of the proposed method? The proposed TRD needs to construct multiple graphs. Considering the marginal performance gains, is TRD more efficient than Relational Proxies?", "limitations": "The authors discuss the limitations.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well written and easy to follow.\n2. The proposed TRD is demonstrated both theoretically and empirically. ", "weaknesses": "1. It seems that most of the experimental results in Table 1 are copied from the Relational Proxies paper. But the experimental setup seems different. For example, the number of local views is different. \n2. As we know, deep GNNs usually suffer from over-smoothing issue, i.e., as the number of layers increases, the learned representations become nearly indistinguishable and the performance degrades significantly. The authors use an 8-layer GAT with 4 attention heads in each hidden layer. The reviewer wonders how the number of layers affects the performance of your models. Does the over-smoothing phenomenon exist?  \n3. The proposed method seems strongly related to Relational Proxies. Can you explain more about the relationship and difference between these two methods? Moreover, compared with Relational Proxies, the performance gains of TRD are very marginal, as can be seen from Table 1 and Figure 5. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W1. Experimental settings** We agree that the number of local views is the only hyperparameter in which we differ from Relational Proxies, but the remaining settings are the same (Line 264). We note that our experiment on robustness (Figure 5) tests both TRD and Relational Proxies with the same number of views, and TRD can be seen to surpass Relational Proxies in the majority of the cases. Following the reviewer’s suggestion, we evaluate both Relational Proxies and TRD with the same number of local views in the normal (no explicit addition of noise) setting on the FGVC Aircraft dataset, and report our findings in the table below. TRD marginally outperforms Relational Proxies for all values of the number of local views, and exhibits a trend of scaling in accuracy with increasing number of local views. Relational Proxies, on the other hand, does not seem to benefit from increasing the number of local views, possibly due to its lack of robustness to noisy views.\n\n| # Local Views      | 8 | 16 | 32 | 64 |\n|--------------------|:-----------:|:-----------:|:-----------:|:-----------:|\n| Relational Proxies | 95.25     | 95.30     | 95.29     | 95.31     |\n| **TRD (Ours)**     | **95.27** | **95.45** | **95.52** | **95.60** |\n\n**W2. Over-smoothing** We thank the reviewer for suggesting this experiment, as it provides valuable insights into the ability of the GAT in TRD to learn the emergent relationships. We had initially evaluated using GATs of up to 16 layers, and had found the 8 layer version to be the best. Following the reviewer’s suggestion, we have evaluated TRD using GATs of up to 64 layers on FGVC Aircraft, presenting our findings below. We see that the performance does drop beyond 8. To validate whether this is due to the oversmoothing phenomenon, we measure the degree of distinguishability among the nodes by taking the average of their pairwise $L_2$ distances. The table shows that the distinguishability also decreases as we increase the number of layers, suggesting that the over-smoothing phenomenon does occur, as the reviewer had correctly speculated. Incidentally, even under the light of the above experiments, the 8-layer GAT remains an optimal choice for our problem.\n\n| GAT-Depth          |   4   |   8   |   16  |   32  |   64  |\n|--------------------|:-----:|:-----:|:-----:|:-----:|:-----:|\n| Accuracy           | 95.05 | **95.60** | 95.32 | 94.78 | 94.20 |\n| Distinguishability |  0.87 |  0.63 |  0.49 |  0.21 |  0.09 |\n\n**W3. Relational Proxies** The similarity between TRD (proposed) and Relational Proxies is in that they both leverage local-to-global emergent relationships to achieve the sufficiency criterion (Appendix A.3). The main difference lies in the central objectives of the two works. Relational Proxies aims to achieve SoTA performance in FGVC by learning abstract relational representations of local-to-global emergence. On the other hand, we aim to make the process of relational representation learning transparent and interpretable, by performing all computations in terms of graphs representing the learned relationships, while maintaining their performance.\\\nThe trade-off between performance and interpretability is a well-known phenomenon in the literature [29, 67, 21, 35]. However, TRD is not only able to retain the performance of the existing SoTA Relational Proxies, but provide marginal gains as well. This can be attributed to the (provable) robustness of TRD to noisy views. Whatever performance degradation comes from the decomposition of the abstract latent representations into graphs over image views, is recovered by the intrinsic robustness of the transitivity recovery objective. This can be seen in action in Rows 1 - 3 in Table 2 of our Ablation Studies.\\\nTo summarize, **our primary objective is not to surpass SoTA in FGVC, but to provide interpretability to existing SoTA algorithms that leverage relational information to achieve maximal expressivity, while retaining their performance**. The degradation in performance that comes from interpretability is compensated for by the inherent robustness of TRD, allowing us to achieve marginal performance gains over Relational Proxies, even though classification SoTA advancement is not our main objective.\\\nApart from our theoretical analyses (Sections 3.1 and 3.2) establishing the equivalence of abstract relational representation learning algorithms and our proposed TRD, we perform empirical evaluations in the Supplementary Section 3 to extract the instance-level relationships learned by Relational Proxies via a post-hoc explainer. Via TRD, we can obtain such relationships in an ante-hoc manner directly as part of the inference pipeline, without the need for any post-hoc explainers, and not only at the level of the instance, but also for the class.\n\n**Q. Compute Cost** Below we provide the computational costs of Relational Proxies and TRD in terms of wall clock time evaluated on FGVC Aircraft (same experimental settings including  # local views):\n\n|                    | Average Inference Time (ms) | Training Time (hrs) |\n|--------------------|:---------------------------:|:-------------------:|\n| Relational Proxies |             130             |          22         |\n| **TRD (Ours)**     |           **110**           |        **15**       |\n\nWe can see that TRD is significantly more efficient than Relational Proxies in terms of both single sample inference as well as training time until convergence. This is because of the following reasons:\n- The Complementarity Graph in TRD is constructed exactly once before training, and the semantic relevance graph, as well as the proxy graph are learned as part of the training process.\n- TRD does not involve updating the relation-agnostic encoder $f$, which is a ResNet50, as part of the training process. Relational Proxies requires it to be updated, thereby exhibiting computationally heavier forward (as local view embeddings cannot be pre-computed) and backward passes.\n"}, {"review_id": "kSeMiVKbDn", "reviewer": "Reviewer_VJoJ", "summary": "This paper aims at fine-grained representation learning. The authors state that local-to-global relationships leveraged in recent fine-grained visual categorization (FGVC) works are abstract. To make such abstract relational representations more human-understandable, the authors first theoretically show the existence of semantically equivalent graphs for abstract relationships and derive their key information theoretic and topological properties. Then, the authors present Transitivity Recovering Decompositions (TRD), which is a graph-space search algorithm that identifies interpretable equivalents of abstract emergent relationships at both instance and class levels and with no post-hoc computations. The authors run experiments to demonstrate the effectiveness of their methods.", "questions": "Please see weaknesses", "limitations": "The authors mentioned the limitations and societal impacts of their work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "+ This paper is well-written and easy to follow.\n+ The motivation is strong, and the technique in this paper is solid.\n+ The proposed method reaches SOTA performance on standard small, medium, and large scale FGVC benchmarks. The authors conduct ablation studies and present visualization results to show the effectiveness of their method.", "weaknesses": "- The authors state that the local-to-global (emergent) relationships leveraged in existing methods are abstract fashion. However, no detailed and deep explanation for the term \"abstract\" is provided in this paper.\n- The authors propose a graph-based model for fine-grained visual categorization (FGVC) recognition. However, the authors do not provide a comprehensive review of the relevant literature in the field, such as [1-3], and do not compare their approach with other relevant methods in their experiments.\n- The author's comparison seems unfair. In the field of FGVC, a common practice is to resize images to 448$\\times$448, but the authors do not follow this approach. Furthermore, there is a lack of experimental details, which raises concerns about the validity of the experiments. I am unsure whether the pre-trained models used in the study are sourced from ImageNet-1K or ImageNet-21K. Additionally, I find the results of TransFG and FFVT on the Aircraft dataset in Table 1 confusing. While I understand that ViT-based models may have limitations on the current dataset, the reported results seem unexpected.\n\n[1] Where to Focus: Investigating Hierarchical Attention Relationship for Fine-Grained Visual Classification, ECCV22\\\n[2] Weakly Supervised Posture Mining for Fine-Grained Classification, CVPR23\\\n[3] SR-GNN: Spatial Relation Aware Graph Neural Network for Fine-Grained Image Categorization, TIP", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**1. Definition of abstract** Although we briefly refer to what we mean by “abstract” in  Line 23-24, we agree that it requires further elaboration and detailing. We provide an in-depth definition below, which we will also add to the final version.\nExisting works that leverage relational information for representation learning typically adopt the following approaches:\n- Modelling all possible ways the local views can combine to form the global view through a transformer, and distill out the information about the most optimal combination in the summary embedding [8, 9].\n- Modelling the underlying relations through a GNN, but performing an aggregation on its outputs [91, 25]. \\\nBoth 1 and 2 produce vector valued outputs, and such, cannot be decoded in a straightforward way to get an understanding of what the underlying emergent relationships between views are. This lack of transparency is what we refer to as “abstract”. The above set of methods exhibit this abstraction not only at the instance, but at the class-level as well, which also appear as vector-valued embeddings. On the contrary, an interpretable relationship encoder should be able to produce graphs encoding relationships in the input, intermediate and output spaces, while also representing a class as relationships among concepts, instead of single vectors that summarize information about emergence.\n\n**2. Related works** We thank the reviewer for pointing us to the related works [a, b, c], and we apologize for missing these out in our literature survey. The table below shows a performance comparison on the common benchmarks between ours and [a, b, c]. Due to the short rebuttal timeframe, we were unable to evaluate all of these methods on the remainder of our datasets. However, on all of the common datasets, our TRD can still be seen to surpass all of [a, b, c], thanks to its inherent robustness. **Note that we designed TRD not with the objective of classification accuracy improvement, but rather for providing interpretability to existing relational representation based algorithms.** \\\n[a] is a discriminative part discovery based approach and does not involve computing any cross-view relationships. Although both [b] and [c] provide graph-based intermediate image representations, they aggregate the full graph into a single vector-valued output, keeping the final image and class representations abstract.\\\nWe will add the above discussions on [a, b, c] in section 4.3 as well as the below comparison to Table 1 in the final version.\n\n|                  |    CUB    | FGVC Aircraft | Stanford Cars |\n|------------------|:---------:|:-------------:|:-------------:|\n| WhereToFocus [a] |   90.80   |     94.70     |     95.30     |\n| PMRC [b]         |   91.80   |     94.80     |     95.40     |\n| SR-GNN [c]       |   91.90   |     95.40     |     96.10     |\n| **TRD (Ours)**   | **92.10** |   **95.60**   |   **96.35**   |\n\n**3. Input size, pretrained weights, and performance of transformers**\n- Input size - It is true that certain works on FGVC that consider the complete image as the only input to the model do resize the image to 448x448. However, we follow recent SoTA FGVC approaches that use relation-agnostic encoders to extract global and local views [9, 78, 88]. In particular, our view extraction process is exactly the same as Relational Proxies (NeurIPS 2022) [9], with the same input image resolution and backbone (relation-agnostic) encoder. The above approaches first extract the global view from the input image, and crop out local views from that. Since there are two scales at which the image is cropped, all the crops are resized to 224x224. In practice, this provides a similar resolution to resizing the full image to 448x448.\nFollowing the reviewer’s proposition, we have now re-trained and re-evaluated our model with the input images resized to 448x448, keeping the remainder of the process of view extraction the same. Below we provide our results on multiple datasets:\n\n|              |  Soy  | FGVC Aircraft | Stanford Cars |\n|--------------|:-----:|:-------------:|:-------------:|\n| TRD: 224x224 | 52.15 | 95.60         | 96.35         |\n| TRD: 448x448 | 52.23 | 95.62         | 96.39         |\n\nWith the resized input of 448x448, we observe minor improvements in the performance of TRD.\n- Pretrained weights - We thank the reviewer for pointing this out. The ResNet50 that we use as our relation-agnostic encoder were pre-trained on ImageNet1K, following existing literature [9, 78, 88]. We provide the details of our experimental settings in Section 4.1 Experimental Settings and Datasets. If the reviewer feels that we have missed something more, we would be happy to add those details as well.\n- Performance of TransFG and FFVT - Unfortunately, neither TransFG, nor FFVT report results on FGVC Aircraft in their original papers. We found the only evaluation of these methods on FGVC Aircraft to be present in [9]. For the sake of assurance, we reevaluated both TransFG and FFVT on FGVCAircraft and were able to replicate the numbers reported in [9], which is what we also report in the paper. We additionally note that our method also surpasses both TransFG and FFVT by significant margins on all other datasets as well (not just FGVC Aircraft), especially the small scale ones. We conjecture that both FFVT and TransFG being transformer-based models, are not able to cope very well with the small dataset sizes and low sample diversity of FGVC Aircraft (as well as the small scale datasets), leading to relatively lower accuracies.\n\n[a] Where to Focus: Investigating Hierarchical Attention Relationship for Fine-Grained Visual Classification, ECCV22 \\\n[b] Weakly Supervised Posture Mining for Fine-Grained Classification, CVPR23 \\\n[c] SR-GNN: Spatial Relation Aware Graph Neural Network for Fine-Grained Image Categorization, TIP\n"}]

Author rebuttal:
We thank the reviewers for their valuable comments and feedback. We have addressed their individual concerns in their respective rebuttal sections. Here we attach some qualitative results for addressing the comment by Reviewer mGG3 on experimenting with causal interventions.

N.B. It can be observed that we choose FGVC Aircraft for performing some of the experiments requested by the reviewers. Our choice was motivated by the fact that the performance of our model on FGVC Aircraft is generally reflective of the general trends across other datasets, because of its challenging low intra-class and high inter-class similarities. Also, the size of the dataset is reasonable enough for us to complete all the experiments suggested by the reviewers within the rebuttal time frame.


Meta-review: The draft presents a well-defined and theoretically supported Transitivity Recovering Decompositions (TRD) method, with both empirical analysis and comprehensive experiments. The empirical results demonstrate consistent state-of-the-art (SOTA) performance across various Fine-Grained Visual Categorization (FGVC) benchmarks. The writing is clear and coherent, as pointed out by all reviewers. Given the strong motivation, solid technique, and achieved SOTA performance on multiple FGVC benchmarks, along with well-conducted ablation studies and visualization, I recommend accepting this paper. I urge the authors consider to enhance their presentation in accordance with the suggestions outlined by reviewers.
Decision: Accept (poster)