Fixed-Point Centrality for Networks

The formulation of fixed-point centrality in this paper follows the idea of the seminal work on graph neural network models ([24, 25]) in using fixed points of some underlying mappings associated with networks. Fixed-point characterizations find applications in many problems in data science, including graph neural networks ([24, 25]), implicit neural networks ([26, 27, 28, 29]), deep equilibrium models [30], among others [31]. A first salient feature of fixed-point centralities that distinguishes themselves from these models above is that permutation equivariance properties must be satisfied. Another salient feature of fixed-point centralities is that the values of fixed-point centralities are restricted to real numbers to allow natural rankings of the nodes and are restricted to non-negative numbers to allow interpretations (after normalizations) as probability distributions. Furthermore, the current paper focuses on variations of the fixed point (centralities) with respect to the variations of graph structures and weights, which differs from [24, 25, 26, 27, 28, 29, 30].

Centralities and graph neural networks are respectively generalized in [18] and [32] to those for infinite graphs characterized by graphons (developed in [33, 34, 35] to characterize dense graph sequences and their limits). The work [18] studies the eigencentrality, PageRank centrality, Katz-Bonacich centrality of symmetric graphs generated from graphons and establishes the rate of convergence of these centralities to the associated graphon centralities. The fixed-point centrality for graphon in the current paper provides a unified view towards these centralities. The graphon versions of graph neural networks as approximations or generalization models of graph neural networks are proposed and analyzed in [32]. One modelling difference is that the graphon neural networks are characterized by layered structures in [32] whereas in the current paper fixed-point equilibrium structures are employed.

We propose the “fixed-point centrality”, which is a class of centralities that can be constructed via a (permutation equivariant) fixed-point mapping associated with the underlying graph. This class of centralities unifies many different centralities (including PageRank centrality, eigencentrality, and Katz-Bonacich centrality) and furthermore it connects to a variety of different problems including graph neural networks [24], and LQG mean field games on networks [20]. In addition, fixed-point centralities are applicable to a broader class of graphs, whether they are undirected or directed, unweighted or weighted (with possibly negative weights), finite or infinite. Moreover, variation bounds of fixed-point centralities with respect to the variations of the underlying graphs are established under mild assumptions following a rather simple idea based on fixed-point analysis.

Notation: $\mathds{R}$ and $\mathds{R}_{\geq 0}$ denote respectively reals and non-negative reals. For $A\in\mathds{R}^{n\times n}$, $\mathcal{G}(A)$ denotes the graph with the adjacency matrix $A$ and the node set $[n]\triangleq\{1,...,n\}$. $\mathcal{G}(V,E)$ denotes the graph with vertex set $V$ and edge set $E\subset V\times V$. For a vector $v\in\mathds{R}^{n}$, $\text{span}(v)\triangleq\{\alpha v:\alpha\in\mathds{R}^{n}\}$. $\mathbf{1}_{n}$ denotes the $n$-dimensional column vector of $1$s and $\mathbf{1}$ denotes the function defined over $[0,1]$ with $\mathbf{1}_{\alpha}=1$ for all $\alpha\in[0,1]$. We use the word “network” to refer to an interconnected group or system where the connection structures along with weights can be characterized by some graph $\mathcal{G}(A)$. For a vector $v\in\mathds{R}^{n}$, $\text{diag}(v)$ denotes the $n\times n$ diagonal matrix with the elements of $v$ on the main diagonal, $[v]_{i}$ (or $v_{i}$) denotes the $i$th element of $v$, $\left\|{v}\right\|_{p}\triangleq\left(\sum_{i=1}^{n}\left|v_{i}\right|^{p}\right)^{1/p}$ with $1\leq p<\infty$, and $\|v\|_{\infty}\triangleq\max_{i\in[n]}|v_{i}|.$ For a matrix $A\in\mathds{R}^{n\times n}$, $[A]_{ij}$ (or $a_{ij}$) denotes the $ij$th element of $A$ and $\|A\|_{p}\triangleq\sup_{v\in\mathds{R}^{n},v\neq 0}\frac{\|Av\|_{p}}{\|v\|_{p}}$ with $1\leq p\leq\infty$. We note that $\|A\|_{1}=\max_{1\leq j\leq n}\sum_{i=1}^{m}|a_{ij}|~{}\text{and}~{}\|A\|_{2}={\sqrt{\lambda_{\max}\left(A^{*}A\right)}}.$

Consider a graph $\mathcal{G}(A)$ with non-negative adjacency matrix $A=[a_{ij}]\in\mathds{R}^{n\times n}$. Depending on $A$, the graph $\mathcal{G}(A)$ may be directed or undirected, and weighted or unweighted.

1. (E1)

   Eigencentrality (proposed in [9]): Assume the largest eigenvalue $\lambda_{1}$ of $A$ is simple (i.e. $\lambda_{1}$ has multiplicity $1$). Then the eigencentrality of $\mathcal{G}(A)$ is given by

   $$\rho_{i}=\left[\lim_{k\to\infty}\Big{(}\frac{1}{\lambda_{1}}A^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\Big{)}^{k}\mathbf{1}_{n}\right]_{i},\quad i\in[n].$$

   An equivalent form in terms of local connections is

   $$\rho_{i}=\frac{1}{\lambda_{1}}\sum_{j=1}^{N}a_{ji}\rho_{j},~{}~{}i\in[n],\quad\text{i.e.}\quad\rho=\frac{1}{\lambda_{1}}A^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\rho.$$

2. (E2)

   Katz-Bonacich centrality with $\alpha\in(0,1)$ (proposed in [10] and generalized in [11, 12]): Let $\alpha<\|A\|_{2}^{-1}$. One (simplest) Katz-Bonacich centrality is given by

   $\displaystyle\rho_{i}$

   $\displaystyle=\sum_{k=0}^{\infty}\sum_{j=1}^{n}\alpha^{k}[A^{k}]_{ji}=\left[\sum_{k=0}^{\infty}\alpha^{k}A^{{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}^{k}}\mathbf{1}_{n}\right]_{i},\quad i\in[n],$

   where the upper bound of $\alpha$ ensures the boundedness of the infinite series. An equivalent form in terms of local connections is given by

   $$\rho_{i}=\alpha\sum_{j=1}^{n}a_{ji}\rho_{j}+1,~{}i\in[n],\quad\text{i.e.}\quad\rho=\alpha A^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\rho+\mathbf{1}_{n},$$

   and the equivalent explicit form is $\rho=(1-\alpha A^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}})^{-1}\mathbf{1}_{n}.$

3. (E3)

   PageRank centrality (proposed in [13]): Consider a network of webpages, where each node represents a webpage, and $a_{ji}=1$ if there is a hyperlink from webpage $j$ to $i$ and $a_{ij}=0$ otherwise [13]. PageRank centrality with $\alpha\in(0,1)$ is given by

   $$\rho_{i}=\alpha\sum_{j=1}^{n}a_{ji}{\frac{\rho_{j}}{d_{j}}}+{\frac{1-\alpha}{n}},\quad d_{j}=\sum_{i=1}^{n}a_{ji},\quad i\in[n],$$

   where $\alpha\frac{a_{ji}}{{d_{j}}}\rho_{j}+(1-\alpha)n^{-2}$ is the probability of jumping from node $j$ to node $i$ in the steady state of the associated random walk. In equivalent forms, PageRank centrality $\rho$ satisfies

   $$\rho=\alpha A^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}D^{-1}\rho+\frac{1-\alpha}{n}\mathbf{1}_{n},~{}~{}\text{with}~{}D\triangleq\textup{diag}(d_{1},...,d_{n})$$

   and the explicit computation form is given by

   $$\rho=\frac{1-\alpha}{n}(I-\alpha A^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}D^{-1})^{-1}\mathbf{1}_{n}.$$

   PageRank centrality can be interpreted as the steady state distribution of random walks on the network.

Graphons are defined as bounded symmetric measurable functions $\mathbf{A}:[0,1]^{2}\to[0,1]$, which, roughly speaking, can be viewed as the “adjacency matrix” of graphs with the vertex set $[0,1]$ (see [36]). Let $\mathcal{W}_{0}$ denote the set of graphons with the range $[0,1]$. A graphon $\mathbf{A}\in\mathcal{W}_{0}$ can be interpreted as an integral operator (for instance from $L^{2}([0,1])$ to $L^{2}([0,1])$) as follows:

$$(\mathbf{A}\mathbf{v})(\cdot)=\int_{[0,1]}\mathbf{A}(\cdot,\alpha)\mathbf{v}_{\alpha}d\alpha,\quad\mathbf{v}\in L^{2}([0,1]).$$

The definitions of eigenvector, PageRank and Katz-Bonacich centralities for graphons in [18] are summarized below. Consider a graphon $\mathbf{A}\in\mathcal{W}_{0}$.

1. (E4)

   The graphon eigencentrality for $\mathbf{A}$ is given by

   $$\rho=\frac{1}{\lambda_{1}}\mathbf{A}\rho,\quad(\mathbf{A}\rho)(\cdot)\triangleq\int_{[0,1]}\mathbf{A}(\cdot,\alpha)\rho_{\alpha}d\alpha,$$

   where $\rho$ denotes the eigenfunction in $L^{2}([0,1])$ associated to the largest eigenvalue $\lambda_{1}$ of $\mathbf{A}$ and $\lambda_{1}$ is assumed to have multiplicity $1$.

2. (E5)

   The graphon Katz-Bonacich centrality with $\alpha\in(0,1)$ for $\mathbf{A}$ is defined by one of the equivalent forms:

   $\displaystyle\rho=\sum_{k=1}^{\infty}\alpha^{k}\mathbf{A}^{k}\mathbf{1},~{}\rho=(I-\alpha\mathbf{A})^{-1}\mathbf{1},\text{or }\rho=~{}\alpha\mathbf{A}\rho+\mathbf{1}$

   where $\alpha<\frac{1}{\lambda_{1}}$ and $\lambda_{1}$ is the largest eigenvalue of $\mathbf{A}$.

3. (E6)

   The graphon PageRank centrality with $\alpha\in(0,1)$ for $\mathbf{A}$ is given by

   $$\rho=\alpha\mathbf{A}\odot\mathbf{D}^{-1}\rho+({1-\alpha})\mathbf{1},\quad\mathbf{A}\in\mathcal{W}_{0},$$

   (1)

   where $\mathbf{D}(x)=\int_{[0,1]}\mathbf{A}(y,x)dy,$ and $(\mathbf{A}\odot\mathbf{D}^{-1})(x)=\frac{\mathbf{A}(x,y)}{\mathbf{D}(y)}$ if $\mathbf{D}(y)\neq 0$, and zero otherwise. Equivalent representation forms are as follows: $\rho=(1-\alpha)(I-\alpha\mathbf{A}\odot\mathbf{D}^{-1})^{-1}\mathbf{1}$ and $\rho=(1-\alpha)\sum_{k=0}^{\infty}\big{(}\alpha\mathbf{A}\odot\mathbf{D}^{-1}\big{)}^{k}\mathbf{1}.$

Proofs are omitted as readers can readily verify the result.

We emphasize that the choice of $S$ in (2) can be very general: it can be a set of vectors, matrices, functions, probability distributions, strings, etc. Below we give an example where $S$ is the space of continuous functions from $[0,T]$ to $\mathds{R}^{q}$ denoted by $C([0,T];\mathds{R}^{q})$ with $q\geq 1$.

We omit the details of the problem formulation of LQG Network Mean Field Games which requires significant space. Interested readers are referred to [21, Sec. IV-B].

An automorphism of a (directed or undirected) graph $\mathcal{G}(V,E)$ is a permutation map $\pi:V\to V$ that satisfies

$$(i,j)\in E\quad\text{if and only if}\quad(\pi(i),\pi(j))\in E,~{}\forall i,j\in V.$$

A vertex transitive graph is a graph $\mathcal{G}$ satisfying that for any given node pair $(i,j)$, there exists some automorphism map $\phi^{i,j}\in\Pi$ such that $\phi^{i,j}(i)=j,$ where $\Pi$ denotes the set of permutation mappings $\pi:[n]\to[n]$. See [42] for examples of vertex transitive graphs.

Properties in Prop. 5 and Prop. 6 are general properties shared by all existing centralities that depend only on graph structures. These properties may not hold in general for the outputs of graph neural network models ([24, 25]).

Consider two graphs $\mathcal{G}(A)$ and $\mathcal{G}(B)$ with the same number of nodes. Let $\rho_{A}$ be a fixed-point centrality for $\mathcal{G}(A)$ and $\rho_{B}$ that of $\mathcal{G}(B)$ with the same function $f(\cdot,\cdot)$, that is,

		$\displaystyle x_{A}=f(A,x_{A}),\quad\rho_{A}=g(x_{A}),$		(3)
		$\displaystyle x_{B}=f(B,x_{B}),\quad\rho_{B}=g(x_{B}),$

where $S^{n}$ is specialized to $\mathds{R}^{n}$, and $f(\cdot,\cdot):{\mathds{R}}^{n\times n}\times\mathds{R}^{n}\to{\mathds{R}}^{n}$ and $g(\cdot):\mathds{R}^{n}\to\mathds{R}^{n}$. (The specialization of $S^{n}$ to $\mathds{R}^{n}$ is for the simplicity of presentation, and it can be relaxed to any normed vector space). In this section we study the conditions under which $\rho_{A}$ and $\rho_{B}$ are close and establish upper bounds of their differences.

Let $\mathcal{U}_{f}\subset\mathds{R}^{n}$ denote the set of feasible fixed-point features with $f(\cdot,\cdot)$ in (3). Consider the following assumption.
Assumption (A1): (a) There exists $L_{1}>0$ such that for all $x\in\mathcal{U}_{f}$,

$$\|f(A,x)-f(B,x)\|\leq L_{1}\|A-B\|_{\textup{op}},$$

(4)

where the operator norm $\|A\|_{\textup{op}}\triangleq\sup_{v\in\mathds{R}^{n},v\neq 0}\frac{\|Av\|}{\|v\|}$;
(b) For any matrix $A$ and for any $x\in\mathcal{U}_{f}$, there exists $L_{0}(A,x)\geq 0$ such that

$$\|f(A,x_{A})-f(A,x)\|\leq L_{0}(A,x)\|x_{A}-x\|$$

(5)

where $x_{A}=f(A,x_{A})$;
(c) For the given matrix $A$,

$$L_{0}(A)\triangleq\sup_{x\in\mathcal{U}_{f}}L_{0}(A,x)<1;$$

(d) There exists $L_{g}>0$ such that for all $x,v\in\mathcal{U}_{f}$,

$$\|g(x)-g(v)\|\leq L_{g}\|x-v\|.$$

We call (A1)-(c) the Contraction Condition for Fixed-Point Centrality for $\mathcal{G}(A)$; if, furthermore, $\mathcal{U}_{f}$ is complete under the chosen norm $\|\cdot\|$, it then gives the existence of a unique fixed-point feature for $f(A,\cdot)$ following Banach fixed-point theorem, and one can simply apply fixed-point iterations to identify such fixed-point feature with the given graph $\mathcal{G}(A)$.

For Katz-Bonacich centrality, we choose $2$-norm and $L_{0}(A)=\alpha\|A\|_{\textup{2}}<1$ if $\alpha<\|A\|_{\textup{2}}^{-1}$. For PageRank centrality, we choose $1$-norm and $L_{0}(A)=\alpha\|A^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\text{diag}(A^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\mathbf{1}_{n})^{-1}\|_{\textup{1}}<1$ if $\alpha<\|A^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\text{diag}(A^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\mathbf{1}_{n})^{-1}\|_{\textup{1}}^{-1}$.

Centralities can be associated with probability distributions: PageRank centrality is the steady state distribution of random walks on the graph of hyperlinks [13], and degree centrality is used as the probability distribution for forming new connections [44]. To (uniquely) associate the fixed-point centrality with a probability (mass function), we consider the following assumption.
Assumption (A2): The fixed-point centralities are normalized with nonnegative entries, that is,

$$\sum_{i\in[n]}\rho_{i}=1,\quad\rho_{i}\geq 0,\quad\forall i\in[n].$$

Clearly, this implies $\|\rho\|_{1}\triangleq\sum_{i=1}^{n}|\rho_{i}|=1$.

For a metric space $(\mathcal{X},d)$ and $p\geq 1$, let ${\displaystyle P_{p}(\mathcal{X})}$ denote the set of all probability measures on $\mathcal{X}$ with finite $p$th moment. The $p$-Wasserstein distance between two probability measures in ${\displaystyle P_{p}(\mathcal{X})}$ is defined as follows:

$$W_{p}(\rho_{A},\rho_{B})=\bigg{(}\inf_{\gamma\in\Gamma(\rho_{A},\rho_{B})}\int_{\mathcal{X}\times\mathcal{X}}d(x,y)^{p}d\gamma(x,y)\bigg{)}^{\frac{1}{p}}$$

where $\Gamma(\rho_{A},\rho_{B})$ denotes the set of probability measures on $\mathcal{X}\times\mathcal{X}$ with marginals $\rho_{A}$ and $\rho_{B}$.

When $p=2$, the operator norm $\|A\|_{\textup{op},2}$ is the maximum singular value of $A$. Consider the matrix cut norm [45]

$$\|A\|_{\Box}\triangleq\max_{S\times T\subset[n]\times[n]}\Big{|}\sum_{i\in S,j\in T}a_{ij}\Big{|},\quad A\in\mathds{R}^{n\times n}$$

(10)

(without the scaling factor $\frac{1}{n^{2}}$ used in [36, p.127]).

Replacing the operator norm by the cut norm in Prop. 7 via the inequality in Lemma 1 yields the following result.

Let $\mathcal{W}_{c}$ denote the set of symmetric measurable functions $\mathbf{W}:[0,1]^{2}\to[-c,c]$ with $c>0$. Let $S^{[0,1]}$ denote the infinite Cartesian product of $S$ with the index set $[0,1]$. Let $d$ denotes the metric for $S^{[0,1]}$. Similar to the finite graph case, a centrality for a graphon with the vertex set $[0,1]$ is defined as the mapping $\rho:[0,1]\to\mathds{R}_{\geq 0}$ which characterizes the “importance” of nodes on the infinite network associated with the underlying graphon.