Search

Predicting unseen relations that cannot be observed during the training phase is a challenging task in relation extraction. Previous works have made progress by matching the semantics between input instances and label descriptions. However, fine-grained matching often requires laborious manual annotation, and rich interactions between instances and label descriptions come with significant computational overhead. In this work, we propose an efficient multi-grained matching approach that uses virtual entity matching to reduce manual annotation cost, and fuses coarse-grained recall and fine-grained classification for rich interactions with guaranteed inference speed. Experimental results show that our approach outperforms the previous State Of The Art (SOTA) methods, and achieves a balance between inference efficiency and prediction accuracy in zero-shot relation extraction tasks. Our code is available at https://github.com/longls777/EMMA., Comment: Accepted to the main conference of NAACL2024

The toughness $\tau(G)=\mathrm{min}\{\frac{|S|}{c(G-S)}: S~\mbox{is a cut set of vertices in}~G\}$ for $G\ncong K_n.$ The concept of toughness initially proposed by Chv$\mathrm{\acute{a}}$tal in 1973, which serves as a simple way to measure how tightly various pieces of a graph hold together. A graph $G$ is called $t$-tough if $\tau(G)\geq t.$ It is very interesting to investigate the relations between toughness and eigenvalues of graphs. Fan, Lin and Lu [European J. Combin. 110 (2023) 103701] provided sufficient conditions in terms of the spectral radius for a graph to be 1-tough with minimum degree $\delta$ and $t$-tough with $t\geq 1$ being an integer, respectively. By using some typical distance spectral techniques and structural analysis, we in this paper present sufficient conditions based on the distance spectral radius to guarantee a graph to be 1-tough with minimum degree $\delta.$ Moreover, we also prove sufficient conditions with respect to the distance spectral radius for a graph to be $t$-tough, where $t$ or $\frac{1}{t}$ is a positive integer.

For any integer $k\geq1,$ a graph $G$ has a $k$-factor if it contains a $k$-regular spanning subgraph. In this paper we prove a sufficient condition in terms of the number of $r$-cliques to guarantee the existence of a $k$-factor in a graph with minimum degree at least $\delta$, which improves the sufficient condition of O \cite{O2021} based on the number of edges. For any integer $k\geq2,$ a spanning $k$-tree of a connected graph $G$ is a spanning tree in which every vertex has degree at most $k$. Motivated by the technique of Li and Ning \cite{Li2016}, we present a tight spectral condition for an $m$-connected graph to have a spanning $k$-tree, which extends the result of Fan, Goryainov, Huang and Lin \cite{Fan2021} from $m=1$ to general $m$. Let $T$ be a spanning tree of a connected graph. The leaf degree of $T$ is the maximum number of leaves adjacent to $v$ in $T$ for any $v\in V(T)$. We provide a tight spectral condition for the existence of a spanning tree with leaf degree at most $k$ in a connected graph with minimum degree $\delta$, where $k\geq1$ is an integer., Comment: 17 pages, 3 figures

Let $G$ be a graph and $h: E(G)\rightarrow [0,1]$ be a function. For any two positive integers $a$ and $b$ with $a\leq b$, a fractional $[a,b]$-factor of $G$ with the indicator function $h$ is a spanning subgraph with vertex set $V(G)$ and edge set $E_h$ such that $a\leq\sum_{e\in E_{G}(v)}h(e)\leq b$ for any vertex $v\in V(G)$, where $E_h = \{e\in E(G)|h(e)>0\}$ and $E_{G}(v)=\{e\in E(G)| e~\mbox{is incident with}~v~\mbox{in}~G\}$. A graph $G$ is ID-factor-critical if for every independent set $I$ of $G$ whose size has the same parity as $|V(G)|$, $G-I$ has a perfect matching. In this paper, we present a tight sufficient condition based on the spectral radius for a graph to contain a fractional $[a,b]$-factor, which extends the result of Wei and Zhang [Discrete Math. 346 (2023) 113269]. Furthermore, we also prove a tight sufficient condition in terms of the spectral radius for a graph with minimum degree $\delta$ to be ID-factor-critical., Comment: 14 pages, 2 figures

A fractional matching of a graph $G$ is a function $f:E(G)\rightarrow [0, 1]$ such that for any $v\in V(G)$, $\sum_{e\in E_{G}(v)}f(e)\leq1$, where $E_{G}(v)=\{e\in E(G): e~ \mbox{is incident with} ~v~\mbox{in}~G\}$.The fractional matching number of $G$ is $\mu_{f}(G)=\mathrm{max}\{\sum_{e\in E(G)}f(e):f$ is a fractional matching of $G\}$. Let $k\in (0,n)$ is an integer. In this paper, we prove a tight lower bound of the spectral radius to guarantee $\mu_{f}(G)>\frac{n-k}{2}$ in a graph with minimum degree $\delta,$ which implies the result on the fractional perfect matching due to Fan et al. [Discrete Math. 345 (2022) 112892]. For a set $\{A, B, C, \ldots\}$ of graphs, an $\{A, B, C, \ldots\}$-factor of a graph $G$ is defined to be a spanning subgraph of $G$ each component of which is isomorphic to one of $\{A, B, C, \ldots\}$.We present a tight sufficient condition in terms of the spectral radius for the existence of a $\{K_2, \{C_k\}\}$-factor in a graph with minimum degree $\delta,$ where $k\geq 3$ is an integer. Moreover, we also provide a tight spectral radius condition for the existence of a $\{K_{1, 1}, K_{1, 2}, \ldots , K_{1, k}\}$-factor with $k\geq2$ in a graph with minimum degree $\delta,$ which generalizes the result of Miao et al. [Discrete Appl. Math. 326 (2023) 17-32]., Comment: 12 pages, 3 figures

Let $G$ be a non-bipartite graph which does not contain any odd cycle of length at most $2k+1$. In this paper, we determine the maximum $Q$-index of $G$ if its order is fixed, and the corresponding extremal graph is uniquely characterized. Moreover, if the size of $G$ is given, the maximum $Q$-index of $G$ and the unique extremal graph are also proved., Comment: 15 pages, 5 figures. arXiv admin note: text overlap with arXiv:2209.00801

For integer $k\geq2,$ a spanning $k$-ended-tree is a spanning tree with at most $k$ leaves. Motivated by the closure theorem of Broersma and Tuinstra [Independence trees and Hamilton cycles, J. Graph Theory 29 (1998) 227--237], we provide tight spectral conditions to guarantee the existence of a spanning $k$-ended-tree in a connected graph of order $n$ with extremal graphs being characterized. Moreover, by adopting Kaneko's theorem [Spanning trees with constraints on the leaf degree, Discrete Appl. Math. 115 (2001) 73--76], we also present tight spectral conditions for the existence of a spanning tree with leaf degree at most $k$ in a connected graph of order $n$ with extremal graphs being determined, where $k\geq1$ is an integer.

For a graph $G$ with domination number $\gamma$, Hedetniemi, Jacobs and Trevisan [European Journal of Combinatorics 53 (2016) 66-71] proved that $m_{G}[0,1)\leq \gamma$, where $m_{G}[0,1)$ means the number of Laplacian eigenvalues of $G$ in the interval $[0,1)$. Let $T$ be a tree with diameter $d$. In this paper, we show that $m_{T}[0,1)\geq (d+1)/3$. However, such a lower bound is false for general graphs. All trees achieving the lower bound are completely characterized. Moreover, for a tree $T$, we establish a relation between the Laplacian eigenvalues, the diameter and the domination number by showing that the domination number of $T$ is equal to $(d+1)/3$ if and only if it has exactly $(d+1)/3$ Laplacian eigenvalues less than one. As an application, it also provides a new type of trees, which show the sharpness of an inequality due to Hedetniemi, Jacobs and Trevisan.

The spread of rumors along with breaking events seriously hinders the truth in the era of social media. Previous studies reveal that due to the lack of annotated resources, rumors presented in minority languages are hard to be detected. Furthermore, the unforeseen breaking events not involved in yesterday's news exacerbate the scarcity of data resources. In this work, we propose a novel zero-shot framework based on prompt learning to detect rumors falling in different domains or presented in different languages. More specifically, we firstly represent rumor circulated on social media as diverse propagation threads, then design a hierarchical prompt encoding mechanism to learn language-agnostic contextual representations for both prompts and rumor data. To further enhance domain adaptation, we model the domain-invariant structural features from the propagation threads, to incorporate structural position representations of influential community response. In addition, a new virtual response augmentation method is used to improve model training. Extensive experiments conducted on three real-world datasets demonstrate that our proposed model achieves much better performance than state-of-the-art methods and exhibits a superior capacity for detecting rumors at early stages., Comment: AAAI 2023

For integer $k\geq2,$ a graph $G$ is called $k$-leaf-connected if $|V(G)|\geq k+1$ and given any subset $S\subseteq V(G)$ with $|S|=k,$ $G$ always has a spanning tree $T$ such that $S$ is precisely the set of leaves of $T.$ Thus a graph is $2$-leaf-connected if and only if it is Hamilton-connected. In this paper, we present a best possible condition based upon the size to guarantee a graph to be $k$-leaf-connected, which not only improves the results of Gurgel and Wakabayashi [On $k$-leaf-connected graphs, J. Combin. Theory Ser. B 41 (1986) 1-16] and Ao, Liu, Yuan and Li [Improved sufficient conditions for $k$-leaf-connected graphs, Discrete Appl. Math. 314 (2022) 17-30], but also extends the result of Xu, Zhai and Wang [An improvement of spectral conditions for Hamilton-connected graphs, Linear Multilinear Algebra, 2021]. Our key approach is showing that an $(n+k-1)$-closed non-$k$-leaf-connected graph must contain a large clique if its size is large enough. As applications, sufficient conditions for a graph to be $k$-leaf-connected in terms of the (signless Laplacian) spectral radius of $G$ or its complement are also presented., Comment: 15 pages, 2 figures

The difference between the two largest eigenvalues of the adjacency matrix of a graph $G$ is called the spectral gap of $G.$ If $G$ is a regular graph, then its spectral gap is equal to algebraic connectivity. Abdi, Ghorbani and Imrich, in [European J. Combin. 95 (2021) 103328], showed that the minimum algebraic connectivity of cubic connected graphs on $2n$ vertices is $(1+o(1))\frac{\pi^{2}}{2n^{2}}$, which is attained on non-bipartite graphs. Motivated by the above result, we in this paper investigate the algebraic connectivity of cubic bipartite graphs. We prove that the minimum algebraic connectivity of cubic bipartite graphs on $2n$ vertices is $(1+o(1))\frac{\pi^{2}}{n^{2}}$. Moreover, the unique cubic bipartite graph with minimum algebraic connectivity is completed characterized. Based on the relation between the algebraic connectivity and spectral gap of regular graphs, the cubic bipartite graph with minimum spectral gap and the corresponding asymptotic value are also presented. In [J. Graph Theory 99 (2022) 671--690], Horak and Kim established a sharp upper bound for the number of perfect matchings in terms of the Fibonacci number. We obtain a spectral characterization for the extremal graphs by showing that a cubic bipartite graph has the maximum number of perfect matchings if and only if it minimizes the algebraic connectivity., Comment: 19 pages, 4 figures

Let $\lambda^{*}$ be the maximum spectral radius of connected irregular graphs on $n$ vertices with maximum degree $\Delta$. Liu, Shen and Wang (2007) conjectured that $\lim_{n\rightarrow \infty}(n^{2}(\Delta-\lambda^{*}))/(\Delta-1)=\pi^{2},$ which describes the asymptotic behavior for the maximum spectral radius of irregular graphs. Focusing on this conjecture, we consider the maximum spectral radius of connected subcubic bipartite graphs. The unique connected subcubic bipartite graph with the maximum spectral radius is determined. Let $G$ be a $k$-connected irregular graph with spectral radius $\lambda_{1}(G)$, we present a lower bound for $\Delta-\lambda_{1}(G)$. Moreover, if $H$ is a proper subgraph of a $k$-connected $\Delta$-regular graph, a lower bound for $\Delta-\lambda_{1}(H)$ is also obtained. These bounds improve some previous results., Comment: 15 pages, 1 figures

A classic result in extremal graph theory, known as Mantel's theorem, states that every non-bipartite graph of order $n$ with size $m>\lfloor \frac{n^{2}}{4}\rfloor$ contains a triangle. Lin, Ning and Wu [Comb. Probab. Comput. 30 (2021) 258-270] proved a spectral version of Mantel's theorem for given order $n.$ Zhai and Shu [Discrete Math. 345 (2022) 112630] investigated a spectral version for fixed size $m.$ In this paper, we prove $Q$-spectral versions of Mantel's theorem., Comment: 14 pages, 4 figures

A bipartite graph is subcubic if it is an irregular bipartite graph with maximum degree three. In this paper, we prove that the asymptotic value of maximum spectral radius over subcubic bipartite graphs of order $n$ is $3-\varTheta(\frac{\pi^{2}}{n^{2}})$. Our key approach is taking full advantage of the eigenvalues of certain tridiagonal matrices, due to Willms [SIAM J. Matrix Anal. Appl. 30 (2008) 639--656]. Moreover, for large maximum degree, i.e., the maximum degree is at least $\lfloor n/2 \rfloor$, we characterize irregular bipartite graphs with maximum spectral radius. For general maximum degree, we present an upper bound on the spectral radius of irregular bipartite graphs in terms of the order and maximum degree., Comment: 15 pages, 1 figure

In multi-label text classification (MLTC), each given document is associated with a set of correlated labels. To capture label correlations, previous classifier-chain and sequence-to-sequence models transform MLTC to a sequence prediction task. However, they tend to suffer from label order dependency, label combination over-fitting and error propagation problems. To address these problems, we introduce a novel approach with multi-task learning to enhance label correlation feedback. We first utilize a joint embedding (JE) mechanism to obtain the text and label representation simultaneously. In MLTC task, a document-label cross attention (CA) mechanism is adopted to generate a more discriminative document representation. Furthermore, we propose two auxiliary label co-occurrence prediction tasks to enhance label correlation learning: 1) Pairwise Label Co-occurrence Prediction (PLCP), and 2) Conditional Label Co-occurrence Prediction (CLCP). Experimental results on AAPD and RCV1-V2 datasets show that our method outperforms competitive baselines by a large margin. We analyze low-frequency label performance, label dependency, label combination diversity and coverage speed to show the effectiveness of our proposed method on label correlation learning., Comment: Accepted by ACL 2021 (Finding)

Brualdi and Hoffman (1985) proposed the problem of determining the maximal spectral radius of graphs with given size. In this paper, we consider the Brualdi-Hoffman type problem of graphs with given matching number. The maximal $Q$-spectral radius of graphs with given size and matching number is obtained, and the corresponding extremal graphs are also determined.

A fractional matching of a graph $G$ is a function $f:E(G) \to [0,1]$ such that for any $v\in V(G)$, $\sum_{e\in E_G(v)}f(e)\leq 1$ where $E_G(v) = \{e \in E(G): e$ is incident with $v$ in $G\}$. The fractional matching number of $G$ is $\mu_{f}(G) = \max\{\sum_{e\in E(G)} f(e): f$ is fractional matching of $G\}$. For any real numbers $a \ge 0$ and $k \in (0, n)$, it is observed that if $n = |V(G)|$ and $\delta(G) > \frac{n-k}{2}$, then $\mu_{f}(G)>\frac{n-k}{2}$. We determine a function $\varphi(a, n,\delta, k)$ and show that for a connected graph $G$ with $n = |V(G)|$, $\delta(G) \leq\frac{n-k}{2}$, spectral radius $\lambda_1(G)$ and complement $\overline{G}$, each of the following holds. (i) If $\lambda_{1}(aD(G)+A(G))<\varphi(a, n, \delta, k),$ then $\mu_{f}(G)>\frac{n-k}{2}.$ (ii) If $\lambda_{1}(aD(\overline{G})+A(\overline{G}))<(a+1)(\delta+k-1),$ then $\mu_{f}(G)>\frac{n-k}{2}.$ As corollaries, sufficient spectral condition for fractional perfect matchings and analogous results involving $Q$-index and $A_{\alpha}$-spectral radius are obtained, and former spectral results in [European J. Combin. 55 (2016) 144-148] are extended.

Let $q(G)$ denote the $Q$-index of a graph $G$, which is the largest signless Laplacian eigenvalue of $G$. We prove best possible upper bounds of $q(G)$ and best possible lower bounds of $q(\overline{G})$ for a connected graph $G$ to be $k$-connected and maximally connected, respectively. Similar upper bounds of $q(G)$ and lower bounds of $q(\overline{G})$ to assure $G$ to be super-connected are also obtained. Upper bounds of $q(G)$ and lower bounds of $q(\overline{G})$ to assure a connected triangle-free graph $G$ to be $k$-connected, maximally connected and super-connected are also respectively investigated.