Source author record

Jisu Jeong

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics Machine Learning Data Structures and Algorithms Information Retrieval Social and Information Networks

Catalog footprint

Research overview

7works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Metropolis-Hastings Data Augmentation for Graph Neural Networks

Graph Neural Networks (GNNs) often suffer from weak-generalization due to sparsely labeled data despite their promising results on various graph-based tasks. Data augmentation is a prevalent remedy to improve the generalization ability of models in many domains. However, due to the non-Euclidean nature of data space and the dependencies between samples, designing effective augmentation on graphs is challenging. In this paper, we propose a novel framework Metropolis-Hastings Data Augmentation (MH-Aug) that draws augmented graphs from an explicit target distribution for semi-supervised learning. MH-Aug produces a sequence of augmented graphs from the target distribution enables flexible control of the strength and diversity of augmentation. Since the direct sampling from the complex target distribution is challenging, we adopt the Metropolis-Hastings algorithm to obtain the augmented samples. We also propose a simple and effective semi-supervised learning strategy with generated samples from MH-Aug. Our extensive experiments demonstrate that MH-Aug can generate a sequence of samples according to the target distribution to significantly improve the performance of GNNs.

preprint2020arXiv

div2vec: Diversity-Emphasized Node Embedding

Recently, the interest of graph representation learning has been rapidly increasing in recommender systems. However, most existing studies have focused on improving accuracy, but in real-world systems, the recommendation diversity should be considered as well to improve user experiences. In this paper, we propose the diversity-emphasized node embedding div2vec, which is a random walk-based unsupervised learning method like DeepWalk and node2vec. When generating random walks, DeepWalk and node2vec sample nodes of higher degree more and nodes of lower degree less. On the other hand, div2vec samples nodes with the probability inversely proportional to its degree so that every node can evenly belong to the collection of random walks. This strategy improves the diversity of recommendation models. Offline experiments on the MovieLens dataset showed that our new method improves the recommendation performance in terms of both accuracy and diversity. Moreover, we evaluated the proposed model on two real-world services, WATCHA and LINE Wallet Coupon, and observed the div2vec improves the recommendation quality by diversifying the system.

preprint2019arXiv

Online Ramsey theory for a triangle on $F$ -free graphs

Given a class $\mathcal{C}$ of graphs and a fixed graph $H$ , the online Ramsey game for $H$ on $\mathcal C$ is a game between two players Builder and Painter as follows: an unbounded set of vertices is given as an initial state, and on each turn Builder introduces a new edge with the constraint that the resulting graph must be in $\mathcal C$ , and Painter colors the new edge either red or blue. Builder wins the game if Painter is forced to make a monochromatic copy of $H$ at some point in the game. Otherwise, Painter can avoid creating a monochromatic copy of $H$ forever, and we say Painter wins the game. We initiate the study of characterizing the graphs $F$ such that for a given graph $H$ , Painter wins the online Ramsey game for $H$ on $F$ -free graphs. We characterize all graphs $F$ such that Painter wins the online Ramsey game for $C_3$ on the class of $F$ -free graphs, except when $F$ is one particular graph. We also show that Painter wins the online Ramsey game for $C_3$ on the class of $K_4$ -minor-free graphs, extending a result by Grytczuk, Hałuszczak, and Kierstead.

preprint2016arXiv

Characterizing graphs of maximum matching width at most 2

The maximum matching width is a width-parameter that is defined on a branch-decomposition over the vertex set of a graph. The size of a maximum matching in the bipartite graph is used as a cut-function. In this paper, we characterize the graphs of maximum matching width at most 2 using the minor obstruction set. Also, we compute the exact value of the maximum matching width of a grid.

preprint2015arXiv

Maximum matching width: new characterizations and a fast algorithm for dominating set

We give alternative definitions for maximum matching width, e.g. a graph $G$ has $\operatorname{mmw}(G) \leq k$ if and only if it is a subgraph of a chordal graph $H$ and for every maximal clique $X$ of $H$ there exists $A,B,C \subseteq X$ with $A \cup B \cup C=X$ and $|A|,|B|,|C| \leq k$ such that any subset of $X$ that is a minimal separator of $H$ is a subset of either $A, B$ or $C$ . Treewidth and branchwidth have alternative definitions through intersections of subtrees, where treewidth focuses on nodes and branchwidth focuses on edges. We show that mm-width combines both aspects, focusing on nodes and on edges. Based on this we prove that given a graph $G$ and a branch decomposition of mm-width $k$ we can solve Dominating Set in time $O^*({8^k})$ , thereby beating $O^*(3^{\operatorname{tw}(G)})$ whenever $\operatorname{tw}(G) > \log_3{8} \times k \approx 1.893 k$ . Note that $\operatorname{mmw}(G) \leq \operatorname{tw}(G)+1 \leq 3 \operatorname{mmw}(G)$ and these inequalities are tight. Given only the graph $G$ and using the best known algorithms to find decompositions, maximum matching width will be better for solving Dominating Set whenever $\operatorname{tw}(G) > 1.549 \times \operatorname{mmw}(G)$ .

preprint2014arXiv

$(1, k)$ -coloring of graphs with girth at least $5$ on a surface

A graph is $(d_1, ..., d_r)$ -colorable if its vertex set can be partitioned into $r$ sets $V_1, ..., V_r$ so that the maximum degree of the graph induced by $V_i$ is at most $d_i$ for each $i\in \{1, ..., r\}$ . For a given pair $(g, d_1)$ , the question of determining the minimum $d_2=d_2(g; d_1)$ such that planar graphs with girth at least $g$ are $(d_1, d_2)$ -colorable has attracted much interest. The finiteness of $d_2(g; d_1)$ was known for all cases except when $(g, d_1)=(5, 1)$ . Montassier and Ochem explicitly asked if $d_2(5; 1)$ is finite. We answer this question in the affirmative with $d_2(5; 1)\leq 10$ ; namely, we prove that all planar graphs with girth at least $5$ are $(1, 10)$ -colorable. Moreover, our proof extends to the statement that for any surface $S$ of Euler genus $γ$ , there exists a $K=K(γ)$ where graphs with girth at least $5$ that are embeddable on $S$ are $(1, K)$ -colorable. On the other hand, there is no finite $k$ where planar graphs (and thus embeddable on any surface) with girth at least $5$ are $(0, k)$ -colorable.

preprint2014arXiv

Excluded vertex-minors for graphs of linear rank-width at most k

Linear rank-width is a graph width parameter, which is a variation of rank-width by restricting its tree to a caterpillar. As a corollary of known theorems, for each $k$ , there is a finite obstruction set $\mathcal{O}_k$ of graphs such that a graph $G$ has linear rank-width at most $k$ if and only if no vertex-minor of $G$ is isomorphic to a graph in $\mathcal{O}_k$ . However, no attempts have been made to bound the number of graphs in $\mathcal{O}_k$ for $k\ge 2$ . We show that for each $k$ , there are at least $2^{Ω(3^k)}$ pairwise locally non-equivalent graphs in $\mathcal{O}_k$ , and therefore the number of graphs in $\mathcal{O}_k$ is at least double exponential. To prove this theorem, it is necessary to characterize when two graphs in $\mathcal O_k$ are locally equivalent. A graph is a block graph if all of its blocks are complete graphs. We prove that if two block graphs without simplicial vertices of degree at least $2$ are locally equivalent, then they are isomorphic. This not only is useful for our theorem but also implies a theorem of Bouchet [Transforming trees by successive local complementations, J. Graph Theory 12 (1988), no. 2, 195-207] stating that if two trees are locally equivalent, then they are isomorphic.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Jisu Jeong

Research overview

Is this your work?

7 publications

Metropolis-Hastings Data Augmentation for Graph Neural Networks

div2vec: Diversity-Emphasized Node Embedding

Online Ramsey theory for a triangle on $F$ -free graphs

Characterizing graphs of maximum matching width at most 2

Maximum matching width: new characterizations and a fast algorithm for dominating set

$(1, k)$ -coloring of graphs with girth at least $5$ on a surface

Excluded vertex-minors for graphs of linear rank-width at most k

See the researcher in context

Building this map preview

Jisu Jeong

Research overview

Is this your work?

7 publications

Metropolis-Hastings Data Augmentation for Graph Neural Networks

div2vec: Diversity-Emphasized Node Embedding

Online Ramsey theory for a triangle on FFF-free graphs

Characterizing graphs of maximum matching width at most 2

Maximum matching width: new characterizations and a fast algorithm for dominating set

(1,k)(1, k)(1,k)-coloring of graphs with girth at least 555 on a surface

Excluded vertex-minors for graphs of linear rank-width at most k

See the researcher in context

Building this map preview

Online Ramsey theory for a triangle on $F$ -free graphs

$(1, k)$ -coloring of graphs with girth at least $5$ on a surface