Graph Neural Networks (GNNs) are widely used deep learning models that learn
meaningful representations from graph-structured data. Due to the finite nature
of the underlying recurrent structure, current GNN methods may struggle to
capture long-range dependencies in underlying graphs. To overcome this
difficulty, we propose a graph learning framework, called Implicit Graph Neural
Networks (IGNN), where predictions are based on the solution of a fixed-point
equilibrium equation involving implicitly defined "state" vectors. We use the
Perron-Frobenius theory to derive sufficient conditions that ensure
well-posedness of the framework. Leveraging implicit differentiation, we derive
a tractable projected gradient descent method to train the framework.
Experiments on a comprehensive range of tasks show that IGNNs consistently
capture long-range dependencies and outperform the state-of-the-art GNN models.

本文提出了一种名为 “Implicit Graph Neural Networks（IGNN）” 的图学习框架，其利用 Perron-Frobenius 理论来确保该框架的良好性，并利用隐式微分得到一种可行的投影梯度下降法来训练该框架，实验证明 IGNN 可以稳定捕捉长程依赖并优于现有的 GNN 模型。

隐式图神经网络

Implicit Graph Neural Networks

We derive and analyse a new iterative algorithm for detecting network
core--periphery structure. Using techniques in nonlinear Perron-Frobenius
theory, we prove global convergence to the unique solution of a relaxed version
of a natural discrete optimization problem. On sparse networks, the cost of
each iteration scales linearly with the number of nodes, making the algorithm
feasible for large-scale problems. We give an alternative interpretation of the
algorithm from the perspective of maximum likelihood reordering of a new
logistic core--periphery random graph model. This viewpoint also gives a new
basis for quantitatively judging a core--periphery detection algorithm. We
illustrate the algorithm on a range of synthetic and real networks, and show
that it offers advantages over the current state-of-the-art.

本文提出一种新的迭代算法，用于检测网络中的核心和边缘结构，利用非线性 Perron-Frobenius 理论技术，证明了在一个自然的离散优化问题的松弛版本下全局收敛于唯一的解。该算法的迭代成本在稀疏网络上随着节点数量的线性增长，使其可以用于大规模问题。我们从新的 logistic random graph model 的最大似然重排序的角度给出了算法的另一种解释，在判断核心 - 边缘检测算法方面也提供了一种新的基础。我们在一些合成和实际网络上展示了该算法，并证明它比当前的最先进技术具有优势。

网络中核心 - 边缘检测的非线性谱方法

A Nonlinear Spectral Method for Core--Periphery Detection in Networks

Recent results of Ye and Hansen, Miltersen and Zwick show that policy
iteration for one or two player (perfect information) zero-sum stochastic
games, restricted to instances with a fixed discount rate, is strongly
polynomial. We show that policy iteration for mean-payoff zero-sum stochastic
games is also strongly polynomial when restricted to instances with bounded
first mean return time to a given state. The proof is based on methods of
nonlinear Perron-Frobenius theory, allowing us to reduce the mean-payoff
problem to a discounted problem with state dependent discount rate. Our
analysis also shows that policy iteration remains strongly polynomial for
discounted problems in which the discount rate can be state dependent (and even
negative) at certain states, provided that the spectral radii of the
nonnegative matrices associated to all strategies are bounded from above by a
fixed constant strictly less than 1.

这篇论文采用非线性 Perron-Frobenius 理论的方法，将 mean-payoff 问题转化为一个具有状态依赖性折现率的折扣问题，从而证明了一个有界的第一次均值回报时间的固定状态，是广义策略迭代强多项式可解的，同时如果所有策略涉及的非负矩阵的谱半径都小于某个值，则折扣问题中折扣率可以是具有状态依赖性（甚至是负值）的。