text:
\section{Introduction}

Few-shot classification aims to learn a classifier that can be readily adapted to novel classes given just a small number of labeled instances. To address this problem, a line of previous literature adopts metric-based methods \cite{vinyals2016matching, snell2017prototypical, sung2018learning} that learn a global image representation in an appropriate feature space and use a distance metric to predict their labels.

Recent approaches \cite{zhang2020deepemd, li2019revisiting, lifchitz2019dense} have demonstrated that the significant intra-class variations would inevitably drive the image-level embedding from the same category far apart in a given metric space under low-data regimes. In contrast, densely representative local features can provide transferrable information across categories that have shown promising performances in the few-shot scenario. Among those methods illustrated in Figure \ref{fig:intro}, DN4 \cite{li2019revisiting} finds the nearest neighbor support feature for each query feature and accumulates all the local matches in a Naive-Bayes way to represent an image-to-class similarity; DeepEMD \cite{zhang2020deepemd} uses the earth mover distance to compare the complex structured representations composed of local features. FRN \cite{wertheimer2021few} reconstructs each of query dense features with a linear combination of support dense features in a latent space and use the reconstruction distance to measure the image-to-class relevance. They all follow a unidirectional query-to-support paradigm, whose evident character is an accumulation over all query features followed by a softmax probability.

In this paper, we incorporate an extra support-to-query connection as a complement to thoroughly affiliate two disjoint sets of dense features. The potential offered by this bidirectional paradigm stems from the intuition that, except for using query features to find related support features, it is also plausible to estimate the task-relevance of query features according to the support features. Specifically, we associate dense features with particles that could bidirectionally random walk to the opposite dense features set in the discrete feature space. The prediction probability for each class is then estimated by the dense features' accessibility, \ie, the expected number of visits to the dense features of that class in a time-homogeneous Markov process.

The contributions are as follows: (1) We propose to learn mutual affiliations between the query and support dense features instead of following the unidirectional query-to-support paradigm in FSL. (2) We introduce the dense features' accessibility to FSL and demonstrate that traditional transductive methods could be easily adapted to the inductive setting if we treat dense features from a single query image as a set of unlabeled data. (3) We propose a novel bidirectional random walk based method in FSL and draw its connection to the single-mode eigenvector centrality of an affiliation network. (4) The underlying centrality investigated in this work can be plugged in existing global feature based methods like ProtoNet and RelationNet by highlighting task-centralized local features instead of global average pooling.

\section{Related Work}

\textbf{Dense Feature based FSL.} Those methods focus on learning image-to-image similarities by encoding each input into a set of dense feature vectors (or a feature map). Among them, DC \cite{lifchitz2019dense} proposes to predict for each local features and average their probabilities. DeepEMD \cite{zhang2020deepemd} adopts the earth mover's distance to compute an image-to-class distance. DN4 \cite{li2019revisiting} uses the top-\emph{k} nearest neighbors in a Naive-Bayes way to represent image-level similarities. ADM \cite{li2021asymmetric} and SAML \cite{hao2019collect} use extra network layers for dense classifications. FRN \cite{wertheimer2021few} reconstructs the dense query features from support features of a given class to predict their relevance. Lifchitz \etal \cite{lifchitz2021local} propagates labels from support sets to query features. MCL is also among the family of dense feature based frameworks. A major difference is that we consider the mutual affiliations between the query and support features instead of the unidirectional one in previous work.

\textbf{Graphical models in FSL.} Another branch of methods learns graphs on FSL. Among them, \cite{garcia2017few} build graph neural network (GNN) from a collection of images. \cite{ding2020graph} use the degree-centrality as part of graph features to adjust the weight of graph vertex in transductive FSL. Our proposed feature accessibility of bidirectional random walks is well-related to the eigenvector centrality. Differently, we use the single-mode centrality of bipartite data as a novel criterion for the inductive classification.

\textbf{From Transductive to Inductive.} TPN \cite{liu2019learning} first introduces the well-known label propagation \cite{zhou2003learning} to the transductive FSL that transfers information from labeled data to unlabeled one and shows substantial improvements over inductive methods. Lifchitz \etal\cite{lifchitz2021local} first demonstrates it feasible to adopt label for inductive FSL by treating the query dense features as numerous unlabeled data. Different from unidirectional label propagation, our MCL further considers the set of query and support features as bipartite data where the self-reinforcements (\ie, query-to-query and support-to-support random walks) are avoided.

\section{Method}

\subsection{Formulation of Dense Features based FSL}

In a $N$-way $K$-shot episode, the goal is to predict a class label for a single query image given $N$ support classes, each of which contains $K$ support images for reference.

We first encode each input image into $r$ number of $d$-dimensional dense features $f_\theta(\cdot)\in \mathbb{R}^{d\times r}$. We use $\mathbf{q}=\{q_1, ..., q_r\}$ to denote dense features from a query image. Inspired by prototype learning \cite{snell2017prototypical}, we average feature vectors from the same spatial locations of $K$ different images into support dense features for each $\mathbf{s}^c=\{s_1^c, ..., s_r^c\}$ category.

We use the bold font (\eg, $\mathbf{q}$ and $\mathbf{s}$) to denote a set of feature vectors and use the normal font (\eg, $q$ and $s$) to denote a single feature vector. We use $\mathbf{S}=\bigcup_{c\in C} \mathbf{s}^c$ to represent the union set of dense features from all supporting classes. The cardinalities for the sets $\mathbf{q}$, $\mathbf{s}^c$ and $\mathbf{S}$ are $r$, $r$ and $Nr$ respectively.

The target of dense features based FSL is to find the label of a query image, given its dense query features $\mathbf{q}$ and the union set of dense support features $\mathbf{S}$ from all categories.

\subsection{Bidirectional Random Walks on Dense Features}\label{sec:2.2}

We start by using the \emph{cosine similarity} $\phi(v_1, v_2)= \langle \frac{v_1}{\|v_1\|}, \frac{v_2}{\|v_2\|} \rangle$ to measure the closeness between the two feature vectors where $\langle\cdot,\cdot\rangle$ is the Frobenius inner product.

Given two dense features sets $\mathbf{q}$ and $\mathbf{S}$, we learn inter similarity matrix $\mathbf{\Phi}\in \mathbb{R}^{r\times Nr}$ between those two disjoint sets where the entry of $\left[\mathbf{\Phi}\right]_{qs}=\phi(q, s)$ indicates the similarity between vectors $q\in \mathbf{q}$ and $s\in \mathbf{S}$.

We build query-to-support affiliations from every query feature $q$ to all support features $s\in \mathbf{S}$ by a random walk probability $p_{sq}=\frac{e^{\gamma\phi(s, q)}}{\sum_{s'\in \mathbf{S}}e^{\gamma\phi(s', q)}}$. The probability matrix from all query to support features can be written by
\begin{equation}\label{eq:SIM_sq}
    \mathbf{P}_\mathbf{Sq} = \mathrm{exp}(\gamma\mathbf{\Phi}^\mathrm{T}) \mathbf{D}^{-1}
\end{equation}
where $\mathrm{exp}(\cdot)$ is the element-wise exponential function, $\gamma$ is a scaling temperature for a softmax like probability and $\mathbf{D}$ is a diagonal normalization matrix with its $(j, j)$-value to be the sum of the $j$-th column of $\mathrm{exp}(\gamma\mathbf{\Phi}^\mathrm{T})$. The subscript serves both as the matrix size and as an indication for the feature vector with which it is associated. For example, $\mathbf{P}_{\mathbf{Sq}}$ is of size $|\mathbf{S}|\times |\mathbf{q}|$ and it includes random walk probabilities from query features $\mathbf{q}$ to support features $\mathbf{S}$.

Likewise, we connect every support feature $s$ to all $q\in \mathbf{q}$ by a similar probability matrix:
\begin{equation}\label{eq:SIM_qs}
    \mathbf{P}_\mathbf{qS} = \mathrm{exp}(\beta\mathbf{\Phi}) \mathbf{W}^{-1}
\end{equation}
where $\mathbf{W}$ is the analogous diagonal matrix with its $(j, j)$-value to be the sum of the $j$-th column of $\mathrm{exp}(\beta\mathbf{\Phi})$.

It should be noted that we use two different scaling parameters since $\mathbf{\Phi}$ is a non-square matrix due to the different cardinalities of dense feature sets $\mathbf{q}$ and $\mathbf{S}$. Although the matrices $\mathrm{exp}(\gamma\mathbf{\Phi}^\mathrm{T})$ and $\mathrm{exp}(\beta\mathbf{\Phi})$ would be symmetric if we ignore their different scaling parameters, the probability matrices $\mathbf{P}_\mathbf{qS}$, $\mathbf{P}_\mathbf{Sq}$ are both column-normalized by different $\mathbf{D}$, $\mathbf{W}$ respectively and are thus directional.

To learn the mutual affiliations between the two dense feature sets, we first associate each feature vector with a particle $z$ that forms a discrete feature space $\mathbf{z} = \mathbf{q} \cup \mathbf{S}$. Next, we let particles bidirectionally random walk between particles in that space according to $\mathbf{P}_\mathbf{Sq}$ and $\mathbf{P}_\mathbf{qS}$ (\ie, particles at query features set are only allowed to move to the support features set, and vice versa). We assume it time-homogeneous in a Markov process $\{X_t\}$ and the random walk probability from $z_j$ to $z_i$ for all $z_i$, $z_j$ in $\mathbf{z}$ can be formulated by:
\begin{equation}\label{eq:3}
\resizebox{\hsize}{!}{%
$\mathbf{Pr}(X_{t+1} = z_i | X_{t}= z_j) = \left\{
\renewcommand{\arraystretch}{1.2}
\begin{array}{ll}
\displaystyle{\frac{e^{\gamma\phi(z_i, z_j)}}{\sum_{s\in \mathbf{S}} e^{\gamma\phi(s, z_j)}}} & \hspace{-5pt}z_i\in \mathbf{S}, z_j \in \mathbf{q} \\
\displaystyle{\frac{e^{\beta\phi(z_i, z_j)}}{\sum_{q\in \mathbf{q}} e^{\beta\phi(q, z_j)}}} & \hspace{-5pt}z_i\in \mathbf{q}, z_j \in \mathbf{S} \\ 0 & \hspace{-5pt}\mathrm{otherwise}.
\end{array}
\right.
$}
\end{equation}

To write it in matrix, we can obtain the Markov transition matrix $\mathbf{P}$:
\begin{equation}\label{eq:prop}
    \mathbf{P}=\begin{pmatrix}
    \mathbf{0} & \mathbf{P}_{\mathbf{S}\mathbf{q}} \\
    \mathbf{P}_{\mathbf{q}\mathbf{S}} & \mathbf{0}
    \end{pmatrix}
\end{equation}
that consists of the column-normalized $\mathbf{P}_\mathbf{Sq}$ and $\mathbf{P}_\mathbf{qS}$.

It can be proved (in supplementary) that, after infinity times of bidirectional random walks, the Markov chain with anti-diagonal $\mathbf{P}$ reaches the periodic stationary distribution:
\begin{align}\label{eq:stationary}
\begin{split}
    \lim_{t\rightarrow\infty} \mathbf{P}^{2t} &= \begin{pmatrix}
    \boldsymbol{\pi}(\mathbf{S})\bm{e}_{Nr}^\mathrm{T} & \mathbf{0} \\
     \mathbf{0} & \boldsymbol{\pi}(\mathbf{q})\bm{e}_{r}^\mathrm{T}
    \end{pmatrix} \\
    \lim_{t\rightarrow\infty} \mathbf{P}^{2t-1} &= \begin{pmatrix}
    \mathbf{0} & \boldsymbol{\pi}(\mathbf{S})\bm{e}_{r}^\mathrm{T}  \\
     \boldsymbol{\pi}(\mathbf{q})\bm{e}_{Nr}^\mathrm{T} & \mathbf{0}
    \end{pmatrix}
\end{split}
\end{align}
where $\boldsymbol{\pi}(\mathbf{S})\in \mathbb{R}^{Nr}$, $\boldsymbol{\pi}(\mathbf{q})\in \mathbb{R}^r$ are the stationary distributions with equations $\boldsymbol{\pi}(\mathbf{S}) = \mathbf{P_{Sq}}\mathbf{P_{qS}}\boldsymbol{\pi}(\mathbf{S})$ and $\boldsymbol{\pi}(\mathbf{q}) = \mathbf{P_{qS}P_{Sq}}\boldsymbol{\pi}(\mathbf{q})$ respectively. $\bm{e}_{|\cdot|}$ is a vector of ones with different length indicated by its subscript.

The motivation of using these stationary distributions to encode mutual affiliations is straightforward: support features would be frequently visited in the long times of bidirectional random walk if they shared the same local characteristics with the query ones. In other words, the support class that owns the most mutual affiliations with querying image would be predicted due to their mutual closeness.

\subsection{Classification by Dense Features' Accessibility}

To formulate it in FSL, we first assume particles are uniformly distributed in the discrete finite space $\mathbf{z}$. Then, we use the expected number of visits from all particles $z\in \mathbf{z}$ to support features $\mathbf{s}^{c}\subset \mathbf{S}$ of class $c$ in the long times of bidirectional random walks $\{X_t\}$ to measure the amount of local characteristics that class $c$ owns for the query image:
\begin{equation}
\resizebox{\linewidth}{!}{%
$\begin{aligned}[b]\label{eq:MEL}%
&\mathbf{Pr}(\tilde{y} = c) \propto \lim_{t\rightarrow\infty}\sum_{z\in\mathbf{z}}\mathbb{E} \left[\sum_{k=1}^t\mathds{1}[X_k\in \mathbf{s}^c] \bigg| X_0=z\right]  \\
&= \lim_{t\rightarrow\infty} \frac{1}{t}\sum_{k=1}^{t}\left[\frac{1}{Nr+r}\sum_{s\in \mathbf{s}^c}\left(\sum_{s'\in \mathbf{S}}\left[\mathbf{P}^{2k}\right]_{ss'} + \sum_{q\in \mathbf{q}}\left[\mathbf{P}^{2k-1}\right]_{sq}\right)\right]  \\
&= \frac{1}{Nr+r} \sum_{s\in \mathbf{s}^c}\left(\sum_{s'\in \mathbf{S}}\left[\lim_{t\rightarrow \infty}\mathbf{P}^{2t}\right]_{ss'} + \sum_{q\in \mathbf{q}}\left[\lim_{t\rightarrow \infty}\mathbf{P}^{2t-1}\right]_{sq}\right)  \\
&=\sum_{s\in \mathbf{s}^c} \left[\boldsymbol{\pi}(\mathbf{S})\right]_s
\end{aligned}
$}
\end{equation}
where $\mathds{1}[\cdot]$ is an indicator function that equals 1 if its argument is true and zero otherwise. $[\cdot]_{ij}$ indicates the entry of the matrix from particle $j$ to particle $i$ and $[\cdot]_{i}$ indicates the entry of the vector that associated to feature $i$.

We give the derivation when the Markov chain length $t$ is even in the first equality of Eqn.(\ref{eq:MEL}) and prove that the odd $t$ reaches the same result in the supplementary material. The second equality is from the \emph{absorbing} property of the periodic Markov chain where the power of matrix gets saturated to Eqn.(\ref{eq:stationary}) for the increasing $t$. Since $\boldsymbol{\pi}(\mathbf{S})$ is the stationary distribution of column-stochastic $\mathbf{P_{Sq}P_{qS}}$ under the probability constraint $\bm{e}^\mathrm{T}_{Nr}\boldsymbol{\pi}(\mathbf{S})=1$, $\mathbf{Pr}(\tilde{y})$ is a valid distribution for classifications.

\subsection{Reinterpretation as a Graph Centrality} \label{sec:interp}

If we interpret the random walk probability matrix $\mathbf{P}$ as an adjacency matrix $\{a_{v_1,v_2}\}$ of a directed bipartite graph $G:=(V=\{\mathbf{q}, \mathbf{S}\}, E)$, we find that the dense features' accessibility in the time-homogeneous bidirectional random walk would be equivalent to learning a \emph{single-mode eigenvector centrality} on the graph $G$. The bipartite graph is also called the \emph{affiliation network} in social network analysis \cite{bonacich1972factoring, bonacich1991simultaneous, borgatti1997network} that models two types of entities "\emph{actors}" and "\emph{society}" related by affiliation of the former in the latter. The concept of centrality in social network analysis is generally used to investigate the acquaintanceships among people that often stem from one or more shared affiliations.

To see this in graph theory, we start with a brief overview of the eigenvector centrality that reflects score $x$ of vertex $v$ for both $q\in \mathbf{q}$ and $s\in \mathbf{S}$ in the affiliation network with adjacency $\{a_{v_1,v_2}\}$:
\begin{align}\label{eq:centrality}
\begin{split}
    x_q&=\frac{1}{\lambda} \sum_{v\in \mathbb{V}(q)}a_{q, v}x_v=\frac{1}{\lambda}\sum_{v\in \mathbf{S}}a_{q, v}x_v \\      x_s&=\frac{1}{\lambda} \sum_{v\in \mathbb{V}(s)}a_{s, v}x_v=\frac{1}{\lambda}\sum_{v\in \mathbf{q}}a_{s, v}x_v
\end{split}
\end{align}
where $\mathbb{V}(\cdot)$ is a set of neighbors for the given vertex and $\lambda$ is a constant.

With a small rearrangement, Eqn.(\ref{eq:centrality}) can be rewritten in vector notation with an eigenvector equation $\mathbf{Px} = \lambda \mathbf{x}$. The additional requirement that all the entries of the eigenvector be non-negative implies (by the Perron–Frobenius theorem \cite{perron1907theorie}) that only the greatest eigenvalue results in the desired centrality measure. For the column-stochastic adjacency matrix $\mathbf{P}$ in our method, the largest eigenvalue $\lambda$ is 1.

Single-mode centrality \cite{borgatti1997network} is a special form of graph centrality that measures the extent to which nodes in one vertex set are relatively central only to other nodes in the same vertex set on bipartite graph. For example, the single-mode centrality for different $s$ in $\mathbf{S}$ is defined by $\hat{\mathbf{x}}_\mathbf{S}=\mathbf{x}_\mathbf{S} / \sum_{s\in \mathbf{S}}x_s$. Lemma \ref{lemm:1} (proved in supplementary material) shows that dense features' accessibility $\boldsymbol{\pi}(\mathbf{S})$ of bidirectional random walks in Eqn.(\ref{eq:MEL}) is equivalent to the single-mode eigenvector centrality of support set $\mathbf{S}$ on bipartite data.

\begin{lemm}\label{lemm:1}
Assume $G$ is the affiliation network of bipartite data $\mathbf{q}$, $\mathbf{S}$ with the adjacency matrix defined by the anti-diagonal Markov transition matrix $\mathbf{P}$ in Eqn.(\ref{eq:prop}). The single-mode eigenvector centrality $\hat{\mathbf{x}}_{\mathbf{S}}=\mathbf{x}_\mathbf{S} / \sum_{s\in \mathbf{S}}x_s$ of vertex set $\mathbf{S}$ is equivalent to the dense features' accessibility $\boldsymbol{\pi}(\mathbf{S})$ on $\mathbf{S}$ in a time-homogeneous Markov process.
\end{lemm}

Based on this reinterpretation, it is straightforward to introduce the attenuation (damping) factor $\alpha$ in Markov bidirectional random walks motivated by the Katz centrality \cite{katz1953new}, where connections made with distant neighbors are penalized by $\alpha$. The dense features' accessibility with attenuation factor $\alpha$ for few-shot classifications is defined by
\begin{align}\label{eq:katz}
\begin{split}
&\mathbf{P}\mathbf{r}_\mathrm{Katz}(\tilde{y}=c) \propto \sum_{z\in\mathbf{z}}\mathbb{E} \left[\sum_{t=1}^\infty\alpha^t\mathds{1}[X_t\in \mathbf{s}^c] \bigg| X_0=z\right]\\
&= \frac{1}{\epsilon}\sum_{t=1}^{\infty}\sum_{s\in \mathbf{s}^c}\left(\sum_{s'\in \mathbf{S}}\left[\alpha^{2t}\mathbf{P}^{2t}\right]_{ss'}+\sum_{q\in \mathbf{q}} \left[\alpha^{2t-1}\mathbf{P}^{2t-1}\right]_{sq}\right)
\end{split}
\end{align}
where $\epsilon=(Nr + r)\sum_{t=1}^{\infty}\alpha^t=(Nr+r)\alpha / (1 - \alpha)$ is a constant for a valid distribution.

Although we simply consider the single-mode centrality on $\mathbf{S}$ for an end-to-end classification purpose, it is also beneficial to learn its conjugate centrality $\boldsymbol{\pi}(\mathbf{q})$ on $\mathbf{q}$ in the affiliation network (by the analogous $\boldsymbol{\pi}(\mathbf{q})=\mathbf{x}_\mathbf{q} / \sum_{q\in\mathbf{q}}x_q$ in Lemma \ref{lemm:1}). We will show that both single-mode centralities on two dense features sets could serve as plug-and-play for finding centralized local characteristics in existing methods (hence the term Mutual Centralized Learning, MCL).

\subsection{End-to-End Training by Katz Approximation}\label{sec:MEL}

The algorithm of Mutual Centralized Learning (MCL) in Eqn.(\ref{eq:MEL}) involves the computation of Markov stationary distribution $\boldsymbol{\pi}(\mathbf{S})$ with equation $\boldsymbol{\pi}(\mathbf{S}) = \mathbf{P_{Sq}P_{qS}} \boldsymbol{\pi}(\mathbf{S})$. Theoretically, the $\boldsymbol{\pi}(\mathbf{S})$ is the eigenvector of $\mathbf{P_{Sq}P_{qS}}$ with the eigenvalue 1 under a probability constraint $\bm{e}_{Nr}^\mathrm{T}\boldsymbol{\pi}(\mathbf{S})=1$.

The above constraints could lead to a solution of $\boldsymbol{\pi}(\mathbf{S})$ by solving the overdetermined linear system
\begin{equation}\label{eq:overdetermined}
\begin{pmatrix}
\mathbf{P_{Sq}P_{qS}} - \bm{I} \\
\bm{e}^\mathrm{T}_{Nr}
\end{pmatrix}
\boldsymbol{\pi}(\mathbf{S}) =
\begin{pmatrix}
\mathbf{0} \\
1
\end{pmatrix}
\end{equation}
where $\bm{I}$ is an identity matrix and $\mathbf{0}$ is a vector of zeros. Although we can solve it by various methods like pseudo-inverse or QR decomposition and back substitution, it is empirically found time-consuming as these operators are either numerically unstable or not paralleled well in modern deep-learning packages.

To handle it, we present an alternative solution based on Lemma \ref{lemm:1} as follows: We first calculate the Katz centrality by its closed-form solution \cite{katz1953new}:
\begin{equation}\label{eq:katz_c}
\mathbf{x}^\mathrm{Katz} = ((\bm{I} - \alpha \mathbf{P})^{-1} - \bm{I})\bm{e}_{Nr+r}
\end{equation}
and then solve single-mode Katz centrality in Eqn.(\ref{eq:katz}) by the definition of the single-mode centrality:
\begin{equation}
    \mathbf{Pr}_\mathrm{Katz}(\tilde{y}=c) = \frac{\sum_{s\in \mathbf{s}^c}\mathbf{x}^\mathrm{Katz}_s}{\sum_{s'\in \mathbf{S}}\mathbf{x}^\mathrm{Katz}_{s'}}
    \label{eq:katz_c_2}
\end{equation}

Since Katz centrality degrades to the eigenvector centrality when $\alpha$ approaches 1 \cite{katz1953new} (indicates no attenuation), we can obtain the approximation of eigenvector centrality by a large $\alpha=0.999$:
\begin{align}\label{eq:eigen_c}
\begin{split}
    \mathbf{x}^\mathrm{Eigen} &= \lim_{\alpha\rightarrow 1}((\bm{I} - \alpha\mathbf{P})^{-1} - \bm{I})\bm{e}_{Nr+r} \\
    &\approx ((\bm{I} - 0.999 \mathbf{P})^{-1} - \bm{I})\bm{e}_{Nr+r}
\end{split}
\end{align}
and the analogous single-mode eigenvector centrality in Eqn.(\ref{eq:MEL}) can then be approximated by:
\begin{equation}
    \mathbf{Pr}_\mathrm{MCL}(\tilde{y}=c) = \frac{\sum_{s\in \mathbf{s}^c}\mathbf{x}^\mathrm{Eigen}_s}{\sum_{s'\in \mathbf{S}}\mathbf{x}^\mathrm{Eigen}_{s' }} \label{eq:mel_final}
\end{equation}

We use the negative log-likelihood loss to update parameters in different feature extractors and the whole picture of MCL for few-shot classifications is shown in Figure \ref{fig:arch}. We provide the detailed algorithm/pseudo-codes in the supplementary material for reference.

\begin{figure*}[t]
    \centering
     \includegraphics[width=\textwidth]{figs/arch-crop.pdf}
     \caption{Our framework for 3-way 1-shot classification. Given the query and support images, we first extract their dense features $\mathbf{q}$ and $\mathbf{S}$ which are two sets of feature vectors. Then we calculate their similarity matrix $\mathbf{\Phi}$. After that, we build probability matrix $\mathbf{P}$ based on the scaled and column-normalized similarity matrix. We obtain the stationary distributions $\boldsymbol{\pi}(\mathbf{S})$ and $\boldsymbol{\pi}(\mathbf{q})$ by the Katz approximation in Eqn.(\ref{eq:eigen_c}) and the Lemma \ref{lemm:1}. Finally, we use them for both end-to-end FSL and as a centrality plugin in global feature based FSL. We explore three dense feature extractors (\ie, \textit{VanillaFCN}, \textit{PyramidFCN}, \textit{PyramidGrid}) inspired by \cite{zhang2020deepemd} to extract dense feature representations.}
     \label{fig:arch}
\end{figure*}

\subsection{Plugin for Global Feature based FSL.\label{sec:plug}}

Since the underlying centrality learned by MCL reveals the different importance of local features on an affiliation network, it is thus plausible to plug it into global feature based methods by replacing their native global average pooling (GAP) with the centrality weighted pooling as follows:

a. Extract dense features for each input image.

b. Compute the eigenvector centrality $\mathbf{x}^\mathrm{Eigen}$ by Eqn.(\ref{eq:eigen_c}).

c. Compute $\boldsymbol{\pi}(\mathbf{S})$ and $\boldsymbol{\pi}(\mathbf{q})$ according to definition of the single-mode centrality in Lemma \ref{lemm:1}.

d. Use $\boldsymbol{\pi}(\mathbf{q})$ as weights on query dense features and weighted accumulate them to a single feature vector.

e. Use the class-wise normalized centrality from $\boldsymbol{\pi}(\mathbf{S})$ to accumulate dense features for each supporting class.

Once we get the centrality weighted features for the query image and support classes, it is straightforward to perform traditional global feature based methods like before.

\section{Experiments}

We conduct experiments on two widely-used FSL datasets and three fine-grained datasets: (1) \textbf{\textit{mini}ImageNet} \cite{vinyals2016matching} contains 600 images per class over 100 classes. We follow the split used by \cite{sachin2017optimization} that takes 64, 16 and 20 classes for train/val/test respectively; (2) \textbf{\textit{tiered}ImageNet} \cite{ren2018meta} is much larger compared to \textit{mini}ImageNet with 608 classes. The 351, 97 and 160 classes are used for train/val/test respectively. (3) \textbf{CUB} \cite{welinder2010caltech} consists 11,788 images from 200 bird classes. 100/50/50 classes are used for train/val/test and each image is first cropped to a human-annotated bounding box. (4) \textbf{meta-iNat} \cite{wertheimer2019few} is a benchmark of animal species in the wild. We follow the same class split proposed by \cite{wertheimer2019few} that uses 908/227 classes for training/evaluation respectively. (5) \textbf{\textit{tiered}-meta-iNat} \cite{wertheimer2019few} is a more difficult version of meta-iNat where a large domain gap is introduced. The 354 test classes are populated by insects and arachnids, while the remaining 781 classes form the training set.

\textbf{Backbone networks.} We conduct experiments with both widely-used four layer convolutional Conv-4 \cite{vinyals2016matching} and deep ResNet-12 \cite{sun2019meta} backbones. As is commonly implemented in the state-of-the-art FSL literature, we adopt a pre-training stage for the ResNet-12 before the episode meta-training while directly meta-train from scratch for the simple Conv-4.

\textbf{Dense feature extractor $f_\theta(\cdot)$.} We explore three dense feature extractors in our experiments as shown in Figure \ref{fig:arch}: (1) \textit{VanillaFCN} simply treats the feature map output of fully convolutional network as dense features. (2) \textit{PyramidFCN} uses an extra adaptative average pooling layer to obtain 34 dense features for each image. (3) \textit{PyramidGrid} crops the image evenly into the grid of size $2\times 2 + 3\times 3$ and encodes each grid cell to a feature vector individually. The feature vectors from all the cells constitute the set of dense features.

\begin{table*}[t]
\centering
\small
\setlength{\tabcolsep}{6pt}
\aboverulesep=0ex
\belowrulesep=0.5ex
\renewcommand\arraystretch{1}
\newcommand{\cellcolor{Gray}}{\cellcolor{Gray}}
\begin{tabular}{cccccccccc}
\toprule
\multicolumn{2}{c}{\multirow{3}{*}{\textbf{Method}}} & \multicolumn{4}{c}{\textbf{Conv-4}}                                             & \multicolumn{4}{c}{\textbf{ResNet-12}} \\
\multicolumn{2}{c}{}                        & \multicolumn{2}{c}{\textit{mini}ImageNet} & \multicolumn{2}{c}{\textit{tiered}ImageNet} & \multicolumn{2}{c}{\textit{mini}ImageNet} & \multicolumn{2}{c}{\textit{tiered}ImageNet} \\ \cmidrule(lr){3-4} \cmidrule(lr){5-6} \cmidrule(lr){7-8} \cmidrule(lr){9-10}
\multicolumn{2}{c}{}                        & 1-shot          & 5-shot         & 1-shot           & 5-shot          & 1-shot          & 5-shot         & 1-shot           & 5-shot          \\ \midrule
\multirow{9}{*}{\textit{Global features}} & DSN \cite{simon2020adaptive} & 51.78 & 68.99 & 53.22 & 71.06 & 62.64 & 78.83 & 67.39 & 82.85 \\
 & MetaOptNet \cite{lee2019meta} & 52.87 & 68.76 & 54.71 & 71.76 & 62.64 & 78.63 & 65.99 & 81.56 \\
 & Negative Margin \cite{liu2020negative} & 52.84 & 70.41 & - & - & 63.85 & 81.57 & - & - \\
& FEAT \cite{ye2020few} & 55.15 & 71.61 & - & - & 66.78 & 82.05 & 70.80 & 84.79 \\
& Meta-Baseline \cite{chen2020new} & - & - & - & - & 63.17 & 79.26 & 68.62 & 83.29 \\
 & RelationNet$^\ddagger$ \cite{sung2018learning} & 52.12 & 66.90 & 54.33 & 69.95 & 60.97 & 75.12 & 64.71 & 78.41 \\
 & \cellcolor{Gray} RelationNet+MCL & \cellcolor{Gray} \textit{54.50} & \cellcolor{Gray} \textit{70.63} & \cellcolor{Gray} \textit{57.73} & \cellcolor{Gray} \textit{74.46} & \cellcolor{Gray} \textit{61.70} & \cellcolor{Gray} \textit{75.53} & \cellcolor{Gray} \textit{65.93} & \cellcolor{Gray} \textit{80.27} \\
 & ProtoNet$^\ddagger$ \cite{snell2017prototypical} & 52.32 & 69.74 & 53.19 & 72.28 & 62.67 & 77.88 & 68.48 & 83.46 \\
 & \cellcolor{Gray} ProtoNet+MCL & \cellcolor{Gray} \textit{54.31} & \cellcolor{Gray} \textit{69.84} & \cellcolor{Gray} \textit{56.67} & \cellcolor{Gray} \textit{74.36} & \cellcolor{Gray} \textit{64.40} & \cellcolor{Gray} \textit{78.60} & \cellcolor{Gray} \textit{70.62} & \cellcolor{Gray} \textit{83.84} \\
 \midrule
\multirow{6}{*}{\makecell{\textit{Dense features}\\(\textit{VanillaFCN})}} & DN4$^\ddagger$ \cite{li2019revisiting} & 54.66 & 71.26 & 56.86 & 72.16 & 65.35 & 81.10 & 69.60 & 83.41 \\
& DeepEMD$^\dagger$ \cite{zhang2020deepemd} & 52.15 & 65.52 & 50.89 & 66.12 & 65.91 & 82.41 & 71.16 & 83.95 \\
& FRN$^\dagger$ \cite{wertheimer2021few} & 54.87 & 71.56 & 55.54 & 74.68 & 66.45 & 82.83 & 71.16 & 86.01 \\
& Label Propagation & 52.24 & 67.68 & 54.56 & 70.08 & 65.00 & 80.07 & 71.12 & 83.89 \\
& \cellcolor{Gray} MCL (ours) & \cellcolor{Gray} 55.38 & \cellcolor{Gray} 70.02 & \cellcolor{Gray} 57.63 & \cellcolor{Gray} 74.25 & \cellcolor{Gray} 67.36 & \cellcolor{Gray} 83.63 & \cellcolor{Gray} 71.76 & \cellcolor{Gray} 86.01 \\
& \cellcolor{Gray} MCL-Katz (ours) & \cellcolor{Gray} \textbf{55.55} & \cellcolor{Gray} \textbf{71.74} & \cellcolor{Gray} \textbf{57.78} & \cellcolor{Gray} \textbf{74.77} & \cellcolor{Gray} \textbf{67.51} & \cellcolor{Gray} \textbf{83.99} & \cellcolor{Gray} \textbf{72.01} & \cellcolor{Gray} \textbf{86.02} \\
\midrule
\multirow{6}{*}{\makecell{\textit{Dense features}\\(\textit{PyramidFCN})}} & DN4$^\ddagger$ \cite{li2019revisiting} & 54.54 & 70.94 & 57.05 & 72.90 & 63.54 & 79.04 & 71.10 & 84.22 \\
& DeepEMD$^\ddagger$ \cite{zhang2020deepemd} & 50.67 & 64.94 & 51.26 & 65.64 & 66.27 & 82.41 & 70.76 & 84.20 \\
& FRN$^\ddagger$ \cite{wertheimer2021few} & 54.40 & 70.75 & 57.30 & \textbf{75.58} & 65.94 & 81.97 & 70.56 & 85.44 \\
& Label Propagation & 53.38 & 68.69 & 55.21 & 71.22 & 65.71 & 75.78 & 71.00 & 78.01 \\
& \cellcolor{Gray} MCL (ours) & \cellcolor{Gray} 55.13 & \cellcolor{Gray} 70.77 & \cellcolor{Gray} 57.93 & \cellcolor{Gray} 74.36 & \cellcolor{Gray} 67.45 & \cellcolor{Gray} 84.36 & \cellcolor{Gray} 72.01 & \cellcolor{Gray} 86.31 \\
& \cellcolor{Gray} MCL-Katz (ours) & \cellcolor{Gray} \textbf{55.77} & \cellcolor{Gray} \textbf{71.24} & \cellcolor{Gray} \textbf{58.20} & \cellcolor{Gray} 74.73 & \cellcolor{Gray} \textbf{67.85} & \cellcolor{Gray} \textbf{84.47} & \cellcolor{Gray} \textbf{72.13} & \cellcolor{Gray} \textbf{86.32} \\
\midrule
\multirow{6}{*}{\makecell{\textit{Dense features}\\(\textit{PyramidGrid})}} & DN4$^\ddagger$ \cite{li2019revisiting} & 57.17 & 70.91 & 56.71 & 70.92 & 67.86 & 80.08 & 71.29 & 82.60 \\
& DeepEMD$^\ddagger$ \cite{zhang2020deepemd} & 55.68 & 70.75 & 55.88 & 70.06 & 67.83 & 81.32 & 73.13 & 84.18 \\
& FRN$^\ddagger$ \cite{wertheimer2021few} & 55.80 & 71.52 & 55.68 & 72.87 & 67.00 & 82.20 & 71.42 & 85.58 \\
& Label Propagation & 55.12 & 68.43 & 56.05 & 72.39 & 67.18 & 81.07 & 73.18 & 85.19 \\
& \cellcolor{Gray} MCL (ours) & \cellcolor{Gray} 57.50 & \cellcolor{Gray} 73.03 & \cellcolor{Gray} 57.57 & \cellcolor{Gray} 73.81 & \cellcolor{Gray} \textbf{69.31} & \cellcolor{Gray} \textbf{85.11} & \cellcolor{Gray} \textbf{73.62} & \cellcolor{Gray} \textbf{86.29} \\
& \cellcolor{Gray} MCL-Katz (ours) & \cellcolor{Gray} \textbf{57.88} & \cellcolor{Gray} \textbf{74.03} & \cellcolor{Gray} \textbf{57.63} & \cellcolor{Gray} \textbf{73.96} & \cellcolor{Gray} 69.25 & \cellcolor{Gray} 84.71 & \cellcolor{Gray} 73.38 & \cellcolor{Gray} 86.21 \\
\bottomrule
\end{tabular}
\caption{Few-shot classification accuracy (\%) on \textit{mini}ImageNet and \textit{tiered}ImageNet. The 95\% confidence intervals are all below 0.2 for the 10,000 episodes evaluation. Results of \textit{italic} font indicates the performance of MCL as a plugin. Results of \textbf{bold} fonts are the best results for different dense feature extractors, respectively. We re-implement our plugin baseline methods (\ie, ProtoNet and RelationNet) as well as the competitive dense features based methods (\ie, DN4, DeepEMD and FRN) in our unified framework in case their performances are not available under specific settings. $\dagger$: re-implemented results on Conv-4 backbone, $\ddagger$: re-implemented results on both backbones. \label{tab:sota}}
\end{table*}

\subsection{General Few-shot Classification Results}

Table \ref{tab:sota} details the comparisons of MCL with global feature based methods \cite{simon2020adaptive,lee2019meta,ye2020few, chen2020new, liu2020negative} as well as dense feature based methods \cite{li2019revisiting, zhang2020deepemd, wertheimer2021few} on \textit{mini}-/\textit{tiered}ImageNet.

Besides these methods, we also exploit label propagation \cite{zhou2003learning} in dense feature based inductive FSL like in \cite{lifchitz2021local} to demonstrate that traditional transductive methods could be easily adapted to inductive settings if we treat dense feature vectors as a set of unlabeled data. As shown, our MCL is highly competitive with recent state-of-the-art results. In particular, our MCL-Katz achieves \textbf{67.51}\% (1-shot) and \textbf{83.99}\% (5-shot) on \textit{mini}ImageNet with the simplest \textit{VanillaFCN}.

\textbf{Comparisons with dense feature based methods.} The last three panes of Table \ref{tab:sota} illustrate that proposed bidirectional MCL outperforms query-to-support DN4's nearest neighboring, DeepEMD's optimal matching and FRN's latent feature reconstructions in various tasks. Although the optimal matching flow is unidirectional in DeepEMD, they adopt a cross-reference attention that encodes the bidirectional relevance to a certain extent. If we treat dense features as \textit{nodes} in the graph and use their similarities as \textit{edges}, a major difference is that they treat nodes equally to derive different weights on edges while we use the fixed edges to derive the centrality of nodes directly for classifications.

\textbf{Comparisons with global feature based methods.} The centrality investigated in this work is also capable to be plugged into global feature based methods as local features are not equally important before global average pooling. As shown in the first pane of Table \ref{tab:sota}, our proposed centrality weighted pooling could provide at most \textbf{3.4}\% and \textbf{4.5}\% performance gains for ProtoNet and RelationNet respectively.
We show in Table \ref{tab:plug} that the improvements are also consistent if we solely apply it on the query and support dense features.

\begin{table*}[]
\centering
\small
\setlength{\tabcolsep}{5pt}
\aboverulesep=0ex
\belowrulesep=0.5ex
\renewcommand\arraystretch{1}
\begin{tabular}{ccccccccccccc}
\toprule
\multirow{3}{*}{\textbf{Method}} & \multicolumn{4}{c}{\textbf{CUB}} & \multicolumn{4}{c}{\textbf{meta-iNat}} & \multicolumn{4}{c}{\textbf{\textit{tiered}-meta-iNat}} \\
 & \multicolumn{2}{c}{Conv-4} & \multicolumn{2}{c}{ResNet-12} & \multicolumn{2}{c}{Conv-4} & \multicolumn{2}{c}{ResNet-12} & \multicolumn{2}{c}{Conv-4} & \multicolumn{2}{c}{ResNet-12} \\
\cmidrule(lr){2-3} \cmidrule(lr){4-5} \cmidrule(lr){6-7} \cmidrule(lr){8-9} \cmidrule(lr){10-11} \cmidrule(lr){12-13}
 & 1-shot & 5-shot & 1-shot & 5-shot & 1-shot & 5-shot & 1-shot & 5-shot & 1-shot & 5-shot & 1-shot & 5-shot \\
 \midrule
ProtoNet \cite{snell2017prototypical} & 71.64 & 81.50 & 82.98 & 91.38 & 53.78 & 73.80 & 76.47 & 90.20 & 35.47 & 54.85 & 47.61 & 71.06 \\
ProtoNet + MCL & \textit{76.87} & \textit{86.95} & \textit{84.59} & \textit{91.71} & \textit{57.52} & \textit{74.33} & \textit{78.75} & \textit{90.53} & \textit{39.09} & \textit{59.16} & \textit{51.22} & \textit{72.50} \\
DSN \cite{simon2020adaptive} & 66.01 & 85.41 & 80.80 & 91.19 & 58.08 & 77.38 & 78.80 & 89.77 & 36.82 & 60.11 & 46.61 & 72.79 \\
CTX \cite{doersch2020crosstransformers} & 69.64 & 87.31 & 78.47 & 90.90 & 60.03 & 78.80 & 69.04 & 88.39 & 36.83 & 60.84 & 42.91 & 69.88 \\
DN4 \cite{li2019revisiting} & 78.31 & 88.43 & 85.44 & 92.51 & 62.32 &
79.76 & 79.58 & 91.37 & 43.82 & 64.17 & 48.99 & 72.29 \\
DeepEMD \cite{zhang2020deepemd} & 75.34 & 85.68 & 83.35 & 91.60 & 54.48 & 68.36 & 76.05 & 86.82 & 36.05 & 48.55 & 48.14 & 66.27 \\
FRN \cite{wertheimer2021few} & 73.48 & 88.43 & 83.16 & 92.59 & 62.42 & 80.45  & 73.52 & 91.83 & 43.91 & 63.36 & 48.86 & 76.62 \\
\midrule
MCL & 77.80 & 88.71 & 83.64 & 92.18 & \textbf{64.66} & \textbf{81.31} & \textbf{80.17} & 91.59 & \textbf{44.08} & \textbf{64.61} & \textbf{51.35} & \textbf{76.87} \\
MCL-Katz & \textbf{79.61} & \textbf{90.56} & \textbf{85.63} & \textbf{93.18} & 63.92 & 81.09 & 79.34 & \textbf{91.84} & 44.00 & 64.24 & 49.68 & 76.05 \\
\bottomrule
\end{tabular}
\caption{Few-shot classification (\%) results on fine-grained datasets. The 95\% confidence intervals are below 0.19 within 10,000 episodes. \label{tab:finegrained}}
\end{table*}

\begin{table}[t]
\small
\centering
\setlength{\tabcolsep}{4pt}
\renewcommand\arraystretch{1.05}
\begin{tabular}{c|c|cccc}
\multirow{2}{*}{} & \multirow{2}{*}{$f_\theta(\cdot)$}  & \multicolumn{2}{c}{\textit{mini}ImageNet} & \multicolumn{2}{c}{\textit{tiered}ImageNet} \\
 & & 1-shot      & 5-shot      & 1-shot       & 5-shot       \\ \hlineB{2}
\textit{unidirectional} & \multirow{3}{*}{\textit{VanillaFCN}} & 54.88 & 69.98   &   55.31  & 68.87 \\
MCL & & 55.38 & 70.02 & 57.63 & 74.25 \\
MCL-Katz & & \textbf{55.55} & \textbf{71.74} & \textbf{57.78} & \textbf{74.77}  \\ \hline
\textit{unidirectional}  & \multirow{3}{*}{\textit{PyramidFCN}}  & 54.92            &     69.17        &     55.69         &   69.26  \\
MCL &    & 55.13 & 70.77 & 57.93 & 74.36  \\
MCL-Katz & & \textbf{55.77} & \textbf{71.24} & \textbf{58.20} & \textbf{74.73} \\ \hline
\textit{unidirectional}     & \multirow{3}{*}{\textit{PyramidGrid}} & 56.61 & 71.40  & 55.12 & 69.19 \\
MCL & & 57.50 & 73.03 & 57.57 & 73.81  \\
MCL-Katz &  & \textbf{57.88} & \textbf{74.03} & \textbf{57.63} & \textbf{73.96}
\end{tabular}
\vspace{-3pt}
\caption{Comparisons between the \textit{unidirectional} random walks and \textit{bidirectional} MCL on \textit{mini-}/\textit{tiered}ImageNet with Conv-4.\label{tab:uni}}
\end{table}

\subsection{Fine-grained Few-shot Classification Results}

We follow the same setting (shown in supplementary) as in FRN \cite{wertheimer2021few} to train all the models from scratch on those fine-grained datasets. We re-implement DN4 \cite{li2019revisiting}, DeepEMD \cite{zhang2020deepemd} to thoroughly compare with dense features based methods. Apart from the basic comparisons (both backbones on CUB and Conv-4 backbone on meta-iNat/\textit{tiered}-meta-iNat) in \cite{wertheimer2021few}, we conduct extra ResNet-12 experiments for all the comparing methods on meta-iNat and \textit{tiered}-meta-iNat in our unified framework for a thorough comparison.

Results in Table \ref{tab:finegrained} demonstrate that both our end-to-end MCL (\textit{VanillaFCN}) and the centrality plugin are broadly effective in various fine-grained few-shot classification tasks.

\section{Analysis}

\subsection{Ablation Study}

\textbf{Different choices of $\gamma$,$\beta$.} Since $\mathbf{\Phi}$ is non-square due to the different cardinalities of set $\mathbf{S}$ and $\mathbf{q}$, we use two different scaling parameters in Eqn.(\ref{eq:SIM_sq}) and Eqn.(\ref{eq:SIM_qs}). By the column-wise normalization, $\gamma$ and $\beta$ can be interpreted as the reciprocal of temperatures in softmax random walk probability. Large $\gamma$, $\beta$ will have a hard random walk probability that leads to a concentrated centrality in the affiliation network. However, extremely large $\gamma$, $\beta$ (\eg, one-hot probability when they approaching infinity) would inevitably bias the episodic training due to the potential gradient explosion.

Since the cardinality of set $\mathbf{S}$ is larger than that of $\mathbf{q}$, we empirically use a larger $\gamma$ than $\beta$ as we need a harder probability in random walks from query to the large set of support features. In the experiments, we carefully select $\gamma$ and $\beta$ (generally $\gamma$\texttt{=}$20$ and $\beta$\texttt{=}$10$ for 1-shot models and $\gamma$\texttt{=}$40$ and $\beta$\texttt{=}$20$ for 5-shot models) from several combinations of parameters by their validation performance.

\begin{table}[t]
\small
\centering
\setlength{\tabcolsep}{4pt}
\aboverulesep=0ex
\belowrulesep=0ex
\renewcommand\arraystretch{1.05}
\begin{tabular}{l|cc|cccc}
\multicolumn{1}{c|}{\multirow{2}{*}{}} & \multicolumn{2}{c|}{+MCL} & \multicolumn{2}{c}{\textit{mini}ImageNet} & \multicolumn{2}{c}{\textit{tiered}ImageNet } \\
\multicolumn{1}{c|}{}                  & $\mathbf{q}$ & $\mathbf{s}$ & 1-shot          & 5-shot         & 1-shot           & 5-shot          \\ \hlineB{2}
\multirow{4}{*}{ProtoNet \cite{snell2017prototypical}}  &    &   &  52.32     & 69.74  &        53.19          & 72.28     \\
       &  \checkmark &             &    53.74    &  69.61    & 55.36 & 73.17 \\
      &             &  \checkmark          &      53.97           &     69.74           &      56.60            &     74.18           \\
      & \checkmark   & \checkmark    &  \textbf{54.31}  & \textbf{69.84}  & \textbf{56.67} &  \textbf{74.36}               \\ \hline
\multirow{4}{*}{RelationNet \cite{sung2018learning}}  & & & 52.12 & 66.90  &    54.33   &  69.95  \\
    & \checkmark &             &      53.25           & 66.79 &     54.46 &     70.71            \\
      &      &  \checkmark           &        54.37         &  70.57 &         57.68 &         74.24        \\
      & \checkmark  & \checkmark &    \textbf{54.50} & \textbf{70.63}   & \textbf{57.73}  &    \textbf{74.46}
\end{tabular}
\caption{Ablation of MCL as plug-and-play that individually applied on query features $\mathbf{q}$ and support features $\mathbf{s}$. The experiments are conducted with Conv-4 and \textit{VanillaFCN}\label{tab:plug}}
\end{table}

\begin{table*}[t]
\newcommand{1.3cm}{1.3cm}
\aboverulesep=0ex
\belowrulesep=0ex
\def\cellbox#1{\raisebox{-.5\height}{\includegraphics[height=1.3cm]{#1}}}
\setlength{\tabcolsep}{1pt}
\begin{tabular}{lp{0.068\textwidth}<{\centering}p{0.088\textwidth}<{\centering}cllp{0.027\textwidth{}}p{0.068\textwidth}<{\centering}p{0.088\textwidth}<{\centering}cll}
\rule{0pt}{4ex}
\raisebox{-.5\height}{\rotatebox[origin=l]{90}{\shortstack[l]{\scriptsize{ProtoNet} \\ \scriptsize{\cite{snell2017prototypical}}}}} & \multicolumn{5}{c}{\cellbox{figs/ProtoNet_5way1shot-crop.pdf}} & & \multicolumn{5}{c}{\cellbox{figs/MCL_e2e_5way_e1-crop.pdf}} \\ \rule{0pt}{5ex}
\raisebox{-.5\height}{\rotatebox[origin=l]{90}{\shortstack[l]{\scriptsize{ProtoNet} \\ \scriptsize{+MCL}}}} & \multicolumn{5}{c}{\cellbox{figs/ProtoMEL_5way1shot-crop.pdf}} & & \multicolumn{5}{c}{\cellbox{figs/MCL_e2e_5way_e2-crop.pdf}} \\
\multicolumn{1}{c}{} & \hspace{5pt}\scriptsize{query} & \scriptsize{ground truth}   & \multicolumn{3}{c}{\scriptsize{confounding support classes}} & & \hspace{6pt}\scriptsize{query}  & \scriptsize{ground truth}  & \multicolumn{3}{c}{\scriptsize{confounding support classes}} \\
\multicolumn{6}{c}{\small{(a) MCL as a plugin for feature centralization}} & & \multicolumn{5}{c}{\small{(b) MCL as an end-to-end classification method}}
\end{tabular}
\caption{Grad-CAM visualizations of query and support images in 5-way 1-shot tasks. The left pane (a) illustrates MCL as a plugin on the ProtoNet. The right pane (b) illustrates MCL as an end-to-end classification method. Images (from \textit{mini}ImageNet) at the second column of each pane are from the ground truth class while the four on the far right are the confounding support classes.}
    \label{tab:MEL_Quality}
\end{table*}

\textbf{Influence of Katz attenuation factor $\alpha$.} When $\alpha$ is small, the contribution given by paths longer than one rapidly declines, and the centrality will be determined by short paths (mostly in-degrees). When $\alpha$ is large, long paths are devalued smoothly, and the centrality would be more influenced by endogenous topology. When $\alpha$ approaching 0, the classification will be only determined by the unidirectional query-to-support random walk where the contributions from paths longer than one just vanished. We show comparisons in Table \ref{tab:uni} to demonstrate that performances are improved by introducing mutual affiliations in a bidirectional manner.

In the experiments, we simply use $\alpha=0.5$ for MCL-Katz methods, and the performances could be further improved by selecting different $\alpha$ as shown in supplementary.

\subsection{Computational Speed}

Intuitively, bidirectional methods would be slower than unidirectional ones since their back-and-forth computations. However, our MCL would definitely reach to the periodic equilibrium state as shown in Eqn.(\ref{eq:stationary}). Thus, we could directly solve it by the Katz approximation.

At first glance, the most expensive step in Eqn.(\ref{eq:katz_c}) is inverting $\bm{I} - \alpha\mathbf{P}$ that costs $O(N^3r^3)$ where $N$ is the number of supporting classes and $r$ is the number of dense features for each image input. Fortunately, $\bm{I} - \alpha\mathbf{P}$ is a very special matrix that equals a diagonal matrix minus an anti-diagonal matrix. In this case, we can reformulate it by block-wise matrix inversion:
\begin{equation}\label{eq:block}
\resizebox{0.85\linewidth}{!}{%
$\begin{aligned}[b]
\renewcommand{\arraystretch}{1.2}
    (\bm{I} - \alpha\mathbf{P})^{-1} &= \begin{pmatrix}
    \bm{I} & -\alpha \mathbf{P}_\mathbf{Sq} \\
    -\alpha \mathbf{P}_\mathbf{Sq} & \bm{I}
    \end{pmatrix}^{-1} \\
    &= \begin{pmatrix}
    \bm{I} + \alpha^2 \mathbf{P}_\mathbf{Sq}\mathbf{\Delta}^{-1}\mathbf{P}_\mathbf{qS} & \alpha \mathbf{P}_\mathbf{Sq}\mathbf{\Delta}^{-1} \\
    \alpha \mathbf{\Delta}^{-1} \mathbf{P}_\mathbf{qS} & \mathbf{\Delta}^{-1}\\
    \end{pmatrix}
\end{aligned}
$}
\end{equation}
where $\mathbf{\Delta}$ is defined by $\bm{I}-\alpha^2 \mathbf{P_{Sq}}\mathbf{P_{qS}}$. The most expensive step then becomes a inversion of $\mathbf{\Delta} \in \mathbb{R}^{r\times r}$ and the time complexity is reduced to $O(r^3)$.

As shown in Table \ref{tab:scale}, we compare the inference speed between MCL and other unidirectional dense feature based methods with different image resolutions on 5-way 1-shot FSL tasks with ResNet-12. Each class contains 15 query images in an episode. It can be observed that our bidirectional MCL did not introduce many computational overheads compared to unidirectional methods, and Katz approximation does accelerate computing the stationary distribution.

\subsection{Qualitative Feature Centralization}

To better understand our centrality based methods, we visualize the Grad-CAM \cite{selvaraju2017grad} of the last convolutional layer in ResNet-12 for both plugin and end-to-end methods. We show in Table \ref{tab:MEL_Quality}(a) that our MCL helps ProtoNet concentrate on the most relevant regions of interest. Table \ref{tab:MEL_Quality}(b) demonstrates that the most centralized support features in MCL are not only from the ground truth but also mutually affiliated with task-relevant objects in the query images. We consider it qualitatively validates our underlying idea that support features would be frequently visited in the long times of bidirectional random walks if they shared the same local characteristics with the query image.

\begin{table}[t]{
\centering
\small
\aboverulesep=0ex
\belowrulesep=0ex
\renewcommand{\arraystretch}{1}
\setlength{\tabcolsep}{5pt}
\begin{tabular}{l|cccc}
\multirow{2}{*}{Model} & \multicolumn{4}{c}{\textit{VanillaFCN} resolution $r$} \\
& 5$\times$5 & 8$\times$8 & 10$\times$10 & 12$\times$12 \\ \toprule
DN4 \cite{li2019revisiting} & 11.16 & 13.41 & 16.82 & 23.45 \\
DeepEMD \cite{zhang2020deepemd} & 262.0 & 814.6 & 2781.9 & 8035.4 \\
FRN \cite{wertheimer2021few} \scriptsize{(Ridge regression)} & 14.55 & 20.42 & 25.81 & 30.65 \\
FRN \cite{wertheimer2021few} \scriptsize{(Woodbury identity)} & 36.74 & 42.33 & 47.31 & 55.84 \\ \midrule
MCL \scriptsize{(\texttt{torch.pinverse})} & 55.91 & 119.0 & 292.2 & 464.8 \\
MCL \scriptsize{(QR decomposition)} & 600.0 & 658.6 & 719.4 & 802.6 \\
MCL \scriptsize{(Katz approximation)} & 12.59 & 14.59 & 18.92 & 29.10
\end{tabular}
\caption{Time per episode (ms) for different feature map resolutions $r$ on 5-way 1-shot tasks where the feature extraction time is excluded for all comparing methods. \label{tab:scale}}}
\end{table}

\section{Conclusions}

We present a novel dense feature based framework: Mutual Centralized Learning (MCL) to highlight the mutual affiliations of bipartite dense features in FSL. We introduce a novel dense features' accessibility criterion and demonstrate classic transductive methods like label propagation could be easily adapted to the inductive setting if we treat dense features from a single image as the set of unlabeled data. We propose bidirectional random walk to learn mutual affiliations in FSL and prove its features' accessibility in a long time-homogeneous Markov process is equivalent to the single-mode eigenvector centrality of an affiliation network. We show that such centrality could not only serve as a noval end-to-end classification criterion but also as a plugin in existing methods. Experimental results demonstrate MCL achieves the state-of-the-art on various datasets.

{\small
\bibliographystyle{ieee_fullname}

\section{Introduction}

Few-shot classification aims to learn a classifier that can be readily adapted to novel classes given just a small number of labeled instances. To address this problem, a line of previous literature adopts metric-based methods \cite{vinyals2016matching, snell2017prototypical, sung2018learning} that learn a global image representation in an appropriate feature space and use a distance metric to predict their labels.

Recent approaches \cite{zhang2020deepemd, li2019revisiting, lifchitz2019dense} have demonstrated that the significant intra-class variations would inevitably drive the image-level embedding from the same category far apart in a given metric space under low-data regimes. In contrast, densely representative local features can provide transferrable information across categories that have shown promising performances in the few-shot scenario. Among those methods illustrated in Figure \ref{fig:intro}, DN4 \cite{li2019revisiting} finds the nearest neighbor support feature for each query feature and accumulates all the local matches in a Naive-Bayes way to represent an image-to-class similarity; DeepEMD \cite{zhang2020deepemd} uses the earth mover distance to compare the complex structured representations composed of local features. FRN \cite{wertheimer2021few} reconstructs each of query dense features with a linear combination of support dense features in a latent space and use the reconstruction distance to measure the image-to-class relevance. They all follow a unidirectional query-to-support paradigm, whose evident character is an accumulation over all query features followed by a softmax probability.

In this paper, we incorporate an extra support-to-query connection as a complement to thoroughly affiliate two disjoint sets of dense features. The potential offered by this bidirectional paradigm stems from the intuition that, except for using query features to find related support features, it is also plausible to estimate the task-relevance of query features according to the support features. Specifically, we associate dense features with particles that could bidirectionally random walk to the opposite dense features set in the discrete feature space. The prediction probability for each class is then estimated by the dense features' accessibility, \ie, the expected number of visits to the dense features of that class in a time-homogeneous Markov process.

The contributions are as follows: (1) We propose to learn mutual affiliations between the query and support dense features instead of following the unidirectional query-to-support paradigm in FSL. (2) We introduce the dense features' accessibility to FSL and demonstrate that traditional transductive methods could be easily adapted to the inductive setting if we treat dense features from a single query image as a set of unlabeled data. (3) We propose a novel bidirectional random walk based method in FSL and draw its connection to the single-mode eigenvector centrality of an affiliation network. (4) The underlying centrality investigated in this work can be plugged in existing global feature based methods like ProtoNet and RelationNet by highlighting task-centralized local features instead of global average pooling.

\section{Related Work}

\textbf{Dense Feature based FSL.} Those methods focus on learning image-to-image similarities by encoding each input into a set of dense feature vectors (or a feature map). Among them, DC \cite{lifchitz2019dense} proposes to predict for each local features and average their probabilities. DeepEMD \cite{zhang2020deepemd} adopts the earth mover's distance to compute an image-to-class distance. DN4 \cite{li2019revisiting} uses the top-\emph{k} nearest neighbors in a Naive-Bayes way to represent image-level similarities. ADM \cite{li2021asymmetric} and SAML \cite{hao2019collect} use extra network layers for dense classifications. FRN \cite{wertheimer2021few} reconstructs the dense query features from support features of a given class to predict their relevance. Lifchitz \etal \cite{lifchitz2021local} propagates labels from support sets to query features. MCL is also among the family of dense feature based frameworks. A major difference is that we consider the mutual affiliations between the query and support features instead of the unidirectional one in previous work.

\textbf{Graphical models in FSL.} Another branch of methods learns graphs on FSL. Among them, \cite{garcia2017few} build graph neural network (GNN) from a collection of images. \cite{ding2020graph} use the degree-centrality as part of graph features to adjust the weight of graph vertex in transductive FSL. Our proposed feature accessibility of bidirectional random walks is well-related to the eigenvector centrality. Differently, we use the single-mode centrality of bipartite data as a novel criterion for the inductive classification.

\textbf{From Transductive to Inductive.} TPN \cite{liu2019learning} first introduces the well-known label propagation \cite{zhou2003learning} to the transductive FSL that transfers information from labeled data to unlabeled one and shows substantial improvements over inductive methods. Lifchitz \etal\cite{lifchitz2021local} first demonstrates it feasible to adopt label for inductive FSL by treating the query dense features as numerous unlabeled data. Different from unidirectional label propagation, our MCL further considers the set of query and support features as bipartite data where the self-reinforcements (\ie, query-to-query and support-to-support random walks) are avoided.

\section{Method}

\subsection{Formulation of Dense Features based FSL}

In a $N$-way $K$-shot episode, the goal is to predict a class label for a single query image given $N$ support classes, each of which contains $K$ support images for reference.

We first encode each input image into $r$ number of $d$-dimensional dense features $f_\theta(\cdot)\in \mathbb{R}^{d\times r}$. We use $\mathbf{q}=\{q_1, ..., q_r\}$ to denote dense features from a query image. Inspired by prototype learning \cite{snell2017prototypical}, we average feature vectors from the same spatial locations of $K$ different images into support dense features for each $\mathbf{s}^c=\{s_1^c, ..., s_r^c\}$ category.

We use the bold font (\eg, $\mathbf{q}$ and $\mathbf{s}$) to denote a set of feature vectors and use the normal font (\eg, $q$ and $s$) to denote a single feature vector. We use $\mathbf{S}=\bigcup_{c\in C} \mathbf{s}^c$ to represent the union set of dense features from all supporting classes. The cardinalities for the sets $\mathbf{q}$, $\mathbf{s}^c$ and $\mathbf{S}$ are $r$, $r$ and $Nr$ respectively.

The target of dense features based FSL is to find the label of a query image, given its dense query features $\mathbf{q}$ and the union set of dense support features $\mathbf{S}$ from all categories.

\subsection{Bidirectional Random Walks on Dense Features}\label{sec:2.2}

We start by using the \emph{cosine similarity} $\phi(v_1, v_2)= \langle \frac{v_1}{\|v_1\|}, \frac{v_2}{\|v_2\|} \rangle$ to measure the closeness between the two feature vectors where $\langle\cdot,\cdot\rangle$ is the Frobenius inner product.

Given two dense features sets $\mathbf{q}$ and $\mathbf{S}$, we learn inter similarity matrix $\mathbf{\Phi}\in \mathbb{R}^{r\times Nr}$ between those two disjoint sets where the entry of $\left[\mathbf{\Phi}\right]_{qs}=\phi(q, s)$ indicates the similarity between vectors $q\in \mathbf{q}$ and $s\in \mathbf{S}$.

We build query-to-support affiliations from every query feature $q$ to all support features $s\in \mathbf{S}$ by a random walk probability $p_{sq}=\frac{e^{\gamma\phi(s, q)}}{\sum_{s'\in \mathbf{S}}e^{\gamma\phi(s', q)}}$. The probability matrix from all query to support features can be written by
\begin{equation}\label{eq:SIM_sq}
    \mathbf{P}_\mathbf{Sq} = \mathrm{exp}(\gamma\mathbf{\Phi}^\mathrm{T}) \mathbf{D}^{-1}
\end{equation}
where $\mathrm{exp}(\cdot)$ is the element-wise exponential function, $\gamma$ is a scaling temperature for a softmax like probability and $\mathbf{D}$ is a diagonal normalization matrix with its $(j, j)$-value to be the sum of the $j$-th column of $\mathrm{exp}(\gamma\mathbf{\Phi}^\mathrm{T})$. The subscript serves both as the matrix size and as an indication for the feature vector with which it is associated. For example, $\mathbf{P}_{\mathbf{Sq}}$ is of size $|\mathbf{S}|\times |\mathbf{q}|$ and it includes random walk probabilities from query features $\mathbf{q}$ to support features $\mathbf{S}$.

Likewise, we connect every support feature $s$ to all $q\in \mathbf{q}$ by a similar probability matrix:
\begin{equation}\label{eq:SIM_qs}
    \mathbf{P}_\mathbf{qS} = \mathrm{exp}(\beta\mathbf{\Phi}) \mathbf{W}^{-1}
\end{equation}
where $\mathbf{W}$ is the analogous diagonal matrix with its $(j, j)$-value to be the sum of the $j$-th column of $\mathrm{exp}(\beta\mathbf{\Phi})$.

It should be noted that we use two different scaling parameters since $\mathbf{\Phi}$ is a non-square matrix due to the different cardinalities of dense feature sets $\mathbf{q}$ and $\mathbf{S}$. Although the matrices $\mathrm{exp}(\gamma\mathbf{\Phi}^\mathrm{T})$ and $\mathrm{exp}(\beta\mathbf{\Phi})$ would be symmetric if we ignore their different scaling parameters, the probability matrices $\mathbf{P}_\mathbf{qS}$, $\mathbf{P}_\mathbf{Sq}$ are both column-normalized by different $\mathbf{D}$, $\mathbf{W}$ respectively and are thus directional.

To learn the mutual affiliations between the two dense feature sets, we first associate each feature vector with a particle $z$ that forms a discrete feature space $\mathbf{z} = \mathbf{q} \cup \mathbf{S}$. Next, we let particles bidirectionally random walk between particles in that space according to $\mathbf{P}_\mathbf{Sq}$ and $\mathbf{P}_\mathbf{qS}$ (\ie, particles at query features set are only allowed to move to the support features set, and vice versa). We assume it time-homogeneous in a Markov process $\{X_t\}$ and the random walk probability from $z_j$ to $z_i$ for all $z_i$, $z_j$ in $\mathbf{z}$ can be formulated by:
\begin{equation}\label{eq:3}
\resizebox{\hsize}{!}{%
$\mathbf{Pr}(X_{t+1} = z_i | X_{t}= z_j) = \left\{
\renewcommand{\arraystretch}{1.2}
\begin{array}{ll}
\displaystyle{\frac{e^{\gamma\phi(z_i, z_j)}}{\sum_{s\in \mathbf{S}} e^{\gamma\phi(s, z_j)}}} & \hspace{-5pt}z_i\in \mathbf{S}, z_j \in \mathbf{q} \\
\displaystyle{\frac{e^{\beta\phi(z_i, z_j)}}{\sum_{q\in \mathbf{q}} e^{\beta\phi(q, z_j)}}} & \hspace{-5pt}z_i\in \mathbf{q}, z_j \in \mathbf{S} \\ 0 & \hspace{-5pt}\mathrm{otherwise}.
\end{array}
\right.
$}
\end{equation}

To write it in matrix, we can obtain the Markov transition matrix $\mathbf{P}$:
\begin{equation}\label{eq:prop}
    \mathbf{P}=\begin{pmatrix}
    \mathbf{0} & \mathbf{P}_{\mathbf{S}\mathbf{q}} \\
    \mathbf{P}_{\mathbf{q}\mathbf{S}} & \mathbf{0}
    \end{pmatrix}
\end{equation}
that consists of the column-normalized $\mathbf{P}_\mathbf{Sq}$ and $\mathbf{P}_\mathbf{qS}$.

It can be proved (in supplementary) that, after infinity times of bidirectional random walks, the Markov chain with anti-diagonal $\mathbf{P}$ reaches the periodic stationary distribution:
\begin{align}\label{eq:stationary}
\begin{split}
    \lim_{t\rightarrow\infty} \mathbf{P}^{2t} &= \begin{pmatrix}
    \boldsymbol{\pi}(\mathbf{S})\bm{e}_{Nr}^\mathrm{T} & \mathbf{0} \\
     \mathbf{0} & \boldsymbol{\pi}(\mathbf{q})\bm{e}_{r}^\mathrm{T}
    \end{pmatrix} \\
    \lim_{t\rightarrow\infty} \mathbf{P}^{2t-1} &= \begin{pmatrix}
    \mathbf{0} & \boldsymbol{\pi}(\mathbf{S})\bm{e}_{r}^\mathrm{T}  \\
     \boldsymbol{\pi}(\mathbf{q})\bm{e}_{Nr}^\mathrm{T} & \mathbf{0}
    \end{pmatrix}
\end{split}
\end{align}
where $\boldsymbol{\pi}(\mathbf{S})\in \mathbb{R}^{Nr}$, $\boldsymbol{\pi}(\mathbf{q})\in \mathbb{R}^r$ are the stationary distributions with equations $\boldsymbol{\pi}(\mathbf{S}) = \mathbf{P_{Sq}}\mathbf{P_{qS}}\boldsymbol{\pi}(\mathbf{S})$ and $\boldsymbol{\pi}(\mathbf{q}) = \mathbf{P_{qS}P_{Sq}}\boldsymbol{\pi}(\mathbf{q})$ respectively. $\bm{e}_{|\cdot|}$ is a vector of ones with different length indicated by its subscript.

The motivation of using these stationary distributions to encode mutual affiliations is straightforward: support features would be frequently visited in the long times of bidirectional random walk if they shared the same local characteristics with the query ones. In other words, the support class that owns the most mutual affiliations with querying image would be predicted due to their mutual closeness.

\subsection{Classification by Dense Features' Accessibility}

To formulate it in FSL, we first assume particles are uniformly distributed in the discrete finite space $\mathbf{z}$. Then, we use the expected number of visits from all particles $z\in \mathbf{z}$ to support features $\mathbf{s}^{c}\subset \mathbf{S}$ of class $c$ in the long times of bidirectional random walks $\{X_t\}$ to measure the amount of local characteristics that class $c$ owns for the query image:
\begin{equation}
\resizebox{\linewidth}{!}{%
$\begin{aligned}[b]\label{eq:MEL}%
&\mathbf{Pr}(\tilde{y} = c) \propto \lim_{t\rightarrow\infty}\sum_{z\in\mathbf{z}}\mathbb{E} \left[\sum_{k=1}^t\mathds{1}[X_k\in \mathbf{s}^c] \bigg| X_0=z\right]  \\
&= \lim_{t\rightarrow\infty} \frac{1}{t}\sum_{k=1}^{t}\left[\frac{1}{Nr+r}\sum_{s\in \mathbf{s}^c}\left(\sum_{s'\in \mathbf{S}}\left[\mathbf{P}^{2k}\right]_{ss'} + \sum_{q\in \mathbf{q}}\left[\mathbf{P}^{2k-1}\right]_{sq}\right)\right]  \\
&= \frac{1}{Nr+r} \sum_{s\in \mathbf{s}^c}\left(\sum_{s'\in \mathbf{S}}\left[\lim_{t\rightarrow \infty}\mathbf{P}^{2t}\right]_{ss'} + \sum_{q\in \mathbf{q}}\left[\lim_{t\rightarrow \infty}\mathbf{P}^{2t-1}\right]_{sq}\right)  \\
&=\sum_{s\in \mathbf{s}^c} \left[\boldsymbol{\pi}(\mathbf{S})\right]_s
\end{aligned}
$}
\end{equation}
where $\mathds{1}[\cdot]$ is an indicator function that equals 1 if its argument is true and zero otherwise. $[\cdot]_{ij}$ indicates the entry of the matrix from particle $j$ to particle $i$ and $[\cdot]_{i}$ indicates the entry of the vector that associated to feature $i$.

We give the derivation when the Markov chain length $t$ is even in the first equality of Eqn.(\ref{eq:MEL}) and prove that the odd $t$ reaches the same result in the supplementary material. The second equality is from the \emph{absorbing} property of the periodic Markov chain where the power of matrix gets saturated to Eqn.(\ref{eq:stationary}) for the increasing $t$. Since $\boldsymbol{\pi}(\mathbf{S})$ is the stationary distribution of column-stochastic $\mathbf{P_{Sq}P_{qS}}$ under the probability constraint $\bm{e}^\mathrm{T}_{Nr}\boldsymbol{\pi}(\mathbf{S})=1$, $\mathbf{Pr}(\tilde{y})$ is a valid distribution for classifications.

\subsection{Reinterpretation as a Graph Centrality} \label{sec:interp}

If we interpret the random walk probability matrix $\mathbf{P}$ as an adjacency matrix $\{a_{v_1,v_2}\}$ of a directed bipartite graph $G:=(V=\{\mathbf{q}, \mathbf{S}\}, E)$, we find that the dense features' accessibility in the time-homogeneous bidirectional random walk would be equivalent to learning a \emph{single-mode eigenvector centrality} on the graph $G$. The bipartite graph is also called the \emph{affiliation network} in social network analysis \cite{bonacich1972factoring, bonacich1991simultaneous, borgatti1997network} that models two types of entities "\emph{actors}" and "\emph{society}" related by affiliation of the former in the latter. The concept of centrality in social network analysis is generally used to investigate the acquaintanceships among people that often stem from one or more shared affiliations.

To see this in graph theory, we start with a brief overview of the eigenvector centrality that reflects score $x$ of vertex $v$ for both $q\in \mathbf{q}$ and $s\in \mathbf{S}$ in the affiliation network with adjacency $\{a_{v_1,v_2}\}$:
\begin{align}\label{eq:centrality}
\begin{split}
    x_q&=\frac{1}{\lambda} \sum_{v\in \mathbb{V}(q)}a_{q, v}x_v=\frac{1}{\lambda}\sum_{v\in \mathbf{S}}a_{q, v}x_v \\      x_s&=\frac{1}{\lambda} \sum_{v\in \mathbb{V}(s)}a_{s, v}x_v=\frac{1}{\lambda}\sum_{v\in \mathbf{q}}a_{s, v}x_v
\end{split}
\end{align}
where $\mathbb{V}(\cdot)$ is a set of neighbors for the given vertex and $\lambda$ is a constant.

With a small rearrangement, Eqn.(\ref{eq:centrality}) can be rewritten in vector notation with an eigenvector equation $\mathbf{Px} = \lambda \mathbf{x}$. The additional requirement that all the entries of the eigenvector be non-negative implies (by the Perron–Frobenius theorem \cite{perron1907theorie}) that only the greatest eigenvalue results in the desired centrality measure. For the column-stochastic adjacency matrix $\mathbf{P}$ in our method, the largest eigenvalue $\lambda$ is 1.

Single-mode centrality \cite{borgatti1997network} is a special form of graph centrality that measures the extent to which nodes in one vertex set are relatively central only to other nodes in the same vertex set on bipartite graph. For example, the single-mode centrality for different $s$ in $\mathbf{S}$ is defined by $\hat{\mathbf{x}}_\mathbf{S}=\mathbf{x}_\mathbf{S} / \sum_{s\in \mathbf{S}}x_s$. Lemma \ref{lemm:1} (proved in supplementary material) shows that dense features' accessibility $\boldsymbol{\pi}(\mathbf{S})$ of bidirectional random walks in Eqn.(\ref{eq:MEL}) is equivalent to the single-mode eigenvector centrality of support set $\mathbf{S}$ on bipartite data.

\begin{lemm}\label{lemm:1}
Assume $G$ is the affiliation network of bipartite data $\mathbf{q}$, $\mathbf{S}$ with the adjacency matrix defined by the anti-diagonal Markov transition matrix $\mathbf{P}$ in Eqn.(\ref{eq:prop}). The single-mode eigenvector centrality $\hat{\mathbf{x}}_{\mathbf{S}}=\mathbf{x}_\mathbf{S} / \sum_{s\in \mathbf{S}}x_s$ of vertex set $\mathbf{S}$ is equivalent to the dense features' accessibility $\boldsymbol{\pi}(\mathbf{S})$ on $\mathbf{S}$ in a time-homogeneous Markov process.
\end{lemm}

Based on this reinterpretation, it is straightforward to introduce the attenuation (damping) factor $\alpha$ in Markov bidirectional random walks motivated by the Katz centrality \cite{katz1953new}, where connections made with distant neighbors are penalized by $\alpha$. The dense features' accessibility with attenuation factor $\alpha$ for few-shot classifications is defined by
\begin{align}\label{eq:katz}
\begin{split}
&\mathbf{P}\mathbf{r}_\mathrm{Katz}(\tilde{y}=c) \propto \sum_{z\in\mathbf{z}}\mathbb{E} \left[\sum_{t=1}^\infty\alpha^t\mathds{1}[X_t\in \mathbf{s}^c] \bigg| X_0=z\right]\\
&= \frac{1}{\epsilon}\sum_{t=1}^{\infty}\sum_{s\in \mathbf{s}^c}\left(\sum_{s'\in \mathbf{S}}\left[\alpha^{2t}\mathbf{P}^{2t}\right]_{ss'}+\sum_{q\in \mathbf{q}} \left[\alpha^{2t-1}\mathbf{P}^{2t-1}\right]_{sq}\right)
\end{split}
\end{align}
where $\epsilon=(Nr + r)\sum_{t=1}^{\infty}\alpha^t=(Nr+r)\alpha / (1 - \alpha)$ is a constant for a valid distribution.

Although we simply consider the single-mode centrality on $\mathbf{S}$ for an end-to-end classification purpose, it is also beneficial to learn its conjugate centrality $\boldsymbol{\pi}(\mathbf{q})$ on $\mathbf{q}$ in the affiliation network (by the analogous $\boldsymbol{\pi}(\mathbf{q})=\mathbf{x}_\mathbf{q} / \sum_{q\in\mathbf{q}}x_q$ in Lemma \ref{lemm:1}). We will show that both single-mode centralities on two dense features sets could serve as plug-and-play for finding centralized local characteristics in existing methods (hence the term Mutual Centralized Learning, MCL).

\subsection{End-to-End Training by Katz Approximation}\label{sec:MEL}

The algorithm of Mutual Centralized Learning (MCL) in Eqn.(\ref{eq:MEL}) involves the computation of Markov stationary distribution $\boldsymbol{\pi}(\mathbf{S})$ with equation $\boldsymbol{\pi}(\mathbf{S}) = \mathbf{P_{Sq}P_{qS}} \boldsymbol{\pi}(\mathbf{S})$. Theoretically, the $\boldsymbol{\pi}(\mathbf{S})$ is the eigenvector of $\mathbf{P_{Sq}P_{qS}}$ with the eigenvalue 1 under a probability constraint $\bm{e}_{Nr}^\mathrm{T}\boldsymbol{\pi}(\mathbf{S})=1$.

The above constraints could lead to a solution of $\boldsymbol{\pi}(\mathbf{S})$ by solving the overdetermined linear system
\begin{equation}\label{eq:overdetermined}
\begin{pmatrix}
\mathbf{P_{Sq}P_{qS}} - \bm{I} \\
\bm{e}^\mathrm{T}_{Nr}
\end{pmatrix}
\boldsymbol{\pi}(\mathbf{S}) =
\begin{pmatrix}
\mathbf{0} \\
1
\end{pmatrix}
\end{equation}
where $\bm{I}$ is an identity matrix and $\mathbf{0}$ is a vector of zeros. Although we can solve it by various methods like pseudo-inverse or QR decomposition and back substitution, it is empirically found time-consuming as these operators are either numerically unstable or not paralleled well in modern deep-learning packages.

To handle it, we present an alternative solution based on Lemma \ref{lemm:1} as follows: We first calculate the Katz centrality by its closed-form solution \cite{katz1953new}:
\begin{equation}\label{eq:katz_c}
\mathbf{x}^\mathrm{Katz} = ((\bm{I} - \alpha \mathbf{P})^{-1} - \bm{I})\bm{e}_{Nr+r}
\end{equation}
and then solve single-mode Katz centrality in Eqn.(\ref{eq:katz}) by the definition of the single-mode centrality:
\begin{equation}
    \mathbf{Pr}_\mathrm{Katz}(\tilde{y}=c) = \frac{\sum_{s\in \mathbf{s}^c}\mathbf{x}^\mathrm{Katz}_s}{\sum_{s'\in \mathbf{S}}\mathbf{x}^\mathrm{Katz}_{s'}}
    \label{eq:katz_c_2}
\end{equation}

Since Katz centrality degrades to the eigenvector centrality when $\alpha$ approaches 1 \cite{katz1953new} (indicates no attenuation), we can obtain the approximation of eigenvector centrality by a large $\alpha=0.999$:
\begin{align}\label{eq:eigen_c}
\begin{split}
    \mathbf{x}^\mathrm{Eigen} &= \lim_{\alpha\rightarrow 1}((\bm{I} - \alpha\mathbf{P})^{-1} - \bm{I})\bm{e}_{Nr+r} \\
    &\approx ((\bm{I} - 0.999 \mathbf{P})^{-1} - \bm{I})\bm{e}_{Nr+r}
\end{split}
\end{align}
and the analogous single-mode eigenvector centrality in Eqn.(\ref{eq:MEL}) can then be approximated by:
\begin{equation}
    \mathbf{Pr}_\mathrm{MCL}(\tilde{y}=c) = \frac{\sum_{s\in \mathbf{s}^c}\mathbf{x}^\mathrm{Eigen}_s}{\sum_{s'\in \mathbf{S}}\mathbf{x}^\mathrm{Eigen}_{s' }} \label{eq:mel_final}
\end{equation}

We use the negative log-likelihood loss to update parameters in different feature extractors and the whole picture of MCL for few-shot classifications is shown in Figure \ref{fig:arch}. We provide the detailed algorithm/pseudo-codes in the supplementary material for reference.

\begin{figure*}[t]
    \centering
     \includegraphics[width=\textwidth]{figs/arch-crop.pdf}
     \caption{Our framework for 3-way 1-shot classification. Given the query and support images, we first extract their dense features $\mathbf{q}$ and $\mathbf{S}$ which are two sets of feature vectors. Then we calculate their similarity matrix $\mathbf{\Phi}$. After that, we build probability matrix $\mathbf{P}$ based on the scaled and column-normalized similarity matrix. We obtain the stationary distributions $\boldsymbol{\pi}(\mathbf{S})$ and $\boldsymbol{\pi}(\mathbf{q})$ by the Katz approximation in Eqn.(\ref{eq:eigen_c}) and the Lemma \ref{lemm:1}. Finally, we use them for both end-to-end FSL and as a centrality plugin in global feature based FSL. We explore three dense feature extractors (\ie, \textit{VanillaFCN}, \textit{PyramidFCN}, \textit{PyramidGrid}) inspired by \cite{zhang2020deepemd} to extract dense feature representations.}
     \label{fig:arch}
\end{figure*}

\subsection{Plugin for Global Feature based FSL.\label{sec:plug}}

Since the underlying centrality learned by MCL reveals the different importance of local features on an affiliation network, it is thus plausible to plug it into global feature based methods by replacing their native global average pooling (GAP) with the centrality weighted pooling as follows:

a. Extract dense features for each input image.

b. Compute the eigenvector centrality $\mathbf{x}^\mathrm{Eigen}$ by Eqn.(\ref{eq:eigen_c}).

c. Compute $\boldsymbol{\pi}(\mathbf{S})$ and $\boldsymbol{\pi}(\mathbf{q})$ according to definition of the single-mode centrality in Lemma \ref{lemm:1}.

d. Use $\boldsymbol{\pi}(\mathbf{q})$ as weights on query dense features and weighted accumulate them to a single feature vector.

e. Use the class-wise normalized centrality from $\boldsymbol{\pi}(\mathbf{S})$ to accumulate dense features for each supporting class.

Once we get the centrality weighted features for the query image and support classes, it is straightforward to perform traditional global feature based methods like before.

\section{Experiments}

We conduct experiments on two widely-used FSL datasets and three fine-grained datasets: (1) \textbf{\textit{mini}ImageNet} \cite{vinyals2016matching} contains 600 images per class over 100 classes. We follow the split used by \cite{sachin2017optimization} that takes 64, 16 and 20 classes for train/val/test respectively; (2) \textbf{\textit{tiered}ImageNet} \cite{ren2018meta} is much larger compared to \textit{mini}ImageNet with 608 classes. The 351, 97 and 160 classes are used for train/val/test respectively. (3) \textbf{CUB} \cite{welinder2010caltech} consists 11,788 images from 200 bird classes. 100/50/50 classes are used for train/val/test and each image is first cropped to a human-annotated bounding box. (4) \textbf{meta-iNat} \cite{wertheimer2019few} is a benchmark of animal species in the wild. We follow the same class split proposed by \cite{wertheimer2019few} that uses 908/227 classes for training/evaluation respectively. (5) \textbf{\textit{tiered}-meta-iNat} \cite{wertheimer2019few} is a more difficult version of meta-iNat where a large domain gap is introduced. The 354 test classes are populated by insects and arachnids, while the remaining 781 classes form the training set.

\textbf{Backbone networks.} We conduct experiments with both widely-used four layer convolutional Conv-4 \cite{vinyals2016matching} and deep ResNet-12 \cite{sun2019meta} backbones. As is commonly implemented in the state-of-the-art FSL literature, we adopt a pre-training stage for the ResNet-12 before the episode meta-training while directly meta-train from scratch for the simple Conv-4.

\textbf{Dense feature extractor $f_\theta(\cdot)$.} We explore three dense feature extractors in our experiments as shown in Figure \ref{fig:arch}: (1) \textit{VanillaFCN} simply treats the feature map output of fully convolutional network as dense features. (2) \textit{PyramidFCN} uses an extra adaptative average pooling layer to obtain 34 dense features for each image. (3) \textit{PyramidGrid} crops the image evenly into the grid of size $2\times 2 + 3\times 3$ and encodes each grid cell to a feature vector individually. The feature vectors from all the cells constitute the set of dense features.

\begin{table*}[t]
\centering
\small
\setlength{\tabcolsep}{6pt}
\aboverulesep=0ex
\belowrulesep=0.5ex
\renewcommand\arraystretch{1}
\newcommand{\cellcolor{Gray}}{\cellcolor{Gray}}
\begin{tabular}{cccccccccc}
\toprule
\multicolumn{2}{c}{\multirow{3}{*}{\textbf{Method}}} & \multicolumn{4}{c}{\textbf{Conv-4}}                                             & \multicolumn{4}{c}{\textbf{ResNet-12}} \\
\multicolumn{2}{c}{}                        & \multicolumn{2}{c}{\textit{mini}ImageNet} & \multicolumn{2}{c}{\textit{tiered}ImageNet} & \multicolumn{2}{c}{\textit{mini}ImageNet} & \multicolumn{2}{c}{\textit{tiered}ImageNet} \\ \cmidrule(lr){3-4} \cmidrule(lr){5-6} \cmidrule(lr){7-8} \cmidrule(lr){9-10}
\multicolumn{2}{c}{}                        & 1-shot          & 5-shot         & 1-shot           & 5-shot          & 1-shot          & 5-shot         & 1-shot           & 5-shot          \\ \midrule
\multirow{9}{*}{\textit{Global features}} & DSN \cite{simon2020adaptive} & 51.78 & 68.99 & 53.22 & 71.06 & 62.64 & 78.83 & 67.39 & 82.85 \\
 & MetaOptNet \cite{lee2019meta} & 52.87 & 68.76 & 54.71 & 71.76 & 62.64 & 78.63 & 65.99 & 81.56 \\
 & Negative Margin \cite{liu2020negative} & 52.84 & 70.41 & - & - & 63.85 & 81.57 & - & - \\
& FEAT \cite{ye2020few} & 55.15 & 71.61 & - & - & 66.78 & 82.05 & 70.80 & 84.79 \\
& Meta-Baseline \cite{chen2020new} & - & - & - & - & 63.17 & 79.26 & 68.62 & 83.29 \\
 & RelationNet$^\ddagger$ \cite{sung2018learning} & 52.12 & 66.90 & 54.33 & 69.95 & 60.97 & 75.12 & 64.71 & 78.41 \\
 & \cellcolor{Gray} RelationNet+MCL & \cellcolor{Gray} \textit{54.50} & \cellcolor{Gray} \textit{70.63} & \cellcolor{Gray} \textit{57.73} & \cellcolor{Gray} \textit{74.46} & \cellcolor{Gray} \textit{61.70} & \cellcolor{Gray} \textit{75.53} & \cellcolor{Gray} \textit{65.93} & \cellcolor{Gray} \textit{80.27} \\
 & ProtoNet$^\ddagger$ \cite{snell2017prototypical} & 52.32 & 69.74 & 53.19 & 72.28 & 62.67 & 77.88 & 68.48 & 83.46 \\
 & \cellcolor{Gray} ProtoNet+MCL & \cellcolor{Gray} \textit{54.31} & \cellcolor{Gray} \textit{69.84} & \cellcolor{Gray} \textit{56.67} & \cellcolor{Gray} \textit{74.36} & \cellcolor{Gray} \textit{64.40} & \cellcolor{Gray} \textit{78.60} & \cellcolor{Gray} \textit{70.62} & \cellcolor{Gray} \textit{83.84} \\
 \midrule
\multirow{6}{*}{\makecell{\textit{Dense features}\\(\textit{VanillaFCN})}} & DN4$^\ddagger$ \cite{li2019revisiting} & 54.66 & 71.26 & 56.86 & 72.16 & 65.35 & 81.10 & 69.60 & 83.41 \\
& DeepEMD$^\dagger$ \cite{zhang2020deepemd} & 52.15 & 65.52 & 50.89 & 66.12 & 65.91 & 82.41 & 71.16 & 83.95 \\
& FRN$^\dagger$ \cite{wertheimer2021few} & 54.87 & 71.56 & 55.54 & 74.68 & 66.45 & 82.83 & 71.16 & 86.01 \\
& Label Propagation & 52.24 & 67.68 & 54.56 & 70.08 & 65.00 & 80.07 & 71.12 & 83.89 \\
& \cellcolor{Gray} MCL (ours) & \cellcolor{Gray} 55.38 & \cellcolor{Gray} 70.02 & \cellcolor{Gray} 57.63 & \cellcolor{Gray} 74.25 & \cellcolor{Gray} 67.36 & \cellcolor{Gray} 83.63 & \cellcolor{Gray} 71.76 & \cellcolor{Gray} 86.01 \\
& \cellcolor{Gray} MCL-Katz (ours) & \cellcolor{Gray} \textbf{55.55} & \cellcolor{Gray} \textbf{71.74} & \cellcolor{Gray} \textbf{57.78} & \cellcolor{Gray} \textbf{74.77} & \cellcolor{Gray} \textbf{67.51} & \cellcolor{Gray} \textbf{83.99} & \cellcolor{Gray} \textbf{72.01} & \cellcolor{Gray} \textbf{86.02} \\
\midrule
\multirow{6}{*}{\makecell{\textit{Dense features}\\(\textit{PyramidFCN})}} & DN4$^\ddagger$ \cite{li2019revisiting} & 54.54 & 70.94 & 57.05 & 72.90 & 63.54 & 79.04 & 71.10 & 84.22 \\
& DeepEMD$^\ddagger$ \cite{zhang2020deepemd} & 50.67 & 64.94 & 51.26 & 65.64 & 66.27 & 82.41 & 70.76 & 84.20 \\
& FRN$^\ddagger$ \cite{wertheimer2021few} & 54.40 & 70.75 & 57.30 & \textbf{75.58} & 65.94 & 81.97 & 70.56 & 85.44 \\
& Label Propagation & 53.38 & 68.69 & 55.21 & 71.22 & 65.71 & 75.78 & 71.00 & 78.01 \\
& \cellcolor{Gray} MCL (ours) & \cellcolor{Gray} 55.13 & \cellcolor{Gray} 70.77 & \cellcolor{Gray} 57.93 & \cellcolor{Gray} 74.36 & \cellcolor{Gray} 67.45 & \cellcolor{Gray} 84.36 & \cellcolor{Gray} 72.01 & \cellcolor{Gray} 86.31 \\
& \cellcolor{Gray} MCL-Katz (ours) & \cellcolor{Gray} \textbf{55.77} & \cellcolor{Gray} \textbf{71.24} & \cellcolor{Gray} \textbf{58.20} & \cellcolor{Gray} 74.73 & \cellcolor{Gray} \textbf{67.85} & \cellcolor{Gray} \textbf{84.47} & \cellcolor{Gray} \textbf{72.13} & \cellcolor{Gray} \textbf{86.32} \\
\midrule
\multirow{6}{*}{\makecell{\textit{Dense features}\\(\textit{PyramidGrid})}} & DN4$^\ddagger$ \cite{li2019revisiting} & 57.17 & 70.91 & 56.71 & 70.92 & 67.86 & 80.08 & 71.29 & 82.60 \\
& DeepEMD$^\ddagger$ \cite{zhang2020deepemd} & 55.68 & 70.75 & 55.88 & 70.06 & 67.83 & 81.32 & 73.13 & 84.18 \\
& FRN$^\ddagger$ \cite{wertheimer2021few} & 55.80 & 71.52 & 55.68 & 72.87 & 67.00 & 82.20 & 71.42 & 85.58 \\
& Label Propagation & 55.12 & 68.43 & 56.05 & 72.39 & 67.18 & 81.07 & 73.18 & 85.19 \\
& \cellcolor{Gray} MCL (ours) & \cellcolor{Gray} 57.50 & \cellcolor{Gray} 73.03 & \cellcolor{Gray} 57.57 & \cellcolor{Gray} 73.81 & \cellcolor{Gray} \textbf{69.31} & \cellcolor{Gray} \textbf{85.11} & \cellcolor{Gray} \textbf{73.62} & \cellcolor{Gray} \textbf{86.29} \\
& \cellcolor{Gray} MCL-Katz (ours) & \cellcolor{Gray} \textbf{57.88} & \cellcolor{Gray} \textbf{74.03} & \cellcolor{Gray} \textbf{57.63} & \cellcolor{Gray} \textbf{73.96} & \cellcolor{Gray} 69.25 & \cellcolor{Gray} 84.71 & \cellcolor{Gray} 73.38 & \cellcolor{Gray} 86.21 \\
\bottomrule
\end{tabular}
\caption{Few-shot classification accuracy (\%) on \textit{mini}ImageNet and \textit{tiered}ImageNet. The 95\% confidence intervals are all below 0.2 for the 10,000 episodes evaluation. Results of \textit{italic} font indicates the performance of MCL as a plugin. Results of \textbf{bold} fonts are the best results for different dense feature extractors, respectively. We re-implement our plugin baseline methods (\ie, ProtoNet and RelationNet) as well as the competitive dense features based methods (\ie, DN4, DeepEMD and FRN) in our unified framework in case their performances are not available under specific settings. $\dagger$: re-implemented results on Conv-4 backbone, $\ddagger$: re-implemented results on both backbones. \label{tab:sota}}
\end{table*}

\subsection{General Few-shot Classification Results}

Table \ref{tab:sota} details the comparisons of MCL with global feature based methods \cite{simon2020adaptive,lee2019meta,ye2020few, chen2020new, liu2020negative} as well as dense feature based methods \cite{li2019revisiting, zhang2020deepemd, wertheimer2021few} on \textit{mini}-/\textit{tiered}ImageNet.

Besides these methods, we also exploit label propagation \cite{zhou2003learning} in dense feature based inductive FSL like in \cite{lifchitz2021local} to demonstrate that traditional transductive methods could be easily adapted to inductive settings if we treat dense feature vectors as a set of unlabeled data. As shown, our MCL is highly competitive with recent state-of-the-art results. In particular, our MCL-Katz achieves \textbf{67.51}\% (1-shot) and \textbf{83.99}\% (5-shot) on \textit{mini}ImageNet with the simplest \textit{VanillaFCN}.

\textbf{Comparisons with dense feature based methods.} The last three panes of Table \ref{tab:sota} illustrate that proposed bidirectional MCL outperforms query-to-support DN4's nearest neighboring, DeepEMD's optimal matching and FRN's latent feature reconstructions in various tasks. Although the optimal matching flow is unidirectional in DeepEMD, they adopt a cross-reference attention that encodes the bidirectional relevance to a certain extent. If we treat dense features as \textit{nodes} in the graph and use their similarities as \textit{edges}, a major difference is that they treat nodes equally to derive different weights on edges while we use the fixed edges to derive the centrality of nodes directly for classifications.

\textbf{Comparisons with global feature based methods.} The centrality investigated in this work is also capable to be plugged into global feature based methods as local features are not equally important before global average pooling. As shown in the first pane of Table \ref{tab:sota}, our proposed centrality weighted pooling could provide at most \textbf{3.4}\% and \textbf{4.5}\% performance gains for ProtoNet and RelationNet respectively.
We show in Table \ref{tab:plug} that the improvements are also consistent if we solely apply it on the query and support dense features.

\begin{table*}[]
\centering
\small
\setlength{\tabcolsep}{5pt}
\aboverulesep=0ex
\belowrulesep=0.5ex
\renewcommand\arraystretch{1}
\begin{tabular}{ccccccccccccc}
\toprule
\multirow{3}{*}{\textbf{Method}} & \multicolumn{4}{c}{\textbf{CUB}} & \multicolumn{4}{c}{\textbf{meta-iNat}} & \multicolumn{4}{c}{\textbf{\textit{tiered}-meta-iNat}} \\
 & \multicolumn{2}{c}{Conv-4} & \multicolumn{2}{c}{ResNet-12} & \multicolumn{2}{c}{Conv-4} & \multicolumn{2}{c}{ResNet-12} & \multicolumn{2}{c}{Conv-4} & \multicolumn{2}{c}{ResNet-12} \\
\cmidrule(lr){2-3} \cmidrule(lr){4-5} \cmidrule(lr){6-7} \cmidrule(lr){8-9} \cmidrule(lr){10-11} \cmidrule(lr){12-13}
 & 1-shot & 5-shot & 1-shot & 5-shot & 1-shot & 5-shot & 1-shot & 5-shot & 1-shot & 5-shot & 1-shot & 5-shot \\
 \midrule
ProtoNet \cite{snell2017prototypical} & 71.64 & 81.50 & 82.98 & 91.38 & 53.78 & 73.80 & 76.47 & 90.20 & 35.47 & 54.85 & 47.61 & 71.06 \\
ProtoNet + MCL & \textit{76.87} & \textit{86.95} & \textit{84.59} & \textit{91.71} & \textit{57.52} & \textit{74.33} & \textit{78.75} & \textit{90.53} & \textit{39.09} & \textit{59.16} & \textit{51.22} & \textit{72.50} \\
DSN \cite{simon2020adaptive} & 66.01 & 85.41 & 80.80 & 91.19 & 58.08 & 77.38 & 78.80 & 89.77 & 36.82 & 60.11 & 46.61 & 72.79 \\
CTX \cite{doersch2020crosstransformers} & 69.64 & 87.31 & 78.47 & 90.90 & 60.03 & 78.80 & 69.04 & 88.39 & 36.83 & 60.84 & 42.91 & 69.88 \\
DN4 \cite{li2019revisiting} & 78.31 & 88.43 & 85.44 & 92.51 & 62.32 &
79.76 & 79.58 & 91.37 & 43.82 & 64.17 & 48.99 & 72.29 \\
DeepEMD \cite{zhang2020deepemd} & 75.34 & 85.68 & 83.35 & 91.60 & 54.48 & 68.36 & 76.05 & 86.82 & 36.05 & 48.55 & 48.14 & 66.27 \\
FRN \cite{wertheimer2021few} & 73.48 & 88.43 & 83.16 & 92.59 & 62.42 & 80.45  & 73.52 & 91.83 & 43.91 & 63.36 & 48.86 & 76.62 \\
\midrule
MCL & 77.80 & 88.71 & 83.64 & 92.18 & \textbf{64.66} & \textbf{81.31} & \textbf{80.17} & 91.59 & \textbf{44.08} & \textbf{64.61} & \textbf{51.35} & \textbf{76.87} \\
MCL-Katz & \textbf{79.61} & \textbf{90.56} & \textbf{85.63} & \textbf{93.18} & 63.92 & 81.09 & 79.34 & \textbf{91.84} & 44.00 & 64.24 & 49.68 & 76.05 \\
\bottomrule
\end{tabular}
\caption{Few-shot classification (\%) results on fine-grained datasets. The 95\% confidence intervals are below 0.19 within 10,000 episodes. \label{tab:finegrained}}
\end{table*}

\begin{table}[t]
\small
\centering
\setlength{\tabcolsep}{4pt}
\renewcommand\arraystretch{1.05}
\begin{tabular}{c|c|cccc}
\multirow{2}{*}{} & \multirow{2}{*}{$f_\theta(\cdot)$}  & \multicolumn{2}{c}{\textit{mini}ImageNet} & \multicolumn{2}{c}{\textit{tiered}ImageNet} \\
 & & 1-shot      & 5-shot      & 1-shot       & 5-shot       \\ \hlineB{2}
\textit{unidirectional} & \multirow{3}{*}{\textit{VanillaFCN}} & 54.88 & 69.98   &   55.31  & 68.87 \\
MCL & & 55.38 & 70.02 & 57.63 & 74.25 \\
MCL-Katz & & \textbf{55.55} & \textbf{71.74} & \textbf{57.78} & \textbf{74.77}  \\ \hline
\textit{unidirectional}  & \multirow{3}{*}{\textit{PyramidFCN}}  & 54.92            &     69.17        &     55.69         &   69.26  \\
MCL &    & 55.13 & 70.77 & 57.93 & 74.36  \\
MCL-Katz & & \textbf{55.77} & \textbf{71.24} & \textbf{58.20} & \textbf{74.73} \\ \hline
\textit{unidirectional}     & \multirow{3}{*}{\textit{PyramidGrid}} & 56.61 & 71.40  & 55.12 & 69.19 \\
MCL & & 57.50 & 73.03 & 57.57 & 73.81  \\
MCL-Katz &  & \textbf{57.88} & \textbf{74.03} & \textbf{57.63} & \textbf{73.96}
\end{tabular}
\vspace{-3pt}
\caption{Comparisons between the \textit{unidirectional} random walks and \textit{bidirectional} MCL on \textit{mini-}/\textit{tiered}ImageNet with Conv-4.\label{tab:uni}}
\end{table}

\subsection{Fine-grained Few-shot Classification Results}

We follow the same setting (shown in supplementary) as in FRN \cite{wertheimer2021few} to train all the models from scratch on those fine-grained datasets. We re-implement DN4 \cite{li2019revisiting}, DeepEMD \cite{zhang2020deepemd} to thoroughly compare with dense features based methods. Apart from the basic comparisons (both backbones on CUB and Conv-4 backbone on meta-iNat/\textit{tiered}-meta-iNat) in \cite{wertheimer2021few}, we conduct extra ResNet-12 experiments for all the comparing methods on meta-iNat and \textit{tiered}-meta-iNat in our unified framework for a thorough comparison.

Results in Table \ref{tab:finegrained} demonstrate that both our end-to-end MCL (\textit{VanillaFCN}) and the centrality plugin are broadly effective in various fine-grained few-shot classification tasks.

\section{Analysis}

\subsection{Ablation Study}

\textbf{Different choices of $\gamma$,$\beta$.} Since $\mathbf{\Phi}$ is non-square due to the different cardinalities of set $\mathbf{S}$ and $\mathbf{q}$, we use two different scaling parameters in Eqn.(\ref{eq:SIM_sq}) and Eqn.(\ref{eq:SIM_qs}). By the column-wise normalization, $\gamma$ and $\beta$ can be interpreted as the reciprocal of temperatures in softmax random walk probability. Large $\gamma$, $\beta$ will have a hard random walk probability that leads to a concentrated centrality in the affiliation network. However, extremely large $\gamma$, $\beta$ (\eg, one-hot probability when they approaching infinity) would inevitably bias the episodic training due to the potential gradient explosion.

Since the cardinality of set $\mathbf{S}$ is larger than that of $\mathbf{q}$, we empirically use a larger $\gamma$ than $\beta$ as we need a harder probability in random walks from query to the large set of support features. In the experiments, we carefully select $\gamma$ and $\beta$ (generally $\gamma$\texttt{=}$20$ and $\beta$\texttt{=}$10$ for 1-shot models and $\gamma$\texttt{=}$40$ and $\beta$\texttt{=}$20$ for 5-shot models) from several combinations of parameters by their validation performance.

\begin{table}[t]
\small
\centering
\setlength{\tabcolsep}{4pt}
\aboverulesep=0ex
\belowrulesep=0ex
\renewcommand\arraystretch{1.05}
\begin{tabular}{l|cc|cccc}
\multicolumn{1}{c|}{\multirow{2}{*}{}} & \multicolumn{2}{c|}{+MCL} & \multicolumn{2}{c}{\textit{mini}ImageNet} & \multicolumn{2}{c}{\textit{tiered}ImageNet } \\
\multicolumn{1}{c|}{}                  & $\mathbf{q}$ & $\mathbf{s}$ & 1-shot          & 5-shot         & 1-shot           & 5-shot          \\ \hlineB{2}
\multirow{4}{*}{ProtoNet \cite{snell2017prototypical}}  &    &   &  52.32     & 69.74  &        53.19          & 72.28     \\
       &  \checkmark &             &    53.74    &  69.61    & 55.36 & 73.17 \\
      &             &  \checkmark          &      53.97           &     69.74           &      56.60            &     74.18           \\
      & \checkmark   & \checkmark    &  \textbf{54.31}  & \textbf{69.84}  & \textbf{56.67} &  \textbf{74.36}               \\ \hline
\multirow{4}{*}{RelationNet \cite{sung2018learning}}  & & & 52.12 & 66.90  &    54.33   &  69.95  \\
    & \checkmark &             &      53.25           & 66.79 &     54.46 &     70.71            \\
      &      &  \checkmark           &        54.37         &  70.57 &         57.68 &         74.24        \\
      & \checkmark  & \checkmark &    \textbf{54.50} & \textbf{70.63}   & \textbf{57.73}  &    \textbf{74.46}
\end{tabular}
\caption{Ablation of MCL as plug-and-play that individually applied on query features $\mathbf{q}$ and support features $\mathbf{s}$. The experiments are conducted with Conv-4 and \textit{VanillaFCN}\label{tab:plug}}
\end{table}

\begin{table*}[t]
\newcommand{1.3cm}{1.3cm}
\aboverulesep=0ex
\belowrulesep=0ex
\def\cellbox#1{\raisebox{-.5\height}{\includegraphics[height=1.3cm]{#1}}}
\setlength{\tabcolsep}{1pt}
\begin{tabular}{lp{0.068\textwidth}<{\centering}p{0.088\textwidth}<{\centering}cllp{0.027\textwidth{}}p{0.068\textwidth}<{\centering}p{0.088\textwidth}<{\centering}cll}
\rule{0pt}{4ex}
\raisebox{-.5\height}{\rotatebox[origin=l]{90}{\shortstack[l]{\scriptsize{ProtoNet} \\ \scriptsize{\cite{snell2017prototypical}}}}} & \multicolumn{5}{c}{\cellbox{figs/ProtoNet_5way1shot-crop.pdf}} & & \multicolumn{5}{c}{\cellbox{figs/MCL_e2e_5way_e1-crop.pdf}} \\ \rule{0pt}{5ex}
\raisebox{-.5\height}{\rotatebox[origin=l]{90}{\shortstack[l]{\scriptsize{ProtoNet} \\ \scriptsize{+MCL}}}} & \multicolumn{5}{c}{\cellbox{figs/ProtoMEL_5way1shot-crop.pdf}} & & \multicolumn{5}{c}{\cellbox{figs/MCL_e2e_5way_e2-crop.pdf}} \\
\multicolumn{1}{c}{} & \hspace{5pt}\scriptsize{query} & \scriptsize{ground truth}   & \multicolumn{3}{c}{\scriptsize{confounding support classes}} & & \hspace{6pt}\scriptsize{query}  & \scriptsize{ground truth}  & \multicolumn{3}{c}{\scriptsize{confounding support classes}} \\
\multicolumn{6}{c}{\small{(a) MCL as a plugin for feature centralization}} & & \multicolumn{5}{c}{\small{(b) MCL as an end-to-end classification method}}
\end{tabular}
\caption{Grad-CAM visualizations of query and support images in 5-way 1-shot tasks. The left pane (a) illustrates MCL as a plugin on the ProtoNet. The right pane (b) illustrates MCL as an end-to-end classification method. Images (from \textit{mini}ImageNet) at the second column of each pane are from the ground truth class while the four on the far right are the confounding support classes.}
    \label{tab:MEL_Quality}
\end{table*}

\textbf{Influence of Katz attenuation factor $\alpha$.} When $\alpha$ is small, the contribution given by paths longer than one rapidly declines, and the centrality will be determined by short paths (mostly in-degrees). When $\alpha$ is large, long paths are devalued smoothly, and the centrality would be more influenced by endogenous topology. When $\alpha$ approaching 0, the classification will be only determined by the unidirectional query-to-support random walk where the contributions from paths longer than one just vanished. We show comparisons in Table \ref{tab:uni} to demonstrate that performances are improved by introducing mutual affiliations in a bidirectional manner.

In the experiments, we simply use $\alpha=0.5$ for MCL-Katz methods, and the performances could be further improved by selecting different $\alpha$ as shown in supplementary.

\subsection{Computational Speed}

Intuitively, bidirectional methods would be slower than unidirectional ones since their back-and-forth computations. However, our MCL would definitely reach to the periodic equilibrium state as shown in Eqn.(\ref{eq:stationary}). Thus, we could directly solve it by the Katz approximation.

At first glance, the most expensive step in Eqn.(\ref{eq:katz_c}) is inverting $\bm{I} - \alpha\mathbf{P}$ that costs $O(N^3r^3)$ where $N$ is the number of supporting classes and $r$ is the number of dense features for each image input. Fortunately, $\bm{I} - \alpha\mathbf{P}$ is a very special matrix that equals a diagonal matrix minus an anti-diagonal matrix. In this case, we can reformulate it by block-wise matrix inversion:
\begin{equation}\label{eq:block}
\resizebox{0.85\linewidth}{!}{%
$\begin{aligned}[b]
\renewcommand{\arraystretch}{1.2}
    (\bm{I} - \alpha\mathbf{P})^{-1} &= \begin{pmatrix}
    \bm{I} & -\alpha \mathbf{P}_\mathbf{Sq} \\
    -\alpha \mathbf{P}_\mathbf{Sq} & \bm{I}
    \end{pmatrix}^{-1} \\
    &= \begin{pmatrix}
    \bm{I} + \alpha^2 \mathbf{P}_\mathbf{Sq}\mathbf{\Delta}^{-1}\mathbf{P}_\mathbf{qS} & \alpha \mathbf{P}_\mathbf{Sq}\mathbf{\Delta}^{-1} \\
    \alpha \mathbf{\Delta}^{-1} \mathbf{P}_\mathbf{qS} & \mathbf{\Delta}^{-1}\\
    \end{pmatrix}
\end{aligned}
$}
\end{equation}
where $\mathbf{\Delta}$ is defined by $\bm{I}-\alpha^2 \mathbf{P_{Sq}}\mathbf{P_{qS}}$. The most expensive step then becomes a inversion of $\mathbf{\Delta} \in \mathbb{R}^{r\times r}$ and the time complexity is reduced to $O(r^3)$.

As shown in Table \ref{tab:scale}, we compare the inference speed between MCL and other unidirectional dense feature based methods with different image resolutions on 5-way 1-shot FSL tasks with ResNet-12. Each class contains 15 query images in an episode. It can be observed that our bidirectional MCL did not introduce many computational overheads compared to unidirectional methods, and Katz approximation does accelerate computing the stationary distribution.

\subsection{Qualitative Feature Centralization}

To better understand our centrality based methods, we visualize the Grad-CAM \cite{selvaraju2017grad} of the last convolutional layer in ResNet-12 for both plugin and end-to-end methods. We show in Table \ref{tab:MEL_Quality}(a) that our MCL helps ProtoNet concentrate on the most relevant regions of interest. Table \ref{tab:MEL_Quality}(b) demonstrates that the most centralized support features in MCL are not only from the ground truth but also mutually affiliated with task-relevant objects in the query images. We consider it qualitatively validates our underlying idea that support features would be frequently visited in the long times of bidirectional random walks if they shared the same local characteristics with the query image.

\begin{table}[t]{
\centering
\small
\aboverulesep=0ex
\belowrulesep=0ex
\renewcommand{\arraystretch}{1}
\setlength{\tabcolsep}{5pt}
\begin{tabular}{l|cccc}
\multirow{2}{*}{Model} & \multicolumn{4}{c}{\textit{VanillaFCN} resolution $r$} \\
& 5$\times$5 & 8$\times$8 & 10$\times$10 & 12$\times$12 \\ \toprule
DN4 \cite{li2019revisiting} & 11.16 & 13.41 & 16.82 & 23.45 \\
DeepEMD \cite{zhang2020deepemd} & 262.0 & 814.6 & 2781.9 & 8035.4 \\
FRN \cite{wertheimer2021few} \scriptsize{(Ridge regression)} & 14.55 & 20.42 & 25.81 & 30.65 \\
FRN \cite{wertheimer2021few} \scriptsize{(Woodbury identity)} & 36.74 & 42.33 & 47.31 & 55.84 \\ \midrule
MCL \scriptsize{(\texttt{torch.pinverse})} & 55.91 & 119.0 & 292.2 & 464.8 \\
MCL \scriptsize{(QR decomposition)} & 600.0 & 658.6 & 719.4 & 802.6 \\
MCL \scriptsize{(Katz approximation)} & 12.59 & 14.59 & 18.92 & 29.10
\end{tabular}
\caption{Time per episode (ms) for different feature map resolutions $r$ on 5-way 1-shot tasks where the feature extraction time is excluded for all comparing methods. \label{tab:scale}}}
\end{table}

\section{Conclusions}

We present a novel dense feature based framework: Mutual Centralized Learning (MCL) to highlight the mutual affiliations of bipartite dense features in FSL. We introduce a novel dense features' accessibility criterion and demonstrate classic transductive methods like label propagation could be easily adapted to the inductive setting if we treat dense features from a single image as the set of unlabeled data. We propose bidirectional random walk to learn mutual affiliations in FSL and prove its features' accessibility in a long time-homogeneous Markov process is equivalent to the single-mode eigenvector centrality of an affiliation network. We show that such centrality could not only serve as a noval end-to-end classification criterion but also as a plugin in existing methods. Experimental results demonstrate MCL achieves the state-of-the-art on various datasets.

{\small
\bibliographystyle{ieee_fullname}